1、 绝密考试结束前全国2 0 2 0年1 0月高等教育自学考试数据结构导论试题课程代码:0 2 1 4 2 1.请考生按规定用笔将所有试题的答案涂、 写在答题纸上。 2.答题前, 考生务必将自己的考试课程名称、 姓名、 准考证号用黑色字迹的签字笔或钢笔填写在答题纸规定的位置上。选择题部分注意事项: 每小题选出答案后, 用2 B铅笔把答题纸上对应题目的答案标号涂黑。如需改动, 用橡皮擦干净后, 再选涂其他答案标号。不能答在试题卷上。一、 单项选择题: 本大题共1 5小题, 每小题2分, 共3 0分。在每小题列出的备选项中只有一项是最符合题目要求的, 请将其选出。1.数据的最小标识单位是A.数据项B
2、.数据类型C.数据元素D.数据变量2.下面程序段的时间复杂度为f o r(i n t i=0;in;i+)f o r(i n t j=0;jn e x t= =NU L LC. h e a d-n e x t= =h e a dD. h e a d=NU L L4.设输入序列为1、2、3、4、5、6, 则通过栈的作用后可以得到的输出序列为A.5,3,4,6,1,2B. 3,2,5,6,4,1C. 3,1,2,5,4,6D. 1,5,4,6,2,35.队列是一种线性表, 其具有的特征是A.先进后出B.只能插入C.只能删除D.先进先出6.设有一个1 0阶的下三角矩阵A( 包括对角线) , 按照从上
3、到下、 从左到右的顺序存储到连续的5 5个存储单元中, 每个数组元素占1个字节的存储空间, 则a5 4地址与a0 0的地址之差为A. 1 0B. 1 9C. 2 8D. 5 5浙0 2 1 4 2#数据结构导论试题 第1页( 共4页)7.设某棵二叉树中只有度数为0和度数为2的结点且度数为0的结点数为n, 则这棵二叉树中共有结点个数是A. 2 nB. n+ lC. 2 n-1D. 2 n+ l8.设按照从上到下、 从左到右的顺序从1开始对完全二叉树进行顺序编号, 若结点i有左孩子, 则编号为i结点的左孩子结点的编号为A. 2 i +1B. 2 iC.i/2D. 2 i -19.已知一棵二叉树的先
4、序遍历结果为A B C D E F, 中序遍历结果为C B A E D F, 则后序遍历的结果为A. C B E F D AB. F E D C B AC. C B E D F AD. C E F B D A1 0.一个具有n个顶点的无向完全图的边数为A. n-1B. n2C. n(n+1) /2D. n(n-1) /21 1.设某有向图中有n个顶点, 则该有向图对应的邻接表中表头结点个数为A. n-1B. nC. n+1D. 2 n-11 2.若查找每个记录的概率均等, 则在具有n个记录的连续顺序文件中采用顺序查找算法查找一个记录, 其平均查找长度A S L为A.(n-1) /2B. n/2
5、C.(n+1) /2D. n1 3.设散列表中有n个存储单元, 散列函数H(k e y)=k e y%p, 则p最好选择小于散列表长度n的A.奇数B.素数C.偶数D.合数1 4.下列排序算法中, 稳定的排序算法是A.堆排序B.快速排序C.直接选择排序D.冒泡排序1 5.下列四个序列中, 是堆的序列为A.7 5,4 5,6 5,3 0,1 5,2 5,2 0,1 0B. 7 5,6 5,4 5,1 0,3 0,2 5,2 0,1 5C. 7 5,6 5,3 0,1 5,2 5,4 5,2 0,1 0D. 7 5,4 5,6 5,1 0,2 5,3 0,2 0,1 5非选择题部分注意事项: 用黑色
6、字迹的签字笔或钢笔将答案写在答题纸上, 不能答在试题卷上。二、 填空题: 本大题共1 3空, 每空2分, 共2 6分。1 6.数据的四类基本逻辑结构是: 线性结构、 树形结构、 图结构和 。1 7.数据的存储结构有顺序存储、 链式存储、 索引存储和 存储。1 8.顺序表插入算法的时间复杂度是 。浙0 2 1 4 2#数据结构导论试题 第2页( 共4页)1 9.设r指向单链表的最后一个结点, 要在最后一个结点之后插入s所指的结点, 需执行的语句序列是r-n e x t=s;r=s; 。2 0.一般情况下, 函数的嵌套调用和程序递归的处理都是用 来实现的。2 1. m行n列的矩阵有t个非零元素,
7、当t满足 条件时, 称该矩阵为稀疏矩阵。2 2.二叉树的第i(i 1) 层上至多有 个结点。2 3.双亲表示法由一个一维数组构成, 数组的每个分量包含两个域: 和双亲域。2 4.无向图的邻接矩阵是一个 矩阵。2 5.设有散列函数H和键值k1、k2, 若k1k2, 但是H(k1)=H(k2) , 则称这种现象为 。2 6.向一个长度为n的顺序表中第i(1 i n) 个元素之前插入一个元素时, 需向后移动 个元素。2 7.直接插入排序的空间复杂度为 。2 8.设记录数为n, 冒泡排序算法在最好情况下所作的比较次数为 。三、 应用题: 本大题共5小题, 每小题6分, 共3 0分。2 9.题2 9图给
8、出了一个稀疏矩阵A, 请写出该稀疏矩阵的三元组表。A=050 0 0 0000 0 0 00-1 0 7 0 0060 0 0 0000 0 9 0000 0 0 8题2 9图3 0.已知二叉树如题3 0图所示, 请将该二叉树转换为对应的森林。题3 0图3 1.设某通信系统中一个待传输的文本有6个不同字符, 它们的出现频率分别是0. 5,0. 7,1. 4,2. 2,2. 4,2. 8, 试画出哈夫曼树, 并给出每个字符的哈夫曼编码。( 要求任一结点的左孩子权值小于右孩子)3 2.选定散列函数为H(k e y)= k e ym o d1 3, 试用链地址法建立键值为2 6,4 1,2 5,0
9、5,0 7,1 5,1 2,4 9,5 1,3 1,6 2的散列表。浙0 2 1 4 2#数据结构导论试题 第3页( 共4页)3 3.对于给定的一组键值:8 3,4 0,6 3,1 3,8 4,3 5,9 6,5 7,3 9,7 9,6 1,1 5, 请分别写出直接选择排序和冒泡排序的第一趟排序结果。四、 算法设计题: 本大题共2小题, 每小题7分, 共1 4分。3 4.写出一个将线性表的顺序表存储方式( 数组a、 表长为n) 改成单链表存储方式( 其头结点由头指针h e a d指向) 的算法。设函数头为:N o d e *C r e a t e L i n k e d L i s t(D a t a T y p ea ,i n tn)3 5.以二叉链表作存储结构, 请写出二叉链表类型定义; 利用二叉树遍历的递归算法, 试编写求二叉树高度的算法。浙0 2 1 4 2#数据结构导论试题 第4页( 共4页)
