2023年10月自考02142数据结构导论试题

绝密★考试结束前年月高等教育自学考试20231数据结构导论试题课程代码

02142.请考生按规定用笔将所有试题的答案涂、写在答题纸上

1.答题前，考生务必将自己的考试课程名称、姓名、准考证号用黑色字迹的签字笔或钢笔填写2在答题纸规定的位置上选择题部分注意事项每小题选出答案后，用铅笔把答题纸上对应题目的答案标号涂黑如需改动，用橡皮擦干净2B后,再选涂其他答案标号不能答在试题卷上

一、单项选择题本大题共小题,每小题分，共分在每小题列出的备选项中只有一项是最

15230.时间复杂度的常数阶表示为1C.On0B.OnO2A.O1D.O2a.下列关于单链表的描述，错误的是••2头指针变量不一定非要用来标识B.head.所有结点通过指针链接形成链表A.通常用尾指针来表示一个单链表D尾结点指针域的值称为空指针C.NULL.线性表实现顺序存储可使用3数组.链表C.D.栈,队列A B符合题目要求的，请将其选出.设单链表中指针指向结点要删除之后的结点偌存在，则修改指针的操作为4p A,AA.pnexkp-next-next B.p=p-next滋酒-〉C.p=p neext D.p-next=p.出队列操作使用的赋值语句是5B.SQ.rear=SQ.rear-1A.SQ.rear=SQ.rear+1D.SQ.front=SQ.front-1C.SQ.front=SQ.front+

1.在一个具有个单元的顺序栈中，假定以地址低端即单元作为栈底，以为栈6n0top顶指针，当栈未满时进行进栈操作，此时不变A.top B.top-C.top++D.top=0,带头结点链队列的头指针和尾指针分别为和则判断队列空的条件为7fro ntrear,A.front==rearB.front=NULLC.rear=NULL D.front==NULL）.深度为》（的二叉树的结点数最多8kk为kA.2k-i B.2-1C.2+1D.2k+ik.下列关于树形结构的描述，正确的是9树中每个结点可以有多个直接前驱结点B.树形结构是线性结构A.树中每个结点只能有一个直接后继结点D.树可以用顺序存储C.,对任何一棵二叉树，若度数为的结点（叶结点）个数为皿度数为的结点个数为四则1002等于n0A.O B.n-1Cm2D.n+

122.设有个顶点的无向图，若它为连通图，则它具有的边数最少为1110A.9B.10C.11D.

12.设含有个顶点,条弧的有向图采用邻接表存储，则拓扑排序算法的时间复杂度为12n eG（））（）0B.OnXe C.On2D.OnxeA.On

13.当查找表中有n个数据元素时，假设（，,••/为直投第i个元素的概率，在P等概率的条件下，顺序查找算法的平均查找长度为（）//C.n D.n+1A.n2B.n+

12.二维数组以行为主序存储，每个元素占个存储单元若元素的存储地址是14A1叩的存储地址是则［田的存储地址是420A3,3446,A55A.470B.471C.472D.473眉泡排序属于

15.插入排序.归并排序.选择排序.交换排序A BC D非选择题部分注意事项用黑色字迹的签字笔或钢笔将答案写在答题纸上，不能答在试题卷上

二、填空题本大题共小题海小题分洪分

13226.在数据库中数据项又称为字段或▲

16.在单链表存储结构中，线性表的表长等于单链表中▲的结点个数

17.二叉树的顺序存储结构可以用▲18避翻编嘉酸集种次序依次执行，需要一个P

1.分雕豳旭曲了保持多个进程、、

19.对称矩阵有近一半元素可以通过其对称元素获得，因此可将含有20n缩存储到含有▲2个元素的对称矩阵压.在树形结构中，结点间具有▲关系23则入栈操作为个丽素的一维数组中P,.在图中,序列中顶点不重复出现的路径称为▲路径24算法用于求▲问题

25.Dijkstra.求最小生成树有▲方法和方法26Kruskal.若在查找过程中，向表中插入不存在的数据元素，或者从表中删除某个数据元素，则称此类表为27▲查找表.在二分查找、索弓顺序查找和散列查找三种查找方法中，平均查找长度与元素个数没有关28I系的查找方法是▲

三、应用题本大题共小题海小题分，共分5630设有一个链栈的输入序列为、八曲瀚出序列分别为和时，请写出对应的进栈和出栈过

29.ABC BCA程,设有一森林如题图所示，请分别写出先序遍历和中序遍历的序列30F30题图

30.如题图所示长度为的散列表,其散列函数为，在表中已填入键313113Hkey=keymod13值分别为的元素163054,,现要插入键值为的元素，应用线性探测法，计算填入散列表中单元的序号要求给出求解129o过程线性探测法中，如何减少堆积的机会20123456789101112541630题图

31.如题图所示的图结构，请写出以为源点的广度优先搜索得到的顶点访问序323210，并画列出搜索过程图（同等情况下，值小的结点优先访问）.给定有序表33D={006087155188220465505508511586656670700766,,,,3333分查找法在中查找试给出查找过程D511,

四、算法设计题本大题共小题,每小题分，共分

2714.编制函数求341+2+...+

11.已知循环队列的结构类型如下35typedefstructcycq ueue{DataType datamaxsizeintfrontrearJCycQueCycQueCQ设计入队列的算法。