2024年4月自考02142《数据结构导论》之选择填空题

一、单项选择题：本大题共15小题，每小题2分，共30分。在每小题列出的备选项中只有一项是最符合题目要求的，请将其选出。

1、在数据结构中，数据的基本单位是

A.数据项 B.数据元素 C.数据类型 D.数据变量

2、在下列数据的逻辑结构中，结构最复杂的是

A.图结构 B.集合 C.线性结构 D.树形结构

3、对长度为n的顺序表实现给定操作的算法中，平均时间复杂度为O(1)的是

A.查找包含指定值元素的算法

B.获取第i(1≤i≤n)个元素的算法

C.在第i(1≤i≤n+1)个元素之前插入一个新元素x的算法

D.删除第i(1≤i≤n)个元素的算法

4、在单链表中，指针域为next,在p指向的结点之后插入结点q的代码是

A.q->next-p->next;p->next=q;

B.p->next=q;q->next-p->next;

C.q->next=p;p->next=q;

D.p->next=q;q->next-p;

5、下列有关队列的叙述，正确的是

A.队列属于非线性表

B.队列在队尾删除数据

C.队列在队首插入数据

D.队列按“先进先出”原则组织数据

6、按照“后进先出”原则组织数据的数据结构是

A.队列 B.栈 C.双向链表 D.二叉树

7、设初始栈为空，s表示入栈操作，x表示出栈操作，则合法的操作序列是

A.sssXXxsx B.ssxsxxxs

C.ssxxxssx D.sxXssxxs

8、二叉树中第5层(根的层号为1)上的结点个数最多为

A.8个 B.15个 C.16个 D.32个

9、二叉树若采用二叉链表存储结构，则对于n个结点的二叉树一定有

A.2n-1个指针域，其中n个指针域为NULL

B.2n-1个指针域，其中n+1个指针域为NULL

C.2n个指针域，其中n个指针域为NULL

D.2n个指针域，其中n+1个指针域为NULL

10、n个顶点的强连通图中至少含有

A.n-1条弧 B.n条弧

C.n(n-1)/2条弧 D.n(n-1)条弧

11、n个顶点的连通图用邻接矩阵表示时，该矩阵中的非零元素至少有

A.n—1个 B.n个

C.2(n-1)个 D.n(n-1)2个

12、若构造一棵具有n个结点的二叉排序树，最坏的情况下其深度不会超过

A.n/2 B.(n+1)/2 C.n-1 D.n

13、对含有64个数据元素的有序表进行顺序查找，在最坏情况下所需要的比较次数为

A.6次 B.7次 C.63次 D.64次

14、归并排序算法的时间复杂度是

A.O(log,n) B.O(n) D.O(n²) C.O(nlog₂n)

15、采用冒泡排序方法对7个记录进行排序，需要进行的键值比较次数是

A.7次 B.14次 C.21次 D.49次

参考答案：

1-5：BABAD

6-10：BACDB

11-15：CDDCC

二、填空题：本大题共13小题，每小题2分，共26分。

16、一个算法通常可从正确性、易读性、健壮性和_____等四个方面评价和分析。

17、在长度为n的顺序表中删除一个元素需移动元素的平均次数为______次。

18、设带头结点的单向循环链表的头指针为head,则空循环链表的判定条件是_____。

19、设某循环队列CQ的容量maxsize为50,队列首指针CQ.front=5(指向队首元素的前一位置),队列尾指针CQ.rear=29(指向队尾元素),则该循环队列中共有_____个元素。

20、设有二维数组int a[10][20],每个数组元素占4个存储单元，数组元素a[0][0]的存储位

置为2000,则数组元素a[5][10]的存储位置为______。

21、某二叉树有5个度为2的结点，3个度为1的结点，则该二叉树中共有_____个结点。

22、已知某完全二叉树的第6层(设根为第1层)有8个叶结点，则该完全二叉树的结点个数最多是______。

23、在有n个顶点的有向图中，每个顶点的度最大可达______。

24、已知有向图G=(V,A),其中V={a,b,c,d,e,f,g},A={,,

,,),则该有向图可以排出______种不同的拓扑序列。

25、在有序表(7,12,15,18,27,32,41,92)中用二分查找法查找和键值32相等的数据元素，在查找过程中依次和键值32比较的键值为____。

26、已知某长度为11的散列表，其散列函数为H(key)=key mod 11,在表中已填入键值分别

为15、27、39的元素，其余地址为空，若采用线性探测法处理冲突，则键值为60的元素保存的地址是______。

27、对初始关键字序列{45,39,72,98,24)的记录，按关键字升序的方式进行直接选择排序，

第一次选择后的结果是______。

28、对初始关键字序列{45,39,72,98,24}的记录，按关键字升序的方式进行快速排序，以

第一个记录关键字45为基准得到的一次划分结果为______。

参考答案：

16、时空性

17、(-1)/2

18、head->next=-head

19、24

20、2440

21、14

22、111

23、2(n-1)

24、12

25、18、32

26、7

27、24,39,72,98,45

28、24,39,45,98,72