【正文】 D） snext=front。 【答案】 C 12．判定一個(gè)棧 S（元素個(gè)數(shù)最多為 MAXSIZE）為空和滿的條件分別為（ ） A） Stop!=1 Stop!=MAXSIZE1 B） Stop=1 Stop=MAXSIZE1 C） Stop=1 Stop!=MAXSIZE1 D） Stop!=1 Stop=MAXSIZE1 【答案】 B 填空題 1．棧是 _____________的線性表，其運(yùn)算遵循 _____________的原則。設(shè)棧為順序棧，每個(gè)元素占 4 個(gè)字節(jié)。根據(jù)棧的性質(zhì)，經(jīng)過 PUSH,PUSH,POP 運(yùn)算之后，棧中存在元素 1，輸出數(shù)據(jù)為 2，然后經(jīng)過 PUSH,POP， 3 入棧， 3 出棧，然后經(jīng)過PUSH,PUSH 之后 4， 5 入棧，此時(shí)出棧序列為 2， 3，棧中元素為 1， 4， 5；每個(gè)元素占 4個(gè)字節(jié)，所以棧頂指針的值為 1000H+3*4=100CH（十六進(jìn)制數(shù)） 3．循環(huán)隊(duì)列的引入，目的是為了克服 _____________。 4．隊(duì)列是限制插入只能在表的一端，而刪除在表的另 一端進(jìn)行的線性表，其特點(diǎn)是_____________。 【答案】 s=(LinkList)malloc(sizeof(LNode))。 snext=rnext。 r=s。 【答案】 (M+1)% N； 9．當(dāng) 兩個(gè)棧共享一存儲(chǔ)區(qū)時(shí)，棧利用一維數(shù)組 stack[1..n]表示，兩棧頂指針為 top[1]與 top[2]，則當(dāng)棧 1 空時(shí)， top[1]為 _____________，棧 2 空時(shí)， top[2]為 _____________，棧滿時(shí)為_____________。 為了增加內(nèi)存空間的利用率和減少溢出的可能性，由兩個(gè)棧共享一片連續(xù)的空間時(shí)，應(yīng)將兩棧的 _____________分別設(shè)在內(nèi)存空間的兩端，這樣只有當(dāng) ______________時(shí)才產(chǎn)生溢出。 【答案】 O(1) 第 4 章 串 2．設(shè)有兩個(gè)串 p 和 q，其中 q 是 p 的子串，求 q 在 p 中首次出現(xiàn) 的位置的算法稱為（ ） A）求子串 B）聯(lián)接 C）匹配 D）求串長 【答案】 C 4．串的長度是指（ ） A）串中所含不同字母的個(gè)數(shù) B）串中所含字符的個(gè)數(shù) C）串中所含不同字符的個(gè)數(shù) D）串中所含非空格字符的個(gè)數(shù) 【答案】 B 5 ．若串 S1=ABCDEFG ， S2=9898 ， S3= ， S4=012345 ， 則 執(zhí) 行concat(replace(S1,substr(S1,length(S2),length(S3)),S3),substr(S4,index(S2, 39。),length(S2)))其結(jié)果為（ ） A） ABCG0123 B） ABCD2345 C） ABCG2345 D） ABCG1234 【答案】 D 【解析】函數(shù) concat(x,y)返回 x 和 y 的連接串， substr(s,i,j)返回串 s 的從序號 i 的字符開始的j 個(gè)字符組成的子串， length(s)返 回串 s 的長度。 substr(S1,length(S2),length(S3))=substr(S1,4,3)= DEF。 substr(S4,index(S2, 39。),length(S2))=substr(S4,2,4)= 1234。839。 【答案】 O(m+n) 4．兩個(gè)字符串相等的充分必要條件是 _____________。 5．一個(gè)字符串中 _____________稱為該串的子串 。 第 5 章 多維數(shù)組和廣義表 選擇題 1．?dāng)?shù)組 A 中，每個(gè) 元素的長度為 3 個(gè)字節(jié)，行下標(biāo) I 從 1 到 8，列下標(biāo) J 從 1 到 10，從首地址 SA 開始連續(xù)存放在存儲(chǔ)器內(nèi)，該數(shù)組占用的字節(jié)數(shù)為（ ） A） 80 B） 100 C） 240 D） 270 【答案】 C 2．?dāng)?shù)組 A 中，每個(gè)元素的長度為 3 個(gè)字節(jié)，行下標(biāo) I 從 1 到 8，列下標(biāo) J 從 1 到 10，從首地址 SA 開始連續(xù)存放在存儲(chǔ)器內(nèi)，該數(shù)組按行存放時(shí)，元素 A[8][5]的起始地址為（ ） A） SA＋ 141 B） SA＋ 144 C） SA＋ 222 D） SA＋ 225 【答案】 C 【解析】數(shù)組 A有 8行 10列，按行存放時(shí)， LOC（ A[8][5]） =SA+（（ 81） *10+（ 51）） *3=SA+222。 4．稀疏矩陣一般的壓縮存儲(chǔ)方法有兩種，即（ ） A）二維數(shù)組和三維數(shù)組 B）三元組和散列 C）三 元組和十字鏈表 D）散列和十字鏈表 【答案】 C 5．設(shè)有廣義表 D=（ a,b,D），則其長度為（ ），深度為（ ） A） 1 B） 3 C）∞ D） 5 【答案】 B C 填空題 1．一維數(shù)組的邏輯結(jié)構(gòu)是 _____________，存儲(chǔ)結(jié)構(gòu)是 _____________。 【答案】（ 1）以行為主序 （ 2）以列為主序 3．二維 數(shù)組 A[c1..d1,c2..d2]共含有 _____________個(gè)元素。 【答案】 326 5．有一個(gè) 10 階對稱矩陣 A，采用以行為主序的壓縮存儲(chǔ)方式， A[0][0]的地址為 1，則 A[8][5]的地址是 。 【答案】（ x,y,z） 判斷題 1．?dāng)?shù)組中存儲(chǔ)的數(shù)可是任意類型的任何數(shù)據(jù)（ ） 【答案】 2． N*N 對稱矩陣的經(jīng)過壓縮存儲(chǔ)后占用的存儲(chǔ)單元是原先的 1/2。 12．若一棵二叉樹具有 10 個(gè)度為 2 的結(jié)點(diǎn)， 5 個(gè)度為 1 的結(jié)點(diǎn)，則度為 0 的結(jié)點(diǎn)個(gè)數(shù)是（ ） A） 9 B） 11 C） 15 D）不確定 【答案】 B 13．利用二叉鏈表存儲(chǔ)樹時(shí)，根結(jié)點(diǎn)的右指針是（ ） A）指向最左孩子 B）指向最右孩子 C）空 D）非 空 【答案】 C 14．設(shè)森林 F 中有三棵樹，第一，第二，第三棵樹的結(jié)點(diǎn)個(gè)數(shù)分別為 M1， M2和 M3。 15．若 X 是中序線索二叉樹中一個(gè)有左孩子的結(jié)點(diǎn)，且 X 不為根，則 X 的前驅(qū)為（ ） A） X 的雙親 B） X 的右子 樹中最左的結(jié)點(diǎn) C） X 的左子樹中最右結(jié)點(diǎn) D） X 的左子樹中最右葉結(jié)點(diǎn) 【答案】 C 16． n 個(gè)結(jié)點(diǎn)的線索二叉樹上含有的線索數(shù)為（ ） A） 2n B） nl C） n+l D） n 【答案】 C 【解析】線索二叉樹是利用二叉樹的空鏈域加上線索， n 個(gè)結(jié)點(diǎn)的二叉樹有 n+1 個(gè)空鏈域。 【答案】 plchild==NULL amp。 prchlid==NULL 2． 深度為 H 的完全二叉樹至少有 _____________個(gè)結(jié)點(diǎn)；至多有 _____________個(gè)結(jié)點(diǎn)； H 和結(jié)點(diǎn)總數(shù)N 之間的關(guān)系是 _____________。 【答案】（ 1） 0 （ 2） (n1） /2 （ 3） (n+1） /2 （ 4） ?log2n? +1 4．對于一個(gè)具有 n 個(gè)結(jié)點(diǎn)的二叉樹，當(dāng)它為一棵 _____________時(shí)，具有最小高度，當(dāng)它為一棵_____________時(shí)，具有最大高度。 6．已知二叉樹有 50 個(gè)葉子結(jié)點(diǎn)，則該二叉樹的總結(jié)點(diǎn)數(shù)至少是 _____________。若要使該二叉樹的結(jié)點(diǎn)數(shù)最少，度為 1 的結(jié)點(diǎn)應(yīng)為 0 個(gè)，即總結(jié)點(diǎn)數(shù) N= N0 +N1+ N2 =99。 【答案】 (n+1） /2 8． 每一棵樹都能惟一的轉(zhuǎn)換為它所對應(yīng)的二叉樹。設(shè)上述二叉樹是由某森林轉(zhuǎn)換而成，則其第一棵的先根次序序列是 _____________。 【答案】（ 1） A （ 2） DBE （ 3） HFCG 10．先根次序周游樹林正好等同于按 _____________周游對應(yīng)的二叉樹；后根次序周游樹林正好等同于_____________周游對應(yīng)的二叉樹。 【答案】（ 1） 2k2+1 （ 2） ?log2i?+1 【解析】第 k 層 1 個(gè)結(jié)點(diǎn)，總結(jié)點(diǎn)個(gè)數(shù)是 2k1，其雙親是 2k1/2=2k2。 【答案】 69 【解析】在二叉樹中， N0 = N2+1，所以，有 20 個(gè)葉子結(jié)點(diǎn)的二 叉樹，有 19 個(gè)度為 2 的結(jié)點(diǎn)。 13．有數(shù)據(jù) WG={7， 19， 2， 6， 32， 3， 21， 10}，則所建 Huffman 樹的樹高是 _____________，帶權(quán)路徑長度 WPL 為 _____________。 【答案】（ 1） 80 （ 2） 001（不惟一） 15．具有 N 個(gè)結(jié)點(diǎn)的二叉樹，采用二叉鏈表存儲(chǔ)，共有 _____________個(gè)空鏈域。 16． 8 層完全二叉樹至少有 _____________個(gè)結(jié)點(diǎn)，擁有 100 個(gè)結(jié)點(diǎn)的完全二叉樹的最大層數(shù)為_____________。 【答案】 21 【解析】已知該樹中結(jié)點(diǎn)數(shù)和分支數(shù)的關(guān)系分別如下： N= N0 +N1+ N2+N3+ N4 （ 1） N1= N1+ 2N2+3N3+ 4N4 （ 2） 由（ 2）式求得 N=（ 1+2*2+3*3+4*4） +1=31，再由（ 1）式求得 N0=21。它共有_____________個(gè)葉子結(jié)點(diǎn)和 _____________個(gè)非葉子結(jié)點(diǎn)，其中深度最大的那棵樹的深度是_____________，它共有 _____________個(gè)葉子結(jié)點(diǎn)和 _____________個(gè)非葉子結(jié)點(diǎn)。 10．二叉樹中序線索化后，不存在空指針域（ ） 【答案】 【解析】非空二叉樹中序遍歷第一個(gè)結(jié)點(diǎn)無前驅(qū)，最后一個(gè)結(jié)點(diǎn)無后繼，這兩個(gè)結(jié)點(diǎn)的前驅(qū)線索和后繼線索為空指針。 【答案】樹的孩子兄弟鏈表表示法和二叉樹二叉鏈表表示法，本質(zhì)是一樣的，只是解釋不同，也就是說樹（樹是森林的特例，即森林中只有一棵樹的特殊情況）可用二叉樹惟一表示，并可使用二叉樹的一些算法去解決樹和森林中的問題。 2．若在內(nèi)存中存放一個(gè)完全二叉樹， 在二叉樹上只進(jìn)行下面兩個(gè)操作： （ 1）尋找某個(gè)結(jié)點(diǎn)雙親 ； （ 2）尋找某個(gè)結(jié)點(diǎn)的子女； 請問應(yīng)該用何種結(jié)構(gòu)來存儲(chǔ)該二叉樹？ 【答案】用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ) n 個(gè)結(jié)點(diǎn)的完全二叉樹。 3．求含有 n 個(gè)結(jié)點(diǎn)、采用順序存儲(chǔ)結(jié)構(gòu)的完全二叉樹中的序號最小的葉子結(jié)點(diǎn)的下標(biāo)。 【答案】根據(jù)完全二叉樹的性質(zhì)，最后一個(gè)結(jié)點(diǎn)（編號為 n）的雙親結(jié)點(diǎn)的編號是 ?n/2?， 這是最后一個(gè)分支結(jié)點(diǎn)，在它之后是第一個(gè)終端（葉子）結(jié)點(diǎn)，故序號最小的葉子結(jié)點(diǎn)的下標(biāo)是 ?n/2?+1。 【答案】先序遍歷是“根左右”，中序遍歷是“左根右”，后序遍歷是“左右根”。 5．試找出滿足下列條件的二叉樹： 1）先序序列與后序序列相同； 2）中序序列與后序序列相同； 3）先序序列與中序序列相同； 4）中序序列與層次序列相同； 【答案】先序遍歷二叉樹的順序是“根 — 左子樹 — 右子樹”，中序遍歷“左子樹 — 根 — 右子樹”，后序遍歷順序是：“左子樹 — 右子樹―根”，根據(jù)以上原則，解答如下： 1）若先序序列與后序序列相同，則或?yàn)榭諛?，或?yàn)橹挥懈Y(jié)點(diǎn)的二叉樹。 （ 3）若先序序列與中序序列相同，則或?yàn)榭諛?，或?yàn)槿我唤Y(jié)點(diǎn)至多只有右子樹的二叉樹。 7．一棵非空二叉樹其先序序列和后序序列正好相反，畫出二叉樹的形狀。請畫出該二叉樹，并將其轉(zhuǎn)換為對應(yīng)的森林。若左子樹不空，層次序列中第二個(gè)結(jié)點(diǎn)為左子樹的根；若右子樹為空，則層次序列中第三個(gè)結(jié)點(diǎn)為右子樹的根。層次序列的特點(diǎn)是，從左到右每個(gè)結(jié)點(diǎn)或是當(dāng)前情況下子樹的根或是葉子。 先序序列： ABCDEFGHIJKLMNO 后序序列： CDEBFHIJGAMLONK 【答案】森林的先序序列和后序序列對應(yīng)其轉(zhuǎn)換的二叉樹的先序序列和中序序列，應(yīng)先據(jù)此構(gòu)造二叉樹，再構(gòu)造出森林。 先序序列 ： _ _ C D E _ G H I _ K 中序 序列 ： C B _ _ F A _ J K I G 后序序列 ： _ E F D B _ J I H _ A 【答案】 11．設(shè)有正文 AADBAACACCDACACAAD，字符集為 A， B， C， D，設(shè)計(jì)一套二進(jìn)制編碼，使得上述正文的編碼最短。其哈夫曼編碼如下： A:1， B:000，C:01， D:001 。 第 7 章 圖 選擇題 1．對于一個(gè)具有 n 個(gè)頂點(diǎn)和 e 條邊的有向圖，在用鄰接表表示圖時(shí)，拓?fù)渑判蛩惴〞r(shí)間復(fù)雜度為（ ） A） O(n) B） O(n+e) C） O(n*n) D） O(n*n*n