《《大數(shù)據(jù)結(jié)構(gòu)》課后參考問題詳解》由會員分享，可在線閱讀，更多相關(guān)《《大數(shù)據(jù)結(jié)構(gòu)》課后參考問題詳解（125頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、word單元練習(xí)1一判斷題如下各題，正確的請在前面的括號打；錯誤的打1數(shù)據(jù)的邏輯結(jié)構(gòu)與數(shù)據(jù)元素本身的容和形式無關(guān)。2一個數(shù)據(jù)結(jié)構(gòu)是由一個邏輯結(jié)構(gòu)和這個邏輯結(jié)構(gòu)上的一個根本運算集構(gòu)成的整體。3數(shù)據(jù)元素是數(shù)據(jù)的最小單位。4數(shù)據(jù)的邏輯結(jié)構(gòu)和數(shù)據(jù)的存儲結(jié)構(gòu)是一樣的。5程序和算法原如此上沒有區(qū)別，所以在討論數(shù)據(jù)結(jié)構(gòu)時可以通用。6從邏輯關(guān)系上講，數(shù)據(jù)結(jié)構(gòu)主要分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)兩類。7數(shù)據(jù)的存儲結(jié)構(gòu)是數(shù)據(jù)的邏輯結(jié)構(gòu)的存儲映像。8數(shù)據(jù)的物理結(jié)構(gòu)是指數(shù)據(jù)在計算機實際的存儲形式。9數(shù)據(jù)的邏輯結(jié)構(gòu)是依賴于計算機的。10算法是對解題方法和步驟的描述。二填空題（1） 數(shù)據(jù)有邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)兩種結(jié)構(gòu)。（2） 數(shù)據(jù)

2、邏輯結(jié)構(gòu)除了集合以外，還包括：線性結(jié)構(gòu)、樹形結(jié)構(gòu)和圖形結(jié)構(gòu)。（3） 數(shù)據(jù)結(jié)構(gòu)按邏輯結(jié)構(gòu)可分為兩大類，它們是線性結(jié)構(gòu)和非線性結(jié)構(gòu)。（4） 樹形結(jié)構(gòu)和圖形結(jié)構(gòu)合稱為非線性結(jié)構(gòu)。（5） 在樹形結(jié)構(gòu)中，除了樹根結(jié)點以外，其余每個結(jié)點只有1個前趨結(jié)點。（6） 在圖形結(jié)構(gòu)中，每個結(jié)點的前趨結(jié)點數(shù)和后續(xù)結(jié)點數(shù)可以任意多個。（7） 數(shù)據(jù)的存儲結(jié)構(gòu)又叫物理結(jié)構(gòu)。（8） 數(shù)據(jù)的存儲結(jié)構(gòu)形式包括：順序存儲、鏈式存儲、索引存儲和散列存儲。（9） 線性結(jié)構(gòu)中的元素之間存在一對一的關(guān)系。（10） 樹形結(jié)構(gòu)結(jié)構(gòu)中的元素之間存在一對多的關(guān)系，（11） 圖形結(jié)構(gòu)的元素之間存在多對多的關(guān)系。（12） 數(shù)據(jù)結(jié)構(gòu)主要研究數(shù)據(jù)的邏輯結(jié)

3、構(gòu)、存儲結(jié)構(gòu)和算法或運算三個方面的容。（13） 數(shù)據(jù)結(jié)構(gòu)被定義為(D，R)，其中D是數(shù)據(jù)的有限集合，R是D上的關(guān)系的有限集合。（14） 算法是一個有窮指令的集合。（15） 算法效率的度量可以分為事先估算法和事后統(tǒng)計法。（16） 一個算法的時間復(fù)雜性是算法輸入規(guī)模的函數(shù)。（17） 算法的空間復(fù)雜度是指該算法所消耗的存儲空間，它是該算法求解問題規(guī)模n的函數(shù)。（18） 假如一個算法中的語句頻度之和為Tn=6n+3nlog2n，如此算法的時間復(fù)雜度為 Onlog2n。（19） 假如一個算法中的語句頻度之和為Tn=3n+nlog2n+n2，如此算法的時間復(fù)雜度為 On2。20數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計算

4、的程序設(shè)計問題中計算機的操作對象，以與它們之間的關(guān)系和運算的學(xué)科。三選擇題1數(shù)據(jù)結(jié)構(gòu)通常是研究數(shù)據(jù)的 A 與它們之間的相互聯(lián)系。 A. 存儲結(jié)構(gòu)和邏輯結(jié)構(gòu) B. 存儲和抽象 C. 聯(lián)系和抽象 D. 聯(lián)系與邏輯2在邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成： C 。 A. 動態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu) B. 緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu) C. 線性結(jié)構(gòu)和非線性結(jié)構(gòu) D. 部結(jié)構(gòu)和外部結(jié)構(gòu)3數(shù)據(jù)在計算機存儲器表示時，物理地址和邏輯地址一樣并且是連續(xù)的，稱之為 C 。 A. 存儲結(jié)構(gòu) B. 邏輯結(jié)構(gòu) C. 順序存儲結(jié)構(gòu) D. 鏈式存儲結(jié)構(gòu)4非線性結(jié)構(gòu)中的每個結(jié)點 D 。A. 無直接前趨結(jié)點B. 無直接后繼結(jié)點C. 只有一個直接前趨結(jié)點

5、和一個直接后繼結(jié)點D. 可能有多個直接前趨結(jié)點和多個直接后繼結(jié)點5鏈式存儲的存儲結(jié)構(gòu)所占存儲空間 A 。 A分兩局部，一局部存放結(jié)點的值，另一局部存放表示結(jié)點間關(guān)系的指針 B只有一局部，存放結(jié)點的值 C只有一局部，存儲表示結(jié)點間關(guān)系的指針 D分兩局部，一局部存放結(jié)點的值，另一局部存放結(jié)點所占單元素6算法的計算量大小稱為算法的 C 。 A. 現(xiàn)實性 B. 難度 C. 時間復(fù)雜性 D. 效率7數(shù)據(jù)的根本單位是 B 。 A. 數(shù)據(jù)結(jié)構(gòu) B. 數(shù)據(jù)元素 C. 數(shù)據(jù)項 D. 文件8每個結(jié)點只含有一個數(shù)據(jù)元素，所有存儲結(jié)點相繼存放在一個連續(xù)的存儲區(qū)里，這種存儲結(jié)構(gòu)稱為 A 結(jié)構(gòu)。 A. 順序存儲 B. 鏈

6、式存儲 C. 索引存儲 D. 散列存儲9每一個存儲結(jié)點不僅含有一個數(shù)據(jù)元素，還包含一組指針，該存儲方式是 B 存儲方式。 A. 順序 B. 鏈式C. 索引 D. 散列10以下任何兩個結(jié)點之間都沒有邏輯關(guān)系的是 D 。 A. 圖形結(jié)構(gòu) B. 線性結(jié)構(gòu) C. 樹形結(jié)構(gòu) D. 集合11在數(shù)據(jù)結(jié)構(gòu)中，與所使用的計算機無關(guān)的是 C 。 A. 物理結(jié)構(gòu) B. 存儲結(jié)構(gòu) C. 邏輯結(jié)構(gòu) D. 邏輯和存儲結(jié)構(gòu)12如下四種根本邏輯結(jié)構(gòu)中，數(shù)據(jù)元素之間關(guān)系最弱的是 A 。 A. 集合 B. 線性結(jié)構(gòu) C. 樹形結(jié)構(gòu) D. 圖形結(jié)構(gòu)13與數(shù)據(jù)元素本身的形式、容、相對位置、個數(shù)無關(guān)的是數(shù)據(jù)的 A 。 A. 邏輯結(jié)構(gòu)

7、B. 存儲結(jié)構(gòu) C. 邏輯實現(xiàn) D. 存儲實現(xiàn)14每一個存儲結(jié)點只含有一個數(shù)據(jù)元素，存儲結(jié)點存放在連續(xù)的存儲空間，另外有一組指明結(jié)點存儲位置的表，該存儲方式是 C 存儲方式。 A. 順序 B. 鏈式 C. 索引 D. 散列15算法能正確的實現(xiàn)預(yù)定功能的特性稱為算法的 A 。 A. 正確性 B. 易讀性 C. 健壯性 D. 高效性16算法在發(fā)生非法操作時可以作出處理的特性稱為算法的 C 。 A. 正確性 B. 易讀性 C. 健壯性 D. 高效性17如下時間復(fù)雜度中最壞的是 D 。 A. O1 B. O n C. Olog2n D. On218如下算法的時間復(fù)雜度是 D 。 for (i=0;in

8、;i+) for (j=0;in;j+) cij=i+j; A. O1 B. O n C. Olog2n D. On219算法分析的兩個主要方面是 A 。A. 空間復(fù)雜性和時間復(fù)雜性 B. 正確性和簡明性C. 可讀性和文檔性 D. 數(shù)據(jù)復(fù)雜性和程序復(fù)雜性20計算機算法必須具備輸入、輸出和 C 。 A. 計算方法 B. 排序方法C. 解決問題的有限運算步驟 D. 程序設(shè)計方法四分析下面各程序段的時間復(fù)雜度（1） for (i=0;in;i+) for (j=0;jm;j+) Aij解： O(n*m)2 s=0; for (i=0;in;i+) for (j=0;jn;j+) s+=Bij; su

9、m=s;解： O(n2)3 T=A；A=B；B=T；解：O(1)4 s1(int n) int p=1,s=0; for (i=1;i=n;i+) p*=i;s+=p; return(s);O(n)5 s2(int n)x=0;y=0;for (k=1;k=n;k+)x+;for (i=1;i=n;i+)for (j=1;j=n;j+)y+;解：O(n2)五根據(jù)二元組關(guān)系，畫出對應(yīng)邏輯圖形的草圖，指出它們屬于何種數(shù)據(jù)結(jié)構(gòu)。1A=D，R，其中：D=a，b，c，d，e，R= 解： a b c d e屬于集合2B=D,R，其中：D=a,b,c,d,e,f，R=rR=, 尖括號表示結(jié)點之間關(guān)系是有向的

10、解：屬于線性結(jié)構(gòu)。3F=D,R，其中：D=50,25,64,57,82,36,75,55，R=rR=,解：屬于樹結(jié)構(gòu)4C=D,R，其中： D=1,2,3,4,5,6，R=rR=(1,2),(2,3),(2,4),(3,4),(3,5),(3,6),(4,5),(4,6)園括號表示結(jié)點之間關(guān)系是有向的解：屬于圖結(jié)構(gòu)5E=D,R，其中：D=a,b,c,d,e,f,g,h，R=rR=,解：c屬于樹結(jié)構(gòu)。單元練習(xí)2一判斷題如下各題，正確的請在前面的括號打；錯誤的打1線性表的鏈式存儲結(jié)構(gòu)優(yōu)于順序存儲。2鏈表的每個結(jié)點都恰好包含一個指針域。3在線性表的鏈式存儲結(jié)構(gòu)中，邏輯上相鄰的兩個元素在物理位置上并不一

11、定緊鄰。4順序存儲方式的優(yōu)點是存儲密度大，插入、刪除效率高。5線性鏈表的刪除算法簡單，因為當刪除鏈中某個結(jié)點后，計算機會自動地將后續(xù)的各個單元向前移動。6順序表的每個結(jié)點只能是一個簡單類型，而鏈表的每個結(jié)點可以是一個復(fù)雜類型。7線性表鏈式存儲的特點是可以用一組任意的存儲單元存儲表中的數(shù)據(jù)元素。8線性表采用順序存儲，必須占用一片連續(xù)的存儲單元。9順序表結(jié)構(gòu)適宜于進展順序存取，而鏈表適宜于進展隨機存取。10插入和刪除操作是數(shù)據(jù)結(jié)構(gòu)中最根本的兩種操作，所以這兩種操作在數(shù)組中也經(jīng)常使用。二填空題（1） 順序表中邏輯上相鄰的元素在物理位置上必須相連。（2） 線性表中結(jié)點的集合是有限的，結(jié)點間的關(guān)系是一對

12、一關(guān)系。（3） 順序表相對于鏈表的優(yōu)點是：節(jié)省存儲和隨機存取。（4） 鏈表相對于順序表的優(yōu)點是：插入、刪除方便。5采用順序存儲結(jié)構(gòu)的線性表叫順序表。6順序表中訪問任意一個結(jié)點的時間復(fù)雜度均為 O(1) 。7鏈表相對于順序表的優(yōu)點是插入、刪除方便；缺點是存儲密度小。8在雙鏈表中要刪除結(jié)點*P，其時間復(fù)雜度為 O(1) 。9在單鏈表中要在結(jié)點*P之前插入一個新結(jié)點，需找到*P的直接前趨結(jié)點的地址，其查找的時間復(fù)雜度為 O(n) 。（10） 單鏈表中需知道頭指針才能遍歷整個鏈表。（11） 性表中第一個結(jié)點沒有直接前趨，稱為開始結(jié)點。（12） 在一個長度為n的順序表中刪除第i個元素，要移動 n-i 個

13、元素。（13） 在一個長度為n的順序表中，如果要在第i個元素前插入一個元素，要后移 n- i +1 個元素。（14） 在無頭結(jié)點的單鏈表中，第一個結(jié)點的地址存放在頭指針中，而其它結(jié)點的存儲地址存放在前趨結(jié)點的指針域中。（15） 當線性表的元素總數(shù)根本穩(wěn)定，且很少進展插入和刪除操作，但要求以最快速度存取線性表中的元素時，應(yīng)采用順序存儲結(jié)構(gòu)。（16） 在線性表的鏈式存儲中，元素之間的邏輯關(guān)系是通過指針決定的。（17） 在雙向鏈表中，每個結(jié)點都有兩個指針域，它們一個指向其前趨結(jié)點，另一個指向其后繼結(jié)點。（18） 對一個需要經(jīng)常進展插入和刪除操作的線性表，采用鏈式存儲結(jié)構(gòu)為宜。（19） 雙鏈表中，設(shè)p

14、是指向其中待刪除的結(jié)點，如此需要執(zhí)行的操作為： p-prior-next=p-next 。（20） 在如下列圖的鏈表中，假如在指針P所在的結(jié)點之后插入數(shù)據(jù)域值為a和b的兩個結(jié)點，如此可用如下兩個語句： S-next-next=P-next;和P-next=S;來實現(xiàn)該操作。PabS三選擇題1在具有n個結(jié)點的單鏈表中，實現(xiàn) A 的操作，其算法的時間復(fù)雜度都是On。A遍歷鏈表或求鏈表的第i個結(jié)點 B在地址為P的結(jié)點之后插入一個結(jié)點C刪除開始結(jié)點 D刪除地址為P的結(jié)點的后繼結(jié)點2設(shè)a、b、c為三個結(jié)點，p、10、20分別代表它們的地址，如此如下的存儲結(jié)構(gòu)稱為 B 。A 循環(huán)鏈表 B單鏈表 C雙向循環(huán)

15、鏈表 D雙向鏈表3單鏈表的存儲密度 C 。 A大于1 B等于1 C小于1 D不能確定4一個順序存儲的線性表，設(shè)每個結(jié)點占m個存儲單元，假如第一個結(jié)點的地址為B，如此第i個結(jié)點的地址為 A 。A B+(i-1)*m BB+i*m C B-i*m D B+(i+1)*m5在有n個結(jié)點的順序表上做插入、刪除結(jié)點運算的時間復(fù)雜度為 B 。AO1 BOnCOn2 DOlog2n6設(shè)Llink、Rlink分別為循環(huán)雙鏈表結(jié)點的左指針和右指針，如此指針P所指的元素是雙循環(huán)鏈表L的尾元素的條件是 D 。AP= L BP-Llink= L CP= NULL DP-Rlink=L7兩個指針P和Q，分別指向單鏈表的

16、兩個元素，P所指元素是Q所指元素前驅(qū)的條件是 B 。AP-next=Q-next BP-next= Q CQ-next= P DP= Q8用鏈表存儲的線性表，其優(yōu)點是 C 。A便于隨機存取B花費的存儲空間比順序表少C便于插入和刪除 D數(shù)據(jù)元素的物理順序與邏輯順序一樣9在單鏈表中，增加頭結(jié)點的目的是 C 。A使單鏈表至少有一個結(jié)點B標志表中首結(jié)點的位置C方便運算的實現(xiàn) D說明該單鏈表是線性表的鏈式存儲結(jié)構(gòu)10下面關(guān)于線性表的表示中，錯誤的答案是 D 關(guān)系。A順序表必須占一片地址連續(xù)的存儲單元 B順序表可以隨機存取任一元素C鏈表不必占用一片地址連續(xù)的存儲單元 D鏈表可以隨機存取任一元素11L是線性

17、表，LengthListL的值是5，經(jīng)DelListL，2運算后，LengthListL的值是 C 。A2 B3 C4 D512單鏈表的示意圖如下： LABCDQ RP指向鏈表Q結(jié)點的前趨的指針是 B 。AL BP CQ DR13設(shè)p為指向單循環(huán)鏈表上某結(jié)點的指針，如此*p的直接前驅(qū) C 。A找不到 B查找時間復(fù)雜度為O1C查找時間復(fù)雜度為On D查找結(jié)點的次數(shù)約為n14等概率情況下，在有n個結(jié)點的順序表上做插入結(jié)點運算，需平均移動結(jié)點的數(shù)目為 C 。An B(n-1)/2 C n/2 D(n+1)/215在如下鏈表中不能從當前結(jié)點出發(fā)訪問到其余各結(jié)點的是 C 。A雙向鏈表 B單循環(huán)鏈表 C單

18、鏈表 D雙向循環(huán)鏈表16在順序表中，只要知道 D ，就可以求出任一結(jié)點的存儲地址。A基地址 B結(jié)點大小 C向量大小 D基地址和結(jié)點大小17在雙鏈表中做插入運算的時間復(fù)雜度為 A 。AO1 BOn COn2 DOlog2n18鏈表不具備的特點是 A 。A隨機訪問 B不必事先估計存儲空間C插入刪除時不需移動元素 D所需空間與線性表成正比19以下關(guān)于線性表的論述，不正確的為 C 。A線性表中的元素可以是數(shù)字、字符、記錄等不同類型B線性順序表中包含的元素個數(shù)不是任意的C線性表中的每個結(jié)點都有且僅有一個直接前趨和一個直接后繼D存在這樣的線性表，即表中沒有任何結(jié)點20在 B 的運算中，使用順序表比鏈表好。

19、A插入 B根據(jù)序號查找 C刪除 D根據(jù)元素查找ListNode *Demo1(LinkList L,ListNode *p) / L是有頭結(jié)點的單鏈表ListNode *q=L-next;While (q & q-next!=p)q=q-next;if (q)return q;elseError(“*p not in L); 四分析下述算法的功能1void Demo2(ListNode *p,ListNode *q) / p,*q是鏈表中的兩個結(jié)點DataType temp;temp=p-data;p-data=q-data;q-data=temp;2解：1返回結(jié)點*p的直接前趨結(jié)點地址。2交

20、換結(jié)點*p和結(jié)點*qp和q的值不變。五程序填空1線性表中的元素是無序的，并以帶表頭結(jié)點的單鏈表作存儲。試寫一算法，刪除表中所有大于min，小于max的元素，試完成如下程序填空。Void delete (lklist head; datatype min, max) q=head-next; while (p!=NULL) if (p-datadata=max ) q=p; p= p-next ; else q-next= p-next ;delete (p) ;p= q-next ; 2在帶頭結(jié)點head的單鏈表的結(jié)點a之后插入新元素x，試完成如下程序填空。struct node elemty

21、pe data; node *next;void lkinsert (node *head, elemtype x) node *s, *p;s= new node ;s-data= x ; p=head-next;while (p!=NULL) & ( p-data!=a )_p=p-next ;if (p=NULL)coutnext=p-next_;_ p-next=s _;六算法設(shè)計題1寫一個對單循環(huán)鏈表進展遍歷打印每個結(jié)點的值的算法，鏈表中任意結(jié)點的地址為P 。解：void Show(ListNode *P) ListNode *t=P; do printf(%c,t-data); t

22、=t-rear; while (t!=P);（2） 對給定的帶頭結(jié)點的單鏈表L，編寫一個刪除L中值為x的結(jié)點的直接前趨結(jié)點的算法。解：void delete(ListNode *L)ListNode *p=L,*q;if(L-next-data=X)printf(“值為x的結(jié)點是第一個結(jié)點，沒有直接前趨結(jié)點可以刪除);return;For(p-next-data!=X;q=p;p=p-next);/ 刪除指針p所指向的結(jié)點q-next=p-next;delete p;（3） 一個單向鏈表，編寫一個函數(shù)從單鏈表中刪除自第i個結(jié)點起的k個結(jié)點。解：void Del(node *head,int i

23、,int k) node *p,*q;int j;if(i=1)for(j=1;jnext;delete p;else p=head; for(j=1;jnext; / p指向要刪除的結(jié)點的前一個結(jié)點 for(j=1;jnext; / q 指向要刪除的結(jié)點 p-next=q-next; delete q;（4） 有一個單向鏈表不同結(jié)點的數(shù)據(jù)域值可能一樣，其頭指針為head，編寫一個函數(shù)計算值域為x的結(jié)點個數(shù)。解：/此題是遍歷單鏈表的每個結(jié)點，每遇到一個結(jié)點，結(jié)點個數(shù)加1，結(jié)點個數(shù)存儲在變量n中。實現(xiàn)此題功能的函數(shù)如下：int counter(head)node *head； node *p;i

24、nt n=0; p=head； while(p!=NULL) if(p-data=x)n+；p=p-next; return(n);5有兩個循環(huán)單向鏈表，鏈頭指針分別為head1和head2，編寫一個函數(shù)將鏈表head1到鏈表head2，后的鏈表仍是循環(huán)鏈表。解：/此題的算法思想是：先找到兩鏈表的尾指針，將第一個鏈表的尾指針與第二個鏈表的頭結(jié)點起來，使之成為循環(huán)的。函數(shù)如下：node *link (node *head1, *head2) node *p,*q;p=head1;while(p-next!=head1) p=p-next;q=head2;while(q-next!=head2)

25、q=q-next;p-next=head2;q-next=head1;return (head1);單元練習(xí)3一判斷題如下各題，正確的請在前面的括號打；錯誤的打1棧是運算受限制的線性表。2在?？盏那闆r下，不能作出棧操作，否如此產(chǎn)生下溢出。3棧一定是順序存儲的線性結(jié)構(gòu)。4棧的特點是“后進先出。5空棧就是所有元素都為0的棧。6在C或C+語言中設(shè)順序棧的長度為MAXLEN，如此top=MAXLEN時表示隊滿。7鏈棧與順序棧相比，其特點之一是通常不會出現(xiàn)棧滿的情況。8一個棧的輸入序列為：A，B，C，D，可以得到輸出序列：C，A，B，D。9遞歸定義就是循環(huán)定義。10將十進制數(shù)轉(zhuǎn)換為二進制數(shù)是棧的典型應(yīng)用

26、之一。二填空題1在棧結(jié)構(gòu)中，允許插入、刪除的一端稱為棧頂。2在順序棧中，當棧頂指針top=-1時，表示?？?。3在有n個元素的棧中，進棧操作的時間復(fù)雜度為 O1。4在棧中，出棧操作的時間復(fù)雜度為： O(1) 。5表達式，求它的后綴表達式是棧的典型應(yīng)用。6在一個鏈棧中，假如棧頂指針等于NULL，如此表示?？?。7向一個棧頂指針為top的鏈棧插入一個新結(jié)點*p時，應(yīng)執(zhí)行 p-next=top；和top=p；操作。8順序棧S存儲在數(shù)組 S-data0.MAXLEN-1中，進棧操作時要執(zhí)行的語句有：S-top + ?；? S-top+19鏈棧LS，指向棧頂元素的指針是 LS-next 。10從一個棧刪除元

27、素時，首先取出棧頂元素，然后再移動棧頂指針。11由于鏈棧的操作只在鏈表的頭部進展，所以沒有必要設(shè)置頭結(jié)點。12順序棧S，在對S進展進棧操作之前首先要判斷棧是否滿。13順序棧S，在對S進展出棧操作之前首先要判斷棧是否空。14假如存空間充足，鏈?？梢圆欢x棧滿運算。15鏈棧LS是空的條件是 LS-next=NULL 。16鏈棧LS的棧頂元素是鏈表的首元素。17同一棧的各元素的類型一樣。18假如進棧的次序是A、B、C、D、E，執(zhí)行三次出棧操作以后，棧頂元素為 B 。19A+B/C-D*E的后綴表達式是： ABC/+DE*- 。20四個元素按A、B、C、D順序進S棧，執(zhí)行兩次PopS，x運算后，x的值

28、是 C 。三選擇題1插入和刪除只能在一端進展的線性表，稱為( C )。 A隊列 B循環(huán)隊列 C棧 D循環(huán)棧2設(shè)有編號為1，2，3，4的四輛列車，順序進入一個棧結(jié)構(gòu)的站臺，如下不可能的出站順序為 ( D ) A1234 B1243 C1324 D14233如果以鏈表作為棧的存儲結(jié)構(gòu)，如此出棧操作時 B A必須判別棧是否滿 B必須判別棧是否空 C必須判別棧元素類型 D隊?？刹蛔鋈魏闻袆e4元素A,B,C,D依次進棧以后，棧頂元素是 D AA BB CC DD5順序棧存儲空間的實現(xiàn)使用 B 存儲棧元素。 A鏈表 B數(shù)組 C循環(huán)鏈表 D變量6在C或C+語言中，一個順序棧一旦被聲明，其占用空間的大小 A

29、。 A已固定 B不固定 C可以改變 D動態(tài)變化7帶頭結(jié)點的鏈棧LS的示意圖如下，棧頂元素是 A LSHABCD AA BB CC DD8鏈棧與順序棧相比，有一個比擬明顯的優(yōu)點是 B 。A插入操作更加方便 B通常不會出現(xiàn)棧滿的情況。C不會出現(xiàn)棧空的情況 D刪除操作根加方便9從一個棧頂指針為top的鏈棧中刪除一個結(jié)點時，用x保存被刪除的結(jié)點，應(yīng)執(zhí)行如下 ( D )命令。 Ax=top;top=top-next; Btop=top-next;x=top-data; Cx=top-data; Dx=top-data;top=top-next;10在一個棧頂指針為HS的鏈棧中，將一個S指針所指的結(jié)點入棧

30、，應(yīng)執(zhí)行如下 ( B )命令。 AHS-next=S; BS-next=HS-next;HS-next=S; CS-next=HS-next;HS=S; DS-next=HS;HS=HS-next;11四個元素按A、B、C、D順序進S棧，執(zhí)行兩次PopS，x運算后，棧頂元素的值是 B 。 AA BB CC DD12元素A,B,C,D依次進棧以后，棧底元素是 A 。 AA BB CC DD13經(jīng)過如下棧的運算后，再執(zhí)行ReadTop(s)的值是 A 。 InitStack(s)初始化棧;Push(s,a);Push(s,b); Pop(s)Aa Bb C1 D014經(jīng)過如下棧的運算后，x的值是

31、B 。 InitStack(s)初始化棧;Push(s,a);Push(s,b); ReadTop(s);Pop(s,x);Aa Bb C1 D015經(jīng)過如下棧的運算后，x的值是 B 。 InitStack(s)初始化棧;Push(s,a);Pop(s,x);Push(s,b);Pop(s,x);Aa Bb C1 D016經(jīng)過如下棧的運算后，SEmpty(s)的值是 C 。 InitStack(s)初始化棧; Push(s,a); Push(s,b);Pop(s,x); Pop(s,x);Aa Bb C1 D017向順序棧中壓入元素時， B 。A 先存入元素，后移動棧頂指針 B先移動棧頂指針，

32、后存入元素C誰先誰后無關(guān)緊要 D同時進展18初始化一個空間大小為5的順序棧S后，S-top的值是 B 。 A0 B-1 C不再改變 D動態(tài)變化19一個棧的入棧次序ABCDE，如此棧的不可能的輸出序列是 ( C )。 AEDCBA BDECBA CDCEAB DABCDE20設(shè)有一個順序棧S，元素A,B,C,D,E,F,依次進棧，如果六個元素出棧的順序是B，D，C，F(xiàn)，E，A，如此棧的容量至少應(yīng)是 ( A )。 A3 B4 C5 D 6四應(yīng)用題1設(shè)有一個棧，元素進棧的次序為：A，B，C，D，E，用I表示進棧操作，O表示出棧操作，寫出如下出棧的操作序列。C，B，A，D，E A，C，B，E，D解：I

33、IIOOOIOIOIOIIOOIIOO（2） 求后綴表達式 ABC/D解：A B C D / -A+B*C+D/E解：0 A B C * + D E / + A*(B+C)*D-E解：A B C + * D * E - (A+B)*C-E/(F+G/H)-D解：A B + C * E F G H / + / - D - 8/(5+2)-6解：8 5 2 + / 6 -六算法設(shè)計題1設(shè)用一維數(shù)組stackn表示一個堆棧，假如堆棧中每個元素需占用M個數(shù)組單元M1。試寫出其入棧操作的算法。試寫出其出棧操作的算法。解：/用一整型變量top表示棧頂指針，top為0時表示棧為空。棧中元素從S 1開始存放元

34、素。/入棧算法：void push (char x) if (top+M)MAXLEN-1) printf (“堆棧溢出！); else if (top= =0) top+; S top=x; else top=top+M; S top=x; /出棧算法： void pop (char x) if (top= =0) printf (“堆棧為空棧！); else if (top= =1) x= S top; top; else x= S top; top=topM; 2設(shè)計一個算法，要求判別一個算術(shù)表達式中的圓括號配對是否正確。解：/設(shè)表達式在字符數(shù)組a 中，使用一堆棧S來幫助判斷。 int

35、correct (char a ) stack s ; InitStack (s); /調(diào)用初始化棧函數(shù) for (i=0; i strlen(a);i+) if (ai= =() Push (s,(); elseif (ai= =) if StackEmpty (s) /調(diào)用判?？蘸瘮?shù) return 0; /假如棧為空返回0；否如此出棧 else Pop(s); if (StackEmpty (s) ) /調(diào)用判棧空函數(shù) printf (“配對正確！); /假如棧空，說明配對正確，并返回1 else printf (“配對錯誤！); /配對錯誤返回0 （3） 設(shè)計一個將十進正整數(shù)轉(zhuǎn)換為十進制

36、數(shù)的算法，并要求上機調(diào)試通過。解： #include #includetypedef struct stacknode /定義棧的存儲結(jié)構(gòu) int data;struct stacknode *next;stacknode;typedef struct stacknode *top; /定義棧頂?shù)闹羔榣inkstack;void Conversion(int n) /棧的應(yīng)用：十十六進制轉(zhuǎn)換 linkstack s;int x; s.top=NULL; /置?？誨o x=n%16; /取余數(shù)n= n/16 ; /取新的商stacknode *p=new stacknode; /申請新結(jié)點p-n

37、ext=s.top ; /修改棧頂指針s.top=p;s.top-data=x; /余數(shù)入棧while(n); printf(ntt轉(zhuǎn)換后的十六進制數(shù)值為：;while (s.top) /出棧處理if(s.top-datadata); else switch(s.top-data) case 10: printf(%c,A);break;case 11: printf(%c,B);break;case 12: printf(%c,C);break;case 13: printf(%c,D);break;case 14: printf(%c,E);break;case 15: printf(%c

38、,F);break; stacknode *p=s.top;s.top=s.top-next;free(p) ; /出棧一個余數(shù)，收回一個結(jié)printf(nn);void main() int n; printf(ntt請輸入一個十進制正整數(shù)：);scanf(%d,&n);Conversion(n);單元練習(xí)4一判斷題如下各題，正確的請在前面的括號打；錯誤的打1隊列是限制在兩端進展操作的線性表。2判斷順序隊列為空的標準是頭指針和尾指針都指向同一個結(jié)點。3在鏈隊列上做出隊操作時，會改變front指針的值。4在循環(huán)隊列中，假如尾指針rear大于頭指針front，其元素個數(shù)為rear- front。

39、5在單向循環(huán)鏈表中，假如頭指針為h，那么p所指結(jié)點為尾結(jié)點的條件是p=h。6鏈隊列在一定圍不會出現(xiàn)隊滿的情況。7在循環(huán)鏈隊列中無溢出現(xiàn)象。8棧和隊列都是順序存儲的線性結(jié)構(gòu)。9在隊列中允許刪除的一端稱為隊尾。10順序隊和循環(huán)隊關(guān)于隊滿和隊空的判斷條件是一樣的。二填空題（1） 在隊列中存取數(shù)據(jù)應(yīng)遵循的原如此是先進先出。（2） 隊列是被限定為只能在表的一端進展插入運算，在表的另一端進展刪除運算的線性表。（3） 在隊列中，允許插入的一端稱為隊尾。（4） 在隊列中，允許刪除的一端稱為隊首或隊頭。（5） 隊列在進展出隊操作時，首先要判斷隊列是否為空。（6） 順序隊列在進展入隊操作時，首先要判斷隊列是否為滿

40、。（7） 順序隊列初始化后，front=rear= -1 。（8） 解決順序隊列“假溢出的方法是采用循環(huán)隊列。（9） 循環(huán)隊列的隊首指針為front，隊尾指針為rear，如此隊空的條件為 front = rear 。（10） 鏈隊列LQ為空時，LQ-front-next= NULL 。（11） 設(shè)長度為n的鏈隊列用單循環(huán)鏈表表示，假如只設(shè)頭指針，如此入隊操作的時間復(fù)雜度為 On。（12） 設(shè)長度為n的鏈隊列用單循環(huán)鏈表表示，假如只設(shè)尾指針，如此出隊操作的時間復(fù)雜度為 01。（13） 在一個鏈隊列中，假如隊首指針與隊尾指針的值一樣，如此表示該隊列為空。（14） 設(shè)循環(huán)隊列的頭指針front指向隊

41、首元素，尾指針rear指向隊尾元素后的一個空閑元素，隊列的最大空間為MAXLEN，如此隊滿標志為： front=(rear+1)%MAXLEN 。（15） 在一個鏈隊列中，假如隊首指針為front，隊尾指針為rear，如此判斷該隊列只有一個結(jié)點的條件為： front=rear & front !NULL 。(或 front=rear & front NULL )（16） 向一個循環(huán)隊列中插入元素時，首先要判斷隊尾指針，然后再向指針所指的位置寫入新的數(shù)據(jù)。（17） 讀隊首元素的操作不改變或不影響隊列元素的個數(shù)。18設(shè)循環(huán)隊列的容量為40序號從0到39，現(xiàn)經(jīng)過一系列的入隊和出隊運算后，有 fron

42、t=11，rear=19，如此循環(huán)隊列中還有 8 個元素。L= (Nrearfront)% N=401911% 40=819隊列Q，經(jīng)過如下運算：InitQueue(Q)(初始化隊列);InQueue(Q,a); InQueue(Q,b);OutQueue(Q,x); ReadFront(Q,x);QEmpty(Q);后的值是0 。20隊列Q經(jīng)過InitQueue(Q)(初始化隊列);InQueue(Q,a);InQueue(Q,b); ReadFront(Q,x)后，x的值是 a 。三選擇題1隊列是限定在 D 進展操作的線性表。 A中間 B隊首 C隊尾 D端點2隊列中的元素個數(shù)是( B )。

43、 A不變的 B可變的 C任意的 D03同一隊列各元素的類型( A )。 A必須一致 B不能一致 C可以不一致 D不限制4隊列是一個( C )線性表結(jié)構(gòu)。 A不加限制的 B推廣了的 C加了限制的 D非5當利用大小為n的數(shù)組順序存儲一個隊列時，該隊列的最后一個元素的下標為 B 。 An-2 Bn-1 Cn Dn+16一個循環(huán)隊列一旦說明，其占用空間的大小 A 。 A已固定 B可以變動 C不能固定 D動態(tài)變化7循環(huán)隊列占用的空間( A )。 A必須連續(xù) B不必連續(xù) C不能連續(xù) D可以不連續(xù)8存放循環(huán)隊列元素的數(shù)組data有10個元素，如此data數(shù)組的下標圍是( B )。 A0.10 B0.9 C1

44、.9 D1.109假如進隊的序列為：A，B，C，D，如此出隊的序列是 C 。 AB，C，D，A BA，C，B，D CA，B，C，D DC，B，D，A10四個元素按：A，B，C，D順序連續(xù)進隊Q，如此隊尾元素是 D 。 A AB B C CD D11四個元素按：A，B，C，D順序連續(xù)進隊Q，執(zhí)行一次OutQueue(Q)操作后，隊頭元素是 B 。 A AB B C C D D12四個元素按：A，B，C，D順序連續(xù)進隊Q，執(zhí)行四次OutQueue(Q)操作后，再執(zhí)行QEmpty(Q);后的值是 B 。 A 0B 1 C 2 D 313隊列Q，經(jīng)過如下運算后，x 的值是 B 。 InitQueue(

45、Q)(初始化隊列);InQueue(Q,a); InQueue(Q,b);OutQueue(Q,x); ReadFront (Q,x);Aa Bb C0 D114循環(huán)隊列SQ隊滿的條件是( B )。 ASQ-rear=SQ-front B(SQ-rear+1)% MAXLEN =SQ-frontCSQ-rear=0 DSQ-front=015設(shè)鏈棧中結(jié)點的結(jié)構(gòu)：data為數(shù)據(jù)域，next為指針域，且top是棧頂指針。假如想在鏈棧的棧頂插入一個由指針s所指的結(jié)點，如此應(yīng)執(zhí)行如下 A 操作。 As-next=top-next；top-next=s； Btop-next=s； Cs-next=top；top=top-next； Ds-next=top；top=s；16帶頭結(jié)點的鏈隊列LQ示意圖如下，鏈隊列的隊頭元素是 A LQ-frontHABCDLQ-rearAA BB CC DD17帶頭結(jié)點的鏈隊列LQ示意圖如下，指向鏈隊列的隊頭指針是 C LQ