数据结构知识点归纳.docx

《数据结构知识点归纳.docx》由会员分享，可在线阅读，更多相关《数据结构知识点归纳.docx（22页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精品名师归纳总结资料word 精心总结归纳 - - - - - - - - - - - -名师精编优秀资料一、数据结构的章节结构及重点构成数据结构学科的章节划分基本上为:概论，线性表，栈和队列，串，多维数组和广义表，树和二叉树，图，查找，内排，外排，文件，动态储备安排。对于绝大多数的学校而言，“外排，文件，动态储备安排”三章基本上是不考的，在大多数高校的运算机本科教学过程中，这三章也是基本上不作讲授的。数据结构的章节比重大致为：1. 概论:概念，时间复杂度。2. 线性表 : 基础章节，必考内容之一。概念，算法设计题。3. 栈和队列 : 基本概念。4. 串 :基本概念。5. 多维数组及广义表:基

2、本概念。6. 树和二叉树: 重点难点章节，各校必考章节。概念，问答，算法设计题。7. 图: 重点难点章节，各校必考章节。概念，问答，算法设计题。8. 查找 : 重点难点章节，概念，问答。9. 排序 : 重点难点章节，问答各种排序算法的排序过程二、各章节的主要内容：第一章概述主要内容：本章主要起到总领作用，为读者进行数据结构的学习进行了一些先期铺垫。大家主要留意以下几点:（ 1）数据结构的基本概念。（数据。数据元素。数据项。数据结构。数据的规律结构：线性和非线性，详细分为集合、线性结构、树形结构和图状结构。数据的储备结构： 次序储备和链式储备。运算）（ 2）算法的度量：时间效率和空间效率，分别用

3、时间复杂度和空间复杂度度量，把握时间复杂度的度量方法量方法。 （大 O 表示法）参考题目：填空题：1、数据结构是相互之间存在一种或多种特定关系的数据元素的集合，它包括三方面的内容，分别是数据的规律结构、 （）和（）。2、数据结构按规律结构可分为两大类，它们分别是（） 和（）3. 数据的物理结构主要包括（）和（）两种情形。4线性表，栈，队列和二叉树四种数据结构中（）是非线性结构， （）是线性结构。5、线性结构中元素之间存在（）关系，树形结构中元素之间存在（）关系，图形结构中元素之间存在（）关系。6、程序段的时间复杂度是 。fori=1;i=n;i+ k+;forj=1;j=n;j+可编辑资料 -

4、 - - 欢迎下载精品名师归纳总结学习资料 名师精选 - - - - - - - - - -第 1 页，共 11 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结资料word 精心总结归纳 - - - - - - - - - - - -名师精编优秀资料x=x+k;7以下算法的时间复杂度是 。fori=0;im;i+ + forj=0;jn;j+ +aij=i。8以下算法的时间复杂度是 。i=s=0;whiles next = NULL。C head - next = head。D head . = NULL。5、在一个单链表中，如P 所指结点不是最终结

5、点，在P 之后插入S所指结点，就执行（）A S-next=P-next;P-next=SB P-next=S-next;S-next=P。 CP-next=P;P-next=S。D P-next=S;S-next=P。可编辑资料 - - - 欢迎下载精品名师归纳总结学习资料 名师精选 - - - - - - - - - -第 2 页，共 11 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结资料word 精心总结归纳 - - - - - - - - - - - -名师精编优秀资料6、在已知头指针的单链表中，要在其尾部插入一新结点，其算法所需的时间复杂度

6、为（）2A（ 1）B（ log2n）C O（ n）D O（ n7、在一个单链表中，已知q 所指结点是p 所指结点的直接前趋，如在p， q 之间插入s 结点，就执行的操作是（）。A s-next=p-next;p-next=s;B q-next=s;s-next=p; Cp-next=s-next;s-next=p;D p-next=s;s-next=q;8、设次序线性表中有n 个数据元素， 就第 i 个位置上插入一个数据元素需要移动表中（）个数据元素，删除第i 个元素（ 1i n）时，需向前移动的元素的个数是（）。在次序表中插入一个元素，需要平均移动（）元素，删除一个元素，需要平均移动（）元素

7、，详细移动的元素个数与（）有关，插入删除操作的时间复杂度均为。9、设单链表的结点结构为data,next ，next 为指针域，已知指针px 指向单链表中data 为 x 的结点，指针py 指向 data 为 y 的新结点, 如将结点y 插入结点x 之后，就需要执行以下语句:（）。10 设 指 针 变 量p指 向 单 链 表 中 结 点A的 前 驱 结 点 ， 如 删 除 单 链 表 中 结 点A ， 就 执 行 操 作（）三、算法设计：1. 设运算法，运算次序表中数据元素为x 的元素个数。次序表结构如下：typedef structint data100;int length;sqlist;

8、函数首部为：int countsqlist L, intx2设运算法，在次序线性表中，删除次序表中第i 个元素，次序表结构同上题。函数首部为： int delsqlist *L,int i3设运算法，在次序线性表中，删除值为x 的元素。函数首部为：void delxsqlist *L , int x4. 对给定的单链表L元素各不相同，编写一个删除L 中值为 x 的结点的算法。链式结构如下：typedef struct LinkList int data;struct LinkList *next;Node,*LinkList;int delxLinkList *head ,int x5. 编写

9、算法求带头结点的单链表的表长, 结构同上题。int countLinkList *head可编辑资料 - - - 欢迎下载精品名师归纳总结学习资料 名师精选 - - - - - - - - - -第 3 页，共 11 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结资料word 精心总结归纳 - - - - - - - - - - - -名师精编优秀资料第三章栈与队列主要内容：栈与队列，是许多学习DS 的同学遇到第一只拦路虎，许多人从这一章开头坐晕车，始终晕到现在。栈和队列一章留意以下几个方面:（ 1）栈的定义及其相关数据结构的概念：合法的出栈序列、出

10、栈序列个数、次序栈，链栈（ 2）队列的定义及其相关数据结构的概念，包括:循环队列。（ 3）栈和队列的特点：栈-后进先出。队列先进先出。（ 4）递归算法概念。栈与递归的关系，全部的递归算法都可以借助栈将递归转向于非递归算法。（ 5）操作：次序栈的进栈、出栈操作。循环队列的队空、队满条件，出队、入队、求队列元素个数操作。参考题目：1. 循环队列是空队列的条件是（）A Q . rear = = Q . frontB（ Q . rear + 1） %maxsize = = Q .frontC Q . rear = = 0D Q. front = = 02. 链栈与次序栈相比，比较明显的优点是（） A通

11、常不会显现栈满的情形B通常不会显现栈空的情形 C插入操作更加便利D删除操作更加便利3. 如一个栈的输入序列是1,2,3， n，输出序列的第一个元素是，就第个输出元素是（）A n - iB n i + 1C iD不确定4. 对于一个栈，给定输入序列为1， 2，3，就以下不行能为输出序列的是（）A 1， 2，3B 3， 2， 1C 3， 1， 2D2， 1， 35. 栈是限定在（）处进行插入或删除操作的线性表。A端点B栈底C栈顶D中间6. 当循环队列q 是满队列时， 存放队列元素的数组data 有 n 个元素， 就 data 中存放 （）个数据元素。A nB. n-1C. n-2D.07. 循环队

12、列用数组elem0 ，m-1 存放其元素值，已知其头尾指针分别是front和 rear ，就当前队列中的元素个数是 。8栈的特点是，队列的特点是。9.设栈 S 和队列 Q 的初始状态为空，元素e1,e2,e3,e4,e5,e6依次通过栈，一个元素出栈后立刻进入队列 Q，如 6 个元素出队的次序是e2,e4,e3,e6,e5,e1,就栈 S 的容量至少应当是_ 。10如用一个大小为6 的一维数组来实现循环队列，当前rear 和 front 的值分别是0 和 3，从队列中删除一个元素，再加入两个元素后，当前队列中共个元素， rear 的值为 ， front 的值为 。第四章串主要内容：最简洁自学的

13、章节之一本章留意：（ 1）串的基本概念：串（串是其元素均为字符型数据的特殊线性表），子串、空串与空格串的区分，串相等的条件、模式匹配。（ 2）串的定长次序储备（ 3）串 的基本操作功能，如求串长,串连接，串替换等，给出一个字符串能够写出操作的结果。参考题目：可编辑资料 - - - 欢迎下载精品名师归纳总结学习资料 名师精选 - - - - - - - - - -第 4 页，共 11 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结资料word 精心总结归纳 - - - - - - - - - - - -名师精编优秀资料1串是一种特殊的线性表，其特殊性表

14、达在。2S1=“ ABCD”， S2=“CD”就 S2 在 S1 中的位置是（）3假设 S=“ abcaabcaaabca”，T=“ bca”， Index S,T,3 的结果是（ 6 ）4设有 S1= ABCDEF，GS2= PQRS，T函数 conx， y返回 x 和 y 串的连接串， subsS， i， j返回串 S 的从序号 i 的字符开头的j 个字符组成的子串，lens 返回串 s 的长度，就consubsS1， 2，lenS2， subsS1， lenS2，2 的结果是。5在串中， SubString “ student ”,5,2 的结果是。可编辑资料 - - - 欢迎下载精品名

15、师归纳总结4假设 S=“ abcaabcaaabca， T”=“ bca，”V=“ x，”Replace S,T,V结 7两个串相等的充分必要条件是 且 _8. 子串的定位操作通常称为。果是。 。可编辑资料 - - - 欢迎下载精品名师归纳总结第五章数组与广义表主要内容：（ 1）多维数组中某数组元素的储备位置求解。一般是给出数组元素的首元素的址和每个元素占用的的址空间并组给出多维数组的维数，然后要求你求出该数组中的某个元素所在的位置。（ 2）明确按行储备和按列储备的区分和联系，并能够依据这两种不同的储备方式求解1 中类型的题。（ 3） 稀疏矩阵的压缩储备概念，三元组表和十字链表储备。（ 4）广

16、义表的概念，懂得广义表的递归特性，特殊应当明确表头与表尾的定义。（ 5）广义表的储备特性-难以用次序储备结构储备。能画出头尾表示法（ 6） 广义表的操作GetHead 和 GetTail，给出一个广义表能够写出取表头和取表尾操作的结果。参考题目：1. 常对数组进行的两种基本操作是。A. 建立与删除B. 索引和修改C. 对数据元素的存取和修改D. 查找与索引2. 二维数组A 中，每个元素A 的长度为3 个字节，行下标i 从 0 到 7，列下标j 从 0 到 9，从首的址SA开头连续存放在储备器内，该数组按行存放时，数组元素A74 的起始的址为 。A. SA+141B. SA+144C. SA+2

17、22D. SA+2253. 对稀疏矩阵进行压缩储备目的是 _。4已知广义表：A=a,b, B=A,A, C=a,b,A,B，就 tailheadtailC运算的结果为 。5求以下广义表操作的结果：(1) GetTailGetHeada,b,c,d= (2) GetTailGetHeadGetTaila,b,c,d = 第六章树与二叉树主要内容：从对线性结构的讨论过度到对树形结构的讨论，是数据结构课程学习的一次跃变，此次跃变完成的好坏，将直接关系到你到实际的考试中是否可以拿到高分，而这全部的一切，将最终影响你的专业课总分。所以，树这一章的重要性，已经不说自明白。总体来说，树一章的学问点包括:（

18、1）二叉树的概念、性质（性质特别重要）（ 2）二叉树的储备结构（次序储备和二叉链表储备）可编辑资料 - - - 欢迎下载精品名师归纳总结学习资料 名师精选 - - - - - - - - - -第 5 页，共 11 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结资料word 精心总结归纳 - - - - - - - - - - - -名师精编优秀资料（ 3）二叉树遍历的三种算法（给二叉树能写出遍历序列，依据遍历序列可以构造二叉树。遍历递归算法 （二叉树的其他算法许多都是在遍历的基础上得到的）、在三种基本遍历算法的基础上实现二叉树的其它算法（如求叶子结

19、点、总结点、高度等，认真揣摩求解思路）（ 4）线索二叉树的概念。 （利用二叉链表储备时的空链域指向前驱和后继，空链域个数。给出一棵二叉树能画出对应的线索二叉树，如P149图 6.16）（ 5）树、森林的概念，树与森林的遍历算法（给出树或森林，能写出其要求的遍历序列），树和森林的遍历算法与二叉树遍历算法的联系。（ 6）树与森林和二叉树的相互转换。（ 7）最优二叉树的概念，哈夫曼树的概念，特点（只有 0 和 2 的结点），能够按指定权值建立哈夫曼树，给出哈夫曼编码，运算WPL。树一章，到处是重点，道道是考题，大家务必个个过关。参考题目：1、在具有n 个结点的完全二叉树中，结点i（ i1）的父结点是

20、（）A 2iB不存在C2i+1D . i/ 2.2、以下陈述中正确的（） A二叉树是度为2 的有序树 B二叉树中结点只有一个孩子时无左右之分 C二叉树中必有度为2 的结点 D二叉树中最多只有两棵子树，并且有左右之分3、以二叉链表作为二叉树的储备结构，在具有个结点的二叉链表中n0，空链域的个数为（）A 2n - 1B n - 1C n + 1D2n + 1 4、将一棵有100 个结点的完全二叉树从上到下，从左到右依次对结点进行编号，根结点的编号为1，就编号为 49 的结点的左孩子编号为（）A 99B 98C50D 485、在一棵具有五层的满二叉树中，结点总数为（）A 31B 32C33D 166

21、深度为k 的完全二叉树中最少有（）个结点。A. 2k-1-1B. 2k-1C.2k-1+1D.2k -17、三个结点可以构成（）种不同外形的二叉树。A 2C 3D 5 8、树中全部结点的度之和等于全部结点数加（）。A 0B1C -1D 29、含有 10 个结点的二叉树中， 度为 0 的结点数为4，就度为 2 的结点数为 （），度为 1 的结点数为 （）A3B 4C 5D 610、有 m 个叶结点的哈夫曼树所具有的结点数为（）A mBm+1C2mD2m - 1填空：1如某二叉树有20 个叶子节点，有30 个节点仅有一个孩子，就该二叉树的总的节点数是。2设二叉树中度数为0 的结点数为50，度数为1

22、 的结点数为30，就该二叉树中总共有 个结点。3. 如前序遍历二叉树的结果为序列A、B、 C，就有 棵不同的二叉树可以得到这一结果。 4线索二叉树的左线索指向其，右线索指向其。5、已知完全二叉树T 的第 5 层只有 7 个结点，就该树共有个叶子结点。简答：1. 已知一棵二叉树的先序遍历序列EFHIGJK，中序遍历序列为HFIEJGK，构造该二叉树，写出后序序列。2. 已知一棵二叉树的前序序列为ABCDEFGH，中序序列为CBEDFAGH，请画出该二叉树，写出后序序列。可编辑资料 - - - 欢迎下载精品名师归纳总结学习资料 名师精选 - - - - - - - - - -第 6 页，共 11

23、页 - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结资料word 精心总结归纳 - - - - - - - - - - - -名师精编优秀资料3. 已知一棵二叉树的后序序列“cdbgfea” , 中序序列“ cbdaegf”，请画出该二叉树，写出先序序列。可编辑资料 - - - 欢迎下载精品名师归纳总结4. 依据后序序列“cedbhjigfa和”中序序列“ cbedahgijf构”建二叉树，并给出其先序序列。可编辑资料 - - - 欢迎下载精品名师归纳总结5. 假设用于通信的电文字符集为A B C D E各,运算 huffman 树的带权路径长度。字母显现

24、次数分别为2 9 5 7 6，现需求这些字母的最优编码，可编辑资料 - - - 欢迎下载精品名师归纳总结6. 假设用于通信的电文由8 个字母 a,b,c,d,e,f,g 组成，其频率分别为W= 5， 2，9，11， 8，3， 7，试构造相应的哈夫曼树，给出每个字母的haffman 编码，并运算它的带权路径长度。三、算法设计：1. 编写算法求二叉树中叶子结点的数目。数据结构定义为：typedef struct Node int data;struct Node *Lchild; struct Node *Rchild;BiTNode,*BiTree;函数首部为：int leafBiTree *r

25、oot2. 利用二叉树遍历算法求二叉树的高度，假设根结点的高度为1. int DepthBiTree *root3. 以二叉链表为储备结构写出求二叉树结点总数的算法。第六章图主要内容：假如说，从线性结构向树形结构讨论的转变，是数据结构学科对数据组织形式讨论的一次升华，那么从树形结构的讨论转到图形结构的讨论，就进一步让我们看到了数据结构对于解决实际问题的重大推动作用。图这一章的特点是:概念繁多，与离散数学中图的概念联系紧密，算法复杂，考研时极易被考到，且简洁出大题，假如不考查树与图两章的学问，几乎是不行想像的。主要学问点如下:（ 1）图的基本概念: 图的定义和特点，无向图，有向图，入度，出度，完

26、全图，生成子图，路径长度，回路，（强）连通图， （强）连通重量、生成树等概念。与这些概念相联系的相关运算题也应当把握（如：有向（无向）完全图边的条数、生成树的边的条数等）。（ 2） 图的储备形式 : 只看邻接矩阵和（逆） 邻接表（ 3） 图的两种遍历算法:深度遍历和广度遍历，能够画出任意一幅图的深度优先搜寻生成树和广度优先搜寻生成树。（ 4） 生成树、最小生成树的概念以及最小生成树的构造RIM 算法和 KRUSKAL算法。考查时，一般不要求写出算法源码，而是要求依据Prim 算法、 Kruskal算法构造该图的最小生成树，画出其构造过程及最终生成的最小生成树。以下内容考研很重要（ 5）拓扑排序

27、问题:拓扑排序有两种方法，一是无前趋的顶点优先算法，二是无后继的顶点优先算法。换句话说，一种是“从前向后”的排序，一种是“从后向前”排。当然，后一种排序出来的结果是“逆拓扑有序”的。要求按指定图，写出拓扑排序序列。（ 6）关键路径问题:这个问题是图一章的难点问题。懂得关键路径的关键有三个方面:一是何谓关键路径，二是最早时间是什么可编辑资料 - - - 欢迎下载精品名师归纳总结学习资料 名师精选 - - - - - - - - - -第 7 页，共 11 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结资料word 精心总结归纳 - - - - - -

28、- - - - - -名师精编优秀资料意思、如何求，三是最晚时间是什么意思、如何求。关键路径问题是工程进度掌握的重要方法，具有很强的有用性。要求对指定图，写出关键路径。（ 7）最短路径问题: 与关键路径问题并称为图一章的两只拦路虎。概念懂得是比较简洁的，关键是算法的懂得。 最短路径问题分为两种: 一是求从某一点动身到其余各点的最短路径。二是求图中每一对顶点之间的最短路径。这个问题也具有特别有用的背景特色，一个典型的应当就是旅行景点及旅行路线的挑选问题。解决第一个问题用DIJSKTRA算法，解决其次个问题用FLOYD算法。 留意区分。参考题目：1、在一个具有n 个结点的无向图中，要连通全部结点至

29、少需要（）A n 条边B n+1 条边C n-1 条边D n/2 条边2、最小生成树指的是（） A由连通图所得到的边数最少的生成树 B由连通图所得到的顶点相对较少的生成树 C连通图的全部生成树中权值之和最小的生成树D连通图的微小连通子图3、在一个有向图中，全部顶点的入度之和等于全部顶点的出度之和的（）A 1/2 倍B 1 倍C 2 倍D 4 倍4、有 n 个结点的无向图的边数最多为（）A n+1B n（ n-1） /2C n（ n+1）D 2n（ n+1） 5、如 n 个顶点的无向图采纳邻接矩阵储备方法，该邻接矩阵是一个（）A一般矩阵B对称矩阵C对角矩阵D稀疏矩阵6. 以下算法中， 算法用来求

30、图中每对顶点之间的最短路径。A. DijkstraB.FloyedC. PrimD.Kruskal 7、最小生成树的构造可使用（A）。A prim 算法B冒泡算法C迪杰斯特拉算法D哈夫曼算法8、有 8 个结点的有向完全图有（C）条边。A 14B28C 56D 112 9、已知有向图G=V,E ，其中 V=V1,V2,V3,V4,V5,V6,V7，E=, ,G的拓扑序列是（）。A V1,V3,V4,V6,V2,V5,V7B V 1,V 3 ,V 2,V 6,V 4,V 5,V 7CV 1,V 3 ,V 4,V 5,V 2,V 6,V 7D V 1,V 2 ,V 5,V 3,V 4,V 6,V 7

31、10设无向图G 中的边的集合E=a， b， a， e， a， c， b， e，e， d，d， f ， f， c，就从顶点a 出发进行深度优先遍历可以得到的一种顶点序列为 。11有 N 个顶点组成的无向连通图，最多可以有 条边。简答题：1.给出下图中从a 动身的深度优先遍历序列和广度优先遍历序列可编辑资料 - - - 欢迎下载精品名师归纳总结学习资料 名师精选 - - - - - - - - - -第 8 页，共 11 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结资料word 精心总结归纳 - - - - - - - - - - - -名师精编优秀资

32、料2. 求下图的最小生成树，要求分别用prim 算法和 kruskal 算法， prim 算法从定点1 动身。画出最小生成树的生成过程。1162可编辑资料 - - - 欢迎下载精品名师归纳总结216115可编辑资料 - - - 欢迎下载精品名师归纳总结1963331454643. 求下图的最小生成树，要求分别用prim 算法和 kruskal 算法， prim 算法从定点a 动身。画出最小生成树的生成过程。4. 已知图 G如下所示，列出图G的邻接表，写出拓扑排序序列（写出一种即可），求出关键路径。5. 已知图 G如下所示，列出图G的邻接表，写出拓扑排序序列（写出一种即可），求出关键路径。第七章

33、查找主要内容：在不少数据结构的教材中，是把查找与排序放入高级数据结构中的。应当说，查找和排序两章是前面我们所学的学问的综合运用，用到了树、也用到了链表等学问，对这些数据结构某一方面的运用就构成了可编辑资料 - - - 欢迎下载精品名师归纳总结学习资料 名师精选 - - - - - - - - - -第 9 页，共 11 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结资料word 精心总结归纳 - - - - - - - - - - - -名师精编优秀资料查找和排序。现实生活中，search 几乎无处不在，特殊是现在的网络时代，万事离不开search，

34、小到文档 内文字的搜寻，大到INTERNET上的搜寻， search 占据了我们上网的大部分时间。在 DS 的教材中，一般将search 分为三类 :1 在次序表上的查找。2 在树表上的查找。3 在哈希表上的查找。本次复习这一章的学问时，要把握以下内容:（ 1）关键字、主关键字、次关键字的含义。静态查找与动态查找的含义及区分。（ 2）线性表上的查找: 次序查找和二分查找及其比较次数。（ 3）基本哈希表的查找算法:参考题目：1、次序查找法适合于储备结构为的线性表。（）A散列储备B次序储备或链接储备C压缩储备D索引储备2、在查找过程中，如同时仍要做增、删工作，这种查找就称为（）A静态查找B动态查找

35、C内查找D外查找3、对线性表进行二分查找时，要求线性表必需（） A以次序方式储备B以次序方式储备且元素有序 C以链接方式储备D以链接方式储备且元素有序4、在有序表 12,24,36,48,60,72,84 中二分查找关键字72 时所需进行的关键字比较次数为。5、折半查找有序表（4,6,12,20,28,38,50,70,88,100 ），如查找表中元素20，它将依次与表中元素比较大小。简答题：1、已知散列函数为H（ k） =k mod 13 ，关键值序列为（19， 01， 23，14， 55， 20，84，27，68，11， 10，77）处理冲突的方法为线性探测法，散列表长度为13（ 1）构造

36、哈希表（画示意图）。（ 2）运算装填因子。（ 3）运算查找胜利情形下的平均查找长度。2. 采纳哈希函数k=3*k mod 13 并用线性探测开放的址法处理冲突，在数列的址空间0.12中对关 键字序列22,15,40,46,17,13,14,28,38（ 1）构造哈希表（画示意图）。（ 2）装填因子。（ 3）等概率下胜利的平均查找长度答：哈希的址0123456789101112关 键 字 比较次数（ 2）装填因子 =（ 3） ASLsucc =3. 已知散列函数为H（k） =k mod 7 ，关键值序列为 19, 01, 23, 14, 55, 68, 11, 82, 36 ，表长为7采纳链表处

37、理冲突。（ 1）构造哈希表（画示意图）。可编辑资料 - - - 欢迎下载精品名师归纳总结学习资料 名师精选 - - - - - - - - - -第 10 页，共 11 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结资料word 精心总结归纳 - - - - - - - - - - - -名师精编优秀资料（ 2）运算查找胜利情形下的平均查找长度。4. 己知一个有序表为12,18,20,25,29,32,40,62,83,90,95,98, 当二分查找法为29 和 90 的元素时 ,分别需要多少次比较才能查找胜利.如采纳次序查找时,分别需要多少次比较才

38、能查找胜利.第八章内部排序主要内容：内排是 DS 课程中最终一个重要的章节，考查你对书本上的各种排序算法及其思想以及其优缺点和性能指标（时间复杂度）能否了如指掌。从排序算法的种类来分，本章主要阐述了以下几种排序方法:插入、挑选、交换、归并、计数等五种排序方法。本次复习这一章的学问时，要把握以下排序算法的思想:（ 1）简洁挑选排序（ 2）快速排序（用中间数将待排数据组一分为二）（ 3）冒泡排序（ 4）明白插入排序，堆排序和归并排序排序（是通过掌握每次参加排序的数的总范畴“由小到大”的增量来实现排序效率提高的目的）给出关键字序列，能够写出每趟排序过程。参考题目：1、关键字序列为 （ 7,6,8,4,3,5），采纳快速排序以第一个记录为基准得到的第一次划分结果是（）。A（ 5,3,6,4,7,8）B（ 3,5,6,4,7,8）C（ 6,4,3,5,7,8）D（ 5,6,3,4,7,8）2初始记录关键字序列为45，80，55，40，42，