【文章內容簡介】 ．設C語言數組Data[m+1]作為循環(huán)隊列SQ的存儲空間， front為隊頭指針，rear為隊為指針，則執(zhí)行出隊操作的語句為 （ ）①front=front+1 ② front=（front+1）%m③rear=(rear+1)%m ④ front=(front+1)%(m+1)（ ）中。①M[1:n(n+1)/2+1] ② M[1:n(n+1)/2]③M[n(n+1)/2+1] ④M[n(n+1)/2]，元素s1,s2,s3,s4,s5,s6依次進棧，如果6個元素出線的順序是s2,s3,s4, s6 , s5,s1,則棧的容量至少應該是 （ ） ①2 ② 3 ③ 5 ④622．設有一順序棧已含3個元素，如下圖所示，元素a4正等待進棧。那么下列4個序列中不可能出現的出棧序列是 （ ） 0 1 2 3 maxsize1a1a2a3sq ↑top ①a3,a1,a4,a2 ②a3,a2,a4,a1 ③ a3,a4,a2,a1 ④a4,a3,a2,a1，其操作步驟為 （ ）①Topnext=s ② snext=Topnext。Topnext=s③snext=Top。Top=s ④ snext=Top。Top=Topnext，并將被刪節(jié)點的值保存到x中，其操作步驟為（ ）①x=Topdata。Top=Topnext ②Top=Topnext。x=Topdata③x=Top。Top=Topnext ④ x=Topdata ，若f,r分別為隊首、隊尾指針，則插入s所指結點的操作為（ ）①fnext=c。f=s ②rnext=s。r=s③snext=r。r=s ④ snext=f。f=s26常對數組進行的兩種基本操作是 （ ）①建立與刪除 ② 索引與修改 ③ 查找與修改 ④ 查找與索引27．鏈棧與順序棧相比，有一個比較明顯的優(yōu)點即 （ ）①插入操作更方便 ② 通常不會出現棧滿的情況③不會出現棧空的情況 ④ 刪除操作更方便 28．若采用三元組壓縮技術存儲稀疏矩陣，只要把每個元素的行下標和列下標互換，就完成了對該矩陣的轉置運算，這種觀點 （ ）①正確 ②錯誤29。二為數組M[i,j]的元素是4個字符（每個字符占一個存儲單元）組成的串，行下標i的范圍從O到4，列下標j的范圍從O到5。M按行存儲時元素M[3,5] 的起始地址與M按列存儲時元素( )的起始地址相同。①M [2,4] ② M[3,4] ③M[3,5] ④M[4,4],b,c,d,e,則棧的不可能的輸出序列是 （ ） ① e d c b a ②d e c b a ③d c e a b ④a b c d e，2，3，4，則隊列的輸出系列是 （ ） ① 4，3，2，1 ② 1，2，3，4， ③1，4，3，2 ④ 3，2，4，132．設計一個判別表達式中左、右括號是否配對出線的算法，采用（ ）數據結構最佳。 ①線性標的順序存儲結構 ②棧③ 隊列 ④ 線性表的鏈式存儲結構 33．若已知一個棧的輸入序列為1，2，3，...,n,其輸出序列為PP...Pn。若p1=n,則P1為 ①i ②n=i ③ ni+1 ④ 不確定34．以下說法正確的是①順序隊和循環(huán)隊的隊滿和隊空判斷條件是一樣的②棧可以作為實現過程調用的一種數據結構③插人和刪除操作是數據結構中最基本的兩種操作，所以這兩種操作在數組中也經常使用④在循環(huán)隊列中，front指向隊列中第一個元素的前一位置，rear指向實際的隊尾元素，隊列為滿的條件front=rear35. 以下說法正確的是①數組是同類型值的集合②數組是一組相繼的內存單元③數組是一種復雜的數據結構，數組元素之間的關系，既不是線性的，也不是樹形的④使用三元組表表示稀疏矩陣的元素，有時并不能節(jié)省存儲空間四、簡答及應用1．簡述順序棧的類型定義。2．簡述鏈棧的類型定義。3．簡述順序隊列、循環(huán)隊列的類型定義。4．簡述鏈隊的類型定義。5，寫出基于三元組的稀疏矩陣的類型說明。6．對于循環(huán)隊列，試寫出求隊列長度的算法。7．設有編號為t，2，3，4的四輛列車。順序進入一個占世界共的展臺，試寫出這四兩列車開出車站的所有可能的順序。8設有上三角矩陣(aij)n*n,將其上三角元素逐行存于數組B(1:m)中（m充分大），使得B[k]=aij,且k=f1(i)+f2(j)+c。是推導出函數f1,f2和常數c(要求f1和f2中不含常數項)。9．設有三對角矩陣（aij）n*n,將其三條對角線上的元素逐行存于數組B(1:3n2)中，使得B[k]=aij,求：（1） 用i、j表示k的下標變換公式；（2） 用k表示i、j的下標變換公式.，寫出程序的運行結果。 define sqstack_maxsize 40typedef struct sqstack{ char data[sqstack_maxsize]。 int top。} SqStackTp。main(){ SqStackTp sq。 int i。 char ch。 InitStack(amp。sq)。 For(ch=’A’。ch=’A’+12。ch++) { Push(amp。sq,ch)。printf(“%c”,ch)。 } printf(“\n”)。 while(!EmptyStack(sq)){ Pop(amp。sq,amp。ch)。 printf(“amp。c”,ch)。} printf(“\n”)。}，寫出其完整的功能。Void reverse_list( LinkedListTP *head){ LstackTP ls,p。 DataType x。 InitStack(amp。ls)。 p=headnext。 While(p!=NULL){ Push(amp。lspdata)。 p=pnext。} p=headnext。 While(! EmptyStack(amp。ls)) { Pop(amp。l,amp。x)。 pdata=x。 p=pnext。}} 12，對下列函數，按照《數據結構導論》課本的圖35失利，畫出調用f(5)是引起的工作棧狀態(tài)變化情況。Int f(int I){ if(n==1) return(10)。 else return(f(I1)+2)。}五、算法設計，過江渡船每次能載10輛車過江。過江車輛分為客車類和貨車類，上渡船的有如下規(guī)定：同類車先到先上船；且每上4輛客車，才允許上一輛貨車；若等待客車不足4輛，則以火車代替，若無貨車等待允許客車都上船。試寫一算法模擬渡口管理?？梢栽谝粋€數組中保存兩個棧：一個棧以數組的第一個單元作為棧底，另一個棧以數組的最后一個單元作為棧底（如下圖所示）。設S是其中一個占，是分別編寫過程push(S,X)(元素X入棧)， 出棧pop(S)和取棧頂元素Top(S).題示：設其中一個棧為0，另一棧為1。 0 1 2 M1 M M+1 棧0底 棧0頂 棧1頂 棧1底3．假設以帶頭結點的循環(huán)鏈表表示隊列，并且只設一個指針指向隊尾元素結點（注意不設頭指針），試編寫相應的初始化隊列、入隊列和出隊列算法。4．假設以數組cycque[m](假設數組范圍在0..m)存放循環(huán)隊列的元素，同時設變量rear和quelen分別指示循環(huán)隊列中隊尾元素位置和內含元素的個數。試給出此循環(huán)隊列的隊滿條件，并寫出相應的入隊列和出隊列的算法。5．編寫算法:按行優(yōu)先存儲順序，將稀疏矩陣轉換為三元組的表示形式。6．稀疏矩陣用三元組的表示形式，試寫一算法實現兩個稀疏矩陣相加，結果仍用三元組表示。7．假設一個算術表達式中可以包含三中括號：圓括號“（”和“）”，方括號“[”和“]”以及花括號與“{”和“}”，且這三種括號可按任意的次序嵌套試用，如（.. .[.. .{.. .}.. .[.. .].. .].. .( .. .[.. .].. .)。試利用棧的運算編寫判斷給定表達式中所含括號是否正確 配對出現的算法（可設表達式已存入字符型數組中）。8．已知Ackerman函數定義如下：akm(m,n)=試寫出遞歸算法。9．設函數f(m,n)按下式定義（ m,n為）0的整數）f(m,n)=試寫出計算函數的遞歸過程。10．設有一個背包可以放入的物品重量為S，現有n件物品，重量分別為w1,w2,.. .，，則稱此背包問題有解（或承接為真），否