3。在数据结构中，从逻辑上可以把数据结构分成（ ） (A)动态结构和静态结构 （B）紧凑结构和非紧凑结构 （C）线性结构和非线性结构（D）内部结构和外部结构 5.算法分析的目的是（）。
（A) 找出数据结构的合理性 （B）研究算法中的输入和输出的关系 （C）分析算法的效率以求改进（D）分析算法的易懂性和文档性
二、判断题
1.数据的机内表示称为数据的存储结构。（ ） 2。算法就是程序。（ ）
5.算法的时间复杂度取决于问题的规模和待处理数据的初态.( ） 三、填空题
1.数据逻辑结构包括________、________、_________ 和_________四种类型，其中树形结构和图形结构合称为_____.
2.在线性结构中，第一个结点____前驱结点,其余每个结点有且只有______个前驱结点；最后一个结点______后续结点，其余每个结点有且只有_______个后续结点。
3.在树形结构中,树根结点没有_______结点,其余每个结点有且只有_______个前驱结点；叶子结点没有________结点，其余每个结点的后续结点可以_________.
4.在图形结构中,每个结点的前驱结点数和后续结点数可以_________。 5.线性结构中元素之间存在________关系，树形结构中元素之间存在______关系，图形结构中元素之间存在_______关系。 8.链式存储结构与顺序存储结构相比较,主要优点是________________________________。
9。设有一批数据元素，为了最快的存储某元素，数据结构宜用_________结构，为了方便插入一个元素,数据结构宜用____________结构。
四、算法分析题，求下列算法段的语句频度及时间复杂度 for （i=1；i<=n;i++） for (j=1;j〈=i；j++) for （ k=1;k<=j；k++) x=i+j—k；
第二章 线性表 一、选择题
1。一个线性表第一个元素的存储地址是100,每个元素的长度为2，则第5个元素的地址是（ ）
（A)110 (B）108（C）100 （D）120
2。 向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动( ）个元素。
（A)64（B）63 （C)63.5 （D）7
3。线性表采用链式存储结构时,其地址（ ). (A) 必须是连续的 （B) 部分地址必须是连续的 (C） 一定是不连续的 (D） 连续与否均可以
4. 在一个单链表中,若p所指结点不是最后结点,在p之后插入s所指结点，则执行（ )
（A)s.next=p；p.next=s; （B) s。next=p.next；p。next=s； （C）s.next=p.next;p=s； （D）p。next=s;s.next=p;
5。在一个单链表中,若删除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； 6.下列有关线性表的叙述中，正确的是（ ) (A)线性表中的元素之间隔是线性关系 （B）线性表中至少有一个元素
（C）线性表中任何一个元素有且仅有一个直接前趋 (D）线性表中任何一个元素有且仅有一个直接后继 7.线性表是具有n个（ )的有限序列（n≠0）
（A）表元素 （B)字符 （C）数据元素 （D）数据项 二、判断题
1。线性表的链接存储,表中元素的逻辑顺序与物理顺序一定相同.（ ) 3.线性结构的特点是只有一个结点没有前驱,只有一个结点没有后继，其余的结点只有一个前驱和后继。（ )
三、填空题
1。已知P为单链表中的非首尾结点，在P结点后插入S结点的语句为：_______________________ 。
2。顺序表中逻辑上相邻的元素物理位置( )相邻， 单链表中逻辑上相邻的元素物理位置_________相邻. 四、算法设计题
对于结点类型为LNode的单链表，编写出下列每个算法。 (1)删除单链表中的第i个结点。
（2）在有序单链表中插入一个元素x的结点。
(3）从单链表中查找出所有元素的最大值，该值由函数返回，若单链表为空,则显示出错信息并停止运行。
（4)统计出单链表中结点的值等于给定值x的结点数。
第三章 栈和队列 一、选择题
1。 一个栈的入栈序列是a,b，c，d，e，则栈的不可能的输出序列是（ )。 (A） edcba（B）decba(C）dceab （D）abcde 2.栈结构通常采用的两种存储结构是( ）。
（A） 线性存储结构和链表存储结构（B)散列方式和索引方式 （C)链表存储结构和数组 （D）线性存储结构和非线性存储结构 3.判定一个栈ST（最多元素为m0)为空的条件是（ ）。 （A） ST.top！=0 （B）ST.top==0 （C）ST。top!=m0 (D）ST。top=m0
4。判定一个栈ST(最多元素为m0）为栈满的条件是（ ）。 （A）ST.top！=0 （B）ST—>top==0 （C）ST。top！=m0—1(D）ST。top==m0-1
5.一个队列的入列序列是1，2,3,4，则队列的输出序列是（ ）. （A)4,3,2,1（B）1,2,3，4（C）1,4，3,2（D）3，2，4，1
6.循环队列用数组A［0,m—1]存放其元素值,已知其头尾指针分别是front和rear则当前队列中的元素个数是（ ）
（A）(rear—front+m)%m （B) rear-front+1 （C）rear—front-1（D）rear-front
7。栈和队列的共同点是( )
(A） 都是先进后出 （B）都是先进先出
（C)只允许在端点处插入和删除元素(D）没有共同点
9。4个元素a1，a2，a3和a4依次通过一个栈，在a4进栈前，栈的状态,则不可能的出栈序是( )
(A）a4,a3，a2，a1 （B）a3,a2，a4，a1 (C)a3，a1，a4，a2 (D）a3，a4，a2，a1
10。以数组Q［0。.m－1]存放循环队列中的元素,变量rear和qulen分别指示循环队列中队尾元素的实际位置和当前队列中元素的个数，队列第一个元素的实际位置是（ ）
(A)rear－qulen (B）rear－qulen＋m
（C)m－qulen (D）1＋（rear＋m－qulen）％ m 二、填空题
1。栈的特点是_______________________，队列的特点是__________________________。
2。线性表、栈和队列都是_____________________结构，可以在线性表的______________位置插入和删除元素，对于栈只能在________插入和删除元素,对于队列只能在_______插入元素和_________删除元素。
3。一个栈的输入序列是12345,则栈有输出序列12345是____________。(正确/错误）
4.设栈S和队列Q的初始状态皆为空，元素a1，a2，a3，a4,a5和a6依次通过一个栈，一个元素出栈后即进入队列Q，若6个元素出队列的顺序是a3，a5，a4,a6,a2，a1则栈S至少应该容纳_____个元素。 三、算法设计题 1.链栈的出栈入栈算法。
2。顺序循环队列的出队入队算法.
第四章 串和数组 一、选择题
1。下列关于串的叙述中,正确的是（ )
（A）一个串的字符个数即该串的长度 (B）一个串的长度至少是1 (C）空串是由一个空格字符组成的串
（D)两个串S1和S2若长度相同，则这两个串相等
2.二维数组M的元素是4个字符（每个字符占一个存储单元)组成的串,行下标i的范围从0到4，列下标j的范围从0到5，M按行存储时元素M［3][5］的起始地址与M按列存储时元素( ） 的起始地址相同.
(A）M[2][4］（B）M[3］［4］（C）M[3]［5]（D）M[4][4］
3.数组A［8］［10］中,每个元素A的长度为3个字节,从首地址SA开始连续存放在存储器内,存放该数组至少需要的单元数是（ )。 (A）80（B)100(C）240(D）270
4.数组A［8]［10］中,每个元素A的长度为3个字节,从首地址SA开始连续存放在存储器内，该数组按行存放时，元素A[7］［4]的起始地址为（ ）。 （A）SA+141（B）SA+144（C）SA+222（D）SA+225
5。数组A［8］［10］中,每个元素A的长度为3个字节，从首地址SA开始连续存放在存储器内,该数组按列存放时,元素A[4］［7]的起始地址为（ ）。 （A)SA+141(B)SA+180（C)SA+222(D）SA+225
6。稀疏矩阵一般的压缩存储方法有两种,即（ ）。 （A) 二维数组和三维数组（B）三元组和散列 （C）三元组和十字链表 （D）散列和十字链表
7.若采用三元组压缩技术存储稀疏矩阵,只要把每个元素的行下标和列下标互换，就完成了对该矩阵的转置运算,这种观点( )。 (A)正确（B)错误
8。设矩阵A是一个对称矩阵，为了节省存储,将其下三角部分按行序存放在一维数组B[1,n（n—1）/2］中,对下三角部分中任一元素ai，j(i〈=j）,在一组数组B的下标位置k的值是（ ）。
(A)i（i-1)/2+j—1（B）i(i-1）/2+j（C）i(i+1）/2+j—1 (D)i(i+1)/2+j 4。串是一种特殊的线性表,其特殊性表现在（ ） （A）可以顺序存储 （B)数据元素是一个字符 (C）可以链式存储 (D）数据元素可以是多个字符
5．设串S1=‘ABCDEFG’,s2=‘PQRST’，函数CONCAT（X，Y）返回X和Y串的连接串，SUBSTR（S，I，J)返回串S从序号I开始的J个字符组成的字串，LENGTH（S）返回串S的长度,则CONCAT（SUBSTR(S1，2，LENGTH（S2)），SUBSTR（S1,LENGTH（S2），2））的结果串是( ) (A）BCDEF （B) BCDEFG (C）BCPQRST （D)BCDEFEF
二、填空题
1.己知二维数组A[m］[n]采用行序为主方式存储，每个元素占k个存储单元,并且第一个元素的存储地址是LOC(A［0][0］）,则A［0］［0］的地址是_____________________.
2.二维数组A［10］[20]采用列序为主方式存储,每个元素占一个存储单元,并且A［0］［0］的存储地址是200，则A［6]［12］的地址是________________。
3。有一个10阶对称矩阵A，采用压缩存储方式(以行序为主,且A[0][0]=1）,则A［8][5］的地址是__________________。
4。设n行n列的下三角矩阵A已压缩到一维数组S[1。。n＊(n+1）/2］中，若按行序为主存储，则A［i］[j]对应的S中的存储位置是________________。 5。若A是按列序为主序进行存储的4×6的二维数组，其每个元素占用3个存储单元，并且A[0］［0］的存储地址为1000，元素A［1]［3］的存储地址为___________,该数组共占用_______________个存储单元。
三、算法设计
1.串的模式匹配算法。
第五章 树与二叉树
3。二叉树的前序遍历序列中，任意一个结点均处在其子女结点的前面,这种说法（ )
（A）正确 (B）错误 （C）不同情况下答案不确定
4.由于二叉树中每个结点的度最大为2，所以二叉树是一种特殊的树，这种说法（ ）
2.正确 （B）错误 （C）不同情况下答案不确定
5。设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为（ ).
（A）2h （B）2h—1(C）2- 9 -3+1（D)h+1
6.已知某二叉树的后序遍历序列是dabec.中序遍历序列是debac，它的前序遍历序列是（ )。
(A)acbed (B）decab（C)deabc （D）cedba
7.如果T2是由有序树T转换而来的二叉树,那么T中结点的前序就是T2中结点的（ )
（A）前序（B）中序（C）后序(D)层次序
8。某二叉树的前序遍历结点访问顺序是abdgcefh,中序遍历的结点访问顺序是dgbaechf,则其后序遍历的结点访问顺序是( ）。
（A）bdgcefha （B）gdbecfha （C）bdgaechf （D)gdbehfca
9.二叉树为二叉排序树的充分必要条件是其任一结点的值均大于其左孩子的值、小于其右孩子的值。这种说法（ )
(A）正确(B）错误(C)不同情况下答案不确定
10。按照二叉树的定义,具有3个结点的二叉树有（ )种。 (A）3（B)4（C）5（D）6
11.在一非空二叉树的中序遍历序列中,根结点的右边（ ） （A）只有右子树上的所有结点（B）只有右子树上的部分结点 (C)只有左子树上的部分结点(D）只有左子树上的所有结点 12。树最适合用来表示( )。
（A）有序数据元素（B）无序数据元素
（C）元素之间具有分支层次关系的数据(D）元素之间无联系的数据
13。任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序（ ) （A)不发生改变（B)发生改变（C）不能确定D。以上都不对 15。对一个满二叉树,m个树叶，n个结点，深度为h,则（ ）
(A）n=h+m （B）h+m=2n（C)m=h—1（D）n=2h-1 16.如果某二叉树的前序为stuwv，中序为uwtvs,那么该二叉树的后序为（ ） （A）uwvts （B）vwuts（C）wuvts (D)wutsv 17.具有五层结点的二叉平衡树至少有( )个结点. （A）10（B)12（C）15（D）17
3.已知一棵树边的集合为｛〈 I ， M >，< I ， N 〉,〈 E ， I 〉，〈 B , E >，〈 B ， D>，〈 A ， B>，< G ， J >，< G ， K〉,< C , G>，〈 C ， F>，〈 H ， L〉，< C ， H>，〈 A ， C >｝,画出这棵树,并回答下列问题：
哪个结点是根结点?
① 哪些结点是叶子结点？
② 哪个结点是结点 G 的双亲结点? ③ 哪些结点是结点 G 的祖先结点？ ④ 哪些结点是结点 G 的孩子结点? ⑤ 哪些结点是结点 E 的子孙结点？
⑥ 哪些结点是结点 E 的兄弟结点？哪些是结点 F 的兄弟结点？ ⑦ 结点 B 和 N 的层次分别是多少？ ⑧ 树的深度是多少？
1) 以结点 C 为根的子树的深度是多少？
4.已知一棵二叉树的先序、中序和后序序列如下,其中各有一部分未给出其值，请构造出该二叉树。
先序：A_CDEF_H_J 中序：C_EDA_GFI_ 后序：C_ _BHGJI_ _ 5.已知一棵树的度为4，其中度为4的结点的数目为3，度为3的结点的数目为4，度为2的结点的数目为54.按照下列给定二叉树的先序遍历序列、中序遍历和后序遍历序列，分别构造出二叉树。
① 先序遍历序列: EBADCFHGIKJ 中序遍历系列： ABCDEFGHIJK ② 中序遍历序列： ACBGEDF 后序遍历序列： ABCDEFG
③ 度为1的结点的数目为2，请求出该树中的叶子结点的数目.
二、判断题
1.二叉树中任何一个结点的度都是2。（ )
2.由二叉树结点的先根序列和后根序列可以唯一地确定一棵二叉树.（ ） 3。一棵哈夫曼树中不存在度为1的结点。( ）
4.平衡二叉排序树上任何一个结点的左、右子树的高度之差的绝对值不大于2（ ） 6.
三、填空题
3.若结点A有三个兄弟（包括A本身），并且B是A的双亲结点，B的度是_______________
4.若一棵具有n个结点的二叉树采用标准链接存储结构，那么该二叉树所有结点共有_______个空指针域.
5。已知二叉树的前序序列为ABDEGCFHIJ,中序序列为DBGEAHFIJC,写出后序序列_______________。
6.已知二叉树的后序序列为FGDBHECA，中序序列为BFDGAEHC ,并写出前序序列_________________。
7.找出满足下列条件的二叉树
1）先序和中序遍历,得到的结点访问顺序一样。_________________________ 2）后序和中序遍历，得到的结点访问顺序一样。_________________________ 3)先序和后序遍历，得到的结点访问顺序一样。__________________________ 9。一棵二叉树有67个结点，这些结点的度要么是0，要么是2.这棵二叉树中度为2的结点有______________________个。
10。含有100个结点的树有_______________________________________条边。
四、问答题
4。有七个带权结点，其权值分别为3,7，8，2,6,10,14，试以它们为叶结点构造一棵哈夫曼树（请按照每个结点的左子树根结点的权小于等于右子树根结点的权的次序构造〉，并计算出带权路径长度WPL及该树的结点总数. 5。有一电文共使用五种字符a，b,c，d,e，其出现频率依次为4，7，5,2，9。 （1)试画出对应的编码哈夫曼树（要求左子树根结点的权小于等于右子树根结点的权）。
(2)求出每个字符的晗夫曼编码。 (3）求出传送电文的总长度。
（4）并译出编码系列1100011100010101的相应电文。
第七章 图 一、判断题
1。一个无向图的邻接矩阵中各非零元素之和与图中边的条数相等。（ ）
2.一个有向图的邻接矩阵中各非零元素之和与图中边的条数相等.( ）
3.一个对称矩阵一定对应着一个无向图。（ ）
4。一个有向图的邻接矩阵一定是一个非对称矩阵。（ ） 二、选择题
1.在一个无向图中，所有顶点的度数之和等于所有边数的（ ）倍。 （A）1/2（B）1（C）2（D）4
2。在一个有向图中,所有顶点的入度之和等于所有顶点的出度之和的（ ）倍. （A）1/2（B)1(C）2（D）4
3。一个有n个顶点的无向图最多有（ ）条边. （A）n （B）n（n—1）（C）n(n—1）/2（D）2n 4.具有4个顶点的无向完全图有（ )条边。 （A）6（B）12（C）16（D)20
5。具有6个顶点的无向图至少应有（ ）条边才能确保是一个连通图. （A）5(B）6（C）7（D)8
6.在一个具有n个顶点的无向图中，要连通全部顶点至少需要（ ）条边。 （A）n (B）n+1（C）n—1（D）n/2
7。对于一个具有n个顶点的无向图，若采用邻接矩阵表示,则该矩阵的大小( ）
（A）n （B）（n—1） 2(C）n-1 （D）n2
8。对于一个具有n个顶点和e条边的无向图,若采用邻接表表示，则表头向量的大小为( )，所有邻接表中的结点总数是（ )。 ①（A）n (B）n+1（C）n—1(D）n+e ②(A）e/2(B）e（C）2e （D)n+e
9。采用邻接表存储的图的深度优先遍历算法类似于二叉树的( )。 (A)先序遍历(B）中序遍历(C）后序遍历(D)按层遍历
10。采用邻接表存储的图的宽度优先遍历算法类似于二叉树的（ ）. （A)先序遍历（B）中序遍历(C）后序遍历（D）按层遍历
11。判定一个有向图是否存在回路除了可以利用拓扑排序方法外,还可以利用（ ）.
（A）求关键路径的方法（B）求最短路径的Dijkstm方法 （C）宽度优先遍历算法（D)深度优先遍历算法
12.用Prim算法求下列连通的带权图的最小代价生成树,在算法执行的某刻，已选取的顶点集合U＝{1，2,5｝,边的集合TE＝｛（1，2），（2，5)}，要选取下一条权值最小的边,应当从（ )组中选取。 （A）｛（1，4），(3，4），（3，5），（2，5)｝ (B)｛（5,4)，（5,3），(5,6)｝ （C){（1，2）,（2,3）,（3，5)｝
（D)｛（3，4），（3，5），（4，5）,（1，4）}
三、填空题
1。n个顶点的连通图至少_____________条边。
2。在一个无环有向图G中，若存在一条从顶点i到顶点j的弧，则在顶点的拓扑序列中，顶点i与顶点j的先后次序是_________________。 3.在一个无向图的邻接表中，若表结点的个数是m,则图中边的条数是________________条。
4。 如果从一个顶点出发又回到该顶点，则此路径叫做_______。
5.如果从一无向图的任意顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是____________。
6。若采用邻接表的存储结构，则图的广度优先搜索类似于二叉树的________遍历.
7。 一个连通图的生成树是该图的________连通子图。若这个连通图有n个顶点, 则它的生成树有________条边。
第八章 查找 一、判断题
1.用二分查找法对一个顺序表进行查找,这个顺序表可以是按各键值排好序的,也可以是没有按键值排好序的。（ ）
3.哈希表的定义函数H（key）=key%p（p<=m)这种方法是直接定址法.（ ）
二、填空题
1.顺序查找法的平均查找长度为__________,二分查找法的平均查找长度为________，分块查找法（以顺序查找确定块)的平均查找长度为__________，分块查找法(以二分查找确定块)的平均查找长度为__________。 2.在各种查找方法中，平均查找长度与结点个数n无关的查法方法是_________
3。二分查找的存储结构仅限于_________,且是__________.
4.在分块查找方法中，首先查找__________,然后再查找相应的___________。 5。长度为255的表,采用分块查找法,每块的最佳长度是____________。 7.假设在有序线性表A[1.。20]上进行二分查找，则比较一次查找成功的结点数为_________，则比较二次查找成功的结点数为__________,则比较三次查找成功的结点数为_________，则比较四次查找成功的结点数为________，则比较五次查找成功的结点数为_________，平均查找长度为_________。 9.己知一个有序表为（12，18,20，25，29，32，40,62,83,90,95，98）,当二分查找值为29和90的元素时，分别需要________次和____________次比较才能查找成功；若采用顺序查找时,分别需要___________次和_________次比较才能查找成功. 三、选择题
1。顺序查找法适合于存储结构为( ）的线性表。
(A）散列存储（B）顺序存储或链接存储（C）压缩存储（D）索引存储 2。对线性表进行二分查找时，要求线性表必须（ ）。 （A）以顺序方式存储（B）以链接方式存储
（C）以顺序方式存储,且结点按关键字有序排序 (D）以链接方式存储,且结点按关键字有序排序
3.采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为（ )
（A)n （B）n/2(C）(n+1)/2（D）（n—1）/2
4.采用二分查找方法查找长度为n的线性表时,每个元素的平均查找长度为（ ）
（A）O(n2）（B)O(log2n）(C)O（n)（D)O(log2n—1） 5。二分查找和二叉排序树的时间性能（ ）。 （A）相同? （B)不相同? （C）无法比较
6.有一个有序表为｛1，3,9,12,32，41，45，62，75，77,82，95,100｝,当二分查找值为82的结点时，（ ）次比较后查找成功。 （A)1（B）2（C)4（D)8
8.有一个长度为12的有序表，按二分查找法对该表进行查找,在表内各元素等概率情况下查找成功所需的平均比较次数为(? ) （A)35/12（B）37/12（C）39/12（D）43/12
9。采用分块查找时，若线性表中共有625个元素,查找每个元素的概率相同,假设采用顺序查找来确定结点所在的块时,每块应分（ ）个结点最佳。 （A）10（B）25(C）6（D）625
10。如果要求一个线性表既能较快地查找，又能适应动态变化的要求，可以采用（ ）查找方法.
（A）分块（B）顺序(C）二分（D）散列
第九章 排序 一、选择题
1。在所有排序方法中，关键字比较的次数与记录得初始排列次序无关的是（ ） （A）希尔排序 (B)起泡排序 （C）插入排序 （D）选择排序
2.设有1000个无序的元素，希望用最快的速度挑选出其中前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）84，79，56，38,40,46 （C)84，79，56,46,40,38 （D）84,56，79,40,46，38
5.一组记录的关键码为(46，79,56，38,40,84)，则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（ )。
（A）38，40，46，56，79，84（B）40，38，46,79，56,84 （C）40,38,46,56,79,84（D）40,38,46，84,56，79
6.一组记录的排序码为(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，72
（C)16,25，48，35,79，82,23，36,40,72（D)16,25,35，48,79,23,36,40,72,82 7。排序方法中,从未排序序列中依次取出元素与己排序序列(初始时为空）中的元素进行比较,将其放入己排序序列的正确位置上的方法,称为（ ） （A)希尔排序（B）起泡排序（C）插入排序（D）选择排序
8。排序方法中,从未排序序列中挑选元素并将其依次放入己排序序列（初始为空)的一端的方法，称为（ ）
（A）希尔排序（B）归并排序（C）插入排序（D）选择排序
9。用某种排序方法对线性表(25,84,21,47,15,27，68，35,20）进行排序时，元素序列的变化情况如下：
（1)25,84,21，47,15，27,68,35，20 ?？(2）20，15,21,25，47，27，68,35，84 （3）15，20，21，25,35,27，47，68,84 ？？（4）15，20,21，25，27,35，47,68，845
则所采用的排序方法是( ）。
（A）选择排序（B）希尔排序(C）归并排序（D）快速排序 10。下述几种排序方法中，平均查找长度最小的是（ ) （A）插入排序（B）选择排序（C）快速排序(D）归并排序 11。下述几种排序方法中,要求内存量最大的是（ ）. （A）插入排序（B)选择排序（C）快速排序（D)归并排序 12.快速排序方法在情况下最不利于发挥其长处.( ）
(A）要排序的数据量太大？？？ （B)要排序的数据中含有多个相同值 （C)要排序的数据已基本有序（D）要排序的数据个数为奇数
13.设有10000个元素组成的无序序列,希望尽快挑选出其中前10个最大值元素,在不改变已有算法结构的前提下，以下几种内排序算法中（?？ ？)最合适。
(A）选择排序法（B）快速排序法(C）堆排序法（D)冒泡排序法。 14.下列四种排序方法中，不稳定的方法是（ ）
（A)直接插入排序 (B)冒泡排序 (C)归并排序 （D）直接选择排序 二、判断题
1.用直接选择排序方法分别对序列S1＝（1，2，3，4,5，6，7）和序列S2＝（7,5，3，2，4，1, 6）进行排序，两者的比较次数不相同。（ ) 2.快速排序是所有排序中速度最快的一种。（ ）
3。堆排序是直到最后一趟排序结束之前所有元素才能在其最终的位置上。（ ) 三、填空题
1。试五种排序方法与对应的操作联系起来: （A)归并排序 ________ （B)选择排序 ________ (C)冒泡排序 _________
(D)插入排序 _________ （E)快速排序__________
(1)从待排序序列中依次取出元素与己排序序列中的元素作比较将其放入己排序序列中的正确的位置上。
（2）从待排序序列中挑选元素，并将其放入己排序序列的一端. (3）依次将相邻的有序表合并成一个有序表。
（4)每次把待排序的区间划分为左、右两个子区间,其中左区间中元素的键值均小于等于基准元素的键值，右区间中元素的键值均大于等于基准元素的键值。
(5)当两个元素比较出现反序（即逆序)时就相互交换位置.
2。在对一组记录（4,38,96，23，15，72,60,45，83）进行直接插入排序时,当把第7个记录60插入到有序表时,为寻找插入位置需比较_______次。 3.在利用快速排序方法对一组记录（54,38,96，23，15，72,60，45,83）进行快速排序时，递归调用而使用的栈的所能达到的最大深度为_________,共需递归调用的次数为_______,其中第二次递归调用是对_________一组记录进行快速排序。
4.在堆排序，快速排序和归并排序中，若只从存储空间考虑，则应首先选取________方法,其次选取________方法,最后选取__________方法：若只从排序结果的稳定性考虑，则应选取________方法：若只从平均情况下排序最快考虑，则应选取________方法:若只从最坏情况下排序最快并且要节省内存考虑，则应选取___________方法.
5。在插入排序、希尔排序、选择排序、快速排序、堆排序、归并排序和基数排序中，排序是不稳定的有___________。
6。在插入排序、希尔排序、选择排序、快速排序、堆排序、归并排序和基数排序中,平均比较次数最少的排序是___________需要内存容量最多的是______________。
7。在堆排序和快速排序中,若原始记录接近正序或反序，则选用___________若原始记录无序则最好选用_____________。
8.在插入和选择排序中,若初始数据基本正序,则选用___________若初始数据基本反序，则选用___________。
9.对n个元素的序列进行起泡排序时，最少的比较次数是_________ 10.两个序列如下： L1＝｛25,57，48，37，92，86，12，33} L2＝{25,37，33,12，48，57,86，92}
用冒泡排序方法分别对序列L1和L2进行排序，交换次序较少的是序列__________。 四、算法设计
1。有一种简单的排序算法，叫做计数排序。这种排序算法对一个待排序的表（用数组表示）进行排序,并将排序结果存放到另一个新的表中。必须注意的是,表中所有待排序的关键字互不相同，计数排序算法针对表中的每个记录,扫描待排序的表一趟，统计表中有多少个记录的关键字比该记录的关键字小。假设对某一个记录,统计出数值为c，那么这个记录在新的有序表中的合适的存放位置即为c。？？？？
(1)给出适用于计数排序的数据表定义。 （2）编写实现计数排序的算法。 (3)对于有n个记录的表,比较次数是多少?
（4)与直接选择排序相比,这种方法是否更好?为什么?
2。修改冒泡排序法以实现双向冒泡排序。即第一次把最大记录放到表尾，第二次将最小记录放到表头，如此反复进行,直至排序结束。试编写此算法。
因篇幅问题不能全部显示，请点此查看更多更全内容