数据结构1-4章习题答案

第1章 概 论 习题参考解答

一、填空题

1、数据的逻辑结构是数据元素之间的逻辑关系，通常有下列4类：（ ）、（ ）、（ ）、（ ）。

【答】 集合、线性结构、树型结构和图状结构。

2、数据的存储结构是数据在计算机存储器里的表示，主要有4种基本存储方法：（ ）、（ ）、（ ）、（ ）。

【答】 顺序存储方法、链接存储方法、索引存储方法和散列存储方法。 二、选择题

1、一个算法必须在执行有穷步之后结束，这是算法的（ ）。 （A）正确性 （B）有穷性 （C）确定性 （D）可行性 【答】 B。

2、算法的每一步，必须有确切的定义。也就是说，对于每步需要执行的动作必须严格、清楚地给出规定。这是算法的（ ）。

（A）正确性 （B）有穷性 （C）确定性 （D）可行性 【答】 C。

3、算法原则上都是能够由机器或人完成的。整个算法好像是一个解决问题的“工作序列”，其中的每一步都是我们力所能及的一个动作。这是算法的（ ）。

（A）正确性 （B）有穷性 （C）确定性 （D）可行性 【答】 D。 三、简答题

1、 算法与程序有何异同？

【答】 尽管算法的含义与程序非常相似，但两者还是有区别的。首先，一个程序不一定满足有穷性，因此它不一定是算法。例如，系统程序中的操作系统，只要整个系统不遭受破坏，它就永远不会停止，即使没有作业要处理，它仍处于等待循环中，以待一个新作业的进入。因此操作系统就不是一个算法。其次，程序中的指令必须是计算机可以执行的，而算法中的指令却无此限止。如果一个算法采用机器可执行的语言来书写，那么它就是一个程序。

2、 什么是数据结构？试举一个简单的例子说明。

【答】 数据结构是指数据对象以及该数据对象集合中的数据元素之间的相互关系（即数据元素的组织形式）。例如，队列的逻辑结构是线性表（先进先出）；队列在计算机中既可以采用顺序存储也可以采用链式存储；对队列可进行删除、插入数据元素以及判断是否为空队列、将队列置空等操作。

3、 什么是数据的逻辑结构？什么是数据的存储结构？

【答】 数据元素之间的逻辑关系，也称为数据的逻辑结构。数据元素以及它们之间的相互关系在计算机存储器内的表示（又称映象），称为数据的存储结构，也称数据的物理结构。

4、 什么是算法？算法有哪些特性？

【答】 算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作；此外，一个算法还具有下列5个特性：

①有穷性：一个算法必须在执行有穷步之后结束，即算法必须在有限时间内完成。 ②确定性：算法中每一步必须有确切的含义，不会产生二义性。并且，在任何条件下，算法只有唯一的一条执行路径，即对于相同的输入只能得出相同的输出。

③可行性：一个算法是能行的，即算法中的每一步都可以通过已经实现的基本运算执行有限次得以实现。

④输入：一个算法有零个或多个输入，它们是算法开始时对算法给出的初始量。 ⑤输出：一个算法有一个或多个输出，它们是与输入有特定关系的量。 四、算法分析题

1、将下列复杂度由小到大重新排序：2n、n!、n2、10000、log2n、n×log2n。 【答】 10000< log2n< n×log2n < n2<2n < n!。 2、用大“O”表示法描述下列复杂度： ⑴ 5n5/2+n2/5 【答】 O(n5/2)。 ⑵ 6×log2n+9n 【答】 O(n)。 ⑶ 3n4+n×log2n 【答】 O(n4)。

⑷ n×log2n+n×log3n 【答】 O(n×log2n)。

3、设n为正整数，请用大“O”表示法描述下列程序段的时间复杂度。 ⑴ i=1; k=0; ⑵ i=0; k=0; while(i

} }while(i

⑶ i=1; j=0; ⑷ x=n; /*n是常数且n>1*/ while(i+j<=n) while(x>=(y+1)*(y+1)) {if(i>j) j++; y++; else i++ }

【答】 O(n)。 【答】 O(n)。

⑸ for((i=1; i<=n; i++) ⑹ x=91; y=100;

for(j=1; j<=i; j++) while(y>0)

for(k=1; k<=j; k++) {if(x>100) {x-=10; y--;} x+=c; (c为常数) else x++; }

【答】 O(n3)。 【答】 O(n)。

第2章 线 性 表 习题参考解答

一、 简答题

1．试描述头指针、头结点、开始结点的区别、并说明头指针和头结点的作用。 【答】头指针：是指向链表中的第一个结点的指针。 头结点：在开始结点之前附加上的一个结点。 开始结点：链表的第一个结点。

头指针是一个指向地址的变量，用于表示一个链表的开始。引入头结点可以更加方便的进行链表是否为空的判断，同时方便了插入和删除结点。开始结点用于存储链表的第一个数据元素。

2．何时选用顺序表、何时选用链表作为线性表的存储结构为宜?

【答】顺序表中查找元素、获取表长非常容易，但是，要插入或者删除一个元素却需要移动大量的元素；相反，链表中却是方便插入或者删除元素，在查找元素的是，需要进行遍历。因此，当所涉及的问题常常进行查找等操作，而插入、删除相对较少的是，适合采用顺序表；当常常需要插入、删除的时候，适合采用链表。

3．为什么在单循环链表中设置尾指针比设置头指针更好?

【答】在单循环链表中，设置尾指针，可以更方便的判断链表是否为空。

4．在单链表、双链表和单循环链表中，若仅知道指针p指向某结点，不知道头指针，能否将结点*p从相应的链表中删去?

【答】本题分三种情况讨论：

1、单链表：当知道指针p指向某结点时，能够根据该指针找到其直接后继，但是

不知道头指针，因此不能找到该结点的直接前趋，因此，无法删除该结点。

2、双链表：根据指针p可以找到该结点的直接前趋和直接后继，因此，能够删除

该结点。

3、单循环链表：和双链表类似，根据指针p也可以找到该结点的直接前趋和直接

后继，因此，也可以删除该结点。

5．下述算法的功能是什么?

LinkList Demo(LinkList *L) /* L是无头结点单链表*/ {

LNode *Q,*P; if(L&&L->next) {

Q=L;L=L->next;P=L; while (P->next) P=P->next;

P->next=Q; Q->next=NULL; }

return L; } /* Demo */

【答】将原来的第一个结点变成末尾结点，原来的第二个结点变成链表的第一个结点。 二、算法设计题

1．试分别用顺序表和单链表作为存储结构，实现将线性表(a0,a1,...an-1)就地逆置的操作，所谓\就地\指辅助空间应为O(1)。 【答】分两种情况讨论如下。 ① 顺序表：

要将该表逆置，可以将表中的开始结点与终端结点互换，第二个结点与倒数第二个结点互换，如此反复，就可将整个表逆置了。算法如下：

void reverlist(sequenlist *L) {

datatype t; /* 设置临时空间用于存放data */ int i;

for (i=0;ilength/2;i++) { t=L->data[i]; /* 交换数据 */

L->data[i]=L->data[L->length-1-i]; L->data[L->length-1-i]=t; } }

② 链表：

可以利用指针的指向转换来达到表逆置的目的。算法是这样的： LinkList *reverselist(LinkList *head) /* 将head 所指的单链表逆置 */

{ LNode *p,*q ; /* 设置两个临时指针变量 */

if((head->next!=NULL) && (head->next->next!=NULL)) /* 当链表不是空表或单结点时 */ { p=head->next; q=p->next;

p->next=NULL; /*将开始结点变成终端结点 */ while (q) /* 每次循环将后一个结点变成开始结点 */ { p=q; q=q->next;

p->next= head-> next; head->next=p; }

return head; }

return head; /* 如是空表或单结点表，直接返回head */ }

2．顺序表L是一个递增有序表，试写一算法，将x插入L中，并使L仍是一个有序表。

【答】因已知顺序表L是递增有序表，所以只要从头找起找到第一个比它大（或相等）