全国2020年10月自考数据结构导论02142真题

全国2020年10月自考数据结构导论02142真题

一、单项选择题:本大题共15小题,每小题2分,共30分。在每小题列出的备选项中只有一项是最符合题目要求的,请将其选出。

1.数据的最小标识单位是

A.数据项

B.数据类型

C.数据元素

D.数据变量

2.下面程序段的时间复杂度为

for(inti=0;i

for(intj=0;j

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.以二叉链表作存储结构,请写出二叉链表类型定义;利用二叉树遍历的递归算法,试编写求二叉树高度的算法。