全国2010年10月自考数据结构导论考试试题,答案,笔记

1、全国2021年10月高等教育自学考试数据结构导论试题课程代码：02142一、单项选择题(本大题共 1515 小题，每题 2 2 分，共 3030 分)在每题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多项选择或未 选均无分。1.1.以下描述中正确的选项是 ( (C C ) )A.数据元素是数据的最小单位 -数据项是数据的最小单位B.数据结构是具有结构的数据对象C.数据结构是指相互之间存在一种或多种特定关系的数据元素的集合D.算法和程序原那么上没有区别，在讨论数据结构时两者是通用的4 4 .顺序存储的表中有 9000090000 个元素，已按关键字值升序排列，

2、假设对每个元素进行查找的概率相同，且每个元素的 关键字值皆不相同，用顺序查找法查找时，需平均比拟的次数为( (C C ) )A. 25000B.30000C.45000D.90000注：为元素的一半5 5 . .散列文件是一种( (D D ) )A.顺序文件C.链接文件6 6 . .两个矩阵 A:A: mxn,mxn, B B： nxnx p p 相乘，其时间复杂度为( (B B ) )A . O(n)B.O(mnp)C.O(n2)D.O (mp)注：不同字母的乘积7 7 .常用于函数调用的数据结构是( (A A ) )A.栈B.队列(常用于广度优先搜索)C.链表D.数组2 2.归并排序的时间

3、复杂度是( (B B ) )2、A . O (n )C.O (n)3.3.二分查找的时间复杂度是( ( D D ) )2、A . O (n )B.O (nlog2n)D.O (log2n)B.O (nlog2n)D.O (log2n)1.冒泡，选择，直接插入-O(n2)2.希尔，归并，快速，堆-O(nlog2n)3.二分法-O(log2n)B.索引文件D.计算寻址文件8 8 . .二维数组 A Ann mm以列优先顺序存储，数组 A A 中每个元素占用1 1 个字节，A A11 11为首元素，其地址为0,0,那么元素 A A ii jj的地址为 B B A.(i-1) x m+(j-l)行B.

4、(j-1) x n+(i-1) 注意是以 1 开头，因此-1.C.(j-1)Xn+iD.j x n+l行一前*后 +后 列-后* 前+前9 9 .图的广度优先搜索使用的数据结构 是 A A A .队列B.树C.栈常用与函数调用D.集合1010 . .序列21,19,37,5,221,19,37,5,2经冒泡排序法由小到大排序，在 第一次执行交换后 所得结果为A A D.2, 21, 19, 37, 5 注：从前往后交换1111 . .数据在计算机存储器内表示时，根据 结点的关键字 直接计算出该结点的存储地址，这种方法称为D D A.索引存储方法还需要增加附加索引B.顺序存储方法一组连续的存储单

5、元存储线性表 C.链式存储方法任意的存储单元，可以不连续 D.散列存储方法1212 . .在单链表中，存储每个结点有两个域，一个是数据域，另一个是指针域，指针域指向该结点的B B A.直接前趋数据域B.直接后继C.开始结点D.终端结点2.第一次归并：26 5931 77 11 51 19 423.第二次归并：16 31 59 7711 19 42 51 3.第三次归并：11 16 19 31 42 51 59 77A . (19, 21, 37, 5, 2)B.(21 , 19, 5, 37, 2)C.(21 , 19, 37, 2, 5)13.13.在头指针的单链表中，要在其尾部插入一新结点

6、，其算法所需的时间复杂度为C C A. O (1)(出队)C.O (n)B.O (log2n)D.O (n2)14.14.在链队列中执行入队操作，A.需判别队是否空D D B.需判别队是否满D.限制在链表尾 p 进行15.15. 一整数序列26,26, 59,59, 77,77, 31,31, 51,51, 11,11, 19,19, 42,42,以二路归并排序从小到大排序,第一阶段的归并结果为B B A.31 , 51, 11, 42, 26, 77, 59, 19C.11, 19, 26, 31, 42, 59, 51, 77B.26 , 59, 31, 77, 11, 51, 19, 4

7、2D.26 , 11, 19, 31, 51, 59, 77, 42注：归并过程 1:初始关键字:26 59 77 31 51 11 19 422323 . .有 m m 个叶结点的哈夫曼树所具有的结点数为_2m-1_2m-12424 . .在一棵具有 n n 个结点的完全二叉树中，从树根起，自上而下、自左至右地给所有结点编号。设根结点编号为1 1。假设编号为 i i 的结点有右孩子，那么其右孩子的编号为_2i+1_2i+1。左孩子为 2i2i2525 . .在一棵树中，根 结点没有前驱结点。2626 . . 一个具有 n n 个顶点的有向完全图的弧数是_n(n-1)O O2727 . . n

8、 n 个顶点的无向图 G G 用邻接矩阵 A A nn nn存储，其中第 i i 列的所有元素之和 等于顶点 V Vi i的一度2828 . .选择排序的平均时间复杂度为_O(n2)二、填空题(本大题共 1313 小题，每题 2 2 分，共 2626 分) 请在每题的空格中填上正确答案。错填、不填均无分。1616 . .以下程序段的时间复杂度为_O(n0.5)。i=0;i=0; s=0;s=0;whilewhile (sn)(s2,时间复杂度为不同字母相乘。2.假设只有一个条件句，那么最后 的表达式 假设为“+-那么时间复杂度为 o(，nr假设为“x-那么时 间复杂度为(log2n).、散列存

9、储结构和 索引存储结构 4 4 种。i i 个元素(1w iw n)n)时，需向 前移动n-i 个元素。注：向后移动 n-i+1n-i+1 个元素。19.19.在单链表中，插入一个新结点需修改个指针。24 .冒泡，选择，直接插入 O(n )5 .希尔，归并，快速，堆-O(nlog2n)6 .二分法- O (log2n)三、应用题(本大题共 5 5 小题，每题 6 6 分，共 3030 分)29.29.在栈的输入端元素的输入顺序为1,1, 2,2, 3,3, 4,4, 5,5, 6,6,进栈过程中可以退栈，那么退栈时能否排成序列3,3,2,2, 5,5, 6,6,4,4, 1 1 和 1,1,

10、5,5, 4,4, 6,6, 2,2, 3,3,假设能，写出进栈、退栈过程，假设不能，简述理由。(用 pushpush (x)(x)表示 x x 进栈，pop(x)pop(x)表示 x x 退栈)29.29.能撑成序列3,2.5,6.4,13,2.5,6.4,1过程puwh(2puwh(2 pushpush：p p叩(3(3人pop(2hpu5h(4)pop(2hpu5h(4)：push(5)*pop(5),pushpush(5)*pop(5),push(6)ipop(6)(6)ipop(6) pop(4)ipop(l)pop(4)ipop(l)4 4(3(3分)不能排成序列1 1 5 5 *

11、 * 4 4. .6 6 2 2 3 3理由；在2*32*3依次进栈后，根据柱结构的特征不能产生排列2.3.2.3.。分)解题技巧剖析：1 1 .根据后进先出原那么。3.把原始字符串与要改变次序的字符串写成如下格式。2.写一点，划一点原那么。2 2 .1,1, 2525 3 3, , 4,4, 5,5, 6 6 3 3 , , 2,2, 5,5, 6,6, 4,4, 1 1 3.例如：enter-1,2,3 exit -3,2 此时，剩下 1。对应着，把区里已输入的 1 1 2 2 3,3,删掉。然后把(B 标明已产生排序,然后以此类推。Push(-)push(3)pop(3)注：退的时候，从

12、后往前划。注：假设有两个连续的数连续，那么这个两个数假设给出的时候也为挨着，假设在末端，那么根据栈的原那么，是不行的。CBEDFAGHCBEDFAGH ,后根遍历序歹 U U 为 CEFDBHGACEFDBHGA ,画出该二叉树。解题说明：1 .前序遍历的第一个为“ root2 .后续遍历的最后一个为“ root3 .中序遍历为控制左右孩子的分界点。4 .总体思路： 先找 root,然后到对应的中续遍历或后续遍历中找 到该元素，对应着该元素的左边的所有元素到前序或者后续里 找到对应元素，再确定root,依次类推即可。5 .前序：中左右中续：左中右 后续：左右中30.30.一棵二叉树的中根遍历序

13、列为答:3131.给定表(15,15, 11,11, 8,8, 20,20, 14,14, 13),13),试按元素在表中的顺序将它们依次插入一棵初始时为空的二叉排序树。画出插入完成后的二叉排序树，并判断该二叉排序树是否为平衡二叉排序树，假设为非平衡二叉排序树，将它调整为二叉树构造法：1.依次插入二叉排序树，按照左小又大，差 值最小原那么依次构造即可。2.从根节点看，总结点总比左面的任何值大， 比右面任何值的值小。23.兄弟节点总比左孩子大比右孩子小。4.上一个兄弟节点总比下一个子节点任意值 大。非平衡二叉树：1.概念通俗化：就是 root 两边有高差，发育 不全。它的左右子树的高度之差不能超

14、过1 (可以为 1)例如此题有 2 个高差，那么 就调整 2 次。2.如果左面的圈密集，那么从左面开始，假设 右面的圈密集，从右边开始。3.不平衡，进行旋转。从最低下开始，假设为 左圈多，那么从最低开始，把最底部的结 点与上部的前接前趋结点互换，由于。2可 知，那么就把左孩子给上一个结点当做又 孩子，假设有又孩子，那么跟着旋转即可， 不给。(2)(2)写出三种以顶点A A 为起点的深度优先搜索顶点序歹 U U。由题意可得邻接矩阵为ABCDEFG HA011000 01B100110 00C100001 00D010000 10E010000 10F00100000G000110 00H1000

15、00 00答：AHBDGECFAHBDGECF AHBEGDCFAHBEGDCF ACFBEGDHACFBEGDH注：无向图为对称阵。33 . .用冒泡排序法对数据序列49,49, 38,38, 65,65, 97,97, 76,76, 134,134, 27,27, 4949进行排序，写出排序过程。并说明冒泡排序是否为稳定排序。答：初始关键字49386597761342749A 趟排序38496576972749134第二趟排序38496576274997134第三趟排序38496527497697134第四趟排序38492749657697134第五趟排序38274949657697134第六趟排序27384949657697134冒泡排序是稳定排序。第一趟排序和第一次交换不一样 四、算法设计题本大题共 2 2 小题，每题 7 7 分，共 1414 分34 .编写计算二叉 树中叶子结点数目 的算法。Int LeafCount(Bitree T)/求二叉树中结点叶子的数目If (! T) return(0);Else if (! T-l chil d&! T-rchil d) return(1);Else return LeafCount(T-l chil d)+LeafCount(T-rchild);/ LeafCount