1数据结构习题及参考答案.doc

数据结构习题习题22.1选择题（1）线性表是具有n个 _的有限序列（n!=0）。A.表元素 B.字符C.数据元素 D.数据项（2）顺序表的存储结构是一种_的存储结构。A.随机存取 B.顺序存取C.索引存取 D.HASH存取（3）在一个长度为n的顺序表中，向第i个元素（1=inext=p-next; p-next=-s; B.q-next=s; s-next=p;C.p-next=s-next; s-next=p; D.p-next=s; s-next=q;(8)设指针变量p指向单链表结点A，则删除结点A的后继结点B的操作为_。A.p-next=p-next-next B.P=P-nextC.p=p-next-next D.P-next=p(9)在一个以h为头的单循环链表中，p指针指向链尾的条件是_.A.P-next=h B.p-next=NULLC.p-next-next=h D.p-data=-1(10)对于只在首尾两端进行插入操作的线性表，宜采用的存储结构为_。A.顺序表 B.用头指针表示的单循环链表C.单链表 D.用尾指针表示的单循环链表2.2填空题（1）线性表是n个元素的_。（2）线性表的存储结构有_。（3）设线性表中有n个数据元素，则在顺序存储结构上实现顺序查找的平均时间复杂度为_，在链式存储结构上实现顺序查找的平均时间复杂度为_。（4）设顺序线性表中有n个数据元素，则第i个位置上插入一个数据元素需要移动表中_个数据元素；删除第i个位置上的数据元素需要移动表中_个元素。（5）若频繁地对线性表进行插入与删除操作，该线性表应采用_存储结构。（6）链式存储结构中的结点包含_域和_域。（7）在双链表中，每个结点有两个指针域，一个指向_，另一个指向_。（8）对于一个长度为n的单链存储的线性表，在表头插入元素的时间复杂度为_，在表尾插入时间的复杂度为_。（9）设指针变量p指向单链表中的结点A，指针s指向被插入结点B，则在结点A的后面插入结点B的操作序列为_。（10）设指针变量p指向单链表中的结点A，则删除结点A的后继结点（假设存在）的语句序列我为： S=p-next; p-next=_；free(s)；习题2参考答案2.1选择题(1). C. (2). B. (3). B. (4). B. 5. D. 6. B. 7. B. 8. A. 9. A. 10. D.2.2.填空题(1). 有限序列(2). 顺序存储和链式存储(3). (n) O(n) (4). n-i+1 n-i (5). 链式(6). 数据 指针(7). 前驱 后继(8). (1) (n) (9). s-next=p-next; p-next=s ;(10). s-next习题三3.1选择题1）下列说法正确的是（）A.堆栈是在两端操作、先进后出的线性表B.堆栈是在一端操作、先进先出的线性表C.队列是在一端操作、先进先出的线性表D.队列是在两端操作、先进先出的线性表2）栈和队列的共同点是（）A.都是先进先出 B.都是先进先出C.只允许在端点出插入和删除元素D.没有共同点3）以下数据结构中（）是非线性结构。 A.队列B.栈C.线性表D.二叉树4）若一个栈的入栈序列是1，2,3，n。其输出序列为p1,p2,p3,pn,p1=n,则pi为（）A. IB. N-iC. N-i+1D. 不确定5）当利用大小为N的一位素组顺序存储一个栈时，假定用top=N表示栈空，则向这个栈插入一个元素时，首先应执行（）语句修改top指针。A.top+B.Top-C.Top=0D.Top6）4个元素s栈的顺序是A,B,C,D,经运算，pop(s)后栈顶元素是（）A. A B. BC. C D.D7)一个栈的输入序列是a，b，c，d，e，则栈的不可能的输出序列是（）A. adcba B. decbaC. dceab D. abcde8)设输入序列是1,2,3，n，经过栈的作用后输出序列的第一个元素是n，则输出序列中第i个输出元素是（）A.n-iB.n-1-iC.n+1-iD.不能确定9）字符A、B、C、D依次进入一个栈，按出栈的先后顺序组成不同的字符串，至多可以组成（）个不同的字符串A.15 B.14C.16 D.2110)递归函数f(n)=f(n-1)+n(n1)的递归出口是（）A.f(1)=0 B.f(1)=1C.f(0)=1 D.f(n)=n11)设指针变量top指向当前链式栈的栈顶，则删除栈顶的元素的操作序列为（）A.top=top+1 B.top=top-1C.top-next=top D.top = top-next12)中缀表达式A-(B+C/D)*E的后缀表达式是（）A.ABC+D/*E- B.ABCD/+E*-C.AB-C+D/E* D.ABC-+D/E*13)用front和rear分别表示顺序循环队列的队首和队尾指针，判断队空的条件是（）A.front+1=rear B.(rear+1)%maxsize = front C.front=0 D.front=rear14)判定一个循环队列QU（最多元素为m0）为满队列的条件是（）A.QU-front=QU-rear B.QU-front!=QU-rearC.QU-front=（QU-rear+1）%m0 D.QU-front!=（QU-rear+1）%m0 15）设栈s和队列Q的初始状态为空。元素E1，E2,E3,E4,E5和E6依次通过栈S，一个元素出栈后即进入队列Q。若6个元素出列的顺序为E2，E4，E3,E6，E5和E1。则栈S的容量至少应该是（）A. 6 B.4C. 3 D.216）用链接式存储的队列。在进行插入运算时，（）A.仅修改头指针B.头、尾指针都要修改C.仅修改尾指针D.头、尾指针可能都要修改17）若用一个大小为6的数组实现循环队列，且当前rear和front的值分别为0和3.当从队列中删除一个元素再加入两个元素后。Rear 和front 的值分别为（）A.1和5 B.2和4C.4和2 D.5和118）设顺序循环队列Q0;M-1的头指针分别为F和R，头指针F总是指向头元素的前一位置。尾指针R总是指向队尾元素的当前位置，则该循环队列中的元素个数为（）A.R-F B.F-RC.(R-F+M)%M D.(F-R+M)%M19)设指针变量front便是链式队列的队头指针，指针变量rear表示链式队列的队尾指针，指针变量s指向将要入队列的结点x，则入队列的操作序列为（）A.front-next=s;front=s B.s-next=rear;rear=sC.rear=next=s;rear=s D.s-next=front;rear=s20)当利用大小为N的数组顺序存储的一个队列是，该队列的最大长度为（）A.n-2 B.n-1C.n D.n+13.2填空题1）栈的插入和删除只能在栈顶栈顶进行，后进栈的元素必定先出栈，所以又把栈称为_表；队列的插入和删除操作分别在队列的两端进行。先进队列的元素必定先出队列，所以又把队列称为_表。2）后缀算式9 2 3+ - 10 2 / -的值为_中缀算式（3+4X）- 2Y/3 对应的后缀算式为_3）下面程序段的功能实现数据X进栈，要求在下划线处填上真确的语句。 Typedef struct int s 100； int top; sqstackVoid push(sqstack & stack , int x )If(stack.top=m-1) printf(“overflow”);Else_,_;4)设指针变量P指向双向循环链表中的结点X。则删除结点X需要执行的语句序列为_,_,(设结点中的两个指针域分别为llink 和 rlink ).5)设有一个顺序循环队列中有M个存储单元。则该循环队列中最多能够存储M-1个队列元素；当前实际存储_个队列元素（设头指针F指向当前队头元素的前一个位置，尾指针指向当前队尾元素的位置）6)设有一个顺序共享栈S0；n-1，其中第一个栈项指针top 1 的初值为-1，第二个栈顶指针top2 的初值为n，则判断共享栈满的条件是_7)设F和R分别表示顺序循环队列指针和尾指针，则判断该循环队列为空的条件为_8)顺序循环队列判空的条件是（使用front,rear,n表示）_9)顺序循环队列判满的条件是（使用front,rear,n表示）_10)顺序循环队列MAXSIZE=N，最多可以存储_元素习题3参考答案3.1.选择题(1). D (2). C (3). D (4). C (5). B (6). C (7). C (8). C (9). B (10).AB (11). D (12). B (13). D (14). C (15). C (16). D(17). B (18). C (19). C (20). C 3.2.填空题（1） FILO, FIFO（2） -1, 3 4 X * + 2 Y * 3 / -（3） stack.top+, stack.sstack.top=x（4） pllink-rlink=p-rlink, p-rlink-llink=p-rlink（5） (R-F+M)%M（6） top1+1=top2（7） F=R（8） front=rear（9） front=(rear+1)%n（10） N-1习题44.1 选择题（1）如下陈述中正确的是_。A.串是一种特殊的线性表 B.串的长度必须大于零C.串中的元素只能是字母 D.空串就是空白串（2） 下列关于串的叙述中，正确的是_。A.串长度是指串中不同字符的个数B.串是n个字母有序数列C.如果两个串含有相同的字符，则它们相等D.只有当两个串的长度相等，并且各个对应位置的字符都相符是串才相等（3） 字符串的长度是指_。A.串中不同字符的个数 B.串中不同字母的个数C.串中所含字符的个数 D.串中不同数字的个数(4) 两个字符串长度相等的充要条件是_。A.两个字符串长度相等 B.两个字符串中对应位置上的字符相等C.同时具备（A）和（B）D.以上答案都不对（5） 串是一种特殊的线性表，其特殊性体现在_。A.可以顺序存储 B.数据元素是一个字符C.可以连接存储 D.数据元素可以是多个字符（6）设有两个串p和q，求q在p中首次出现的位置的运算称为_。A.链接B.模式匹配C.求子串D.求串长（7）设串sI=“ABCDEFG”,S2=“PQRST”,函数con(X,Y)返回X和Y串的连接串，subs（s,I,j）返回串s的从序号i的字符开始的j个字符组成的字串，len(s)返回串s的长度，则con(subs(sI,2,len(s2),2的结果串是_。A.BCDEF B.BCDEFGC.BCPQRST D.BCDEFEF（8）函数substr(“DATASTRUCTURE”,5,9)的返回值为_。A.“STRUCTURE” B.“DATA”C.“ASTRUCTUR” D.“DATASTRUCTURE”(9) 常对数组进行的两种基本操作是_。A.建立与删除 B.索引与修改C.查找与修改 D.查找与索引（10） 设串S=“IAMATEACHER!”,其长度是_。A.16 B.11 C.14 D.154.2 填空题（1）两个串相等的充要条件是_。（2）空串是_，其长度为_。（3）空格串是_，其长度是_。（4）s=“I am a men”长度为_。（5）s1=“hello”，s2=“boy”,s1,s2连接后为_。（6）s=“this is the main string”，sub=“string”,strindex(s,sub)是（7）int a1010,已知a=1000，sizeof(int)=2,求a33地址（8）设有两个串p和q，求q和p中首次出现的位置的运算称为_。（9）串的长度是指：_。（10）s=“xiaotech”所含字串的个数是_。习题4参考答案4.1 选择题：(1). A (2). D (3). C (4). C (5). B (6). B (7). D (8). A (9). B (10). D4.2 填空题：（1）串长相等且对应位置字符相等（2）不含任何元素的串，0（3）所含字符均是空格，所含空格数（4）10（5）“helloboy”（6）18（7）1066（8）由零个或多个任意字符组成的字符序列（9）串中所含不同字符的个数（10）36 第五章 一、选择题 1.树最适合用来表示（）。 A. 有序数据元素 B. 无序数据元素 C. 元素间具有分层次关系的数据 D. 元素间无联系的数据 2.在m叉树中，度为0的结点称为（）。 A. 兄弟 B. 树叶 C. 树根 D. 分支结点 3.如果树的结点A有4个兄弟，而且B为A的双亲，则B的度为（）。 A. 3 B. 4 C. 5 D. 1 4.根据二叉树的定义可知二叉树共有（）种不同的形态。 A. 4 B. 5 C. 6 D. 7 5.由3个结点可以构造出（）种不同形态的二叉树。 A. 3 B. 4 C. 5 D. 6 6.具有20个结点的二叉树，其深度最多为（）。 A. 4 B. 5 C. 6 D. 20 7.高度为h的满二叉树的结点数是（）个。 A. log2h+1 B. 2h+1 C. 2h-1 D. 2h-1 8.深度为5的二叉树至多有（）个据点。 A. 16 B. 32 C. 31 D. 10 9.设一颗二叉树共有50发业主据点（终端据点），则共有（）个度为2的结点。 A. 25 B. 49 C. 50 D. 51 10.一颗二叉树中根结点的编号为1，而且23好结点有左孩子但没有右孩子，则完全二叉树总共有（）个结点。 A. 24 B. 45 C. 46 D. 47 11.二叉树的第3层最少有（）个结点。 A. 0 B. 1 C. 2 D. 3 12.设n、m为一颗二叉树上的俩个结点，在中序遍历时，n在m之前的条件是（）。 A. n在m的右方 B. n是m祖先 C. n在m的左方 D. n是m子孙 13.某二叉树的先序序列和后序序列正好相反，则该二叉树可能是（）的二叉树。 A. 高度大于1的左单支 B. 高度大于1的右单支 C. 最多只有一个结点 D. 既有左孩子又有右孩子 14.某二叉树的中序序列和后序序列正好相反，则该二叉树一定是（）的二叉树。 A. 空或只有一个结点 B, 高度等于其结点数 C. 任一结点无左孩子 D. 任一结点无右孩子 15.有n个结点的二叉树链共有（）个空指针域。 A. n-1 B. n C. n+1 D. n+2 二、填空题 1. 一颗深度为5的二叉树，至少有 1 个叶子结点。 2.一颗完全二叉树采用顺序存储结构，每个结点占4字节，设编号为5的元素地址为1016，且它有左孩子和右孩子，则该左孩子和右孩子的地址分别为 1036 和 1040 。 3.一颗完全二叉树采用顺序存储结构，若编号为i的元素左孩子，则该左孩子的编号为2i 。 4.一颗含有n(n1)个结点的K叉树，当k= 1 时深度最大，此最大深度为 n ；当k= n-1 时深度最小，此最小深度为 2 。 5.深度为K的完全二叉树至少有 2k-1 个结点，至多有 2k-1 个结点。 6.已知一颗二叉树的先序遍历序列为EBADCFHGIKJ，中序遍历序列为ABCDEFGHIJK，则该二叉树的后序遍历序列为 ACDBGJKIHFE 。7.如果指针p指向一颗二叉树的一个结点，则判断p没有左孩子的逻辑表达式为p!=NULL。8.在由n个带权叶子结点构造出的所有二叉树中，带权路径长度最小的二叉树称为Huffman树 。9.在树的孩子兄弟表示法中，每个结点有俩个指针域，一个指向 其第一个孩子；另一个指向 下一个兄弟 。10.树的先根遍历结果与其转换的相应二叉树的 先序遍历 结果相同；树的后根遍历结果与其转换的相应二叉树的 中序遍历 结果相同。习题5参考答案5.1 选择（1）C（2）B（3）C（4）B（5）C（6）D（7）C（8）C（9）B（10）C（11）B（12）C（13）C（14）C（15）C5.2 填空（1）1（2）1036；1040（3）2i（4） 1 ； n ; n-1 ; 2 （5）2k-1；2k-1（6）ACDBGJKIHFE（7）p!=NULL（8）Huffman树（9）其第一个孩子; 下一个兄弟（10）先序遍历；中序遍历6.1 选择题（1）一个有8个顶点的有向图，所有顶点的入度之和与所有顶点的初读之和的差是（）。A. 16 B. 4 C. 0 D. 2(2)一个有n个顶点的连通无向图至少有（）条边。A. n-1 B.n C.n+1 D. n+2(3)具有n个顶点的完全有向图的弧数为（）。A. n(n-1) /2 B. n(n-1) C. n2 D. n2-1(4)一个n 条边的连通无向图.其顶点的个数至多为（）。A. n-1 B. n C. n+1 D. n+2（5）设无向图的顶点个数为n，则该图最多有（）条边。A. n-1 B.n（n-1）/2 C. n（n+1）/2 D. 0(6)任何一个无向连通图的最小生成树（）。A. 只有一颗 B. 有一颗或多颗 C. 一定有多颗 D.可能不存在（7）下列算法中，（）算法用来球图中某顶点到其他所有顶点之间的最短路径。A.Dijkstra B.Floyed C.Prim D.Kruskal(8)在一个无向图中，所有顶点的度数之和等于所有边数的（）倍。A. 2 B. 3 C. 1 D. 1.5（9）下面关于图的存储的叙述中正确的是（）。A. 用邻接表法储存图，占用的存储空间大小只与图中边数有关，而与顶点个数无关 B. 用邻接表法储存图，占用的存储空间大小与图中边数喝顶点个数都有关 C. 用邻接矩阵法储存图，占用的存储空间大小与图中边数喝顶点个数都有关 D. 用邻接矩阵法储存图，占用的存储空间大小只与图中边数有关，而与顶点个数无关（10）设有向无环图G中的有向边集合E=,则下列属于该有向图G的一种拓扑排序序列的是（）A.1，2，3，4 B.2，3，4，1C.1，4，2，3 D.1，2，4，3(11)设有无向图G中的边集合E=(a,b)(a,e)(a,c)(b,e)(e,d)(d,f)(f,c),则从顶点a出发进行深度优先遍历可以得到的一种顶点序列为（）。A.aedfcb B.acfebd C.aebcfd D.aedfbc(12)连通图G中有n个顶点，G的生成树是（）连通子图。A.包含G的所有顶点 B.包含G的所有边C.不必包含G的所有顶点 D .包含G的所有顶点喝所有边（13）设某有向图中有n个顶点，则该有向图对应的邻接表中有（）个表头结点。A.n-1 B.n C. n+1 D. 2n-1（14）设无向图G中有n个顶点，e 条边，则起对应的邻接中的表头结点喝边表结点的个数分别为（）。A. n,e B.e.n C.2n,e D.n,2e (15)用邻接矩阵A 表示有向图G的存储结构，则有向图G中顶点i的入度为（）。A. 第i行非0元素的个数之和 B. 第i列非0元素的个数之和C. 第i行0元素的个数之和 D. 第i列0元素的个数之和（16）用邻接矩阵A表示有向图G的存储结构，则有向图G中顶点i的出度为（）。A. 第i行非0元素的个数之和 B. 第i列非0元素的个数之和C. 第i行0元素的个数之和 D. 第i列0元素的个数之和（17）可以判断一个有向图中是否含有回路的方法为（）。A. 广度优先搜索 B. 深度优先搜索 C.拓扑排序 D. 求最短路径6.2 填空题（1）.一个连通无向图有5个顶点，8条边，则起生成树将要去掉（）条边。（2）.在树结构和图结构中，前趋和后继结点之间分别存在（）和（）的联系。（3）.有n 个顶点的连通图至少有（）条边；有n 个顶点的强连通图则至少有（）条边。（4）.一个具有n个顶点的有向图至少有（）条弧。（5）.如果不知道一个图是有向图还是无向图，但知道它的邻接矩阵是非对称的，那么这个图必定是（）。（6）.在无向图G的邻接矩阵A中，若AIJ=1，则AJI为（）。（7）.无向图用邻接矩阵存储，其所有元素之和表示无向图的边数的（）（8）.无向图用邻接表存储，其所有边表结点之和表示无向图的边数的（）（9）.无向图用邻接表存储，顶点Vi的度为（）。（10）.有向图用邻接表存储，顶点Vi的出度为（）。（11）.图的遍历方式一般有（）和（）两种。（12）.Prim算法的时间复杂度为（），与边数无关，因此适用于求边稠密的网的最小生成树。（13）.如果某有向图的所有顶点可以构成一个拓扑排序序列，则说明该有向图（）。习题6参考答案6.1 选择题（1）C （2）A （3）B（4）C（5）B_条边。（6）B（7）A（8）A（9）B（10）A（11）A（12）A（13）B（14）A（15）B（16）A（17）C6.2 填空（1） 4 （2） 1对多 ; 多对多 （3） n-1 ; n （4） 0_（5） 有向图 （6） 1 （7） 一半 （8） 一半 （9）_第i个链表中边表结点数_（10）_第i个链表中边表结点数_（11）深度优先遍历；广度优先遍历（12）O（n2） （13）_无回路 7.1选择题（1）对于长度为n的无序线性表进行顺序查找，则查找成功、不成功时的平均数据比较次数分别为A n/2 , n B n+1/2 ,n-1C n+1/2 , n D n-1/2 ,n-1（2）请指出在顺序表中2,5,7,10,14,15,18,23,35,41,52中，用二分法查找关键字码12须做 次关键字比较。A 2 B 3 C 4 D 5（3）对线性表进行折半查找时，必须要求线性表 。A 以线性表方式存储B 以链接式方式存储C s以顺序方式存储，且结点按关键字有顺排列D 以链接式方式存储，且结点按关键字有顺排列（4）设二叉排序树中有n个结点，则二叉排序树的平均查找长度为 。A O(1) B O(long2n) C O（n） D （n2）（5）依次插入顺序（50,72,43,85,75,20,35,45,65,30）后建立的二叉搜索树中，查找元素35要进行 元素间的比较。A 4次 B 5次 C 7次 D 10次（6）一颗高度为5的理想平衡树中，最少含有16个结点，最多含有 个结点。A 31 B 32 C 30 D 33（7）对包含N个元素的散列表进行查找，平均查找度 。A 为 O（long2n） B 为O(N)C 不直接依赖于N D 上述三者都不对（8）设散列表中有m个存储单元，散列函数H(key)=key%p,则p最好选择 。A 小于等于m的最大奇数 B 小于等于m的最大素数C 小于等于m的最大偶数 D 小于等于m的最大合数（9） 是Hash查找的冲突处理方法。A 求余法 B 平方取中法 C 二分法 D 开放地址法（10）当a的值较小时，散列存储通常比其他存储方式具有 的查找速度。A 较慢 B 较快 C 相同 D 不确定 （11）对线性表进行折半查找，最方便的存储结构是 。A 顺序表 B 有序的顺序表 C 链表 D 有序的链表（12）对一个排好序的线性表，用二分法检索表中的元素，被检索的表应当采用 表示。A 顺序存储 B 连接存储C 散列法存储 D 存储表示不受限制（13）若在线性表中采用折半查找法查找元素，该线性表应该 。（北京航天大学1999年试题）A 元素按值有序 B 采用顺序存储结构C 元素按值有序，且采用顺序存储结构 D元素按值有序 ，且采用链式存储结构（14）用二分法查找一个长度为10的排好序的线性表，查找不成功时，最多需要比较 次。A 5 B 2 C 4 D 1（15）采用分块查找时，若线性表中共有625个元素，查找每个元素的概率相同，假设采用顺序查找来确定结点所在的块时，每块应分 个结点最佳。A 10 B 25 C 6 D 625（16）如果要求一个线性表既能较快的查找，又能适应动态变化的要求，可以采用 查找方法。A 分块 B 顺序 C 二分 D 散列7.2填空题（1）对于长度为n的线性表，若进行顺序查找，则时间复杂度为 ；若采用折半法查找，则时间复杂度为 。（2）假设在有序线性表A1.20上进行折半查找，则比较一次查找成功的结点数为 ，比较两次查找成功的结点数为 ，比较三次查找成功的结点数为 ， 比较四次查找成功的结点数为 ，比较五次查找成功的结点数为 ，平均查找长度为 。（3）在一棵二叉搜索树中，每个分支结点的左子树上所有结点的值一定 该结点的值，右子树上所有结点的值一定 该结点的值。（4）对于一棵二叉搜索树进行遍历时，得到的结点序列是一个 （5）在一棵m阶B-树上，每个非树根结点的关键字数目最少为 个，最多为 。（6）对于线性表（70 ，34,55,23,65,41,20）进行散列存储时，若选用H（K）=K%7作为散列函数，则散列地址为0的元素有 ，散列地址为6的有 。（8）散列表中解决冲突的两种方法是 和 。（11）最优二叉树（哈夫曼树）、最优查找树均为平均查找路径长度i=1nwihi最小的树，其中对最优二叉树，n表示 ，对最优查找树，n表示 ，构成这两种树 。（12）在分块检索中，对256个元素的线性表分成 块最好，每块的最佳长度是 ；若每块的长度为 ，其平均检索长度为 。 （14）哈希表处理冲突的方法有 。（16）在分块查找中首先查找 ，然后查找相应的 （18）当所有的结点的权值都相等时，用这些结点构造的二叉排序树 遍历它们得到的序列的顺序是一样的。(19)对两棵具有相同关键字集合而形状不同的二叉树， 遍历它们得到的序列的顺序是一样的。习题7参考答案7.1 选择题（1）C (2)C (3) C (4)B (5) A (6)A (7) D (8)B (9)D (10) B(11)B (12)A (13)C (14)C (15)A (16)D (17)C (18)B,C (19)B (20)A7.2 填空题（1） O(n),O(log2n)（2） 1,2,4,8,5, log2(n+1)-1（3） 小于，大于（4） 增序序列（5） ,m-1（6） 70; 34,20,55（7） n/m（8） 开放地址法，链地址法（9） 产生冲突的可能性就越大，产生冲突的可能性就越小（10） 关键码直接（11） , , （12） 16,16,8,21（13） 直接定址法，数字分析法，平方取中法，折叠法，除留余数法，随机数法（14） 开放地址法，再哈希法，链地址法，建立一个公共溢出区（15） 装满程度（16） 索引，快（17） 哈希函数，装填因子（18） 一个结点（19） 中序（20） 等于 习题88.1选择题（1）下述排序算法中，稳定的是 。A.直接选择排序 B.直接插入排序C.快速排序 D.堆排序（2）下列排序算法中， 需要的辅助储存空间最大。A.快速排序 B.插入排序 C.希尔排序 D.基数排序（3）下列各种排序算法中平均时间复杂度为O（n2）是 。A.快速排序 B.堆排序 C.归并排序 D.冒泡排序（4）在基于关键码比较的排序算法中， 算法在最坏情况下，关键码比较次数不高于O（nlog2n）。A.冒泡排序 B.直接插入排序C.二路归并排序 D.快速排序（5）一组记录为46，79，56，38，84，40，则采用冒泡排序法按升序排列时第一趟排序的结果是 。A.46，79，56，38，40，84 B.46，56，38，79，40，84C.38，40，46，56，84，79 D.38，46，79，56，40，84（6）每次从无序表中取出一个元素，把它插入到有序表中的适当位置，此种排序方法叫做 排序。A.插入 B.堆 C.快速 D.归并（7）每次从无序表中挑选出一个最小或最大元素，把它交换到有序表的一端，此种排序方法叫做 排序。A.插入 B.堆 C.快速 D.归并（8）设一组初始记录关键字序列（5，2，6，3，8），以第一个记录关机键字5为基准进行一趟快速排序的结果为 。A.2，3，5，8，6 B.3，2，5，8，6C.3，2，5，6，8 D.2，3，6，5，8（9）设有n个待排序的记录关键字，则在堆排序中需要 个辅助记录单元。A.1 B. n C.nlog2n D.n2（10）对于关键字值排序列（12，13，11，18，60，15，7，18，25，100），用筛选法建堆，必须从关键字值为 的结点开始。A.100 B.100 C.60 D.15（11）下列排序方法中， 方法的比较次数与记录的初始排列状态无关。A.直接插入排序 B.冒泡排序C.快速排序 D.直接选择排序（12）设有关键码初始序列Q，H，C，Y，P，A，M，S，R，D，F，X，新序列F，H，C，D，P，A，M，Q，R，S，Y，X是采用 方法对初始序列进行第一趟排序的结果。A.直接插入排序 B.二路归并排序C.以第一元素为分界元素的快递排序 D.基数排序（13）在待排序文件已基本有序的前提下，下述排序方法中效率最高的是 。A.直接插入排序 B.直接选择排序C.快速排序 D.二路归并排序（14）排序的算法很多，若按排序的稳定性和不稳定性分类，则 是不稳定排序。A.冒泡排序 B.归并排序 C.直接插入排序 D.希尔排序（15）若需在O（nlog2n）的时间内完成对数组的排序，且要求排序是稳定的，则可选排序方法是 。A.快速排序 B.堆排序 C.归并排序 D.直接插入排序（16）将两个各有n个元素的有序表归并成一个有序表，最少的比较次数是 。A.n B.2n-1 C.2n D.n-1（17）下列排序算法中，时间复杂度不受数据初始状态影响，恒为O(long2n)的是 。A.堆排序 B.冒泡排序 C.直接选择排序 D.快速排序（18）下列排序算法中， 算法可能会出现下面情况：初始数据有序时，花费的时间反而最多。A.堆排序 B.冒泡排序 C.快速排序 D.希尔排序（19）数据表A中有10000个元素，如果仅要求求出其中最大的10个元素，则采用 最节省时间。A.堆排序 B.希尔排序 C.快速排序 D.直接选择排序（20）如果只想得到1024个元素组成的序列中第5个最小元素之前的部分排序的序列，用 方法最快。A.冒泡排序 B.快速排序 C.简单选择排序 D.堆排序 8.2填空题（1）当待排序的记录数较大、排序码较随机且对稳定性不做要求时，宜采用_排序；当待排序的记录数较大，存储空间允许且要求排序是稳定时，宜采用_排序。（2）在堆排序的过程中，对任意一个分支结点进行筛运算的时间复杂度为_，整个堆排序过程的时间复杂度为_。（3）快速排序、堆排序、归并排序中，_排序是稳定的。（4）当向一个大根堆插入一个具有最大值的元素时，需要逐层_调整，直到被调整到_位置为止。（5）设一组初始记录关键字序列为（20，18，22，16，30，19），则以20为中轴的一趟快速排序结果为_。（6）设一组初始记录关键字序列为（20，18，22，16，30，19），则根据这些初始关键字序列建成的初始堆为_。（7）设一组初始记录关键字序列为（4