数据结构复习题(1)

《数据结构复习题(1)》由会员分享，可在线阅读，更多相关《数据结构复习题(1)（20页珍藏版）》请在装配图网上搜索。

1、数据结构复习提纲第1章 绪论一、基本概念1、数据结构及其三方面的内容：数据元素的逻辑结构、存储结构和及其在数据上的基本操作。2、数据元素的逻辑结构的四种基本形式：集合、线性结构、树形结构、图形（网状）结构。3、数据元素的两种基本存储结构：顺序存储结构和链式存储结构；两种衍生结构：索引存储结构和散列存储结构。4、抽象数据类型。5、算法的基本概念及其5个特性。6、衡量算法的4个基本要求。7、算法时间复杂度的估算。二、练习题1. 数据结构是一门研究非数值计算的程序设计问题中,数据元素的 、数据信息在计算机中的 以及一组相关的运算等的课程。 A操作对象计算方法逻辑结构数据映象 A存储结构 关系 运算

2、算法2. 数据结构DS(Data Struct)可以被形式地定义为DS=（D，R），其中D是 的有限集合，R是D上的 有限集合。 A算法 数据元素 数据操作 数据对象 A操作 映象 存储 关系3. 在数据结构中，从逻辑上可以把数据结构分成 。A动态结构和静态结构 紧凑结构和非紧凑结构 线性结构和非线性结构 内部结构和外部结构4. 算法分析的目的是 ，算法分析的两个主要方面是 。 A. 找出数据结构的合理性 B. 研究算法中的输入和输出的关系C. 分析算法的效率以求改进 D. 分析算法的易懂性和文档性 A. 空间复杂性和时间复杂性 B. 正确性和简明性C. 可读性和文档性 D. 数据复杂性和程序

3、复杂性5. 计算机算法指的是 ，它必具备输入、输出和 等五个特性。 A. 计算方法 B. 排序方法C. 解决问题的有限运算序列 D. 调度方法 A. 可行性、可移植性和可扩充性 B. 可行性、确定性和有穷性 C. 确定性、有穷性和稳定性 D. 易读性、稳定性和安全性6. 分析下面算法（程序段），该算法的时间复杂度是_ _。for (i=0;in;i+) for (j=0;jn; j+) Aij=0;7. 分析下面算法（程序段），该算法的时间复杂度是_ _。for (i=0;in;i+) for (j=0; ji; j+)Aij=0;8. 分析下面算法（程序段），该算法的时间复杂度是_ _。s=

4、0;for (i=0;in;i+) for (j=0;jn;j+) for (k=0;kn;k+) s=s+Bijk;sum=s;9. 分析下面算法（程序段），该算法的时间复杂度是_ _。i=s=0;while (sn) i+; s+=i; /s=s+i 10. 分析下面算法（程序段），该算法的时间复杂度是_ _。i=1;while (inext= =NULLC. head-next= =head D. head!=NULL8. 带头结点的单链表head为空的判定条件是_。A. head= =NULL B. head-next= =NULLC. head-next= =head D. head

5、!=NULL9. 非空的循环单链表head的尾结点（由p所指向）满足_。A. p-next= =NULL B. p= =NULLC. p-next= =head D. p= =head 10. 在双向循环链表的p所指结点之后插入s所指结点的操作是_。A. p-right=s; s-left=p; p-right-left=s; s-right=p-right;B. p-right=s; p-right-left=s; s-left=p; s-right=p-right;C. s-left=p; s-right=p-right; p-right=s; p-right-left=s;D. s-le

6、ft=p; s-right=p-right; p-right-left=s; p-right=s;11. 在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入s结点，则执行_。A. s-next=p-next; p-next=s; B. p-next=s-next; s-next=p;B. q-next=s; s-next=p; C. p-next=s; s-next=q;12. 在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行_。A. s-next=p; p-next=s; B. s-next=p-next; p-next=s;C. s-next=

7、p-next; p=s; C. p-next=s; s-next=p;13. 在一个单链表中，若删除p所指结点的后续结点，则执行_。A. p-next= p-next-next； B. p= p-next; p-next= p-next-next；C. p-next= p-next; D. p= p-next-next；14. 从一个具有n个结点的单链表中查找其值等于x结点时，在查找成功的情况下，需平均比较_个结点。A. n B. n/2 C. (n-1)/2 D. (n+1)/215. 在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是_ _。A. O(1) B. O(n

8、) C. O (n2) D. O (nlog2n)16. 给定有n个元素的向量，建立一个有序单链表的时间复杂度是_ _。A. O(1)） B. O(n) C. O (n2) D. O (n*log2n)综合题类型：17 .设顺序表va中的数据元数递增有序。试写一算法，将x插入到顺序表的适当位置上，以保持该表的有序性。18 . 已知线性表中的元素以值递增有序排列，并以单链表作存储结构。试写一算法，删除表中所有大于x且小于y的元素（若表中存在这样的元素）同时释放被删除结点空间。19. 试写一算法，实现单链表的就地逆置(要求在原链表上进行)。20.有两个循环链表，链头指针分别为L1和L2，要求写出算

9、法将L2链表链到L1链表之后，且连接后仍保持循环链表形式。21. 设一个带头结点的单向链表的头指针为head，设计算法，将链表的记录，按照data域的值递增排序。22. 在带头结点的循环链表L中，结点的数据元素为整型，且按值递增有序存放。给定两个整数a和b，且ab，编写算法删除链表L中元素值大于a且小于b的所有结点。第3 栈和队列一、基本概念1、栈的定义、特点2、顺序栈和链栈的进栈和退栈操作；栈空和栈满的判定条件3、队列的定义和特点4、循环队列、链队列的出队和入队操作、判定队列为空、队列为满的条件二、练习题1. 一个栈的入栈序列a，b，c，d，e，则栈的不可能的输出序列是_。A. edcba

10、B. decba C. dceab D. abcde 2. 栈结构通常采用的两种存储结构是_。A. 顺序存储结构和链式存储结构B. 散列方式和索引方式C. 链表存储结构和数组D. 线性存储结构和非线性存储结构4. 判定一个顺序栈ST（最多元素为m0）为空的条件是_。A. top !=0 B. top= =0 C. top !=m0 D. top= =m0-15. 判定一个顺序栈ST（最多元素为m0）为栈满的条件是_。A. top！=0 B. top= =0 C. top！=m0 D. top= =m0-16. 栈的特点是_，队列的特点是_。 A. 先进先出 B. 先进后出7. 向一个栈顶指针为

11、HS的链栈中插入一个s所指结点时，则执行_ _。(不带空的头结点)A. HSnext=s;B. snext= HSnext; HSnext=s;C. snext= HS; HS=s;D. snext= HS; HS= HSnext;8. 从一个栈顶指针为HS的链栈中删除一个结点时，用x保存被删结点的值，则执行_ _。(不带空的头结点) A. x=HS; HS= HSnext; B. x=HSdata;C. HS= HSnext; x=HSdata; D. x=HSdata; HS= HSnext;9. 一个队列的数据入列序列是1，2，3，4，则队列的出队时输出序列是_ 。A. 4，3，2，1

12、B. 1，2，3，4 C. 1，4，3，2 D. 3，2，4，110. 判定一个循环队列QU（最多元素为m0）为空的条件是_。A. rear - front= =m0 B. rear-front-1= =m0C. front= = rear D. front= = rear+111. 判定一个循环队列QU（最多元素为m0, m0= =Maxsize-1）为满队列的条件是_。A. (rear- front)+ Maxsize)% Maxsize = =m0B. rear-front-1= =m0 C. front= =rear D. front= = rear+112. 循环队列用数组A0，m-

13、1存放其元素值，已知其头尾指针分别是front和rear，则当前队列中的元素个数是_。A. (rear-front+m)%m B. rear-front+1C. rear-front-1 D. rear-front13. 栈和队列的共同点是_。A. 都是先进后出 B. 都是先进先出C. 只允许在端点处插入和删除元素 D. 没有共同点综合题类型：14. 假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点（注意不设头指针），试编写相应的队列初始化、入队列和出队列的算法。15. 已知Q是一个非空队列，S是一个空栈。编写算法，仅用队列和栈的ADT函数和少量工作变量，将队列Q的所有元素逆

14、置。栈的ADT函数有：void makeEmpty(SqStack s);置空栈void push(SqStack s,ElemType e);元素e入栈ElemType pop(SqStack s);出栈，返回栈顶元素int isEmpty(SqStack s);判断栈空队列的ADT函数有：void enQueue(Queue q,ElemType e);元素e入队ElemType deQueue(Queue q);出队，返回队头元素int isEmpty(Queue q);判断队空16. 有一字符串序列为5*-x-y/x+2，利用栈的运算将其输出结果变为5x-*yx+/-2，试写出该操作的

15、入栈和出栈过程（采用push(a)表示a入栈，pop(a)表示a出栈）。第4章 串一、基本概念1、串的概念2、空串与空格串的区别3、子串与主串4、串相等5、串比较6、串的模式匹配7、串的模式匹配算法（BF、KMP、注意指针i，j的变化，模式串的next值）二、练习题1以下叙述中正确的是 。A.串是一种特殊的线性表B.串的长度必须大于零C.串中无素只能是字母D.空串就是空白串2空串与空格串是相同的，这种说法_。A. 正确 B. 不正确3串是一中特殊的线性表，其特殊性体现在_。A. 可以顺序存储 B. 数据元素是一个字符C. 可以链接存储 D. 数据元素可以是多个字符4设有两个串p和q，求q在p中

16、首次出现的位置的运算称作_。A. 连接 B. 模式匹配C. 求子串 D. 求串长5设串s1=ABCDEFG，s2=PQRST，函数con (x,y)返回x和y串的连接串，subs(s,i,j)返回串s的从序号i的字符开始的j个字符组成的子串，len(s)返回串s的长度，则con (subs (s1,2,len (s2), subs (s1,len (s2),2)的结果串是_。A. BCDEF B. BCDEFGC. BCPQRST D. BCDEFEF第5章 数组与广义表一、基本概念1、数组地址的计算（一维数组，二维数组）2、稀疏矩阵的压缩存储方法：三元组表和十字链表（要求会稀疏矩阵的三元组表

17、示）3、广义表的概念4、求广义表的深度和长度、求广义表的表头和表尾二、练习题1. 常对数组进行的两种基本操作是_。A. 建立与删除 B. 索引和修改 C. 对数据元素的存取和修改 D. 查找与索引2. 二维数组A中，每个元素A的长度为3个字节，行下标i从0到7，列下标j从0到9，从首地址SA开始连续存放在存储器内，该数组按列存放时，元素A47的起始地址为_。A. SA+141 B. SA+180 C. SA+222 D. SA+2253. 二维数组A1020采用列序为主方式存储，每个元素占一个存储单元并且A00的存储地址是200，则A612的地址是_。4. 二维数组A10.205.10采用行序

18、为主方式存储，每个元素占4个存储单元，并且A105的存储地址是1000，则A189的地址是_。5.数组A0.5,0.6的每个元素占5个字节，将其按列优先次序存储在起始地址为1000的内存单元中，则元素A55的地址是（ ）。A. 1175 B. 1180C. 1205 D. 12106求下列广义表操作的结果：(1) GetTailGetHead(a,b),(c,d);(2) GetTailGetHeadGetTail(a,b),(c,d)第6章 树和二叉树一、基本概念1、树的基本概念（度、深度）2、二叉树的定义和基本性质（5个）3、二叉树的基本算法（1）遍历算法（递归、非递归）（2）求叶子结点（

19、3）求二叉树深度4、表达式的前缀、后缀表达式表示5、线索二叉树的基本概念5、哈夫曼树的概念、哈夫曼树的构造方法、哈夫曼编码6、二叉树、树和森林的相互转换二、练习题1. 假定在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子结点数为 个。 A15 B16 C17 D472. 深度为5的二叉树至多有_个结点。A. 16 B. 32 C. 31 D. 103. 任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序_。A.不发生改变 B.发生改变 C.不能确定 D.以上都不对4. 某二叉树的先序遍历结点访问顺序是abdgcefh，中序遍历的结点访问顺序是dgbaechf，则其后序

20、遍历的结点访问顺序是_。A. bdgcefha B. gdbecfha C. bdgaechf D. gdbehfca5. 如图所示二叉树的中序遍历序列是_。A. abcdgef B. dfebagc C. dbaefcg D. defbagcgcefdbaagedbchf 6设a,b为一棵二叉树上的两个结点，在中序遍历时，a在b前的条件是 。Aa在b的右方Ba在b的左方Ca是b的祖先Da是b的子孙7实现任意二叉树的后序遍历的非递归算法而不使用栈结构，最佳方案是二叉树采用_存储结构。A. 二叉链表 B. 广义表存储结构 C. 三叉链表 D. 顺序存储结构8. 如图所示的4棵二叉树，_不是完全二

21、叉树。(A) (B) (C) (D)9. 如图所示的4棵二叉树，_是平衡二叉树。（A）（B）（C）（D）图8.8 4棵二叉树(A) (B) ( C ) (D) 10. 在线索化二叉树中，t所指结点没有左子树的充要条件是_。A. tleft=NULL B. tltag=1C. tltag=1且tleft=NULL D. 以上都不对11. 二叉树按某种顺序线索化后，任一结点均有指向其前驱和后续的线索，这种说法_。 A. 正确 B. 错误12. 二叉树为二叉排序树的充分必要条件是其任一结点的值均大于其左孩子的值、小于其右孩子的值。这种说法_。 A. 正确 B. 错误13. 具有五层结点的二叉平衡树至

22、少有_个结点。A. 10 B. 12 C. 15 D. 1714. 树最适合用来表示_。A. 有序数据元素 B. 无序数据元素 C. 元素之间具有分支层次关系的数据 D. 元素之间无联系的数据综合题类型：15. 假设一棵二叉树的先序序列为EBADCFHGIKJ和中序序列为ABCDEFGHIJK。请画出该树。16. 以数据集4，5，6，7，10，12，18为结点权值，画出构造Huffman树的每一步图示，计算其带权路径长度。17. 假设用于通讯的电文仅有八个字母(a,b,c,d,e,f,g,h)组成，字母在电文中出现的频率分别为0.07, 0.19, 0.02, 0.06, 0.32, 0.03

23、, 0.21, 0.10。试为这八个字母设计哈夫曼编码。18. 将下列森林转换为相应的二叉树。19. 画出与下图所示的森林相对应的二叉树，并指出森林中的叶子结点在二叉树中具有什么特点。20.已知一树的双亲表示法如下，其中各兄弟结点是依次出现的，画出该树根据二叉链表对应的二叉树。123456789101112131415dataABCDEFGHIJKLMNOparent011122334456678第7章 图一、基本概念1、图的概念和基本术语（1）有向图和无向图（2）有向完全图和无向完全图（3）度和边（弧）的关系（4）路径、简单路径、回路（5）连通图和连通分量（6）强连通图和强连通分量（7）生成

24、树和最小生成树2、图的两种存储结构（1）邻接矩阵与邻接表表示（给定图，能够写出其表示）（2）根据图的存储表示求边数、弧数、度（入度和出度）的方法3、图的搜索（1）图的深度搜索基本算法，能够写出深度搜索序列（2）图的广度搜索基本方法，能够写出广度搜索序列4、图的最小生成树算法（Prim和Kruskal），可根据给定图，写出其生成过程。（图或表的方式均可）5、拓扑排序（1）写出有向图的拓扑序列（2）拓扑排序是检测图中是否有环的方法，除此外，检测有向图是否具有环还可以利用深度优先搜索。6、最短路径（1）两个最短路径算法的基本步骤和时间复杂度（2）最短路径的求解步骤（参见教材p190和p192）7、关

25、键路径（1）关键路径的定义和意义（2）关键路径的求解步骤（四个关键量的求解）二、练习题1在一个图中，所有顶点的度数之和等于所有边数的_倍。A. 1/2 B. 1 C. 2 D. 4 2任何一个无向连通图的最小生成树 。A.只有一棵B.有一棵或多棵C.一定有多棵D.可能不存在3在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的_倍。A. 1/2 B. 1 C. 2 D. 44一个有n个顶点的无向图最多有_条边。A. n B. n(n-1) C. n(n-1)/2 D. 2n5具有4个顶点的无向完全图有_条边。A. 6 B. 12 C. 16 D. 206具有6个顶点的无向图至少应有_条边

26、才能确保是一个连通图。A. 5 B. 6 C. 7 D. 87在一个具有n个顶点的无向图中，要连通全部顶点至少需要_条边。A. n B. n+1 C. n-1 D. n/28对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是_。A. n B. (n-1)2 C. n-1 D. n29对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表头向量的大小为_；所有邻接表中的接点总数是_。 A. n B. n+1 C. n-1 D. n+e A. e/2 B. e C.2e D. n+e 10已知一个图如图7.1所示，若从顶点a出发按深度搜索法进行遍历，则可能得到的一种顶点序列为

27、_；按宽度搜索法进行遍历，则可能得到的一种顶点序列为_。 A. a,b,e,c,d,f B. e,c,f,e,b,d C. a,e,b,c,f,d D. a,e,d,f,c,b A. a,b,c,e,d,f B. a,b,c,e,f,d C. a,e,b,c,f,d D. a,c,f,d,e,bbaecdf图 7.1 一个无向图11已知一有向图的邻接表存储结构如图7.2所示。12345324524图7.2 一个有向图的邻接表存储结构 根据有向图的深度优先遍历算法，从顶点v1出发，所得到的顶点序列是_。A. v1,v2,v3,v5,v4 B. v1,v2,v3,v4,v5C. v1,v3,v4,

28、v5,v2 D. v1,v4,v3,v5,v2 根据有向图的宽度优先遍历算法，从顶点v1出发，所得到的顶点序列是_。A. v1,v2,v3,v4,v5 B. v1,v3,v2,v4,v5C. v1,v2,v3,v5,v4 D. v1,v4,v3,v5,v212采用邻接表存储的图的深度优先遍历算法类似于二叉树的_。A. 先序遍历 B. 中序遍历 C. 后序遍历 D. 按层遍历13采用邻接表存储的图的宽度优先遍历算法类似于二叉树的_。A. 先序遍历 B. 中序遍历 C. 后序遍历 D. 按层遍历14判定一个有向图是否存在回路除了可以利用拓扑排序方法外，还可以利用_。A. 求关键路径的方法 B. 求

29、最短路径的Dijkstra方法C. 宽度优先遍历算法 D. 深度优先遍历算法15关键路径是事件结点网络中 。A.从源点到汇点的最长路径 B.从源点到汇点的最短路径C.最长的回路 D.最短的回路16下面不正确的说法是 。 （1）在AOE网中，减小一个关键活动上的权值后，整个工期也就相应减小； （2）AOE网工程工期为关键活动上的权之和； （3）在关键路径上的活动都是关键活动，而关键活动也必在关键路径上。A.（1）B.（2）C.（3）D.（1）、（2）17用DFS遍历一个无环有向图，并在DFS算法退栈返回时打印出相应的顶点，则输出的顶点序列是 。A.逆拓朴有序的B.拓朴有序的C.无序的18在图7.

30、3所示的拓朴排列的结果序列为 。A.125634B.516234C.123456D.521634图7.3有向图19一个有n个顶点的无向连通图，它所包含的连通分量个数为 。A.0B.1C.nD.n+120对于一个有向图，若一个顶点的入度为k1,、出度为k2，则对应邻接表中该顶点单链表中的结点数为 。A.k1B.k2C.k1-k2D.k1+k221对于一个有向图，若一个顶点的入度为k1,、出度为k2，则对应逆邻接表中该顶点单链表中的结点数为 。A.k1B.k2C.k1-k2D.k1+k2综合题类型：22. 已知如图7.5所示的有向图，请给出该图的:（1）每个顶点的入/出度；（2）邻接距阵；1562

31、43（3）邻接表；（4）逆邻接表；（5）强连通分量。图7。5一个有向图23请用克鲁斯卡尔和普里姆两种算法分别为下图构造从顶点a出发的最小生成树：（给出构造过程，表或图均可） badcef16111515151613141221 24试列出图中全部的拓扑排序序列。12345625求顶点a到其余各顶点之间的最短路径。（要求给出求解过程）543223356abdfce26已知AOE网有9个结点：V1，V2，V3，V4，V5，V6，V7，V8，V9，其邻接矩阵如下：(1)请画出该AOE图。(2)计算完成整个计划需要的时间。(3)求出该AOE网的关键路径。（要求计算出ve,vl,ee,el）645112

32、9742427. 已知图G的邻接表如图7.4所示，其从顶点v1出发的深度有限搜索序列为_，其从顶点v1出发的宽度优先搜索序列为_。v1v3v2v4v5v6v2v5v4v3v5v6v4v6v3 图7.4 图G的邻接表第9章 查找一、基本概念1、静态查找表、动态查找表的概念2、静态查找表（1）顺序查找、折半查找、分块查找的基本方法（2）给定查找表，查找某元素的比较次数计算（3）平均查找长度的计算3、动态查找表（1）二叉排序树的构造及平均查找长度计算（2）平衡二叉树的旋转平衡方法4、哈希表（1）哈希表、哈希函数、散列、冲突、同义词、装填因子的概念（2）哈希函数的常用构造方法（3）冲突的解决方法（重点

33、掌握开放地址法和链地址法）（4）哈希表的构造和平均查找长度计算二、练习题1.顺序查找法适合于存储结构为_的线性表。A. 散列存储 B. 顺序存储或链接存储C. 压缩存储 D. 索引存储2.对线性表进行二分查找时，要求线性表必须_。A. 以顺序方式存储 B. 以链接方式存储C. 以顺序方式存储，且结点按关键字有序排序D. 以链接方式存储，且结点按关键字有序排序3.采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为_.A. n B. n/2 C. (n+1)/2 D. (n-1)/24.采用二分查找方法查找长度为n的线性表时，每个元素的平均查找长度为_。AO（n2） B. O(nlo

34、g2n) C. O(n) D. O(log2n)5.有一个有序表为1，3，9，12，32，41，45，62，75，77，82，95，100，当二分查找值82为的结点时，_次比较后查找成功。A. 1 B. 2 C. 4 D. 86.设哈希表长m=14，哈希函数H(key)=key%11。表中已有4个结点：addr (15)=4; addr (38)=5; addr (61)=6; addr (84)=7如用二次探测再散列处理冲突，关键字为49的结点的地址是_。A. 8 B. 3 C. 5 D. 97.有一个长度为12的有序表，按二分查找法对该表进行查找，在表内各元素等概率情况下查找成功所需的平均

35、比较次数为_。A. 35/12 B. 37/12 C. 39/12 D. 43/128解决散列法中出现的冲突问题常采用的方法是 。A.数字分析法、除余法、平方取中法B.数字分析法、除余法、线性探测法C.数字分析法、线性探测法、多重散列法D.线性探测法、多重散列法、链地址法9采用线性探测法解决冲突问题，所产生的一系列后继散列地址 。A.必须大于等于原散列地址B.必须小于等于原散列地址C.可以大于或小于但不能等于原散列地址D.地址大小没有具体限制11对于查找表的查找过程中，若被查找的数据元素不存在，则把该数据元素插入到集合中。这种方式主要适合于 。A.静态查找表B.动态查找表C.静态查找表与动态查

36、找表D两种表都不适合12.散列表的平均查找长度 。A.与处理冲突方法有关而与表的长度无关B.与处理冲突方法无关而与表的长度有关C.与处理冲突方法有关而与表的长度有关D.与处理冲突方法无关而与表的长度无关13平衡二叉排序树上任一结点的平衡因子只可能是 、 或 。14在散列函数H(key)=key%p中，p应取_。15在散列存储中，装填因子的值越大，则_；的值越小，则_。综合题类型：16. 选取哈稀函数H（k）=（3k）MOD 11。用开放定址法处理冲突，di=i（7k）MOD 10+1）（I=1，2，3，）.试在0-10的散列地址空间中对关键字序列（22,41,53,46,30,13,01,67

37、）造哈希表，并求等概率情况下查找成功时的平均查找长度。17. 已知一组关键字49，38，65，97，76，13，27，44，82，35，50，画出由此生成的二叉排序树，注意边插入边平衡，并计算等概率下查找成功的平均查找长度。（要求按插入和调整步骤画出生成过程）第10章 排序一、基本概念1、 各种排序方法的时间复杂度、空间复杂度、稳定性比较。2、 各种排序方法的基本步骤（能够写出每趟排序的结果、根据排序结果判断所选用的排序方法）二、练习题1. 在所有排序方法中，关键字比较的次数与记录的初始排列次序无关的是_。A. 希尔排序 B. 起泡排序 C. 插入排序 D. 选择排序2. 设有1000个无序的

38、元素，希望用最快的速度挑选出其中前10个最大的元素，最好选用_排序法。A. 起泡排序 B. 快速排序 C. 堆排序 D. 基数排序3. 在待排序的元素序列基本有序的前提下，效率最高的排序方法是_。A. 插入排序 B. 选择排序 C. 快速排序 D. 归并排序4. 一组记录的排序码为（46，79，56，38，40，84），则利用堆排序的方法建立的初始堆为_。A. 79，46，56，38，40，80 B. 38，46, 56，79， 40，84，C. 84，79，56，46，40，38 D. 84，56，79，40，46，385. 一组记录的关键码为（46，79，56，38，40，84），则利用快

39、速排序的方法，以第一个记录为基准得到的一次划分结果为_。A. 38，40，46，56，79，84 B. 40，38，46，79，56，84C. 40，38，46，56，79，84 D. 40，38，46，84，56，796. 一组记录的排序码为（25，48，16，35，79，82，23，40，36，72），其中含有5个长度为2的有序表，按归并排序的方法对该序列进行一趟归并后的结果为_。A. 16，25，35，48，23，40，79，82，36，72 B. 16，25，35，48，79，82，23，36，40，72C. 16，25，48，35，79，82，23，36，40，72D. 16，25，

40、35，48，79，23，36，40，72，827. 排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为_。A. 希尔排序 B. 起泡排序 C. 插入排序 D. 选择排序8. 排序方法中，从未排序序列中挑选元素，并将其依次放入已排序序列（初始时为空）的一端的方法，称为_。A. 希尔排序 B. 归并排序 C. 插入排序 D. 选择排序9. 用某种排序方法对线性表（ 25，84，21，47，15，27，68，35，20）进行排序时，元素序列的变化情况如下： 25，84，21，47，15，27，68，35，20 20，15，21

41、，25，47，27，68，35，84 15，20，21，25，35，27，47，68，84 15，20，21，25，27，35，47，68，84则所采用的排序方法是_。A. 选择排序 B. 希尔排序 C. 归并排序 D. 快速排序10. 下述几种排序方法中，平均查找长度最小的是_。A. 插入排序 B. 选择排序 C. 快速排序 D. 归并排序11. 下述几种排序方法中，要求内存量最大的是_。A. 插入排序 B. 选择排序 C. 快速排序 D. 归并排序12. 快速排序方法在_情况下最不利于发挥其长处。A. 要排序的数据量太大 B. 要排序的数据中含有多个相同值 C. 要排序的数据已基本有序 D. 要排序的数据个数为奇数综合题类型：13. 以关键码序列（503,087,512,061,908,170,897,275,653,426），为例，手工执行以下排序算法，写出每一趟排序结果：（1） 直接插入排序；（2） 希尔排序（增量d1=5）；（3） 快速排序；（4） 堆排序；（5） 归并排序；