2024年4月重庆自考02142数据结构导论试题考试试卷

2024年4月高等教育自学考试
数据结构导论试题
课程代码：02142
1.请考生按规定用笔将所有试题的答案涂、写在答题纸上。
2.答题前，考生务必将自己的考试课程名称、姓名、准考证号用黑色字迹的签字笔或钢笔 填写在答题纸规定的位置上。
选择题部分
注意事项：
每小题选出答案后，用2B 铅笔把答题纸上对应题目的答案标号涂黑。如需改动，用橡皮 擦干净后，再选涂其他答案标号。不能答在试题卷上。
 
一 、单项选择题：本大题共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. 队列按“先进先出”原则组织数据
 02142#数据结构导论试题第1页(共4页)

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)
C.O(nlog₂n)                                                         D.O(n²)
15. 采用冒泡排序方法对7个记录进行排序，需要进行的键值比较次数是
A.7   次                                B.14 次
C.21 次                                D.49  次
 
 02142#数据结构导论试题第2页(共4页)

非选择题部分
注意事项：
用黑色字迹的签字笔或钢笔将答案写在答题纸上，不能答在试题卷上。
二 、填空题：本大题共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为基准得到的一次划分结果为        _。
三、应用题：本大题共5小题，每小题6分，共30分。
29. 有5个元素，其入栈次序为：A、B、C、D、E,  写出以元素 C、D 最先出栈(即C 第
一个且D 第二个出栈)的各种可能的出栈次序。
30. 假设某通信系统中电文使用的字符集为{A,B,C,D,E,F,G,H},        各字符在电文中出现的 频率分别为：0.07,0.19,0.02,0.06,0.32,0.03,0.21和0.10。试画出哈夫曼树(要 求树中任一结点的左孩子结点的权值不小于其右孩子结点的权值),并按左分支为0和
右分支为1的规则分别写出与每个字符对应的哈夫曼编码。
 02142#数据结构导论试题第3页(共4页)