《华东理工大学数据结构(本)期末考试复习题.pdf》由会员分享，可在线阅读，更多相关《华东理工大学数据结构(本)期末考试复习题.pdf（2页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、 1/4 第 4 场 数据结构（本）一、单选题 1、设循环队列中数组的下标范围是 1n,其头尾指针分别尾 f、r,则队列中元素的个数为(D).A、r-f B、r-f+1 C、(r-f+1)mod n D、(r-f+n)mod n 2、以下哪一个不是队列的基本运算?B A、从队尾插入一个新元素 B、从队列中删除第 i 个元素 C、判断一个队列是否为空 D、读取队头元素的值 3、有一个有序表1,3,9,12,32,41,62,75,77,86,95,100,当二分查找值为 86 的关键字时,需要比较的次数是(C)。A、2 B、3 C、4 D、5 4、栈 S 最多能容纳 4 个元素。现有 6 个元素
2、按 A、B、C、D、E、F 的顺序进栈,问下列哪一个序列是可能的出栈序列?(C)A.E、D、C、B、A、F B.B、C、E、F、A、D C.C、B、E、D、A、F D.A、D、F、E、B、C 5、n 个顶点的无向连通图至少有(A)条边。A、n-1 B、n C、n+1 D、2n 6、设有 10000 个无序元素,希望用较快速度挑选出其中前 15 个最大元素,采用(B)方法最好.A、直接插入排序 B、堆排序 C、快速排序 D、归并排序 7、已知一棵二叉排序树,通过(B)可以得到结点的有序序列。A、前序遍历 B、中序遍历 C、后序遍历 D、线索化 8、S=“A;/document/Mary.doc”
3、,则“/”的字符定位的位置为(B).A、2 B、3 C、12 D、11 9、假设有 60 行 70 列的二维数组 a160,170以列序为主序顺序存储,其基地址为 10000,每个元素占 2 个存储单元,那么第 32 行第 58 列的元素 a32,58的存储地址为(A)。(无第 0 行第 0 列元素)A、16902 B、16904 C、14454 D、答案 A,B,C 均不对 10、具有 36 个结点的完全二叉树的深度为(B)。A、5 B、6 C、7 D、8 二、填空题 1、进栈序列为 a,b,c,则通过出栈和进栈操作可能得到的 a,b,c 的不同的排列序列有_5_种。2、广义表(a,b),c
4、,d)的表头是(a,b)|,表尾是(c,d)。3、假设用循环单链表实现队列,若队列非空,且队尾指针为 R,则将新结点 S 加入队列时,需执行下面语句:S-next=R-next;R-next=S;R=S。4、具有 8 个顶点的有向完全图有_56_条弧。5、判定一个栈 ST(最多元素为 m0)为空的条件是 T-top=0 为满的条件是 ST-top=m0。6、若对线性表进行的主要操作是按照下标存取而不是插入和删除,则该线性表宜采用顺序存储结构;如果需要频繁的插入和删除操作,则该线性表宜采用链式存储结构。2/4 7、图的广度优先遍历类似于树的链式_遍历。8、一个有 n 个叶子结点的哈夫曼树中,其结
5、点总数为 2n-1。9、一棵具有 35 个结点的完全二叉树,它的深度为_6_。10、设目标串 T=”cdbccadcdccbaa”,模式 P=“cadc”,则第_5_次匹配成功。三、判断题 1、链式存储是一种随机存取的数据结构。（）2、线性表的逻辑顺序与存储顺序总是一致的。（）3、拓扑排序时,总是在有向图中选择入度为 0 的顶点输出。（）4、二叉树中所有结点,如果不存在非空左子树,则不存在非空右子树。（）5、用二叉链表法(link-rlink)存储包含 n 个结点的二叉树,结点的 2n 个指针区域中有 n+1 个为空指针。（）6、平衡二叉排序树具有的特点是左子树与右子树的高度差的绝对值不超过
6、1。（）7、图的深度优先遍历类似于树的层次遍历。（）8、在一个图中,所有顶点的度数之和等于图的边数的 2 倍。（）9、栈和队列是一种非线性数据结构。（）10、顺序存储结构只能用来存放线性结构;链式存储结构只能用来存放非线性结构。（）四、简答题 1、顺序队列的“假溢出”是怎样产生的?如何解决?答：一般的一维数组队列的尾指针已经到了数组的上界，不能再有入队操作，但其实数组中还有空位置，这就叫“假溢出”。采用循环队列是解决假溢出的途径。另外，解决循环队满与队空的办法是浪费一个元素空间，用于区别队满还是队空。判断循环队列队空标志是:front=rear 队满标志是:front=(rear+1)%N，N
7、为数组的长度。2、写出下列程序段的输出结果(队列中的元素类型 QElem Type 为 char)。void main()Queue Q;InitQueue(Q);Char x=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）答：