《第1章緒論 在順序表中等概率情況下插入和刪除一個(gè)元素平均 練習(xí)題》由會(huì)員分享，可在線閱讀，更多相關(guān)《第1章緒論 在順序表中等概率情況下插入和刪除一個(gè)元素平均 練習(xí)題（68頁珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、第 1 章 緒 論 1. 填空 ⑴ 在順序表中，等概率情況下，插入和刪除一個(gè)元素平均需移動(dòng)（ ）個(gè)元素，具體移動(dòng)元素的個(gè)數(shù)與（ ）和（ ）有關(guān)。 【解答】表長的一半，表長，該元素在表中的位置 ⑵ 順序表中第一個(gè)元素的存儲(chǔ)地址是100，每個(gè)元素的長度為2，則第5個(gè)元素的存儲(chǔ)地址是（ ）。 【解答】108 【分析】第5個(gè)元素的存儲(chǔ)地址=第1個(gè)元素的存儲(chǔ)地址＋(5－1)×2=108 ⑶ 設(shè)單鏈表中指針p 指向結(jié)點(diǎn)A，若要?jiǎng)h除A的后繼結(jié)點(diǎn)（假設(shè)A存在后繼結(jié)點(diǎn)），則需修改指針的操作為（ ）。 【解答】p->next=(p->next)->next ⑷ 單鏈表中設(shè)置頭結(jié)點(diǎn)的作用是（ ）

2、。 【解答】為了運(yùn)算方便 【分析】例如在插入和刪除操作時(shí)不必對(duì)表頭的情況進(jìn)行特殊處理。 ⑸ 非空的單循環(huán)鏈表由頭指針head指示，則其尾結(jié)點(diǎn)（由指針p所指）滿足（ ）。 【解答】p->next=head 【分析】如圖2-8所示。 ⑹ 在由尾指針rear指示的單循環(huán)鏈表中，在表尾插入一個(gè)結(jié)點(diǎn)s的操作序列是（ ）；刪除開始結(jié)點(diǎn)的操作序列為（ ）。 【解答】s->next =rear->next; rear->next =s; rear =s;(將S的指針域先弄成表尾指針域，而表尾指針域是代表下個(gè)結(jié)點(diǎn)的地址信息，所以要將指針域要用S替代，最后把表尾給S) q=rear->next

3、->next; rear->next->next=q->next; delete q; 【分析】操作示意圖如圖2-9所示： ⑺ 一個(gè)具有n個(gè)結(jié)點(diǎn)的單鏈表，在指針p所指結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度為（ ）；在給定值為x的結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度為（ ）。 【解答】Ο(1)，Ο(n) 【分析】在p所指結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)只需修改指針，所以時(shí)間復(fù)雜度為Ο(1)（是表示常數(shù)計(jì)算時(shí)間）；而在給定值為x的結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)需要先查找值為x的結(jié)點(diǎn)，所以時(shí)間復(fù)雜度為Ο(n)。 ⑻ 可由一個(gè)尾指針唯一確定的鏈表有（ ）、（ ）、（ ）。 【解答】循環(huán)鏈表，循環(huán)雙鏈表，雙鏈表 2

4、. 選擇題 ⑴ 線性表的順序存儲(chǔ)結(jié)構(gòu)是一種（ ）的存儲(chǔ)結(jié)構(gòu)，線性表的鏈接存儲(chǔ)結(jié)構(gòu)是一種（ ）的存儲(chǔ)結(jié)構(gòu)。 A 隨機(jī)存取 B 順序存取 C 索引存取 D 散列存取 【解答】A，B 【分析】參見2.2.1。 ⑵ 線性表采用鏈接存儲(chǔ)時(shí)，其地址（ ）。 A 必須是連續(xù)的　　　　　 B 部分地址必須是連續(xù)的 C 一定是不連續(xù)的　　 　 D 連續(xù)與否均可以 【解答】D 【分析】線性表的鏈接存儲(chǔ)是用一組任意的存儲(chǔ)單元存儲(chǔ)線性表的數(shù)據(jù)元素，這組存儲(chǔ)單元可以連續(xù)，也可以不連續(xù)，甚至可以零散分布在內(nèi)存中任意位置。 ⑶ 單循環(huán)鏈表的主要優(yōu)點(diǎn)是（ ）。 A 不再需要頭指針了 B 從表中任一

5、結(jié)點(diǎn)出發(fā)都能掃描到整個(gè)鏈表； C 已知某個(gè)結(jié)點(diǎn)的位置后，能夠容易找到它的直接前驅(qū)； D 在進(jìn)行插入、刪除操作時(shí)，能更好地保證鏈表不斷開。 【解答】B ⑷ 鏈表不具有的特點(diǎn)是（ ）。 A 可隨機(jī)訪問任一元素 B 插入、刪除不需要移動(dòng)元素 C 不必事先估計(jì)存儲(chǔ)空間 D 所需空間與線性表長度成正比 【解答】A ⑸ 若某線性表中最常用的操作是取第i 個(gè)元素和找第i個(gè)元素的前驅(qū)，則采用（ ）存儲(chǔ)方法最節(jié)省時(shí)間。 A 順序表 B 單鏈表 C 雙鏈表 D 單循環(huán)鏈表 【解答】A 【分析】線性表中最常用的操作是取第i 個(gè)元素，所以，應(yīng)選擇隨機(jī)存取結(jié)構(gòu)即順序表，同時(shí)在順序表中查找第i個(gè)元

6、素的前驅(qū)也很方便。單鏈表和單循環(huán)鏈表既不能實(shí)現(xiàn)隨機(jī)存取，查找第i個(gè)元素的前驅(qū)也不方便，雙鏈表雖然能快速查找第i個(gè)元素的前驅(qū)，但不能實(shí)現(xiàn)隨機(jī)存取。 ⑹ 若鏈表中最常用的操作是在最后一個(gè)結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)和刪除第一個(gè)結(jié)點(diǎn)，則采用（ ）存儲(chǔ)方法最節(jié)省時(shí)間。 A 單鏈表 B 帶頭指針的單循環(huán)鏈表 C 雙鏈表 D 帶尾指針的單循環(huán)鏈表 【解答】D 【分析】在鏈表中的最后一個(gè)結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)需要知道終端結(jié)點(diǎn)的地址，所以，單鏈表、帶頭指針的單循環(huán)鏈表、雙鏈表都不合適，考慮在帶尾指針的單循環(huán)鏈表中刪除第一個(gè)結(jié)點(diǎn)，其時(shí)間性能是O(1)，所以，答案是D 。 ⑺ 若鏈表中最常用的操作是在最后一個(gè)結(jié)點(diǎn)

7、之后插入一個(gè)結(jié)點(diǎn)和刪除最后一個(gè)結(jié)點(diǎn)，則采用（ ）存儲(chǔ)方法最節(jié)省運(yùn)算時(shí)間。 A 單鏈表 B 循環(huán)雙鏈表 C單循環(huán)鏈表 　　D 帶尾指針的單循環(huán)鏈表 【解答】B 【分析】在鏈表中的最后一個(gè)結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)需要知道終端結(jié)點(diǎn)的地址，所以，單鏈表、單循環(huán)鏈表都不合適，刪除最后一個(gè)結(jié)點(diǎn)需要知道終端結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)的地址，所以，帶尾指針的單循環(huán)鏈表不合適，而循環(huán)雙鏈表滿足條件。 ⑻ 在具有n個(gè)結(jié)點(diǎn)的有序單鏈表中插入一個(gè)新結(jié)點(diǎn)并仍然有序的時(shí)間復(fù)雜度是（ ）。 A O(1) B O(n) C O(n2) D O(nlog2n) 【解答】B 【分析】首先應(yīng)順序查找新結(jié)點(diǎn)在單鏈表中的位置。 ⑼ 對(duì)

8、于n個(gè)元素組成的線性表，建立一個(gè)有序單鏈表的時(shí)間復(fù)雜度是（ ）。 A O(1) B O(n) C O(n2) D O(nlog2n) 【解答】C 【分析】該算法需要將n個(gè)元素依次插入到有序單鏈表中，而插入每個(gè)元素需O(n)。 ⑽ 使用雙鏈表存儲(chǔ)線性表，其優(yōu)點(diǎn)是可以（ ）。 A 提高查找速度 B 更方便數(shù)據(jù)的插入和刪除 C 節(jié)約存儲(chǔ)空間 D 很快回收存儲(chǔ)空間 【解答】B 【分析】在鏈表中一般只能進(jìn)行順序查找，所以，雙鏈表并不能提高查找速度，因?yàn)殡p鏈表中有兩個(gè)指針域，顯然不能節(jié)約存儲(chǔ)空間，對(duì)于動(dòng)態(tài)存儲(chǔ)分配，回收存儲(chǔ)空間的速度是一樣的。由于雙鏈表具有對(duì)稱性，所以，其插入和刪除操作更加

9、方便。 ⑾ 在一個(gè)單鏈表中，已知q所指結(jié)點(diǎn)是p所指結(jié)點(diǎn)的直接前驅(qū)，若在q和p之間插入s所指結(jié)點(diǎn)，則執(zhí)行（ ）操作。 A s->next=p->next; p->next=s; B q->next=s; s->next=p; C p->next=s->next; s->next=p; D p->next=s; s->next=q; 【解答】B 【分析】注意此題是在q和p之間插入新結(jié)點(diǎn)，所以，不用考慮修改指針的順序。 ⑿ 在循環(huán)雙鏈表的p所指結(jié)點(diǎn)后插入s所指結(jié)點(diǎn)的操作是（ ）。 A p->next=s; s->prior=p; p->next->prior=s; s->next=p

10、->next; B p->next=s; p->next->prior=s; s->prior=p; s->next=p->next; C s->prior=p; s->next=p->next; p->next=s; p->next->prior=s; D s->prior=p; s->next=p->next; p->next->prior=s; p->next=s 【解答】D 【分析】在鏈表中，對(duì)指針的修改必須保持線性表的邏輯關(guān)系，否則，將違背線性表的邏輯特征，圖2-10給出備選答案C和D的圖解。 3. 判斷題 ⑴ 線性表的邏輯順序和存儲(chǔ)順序總是一致的。 【解答】錯(cuò)

11、。順序表的邏輯順序和存儲(chǔ)順序一致，鏈表的邏輯順序和存儲(chǔ)順序不一定一致。 ⑵ 線性表的順序存儲(chǔ)結(jié)構(gòu)優(yōu)于鏈接存儲(chǔ)結(jié)構(gòu)。 【解答】錯(cuò)。兩種存儲(chǔ)結(jié)構(gòu)各有優(yōu)缺點(diǎn)。 ⑶ 設(shè)p，q是指針，若p=q，則*p=*q。 【解答】錯(cuò)。p=q只能表示p和q指向同一起始地址，而所指類型則不一定相同。 ⑷ 線性結(jié)構(gòu)的基本特征是：每個(gè)元素有且僅有一個(gè)直接前驅(qū)和一個(gè)直接后繼。 【解答】錯(cuò)。每個(gè)元素最多只有一個(gè)直接前驅(qū)和一個(gè)直接后繼，第一個(gè)元素沒有前驅(qū)，最后一個(gè)元素沒有后繼。 ⑸ 在單鏈表中，要取得某個(gè)元素，只要知道該元素所在結(jié)點(diǎn)的地址即可，因此單鏈表是隨機(jī)存取結(jié)構(gòu)。 【解答】錯(cuò)。要找到該結(jié)點(diǎn)的地址，必須從頭指

12、針開始查找，所以單鏈表是順序存取結(jié)構(gòu)。 4．請(qǐng)說明順序表和單鏈表各有何優(yōu)缺點(diǎn)，并分析下列情況下，采用何種存儲(chǔ)結(jié)構(gòu)更好些。 ⑴ 若線性表的總長度基本穩(wěn)定，且很少進(jìn)行插入和刪除操作，但要求以最快的速度存取線性表中的元素。 ⑵ 如果n個(gè)線性表同時(shí)并存，并且在處理過程中各表的長度會(huì)動(dòng)態(tài)發(fā)生變化。 ⑶ 描述一個(gè)城市的設(shè)計(jì)和規(guī)劃。 【解答】順序表的優(yōu)點(diǎn)：① 無需為表示表中元素之間的邏輯關(guān)系而增加額外的存儲(chǔ)空間；② 可以快速地存取表中任一位置的元素（即隨機(jī)存?。?。順序表的缺點(diǎn)：① 插入和刪除操作需移動(dòng)大量元素；② 表的容量難以確定；③ 造成存儲(chǔ)空間的“碎片”。 單鏈表的優(yōu)點(diǎn)：① 不必事先知道線性

13、表的長度；② 插入和刪除元素時(shí)只需修改指針，不用移動(dòng)元素。單鏈表的缺點(diǎn)：① 指針的結(jié)構(gòu)性開銷；② 存取表中任意元素不方便，只能進(jìn)行順序存取。 ⑴ 應(yīng)選用順序存儲(chǔ)結(jié)構(gòu)。因?yàn)轫樞虮硎请S機(jī)存取結(jié)構(gòu)，單鏈表是順序存取結(jié)構(gòu)。本題很少進(jìn)行插入和刪除操作，所以空間變化不大，且需要快速存取，所以應(yīng)選用順序存儲(chǔ)結(jié)構(gòu)。 ⑵ 應(yīng)選用鏈接存儲(chǔ)結(jié)構(gòu)。鏈表容易實(shí)現(xiàn)表容量的擴(kuò)充，適合表的長度動(dòng)態(tài)發(fā)生變化。 ⑶ 應(yīng)選用鏈接存儲(chǔ)結(jié)構(gòu)。因?yàn)橐粋€(gè)城市的設(shè)計(jì)和規(guī)劃涉及活動(dòng)很多，需要經(jīng)常修改、擴(kuò)充和刪除各種信息，才能適應(yīng)不斷發(fā)展的需要。而順序表的插入、刪除的效率低，故不合適。 5．算法設(shè)計(jì) ⑴ 設(shè)計(jì)一個(gè)時(shí)間復(fù)雜度為Ｏ(n)的

14、算法，實(shí)現(xiàn)將數(shù)組A[n]中所有元素循環(huán)右移k個(gè)位置。 【解答】算法思想請(qǐng)參見主教材第一章思想火花。下面給出具體算法。 分析算法，第一次調(diào)用Reverse函數(shù)的時(shí)間復(fù)雜度為O(k)，第二次調(diào)用Reverse函數(shù)的時(shí)間復(fù)雜度為O(n-k)，第三次調(diào)用Reverse函數(shù)的時(shí)間復(fù)雜度為O(n)，所以，總的時(shí)間復(fù)雜度為O(n)。 ⑵ 已知數(shù)組A[n]中的元素為整型，設(shè)計(jì)算法將其調(diào)整為左右兩部分，左邊所有元素為奇數(shù)，右邊所有元素為偶數(shù)，并要求算法的時(shí)間復(fù)雜度為Ｏ(n)。 【解答】從數(shù)組的兩端向中間比較，設(shè)置兩個(gè)變量i和j，初始時(shí)i=0，j=n-1，若A[i]為偶數(shù)并且A[j]為奇數(shù)，則將A[i

15、]與A[j]交換。具體算法如下： 分析算法，兩層循環(huán)將數(shù)組掃描一遍，所以，時(shí)間復(fù)雜度為Ｏ(n)。 ⑶ 試編寫在無頭結(jié)點(diǎn)的單鏈表上實(shí)現(xiàn)線性表的插入操作的算法，并和帶頭結(jié)點(diǎn)的單鏈表上的插入操作的實(shí)現(xiàn)進(jìn)行比較。 【解答】參見2.2.3。 ⑷ 試分別以順序表和單鏈表作存儲(chǔ)結(jié)構(gòu)，各寫一實(shí)現(xiàn)線性表就地逆置的算法。 【解答】順序表的逆置，即是將對(duì)稱元素交換，設(shè)順序表的長度為length，則將表中第i個(gè)元素與第length-i-1個(gè)元素相交換。具體算法如下： 單鏈表的逆置請(qǐng)參見2.2.4算法2-4和算法2-6。 ⑸ 假設(shè)在長度大于1的循環(huán)鏈表中，即無頭結(jié)點(diǎn)也無頭指針，s為指向鏈表中某個(gè)結(jié)

16、點(diǎn)的指針，試編寫算法刪除結(jié)點(diǎn)s的前驅(qū)結(jié)點(diǎn)。 【解答】利用單循環(huán)鏈表的特點(diǎn)，通過指針s可找到其前驅(qū)結(jié)點(diǎn)r以及r的前驅(qū)結(jié)點(diǎn)p，然后將結(jié)點(diǎn)r刪除，如圖2-11所示，具體算法如下： ⑹ 已知一單鏈表中的數(shù)據(jù)元素含有三類字符：字母、數(shù)字和其他字符。試編寫算法，構(gòu)造三個(gè)循環(huán)鏈表，使每個(gè)循環(huán)鏈表中只含同一類字符。 【解答】在單鏈表A中依次取元素，若取出的元素是字母，把它插入到字母鏈表B 中，若取出的元素是數(shù)字，則把它插入到數(shù)字鏈表D中，直到鏈表的尾部，這樣表B，D，A中分別存放字母、數(shù)字和其他字符。具體算法如下： ⑺ 設(shè)單鏈表以非遞減有序排列，設(shè)計(jì)算法實(shí)現(xiàn)在單鏈表中刪去值相同的多余結(jié)點(diǎn)。

17、 【解答】從頭到尾掃描單鏈表，若當(dāng)前結(jié)點(diǎn)的元素值與后繼結(jié)點(diǎn)的元素值不相等，則指針后移；否則刪除該后繼結(jié)點(diǎn)。具體算法如下： ⑻ 判斷帶頭結(jié)點(diǎn)的雙循環(huán)鏈表是否對(duì)稱。 【解答】設(shè)工作指針p和q分別指向循環(huán)雙鏈表的開始結(jié)點(diǎn)和終端結(jié)點(diǎn)，若結(jié)點(diǎn)p和結(jié)點(diǎn)q的數(shù)據(jù)域相等，則工作指針p后移，工作指針q前移，直到指針p和指針q指向同一結(jié)點(diǎn)（循環(huán)雙鏈表中結(jié)點(diǎn)個(gè)數(shù)為奇數(shù)），或結(jié)點(diǎn)q成為結(jié)點(diǎn)p的前驅(qū)（循環(huán)雙鏈表中結(jié)點(diǎn)個(gè)數(shù)為偶數(shù)）。如圖2-12所示。 學(xué)習(xí)自測及答案 1. 已知一維數(shù)組A采用順序存儲(chǔ)結(jié)構(gòu)，每個(gè)元素占用4個(gè)存儲(chǔ)單元，第9個(gè)元素的地址為144，則第一個(gè)元素的地址是（ ）。 A 10

18、8 B 180 C 176 D 112 【解答】D 2．在長度為n的線性表中查找值為x的數(shù)據(jù)元素的時(shí)間復(fù)雜度為： （ ）。 A O(0) B O(1) C O(n) D O(n2) 【解答】C 3．在一個(gè)長度為n的順序表的第i（1≤i≤n+1）個(gè)元素之前插入一個(gè)元素，需向后移動(dòng)（ ）個(gè)元素，刪除第i（1≤i≤n）個(gè)元素時(shí)，需向前移動(dòng)（ ）個(gè)元素。 【解答】n-i+1，n-i 4．在單鏈表中，除了頭結(jié)點(diǎn)以外，任一結(jié)點(diǎn)的存儲(chǔ)位置由（ ）指示。 【解答】其前驅(qū)結(jié)點(diǎn)的指針域 5．當(dāng)線性表采用順序存儲(chǔ)結(jié)構(gòu)時(shí)，其主要特點(diǎn)是（ ）。 【解答】邏輯結(jié)構(gòu)中相鄰的結(jié)點(diǎn)在存儲(chǔ)結(jié)構(gòu)中仍相鄰

19、 6．在雙鏈表中，每個(gè)結(jié)點(diǎn)設(shè)置了兩個(gè)指針域，其中一個(gè)指向（ ）結(jié)點(diǎn)，另一個(gè)指向（ ）結(jié)點(diǎn)。 【解答】前驅(qū)，后繼 7．設(shè)A是一個(gè)線性表（a1, a2, …, an），采用順序存儲(chǔ)結(jié)構(gòu)，則在等概率的前提下，平均每插入一個(gè)元素需要移動(dòng)的元素個(gè)數(shù)為多少？若元素插在ai與ai+1之間（1≤i≤n）的概率為 ，則平均每插入一個(gè)元素所要移動(dòng)的元素個(gè)數(shù)又是多少？ 【解答】 ， 。 8．線性表存放在整型數(shù)組A[arrsize]的前elenum 個(gè)單元中，且遞增有序。編寫算法，將元素x插入到線性表的適當(dāng)位置上，以保持線性表的有序性，并且分析算法的時(shí)間復(fù)雜度。 【解答】本題是在一個(gè)遞增有序表中插入元

20、素x，基本思路是從有序表的尾部開始依次取元素與x比較，若大于x，此元素后移一位，再取它前面一個(gè)元素重復(fù)上述步驟；否則，找到插入位置，將x插入。具體算法如下： 9. 已知單鏈表中各結(jié)點(diǎn)的元素值為整型且遞增有序，設(shè)計(jì)算法刪除鏈表中所有大于mink且小于maxk的所有元素，并釋放被刪結(jié)點(diǎn)的存儲(chǔ)空間。 【解答】因?yàn)槭窃谟行騿捂湵砩系牟僮?，所以，要充分利用其有序性。在單鏈表中查找第一個(gè)大于mink的結(jié)點(diǎn)和第一個(gè)小于maxk的結(jié)點(diǎn)，再將二者間的所有結(jié)點(diǎn)刪除。 10．設(shè)單循環(huán)鏈表L1，對(duì)其遍歷的結(jié)果是：x1, x2, x3,…, xn-1, xn。請(qǐng)將該循環(huán)鏈表拆成兩個(gè)單循環(huán)鏈表L1和L2

21、，使得L1中含有原L1表中序號(hào)為奇數(shù)的結(jié)點(diǎn)且遍歷結(jié)果為：x1, x3,… ；L2中含有原L1表中序號(hào)為偶數(shù)的結(jié)點(diǎn)且遍歷結(jié)果為：… , x4, x2。 【解答】算法如下： 第 3 章 特殊線性表——棧、隊(duì)列和串 課后習(xí)題講解 1. 填空 ⑴ 設(shè)有一個(gè)空棧，棧頂指針為1000H，現(xiàn)有輸入序列為1、2、3、4、5， 經(jīng)過push，push，pop，push，pop，push，push后，輸出序列是（ ），棧頂指針為（ ）。 【解答】23，1003H ⑵ 棧通常采用的兩種存儲(chǔ)結(jié)構(gòu)是（ ）；其判定?？盏臈l件分別是（ ），判定棧滿的條件分別是（ ）。 【解答】順序存儲(chǔ)結(jié)構(gòu)和鏈

22、接存儲(chǔ)結(jié)構(gòu)（或順序棧和鏈棧），棧頂指針top= -1和top=NULL，棧頂指針top等于數(shù)組的長度和內(nèi)存無可用空間 ⑶（ ）可作為實(shí)現(xiàn)遞歸函數(shù)調(diào)用的一種數(shù)據(jù)結(jié)構(gòu)。 【解答】棧 【分析】遞歸函數(shù)的調(diào)用和返回正好符合后進(jìn)先出性。 ⑷ 表達(dá)式a*(b+c)-d的后綴表達(dá)式是（ ）。 【解答】abc+*d- 【分析】將中綴表達(dá)式變?yōu)楹缶Y表達(dá)式有一個(gè)技巧：將操作數(shù)依次寫下來，再將算符插在它的兩個(gè)操作數(shù)的后面。 ⑸ 棧和隊(duì)列是兩種特殊的線性表，棧的操作特性是（ ），隊(duì)列的操作特性是（ ），棧和隊(duì)列的主要區(qū)別在于（ ）。 【解答】后進(jìn)先出，先進(jìn)先出，對(duì)插入和刪除操作限定的位置不同 ⑹ 循

23、環(huán)隊(duì)列的引入是為了克服（ ）。 【解答】假溢出 ⑺ 數(shù)組Q[n]用來表示一個(gè)循環(huán)隊(duì)列，front為隊(duì)頭元素的前一個(gè)位置，rear為隊(duì)尾元素的位置，計(jì)算隊(duì)列中元素個(gè)數(shù)的公式為（ ）。 【解答】（rear-front+n）% n 【分析】也可以是（rear-front）% n，但rear-front的結(jié)果可能是負(fù)整數(shù)，而對(duì)一個(gè)負(fù)整數(shù)求模，其結(jié)果在不同的編譯器環(huán)境下可能會(huì)有所不同。 ⑻ 用循環(huán)鏈表表示的隊(duì)列長度為n，若只設(shè)頭指針，則出隊(duì)和入隊(duì)的時(shí)間復(fù)雜度分別是（ ）和（ ）。 【解答】Ｏ(1)，Ｏ(n) 【分析】在帶頭指針的循環(huán)鏈表中，出隊(duì)即是刪除開始結(jié)點(diǎn)，這只需修改相應(yīng)指針；入隊(duì)即是

24、在終端結(jié)點(diǎn)的后面插入一個(gè)結(jié)點(diǎn)，這需要從頭指針開始查找終端結(jié)點(diǎn)的地址。 ⑼ 串是一種特殊的線性表，其特殊性體現(xiàn)在（ ）。 【解答】數(shù)據(jù)元素的類型是一個(gè)字符 ⑽ 兩個(gè)串相等的充分必要條件是（ ）。 【解答】長度相同且對(duì)應(yīng)位置的字符相等 【分析】例如"abc"≠"abc "，"abc"≠"bca"。 2. 選擇題 ⑴ 若一個(gè)棧的輸入序列是1，2，3，…，n，輸出序列的第一個(gè)元素是n，則第i個(gè)輸出元素是（ ）。 A 不確定 B n-i C n-i-1 D n-i+1 【解答】D 【分析】此時(shí)，輸出序列一定是輸入序列的逆序。 ⑵ 設(shè)棧S和隊(duì)列Q的初始狀態(tài)為空，元素e1、e2、e3、

25、e4、e5、e6依次通過棧S，一個(gè)元素出棧后即進(jìn)入隊(duì)列Q，若6個(gè)元素出隊(duì)的順序是e2、e4、e3、e6、e5、e1，則棧S的容量至少應(yīng)該是（　　 ）。 A 6　　　　 B 4　　　　 C 3　　　　 D 2 【解答】C 【分析】由于隊(duì)列具有先進(jìn)先出性，所以，此題中隊(duì)列形同虛設(shè)，即出棧的順序也是e2、e4、e3、e6、e5、e1。 ⑶ 一個(gè)棧的入棧序列是1，2，3，4，5，則棧的不可能的輸出序列是（ ）。 A 54321 B 45321 C 43512 D 12345 【解答】C 【分析】此題有一個(gè)技巧：在輸出序列中任意元素后面不能出現(xiàn)比該元素小并且是升序（指的是元素的序號(hào)）的兩

26、個(gè)元素。 ⑷ 設(shè)計(jì)一個(gè)判別表達(dá)式中左右括號(hào)是否配對(duì)的算法，采用（ ）數(shù)據(jù)結(jié)構(gòu)最佳 A 順序表 B 棧 C 隊(duì)列 D 鏈表 【解答】B 【分析】每個(gè)右括號(hào)與它前面的最后一個(gè)沒有匹配的左括號(hào)配對(duì)，因此具有后進(jìn)先出性。 ⑸ 在解決計(jì)算機(jī)主機(jī)與打印機(jī)之間速度不匹配問題時(shí)通常設(shè)置一個(gè)打印緩沖區(qū)，該緩沖區(qū)應(yīng)該是一個(gè)（ ）結(jié)構(gòu)。 A 棧 B隊(duì)列 C 數(shù)組 D線性表 【解答】B 【分析】先進(jìn)入打印緩沖區(qū)的文件先被打印，因此具有先進(jìn)先出性。 ⑹ 一個(gè)隊(duì)列的入隊(duì)順序是1，2，3，4，則隊(duì)列的輸出順序是（ ）。 A 4321 B 1234 C 1432 D 3241 【解答】B 【分析】隊(duì)列

27、的入隊(duì)順序和出隊(duì)順序總是一致的。 ⑺ 棧和隊(duì)列的主要區(qū)別在于（ ）。 A 它們的邏輯結(jié)構(gòu)不一樣 B 它們的存儲(chǔ)結(jié)構(gòu)不一樣 C 所包含的運(yùn)算不一樣 D 插入、刪除運(yùn)算的限定不一樣 【解答】D 【分析】棧和隊(duì)列的邏輯結(jié)構(gòu)都是線性的，都有順序存儲(chǔ)和鏈接存儲(chǔ)，有可能包含的運(yùn)算不一樣，但不是主要區(qū)別，任何數(shù)據(jù)結(jié)構(gòu)在針對(duì)具體問題時(shí)包含的運(yùn)算都可能不同。 ⑻ 設(shè)數(shù)組S[n]作為兩個(gè)棧S1和S2的存儲(chǔ)空間，對(duì)任何一個(gè)棧只有當(dāng)S[n]全滿時(shí)才不能進(jìn)行進(jìn)棧操作。為這兩個(gè)棧分配空間的最佳方案是（ ）。 A S1的棧底位置為0，S2的棧底位置為n-1 B S1的棧底位置為0，S2的棧底位置為n/2

28、C S1的棧底位置為0，S2的棧底位置為n D S1的棧底位置為0，S2的棧底位置為1 【解答】A 【分析】兩棧共享空間首先兩個(gè)棧是相向增長的，棧底應(yīng)該分別指向兩個(gè)棧中的第一個(gè)元素的位置，并注意C++中的數(shù)組下標(biāo)是從0開始的。 ⑼ 設(shè)有兩個(gè)串p和q，求q在p中首次出現(xiàn)的位置的運(yùn)算稱作（ ）。 A 連接 B 模式匹配 C 求子串 D 求串長 【解答】B 3. 判斷題 ⑴ 有n個(gè)元素依次進(jìn)棧，則出棧序列有(n-1)/2種。 【解答】錯(cuò)。應(yīng)該有 種。 ⑵ ?？梢宰鳛閷?shí)現(xiàn)過程調(diào)用的一種數(shù)據(jù)結(jié)構(gòu)。 【解答】對(duì)。只要操作滿足后進(jìn)先出性，都可以采用棧作為輔助數(shù)據(jù)結(jié)構(gòu)。 ⑶ 在棧滿的情

29、況下不能做進(jìn)棧操作，否則將產(chǎn)生“上溢”。 【解答】對(duì)。 ⑷ 在循環(huán)隊(duì)列中，front指向隊(duì)頭元素的前一個(gè)位置，rear指向隊(duì)尾元素的位置，則隊(duì)滿的條件是front=rear。 【解答】錯(cuò)。這是隊(duì)空的判定條件，在循環(huán)隊(duì)列中要將隊(duì)空和隊(duì)滿的判定條件區(qū)別開。 ⑸ 空串與空格串是相同的。 【解答】錯(cuò)?？沾拈L度為零，而空格串的長度不為0，其長度是串中空格的個(gè)數(shù)。 4. 設(shè)有一個(gè)棧，元素進(jìn)棧的次序?yàn)锳，B，C，D，E，能否得到如下出棧序列，若能，請(qǐng)寫出操作序列，若不能，請(qǐng)說明原因。 ⑴ C，E，A，B，D ⑵ C，B，A，D，E 【解答】⑴不能，因?yàn)樵贑、E出棧的情況下，A一定在棧中

30、，而且在B的下面，不可能先于B出棧。⑵可以，設(shè)Ｉ為進(jìn)棧操作，Ｏ為入棧操作，則其操作序列為IIIOOOIOIO。 5. 舉例說明順序隊(duì)列的“假溢出”現(xiàn)象。 【解答】假設(shè)有一個(gè)順序隊(duì)列，如圖3-6所示，隊(duì)尾指針rear=4，隊(duì)頭指針front=1，如果再有元素入隊(duì)，就會(huì)產(chǎn)生“上溢”，此時(shí)的“上溢”又稱為“假溢出”，因?yàn)殛?duì)列并不是真的溢出了，存儲(chǔ)隊(duì)列的數(shù)組中還有2個(gè)存儲(chǔ)單元空閑，其下標(biāo)分別為0和1。 6. 在操作序列push(1)、push(2)、pop、push(5)、push(7)、pop、push(6)之后，棧頂元素和棧底元素分別是什么？（push(k)表示整數(shù)k入棧，pop表示棧頂

31、元素出棧。） 【解答】棧頂元素為6，棧底元素為1。其執(zhí)行過程如圖3-7所示。 7． 在操作序列EnQueue(1)、 EnQueue(3)、 DeQueue、EnQueue(5)、EnQueue(7)、DeQueue、EnQueue(9)之后，隊(duì)頭元素和隊(duì)尾元素分別是什么？（EnQueue(k)表示整數(shù)k入隊(duì)，DeQueue表示隊(duì)頭元素出隊(duì)）。 【解答】隊(duì)頭元素為5，隊(duì)尾元素為9。其執(zhí)行過程如圖3-8所示。 8．空串和空格串有何區(qū)別？串中的空格符有何意義？空串在串處理中有何作用？ 【解答】不含任何字符的串稱為空串，其長度為零。僅含空格的串稱為空格串，它的長度為串中空格符的個(gè)數(shù)

32、。串中的空格符可用來分隔一般的字符，便于人們識(shí)別和閱讀，但計(jì)算串長時(shí)應(yīng)包括這些空格符?？沾诖幚碇锌勺鳛槿我獯淖哟?。 9. 算法設(shè)計(jì) ⑴ 假設(shè)以不帶頭結(jié)點(diǎn)的循環(huán)鏈表表示隊(duì)列，并且只設(shè)一個(gè)指針指向隊(duì)尾結(jié)點(diǎn)，但不設(shè)頭指針。試設(shè)計(jì)相應(yīng)的入隊(duì)和出隊(duì)的算法。 【解答】出隊(duì)操作是在循環(huán)鏈表的頭部進(jìn)行，相當(dāng)于刪除開始結(jié)點(diǎn)，而入隊(duì)操作是在循環(huán)鏈表的尾部進(jìn)行，相當(dāng)于在終端結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)。由于循環(huán)鏈表不帶頭結(jié)點(diǎn)，需要處理空表的特殊情況。 入隊(duì)算法如下： 出隊(duì)算法如下： ⑵ 設(shè)順序棧S中有2n個(gè)元素，從棧頂?shù)綏５椎脑匾来螢閍2n，a2n-1，…，a1，要求通過一個(gè)循環(huán)隊(duì)列重新排列棧中

33、元素，使得從棧頂?shù)綏５椎脑匾来螢閍2n，a2n-2，…，a2，a2n-1，a2n-3，…，a1，請(qǐng)?jiān)O(shè)計(jì)算法實(shí)現(xiàn)該操作，要求空間復(fù)雜度和時(shí)間復(fù)雜度均為O(n)。 【解答】操作步驟為： ① 將所有元素出棧并入隊(duì)； ② 依次將隊(duì)列元素出隊(duì)，如果是偶數(shù)結(jié)點(diǎn)，則再入隊(duì)，如果是奇數(shù)結(jié)點(diǎn)，則入棧； ③ 將奇數(shù)結(jié)點(diǎn)出棧并入隊(duì)； ④ 將偶數(shù)結(jié)點(diǎn)出隊(duì)并入棧； ⑤ 將所有元素出棧并入隊(duì)； ⑥ 將所有元素出隊(duì)并入棧即為所求。 ⑶ 用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)串S，編寫算法刪除S中第 i個(gè)字符開始的連續(xù)j個(gè)字符。 【解答】先判斷串S中要?jiǎng)h除的內(nèi)容是否存在，若存在，則將第i+j-1之后的字符前移j個(gè)位置。算法如

34、下： ⑷ 對(duì)于采用順序存儲(chǔ)結(jié)構(gòu)的串S，編寫一個(gè)函數(shù)刪除其值等于ch的所有字符。 【解答】從后向前刪除值為ch的所有元素，這樣所有移動(dòng)的元素中沒有值為ch的元素，能減少移動(dòng)元素的次數(shù)，提高算法的效率。算法如下： ⑸ 對(duì)串的模式匹配KMP算法設(shè)計(jì)求模式滑動(dòng)位置的next函數(shù)。 【解答】參見3.2.5 學(xué)習(xí)自測及答案 1．在一個(gè)具有n個(gè)單元的順序棧中，假定以地址低端（即下標(biāo)為0的單元）作為棧底，以top作為棧頂指針，當(dāng)出棧時(shí)，top的變化為（ ）。 A 不變 B top=0; C top=top-1; D top=top+1; 【解答】C 2．一個(gè)棧的入棧序列是a, b,

35、 c, d, e，則棧的不可能的出棧序列是（ ）。 A edcba B cdeba C debca D abcde 【解答】C 3．從棧頂指針為top的鏈棧中刪除一個(gè)結(jié)點(diǎn)，用x保存被刪除結(jié)點(diǎn)的值，則執(zhí)行（ ）。 A x=top; top=top->next; B x=top->data; C top=top->next; x=top->data; D x=top->data; top=top->next; 【解答】D 4．設(shè)元素1, 2, 3, P, A依次經(jīng)過一個(gè)棧，進(jìn)棧次序?yàn)?23PA，在棧的輸出序列中，有哪些序列可作為C++程序設(shè)計(jì)語言的變量名。 【解答】PA321,

36、P3A21, P32A1, P321A, AP321 5.設(shè)S="I_ am_ a_ teacther"，其長度為（ ）。 【解答】15 第 4 章 廣義線性表——多維數(shù)組和廣義表 課后習(xí)題講解 1. 填空 ⑴ 數(shù)組通常只有兩種運(yùn)算：（ ）和（ ），這決定了數(shù)組通常采用（ ）結(jié)構(gòu)來實(shí)現(xiàn)存儲(chǔ)。 【解答】存取，修改，順序存儲(chǔ) 【分析】數(shù)組是一個(gè)具有固定格式和數(shù)量的數(shù)據(jù)集合，在數(shù)組上一般不能做插入、刪除元素的操作。除了初始化和銷毀之外，在數(shù)組中通常只有存取和修改兩種操作。 ⑵ 二維數(shù)組A中行下標(biāo)從10到20，列下標(biāo)從5到10，按行優(yōu)先存儲(chǔ)，每個(gè)元素占4個(gè)存儲(chǔ)單元，A[10][5

37、]的存儲(chǔ)地址是1000，則元素A[15][10]的存儲(chǔ)地址是（ ）。 【解答】1140 【分析】數(shù)組A中每行共有6個(gè)元素，元素A[15][10]的前面共存儲(chǔ)了(15-10)×6+5個(gè)元素，每個(gè)元素占4個(gè)存儲(chǔ)單元，所以，其存儲(chǔ)地址是1000+140=1140。 ⑶ 設(shè)有一個(gè)10階的對(duì)稱矩陣A采用壓縮存儲(chǔ)，A[0][0]為第一個(gè)元素，其存儲(chǔ)地址為d，每個(gè)元素占1個(gè)存儲(chǔ)單元，則元素A[8][5]的存儲(chǔ)地址為（ ）。 【解答】d+41 【分析】元素A[8][5]的前面共存儲(chǔ)了(1+2+…+8)+5=41個(gè)元素。 ⑷ 稀疏矩陣一般壓縮存儲(chǔ)方法有兩種，分別是（ ）和（ ）。 【解答】三元組順

38、序表，十字鏈表 ⑸ 廣義表((a), (((b),c)),(d))的長度是（　　?。疃仁牵ā　　。?，表頭是（　　　），表尾是（　　?。?。 【解答】3，4，(a)，((((b),c)),(d)) ⑹ 已知廣義表LS=(a，(b，c，d)，e)，用Head和Tail函數(shù)取出LS中原子b的運(yùn)算是（ ）。 【解答】Head(Head(Tail(LS))) 2. 選擇題 ⑴ 二維數(shù)組A的每個(gè)元素是由6個(gè)字符組成的串，行下標(biāo)的范圍從0~8，列下標(biāo)的范圍是從0~9，則存放A至少需要（　　?。﹤€(gè)字節(jié)，A的第8列和第5行共占（　　?。﹤€(gè)字節(jié)，若A按行優(yōu)先方式存儲(chǔ)，元素A[8][5]的起始地址與當(dāng)

39、A按列優(yōu)先方式存儲(chǔ)時(shí)的（ ）元素的起始地址一致。 A 90 B 180 C 240 D 540 E 108 F 114 G 54 H A[8][5] I A[3][10] J A[5][8] K A[4][9] 【解答】D，E，K 【分析】數(shù)組A為9行10列，共有90個(gè)元素，所以，存放A至少需要90×6=540個(gè)存儲(chǔ)單元，第8列和第5行共有18個(gè)元素（注意行列有一個(gè)交叉元素），所以，共占108個(gè)字節(jié)，元素A[8][5]按行優(yōu)先存儲(chǔ)的起始地址為d+8×10+5=d+85，設(shè)元素A[i][j]按列優(yōu)先存儲(chǔ)的起始地址與之相同，則d+j×9+i=d+85，解此方程，得i=4，j=9。 ⑵

40、將數(shù)組稱為隨機(jī)存取結(jié)構(gòu)是因?yàn)椋ā　　。? A 數(shù)組元素是隨機(jī)的 B 對(duì)數(shù)組任一元素的存取時(shí)間是相等的 C 隨時(shí)可以對(duì)數(shù)組進(jìn)行訪問 D 數(shù)組的存儲(chǔ)結(jié)構(gòu)是不定 【解答】B ⑶ 下面的說法中，不正確的是（　　?。? A 數(shù)組是一種線性結(jié)構(gòu) B 數(shù)組是一種定長的線性結(jié)構(gòu) C 除了插入與刪除操作外，數(shù)組的基本操作還有存取、修改、檢索和排序等 D 數(shù)組的基本操作有存取、修改、檢索和排序等，沒有插入與刪除操 【解答】C 【分析】數(shù)組屬于廣義線性表，數(shù)組被創(chuàng)建以后，其維數(shù)和每維中的元素個(gè)數(shù)是確定的，所以，數(shù)組通常沒有插入和刪除操作。 ⑷ 對(duì)特殊矩陣采用壓縮存儲(chǔ)的目的主要是為了（　　?。? A

41、 表達(dá)變得簡單 B 對(duì)矩陣元素的存取變得簡單 C 去掉矩陣中的多余元素 D 減少不必要的存儲(chǔ)空間 【解答】D 【分析】在特殊矩陣中，有很多值相同的元素并且他們的分布有規(guī)律，沒有必要為值相同的元素重復(fù)存儲(chǔ)。 ⑸ 下面（　　　）不屬于特殊矩陣。 A 對(duì)角矩陣 B 三角矩陣 C 稀疏矩陣 D 對(duì)稱矩陣 【解答】C ⑹ 若廣義表A滿足Head(A)=Tail(A)，則A為（ ） A ( ) B (( )) C (( ),( )) D(( ),( ),( )) 【解答】B ⑺ 下面的說法中，不正確的是（　　　） A 廣義表是一種多層次的結(jié)構(gòu) B 廣義表是一種非線性結(jié)構(gòu) C 廣義

42、表是一種共享結(jié)構(gòu) D 廣義表是一種遞歸 【解答】B 【分析】從各層元素各自具有的線性關(guān)系講，廣義表屬于線性結(jié)構(gòu)。 ⑻ 下面的說法中，不正確的是（　　　） A 對(duì)稱矩陣只須存放包括主對(duì)角線元素在內(nèi)的下（或上）三角的元素即可。 B 對(duì)角矩陣只須存放非零元素即可。 C 稀疏矩陣中值為零的元素較多，因此可以采用三元組表方法存儲(chǔ)。 D 稀疏矩陣中大量值為零的元素分布有規(guī)律，因此可以采用三元組表方法存儲(chǔ) 【解答】D 【分析】稀疏矩陣中大量值為零的元素分布沒有規(guī)律，因此采用三元組表存儲(chǔ)。如果零元素的分布有規(guī)律，就沒有必要存儲(chǔ)非零元素的行號(hào)和列號(hào)，而需要按其壓縮規(guī)律找出相應(yīng)的映象函數(shù)。 3

43、. 判斷題 ⑴ 數(shù)組是一種復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，數(shù)組元素之間的關(guān)系既不是線性的，也不是樹形的。 【解答】錯(cuò)。例如二維數(shù)組可以看成是數(shù)據(jù)元素為線性表的線性表。 ⑵ 使用三元組表存儲(chǔ)稀疏矩陣的元素，有時(shí)并不能節(jié)省存儲(chǔ)空間。 【解答】對(duì)。因?yàn)槿M表除了存儲(chǔ)非零元素值外，還需要存儲(chǔ)其行號(hào)和列號(hào)。 ⑶ 稀疏矩陣壓縮存儲(chǔ)后，必會(huì)失去隨機(jī)存取功能。 【解答】對(duì)。因?yàn)閴嚎s存儲(chǔ)后，非零元素的存儲(chǔ)位置和行號(hào)、列號(hào)之間失去了確定的關(guān)系。 ⑷ 線性表可以看成是廣義表的特例，如果廣義表中的每個(gè)元素都是單元素，則廣義表便成為線性表。 【解答】對(duì)。 ⑸ 若一個(gè)廣義表的表頭為空表，則此廣義表亦為空表。 【解答

44、】錯(cuò)。如廣義表L=(( )，(a，b))的表頭為空表，但L不是空表。 4．一個(gè)稀疏矩陣如圖4-4所示，寫出對(duì)應(yīng)的三元組順序表和十字鏈表存儲(chǔ)表示。 【解答】對(duì)應(yīng)的三元組順序表如圖4-5所示，十字鏈表如圖4-6所示。 5．已知A為稀疏矩陣，試從空間和時(shí)間角度比較采用二維數(shù)組和三元組順序表兩種不同的存儲(chǔ)結(jié)構(gòu)完成求 運(yùn)算的優(yōu)缺點(diǎn)。 【解答】設(shè)稀疏矩陣為m行n列，如果采用二維數(shù)組存儲(chǔ)，其空間復(fù)雜度為Ｏ(m×n)；因?yàn)橐獙⑺械木仃囋乩奂悠饋?，所以，需要用一個(gè)兩層的嵌套循環(huán)，其時(shí)間復(fù)雜度亦為Ｏ(m×n)。如果采用三元組順序表進(jìn)行壓縮存儲(chǔ)，假設(shè)矩陣中有t個(gè)非零元素，其空間復(fù)雜度為Ｏ

45、(t)，將所有的矩陣元素累加起來只需將三元組順序表掃描一遍，其時(shí)間復(fù)雜度亦為Ｏ(t)。當(dāng)t << m×n時(shí)，采用三元組順序表存儲(chǔ)可獲得較好的時(shí)、空性能。 6．設(shè)某單位職工工資表ST由“工資”、“扣除”和“實(shí)發(fā)金額”三項(xiàng)組成，其中工資項(xiàng)包括“基本工資”、“津貼”和“獎(jiǎng)金”，扣除項(xiàng)包括“水”、“電”和“煤氣” 。 ⑴ 請(qǐng)用廣義表形式表示所描述的工資表ST，并用表頭和表尾求表中的“獎(jiǎng)金”項(xiàng)； ⑵ 畫出該工資表ST的存儲(chǔ)結(jié)構(gòu)。 【解答】⑴ ST=((基本工資，津貼，獎(jiǎng)金)，(水，電，煤氣)，實(shí)發(fā)金額) Head(Tail(Tail(Head(ST))))=獎(jiǎng)金 ⑵ 工資表ST的頭尾表示法如

46、圖4-7所示。 7．若在矩陣A中存在一個(gè)元素ai,j（0≤i≤n-1，0≤j≤m-1），該元素是第i行元素中最小值且又是第j列元素中最大值，則稱此元素為該矩陣的一個(gè)馬鞍點(diǎn)。假設(shè)以二維數(shù)組存儲(chǔ)矩陣A，試設(shè)計(jì)一個(gè)求該矩陣所有馬鞍點(diǎn)的算法，并分析最壞情況下的時(shí)間復(fù)雜度。 【解答】在矩陣中逐行尋找該行中的最小值，然后對(duì)其所在的列尋找最大值，如果該列上的最大值與該行上的最小值相等，則說明該元素是鞍點(diǎn)，將它所在行號(hào)和列號(hào)輸出。 具體算法如下： 分析算法，外層for循環(huán)共執(zhí)行n次，內(nèi)層第一個(gè)for循環(huán)執(zhí)行m次，第二個(gè)for循環(huán)最壞情況下執(zhí)行n次，所以，最壞情況下的時(shí)間復(fù)雜度為Ｏ(mn+n

47、2)。 學(xué)習(xí)自測及答案 (沒看) 1．二維數(shù)組M中每個(gè)元素的長度是3個(gè)字節(jié)，行下標(biāo)從0到7，列下標(biāo)從0到9，從首地址d開始存儲(chǔ)。若按行優(yōu)先方式存儲(chǔ)，元素M[7][5]的起始地址為（　　 ），若按列優(yōu)先方式存儲(chǔ)，元素M[7][5]的起始地址為（　　 ）。 【解答】d+22，d+141 2．一個(gè)n×n的對(duì)稱矩陣，按行優(yōu)先或列優(yōu)先進(jìn)行壓縮存儲(chǔ)，則其存儲(chǔ)容量為（　　 ）。 【解答】n(n+1)/2 3．設(shè)n行n列的下三角矩陣A（行列下標(biāo)均從1開始）已壓縮到一維數(shù)組S[1]~S[n(n+1)/2]中，若按行優(yōu)先存儲(chǔ)，則A[i][j]在數(shù)組S中的存儲(chǔ)位置是（ ）。 【解答】i×(i-1)

48、/2+j 4．已知廣義表LS=(a, (b, c), (d, e, a))，運(yùn)用Head函數(shù)和Tail函數(shù)取出LS中原子d的運(yùn)算是（　　 ）。 【解答】Head(Head(Tail(Tail(LS)))) 5．廣義表(a, b, (c, (d)))的表尾是（ ）。 A (d) B (c,(d)) C b,(c,(d)) D (b,(c,(d))) 【解答】D 6．設(shè)有三對(duì)角矩陣An×n（行、列下標(biāo)均從0開始），將其三條對(duì)角線上的元素逐行存于數(shù)組B[3n-2]中，使得B[k]=aij求： ⑴ 用i, j表示k的下標(biāo)變換公式； ⑵ 用k表示i, j的下標(biāo)變換公式。 【解答】⑴ 要

49、求i, j表示k的下標(biāo)變換公式，就是要求在k之前已經(jīng)存儲(chǔ)了多少個(gè)非零元素，這些非零元素的個(gè)數(shù)就是k的值。元素aij求所在的行為i，列為j，則在其前面的非零元素的個(gè)數(shù)是；k=2 + 3(i－1)+( j－i + 1)= 2i+ j。 ⑵ 因?yàn)閗和i, j之間是一一對(duì)應(yīng)的關(guān)系，k+1是當(dāng)前非零元素的個(gè)數(shù)，整除即為其所在行號(hào)，取余表示當(dāng)前行中第幾個(gè)非零元素，加上前面零元素所在列數(shù)就是當(dāng)前列號(hào)，即： 7．已知兩個(gè)n×n的對(duì)稱矩陣按壓縮存儲(chǔ)方法存儲(chǔ)在已維數(shù)組A和B中，編寫算法計(jì)算對(duì)稱矩陣的乘積。 【解答】對(duì)稱矩陣采用壓縮存儲(chǔ)，乘積矩陣也采用壓縮存儲(chǔ)。注意矩陣元素的表示方法。 第 5 章

50、樹和二叉樹 課后習(xí)題講解 1. 填空題 ⑴ 樹是n（n≥0）結(jié)點(diǎn)的有限集合，在一棵非空樹中，有（ ）個(gè)根結(jié)點(diǎn)，其余的結(jié)點(diǎn)分成m（m＞0）個(gè)（ ）的集合，每個(gè)集合都是根結(jié)點(diǎn)的子樹。 【解答】有且僅有一個(gè)，互不相交 ⑵ 樹中某結(jié)點(diǎn)的子樹的個(gè)數(shù)稱為該結(jié)點(diǎn)的（ ），子樹的根結(jié)點(diǎn)稱為該結(jié)點(diǎn)的（ ），該結(jié)點(diǎn)稱為其子樹根結(jié)點(diǎn)的（ ）。 【解答】度，孩子，雙親 ⑶ 一棵二叉樹的第i（i≥1）層最多有（ ）個(gè)結(jié)點(diǎn)；一棵有n（n>0）個(gè)結(jié)點(diǎn)的滿二叉樹共有（ ）個(gè)葉子結(jié)點(diǎn)和（ ）個(gè)非終端結(jié)點(diǎn)。 【解答】2i-1，(n+1)/2，(n-1)/2 【分析】設(shè)滿二叉樹中葉子結(jié)點(diǎn)的個(gè)數(shù)為n

51、0，度為2的結(jié)點(diǎn)個(gè)數(shù)為n2，由于滿二叉樹中不存在度為1的結(jié)點(diǎn)，所以n=n0+n2；由二叉樹的性質(zhì)n0=n2+1，得n0=(n+1)/2，n2=(n-1)/2。 ⑷ 設(shè)高度為h的二叉樹上只有度為0和度為2的結(jié)點(diǎn)，該二叉樹的結(jié)點(diǎn)數(shù)可能達(dá)到的最大值是（ ），最小值是（ ）。 【解答】2h -1，2h-1 【分析】最小結(jié)點(diǎn)個(gè)數(shù)的情況是第1層有1個(gè)結(jié)點(diǎn)，其他層上都只有2個(gè)結(jié)點(diǎn)。 ⑸ 深度為k的二叉樹中，所含葉子的個(gè)數(shù)最多為（ ）。 【解答】2k-1 【分析】在滿二叉樹中葉子結(jié)點(diǎn)的個(gè)數(shù)達(dá)到最多。 ⑹ 具有100個(gè)結(jié)點(diǎn)的完全二叉樹的葉子結(jié)點(diǎn)數(shù)為（ ）。 【解答】50 【分析】1

52、00個(gè)結(jié)點(diǎn)的完全二叉樹中最后一個(gè)結(jié)點(diǎn)的編號(hào)為100，其雙親即最后一個(gè)分支結(jié)點(diǎn)的編號(hào)為50，也就是說，從編號(hào)51開始均為葉子。 ⑺ 已知一棵度為3的樹有2個(gè)度為1的結(jié)點(diǎn)，3個(gè)度為2的結(jié)點(diǎn)，4個(gè)度為3的結(jié)點(diǎn)。則該樹中有（ ）個(gè)葉子結(jié)點(diǎn)。 【解答】12 【分析】根據(jù)二叉樹性質(zhì)3的證明過程，有n0=n2+2n3+1（n0、n2、n3分別為葉子結(jié)點(diǎn)、度為2的結(jié)點(diǎn)和度為3的結(jié)點(diǎn)的個(gè)數(shù)）。 ⑻ 某二叉樹的前序遍歷序列是ABCDEFG，中序遍歷序列是CBDAFGE，則其后序遍歷序列是（ ）。 【解答】CDBGFEA 【分析】根據(jù)前序遍歷序列和后序遍歷序列將該二叉樹構(gòu)造出來。 ⑼ 在具

53、有n個(gè)結(jié)點(diǎn)的二叉鏈表中，共有（ ）個(gè)指針域，其中（ ）個(gè)指針域用于指向其左右孩子，剩下的（ ）個(gè)指針域則是空的。 【解答】2n，n-1，n+1 ⑽ 在有n個(gè)葉子的哈夫曼樹中，葉子結(jié)點(diǎn)總數(shù)為（ ），分支結(jié)點(diǎn)總數(shù)為（ ）。 【解答】n，n-1 【分析】n-1個(gè)分支結(jié)點(diǎn)是經(jīng)過n-1次合并后得到的。 2. 選擇題 ⑴ 如果結(jié)點(diǎn)A有3個(gè)兄弟，B是A的雙親，則結(jié)點(diǎn)B的度是（　?。?。 A 1 B 2 C 3 D 4 【解答】D ⑵ 設(shè)二叉樹有n個(gè)結(jié)點(diǎn)，則其深度為（ ）。 A n-1 B n C +1 D 不能確定 【解答】D 【分析】此題并沒有指明是完全二叉樹，則其深

54、度最多是n，最少是 +1。 ⑶ 二叉樹的前序序列和后序序列正好相反，則該二叉樹一定是（ ）的二叉樹。 A 空或只有一個(gè)結(jié)點(diǎn) B 高度等于其結(jié)點(diǎn)數(shù) C 任一結(jié)點(diǎn)無左孩子 D 任一結(jié)點(diǎn)無右孩子 【解答】B 【分析】此題注意是序列正好相反，則左斜樹和右斜樹均滿足條件。 ⑷ 線索二叉樹中某結(jié)點(diǎn)R沒有左孩子的充要條件是（ 　?。? A R.lchild=NULL B R.ltag=0 C R.ltag=1 D R.rchild=NULL 【解答】C 【分析】線索二叉樹中某結(jié)點(diǎn)是否有左孩子，不能通過左指針域是否為空來判斷，而要判斷左標(biāo)志是否為1。 ⑸ 深度為k的完全二叉樹至

55、少有（ ）個(gè)結(jié)點(diǎn)，至多有（ ）個(gè)結(jié)點(diǎn)，具有n個(gè)結(jié)點(diǎn)的完全二叉樹按層序從1開始編號(hào)，則編號(hào)最小的葉子的序號(hào)是（ ）。 A 2k-2+1 B 2k-1 C 2k -1 D 2k–1 -1 E 2k+1 F 2k+1 -1 G 2k -1+1 H 2k 【解答】B，C，A 【分析】深度為k的完全二叉樹最少結(jié)點(diǎn)數(shù)的情況應(yīng)是第k層上只有1個(gè)結(jié)點(diǎn)，最多的情況是滿二叉樹，編號(hào)最小的葉子應(yīng)該是在結(jié)點(diǎn)數(shù)最少的情況下，葉子結(jié)點(diǎn)的編號(hào)。 ⑹ 一個(gè)高度為h的滿二叉樹共有n個(gè)結(jié)點(diǎn)，其中有m個(gè)葉子結(jié)點(diǎn)，則有（ ?。┏闪ⅰ? A n=h+m B h+m=2n C m=h-1 D n=2m-1 【解答】D

56、 【分析】滿二叉樹中沒有度為1的結(jié)點(diǎn)，所以有m個(gè)葉子結(jié)點(diǎn)，則度為2的結(jié)點(diǎn)個(gè)數(shù)為m-1。 ⑺ 任何一棵二叉樹的葉子結(jié)點(diǎn)在前序、中序、后序遍歷序列中的相對(duì)次序（ ）。 A 肯定不發(fā)生改變 B 肯定發(fā)生改變 C 不能確定 D 有時(shí)發(fā)生變化 【解答】A 【分析】三種遍歷次序均是先左子樹后右子樹。 ⑻ 如果T' 是由有序樹T轉(zhuǎn)換而來的二叉樹，那么T中結(jié)點(diǎn)的前序序列就是T' 中結(jié)點(diǎn)的（ ）序列，T中結(jié)點(diǎn)的后序序列就是 T' 中結(jié)點(diǎn)的（　?。┬蛄?。 A 前序 B 中序 C 后序 D 層序 【解答】A，B ⑼ 設(shè)森林中有4棵樹，樹中結(jié)點(diǎn)的個(gè)數(shù)依次為n1、n2、n3、n4，則把森林

57、轉(zhuǎn)換成二叉樹后，其根結(jié)點(diǎn)的右子樹上有（ ）個(gè)結(jié)點(diǎn)，根結(jié)點(diǎn)的左子樹上有（ ）個(gè)結(jié)點(diǎn)。 A n1-1 B n1 C n1+n2+n3 D n2+n3+n4 【解答】D，A 【分析】由森林轉(zhuǎn)換的二叉樹中，根結(jié)點(diǎn)即為第一棵樹的根結(jié)點(diǎn)，根結(jié)點(diǎn)的左子樹是由第一棵樹中除了根結(jié)點(diǎn)以外其余結(jié)點(diǎn)組成的，根結(jié)點(diǎn)的右子樹是由森林中除第一棵樹外其他樹轉(zhuǎn)換來的。 ⑽ 討論樹、森林和二叉樹的關(guān)系，目的是為了（ ）。 A 借助二叉樹上的運(yùn)算方法去實(shí)現(xiàn)對(duì)樹的一些運(yùn)算 B 將樹、森林按二叉樹的存儲(chǔ)方式進(jìn)行存儲(chǔ)并利用二叉樹的算法解決樹的有關(guān)問題 C 將樹、森林轉(zhuǎn)換成二叉樹 D 體現(xiàn)一種技巧，沒有什么實(shí)際意義

58、【解答】B 3. 判斷題 ⑴ 在線索二叉樹中，任一結(jié)點(diǎn)均有指向其前驅(qū)和后繼的線索。 【解答】錯(cuò)。某結(jié)點(diǎn)是否有前驅(qū)或后繼的線索，取決于該結(jié)點(diǎn)的標(biāo)志域是否為1。 ⑵ 在二叉樹的前序遍歷序列中，任意一個(gè)結(jié)點(diǎn)均處在其子女的前面。 【解答】對(duì)。由前序遍歷的操作定義可知。 ⑶ 二叉樹是度為2的樹。 【解答】錯(cuò)。二叉樹和樹是兩種不同的樹結(jié)構(gòu)，例如，左斜樹是一棵二叉樹，但它的度為1。 ⑷ 由樹轉(zhuǎn)換成二叉樹，其根結(jié)點(diǎn)的右子樹總是空的。 【解答】對(duì)。因?yàn)楦Y(jié)點(diǎn)無兄弟結(jié)點(diǎn)。 ⑸ 用一維數(shù)組存儲(chǔ)二叉樹時(shí)，總是以前序遍歷存儲(chǔ)結(jié)點(diǎn)。 【解答】錯(cuò)。二叉樹的順序存儲(chǔ)結(jié)構(gòu)是按層序存儲(chǔ)的

59、，一般適合存儲(chǔ)完全二叉樹。 4．證明：對(duì)任一滿二叉樹，其分枝數(shù)B＝2(n0-1) 。（其中，n0為終端結(jié)點(diǎn)數(shù)） 【解答】因?yàn)樵跐M二叉樹中沒有度為1的結(jié)點(diǎn)，所以有： n=n0+n2 設(shè)B為樹中分枝數(shù)，則 n=B+1 所以 B=n0 +n2-1 再由二叉樹性質(zhì)： n0=n2+1 代入上式有： B=n0+n0-1-1=2(n0-1) 5．證明：已知一棵二叉樹的前序序列和中序序列，則可唯一確定該二叉樹。 【解答】證明采用歸納法。 設(shè)二叉樹的前序遍歷序列為a1a2a3… an，中序遍歷序列為b1b2b3… bn。 當(dāng)n=1時(shí)，前序遍歷序列為a1，中序遍歷序列為b1

60、，二叉樹只有一個(gè)根結(jié)點(diǎn)，所以，a1= b1，可以唯一確定該二叉樹； 假設(shè)當(dāng)n<=k時(shí)，前序遍歷序列a1a2a3… ak和中序遍歷序列b1b2b3… bk可唯一確定該二叉樹，下面證明當(dāng)n=k+1時(shí)，前序遍歷序列a1a2a3… akak+1和中序遍歷序列b1b2b3… bk bk+1可唯一確定一棵二叉樹。 在前序遍歷序列中第一個(gè)訪問的一定是根結(jié)點(diǎn)，即二叉樹的根結(jié)點(diǎn)是a1，在中序遍歷序列中查找值為a1的結(jié)點(diǎn)，假設(shè)為bi，則a1=bi且b1b2… bi-1是對(duì)根結(jié)點(diǎn)a1的左子樹進(jìn)行中序遍歷的結(jié)果，前序遍歷序列a2a3… ai是對(duì)根結(jié)點(diǎn)a1的左子樹進(jìn)行前序遍歷的結(jié)果，由歸納假設(shè)，前序遍歷序列a2a3

61、… ai和中序遍歷序列b1b2… bi-1唯一確定了根結(jié)點(diǎn)的左子樹，同樣可證前序遍歷序列ai+1ai+2… ak+1和中序遍歷序列bi+1bi+2… bk+1唯一確定了根結(jié)點(diǎn)的右子樹。 6．已知一棵度為m的樹中有：n1個(gè)度為1的結(jié)點(diǎn)，n2個(gè)度為2的結(jié)點(diǎn)，……，nm個(gè)度為m的結(jié)點(diǎn)，問該樹中共有多少個(gè)葉子結(jié)點(diǎn)？ 【解答】設(shè)該樹的總結(jié)點(diǎn)數(shù)為n，則 n=n0+n1+n2+……+nm 又： n=分枝數(shù)+1=0×n0+1×n1+2×n2+……+m×nm+1 由上述兩式可得： n0= n2+2n3+……+(m-1)nm+1 7．已知二叉樹的中序和后序序列分別為CBEDAFIGH和CEDB

62、IFHGA，試構(gòu)造該二叉樹。 【解答】二叉樹的構(gòu)造過程如圖5-12 所示。 8．對(duì)給定的一組權(quán)值W＝（5，2，9，11，8，3，7），試構(gòu)造相應(yīng)的哈夫曼樹，并計(jì)算它的帶權(quán)路徑長度。 【解答】構(gòu)造的哈夫曼樹如圖5-13所示。 樹的帶權(quán)路徑長度為： WPL=2×4+3×4+5×3+7×3+8×3+9×2+11×2 =120 9．已知某字符串S中共有8種字符，各種字符分別出現(xiàn)2次、1次、4次、5次、7次、3次、4次和9次，對(duì)該字符串用[0，1]進(jìn)行前綴編碼，問該字符串的編碼至少有多少位。 【解答】以各字符出現(xiàn)的次數(shù)作為葉子結(jié)點(diǎn)的權(quán)值構(gòu)造的哈夫曼編碼樹如圖5-14所示。其帶

63、權(quán)路徑長度=2×5+1×5+3×4+5×3+9×2+4×3+4×3+7×2=98，所以，該字符串的編碼長度至少為98位。 ? 10．算法設(shè)計(jì) ⑴ 設(shè)計(jì)算法求二叉樹的結(jié)點(diǎn)個(gè)數(shù)。 【解答】本算法不是要打印每個(gè)結(jié)點(diǎn)的值，而是求出結(jié)點(diǎn)的個(gè)數(shù)。所以可將遍歷算法中的“訪問”操作改為“計(jì)數(shù)操作”，將結(jié)點(diǎn)的數(shù)目累加到一個(gè)全局變量中，每個(gè)結(jié)點(diǎn)累加一次即完成了結(jié)點(diǎn)個(gè)數(shù)的求解。 具體算法如下： ⑵ 設(shè)計(jì)算法按前序次序打印二叉樹中的葉子結(jié)點(diǎn)。 【解答】本算法的要求與前序遍歷算法既有相同之處，又有不同之處。相同之處是打印次序均為前序，不同之處是此處不是打印每個(gè)結(jié)點(diǎn)的值，而是打印出其中的葉子結(jié)點(diǎn)，即

64、為有條件打印。為此，將前序遍歷算法中的訪問操作改為條件打印即可。算法如下： ? ⑶ 設(shè)計(jì)算法求二叉樹的深度。 【解答】當(dāng)二叉樹為空時(shí)，深度為0；若二叉樹不為空，深度應(yīng)是其左右子樹深度的最大值加1，而其左右子樹深度的求解又可通過遞歸調(diào)用本算法來完成。具體算法如下： ? ⑷ 編寫算法，要求輸出二叉樹后序遍歷序列的逆序。 【解答】要想得到后序的逆序，只要按照后序遍歷相反的順序即可，即先訪問根結(jié)點(diǎn)，再遍歷根結(jié)點(diǎn)的右子樹，最后遍歷根結(jié)點(diǎn)的左子樹。注意和前序遍歷的區(qū)別，具體算法如下： ⑸ 以二叉鏈表為存儲(chǔ)結(jié)構(gòu)，編寫算法求二叉樹中結(jié)點(diǎn)x的雙親。 【解答】對(duì)二叉鏈表進(jìn)行遍歷，在遍歷

65、的過程中查找結(jié)點(diǎn)x并記載其雙親。具體算法如下： ? ⑹ 以二叉鏈表為存儲(chǔ)結(jié)構(gòu)，在二叉樹中刪除以值x為根結(jié)點(diǎn)的子樹。 【解答】對(duì)二叉鏈表進(jìn)行遍歷，在遍歷的過程中查找結(jié)點(diǎn)x并記載其雙親，然后將結(jié)點(diǎn)x的雙親結(jié)點(diǎn)中指向結(jié)點(diǎn)x的指針置空。具體算法如下： ? ⑺ 一棵具有n個(gè)結(jié)點(diǎn)的二叉樹采用順序存儲(chǔ)結(jié)構(gòu)，編寫算法對(duì)該二叉樹進(jìn)行前序遍歷。 【解答】按照題目要求，設(shè)置一個(gè)工作棧以完成對(duì)該樹的非遞歸算法，思路如下： ① 每訪問一個(gè)結(jié)點(diǎn)，將此結(jié)點(diǎn)壓棧，查看此結(jié)點(diǎn)是否有左子樹，若有，訪問左子樹，重復(fù)執(zhí)行該過程直到左子樹為空。 ② 從棧彈出一個(gè)結(jié)點(diǎn)，如果此結(jié)點(diǎn)有右子樹，訪問右子樹執(zhí)行步驟①，否

66、則重復(fù)執(zhí)行步驟②。 具體算法如下： ⑻ 編寫算法交換二叉樹中所有結(jié)點(diǎn)的左右子樹。 【解答】對(duì)二叉樹進(jìn)行后序遍歷，在遍歷過程中訪問某結(jié)點(diǎn)時(shí)交換該結(jié)點(diǎn)的左右子樹。 具體算法如下： ? ⑼ 以孩子兄弟表示法做存儲(chǔ)結(jié)構(gòu)，求樹中結(jié)點(diǎn)x的第i個(gè)孩子。 【解答】先在鏈表中進(jìn)行遍歷，在遍歷過程中查找值等于x的結(jié)點(diǎn)，然后由此結(jié)點(diǎn)的最左孩子域firstchild找到值為x結(jié)點(diǎn)的第一個(gè)孩子，再沿右兄弟域rightsib找到值為x結(jié)點(diǎn)的第i個(gè)孩子并返回指向這個(gè)孩子的指針。 樹的孩子兄弟表示法中的結(jié)點(diǎn)結(jié)構(gòu)定義如下： template struct TNode { T data; TNode *firstchild, *rightsib; }; 具體算法如下： 學(xué)習(xí)自測及答案 1．前序遍歷和中序遍歷結(jié)果相同的二叉樹是（ ）。 A 根結(jié)點(diǎn)無左孩子的二叉樹 B 根結(jié)點(diǎn)無右孩子的二叉樹 C 所有結(jié)點(diǎn)只有左子樹的二叉樹 D 所有結(jié)點(diǎn)只有右子樹的二叉樹 【解答】D 1．前序遍歷和中序遍歷結(jié)果相同的二叉樹是（ ）。 A 根結(jié)點(diǎn)無左孩子的二叉樹 B 根結(jié)點(diǎn)無右孩子的二