数据结构题集答案复习过程

1、数据结构题集答案数据结构题集第一章绪论一、单选题1 .在数据结构中，从逻辑上可以把数据结构分成C0A.动态结构和静态结构B.紧凑结构和非紧凑结构C.线性结构和非线性结构D.内部结构和外部结构2 .数据结构在计算机内存中的表示是指AoA.数据的存储结构B.数据结构C.数据结构的逻辑结构D.数据元素之间的关系3 .【A】是数据的最小单位，【B】是数据的基本单位。A.数据项B.数据元素C.信息项D.表元素4 .计算机所处理数据一般具有某种内在联系，这是指BoA.数据与数据之间存在某种关系B.数据元素与数据元素之间存在某种关系C.元素内部存在某种结构D.数据项与数据项之间存在某种关系5 .算法分析的目

2、的是【C】。A.找出数据结构的合理性B.研究输入和输出的关系C.分析算法的效率以求改进D.分析算法的易懂性6 .在存储数据时，不仅要考虑存储各数据元素的值，而且还要存储【C】。A.数据处理的方法B.数据元素的类型C.数据元素之间的关系D.数据的存储方法7 .算法分析的主要任务是分析DoA.算法是否具有较好的可读性8 .算法中是否存储语法错误和逻辑错误C.算法的功能是否符合设计要求D.算法的执行时间与问题规模之间的关系。8 .数据的运算AoA.效率与采用何种存储结构有关B.是根据存储结构来定义的C.有算术运算和关系运算两大类D.必须用程序设计语言来描述9 .算法的计算量的大小称为算法的BoA.效

3、率B.时间复杂度C.现实性D.难度10 .连续存储分配时，存储单元的地址【A】。A.一定连续B.一定不连续C.不一定连续D.部分连续，部分不连续二、判断题1 .数据元素是数据结构的最小单位【.X】。2 .数据的逻辑结构说明数据元素之间的顺序关系，它依赖于计算机的存储结构X.03 .数据的逻辑结构指数据元素的各数据项之间的逻辑关系【X.】。4 .算法的优劣与算法的描述语言无关，但与使用的计算机有关【.X】。5 .数据结构的抽象操作的定义与具体实现有关【.X】。三、填空题1 .数据的逻辑结构指数据元素之间的逻辑关系。2 .一个数据结构在计算机中的表示称为存储结构。3 .数据的物理结构主要包括顺序存

4、储结构的表示和链式存储结构的表示。4 .数据逻辑结构包括集合、线性结构、树和图四种,树结构和图结构统称为非线性结构。5 .顺序存储方法把逻辑上逻辑上相邻的元素存储在物理位置相邻的存储单五里；链式存储方法中结点间的逻辑关系是由指针域表示的。6、数据结构研究的是逻辑结构和物理结构以及它们之间的相互关系、并对于这种结构定义相应的运算，设计出相应的算法。7 .算法的执行时间是问题规模n的函数。8 .以下是4个算法所有语句频度之和的表达式，其中的复杂度相同的是A和B。A.TA(n)=2n3+3n2+1000B.TB(n尸n3-n210g2n-1000C.Tc(n)=n210g2n+n2D.TD(n)=n

5、2+1000四、解答题1 .简述数据的逻辑结构和存储结构的关系。答：在数据结构中，逻辑结构和存储结构是密切相关的，存储结构不仅将数据元素存储到计算机中，而且还要表示各数据元素之间的逻辑关系。逻辑结构与计算机无关，存储结构是数据元素之间的关系在计算机中的表示。通常情况下，一种逻辑结构可以有多种存储结构，例如，线性结构可以采取顺序存储结构或链式存粗结构表示。2 .数据结构和数据类型有什么区别？答：数据结构是相互间存在一种或多种特定关系的数据元素的集合，一般包括三个方面的内容：数据的逻辑结构、存储结构和多数据的运算。数据类型是一个值得集合和定义在这个值集上的一组操作的总称。数据结构重点考虑元素之间的

6、关系，数据类型重点考虑数据的个体特征。3 .当为解决某一问题已经选定其数据的逻辑结构后，选择数据的存储结构时,应从哪些方面考虑？答：通常从两个方面考虑：第一是算法实现的存储空间复杂度；第二是算法执行的时间复杂度。若存储空间难以确定，宜选择链式存储结构，否则选择顺序存储结构。若插入、删除操作频繁，则选链式存储结构，否则选择顺序存储结构。第二章线性表一、单选题1 .链表不具备的特点是【A】。A.可随机访问任一结点B.插入删除不需要移动元素C.不必事先估算存储空间D.所需空间与其长度成正比2 .设线性表有n个元素，以下操作中，【A】在顺序表上实现比在链表上实现效率更高。A.输出第i(1&iwn)个元

7、素的值B.顺序输出这n个元素C.交换第1个与第2个元素的值D.输出与给定值x相等的元素在线性表中的序号3 .如果最常用的操作是取第i个结点及其前驱，则采用【D】存储方法最节省时间。A.单链表B.双链表C.线性链表D.顺序表4 .线性表是具有口个C的有限序列(n10)。A.表元素B.字符C.数据元素D.数据项5 .下面关于线性表的叙述中，错误的是BoA.线性表采用顺序存储，则必须占用一片连续的存储单元B.线性表采用顺序存储，则便于插入和删除操作C.线性表采用链式存储，则不必占用一片连续的存储单元D.线性表采用链式存储，则便于插入和删除操作6 .线性表的顺序存储结构是一种AoA.随机存取的存储结构

8、B.顺序存取的存储结构C.索引存取的存储结构D.Hash存取的存储结构7 .单链表中增加一个头结点的目的是为了【CloA.使单链表至少有一个结点B.标识表首结点的位置C.方便运算的实现D.说明单链表是线性表的链式存储8 .不带头结点的单链表（头指针为h）为空的条件是AoA.h=NULLB.h-next=NULLC.h-next=hD.h!=NULL9 .带头结点的单链表（头指针为h）为空的条件是BoA.h=NULLB.h-next=NULLC.h-next=hD.h!=NULL10 .带头结点的循环双向链表（头指针为L）为空的条件是DoA.L=NULLB.L-next-prior=NULLC.

9、L-prior=NULLD.L-next=L11 .非空的循环单链表（头指针为head）的尾结点（由p指向）满足【C】。A.p-next=NULLB.p=NULLC.p-next=headD.p=head12 .设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用【A】最节省时间。A.带头结点的双循环链表B.单循环链表C.带尾指针的单循环链表D.单链表13 .若某线性表最常用的操作存取任意指定序号的元素和在表尾进行插入和删除，则选用【A】的存储方式最节省时间。A.顺序表B.双链表C.带头结点的双循环链表D.单循环链表14 .在n个结点的线性表的顺序实现中，算法的时间复杂度为O的操作是【A

10、loA.访问第i个结点和求第i个结点的直接前驱B.在第i个结点后插入一个新结点C.删除第i个结点D.以上都不对15 .若长度为n的线性表采用顺序存储结构，在第i个位置插入一个新元素的算法的时间复杂度为【C】。A.O(0)B.O(1)C.O(n)D.O(n2)16 .对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为CoA.O(n)O(n)B.O(n)O(1)C.O(1)O(n)D.O(1)O(1)17 .线性表以链式方式存储，访问第i个结点的时间复杂度为CoA.O(i)B.O(1)C.O(n)D.O(i-1)18 .循环链表H尾结点p的特点是AoA.p-next=HB.p-next=

11、H-nextC.p=HD.p=H-next二、判断题x1.取线性表的第i个元素的时间同i的大小有关。X2.线性表中每个元素都有一个直接前驱和一个直接后继。X3.顺序存储方式只能用于存储线性结构。X4.线性表采用链式存储时，结点和结点内部的存储空间可以不连续。X5.在一个设有头指针和尾指针的单链表中，执行删除单链表最后一个结点的操作与链表的长度无关。三、填空题1 .向一个长度为n的顺序表中的第i个元素之前插入一个元素时，需要向后移动n-i+1个元素。2 .在一个长度为n的顺序表中删除第i个元素时，需要向前移动上L个元素3 .在单链表中设置头结点的作用是简化插入、删除算法。4 .在单链中要删除某一

12、指定结点,必须找到该结点的直接前驱结点。5 .访问单链表中的结点，必须沿着指针域依次进行。6 .在双链表中每个结点有两个指针域，一个指向直接前驱结点，一个指向直接后继结点。7 .在双向循环链表中、删除最后一个结点的算法时间复杂度为0(1)。8 .访问一个线性表中具有给定值的时间复杂度的数量级是0(n)。9 .由n个数据元素生成一个顺序表，若每次都调用插入算法把一个元素插入到表头，则整个算法的时间复杂度为0(n)、若每次都调用插入算法把一个元素插入到表尾，则整个算法的时间复杂度为0(n2)。10 .在双向链表中、可以用表尾指针代替表头指针。11 .根据n个数据元素建立对应的顺序表和单链表存储结构

13、，其算法的时间复杂度最好的情况是0(n)、最坏的情况是0(n2)。12 .求线性表的顺序存储和链式存储的长度的算法时间复杂度分别是_0W和0(n)。13 .在一个带头结点的单链表中，在表头插入或删除与在其他位置插入或删除，其操作过程是否相同？相同。14 .在一个不带头结点的单链表中，在表头插入或删除与在其他位置插入或删除，其操作过程是否相同？不相同。四、简答题15 阐述顺序表和链表存储方式的特点。答：顺序表存储方式为数据分配连续的存储单元，数据元素按逻辑顺序依次存储到相应存储单元中，使得逻辑相邻的数据元素物理也相邻，因此可以实现随机访问线性表的数据元素，即数据访问的时间复杂度为0(1)。链表存

14、储方式分配的存储单元可以不连续，通过每个结点的指针域来表示数据元素之间的逻辑关系，只能顺序访问线性表中的数据元素。16 若频繁地对一个线性表进行插入和删除操作，则该线性表宜采用何种存储结构，为什么？答：若频繁地对一个线性表进行插入和删除操作，则该线性表宜采用链式存储结构。因为链式存储结构在插入和删除数据元素时不需要移动数据元素，只需要修改结点的指针域就可以改变数据元素之间的逻辑关系。17 在单链表、双向循环链表和单循环链表中，若仅知道指针p指向某结点，不知道头指针，能否将结点p从相应的链表中删除？若可以，时间复杂度各为多少。答：要实现删除p结点的操作，必须找到其前驱结点，修改其指针域的值使其指

15、向p的后继结点，以实现删除结点p。单链表不行，因为不知道头指针就无法找到结点p的前驱结点。双向循环链表和单循环链表可以可以实现删除p结点。单循环链表删除p结点的时间复杂度为0(n),双循环链表删除P结点的时间复杂度为0(1)。18 对链表设置头结点的作用是什么？答：对带头结点的链表，在表的任何结点之前插入结点或删除任何位置的结点，所要做的都是修改前一个结点的指针域，因为在带头结点的链表中任何元素结点都有前驱结点。如果没有头结点，在首元结点前插入结点或删除首元结点都要修改头指针，其算法要比带头结点的算法复杂些。其次，带头结点的链表结构，初始化后的头指针就固定了，除撤销算法外，所有算法都不会修改头

16、指针，可以减少出错的可能性。五、算法设计题19 已知一个线性表用含头结点的单链表做存储结构，写一个算法求单链表的长度。解：算法基本思想：从头结点的下一个结点开发，遍历单链表的每个结点，每遇到一个结点，结点计算器加1。intlistlenght(linklistL)intlength=0;P=L-next;while(p)length+;p=p-next;return(length);20 已知一个顺序表L,其中的元素按值递增有序排列，设计一个算法插入一个值为x的元素后保持该顺序表仍然递增有序，且空间复杂度为0(1)voidinsertsq(sqlistL,elemtypex)n=L.lengt

17、h-1;while(n=0<(x,L.elemn)L.elemn+1=L.elemn;n-;L.elemn+1=x;L.lenght+;return;)21 写一个算法，从顺序表中删除值为x的所有元素voiddelallsq(Sqlist&L)inti=0,j=0;while(jnext=Q.rear。10 .如果栈的最大长度难以估计,最好使用链栈。四、简答题1 .为什么说栈是一种后进先出表？答：因为栈是限定在表的一端进行插入和删除操作，所以后入栈的数据元素总是先出栈，所以说栈是一种后进先出表。2 .对于一个栈，其输入序列是A,B,C,试给出全部可能的输出序列。答：可能的出栈序列是：ABC

18、、ACB、BAC、BCA、CBA。3 .何谓队列上溢？何为假溢出现象？有哪些解决假溢出问题的方法，并分别阐述其工作原理。答：队列上溢指在队列的顺序存储分配中，所有单元中已有元素，再进行插入操作时称为队列上溢。假溢出指在队列的顺序存储分配中，分配给队列的存储空间有存储单元未被占用，但按照操作规则而使进队的数据元素无法进队的现象。解决假溢出问题的方法是在队列的顺序存储分配中，分配给队列的存储空间可以循环使用，具进本原理是用表示队头和队尾指针与分配给队列的存储空间长度进行取模运算。即：入队操作：Q.rear=(Q.rear+1)%MSize出队操作：Q.front=(Q.front+1)%MSize

19、4 .队列可以用单循环链表来实现，故可以只设一个头指针或只设一个尾指针，请分析用哪种方案最合适。答：使用循环链表来表示队列，设置尾指针比较合适，因为入队操作可以直接在尾结点后进行插入操作，出队操作时可以根据尾指针很容易找到链表的头结点，入队出队操作的算法时间复杂度均为0(1)。若只设头指针，则出队操作的算法时间复杂度为0(1),入队操作的算法时间复杂度为0(n)。5 .简述线性表、栈和队列的异同？答：栈和队列都是操作位置受限的线性表，即对插入和删除操作的位置加以限制。栈是仅允许在表的一端进行插入和删除操作的线性表，因而是后进先出表。队列是允许在表的一端进行插入，在表的另一端进行删除的线性表，因

20、而是先进先出表。线性表可以在任何位置进行插入和删除操作。五、算法设计题1 .设计一个算法，利用栈和队列的基本运算将指定栈中的元素顺序逆转。解：算法基本思想：先将栈中元素出栈运算移至队列中，再将队列中元素出队列移至栈中。voidreverse(Stack&st)Queuesq；ElemTypex;InitQueue(sq)while(!StackEmpty(st)pop(st,x)EnQueue(sq,x);while(!QueueEmpty(sq)DeQueue(sq,x);Push(st,x);DestroyQueue(sq);2 .设计一个算法，利用栈的基本运算返回指定栈中栈底元素。解：先

21、将栈中元素依次移至另一个临时栈中，最后一个元素即为栈底元素，设为x.。冉将临时栈中元素移至原栈中，即恢复栈内容。ElemTypebottom(Stack&st)ElemTypex,y;Stacktmpst;InitStack(tmpst)while(!StackEmpty(st)pop(st,x)push(tmpst,x);while(!QueueStack(temst)pop(tmpst,y);/此时必须用另一个变量y,才能保留栈底元素在中Push(st,y);DestroyStack(tmpst);return(x);3 .设计一个算法，利用栈来实现带头结点的单链表h的逆序。解：算法基本思

22、想：将单链表结点依次放入链栈中，链栈本身就是一个单链表，即实现了原单链表的逆序。假设链栈不带头结点，再加上原来的头结点，就完成了原单链表的逆序。Voidrevert(SNode*h)SNode*st=NULL,*p=h-next,q;While(p)q=p-next;p-next=st;st=p;p=q;h-next=st;第四章串一、单选题1 .用是任意有限个【D】。A.符号构成的集合B.符号构成的序列C.字符构成的集合D.字符构成的序列2 .用是一种特殊的线性表，其特殊性体现在BoA.可以顺序存储B.数据元素是一个字符C.数据元素可以使多个字符D.可以链接存储3 .两个用相等必有用长度相等

23、且【B】。A.用的各位置字符任意B.用中各位置字符均对应相等C.两个用含有相同的字符D.两个用所含字符任意4 .设有两个用p和q,求q在p中首次出现的位置的运算称着【B】。A.连接B.模式匹配C.求子用D.求用长二、填空1 .空用是长度为0的4。2 .一个用中任意连续字符组成的子序列称为该串的子串。3 .设s=abcd”,贝执行语句s2=Substr(s,2,2后，s2=bc。4 .空白串是由一个或多个空格字符组成的串，其长度等于其所包含的空格字符的个数。第五章数组一、单选题1.一维数组与线性表的区别是【A】。A.前者长度固定，后者长度可变B.后进长度固定，前者长度可变C.两者长度均固定D.两

24、者长度均可变2 .多维数组的数组元素之间的关系，【A】。A.是线性的B.是树型的C.既是线性的，又是树型的D.既不是线性的，也不是树型的3 .设有数组A810,每个元素占3个存储单元，存放该数组的存储单元数为CoA.80B.100C.240D.2704 .设有数组A810,每个元素占3个存储单元，首地址为SA,则元素口5的起始地址是【D】。A.SA+141B.SA+144C.SA+222D.SA+2255 .设有一个n*n的对称矩阵，采用压缩存储，则存入内存的元素个数为CoA.n*nB.n*n/2C.n*(n+1)/2D.(n+1)2/26 .设A是一个n*n的对称矩阵，压缩存储到一个一维数组

25、B0.n(n+1)/2-1中，则下三角部分元素ai,j在B中的位置是【A】。A.i(i-1)/2+j-1B.i(i-1)/2+jC.i(i+1)/2+j-1D.i(i+1)/2+j7 .稀疏矩阵一般的压缩方法有两种，即【CloA.二维数组和三维数组B.三元组和散列C.三元组和十字链表D.散列和十字链表8 .设有一个10*10的对称矩阵A,以行主次序进行压缩存储，每个元素占一个存储单元，a,i的地址是1,则A8,5的起始地址是【B】。A.13B.33C.18D.40二、解答题1.设数组A5080,其基地址为2000,每个元素占2个存储单元，以行序位主序顺序存储，回答下列问题：(1)该数据组由多少

26、元素？(2)该数组占用多少存储单元？(3)数组元素a3030的存储地址是多少？答：(1)该数组有：50*80=4000个元素(2)该数组占用4000*4=8000个存储单元(3)10c(30,30)=2000+(30*80+30)*2=2000+4860=6860第六章树与二叉树一、单选题1 .有关二叉树下列说法正确的是【B】。A.二叉树的度为2B.一棵二叉树的度可以小于2C.一棵二叉树至少有一个结点的度为2D.二叉树中任何一个结点的度为22 .利用二叉链表存储树，则根结点的右指针是CoA.指向最左孩子B.指向最右孩子C.空D.非空3 .若一棵二叉树具有10个度为2的结点，5个度为1的结点，则

27、度为0的结点个数为【B】。A.9B.11C.15D.不确定4 .一棵二叉树有1001个结点，其中叶结点的个数为【D】。A.250B.490C.254D不确定5 .一棵完全二叉树有1001个结点，其中叶结点的个数为【D】。A.250B.500C.254D.以上答案均不对6 .一棵具有1025个结点的二叉树的高h为1C】。A.11B.11C.11至1025之间D.10至1024之间7 .一棵124个叶结点的完全树，最多具有B个结点。A.247B.248C.249D.2518 .一棵具有10个叶结点的二叉树具有B度为2的结点。A.8B.9C.10D.119 .已知一棵完全二叉树有625个结点，叶结点

28、的个数为CoA.311B.312C.313D其它10 .一棵具有n个结点的完全二叉树的高h为AB0A.log2n+1B.log2n+1C.log2n+1D.log2n-111 .由8个权值构造一棵哈夫曼树，该哈夫曼树有A个结点A.15B.16C.17D.1412 .由3个结点可以构造【D】种不同的二叉树。A.2B.3C.4D.513 .树最适合用来表示【C】。A.有序数据元素B无序数据元素C.元素间具有分支层次关系的数据D.元素间无联系的数据15 .某二叉树的先序遍历序列和后序便利序列正好相反，则该二叉树一定是【A1oA.空或只有一个结点B.完全二叉树C.二叉排序树D.高度等于其结点数16 .

29、在一棵非空二叉树的中序遍历序列中，根结点的右边【A】。A.只有右子树上的所有结点B只有右子树上的部分结点C.只有左子树上的部分结点D只有左子树上的所有结点17 .任何一棵二叉树的叶子结点在先序、中序和后序遍历序列中的相对次序AoA.不发生上改变B发生改变C.不能确定D.以上都不对18 .一棵满二叉树，m个叶结点，n个结点，深度为h,则【D】。A.n=h+mB.h+m=2nC.m=h-1D.n=2h-119 .设n,m是二叉树上的两个结点，在中序遍历时，n在m之前的条件是CoA.n在m右方B.n是m的祖先C.n在m左方D.n是m的子孙20.设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉

30、树中包含的结点数最少为【B】。A.2hB.2h-1C.2h+1D.h+1二、判断题x1.二叉树是一般树的特殊树型。IV】2.树与二叉树是两种不同的树形结构。【X】3.对于有n个结点的二叉树，其高度为10g2n。V4.完全二叉树中，若一个没有左孩子，则它必定是叶结点。5.一棵具有n个结点的完全二叉树，从上到下、从左到右用自然数对结点进行编号，结点为i的结点的左孩子的编号为2i(2ilchild=NULL&p-rchild=NULL。10 .二叉树的先序序列和中序序列相等的条件是任何结点至多只有右子树011 .有一棵如下图所示的树，回答下列问题：这棵树的根结点是a。这棵树的叶子结点是b,e,g,d

31、。结点c的度为2。这棵树的深度是4。结点c的孩子结点是ef。结点c的双亲结点是a。这棵树的度是。12 .树与二叉树的两个主要差别是树中结点的最大度没有限制，二叉树结点的最大度限定为2、树的结点无左右之分，二叉树的的结点有左右之分013 .树中任一结点允许有0个或多个孩子个孩子结点,除根结点之外，其余结点有1个双亲结点。四、简答题1.设有如下图所示的二叉树，给出其前序、中序和后序遍历结果。答：前序序列：eadcbifghj中序序列：abcdiefhgj后序序列：bcidahjgfe2.给出下图所示的树的二叉树表示。答：下图为其树的二叉树表示3 .有一份电文共有5个字符：a,b,c,d,e它们出现

32、的频率依次为4,7,5,2,9,构造对应的哈夫曼树，求哈夫曼树的带权路径长度和每个字符的哈夫曼编码。字符编码：a：011b:10c：00d:010e：114 .假设一棵二叉树采用顺序存储结构，如下图所示05101520eafdgcjhib回答些列问题：画出二叉树表示。写出先序、中序和后序遍历结果写出结点c的双亲结点和左、右孩子结点画出此二叉树还原成森林的图先序序列为：eadcbjfghi中序序列为：acbdjefhgi后序序列为：bcjdahigfe结点c的双亲结点是d,左孩子为b,无右孩子该二叉树对应的森林为第七章图一、单选题1 .在一个无向图中，所有顶点的度数之和等于所有边的【C】倍。A.

33、1/2B.1C.2D.42 .在一个有向图中，所有顶点的入度数之和等于所有顶点的出度之和的【B】倍。A.1/2B.1C.2D.43 .一个有n个顶点的无向图最多有C条边。A.nB.n(n-1)C.n(n-1)/2D.2n4 .具有4个顶点的无向完全图有A条边。A.6B.12C.16D.205 .具有6个顶点的无向图至少应有A)条边才能确保是一个连通图。A.5B.6C.7D.86 .一个有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是D0A.nB.(n-1)2C.(n-1)D.n27 .对某个无向图的邻接矩阵来说，AoA.第i行上的非0元素个数等于第i列上非0元素个数8 .矩阵中非0元素

34、个数等于图中的边数C.第i行、第i列上非0元素个数等于顶点vi的度数D.矩阵中非全0行的行数等于图中的顶点数8.对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表头向量的大小为【A；所有邻接表中结点总数为Co A.nB.n+1C.n-1D.n2 A.e/2B.eC.2eD.n+e二、判断题【X】1.n个顶点的无向图至多有n(n-1)条边。2.有向图中，各顶点的入度之和等于各顶点的出度之和。【，】3.邻接矩阵只存储了边的信息，没有存储顶点的信息。【X】4.连通分量是无向图的极小连通子图。【X】5.如果表示有向图的邻接矩阵是对称的，则该有向图一定是完全有向图。【X】6.如果表示图的邻接矩

35、阵是对称的，则该图一定是无向图。VJ7.如果表示图的邻接矩阵不是对称的，则该图一定是有向图。三、填空题1 .有n个顶点的无向图最多有n(n-1)/2条边。2 .具有n个顶点的强连通有向图至少有_n一条边。3 .具有n个顶点的有向图最多有n(n-1)条边。4 .一个图的临接矩阵表示法是唯一的.而邻接表表示法是不唯一的。5 .具有10个顶点的无向图，边的总数最多为45。6 .在有n个顶点的有向图中，每个顶点的度最大可达n-1。7 .已知一个有向图采用邻接矩阵表示，计算第i个顶点的入度的方法是求第i列非0元素个数。8 .已知一个有向图的邻接矩阵表示，删除所有从第i个结点出发的弧的方法是将第i行对应的

36、1置成0。9 .对于n的顶点的无向图，采用邻接矩阵表示，求图中边的方法是计算邻接矩阵中元素值为1的个数,判断任意两个顶点是否有边相连的方法是判断对应邻接矩阵元素的值是否为1,再除以2,求任意顶点的度的方法是求邻接矩阵中对应顶点所在行值为1的元素个数。10 .对于n的顶点的有向图，采用邻接矩阵表示，求图中边的方法是计算邻接矩阵中元素值为1的个数,判断任意两个顶点是否有边相连的方法是判断对应邻接矩阵元素的值是否为1,求任意顶点的度的方法是求邻接矩阵中对应顶点所在行和列的元素值为1的个数。11 .无向图的连通分量指无向图中最大连通子图。12 .若无向图有m条边，则表示该无向图的邻接表中有2m结点。四

37、、简答题1 .从占用的存储空间来看，对于稠密图和稀疏图，采用邻接矩阵和邻接表那个更好些？答：从占用存储空间看，稠密图采用邻接矩阵更好，稀疏图采用邻接表更好。2 .用邻接矩阵表示图时，矩阵元素的个数与顶点个数是否相关？与边的条数是否相关？为什么？。答：用邻接矩阵表示图，矩阵元素的个数与图的顶点个数直接相关，与边的条数无关。因为假设定点个数为n,则邻接矩阵的大小为n20第九章查找一、单选题1 .顺序查找法适合于存储结构为【B】的查找表。A.散列存储B.顺序存储或链式存储C.压缩存储D.索引存储2 .对查找表进行折半查找时，要求查找表必须【B】。A.以顺序方式存储B.以顺序方式存储，且结点按关键字有

38、序排列C.以链式方式存储D.以链式方式存储，且结点按关键字有序排列3.采用顺序查找法查找长度为n的查找表时，每个元素查找的平均查找长度为C oA.nB.n/2C.(n+1)/2D.(n-1)/24.采用折半查找法查找长度为n的查找表时，每个元素查找的平均查找长度为D 0A.O(n2)B.O(nlog2n)C.O(n)D.O(log2n)5 .采用分块查找时，若查找表中有625个元素，查找每个元素的概率相同，假设对索引表和块都采用顺序查找，每块应分B个结点最佳。A.10B.25C.6D.6256 .查找n个元素的有序表时，最有效的查找方法是【C】。A.顺序查找B.分块查找C.折半查找D.二叉排序

39、树7 .如果要求一个查找表既能快速查找，又能适应动态变化的要求，可以采用A查找方法。A.分块B.顺序C.折半D.散列8 .在关键字随机分布的情况下，用二叉排序树的方法进行查找，其查找长度与B量级相当。A.顺序查找B.折半查找C.分块查找D.前三个都不正确9 .查找效率最高的二叉排序树是【C】。A.所有结点的左子树都为空的二叉排序树B.所有结点的右子树都为空的二叉排序树C.平衡二叉树D.没有左子树的二叉排序树10 .假定有k个关键字互为同义词，若用线性探测再散列法把这k个关键字的纪录插入到散列表中，至少要进行D次探测。A.k-1B.kC.k+1D.k(k+1)/211 .以下说法错误的是【BA.

40、散列法存储的基本思想是由记录关键字决定数据存储地址B.散列法的结点中只包含数据元素自身的信息，不包含任何指针C.装填因子是散列法的一个重要参数，它反映了散列表的装填程度D.散列表的查找效率取决于散列造表是的散列函数和冲突处理的方法12 .散列表的平均查找长度【A】。A.与冲突处理方法有关而与表的长度无关B.与冲突处理方法无关而与表的长度有关C.与冲突处理方法有关且与表的长度有关D.与冲突处理方法无关且与表的长度无关二、判断题V1.顺序查找法适合于顺序或链式存储结构的查找表。【X】2.顺序查找法只能在顺序存储结构上进行。【X】3.二分查找可以在有序的双向链表上进行。【X】4.在二叉排序树中，每个

41、结点的关键字比左孩子的关键字大，比右孩子的关键字小。【X】5.每个结点的关键字都比左孩子的关键字大，比右孩子的关键字小，这样的二叉树都是二叉排序树。【V6.哈希存储法只能存储数据元素的值，不能存储数据元素之间的关系。【X】7.哈希冲突是指同一个关键字对应多个不同的哈希地址。三、填空题1 .顺序查找含n个元素的顺序表，若查找成功，则比较关键字的次数最多为_次;若查找不成功，则比较关键字的次数为n+1次。2 .在含有n个元素的有序顺序表中进行二分查找，最大的比较次数星.log2n+1。3 .用二分查找一个查找表，该查找表必须具有的特点是顺序存储且关键字有ff。4 .分块查找发将待查找的表均匀地分成

42、若干块且块中诸记录的顺序可以是任意的，但块与块之间关键享有序。5 .在分块查找方法中，首先查找关键字表，然后再查找相应的对应的6 。6 .用二叉排序树在n个元素中进行查找，最坏情况下查找时间复杂度为O(n),最好情况的查找时间复杂度为O(log2n)。7 .折半查找的存储结构仅限于顺序存储结构，且是关键字有序排。8 .一个无序序列可以通过构造一棵二叉排序树而变成有序序列,构造树的过程即是对无序序列进行排序的过程。9 .用二叉排序树查找，在最坏的情况下，平均查找长度为(n+1)/2,最好的情况下，平均查找长度为.(log2n+1)-1o10 .在哈希函数H(key)=key/p中，p最好取小于或

43、等于m的最大质数。11 .哈希表是通过将关键字按选定的哈希函数和冲突处理方法，把记录按关键字转换为地址进行存储的存储表，哈希方法的关键是选择好的哈希函数和冲突处理的方法。一个好的哈希函数其转换地址应尽可能均匀,而且函数运算应尽可能简单。四、解答题1、画出对长度为10的右序表进行折半查找的一棵判定树，并求其等概率时查找成功的平均查找长度。平均查找长度=(1+2*2+4*3+3*4)/10=2.92、设有数据集合d=1,12,5,8,3,10,7,13,9,回答下列问题:依次取d中各数据，构造一棵二叉排序树bt;如何依据此二叉排序树得到d的一个有序序列。答：构造的二叉排序树如下图所示。对该二叉排序树进行中序遍历，就可以得到d的一个有序序列:1,3,5,7,8,9,10,12,133.若对具有n个元素的有序的顺序表和无序的顺序表分别