南邮《数据结构》练习册期末复习题

《数据结构》综合练习南京邮电大学高等函授《数据结构》综合练习习题与解答南京邮电大学继续教育学院2021年2月《数据结构》综合练习注：此版本的综合练习册对应教材是《数据结构》，严蔚敏、吴伟民主编，清华大学出版社，2007年3月第一版，ISBN9787302147510一、选择题:1.若结点的存储地址与其关键字之间存在某种映射关系，则称这种存储结构为()A.顺序存储结构 B.链式存储结构C.索引存储结构 D.散列存储结构2.在长度为n的顺序表的第i(1≤i≤n+1)个位置上插入一个元素，元素的移动次数为()A.n-i+1B.n-iC.i D.i-13.对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为()A.顺序表 B.用头指针表示的单循环链表C.用尾指针表示的单循环链表 D.单链表4.若进栈序列为a,b,c，则通过入出栈操作可能得到的a,b,c的不同排列个数为()A.4 B.5 C.6 D.75.为查找某一特定单词在文本中出现的位置，可应用的串运算是()A.插入 B.删除C.串联接D.子串定位6.已知函数Sub(s,i,j)的功能是返回串s中从第i个字符起长度为j的子串，函数Scopy(s,t)的功能为复制串t到s。若字符串S=“SCIENCESTUDY”，则调用函数Scopy(P,Sub(S,1,7))后得到()A.P=″SCIENCE″ B.P=″STUDY″C.S=″SCIENCE″ D.S=″STUDY″7.无论采用何种遍历方式，访问序列均相同的非空二叉树的结点个数是()A.0 B.1C.28.下列函数中对应的时间复杂度（n为问题规模）最小的是（）A.T1(n)=nlog2n+5000n B.T2(n)=n2-800nC.T3(n)=100000000log2n D.T4(n)=50n+98019.下列陈述中正确的是()A.二叉树是度为2的有序树B.二叉树中结点只有一个孩子时无左右之分C.二叉树中必有度为2的结点D.二叉树中最多只有两棵子树，并且有左右之分10.n个顶点的有向完全图中含有向边的数目最多为()A.n-1B.nC.n(n-1)/2D.n(n-1)11.计算机识别、存储和加工处理的对象被统称为()A.数据B.数据元素C.数据结构D.数据类型12.在具有n个结点的有序单链表中插入一个新结点并使链表仍然有序的时间复杂度是()A.O(1) B.O(n)C.O(nlogn)D.O(n2)13.队和栈的主要区别是()A.逻辑结构不同 B.存储结构不同C.所包含的运算个数不同 D.限定插入和删除的位置不同14.链栈与顺序栈相比，比较明显的优点是()A.插入操作更加方便B.删除操作更加方便C.不会出现下溢的情况D.不会出现上溢的情况15.采用两类不同存储结构的字符串可分别简称为()A.主串和子串B.顺序串和链串C.目标串和模式串D.变量串和常量串16.在目标串T［0..n-1］=“xwxxyxy”中，对模式串P［0..m-1］=″xy″进行子串定位操作的结果是()A.0B.2C.417.以下排序方法中,平均时间复杂度为O(n2)的是（）A.归并排序 B.直接选择排序 C.堆排序 D.快速排序18.对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是（）A.n-1 B.n C.(n-1)2 D.n219.二叉树中第5层上的结点个数最多为()A.8B.1520.若线性表最常用的操作是存取第i个元素及其前趋和后继元素的值，为节省时间应采用的存储方式是()A.顺序表 B.单链表C.双向链表 D.单循环链表21.如果某图的邻接矩阵是对角线上元素均为零的上三角矩阵，则此图是()A.有向完全图 B.连通图C.无向图 D.有向无环图22.对n个关键字的序列进行快速排序，平均情况下的时间复杂度为()A.O(1)B.O(logn) C.O(n)D.O(nlog2n)23.对表长为n的顺序表进行顺序查找，在查找概率相等的情况下，查找成功的平均查找长度为()A. B.C.D.n24.以下排序方法中,最好情况下时间复杂度为O(n)的是（）A.直接插入排序 B.直接选择排序 C.堆排序 D.快速排序25.稠密索引是在索引表中()A.为每个记录建立一个索引项 B.为每个页块建立一个索引项C.为每组记录建立一个索引项 D.为每个字段建立一个索引项26.设有两个串p和q，求串q在串p中首次出现的位置的运算称为（）A.连接 B.求子串C.模式匹配D.求串长27.栈S和队列Q的初始状态为空，元素1、2、3、4、5、6依次通过栈，一个元素出栈后即入队，若六个元素出队顺序为2、4、3、6、5、1，则栈的容量至少是（） A.2 B.3 C.4 D.28.二叉树结点的先序序列、中序序列、后序序列中，所有叶子结点的先后顺序（） A.完全相同 B.都不相同 C.先序和中序相同，而与后序不同 D.中序和后序相同，与先序不同29.下面关于线性表的叙述中，错误的是（） A.线性表采用顺序存储，必须占用一片连续的存储单元 B.线性表采用链接存储，不必占用一片连续的存储单元 C.线性表采用顺序存储，便于进行插入和删除操作 D.线性表采用链接存储，便于进行插入和删除操作30.一个向量第一个元素的存储地址是100，每个元素的长度是2，则第五个元素地址是（） A.110 B.108 C.100 D.31.在数据结构中，数据的基本单位是()A.数据项 B.数据类型C.数据元素 D.数据变量32.在最好和最坏情况下的时间复杂度均为O(nlogn)且稳定的排序方法是()A.快速排序B.堆排序C.归并排序D.插入排序33.数组的基本运算是（ ）A.插入数组元素 B.删除数组元素C.只可以读 D.读和写34.AVL树是一种平衡的二叉排序树，树中任一结点的()A.左、右子树的高度均相同B.左、右子树高度差的绝对值不超过1C.左子树的高度均大于右子树的高度D.左子树的高度均小于右子树的高度35.在VSAM文件的控制区间中，记录的存储方式为()A.无序顺序 B.有序顺序C.无序链接 D.有序链接36.串是一种特殊的线性表，其特殊性体现在（）A.可以连续存储 B.数据元素是字符C.可以链接存储 D.数据元素可以是任意类型37.对下列四个序列用快速排序的方法进行排序，以序列的第一个元素为基础进行划分。在第一趟划分过程中，元素移动次数最多的序列是（）A.70,75,82,90,23,16,10,68B.70,75,68,23,10,16,90,82C.82,75,70,16,10,90,68,23D.23,10,16,70,82,75,68,9038.若关键码序列（K1,K2,…,Kn）是一个堆，序列中元素的关系是（）A.Ki≤K2i或Ki≥K2i（i=1,2,…[n/2]）Ki≤K2i+1Ki≥K2i+1B.K1≤K2≤…≤KnC.K1≥K2≥…≥KnD.元素之间的值没有任何限制39.对关键码Κ=｛53,30,37,12,45,24,96｝，从空二叉树开始逐个插入每个关键码，建立与集合Κ对应的二叉排序树（又称二叉查找树）BST，若希望得到的BST高度最小，应选择下列输入序列（）A.45,24,53,12,37,96,30 B.37,24,12,30,53,45,96C.12,24,30,37,45,53,96 D.30,24,12,37,45,96,5340.邻接矩阵是对称矩阵的图为（）A.有向图 B.带权有向图C.带权连通图 D.无向图41.计算机识别、存储和加工处理的对象被统称为()A.数据B.数据元素C.数据结构D.数据类型42.在具有n个结点的有序单链表中插入一个新结点并使链表仍然有序的时间复杂度是()A.O(1) B.O(n)C.O(nlogn)D.O(n2)43.队和栈的主要区别是()A.逻辑结构不同 B.存储结构不同C.所包含的运算个数不同 D.限定插入和删除的位置不同44.链栈与顺序栈相比，比较明显的优点是()A.插入操作更加方便B.删除操作更加方便C.不会出现下溢的情况D.不会出现上溢的情况45.采用两类不同存储结构的字符串可分别简称为()A.主串和子串B.顺序串和链串C.目标串和模式串D.变量串和常量串46.在目标串T［0..n-1］=“xwxxyxy”中，对模式串P［0..m-1］=″xy″进行子串定位操作的结果是()A.0B.2C.447.以下排序方法中,平均时间复杂度为O(n2)的是（）A.归并排序 B.直接选择排序 C.堆排序 D.快速排序48.对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是（）A.n-1 B.n C.(n-1)2 D.n249.二叉树中第5层上的结点个数最多为()A.8B.15C50.若线性表最常用的操作是存取第i个元素及其前趋和后继元素的值，为节省时间应采用的存储方式是()A.顺序表 B.单链表C.双向链表 D.单循环链表51.如果某图的邻接矩阵是对角线上元素均为零的上三角矩阵，则此图是()A.有向完全图 B.连通图C.无向图 D.有向无环图52.对n个关键字的序列进行快速排序，平均情况下的时间复杂度为()A.O(1)B.O(logn) C.O(n)D.O(nlog2n)53.对表长为n的顺序表进行顺序查找，在查找概率相等的情况下，查找成功的平均查找长度为()A. B.C.D.n54.以下排序方法中,最好情况下时间复杂度为O(n)的是（）A.直接插入排序 B.直接选择排序 C.堆排序 D.快速排序55.稠密索引是在索引表中()A.为每个记录建立一个索引项 B.为每个页块建立一个索引项C.为每组记录建立一个索引项 D.为每个字段建立一个索引项56.设有两个串p和q，求串q在串p中首次出现的位置的运算称为（）A.连接 B.求子串C.模式匹配D.求串长57.栈S和队列Q的初始状态为空，元素1、2、3、4、5、6依次通过栈，一个元素出栈后即入队，若六个元素出队顺序为2、4、3、6、5、1，则栈的容量至少是（） A.2 B.3 C.4 D.58.二叉树结点的先序序列、中序序列、后序序列中，所有叶子结点的先后顺序（） A.完全相同 B.都不相同 C.先序和中序相同，而与后序不同 D.中序和后序相同，与先序不同59.下面关于线性表的叙述中，错误的是（） A.线性表采用顺序存储，必须占用一片连续的存储单元 B.线性表采用链接存储，不必占用一片连续的存储单元 C.线性表采用顺序存储，便于进行插入和删除操作 D.线性表采用链接存储，便于进行插入和删除操作60.一个向量第一个元素的存储地址是100，每个元素的长度是2，则第五个元素地址是（） A.110 B.108 C.100 D.二、判断题:1.存在这样的二叉树，对它采用任何次序的遍历，其结果相同。 （ ）2.完全二叉树中，若一个结点没有左孩子，则它必是树叶。 （ ）3.若连通网络上各边的权值均不相同，则其最小生成树是唯一的。（）4.队列和栈都是运算受限的线性表。 （ ）5.算法DFS应用于一个连通图时，所经过的边形成一棵树。 （ ）6.当有序表中个记录的查找概率相当时，其静态最优二叉排序树就是折半查找判定树。7.稀疏图用邻接表存储表示比较好，稠密图用邻接矩阵表示比较好。（）8.在有向图中，各顶点的入度之和等于各顶点的出度之和。（）9.无论是有向图还是无向图，其邻接矩阵表示都是唯一的。（）10.连通图的生成树包含了图中所有顶点。（）11.无环有向图才能进行拓扑排序。（）12.连通图的广度优先遍历中一般要用队列来暂存刚访问过的顶点。（）13.图的深度优先遍历中一般用栈来暂存刚访问过的顶点。 （）14.度为m的树中至少有一个度为m的结点。 （）15.在先序遍历二叉树的序列中，对于任何结点，其子树的所有结点都是直接跟在该结点之后。 （）16.哈夫曼树中不存在度为1的结点。 （）17.当二叉树中结点树多于1个时，不可能根据结点的先序遍历序列和后序遍历序列唯一的确定该二叉树的逻辑结构。 （）18.存在这样的二叉树，对它采用任何次序的遍历，结构相同。 （）19.对n个元素执行直接选择排序，关键字的比较次数总是n(n-1)/2次。（）20.只有在线性表的初始状态为反序的情况下，直接插入排序过程中，元素的移动次数才会达到最大值。 （）21.只有在线性表的初始状态为反序的情况下，冒泡排序过程中，元素的移动次数才会达到最大值（）22.对n个元素执行快速排序，在进行第一次划分时，关键字的比较次数总是n-1次。（）23.分块查找的效率与线性表被分成多少块有关。 （）24.在二叉排序树中，新结点总是作为叶子来插入的。（）25.顺序查找方法只能在顺序存储结构上进行。（） 26.二分查找可以在有序的双向链表上进行。 （）27.二叉排序树是用来进行排序的。 （）28.数据元素是数据的最小单位。（）29.数据的逻辑结构是指数据的各数据项之间的逻辑关系。 （）30.顺序存储方式只能用于存储线性结构。（）31.将一颗树转换成二叉树后，根结点没有左子树。（）32.快速排序在任何情况下均可得到最快的排序效果。（）三、名词解释：索引存储：双向循环链表：满二叉树：最小生成树：交换排序：串相等：队列：完全二叉树：深度优先搜索：AVL树：栈：邻接表：二分查找法：二叉排序树：冒泡排序：平均时间复杂度：顺序表：三叉链表：倒排文件：直接选择排序：最坏情况时间复杂度：静态双亲链表：哈夫曼树：散列查找：ISAM文件：存储密度：顺序队假溢出：结点的度：二次探测法：B+树：判定树：树的深度：公共溢出区法：索引顺序文件：多重表文件：单链表：稀疏矩阵：静态查找表：索引顺序表：先根遍历：四、算法阅读题：1.阅读下面的链栈的退栈操作，栈顶元素通过参数返回，它的直接后继成为新的栈顶，请在空缺处填入合适的内容，使其成为一个完整的算法。intPop(LStackTp*ls,DataType*x){LStackTp*p;if(ls!=NULL){p=ls;（1）_______________（2）_______________free(p);/*释放原栈顶结点空间*/return（1）;}elsereturn（0）;}（1）_______________（2）_______________2.阅读下面算法，回答问题：voidfun1(intn,listr){for(i=1;i=n-1;i++){flag=1;for(j=1;j=n－i;j++)if(r[j+1].key<r[j].key){flag=0;p=r[j];r[j]=r[j+1];r[j+1]=p;}if(flag)return;}｝说明算法fun1（）的功能。该算法的时间复杂度。3阅读下面算法，回答问题：Intvisited[vnum];Count_Component(GraphTpg){intcount;for(v=0;v<g.vexnum;v++)/*初始化visited数组*/visited[v]=0;count=0;for(v=0;v<g.vexnum;v++)if(!visited=[v]){count++;printf("连通分量%d包含以下顶点：",count);Dfs(g,v);Printf("\n");}}如果用上面算法遍历如下图，看到输出结果为：4.阅读下面算法，回答问题：voidfun1(SeqStack*S){inti;arr[100];n=0;while(StackEmpty(S))arr[n++]=Pop(S);for(i=0,i<n;i++)Push(S,arr[i]);}（1）简述fun1（）的功能（2）如果S的入栈顺序为{A,B,C,D}，请画出最终S栈内存储情况。5.阅读下面的链队的出队列算法，出队元素由参数返回，请在空缺处填入合适的内容，使其成为一个完整的算法。OutQueue(QueptrTp*lq,DataType*x){LqueueTp*s;if(lq->front==lq->rear){error("队空");return（0）;}else{（1）______________（2）______________（3）______________if(s->next==NULL)lq->rear=lq->front;free(s);return（1）;}}（1）______________（2）______________（3）______________6.已知下面算法，回答以下问题intcount=0;voidfun1(bitreptrt){if(t!=NULL){if((t->lchild==NULL)&&(t->rchild==NULL))count++;fun1(t->lchild,count);fun1(t->rchild,count);}}简述fun1（）的功能如果程序遍历的二叉树如下，写出最终count的结果7.阅读下列算法并回答问题：voidfun3(listr);{for(i=2;i=n;i++){r[0]=r[i];j=i-1;while(r[0].key<r[j].key){r[j+1]=r[j];j――;}r[j+1]=r[0];}}简述fun3（）的功能在程序中r[0]的功能8.阅读下面算法，回答以下问题intfun1(StackS){intn=0;while(!StackEmpty(S)){n++;Pop(S);}return(n）;}如果现在{7,2,3,23,56,9}6个元素依次入栈，算法返回值是多少？简述fun1（）的功能。9.阅读下面的二分法查找的算法，请在空缺处填入合适的内容，使其成为一个完整的算法。intbinsearch(sqtableR,keytypeK){low=1;hig=R.n;while(low<=hig){（1）______________switch{caseK==R.item[mid].key:return(mid);caseK<R.item[mid].key:（2）______________；break;caseK>R.item[mid].key:（3）______________；break;}}return(0);}（1）______________（2）______________（3）______________10.有向图的邻接表类型定义如下，阅读下面算法，要求回答下面问题：#definevnum5typedefstructarcnode{intadjvex;structarcnode*nexttarc;}ArcNodeTp;typedefstructvexnode{intvertex;ArcNodeTp*firstarc;}AdjList[vnum];typedefstructgraph{AdjListadjlist;intvexnum,arcnum;}Graphtp;voidIndegree(AdjListg){for(i=0;i<n;j++){num=0;for(j=0;j<n;j++)if(i!=j){p=g[j].firstarc;while(p){if(p->adjvex==i)num++;p=p->next;}}printf(“顶点%d：%d\n”,g[i].vexdata,num);}}已知有向图如下，该算法的输出结果为：该算法的功能。11.阅读下面的单链表第i位置上插入一个以x为值的新结点的算法，请在空缺处填入合适的内容，使其成为一个完整的算法。voidins_lklist(lklisthead,inti){p=find_lklist(head,i-1);if(p==NULL)error('不存在第i个位置');else{s=malloc(size);s->data=x;（1）_______________。（2）_______________。}（1）_______________。（2）_______________。12.下面是在顺序栈上实现的一个栈基本操作，该操作的功能是_________。typedefstruct{DataTypedata[100]；inttop；}SeqStack；DataTypefun1(SeqStack*S){if(StackEmpty(S))Error(”Stackisempty”)；return（S->data[S->top]）；}13.阅读下面算法，回答问题。intfun2(MGraph*G,inti){intd=0,j;for(j=0;j<n;j++){if(G->edges[i][j])d++;if(G->edges[j][i])d++;}return

(d);}(1)简述函数fun2（）的功能;(2)写出函数fun2（）的时间复杂度。14.阅读下面算法，回答问题：LinkListfun1(LinkListL)/*L是无头结点单链表*/

{ListNode*Q,*P;

if(L&&L->next){

Q=L;L=L->next;P=L;

while(P->next)P=P->next;

P->next=Q;Q->next=NULL;

}

returnL;

}简述fun1（）的功能如果L的初始状况如下，请画出最终L的状态15.阅读下面算法，算法功能为往无向图的邻接矩阵中插入顶点，解释（1）（2）两句语句功能voidAddVertexMGraph(MGraph*G,VertexTypex){if(G->n>=MaxVertexNum)Error("顶点数太多")；G->vexs[G->n]=x;（1）G->n++；（2）}（1）______________（2）______________16.阅读下面程序，回答问题：for(i=1;i<＝n;i++) for(j=1;j<＝i;j++) t=t+1;该程序段的时间复杂性量度是多少？（要求写出运算步骤）17.阅读下面算法借助栈将一个带头结点的单链表倒置，请在空缺处填入合适的内容，使其成为一个完整的算法。voidreverse_list(LkListTp*head){LStackTpls,p;datatypex;InitStack(&ls);/*初始化链栈*/p=(*head)->next;while(p!=NULL){Push(&ls,p->data);p=p->next;}（1）_____________while(!EmptyStack(ls)){Pop(&ls,&x);（2）_____________（3）_____________}（1）_____________（2）_____________（3）_____________18.阅读下面算法，算法功能为向无向图的邻接表中插入一个顶点，解释（1）（2）（3）的语句功能voidAddVertexALGraPh(ALGrahp*G,VertexTypex){if(G->n>=MaxVertexNum)Error("顶点数太多")；G->adjlist[G->n].vertex=x;（1）G->adjlist[G->n].firstedge=NULL;（2）G->n++；（3）}（1）_____________（2）_____________（3）_____________19.for(i=1；i<=n；i++){s=i+2;

for(j=1；j<=n；j++)

s=2*j；}该程序段的时间复杂度为多少？（写出运算步骤）20.阅读下面算法，要求回答下面问题：typedefstrutcycqueue{DataTypedata[maxsize];intrear,front;}CycqueueTp;CycqueueTpsq;intfun2(CycqueueTp*sq,DataTypex){if((sq->rear+1)%maxsize==sq->front){error("队满");return0;}else{sq->rear=(sq->rear+1)%maxsize;sq->data[sq->rear]=x;return1;}}intfun3(CycqueueTp*sq,DataType*x){if((sq->front==sq->rear){error("队空");return0;}else{sq->front=(sq->front+1)%maxsize;*x=sq->data[sq->front];return1;}}intfun4(cycqueueTpsq,DataType*x){if(sq.rear==sq.front)return0;else{*x=sq.data[(sq.front+1)%maxsize];return1;}}（1）算法fun2（）的功能。（2）算法fun3（）的功能。（3）算法fun4（）的功能。21.阅读下面广度优先搜索算法，请在空缺处填入合适的内容，使其成为一个完整的算法。Bfs(GraphTpg,intv){QueptrTpQ;ArcNodeTp*p;InitQueue(&Q);Printf("%d",v);Visited[v]=1;EnQueue(&Q,v);While(!EmptyQueue(Q)){（1）_____________p=g.adjlist[v].firstarc;while(p!=NULL){if(!visited[p->adjvex]){printf("%d",p->adjvex);（2）_____________EnQueue(&Q,p->adjvex);}p=p->nextarc;}}}（1）_____________（2）_____________22.已知下列程序是完成链队lq中将数据元素x的入队列运算，请在空缺处填入合适的内容，使其成为一个完整的算法。链队类型定义如下typedefstructlinked_queue{DataTypedata;structlinked_queue*next;}LqueueTp;typedefstructqueuetr{LqueueTp*front,*rear;}QueptrTp;QueptrTplq;voidenqueue(QueptrTp*lq;DataTypex){LqueueTp*p;p=(LqueueTp*)malloc(sizeof(LqueueTp));p->data=x;p->next=NULL;（1）____________（2）____________}（1）____________（2）____________23.阅读下面算法，回答问题：Intvisited[vnum];Count_Component(GraphTpg){intcount;for(v=0;v<g.vexnum;v++)/*初始化visited数组*/visited[v]=0;count=0;for(v=0;v<g.vexnum;v++)if(!visited=[v]){count++;printf("连通分量%d包含以下顶点：",count);Dfs(g,v);Printf("\n");}}如果用上面算法遍历如下图，看到输出结果为：24.已知下面算法，回答以下问题intcount=0;voidfun1(bitreptrt){if(t!=NULL){if((t->lchild==NULL)&&(t->rchild==NULL))count++;fun1(t->lchild,count);fun1(t->rchild,count);}}简述fun1（）的功能如果程序遍历的二叉树如下，写出count的值五、简答题：1.在单链表和双向链表中，能否从当前结点出发访问到任一结点？为什么？2．若较频繁地对一个线性表进行插入和删除操作，改线性表宜采用何种存储结构？为什么？ 3.对关键字序列（72，87，61，23，94，16，05，58）进行堆排序，使之按关键字递减次序排列。请写出排序过程中得到的初始堆和前三趟的序列状态。4.在关键字序列（07，12，15，18，27，32，41，92）中用二分查找和给定值92相等的关键字，请写出查找过程中依次和给定值92比较的关键字。 5.若线性表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取线性表在的元素，那么应采用哪种存储结构？为什么？ 6．说明什么是顺序队的“假溢出”，并给出解决方法。7.如何判定循环队列的空和满？并给出循环队列中元素个数的计算式（设队长最大值为N，队头指针front,队尾指针rear）。 8.请画出具有三个结点的二叉树所有可能的不同形态？9.简述无向图和有向图有哪两种主要的存储结构，并说明各种结构在图中的不同操作（如图的遍历，有向图的拓扑排序等）中有什么样的优越性？ 10.试述顺序查找法、二分查找法和分块查找法对被查找的表中元素的要求。11.当实现插入排序过程中，可以用二分查找来确定第i个元素在前i-1个元素中的可能插入位置（二分插入排序），这样做能否改善插入排序的时间复杂度？为什么？12.指出堆和二叉排序树的区别。13.如果一棵哈夫曼树T有n0个叶子结点，那么，树T有多少个结点？要求给出求解过程。14.以关键字序列{265，301，751，129，937，863，742，694，76，438}为例，给出归并排序算法的各趟排序结束时，关键字序列的状态。15.设T是非空的二叉树，则满足以下特点的T分别应是什么形态？16.常用的散列函数构造法有哪些？17.什么是文件的存储结构，常见的有哪几种结构？ 18.简述散列文件的特点。 19.已知关键字序列（49，38，65，97，76，13，27，49），写出按升序进行快速排序的各趟划分及最终的排序结果。 20.已知关键字序列（70，73，69，23，93，18，11，68），写出按升序进行快速排序的各趟划分及最终的排序结果。 21.什么是内排序？按排序过程中依据的不同原则对内部排序方法进行分类有哪些方法? 22.已知一棵二叉树的后序遍历序列是DABEC，中序遍历序列是DEBAC，则（1）写出先序遍历系列（2）已知结点的前序序列和后序序列，能否唯一确定其中序遍历序列。23.已知结点的前序遍历序列是ABCDEFG，中序遍历序列是CBEDAFG，画出整棵二叉树（2）已知结点的中序序列和后序序列，能否唯一确定一棵二叉树。24.已知有向图G=（V，E），其中V={V1，V2，V3，V4，}，E={<V2，V1>,<V3,V2>,<V4,V3>,<V4,V2>,<V1,V4>}，试画出G的邻接矩阵和邻接表，并写出深度优先遍历序列、广度优先遍历序列（以V1为出发点）。25.一份电文中共使用5个字符：A,B,C,D,E他们的出现频率为4、7、5、2、9，试画出对应的哈夫曼树（按左子树根结点的权小于等于右子树根结点的权的次序构造）。26.一份电文中共使用5个字符：H,M,N,K,P他们的出现频率为4、7、5、2、9，求出每个字符的哈夫曼编码。(构造对应的哈夫曼树时按左子树根结点的权小于等于右子树根结点的权的次序构造）。28.现有按中序遍历二叉树的结果为ABC，问有几种不同形态的二叉树看可得到这一遍历结果？

《数据结构》综合练习参考答案：一、选择题:1.D2.A3.C4.B5.D6.A7.B8.C9.D10.D11.A12.B13.D14.D15.B16.C17.B18.D19.C20.A21.D22.D23.C24.A25.A26.C27.B28.A29.C30.B31.C32.C33.D34.B35.B36.B37.A38.A39.B40.D41.A42.B43.D44.D45.B46.C47.B48.D49.C50.A51.D52.D53.C54.A55.A56.C57.B58.A59.C60.B二、判断题:1.存在这样的二叉树，对它采用任何次序的遍历，其结果相同。 （√）√2.完全二叉树中，若一个结点没有左孩子，则它必是树叶。 （ ）√3.若连通网络上各边的权值均不相同，则其最小生成树是唯一的。（）√4.队列和栈都是运算受限的线性表。 （ ）√5.算法DFS应用于一个连通图时，所经过的边形成一棵树。 （ ）√6.当有序表中个记录的查找概率相当时，其静态最优二叉排序树就是折半查找判定树。7.稀疏图用邻接表存储表示比较好，稠密图用邻接矩阵表示比较好。（）√8.在有向图中，各顶点的入度之和等于各顶点的出度之和。（）√9.无论是有向图还是无向图，其邻接矩阵表示都是唯一的。（）√10.连通图的生成树包含了图中所有顶点。（）√11.无环有向图才能进行拓扑排序。（）√12.连通图的广度优先遍历中一般要用队列来暂存刚访问过的顶点。（）√13.图的深度优先遍历中一般用栈来暂存刚访问过的顶点。 （）√14.度为m的树中至少有一个度为m的结点。 （）√15.在先序遍历二叉树的序列中，对于任何结点，其子树的所有结点都是直接跟在该结点之后。 （）√16.哈夫曼树中不存在度为1的结点。 （）√17.当二叉树中结点树多于1个时，不可能根据结点的先序遍历序列和后序遍历序列唯一的确定该二叉树的逻辑结构。 （）√18.存在这样的二叉树，对它采用任何次序的遍历，结构相同。 （）√19.对n个元素执行直接选择排序，关键字的比较次数总是n(n-1)/2次。（）√20.只有在线性表的初始状态为反序的情况下，直接插入排序过程中，元素的移动次数才会达到最大值。 （）√21.只有在线性表的初始状态为反序的情况下，冒泡排序过程中，元素的移动次数才会达到最大值。 （）√22.对n个元素执行快速排序，在进行第一次划分时，关键字的比较次数总是n-1次。（√）23.分块查找的效率与线性表被分成多少块有关。 （）√24.在二叉排序树中，新结点总是作为叶子来插入的。（）√25.顺序查找方法只能在顺序存储结构上进行。 （X）。正确：顺序查找方法也可以在链式存储结构上进行。26.二分查找可以在有序的双向链表上进行。 （X）。正确：二分查找只能在可以进行随机查找存储结构上进行，即只能在顺序存储的有序表上进行。27.二叉排序树是用来进行排序的。 （X）。正确：二叉排序树主要用于改进一般二叉树的查找效率。28.数据元素是数据的最小单位。 （X）。正确：数据项是数据的最小单位。29.数据的逻辑结构是指数据的各数据项之间的逻辑关系。 （X）。正确：数据的逻辑结构是指数据的各数据元素之间的逻辑关系。30.顺序存储方式只能用于存储线性结构。（X）。正确：顺序存储方式也可以用于存储树性结构，如完全二叉树可用一维数组存储。31.将一颗树转换成二叉树后，根结点没有左子树。 （X）。正确：通常有左子树而无右子树。32.快速排序在任何情况下均可得到最快的排序效果。（X）。正确：快速排序在待排序记录关键字为随机分布是效果最好，基本有序是效果最差。三、名词解释：索引存储：每个存储结点只含有一个数据元素，所有存储结点连续存放，此外增设一个索引表，索引表中的索引指示各存储结点的存储位置或存储位置区间端点。双向循环链表：双链表两个链域prior和next分别指向本结点数据域data所含数据元素的直接前驱和直接后继所在的结点。所有结点通过前驱指针和后继指针链接在一起，再加上起标识作用的头指针，就形成的了双向循环链表。满二叉树：深度为k的且有2k－1个结点的二叉树。最小生成树：n个顶点的无向完全图，共有n（n－1）/2条边，构造一个权最小的n－1条边并使这个图仍然连通的树。交换排序：根据序列中的两个记录键值的比较结果来对换这两个记录在序列中的位置。特点是：将键值较大的记录向尾部移动，键值较小的记录向序列的前部移动。串相等：两个串相等当且仅当两个串的长度相等并且各个对应位置上的字符都相同。队列：在这种线性表上，插入限定在表的一段进行，删除限定在表的另一端进行。完全二叉树：在一棵深度为k的满二叉树上删除第k层上最右边的连续j（0≤j≤2k－1）个结点。深度优先搜索：首先访问出发点，然后任选一个vi的未访问国的邻接点vj，以vj为新的出发点继续进行深度优先搜索，直至所有顶点都被访问过。AVL树：平衡二叉排序树，或者是空树，或者是一个任一结点的左子树和右子树的高度至多差1的二叉排序树。栈：一种特殊的线性表,进行插入和删除的运算都只限定在表的一端进行。允许插入和删除的这一端称为栈顶，另一端称为栈底。邻接表：图的一种链式存储结构，在邻接表中，对图中每个顶点建立一个单链表，n个顶点就要建n个链表，无向图中，单链表中的结点表示依赖于顶点vi的边，对于有向图，是以顶点vi为尾的弧。二分查找法：每次将处于查找区间中间位置上的数据元素的键值和给定值K比较，若不等则缩小查找区间并在新的区间内重复，知道查找成功或查找区间长度为0为止。二叉排序树：或者是一棵空树，或者是一棵满足下列条件的二叉树：若它的左子树不空，则左子树上所有结点的键值均小于它的根结点的键值。若它的右子树不空，则右子树上所有结点的键值均大于它的根结点的键值。它的左右子树也分别是二叉排序树。冒泡排序：先将第一和第二个键值比较交换，然后比较第二和第三个键值交换，以此类推，直到第n个和n－1个记录比较交换，这称为一趟起泡。每趟将键值最大的记录换到最后。重复以上过程，每次移动都向最终目标前进，直至没有记录需要交换为止。平均时间复杂度：在算法所有输入下的计算量的加权平均值作为算法的计算量。顺序表：顺序表的一个存储结点存储线性表的一个结点的内容，即数据元素，所有存储结点按照相应数据元素间的逻辑关系决定的次序依次排列。三叉链表：每个数据元素含有一个data域和三个指针域，三个指针域分别指向双亲，左孩子和有孩子的链式存储结构。倒排文件：和多重表文件的关键字索引的结构不同，称倒排文件中的次关键字索引为倒排表，倒排表中次关键字的一项存放记录的物理记录号，同一关键字的记录号有序排列。直接选择排序：首先在所有记录中选出键值最小的记录，把它与第一个记录交换，然后在其余的记录中再选出键值最小的记录与第二个记录交换，直至所有记录排序完成。最坏情况时间复杂度：以算法再所有输入下的计算量的最大值作为算法的计算量。静态双亲链表：由一个一维数组组成，数组的每个分量包含两个域：数据域和双亲域。数据域用于存储数据元素，双亲域用于存放本结点的双亲结点再数组中的序号。哈夫曼树：给定一组值：p1,…pk,构造一棵有k个叶子且非别以这些值为权的判定树,使得其平均比较次数最小散列查找：对于给定的动态查找表T,如果选定了某个理想的散列函数H及相应的散列表L,则对于T中的每个数据元素X,函数值H(X.Key)就是X在散列表中的存储位置.ISAM文件：ISAM文件由多级主索引，柱面索引，磁道索引和主文件组成。文件的记录在同一盘上存放时，应尽量先放在一个柱面上，然后再顺序存放在相邻的柱面上，对于同一柱面，则应按盘面的次序顺序存放。存储密度：存储结点中数据域占用的存储量与整个存储结点占用存储量之比。顺序队假溢出：在顺序队的存储过程中，发现在数组高端不能入队，但是数组的低端仍有空闲位置，即顺序队的存储空间没有被占满。结点的度：结点拥有的子树的树木。二次探测法：生成的后继散列地址不是连续的，而是跳跃式的，以便为后续数据元素留下空间而减少堆积。B+树：m阶B+树满足以下条件每个结点至多有m个孩子。根结点至少有2个孩子，其余每个结点至少有[m/2]个孩子。所有叶子都在同一层上有k个孩子的结点必有k个关键字。判定树：用于描述分类过程的二叉树称为判定树，判定树的每个非终端结点包含一个条件，因而对应于一次比较或判断，每个终端结点包含一个种类标记，对应于一种分类结果。树的深度：一棵树中所有结点层数的最大值。公共溢出区法：在构造后继散列地址序列的过程中，散列表由两个一维数组组成，一个是基本表，就是闭散列表，另一个称为溢出表，插入首先在基本表上进行，假如发生冲突，则将同义词存入溢出表。索引顺序文件：由索引表和主文件组成，索引表指一张指示逻辑记录和物理记录之间对应关系的表。索引项按照关键字值顺序排列，文件本身也是按照关键字顺序排列。多重表文件：记录按主关键字的顺序构成一个串联文件，并建立主关键字的索引，对每个次关键字建立此关键字索引，所有具有同一次关键字的记录构成一个链表。单链表：单链表的一个存储结点包含两个部分：data域称为数据域，next称为指针域，存放一个指针，指向本结点所含数据元素的直接后继所在的结点。稀疏矩阵：矩阵中零元素远远多于非零元素，并且非零元素的分布没有规律的矩阵。静态查找表：以集合为逻辑结构，包含建表，查找，读表元三种基本运算的数据结构。索引顺序表：索引顺序表由两部分组成：一个顺序表和一个索引表，顺序表组织形式和普通的顺序表相同，而索引表本身在组织形式上也是一个顺序表。先根遍历：若需遍历的二叉树为空，执行空操作，否则，依次执行以下操作：访问根结点先根遍历左子树先根遍历右子树四、算法阅读题：1.阅读下面的链栈的退栈操作，栈顶元素通过参数返回，它的直接后继成为新的栈顶，请在空缺处填入合适的内容，使其成为一个完整的算法。intPop(LStackTp*ls,DataType*x){LStackTp*p;if(ls!=NULL){p=ls;（1）_______________（2）_______________free(p);/*释放原栈顶结点空间*/return（1）;}elsereturn（0）;}（1）_______________（2）_______________（1）*x=p->data;（2）ls=ls->next;2.阅读下面算法，回答问题：voidfun1(intn,listr){for(i=1;i=n-1;i++){flag=1;for(j=1;j=n－i;j++)if(r[j+1].key<r[j].key){flag=0;p=r[j];r[j]=r[j+1];r[j+1]=p;}if(flag)return;}｝说明算法fun1（）的功能。该算法的时间复杂度。（1）冒泡排序（2）O（n2）3阅读下面算法，回答问题：Intvisited[vnum];Count_Component(GraphTpg){intcount;for(v=0;v<g.vexnum;v++)/*初始化visited数组*/visited[v]=0;count=0;for(v=0;v<g.vexnum;v++)if(!visited=[v]){count++;printf("连通分量%d包含以下顶点：",count);Dfs(g,v);Printf("\n");}}如果用上面算法遍历如下图，看到输出结果为：连通分量1包含以下顶点：12354连通分量2包含以下顶点：6784.阅读下面算法，回答问题：voidfun1(SeqStack*S){inti;arr[100];n=0;while(StackEmpty(S))arr[n++]=Pop(S);for(i=0,i<n;i++)Push(S,arr[i]);}（1）简述fun1（）的功能（2）如果S的入栈顺序为{A,B,C,D}，请画出最终S栈内存储情况。（1）程序段的功能是将一栈中的元素按反序重新排列，也就是原来在栈顶的元素放到栈底，栈底的元素放到栈顶。此栈中元素个数限制在100个以内。（2）5.阅读下面的链队的出队列算法，出队元素由参数返回，请在空缺处填入合适的内容，使其成为一个完整的算法。OutQueue(QueptrTp*lq,DataType*x){LqueueTp*s;if(lq->front==lq->rear){error("队空");return（0）;}else{（1）______________（2）______________（3）______________if(s->next==NULL)lq->rear=lq->front;free(s);return（1）;}}（1）______________（2）______________（3）______________（1）s=(lq->front)->next;（2）*x=s->data;（3）(lq->front)->next=s->next;6.已知下面算法，回答以下问题intcount=0;voidfun1(bitreptrt){if(t!=NULL){if((t->lchild==NULL)&&(t->rchild==NULL))count++;fun1(t->lchild,count);fun1(t->rchild,count);}}简述fun1（）的功能如果程序遍历的二叉树如下，写出最终count的结果（1）求二叉树的叶子数目（2）37.阅读下列算法并回答问题：voidfun3(listr);{for(i=2;i=n;i++){r[0]=r[i];j=i-1;while(r[0].key<r[j].key){r[j+1]=r[j];j――;}r[j+1]=r[0];}}简述fun3（）的功能在程序中r[0]的功能（1）直接插入排序（2）a．在进入循环之前，存储r[i]的值b．在while循环中监视j是否越界（哨兵，监视哨）8.阅读下面算法，回答以下问题intfun1(StackS){intn=0;while(!StackEmpty(S)){n++;Pop(S);}return(n）;}如果现在{7,2,3,23,56,9}6个元素依次入栈，算法返回值是多少？简述fun1（）的功能。（1）6（2）计算栈中的数的个数9.阅读下面的二分法查找的算法，请在空缺处填入合适的内容，使其成为一个完整的算法。intbinsearch(sqtableR,keytypeK){low=1;hig=R.n;while(low<=hig){（1）______________switch{caseK==R.item[mid].key:return(mid);caseK<R.item[mid].key:（2）______________；break;caseK>R.item[mid].key:（3）______________；break;}}return(0);}（1）______________（2）______________（3）______________（1）mid=(low+hig)/2;（2）hig=mid-1;（3）low=mid+1；10.有向图的邻接表类型定义如下，阅读下面算法，要求回答下面问题：#definevnum5typedefstructarcnode{intadjvex;structarcnode*nexttarc;}ArcNodeTp;typedefstructvexnode{intvertex;ArcNodeTp*firstarc;}AdjList[vnum];typedefstructgraph{AdjListadjlist;intvexnum,arcnum;}Graphtp;voidIndegree(AdjListg){for(i=0;i<n;j++){num=0;for(j=0;j<n;j++)if(i!=j){p=g[j].firstarc;while(p){if(p->adjvex==i)num++;p=p->next;}}printf(“顶点%d：%d\n”,g[i].vexdata,num);}}已知有向图如下，该算法的输出结果为：该算法的功能。（1）顶点1：2顶点2：1顶点3：1顶点4：1顶点5：1（2）求5个顶点有向图每个顶点的入度.11.阅读下面的单链表第i位置上插入一个以x为值的新结点的算法，请在空缺处填入合适的内容，使其成为一个完整的算法。voidins_lklist(lklisthead,inti){p=find_lklist(head,i-1);if(p==NULL)error('不存在第i个位置');else{s=malloc(size);s->data=x;（1）_______________。（2）_______________。}（1）_______________。（2）_______________。（1）s->next=p->next;（2）p->next=s;12.下面是在顺序栈上实现的一个栈基本操作，该操作的功能是_________。typedefstruct{DataTypedata[100]；inttop；}SeqStack；DataTypefun1(SeqStack*S){if(StackEmpty(S))Error(”Stackisempty”)；return（S->data[S->top]）；}取栈顶元素（5分）13.阅读下面算法，回答问题。intfun2(MGraph*G,inti){intd=0,j;for(j=0;j<n;j++){if(G->edges[i][j])d++;if(G->edges[j][i])d++;}return

(d);}(1)简述函数fun2（）的功能;(2)写出函数fun2（）的时间复杂度。（1）计算邻接矩阵中第i结点的入度和出度之和（2）O（n）14.阅读下面算法，回答问题：LinkListfun1(LinkListL)/*L是无头结点单链表*/

{ListNode*Q,*P;

if(L&&L->next){

Q=L;L=L->next;P=L;

while(P->next)P=P->next;

P->next=Q;Q->next=NULL;

}

returnL;

}简述fun1（）的功能如果L的初始状况如下，请画出最终L的状态（1）该算法的功能是：将开始结点摘下链接到终端结点之后成为新的终端结点，而原来的第二个结点成为新的开始结点，返回新链表的头指针。（2）15.阅读下面算法，算法功能为往无向图的邻接矩阵中插入顶点，解释（1）（2）两句语句功能voidAddVertexMGraph(MGraph*G,VertexTypex){if(G->n>=MaxVertexNum)Error("顶点数太多")；G->vexs[G->n]=x;（1）G->n++；（2）}（1）______________（2）______________（1）将新顶点输入顶点表（2）顶点数加116.阅读下面程序，回答问题：for(i=1;i<＝n;i++) for(j=1;j<＝i;j++) t=t+1;该程序段的时间复杂性量度是多少？（要求写出运算步骤）计算频度最大的语句为t=t+1，计算总的次数为1＋2＋3＋…+n=n*(n+1)/2所以时间复杂度为O(n2)17.阅读下面算法借助栈将一个带头结点的单链表倒置，请在空缺处填入合适的内容，使其成为一个完整的算法。voidreverse_list(LkListTp*head){LStackTpls,p;datatypex;InitStack(&ls);/*初始化链栈*/p=(*head)->next;while(p!=NULL){Push(&ls,p->data);p=p->next;}（1）_____________while(!EmptyStack(ls)){Pop(&ls,&x);（2）_____________（3）_____________}（1）_____________（2）_____________（3）_____________（1）p=(*head)->next;（2）p->data=x;（3）p=p->next;18.阅读下面算法，算法功能为向无向图的邻接表中插入一个顶点，解释（1）（2）（3）的语句功能voidAddVertexALGraPh(ALGrahp*G,VertexTypex){if(G->n>=MaxVertexNum)Error("顶点数太多")；G->adjlist[G->n].vertex=x;（1）G->adjlist[G->n].firstedge=NULL;（2）G->n++；（3）}（1）_____________（2）_____________（3）_____________（1）将新顶点输入顶点表（2）边表置为空表（3）顶点数加119.for(i=1；i<=n；i++){s=i+2;

for(j=1；j<=n；j++)

s=2*j；}该程序段的时间复杂度为多少？（写出运算步骤）赋值为频度最高语句，执行次数为n*n次所以时间复杂度为O（n2）20.阅读下面算法，要求回答下面问题：typedefstrutcycqueue{DataTypedata[maxsize];intrear,front;}CycqueueTp;CycqueueTpsq;intfun2(CycqueueTp*sq,DataTypex){if((sq->rear+1)%maxsize==sq->front){error("队满");return0;}else{sq->rear=(sq->rear+1)%maxsize;sq->data[sq->rear]=x;return1;}}intfun3(CycqueueTp*sq,DataType*x){if((sq->front==sq->rear){error("队空");return0;}else{sq->front=(sq->front+1)%maxsize;*x=sq->data[sq->front];return1;}}intfun4(cycqueueTpsq,DataType*x){if(sq.rear==sq.front)return0;else{*x=sq.data[(sq.front+1)%maxsize];return1;}}（1）算法fun2（）的功能。（2）算法fun3（）的功能。（3）算法fun4（）的功能。（1）循环队元素入队（2）循环队元素出队（3）循环队元素取队头元素21.阅读下面广度优先搜索算法，请在空缺处填入合适的内容，使其成为一个完整的算法。Bfs(GraphTpg,intv){QueptrTpQ;ArcNodeTp*p;InitQueue(&Q);Printf("%d",v);Visited[v]=1;EnQueue(&Q,v);Whi