2024年4月安徽自学考试数据结构导论试题 课程代码：02142

绝密★考试结束前2024年4月高等教育自学考试数据结构导论试题课程代码：021421.请考生按规定用笔将所有试题的答案涂、写在答题纸上。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.SsxsxxxsC.ssxxxssx D.sxxssxxs8. 二叉树中第5层(根的层号为1)上的结点个数最多为A.8个B.15个C.16个 D.32个9. 二叉树若采用二叉链表存储结构，则对于n 个结点的二叉树一定有A.2n-1 个指针域，其中n 个指针域为NULLB.2n-1个指针域，其中n+1 个指针域为NULLC.2n个指针域，其中n个指针域为NULLD.2n 个指针域，其中n+1个指针域为NULL10.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)/2C.n-1D.n13.对含有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.设有二维数组inta[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)=keymod11,在表中已填入键值分别为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页)

31.某有向图G如题31图所示，试画出图G的邻接表存储结构。题31图32.已知一棵二叉排序树(结点值大小按字母顺序)的先序遍历序列为FBADCEGH, 试画出此二叉排序树，并且写出此二叉排序树的后序遍历序列。33. 对关键字序列{72,87,61,23,94,16,5,58}进行堆排序，使之按关键字递减次序排列。写出排序过程中得到的初始堆和前两趟排序后的序列状态。四、算法设计题：本大题共2小题，每小题7分，共14分。34. 已知单链表的类型定义如下：typedefintDataType;typedefstructnode{DataTypedata;structnode*next;}LinkNode,*LinkList;编写一个函数 DataTypeminValue(LinkListL), 求非空的带头结点单链表L中各结点data域的最小值。35. 已知二叉树的存储结构类型定义如下：TypedefstructbtnodeDataTypedata:Structbtnode*lchild,*rchild;}*BinTree;编写递归算法intCountD2Node(BinTreebt),求二叉树 bt中所有度为2的结点的个数。02142#数据结构导论试题第4页(共4页)