欢迎访问桃李自考网，本站可为自考生提供学习指导服务，今天是
欢迎访问桃李自考网，本站可为自考生提供学习指导服务，今天是
全国2020年10月自考数据结构导论02142真题
一、单项选择题:本大题共15小题,每小题2分,共30分。在每小题列出的备选项中只有一项是最符合题目要求的,请将其选出。
1.数据的最小标识单位是
A.数据项
B.数据类型
C.数据元素
D.数据变量
2.下面程序段的时间复杂度为
for(inti=0;i< p=""><>
for(intj=0;j< p=""><>
a[i][j]=i*j;
A.O(1)
B.O(n)
C.O(2n)
D.O(n2)
3.设带头结点的单向循环链表的头指针变量为head,则空循环链表的判定条件是
A.head= =NULL
B.head->next= =NULL
C.head->next= =head
D.head=NULL
4.设输入序列为1、2、3、4、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个存储单元中,每个数组元素占1个字节的存储空间,则a54地址与a00的地址之差为
A.10
B.19
C.28
D.55
7.设某棵二叉树中只有度数为0和度数为2的结点且度数为0的结点数为n,则这棵二叉树中共有结点个数是
A.2n
B.n+l
C.2n-1
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.n2
C.n(n+1)/2
D.n(n-1)/2
11.设某有向图中有n个顶点,则该有向图对应的邻接表中表头结点个数为
A.n-1
B.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,45,65,30,15,25,20,10
B.75,65,45,10,30,25,20,15
C.75,65,30,15,25,45,20,10
D.75,45,65,10,25,30,20,15
二、填空题:本大题共13空,每空2分,共26分。
16.数据的四类基本逻辑结构是:线性结构、树形结构、图结构和 ▲ 。
17.数据的存储结构有顺序存储、链式存储、索引存储和 ▲ 存储。
18.顺序表插入算法的时间复杂度是 ▲ 。
浙02142# 数据结构导论试题 第 2页(共4页)19.设r指向单链表的最后一个结点,要在最后一个结点之后插入s所指的结点,需执行的语句序列是r->next=s;r=s; ▲ 。
20.一般情况下,函数的嵌套调用和程序递归的处理都是用 ▲ 来实现的。
21.m 行n列的矩阵有t个非零元素,当t满足 ▲ 条件时,称该矩阵为稀疏矩阵。
22.二叉树的第i(i≥1)层上至多有 ▲ 个结点。
23.双亲表示法由一个一维数组构成,数组的每个分量包含两个域: ▲ 和双亲域。
24.无向图的邻接矩阵是一个 ▲ 矩阵。
25.设有散列函数 H 和键值k1、k2,若k1≠k2,但是 H(k1)=H(k2),则称这种现象为 ▲ 。
26.向一个长度为n的顺序表中第i(1≤i≤n)个元素之前插入一个元素时,需向后移动 ▲ 个元素。
27.直接插入排序的空间复杂度为 ▲ 。
28.设记录数为n,冒泡排序算法在最好情况下所作的比较次数为 ▲ 。
三、应用题:本大题共5小题,每小题6分,共30分。
29.题29图给出了一个稀疏矩阵 A,请写出该稀疏矩阵的三元组表。
30.已知二叉树如题30图所示,请将该二叉树转换为对应的森林。
31.设某通信系统中一个待传输的文本有6个不同字符,它们的出现频率分别是0.5,0.7,1.4,2.2,2.4,2.8,试画出哈夫曼树,并给出每个字符的哈夫曼编码。(要求任一结点的左孩子权值小于右孩子)
32.选定散列函数为 H(key)= keymod13,试用链地址法建立键值为26,41,25,05,07,15,12,49,51,31,62的散列表。
33.对于给定的一组键值:83,40,63,13,84,35,96,57,39,79,61,15,请分别写出直接选择排序和冒泡排序的第一趟排序结果。
四、算法设计题:本大题共2小题,每小题7分,共14分。
34.写出一个将线性表的顺序表存储方式(数组a、表长为n)改成单链表存储方式(其头结点由头指针head指向)的算法。设函数头为:Node*CreateLinkedList(DataTypea[],intn)
35.以二叉链表作存储结构,请写出二叉链表类型定义;利用二叉树遍历的递归算法,试编写求二叉树高度的算法。