深圳开放大学 数据结构复习题-答案.docx

数据结构复习题2020秋季

（参考答案）

绪论

一、选择题

1、B.物理结构

2、D.数据项可由若干个数据元素构成

3、A.数据元素

4、D.逻辑结构

5、C.可读性

6、B.算法本身

7、B.O(log2n)

8、B.O(log2n)

10、C.内部结构和外部结构

11、B.n2/2

12、A.数据元素间的关系的表示

13、B.多对多

14、A.与存储该逻辑结构的计算机相关

15、B.数据元素的存储

二、判断题

1.×

2.?

3.×

4.?

5.×

6.×

7.?

8.×

9.×

10.×

11．×

12.×

13.×

14.×

15．×

三、程序题

1、答案：O(log2n)

2、答案：O(log2n)

3、答案：O(n!)

4、答案：O(n)

第二章线性表

一、选择题

1、C.n-i+1

2、C.n-i

3、B.p-next=q-next

4、C.s-next=p-next;p-next=s;

5、A.p-next==head

6、B.可随机访问任一元素

7、A.head-next==head

8、C.20

9、D.除了一个和最后一个元素外，其余元素都有一个且仅有一个直接前驱和一个直接后继

10、A.63.5

11、A.106

12、A.q-next=p

13、D.逻辑上相邻的元素在物理位置上也相邻

14、A.不能随机访问任一结点

15、A.n-i+1

16、A.HL=p;p-next=HL;

17、D.q-next=s；s-next=p；

18、B.p-right=s；p-right-left=s；s-left=p；s-right=p-right；

19、B.只有1个元素；

20、B.HL-next==NULL

21、D.p-next=head;

二、判断题

1、?

2、 ?

3、 ?

4、 ×

5、 ?

6、?

7、 ?

8、 ×

9、 ×

10、?

三、程序填空

1、

答案：（1）pdata（2）p=pnext（3）p!=NULL

2、

答案：（4）qnext!=NULL（5）p=pnext（6）qnext=s

3、

答案：（7）p=p-next;（8）p-data或prep-data（9）p-next

第三章数组和广义表

一、选择题

1．C．3，1，2

2．B．1，2，3，4

3.B．40,30,50,10,20

4.D．10，8，6，4

5．A．先移动栈顶指针，再存入元素

6．C．p-next=top;top=p;

7．D．x=top-data;top=top-next;

8．A．栈

9．B．abc+*d-

10．C．sq-front==sq-rear

11．C．Q-front==(Q-rear+1)%m

12．C．s-top==n-1

13．B．a,b,c,d

14．C．必须判断栈是否空

15．B．队列

16．D．终止条件和迭代部分

17．A．x=top-data;top=top-next;

18．C．f=f-next;

19．B．r-next=s;r=s;

20．C．x=f-data；f=f-next;

21．C．只容许在端点处插入和删除元素

22．A．栈顶

23．A．前一个

24．B.n-1

25．A.队头指针加一

判断题

1.?

2.×

3.?

4.×

5.×

6.?

7.×

8.?

9.×

?

×

×

13.?

14.?

?

×

?

?

三、程序选择题

1．C.q-rear=q-front;

2.D.(1)Q-queue[Q-rear]=x;(2)Q-front==Q-rear

3.B.121553018

4.A.151285133

5.C.s-top++;

6.A.s-top--;

第四章字符串

一、选择题

1．A．串是一种特殊的线性表

2．C．匹配

3．D．有限个字符的序列

4．D．串中所含非空格字符的个数

5.D．28

6．B．空串是由空格构成的串

7．C．数据元素是一个字符

8．B．不相同

9．D．两串的长度相等