《數(shù)據(jù)結(jié)構(gòu)[C語言版][第2版]課后習(xí)題答案解析》由會員分享，可在線閱讀，更多相關(guān)《數(shù)據(jù)結(jié)構(gòu)[C語言版][第2版]課后習(xí)題答案解析（66頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、. 數(shù)據(jù)結(jié)構(gòu)〔C語言版〔第2版 課后習(xí)題答案 李冬梅 2015.3 目 錄 第1章緒論1 第2章線性表5 第3章棧和隊列13 第4章串、數(shù)組和廣義表26 第5章樹和二叉樹33 第6章圖43 第7章查找54 第8章排序65 65 / 66 . 第1章 緒論 1．簡述下列概念：數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項、數(shù)據(jù)對象、數(shù)據(jù)結(jié)構(gòu)、邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)、抽象數(shù)據(jù)類型。 答案： 數(shù)據(jù)：是客觀事物的符號表示,指所有能輸入到計算機(jī)中并被計算機(jī)程序處理的符號的總稱。如數(shù)學(xué)計算中用到的整數(shù)和實數(shù),文本編輯所用到的字符串,多媒體程序處理的圖形、圖像、聲音、動畫等通過特殊編碼定

2、義后的數(shù)據(jù)。 數(shù)據(jù)元素：是數(shù)據(jù)的基本單位,在計算機(jī)中通常作為一個整體進(jìn)行考慮和處理。在有些情況下,數(shù)據(jù)元素也稱為元素、結(jié)點、記錄等。數(shù)據(jù)元素用于完整地描述一個對象,如一個學(xué)生記錄,樹中棋盤的一個格局〔狀態(tài)、圖中的一個頂點等。 數(shù)據(jù)項：是組成數(shù)據(jù)元素的、有獨立含義的、不可分割的最小單位。例如,學(xué)生基本信息表中的學(xué)號、姓名、性別等都是數(shù)據(jù)項。 數(shù)據(jù)對象：是性質(zhì)相同的數(shù)據(jù)元素的集合,是數(shù)據(jù)的一個子集。例如：整數(shù)數(shù)據(jù)對象是集合N={0,±1,±2,…},字母字符數(shù)據(jù)對象是集合C={‘A’,‘B’,…,‘Z’, ‘a(chǎn)’,‘b’,…,‘z’},學(xué)生基本信息表也可是一個數(shù)據(jù)對象。 數(shù)據(jù)結(jié)構(gòu)：是相互之

3、間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。換句話說,數(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ù)的存儲無關(guān),是獨立于計算機(jī)的。因此,數(shù)據(jù)的邏輯結(jié)構(gòu)可以看作是從具體問題抽象出來的數(shù)學(xué)模型。 存儲結(jié)構(gòu)：數(shù)據(jù)對象在計算機(jī)中的存儲表示,也稱為物理結(jié)構(gòu)。 抽象數(shù)據(jù)類型：由用戶定義的,表示應(yīng)用問題的數(shù)學(xué)模型,以及定義在這個模型上的一組操作的總稱。具體包括三部分：數(shù)據(jù)對象、數(shù)據(jù)對象上關(guān)系的集合和對數(shù)據(jù)對象的基本操作的集合。 2．試舉一個數(shù)據(jù)結(jié)構(gòu)的例子,敘述其邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)兩方面的含義和相互關(guān)系。 答案： 例如有一張學(xué)生

4、基本信息表,包括學(xué)生的學(xué)號、姓名、性別、籍貫、專業(yè)等。每個學(xué)生基本信息記錄對應(yīng)一個數(shù)據(jù)元素,學(xué)生記錄按順序號排列,形成了學(xué)生基本信息記錄的線性序列。對于整個表來說,只有一個開始結(jié)點<它的前面無記錄>和一個終端結(jié)點<它的后面無記錄>,其他的結(jié)點則各有一個也只有一個直接前趨和直接后繼。學(xué)生記錄之間的這種關(guān)系就確定了學(xué)生表的邏輯結(jié)構(gòu),即線性結(jié)構(gòu)。 這些學(xué)生記錄在計算機(jī)中的存儲表示就是存儲結(jié)構(gòu)。如果用連續(xù)的存儲單元<如用數(shù)組表示>來存放這些記錄,則稱為順序存儲結(jié)構(gòu)；如果存儲單元不連續(xù),而是隨機(jī)存放各個記錄,然后用指針進(jìn)行鏈接,則稱為鏈?zhǔn)酱鎯Y(jié)構(gòu)。 即相同的邏輯結(jié)構(gòu),可以對應(yīng)不同的存儲結(jié)構(gòu)。 3．

5、簡述邏輯結(jié)構(gòu)的四種基本關(guān)系并畫出它們的關(guān)系圖。 答案： 〔1集合結(jié)構(gòu) 數(shù)據(jù)元素之間除了"屬于同一集合"的關(guān)系外,別無其他關(guān)系。例如,確定一名學(xué)生是否為班級成員,只需將班級看做一個集合結(jié)構(gòu)。 〔2線性結(jié)構(gòu) 數(shù)據(jù)元素之間存在一對一的關(guān)系。例如,將學(xué)生信息數(shù)據(jù)按照其入學(xué)報到的時間先后順序進(jìn)行排列,將組成一個線性結(jié)構(gòu)。 〔3樹結(jié)構(gòu) 數(shù)據(jù)元素之間存在一對多的關(guān)系。例如,在班級的管理體系中,班長管理多個組長,每位組長管理多名組員,從而構(gòu)成樹形結(jié)構(gòu)。 〔4圖結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu) 數(shù)據(jù)元素之間存在多對多的關(guān)系。例如,多位同學(xué)之間的朋友關(guān)系,任何兩位同學(xué)都可以是朋友,從而構(gòu)成圖形結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)。

6、其中樹結(jié)構(gòu)和圖結(jié)構(gòu)都屬于非線性結(jié)構(gòu)。 四類基本邏輯結(jié)構(gòu)關(guān)系圖 4．存儲結(jié)構(gòu)由哪兩種基本的存儲方法實現(xiàn)？ 答案： 〔1順序存儲結(jié)構(gòu) 順序存儲結(jié)構(gòu)是借助元素在存儲器中的相對位置來表示數(shù)據(jù)元素之間的邏輯關(guān)系,通常借助程序設(shè)計語言的數(shù)組類型來描述。 〔2鏈?zhǔn)酱鎯Y(jié)構(gòu) 順序存儲結(jié)構(gòu)要求所有的元素依次存放在一片連續(xù)的存儲空間中,而鏈?zhǔn)酱鎯Y(jié)構(gòu),無需占用一整塊存儲空間。但為了表示結(jié)點之間的關(guān)系,需要給每個結(jié)點附加指針字段,用于存放后繼元素的存儲地址。所以鏈?zhǔn)酱鎯Y(jié)構(gòu)通常借助于程序設(shè)計語言的指針類型來描述。 5．選擇題 〔1在數(shù)據(jù)結(jié)構(gòu)中,從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成〔 。 A．動

7、態(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)容、相對位置、個數(shù)無關(guān)的是數(shù)據(jù)的〔 。 A．存儲結(jié)構(gòu) B．存儲實現(xiàn) C．邏輯結(jié)構(gòu) D．運算實現(xiàn) 答案：C 〔3通常要求同一邏輯結(jié)構(gòu)中的所有數(shù)據(jù)元素具有相同的特性,這意味著〔 。 A．?dāng)?shù)據(jù)具有同一特點 B．不僅數(shù)據(jù)元素所包含的數(shù)據(jù)項的個數(shù)要相同,而且對應(yīng)數(shù)據(jù)項的類型要一致 C．每個數(shù)據(jù)元素都一樣 D．?dāng)?shù)據(jù)元素所包含的數(shù)據(jù)項的個數(shù)要相等 答案：B 〔4以下說法正

8、確的是〔 。 A．?dāng)?shù)據(jù)元素是數(shù)據(jù)的最小單位 B．?dāng)?shù)據(jù)項是數(shù)據(jù)的基本單位 C．?dāng)?shù)據(jù)結(jié)構(gòu)是帶有結(jié)構(gòu)的各數(shù)據(jù)項的集合 D．一些表面上很不相同的數(shù)據(jù)可以有相同的邏輯結(jié)構(gòu) 答案：D 解釋：數(shù)據(jù)元素是數(shù)據(jù)的基本單位,數(shù)據(jù)項是數(shù)據(jù)的最小單位,數(shù)據(jù)結(jié)構(gòu)是帶有結(jié)構(gòu)的各數(shù)據(jù)元素的集合。 〔5算法的時間復(fù)雜度取決于〔 。 A．問題的規(guī)模 B．待處理數(shù)據(jù)的初態(tài) C．計算機(jī)的配置 D．A和B 答案：D 解釋：算法的時間復(fù)雜度不僅與問題的規(guī)模有關(guān),還與問題的其他因素有關(guān)。如某些排序的算法,其執(zhí)行時間與待排序記錄的初始狀態(tài)有關(guān)。為此,有時會對算法有最好、最壞以及平均時間復(fù)雜度的評價。 〔6

9、以下數(shù)據(jù)結(jié)構(gòu)中,〔是非線性數(shù)據(jù)結(jié)構(gòu) A．樹 B．字符串 C．隊列 D．棧 答案：A 6．試分析下面各程序段的時間復(fù)雜度。 〔1x=90; y=100;? while0> if100> {x=x-10;y--;} else x++; 答案：O<1> 解釋：程序的執(zhí)行次數(shù)為常數(shù)階。 〔2for for a[i][j]=0; 答案：O 解釋：語句a[i][j]=0;的執(zhí)行次數(shù)為m*n。 〔3s=0; for i=0; i

10、 for s+=B[i][j]; sum=s; 答案：O 解釋：語句s+=B[i][j];的執(zhí)行次數(shù)為n2。 〔4i=1; while i=i*3; 答案：O 解釋：語句i=i*3;的執(zhí)行次數(shù)為?log3n?。 〔5x=0; for for x++; 答案：O 解釋：語句x++;的執(zhí)行次數(shù)為n-1+n-2+……＋1= n/2。 〔6x=n; //n>1 y=0; while*

11、 > y++; 答案：O<> 解釋：語句y++;的執(zhí)行次數(shù)為??。 第2章 線性表 1．選擇題 〔1順序表中第一個元素的存儲地址是100,每個元素的長度為2,則第5個元素的地址是〔 。 A．110 B．108 C．100 D．120 答案：B 解釋：順序表中的數(shù)據(jù)連續(xù)存儲,所以第5個元素的地址為：100+2*4=108。 〔2在n個結(jié)點的順序表中,算法的時間復(fù)雜度是O<1>的操作是〔 。 A．訪問第i個結(jié)點〔1≤i≤n和求第i個結(jié)點的直接前驅(qū)〔2≤i≤n B．在第i個結(jié)點后插入一個新結(jié)點〔1≤i≤n

12、C．刪除第i個結(jié)點〔1≤i≤n D．將n個結(jié)點從小到大排序 答案：A 解釋：在順序表中插入一個結(jié)點的時間復(fù)雜度都是O,排序的時間復(fù)雜度為O或O。順序表是一種隨機(jī)存取結(jié)構(gòu),訪問第i個結(jié)點和求第i個結(jié)點的直接前驅(qū)都可以直接通過數(shù)組的下標(biāo)直接定位,時間復(fù)雜度是O<1>。 〔3向一個有127個元素的順序表中插入一個新元素并保持原來順序不變,平均要移動的元素個數(shù)為〔 。 A．8 B．63.5 C．63 D．7 答案：B 解釋：平均要移動的元素個數(shù)為：n/2。 〔4鏈接存儲的存儲結(jié)構(gòu)所占存儲空間〔 。 A．分兩部分,一部分存放結(jié)點值,另一

13、部分存放表示結(jié)點間關(guān)系的指針 B．只有一部分,存放結(jié)點值 C．只有一部分,存儲表示結(jié)點間關(guān)系的指針 D．分兩部分,一部分存放結(jié)點值,另一部分存放結(jié)點所占單元數(shù) 答案：A 〔5線性表若采用鏈?zhǔn)酱鎯Y(jié)構(gòu)時,要求內(nèi)存中可用存儲單元的地址〔 。 A．必須是連續(xù)的 B．部分地址必須是連續(xù)的 C．一定是不連續(xù)的 D．連續(xù)或不連續(xù)都可以 答案：D 〔6線性表Ｌ在〔 情況下適用于使用鏈?zhǔn)浇Y(jié)構(gòu)實現(xiàn)。 A．需經(jīng)常修改Ｌ中的結(jié)點值 Ｂ．需不斷對Ｌ進(jìn)行刪除插入 C．Ｌ中含有大量的結(jié)點 Ｄ．Ｌ中結(jié)點結(jié)構(gòu)復(fù)雜 答案：B 解釋：鏈表最大

14、的優(yōu)點在于插入和刪除時不需要移動數(shù)據(jù),直接修改指針即可。 〔7單鏈表的存儲密度〔 。 A．大于1 B．等于1 C．小于1 D．不能確定 答案：C 解釋：存儲密度是指一個結(jié)點數(shù)據(jù)本身所占的存儲空間和整個結(jié)點所占的存儲空間之比,假設(shè)單鏈表一個結(jié)點本身所占的空間為D,指針域所占的空間為N,則存儲密度為：D/,一定小于1。 〔8將兩個各有n個元素的有序表歸并成一個有序表,其最少的比較次數(shù)是〔 。 A．n B．2n-1 C．2n D．n-1 答案：A 解釋：當(dāng)?shù)谝粋€有序表中所有的元素都小于〔或大于第二個表中的元素,只需要用

15、第二個表中的第一個元素依次與第一個表的元素比較,總計比較n次。 〔9在一個長度為n的順序表中,在第i個元素〔1≤i≤n+1之前插入一個新元素時須向后移動〔 個元素。 A．n-i B．n-i+1 C．n-i-1 D．I 答案：B <10> 線性表L=,下列說法正確的是〔 。 A．每個元素都有一個直接前驅(qū)和一個直接后繼 B．線性表中至少有一個元素 C．表中諸元素的排列必須是由小到大或由大到小 D．除第一個和最后一個元素外,其余每個元素都有一個且僅有一個直接前驅(qū)和直接后繼。 答案：D <11> 創(chuàng)建一個包括n個結(jié)點的有序單鏈表的時間復(fù)雜度是〔

16、 。 A．O<1> B．O C．O D．O 答案：C 解釋：單鏈表創(chuàng)建的時間復(fù)雜度是O,而要建立一個有序的單鏈表,則每生成一個新結(jié)點時需要和已有的結(jié)點進(jìn)行比較,確定合適的插入位置,所以時間復(fù)雜度是O。 <12> 以下說法錯誤的是〔 。 A．求表長、定位這兩種運算在采用順序存儲結(jié)構(gòu)時實現(xiàn)的效率不比采用鏈?zhǔn)酱鎯Y(jié)構(gòu)時實現(xiàn)的效率低 B．順序存儲的線性表可以隨機(jī)存取 C．由于順序存儲要求連續(xù)的存儲區(qū)域,所以在存儲管理上不夠靈活 D．線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)優(yōu)于順序存儲結(jié)構(gòu) 答案：D 解釋：鏈?zhǔn)酱鎯Y(jié)構(gòu)和順序存儲結(jié)構(gòu)各有優(yōu)缺點,有

17、不同的適用場合。 <13> 在單鏈表中,要將s所指結(jié)點插入到p所指結(jié)點之后,其語句應(yīng)為〔 。 A．s->next=p+1;p->next=s; B．<*p>.next=s;<*s>.next=<*p>.next; C．s->next=p->next;p->next=s->next; D．s->next=p->next;p->next=s; 答案：D <14> 在雙向鏈表存儲結(jié)構(gòu)中,刪除p所指的結(jié)點時須修改指針〔 。 A．p->next->prior=p->prior;p->prior->next=p->next; B．p->next=p->next->next;

18、p->next->prior=p; C．p->prior->next=p;p->prior=p->prior->prior; D．p->prior=p->next->next;p->next=p->prior->prior; 答案：A <15> 在雙向循環(huán)鏈表中,在p指針?biāo)傅慕Y(jié)點后插入q所指向的新結(jié)點,其修改指針的操作是〔 。 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->

19、next=p->next;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è)計題 〔1將兩個遞增的有序鏈表合并為一個遞增的有序鏈表。要求結(jié)果鏈表仍使用原來兩個鏈表的存儲空間, 不另外占用其它的存儲空間。表中不允許有重復(fù)的數(shù)據(jù)。 [題目分析] 合并后的新表使用頭指針Lc指向,pa和pb分別是鏈表La和Lb的工作指針,初始化為相應(yīng)鏈表的第一個結(jié)點,從第一個結(jié)點開始進(jìn)行比較,當(dāng)兩個鏈表La和Lb均為到達(dá)表尾結(jié)點時,依次摘取其中較小者重新鏈接在Lc表的

20、最后。如果兩個表中的元素相等,只摘取La表中的元素,刪除Lb表中的元素,這樣確保合并后表中無重復(fù)的元素。當(dāng)一個表到達(dá)表尾結(jié)點,為空時,將非空表的剩余元素直接鏈接在Lc表的最后。 [算法描述] void MergeList {//合并鏈表La和Lb,合并后的新表使用頭指針Lc指向 pa=La->next; pb=Lb->next; //pa和pb分別是鏈表La和Lb的工作指針,初始化為相應(yīng)鏈表的第一個結(jié)點 Lc=pc=La; //用La的頭結(jié)點作為Lc的頭結(jié)點 while

21、& pb> {ifdatadata>{pc->next=pa;pc=pa;pa=pa->next;} //取較小者La中的元素,將pa鏈接在pc的后面,pa指針后移 else ifdata>pb->data> {pc->next=pb; pc=pb; pb=pb->next;} //取較小者Lb中的元素,將pb鏈接在pc的后面,pb指針后移 else //相等時取La中的元素,刪除Lb中的元素 {pc->next=pa;pc=pa;pa=pa->next; q=pb->next;delete pb ;pb

22、=q; } } pc->next=pa?pa:pb; //插入剩余段 delete Lb; //釋放Lb的頭結(jié)點 } 〔2將兩個非遞減的有序鏈表合并為一個非遞增的有序鏈表。要求結(jié)果鏈表仍使用原來兩個鏈表的存儲空間, 不另外占用其它的存儲空間。表中允許有重復(fù)的數(shù)據(jù)。 [題目分析] 合并后的新表使用頭指針Lc指向,pa和pb分別是鏈表La和Lb的工作指針,初始化為相應(yīng)鏈表的第一個結(jié)點,從第一個結(jié)點開始進(jìn)行比較,當(dāng)兩個鏈表La和Lb均為到達(dá)表尾結(jié)點時,依次摘取其中較小者重新鏈接在Lc表的表頭結(jié)點之后,如果兩個表中的元素相等,只摘取La表中的元素,保留

23、Lb表中的元素。當(dāng)一個表到達(dá)表尾結(jié)點,為空時,將非空表的剩余元素依次摘取,鏈接在Lc表的表頭結(jié)點之后。 [算法描述] void MergeList {//合并鏈表La和Lb,合并后的新表使用頭指針Lc指向 pa=La->next; pb=Lb->next; //pa和pb分別是鏈表La和Lb的工作指針,初始化為相應(yīng)鏈表的第一個結(jié)點 Lc=pc=La; //用La的頭結(jié)點作為Lc的頭結(jié)點 Lc->next=NULL; while {//只要存在一個非

24、空表,用q指向待摘取的元素 if {q=pb; pb=pb->next;} //La表為空,用q指向pb,pb指針后移 else if {q=pa; pa=pa->next;} //Lb表為空,用q指向pa,pa指針后移 else ifdata<=pb->data> {q=pa; pa=pa->next;} //取較小者〔包括相等La中的元素,用q指向pa,pa指針后移 else {q=pb; pb=pb->next;} //取較小者Lb中的元素,用q指向pb,pb指針后移 q->next = L

25、c->next; Lc->next = q; //將q指向的結(jié)點插在Lc 表的表頭結(jié)點之后 } delete Lb; //釋放Lb的頭結(jié)點 } 〔3已知兩個鏈表A和B分別表示兩個集合,其元素遞增排列。請設(shè)計算法求出A與B的交集,并存放于A鏈表中。 [題目分析] 只有同時出現(xiàn)在兩集合中的元素才出現(xiàn)在結(jié)果表中,合并后的新表使用頭指針Lc指向。pa和pb分別是鏈表La和Lb的工作指針,初始化為相應(yīng)鏈表的第一個結(jié)點,從第一個結(jié)點開始進(jìn)行比較,當(dāng)兩個鏈表La和Lb均為到達(dá)表尾結(jié)點時,如果兩個表中相等的元素時,摘取La表中的元素,刪除Lb表中的元素；如果

26、其中一個表中的元素較小時,刪除此表中較小的元素,此表的工作指針后移。當(dāng)鏈表La和Lb有一個到達(dá)表尾結(jié)點,為空時,依次刪除另一個非空表中的所有元素。 [算法描述] void Mix {pa=La->next;pb=Lb->next; pa和pb分別是鏈表La和Lb的工作指針,初始化為相應(yīng)鏈表的第一個結(jié)點 Lc=pc=La; //用La的頭結(jié)點作為Lc的頭結(jié)點 while { ifdata==pb->data>∥交集并入結(jié)果表中。 { pc->next=pa;pc=

27、pa;pa=pa->next; u=pb;pb=pb->next; delete u;} else ifdatadata> {u=pa;pa=pa->next; delete u;} else {u=pb; pb=pb->next; delete u;} } while{u=pa; pa=pa->next; delete u;}∥ 釋放結(jié)點空間 while {u=pb; pb=pb->next; delete u;}∥釋放結(jié)點空間 pc->next=null;∥置鏈表尾標(biāo)記。 delete Lb; //釋放Lb的頭結(jié)點 } 〔4已

28、知兩個鏈表A和B分別表示兩個集合,其元素遞增排列。請設(shè)計算法求出兩個集合A和B 的差集〔即僅由在A中出現(xiàn)而不在B中出現(xiàn)的元素所構(gòu)成的集合,并以同樣的形式存儲,同時返回該集合的元素個數(shù)。 [題目分析] 求兩個集合A和B的差集是指在A中刪除A和B中共有的元素,即刪除鏈表中的相應(yīng)結(jié)點,所以要保存待刪除結(jié)點的前驅(qū),使用指針pre指向前驅(qū)結(jié)點。pa和pb分別是鏈表La和Lb的工作指針,初始化為相應(yīng)鏈表的第一個結(jié)點,從第一個結(jié)點開始進(jìn)行比較,當(dāng)兩個鏈表La和Lb均為到達(dá)表尾結(jié)點時,如果La表中的元素小于Lb表中的元素,pre置為La表的工作指針pa刪除Lb表中的元素；如果其中一個表中的元素較小時,刪除

29、此表中較小的元素,此表的工作指針后移。當(dāng)鏈表La和Lb有一個為空時,依次刪除另一個非空表中的所有元素。 [算法描述] void Difference〔LinkList& La, LinkList& Lb,int *n {∥差集的結(jié)果存儲于單鏈表La中,*n是結(jié)果集合中元素個數(shù),調(diào)用時為0 pa=La->next; pb=Lb->next; ∥pa和pb分別是鏈表La和Lb的工作指針,初始化為相應(yīng)鏈表的第一個結(jié)點 pre=La;∥pre為La中pa所指結(jié)點的前驅(qū)結(jié)點的指針 while〔pa&&pb {if〔pa->datadata{pre=pa;pa=pa->next

30、;*n++;} ∥ A鏈表中當(dāng)前結(jié)點指針后移 else if〔pa->data>q->dataq=q->next;∥B鏈表中當(dāng)前結(jié)點指針后移 else {pre->next=pa->next;∥處理A,B中元素值相同的結(jié)點,應(yīng)刪除 u=pa; pa=pa->next;delete u;} ∥刪除結(jié)點 } } 〔5設(shè)計算法將一個帶頭結(jié)點的單鏈表A分解為兩個具有相同結(jié)構(gòu)的鏈表B、C,其中B表的結(jié)點為A表中值小于零的結(jié)點,而C表的結(jié)點為A表中值大于零的結(jié)點〔鏈表A中的元素為非零整數(shù),要求B、C表利用A表的結(jié)點。 [題目分析] B表的頭結(jié)點使用原來A表的頭

31、結(jié)點,為C表新申請一個頭結(jié)點。從A表的第一個結(jié)點開始,依次取其每個結(jié)點p,判斷結(jié)點p的值是否小于0,利用前插法,將小于0的結(jié)點插入B表,大于等于0的結(jié)點插入C表。 [算法描述] void DisCompose { B=A; B->next= NULL;∥B表初始化 C=new LNode;∥為C申請結(jié)點空間 C->next=NULL;∥C初始化為空表 p=A->next; ∥p為工作指針 while {r=p->next; ∥暫存p的后繼 ifdata<0

32、> {p->next=B->next; B->next=p; }∥將小于0的結(jié)點鏈入B表,前插法 else {p->next=C->next; C->next=p; }∥將大于等于0的結(jié)點鏈入C表,前插法 p=r;∥p指向新的待處理結(jié)點。 } } 〔6設(shè)計一個算法,通過一趟遍歷在單鏈表中確定值最大的結(jié)點。 [題目分析] 假定第一個結(jié)點中數(shù)據(jù)具有最大值,依次與下一個元素比較,若其小于下一個元素,則設(shè)其下一個元素為最大值,反復(fù)進(jìn)行比較,直到遍歷完該鏈表。 [算法描述] ElemType Max { if

33、next==NULL> return NULL; pmax=L->next; //假定第一個結(jié)點中數(shù)據(jù)具有最大值 p=L->next->next; while

{//如果下一個結(jié)點存在 ifdata > pmax->data> pmax=p;//如果p的值大于pmax的值,則重新賦值 p=p->next;//遍歷鏈表 } return pmax->data; 〔7設(shè)計一個算法,通過遍歷一趟,將鏈表中所有結(jié)點的鏈接方向逆轉(zhuǎn),仍利用原表的存儲空間。 [題目分析] 從首元結(jié)點開始,逐個地把鏈表L的當(dāng)前結(jié)點p插入新的鏈表頭部。 [算

34、法描述] void inverse {// 逆置帶頭結(jié)點的單鏈表 L p=L->next; L->next=NULL; while < p> { q=p->next; // q指向*p的后繼 p->next=L->next; L->next=p; // *p插入在頭結(jié)點之后 p = q; } } 〔8設(shè)計一個算法,刪除遞增有序鏈表中值大于mink且小于maxk的所有元素〔mink和maxk是給定的兩個參數(shù),其值可以和表中的元素相同,也可

35、以不同 。 [題目分析] 分別查找第一個值>mink的結(jié)點和第一個值 ≥maxk的結(jié)點,再修改指針,刪除值大于mink且小于maxk的所有元素。 [算法描述] void delete { p=L->next; //首元結(jié)點 while

data<=mink> { pre=p; p=p->next; } //查找第一個值>mink的結(jié)點 if

{while

data p=p->next;

36、 // 查找第一個值 ≥maxk的結(jié)點 q=pre->next; pre->next=p; // 修改指針 while { s=q->next; delete q; q=s; } // 釋放結(jié)點空間 }//if } 〔9已知p指向雙向循環(huán)鏈表中的一個結(jié)點,其結(jié)點結(jié)構(gòu)為data、prior、next三個域,寫出算法change

,交換p所指向的結(jié)點和它的前綴結(jié)點的順序。 [題目分析] 知道雙向循環(huán)鏈表中的一個結(jié)點,與前驅(qū)交換涉及到四個結(jié)點〔p結(jié)點,前驅(qū)結(jié)點,前驅(qū)的前驅(qū)結(jié)點,后繼結(jié)點六條鏈。

37、[算法描述] void Exchange〔LinkedList p ∥p是雙向循環(huán)鏈表中的一個結(jié)點,本算法將p所指結(jié)點與其前驅(qū)結(jié)點交換。 {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的后繼指向其原來的前驅(qū) }∥算法exchange結(jié)束。 〔10已知長度

38、為n的線性表A采用順序存儲結(jié)構(gòu),請寫一時間復(fù)雜度為O、空間復(fù)雜度為O<1>的算法,該算法刪除線性表中所有值為item的數(shù)據(jù)元素。 [題目分析] 在順序存儲的線性表上刪除元素,通常要涉及到一系列元素的移動〔刪第i個元素,第i+1至第n個元素要依次前移。本題要求刪除線性表中所有值為item的數(shù)據(jù)元素,并未要求元素間的相對位置不變。因此可以考慮設(shè)頭尾兩個指針〔i=1,j=n,從兩端向中間移動,凡遇到值item的數(shù)據(jù)元素時,直接將右端元素左移至值為item的數(shù)據(jù)元素位置。 [算法描述] void Delete〔ElemType A[ ],int n ∥A是有n個元素的一維數(shù)組,本

39、算法刪除A中所有值為item的元素。 {i=1；j=n；∥設(shè)置數(shù)組低、高端指針〔下標(biāo)。 while〔i

40、案：C 解釋：棧是后進(jìn)先出的線性表,不難發(fā)現(xiàn)C選項中元素1比元素2先出棧,違背了棧的后進(jìn)先出原則,所以不可能出現(xiàn)C選項所示的情況。 〔2若已知一個棧的入棧序列是1,2,3,…,n,其輸出序列為p1,p2,p3,…,pn,若p1=n,則pi為〔 。 A．i B．n-i C．n-i+1 D．不確定 答案：C 解釋：棧是后進(jìn)先出的線性表,一個棧的入棧序列是1,2,3,…,n,而輸出序列的第一個元素為n,說明1,2,3,…,n一次性全部進(jìn)棧,再進(jìn)行輸出,所以p1=n,p2=n-1,…,pi=n-i+1。 〔3數(shù)組Ｑ［ｎ］用來表示一個循環(huán)隊

41、列,ｆ為當(dāng)前隊列頭元素的前一位置,ｒ為隊尾元素的位置,假定隊列中元素的個數(shù)小于ｎ,計算隊列中元素個數(shù)的公式為〔 。 A．r-f B．%n C．n+r-fD．〔n+r-f>%n 答案：D 解釋：對于非循環(huán)隊列,尾指針和頭指針的差值便是隊列的長度,而對于循環(huán)隊列,差值可能為負(fù)數(shù),所以需要將差值加上MAXSIZE〔本題為n,然后與MAXSIZE〔本題為n求余,即〔n+r-f>%n。 〔4鏈?zhǔn)綏＝Y(jié)點為：,top指向棧頂.若想摘除棧頂結(jié)點,并將刪除結(jié)點的值保存到x中,則應(yīng)執(zhí)行操作〔。 A．x=top->data;top=

42、top->link；B．top=top->link;x=top->link； C．x=top;top=top->link； D．x=top->link； 答案：A 解釋：x=top->data將結(jié)點的值保存到x中,top=top->link棧頂指針指向棧頂下一結(jié)點,即摘除棧頂結(jié)點。 〔5設(shè)有一個遞歸算法如下 int fact { //n大于等于0 if return 1; else return n*fact; } 則計算fact需要調(diào)用該函數(shù)的次數(shù)為〔。 A．n+1B．n-1C． nD． n+2 答案：

43、A 解釋：特殊值法。設(shè)n=0,易知僅調(diào)用一次fact函數(shù),故選A。 〔6棧在〔中有所應(yīng)用。 A．遞歸調(diào)用B．函數(shù)調(diào)用C．表達(dá)式求值D．前三個選項都有 答案：D 解釋：遞歸調(diào)用、函數(shù)調(diào)用、表達(dá)式求值均用到了棧的后進(jìn)先出性質(zhì)。 〔7為解決計算機(jī)主機(jī)與打印機(jī)間速度不匹配問題,通常設(shè)一個打印數(shù)據(jù)緩沖區(qū)。主機(jī)將要輸出的數(shù)據(jù)依次寫入該緩沖區(qū),而打印機(jī)則依次從該緩沖區(qū)中取出數(shù)據(jù)。該緩沖區(qū)的邏輯結(jié)構(gòu)應(yīng)該是〔。 A．隊列 B．棧 C． 線性表 D．有序表 答案：A 解釋：解決緩沖區(qū)問題應(yīng)利用一種先進(jìn)先出的線性表,而隊列正是一種先進(jìn)先出的線性表。

44、 〔8設(shè)棧S和隊列Q的初始狀態(tài)為空,元素e1、e2、e3、e4、e5和e6依次進(jìn)入棧S,一個元素出棧后即進(jìn)入Q,若6個元素出隊的序列是e2、e4、e3、e6、e5和e1,則棧S的容量至少應(yīng)該是〔　。 A．2 B．3 C．4 D． 6 答案：B 解釋：元素出隊的序列是e2、e4、e3、e6、e5和e1,可知元素入隊的序列是e2、e4、e3、e6、e5和e1,即元素出棧的序列也是e2、e4、e3、e6、e5和e1,而元素e1、e2、e3、e4、e5和e6依次進(jìn)入棧,易知棧S中最多同時存在3個元素,故棧S的容量至少為3。 〔9若一個棧

45、以向量V[1..n]存儲,初始棧頂指針top設(shè)為n+1,則元素x進(jìn)棧的正確操作是< >。 A．top++; V[top]=x; B．V[top]=x; top++; C．top--; V[top]=x; D．V[top]=x; top--; 答案：C 解釋：初始棧頂指針top為n+1,說明元素從數(shù)組向量的高端地址進(jìn)棧,又因為元素存儲在向量空間V[1..n]中,所以進(jìn)棧時top指針先下移變?yōu)閚,之后將元素x存儲在V[n]。 〔10設(shè)計一個判別表達(dá)式中左,右括號是否配對出現(xiàn)的算法,采用〔　數(shù)據(jù)結(jié)構(gòu)最佳。 A．線性表的順序存儲結(jié)構(gòu)B．隊列 C. 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)D. 棧 答

46、案：D 解釋：利用棧的后進(jìn)先出原則。 〔11用鏈接方式存儲的隊列,在進(jìn)行刪除運算時〔　。 A. 僅修改頭指針 B. 僅修改尾指針 C. 頭、尾指針都要修改 D. 頭、尾指針可能都要修改 答案：D 解釋：一般情況下只修改頭指針,但是,當(dāng)刪除的是隊列中最后一個元素時,隊尾指針也丟失了,因此需對隊尾指針重新賦值。 〔12循環(huán)隊列存儲在數(shù)組A[0..m]中,則入隊時的操作為〔　。 A. rear=rear+1 B. rear=% C. rear=%mD. rear=

47、ear+1>% 答案：D 解釋：數(shù)組A[0..m]中共含有m+1個元素,故在求模運算時應(yīng)除以m+1。 〔13最大容量為n的循環(huán)隊列,隊尾指針是rear,隊頭是front,則隊空的條件是〔　。 A. %n==front B. rear==front C．rear+1==front D. %n==front 答案：B 解釋：最大容量為n的循環(huán)隊列,隊滿條件是%n==front,隊空條件是rear==front。 〔14棧和隊列的共同點是〔　。 A. 都是先進(jìn)先出

48、 B. 都是先進(jìn)后出 C. 只允許在端點處插入和刪除元素 D. 沒有共同點 答案：C 解釋：棧只允許在棧頂處進(jìn)行插入和刪除元素,隊列只允許在隊尾插入元素和在隊頭刪除元素。 〔15一個遞歸算法必須包括〔　。 A. 遞歸部分B. 終止條件和遞歸部分 C. 迭代部分 D. 終止條件和迭代部分 答案：B 2．算法設(shè)計題 〔1將編號為0和1的兩個棧存放于一個數(shù)組空間V[m]中,棧底分別處于數(shù)組的兩端。當(dāng)?shù)?號棧的棧頂指針top[0]等于-1時該棧為空,當(dāng)?shù)?號棧的棧頂指針top[1]等于m時該棧為空。兩個棧均從兩端向中間增長。試編寫

49、雙棧初始化,判斷?？?、棧滿、進(jìn)棧和出棧等算法的函數(shù)。雙棧數(shù)據(jù)結(jié)構(gòu)的定義如下： Typedef struct {int top[2],bot[2]; //棧頂和棧底指針 SElemType *V; //棧數(shù)組 int m; //棧最大可容納元素個數(shù) }DblStack [題目分析] 兩棧共享向量空間,將兩棧棧底設(shè)在向量兩端,初始時,左棧頂指針為-1,右棧頂為m。兩棧頂指針相鄰時為棧滿。兩棧頂相向、迎面增長,棧頂指針指向棧頂元素。 [算法描述] <1>?棧初始化 int?Init<> ?{S.top[0]=-1; ??S.top[1]=m; ??ret

50、urn?1;?//初始化成功 } <2>?入棧操作： int?push ∥i為棧號,i=0表示左棧,i=1為右棧,x是入棧元素。入棧成功返回1,失敗返回0 {if1>{cout<<"棧號輸入不對"<;} if {cout<<"棧已滿"<;} switch ?{case?0: S.V[++S.top[0]]=x;?return<1>;?break; case?1: S.V[--S.top[1]]=x;?return<1

51、>; } }∥push <3>?退棧操作 ElemType pop ∥退棧。i代表棧號,i=0時為左棧,i=1時為右棧。退棧成功時返回退棧元素 ∥否則返回-1 {if1>{cout<<"棧號輸入錯誤"<;} ?switch {case?0:?if {cout<<"?？?<; case?1:?if

52、;} else?return; ???}∥switch????? }∥算法結(jié)束 <4>?判斷?？? int?Empty<>; {return?; } [算法討論]? 請注意算法中兩棧入棧和退棧時的棧頂指針的計算。左棧是通常意義下的棧,而右棧入棧操作時,其棧頂指針左移〔減1,退棧時,棧頂指針右移〔加1。 〔2回文是指正讀反讀均相同的字符序列,如"abba"和"abdba"均是回文,但"good"不是回文。試寫一個算法判定給定的字符向量是否為回文。<提示：將一半字符入棧>? [題目分析

53、] 將字符串前一半入棧,然后,棧中元素和字符串后一半進(jìn)行比較。即將第一個出棧元素和后一半串中第一個字符比較,若相等,則再出棧一個元素與后一個字符比較,……,直至棧空,結(jié)論為字符序列是回文。在出棧元素與串中字符比較不等時,結(jié)論字符序列不是回文。 [算法描述] #define StackSize 100 //假定預(yù)分配的?？臻g最多為100個元素 typedef char DataType;//假定棧元素的數(shù)據(jù)類型為字符 typedef struct {DataType data[StackSize]; int top; }SeqStack; int IsHuiwen< char

54、*t> {//判斷t字符向量是否為回文,若是,返回1,否則返回0 SeqStack s; int i , len; char temp; InitStack< &s>; len=strlen; //求向量長度 for < i=0; i//將一半字符入棧 Push< &s, t[i]>; while< !EmptyStack< &s>> {// 每彈出一個字符與相應(yīng)字符比較 temp=Pop <&s>; if< temp!=S[i]>? return 0 ;// 不等則返回0 else i++; }? return 1 ; // 比較完

55、畢均相等則返回 1 } 〔3設(shè)從鍵盤輸入一整數(shù)的序列：a1, a2, a3,…,an,試編寫算法實現(xiàn)：用棧結(jié)構(gòu)存儲輸入的整數(shù),當(dāng)ai≠-1時,將ai進(jìn)棧；當(dāng)ai=-1時,輸出棧頂整數(shù)并出棧。算法應(yīng)對異常情況〔入棧滿等給出相應(yīng)的信息。 [算法描述] #define maxsize ?？臻g容量 void InOutS //s是元素為整數(shù)的棧,本算法進(jìn)行入棧和退棧操作。 {int top=0; //top為棧頂指針,定義top=0時為?？?。 for //n個整數(shù)序列作處理。 {cin>>x

56、>; //從鍵盤讀入整數(shù)序列。 if // 讀入的整數(shù)不等于-1時入棧。 ｛if{cout<<"棧滿"<;} else s[++top]=x; //x入棧。 ｝ else //讀入的整數(shù)等于-1時退棧。 {if{cout<<"?？?<;} else cout<<"出棧元素是"<

57、符作為輸入結(jié)束,操作數(shù)之間用空格分隔,操作符只可能有+、-、*、/四種運算。例如：234 34+2*$。 [題目分析] 逆波蘭表達(dá)式<即后綴表達(dá)式>求值規(guī)則如下：設(shè)立運算數(shù)棧OPND,對表達(dá)式從左到右掃描<讀入>,當(dāng)表達(dá)式中掃描到數(shù)時,壓入OPND棧。當(dāng)掃描到運算符時,從OPND退出兩個數(shù),進(jìn)行相應(yīng)運算,結(jié)果再壓入OPND棧。這個過程一直進(jìn)行到讀出表達(dá)式結(jié)束符$,這時OPND棧中只有一個數(shù),就是結(jié)果。 [算法描述] float expr< > //從鍵盤輸入逆波蘭表達(dá)式,以‘$’表示輸入結(jié)束,本算法求逆波蘭式表達(dá)式的值。 ｛float OPND[30]; // OPND是操作數(shù)

58、棧。 init; //兩棧初始化。 float num=0.0; //數(shù)字初始化。 cin>>x;//x是字符型變量。 while {switch {case‘0’<=x<=’9’: while<=’0’&&x<=’9’>||x==’.’> //拼數(shù) if //處理整數(shù) {num=num*10+〔ord-ord<‘0’>; cin>>x;} else //處理小數(shù)部分。 {scale=10.0; cin>>x; while=’0’&&x<=’9’> {

59、num=num+-ord<‘0’>/scale; scale=scale*10; cin>>x; } }//else push; num=0.0;//數(shù)壓入棧,下個數(shù)初始化 case x=‘ ’:break; //遇空格,繼續(xù)讀下一個字符。 case x=‘+’:push+pop>;break; case x=‘-’:x1=pop;x2=pop;push;break; case x=‘*’:push

60、*pop>;break; case x=‘/’:x1=pop;x2=pop;push;break; default: //其它符號不作處理。 }//結(jié)束switch cin>>x;//讀入表達(dá)式中下一個字符。 }//結(jié)束while〔x！=‘$’ cout<<"后綴表達(dá)式的值為"<; }//算法結(jié)束。 [算法討論]假設(shè)輸入的后綴表達(dá)式是正確的,未作錯誤檢查。算法中拼數(shù)部分是核心。若遇到大于等于‘0’且小于等于‘9’的

61、字符,認(rèn)為是數(shù)。這種字符的序號減去字符‘0’的序號得出數(shù)。對于整數(shù),每讀入一個數(shù)字字符,前面得到的部分?jǐn)?shù)要乘上10再加新讀入的數(shù)得到新的部分?jǐn)?shù)。當(dāng)讀到小數(shù)點,認(rèn)為數(shù)的整數(shù)部分已完,要接著處理小數(shù)部分。小數(shù)部分的數(shù)要除以10〔或10的冪數(shù)變成十分位,百分位,千分位數(shù)等等,與前面部分?jǐn)?shù)相加。在拼數(shù)過程中,若遇非數(shù)字字符,表示數(shù)已拼完,將數(shù)壓入棧中,并且將變量num恢復(fù)為0,準(zhǔn)備下一個數(shù)。這時對新讀入的字符進(jìn)入‘+’、‘-’、‘*’、‘/’及空格的判斷,因此在結(jié)束處理數(shù)字字符的case后,不能加入break語句。 〔5假設(shè)以I和O分別表示入棧和出棧操作。棧的初態(tài)和終態(tài)均為空,入棧和出棧的操作序列可

62、表示為僅由I和O組成的序列,稱可以操作的序列為合法序列,否則稱為非法序列。 ①下面所示的序列中哪些是合法的？ A. IOIIOIOO B. IOOIOIIO C. IIIOIOIO D. IIIOOIOO ②通過對①的分析,寫出一個算法,判定所給的操作序列是否合法。若合法,返回true,否則返回false〔假定被判定的操作序列已存入一維數(shù)組中。 答案： ①A和D是合法序列,B和C 是非法序列。 ②設(shè)被判定的操作序列已存入一維數(shù)組A中。 int Judge //判斷字符數(shù)組A中的輸入輸出序列是否是合法序列。如是,

63、返回true,否則返回false。 {i=0; //i為下標(biāo)。 j=k=0; //j和k分別為I和字母O的的個數(shù)。 while //當(dāng)未到字符數(shù)組尾就作。 {switch {case‘I’: j++; break; //入棧次數(shù)增1。 case‘O’: k++; ifj>{cout<<"序列非法"<;}

64、} i++; //不論A[i]是‘I’或‘O’,指針i均后移。} if {cout<<"序列非法"<;} else {cout<<"序列合法"<;} }//算法結(jié)束。 [算法討論]在入棧出棧序列〔即由‘I’和‘O’組成的字符串的任一位置,入棧次數(shù)〔‘I’的個數(shù)都必須大于等于出棧次數(shù)〔即‘O’的個數(shù),否則視作非法序列,立即給出信息,退出算法。整個序列〔即讀到字符數(shù)組中字符串的結(jié)束標(biāo)記‘\0’,入棧次數(shù)必須等于出棧次數(shù)〔題目中要求棧的初態(tài)和終

65、態(tài)都為空,否則視為非法序列。 <6假設(shè)以帶頭結(jié)點的循環(huán)鏈表表示隊列,并且只設(shè)一個指針指向隊尾元素站點<注意不設(shè)頭指針> ,試編寫相應(yīng)的置空隊、判隊空 、入隊和出隊等算法。 [題目分析] 置空隊就是建立一個頭節(jié)點,并把頭尾指針都指向頭節(jié)點,頭節(jié)點是不存放數(shù)據(jù)的；判隊空就是當(dāng)頭指針等于尾指針時,隊空；入隊時,將新的節(jié)點插入到鏈隊列的尾部,同時將尾指針指向這個節(jié)點；出隊時,刪除的是隊頭節(jié)點,要注意隊列的長度大于1還是等于1的情況,這個時候要注意尾指針的修改,如果等于1,則要刪除尾指針指向的節(jié)點。 [算法描述] //先定義鏈隊結(jié)構(gòu): typedef struct queuenode {D

66、atatype data; struct queuenode *next; }QueueNode; //以上是結(jié)點類型的定義 typedef struct {queuenode *rear; }LinkQueue; //只設(shè)一個指向隊尾元素的指針 (1) 置空隊 void InitQueue< LinkQueue *Q> { //置空隊：就是使頭結(jié)點成為隊尾元素 QueueNode *s; Q->rear = Q->rear->next;//將隊尾指針指向頭結(jié)點 while rear!=Q->rear->next>//當(dāng)隊列非空,將隊中元素逐個出隊 {s=Q->rear->next; Q->rear->next=s->next; delete s; }//回收結(jié)點空間 } (2) 判隊空? int EmptyQueue< LinkQueue *Q> { //判隊空。當(dāng)頭結(jié)點的next指針指向自己時為空隊 return Q->rear->next->next==Q->rear->next; } (3) 入隊 void EnQueue<