计算机水平考试-数据库系统工程师分类模拟题数据结构与算法(一)

数据库系统工程师分类模拟题数据结构与算法一1、在一棵完全二叉树中，其根的序号为1，1可判声序号为P和Q的两个结点是否在同一层。2、堆是一种数据结构，2是堆。A10，50，80，30，60，20，15，18B10，18，15，20，50，80，30，60C10，15，18，50，80，30，60，20D10，30，60，20，15，18，50，803、3从二叉树的任一结点出发到根的路径上，所经过的结点序列必须按其关键字降序排列。A二叉排序树B大顶堆C小顶堆D平衡二叉树4、若广义表L1，2，3，则L的长度和深度分别为4。A1和1B1和2C1和3D2和25、若对27个元素只进行三趟多路归并排序，则选取的归并路数为5。A2B3C4D56、循环链表的主要优点是6。A不再需要头指针了B已知某个结点的位置后，能很容易地找到它的直接前驱结点C在进行删除操作后，能保证链表不断开D从表中任一结点出发都能遍历整个链表7、表达式ABCD的后缀表达形式为7。AABCDBABCDCABCDDABCD8、若二叉树的先序遍历序列为ABDECF，中序遍历序列为DBEAFC，则其后序遍历序列为8。ADEBAFCBDEFBCACDEBCFADDEBFCA9、无向图中一个顶点的度是指图中9。A通过该顶点的简单路径数B通过该顶点的回路数C与该顶点相邻的顶点数D与该顶点连通的顶点数10、利用逐点插入法建立序列50，72，43，85，75，20，35，45，65，30对应的二叉排序树以后，查找元素30要进行10次元素间的比较。A4B5C6D711、表达式“XABCD/E”的后缀表示形式可以为11运算符优先级相同时，遵循左结合的原则。AXABCDE/BXABCDE/CXABCDXE/DXABCDEX/设栈S和队列Q的初始状态为空，元素A、B、C、D、E依次进入栈S，当一个元素从栈中出来后立即进入队列Q。若从队列的输出端依次得到元素C、D、B、A、E，则元素的出栈顺序是12，栈S的容量至少为13。12、AA、B、C、D、EBE、D、C、B、ACC、D、B、A、EDE、A、B、D、C13、A2B3C4D5已知某图的邻接表如图412所示。此邻接表所对应的无向图为14。此图由F开始的深度优先遍历为15。此图由9开始的深度优先遍历的支撑树为16。此图由F开始的广度优先遍历为17。此图由9开始的广度优先遍历的支撑树为18。14、15、AFGILJMKHBFGILJKHMCFGILJKMHDFGHMILJKEFGHILJKMFFGHMKLJI16、17、AFGILJMKHBFGILJKHMCFGILJKMHDFGHMILJKEFGHILJKMFFGHMKLJI18、在查找算法中，可用平均查找长度记为ASL来衡量一个查找算法的优劣，其定义为此处PI为表中第I个记录被查找的概率，CI为查找第I个记录时同关键字比较的次数，N为表中记录数。以下叙述中均假定每一个记录被查找的概率相等，即PI/NI1，2，N。当表中的记录连续存储在一个一维数组中时，可采用顺序查找与折半查找方法折半查找要求表是按关键字有序排列的。顺序查找时的ASL为19，折半查找时的ASL为20。记录的关键字有序时，用二叉排序树查找记录，在最坏的情况下，ASL为21。当二叉排序树是一棵平衡树时，ASL为22。在平衡树上删除一个结点后可以通过旋转使其平衡，最坏的情形下需23次旋转。19、AO1BOLOG2NCOLOG2N2DONLOG2NEONFON220、AO1BOLOG2NCOLOG2N2DONLOG2NEONFON221、AO1BOLOG2NCOLOG2N2DONLOG2NEONFON222、AO1BOLOG2NCOLOG2N2DONLOG2NEONFON223、AO1BOLOG2NCOLOG2N2DONLOG2NEONFON2在内排序的过程中，通常需要对待排序的关键码集合进行多遍扫描。采用不同排序方法，会产生不同的排序中间结果。设要将序列Q，H，C，Y，P，A，M，S，R，D，F，X中的关键码按字母的升序重新排列，则24是冒泡排序一趟扫描的结果，25是初始步长为4的希尔排序一趟扫描的结果，26是两路归并合并排序一趟扫描的结果，27是以第一个元素为分界元素的快速排序一趟扫描的结果，28是堆排序初始建堆的结果。24、AF，H，C，D，P，A，M，Q，R，S，Y，XBP，A，C，S，Q，D，F，X，R，H，M，YCA，D，C，R，F，Q，M，S，Y，P，H，XDH，C，P，A，M，S，R，D，F，X，YEH，Q，C，Y，A，P，M，S，D，R，F，X25、AF，H，C，D，P，A，M，Q，R，S，Y，XBP，A，C，S，Q，D，F，X，R，H，M，YCA，D，C，R，F，Q，M，S，Y，P，H，XDH，C，P，A，M，S，R，D，F，X，YEH，Q，C，Y，A，P，M，S，D，R，F，X26、AF，H，C，D，P，A，M，Q，R，S，Y，XBP，A，C，S，Q，D，F，X，R，H，M，YCA，D，C，R，F，Q，M，S，Y，P，H，XDH，C，P，A，M，S，R，D，F，X，YEH，Q，C，Y，A，P，M，S，D，R，F，X27、AF，H，C，D，P，A，M，Q，R，S，Y，XBP，A，C，S，Q，D，F，X，R，H，M，YCA，D，C，R，F，Q，M，S，Y，P，H，XDH，C，P，A，M，S，R，D，F，X，YEH，Q，C，Y，A，P，M，S，D，R，F，X28、AF，H，C，D，P，A，M，Q，R，S，Y，XBP，A，C，S，Q，D，F，X，R，H，M，YCA，D，C，R，F，Q，M，S，Y，P，H，XDH，C，P，A，M，S，R，D，F，X，YEH，Q，C，Y，A，P，M，S，D，R，F，X对由N个记录所组成的有序关键码排序时，下列各常用排序算法的平均比较次数分别是二路归并排序为29，冒泡排序30，快速排序为31。其中，归并排序和快速排序所需要的辅助存储分别是32和33。29、AO1BONLOG2NCONDON2EONLOG2N2FOLOG2N30、AO1BONLOG2NCONDON2EONLOG2N2FOLOG2N31、AO1BONLOG2NCONDON2EONLOG2N2FOLOG2N32、AO1BONLOG2NCONDON2EONLOG2N2FOLOG2N33、AO1BONLOG2NCONDON2EONLOG2N2FOLOG2N一棵二叉排序树可顺序存放在一组物理上相邻的存储区中，每个结点及左、右指针依次分别放在该存储区的3个连续单元中。现对一棵结点按字母的字典顺序构成的二叉排序树从根结点户开始顺序放在一个存储区中，结果如图413所示。其中LI为第I个结点的左指针，RI为第I个结点的右指针，则L2应为34，L4应为35，R1应为36。该二叉排序树的前序遍历序列为37，后序遍历序列为38。1000P1001L11002R11003B1004L21005R21006Q1007L31008R31009H100AL4100BR4100CC100DL5100ER5100FJ10010L610011R6图413二叉排序树的存储34、A1003B1004C100AD1009E1006F1000G100CH100FINULL35、A1003B1004C100AD1009E1006F1000G100CH100FINULL36、A1003B1004C100AD1009E1006F1000G100CH100FINULL37、APBQHCJBPBHCJQCBCHJPQDCJHBQPEBHCJQP38、APBQHCJBPBHCJQCBCHJPQDCJHBQPEBHCJQP在图414中，39是非简单图，40是完全图，41和42都是哈密尔顿图，其中41又是欧拉图，44是树。给定数据结构V，E，V为结点的有限集合，VV1，V2，V3，V4，V5，V6，V7，V8，E是V上关系的集合。EV1，V2，V3，V4，V5，V8，V5，V6，V1，V3，V4，V7，V4，V5，V2，V4，V4，V6，它所对应的图形是44，这是45。图的存储结构主要有邻接表和46，若用邻接表来存储一个图，则需要保存一个47存储的结点表和若干个48上存储的关系表又称边表。44、45、A无向树B无向图C有向图D有向树46、A转移矩阵B邻接矩阵C状态矩阵D优先矩阵47、A顺序B链接C散列D分块48、A顺序B链接C散列D索引二叉树的前序、中序和后序遍历法最适合采用49来实现。查找树中，由根结点到所有其他结点的路径长度的总和称为50，而使上述路径长度总和达到最小的树称为51，它一定是52。在关于树的几个叙述中，只有53是正确的。49、A递归程序B迭代程序C队列操作D栈操作50、A路径和B内部路径长度C总深度D深度和51、AB树BB树C丰满树D穿线树52、AB树B平衡树C非平衡树D穿线树53、A用指针方式存储有N个结点的二叉树，至少要有N1个指针BM阶B树中，每个非叶子结点的后件个数大于等于CM阶B树中，具有K个后件的结点，必含有K1个键值D平衡树一定是丰满树一棵查找二叉树，其结点A，B，C，D，E，F依次存放在一个起始地址为N假定地址以字节为单位顺序编号的连续区域中，每个结点占4个字节前2个字节存放结点值，后2个字节依次放左指针、右指针。若该查找二叉树的根结点为万，则它的一种可能的前序遍历为54，相应的层次遍历为55。在以上两种遍历情况下，结点C的左指针LC的存放地址为56，LC的内容为57。结点A的右指针凡的内容为58。54、AEAFCBDBEFACDBCEABCFDDEACBDF55、AEAFCBDBEFACDBCEABCFDDEACBDF56、AN9BN10CN12DN1357、AN4BN8CN12DN1658、AN4BN8CN12DN16在数据压缩编码的应用中，哈夫曼HUFFMAN算法可以用来构造具有59的二叉树，这是一种采用了60的算法。59、A前缀码B最优前缀码C后缀码D最优后缀码60、A贪心B分治C递推D回溯61、关键路径是指AOEACTIVITYONEDGE网中61。A最长的回路B最短的回路C从源点到汇点结束顶点的最长路径D从源点到汇点结束顶点的最短路径62、一个具有767个结点的完全二叉树，其叶子结点个数为62。A383B384C385D38663、若一个具有N个结点、K条边的非连通无向图是一个森林NK，则该森林中必有63棵树。AKBNCNKDNK64、若G是一个具有36条边的非连通无向图不含自回路和多重边，则图G至少有64个顶点。A11B10C9D865、任何一个基于“比较”的内部排序算法，若对6个元素进行排序，则在最坏情况下所需的比较次数至少为65。A10B11C21D3666、66的特点是数据结构中元素的存储地址与其关键字之间存在某种映射关系。A树形存储结构B链式存储结构C索引存储结构D散列存储结构67、若循环队列以数组Q0，M1作为其存储结构，变量REAR表示循环队列中队尾元素的实际位置，其移动按REARREAR1MODM进行，变量LENGTH表示当前循环队列中的元素个数，则循环队列的队首元素的实际位置是67。AREARLENGTHBREARLENGTHMMODMC1REARMLENGTHMODMDMLENGTH68、一个含有N个顶点和E条边的简单无向图，在其邻接矩阵存储结构中共有68个零元素。AEB2ECN2EDN22E69、若一棵哈夫曼树共有9个顶点，则其叶子结点的个数为69。A4B5C6D770、在一棵度为3的树中，有2个度为3的结点，有1个度为2的结点，则有70个度为0的结点。A4B5C6D771、设结点X和Y是二叉树中任意的两个结点，在该二叉树的先根遍历序列中X在Y之前，而在其后根遍历序列中X在Y之后，则X和Y的关系是71。AX是Y的左兄弟BX是Y的右兄弟CX是Y的祖先DX是Y的后裔72、设顺序存储的某线性表共有123个元素，按分块查找的要求等分为3块。若对索引表采用顺序查找方法来确定子块，且在确定的子块中也采用顺序查找方法，则在等概率的情况下，分块查找的平均查找长度为72。A21B23C41D6273、已知有一维数组A0，MN1，若要对应为M行、N列的矩阵，则下面的对应关系73可将元素AK0KMN表示成矩阵的第I行、第J列的元素0IM，0JN。AIK/N，JKMBIK/M，JKMCIK/N，JKNDIK/M，JKN答案1、A解析一棵深度为K且有2K1K1个结点的二叉树称为满二叉树。如果深度为K、有N个结点的二叉树中各结点能够与深度为K的顺序编号的满二叉树从1到N标号的结点相对应，则称这样的二叉树为完全二叉树。根据完全二叉树的定义，显然，在一棵完全二叉树中，所有的叶子结点都出现在第K层或K1层最后两层。性质1具有NN0个结点的完全二叉树的深度为1。性质2如果对一棵有N个结点的完全二叉树的结点按层序编号从第1层到第1层，每层从左到右，则对任一结点I1IN，有1如果I1，则结点I无双亲，是二叉树的根；如果I1，则其双亲是结点I/2。2如果2IN，则结点I为叶子结点，无左孩子；否则，其左孩子是结点2I。3如果2I1N，则结点I无右孩子否则，其右孩子是结点2I1。根据以上性质，要判定序号为P和Q的两个结点是否在同一层，即求是否成立。所以A为所求的结果。2、B解析一个有N个元素的序列K1，K2，KN如果满足则称为小顶堆如果满足则称为大顶堆。由堆的定义可以看出，在大顶堆中，第1个元素是所有元素的最大值。在小顶堆中，第1个元素是所有元素的最小值。根据这个定义，从给定的4个选项来看，如果是堆的话，一定是小顶堆，因为第1个元素10是所有元素中最小的元素。首先看选项A。第1个元素小于第2个元素50和第3个元素80，第2个元素50大于第4个元素30，因此不是堆。按照这种方式，考察所有选项，可以得出B是堆。其对应的树形表示如图41所示。3、C解析由堆的定义我们知道，当为小顶堆时，任意一棵子树的根结点比其左右子结点都要小，所以从任一结点出发到根的路径上，所经过的结点序列必须按其关键字降序排列。大根堆则具有完全相反的性质。很多考生对这个答案不是很理解，认为是二叉排序树。下面，我们根据二叉排序树的定义和性质推导错误结果。二叉排序树又称为二叉查找树，其定义为二叉排序树或者是一棵空树，或者是具有如下性质BST性质的二叉树1若它的左子树非空，则左子树上所有结点的值均小于根结点；2若它的右子树非空，则右子树上所有结点的值均大于根结点；3左、右子树本身又各是一棵二叉排序树。例如，如图42所示就是一棵二叉排序树。由图42可知，从二叉排序树的任一结点出发到根结点的路径上，所经过的结点序列不一定按其关键字降序排列或者升序排列。4、B解析广义表一般记作LSA1，A2，AN其中N是它的长度，AI可以是单个元素原子，也可以是广义表子表，当广义表非空时，称第一个元素A1为LS的表头，称其余元素组成的表为LS的表尾。注意表头是元素可以是原子，也可以是广表，而表尾一定是广义表。例如CA，A的表头是A，表尾是A。A的表头是A，表尾是。广义表的深度定义为所含括弧的重数。注意原子的深度为0，空表的深度为1。例如EA，E是一个递归的广义表，长度为2，深度为1。D，E，A，B，C，D是多层次的广义表，长度为3，深度为3。5、B解析MM1路归并就是将M个有序表组合成一个新的有序表保持原来的顺序。本题已知对27个元素进行3趟归并，要求M。每趟归并M个有序表，第一趟27个元素归并后，剩余27/M个表，归并2趟后剩余27/M2个表，归并3趟后剩余27/M3个表。这时候27/M31，因此，M3。6、D解析本题考查循环链表的基础知识，所以我们来了解一下什么是循环链表。一个带头结点的线性链表如图43所示。若将此链表的最后一个结点D的NEXT域指向头结点，则形成了循环链表，如图44所示。对照图44，我们现在来分析题目的备选答案。选项A“不再需要头指针了”，言下之意就是线性链表一定需要头指针，但实际上不管是非循环的线性链表还是循环链表，头指针都是可要可不要的，所以选项A错误。再来看B选项，“已知某个结点的位置后，能很容易地找到它的直接前驱结点”，题目中只说是循环链表，没有说是双向的循环链表，在单向循环链表中，已知某个结点的位置很难得到它的直接前驱结点，所以B选项不对。接着看C选项，“在进行删除操作后，能保证链表不断开”。在进行结点删除操作后，原则上链表都是断开的，关键是靠删除算法来保证其不断开，与是否循环没有关系。所以也不正确。其实，到这里我们已经知道答案为D了，但我们还是看看D到底对不对。D选项是这样的“从表中任一结点出发都能遍历整个链表”。我们首先看看在非循环的线性链表中，是否能满足这个要求。以图43线性链表中C为例，C只能往向走到D，然后D的NEXT域为空，无路可走，所以非循环的线性链表无法满足这个要求。再看循环链表图44，无论从哪一点出发，都可以到达任一结点，因为所有的结点围成了一个圈。7、B解析题目要求根据已知的表达式写对应后缀表达式。解这种题，如果考生知道了前缀、中缀、后缀表达式有何关联，有什么特点，那么解题就非常轻松了。其实前缀、中缀、后缀的得名，是从二叉树而来的，也就是把一个表达式转化为一棵二叉树后，对二叉树进行前序遍历得到前缀表达式，对二叉树进行中序遍历得到中缀表达式也就是一般形式的表达式，对二叉树进行后序遍历得到后缀表达式。因此，我们只要把表达式转换成二叉树的形式，再对二叉树进行后序遍历，即可得到正确答案。但现在最主要的问题是如何构造这棵树。构造的规则是这样的，所有的操作数只能在叶子结点上，操作符是它们的根结点，括号不构造到二叉树中去，构造树的顺序要遵循运算的顺序。在表达式ABCD中最先计算BC，所以先构造图45的部分。然后，把BC的结果与。进行运算，所以有图46所示的结果。最后，把运算结果和D相减，最终得到的二叉树如图47所示。对图47的二叉树进行后序遍历得到序列ABCD，所以正确答案应是B。8、D解析本题要求根据二叉树的先序遍历和中序遍历求后序遍历。我们可以根据这棵二叉树的先序和中序遍历画出这棵二叉树，然后再得出其后序遍历结果。根据先序和中序来构造二叉树的规则是这样的首先看先序遍历序列ABDECF，先序遍历中第一个访问的结点是A，这说明A是二叉树的根结点因为先序遍历顺序是根，左，右。然后看中序遍历序列DBEAFC，中序中A前面有结点DBE，后面有结点FC。这说明DBE是A的左子树，FC是A的右子树因为中序遍历顺序是左，根，右。再回到先序遍历序列中看DBE的排列顺序此时可以不看其他的结点，我们发现在先序遍历序列中B排在最前面，所以B是A的左子树的根结点。接下来又回到了中序遍历序列，中序遍历序列中D在B的前面，E在B的后面，所以D是B的左子树，E是B的右子树。对于A的右子树，可同样依此规则得出。由此，可构造二叉树，如图48所示。然后对这棵二叉树进行后序遍历，得到DEBFCA。9、C解析本题是纯概念题。1无向图中顶点的度无向图中顶点V的度DEGREE是关联于该顶点的边的数目，也可以说是直接与该顶点相邻的顶点个数，记为DV。例如，在图49中，V1的度为1，V2的度为2，V3的度为3，V4的度为2。2有向图顶点的入度在有向图中，以顶点V为终点的边的数目称为V的入度INDEGREE，记为IDV。例如，在图410中，V1的入度为1，V2的入度为2，V3的入度为1，V4的入度为0。3有向图顶点的出度在有向图中，以顶点V为始点的边的数目，称为V的出度OUTDEGREE，记为ODV。例如，在图410中，V1的出度为0，V2的出度为0，V3的出度为2，V4的出度为2。10、B解析首先，利用逐点插入法对给出的序列建立排序二叉树，如图411所示。从图411中我们可以看出，要查找元素30，其步骤如下1首先，要与50比较，因为3050，所以进入结点50的左子树；2接着，与43比较，因为3043，所以进入结点43左子树；3然后，与20比较，3020所以进入结点20的右子树；4再和35比较，因为3035，所以进入结点35的左子树；5最后与30比较，结果相等，查找结束。所以此查找过程要进行5次比较。11、C解析要把表达式从中缀表达式的形式转换成用后缀表示法表示的等价表达式，必须了解操作符的优先级和结合性。优先级或者说操作符的强度决定求值顺序；优先级高的操作符比优先级低的操作符先求值。如果所有操作符优先级一样，那么求值顺序就取决于它们的结合性。操作符的结合性定义了相同优先级操作符组合的顺序从右至左或从左至右。转换过程包括用下面的算法读入中缀表达式的操作数、操作符和括号1初始化一个空堆栈，将结果字符串变量置空。2从左到右读入中缀表达式，每次一个字符。3如果字符是操作数，将它添加到结果字符串。4如果字符是个操作符，弹出POP操作符，直至遇见开括号OPENINGPARENTHESIS、优先级较低的操作符或者同一优先级的右结合符号。把这个操作符压入PUSH堆栈。5如果字符是个开括号，把它压入堆栈。6如果字符是个闭括号CLOSINGPARENTHESIS，在遇见开括号前，弹出所有操作符，然后把它们添加到结果字符串。7如果到达输入字符串的末尾，弹出所有操作符并添加到结果字符串。12、C13、B解析1队列是一种特殊的线性表，它只允许在表的前端FRONT进行删除操作，而在表的后端REAR进行插入操作。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。队列具有先进先出FIFO的特点。队列空的条件FRONTREAR队列满的条件REARMAXSIZE队列可以用数组Q1M来存储，数组的上界M即是队列所允许的最大容量。在队列的运算中需设两个指针HEAD，队头指针，指向实际队头元素的前一个位置；TALL，队尾指针，指向实际队尾元素所在的位置。一般情况下，两个指针的初值设为0，这时队列为空，没有元素。队列中拥有的元素个数为LTAILHEAD。现在要让排头的元素出队，则需将头指针加1。如果想让一个新元素入队，则需将尾指针向上移动一个位置。2栈是一种只能在叫做栈的一段进行进栈或者出栈操作的线性数据结构。栈的主要特点是“后进先出”，即后进栈的元素先处理。通常栈用顺序表存储，分配一块连续的内存区域存放栈中的元素，并用一个变量指向当前的栈顶。栈的基本操作置空栈INITSTACKS设置一个空栈S。进栈PUSHS,X将元素X进到栈S中，栈指针递增。POPS,X将栈S的栈顶元素赋给X，栈指针递减。判断栈空STACKEMPTYS若栈为空，返回1，否则返回0。根据队列的特点，从队列的输出端依次得到元素C、D、B、A、E，则在从队列的输入端应依次输入元素C、D、B、A、E，则元素的出栈顺序是C、D、B、A、E，由于C是第一个出栈，而C是第三个出栈，所以栈S的容量至少为3。14、C15、B16、A17、D18、B解析本题实际上是考查无向图的邻接表存储方式，以及深度、广度优先遍历。在图的邻接表中，为图的每个顶点建立一个链表，且第I个链表中的结点代表与顶点I相关联的一条边或由顶点I出发的一条弧。有N个顶点的图，需用N个链表表示，这N个链表的头指针通常由顺序线性表存储。第一问是求邻接表所对应的无向图。首先我们看邻接表的第一行链表，在这个链表中，头结点为几后继结点有G、H和M，这表示的是结点G、H、M与结点F直接相连，而题目备选答案B中F和M并不是直接相连的，因此可以排除答案B。再看邻接表的第二行链表，在这个链表中，头结点为G，后继结点有F、I、L、J和K，这表示的是结点F、I、L、J、K与结点G直接相连，而题目备选答案A中G和L并不是直接相连的，所以答案A也可以排除。这样答案也就出来了，1应选C。接下来求深度优先遍历。在图中任选一顶点V为初始出发点源点，则深度优先遍历可定义如下首先访问出发点V，并将其标记为已访问过然后依次从V出发搜索Y的每个邻接点W。若W未曾访问过，则以W为新的出发点继续进行深度优先遍历，直至图中所有和源点V有路径相通的顶点亦称为从源点可达的顶点均已被访问为止。若此时图中仍有未访问的顶点，则另选一个尚未访问的顶点作为新的源点重复上述过程，直至图中所有顶点均已被访问为止。在本题中，以9为源点。首先访问9，然后扫描其邻接表，邻接表的第一个元素是G，且G未被访问过，所以访问G。接下来扫描G的邻接表，G邻接表的第一个元素是F，已经访问过，所以跳过第二个是I，I未被访问过，所以访问结点I。接下来扫描I的邻接表，I的邻接表的第一个元素是G，已经访问过，所以跳过第二个是L，L未被访问过，所以访问结点L，依次类推。最终得到深度优先遍历序列为F、G、I、L、J、K、H、M。所以2应选答案B。求出了深度优先遍历，深度优先遍历的支撑树就好求了。支撑树实际上就是生成树，也就是留下深度优先遍历时经过的边，去除其余的边而得到的树。如图415所示。图415中的实线表示深度优先遍历经过的边，虚线表示不经过的边，把虚线去除，便得到深度优先遍历生成树，如图416所示。接下来求广度优先遍历。广度优先遍历的过程是首先访问出发顶点Y，然后访问与顶点V邻接的全部未被访问过的顶点W0，W1，WK1；接着再依次访问与顶点W0，W1，WK1邻接的全部未被访问过的顶点。依次类推，直至图的所有顶点都被访问到，或出发顶点V所在的连通分量的全部顶点都被访问到为止。在本题中，从F点出发。首先访问F，然后依次访问F邻接表中所有未被访问过的结点G、H、M。接着访问当前邻接表第一个元素所指邻接表的所有未被访问过的元素，即G的邻接表中所有未访问元素I、L、J、K。所以得到广度优先遍历序列F、G，H，M，I，L，J，K。我们可以用同样的方法来求广度优先遍历的生成树，结果如图417所示。把虚线去除得如图418所示的生成树。19、E20、B21、E22、B23、B解析顺序查找的基本思想是从表的一端开始，顺序扫描线性表，依次将扫描到的结点关键字和给定值K相比较。若当前扫描到的结点关键字与K相等，则查找成功；若扫描结束后，仍未找到关键字等于K的结点，则查找失败。顺序查找方法既适用于线性表的顺序存储结构，也适用于线性表的链式存储结构。成功的顺序查找的平均查找长度如下ASLPICINI1NP1N1P22PN1PN在等概率情况下，PI1/N1IN，平均查找长度为N21/NN1/2，即查找成功时的平均比较次数约为表长的一半。若K值不在表中，则需进行N1次比较之后才能确定查找失败。查找时间复杂度为ON。若事先知道表中各结点的查找概率不相等，以及它们的分布情况，则应将表中结点按查找概率由小到大的顺序存放，以便提高顺序查找的效率。顺序查找的优点是算法简单，且对表的结构无任何要求，无论是用向量还是用链表来存放结点，也无论结点之间是否按关键字有序，它都同样适用。缺点是查找效率低，因此，当N较大时不宜采用顺序查找。二分法查找又称折半查找，它是一种效率较高的查找方法。二分法查找要求线性表是有序表，即表中结点按关键字有序，并且要用向量作为表的存储结构。二分法查找的基本思想是设RLOW，HIGH是当前的查找区间1确定该区间的中点位置MIDLOWHIGH/2。2将待查的K值与RMIDKEY比较，若相等，则查找成功并返回此位置，否则需确定新的查找区间，继续二分查找，具体方法如下若RMIDKEYK，则由表的有序性可知RMID，NKEY均大于A，因此若表中存在关键字等于K的结点，则该结点必定是在位置MID左边的子表RLOW，MID1中。因此，新的查找区间是左子表RLOW，HIGH，其中HIGHMID1。若RMIDKEYK，则要查找的K必在MID的右子表RMID1，HIGH中，即新的查找区间是右子表RLOW，HIGH，其中LOWMID1。若RMIDKEYK，则查找成功，算法结束。3下一次查找针对新的查找区间进行，重复步骤1和2。4在查找过程中，LOW逐步增加，而HIGH逐步减少。如果HIGHLOW，则查找失败，算法结束。因此，从初始的查找区间R1，N开始，每经过一次与当前查找区间中点位置上结点关键字的比较，就可确定查找是否成功，不成功则当前的查找区间就缩小一半。重复这一过程，直至找到关键字为K的结点，或者直至当前的查找区间为空即查找失败时为止。查找的时间复杂度为OLOG2N。在二叉排序树上查找，和二分法查找类似，也是一个逐步缩小查找范围的过程。在二叉排序树上进行查找时，若查找成功，则是从根结点出发，走了一条从根到待查结点的路径。若查找不成功，则是从根结点出发，走了一条从根到某个叶子的路径。与二分法查找类似，这种方法中和关键字比较的次数不超过树的深度。二分查找法查找长度为N的有序表，其判定树是唯一的。含有N个结点的二叉排序树却不唯一。对于含有同样一组结点的表，由于结点插入的先后次序不同，所构成的二叉排序树的形态和深度也可能不同，这与在二叉排序树上进行查找时的平均查找长度和二叉树的形态有关。1在最坏的情况下，二叉排序树是通过把一个有序表的N个结点依次插入而生成的，此时所得的二叉排序树退化为一棵深度为N的单支树，它的平均查找长度和单链表上的顺序查找相同，也是N1/2。2在最好的情况下，二叉排序树在生成的过程中，树的形态比较匀称，最终得到的是一棵形态与二分法查找的判定树相似的二叉排序树，此时它的平均查找长度大约是LOG2N。对于平衡的二叉排序树查找，平衡二叉排序树中的每个结点的左、右子树高度差不大于1，N个结点的平衡树的深度和LOG2N是同数量级的。对二叉排序树来说，它的查找时间与树的深度成正比。因此，平衡二叉排序树的平均查找时间为OLOG2N。在平衡树上删除或插入结点往往会破坏树的平衡。通过旋转又可使其重新成为一棵平衡树。在最坏情况下，从叶子开始一直调整到根为止，需进行的旋转次数与树的深度一致，等于OLOG2N次。24、D25、B26、E27、A28、C解析本题比较容易，直接考查各种排序的方法，但从历年试题看来，再考的概率是比较高的。1冒泡排序冒泡排序将被排序的记录数组R1N垂直排列，每个记录RI看做是重量为KI的气泡。根据轻气泡不能在重气泡之下的原则，从下往上扫描数组R凡扫描到违反本原则的轻气泡，就使其向上“飘浮”。如此反复进行，直到最后任何两个气泡都是轻者在上，重者在下为止。冒泡排序的具体过程如下。第一步，先比较K1和K2，若K1K2，则交换K1和K2所在的记录，否则不交换。继续对K2和K3重复上述过程，直到处理完KN1，和KN。这时最大的排序码记录转到了最后位置，称第1次起泡，共执行N1次比较。与第一步类似，从K1和K2开始比较，到KN2和KN1为止，共执行N2次比较，称第2次起泡。依次类推，共做N1次起泡，完成整个排序过程。在本题中，待排序的序列为Q，H，C，Y，P，A，M，S，R，D，F，X，按照上述规则，第一趟冒泡结果为H，C，Q，P，A，M，S，R，D，F，X，Y。2希尔排序希尔SHELL排序的基本思想是先取一个小于N的整数D1作为第一个增量，把文件的全部记录分成D1个组。所有距离为D1的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量D2D1重复上述的分组和排序，直至所取的增量DT1DTDT1D2D1，即所有记录放在同一组中进行直接插入排序为止。该方法实质上是一种分组插入方法。一般取D1N/2，DI1DI/2。如果结果为偶数，则加1，保证DI为奇数。在本题中，待排序的序列为Q，H，C，Y，P，A，M，S，R，D，F，X，规定初始步长D14，则Q，P，R排在一组。这需要对Q，P，R进行排序，排序得P，Q，R，所以P应是序列的首字母。在4个选项中，只有B满足要求。3归并排序归并排序是将MM1个有序子表合并成一个新的有序表。初始时，把含有N个结点的待排序序列看做由N个长度都为1的有序子表所组成，将它们依次M归并得到长度为2的若干有序子表，再对它们M合并。直到得到长度为N的有序表，排序结束。在本题中，待排序的序列为Q，H，C，Y，P，A，M，S，R，D，F，X，规定M2两路归并。把题目中的数据进行分组有Q，H，C，Y，P，A，M，S，R，D，F，X，调整后得H，Q，C，Y，A，P，M，S，D，R，F，X。所以正确答案为E。4快速排序快速排序采用了一种分治的策略，通常称其为分治法。其基本思想是将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题，然后将这些子问题的解组合为原问题的解。快速排序的具体过程如下。第一步，在待排序的N个记录中任取一个记录，以该记录的排序码为准，将所有记录分成两组，第1组各记录的排序码都小于等于该排序码，第2组各记录的排序码都大于该排序码，并把该记录排在这两组中间。第二步，采用同样的方法，对左边的组和右边的组进行排序，直到所有记录都排到相应的位置为止。从上面的介绍中我们知道，对一个序列进行快速排序后有一个非常明显的特征，即“关键字前面的所有元素小于关键字，关键字后面的所有元素大于关键字”。我们往往能以此规则来快速又准确地得到正确答案。在此题中，以序列首字母Q为关键字，我们先看A，此选项满足上述特征。请读者想想分析到此处，我们能否断定A是正确答案呢不能。我们只能说找到不合规则的选项将其排除，最终得到正确答案。一个序列满足上述条件不一定就是快速排序的结果。所以我们继续看B和C在这两个选项中，H比Q小，但在Q后面，不正确。D和E两个选项中A在Q的后面，显然不正确，所以答案应选A。5堆排序有关堆的定义和性质，请读者参考第2题的分析。堆排序的关键步骤有两个一是如何建立初始堆二是当堆的根结点与堆的最后一个结点交换后，如何对少了一个结点后的结点序列做调整，使之重新成为堆。在本题中，只要求建立初始堆，我们可以按照412节的方法，判断给定的5个选项中，哪个选项满足堆的定义就可以了，在此不再重复。29、B30、D31、B32、C33、F解析本题是对排序算法的时间复杂度和空间复杂度进行比较分析，下面给出比较分析表，如表41所示。表41常用排序算法的比较表排序方法最好情况平均时间最坏情况辅助空间直接插入排序ONON2ON2O1简单选择排序ON2ON2ON2O1冒泡排序ONON2ON2O1快速排序ONLOG2NONLOG2NON2ONLOG2N堆排序ONLOG2NONLOG2NONLOG2NO1归并排序ONLOG2NONLOG2NONLOG2NON基数排序ODNRDODNRDODNRDONRD根据表41，可直接得到本题的答案。读者需要对表41进行理解，能够自己推导出有关复杂性结果，或者进行记忆。34、I35、G36、E37、B38、D解析解答本题最关键的一步是要构造出与题目对应的二叉树，可以利用的条件有4个二叉排序树、顺序存放、根结点P，以及存储结构图中出现的结点关键字。构造树的过程是这样的首先画出根结点P，然后在存储结构图413中找出下一个结点关键字B因为题目告诉我们，二叉排序树是顺序存放在一组物理上相邻的存储区中的，由于BP，所以B以左子结点的身份加入排序二叉树；接着从结构图中找下一个结点关键字Q，QP，所以Q以右子结点的身份加入排序二叉树。接下来的结点是H，因为HP，则H在P的左子树中，又因为HB，所以H最终作为B的右子树。再下一个结点是巴同理，因为CP，CB，CH，则C最终作为H的左子树。最后一个结点是J，JP，JB，JH，则J最终作为H的右子树。得到的二叉排序树如图419所示。由图419可得出，L2指向NULL；L4指向巴即100C；R1指向Q，即1006；该二叉排序树的前序遍历序列为PBHCJQ，后序遍历序列为CJHBQP。39、B40、A41、A42、B43、D解析本题主要考查一些特殊图的概念，下面分别进行介绍。非简单图既无平行边也无环的无向图称为简单无向图，有平行边或有环的图是非简单图。在本题中，只有B有环，其余的5个图都既无平行边也无环，因而26的答案应为B。完全图每个顶点度数都等于N1的N阶无向简单图称为N阶无向完全图，并记为KN。在给定的6个图中，只有A图满足要求，它是K5，所以27的答案为A。哈密尔顿图通过连通图中所有结点一次且仅一次的回路称为哈密尔顿回路，具有哈密尔顿回路的图称为哈密尔顿图。一个图是哈密尔顿图的必要条件注意不是充分条件是图的连通性和图中不存在度数为1的顶点。在本题中，E图是分离的K3，即E是非连通图，而C、D、F均有度数为1的顶点，所以C、D、E、F都不是哈密尔顿图。A、B中均存在哈密尔顿回路，因而A、B均为哈密尔顿图。所以28、29的答案可以为A、B。欧拉图通过连通图有向图或无向图中每条边一次且仅一次遍历图中所有顶点的回路，称为欧拉回路，存在欧拉回路的图称为欧拉图。设G是连通图，则G是欧拉图，当且仅当G的所有顶点都是偶顶点度数为偶数的顶点。在本题中，只有A连通且无奇度顶点，因而A为欧拉图，在其余各图中，E无奇度顶点，但它不连通，所以不是欧拉图。而B、C、D、F中都有奇度顶点，因而它们也不是欧拉图，所以28的答案为A，29的答案为B。树连通且无回路的无向图称为无向树。在本题中，只有D满足要求，其余5个图中均有回路，因而都不是树，30的答案为D。另外，还有一些特殊的图，我们也简单介绍一下。平面图平面图是指一个图能画在平面上，除顶点之外，再没有边与边相交。在本题中，B、C、D、F为平面图。二部图若能将无向图的顶点集V划分成两个子集V1和V2，使得G中任何一条边的两个端点一个属于V1，另一个属于V2，则称G为二部图也称为偶图。在本题中，D为二部图。44、A45、B46、B47、A48、B解析题目第一问是求原题所给数据结构表示的图。我们可以先在纸上画出V1V8这8个顶点，然后看边关系召，召集合的第一个元素是V1，V2，这表示在V1和V2之间有一条边，如图420所示。接下来是V3，V4，所以在V3和V4之间也有一条边，如图421所示。依次类推，最后得到的图形与A一致，所以31应选答案A。图A显然是一个无向图，所以32应选答案B。图的存储结构主要有邻接表和邻接矩阵，若用邻接表来存储一个图，则需要保存一个顺序存储结点表和若干个链接存储关系表。请读者参考本节练习1的分析。49、A50、B51、C52、B53、C解析由于二叉树的前序、中序和后序遍历方法都是递归定义的，所以最适合采用递归程序来实现。此外，递归程序的实现基础是栈操作，所以二叉树的遍历也可以使用栈操作来完成，但是用栈操作来实现遍历的程序逻辑结构没有递归程序那么清晰，而且用栈来实现的二叉树遍历代码比较难懂，其优点是代码的机器执行效率较高。在查找二叉树中，由根结点到所有其他结点的路径长度总和称为内部路径长度。具有最小内部路径长度的树称为丰满树，对丰满查找树进行插入或者删除操作后，会产生一棵非丰满树。为了保证查找二叉树的高度为LOG2N，从而保证在查找二叉树上实现的插入、删除和查找等基本操作的平均时间为OLOG2N，往树中插入或删除结点时，要调整树的形态来保持树的“平衡”，使之既保持查找二叉树性质不变，又保证树的高度在任何情况下均为OLOG2N，从而确保树上的基本操作在最坏情况下的时间均为OLOG2N。平衡二叉树是指树中任一结点的左、右子树的高度大致相同，即平衡树上任一结点的左、右子树仍然保持平衡。平衡树的查找效率和丰满树相近，但是在插入或者删除结点时，平衡树能动态地调整保持平衡的特点。如果任一结点的左、右子树的高度均相同如满二叉树，则二叉树是完全平衡的。通常，只要二叉树的高度为OLOG2N，就可看做是平衡的。平衡二叉树中任一结点的左、右子树的高度之差的绝对值不超过1。在最坏情况下，N个结点的平衡二叉树的高度约为144LOG2N。而完全平衡的二叉树高度约为LOG2N，平衡二叉树是接近最优的。根据丰满树和平衡树的定义可知，丰满树一定是平衡树，但平衡树不一定是丰满树。M阶B树是一种平衡的M叉树，具有如下的性质1每个结点的后件孩子个数不大于M。2除根结点和叶子结点外，每个结点的后件个数不大于。3具有K个后件的非叶子结点含有K1个键值。4所有叶子结点在同一层上，而且不包含任何关键字信息，不附有信息。54、D55、A56、B57、A58、B解析本题的出题方式比较新颖，很多考生在求第一空时就不知如何动手，因为他们都只看到了条件“根结点为E”。但未挖掘“查找二叉树”给出的隐含条件。实际上此题最主要的条件就是“查找二叉树”。查找二叉树中每一个结点的左子树结点关键值小于结点本身，而右子树结点大于结点本身。题目中又给出条件“根结点为召”，所以比E小的结点A，B，C，D都是E的左子树结点，而F是右子树结点，又因为前序遍历顺序为根、左、右，所以前序遍历的第一个结点是E，最后一个结点是F。在41的4个选项中，只有D才满足此条件。既然已经知道前序遍历序列为EACBDF，且知道二叉树的左子树是ACBD，再根据前序遍历的性质和A是左子树的根结点，可知C，召，D均是A结点下的右子树A的左子树为空。同理，B和D分别是C的左子树和右子树。最后所得的二叉树如图422所示。根据图422，我们立即可得该二叉树的层次遍历序列为EAFCBD。根据试题条件，结点A，B，C，D，E，F依次存放，且每个结点占4个字节前2个字节存放结点值，后2个字节依次放左指针、右指针，所以C的起始地址为N8，LC的地址为N10。根据图423所示，LC中应存放B的地址，由于起始地址为N，因此B的地址为N4，LC的内容是N4。结点A的右指针RA中应存放C的地址，而C的地址为N8，即RA的内容是N8。另外，我们也可以参考练习5的分析，来解答这道试题。59、B60、A解析给定一个序列的集合，若不存在一个序列是另一个序列的前缀，则该序列集合称为前缀码。相反，给定一个序列的集合，若不存在一个序列是另一个序列的后缀，则该序列集合称为后缀码。平均码长或文件总长最小的前缀编码称为最优的前缀码，最优的前缀码对文件的压缩效果亦最佳。利用哈夫曼树很容易求出给定字符集及其概率或频度分布的最优前缀码。哈夫曼编码是一种应用广泛且非常有效的数据压缩技术，该技术一般可将数据文件压缩掉20至90，其压缩效率取决于被压缩文件的特征。在构造哈夫曼树的过程中，每次都是选取两棵最小权值的二叉树进行合并，因此使用的是贪心算法。哈夫曼树的具体构造过程如下假设有N个权值，则构造出的哈夫曼树有N个叶子结点。N个权值分别设为W1，W2，WN，则哈夫曼树的构造规则为1将W1，W2，WN看成是有N棵树的森林每棵树仅有一个结点；2在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和；3从森林中