13994数据结构习题及参考答案.doc 45页

'习题1一、单项选择题1.数据结构是指（A）。A.数据元素的组织形式B.数据类型C.数据存储结构D.数据定义2.数据在计算机存储器内表示时，物理地址与逻辑地址不相同的，称之为（C）。A.存储结构B.逻辑结构C.链式存储结构D.顺序存储结构3.树形结构是数据元素之间存在一种（D）。A.一对一关系B.多对多关系C.多对一关系D.一对多关系4.设语句x++的时间是单位时间，则以下语句的时间复杂度为（B）。for(i=1;i<=n;i++)for(j=i;j<=n;j++)x++;A.O(1)B.O()C.O(n)D.O()5.算法分析的目的是（C），算法分析的两个主要方面是（A）。（1）A.找出数据结构的合理性B.研究算法中的输入和输出关系C.分析算法的效率以求改进D.分析算法的易懂性和文档性（2）A.空间复杂度和时间复杂度B.正确性和简明性C.可读性和文档性D.数据复杂性和程序复杂性6.计算机算法指的是（C），它具备输入，输出和（B）等五个特性。（1）A.计算方法B.排序方法C.解决问题的有限运算序列D.调度方法（2）A.可行性，可移植性和可扩充性B.可行性，确定性和有穷性C.确定性，有穷性和稳定性D.易读性，稳定性和安全性7.数据在计算机内有链式和顺序两种存储方式，在存储空间使用的灵活性上，链式存储比顺序存储要（B）。A.低B.高C.相同D.不好说8.数据结构作为一门独立的课程出现是在（D）年。A.1946B.1953C.1964D.19689.数据结构只是研究数据的逻辑结构和物理结构，这种观点（B）。A.正确B.错误C.前半句对，后半句错D.前半句错，后半句对10.计算机内部数据处理的基本单位是（B）。A.数据B.数据元素C.数据项D.数据库二、填空题1.数据结构按逻辑结构可分为两大类，分别是__线性结构和___非线性结构______________。2.数据的逻辑结构有四种基本形态，分别是___集合_____________、_____线性_____________、_____树_____________和______图____________。3.线性结构反映结点间的逻辑关系是__________________ 的，非线性结构反映结点间的逻辑关系是__________________的。4.一个算法的效率可分为__________________效率和__________________效率。5.在树型结构中，树根结点没有__________________结点，其余每个结点的有且只有__________________个前趋驱结点；叶子结点没有__________________结点；其余每个结点的后续结点可以__________________。6.在图型结构中，每个结点的前趋结点数和后续结点数可以__________________。7.线性结构中元素之间存在__________________关系；树型结构中元素之间存在__________________关系；图型结构中元素之间存在__________________关系。8.下面程序段的时间复杂度是__________________。for(i=0;i=0)&&A[i]!=k))j--;return(i);5.fact(n){if(n<=1)return(1);elsereturn(n*fact(n-1));}习题1参考答案一、单项选择题1.A2.C3.D4.B5.C、A6.C、B7.B8.D9.B10.B二、填空题1.线性结构，非线性结构2.集合，线性，树，图3.一对一，一对多或多对多4.时间，空间5.前趋，一，后继，多6.有多个7.一对一，一对多，多对多8.O()9.O()10.O()11.O(logn)12.程序对于精心设计的典型合法数据输入能得出符合要求的结果。13.事后统计，事前估计三、算法设计题1.O()2.O()3.O(n)4.O(n)5.O(n) 习题2一、单项选择题1.线性表是________。A．一个有限序列，可以为空B．一个有限序列，不可以为空C．一个无限序列，可以为空D．一个无限序列，不可以为空2.在一个长度为n的顺序表中删除第i个元素(0<=i<=n)时，需向前移动个元素。A．n-iB．n-i+lC．n-i-1D．i3.线性表采用链式存储时，其地址________。A．必须是连续的B．一定是不连续的C．部分地址必须是连续的D．连续与否均可以4.从一个具有n个结点的单链表中查找其值等于x的结点时，在查找成功的情况下，需平均比较________个元素结点。A．n/2B．nC．（n+1）/2D．（n-1）/25.在双向循环链表中，在p所指的结点之后插入s指针所指的结点，其操作是____。A．p->next=s;s->prior=p;p->next->prior=s;s->next=p->next;B．s->prior=p;s->next=p->next;p->next=s;p->next->prior=s;C．p->next=s;p->next->prior=s;s->prior=p;s->next=p->next;D．s->prior=p;s->next=p->next;p->next->prior=s;p->next=s;6.设单链表中指针p指向结点m，若要删除m之后的结点（若存在），则需修改指针的操作为________。A．p->next=p->next->next;B．p=p->next;C．p=p->next->next;D．p->next=p;7.在一个长度为n的顺序表中向第i个元素(0next=p->next;p->next=sB．q->next=s;s->next=pC．p->next=s->next;s->next=pD．p->next=s;s->next=q9.以下关于线性表的说法不正确的是______。 A．线性表中的数据元素可以是数字、字符、记录等不同类型。B．线性表中包含的数据元素个数不是任意的。C．线性表中的每个结点都有且只有一个直接前趋和直接后继。D．存在这样的线性表：表中各结点都没有直接前趋和直接后继。10.线性表的顺序存储结构是一种_______的存储结构。 A．随机存取B．顺序存取C．索引存取D．散列存取11.在顺序表中，只要知道_______，就可在相同时间内求出任一结点的存储地址。 A．基地址B．结点大小C．向量大小D．基地址和结点大小12.在等概率情况下，顺序表的插入操作要移动______结点。 A．全部B．一半 C．三分之一 D．四分之一13.在______运算中，使用顺序表比链表好。 A．插入 B．删除 C．根据序号查找 D．根据元素值查找14.在一个具有n个结点的有序单链表中插入一个新结点并保持该表有序的时间复杂度是_______。 A．O(1) B．O(n) C．O(n2)D．O(log2n)15.设有一个栈，元素的进栈次序为A,B,C,D,E,下列是不可能的出栈序列__________。A．A,B,C,D,EB．B,C,D,E,AC．E,A,B,C,DD．E,D,C,B,A16.在一个具有n个单元的顺序栈中，假定以地址低端（即0单元）作为栈底，以top作为栈顶指针，当做出栈处理时，top变化为______。A．top不变B．top=0C．top--D．top++17.向一个栈顶指针为hs的链栈中插入一个s结点时，应执行______。A．hs->next=s;B．s->next=hs;hs=s;C．s->next=hs->next;hs->next=s;D．s->next=hs;hs=hs->next;18.在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队头指针和队尾指针，则判断队满的条件为________。A．rear％n==frontB．（front+l）％n==rearC．rear％n-1==frontD．(rear+l)％n==front19.在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队头指针和队尾指针，则判断队空的条件为________。A．rear％n==frontB．front+l=rearC．rear==frontD．(rear+l)％n=front20.在一个链队列中，假定front和rear分别为队首和队尾指针，则删除一个结点的操作为________。A．front=front->next　B．rear=rear->nextC．rear=front->next　D．front=rear->next二、填空题1.线性表是一种典型的_________结构。2.在一个长度为n的顺序表的第i个元素之前插入一个元素，需要后移____个元素。3.顺序表中逻辑上相邻的元素的物理位置________。4.要从一个顺序表删除一个元素时，被删除元素之后的所有元素均需_______一个位置，移动过程是从_______向_______依次移动每一个元素。5.在线性表的顺序存储中，元素之间的逻辑关系是通过_______决定的；在线性表的链接存储中，元素之间的逻辑关系是通过_______决定的。6.在双向链表中，每个结点含有两个指针域，一个指向_______结点，另一个指向_______结点。7.当对一个线性表经常进行存取操作，而很少进行插入和删除操作时，则采用_______ 存储结构为宜。相反，当经常进行的是插入和删除操作时，则采用_______存储结构为宜。8.顺序表中逻辑上相邻的元素，物理位置_______相邻，单链表中逻辑上相邻的元素，物理位置_______相邻。9.线性表、栈和队列都是_______结构，可以在线性表的______位置插入和删除元素；对于栈只能在_______位置插入和删除元素；对于队列只能在_______位置插入元素和在_______位置删除元素。10.根据线性表的链式存储结构中每个结点所含指针的个数，链表可分为_________和_______；而根据指针的联接方式，链表又可分为________和_________。11.在单链表中设置头结点的作用是________。12.对于一个具有n个结点的单链表，在已知的结点p后插入一个新结点的时间复杂度为______，在给定值为x的结点后插入一个新结点的时间复杂度为_______。13.对于一个栈作进栈运算时，应先判别栈是否为_______，作退栈运算时，应先判别栈是否为_______，当栈中元素为m时，作进栈运算时发生上溢，则说明栈的可用最大容量为_______。为了增加内存空间的利用率和减少发生上溢的可能性，由两个栈共享一片连续的内存空间时，应将两栈的_______分别设在这片内存空间的两端，这样只有当_______时才产生上溢。14.设有一空栈，现有输入序列1，2，3，4，5，经过push,push,pop,push,pop,push,push后，输出序列是_________。15.无论对于顺序存储还是链式存储的栈和队列来说，进行插入或删除运算的时间复杂度均相同为__________。三、简答题1.描述以下三个概念的区别：头指针，头结点，表头结点。2.线性表的两种存储结构各有哪些优缺点？3.对于线性表的两种存储结构，如果有n个线性表同时并存，而且在处理过程中各表的长度会动态发生变化，线性表的总数也会自动改变，在此情况下，应选用哪一种存储结构？为什么？4.对于线性表的两种存储结构，若线性表的总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素，应选用何种存储结构？试说明理由。5.在单循环链表中设置尾指针比设置头指针好吗？为什么?6.假定有四个元素A,B,C,D依次进栈，进栈过程中允许出栈，试写出所有可能的出栈序列。7.什么是队列的上溢现象？一般有几种解决方法，试简述之。8.下述算法的功能是什么?LinkList*Demo(LinkList*L){//L是无头结点的单链表LinkList*q,*p;if(L&&L->next){q=L;L=L->next;p=L;　　　while(p->next)p=p->next;　　p->next=q;q->next=NULL;　　}　　return(L);}四、算法设计题1.设计在无头结点的单链表中删除第i个结点的算法。2.在单链表上实现线性表的求表长ListLength(L)运算。3.设计将带表头的链表逆置算法。 4.假设有一个带表头结点的链表，表头指针为head，每个结点含三个域：data,next和prior。其中data为整型数域，next和prior均为指针域。现在所有结点已经由next域连接起来，试编一个算法，利用prior域（此域初值为NULL）把所有结点按照其值从小到大的顺序链接起来。5.已知线性表的元素按递增顺序排列，并以带头结点的单链表作存储结构。试编写一个删除表中所有值大于min且小于max的元素（若表中存在这样的元素）的算法。6.已知线性表的元素是无序的，且以带头结点的单链表作为存储结构。设计一个删除表中所有值小于max但大于min的元素的算法。7.假定用一个单循环链表来表示队列（也称为循环队列），该队列只设一个队尾指针，不设队首指针，试编写下列各种运算的算法：（1）向循环链队列插入一个元素值为x的结点；（2）从循环链队列中删除一个结点。8.设顺序表L是一个递减有序表，试写一算法，将x插入其后仍保持L的有序性。习题2参考答案一、单项选择题1．A2．A3．D4．C5．D6．A7．B8．B9．C10．A11．D12．B13．C14．B15．C16．C17．B18．D19．C20．A二、填空题1．线性2．n-i+13．相邻4．前移，前，后5．物理存储位置，链域的指针值6．前趋，后继7．顺序，链接8．一定，不一定9．线性，任何，栈顶，队尾，队头10．单链表，双链表，非循环链表，循环链表11．使空表和非空表统一；算法处理一致12．O(1)，O(n)13．栈满，栈空，m，栈底，两个栈的栈顶在栈空间的某一位置相遇14．2、315．O(1)三、简答题1．头指针是指向链表中第一个结点（即表头结点）的指针；在表头结点之前附设的结点称为头结点；表头结点为链表中存储线性表中第一个数据元素的结点。若链表中附设头结点，则不管线性表是否为空表，头指针均不为空，否则表示空表的链表的头指针为空。2．线性表具有两种存储结构即顺序存储结构和链接存储结构。线性表的顺序存储结构可以直接存取数据元素，方便灵活、效率高，但插入、删除操作时将会引起元素的大量移动，因而降低效率：而在链接存储结构中内存采用动态分配，利用率高，但需增设指示结点之间关系的指针域，存取数据元素不如顺序存储方便，但结点的插入、删除操作较简单。3 ．应选用链接存储结构，因为链式存储结构是用一组任意的存储单元依次存储线性表中的各元素，这里存储单元可以是连续的，也可以是不连续的：这种存储结构对于元素的删除或插入运算是不需要移动元素的，只需修改指针即可，所以很容易实现表的容量的扩充。4．应选用顺序存储结构，因为每个数据元素的存储位置和线性表的起始位置相差一个和数据元素在线性表中的序号成正比的常数。因此，只要确定了其起始位置，线性表中的任一个数据元素都可随机存取，因此，线性表的顺序存储结构是一种随机存取的存储结构，而链表则是一种顺序存取的存储结构。5．设尾指针比设头指针好。尾指针是指向终端结点的指针，用它来表示单循环链表可以使得查找链表的开始结点和终端结点都很方便，设一带头结点的单循环链表，其尾指针为rear，则开始结点和终端结点的位置分别是rear->next->next和rear,查找时间都是O(1)。若用头指针来表示该链表，则查找终端结点的时间为O(n)。6．共有14种可能的出栈序列，即为：ABCD,ABDC，ACBD,ACDB，BACD，ADCB，BADC，BCAD,BCDA，BDCA,CBAD,CBDA，CDBA,DCBA7．在队列的顺序存储结构中，设队头指针为front，队尾指针为rear，队列的容量（即存储的空间大小）为maxnum。当有元素要加入队列（即入队）时，若rear=maxnum，则会发生队列的上溢现象，此时就不能将该元素加入队列。对于队列，还有一种“假溢出”现象，队列中尚余有足够的空间，但元素却不能入队，一般是由于队列的存储结构或操作方式的选择不当所致，可以用循环队列解决。一般地，要解决队列的上溢现象可有以下几种方法：（1）可建立一个足够大的存储空间以避免溢出，但这样做往往会造成空间使用率低，浪费存储空间。（2）要避免出现“假溢出”现象可用以下方法解决：第一种：采用移动元素的方法。每当有一个新元素入队，就将队列中已有的元素向队头移动一个位置，假定空余空间足够。第二种：每当删去一个队头元素，则可依次移动队列中的元素总是使front指针指向队列中的第一个位置。第三种：采用循环队列方式。将队头、队尾看作是一个首尾相接的循环队列，即用循环数组实现，此时队首仍在队尾之前，作插入和删除运算时仍遵循“先进先出”的原则。8．该算法的功能是：将开始结点摘下链接到终端结点之后成为新的终端结点，而原来的第二个结点成为新的开始结点，返回新链表的头指针。四、算法设计题1．算法思想为：（1）应判断删除位置的合法性，当i<0或i>n-1时，不允许进行删除操作；（2）当i=0时，删除第一个结点：（3）当０next;free(s);} else{j=0;s=q;while((jnext;j++;}if(s==NULL)printf("Cant"tdelete");else{p->next=s->next;free(s);}}}2．由于在单链表中只给出一个头指针，所以只能用遍历的方法来数单链表中的结点个数了。算法描述如下：intListLength(LinkList*L){//求带头结点的单链表的表长　intlen=0;　ListList*p;　p=L;　while(p->next!=NULL){p=p->next;　　　len++;　}　return(len);}3．设单循环链表的头指针为head，类型为LinkList。逆置时需将每一个结点的指针域作以修改，使其原前趋结点成为后继。如要更改q结点的指针域时，设s指向其原前趋结点，p指向其原后继结点，则只需进行q->next=s;操作即可，算法描述如下：voidinvert(LinkList*head){//逆置head指针所指向的单循环链表linklist*p,*q,*s;q=head;p=head->next;while(p!=head)//当表不为空时，逐个结点逆置{s=q;q=p;p=p->next;q->next=s;}p->next=q;}4．定义类型LinkList如下：typedefstructnode{intdata;structnode*next,*prior;}LinkList; 此题可采用插入排序的方法，设p指向待插入的结点，用q搜索已由prior域链接的有序表找到合适位置将p结点链入。算法描述如下：insert(LinkList*head){LinkList*p,*s,*q;p=head->next;//p指向待插入的结点，初始时指向第一个结点while(p!=NULL){s=head;//s指向q结点的前趋结点q=head->prior;//q指向由prior域构成的链表中待比较的结点while((q!=NULL)&&(p->data>q->data))//查找插入结点p的合适的插入位置{s=q;q=q->prior;}s->prior=p;p->prior=q;//结点p插入到结点s和结点q之间p=p->next;}}5．算法描述如下：delete(LinkList*head,intmax,intmin){linklist*p,*q;if(head!=NULL){q=head;p=head->next;while((p!=NULL)&&(p->data<=min)){q=p;p=p->next;}while((p!=NULL)&&(p->datanext;q->next=p;　}}6．算法描述如下：delete(LinkList*head,intmax,intmin){LinkList*p,*q;q=head;p=head->next;while(p!=NULL)if((p->data<=min)||(p->data>=max)){q=p;p=p->next;}else{q->next=p->next;free(p);p=q->next;}}7 ．本题是对一个循环链队列做插入和删除运算，假设不需要保留被删结点的值和不需要回收结点，算法描述如下：（1）插入（即入队）算法：insert(LinkList*rear,elemtypex){//设循环链队列的队尾指针为rear,x为待插入的元素LinkList*p;p=(LinkList*)malloc(sizeof(LinkList));if(rear==NULL)//如为空队，建立循环链队列的第一个结点{rear=p;rear->next=p;//链接成循环链表}else//否则在队尾插入p结点{p->next=rear->next;rear->next=p;rear=p;}}（2）删除（即出队）算法：delete(LinkList*rear){//设循环链队列的队尾指针为rearif(rear==NULL)//空队printf("underflown");if(rear->next==rear)//队中只有一个结点rear=NULL;elserear->next=rear->next->next;//rear->next指向的结点为循环链队列的队头结点}8．只要从终端结点开始往前找到第一个比x大(或相等)的结点数据，在这个位置插入就可以了。算法描述如下：intInsertDecreaseList(SqList*L,elemtypex){inti;if((*L).len>=maxlen){printf(“overflow");return(0);}for(i=(*L).len;i>0&&(*L).elem[i-1]data!=pt->data))pt=pt->next;if(pt==NULL)ps=NULL;else{ps=ps->next;s=ps;}}returns;}//find 习题4一、单项选择题1.设二维数组A[0…m-1][0…n-1]按行优先顺序存储在内存中，第一个元素的地址为p，每个元素占k个字节，则元素aij的地址为（）。A.p+[i*n+j-1]*kB.p+[(i-1)*n+j-1]*kC.p+[(j-1)*n+i-1]*kD.p+[j*n+i-1]*k2.已知二维数组A10×10中，元素a20的地址为560，每个元素占4个字节，则元素a10的地址为（）。A.520B.522C.524D.5183.若数组A[0…m][0…n]按列优先顺序存储，则aij地址为（）。A.LOC(a00)+[j*m+i]B.LOC(a00)+[j*n+i]C.LOC(a00)+[(j-1)*n+i-1]D.LOC(a00)+[(j-1)*m+i-1]4.若下三角矩阵An×n，按列顺序压缩存储在数组Sa[0…(n+1)n/2]中，则非零元素aij的地址为（）。（设每个元素占d个字节）A.[(j-1)*n-+i-1]*dB.[(j-1)*n-+i]*dC．[(j-1)*n-+i+1]*dD．[(j-1)*n-+i-2]*d5.设有广义表D=(a,b,D)，其长度为（），深度为（）。A.无穷大B.3C.2D.56.广义表A=（a），则表尾为（）。A.aB.(())C.空表D.(a)7.广义表A=((x,(a,B)),(x,(a,B),y))，则运算head(head(tail(A)))的结果为（）。A.xB.(a,B)C.(x,(a,B))D.A8.下列广义表用图来表示时，分支结点最多的是（）。A.L=((x,(a,B)),(x,(a,B),y))B.A=(s,(a,B))C.B=((x,(a,B),y))D.D=((a,B),(c,(a,B),D)9.通常对数组进行的两种基本操作是（）。A.建立与删除B.索引和修改C.查找和修改D.查找与索引10.假定在数组A中，每个元素的长度为3个字节，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，存放该数组至少需要的单元数为（）。A.80B.100C.240D.27011.数组A中，每个元素的长度为3个字节，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，该数组按行存放时，元素A[8][5]的起始地址为（）。A.SA+141B.SA+144C.SA+222D.SA+225 12.稀疏矩阵一般的压缩存储方法有两种，即（）。A.二维数组和三维数组B.三元组和散列C.三元组和十字链表D.散列和十字链表13.若采用三元组压缩技术存储稀疏矩阵，只要把每个元素的行下标和列下标互换，就完成了对该矩阵的转置运算，这种观点（）。A.正确B.不正确14.一个广义表的表头总是一个（）。A.广义表B.元素C.空表D.元素或广义表15.一个广义表的表尾总是一个（）。A.广义表B.元素C.空表D.元素或广义表16.数组就是矩阵，矩阵就是数组，这种说法（）。A.正确B.错误C.前句对，后句错D.后句对二、填空题1.一维数组的逻辑结构是______________，存储结构是______________；对于二维或多维数组，分为______________和______________两种不同的存储方式。2.对于一个二维数组A[m][n]，若按行序为主序存储，则任一元素A[i][j]相对于A[0][0]的地址为______________。3.一个广义表为(a,(a,b),d,e,((i,j),k))，则该广义表的长度为_____，深度为_____。4.一个稀疏矩阵为，则对应的三元组线性表为_____________。5.一个n×n的对称矩阵，如果以行为主序或以列为主序存入内存，则其容量为______________。6.已知广义表A=((a,b,c),(d,e,f))，则运算head(tail(tail(A)))=____________。7.设有一个10阶的对称矩阵A，采用压缩存储方式以行序为主序存储，a为第一个元素，其存储地址为0，每个元素占有1个存储地址空间，则a的地址为______________。8.已知广义表Ls=(a,(b,c,d),e)，运用head和tail函数取出Ls中的原子b的运算是______________。9.三维数组R[c1…d1,c2…d2,c3…d3]共含有______________个元素。（其中：c1≤d1,c2≤d2,c3≤d3）10.数组A[1…10，-2…6，2…8]以行优先的顺序存储，设第一个元素的首地址是100，每个元素占3个存储长度的存储空间，则元素A[5，0，7]的存储地址为______________。三、判断题1.数组可看作基本线性表的一种推广，因此与线性表一样，可以对它进行插入、删除等操作。（） 2.多维数组可以看作数据元素也是基本线性表的基本线性表。（）3.以行为主序或以列为主序对于多维数组的存储没有影响。（）4.对于不同的特殊矩阵应该采用不同的存储方式。（）5.采用压缩存储之后，下三角矩阵的存储空间可以节约一半。（）6.在一般情况下，采用压缩存储之后，对称矩阵是所有特殊矩阵中存储空间节约最多的。（）7.矩阵不仅是表示多维数组，而且是表示图的重要工具。（）8.距阵中的数据元素可以是不同的数据类型。（）9.矩阵中的行列数往往是不相等的。（）10.广义表的表头可以是广义表，也可以是单个元素。（）11.广义表的表尾一定是一个广义表。（）12.广义表的元素可以是子表，也可以是单元素。（）13.广义表不能递归定义。（）14.广义表实际上是基本线性表的推广。（）15.广义表的组成元素可以是不同形式的元素。（）习题4参考答案一、单项选择题1.A2.A3.A4.B5.BA6.C7.A8.A9.C10.C11.C12.C13.B14.D15.A16.B二、填空题1.线性结构，顺序结构，以行为主序，以列为主序2.i×n+j个元素位置3.5，34.（（0，2，2），（1，0，3），（2，2，-1），（2，3，5））5.n×(n+1)/26.e7.418.head(head(tail(Ls)))9.（d-c+1）×（d-c+1）×（d-c+1）10.913三、判断题1.×2.√3.√4.√5.×6.×7.√8.×9.×10.√11.√12.√13.×14.√15.√ 习题5一、单项选择题1.在一棵度为3的树中，度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数为（）个。A.4B.5C.6D.72.假设在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子结点数为（）个。A.15B.16C.17D.473.假定一棵三叉树的结点数为50，则它的最小高度为（）。A.3B.4C.5D.64.在一棵二叉树上第4层的结点数最多为（）。A.2B.4C.6D.85.用顺序存储的方法将完全二叉树中的所有结点逐层存放在数组中R[1..n]，结点R[i]若有左孩子，其左孩子的编号为结点（）。A.R[2i+1]B.R[2i]C.R[i/2]D.R[2i-1]6.由权值分别为3,8,6,2,5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（）。A.24B.48C.72D.537.线索二叉树是一种（）结构。A.逻辑B.逻辑和存储C.物理D.线性8.线索二叉树中，结点p没有左子树的充要条件是（）。A.p->lc=NULLB.p->ltag=1C.p->ltag=1且p->lc=NULLD.以上都不对9.设n,m为一棵二叉树上的两个结点，在中序遍历序列中n在m前的条件是（）。A.n在m右方B.n在m左方C.n是m的祖先D.n是m的子孙10.如果F是由有序树T转换而来的二叉树，那么T中结点的前序就是F中结点的（）。A.中序B.前序C.后序D.层次序11.欲实现任意二叉树的后序遍历的非递归算法而不必使用栈，最佳方案是二叉树采用（）存储结构。A.三叉链表B.广义表C.二叉链表D.顺序12.下面叙述正确的是（）。A.二叉树是特殊的树B.二叉树等价于度为2的树C.完全二叉树必为满二叉树D.二叉树的左右子树有次序之分13.任何一棵二叉树的叶子结点在先序、中序和后序遍历序列中的相对次序（）。A.不发生改变B.发生改变C.不能确定D.以上都不对14.已知一棵完全二叉树的结点总数为9个，则最后一层的结点数为（）。A.1B.2C.3D.415.根据先序序列ABDC和中序序列DBAC确定对应的二叉树，该二叉树（）。A.是完全二叉树B.不是完全二叉树 C.是满二叉树D.不是满二叉树二、判断题1.二叉树中每个结点的度不能超过2，所以二叉树是一种特殊的树。（　）2.二叉树的前序遍历中，任意结点均处在其子女结点之前。（　）3.线索二叉树是一种逻辑结构。（　）4.哈夫曼树的总结点个数（多于1时）不能为偶数。（　）5.由二叉树的先序序列和后序序列可以唯一确定一颗二叉树。（　）6.树的后序遍历与其对应的二叉树的后序遍历序列相同。（　）7.根据任意一种遍历序列即可唯一确定对应的二叉树。（　）8.满二叉树也是完全二叉树。（　）9.哈夫曼树一定是完全二叉树。（　）10.树的子树是无序的。（　）三、填空题1.假定一棵树的广义表表示为A（B（E），C（F（H，I，J），G），D），则该树的度为_____，树的深度为_____，终端结点的个数为______，单分支结点的个数为______，双分支结点的个数为______，三分支结点的个数为_______，C结点的双亲结点为_______，其孩子结点为_______和_______结点。2.设F是一个森林，B是由F转换得到的二叉树，F中有n个非终端结点，则B中右指针域为空的结点有_______个。3.对于一个有n个结点的二叉树，当它为一棵________二叉树时具有最小高度，即为_______，当它为一棵单支树具有_______高度，即为_______。4.由带权为3，9，6，2，5的5个叶子结点构成一棵哈夫曼树，则带权路径长度为___。5.在一棵二叉排序树上按_______遍历得到的结点序列是一个有序序列。6.对于一棵具有n个结点的二叉树，当进行链接存储时，其二叉链表中的指针域的总数为_______个，其中_______个用于链接孩子结点，_______个空闲着。7.在一棵二叉树中，度为0的结点个数为n0，度为2的结点个数为n2，则n0=______。8.一棵深度为k的满二叉树的结点总数为_______，一棵深度为k的完全二叉树的结点总数的最小值为_____，最大值为______。9.由三个结点构成的二叉树，共有____种不同的形态。10.设高度为h的二叉树中只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为____。11.一棵含有n个结点的k叉树，______形态达到最大深度，____形态达到最小深度。12.对于一棵具有n个结点的二叉树，若一个结点的编号为i(1≤i≤n)，则它的左孩子结点的编号为________，右孩子结点的编号为________，双亲结点的编号为________。13.对于一棵具有n个结点的二叉树，采用二叉链表存储时，链表中指针域的总数为_________个，其中___________个用于链接孩子结点，_____________个空闲着。14.哈夫曼树是指________________________________________________的二叉树。15.空树是指________________________，最小的树是指_______________________。16.二叉树的链式存储结构有______________和_______________两种。17.三叉链表比二叉链表多一个指向______________的指针域。18.线索是指___________________________________________。19.线索链表中的rtag域值为_____时，表示该结点无右孩子，此时______域为指向该结点后继线索的指针。20.本节中我们学习的树的存储结构有_____________、___________和___________。 四、应用题1.已知一棵树边的集合为{，，，，，，，，，，，，}，请画出这棵树，并回答下列问题：（1）哪个是根结点？（2）哪些是叶子结点？（3）哪个是结点g的双亲？（4）哪些是结点g的祖先？（5）哪些是结点g的孩子？（6）哪些是结点e的孩子？（7）哪些是结点e的兄弟？哪些是结点f的兄弟？（8）结点b和n的层次号分别是什么？（9）树的深度是多少？（10）以结点c为根的子树深度是多少？2.一棵度为2的树与一棵二叉树有何区别。3.试分别画出具有3个结点的树和二叉树的所有不同形态？4.已知用一维数组存放的一棵完全二叉树：ABCDEFGHIJKL，写出该二叉树的先序、中序和后序遍历序列。5.一棵深度为H的满k叉树有如下性质：第H层上的结点都是叶子结点，其余各层上每个结点都有k棵非空子树，如果按层次自上至下，从左到右顺序从1开始对全部结点编号，回答下列问题：（1）各层的结点数目是多少？（2）编号为n的结点的父结点如果存在，编号是多少？（3）编号为n的结点的第i个孩子结点如果存在，编号是多少？（4）编号为n的结点有右兄弟的条件是什么？其右兄弟的编号是多少？6.找出所有满足下列条件的二叉树：（1）它们在先序遍历和中序遍历时，得到的遍历序列相同；（2）它们在后序遍历和中序遍历时，得到的遍历序列相同；（3）它们在先序遍历和后序遍历时，得到的遍历序列相同；7.假设一棵二叉树的先序序列为EBADCFHGIKJ，中序序列为ABCDEFGHIJK，请写出该二叉树的后序遍历序列。8.假设一棵二叉树的后序序列为DCEGBFHKJIA，中序序列为DCBGEAHFIJK，请写出该二叉树的后序遍历序列。9.给出如图5-14所示的森林的先根、后根遍历结点序列，然后画出该森林对应的二叉树。10．给定一组权值（5，9，11，2，7，16），试设计相应的哈夫曼树。五、算法设计题1.一棵具有n 个结点的完全二叉树以一维数组作为存储结构，试设计一个对该完全二叉树进行先序遍历的算法。2.给定一棵用二叉链表表示的二叉树，其中的指针t指向根结点，试写出从根开始，按层次遍历二叉树的算法，同层的结点按从左至右的次序访问。3.写出在中序线索二叉树中结点P的右子树中插入一个结点s的算法。4.给定一棵二叉树，用二叉链表表示，其根指针为t，试写出求该二叉树中结点n的双亲结点的算法。若没有结点n或者该结点没有双亲结点，分别输出相应的信息；若结点n有双亲，输出其双亲的值。习题5参考答案一、单项选择题1.C2.B3.C4.D5.B6.D7.C8.B9.B10.B11.A12.D13.A14.B15.A二、判断题1.×2.√3.×4.√5.×6.√7.√8.√9.×10.×三、填空题1.3，4，6，1，1，2，A，F，G2.n+13.完全，，最大，n4.555.中序6.2n，n-1，n+17.n2+18.2k-1，2k-1，2k-19.510.2h-111.单支树，完全二叉树12.2i，2i+1，i/2（或?i/2?）13.2n，n-1，n+114.带权路径长度最小15.结点数为0，只有一个根结点的树16.二叉链表，三叉链表17.双亲结点18.指向结点前驱和后继信息的指针19.1，RChild20.孩子表示法，双亲表示法，长子兄弟表示法四、应用题1.解答：根据给定的边确定的树如图5-15所示。其中根结点为a；叶子结点有：d、m、n、j、k、f、l；c是结点g的双亲； a、c是结点g的祖先；j、k是结点g的孩子；m、n是结点e的子孙；e是结点d的兄弟；g、h是结点f的兄弟；结点b和n的层次号分别是2和5；树的深度为5。2.解答：度为2的树有两个分支，但分支没有左右之分；一棵二叉树也有两个分支，但有左右之分，左右子树不能交换。3.解答：　略4.解答：　先序序列：ABDHIEJKCFLG中序序列：HDIBJEKALFCG后序序列：HIDJKEBLFGCA5.解答：（1）第i层上的结点数目是mi-1。（2）编号为n的结点的父结点如果存在，编号是((n-2)/m)+1。（3）编号为n的结点的第i个孩子结点如果存在，编号是(n-1)*m+i+1。（4）编号为n的结点有右兄弟的条件是(n-1)%m≠0。其右兄弟的编号是n+1。6.解答：（1）先序序列和中序序列相同的二叉树为：空树或者任一结点均无左孩子的非空二叉树；（2）中序序列和后序序列相同的二叉树为：空树或者任一结点均无右孩子的非空二叉树；（3）先序序列和后序序列相同的二叉树为：空树或仅有一个结点的二叉树。7.解答：后序序列：ACDBGJKIHFE8.解答：先序序列：ABCDGEIHFJK9.解答：先根遍历：ABCDEFGHIJKLMNO后根遍历：BDEFCAHJIGKNOML森林转换成二叉树如图5-16所示。10.解答：构造而成的哈夫曼树如图5-17所示。五、算法设计题1.解答：这个问题可以用递归算法，也可用非递归算法，下面给出的为非递归算法。假设该完全二叉树的结点以层次为序，按照从上到下，同层从左到右顺序编号，存放在一个一维数组R[1..n]中，且用一个有足够大容量为maxlen的顺序栈作辅助存储，算法描述如下：preorder(R)//先序遍历二叉树R intR[n];{introot;SqStack*s;//s为一个指针栈，类型为seqstack，其中包含top域和数组datas->top=-1;//s栈置空root=1;while((root<=n)&&(s->top>-1)){while(root<=n){printf(R[root]);s->top++;s->data[s->top]=root;root=2*root;}if(s->top>-1)//栈非空访问，遍历右子树{root=s->data[s->top]*2+1;s->top--;}}}2.解答：考虑用一个顺序队que来保存遍历过程中的各个结点，由于二叉树以二叉链表存储，所以可设que为一个指向数据类型为bitree的指针数组，最大容量为maxnum，下标从1开始，同层结点从左到右存放。算法中的front为队头指针，rear为队尾指针。levelorder(BiTree*t)//按层次遍历二叉树t{BiTree*que[maxnum];　　intrear,front;if(t!=NULL){front=0;//置空队列rear=1;que[1]=t;do{front=front%maxsize+1;//出队t=que[front];printf(t->data);if(t->lchild!=NULL)//左子树的根结点入队{rear=rear%maxsize+1;que[rear]=t->lchild;}if(t->rchild!=NULL)//右子树的根结点入队{rear=rear%maxsize+1;que[rear]=t->rchild;}}while(rear==front);//队列为空时结束}}3.解答：设该线索二叉树类型为bithptr，包含5个域：lchild，ltag，data，rchild，rtag。insert(p,s)//将s结点作为p的右子树插入BiThrNode*p,*s;{BiThrNode*q;if(p->rtag==1)//无右子树，则有右线索{s->rchild=p->rchild; s->rtag=1;p->rchild=s;p->rtag=0;}else{q=p->rchild;while(q->ltag==0)//查找p所指结点中序后继，即为其右子树中最左下的结点q=q->lchild;q->lchild=p->rchild;s->rtag=0;p->rchild=s;}s->lchild=p;//将s结点的左线索指向p结点s->ltag=1;}4.解答：利用一个队列来完成，设该队列类型为指针类型，最大容量为maxnum。算法中的front为队头指针，rear为队尾指针，若当前队头结点的左、右子树的根结点不是所求结点，则将两子树的根结点入队，否则，队头指针所指结点即为结点的双亲。parentjudge(t,n)BiTree*t;intn;{BiTree*que[maxnum];intfront,rear;BiTree*parent;parent=NULL;if(t)if(t->data==n)printf(“noparent!”);//n是根结点，无双亲else{front=0;//初始化队列rear=1;que[1]=t;//根结点进队do{front=front%maxsize+1;t=que[front];if((t->lchild->data==n)||(t->rchild->data==n))//结点n有双亲{parent=t;front=rear;printf(“parent”,t->data);}else{if(t->lchild!=NULL)//左子树的根结点入队{rear=rear%maxsize+1;que[rear]=t->lchild;}if(t->rchild!=NULL)//右子树的根结点入队{rear=rear%maxsize+1;que[rear]=t->rchild;} }}while(rear==front);//队空时结束if(parent==NULL)printf(“结点不存在”);}} 习题6一、单项选择题1.在一个具有n个顶点的有向图中，若所有顶点的出度数之和为s，则所有顶点的入度数之和为(　　)。A.sB.s-1C.s+1D.n2.在一个具有n个顶点的有向图中，若所有顶点的出度数之和为s，则所有顶点的度数之和为(　　)。A.sB.s-1C.s+1D.2s3.在一个具有n个顶点的无向图中，若具有e条边，则所有顶点的度数之和为(　　)。A.nB.eC.n+eD.2e4.在一个具有n个顶点的无向完全图中，所含的边数为(　　)。A.nB.n(n-1)C.n(n-1)/2D.n(n+1)/25.在一个具有n个顶点的有向完全图中，所含的边数为()。A.nB.n(n-1)C.n(n-1)/2D.n(n+1)/26.在一个无向图中，若两顶点之间的路径长度为k，则该路径上的顶点数为()。A.kB.k+1C.k+2D.2k7.对于一个具有n个顶点的无向连通图，它包含的连通分量的个数为()。A.0B.1C.nD.n+18.若一个图中包含有k个连通分量，若要按照深度优先搜索的方法访问所有顶点，则必须调用()次深度优先搜索遍历的算法。A.kB.1C.k-1D.k+19.若要把n个顶点连接为一个连通图，则至少需要()条边。A.nB.n+1C.n-1D.2n10.在一个具有n个顶点和e条边的无向图的邻接矩阵中，表示边存在的元素（又称为有效元素）的个数为()。A.nB.n´eC.eD.2´e11.在一个具有n个顶点和e条边的有向图的邻接矩阵中，表示边存在的元素个数为()。A.nB.n´eC.eD.2´e12.在一个具有n个顶点和e条边的无向图的邻接表中，边结点的个数为()。A.nB.n´eC.eD.2´e13.在一个具有n个顶点和e条边的有向图的邻接表中，保存顶点单链表的表头指针向量的大小至少为()。A.nB.2nC.eD.2e14.在一个无权图的邻接表表示中，每个边结点至少包含()域。A.1B.2C.3D.415.对于一个有向图，若一个顶点的度为k1，出度为k2，则对应邻接表中该顶点单链表中的边结点数为()。A.k1B.k2C.k1-k2D.k1+k216.对于一个有向图，若一个顶点的度为k1，出度为k2，则对应逆邻接表中该顶点单链表中的边结点数为()。A.k1B.k2C.k1-k2D.k1+k2 17.对于一个无向图，下面()种说法是正确的。A.每个顶点的入度等于出度B.每个顶点的度等于其入度与出度之和C.每个顶点的入度为0D.每个顶点的出度为018.在一个有向图的邻接表中，每个顶点单链表中结点的个数等于该顶点的()。A.出边数B.入边数C.度数D.度数减119.若一个图的边集为{(A,B),(A,C),(B,D),(C,F),(D,E),(D,F)}，则从顶点A开始对该图进行深度优先搜索，得到的顶点序列可能为()。A.A,B,C,F,D,EB.A,C,F,D,E,BC.A,B,D,C,F,ED.A,B,D,F,E,C20.若一个图的边集为{(A,B),(A,C),(B,D),(C,F),(D,E),(D,F)}，则从顶点A开始对该图进行广度优先搜索，得到的顶点序列可能为()。A.A,B,C,D,E,FB.A,B,C,F,D,EC.A,B,D,C,E,FD.A,C,B,F,D,E21.若一个图的边集为{<1,2>,<1,4>,<2,5>,<3,1>,<3,5>,<4,3>}，则从顶点1开始对该图进行深度优先搜索，得到的顶点序列可能为()。A.1,2,5,4,3B.1,2,3,4,5C.1,2,5,3,4D.1,4,3,2,522.若一个图的边集为{<1,2>,<1,4>,<2,5>,<3,1>,<3,5>,<4,3>}，则从顶点1开始对该图进行广度优先搜索，得到的顶点序列可能为()。A.1,2,3,4,5B.1,2,4,3,5C.1,2,4,5,3D.1,4,2,5,323.由一个具有n个顶点的连通图生成的最小生成树中，具有()条边。A.nB.n-1C.n+1D.2´n24.已知一个有向图的边集为{,,,,,}，则由该图产生的一种可能的拓扑序列为()。A.a,b,c,d,eB.a,b,d,e,bC.a,c,b,e,dD.a,c,d,b,e二、填空题1.在一个图中，所有顶点的度数之和等于所有边数的________倍。2.在一个具有n个顶点的无向完全图中，包含有________条边，在一个具有n个顶点的有向完全图中，包含有________条边。3.假定一个有向图的顶点集为{a,b,c,d,e,f}，边集为{,,,,,}，则出度为0的顶点个数为________，入度为1的顶点个数为________。4.在一个具有n个顶点的无向图中，要连通所有顶点则至少需要________条边。5.表示图的两种存储结构为__________和__________。6.在一个连通图中存在着________个连通分量。7.图中的一条路径长度为k，该路径所含的顶点数为________。8.若一个图的顶点集为{a,b,c,d,e,f}，边集为{(a,b),(a,c),(b,c),(d,e)}，则该图含有________个连通分量。9.对于一个具有n个顶点的图，若采用邻接矩阵表示，则矩阵大小至少为________´________。10.对于具有n个顶点和e条边的有向图和无向图，在它们对应的邻接表中，所含边结点的个数分别为________和________。11.在有向图的邻接表和逆邻接表表示中，每个顶点邻接表分别链接着该顶点的所有________和________结点。12.对于一个具有n个顶点和e条边的无向图，当分别采用邻接矩阵和邻接表表示时，求任一顶点度数的时间复杂度分别为________和________。 13.假定一个图具有n个顶点和e条边，则采用邻接矩阵和邻接表表示时，其相应的空间复杂度分别为________和________。14.一个图的边集为{(a,c),(a,e),(b,e),(c,d),(d,e)}，从顶点a出发进行深度优先搜索遍历得到的顶点序列为____________，从顶点a出发进行广度优先搜索遍历得到的顶点序列为____________。15.一个图的边集为{,,,,,}，从顶点a出发进行深度优先搜索遍历得到的顶点序列为____________，从顶点a出发进行广度优先搜索遍历得到的顶点序列为____________。16.图的________优先搜索遍历算法是一种递归算法，图的________优先搜索遍历算法需要使用队列。17.对于一个具有n个顶点和e条边的连通图，其生成树中的顶点数和边数分别为________和________。18.若一个连通图中每个边上的权值均不同，则得到的最小生成树是________（唯一/不唯一）的。19.根据图的存储结构进行某种次序的遍历，得到的顶点序列是__（唯一/不唯一）的。20.假定一个有向图的边集为{,,,,,}，对该图进行拓扑排序得到的顶点序列为________。三、应用题1.对于一个无向图6-11(a)，假定采用邻接矩阵表示，试分别写出从顶点0出发按深度优先搜索遍历得到的顶点序列和按广度优先搜索遍历得到的顶点序列。注：每一种序列都是唯一的，因为都是在存储结构上得到的。2.对于一个有向图6-11(b)，假定采用邻接表表示，并且假定每个顶点单链表中的边结点是按出边邻接点序号从大到小的次序链接的，试分别写出从顶点0出发按深度优先搜索遍历得到的顶点序列和按广度优先搜索遍历得到的顶点序列。注：每一种序列都是唯一的，因为都是在存储结构上得到的。3.已知一个无向图的邻接矩阵如图6-12(a)所示，试写出从顶点0出发分别进行深度优先和广度优先搜索遍历得到的顶点序列。4.已知一个无向图的邻接表如图6-12(b)所示，试写出从顶点0出发分别进行深度优先和广度优先搜索遍历得到的顶点序列。 5.已知图6-13所示的一个网，按照Prim方法，从顶点1出发，求该网的最小生成树的产生过程。6.已知图6-13所示的一个网，按照Kruskal方法，求该网的最小生成树的产生过程。7.图6-14所示为一个有向网图及其带权邻接矩阵，要求对有向图采用Dijkstra算法，求从V0到其余各顶点的最短路径。8.图6-15给出了一个具有15个活动、11个事件的工程的AOE网，求关键路径。 四、算法设计题1.编写一个算法，求出邻接矩阵表示的无向图中序号为numb的顶点的度数。intdegree1(Graph&ga,intnumb)2.编写一个算法，求出邻接矩阵表示的有向图中序号为numb的顶点的度数。intdegree2(Graph&ga,intnumb)3.编写一个算法，求出邻接表表示的无向图中序号为numb的顶点的度数。intdegree3(GraphL&gl,intnumb)4.编写一个算法，求出邻接表表示的有向图中序号为numb的顶点的度数。intdegree4(GraphL&gl,intnumb)习题6参考答案一、单项选择题1.A2.D3.D4.C5.B6.B7.B8.A9.C10.D11.C12.D13.A14.B15.B16.C17.A18.A19.B20.D21.A22.C23.B24.A二、填空题1.22.n(n-1)/2，n(n-1)3.2，4　　4.n-15.邻接矩阵，邻接表6.17.k+18.39.n，n10.2e，e11.出边，入边12.O（n），O（e/n）13.O（n2），O（n+e）14.acdeb，acedb（答案不唯一）15.acfebd，acefbd（答案不唯一）16.深度，广度17.n，n-118.唯一19.唯一20.aebdcf（答案不唯一）三、应用题1.深度优先搜索序列：0,1,2,8,3,4,5,6,7,9广度优先搜索序列：0,1,4,2,7,3,8,6,5,92.深度优先搜索序列：0,4,7,5,8,3,6,1,2 广度优先搜索序列：0,4,3,1,7,5,6,2,83.深度优先搜索序列：0,2,3,5,6,1,4广度优先搜索序列：0,2,3,5,6,1,44.深度优先搜索序列：0,3,6,4,1,5,2广度优先搜索序列：0,3,2,6,5,4,15.过程如图6-16所示6.求解过程如图6-17所示。7.求解过程如下表所示。终点从v0到各终点的D值和最短路径的求解过程 i=1i=2i=3i=4i=5 V1∞∞∞∞∞无 ∞VjV2V4V3V5 S{v0,v2}{v0,v2,v4}{v0,v2,v3,v4}{v0,v2,v3,v4,v5} 8.求解过程如下：①事件的最早发生时间ve[k]。ve(1)=0ve(2)=3ve(3)=4ve(4)=ve(2)+2=5ve(5)=max{ve(2)+1,ve(3)+3}=7ve(6)=ve(3)+5=9ve(7)=max{ve(4)+6,ve(5)+8}=15ve(8)=ve(5)+4=11ve(9)=max{ve(8)+10,ve(6)+2}=21ve(10)=max{ve(8)+4,ve(9)+1}=22ve(11)=max{ve(7)+7,ve(10)+6}=28②事件的最迟发生时间vl[k]。vl(11)=ve(11)=28vl(10)=vl(11)-6=22vl(9)=vl(10)-1=21vl(8)=min{vl(10)-4,vl(9)-10}=11vl(7)=vl(11)-7=21vl(6)=vl(9)-2=19vl(5)=min{vl(7)-8,vl(8)-4}=7vl(4)=vl(7)-6=15vl(3)=min{vl(5)-3,vl(6)-5}=4vl(2)=min{vl(4)-2,vl(5)-1}=6vl(1)=min{vl(2)-3,vl(3)-4}=0③活动ai的最早开始时间e[i]和最晚开始时间l[i]。活动a1e(1)=ve(1)=0l(1)=vl(2)-3=3活动a2e(2)=ve(1)=0l(2)=vl(3)-4=0活动a3e(3)=ve(2)=3l(3)=vl(4)-2=13活动a4e(4)=ve(2)=3l(4)=vl(5)-1=6活动a5e(5)=ve(3)=4l(5)=vl(5)-3=4活动a6e(6)=ve(3)=4l(6)=vl(6)-5=14活动a7e(7)=ve(4)=5l(7)=vl(7)-6=15活动a8e(8)=ve(5)=7l(8)=vl(7)-8=13活动a9e(9)=ve(5)=7l(9)=vl(8)-4=7活动a10e(10)=ve(6)=9l(10)=vl(9)-2=19活动a11e(11)=ve(7)=15l(11)=vl(11)-7=21活动a12e(12)=ve(8)=11l(12)=vl(10)-4=18活动a13e(13)=ve(8)=11l(13)=vl(9)-10=11 活动a14e(14)=ve(9)=21l(14)=vl(10)-1=21活动a15e(15)=ve(10)=22l(15)=vl(11)-6=22④最后，比较e[i]和l[i]的值可判断出a2,a5,a9,a13,a14,a15是关键活动，关键路径如图6-18所示。四、算法设计题1.intdegree1(Graph&ga,intnumb){//根据无向图的邻接矩阵求出序号为numb的顶点的度数intj,d=0;for(j=0;jnext;}return(d);} 4.intdegree4(GraphL&gl,intnumb)//根据有向图的邻接表求出序号为numb的顶点的度数{intd=0,i;vexnode*p=gl.adjlist[numb];while(p!=NULL){d++;p=p->next;}//求出顶点numb的出度for(i=0;ivertex==numb)d++;p=p->next;}}//求出顶点numb的入度return(d);//返回顶点numb的度数} 习题7一、单项选择题1.若查找每个元素的概率相等，则在长度为n的顺序表上查找任一元素的平均查找长度为(　　)。A.nB.n+1C.(n-1)/2D.(n+1)/22.对于长度为9的顺序存储的有序表，若采用折半查找，在等概率情况下的平均查找长度为(　　)的9分之一。A.20B.18C.25D.223.对于长度为18的顺序存储的有序表，若采用折半查找，则查找第15个元素的比较次数为(　　)。A.3B.4C.5D.64.对于顺序存储的有序表(5,12,20,26,37,42,46,50,64)，若采用折半查找，则查找元素26的比较次数为(　　)。A.2B.3C.4D.55.对具有n个元素的有序表采用折半查找，则算法的时间复杂度为(　　)。A.O(n)B.O(n2)C.O(1)D.O(log2n)6.在索引查找中，若用于保存数据元素的主表的长度为n，它被均分为k个子表，每个子表的长度均为n/k，则索引查找的平均查找长度为(　　)。A.n+kB.k+n/kC.(k+n/k)/2D.(k+n/k)/2+17.在索引查找中，若用于保存数据元素的主表的长度为144，它被均分为12子表，每个子表的长度均为12，则索引查找的平均查找长度为(　　)。A.13B.24C.12D.798.从具有n个结点的二叉排序树中查找一个元素时，在平均情况下的时间复杂度大致为(　　)。A.O(n)B.O(1)C.O(log2n)D.O(n2)9.从具有n个结点的二叉排序树中查找一个元素时，在最坏情况下的时间复杂度为(　　)。A.O(n)B.O(1)C.O(log2n)D.O(n2)10.在一棵平衡二叉排序树中，每个结点的平衡因子的取值范围是(　　)。A.-1~1B.-2~2C.1~2D.0~111.若根据查找表(23,44,36,48,52,73,64,58)建立哈希表，采用h(K)=K%13计算哈希地址，则元素64的哈希地址为(　　)。A.4B.8C.12D.1312.若根据查找表(23,44,36,48,52,73,64,58)建立哈希表，采用h(K)=K%7计算哈希地址，则哈希地址等于3的元素个数(　　)。A.1B.2C.3D.413.若根据查找表建立长度为m的哈希表，采用线性探测法处理冲突，假定对一个元素第一次计算的哈希地址为d，则下一次的哈希地址为(　　)。A.dB.d+1C.(d+1)/mD.(d+1)%m二、填空题1.以顺序查找方法从长度为n的顺序表或单链表中查找一个元素时，平均查找长度为________，时间复杂度为________。 2.对长度为n的查找表进行查找时，假定查找第i个元素的概率为pi,查找长度（即在查找过程中依次同有关元素比较的总次数）为ci，则在查找成功情况下的平均查找长度的计算公式为________。3.假定一个顺序表的长度为40，并假定查找每个元素的概率都相同，则在查找成功情况下的平均查找长度________，在查找不成功情况下的平均查找长度________。4.以折半查找方法从长度为n的有序表中查找一个元素时，平均查找长度约等于________的向上取整减1，时间复杂度为________。5.以折半查找方法在一个查找表上进行查找时，该查找表必须组织成________存储的________表。6.从有序表(12,18,30,43,56,78,82,95)中分别折半查找43和56元素时，其比较次数分别为________和________。7.假定对长度n=50的有序表进行折半查找，则对应的判定树高度为________，最后一层的结点数为________。8.假定在索引查找中，查找表长度为n，每个子表的长度相等，设为s，则进行成功查找的平均查找长度为____________。9.在索引查找中，假定查找表（即主表）的长度为96，被等分为8个子表，则进行索引查找的平均查找长度为________。10.在一棵二叉排序树中，每个分支结点的左子树上所有结点的值一定________该结点的值，右子树上所有结点的值一定________该结点的值。11.对一棵二叉排序树进行中序遍历时，得到的结点序列是一个________。12.从一棵二叉排序树中查找一个元素时，若元素的值等于根结点的值，则表明_______，若元素的值小于根结点的值，则继续向________查找，若元素的值大于根结点的值，则继续向________查找。13.向一棵二叉排序树中插入一个元素时，若元素的值小于根结点的值，则接着向根结点的________插入，若元素的值大于根结点的值，则接着向根结点的________插入。14.根据n个元素建立一棵二叉排序树的时间复杂度大致为________。15.在一棵平衡二叉排序树中，每个结点的左子树高度与右子树高度之差的绝对值不超过________。16.假定对线性表(38,25,74,52,48)进行哈希存储，采用H(K)=K%7作为哈希函数，采用线性探测法处理冲突，则在建立哈希表的过程中，将会碰到________次存储冲突。17.假定对线性表(38,25,74,52,48)进行哈希存储，采用H(K)=K%7作为哈希函数，采用线性探测法处理冲突，则平均查找长度为________。18.在线性表的哈希存储中，装填因子a又称为装填系数，若用m表示哈希表的长度，n表示线性表中的元素的个数，则a等于________。19.对线性表(18,25,63,50,42,32,90)进行哈希存储时，若选用H(K)=K%9作为哈希函数，则哈希地址为0的元素有________个，哈希地址为5的元素有________个。三、应用题1.已知一个顺序存储的有序表为(15,26,34,39,45,56,58,63,74,76)，试画出对应的折半查找判定树，求出其平均查找长度。2.假定一个线性表为(38,52,25,74,68,16,30,54,90,72)，画出按线性表中元素的次序生成的一棵二叉排序树，求出其平均查找长度。3.假定一个待哈希存储的线性表为(32,75,29,63,48,94,25,46,18,70)，哈希地址空间为HT[13]，若采用除留余数法构造哈希函数和线性探测法处理冲突，试求出每一元素在哈希表中的初始哈希地址和最终哈希地址，画出最后得到的哈希表，求出平均查找长度。元素32752963489425461870 初始哈希地址最终哈希地址0123456789101112哈希表4.假定一个待哈希存储的线性表为(32,75,29,63,48,94,25,36,18,70,49,80)，哈希地址空间为HT[12]，若采用除留余数法构造哈希函数和拉链法处理冲突，试画出最后得到的哈希表，并求出平均查找长度。四、算法设计题1.试写一个判别给定二叉树是否为二叉排序树的算法，设此二叉树以二叉链表作为存储结构，且树中结点的关键字均不同。2.试将折半查找的算法改写成递归算法。习题7参考答案一、单项选择题1.D2.A3.B4.C5.D6.D7.A8.C9.A10.A11.C12.B13.D二、填空题1.(n+1)/2,O(n)2.3.20.5,414.élog2(n+1)ù，O(log2n)5.顺序有序6.1，37.6，198.(n/s+s)/2+19.1110.小于，大于11.有序序列12.查找成功，左子树，右子树13.左子树，右子树14.O(nlog2n)15.116.517.218.n/m19.3，2三、应用题1.折半查找判定树如图7-3所示，平均查找长度等于29/10。图7-3中的结点与有序表中元素的对应关系如下表所示。1234567891015263439455658637476 2.二叉排序树如图7-4所示，平均查找长度等于32/10。3.H(K)=K%13平均查找长度为14/10，其余解答如下。元素32752963489425461870初始哈希地址6103119312755最终哈希地址61031194127580123456789101112哈希表299418324670487563254.H(K)=K%11，哈希表如图7-5所示，平均查找长度17/12。四、算法设计题1.设计思路：进入判别算法之前，pre取初值为min(小于树中任一结点值)，fail=FALSE,即认为bt是二叉排序树。按中序遍历bt，并在沿向根结点，与前趋比较，若逆序，则fail为TRUE,则bt不是二叉排序树。voidbisorttree(bitreebt,keytypepre,bool&fail){//fail初值为FALSE，若非二叉序树，则fail值TRUEif(!fail){if(bt){bisosrttree(bt->lchild,pre,fail);//判断左子树if(bt->data_keydata_key;bisorttree(bt->rchild,pre,fail);//判断右子树}}}}//bisorttree说明：较为直观的方法，可套用中序遍历非递归算法。2.intsearch_bin(SeqTablest,keytypek,intlow,inthigh){if(lowa[i+1])      {a[i]<->a[i+1];        change=1;      }    high--;//修改上界    for(i=high;i>low;i--)//从下向上起泡      if(a[i]a[i-1];        change=1;      }    low++;//修改下界  }//while}//Bubble_Sort22.voidLinkList_Select_Sort(LinkList&L)//单链表上的简单选择排序算法{for(p=L;p->next->next;p=p->next)  { q=p->next;x=q->data;   for(r=q,s=q;r->next;r=r->next)//在q后面寻找元素值最小的结点     if(r->next->datanext->data;        s=r;    }    if(s!=q)//找到了值比q->data更小的最小结点s->next    {p->next=s->next;s->next=q;      t=q->next;q->next=p->next->next;      p->next->next=t;    }//交换q和s->next两个结点  }//for}//LinkList_Select_Sort'