數(shù)據(jù)結(jié)構(gòu)(C++版)王紅梅 版課后答案khdaw

1、課后答案網(wǎng)第 1 章 緒 論課后習(xí)題講解1. 填空（ ）是數(shù)據(jù)的基本單位，在計(jì)算機(jī)程序中通常作為一個(gè)整體進(jìn)行考慮和處理?！窘獯稹繑?shù)據(jù)元素（ ）是數(shù)據(jù)的最小單位，（ ）是討論數(shù)據(jù)結(jié)構(gòu)時(shí)涉及的最小數(shù)據(jù)單位?！窘獯稹繑?shù)據(jù)項(xiàng)，數(shù)據(jù)元素【分析】數(shù)據(jù)結(jié)構(gòu)指的是數(shù)據(jù)元素以及數(shù)據(jù)元素之間的關(guān)系。 從邏輯關(guān)系上講，數(shù)據(jù)結(jié)構(gòu)主要分為（ ）、（ ）、（ ）和（ ）?！窘獯稹考?，線性結(jié)構(gòu)，樹結(jié)構(gòu)，圖結(jié)構(gòu) 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)主要有（ ）和（ ）兩種基本方法，不論哪種存儲(chǔ)結(jié)構(gòu)，都要存儲(chǔ)兩方面的內(nèi)容：（ ） 和（ ）?！窘獯稹宽樞虼鎯?chǔ)結(jié)構(gòu)，鏈接存儲(chǔ)結(jié)構(gòu)，數(shù)據(jù)元素，數(shù)據(jù)元素之間的關(guān)系 算法具有五個(gè)特性，分別是（ ）、（ ）、（

2、 ）、（ ）、（ ）。【解答】有零個(gè)或多個(gè)輸入，有一個(gè)或多個(gè)輸出，有窮性，確定性，可行性 算法的描述方法通常有（ ）、（ ）、（ ）和（ ）四種，其中，（ ）被稱為算法語言?！窘獯稹孔匀徽Z言，程序設(shè)計(jì)語言，流程圖，偽代碼，偽代碼 在一般情況下，一個(gè)算法的時(shí)間復(fù)雜度是（ ）的函數(shù)。【解答】問題規(guī)模 設(shè)待處理問題的規(guī)模為 n，若一個(gè)算法的時(shí)間復(fù)雜度為一個(gè)常數(shù)，則表示成數(shù)量級的形式為（ ），若 為 n*log25n，則表示成數(shù)量級的形式為（ ）?！窘獯稹?1)，(nlog2n)【分析】用大 O 記號表示算法的時(shí)間復(fù)雜度，需要將低次冪去掉，將最高次冪的系數(shù)去掉。2. 選擇題 順序存儲(chǔ)結(jié)構(gòu)中數(shù)據(jù)元素之間

3、的邏輯關(guān)系是由（ ）表示的，鏈接存儲(chǔ)結(jié)構(gòu)中的數(shù)據(jù)元素之間的邏輯關(guān) 系是由（ ）表示的。A 線性結(jié)構(gòu) B 非線性結(jié)構(gòu) C 存儲(chǔ)位置 D 指針【解答】C，D【分析】順序存儲(chǔ)結(jié)構(gòu)就是用一維數(shù)組存儲(chǔ)數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)元素，其邏輯關(guān)系由存儲(chǔ)位置（即元素在數(shù) 組中的下標(biāo)）表示；鏈接存儲(chǔ)結(jié)構(gòu)中一個(gè)數(shù)據(jù)元素對應(yīng)鏈表中的一個(gè)結(jié)點(diǎn)，元素之間的邏輯關(guān)系由結(jié)點(diǎn)中 的指針表示。 假設(shè)有如下遺產(chǎn)繼承規(guī)則：丈夫和妻子可以相互繼承遺產(chǎn)；子女可以繼承父親或母親的遺產(chǎn)；子女間不 能相互繼承。則表示該遺產(chǎn)繼承關(guān)系的最合適的數(shù)據(jù)結(jié)構(gòu)應(yīng)該是（ ）。A 樹 B 圖 C 線性表 D 集合【解答】B【分析】將丈夫、妻子和子女分別作為數(shù)據(jù)元素，

4、根據(jù)題意畫出邏輯結(jié)構(gòu)圖。 算法指的是（ ）。A 對特定問題求解步驟的一種描述，是指令的有限序列。B 計(jì)算機(jī)程序 C 解決問題的計(jì)算方法 D 數(shù)據(jù)處理【解答】A【分析】計(jì)算機(jī)程序是對算法的具體實(shí)現(xiàn)；簡單地說，算法是解決問題的方法；數(shù)據(jù)處理是通過算法完成 的。所以，只有 A 是算法的準(zhǔn)確定義。 下面（ ）不是算法所必須具備的特性。A 有窮性 B 確切性 C 高效性 D 可行性【解答】C【分析】高效性是好算法應(yīng)具備的特性。 算法分析的目的是（ ），算法分析的兩個(gè)主要方面是（ ）。A 找出數(shù)據(jù)結(jié)構(gòu)的合理性 B 研究算法中輸入和輸出的關(guān)系 C 分析算法的效率以求改進(jìn) D 分析算法的易讀性和文檔性 E 空

5、間性能和時(shí)間性能 F 正確性和簡明性G 可讀性和文檔性 H 數(shù)據(jù)復(fù)雜性和程序復(fù)雜性【解答】C，E3. 判斷題 算法的時(shí)間復(fù)雜度都要通過算法中的基本語句的執(zhí)行次數(shù)來確定?！窘獯稹垮e(cuò)。時(shí)間復(fù)雜度要通過算法中基本語句執(zhí)行次數(shù)的數(shù)量級來確定。 每種數(shù)據(jù)結(jié)構(gòu)都具備三個(gè)基本操作：插入、刪除和查找?！窘獯稹垮e(cuò)。如數(shù)組就沒有插入和刪除操作。此題注意是每種數(shù)據(jù)結(jié)構(gòu)。 所謂數(shù)據(jù)的邏輯結(jié)構(gòu)指的是數(shù)據(jù)之間的邏輯關(guān)系。【解答】錯(cuò)。是數(shù)據(jù)之間的邏輯關(guān)系的整體。 邏輯結(jié)構(gòu)與數(shù)據(jù)元素本身的內(nèi)容和形式無關(guān)?！窘獯稹繉?。因此邏輯結(jié)構(gòu)是數(shù)據(jù)組織的主要方面。 基于某種邏輯結(jié)構(gòu)之上的基本操作，其實(shí)現(xiàn)是唯一的?！窘獯稹垮e(cuò)?；静僮鞯膶?shí)現(xiàn)

6、是基于某種存儲(chǔ)結(jié)構(gòu)設(shè)計(jì)的，因而不是唯一的。4. 分析以下各程序段，并用大 O 記號表示其執(zhí)行時(shí)間?！窘獯稹?基本語句是 k=k+10*i，共執(zhí)行了 n-2 次，所以 T(n)=O(n)。 基本語句是 k=k+10*i，共執(zhí)行了 n 次，所以 T(n)=O(n)。 分析條件語句，每循環(huán)一次，i+j 整體加 1，共循環(huán) n 次，所以 T(n)=O(n)。 設(shè)循環(huán)體共執(zhí)行 T(n)次，每循環(huán)一次，循環(huán)變量 y 加 1，最終 T(n)=y，即：(T(n)+1)2n，所以 T(n)=O(n 1/2)。 x+是基本語句，所以 5設(shè)有數(shù)據(jù)結(jié)構(gòu)（D，R），其中 D=1, 2, 3, 4, 5, 6，R=(1,

7、2),(2,3),(2,4),(3,4),(3,5),(3,6),(4,5),(4,6)。試畫出其邏輯結(jié)構(gòu)圖并指出屬于何種結(jié)構(gòu)?！窘獯稹科溥壿嫿Y(jié)構(gòu)圖如圖 1-3 所示，它是一種圖結(jié)構(gòu)。6. 為整數(shù)定義一個(gè)抽象數(shù)據(jù)類型，包含整數(shù)的常見運(yùn)算，每個(gè)運(yùn)算對應(yīng)一個(gè)基本操作，每個(gè)基本操作的接 口需定義前置條件、輸入、功能、輸出和后置條件?！窘獯稹空麛?shù)的抽象數(shù)據(jù)類型定義如下：ADT integerData整數(shù) a：可以是正整數(shù)(1, 2, 3, )、負(fù)整數(shù)(-1, -2, -3, )和零OperationConstructor 前置條件：整數(shù) a 不存在 輸入：一個(gè)整數(shù) b 功能：構(gòu)造一個(gè)與輸入值相同的整數(shù)

8、輸出：無后置條件：整數(shù) a 具有輸入的值Set 前置條件：存在一個(gè)整數(shù) a 輸入：一個(gè)整數(shù) b功能：修改整數(shù) a 的值，使之與輸入的整數(shù)值相同 輸出：無后置條件：整數(shù) a 的值發(fā)生改變Add 前置條件：存在一個(gè)整數(shù) a 輸入：一個(gè)整數(shù) b功能：將整數(shù) a 與輸入的整數(shù) b 相加 輸出：相加后的結(jié)果后置條件：整數(shù) a 的值發(fā)生改變Sub 前置條件：存在一個(gè)整數(shù) a 輸入：一個(gè)整數(shù) b功能：將整數(shù) a 與輸入的整數(shù) b 相減 輸出：相減的結(jié)果后置條件：整數(shù) a 的值發(fā)生改變Multi 前置條件：存在一個(gè)整數(shù) a 輸入：一個(gè)整數(shù) b功能：將整數(shù) a 與輸入的整數(shù) b 相乘 輸出：相乘的結(jié)果后置條件：

9、整數(shù) a 的值發(fā)生改變Div 前置條件：存在一個(gè)整數(shù) a 輸入：一個(gè)整數(shù) b功能：將整數(shù) a 與輸入的整數(shù) b 相除輸出：若整數(shù) b 為零，則拋出除零異常，否則輸出相除的結(jié)果 后置條件：整數(shù) a 的值發(fā)生改變Mod 前置條件：存在一個(gè)整數(shù) a 輸入：一個(gè)整數(shù) b功能：求當(dāng)前整數(shù)與輸入整數(shù)的模，即正的余數(shù)輸出：若整數(shù) b 為零，則拋出除零異常，否則輸出取模的結(jié)果 后置條件：整數(shù) a 的值發(fā)生改變Equal 前置條件：存在一個(gè)整數(shù) a 輸入：一個(gè)整數(shù) b功能：判斷整數(shù) a 與輸入的整數(shù) b 是否相等 輸出：若相等返回 1，否則返回 0后置條件：整數(shù) a 的值不發(fā)生改變endADT7. 求多項(xiàng)式 A

10、(x)的算法可根據(jù)下列兩個(gè)公式之一來設(shè)計(jì)： A(x)=anxn+an-1xn-1+a1x+a0 A(x)=(anx+an-1)x+a1)x)+a0根據(jù)算法的時(shí)間復(fù)雜度分析比較這兩種算法的優(yōu)劣。【解答】第二種算法的時(shí)間性能要好些。第一種算法需執(zhí)行大量的乘法運(yùn)算，而第二種算法進(jìn)行了優(yōu)化， 減少了不必要的乘法運(yùn)算。8. 算法設(shè)計(jì)（要求：算法用偽代碼和 C+描述，并分析最壞情況下的時(shí)間復(fù)雜度） 對一個(gè)整型數(shù)組 An設(shè)計(jì)一個(gè)排序算法。【解答】下面是簡單選擇排序算法的偽代碼描述。下面是簡單選擇排序算法的 C+描述。分析算法，有兩層嵌套的 for 循環(huán)，所以， 。 找出整型數(shù)組 An中元素的最大值和次最大值

11、。【解答】算法的偽代碼描述如下：算法的 C+描述如下：分析算法，只有一層循環(huán)，共執(zhí)行 n-2 次，所以，T(n)=O(n)。學(xué)習(xí)自測及答案1順序存儲(chǔ)結(jié)構(gòu)的特點(diǎn)是（ ），鏈接存儲(chǔ)結(jié)構(gòu)的特點(diǎn)是（ ）?！窘獯稹坑迷卦诖鎯?chǔ)器中的相對位置來表示數(shù)據(jù)元素之間的邏輯關(guān)系，用指示元素存儲(chǔ)地址的指針表示 數(shù)據(jù)元素之間的邏輯關(guān)系。2. 算法在發(fā)生非法操作時(shí)可以作出處理的特性稱為（ ）?！窘獯稹拷研?. 常見的算法時(shí)間復(fù)雜度用大記號表示為：常數(shù)階( )、對數(shù)階( )、線性階 ( )、平方階( )和指數(shù)階( )?！窘獯稹?1)，(log2n)，(n)，(n2)，(2n)4將下列函數(shù)按它們在 n 時(shí)的無窮大階數(shù)，從

12、小到大排列。n, n-n3+7n5, nlogn, 2n/2, n3, log2n, n1/2+log2n, (3/2)n, n!, n2+log2n【解答】log2n, n1/2+log2n, n, nlog2n, n2+log2n, n3, n-n3+7n5, 2n/2, (3/2)n, n!5試描述數(shù)據(jù)結(jié)構(gòu)和抽象數(shù)據(jù)類型的概念與程序設(shè)計(jì)語言中數(shù)據(jù)類型概念的區(qū)別?！窘獯稹繑?shù)據(jù)結(jié)構(gòu)是指相互之間存在一定關(guān)系的數(shù)據(jù)元素的集合。而抽象數(shù)據(jù)類型是指一個(gè)數(shù)據(jù)結(jié)構(gòu)以及 定義在該結(jié)構(gòu)上的一組操作。程序設(shè)計(jì)語言中的數(shù)據(jù)類型是一個(gè)值的集合和定義在這個(gè)值集上一組操作的 總稱。抽象數(shù)據(jù)類型可以看成是對數(shù)據(jù)類型的一

13、種抽象。6. 對下列用二元組表示的數(shù)據(jù)結(jié)構(gòu),試分別畫出對應(yīng)的邏輯結(jié)構(gòu)圖，并指出屬于何種結(jié)構(gòu)。 A=(D，R)， 其中 D=a1, a2, a3, a4，R= B=(D，R)， 其中 D=a, b, c, d, e, f，R=, C=( D，R)，其中 D=a，b，c，d，e，f，R=, D=(D，R)， 其中 D=1, 2, 3, 4, 5, 6，R=(1, 2)，(1, 4)，(2, 3)，(2, 4)，(3, 4)，(3, 5)，(3, 6)，(4, 6)【解答】 屬于集合，其邏輯結(jié)構(gòu)圖如圖 1-4(a)所示； 屬于線性結(jié)構(gòu)，其邏輯結(jié)構(gòu)圖如圖 1-4(b)所示； 屬于樹結(jié)構(gòu)，其邏輯結(jié)構(gòu)圖如

14、圖 1-4(c)所示； 屬于圖結(jié)構(gòu)，其邏輯結(jié)構(gòu)圖如圖 1-4(d)所示。7. 求下列算法的時(shí)間復(fù)雜度。count=0; x=1; while (x x*=2; count+;return count;【解答】(log2n)第 2 章 線性表課后習(xí)題講解1. 填空 在順序表中，等概率情況下，插入和刪除一個(gè)元素平均需移動(dòng)（ ）個(gè)元素，具體移動(dòng)元素的個(gè)數(shù)與（ ） 和（ ）有關(guān)。【解答】表長的一半，表長，該元素在表中的位置 順序表中第一個(gè)元素的存儲(chǔ)地址是 100，每個(gè)元素的長度為 2，則第 5 個(gè)元素的存儲(chǔ)地址是（ ）?！窘獯稹?08【分析】第 5 個(gè)元素的存儲(chǔ)地址=第 1 個(gè)元素的存儲(chǔ)地址(51)&

15、#215;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)的作用是（ ）?！窘獯稹繛榱诉\(yùn)算方便【分析】例如在插入和刪除操作時(shí)不必對表頭的情況進(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)的操作序列為（ ）。【

16、解答】s->next =rear->next; rear->next =s; rear =s;q=rear->next->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)；而在給定值為 x 的結(jié)點(diǎn) 后插入一個(gè)新結(jié)點(diǎn)需要先查找值為 x

17、 的結(jié)點(diǎn)，所以時(shí)間復(fù)雜度為 (n)。 可由一個(gè)尾指針唯一確定的鏈表有（ ）、（ ）、（ ）?！窘獯稹垦h(huán)鏈表，循環(huán)雙鏈表，雙鏈表2. 選擇題 線性表的順序存儲(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)

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

19、表中 查找第 i 個(gè)元素的前趨也很方便。單鏈表和單循環(huán)鏈表既不能實(shí)現(xiàn)隨機(jī)存取，查找第 i 個(gè)元素的前趨也不方 便，雙鏈表雖然能快速查找第 i 個(gè)元素的前趨，但不能實(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 。 若鏈表中最常用的操

20、作是在最后一個(gè)結(jié)點(diǎn)之后插入一個(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)在單鏈表中的位置。 對于 n 個(gè)

21、元素組成的線性表，建立一個(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ǔ)空間，對于動(dòng)態(tài)存儲(chǔ)分配，回收存儲(chǔ)空間的速度是一樣的。由于雙鏈表具有對稱性， 所以，其插入和刪除操作更加方便。 在一個(gè)單鏈表中，已知

22、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-&

23、gt;next->prior=s; s->next=p->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【分析】在鏈表中，對指針的修改必須保持

24、線性表的邏輯關(guān)系，否則，將違背線性表的邏輯特征，圖 2-10給出備選答案 C 和 D 的圖解。3. 判斷題 線性表的邏輯順序和存儲(chǔ)順序總是一致的?！窘獯稹垮e(cuò)。順序表的邏輯順序和存儲(chǔ)順序一致，鏈表的邏輯順序和存儲(chǔ)順序不一定一致。 線性表的順序存儲(chǔ)結(jié)構(gòu)優(yōu)于鏈接存儲(chǔ)結(jié)構(gòu)?！窘獯稹垮e(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è)直接后繼?！窘獯稹垮e(cuò)。每個(gè)元素最多只有一個(gè)直接前驅(qū)和一個(gè)直接后繼，第一個(gè)元素沒有前驅(qū)，最后一個(gè)元素沒有 后繼

25、。 在單鏈表中，要取得某個(gè)元素，只要知道該元素所在結(jié)點(diǎn)的地址即可，因此單鏈表是隨機(jī)存取結(jié)構(gòu)?！窘獯稹垮e(cuò)。要找到該結(jié)點(diǎn)的地址，必須從頭指針開始查找，所以單鏈表是順序存取結(jié)構(gòu)。4請說明順序表和單鏈表各有何優(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)： 插入和刪除操

26、作需移動(dòng)大量元素； 表的 容量難以確定； 造成存儲(chǔ)空間的“碎片”。單鏈表的優(yōu)點(diǎn)： 不必事先知道線性表的長度； 插入和刪除元素時(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ā)展的需要。而順序表的插入、刪

27、除的效率低，故不合適。5算法設(shè)計(jì) 設(shè)計(jì)一個(gè)時(shí)間復(fù)雜度為(n)的算法，實(shí)現(xiàn)將數(shù)組 An中所有元素循環(huán)右移 k 個(gè)位置。【解答】算法思想請參見主教材第一章思想火花。下面給出具體算法。分析算法，第一次調(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ù)組 An中的元素為整型，設(shè)計(jì)算法將其調(diào)整為左右兩部分，左邊所有元素為奇數(shù)，右邊所有元 素為偶數(shù)，并要求算法的時(shí)間復(fù)雜度為(n)?！窘獯稹繌臄?shù)組的兩端向中間比較，設(shè)置兩個(gè)變量 i 和 j，初始

28、時(shí) i=0，j=n-1，若 Ai為偶數(shù)并且 Aj為奇 數(shù)，則將 Ai與 Aj交換。具體算法如下：分析算法，兩層循環(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)線性表就地逆置的算法?！窘獯稹宽樞虮淼哪嬷?，即是將對稱元素交換，設(shè)順序表的長度為 length，則將表中第 i 個(gè)元素與第 length-i-1個(gè)元素相交換。具體算法如下：單鏈表的逆置請參見 2.2.4 算法 2-4 和算法 2-6。 假設(shè)在長度大于 1 的循環(huán)鏈表

29、中，即無頭結(jié)點(diǎn)也無頭指針，s 為指向鏈表中某個(gè)結(jié)點(diǎn)的指針，試編寫算 法刪除結(jié)點(diǎn) s 的前趨結(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è)單

30、鏈表以非遞減有序排列，設(shè)計(jì)算法實(shí)現(xiàn)在單鏈表中刪去值相同的多余結(jié)點(diǎn)?！窘獯稹繌念^到尾掃描單鏈表，若當(dāng)前結(jié)點(diǎn)的元素值與后繼結(jié)點(diǎn)的元素值不相等，則指針后移；否則刪除 該后繼結(jié)點(diǎn)。具體算法如下： 判斷帶頭結(jié)點(diǎn)的雙循環(huán)鏈表是否對稱。【解答】設(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è)元素占

31、用 4 個(gè)存儲(chǔ)單元，第 9 個(gè)元素的地址為 144，則第一個(gè) 元素的地址是（ ）。A 108 B 180 C 176 D 112【解答】D2在長度為 n 的線性表中查找值為 x 的數(shù)據(jù)元素的時(shí)間復(fù)雜度為： （ ）。A O(0) B O(1) C O(n) D O(n2)【解答】C3在一個(gè)長度為 n 的順序表的第 i（1in+1）個(gè)元素之前插入一個(gè)元素，需向后移動(dòng)（ ）個(gè)元素，刪除 第 i（1in）個(gè)元素時(shí)，需向前移動(dòng)（ ）個(gè)元素?！窘獯稹縩-i+1，n-i4在單鏈表中，除了頭結(jié)點(diǎn)以外，任一結(jié)點(diǎn)的存儲(chǔ)位置由（ ）指示?！窘獯稹科淝摆吔Y(jié)點(diǎn)的指針域5當(dāng)線性表采用順序存儲(chǔ)結(jié)構(gòu)時(shí)，其主要特點(diǎn)是（ ）。【

32、解答】邏輯結(jié)構(gòu)中相鄰的結(jié)點(diǎn)在存儲(chǔ)結(jié)構(gòu)中仍相鄰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 之間（1in）的概率為 ，則平均每插 入一個(gè)元素所要移動(dòng)的元素個(gè)數(shù)又是多少？【解答】，。8線性表存放在整型數(shù)組 Aarrsize的前 elenum 個(gè)單元中，且遞增有序。編寫算法，將元素 x 插入到線 性表的適當(dāng)位置上，以保持線性表的有序性，并且分析算法的時(shí)間復(fù)雜度。【解答】本題是在一

33、個(gè)遞增有序表中插入元素 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，對其遍歷的結(jié)果是：x1, x2, x3, xn-1, xn。請將該循環(huán)鏈表拆成兩

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

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

36、答】假溢出 數(shù)組 Qn用來表示一個(gè)循環(huán)隊(duì)列，front 為隊(duì)頭元素的前一個(gè)位置，rear 為隊(duì)尾元素的位置，計(jì)算隊(duì)列 中元素個(gè)數(shù)的公式為（ ）?！窘獯稹浚╮ear-front+n）% n【分析】也可以是（rear-front）% n，但 rear-front 的結(jié)果可能是負(fù)整數(shù)，而對一個(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ì)即是在終端結(jié)點(diǎn) 的后面插入一個(gè)結(jié)點(diǎn)，這需要從頭指針開始查找終端

37、結(jié)點(diǎn)的地址。 串是一種特殊的線性表，其特殊性體現(xiàn)在（ ）?！窘獯稹繑?shù)據(jù)元素的類型是一個(gè)字符 兩個(gè)串相等的充分必要條件是（ ）?！窘獯稹块L度相同且對應(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、e4、e5、e6

38、依次通過棧 S，一個(gè)元素出棧后即進(jìn) 入隊(duì)列 Q，若 6 個(gè)元素出隊(duì)的順序是 e2、e4、e3、e6、e5、e1，則棧 S 的容量至少應(yīng)該是（）。A 6B 4C 3D 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)比該元素小并且是升序（指的是元素的序 號）的兩個(gè)元素。 設(shè)計(jì)一個(gè)判別表達(dá)式中左右括號是否配對的算法，采用（

39、）數(shù)據(jù)結(jié)構(gòu)最佳A 順序表 B 棧 C 隊(duì)列 D 鏈表【解答】B【分析】每個(gè)右括號與它前面的最后一個(gè)沒有匹配的左括號配對，因此具有后進(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ì)列的入隊(duì)順序和出隊(duì)順序總是一致的。 棧和隊(duì)列的主要區(qū)別在于（ ）。A 它們的邏輯結(jié)構(gòu)不一樣 B 它們的存儲(chǔ)結(jié)構(gòu)

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

41、空間首先兩個(gè)棧是相向增長的，棧底應(yīng)該分別指向兩個(gè)棧中的第一個(gè)元素的位置，并注 意 C+中的數(shù)組下標(biāo)是從 0 開始的。 設(shè)有兩個(gè)串 p 和 q，求 q 在 p 中首次出現(xiàn)的位置的運(yùn)算稱作（ ）。A 連接 B 模式匹配 C 求子串 D 求串長【解答】B3. 判斷題 有 n 個(gè)元素依次進(jìn)棧，則出棧序列有(n-1)/2 種?！窘獯稹垮e(cuò)。應(yīng)該有 種。 ?？梢宰鳛閷?shí)現(xiàn)過程調(diào)用的一種數(shù)據(jù)結(jié)構(gòu)?！窘獯稹繉?。只要操作滿足后進(jìn)先出性，都可以采用棧作為輔助數(shù)據(jù)結(jié)構(gòu)。 在棧滿的情況下不能做進(jìn)棧操作，否則將產(chǎn)生“上溢”?！窘獯稹繉?。 在循環(huán)隊(duì)列中，front 指向隊(duì)頭元素的前一個(gè)位置，rear 指向隊(duì)尾元素的位置，則隊(duì)

42、滿的條件是front=rear。【解答】錯(cuò)。這是隊(duì)空的判定條件，在循環(huán)隊(duì)列中要將隊(duì)空和隊(duì)滿的判定條件區(qū)別開。 空串與空格串是相同的?！窘獯稹垮e(cuò)。空串的長度為零，而空格串的長度不為 0，其長度是串中空格的個(gè)數(shù)。4. 設(shè)有一個(gè)棧，元素進(jìn)棧的次序?yàn)?A，B，C，D，E，能否得到如下出棧序列，若能，請寫出操作序列，若 不能，請說明原因。 C，E，A，B，D C，B，A，D，E【解答】不能，因?yàn)樵?C、E 出棧的情況下，A 一定在棧中，而且在 B 的下面，不可能先于 B 出棧。 可以，設(shè)為進(jìn)棧操作，為入棧操作，則其操作序列為 IIIOOOIOIO。5. 舉例說明順序隊(duì)列的“假溢出”現(xiàn)象?！窘獯稹考僭O(shè)有一

43、個(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 表示棧頂元素出棧。）【解答】棧頂元素為 6，棧底元素為 1。其執(zhí)行過程如圖 3-7 所示。7在操作序列 EnQueue(1)、EnQueue(3)、DeQueue

44、、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ù)。串中的空格符可用來分隔一般的字符，便于人們識別和閱讀，但計(jì)算串長時(shí)應(yīng)包括這些空格符?？?串在串處理中可作為任意串的子串。9. 算法設(shè)計(jì) 假設(shè)以不帶頭結(jié)點(diǎn)的循環(huán)鏈表表

45、示隊(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ù)綏５椎脑匾来螢?a2n，a2n-1，a1，要求通過一個(gè)循環(huán)隊(duì)列 重新排列棧中元素，使得從棧頂?shù)綏５椎脑匾来螢?a2n，a2n-2，a2，a2n-1，a2n-3，a1，請?jiān)O(shè) 計(jì)算法實(shí)現(xiàn)該操作，要求空間復(fù)雜度和時(shí)間復(fù)雜度均為 O(n)?！窘獯稹坎僮鞑襟E為： 將所有元

46、素出棧并入隊(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è)位置。算法如下： 對于采用順序存儲(chǔ)結(jié)構(gòu)的串 S，編寫一個(gè)函數(shù)刪除其值等于 ch 的所有字符?！窘獯稹繌暮笙蚯皠h除值為 ch 的所有元素，這樣所有移動(dòng)的元素中沒有值為 ch 的元素，能減少移動(dòng)元素 的次數(shù)，提高算法的效率。算法如下

47、： 對串的模式匹配 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;【解答】C2一個(gè)棧的入棧序列是 a, b, c, d, e，則棧的不可能的出棧序列是（ ）。A edcba B cdeba C debca D abcde【解答】C3從棧頂指針為 top 的鏈棧中刪除一個(gè)結(jié)點(diǎn)，用 x 保存被刪除結(jié)點(diǎn)的值，則執(zhí)行（ ）。A x=top;

48、 top=top->next; B x=top->data;C top=top->next; x=top->data; D x=top->data; top=top->next;【解答】D4設(shè)元素 1, 2, 3, P, A 依次經(jīng)過一個(gè)棧，進(jìn)棧次序?yàn)?123PA，在棧的輸出序列中，有哪些序列可作為 C+程序設(shè)計(jì)語言的變量名?！窘獯稹縋A321, P3A21, P32A1, P321A, AP3215.設(shè) S="I_ am_ a_ teacther"，其長度為（ ）?！窘獯稹?56對于棧和隊(duì)列，無論它們采用順序存儲(chǔ)結(jié)構(gòu)還是鏈接存儲(chǔ)結(jié)構(gòu)，進(jìn)

49、行插入和刪除操作的時(shí)間復(fù)雜度都是（ ）?！窘獯稹?1)7如果進(jìn)棧序列為 A、B、C、D，則可能的出棧序列是什么？答：共 14 種，分別是：ABCD，ABDC，ACBD，ACDB，ADCB，BACD，BADC，BCAD，BCDA，BDCA，CBAD，CBDA，CDBA，DCBA8簡述隊(duì)列和棧這兩種數(shù)據(jù)結(jié)構(gòu)的相同點(diǎn)和不同點(diǎn)?！窘獯稹肯嗤c(diǎn)：它們都是插入和刪除操作的位置受限制的線性表。 不同點(diǎn)：棧是限定僅在表尾進(jìn)行插入和刪除的線性表，是后進(jìn)先出的線性表，而隊(duì)列是限定在表的一端進(jìn) 行插入，在另一端進(jìn)行刪除的線性表，是先進(jìn)先出的線性表。9. 利用兩個(gè)棧 S1 和 S2 模擬一個(gè)隊(duì)列，如何利用棧的運(yùn)算實(shí)現(xiàn)

50、隊(duì)列的插入和刪除操作，請簡述算法思想?！窘獯稹坷脙蓚€(gè)棧 S1 和 S2 模擬一個(gè)隊(duì)列，當(dāng)需要向隊(duì)列中插入一個(gè)元素時(shí)，用 S1 來存放已輸入的元 素，即通過向棧 S1 執(zhí)行入棧操作來實(shí)現(xiàn)；當(dāng)需要從隊(duì)列中刪除元素時(shí)，則將 S1 中元素全部送入到 S2 中， 再從 S2 中刪除棧頂元素，最后再將 S2 中元素全部送入到 S1 中；判斷隊(duì)空的條件是：棧 S1 和 S2 同時(shí)為 空。10. 設(shè)計(jì)算法把一個(gè)十進(jìn)制整數(shù)轉(zhuǎn)換為二至九進(jìn)制之間的任一進(jìn)制數(shù)輸出?！窘獯稹克惴ɑ谠恚篘=(N div d)×d + N mod d （div 為整除運(yùn)算，mod 為求余運(yùn)算）。11假設(shè)一個(gè)算術(shù)表達(dá)式中可以

51、包含三種括號：圓括號“（”和“）”，方括號“”和“”以及花括號“”和“”，且這三種括號可按任意的次序嵌套使用。編寫算法判斷給定表達(dá)式中所含括號是否配對出現(xiàn)?！窘獯稹考僭O(shè)表達(dá)式已存入字符數(shù)組 An中，具體算法如下：第 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，按

52、行優(yōu)先存儲(chǔ)，每個(gè)元素占 4 個(gè)存儲(chǔ)單元，A105的存儲(chǔ)地址是 1000，則元素 A1510的存儲(chǔ)地址是（ ）?！窘獯稹?140【分析】數(shù)組 A 中每行共有 6 個(gè)元素，元素 A1510的前面共存儲(chǔ)了(15-10)×6+5 個(gè)元素，每個(gè)元素占 4個(gè)存儲(chǔ)單元，所以，其存儲(chǔ)地址是 1000+140=1140。 設(shè)有一個(gè) 10 階的對稱矩陣 A 采用壓縮存儲(chǔ)，A00為第一個(gè)元素，其存儲(chǔ)地址為 d，每個(gè)元素占 1 個(gè) 存儲(chǔ)單元，則元素 A85的存儲(chǔ)地址為（ ）?！窘獯稹縟+41【分析】元素 A85的前面共存儲(chǔ)了(1+2+8)+5=41 個(gè)元素。 稀疏矩陣一般壓縮存儲(chǔ)方法有兩種，分別是（ ）和（

53、 ）?！窘獯稹咳M順序表，十字鏈表 廣義表(a), (b),c),(d)的長度是（），深度是（），表頭是（），表尾是（）?！窘獯稹?，4，(a)，(b),c),(d) 已知廣義表 LS=(a，(b，c，d)，e)，用 Head 和 Tail 函數(shù)取出 LS 中原子 b 的運(yùn)算是（ ）?！窘獯稹縃ead(Head(Tail(LS)2. 選擇題 二維數(shù)組 A 的每個(gè)元素是由 6 個(gè)字符組成的串，行下標(biāo)的范圍從 08，列下標(biāo)的范圍是從 09，則存 放 A 至少需要（ ）個(gè)字節(jié)，A 的第 8 列和第 5 行共占（ ）個(gè)字節(jié)，若 A 按行優(yōu)先方式存儲(chǔ)， 元素 A85的起始地址與當(dāng) A 按列優(yōu)先方式存儲(chǔ)時(shí)的（ ）元素的起始地址一致。A 90 B 180 C 24