数据结构自考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树的叙述中，错误的是(　　)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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