數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言版第版課后習(xí)題答案（精編版）

1、數(shù)據(jù)結(jié)構(gòu)（ c 語(yǔ)言版）（第 2 版）課后習(xí)題答案李冬梅2015.3目錄第 1 章緒論 .第 2 章線(xiàn)性表.第 3 章棧和隊(duì)列.第 4 章串、數(shù)組和廣義表.第 5 章樹(shù)和二叉樹(shù).第 6 章圖 .第 7 章查找 .第 8 章排序 .第 1 章緒論1. 簡(jiǎn)述下列概念：數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項(xiàng)、數(shù)據(jù)對(duì)象、數(shù)據(jù)結(jié)構(gòu)、邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)、抽象數(shù)據(jù)類(lèi)型。答案：數(shù)據(jù) ：是客觀事物的符號(hào)表示，指所有能輸入到計(jì)算機(jī)中并被計(jì)算機(jī)程序處理的符號(hào)的總稱(chēng)。如數(shù)學(xué)計(jì)算中用到的整數(shù)和實(shí)數(shù)，文本編輯所 用到的字符串，多媒體程序處理的圖形、圖像、聲音、動(dòng)畫(huà)等通過(guò)特殊 編碼定義后的數(shù)據(jù)。數(shù)據(jù)元素 ：是數(shù)據(jù)的基本單位，在計(jì)算機(jī)中通常

2、作為一個(gè)整體進(jìn)行考慮和處理。在有些情況下，數(shù)據(jù)元素也稱(chēng)為元素、結(jié)點(diǎn)、記錄等。數(shù)據(jù) 元素用于完整地描述一個(gè)對(duì)象，如一個(gè)學(xué)生記錄，樹(shù)中棋盤(pán)的一個(gè)格局（狀態(tài)）、圖中的一個(gè)頂點(diǎn)等。數(shù)據(jù)項(xiàng) ：是組成數(shù)據(jù)元素的、有獨(dú)立含義的、不可分割的最小單位。例如，學(xué)生基本信息表中的學(xué)號(hào)、姓名、性別等都是數(shù)據(jù)項(xiàng)。數(shù)據(jù)對(duì)象 ：是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個(gè)子集。例如：整數(shù)數(shù)據(jù)對(duì)象是集合n=0 ，± 1，± 2， ，字母字符數(shù)據(jù)對(duì)象是集合 c=a，b，z， a， b，z ，學(xué)生基本信息表也可是一個(gè)數(shù)據(jù)對(duì)象。數(shù)據(jù)結(jié)構(gòu) ：是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。換句話(huà)說(shuō)，數(shù)據(jù)結(jié)構(gòu)是帶“結(jié)

3、構(gòu)”的數(shù)據(jù)元素的集合，“結(jié)構(gòu)”就是指數(shù)據(jù)元素之間存在的關(guān)系。邏輯結(jié)構(gòu) ：從邏輯關(guān)系上描述數(shù)據(jù)，它與數(shù)據(jù)的存儲(chǔ)無(wú)關(guān)，是獨(dú)立于計(jì)算機(jī)的。因此，數(shù)據(jù)的邏輯結(jié)構(gòu)可以看作是從具體問(wèn)題抽象出來(lái)的數(shù) 學(xué)模型。存儲(chǔ)結(jié)構(gòu)：數(shù)據(jù)對(duì)象在計(jì)算機(jī)中的存儲(chǔ)表示，也稱(chēng)為物理結(jié)構(gòu) 。抽象數(shù)據(jù)類(lèi)型：由用戶(hù)定義的，表示應(yīng)用問(wèn)題的數(shù)學(xué)模型，以及定義在這個(gè)模型上的一組操作的總稱(chēng)。具體包括三部分：數(shù)據(jù)對(duì)象、數(shù)據(jù)對(duì) 象上關(guān)系的集合和對(duì)數(shù)據(jù)對(duì)象的基本操作的集合。2. 試舉一個(gè)數(shù)據(jù)結(jié)構(gòu)的例子，敘述其邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)兩方面的含義和相互關(guān)系。答案：例如有一張學(xué)生基本信息表，包括學(xué)生的學(xué)號(hào)、姓名、性別、籍貫、專(zhuān)業(yè)等。每個(gè)學(xué)生基本信息記錄對(duì)應(yīng)一個(gè)

4、數(shù)據(jù)元素，學(xué)生記錄按順序號(hào)排列，形成了學(xué)生基本信息記錄的線(xiàn)性序列。對(duì)于整個(gè)表來(lái)說(shuō)，只有一個(gè)開(kāi)始結(jié)點(diǎn)( 它的前面無(wú)記錄) 和一個(gè)終端結(jié)點(diǎn)( 它的后面無(wú)記錄) ，其他的結(jié)點(diǎn)則各有一個(gè)也只有一個(gè)直接前趨和直接后繼。學(xué)生記錄之間的這種關(guān)系就確定了學(xué)生表的邏輯結(jié)構(gòu)，即線(xiàn)性結(jié)構(gòu)。這些學(xué)生記錄在計(jì)算機(jī)中的存儲(chǔ)表示就是存儲(chǔ)結(jié)構(gòu)。如果用連續(xù)的存儲(chǔ)單元 ( 如用數(shù)組表示) 來(lái)存放這些記錄，則稱(chēng)為順序存儲(chǔ)結(jié)構(gòu)；如果存儲(chǔ)單元不連續(xù)，而是隨機(jī)存放各個(gè)記錄，然后用指針進(jìn)行鏈接，則稱(chēng)為 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。即相同的邏輯結(jié)構(gòu)，可以對(duì)應(yīng)不同的存儲(chǔ)結(jié)構(gòu)。 3簡(jiǎn)述邏輯結(jié)構(gòu)的四種基本關(guān)系并畫(huà)出它們的關(guān)系圖。答案：（ 1）集合結(jié)構(gòu)數(shù)據(jù)元素之

5、間除了“屬于同一集合”的關(guān)系外，別無(wú)其他關(guān)系。例如，確定一名學(xué)生是否為班級(jí)成員，只需將班級(jí)看做一個(gè)集合結(jié)構(gòu)。（ 2）線(xiàn)性結(jié)構(gòu)數(shù)據(jù)元素之間存在一對(duì)一的關(guān)系。例如，將學(xué)生信息數(shù)據(jù)按照其入學(xué)報(bào)到的時(shí)間先后順序進(jìn)行排列，將組成一個(gè)線(xiàn)性結(jié)構(gòu)。（ 3）樹(shù)結(jié)構(gòu)數(shù)據(jù)元素之間存在一對(duì)多的關(guān)系。例如，在班級(jí)的管理體系中，班長(zhǎng)管理多個(gè)組長(zhǎng)，每位組長(zhǎng)管理多名組員，從而構(gòu)成樹(shù)形結(jié)構(gòu)。（ 4）圖結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)數(shù)據(jù)元素之間存在多對(duì)多的關(guān)系。例如，多位同學(xué)之間的朋友關(guān)系， 任何兩位同學(xué)都可以是朋友，從而構(gòu)成圖形結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)。其中樹(shù)結(jié)構(gòu)和圖結(jié)構(gòu)都屬于非線(xiàn)性結(jié)構(gòu)。4. 存儲(chǔ)結(jié)構(gòu)由哪兩種基本的存儲(chǔ)方法實(shí)現(xiàn)？ 答案：（ 1）順序存

6、儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)是借助元素在存儲(chǔ)器中的相對(duì)位置來(lái)表示數(shù)據(jù)元素之間的邏輯關(guān)系，通常借助程序設(shè)計(jì)語(yǔ)言的數(shù)組類(lèi)型來(lái)描述。（ 2）鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)要求所有的元素依次存放在一片連續(xù)的存儲(chǔ)空間中，而鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，無(wú)需占用一整塊存儲(chǔ)空間。但為了表示結(jié)點(diǎn)之間的關(guān) 系，需要給每個(gè)結(jié)點(diǎn)附加指針字段，用于存放后繼元素的存儲(chǔ)地址。所以鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)通常借助于程序設(shè)計(jì)語(yǔ)言的指針類(lèi)型來(lái)描述。5. 選擇題（ 1）在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成（）。a動(dòng)態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)b緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu) c線(xiàn)性結(jié)構(gòu)和非線(xiàn)性結(jié)構(gòu)d內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)答案： c（ 2）與數(shù)據(jù)元素本身的形式、內(nèi)容、相對(duì)位置、個(gè)數(shù)無(wú)關(guān)的是數(shù)據(jù)的

7、（）。a存儲(chǔ)結(jié)構(gòu)b存儲(chǔ)實(shí)現(xiàn)c邏輯結(jié)構(gòu)d運(yùn)算實(shí)現(xiàn)答案： c（ 3）通常要求同一邏輯結(jié)構(gòu)中的所有數(shù)據(jù)元素具有相同的特性，這意味著（）。a數(shù)據(jù)具有同一特點(diǎn)b. 不僅數(shù)據(jù)元素所包含的數(shù)據(jù)項(xiàng)的個(gè)數(shù)要相同，而且對(duì)應(yīng)數(shù)據(jù)項(xiàng)的類(lèi)型要一致c. 每個(gè)數(shù)據(jù)元素都一樣 d數(shù)據(jù)元素所包含的數(shù)據(jù)項(xiàng)的個(gè)數(shù)要相等答案： b（ 4）以下說(shuō)法正確的是（） 。 a數(shù)據(jù)元素是數(shù)據(jù)的最小單位 b數(shù)據(jù)項(xiàng)是數(shù)據(jù)的基本單位 c數(shù)據(jù)結(jié)構(gòu)是帶有結(jié)構(gòu)的各數(shù)據(jù)項(xiàng)的集合d. 一些表面上很不相同的數(shù)據(jù)可以有相同的邏輯結(jié)構(gòu)答案： d解釋?zhuān)簲?shù)據(jù)元素是數(shù)據(jù)的基本單位，數(shù)據(jù)項(xiàng)是數(shù)據(jù)的最小單位， 數(shù)據(jù)結(jié)構(gòu)是帶有結(jié)構(gòu)的各數(shù)據(jù)元素的集合。（ 5）算法的時(shí)間復(fù)雜度取決

8、于（） 。 a問(wèn)題的規(guī)模b待處理數(shù)據(jù)的初態(tài)c計(jì)算機(jī)的配置d a 和 b答案： d解釋?zhuān)核惴ǖ臅r(shí)間復(fù)雜度不僅與問(wèn)題的規(guī)模有關(guān)，還與問(wèn)題的其他因素有關(guān)。如某些排序的算法，其執(zhí)行時(shí)間與待排序記錄的初始狀態(tài)有關(guān)。為此，有時(shí)會(huì)對(duì)算法有最好、最壞以及平均時(shí)間復(fù)雜度的評(píng)價(jià)。（ 6）以下數(shù)據(jù)結(jié)構(gòu)中，（）是非線(xiàn)性數(shù)據(jù)結(jié)構(gòu)a樹(shù)b字符串c隊(duì)列d棧答案： a6. 試分析下面各程序段的時(shí)間復(fù)雜度。（ 1） x=90; y=100;?while(y>0)if(x>100)x=x-10;y-;else x+;答案： o(1)解釋?zhuān)撼绦虻膱?zhí)行次數(shù)為常數(shù)階。（ 2） for (i=0; i<n; i+)for

9、 (j=0; j<m; j+)aij=0;答案： o(m*n)解釋?zhuān)赫Z(yǔ)句aij=0;的執(zhí)行次數(shù)為m*n。（ 3） s=0;for i=0; i<n; i+)for(j=0; j<n; j+)s+=bij;sum=s;2答案： o(n )2解釋?zhuān)赫Z(yǔ)句s+=bij;的執(zhí)行次數(shù)為n 。（ 4） i=1;while(i<=n)i=i*3;答案： o(log 3 n)解釋?zhuān)赫Z(yǔ)句i=i*3;的執(zhí)行次數(shù)為?log 3 n?。（ 5） x=0;for(i=1; i<n; i+)for (j=1; j<=n-i; j+)x+;2答案： o(n )解釋?zhuān)赫Z(yǔ)句x+; 的執(zhí)行次數(shù)為

10、n-1+n-2+ 1= n(n-1)/2。（ 6） x=n; /n>1y=0;while(x (y+1)* (y+1)y+;答案： o(n)解釋?zhuān)赫Z(yǔ)句y+; 的執(zhí)行次數(shù)為?n?。第 2 章線(xiàn)性表1. 選擇題（ 1）順序表中第一個(gè)元素的存儲(chǔ)地址是100 ，每個(gè)元素的長(zhǎng)度為2，則第5 個(gè)元素的地址是（）。a 110b 108c 100d 120答案： b解釋?zhuān)喉樞虮碇械臄?shù)據(jù)連續(xù)存儲(chǔ)，所以第5 個(gè)元素的地址為：100+2*4=108 。（ 2）在 n 個(gè)結(jié)點(diǎn)的順序表中，算法的時(shí)間復(fù)雜度是o(1) 的操作是（）。a. 訪(fǎng)問(wèn)第i個(gè)結(jié)點(diǎn)（ 1i n）和求第i個(gè)結(jié)點(diǎn)的直接前驅(qū)（2 i n）b. 在第i

11、個(gè)結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)（1 i n）c. 刪除第i個(gè)結(jié)點(diǎn)（ 1i n）d. 將 n 個(gè)結(jié)點(diǎn)從小到大排序答案： a22解釋?zhuān)涸陧樞虮碇胁迦胍粋€(gè)結(jié)點(diǎn)的時(shí)間復(fù)雜度都是o(n ) ，排序的時(shí)間復(fù)雜度為o(n ) 或 o(nlog 2 n) 。順序表是一種隨機(jī)存取結(jié)構(gòu)，訪(fǎng)問(wèn)第i 個(gè)結(jié)點(diǎn)和求第i個(gè)結(jié)點(diǎn)的直接前驅(qū)都可以直接通過(guò)數(shù)組的下標(biāo)直接定位，時(shí)間復(fù)雜度是o(1) 。（ 3） 向一個(gè)有127 個(gè)元素的順序表中插入一個(gè)新元素并保持原來(lái)順序不變，平均要移動(dòng)的元素個(gè)數(shù)為（）。a 8b 63.5c 63d 7答案： b解釋?zhuān)浩骄苿?dòng)的元素個(gè)數(shù)為：n/2 。（ 4）鏈接存儲(chǔ)的存儲(chǔ)結(jié)構(gòu)所占存儲(chǔ)空間（）。a. 分兩部

12、分，一部分存放結(jié)點(diǎn)值，另一部分存放表示結(jié)點(diǎn)間關(guān)系的指針b. 只有一部分，存放結(jié)點(diǎn)值 c只有一部分，存儲(chǔ)表示結(jié)點(diǎn)間關(guān)系的指針d分兩部分，一部分存放結(jié)點(diǎn)值，另一部分存放結(jié)點(diǎn)所占單元數(shù)答案： a（ 5）線(xiàn)性表若采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí)，要求內(nèi)存中可用存儲(chǔ)單元的地址（）。a必須是連續(xù)的c一定是不連續(xù)的bd部分地址必須是連續(xù)的連續(xù)或不連續(xù)都可以答案： d（ 6）線(xiàn)性表在（）情況下適用于使用鏈?zhǔn)浇Y(jié)構(gòu)實(shí)現(xiàn)。 a需經(jīng)常修改中的結(jié)點(diǎn)值需不斷對(duì)進(jìn)行刪除插入c中含有大量的結(jié)點(diǎn)中結(jié)點(diǎn)結(jié)構(gòu)復(fù)雜答案： b解釋?zhuān)烘湵碜畲蟮膬?yōu)點(diǎn)在于插入和刪除時(shí)不需要移動(dòng)數(shù)據(jù)，直接修改指針即可。（ 7）單鏈表的存儲(chǔ)密度（）。a大于1b等于1c小于

13、1d不能確定答案： c解釋?zhuān)捍鎯?chǔ)密度是指一個(gè)結(jié)點(diǎn)數(shù)據(jù)本身所占的存儲(chǔ)空間和整個(gè)結(jié)點(diǎn)所占的存儲(chǔ)空間之比，假設(shè)單鏈表一個(gè)結(jié)點(diǎn)本身所占的空間為d，指針域所占的空間為n，則存儲(chǔ)密度為：d/(d+n) ，一定小于1。（ 8）將兩個(gè)各有n 個(gè)元素的有序表歸并成一個(gè)有序表，其最少的比較次數(shù)是（）。a nb 2n-1c 2nd n-1答案： a解釋?zhuān)寒?dāng)?shù)谝粋€(gè)有序表中所有的元素都小于（或大于）第二個(gè)表中的元素，只需要用第二個(gè)表中的第一個(gè)元素依次與第一個(gè)表的元素比較，總計(jì)比較n 次。（ 9）在一個(gè)長(zhǎng)度為n 的順序表中，在第i個(gè)元素（ 1 i n+1 ）之前插入一個(gè)新元素時(shí)須向后移動(dòng)（）個(gè)元素。a n-ib n-i+

14、1c n-i-1d i答案： b(10) 線(xiàn)性表l=(a 1 ， a2,an) ，下列說(shuō)法正確的是（）。 a每個(gè)元素都有一個(gè)直接前驅(qū)和一個(gè)直接后繼 b線(xiàn)性表中至少有一個(gè)元素 c表中諸元素的排列必須是由小到大或由大到小d除第一個(gè)和最后一個(gè)元素外，其余每個(gè)元素都有一個(gè)且僅有一個(gè)直接前驅(qū)和直接后繼。答案： d(11) 創(chuàng)建一個(gè)包括n 個(gè)結(jié)點(diǎn)的有序單鏈表的時(shí)間復(fù)雜度是（）。2a o(1)b o(n)c o(n )d o(nlog 2 n)答案： c解釋?zhuān)簡(jiǎn)捂湵韯?chuàng)建的時(shí)間復(fù)雜度是o(n) ，而要建立一個(gè)有序的單鏈表，則每生成一個(gè)新結(jié)點(diǎn)時(shí)需要和已有的結(jié)點(diǎn)進(jìn)行比較，確定合適的插入位置，所以時(shí)間復(fù)雜度是o(n

15、2) 。(12) 以下說(shuō)法錯(cuò)誤的是（）。a. 求表長(zhǎng)、定位這兩種運(yùn)算在采用順序存儲(chǔ)結(jié)構(gòu)時(shí)實(shí)現(xiàn)的效率不比采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí)實(shí)現(xiàn)的效率低b. 順序存儲(chǔ)的線(xiàn)性表可以隨機(jī)存取c. 由于順序存儲(chǔ)要求連續(xù)的存儲(chǔ)區(qū)域，所以在存儲(chǔ)管理上不夠靈活d. 線(xiàn)性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)優(yōu)于順序存儲(chǔ)結(jié)構(gòu)答案： d解釋?zhuān)烘準(zhǔn)酱鎯?chǔ)結(jié)構(gòu)和順序存儲(chǔ)結(jié)構(gòu)各有優(yōu)缺點(diǎn)，有不同的適用場(chǎng)合。(13) 在單鏈表中，要將s 所指結(jié)點(diǎn)插入到p 所指結(jié)點(diǎn)之后，其語(yǔ)句應(yīng)為（）。a. s->next=p+1; p->next=s;b. (*p).next=s; (*s).next=(*p).next;c. s->next=p->ne

16、xt; p->next=s->next;d. s->next=p->next; p->next=s;答案： d(14) 在雙向鏈表存儲(chǔ)結(jié)構(gòu)中，刪除p 所指的結(jié)點(diǎn)時(shí)須修改指針（）。a. p->next->prior=p->prior; p->prior->next=p->next;b. p->next=p->next->next; p->next->prior=p;c. p->prior->next=p; p->prior=p->prior->prior;d. p->

17、;prior=p->next->next; p->next=p->prior->prior;答案： a(15) 在雙向循環(huán)鏈表中，在p 指針?biāo)傅慕Y(jié)點(diǎn)后插入q 所指向的新結(jié)點(diǎn)，其修改指針的操作是（）。a. p->next=q; q->prior=p; p->next->prior=q; q->next=q;b. p->next=q; p->next->prior=q; q->prior=p; q->next=p->next;c. q->prior=p; q->next=p->nex

18、t; p->next->prior=q; p->next=q;d. q->prior=p; q->next=p->next; p->next=q; p->next->prior=q;答案： c 2算法設(shè)計(jì)題（ 1）將兩個(gè)遞增的有序鏈表合并為一個(gè)遞增的有序鏈表。要求結(jié)果鏈表仍使用原來(lái)兩個(gè)鏈表的存儲(chǔ)空間,不另外占用其它的存儲(chǔ)空間。表中不允許有重復(fù)的數(shù)據(jù)。 題目分析 合并后的新表使用頭指針lc 指向， pa 和 pb 分別是鏈表la 和 lb 的工作指針 , 初始化為相應(yīng)鏈表的第一個(gè)結(jié)點(diǎn)，從第一個(gè)結(jié)點(diǎn)開(kāi)始進(jìn)行比較，當(dāng)兩個(gè)鏈表la 和 lb 均為到

19、達(dá)表尾結(jié)點(diǎn)時(shí)，依次摘取其中較小者重新鏈接在lc 表的最后。如果兩個(gè)表中的元素相等，只摘取la 表中的元素，刪除lb 表中的元素，這樣確保合并后表中無(wú)重復(fù)的元素。當(dāng)一個(gè)表到達(dá)表尾結(jié)點(diǎn)，為空時(shí)，將非空表的剩余元素直接鏈接在lc 表的最后。 算法描述 void mergelist(linklist &la,linklist &lb,linklist &lc)/合并鏈表la 和 lb，合并后的新表使用頭指針lc 指向pa=la->next;pb=lb->next;/pa和 pb 分別是鏈表la 和 lb 的工作指針, 初始化為相應(yīng)鏈表的第一個(gè)結(jié)點(diǎn)lc=pc=la;/

20、用 la 的頭結(jié)點(diǎn)作為lc 的頭結(jié)點(diǎn)while(pa && pb)if(pa->data<pb->data)pc->next=pa;pc=pa;pa=pa->next;/取較小者la 中的元素，將pa 鏈接在pc 的后面， pa 指針后移else if(pa->data>pb->data) pc->next=pb; pc=pb; pb=pb->next;/取較小者lb 中的元素，將pb 鏈接在pc 的后面， pb 指針后移else /相等時(shí)取la 中的元素，刪除lb 中的元素pc->next=pa;pc=pa;p

21、a=pa->next;q=pb->next;delete pb ;pb =q;pc->next=pa?pa:pb;/插入剩余段delete lb;/釋放 lb 的頭結(jié)點(diǎn)（ 2）將兩個(gè)非遞減的有序鏈表合并為一個(gè)非遞增的有序鏈表。要求結(jié)果鏈表仍使用原來(lái)兩個(gè)鏈表的存儲(chǔ)空間,不另外占用其它的存儲(chǔ)空間。表中允許有重復(fù)的數(shù)據(jù)。 題目分析 合并后的新表使用頭指針lc 指向， pa 和 pb 分別是鏈表la 和 lb 的工作指針 , 初始化為相應(yīng)鏈表的第一個(gè)結(jié)點(diǎn)，從第一個(gè)結(jié)點(diǎn)開(kāi)始進(jìn)行比較，當(dāng)兩個(gè)鏈表la 和 lb 均為到達(dá)表尾結(jié)點(diǎn)時(shí)，依次摘取其中較小者重新鏈接在lc 表的表頭結(jié)點(diǎn)之后，如果兩

22、個(gè)表中的元素相等，只摘取la表中的元素，保留lb 表中的元素。當(dāng)一個(gè)表到達(dá)表尾結(jié)點(diǎn)，為空時(shí)，將非空表的剩余元素依次摘取，鏈接在lc 表的表頭結(jié)點(diǎn)之后。 算法描述 void mergelist(linklist& la, linklist& lb, linklist& lc, )/合并鏈表la 和 lb ，合并后的新表使用頭指針lc 指向pa=la->next;pb=lb->next;/pa和 pb 分別是鏈表la 和 lb 的工作指針, 初始化為相應(yīng)鏈表的第一個(gè)結(jié)點(diǎn)lc=pc=la; /用 la 的頭結(jié)點(diǎn)作為lc 的頭結(jié)點(diǎn)lc->next=null;w

23、hile(pa|pb )/只要存在一個(gè)非空表，用q 指向待摘取的元素if(!pa)q=pb;pb=pb->next;/la表為空，用q 指向 pb， pb 指針后移else if(!pb)q=pa;pa=pa->next;/lb表為空，用q 指向 pa， pa 指針后移else if(pa->data<=pb->data)q=pa;pa=pa->next;/取較小者（包括相等）la 中的元素，用q 指向 pa ， pa 指針后移else q=pb;pb=pb->next;/取較小者lb 中的元素，用q 指向 pb， pb 指針后移q->next

24、= lc->next;lc->next = q;/將 q 指向的結(jié)點(diǎn)插在lc表的表頭結(jié)點(diǎn)之后delete lb;/釋放 lb 的頭結(jié)點(diǎn)（ 3）已知兩個(gè)鏈表a 和 b 分別表示兩個(gè)集合，其元素遞增排列。請(qǐng)?jiān)O(shè)計(jì)算法求出a 與 b 的交集，并存放于a 鏈表中。 題目分析 只有同時(shí)出現(xiàn)在兩集合中的元素才出現(xiàn)在結(jié)果表中, 合并后的新表使用頭指針lc 指向。 pa 和 pb 分別是鏈表la 和 lb 的工作指針, 初始化為相應(yīng)鏈表的第一個(gè)結(jié)點(diǎn)，從第一個(gè)結(jié)點(diǎn)開(kāi)始進(jìn)行比較，當(dāng)兩個(gè)鏈表la 和 lb 均為到達(dá)表尾結(jié)點(diǎn)時(shí)，如果兩個(gè)表中相等的元素時(shí)，摘取la 表中的元素，刪除lb 表中的元素；如果其中一

25、個(gè)表中的元素較小時(shí)，刪除此表中較小的元素，此表的工作指針后移。當(dāng)鏈表la 和 lb 有一個(gè)到達(dá)表尾結(jié)點(diǎn)，為空時(shí)，依次刪除另一個(gè)非空表中的所有元素。 算法描述 void mix(linklist& la, linklist& lb, linklist& lc)pa=la->next;pb=lb->next;pa 和 pb 分別是鏈表la 和 lb 的工作指針, 初始化為相應(yīng)鏈表的第一個(gè)結(jié)點(diǎn)lc=pc=la; /用 la 的頭結(jié)點(diǎn)作為lc 的頭結(jié)點(diǎn)while(pa&&pb) if(pa->data=pb->data) 交集并入結(jié)果表中

26、。 pc->next=pa;pc=pa;pa=pa->next;u=pb;pb=pb->next; delete u;else if(pa->data<pb->data) u=pa;pa=pa->next; delete u;else u=pb; pb=pb->next; delete u;while(pa) u=pa; pa=pa->next; deleteu; 釋放結(jié)點(diǎn)空間while(pb) u=pb; pb=pb->next; delete u; 釋放結(jié)點(diǎn)空間pc- >next=null;置鏈表尾標(biāo)記。delete lb;

27、/釋放 lb 的頭結(jié)點(diǎn)（ 4）已知兩個(gè)鏈表a 和 b 分別表示兩個(gè)集合，其元素遞增排列。請(qǐng)?jiān)O(shè)計(jì)算法求出兩個(gè)集合a 和 b 的差集（即僅由在a 中出現(xiàn)而不在b 中出現(xiàn)的元素所構(gòu)成的集合），并以同樣的形式存儲(chǔ)，同時(shí)返回該集合的元素個(gè)數(shù)。 題目分析 求兩個(gè)集合a 和 b 的差集是指在a 中刪除a 和 b 中共有的元素，即刪除鏈表中的相應(yīng)結(jié)點(diǎn), 所以要保存待刪除結(jié)點(diǎn)的前驅(qū)，使用指針pre指向前驅(qū)結(jié)點(diǎn)。pa 和 pb 分別是鏈表la 和 lb 的工作指針, 初始化為相應(yīng)鏈表的第一個(gè)結(jié)點(diǎn)，從第一個(gè)結(jié)點(diǎn)開(kāi)始進(jìn)行比較，當(dāng)兩個(gè)鏈表la 和 lb 均為到達(dá)表尾結(jié)點(diǎn)時(shí)，如果la 表中的元素小于lb 表中的元素，pr

28、e置為la 表的工作指針pa 刪除 lb 表中的元素；如果其中一個(gè)表中的元素較小時(shí)，刪除此表中較小的元素，此表的工作指針后移。當(dāng)鏈表la 和 lb 有一個(gè)為空時(shí)，依次刪除另一個(gè)非空表中的所有元素。 算法描述 void difference（ linklist& la, linklist& lb,int *n） 差集的結(jié)果存儲(chǔ)于單鏈表la 中， *n 是結(jié)果集合中元素個(gè)數(shù)，調(diào)用時(shí)為0pa=la->next; pb=lb->next; pa 和 pb 分別是鏈表la 和 lb 的工作指針, 初始化為相應(yīng)鏈表的第一個(gè)結(jié)點(diǎn)pre=la; pre為 la 中 pa 所指結(jié)點(diǎn)的

29、前驅(qū)結(jié)點(diǎn)的指針while（ pa&&pb）if（ pa->data<q->data） pre=pa;pa=pa->next;*n+; a 鏈表中當(dāng)前結(jié)點(diǎn)指針后移else if（ pa->data>q->data） q=q->next;b 鏈表中當(dāng)前結(jié)點(diǎn)指針后移else pre->next=pa->next;處理a， b 中元素值相同的結(jié)點(diǎn)，應(yīng)刪除u=pa; pa=pa->next; delete u;刪除結(jié)點(diǎn)（ 5）設(shè)計(jì)算法將一個(gè)帶頭結(jié)點(diǎn)的單鏈表a 分解為兩個(gè)具有相同結(jié)構(gòu)的鏈表b、c，其中b 表的結(jié)點(diǎn)為a 表中值

30、小于零的結(jié)點(diǎn)，而c表的結(jié)點(diǎn)為 a 表中值大于零的結(jié)點(diǎn)（鏈表a 中的元素為非零整數(shù)，要求b、c 表利用 a 表的結(jié)點(diǎn)） 。 題目分析 b 表的頭結(jié)點(diǎn)使用原來(lái)a 表的頭結(jié)點(diǎn)，為c 表新申請(qǐng)一個(gè)頭結(jié)點(diǎn)。從a 表的第一個(gè)結(jié)點(diǎn)開(kāi)始，依次取其每個(gè)結(jié)點(diǎn)p，判斷結(jié)點(diǎn)p 的值是否小于0，利用前插法，將小于0 的結(jié)點(diǎn)插入b 表, 大于等于0 的結(jié)點(diǎn)插入c 表。 算法描述 void discompose(linkedlist a)b=a;b->next= null; b 表初始化c=newlnode;為c 申請(qǐng)結(jié)點(diǎn)空間c->next=null;c 初始化為空表p=a->next;p 為工作指針wh

31、ile(p!= null) r=p->next;暫存p 的后繼if(p->data<0)p->next=b->next; b->next=p; 將小于0 的結(jié)點(diǎn)鏈入b表, 前插法else p->next=c->next; c->next=p; 將大于等于0 的結(jié)點(diǎn)鏈入c 表, 前插法p=r; p 指向新的待處理結(jié)點(diǎn)。（ 6）設(shè)計(jì)一個(gè)算法，通過(guò)一趟遍歷在單鏈表中確定值最大的結(jié)點(diǎn)。 題目分析 假定第一個(gè)結(jié)點(diǎn)中數(shù)據(jù)具有最大值，依次與下一個(gè)元素比較，若其小于下一個(gè)元素，則設(shè)其下一個(gè)元素為最大值，反復(fù)進(jìn)行比較，直到遍歷完該鏈表。 算法描述 elemt

32、ype max (linklist l )if(l->next=null) return null;pmax=l->next; /假定第一個(gè)結(jié)點(diǎn)中數(shù)據(jù)具有最大值p=l->next->next;while(p != null )/如果下一個(gè)結(jié)點(diǎn)存在if(p->data > pmax->data) pmax=p;/如果 p 的值大于pmax的值，則重新賦值p=p->next;/遍歷鏈表return pmax->data;（ 7）設(shè)計(jì)一個(gè)算法，通過(guò)遍歷一趟，將鏈表中所有結(jié)點(diǎn)的鏈接方向逆轉(zhuǎn)，仍利用原表的存儲(chǔ)空間。 題目分析 從首元結(jié)點(diǎn)開(kāi)始，逐個(gè)地把

33、鏈表l 的當(dāng)前結(jié)點(diǎn)p 插入新的鏈表頭部。 算法描述 voidinverse(linklist &l)/逆置帶頭結(jié)點(diǎn)的單鏈表lp=l->next;l->next=null;while ( p) q=p->next;/ q指向 *p的后繼p->next=l->next;l->next=p;/ *p插入在頭結(jié)點(diǎn)之后p = q;（ 8）設(shè)計(jì)一個(gè)算法，刪除遞增有序鏈表中值大于mink且小于 maxk的所有元素（mink 和 maxk 是給定的兩個(gè)參數(shù)，其值可以和表中的元素相同，也可以不同）。 題目分析 分別查找第一個(gè)值>mink的結(jié)點(diǎn)和第一個(gè)值 maxk

34、 的結(jié)點(diǎn)，再修改指針，刪除值大于mink 且小于maxk 的所有元素。 算法描述 void delete(linklist &l, int mink, int maxk) p=l->next; /首元結(jié)點(diǎn)while (p && p->data<=mink) pre=p;p=p->next; /查找第一個(gè)值>mink 的結(jié)點(diǎn)if (p)while (p && p->data<maxk)p=p->next;/查找第一個(gè)值 maxk 的結(jié)點(diǎn)q=pre->next;while (q!=p)pre->ne

35、xt=p;/修改指針 s=q->next;delete q;q=s; /釋放結(jié)點(diǎn)空間/if（ 9）已知p 指向雙向循環(huán)鏈表中的一個(gè)結(jié)點(diǎn)，其結(jié)點(diǎn)結(jié)構(gòu)為data 、prior、next三個(gè)域，寫(xiě)出算法change(p),交換 p 所指向的結(jié)點(diǎn)和它的前綴結(jié)點(diǎn)的順序。 題目分析 知道雙向循環(huán)鏈表中的一個(gè)結(jié)點(diǎn)，與前驅(qū)交換涉及到四個(gè)結(jié)點(diǎn)（p 結(jié)點(diǎn)，前驅(qū)結(jié)點(diǎn)，前驅(qū)的前驅(qū)結(jié)點(diǎn)，后繼結(jié)點(diǎn)）六條鏈。 算法描述 voidexchange（ linkedlist p） p 是雙向循環(huán)鏈表中的一個(gè)結(jié)點(diǎn)，本算法將p 所指結(jié)點(diǎn)與其前驅(qū)結(jié)點(diǎn)交換。q=p->llink；q->llink->rlink=p

36、；p 的前驅(qū)的前驅(qū)之后繼為p p->llink=q->llink；p 的前驅(qū)指向其前驅(qū)的前驅(qū)。q->rlink=p->rlink；p 的前驅(qū)的后繼為p 的后繼。q->llink=p；p 與其前驅(qū)交換p->rlink->llink=q；p 的后繼的前驅(qū)指向原p 的前驅(qū)p->rlink=q；p 的后繼指向其原來(lái)的前驅(qū) 算法exchange結(jié)束。（ 10）已知長(zhǎng)度為n 的線(xiàn)性表a 采用順序存儲(chǔ)結(jié)構(gòu)，請(qǐng)寫(xiě)一時(shí)間復(fù)雜度為 o(n) 、空間復(fù)雜度為o(1) 的算法，該算法刪除線(xiàn)性表中所有值為item的數(shù)據(jù)元素。 題目分析 在順序存儲(chǔ)的線(xiàn)性表上刪除元素，通常要

37、涉及到一系列元素的移動(dòng)（刪第i個(gè)元素，第i+1至第 n 個(gè)元素要依次前移）。本題要求刪除線(xiàn)性表中所有值為item的數(shù)據(jù)元素，并未要求元素間的相對(duì)位置不變。因此可以考慮設(shè)頭尾兩個(gè)指針（i=1 ， j=n ），從兩端向中間移動(dòng)，凡遇到值item的數(shù)據(jù)元素時(shí)，直接將右端元素左移至值為item的數(shù)據(jù)元素位置。 算法描述 voiddelete（ elemtype a ， intn） a 是有 n 個(gè)元素的一維數(shù)組，本算法刪除a 中所有值為item的元素。i=1； j=n ；設(shè)置數(shù)組低、高端指針（下標(biāo)）。while（ i<j）while（ i<j && ai!=item） i+

38、 ；若值不為item ，左移指針。if（ i<j） while（ i<j && aj=item） j-；若右端元素為item ，指針左移if（ i<j） ai+=aj-；第 3 章棧和隊(duì)列1. 選擇題（ 1）若讓元素1， 2， 3， 4， 5 依次進(jìn)棧，則出棧次序不可能出現(xiàn)在（）種情況。a 5， 4， 3， 2， 1b 2， 1， 5， 4， 3c 4， 3， 1， 2， 5 d 2， 3， 5， 4， 1答案： c解釋?zhuān)簵Ｊ呛筮M(jìn)先出的線(xiàn)性表，不難發(fā)現(xiàn)c 選項(xiàng)中元素1 比元素2先出棧，違背了棧的后進(jìn)先出原則，所以不可能出現(xiàn)c 選項(xiàng)所示的情況。（ 2）若已知一個(gè)

39、棧的入棧序列是1， 2， 3， n，其輸出序列為p1 ， p2， p3 ， pn ，若 p1=n，則 pi為（）。a ib n-ic n-i+1 d不確定答案： c解釋?zhuān)簵Ｊ呛筮M(jìn)先出的線(xiàn)性表，一個(gè)棧的入棧序列是1， 2，3， n，而輸出序列的第一個(gè)元素為n，說(shuō)明1， 2， 3， n 一次性全部進(jìn)棧，再進(jìn)行輸出，所以p1=n ， p2=n-1 ， pi=n-i+1。（ 3）數(shù)組用來(lái)表示一個(gè)循環(huán)隊(duì)列，為當(dāng)前隊(duì)列頭元素的前一位置，為隊(duì)尾元素的位置，假定隊(duì)列中元素的個(gè)數(shù)小于，計(jì)算隊(duì)列中元素個(gè)數(shù)的公式為（）。a r-fb (n+f-r)%nc n+r-f d（ n+r-f)%n答案： d解釋?zhuān)簩?duì)于非循環(huán)

40、隊(duì)列，尾指針和頭指針的差值便是隊(duì)列的長(zhǎng)度，而對(duì)于循環(huán)隊(duì)列，差值可能為負(fù)數(shù)，所以需要將差值加上maxsize（本題為n），然后與maxsize（本題為n）求余，即（n+r-f)%n。（ 4）鏈?zhǔn)綏＝Y(jié)點(diǎn)為：(data,link)， top指向棧頂 . 若想摘除棧頂結(jié)點(diǎn)，并將刪除結(jié)點(diǎn)的值保存到x 中, 則應(yīng)執(zhí)行操作（）。a. x=top->data;top=top->link；b. top=top->link;x=top->link；c. x=top;top=top->link；d x=top->link； 答案： a解釋?zhuān)?x=top->data將結(jié)點(diǎn)的值

41、保存到x 中， top=top->link棧頂指針指向棧頂下一結(jié)點(diǎn)，即摘除棧頂結(jié)點(diǎn)。（ 5）設(shè)有一個(gè)遞歸算法如下? ? int fact(int n) ? /n大于等于0? ? if(n<=0) return 1;? ? else return n*fact(n-1);? ? 則計(jì)算fact(n)需要調(diào)用該函數(shù)的次數(shù)為（）。 ?a ?n+1? ?b ?n-1?c n?d. n+2答案： a解釋?zhuān)禾厥庵捣?。設(shè)n=0，易知僅調(diào)用一次fact(n)函數(shù)，故選a。（ 6）棧在 ?（）中有所應(yīng)用。a遞歸調(diào)用b函數(shù)調(diào)用c表達(dá)式求值d前三個(gè)選項(xiàng)都有答案： d解釋?zhuān)哼f歸調(diào)用、函數(shù)調(diào)用、表達(dá)式求值均

42、用到了棧的后進(jìn)先出性質(zhì)。（ 7）為解決計(jì)算機(jī)主機(jī)與打印機(jī)間速度不匹配問(wèn)題，通常設(shè)一個(gè)打印數(shù)據(jù)緩沖區(qū)。主機(jī)將要輸出的數(shù)據(jù)依次寫(xiě)入該緩沖區(qū)，而打印機(jī)則依 次從該緩沖區(qū)中取出數(shù)據(jù)。該緩沖區(qū)的邏輯結(jié)構(gòu)應(yīng)該是（）。a隊(duì)列b棧c 線(xiàn)性表d有序表答案： a解釋?zhuān)航鉀Q緩沖區(qū)問(wèn)題應(yīng)利用一種先進(jìn)先出的線(xiàn)性表，而隊(duì)列正是一種先進(jìn)先出的線(xiàn)性表。（ 8）設(shè)棧s 和隊(duì)列q的初始狀態(tài)為空，元素e1 、e2 、e3 、e4 、e5 和e6 依次進(jìn)入棧s，一個(gè)元素出棧后即進(jìn)入q，若 6 個(gè)元素出隊(duì)的序列是e2 、e4、e3 、e6 、e5 和 e1，則棧s 的容量至少應(yīng)該是（）。a 2b 3c 4d 6答案： b解釋?zhuān)涸爻鲫?duì)

43、的序列是e2、e4 、 e3、e6、 e5 和 e1，可知元素入隊(duì)的序列是e2、e4、 e3、 e6 、e5 和 e1，即元素出棧的序列也是e2 、e4 、e3、e6 、e5 和 e1，而元素e1、e2、 e3、 e4、 e5 和 e6 依次進(jìn)入棧， 易知棧s 中最多同時(shí)存在3 個(gè)元素，故棧s 的容量至少為3。（ 9）若一個(gè)棧以向量v1.n存儲(chǔ)，初始棧頂指針top設(shè)為 n+1 ，則元素 x 進(jìn)棧的正確操作是()。a top+; vtop=x;b vtop=x; top+;c top-; vtop=x;d vtop=x; top-;答案： c解釋?zhuān)撼跏紬ｍ斨羔榯op為 n+1，說(shuō)明元素從數(shù)組向量

44、的高端地址進(jìn)棧，又因?yàn)樵卮鎯?chǔ)在向量空間v1.n中，所以進(jìn)棧時(shí)top指針先下移變?yōu)閚，之后將元素x 存儲(chǔ)在vn。（ 10）設(shè)計(jì)一個(gè)判別表達(dá)式中左，右括號(hào)是否配對(duì)出現(xiàn)的算法，采用（）數(shù)據(jù)結(jié)構(gòu)最佳。a線(xiàn)性表的順序存儲(chǔ)結(jié)構(gòu)b隊(duì)列c.線(xiàn)性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)d.棧答案： d解釋?zhuān)豪脳５暮筮M(jìn)先出原則。（ 11）用鏈接方式存儲(chǔ)的隊(duì)列，在進(jìn)行刪除運(yùn)算時(shí)（）。a.僅修改頭指針b.僅修改尾指針c.頭、尾指針都要修改d.頭、尾指針可能都要修改答案： d解釋?zhuān)阂话闱闆r下只修改頭指針，但是，當(dāng)刪除的是隊(duì)列中最后一個(gè)元素時(shí)，隊(duì)尾指針也丟失了，因此需對(duì)隊(duì)尾指針重新賦值。（ 12）循環(huán)隊(duì)列存儲(chǔ)在數(shù)組a0.m中，則入隊(duì)時(shí)的操作

45、為（）。a. rear=rear+1b. rear=(rear+1)%(m-1)c. rear=(rear+1)%md. rear=(rear+1)%(m+1)答案： d解釋?zhuān)簲?shù)組a0.m中共含有m+1個(gè)元素，故在求模運(yùn)算時(shí)應(yīng)除以m+1。（ 13）最大容量為n 的循環(huán)隊(duì)列，隊(duì)尾指針是rear，隊(duì)頭是front， 則隊(duì)空的條件是（）。a. (rear+1)%n=frontb. rear=frontc rear+1=frontd. (rear- l)%n=front答案： b解釋?zhuān)鹤畲笕萘繛閚 的循環(huán)隊(duì)列，隊(duì)滿(mǎn)條件是(rear+1)%n=front，隊(duì)空條件是rear=front。（ 14）棧和隊(duì)

46、列的共同點(diǎn)是（）。a.都是先進(jìn)先出b.都是先進(jìn)后出c.只允許在端點(diǎn)處插入和刪除元素d.沒(méi)有共同點(diǎn)答案： c解釋?zhuān)簵Ｖ辉试S在棧頂處進(jìn)行插入和刪除元素，隊(duì)列只允許在隊(duì)尾插入元素和在隊(duì)頭刪除元素。（ 15）一個(gè)遞歸算法必須包括（）。a.遞歸部分b.終止條件和遞歸部分c.迭代部分d.終止條件和迭代部分答案： b2. 算法設(shè)計(jì)題（ 1）將編號(hào)為0 和 1 的兩個(gè)棧存放于一個(gè)數(shù)組空間vm 中，棧底分別處于數(shù)組的兩端。當(dāng)?shù)? 號(hào)棧的棧頂指針top0等于 -1時(shí)該棧為空， 當(dāng)?shù)?1 號(hào)棧的棧頂指針top1等于 m時(shí)該棧為空。兩個(gè)棧均從兩端向中間增長(zhǎng)。試編寫(xiě)雙棧初始化，判斷?？?、棧滿(mǎn)、進(jìn)棧和出棧等算法的函數(shù)。雙棧數(shù)據(jù)結(jié)構(gòu)的定義如下：typedef structint top2,bot2;selemtype *v;/棧頂和棧底指針棧數(shù)組int m;/棧最大可容納