数据结构复习知识点.pdf

第一章：概论知识点：1、数据结构的基本概念：数据、数据元素、数据项等之间的区和联系。2、数据的逻辑结构，数据的存储结构、数据的逻辑结构和存储结构各有哪些基本类型、数据的基本逻辑结构有什么特点。我们所学的几种常见的数据结构中（顺序表、链表、队列、栈、串、树、图等），哪些是线性数据结构，哪些是非线性数据结构？3、算法复杂性的概念、内容和算法复杂性的计算。简单算法复杂性的判断：(1)sum=0;for(i=1;i=n;i+)sum=sum+i;其中 i=1,2,3,k,需频度 k=n，所以复杂性为 O(n)(2)i=1;while(i=n)i=i+2;其中 i=1,3,5,(2k-1),需 2k-1=n，则频度 k=(n+1)/2，复杂性为 O(n)(3)i=1;while(i=n)i=i*3;其中 i=1,3,32,3k,需 3k=n，则频度 k=log3n，复杂性为 O(log3n)(4)i=1;while(i*i=n)i+;其中 i=1,2,3,k，需 k2=n，则频度 k=n1/2，复杂性为 O(n1/2)习题：1、填空题（1）数据的逻辑结构包括：、；（2）存储结构包括：、。（3）数据结构中评价算法的两个重要指标是 （4）下面程序段中带下划线的语句的执行次数的数量级是：i=1；while(in)i=i*2;（5）计算机执行下面的语句时，语句 s 的执行次数为 _。for(i=l；i=i;j-)s;（6）下面程序段的时间复杂度为_。(n1)sum=1；for(i=0;sumn;i+)sum+=1;2、选择题（1）算法的计算量的大小称为计算的（）。A效率 B.复杂性 C.现实性 D.难度（2）算法的时间复杂度取决于（）A问题的规模 B.待处理数据的初态 C.A 和 B（3）计算机算法指的是（），它必须具备（）这三个特性。(1)A计算方法 B.排序方法 C.解决问题的步骤序列 D.调度方法(2)A可执行性、可移植性、可扩充性 B.可执行性、确定性、有穷性C.确定性、有穷性、稳定性 D.易读性、稳定性、安全性 （4）从逻辑上可以把数据结构分为（）两大类。A动态结构、静态结构 B顺序结构、链式结构 C线性结构、非线性结构 D初等结构、构造型结构（5）以下数据结构中，哪一个是线性结构（）？A广义表 B.二叉树 C.稀疏矩阵 D.串（6）在下面的程序段中，对 x 的赋值语句的频度为（）for(i=1;i=n;i+)for(j=1;j=1;i-)for(j=1;jAj+1 THEN Aj与 Aj+1对换；其中 n 为正整数，则最后一行的语句频度在最坏情况下是（）A.O（n）B.O(nlogn)C.O(n3)D.O(n2)（8）以下数据结构中，（）是非线性数据结构A树 B字符串 C队 D栈（9）连续存储设计时，存储单元的地址（）。A一定连续 B一定不连续 C不一定连续 D部分连续，部分不连续3、问答题（1）数据元素之间的关系在计算机中有几种表示方法？各有什么特点？（2）数据的逻辑结构有哪些基本类型？（3）数据的存储结构由哪四种基本的存储方法实现？第二章：线性表知识点：1、线性表的基本概念和两种存储方式：顺序存储、链式存储2、顺序表的概念、数据结构、存储，插入、删除运算及其时间复杂度；顺序表的特点：随机存储3、单链表的存储、插入、删除运算特点？是否可以随机存取？访问、增加或者删除结点时的时间复杂度？4、单链表中插入结点和删除结点的基本步骤？头指针与头结点之间的根本区别，头结点与首元结点的关系？在链表里面，引入头结点有什么作用？5、有头结点、无头结点的单链表为空的条件分别是什么？有头结点：L-next=NULL，无头结点：L=NULL习题：1 1、选择题、选择题（1）下述哪一条是顺序存储结构的优点？（）A存储密度大 B插入运算方便 C删除运算方便 D可方便地用于各种逻辑结构的存储表示（2）下面关于线性表的叙述中，错误的是哪一个？（）A线性表采用顺序存储，必须占用一片连续的存储单元。B线性表采用顺序存储，便于进行插入和删除操作。C线性表采用链接存储，不必占用一片连续的存储单元。D线性表采用链接存储，便于插入和删除操作。（3）线性表是具有 n 个（）的有限序列（n0）。A3表元素 B字符 C数据元素 D数据项 E信息项（4）链表不具有的特点是（）A插入、删除不需要移动元素 B可随机访问任一元素 C不必事先估计存储空间 D所需空间与线性长度成正比（5）下面的叙述不正确的是（）A线性表在链式存储时，查找第 i 个元素的时间同 i 的值成正比 B.线性表在链式存储时，查找第 i 个元素的时间同 i 的值无关C.线性表在顺序存储时，查找第 i 个元素的时间同 i 的值成正比D.线性表在顺序存储时，查找第 i 个元素的时间同 i 的值无关（6）若长度为 n 的线性表采用顺序存储结构，在其第 i 个位置插入一个新元素的算法的时间复杂度为（）(1=i=n+1)。A.O(0)B.O(1)C.O(n)D.O(n2)（7）对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为（）。AO(n)O(n)B.O(n)O(1)C.O(1)O(n)D.O(1)O(1)（8）线性表（a1,a2,an）以链接方式存储时，访问第 i 位置元素的时间复杂性为（）AO（i）BO（1）CO（n）DO（i-1）2 2、填空、填空（1）当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用_ _存储结构。（2）线性表 L=（a1,a2,an）用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是_ _。（3）在一个长度为 n 的顺序表中第 i 个元素（1=i=n）之前插入一个元素时，需向后移动_ 1_个元素。（4）在单链表中设置头结点的作用是_ _。（5）链接存储的特点是利用_来表示数据元素之间的逻辑关系。（6）顺序存储结构是通过_ _表示元素之间的关系的;链式存储结构是通过_表示元素之间的关系的。（7）对于双向链表,在两个结点之间插入一个新结点需修改的指针共 _个，单链表为_个。（8）在单链表 L 中，指针 p 所指结点有后继结点的条件是：_ （9）线性结构包括_、_、_和_。线性表的存储结构分成_ _和_ _。3、应用题（1）线性表有两种存储结构：一是顺序表，二是链表。试问：如果有 n 个线性表同时并存，并且在处理过程中各表的长度会动态变化，线性表的总数也会自动地改变。在此情况下，应选用哪种存储结构？为什么？若线性表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取线性表中的元素，那么应采用哪种存储结构？为什么？（2）说明在线性表的链式存储结构中，头指针与头结点之间的根本区别；头结点与首元结点的关系。（3）删除顺序表中所有的正数，要求移动次数小。搜索顺序表，对每一个正数，先不删除，而是累计当前正数个数 s，于是，对每个非正数，将它一次性前移 s 位。算法复杂性为 O（n）。void dels(sqlist*L)int s,i;s=0;/正数计数器 for(i=0;in;i+)if(L-datai0 s+;/累计当前正数 else if(s0)L-datai-s=l-datai;/向前移动 s 位 L-n=L-n-s;/调整表长还可以删除顺序表中所有的负数、字符等，主要是删除数据的条件不一样（4）单链表算法运用，如链表合并，将两个有序表合并为一个有序表lklist purge(lklist A,lklist B)pointer C,p,q,r;p=A-next;q=B-next;C=A;r=C;/取 A 头结点作 C 头结点 while(p!=NULL&q!=NULL)if(p-datadata)rnext=p;r=p;p=p-next;else rnext=q;r=q;q=q-next;if(p!=NULL)r-next=p;/A 表有剩余结点 else r-next=q;delete B;/释放 B 头结点 return C;第三章 栈、队列和串知识点：1、栈的定义、栈顶、栈底、运算特点（先进后出），顺序实现和链接实现及其特点，栈的应用2、队列的概念，队头、队尾、运算特点（后进后出），顺序实现、循环队列、链队列3、串的概念和串长的计算习题1、选择题（1）对于栈操作数据的原则是（）。A.先进先出 B.后进先出 C.后进后出 D.不分顺序（2）栈在（）中应用。A.递归调用 B.子程序调用 C.表达式求值 D.A，（3）一个递归算法必须包括（）。A.递归部分 B.终止条件和递归部分 C.迭代部分 D.终止条件和迭代部分（4）用链接方式存储的队列，在进行删除运算时（）。A.仅修改头指针 B.仅修改尾指针 C.头、尾指针都要修改 D.头、尾指针可能都要修改（5）用不带头结点的单链表存储队列时,其队头指针指向队头结点,其队尾指针指向队尾结点，则在进行删除操作时()。A仅修改队头指针 B.仅修改队尾指针 C.队头、队尾指针都要修改 D.队头,队尾指针都可能要修改（6）递归过程或函数调用时，处理参数及返回地址，要用一种称为（）的数据结构。A队列 B多维数组 C栈 D.线性表（7）栈和队列都是（）A顺序存储的线性结构 B.链式存储的非线性结构C.限制存取点的线性结构 D.限制存取点的非线性结构2、应用题（1）名词解释：栈、队列？（2）简述顺序存储队列的假溢出的避免方法及队列满和空的条件。第 4 章 多维数组和广义表知识点：1、多维数组的定义，对于一个多维数据，如何计算里面元素的个数？在存储多维数组时，如果已知首元素的存储地址，如何求数组里面任意元素的存储地址？（注意，行优先、列优先、元素的长度）2、广义表的概念、表长、深度、表头、表尾；广义表的取表头和取表尾操作；注意，取表头去的是原则取表尾得到的是表，会利用广义表的取表头和取表尾操作分离广义表的原子。习题：1、选择题（1）将一个 A1.100，1.100的三对角矩阵，按行优先存入一维数组B1298中，A 中元素 A6665（即该元素下标 i=66，j=65），在 B 数组中的位置 K 为（）。供选择的答案：A.198 B.195 C.197 （2）设 A 是 n*n 的对称矩阵，将 A 的对角线及对角线上方的元素以列为主的次序存放在一维数组 B1.n(n+1)/2中，对上述任一元素 aij(1i，jn，且ij)在 B 中的位置为()。A.i(i-l)/2+j B.j(j-l)/2+i C.j(j-l)/2+i-1 D.i(i-l)/2+j-1（3）设二维数组 A1.m，1.n（即 m 行 n 列）按行存储在数组 B1.m*n中，则二维数组元素 Ai，j在一维数组 B 中的下标为()。A.（i-1）*n+j B.（i-1）*n+j-1 C.i*（j-1）D.j*m+i-1（4）数组 A0.4,-1.-3,5.7中含有元素的个数（）。A.55 B.45 C.36 D.16 （5）广义表 A=(a,b,(c,d),(e,(f,g),则下面式子的值为（）。Head(Tail(Head(Tail(Tail(A)A.(g)B.(d)C.c D.d（6）广义表运算式 Tail(a,b),(c,d)的操作结果是（）。A.(c,d)B.c,d C.(c,d)D.d（7）广义表（a,b,c,d）的表头是（），表尾是（）。A.a B.（）C.（a,b,c,d）D.（b,c,d）2、填空题（1）设广义表 L=(),(),则 head(L)是(1)_；tail(L)是(2)_；L 的长度是(3)_；深度是 (4)_ _。（2）已知广义表 A=(9,7,(8,10,(99),12)，试用求表头和表尾的操作 Head()和Tail()将原子元素 99 从 A 中取出来。（3）广义表的深度是_ _。（4）广义表(a,(a,b),d,e,(i,j),k)的长度是 ，深度是 _。（5）已知广义表 LS=(a，(b，c，d)，e),运用 head 和 tail 函数取出 LS 中原子 b 的运算是_ _。（6）广义表 A=（a，b），（c，d，e），取出 A 中的原子 e 的操作是:_ _ _。第五章 树形结构知识点：1、树的概念、根、度、兄弟、路径、叶子、孩子、双亲、高度、深度、层数；根据一棵树，能够知道它的度、根节点、叶子结点、深度等；根据树中的某个结点，可以找出它的孩子结点；2、二叉树的概念、性质和几种特殊形态的二叉树及其特点：斜树、满二叉树、完全二叉树3、二叉树的存储（顺序存储，适合完全二叉树；链式存储）4、二叉树的遍历及其应用（先根、中根和后根遍历）5、二叉树的双序列生成（先根和中根或者中根和后根生成二叉树）6、树和森林的概念、树和森林与二叉树的相互转换方法、以及转换的二叉树的特点，树和森林的遍历7、哈弗曼编码的概念和哈弗曼树的构造题目1、选择题（1）已知一算术表达式的中缀形式为 A+B*C-D/E，后缀形式为 ABC*+DE/-，其前缀形式为()A-A+B*C/DE B.-A+B*CD/E C-+*ABC/DE D.-+A*BC/DE（2）设树 T 的度为 4，其中度为 1，2，3 和 4 的结点个数分别为 4，2，1，1 则 T 中的叶子数为（）A5 B6 C7 D8（3）在下述结论中，正确的是（）只有一个结点的二叉树的度为 0;二叉树的度为 2；二叉树的左右子树可任意交换;深度为 K 的完全二叉树的结点个数小于或等于深度相同的满二叉树。A B C D（4）设森林 F 对应的二叉树为 B，它有 m 个结点，B 的根为 p,p 的右子树结点个数为 n,森林 F 中第一棵树的结点个数是（）Am-n Bm-n-1 Cn+1 D条件不足，无法确定（5）若一棵二叉树具有 10 个度为 2 的结点，5 个度为 1 的结点，则度为 0 的结点个数是（）A9 B11 C15 D不确定（6）在一棵三元树中度为 3 的结点数为 2 个，度为 2 的结点数为 1 个，度为 1的结点数为 2 个，则度为 0 的结点数为（）个A4 B5 C6 D7 （7）设森林 F 中有三棵树，第一，第二，第三棵树的结点个数分别为 M1，M2和 M3。与森林 F 对应的二叉树根结点的右子树上的结点个数是（）。AM1 BM1+M2 CM3 DM2+M3（8）具有 10 个叶结点的二叉树中有（）个度为 2 的结点，A8 B9 C10 Dll（9）一棵完全二叉树上有 1001 个结点，其中叶子结点的个数是（）A 250 B 500 C254 D505 E以上答案都不对 （10）设给定权值总数有 n 个，其哈夫曼树的结点总数为()A不确定 B2n C2n+1 D2n-1（11）有关二叉树下列说法正确的是（）A二叉树的度为 2 B一棵二叉树的度可以小于 2 C二叉树中至少有一个结点的度为 2 D二叉树中任何一个结点的度都为 2（12）二叉树的第 I 层上最多含有结点数为（）A2I B 2I-1-1 C 2I-1 D2I -1（13）一个具有 1025 个结点的二叉树的高 h 为（）A11 B10 C11 至 1025 之间 D10 至 1024 之间（14）一棵二叉树高度为 h,所有结点的度或为 0，或为 2，则这棵二叉树最少有()结点A2h B2h-1 C2h+1 Dh+1 （15）在一棵高度为 k 的满二叉树中，结点总数为（）A2k-1 B2k C2k-1 Dlog2k+1（16）一棵树高为 K 的完全二叉树至少有（）个结点A2k 1 B.2k-1 1 C.2k-1 D.2k（17）一棵二叉树的前序遍历序列为 ABCDEFG，它的中序遍历序列可能是（）ACABDEFG BABCDEFG CDACEFBG DADCFEG （18）已知一棵二叉树的前序遍历结果为 ABCDEF,中序遍历结果为 CBAEDF,则后序遍历的结果为（）。ACBEFDA B FEDCBA C CBEDFA D不定 （19）某二叉树中序序列为 A,B,C,D,E,F,G，后序序列为 B,D,C,A,F,G,E 则前序序列是：（）AE,G,F,A,C,D,B BE,A,C,B,D,G,F CE,A,G,C,F,B,D D上面的都不对（20）二叉树的先序遍历和中序遍历如下：先序遍历：EFHIGJK；中序遍历:HFIEJKG。该二叉树根的右子树的根是：（）A、E B、F C、G D、H 2、填空题（1）二叉树由_(1)_，_(2)_，_(3)_三个基本单元组成。（2）具有 256 个结点的完全二叉树的深度为_。（3）深度为 k 的完全二叉树至少有_(1)_个结点，至多有_(2)_个结点。（4）深度为 H 的完全二叉树至少有_(1)_个结点；至多有_(2)_个结点；H 和结点总数 N 之间的关系是(3)。（5）假设根结点的层数为，具有个结点的二叉树的最大高度是_ _。（6）在一棵二叉树中，度为零的结点的个数为 N0,度为 2 的结点的个数为 N2,则有 N0=_ _（7）高度为 K 的完全二叉树至少有_个叶子结点。（8）高度为 8 的完全二叉树至少有_个叶子结点。（9）已知二叉树有 50 个叶子结点，则该二叉树的总结点数至少是_。（10）层完全二叉树至少有_个结点，拥有 100 个结点的完全二叉树的最大层数为_。3、应用题（1）树所有结点的度数之和与结点数有何关系？与边数有何关系？二叉树（或者树中），度为 0 的结点数与度不为 0 的结点树有何关系？（2）已知一棵二叉树的对称序和后序序列如下：中序：GLDHBEIACJFK 后序：LGHDIEBJKFCA(1)出这棵二叉树，并写出该二叉树的先序序列：(2)写出这棵二叉树的根节点、叶子节点、度为 1 的节点、度为 2 的节点(3)转换为对应的森林：（3）从概念上讲，树，森林和二叉树是三种不同的数据结构，将树，森林转化为二叉树的基本目的是什么，并指出树和二叉树的主要区别。（4）二叉树的遍历算法及其应用，如求叶子结点数、度为 1 的结点数、度为 2的结点数，交换二叉树的左右子树、判断两棵二叉树是否等价等。第 6 章 图知识点1、图的概念：有向图、无向图、完全图、连通图、强连通图、邻接点、顶点的度、出度、入度、路径2、图的存储：有向图和无向图的邻接矩阵存储和邻接表存储，及其特点3、图的深度优点遍历和广度优先遍历4、生成树、最小生成树，Prim 和 Kruskal 算法5、有向无环图的应用：拓扑排序和关键路径（课件例题）习题1、选择题（1）图中有关路径的定义是（）。A由顶点和相邻顶点序偶构成的边所形成的序列 B由不同顶点所形成的序列C由不同边所形成的序列 D上述定义都不是（2）设无向图的顶点个数为 n，则该图最多有（）条边。An-1 Bn(n-1)/2 C n(n+1)/2 D0 En2（3）一个 n 个顶点的连通无向图，其边的个数至少为（）。An-1 Bn Cn+1 Dnlogn；（4）要连通具有 n 个顶点的有向图，至少需要（）条边。An-l Bn Cn+l D2n（5）n 个结点的完全有向图含有边的数目（）。An*n n（n）Cn2 Dn*（nl）（6）一个有 n 个结点的图，最少有（）个连通分量，最多有（）个连通分量。A0 B1 Cn-1 Dn（7）在一个无向图中，所有顶点的度数之和等于所有边数（）倍，在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（）倍。A1/2 B2 C1 D4（8）下列哪一种图的邻接矩阵是对称矩阵？（）A有向图 B无向图 CAOV 网 DAOE网（9）下列说法不正确的是（）。A图的遍历是从给定的源点出发每一个顶点仅被访问一次 C图的深度遍历不适用于有向图B遍历的基本算法有两种：深度遍历和广度遍历 D图的深度遍历是一个递归过程（10）下面哪一方法可以判断出一个有向图是否有环（回路）：（）A深度优先遍历 B.拓扑排序 C.求最短路径 D.求关键路径（11）已知有向图 G=(V,E)，其中 V=V1,V2,V3,V4,V5,V6,V7，E=,G的拓扑序列是（）。AV1,V3,V4,V6,V2,V5,V7 BV1,V3,V2,V6,V4,V5,V7CV1,V3,V4,V5,V2,V6,V7 DV1,V2,V5,V3,V4,V6,V7（12）在有向图 G 的拓扑序列中，若顶点 Vi 在顶点 Vj 之前，则下列情形不可能出现的是（）。AG 中有弧 BG 中有一条从 Vi 到 Vj 的路径 CG 中没有弧 DG 中有一条从 Vj 到 Vi 的路径 （13）关键路径是事件结点网络中（）。A从源点到汇点的最长路径 B从源点到汇点的最短路径C最长回路 D最短回路（14）下面关于求关键路径的说法不正确的是（）。A求关键路径是以拓扑排序为基础的 B一个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同 C一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的差 D关键活动一定位于关键路径上（15）下列关于 AOE 网的叙述中，不正确的是（）。A关键活动不按期完成就会影响整个工程的完成时间B任何一个关键活动提前完成，那么整个工程将会提前完成C所有的关键活动提前完成，那么整个工程将会提前完成D某些关键活动提前完成，那么整个工程将会提前完成2 2、填空题、填空题（1）判断一个无向图是一棵树的条件是_ _。（2）一个连通图的_ _是一个极小连通子图。（3）具有 10 个顶点的无向图，边的总数最多为_ _。（4）若用 n 表示图中顶点数目，则有_ _条边的无向图成为完全图。（5）G 是一个非连通无向图，共有 28 条边，则该图至少有_ _个顶点。（6）在有 n 个顶点的有向图中，若要使任意两点间可以互相到达，则至少需要_ _条弧。（7）在有 n 个顶点的有向图中，每个顶点的度最大可达_ _。（8）在图 G 的邻接表表示中，每个顶点邻接表中所含的结点数，对于无向图来说等于该顶点的_ _；对于有向图来说等于该顶点的_ _。（9）在有向图的邻接矩阵表示中，计算第 I 个顶点入度的方法是_ _。（10）对于一个具有 n 个顶点 e 条边的无向图的邻接表的表示，则表头向量大小为_ _，邻接表的边结点个数为_ _。（11）构造连通网最小生成树的两个典型算法是_ _。（12）求图的最小生成树有两种算法，_ _算法适合于求稀疏图的最小生成树。(13)Prim（普里姆）算法适用于求_ _的网的最小生成树；kruskal（克鲁斯卡尔）算法适用于求_ _的网的最小生成树。三、三、应用题应用题（1）1）如果 G1 是一个具有 n 个顶点的连通无向图，那么 G1 最多有多少条边？G1 最少有多少条边？2）如果 G2 是一个具有 n 个顶点的强连通有向图，那么 G2 最多有多少条边？G2 最少有多少条边？3）如果 G3 是一个具有 n 个顶点的弱连通有向图，那么 G3 最多有多少条边？G3 最少有多少条边？（2）考虑右图：1)从顶点 A 出发，求它的深度优先生成树：ABGFDEC2)从顶点 E 出发，求它的广度优先生成树：EACFBDG3）根据普利姆(Prim)算法，求它的最小生成树并计算最小生成树的权值（3）已知一个无向图如下图所示，要求分别用 Prim 和 Kruskal 算法生成最小树并计算最小生成树的权值（假设以为起点，试画出构造过程）。第七章 排序知识点1、排序的基本概念。如稳定性、内排序、外排序，有序区增长法，有序度增长等。2、理解下面排序算法的原理、稳定性、时间复杂度、空间复杂度，最好情况、最坏情况：直接插入排序、希尔排序、冒泡排序、快速排序、直接选择排序、堆排序、归并排序3、对于上面给的排序算法，给出一组序列，可以写出每一趟的排序结果。习题1、选择题（1）某内排序方法的稳定性是指()。A该排序算法不允许有相同的关键字记录 B该排序算法允许有相同的关键字记录C平均时间为 0（n log n）的排序方法 D以上都不对（2）下面给出的四种排序法中()排序法是不稳定性排序法。A.插入 B.冒泡 C.二路归并 D.堆（3）下列排序算法中，其中（）是稳定的。A.堆排序，冒泡排序 B.快速排序，堆排序 C.直接选择排序，归并排序 D.归并排序，冒泡排序（4）若要求尽可能快地对序列进行稳定的排序，则应选（）。A快速排序 B归并排序 C冒泡排序（5）下面给出的四种排序方法中，排序过程中的比较次数与排序方法无关的是。()A选择排序法 B.插入排序法 C.快速排序法 D.堆积排序法（6）在下列排序算法中,哪一个算法的时间复杂度与初始排序无关（）。A 直接插入排序 B.气泡排序 C.快速排序 D.直接选择排序（7）下列排序算法中()不能保证每趟排序至少能将一个元素放到其最终的1265432010116618101459EABGCDF536141325位置上。A.快速排序 B.shell 排序 C.堆排序 D.冒泡排序 （8）下列排序算法中()排序在一趟结束后不一定能选出一个元素放在其最终位置上。A.选择 B.冒泡 C.归并 D.堆（9）在下面的排序方法中，辅助空间为 O（n）的是()。A希尔排序 B.堆排序 C.选择排序 D.归并排序 （10）下列排序算法中，占用辅助空间最多的是：()A.归并排序 B.快速排序 C.希尔排序 D.堆排序（11）在排序算法中，每次从未排序的记录中挑出最小（或最大）关键码字的记录，加入到已排序记录的末尾，该排序方法是（）。A.选择 B.冒泡 C.插入 D.堆（12）直接插入排序在最好情况下的时间复杂度为（）A O(logn)B O(n)C O(n*logn)D O(n2)（13）归并排序中，归并的趟数是()。AO（n）BO(logn)CO(nlogn)DO(n*n)2、应用题给出一组关键字：29，18，25，47，58，12，51，10，分别写出按下列各种排序方法进行排序时的变化过程：(1)归并排序 每归并一次书写一个次序。(2)快速排序 每划分一次书写一个次序。(3)堆排序 先建成一个堆，然后每从堆顶取下一个元素后，将堆调整一次。（4）直接选择排序（5）希尔排序（增量序列为 5,3,1）（6）冒泡排序（7）直接选择排序的变化过程(1)2路归并 第一趟:18,29,25,47,12,58,10,51；第二趟:18,25,29,47,10,12,51,58；第三趟:10,12,18,25,29,47,51,58(2)快速排序 第一趟:10,18,25,12,29,58,51,47；第二趟:10,18,25,12,29,47,51,88；第三趟:10,12,18,25,29,47,51,88(3)堆排序 建大堆58,47,51,29,18,12,25,10；第一趟:51,47,25,29,18,12,10,58；第二趟:47,29,25,10,18,12,51,58；第三趟:29,18,25,10,12,47,51,58；第四趟:25,18,12,10,29,47,51,58；第五趟:18,10,12,25,29,47,51,58；第六趟:12,10,18,25,29,47,51,58；第七趟:10,12,18,25,29,47,51,58第八章：查找知识点：1、查找的基本概念，什么是平均查找长度2顺序查找的基本原理、平均查找长度和查找算法3二分查找的基本原理、查找算法和平均查找长度（会根据二分判定树，确定利用二分查找时找某个关键字的查找次数）习题：1、对关键字序列1，2，3，4，6，7，8，9，10，11，写出利用折半查找查找里面各个关键字的比较次数；写出顺序查找时找出关键字 4 的比较次数和顺序查找时的平均查找长度。解：初始取 low=1，high=10，计算 mid=（1+10）/2=5，以该下标对应的数据作为树根；依次在不断的建立其左子树和右子树，知道所有的数据处理完成，如下图所示：12345678910123467891011323413423452813467910