數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）（第2版）課后習(xí)題答案李冬梅 2015.3目 錄第1章 緒論1第2章 線性表5第3章 棧和隊(duì)列13第4章 串、數(shù)組和廣義表26第5章 樹和二叉樹33第6章 圖43第7章 查找54第8章 排序6573第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ù)類型。答案：數(shù)據(jù)：是客觀事物的符號(hào)表示，指所有能輸入到計(jì)算機(jī)中并被計(jì)算機(jī)程序處理的符號(hào)的總稱。如數(shù)學(xué)計(jì)算中用到的整數(shù)和實(shí)數(shù)，文本編輯所用到的字符串，多媒體程序處理的圖形、圖像、聲音、動(dòng)畫等通過(guò)特殊編碼定義后的數(shù)據(jù)。數(shù)據(jù)元素：是數(shù)據(jù)的基本單位，在計(jì)算機(jī)中通常作為一個(gè)整體進(jìn)行考慮和處理。在有些情況下，數(shù)據(jù)元素也稱為元素、結(jié)點(diǎn)、記錄等。數(shù)據(jù)元素用于完整地描述一個(gè)對(duì)象，如一個(gè)學(xué)生記錄，樹中棋盤的一個(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ù)元素的集合。換句話說(shuō)，數(shù)據(jù)結(jié)構(gòu)是帶“結(jié)構(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ǔ)表示，也稱為物理結(jié)構(gòu)。抽象數(shù)據(jù)類型：由用戶定義的，表示應(yīng)用問(wèn)題的數(shù)學(xué)模型，以及定義在這個(gè)模型上的一組操作的總稱。具體包括三部分：數(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)、姓名、性別、籍貫、專業(yè)等。每個(gè)學(xué)生基本信息記錄對(duì)應(yīng)一個(gè)數(shù)據(jù)元素，學(xué)生記錄按順序號(hào)排列，形成了學(xué)生基本信息記錄的線性序列。對(duì)于整個(gè)表來(lái)說(shuō)，只有一個(gè)開始結(jié)點(diǎn)(它的前面無(wú)記錄)和一個(gè)終端結(jié)點(diǎn)(它的后面無(wú)記錄)，其他的結(jié)點(diǎn)則各有一個(gè)也只有一個(gè)直接前趨和直接后繼。學(xué)生記錄之間的這種關(guān)系就確定了學(xué)生表的邏輯結(jié)構(gòu)，即線性結(jié)構(gòu)。這些學(xué)生記錄在計(jì)算機(jī)中的存儲(chǔ)表示就是存儲(chǔ)結(jié)構(gòu)。如果用連續(xù)的存儲(chǔ)單元(如用數(shù)組表示)來(lái)存放這些記錄，則稱為順序存儲(chǔ)結(jié)構(gòu)；如果存儲(chǔ)單元不連續(xù)，而是隨機(jī)存放各個(gè)記錄，然后用指針進(jìn)行鏈接，則稱為鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。即相同的邏輯結(jié)構(gòu)，可以對(duì)應(yīng)不同的存儲(chǔ)結(jié)構(gòu)。3簡(jiǎn)述邏輯結(jié)構(gòu)的四種基本關(guān)系并畫出它們的關(guān)系圖。答案：（1）集合結(jié)構(gòu)數(shù)據(jù)元素之間除了“屬于同一集合”的關(guān)系外，別無(wú)其他關(guān)系。例如，確定一名學(xué)生是否為班級(jí)成員，只需將班級(jí)看做一個(gè)集合結(jié)構(gòu)。（2）線性結(jié)構(gòu)數(shù)據(jù)元素之間存在一對(duì)一的關(guān)系。例如，將學(xué)生信息數(shù)據(jù)按照其入學(xué)報(bào)到的時(shí)間先后順序進(jìn)行排列，將組成一個(gè)線性結(jié)構(gòu)。（3）樹結(jié)構(gòu)數(shù)據(jù)元素之間存在一對(duì)多的關(guān)系。例如，在班級(jí)的管理體系中，班長(zhǎng)管理多個(gè)組長(zhǎng)，每位組長(zhǎng)管理多名組員，從而構(gòu)成樹形結(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)。其中樹結(jié)構(gòu)和圖結(jié)構(gòu)都屬于非線性結(jié)構(gòu)。 四類基本邏輯結(jié)構(gòu)關(guān)系圖4存儲(chǔ)結(jié)構(gòu)由哪兩種基本的存儲(chǔ)方法實(shí)現(xiàn)？答案：（1）順序存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)是借助元素在存儲(chǔ)器中的相對(duì)位置來(lái)表示數(shù)據(jù)元素之間的邏輯關(guān)系，通常借助程序設(shè)計(jì)語(yǔ)言的數(shù)組類型來(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)描述。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線性結(jié)構(gòu)和非線性結(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ù)的（ ）。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)的類型要一致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解釋：數(shù)據(jù)元素是數(shù)據(jù)的基本單位，數(shù)據(jù)項(xiàng)是數(shù)據(jù)的最小單位，數(shù)據(jù)結(jié)構(gòu)是帶有結(jié)構(gòu)的各數(shù)據(jù)元素的集合。（5）算法的時(shí)間復(fù)雜度取決于（ ）。A問(wèn)題的規(guī)模B待處理數(shù)據(jù)的初態(tài)C計(jì)算機(jī)的配置DA和B答案：D解釋：算法的時(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)中，（ ）是非線性數(shù)據(jù)結(jié)構(gòu)A樹 B字符串 C隊(duì)列 D棧答案：A6試分析下面各程序段的時(shí)間復(fù)雜度。（1）x=90; y=100;while(y0)if(x100) x=x-10;y-;else x+;答案：O(1)解釋：程序的執(zhí)行次數(shù)為常數(shù)階。（2）for (i=0; in; i+)for (j=0; jm; j+)aij=0;答案：O(m*n)解釋：語(yǔ)句aij=0;的執(zhí)行次數(shù)為m*n。（3）s=0; for i=0; in; i+)for(j=0; jn; j+) s+=Bij;sum=s;答案：O(n2)解釋：語(yǔ)句s+=Bij;的執(zhí)行次數(shù)為n2。（4）i=1; while(i=n) i=i*3;答案：O(log3n) 解釋：語(yǔ)句i=i*3;的執(zhí)行次數(shù)為log3n。（5）x=0;for(i=1; in; i+) for (j=1; j1y=0;while(x(y+1)* (y+1) y+;答案：O()解釋：語(yǔ)句y+;的執(zhí)行次數(shù)為。第2章 線性表1選擇題（1）順序表中第一個(gè)元素的存儲(chǔ)地址是100，每個(gè)元素的長(zhǎng)度為2，則第5個(gè)元素的地址是（ ）。A110 B108 C100 D120答案：B解釋：順序表中的數(shù)據(jù)連續(xù)存儲(chǔ)，所以第5個(gè)元素的地址為：100+2*4=108。（2）在n個(gè)結(jié)點(diǎn)的順序表中，算法的時(shí)間復(fù)雜度是O(1)的操作是（ ）。A訪問(wèn)第i個(gè)結(jié)點(diǎn)（1in）和求第i個(gè)結(jié)點(diǎn)的直接前驅(qū)（2in） B在第i個(gè)結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)（1in）C刪除第i個(gè)結(jié)點(diǎn)（1in）D將n個(gè)結(jié)點(diǎn)從小到大排序答案：A解釋：在順序表中插入一個(gè)結(jié)點(diǎn)的時(shí)間復(fù)雜度都是O(n2)，排序的時(shí)間復(fù)雜度為O(n2)或O(nlog2n)。順序表是一種隨機(jī)存取結(jié)構(gòu)，訪問(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ù)為（ ）。A8 B63.5 C63 D7答案：B解釋：平均要移動(dòng)的元素個(gè)數(shù)為：n/2。（4）鏈接存儲(chǔ)的存儲(chǔ)結(jié)構(gòu)所占存儲(chǔ)空間（ ）。A分兩部分，一部分存放結(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）線性表若采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí)，要求內(nèi)存中可用存儲(chǔ)單元的地址（ ）。A必須是連續(xù)的 B部分地址必須是連續(xù)的C一定是不連續(xù)的 D連續(xù)或不連續(xù)都可以答案：D（6）線性表在（ ）情況下適用于使用鏈?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解釋：鏈表最大的優(yōu)點(diǎn)在于插入和刪除時(shí)不需要移動(dòng)數(shù)據(jù)，直接修改指針即可。（7）單鏈表的存儲(chǔ)密度（ ）。A大于1 B等于1 C小于1 D不能確定答案：C解釋：存儲(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ù)是（ ）。An B2n-1 C2n Dn-1答案：A解釋：當(dāng)?shù)谝粋€(gè)有序表中所有的元素都小于（或大于）第二個(gè)表中的元素，只需要用第二個(gè)表中的第一個(gè)元素依次與第一個(gè)表的元素比較，總計(jì)比較n次。（9）在一個(gè)長(zhǎng)度為n的順序表中，在第i個(gè)元素（1in+1）之前插入一個(gè)新元素時(shí)須向后移動(dòng)（ ）個(gè)元素。An-i Bn-i+1 Cn-i-1 DI答案：B(10) 線性表L=(a1，a2,an)，下列說(shuō)法正確的是（ ）。A每個(gè)元素都有一個(gè)直接前驅(qū)和一個(gè)直接后繼B線性表中至少有一個(gè)元素C表中諸元素的排列必須是由小到大或由大到小D除第一個(gè)和最后一個(gè)元素外，其余每個(gè)元素都有一個(gè)且僅有一個(gè)直接前驅(qū)和直接后繼。答案：D(11) 創(chuàng)建一個(gè)包括n個(gè)結(jié)點(diǎn)的有序單鏈表的時(shí)間復(fù)雜度是（ ）。AO(1) BO(n) CO(n2) DO(nlog2n)答案：C解釋：?jiǎn)捂湵韯?chuàng)建的時(shí)間復(fù)雜度是O(n)，而要建立一個(gè)有序的單鏈表，則每生成一個(gè)新結(jié)點(diǎn)時(shí)需要和已有的結(jié)點(diǎn)進(jìn)行比較，確定合適的插入位置，所以時(shí)間復(fù)雜度是O(n2)。(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ǔ)的線性表可以隨機(jī)存取C由于順序存儲(chǔ)要求連續(xù)的存儲(chǔ)區(qū)域，所以在存儲(chǔ)管理上不夠靈活D線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)優(yōu)于順序存儲(chǔ)結(jié)構(gòu)答案：D解釋：鏈?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)為（ ）。As-next=p+1; p-next=s;B(*p).next=s; (*s).next=(*p).next;Cs-next=p-next; p-next=s-next;Ds-next=p-next; p-next=s; 答案：D (14) 在雙向鏈表存儲(chǔ)結(jié)構(gòu)中，刪除p所指的結(jié)點(diǎn)時(shí)須修改指針（ ）。Ap-next-prior=p-prior; p-prior-next=p-next;Bp-next=p-next-next; p-next-prior=p;Cp-prior-next=p; p-prior=p-prior-prior;Dp-prior=p-next-next; p-next=p-prior-prior;答案：A(15) 在雙向循環(huán)鏈表中，在p指針?biāo)傅慕Y(jié)點(diǎn)后插入q所指向的新結(jié)點(diǎn)，其修改指針的操作是（ ）。Ap-next=q; q-prior=p; p-next-prior=q; q-next=q;Bp-next=q; p-next-prior=q; q-prior=p; q-next=p-next;Cq-prior=p; q-next=p-next; p-next-prior=q; p-next=q;Dq-prior=p; q-next=p-next; p-next=q; p-next-prior=q;答案：C2算法設(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)開始進(jìn)行比較，當(dāng)兩個(gè)鏈表La和Lb均為到達(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; /用La的頭結(jié)點(diǎn)作為L(zhǎng)c的頭結(jié)點(diǎn) while(pa & pb)if(pa-datadata)pc-next=pa;pc=pa;pa=pa-next; /取較小者La中的元素，將pa鏈接在pc的后面，pa指針后移 else if(pa-datapb-data) pc-next=pb; pc=pb; pb=pb-next; /取較小者Lb中的元素，將pb鏈接在pc的后面，pb指針后移 else /相等時(shí)取La中的元素，刪除Lb中的元素pc-next=pa;pc=pa;pa=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)開始進(jìn)行比較，當(dāng)兩個(gè)鏈表La和Lb均為到達(dá)表尾結(jié)點(diǎn)時(shí)，依次摘取其中較小者重新鏈接在Lc表的表頭結(jié)點(diǎn)之后，如果兩個(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)作為L(zhǎng)c的頭結(jié)點(diǎn) Lc-next=NULL; while(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-datadata) q=pa; pa=pa-next;/取較小者（包括相等）La中的元素，用q指向pa，pa指針后移 else q=pb; pb=pb-next;/取較小者Lb中的元素，用q指向pb，pb指針后移 q-next = 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)開始進(jìn)行比較，當(dāng)兩個(gè)鏈表La和Lb均為到達(dá)表尾結(jié)點(diǎn)時(shí)，如果兩個(gè)表中相等的元素時(shí)，摘取La表中的元素，刪除Lb表中的元素；如果其中一個(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)作為L(zhǎng)c的頭結(jié)點(diǎn)while(pa&pb) if(pa-data=pb-data)交集并入結(jié)果表中。 pc-next=pa;pc=pa;pa=pa-next; u=pb;pb=pb-next; delete u; else if(pa-datadata) u=pa;pa=pa-next; delete u;else u=pb; pb=pb-next; delete u;while(pa) u=pa; pa=pa-next; delete u; 釋放結(jié)點(diǎn)空間while(pb) u=pb; pb=pb-next; delete u;釋放結(jié)點(diǎn)空間pc-next=null;置鏈表尾標(biāo)記。delete Lb; /釋放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)開始進(jìn)行比較，當(dāng)兩個(gè)鏈表La和Lb均為到達(dá)表尾結(jié)點(diǎn)時(shí)，如果La表中的元素小于Lb表中的元素，pre置為L(zhǎng)a表的工作指針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為L(zhǎng)a中pa所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)的指針 while（pa&pb）if（pa-datadata）pre=pa;pa=pa-next;*n+; A鏈表中當(dāng)前結(jié)點(diǎn)指針后移else if（pa-dataq-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表中值小于零的結(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)開始，依次取其每個(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=new LNode;為C申請(qǐng)結(jié)點(diǎn)空間 C-next=NULL; C初始化為空表 p=A-next; p為工作指針 while(p!= NULL) r=p-next; 暫存p的后繼 if(p-datanext=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)行比較，直到遍歷完該鏈表。算法描述ElemType 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)開始，逐個(gè)地把鏈表L的當(dāng)前結(jié)點(diǎn)p插入新的鏈表頭部。算法描述void inverse(LinkList &L) / 逆置帶頭結(jié)點(diǎn)的單鏈表 L p=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的結(jié)點(diǎn)，再修改指針，刪除值大于mink且小于maxk的所有元素。算法描述void delete(LinkList &L, int mink, int maxk) p=L-next; /首元結(jié)點(diǎn) while (p & p-datanext; /查找第一個(gè)值mink的結(jié)點(diǎn) if (p) while (p & p-datanext; / 查找第一個(gè)值 maxk的結(jié)點(diǎn) q=pre-next; pre-next=p; / 修改指針 while (q!=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è)域，寫出算法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)）六條鏈。算法描述void Exchange（LinkedList p）p是雙向循環(huán)鏈表中的一個(gè)結(jié)點(diǎn)，本算法將p所指結(jié)點(diǎn)與其前驅(qū)結(jié)點(diǎn)交換。q=p-llink； q-llink-rlink=p； 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的線性表A采用順序存儲(chǔ)結(jié)構(gòu)，請(qǐng)寫一時(shí)間復(fù)雜度為O(n)、空間復(fù)雜度為O(1)的算法，該算法刪除線性表中所有值為item的數(shù)據(jù)元素。題目分析 在順序存儲(chǔ)的線性表上刪除元素，通常要涉及到一系列元素的移動(dòng)（刪第i個(gè)元素，第i+1至第n個(gè)元素要依次前移）。本題要求刪除線性表中所有值為item的數(shù)據(jù)元素，并未要求元素間的相對(duì)位置不變。因此可以考慮設(shè)頭尾兩個(gè)指針（i=1，j=n），從兩端向中間移動(dòng)，凡遇到值item的數(shù)據(jù)元素時(shí)，直接將右端元素左移至值為item的數(shù)據(jù)元素位置。算法描述void Delete（ElemType A ，int n）A是有n個(gè)元素的一維數(shù)組，本算法刪除A中所有值為item的元素。i=1；j=n；設(shè)置數(shù)組低、高端指針（下標(biāo)）。 while（ij） while（ij & Ai!=item）i+； 若值不為item，左移指針。 if（ij）while（ij & Aj=item）j-；若右端元素為item，指針左移 if（idata;top=top-link； Btop=top-link;x=top-link； Cx=top;top=top-link； Dx=top-link；答案：A解釋：x=top-data將結(jié)點(diǎn)的值保存到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ù)為（ ）。An+1 Bn-1 C n D n+2答案：A解釋：特殊值法。設(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解釋：遞歸調(diào)用、函數(shù)調(diào)用、表達(dá)式求值均用到了棧的后進(jìn)先出性質(zhì)。（7）為解決計(jì)算機(jī)主機(jī)與打印機(jī)間速度不匹配問(wèn)題，通常設(shè)一個(gè)打印數(shù)據(jù)緩沖區(qū)。主機(jī)將要輸出的數(shù)據(jù)依次寫入該緩沖區(qū)，而打印機(jī)則依次從該緩沖區(qū)中取出數(shù)據(jù)。該緩沖區(qū)的邏輯結(jié)構(gòu)應(yīng)該是（ ）。A隊(duì)列 B棧 C 線性表 D有序表答案：A解釋：解決緩沖區(qū)問(wèn)題應(yīng)利用一種先進(jìn)先出的線性表，而隊(duì)列正是一種先進(jì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)該是（）。A2 B3 C4 D 6答案：B解釋：元素出隊(duì)的序列是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)棧的正確操作是( )。Atop+; Vtop=x;BVtop=x; top+;Ctop-; Vtop=x;DVtop=x; top-;答案：C解釋：初始棧頂指針top為n+1，說(shuō)明元素從數(shù)組向量的高端地址進(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線性表的順序存儲(chǔ)結(jié)構(gòu) B隊(duì)列 C. 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) D. 棧答案：D解釋：利用棧的后進(jìn)先出原則。（11）用鏈接方式存儲(chǔ)的隊(duì)列，在進(jìn)行刪除運(yùn)算時(shí)（）。A. 僅修改頭指針 B. 僅修改尾指針C. 頭、尾指針都要修改 D. 頭、尾指針可能都要修改答案：D解釋：一般情況下只修改頭指針，但是，當(dāng)刪除的是隊(duì)列中最后一個(gè)元素時(shí)，隊(duì)尾指針也丟失了，因此需對(duì)隊(duì)尾指針重新賦值。（12）循環(huán)隊(duì)列存儲(chǔ)在數(shù)組A0.m中，則入隊(duì)時(shí)的操作為（）。A. rear=rear+1 B. rear=(rear+1)%(m-1) C. rear=(rear+1)%m D. rear=(rear+1)%(m+1) 答案：D解釋：數(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=front B. rear=front Crear+1=front D. (rear-l)%n=front答案：B解釋：最大容量為n的循環(huán)隊(duì)列，隊(duì)滿條件是(rear+1)%n=front，隊(duì)空條件是rear=front。（14）棧和隊(duì)列的共同點(diǎn)是（）。A. 都是先進(jìn)先出 B. 都是先進(jìn)后出 C. 只允許在端點(diǎn)處插入和刪除元素 D. 沒(méi)有共同點(diǎn)答案：C解釋：棧只允許在棧頂處進(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ù)?號(hào)棧的棧頂指針top1等于m時(shí)該棧為空。兩個(gè)棧均從兩端向中間增長(zhǎng)。試編寫雙棧初始化，判斷?？?、棧滿、進(jìn)棧和出棧等算法的函數(shù)。雙棧數(shù)據(jù)結(jié)構(gòu)的定義如下：Typedef structint top2,bot2;/棧頂和棧底指針 SElemType *V;/棧數(shù)組 int m;/棧最大可容納元素個(gè)數(shù)DblStack題目分析兩棧共享向量空間，將兩棧棧底設(shè)在向量?jī)啥?，初始時(shí)，左棧頂指針為-1，右棧頂為m。兩棧頂指針相鄰時(shí)為棧滿。兩棧頂相向、迎面增長(zhǎng)，棧頂指針指向棧頂元素。算法描述(1)棧初始化intInit()S.top0=-1;S.top1=m;return1;/初始化成功(2)入棧操作：intpush(stk S,inti,intx)i為棧號(hào)，i=0表示左棧，i=1為右棧，x是入棧元素。入棧成功返回1，失敗返回0if(i1) cout“棧號(hào)輸入不對(duì)”endl;exit(0);if(S.top1-S.top0=1) cout“棧已滿”endl;return(0);switch(i)case0: S.V+S.top0=x;return(1);break;case1: S.V-S.top1=x;return(1);push(3)退棧操作ElemType pop(stk S,inti)退棧。i代表?xiàng)Ｌ?hào)，i=0時(shí)為左棧，i=1時(shí)為右棧。退棧成功時(shí)返回退棧元素否則返回-1if(i1)cout“棧號(hào)輸入錯(cuò)誤”endl；exit(0);switch(i)case0:if(S.top0=-1) cout“?？铡眅ndl；return（-1）；elsereturn(S.VS.top0-);case1:if(S.top1=m cout“?？铡眅ndl;return(-1);elsereturn(S.VS.top1+);switch 算法結(jié)束(4)判斷棧空intEmpty();return(S.top0=-1 & S.top1=m);算法討論請(qǐng)注意算法中兩棧入棧和退棧時(shí)的棧頂指針的計(jì)算。左棧是通常意義下的棧，而右棧入棧操作時(shí)，其棧頂指針左移（減1），退棧時(shí)，棧頂指針右移（加1）。（2）回文是指正讀反讀均相同的字符序列，如“abba”和“abdba”均是回文，但“good”不是回文。試寫一個(gè)算法判定給定的字符向量是否為回文。(提示：將一半字符入棧)題目分析將字符串前一半入棧，然后，棧中元素和字符串后一半進(jìn)行比較。即將第一個(gè)出棧元素和后一半串中第一個(gè)字符比較，若相等，則再出棧一個(gè)元素與后一個(gè)字符比較，直至棧空，結(jié)論為字符序列是回文。在出棧元素與串中字符比較不等時(shí)，結(jié)論字符序列不是回文。算法描述#define StackSize 100 /假定預(yù)分配的棧空間最多為100個(gè)元素typedef char DataType;/假定棧元素的數(shù)據(jù)類型為字符typedef structDataType dataStackSize;int top;SeqStack;int IsHuiwen( char *t)/判斷t字符向量是否為回文，若是，返回1，否則返回0SeqStack s;int i , len;char temp;InitStack( &s);len=strlen(t); /求向量長(zhǎng)度f(wàn)or ( i=0; ilen/2; i+)/將一半字符入棧Push( &s, ti);while( !EmptyStack( &s)/ 每彈出一個(gè)字符與相應(yīng)字符比較temp=Pop (&s);if( temp!=Si) return 0 ;/ 不等則返回0else i+;return 1 ; / 比較完畢均相等則返回 1（3）設(shè)從鍵盤輸入一整數(shù)的序列：a1, a2, a3，an，試編寫算法實(shí)現(xiàn)：用棧結(jié)構(gòu)存儲(chǔ)輸入的整數(shù)，當(dāng)ai-1時(shí)，將ai進(jìn)棧；當(dāng)ai=-1時(shí)，輸出棧頂整數(shù)并出棧。算法應(yīng)對(duì)異常情況（入棧滿等）給出相應(yīng)的信息。算法描述#define maxsize ?？臻g容量void InOutS(int smaxsize)/s是元素為整數(shù)的棧，本算法進(jìn)行入棧和退棧操作。int top=0; /top為棧頂指針，定義top=0時(shí)為?？?。 for(i=1; ix); /從鍵盤讀入整數(shù)序列。 if(x!=-1) / 讀入的整數(shù)不等于-1時(shí)入棧。 if(top=maxsize-1)cout“棧滿”endl;exit(0);else s+top=x; /x入棧。 else /讀入的整數(shù)等于-1時(shí)退棧。 if(top=0) cout“?？铡眅ndl;exit(0); else cout“出棧元素是” stop-x;/x是字符型變量。while(x!=$) switch case0=x=0&xx;else /處理小數(shù)部分。scale=10.0; cinx;while(x=0&xx; /elsepush(OPND,num); num=0.0;/數(shù)壓入棧，下個(gè)數(shù)初始化 case x= :break; /遇空格，繼續(xù)讀下一個(gè)字符。 case x=+:push(OPND,pop(OPND)+pop(OPND);break; case x=-:x1=pop(OPND);x2=pop(OPND);push(OPND,x2-x1);break; case x=*:push(OPND,pop(OPND)*pop(OPND);break; case x=/:x1=pop(OPND);x2=pop(OPND);push(OPND,x2/x1);break; default: /其它符號(hào)不作處理。 /結(jié)束switch cinx;/讀入表達(dá)式中下一個(gè)字符。 /結(jié)束while（x！=$）cout“后綴表達(dá)式的值為”j)cout“序列非法”ednl；exit(0); i+; /不論Ai是I或O，指針i均后移。 if(j!=k) cout“序列非法”endl；return(false); else cout“序列合法”endl；return(true); /算法結(jié)束。 算法討論在入棧出棧序列（即由I和O組成的字符串）的任一位置，入棧次數(shù)（I