数据结构精品课程习题

（2）GET（L，4）=（ ）。

A.a B.d C.h D. 8

(3)INSERT（L，W，4）；GET（L，4）的值为（ ）。

A. a B.d C.w D.8

(4)DELETE（L，1）；GET（L，1）的值为（ ）。

A.a B.b C.w D.8 2、单链表表示意图如下：

L 2 5 (1)表

7 null P Q R 头指针（ ）。

A.L B.P C.Q D.R （2）指向链表首结点的指针是（ ）。

A.L B.P C.Q D.R

（3）指向链表Q结点的前驱的指针是（ ）。

A.L B.P C.Q D.R

（4）指向链表Q结点的后继的指针是（ ）。

A.L B.P C.Q D.R

3、在一个具有n个结点的有序单链表中插入一个新结点，并使插入后仍然有序，则该操作的时间复杂性量级为（ ）。

A.0(1) B.0(n) C.0(nlog2n) D.0(n2)

4、顺序存储的线性表(a1,a2,?an)，在任一结点前插入一个新结点时所需移动结点的平均次数为（ ）。

A.n B.n/2

C.n+1 D.(n+1)/2

5、线性表L=（a,b,c,d,e），经运算Delete(L，3)后，L表等于（ ）。

A.(a,b,d,e) B.(a,b,c,d) C.(b,c,d,e) D.(d,e)

6、L是线性表，已知Length(L)的值是5，经运算Ddelete(L,2)，后Length(L)的值是（ ）。

A.5 B.0 C.4 D.6

5

7、线性表中（ ）只有一个直接前驱和一个直接前驱和一个直接后继。

A.首元素 B.尾元素 C.中间的元素 D.所有的元素 8、下列说法正确的是（ ）。

A.线性表的逻辑顺序与存储顺序总是一致的

B.线性表的链式存储结构中，要求内存中可用的存储单元可以是连续的，也可以不连续

C.线性表的顺序存储结构优于链式存储结构

D.每种数据结构都具有插入、删除和查找三种基本运算

9、设非空单链表的数据域为data，指针域为next，指针p指向单链表中第i个结点，s指向已生成的新结点，现将s结点插入到单链表中，使其成为i个结点，下列算法段能正确完成上述要求的是（ ）

A.s-﹥next=p-﹥next=s; B.p-﹥next=s;s-﹥next=p-﹥next;

C.s-﹥next=p-﹥next=s;交换p-﹥data和 s-﹥data; D.p=s;s-﹥next=p;

10、指针p指向循环链表L 的首元素的条件是（ ）。

A.p= =L

B. p -﹥n e x t= =L C.L -﹥n e x t= =p D.p-﹥n e x t= =NULL

11、线性表中各元素之间的关系是（ ）关系。

A.层次 B.网状 C.有序 D.集合

12、假设left和right为双向链表中指向直接前趋结点和直接后继结点的指针域，现要指一个指针s所指的新结点作为非空双链表中q所指结点（中间结点）的直接后继结点插入到该双向链表中，则下列算法段能正确完成上述要求的是（ ）。

A.q-﹥right=sls-﹥left=q;q-﹥right-﹥;left=s;s-﹥right=q-﹥right; B.s-﹥left=q;q-﹥right=s;q-﹥right-﹥left=s;s-﹥right=q-﹥right; C.s-﹥left=q;s-﹥right=q-﹥right;q-﹥right-﹥left=s;q-﹥right=s;

6

D.以上都不对

13、在单链表的一个结点中有（ ）个指针。

A.1 B.2 C.0 D.3

14、设双链表中结点的前趋指针和后继指针的域名分别为t1和r1，则删除双链表中指针s所指结点的操作为（ ）。

A.s-﹥tl-﹥r1=s-﹥tl;s-﹥rl-﹥tl=s-﹥rl; B.s-﹥tl-﹥rl=s-﹥rl;s-﹥rl-﹥tl=s-﹥tl; C.s-﹥rl=s-﹥tl-﹥rl;s-﹥tl=s-﹥rl-﹥tl; D.s-﹥tl=s-﹥tl-﹥rl;s-﹥rl=s-﹥rl-﹥tl

15、 指针P 所指的元素是双向循环链表L的尾元素的条件是（ ）。

A.P= =L B.P= =NULL C.P-﹥Llink==L D.P-﹥Rlink==l

16、P和我两个指针分别指向双向循环表L的两个元素，P所指元素是Q所指元素的后继的条件是（ ）。

A.P= =Q B.Q-﹥Rlink==P

C.P-﹥Rlink==q D.Q-﹥Rlink==P-﹥Rlink

17、两指针P和Q，分别指向单链表的两个元素，P所指元素是Q所指元素的前导的条件是（ ）。

A.p-﹥next==q B.Q-﹥next==p C.P= =Q D.P-﹥next==q-﹥next 18、指针P指向线性链表L的首元素的条件是（ ）。

A.P= =L B.L-﹥Next==P C.P-﹥next==L D.P-﹥next==NULL

19、L=(a,b,c,d,e,f)，函数Length(L)的值是（ ）。

A.1 B.TRUE C.6 D.C

20、已知s=‘a b c’,t=‘x y ’经运算ASSIGN(t, s)后，s的值是（ ）。

A.‘a b c’ B. ‘x y’ C. ‘a b c x y’ D. ‘x y a b c’

21、串S=‘abcdefg’，经DELETE（S，2）后S=（ ）。

7

A. ‘AEFG’ B. ‘abcd’ C. ‘’acdefg D. ‘ABCD’

22、replace(‘abacd’, ‘a’, ‘d’)的值是（ ）。

A. ‘a’ B. ‘d’ C. ‘dbacd’ D. ‘dbdcd’

23、吕、串S=‘abbcabdf’经运算REPLACE（S，‘ab’, ‘xy’）后S=（ ）。

A. ‘xybcxydf’ B. ‘xybcabdf’ C. ‘abbcxydf’ D. ‘abbcabdf’ 24、在数据结构中，（ ）不都是线性结构。

A栈和队列 B.队列和数组 C.数组和串 D.文件和队列 二、填空题

1、Insert sqlist(L,X,i)的时间复杂度为0( )。 2、Delete sqlist(L,i)的时间复杂度为0（ ）。

3、顺序表中逻辑上相邻的元素在物理位置上 相连。 4、链表中逻辑上相邻的元素的物理位置 相连。

5、在单链表中除首结点外，任意结点的存储位置都 由结点中的指针指示。

6、在单链表中，设置头结点的作用是在插入或删除头结点时不必对 进行处理。

7、已知带表头结点的单链表L，指针P指向L链表中的一个结点，指针Q是指向L镕表外的一个结点，则：

（1）在指针P所指结点后插入Q所指结点的语句序列是 ； （2）在指针P所指结点前插入Q所指结点的语句序列是 ； （3）将Q所指结点插入在链表首结点的语句序列是 ； （4）将Q所指结点插入在链表尾结点的语句序列是 。

8、书籍带头结点的单链表L，指针P指向L链表中的一个结点为（非首结点、非尾结点），则

（1）删除P结点的直接后继结点的语句是 ；

8