1、 绝密 考试结束前2 0 2 3年1 0月高等教育自学考试数据结构导论试题课程代码:0 2 1 4 2 1.请考生按规定用笔将所有试题的答案涂、写在答题纸上。2.答题前,考生务必将自己的考试课程名称、姓名、准考证号用黑色字迹的签字笔或钢笔填写在答题纸规定的位置上。选择题部分注意事项:每小题选出答案后,用2 B铅笔把答题纸上对应题目的答案标号涂黑。如需改动,用橡皮擦干净后,再选涂其他答案标号。不能答在试题卷上。一、单项选择题:本大题共1 5小题,每小题2分,共3 0分。在每小题列出的备选项中只有一项是最符合题目要求的,请将其选出。1.时间复杂度的常数阶表示为A.O(1)B.O(n)C.O(n2)
2、D.O(2n)2.下列关于单链表的描述,错误的是A.所有结点通过指针链接形成链表B.头指针变量不一定非要用h e a d来标识C.尾结点指针域的值N U L L称为空指针D.通常用尾指针来表示一个单链表3.线性表实现顺序存储可使用A.栈B.队列C.数组D.链表4.设单链表中指针p指向结点A,要删除A之后的结点(若存在),则修改指针的操作为A.pn e x t=pn e x tn e x tB.p=pn e x tC.p=pn e x tn e x tD.pn e x t=p5.出队列操作使用的赋值语句是A.S Q.r e a r=S Q.r e a r+1B.S Q.r e a r=S Q.r
3、 e a r-1C.S Q.f r o n t=S Q.f r o n t+1D.S Q.f r o n t=S Q.f r o n t-1 6.在一个具有n个单元的顺序栈中,假定以地址低端(即0单元)作为栈底,以t o p为栈顶指针,当栈未满时进行进栈操作,此时A.t o p不变B.t o p-C.t o p+D.t o p=0浙0 2 1 4 2#数据结构导论试题 第 1页(共4页)7.带头结点链队列的头指针和尾指针分别为f r o n t和r e a r,则判断队列空的条件为A.f r o n t=r e a rB.f r o n t!=NU L LC.r e a r!=NU L LD.
4、f r o n t=NU L L8.深度为k(k1)的二叉树的结点数最多为A.2k-1B.2k-1 C.2k+1D.2k+19.下列关于树形结构的描述,正确的是A.树形结构是线性结构B.树中每个结点可以有多个直接前驱结点C.树可以用顺序存储D.树中每个结点只能有一个直接后继结点1 0.对任何一棵二叉树,若度数为0的结点(叶结点)个数为n0,度数为2的结点个数为n2,则n0等于A.0B.n2-1C.n2D.n2+11 1.设有1 0个顶点的无向图,若它为连通图,则它具有的边数最少为A.9B.1 0C.1 1D.1 21 2.设含有n个顶点,e条弧的有向图G采用邻接表存储,则拓扑排序算法的时间复杂
5、度为A.O(n)B.O(n+e)C.O(n2)D.O(n e)1 3.当查找表中有n个数据元素时,假设Pi(i=1,2,n)为查找第i个元素的概率,在Pi等概率的条件下,顺序查找算法的平均查找长度为A.n/2B.(n+1)/2C.nD.n+11 4.二维数组A以行为主序存储,每个元素占1个存储单元。若元素A1 1 的存储地址是4 2 0,A3 3 的存储地址是4 4 6,则A5 5 的存储地址是A.4 7 0B.4 7 1C.4 7 2D.4 7 31 5.冒泡排序属于A.插入排序B.归并排序C.选择排序D.交换排序非选择题部分注意事项:用黑色字迹的签字笔或钢笔将答案写在答题纸上,不能答在试题
6、卷上。二、填空题:本大题共1 3小题,每小题2分,共2 6分。1 6.在数据库中数据项又称为字段或 。1 7.在单链表存储结构中,线性表的表长等于单链表中 的结点个数。1 8.二叉树的顺序存储结构可以用 维数组来实现。1 9.在操作系统中,为了保持多个进程P 1、P 2、P 3和P 4按某种次序依次执行,需要一个 来实现这个过程。浙0 2 1 4 2#数据结构导论试题 第 2页(共4页)2 0.对称矩阵有近一半元素可以通过其对称元素获得,因此可将含有n2个元素的对称矩阵压缩存储到含有 个元素的一维数组中。2 1.设有一个带头结点的链栈,其头指针为h e a d,现有一个新结点入栈,指向该结点的
7、指针为p,则入栈操作为 和h e a dn e x t=p。2 2.满二叉树一定是 二叉树。2 3.在树形结构中,结点间具有 关系。2 4.在图中,序列中顶点不重复出现的路径称为 路径。2 5.D i j k s t r a算法用于求 问题。2 6.求最小生成树有 方法和K r u s k a l方法。2 7.若在查找过程中,向表中插入不存在的数据元素,或者从表中删除某个数据元素,则称此类表为 查找表。2 8.在二分查找、索引顺序查找和散列查找三种查找方法中,平均查找长度与元素个数没有关系的查找方法是 。三、应用题:本大题共5小题,每小题6分,共3 0分。2 9.设有一个链栈的输入序列为A、B
8、、C,当输出序列分别为A B C和B C A时,请写出对应的进栈和出栈过程。3 0.设有一森林F如题3 0图所示,请分别写出先序遍历和中序遍历的序列。题3 0图3 1.如题3 1图所示长度为1 3的散列表,其散列函数为H(k e y)=k e y m o d 1 3,在表中已填入键值分别为1 6,3 0,5 4的元素。(1)现要插入键值为2 9的元素,应用线性探测法,计算填入散列表中单元的序号。(要求给出求解过程)(2)线性探测法中,如何减少堆积的机会?01234567891 0 1 1 1 25 4 1 6 3 0题3 1图浙0 2 1 4 2#数据结构导论试题 第 3页(共4页)3 2.如
9、题3 2图所示的图结构,请写出以1 0为源点的广度优先搜索得到的顶点访问序列,并画出搜索过程图。(同等情况下,值小的结点优先访问)题3 2图3 3.给定有序表D=0 0 6,0 8 7,1 5 5,1 8 8,2 2 0,4 6 5,5 0 5,5 0 8,5 1 1,5 8 6,6 5 6,6 7 0,7 0 0,7 6 6,用二分查找法在D中查找5 1 1,试给出查找过程。四、算法设计题:本大题共2小题,每小题7分,共1 4分。3 4.编制函数求1+2+n 。3 5.已知循环队列的结构类型如下:t y p e d e f s t r u c t c y c q u e u eD a t a
10、 T y p e d 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年1 0月高等教育自学考试全国统一命题考试数数据据结结构构导导论论试试题题答答案案及及评评分分参参考考(课程代码 0 2 1 4 2)一、单项选择题:本大题共1 5小题,每小题2分,共3 0分。1.A2.D3.C4.A5.C6.C7.B8.B9.C1 0.D1 1.A1 2.B1 3.B1 4.C1 5.D二、填空题:本大题共1 3
11、小题,每小题2分,共2 6分。1 6.域1 7.数据元素1 8.一1 9.队列2 0.n(n+1)/22 1.pn e x t=h e a dn e x t2 2.完全2 3.层次2 4.简单2 5.单源最短路径2 6.P r i m2 7.动态2 8.散列查找三、应用题:本大题共5小题,每小题6分,共3 0分。2 9.输出A B C:A进,A出,B进,B出,C进,C出;(3分)输出B C A:A进,B进,B出,C进,C出,A出。(3分)3 0.先序序列为A B C D E F GH J I;(3分)中序序列为B C D A F E J H I G。(3分)3 1.(1)散列函数求出其散列地址
12、为3,在地址3上面已有元素1 6,发生冲突。(1分)应用线性探测法,得到下一个地址为d+1=4,仍冲突,(1分)则再求下一个地址d+2=5,这个位置上没有元素,将元素填入散列表中序号为5的单元。(2分)(2)应设法使后继散列地址尽量均匀地分散在整个散列表中。(2分)3 2.序列:1 0,2 0,3 0,5 0,4 0,6 0(3分)答3 2图(3分)数据结构导论试题答案及评分参考第1页(共2页)3 3.0 1(1)0 0 6 0 20 8 7 0 31 5 5 0 41 8 8 0 52 2 0 0 64 6 5 0 75 0 5 0 85 0 8 0 95 1 1 1 05 8 6 1 16
13、 5 6 1 26 7 0 1 37 0 0 1 47 6 6l o wm i dh i g h(2分)(2)0 0 6 0 8 7 1 5 5 1 8 8 2 2 0 4 6 5 5 0 5 5 0 8 5 1 1 5 8 6 6 5 6 6 7 0 7 0 0 7 6 6l o wm i dh i g h(2分)(3)0 0 6 0 8 7 1 5 5 1 8 8 2 2 0 4 6 5 5 0 5 5 0 8 5 1 1 5 8 6 6 5 6 6 7 0 7 0 0 7 6 6l o wm i d h i g h(2分)四、算法设计题:本大题共2小题,每小题7分,共1 4分。3 4.i
14、 n t f a c t 1(i n tn)i n t i,j,t e m p,s;s=0;(2分)f o r(i=1;i=n;i+)t e m p=1;(3分)f o r(j=1;j=i;j+)t e m p=t e m p*j;s=s+t e m p;r e t u r n s;(2分)(注:答案不唯一,正确即可)3 5.i n tE n Q u e u e(C y c Q u eC Q,D a t a T y p ex)i f (C Q.r e a r+1)%m a x s i z e=C Q.f r o n t)e r r o r(“队列满”);r e t u r n0;(3分)e l s e C Q.r e a r=(C Q.r e a r+1)%m a x s i z e;C Q.d a t aC Q.r e a r=x;(3分)r e t u r n 1;(1分)数据结构导论试题答案及评分参考第2页(共2页)
