华东理工大学数据结构（本）期末复习题及参考答案.docx
数据结构(本)(网教)202301-模拟卷注：找到所考试题直接看该试题所有题目和答案即可。查找按键：Ctrl+F超越高度一、单选题(共10题，20分)1、设循环队列中数组的下标范围是ln,其头尾指针分别尾f、r,则队列中元素的个数为().A、 r-fB、 r-f+1C、 (r-f+1)modnD、 (r-f+n)modn正确答案：D2、以下哪一个不是队列的基本运算？A、从队尾插入一个新元素B、从队列中删除第i个元素C、判断一个队列是否为空D、读取队头元素的值正确答案：B3、有一个有序表1,3,9,12,32,41,62,75,77,86,95,100),当二分查找值为86的关键字时,需要比较的次数是()。A、2B、3C、4D、5正确答案：C4、栈S最多能容纳4个元索。现有6个元索按A、B、C、D、E、F的顺序进栈,问下列哪一个序列是可能的出栈序列？.E、D、C、B、A、FB. B、C、E、F、A、DC. C、B、E、D、A、FD. A、D、F、E、B、C正确答案：C5、n个顶点的无向连通图至少有()条边。A、 n-1B、 nC、 n+1D、2n正确答案：A6、设有IOOOO个无序元索,希望用较快速度挑选出其中前15个最大元素,采用()方法最好.A、直接插入排序B、堆排序C、快速排序D、归并排序正确答案：B7、已知一棵二叉排序树,通过()可以得到结点的有序序列。A、前序遍历B、中序遍历C、后序遍历D、线索化正确答案：B8、S="A;/document/Mary.doc",则的字符定位的位置为().A、2B、3C、12D、11正确答案：B9、假设有60行70列的二维数组ab60,170以列序为主序顺序存储,其基地址为10000,每个元索占2个存储单元,那么第32行第58列的元素a32,58的存储地址为()。(无第。行第0列元素)A、 16902B、 16904C、 14454D、答案A,B,C均不对正确答案：A10、具有36个结点的完全二叉树的深度为()。A、5B、6C、7D、8正确答案：B二、填空题(共10题，10分)1>进栈序列为a,b,c,则通过出栈和进栈操作可能得到的a,b,c的不同的排列序列有一种。(1.0)正确答案：第1空:52、广义表(a,b),c,d)的表头是,表尾是。(1.0)正确答案：第1空：(a,b)(c,d)3、假设用循环单链表实现队列,若队列非空,且队尾指针为R,则将新结点S加入队列时,需执行下面语句:;O(1.0)正确答案：第1空：S->next=R->next第2空：R->next=S第3空:R=S4、具有8个顶点的有向完全图有条弧。(LO)正确答案：第1空:565、判定一个栈ST(最多元素为InO)为空的条件是为满的条件是。(1.0)正确答案：第1空：ST->top=0第2空：ST->top=m06、若对线性表进行的主要操作是按照下标存取而不是插入和删除,则该线性表宜采用一存储结构;如果需要频繁的插入和删除操作,则该线性表宜采用一存储结构。(L0)正确答案：第1空:顺序第2空:链式7、图的广度优先遍历类似于树的一遍历。（Lo）正确答案：第1空:层次8、一个有n个叶子结点的哈夫曼树中,其结点总数为一（1.0）正确答案：第1空：2nT9、一棵具有35个结点的完全二叉树,它的深度为一（1.0）正确答案：第1空:610、设目标串T="CdbCCadCdCCbaa”,模式P="cade”,则第次匹配成功。（LO）正确答案：第1空:5三、判断题（共10题，10分）1、链式存储是一种随机存取的数据结构。（LO）正确答案：错误2、线性表的逻辑顺序与存储顺序总是一致的。（Lo）正确答案：错误3、拓扑排序时,总是在有向图中选择入度为O的顶点输出。（LO）正确答案：正确4、二叉树中所有结点,如果不存在非空左子树,则不存在非空右子树。（1.0）正确答案：错误5、用二叉链表法（Iink-TIink）存储包含n个结点的二叉树,结点的2n个指针区域中有n+1个为空指针。（1.0）正确答案：正确6、平衡二叉排序树具有的特点是左子树与右子树的高度差的绝对值不超过1。（1.0）正确答案：正确7、图的深度优先遍历类似于树的层次遍历。（LO）正确答案：错误8、在一个图中,所有顶点的度数之和等于图的边数的2倍。（LO）正确答案：正确9、栈和队列是一种非线性数据结构。（LO）正确答案：错误10、顺序存储结构只能用来存放线性结构;链式存储结构只能用来存放非线性结构。（LO）正确答案：错误四、简答题（共2题，10分）1、顺序队列的“假溢出”是怎样产生的?如何解决？（5.0）正确答案：一般的一维数组队列的尾指针已经到了数组的上界，不能再有入队操作，但其实数组中还有空位置，这就叫“假溢出”。采用循环队列是解决假溢出的途径。另外，解决循环队满与队空的办法是浪费一个元素空间，用于区别队满还是队空。判断循环队列队空标志是:front=rear队满标志是:front=（rear+l）%N,N为数组的长度。2、写出下列程序段的输出结果（队列中的元素类型QEIenlTyPe为Char）.voidmain()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);该程序段的功能是(5.0)正确答案：char五、算法设计题(共2题，20分)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;p->next=q;将B的元素插入if(s)t=q->next;q->next=s;如A非空,将A的元素插入p=sjq=t;/while/merge)2、设计一递归算法,将以二叉链表为存储结构的二叉树中的叶子结点全部删除。二叉排序树的存储结构如下：正确答案：voidCoutnode(BSTreeT)/*T为树根指针if(T)if(T->IchiId=NULD&&(T->rchiId=NULL)Free(T);/删除度为。的结点；COUnLnOde(T-Xchild);/递归删除左子树中度为0的结点数count_node(T->rchi1d);/递归删除右子树中度为0的结点数1六、计算题(共3题，30分)1、已知某通讯系统使用8种字符,其概率分布分别为：0.06,0.28,0.07,0.08,0.14,0.22,0.03,0.12,试设计其哈夫曼编码(10.0)正确答案：哈夫曼不唯一,其对应编码也不唯一。2、已知二叉树的中序序列为DBGEAFC,后序序列为DGEBFCA,画出对应的二叉树并写出先序遍历序列。(10.0)正确答案：先序序列:ABDCEFGe3、试给出以1为起点的深度优先搜索和广度优先搜索的遍历序列，并用Kruscal算法求其最小生成树。(10分)标准答案：遍历序列不唯一。最小生成树：
