1、 绝密 考试结束前2 0 2 3年4月高等教育自学考试数据结构导论试题课程代码:0 2 1 4 2 1.请考生按规定用笔将所有试题的答案涂、写在答题纸上。2.答题前,考生务必将自己的考试课程名称、姓名、准考证号用黑色字迹的签字笔或钢笔填写在答题纸规定的位置上。选择题部分注意事项:每小题选出答案后,用2 B铅笔把答题纸上对应题目的答案标号涂黑。如需改动,用橡皮擦干净后,再选涂其他答案标号。不能答在试题卷上。一、单项选择题:本大题共1 5小题,每小题2分,共3 0分。在每小题列出的备选项中只有一项是最符合题目要求的,请将其选出。1.与数据元素本身的形式、内容、相对位置、个数无关的是数据的A.存储结
2、构B.逻辑结构C.类型D.运算实现2.在单链表中,释放已移出结点p的空间使用语句A.m a l l o c(p)B.s i z e o f(p)C.f r e e(p)D.p=NU L L3.在表长为n的顺序表上做插入运算,平均要移动的结点数为A.n/4B.n/3C.n/2D.n4.线性表实现顺序存储使用A.栈B.队列C.链表D.数组5.栈可以实现A.函数的嵌套调用和操作系统中进程调度B.函数的嵌套调用和程序递归的处理C.程序递归的处理和操作系统中进程调度D.操作系统中进程调度和网络管理中的打印服务6.顺序队列结构类型中,d a t a为A.一维数组 B.二维数组C.单链表D.循环链表浙0 2
3、 1 4 2#数据结构导论试题 第 1页(共4页)7.下列关于树的描述,正确的是A.树形结构不可以表示具有层次结构的数据B.树是n(n 0)个结点的有限集合C.任何只含一个结点的集合不是一棵树D.树形结构的定义是非递归的8.叶子的度为A.-1B.0C.1D.29.树的遍历有三种,为A.先序、中序和后序遍历B.先序、中序和层次遍历C.先序、后序和层次遍历D.中序、后序和层次遍历1 0.二叉树的中序序列中,结点P排在结点Q之前的条件是:在二叉树中A.P在Q的左边B.P在Q的右边C.P是Q的祖先D.P是Q的子孙1 1.无向图中一个顶点的度是指图中A.通过该顶点的简单路径数B.与该顶点连通的顶点数C.
4、通过该顶点的回路数D.与该顶点相邻接的顶点数1 2.下列序列中,符合堆定义的是A.(1 0 0,8 0,5 5,6 0,5 0,4 0,5 8,3 5,2 0)B.(1 0 0,8 0,5 5,6 0,5 0,4 0,3 5,5 8,2 0)C.(1 0 0,8 0,5 5,5 8,5 0,4 0,6 0,3 5,2 0)D.(1 0 0,7 0,5 5,6 0,5 0,4 0,5 8,3 5,2 0)1 3.下列有关解决冲突的几种方法,描述正确的是A.线性探测法生成后继散列地址计算复杂B.二次探测法生成的后继散列地址是连续的C.链地址法是挑选部分同义词建单链表来解决冲突D.多重散列法不易产生
5、“堆积”1 4.双向循环链表的对称性可以表示为A.p=p-p r i o r-n e x t=p-n e x t-p r i o rB.p=p-n e x t=p-p r i o rC.p=p-n e x t-n e x t=p-p r i o r-p r i o rD.p=p-n e x t-n e x t=p-n e x t1 5.待排序记录的数量很大时,排序方法效果较好的是A.堆排序和快速排序B.堆排序和直接插入排序C.直接插入排序和直接选择排序D.直接选择排序和快速排序浙0 2 1 4 2#数据结构导论试题 第 2页(共4页)非选择题部分注意事项:用黑色字迹的签字笔或钢笔将答案写在答题
6、纸上,不能答在试题卷上。二、填空题:本大题共1 3小题,每小题2分,共2 6分。1 6.表示数据元素之间的关联方式主要有顺序存储方式和 存储方式。1 7.在单链表中,如果让最后一个结点的指针域指向第一个结点可以构成 链表。1 8.栈的插入运算称为 。1 9.队列的链接实现实际上是使用一个带有 的单链表来表示队列。2 0.以 为界的上(下)半部分是一个固定的值c或零,这样的矩阵叫做下(上)三角矩阵。2 1.循环队列结构类型中含有三个域:d a t a、f r o n t和r e a r,循环队列S Q为空的条件是 。2 2.对于任何完全二叉树来说,可以采用以 作为数组的下标的方法将结点存入一维数
7、组中。2 3.如果一棵二叉树中度数为0的结点有6个,那么度数为2的结点有 个。2 4.如果G是一个有向图,则把以顶点v为终点的弧的数目称为v的 。2 5.一个图的最小生成树是指该图的所有生成树中 的生成树。2 6.若图的顶点个数为n,图的弧的数目为e,则拓扑排序算法的时间复杂度为 。2 7.静态查找表最简单的实现方法是以 作为存储结构。2 8.归并排序要求待排序列是由若干个 子序列组成。三、应用题:本大题共5小题,每小题6分,共3 0分。2 9.题2 9图给出了矩阵A,请将矩阵A表示成三元组表。A=0 2 0 0 0 00 0 0 0 0 00 0 0 5 0 90 6 0 0 0 00 0
8、0 0 4 0题2 9图3 0.根据有向图的邻接表回答下列问题:(1)如何判断图中有多少条弧?(2)如何判断图中是否存在从顶点i到顶点j的弧?(3)如何求顶点i的出度?3 1.设某通信系统中一个待传输的文本有6个不同字符,它们的出现频率分别是0.5,0.8,1.4,2.2,2.3,2.8,试设计哈夫曼编码。浙0 2 1 4 2#数据结构导论试题 第 3页(共4页)3 2.如题3 2图所示长度为1 3的散列表,其散列函数为H(k e y)=k e y m o d 1 3,在表中已填入键值分别为1 6,3 0,5 4的元素。(1)现要插入键值为2 9的元素,应用二次探测法,计算填入散列表中单元的序
9、号。(要求给出求解过程)(2)二次探测法有什么缺点?01234567891 0 1 1 1 25 4 1 6 3 0题3 2图3 3.给定表(1 9,1 4,2 2,0 1,6 6,2 1,8 3,2 7,5 6,1 3,1 0),试按元素在表中的次序将它们依次插入一棵初始时为空的二叉排序树,画出插入完成后的二叉排序树。四、算法设计题:本大题共2小题,每小题7分,共1 4分。3 4.写出计算方阵An n 与Bn n 的乘积Cn n 的算法。3 5.已知循环队列的结构类型如下:t y p e d e f s t r u c t c y c q u e u e D a t a T y p e d
10、a t a m a x s i z e i n t f r o n t r e a r C y c Q u e C y c Q u e C Q 设计出队列的算法。浙0 2 1 4 2#数据结构导论试题 第 4页(共4页)绝密启用前2 0 2 3年4月高等教育自学考试全国统一命题考试数数据据结结构构导导论论试试题题答答案案及及评评分分参参考考(课程代码 0 2 1 4 2)一、单项选择题:本大题共1 5小题,每小题2分,共3 0分。1.B2.C3.C4.D5.B6.A7.B8.B9.C1 0.A1 1.D1 2.B1 3.D1 4.A1 5.A二、填空题:本大题共1 3小题,每小题2分,共2 6
11、分。1 6.链式1 7.循环1 8.进栈1 9.头结点2 0.主对角线2 1.S Q.r e a r=S Q.f r o n t2 2.编号2 3.52 4.入度2 5.权总和最小2 6.O(n+e)2 7.顺序表2 8.有序三、应用题:本大题共5小题,每小题6分,共3 0分。2 9.(0,1,2),(1分)(2,3,5),(1分)(2,5,9),(1分)(3,1,6),(1分)(4,4,4)。(2分)3 0.(1)图中弧的条数为邻接表的表结点的个数。(2分)(2)要判断图中是否存在从i到j的弧,只要看第i个表头结点的链表中是否存在a d j v e x为j的表结点。(2分)(3)顶点i的出度
12、即为:第i个表头结点的链表中表结点的个数。(2分)3 1.(1)出现频率为0.5的字符编码为1 0 0 0。(1分)(2)出现频率为0.8的字符编码为1 0 0 1。(1分)(3)出现频率为1.4的字符编码为1 0 1。(1分)(4)出现频率为2.2的字符编码为0 0。(1分)(5)出现频率为2.3的字符编码为0 1。(1分)(6)出现频率为2.8的字符编码为1 1。(1分)数据结构导论试题答案及评分参考第1页(共3页)3 2.(1)H(2 9)=2 9 m o d1 3=3,地址3已有键值为1 6的元素,产生冲突。当发生冲突时,应用二次探测法,得到下一个地址d1=(3+12)m o d1 3
13、=4仍冲突,(1分)则再求下一个地址d2=(3-12)m o d1 3=2仍冲突,(1分)直到散列地址为d3=(3+22)m o d1 3=7时其位置上没有元素,则元素填入散列表中序号为7的位置。(2分)(2)不易探测到整个散列表的所有空间。(2分)3 3.答3 3图四、算法设计题:本大题共2小题,每小题7分,共1 4分。3 4.v o i dm a t r i x m u l t i p l y(i n tA n,i n tB n,i n tC n,i n tn)i n t i,j;f o r(i=0;i n;i+)f o r(j=0;j n;j+)(3分)C i j=0;f o r(k=0
14、;kn;k+)(2分)C i j+=A i k*B k j;(2分)3 5.i n tO u t Q u e u e(C y c Q u eC Q)i f(Em p t y Q u e u e(C Q)e r r o r(“队列空”);r e t u r n0;(2分)e l s e C Q.f r o n t=(C Q.f r o n t+1)%m a x s i z e;数据结构导论试题答案及评分参考第2页(共3页)r e t u r n 1;(2分)i n tEm p t y Q u e u e(C y c Q u eC Q)i f (C Q.r e a r=C Q.f r o n t)r e t u r n 1;(2分)e l s e r e t u r n 0;(1分)数据结构导论试题答案及评分参考第3页(共3页)
