1、数据结构期末考试复习题及参考答案数据结构 复习题（课程代码 252259）一、填空题（本大题共40小题）1.队列中是按照_先进先出_的原则进行数据元素的增删。2._栈_又称为LIFO表。3.在顺序存储的完全二叉树中，若编号为i的结点有左孩子结点，则其右孩子结点的编号为_2i+1_。4.存储地址与关键字之间存在某种映射关系的存储结构为_散列存储结构_。5.在串S=“structure”中，以r为首字符的子串有_9_个。6.设有整型二维数组M43，每个元素（整数）占2个存储单元，元素按行的顺序存储，数组的起始地址为200，元素M11的地址是_208_。7.在一个具有n个顶点的无向完全图中，包含有_
2、 n(n-1)/2_条边，在一个具有n个顶点的有向完全图中，包含有_ n(n-1)_条边。8.假定一个线性表为(12,23,74,55,63,40)，若按Key % 4条件进行划分，使得同一余数的元素成为一个子表，则得到的四个子表分别为_（12，40） （ ） （74） （23,55，63）_。9.向一棵B_树插入元素的过程中，若最终引起树根结点的分裂，则新树比原树的高度_增加1_。10.在堆排序的过程中，对任一分支结点进行筛运算的时间复杂度为_ O(log2n)_，整个堆排序过程的时间复杂度为_ O(nlog2n)_。11.在快速排序、堆排序、归并排序中，_归并_排序是稳定的。12.一棵深度
3、为5的满二叉树中的结点数为_31_个。13.在含n个顶点和e条边的无向图的邻接矩阵中,非零元素的个数为_2e _。14.从一棵二叉排序树中查找一个元素时，若元素的值大于根结点的值，则继续向_右子树_查找。15._拓朴排序_可以判断出一个有向图中是否有环。16.栈又称为_后进先出_的线性表。17.数据结构在计算机中的表示称为数据的_物理结构_。18.有4个结点的不同的二叉树有_9_棵。19.含有60个结点的树有_59_条分支。20.在图结构中，前驱元素和后继元素之间存在着_多对多_的联系。21._哈夫曼树_又称最优二叉树。22.一棵二叉树有67个结点，这些结点的度要么是0，要么是2。这棵二叉树中
4、度为2的结点有_33_个。23.在一个带头结点的单循环链表中，p指向尾结点的直接前驱，则指向头结点的指针head可用p表示为head=_ pnextnext _。24.栈顶的位置是随着_进栈和出栈_操作而变化的。25.设一个散列表的容量为M，用线性探测法解决冲突.。若要查找一个键值，至少要进行1次比较，至多要进行_M_次比较。26.在n个结点的线索二叉链表中，有_ n-1_个线索指针。27.具有180个结点的二叉树，其深度至少为_8_。28.序列中有1000个元素基本按键值递增顺序排列，就算法的比较次数而言，应选择_ _直接插入_排序算法。29.若堆栈的入栈序列为1,2,3,n-1,n，输出元
5、素i需要进行_ n-i+1_次出栈操作。30.对于队，只能在 队尾 插入元素，只能在 队头 删除元素。31.抽象数据类型ADT可以用三元组（D，S，P）表示，它们分别表示： 数据对象 、 数据关系 和 基本操作 。32.栈是一种受限制的线性表，也叫LIFO结构，LIFO的含义是 后进先出 33.在单链表中，若要在指针p所指结点后插入指针s所指结点，则需要执行下列两条语句：s-next=p-next； p-next=s 34.通常从四个方面评价算法的质量：_正确性 易读性 强壮性 高效率_。35.一个算法的时间复杂度为(n3+n2log2n+14n)/n2，其数量级表示为_ O(n)_。36.假
6、定一棵树的广义表表示为A（C，D（E，F，G），H（I，J），则树中所含的结点数为_9_个，树的深度为_3_，树的度为_3_。37.后缀算式9 2 3 +- 10 2 / -的值为_1_。中缀算式（3+4X）-2Y/3对应的后缀算式为_3 4 X * + 2 Y * 3 / -_。38.若用链表存储一棵二叉树时，每个结点除数据域外，还有指向左孩子和右孩子的两个指针。在这种存储结构中，n个结点的二叉树共有_2n_个指针域，其中有_n-1_个指针域是存放了地址，有_n+1_个指针是空指针。39.对于一个具有n个顶点和e条边的有向图和无向图，在其对应的邻接表中，所含边结点分别有_e_个和_2e_个。
7、40.AOV网是一种_有向无回路_的图。二、单项选择题（本大题共50小题）1将长度为n的单链表链接在长度为m的单链表之后的算法的时间复杂度为（D ）A）O（1） B）O（n） C）O（m） D）O（m+n）2如下所示的图的拓扑序列为（ D） A） C1，C2，C3，C4，C5，C6B)C1，C2，C5，C3，C4，C5，C7C)C1，C4，C2，C3，C5，C6D)C1，C2，C5，C4，C3，C63在含n个顶点和e条边的无向图的邻接矩阵中,零元素的个数为( D )A）e B）2e C）n2e D）n22e4设有6个结点的无向图，该图至少应该有(A)条边才能确保是一个连通图A5 B6 C7 D
8、85有N个结点的图的邻接矩阵存储法中，链表的表头结点有（ A ）个。A、 N B、 2N C、N/2 D、N*N E、N-26具有4个顶点的无向完全图有（ A ）条边。A、6 B、12 C、16 D、207邻接矩阵是对称矩阵的图为(D ）。A、有向图 B、带权有向图 C、带权连通图 D、无向图8在长度为n的线性表中查找值为x的数据元素的时间复杂度为（C）。A）O(0)B）O(1)C）O(n)D）O(n2)9若一个栈的输入序列是1，2，3，n，输出序列的第一个元素是n，则第i个输出元素是（D）。A）不确定B）n-iC、n-i-1D、n-i+110设栈S和队列Q的初始状态为空，元素e1,e2,e3
9、,e4,e5,e6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出队的顺序是e2,e4,e3,e6,e5,e1，则栈的容量至少应该是（C）。A、6B、4C、3D、211一个栈的入栈序列是1，2，3，4，5，则栈的不可能的出栈序列是（C）。A、5，4，3，2，1B、4，5，3，2，1C、4，3，5，1，2D、1，2，3，4，512设计一个判别表达式中左右括号是否匹配的算法，采用（B）数据结构最佳。A、顺序表B、栈C、队列D、链表13在解决计算机主机与打印机之间速度不匹配问题时，通常设置一个打印缓冲区，该缓冲区应该是一个（B）结构。A、栈B、队列C、数组D、线性表14线性表若采用链表存储结构
10、，要求内存中可用存储单元地址( D )A必须连续 B部分地址必须连续 C一定不连续 D连续不连续均可15依次在初始为空的队列中插入元素X，Y，Z，W以后，紧接着作了两次删除操作，此时的队头元素是（ C ）A）X B）Y C）Z D）W16已知一个有向图如下图所示，则从顶点a出发进行深度优先偏历，不可能得到的DFS序列为（ A ）。 A) a d b e f c B) a d c e f b C) a d c b f e D) a d e f c b17若连通无向图G有n个顶点，则图G的生成树有（ B ）条边A）n B）n-1 C）n(n-1)/2 D）n/218设数组datam作为循环队列SQ
11、的存储空间，front为队头指针，rear为队尾指针，则执行出队操作后其头指针front值为（ D ）A）front=front+1 B）front=(front+1)%(m-1) C）front=(front-1)%m D）front=(front+1)%m19设某算法的问题规模函数f(n)=25n3+5000n2，则它的渐进时间复杂度为（ A ）。 A）O(n3) B）O(n2) C）O(n) D）O(1)20假定一个顺序队列的队首和队尾指针分别为f和r，则判断队空的条件为( D )。A）f+1=r B）r+1=f C）f=0 D）f=r21线性表采用链式存储时，结点的存储地址（ B ）
12、A） 必须是不连续的 B） 连续与否均可 C） 必须是连续的 D） 和头结点的存储地址相连续22设计递归问题的非递归算法一般需要用到（ D ）。A）链表 B）队列 C）树 D）堆栈23对下面二叉树，按中序遍历所得到的结点序列为（ A ）。A）DBEAFC B）DEBFCA C）BDEACF D）ABCDEF24对于一个具有n个顶点的无向图，若采用邻接表表示，则存放表头结点的数组的大小为（ A ）。A）n B）n+1 C）n-1 D）n+边数25设有一个含有n 个(n2)关键字的有序表，设s和h分别是用顺序查找法和二分查找法进行查找时的等概率情况下查找成功的平均查找次数，则s和h的关系是（ B
13、）。A）s = h B）s h C）s h D）不能确定26一棵深度为7的满二叉树有（ D ）叶子结点。 A）7 B）14 C）32 D）6427设二叉树根结点的层次为1，含有15个结点的二叉树中的最小高度是（4 ） A） 6 B） 5 C） 4 D） 328在长度为n的顺序表的第i（1in+1）个位置上插入一个元素，元素的移动次数为（ B ）。A）i-1 B）n-i+1 C）i D）n-i29一棵深度为8的满二叉树有（ C ）叶子结点。 A）256 B）255 C）128 D）12730在一非空二叉树的中序遍历序列中，根结点的右边(A )A只有右子树上的所有结点 B只有右子树上的部分结点C只
14、有左子树上的所有结点 D只有左子树上的部分结点31以下关于数据结构的叙述，正确的是( C)A线性表的线性存储结构优于链式结构B二叉树的第I层上有2的（I-1）次幂个结点，深度为K的二叉树上有2的（k-1）次幂个结点C二维数组是其数据元素为线性表的线性表D栈的操作方式是先进先出32在单链表中，增加头结点的目的是为了（ C ）。A使单链表至少有一个结点B表示表结点中首结点的位置C方便运算的实现D说明单链表是线性表的链式存储实现33使用双向链表存放数据的优点是(A )A提高检索速度 B很方便地插入和删除数据C节约存储空间 D很快回收存储空间34带头结点的单链表Head为空的判定条件是(B )AHea
15、d=NIL BHead.Next=NIL CHead.Next=Head DHead=Head35下列哪一种图的邻接矩阵是对称矩阵(B )A有向图 B无向图 CAOV网 DAOE网36下列叙述中，正确的是( D)A线性表的线性存储结构优于链表存储结构 B队列的操作方式是先进后出C栈的操作方式是先进先出D二维数组是指它的每个数据元素为一个线性表的线性表37一维数组与线性表的区别是 ( A ) A前者长度固定，后者长度可变 B后者长度固定，前者长度可变C两者长度均固定 D两者长度均可变38设有三个元素A、B、C顺序进栈，在进栈过程中可以出栈，出栈次序错误的排列是(C )AABC BBCA CCAB
16、 DCBA39若进栈序列为1，2，34假定进栈和出栈可以穿插进行，则可能的出栈序列是( D)A2，4，1，3 B3，1，4，2 C3，4，1，2 D1，2，3，440若已知一个栈的入栈顺序是1，2，3n，其输出序列为P1,P2，P3Pn，若P1是n，则Pi是（ C）（A） I （B）n-i （C）n-i+1 （D）不确定41栈和队列都是(C )A顺序存储的线性结构 B链式存储的非线性结构C限制存取点的线性结构 D限制存取点的非线性结构42循环队列用数组A0m-1存放其元素值，已知其头尾指针分别是front和rear，则当前队列中的元素个数是(A )A（rear-front+m） MOD m B
17、rear-front-1 Crear-front+1 Drear-front43设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5和e6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出队的顺序是e2、e4、e3、e6、e5、e1，则栈S的容量至少应是（B ）A2 B3 C4 D644一个文本屏幕有25列及80行，屏幕的左上角以（1，1）表示，而右下角则以（80，25）表示，屏幕上每一个字符占用两字节（byte），整个屏幕则以线性方式存储在电脑的存储器内，从屏幕左上角开始，位移为0，然后逐列逐列存储。求位於屏幕（X，Y）的第一个字节的位移是（ ）A.（Y*80+X）*2-1 B
18、.（Y-1）*80+X-1）*2C.（Y*80+X-1）*2 D.（Y-1）*80+X）*2-145对任何一棵二叉树T，设N0、N1、N2分别是度数为0、1、2的结点数，则下列判断正确的是（ A）AN0N21BN1N01CN2N01DN2N1146下面关于二叉树的叙述正确的是(A )A一棵二叉树中叶子结点的个数等于度为2的结点个数加1B一棵二又树中的结点个数大于0C二叉树中任何一个结点要么是叶，要么恰有两个子女D二叉树中，任何一个结点的左子树和右子树上的结点个数一定相等47先序序列和中序序列相同的二叉树为空树或(C )A任一结点均无右孩子的非空二叉树 B仅有两个结点的二叉树C任一结点均无左孩子
19、的非空二叉树 D不存在这样的二叉树48给出一组整型数28、10、37、63、35、30、23，请用二叉树对它进行排序。为此，首先要生成一棵二叉树，规则是把第一数放在根处，接着凡比它小的数放在左子树，比它大的数放在右子树，直到把所有的数均安排好。然后对此二叉树进行( )，得到的就是按照升序排列好的序列。( B)A前序遍历 B中序遍历 C后序遍历 D横向遍历49下面关于数据结构的叙述中，不正确的叙述是( A)A顺序存储方式的优点是存储密度大，且插入、删除运算效率高B链表中的每一个结点都包含一个指针C包含n个结点的二叉排序树的最大检索长度为nD将一棵树转换为二又树后，根结点没有右子树50由3个结点可
20、以构造出多少种不同的有序树(D )A2 B3 C4 D5三、判断题（本大题共30小题）1.（ ）折半搜索只适用于有序表，包括有序的顺序表和有序的链表。2.（）数据的机内表示称为数据的存储结构。3.（ ）程序就是算法，但算法不一定是程序。 4.（ ）101，88，46，70，34，39，45，58，66，10是堆。5.（ ）程序就是算法，但算法不一定是程序。6.（）二叉树中任何一个结点的度都是2。7.（ ）双循环链表中任一结点的前趋指针均指向其逻辑前趋8.（ ）若从有向图的某个顶点出发进行一次深度优先搜索可以访问图的每个顶点， 则该图一定是有向完全图。9.（ ）强连通图的各顶点间均可达。10.（
21、 ）对于任意一个图，从它的某个结点进行一次深度或广度优先遍历可以访问到该图的每个顶点。11.（）在待排序的记录集中，存在多个具有相同键值的记录，若经过排序，这些记录的相对次序仍然保持不变，称这种排序为稳定排序。12.（ ）不管堆栈采用何种存储结构，只要堆栈不空，可以任意删除一个元素。13.（）单链表中至多只有一个结点的后继指针为空。14.（ ）对线性表进行折半查找时，要求线性表必须以链式方式存储，且结点按关键字有序排列。15.（）散列法存储的思想是由关键字值决定数据的存储地址。16.（）二叉树为二叉排序树的充分必要条件是其任一结点的值均大于其左孩子的值、小于其右孩子的值。17.（ ）队列是一种
22、插入和删除操作分别在表的两端进行的线性表，是一种先进后出的结构。18.（ ）串是一种特殊的线性表，其特殊性体现在可以顺序存储。19.（）长度为1的串等价于一个字符型常量。20.（）空串和空白串是相同的。21.（ ）数组元素的下标值越大，存取时间越长。22.（）在平衡二叉树中，任意结点左右子树的高度差（绝对值）不超过1。23.（ ）一个无向图的邻接矩阵中各元素之和与图中边的条数相等。24.（ ）程序就是算法，但算法不一定是程序。25.（ ）设S=”cart”，S=”cat”，则S为S的子串。26.（ ）有n个结点的不同的二叉树有n！棵。27.（ ）一棵哈夫曼树中不存在度为1的结点。28.（ ）拓
23、扑排序是按AOE网中每个结点事件的最早发生时间对结点进行排序。29.（ ）冒泡排序算法关键字比较的次数与记录的初始排列次序无关。30.（ ）具有n个结点的二叉排序树有多种，其中树高最小的二叉排序树是最佳的。四、应用题（本大题共10道小题）1、初始序列的键值：（84，85，83，34，98，28，19，76，54，48），采用冒泡排序法进行从小到大的排序，请写出每一趟排序的结果，并记录每一趟排序时交换元素的次数最后求出该排序过程的总的元素交换次数。排序过程：初 始： 84，85，83，34，98，28，19，76，54，48 交换次数第1趟： 84，83，34，85，28，19，76，54，48
24、，98 7第2趟： 83，34，84，28，19，76，54，48，85 7第3趟： 34，83，28，19，76，54，48，84 6第4趟： 34，28，19，76，54，48，83 6第5趟： 28，19，34，54，48，76 4第6趟： 19，28，34，48, 54 2第7趟： 19，28，34，48 0上一趟无交换，排序完成总共交换了2+4+6+6+7+7=32次2、证明：已知一棵二叉树的前序序列和中序序列，则可唯一确定该二叉树。参考答案：证明采用归纳法。设二叉树的前序遍历序列为a1a2a3 an，中序遍历序列为b1b2b3 bn。当n=1时，前序遍历序列为a1，中序遍历序列为b
25、1，二叉树只有一个根结点，所以，a1= b1，可以唯一确定该二叉树；假设当n=k时，前序遍历序列a1a2a3 ak和中序遍历序列b1b2b3 bk可唯一确定该二叉树，下面证明当n=k+1时，前序遍历序列a1a2a3 akak+1和中序遍历序列b1b2b3 bk bk+1可唯一确定一棵二叉树。在前序遍历序列中第一个访问的一定是根结点，即二叉树的根结点是a1，在中序遍历序列中查找值为a1的结点，假设为bi，则a1=bi且b1b2 bi-1是对根结点a1的左子树进行中序遍历的结果，前序遍历序列a2a3 ai是对根结点a1的左子树进行前序遍历的结果，由归纳假设，前序遍历序列a2a3 ai和中序遍历序列
26、b1b2 bi-1唯一确定了根结点的左子树，同样可证前序遍历序列ai+1ai+2 ak+1和中序遍历序列bi+1bi+2 bk+1唯一确定了根结点的右子树。3、逐个结点插入构成平衡二叉树，插入结点的数据顺序为：12,4,1,7,8,10,9,2,11,6,5，在插入过程中平衡树条件如被破坏，则进行必要的调整，试画出每插入一个结点后平衡树的情况。参考答案：4、画出将下面的树转化成二叉树的过程，并写出构造出的二叉树的先根、中根和后根遍历序列。参考转换过程：先根：ABCEFGDIJK中根：BFGECIJKDA 后根：GFEKJIDCBA5、设有升序排列的线性表（2,4,7,10,12,16,18,1
27、9,20,24,27,29,30,35,36,40,41），用二分查找法进行查找。1)画出查找关键字27的过程（3分）第1次：2, 4, 7, 10, 12, 16, 18, 19, 20, 24, 27, 29, 30, 35, 36, 40, 41 第2次：2, 4, 7, 10, 12, 16, 18, 19, 20, 24, 27, 29, 30, 35, 36, 40, 41 第3次：2, 4, 7, 10, 12, 16, 18, 19, 20, 24, 27, 29, 30, 35, 36, 40, 41查找成功。2)画出查找关键字11的过程（4分）第1次：2, 4, 7, 10
28、, 12, 16, 18, 19, 20, 24, 27, 29, 30, 35, 36, 40, 41 第2次：2, 4, 7, 10, 12, 16, 18, 19,20, 24, 27, 29, 30, 35, 36, 40, 41 第3次：2, 4, 7, 10, 12, 16, 18, 19,20, 24, 27, 29, 30, 35, 36, 40, 41第4次：2, 4, 7, 10, 12,16, 18, 19, 20, 24, 27, 29, 30, 35, 36, 40, 41第5次：2, 4, 7, 10, 12,16, 18, 19, 20, 24, 27, 29, 30, 35, 36, 40, 41无数据可比，查找不成功。3)计算该表在等概率的情况下查找成功的平均查找次数为多少？(3分)先画出该序列对应的二分查找树：
