【正文】 s；f=s； *B．rnext=s；r=s； C．snext=r；r=s； D．snext=f；f=s；17．一個(gè)棧的入棧序列是a，b，c，d，e，則棧的不可能的輸出序列是( )。 A．e，d，c，b，a B．d，e，c，b，a *C．d，c，e，a，b D．a(chǎn)，b，c，d，e18．一個(gè)隊(duì)列的入隊(duì)序列是1，2，3，4，則隊(duì)列可能的輸出序列是( )。 A．4，3，2，1 *B．1，2，3，4 C．1，4，3，2 D．3，2，4，119．設(shè)計(jì)一個(gè)判別表達(dá)式中左，右括號(hào)是否配對出現(xiàn)的算法，采用( )數(shù)據(jù)結(jié)構(gòu)最佳。 A．線性表的順序存儲(chǔ)結(jié)構(gòu) *B．棧 C．隊(duì)列 D．線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)二、判斷題√1．在順序棧棧滿情況下，不能再入棧，否則會(huì)產(chǎn)生“上溢”。╳2．與順序棧相比，鏈棧的一個(gè)優(yōu)點(diǎn)是插入和刪除操作更加方便。╳3．若一個(gè)棧的輸入序列為1，2，3，…，n，其輸出序列的第一個(gè)元素為n，則其輸出序列的每個(gè)元素ai一定滿足ai=i+1(i=1，2，…，n)?！?．在鏈隊(duì)中，即使不設(shè)置尾指針也能進(jìn)行入隊(duì)操作?！?．在對鏈隊(duì)(帶頭指針)做出隊(duì)操作時(shí)，不會(huì)改變front指針的值。╳6．循環(huán)隊(duì)列中元素個(gè)數(shù)為rearfront。╳7．一個(gè)棧的輸入序列是1,2,3,4，則在棧的輸出序列中可以得到4,3,1,2．√8．一個(gè)棧的輸入序列是1,2,3,4，則在棧的輸出序列中可以得到1,2,3,4。╳9．若以鏈表作為棧的存儲(chǔ)結(jié)構(gòu)，則入棧需要判斷棧是否滿．√10．若以鏈表作為棧的存儲(chǔ)結(jié)構(gòu)，則出棧需要判斷棧是否空。三、填空題1．向一個(gè)棧頂指針為Top的鏈棧中插入一個(gè)s所指的結(jié)點(diǎn)時(shí)，其進(jìn)行的操作是__ snext=Top；Top =s；__。2．從棧頂指針為Top的鏈棧中刪除一個(gè)結(jié)點(diǎn)，并將結(jié)點(diǎn)保存在x中，進(jìn)行的操作是_ x=Topdata；Top=Topnext；__。3．在具有n個(gè)單元的循環(huán)隊(duì)列中，隊(duì)滿時(shí)共有___n1_個(gè)元素。4．假設(shè)以S和X分別表示入棧和出棧操作，則對輸入序列a，b，c，d，e進(jìn)行一系列棧操作SSXSXSSXXX之后，得到的輸出序列為__ b，c，e，d，a ___。5．設(shè)有數(shù)組A[m]作為循環(huán)隊(duì)列的存儲(chǔ)空間，front為隊(duì)頭指針，rear為隊(duì)尾指針，則元素x執(zhí)行入隊(duì)操作的語句是_rear=（rear +1）％（m+1）； A[rear]=x。__。6．在一個(gè)鏈隊(duì)中，如果f、r分別為隊(duì)頭、隊(duì)尾指針，則插入s所指結(jié)點(diǎn)的操作是_rnext=s。 r=s。___。7．棧的邏輯特點(diǎn)是__后進(jìn)先出____，隊(duì)列的邏輯特點(diǎn)是_先進(jìn)先出__，二者的共同特點(diǎn)是_操作受限__。8．___棧___可以作為實(shí)現(xiàn)遞歸函數(shù)調(diào)用的一種數(shù)據(jù)結(jié)構(gòu)。9．在隊(duì)列中，新插入的結(jié)點(diǎn)只能添加到__隊(duì)尾__。10．鏈隊(duì)在一定范圍內(nèi)不會(huì)出現(xiàn)__隊(duì)滿___的情況。當(dāng)lq．front==lq．rear時(shí)，隊(duì)中無元素，此時(shí)___隊(duì)空__。11．設(shè)一個(gè)鏈棧的棧頂指針為ls，棧中結(jié)點(diǎn)的格式為data:next，?？盏臈l件是_ ls = NULL__；如果棧不為空，則出棧操作為p=ls。 ___ ls = ls next __；free(p)。12．對帶有頭結(jié)點(diǎn)的鏈隊(duì)lq，判定隊(duì)列中只有一個(gè)數(shù)據(jù)元素的條件是__lqfrontnext= lqrear___。 13．設(shè)有一個(gè)空棧，現(xiàn)在輸入序列為1，2，3，4，5，經(jīng)過push，push，pop，push，pop，push后，棧頂指針?biāo)冈厥莀_4__。14．設(shè)用一維數(shù)組A[n]來表示一個(gè)棧，令A(yù)[0]為棧底。用整型變量t來指示當(dāng)前棧頂?shù)奈恢?，A[t]為棧頂元素。往棧中壓入一個(gè)新元素時(shí)，變量t的值__加1___，從棧中彈出一個(gè)元素時(shí)，變量t的值___減1___。設(shè)空棧時(shí)，輸入序列a，b，c經(jīng)過push，pop，push，push，pop操作后，從棧中彈出的元素是___c__。四、應(yīng)用題2．設(shè)有字符串為3*ya/y^2，試?yán)脳懗鰧⑵滢D(zhuǎn)換為3y*ay2^/的操作過程。假定用X代表掃描該字符串過程中順序取一個(gè)字符入棧的操作，用S代表從棧中取出一個(gè)字符加入到新字符串尾的出棧操作。例如，ABC變?yōu)锽CA的操作步驟為XXSXSS。答：XSXXXSSSXXSXXSXXSSSS3．設(shè)有一個(gè)輸入序列a，b，c，d，元素經(jīng)過一個(gè)棧到達(dá)輸出序列，而且元素一旦離開輸入序列就不能再回到輸入序列，試問經(jīng)過這個(gè)棧后可以得到多少種輸出序列?答：可以得到14種輸出序列：abcd,abdc,acbd,acdb,adcb,bacd,bcad,bcda,bdca,cbad,cbda,cdba,dcba,badc.4．按照運(yùn)算符優(yōu)先法，畫出對下面算術(shù)表達(dá)式求值時(shí)，操作數(shù)棧和運(yùn)算符棧的變化過程：92*4+(8+1)/3。答：序號(hào)運(yùn)算符棧操作數(shù)棧輸入字符1929392492*5*9246*924+798819+1(10+(1811+(18+12+(+18113+(+181)14+19/15+/19316+/19317+131845．鏈棧中為何不設(shè)置頭結(jié)點(diǎn)?答：因?yàn)殒湕Ｖ辉阪湵眍^插入和刪除結(jié)點(diǎn)，不可能在鏈表中間插入或刪除結(jié)點(diǎn)，算法實(shí)現(xiàn)很簡單，所以一般不設(shè)置頭結(jié)點(diǎn)。第四節(jié) 數(shù)組一、選擇題1．?dāng)?shù)組通常具有的兩種基本操作是( )。 A．建立和刪除 B．索引和修改 *C．查找和修改 D．查找和索引2．二維數(shù)組A[11，6]采用行序?yàn)橹餍蚍绞酱鎯?chǔ)，每個(gè)數(shù)據(jù)元素占4個(gè)存儲(chǔ)單元，且A[0，0]的存儲(chǔ)地址是1000，則A[8，4]的存儲(chǔ)地址是( )。 *A．1208 B．1212 C．1368 D．13643．對矩陣壓縮存儲(chǔ)是為了( )。 A．方便運(yùn)算 *B．節(jié)省空間 C．方便存儲(chǔ) D．提高運(yùn)算速度4．稀疏矩陣的壓縮存儲(chǔ)方法通常有兩種，即( )。 A．二元數(shù)組和三元數(shù)組 B．三元組和散列 *C．三元組和十字鏈表 D．散列和十字鏈表二、判斷題 √ 1．?dāng)?shù)組是同類型值的集合。 √2．?dāng)?shù)組是一組連續(xù)的內(nèi)存單元。 ╳3．?dāng)?shù)組是一種復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，數(shù)組元素之間的關(guān)系既不是線性的也不是樹形的。 ╳4．插入和刪除操作是數(shù)據(jù)結(jié)構(gòu)中最基本的兩種操作，所以這兩種操作在數(shù)組中也經(jīng)常使用。 √ 5．使用三元組表示稀疏矩陣的元素，有時(shí)并不能節(jié)省存儲(chǔ)空間。三、填空題 1．二維數(shù)組A[10， 20]采用列序?yàn)橹餍蚍绞酱鎯?chǔ)，每個(gè)元素占一個(gè)存儲(chǔ)單元，并且A[1，1]的存儲(chǔ)地址是200，則A[6，12]的地址是___315___。 2．有一個(gè)10階對稱矩陣A采用壓縮存儲(chǔ)方式(以行序?yàn)橹餍蚍绞?存儲(chǔ)其下三角元素，且第一個(gè)元素A[0，0]的存儲(chǔ)地址為1，則A[4，5]的地址是__14__，A[8，3]的地址是___31_。 3．下三角矩陣A[N,N]的下三角元素已壓縮到一維數(shù)組S[N(N+1)／2]中，若按行序?yàn)橹餍虼鎯?chǔ)，則A[i，j]對應(yīng)的S中的存儲(chǔ)位置是__I(I1)/2+j(i≥j),n(n+1)/2+1(Ij)__ ___。四、應(yīng)用題1．假設(shè)有二維數(shù)組A[6,8]，每個(gè)元素用相鄰的6個(gè)字節(jié)存儲(chǔ)，存儲(chǔ)器按字節(jié)編址。已知A的起始地址(基地址)為1000，計(jì)算：(1)數(shù)組A的容量。(2)按行優(yōu)先方式存儲(chǔ)時(shí)，元素A[1，4]的地址。(3)按列優(yōu)先方式存儲(chǔ)時(shí)，元素A[4,7]的地址。答：(1)數(shù)組A的容量:6*8*6=288。(2)按行優(yōu)先方式存儲(chǔ)時(shí)，元素A[1，4]的地址=1000+3*6=1018。(3)按列優(yōu)先方式存儲(chǔ)時(shí)，元素A[4,7]的地址=1000+(6*6+3)*6=1234。2．設(shè)有三對角矩陣A[n，n]，將其三條對角線上的元素逐行存放于數(shù)組B[3n3]中，使得B[k]=A[i,j]，求： (1)用i，j表示k的下標(biāo)變換公式。 (2)用k表示i，j的下標(biāo)變換公式。答：(1) k=2i+j3 (2) I=(k+1)/3+1，j=k2i+3。3．畫出圖52所示的稀疏矩陣A的三元組表和十字鏈表。答：rowcole1422152363585145394．用三元組表表示圖53所示的稀疏矩陣的轉(zhuǎn)置矩陣。答：rowcole122211334445523五、算法設(shè)計(jì)題1．設(shè)計(jì)將數(shù)組A[n]中的所有奇數(shù)移到所有偶數(shù)之前的算法。要求不另外增加存儲(chǔ)空間且時(shí)間復(fù)雜度為O(n)。 算法采用兩個(gè)變量i和j分別表示數(shù)組的開頭和末尾元素，同時(shí)向中間搜索：void change(int a[n]) { I=0。 j=n1。 while (Ij){while (a[I]%2!=0amp。amp。Ij) I++。 while (a[I]%2==0amp。amp。Ij) j。 if (Ij) {c=a[I]。a[I]=a[j]。a[j]=c。 I++。j。}} }*2．當(dāng)稀疏矩陣A和B均以三元組作為存儲(chǔ)結(jié)構(gòu)時(shí)，試寫出矩陣相加的算法，其結(jié)果存放在三元組C中。 略。第五節(jié) 樹(樹根結(jié)點(diǎn)的高度為1)一、選擇題1．以下說法錯(cuò)誤的是( )。 *A．樹形結(jié)構(gòu)的特點(diǎn)是一個(gè)結(jié)點(diǎn)可以有多個(gè)直接前驅(qū) B．線性結(jié)構(gòu)中的一個(gè)結(jié)點(diǎn)至多只有一個(gè)直接后繼 C．二叉樹與樹是兩種不同的數(shù)據(jù)結(jié)構(gòu) D．樹(及一切樹形結(jié)構(gòu))是一種“分支層次’結(jié)構(gòu)2．以下說法錯(cuò)誤的是( )。 A．二叉樹可以是空集 *B．二叉樹的任一結(jié)點(diǎn)都有兩棵子樹 C．二叉樹與樹具有相同的樹形結(jié)構(gòu) D、二叉樹中任一結(jié)點(diǎn)的兩棵子樹有次序之分3．以下說法錯(cuò)誤的是( )。 A．完全二叉樹上結(jié)點(diǎn)之間的父子關(guān)系可由它們編號(hào)之間的關(guān)系來表達(dá) B．在三叉鏈表上，二叉樹的求雙親操作很容易實(shí)現(xiàn) C．在二叉鏈表上，求根以及求左、右孩子等操作很容易實(shí)現(xiàn) *D．在二叉鏈表上，求雙親操作的時(shí)間性能很好4．以下說法錯(cuò)誤的是( )。 A．一般在哈夫曼樹中，權(quán)值越大的葉子離根結(jié)點(diǎn)越近 B．哈夫曼樹中沒有度數(shù)為1的分支結(jié)點(diǎn) C．若初始森林中共有n棵二叉樹，最終求得的哈夫曼樹共有2n1個(gè)結(jié)點(diǎn) *D．若初始森林中共有n棵二叉樹，進(jìn)行2n1次合并后才能剩下一棵最終的哈夫曼樹5．深度為6的二叉樹最多有( )個(gè)結(jié)點(diǎn)。 A．64 *B．63 C．32 D．316．將含有41個(gè)結(jié)點(diǎn)的完全二叉樹從根結(jié)點(diǎn)開始編號(hào)，根為1號(hào)，后面按從上到下、從左到右的順序?qū)Y(jié)點(diǎn)編號(hào)，那么編號(hào)為21的雙親結(jié)點(diǎn)編號(hào)為( )。 *A．10 B．11 C．41 D．207．任何一棵二叉樹的葉結(jié)點(diǎn)在其前序、中序、后序遍歷序列中的相對位置( )。 A．肯定發(fā)生變化 B．有時(shí)發(fā)生變化 *C．肯定不發(fā)生變化 D．無法確定8．設(shè)二叉樹有n個(gè)結(jié)點(diǎn)，則其深度為( )。 A．n1 B．n C．└log2n┘+1 *D．無法確定9．設(shè)深度為k的二叉樹上只有度為0和度為2的結(jié)點(diǎn)，則這類二叉樹上所含結(jié)點(diǎn)總數(shù)最少( )個(gè)。 A．k+l B．2k *C．2k1 D．2k+110．下列說法正確的是( )。 *A．樹的前序遍歷序列與其對應(yīng)的二叉樹的前序遍歷序列相同 B．樹的前序遍歷序列與其對應(yīng)的二叉樹的后序遍歷序列相同 C．樹的后序遍歷序列與其對應(yīng)的二叉樹的前序遍歷序列相同 D．樹的后序遍歷序列與其對應(yīng)的二叉樹的后序遍歷序列相同11．下列說法中正確的是( )。 A．任何一棵二叉樹中至少有一個(gè)結(jié)點(diǎn)的度為2 B．任何一棵二叉樹中每個(gè)結(jié)點(diǎn)的度都為2 C．任何一棵二叉樹中的每個(gè)結(jié)點(diǎn)的度肯定等于2 *D．任何一棵二叉樹中的每個(gè)結(jié)點(diǎn)的度都可以小于212．一棵二叉樹滿足下列條件：對任意結(jié)點(diǎn)，若存在左、右子樹，則其值都小于它的左子樹上所有結(jié)點(diǎn)的值，而大于右子樹上所有結(jié)點(diǎn)的值?，F(xiàn)采用( )遍歷方式就可以得到這棵二叉樹所有結(jié)點(diǎn)的遞減序列。 A．前序 *B．中序 C．后序 D．層次13．設(shè)森林T中有4棵樹，結(jié)點(diǎn)個(gè)數(shù)分別是nnnn4，當(dāng)把森林T轉(zhuǎn)換成一棵二叉樹后，根結(jié)點(diǎn)的右子樹上有( )個(gè)結(jié)點(diǎn)。 A．n11 B．n1 C．n1+n2+n3 *D． n2+n3+n414．對含有( )個(gè)結(jié)點(diǎn)的非空二叉樹，采用任何一種遍歷方式，其結(jié)點(diǎn)訪問序列均相同。 A．0 *B．1 C．2 D．不存在這樣的二叉樹15．如圖61所示的二叉樹的中序遍歷序列是( )。 A．a(chǎn)bcdgef *B．dfebagc C．dbaefcg D．defbagc16．已知某二叉樹的后序遍歷序列是deacb，中序遍歷序列是deabc，它的前序遍歷序列是( )。 A．a(chǎn)cbed *B．baedc C．dceab D．cedba17．如果T1是由有序樹轉(zhuǎn)化而來的二叉樹，那么T中結(jié)點(diǎn)的前序就是T1中結(jié)點(diǎn)的( )。 *A．前序 B．中序 C．后序 D．層次序18．某二叉樹的前序遍歷的結(jié)點(diǎn)訪問順序是abd