【文章內(nèi)容簡介】 序存放時(shí)，元素A[5,8]的存儲首地址是（ B ）A. BA+141 B. BA+180 C. BA+222 D. BA+2257. 遞歸過程或函數(shù)調(diào)用時(shí)，處理參數(shù)及返回地址，要用一種稱為（ C ）的數(shù)據(jù)結(jié)構(gòu)。A．隊(duì)列 B．多維數(shù)組 C．棧 D. 線性表 8. 對于單鏈表形式的隊(duì)列，隊(duì)空的條件是（ A ）A．F＝R＝nil　　　 B．F＝R　　　　C．F≠nil且R＝nil　 　 D．R－F＝19. 若循環(huán)隊(duì)列以數(shù)組Q[0..m1]作為其存儲結(jié)構(gòu)，變量rear表示循環(huán)隊(duì)列中的隊(duì)尾元素的實(shí)際位置，其移動(dòng)按 rear=(rear+1) Mod m 進(jìn)行，變量length表示當(dāng)前循環(huán)隊(duì)列中的元素個(gè)數(shù)，則循環(huán)隊(duì)列的隊(duì)首元素的實(shí)際位置是（ C ）A．rearlengthB．(rearlength+m) Mod mC．(1+rear+mlength) Mod mD．Mlength（二）應(yīng)用題（10分）假設(shè)一個(gè)準(zhǔn)對角矩陣按以下方式存儲于一維數(shù)組B[4m]中：01234k4m－24m－1............寫出由一對下標(biāo)（i，j）表示的k的轉(zhuǎn)換公式。答：i為奇數(shù)時(shí) k=i+j2i為偶數(shù)時(shí) k=i+j1合并后可寫成 k=i+j(i%2)1 或 k=2(i/2)+j1特殊矩陣和稀疏矩陣哪一種壓縮存儲后失去隨機(jī)存取的功能？為什么？答：特殊矩陣指值相同的元素或零元素在矩陣中的分布有一定規(guī)律，因此可以對非零元素分配單元（對值相同元素只分配一個(gè)單元），將非零元素存儲在向量中，元素的下標(biāo)i和j和該元素在向量中的下標(biāo)有一定規(guī)律，可以用簡單公式表示，仍具有隨機(jī)存取功能。而稀疏矩陣是指非零元素和矩陣容量相比很?。╰m*n），且分布沒有規(guī)律。用十字鏈表作存儲結(jié)構(gòu)自然失去了隨機(jī)存取的功能。即使用三元組表的順序存儲結(jié)構(gòu)，存取下標(biāo)為i和j的元素時(shí)，要掃描三元組表，下標(biāo)不同的元素，存取時(shí)間也不同，最好情況下存取時(shí)間為O(1)，最差情況下是O(n)，因此也失去了隨機(jī)存取的功能。有人說，采用循環(huán)鏈表作為存儲結(jié)構(gòu)的隊(duì)列就是循環(huán)隊(duì)列，你認(rèn)為這種說法對嗎？說明你的理由。答：這種說法是錯(cuò)誤的。隊(duì)列（包括循環(huán)隊(duì)列）是一個(gè)邏輯概念，而鏈表是一個(gè)存儲概念，一個(gè)隊(duì)列是否是循環(huán)隊(duì)列。不取決于它將采用何種存儲結(jié)構(gòu)。根據(jù)實(shí)際的需要，循環(huán)隊(duì)列可以采用順序存儲結(jié)構(gòu)，也可以采用鏈?zhǔn)酱鎯Y(jié)構(gòu)，包括采用循環(huán)鏈表作為存儲結(jié)構(gòu)。指出下列程序段的功能是什么？ (1) void demo1(seqstack *s){ int I。arr[64]。n=0。 while (!stackempty(s)) arr[n++]=pop(s)。 for(I=0。n。I++) push(s,arr[I])。 } (2) void demo2(seqstack *s,int m){ seqstack t。 int i。 initstack(t)。while(! Stackempty(s)) if(I=pop(s)!=m) push(t,I)。while(! Stackempty(t)) { i=pop(t)。 push(s,I)。}}（三）算法設(shè)計(jì)題1． 試?yán)醚h(huán)隊(duì)列編寫求k階斐波那契序列中前n+1項(xiàng)（）的算法，要求滿足且，其中max為某個(gè)約定的常數(shù)。循環(huán)隊(duì)列的容量為k，因此，在算法執(zhí)行結(jié)束時(shí)，留在循環(huán)隊(duì)列中的元素應(yīng)是所求k階斐波那契序列中的最后k項(xiàng)。答：void GetFib(int k,int n){ InitQueue(Q)。 for(i=0。kk1。i++) [i]=0。[k1]=1。 for(i=0。ik。i++) printf(“%d”,[i])。 for(i=k。i=n。i++) { m=i%k。 sum=0。 for(j=0。jk。j++) sum+=[(m+j)%k]。 [m]=sum。 printf(“%d”,sum)。 }}2. 已知num為無符號十進(jìn)制整數(shù)，請寫一非遞歸算法，該算法輸出num對應(yīng)的r進(jìn)制的各位數(shù)字。要求算法中用到的棧采用線性鏈表存儲結(jié)構(gòu)（1r10）。 解：typedef struct node{int data。struct node *next。}link。void trans(int num,int r){ link *head=NULL,*s。 int n。 while (num0){ n=num%r。 s=(link *)malloc(sizeof(link))。 sdata=n。 snext=head。head=s。 num=num/r。} printf(“輸出r進(jìn)制的各位數(shù)字：”)； s=head。 while (s!=NULL){ printf(“%d”,sdata)。 s=snext。 }}三、樹與二叉樹大綱要求：（一） 樹的概念 （二） 二叉樹 1. 二叉樹的定義及其主要特征 2. 二叉樹的順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu) 3. 二叉樹的遍歷 4. 線索二叉樹的基本概念和構(gòu)造 5. 二叉排序樹 6. 平衡二叉樹 （三） 樹、森林 1. 樹的存儲結(jié)構(gòu) 2. 森林與二叉樹的轉(zhuǎn)換 3. 樹和森林的遍歷 （四） 樹的應(yīng)用 1. 等價(jià)類問題 2. 哈夫曼（Huffman）樹和哈夫曼編碼 知識點(diǎn)：1. 二叉樹的概念、性質(zhì)（1）掌握樹和二叉樹的定義。（2）理解二叉樹與普通雙分支樹的區(qū)別。二叉樹是一種特殊的樹，這種特殊不僅僅在于其分支最多為2以及其它特征，一個(gè)最重要的特殊之處是在于：二叉樹是有序的。即二叉樹的左右孩子是不可交換的，如果交換了就成了另外一棵二叉樹，這樣交換之后的二叉樹與原二叉樹是不相同的兩棵二叉樹。但是，對于普通的雙分支樹而言，不具有這種性質(zhì)。（3）滿二叉樹和完全二叉樹的概念。（4）重點(diǎn)掌握二叉樹的五個(gè)性質(zhì)及證明方法，并把這種方法推廣到K叉樹。普通二叉樹的五個(gè)性質(zhì)：第i層的最多結(jié)點(diǎn)數(shù)，深度為k的二叉樹的最多結(jié)點(diǎn)數(shù)，n0=n2+1的性質(zhì)，n個(gè)結(jié)點(diǎn)的完全二叉樹的深度，順序存儲二叉樹時(shí)孩子結(jié)點(diǎn)與父結(jié)點(diǎn)之間的換算關(guān)系（序號i結(jié)點(diǎn)的左孩子為：2*i，右孩子為：2*i+1）。2. 掌握二叉樹的順序存儲結(jié)構(gòu)和二叉鏈表、三叉鏈表存儲結(jié)構(gòu)的各自優(yōu)缺點(diǎn)及適用場合，以及二叉樹的順序存儲結(jié)構(gòu)和二叉鏈表存儲結(jié)構(gòu)的相互轉(zhuǎn)換的算法。3. 熟練掌握二叉樹的先序，中序和后序遍歷算法以及按層次遍歷二叉樹的先序、中序和后序三種遍歷算法，劃分的依據(jù)是視其每個(gè)算法中對根結(jié)點(diǎn)數(shù)據(jù)的訪問順序而定。不僅要熟練掌握這三種遍歷的遞歸算法，理解其執(zhí)行的實(shí)際步驟，并且應(yīng)該熟練掌握三種遍歷的非遞歸算法?！癜磳哟伪闅v二叉樹void LayerOrder(Bitree T)//層序遍歷二叉樹{InitQueue(Q)。 //建立工作隊(duì)列EnQueue(Q,T)。while(!QueueEmpty(Q)){DeQueue(Q,p)。visit(p)。if(plchild) EnQueue(Q,plchild)。if(prchild) EnQueue(Q,prchild)。}}//LayerOrder 4. 遍歷是基礎(chǔ)，重點(diǎn)掌握在三種基本遍歷算法的基礎(chǔ)上實(shí)現(xiàn)二叉樹的其它算法如求二叉樹葉子結(jié)點(diǎn)總數(shù)，求二叉樹結(jié)點(diǎn)總數(shù)，求度為1或度為2的結(jié)點(diǎn)總數(shù)，復(fù)制二叉樹，建立二叉樹，交換左右子樹，查找值為n的某個(gè)指定結(jié)點(diǎn)，刪除值為n的某個(gè)指定結(jié)點(diǎn)等等。5. 線索二叉樹的引出，是為避免如二叉樹遍歷時(shí)的遞歸求解。遞歸雖然形式上比較好理解，但是消耗了大量的內(nèi)存資源，如果遞歸層次一多，勢必帶來資源耗盡的危險(xiǎn)。二叉樹線索化的實(shí)質(zhì)是建立結(jié)點(diǎn)在相應(yīng)序列中與其前驅(qū)和后繼之間的直接聯(lián)系。對于線索二叉樹，應(yīng)該掌握：線索化的實(shí)質(zhì)，三種線索化的算法，線索化后二叉樹的遍歷算法，基本線索二叉樹的其它算法問題（如：查找某一類線索二叉樹中指定結(jié)點(diǎn)的前驅(qū)或后繼結(jié)點(diǎn)）。6. 二叉排序樹的中序遍歷結(jié)果是一個(gè)遞增的有序序列。二叉排序樹的形態(tài)取決于元素的輸入順序，二叉排序樹在最差情況下形成單支樹。熟練掌握其建立、查找、插入和刪除算法，以及判斷某棵二叉樹是否二叉排序樹這一問題的遞歸與非遞歸算法。7. 平衡二叉樹是二叉排序樹的優(yōu)化，平衡二叉樹對左右子樹的深度有了限定：深度之差的絕對值不得大于1。掌握平衡二叉樹的四種調(diào)整算法。8. 樹與森林的遍歷，只有兩種遍歷算法：先根與后根（對于森林而言稱作：先序與中序遍歷）。二者的先根與后根遍歷與二叉樹中的遍歷算法是有對應(yīng)關(guān)系的：先根遍歷對應(yīng)二叉樹的先序遍歷，而后根遍歷對應(yīng)二叉樹的中序遍歷。二叉樹使用二叉鏈表分別存放它的左右孩子，樹利用二叉鏈表存儲孩子及兄弟（稱孩子兄弟鏈表），而森林也是利用二叉鏈表存儲孩子及兄弟。掌握樹、森林和二叉樹間的相互轉(zhuǎn)換。9. 簡單掌握等價(jià)類的生成算法。10. 哈夫曼樹為了解決特定問題引出的特殊二叉樹結(jié)構(gòu)，它的前提是給二叉樹的每條邊賦予了權(quán)值，這樣形成的二叉樹按權(quán)相加之和是最小的，一般來說，哈夫曼樹的形態(tài)不是唯一的。理解哈夫曼編碼的基本原理，掌握基于哈夫曼樹生成哈夫曼編碼的方法。練習(xí)題：（一）選擇題：一棵二叉樹的前序遍歷結(jié)果為ABCDEF，中序遍歷結(jié)果為CBAEDF，則后序遍歷結(jié)果為（ A ）A. CBEFDA B. FEDCBA C. CBEDFA D. 不確定某二叉樹的后序遍歷序列為dabec，中序遍歷序列為debac，則前序遍歷序列為（D）。A．a(chǎn)cbed B．decab C．deabc D．cedba具有10個(gè)葉子結(jié)點(diǎn)的二叉樹中有（ B）個(gè)度為2的結(jié)點(diǎn)。A. 8 B. 9 C. 10 D. 11樹中所有結(jié)點(diǎn)的度等于所有結(jié)點(diǎn)數(shù)加（ C ）。A．0 B．1 C．－1 D．2設(shè)n，m為一棵二叉樹的兩個(gè)結(jié)點(diǎn)，在中序遍歷時(shí)，n在m前的條件是（ C ）A. n在m的右方 B. n是m的祖先C. n在m的左方 D. n是m的子孫利用逐點(diǎn)插入建立序列（50，72，43，85，75，20，35，45，65，30）對應(yīng)的二叉排序樹以后，要查找元素30要進(jìn)行（ B ）次元素間的比較。A．4 B. 5C．6 D. 7在平衡二叉樹中，（ C ）。A．任意結(jié)點(diǎn)的左、右子樹結(jié)點(diǎn)數(shù)目相同B．任意結(jié)點(diǎn)的左、右子樹高度相同C．任意結(jié)點(diǎn)的左右子樹高度之差的絕對值不大于1D．不存在度為1的結(jié)點(diǎn)由元素序列（27，16，75，38，51）構(gòu)造平衡二叉樹，則首次出現(xiàn)的最小不平衡子樹的根（即離插入結(jié)點(diǎn)最近且平衡因子的絕對值為2的結(jié)點(diǎn)）為（ D ）A．27 B．38C．51 D. 75在二叉樹的順序存儲中，每個(gè)結(jié)點(diǎn)的存儲位置與其父結(jié)點(diǎn)、左右子樹結(jié)點(diǎn)的位置都存在一個(gè)簡單的映射關(guān)系，因此可與三叉鏈表對應(yīng)。若某二叉樹共有n個(gè)結(jié)點(diǎn)，采用三叉鏈表存儲時(shí)，每個(gè)結(jié)點(diǎn)的數(shù)據(jù)域需要d個(gè)字節(jié)，每個(gè)指針域占用4個(gè)字節(jié)，若采用順序存儲，則最后一個(gè)結(jié)點(diǎn)下標(biāo)為k（起始下標(biāo)為1），那么（ A ）時(shí)采用順序存儲更節(jié)省空間。A．d12n/(kn) B. d12n/(kn)C. d12n/(k+n) D. d12n/(k+n)在常用的描述二叉排序樹的存儲結(jié)構(gòu)中，關(guān)鍵字值最大的結(jié)點(diǎn)（ B ）A．左指針一定為空 B. 右指針一定為空C．左右指針均為空 D. 左右指針均不為空（二）應(yīng)用題一棵滿k叉樹，按層次遍歷（從1開始對全部結(jié)點(diǎn)進(jìn)行編號）存儲在一維數(shù)組中，試計(jì)算編號為u的結(jié)點(diǎn)的第i個(gè)孩子（若存在）的下標(biāo)以及編號為v的結(jié)點(diǎn)的雙親結(jié)點(diǎn)（若存在）的下標(biāo)。答：結(jié)點(diǎn)下標(biāo)為u的結(jié)點(diǎn)的第i個(gè)孩子的下標(biāo)：結(jié)點(diǎn)下標(biāo)為v的結(jié)點(diǎn)的父母結(jié)點(diǎn)的下標(biāo)：試求有n個(gè)葉結(jié)點(diǎn)的非滿的完全二叉樹的高度.完全二叉樹中葉子結(jié)點(diǎn)數(shù)為n，則根據(jù)完全二叉樹的性質(zhì)，度為2的結(jié)點(diǎn)數(shù)是n1，而完全二叉樹中，度為1的結(jié)點(diǎn)數(shù)至多為1，所以具有n個(gè)葉子結(jié)點(diǎn)的完全二叉樹結(jié)點(diǎn)數(shù)是n+(n1)+1=2n或2n1（有或無度為1的結(jié)點(diǎn)）。由于具有2n(或2n1)個(gè)結(jié)點(diǎn)的完全二叉樹的深度是235。log2(2n