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

不飞则已，一飞冲天；不鸣则已，一鸣惊人。——《韩非子》

第3章线性表的链式存储

3.1选择题

（1）两个有序线性表分别具有n个元素与m个元素且n≤m，现将其归并成一个有序表，

其最少的比较次数是（A）。

A．nB．mC．n−1D．m+n

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

A．p-next==NULLB．p==NULLC．p-next==headD．p==head

（3）在带头结点的单链表中查找x应选择的程序体是（C）。

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

if(p-info==x)returnpelsereturnNULL;

B．node*p=head;while(pp-info!=x)p=p-next;returnp;

C．node*p=head-next;while(pp-info!=x)p=p-next;returnp;

D．node*p=head;while(p-info!=x)p=p-next;returnp;

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

A．必须是连续的B．部分地址必须是连续的

C．一定是不连续的D．连续不连续都可以

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

复杂度是（B）。

A．O(1)B．O(n)C．O(n)D．O(nlog

2

2n)

（6）用不带头结点的单链表存储队列时，其队头指针指向队头结点，其队尾指针指向队

尾结点，则在进行删除操作时（D）。

A．仅修改队头指针B．仅修改队尾指针

C．队头、队尾指针都要修改D．队头,队尾指针都可能要修改

（7）若从键盘输入n个元素，则建立一个有序单向链表的时间复杂度为（B）。

A．O(n)B．O(n)C．O(n)D．O(n×log2)

23n

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

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

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

A．p-next=p-next-next;B．p=p-next;p-next=p-next-next;