数据结构试卷（一）一、选择题（每题2 分，共20分）1. 栈和队列的共同特点是（ A ）。A. 只允许在端点处插入和删除元素B. 都是先进后出C. 都是先进先出D. 没有共同点2. 用链接方式存储的队列在进行插入运算时（D）。A. 仅修改头指针B. 头、尾指针都要修改C. 仅修改尾指针D. 头、尾指针可能都要修改3. 以下数据结构中（D）是非线性结构。A. 队列B. 栈C. 线性表D. 二叉树4.设有一个二维数组Amn,假设A00的存放位置在644（10），A22的存放位置在676（10）, 每个元素占一个空间，那么A33（10）存放在（C）位置。脚注（10）表示用十进制表示。A. 688B. 678C. 692D. 6965. 树最适合用来表示（C）。A. 有序数据元素B. 无序数据元素C. 元素之间具有分支层次关系的数据D. 元素之间无联系的数据6. 二叉树的第k层的结点数最多为（D）。A. 2k-1B. 2K+1C. 2K-1D. 2k-17. 若有18个元素的有序表存放在一维数组A19中，第一个元素放在A1中，现进行二分 查找，则查找A3的比较序列的下标依次为（C）。A. 1， 2， 3B. 9，5，2，3C. 9，5，3D. 9，4，2，38. 对n个记录的文件进行快速排序所需要的辅助存储空间大致为(D)。A. O(1)B. O(n)C. O(1og2n)D. O(n2)9. 对线性表(7, 34，55, 25, 64, 46, 20, 10)进行散列存储时，若选用H(K)=K%9作为散列 函数，则散列地址为1的元素有(C)个。A. 1B. 2C. 3D. 410. 设有6个结点的无向图，该图至少应有(B)条边才能确保是一个连通图。A. 5B. 6C. 7D. 8二、填空题(每空 1 分,共26 分)1. 通常从4个方面评价算法的质量，即正确性、易读性、强壮性和高效性。2. 一个算法的时间复杂度为(n3+n2log2n+14n)/n2,其数量级表示_o (n)3. 假定一棵树的广义表表示为A(C, D(E, F, G), H(I, J),则树中所含的结点数为9个，树 的深度为3,树的度为3。4. 后缀算式9 2 3 +- 10 2 /-的值为4_。中缀算式(3+4X)-2Y/3对应的后缀算式为3 4 X * +2 Y 3 / * _。5. 若用链表存储一棵二叉树，每个结点除数据域外还有指向左孩子和右孩子的两个指针。 在这种存储结构中，n个结点的二叉树共有个指针域，其中有指针域存放了地址， 有个指针是空指针。6. 对于一个有n个顶点和e条边的有向图和无向图，在其对应的邻接表中所含的边结点分 别为e个和2e个。7. AOV网是一种没有回路的图。8. 在一个有n个顶点的无向完全图中包含有(n-1)/2_条边，在一个有n个顶点的有向完全 图中包含有_n(n-1)_条边。9. 假定一个线性表为(12,23,74,55,63,40),若按key % 4条件进行划分，使得同一余数的元素 成为一个子表，则得到的4个子表分别为_12, 40_、_虫_、74_和_23.55.63_。10. 在向一棵B-树插入元素的过程中若最终引起树根结点的分裂，则新树比原树的高度_多 1_。11. 在堆排序的过程中，对任一分支结点进行筛运算的时间复杂度为_OJognL_,整个堆排 序过程的时间复杂度为_o(nlog2m_。12. 在快速排序、堆排序、归并排序中归并排序是稳定的。三、计算题(每题6 分，共 24 分)1.在如图A.1所示的数组A中链接存储了一个线性表，表头指针为AO.next，试写出该线性表。60507S9034405724datariCTt图 A.1 数组 A线性表为：A3-A2-A7-A1-A5-A4-AO-A32请画出图A.2所示的邻接矩阵和邻接表。图 A.2 无向图 邻接矩阵：1111011101111111011101111邻接表：3.已知一个图的顶点集V和边集E如下：V=1,2,3,4,5,6,7;E=(1,2)3,(1,3)5,(1,4)8,(2,5)1O,(2,3)6,(3,4)15, (3,5)12,(3,6)9,(4,6)4,(4,7)2O,(5,6)18,(6,7)25; 用克鲁斯卡尔算法得到最小生成树，试写出在最小生成树中依次得到的各条边。O,3）2（4,6）4（O,2）5（1,5）6（O,1）8（3,6）1O（5,7）2O 4.画出向小根堆中加入数据4、 2、 5、 8、 3时每加入一个数据后堆的变化。四、阅读算法(每题7 分，共14分)1.1 def mynote(L):2 # L是不带头结点的单链表的头指针3 if L is not None and L.next is not None:4 q = L5 l = L.nex t6 p 二 L7 while p.nex t:8 p 二 p.next # SI9 p.next 二 q10 q.next 二 None11 return L请回答下列问题：(1)(2)(3)答说明语句S1的功能； 说明语句组S2的功能；设链表表示的线性表为(a1,a2, .,an),写出算法执行后的返回值所表示的线性表。(1) 找到链表的最后一个节点。 将链表的最后一个节点指向L,并将L的下一节点清空。(3) a2,.,an,a1。2.1 def ABC (BT):2 # BT是二叉树的结点3 if BT is not None:4 ABC(BT.lchild)ABC(BT.rchild)print (BT.data, end二)该算法的功能是一打印二叉树各节点的值_。五、算法填空（共8 分） 二叉搜索树的查找递归算法:1 def Find(BST, item):2 # BST是搜索二叉树的结点，item是查找的元素3 if BST is None:4 ret urn false # 查找失败5 if item 二二 BST.data:6 item 二 BST.data # 查找成功return true8 elif it emBST.da ta:9 ret urn Find(BST-lef t,it em)10 else:11return Find(BST-right,item)六、编写算法(共8 分)统计出单链表 HL 中结点的值等于给定值 X 的结点数定义函数如下：def is_count(self, X):cur = self._headcount = 0while cur is not None: if cur.data = X:count+=1 cur = cur.next return count