數(shù)據(jù)結(jié)構(gòu)(殷人昆)練習(xí)題答案附在后邊

1、第一章 緒論1-1什么是數(shù)據(jù)? 它與信息是什么關(guān)系?1-2什么是數(shù)據(jù)結(jié)構(gòu)? 有關(guān)數(shù)據(jù)結(jié)構(gòu)的討論涉及哪三個方面?1-3數(shù)據(jù)的邏輯結(jié)構(gòu)分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)兩大類。線性結(jié)構(gòu)包括數(shù)組、鏈表、 棧、隊列、優(yōu)先級隊列等; 非線性結(jié)構(gòu)包括樹、圖等、這兩類結(jié)構(gòu)各自的特點是什么？1-4什么是抽象數(shù)據(jù)類型？試用C+的類聲明定義“復(fù)數(shù)”的抽象數(shù)據(jù)類型。要求(1) 在復(fù)數(shù)內(nèi)部用浮點數(shù)定義它的實部和虛部。(2) 實現(xiàn)3個構(gòu)造函數(shù)：缺省的構(gòu)造函數(shù)沒有參數(shù)；第二個構(gòu)造函數(shù)將雙精度浮點數(shù)賦給復(fù)數(shù)的實部，虛部置為0；第三個構(gòu)造函數(shù)將兩個雙精度浮點數(shù)分別賦給復(fù)數(shù)的實部和虛部。(3) 定義獲取和修改復(fù)數(shù)的實部和虛部，以及+、-

2、、*、/等運算的成員函數(shù)。(4) 定義重載的流函數(shù)來輸出一個復(fù)數(shù)。1-5 用歸納法證明：(1) (2) (3) 1-6 什么是算法? 算法的5個特性是什么? 試根據(jù)這些特性解釋算法與程序的區(qū)別。1-7 設(shè)n為正整數(shù), 分析下列各程序段中加下劃線的語句的程序步數(shù)。 (1) for (int i = 1; i <= n; i+) (2) x = 0; y = 0; for (int j = 1; j <= n; j+) for (int i = 1; i <= n; i+) cij = 0.0; for (int j = 1; j <= i; j+) for (int k

3、= 1; k <= n; k+) for (int k = 1; k <= j; k+) cij = cij + aik * bkj; x = x + y; (3) int i = 1, j = 1; (4) int i =1; while (i<=n && j<=n) do i = i + 1; j = j + i; for (int j = 1; j <= n; j+) i = i + j; while ( i < 100 + n );1-8 試編寫一個函數(shù)計算n!*2n的值，結(jié)果存放于數(shù)組AarraySize的第n個數(shù)組元素中，0 &#

4、163; n £ arraySize。若設(shè)計算機中允許的整數(shù)的最大值為maxInt，則當(dāng)n > arraySize或者對于某一個k (0 £ k £ n)，使得k!*2k > maxInt時，應(yīng)按出錯處理?？捎腥缦氯N不同的出錯處理方式：(1) 用cerr<<及exit (1)語句來終止執(zhí)行并報告錯誤；(2) 用返回整數(shù)函數(shù)值0, 1來實現(xiàn)算法，以區(qū)別是正常返回還是錯誤返回；(3) 在函數(shù)的參數(shù)表設(shè)置一個引用型的整型變量來區(qū)別是正常返回還是某種錯誤返回。試討論這三種方法各自的優(yōu)缺點，并以你認為是最好的方式實現(xiàn)它。1-9 (1) 在下面所給函

5、數(shù)的適當(dāng)?shù)胤讲迦胗嬎鉩ount的語句：void d (ArrayElement x , int n ) int i = 1; do xi += 2; i +=2; while (i <= n ); i = 1; while ( i <= (n/2) ) xi += xi+1; i+; (2) 將由(1)所得到的程序化簡。使得化簡后的程序與化簡前的程序具有相同的count值。(3) 程序執(zhí)行結(jié)束時的count值是多少？(4) 使用執(zhí)行頻度的方法計算這個程序的程序步數(shù)，畫出程序步數(shù)統(tǒng)計表。 1-10 設(shè)有3個值大小不同的整數(shù)a、b和c，試求(1) 其中值最大的整數(shù)；(2) 其中值最小的

6、整數(shù)；(3) 其中位于中間值的整數(shù)。第二章 數(shù)組2-1作為抽象數(shù)據(jù)類型數(shù)組的類聲明。#include <iostream.h>/在頭文件“array.h”中#include <stdlib.h>const int DefaultSize = 30;template <class Type> class Array /數(shù)組是數(shù)據(jù)類型相同的n（size）個元素的一個集合, 下標范圍從0到n-1。對數(shù)組中元素/可按下標所指示位置直接訪問。private: Type *elements;/數(shù)組 int ArraySize;/元素個數(shù)public: Array ( i

7、nt Size = DefaultSize );/構(gòu)造函數(shù) Array ( const Array<Type> & x );/復(fù)制構(gòu)造函數(shù) Array ( ) delete elements; /析構(gòu)函數(shù) Array<Type> & operator = ( const Array<Type> & A );/數(shù)組整體賦值 (復(fù)制) Type& operator ( int i );/按下標訪問數(shù)組元素 int Length ( ) const return ArraySize; /取數(shù)組長度 void ReSize ( int

8、 sz );/修改數(shù)組長度順序表的類定義#include < iostream.h>/定義在頭文件“seqlist.h”中#include <stdlib.h>template <class Type> class SeqList private: Type *data;/順序表的存放數(shù)組 int MaxSize;/順序表的最大可容納項數(shù) int last;/順序表當(dāng)前已存表項的最后位置 int current;/順序表的當(dāng)前指針（最近處理的表項）public: SeqList ( int MaxSize );/構(gòu)造函數(shù) SeqList ( ) delete

9、 data; /析構(gòu)函數(shù) int Length ( ) const return last+1; /計算表長度 int Find ( Type& x ) const;/定位函數(shù): 找x在表中位置，置為當(dāng)前表項 int IsIn ( Type& x );/判斷x是否在表中，不置為當(dāng)前表項 Type *GetData ( ) return current = -1？NULL : datacurrent; /取當(dāng)前表項的值 int Insert ( Type& x );/插入x在表中當(dāng)前表項之后，置為當(dāng)前表項 int Append ( Type& x );/追加x到表

10、尾，置為當(dāng)前表項 Type * Remove ( Type& x );/刪除x，置下一表項為當(dāng)前表項 Type * First ( ); /取表中第一個表項的值，置為當(dāng)前表項 Type * Next ( ) return current < last ? &data+current : NULL; /取當(dāng)前表項的后繼表項的值，置為當(dāng)前表項 Type * Prior ( ) return current > 0 ? &data-current : NULL; /取當(dāng)前表項的前驅(qū)表項的值，置為當(dāng)前表項 int IsEmpty ( ) return last =

11、-1; /判斷順序表空否, 空則返回1; 否則返回0 int IsFull ( ) return last = MaxSize-1; /判斷順序表滿否, 滿則返回1; 否則返回02-1 設(shè)n個人圍坐在一個圓桌周圍，現(xiàn)在從第s個人開始報數(shù)，數(shù)到第m個人，讓他出局；然后從出局的下一個人重新開始報數(shù)，數(shù)到第m個人，再讓他出局，如此反復(fù)直到所有的人全部出局為止。下面要解決的Josephus問題是：對于任意給定的n, s和m，求出這n個人的出局序列。請以n = 9, s = 1, m = 5為例，人工模擬Josephus的求解過程以求得問題的解。2-2 試編寫一個求解Josephus問題的函數(shù)。用整數(shù)序

12、列1, 2, 3, , n表示順序圍坐在圓桌周圍的人，并采用數(shù)組表示作為求解過程中使用的數(shù)據(jù)結(jié)構(gòu)。然后使用n = 9, s = 1, m = 5，以及n = 9, s = 1, m = 0，或者n = 9, s = 1, m = 10作為輸入數(shù)據(jù)，檢查你的程序的正確性和健壯性。最后分析所完成算法的時間復(fù)雜度。2-3 設(shè)有一個線性表 (e0, e1, , en-2, en-1) 存放在一個一維數(shù)組AarraySize中的前n個數(shù)組元素位置。請編寫一個函數(shù)將這個線性表原地逆置，即將數(shù)組的前n個原址內(nèi)容置換為 (en-1, en-2, , e1, e0)。2-4 假定數(shù)組AarraySize中有多個

13、零元素, 試寫出一個函數(shù), 將A 中所有的非零元素依次移到數(shù)組A的前端Ai（0£ i £ arraySize）。2-5 順序表的插入和刪除要求仍然保持各個元素原來的次序。設(shè)在等概率情形下, 對有127個元素的順序表進行插入, 平均需要移動多少個元素? 刪除一個元素, 又平均需要移動多少個元素?2-6 若矩陣Am´n中的某一元素Aij是第i行中的最小值，同時又是第j列中的最大值，則稱此元素為該矩陣的一個鞍點。假設(shè)以二維數(shù)組存放矩陣，試編寫一個函數(shù)，確定鞍點在數(shù)組中的位置（若鞍點存在時），并分析該函數(shù)的時間復(fù)雜度。2-7 設(shè)有一個二維數(shù)組Amn，假設(shè)A00存放位置在6

14、44(10)，A22存放位置在676(10)，每個元素占一個空間，問A33(10)存放在什么位置？腳注(10)表示用10進制表示。2-8 利用順序表的操作，實現(xiàn)以下的函數(shù)。(1) 從順序表中刪除具有最小值的元素并由函數(shù)返回被刪元素的值?？粘龅奈恢糜勺詈笠粋€元素填補，若順序表為空則顯示出錯信息并退出運行。 (2) 從順序表中刪除第i個元素并由函數(shù)返回被刪元素的值。如果i不合理或順序表為空則顯示出錯信息并退出運行。(3) 向順序表中第i個位置插入一個新的元素x。如果i不合理則顯示出錯信息并退出運行。(4) 從順序表中刪除具有給定值x的所有元素。(5) 從順序表中刪除其值在給定值s與t之間（要求s小

15、于t）的所有元素，如果s或t不合理或順序表為空則顯示出錯信息并退出運行。(6) 從有序順序表中刪除其值在給定值s與t之間（要求s小于t）的所有元素，如果s或t不合理或順序表為空則顯示出錯信息并退出運行。(7) 將兩個有序順序表合并成一個新的有序順序表并由函數(shù)返回結(jié)果順序表。(8) 從順序表中刪除所有其值重復(fù)的元素，使表中所有元素的值均不相同。2-9 設(shè)有一個n´n的對稱矩陣A，如圖(a)所示。為了節(jié)約存儲，可以只存對角線及對角線以上的元素，或者只存對角線或?qū)蔷€以下的元素。前者稱為上三角矩陣，后者稱為下三角矩陣。我們把它們按行存放于一個一維數(shù)組B中，如圖(b)和圖(c)所示。并稱之為

16、對稱矩陣A的壓縮存儲方式。試問：(1) 存放對稱矩陣A上三角部分或下三角部分的一維數(shù)組B有多少元素？(2) 若在一維數(shù)組B中從0號位置開始存放，則如圖(a)所示的對稱矩陣中的任一元素aij在只存上三角部分的情形下(圖(b)應(yīng)存于一維數(shù)組的什么下標位置？給出計算公式。(3) 若在一維數(shù)組B中從0號位置開始存放，則如圖(a)所示的對稱矩陣中的任一元素aij在只存下三角部分的情形下(圖(c)應(yīng)存于一維數(shù)組的什么下標位置？給出計算公式。2-10 設(shè)A和B均為下三角矩陣，每一個都有n行。因此在下三角區(qū)域中各有n(n+1)/2個元素。另設(shè)有一個二維數(shù)組C，它有n行n+1列。試設(shè)計一個方案，將兩個矩陣A和B

17、中的下三角區(qū)域元素存放于同一個C中。要求將A的下三角區(qū)域中的元素存放于C的下三角區(qū)域中，B的下三角區(qū)域中的元素轉(zhuǎn)置后存放于C的上三角區(qū)域中。并給出計算A的矩陣元素aij和B的矩陣元素bij在C中的存放位置下標的公式。2-11 在實際應(yīng)用中經(jīng)常遇到的稀疏矩陣是三對角矩陣，如右圖所示。在該矩陣中除主對角線及在主對角線上下最臨近的兩條對角線上的元素外，所有其它元素均為0?，F(xiàn)在要將三對角矩陣A中三條對角線上的元素按行存放在一維數(shù)組B中，且a11存放于B0。試給出計算A在三條對角線上的元素aij （1£ i £ n, i-1 £ j £ i+1）在一維數(shù)組B中的存

18、放位置的計算公式。2-12 設(shè)帶狀矩陣是n´n階的方陣，其中所有的非零元素都在由主對角線及主對角線上下各b條對角線構(gòu)成的帶狀區(qū)域內(nèi)，其它都為零元素。試問：(1) 該帶狀矩陣中有多少個非零元素？(2) 若用一個一維數(shù)組B按行順序存放各行的非零元素，且設(shè)a11存放在B0中，請給出一個公式，計算任一非零元素aij在一維數(shù)組B中的存放位置。2-13 稀疏矩陣的三元組表可以用帶行指針數(shù)組的二元組表代替。稀疏矩陣有多少行，在行指針數(shù)組中就有多少個元素：第i個元素的數(shù)組下標i代表矩陣的第i行，元素的內(nèi)容即為稀疏矩陣第i行的第一個非零元素在二元組表中的存放位置。二元組表中每個二元組只記錄非零元素的列

19、號和元素值，且各二元組按行號遞增的順序排列。試對右圖所示的稀疏矩陣，分別建立它的三元組表和帶行指針數(shù)組的二元組表。2-14 字符串的替換操作replace (String &s, String &t, String &v)是指：若t是s的子串，則用串v替換串t在串s中的所有出現(xiàn)；若t不是s的子串，則串s不變。例如，若串s為“aabbabcbaabaaacbab”，串t為“bab”，串v為“abdc”，則執(zhí)行replace操作后，串s中的結(jié)果為“aababdccbaabaaacabdc”。試利用字符串的基本運算實現(xiàn)這個替換操作。2-15 編寫一個算法frequency，統(tǒng)

20、計在一個輸入字符串中各個不同字符出現(xiàn)的頻度。用適當(dāng)?shù)臏y試數(shù)據(jù)來驗證這個算法。2-16 設(shè)串s為“aaab”，串t為“abcabaa”，串r為“abcaabbabcabaacbacba”，試分別計算它們的失效函數(shù)f (j)的值。2-17 設(shè)定整數(shù)數(shù)組Bm+1n+1的數(shù)據(jù)在行、列方向上都按從小到大的順序排序，且整型變量x中的數(shù)據(jù)在B中存在。試設(shè)計一個算法，找出一對滿足Bij = x的i, j值。要求比較次數(shù)不超過m+n。第三章 鏈表單鏈表的結(jié)點類(ListNode class)和鏈表類(List class)的類定義。template <class Type> class List;/

21、前視的類定義template <class Type> class ListNode /鏈表結(jié)點類的定義friend class List<Type>/List類作為友元類定義private: Type data;/數(shù)據(jù)域 ListNode<Type> *link;/鏈指針域public: ListNode ( ) : link (NULL) /僅初始化指針成員的構(gòu)造函數(shù) ListNode ( const Type& item ) : data (item), link (NULL) /初始化數(shù)據(jù)與指針成員的構(gòu)造函數(shù) ListNode<Type

22、> * getNode ( const Type& item, ListNode<Type> *next = NULL ) /以item和next建立一個新結(jié)點 ListNode<Type> * getLink ( ) return link; /取得結(jié)點的下一結(jié)點地址 Type getData ( ) return data; /取得結(jié)點中的數(shù)據(jù) void setLink ( ListNode<Type> * next ) link = next; /修改結(jié)點的link指針 void setData ( Type value ) data =

23、 value; /修改結(jié)點的data值;template <class Type> class List /單鏈表類定義private: ListNode<Type> *first, *current;/鏈表的表頭指針和當(dāng)前元素指針public: List ( const Type& value ) first = current = new ListNode<Type> ( value ); /構(gòu)造函數(shù) List ( ) MakeEmpty ( ); delete first; /析構(gòu)函數(shù) void MakeEmpty ( );/將鏈表置為空表 i

24、nt Length ( ) const;/計算鏈表的長度 ListNode<Type> * Find ( Type value );/搜索含數(shù)據(jù)value的元素并成為當(dāng)前元素 ListNode<Type> * Locate( int i );/搜索第i個元素的地址并置為當(dāng)前元素 Type * GetData ( );/取出表中當(dāng)前元素的值 int Insert ( Type value );/將value插在表當(dāng)前位置之后并成為當(dāng)前元素 Type *Remove ( );/將鏈表中的當(dāng)前元素刪去, 填補者為當(dāng)前元素 ListNode<Type> * Firs

25、ter ( ) current = first; return first; /當(dāng)前指針定位于表頭結(jié)點 Type *First ( );/當(dāng)前指針定位于表中第一個元素并返回其值 Type *Next ( );/將當(dāng)前指針進到表中下一個元素并返回其值 int NotNull ( ) return current != NULL; /表中當(dāng)前元素空否？空返回1, 不空返回0 int NextNotNull ( ) return current != NULL && current->link != NULL; /當(dāng)前元素下一元素空否？空返回1, 不空返回0;3-1線性表可用順

26、序表或鏈表存儲。試問：(1) 兩種存儲表示各有哪些主要優(yōu)缺點?(2) 如果有n個表同時并存，并且在處理過程中各表的長度會動態(tài)發(fā)生變化，表的總數(shù)也可能自動改變、在此情況下，應(yīng)選用哪種存儲表示？為什么？(3) 若表的總數(shù)基本穩(wěn)定，且很少進行插入和刪除，但要求以最快的速度存取表中的元素，這時，應(yīng)采用哪種存儲表示？為什么？3-2 針對帶表頭結(jié)點的單鏈表，試編寫下列函數(shù)。(1) 定位函數(shù)Locate：在單鏈表中尋找第i個結(jié)點。若找到，則函數(shù)返回第i個結(jié)點的地址；若找不到，則函數(shù)返回NULL。(2) 求最大值函數(shù)max：通過一趟遍歷在單鏈表中確定值最大的結(jié)點。(3) 統(tǒng)計函數(shù)number：統(tǒng)計單鏈表中具有

27、給定值x的所有元素。(4) 建立函數(shù)create：根據(jù)一維數(shù)組an建立一個單鏈表，使單鏈表中各元素的次序與an中各元素的次序相同，要求該程序的時間復(fù)雜性為O(n)。(5) 整理函數(shù)tidyup：在非遞減有序的單鏈表中刪除值相同的多余結(jié)點。3-3 設(shè)ha和hb分別是兩個帶表頭結(jié)點的非遞減有序單鏈表的表頭指針, 試設(shè)計一個算法, 將這兩個有序鏈表合并成一個非遞增有序的單鏈表。要求結(jié)果鏈表仍使用原來兩個鏈表的存儲空間, 不另外占用其它的存儲空間。表中允許有重復(fù)的數(shù)據(jù)。3-4 設(shè)有一個表頭指針為h的單鏈表。試設(shè)計一個算法，通過遍歷一趟鏈表，將鏈表中所有結(jié)點的鏈接方向逆轉(zhuǎn)，如下圖所示。要求逆轉(zhuǎn)結(jié)果鏈表的

28、表頭指針h指向原鏈表的最后一個結(jié)點。3-5 從左到右及從右到左遍歷一個單鏈表是可能的，其方法是在從左向右遍歷的過程中將連接方向逆轉(zhuǎn)，如右圖所示。在圖中的指針p指向當(dāng)前正在訪問的結(jié)點，指針pr指向指針p所指結(jié)點的左側(cè)的結(jié)點。此時，指針p所指結(jié)點左側(cè)的所有結(jié)點的鏈接方向都已逆轉(zhuǎn)。(1) 編寫一個算法，從任一給定的位置(pr, p)開始，將指針p右移k個結(jié)點。如果p移出鏈表，則將p置為0，并讓pr停留在鏈表最右邊的結(jié)點上。(2) 編寫一個算法，從任一給定的位置(pr, p)開始，將指針p左移k個結(jié)點。如果p移出鏈表，則將p置為0，并讓pr停留在鏈表最左邊的結(jié)點上。3-6 試寫出用單鏈表表示的字符串類

29、及字符串結(jié)點類的定義，并依次實現(xiàn)它的構(gòu)造函數(shù)、以及計算串長度、串賦值、判斷兩串相等、求子串、兩串連接、求子串在串中位置等7個成員函數(shù)。要求每個字符串結(jié)點中只存放一個字符。3-7 如果用循環(huán)鏈表表示一元多項式，試編寫一個函數(shù)Polynomial : Calc(x)，計算多項式在x處的值。3-8 設(shè)a和b是兩個用帶有表頭結(jié)點的循環(huán)鏈表表示的多項式。試編寫一個算法，計算這兩個多項式的乘積c = a*b，要求計算后多項式a與b保持原狀。如果這兩個多項式的項數(shù)分別為n與m, 試說明該算法的執(zhí)行時間為O(nm2)或O(n2m)。但若a和b是稠密的, 即其很少有系數(shù)為零的項, 那么試說明該乘積算法的時間代價

30、為O(nm)。3-9 計算多項式 Pn (x) = a0 xn + a1 xn-1 + a2 xn-2 + + an-1 x + an的值，通常使用的方法是一種嵌套的方法。它可以描述為如下的迭代形式：b0 = a0 , bi+1 = x * bi + ai+1, i = 0, 1, , n-1。若設(shè)bn = pn （x）. 則問題可以寫為如下形式：Pn (x) = x * Pn-1 (x) + an ，此處， Pn-1 (x) = a0 xn-1 + a1 xn-2 + + an-2 x + an-1，這是問題的遞歸形式。試編寫一個遞歸函數(shù)，計算這樣的多項式的值。3-10 試設(shè)計一個實現(xiàn)下述要

31、求的Locate運算的函數(shù)。設(shè)有一個帶表頭結(jié)點的雙向鏈表L，每個結(jié)點有4個數(shù)據(jù)成員：指向前驅(qū)結(jié)點的指針prior、指向后繼結(jié)點的指針next、存放數(shù)據(jù)的成員data和訪問頻度freq。所有結(jié)點的freq初始時都為0。每當(dāng)在鏈表上進行一次Locate (L, x)操作時，令元素值為x的結(jié)點的訪問頻度freq加1，并將該結(jié)點前移，鏈接到與它的訪問頻度相等的結(jié)點后面，使得鏈表中所有結(jié)點保持按訪問頻度遞減的順序排列，以使頻繁訪問的結(jié)點總是靠近表頭。3-11 利用雙向循環(huán)鏈表的操作改寫2-2題，解決約瑟夫(Josephus)問題。3-12 試設(shè)計一個算法，改造一個帶表頭結(jié)點的雙向鏈表，所有結(jié)點的原有次序

32、保持在各個結(jié)點的rLink域中，并利用lLink域把所有結(jié)點按照其值從小到大的順序連接起來。第四章 棧與隊列4-1 改寫順序棧的進棧成員函數(shù)Push (x )，要求當(dāng)棧滿時執(zhí)行一個stackFull ( )操作進行棧滿處理。其功能是：動態(tài)創(chuàng)建一個比原來的棧數(shù)組大二倍的新數(shù)組，代替原來的棧數(shù)組，原來棧數(shù)組中的元素占據(jù)新數(shù)組的前MaxSize位置。4-2 鐵路進行列車調(diào)度時, 常把站臺設(shè)計成棧式結(jié)構(gòu)的站臺，如右圖所示。試問：(1) 設(shè)有編號為1,2,3,4,5,6的六輛列車, 順序開入棧式結(jié)構(gòu)的站臺, 則可能的出棧序列有多少種?(2) 若進站的六輛列車順序如上所述, 那么是否能夠得到435612,

33、 325641, 154623和135426的出站序列, 如果不能, 說明為什么不能; 如果能, 說明如何得到(即寫出"進棧"或"出棧"的序列)。4-3 試證明：若借助?？捎奢斎胄蛄?, 2, 3, , n得到一個輸出序列p1, p2, p3, , pn (它是輸入序列的某一種排列)，則在輸出序列中不可能出現(xiàn)以下情況，即存在i < j < k，使得pj < pk < pi。(提示：用反證法)0 m-14-4 將編號為0和1的兩個棧存放于一個數(shù)組空間Vm中，棧底分別處于數(shù)組的兩端。當(dāng)?shù)?號棧的棧頂指針top0等于-1時該棧為空，當(dāng)?shù)?/p>

34、1號棧的棧頂指針top1等于m時該棧為空。兩個棧均從兩端向中間增長。當(dāng)向第0號棧插入一個新元素時，使top0增1得到新的棧頂位置，當(dāng)向第1號棧插入一個新元素時，使top1減1得到新的棧頂位置。當(dāng)top0+1 = top1時或top0 = top1-1時，?？臻g滿，此時不能再向任一棧加入新的元素。試定義這種雙棧(Double Stack)結(jié)構(gòu)的類定義，并實現(xiàn)判?？?、判棧滿、插入、刪除算法。4-5 寫出下列中綴表達式的后綴形式：(1) A * B * C(2) - A + B - C + D(3) A* - B + C(4) (A + B) * D + E / (F + A * D) + C(5)

35、 A && B| ! (E > F) /*注：按C+的優(yōu)先級*/(6) !(A && !( (B < C)|(C > D) ) )|(C < E) 4-6 根據(jù)課文中給出的優(yōu)先級，回答以下問題：(1) 在函數(shù)postfix中，如果表達式e含有n個運算符和分界符，問棧中最多可存入多少個元素？(2) 如果表達式e含有n個運算符，且括號嵌套的最大深度為6層，問棧中最多可存入多少個元素？4-7 設(shè)表達式的中綴表示為a * x - b / x2，試利用棧將它改為后綴表示ax * bx2/ -。寫出轉(zhuǎn)換過程中棧的變化。4-8 試利用運算符優(yōu)先數(shù)法，畫

36、出對如下中綴算術(shù)表達式求值時運算符棧和運算對象棧的變化。a + b * (c - d) - ef / g 4-9 假設(shè)以數(shù)組Qm存放循環(huán)隊列中的元素, 同時以rear和length分別指示環(huán)形隊列中的隊尾位置和隊列中所含元素的個數(shù)。試給出該循環(huán)隊列的隊空條件和隊滿條件, 并寫出相應(yīng)的插入(enqueue)和刪除(dlqueue)元素的操作。4-10 假設(shè)以數(shù)組Qm存放循環(huán)隊列中的元素, 同時設(shè)置一個標志tag，以tag = 0和tag = 1來區(qū)別在隊頭指針(front)和隊尾指針(rear)相等時，隊列狀態(tài)為“空”還是“滿”。試編寫與此結(jié)構(gòu)相應(yīng)的插入(enqueue)和刪除(dlqueue)

37、算法。4-11 若使用循環(huán)鏈表來表示隊列，p是鏈表中的一個指針。試基于此結(jié)構(gòu)給出隊列的插入(enqueue)和刪除(dequeue)算法，并給出p為何值時隊列空。4-12 若將一個雙端隊列順序表示在一維數(shù)組Vm中，兩個端點設(shè)為end1和end2，并組織成一個循環(huán)隊列。試寫出雙端隊列所用指針end1和end2的初始化條件及隊空與隊滿條件，并編寫基于此結(jié)構(gòu)的相應(yīng)的插入(enqueue)新元素和刪除(dlqueue)算法。4-13 設(shè)用鏈表表示一個雙端隊列，要求可在表的兩端插入，但限制只能在表的一端刪除。試編寫基于此結(jié)構(gòu)的隊列的插入(enqueue)和刪除(dequeue)算法，并給出隊列空和隊列滿

38、的條件。4-14 試建立一個繼承結(jié)構(gòu)，以棧、隊列和優(yōu)先級隊列為派生類，建立它們的抽象基類Bag類。寫出各個類的聲明。統(tǒng)一命名各派生類的插入操作為Add，刪除操作為Remove，存取操作為Get和Put，初始化操作為MakeEmpty，判空操作為Empty，判滿操作為Full，計數(shù)操作為Length。4-15 試利用優(yōu)先級隊列實現(xiàn)棧和隊列。4-15 所謂回文，是指從前向后順讀和從后向前倒讀都一樣的不含空白字符的串。例如did，madamimadam，pop即是回文。試編寫一個算法，以判斷一個串是否是回文。4-16 設(shè)有一個雙端隊列，元素進入該隊列的順序是1, 2, 3, 4。試分別求出滿足下列條

39、件的輸出序列。(1) 能由輸入受限的雙端隊列得到，但不能由輸出受限的雙端隊列得到的輸出序列；(2) 能由輸出受限的雙端隊列得到，但不能由輸入受限的雙端隊列得到的輸出序列；(3) 既不能由輸入受限的雙端隊列得到，又不能由輸出受限的雙端隊列得到的輸出序列。第五章 遞歸與廣義表5-1 已知An為整數(shù)數(shù)組，試寫出實現(xiàn)下列運算的遞歸算法：(1) 求數(shù)組A中的最大整數(shù)。(2) 求n個整數(shù)的和。(3) 求n個整數(shù)的平均值。5-2 已知Ackerman函數(shù)定義如下：(1) 根據(jù)定義，寫出它的遞歸求解算法；(2) 利用棧，寫出它的非遞歸求解算法。5-3 【背包問題】設(shè)有一個背包可以放入的物品的重量為s，現(xiàn)有n件

40、物品，重量分別為w1, w2, , wn。問能否從這n件物品中選擇若干件放入此背包中，使得放入的重量之和正好為s。如果存在一種符合上述要求的選擇，則稱此背包問題有解(或稱其解為真)；否則稱此背包問題無解(或稱其解為假)。試用遞歸方法設(shè)計求解背包問題的算法。（提示：此背包問題的遞歸定義如下：）5-4 【八皇后問題】設(shè)在初始狀態(tài)下在國際象棋棋盤上沒有任何棋子(皇后)。然后順序在第1行，第2行，。第8行上布放棋子。在每一行中有8個可選擇位置，但在任一時刻，棋盤的合法布局都必須滿足3個限制條件，即任何兩個棋子不得放在棋盤上的同一行、或者同一列、或者同一斜線上。試編寫一個遞歸算法，求解并輸出此問題的所有

41、合法布局。(提示：用回溯法。在第n行第j列安放一個棋子時，需要記錄在行方向、列方向、正斜線方向、反斜線方向的安放狀態(tài)，若當(dāng)前布局合法，可向下一行遞歸求解，否則可移走這個棋子，恢復(fù)安放該棋子前的狀態(tài)，試探本行的第j+1列。)5-5 已知f為單鏈表的表頭指針, 鏈表中存儲的都是整型數(shù)據(jù)，試寫出實現(xiàn)下列運算的遞歸算法：(1) 求鏈表中的最大整數(shù)。(2) 求鏈表的結(jié)點個數(shù)。(3) 求所有整數(shù)的平均值。5-6 畫出下列廣義表的圖形表示和它們的存儲表示：(1) D(A(c), B(e), C(a, L(b, c, d)(2) J1(J2(J1, a, J3(J1), J3(J1) 5-7 利用廣義表的he

42、ad和tail操作寫出函數(shù)表達式，把以下各題中的單元素banana從廣義表中分離出來：(1) L1(apple, pear, banana, orange)(2) L2(apple, pear), (banana, orange)(3) L3(apple), (pear), (banana), (orange)(4) L4(apple), (pear), (banana), orange)(5) L5(apple), pear), banana), orange)(6) L6(apple, (pear, (banana), orange) 5-8 廣義表具有可共享性，因此在遍歷一個廣義表時必需

43、為每一個結(jié)點增加一個標志域mark，以記錄該結(jié)點是否訪問過。一旦某一個共享的子表結(jié)點被作了訪問標志，以后就不再訪問它。(1) 試定義該廣義表的類結(jié)構(gòu)；(2) 采用遞歸的算法對一個非遞歸的廣義表進行遍歷。(3) 試使用一個棧，實現(xiàn)一個非遞歸算法，對一個非遞歸廣義表進行遍歷。第六章 樹與森林6-1 寫出用廣義表表示法表示的樹的類聲明，并給出如下成員函數(shù)的實現(xiàn)：(1) operator >> ( )接收用廣義表表示的樹作為輸入，建立廣義表的存儲表示；(2) 復(fù)制構(gòu)造函數(shù)用另一棵表示為廣義表的樹初始化一棵樹；(3) operator = ( )測試用廣義表表示的兩棵樹是否相等；(4) op

44、erator << ( )用廣義表的形式輸出一棵樹；(5) 析構(gòu)函數(shù)清除一棵用廣義表表示的樹。6-2 列出右圖所示二叉樹的葉結(jié)點、分支結(jié)點和每個結(jié)點的層次。6-3 使用 (1) 順序表示和 (2) 二叉鏈表表示法，分別畫出右圖所示二叉樹的存儲表示。0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 順序表示 二叉鏈表表示 6-4 用嵌套類寫出用鏈表表示的二叉樹的類聲明。6-5 在結(jié)點個數(shù)為n (n>1)的各棵樹中，高度最小的樹的高度是多少？它有多少個葉結(jié)點？多少個分支結(jié)點？高度最大的樹的高度是多少？它有多少個葉結(jié)點？多少個分支結(jié)點？

45、6-6 試分別畫出具有3個結(jié)點的樹和3個結(jié)點的二叉樹的所有不同形態(tài)。6-7 如果一棵樹有n1個度為1的結(jié)點, 有n2個度為2的結(jié)點, , nm個度為m的結(jié)點, 試問有多少個度為0的結(jié)點? 試推導(dǎo)之。6-8 試分別找出滿足以下條件的所有二叉樹:(1) 二叉樹的前序序列與中序序列相同;(2) 二叉樹的中序序列與后序序列相同;(3) 二叉樹的前序序列與后序序列相同。6-9 若用二叉鏈表作為二叉樹的存儲表示，試針對以下問題編寫遞歸算法：(1) 統(tǒng)計二叉樹中葉結(jié)點的個數(shù)。(2) 以二叉樹為參數(shù)，交換每個結(jié)點的左子女和右子女。6-10 一棵高度為h的滿k叉樹有如下性質(zhì): 第h層上的結(jié)點都是葉結(jié)點, 其余各

46、層上每個結(jié)點都有k棵非空子樹, 如果按層次自頂向下, 同一層自左向右, 順序從1開始對全部結(jié)點進行編號, 試問:(1) 各層的結(jié)點個數(shù)是多少?(2) 編號為i的結(jié)點的父結(jié)點(若存在)的編號是多少?(3) 編號為i的結(jié)點的第m個孩子結(jié)點(若存在)的編號是多少?(4) 編號為i的結(jié)點有右兄弟的條件是什么? 其右兄弟結(jié)點的編號是多少?(5) 若結(jié)點個數(shù)為 n, 則高度h是n 的什么函數(shù)關(guān)系?6-11 試用判定樹的方法給出在中序線索化二叉樹上：6-11 已知一棵完全二叉樹存放于一個一維數(shù)組Tn中，Tn中存放的是各結(jié)點的值。試設(shè)計一個算法，從T0開始順序讀出各結(jié)點的值，建立該二叉樹的二叉鏈表表示。6-1

47、2 試編寫一個算法，把一個新結(jié)點l作為結(jié)點s的左子女插入到一棵線索化二叉樹中，s原來的左子女變成l的左子女。6-13 寫出向堆中加入數(shù)據(jù)4, 2, 5, 8, 3, 6, 10, 14時，每加入一個數(shù)據(jù)后堆的變化。6-14 判斷以下序列是否是最小堆? 如果不是, 將它調(diào)整為最小堆。(1) 100, 86, 48, 73, 35, 39, 42, 57, 66, 21 (2) 12, 70, 33, 65, 24, 56, 48, 92, 86, 33 (3) 103, 97, 56, 38, 66, 23, 42, 12, 30, 52, 06, 20 (4) 05, 56, 20, 23,

48、40, 38, 29, 61, 35, 76, 28, 100 6-15 請畫出右圖所示的樹所對應(yīng)的二叉樹。 6-16 在森林的二叉樹表示中，用llink存儲指向結(jié)點第一個子女的指針，用rlink存儲指向結(jié)點下一個兄弟的指針，用data存儲結(jié)點的值。如果我們采用靜態(tài)二叉鏈表作為森林的存儲表示，同時按森林的先根次序依次安放森林的所有結(jié)點，則可以在它們的結(jié)點中用只有一個二進位的標志ltag代替llink，用rtag代替rlink。并設(shè)定若ltag = 0，則該結(jié)點沒有子女，若ltag ¹ 0，則該結(jié)點有子女；若rtag = 0，則該結(jié)點沒有下一個兄弟，若rtag ¹ 0，則該結(jié)

49、點有下一個兄弟。試給出這種表示的結(jié)構(gòu)定義，并設(shè)計一個算法，將用這種表示存儲的森林轉(zhuǎn)換成用llink - rlink表示的森林。6-17 二叉樹的雙序遍歷(Double-order traversal)是指：對于二叉樹的每一個結(jié)點來說，先訪問這個結(jié)點，再按雙序遍歷它的左子樹，然后再一次訪問這個結(jié)點，接下來按雙序遍歷它的右子樹。試寫出執(zhí)行這種雙序遍歷的算法。6-18 已知一棵二叉樹的前序遍歷的結(jié)果是ABECDFGHIJ, 中序遍歷的結(jié)果是EBCDAFHIGJ, 試畫出這棵二叉樹。6-19 已知一棵樹的先根次序遍歷的結(jié)果與其對應(yīng)二叉樹表示(長子-兄弟表示)的前序遍歷結(jié)果相同, 樹的后根次序遍歷結(jié)果與

50、其對應(yīng)二叉樹表示的中序遍歷結(jié)果相同。試問利用樹的先根次序遍歷結(jié)果和后根次序遍歷結(jié)果能否唯一確定一棵樹? 舉例說明。6-20 給定權(quán)值集合 15, 03, 14, 02, 06, 09, 16, 17 , 構(gòu)造相應(yīng)的霍夫曼樹, 并計算它的帶權(quán)外部路徑長度。6-21 假定用于通信的電文僅由8個字母c1, c2, c3, c4, c5, c6, c7, c8組成, 各字母在電文中出現(xiàn)的頻率分別為5, 25, 3, 6, 10, 11, 36, 4。試為這8個字母設(shè)計不等長Huffman編碼, 并給出該電文的總碼數(shù)。6-22 給定一組權(quán)值: 23, 15, 66, 07, 11, 45, 33, 52

51、, 39, 26, 58, 試構(gòu)造一棵具有最小帶權(quán)外部路徑長度的擴充4叉樹, 要求該4叉樹中所有內(nèi)部結(jié)點的度都是4, 所有外部結(jié)點的度都是0。這棵擴充4叉樹的帶權(quán)外部路徑長度是多少? (提示：如果權(quán)值個數(shù)不足以構(gòu)造擴充4叉樹，可補充若干值為零的權(quán)值，再仿照霍夫曼樹的思路構(gòu)造擴充4叉樹)6-12 已知一棵完全二叉樹存放于一個一維數(shù)組Tn中，Tn中存放的是各結(jié)點的值。試設(shè)計一個算法，從T0開始順序讀出各結(jié)點的值，建立該二叉樹的二叉鏈表表示。6-14 寫出向堆中加入數(shù)據(jù)4, 2, 5, 8, 3, 6, 10, 14時，每加入一個數(shù)據(jù)后堆的變化。6-16 請畫出右圖所示的樹所對應(yīng)的二叉樹。6-17

52、在森林的二叉樹表示中，用llink存儲指向結(jié)點第一個子女的指針，用rlink存儲指向結(jié)點下一個兄弟的指針，用data存儲結(jié)點的值。如果我們采用靜態(tài)二叉鏈表作為森林的存儲表示，同時按森林的先根次序依次安放森林的所有結(jié)點，則可以在它們的結(jié)點中用只有一個二進位的標志ltag代替llink，用rtag代替rlink。并設(shè)定若ltag = 0，則該結(jié)點沒有子女，若ltag ¹ 0，則該結(jié)點有子女；若rtag = 0，則該結(jié)點沒有下一個兄弟，若rtag ¹ 0，則該結(jié)點有下一個兄弟。試給出這種表示的結(jié)構(gòu)定義，并設(shè)計一個算法，將用這種表示存儲的森林轉(zhuǎn)換成用llink - rlink表示的

53、森林。6-18 二叉樹的雙序遍歷(Double-order traversal)是指：對于二叉樹的每一個結(jié)點來說，先訪問這個結(jié)點，再按雙序遍歷它的左子樹，然后再一次訪問這個結(jié)點，接下來按雙序遍歷它的右子樹。試寫出執(zhí)行這種雙序遍歷的算法。6-19 已知一棵二叉樹的前序遍歷的結(jié)果是ABECDFGHIJ, 中序遍歷的結(jié)果是EBCDAFHIGJ, 試畫出這棵二叉樹。6-20 已知一棵樹的先根次序遍歷的結(jié)果與其對應(yīng)二叉樹表示(長子-兄弟表示)的前序遍歷結(jié)果相同, 樹的后根次序遍歷結(jié)果與其對應(yīng)二叉樹表示的中序遍歷結(jié)果相同。試問利用樹的先根次序遍歷結(jié)果和后根次序遍歷結(jié)果能否唯一確定一棵樹? 舉例說明。6-2

54、2 假定用于通信的電文僅由8個字母c1, c2, c3, c4, c5, c6, c7, c8組成, 各字母在電文中出現(xiàn)的頻率分別為5, 25, 3, 6, 10, 11, 36, 4。試為這8個字母設(shè)計不等長Huffman編碼, 并給出該電文的總碼數(shù)。6-23 給定一組權(quán)值: 23, 15, 66, 07, 11, 45, 33, 52, 39, 26, 58, 試構(gòu)造一棵具有最小帶權(quán)外部路徑長度的擴充4叉樹, 要求該4叉樹中所有內(nèi)部結(jié)點的度都是4, 所有外部結(jié)點的度都是0。這棵擴充4叉樹的帶權(quán)外部路徑長度是多少?第7章 集合與搜索7-1 設(shè)A = 1, 2, 3 , B = 3, 4, 5 ，求下列結(jié)果：(1) A + B(2) A * B(3) A - B(4) A.Contains (1)(5) A.AddMember (1)(6) A.DelMember (1)(7) A.