2014考研計算機數(shù)據(jù)結構沖刺課程講義

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