《大數(shù)據(jù)結構》課后參考問題詳解

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

1、word 單元練習1 一．判斷題〔如下各題，正確的請在前面的括號打√；錯誤的打╳〕 〔√〕〔1〕數(shù)據(jù)的邏輯結構與數(shù)據(jù)元素本身的容和形式無關。 〔√〕〔2〕一個數(shù)據(jù)結構是由一個邏輯結構和這個邏輯結構上的一個根本運算集構成的整體。 〔ㄨ〕〔3〕數(shù)據(jù)元素是數(shù)據(jù)的最小單位。 〔ㄨ〕〔4〕數(shù)據(jù)的邏輯結構和數(shù)據(jù)的存儲結構是一樣的。 〔ㄨ〕〔5〕程序和算法原如此上沒有區(qū)別，所以在討論數(shù)據(jù)結構時可以通用。 〔√〕〔6〕從邏輯關系上講，數(shù)據(jù)結構主要分為線性結構和非線性結構兩類。 〔√〕〔7〕數(shù)據(jù)的存儲結構是數(shù)據(jù)的邏輯結構的存儲映像。 〔√〕〔8〕數(shù)據(jù)的物理結構是指數(shù)據(jù)在計算機實際的存儲形

2、式。 〔ㄨ〕〔9〕數(shù)據(jù)的邏輯結構是依賴于計算機的。 〔√〕〔10〕算法是對解題方法和步驟的描述。 二．填空題 （1） 數(shù)據(jù)有邏輯結構和存儲結構兩種結構。 （2） 數(shù)據(jù)邏輯結構除了集合以外，還包括：線性結構、樹形結構和圖形結構。 （3） 數(shù)據(jù)結構按邏輯結構可分為兩大類，它們是線性結構和非線性結構。 （4） 樹形結構和圖形結構合稱為非線性結構。 （5） 在樹形結構中，除了樹根結點以外，其余每個結點只有1個前趨結點。 （6） 在圖形結構中，每個結點的前趨結點數(shù)和后續(xù)結點數(shù)可以任意多個。 （7） 數(shù)據(jù)的存儲結構又叫物理結構。 （8） 數(shù)據(jù)的存儲結構形式包括：順序存儲、鏈式存儲

3、、索引存儲和散列存儲。 （9） 線性結構中的元素之間存在一對一的關系。 （10） 樹形結構結構中的元素之間存在一對多的關系， （11） 圖形結構的元素之間存在多對多的關系。 （12） 數(shù)據(jù)結構主要研究數(shù)據(jù)的邏輯結構、存儲結構和算法〔或運算〕三個方面的容。 （13） 數(shù)據(jù)結構被定義為(D，R)，其中D是數(shù)據(jù)的有限集合，R是D上的關系的有限集合。 （14） 算法是一個有窮指令的集合。 （15） 算法效率的度量可以分為事先估算法和事后統(tǒng)計法。 （16） 一個算法的時間復雜性是算法輸入規(guī)模的函數(shù)。 （17） 算法的空間復雜度是指該算法所消耗的存儲空間，它是該算法求解問題規(guī)模n的函數(shù)。

4、 （18） 假如一個算法中的語句頻度之和為T〔n〕=6n+3nlog2n，如此算法的時間復雜度為 O〔nlog2n〕。 （19） 假如一個算法中的語句頻度之和為T〔n〕=3n+nlog2n+n2，如此算法的時間復雜度為 O〔n2〕。 〔20〕數(shù)據(jù)結構是一門研究非數(shù)值計算的程序設計問題中計算機的操作對象，以與它們之間的關系和運算的學科。 三．選擇題 〔1〕數(shù)據(jù)結構通常是研究數(shù)據(jù)的〔 A 〕與它們之間的相互聯(lián)系。 A. 存儲結構和邏輯結構 B. 存儲和抽象 C. 聯(lián)系和抽象 D. 聯(lián)系與邏輯 〔2〕在邏輯上可以把數(shù)據(jù)結構分成：〔 C 〕。

5、 A. 動態(tài)結構和靜態(tài)結構 B. 緊湊結構和非緊湊結構 C. 線性結構和非線性結構 D. 部結構和外部結構 〔3〕數(shù)據(jù)在計算機存儲器表示時，物理地址和邏輯地址一樣并且是連續(xù)的，稱之為〔 C 〕。 A. 存儲結構 B. 邏輯結構 C. 順序存儲結構 D. 鏈式存儲結構 〔4〕非線性結構中的每個結點〔 D 〕。 A. 無直接前趨結點 B. 無直接后繼結點 C. 只有一個直接前趨結點和一個直接后繼結點 D. 可能有多個直接前趨結點和多個直接

6、后繼結點 〔5〕鏈式存儲的存儲結構所占存儲空間〔 A 〕。 A．分兩局部，一局部存放結點的值，另一局部存放表示結點間關系的指針 B．只有一局部，存放結點的值 C．只有一局部，存儲表示結點間關系的指針 D．分兩局部，一局部存放結點的值，另一局部存放結點所占單元素 〔6〕算法的計算量大小稱為算法的〔 C 〕。 A. 現(xiàn)實性 B. 難度 C. 時間復雜性 D. 效率 〔7〕數(shù)據(jù)的根本單位是〔 B 〕。 A. 數(shù)據(jù)結構 B. 數(shù)據(jù)元素

7、 C. 數(shù)據(jù)項 D. 文件 〔8〕每個結點只含有一個數(shù)據(jù)元素，所有存儲結點相繼存放在一個連續(xù)的存儲區(qū)里，這種存儲結構稱為〔 A 〕結構。 A. 順序存儲 B. 鏈式存儲 C. 索引存儲 D. 散列存儲 〔9〕每一個存儲結點不僅含有一個數(shù)據(jù)元素，還包含一組指針，該存儲方式是〔 B 〕存儲方式。 A. 順序 B. 鏈式 C. 索引 D. 散列 〔10〕以下任何兩個結點之間都沒有邏輯關系的是〔 D 〕。 A

8、. 圖形結構 B. 線性結構 C. 樹形結構 D. 集合 〔11〕在數(shù)據(jù)結構中，與所使用的計算機無關的是〔 C 〕。 A. 物理結構 B. 存儲結構 C. 邏輯結構 D. 邏輯和存儲結構 〔12〕如下四種根本邏輯結構中，數(shù)據(jù)元素之間關系最弱的是〔 A 〕。 A. 集合 B. 線性結構 C. 樹形結構 D. 圖形結構 〔13〕與數(shù)據(jù)元素本身的形式、容、相對位置、個數(shù)無關的是數(shù)據(jù)的〔 A 〕。

9、 A. 邏輯結構 B. 存儲結構 C. 邏輯實現(xiàn) D. 存儲實現(xiàn) 〔14〕每一個存儲結點只含有一個數(shù)據(jù)元素，存儲結點存放在連續(xù)的存儲空間，另外有一組指明結點存儲位置的表，該存儲方式是〔 C 〕存儲方式。 A. 順序 B. 鏈式 C. 索引 D. 散列 〔15〕算法能正確的實現(xiàn)預定功能的特性稱為算法的〔 A 〕。 A. 正確性 B. 易讀性 C. 健壯性 D.

10、高效性 〔16〕算法在發(fā)生非法操作時可以作出處理的特性稱為算法的〔 C 〕。 A. 正確性 B. 易讀性 C. 健壯性 D. 高效性 〔17〕如下時間復雜度中最壞的是〔 D 〕。 A. O〔1〕 B. O〔 n〕 C. O〔log2n〕 D. O〔n2〕 〔18〕如下算法的時間復雜度是〔 D 〕。 for (i=0;i

11、i][j]=i+j; A. O〔1〕 B. O〔 n〕 C. O〔log2n〕 D. O〔n2〕 〔19〕算法分析的兩個主要方面是〔 A 〕。 A. 空間復雜性和時間復雜性 B. 正確性和簡明性 C. 可讀性和文檔性 D. 數(shù)據(jù)復雜性和程序復雜性 〔20〕計算機算法必須具備輸入、輸出和〔 C 〕。 A. 計算方法 B. 排序方法 C. 解決問題的有限運算步驟 D. 程序設計方法

12、 四．分析下面各程序段的時間復雜度 （1） for (i=0;i

13、++) { 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ù)二元組關系，畫出對應邏輯圖形的草圖，指出它們屬于何種數(shù)據(jù)結構。 〔1〕A=〔D，R〕，其中： D={a，b，c，d，e}， R={ } 解： a b c d e 屬于集合 〔2〕

14、B=〔D,R〕，其中： D={a,b,c,d,e,f}，R={r} R={,,,,} 〔尖括號表示結點之間關系是有向的〕 解： 屬于線性結構。 〔3〕F=〔D,R〕，其中： D={50,25,64,57,82,36,75,55}，R={r} R={<50,25>,<50,64>,<25,36>,<64,57>,<64,82>,<57,55>,<57,75>} 解： 屬于樹結構 〔4〕C=〔D,R〕，其中： D={1,2,3,4,5,6}，R={r} R={(1,2),(2,

15、3),(2,4),(3,4),(3,5),(3,6),(4,5),(4,6)}〔園括號表示結點之間關系是有向的〕 解： 屬于圖結構 〔5〕E=〔D,R〕，其中： D={a,b,c,d,e,f,g,h}，R={r} R={,,,,,,} 解： c 屬于樹結構。單元練習2 一．判斷題〔如下各題，正確的請在前面的括號打√；錯誤的打╳〕 〔×〕〔1〕線性表的鏈式存儲結構優(yōu)于順序存儲。 〔×〕〔2〕鏈表的每個結點都恰好包含一個指針域。 〔√〕〔

16、3〕在線性表的鏈式存儲結構中，邏輯上相鄰的兩個元素在物理位置上并不一定緊鄰。 〔×〕〔4〕順序存儲方式的優(yōu)點是存儲密度大，插入、刪除效率高。 〔×〕〔5〕線性鏈表的刪除算法簡單，因為當刪除鏈中某個結點后，計算機會自動地將后續(xù)的各個單元向前移動。 〔×〕〔6〕順序表的每個結點只能是一個簡單類型，而鏈表的每個結點可以是一個復雜類型。 〔√〕〔7〕線性表鏈式存儲的特點是可以用一組任意的存儲單元存儲表中的數(shù)據(jù)元素。 〔√〕〔8〕線性表采用順序存儲，必須占用一片連續(xù)的存儲單元。 〔×〕〔9〕順序表結構適宜于進展順序存取，而鏈表適宜于進展隨機存取。 〔ㄨ〕〔10〕插入和刪除操作是數(shù)據(jù)結構中最

17、根本的兩種操作，所以這兩種操作在數(shù)組中也經(jīng)常使用。 二．填空題 （1） 順序表中邏輯上相鄰的元素在物理位置上必須相連。 （2） 線性表中結點的集合是有限的，結點間的關系是一對一關系。 （3） 順序表相對于鏈表的優(yōu)點是：節(jié)省存儲和隨機存取。 （4） 鏈表相對于順序表的優(yōu)點是：插入、刪除方便。 〔5〕采用順序存儲結構的線性表叫順序表。 〔6〕順序表中訪問任意一個結點的時間復雜度均為 O(1) 。 〔7〕鏈表相對于順序表的優(yōu)點是插入、刪除方便；缺點是存儲密度小。 〔8〕在雙鏈表中要刪除結點*P，其時間復雜度為 O(1) 。 〔9〕在單鏈表中要在結點*P之

18、前插入一個新結點，需找到*P的直接前趨結點的地址，其查找的時間復雜度為 O(n) 。 （10） 單鏈表中需知道頭指針才能遍歷整個鏈表。 （11） 性表中第一個結點沒有直接前趨，稱為開始結點。 （12） 在一個長度為n的順序表中刪除第i個元素，要移動 n-i 個元素。 （13） 在一個長度為n的順序表中，如果要在第i個元素前插入一個元素，要后移 n- i +1 個元素。 （14） 在無頭結點的單鏈表中，第一個結點的地址存放在頭指針中，而其它結點的存儲地址存放在前趨結點的指針域中。 （15） 當線性表的元素總數(shù)根本穩(wěn)定，且很少進展插入和刪除操作，但要求以最快速度存取

19、線性表中的元素時，應采用順序存儲結構。 （16） 在線性表的鏈式存儲中，元素之間的邏輯關系是通過指針決定的。 （17） 在雙向鏈表中，每個結點都有兩個指針域，它們一個指向其前趨結點，另一個指向其后繼結點。 （18） 對一個需要經(jīng)常進展插入和刪除操作的線性表，采用鏈式存儲結構為宜。 （19） 雙鏈表中，設p是指向其中待刪除的結點，如此需要執(zhí)行的操作為： p->prior->next=p->next 。 （20） 在如下列圖的鏈表中，假如在指針P所在的結點之后插入數(shù)據(jù)域值為a和b的兩個結點，如此可用如下兩個語句： S->next->next=P->next;和P->next=S;來實

20、現(xiàn)該操作。 P Λ a b S 三．選擇題 〔1〕在具有n個結點的單鏈表中，實現(xiàn)〔 A 〕的操作，其算法的時間復雜度都是O〔n〕。 A．遍歷鏈表或求鏈表的第i個結點 B．在地址為P的結點之后插入一個結點 C．刪除開始結點 D．刪除地址為P的結點的后繼結點 〔2〕設a、b、c為三個結點，p、10、20分別代表它們的地址，如此如下的存儲結構稱為〔 B 〕。 A． 循環(huán)鏈表 B．單鏈表

21、 C．雙向循環(huán)鏈表 D．雙向鏈表 〔3〕單鏈表的存儲密度〔 C 〕。 A．大于1 B．等于1 C．小于1 D．不能確定 〔4〕一個順序存儲的線性表，設每個結點占m個存儲單元，假如第一個結點的地址為B，如此第i個結點的地址為〔 A 〕。 A． B+(i-1)*m B．B+i*m C． B-i*m D． B+(i+1)*m 〔5〕在有n個結點的順序表上做插入、刪除結點運算的時間復雜度為〔 B 〕。 A．O〔1〕 B．O〔n〕C．O〔n2〕

22、 D．O〔log2n〕 〔6〕設Llink、Rlink分別為循環(huán)雙鏈表結點的左指針和右指針，如此指針P所指的元素是雙循環(huán)鏈表L的尾元素的條件是〔 D 〕。 A．P== L B．P->Llink== L C．P== NULL D．P->Rlink==L 〔7〕兩個指針P和Q，分別指向單鏈表的兩個元素，P所指元素是Q所指元素前驅的條件是〔 B 〕。 A．P->next==Q->next B．P->next== Q C．Q->next== P D．P== Q 〔8〕用鏈表存儲的線性表，其優(yōu)點是〔 C 〕

23、。 A．便于隨機存取B．花費的存儲空間比順序表少 C．便于插入和刪除 D．數(shù)據(jù)元素的物理順序與邏輯順序一樣 〔9〕在單鏈表中，增加頭結點的目的是〔 C 〕。 A．使單鏈表至少有一個結點B．標志表中首結點的位置 C．方便運算的實現(xiàn) D．說明該單鏈表是線性表的鏈式存儲結構 〔10〕下面關于線性表的表示中，錯誤的答案是〔 D 〕關系。 A．順序表必須占一片地址連續(xù)的存儲單元 B．順序表可以隨機存取任一元素 C．鏈表不必占用一片地址連續(xù)的存儲單元 D．鏈表可以隨機存取任一元素

24、〔11〕L是線性表，LengthList〔L〕的值是5，經(jīng)DelList〔L，2〕運算后，LengthList〔L〕的值是〔 C 〕。 A．2 B．3 C．4 D．5 〔12〕單鏈表的示意圖如下： L A B C D Λ Q R P 指向鏈表Q結點的前趨的指針是〔 B 〕。 A．L B．P C．Q D．R 〔13〕設p為指向單循環(huán)鏈表上某結點的指針，如此*p

25、的直接前驅〔 C 〕。 A．找不到 B．查找時間復雜度為O〔1〕 C．查找時間復雜度為O〔n〕 D．查找結點的次數(shù)約為n 〔14〕等概率情況下，在有n個結點的順序表上做插入結點運算，需平均移動結點的數(shù)目為〔 C 〕。 A．n B．(n-1)/2 C． n/2 D．(n+1)/2 〔15〕在如下鏈表中不能從當前結點出發(fā)訪問到其余各結點的是〔 C 〕。 A．雙向鏈表 B．單循環(huán)鏈表 C．單鏈表 D．雙向循環(huán)鏈表 〔16〕在順序表中，只要

26、知道〔 D 〕，就可以求出任一結點的存儲地址。 A．基地址 B．結點大小 C．向量大小 D．基地址和結點大小 〔17〕在雙鏈表中做插入運算的時間復雜度為〔 A 〕。 A．O〔1〕 B．O〔n〕 C．O〔n2〕 D．O〔log2n〕 〔18〕鏈表不具備的特點是〔 A 〕。 A．隨機訪問 B．不必事先估計存儲空間 C．插入刪除時不需移動元素 D．所需空間與線性表成正比 〔19〕以下關于線性表的論述，不

27、正確的為〔 C 〕。 A．線性表中的元素可以是數(shù)字、字符、記錄等不同類型 B．線性順序表中包含的元素個數(shù)不是任意的 C．線性表中的每個結點都有且僅有一個直接前趨和一個直接后繼 D．存在這樣的線性表，即表中沒有任何結點 〔20〕在〔 B 〕的運算中，使用順序表比鏈表好。 A．插入 B．根據(jù)序號查找 C．刪除 D．根據(jù)元素查找 ListNode *Demo1(LinkList L,ListNode *p) { // L是有頭結點的單鏈表 ListNode *q=L->next; While (q && q

28、->next!=p) q=q->next; if (q) return q; else Error(“*p not in L〞); } 四．分析下述算法的功能 〔1〕 void Demo2(ListNode *p,ListNode *q) { // p,*q是鏈表中的兩個結點 DataType temp; temp=p->data; p->data=q->data; q->data=temp; } 〔2〕

29、 解： 〔1〕返回結點*p的直接前趨結點地址。 〔2〕交換結點*p和結點*q〔p和q的值不變〕。 五．程序填空 〔1〕線性表中的元素是無序的，并以帶表頭結點的單鏈表作存儲。試寫一算法，刪除表中所有大于min，小于max的元素，試完成如下程序填空。 Void delete (lklist head; datatype min, max) { q=head->next; while (p!=NULL) { if ((p->data<=min ) | | ( p->data>=max ) {q=p; p= p->next

30、 ; } else { q->next= p->next ; delete (p) ; p= q->next ; } } } 〔2〕在帶頭結點head的單鏈表的結點a之后插入新元素x，試完成如下程序填空。 struct node { elemtype data; node *next; }; void lkinsert (node *head, elemtype x) { node *s, *p; s= new node ; s->data= x ; p=head->next; while (p!=NULL) &&

31、 ( p->data!=a ) ____p=p->next ; if (p==NULL) cout<< " 不存在結點a! "; else {_____s->next=p->next______; ___ p->next=s __________; } } 六．算法設計題 〔1〕寫一個對單循環(huán)鏈表進展遍歷〔打印每個結點的值〕的算法，鏈表中任意結點的地址為P 。 解： void Show(ListNode *P) { ListNode *t=P; do { printf("%c",t->data); t=t->rear; }

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

33、自第i個結點起的k個結點。 解： void Del(node *head,int i,int k) { node *p,*q; int j; if(i==1) for(j=1;j<=k;j++) // 刪除前k個元素 { p=head; // p指向要刪除的結點 head=head->next; delete p; } else { p=head; for(j=1;j<=i-2;j++) p=p->next; // p指向要刪除的結點的前一個結點

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

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

36、t; q=head2; while(q->next!=head2) q=q->next; p->next=head2; q->next=head1; return (head1); } 單元練習3 一．判斷題〔如下各題，正確的請在前面的括號打√；錯誤的打╳〕 〔√〕〔1〕棧是運算受限制的線性表。 〔√〕〔2〕在棧空的情況下，不能作出棧操作，否如此產(chǎn)生下溢出。 〔ㄨ〕〔3〕棧一定是順序存儲的線性結構。 〔√〕〔4〕棧的特點是“后進先出〞。 〔ㄨ〕〔5〕空棧就是所有元素都為0的棧。 〔ㄨ〕〔6〕在C或C++語言中設順序棧的長度為MAXLEN，如此top=MAXL

37、EN時表示隊滿。 〔√〕〔7〕鏈棧與順序棧相比，其特點之一是通常不會出現(xiàn)棧滿的情況。 〔ㄨ〕〔8〕一個棧的輸入序列為：A，B，C，D，可以得到輸出序列：C，A，B，D。 〔ㄨ〕〔9〕遞歸定義就是循環(huán)定義。 〔√〕〔10〕將十進制數(shù)轉換為二進制數(shù)是棧的典型應用之一。 二．填空題 〔1〕在棧結構中，允許插入、刪除的一端稱為棧頂。 〔2〕在順序棧中，當棧頂指針top=-1時，表示棧空。 〔3〕在有n個元素的棧中，進棧操作的時間復雜度為 O〔1〕。 〔4〕在棧中，出棧操作的時間復雜度為： O(1) 。 〔5〕表達式，求它的后綴表達式是棧的典型應用。 〔6〕在一個鏈棧中，

38、假如棧頂指針等于NULL，如此表示?？铡? 〔7〕向一個棧頂指針為top的鏈棧插入一個新結點*p時，應執(zhí)行 p->next=top；和top=p；操作。 〔8〕順序棧S存儲在數(shù)組 S->data[0..MAXLEN-1]中，進棧操作時要執(zhí)行的語句有： S->top ++ ?！不? S->top+1〕 〔9〕鏈棧LS，指向棧頂元素的指針是 LS->next 。 〔10〕從一個棧刪除元素時，首先取出棧頂元素，然后再移動棧頂指針。 〔11〕由于鏈棧的操作只在鏈表的頭部進展，所以沒有必要設置頭結點。 〔12〕順序棧S，在對S進展進棧操作之前首先要判斷棧是否滿。 〔13〕順序棧

39、S，在對S進展出棧操作之前首先要判斷棧是否空。 〔14〕假如存空間充足，鏈?？梢圆欢x棧滿運算。 〔15〕鏈棧LS是空的條件是 LS->next=NULL 。 〔16〕鏈棧LS的棧頂元素是鏈表的首元素。 〔17〕同一棧的各元素的類型一樣。 〔18〕假如進棧的次序是A、B、C、D、E，執(zhí)行三次出棧操作以后，棧頂元素為 B 。 〔19〕A+B/C-D*E的后綴表達式是： ABC/+DE*- 。 〔20〕四個元素按A、B、C、D順序進S棧，執(zhí)行兩次Pop〔S，x〕運算后，x的值是 C 。 三．選擇題 〔1〕插入和刪除只能在一端進展的線性表，稱為( C

40、 )。 A．隊列 B．循環(huán)隊列 C．棧 D．循環(huán)棧 〔2〕設有編號為1，2，3，4的四輛列車，順序進入一個棧結構的站臺，如下不可能的出站順序為 ( D ) A．1234 B．1243 C．1324 D．1423 〔3〕如果以鏈表作為棧的存儲結構，如此出棧操作時〔 B 〕 A．必須判別棧是否滿 B．必須判別棧是否空 C．必須判別棧元素類型 D．隊?？刹蛔鋈魏闻袆e 〔4〕元素A,B,C,D依次進棧以后，棧頂元素是〔 D 〕 A．A

41、B．B C．C D．D 〔5〕順序棧存儲空間的實現(xiàn)使用〔 B 〕存儲棧元素。 A．鏈表 B．數(shù)組 C．循環(huán)鏈表 D．變量 〔6〕在C或C++語言中，一個順序棧一旦被聲明，其占用空間的大小〔 A 〕。 A．已固定 B．不固定 C．可以改變 D．動態(tài)變化 〔7〕帶頭結點的鏈棧LS的示意圖如下，棧頂元素是〔 A 〕 LS H A B C D Λ A．A B．B C．C

42、 D．D 〔8〕鏈棧與順序棧相比，有一個比擬明顯的優(yōu)點是〔 B 〕。 A．插入操作更加方便 B．通常不會出現(xiàn)棧滿的情況。 C．不會出現(xiàn)?？盏那闆r D．刪除操作根加方便 〔9〕從一個棧頂指針為top的鏈棧中刪除一個結點時，用x保存被刪除的結點，應執(zhí)行如下 ( D )命令。 A．x=top;top=top->next; B．top=top->next;x=top->data; C．x=top->data; D．x=top->data;top=top->next; 〔10〕在一個棧頂指針為HS的

43、鏈棧中，將一個S指針所指的結點入棧，應執(zhí)行如下 ( B )命令。 A．HS->next=S; B．S->next=HS->next;HS->next=S; C．S->next=HS->next;HS=S; D．S->next=HS;HS=HS->next; 〔11〕四個元素按A、B、C、D順序進S棧，執(zhí)行兩次Pop〔S，x〕運算后，棧頂元素的值是〔 B 〕。 A．A B．B C．C D．D 〔12〕元素A,B,C,D依次進棧以后，棧底元素是〔 A 〕。 A．A

44、 B．B C．C D．D 〔13〕經(jīng)過如下棧的運算后，再執(zhí)行ReadTop(s)的值是〔 A 〕。 InitStack(s)〔初始化?！?Push(s,a);Push(s,b); Pop(s) A．a(chǎn) B．b C．1 D．0 〔14〕經(jīng)過如下棧的運算后，x的值是〔 B 〕。 InitStack(s)〔初始化?！?Push(s,a);Push(s,b); ReadTop(s);Pop(s,x); A．a(chǎn) B．b C

45、．1 D．0 〔15〕經(jīng)過如下棧的運算后，x的值是〔 B 〕。 InitStack(s)〔初始化?！?Push(s,a);Pop(s,x);Push(s,b);Pop(s,x); A．a(chǎn) B．b C．1 D．0 〔16〕經(jīng)過如下棧的運算后，SEmpty(s)的值是〔 C 〕。 InitStack(s)〔初始化?！? Push(s,a); Push(s,b);Pop(s,x); Pop(s,x); A．a(chǎn) B．b C．1 D．0

46、 〔17〕向順序棧中壓入元素時，〔 B 〕。 A． 先存入元素，后移動棧頂指針 B．先移動棧頂指針，后存入元素 C．誰先誰后無關緊要 D．同時進展 〔18〕初始化一個空間大小為5的順序棧S后，S->top的值是〔 B 〕。 A．0 B．-1 C．不再改變 D．動態(tài)變化 〔19〕一個棧的入棧次序ABCDE，如此棧的不可能的輸出序列是 ( C )。 A．EDCBA B．DECBA C．DCEAB D．ABCDE 〔20〕設有一個順序棧S，元素A,B,C,D,E,F,依次進棧，

47、如果六個元素出棧的順序是B，D，C，F(xiàn)，E，A，如此棧的容量至少應是 ( A )。 A．3 B．4 C．5 D． 6 四．應用題 〔1〕設有一個棧，元素進棧的次序為：A，B，C，D，E，用I表示進棧操作，O表示出棧操作，寫出如下出棧的操作序列。 ①C，B，A，D，E ②A，C，B，E，D 解：①IIIOOOIOIO ②IOIIOOIIOO （2） 求后綴表達式 ① A^B^C/D 解：A B ^ C ^ D / ② -A+B*C+D/E 解：

48、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 - 六．算法設計題 〔1〕設用一維數(shù)組stack[n]表示一個堆棧，假如堆棧中每個元素需占用M個數(shù)組單元〔M>1〕。 ①試寫出其入棧操作的算法。 ②試寫出其出棧操作的算法。 解：//用一整型變量top表示棧頂指針，top為0時表示棧為空。棧中元素從S [1]開始存放元素。 //①入棧算法： v

49、oid 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) {

50、 if (top= =0) printf (“堆棧為空棧！〞); else { if (top= =1) { x= S [top]; top––; } else { x= S [top]; top=top–M; } } } 〔2〕設計一個算法，要求判別一個算術表

51、達式中的圓括號配對是否正確。 解：//設表達式在字符數(shù)組a[ ]中，使用一堆棧S來幫助判斷。 int correct (char a[ ]) { stack s ; InitStack (s); //調用初始化棧函數(shù) for (i=0; i

52、0; //假如棧為空返回0；否如此出棧 else Pop(s); } if (StackEmpty (s) ) //調用判?？蘸瘮?shù) printf (“配對正確！〞); //假如?？眨f明配對正確，并返回1 else printf (“配對錯誤！〞); //配對錯誤返回0 } （3） 設計一個將十進正整數(shù)轉換為十進制數(shù)的算法，并要求上機調試通過。 解： #include #include

53、b.h> typedef struct stacknode //定義棧的存儲結構 { int data; struct stacknode *next; }stacknode; typedef struct { stacknode *top; //定義棧頂?shù)闹羔? }linkstack; void Conversion(int n) //棧的應用：十——十六進制轉換 { linkstack s; int x; s.top=NULL;

54、 //置?？? do { x=n%16; //取余數(shù) n= n/16 ; //取新的商 stacknode *p=new stacknode; //申請新結點 p->next=s.top ; //修改棧頂指針 s.top=p; s.top->data=x; //余數(shù)入棧 } while(n);

55、 printf("\n\t\t轉換后的十六進制數(shù)值為："; while (s.top) //出棧處理 { if(s.top->data<10); printf("%d",s.top->data); else switch(s.top->data) { case 10: printf("%c",'A');break; case 11: printf("%c",'B');break; case 12: printf("%c",'C');bre

56、ak; case 13: printf("%c",'D');break; case 14: printf("%c",'E');break; case 15: printf("%c",'F');break; } stacknode *p=s.top; s.top=s.top->next; free(p) ; //出棧一個余數(shù)，收回一個結 } printf("\n\n"); } void main() { int n; printf("\n\t\t請輸入一個十進制正整數(shù)：")

57、; scanf("%d",&n); Conversion(n); } 單元練習4 一．判斷題〔如下各題，正確的請在前面的括號打√；錯誤的打╳〕 〔√〕〔1〕隊列是限制在兩端進展操作的線性表。 〔√〕〔2〕判斷順序隊列為空的標準是頭指針和尾指針都指向同一個結點。 〔×〕〔3〕在鏈隊列上做出隊操作時，會改變front指針的值。 〔√〕〔4〕在循環(huán)隊列中，假如尾指針rear大于頭指針front，其元素個數(shù)為rear- front。 〔×〕〔5〕在單向循環(huán)鏈表中，假如頭指針為h，那么p所指結點為尾結點的條件是p=h。 〔√〕〔6〕鏈隊列在一定圍不會出現(xiàn)隊滿的情況。 〔×〕〔

58、7〕在循環(huán)鏈隊列中無溢出現(xiàn)象。 〔×〕〔8〕棧和隊列都是順序存儲的線性結構。 〔×〕〔9〕在隊列中允許刪除的一端稱為隊尾。 〔×〕〔10〕順序隊和循環(huán)隊關于隊滿和隊空的判斷條件是一樣的。 二．填空題 （1） 在隊列中存取數(shù)據(jù)應遵循的原如此是先進先出。 （2） 隊列是被限定為只能在表的一端進展插入運算，在表的另一端進展刪除運算的線性表。 （3） 在隊列中，允許插入的一端稱為隊尾。 （4） 在隊列中，允許刪除的一端稱為隊首〔或隊頭〕。 （5） 隊列在進展出隊操作時，首先要判斷隊列是否為空。 （6） 順序隊列在進展入隊操作時，首先要判斷隊列是否為滿。 （7） 順序隊列初始化

59、后，front=rear= -1 。 （8） 解決順序隊列“假溢出〞的方法是采用循環(huán)隊列。 （9） 循環(huán)隊列的隊首指針為front，隊尾指針為rear，如此隊空的條件為 front == rear 。 （10） 鏈隊列LQ為空時，LQ->front->next= NULL 。 （11） 設長度為n的鏈隊列用單循環(huán)鏈表表示，假如只設頭指針，如此入隊操作的時間復雜度為 O〔n〕。 （12） 設長度為n的鏈隊列用單循環(huán)鏈表表示，假如只設尾指針，如此出隊操作的時間復雜度為 0〔1〕。 （13） 在一個鏈隊列中，假如隊首指針與隊尾指針的值一樣，如此表示該隊列為空。

60、 （14） 設循環(huán)隊列的頭指針front指向隊首元素，尾指針rear指向隊尾元素后的一個空閑元素，隊列的最大空間為MAXLEN，如此隊滿標志為： front==(rear+1)%MAXLEN 。 （15） 在一個鏈隊列中，假如隊首指針為front，隊尾指針為rear，如此判斷該隊列只有一個結點的條件為： front==rear && front !NULL 。 (或 front==rear && front <>NULL ) （16） 向一個循環(huán)隊列中插入元素時，首先要判斷隊尾指針，然后再向指針所指的位置寫入新的數(shù)據(jù)。 （17） 讀隊首元素的操作不改變〔或不影響〕隊

61、列元素的個數(shù)。 〔18〕設循環(huán)隊列的容量為40〔序號從0到39〕，現(xiàn)經(jīng)過一系列的入隊和出隊運算后，有 front=11，rear=19，如此循環(huán)隊列中還有 8 個元素。 〔L= (N＋rear－front)% N=〔40＋19－11〕% 40=8〕 〔19〕隊列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,

62、b); ReadFront(Q,x)后，x的值是 a 。 三．選擇題 〔1〕隊列是限定在〔 D 〕進展操作的線性表。 A．中間 B．隊首 C．隊尾 D．端點 〔2〕隊列中的元素個數(shù)是( B )。 A．不變的 B．可變的 C．任意的 D．0 〔3〕同一隊列各元素的類型( A )。 A．必須一致 B．不能一致 C．可以不一致 D．不限制 〔4〕隊列是一個( C )線性表結構。 A．不加限制的 B．推廣了的 C．加了限制的 D．非 〔5〕當利用大小為n的數(shù)組順序存儲一

63、個隊列時，該隊列的最后一個元素的下標為〔 B 〕。 A．n-2 B．n-1 C．n D．n+1 〔6〕一個循環(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 )。 A．0..10 B．0..9 C．1..9

64、 D．1..10 〔9〕假如進隊的序列為：A，B，C，D，如此出隊的序列是〔 C 〕。 A．B，C，D，A B．A，C，B，D C．A，B，C，D D．C，B，D，A 〔10〕四個元素按：A，B，C，D順序連續(xù)進隊Q，如此隊尾元素是〔 D 〕。 A． A B． B C． C D． D 〔11〕四個元素按：A，B，C，D順序連續(xù)進隊Q，執(zhí)行一次OutQueue(Q)操作后，隊頭元素是〔 B 〕。 A． A B． B C． C D． D

65、 〔12〕四個元素按：A，B，C，D順序連續(xù)進隊Q，執(zhí)行四次OutQueue(Q)操作后，再執(zhí)行QEmpty(Q);后的值是〔 B 〕。 A． 0 B． 1 C． 2 D． 3 〔13〕隊列Q，經(jīng)過如下運算后，x 的值是〔 B 〕。 InitQueue(Q)(初始化隊列);InQueue(Q,a); InQueue(Q,b);OutQueue(Q,x); ReadFront (Q,x); A．a(chǎn) B．b C．0 D．1 〔14〕循環(huán)隊列SQ隊滿的條件是( B

66、 )。 A．SQ->rear==SQ->front B．(SQ->rear+1)% MAXLEN ==SQ->front C．SQ->rear==0 D．SQ->front==0 〔15〕設鏈棧中結點的結構：data為數(shù)據(jù)域，next為指針域，且top是棧頂指針。假如想在鏈棧的棧頂插入一個由指針s所指的結點，如此應執(zhí)行如下〔 A 〕操作。 A．s->next=top->next；top->next=s； B．top->next=s； C．s->next=top；top=top->next； D．s->next=top；top=s； 〔16〕帶頭結點的鏈隊列LQ示意圖如下，鏈隊列的隊頭元素是〔 A 〕 LQ->front H A B C D Λ LQ->rear A．A B．B C．C D．D 〔17〕帶頭結點的鏈隊列LQ示意圖如下，指向鏈隊列的隊頭指針是〔 C 〕 LQ