【正文】 }[low]=[0]。 while(lowhighamp。 while(lowhigh){ while(lowhighamp。[low]=[j]。} }}3．設待排序文件有n ( n0 )個記錄，試編寫算法，不經(jīng)全部排序，將第j (0j≤n)個元素放在適當位置（即在排序后它應在的位置）。 //白色在中間 else if(a[w]==2) //指針b從后往前移動，藍色在最右邊 {temp=a[w]。 a[r]=temp。分析：3種顏色紅白藍分別用0，1，2表示放在一個數(shù)組里，設三個指針兩個在數(shù)組開頭，一個在數(shù)組末尾，分別用來指向排好序以后的紅白藍條塊最后一塊的位置。j。針對表中的每一個記錄，掃描待排序的表一趟，統(tǒng)計表中有多少個記錄的關鍵字比該記錄的關鍵字小，假設針對某一記錄，統(tǒng)計出的計數(shù)值為c，那么這個記錄在新的有序表中的合適存放位置為c。A. 選擇 B. 冒泡 C. 歸并 D. 堆5. 在下面的排序方法中，輔助空間為O（n）的是( D ) 。四、練習題（一）選擇題 ( D )排序法。首先與10比較，交換位置，再與25比較，不交換位置，共比較2次。 ，先處理較長的分區(qū)可以減少遞歸次數(shù)，先處理較短的分區(qū)可以減少遞歸次數(shù)分析：答案是D，此題考查快速排序的思想。,5,12,8,28,20,15,22,19,5,12,19,20,15,22,8,28,8,12,5,20,15,22,28,19,12,5,8,28,20,15,22,19分析：答案是A，此題考查堆得構造與調(diào)整。（1）散列地址0123456789101112關鍵字13225314167465130比較次數(shù)111212111（2）裝填因子=9/13=（3）ASLsucc =11/9ASLunsucc =29/132．已知長度為11的表（xal,wan,wil,zol,yo,xul,yum,wen，wim,zi,yon），按表中元素順序依次插入一棵初始為空的平衡二叉排序樹，畫出插入完成后的平衡二叉排序樹，并求其在等概率的情況下查找成功的平均查找長度。（1）元素59存放在散列表中的地址是（ D ）。 (1): (2): 。綜合題出哈希表的可能性比較多，也有可能出算法題，這樣會和第2章線性表和第6章二叉樹結合來考，總之是和前面的內(nèi)容有聯(lián)系的，一定要掌握各種查找方法的思想并能進行分析。問題：（1）請畫出所構造的散列表；（2）分別計算等概率情況下，查找成功和查找不成功的平均查找長度。 在答案A中檔找到91后向24查找，說明后面的數(shù)都比91小，而后面序列中出現(xiàn)了94，顯然不對。 ,20,91,34,88,35,89,77,29,36,38 分析：答案是A，此題考查有序表的折半查找的思想。4.（10年）已知一個長度為16的順序表L，其元素按關鍵字有序排列，若采用折半查找法查找一個不存在的元素，則比較次數(shù)最多是（ ）。2．（09年）下列敘述中，不符合m階B樹定義要求的是（ ）。解答：設vi表示第i年購進一臺新設備，（vi，vj）表示設備由第i年初使用到第j年初，權值表示使用費用，得到下圖：在圖中求由v1到v6的最短路徑得到兩條：v1v3v6和v1v4v6，因此設備的更新計劃為在第1年和第3年年初更新設備或者是在第1年和第4年年初更新設備，總費用是53。4．某企業(yè)使用一臺設備，在每年年初，企業(yè)領導部門就要決定是購置新的，還是繼續(xù)使用舊的設備。3．已知有6個村子，相互間道路的距離如圖所示。 A．深度優(yōu)先遍歷 B. 拓撲排序 C. 求最短路徑 D. 求關鍵路徑（ C ）。四、練習題（一）選擇題=(V,E),其中：V={a,b,c,d,e,f},E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)}，由頂點a開始對該圖進行深度優(yōu)先遍歷，得到的頂點序列正確的是（ D ）。三、考查重點1．圖的基本概念及特點；2. 圖的存儲結構（鄰接矩陣和鄰接表）；3．圖的深度優(yōu)先和廣度優(yōu)先遍歷；4．圖的應用（最小生成樹的構造過程、拓撲序列的生成、最短路徑和關鍵路徑的求解過程）。解答：此題考查圖的鄰接矩陣的存儲以及 關鍵路徑的求解，同時考查了特殊矩陣的壓縮存儲，主要是考查的圖的基本知識。2．（11年）已知有6個頂點（頂點編號為05）的有向帶權圖G，其鄰接矩陣A為上三角矩陣，按行優(yōu)先為主序保存在如下的一維數(shù)組中。請問上述方法能否求得最短路徑？若該方法可行，請證明之；否則，請舉例說明。 、III分析：答案是C，此題考查圖的基本概念。4．（11年）下列關于圖的敘述中，正確的是（ ）。 分析：答案是A，此題考查無向連通圖的特性。5．給定一組數(shù)列（15,8,10,21,6,19,3）分別代表字符A,B,C,D,E,F,G出現(xiàn)的頻度，試敘述建立哈夫曼樹的算法思想，畫出哈夫曼樹，給出各字符的編碼值，并說明這種編碼的優(yōu)點。因為前序序列的第一個元素是根結點，該元素將二叉樹中序序列分成兩部分，左邊（設l個元素）表示左子樹，若左邊無元素，則說明左子樹為空；右邊（設r個元素）是右子樹，若為空，則右子樹為空。若不能，請給出反例。}}分析：二叉樹遍歷算法的應用中關鍵的一個環(huán)節(jié)是分析要實現(xiàn)相關功能應該選擇二叉樹的哪一種遍歷方式有利于實現(xiàn)，如以上兩個例子中分別選用二叉樹的層次遍歷和后序遍歷實現(xiàn)具體操作，主要對遍歷算法稍加處理就可以實現(xiàn)了。 p=prchild。}while(tag[top]==1amp。for(i=1。 stack[top]=p。 p=T。 } return 1。 flag=0。amp。 }}判斷兩棵樹是否相似的遞歸算法。 } if(Trchild) Bitree_Revolute(Trchild)。void Bitree_Revolute(Bitree T){ if(T!=NULL) TlchildTrchild。amp。 EnQueue(Q,T)。 tag[top]=1。 p=stack[to} p=plchild。 while(top0||p!=NULL) Push(S,T)。A．先序 B．中序 C．后序 D．從根開始按層次遍歷，則該二叉樹一定是（ C ）的二叉樹。雖然近兩年沒有出綜合題，同學們也不要忽視，綜合題一般會現(xiàn)在二叉樹的遍歷及其應用、樹與二叉樹的轉換和哈夫曼樹的構造及哈夫曼編碼。考慮一種特殊的情況，設題意中的樹是如下圖所示的結構，則對應的二叉樹中僅有前115個葉結點有右孩子。9．（11年）已知一棵有2011個結點的樹，其葉結點個數(shù)116，該樹對應的二叉樹中無右孩子的結點個數(shù)是（ ）。 ,2,4,1 分析：答案是C，考查二叉樹的性質(zhì)，葉結點個數(shù)為你n則度為2的結點個數(shù)為n1，總結點個數(shù)為偶數(shù)，則度為1的結點個數(shù)為1，因此2n=768。 分析：答案是D，此題考查二叉樹的線索化。3.（09年）將森林轉換為對應的二叉樹，若在二叉樹中，結點u是結點v的父結點的父結點，則在原來的森林中，u和v可能具有的關系是（ ）。若遍歷后的結點序列為3,7,5,6,1,2,4，則其遍歷方式是（ ）。（1）存放A至少需要（ E ）個字節(jié)；（2）A的第8列和第5行共占（ A ）個字節(jié)；（3）若A按行存放，元素A[8，5]的起始地址與A按列存放時的元素（ B ）的起始地址一致。+141 +180 +222 +2253. 假設以行序為主序存儲二維數(shù)組A=array[1..100，1..100]，設每個數(shù)據(jù)元素占2個存儲單元，基地址為10，則LOC[5，5]=（ B ）。第5章 數(shù)組和廣義表一、考研知識點特殊矩陣的壓縮存儲二、考研真題近兩年此知識點沒有出題。 +1 2. 若一個棧的輸入序列為1,2,3,…,n，輸出序列的第一個元素是i，則第j個輸出元素是（ D ）。分析：此章內(nèi)容是線性表的深化，如果線性表理解的好，這一章就比較容易。 ）。 分析：答案是C，此題考查棧的入棧和出棧操作和隊列的入隊和出隊操作。該緩沖區(qū)的邏輯結構應該是（ ）。amp。if（klen）{printf（“給的%d太大\n”,len）；exit（0）；}pnext=q；∥A鏈表刪除了len個元素。{k++；p=pnext；}if（p==null）{printf（“給的%d太大\n”,i）；exit（0）；} ∥i太大，退出算法q=pnext；∥q為工作指針，初始指向A鏈表第一個被刪結點。if（i1 || len1 || j1）{printf（“參數(shù)錯誤\n”）；exit（0）；}∥參數(shù)錯，退出算法。再查B鏈表的第j個元素，將A鏈表插入之?！捂湵聿恢行膶ΨQ}∥算法結束。 p=pnext?！稳鬾是奇數(shù)，后移過中心結點。{ s[i]=pdata。∥p是鏈表的工作指針，指向待處理的當前元素。int dc（Linklist h,int n）{∥ h是帶頭結點的n個元素單鏈表，鏈表中結點的數(shù)據(jù)域是字符。分析：判斷鏈表中數(shù)據(jù)是否中心對稱，通常使用棧。 }分析：此算法的高效在于在循環(huán)過程中利用最小值結點的前驅指針進行比較，比較結束后直接保留了最小值結點的前驅，方便進行刪除操作。 q=pnext。void delete ( linklist L){p=Lnext。} else //偶數(shù)鏈鏈接 {snext=qnext。 qnext=NULL。 分析：利用原鏈表空間，在原鏈表的分解過程中新建鏈表。 pb=r。 pa=r。 pb=r。 pa=r。amp。 pb=Bnext。} =m+n。 j。 k。 j=n。分析：從后往前插入，避免移動元素void union (Sqlist la, Sqlist lb){m=。 q=r。 q=pnext。ij。A. O(0) B. O(1) C. O(n) D. O(n2) 7. 對于順序存儲的線性表，訪問結點和增加、刪除結點的時間復雜度為（ C ）。3．線性表是具有n個（ C ）的有限序列（n0）。四、練習題（一）選擇題1．下述哪一條是順序存儲結構的優(yōu)點？（ A ）A．存儲密度大 B．插入運算方便 C．刪除運算方便 D．可方便地用于各種邏輯結構的存儲表示2．下面關于線性表的敘述中，錯誤的是哪一個？（ B ）A．線性表采用順序存儲，必須占用一片連續(xù)的存儲單元。單鏈表中設置頭指針、循環(huán)鏈表中設置尾指針而不設置頭指針的各自好處；4．能分析所寫算法的時間和空間復雜度。s2=m2。d2=m2。 if(A[m1]==B[m2]) return A[m1]。（1）算法的基本設計思想如下：分別求出序列A 和B的中位數(shù)，設為a和b，求序列A和B的中位數(shù)過程如下：1）若a=b，則a或b即為所求中位數(shù)，算法結束；2）若ab，則舍棄序列A中較小的一半，同時舍棄序列B中較大的一半，要求舍棄的長度相等；3）若ab，則舍棄序列A中較大的一半，同時舍棄序列B中較小的一半，要求舍棄的長度相等；在保留的兩個升序序列中，重復過程1）3），直到兩個序列中只含一個元素時為止，較小者即為所求的中位數(shù)。要求：（1）給出算法的基本設計思想。時間復雜度為O(n)，空間復雜度為O(p)。 reverse(R,p,n1)。i++) { temp=R[low+i]。注：re