数据结构(第二版)习题答案第3章

第 3 章 线性表的链式存储

选择题

（1）两个有序线性表分别具有 n 个元素与 m 个元素且 n≤m，现将其归并成一个有序表， 其最少的比较次数是（ A ）。

A．n B．m C．n 1 D．m + n

（2）非空的循环单链表 head 的尾结点（由 p 所指向）满足（ C ）。

A．p->next==NULL B．p==NULL C．p->next==head D．p==head （3）在带头结点的单链表中查找 x 应选择的程序体是（ C ）。

A．node *p=head->next; while (p && p->info!=x) p=p->next;

if (p->info==x) return p else return NULL;

B．node *p=head; while (p&& p->info!=x) p=p->next; return p; C．node *p=head->next; while (p&&p->info!=x) p=p->next; return p; D．node *p=head; while (p->info!=x) p=p->next ; return p;

（4）线性表若采用链式存储结构时，要求内存中可用存储单元的地址（ D ）。

A．必须是连续的 B．部分地址必须是连续的 C．一定是不连续的 D．连续不连续都可以

（5）在一个具有 n 个结点的有序单链表中插入一个新结点并保持单链表仍然有序的时间 复杂度是（ B ）。

A．O(1) B．O(n) C．O(n2) D．O(nlog2n)

（6）用不带头结点的单链表存储队列时，其队头指针指向队头结点，其队尾指针指向队 尾结点，则在进行删除操作时（ D ）。

A．仅修改队头指针 B．仅修改队尾指针 C．队头、队尾指针都要修改 D．队头,队尾指针都可能要修改 （7）若从键盘输入 n 个元素，则建立一个有序单向链表的时间复杂度为（ B ）。

A．O(n) B．O(n2) C．O(n3) D．O(n × log2n)

（8）下面哪个术语与数据的存储结构无关（ D ）。

D．队列 A．顺序表 B．链表 C．散列表

（9）在一个单链表中，若删除 p 所指结点的后续结点，则执行（ A ）。

A．p->next=p->next->next; B．p=p->next; p->next=p->next->next; C．p->next=p->next; D．p =p->next->next;

（10）在一个单链表中，若 p 所指结点不是最后结点，在 p 之后插入 s 所指结点，则执行（ B ）。

A．s->next=p;p->next=s; B．s->next=p->next;p->next=s; C．s->next=p->next;p=s; D．p->next=s;s->next=p;

设计一个算法，求一个单链表中的结点个数。 【答】：单链表存储结构定义如下（相关文件：） #include <>

11

#include <>

typedef struct node { int data;

struct node *next; }linknode;

typedef linknode *linklist;

/*尾插法创建带头结点的单链表*/ linklist creatlinklist() { linklist head,r,x,s;

head=r=(linklist)malloc(sizeof(linknode));

printf(\请输入一组以 0 结束的整数序列：\\n\ scanf(\ while (x)

{ s=(linklist)malloc(sizeof(linknode)); s->data=x; r->next=s; r=s;

scanf(\

}

r->next=NULL; return head; }

/*输出带头结点的单链表*/ void print(linklist head) { linklist p; p=head->next; printf(\ while(p)

{ printf(\ p=p->next;

}

printf(\ }

基于上述结构定义，求单链表中的结点个数的算法程序如下：int count(linklist head) { int c=0;

linklist p=head; while (p) {c++;

12

p=p->next;

}

return c; }

设计一个算法，求一个带头结点单链表中的结点个数。

【答】：带头结点的单链表的存储结构定义同题 ，实现本题功能的算法程序如下（） #include \

int count(linklist head) { int c=0;

linklist p=head->next; while (p) {c++; p=p->next;

}

return c; }

main() /*测试函数*/ {linklist head;

head=creatlinklist(); print(head);

printf(\ getch(); }

当输入 5 个数据时，产生的输出结果如下图所示：

设计一个算法，在一个单链表中值为 y 的结点前面插入一个值为 x 的结点。即使值为 x 的 新结点成为值为 y 的结点的前驱结点。 【答】： #include \

void insert(linklist head,int y,int x)

{/*在值为 y 的结点前插入一个值为 x 的结点*/ linklist pre,p,s; pre=head; p=head->next;

13

while (p && p->data!=y) { pre=p; p=p->next; }

if (p)/*找到了值为 y 的结点*/

{ s=(linklist)malloc(sizeof(linknode)); s->data=x; s->next=p; pre->next=s; } }

void main() /*测试程序*/ {linklist head; int y,x;

head=creatlinklist(); /*创建单链表*/

print(head); /*输出单链表*/

printf(\请输入 y 与 x 的值:\\n\ scanf(\ insert(head,y,x); print(head); }

程序的一种运行结果如下图所示：

设计一个算法，判断一个单链表中各个结点值是否有序。 【答】： #include \

int issorted(linklist head,char c)

/*当参数 c=’a’时判断链表是否为升序，当参数 c=’d’是判断链表是否为降序*/ { int flag=1;

linklist p=head->next; switch (c)

{case 'a':/*判断带头结点的单链表 head 是否为升序*/

14