【導(dǎo)讀】1．要求同一邏輯結(jié)構(gòu)的所有數(shù)據(jù)元素具有相同的特性，這意味著()。A．?dāng)?shù)據(jù)元素具有同一的特點*B．不僅數(shù)據(jù)元素包含的數(shù)據(jù)項的個數(shù)要相同，而且對應(yīng)數(shù)據(jù)項的類型要一致C．每個數(shù)據(jù)元素都一樣D．?dāng)?shù)據(jù)元素所。2．?dāng)?shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計算的程序設(shè)計問題中計算機的((1))以及它們之間的((2))和運算的學(xué)科。3．?dāng)?shù)據(jù)結(jié)構(gòu)被形式地定義為(D，R)，其中D是((1))的有限集合，R是D上((2))的有限集合。A．找出數(shù)據(jù)結(jié)構(gòu)的合理性B．研究算法中的輸入和輸出的關(guān)系*C．分析算法的效率以求改進D．分析算法的易懂性和文檔性。A．線性表的線性存儲結(jié)構(gòu)優(yōu)于鏈式存儲結(jié)構(gòu)*B．二維數(shù)組是它的每個數(shù)據(jù)元素為一個線性表的線性表C．棧的操作方式是先進先出D．隊列的操作。10．根據(jù)數(shù)據(jù)元素之間關(guān)系的不同特性，以下四類基本的邏輯結(jié)構(gòu)反映了四類基本的數(shù)據(jù)組織形式，其中解釋錯誤的是()。不同的條件下，數(shù)據(jù)元素又可稱為元素、結(jié)點、頂點、記錄等。5．將數(shù)量級210，

　　

【正文】 不帶頭結(jié)點的、已知尾指針的單循環(huán)鏈表為存儲結(jié)構(gòu)解決上述問題。 答： void Js1(int A[n]， int N， iht K) {／／以數(shù)組為存儲結(jié)構(gòu) for(i=0； iN。i++)A[I]=1； ／／用 1 標志在環(huán)上的結(jié)點 j=0； for(i=0； iN。 i++) {s=0； while(sK) {j=(j%N)+1； s=s+A[j1]； } ／／計數(shù) printf(” %d”， j)； A[j1]=0。／／將計滿 k 值的數(shù)字輸出，并將其位置標為 0 表明已刪除 } } void Js2(LinkedList last， int N， int K) {／／以不帶頭結(jié)點的、已知尾指針的單循環(huán)鏈表為存儲結(jié)構(gòu) p=last； q=pnext； ／／此時 q 為頭結(jié)點 fp 為 q 的前驅(qū) while(N0) {for(j=2； j=K； j++) ／／循環(huán) K1 次 {p=q； q=pnext； } printf(” %d”， qdata)； N； pnext=qnext。 ／／刪除 q q=p— next； } } 第三節(jié) 棧和隊列 一、選擇題 1．設(shè)有一順序棧 s，元素 s1， s2， s3， s4， s5， s6 依次入棧，如果 6 個元素出棧的順序是 s2， s3， s4， s6， s5， s1，則棧的容量至少應(yīng)該是 ( )。 A． 2 *B． 3 C． 5 D． 6 2．若一個棧的輸入序列是 a、 b、 c，則通過入棧、出棧操作可能得到 a、 b、 c 的不同排列個數(shù)為 ( )。 A． 4 *B． 5 C． 6 D． 7 3．設(shè)有一順序棧已經(jīng)含有 3 個元素，如圖 31 所示，元素 a4 正等待入棧。以下序列中不可能出現(xiàn)的出棧序列是 ( )。 *A． a3， a1， a4， a2 B． a3， a2， a4， a1 C． a3， a4， a2， a1 D． a4， a3， a2， a1 4．和順序棧相比，鏈棧有一個比較明顯的優(yōu)勢是 ( )。 *A．通常不會出現(xiàn)棧滿的情況 B．通常不會出現(xiàn)?？盏那闆r C．插入操作更容易實現(xiàn) D．刪除操作更容易實現(xiàn) 5．若一個棧的輸入序列是 1， 2， 3， 4，?， n，輸出序列的第一個元素是 n，則第 i 個輸出元素是 ( )。 A．不確定 B． ni *C． ni+1 D． ni1 6．以下說法正確的是 ( )。 *A．因鏈棧本身沒有容量限制，故在用戶內(nèi)存空間的范圍內(nèi)不會出現(xiàn)棧滿情況 B．因順序棧本身沒有容量限制，故在用戶內(nèi)存空間的范圍內(nèi)不會出現(xiàn)棧滿情況 C．對于鏈棧而言，在棧滿狀態(tài)下，如果再進行 入棧操作，則會發(fā)生“上溢” D．對于順序棧而言，在棧滿狀態(tài)下，如果再進行入棧操作，則會發(fā)生“下溢” 7．順序隊列的入隊操作應(yīng)為 ( 初值為 1 )。 13 *A． =+1； []=x。 B． []=x； =+1； C． =(+1)％ maxsize； [+1]=x。 D． []=x； =x。 =(+1)％ maxslze； 8．循環(huán)隊列的入隊操作應(yīng)為 ( 初值為 1 )。 A． sq． rear=sq． rear+1； sq． data[sq． rear]=x B． sq． data[sq． rear]=x； sq． rear=sq． rear+l； *C． sq． rear=(sq． rear+1)％ maxsize； sq． data[sq． rear]=x； D． sq． data[sq． rear]=x； sq． rear=(sq． rear+1)％ maxsize； 9．順序隊列的出隊操作為 (sq. front 初值為 1 )。 A． sq． front=(sq． front+1)％ maxsize； *B． sq． front=sq． front+1； C． sq． rear=(sq． rear+1)％ maxsize； D． sq． rear=sq． rear+1。 10．循環(huán)隊列的出隊操作為 (sq. front 初值為 1 )。 *A． sq． front=(sq． front+1)％ maxsize； B． sq． front=sq． front+1； C． sq． rear=(sq． rear+1)％ maxsize； D． sq． rear=sq． rear+l； 11．循環(huán)隊列的隊滿條件為 ( )。 A． (sq． rear+1)％ maxsize==(sq． front+1)％ maxsize； B． (sq． rear+1)％ maxsize==sq． front+1； *C． (sq． rear+1)％ maxsize==sq． front； D． sq． rear==sq． front； 12．循環(huán)隊列的隊空條件為 ( )。 A． (sq． rear+1)％ maxsize==(sq． front+1)％ maxsize； B． (sq． rear+1)％ maxsize==sq． front+1； C． (sq． rear+1)％ maxsize==sq． front； *D． sq． rear==sq． front； 13．如果以鏈表作為棧的存儲結(jié)構(gòu)，則出棧操作時 ( )。 A．必須判別棧是否滿 B．判別棧元素的類型 *C．必須判別棧是否空 D．對棧不做任何判別 14，向一個棧頂指針為 Top 的鏈棧中插入一個 s 所指結(jié)點時，其操作步驟為 ( )。 A． Topnext=s； B． snext=Topnext； Topnext=s； *C． snext=Top； Top=s； D． snext=Top； Top=Topnext； 15．從棧頂指針為 Top 的鏈棧中刪除一個結(jié)點，并將被刪結(jié)點的值保存到 x 中，其操作步驟為 ( )。 *A． x=Topdata； Top=Topnext； B． Top=Topnext； x=Topdata； C． x=Top； Top=Topnext； D． x=Topdata； 16．在一個鏈隊中，苕 f、 r 分別為隊頭、隊尾指針，則插入 s 所指結(jié)點的操 作為 ( )。 A． fnext=s； f=s； *B． rnext=s； r=s； C． snext=r； r=s； D． snext=f； f=s； 17．一個棧的入棧序列是 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， b， c， d， e 18．一個隊列的入隊序列是 1， 2， 3， 4，則隊列可能的輸出序列是 ( )。 A． 4， 3， 2， 1 *B． 1， 2， 3， 4 C． 1， 4， 3， 2 D． 3， 2， 4， 1 19．設(shè)計一個判別表達式中左，右括號是否配對出現(xiàn)的算法，采用 ( )數(shù)據(jù)結(jié)構(gòu)最佳。 A．線性表的順序存儲結(jié)構(gòu) *B．棧 C．隊列 D．線性表的鏈式存儲結(jié)構(gòu) 二、判斷題 √ 1．在順序棧棧滿情況下，不能再入棧，否則會產(chǎn)生“上溢”。 ╳ 2．與順序棧相比，鏈棧的一個優(yōu)點是插入和刪除操作更加方便。 ╳ 3．若一個棧的輸入序列為 1， 2， 3，?， n，其輸出序列的第一個元素為 n，則其輸出序列的每個元素 ai 一定滿足 ai=i+1(i=1， 2，?， n)。 √ 4．在鏈隊 中，即使不設(shè)置尾指針也能進行入隊操作。 √ 5．在對鏈隊 (帶頭指針 )做出隊操作時，不會改變 front 指針的值。 ╳ 6．循環(huán)隊列中元素個數(shù)為 rearfront。 ╳ 7．一個棧的輸入序列是 1,2,3,4，則在棧的輸出序列中可以得到 4,3,1,2． √ 8．一個棧的輸入序列是 1,2,3,4，則在棧的輸出序列中可以得到 1,2,3,4。 ╳ 9．若以鏈表作為棧的存儲結(jié)構(gòu)，則入棧需要判斷棧是否滿． √ 10．若以鏈表作為棧的存儲結(jié)構(gòu)，則出棧需要判斷棧是否空。 三、填空題 1．向一個棧頂指針為 Top 的鏈棧中插入一個 s 所指的結(jié)點 時，其進行的操作是 __ snext=Top； Top =s； __。 2．從棧頂指針為 Top 的鏈棧中刪除一個結(jié)點，并將結(jié)點保存在 x 中，進行的操作是 _ x=Topdata； Top=Topnext； __。 3．在具有 n 個單元的循環(huán)隊列中，隊滿時共有 ___n1_個元素。 4．假設(shè)以 S 和 X 分別表示入棧和出棧操作，則對輸入序列 a， b， c， d， e 進行一系列棧操作 SSXSXSSXXX之后，得到的輸出序列為 __ b， c， e， d， a ___。 5．設(shè)有數(shù)組 A[m]作為循環(huán)隊列的存儲空間， front 為隊頭指針， rear 為隊尾指針，則元素 x 執(zhí)行入隊操作的語句是 _rear=（ rear +1） ％（ m+1） ； A[rear]=x。__。 6．在一個鏈隊中，如果 f、 r 分別為隊頭、隊尾指針，則插入 s 所指結(jié)點的操作是 _rnext=s。 r=s。___。 7．棧的邏輯特點是 __后進先出 ____，隊列的邏輯特點是 _先進先出 __，二者的共同特點是 _操作受限 __。 8． ___棧 ___可以作為實現(xiàn)遞歸函數(shù)調(diào)用的一種數(shù)據(jù)結(jié)構(gòu)。 14 9．在隊列中，新插入的結(jié)點只能添加到 __隊尾 __。 10．鏈隊在一定范圍內(nèi)不會出現(xiàn) __隊滿 ___的情況。當(dāng) lq． front==lq． rear 時，隊中無元素，此時 ___隊空 __。 11．設(shè)一個鏈棧的棧頂指針為 ls，棧中結(jié)點的格式為 data:next，?？盏臈l件是 _ ls = NULL__；如果棧不為空，則出棧操作為 p=ls。 ___ ls = ls next __；free(p)。 12．對帶有頭結(jié)點的鏈隊 lq，判定隊列中只有一個數(shù)據(jù)元素的條件是 __lqfrontnext= lqrear___。 13．設(shè)有一個空棧，現(xiàn)在輸入序列為 1， 2， 3， 4， 5，經(jīng)過 push， push， pop， push， pop， push 后，棧頂指針所指元素是 __4__。 14．設(shè)用一維數(shù)組 A[n]來表示一個棧，令 A[0]為棧底。用整型變量 t 來指示當(dāng)前棧頂?shù)奈恢茫?A[t]為棧頂元素。往棧中壓入一個新元素時，變量 t 的值 __加1___，從棧中彈出一個元素時，變量 t 的值 ___減 1___。設(shè)空棧時，輸入序列 a， b， c 經(jīng)過 push， pop， push， push， pop 操作后，從棧中彈出的元素是 ___c__。 四、應(yīng)用題 2．設(shè)有字符串為 3*ya/y^2，試利用棧寫出將其轉(zhuǎn)換為 3y*ay2^/的操作過程。假定用 X 代表掃描該字符串過程中順序取 一個字符入棧的操作，用 S 代表從棧中取出一個字符加入到新字符串尾的出棧操作。例如， ABC 變?yōu)?BCA 的操作步驟為 XXSXSS。 答： XSXXXSSSXXSXXSXXSSSS 3．設(shè)有一個輸入序列 a， b， c， d，元素經(jīng)過一個棧到達輸出序列，而且元素一旦離開輸入序列就不能再回到輸入序列，試問經(jīng)過這個棧后可以得到多少種輸出序列 ? 答：可以得到 14 種輸出序列： abcd,abdc,acbd,acdb,adcb,bacd,bcad,bcda,bdca,cbad,cbda,cdba,dcba,badc. 4．按照運算符優(yōu)先法 ，畫出對下面算術(shù)表達式求值時，操作數(shù)棧和運算符棧的變化過程： 92*4+(8+1)/3。 答： 序號 運算符棧 操作數(shù)棧 輸入字符 1 9 2 9 3 9 2 4 92 * 5 * 92 4 6 * 924 + 7 98 8 1 9 + 1 ( 10 +( 1 8 11 +( 18 + 12 +(+ 18 1 13 +(+ 181 ) 14 + 19 / 15 +/ 19 3 16 +/ 193 17 + 13 18 4 5．鏈棧中為何不設(shè)置頭結(jié)點 ? 答：因為鏈棧只在鏈表頭插入和刪除結(jié)點，不可能在鏈表中間插入或刪除結(jié)點，算法實現(xiàn)很簡單，所以一般不設(shè)置頭結(jié)點。 第五節(jié) 樹 (樹根結(jié)點的高度為 1) 一、選擇題 1．以下說法錯誤的是 ( )。 *A．樹形結(jié)構(gòu)的特點是一個結(jié)點可以有多個直接前驅(qū) B．線性結(jié)構(gòu)中的一個結(jié)點至多只有一個直接后繼 C．二叉樹與樹是兩種不同的數(shù)據(jù)結(jié)構(gòu) D．樹(及一切樹形結(jié)構(gòu) )是一種“分支層次’結(jié)構(gòu) 2．以下說法錯誤的是 (