数据结构题集

数据构造题集第一章绪论一、单选题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.数据项与数据项之间存在某种关系5.算法分析的目的是【C】。A.找出数据构造的合理性B.研究输入和输出的关系C.分析算法的效率以求改善D.分析算法的易懂性6.在存储数据时，不仅要考虑存储各数据元素的值，并且还要存储【C】。A.数据解决的办法B.数据元素的类型C.数据元素之间的关系D.数据的存储办法7.算法分析的重要任务是分析【D】。A.算法与否含有较好的可读性B.算法中与否存储语法错误和逻辑错误C.算法的功效与否符合设计规定D.算法的执行时间与问题规模之间的关系。8.数据的运算【A】。A.效率与采用何种存储构造有关B.是根据存储构造来定义的C.有算术运算和关系运算两大类D.必须用程序设计语言来描述9.算法的计算量的大小称为算法的【B】。A.效率B.时间复杂度C.现实性D.难度10.持续存储分派时，存储单元的地址【A】。A.一定持续B.一定不持续C.不一定持续D.部分持续，部分不持续二、判断题1.数据元素是数据构造的最小单位【.×】。2.数据的逻辑构造阐明数据元素之间的次序关系，它依赖于计算机的存储构造【×.】。3.数据的逻辑构造指数据元素的各数据项之间的逻辑关系【×.】。4.算法的优劣与算法的描述语言无关，但与使用的计算机有关【.×】。5.数据构造的抽象操作的定义与具体实现有关【.×】。三、填空题1.数据的逻辑构造指数据元素之间的逻辑关系。2.一种数据构造在计算机中的表达称为存储构造。3.数据的物理构造重要涉及次序存储构造的表达和链式存储构造的表达。4.数据逻辑构造涉及集合、线性构造、树和图四种，树构造和图构造统称为非线性构造。5.次序存储办法把逻辑上逻辑上相邻的元素存储在物理位置相邻的存储单元里；链式存储办法中结点间的逻辑关系是由指针域表达的。6、数据构造研究的是逻辑构造和物理构造以及它们之间的互有关系，并对于这种构造定义对应的运算，设计出对应的算法。7.算法的执行时间是问题规模n的函数。8.下列是4个算法全部语句频度之和的体现式，其中的复杂度相似的是A和B。A.TA(n)=2n3+3n2+1000B.TB(n)=n3-n2log2n-1000C.TC(n)=n2log2n+n2D.TD(n)=n2+1000四、解答题1.简述数据的逻辑构造和存储构造的关系。答：在数据构造中，逻辑构造和存储构造是亲密有关的，存储构造不仅将数据元素存储到计算机中，并且还要表达各数据元素之间的逻辑关系。逻辑构造与计算机无关，存储构造是数据元素之间的关系在计算机中的表达。普通状况下，一种逻辑构造能够有多个存储构造，例如，线性构造能够采用次序存储构造或链式存粗构造表达。2.数据构造和数据类型有什么区别？答：数据构造是互相间存在一种或多个特定关系的数据元素的集合，普通涉及三个方面的内容：数据的逻辑构造、存储构造和多数据的运算。数据类型是一种值得集合和定义在这个值集上的一组操作的总称。数据构造重点考虑元素之间的关系，数据类型重点考虑数据的个体特性。3.当为解决某一问题已经选定其数据的逻辑构造后，选择数据的存储构造时，应从哪些方面考虑？答：普通从两个方面考虑：第一是算法实现的存储空间复杂度；第二是算法执行的时间复杂度。若存储空间难以拟定，宜选择链式存储构造，否则选择次序存储构造。若插入、删除操作频繁，则选链式存储构造，否则选择次序存储构造。

第二章线性表一、单选题1.链表不含有的特点是【A】。A.可随机访问任一结点B.插入删除不需要移动元素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.线性表是含有n个【C】的有限序列（n≥0）。A.表元素B.字符C.数据元素D.数据项5.下面有关线性表的叙述中，错误的是【B】。A.线性表采用次序存储，则必须占用一片持续的存储单元B.线性表采用次序存储，则便于插入和删除操作C.线性表采用链式存储，则不必占用一片持续的存储单元D.线性表采用链式存储，则便于插入和删除操作6.线性表的次序存储构造是一种【A】。A.随机存取的存储构造B.次序存取的存储构造C.索引存取的存储构造D.Hash存取的存储构造7.单链表中增加一种头结点的目的是为了【C】。A.使单链表最少有一种结点B.标记表首结点的位置C.方便运算的实现D.阐明单链表是线性表的链式存储8.不带头结点的单链表（头指针为h）为空的条件是【A】。A.h==NULLB.h->next==NULLC.h->next==hD.h!=NULL9.带头结点的单链表（头指针为h）为空的条件是【B】。A.h==NULLB.h->next==NULLC.h->next==hD.h!=NULL10.带头结点的循环双向链表（头指针为L）为空的条件是【D】。A.L==NULLB.L->next->prior==NULLC.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(1)的操作是【A】。A.访问第i个结点和求第i个结点的直接前驱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的特点是【A】。A.p->next==HB.p->next==H->nextC.p==HD.p==H->next二、判断题【×】1.取线性表的第i个元素的时间同i的大小有关。【×】2.线性表中每个元素都有一种直接前驱和一种直接后继。【×】3.次序存储方式只能用于存储线性构造。【×】4.线性表采用链式存储时，结点和结点内部的存储空间能够不持续。【×】5.在一种设有头指针和尾指针的单链表中，执行删除单链表最后一种结点的操作与链表的长度无关。三、填空题1.向一种长度为n的次序表中的第i个元素之前插入一种元素时，需要向后移动n-i+1个元素。2.在一种长度为n的次序表中删除第i个元素时，需要向前移动n-i个元素。3.在单链表中设立头结点的作用是简化插入、删除算法。4.在单链中要删除某一指定结点，必须找到该结点的直接前驱结点。5.访问单链表中的结点，必须沿着指针域依次进行。6.在双链表中每个结点有两个指针域，一种指向直接前驱结点，一种指向直接后继结点。7.在双向循环链表中，删除最后一种结点的算法时间复杂度为O(1)。8.访问一种线性表中含有给定值的时间复杂度的数量级是O(n)。9.由n个数据元素生成一种次序表，若每次都调用插入算法把一种元素插入到表头，则整个算法的时间复杂度为O(n)，若每次都调用插入算法把一种元素插入到表尾，则整个算法的时间复杂度为O(n2)。10.在双向链表中，能够用表尾指针替代表头指针。11.根据n个数据元素建立对应的次序表和单链表存储构造，其算法的时间复杂度最佳的状况是O(n)，最坏的状况是O(n2)。12.求线性表的次序存储和链式存储的长度的算法时间复杂度分别是O(1)和O(n)。13.在一种带头结点的单链表中，在表头插入或删除与在其它位置插入或删除，其操作过程与否相似？相似。14.在一种不带头结点的单链表中，在表头插入或删除与在其它位置插入或删除，其操作过程与否相似？不相似。四、简答题1.论述次序表和链表存储方式的特点。答：次序表存储方式为数据分派持续的存储单元，数据元素按逻辑次序依次存储到对应存储单元中，使得逻辑相邻的数据元素物理也相邻，因此能够实现随机访问线性表的数据元素，即数据访问的时间复杂度为O(1)。链表存储方式分派的存储单元能够不持续，通过每个结点的指针域来表达数据元素之间的逻辑关系，只能次序访问线性表中的数据元素。2.若频繁地对一种线性表进行插入和删除操作，则该线性表宜采用何种存储构造，为什么？答：若频繁地对一种线性表进行插入和删除操作，则该线性表宜采用链式存储构造。由于链式存储构造在插入和删除数据元素时不需要移动数据元素，只需要修改结点的指针域就能够变化数据元素之间的逻辑关系。3.在单链表、双向循环链表和单循环链表中，若仅懂得指针p指向某结点，不懂得头指针，能否将结点p从对应的链表中删除？若能够，时间复杂度各为多少。答：要实现删除p结点的操作，必须找到其前驱结点，修改其指针域的值使其指向p的后继结点，以实现删除结点p。单链表不行，由于不懂得头指针就无法找到结点p的前驱结点。双向循环链表和单循环链表能够能够实现删除p结点。单循环链表删除p结点的时间复杂度为O(n)，双循环链表删除P结点的时间复杂度为O(1)。4.对链表设立头结点的作用是什么？答：对带头结点的链表，在表的任何结点之前插入结点或删除任何位置的结点，所要做的都是修改前一种结点的指针域，由于在带头结点的链表中任何元素结点都有前驱结点。如果没有头结点，在首元结点前插入结点或删除首元结点都要修改头指针，其算法要比带头结点的算法复杂些。另一方面，带头结点的链表构造，初始化后的头指针就固定了，除撤销算法外，全部算法都不会修改头指针，能够减少出错的可能性。五、算法设计题1.已知一种线性表用含头结点的单链表做存储构造，写一种算法求单链表的长度。解：算法基本思想：从头结点的下一种结点开发，遍历单链表的每个结点，每碰到一种结点，结点计算器加1。intlistlenght(linklistL){intlength=0;P=L->next;while(p){length++;p=p->next;}return(length);}2.已知一种次序表L，其中的元素按值递增有序排列，设计一种算法插入一种值为x的元素后保持该次序表仍然递增有序，且空间复杂度为0（1）。voidinsertsq(sqlistL,elemtypex){n=L.length-1;while(n>=0&<(x,L.elem[n]){L.elem[n+1]=L.elem[n];n--;}L.elem[n+1]=x;}L.lenght++;return;}3.写一种算法，从次序表中删除值为x的全部元素。voiddelallsq(Sqlist&L){inti=0,j=0;while(j<L.length){if(L.elem[j]!=x)L.elem[i++]=L.elem[j];j++;}L.longth=i;}

第三章栈和队列一、单选题1.对于栈操作数据的原则是【C】。A.先进先出B.后进后出C.后进先出D.不分次序2.队列的先进先出特性是指【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，则【④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,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.对队列中的元素排序B.取出近来进队的元素C.在队头之前插入元素D.删除队头元素12.对于循环队列【D】。A.无法判断队列与否为空B.无法判断队列与否为满C.队列不可能满D.以上说法都不对13.队列寄存在A[0..M-1]中，则入队时的操作为【B】。A.rear=rear+1B.rear=(rear+1)%MC.rear=(rear+1)%(M+1)D.rear=(rear+1)%(M-1)14.队列寄存在A[0..M-1]中，则出队时的操作为【B】。A.front=front+1B.front=(front+1)%MC.front=(front+1)%(M+1)D.front=(front+1)%(M-1)15.循环队列的最大容量为M，则队空的条件是【A】。A.rear==frontB.(rear+1)%M==frontC.rear+1==frontD.(rear-1)%M==front16.循环队列的最大容量为M，则队满的条件是【B】。A.rear==frontB.(rear+1)%M==frontC.rear+1==frontD.(rear-1)%M==front二、判断题【×】1.队列在函数调用时必不可少，因此递归离不开队列。【√】2.栈和队列的存储方式，既能够是次序方式，又能够是链式方式。【√】3.设尾指针的循环链表表达队列，则入队和出队算法的时间复杂度为0(1)。【×】4.队列逻辑上是一种上端和下端既能增加又能减少的线性表。【√】5.在链队列中，即使不设立尾指针也能进行入队操作。【√】6.栈和队列度是限制存取点的线性构造。【×】7.即使对不含相似元素的同一输入序列进行两组不同的正当的入栈和出栈操作，所得的输出序列一定相似。【√】8.栈是实现函数调用所必需的数据构造。【√】9.次序队列中的元素个数，能够根据队首指针和队尾指针的值计算出来。三、填空题1.循环队列的引入，目的是为了克服次序队列的假溢出。2.辨别循环队列的空与满有3种办法，它们是少用一种元素、设空满标志、用计数器统计队列中元素个数。3.栈和队列的区别是栈只能在表一端进行插入和删除操作，队列限制在表的一端进行插入操作，在另一端进行删除操作。4.一种栈的输入序列是12345，则栈的输出序列43512是错误的。5.设栈采用次序存储构造，栈中已有i-1个元素，则第i个元素进栈操作的算法时间复杂度是O（1）。6.若用不带头结点的单链表表达栈，则创立一种空栈要执行的操作是top=NULL。7.从循环队列中删除一种元素的操作是Q.front=(Q.front+1)%QSize。8.从循环队列中插入一种元素的操作是Q.rear=(Q.rear+1)%QSize。9.判断链队列中只有一种结点的条件是Q.front->next==Q.rear。10.如果栈的最大长度难以预计，最佳使用链栈。四、简答题1.为什么说栈是一种后进先出表？答：由于栈是限定在表的一端进行插入和删除操作，因此后入栈的数据元素总是先出栈，因此说栈是一种后进先出表。2.对于一种栈，其输入序列是A,B,C,试给出全部可能的输出序列。答：可能的出栈序列是：ABC、ACB、BAC、BCA、CBA。3.何谓队列上溢？何为假溢出现象？有哪些解决假溢出问题的办法，并分别论述其工作原理。答：队列上溢指在队列的次序存储分派中，全部单元中已有元素，再进行插入操作时称为队列上溢。假溢出指在队列的次序存储分派中，分派给队列的存储空间有存储单元未被占用，但按照操作规则而使进队的数据元素无法进队的现象。解决假溢出问题的办法是在队列的次序存储分派中，分派给队列的存储空间能够循环使用，其进本原理是用表达队头和队尾指针与分派给队列的存储空间长度进行取模运算。即：入队操作：Q.rear=(Q.rear+1)%MSize出队操作：Q.front=(Q.front+1)%MSize4.队列能够用单循环链表来实现，故能够只设一种头指针或只设一种尾指针，请分析用哪种方案最适宜。答：使用循环链表来表达队列，设立尾指针比较适宜，由于入队操作能够直接在尾结点后进行插入操作，出队操作时能够根据尾指针很容易找到链表的头结点，入队出队操作的算法时间复杂度均为O(1)。若只设头指针，则出队操作的算法时间复杂度为O(1)，入队操作的算法时间复杂度为O(n)。5.简述线性表、栈和队列的异同？答：栈和队列都是操作位置受限的线性表，即对插入和删除操作的位置加以限制。栈是仅允许在表的一端进行插入和删除操作的线性表，因而是后进先出表。队列是允许在表的一端进行插入，在表的另一端进行删除的线性表，因而是先进先出表。线性表能够在任何位置进行插入和删除操作。五、算法设计题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.设计一种算法，运用栈的基本运算返回指定栈中栈底元素。解：先将栈中元素依次移至另一种临时栈中，最后一种元素即为栈底元素，设为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，才干保存栈底元素在x中Push(st,y);}DestroyStack(tmpst);return(x);}3.设计一种算法，运用栈来实现带头结点的单链表h的逆序。解：算法基本思想：将单链表结点依次放入链栈中，链栈本身就是一种单链表，即实现了原单链表的逆序。假设链栈不带头结点，再加上原来的头结点，就完毕了原单链表的逆序。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.串是一种特殊的线性表，其特殊性体现在【B】。A.能够次序存储B.数据元素是一种字符C.数据元素能够使多个字符D.能够链接存储3.两个串相等必有串长度相等且【B】。A.串的各位置字符任意B.串中各位置字符均对应相等C.两个串含有相似的字符D.两个串所含字符任意4.设有两个串p和q，求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】。A.是线性的B.是树型的C.既是线性的，又是树型的D.既不是线性的，也不是树型的3.设有数组A[8][10]，每个元素占3个存储单元，寄存该数组的存储单元数为【C】。A.80B.100C.240D.2704.设有数组A[8][10]，每个元素占3个存储单元，首地址为SA，则元素[7][5]的起始地址是【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的对称矩阵，压缩存储到一种一维数组B[0..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，以行主次序进行压缩存储，每个元素占一种存储单元，a1,1的地址是1，则A8,5的起始地址是【B】。A.13B.33C.18D.40二、解答题1.设数组A[50][80]，其基地址为，每个元素占2个存储单元，以行序位主序次序存储，回答下列问题：（1）该数据组由多少元素？（2）该数组占用多少存储单元？（3）数组元素a[30][30]的存储地址是多少？答：（1）该数组有：50*80=4000个元素（2）该数组占用4000*4=8000个存储单元（3）loc(30,30)=+(30*80+30)*2=+4860=6860

第六章树与二叉树一、单选题1.有关二叉树下列说法对的的是【B】。A.二叉树的度为2B.一棵二叉树的度能够不大于2C.一棵二叉树最少有一种结点的度为2D.二叉树中任何一种结点的度为22.运用二叉链表存储树，则根结点的右指针是【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至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.?log2n+1?C.log2n+1D.log2n-111.由8个权值构造一棵哈夫曼树，该哈夫曼树有【A】个结点。A.15B.16C.17D.1412.由3个结点能够构造【D】种不同的二叉树。A.2B.3C.4D.513.树最适合用来表达【C】。A.有序数据元素B.无序数据元素C.元素间含有分支层次关系的数据D.元素间无联系的数据14.下图中4棵二叉树中，【C】不是完全二叉树。A.B.C.D.15.某二叉树的先序遍历序列和后序便利序列正好相反，则该二叉树一定是【A】。A.空或只有一种结点B.完全二叉树C.二叉排序树D.高度等于其结点数16.在一棵非空二叉树的中序遍历序列中，根结点的右边【A】。A.只有右子树上的全部结点B.只有右子树上的部分结点C.只有左子树上的部分结点D.只有左子树上的全部结点17.任何一棵二叉树的叶子结点在先序、中序和后序遍历序列中的相对次序【A】。A.不发生上变化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之前的条件是【C】。A.n在m右方B.n是m的祖先C.n在m左方D.n是m的子孙20.设高度为h的二叉树上只有度为0和度为2的结点，则这类二叉树中包含的结点数最少为【B】。A.2hB.2h-1C.2h+1D.h+1二、判断题【×】1.二叉树是普通树的特殊树型。【√】2.树与二叉树是两种不同的树形构造。【×】3.对于有n个结点的二叉树，其高度为log2n。【√】4.完全二叉树中，若一种没有左孩子，则它必然是叶结点。【√】5.一棵含有n个结点的完全二叉树，从上到下、从左到右用自然数对结点进行编号，结点为i的结点的左孩子的编号为2i(2i<n)。【×】6.一棵树中的叶结点数一定等于与其对应的二叉树的叶结点数。【√】7.哈夫曼树是带权途径长度最短的树，路经上权值较大的结点离根近来。【√】8.哈夫曼树的结点个数不偶数。三、填空题1.深度为k的完全二叉树最少有2K-1个结点，至多有2K-1个结点。2.在一棵二叉树中，度为0的结点个数为n0，度为2的结点个数为n2,则有n0=n2+1。3.一棵二叉树第i层最多有2i-1个结点，一棵有n个结点的满二叉树共有2K-1个结点，共有2K-1个叶结点。4.根据二叉树的定义，含有3个结点的二叉树共有5种不同形态，它们分别是。5.在一棵完全二叉树中，结点个数为n，则编号最大的分支结点的编号为.?n/2?。6.在一棵完全二叉树中，编号i和j的两个结点处在同一层的条件是.?log2i?==.?log2j?。7.含有n个结点的二叉树采用二叉链表存储构造，共有n+1个空指针域。8.含有n个结点的二叉树中，如果有m个叶结点，则一定有m-1个度为2的结点，有n-2m+1个度为1的结点。9.在二叉树的链式存储构造中，指针p所指结点为叶结点的条件是p->lchild==NULL&&p->rchild==NULL。10.二叉树的先序序列和中序序列相等的条件是任何结点至多只有右子树。11.有一棵以下图所示的树，回答下列问题：①这棵树的根结点是a。②这棵树的叶子结点是b,e,g,d。③结点c的度为2。④这棵树的深度是4。⑤结点c的孩子结点是e,f。⑥结点c的双亲结点是a。⑦这棵树的度是3。aabcdefg12.树与二叉树的两个重要差别是树中结点的最大度没有限制，二叉树结点的最大度限定为2、树的结点无左右之分，二叉树的的结点有左右之分。13.树中任一结点允许有0个或多个孩子个孩子结点，除根结点之外，其它结点有1个双亲结点。四、简答题1.设有以下图所示的二叉树，给出其前序、中序和后序遍历成果。答：前序序列：eadcbifghj中序序列：abcdiefhgj后序序列：bcidahjgfeeeafdigcjbh2.给出下图所示的树的二叉树表达。eeafdigcjbhk答：下图为其树的二叉树表达。eeadfcbhgijk3.有一份电文共有5个字符：a,b,c,d,e,它们出现的频率依次为4，7，5，2，9，构造对应的哈夫曼树，求哈夫曼树的带权途径长度和每个字符的哈夫曼编码。11117956421627字符编码：a：011b：10c：00d：010e：114.假设一棵二叉树采用次序存储构造，以下图所示。05101520eafdgcjhib回答些列问题：①画出二叉树表达。②写出先序、中序和后序遍历成果③写出结点c的双亲结点和左、右孩子结点④画出此二叉树还原成森林的图aefdaefdjhbgci②先序序列为：eadcbjfghi中序序列为：acbdjefhgi后序序列为：bcjdahigfe③结点c的双亲结点是d，左孩子为b，无右孩子④该二叉树对应的森林为aefaefdjhbgci一、单选题1.在一种无向图中，全部顶点的度数之和等于全部边的【C】倍。A.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个顶点的无向图，若采用邻接矩阵表达，则该矩阵的大小是【D】。A.nB.(n-1)2C.(n-1)D.n27.对某个无向图的邻接矩阵来说，【A】。A.第i行上的非0元素个数等于第i列上非0元素个数B.矩阵中非0元素个数等于图中的边数C.第i行、第i列上非0元素个数等于顶点vi的度数D.矩阵中非全0行的行数等于图中的顶点数8.对于一种含有n个顶点和e条边的无向图，若采用邻接表表达，则表头向量的大小为【①A】；全部邻接表中结点总数为【②C】。①A.nB.n+1C.n-1D.n2②A.e/2B.eC.2eD.n+e二、判断题【×】1.n个顶点的无向图至多有n(n-1)条边。【√】2.有向图中，各顶点的入度之和等于各顶点的出度之和。【√】3.邻接矩阵只存储了边的信息，没有存储顶点的信息。【×】4.连通分量是无向图的极小连通子图。。【×】5.如果表达有向图的邻接矩阵是对称的，则该有向图一定是完全有向图。【×】6.如果表达图的邻接矩阵是对称的，则该图一定是无向图。【√】7.如果表达图的邻接矩阵不是对称的，则该图一定是有向图。三、填空题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行对应的1置成0。9.对于n的顶点的无向图，采用邻接矩阵表达，求图中边的办法是计算邻接矩阵中元素值为1的个数，判断任意两个顶点与否有边相连的办法是判断对应邻接矩阵元素的值与否为1，再除以2，求任意顶点的度的办法是求邻接矩阵中对应顶点所在行值为1的元素个数。10.对于n的顶点的有向图，采用邻接矩阵表达，求图中边的办法是计算邻接矩阵中元素值为1的个数，判断任意两个顶点与否有边相连的办法是判断对应邻接矩阵元素的值与否为1，求任意顶点的度的办法是求邻接矩阵中对应顶点所在行和列的元素值为1的个数。11.无向图的连通分量指无向图中最大连通子图。12.若无向图有m条边，，则表达该无向图的邻接表中有2m结点。四、简答题1.从占用的存储空间来看，对于稠密图和稀疏图，采用邻接矩阵和邻接表那个更加好些？答：从占用存储空间看，稠密图采用邻接矩阵更加好，稀疏图采用邻接表更加好。2.用邻接矩阵表达图时，矩阵元素的个数与顶点个数与否有关？与边的条数与否有关？为什么？。答：用邻接矩阵表达图，矩阵元素的个数与图的顶点个数直接有关，与边的条数无关。由于假设定点个数为n，则邻接矩阵的大小为n2。

第九章查找一、单选题1.次序查找法适合于存储构造为【B】的查找表。A.散列存储B.次序存储或链式存储C.压缩存储D.索引存储2.对查找表进行折半查找时，规定查找表必须【B】。A.以次序方式存储B.以次序方式存储，且结点按核心字有序排列C.以链式方式存储D.以链式方式存储，且结点按核心字有序排列3.采用次序查找法查找长度为n的查找表时，每个元素查找的平均查找长度为【C】。A.nB.n/2C.(n+1)/2D.(n-1)/24.采用折半查找法查找长度为n的查找表时，每个元素查找的平均查找长度为【D】。A.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.二叉排序树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.下列说法错误的是【B】。A.散列法存储的基本思想是由统计核心字决定数据存储地址B.散列法的结点中只包含数据元素本身的信息，不包含任何指针C.装填因子是散列法的一种重要参数，它反映了散列表的装填程度D.散列表的查找效率取决于散列造表是的散列函数和冲突解决的办法12.散列表的平均查找长度【A】。A.与冲突解决办法有关而与表的长度无关B.与冲突解决办法无关而与表的长度有关C.与冲突解决办法有关且与表的长度有关D.与冲突解决办法无关且与表的长度无关二、判断题【√】1.次序查找法适合于次序或链式存储构造的查找表。【×】2.次序查找法只能在次序存储构造上进行。【×】3.二分查找能够在有序的双向链表上进行。【×】4.在二叉排序树中，每个结点的核心字比左孩子的核心字大，比右孩子的核心字小。【×】5.每个结点的核心字都比左孩子的核心字大，比右孩子的核心字小，这样的二叉树都是二叉排序树。【√】6.哈希存储法只能存储数据元素的值，不能存储数据元素之间的关系。【×】7.哈希冲突是指同一种核心字对应多个不同的哈希地址。三、填空题1.次序查找含n个元素的次序表，若查找成功，则比较核心字的次数最多为n次；若查找不成功，则比较核心字的次数为n+1次。2.在含有n个元素的有序次序表中进行二分查找，最大的比较次数是.?log2n?+1。3.用二分查找一种查找表，该查找表必须含有的特点是次序存储且核心字有序。4.分块查找发将待查找的表均匀地分成若干块且块中诸统计的次序能够是任意的，但块与块之间核心字有序。5.在分块查找办法中，首先查找核心字表，然后再查找对应的对应的块。6.用二叉排序树在n个元素中进行查找，最坏状况下查找时间复杂度为O(n)，最佳状况的查找时间复杂度为O(log2n)。7.折半查找的存储构造仅限于次序存储构造，且是核心字有序排列。8.一种无序序列能够通过构造一棵二叉排序树而变成有序序列，构造树的过程即是对无序序列进行排序的过程。9.用二叉排序树查找，在最坏的状况下，平均查找长度为（n+1）/2，最佳的状况下，平均查找长度为.(log2n+1)-1。10.在哈希函数H(key)=key/p中，p最佳取不大于或等于m的最大质数。11.哈希表是通过将核心字按选定的哈希函数和冲突解决办法，把统计按核心字转换为地址进行存储的存储表，哈希办法的核心是选择好的哈希函数和冲突解决的办法。一种好的哈希函数其转换地址应尽量均匀，并且函数运算应尽量简朴。四、解答题1、画出对长度为10的右序