数据结构题集答案65692

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. 效率与采用何种存储结构有关B. 是根据存储

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

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

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

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

7、. 可随机访问任一结点B. 插入删除不需要移动元素C. 不必事先估算存储空间D. 所需空间与其长度成正比2. 设线性表有n 个元素，以下操作中， 【 A 】在顺序表上实现比在链表上实现效率更高。A.输出第i （iwiwn）个元素的值B. 顺序输出这 n 个元素C. 交换第 1 个与第 2 个元素的值D. 输出与给定值x 相等的元素在线性表中的序号3. 如果最常用的操作是取第 i 个结点及其前驱，则采用【 D 】存储方法最节省时间。A. 单链表B. 双链表 C. 线性链表D. 顺序表4. 线性表是具有n个【C】的有限序列（n >0）oA. 表元素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=NULLB.h->next=NULLC.h->next=hD.h!=NULL9. 带头结点的单链表（头指针为 h ）为空的条件是【 B 】 。A.h=NULLB.h->next=NULLC.h->next=h D.h!=NULL10. 带头结点的循环双向链表（头指针为 L ）为空的条件是【D 】 。A.L=NULLB.L->next->prior=NULLC.L->prior=NULLD.L->next=L11. 非空的循环单链表（头指针为head ）的尾结点（由p 指向）满足【 C 】 。A.p->next=NUL

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

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

12、【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 .在 双向循环链表中,删除最后一个结点的算法时间复杂度为O(1)。8 .访问一个线性表中具有给定值的时间复杂度的数量级是O(n)。9 .由n个数据元素生成一个顺序表，若每次都调用插入算法把一个元素插入到表头，则 整个算法的时间复杂度为O(n) ,若每次都调用插入算法把一个元素插入到表尾，则整个算法的时间复杂度为O(n 2)。10 .在 双向 链表中,可以用表尾指针代替表头指针。11 .根据n个数据元素建立对应的顺序表和单链表存储结构，其算法

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

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

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

17、，所有算法都不会修改头指针，可以减少出错的可能性。 五、算法设计题1 .已知一个线性表用含头结点的单链表做存储结构，写一个算法求单链表的长度。解：算法基本思想：从头结点的下一个结点开发，遍历单链表的每个结点，每遇到一个结点，结点计算器加1。int listlenght(linklist L) int length=0;P=L->next; while(p) length+; p=p->next; return(length); 2 .已知一个顺序表 L,其中的元素按值递增有序排列，设计一个算法插入一个值为0 (1)。void insertsq(sqlist L,elemtype x

18、) 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 .对于栈操作数据的原则是【C 】。A. 先进先出B. 后进后出C. 后进先出D. 不分顺序2.

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

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

21、,58. 输入序列是ABC ，若输出序列变为 CBA ，经过的栈操作为【 B 】 。A.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,C10. 设计一个判别表达式中左、右括号是否配对的算法，采用【 D 】数据结构最佳。A. 线性表的顺序存储结构B.队列C. 线性表的链式存储结构D. 栈11. 允许对队列进行的操作有【D 】 。A. 对队

22、列中的元素排序B. 取出最近进队的元素C. 在队头之前插入元素D. 删除队头元素12. 对于循环队列【 D 】 。A.无法判断队列是否为空C.队列不可能满13 .队列存放在 A0.M-1A.rear=rear+1C.rear=(rear+1)%(M+1)14 .队列存放在 A0.M-1A.front=front+1B.无法判断队列是否为满D.以上说法都不对中，则入队时的操作为【B.rear=(rear+1)%MD.rear=(rear+1)%(M-1) 中，则出队时的操作为【B. front=(front+1)%MB】。B】。C. front=(front+1)%(M+1) D. front=

23、(front+1)%(M-1)15 .循环队列的最大容量为A.rear=frontC.rear+1=front16 .循环队列的最大容量为A.rear=frontC.rear+1=front二、判断题M ,则队空的条件是【B.(rear+1)%M=frontD.(rear-1)%M=frontM ,则队满的条件是【B.(rear+1)%M=frontD.(rear-1)%M=frontA oB oX 1.队列在函数调用时必不可少，因此递归离不开队列。V2.栈和队列的存储方式，既可以是顺序方式，又可以是链式方式。IV】3.设尾指针的循环链表表示队列，则入队和出队算法的时间复杂度为0(1)。【X】

24、4.队列逻辑上是一个上端和下端既能增加又能减少的线性表。V5.在链队列中，即使不设置尾指针也能进行入队操作。IV】6.栈和队列度是限制存取点的线性结构。X 7.即使对不含相同元素的同一输入序列进行两组不同的合法的入栈和出栈操作，所 得的输出序列一定相同。V8.栈是实现函数调用所必需的数据结构。IV】9.顺序队列中的元素个数，可以根据队首指针和队尾指针的值计算出来。三、填空题1 .循环队列的引入，目的是为了克服 顺序队列的假溢出。2 .区分循环队列的空与满有3种方法，它们是少用一个元素、设空满标志、用计数器记录队列中元素个数。3 .栈和队列的区别是栈只能在表一端进行插入和删除操作，队列限制在表的

25、一端进行插入操作，在另一端进行删除操作。4 .一个栈的输入序列是 12345 ,则栈的输出序列 43512是错误的。5 .设栈采取顺序存储结构，栈中已有i-1个元素，则第i个元素进栈操作的算法时间复杂度是 O (1)。6 .若用不带头结点的单链表表示栈，则创建一个空栈要执行的操作是Q.front=(Q.front+1)%QSizeQ.rear=(Q.rear+1)%QSize Q.front->next=Q.rear 链栈。top=NULL。7 .从循环队列中删除一个元素的操作是8 .从循环队列中插入一个元素的操作是9 .判断链队列中只有一个结点的条件是10 .如果栈的最大长度难以估计，

26、最好使用四、简答题1. 为什么说栈是一种后进先出表?答： 因为栈是限定在表的一端进行插入和删除操作， 所以后入栈的数据元素总是先出栈，所以说栈是一种后进先出表。2. 对于一个栈，其输入序列是A,B,C, 试给出全部可能的输出序列。答：可能的出栈序列是： ABC 、 ACB 、 BAC 、 BCA 、 CBA 。3. 何谓队列上溢？何为假溢出现象？有哪些解决假溢出问题的方法， 并分别阐述其工作原理。答： 队列上溢指在队列的顺序存储分配中， 所有单元中已有元素， 再进行插入操作时称为队列上溢。假溢出指在队列的顺序存储分配中， 分配给队列的存储空间有存储单元未被占用， 但按照操作规则而使进队的数据元

27、素无法进队的现象。解决假溢出问题的方法是在队列的顺序存储分配中， 分配给队列的存储空间可以循环使用，其进本原理是用表示队头和队尾指针与分配给队列的存储空间长度进行取模运算。即：入队操作： Q.rear=(Q.rear+1)%MSize出队操作：Q.front=(Q.front+1)%MSize4. 队列可以用单循环链表来实现， 故可以只设一个头指针或只设一个尾指针，请分析用哪种方案最合适。答：使用循环链表来表示队列，设置尾指针比较合适，因为入队操作可以直接在尾结点后进行插入操作， 出队操作时可以根据尾指针很容易找到链表的头结点， 入队出队操作的算法时间复杂度均为 O(1) 。若只设头指针，则出

28、队操作的算法时间复杂度为 O(1) ，入队操作的算法时间复杂度为 O(n) 。5. 简述线性表、栈和队列的异同？答：栈和队列都是操作位置受限的线性表，即对插入和删除操作的位置加以限制。栈是仅允许在表的一端进行插入和删除操作的线性表， 因而是后进先出表。 队列是允许在表的一端进行插入， 在表的另一端进行删除的线性表， 因而是先进先出表。 线性表可以在任何位置进行插入和删除操作。五、算法设计题1. 设计一个算法，利用栈和队列的基本运算将指定栈中的元素顺序逆转。解：算法基本思想：先将栈中元素出栈运算移至队列中，再将队列中元素出队列移至栈中。void reverse(Stack &st) Qu

29、eue 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. 。再将临时栈中元素移至原栈中，即恢复栈内容。ElemType bottom(Stack &st) ElemType x,y;Stack tmpst;InitStack(tmp

30、st)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=

31、NULL,*p=h->next,q;While(p) q=p->next;p->next=st;st=p;p=q;h->next=st;、单选题1 .串是任意有限个【 DA.符号构成的集合C.字符构成的集合第四章串B.符号构成的序列D.字符构成的序列2 .串是一种特殊的线性表，A.可以顺序存储C.数据元素可以使多个字符3 .两个串相等必有串长度相等且【A.串的各位置字符任意C.两个串含有相同的字符4 .设有两个串A.连接C.求子串其特殊性体现在【 BB.数据元素是一个字符D.可以链接存储B】。8 .串中各位置字符均对应相等D.两个串所含字符任意B】。p和q,求q在p中首

32、次出现的位置的运算称着【B.模式匹配D.求串长二、填空1 .空串是长度为0的串。2 .一个串中任意连续字符组成的子序列 称为该串的子串。3 .设 s= "abcd ",则执行语句 s2=Substr(s,2,2) 后，s2=" bc”。4 .空白串是由一个或多个空格字符组成的串，其长度等于其所包含的空格字符的个数 。第五章 数组一、单选题1. 一维数组与线性表的区别是【 A 】。A. 前者长度固定，后者长度可变B. 后进长度固定，前者长度可变C. 两者长度均固定 D. 两者长度均可变2. 多维数组的数组元素之间的关系， 【 A 】 。A. 是线性的 B. 是树型的

33、C. 既是线性的，又是树型的D. 既不是线性的，也不是树型的3. 设有数组 A810 ，每个元素占 3 个存储单元，存放该数组的存储单元数为【 C 】 。 A.80B.100C.240D.2704. 设有数组 A810 ，每个元素占 3 个存储单元，首地址为 SA ，则元素 75 的起始地址 是【 D 】 。 A.SA+141B.SA+144C.SA+222D.SA+2255. 设有一个 n*n 的对称矩阵，采用压缩存储，则存入内存的元素个数为【 C 】 。 A.n*nB.n*n/2C.n*(n+1)/2D.(n+1)2/26. 设 A 是一个 n*n 的对称矩阵，压缩存储到一个一维数组 B0

34、.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. 稀疏矩阵一般的压缩方法有两种，即【 C 】 。A. 二维数组和三维数组B. 三元组和散列C. 三元组和十字链表D. 散列和十字链表8. 设有一个 10*10 的对称矩阵A ，以行主次序进行压缩存储，每个元素占一个存储单元，a 1,1 的地址是 1 ，则 A8,5 的起始地址是【 B 】 。 A.13B.33C.18D.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. 二叉树的度为 2B. 一棵二叉树的度可以小于 2C. 一棵二叉树至少有一个结点的度为 2 D. 二叉树中任何一个结点的度为 22. 利用二叉

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

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

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

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

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

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

42、hild=NULL&&p->rchild=NULL10 .二叉树的先序序列和中序序列相等的条件是11 .有一棵如下图所示的树，回答下列问题：O任何结点至多只有右子树这棵树的根结点是这棵树的叶子结点是结点c的度为 2这棵树的深度是一 结点c的孩子结点是 结点c的双亲结点是 这棵树的度是ab,e,g,d4e,fOao12 .树与二叉树的两个主要差别是树中结点的最大度没有限制，二叉树结点的最大度限定为2树的结点无左右之分,二叉树的的结点有左右之分个孩子结点，除根结点之外，其余结13.树中任一结点允许有0个或多个孩子点有 1个双亲结点。四、简答题1.设有如下图所示的二叉树，给出其

43、前序、中序和后序遍历结果。答： 前序序列：eadcbifghj中序序列：abcdiefhgj后序序列：bcidahjgfe答：下图为其树的二叉树表示。3.有一份电文共有 5个字符：a,b,c,d,e,它们出现的频率依次为4, 7, 5, 2, 9,构造对应的哈夫曼树，求哈夫曼树的带权路径长度和每个字符的哈夫曼编码。字符编码：a： 011b ： 10c： 00d : 010e： 114.假设一棵二叉树采用顺序存储结构，如下图所示。05101520eafdgcjhib回答些列问题：画出二叉树表示。写出先序、中序和后序遍历结果写出结点c的双亲结点和左、右孩子结点画出此二叉树还原成森林的图 答：二叉树

44、表示如下图所示。先序序列为：eadcbjfghi中序序列为：acbdjefhgi后序序列为：bcjdahigfe结点c的双亲结点是d ,左孩子为b ,无右孩子 该二叉树对应的森林为第七章图一、单选题1 .在一个无向图中，所有顶点的度数之和等于所有边的【 C】倍。 A.1/2B.1C.2D.42 .在一个有向图中，所有顶点的入度数之和等于所有顶点的出度之和的【B】倍。A.1/2B.1C.2D.43 .一个有n个顶点的无向图最多有 C 条边。A.n B.n(n-1)C.n(n-1)/2 D.2n4 .具有4个顶点的无向完全图有【 A】条边。A.6B.12C.16D.205 .具有6个顶点的无向图至

45、少应有【 A】条边才能确保是一个连通图。A.5B.6C.7D.86 .一个有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是【 DA.nB. (n-1) 2 C. (n-1) D. n 27 .对某个无向图的邻接矩阵来说，【A loA.第i行上的非0元素个数等于第i列上非0元素个数8 .矩阵中非0元素个数等于图中的边数C.第i行、第i列上非0元素个数等于顶点 vi的度数D.矩阵中非全0行的行数等于图中的顶点数8.对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表头向量的大小为 【 A】；所有邻接表中结点总数为【 C】。 A.n B.n+1C.n-1 D.n2 A.e/2 B.e

46、 C.2e D.n+e 二、判断题【X】1.n个顶点的无向图至多有n(n-1)条边。【V1 2.有向图中，各顶点的入度之和等于各顶点的出度之和。【V1 3.邻接矩阵只存储了边的信息，没有存储顶点的信息。【X】4.连通分量是无向图的极小连通子图。【X】5.如果表示有向图的邻接矩阵是对称的，则该有向图一定是完全有向图。【X】6.如果表示图的邻接矩阵是对称的，则该图一定是无向图。【VI 7.如果表示图的邻接矩阵不是对称的，则该图一定是有向图。 三、填空题1 .有n个顶点的无向图最多有n(n-1)/2 条边。2 .具有n个顶点的强连通有向图至少有n 条边。3 .具有n个顶点的有向图最多有n(n-1)条

47、边。4 .一个图的临接矩阵表示法是唯一的,而 邻接表 表示法是不唯一的。5 .具有10个顶点的无向图，边的总数最多为45。6 .在有n个顶点的有向图中，每个顶点的度最大可达n-1。7 .已知一个有向图采用邻接矩阵表示，计算第i个顶点的入度的方法是求第i列非0元素个数。8 .已知一个有向图的邻接矩阵表示，删除所有从第i个结点出发的弧的方法是将第i行对应的1置成0。计算邻接矩阵中9 .对于n的顶点的无向图，采用邻接矩阵表示，求图中边的方法是元素值为1的个数，判断任意两个顶点是否有边相连的方法是判断对应邻接矩阵元素的值是否为 1 ,再除以2,求任意顶点的度的方法是求邻接矩阵中对应顶点所在行值为1的元

48、素个数。10 .对于n的顶点的有向图，采用邻接矩阵表示， 求图中边的方法是计算邻接矩阵中元素值为1的个数 ，判断任意两个顶点是否有边相连的方法是判断对应邻接矩阵元素的值是否为 1,求任意顶点的度的方法是求邻接矩阵中对应顶点所在行和列的元素值为 1的个数。11 .无向图的连通分量指无向图中最大连通子图。12 .若无向图有m条边，则表示该无向图的邻接表中有2m 结点。四、简答题1 .从占用的存储空间来看，对于稠密图和稀疏图，采用邻接矩阵和邻接表那个更好些？ 答：从占用存储空间看，稠密图采用邻接矩阵更好，稀疏图采用邻接表更好。2 .用邻接矩阵表示图时，矩阵元素的个数与顶点个数是否相关？与边的条数是否

49、相关？ 为什么？。答：用邻接矩阵表示图，矩阵元素的个数与图的顶点个数直接相关，与边的条数无关。因为假设定点个数为 n,则邻接矩阵的大小为 n2。第九章 查找一、单选题1 .顺序查找法适合于存储结构为【 B 】的查找表。A. 散列存储B. 顺序存储或链式存储C. 压缩存储D. 索引存储2. 对查找表进行折半查找时，要求查找表必须【 B 】 。A. 以顺序方式存储B. 以顺序方式存储，且结点按关键字有序排列C. 以链式方式存储D. 以链式方式存储，且结点按关键字有序排列3. 采用顺序查找法查找长度为n 的查找表时，每个元素查找的平均查找长度为【C 】 。A.n B.n/2C.(n+1)/2D.(n

50、-1)/24. 采用折半查找法查找长度为n 的查找表时，每个元素查找的平均查找长度为【D 】 。A.O(n 2 ) B.O(nlog 2n)C.O(n) D.O(log 2n)5. 采用分块查找时，若查找表中有625 个元素，查找每个元素的概率相同，假设对索引表和块都采用顺序查找，每块应分【 B 】个结点最佳。A.10B.25C.6D.6256. 查找 n 个元素的有序表时，最有效的查找方法是【 C 】 。A. 顺序查找B. 分块查找 C. 折半查找D. 二叉排序树7. 如果要求一个查找表既能快速查找，又能适应动态变化的要求，可以采用【 A 】查找方 法。A. 分块 B. 顺序 C. 折半 D

51、. 散列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. 以下说法错误的是【 B 】 。A. 散列法存储的基本思想是由记录关键字决定数据存储

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

53、关键字大，比右孩子的关键字小。X 5.每个结点的关键字都比左孩子的关键字大，比右孩子的关键字小，这样的二叉树 都是二叉排序树。【V) 6.哈希存储法只能存储数据元素的值，不能存储数据元素之间的关系。【X】7.哈希冲突是指同一个关键字对应多个不同的哈希地址。 三、填空题1 .顺序查找含n个元素的顺序表，若查找成功，则比较关键字的次数最多为 n 次； 若查找不成功，则比较关键字的次数为n+1 次。2 .在含有n个元素的有序顺序表中进行二分查找，最大的比较次数 是.？喻“？+1。3 .用二分查找一个查找表，该查找表必须具有的特点是顺序存储且关键字有序。4 .分块查找发将待查找的表均匀地分成若干块且块中诸记录的顺序可以是任意的，但块与块之间关键字有序。5 .在分块查找方法中， 首先查找 关键字表，然后再查找相应的对应的块。6 .用二叉排序树在 n个元素中进行查找，最坏情况下查找时间复杂度为。,最好情况的查找时间