数据结构题集答案

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. 元素内部存在某种结构D.数据项与数据

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

3、运算两大类D. 必须用程序设计语言来描述9. 算法的计算量的大小称为算法的【 B 】。A. 效率 B. 时间复杂度 C. 现实性 D. 难度10. 连续存储分配时，存储单元的地址【 A 】。A. 一定连续 B. 一定不连续C. 不一定连续 D. 部分连续，部分不连续二、判断题1. 数据元素是数据结构的最小单位【 X】。2. 数据的逻辑结构说明数据元素之间的顺序关系，它依赖于计算机的存储结构【X .】。3. 数据的逻辑结构指数据元素的各数据项之间的逻辑关系【X .】。. X 】。4. 算法的优劣与算法的描述语言无关，但与使用的计算机有关【5. 数据结构的抽象操作的定义与具体实现有关【.X】。三、

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

5、A.TA（n）=2n 3+3n2+1000B.TB（n）二n 3-n2log 2n-10002 2 2C.Tc(n)=n log 2n+nD.TD(n)=n +1000四、解答题1. 简述数据的逻辑结构和存储结构的关系。答：在数据结构中，逻辑结构和存储结构是密切相关的，存储结构不仅将数据元素存储到计算机中，而且还要表示各数据元素之间的逻辑关系。逻辑结 构与计算机无关，存储结构是数据元素之间的关系在计算机中的表示。通常情 况下，一种逻辑结构可以有多种存储结构，例如，线性结构可以采取顺序存储 结构或链式存粗结构表示。2. 数据结构和数据类型有什么区别？答：数据结构是相互间存在一种或多种特定关系的数

6、据元素的集合，一般 包括三个方面的内容：数据的逻辑结构、存储结构和多数据的运算。数据类型 是一个值得集合和定义在这个值集上的一组操作的总称。数据结构重点考虑元 素之间的关系，数据类型重点考虑数据的个体特征。3. 当为解决某一问题已经选定其数据的逻辑结构后，选择数据的存储结构 时，应从哪些方面考虑？答：通常从两个方面考虑：第一是算法实现的存储空间复杂度；第二是算法 执行的时间复杂度。若存储空间难以确定，宜选择链式存储结构，否则选择顺 序存储结构。若插入、删除操作频繁，则选链式存储结构，否则选择顺序存储 结构第二章 线性表、单选题1. 链表不具备的特点是【 A 】。A. 可随机访问任一结点 B.

7、插入删除不需要移动元素C. 不必事先估算存储空间 D. 所需空间与其长度成正比2. 设线性表有 n 个元素，以下操作中， 【 A 】在顺序表上实现比在链表上实现 效率更高。A. 输出第i (1< i < n)个元素的值B. 顺序输出这 n 个元素C. 交换第 1 个与第 2 个元素的值D. 输出与给定值 x 相等的元素在线性表中的序号3. 如果最常用的操作是取第 i 个结点及其前驱，则采用【 D 】存储方法最节省 时间。A. 单链表 B. 双链表 C. 线性链表 D. 顺序表4. 线性表是具有门个【C】的有限序列(n 0)。A. 表元素 B. 字符 C. 数据元素 D. 数据项5.

8、 下面关于线性表的叙述中，错误的是【 B 】。A. 线性表采用顺序存储，则必须占用一片连续的存储单元B. 线性表采用顺序存储，则便于插入和删除操作C. 线性表采用链式存储，则不必占用一片连续的存储单元D. 线性表采用链式存储，则便于插入和删除操作6. 线性表的顺序存储结构是一种【 A 】A. 随机存取的存储结构 B. 顺序存取的存储结构C. 索引存取的存储结构 D.Hash 存取的存储结构7. 单链表中增加一个头结点的目的是为了【 C 】。A. 使单链表至少有一个结点 B. 标识表首结点的位置C. 方便运算的实现D. 说明单链表是线性表的链式存储8. 不带头结点的单链表（头指针为h）为空的条件

9、是【A】A.h=NULL B.h->next=NULLC.h->next=h D.h!=NULL9. 带头结点的单链表（头指针为h）为空的条件是【B】A.h=NULL B.h->next=NULLC.h->next=h D.h!=NULL10. 带头结点的循环双向链表（头指针为L）为空的条件是【D】A.L=NULL B.L->next->prior=NULLC.L->prior=NULL D.L->next=L11. 非空的循环单链表（头指针为head）的尾结点（由p指向）满足【C】A.p->next=NULL B.p=NULLC.p-&g

10、t;next=head D.p=head12. 设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用【A 】最节省时间。A. 带头结点的双循环链表 B. 单循环链表C. 带尾指针的单循环链表 D. 单链表13. 若某线性表最常用的操作存取任意指定序号的元素和在表尾进行插入和删 除，则选用【 A 】的存储方式最节省时间。A. 顺序表 B. 双链表C. 带头结点的双循环链表 D. 单循环链表14. 在n个结点的线性表的顺序实现中，算法的时间复杂度为 0(1)的操作是【A】A. 访问第 i 个结点和求第 i 个结点的直接前驱B. 在第 i 个结点后插入一个新结点C. 删除第 i 个结点 D.

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

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

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

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

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

16、作，必须找到其前驱结点，修改其指针域的值使其指向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;return(length);个算法插入一0（1）。2. 已知一个顺序表L,其中的元素按值递增有序排列，设 个值为 x 的元素后保持

18、该顺序表仍然递增有序，且空间复杂度为void insertsq(sqlist L,elemtype x) n=L.length-1;while(n>=0&&LT(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(j<L.length) if(L.elemj!=x)L.elemi+=L.elemj;j+;L.longth=i;第三章 栈和队列、单选题1

19、. 对于栈操作数据的原则是【 C 】。A. 先进先出 B. 后进后出C. 后进先出 D. 不分顺序2. 队列的先进先出特征是指【 A 】。A. 最后插入队列的元素总是最后被删除B. 当同时进行插入、删除操作时，总是插入操作优先C. 每当有删除操作时，总要先做一次插入操作D. 每次从队中删除的元素总是最早插入的元素3. 与顺序栈相比较，链栈有一个比较明显的优势是【A 】。A. 通常不会出现栈满的情况 B. 插入操作更容易实现C. 通常不会出现栈空的情况 D. 删除操作更容易实现4. 栈和队列的共同点是【 C 】。A. 都是先进先出 B. 都是后进后出C. 只允许在端点处进行插入和删除 D. 无共

20、同点5. 栈的特点是【B】队列的特点是【 A 】栈和队列都是【 C】若 入栈序列是1, 2, 3, 4 ,则【A】是不可能的出栈序列；若进队列的序列 是1，2，3，4,贝V【D】是可能的出队序列。 A. 先进先出 B. 后进先出 C. 进优先于出 D. 出优先于进 A. 顺序存储的线性结构 B. 链式存储的线性结构C. 限制存取点的线性结构 D. 限制存取点的非线性结构 A.3,2,1,4 B.3,2,4,1 C.4,2,3,1 D.1,2,3,46. 用单链表表示的链队列的队头在链表的【 A 】。A. 链头 B. 链尾 C. 链中 D. 都不是7. 设入栈序列为 1,2,3,4,5, 则可能

21、得到的出栈序列为【 C 】。A.1,2,5,3,4 B.3,1,2,5,4C.3,2,5,4,1 D.1,4,2,3,58. 输入序列是ABC若输出序列变为 CBA经过的栈操作为【BA. push,pop,push,pop,push,popB. push,push,push,pop,pop,popC. push,push,pop,pop,push,popD. push,pop,push,push,pop,pop9. 栈在【 D 】应用。A. 递归调用 B. 函数调用C. 表达式求值 D.A,B,CD 】数据结构10. 设计一个判别表达式中左、右括号是否配对的算法，采用【 最佳。A. 线性表的顺

22、序存储结构 B. 队列C. 线性表的链式存储结构 D. 栈11. 允许对队列进行的操作有【 D 】。A. 对队列中的元素排序 B. 取出最近进队的元素C. 在队头之前插入元素 D. 删除队头元素12. 对于循环队列【 D 】。A. 无法判断队列是否为空 B. 无法判断队列是否为满C. 队列不可能满 D. 以上说法都不对13. 队列存放在 A0.M-1 中，则入队时的操作为【 B 】。 A.rear=rear+1 B.rear=(rear+1)%MC.rear=(rear+1)%(M+1) D.rear=(rear+1)%(M-1)14. 队列存放在 A0.M-1 中，则出队时的操作为【 B 】

23、。A.front=front+1 B. front=(front+1)%MC. front=(front+1)%(M+1) D. front=(front+1)%(M-1)15. 循环队列的最大容量为 M,则队空的条件是【A】。A.rear=front B.(rear+1)%M=frontC.rear+1=front D.(rear-1)%M=front16. 循环队列的最大容量为 M,则队满的条件是【B】。A.rear=front B.(rear+1)%M=frontC.rear+1=front D.(rear-1)%M=front二、判断题X】1.队列在函数调用时必不可少，因此递归离不幵队

24、列。V】2.栈和队列的存储方式，既可以是顺序方式，又可以是链式方式。V】3.设尾指针的循环链表表示队列，则入队和出队算法的时间复杂度为 0(1)。【X 】 4.队列逻辑上是一个上端和下端既能增加又能减少的线性表。【V 】 5.在链队列中，即使不设置尾指针也能进行入队操作。V 】 6. 栈和队列度是限制存取点的线性结构x】7.即使对不含相同元素的同一输入序列进行两组不同的合法的入栈和出栈操作，所得的输出序列一定相同。V】8.栈是实现函数调用所必需的数据结构。V】9.顺序队列中的元素个数，可以根据队首指针和队尾指针的值计算出来。三、填空题1. 循环队列的引入，目的是为了克服顺序队列的假溢出。2.

25、区分循环队列的空与满有3种方法，它们是少用一个元素、设空满标志 、用计数器记录队列中元素个数03. 栈和队列的区别是栈只能在表一端进行插入和删除操作，队列限制在表的一端进行插入操作，在另一端进行删除操作 04. 一个栈的输入序列是12345,则栈的输出序列43512是。5. 设栈采取顺序存储结构，栈中已有i-1个元素，则第i个元素进栈操作的算法时间复杂度是 O ( 1)06. 若用不带头结点的单链表表示栈，则创建一个空栈要执行的操作是top二NULLo7.从循环队列中删除- 个 元 素的操作是Q.fro nt=(Q.fro nt+1)%QSize08.从循环队列中插入- 个 元 素的操作是Q.

26、rear=(Q.rear+1)%QSize09.判断链队列中只有-个结点的条件是Q.fr on t-> next=Q.rear010.如果栈的最大长度难以估计，最好使用链栈0四、简答题1. 为什么说栈是一种后进先出表？ 答：因为栈是限定在表的一端进行插入和删除操作，所以后入栈的数据元 素总是先出栈，所以说栈是一种后进先出表。2. 对于一个栈，其输入序列是 A,B,C, 试给出全部可能的输出序列。 答：可能的出栈序列是： ABC、ACB、BAC、 BCA、CBA。3. 何谓队列上溢？何为假溢出现象？有哪些解决假溢出问题的方法，并分别阐述其工作原理。答：队列上溢指在队列的顺序存储分配中，所有

27、单元中已有元素，再进行 插入操作时称为队列上溢。假溢出指在队列的顺序存储分配中，分配给队列的存储空间有存储单元未 被占用，但按照操作规则而使进队的数据元素无法进队的现象。解决假溢出问题的方法是在队列的顺序存储分配中，分配给队列的存储空 间可以循环使用，其进本原理是用表示队头和队尾指针与分配给队列的存储空 间长度进行取模运算。即：入队操作： Q.rear=(Q.rear+1)%MSize出队操作： Q.front=(Q.front+1)%MSize4. 队列可以用单循环链表来实现，故可以只设一个头指针或只设一个尾指 针，请分析用哪种方案最合适。答：使用循环链表来表示队列，设置尾指针比较合适，因为

28、入队操作可以直 接在尾结点后进行插入操作，出队操作时可以根据尾指针很容易找到链表的头 结点，入队出队操作的算法时间复杂度均为O(1) 。若只设头指针，则出队操作 的算法时间复杂度为 O(1) ，入队操作的算法时间复杂度为 O(n) 。5. 简述线性表、栈和队列的异同？答：栈和队列都是操作位置受限的线性表，即对插入和删除操作的位置加以 限制。栈是仅允许在表的一端进行插入和删除操作的线性表，因而是后进先出 表。队列是允许在表的一端进行插入，在表的另一端进行删除的线性表，因而 是先进先出表。线性表可以在任何位置进行插入和删除操作。五、算法设计题1. 设计一个算法，利用栈和队列的基本运算将指定栈中的元

29、素顺序逆转。解：算法基本思想：先将栈中元素出栈运算移至队列中，再将队列中元素出 队列移至栈中。void reverse(Stack &st) Queue sq ；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. 。再将临时栈中元素移至原栈中

30、，即恢复栈内容。ElemType bottom(Stack &st) ElemType x,y;Stack tmpst;InitStack(tmpst)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 的逆序。解：算法基本思想：将单链表结点依次放入链栈中，链栈本身就是一个单链 表

31、，即实现了原单链表的逆序。假设链栈不带头结点，再加上原来的头结点， 就完成了原单链表的逆序。Void revert(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. 串是一种特殊的线性表，其特殊性体现在【 B】。A. 可以顺序存储B.数据元素是一个字符C.数据元素可以使多个字符D.可以链接存储3. 两个串相等必有串长度相等且【

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

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

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

35、 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. 一棵二叉树的度可以小于 2C. 一棵二叉树至少有一个结点的度为 2 D. 二叉树中任何一个结点的度 为22. 利用二叉链表存储树，则根结点的右指针

36、是【 C 】。A. 指向最左孩子 B. 指向最右孩子C. 空 D. 非空3. 若一棵二叉树具有 10个度为 2的结点， 5个度为 1的结点，则度为 0的结点 个数为【 B 】。A.9 B.11C.15 D. 不确定4. 一棵二叉树有 1001 个结点，其中叶结点的个数为【 D 】。A.250B.490C.254D.不确定5. 一棵完全二叉树有 1001 个结点，其中叶结点的个数为【 D 】。A.250B.500C.254D.以上答案均不对6. 一棵具有1025个结点的二叉树的高h为【C】。C.11 至 1025之间 D.10 至1024之间A.11B.117. 一棵 124 个叶结点的完全树，

37、最多具有【 B 】个结点A.247B.248C.249D.2518. 一棵具有 10 个叶结点的二叉树具有【 B 】度为 2的结点。A.8 B.9C.10 D.119. 已知一棵完全二叉树有 625 个结点，叶结点的个数为【 C 】。A.311 B.312C.313 D. 其它10. 一棵具有 n 个结点的完全二叉树的高 h 为【 AB】。n n+1A.log 2 +1 B.log 2C.log 2n+1D.log2n-111. 由 8个权值构造一棵哈夫曼树，该哈夫曼树有【 A 】个结点A.15B.16C.17D.1412. 由 3个结点可以构造【 D 】种不同的二叉树。A.2 B.3C.4

38、D.513. 树最适合用来表示【 C 】。A. 有序数据元素 B. 无序数据元素C. 元素间具有分支层次关系的数据 D. 元素间无联系的数据14. 下图中 4 棵二叉树中，【 C 】不是完全二叉树。D.15. 某二叉树的先序遍历序列和后序便利序列正好相反，则该二叉树一定是A 】。A. 空或只有一个结点 B. 完全二叉树C. 二叉排序树 D. 高度等于其结点数16. 在一棵非空二叉树的中序遍历序列中，根结点的右边【 A 】。A. 只有右子树上的所有结点B.只有右子树上的部分结点C. 只有左子树上的部分结点D.只有左子树上的所有结点17. 任何一棵二叉树的叶子结点在先序、中序和后序遍历序列中的相对

39、次序A 】。A. 不发生上改变B.发生改变C. 不能确定D.以上都不对18. 一棵满二叉树，m个叶结点，n个结点，深度为h,贝V【D】。A.n=h+m B.h+m=2n C.m=h-1D.n=2h-119.设n, m是二叉树上的两个结点,在中序遍历时，n在m之前的条件是【C】。A.n 在m右方B.n是m的祖先C.n 在m左方D.n是m的子孙20. 设高度为 h 的二叉树上只有度为0 和度为 2 的结点,则此类二叉树中包含的结点数最少为【 B 】。、判断题X】1.二叉树是一般树的特殊树型IV】2.树与二叉树是两种不同的树形结构。【X】3.对于有n个结点的二叉树，其高度为log 2n。【V】4.完

40、全二叉树中，若一个没有左孩子，则它必定是叶结点。【V】5. 一棵具有n个结点的完全二叉树，从上到下、从左到右用自然数对结点进行编号，结点为i的结点的左孩子的编号为 2i(2i<n)。【X】6. 一棵树中的叶结点数一定等于与其对应的二叉树的叶结点数。【V】7.哈夫曼树是带权路径长度最短的树，路经上权值较大的结点离根最近。【V】8.哈夫曼树的结点个数不偶数。三、填空题1.深度为k的完全二叉树至少有 丄2个结点，至多有2k-1个结点。2. 在一棵二叉树中，度为 0的结点个数为n0,度为2的结点个数为n2,则有 n0二 n2+1。3. 一棵二叉树第i层最多有2 '1个结点，一棵有n个结点

41、的满二叉树共有2K-1个结点，共有2 K-1个叶结点。4. 根据二叉树的定义，具有 3个结点的二叉树共有_5种不同形态，它们分另y是。5. 在一棵完全二叉树中，结点个数为n,则编号最大的分支结点的编号为.n/2。6. 在一棵完全二叉树中，编号i和j的两个结点处于同一层的条件是 og 2丄二og <。7. 具有n个结点的二叉树采用二叉链表存储结构，共有n+1个空指针域。8. 具有n个结点的二叉树中，如果有 m个叶结点，则一定有m-1 个度为2的结点，有 n-2m+1个度为1的结点。9. 在二叉树的链式存储结构中，指针p所指结点为叶结点的条件是p->lchild=NULL&&a

42、mp;p->rchild=NULL。10. 二叉树的先序序列和中序序列相等的条件是任何结点至多只有右子11. 有一棵如下图所示的树，回答下列问题： 这棵树的根结点是_a。 这棵树的叶子结点是b,e,g,d 结点c的度为Ao 这棵树的深度是丄4o 结点c的孩子结点是_eo 结点c的双亲结点是ao外，其余结点有_J个双亲结点这棵树的度是3o12.树与二叉树的两差0个结点的最大度限定为 2树中结点的最大度没有限制，二叉树托勺结点无左右之分，二叉树的的结点有左右之13.树中任一结点允许有个孩子个孩子结点，除根结点之四、简答题1. 设有如下图所示的二叉树，给出其前序、中序和后序遍历结果答：前序序列

43、：eadcbifghj中序序列：abcdiefhgje答：下图为其树的二叉树表示。3. 有一份电文共有5个字符：a,b,c，det丿它们出现的频率依次为4,7, 5,2,9,e : 114. 假设一棵二叉树采用顺序存储结构，如下图所示5101520eafdgcjhib回答些列问题： 画出二叉树表示。 写出先序、中序和后序遍历结果 写出结点c的双亲结点和左、右孩子结点第七章 图、单选题1. 在一个无向图中，所有顶点的度数之和等于所有边的【 C 】倍。A. 1/2 B.1 C.2 D.42. 在一个有向图中，所有顶点的入度数之和等于所有顶点的出度之和的【 B 】 倍。A. 1/2 B.1 C.2

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

45、数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二、判断题【x 1.n个顶点的无向图至多有 n(n-1)条边。【V 2.有向图中，各顶点的入度之和等于各顶点的出度之和。【V 3.邻接矩阵只存储了边的信息，没有存储顶点的信息。【x 4.连通分量是无向图的极小连通子图。【X 5.如果表示有向图的邻接矩阵是对称的，则该有向图一定是完全

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

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

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

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

50、 查找 n 个元素的有序表时，最有效的查找方法是【 C 】。A. 顺序查找 B. 分块查找 C. 折半查找 D. 二叉排序树7. 如果要求一个查找表既能快速查找，又能适应动态变化的要求，可以采用A 】查找方法。A. 分块 B. 顺序 C. 折半 D. 散列8. 在关键字随机分布的情况下，用二叉排序树的方法进行查找，其查找长度与【 B 】量级相当。A. 顺序查找 B. 折半查找 C. 分块查找 D. 前三个都不正确9. 查找效率最高的二叉排序树是【 C 】。A. 所有结点的左子树都为空的二叉排序树B. 所有结点的右子树都为空的二叉排序树C. 平衡二叉树D. 没有左子树的二叉排序树10. 假定有

51、k 个关键字互为同义词，若用线性探测再散列法把这 k 个关键字的纪 录插入到散列表中，至少要进行【 D 】次探测。A.k-1 B.k C.k+1 D.k(k+1)/211. 以下说法错误的是【 B 】。A. 散列法存储的基本思想是由记录关键字决定数据存储地址B. 散列法的结点中只包含数据元素自身的信息，不包含任何指针C. 装填因子是散列法的一个重要参数，它反映了散列表的装填程度D. 散列表的查找效率取决于散列造表是的散列函数和冲突处理的方法12. 散列表的平均查找长度【 A 】。A. 与冲突处理方法有关而与表的长度无关B. 与冲突处理方法无关而与表的长度有关C. 与冲突处理方法有关且与表的长度

52、有关D. 与冲突处理方法无关且与表的长度无关二、判断题【V 1顺序查找法适合于顺序或链式存储结构的查找表。【X 2顺序查找法只能在顺序存储结构上进行。【X 3.二分查找可以在有序的双向链表上进行。【X 4.在二叉排序树中，每个结点的关键字比左孩子的关键字大，比右孩子 的关键字小。【X 5.每个结点的关键字都比左孩子的关键字大，比右孩子的关键字小，这样的二叉树都是二叉排序树。【V 6.哈希存储法只能存储数据元素的值，不能存储数据元素之间的关系。【X 7.哈希冲突是指同一个关键字对应多个不同的哈希地址。三、填空题1. 顺序查找含n个元素的顺序表，若查找成功，则比较关键字的次数最多为n 次；若查找不

53、成功，则比较关键字的次数为n+1 次。2. 在含有n个元素的有序顺序表中进行二分查找，最大的比较次数n是og 2 +1。3. 用二分查找一个查找表，该查找表必须具有的特点是顺序存储且关键字有序。4. 分块查找发将待查找的表均匀地分成若干块且块中诸记录的顺序可以是任意的，但块与块之间关键字有序。5. 在分块查找方法中，首先查找关键字表 ，然后再查找相应的对应 的块6. 用二叉排序树在 n个元素中进行查找，最坏情况下查找时间复杂度为0(n)，最好情况的查找时间复杂度为O(loq 2 o7. 折半查找的存储结构仅限于顺序存储结构 ，且是关键字有序排列o8. 一个无序序列可以通过构造一棵二叉排序树而变成有序序列,构造树的过程即是对无序序列进行排序的过程。9. 用二叉排序树查找，在最坏的情况下，平均查找长度为(n+1) /2,最好的情况下，平均查找长度为.(log?n+1)-1o10. 在