《2022年数据结构复习题目及答案》由会员分享，可在线阅读，更多相关《2022年数据结构复习题目及答案（32页珍藏版）》请在金锄头文库上搜索。
1、学而不思则惘，思而不学则殆数据结构 -C 语言版第一章绪论单项选择题1在数据结构中，数据的基本单位是_ _。A. 数据项B. 数据类型C. 数据元素D. 数据变量2数据结构中数据元素之间的逻辑关系被称为_ _。A. 数据的存储结构B. 数据的基本操作C. 程序的算法D. 数据的逻辑结构3在数据结构中，与所使用计算机无关的是数据的_ _。A. 存储结构B. 逻辑和物理结构C. 逻辑结构D. 物理结构4在链式存储结构中，数据之间的关系是通过_ _体现的。A. 数据在内存的相对位置B. 指示数据元素的指针C. 数据的存储地址D. 指针5计算算法的时间复杂度是属于一种_ _。A. 事前统计的方法B.
2、事前分析估算的方法C. 事后统计的方法D. 事后分析估算的方法6在对算法的时间复杂度进行估计的时候，下列最佳的时间复杂度是_ _。A. n2B. nlogn C. n D. logn 7设使用某算法对n 个元素进行处理，所需的时间是T(n)=100nlog2n+200n+2000，则该算法的渐近时间复杂度为_ _。A. O(1) B. O(n) C. O(200n) D. O(nlog2n) 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 1 页，共 32 页学而不思则惘，思而不学则殆CDCBBDD 第二章线性表单项选择题1链表不具有的特点是_ _
3、。A. 可随机访问任一元素B. 插入和删除时不需要移动元素C. 不必事先估计存储空间D. 所需空间与线性表的长度正比2设顺序表的每个元素占8 个存储单元。第1 个单元的存储地址是100，则第 6 个元素占用的最后一个存储单元的地址为。A. 139 B. 140 C. 147 D. 148 3在线性链表存储结构下，插入操作算法。A. 需要判断是否表满B. 需要判断是否表空C. 不需要判断表满D. 需要判断是否表空和表满4在一个单链表中，若删除p 所指结点的后继结点，则执行。A. p-next = p-next-next; B. p-next = p-next; C. p = p-next-nex
4、t; D. p = p-next; p-next = p-next-next; 5将长度为n 的单链表接在长度为m 的单链表之后的算法时间复杂度为。A. O(n) B. O(1) C. O(m) D. O(m+n) 6需要预分较大空间，插入和删除不需要移动元素的线性表，其存储结构是。A. 单链表B. 静态链表C. 线性链表D. 顺序存储方式ACCABB 填空题1在带表头结点的单链表中，当删除某一指定结点时，必须找到该结点的_结点。2在单链表中，指针p 所指结点为最后一个结点的条件是。3将两个各有n 个元素的有序表归并成一个有序表，其最少的比较次数是。4在一个长度为n 的顺序表中第i 个元素（
5、1i n）之前插入一个元素时，需向后移动元素的个数是。5在长度为n 的顺序表中插入一个元素的时间复杂度为。1 前驱2 p-next=NULL 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 2 页，共 32 页学而不思则惘，思而不学则殆3.1 4.n-i+1 5.O(n) 例题解析【例 2-1】 编写一个算法将一个单链表逆转，要求在原表上进行，不允许重新建链表。解：该算法可以在遍历原表的时候将各结点的指针逆转，从原表的第一个结点开始，头结点的指针在最后修改成指向原表的最后一个结点，即新表的第一个结点。实现本题功能的函数如下：void inverse
6、(Lnode *h) s=h-next; if(s=NULL) return; q=NULL; p=s; while(p!=NULL) p=p-next; s-next=q; /*逆转指针 */ q=s; /*指针前移 */ s=p; h-next=q; /*头指针 h 的后继是 p*/ 【例 2-2】 编写一算法将两个按元素值递增有序排列的单链表A和 B归并成一个按元素值递增有序排列的单链表C。解：对于两个或两个以上的，结点按元素值有序排列的单链表进行操作时，应采用“指针平行移动， 依次扫描完成” 的方法。 从两表的第一个结点开始顺链表逐个将对应数据元素进行比较， 复制小的并插入c 表尾。当
7、两表中之一已到表尾，则复制另一个链表的剩余部分，插入到 c 表尾。设pa、pb 分别指向两表当前结点，p 指向 c 表的当前表尾结点。若设A中当前所指的元素为a，B中当前所指的元素为b，则当前应插入到 C 中的元素c 为babbaac例如： A=(3,5,8,11) B=(2,6,8,9,11,15,20) 则 C=(2,3,5,6,8,8,9,11,11,15,20) 实现本题功能的函数如下：Lnode *hb(Lnode *pa,Lnode *pb) Lnode * p,*q,*pc; pc=(Lnode*)malloc(sizeof(Lnode); /* 建立表 c 的头结点 pc*/
8、精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 3 页，共 32 页学而不思则惘，思而不学则殆p=pc; /*p 指向 C 表头结点 */ while(pa!=NULL&pb!=NULL) q=(Lnode*)malloc(sizeof(Lnode); /*建立新结点q*/ if(pb-datadata) /* 比较 A、B 表中当前结点的数据域值的大小*/ q-data=pb-data; /*B 中结点值小，将其值赋给q 的数据域 */ pb=pb-next; /*B 中指针 pb 后移 */ else q-data=pa-data; /*相反，
9、将 A 结点值赋给q 的数据域 */ pa=pa-next; /*A 中指针 pa后移 */ p-next=q; /*将 q 接在 p 的后面 */ p=q; /*p 始终指向 C 表当前尾结点 */ while(pa!=NULL) /*若表 A 比 B 长，将 A 余下的结点链在C 表尾 */ q=(Lnode*)malloc(sizeof(Lnode); q-data=pa-data; pa=pa-next; p-next=q; p=q; while(pb!=NULL) /*若表 B 比 A 长，将 B 余下的结点链在C 表尾 */ q=(Lnode*)malloc(sizeof(Lnod
10、e); q-data=pb-data; pb=pb-next; p-next=q; p=q; p-next=NULL; p=pc; /*p 指向表 C 的头结点 pc*/ pc=p-next; /*改变指针状态，使pc 指向 p 的后继 */ free(p); /* 释放 p 空间 */ return (pc); 此算法的时间复杂度为O(m+n) ，其中 m，n 分别是两个被合并表的表长。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 4 页，共 32 页学而不思则惘，思而不学则殆第三章栈和队列单项选择题1在初始为空的堆栈中依次插入元素f，e，d，
11、c，b，a 以后，连续进行了三次删除操作，此时栈顶元素是。A. B.C.D. 2若某堆栈的输入序列是1，2，3，.，n，输出序列的第一个元素为n，则第 i 个输出元素为。A. i B. n-i C. n-i+1 D. 哪个元素无所谓3向一个栈顶指针为h 的带头结点链栈中插入指针s 所指的结点时， 应执行。A. h-next = s; B. s-next = h; C. s-next = h; h = h-next; D. s-next = h-next; h-next=s; 4一个栈的入栈序列是a，b，c，d，e，则栈的不可能的输出序列是。A. edcba B. decba C. dceab
12、D. abcde 5栈和队列的共同点是。A. 都是先进后出B. 都是先进先出C. 只允许在端点处插入和删除元素D. 没有共同点6对于循环队列。A. 无法判断队列是否为空B. 无法判断队列是否为满C. 队列不可能满D. 以上说法都不是7. 若用一个大小为6 的数组来实现循环队列，且当前队尾指针rear 和队头指针front 的值分别为 0 和 3。当从队列中删除一个元素，再加入两个元素后，rear 和 front 的值分别为。A. 1 和 5 B. 2 和 4 C. 4 和 2 D. 5 和 1 8. 判定一个循环队列QU（最多元素为m0）为满队列的条件是。A. QU-front=QU-rear
13、 B. QU-front!=QU-rear C. QU-front=(QU-rear+1) % m0 D. QU-front!=(QU-rear+1) % m0 9.判定一个循环队列QU（最多元素为m0）为空的条件是。A. QU-front=QU-rear B. QU-front!=QU-rear C. QU-front=(QU-rear+1) % m0 D. QU-front!=(QU-rear+1) % m0 BCDCCDACA 填空题1在求表达式值的算符优先算法中使用的主要数据结构是。2设有一个空栈，现输入序列为1，2，3，4，5。经过 push，push，pop，push，pop，pu
14、sh，pop，push 后，输出序列是。3仅允许在同一端进行插入和删除的线性表称为。7在顺序栈s 中，栈为空的条件是，栈为满的条件是_。4用 S表示入栈操作，X 表示出栈操作，若元素入栈顺序为1234，为了得到1342 出栈顺精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 5 页，共 32 页学而不思则惘，思而不学则殆序，相应的S、X 操作串为。5用一个大小为1000 的数组来实现循环队列，当前rear 和 front 的值分别为0 和 994，若要达到队满的条件，还需要继续入队的元素个数是。1.栈2. 2 3 4 3.栈4.s.top=s.bas
15、e, s.top-s.base=s.stacksize SXSSXSXX 5.993 例题解析【例 3-1】 编程实现：用除法把十进制数转换成二进制数。解：算法思想： 用初始十进制数除以2 把余数记录下来并且若商不为0 则再用商去除以2 直到商为0，这时把所有的余数按出现的逆序排列起来（先出现的余数排在后面，后出现的余数排在前面）就得到了相应的二进制数，如把十进制数35 转换成二进制数的过程如图3-1 所示。图 3-1 十进制数转换成二进制数的过程由题意可知， 我们可以用一个栈来保存所有的余数，当商为 0 时则让栈里的所有余数出栈则可以得到正确的二进制数，算法可描述如下：void conver
16、sion() Stack S; int n; InitStack(&S); printf(Input a number to convert:n); scanf(%d,&n); if(n0）个结点的满二叉树共有个叶子和个非终端结点。答：21inlog212logn4. 具有 n 个结点的完全二叉树的深度为。5. 哈夫曼树是带权路径度_的树，通常权值较大的结点离根_。最短较近6在 _遍历二叉树的序列中，任何结点的子树上的所有结点，都是直接跟在该结点之后。1.答：k1 k2 k5 k7 k4 2 3 4 k5，k6 k1 2. 3. 4.floor(log2n)+1 5. 6. 先根例题解析【例
17、6-1】由如图6-1 所示的二叉树，回答以下问题。（1）其中序遍历序列为；（2）其前序遍历序列为；（3）其后序遍历序列为；（4）该二叉树的中序线索二叉树为；（5）该二叉树的后序线索二叉树为；（6）该二叉树对应的森林是。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 12 页，共 32 页学而不思则惘，思而不学则殆bacdeghfi图 6-1 1 棵二叉树解：中序遍历序列为dgbaechif 前序遍历序列为abdgcefhi 后序遍历序列为gdbeihfca 该二叉树的中序线索二叉树如图6.1.1(a)所示该二叉树的后序线索二叉树如图6-1-1 (b
18、)所示该二叉树对应的森林如图6-1-2 所示图 6-1-1 二叉树的中序线索二叉树和后序线索二叉树baedfdihg图 6-1-2 二叉树对应的森林精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 13 页，共 32 页学而不思则惘，思而不学则殆综合题1二叉树结点数值采用顺序存储结构，如表6-2 所示。表 6-2 二叉树的顺序存储结构1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 e a f d g c j h i b （1）画出二叉树表示；（2）写出前序遍历，中序遍历和后序遍历的结果；（3）写出
19、结点值c 的父结点，其左、右孩子。解：（1）该二叉树如图6-9 所示。图 6-9 1 棵二叉树（2）本题二叉树的各种遍历结果如下：前序遍历： eadcbjfghi 中序遍历： abcdjefhgi 后序遍历： bcjdahigfa （3）c 的父结点为d，左孩子为j，没有右孩子。2有一份电文中共使用5 个字符： a、b、c、d、e，它们的出现频率依次为4、7、 5、2、9， 试画出对应的哈夫曼树 （请按左子树根结点的权小于等于右子树根结点的权的次序构造），并求出每个字符的哈夫曼编码。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 14 页，共 32
20、 页学而不思则惘，思而不学则殆解：依题意，本题对应的哈夫曼树如图6-15 所示。各字符对应的哈夫曼编码如下：a： 001 b： 10 c： 01 d： 000 e： 11 图 6-15 一棵哈夫曼树3设给定权集w=2 ，3，4，7，8，9 ，试构造关于w 的一棵哈夫曼树，并求其加权路径长度WPL 。解：本题的哈夫曼树如图6-16 所示。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 15 页，共 32 页学而不思则惘，思而不学则殆图 6-16 一棵哈夫曼树其加权路径长度WPL=7 2+82+43+24+34+92=80 4. 已知一棵二叉树的中序序
21、列为cbedahgijf，后序序列为cedbhjigfa，画出该二叉树的先序线索二叉树。解：由后序序列的最后一个结点a 可推出该二叉树的树根为a，由中序序列可推出a的左子树由cbed 组成，右子树由hgijf 组成，又由cbed 在后序序列中的顺序可推出该子树的根结点为b，其左子树只有一个结点c，右子树由ed 组成，显然这里的e 是根结点，其右子树为结点d，这样可得到根结点a 的左子树的先序序列为：bcde；再依次推出右子树的先序序列为：fghij 。因此该二叉树如图6-17 所示。图 6-17 二叉树设二叉树的先序线索链表如图6-18 所示。精选学习资料 - - - - - - - - -
22、名师归纳总结 - - - - - - -第 16 页，共 32 页学而不思则惘，思而不学则殆图 6-18 二叉树的先序线索链表第 7 章 图单项选择题1在一个图中，所有顶点的度数之和等于所有边数的倍。A. 1/2 B. 1 C. 2 D. 4 2在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的B 倍。A. 1/2 B. 1 C. 2 D. 4 3具有4 个顶点的无向完全图有条边。A. 6 B. 12 C. 16 D. 20 4具有6 个顶点的无向图至少应有条边才能确保是一个连通图。A. 5 B. 6 C. 7 D. 8 5在一个具有n 个顶点的无向图中，要连通全部顶点至少需要条边。A
23、. n B. n+1 C. n-1 D. n/2 6对于一个具有n 个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是。A. n B. (n-1)2C. n-1 D. n27对于一个具有n 个顶点和e 条边的无向图，若采用邻接表表示，则所有邻接表中的结点总数是。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 17 页，共 32 页学而不思则惘，思而不学则殆A. e/2 B. e C. 2e D. n+e 8已知一有向图的邻接表存储结构如图7-2 所示。（1）根据有向图的深度优先遍历算法，从顶点v1 出发，所得到的顶点序列是。A. v1 ，v2，v
24、3， v5，v4 B. v1，v2，v3，v4，v5 C. v1，v3，v4，v5，v2 D. v1，v4，v3，v5，v2 （2）根据有向图的广度优先遍历算法，从顶点v1 出发，所得到的顶点序列是。A. v1 ，v2，v3，v4，v5 B. v1， v3，v2，v4，v5 C. v1，v2，v3， v5，v4 D. v1， v4，v3，v5，v2 123245243454图 7-2 一个有向图的邻接表存储结构9. 判定一个有向图是否存在回路除了可以利用拓扑排序方法外，还可以利用。A. 求关键路径的方法B. 求最短路径的Dijkstra 方法C. 广度优先遍历算法D. 深度优先遍历算法1-5.
25、CBAAC 6-9 DCCBD 填空题1n 个顶点的连通图至少条边。2在无向图G 的邻接矩阵A 中，若Aij 等于1，则Aji 等于。3已知图 G 的邻接表如图7-3 所示， 其从顶点v1 出发的深度优先搜索序列为，其从顶点v1 出发的广度优先搜索序列为。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 18 页，共 32 页学而不思则惘，思而不学则殆v1v2v5v4v3v5v6v4v6v3v2v3v4v5v6图 7-3 G 的邻接表4设 x,y 是图 G 中的两顶点， 则（x,y）与（y,x）被认为 _边，但 与 是_的两条弧。答：无向，有向5.已
26、知一个图的邻接矩阵表示，删除所有从第i 个结点出发的边的方法是。6 在有向图的邻接矩阵上，由第 i 行可得到第 _个结点的出度， 而由第 j 列可得到第 _ _个结点的入度。i j 7. 在无向图中，如果从顶点v 到顶点 v 有路径，则称v 和 v 是_的。如果对于图中的任意两个顶点vi,vj V，且 vi 和 vj 都是连通的，则称G 为 _。连通，连通图1.n-1 2.1 3.答：v1，v2，v3， v6，v5，v4 v1，v2，v5，v4，v3，v6 4.5. 将矩阵第i 行全部置为0 5.6.例题解析【例 7-1】对 m个顶点的无向图G，采用邻接矩阵，如何判别下列有关问题：（1） 图中
27、有多少条边？（2） 任意两个顶点i 和 j 是否有边相连？精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 19 页，共 32 页学而不思则惘，思而不学则殆（3） 任意一个顶点的度是多少？解：邻接矩阵非零元素个数的总和除以2。当 A i,j 0 时，表示两顶点i,j 之间有边相连。计算邻接矩阵上顶点对应行上非零元素的个数。综合题1给出如图7-4 所示的无向图G 的邻接矩阵和邻接表两种存储结构。图 7-4 无向图 G 解：图G 对应的邻接矩阵和邻接表两种存储结构分别如图所示。2用广度优先搜索和深度优先搜索对如图7-5 所示的图G 进行遍历 （从顶点1
28、出发） ，给出遍历序列。解：搜索本题图的广度优先搜索的序列为：1，2，3，6，4，5，8，7，深度优先搜索的序列为： 1，2，6，4， 5，7，8， 3。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 20 页，共 32 页学而不思则惘，思而不学则殆21365478图 7-5 无向图 G 3使用普里姆算法构造出如图7-6 所示的图G 的一棵最小生成树。2136546515536642图 7-6 无向图 G 解：使用普里姆算法构造棵最小生成树的过程如图7-11 所示。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - -
29、- -第 21 页，共 32 页学而不思则惘，思而不学则殆21365415342131136141364142213641542(a)(b )(c)(d)(e)图 7-11 普里姆算法构造最小生成树的过程4使用克鲁斯卡尔算法构造出如图7-7 所示的图G 的一棵最小生成树。21365471 86742 31 22 51 582 051 0图 7-7 无向图 G 解：使用克鲁斯卡尔算法构造棵最小生成树的过程如图7-12 所示。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 22 页，共 32 页学而不思则惘，思而不学则殆1642136476485213
30、65471864128523521367645(a)(b)(c)(d)(e)(f)2136547641285图 7-12 克鲁斯卡尔算法构造最小生成树的过程第 8 章查找单项选择题1. 顺序查找法适合于存储结构为的线性表。A. 散列存储 B. 顺序存储或链接存储C. 压缩存储 C. 索引存储2. 对线性表进行折半查找时，要求线性表的存储方式是。A. 顺序存储B. 链接存储C. 以关键字有序排序的顺序存储D. 以关键字有序排序的链接存储3. 对有 18 个元素的有序表作二分（折半）查找，则查找A3 的比较序列的下标为。A. 1.2.3 B. 9.5.2.3 C. 9.5.3 D. 9.4.2.3
31、 4. 如果要求一个线性表既能较快地查找，又能适应动态变化的要求，可以采用查找方法。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 23 页，共 32 页学而不思则惘，思而不学则殆A. 分块 B. 顺序 C. 二分 D. 散列5. 有一个有序表为2，5，7，11，22，45，49，62，71，77，90，93，120 ，当折半查找值为 90 的结点时，经过次比较后查找成功。A. 1 B. 2 C. 4 D. 8 6. 设哈希表长 m=14，哈希函数 H(key)=key % 11。表中已有 4 个结点：addr(14)=3 ，addr(38)=5
32、，addr(61)=6 ，addr(85)=8 ，其余地址为空，如用线性探测再散列处理冲突，关键字为 49 的结点的地址是。A. 7 B. 3 C. 5 D. 4 7. 在采用链接法处理冲突的开散列表上，假定装填因子a 的值为 4 ，则查找任一元素的平均查找长度为。A. 3 B.3.5 C.4 D.2.5 1-4 BCDA 5-7CAA 填空题1. 在各种查找方法中，平均查找长度与结点个数 n 无关的查法方法是。2. 二分查找的存储结构仅限于。3. 在散列存储中，装填因子的值越大，则；的值越小，则。 存取元素时发生冲突的可能性就越大 存取元素时发生冲突的可能性就越小4. 对于二叉排序树的查找，
33、若根结点元素的键值大于被查元素的键值，则应该在二叉树的_上继续查找。5. 高度为 8 的平衡二叉树至少有_个结点。6. 在散列函数H(key)=key % p 中， p 应取。1.散列表查找2.有序的顺序存储结构3.4.左子树5.54 6.素数例题解析【例 8-1】设有一组关键字19 ，01，23，14， 55，20，84， 27，68，11，10，77，采用哈希函数： H(key)=key % 13 , 采用开放地址法的二次探测再散列方法解决冲突，试在 0 18 的散列地址空间中对该关键字序列构造哈希表。解：依题意， m=19，二次探测再散列的下一地址计算公式为：d1=H(key) dj2=
34、( d1+j*j) % m 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 24 页，共 32 页学而不思则惘，思而不学则殆d12 j=( d1-j*j) % m； j=1 ，2，. 其计算函数如下：H(19)=19 % 13=6 H(01)=01 % 13=1 H(23)=23 % 13=10 H(14)=14 % 13=1 ( 冲突 ) H(14)=(1+1*1) % 19=2 H(55)=55 % 13=3 H(20)=20 % 13=7 H(84)=84 % 13=6 ( 冲突 ) H(84)=(6+1*1) % 19=7 ( 仍冲突 )
35、H(84)=(6-1*1) % 19=5 H(27)=27 % 13=1 ( 冲突 ) H(27)=(1+1*1) % 19=2 ( 冲突 ) H(27)=(1-1) % 19=0 H(68)=68 % 13=3 ( 冲突 ) H(68)=(3+1*1) % 19=4 H(11)=11 % 13=11 H(10)=10 % 13=10 ( 冲突 ) H(10)=(10+1*1) % 19=11 ( 仍冲突 ) H(10)=(10-1*1) % 19=9 H(77)=77 % 13=12 因此：各关键字的记录对应的地址分配如下： addr(27)=0 addr(01)=1 addr(14)=2
36、addr(55)=3 addr(68)=4 addr(84)=5 addr(19)=6 addr(20)=7 addr(10)=9 addr(23)=10 addr(11)=11 addr(77)=12 其他地址为空。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 25 页，共 32 页学而不思则惘，思而不学则殆综合题1. 设散列表为 T0.12 ，散列函数为 H（key）= key%13 ，给定键值序列是39，36，28，38， 44，15，42， 12，06，25 ，请画出分别用拉链法和线性探查法处理冲突时所构造的散列表，并求出在等概率情况下，
37、这两种方法查找成功和查找失败时的平均查找长度。解 用散列函数 H（key）= key% 13 计算出键值序列的散列地址。并用探查次数表示待查键值需对散列表中键值比较次数。键值序列：39， 36，28，38， 44，15，42，12，06，25散列地址： 0 ，10，2，12，5，2，3， 12，6， 12 （1）线性探查法处理冲突用线性探查法处理冲突构造的散列表见表8-1 所示。表 8-1 用线性探查法处理冲突构造的散列表下标0 1 2 3 4 5 6 7 8 9 10 11 12 T0.1239 12 28 15 42 44 06 25 36 38 查找成功探查次数1 3 1 2 2 1 1
38、 9 1 1 查找失败探查次数9 8 7 6 5 4 3 2 1 1 2 1 10 在等概率的情况下，查找成功的平均查找长度ASL= （16+22+31+91）/10=2.2 设待查键值 k 不在散列表中：若 H（ k）= k% 13= d，则从 i=d开始顺次与 T i 位置的键值进行比较，直到遇到空位，才确定其查找失败，同时累计 k键值的比较次数，例如若 k% 13= 0 ，则必须将 k与 T 0 、T 1 、 T8中的键值进行比较之后，发现 T8为空，比较次数为 9 、类似地可对 k% 13=1，2， 3， 12 进行分析可得查找失败的平均查找长度。ASL =（9+8+7+6+5+4+3
39、+2+1+1+10）/13 = 59/13 = 4.54 （2）拉链法处理冲突用拉链法处理冲突构造的散列表见图8-2 所示。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 26 页，共 32 页学而不思则惘，思而不学则殆图 8-2 拉链法处理冲突构造的散列表在等概率的情况下查找成功的平均查找长度：ASL= （17+22+31） /10=1.4 设待查键值 k 不在散列表中，若 k% 13= d 。则需在 d 链表中查找键值为 k 的结点，直到表尾，若不存在则查找失败，设 d 链表中有 i个结点，则 k 需与表中键值比较 i次，查找失败的平均长度为：
40、ASL= （1+ 0+ 2+ 1+ 0+ 1+ 1+ 0+0+0+1+0+3）/13=10/13 = 0.77 2. 线性表的关键字集合87 ，25，310，08，27，132，68， 95，187，123，70，63，7 ，共有 13 个元素，已知散列函数为：H(k) = k % 13 ，采用拉链法处理冲突。设计出这种链表结构，并计算该表的成功查找的平均查找长度。解：依题意，得到：H(87)=87 % 13=9 H(25)=25 % 13=12 H(310)=310 % 13=11 H(08)=08 % 13=8 H(27)=27 % 13=1 H(132)=132 % 13=2 H(68)
41、=68 % 13=3 H(95)=95 % 13=4 H(187)=187 % 13=5 H(123)=123 % 13=6 H(70)=70 % 13=5 H(63)=63 % 13=11 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 27 页，共 32 页学而不思则惘，思而不学则殆H(47)=47 % 13=8 采用拉链法处理冲突的链接表如图8-3 所示。成功查找的平均查找长度：ASL=(110+23)/13=16/13=113327 132 68 95 70 123 08 87 63 25 310 47 187 0 1 2 3 4 5 6
42、7 8 9 10 11 12 图 8.3 处理冲突的链接表精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 28 页，共 32 页学而不思则惘，思而不学则殆第 9 章排序单项选择题1. 在所有排序方法中，关键字比较的次数与记录的初始排列次序无关的是。A. 希尔排序 B. 起泡排序C. 插入排序 D. 选择排序2. 设有 10000 个无序的元素，希望用最快的速度挑选出其中前 10 个最大的元素，排序方法最好选用。A. 起泡排序 B. 快速排序C. 堆排序 D. 基数排序3. 在待排序的元素序列基本有序的前提下，效率最高的排序方法是。A. 插入排序 B
43、. 选择排序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. 在下列算法中，算法可能出现下列情况：在最后一趟开始之前，所有的元素都不在其最终的位置上。A堆排序 B冒泡排序 C插入排序 D. 快速排序6. 一组记录的关键码为(46，79，56，38，40，84) ，则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为。A.
44、 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 7. 一组记录的排序码为(48 ，16， 79 ，35，82，23，36，72) ，按归并排序的方法对该序列进行一趟归并后的结果为。A. 16 48 35 79 23 82 36 72 B. 16 35 48 79 82 23 36 72 C. 16 48 35 79 82 23 36 72 D. 16 35 48 79 23 36 72 82 8. 排序方法中， 从未排序序列中依次取出元素与已排序序列（初始时为空） 中的
45、元素进行比较，将其放入已排序序列的正确位置上的方法，称为。A. 希尔排序 B. 起泡排序C. 插入排序 D. 选择排序9. 排序方法中，从未排序序列中挑选元素，并将其依次放入已排序序列（初始时为空）的一端的方法，称为。A. 希尔排序 B. 归并排序C. 插入排序 D. 选择排序1-5 DCABC 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 29 页，共 32 页学而不思则惘，思而不学则殆6-9 CACD 填空题1. 在对一组记录(54 ，38，96，23，15，72，60，45，83) 进行直接插入排序时，当把第 8 个记录 45 插入到有序表
46、时，为寻找插入位置需比较次。2. 对于关键字序列（12，13，11， 18，60，15，7，20，25，100） ，用筛选法建堆，必须从键值为的关键字开始。3. 对 n 个记录的表 r1.n进行简单选择排序，所需进行的关键字间的比较次数为4. 在插入和选择排序中，若初始数据基本正序，则选用；若初始数据基本反序则选用。 插入排序选择排序5. 对 n 个元素的序列进行起泡排序时，最少的比较次数是。6. 排序不需要进行记录关键字间的比较。1.5 2.60 3.n(n-1)/24.5.n-16.基数综合题1.已知序列4938，65，97，76，13，27，请给出采用起泡排序对该序列作升序排列的每一趟的
47、结果。2. 已知序列 503 ，87，512，61，908，170，897，275，653，462 ，采用快速排序法对该序列作升序排序时的每一趟的结果。3. 已知序列 265，301，751，129，937，863， 742，694，076，438，采用基数排序法对该序列作升序排序时的每一趟的结果。4. 已知序列 503 ， 17，512， 908， 170，897，275，653，426，154，509，612，677，765，703，94 ，请给出采用希尔排序法(d1=8) 对该序列作升序排序时的每一趟的结果。5. 已知序列 35，89，61， 135，78，29，50 ，请给出采用插入排
48、序法对该序列作升序排序时的每一趟的结果。6. 已知序列 11 ，18，4，3，6，15，1，9，18，8 ，请给出采用归并排序法对该序列作升序排序时的每一趟的结果。1.解：根据起泡排序法的基本思想，比较无序区中相邻关键字。按照大小关系调整其位置，本题的解法是，通过比较已知序列中相邻关键字，并根据需要调整其位置、重复此过程直到没有关键字的位置交换为止，结果正好是关键字的升序排列。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 30 页，共 32 页学而不思则惘，思而不学则殆依题意，采用起泡排序法排序的各趟的结果如下：初始： 49，38、65，97，7
49、6， 13，27 第一趟； 38， 49，65，76，13，27，97 第二趟： 38， 49，65，13，27，76，97 第二趟： 38， 4913，27，65，76，97 第四趟： 38， 13，27，49，65，76，97 第五趟： 13， 27，38，49，6576，97 第六趟： 13， 27，38，49，65，76，97 第六题无元素交换，排序结束。2.依题意，采用快速排序法排序的各趟的结果如下：初始： 503，87，512，61，908，170，897，275，653，462 第 1 趟： 462 ，87， 275，61，170 503 897，908，653，512 第 2
50、趟： 170 ，87， 275，61 462 ， 503 897 ，908，653，512 第 3 趟： 61 ，87 170 275 462， 503 897 ，908，653，512 第 4 趟： 61 87 170 275 462，503 897 ，908， 653，512 第 5 趟： 61，87，170 275 462，503 897 ，908， 653，512 第 6 趟： 61，87，170，275，462，503 897 ，908， 653，512 第 7 趟： 61，87，170，275，462，503 512 ，653 897 908 第 8 趟： 61，87，170，27
51、5，462，503，512 653 897 908 第 9 趟： 61，87，170，275，462，503，512，653， 897 908 第 10 趟： 61，87，170，275，462， 503，512，653，897，908 3.依题意，采用基数排序法排序的各趟的结果如下：初始态： 265 301 751 129 937 863 742 694 076 438 第一趟： 301 751 742 863 694 265 076 937 438 129 第二趟： 301 129 937 438 742 751 863 265 076 694 第三趟： 075 129 265 301 4
52、38 694 742 751 863 937 4.依题意，采用希尔排序法排序的各趟的结果如下：初始： 503，17，512，908，170，897，275， 653，426，154，509，612，677，765，703，94 第 1 趟 (d1=8) ：426，17，509，612，170，765，275，94，503，154，512，908，677，897，703，653 第 2 趟 (d2=4) ：170，17，275，94，426，154，509，612，503，765，512，653，677，897，703，908 第 3 趟 (d3=2) ：170，17，275，94，426，15
53、4，503，612，509，653，512，765，677，897，703，908 第 4 趟 (d1=1) ：17，94，154，170，275，426，503，509，512，612，653，677，703，765，897，908 5.依题意，采用直接插入排序法排序的各趟的结果如下初始： (35)89，61， 135，78，29，50 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 31 页，共 32 页学而不思则惘，思而不学则殆第一趟：（35，89，)6l，135， 78，29，50 第二趟： (35，61，89，)135，78，29，50
54、第三趟： (35，6l，89，135)78， 29，50 第四趟： (35，61，78，89，135)29，50 第五趟： (29，35，61，78，89135)50 第六趟： (29，35，50，61，78，89，135) 6.依题意，采用归并排序法排序的各趟的结果如下：初始： 11，18，4，3，6，15，1，9， 18，8 第 1 趟： 11 ，18 3，4 6，15 1，9 8，18 第 2 趟： 3 ，4，11，18 1，6，9，15 8，18 第 3 趟： 3 ，4，11，18 1，6，8，9，15，18 第 4 趟： 1 ，3，4， 6，8，9，11，12，18， 18 第 4 趟归并完毕，则排序结束。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 32 页，共 32 页
