答案
一、单项选择题（每小题 2 分，共20分）
1．在下面给出的链式存储结构中，能在O(1)时间内完成在指定结点p之前插入元素x的结构是为（ ）。
A）单向链表 B）单向循环链表 C）带表头的单向链表 D）双向循环链表 参考答案：D）
2．栈应用的典型事例是（ ）。
A）排队 B）查找 C）归并 D）用“算符优先法”进行表达式求值 参考答案：D）
3．一般情况下，将递归算法转换成等价的非递归算法应该设置（ ）。
A）栈 B）队列 C）堆栈或队列 D）数组 参考答案：A） 4．（ ）是C语言中\"abcd32lABCD\"的子串。
A）abed B）d2lAB C）\"abcABC\" D）\"21AB\" 参考答案：D）
5．有一矩阵为A[-3:1,2:6]，每个元素占一个存储单元，存储的首地址为100，以行序为主，则元素a-1,4的地址为（ ）。
A）111 B）112 C）113 D）125 参考答案：B）
6．从L=((apple,pear),(banana,orange))中，取出pear元素的表达式为（ ）。
A）head(tail(L)) B）head(head(tail(L))) C）tail(head(tail(L))) D）head (tail (head(L))) 参考答案：D） 7．若一个具有N个顶点，K条边的无向图是一个森林（N＞K），则该森林中必有（ ）棵树。
A）K B）N C）N-K D）1
【分析】因为一棵具有n个顶点的树有n-1条边，因此设此森林中有m棵树，每棵树具有的顶点数为vi（l≤i≤m），则：
v1+v2+„+vm=N (1) (v1-1)+(v2-1)+„+(vm-1)=K (2) 由(1)-(2)可知N-K为森林所含树的棵数。 参考答案：C）
8．采用分块查找时，如某线性表中共有256个元素，查找每个元素的概率相同，假设采用顺序查找来确定元素所在的块，则每块包含（ ）个结点时，平均查找长度最小。
A）256 B）15 C）16 D）18
【分析】设长度为n的表均匀地分成b块，每块含有s个元素，用顺序查找确定所在的块时平均查找长度为
1n1n(s)1，当s=n=16时，(s)1取最小值n+1=17。 2s2s参考答案：C）
9．若需在O(nlogn)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（ ）。
A）快速排序 B）堆排序 C）归并排序 D）直接插入排序 参考答案：C）
10．在如下图所示的AOE网中，关键路径长度为（ ）。
A）16 B）13 C）10 D）9 参考答案：A） 二、（本题8分）
已知一个栈S的输入序列为abcd，下面两个序列能否通过栈的Push和Pop操作输出；如果能，请写出操作序列；如果不能，清说明原因。
（1）dbca （2）cbda 解答： （1）不能实现，由于最先d出栈，要求abc先入栈，由栈的特点，出栈序列最能为dcba。 （2）可以实现，操作序列为：
入栈，入栈，入栈，出栈，出栈，入栈，出栈，出栈。 三、（本题8分）
已知一组关键字为（19，14，23，1，68，20，84，27，55，11，10，79），哈希函数：H(key)=key MOD 13，哈希地址空间为0~12，请构造用链地址法处理冲突的哈希表，并求平均查找长度。
解答：哈希表如下图所示：
平均查找长度为ASL=
1(1*6+2*4+3*1+4*1)=1.75 12四、（本题9分）
已知某字符串S中共有8种字符，各种字符分别出现2次、1次、4次、5次、7次、3次、4次和9次，对该字符串用｛0，1｝进行前缀编码，问该字符串的编码至少有多少位？
解答：按照哈夫曼树的算法，以字符出现次数作为权，可构造出8种字符构造的哈夫曼树，如下图所示。
由于字符编码长度与路径长度相等，所以字符串的编码至少有：
wli18ii5*1+5*2+4*3+3*5+3*4+3*4+2*9+2*7=98位。
五、（本题9分）
一棵非空的有向树中恰有一个顶点入度为0，其他顶点入度为1。但一个恰有一个顶点入度为0、其他顶点入度为1的有向图却不一定是一棵有向树。请举例说明之。
解答：如下图所示的有向图，只有一个顶点的入度为0外，其他每个顶点的入度都为1，因为非连通，所以此图却不是有向树。
六、（本题8分）
将如下图所示的森林转换成一棵二叉树，并写出森林的两种遍历序列。
解答：将森林转化为二叉树时，可用孩子兄弟表示法先将每棵树转化为二叉树，然后再认为二叉树的根为兄弟，进一步将所有二叉树转化为一棵二叉树，如下图所示：
森林的遍历等价于相应的二叉树的遍历，易知： 森林的先序遍历序列为ABCDEFGHIJKLMN； 森林的中序遍历序列为CEDBAGHIFKJMNL。 七、（本题9分）
已知哈希表地址空间是0..8，哈希函数是H(k)=k%7，采用线性探测再散列处理冲突，将序列{100,20,21,35,3,78,99,45}数据序依次存入此哈希表中，列出插入时的比较次数，并求出在等概率下的平均查找长度。
解答：哈希表及查找各关键字的比较次数如下表所示： 哈希表及查找各关键字的比较次数 哈希地址 关键字 比较次数 0 21 1 1 35 2 2 100 1 3 3 1 4 78 4 5 99 5 6 20 1 7 45 5 8 平均查找长度=
411214252.5
8八、（本题9分）
设有n个不同的英文单词，这些单词是无序的，它们的长度都相同，均为d(并且d<10)，设n>>d，试问使用哪种排序方法的时间复杂度最佳，并说出理由。
解答：采用基数排序法时间复杂度最佳，因为n>>d，可知时间复杂度为O(d(n+rd))≈O(n)，此时其他排序方法时间复杂度至少为O(nlog(n))。
九、（本题9分）
试分别画出具有3个结点的树和具有3个结点的二叉树的所有不同形态。 解答：具有3个结点的树的不同形态如下图所示。
具有3个结点的二叉树的不同形态如下图所示。
十、（本题10分）
假设二叉树中每个结点所含数据元素均为单字母，以二叉链表为存储结构，试编写算法按如下图所示的树状显示二叉树。
解答：从上图来看，二叉树的第一层显示在第一列，第二层显示在第二列，第三层显示在第三列；每行显示一个结点，从上至下是先显示右子树，再显示根，最后最左子树，也就是以先遍历右子树，最后遍历左子树的中序遍历次序显示各结点。
具体算当如下：
void DisplayBTWithTreeShape(BiTree T,int level=1)
// 按树状形式显示二叉树，level为层次数，可设根结点的层次数为1 { if(T) { //空树不显式，只显式非空树 DisplayBTWithTreeShape(T->rchild,level+1);//显示右子树 cout< 因篇幅问题不能全部显示，请点此查看更多更全内容