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

二叉排序树的类型定义如下：

typedef struct node {i

     nt data;

      struct node *lchild,*rchild;

}*BSTree;

编写递归算法从小到大输出二叉排序树T中所有data域值大于m且小于n的数据。函数原型为void f34(BSTree T， int m， int n)

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

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

阅读下列算法(假设栈的操作函数都已定义)，并回答问题：

(1)自底向上写出执行while语句之前栈S中的元素序列。

(2)写出该函数的最后输出结果。

单链表类型定义如下：

(1)该算法的功能是什么?

(2)若单链表的长度为n，算法的时间复杂度是多少?该时间复杂度和链表的初始状态有关吗?

判别以下序列是否为堆，若不是，将其调整为大根堆，并画出大根堆。

①(1,5,7,20,18,8,10,40)

②(18,9,5,8,4,17,21,6)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

对序列(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)

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

• A.e
• B.2e
• C.
• D.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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