​数据结构自考2015年10月真题

数据结构自考2015年10月真题及答案解析

本试卷为单选题型，填空题，算法阅读，算法设计等题型。

一、单项选择题(本大题共15小题，每小题2分，共30分) 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。

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

A.网
B.栈
C.队列
D.线性表

2.长度为n的顺序表，删除位置i上的元素(0≤i≤n-1)，需要移动的元素个数为(　　)

A.n-i
B.n-i-1
C.i
D.i+1

3.栈采用不同的存储方式时，下列关于出栈过程的叙述中，正确的是(　　)

A.顺序栈需要判定栈空，链栈也需要判定
B.顺序栈需要判定栈空，而链栈不需要判定
C.顺序栈不需要判定栈空，而链栈需要判定
D.顺序栈不需要判定栈空，链栈也不需要判定

4.若一个栈以数组V[0..n-1]存储，初始栈顶指针top为n，则x入栈的正确操作是(　　)

A.top=top+1;V[top]=x
B.V[top]=x;top=top+1
C.top=top-1;V[mp]=x
D.V[top]=x;top=top-1

5.在二维数组a[9][10]中：每个数组元素占用3个存储空间，从首地址SA开始按行优先连续存放，则元素a[8][5]的起始地址是(　　)

A.SA+141
B.SA+144
C.SA+222
D.SA+255

6.广义表A=(x，((y)，((a))，A))的深度是(　　)

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

7.一棵左子树为空的二叉树在前序线索化后，其空指针域个数为(　　)

A.0
B.1
C.2
D.不确定

8.下列关于哈夫曼树的叙述中，错误的是(　　)

A.用n个结点构造的哈夫曼树是唯一的
B.哈夫曼树中只有度为0或度为2的结点
C.树中两个权值最小的结点可能是兄弟结点
D.同一结点集构造的二叉树中，哈夫曼树的WPL最小

9.6个顶点的强连通图中，含有的边数至少是(　　)

A.4
B.5
C.6
D.7

10.对题10图进行深度优先搜索遍历，下列选项中，正确的遍历序列是(　　)

A.

B.

C.

D.

11.下列选项中，能构成题10图中一条路径的是(　　)

A.

B.

C.

D.

12.有向图采用邻接矩阵存储，某一行中非零元素的个数等于(　　)

A.对应顶点v的度
B.对应顶点v的出度
C.对应顶点v的入度
D.依附于对应顶点v的边数

13.下列选项中，符合堆定义的是(　　)

A.{102，24，55，60，89，93}
B.{24，89，55，60，93，102}
C.{102，93，55，60，89，24}
D.{102，60，89，93，55，24}

14.已知关键字序列为{66，82，25，51，98，108}，利用快速排序方法，以第一个元素为基准得到的一趟排序结果为(　　)

A.{25，51，66，82，98，108}
B.{25，51，66，98，82，108}
C.{51，25，66，108，98，82}
D.{51，25，66，82，98，108}

15.下列选项中，其平均查找性能与基于二叉排序树的查找相当的是(　　)

A.二分查找
B.顺序查找
C.分块查找
D.索引顺序查找

二、填空题(本大题共10小题，每小题2分，共20分) 请在每小题的空格中填上正确答案。错填、不填均无分。

11.线性表(a1，a2，…，an)中，除_______外，每个元素都有唯一的直接前趋。

12.指针P指向单链表中某个结点，在P所指结点后插入指针s所指的结点，正确的操作序列是_______。

13.设Push，、Pop分别表示人栈和出栈操作，x=10，y=20，z=30。依次进行下列操作：Push(y)、Push(z)、Push(z)、X=Pop()、Y=Pop()，x,y的值分别是_______。

14.广义表L=(a，(b，e，(e，f，g，h)))，head(L)= _______。

15.设树T的度为3，其中度为1、2和3的结点个数分别为3、2和1，则T中叶子结点的个数为_______。

16.由一棵二叉树的后序遍历序列和_______遍历序列可以唯一确定该二叉树。

17.在有n个顶点的无向图中，任一顶点的度不大于_______。

18.借助于一个栈来实现的图的遍历算法是_______。

19. 若有向图中存在拓扑排序序列，则该图一定不存在_______。

110.已知关键字序列为{66，82，25，51，98，108}，一趟二路归并排序的结果为_______。

三、解答题(本大题共4小题，每小题5分，共20分)

21.已知n阶对称矩阵A的元素为(0≤i，j≤n-1)，采用“按行优先”将下三角部分的元素(含主对角线)保存在一维数组sa中，且约定元素,0保存在sa[0]中，元素(≤i，j≤n-1)保存在sa[k]中，请给出由下标i，j计算下标k的计算公式。

22.己知二又树T如题27图所示。请问答下列问题：(1)画出该二叉树对应的森林。(2)写出对森林进行前序遍历的遍历序列i

23.题28图所示为一棵含2个关键字的3阶B树T。现将关键字序列{40，60，70，20，10}依次插入到T中，画出每插入一个关键字后得到的树型。

24.给定无向带权连通图G如题29图所示，从顶点v0开始，使用普里姆(Prim)算法，求G的最小生成树T。请回答下列问题。(1)画出最小生成树T。(2)计算T中各边权值之和。

四、算法阅读题(本大题共4小题，每小题5分，共20分)

31.请写出下列程序段的输出结果。

32.己知存储稀疏矩阵三元组表的类型定义如下：#define MAX 100typedef struct{            int i, j;                //非零元素的行号、列号(下标)            int v;                 //非零元素值} TriTupleNode;typedef struct{      TriTupleNode data[ MAX];           //存储三元组的数组       int m, n, t;                   //矩阵的行数、列数和非零元素个数      }TSMatrix;               //稀疏矩阵类型函数f31的功能是将a所表示的矩阵转置后保存在*b中。请在空白处填写适当内容，使其完成指定功能。

33.已知二叉树的二叉链表类型定义如下：为完成指定功能，请在空白处填写适当内容，使其功能完整。

34.函数f33的参数t指向题33图所示的二叉排序树的根，阅读程序，回答下列问题。(1)若连续3次调用函数f33，参数K的值依次取10、25、10，写出每次调用后函数的输出结果;(2)说明函数f33的功能。

五、算法设计题(本大题共1小题，共10分)

41.已知顺序表SeqList定义如下：typedef struct{    KeyType key;    InfoType otherinf0;  }RecType：typedef RecType SeqList[MAXSIZE+1];编写函数，用冒泡排序法将n个元素的待排序列R按关键字降序排序。函数原型为：int f34(SeqList R，int n)。