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)算是語(yǔ)句x++，設(shè)其執(zhí)行時(shí)間為Tn解答：D==n(n-1)/2=[[題 以下算法的時(shí)間復(fù)雜度是 ）voidfn){inti=0;}A. B. C.O(nlog2n)D.)分析：基本運(yùn)算是語(yǔ)句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)≤n12、線性表有順序和鏈?zhǔn)絻?結(jié)構(gòu) 操作平均移動(dòng)n/2個(gè)結(jié)點(diǎn)，刪除操作平均移動(dòng) 網(wǎng)絡(luò)課堂系列 #defineLISTSIZEtypedef ElemType//當(dāng)前#defineLIST_INIT_SIZE#defineLISTINCREMENTtypedefstruct{ElemType*elem;//初始分配//分配}（（2）間的邏輯關(guān)系，必須附加指針來(lái)表示，這也導(dǎo)致線性表的空間利用率降低。但在鏈表中或刪除操作始，只需修改相關(guān)結(jié)點(diǎn)的指針域即可，不typedefstruct data;//數(shù)據(jù)域structLNode*next;//指針域} [[題1]設(shè)線性表有n個(gè)元素，以下操作中，（）在順序表上D．輸出與給定值x相等的元 性表中的序[[題2]采用順結(jié)構(gòu)的線性表算法中，當(dāng)n個(gè)空已滿時(shí)，可申請(qǐng)?jiān)僭黾臃峙鋗個(gè)空間。若申請(qǐng)失敗，則明系統(tǒng)沒(méi)有（）可分配的 A．m個(gè)B．m個(gè)連續(xù)的 表的順 順序存放線性表的各元素解答移動(dòng)上，在第i個(gè)位置上xai到an2、順序表的刪除運(yùn)算與運(yùn)算相同，其時(shí)間主要消耗在了移動(dòng)表中元素上，刪除第i個(gè)元素時(shí)，其后面的元素ai+1～an都要向上移動(dòng)一個(gè)位置，共移動(dòng)了n-i個(gè)元素。時(shí)間復(fù)雜度為Ｏ(n)。 [ ]網(wǎng)絡(luò)課堂系 計(jì)算 根據(jù)設(shè)計(jì)思想，采用C或C++或JAVA語(yǔ)言表述算法，關(guān)鍵之處給出；分析：此題主要考查線性表的順序結(jié)構(gòu)（這里為數(shù)組）的應(yīng)用。算法的基。這樣，可使算法的時(shí)間復(fù)雜度為O(n){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;}}}1、建立單鏈表（1）頭插法2、鏈表中查找第i法3、鏈表 運(yùn)5法 voidCrea n){LNode*s;inti; s->next=L- }}voidCrea istR(LinkList&L,ElemTypea[],intn){LNode*s，*r;inti;r=L；∥rfor(i=0;i<n;i++)r-r=s;;}[[題1]采用法對(duì)單鏈表中的元素進(jìn)行排序，其中L鏈表的頭結(jié)點(diǎn)指針，鏈表元素的數(shù)據(jù)類型為整型int分析：此題主要考查線性表的鏈?zhǔn)浇Y(jié)構(gòu)的應(yīng)用，此題空鏈表，然后將待排序鏈表的結(jié)點(diǎn)依次這個(gè)空鏈表，所有結(jié)點(diǎn) 完畢后，這個(gè)新生成的鏈表就是所的有序鏈voidvoidInsertsort（LinkList{LNode// r=L;q=L-while(q!=NULL&&q->data<=p-} }s->next=① t=p-p->data=② s->data= 分析：采用的方法是在p所指結(jié)點(diǎn)之一個(gè)s所指結(jié)點(diǎn)時(shí)一個(gè)s所指結(jié)點(diǎn)，然將p所指結(jié)點(diǎn)和s所指結(jié)點(diǎn)的數(shù)據(jù)域進(jìn)行交換解答：①p->next②s voidvoidIntersection(LinkListha,LinkListhb,LinkList∥將ha和 同的元素到單鏈表hcLNodeInsertsort(ha);∥參考題1將ha指向的單鏈表由小到大排序Insertsort(hb);∥參考題1將hb指向的單鏈表由小到大排序 ∥申請(qǐng)頭hc-whliewhlie(pa&&if(pa->data<pb- pb=pb->nxtelse{∥pa和pbpc=(LNode*)malloc(sizeof(LNode));∥pb=pb-∥}}結(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-順序不能完成在*p結(jié)點(diǎn)之后結(jié)點(diǎn)*q的操作。1、棧是運(yùn)算受限（限制在表的一端）的線性表，允許、刪除的這一端稱為棧頂，—可以使數(shù)據(jù)通過(guò)棧后仍然保持次，對(duì)于順序結(jié)構(gòu)的棧還需注意（1）進(jìn)[[題1]設(shè)n個(gè)元素進(jìn)棧序列是p1，p2，p3，…，pn，其輸值是。A.n- B.n- D.有多種可，p2，p3，…，pn進(jìn)棧，然后依次出棧，即pn- 解答：C1、隊(duì)列是運(yùn)算受限（在表的一端進(jìn)行，而刪除在表的另一端進(jìn)行）的線性表，允許的一端稱為隊(duì)尾，把允許刪除的一端稱使隊(duì)列的向量空間得到充分的利用。判斷循環(huán)隊(duì)列的“空”和 加入兩個(gè)元素后，rear和front的值分別為（）。A．1和 B.2和 C.4和 D.5和解答：BLOC(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]（上）三角中的元后，接著對(duì)角線上（下）方的到SA[n(n+1)/2+1]中，aij的下標(biāo)i、j與在SA[k]將對(duì)角矩陣A與在SA[k]中的對(duì)應(yīng)元素的下標(biāo)k的關(guān)到一維數(shù)組SA[0..u-1]中，aij的下標(biāo)i、當(dāng)0≤i，j≤n-1時(shí)例如：將三對(duì)角矩陣A與在SA[k]中的對(duì)應(yīng)元素的下標(biāo)k的關(guān)系為：當(dāng)0≤i，j≤n-0≤k＜3n-2時(shí)，k=2i+j到SA[3n-2]中，aij的下標(biāo)i、[[題 設(shè)矩陣A[1..n][1..n]是一個(gè)對(duì)稱矩陣，為了節(jié)省空間，下三角部分按行序存放在一維數(shù)組B[1..n(n-1)/2]下三角部分中任一元素置k的值為 ）—BA.i(i-1)/2+j- B.i(i- C.i(i+1)/2+j- D.分析：對(duì)稱矩陣A的下標(biāo)從1開始，對(duì)于任一元素aij（由于共有i(i-1)/2+j-1個(gè)元素，k=i(i-1)/2+j-1+1=i(i-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可知，解答：B九、樹、九、樹、二叉樹結(jié) 從左到右的順序進(jìn)行，如果為i（1≤i≤n）的結(jié)點(diǎn)與滿二叉樹中為i的33、二叉樹 結(jié)（1）順 結(jié)完全二叉樹和滿二叉樹采用順比較合適，樹中結(jié) 靈活、操作方便，對(duì)于一般情況的二叉樹，甚至比順序結(jié)構(gòu)還節(jié)省空間。因此，二叉鏈表是最常用的二叉樹方式。typedef emTypestructBiTNode*lchild;*rchild;//BiTree [[題2]設(shè)二叉樹只有度為0和2的結(jié)點(diǎn)，其結(jié)點(diǎn)個(gè)數(shù)為15二叉樹的最大深度為 ）。由于結(jié)點(diǎn)個(gè)數(shù)為15，因此二叉樹的深度h為8解答：C性質(zhì)性質(zhì)4：具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度k。的順序?qū)Χ鏄渲械乃薪Y(jié)點(diǎn)從1開始順序，則對(duì)于任意的序號(hào)二二叉樹性質(zhì)的度為1的結(jié)點(diǎn)，N2個(gè)度為2的結(jié)點(diǎn)，，Nm個(gè)度為m的結(jié)①有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叉樹的高度 ①，為p=1的結(jié)點(diǎn)無(wú)父結(jié)點(diǎn)，否為p結(jié)點(diǎn)的父 ②為p的結(jié)點(diǎn)的第k-1個(gè)孩子為p×k，所以，如號(hào)為p結(jié)點(diǎn)有孩子，其第i個(gè)孩子為p×k+(i 為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é)共有（）個(gè)葉結(jié)點(diǎn)。 分析：由二叉樹性質(zhì)3的推廣，度為7的樹應(yīng)該有解答：D十十一、二叉樹的遍歷及應(yīng)先序遍歷：遞歸算法、非遞歸層次遍 [[題1]任何一棵非空二叉樹中的葉子結(jié)點(diǎn)在先序遍歷、中序遍歷與后序遍歷中的相對(duì)位置（）。A．都會(huì)發(fā)生改 B．不會(huì)發(fā)生改C．有可能會(huì)發(fā)生改 D．部分會(huì)發(fā)生改或是后序遍歷（LRD），對(duì)于葉子結(jié)點(diǎn)而言，被的解答：B[[題2]對(duì)于二叉樹的兩個(gè)結(jié)點(diǎn)X和Y，應(yīng)該選擇（）兩個(gè)序A．先序和后 B．先序和中C．中序和后 D．A、B、C都解答：D反例（給出任何一個(gè)正確的反例即可 結(jié)voidvoidlink(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->rchild,head,tail);}} 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);//遞歸掃描右子樹 }}}十二、十二、這樣 ，也不使用棧（其中后序線索二叉樹中查找后繼仍需要棧）索二叉樹中，下面說(shuō)法不正確的是（） A．不確 解答：D 1,T2,…,Tn) 其中，T1=(root，t11,t12,…,t1m)；二叉樹B=(LBT,Node(root),RBT)；若F=Φ，則B=Φ；由(t11t12t1mLBT(T2T3TnRBT若B=Φ,則F=Φ；否則，由Node(root)ROOTT1 33、森林的遍①森林中第一棵樹的根結(jié)②森林中第一棵樹的子樹③森林中其他樹構(gòu)成的森森林的遍歷可有2條搜索路①先序②中序孩子，則只要先找到*p的第1個(gè)孩子，然后（）。解答：D 解答：D十十四、二叉排序樹與平衡二ASLn個(gè)關(guān)鍵字，構(gòu)造所得的不同形。33、（1） 注意：在二叉排序樹 的結(jié)點(diǎn)均作為葉子結(jié)點(diǎn)①被刪除的結(jié)點(diǎn)*p，且左子樹和右子樹高度之差的絕對(duì)值不超過(guò)1LL型平衡旋轉(zhuǎn)，A；RR型平衡旋轉(zhuǎn)；A； A．充分不必 B．必要不充C．充分必 D．既不充分也不必值30時(shí)發(fā)生不平衡，則應(yīng)進(jìn)行的平衡旋轉(zhuǎn)是 ） D.[[題 在含有n個(gè)結(jié)點(diǎn)的二叉排序樹中查找一個(gè)關(guān)鍵字，進(jìn)關(guān)鍵字比較次數(shù)最大值是 B.） 解答：D十十五、哈夫曼樹和哈夫曼編33、對(duì)哈夫曼樹的55、對(duì)哈夫曼樹編深度為h的哈夫曼樹，其葉子結(jié)點(diǎn)的最大編碼長(zhǎng)度為h-。 解答：C十十六、圖的基本概1、2、無(wú)向3、有向4、無(wú)向完全圖：在一個(gè)含有n個(gè)頂點(diǎn)的無(wú)向完，有n(n-1)/2條邊5、有向完全圖：在一個(gè)含有n個(gè)頂點(diǎn)的有向完，有n(n-1)條邊1111、子圖：對(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條邊的非連通無(wú)向圖至少有）個(gè)頂 解答：C結(jié)之間的鄰接關(guān)系（鄰接矩陣的形式描述）角矩陣的元素即可，又由于主對(duì)角線為0，則至少需要n(n-1)/2空間。行（或第列）非零元素（或非元素）的個(gè)數(shù)正好是第i個(gè)頂點(diǎn)的度TD(i。行（或第列）非零元素（或非元素）的個(gè)數(shù)正好是第i個(gè)頂點(diǎn)的出度(i（或入度(i)）。用鄰接矩陣方法圖，很容易確定圖中任意兩個(gè)頂點(diǎn)之間是否有邊相測(cè)，所花費(fèi)的時(shí)間代價(jià)很大。這是用鄰接矩陣圖的局限性。稠密圖適合用鄰接矩陣的22、鄰接表是圖的一方法，類似n個(gè)頂點(diǎn)、條邊，則它的鄰接表需個(gè)頭結(jié)點(diǎn)和2個(gè)表結(jié)點(diǎn)。稀疏圖用鄰接表表示比鄰接矩陣節(jié)省多時(shí)更是如此。（i和j）i個(gè)或第j例a例abcd111^ ^344 4 4 ^13c鏈34^^例例abcde441a121^4^2b3c32344d5e52^3^5^[[題 n個(gè)頂點(diǎn)的無(wú)向圖的鄰接表中邊表結(jié)點(diǎn)總數(shù)最多有 ） D.n(n-解答：D1、圖的遍歷通常有深度優(yōu)先搜索和廣度優(yōu)先搜索兩種（1）①遞歸算法②非 先搜索遍歷圖的時(shí)間復(fù)雜度為O(n+e)。深度優(yōu)先搜索遍點(diǎn)的順序不同。 解答：B[[題2]假設(shè)圖G，設(shè)計(jì)一個(gè)算法，輸出圖G。由于在搜索過(guò)程中，每個(gè)頂點(diǎn)只voidvoidPathAll(ALGraph*G,intu,intv,intk,intpath[],intintm,i; ode*p; 路徑長(zhǎng)度加 if(u==v&&d==k)for(i=0;i<=d;i++)printf(path[i]);//輸出一條路徑 arc;//p指向頂點(diǎn)u的第一條弧的弧頭結(jié)點(diǎn)while if(visited[m]==0) p->nextarc;}} 3、克魯 （Kruskal）算法的基本思 A.G是G的連通分 B.G是G的無(wú)環(huán)子C.G’是G的子 G’是G的極小連通子圖且解答：A1、拓?fù)溆行蛐蛄惺茿OV網(wǎng)G中的頂點(diǎn)所構(gòu)成的有序序列1,…,i,…,n），33、對(duì)AOV網(wǎng)進(jìn)行拓?fù)渑判虻姆椒ā?A．深度優(yōu)先遍 B．廣度優(yōu)先遍C．求最短路 D．求關(guān)鍵路理由是：設(shè)整個(gè)圖G的度之和為N，則N≥2n，又因?yàn)閳D中邊數(shù)，因此圖G至少有n條邊因?yàn)槎嘤趎-1條邊的圖中必然存在回路，所以圖G解答：A[[題2]已知帶權(quán)圖G＝（V，E），其中 ＝{<v1，v2>，<v1，v4>，<v2，v6>，<v3，v1>，<，<v5，v2>，<v5，v6>},G的拓?fù)湫蛄惺牵ǎ? 二二十一、求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)鍵路徑的問(wèn)題中說(shuō)法正確的是（）A．僅Ⅰ和IIB．僅Ⅰ和IIIC．僅ⅠD．僅III解答：D二十二、二十二、法的時(shí)間復(fù)雜度也是O(n3)[[題1]下列說(shuō)法不正確的是（）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ù)利用Dijkstr算法n次求得每一對(duì)不同頂點(diǎn)n3)，因此I正確；而最短路徑算法要求弧、III錯(cuò)誤；Dijkstr算法可用于有回路的有向網(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)是順。 44、分塊查找分塊查找法要求將列表組織成以下索引順序塊的長(zhǎng)度均勻，最后一塊可以不滿。每塊中元素任意排例如例如順序 索索引順序214078定表中每個(gè)元素的查找概率相等，則每個(gè)索引項(xiàng)的查找概率為1/b，塊將將typedefstructnode{intA[m]；structnode*next;//指向下一結(jié)點(diǎn)的指針typedefstruct{intj; LNode*s;

n){rcd*R;while&&!found){forifp->A[j]=nfound=1;//p=p-if(p==NULL)returnNULL;else{ R.j=i;return}}[[題2]順的某線性表共有123個(gè)元素，按分塊查找等分為3塊。若對(duì)索引表采用順序查找方法來(lái)確定子塊在確定的子塊中也采用順序查找方，分塊查找成功的平均查概率況B.C.D.解答二十四、二十四、B‐樹與B+1、一棵m階的B-樹，或者為空樹，或?yàn)闈M足下列特性的m⑴樹中每個(gè)結(jié)點(diǎn)至多有m⑶除根結(jié)點(diǎn)之外的所有非終端結(jié)點(diǎn)至少有m/2Kii=12…n)，An所指子樹中所有結(jié)點(diǎn)的關(guān)鍵碼均大于Kn，m/222、B-樹的基本（1）查點(diǎn)的路徑上涉及的結(jié)點(diǎn)數(shù)不超過(guò)B-關(guān)鍵字而得。但由于B-結(jié)點(diǎn)中的關(guān)鍵字個(gè)數(shù)必須大于等于m/21一個(gè)關(guān)鍵字不是在樹中添加一個(gè)葉子結(jié)點(diǎn)，而是首先在最低層的某個(gè)非終端結(jié)點(diǎn)中添加一個(gè)關(guān)鍵字，若該結(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù)不超過(guò)m1（3）在B-完成，否則要產(chǎn)生結(jié)點(diǎn)的”33、一棵m階的B+樹和m階的B-樹的差有n棵子樹的結(jié)點(diǎn)中含有n個(gè)關(guān)鍵 [[題1]下面關(guān)于m階B-樹說(shuō)法正確的是（） IV 一個(gè)數(shù)據(jù)引起B(yǎng)-樹結(jié)A．I、II、 B．II、C．II、III、 [[題2]下面關(guān)于B-樹和B+樹的敘述中，不正確的是（）B．B樹和B+樹都可用于文件的索引結(jié)構(gòu)到大地順序，所以支持從根結(jié)點(diǎn)的隨機(jī)檢索和直接從葉子結(jié)點(diǎn)二十五、二十五、 ”現(xiàn)象，即：key1，而f(key1f(key2)H(key)=keyMOD Hi=H +diMOD1≤i<m其中：di1，2，……，m-1，且di=i ②二次探測(cè)法 Hi=(H(key)±di)MOD其中：di為增量序列12，-12，22，-22，……，q2，-q2且q≤m/2。 種方法中，散列表每個(gè)單元存放的不再是記錄本身，而是相應(yīng)同義44，但找到位置的平均探查次數(shù)，它是表中所有可能散列到的位置上要新元素時(shí)為找到空位置的探查次數(shù)的平均[[題1]下列有關(guān)散列查找的敘述正確的是（） D.若散列表的裝填因子α<<1，則可避 的產(chǎn) ，所以選項(xiàng)A正確；散列是指多個(gè)不同關(guān)鍵字對(duì)應(yīng)相，選項(xiàng)B錯(cuò)誤；用線性探測(cè)法解決的散列表中，散列函數(shù)值相同的關(guān)鍵字不一定總是存放在一片連續(xù)的單元中，選項(xiàng)C錯(cuò)誤；裝填因子α越小，發(fā)生的概率越小，但仍有可能發(fā)生。解答：A[[題2]散列表的平均查找長(zhǎng)度） 解答：A[[題3]采用散列函數(shù)H(k)=3×kMOD13并用線性探測(cè)開放地 構(gòu)造散列表（畫示意圖裝填因等概率情況下查找失敗的平均查找長(zhǎng)度[[題 已知一組關(guān)鍵字為列函數(shù)的形式為Hke =keyMODp，回答下列問(wèn)題：分析：本題是對(duì)散列表的一種常見(jiàn)考查方式。采用鏈地址，查找成功表示找到了關(guān)鍵字集合中的某記錄的比較次數(shù)，查找不成功表示在散列表中未找到指定關(guān)鍵字的記錄的比較次數(shù)。首首先，回憶一下串匹配(查找)的定義INDEX(S,T,初始條件：ST存在，T1≤pos≤StrLength(S)操作結(jié)果：若主串S中存在和串T值相同的Spos個(gè)字符之后第一次出現(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 }//J.H.Morris)算法intintIndex(SStringS,SStringT,intpos)//其中，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}//二、二、首尾匹配算n-1intintIndex_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(D.E.KnuthV.R.Pratt,J.H.MorrisKMP算法的時(shí)間復(fù)雜度可以達(dá)到S[iT[j時(shí)，S[i-j+1..i-1]==T[1..j-若已 T[1..k-1]==T[j-k+1..j-則 S[i-k+1..i-1]==T[1..k-定義：定義：模式串的next[[題1]串‘a(chǎn)babaaababaa’的next數(shù)組為 intintIndex_KMP(SStringS,SStringT,intpos)//1≤pos≤StrLength(S)i=pos;j=1;while(i<=S[0]&&j<=T[0])if(j=0||S[i]==T[j]){++i;++j;elsej if(jT[0])returni- elsereturn}/