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

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

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

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

A.数据项

B.数据种类

C.数据元素

D.数据变量

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

for(inti=0;i<n;i++)

for(intj=0;j<n;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,请写出该稀疏矩阵的三元组表。

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

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.以二叉链表作存储结构,请写出二叉链表种类概念;借助二叉树遍历的递归算法,试撰写求二叉树高度的算法。

热点推荐:

自考网上报名有疑问、不知晓怎么样选择主考院校及专业、自学考试当地政策不清楚,点击立即报考咨询>>

推荐阅读

2020年十月部分自学考试真题及答案大全

十月各省自考查分时间及入口

2021年四月各省自考报名日期及入口

原创文章,作者:admin,如若转载,请注明出处:http://www.lubanyouke.com/2371.html