自考《数据结构》真题和答案.pdfVIP

⾃考《数据结构》真题和答案

2016年10⽉⾼等教育⾃学考试全国统⼀命题考试

数据结构试卷

（课程代码02331）

本试卷共7页，满分100分，考试时间150分钟。

考⽣答题注意事项：

1?本卷所有试题必须在答题卡上作答。答在试卷上⽆效，试卷空⽩处和背⾯均可作草稿纸

2.第⼀部分为选择题。必须对应试卷上的题号使⽤2B铅笔将答题卡“”的相应代码涂⿊

3.第⼆部分为⾮选择题。毖须注明⼤、⼩题号，使⽤0.5毫⽶⿊⾊字迹签字笔作答。

4?合理安排答题空间，超出答题区域⽆效。

第⼀部分选择题（共30分）

⼀、单项选择题（本⼤题共15⼩题，每⼩题2分，共30分＞

在每⼩题列出的四个备选项中只有⼀个是符合题⽬要求的，请将其选出并将答题卡“”的相应代码涂⿊。错涂、多涂或未涂均⽆分。

1.下列选项中，不属于线性结构特征的是

A.数据元素之间存在线性关系B.结构中只有⼀个幵始结点

C.结构中只有⼀个终端结点D.每个结点都仅有⼀个直接前趋

2.设17个元素的顺序表中，若将第个元素e移动到第个位置,

不改变除e外其他元素之间的相对次序，则需移动的表中元素个数是

A.AMB,i-iC.上汁】D讨3.若⽤⼀个⼤⼩为7的数组作为循环队列的存储结构，且当前rew和盘Ont的值分别

为2和4,在此之前的操作是从队列中删除了⼀个元素及加⼊两个元素，请问这3

个操作之前rear和矗Ont的值分别是

A.0和IB.0和3C.3和6D.4和5

4.已知⼴义表LS=(((a)),((b,(c)),(d,(e,f))),0),LS的长度是

A.2B.3C.4D.5

5.—棵完全⼆叉树T的全部k个叶结点都在同⼀层中且每个分⽀结点都有两个孩⼦结点

于中包含的结点数是

A.k

B.2k-1Ck2D.2k-1

6.如果某⼆叉树的前序遍历序列为abced，中序遍历序列为cebda，则该⼆叉树的后序遍历序列是

A.cedbaBdecbaCecdbaD.ecbad

7.—个森林有m棵树，顶点总数为n,则森林中含有的总边数是

A.m

B.n-lCn-mn+m

8.设图的邻接矩阵A如下所⽰。各顶点的度依次是

0101

0011

A.1,2,1,2B.2,2,1,1C.3,4,2,3D.4,4,2,2

9.若对下厦⽆向图进⾏深度优先遍历，得到的正确遍历序列是

C.a,C,d,e,b,f,g

D.a

11.下列排序算法中，在每⼀趟都能选出⼀个元素放到其最终位置上的是

A.h

,C,a,b,d,e,g,f.e,a,f,g,b,h,c,d

C.d,b,c,a,h,e,f,g.a,b,C,d,h,e,f,g

10.⼰知有向图G如下所⽰G的拓扑序列是

A.a,b,e,c,d,f,g

B.a,c,b,f,d,e,g

,c,d,f,b,e,g

A.插⼊排序.希尔排序.归并排序D.直接选择排序

12．对⼀组数据（2，l2，16，88，5，10）进⾏排序，若前3趟排序结果如下：2，12，l6，5，10，88

第⼀

趟：

第⼆

2，12，5，l0，16，88

趟：

第三

趟：2，5，10，l2，l6，88

则采⽤的排序⽅法是

A.冒泡排序B.希尔排序C.归并排序D.基数排序

13．设有序表为{9，l2，21，32，41，45，52}，当⼆分查找值为52的结点时，元素之间

的⽐较次数是

A.1B.2.3D.4

14.下列选项中，既熊捌回事存储结构也能在链式存储结构上进⾏查找的⽅法是

A.散列查找B.顺序查找

C.⼆分查找D.以上选项均不能

15.在⼀棵5阶B树中，每个⾮根结点中所含关键字的个数最少是

A.1B.2C.3D.4

第⼆部分⾮选择题（共70分）

⼆、填空题（本⼤题共l0⼩题，每⼩题2分，共20分）

16.两个栈S和S2共⽤含100个元素的数组S[0⼀99]，为充分利⽤存储空间，若S2的

栈底兀素保存在S[99]中，则Si的栈底兀素保存在__________中。

17?在⼀个单链表中，已知指针变量q所指结点不是表尾结点，若在q所指结点之后插⼊指针变量S所指结点，则正确的执