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 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页)
