全国2020年10月高等教育自学考试
数据结构导论试题
课程代码:02142
1.请考生按规定用笔将所有试题的答案涂、写在答题纸上。
2.答题前,考生务必将自己的考试课程名称,姓名,准考证号用黑色字迹的签字笔或钢笔填写在答题纸规定的位置上。
选择题部分
注意事项:
每小题选出答案后.用2B铅笔把答题纸上:对应题目的答案标号涂黑。如需改动,用橡皮擦干净后﹒再选涂其他答案标号。不能答在试题卷上。
一、单项选择题:本大题共15小题,每小题2分,共 30分。在每小题列出的备选项中只有一项是最符合题目要求的,请将其选出。
1.数据的最小标识单位是
A.数据项
3.数据类型
C.数据元素
D.数据变量
2.下面程序段的时间复杂度为
for (int i=0; inex1 = = hcad
D. hcad= NUI.I.
4.设输入序列为1、2,3,1 ,5、6.则通过栈的作用后可以得到的输出序列为A.5.3.4.6,1.2
B.3.2.5.6.4.1
C.3.1.2.5.4,6
D.1 .5.4,6.2.3
5.队列是一种线性表,其具有的特征是
A.先进后出
B.只能插入
C.只能删除
D.先进先出
6.设有一个10阶的下三角矩阵A(包括对角线),按照从上到下,从左到石的顺序存储到连续的55个存储单元中,每个数组元素占l个字节的存储空间.则 a;,地址与as的地址之差为
A.10
B.19
C.28
D.55
7.设某棵二义树中只有度数为О和度数为______的结点旦度数为0的结点数为n,则这棵二义树中共有结点个数是
A.2n
B.n+l
C.2nl
D.2n+l
8.设按照从上到下.从左到右的顺序从1开始对完全.二叉树进行顺序编号,若结点i有左孩子,则编号为i结点的左孩子结点的编号为
A.2i+ 1
B.2i
C.i/ 2
D.2i—1
9.已知一棵二叉树的先序遍历结果为ABCDEF.中序遍历结果为CBAEDF .则后序遍历的结果为
A.CBEFDA
B.FEDCBA
C.CBEDFA
D.CEFBDA
10.一个具有n个顶点的无向完全图的边数为
A.n—1
B.n
C.n(n+-1)/2
D.n(n—1)/2
11.设某有向图中有n个顶点.则该有向图对应的邻接表中表头结点个数为
A.n—1
3.n
C.n十1
D.2n-1
12.若查找每个记录的概率均等,则在具有n个记录的连续顺序文件中采用顺序查找算法查找一个记录.其平均查找长度ASL为
A.(n— 1)/2
B.n/ 2
C.(n+1)/2
D.n
13.设散列表中有n个存储单元,散列函数H(key)= key % p.则 p最好选择小于散列表长度n的
A.奇数
B.素数
C.偶数
D.合数
14.下列排序算法中,稳定的排序算法是
A.堆排序
B.快速排序
C.直接选择排序
D.冒泡排序
15.下列四个序列中,是堆的序列为
A.75.15.65.30.15.25.20.10
B.75.65.45.10,30.25.20.15
C.75.65.30.15.25.45.20,l0
D.75,45.65.10.25.30.20.15
非选择题部分
注意事项:
用黑色字迹的签字笔或钢笔将答案写在答题纸上,不能答在试题卷上。
二.填空题:本大题共13空,每空2分,共26分。
16.数据的四类基本逻辑结构是;线性结构,树形结构,图结构和______
17.数据的存储结构有顺序存储、链式存储、索引存储和_________存储。
18.顺序表插入算法的时间复杂度是_______
19.设r指向单链表的最后一个结点,要在最后一个结点之后插入所指的结点,需执行的语句序列是r->nexl= s ;r=s;________
20.一般情况下﹒函数的嵌套调用和程序递归的处理都是用________来实现的。
21.m行n列的矩阵有_______个非零元素,当t满足________条件时,称该矩阵为稀疏矩阵。
22.二叉树的第ii≥1)层上至多有________个结点。
23.双亲表示法由一个一维数组构成.数组的每个分量包含两个域:___________和双亲域。
24.无向图的邻接矩阵是一个________矩阵。
25.设有散列函数H和键值 k, ,k..若k,≠k, ,但是H(k;)一H(k;).则称这种现象为________
26.向一个长度为n的顺序表中第i(1≤i≤n)个元素之前插人一个元素时.需向后移动________个元素。
27.直接插人排序的空间复杂度为________
28.设记录数为n.官冒泡排序算法在最好情况下所作的比较次数为________
三、应用题:本大题共5小题,每小题6分,共30分。
29.题29图给出了一个稀疏矩阵A.请写出该稀疏矩阵的三元组表。
诚为径自考频道也为广大考生提供了