数据结构辅导-树型结构

数据结构辅导-树型结构树形结构部份：基本知识点：树的定义及相关术语、树的表示及树的性质。二叉树的定义、二叉树的性质、满二叉树和完全二叉树的定义、二叉树的顺序存储和链式存储、二叉树的遍历过程、二叉树的线索化过程、哈夫曼树的定义与构造方法以及二叉树与森林之间的转换。递归的相关概念。重点：二叉树的性质、二叉树的遍历（二叉树各种遍历方法及它们所确定的序列之间的关系）、二叉树的线索化方法，构造哈夫曼树。递归模型、递归算法的执行过程和递归设计思想。难点：二叉树上各种算法特别是递归算法的设计和非递归算法的设计。将递归算法转化为非递归算法。（重点要求掌握二叉树的二叉链表存储表示结构下的递归算法。）树形结构知识体系结构树二叉树二叉树和树例题：已知A[n]为整数数组，编写一个递归算法，求n个元素的平均值。解：算法如下：intaverage(intA[]，intn){if(n==1)returnA[0];elsereturn(average(A，n-1)*(n-1)+A[n-1])/n；}例6.2：有一个不带头结点的单链表，其结点类型如下：typedefintElemType;typedefstructnode{ElemTypedata;structnode*next;}Node;设计如下递归算法：（1）求以H为头指针的单链表的结点个数。（2）正向显示以H为头指针的单链表的所有结点值。（3）反向显示以H为头指针的单链表的所有结点值。（4）删除以H为头指针的单链表中值为x的第一个结点。（5）删除以H为头指针的单链表中值为x的所有结点。（6）求出以H为头指针的单链表中最大结点值。（7）求出以H为头指针的单链表中最小结点值。解：递归算法分别如下：intCount(Node*H){if(H==0)return0;elsereturn1+Count(H->next);}(2)voidtraverse(Node*H){if(H==0)return;cout<<H->data;traverse(H->next);}(3)voidtraverseR(Node*H){if(H==0)return;ctraverse(H->next);out<<H->data;}(4)voiddelFirstx(Node*H,ElemTypex){Node*t;if(H==0)return;if(H->data==x){t=H;H=H->next;deletet;return;}delFirstx(H->next,x);}(5)voiddelAllx(Node*H,ElemTypex){Node*t;if(H==0)return;if(H->data==x){t=H;H=H->next;deletet;}delAllx(H->next,x);}(6)ElemTypeMaxv(Node*H){ElemTypem;if(H->next==0)returnH->data;m=Maxv(H->next);if(m>H->data)returnm;elsereturnH->data;}(7)ElemTypeMinv(Node*H){ElemTypem;if(H->next==0)returnH->data;m=Minv(H->next);if(m<H->data)returnm;elsereturnH->data;}注意：完全二叉树有注意：完全二叉树有n0=n2+1n1=1或者n1=0例题一棵完全二叉树上有1001个结点，问其中叶子结点个数是多少？答案：501注：n0+n1+n2=n,n-1=n1+2n2,n0=n2+1,n1=0或n1=1;n=2*n0+n1-1，n=1001，故n1=0，n0=501。例题一棵有124个叶子结点的完全二叉树中，最多有多少个结点？答案：248注：n=n0+n1+n2=n0+n1+n0-1=2*n0+n1-1,n1最多为1。n=2*124=248。例题设有13个值，用它们组成一棵哈夫曼树，问该哈夫曼树有多少个结点？答案：25注：有m个叶结点的哈夫曼树共有2m-1个结点。2*13-1=25。例题问8层完全二叉树至少有多少个结点？答案：128注：1+2+4+8+16+32+64+1=128例题问拥有100个结点的完全二叉树的最大层数是多少？答案：7例题已知二叉树有50个叶子结点，则该二叉树的结点总数至少是多少？答案：99注：n0=n2+1;n0=50,n2=49,n1=0或1，n=n0+n1+n2=99。例题：已知二叉树用二叉链表表示，写出二叉树的先序遍历、中序遍历、后序遍历的递归算法。解：设存储结构如下：structBitreeNode{ElemTypedata;BitreeNode*left,*right;};先序遍历二叉树的的方法是：先访问根结点，然后按先序遍历方法访问左子树，再按先序遍历方法访问右子树。则先序遍历的递归算法如下：voidPreOrder(BitreeNodeode*Bt){if(Bt){cout<<Bt->data;PreOrder(Bt->left);PreOrder(Bt->right);}}中序遍历二叉树的方法是：先按中序遍历方法访问左子树，然后访问根结点，再按中序遍历方法访问右子树。则中序遍历的递归算法如下：voidInOrder(BitreeNode*Bt){if(Bt){InOrder(Bt->left);cout<<Bt->data;InOrder(Bt->right);}}后序遍历二叉树的方法是：先按后序遍历方法访问左子树，然后按后序遍历方法访问右子树，最后访问根结点。则后序遍历的递归算法如下：voidPostOrder(BitreeNode*Bt){if(Bt){PostOrder(Bt->left);PostOrder(Bt->right);cout<<Bt->data;}}注意：有关二叉树的算法，一般是用二叉链表作存储结构注意：有关二叉树的算法，一般是用二叉链表作存储结构根结点左子树右子树例题：已知二叉树用二叉链表表示，编写算法求二叉树的结点个数。解：设存储结构如下：structBitreeNode{ElemTypedata;BitreeNode*left,*right;};二叉树的结点个数包括三部分：左子树的结点个数、根结点、右子树的结点个数。因此二叉树的结点个数等于这三部分相加。求二叉树的结点个数的算法如下：intNodes(BitreeNode*Bt){if(!Bt)return0;elsereturn1+Nodes(Bt->left)+Nodes(Bt->right);}例题：假设二叉树用二叉链表表示，分别编写算法求叶结点的个数、求度为1的结点的个数、求度为2的结点的个数。解：设存储结构如下：structBitreeNode{ElemTypedata;BitreeNode*left,*right;};求二叉树的叶结点的个数的算法如下：intleafs(BitreeNode*Bt){if(!Bt)return0;elseif(!Bt->left&&!Bt->right)return1;elsereturnlefts(Bt->left)+lefts(Bt->right);}求二叉树的度数为1的结点个数的算法如下：intNodesOne(BitreeNode*Bt){if(!Bt)return0;elseif((!Bt->left&&Bt->right)||(Bt->left&&!Bt->right))return1+NodesOne(Bt->left)+NodesOne(Bt->right)elsereturnNodesOne(Bt->left)+NodesOne(Bt->right);}求二叉树的度数为2的结点个数的算法如下：intNodesTwo(BitreeNode*Bt){if(!Bt)return0;elseif(Bt->left&&Bt->right)return1+NodesTwo(Bt->left)+NodesTwo(Bt->right);elsereturnNodesTwo(Bt->left)+NodesTwo(Bt->right);}例题：假定二叉树采用二叉链存储结构，设计一个算法，删除该二叉树，并释放所有的结点。解：设存储结构如下：structBitreeNode{ElemTypedata;BitreeNode*left,*right;};删除二叉树的算法如下：voiddeleteBitree(BitreeNode*Bt){if(Bt){deleteBitree(Bt->left);deleteBitree(Bt->right);delete(bt);bt=0;}}例题：编写一个算法，将用二叉链表表示的二叉树的所有结点的左右子树交换。解：设存储结构如下：structBitreeNode{ElemTypedata;BitreeNode*left,*right;};算法如下：voidexchange(BiTreeNode*&T){if(T==0)return;BiTreeNode*temp;temp=T->left;T->left=T->right;T->right=temp;exchange(T->left);exchange(T->right);}例题：写一个算法，建立二叉树的二叉链表。解：（最简单的算法是用扩充先序序列）假设二叉树的存储结构是：TypedefcharElemType;typedefstructBitreeNode{ElemTypedata;BitreeNode*left,*right;}BitreeNode,*Bitree假设输入的是二叉树的扩充先序序列，如果某个子树为空则用特殊的标志符号。假设二叉树的结点用字符来表示，空的子树用特殊符号#来表示，则算法如下：voidcreat_bitree(Bitree&T){//按扩展的先序序列输入结点，输入‘＃’表示空。ElemTypech;cin>>ch;if(ch==’#’)T=0;else{T=newBitreeNode;T->data=ch;creat_bitree(T->left);creat_bitree(T->right);}}例题：已知一棵二叉树的前序和中序序列，画出该二叉树并求其后序序列。前序序列：A，B，C，D，E，F，G，H，I，J中序序列：C，B，A，E，F，D，I，H，J，G例题：已知一棵二叉树的中序序列和后序序列，画出该二叉树并写出其前序序列。中序序列：C，B，A，E，F，D，I，H，J，G后序序列：C，B，F，E，I，J，H，G，D，A例题：假设一棵二叉树的先序序列是EBADCFHGIKJ和中序序列是ABCDEFGHIJK。请画出该二叉树并写出其后序序列。解：该二叉树是EEBADCFHJKIG该二叉树的后序序列是：ACDBGJKIHFE。例题：假设一棵二叉树的中序序列为DCBGEAHFIJK和后序序列为DCEGBFHKJIA。请画出该二叉树并写出其先序序列。例题：已知二叉树的先序序列是ABDEHCFIG，中序序列是DBHEAFICG，请画出该二叉树。例题：假设一棵二叉树的层次序列为ABCDEFGHIJ和中序序列为DBGEHJACIF。请画出该二叉树并写出其先序序列和后序序列。例题：己知一棵二叉树先序遍历的结果是ABCDEFG，中序遍历的结果是CBDAFGE。（1）画出此二叉树；（2）写出其后先序遍历的结果。（答案：后序序列:CDBGFEA）解：根据二叉树的先序序列和中序序列，该二叉树是：AABCEDFG该二叉树的后序序列是：CDBGFEA。例题：从空树起，依次插入关键词{37，50，42，18，48，12，56，30，23}，建立一棵二叉排序树，然后删除结点37，分别画出该二叉树及删除37之后的二叉树。例题：输入下列整数序列，画出建立的二叉排序树，并画出删除79后的二叉排序树。{79，95，64，50，21，99，67，85，65}解：建立和二叉排序树是：65652150646799859579删除结点79后的二叉排序树是：212150646599859567例题：输入下列整数序列，画出建立的二叉排序树，并画出删除70后的二叉排序树。（70，88，64，55，23，100，67，80，58）。例题：从空树起，依次插入关键词{45，37，48，25，17，67，41，40，54，57，44，49}，建立一棵二叉排序树，请画出该二叉排序树。例题：从空树起，依次插入关键词{34，37，58，25，17，16，11，70，24，27，31，19}，建立一棵二叉排序树，请画出该二叉排序树。解：从空树起，依次插入相应关键字，建立的二叉排序树是：34343758703127192411161725例题：对于下面给出的数据序列，构造一棵哈夫曼树，并求出其带权路径长度。{12，15，6，7，10，18}例题：对于下面给出的数据序列，构造一棵哈夫曼树，并求出其带权路径长度。{18，14，13，7，8，17}解：构造的哈夫曼树如下：2727324515271817781314由此求出其带权路径长度是：WPL=（7+8+13+14）*3+（17+18）*2=196例题：设给定权集散地W={5，6，7，12，13，15}，试构造关于W的一棵哈夫曼树，并求其加权路径长度WPL。例题：已知字符：C1，C2，C3，C4，C5，C6的权分别为：17，5，16，4，8，11，请构造相应的赫夫曼树，并给出相应字符的赫夫曼编码。（答案：c1:10，c2:1111，c3:01，c4:1110，c5:110，c6:00）例题：已知字符：A，B，C，D，E，F的权分别为：4，5，8，11，16，17，请构造相应的赫夫曼树，并给出相应字符的赫夫曼编码。例题：已知字符：A，B，C，D，E，F的权分别为：18，14，13，7，8，17，请构造相应的赫夫曼树，并给出相应字符的赫夫曼编码。解：构造的哈夫曼树如下：2727324515271817781314按照左子树对应于0,右子树对应于1的方法，得到各字符的哈夫曼编码分别是：A（18）：10B（14）：111C（13）：110D（7）：000E（8）：001F（17）：01例题：[选择题]1、树中所有结点的度等于所有结点数加______。(A)0(B)1(C)-1(D)22、在一棵树中，______没有前驱结点。(A)树枝结点(B)叶子结点(C)树根结点(D)空结点3、在一棵二叉树的二叉链表中，空指针域数等于非空指针域数加_________。(A)2(B)1(C)0(D)-14、在一棵具有32个结点的二叉树中，所有结点的空子树个数等于_________。(A)32(B)31(C)33(D)645、在一棵具有35个结点的完全二叉树中，该树的深度为_________。(A)5(B)6(C)7(D)86、利用n个结点生成的哈夫曼树中共有_________个结点。(A)n(B)n+1(C)2n(D)2n-17、利用{3，6，8，12}这四个值作为叶子结点的权，生成一棵哈夫曼树，该树的带权路径长度为_________。(A)55(B)29(C)58(D)388、利用{3，6，8，12，5，7}这六个值作为叶子结点的权，生成一棵哈夫曼树，该树的深度为_________。(A)3(B)4(C)5(D)69、若二叉树采用顺序方法存储，则下列4种运算中，_________最容易实现。(A)先序遍历二叉树(B)层次遍历二叉树(C)判断二个结点是否在同一层上(D)根据结点的值查找其存储位置10、设m、n为一棵二叉树上的两个结点，在中序遍历时，n在m前的条件是_________。(A)n在m右方(B)n是m祖先(C)n在m左方(D)n是m子孙11、线索二叉树是一种_________结构。(A)逻辑(B)逻辑和存储(C)物理(D)线性12、按照二叉树的定义，具有3个结点的二叉树有_________种。(A)3(B)4(C)5(D)613、具有10个叶子结点的二叉树中，有_________个度为2的结点。(A)8(B)9(C)10(D)1114、深度为5的二叉树中至多有_________个结点。(A)10(B)16(C)31(D)3215、某二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树一定是_________。(A)空树或只有一个结点(B)完全二叉树(C)二叉排序树(D)高度等于其结点数16、任何一棵二叉树的叶子结点在先序、中序、后序遍历序列中其相对次序_________。(A)不会发生改变(B)发生改变(C)不能确定(D)以上都不对17．一棵5层满二叉树中，结点总数为（）个。(A)33(B)32(C)31(D)3018.设有6个结点的无向图，该图至少应有()条边才能确保是一个连通图。(A)5(B)6(C)7(D)819、二叉树若用顺序方法存储，则下列4种运算中的______最容易实现。(A)先序遍历二叉树(B)判断两个结点是否在同一层上(C)层次遍历二叉树(D)根据结点的值查找其存储位置例题：己知完全二叉树的第7层有8个结点（根为第0层），则其叶子结点数是68。例题：设二叉树有N个结点，采用二叉链表存储结构，有N-1个非空指针域，有N+1个空的批针域。例题：一棵深度为5的二叉树（根的层次为0），最多有31个结点。例题：具有100个结点的完全二叉树的深度是7。例题：己知完全二叉树的第八层有8个结点（根为第一层），则其叶子结点数是68。例题：对于任何一棵二叉树T，如果其终端结点数为n0,度为2的结点数为n2，则n0=n2+1。例题：有m个叶结点的哈夫曼树所具有的结点数为2m+1。例题：若某二叉树的叶子结点数为1，则其先序序列和后序序列一定相反。例题：有64个结点的完全二叉树的深度为7。例题：按照二叉树的定义，具有三个结点的二叉树有5种。例题：高度为4，度为5的树中，至少有8个结点，至多有156个结点。例题：深度为N的完全二叉树至少有2N-1个结点，至多有2N-1个结点，若按自上而下，从左至右次序给结点编号（从1开始），则编号最小的叶子结点的编号是2N-1。例题：向二叉排序树中插入一个结点，所需比较的次数可能大于此二叉排序树的高度。对吗？例题：完全二叉树中，若一个结点没有左儿子，由必是树叶。对吗？答案：正确。例题：是否存在这样的二叉树，对它采用任何次序的遍历，其结果相同？答案：存在。例题：删除二叉排序树一个结点，然后再重新插入进去，得到的二叉排序树与原来的二叉排序树相同吗？答案：不一定相同。例题：按照二叉树的定义，具有三个结点的二叉树有多少种？答案：有五种。例题：二叉排序树中，新结点总是作为树叶来插入的。对吗？答案：正确。例题：二叉树与度为2的树有差别吗？答案：有差别。例题：二叉树的顺序存储，最容易实现的运算之一是层次遍历运算。说明：二叉树的五种情形：（1）空二叉树，（2）只有一个根结点，（3）根结点和左子树，（4）根结点和右子树，（5）根结点和左右子树说明：三个结点的二叉树的情形：图结构部份：基本知识点：图的基本概念、图的存储结构（主要是邻接矩阵和邻接表）、图的遍历算法（深度优先遍历和广度优先遍历）、图的生成树和最小生成树（Prim算法和Kruskal算法）、最短路径（Dijkstra算法和Floyd算法）、关键路径和拓扑排序。重点：图的各种存储结构和遍历算法（递归和非递归算法）设计，构造最小生成树，生成最短路径、生成图的关键路径，拓扑排序的应用。难点：图的遍历算法和图的各种复杂算法的设计。例题：给定一个带权图，按照普里姆(Prim)算法，从顶点v1出发生成最小生成树，按生成次序写出各条边。例题：若连通图G的顶点个数为n，则G的生成树的边数为n－1。例题：有n个结点的强连通有向图G至少有n条弧。例题：有n个结点的无向图的边数最多是（n(n-1)/2）。例题：有20个结点的强连通有向图G至少有21条弧。例题：求最短路径的DIJKSTRA算法的时间复杂度为O(n2)。例题：一棵树中的叶子结点数与其对应的二叉树中的叶子结点数一般情况下是不一样的。例题：有向图用邻接矩阵表示后，顶点i的入度等于邻接矩阵中第i列的元素个数。例题：具有4个顶点的无向完全图有6条边。例题：在一个图中，所有顶点的度数之和等于所有边数的2倍。例题：N个顶点的连通图至少有N-1条边。例题：图的广度（宽度）优先遍历类似于树（或二叉树）的层次遍历。例题：将一棵树转换为二叉树表示后,该二叉树的根结点没有右子树。例题：存储图的邻接矩阵中，邻接矩阵的大小与图的顶点个数有关，与图的边数无关。例题：可以进行拓扑排序的有向图一定是无环图。如果一个有向图，无法进行拓扑排序，则一定是有环的图。例题：在一个有向图的邻接表中，如果某个顶点的链表为空，则该顶点的出度一定为0。例题：在一个有向图的逆邻接表中，如果某个顶点的链表为空，则该顶点的入度一定为0。例题：如果有向图G=（V，E）的拓扑序列唯一，则图中必定仅有一个顶点的入度为0，一个顶点的出度为0。例题：给出一个有向图或无向图的邻接矩阵，请画出该图，或画出该图的邻接表表示。例题：给出一个无向图的邻接矩阵，请画出该图，或画出该图的邻接表（逆邻接表）表示。例题：如果一个有向图G=(V，E)的邻接矩阵如下：请画出该有向图。解：设该有向图对应的顶点分别是0，1，2，3，4，则该有向图是：001342例题：设一个无向图的邻接矩阵如下：（1）请画出该无向图。（2）画出该无向图的邻接表。例题：给出一个图G如下：v3v3v5v4v6v7v2v1（1）请写出其邻接矩阵。（2）请画出其邻接表。例题：给定一个图如下：007261453（1）请写出其邻接矩阵。（2）请画出其邻接表。例题：给定一个有向图如下：V211V211V411V311V511V111V011（1）请写出该图的邻接矩阵。（2）请画出该图的邻接表。（3）请画出该图的逆邻接表。解：（1）该图的邻接矩阵是：（2）该图的邻接表是：0012345340541404（3）该图的逆邻接表是：0012^345142053212例题：给定一个有向图如下：V211V211V411V311V511V111V011（1）请写出该图的邻接矩阵。（2）请画出该图的邻接表。（3）请画出该图的逆邻接表。（4）请写出该有向图的一个拓扑序列。例题：给出一个无向带权图G如下：77956755381273466524请画出该图的一棵最小生成树。例题：给出一个无向带权图G=（V，E）的表示如下：V={V0，V1，V2，V3，V4，V5，V6}，E={(V0,V1,8),(V1,V5,4),(V0,V5,9),(V1,V2,5),(V2,V5,3),(V2,V3,6),(V3,V5,8),(V4,V5,4),(V3,V4,8),(V3,V6,3),(V4,V6,7)}（1）请画出该图。（2）请画出该图的最小生成树。（3）请画出该图的邻接表。（4）请写出该图的邻接矩阵。例题：给定下面的一个无向图G=(V,E)，（1）写出其邻接矩阵；（2）画出其邻接表；（3）根据邻接矩阵，写出其从0出发按深度优先遍历的结点序列；（4）根据邻接矩阵，写出其从0出发按广度优先遍历的结点序列；（5）根据邻接表，写出其从0出发按深度优先遍历的结点序列；（6）根据邻接表，写出其从0出发按广度优先遍历的结点序列；00123465987例题：[选择题]1、一个图的简单路径是指_________。(A)任何一条边在这条路径上不重复出现(B)任何一个顶点在这条路径上不重复出现(C)这条路径由一个顶点序列构成，不包含边(D)这条路径由一个边的序列构成，不包含顶点2、无向图的邻接矩阵是一个_________。(A)对称矩阵(B)零矩阵(C)上三角矩阵(D)对角矩阵3、在一个无向图中，所有顶点的度数之和等于边数的______倍。(A)1/2(B)1(C)2(D)44、一个有n个顶点的无向图至多有______条边。(A)n(B)2n(C)n(n-1)(D)n(n-1)/25、具有6个顶点的无向图至少应有______条边才能确保是一个连通图。(A)5(B)6(C)7(D)86、在一个具有n个顶点的无向图中，要连通全部顶点至少需要______条边。(A)n(B)n+1(C)n-1(D)n/27、下列图中，______的邻接矩阵是对称矩阵。(A)有向图(B)无向图(C)AOV网(D)AOE网8、对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小为______。(A)n行n列(B)n-1行n-1列(C)n行1列(D)n-1行1列9、如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是_________。(A)完全图(B)连通图(C)有回路(D)一棵树10、采用邻接表存储的图的深度优先遍历算法类似于二叉树的_________算法。(A)先序遍历(B)中序遍历(C)后序遍历(D)层次遍历11、采用邻接表存储的图的广度优先遍历算法类似于二叉树的_________算法。(A)先序遍历(B)中序遍历(C)后序遍历(D)层次遍历12、任何一个无向连通图_________最小生成树。(A)只有一棵(B)有一棵或多棵(C)一定有多棵(D)可能不存在13、一个无向连通图的生成树是含有该连通图的全部顶点的_________。(A)极小连通子图(B)极小子图(C)极大连通子图(D)极大子图14、若图的邻接矩阵中主对角线上的元素全是0，其余元素全是1，则可以断定该图一定是_________。(A)无向图(B)不是带权图(C)有向图(D)完全图15、关键路径是AOE网中的_________。(A)从源点到汇点的最长路径(B)从源点到汇点的最短路径(C)最长回路(D)最短回路查找与排序部份1、查找基本知识点：查找及相关概念，各种顺序表的查找算法和性能分析，各种树表的查找算法和性能分析，哈希表的构造、查找和性能分析。顺序查找法和二分查找法、哈希表、二叉排序树重点：各种顺序表和树表的查找算法和性能分析，构造哈希表、冲突处理和性能分析。难点：各种查找算法设计和性能分析。2、内部排序基本知识点：内排序的概念；各种排序的方法。（排序算法中用到的一些概念。）重点：各种排序算法的性能特点；各种排序算法的比较和选择。冒泡排序、直接选择排序、直接插入排序、快速排序、归并排序、堆排序。难点：复杂排序算法设计。[选择题]：1、在二叉排序树中，凡是新插入的结点，都是没有_______的。（A）孩子（B）关键字（C）平衡因子（D）赋值2、只有在顺序存储结构上才能实现的的查找方法是______法。（A）顺序查找（B）二分查找（C）树型查找（D）哈希查找3、在数据元素有序，元素个数较多而且固定不变的情况下，宜采用_______法。（A）二分查找（B）分块查找（C）二分排序树查找（D）顺序查找4、设有n个关键字，散列查找法的平均查找长度是______。（A）O（1）（B）O（n）(C)O(log2n)(D)O(n2)5、下列排序方法中，时间复杂性不受数据初始状态影响，恒为O(nlog2n)的是______。（A）堆排序（B）冒泡排序（C）直接选择排序（D）快速排序6、下列排序方法中，某一趟结束后未必能选出一个元素放在其最终位置上的是______。（A）堆排序（B）冒泡排序（C）直接插入排序（D）快速排序7、下列排序方法中，在待排序的数据已经为有序时，花费时间反而最多的是______。（A）快速排序（B）希尔排序（C）冒泡排序（D）堆排序8、依次将待排序序列中的元素插入到有序子序列中并扩大有序子序列的排序方法是______。（A）快速排序（B）直接插入排序（C）冒泡排序（D）堆排序9、若表R在排序前已按关键字正序排列，则______方法的比较次数最少。(A)直接插入排序(B)快速排序(C)归并排序(D)直接选择排序10、假设表A中每个元素距其正序的最终位置不远，采用__B____方法最节省时间。(A)堆排序(B)直接插入排序(C)快速排序(D)直接选择排序11、在下列排序方法中，关键字比较的次数与记录的初始排列次序无关的是______。(A)希尔排序(B)冒泡排序(C)直接插入排序(D)直接选择排序12、快速排序方法在______情况下最不利于发挥其长处。(A)要排序的数据量太大(B)要排序的数据中含有多个相同的值(C)要排序的数据已基本有序(D)要排序的数据个数为奇数13、数据表中有100000个元素，如果仅要求求出其中最大的10个元素，则采用______方法最节省时间。(A)堆排序(B)希尔排序(C)快速排序(D)基数排序14、内排序方法的稳定性是指______。(A)该排序方法不允许有相同的关键字记录(B)该排序方法允许有相同的关键字记录(C)平均时间为O(nlog2n)的排序方法(D)以上都不对15、以下排序方法中，______是不稳定的排序方法。(A)直接插入排序(B)冒泡排序(C)归并排序(D)堆排序16、在以下各排序方法中，______是稳定的排序方法。(A)直接插入排序和快速排序(B)快速排序和堆排序(C)直接选择排序和归并排序(D)归并排序和冒泡排序17、在以下各排序方法中，______是稳定的排序方法。(A)直接选择排序(B)二分插入排序(C)希尔排序(D)快速排序18、若需要在O(nlog2n)的时间内完成对顺序表的排序，且要求排序是稳定的，则可选择的排序方法是______。(A)快速排序(B)堆排序(C)归并排序(D)直接插入排序19、以下各排序方法中，辅助空间为O(n)的是______。(A)堆排序(B)归并排序(C)希尔排序(D)快速排序例题：对于有序表{1，2，3，4，5，6，7，8，9}，采用顺序查找时，平均查找长度是45/9=5，采用二分查找时平均查找长度是25/9。（假定等概率且查找成功）。例题：有n个数存放在一维数组A[1..n]中，在进行顺序查找时，这n个数的排列有序或无序，其平均查找长度是相同的。例题：在有序表A[1….20]中，采用二分查找算法查找元素值等于A[12]的元素，所比较的元素的下标依次为10、15、12。说明：对于二分查找法，每一次查找的下标：mid=(low+high)/2。例题：衡量查找算法性能好坏的主要标准是关键字的平均比较次数。例题：在各种查找方法中，平均查找长度与结点个数N无关的查找方法是哈希表查找法。例题：顺序查找的平均查找长度是O(n)。例题：对于同一组结点，由于建立二叉排序树时插入结点的先后次序不同，所构成的二叉排序树的形态及深度也不同，所以含有n个结点的二叉排序树不唯一。例题：向二叉排序树中插入一个结点，所需比较的次数不可能大于此二叉排序树的高度。例题：什么是堆？如何判断给定的一个序列是堆？{99，85，98，77，80，60，81，39，19，11，66}{99，98，85，81，80，77，65，59，39，19，12}{99，85，39，75，80，59，65，98，82，12，21}{12，23，35，55，65，70，79，83，86，97，99}例题：快速排序的速度在所有的排序方法中是最快的，且所需的附加空间也最小。例题：给定一个关键码集合，写出按某种排序算法（冒泡排序、直接选择排序、直接插入排序、快速排序、归并排序、堆排序）执行排序后的各趟关键码状态。例如：Key＝{50，40，66，88，72，18，20，45，37}解一：（冒泡排序算法算法后各趟的关键码状态如下）初始状态：{50，40，66，88，72，18，20，45，37}第一趟：{40，50，66，72，18，20，45，37，88}第二趟：{40，50，66，18，20，45，37，72，88}第三趟：{40，50，18，20，45，37，66，72，88}第四趟：{40，18，20，45，37，50，66，72，88}第五趟：{18，20，40，37，45，50，66，72，88}第六趟：{18，20，37，40，45，50，66，72，88}第七趟：{18，20，37，40，45，50，66，72，88}至此，没有交换，排序结束。解二：（直接选择排序算法算法后各趟的关键码状态如下）初始状态：{50，40，66，88，72，18，20，45，37}第一趟：{50，40，66，37，72，18，20，45，88}第二趟：{50，40，66，37，45，18，20，72，88}第三趟：{50，40，20，37，45，18，66，72，88}第四趟：{18，40，20，37，45，50，66，72，88}第五趟：{18，40，20，37，45，50，66，72，88}第六趟：{18，37，20，40，45，50，66，72，88}第七趟：{18，20，37，40，45，50，66，72，88}第八趟：{18，20，37，40，45，50，66，72，88}至此，排序结束。解三：（直接插入排序算法算法后各趟的关键码状态如下）初始状态：{50，40，66，88，72，18，20，45，37}第一趟：{40，50，66，88，72，18，20，45，37}第二趟：{40，50，66，88，72，18，20，45，37}第三趟：{40，50，66，88，72，18，20，45，37}第四趟：{40，50，66，72，88，18，20，45，37}第五趟：{18，40，50，66，72，88，20，45，37}第六趟：{18，20，40，50，66，72，88，45，37}第七趟：{18，20，40，45，50，66，72，88，37}第八趟：{18，20，40，37，45，50，66，72，88}至此，排序结束。例题：已知序列（12，4，17，10，7，30），用冒泡排序法对其进行递增排序，写出每一趟的排序结果。例题：已知序列（45，78，17，33，57，26），用冒泡排序法对其进行递增排序，写出每一趟的排序结果。解：对该序列进行冒泡排序，每一趟结果如下：1、（45，17，33，57，26，78）2、（17，33，45，26，57，78）3、（17，33，26，45，57，78）4、（17，26，33，45，57，78）5、（17，26，33，45，57，78）至此，算法结束。例题：对于给定结点序列的关键字如下：{78，35，17，15，48，33，27}，用直接选择排序法对其进行递增排序，请写出每一趟的排序结果。解：对该序列进行直接选择排序，每一趟结果如下：1、{15，35，17，78，48，33，27}2、{15，17，35，78，48，33，27}3、{15，17，27，78，48，33，35}4、{15，17，27，33，48，78，35}5、{15，17，27，33，35，78，48}6、{15，17，27，33，35，48，78}至此，排序结束。例题：对于给定结点序列的关键字如下：{78，35，17，15，48，33，27}，用直接插入排序法对其进行递增排序，请写出每一趟的排序结果。解：对该序列进行直接插入排序，每一趟结果如下：1、{35，78，17，15，48，33，27}2、{17，35，78，15，48，33，27}3、{15，17，35，78，48，33，27}4、{15，17，35，48，78，33，27}5、{15，17，33，35，48，78，27}6、{15，17，27，33，35，48，78}至此，排序结束。例题：对于给定结点序列的关键字如下：{28，35，17，65，48，54，57}，用选择排序法对其进行递增排序，请写出每一趟的排序结果。例题：以关键字序列{265，301，751，129，937，863