数据结构练习题(DOC)

数据结构练习题习题1绪论1.1单项选择题1.数据结构是一门研究非数值计算的程序设计问题中,数据元素的①、数据信息在计算机中的②以及一组有关的运算等的课程。①A．操作对象Ｂ．计算方法Ｃ．逻辑结构Ｄ．数据映象②A．存储结构Ｂ．关系Ｃ．运算Ｄ．算法2.数据结构DS(DataStruct)能够被形式地定义为DS=〔D，R〕，其中D是①的有限会合，R是D上的②有限集合。①A．算法Ｂ．数据元素Ｃ．数据操作Ｄ．数据对象②A．操作Ｂ．映象Ｃ．存储Ｄ．关系3.在数据结构中，从逻辑上能够把数据结构分红。A．动向结构和静态结构Ｂ．紧凑结构和非紧凑结构Ｃ．线性结构和非线性结构Ｄ．内部结构和外部结构4.算法剖析的目的是①，算法剖析的两个主要方面是②。①A.找出数据结构的合理性B.研究算法中的输入和输出的关系C.剖析算法的效率以求改进D.剖析算法的易懂性和文档性②A.空间复杂性和时间复杂性B.正确性和简洁性C.可读性和文档性D.数据复杂性和程序复杂性5.计算机算法指的是①，它必具备输入、输出和②等五个特性。①A.计算方法B.排序方法C.解决问题的有限运算序列D.调动方法②A.可行性、可移植性和可扩大性B.可行性、确定性和有穷性C.确定性、有穷性和稳定性D.易读性、稳定性和平安性1.2填空题〔将正确的答案填在相应的空中〕1.数据逻辑结构包括、和三种种类，树形结构和图形结构合称为。2.在线性结构中，第一个结点前驱结点，其余每个结点有且只有个前驱结点；最后一个结点后续结点，其余每个结点有且只有个后续结点。3.在树形结构中，树根结点没有结点，其余每个结点有且只有个直接前驱结点，叶子结点没有结点，其余每个结点的直接后续结点能够。4.在图形结构中，每个结点的前驱结点数和后续结点数能够。5.线性结构中元素之间存在关系，树形结构中元素之间存在关系，图形结构中元素之间存在关系。6.算法的五个重要特性是____,____,____,____,____。7.剖析下面算法〔程序段〕，给出最大语句频度，该算法的时间复杂度是____。for(i=0;i<n;i++)for(j=0;j<n;j++)A[i][j]=0;8.剖析下面算法〔程序段〕，给出最大语句频度，该算法的时间复杂度是____。for(i=0;i<n;i++)for(j=0;j<i;j++)A[i][j]=0;9.剖析下面算法〔程序段〕，给出最大语句频度，该算法的时间复杂度是____。s=0;for(i=0;i<n;i++)for(j=0;j<n;j++)for(k=0;k<n;k++)s=s+B[i][j][k];sum=s;10.剖析下面算法〔程序段〕给出最大语句频度，该算法的时间复杂度是____。精选i=s=0;while(s<n){i++;s+=i;//s=s+i}11.剖析下面算法〔程序段〕给出最大语句频度，该算法的时间复杂度是____。i=1;while(i<=n)i=i*2;1.3算法设计题1.试写一算法,自傲到小依次输出次序读入的三个数X,Y和Z的值.试写一算法,求出n个数据中的最大值。写出最大语句频度，该算法的时间复杂度。习题答案1.11.C,A2.B,D3.C4.C,A5.C,B1.21.线性结构、树形结构、图形结构，非线性结构没有、1、没有、1前驱、1、后续、随意多个随意多个一对一、一对多、多对多有穷性、确定性、可行性、输入、输出最大语句频度：n2，时间复杂度：.O(n2)8.最大语句频度：n(n+1)/2，时间复杂度：.O(n2)9.最大语句频度：n3，时间复杂度：.O(n3)1110.最大语句频度：n2，时间复杂度：.O(n2)11.最大语句频度：logn，时间复杂度：.O(logn)22习题2线性表2.1单项选择题1.一个向量〔即一批地点连续的存储单元〕第一个元素的存储地点是100，每个元素的长度为2，那么第5个元素的地点是____。A.110B.108C.100D.1202.线性表的次序存储结构是一种___的存储结构，而链式存储结构是一种___的存储结构。A．随机存取B．索引存取C．次序存取D．散列存取3.线性表的逻辑次序与存储次序老是一致的，这种说法___。A.正确B.不正确4.线性表假定采用链式存储结构时，要求内存中可用存储单元的地点___。A.必须是连续的B.局部地点必须是连续的C.一定是不连续的D.连续或不连续都能够在以下的表达中，正确的选项是___。A.线性表的次序存储结构优于链表存储结构B.线性表的次序存储结构合用于频繁插入/删除数据元素的情况C.线性表的链表存储结构合用于频繁插入/删除数据元素的情况线性表的链表存储结构优于次序存储结构6.每种数据结构都具备三个根本运算：插入、删除和查找，这种说法___。A.正确B.不正确精选不带头结点的单链表head为空的判断条件是____。A.head==NULLB.head->next==NULLC.head->next==headD.head!=NULL带头结点的单链表head为空的判断条件是____。A.head==NULLB.head->next==NULLC.head->next==headD.head!=NULL非空的循环单链表head的尾结点〔由p所指向〕知足____。A.p->next==NULLB.p==NULLC.p->next==headD.p==head10.在双向循环链表的p所指结点之后插入s所指结点的操作是____。A.p->right=s;s->left=p;p->right->left=s;s->right=p->right;B.p->right=s;p->right->left=s;s->left=p;s->right=p->right;C.s->left=p;s->right=p->right;p->right=s;p->right->left=s;D.s->left=p;s->right=p->right;p->right->left=s;p->right=s;11.在一个单链表中，q所指结点是p所指结点的前驱结点，假定在q和p之间插入s结点，那么履行____。A.s->next=p->next;p->next=s;B.p->next=s->next;s->next=p;B.q->next=s;s->next=p;C.p->next=s;s->next=q;12.在一个单链表中，假定p所指结点不是最后结点，在p之后插入s所指结点，那么履行____。A.s->next=p;p->next=s;B.s->next=p->next;p->next=s;C.s->next=p->next;p=s;C.p->next=s;s->next=p;13.在一个单链表中，假定删除p所指结点的后续结点，那么履行____。A.p->next=p->next->next；B.p=p->next;p->next=p->next->next；C.p->next=p->next;D.p=p->next->next；14.从一个拥有n个结点的单链表中查找其值等于x结点时，在查找成功的情况下，需平均比较____个结点。A.nB.n/2C.(n-1)/2D.(n+1)/215.在一个拥有n个结点的有序单链表中插入一个新结点并仍旧有序的时间复杂度是____。A.O(1)B.O(n)C.O(n2)D.O(nlog2n)16.给定有n个元素的向量，成立一个有序单链表的时间复杂度是____。A.O(1)〕B.O(n)C.O(n2)D.O(n*log2n)2.2填空题〔将正确的答案填在相应的空中〕单链表能够做____的链接存储表示。2.在双链表中，每个结点有两个指针域，一个指向______，另一个指向_____。3.在一个单链表中p所指结点以前插入一个s(值为e)所指结点时，可履行如下操作：q=head;while(q->next!=p)q=q->next;s=newNode;s->data=e;q->next=;//填空s->next=;//填空在一个单链表中删除p所指结点的后继结点时，应履行以下操作：q=p->next;p->next=____;//填空delete;//填空5.在一个单链表中p所指结点之后插入一个s所指结点时，应履行s->next=____和p->next=____的操作。6.关于一个拥有n个结点的单链表，在p所指结点后插入一个新结点的时间复杂度是____；在给定值为x的结点后插入一个新结点的时间复杂度是____。2.3算法设计题:1.设次序表va中的数据元数递增有序。试写一算法，将x插入到次序表的适合地点上，以保持该表的有序性。StatusInsert_SqList(SqList&va,intx){if(va.length+1>maxsize)returnERROR;va.length++;for(i=va.length-1;va.elem[i]>x&&i>=0;i--)精选va.elem[i+1]=va.elem[i];va.elem[i+1]=x;returnOK;}2.试写一算法，实现次序表的就地逆置，即利用原表的存储空间将线性表〔a1,a2,.nn,an-1,.,1)。a〕逆置为(aavoidreverse(inta[],intsize){inti,j,tmp;for(i=0,j=size-1;i<j;i++,j--){tmp=a[i];a[i]=a[j];a[j]=tmp;}}3.线性表中的元素以值递增有序排列，并以单链表作存储结构。试写一算法，删除表中所有大于x且小于y的元素〔假定表中存在这样的元素〕同时释放被删除结点空间。voiddel(LinkListL,elemtypea,elemtypeb){p=L;q=p->next;while(q!=L&&q->data<a){p=q;q=q->next;}while(q!=L&&q->data<b){r=q;q=q->next;free(r);}if(p!=q)p->next=q;}试写一算法，实现单链表的就地逆置(要求在原链表上进行)。voidconverse(NODEPTRL){NODEPTRp,q;p=L->next;q=p->next;L->next=NULL;while(p)/*关于目前结点p，用头插法将结点p插入到头结点之后*/{p->next=L->next;L->next=p;p=q;q=q->next;}}精选习题答案2.11.B2.A,C3.B4.D5.C6.A7.A8.B9.C10.D11.B12.B13.A14.D15.B16.C2.21.线性结表2.前驱结点、后继结点3.s,p4.q->next,q5.p->next,s6.O(1),O(n)习题3栈和行列3.1单项选择题一个栈的入栈序列a，b，c，d，e，那么栈的不可能的输出序列是____。A.edcbaB.decbaC.dceabD.abcde假定一个栈的入栈序列是1，2，3，，n，其输出序列为p1，p2，p3，，pn，假定p1=n，那么pi为____。A.iB.n=iC.n-i+1D.不确定栈结构往常采用的两种存储结构是____。次序存储结构和链式存储结构散列方式和索引方式链表存储结构和数组线性存储结构和非线性存储结构判断一个次序栈ST〔最多元素为m0〕为空的条件是____。A.top!=0B.top==0C.top!=m0D.top==m0-1判断一个次序栈ST〔最多元素为m0〕为栈满的条件是____。A.top！=0B.top==0C.top！=m0D.top==m0-1栈的特点是____，行列的特点是____。A.先进先出B.先进后出7.向一个栈顶指针为HS的链栈中插入一个s所指结点时，那么履行____。(不带空的头结点)HS—＞next=s;s—＞next=HS—＞next;HS—＞next=s;s—＞next=HS;HS=s;D.s—＞next=HS;HS=HS—＞next;8.从一个栈顶指针为HS的链栈中删除一个结点时，用x保留被删结点的值，那么履行____。(不带空的头结点)A.x=HS;HS=HS—＞next;B.x=HS—＞data;C.HS=HS—＞next;x=HS—＞data;D.x=HS—＞data;HS=HS—＞next;9.一个行列的数据入列序列是1，2，3，4，那么行列的出队时输出序列是____。A.4，3，2，1B.1，2，3，4C.1，4，3，2D.3，2，4，1判断一个循环行列QU〔最多元素为m0〕为空的条件是____。A.rear-front==m0B.rear-front-1==m0C.front==rearD.front==rear+111.判断一个循环行列QU〔最多元素为m0,m0==Maxsize-1〕为满行列的条件是____。A.((rear-front)+Maxsize)%Maxsize==m0B.rear-front-1==m0C.front==rearD.front==rear+112.循环行列用数组A[0，m-1]寄存其元素值，其头尾指针分别是front和rear，那么目前行列中的元素个数是____。(rear-front+m)%mrear-front+1C.rear-front-1rear-front栈和行列的共同点是____。A.都是先进后出B.都是先进先出C.只允许在端点处插入和删除元素D.没有共同点精选3.2填空题〔将正确的答案填在相应的空中〕向量、栈和行列都是____结构，能够在向量的____地点插入和删除元素；关于栈只能在____插入和删除元素；关于行列只能在____插入元素和____删除元素。2.向一个长度为n的向量的第i个元素〔1≤i≤n+1〕以前插入一个元素时，需向后移动____个元素。3.向一个长度为n的向量中删除第i个元素〔1≤i≤n〕时，需向前移动____个元素。4.在拥有n个单元的循环行列中，队满时共有____个元素。习题答案3.11.C2.C3.A4.B5.D6.BA7.C8.B9.C10.C11.A12.A13.C3.21.线性、任何、栈顶、队尾、队首2.n-i+13.n-i4.n-1习题6树和二叉树6.1单项选择题1.由于二叉树中每个结点的度最大为2，所以二叉树是一种特殊的树，这种说法____。A.正确B.错误2.假定在一棵二叉树中，双分支结点数为15，单分支结点数为30个，那么叶子结点数为个。A．15B．16C．17D．473.按照二叉树的定义，拥有3个结点的不同形状的二叉树有____种。A.3B.4C.5D.64.按照二叉树的定义，拥有3个不同数据结点的不同的二叉树有____种。A.5B.6C.30D.32深度为5的二叉树至多有____个结点。A.16B.32C.31D.106.设高度为h的二叉树上只有度为0和度为2的结点，那么此类二叉树中所包含的结点数起码为____。A.2hB.2h-1C.2h+1D.h+1对一个满二叉树，m个树叶，n个结点，深度为h，那么____。A.n=h+mB.h+m=2nC.m=h-1D.n=2h-18.任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对序次____。A.不发生改变B.发生改变C.不能确定D.以上都不对9.如果某二叉树的前根序次遍历结果为stuwv，中序遍历为uwtvs，那么该二叉树的后序为____。A.uwvtsB.vwutsC.wuvtsD.wutsv10.二叉树的前序遍历序列中，随意一个结点均处在其儿女结点的前面，这种说法____。A.正确B.错误11.某二叉树的前序遍历结点接见次序是abdgcefh，中序遍历的结点接见次序是dgbaechf，那么后来序遍历的结点接见次序是____。A.bdgcefhaB.gdbecfhaC.bdgaechfD.gdbehfca12.在一非空二叉树的中序遍历序列中，根结点的右边____。A.只有右子树上的所有结点B.只有右子树上的局部结点C.只有左子树上的局部结点D.只有左子树上的所有结点13.如图6.1所示二叉树的中序遍历序列是____。A.abcdgefB.dfebagcC.dbaefcgD.defbagcaabcbdgcdeef图6.1ghf14.一棵二叉树如图6.2所示，其中序遍历的序列为____。A.图6.2abdgcefhB.dgbaechfaD.C.gdbehfcaabcdefgh精选15．设a,b为一棵二叉树上的两个结点，在中序遍历时，a在b前的条件是。A．a在b的右方B．a在b的左方C．a是b的祖先D．a是b的后代某二叉树的后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是____。A.acbedB.decabC.deabcD.cedba17.实现随意二叉树的后序遍历的非递归算法而不使用栈结构，最正确方案是二叉树采用____存储结构。A.二叉链表B.广义表存储结构C.三叉链表D.次序存储结构如图6.3所示的4棵二叉树，____不是完全二叉树。(A)(B)(C)(D)图6.3在线索化二叉树中，t所指结点没有左子树的充要条件是____。A.t—＞left=NULLB.t—＞ltag=1C.t—＞ltag=1且t—＞left=NULLD.以上都不对21.二叉树按某种次序线索化后，任一结点均有指向其前驱和后续的线索，这种说法____。A.正确B.错误22.二叉树为二叉排序树的充分必要条件是其任一结点的值均大于其左孩子的值、小于其右孩子的值。这种说法____。A.正确B.错误拥有五层结点的二叉平衡树起码有____个结点。A.10B.12C.15D.17树的根本遍历策略可分为先根遍历和后根遍历；二叉树的根本遍历策略可分为先序遍历、中序遍历和后序遍历。这里，我们把由树转变获得的二叉树叫做这棵数对应的二叉树。结论____是正确的。树的先根遍历序列与其对应的二叉树的先序遍历序列相同树的后根遍历序列与其对应的二叉树的后序遍历序列相同树的先根遍历序列与其对应的二叉树的中序遍历序列相同D.以上都不对树最适合用来表示____。A.有序数据元素B.无序数据元素C.元素之间拥有分支层次关系的数据D.元素之间无联系的数据6.2填空题〔将正确的答案填在相应的空中〕有一棵树如图6.5所示，回复下面的问题：⑴这棵树的根结点是____；⑵这棵树的叶子结点是____；⑶结点k3的度是____；⑷这棵树的度是____；⑸这棵树的深度是____；⑹结点k3的儿女是____；⑺结点k3的父结点是__

k1k2k3k4k5k6图6.5一棵树k7指出树和二叉树的三个主要差别____、____、____。__；3.从观点上讲，树与二叉树是两种不同的数据结构，将树转变为二叉树的基本目的是____。4.一棵二叉树的结点数据采用次序存储结构，存储于数组t中，如图6.6所示，那么该二叉树的链接表示形式为____。5.深度为k的完全二叉树起码有____个结点。至多有____个结点，假定按自上而下，从左到右序次给结点编号〔从1开123456789101112131415161718192021eafdgcj精选lhb图6.6一棵二叉树的次序存储数组t始〕，那么编号最小的叶子结点的编号是____。6.在一棵二叉树中，度为零的结点的个数为n0，度为2的结点的个数为n2，那么有n0=____。7.一棵二叉树的第i〔i≥1〕层最多有____个结点；一棵有n〔n>0〕个结点的满二叉树共有____个叶子和____个非终端结点。结点最少的树为____，结点最少的二叉树为____。现有按中序遍历二叉树的结果为abc，问有____种不同形态的二叉树能够获得这一遍历结果，这些二叉树分别是____。由如图6.7所示的二叉树，回复以下问题：⑴其中序遍历序列为____；a⑵其前序遍历序列为____；⑶后来序遍历序列为____；bcdefh6.3简答题i1.根据二叉树的定义，拥有三个结点的二叉树有5种不同的形态，请将它们分别画出。图6.7一棵二叉树2.假定一棵二叉树的先序序列为EBADCFHGIKJ和中序序列为ABCDEFGHIJK。请画出该树。3.由如图6.7所示的二叉树，回复以下问题：a〔1〕画出该二叉树的中序线索二叉树；〔2〕画出该二叉树的后序线索二叉树；〔3〕画出该二叉树对应的森林。bcd4.一棵树如图6.8所示，转变为一棵二叉树，表示为____。efg图6.8一棵树5.以数据集{4，5，6，7，10，12，18}为结点权值，画出结构Huffman树的每一步图示，计算其带权路径长度为。一棵含有N个结点的k叉树,可能抵达的最大深度和最小深度各为多少?7.证明:一棵满k叉树上的叶子结点数n0和非叶子结点数n1之间知足以下关系

:n

0=(k-1)n

1+16.4算法设计题编写按层次次序〔同一层自左至右〕遍历二叉树的算法。．试编写算法，对一棵二叉树,统计叶子的个数。．试编写算法，对一棵二叉树根结点不变，将左、右子树进行互换，树中每个结点的左、右子树进行互换。7.假定用于通讯的电文仅有八个字母(a,b,c,d,e,f,g,h)组成，字母在电文中出现的频次分别为0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10。试为这八个字母设计哈夫曼编码。使用0-7的二进制表示形式是另一种编码方案。关于上述实例，比较两种方案的优缺点。8.试编写算法，对一棵以孩子-兄弟链表表示的树统计叶子的个数。假定一棵二叉树的先序序列为EBADCFHGIKJ和中序序列为ABCDEFGHIJK。请画出该树。习题答案6.11.B2.B3.C4.C5.C6.A7.D8.A9.C10.A11.D2.A13.B14.B15.B16.D17.C18.C19.B20.B21.B22.B23.B24.A25.C6.21.⑴k1⑵k2,k5,k7,k4⑶2⑷3⑸4⑹k5,k6⑺k12.树的结点个数起码为1(不同教材规定不同)，而二e叉树的结点个数能够为0；树中结点的最大度数没有限制，而二叉树结点的最大度数为2；树的结点无左、右之分，而二叉树的结点有左、右af之分；3.树可采用孩子-兄弟链表〔二叉链表〕做存储结构，目的并利用二叉树的已有算法解决树的有关问题。dg4.如图6.9所示cjlh精选b图6.95.2k-1、2k-1、2k-2+16.n2+17.2i-12[logn+1]-12[logn+1]–122只有一个结点的树；空的二叉树5；如图6.10所示ccaabbabcacabcb图6.10树形5种10.dgbaechif、abdgcefhi、gdbeihfca、6.31.5种,图6.112.二叉树如图6.12所示。图6.11树形5种EBFADH3.中序线索二叉树如图6.13〔左〕所示；后序CG线索二叉树如图6.13〔右〕所示；该二叉树变换后的的森林如图6.14所示。IaaKbcbcacJfNULL图6.12defdefbehi4.图6.8的树转变为一棵二叉树如下，图d：j6.15ajhjhNULLii

图6.14b对应的森林图8.18中序和后序线索树图6.13

cedig图6.15一棵树的孩子兄弟表5.画出结构Huffman树如图6.16所示，计算其带权路径长度为。6.一棵含有N个结点的k叉树,可能抵达的最大深度h=N-k+1，最小深度各为:logkN+1。623725191813121096745精选图6.16Huffman树习题7图7.1单项选择题1．在一个图中，所有极点的度数之和等于所有边数的____倍。A.1/2B.1C.2D.42．任何一个无向连通图的最小生成树。A.只有一棵B.有一棵或多棵C.一定有多棵D.可能不存在3．在一个有向图中，所有极点的入度之和等于所有极点的出度之和的____倍。A.1/2B.1C.2D.44．一个有n个极点的无向图最多有____条边。A.nB.n(n-1)C.n(n-1)/2D.2n5．拥有4个极点的无向完全图有____条边。A.6B.12C.16D.206．拥有6个极点的无向图起码应有____条边才能保证是一个连通图。A.5B.6C.7D.87．在一个拥有n个极点的无向图中，要连通全部极点起码需要____条边。A.nB.n+1C.n-1D.n/28．关于一个拥有n个极点的无向图，假定采用毗邻矩阵表示，那么该矩阵的大小是____。A.nB.(n-1)2C.n-1D.n29．关于一个拥有n个极点和e条边的无向图，假定采用毗邻表表示，那么表头向量的大小为_①___；所有毗邻表中的接点总数是_②___。①A.nB.n+1C.n-1D.n+e②A.e/2B.eC.2eD.n+e10．一个图如图7.1所示，假定从极点a出发按深度搜寻法进行遍历，那么可能获得的一种极点序列为__①__；按宽度搜寻法进行遍历，那么可能获得的一种极点序列为__②__。①A.a,b,e,c,d,fB.e,c,f,e,b,dC.a,e,b,c,f,dD.a,e,d,f,c,b②A.a,b,c,e,d,fB.a,b,c,e,f,dC.a,e,b,c,f,dD.a,c,f,d,e,babecf图7.1一个无向图11．一有向图的毗邻表存储结构如图7.2所示。132^^345^精选^524^图7.2一个有向图的毗邻表存储结构⑴根据有向图的深度优先遍历算法，从极点v1出发，所获得的极点序列是____。A.v1,v2,v3,v5,v4B.v1,v2,v3,v4,v5C.v1,v3,v4,v5,v2D.v1,v4,v3,v5,v2⑵根据有向图的宽度优先遍历算法，从极点v1出发，所获得的极点序列是____。A.v1,v2,v3,v4,v5B.v1,v3,v2,v4,v5C.v1,v2,v3,v5,v4D.v1,v4,v3,v5,v212．采用毗邻表存储的图的深度优先遍历算法近似于二叉树的____。A.先序遍历B.中序遍历C.后序遍历D.按层遍历13．采用毗邻表存储的图的宽度优先遍历算法近似于二叉树的____。A.先序遍历B.中序遍历C.后序遍历D.按层遍历14．判断一个有向图是否存在回路除了能够利用拓扑排序方法外，还能够利用____。A.求重点路径的方法B.求最短路径的Dijkstra方法C.宽度优先遍历算法D.深度优先遍历算法15．重点路径是事件结点网络中。A.从源点到汇点的最长路径B.从源点到汇点的最短路径C.最长的回路D.最短的回路16．下面不正确的说法是。1〕在AOE网中，减小一个重点活动上的权值后，整个工期也就相应减小；2〕AOE网工程工期为重点活动上的权之和；3〕在重点路径上的活动都是重点活动，而重点活动也必在重点路径上。A.〔1〕B.〔2〕C.〔3〕D.〔1〕、〔2〕17．用DFS遍历一个无环有向图，并在DFS算法退栈返回时打印出相应的极点，那么输出的极点序列是。A.逆拓朴有序的B.拓朴有序的C.无序的18．在图7.3所示的拓朴排列的结果序列为。A.125634B.516234C.123456D.52163419．一个有图7.3有向图。n个极点的无向连通图，它所包含的连通分量个数为A.0B.1C.nD.n+120．关于一个有向图，假定一个极点的入度为k1,、出度为k2，那么对应毗邻表中该极点单链表中的结点数为。A.k1B.k2C.k1-k2D.k1+k221．关于一个有向图，假定一个极点的入度为k1,、出度为k2，那么对应逆毗邻表中该极点单链表中的结点数为。A.k1B.k2C.k1-k2D.k1+k27.2填空题〔将正确的答案填在相应饿空中〕1．n个极点的连通图起码____条边。2．在无权图G的毗邻矩阵A中，假定(vi,vj)或＜vi,vj＞属于图G的边会合，那么对应元素A[i][j]等于____，否那么等于____。3．在无向图G的毗邻矩阵A中，假定A[i][j]等于1，那么A[j][i]等于____。4．图G的毗邻表如图7.4所示，其从极点v1出发的深度有限搜寻序列为____，其从极点v1出发的宽度优先搜寻序列为____。v1v2v5v4v2v3v5v3v6精选v4^v5v4v6v3图7.4图G的毗邻表5．一个有向图的毗邻矩阵表示，计算第i个结点的入度的方法是____。6．一个图的毗邻矩阵表示，删除所有从第i个结点出发的边的方法是____。7．如果含n个极点的图形成一个环，那么它有棵生成树。8．一个非连通无向图，共有28条边，那么该图起码有个极点。9．遍历图的过程实质上是。BFS遍历图的时间复杂度为，DFS遍历图的时间复杂度为，两者不同之处在于，反应在数据结构上的差别是。10．一个图的表示法是唯一的，而表示法是不唯一的。11．有向图中的结点前驱后继关系的特点是。12．假定无向图G的极点度数最小值大于等于时，G起码有一条回路。13．根据图的存储结构进行某种序次的遍历，获得的极点序列是的。7.3综合题1．如图7.5所示的有向图，请给出该图的:〔1〕每个极点的入/出度；152〕毗邻距阵；3〕毗邻表；〔4〕逆毗邻表；6〔5〕强连通分量。243图7。5一个有向图2．请用克鲁斯卡尔和普里姆两种算法分别为图7.6、图7.7结构最小生成树：〔1〕a161115b15c15d13161412e21f图7.6〔2〕12161361524167522091012543图7.7精选3．试列出图7.8中全部的拓扑排序序列。123456图7.84．请用图示说明图7.9从极点a到其余各极点之间的最短路径。b5d36a232f35ce7.95．AOE网有9个结点：V1，V2，V3，V4，V5，V6，V7，V8，V9，其毗邻矩阵如下：请画出该AOE图。计算达成整个方案需要的时间。求出该AOE网的重点路径。∝645∝∝∝∝∝∝∝∝∝1∝∝∝∝∝∝∝∝1∝∝∝∝∝∝∝∝∝2∝∝∝∝∝∝∝∝∝97∝∝∝∝∝∝∝∝4∝∝∝∝∝∝∝∝∝2∝∝∝∝∝∝∝∝4∝∝∝∝∝∝∝∝∝习题答案7.11.C2.B3.B4.C5.A6.A7.C8.D9.AC10.DB11.CB12.A13.D14.D15.A16.A17.A18.B19.B20.B21.A7.21.n-12.1;03.14.v1,v2,v3,v6,v5,v4；v1,v2,v5,v4,v3,v6求矩阵第i列非零元素之和将矩阵第i行全部置为零7.n8.9对每个极点查找其毗邻点的过程；O〔e〕〔e为图中的边数〕；O〔e〕；遍历图的次序不同；DFS采用栈存储接见过的结点，BFS采用行列存储接见过的结点。10．毗邻矩阵毗邻表精选11．一个结点可能有假定干个前驱，也可能有假定干个后继12．213．唯一7.31.156242.3(1)．a11b15cd131412ef〔2〕11263．615236445721526349101562345456123435162345126345123644．W=6W=5bd3a23f3W=9ce4W=3W=75．(1)该AOE图为：21597267114349854264达成整个方案需要18天。重点路径为：〔V1，V2，V5，V7，V9〕和〔V1，V2，V5，V8，V9，〕精选习题8查找8.1单项选择题次序查找法适合于存储结构为____的线性表。A.散列存储B.次序存储或链接存储C.压缩存储D.索引存储对线性表进行二分查找时，要求线性表必须____。A.以次序方式存储B.以链接方式存储以次序方式存储，且结点按重点字有序排序以链接方式存储，且结点按重点字有序排序3.采用次序查找方法查找长度为n的线性表时，每个元素的平均查找长度为____.A.nB.n/2C.(n+1)/2D.(n-1)/24.采用二分查找方法查找长度为n的线性表时，每个元素的平均查找长度为____。A．O〔n2〕B.O(nlog2n)C.O(n)D.O(log2n)二分查找和二叉排序树的时间性能____。A.相同B.不相同6.有一个有序表为{1，3，9，12，32，41，45，62，75，77，82，95，100}，当二分查找值82为的结点时，____次比较后查找成功。A.1B.2C.4D.8设哈希表长m=14，哈希函数H(key)=key%11。表中已有4个结点：addr(15)=4;addr(38)=5;addr(61)=6;addr(84)=7如用二次探测再散列办理矛盾，重点字为49的结点的地点是____。A.8B.3C.5D.9有一个长度为12的有序表，按二分查找法对该表进行查找，在表内各元素等概率情况下查找成功所需的平均比较次数为____。A.35/12B.37/12C.39/12D.43/129．关于静态表的次序查找法，假定在表头设置岗哨，那么正确的查找方式为。A.从第0个元素往后查找该数据元素B.从第1个元素往后查找该数据元素C.从第n个元素往开始前查找该数据元素与查找次序无关10．解决散列法中出现的矛盾问题常采用的方法是。数字剖析法、除余法、平方取中法数字剖析法、除余法、线性探测法数字剖析法、线性探测法、多重散列法线性探测法、多重散列法、链地点法11．采用线性探测法解决矛盾问题，所产生的一系列后继散列地点。必须大于等于原散列地点必须小于等于原散列地点能够大于或小于但不能等于原散列地点地点大小没有详细限制12．关于查找表的查找过程中，假定被查找的数据元素不存在，那么把该数据元素插入到会合中。这种方式主要适合于。A.静态查找表B.动向查找表C.静态查找表与动向查找表D两种表都不适合13.散列表的平均查找长度。与办理矛盾方法有关而与表的长度无关与办理矛盾方法无关而与表的长度有关与办理矛盾方法有关而与表的长度有关与办理矛盾方法无关而与表的长度无关8.2填空题〔将正确的答案填在相应的空中〕次序查找法的平均查找长度为____；折半查找法的平均查找长度为____；哈希表查找法采用链接法办理矛盾时的平均查找长度为____。2.在各样查找方法中，平均查找长度与结点个数n无关的查找方法是____。精选折半查找的存储结构仅限于____，且是____。4.假定在有序线性表A[1..20]上进行折半查找，那么比较一次查找成功的结点数为____，那么比较二次查找成功的结点数为____，那么比较三次查找成功的结点数为____，那么比较四次查找成功的结点数为____，那么比较五次查找成功的结点数为____，平均查找长度为____。5.关于长度为n的线性表，假定进行次序查找，那么时间复杂度为____；假定采用折半法查找，那么时间复杂度为____；6．有序表为〔12，18，24，35，47，50，62，83，90，115，134〕，当用折半查找90时，需进行次查找可确定成功；查找47时，需进行次查找成功；查找100时，需进行次查找才能确定不可功。7．二叉排序树的查找长度不单与有关，也与二叉排序树的有关。8．一个无序序列能够经过结构一棵树而变成一个有序树，结构树的过程即为对无序序列进行排序的过程。9．平衡二叉排序树上任一结点的平衡因子只可能是、或。10．法结构的哈希函数肯定不会发生矛盾。11．在散列函数H(key)=key%p中，p应取____。12．在散列存储中，装填因子的值越大，那么____；的值越小，那么____。8.3综合练习题:画出对长度为10的有序表进行折半查找的判断树，并求其等概率时查找成功的平均查找长度。4.选用哈稀函数H〔k〕=〔3k〕MOD11。用开放定址法办理矛盾，di=i〔〔7k〕MOD10+1〕〔I=1，2，3，〕.试在0-10的散列地点空间中对重点字序列〔22,41,53,46,30,13,01,67〕造哈希表，并求等概率情况下查找成功时的平均查找长度。一组重点字{49，38，65，97，76，13，27，44，82，35，50}，画出由今生成的二叉排序树，注意边插入边平衡。习题答案8.11．B2．C3．C4．D5．B6．C7．D8．B9．C10．D11．C12．B13．C8.21.〔n+1〕/2、((n+1)*log2(n+1))/n-1、1+〔为装填因子〕哈希表查找法次序存储结构、有序的1、2、4、8、5、3．7〔依题意，结构一棵有序二叉树，共12个结点，第一层1个结点，第二层2个结点，第三层4个结点，第四层5个结点，那么：ASL=〔1*1+2*2+3*4+4*5〕/12=37/12〕5.O〔n〕、O(log2n)6．2、4、3．结点个数n、生成过程．二叉排序树．0、1、-1．直接定址11．素数12．存取元素时发生矛盾的可能性就越大、存取元素时发生矛盾的可能性就越小习题9排序9.1单项选择题1.在所有排序方法中，重点字比较的次数与记录的初始排列序次无关的是____。A.希尔排序B.起泡排序C.插入排序D.选择排序2.设有1000个无序的元素，希望用最快的速度精选出其中前10个最大的元素，最好采用____排序法。A.起泡排序B.迅速排序C.堆排序D.基数排序3.在待排序的元素序列根本有序的前提下，效率最高的排序方法是____。A.插入排序B.选择排序C.迅速排序D.合并排序一组记录的排序码为〔46，79，56，38，40，84〕，那么利用堆排序的方法成立的初始堆为____。A.79，46，56，38，40，80B.38，46,56，79，40，84，C.84，79，56，46，40，38D.84，56，79，40，46，38一组记录的重点码为〔46，79，56，38，40，84〕，那么利用迅速排序的方法，以第一个记录为基准获得的一次区分结果为____。A.38，40，46，56，79，84B.40，38，46，79，56，84C.40，38，46，56，79，84D.40，38，46，84，56，79精选一组记录的排序码为〔25，48，16，35，79，82，23，40，36，72〕，其中含有5个长度为2的有序表，按合并排序的方法对该序列进行一趟合并后的结果为____。16，25，35，48，23，40，79，82，36，7216，25，35，48，7