​数据结构自考2013年1月真题

数据结构自考2013年1月真题及答案解析

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

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

1.数据的逻辑结构可以分为(　　)

A.动态结构和静态结构
B.顺序结构和链式结构
C.线性结构和非线性结构
D.简单结构和构造结构

2.线性表是一个有限序列，组成线性表的基本单位是(　　)

A.数据项
B.数据元素
C.数据域
D.字符

3.栈中有a、b和c三个元素，a是栈底元素，c是栈顶元素，元素d等待进栈，则不可 能的出栈序列是(　　)

A.dcba
B.cbda
C.cadb
D.cdba

4.稀疏矩阵的三元组表是(　　)

A.顺序存储结构
B.链式存储结构
C.索引存储结构
D.散列表存储结构

5.已知广义表G，head(G)与tail(G)的深度均为6，则G的深度是(　　)

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

6.下列编码集合中，属于前缀编码的一组是(　　)

A.{11,10,001,101,0001}
B.{00,010,0110,1000}
C.{11,01,001,0101,0001}
D.{0,10,110,1011}

7.如题7图所示二叉树的中序序列为(　　)

A.ACDB
B.DCBA
C.CDBA
D.ABCD 题7图

8.有向图中所有顶点入度之和与所有顶点出度之和的比是(　　)

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

9.含有n个顶点和e条边的有向图的邻接矩阵中，零元素的个数是(　　)

A.e
B.2e
C.
D.

10.n个顶点的无向连通图，其生成树的边数为(　　)

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

11.用自底向上的冒泡排序方法对序列(8,13,26,55,29,44)从大到小排序，第一趟排序需进行交换的次数为(　　)

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

12.对序列(8,13,26,55,29,44)从小到大进行基数排序，第一趟排序的结果是(　　)

A.(13,44,55,26,8,29)
B.(13,26,55,44,8,29)
C.(8,13,26,29,44,55)
D.(29,26,8,44,55,13)

13.采用分块查找时，要求数据(　　)

A.块内有序
B.分块有序
C.分块无序
D.每块中数据个数必须相同

14.下列关于散列函数的说法正确的是(　　)

A.散列函数越复杂越好
B.散列函数越简单越好
C.用除余法构造的散列函数是最好的
D.在冲突尽可能少的情况下，散列函数越简单越好

15.下列关于m阶B树的叙述中，错误的是(　　)

A.每个结点至多有m棵子树
B.每个结点至多有m-1个关键字
C.所有的叶结点均在同一层上
D.根结点至少有 棵子树

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

11.算法的时间复杂度与实现时采用的程序设计语言____________。

12.在长度为n的顺序表的第i(1≤i≤n)个元素之后插入一个元素时，需向后移动___________个元素。

13.设循环队列存放在向量data[0..m-l]中，在出队操作后，队头指针front变化为___________。

14.树的前序遍历序列等同于该树对应二叉树的____遍历序列。

15.一个100×90的整型稀疏矩阵有10个非零元素，设每个整型数占2个字节，则用三元组表存储该矩阵时，所需的字节数是___________。

16.当用二叉链表作为n个结点的二叉树的存储结构时，空指针域的个数是____。

17.采用邻接表表示n个顶点的有向图时，若表结点的个数为m，则该有向图的边数 为___________。

18.对同一个基本有序的待排序列分别进行堆排序、快速排序和冒泡排序，最省时间的 算法是___________。

19.在16个记录的有序顺序表中进行二分查找，最大比较次数是___________。

110.在排序算法中，若排序前后具有相同关键字的记录之间的相对次序保持不变，则称这种排序方法是___________的。

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

21.在定义顺序表时，存放表结点的向量空间不宜过大也不宜过小，为什么?

22.画出题27图所示树的孩子链表。 

23.已知一个无向图G如题28图所示，以顶点①为根，且小序号优先，分别画出G的深度优先生成树和广度优先生成树。

24.判别以下序列是否为堆，若不是，将其调整为大根堆，并画出大根堆。①(1,5,7,20,18,8,10,40)②(18,9,5,8,4,17,21,6)

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

31.单链表类型定义如下：(1)该算法的功能是什么?(2)若单链表的长度为n，算法的时间复杂度是多少?该时间复杂度和链表的初始状态有关吗?

32.阅读下列算法(假设栈的操作函数都已定义)，并回答问题：(1)自底向上写出执行while语句之前栈S中的元素序列。(2)写出该函数的最后输出结果。

33.下列算法的功能是在中序线索树中查找结点*p的前趋，填上适当内容使算法完整。

34.分析下列排序算法中语句1和语句2的频度以及此算法的时间复杂度，并指出该算法是属于哪一种排序方法。

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

41.二叉排序树的类型定义如下：typedef struct node { i      nt data;      struct node *lchild,*rchild;}*BSTree;编写递归算法从小到大输出二叉排序树T中所有data域值大于m且小于n的数据。 函数原型为void f34(BSTree T， int m， int n)