华东理工大学数据结构（本）期末考试复习题.docx
第4场数据结构(本)一、单选题1、设循环队列中数组的下标范围是ln,其头尾指针分别尾f、r,则队列中元素的个数为(D).A>r-fB、r-f÷lC>(r-f+l)modnD(r-f+n)modn2、以下哪一个不是队列的基本运算？BA、从队尾插入一个新元素B、从队列中删除第i个元素C、判断一个队列是否为空D、读取队头元素的值3、有一个有序表1,3,9,12,32,41,62,75,77,86,95,100),当二分查找值为86的关键字时,需要比较的次数是(OoA、2B、3C、4D、54、栈S最多能容纳4个元素。现有6个元素按A、B、C、D、E、F的顺序进栈，问下列哪一个序列是可能的出栈序列？(C)A.E、DsC、B、A、FB.B、C、E、F、A、DC.C、B、E、D、AFD.A、D、F、E、C5、n个顶点的无向连通图至少有(A)条边。A、n-1B>nC>n+1D>2n6、设有10000个无序元素,希望用较快速度挑选出其中前15个最大元素,采用(B)方法最好.A、直接插入排序B、堆排序C、快速排序D、归并排序7、已知一棵二叉排序树,通过(B)可以得到结点的有序序列。A、前序遍历B、中序遍历C、后序遍历D、线索化8、S="A;/document/Mary.doc",则的字符定位的位置为(B).A、2B、3C、12D、119、假设有60行70列的二维数组al60,1-70以列序为主序顺序存储,其基地址为10000,每个元素占2个存储单元,那么第32行第58列的元索a32,58的存储地址为(A)。(无第。行第。列元素)A、16902B、16904C>14454D、答案A,B,C均不对10>具有36个结点的完全二叉树的深度为(B)oA、5Bs6C、7D、8二、填空题1、进栈序列为a,b,c,则通过出栈和进栈操作可能得到的a,b,c的不同的排列序列有_5一种。2、广义表(a,b),c,d)的表头是E,b),表尾是(c,d).3、假设用循环单链表实现队列,若队列非空,且队尾指针为R,则将新结点S加入队列时,需执行下面语句:S->next=R->next;R->next=S;R=SO4、具有8个顶点的有向完全图有_56_条弧。5、判定一个栈ST(最多元素为m)为空的条件是T->top=0为满的条件是ST->top=m0o6、若对线性表进行的主要操作是按照下标存取而不是插入和删除,则该线性表宜采用顺序存储结构;如果需要频繁的插入和删除操作,则该线性表宜采用徒式存储结构。7、图的广度优先遍历类似于树的链式_遍历。8、一个有n个叶子结点的哈夫曼树中,其结点总数为2nT。9、一棵具有35个结点的完全二叉树,它的深度为_6_。IOx设目标串T="CdbCCadCdCCbaa",模式P="cade”,则第_5_次匹配成功。三、判断题1、链式存储是一种随机存取的数据结构。(X)2、线性表的逻辑顺序与存储顺序总是一致的。(X)3、拓扑排序时,总是在有向图中选择入度为0的顶点输出。(J)4、二叉树中所有结点,如果不存在非空左子树,则不存在非空右子树。(X)5、用二叉链表法(Iink-rlink)存储包含n个结点的二叉树,结点的2n个指针区域中有n+1个为空指针。()6、平衡二叉排序树具有的特点是左子树与右子树的高度差的绝对值不超过Io()7、图的深度优先遍历类似于树的层次遍历。(X)8、在一个图中,所有顶点的度数之和等于图的边数的2倍。(J)9、栈和队列是一种非线性数据结构。(X)10、顺序存储结构只能用来存放线性结构;链式存储结构只能用来存放非线性结构。(X)四、简答题1、顺序队列的“假溢出”是怎样产生的?如何解决？答：一般的一维数组队列的尾指针已经到了数组的上界，不能再有入队操作，但其实数组中还有空位置，这就叫“假溢出”。采用循环队列是解决假溢出的途径。另外，解决循环队满与队空的办法是浪费一个元素空间，用于区别队满还是队空。判断循环队列队空标志是:front=rear队满标志是:front=(rear+l)%N,N为数组的长度。2、写出下列程序段的输出结果(队列中的元素类型QEIemTyPe为Char)Ovoidmain()(QueueQ;InitQueue(Q);Charx='e,;y='c'EnQueue(Q,h,);EnQueue(Q,'r');EnQueue(Q,y);DeQueue(Q,x);EnQueue(Q,x);DeQueue(Q,x);EnQueue(Q,a,);While(!QueueEmpty(Q)DeQueue(Q,y);printf(y);Printf(x);该程序段的功能是char.五、算法设计题1、把单链表A和B合并为C,A和B的元素间隔排列,且使用原存储空间。(10.0)答：voidmerge(LinklistA;LinklistB)p=A->next;q=B->next;C=A;while(p&q)s=p->next->next=q;/B的元素插入if(s)t=q->next;q->next=s;/llA非空,将A的元素插入p=s;q=t;/while/merge)2、设计一递归算法,将以二叉链表为存储结构的二叉树中的叶子结点全部删除。二叉排序树的存储结构如下：答：voidcotnode(BSTreeT)/*T为树根指针if(T)if(T->lchiId=NULL)&&(T->rchiId=NULL)Free(T);/删除度为0的结点;Count_node(T->lchild);/递归删除左子树中度为0的结点数COUnt_node(T->rchiId);/递归删除右子树中度为。的结点数)六、计算题1、已知某通讯系统使用8种字符,其概率分布分别为：0.06,0.28,0.07,0.08,0.14,0.22,0.03,0.12,试设计其哈夫曼编码答：哈夫曼不唯一,其对应编码也不唯J2、已知二叉树的中序序列为DBGEAFC,后序序列为DGEBFCA,画出对应的二叉树并写出先序遍历序列。答：先序序列:ABDCEFG。3、试给出以1为起点的深度优先搜索和广度优先搜索的遍历序列，并用KnISCal算法求其最小生成树。答：遍历序列不唯、最小生成树:
