数据结构习题

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

1、绪论选择题1.算法的计算量的大小称为计算的（算法的计算量的大小称为计算的（）。）。A效率效率 B.复杂性复杂性 C.现实性现实性 D.难度难度2.下面关于算法说法错误的是（下面关于算法说法错误的是（）A算法最终必须由计算机程序实现算法最终必须由计算机程序实现B.为解决某问题的算法同为该问题编写的程序含义是相同的为解决某问题的算法同为该问题编写的程序含义是相同的C.算法的确定性是指指令不能有二义性算法的确定性是指指令不能有二义性 D.以上几个都是错误的以上几个都是错误的BD选择题3从逻辑上可以把数据结构分为（从逻辑上可以把数据结构分为（）两大类。）两大类。A动态结构、静态结构动态结构、静态结构

2、B顺序结构、链式结构顺序结构、链式结构 C线性结构、非线性结构线性结构、非线性结构 D初等结构、构造型结构初等结构、构造型结构4在下面的程序段中，对在下面的程序段中，对x的赋值语句的频度为（的赋值语句的频度为（）FOR i:=1 TO n DO FOR j:=1 TO n DO x:=x+1;A O(2n)BO(n)CO(n2)DO(log2n)CC判断题1.数据元素是数据的最小单位。数据元素是数据的最小单位。()2.数据的逻辑结构是指数据的各数据项之间的逻辑关系；数据的逻辑结构是指数据的各数据项之间的逻辑关系；()3算法的优劣与算法描述语言无关，但与所用计算机有关。算法的优劣与算法描述语言无

3、关，但与所用计算机有关。()4数据的物理结构是指数据在计算机内的实际存储形式。数据的物理结构是指数据在计算机内的实际存储形式。()5.数据结构的抽象操作的定义与具体实现有关。数据结构的抽象操作的定义与具体实现有关。()填空题1数据的物理结构包括数据的物理结构包括 的表示和的表示和 的表示。的表示。2数据的逻辑结构是指数据的逻辑结构是指 。3抽象数据类型的定义仅取决于它的一组抽象数据类型的定义仅取决于它的一组_（1）_，而与，而与_（2）_无关，即不论其内部结构如何变化，只要它的无关，即不论其内部结构如何变化，只要它的_（3）_不变，都不影响其外部使用。不变，都不影响其外部使用。4数据结构中评价

4、算法的两个重要指标是数据结构中评价算法的两个重要指标是_ _1数据元素数据元素 数据元素间关系数据元素间关系 2数据的组织形式，即数据元素之间逻辑关系的总体。而逻辑数据的组织形式，即数据元素之间逻辑关系的总体。而逻辑关系是指数据元素之间的关联方式或称关系是指数据元素之间的关联方式或称“邻接关系邻接关系”。3（1）逻辑特性）逻辑特性 （2）在计算机内部如何表示和实现）在计算机内部如何表示和实现 （3）数学特性。数学特性。4算法的时间复杂度和空间复杂度。算法的时间复杂度和空间复杂度。线性结构一一.选择选择1若某表最常用的操作是在最后一个结点之后插入一若某表最常用的操作是在最后一个结点之后插入一个结

5、点或删除最后一个结点。则采用（个结点或删除最后一个结点。则采用（）存储方式最）存储方式最节省运算时间。节省运算时间。A单链表单链表 B双链表双链表 C单循环链表单循环链表 D带头结点的双循环链表带头结点的双循环链表2.一个栈的输入序列为一个栈的输入序列为123n，若输出序列的第一个，若输出序列的第一个元素是元素是n，输出第，输出第i（1=i=n）个元素是（）个元素是（）。）。A.不确定不确定 B.n-i+1 C.i D.n-i3.若一个栈的输入序列为若一个栈的输入序列为1,2,3,n，输出序列的第一，输出序列的第一个元素是个元素是i，则第，则第j个输出元素是（个输出元素是（）。）。A.i-j-

6、1 B.i-j C.j-i+1 D.不确定的不确定的DBD一一.选择选择4下面关于串的的叙述中，哪一个是不正确的？（下面关于串的的叙述中，哪一个是不正确的？（）A串是字符的有限序列串是字符的有限序列 B空串是由空格构成的串空串是由空格构成的串 C模式匹配是串的一种重要运算模式匹配是串的一种重要运算 D串既可以采用顺序存储，也可以采用链式存储串既可以采用顺序存储，也可以采用链式存储5.设有一个设有一个10阶的对称矩阵阶的对称矩阵A，采用压缩存储方式，以，采用压缩存储方式，以行序为主存储，行序为主存储，a11为第一元素，其存储地址为为第一元素，其存储地址为1，每，每个元素占一个地址空间，则个元素占

7、一个地址空间，则a85的地址为（的地址为（）。）。A.13 B.33 C.18 D.40 BB一一.选择选择6.对稀疏矩阵进行压缩存储目的是（对稀疏矩阵进行压缩存储目的是（）。）。A便于进行矩阵运算便于进行矩阵运算 B便于输入和输出便于输入和输出 C节省存储空间节省存储空间 D降低运算的时间复杂度降低运算的时间复杂度7.已知广义表已知广义表LS(a,b,c),(d,e,f),运用运用head和和tail函函数取出数取出LS中原子中原子e的运算是的运算是()。A.head(tail(LS)B.tail(head(LS)C.head(tail(head(tail(LS)D.head(tail(ta

8、il(head(LS)CC二二.应用应用1 1、在下面的程序段中，对、在下面的程序段中，对x x的赋值语句的频的赋值语句的频度为多少？（表示为度为多少？（表示为n n的函数）的函数）for(i=1;in;i+)for(i=1;in;i+)for(j=1;ji;j+)for(j=1;ji;j+)for(k=1;kj;k+)for(k=1;k1;i-i=n;i1;i-）x=x+1 x=x+1；语句语句11 for(j=n;ji;j-)for(j=n;ji;j-)y=y+1;y=y+1;语句语句22 请回答语句请回答语句1 1、语句、语句2 2的执行的频度分别为多的执行的频度分别为多少？（表示为少？

9、（表示为n n的函数）的函数）n n23 3、（1 1）若长度为）若长度为n n的线性表采用顺序存储结构，的线性表采用顺序存储结构，访问结点和增加、删除结点的时间复杂度为访问结点和增加、删除结点的时间复杂度为多少？多少？（2 2）若线性表（）若线性表（a1,a2,ana1,a2,an）以链接方）以链接方式存储时，访问第式存储时，访问第i i位置元素的时间复杂度位置元素的时间复杂度为多少？（为多少？（1in1in）O(1),O(n),O(n)O(n)4 4、线性表中数据元素（表元）的存储方式、线性表中数据元素（表元）的存储方式有顺序和链式两种，其中链式存储又分为：有顺序和链式两种，其中链式存储又

10、分为：单向链表、单向循环链表、双向链表、双向单向链表、单向循环链表、双向链表、双向循环链表。以下是对同一线性表的不同存储，循环链表。以下是对同一线性表的不同存储，请分析下列各存储表使用的是何种存储方式？请分析下列各存储表使用的是何种存储方式？（注：表左的（注：表左的s s指向起始记录，编号为指向起始记录，编号为0 0的记的记录为空记录。）录为空记录。）ss表元编号表元编号 货号货号数量数量表元间联系表元间联系 1 1 618 618 40 40 2 2 2 2 205 205 2 2 3 3 3 3 103 103 15 15 4 4 4 4 501 501 20 20 5 5 5 5 781

11、 781 17 17 6 6 6 6 910 910 24 24 0 0表表1：顺序存储方式：顺序存储方式ss表元编号表元编号货号货号数量数量表元间联系表元间联系 1 1 618 618 40 40 5 5 2 2 205 205 2 2 1 1 3 3 103 103 15 15 4 4 4 4 501 501 20 20 2 2 5 5 781 781 17 17 6 6 6 6 910 910 24 24 3 3表表2：单向循环链表存储方式：单向循环链表存储方式 ss表元编号表元编号 货号货号数量数量表元间联系表元间联系 1 1 618 618 40 40 5 5 2 2 205 205

12、 2 2 0 0 3 3 103 103 15 15 4 4 4 4 501 501 20 20 2 2 5 5 781 781 17 17 6 6 6 6 910 910 24 24 3 3表表3：单向链表：单向链表 ss表元编号表元编号 货号货号数量数量表元间联系表元间联系1 1 2 2 1 1 618 618 40 40 5 5 2 2 2 2 205 205 2 2 1 1 4 4 3 3 103 103 15 15 4 4 6 6 4 4 501 501 20 20 2 2 3 3 5 5 781 781 17 17 6 6 1 1 6 6 910 910 24 24 3 3 5 5

13、表表4：双向循环链表：双向循环链表 5、完善算法：、完善算法：已知单链表结点类型为：已知单链表结点类型为：typedef struct ListNode int data;ListNode *next;ListNode;函数函数create建立以建立以head为为头指针的单链表。头指针的单链表。void create(1)ListNode*p,*q；int k；head=(ListNode*)malloc(sizeof(ListNode);q=head；scanf(“%d”,&k)；WHILE(k0)(2);(3);(4);(5);scanf(“%d”,&k)；q-next=NULL;(1)L

14、istNode*head (2)p=(ListNode*)malloc(sizeof(ListNode)(3)p-data=k (4)q-next=p (5)q=p 6、有、有5 个元素，其入栈次序为：个元素，其入栈次序为：A，B，C，D，E，在各种可能的出栈次序中，以元素，在各种可能的出栈次序中，以元素C，D最先出栈（即最先出栈（即C第一个且第一个且D第二个出栈）第二个出栈）的次序有哪几个？的次序有哪几个？三个：三个：CDEBA，CDBEA，CDBAE 7、（、（1）单向循环链表中有一个指向后继的）单向循环链表中有一个指向后继的指针域指针域next,在一个以在一个以 h 为头的单循环链表中，

15、为头的单循环链表中，p 指针指向表尾的条件是什么？指针指向表尾的条件是什么？（2）双向链表中有两个指针域，）双向链表中有两个指针域，llink和和rlink，分别指向前驱及后继，设分别指向前驱及后继，设p指向链表中的一个指向链表中的一个结点，结点，q指向一待插入结点，现要求在指向一待插入结点，现要求在p前插前插入入q，则正确的插入算法是什么？，则正确的插入算法是什么？（3）在双向链表存储结构中，删除）在双向链表存储结构中，删除p所指的所指的结点的算法是什么？结点的算法是什么？(1)p-next=h (2)p-llink-rlink=q;q-rlink=p;q-llink=p-llink;p-l

16、link=q;(3)p-llink-rlink=p-rlink p-rlink-llink=p-llink;8、下面是一个求两个集合、下面是一个求两个集合A和和B之差之差C=A-B的程序，的程序，即当且仅当即当且仅当e是是A的一个元素，但不是的一个元素，但不是B中的一个元中的一个元素时，素时，e才是才是C中的一个元素。集合用有序链表实现，中的一个元素。集合用有序链表实现，初始时，初始时，A，B集合中的元素按递增排列，集合中的元素按递增排列，C为空；为空；操作完成后操作完成后A，B保持不变，保持不变，C中元素按递增排列。中元素按递增排列。下面的函数下面的函数append(last,e)是把值为是

17、把值为e的新结点链接的新结点链接在由指针在由指针last指向的结点的后面，并返回新结点的指向的结点的后面，并返回新结点的地址；函数地址；函数difference(A,B)实现集合运算实现集合运算A-B，并，并返回表示结果集合返回表示结果集合C的链表的首结点的地址。在执的链表的首结点的地址。在执行行A-B运算之前，用于表示结果集合的链表首先增运算之前，用于表示结果集合的链表首先增加一个附加的表头结点，以便新结点的添加，当加一个附加的表头结点，以便新结点的添加，当A-B运算执行完毕，再删除并释放表示结果集合的链运算执行完毕，再删除并释放表示结果集合的链表的表头结点。表的表头结点。typedef s

18、truct node int element;struct node*link;NODE;NODE *A，*B，*C;NODE *append(NODE*last,int e)last-link=(NODE*)malloc(sizeof(NODE);last-link-element=e;return(last-link);NODE*difference(NODE*A,NODE*B)NODE*C,*last;C=last=(NODE*)malloc(sizeof(NODE);while(1)_ if(A-elementelement)last=append(last,A-element);A=

19、A-link;else if(2)_ A=A-link;B=B-link;ELSE (3)_;while(4)_ last=append(last,A-element);A=A-link;(5)_;last=C;C=C-link;free(last);return(C);/*call form:C=difference(A,B);*/(1)(A!=null&B!=null)两均未空时循环两均未空时循环(2)A-element=B-element 两表中相等元素不作结果两表中相等元素不作结果元素元素(3)B=B-link 向后移动向后移动B表指针表指针(4)A!=null 将将A 表剩余部分放入

20、结果表中表剩余部分放入结果表中(5)last-link=null 置链表尾置链表尾树型结构1若一棵二叉树具有若一棵二叉树具有10个度为个度为2的结点，的结点，5个度为个度为1的结点，则的结点，则度为度为0的结点个数是（的结点个数是（）A9 B11 C15 D不确定不确定2.有有n个叶子的哈夫曼树的结点总数为（个叶子的哈夫曼树的结点总数为（）。）。A不确定不确定 B2n C2n+1 D2n-13一棵非空的二叉树的先序遍历序列与后序遍历序列正好相一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足（反，则该二叉树一定满足（）A所有的结点均无左孩子所有的结点均无左孩子B所有的结点

21、均无右孩子所有的结点均无右孩子C只有一个叶子结点只有一个叶子结点D是任意一棵二叉树是任意一棵二叉树BCD选择题选择题4在二叉树结点的先序序列，中序序列和后序序列中，所有在二叉树结点的先序序列，中序序列和后序序列中，所有叶子结点的先后顺序（叶子结点的先后顺序（）A都不相同都不相同B完全相同完全相同 C先序和中序相同，而与后序不同先序和中序相同，而与后序不同 D中序和后序相同，而与先序不同中序和后序相同，而与先序不同5.引入二叉线索树的目的是（引入二叉线索树的目的是（）A加快查找结点的前驱或后继的速度加快查找结点的前驱或后继的速度 B为了能在二叉树中方便的进行插入与删除为了能在二叉树中方便的进行插

22、入与删除C为了能方便的找到双亲为了能方便的找到双亲 D使二叉树的遍历结果唯一使二叉树的遍历结果唯一 BA6.由由3 个结点可以构造出多少种不同的有向树？（个结点可以构造出多少种不同的有向树？（）A2 B3 C4 D5 7.一棵有一棵有n个结点的二叉树，按层次从上到下，同一层从左到个结点的二叉树，按层次从上到下，同一层从左到右顺序存储在一维数组右顺序存储在一维数组A1.n中，则二叉树中第中，则二叉树中第i个结点（个结点（i从从1开始用上述方法编号）的右孩子在数组开始用上述方法编号）的右孩子在数组A中的位置是（中的位置是（）AA2i(2i=n)BA2i+1(2i+1lchild;bt-lchild

23、=bt-rchild;bt-rchild=q;exchangeLR(bt-lchild);exchangeLR(bt-rchild);图结构选择题选择题1 1图中有关路径的定义是（图中有关路径的定义是（）。）。A A由顶点和相邻顶点序偶构成的边所形成的序列由顶点和相邻顶点序偶构成的边所形成的序列B B由不同顶点所形成的序列由不同顶点所形成的序列C C由不同边所形成的序列由不同边所形成的序列 D D上述定义都不是上述定义都不是2 2要连通具有要连通具有n n个顶点的有向图，至少需要（个顶点的有向图，至少需要（）条边。）条边。A An-1 Bn-1 Bn Cn Cn+1 Dn+1 D2n2n3 3

24、在一个无向图中，所有顶点的度数之和等于所有边数在一个无向图中，所有顶点的度数之和等于所有边数（）倍，在一个有向图中，所有顶点的入度之和等于）倍，在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（所有顶点出度之和的（）倍。）倍。A A1/2 B1/2 B2 C2 C1 D1 D4 4ABBC4 4下列哪一种图的邻接矩阵是对称矩阵？（下列哪一种图的邻接矩阵是对称矩阵？（）A A有向图有向图 B B无向图无向图 C CAOVAOV网网 D DAOEAOE网网5.5.下列说法不正确的是（下列说法不正确的是（）。）。A A图的遍历是从给定的源点出发每一个顶点仅被访问一次图的遍历是从给定的源点出发

25、每一个顶点仅被访问一次 B B遍历的基本算法有两种：深度遍历和广度遍历遍历的基本算法有两种：深度遍历和广度遍历C C图的深度遍历不适用于有向图图的深度遍历不适用于有向图D D图的深度遍历是一个递归过程图的深度遍历是一个递归过程6.6.关键路径是事件结点网络中（关键路径是事件结点网络中（）。）。A A从源点到汇点的最长路径从源点到汇点的最长路径 B B从源点到汇点的最短路径从源点到汇点的最短路径C C最长回路最长回路 D D最短回路最短回路 BCA填空题填空题1.1.判断一个无向图是一棵树的条件是判断一个无向图是一棵树的条件是_。2 2一个连通图的一个连通图的_是一个极小连通子图。是一个极小连通

26、子图。3.3.遍历图的过程实质上是遍历图的过程实质上是_，breath-first searchbreath-first search遍遍历图的时间复杂度历图的时间复杂度_；depth-first searchdepth-first search遍历图的时遍历图的时间复杂度间复杂度_，两者不同之处在于，两者不同之处在于_，反映在数据结，反映在数据结构上的差别是构上的差别是_。有有n n个顶点，个顶点，n-1n-1条边的无向连通图条边的无向连通图生成树生成树(1)(1)查找顶点的邻接点的过程查找顶点的邻接点的过程 (2)O(n+e)(3)O(n+e)(2)O(n+e)(3)O(n+e)(4)(4

27、)访问顶点的顺序不同访问顶点的顺序不同 (5)(5)队列和栈队列和栈填空题填空题4.Prim4.Prim（普里姆）算法适用于求（普里姆）算法适用于求_的网的最小生成树；的网的最小生成树；kruskalkruskal（克鲁斯卡尔）算法适用于求（克鲁斯卡尔）算法适用于求_的网的最小生的网的最小生成树成树5.Dijkstra5.Dijkstra最短路径算法从源点到其余各顶点的最短路径最短路径算法从源点到其余各顶点的最短路径的路径长度按的路径长度按_次序依次产生，该算法弧上的权出现次序依次产生，该算法弧上的权出现_情况时，不能正确产生最短路径。情况时，不能正确产生最短路径。边稠密边稠密 边稀疏边稀疏递

28、增递增 负值负值1.对有向图写出每个顶点入度与出度；邻接矩阵 邻接表123654邻接矩阵邻接矩阵0 0 0 0 1 01 0 0 0 0 00 1 0 0 0 10 0 1 0 1 00 0 0 0 0 00 1 0 0 1 0邻接表邻接表 5adjvex next12341342vexdata firstarc55 5 1 2 6 3 5 266逆邻接表逆邻接表 2adjvex next1342vexdata firstarc5 6 3 4 6 1 4 361234561/12/11/20/23/01/2入度出度2 从顶点4出发，画出一棵深度优先生成树和广度优先生成树132465872321

29、22412317241233225227283614123322522728361深度优先生成树深度优先生成树1324658723212241231724122252272316482广度优先生成树广度优先生成树41432225227282612 从顶点4出发，画出一棵深度优先生成树和广度优先生成树3 写出执行构造最小生成树Prim算法后的最小生成树1324658722141211324658723212241231724 用Dijkstra算法求从顶点V1到其它各顶点的最短路径。13246510215304201015610终点 从V1到各终点的最短路径及其长度V2V3V4V5V6Vj201

30、5V3:1520-25V2:20-3025V6:25-2930-V4:29-30-V5:305.求关键路径，完成工程最短时间V1V2V3V4V5V6V7顶点 Ve Vla1a2a3a4a5a6a7a8a9a10a11活动 e l l-e000880016161616016193161821919019190202002525001010642531718286683352a1a2a3a4a5a6a7a8a9a10a1164253186813752a1a2a5a8a9a10a11081619202527272520191680完成工程最短时间27天查找、排序选择题选择题1.1.若查找每个记录的概

31、率均等，则在具有若查找每个记录的概率均等，则在具有n n个记录的连续顺序个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度文件中采用顺序查找法查找一个记录，其平均查找长度ASLASL为为()()。A A (n-1)/2 B.n/2 (n-1)/2 B.n/2 C.(n+1)/2 D.nC.(n+1)/2 D.n2.2.下面关于二分查找的叙述正确的是下面关于二分查找的叙述正确的是 ()()A.A.表必须有序，表可以顺序方式存储，也可以链表方式存储表必须有序，表可以顺序方式存储，也可以链表方式存储 B.B.表必须有序且表中数据必须是整型，实型或字符型表必须有序且表中数据必须是整型，实

32、型或字符型 C.C.表必须有序，而且只能从小到大排列表必须有序，而且只能从小到大排列D.D.表必须有序，且表只能以顺序方式存储表必须有序，且表只能以顺序方式存储CD 选择题选择题CD 3.3.既希望较快的查找又便于线性表动态变化的查找方法既希望较快的查找又便于线性表动态变化的查找方法是是 ()()A A顺序查找顺序查找 B.B.折半查找折半查找 C.C.索引顺序查找索引顺序查找 D.D.哈希法查找哈希法查找4.4.设哈希表长为设哈希表长为1414，哈希函数是，哈希函数是H(key)=key%11,H(key)=key%11,表中已表中已有数据的关键字为有数据的关键字为1515，3838，616

33、1，8484共四个，现要将关键共四个，现要将关键字为字为4949的结点加到表中，用二次探测再散列法解决冲突，的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是则放入的位置是()()A A8 B8 B3 3 C C5 D5 D9 9 选择题选择题DA 5 5某内排序方法的稳定性是指某内排序方法的稳定性是指()()。A A该排序算法不允许有相同的关键字记录该排序算法不允许有相同的关键字记录B B该排序算法允许有相同的关键字记录该排序算法允许有相同的关键字记录C C平均时间为平均时间为0 0（n log nn log n）的排序方法）的排序方法D D以上都不对以上都不对6 6下面给出的四种排

34、序方法中，排序过程中的比较次数下面给出的四种排序方法中，排序过程中的比较次数与排序方法无关的是。与排序方法无关的是。()()A A选择排序法选择排序法 B.B.插入排序法插入排序法 C.C.快速排序法快速排序法 D.D.堆积排序法堆积排序法 填空题填空题1.1.在顺序表（在顺序表（8,11,15,19,25,26,30,33,42,48,508,11,15,19,25,26,30,33,42,48,50）中，用）中，用二分（折半）法查找关键码值二分（折半）法查找关键码值2020，需做的关键码比较次数，需做的关键码比较次数为为_._.2.2.哈希表是通过将查找码按选定的哈希表是通过将查找码按选定

35、的_ _(1)_(1)_和和 _ _(2)_(2)_，把，把结点按查找码转换为地址进行存储的线性表。哈希方法的结点按查找码转换为地址进行存储的线性表。哈希方法的关键是关键是_(3)_(3)_ _和和 _ _(4)_(4)_ _。一个好的哈希函数其转换地址。一个好的哈希函数其转换地址应尽可能应尽可能_ _(5)_(5)_ _，而且函数运算应尽可能，而且函数运算应尽可能_(6)_(6)_ _。4 4(1)(1)哈希函数哈希函数(2)(2)解决冲突的方法解决冲突的方法 (3)(3)选择好的哈希函数选择好的哈希函数 (4)(4)处理冲突的方法处理冲突的方法 (5)(5)均匀均匀(6)(6)简单简单填空

36、题填空题3.3.平衡二叉树又称平衡二叉树又称_，其定义是，其定义是_。4.4.动态查找表和静态查找表的重要区别在于前者包含有动态查找表和静态查找表的重要区别在于前者包含有_和和_运算，而后者不包含这两种运算运算，而后者不包含这两种运算AVLAVL树（高度平衡树，高度平衡的二叉排序树），树（高度平衡树，高度平衡的二叉排序树），或为空二叉树，或二叉树中任意结点左子树高度与或为空二叉树，或二叉树中任意结点左子树高度与右子树高度差的绝对值小于等于右子树高度差的绝对值小于等于1 1。插入插入 删除删除 设哈希函数H（k）=3K mod 11，哈希表的大小为11(0.10)，对关键字序列（32,13,49

37、,24,38,21,4,12）按下述两种解决冲突的方法构造哈希表：（1）线性探测再散列；（2）链地址法；（3）分别求出等概率下查找成功时的平均查找长度ASL线性和ASL链地址。哈希地址哈希地址0 01 12 23 34 45 56 67 78 89 91010关键字关键字4 41212494938381313242432322121比较次数比较次数1 11 11 12 21 12 21 12 2ASL线性线性=（1+1+1+2+1+2+1+2）/8 =11/8ASL链地址链地址=（51+32）/8=11/8 一棵二叉排序树结构如下,各结点的值从小到大依次为1-9，请标出各结点的值。519423

38、678 依次输入表(30,15,28,20,24,10,12,68,35,50,46,55)中的元素，生成一棵二叉排序树(1)试画出生成二叉排序树的全过程;(2)对该二叉排序树作中序遍历，试写出遍历序列;(3)假定每个元素的查找概率相等，试计算该二叉排序树的平均查找长度。301528202410126835504655（2）对该二叉排序树作中序遍历，）对该二叉排序树作中序遍历，遍历序列为：遍历序列为：10，12，15，20，24，28，30，35，46，50，55，68（3）假定每个元素的查找概率相等，）假定每个元素的查找概率相等，该二叉排序树的平均查找长度为：该二叉排序树的平均查找长度为：A

39、SL=（1+2*2+3*3+4*3+5*3）/12 =41/12 设记录的关键字集合K=49、38、65、97、76、13、27、48、55、4，给定的增量序列D=5，3，1，请写出对K按“希尔排序”排序时各趟排序的分组情况和结束时的结果。取取d1=5一趟排序：一趟排序：13 27 48 55 4 49 38 65 97 76取取d2=3二趟排序：二趟排序：13 4 48 38 27 49 55 65 97 76取取d3=1三趟排序：三趟排序：4 13 27 38 48 49 55 65 76 97复习(了解)1.绪论：数据结构、算法 2.线性表：类型特点；顺序存储；链式存储（单链表、循环链表

40、、双向链表）3.栈和队列：特点和应用(了解)4.串：表示和实现，模式匹配(了解)5.数组和广义表：顺序表示；矩阵压缩存储；广义表存储结构复习 6.树和二叉树：类型定义、二叉树特点；遍历；树、二叉树、森林转换；赫夫曼树 7.图：定义、存储；遍历、最小生成树、拓扑排序、关键路径、最短路径 9.查找：静态查找表（顺序、折半）；二叉排序树（查找、插入、删除）；哈希表 10.排序：插入(直接、折半、希尔)；快速(冒泡、快速)；选择(简单、堆)考试题型 一、填空题。（每空一、填空题。（每空1分，共分，共10分）分）二、简答题（每题二、简答题（每题10分，共分，共30分）分）三、综合应用题（每题三、综合应用题（每题15分，共分，共60分）分）