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

Four short words sum up what has lifted most successful individuals above the crowd: a little bit more.-author-date华中科技大学计算机学院数据结构(计算机专业)试题编译技术试题 数据结构试卷 (A卷)2010 2011 年度第二学期计算机学院班级_ 学号_ 姓名_考试时间：2011年 月 日 考试形式：闭卷题号一二三四五六七八总分核对人题分101010123210610100得分得分评卷人一、单项选择题(从下列各题四个备选答案中选出一个正确答案,将其代号(A,B,C,D)写在下表中,每小题1分,共10分)题号12345678910答案1对于栈的进栈和出栈运算，采用_存储结构时运算效率最高。A单链表 B容量足够大的顺序表C单向循环链表 D双向循环链表2链式队列和顺序队列比较，具有_这个优势。A进队操作方便 B出队操作方便C通常不会出现满队列情况 D求队列元素个数方便3下列关于串的叙述中，正确的是_。 A2个串的长度相等，则2个串相等 B空串至少包一个空格 C替换操作可以实现字符的删除 D一个串的长度至少是14二叉树在线索化后，下列问题中相对难解决的是_。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个结点可以组成_棵不同形态的二叉树。A10 B12 C14 D16 8对包含n个元素的散列表进行检索，平均查找长度为_。 AO(logn) BO(n) CO(nlogn) D不直接依赖于n9广义表 (a,(b),c),(),(d),(e),f),()的长度是_。A2 B3 C4 D510对某无向图进行一次深度优先搜索遍历，如果能访问到所有的顶点，则该无向图一定是_。A连通图 B树图 C有回路的连通图 D完全图得分评卷人二、填空题(在下表中填写正确的答案,每空1分,共10分) 题号12345678910答案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分) 题号12345678910答案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列矩阵A1.n，1.2n-1，现以行为主序进行压缩存储到一维数组SA1m中。（1）试问m值是什么？（2）假定非零元素Ai，j保存在SAk中，试写出由下标(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 10void main() int aN =1,4,5,6, 8,10,11,13,15,20 , bN,i,j,k; scanf（”%d”,&k）;for(i=0;i<N;i+)bN-i-1=k-ai;i=j=0;while(i<N && j<N)if (ai=bj)break;else if (ai<bj) i+; else j+;if (i>=N |j>=N)printf("No Solution!");else printf("%5d%5d",ai,k-bj);(1) 阅读上面的算法程序，叙述算法的功能，并给出算法的时间与空间复杂度。(2) 改写算法，使改进算法的时间和空间效率尽可能提高。 数据结构试卷参考答案 (A卷)2010 2011 年度第二学期计算机学院一、单项选择题(从下列各题四个备选答案中选出一个正确答案,将其代号(A,B,C,D)写在下表中,每小题1分,共10分)题号12345678910答案BCCDADCDCA二、填空题(在下表中填写正确的答案,每空1分,共10分) 题号12345678910答案n-1(n+e)5n2+n3链式34队列7n-1三、判断题(判断下列各题叙述的正确性,用表示正确，×表示错误，每小题1分,共10分) 题号12345678910答案××××× 四、存储结构图(要求标明各结点的数据域、指针域、权值等，每小题6分，共12分)2 如下图所示为二叉树排序树T的一种线索二叉树逻辑结构图，试画出插入结点48后的线索二叉树的物理存储结构图。答案：2 试画出如下图所示无向网的邻接多重表存储结构图。参考答案： 五、求解问题(每小题8分，共32分)2 如下图所示为n行2n-1列矩阵A1.n，1.2n-1，现以行为主序进行压缩存储到一维数组SA1m中。（1）试问m值是什么？（2）假定非零元素Ai，j保存在SAk中，试写出由下标(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/74已知图的邻接表法存储结构如下，从顶点A出发求图的深度遍历的结果。 答案： ABDECF 六、证明题(每小题5分，共10分)2， 证明在哈夫曼树种最小权值所对应的叶结点的层数正好是哈夫曼树的高度。略2证明有n个结点的完全二叉树的高度为élog2(n+1)ù。略七、编程题(6分)1 已知大小为N的数组AN、BN分别存放着有N个结点的某二叉树的先根和中根遍历序列，试编写函数CreateBiTree构造该二叉树。相关说明如下：参考答案：bitTree CreateBiTree(ElemType X，ElemType YN，int n)int i;if (!n) return NULL;T=(BitTree)malloc(sizeof(NODE);T->data=X0;for(i=0; Yi=X0 ;i+);T->lchild= CreateBiTree(&X1,Y,i);T->rchild= CreateBiTree(&Xi+1,&Yi+1,n-i-1);Return T;八、阅读并改进算法(每小题4分，共8分)（1）. 阅读上面的算法程序，叙述算法的功能，并给出算法的时间与空间复杂度。答案：输入一个数k，在有序序列中找2个数，使其和等于kT(n)= O(n) S(n)= O(n)（2） 改写算法，使改进算法的时间和空间效率尽可能提高。参考答案：#include<stdio.h>#define MAXSIZE 13main() int aMAXSIZE= =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(ai+aj=k) break; if(ai+aj>k j-; else i+; if(i<j)printf("%d=%d+%dn",k,ai,aj); else printf("no solution!n");-