2014考研計(jì)算機(jī)數(shù)據(jù)結(jié)構(gòu)沖刺課程講義

[[題1]以下算法的時(shí)間復(fù)雜度是（）voidfn){inti,j,fori=1i<nfor(intj=n;j>=i+1;j--)x++；} B. C.O(nlog2n)D.分析：基本運(yùn)算是語句x++，設(shè)其執(zhí)行時(shí)間為Tn解答：D==n(n-1)/2=[[題2]以下算法的時(shí)間復(fù)雜度是（）voidfn){inti=0;}A. B. C.O(nlog2n)D.)分析：基本運(yùn)算是語句i++，設(shè)其執(zhí)行時(shí)間為則有T(n)×T(n)×T(n)即解答：D=)[[題3]以下算法的時(shí)間復(fù)雜度是（）voidf(intwhile(d>0){if(d%2==1) =*f=f*f;d=d/2;}} B. C. D.則有d=n/2T(n>0≥1，2T(n)≤n1、線2、線性表有順序和鏈?zhǔn)絻?結(jié)構(gòu)（1），插入操作平均移動(dòng)n/2個(gè)結(jié)點(diǎn)，刪除操作平均移動(dòng) #defineLISTSIZEtypedef ElemType//#defineLIST_INIT_SIZE#defineLISTINCREMENTtypedefstruct{ElemType*elem;////}（（2）間 typedefstruct data;//數(shù)據(jù)域structLNode*next;//指針域} [[題1]設(shè)線性表有n個(gè)元素，以下操作中，（）在順序表上D．輸出與給定值x相等的元 性表中的序[[題2]采用順結(jié)構(gòu)的線性表的插入算法中，當(dāng)n已滿時(shí)，可申請(qǐng)?jiān)僭黾臃峙鋗個(gè)空間。若申請(qǐng)失敗，則明系統(tǒng)沒有（）可分配的 A．m個(gè)B．m個(gè)連續(xù)的 分析：此題主要考查線性表的順序結(jié)構(gòu)的特點(diǎn)。線性表的順序是指在內(nèi)存中用地址連續(xù)的一塊空間解答移動(dòng)上，在第ixai到an都要向后面的元素ai+1～an都要向上移動(dòng)一個(gè)位置，共移動(dòng)了n-i個(gè)元素。時(shí)間復(fù)雜度為Ｏ(n)。 ；分析：此題主要考查線性表的順序結(jié)構(gòu)（這里為數(shù)組）的應(yīng)用。算法的基。這樣，可使算法的時(shí)間復(fù)雜度為O(n)voidvoidAdjust（int{inti=1,j=n,temp;while(A[i]%2!=0)i++;∥A[i]為奇數(shù)時(shí)，i增1while(A[j]%2==0)j++;∥A[j]為偶數(shù)時(shí)，j減1if(i<j){temp=A[i];A[i]=A[j];A[j]=temp;}∥A[i]為偶數(shù)、A[j]為奇數(shù)時(shí)，交}}該算法的時(shí)間復(fù)雜度為O(n)；算法的空間復(fù)雜度為O(1)1、建立單鏈表（1）頭插法2、鏈表中查找第i3法5點(diǎn)不是新結(jié)點(diǎn)而是利用原表結(jié)點(diǎn)，因此這類算法中建立鏈表的法 結(jié)點(diǎn)的單鏈voidCrea n){LNode*s;inti; s->next=L- L-}}voidCrea istR(LinkList&L,ElemTypea[],intn){LNode*s，*r;inti;));r=L；∥rfor(i=0;i<n;i++) ∥將s插入到rr=s;r->next=NULL;∥終端結(jié)點(diǎn)next域置為}題1in。分析：此題主要考查線性表的鏈?zhǔn)浇Y(jié)構(gòu)的應(yīng)用，此題空鏈表，然后將待排序鏈表的結(jié)點(diǎn)依次插入這個(gè)空鏈表的有序鏈表。voidvoidInsertsort（LinkList{LNodep=L->next;L->next=NULL;//空鏈表，將原鏈表結(jié)點(diǎn)逐個(gè)插入到有序表中 r=L;q=L-while(q!=NULL&&q->data<=p-}}題2在一個(gè)單鏈表中的ps執(zhí)行如下操作（填空）：s->next=① t=p-p->data=② s->data= 分析：采用的方法是在ps將p所指結(jié)點(diǎn)和s解答：①p->next②s- voidvoidIntersection(LinkListha,LinkListhb,LinkList∥將ha和hb中共同的元 到單鏈表hcLNodeInsertsort(ha∥參考題1將ha指向的單鏈表由小到大排序Insertsort(hb∥參考題1將hb指向的單鏈表由小到大排序hc=(LinkList)malloc(sizeof(LNode));∥申請(qǐng)頭結(jié)點(diǎn)hc-whliewhlie(pa&& pa=pa- pb=pb->nxtelse{∥pa和pb)); }}[[題1]在一個(gè)雙向鏈表中，在*p結(jié)點(diǎn)之后插入結(jié)點(diǎn)*q的操作是（）q- p- p->next->prior=q;q->next=p-q->next=p->next;p->next->prior=q;p->next=q;q-p->next=q;q->prior=p;q->next=p->next;p->next-p->next->prior=q;q->next=p->next;q->prior=p;p-1、棧是運(yùn)算受限（限制在表的一端進(jìn)行插入和）的線性表，允許插入、刪除的這一端稱為棧頂，操作序列——“進(jìn)棧、出棧、進(jìn)棧、出棧……”——可以使數(shù)據(jù)通過棧后仍然保持次序不變。，對(duì)于順序結(jié)構(gòu)的棧還需注意（1）進(jìn)題1]設(shè)n個(gè)元素進(jìn)棧序列是p1，p2，p3，…，pn，其輸出序列是,3，…，n，若p=1，則i（1≤n1）的值是。A.n- B.n- D.有多種p=1進(jìn)棧序列是p1，p2，3，…，1，由輸出序列可知，1，p2，p3，…，pn進(jìn)棧，然后依次出棧，即pn-題2設(shè)np1p2p3…，pn序列是123，…，np=1p11≤≤n1）的值是（）。A.可能是 B.一定是 C.不可能是 D.不可能是分析：當(dāng)p3=1時(shí)，進(jìn)棧序列是p1，p2，p3，…，pn，由輸出序列可知，p1，p2，p3都進(jìn)棧，出棧p3，此后緊跟著出棧的一個(gè)元素是2，而p1不可能緊跟著p3出棧，因?yàn)闂Ｖ星懊嬗衟2，因此p1不可能是2。解答：C使隊(duì)列的向量空間得到充分的利用。判斷循環(huán)隊(duì)列的“空”和[[題1]若用一個(gè)大小為6的數(shù)組來實(shí)現(xiàn)循環(huán)隊(duì)列，且當(dāng)前rear加入兩個(gè)元素后，rear和front的值分別為（）。A．1和 B.2和 C.4和 D.5和分析：ar值為0，進(jìn)隊(duì)兩個(gè)元素后，er循環(huán)遞增2，則ear值為2；ot值為3，出隊(duì)一個(gè)元素后，ont循環(huán)遞增1，則on值為4。解答：B1LOC(aij)=LOC(a00)+(i×n+j)×d ，每個(gè)數(shù)組元素占據(jù)d個(gè)地址單元,LOC(aij)=LOC(a00)+(j×n+i22、特殊矩陣（假設(shè)以行序?yàn)橹餍颍?）對(duì)稱矩陣：將對(duì)稱矩陣A壓 到SA[n(n+1)/2]，j的下標(biāo)、與在Akk下：當(dāng)0≤，≤n10k＜n+1時(shí)，（上）三角中的元后，接著對(duì)角線上（下）方的A壓縮到SA[n(n+1)/2+1]中，aij的下標(biāo)i、j與在SA[k]中（（3）對(duì)角矩陣：一個(gè)有m（1≤m＜n）條非0元素的n階對(duì)角陣，在這種矩陣中，所有的非0中心的帶狀區(qū)域中，其非0u將對(duì)角矩陣A壓到一維數(shù)組SA[0..u-1]中，aij的下標(biāo)i、與在SA[k]中的對(duì)應(yīng)元素的下標(biāo)k的關(guān)系是當(dāng)0≤i，j≤n-1時(shí) [[題1]設(shè)矩陣A[1..n][1..n]下三角部分按行序存放在一維數(shù)組B[1..n(n-1)/2]置k的值為（）。—A.i(i-1)/2+j- B.i(i- C.i(i+1)/2+j- D.分析：對(duì)稱矩陣A的下標(biāo)從1開始，對(duì)于任一元素aij（由于，故它在下三角形中），其前有1行，第1行有1個(gè)元素，第2行有2個(gè)元素，…，第1行有1個(gè)元素，共計(jì)12個(gè)元素，在第行中，該元素前有1個(gè)元素，所以，元素j前共有i1)/2+1個(gè)元素，k=(1/2+1+1=1)/2+j。解答：B[[題2]設(shè)二維數(shù)組A[6][10]，每個(gè)數(shù)組元素占用4單元若按行優(yōu)先順序存放的數(shù)組元素a[3][5] 地址為，則a00 地址是（） LOC(aij)=LOC(a00)+(i×n+j)×d可知，LOC(a[3][5])=LOC(a[0][0])+(3×10+5)×4=1000，計(jì)算可解答：B九、樹、九、樹、二叉樹 結(jié)2。即使樹中結(jié)點(diǎn)只有一棵，也要區(qū)分它是左還是右。滿二叉樹：在一棵二叉樹中，如果所有分支結(jié)點(diǎn)都存在左和右，并且所33、二叉樹 結(jié)（1）順 結(jié)完全二叉樹和滿二叉樹采用順比較合適，樹中結(jié)的序號(hào)可以唯一地反映出結(jié)點(diǎn)之間的邏輯關(guān)系，這樣 下標(biāo)值確定結(jié)點(diǎn)在二叉樹中的位置，以及結(jié)點(diǎn)之間的系靈活、操作方便，對(duì)于一般情況的二叉樹，甚至比順序結(jié)構(gòu)還節(jié)省空間。因此，二叉鏈表是最常用的二叉樹方式。typedef emTypestructBiTNode*lchild;*rchild;//BiTree 解答：C[[題2]設(shè)二叉樹只有度為0和2的結(jié)點(diǎn)，其結(jié)點(diǎn)個(gè)數(shù)為15二叉樹的最大深度為 ）分析：對(duì)于結(jié)點(diǎn)的度只有0和2的二叉樹，為使其深度h除根結(jié)點(diǎn)層外，樹中其余層有兩個(gè)結(jié)點(diǎn)，即結(jié)點(diǎn)總數(shù)=2h-。由于結(jié)點(diǎn)個(gè)數(shù)為15，因此二叉樹的深度h為8解答：C性質(zhì)性質(zhì)4：具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度k。二二叉樹性質(zhì)的性質(zhì)2k1k1結(jié)點(diǎn)總數(shù)多1個(gè)。性質(zhì)3推廣：已知一棵度為m的樹中有0個(gè)葉子結(jié)點(diǎn)數(shù)，1個(gè)度為1的結(jié)點(diǎn)，N2個(gè)度為2的結(jié)點(diǎn)，，N個(gè)度為m的結(jié)點(diǎn)，則有：N=+2+Nm1N。性質(zhì)性質(zhì)4①有n>0個(gè)葉結(jié)點(diǎn)的完全二叉樹的高度(結(jié)點(diǎn)層次數(shù))當(dāng)n≠2k,即n不是2的 或者n=2k但是一棵滿二叉樹，其高度為。當(dāng)n=2k但是非滿二叉樹，其高度 ②有n個(gè)結(jié)點(diǎn)的完全k叉樹的高度為性質(zhì)性質(zhì)5k1①編號(hào)為p=1結(jié)點(diǎn)無父結(jié)點(diǎn)，否則為p結(jié)點(diǎn)的父結(jié)點(diǎn)是 （k≥2）；②編號(hào)為p的結(jié)點(diǎn)的第k1個(gè)孩子的編號(hào)為pk，所以，如果編號(hào)為p結(jié)點(diǎn)有孩子，則編號(hào)其第i個(gè)孩子的編號(hào)為p×kk-；③編號(hào)為p的結(jié)點(diǎn)有右兄弟的條件是(p-1)%k0時(shí)，其右兄弟性質(zhì)1：樹中的結(jié)點(diǎn)數(shù)等于所有結(jié)點(diǎn)的度數(shù)+1性質(zhì)2：度為m樹中第i層上至多有mi-1個(gè)結(jié)點(diǎn)（i≥1）性質(zhì)3：高度為h的度為m樹至多有(mh-1)/(m-1)個(gè)結(jié)點(diǎn)。性質(zhì)4：具有n個(gè)結(jié)點(diǎn)的度為m樹的最小高度為logm(n(m-。[[題1]若一棵二叉樹有126個(gè)結(jié)點(diǎn)，在第7層（根結(jié)點(diǎn)在第1層）至多有 D.不存在第7。題2]若一棵度為7的樹有8個(gè)度為1的結(jié)點(diǎn)，有7個(gè)度為2的結(jié)點(diǎn)，有6個(gè)度為3的結(jié)點(diǎn)，有5個(gè)度為4的結(jié)點(diǎn)，有4個(gè)度為5的結(jié)點(diǎn)，有3個(gè)度為6的結(jié)點(diǎn)，有2個(gè)度為7的點(diǎn)點(diǎn)，該樹一共有（）個(gè)葉結(jié)點(diǎn)。 分析：由二叉樹性質(zhì)3的推廣，度為7的樹應(yīng)該有＋3n445＋56＋67（1的結(jié)點(diǎn)的個(gè)數(shù)無關(guān)）。因此，如0n01＋7+2×+35+44+×3×278。（表示度為的結(jié)點(diǎn)解答：D十一、十一、二叉樹的遍歷及應(yīng)用1先序遍歷：遞歸算法、非遞歸中序遍歷：遞歸算法、非遞歸后序遍歷：遞歸算法、非遞歸層次遍2、遍歷二叉樹2、遍歷二叉樹制和左、右之間的交換，其思想是質(zhì)、結(jié)構(gòu)特點(diǎn)和遍歷算法的基礎(chǔ)上，可[[題1]任何一棵非空二叉樹中的葉子結(jié)點(diǎn)在先序遍歷、中序遍歷與后序遍歷中的相對(duì)位置（）。A．都會(huì)發(fā)生改 B．不會(huì)發(fā)生改變C．有可能會(huì)發(fā)生改 D．部分會(huì)發(fā)生改分析：無論是先序遍歷（DR）還是中序遍歷（DR），或是后序遍歷（D），對(duì)于葉子結(jié)點(diǎn)而言，被的先后次序都是先左后右，因此，葉子結(jié)點(diǎn)在先序遍歷、解答：B[[題2]對(duì)于二叉樹的兩個(gè)結(jié)點(diǎn)X和Y，應(yīng)該選擇（）兩個(gè)序A．先序和后 B．先序和中C．中序和后 D．A、B、C都分析：雖然先序和后序無法得出二叉樹的結(jié)構(gòu)，但是可以判斷祖先。其他兩個(gè)序列可以直接得出二叉樹的結(jié)構(gòu)，就可以判斷祖先。解答：D理由二：一棵樹可以轉(zhuǎn)換成一棵沒有右的二叉樹，反之亦然。所以，對(duì)于理由二：一棵樹可以轉(zhuǎn)換成一棵沒有右的二叉樹，反之亦然。所以，對(duì)于n個(gè)結(jié)點(diǎn)（（2）如（1）所述，不一定能得到一棵樹。但是如果所給出的序列合法，就能夠得到一棵樹，而且得到的樹是唯列為p1,p2,…pn，那么只有當(dāng)pn=1時(shí)，而且在p1,p2,…pn-1中亦然。所以，對(duì)于n除去根結(jié)點(diǎn)（即1）以外的n1）在這里23np,,…1就是相應(yīng)二叉樹的中序遍歷序列—— 的理由二：對(duì)于合法的序列：先根序理由二：對(duì)于合法的序列：先根序?yàn)?,,n，后根列p,,…n,1，先可以確定樹根為其形成的森林的先根序列為,,n，后根序列p,,p1，這些森林被分成（m≥0）個(gè)不交的集T2,m，且這些集合的每一個(gè)又都是樹，在先根序列中照,,m的結(jié)點(diǎn)順序出現(xiàn)，在后根序列中也按,,m的結(jié)點(diǎn)序出現(xiàn)（但是對(duì)應(yīng)的每個(gè)i中，結(jié)點(diǎn)出的順序不同）。因此可以找到每棵 的結(jié)點(diǎn)集合，進(jìn)行遞歸處理，最終只能得到一棵確定的樹。[[題4]結(jié)，利用結(jié)點(diǎn)的右孩子指針rchildvoidvoidlink(BiTreebt,BiTNode*head,BiTNodeif(bt!=NULL){if(bt->lchild==NULL&&bt->rchild==NULL)//葉子結(jié)點(diǎn)if(head==NULL){ if(bt->lchild!=NULL)link(bt->lchild,head,tail);if(bt->rchild!=NULL)link(bt-}} f(b,path,pathlen)：將b->data放入path，pathlen++；//其他情況f(b-inti；ifif(b->lchild==NULL&&b-printf(%c到根結(jié)點(diǎn)路徑：%c,b>data);for(i=pathlen-1;i>=0;i--) (“%c”,path[i]);printf(“\n”);} Allpath(b->lchild,path,pathlen);//遞歸掃描左Allpath(b->rchild,path,pathlen);//遞歸掃描右 }}}十二、十二、線索二叉樹 ，也不使用棧（其中后序線索二叉樹中查找后繼仍需要棧）22當(dāng)標(biāo)志位取1[[題索二叉樹中，下面說法不正確的是（）點(diǎn).[[題2]域的個(gè)數(shù)是（）），先序序列的最后結(jié)點(diǎn)的右線索為空（無后繼），共解答：D 1,T2,…,Tn) 其中，T1=(root，t11,t12,…,t1m)；二叉樹B=(LBT,Node(root),RBT)；若F=Φ，則B=Φ；ROOTT1對(duì)應(yīng)得到由(t11t12t1mLBT(T2T3TnRBT若B=Φ,F=Φ；否則，由Node(root)ROOTT122、樹的遍歷可有2（1）先根(次序)依次先根遍歷各 （2）后根(次序)，然 根結(jié)點(diǎn)33、森林的遍歷①森林中第一棵樹的根結(jié)點(diǎn)；②森林中第一棵樹 森林③森林中其他樹構(gòu)成的森林。森林的遍歷可有2①先序遍歷②中序遍歷[[題]用孩子兄弟鏈表表示一棵樹，若要找到結(jié)點(diǎn)p的第5個(gè)孩子，則只要先找到*p的第1個(gè)孩子，然后（）。D.從兄弟域指針連續(xù)掃描4個(gè)結(jié)點(diǎn)即可分析：樹的孩子兄弟鏈表表示法和所對(duì)應(yīng)的二叉樹的二叉鏈表表示法完全一樣，以二叉鏈表作為媒介可導(dǎo)出樹與二叉樹之間的一個(gè)對(duì)應(yīng)關(guān)系。因此可利用二叉樹的算法來實(shí)現(xiàn)對(duì)樹的操作。應(yīng)當(dāng)注意的是，和樹對(duì)應(yīng)的二叉樹，其左、右解答：DB中，X是其雙親的右孩子，下列結(jié)論正確的是（）。右孩子對(duì)應(yīng)原樹結(jié)點(diǎn)的右邊兄弟。所以X一定有左邊兄弟。解答：D十十四、二叉排序樹與平衡二叉樹 左、 ASL值，顯然，由值相同的n個(gè)關(guān)鍵字，構(gòu)造所得的不同形。33、（1）②若二叉排序樹非空，則新結(jié)點(diǎn)的根結(jié)點(diǎn)比較，若小根結(jié)點(diǎn)，則插入左 ；否則插入右 。（2）*p（*），以下三種情況：①被刪除的結(jié)點(diǎn)*p②被刪除的結(jié)點(diǎn)*p③被刪除的結(jié)點(diǎn)*p；?的二叉排序樹：它的左和右都是平衡二叉樹，且左和 高度之差的絕對(duì)值不超過1LL型平衡旋轉(zhuǎn)，A；RR型平衡旋轉(zhuǎn)；A； [[題1]二叉樹為二叉排序樹的（）條件是其任一結(jié)點(diǎn)的值均大A．充分不必 B．必要不充C．充分必 D．既不充分也不必分析：本題主要考查二叉排序樹的定義。由二叉排序樹的定義可知，在二叉排序樹中，任意非終端結(jié)點(diǎn)的關(guān)鍵字的值大于其左上所有結(jié)點(diǎn)的關(guān)鍵字的值（當(dāng)然也大于其左孩子的值）；小于右上所有結(jié)點(diǎn)的關(guān)鍵字的值（當(dāng)然也小于其右孩子的值）。所以，該題的選項(xiàng)中至少應(yīng)該包含必要條件，A、D[[題2]輸入序列為（20,35,…），構(gòu)造平衡二叉樹，當(dāng)在樹中插入值30時(shí)發(fā)生不平衡，則應(yīng)進(jìn)行的平衡旋轉(zhuǎn)是（）。 D.分析：平衡二叉樹的旋轉(zhuǎn)有4將以35為根的樹向右旋轉(zhuǎn)，然后將以20為根的樹向左旋轉(zhuǎn)[[題3]在含有n個(gè)結(jié)點(diǎn)的二叉排序樹中查找一個(gè)關(guān)鍵字，進(jìn)行關(guān)鍵字比較次數(shù)最大值是（）。 B. 解答：D樹和編122在集合F叉樹加入到集合F重復(fù)（2）（3）兩步，當(dāng)F便是所要建立的樹。33樹的總（1）用n個(gè)權(quán)值（對(duì)應(yīng)n個(gè)葉子結(jié)點(diǎn)）構(gòu)樹，共需n-1次合并， 樹中非葉子結(jié)點(diǎn)的總數(shù)為n-1，總結(jié)個(gè)數(shù)為2n-1樹中沒有度為1的結(jié)點(diǎn)因?yàn)榉亲咏Y(jié)點(diǎn)都是通過兩個(gè)結(jié)點(diǎn)合并而來。但是，沒有為的二叉樹并不一是 樹。 44中字符的使用頻率或次數(shù)，構(gòu)造樹。此樹中從根到每個(gè)葉子結(jié)點(diǎn)都有一條唯一的路徑，對(duì)路徑上各分支約定，左分支標(biāo)識(shí)為“0”碼，右標(biāo)識(shí)為“1”碼，則從根結(jié)點(diǎn)到葉子結(jié)點(diǎn)的路徑上分支的“0”、“”碼組成的字符串即為該葉子結(jié)點(diǎn)的55、 樹編碼的總編碼是能使電文代碼總長(zhǎng)最編碼方式。結(jié)論由 樹是帶權(quán)路徑長(zhǎng)度最樹的特征可得。 ，而葉子結(jié)點(diǎn)不可能從根結(jié)點(diǎn)到其他葉子結(jié)點(diǎn)的路徑上所以一個(gè)字符編碼的前綴（3）深度為h。編碼不可能是另一個(gè)字樹，其葉子結(jié)點(diǎn)的最大編碼長(zhǎng)度為h-[[題1]若度為m 樹，其葉子結(jié)點(diǎn)個(gè)數(shù)為n，則非葉子點(diǎn)的個(gè)數(shù)為（）分析：在構(gòu)造度為m樹過程中，每次把m并為一個(gè)父結(jié)點(diǎn)（第一次合并可能少于m個(gè)子結(jié)點(diǎn)），合并減少m1個(gè)結(jié)點(diǎn)，n個(gè)葉子結(jié)點(diǎn)少到最后只剩一個(gè)共需 次合并，每次合并增加一個(gè)非葉子結(jié)解答：C十六、十六、圖的基本概念12、無3、有4、無向完全圖：在一個(gè)含有n個(gè)頂點(diǎn)的無向完全，有n(n-1)/25、有向完全圖：在一個(gè)含有n個(gè)頂點(diǎn)的有向完全，有n(n-1)66789101111、子圖：對(duì)于圖G=（V，E），G’=（V’，E’），若存在是V的子集，E’是E的子集，則稱圖G’是G的一個(gè)子12、連通圖、連通13、強(qiáng)連通圖、強(qiáng)14、生15、生成[[題1]以下關(guān)于圖的敘述中，正確的是（）[[題2]一個(gè)有28條邊的非連通無向圖至少有（）個(gè)頂 分析：88×8/2=2非連通無向圖則有至少9解答：C十七、十七、圖的結(jié)角矩陣的元素即可，又由于主對(duì)角線為0，則至少需要n(n-1)/2空間。對(duì)于有向圖，鄰接矩陣的第i行（或第i列）非零元素（或非∞元素）的個(gè)數(shù)正好是第i個(gè)頂點(diǎn)的出度Dv)（或入度Dv)）。用鄰接矩陣方法圖，很容易確定圖中任意兩個(gè)頂點(diǎn)之間是否有邊相測(cè)，所花費(fèi)的時(shí)間代價(jià)很大。這是用鄰接矩陣圖的局限性。稠密圖適合用鄰接矩陣的若無向圖中有n個(gè)頂點(diǎn)、e條邊，則它的鄰接表需n個(gè)頭結(jié)點(diǎn)和2e個(gè)表結(jié)點(diǎn)。稀疏圖用鄰接表表示比鄰接矩陣節(jié)省空間，當(dāng)和邊相關(guān)的信息較多時(shí)更是如此。在鄰接表上容易找到任一頂點(diǎn)的第一個(gè)鄰接點(diǎn)和下一個(gè)鄰接點(diǎn)，但要判定任意兩個(gè)頂點(diǎn)（vi和vj）之間是否有邊或弧相連，則需搜索第i個(gè)或第j個(gè)鏈表，因此，這種方法不及鄰接矩陣方便。34^^例例abcde441a121^4^2b3c32344d5e52^3^5^[[題 n個(gè)頂點(diǎn)的無向圖的鄰接表中邊表結(jié)點(diǎn)總數(shù)最多有（） D.n(n-分析：nnn1表中，每條邊對(duì)應(yīng)兩個(gè)邊表結(jié)點(diǎn)。解答：D十十八、圖的遍歷1、圖的遍歷通常有深度優(yōu)先搜索和廣度優(yōu)先搜索兩種方式一個(gè)非遞歸過程。（1）①遞歸算法②非遞歸 時(shí)間復(fù)雜度為O(n2)。當(dāng)以鄰接表作結(jié)構(gòu)時(shí)，深度優(yōu)先搜索遍歷圖的時(shí)間復(fù)雜度為O(n+e)。深度優(yōu)先搜索遍（（2）廣度優(yōu)先搜索：廣度優(yōu)搜索遍圖的時(shí)間復(fù)雜度深度優(yōu)先搜索遍歷的相同，兩者不處僅僅在于對(duì)頂點(diǎn) 的順序不同。所有頂點(diǎn)，則該圖一定是（）。 到圖中的所有頂點(diǎn)，但若無向圖是非連通圖，則只頂點(diǎn)不可能到。解答：B[[題2]假設(shè)圖G，設(shè)計(jì)一個(gè)算法，輸出圖G從頂點(diǎn)u到v的長(zhǎng)度為k。由于在搜索過程中，每個(gè)頂點(diǎn)只，所以這條路徑必定是一條簡(jiǎn)單路徑。因此，在搜索過程中，需要把當(dāng)前的搜索線路記錄下來。為了記錄當(dāng)前的搜索路徑，可設(shè)立一個(gè)數(shù)組pth保存走過的路徑，用d記錄走過的路徑長(zhǎng)度。若當(dāng)前掃描到的結(jié)點(diǎn)u等于v且路徑長(zhǎng)度為kath。voidvoidPathAll(ALGraph*G,intu,intv,intk,intpath[],intintm,i; ode*p; 路徑長(zhǎng)度加 ifu=v&&d=k)fori=0;i<=d;i++)printfpath[i輸出一條路徑p=G->adjlist[u].firstarc;//p指向頂點(diǎn)u的第一條弧的弧頭結(jié)點(diǎn)while if(visited[m]==0) ，則用遞歸p->nextarc;} } 十九、圖的最小生成樹問題十九、圖的最小生成樹問題1法算2 姆（Prim）算法的基本思3 （Kruskal）算法的基本思4、Prim算法的時(shí)間復(fù)雜度為O(n2)[[題1]設(shè)有無向圖G=（V，E）和G’=（V’，E’），如果G’是G的生成樹，則下面不正確的說法是（）。A.G是G的連通分 B.G是G的無環(huán)子C.G’是G的子 G’是G的極小連通子圖且B、而選項(xiàng)A為概念錯(cuò)誤。解答：A二十、二十、圖的拓?fù)渑判騿栴}1、拓?fù)溆行蛐蛄惺茿OV網(wǎng)G中的頂點(diǎn)所構(gòu)成的有序序列1,…,i,…,n），AOVAOV33、對(duì)AOV網(wǎng)進(jìn)行拓?fù)渑判虻姆椒ê?。?dāng)有向圖中無環(huán)時(shí)，也可用深度優(yōu)先遍歷的方法進(jìn)行拓?fù)渑判颍碊F撲有序序列。[[題1]出一個(gè)有向圖是否有回路（）A．深度優(yōu)先遍歷BC．求最短路 D．求關(guān)鍵路（2）設(shè)圖是n個(gè)頂點(diǎn)的無向圖，若的邊數(shù)e≥n一定有回路存在。理由是：設(shè)整個(gè)圖G的度之和為N，則N≥2n，又因?yàn)閳D中邊數(shù)，因此圖G至少有n條邊因?yàn)槎嘤趎-1條邊的圖中必然存在回路，所以圖G中一定有回路解答：A[[題2]已知帶權(quán)圖G＝（V，E），其中V＝{v1，v2，v3，v4，v5，v6＝{<v1，v2>，<v1，v4>，<v2，v6>，<v3，v1>，<，<v5，v2>，<v5，v6>},G的拓?fù)湫蛄惺牵ǎ? D．v1，v4，v3，v5，v2，v6二二十一、圖的關(guān)鍵路徑問題22求AOV網(wǎng)中所 的最早發(fā)生時(shí)間求AOV網(wǎng)中所 的最遲發(fā)生時(shí)間求AOV網(wǎng)中所有活動(dòng)的最早發(fā)生時(shí)間求AOV網(wǎng)中所有活動(dòng)的最遲發(fā)生時(shí)間（5）求AOV網(wǎng)中所有活動(dòng) 余量 ； （6）找出所有 )為0的活動(dòng)構(gòu)成的關(guān)鍵路徑, ve(源點(diǎn)ve(k)=Max{ve(j)+dut(<j,vl(匯點(diǎn)ve(匯點(diǎn)vl(j)=Min{vl(k)–dut(<j,e[i]=l[i]的活動(dòng)就是關(guān)鍵活動(dòng)，關(guān)鍵活動(dòng)所在的路徑就是關(guān)鍵路徑[[題1]下面關(guān)于關(guān)鍵路徑的問題中說法正確的是（）IA．僅Ⅰ和IIB．僅Ⅰ和IIIC．僅ⅠD．僅III解答：D[[題2]下面關(guān)于工程計(jì)劃的AOE網(wǎng)的敘述中，不正確的是（）二十二、二十二、圖的最短路徑問題法的時(shí)間復(fù)雜度也是O(n3)[[題1]下列說法不正確的是（）I求從指定源點(diǎn)到其余各頂點(diǎn)的Dijkstra最短路徑算法中弧上權(quán)值可以為負(fù)值IV求單源路徑的Dijkstra算法不適合用于有回路A.I、II、III、 B.I、 C.I、III、 D.II、分析：每次以一個(gè)頂點(diǎn)為源點(diǎn)，重復(fù)利用Dijkstra算法n次求得每一對(duì)不同頂點(diǎn)間的最短路徑，其算法時(shí)間為O(n3)，因此II正確；而最短路徑算法要求弧的權(quán)值必須為正數(shù)，所以I、III錯(cuò)誤；Dijkstra算法可用于有回路的有向網(wǎng)，例如知識(shí)點(diǎn)聚焦22的例題1中就是有回路的有向網(wǎng)。解答：C。二十三、二十三、順序查找、折半查找、分塊查找順序查找算法的時(shí)間復(fù)雜度為O(n)。它的缺點(diǎn)是當(dāng)n，平均查找長(zhǎng)度較大，效率低；優(yōu)點(diǎn)是表的結(jié)構(gòu)是順22。對(duì)表中每個(gè)數(shù)據(jù)元素的查找過程，二叉樹來描述，稱這個(gè)描述折半查找過程的二叉樹為判定表的中間結(jié)點(diǎn)是二樹的根，左子表相當(dāng)于左 ，右相當(dāng)于右。折查找的過程是從根結(jié)點(diǎn)到待查找結(jié)過程，不論查找成或失敗，查找長(zhǎng)度均不超過樹的高因此，如果有序表長(zhǎng)度為n，那么在查找成功時(shí)給定值行比較的關(guān)鍵字個(gè)多為。折半查找的時(shí)間效率折半查找的時(shí)間效率為Oo2n。可見折半查找的效率比順序查找高，但折半查找只適用于有，且限于順序 構(gòu)（對(duì)線性鏈表無法有效地進(jìn)行折找）。因此，折半找不適用于對(duì)查找表頻繁插入和刪適合表中元素變化少而查找頻繁的情況。3比較的特征。同時(shí)，考生要特別注找在順序結(jié)構(gòu)鏈?zhǔn)浇Y(jié)構(gòu)上的區(qū)別。44、分塊查找分塊查找法要求將列表組織成以下索引順序結(jié)構(gòu)：首先將列表分成若干個(gè)塊（子表）塊的長(zhǎng)度均勻，最后一塊可以不滿。每塊中元素任意排構(gòu)造一個(gè)索引表。其中每個(gè)索引項(xiàng)對(duì)應(yīng)一個(gè)塊并記錄每塊的起始位置，以及每塊中的最大關(guān)鍵字（或最小關(guān)鍵字）214078查找長(zhǎng)度為L(zhǎng)B，以及在相應(yīng)塊內(nèi)進(jìn)行順序查找的平均查找長(zhǎng)度為L(zhǎng)W假定將長(zhǎng)度為n的表分成b塊，且每塊含s個(gè)元素，則b=n/s。又假將將題15（若最后一個(gè)結(jié)點(diǎn)的數(shù)據(jù)元素不滿50），法查找值為nn0typedefstructnode{intA[m]；structnode*next;//指向下一結(jié)點(diǎn)的指針typedefstruct{intj; LNode*s;

n){rcd*R;while&&!found){forif(p->A[jn)found=1;//查找成功if(p==NULL)returnelse R.j=i;return}}[[題2]順的某線性表共有123個(gè)元素，按分塊查找的要等分為3塊。若對(duì)索引表采用順序查找方法來確定子塊，在確定的子塊中也采用順序查找方法，則在，分塊查找成功的平均查找長(zhǎng)概率況 B. C. D.SL=(2s+n/2題中，n=1，s=23/=41，23。解答二十四、二十四、B‐樹與B+1、一棵m階的B-樹，或者為空樹，或?yàn)闈M足下列特性的m⑴樹中每個(gè)結(jié)點(diǎn)至多有m ⑶除根結(jié)點(diǎn)之外的所有非終端結(jié)點(diǎn)至少有m/2棵Kii=12…n)，An所指中所有結(jié)點(diǎn)的關(guān)鍵碼均大于Kn，m/22、B-2、B-樹的基本（1）B-樹的查找類似二叉排序樹的查找，不同的是-樹每個(gè)結(jié)點(diǎn)上是多關(guān)鍵碼的有序表，在到達(dá)某個(gè)結(jié)點(diǎn)時(shí)，先在有序表中查找，若找到，則查找成功；否則，到按照對(duì)應(yīng)的指針信息指向的子樹中去查找，當(dāng)?shù)竭_(dá)葉子結(jié)點(diǎn)時(shí)，則說明樹中沒有對(duì)應(yīng)的關(guān)鍵碼，查找失敗。即在-樹上的查找過程是一個(gè)順指針查找結(jié)點(diǎn)在含有n個(gè)關(guān)鍵碼的B點(diǎn)的路徑上涉及的結(jié)點(diǎn)數(shù)不超過（2）（2）B-樹的生成是從空樹開始，逐個(gè)插入關(guān)鍵字而得。但由于B-樹結(jié)點(diǎn)中的關(guān)鍵字個(gè)數(shù)必須大于等于m/21，因此，每次插入一個(gè)關(guān)鍵字不是在樹中添加一個(gè)葉子結(jié)點(diǎn)，而是首先在最低層不超過m1，則插入完成，否則要產(chǎn)生結(jié)點(diǎn)的（3）在B-”33、一棵m階的B+樹和m階的B-樹的差異在于：有n 的結(jié)點(diǎn)中含有n個(gè)關(guān)鍵碼自小而大地順序；其根結(jié)點(diǎn)中最大（或最?。╆P(guān)。[[題1]下面關(guān)于m階B-樹說法正確的是（） IV當(dāng)插入一個(gè)數(shù)據(jù)引起B(yǎng)-A．I、II、 B．II、C．II、III、 [[題2]下面關(guān)于B-樹和B+樹的敘述中，不正確的是（）A．B-樹和B+樹都是平衡的多分支B．B樹和B+樹都可用于文件的索引結(jié)構(gòu)分析：因?yàn)?樹所有的葉子結(jié)點(diǎn)中包含了全部關(guān)鍵字信息，以及指向含有這些關(guān)鍵字記錄的指針，且葉子結(jié)點(diǎn)本身依關(guān)鍵字的大小自小到大地順序，所以支持從根結(jié)點(diǎn)的隨機(jī)檢索和直接從葉子結(jié)點(diǎn)開始的順序檢索，但是-樹不具有這種結(jié)構(gòu)特性，所以只支持從根解答：D二十五、二十五、在一般情況下，很容易產(chǎn)生 ”現(xiàn)象，即：key1，而f(key1)=f(key2)H(key)=keyMODp 33Hi=H +diMOD1≤i<m ②二次探測(cè)法 Hi=(H(key)±di)MOD其中：di為增量序列12，-12，22，-22，……，q2，-q2且q≤m/2。特點(diǎn)是：發(fā)生時(shí)，在表的左右進(jìn)行跳躍式探測(cè)，比較靈活。（2）鏈地址法：將所有散列地址相同的記錄都在同一鏈表中。在這[[題1]下列有關(guān)散列查找的敘述正確的是（） D.若散列表的裝填因子α<<1，則可避 得到，散 法 數(shù)據(jù)，所以選項(xiàng)A正確；散 關(guān)鍵字不一定總是存放在一片連續(xù) 單元中，選項(xiàng)C錯(cuò)誤；裝填解答：A。[題2][題2]散列表的平均查找長(zhǎng)度）與處 方法有關(guān)而與表的長(zhǎng)度無與處 方法無關(guān)而與表的長(zhǎng)度有與處 方法有關(guān)且與表的長(zhǎng)度有與處 方法無關(guān)且與表的長(zhǎng)度無、與處理 方法有關(guān)、與表的裝子有關(guān)，但與表的關(guān)。解答：A[[題3]采用散列函數(shù)H(k)=3×kMOD13并用線性探測(cè)開放地 構(gòu)造散列表（畫示意圖裝填因等概率情況下查找成功的平均查找長(zhǎng)等概率情況下查找失敗的平均查找長(zhǎng)度[[題 已知一組關(guān)鍵字為，51，25），鏈地址法解決。設(shè)裝填因子=.7，散列函數(shù)的形式為Hke =keyMODp，回答下列問題：構(gòu)造散列函畫出散列計(jì)算出等概率情況下查找成功的平均查計(jì)算出等概率情況下查找不成功的平均查找長(zhǎng)，查找成功表示找到了關(guān)鍵字集合中的某記錄的比較次數(shù)，查找不成功表示在散列表中未找到指定關(guān)鍵字的記錄的比較次數(shù)。首先，首先，回憶一下串匹配(查找)的定義INDEX(S,T,初始條件：ST存在，T1≤pos≤StrLength(S)操作結(jié)果：ST次出現(xiàn)的位置;否則函數(shù)值為0。intintIndex(StringS,StringT,intpos)回第一個(gè)這樣的子串在S中的位置，否則返回0if(pos>0)n=StrLength(S);m=StrLength(T);i=while(i<=n-m+1)SubString(sub,S,i,if pare(sub,T)!=0)++ielse}//}//return //}//一、簡(jiǎn)單算法二、首尾匹配算法J.H.Morris)算法intintIndex(SStringS,SStringT,intpos)返回子串T在主串S中第pos個(gè)字符之后的位置。若不存在，則函數(shù)值為0其中，T非空，1≤pos≤StrLenthSi=pos;j=while(i<=S[0]&&j<=T[0])if(S[i]T[j])++i;++j}elseii-j+2;j1;}if(j>T[0])returni-elsereturn}//二、二、首尾匹配intintIndex_FL(SStringS,SStringT,intpos)sLength=S[0];tLength=T[0];i=pos;patStartChar=T[1];patEndChar=while(i<=sLength–tLength+1)if(S[i]patStartChar++i;//elseif(S[i+tLength-1]!=patEndChar)else}return}KMP算法的時(shí)間復(fù)雜度可以達(dá)到S[iT[j時(shí)，若已 T[1..k-1]==T[j-k+1..j-則 定義：定義：模式串的next[題1]串[題1]串‘a(chǎn)babaaababaa’的n