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

已知二叉树的定义如下：

typedef struct node{

int data;

struct node *lchild, *rchild;

}*Bitptr;

编写递归算法求二叉树的高度。函数原型为：int f34(Bitptr t);

设有单链表类型定义如下：

typedef struct node{

int data;

struct node *next;

} *LinkList;

阅读下列算法，并回答问题：

下面程序实现插入排序算法。

在空白处填写适当的内容，使该程序功能完整。

阅读下列程序，并回答问题：

(1)写出执行该程序后的输出结果;

(2)简述函数f31的功能。

已知线性表(a1,a2,a3...，an)按顺序存放在数组a中，每个元素均为整数，下列程序的功能是将所有小于0的元素移到全部大于等于0的元素之前。例如，有7个整数的原始序列为(x,x,-x,-x,x,x,-x)，变换后数组中保存的序列是(-x,-x,-x,x,x,x,x)。请在程序处填入合适的内容，使其成为完整的算法。

已知广义表如下：

A=(B,y)

B=(x，L)

L=(a，b)

要求：

(1)写出下列操作的结果tail(A)=_______________.head(B)=______________。

(2)请画出广义表A对应的图形表示。

已知二叉树如下：

请画出该二叉树对应的森林。

请回答下列问题：

(1)英文缩写DAG的中文含义是什么?

(2)请给出下面DAG图的全部拓扑排序。

如果要为文件中的每个记录建立一个索引项，则这样建立的索引表称为___________。

要在[0..n-1]的向量空间中建立两个栈stack1和stack2，请回答：

(1)应该如何设计这两个栈才能充分利用整个向量空间?

(2)若stack1的栈顶指针为top1,stack2的栈顶指针为top2，如果需要充分利用整个向量空间，则：栈stack1空的条件是：___________;栈stack2空的条件是：___________;栈stackl和栈stack2满的条件是：___________。

影响排序效率的两个因素是关键字的___________次数和记录的移动次数。

对任一m阶的B树，每个结点中最多包含___________个关键字。

若两个关键字通过散列函数映射到同一个散列地址，这种现象称为___________。

用5个权值{3, 2，4，5，1}构造的哈夫曼(Huffman)树的带权路径长度是___________。

若无向图G中有n个顶点m条边，采用邻接矩阵存储，则该矩阵中非0元素的个数为___________。

使用一个100个元素的数组存储循环队列，如果采取少用一个元素空间的方法来区别循环队列的队空和队满，约定队头指针front等于队尾指针rear时表示队空。若为front=8，rear=7，则队列中的元素个数为___________。

已知链表结点定义如下：

typedef struct node{

char data[16];

struct node *next;

} LinkStrNode;

如果每个字符占1个字节，指针占4个字节，则该链表的存储密度是___________。

3个结点可以组成___________种不同树型的二叉树。

下面程序段的时间复杂度为___________。

sum=1;

for(i=0;sum

sum+=1;

若需高效地查询多关键字文件，可以采用的文件组织方式为( )

设有一组关键字(19, 14, 23, 1，6，20, 4，27, 5，11, 10, 9)，用散列函数H(key)=key%13构造散列表，用拉链法解决冲突，散列地址为1的链中记录个数为( )

已知二叉树结点关键字类型为字符，下列二叉树中符合二叉排序树性质的是( )

下图G=(V,E)是一个带权连通图，G的最小生成树的权为( )

在下图中，从顶点1出发进行深度优先遍历可得到的序列是( )

如果在排序过程中不改变关键字相同元素的相对位置，则认为该排序方法是( )

若根结点的层数为1，则具有n个结点的二叉树的最大高度是( )

在图G中求两个结点之间的最短路径可以采用的算法是( )

串匹配算法的本质是( )

若一棵二叉树的前序遍历序列与后序遍历序列相同，则该二叉树可能的形状是( )

设有一个10阶的对称矩阵A，采用行优先压缩存储方式，a11为第一个元素，其存储地址为1，每个元素占一个字节空间，则a85的地址为( )

若带头结点的单链表的头指针为head，则判断链表是否为空的条件是( )

若元素的入栈顺序为1，2，3....，n，如果第2个出栈的元素是n，则输出的第i(1<=i<=n)个元素是( )

数据的四种存储结构是( )

若对某线性表最常用的操作是在最后一个结点之后插入一个新结点或删除最后一个结点，要使操作时间最少，下列选项中，应选择的存储结构是( )