2021年4月自考数据结构导论02142真题与答案

对于参加2021年10月自考的考生来说，2021年4月自考真题的参考价值最高，下文是希赛自考频道整理的2021年4月自考数据结构导论02142真题与答案，想要查看更多自考真题，可以选择【自考历年真题】【2021年自考真题汇总】【自考题库app下载】。

2021年4月自考数据结构导论02142真题与答案

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

2.答题前,考生务必将自己的考试课程名称、姓名、准考证号用黑色字迹的签字笔或钢笔填写在答题纸规定的位置上。

注意事项:每小题选出答案后.用2B铅笔把答题纸上对应题日的答案标号涂黑。如需改动.用橡皮擦干净后﹐再选涂其他答案标号。不能答在试题卷上。

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

1.设某数据结构A的二元组形式表示为A=(D).R).数据元素集合I)= (01.02.03,04.05.06.07.08,09}.数据元素之间的关系R= {r).r= {<01.02>. <01.03>. < 01.01>.<02.05> .<02.06>.< 03.07>.< 03.08> .<03.09> } .则数据结构A属于

A.线性结构

B.树形结构

C.存储结构

D.图结构

2.算法指的是求解给定问题所需的

A.计算机程序

B.查找方法

C.排序方法

D.处理步骤

3.若长度为n的线性表采用顺序存储结构。在其第i(1≤i≤n+ 1)个位置插入一个新元素的算法的时间复杂度为

A.0(1)

B.0(log: n)

C. ((n)

D. ()(n° )

4.在单链表指针为p的结点之后插入指针为s的结点，正确的指针操作是

A.p- >nex1=s;s- > next=p一> next;

B.s- >nexl=p一> next;p ->next = s;

C.p一> next=s;p一>nex1=s -> next;

D.p-> nexl=s一> nexl;p- -> nex1=s;

5.设数组data[ m]作为循环队列SQ的存储空间.fromt为队头指针,rear为队尾指针,则执行

出队操作后其头指针front值为

A. SQ. front- SQ. front t 1

B. SQ. front=(SQ. front十1)%(m一1)

C. SQ. front= (SQ. front- 1)%m .

D. SQ. front= (SQ. front + 1)%m

6.对稀疏矩阵使用三元组表示法的目的是

A.节省存储空间

B.降低时间复杂度

C.便于矩阵运算实现

D.便于输人和输出

7.操作系统中的进程调度使用先到先服务的方法.所采用的数据结构是

A.最小堆

B.堆栈

C.队列

D.二叉树

8.假设通信电文使用的字符集为{a.b.c.d.c.f).各字符在电文中出现的频率分别为{34.5.12.23.8.18).利用构造Huffman树对每个字符进行编码.则其中编码长度最长的字符是

A.a.b

B. a.d

C. b.e

D. e.f

9.一个具有1025个结点的二叉树的高度h在

A.10至1024之间

B.10至1025之间

C.11至1024之间

D.11至1025之间

10.由3个结点可以构造出多少种不同的二叉树?

A.2种

B.3种

(.4种

D.5种

11.要使具有n个顶点的有问图是强连通图，至少需要的边数是

A.n-l

B. n

(.n+1

D.2n

12.某散列表表长为40.散列雨数为H(key)= key%p.则p通常选择

A.36

B.37

C.38

D.39

13.若采用链地址法构造散列表.散列雨数为H(key)=key mod 17.链表的链首指针构成一个指针数组，数组的下标范围为

A.0~16

B.0~17

C.1~16

D.1~ 17

14.取键值55为基准.执行一趟快速排序后可能得到的序列是

A. [63,12,34.45.27] 55 [41.72]

B.[45,34,12.41] 55 [72.63.27]

C.[41.12.34.45.27] 55 [72.63]

D.[12.27.45.11] 55 [34.63.72]

二、填空题:本大题共13空,每空2分,共26分。

16.数据结构是指一组相互之间存在一种或多种特定关系的数据的组织方式和它们在计算机内的存储方式以及定义在该组数据上的一组                。

17.数据元素由                组成。

19.线性表中结点具有                的关系。

20.表长为n的顺序表插人算法的平均移动次数约为                

22.栈是运算受限的线性表,这种线性表上的插人和删除运算限定在表的某一端进行。允许进行插入和删除的一端称为                

23.对称矩阵有近一半的元素可以通过其对称元素获得.可将含有n'个元素的对称矩阵压缩存储到含有                个元素的一 维数组中。

24.深度为k(k≥1)的二叉树至多有                个结点。

三、应用题:本大题共5小题,每小题6分,共30分。

29.设一个链栈的输入序列为A.B.C.请问共有几种可能的输出序列?试写出所得到的所有可能的输出序列。

30.假设一棵二叉树的中序序列与后序序列分别为:B ACDEFC; H和BCA E DG; H F.请画出该二叉树。

31.用Kruskal方法求题31图所示的图的最小生成树。(要求给出求解过程)

32.根据二叉排序树的插人算法.从空树开始建立键值序列{50.48.24.55.53.90>的二叉排序树，要求给出建立过程。

33.对于给定的一组键值:25.11.22.34.5.44.76.61.100.3.14.120.请分别写出直接插入排序和冒泡排序的第一趟排序结果。