数据结构数据结构考研辅导考研辅导 例题详解例题详解浙江大学计算机学院浙江大学计算机学院1内容提纲内容提纲真题解答真题解答1分类测试分类测试2线性表、堆栈、队列、数组线性表、堆栈、队列、数组A树与图树与图B查找与排序查找与排序C2真题解答真题解答v单项选择题：单项选择题：140小题，每小题小题，每小题2分，共分，共80分。下列每题给出的四个选项中，只有分。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。一个选项是最符合题目要求的。1.为解决计算机主机与打印机之间速度不匹配问为解决计算机主机与打印机之间速度不匹配问题，通常设置一个打印数据缓冲区，主机将要题，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是构应该是？A.栈栈B.队列队列C.树树D.图图3真题解答真题解答2.设栈设栈S和队列和队列Q的初始状态均为空，元素的初始状态均为空，元素a,b,c,d,e,f,g依次进入栈依次进入栈S。若每个元素出栈后。若每个元素出栈后立即进入队列立即进入队列Q，且，且7个元素出队的顺序是个元素出队的顺序是b,d,c,f,e,a,g，则栈，则栈S的容量至少是的容量至少是A.1B.2C.3D.4 ab cdefg4真题解答真题解答3.给定二叉树如下图所示。设给定二叉树如下图所示。设N代表二叉树的根，代表二叉树的根，L代表根结点的左子树，代表根结点的左子树，R代表根结点的右子树代表根结点的右子树。若遍历后的结点序列为。若遍历后的结点序列为3，1，7，5，6，2，4，则其遍历方式是，则其遍历方式是A. LRN B. NRLC. RLND. RNL12345675真题解答真题解答4.下列二叉排序树中，满足平衡二叉树定义的是下列二叉排序树中，满足平衡二叉树定义的是A.B.C.D.6真题解答真题解答5.已知一棵完全二叉树的第已知一棵完全二叉树的第6层（设根为第层（设根为第1层）层）有有8个叶结点，则该完全二叉树的结点个数最个叶结点，则该完全二叉树的结点个数最多是多是A.39B.52C.111D.1196层共层共261=63个个328=24487真题解答真题解答6.将森林转换为对应的二叉树，若在二叉树中，将森林转换为对应的二叉树，若在二叉树中，结点结点u是结点是结点v的父结点的父结点，则在原来的的父结点的父结点，则在原来的森林中，森林中，u和和v可能具有的关系是可能具有的关系是 I.父子关系父子关系II.兄弟关系兄弟关系III.u的父结点与的父结点与v的父结点是兄弟关系的父结点是兄弟关系A.只有只有II B.I和和IIC.I和和IIID.I、II和和IIIuvuvuvuv8真题解答真题解答7.下列关于无向连通图特征的叙述中，正确的是下列关于无向连通图特征的叙述中，正确的是I.所有顶点的度之和为偶数所有顶点的度之和为偶数II.边数大于顶点个数减边数大于顶点个数减1III.至少有一个顶点的度为至少有一个顶点的度为1A.只有只有IB.只有只有IIC.I和和IID.I和和III9真题解答真题解答8.下列叙述中，不符合下列叙述中，不符合m阶阶B树定义要求的是树定义要求的是 A.根结点最多有根结点最多有m棵子树棵子树B.所有叶结点都在同一层上所有叶结点都在同一层上C.各结点内关键字均升序或降序排列各结点内关键字均升序或降序排列D.叶结点之间通过指针链接叶结点之间通过指针链接10真题解答真题解答9.已知关键字序列已知关键字序列5，8，12，19，28，20，15，22是小根堆（最小堆），插入关键字是小根堆（最小堆），插入关键字3，调，调整后得到的小根堆是整后得到的小根堆是 A.3，5，12，8，28，20，15，22，19B.3，5，12，19，20，15，22，8，28C.3，8，12，5，20，15，22，28，19D.3，12，5，8，28，20，15，22，195812192820152235128282015221911真题解答真题解答10.若数据元素序列若数据元素序列11，12，13，7，8，9，23，4，5是采用下列排序方法之一得是采用下列排序方法之一得到的第二趟排序后的结果，则该排序算到的第二趟排序后的结果，则该排序算法只能是法只能是A.起泡排序起泡排序B.插入排序插入排序C.选择排序选择排序D.二路归并排序二路归并排序12真题解答真题解答2综综合合应应用用题题：4147小小题题，共共70分分。请请将将答答案写在答题纸指定位置上案写在答题纸指定位置上。41.（10分）带权图（权值非负，表示边连接的两顶点间的距离）分）带权图（权值非负，表示边连接的两顶点间的距离）的最短路径问题是找出从初始顶点到目标顶点之间的一条最短的最短路径问题是找出从初始顶点到目标顶点之间的一条最短路径。假设从初始顶点到目标顶点之间存在路径，现有一种解路径。假设从初始顶点到目标顶点之间存在路径，现有一种解决该问题的方法决该问题的方法：设最短路径初始时仅包含初始顶点，令当前顶点设最短路径初始时仅包含初始顶点，令当前顶点u为初始顶点；为初始顶点；选择离选择离u最近且尚未在最短路径中的一个顶点最近且尚未在最短路径中的一个顶点v，加入到最短路径，加入到最短路径中，修改当前顶点中，修改当前顶点u=v；重复步骤重复步骤，直到，直到u是目标顶点时为止。是目标顶点时为止。请问上述方法能否求得最短路径？若该方法可行，请证明之；请问上述方法能否求得最短路径？若该方法可行，请证明之；否则请举例说明。否则请举例说明。13真题解答真题解答【参考答案参考答案】该方法不一定能求得最短路径。该方法不一定能求得最短路径。举例说明：举例说明： 图图a 图图b 图图a中，设初始顶点为中，设初始顶点为1，目标顶点为，目标顶点为4，欲求从顶点，欲求从顶点1到顶点到顶点4之间的最短路之间的最短路径。显然这两点之间的最短路径长度为径。显然这两点之间的最短路径长度为2。但利用给定方法求得的路径长度为。但利用给定方法求得的路径长度为3，这条路径并不是这两点之间的最短路径。，这条路径并不是这两点之间的最短路径。 图图b中，设初始顶点为中，设初始顶点为1，目标顶点为，目标顶点为3，欲求从顶点，欲求从顶点1到顶点到顶点3之间的最短路之间的最短路径。利用给定的方法，无法求出顶点径。利用给定的方法，无法求出顶点1到顶点到顶点3的路径。的路径。 此题目给出的算法的关键错误是，将局部最优作为全局最优处理，从此题目给出的算法的关键错误是，将局部最优作为全局最优处理，从而采用了贪心的方法。解答时只要能体现而采用了贪心的方法。解答时只要能体现“局部最优不等于全局最优局部最优不等于全局最优”的思想，就可以得到的思想，就可以得到60%的分数。的分数。143211123211214真题解答真题解答42.（15分）已知一个带有表头结点的单链表，结点结构为分）已知一个带有表头结点的单链表，结点结构为，假设该链表只给出了头指针，假设该链表只给出了头指针list。在不改变链表的前提下，。在不改变链表的前提下，请设计一个请设计一个尽可能高效尽可能高效的算法，查找链表中倒数第的算法，查找链表中倒数第k个位置上个位置上的结点（的结点（k为整数）。若查找成功，算法输出该结点的为整数）。若查找成功，算法输出该结点的data域域的值，并返回的值，并返回1；否则，只返回；否则，只返回0。要求。要求：（1）描述算法的基本设计思想；）描述算法的基本设计思想；（2）描述算法的详细实现步骤；）描述算法的详细实现步骤；（3）根据设计思想和实现步骤，采用程序设计语言描述算法（使）根据设计思想和实现步骤，采用程序设计语言描述算法（使用用C或或C+或或JAVA语言实现），关键之处请给出简要注释。语言实现），关键之处请给出简要注释。datalink15真题解答真题解答【参考答案参考答案】（1）算法的基本设计思想：）算法的基本设计思想： 定义两个指针变量定义两个指针变量p和和q，初始时均指向头结点的下一个结点。，初始时均指向头结点的下一个结点。p指针指针沿链表移动；当沿链表移动；当p指针移动到第指针移动到第k个结点时，个结点时，q指针开始与指针开始与p指针同步指针同步移动；当移动；当p指针移动到链表最后一个结点时，指针移动到链表最后一个结点时，q指针所指元素为倒数指针所指元素为倒数第第k个结点。个结点。（2）算法的详细实现步骤：）算法的详细实现步骤： count = 0, p和和q指向链表表头结点的下一个结点；指向链表表头结点的下一个结点； 若若p为空，转为空，转； 若若count等于等于k，则，则q指向下一个结点；否则，指向下一个结点；否则，count = count + 1； p指向下一个结点，转步骤指向下一个结点，转步骤； 若若count等于等于k，则查找成功，输出该结点的，则查找成功，输出该结点的data域的值，返回域的值，返回1；否则，查找失败，返回否则，查找失败，返回0； 算法结束。算法结束。 16bool WrongMethod( LinkList list, int k )LinkList p, q;int count = 0;p = q = list-link;while ( p ) p = p-link;if(countlink;if ( count data);return 1;17boolKthCountedBackwards(LinkListlist,intk)LinkListp,q;intcount=0;p=q=list-link;while(p&countlink;count+;if(p)while(p)p=p-link;q=q-link;if(countdata);return1;（3）算法实现：typedef struct ListNode *ListPtr;typedef struct ListNode ElementType data;ListPtr link;ListPtr LinkList;18真题解答真题解答v类似题目：类似题目：给定一单链表，判断其链接是否存在回路，给定一单链表，判断其链接是否存在回路，要求额外空间复杂度为要求额外空间复杂度为O(1)。算法思路为：令算法思路为：令2个指针从头结点开始，以不同的步长个指针从头结点开始，以不同的步长1和和2前进；若前进；若它们再次相遇于同一结点，则链表中存在回路。实现代码如下：它们再次相遇于同一结点，则链表中存在回路。实现代码如下：boolIsCycle(LinkListlist)inti;LinkListp1,p2;p1=p2=list;while(true)for(i=0;ilink;if(p1=p2)returntrue;p2=p2-link;return0;19真题解答真题解答v类似题目：类似题目：令指针令指针p指向非空链表中的一个结点，且该结指向非空链表中的一个结点，且该结点不在表尾。设计算法将点不在表尾。设计算法将p所指的结点删除。所指的结点删除。注意到题目中特别申明该结点注意到题目中特别申明该结点不在表尾不在表尾，即该结点的后继结点不为，即该结点的后继结点不为空，于是我们可以将其后继结点的内容复制到该结点，然后将其后继空，于是我们可以将其后继结点的内容复制到该结点，然后将其后继结点删除即可。实现代码如下：结点删除即可。实现代码如下：voidDeleteThisP(LinkListp)LinkListtmp=p-link;p-data=tmp-data;p-link=tmp-link;free(tmp);20分类测试分类测试v线性表、堆栈、队列、数组线性表、堆栈、队列、数组v树与图树与图v查找与排序查找与排序21v自测题自测题在具有在具有n个结点的单链表中，实现下列个结点的单链表中，实现下列哪个操作，其算法的时间复杂度是哪个操作，其算法的时间复杂度是O(n) A遍历链表和求链表的第遍历链表和求链表的第i个结点个结点B在地址为在地址为p的结点之后插入一个结点的结点之后插入一个结点C删除开始结点删除开始结点D删除地址为删除地址为p的结点的后继结点的结点的后继结点 线性表、堆栈、队列、数组线性表、堆栈、队列、数组22v自测题自测题令令P代表入栈，代表入栈，O代表出栈。则将一个字符串代表出栈。则将一个字符串3*a+b/c变为变为3a*bc/+的堆栈操作序列是哪的堆栈操作序列是哪个？（例如将个？（例如将ABC变成变成BCA的操作序列是的操作序列是PPOPOO。）。）A.PPPOOOPPOPPOOO B.POPOPOPPOPPOOO C.POPPOOPPOPPOOO D.POPPOOPPOPOOPO 线性表、堆栈、队列、数组线性表、堆栈、队列、数组23v自测题自测题某线性表中最常用的操作是在最后一个元素之某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用什后插入一个元素和删除第一个元素，则采用什么存储方式最节省运算时间？么存储方式最节省运算时间？ A.单链表单链表B.仅有头指针的单循环链表仅有头指针的单循环链表C.双链表双链表D.仅有尾指针的单循环链表仅有尾指针的单循环链表线性表、堆栈、队列、数组线性表、堆栈、队列、数组24v自测题自测题线性表在什么情况下适用于使用链式线性表在什么情况下适用于使用链式结构实现结构实现?A.需经常修改中的结点值需经常修改中的结点值B.需不断对进行删除插入需不断对进行删除插入C.中含有大量的结点中含有大量的结点D.中结点结构复杂中结点结构复杂 线性表、堆栈、队列、数组线性表、堆栈、队列、数组25v自测题自测题对于一个具有对于一个具有n个结点的单链表，在给个结点的单链表，在给定值为定值为x的结点后插入一个新结点的时的结点后插入一个新结点的时间复杂度为间复杂度为.O(n).O(1).O(n/2).O(n2) 线性表、堆栈、队列、数组线性表、堆栈、队列、数组26v自测题自测题设一个栈的输入序列是设一个栈的输入序列是1，2，3，4，5,则下则下列序列中，是栈的合法输出序列的是？列序列中，是栈的合法输出序列的是？ A.51234B.45132C.43125D.32154线性表、堆栈、队列、数组线性表、堆栈、队列、数组27v自测题自测题若已知一个栈的入栈序列是若已知一个栈的入栈序列是1，2，3，n，其输出序列为，其输出序列为p1，p2，p3，pn。若若p1=n，则，则pi为为：A.iB.niC.ni+1D.不确定不确定 线性表、堆栈、队列、数组线性表、堆栈、队列、数组28v自测题自测题将将5个字母个字母ooops按此顺序入栈，则按此顺序入栈，则有多少种不同的出栈顺序可以仍然得到有多少种不同的出栈顺序可以仍然得到ooops？A.1B.3C.5D.6 线性表、堆栈、队列、数组线性表、堆栈、队列、数组29v自测题自测题链表不具有的特点是链表不具有的特点是：A.插入、删除不需要移动元素插入、删除不需要移动元素B.可随机访问任一元素可随机访问任一元素C.不必事先估计存储空间不必事先估计存储空间D.所需空间与线性长度成正比所需空间与线性长度成正比 线性表、堆栈、队列、数组线性表、堆栈、队列、数组30v自测题自测题若某表最常用的操作是在最后一个结点之若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。则后插入一个结点或删除最后一个结点。则采用哪种存储方式最节省运算时间采用哪种存储方式最节省运算时间？A.单链表单链表B.双链表双链表C.单循环链表单循环链表D.带头结点的双循环链表带头结点的双循环链表 线性表、堆栈、队列、数组线性表、堆栈、队列、数组31v自测题自测题若某线性表最常用的操作是存取任一指定若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，序号的元素和在最后进行插入和删除运算，则利用哪种存储方式最节省时间则利用哪种存储方式最节省时间？A.顺序表顺序表 B.双链表双链表C.单循环链表单循环链表D.带头结点的双循环链表带头结点的双循环链表 线性表、堆栈、队列、数组线性表、堆栈、队列、数组32v自测题自测题数组数组A1.5,1.6每个元素占每个元素占5个单元，将其个单元，将其按行优先次序存储在起始地址为按行优先次序存储在起始地址为1000的连的连续的内存单元中，则元素续的内存单元中，则元素A5,5的地址为的地址为A.1140B.1145C.1120D.1125 线性表、堆栈、队列、数组线性表、堆栈、队列、数组1000+(291)*533v自测题自测题已知两个堆栈已知两个堆栈S1和和S2的相关操作为：的相关操作为：Push(X,S)：将元素：将元素X压入堆栈压入堆栈S；Pop(S)：将堆栈：将堆栈S的栈顶元素退栈；的栈顶元素退栈；IsFull(S)：判断堆栈：判断堆栈S是否已满，若满则返回是否已满，若满则返回1，否则返，否则返回回0；IsEmpty(S)：判断堆栈：判断堆栈S是否为空，若空则返回是否为空，若空则返回1，否则，否则返回返回0。现想用这两个堆栈实现一个队列，请用上述堆栈操现想用这两个堆栈实现一个队列，请用上述堆栈操作实现队列的的入列（作实现队列的的入列（Enqueue）和出列）和出列（Dequeue）功能。）功能。线性表、堆栈、队列、数组线性表、堆栈、队列、数组34v利用堆栈的后进先出特点，利用堆栈的后进先出特点，经过两次经过两次“后进先出后进先出”转变为转变为“先进先进先出先出”，即元素先经过堆栈，即元素先经过堆栈S1再经过堆栈再经过堆栈S2，从而实现队列的，从而实现队列的功能。功能。v入队的原理相对简单，向入队的原理相对简单，向S1中压入即可。问题是当中压入即可。问题是当S1满时，为满时，为了能最大限度不浪费空间，我们应检查了能最大限度不浪费空间，我们应检查S2。这里假设。这里假设S1和和S2容容量相同。若量相同。若S2是空的，我们可以将是空的，我们可以将S1中的元素逐一退栈，并压中的元素逐一退栈，并压入入S2中。新入列的元素就可以压入腾空的中。新入列的元素就可以压入腾空的S1了。只有在了。只有在S2还没还没有空、且有空、且S1已满的情况下，模拟队列中才不能再接受新元素。已满的情况下，模拟队列中才不能再接受新元素。v当需要出队时，首先判断模拟队列是否为空。若当需要出队时，首先判断模拟队列是否为空。若S1和和S2都是空都是空的，则应返回错误信息。若出队请求是合法的，则检查的，则应返回错误信息。若出队请求是合法的，则检查S2。若。若S2为空，则为空，则S1必不为空，将必不为空，将S1中的元素逐一退栈，并压入中的元素逐一退栈，并压入S2中。这时中。这时S2中栈底存的是中栈底存的是S1的栈顶元素，也即最晚入列的元素；的栈顶元素，也即最晚入列的元素；栈顶存的是栈顶存的是S1的栈底元素，也即最早入列的元素。这时的栈底元素，也即最早入列的元素。这时S2退栈退栈就相当于队列的出队，实现了先进先出。就相当于队列的出队，实现了先进先出。线性表、堆栈、队列、数组线性表、堆栈、队列、数组35v自测题自测题请设计尽可能高效的算法，颠倒一个英文句子中单请设计尽可能高效的算法，颠倒一个英文句子中单词的顺序，例如将词的顺序，例如将“thisisatest”转换为转换为“testaisthis”。设该句子以字符数组方式存放在。设该句子以字符数组方式存放在S中，中，并已知其长度为并已知其长度为N。 线性表、堆栈、队列、数组线性表、堆栈、队列、数组此题的核心在于颠倒一个字符串，方法是令此题的核心在于颠倒一个字符串，方法是令p1和和p2两两个指针分别从字符串头尾向中心移动，不断交换它们各个指针分别从字符串头尾向中心移动，不断交换它们各自所指的字符。自所指的字符。颠倒整个句子方法是先将整句作为一个字符串，完全颠倒整个句子方法是先将整句作为一个字符串，完全颠倒，再将其中的每个单词识别出来，分别颠倒回来。颠倒，再将其中的每个单词识别出来，分别颠倒回来。参考答案中的代码可以处理单词间不只一个空格的情况。参考答案中的代码可以处理单词间不只一个空格的情况。36v自测题自测题设高为设高为h的二叉树只有度为的二叉树只有度为0和和2的结点，的结点，则此类二叉树的结点数至少为则此类二叉树的结点数至少为_，最多，最多为为_？ A.2h-1+1,2h1B.2h,2h1C.2h1,2h1D.2h1,2h-11树与图树与图37树与图树与图v自测题自测题三叉树中，度为三叉树中，度为1的结点有的结点有5个，度为个，度为2的结点的结点3个，度为个，度为3的结点的结点2个，问该树含有几个叶结点个，问该树含有几个叶结点？A.8B.10C.12D.13N1=5;N2=3;N3=2N=N0+10N1=5*1+3*2+2*338树与图树与图v自测题自测题一棵树有一棵树有n1个孩子数为个孩子数为1的结点的结点,n2个孩子数个孩子数为为2的结点的结点,nm个孩子数为个孩子数为m的结点，则的结点，则该树的叶结点数为该树的叶结点数为ABCD39树与图树与图v自测题自测题对二叉排序树进行什么遍历可以得到从小到大对二叉排序树进行什么遍历可以得到从小到大的排序序列的排序序列？A.前序遍历前序遍历B.中序遍历中序遍历C.后序遍历后序遍历D.层次遍历层次遍历 40树与图树与图v自测题自测题在下述结论中，正确的是在下述结论中，正确的是只有一个结点的二叉树的度为只有一个结点的二叉树的度为0;二叉树的度为二叉树的度为2；二叉树的左右子树可任意交换；二叉树的左右子树可任意交换；深度为深度为K的完全二叉树的结点个数小于或等于深度相同的完全二叉树的结点个数小于或等于深度相同的满二叉树。的满二叉树。ABCD41树与图树与图v自测题自测题12个结点的个结点的AVL树的最大深度是？树的最大深度是？A.3B.4C.5D.6等价问题：深度为等价问题：深度为h的的AVL树的最少树的最少结点数是？结点数是？42树与图树与图v自测题自测题对于一个共有对于一个共有n个结点、个结点、k条边的森林，共有几条边的森林，共有几棵树？棵树？A.nkB.nk+1C.nk1D.不能确定不能确定每棵有每棵有m个结点的树必有个结点的树必有m-1条边条边n= mk= mt（t是树的个数）是树的个数）t=?43树与图树与图v自测题自测题设森林设森林F中有三棵树，第一，第二，第中有三棵树，第一，第二，第三棵树的结点个数分别为三棵树的结点个数分别为M1，M2和和M3。与森林与森林F对应的二叉树根结点的右子树对应的二叉树根结点的右子树上的结点个数是上的结点个数是AM1BM1+M2CM3DM2+M3 44v自测题自测题设每个设每个d叉树的结点有叉树的结点有d个指针指向子树，个指针指向子树，有有n个结点的个结点的d叉树有多少叉树有多少空链域？空链域？A.n(d-1)B.n(d-1)+1C.ndD.以上都不是以上都不是 树与图树与图n个结点有个结点有nd个指针个指针除了根，每个结点被除了根，每个结点被1个指针所指个指针所指nd(n1)45v自测题自测题哪种树，树中任何结点到根结点路径上的哪种树，树中任何结点到根结点路径上的各结点值是有序的？各结点值是有序的？A.堆堆B.二叉排序树二叉排序树C.完全二叉树完全二叉树D.以上都不是以上都不是 树与图树与图46v自测题自测题某二叉树的中序序列和后序序列正好相某二叉树的中序序列和后序序列正好相反，则该二叉树一定是反，则该二叉树一定是A.空或只有一个结点空或只有一个结点B.高度等于其结点数高度等于其结点数C.任一结点无左孩子任一结点无左孩子D.任一结点无右孩子任一结点无右孩子 树与图树与图47v自测题自测题设设n、m为一棵二叉树上的两个结点，在为一棵二叉树上的两个结点，在中序遍历时，中序遍历时，n在在m前的条件是前的条件是An在在m右方右方Bn是是m祖先祖先Cn在在m左方左方Dn是是m子孙子孙树与图树与图48v自测题自测题请设计算法求二叉树中叶结点的个数。请设计算法求二叉树中叶结点的个数。树与图树与图intCountLeaf(TreeT)/这里假设树不为空这里假设树不为空intLeafNum;if(!T-LeftChild&!T-RightChild)return1;elseif(T-LeftChild)LeafNum=CountLeaf(T-LeftChild);if(T-RightChild)LeafNum+=CountLeaf(T-RightChild);returnLeafNum;49v自测题自测题树中任意两结点之间都存在一条路径，两结点的树中任意两结点之间都存在一条路径，两结点的距离即定义为路径的长度。距离最远的两个结点距离即定义为路径的长度。距离最远的两个结点的距离定义为树的的距离定义为树的“直径直径”。给定一棵用二叉链。给定一棵用二叉链表存储的二叉树，其结点构造为如图。指针表存储的二叉树，其结点构造为如图。指针Root指向根结点。请设计时间复杂度为指向根结点。请设计时间复杂度为O(n)的的算法（算法（n为树中结点的个数）求二叉树的直径。为树中结点的个数）求二叉树的直径。树与图树与图Left_ChildDataRight_Child直径直径=max(左树深度左树深度+右树右树深度深度)50树与图树与图intBinaryTreeHeight(TreeT,int*MaxHeightSumP)if(!T)return0;intLeftHeight=BinaryTreeHeight(T-LeftChild,MaxHeightSumP);intRightHeight=BinaryTreeHeight(T-RightChild,MaxHeightSumP);(*MaxHeightSumP)=max(LeftHeight+RightHeight,*MaxHeightSumP);returnmax(LeftHeight,RightHeight)+1;intFindRadOfTree(TreeRoot)intMaxHeightSum=0;BinaryTreeHeight(Root,&MaxHeightSum);returnMaxHeightSum;51v自测题自测题(考研大纲中例题考研大纲中例题)已知一棵二叉树采用二叉链表存储。现定义二叉已知一棵二叉树采用二叉链表存储。现定义二叉树中结点树中结点X0的根路径为从根结点到的根路径为从根结点到X0的一条路径，的一条路径，请编写算法输出该二叉树中最长的根路径（多条请编写算法输出该二叉树中最长的根路径（多条最长根路径中只输出一条即可。算法可用最长根路径中只输出一条即可。算法可用C或或C+或或JAVA语言实现）。语言实现）。参考答案：参考答案：v此题要求最长的根路径，该路径的长度就是树的深度。解题思此题要求最长的根路径，该路径的长度就是树的深度。解题思路分两步走：首先求树的深度，同时记住最深的那个叶子结点；路分两步走：首先求树的深度，同时记住最深的那个叶子结点；然后对树做先序遍历，在遍历过程中找最深的那个叶子结点。然后对树做先序遍历，在遍历过程中找最深的那个叶子结点。当找到时，存在系统堆栈中的结点就构成了最长的根路径。整当找到时，存在系统堆栈中的结点就构成了最长的根路径。整个算法在最坏情况下会执行两次树的遍历，复杂度是个算法在最坏情况下会执行两次树的遍历，复杂度是O(n)（n为树中结点的个数）。为树中结点的个数）。v另外有算法用一个数组保存路径上的结点，在求树深的同时不另外有算法用一个数组保存路径上的结点，在求树深的同时不断更新最深路径，虽然程序结构相对简单，但复杂度显然超过断更新最深路径，虽然程序结构相对简单，但复杂度显然超过线性。线性。 树与图树与图52v自测题自测题给定一个整数给定一个整数x，以及一个可能的查找的，以及一个可能的查找的关键字序列关键字序列K0,KN-1，请设计，请设计算法判别一个序列是否是一个可能的二叉算法判别一个序列是否是一个可能的二叉排序树上进行的查找序列。（例如：排序树上进行的查找序列。（例如：1,4,2,3就是查找就是查找3的序列，对应二叉排序的序列，对应二叉排序树如图。而树如图。而2,4,1,3就不可能是。）要就不可能是。）要求算法时间复杂度为求算法时间复杂度为O(N)。树与图树与图1234答案答案1：先构造树，再判断是否二叉排序树：先构造树，再判断是否二叉排序树53树与图树与图boolIs_BST_sequence(intK,intN)if(N=2)returntrue;CreaterootforK0;Parent=root;for(i=1;ikeykey)Parent-rightchild=node;elseParent-leftchild=node;Parent=node;returnIS_BST(root,&min,&max);可以用简单的后序遍历吗？可以用简单的后序遍历吗？432751654树与图树与图boolIS_BST(TreeT,int*min,int*max)if(!T-leftchild&!T-rightchild)(*min)=(*max)=T-key;returntrue;Left_flag=Right_flag=false;if(T-leftchild&IS_BST(T-leftchild,&lmin,&lmax)&T-keylmax)|!T-leftchild)Left_flag=true;if(T-rightchild&IS_BST(T-rightchild,&rmin,&rmax)&T-keyrightchild)Right_flag=true;if(Left_flag&Right_flag)if(T-leftchild)(*min)=lmin;else(*min)=T-key;if(T-rightchild)(*max)=rmax;else(*max)=T-key;returntrue;elsereturnfalse;55树与图树与图答案答案2：#defineIsInRange(n)(nmin)boolIs_BST_sequence(intK,intN,intX)min=MIN_ELEMENT;max=MAX_ELEMENT;for(i=0;iX)max=Ki;elseif(KiRightChild)SortBST(T-RightChild,x);if(T-datadata);if(T-LeftChild)SortBST(T-LeftChild,x);57v自测题自测题在有在有N个结点且为完全二叉树的二叉排序树个结点且为完全二叉树的二叉排序树中查找一个键值，其平均比较次数的数量中查找一个键值，其平均比较次数的数量级为（）。级为（）。 A.O(logN)B.O(N)C.O(NlogN)D.O(N2) 树与图树与图58v自测题自测题给定链表表示的二叉树，判断其是否为完给定链表表示的二叉树，判断其是否为完全二叉树。全二叉树。答案：对于完全二叉树，其关键特点是：答案：对于完全二叉树，其关键特点是：若某结点无左孩子就不应有右孩子。算法若某结点无左孩子就不应有右孩子。算法基本思路是利用队列做树的层次遍历，当基本思路是利用队列做树的层次遍历，当发现第一个缺少孩子的结点时，用发现第一个缺少孩子的结点时，用Flag标标记。而一旦发现了一个缺少孩子的结点，记。而一旦发现了一个缺少孩子的结点，其后的所有结点都不能再有孩子。若在其后的所有结点都不能再有孩子。若在Flag为为1的情况下还发现某结点有非空孩子的情况下还发现某结点有非空孩子结点，则必非完全二叉树。结点，则必非完全二叉树。树与图树与图59树与图树与图boolIsCompleteBinaryTree(TreeT)intFlag=0;/0表示尚未发现结点有空子树表示尚未发现结点有空子树if(!T)returnTRUE;EnQueue(Q,T);while(!IsEmpty(Q)T=DeQueue(Q);if(T-LeftChild&!Flag)EnQueue(Q,T-LeftChild);elseif(T-LeftChild)returnFALSE;elseFlag=1;/结点有空子树结点有空子树if(T-RightChild&!Flag)EnQueue(Q,T-RightChild);elseif(T-RightChild)returnFALSE;elseFlag=1;/结点有空子树结点有空子树returnTRUE;60v自测题自测题森林的二叉树用森林的二叉树用T表示。已知表示。已知T的前序和的前序和中序遍历结果，请画出对应的森林中序遍历结果，请画出对应的森林前序：前序：ABCDEFGHIJKL中序：中序：CBEFDGAJIKLH树与图树与图ABCDEFGHIJKLAHBDGCEFIKLJ61v自测题自测题设一段文本中包含字符设一段文本中包含字符a,b,c,d,e，其出，其出现频率相应为现频率相应为3,2,5,1,1。则经过哈夫曼。则经过哈夫曼编码后，文本所占字节数为编码后，文本所占字节数为A.40B.36C.25D.12 树与图树与图127425321162v自测题自测题给定字符出现频率以及哈夫曼编码的正确给定字符出现频率以及哈夫曼编码的正确长度，现对于任一套输入的编码，判断其长度，现对于任一套输入的编码，判断其是否哈夫曼编码。是否哈夫曼编码。树与图树与图63树与图树与图核心部分：核心部分：while(codeij!=0)if(codeij=0)if(!tmp-left_child)tmp-left_child=new_node();elseif(tmp-left_child-data0)ok=false;tmp=tmp-left_child;if(codeij=1)if(!tmp-right_child)tmp-right_child=new_node();elseif(tmp-right_child-data0)ok=false;tmp=tmp-right_child;j+;if(!tmp-left_child&!tmp-right_child)tmp-data=fi;elseok=false;Length+=fi*j;/计算编码长度计算编码长度64v自测题自测题在在AOE网中，什么是关键路径？网中，什么是关键路径？A.最短回路最短回路B.从第一个事件到最后一个事件的最短路径从第一个事件到最后一个事件的最短路径C.最长回路最长回路D.从第一个事件到最后一个事件的最长路径从第一个事件到最后一个事件的最长路径树与图树与图65v自测题自测题用用DFS遍历一个无环有向图，并在遍历一个无环有向图，并在DFS算算法退栈返回时打印相应的顶点，则输出的法退栈返回时打印相应的顶点，则输出的顶点序列是？顶点序列是？A.逆拓扑有序逆拓扑有序B.拓扑有序拓扑有序C.无序的无序的D.以上都不对以上都不对树与图树与图1234DFS:4,3,2,166v自测题自测题已知有向图已知有向图G=(V,E)，其中，其中V=v1,v2,v3,v4,v5,v6，E=,。G的拓扑的拓扑序列是序列是?A.v3,v4,v1,v5,v2,v6B.v1,v3,v4,v5,v2,v6C.v3,v1,v4,v5,v2,v6D.v1,v4,v3,v5,v2,v6树与图树与图12345667v自测题自测题任何一个带权无向连通图的最小生成树任何一个带权无向连通图的最小生成树 A.是唯一的是唯一的B.是不唯一的是不唯一的C.有可能不唯一有可能不唯一D.有可能不存在有可能不存在树与图树与图68v自测题自测题一个有一个有n个顶点的强连通图至少有多少条边个顶点的强连通图至少有多少条边？An(n-1)Bn-1CnDn+1树与图树与图69v自测题自测题对于有向图，其邻接矩阵表示比邻接表表对于有向图，其邻接矩阵表示比邻接表表示更易于示更易于A求一个顶点的入度求一个顶点的入度B求一个顶点的出边邻接点求一个顶点的出边邻接点C进行图的深度优先遍历进行图的深度优先遍历D进行图的广度优先遍历进行图的广度优先遍历树与图树与图70v自测题自测题在图中自在图中自a点开始进行深度优先遍历算法可能得到点开始进行深度优先遍历算法可能得到的结果为的结果为A.a,b,e,c,d,fB.a,e,d,f,c,bC.a,c,f,e,b,dD.a,e,b,c,f,d树与图树与图abecdf71v自测题自测题在图中自在图中自a点开始进行广度优先遍历算法可能得到点开始进行广度优先遍历算法可能得到的结果为的结果为A.a,b,e,c,d,fB.a,e,d,f,c,bC.a,c,f,e,b,dD.a,e,b,c,f,d树与图树与图abecdf72v自测题自测题以下哪个命题是正确的？以下哪个命题是正确的？A.对于带权无向图对于带权无向图G=(V,E)，M是是G的最小生成的最小生成树，则树，则M中任意两点中任意两点V1到到V2的路径一定是它们的路径一定是它们之间的最短路径。之间的最短路径。B.P是顶点是顶点s到到t的最短路径，如果该图中的所有路的最短路径，如果该图中的所有路径的权值都加径的权值都加1，P仍然是仍然是s到到t的最短路径。的最短路径。C.深度优先遍历也可用于完成拓扑排序。深度优先遍历也可用于完成拓扑排序。D.以上都不是。以上都不是。树与图树与图73v自测题自测题下列说法不正确的是下列说法不正确的是A图的遍历是从给定的源点出发每一个顶点图的遍历是从给定的源点出发每一个顶点仅被访问一次仅被访问一次B遍历的基本算法有两种：深度遍历和广度遍历的基本算法有两种：深度遍历和广度遍历遍历C图的深度遍历不适用于有向图图的深度遍历不适用于有向图D图的深度遍历是一个递归过程图的深度遍历是一个递归过程 树与图树与图74v自测题自测题下图中每个顶点表示一个岛，每条边表示岛屿间建下图中每个顶点表示一个岛，每条边表示岛屿间建桥的成本，找到一个算法计算正确的造桥方法，使桥的成本，找到一个算法计算正确的造桥方法，使得所有的岛屿都能连通，并且总的造价最小，给出得所有的岛屿都能连通，并且总的造价最小，给出这个算法的名字，并给出求解过程。这个算法的名字，并给出求解过程。 树与图树与图1215303525171572010512ABCGFED求最小生成树：求最小生成树：注意到给出的图中有注意到给出的图中有7个结点、个结点、12条边，属于边稀疏的情况，用条边，属于边稀疏的情况，用克鲁斯卡尔算法克鲁斯卡尔算法是合适的。若给是合适的。若给出一个完全图，则普里姆出一个完全图，则普里姆(Prim)算法将是更好的选择。算法将是更好的选择。75v自测题自测题某省调查乡村交通状况，得到的统计表中某省调查乡村交通状况，得到的统计表中列出了任意两村庄间的距离。省政府列出了任意两村庄间的距离。省政府“畅畅通工程通工程”的目标是使全省任何两个村庄间的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可）公路相连，只要能间接通过公路可达即可），并要求铺设的公路总长度为最小。要解，并要求铺设的公路总长度为最小。要解决这个问题，问：决这个问题，问：(1)可用什么数据结构表示城镇和道路？可用什么数据结构表示城镇和道路？(2)请描述效率最高的算法。请描述效率最高的算法。树与图树与图答案：最小生成树；答案：最小生成树；Prim76v自测题自测题某省调查城镇交通状况，得到现有城镇道某省调查城镇交通状况，得到现有城镇道路统计表，表中列出了每条道路直接连通路统计表，表中列出了每条道路直接连通的城镇。省政府的城镇。省政府“畅通工程畅通工程”的目标是使的目标是使全省任何两个城镇间都可以实现交通（但全省任何两个城镇间都可以实现交通（但不一定有直接的道路相连，只要互相间接不一定有直接的道路相连，只要互相间接通过道路可达即可），并要求增设的道路通过道路可达即可），并要求增设的道路条数为最少。要解决这个问题，问：条数为最少。要解决这个问题，问：(1)可用什么数据结构表示城镇和道路？可用什么数据结构表示城镇和道路？(2)请用伪码描述效率最高的解法。请用伪码描述效率最高的解法。 树与图树与图答案：答案：DSF数连通集个数数连通集个数177v自测题自测题给定给定n个村庄之间的交通图，若村庄个村庄之间的交通图，若村庄i和和j之间有道之间有道路，则将顶点路，则将顶点i和和j用边连接，边上的用边连接，边上的Wij表示这条道表示这条道路的长度，现在要从这路的长度，现在要从这n个村庄中选择一个村庄建个村庄中选择一个村庄建一所医院，问这所医院应建在哪个村庄，才能使离一所医院，问这所医院应建在哪个村庄，才能使离医院最远的村庄到医院的路程最短医院最远的村庄到医院的路程最短? 树与图树与图答案：答案：先用先用Floyd求任意求任意2点间最短路；点间最短路；对每个村庄，求它到其他村庄的最短路中最长的；对每个村庄，求它到其他村庄的最短路中最长的；找所有找所有n条最长路中最短的，那个村庄就建医院。条最长路中最短的，那个村庄就建医院。78v自测题自测题给定现有城镇道路统计表，表中列出了每给定现有城镇道路统计表，表中列出了每条道路直接连通的城镇以及距离。现有一条道路直接连通的城镇以及距离。现有一镇受灾，指定另一镇救援，要求设计算法镇受灾，指定另一镇救援，要求设计算法使得救援队以最快速度到达。另外，救援使得救援队以最快速度到达。另外，救援队每经过一镇，可以得到一个单位的救援队每经过一镇，可以得到一个单位的救援物资。要求在最快到达的同时带去最多的物资。要求在最快到达的同时带去最多的救援物资。救援物资。树与图树与图79树与图树与图修改修改Dijkstra：if(Tv.Dist+CvwTw.Count)Tw.Count=Tv.Count+1;Tw.Path=v;/*DONOTforgetthis*/80v自测题自测题带权图（权值非负，表示边连接的两顶点间的距离）的最短路径带权图（权值非负，表示边连接的两顶点间的距离）的最短路径问题是找出从初始顶点到目标顶点之间的一条最短路径。若最短问题是找出从初始顶点到目标顶点之间的一条最短路径。若最短路径不止一条，在找到一条最短路径的同时，还需要路径不止一条，在找到一条最短路径的同时，还需要输出不同的输出不同的最短路径的条数最短路径的条数。现有一种解决该问题的方法：。现有一种解决该问题的方法：初始化结点集合初始化结点集合S为仅包含源结点为仅包含源结点s；用一个整型数组；用一个整型数组Counterv来记录从来记录从s到结点到结点v的最短路径的条数，各结点的最短路径的条数，各结点Counter的初始值的初始值均为均为0；从未加入从未加入S的结点中选择当前距离最小的结点的结点中选择当前距离最小的结点v（“当前距离当前距离”指指从从s到到v且仅经过且仅经过S中结点的最短距离），将其加入中结点的最短距离），将其加入S；对每个与对每个与v相邻的结点相邻的结点w，若，若w不在不在S内，检查：内，检查：a)若若v的加入使得的加入使得w的当前距离变小，则更新的当前距离变小，则更新w的当前距离为的当前距离为(v,w)的边的边长与长与v的当前距离之和，并且令的当前距离之和，并且令Counterw=1；b)若若v的加入是的加入是s到到w的长度相同的另一条最短路，则的长度相同的另一条最短路，则Counterw+；重复步骤（重复步骤（2）（）（3），直到所有结点都被收入），直到所有结点都被收入S。若该方法可行，请证明之；否则，请举例说明。若该方法可行，请证明之；否则，请举例说明。树与图树与图81树与图树与图v答案：答案：错！错！svtw问题出在问题出在3个地方：个地方：1.当当v的加入产生新的最短路径时，从的加入产生新的最短路径时，从s到到v再到再到w的最的最短路径条数等于短路径条数等于v的最短路径条数，而不是仅等于的最短路径条数，而不是仅等于1。所以所以(3a)中中Counterw=1应改为应改为Counterw=Counterv。2.若若v的加入是的加入是s到到w的长度相同的另一条最短路，则的长度相同的另一条最短路，则w的最短路径条数不是只增加了的最短路径条数不是只增加了1，而是，而是v带过来的所带过来的所有最短路径，即有最短路径，即(3b)中的中的Counterw+应改为应改为Counterw+=Counterv。3.根据前根据前2步修改，步修改，Counters的初始值必须为的初始值必须为1，而，而不是不是0，否则后面所有结点的，否则后面所有结点的Counter都会一直是都会一直是0。82v类似题目类似题目找到找到包含边数最少包含边数最少的那条最短路径。的那条最短路径。这时第（这时第（3）步应改为：）步应改为：（3）对每个与）对每个与v相邻的结点相邻的结点w，若，若w不在不在S内，检查：内，检查：a)若若v的加入使得的加入使得w的当前距离变小，则更新的当前距离变小，则更新w的当前距离为的当前距离为(v,w)的边长与的边长与v的当前距离之和，更新的当前距离之和，更新Counterw=Counterv+1，并且将，并且将v记录在记录在w的路径上；的路径上；b)若若v的加入是的加入是s到到w的的长度相同并且边数更少长度相同并且边数更少（CounterwCounterv+1）的另一条最短路，则）的另一条最短路，则Counterw=Counterv+1，并且将，并且将v记录在记录在w的路径上；的路径上；这里的整型数组这里的整型数组Counterv记录从记录从s到结点到结点v的最短的最短路径包含的边数，各结点路径包含的边数，各结点Counter的初始值均为的初始值均为0。此问题很容易做错的地方，是当发现另一条长度相此问题很容易做错的地方，是当发现另一条长度相同但包含边数更少的最短路时，只更新了同但包含边数更少的最短路时，只更新了Counter，却却忘了更新忘了更新w的路径的路径。树与图树与图83v自测题自测题设有设有100个元素的有序序列，如果用折半个元素的有序序列，如果用折半插入排序再插入一个元素，则最大比较次插入排序再插入一个元素，则最大比较次数是数是（）A.25B.50C.10D.7查找与排序查找与排序84v自测题自测题从一个具有从一个具有n个结点的单链表中查找其值等于个结点的单链表中查找其值等于x结结点时，在查找成功的情况下，需平均比较多少个点时，在查找成功的情况下，需平均比较多少个结点？结点？ A.nB.n/2C.(n-1)/2D.(n+1)/2查找与排序查找与排序85v自测题自测题散列表的地址区间为散列表的地址区间为0-16,散列函数为散列函数为H(K)=Kmod17。采用线性探测法处理。采用线性探测法处理冲突，并将关键字序列冲突，并将关键字序列26，25，72，38，8，18，59依次存储到散列表中。元素依次存储到散列表中。元素59存放在散列表中的地址是（）存放在散列表中的地址是（）A.8B.9C.10D.11查找与排序查找与排序86v自测题自测题假定有假定有k个关键字互为同义词，若用线性探测法个关键字互为同义词，若用线性探测法把这把这k个关键字存入散列表中，至少要进行多少个关键字存入散列表中，至少要进行多少次探测？次探测？ A.k-1B.kC.k+1D.k(k+1)/2查找与排序查找与排序87v自测题自测题在一散列查找中，设散列表大小为在一散列查找中，设散列表大小为11，散列函数为散列函数为H(x)=x%11。现要把。现要把1，13，12，34，38，33，27，22插入到散列表插入到散列表中，冲突解决策略为线性探测（中，冲突解决策略为线性探测（LinearProbing）。请写出）。请写出：（1）上述数据插入后的散列表状态；）上述数据插入后的散列表状态；（2）在上述散列表状态下，进行等概率成功与不成）在上述散列表状态下，进行等概率成功与不成功查找的平均查找次数。功查找的平均查找次数。查找与排序查找与排序88查找与排序查找与排序33113342227381201345678921，13，12，34，38，33，27，2210平均成功平均成功查找次数找次数= (1+1+3+4+1+1+2+8)/8=2.625所谓等概率不成功查找，是指不成功的查找中，被散所谓等概率不成功查找，是指不成功的查找中，被散列函数映射到列函数映射到11个地址的概率相同，都是个地址的概率相同，都是1/11。平均不成功平均不成功查找次数找次数= (9+8+7+6+5+4+3+2+1+1+1)/11 4.27389v自测题自测题在下列查找的方法中，平均查找长度与在下列查找的方法中，平均查找长度与结点个数结点个数n无关的查找方法是无关的查找方法是A顺序序查找找B二分法二分法C利用二叉搜索利用二叉搜索树D利用哈希利用哈希(hash)表表 查找与排序查找与排序90v自测题自测题采用线性探查法解决冲突时所产生的一采用线性探查法解决冲突时所产生的一系列后继散列地址系列后继散列地址A必必须大于等于原散列地址大于等于原散列地址B必必须小于等于原散列地址小于等于原散列地址C可以大于或小于但不等于原散列地址可以大于或小于但不等于原散列地址D对地址在何地址在何处没有限制没有限制 查找与排序查找与排序91v自测题自测题127阶阶B-树中除根结点外所有非终端结点树中除根结点外所有非终端结点至少有多少棵子树？至少有多少棵子树？A.2B.64C.126D.63查找与排序查找与排序92v自测题自测题给出关键字序列给出关键字序列321，156，57，46，28，7，331，33，34，63，下面哪个，下面哪个选择是按选择是按LSD链式基数排序进行了一趟链式基数排序进行了一趟分配和收集的结果？分配和收集的结果？A.3313213363341564657728B.1562832133133344657637C.3213313363341564657728 D.5746287333463156321331查找与排序查找与排序93v自测题自测题有组记录的排序码为（有组记录的排序码为（46，79，56，38，40，84），则利用堆排序的方法建立的初始堆为），则利用堆排序的方法建立的初始堆为A79，46，56，38，40，80B84，79，56，38，40，46C84，79，56，46，40，38D84，56，79，40，46，38查找与排序查找与排序94v自测题自测题一个对象序列的排序码为一个对象序列的排序码为46,79,56,38,40,84，采用快速排序（以位于最左位置的对象为，采用快速排序（以位于最左位置的对象为基准而）得到的第一次划分结果为基准而）得到的第一次划分结果为 A38,46,79,56,40,84B38,79,56,46,40,84C40,38,46,56,79,84D38,46,56,79,40,84 查找与排序查找与排序95v自测题自测题对于序列（对于序列（49,38,65,97,76,13,27,50），按由小），按由小到大进行排序，下面哪一个是初始步长到大进行排序，下面哪一个是初始步长d=4的希的希尔排序法第一趟的结果？尔排序法第一趟的结果？A49,76,65,13,27,50,97,38B13,27,38,49,50,65,76,97C97,76,65,50,49,38,27,13D49,13,27,50,76,38,65,97 查找与排序查找与排序96v自测题自测题就排序算法所用的辅助空间而言，堆排序、快就排序算法所用的辅助空间而言，堆排序、快速排序、归并排序的关系是速排序、归并排序的关系是A.堆排序堆排序快速排序快速排序归并排序归并排序B.堆排序堆排序归并排序归并排序归并排序归并排序快速排序快速排序D.堆排序堆排序快速排序快速排序归并排序归并排序查找与排序查找与排序97v自测题自测题下面四种排序算法中，稳定的算法是下面四种排序算法中，稳定的算法是 A.快速排序快速排序B.归并排序归并排序C.堆排序堆排序D.希尔排序希尔排序查找与排序查找与排序98v自测题自测题在基于排序码比较的排序算法中，哪种在基于排序码比较的排序算法中，哪种算法的最坏情况下的时间复杂度不高于算法的最坏情况下的时间复杂度不高于O(nlog2n)？A.冒泡排序冒泡排序B.希希尔排序排序C.归并排序并排序D.快速排序快速排序 查找与排序查找与排序99v自测题自测题下列排序算法中，时间复杂度不受数据下列排序算法中，时间复杂度不受数据初始状态影响，恒为初始状态影响，恒为O(nlog2n）的是）的是A.堆排序堆排序B.冒泡排序冒泡排序C.直接直接选择排序排序D.快速排序快速排序查找与排序查找与排序100v自测题自测题排序方法中，从未排序序列中依次取出排序方法中，从未排序序列中依次取出元素与已排序序列中的元素进行比较，元素与已排序序列中的元素进行比较，将其放入已排序序列的正确位置上的方将其放入已排序序列的正确位置上的方法称为法称为A插入排序插入排序B选择排序排序C快速排序快速排序D归并排序并排序 查找与排序查找与排序101v自测题自测题输入输入N10个只有个只有1位数字的整数，试设位数字的整数，试设计计O(N)复杂度的算法将其排序。复杂度的算法将其排序。答案：基数排序答案：基数排序查找与排序查找与排序102v自测题自测题假设有假设有n个值不同数据元素存储在顺序表个值不同数据元素存储在顺序表中，要求不经过完全排序就从中选出自中，要求不经过完全排序就从中选出自小到大顺序的前小到大顺序的前m(mn)个元素，试问要个元素，试问要如何进行才能使最坏情况下的元素间所如何进行才能使最坏情况下的元素间所作的比较次数最少？作的比较次数最少？查找与排序查找与排序改造堆排序，建立最小堆。改造堆排序，建立最小堆。103v自测题自测题将将100000个数字按升序排列，有一个数字排错，个数字按升序排列，有一个数字排错，如何纠错？请写出效率最高的方法。两个数字如何纠错？请写出效率最高的方法。两个数字呢？呢？答案：插入排序答案：插入排序附加：若有附加：若有k个数字排错，且不知顺序，如何判个数字排错，且不知顺序，如何判断是升序还是降序？断是升序还是降序？答案：答案：只需要比较只需要比较2k+1对相邻元素的相对大小，对相邻元素的相对大小，其中至多有其中至多有k对元素的相对大小是错的，另外至对元素的相对大小是错的，另外至少少k+1对相邻元素的相对大小是一致的。对相邻元素的相对大小是一致的。 查找与排序查找与排序104v自测题自测题给定一个带有表头结点的单链表，结点结构为给定一个带有表头结点的单链表，结点结构为.。假设该链表只给出了头指针。假设该链表只给出了头指针L，请，请设计尽可能高效的算法按设计尽可能高效的算法按data域递增排序域递增排序 。答案：答案：冒泡排序冒泡排序。因为链表是因为链表是单向单向的，而冒泡排的，而冒泡排序序只比较并交换相邻元素只比较并交换相邻元素，故比较容易实现。作，故比较容易实现。作为提高效率的手段，为提高效率的手段，Flag检查每一趟冒泡过程中检查每一趟冒泡过程中是否有元素进行了交换，若整趟冒泡过程中都没是否有元素进行了交换，若整趟冒泡过程中都没有任何元素交换，则说明链表已经有序，就可以有任何元素交换，则说明链表已经有序，就可以直接跳出直接跳出while循环了。循环了。 查找与排序查找与排序datanext105v自测题自测题借助于快速排序的算法思想，在一组无序借助于快速排序的算法思想，在一组无序的记录中查找第的记录中查找第k大元。请编写出算法并简大元。请编写出算法并简要说明算法思想。要说明算法思想。答案：答案：首先选支点将集合划分为首先选支点将集合划分为2部分；部分；S1和和S2若若k|S2|+1，则第，则第k大元必在大元必在S1中，并且是第中，并且是第(k-|S2|-1)大元。递归大元。递归查找与排序查找与排序106v自测题自测题已知散列表大小为已知散列表大小为11，散列函数为，散列函数为H(x)=x%11，冲突解决策略为线性探测（冲突解决策略为线性探测（LinearProbing）。）。给定当前散列表状态如下给定当前散列表状态如下：请写出请写出:(1)一个可能的元素插入序列（当有多种插入选择时，一个可能的元素插入序列（当有多种插入选择时，总是选择最小的候选数字）；总是选择最小的候选数字）；(2)针对上述给定的散列函数和冲突解决方法设计算法，针对上述给定的散列函数和冲突解决方法设计算法，读入任意散列表状态读入任意散列表状态,可给出一个可能的元素插入可给出一个可能的元素插入序列。序列。查找与排序查找与排序0134567892331123438272232131021107v答案答案（1）1、13、12、21、33、34、38、27、22、32（2）事实上这是拓扑排序的应用：若在插入）事实上这是拓扑排序的应用：若在插入x的过程中遇到冲突，的过程中遇到冲突，则则冲突元必然在冲突元必然在x之前被插入之前被插入，所以是，所以是x的的前驱结点前驱结点。算法思。算法思路为：路为：第第1步：构造有向图。将每个元素作为有向图中的一个结点，比步：构造有向图。将每个元素作为有向图中的一个结点，比较每个元素较每个元素x的散列值的散列值H(x)与该元素所在单元的地址与该元素所在单元的地址I(x)，若，若两者不相等，则遵循冲突解决方法从两者不相等，则遵循冲突解决方法从H(x)开始查找开始查找x，并且，并且为查找过程中探测的每一个结点都添加一条指向为查找过程中探测的每一个结点都添加一条指向x的边。的边。第第2步：对该图应用拓扑排序，得到的序列就是一个可能的元素步：对该图应用拓扑排序，得到的序列就是一个可能的元素插入序列。若还要满足插入序列。若还要满足“当有多种插入选择时，总是选择最当有多种插入选择时，总是选择最小的候选数字小的候选数字”，则在实现时将所有入度为，则在实现时将所有入度为0的结点保存在的结点保存在一个最小堆里即可。一个最小堆里即可。 查找与排序查找与排序0134567892331123438272232131021108v其他可能的题目其他可能的题目实现指定的排序法并略做修改实现指定的排序法并略做修改双向冒泡双向冒泡二路插入排序二路插入排序表排序表排序+任何一种排序任何一种排序查找与排序查找与排序109110