华中科技大学计算机学院数据结构(计算机专业)试题.doc

华中科技大学计算机学院
《数据结构》试卷 (A卷)
2010 —2011 年度第二学期计算机学院
班级______ 学号___________ 姓名_________
考试时间：2011年 月 日 考试形式：闭卷
题号
一
二
三
四
五
六
七
八
总分
核对人
题分
10
10
10
12
32
10
6
10
100

得分

得分
评卷人

一、单项选择题(从下列各题四个备选答案中选出一个正确答案,将其代号(A,B,C,D)写在下表中,每小题1分,共10分)

题号
1
2
3
4
5
6
7
8
9
10
答案

1．对于栈的进栈和出栈运算，采用______存储结构时运算效率最高。
A．单链表 B．容量足够大的顺序表
C．单向循环链表 D．双向循环链表
2．链式队列和顺序队列比较，具有_____这个优势。
A．进队操作方便 B．出队操作方便
C．通常不会出现满队列情况 D．求队列元素个数方便
3．下列关于串的叙述中，正确的是_____。
A．2个串的长度相等，则2个串相等 B．空串至少包一个空格
C．替换操作可以实现字符的删除 D．一个串的长度至少是1
4．二叉树在线索化后，下列问题中相对难解决的是____。
A．先根线索二叉树中求先根后继
B．中根线索二叉树中求中根前趋
C．中根线索二叉树中求中根后继
D．后根线索二叉树中求后根后继
5．对序列（30，26，18，16，5，66）进行2遍 ________排序后得到序列（5，16，18，26，30，66）。
A．选择 B．冒泡 C．插入 D．归并
6．在下列排序算法中，_______算法可能出现如下情况：在最后一趟排序之前，所有元素均不在其最终的位置上。
A．堆排序 B．快速排序 C．冒泡排序 D．插入排序
7．由4个结点可以组成______棵不同形态的二叉树。
A．10 B．12 C．14 D．16
8．对包含n个元素的散列表进行检索，平均查找长度为____。
A．O(logn) B．O(n) C．O(nlogn) D．不直接依赖于n
9．广义表 ((a,(b),c),((),(d)),(((((e)),f))),())的长度是____。
A．2 B．3 C．4 D．5
10．对某无向图进行一次深度优先搜索遍历，如果能访问到所有的顶点，则该无向图一定是________。
A．连通图 B．树图 C．有回路的连通图 D．完全图

得分
评卷人

二、填空题(在下表中填写正确的答案,每空1分,共10分)

题号
1
2
3
4
5
6
7
8
9
10
答案

1． 具有n个单元、用首尾指针、无标志位的循环队列中，队满时共有_______个元素。
2． 设顶点数为n，弧数为e的有向图的用邻接表存储，求顶点值为V的顶点的入度的算法时间复杂度为_____。
3． 某哈夫曼树有11个结点，则它有____个度为2的结点。
4． 设森林T中有三棵树，第一、二、三棵树的结点个数分别是n1，n2，n3，那么当把森林转换成二叉树后，其根结点的右子树上有______个结点。
5． 当线性表经常进行插入和删除操作时，应该选择使用________存储结构。
6． 设栈S和队列Q的初始状态为空，元素a、b、c、d、e、f依次通过栈S，一个元素出栈后即进入队列Q。若这6个元素出队列的顺序是b、d、c、f、e、a，则栈S的容量至少应该是______。
7． 满足先根遍历序列为a、b、c，后根序列为c、b、a的二叉树共有______棵。
8． 按广度优先搜索遍历图的算法需要借助的辅助数据结构是_____。
9．高度为4的平衡二叉树至少有_____个结点。
10．对n个元素的序列进行简单选择排序，最多进行______次元素的交换。
得分
评卷人

三、判断题(判断下列各题叙述的正确性,用√表示正确，×表示错误，每小题1分,共10分)
题号
1
2
3
4
5
6
7
8
9
10
答案

1． 可以以随机方式访问以三元组方式存放的稀疏矩阵的非零元素。
2． 对完全二叉树，如已知高度h和第h层的结点数，一定能求二叉树的结点数。
3． 算法分析的目的之一是分析算法的效率以求改进。
4． 正确性是算法的特征之一。
5． 线性表的逻辑结构与存储顺序总是一致的。
6． 在循环链表中，任何一个结点的指针部分都指向其直接后继元素的结点。
7． 将递归算法改写成非递归算法时，通常需要使用的数据结构为栈。
8． 有n个顶点，n2-2n+2条弧的有向图不一定是强连通图。
9． 某二叉树的中根遍历序列得到的关键字序列是递增有序的，则该二叉树一定是二叉排序树。
10．快速排序方法的每一趟都能找到一个元素把它放到最终的位置上。
得分
评卷人

四、存储结构图(要求标明各结点的数据域、指针域、权值等，每小题6分，共12分)
1． 如下图所示为二叉树排序树T的一种线索二叉树逻辑结构图，试画出插入结点48后的线索二叉树的物理存储结构图。

2． 试画出如下图所示无向网的邻接多重表存储结构图。

得分
评卷人

五、求解问题(每小题8分，共32分)

1． 如下图所示为n行2n-1列矩阵A[1..n，1..2n-1]，现以行为主序进行压缩存储到一维数组SA[1…m]中。（1）试问m值是什么？（2）假定非零元素A[i，j]保存在SA[k]中，试写出由下标(i，j)到k的转换公式。

2．如下图所示为有序表（10，15，21，33，44，60，67，68，70，86）的判定树，试问该判定树是否正确？如果正确，说明理由，错误则指出错误处并给出正确结果。

3．试用元素序列(63、72、88、68、66、38、43),生成平衡二叉排序树T,(1)按步骤画出该平衡二叉排序树T,(2)写出平衡二叉排序树T的中序遍历序列,(3)假定每个元素的查找概率相等,计算查找成功时的平均查找长度。

4．已知图的邻接表法存储结构如下，从顶点A出发求图的深度遍历的结果。

得分
评卷人

六、证明题(每小题5分，共10分)

1， 证明在哈夫曼树中最小权值所对应的叶结点的层数正好是哈夫曼树的高度。

2．证明有n个结点的完全二叉树的高度为élog2(n+1)ù。

得分
评卷人

七、编程题(6分)

根据二叉树的先根和中根遍历序列，试编写函数CreateBiTree构造该二叉树。相关说明如下：
typedef struct node {
ElemType data;
struct node *lchild,*rchild;
} NODE,*bitTree;
bitTree CreateBiTree(ElemType X[]，ElemType Y[]，int n); /*要实现的函数原型说明,其中X、Y分别表示n个结点的二叉树的先根和中根遍历序列*/

得分
评卷人

八、阅读并改进算法(每小题5分，共10分)

#define N 10
void main()
{ int a[N] ={1,4,5,6, 8,10,11,13,15,20 }, b[N],i,j,k;
scanf（”%d”,&k）;
for(i=0;i<N;i++) b[N-i-1]=k-a[i];
i=j=0;
while(i<N && j<N)
if (a[i]==b[j]) break;
else if (a[i]<b[j]) i++;
else j++;
if (i>=N ||j>=N) printf("No Solution!");
else printf("%5d%5d",a[i],k-b[j]);
}
(1) 阅读上面的算法程序，叙述算法的功能，并给出算法的时间与空间复杂度。
(2) 改写算法，使改进算法的时间和空间效率尽可能提高。

《数据结构》试卷参考答案 (A卷)

2010 —2011 年度第二学期计算机学院
一、单项选择题(从下列各题四个备选答案中选出一个正确答案,将其代号(A,B,C,D)写在下表中,每小题1分,共10分)
题号
1
2
3
4
5
6
7
8
9
10
答案
B
C
C
D
A
D
C
D
C
A
二、填空题(在下表中填写正确的答案,每空1分,共10分)
题号
1
2
3
4
5
6
7
8
9
10
答案
n-1
(n+e)
5
n2+n3
链式
3
4
队列
7
n-1
三、判断题(判断下列各题叙述的正确性,用√表示正确，×表示错误，每小题1分,共10分)
题号
1
2
3
4
5
6
7
8
9
10
答案
×
√
√
×
×
×
√
×
√
√

四、存储结构图(要求标明各结点的数据域、指针域、权值等，每小题6分，共12分)
2． 如下图所示为二叉树排序树T的一种线索二叉树逻辑结构图，试画出插入结点48后的线索二叉树的物理存储结构图。
答案：

2． 试画出如下图所示无向网的邻接多重表存储结构图。
参考答案：

五、求解问题(每小题8分，共32分)
2． 如下图所示为n行2n-1列矩阵A[1..n，1..2n-1]，现以行为主序进行压缩存储到一维数组SA[1…m]中。（1）试问m值是什么？（2）假定非零元素A[i，j]保存在SA[k]中，试写出由下标(i，j)到k的转换公式。

答案：（1）m=n2
（2）k=(i-1) 2+i+j-n (当 |j-n|<i)
2. 如下图所示为有序表（10，15，21，33，44，60，67，68，70，80）的判定树，试问该判定树是否正确？如果正确，说明理由，错误则指出错误处并给出正确结果。
答案：

注：没按序号作为结点值扣1分
3．试用元素序列(63、72、88、68、66、38、43),生成平衡二叉排序树T,(1)按步骤画出该平衡二叉排序树T,(2)写出平衡二叉排序树T的中序遍历序列,(3)假定每个元素的查找概率相等,计算查找成功时的平均查找长度。
答案：
（1）
（2）38，43，63，66，68，72，88
（3）ASL=（1+2*2+3*4）/7=17/7

4．已知图的邻接表法存储结构如下，从顶点A出发求图的深度遍历的结果。

答案： ABDECF
六、证明题(每小题5分，共10分)

2， 证明在哈夫曼树种最小权值所对应的叶结点的层数正好是哈夫曼树的高度。
略
2．证明有n个结点的完全二叉树的高度为élog2(n+1)ù。
略

七、编程题(6分)

1． 已知大小为N的数组A[N]、B[N]分别存放着有N个结点的某二叉树的先根和中根遍历序列，试编写函数CreateBiTree构造该二叉树。相关说明如下：
参考答案：
bitTree CreateBiTree(ElemType X[]，ElemType Y[N]，int n)
{
int i;
if (!n) return NULL;
T=(BitTree)malloc(sizeof(NODE));
T->data=X[0];
for(i=0; Y[i]==X[0] ;i++);
T->lchild= CreateBiTree(&X[1],Y,i);
T->rchild= CreateBiTree(&X[i+1],&Y[i+1],n-i-1);
Return T;
}

八、阅读并改进算法(每小题4分，共8分)

（1）. 阅读上面的算法程序，叙述算法的功能，并给出算法的时间与空间复杂度。
答案：输入一个数k，在有序序列中找2个数，使其和等于k
T(n)= O(n) S(n)= O(n)
（2） 改写算法，使改进算法的时间和空间效率尽可能提高。
参考答案：
#include<stdio.h>
#define MAXSIZE 13
main(){
int a[MAXSIZE]= ={1,4,5,6, 8,10,11,13,15,20 };
int k,i,j;
scanf("%d",&k);
i=0,j=MAXSIZE-1;
while(i<j){
if(a[i]+a[j]==k) break;
if(a[i]+a[j]>k j--;
else i++;
}
if(i<j)printf("%d=%d+%d\n",k,a[i],a[j]);
else printf("no solution!\n");
}

10
10