《数据结构总练习题ppt课件.ppt》由会员分享，可在线阅读，更多相关《数据结构总练习题ppt课件.ppt（43页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、1.1 什么是数据结构什么是数据结构1.2 基本概念和术语基本概念和术语1.4 算法和算法分析算法和算法分析1.3 抽象数据类型的表示与实现抽象数据类型的表示与实现1. 1. 熟悉熟悉各名词、术语各名词、术语的含义，掌握基本概念。的含义，掌握基本概念。2. 2. 理解理解算法五个要素算法五个要素的确切含义。的确切含义。本章学习要点3. 3. 掌握计算掌握计算语句频度语句频度和估算和估算算法时间复杂度算法时间复杂度的方法。的方法。第第1章练习题章练习题1.数据结构是研究数据的数据结构是研究数据的( )以及它们之间的相互关系。以及它们之间的相互关系。A. 物理结构，逻辑结构物理结构，逻辑结构 B.
2、 理想结构，抽象结构理想结构，抽象结构C. 理想结构，物理结构理想结构，物理结构 D. 抽象结构，逻辑结构抽象结构，逻辑结构2.从逻辑上可以把数据结构分为（从逻辑上可以把数据结构分为（ ）两大类。）两大类。A.动态结构、静态结构动态结构、静态结构 B.顺序结构、链式结构顺序结构、链式结构C.线性结构、非线性结构线性结构、非线性结构 D.初等结构、构造型结构初等结构、构造型结构3.在发生非法操作时，算法能够做出适当处理的特性称为在发生非法操作时，算法能够做出适当处理的特性称为（ ）A.正确性正确性 B. 健壮性健壮性 C.可读性可读性 D.可移植性可移植性4.以下（以下（ ）不是算法的基本特性。
3、）不是算法的基本特性。 A.可行性可行性 B.长度有限长度有限 C.在规定的时间内完成在规定的时间内完成 D.确定性确定性ACBB 5. 算法的时间复杂度与（算法的时间复杂度与（ ）有关。）有关。A.问题规模问题规模 B.计算机硬件性能计算机硬件性能 C.编译程序质量编译程序质量 D.程序设计语言程序设计语言6.某算法的时间复杂度为某算法的时间复杂度为O（n2），表明该算法的（），表明该算法的（ ）。）。.A.问题规模是问题规模是n2 B.执行时间等于执行时间等于n2 C.执行时间与执行时间与n2成正比成正比 D.问题规模与问题规模与n2成正比成正比7.在下面的程序段中，对在下面的程序段中，对
4、x的赋值语句的频度为（的赋值语句的频度为（ ）。）。for(k=1;k=n;k+) for(j=1;jnext=h C. h-next=NULL D.h!=NULLDBDC第第2章练习题章练习题5.对于用一维数据对于用一维数据d1n顺序存储的线性表，其算法的顺序存储的线性表，其算法的时间复杂度为时间复杂度为O(1)的操作是的操作是 （ ）。）。 A.将将n个元素从小到大排序个元素从小到大排序 B.从线性表中删除第从线性表中删除第i个元素（个元素（1in） C.查找第查找第i个元素（个元素（1in） D.向线性表中第向线性表中第i个元素之后插入一个元素（个元素之后插入一个元素（1in）6.在表头
5、指针为在表头指针为head且表长大于且表长大于1的单向循环链表中，指的单向循环链表中，指针针p指向表中的某个结点，若指向表中的某个结点，若p-next-next= =head,则则（ ）。）。 A. p指向头结点指向头结点 B. *p的直接后继是尾结点的直接后继是尾结点 C. p指向尾结点指向尾结点 D. *p的直接后继是头结点的直接后继是头结点CB7.在一个单链表中，删除在一个单链表中，删除*p结点之后的一个结点的操作是结点之后的一个结点的操作是（ ）。）。 A.p-next=p B.p-next-next=p-next C.p-next-next=p D.p-next=p-next-nex
6、t8.以下是结点以下是结点s（data, next）插入到结点）插入到结点p之后的插入过程，之后的插入过程，请补充完整。请补充完整。 s=new LNode; / 生成新结点生成新结点 if(s= =NULL) return ERROR; s-data=e; （ ）; （ ）;Ds-next=p-next;p-next=s;9.设单链表的结点结构为设单链表的结点结构为(data,next)，已知单链表的初始，已知单链表的初始状态如下图所示，执行下列程序段后，画出变化后的单状态如下图所示，执行下列程序段后，画出变化后的单链表结构图。链表结构图。T=L;while(T-next!=NULL) if
7、(T-datadata=T-data*2; T=T-next; 3.1 栈的类型定义栈的类型定义3.3 栈的应用举例栈的应用举例3.2 栈类型的实现栈类型的实现3.4 队列的类型定义队列的类型定义3.5 队列类型的实现队列类型的实现1.1.掌握掌握栈和队列类型的特点，栈和队列类型的特点，并能在相应的应并能在相应的应用问题中正确选用它们。用问题中正确选用它们。2.2.熟练掌握熟练掌握栈类型栈类型的基本操作和实现算法。的基本操作和实现算法。3.3.熟练掌握熟练掌握循环队列循环队列的基本操作实现算法。的基本操作实现算法。本章学习要点4.4.理解理解使用栈实现非递归的原理使用栈实现非递归的原理。1.
8、栈和队列的共同点是（栈和队列的共同点是（ ） A.都是先进先出都是先进先出 B.都是先进后出都是先进后出 C.只允许在端点处插入和删除元素只允许在端点处插入和删除元素 D.没有共同点没有共同点2.经过以下栈运算后，经过以下栈运算后，StackEmpty( s )的值是（的值是（ ） InitStack(s);Push(s,a);Push(s,b);Pop(s,x);Pop(s,y); A.a B.b C.1 D.03.4个元素个元素a、b、c和和d依次入栈，入栈过程中允许元素出依次入栈，入栈过程中允许元素出栈，假设某一时刻栈的状态是栈，假设某一时刻栈的状态是c（栈顶）、（栈顶）、b、a（栈（栈
9、底），则不可能的出栈顺序是（底），则不可能的出栈顺序是（ ）。）。 A. d,c,b,a B. c,b,d,a C. c,a,d,b D. c,d,b,a 4.向一个栈顶指针为向一个栈顶指针为Top的链栈中插入一个的链栈中插入一个p所指结点时，所指结点时，其操作步骤为（其操作步骤为（ ） A.Top-next=p; B.p-next=Top-next;Top-next=p; C.p-next=Top;Top=p; D.p-next=Top;Top=Top-next;第第3章练习题章练习题CCCC5. 设有一顺序栈设有一顺序栈S，元素，元素a，b，c，d，e，f依次进栈，如依次进栈，如果果6个元
10、素出栈的顺序是个元素出栈的顺序是b，d，c，f，e，a，则栈的容，则栈的容量至少应该是（量至少应该是（ ） A.2 B.3 C.5 D.66.若用一个大小为若用一个大小为6的数组来实现循环队列，且当前的数组来实现循环队列，且当前rear和和front的值分别为的值分别为0和和3，当从队列中删除一个元素，当从队列中删除一个元素，再加入两个元素后，再加入两个元素后，rear和和front的值分别为的值分别为( )。 A. 1和和5 B. 2和和4 C. 4和和2 D. 5和和17.判定一个循环队列判定一个循环队列Q（存放元素位置（存放元素位置0MaxSize-1）队）队满的条件是（满的条件是（ ）
11、A.Q.front=Q.rear B. Q.rear=(Q.front+1)%MaxSizeC.Q.front=(Q.rear+1)%MaxSize D.Q.front+1=Q.rearBBC8. 设循环队列中数组的下标是设循环队列中数组的下标是0N-1，其头尾指针分别为，其头尾指针分别为f和和r，则其元素个数为（，则其元素个数为（ ） A. r-f B.r-f-1 C.(r-f)%N+1 D.(r-f+N)%N9.设有编号为设有编号为1，2，3，4的四辆列车，顺序进入一个栈式的四辆列车，顺序进入一个栈式结构的车站，具体写出这四辆列车开出车站的所有可能结构的车站，具体写出这四辆列车开出车站的所
12、有可能的顺序。的顺序。答案：至少有答案：至少有14种。种。 全进之后再出情况，只有全进之后再出情况，只有1种：种：4,3,2,1 进进3个之后再出的情况，有个之后再出的情况，有3种，种，3,4,2,1 3,2,4,1 3,2,1,4 进进2个之后再出的情况，有个之后再出的情况，有5种，种，2,4,3,1 2,3,4,1 2,1, 3,4 2,1,4,3 2,3,1,4 进进1个之后再出的情况，有个之后再出的情况，有5种，种，1,4,3,2 1,3,2,4 1,3,4,2 1,2,3,4 1,2,4,3D10.以下代码段是最大长度为以下代码段是最大长度为N的循环队列的循环队列Q的入队操作，的入队
13、操作，请补充完整。请补充完整。Status EnQueue(SqQueue &Q, QElemType e)if( ) return ERROR; /队列满队列满Q.baseQ.rear=e;( ); /队尾后移一位队尾后移一位return OK;(Q.rear+1)%N=Q.front;Q.rear=(Q.rear+1)%N;11.利用算符优先算法对表达式利用算符优先算法对表达式8/(31)求值，写出求值过求值，写出求值过程中操作数栈（程中操作数栈（OPND）和算符栈（）和算符栈（OPTR）的变化情况。）的变化情况。步骤步骤算符栈算符栈操作数栈操作数栈表达式表达式0#8/(3-1)#1#8/
14、(3-1)#2# /8(3-1)#3# / (83-1)#4# / (8 3-1)#5# / ( -8 31)#6# / ( -8 3 1)#7# / (8 2)#8#/8 2#9#4#4.1 串类型的定义串类型的定义4.2 串的表示和实现串的表示和实现1.1.熟悉串的基本操作。熟悉串的基本操作。2.2.熟练掌握在不同的存储结构下，串的特点。熟练掌握在不同的存储结构下，串的特点。本章学习要点1.串是一种特殊的线性表，其特殊性体现在（串是一种特殊的线性表，其特殊性体现在（ ） A.可以顺序存储可以顺序存储 B.数据元素是一个字符数据元素是一个字符 C.可以链式存储可以链式存储 D.数据元素可以是
15、多个字符数据元素可以是多个字符2.若串若串S=“software”，其子串数目是（，其子串数目是（ ） A.8 B.37 C.36 D.9 3.设设s= 数据结构数据结构A，则，则StrLength(s)=（ ）。）。BB95.15.1 数组的类型定义数组的类型定义5.25.2 数组的顺序表示和实现数组的顺序表示和实现5.45.4 广义表的类型定义广义表的类型定义本章学习要点1.1.掌握二维数组以行为主序和以列为主的存储掌握二维数组以行为主序和以列为主的存储结构中的地址计算方法。结构中的地址计算方法。2.2.掌握广义表的定义。掌握广义表的定义。1. 数组数组A05,06的每个元素占的每个元素占
16、5个单元，将其按列优个单元，将其按列优先次序存储在起始地址为先次序存储在起始地址为1000的连续内存单元中，则元的连续内存单元中，则元素素a55的地址为（的地址为（ ） A.1175 B.1180 C.1205 D.12102.空的广义表，是指广义表（空的广义表，是指广义表（ ）A.深度为深度为0 B.尚未赋值尚未赋值 C.不含任何原子不含任何原子 D.不含任何元素不含任何元素3.对于广义表对于广义表(a,b),(),(a,(b)来说，其（来说，其（ ） A.长度为长度为4 B.深度为深度为4 C.有有3个元素个元素 D.有有2个元素个元素4.在广义表在广义表(a,b),c,(d),e),(f
17、,j,(g),(h)中，第中，第4个元素的第个元素的第3个元素是（个元素是（ ） A.原子原子g B.子表子表(g) C.原子原子e D.子表子表(d),e)ADCB5.广义表广义表A=(a,b,(c,d),(e,(f,g)，则下面式子的值是（，则下面式子的值是（ ） Headtailheadtailtail(A) A. (g) B. (d) C. (c) D. d6.已知广义表已知广义表L=(x,y,z),a,(u,t,w)，从，从L表中取出原子项表中取出原子项t的的运算是（运算是（ ）A. Head(Tail(Tail(L)B. Tail(Head(Head(Tail(L)C. Head(
18、Tail(Head(Tail(L)D. Head(Tail(Head(Tail(Tail(L)DD6.1 树的类型定义树的类型定义6.2 二叉树的类型定义和实现二叉树的类型定义和实现6.3 遍历二叉树和线索二叉树遍历二叉树和线索二叉树6.4 树和森林树和森林6.5 Huffman树与树与Huffman编码编码本章学习要点1.1.熟练掌握熟练掌握二叉树的性质二叉树的性质，了解相关，了解相关性质证明性质证明。2.2.熟悉熟悉二叉链表二叉链表的存储结构的特点。的存储结构的特点。3.3.掌握各种二叉树掌握各种二叉树遍历策略遍历策略的递归和非递归算法，的递归和非递归算法，灵活运用遍历算法实现其它操作。灵
19、活运用遍历算法实现其它操作。4.4.理解理解线索二叉树线索二叉树以及二叉树的线索化过程。以及二叉树的线索化过程。5.5.熟悉熟悉树的存储结构树的存储结构及其基本操作。及其基本操作。6.6.掌握掌握树和森林与二叉树的转换方法树和森林与二叉树的转换方法。7.7.了解最优二叉树的特性，掌握建立最优二叉树了解最优二叉树的特性，掌握建立最优二叉树和和Huffman编码编码的方法。的方法。1.对于一颗具有对于一颗具有n个结点，度为个结点，度为4的树来说，（的树来说，（ ） A.树的高度至多是树的高度至多是n-3 B.至少在某一层上正好有至少在某一层上正好有4个结点个结点C.树的高度至多是树的高度至多是n-
20、4 D.第第i层上至多有层上至多有4*(i-1)个结点个结点 2.用双亲存储结构表示树，其优点之一是比较方便（用双亲存储结构表示树，其优点之一是比较方便（ ）A.找指定结点的双亲结点找指定结点的双亲结点 B.找指定结点的孩子结点找指定结点的孩子结点C.找指定结点的兄弟结点找指定结点的兄弟结点 D.判断某结点是不是叶子结点判断某结点是不是叶子结点3.用孩子链存储结构表示树，其优点之一是比较方便（）用孩子链存储结构表示树，其优点之一是比较方便（）A.判断两个指定结点是不是兄弟判断两个指定结点是不是兄弟 B.找指定结点的双亲找指定结点的双亲C.判断指定结点在第几层判断指定结点在第几层 D.计算指定结
21、点的度数计算指定结点的度数4.如果在树的孩子兄弟链存储结构中有如果在树的孩子兄弟链存储结构中有6个空的左指针域，个空的左指针域，7个空的右指针域，则该树中树叶的个数为（个空的右指针域，则该树中树叶的个数为（ ）A.7个个 B.6个个 C.13个个 D.不能确定不能确定AADB5.设森林设森林F中有中有3棵树，第一，第二，和第三棵树的结点个棵树，第一，第二，和第三棵树的结点个数分别为数分别为m1，m2和和m3。与森林。与森林F对应的二叉树根结点对应的二叉树根结点的右子树上的结点个数是（的右子树上的结点个数是（ ） A.m1 B.m1+m2 C.m3 D.m2+m36.如果如果T1是由树是由树T转
22、换而来的二叉树，那么转换而来的二叉树，那么T中结点的后中结点的后根序列就是根序列就是T1中结点的（中结点的（ ）序列）序列 A.先序先序 B.中序中序 C.后序后序 D.层次层次7.二叉树和度为二叉树和度为2的树的相同之处包括（的树的相同之处包括（ ） A.每个结点都有一个或两个孩子结点每个结点都有一个或两个孩子结点 B.至少有一个根结点至少有一个根结点 C.至少有一个度为至少有一个度为2的结点的结点 D.每个结点至多只有一个双亲结点每个结点至多只有一个双亲结点DBD8.若一棵二叉树具有若一棵二叉树具有10个度为个度为2的结点，的结点，5个度为个度为1的结点，的结点，则度为则度为0的结点个数是
23、（的结点个数是（ ） A.9 B.11 C.15 D.不确定不确定9.一棵完全二叉树上有一棵完全二叉树上有1001个结点，其中叶子结点的个数个结点，其中叶子结点的个数是（是（ ） A.500 B.501 C.254 D.50510.一棵有一棵有124个叶子结点的完全二叉树，最多有（个叶子结点的完全二叉树，最多有（ ）个）个结点。结点。 A.247 B.248 C.249 D.25011.在一棵具有在一棵具有n个结点的完全二叉树中，分支结点的最大个结点的完全二叉树中，分支结点的最大编号为（编号为（ ） A. (n+1)/2 B. (n-1)/2 C. n/2 D. n/2 BBBD12.如果一棵
24、二叉树的先序序列是如果一棵二叉树的先序序列是ab，中序序列，中序序列是是ba，则（，则（ ） A.结点结点a和结点和结点b分别在某结点的左子树和右子树中分别在某结点的左子树和右子树中 B.结点结点b在结点在结点a的右子树中的右子树中 C.结点结点b在结点在结点a的左子树中的左子树中 D.结点结点a和结点和结点b分别在某结点的两棵非空子树中分别在某结点的两棵非空子树中13.设有设有13个值，用它们组成一棵哈夫曼树，则该哈夫曼个值，用它们组成一棵哈夫曼树，则该哈夫曼树共有（树共有（ ）个结点。）个结点。 A. 13 B.12 C.26 D.2514.根据使用频率为根据使用频率为5个字符设计的哈夫曼
25、编码不可能的是个字符设计的哈夫曼编码不可能的是（ ） A.111,110,10,01,00 B.000,001,010,011,1 C.100,11,10,1,0 D.001,000,01,11,10CDC15.若二叉树采用二叉链表存储结构，要交换其所有分支若二叉树采用二叉链表存储结构，要交换其所有分支结点左右子树的位置，采用（结点左右子树的位置，采用（ ）遍历方法最合适。）遍历方法最合适。 A.先序先序 B.中序中序 C.后序后序 D.层次层次16.若二叉树的中序序列是若二叉树的中序序列是abcdef，且，且c为根结点，则（为根结点，则（ ） A.结点结点c有两个孩子有两个孩子 B.二叉树有
26、两个度为二叉树有两个度为0的结点的结点 C.二叉树的高度为二叉树的高度为5 D.以上都不对以上都不对17.在任何一棵二叉树中，如果结点在任何一棵二叉树中，如果结点a有左孩子有左孩子b，右孩子，右孩子c，则在结点的先序序列、中序序列、后序序列中，（则在结点的先序序列、中序序列、后序序列中，（ ）A.结点结点b一定在结点一定在结点a的前面的前面 B.结点结点a一定在结点一定在结点c的前面的前面C.结点结点b一定在结点一定在结点c的前面的前面 D.结点结点a一定在结点一定在结点b的前面的前面CAC7.1 图的类型定义图的类型定义7.2 图的存储结构图的存储结构7.3 图的遍历图的遍历7.4 最小生成
27、树最小生成树7.5 有向无环图及关键路径有向无环图及关键路径7.6 最短路径最短路径2.2.熟悉图的各种熟悉图的各种存储结构存储结构，解实际问题的求解效，解实际问题的求解效率与采用何种存储结构有密切联系。率与采用何种存储结构有密切联系。本章学习要点3.3.熟练掌握图的两种搜索路径的熟练掌握图的两种搜索路径的遍历遍历：深度优先：深度优先搜索和广度优先搜索的算法。搜索和广度优先搜索的算法。4.4.掌握图的掌握图的最小生成树、拓扑排序、关键路径和最小生成树、拓扑排序、关键路径和最短路径最短路径的求解方法的求解方法1.1.熟练掌握图的熟练掌握图的各相关定义各相关定义。1. 在一个有向图中，所有顶点的度
28、数之和等于图的弧数在一个有向图中，所有顶点的度数之和等于图的弧数的（的（ ）倍。）倍。 A1/2 B. 1 C. 2 D. 4 2. 无向图的邻接矩阵是一个（）。无向图的邻接矩阵是一个（）。 A. 对称矩阵对称矩阵 B. 零矩阵零矩阵 C. 上三角矩阵上三角矩阵 D. 对角矩阵对角矩阵3.一个有一个有n个结点的有向完全图有（）条弧。个结点的有向完全图有（）条弧。 A. n B. n(n-1) C. n(n-1)/2 D. 2n4.具有具有6个顶点的无向图至少应有（）条边才能确保是一个顶点的无向图至少应有（）条边才能确保是一个连通图。个连通图。 A. 5 B. 6 C. 7 D. 85.G是一个
29、非连通无向图，共有是一个非连通无向图，共有28条边，则该图至少有条边，则该图至少有（）（） 个顶点。个顶点。 A. 6 B. 7 C. 8 D. 9CABAD第第7章练习题章练习题练习题6. 下面结构中最适于表示稀疏无向图的是（）。下面结构中最适于表示稀疏无向图的是（）。A. 邻接矩阵邻接矩阵 B. 邻接表邻接表 C. 邻接多重表邻接多重表 D. 十字链表十字链表7.任何一个无向连通图有（）最小生成树。任何一个无向连通图有（）最小生成树。 A. 只有一棵只有一棵 B. 有一棵或多棵有一棵或多棵 C. 一定有多棵一定有多棵 D. 可能不存在可能不存在 8. n条边的无向图的邻接表的存储中，边结点
30、的个数有条边的无向图的邻接表的存储中，边结点的个数有 （）个。（）个。 A. n B. 2n C. n/2 D. nn9.如果从无向图的任一顶点出发进行一次深度优先搜索即如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是（）。可访问所有顶点，则该图一定是（）。 A.完全图完全图 B.连通图连通图 C.有回路有回路 D.一棵树一棵树CBBB练习题10.采用邻接表存储的图的深度优先遍历算法类似于二叉采用邻接表存储的图的深度优先遍历算法类似于二叉树的（）算法。树的（）算法。 A.先序遍历先序遍历 B.中序遍历中序遍历 C.后序遍历后序遍历 D.层次遍历层次遍历11.对于含有
31、对于含有n个顶点的带权连通图，它的最小生成树是指个顶点的带权连通图，它的最小生成树是指图中任意一个（）。图中任意一个（）。 A. 由由n-1条权值最小的边构成的子图条权值最小的边构成的子图 B. 由由n-1条权值之和最小的边构成的子图条权值之和最小的边构成的子图 C.由由n-1条权值之和最小的边构成的连通子图条权值之和最小的边构成的连通子图 D. 由由n个顶点构成的边的权值之和最小的连通子图个顶点构成的边的权值之和最小的连通子图AD练习题12.判断一个有向图是否存在回路除了可以利用拓扑排序判断一个有向图是否存在回路除了可以利用拓扑排序方法外，还可以用（）。方法外，还可以用（）。 A. 求关键路
32、径的方法求关键路径的方法 B. 求最短路径的方法求最短路径的方法 C.广度优先遍历算法广度优先遍历算法 D. 深度优先遍历算法深度优先遍历算法13.若图的邻接矩阵中主对角线上的元素全是若图的邻接矩阵中主对角线上的元素全是0，其余元素，其余元素全是全是1，则可以断定该图一定是（）。，则可以断定该图一定是（）。 A. 无向图无向图 B. 不是带权图不是带权图 C. 有向图有向图 D. 完全图完全图14.关键路径是关键路径是AOV网中（）。网中（）。 A.从源点到汇点的最长路径从源点到汇点的最长路径 B.最长的回路最长的回路 C.从源点到汇点的最短路径从源点到汇点的最短路径 D.最短的回路最短的回路
33、15.最短路径的生成算法可用（）。最短路径的生成算法可用（）。 A. Prim算法算法 B. Kruskal算法算法 C. Dijkstra算法算法 D. Huffman算法算法DDAC练习题填空题填空题1.一个图的一个图的 示法是唯一的，而示法是唯一的，而 表示法是表示法是不唯一的。不唯一的。2.用一个邻接矩阵存储有向图用一个邻接矩阵存储有向图G，其第，其第i行的所有元素之和行的所有元素之和等于顶点等于顶点i的的 。3.图的逆邻接表存储结构只适用于图的逆邻接表存储结构只适用于 图。图。4.连通分量是无向图的连通分量是无向图的 连通子图。连通子图。5.一个连通图的一个连通图的 是一个极小连通子
34、图。是一个极小连通子图。6. Prim算法适用于求算法适用于求 网的最小生成树；网的最小生成树； 7. Kruskal适用于求适用于求 网的最小生成树。网的最小生成树。8.如果如果n个顶点的图是一个环，则它有个顶点的图是一个环，则它有 棵生成树。棵生成树。9.拓扑排序算法是通过重复选择具有拓扑排序算法是通过重复选择具有 个前驱顶点的个前驱顶点的过程来完成的。过程来完成的。邻接矩阵邻接矩阵邻接表邻接表出度出度有向有向极大极大生成树生成树边稠密边稠密边稀疏边稀疏n09.1 静态查找表静态查找表9.2 动态查找表动态查找表9.3 哈希表哈希表1.1.顺序表和有序表顺序表和有序表的查找方法及其的查找方
35、法及其平均查找长平均查找长度度的计算方法。的计算方法。2.2.熟练掌握熟练掌握折半查找和判定树折半查找和判定树的构造。的构造。3.3.熟练掌握熟练掌握二叉排序树二叉排序树的构造和查找方法。的构造和查找方法。4.4.熟练掌握熟练掌握哈希表哈希表的构造方法，深刻理解哈希的构造方法，深刻理解哈希表与其它结构的表的实质性的差别。表与其它结构的表的实质性的差别。5.5.掌握按定义计算各种查找方法在等概率情况掌握按定义计算各种查找方法在等概率情况下查找成功时的下查找成功时的平均查找长度平均查找长度。本章学习要点填空题填空题1.1.在数据的存放无规律而言的线性表中进行查找的最在数据的存放无规律而言的线性表中
36、进行查找的最佳方法是（）。佳方法是（）。2.2.线性有序表（线性有序表（a a1 1，a a2 2，a a3 3，a a256256）是从小到大排）是从小到大排列的，对一个给定的值列的，对一个给定的值k k，用折半查找法查找表中与，用折半查找法查找表中与k k相等的元素，在查找不成功的情况下，相等的元素，在查找不成功的情况下，最多最多需要比需要比较较（）（）次。设有次。设有100100个结点，用折半查找法查找时，个结点，用折半查找法查找时，最大比较次数是最大比较次数是（）（）。3.3.假设在有序线性表假设在有序线性表a20a20上进行折半查找，则比较一上进行折半查找，则比较一次查找成功的结点数
37、为次查找成功的结点数为1 1；比较两次查找成功的结点；比较两次查找成功的结点数为数为（）（）；比较四次查找成功的结点数为；比较四次查找成功的结点数为（）（）；平；平均查找长度为均查找长度为（）（）。顺序查找顺序查找2，8，3.7 9，7（1122438455）/20 =74/20=3.7 第第9章练习题章练习题4.4.折半查找有序表折半查找有序表44，6 6，1212，2020，2828，3838，5050，7070，8888，100100，若查找表中元素，若查找表中元素2020，它将依次与表中元，它将依次与表中元素（素（ ）比较大小。）比较大小。5.5.对二叉排序数进行（）遍历，可以得到按关
38、键字从对二叉排序数进行（）遍历，可以得到按关键字从小到大排列的结点序列。小到大排列的结点序列。6.6.评价哈希函数好坏的标准是（）。评价哈希函数好坏的标准是（）。7.7.哈希表存储的基本思想是由（）决定数据的存储地哈希表存储的基本思想是由（）决定数据的存储地址。址。选择题选择题1. 静态查找表与动态查找表的根本区别在于（）。静态查找表与动态查找表的根本区别在于（）。A. 逻辑结构不一样逻辑结构不一样 B. 施加在其上的操作不一样施加在其上的操作不一样 C. 所包含的数据元素类型不一样所包含的数据元素类型不一样 D. 存储实现不一样存储实现不一样 28，6，12，20中序中序哈希函数取值是否均匀
39、哈希函数取值是否均匀B关键字的值关键字的值 2. 在表长为在表长为n的顺序表上实施顺序查找，在查找不成功时的顺序表上实施顺序查找，在查找不成功时与关键字比较的次数为（）。与关键字比较的次数为（）。 A. n B. 1 C. n+1 D. n-13.顺序查找适用于存储结构为（）的线性表。顺序查找适用于存储结构为（）的线性表。 A. 哈希存储哈希存储B.压缩存储压缩存储C. 顺序或链式存储顺序或链式存储D.索引存储索引存储4.适于折半查找的表的存储方式及元素排列要求为（）适于折半查找的表的存储方式及元素排列要求为（）A. 链式链式,无序无序 B.链式链式,有序有序 C. 顺序顺序,无序无序 D.顺
40、序顺序,有序有序5.对对22个记录的有序表作折半查找，当查找失败时，个记录的有序表作折半查找，当查找失败时，至至少少需要比较（）次关键字。需要比较（）次关键字。A3 B4 C5 D 6ACDB6.二叉排序树中，键值最小的结点一定（）二叉排序树中，键值最小的结点一定（）A.左指针为空左指针为空 B.右指针为空右指针为空C.左右指针均为空左右指针均为空 D.左右指针均非空左右指针均非空7. 在有序表在有序表1，3，9，12，32，41，62，75，77，82，95，100上进行折半查找关键字为上进行折半查找关键字为82的数据元素需要的数据元素需要比较（）次。比较（）次。 A. 1 B. 2 C.
41、4 D. 5 8. 采用分块查找时，若线性表中共有采用分块查找时，若线性表中共有625个元素，查找每个元素，查找每个元素的概率相同，假设采用顺序查找来确定结点所个元素的概率相同，假设采用顺序查找来确定结点所在的块，每块应分（）个结点最佳。在的块，每块应分（）个结点最佳。 A. 10 B. 25 C. 6 D. 625ACB9.设哈希表长为设哈希表长为14，哈希函数为，哈希函数为H(key)=key mod 11，当，当前表中已有前表中已有4个结点：个结点：addr(15)=4，addr(38)=5，addr(61)=6，addr(84)=7。如用二次探测再散列处理。如用二次探测再散列处理冲突，则关键字为冲突，则关键字为49的结点的地址是（）。的结点的地址是（）。 A. 8 B.3 C. 5 D.910. 假设有假设有K个关键字互为同义词，若用线性探测法把这个关键字互为同义词，若用线性探测法把这K个关键字存入哈希表中，至少要进行（）次探测。个关键字存入哈希表中，至少要进行（）次探测。AK-1 BK CK+1 D K(K-1)/2DD0+1+2+(k-1)=k(k-1)/2