《数据结构题集答案.pdf》由会员分享，可在线阅读，更多相关《数据结构题集答案.pdf（42页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、数据结构题集第一章绪论一、单选题1. 在数据结构中，从逻辑上可以把数据结构分成【 C 】 。 A. 动态结构和静态结构 B.紧凑结构和非紧凑结构 C. 线性结构和非线性结构 D. 内部结构和外部结构2. 数据结构在计算机内存中的表示是指【 A 】 。 A. 数据的存储结构 B.数据结构 C. 数据结构的逻辑结构 D.数据元素之间的关系3. 【 A 】是数据的最小单位， 【 B 】是数据的基本单位。A.数据项 B.数据元素 C. 信息项 D.表元素4. 计算机所处理数据一般具有某种内在联系，这是指【 B 】 。A.数据与数据之间存在某种关系 B.数据元素与数据元素之间存在某种关系 C. 元素内部
2、存在某种结构 D.数据项与数据项之间存在某种关系5. 算法分析的目的是【 C 】 。 A. 找出数据结构的合理性 B.研究输入和输出的关系 C. 分析算法的效率以求改进 D. 分析算法的易懂性6. 在存储数据时，不仅要考虑存储各数据元素的值，而且还要存储【 C 】 。 A.数据处理的方法 B.数据元素的类型 C.数据元素之间的关系 D.数据的存储方法7. 算法分析的主要任务是分析【 D 】 。 A. 算法是否具有较好的可读性 B. 算法中是否存储语法错误和逻辑错误 C. 算法的功能是否符合设计要求 D. 算法的执行时间与问题规模之间的关系。8. 数据的运算【 A 】 。 A. 效率与采用何种存
3、储结构有关 B. 是根据存储结构来定义的 C. 有算术运算和关系运算两大类 D. 必须用程序设计语言来描述9. 算法的计算量的大小称为算法的【 B 】 。 A. 效率 B.时间复杂度 C.现实性 D. 难度10. 连续存储分配时，存储单元的地址【A 】 。 A. 一定连续 B.一定不连续 C. 不一定连续 D. 部分连续，部分不连续二、判断题1. 数据元素是数据结构的最小单位【. 】 。 2.数据的逻辑结构说明数据元素之间的顺序关系，它依赖于计算机的存储结构【 . 】 。 3.数据的逻辑结构指数据元素的各数据项之间的逻辑关系【. 】 。 4.算法的优劣与算法的描述语言无关，但与使用的计算机有关
4、【. 】 。 5.数据结构的抽象操作的定义与具体实现有关【. 】 。三、填空题1. 数据的逻辑结构指数据元素之间的逻辑关系。2. 一个数据结构在计算机中的表示称为存储结构。3. 数据的物理结构主要包括顺序存储结构的表示和链式存储结构的表示。 4.数据逻辑结构包括集合、线性结构、树和图四种，树结构和图结构统称为非线性结构。 5.顺序存储方法把逻辑上逻辑上相邻的元素存储在物理位置相邻的存储单元里；链式存储方法中结点间的逻辑关系是由指针域表示的。 6 、数据结构研究的是逻辑结构和 物理结构以及它们之间的相互关 系 ， 并 对 于 这 种 结 构 定 义 相 应 的运 算， 设 计 出 相 应 的算法
5、。 7.算法的执行时间是问题规模 n 的函数。 8.以下是4 个算法所有语句频度之和的表达式，其中的复杂度相同的是 A和 B 。 A.TA(n)=2n3+3n2+1000 B.TB(n)=n3-n2log2n-1000 C.TC(n)=n2log2n+n2 D.TD(n)=n2+1000 四、解答题 1.简述数据的逻辑结构和存储结构的关系。答：在数据结构中，逻辑结构和存储结构是密切相关的，存储结构不仅将数据元素存储到计算机中，而且还要表示各数据元素之间的逻辑关系。逻辑结构与计算机无关，存储结构是数据元素之间的关系在计算机中的表示。通常情况下，一种逻辑结构可以有多种存储结构，例如，线性结构可以采
6、取顺序存储结构或链式存粗结构表示。 2.数据结构和数据类型有什么区别？答：数据结构是相互间存在一种或多种特定关系的数据元素的集合，一般包括三个方面的内容：数据的逻辑结构、存储结构和多数据的运算。数据类型是一个值得集合和定义在这个值集上的一组操作的总称。数据结构重点考虑元素之间的关系，数据类型重点考虑数据的个体特征。 3.当为解决某一问题已经选定其数据的逻辑结构后，选择数据的存储结构时，应从哪些方面考虑？答：通常从两个方面考虑：第一是算法实现的存储空间复杂度；第二是算法执行的时间复杂度。若存储空间难以确定，宜选择链式存储结构，否则选择顺序存储结构。若插入、删除操作频繁，则选链式存储结构，否则选择
7、顺序存储结构。第二章线性表一、单选题1. 链表不具备的特点是【 A 】 。 A. 可随机访问任一结点 B.插入删除不需要移动元素 C. 不必事先估算存储空间 D. 所需空间与其长度成正比2. 设线性表有n 个元素，以下操作中， 【 A 】在顺序表上实现比在链表上实现效率更高。 A.输出第 i （1i n）个元素的值 B.顺序输出这 n 个元素 C.交换第 1 个与第 2 个元素的值 D.输出与给定值x 相等的元素在线性表中的序号3. 如果最常用的操作是取第i 个结点及其前驱，则采用【 D 】存储方法最节省时间。 A.单链表 B.双链表 C.线性链表 D. 顺序表4. 线性表是具有n 个【 C
8、】的有限序列（ n0） 。 A.表元素 B.字符 C.数据元素 D. 数据项5. 下面关于线性表的叙述中，错误的是【 B 】 。 A. 线性表采用顺序存储，则必须占用一片连续的存储单元 B. 线性表采用顺序存储，则便于插入和删除操作 C. 线性表采用链式存储，则不必占用一片连续的存储单元 D. 线性表采用链式存储，则便于插入和删除操作6. 线性表的顺序存储结构是一种【 A 】 。 A.随机存取的存储结构 B. 顺序存取的存储结构 C.索引存取的存储结构 D.Hash 存取的存储结构7. 单链表中增加一个头结点的目的是为了【 C 】 。 A.使单链表至少有一个结点 B.标识表首结点的位置 C.方
9、便运算的实现 D.说明单链表是线性表的链式存储8. 不带头结点的单链表（头指针为h）为空的条件是【 A 】 。 A.h=NULL B.h-next=NULL C.h-next=h D.h!=NULL 9. 带头结点的单链表（头指针为h）为空的条件是【 B 】 。 A.h=NULL B.h-next=NULL C.h-next=h D.h!=NULL 10. 带头结点的循环双向链表（头指针为L）为空的条件是【 D 】 。 A.L=NULL B.L-next-prior=NULL C.L-prior=NULL D.L-next=L 11. 非空的循环单链表（头指针为head）的尾结点（由p 指向）
10、满足【 C 】 。 A.p-next=NULL B.p=NULL C.p-next=head D.p=head 12. 设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用【 A 】最节省时间。 A.带头结点的双循环链表 B.单循环链表 C.带尾指针的单循环链表 D.单链表13. 若某线性表最常用的操作存取任意指定序号的元素和在表尾进行插入和删除，则选用【 A 】的存储方式最节省时间。 A.顺序表 B.双链表 C.带头结点的双循环链表 D.单循环链表14. 在 n个结点的线性表的顺序实现中，算法的时间复杂度为O(1) 的操作是【 A】 。 A.访问第 i 个结点和求第i 个结点的直接前驱
11、 B.在第 i 个结点后插入一个新结点 C.删除第 i 个结点 D.以上都不对15. 若长度为 n 的线性表采用顺序存储结构，在第i 个位置插入一个新元素的算法的时间复杂度为【 C 】 。 A.O(0) B.O(1) C.O(n) D.O(n2) 16. 对于顺序存储的线性表，访问结点和增加、 删除结点的时间复杂度为【 C 】 。 A.O(n)O(n) B.O(n)O(1) C.O(1)O(n) D.O(1)O(1) 17. 线性表以链式方式存储，访问第i 个结点的时间复杂度为【 C 】 。 A.O(i) B.O(1) C.O(n) D.O(i-1) 18. 循环链表 H尾结点 p 的特点是【
12、 A 】 。 A.p-next=H B.p-next=H-next C.p=H D.p=H-next 二、判断题【 】1. 取线性表的第i 个元素的时间同i 的大小有关。【 】2. 线性表中每个元素都有一个直接前驱和一个直接后继。【 】3. 顺序存储方式只能用于存储线性结构。【 】4. 线性表采用链式存储时，结点和结点内部的存储空间可以不连续。【 】5. 在一个设有头指针和尾指针的单链表中，执行删除单链表最后一个结点的操作与链表的长度无关。三、填空题1. 向一个长度为n 的顺序表中的第i 个元素之前插入一个元素时，需要向后移动 n-i+1 个元素。 2. 在一个长度为n 的顺序表中删除第i 个
13、元素时，需要向前移动 n-i 个元素。 3.在单链表中设置头结点的作用是简化插入、删除算法。 4.在单链中要删除某一指定结点，必须找到该结点的直接前驱结点。 5. 访问单链表中的结点，必须沿着指针域依次进行。 6.在双链表中每个结点有两个指针域，一个指向直接前驱结点，一个指向 直接后继结点。 7.在双向循环链表中，删除最后一个结点的算法时间复杂度为O(1)。 8.访 问 一 个 线 性 表 中 具 有 给 定 值 的 时 间 复 杂 度 的 数 量 级 是O(n) 。 9.由 n 个数据元素生成一个顺序表，若每次都调用插入算法把一个元素插入到表头，则整个算法的时间复杂度为 O(n) ，若每次都
14、调用插入算法把一个元素插入到表尾，则整个算法的时间复杂度为 O(n2) 。 10. 在双向链表中，可以用表尾指针代替表头指针。 11.根据 n 个数据元素建立对应的顺序表和单链表存储结构，其算法的时间复杂度最好的情况是 O(n) ，最坏的情况是 O(n2) 。 12.求线性表的顺序存储和链式存储的长度的算法时间复杂度分别是 O(1) 和 O(n) 。 13.在一个带头结点的单链表中，在表头插入或删除与在其他位置插入或删除，其操作过程是否相同？相同。14. 在一个不带头结点的单链表中，在表头插入或删除与在其他位置插入或删除，其操作过程是否相同？不相同。四、简答题1. 阐述顺序表和链表存储方式的特
15、点。答：顺序表存储方式为数据分配连续的存储单元，数据元素按逻辑顺序依次存储到相应存储单元中，使得逻辑相邻的数据元素物理也相邻，因此可以实现随机访问线性表的数据元素，即数据访问的时间复杂度为O(1) 。链表存储方式分配的存储单元可以不连续，通过每个结点的指针域来表示数据元素之间的逻辑关系，只能顺序访问线性表中的数据元素。2. 若频繁地对一个线性表进行插入和删除操作，则该线性表宜采用何种存储结构，为什么？答：若频繁地对一个线性表进行插入和删除操作，则该线性表宜采用链式存储结构。因为链式存储结构在插入和删除数据元素时不需要移动数据元素，只需要修改结点的指针域就可以改变数据元素之间的逻辑关系。 3.在
16、单链表、双向循环链表和单循环链表中，若仅知道指针p 指向某结点，不知道头指针，能否将结点p 从相应的链表中删除？若可以，时间复杂度各为多少。答：要实现删除p 结点的操作，必须找到其前驱结点，修改其指针域的值使其指向 p 的后继结点，以实现删除结点p。单链表不行，因为不知道头指针就无法找到结点p 的前驱结点。双向循环链表和单循环链表可以可以实现删除p结点。单循环链表删除p 结点的时间复杂度为O(n) ，双循环链表删除P 结点的时间复杂度为O(1) 。4. 对链表设置头结点的作用是什么？答：对带头结点的链表，在表的任何结点之前插入结点或删除任何位置的结点，所要做的都是修改前一个结点的指针域，因为在
17、带头结点的链表中任何元素结点都有前驱结点。如果没有头结点，在首元结点前插入结点或删除首元结点都要修改头指针，其算法要比带头结点的算法复杂些。其次，带头结点的链表结构，初始化后的头指针就固定了，除撤销算法外，所有算法都不会修改头指针，可以减少出错的可能性。五、算法设计题1. 已知一个线性表用含头结点的单链表做存储结构，写一个算法求单链表的长度。解：算法基本思想：从头结点的下一个结点开发，遍历单链表的每个结点，每遇到一个结点，结点计算器加1。int listlenght(linklist L) int length=0; P=L-next; while(p) length+; p=p-next;
18、return(length); 2. 已知一个顺序表L，其中的元素按值递增有序排列，设计一个算法插入一个值为 x 的元素后保持该顺序表仍然递增有序，且空间复杂度为0（1） 。void insertsq(sqlist L,elemtype x) n=L.length-1; while(n=0<(x,L.elemn) L.elemn+1=L.elemn; n-; L.elemn+1=x; L.lenght+; return; 3. 写一个算法，从顺序表中删除值为x 的所有元素。 void delallsq(Sqlist &L) int i=0,j=0; while(jnext=Q.rear 。
19、10. 如果栈的最大长度难以估计，最好使用链栈。四、简答题1. 为什么说栈是一种后进先出表？答：因为栈是限定在表的一端进行插入和删除操作，所以后入栈的数据元素总是先出栈，所以说栈是一种后进先出表。2. 对于一个栈，其输入序列是A,B,C, 试给出全部可能的输出序列。答：可能的出栈序列是：ABC 、ACB 、BAC 、BCA 、CBA 。3. 何谓队列上溢？何为假溢出现象？有哪些解决假溢出问题的方法，并分别阐述其工作原理。答：队列上溢指在队列的顺序存储分配中，所有单元中已有元素，再进行插入操作时称为队列上溢。假溢出指在队列的顺序存储分配中，分配给队列的存储空间有存储单元未被占用，但按照操作规则而
20、使进队的数据元素无法进队的现象。解决假溢出问题的方法是在队列的顺序存储分配中，分配给队列的存储空间可以循环使用，其进本原理是用表示队头和队尾指针与分配给队列的存储空间长度进行取模运算。即：入队操作： Q.rear=(Q.rear+1)%MSize 出队操作： Q.front=(Q.front+1)%MSize 4. 队列可以用单循环链表来实现，故可以只设一个头指针或只设一个尾指针，请分析用哪种方案最合适。答：使用循环链表来表示队列，设置尾指针比较合适，因为入队操作可以直接在尾结点后进行插入操作，出队操作时可以根据尾指针很容易找到链表的头结点，入队出队操作的算法时间复杂度均为O(1) 。若只设头
21、指针，则出队操作的算法时间复杂度为O(1)，入队操作的算法时间复杂度为O(n) 。5. 简述线性表、栈和队列的异同？答：栈和队列都是操作位置受限的线性表，即对插入和删除操作的位置加以限制。栈是仅允许在表的一端进行插入和删除操作的线性表，因而是后进先出表。队列是允许在表的一端进行插入，在表的另一端进行删除的线性表，因而是先进先出表。线性表可以在任何位置进行插入和删除操作。五、算法设计题 1.设计一个算法，利用栈和队列的基本运算将指定栈中的元素顺序逆转。解：算法基本思想：先将栈中元素出栈运算移至队列中，再将队列中元素出队列移至栈中。void reverse(Stack &st) Queue sq；
22、 ElemType x; InitQueue(sq) while(!StackEmpty(st) pop(st,x) EnQueue(sq,x); while(!QueueEmpty(sq) DeQueue(sq,x); Push(st,x); DestroyQueue(sq); 2.设计一个算法，利用栈的基本运算返回指定栈中栈底元素。解：先将栈中元素依次移至另一个临时栈中，最后一个元素即为栈底元素，设为 x. 。再将临时栈中元素移至原栈中，即恢复栈内容。ElemType bottom(Stack &st) ElemType x,y; Stack tmpst; InitStack(tmpst)
23、 while(!StackEmpty(st) pop(st,x) push(tmpst,x); while(!QueueStack(temst) pop(tmpst,y); /此时必须用另一个变量y，才能保留栈底元素在 x 中 Push(st,y); DestroyStack(tmpst); return(x); 3.设计一个算法，利用栈来实现带头结点的单链表h 的逆序。解：算法基本思想：将单链表结点依次放入链栈中，链栈本身就是一个单链表，即实现了原单链表的逆序。假设链栈不带头结点，再加上原来的头结点，就完成了原单链表的逆序。Void revert(SNode *h) SNode *st=NU
24、LL,*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. 串是一种特殊的线性表，其特殊性体现在【 B 】 。 A. 可以顺序存储 B.数据元素是一个字符C.数据元素可以使多个字符 D.可以链接存储3. 两个串相等必有串长度相等且【 B 】 。 A. 串的各位置字符任意 B.串中各位置字符均对应相等C.两个串含有相同的字符 D.两个串所含字符任意4. 设有两个串 p 和 q，求
25、 q 在 p 中首次出现的位置的运算称着【 B 】 。 A. 连接 B.模式匹配C.求子串 D.求串长二、填空 1. 空串是长度为 0 的串。 2. 一个串中任意连续字符组成的子序列称为该串的子串。 3. 设 s= “abcd” ， 则执行语句s2=Substr(s,2,2)后，s2= “bc”。 4. 空白串是由一个或多个空格字符组成的串，其长度等于其所包含的空格字符的个数。第五章数组一、单选题1. 一维数组与线性表的区别是【 A 】 。 A. 前者长度固定，后者长度可变 B. 后进长度固定，前者长度可变 C. 两者长度均固定 D.两者长度均可变2. 多维数组的数组元素之间的关系，【 A 】
26、 。 A. 是线性的 B. 是树型的 C. 既是线性的，又是树型的 D. 既不是线性的，也不是树型的3. 设有数组 A810，每个元素占3 个存储单元，存放该数组的存储单元数为【 C 】 。 A.80 B.100 C.240 D.270 4. 设有数组 A810，每个元素占3 个存储单元，首地址为SA，则元素 75的起始地址是【 D 】 。 A.SA+141 B.SA+144 C.SA+222 D.SA+225 5. 设有一个 n*n 的对称矩阵，采用压缩存储，则存入内存的元素个数为【 C 】 。 A.n*n B.n*n/2 C.n*(n+1)/2 D.(n+1)2/2 6. 设 A是一个 n
27、*n 的对称矩阵， 压缩存储到一个一维数组B0.n(n+1)/2-1中，则下三角部分元素ai,j在 B中的位置是【 A 】 。 A. i(i-1)/2+j-1 B. i(i-1)/2+j C. i(i+1)/2+j-1 D. i(i+1)/2+j 7. 稀疏矩阵一般的压缩方法有两种，即【 C 】 。 A. 二维数组和三维数组 B. 三元组和散列 C. 三元组和十字链表 D.散列和十字链表8. 设有一个 10*10 的对称矩阵 A，以行主次序进行压缩存储，每个元素占一个存储单元， a1,1的地址是 1，则 A8,5 的起始地址是【 B 】 。 A.13 B.33 C.18 D.40 二、解答题
28、1.设数组 A5080，其基地址为2000，每个元素占2 个存储单元，以行序位主序顺序存储，回答下列问题：（1）该数据组由多少元素？（2）该数组占用多少存储单元？（3）数组元素 a3030的存储地址是多少？答：（1）该数组有： 50*80=4000 个元素（2）该数组占用4000*4=8000 个存储单元（3）loc(30,30)=2000+(30*80+30)*2=2000+4860=6860 第六章树与二叉树一、单选题1. 有关二叉树下列说法正确的是【 B 】 。 A. 二叉树的度为2 B.一棵二叉树的度可以小于2 C. 一棵二叉树至少有一个结点的度为2 D.二叉树中任何一个结点的度为 2
29、 2. 利用二叉链表存储树，则根结点的右指针是【 C 】 。 A. 指向最左孩子 B.指向最右孩子 C. 空 D.非空3. 若一棵二叉树具有10 个度为 2 的结点， 5 个度为 1 的结点，则度为0 的结点个数为【 B 】 。 A.9 B.11 C.15 D.不确定4. 一棵二叉树有1001 个结点，其中叶结点的个数为【 D 】 。 A.250 B.490 C.254 D.不确定5. 一棵完全二叉树有1001 个结点，其中叶结点的个数为【 D 】 。 A.250 B.500 C.254 D.以上答案均不对6. 一棵具有 1025 个结点的二叉树的高h 为【 C 】 。 A.11 B.11 C
30、.11至 1025 之间 D.10至 1024 之间7. 一棵 124 个叶结点的完全树，最多具有【 B 】个结点。 A.247 B.248 C.249 D.251 8. 一棵具有 10 个叶结点的二叉树具有【 B 】度为 2 的结点。 A.8 B.9 C.10 D.11 9. 已知一棵完全二叉树有625 个结点，叶结点的个数为【 C 】 。 A.311 B.312 C.313 D.其它10. 一棵具有 n 个结点的完全二叉树的高h 为【 AB】 。 A.log2n+1 B.log2n+1 C.log2n+1 D.log2n-111. 由 8 个权值构造一棵哈夫曼树，该哈夫曼树有【 A 】个结
31、点。 A.15 B.16 C.17 D.14 12. 由 3 个结点可以构造【 D 】种不同的二叉树。 A.2 B.3 C.4 D.5 13. 树最适合用来表示【 C 】 。 A. 有序数据元素 B.无序数据元素 C. 元素间具有分支层次关系的数据 D.元素间无联系的数据14. 下图中 4 棵二叉树中，【 C 】不是完全二叉树。 A. B. C. D. 15. 某二叉树的先序遍历序列和后序便利序列正好相反，则该二叉树一定是【 A 】 。 A. 空或只有一个结点 B.完全二叉树 C. 二叉排序树 D.高度等于其结点数 16. 在一棵非空二叉树的中序遍历序列中，根结点的右边【 A 】 。 A. 只
32、有右子树上的所有结点 B.只有右子树上的部分结点 C. 只有左子树上的部分结点 D.只有左子树上的所有结点 17. 任何一棵二叉树的叶子结点在先序、中序和后序遍历序列中的相对次序【 A 】 。 A. 不发生上改变 B.发生改变 C. 不能确定 D.以上都不对 18. 一棵满二叉树， m个叶结点， n 个结点，深度为h，则【 D 】 。 A.n=h+m B.h+m=2n C.m=h-1 D.n=2 h-1 19. 设 n， m是二叉树上的两个结点， 在中序遍历时， n 在 m之前的条件是 【 C 】 。 A.n在 m右方 B.n是 m的祖先 C.n在 m左方 D.n是 m的子孙20. 设高度为
33、h 的二叉树上只有度为0 和度为 2 的结点，则此类二叉树中包含的结点数最少为【 B 】 。 A.2h B.2h-1 C.2h+1 D.h+1 二、判断题【 】1. 二叉树是一般树的特殊树型。【 】2. 树与二叉树是两种不同的树形结构。【 】3. 对于有 n 个结点的二叉树，其高度为log2n。【 】4. 完全二叉树中，若一个没有左孩子，则它必定是叶结点。【 】5. 一棵具有 n 个结点的完全二叉树，从上到下、从左到右用自然数对结点进行编号，结点为i 的结点的左孩子的编号为2i(2ilchild=NULL&p-rchild=NULL 。10. 二叉树的先序序列和中序序列相等的条件是任何结点至多
34、只有右子树。11. 有一棵如下图所示的树，回答下列问题：这棵树的根结点是 a 。这棵树的叶子结点是 b,e,g,d 。结点 c 的度为 2 。这棵树的深度是 4 。结点 c 的孩子结点是 e,f 。结点 c 的双亲结点是 a 。这棵树的度是 3 。12. 树与二叉树的两个主要差别是树中结点的最大度没有限制，二叉树结点的最大度限定为2 、 树的结点无左右之分，二叉树的的结点有左右之分。13. 树中任一结点允许有 0个或多个孩子个孩子结点，除根结点之外，其余结点有 1 个双亲结点。a b c d e f g 四、简答题1. 设有如下图所示的二叉树，给出其前序、中序和后序遍历结果。答： 前序序列：
35、eadcbifghj 中序序列： abcdiefhgj 后序序列： bcidahjgfe 2. 给出下图所示的树的二叉树表示。e a f d i g c j b h 答：下图为其树的二叉树表示。3. 有一份电文共有5 个字符： a,b,c,d,e,它们出现的频率依次为4，7，5，2，9，构造对应的哈夫曼树，求哈夫曼树的带权路径长度和每个字符的哈夫曼编码。字符编码： a：011 b：10 c：00 d：010 e：11 4. 假设一棵二叉树采用顺序存储结构，如下图所示。0 5 10 15 20 e a f d i g c j b h k e a d f c b h g i j k 11 7 9
36、5 6 4 2 16 27 e a f d g c j h i b 回答些列问题：画出二叉树表示。写出先序、中序和后序遍历结果写出结点 c 的双亲结点和左、右孩子结点画出此二叉树还原成森林的图答：二叉树表示如下图所示。先序序列为： eadcbjfghi 中序序列为： acbdjefhgi 后序序列为： bcjdahigfe 结点 c 的双亲结点是d，左孩子为b，无右孩子该二叉树对应的森林为a e f d j h b g c i a e f d j h b g c i 第七章图一、单选题1. 在一个无向图中，所有顶点的度数之和等于所有边的【 C 】倍。 A.1/2 B.1 C.2 D.4 2.
37、在一个有向图中，所有顶点的入度数之和等于所有顶点的出度之和的【 B 】倍。 A.1/2 B.1 C.2 D.4 3. 一个有 n 个顶点的无向图最多有【 C 】条边。 A.n B.n(n-1) C.n(n-1)/2 D.2n 4. 具有 4 个顶点的无向完全图有【 A 】条边。 A.6 B.12 C.16 D.20 5. 具有 6 个顶点的无向图至少应有【 A 】条边才能确保是一个连通图。 A.5 B.6 C.7 D.8 6. 一个有 n 个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是【 D 】 。 A.n B. (n-1)2 C. (n-1) D. n27. 对某个无向图的邻接矩阵来说
38、，【 A 】 。 A. 第 i 行上的非 0 元素个数等于第i 列上非 0 元素个数 B. 矩阵中非 0 元素个数等于图中的边数 C. 第 i 行、第 i 列上非 0 元素个数等于顶点vi 的度数 D. 矩阵中非全 0 行的行数等于图中的顶点数8. 对于一个具有n 个顶点和e 条边的无向图，若采用邻接表表示，则表头向量的大小为【 A 】 ；所有邻接表中结点总数为【 C 】 。A.n B.n+1 C.n-1 D.n2 A.e/2 B.e C.2e D.n+e 二、判断题【 】1.n 个顶点的无向图至多有n(n-1) 条边。【 】2. 有向图中，各顶点的入度之和等于各顶点的出度之和。【 】3. 邻
39、接矩阵只存储了边的信息，没有存储顶点的信息。【 】4. 连通分量是无向图的极小连通子图。【 】5. 如果表示有向图的邻接矩阵是对称的，则该有向图一定是完全有向图。【 】6. 如果表示图的邻接矩阵是对称的，则该图一定是无向图。【 】7. 如果表示图的邻接矩阵不是对称的，则该图一定是有向图。三、填空题1. 有 n 个顶点的无向图最多有 n(n-1)/2 条边。2. 具有 n 个顶点的强连通有向图至少有 n 条边。3. 具有 n 个顶点的有向图最多有 n(n-1) 条边。4. 一个图的临接矩阵表示法是唯一的，而邻接表表示法是不唯一的。 5.具有 10 个顶点的无向图，边的总数最多为 45 。 6.在
40、有 n 个顶点的有向图中，每个顶点的度最大可达 n-1 。7. 已知一个有向图采用邻接矩阵表示，计算第i个顶点的入度的方法是求第 i 列非 0 元素个数。8. 已知一个有向图的邻接矩阵表示，删除所有从第i 个结点出发的弧的方法是将第 i 行对应的 1 置成 0 。9. 对于 n 的顶点的无向图，采用邻接矩阵表示，求图中边的方法是计算邻接矩阵中元素值为1 的个数，判断任意两个顶点是否有边相连的方法是判断对应邻接矩阵元素的值是否为1，再除以 2 ，求任意顶点的度的方法是求邻接矩阵中对应顶点所在行值为1 的元素个数。10. 对于 n 的顶点的有向图，采用邻接矩阵表示，求图中边的方法是计算邻接矩阵中元
41、素值为1 的个数，判断任意两个顶点是否有边相连的方法是判断对应邻接矩阵元素的值是否为1 ，求任意顶点的度的方法是求邻接矩阵中对应顶点所在行和列的元素值为1 的个数。11. 无向图的连通分量指无向图中最大连通子图。12. 若无向图有 m条边， ，则表示该无向图的邻接表中有 2m 结点。四、简答题1. 从占用的存储空间来看，对于稠密图和稀疏图，采用邻接矩阵和邻接表那个更好些？答：从占用存储空间看，稠密图采用邻接矩阵更好，稀疏图采用邻接表更好。2. 用邻接矩阵表示图时，矩阵元素的个数与顶点个数是否相关？与边的条数是否相关？为什么？。答：用邻接矩阵表示图，矩阵元素的个数与图的顶点个数直接相关，与边的条
42、数无关。因为假设定点个数为n，则邻接矩阵的大小为n2。第九章查找一、单选题1. 顺序查找法适合于存储结构为【 B 】的查找表。 A. 散列存储 B.顺序存储或链式存储 C. 压缩存储 D.索引存储2. 对查找表进行折半查找时，要求查找表必须【 B 】 。 A. 以顺序方式存储 B. 以顺序方式存储，且结点按关键字有序排列 C. 以链式方式存储 D. 以链式方式存储，且结点按关键字有序排列3. 采用顺序查找法查找长度为n 的查找表时，每个元素查找的平均查找长度为【 C 】 。 A.n B.n/2 C.(n+1)/2 D.(n-1)/2 4. 采用折半查找法查找长度为n 的查找表时，每个元素查找的
43、平均查找长度为【 D 】 。 A.O(n2) B.O(nlog2n) C.O(n) D.O(log2n) 5. 采用分块查找时，若查找表中有625 个元素，查找每个元素的概率相同，假设对索引表和块都采用顺序查找，每块应分【 B 】个结点最佳。 A.10 B.25 C.6 D.625 6. 查找 n 个元素的有序表时，最有效的查找方法是【 C 】 。 A. 顺序查找 B.分块查找 C.折半查找 D.二叉排序树7. 如果要求一个查找表既能快速查找，又能适应动态变化的要求，可以采用【 A 】查找方法。 A. 分块 B.顺序 C.折半 D.散列8. 在关键字随机分布的情况下，用二叉排序树的方法进行查找
44、，其查找长度与【 B】量级相当。 A. 顺序查找 B.折半查找 C.分块查找 D.前三个都不正确9. 查找效率最高的二叉排序树是【 C 】 。 A. 所有结点的左子树都为空的二叉排序树 B. 所有结点的右子树都为空的二叉排序树 C. 平衡二叉树 D. 没有左子树的二叉排序树10. 假定有 k 个关键字互为同义词，若用线性探测再散列法把这k 个关键字的纪录插入到散列表中，至少要进行【 D 】次探测。 A.k-1 B.k C.k+1 D.k(k+1)/2 11. 以下说法错误的是【 B 】 。 A. 散列法存储的基本思想是由记录关键字决定数据存储地址 B. 散列法的结点中只包含数据元素自身的信息，
45、不包含任何指针 C. 装填因子是散列法的一个重要参数，它反映了散列表的装填程度 D. 散列表的查找效率取决于散列造表是的散列函数和冲突处理的方法12. 散列表的平均查找长度【 A 】 。 A. 与冲突处理方法有关而与表的长度无关 B. 与冲突处理方法无关而与表的长度有关 C. 与冲突处理方法有关且与表的长度有关 D. 与冲突处理方法无关且与表的长度无关二、判断题【 】1. 顺序查找法适合于顺序或链式存储结构的查找表。【 】2. 顺序查找法只能在顺序存储结构上进行。【 】3. 二分查找可以在有序的双向链表上进行。【 】4. 在二叉排序树中，每个结点的关键字比左孩子的关键字大，比右孩子的关键字小。
46、【 】5. 每个结点的关键字都比左孩子的关键字大，比右孩子的关键字小，这样的二叉树都是二叉排序树。【 】6. 哈希存储法只能存储数据元素的值，不能存储数据元素之间的关系。【 】7. 哈希冲突是指同一个关键字对应多个不同的哈希地址。三、填空题1. 顺序查找含n 个元素的顺序表，若查找成功，则比较关键字的次数最多为 n 次；若查找不成功，则比较关键字的次数为 n+1 次。 2.在含有n 个元素的有序顺序表中进行二分查找，最大的比较次数是 .log2n+1 。 3.用二分查找一个查找表，该查找表必须具有的特点是顺序存储且关键字有序。 4.分块查找发将待查找的表均匀地分成若干块且块中诸记录的顺序可以是
47、任意的，但块与块之间关键字有序。 5.在分块查找方法中，首先查找关键字表，然后再查找相应的对应的块。 6.用二叉排序树在n 个元素中进行查找，最坏情况下查找时间复杂度为O(n) ，最好情况的查找时间复杂度为 O(log2n) 。7. 折半查找的存储结构仅限于顺序存储结构，且是关键字有序排列。8. 一个无序序列可以通过构造一棵二叉排序树而变成有序序列， 构造树的过程即是对无序序列进行排序的过程。9. 用二叉排序树查找， 在最坏的情况下， 平均查找长度为（n+1）/2 ，最好的情况下，平均查找长度为 .(log2n+1)-1 。10. 在哈希函数H(key)=key/p中， p 最好取小于或等于m
48、 的最大质数。11. 哈希表是通过将关键字按选定的哈希函数和冲突处理方法， 把记录按关键字转换为地址进行存储的存储表，哈希方法的关键是选择好的哈希函数和 冲突处理的方法。一个好的哈希函数其转换地址应尽可能均匀，而且函数运算应尽可能简单。四、解答题 1 、画出对长度为10 的右序表进行折半查找的一棵判定树，并求其等概率时查找成功的平均查找长度。平均查找长度 =(1+2*2+4*3+3*4)/10=2.9 2 、设有数据集合d=1，12，5，8，3，10，7，13，9，回答下列问题： 依次取 d 中各数据，构造一棵二叉排序树bt ； 如何依据此二叉排序树得到d 的一个有序序列。2 5 8 1 3
49、7 4 9 6 10 答：构造的二叉排序树如下图所示。对该二叉排序树进行中序遍历，就可以得到d 的一个有序序列： 1，3，5，7，8，9，10，12，13 3. 若对具有n 个元素的有序的顺序表和无序的顺序表分别进行顺序查找，试在下列两种情况下分别讨论两者在等概率时的平均查找长度：查找不成功，即表中无关键字等于给定值k 的记录。查找成功，即表中有关键字等于给定值k 的记录。答：对无序表的顺序查找，需要进行n+1 次比较才能确定查找失败。对有序表的顺序查找，只要确定某个记录关键字不等于且大于给定k值， 就能确定查找失败， 即最少 1 次，最多 n+1次，平均查找长度为 （n+2）/2 。查找成功
50、，其平均查找长度均为（n+1）/2 ，有序表和无序表是一样的。7 1 12 9 8 3 13 5 10 第十章排序一、单选题1. 直接插入排序在最好的情况下的时间复杂度为【 A 】 。 A.O(n) B.O(nlog2n) C.O(n2) D.O(log2n) 2. 排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为1）中的元素进行比较，将其放入已排序序列的正确位置的方法，称为【 B 】 。 A. 冒泡排序 B. 插入排序 C. 选择排序 D. 归并排序3. 在待排序的元素序列基本有序的前提下，效率最高的排序方法是【 A 】 。 A. 插入排序 B. 选择排序 C.快速排序 D. 归