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

[[題1]以下算法的時間復(fù)雜度是（）voidfn){inti,j,fori=1i<nfor(intj=n;j>=i+1;j--)x++；} B. C.O(nlog2n)D.分析：基本運算是語句x++，設(shè)其執(zhí)行時間為Tn解答：D==n(n-1)/2=[[題 以下算法的時間復(fù)雜度是 ）voidfn){inti=0;}A. B. C.O(nlog2n)D.)分析：基本運算是語句i++，設(shè)其執(zhí)行時間為則有T(n)×T(n)×T(n)即解答：D=)[[題3]以下算法的時間復(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) 操作平均移動n/2個結(jié)點，刪除操作平均移動 網(wǎng)絡(luò)課堂系列 #defineLISTSIZEtypedef ElemType//當(dāng)前#defineLIST_INIT_SIZE#defineLISTINCREMENTtypedefstruct{ElemType*elem;//初始分配//分配}（（2）間的邏輯關(guān)系，必須附加指針來表示，這也導(dǎo)致線性表的空間利用率降低。但在鏈表中或刪除操作始，只需修改相關(guān)結(jié)點的指針域即可，不typedefstruct data;//數(shù)據(jù)域structLNode*next;//指針域} [[題1]設(shè)線性表有n個元素，以下操作中，（）在順序表上D．輸出與給定值x相等的元 性表中的序[[題2]采用順結(jié)構(gòu)的線性表算法中，當(dāng)n個空已滿時，可申請再增加分配m個空間。若申請失敗，則明系統(tǒng)沒有（）可分配的 A．m個B．m個連續(xù)的 表的順 順序存放線性表的各元素解答移動上，在第i個位置上xai到an2、順序表的刪除運算與運算相同，其時間主要消耗在了移動表中元素上，刪除第i個元素時，其后面的元素ai+1～an都要向上移動一個位置，共移動了n-i個元素。時間復(fù)雜度為Ｏ(n)。 [ ]網(wǎng)絡(luò)課堂系 計算 根據(jù)設(shè)計思想，采用C或C++或JAVA語言表述算法，關(guān)鍵之處給出；分析：此題主要考查線性表的順序結(jié)構(gòu)（這里為數(shù)組）的應(yīng)用。算法的基。這樣，可使算法的時間復(fù)雜度為O(n){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;}}}1、建立單鏈表（1）頭插法2、鏈表中查找第i法3、鏈表 運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]采用法對單鏈表中的元素進(jìn)行排序，其中L鏈表的頭結(jié)點指針，鏈表元素的數(shù)據(jù)類型為整型int分析：此題主要考查線性表的鏈?zhǔn)浇Y(jié)構(gòu)的應(yīng)用，此題空鏈表，然后將待排序鏈表的結(jié)點依次這個空鏈表，所有結(jié)點 完畢后，這個新生成的鏈表就是所的有序鏈voidvoidInsertsort（LinkList{LNode// r=L;q=L-while(q!=NULL&&q->data<=p-} }s->next=① t=p-p->data=② s->data= 分析：采用的方法是在p所指結(jié)點之一個s所指結(jié)點時一個s所指結(jié)點，然將p所指結(jié)點和s所指結(jié)點的數(shù)據(jù)域進(jìn)行交換解答：①p->next②s voidvoidIntersection(LinkListha,LinkListhb,LinkList∥將ha和 同的元素到單鏈表hcLNodeInsertsort(ha);∥參考題1將ha指向的單鏈表由小到大排序Insertsort(hb);∥參考題1將hb指向的單鏈表由小到大排序 ∥申請頭hc-whliewhlie(pa&&if(pa->data<pb- pb=pb->nxtelse{∥pa和pbpc=(LNode*)malloc(sizeof(LNode));∥pb=pb-∥}}結(jié)點*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é)點之后結(jié)點*q的操作。1、棧是運算受限（限制在表的一端）的線性表，允許、刪除的這一端稱為棧頂，—可以使數(shù)據(jù)通過棧后仍然保持次，對于順序結(jié)構(gòu)的棧還需注意（1）進(jìn)[[題1]設(shè)n個元素進(jìn)棧序列是p1，p2，p3，…，pn，其輸值是。A.n- B.n- D.有多種可，p2，p3，…，pn進(jìn)棧，然后依次出棧，即pn- 解答：C1、隊列是運算受限（在表的一端進(jìn)行，而刪除在表的另一端進(jìn)行）的線性表，允許的一端稱為隊尾，把允許刪除的一端稱使隊列的向量空間得到充分的利用。判斷循環(huán)隊列的“空”和 加入兩個元素后，rear和front的值分別為（）。A．1和 B.2和 C.4和 D.5和解答：BLOC(aij)=LOC(a00)+(i×n+j)×d ，每個數(shù)組元素占據(jù)d個地址單元,LOC(aij)=LOC(a00)+(j×n+i22、特殊矩陣的壓（假設(shè)以行序為主序（1）對稱矩陣：將對稱矩陣A壓 到SA[n(n+1)/2]（上）三角中的元后，接著對角線上（下）方的到SA[n(n+1)/2+1]中，aij的下標(biāo)i、j與在SA[k]將對角矩陣A與在SA[k]中的對應(yīng)元素的下標(biāo)k的關(guān)到一維數(shù)組SA[0..u-1]中，aij的下標(biāo)i、當(dāng)0≤i，j≤n-1時例如：將三對角矩陣A與在SA[k]中的對應(yīng)元素的下標(biāo)k的關(guān)系為：當(dāng)0≤i，j≤n-0≤k＜3n-2時，k=2i+j到SA[3n-2]中，aij的下標(biāo)i、[[題 設(shè)矩陣A[1..n][1..n]是一個對稱矩陣，為了節(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.分析：對稱矩陣A的下標(biāo)從1開始，對于任一元素aij（由于共有i(i-1)/2+j-1個元素，k=i(i-1)/2+j-1+1=i(i-1)/2+j。解答：B[[題2]設(shè)二維數(shù)組A[6][10]，每個數(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é)點與滿二叉樹中為i的33、二叉樹 結(jié)（1）順 結(jié)完全二叉樹和滿二叉樹采用順比較合適，樹中結(jié) 靈活、操作方便，對于一般情況的二叉樹，甚至比順序結(jié)構(gòu)還節(jié)省空間。因此，二叉鏈表是最常用的二叉樹方式。typedef emTypestructBiTNode*lchild;*rchild;//BiTree [[題2]設(shè)二叉樹只有度為0和2的結(jié)點，其結(jié)點個數(shù)為15二叉樹的最大深度為 ）。由于結(jié)點個數(shù)為15，因此二叉樹的深度h為8解答：C性質(zhì)性質(zhì)4：具有n個結(jié)點的完全二叉樹的深度k。的順序?qū)Χ鏄渲械乃薪Y(jié)點從1開始順序，則對于任意的序號二二叉樹性質(zhì)的度為1的結(jié)點，N2個度為2的結(jié)點，，Nm個度為m的結(jié)①有n>0個葉結(jié)點的完全二叉樹的高度(結(jié)點層次數(shù))當(dāng)n≠2k,即n不是2的方冪或者n=2k但是一棵滿二叉樹，其 當(dāng)n=2k但是非滿二叉樹，其高度 ②有n個結(jié)點的完全k叉樹的高度 ①，為p=1的結(jié)點無父結(jié)點，否為p結(jié)點的父 ②為p的結(jié)點的第k-1個孩子為p×k，所以，如號為p結(jié)點有孩子，其第i個孩子為p×k+(i 為p的結(jié)點有右兄弟的條件是(p-1)%k0時，其右兄弟 性質(zhì)1：樹中的結(jié)點數(shù)等于所有結(jié)點的度數(shù)+1性質(zhì)2：度為m樹中第i層上至多有mi-1個結(jié)點（i≥1）性質(zhì)3：高度為h的度為m樹至多有(mh-1)/(m-1)個結(jié)點。性質(zhì)4：具有n個結(jié)點的度為m樹的最小高度為logm(n(m-。[[題1]若一棵二叉樹有126個結(jié)點，在第7層（根結(jié)點在第1層）至多有 D.不存在第7。[[題2]若一棵度為7的樹有8個度為1的結(jié)點，有7個度為2的結(jié)共有（）個葉結(jié)點。 分析：由二叉樹性質(zhì)3的推廣，度為7的樹應(yīng)該有解答：D十十一、二叉樹的遍歷及應(yīng)先序遍歷：遞歸算法、非遞歸層次遍 [[題1]任何一棵非空二叉樹中的葉子結(jié)點在先序遍歷、中序遍歷與后序遍歷中的相對位置（）。A．都會發(fā)生改 B．不會發(fā)生改C．有可能會發(fā)生改 D．部分會發(fā)生改或是后序遍歷（LRD），對于葉子結(jié)點而言，被的解答：B[[題2]對于二叉樹的兩個結(jié)點X和Y，應(yīng)該選擇（）兩個序A．先序和后 B．先序和中C．中序和后 D．A、B、C都解答：D反例（給出任何一個正確的反例即可 結(jié)voidvoidlink(BiTreebt,BiTNode*head,BiTNodeif(bt!=NULL){if(bt->lchild==NULL&&bt->rchild==NULL)//葉子結(jié)點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é)點路徑：%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);//遞歸掃描右子樹 }}}十二、十二、這樣 ，也不使用棧（其中后序線索二叉樹中查找后繼仍需要棧）索二叉樹中，下面說法不正確的是（） 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個孩子，然后（）。解答：D 解答：D十十四、二叉排序樹與平衡二ASLn個關(guān)鍵字，構(gòu)造所得的不同形。33、（1） 注意：在二叉排序樹 的結(jié)點均作為葉子結(jié)點①被刪除的結(jié)點*p，且左子樹和右子樹高度之差的絕對值不超過1LL型平衡旋轉(zhuǎn)，A；RR型平衡旋轉(zhuǎn)；A； A．充分不必 B．必要不充C．充分必 D．既不充分也不必值30時發(fā)生不平衡，則應(yīng)進(jìn)行的平衡旋轉(zhuǎn)是 ） D.[[題 在含有n個結(jié)點的二叉排序樹中查找一個關(guān)鍵字，進(jìn)關(guān)鍵字比較次數(shù)最大值是 B.） 解答：D十十五、哈夫曼樹和哈夫曼編33、對哈夫曼樹的55、對哈夫曼樹編深度為h的哈夫曼樹，其葉子結(jié)點的最大編碼長度為h-。 解答：C十十六、圖的基本概1、2、無向3、有向4、無向完全圖：在一個含有n個頂點的無向完，有n(n-1)/2條邊5、有向完全圖：在一個含有n個頂點的有向完，有n(n-1)條邊1111、子圖：對于圖G=（V，E），G’=（V’，E’），若存在是V的子集，E’是E的子集，則稱圖G’是G的一個子圖12、連通圖、連13、強連通圖、強連通14、生成15[[題1]以下關(guān)于圖的敘述中，正確的是（） [[題2]一個有28條邊的非連通無向圖至少有）個頂 解答：C結(jié)之間的鄰接關(guān)系（鄰接矩陣的形式描述）角矩陣的元素即可，又由于主對角線為0，則至少需要n(n-1)/2空間。行（或第列）非零元素（或非元素）的個數(shù)正好是第i個頂點的度TD(i。行（或第列）非零元素（或非元素）的個數(shù)正好是第i個頂點的出度(i（或入度(i)）。用鄰接矩陣方法圖，很容易確定圖中任意兩個頂點之間是否有邊相測，所花費的時間代價很大。這是用鄰接矩陣圖的局限性。稠密圖適合用鄰接矩陣的22、鄰接表是圖的一方法，類似n個頂點、條邊，則它的鄰接表需個頭結(jié)點和2個表結(jié)點。稀疏圖用鄰接表表示比鄰接矩陣節(jié)省多時更是如此。（i和j）i個或第j例a例abcd111^ ^344 4 4 ^13c鏈34^^例例abcde441a121^4^2b3c32344d5e52^3^5^[[題 n個頂點的無向圖的鄰接表中邊表結(jié)點總數(shù)最多有 ） D.n(n-解答：D1、圖的遍歷通常有深度優(yōu)先搜索和廣度優(yōu)先搜索兩種（1）①遞歸算法②非 先搜索遍歷圖的時間復(fù)雜度為O(n+e)。深度優(yōu)先搜索遍點的順序不同。 解答：B[[題2]假設(shè)圖G，設(shè)計一個算法，輸出圖G。由于在搜索過程中，每個頂點只voidvoidPathAll(ALGraph*G,intu,intv,intk,intpath[],intintm,i; ode*p; 路徑長度加 if(u==v&&d==k)for(i=0;i<=d;i++)printf(path[i]);//輸出一條路徑 arc;//p指向頂點u的第一條弧的弧頭結(jié)點while if(visited[m]==0) p->nextarc;}} 3、克魯 （Kruskal）算法的基本思 A.G是G的連通分 B.G是G的無環(huán)子C.G’是G的子 G’是G的極小連通子圖且解答：A1、拓?fù)溆行蛐蛄惺茿OV網(wǎng)G中的頂點所構(gòu)成的有序序列1,…,i,…,n），33、對AOV網(wǎng)進(jìn)行拓?fù)渑判虻姆椒ā?A．深度優(yōu)先遍 B．廣度優(yōu)先遍C．求最短路 D．求關(guān)鍵路理由是：設(shè)整個圖G的度之和為N，則N≥2n，又因為圖中邊數(shù)，因此圖G至少有n條邊因為多于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ā)生時間求AOV網(wǎng)中所有事件的最遲發(fā)生時間求AOV網(wǎng)中所有活動的最早發(fā)生時間求AOV網(wǎng)中所有活動的最遲發(fā)生時間（5）求AOV網(wǎng)中所有活動的事件余量 ；- （6）找出所有 )為0的活動構(gòu)成的關(guān)鍵路徑,ve(源點ve(k)=Max{ve(j)+dut(<j,vl(匯點)=ve(匯點vl(j)=Min{vl(k)–dut(<j,e[i]=l[i]的活動就是關(guān)鍵活動，關(guān)鍵活動所在的路徑就是關(guān)[[題1]下面關(guān)于關(guān)鍵路徑的問題中說法正確的是（）A．僅Ⅰ和IIB．僅Ⅰ和IIIC．僅ⅠD．僅III解答：D二十二、二十二、法的時間復(fù)雜度也是O(n3)[[題1]下列說法不正確的是（）I求從指定源點到其余各頂點的Dijkstra最短路徑算法中弧上權(quán)值可以為負(fù)值 IV求單源路徑的Dijkstra算法不適合用于有回路的A.I、II、III、 B.I、 C.I、III、 D.II、分析：每次以一個頂點為源點，重復(fù)利用Dijkstr算法n次求得每一對不同頂點n3)，因此I正確；而最短路徑算法要求弧、III錯誤；Dijkstr算法可用于有回路的有向網(wǎng)，例如知識點聚焦22的例題1中就是有回路的有向網(wǎng)解答：C二十三、二十三、順序查找算法的時間復(fù)雜度為O(n)。它的缺點是當(dāng)n，平均查找長度較大，效率低；優(yōu)點是表的結(jié)構(gòu)是順。 44、分塊查找分塊查找法要求將列表組織成以下索引順序塊的長度均勻，最后一塊可以不滿。每塊中元素任意排例如例如順序 索索引順序214078定表中每個元素的查找概率相等，則每個索引項的查找概率為1/b，塊將將typedefstructnode{intA[m]；structnode*next;//指向下一結(jié)點的指針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個元素，按分塊查找等分為3塊。若對索引表采用順序查找方法來確定子塊在確定的子塊中也采用順序查找方，分塊查找成功的平均查概率況B.C.D.解答二十四、二十四、B‐樹與B+1、一棵m階的B-樹，或者為空樹，或為滿足下列特性的m⑴樹中每個結(jié)點至多有m⑶除根結(jié)點之外的所有非終端結(jié)點至少有m/2Kii=12…n)，An所指子樹中所有結(jié)點的關(guān)鍵碼均大于Kn，m/222、B-樹的基本（1）查點的路徑上涉及的結(jié)點數(shù)不超過B-關(guān)鍵字而得。但由于B-結(jié)點中的關(guān)鍵字個數(shù)必須大于等于m/21一個關(guān)鍵字不是在樹中添加一個葉子結(jié)點，而是首先在最低層的某個非終端結(jié)點中添加一個關(guān)鍵字，若該結(jié)點的關(guān)鍵字個數(shù)不超過m1（3）在B-完成，否則要產(chǎn)生結(jié)點的”33、一棵m階的B+樹和m階的B-樹的差有n棵子樹的結(jié)點中含有n個關(guān)鍵 [[題1]下面關(guān)于m階B-樹說法正確的是（） IV 一個數(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é)點的隨機檢索和直接從葉子結(jié)點二十五、二十五、 ”現(xiàn)象，即：key1，而f(key1f(key2)H(key)=keyMOD Hi=H +diMOD1≤i<m其中：di1，2，……，m-1，且di=i ②二次探測法 Hi=(H(key)±di)MOD其中：di為增量序列12，-12，22，-22，……，q2，-q2且q≤m/2。 種方法中，散列表每個單元存放的不再是記錄本身，而是相應(yīng)同義44，但找到位置的平均探查次數(shù)，它是表中所有可能散列到的位置上要新元素時為找到空位置的探查次數(shù)的平均[[題1]下列有關(guān)散列查找的敘述正確的是（） D.若散列表的裝填因子α<<1，則可避 的產(chǎn) ，所以選項A正確；散列是指多個不同關(guān)鍵字對應(yīng)相，選項B錯誤；用線性探測法解決的散列表中，散列函數(shù)值相同的關(guān)鍵字不一定總是存放在一片連續(xù)的單元中，選項C錯誤；裝填因子α越小，發(fā)生的概率越小，但仍有可能發(fā)生。解答：A[[題2]散列表的平均查找長度） 解答：A[[題3]采用散列函數(shù)H(k)=3×kMOD13并用線性探測開放地 構(gòu)造散列表（畫示意圖裝填因等概率情況下查找失敗的平均查找長度[[題 已知一組關(guān)鍵字為列函數(shù)的形式為Hke =keyMODp，回答下列問題：分析：本題是對散列表的一種常見考查方式。采用鏈地址，查找成功表示找到了關(guān)鍵字集合中的某記錄的比較次數(shù)，查找不成功表示在散列表中未找到指定關(guān)鍵字的記錄的比較次數(shù)。首首先，回憶一下串匹配(查找)的定義INDEX(S,T,初始條件：ST存在，T1≤pos≤StrLength(S)操作結(jié)果：若主串S中存在和串T值相同的Spos個字符之后第一次出現(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非空，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算法的時間復(fù)雜度可以達(dá)到S[iT[j時，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}/