《数据结构》习题

数据结构习题一、单项选择题1对矩阵进行压缩存储是为了（）A节省存储空间B提高运算速度C便于运算D方便存储2链式栈与顺序栈相比，一个比较明显的优点是（）A插入操作更加方便B通常不会出现栈满的情况C不会出现栈空的情况D删除操作更加方便3设输入序列为1，2，3，4，5，则借助一个队列可以得到的输出序列是（）A3，4，1，2，5B1，2，3，4，5C2，3，4，1，5D5，4，3，2，14一个栈的输入序列是6,5,4,3,2,1,可能的输出序列是（）A4,3,2,1,5,6B3,6,2,1,5,4C1,2,3,5,4,6D5,4,1,3,2,65设输入序列为A，B，C，D。借助一个栈可以得到的输出序列是（）AA，C，D，BBC，A，D，BCD，C，A，BDD，A，B，C6将含100个结点的完全二叉树从根开始，每层从左到右依次对结点编号，根结点的编号为1，则编号为71的结点的双亲结点的编号为（）A34B35C36D无法确定7已知完全二叉树有80个结点，则该二叉树有（）个度为1的结点。A0B1C2D不确定8任何一个无向连通图的最小生成树（）A只有一棵B有一棵或多棵C一定有多棵D可能不存在9设图G用邻接表存储，对该图进行深度优先搜索遍历，则算法的时间复杂度为（）AONBONECON2DON310用N个键值构造一棵二叉排序树，最低高度为（）AN/2BNC2ND2N111如果以链表作为栈的存储结构，则执行出栈操作时（）A必须判断栈是否满B必须判断栈是否空C判断栈元素的类型D对栈不作任何判断12设数组DATAM作为循环队列SQ的存储空间，FRONT为队头指针，REAR为队尾指针，则执行出队操作的语句为（）AFRONTFRONT1BFRONTFRONT1MCREARREAR1MDFRONTFRONT1M113线性表的长度是指（）A顺序存储方式下数组所占用的元素个数B链表存储方式下的结点个数C表中的元素个数D所能存储的最大的结点个数14设有一个无向图GV，E和GV，E，如果G是G的生成树，则下面不正确的说法是（）AG为G的子图BG为G的连通分量CG为G的极小连通子图且VVDG是G的一个无环子图15在采用线性探测法处理冲突所构成的闭散列表上进行查找，可能要探测多个位置，在查找成功的情况下，所探测的这些位置上的键值（）A一定都是同义词B一定都不是同义词C都相同D不一定都是同义词16在有序表A20中按二分查找方法查找A13依次比较的元素的下标是（）A9，14，12，13B9，15，12，13C9，14，11，12，13D10，15，12，1317栈和队列都是（）A顺序存储的线性表B链式存储的线性表C限制的线性表D限制存储点的非线性结构18向顺序栈中压入新元素时，应当（）A先移动栈顶指针，再存入元素B先存入元素，再移动栈顶指针C先后次序无关紧要D同时进行19若树的先序序列和中序序列正好相同，则一定是一棵（）的二叉树。A结点个数可能大于1且该树无左子树B结点个数可能大于1且根结点无左孩子C结点个数可能大于1且各结点均无左孩子D其中任意一个结点的度不为220下列算法中，在第一趟排序之后，一定能把数据表中最大或最小元素放在其最终位置上的算法是A归并排序B直接插入排序C快速排序D冒泡排序21当初始序列已经按键值有序时，用直接插入算法进行排序，需要比较元素的次数为（）AN2BN2NC2NDN122下列排序算法中，在最好情况下，时间复杂度为ON的算法是（）A直接选择排序B归并排序C快速排序D冒泡排序23下列排序方法中，排序所花费时间不受数据初始排列特性影响的算法是（）A直接插入排序B冒泡排序C直接选择排序D快速排序24对待排序的元素序列进行划分，将其分为左、右两个子序列，再对两个子序列施加同样的排序操作，直到子序列为空或只剩一个元素为止。这样的排序方法是（）A直接选择排序B直接插入排序C快速排序D起泡排序25对5个不同的数据元素进行直接插入排序，最多需要进行（）次比较。A8B10C15D2526在一个具有N个结点的双链表中插入一个新结点,则该操作的时间复杂性的量级为（）AO1BONCONLOG2NDON227二分查找法要求被查找的表是（）A顺序表B分块有序表C顺序表且是按键值递增或递减次序排列D不受上述任何限制28若某线性表中最常用的操作是在最后一个元素之后插人一个元素和删除第1个元素，则采用（）存储方式最节省运算时间。A单链表B仅有头指针的单循环链表C仅有尾指针的单循环链表D双链表29在一个顺序存储的循环队列中，队头指针指向队头元素的（）A前一个位置B后一个位置C队头元素位置D队尾元素的前一个位置30设循环队列用数组AN存储，头尾指针为FRONT和REAR,求解当前队列中元素个数的公式AREARFRONTBFRONTREARCNFRONTREARDNREARFRONTN31已知完全二叉树有100个结点，则该完全二叉树共有（）个叶子结点。A37B49C50D不确定32下列存储形式中，（）不是树的存储形式。A双亲表示法B左子女右兄弟表示法C广义表表示法D顺序表示法33在一棵具有5层的满二叉树中结点总数为（）A31B32C33D1634设有100个数据元素，采用折半搜索时，最大比较次数为（）A6B7C8D1035在顺序存储的线性表A1,A2,AN中,删除任意一个结点时所需移动结点的平均次数为（）ANBN/2CN1/2DN1/236下列说法不正确的是（）A数据元素是数据的基本单位B数据项是数据中不可分割的最小标识单位C数据可由若干个数据元素构成D数据项可由若干个数据元素构成37为了方便在线性结构的数据中插入一个数据元素,则其数据结构宜采用（）方式A顺序存储B链式存储C索引存储D散列存储38矩阵A56的每个元素占5个单元，将其按行优先次序存储在起始地址为1000的连续的内存单元中，则元素A55的地址为（）A1120B1125C1140D114539设矩阵AAIJ，0I,J9的元素满足AIJ0IJ,0I,J9AIJ0IT1R1ST1SR1T1SR1BST1R1SR1SR1T1ST1CSR1ST1R1ST1SRT1DST1ST1R1SR1SRT166假设LEFT和RIGHT为双向链表中指向直接前趋结点和直接后继结点的指针域，现要把一个指针S所指的新结点作为非空双链表中Q所指地点中间结点的直接后继结点插入到该双向链表中，则下列算法段能正确完成上述要求的是AQRIGHTSSLEFTQQRIGHTLEFTSSRIGHTQRIGHTBSLEFTQQRIGHTSQRIGHTLEFTSSRIGHTQRIGHTCSLEFTQSRIGHTQRIGHTQRIGHTLEFTSQRIGHTSD以上都不对67已知一个稀疏矩阵的三元组表如下1，2，3，1，6，1，3，1，5，3，2，1，4，5，4，5，1，3，则其转置矩阵的三元组表中第3个三元组为A2，1，3B3，1，5C3，2，1D2，3，168顺序查找法与二分查找法对存储结构的要求是A顺序查找与二分查找均只适用于顺序表B顺序查找只适用于顺序表C顺序查找与二分查找既适用于顺序表，也适用于链表D二分查找只适用于顺序表69程序段FORI0INEXTBPNEXTPNEXTNEXTCPNEXTPDPPNEXTNEXT71在头指针为HEAD且表长大于1的单循环链表中，若指针PNEXTNEXTHEAD,则AP指向头结点BP指向尾结点CP的直接后继是头结点DP的直接后继是尾结点72广义表AA,B,C,D,E的长度为A4B5C6D773无向图中一个顶点的度是指图中A通过该顶点的简单路径数B与该顶点相邻接的顶点数C通过该顶点的回路数D与该顶点连通的顶点数74已知一个图如下所示，从顶点A出发进行广度优先遍历可能得到的序列为AACEFBDBACBDFECACBDEFDACDBFE75设顺序存储的线性表共有123个元素，按分块查找的要求等分成3块。若对索引表采用顺序查找来确定块，并在确定的块中进行顺序查找，则在查找概率相等的情况下，分块查找成功时的平均查找长度为A21B23C41D6276下面的二叉树中，不是完全二叉树。77下列说法错误的是。A一个图的邻接矩阵表示是唯一的B一个图的邻接表表示是不唯一的C一个图的生成树必为该图的极小连通子图D一个无环有向图的拓扑排序序列必唯一78设有6个结点的无向图，该图至少应有条边才能确保是一个连通图。A5B6C7D879二叉树在线索化后，仍不能有效求解的问题是A先序线索二叉树中求先序后继B中序线索二叉树中求中序后继C中序线索二叉树中求中序前趋D后序线索二叉树中求后序后继80数据表A中有10000个元素，如果仅要求求出其中最大的10个元素，则采用排序算法最节省时间。A堆排序B希尔排序C快速排序D直接选择排序81若给定有N个元素的向量，则建立一个有序单向链表的时间复杂性的量级是AO1BONCON2DONLOG2N82在一个具有N个结点的单链表中查找值为M的某结点，若查找成功，则平均比较个结点。ANBN2CN12DN1283研究数据结构就是研究A数据的逻辑结构B数据的存储结构C数据的逻辑结构和存储结构D数据的逻辑结构、存储结构及其数据在运算上的实现84设有13个值，用它们组成一棵哈夫曼树，则该哈夫曼树中共有个结点。A13B12C26D2585下列四种排序方法中，不稳定的方法是（）A直接插入排序B冒泡排序C归并排序D直接选择排序86下列说法中不正确的是A无向图中的极大连通子图称为连通分量B连通图的广度优先搜索中一般要采用队列来暂存刚访问过的顶点C图的深度优先搜索中一般要采用栈来暂存刚访问过的顶点D有向图的遍历不可采用广度优先搜索方法87下列说法中不正确的是（）A图的遍历过程中每一顶点仅被访问一次B遍历图的基本方法有深度优先搜索和广度优先搜索两种C图的深度优先搜索的方法不适用于有向图D图的深度优先搜索是一个递归过程88对有序表18，20，25，34，48，62，74，85用二分查找法查找85，所需的比较次数为A1次B2次C3次D4次89散列表的平均查找长度A与处理冲突方法有关而与表的长度无关B与处理冲突方法无关而与表的长度有关C与处理冲突方法有关且与表的长度有关D与处理冲突方法无关且与表的长度无关90若结点的存储地址与其关键字之间存在某种映射关系，则称这种存储结构为A顺序存储结构B链式存储结构C索引存储结构D散列存储结构91若进栈序列为A,B,C，则通过入出栈操作可能得到的A,B,C的不同排列个数为A4B5C6D792三维数组A456按行优先存储方法存储在内存中，若每个元素占2个存储单元，且数组中第一个元素的存储地址为120，则元素A45的存储地址为A356B358C360D36293下列陈述中正确的是A二叉树是度为2的有序树B二叉树中结点只有一个孩子时无左右之分C二叉树中必有度为2的结点D二叉树中最多只有两棵子树，并且有左右之分94N个顶点的有向完全图中含有向边的数目最多为AN1BNCNN1/2DNN195设有一个含200个表项的散列表，用线性探查法解决冲突，按关键码查询时找到一个表项的平均探查次数不超过15，则散列存储空间应能够至少容纳（）个表项。（设搜索成功的平均搜索长度为SNL11/1A/2,其中A为装填因子）A400B526C624D67696在有向图中每个顶点的度等于该顶点的（）A入度B出度C入度与出度之和D入度与出度之差97一个二叉树按顺序方式存储在一维数组中，如图则结点E在二叉树的第（）层。0123456789101112131415ABCDEFGHIJA1B2C3D498设某线性链表的头结点指针为L,LDATA表示该链表的结点个数，LNEXT指向该链表的第一个结点，P指向新建立的结点，其类型与L相同。在建立该链表的过程中，若希望LNEXT始终指向新输入的结点，可采用如下的C语言语句实现（）APNEXTLNEXT,LNEXTP，LDATABPNEXTNULL,LNEXTP,LDATACLDATA,LNEXTPNEXT,PNEXTLD以上都不是。99以数组Q0M1存放循环队列中的元素，变量REAR和QULEN分别指示循环队列中队尾元素的实际位置和当前队列中元素的个数，队列第一个元素的实际位置是（）AREARQULENBREARQULENMCMQULEND1（REARMQULEN）M100设结点X和结点Y是二叉树T中的任意两个结点，若在先根序列中X在Y之前，而在后根序列中X在Y之后，则X和Y的关系是（）AX是Y的左兄弟BX是Y的右兄弟CX是Y的祖先DX是Y的后代101对线性表进行二分查找时，要求线性表必须。A以顺序方式存储B以链接方式存储C以顺序方式存储，且结点按关键字有序排序D以链接方式存储，且结点按关键字有序排序二、判断题若正确在内打，否则打。1对链表执行插入和删除操作时，不必移动结点。2双链表中只有一个结点的后继指针为空。3数据的逻辑结构是指各数据元素之间的逻辑关系，是用户按使用需要建立的。4线性表的逻辑顺序与物理顺序总是一致的。5线性表的顺序存储表示优于链式存储表示。6栈是实现函数调用的必不可少的数据结构。7线性表的长度是线性表所占用的存储空间的大小。8在带头结点的单链表中插入元素结点不会改变头指针的值。9对链队列执行出队操作不会改变尾指针的值。10树或森林转化为对应的二叉树后，两者的分支数相等。11由给定的N个权值所构造的哈夫曼树可能不唯一，其结点个数也可能不确定。12图中一个顶点I的出度等于其邻接矩阵中第I列的非0元素个数。13二叉树是树的特殊情形。14所谓冲突即是两个关键字的值不同的元素，其散列地址相同。15二叉树的先序序列和后序序列正好相反。16在循环队列中，若尾指针REAR大于头指针FRONT，则其元素总数为REARFRONT17一个有向图的邻接表和逆邻接表中的结点个数一定相等。18在编号的完全二叉树中根结点的编号为1，编号为100的结点一定在其左子树中。19在索引顺序表的查找中，对索引表的查找既可采用顺序查找法，也可采用二分查找法。20对同一组键值的不同顺序的输入序列，所构造的二叉排序树一定不同。21稀疏矩阵只能用三元组表压缩存储。22在一个大根堆中，关键字最大的两个元素一定在数据表的前三个元素中。23线性表采用链表存储后，线性表的长度等于链表中的结点个数24双循环链表中，任一结点的前趋指针均指向其逻辑前趋。25如果一棵二叉树的中序序列是递增有序序列，则一定是一棵二叉排序树。26对一个有序表作二分查找，查找每个元素所需的查找次数均比用顺序查找所需的查找次数要少。27对有N个元素的数据表用直接选择排序方法进行排序，最好情况下所需的时间复杂度是ON。28快速排序算法是所有排序算法中时间复杂度最好的一种排序算法。29顺序表用一维数组作为存储结构，因此顺序表是一维数组。30通常使用两个类来协同表示单链表，即链表的结点类和链表类。31具有N个结点的完全二叉树的高度为LOG2N1。（N0，根结点在第0层）32闭散列法通常比开散列法时间效率更高。33已知指针P指向单链表L中的某结点，执行语句PPNEXT不会删除该链表中的结点。34在链队列中，即使不设置尾指针也能进行入队操作。35如果一个串中的所有字符均在另一串中出现，则说前者是后者的子串。36数据的逻辑结构与数据元素本身的内容和形式无关。37从逻辑关系上讲，数据结构主要分为两大类线性结构和非线性结构。38由于希尔排序的最后一趟与直接插入排序过程相同，因此前者一定比后者花费的时间多。39数据的基本单位是数据项。40带权的无向连通图的最小生成树是唯一的。41用邻接矩阵法存储一个图所需的存储单元数目与图的边数有关。42在霍夫曼编码中，当两个字符出现的频率相同时，其编码也相同，对于这种情况应当特殊处理。43线性表采用顺序存储表示时，必须占用一片连续的存储单元。44装载因子是散列表的一个重要参数，它反映了散列表的装满程度。45算法和程序没有区别，所以在数据结构中二者是通用的。46在顺序表中无需为表示结点间的逻辑关系而增加存储空间。47单链表中的头结点就是单链表的第一个结点。48队列和栈都是运算受限的线性表。49任何一棵二叉树中至少有一个结点的度为2。50对于N个记录的集合进行冒泡排序，所需要的平均时间是0N。51一棵哈夫曼树中不存在度为1的结点。52二叉树中的叶子结点就是二叉树中没有左右子树的结点。53一棵树中的叶子结点数一定等于与其对应的二叉树中的叶子结点数。54由二叉树结点的先根序列和后根序列可以唯一地确定一棵二叉树。55在用循环单链表表示的链式队列中，可以不设队头指针，仅在链尾设置队尾指针。56一个广义表的表尾总是一个广义表。57对于一棵具有N个结点，其高度为H的二叉树，进行任一种次序的遍历的时间复杂度为OH。58数据结构是数据对象与对象中数据元素之间关系的集合。59所谓数据的逻辑结构是指数据元素之间的逻辑关系。60二维数组是其数组元素为一维数组的线性表，因此它是线性结构。61若图G的最小生成树不唯一，则G的边数一定多于N1，并且权值最小的边有多条（其中N为G的顶点数）。62用直接选择排序方法分别对序列S1（1，2，3，4，5，6）和序列S2（5，3，2，4，1，6）进行排序，两者的比较次数不相同。63用二分查找法对一个顺序表进行查找，这个顺序表可以是按各键值排好序的，也可以是没有按键值排好序的。64当从一个小根堆（最小堆）中删除一个元素时，需要把堆尾元素填补到堆顶位置，然后再按条件把它逐层向下调整，直到调整到合适位置为止。65同一数据逻辑结构中的所有数据元素都具有相同的特性是指数据元素所包含的数据项的个数都相等。66若有一个结点是二叉树中某个子树的中序遍历结果序列的最后一个结点，则它一定是该子树的前序遍历结果的最后一个结点。67如果二叉树中每个结点的值都大于其左孩子结点的值、小于其右孩子结点的值，则可断定它是二叉排序树。68在循环队列中，FRONT指向队列中第1个元素的前一位置，REAR指向实际的队尾元素，则队列为满的条件是FRONTREAR。69在用线性探测法解决冲突所构造的闭散列表中，每组同义词中至少有一个元素的地址正好等于其散列地址。70设与一棵树T所对应的二叉树为BT，则与T中的叶子结点所对应的BT中的结点也一定是叶子结点。71对有向图G，如果从任一顶点出发进行一次深度优先或广度优先搜索能访问到每个顶点，则该图一定是有向完全图。72若一个栈的输入序列为123N，其输出序列的第一个元素为N，则其输出序列的每个元素AI一定满足AINI1I1,2,N三、填空题1双循环链表中，在指针P所指结点前插入指针S所指的结点，应执行下列语句SNEXTP；SPRIOR；PPRIORS；2在有N个叶子结点的哈夫曼树中，结点总数是3已知完全二叉树的第六层有5个结点，则其叶子结点的个数是4栈的特性是，队列的特性是5有N个顶点的有向图最多有条弧。6在有N个元素的待排序序列已经有序的情况下，用冒泡排序算法进行排序，所作的比较元素的次数为，交换元素的次数为7单循环链表L为空的条件是8带头结点的双循环链表为空表的条件是9设指针R指向单链表的最后一个结点，要在最后一个结点之后插入指针S所指的结点，需执行的三条语句是；RS；RNEXTNULL；10在单链表中，若要删除指针P所指结点的后继结点，则需执行下列三条语句UPNEXT；FREEU；11设链队列的队头指针为FRONT，队尾指针为REAR，队列为空的条件是12已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点，则该树中有个叶子结点。13已知一棵二叉树中有10个叶子结点，有15个结点仅有左孩子结点，20个结点仅有右孩子结点，则整个二叉树有个结点。14有N个顶点的连通图的生成树有条边。15设有一个链栈，结点中有DATA和NEXT两个字段，栈顶指针LS不空，则结点S入栈操作的语句为LSNEXTS；LS；16一棵二叉树的先序序列和后序序列正好相反的条件是17一棵二叉排序树中若有14个结点的查找长度4，则有个结点的查找长度3。18在对有12个元素的有序表做二分查找时，有个结点的查找长度是4。19栈可看成是一种运算受限制的线性表,其中可以进行插入和删除的一端称为20设链队列1Q中结点的格式为DATANEXT,头指针为1QFRONT，尾指针为1QREAR,队列为空的条件是。21无向图中的极大连通子图称为该无向图的22闭散列表中通常采用构造后继散列以减少堆积。23算法的时间复杂度取决于_24设一棵二叉树结点的先根序列为ABDECFGH，中根序列为DEBAFCHG，则二叉树中叶子结点是_25N个顶点的无向连通图用邻接矩阵表示时,该矩阵至少有_个非零元素26取出广义表AX,A,B,C,D中原子A的函数是27在线性表的单链表达式存储中，若一个元素所在结点的地址为P，则其后继结点的地址为，若假定P为一个数组A中的下标，则其后继结点的下标的。28对于一个具有N个顶点和E条边的连通图，其生成树中的顶点数和边数分别为和。29二分查找过程所对应的判定树既是一棵，又是一棵。30若长度N10000的线性表进行二级索引存储每级索引表中的索引项是下一级20个记录的索引，则一级索引表的长度为，二级索引表的长度为。31设数组B14,15中的任一元素均占3个单元，从首地址SB开始把数组B按行优先存储，则元素B3,4的地址为_。32在N个结点的线索二叉链表中，有_个线索指针。33在对有10个数据的有序表作二分查找时，有_个结点的查找长度是4。34在开散列表上查找键值等于K的结点，首先必须计算该键值的_,然后再通过指针查找该结点。35对静态表顺序查找算法采用设置岗哨方式与普通的设置循环控制变量相比，进行一次查找所花费的平均时间大约减少_。36若要对某二叉排序树进行遍历，保证输出的所有结点键值序列按递增次序排列，应对该二叉树采用_遍历法。37设需将一组数据按升序排序。在无序区中依次比较相邻两个元素AI和AI1的值，若AI的值大于AI1的值，则交换AI和AI1。如此反复，直到某一趟中没有记录需要交换为止，该排序方法被称为_。38在队列中，允许进行插入操作的一端称为_，允许进行删除操作的一端称为_。39如图两个栈共享一个向量空间，TOP1和TOP分别为指向两个栈顶元素的指针，则“栈满”的判定条件是_。40如果在排序前，关键字序列已接近正序，则在堆排序和快速排序两者之中，选用_较为适当。41通常从四个方面评价算法的质量_、_、_和_。42在具有N个单元的循环队列中，队满时共有_个元素。43矩阵压缩存储的基本思想是_的多个元素只分配一个存储空间，_不分配空间。44深度为K的完全二叉树至少有_个结点，至多有_个结点。45图的主要存储结构有两种，分别为_和_。46直接插入排序需要_个记录的辅助空间。47在插入和选择排序中，若初始数据基本正序，则选用_；若初始数据基本反序，则选用_48一棵树采用二叉链表存储，如果树中某结点为叶子结点，则在二叉链表BT中所对应的结点一定是49在有N个结点的无向图中，其边数最多为_。50对广义表AX,A,B,C,D的运算HEADHEADTAILA的结果是_。51假设哈希表的表长为M，哈希函数为HKEY，若用线性探查法解决冲突，则探查地址序列的形式表达为_。52判断线索二叉树中某结点指针P所指结点有左孩子的条件是53设链栈的栈顶指针为LS，栈不空的条件为_54遍历图的基本方法有深度优先搜索和广度优先搜索。其中，_是一个递归过程。55对于二叉排序树的查找，若根结点元素的键值大于被查找元素的键值，则应该在该二叉树的_上继续查找。56采用二次探测法解决冲突问题，对于键值为K、容量为M的闭散列表，若散列地址为D0，则发生冲突后，其第三个后继散列地址D3为_。57对一组记录54，38，96，23，15，72，60，45，83进行直接插入排序时，当把第7个记录60插入到已排序的有序表时，为寻找其插入位置需比较_次。58一棵哈夫曼树有19个结点，则其叶子结点的个数是_。59假设以S和X分别表示进栈和退栈操作，则对输入序列A,B,C,D,E进行一系列栈操作SSXSXSSXXX之后，得到的输出序列为_。60假设一个10阶的下三角矩阵A按列优先顺序压缩存储在一维数组C中，则C数组的大小应为_61若采用邻接矩阵结构存储具有N个顶点的图，则对该图进行广度优先遍历的算法时间复杂度为_62对关键字序列52，80，63，44，48，91进行一趟快速排序之后得到的结果为63由10000个结点构成的二叉排序树，在等概率查找的假设下，查找成功时的平均查找长度的最大值可能达到_03281A64已知某稀疏矩阵为，可用三元组的形式表示该稀疏矩阵为65已知某二叉树的叶子结点的个数为10个，度为1的结点个数为8个，则该二叉树的结点总数为个。具有这种特点的所有二叉树中，其最大深度为，其最小深度。66已知某二叉树先序遍历的结果为ABDEFGCHIJ，其中序遍历的结果为DBFGEAHCJI，则其后序遍历的结果为。67线性表L（A1，A2，AN）采用顺序存储，假定在不同的N1个位置上插入的概率相同，则插入一个新元素平均需要移动的元素个数是_。68设栈S和队列Q的初始状态皆为空，元素A1，A2，A3，A4，A5和A6依次通过一个栈，一个元素出栈后即进入队列Q，若6个元素出队列的顺序是A3，A5，A4，A6，A2，A1则栈S至少应该容纳_个元素。69两个序列L125，57，48，37，92，86，12，33L225，37，33，12，48，57，86，92用冒泡排序方法分别对序列L1和L2进行排序，交换次序较少的是序列_。四、解答下列各题1采用直接插入排序算法，对关键字序列（46,32,55,81,65,11,25,43）按从小到大的次序进行排序，写出每趟排序的结果。2设待排序序列为10，18，4，3，6，12，1，9，15，8，请给出用希尔排序每一趟的结果。增量序列取为5，3，2，1。3对数据表25，50，70，21，4，18，100，43，7，12采用快速排序算法进行排序，写出每趟的结果。4已知序列15,18,60,41,6,32,83,75,95,请给出采用冒泡排序法对该序列作升序排序时每一趟的结果。5对数据列50，72，31，80，60，20，96，14写出采用直接选择排序算法排序的每一趟排序的结果。6已知二叉树的先序、中序序列分别如下，构造出该二叉树。先序序列ABCDEFGHIJK中序序列CBEDAHIGFJK7已知一棵二叉树的中序序列和后序序列如下，构造出该二叉树。中序序列HDIBJEAFCG后序序列HIDJEBFGCA8已知二叉树的先序、中序和后序序列分别如下，但其中有一些已模糊不清。请构造出该二叉树先序序列BCEGH中序序列CDAGHF后序序列DBFEA9已知二叉树的先序、中序和后序序列分别如下，但其中有一些已模糊不清，构造出该二叉树先序序列_BC_EF_中序序列BDE_AG_H后序序列_DC_GH_A10以3，4，5，8，12，18，20，30为叶子结点的权值，构造一棵哈夫曼树，并计算其带权路径长度。11求出满足下列条件的所有二叉树。A其先序序列为ABCDE。B高度为5，而与其对应的树森林的高度为4。12某二叉树的结点数据采用顺序存储表示如下01234567891011121314151617181920EAFDHCGIB1试画出此二叉树的图形表示。2写出结点D的双亲结点及左右子女。3将此二叉树看作森林的二叉树表示，试将它还原为森林。13对下面的带权无向图从顶点开始采用PRIM算法和KRUSKAL算法构造最小生成树。14设散列函数HKK7，采用拉链法处理冲突，对下面输入序列；要求构造出该散列表，并求出在等概率情况下成功的平均查找长度。输入序列100，90，120，60，78，35，42，31，15，20，22，12，16，2415设散列表为HT17，待插入关键码序列为JAN,FEB,MAR,APR,MAY,JUNE,JULY,AUG,SEP,OCT,NOV,DEC，散列函数为HKEYI/2向下取整，其中I是关键码第一个字母在字母表中的序号，现采用线性探查法解决冲突16设散列表长度为11，散列函数HKK11，采用线性探测法处理冲突，若输入序列为100，90，120，60，78，35，42，31，15，要求构造出散列表，并求出在等概率情况下查找成功的平均查找长度。17设散列表的长度为13，散列函数为H（K）K13，给定的关键码序列为19，14，23，01，68，20，84，27。试画出用线性探查法解决冲突时所构成的散列表。18已知一组关键字为70,46,18,25,9,16,65,8,19,34,散列函数为HKK161分别画出采用线性探测法和链接地址法解决冲突时得到的散列表2在记录查找概率相同的情况下,分别求出其平均查找长度19已知线性表的关键字集合87,25,310,08,27,132,68,95,187,123,70,63,47，已知散列函数为HKK13，采用拉链法处理冲突，设计出该散列表的结构。20请画出下图所示的二叉树所对应的树。21若只知道上图所示的二叉排序树的各结点的值依次为19，则请具体的标出该二叉树各结点的值。22一棵二叉树的顺序存储结构为123450000671画出该二叉树,并把该二叉树转换为森林2中序线索该二叉树23已知一个有序表15,26,34,39,45,56,58,63,74,76,83,94顺序存储在一维数组A12中，根据折半搜索过程填写成功搜索下表中所给元素34，56，58，63，94时的比较次数。24从一棵空的二叉排序树开始，将以下关键码值依次插入25,13,15,31,7,20,37，请画出插入全部完成后的二叉排序树。25从空树起，依次插入关键字40，8，90，15，62，95，12，23，56，32，构造一棵二叉排序树。1画出该二叉排序树2画出删去该树中元素值为90的结点之后的二叉排序树。26假定一棵二叉树的广义表表示为A（B（D,E），C（F（H，IJ，G）；分别写出先根、后根、按层遍历的序列。27己知一个带权图的顶点集V和边集E分别为V0，1，2，3，4，5，6，7；E（0，1）8，（0，2）5，（0，3）2，（1，5）6，（2，3）25，（2，4）13，（3，5）9，（3，6）10，（4，6）4，（5，7）20；则求出该图的最小生成树的权。28将关键码53，78，65，17，87，09，81，45，23依次插入到一棵初始为空的二搜索树中，画出该二叉搜索树。29假设通信电文使用的字符集为A,B,C,D,E,F，各字符在电文中出现的频度分别为34，5，12，23，8，18，试为这6个字符设计哈夫曼编码。请先画出你所构造的哈夫曼树要求树中左孩子结点的权值小于右孩子结点的权值，然后分别写出每个字符对应的编码。30请简述散列函数在散列法存储中的作用。31请简述装填因子的定义，为什么说装填因子是散列法存储的一个重要参数32已知一个图如下所示，其顶点按A、B、C、D、E、F顺序存放在邻接表的顶点表中，请画出该图的邻接表，使得按此邻接表进行深度优先遍历时得到的顶点序列为ACBEFD，进行广度优先遍历时得到的顶点序列为ACBDFE。33已知两个45的稀疏矩阵的三元组表分别如下,请画出这两个稀疏矩阵之和的三元组表。01416011321221812222234252256934228334254425134求出下图的一棵最小生成树。35已知一树的双亲表示法如下，其中各兄弟结点是依次出现的，画出该树及对应的二叉树。下标123456789101112131415DATAABCDEFGHIJKLMNOPARENT01112233445667836如图所示，在栈的输入端有6个元素，顺序为A，B，C，D，E，F能否在栈的输出端得到序列DCFEBA及EDBFCA若能，给出栈操作的过程，若不能，简述其理由。五、算法设计题1编写算法，判断带头结点的单循环链表L中从第3项起的各结点的值是否是其前面两项之差的绝对值。已知链表L的结点数不少于3，且各结点有DATA和NEXT两个字段。2设二叉树采用二叉链表存储，各结点有LCHILD、DATA和RCHILD三个字段，设计算法仅打印出其中所有叶子结点的值。3设图G用邻接矩阵AN，N表示，设计算法判断G是否是无向图。4设计算法，将单链表L1复制到单链表L2中即建立一个和L1有完全相同数据的单链表L2。5已知二叉树T，以二叉链表存储，设计算法求二叉树T中的结点个数。6编写完整程序，采用链式存储结构，实现两稀疏矩阵的加法运算。7设计算法按递减次序输出二叉排序树中所有结点的值。8编写算法，求出单循环链表L中值为最大的结点的指针。已知各结点中有DATA和NEXT两个字段。9设二叉树采用二叉链表存储，其中各结点中有LHILD、DATA和RCHILD三个字段，其中DATA为整型字段。设计算法打印出值为偶数的结点的值，并要求打印次序满足每个结点不能比其孩子结点先打印。10设计算法将顺序表L的所有元素倒置。11设计算法将整型数组AN中的元素调整为满足如下条件其中所有的3的倍数的元素集中在左边，其余元素放在右边。12设一棵二叉树以二叉链表为存储结构，结点包含LCHILD、DATA和RCHILD三个字段。设计算法，求出在先序序列中处于第K个位置的结点。13设某单链表L的结点包含DATA和NEXT两个字段，试画出该链表的结构图，并编写算法判断该链表的元素值是否是递增的假设链表中至少有一个元素。14设计一个非递归的算法以求出二叉树的先序序列的最后一个结点。15已知一棵完全二叉树存放于一个一维数组TN中，TN中存放的是各结点的值。试设计一个算法，从T0开始顺序读出各结点的值，建立该二叉树的二叉链表表示。16设某带头结点的单链表结构说明如下TYPEDEFSTRUCTNODE1INTDATASTRUCTNODE1NEXTNODE试设计一个算法INTCOUNTNODEHEAD计算该单链表中数据域DATA的值为M的结点个数。设单链表的头指针为HEAD。17写出在递增有序表A1,N中采用二分查找法查找值为X的元素的非递归算法。18设二叉树采用二叉链表表示，DATA为整数型字段。设计算法判别一棵二叉树是否是二叉排序树。19设有两个按升序排列的单链表X和Y，其头指针分别为P,Q结点结构说明如下TYPEDEFSTRUCTNODELINTDATASTRUCTNODELNEXTNODE试设计一个算法VOIDCONCATNODEP,Q将它们合并成一个以P为头指针的单链表Z，使其仍然有序。20编写完整程序，采用非递归算法建立二叉树，并求该二叉树的深度。附算法设计部分习题解答第1题算法INCLUDEINCLUDESTRUCTNODEINTDATANODENEXTNODELNULLVOIDDISPNODEPLNEXTWHILEPLCOUTDATANEXTCOUTNEXT,P2P1NEXT,P3P2NEXTWHILEP3LIFP3DATAFABSP1DATAP2DATAK0BREAKP1P1NEXTP2P2NEXTP3P3NEXTRETURNKVOIDMAINNODER,SLNEWNODERLINTXCINXWHILEX1000SNEWNODESDATAXRNEXTSRSCINXRNEXTLCOUTLCHILDNULLPREORDERTRCHILD第3题算法DEFINEN8VOIDF03INTANNINTI,J,OK1FORI0INEXT,S2,RL2NEWNODERL2WHILES1S2NEWNODES2DATAS1DATARNEXTS2RS2S1S1NEXTRNEXTNULLRETURNL2第5题算法STRUCTBITREECHARDATABITREELCHILD,RCHILDINTN0VOIDCOUNTFBITREETIFTNN1COUNTFTLCHILDCOUNTFTRCHILD第7题算法STRUCTBITREEINTDATABITREELCHILD,RCHILDVOIDLISTBITREEPIFPLISTPRCHILDCOUTDATALCHILD第8题算法STRUCTNODEINTDATANODENEXTNODELNULLNODEPMAXNODEPLNEXT,P0PINTMAXMAXPDATAWHILEPLIFPDATAMAXMAXPDATAP0PPPNEXTCOUTDATALCHILDFOUNDTRCHILDIFTDATA20COUTDATADATALCHILDDISPKTRCHILD第13题算法STRUCTNODEINTDATANODENEXTNODELNULLINTQZHINTK1NODEP1LNEXT,P2P1NEXTWHILEP2IFP2DATADATAK0BREAKP1P1NEXTP2P2NEXTRETURNKVOIDMAINNODER,SLNEW