數(shù)據(jù)結(jié)構(gòu)習(xí)題解答

1、數(shù)據(jù)結(jié)構(gòu)習(xí)題解答第1章 緒論一、基本內(nèi)容數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)對(duì)象、數(shù)據(jù)結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)和數(shù)據(jù)類型等概念術(shù)語(yǔ)的確定含義；抽象數(shù)據(jù)類型的定義、表示和實(shí)現(xiàn)方法；描述算法的類C語(yǔ)言；算法設(shè)計(jì)的基本要求以及從時(shí)間和空間角度分析算法的方法。二、學(xué)習(xí)要點(diǎn)1熟悉各名詞、術(shù)語(yǔ)的含義，掌握基本概念，特別是數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)之間的關(guān)系。分清哪些是邏輯結(jié)構(gòu)的性質(zhì)，哪些是存儲(chǔ)結(jié)構(gòu)的性質(zhì)。2了解抽象數(shù)據(jù)類型的定義、表示和實(shí)現(xiàn)方法。3熟悉類C語(yǔ)言的書寫規(guī)范，特別要注意值調(diào)用和引用調(diào)用的區(qū)別，輸入、輸出的方式以及錯(cuò)誤處理方式。4理解算法五個(gè)要素的確切含義：動(dòng)態(tài)有窮性（能執(zhí)行結(jié)束）；確定性（對(duì)于相同的輸入執(zhí)行相同的路徑）；

2、有輸入；有輸出；可行性（用以描述算法的操作都是足夠基本的）。5掌握計(jì)算語(yǔ)句頻度和估算算法時(shí)間復(fù)雜度的方法。三、基礎(chǔ)知識(shí)題1.1 簡(jiǎn)述下列術(shù)語(yǔ)：數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)對(duì)象、數(shù)據(jù)結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)、數(shù)據(jù)類型和抽象數(shù)據(jù)類型。答：數(shù)據(jù)是對(duì)客觀事物的符號(hào)表示，在計(jì)算機(jī)科學(xué)中是指所有能輸入到計(jì)算機(jī)中并被計(jì)算機(jī)程序處理的符號(hào)的總稱。數(shù)據(jù)元素是數(shù)據(jù)的基本單位，在計(jì)算機(jī)程序中通常作為一個(gè)整體進(jìn)行考慮和處理。數(shù)據(jù)對(duì)象是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個(gè)子集。數(shù)據(jù)結(jié)構(gòu)是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。存儲(chǔ)結(jié)構(gòu)是數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的表示（又稱映像）。數(shù)據(jù)類型是一個(gè)值的集合和定義在這個(gè)值集上的一組操作的總

3、稱。抽象數(shù)據(jù)類型是指一個(gè)數(shù)學(xué)模型以及定義在該模型上的一組操作。1.2 試描述數(shù)據(jù)結(jié)構(gòu)和抽象數(shù)據(jù)類型的概念與程序設(shè)計(jì)語(yǔ)言中數(shù)據(jù)類型概念的區(qū)別。答：簡(jiǎn)單地說(shuō)，數(shù)據(jù)結(jié)構(gòu)定義了一組按某些關(guān)系結(jié)合在一起的數(shù)組元素。數(shù)據(jù)類型不僅定義了一組帶結(jié)構(gòu)的數(shù)據(jù)元素，而且還在其上定義了一組操作。程序設(shè)計(jì)語(yǔ)言中的數(shù)據(jù)類型是一個(gè)值的集合和定義在這個(gè)值集上的一組操作的總稱。而抽象數(shù)據(jù)類型是指一個(gè)數(shù)學(xué)模型以及定義在該模型上的一組操作。1.8 設(shè)n為正整數(shù)，試確定下列各程序段中前置以記號(hào)的語(yǔ)句的頻度。（1）i=1; k=0;while (i=n-1) k + =10 * i; i+ +; 答：n-1（2）i=1; k=0; d

4、o k + =10 * i; i+ +; while (i=n-1);答：（3）i=1; k=0;while (i=n-1) i+ +; k + =10 * i;答：n-1（4）k=0;for ( i=1; i=n; i+ +) for (j=i; j=n; j+ +) k+ +; 答：（5）for ( i=1; i=n; i+ +) for (j=i; j=i; j+ +) for (k=1; k=j; k+ +) x+ =delta; 答：（6）i=1; j=0;while (i+jj) j+ +; else i+ +; 答：n（7）x=n; y=0;while (x=(y+1)*(y+1

5、) y+ +; 答：（8）x=91; y=100;while (y0) if (x100) x- =100; y- -; else x+ +; 答：1100四、算法設(shè)計(jì)題1.16 試寫一算法，自大至小依次輸出順序讀入的三個(gè)整數(shù)X，Y，Z的值。答：void print_descending(int x,int y,int z)/按從大到小順序輸出三個(gè)數(shù) scanf(%d,%d,%d,&x,&y,&z); if(xy)temp=x; x=y; y=temp; if(y=temp) y=temp; else y=x; x=temp; printf(%d %d %d,x,y,z);/print_des

6、cending五、附加題5.1填空題1.數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問(wèn)題中計(jì)算機(jī)的 以及它們之間的 和運(yùn)算等的學(xué)科。操作對(duì)象，關(guān)系2. 數(shù)據(jù)結(jié)構(gòu)被形式地定義為（D, R），其中D是 的有限集合，R是D上的 有限集合。數(shù)據(jù)元素，關(guān)系3. 數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)的 、數(shù)據(jù)的 和數(shù)據(jù)的 這三個(gè)方面的內(nèi)容。4. 數(shù)據(jù)結(jié)構(gòu)按邏輯結(jié)構(gòu)可分為兩大類，它們分別是 和 。線性結(jié)構(gòu)，非線性結(jié)構(gòu)5. 線性結(jié)構(gòu)中元素之間存在 關(guān)系，樹(shù)形結(jié)構(gòu)中元素之間存在 關(guān)系，圖形結(jié)構(gòu)中元素之間存在 關(guān)系。一對(duì)一，一對(duì)多，多對(duì)多6數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)可用四種基本的存儲(chǔ)方法表示，它們分別是 。順序存儲(chǔ)結(jié)構(gòu)，鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，索引存儲(chǔ)結(jié)構(gòu)，散

7、列存儲(chǔ)結(jié)構(gòu)7. 一個(gè)算法的效率可分為 效率和 效率。時(shí)間，空間5.2 選擇題（ ）1.線性結(jié)構(gòu)是數(shù)據(jù)元素之間存在一種：DA一對(duì)多關(guān)系 B多對(duì)多關(guān)系 C多對(duì)一關(guān)系 D一對(duì)一關(guān)系（ ）2. 數(shù)據(jù)結(jié)構(gòu)中，與所使用的計(jì)算機(jī)無(wú)關(guān)的是數(shù)據(jù)的 結(jié)構(gòu)。CA存儲(chǔ) B物理 C邏輯 D物理和存儲(chǔ)（ ）3. 算法分析的目的是：CA找出數(shù)據(jù)結(jié)構(gòu)的合理性 B研究算法中的輸入和輸出的關(guān)系C分析算法的效率以求改進(jìn) D分析算法的易懂性和文檔性（ ）4. 計(jì)算機(jī)算法指的是：CA計(jì)算方法 B排序方法 C解決問(wèn)題的有限運(yùn)算序列 D調(diào)度方法（ ）5. 計(jì)算機(jī)算法必須具備輸入、輸出和 等5個(gè)特性。BA可行性、可移植性和可擴(kuò)充性 B可行性

8、、確定性和有窮性C確定性、有窮性和穩(wěn)定性 D易讀性、穩(wěn)定性和安全性第2章 線性表一、基本內(nèi)容線性表的邏輯結(jié)構(gòu)定義、抽象數(shù)據(jù)類型定義和各種存儲(chǔ)結(jié)構(gòu)的描述方法；在線性表的兩類存儲(chǔ)結(jié)構(gòu)（順序的和鏈?zhǔn)降模┥蠈?shí)現(xiàn)基本操作；稀疏多項(xiàng)式的抽象數(shù)據(jù)類型定義、表示和加法的實(shí)現(xiàn)。二、學(xué)習(xí)要點(diǎn)1了解線性表的邏輯結(jié)構(gòu)特性是數(shù)據(jù)元素之間存在著線性關(guān)系，在計(jì)算機(jī)中表示這種關(guān)系的兩類不同的存儲(chǔ)結(jié)構(gòu)是順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。用前者表示的線性表簡(jiǎn)稱為順序表，用后者表示的線性表簡(jiǎn)稱為鏈表。2熟練掌握這兩類存儲(chǔ)結(jié)構(gòu)的描述方法，如一維數(shù)據(jù)中一個(gè)區(qū)域i.j的上、下界和長(zhǎng)度之間的變換公式（L=j-i+1,i=j-L+1,j=i+L-

9、1）,鏈表中指針P和結(jié)點(diǎn)*p的對(duì)應(yīng)關(guān)系（結(jié)點(diǎn)*(p-next)是結(jié)點(diǎn)*p的后繼等），鏈表中的頭結(jié)點(diǎn)、頭指針和首元結(jié)點(diǎn)的區(qū)別及循環(huán)鏈表、雙向鏈表的特點(diǎn)等。鏈表是本章的重點(diǎn)和難點(diǎn)。扎實(shí)的指針操作和內(nèi)在動(dòng)態(tài)分配的編程技術(shù)是學(xué)好本章的基本要求。3熟練掌握線性表在順序存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)基本操作：查找、插入和刪除的算法。4熟練掌握在各種鏈表結(jié)構(gòu)中實(shí)現(xiàn)線性表操作的基本方法，能在實(shí)際應(yīng)用中選用適當(dāng)?shù)逆湵斫Y(jié)構(gòu)。了解靜態(tài)鏈表，能夠加深對(duì)鏈表本質(zhì)的理解。5能夠從時(shí)間和空間復(fù)雜度的角度綜合比較線性表兩種存儲(chǔ)結(jié)構(gòu)的不同特點(diǎn)及其適用場(chǎng)合。三、基礎(chǔ)知識(shí)題2.1 描述以下三個(gè)概念的區(qū)別：頭指針，頭結(jié)點(diǎn)，首元結(jié)點(diǎn)（第一個(gè)元素結(jié)點(diǎn)）

10、。答：首元結(jié)點(diǎn)是指鏈表中存儲(chǔ)線性表中第一個(gè)數(shù)據(jù)元素a1的結(jié)點(diǎn)。為了操作方便，通常在鏈表的首元結(jié)點(diǎn)之前附設(shè)一個(gè)結(jié)點(diǎn)，稱為頭結(jié)點(diǎn)，該結(jié)點(diǎn)的數(shù)據(jù)域中不存儲(chǔ)線性表的數(shù)據(jù)元素，其作用是當(dāng)對(duì)鏈表進(jìn)行操作時(shí)，可以對(duì)空表、非空表的情況以及對(duì)首元結(jié)點(diǎn)進(jìn)行統(tǒng)一處理。頭指針是指向鏈表中第一個(gè)結(jié)點(diǎn)（或?yàn)轭^結(jié)點(diǎn)或?yàn)槭自Y(jié)點(diǎn)）的指針。若鏈表中附設(shè)頭結(jié)點(diǎn)，則不管線性表是否為空表，頭指針均不為空，否則表示空表的鏈表的頭指針為空。這3個(gè)概念對(duì)單鏈表、雙向鏈表和循環(huán)鏈表均適用。是否設(shè)置頭結(jié)點(diǎn)，是不同的存儲(chǔ)結(jié)構(gòu)表示同一邏輯結(jié)構(gòu)的問(wèn)題。2.2 填空題1. 在順序表中插入或刪除一個(gè)元素，需要平均移動(dòng) 元素，具體移動(dòng)的元素個(gè)數(shù)與 有關(guān)。

11、答：表中一半，表長(zhǎng)和該元素在表中的位置2. 順序表中邏輯上相鄰的元素的物理位置 相鄰。單鏈表中邏輯上相鄰的元素的物理位置 相鄰。答：必定，不一定3. 在單鏈表中，除了首元結(jié)點(diǎn)外，任一結(jié)點(diǎn)的存儲(chǔ)位置由 指示。其前驅(qū)結(jié)點(diǎn)的鏈域的值4在單鏈表中設(shè)置頭結(jié)點(diǎn)的作用是 。插入和刪除首元素時(shí)不必進(jìn)行特殊處理2.6 已知L是無(wú)表頭結(jié)點(diǎn)的單鏈表，且P結(jié)點(diǎn)既不是首元結(jié)點(diǎn)，也不是尾元結(jié)點(diǎn)，試從下列提供的答案中選擇合適的語(yǔ)句序列。a.在P結(jié)點(diǎn)后插入S結(jié)點(diǎn)的語(yǔ)句序列是 。4，1b.在P結(jié)點(diǎn)前插入S結(jié)點(diǎn)的語(yǔ)句序列是 。7，11，8，4，1c.在表首插入S結(jié)點(diǎn)的語(yǔ)句序列是 。5，12d.在表尾插入S結(jié)點(diǎn)的語(yǔ)句序列是 。9，

12、1，6（1）P-next=S;（2）P-next=P-next-next;（3）P-next=S-next;（4）S-next=P-next;（5）S-next=L;（6）S-next=NULL;（7）Q=P;（8）while (p-next!=Q) P=P-next;（9）while (P-next!=NULL) P=P-next;（10）P=Q;（11）P=L;（12）L=S;（13）L=p;2.7 已知L是帶表頭結(jié)點(diǎn)的非空單鏈表，且P結(jié)點(diǎn)既不是首元結(jié)點(diǎn)，也不是尾元結(jié)點(diǎn)，試從下列提供的答案中選擇合適的語(yǔ)句序列。a.刪除P結(jié)點(diǎn)的直接后繼結(jié)點(diǎn)的語(yǔ)句序列是 。11，3，14b.刪除P結(jié)點(diǎn)的直接前

13、驅(qū)結(jié)點(diǎn)的語(yǔ)句序列是 。10，12，8，11，3，14c.刪除P結(jié)點(diǎn)的語(yǔ)句序列是 。10，12，7，3，14d.刪除首元結(jié)點(diǎn)的語(yǔ)句序列是 。12，11，3，14e.刪除尾元結(jié)點(diǎn)的語(yǔ)句序列是 。9，11，3，14（1）P=P-next;（2）P-next=P;（3）P-next=P-next-next;（4）P=P-next-next;（5）while (P!=NULL) P=P-next;（6）while (Q-next!=NULL) P=Q; Q=Q-next;（7）while (P-next!=Q) P=P-next;（8）while (p-next-next!=Q) P=P-next;（9

14、）while (P-next-next!=NULL) P=P-next;（10）Q=P;（11）Q=P-next;（12）P=L;（13）L=L-next;（14）free(Q);2.8 已知P結(jié)點(diǎn)是某雙向鏈表的中間結(jié)點(diǎn)，試從下列提供的答案中選擇合適的語(yǔ)句序列。a.在P結(jié)點(diǎn)后插入S結(jié)點(diǎn)的語(yǔ)句序列是 。7，12，3，6b.在P結(jié)點(diǎn)前插入S結(jié)點(diǎn)的語(yǔ)句序列是 。8，13，5，4c.刪除P結(jié)點(diǎn)的直接后繼結(jié)構(gòu)的語(yǔ)句序列是 。15，1，11，18d.刪除P結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)的語(yǔ)句序列是 。16，2，10，18e.刪除P結(jié)點(diǎn)的語(yǔ)句序列是 。9，14，17（1）P-next=P-next-next;（2）P-

15、priou=P-priou-priou;（3）P-next=S;（4）P-priou=S;（5）S-next=P;（6）S-priou=P;（7）S-next=P-next;（8）S-priou=P-priou;（9）P-priou-next=P-next;（10）P-priou-next=P;（11）P-next-priou=P;（12）P-next-priou=S;（13）P-priou -next =S;（14）P-next-priou=p-priou;（15）Q=P-next;（16）Q=P-priou;（17）free(P);（18）free(Q);2.7 簡(jiǎn)述以下算法的功能。（1）

16、 Status A(LinkedList L) /L是無(wú)表頭結(jié)點(diǎn)的單鏈表 if (L&L-next) Q=L; L=L-next; P=L; While (P-next) P=P-next; P-next=Q; Q-next=NULL; return OK; /A答：如果L的長(zhǎng)度不小于2，則將首元結(jié)點(diǎn)刪去并插入到表尾。（2） void BB(LNode *s, LNode *q) p=s;while (p-next!=q) p=p-next;p-next=s; /BBvoid AA(LNode *pa, LNode *pb) /pa和pb分別指向單循環(huán)鏈表中的兩個(gè)結(jié)點(diǎn)BB(pa,pb);BB(

17、pb,pa); /AA 答：將s至q之前的結(jié)點(diǎn)組成一個(gè)新的單循環(huán)鏈表，將q斷開(kāi)。四、算法設(shè)計(jì)題2.11設(shè)順序表va中的數(shù)據(jù)元素遞增有序。試寫一算法，將x插入到順序表的適當(dāng)位置上，以保持該表的有序性。答：Status Insert_SqList(SqList &va,int x)/把x插入遞增有序表va中 if(va.length+1va.listsize) return ERROR; va.length+; for(i=va.length-1;va.elemix&i=0;i-) va.elemi+1=va.elemi; va.elemi+1=x;return OK; /Insert_SqLis

18、t2.13 試寫一算法在帶頭結(jié)點(diǎn)的單鏈表結(jié)構(gòu)上實(shí)現(xiàn)線性表操作LOCATE(L,X)。答：LNode* Locate(LinkList L,int x)/鏈表上的元素查找,返回指針for(p=l-next;p&p-data!=x;p=p-next);return p;/Locate2.14 試寫一算法在帶頭結(jié)點(diǎn)的單鏈表結(jié)構(gòu)上實(shí)現(xiàn)線性表操作LENGTH（L）。答：int Length(LinkList L)/求鏈表的長(zhǎng)度f(wàn)or(k=0,p=L;p-next;p=p-next,k+);return k;/Length4已知線性表中的元素以值遞增有序排列，并以單鏈表作存儲(chǔ)結(jié)構(gòu)。試寫一高效算法，刪除表中

19、所有值大于mink且小于maxk的元素（若表中存在這樣的元素），同時(shí)釋放被刪結(jié)點(diǎn)空間，并分析你的算法的時(shí)間復(fù)雜度（注意：mink和maxk是給定的兩個(gè)參變量，它們的值可以和表中的元素相同，也可以不同）。5已知線性表中的元素以值遞增有序排列，并以單鏈表作存儲(chǔ)結(jié)構(gòu)。試寫一高效算法，刪除表中所有值相同的多余元素（使得操作后的線性表中所有元素的值均不相同），同時(shí)釋放被刪結(jié)點(diǎn)空間，并分析你的算法的時(shí)間復(fù)雜度。6試寫一算法，實(shí)現(xiàn)順序表的就地逆置，即得用原表的存儲(chǔ)空間將線性表(a1,a2,a3,an)逆置為(an,an-1a1)。7試寫一算法，對(duì)單鏈表實(shí)現(xiàn)就地逆置。答：void LinkList_rever

20、se(Linklist &L)/鏈表的就地逆置;為簡(jiǎn)化算法,假設(shè)表長(zhǎng)大于2p=L-next;q=p-next;s=q-next;p-next=NULL;while(s-next)q-next=p;p=q;q=s;s=s-next; /把L的元素逐個(gè)插入新表表頭q-next=p;s-next=q;L-next=s;/LinkList_reverse五、附加題5.1 判斷正誤（ ）1. 鏈表的每個(gè)結(jié)點(diǎn)中都恰好包含一個(gè)指針。 對(duì)（ ）2. 鏈表的物理存儲(chǔ)結(jié)構(gòu)具有同鏈表一樣的順序。錯(cuò) （ ）3. 鏈表的刪除算法很簡(jiǎn)單，因?yàn)楫?dāng)刪除鏈中某個(gè)結(jié)點(diǎn)后，計(jì)算機(jī)會(huì)自動(dòng)將后續(xù)各個(gè)單元向前移動(dòng)。 錯(cuò)（ ）4. 線性表

21、的每個(gè)結(jié)點(diǎn)只能是一個(gè)簡(jiǎn)單類型，而鏈表的每個(gè)結(jié)點(diǎn)可以是一個(gè)復(fù)雜類型。錯(cuò)（ ）5. 順序表結(jié)構(gòu)適宜于進(jìn)行順序存取，而鏈表適宜于進(jìn)行隨機(jī)存取。 錯(cuò)（ ）6. 順序存儲(chǔ)方式的優(yōu)點(diǎn)是存儲(chǔ)密度大，且插入、刪除運(yùn)算效率高。錯(cuò)（ ）7. 線性表在物理存儲(chǔ)空間中也一定是連續(xù)的。錯(cuò)（ ）8. 線性表在順序存儲(chǔ)時(shí)，邏輯上相鄰的元素未必在存儲(chǔ)的物理位置次序上相鄰。錯(cuò)（ ）9. 順序存儲(chǔ)方式只能用于存儲(chǔ)線性結(jié)構(gòu)。錯(cuò)（ ）10. 線性表的邏輯順序與存儲(chǔ)順序總是一致的。對(duì)4.2 單項(xiàng)選擇題（ ）1數(shù)據(jù)在計(jì)算機(jī)存儲(chǔ)器內(nèi)表示時(shí)，物理地址與邏輯地址相同并且是連續(xù)的，稱之為：CA存儲(chǔ)結(jié)構(gòu) B邏輯結(jié)構(gòu) C順序存儲(chǔ)結(jié)構(gòu) D鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

22、（ ）2. 一個(gè)向量第一個(gè)元素的存儲(chǔ)地址是100，每個(gè)元素的長(zhǎng)度為2，則第5個(gè)元素的地址是 BA110 B108 C100 D120（ ）3. 在n個(gè)結(jié)點(diǎn)的順序表中，算法的時(shí)間復(fù)雜度是O（1）的操作是：AA訪問(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)從小到大排序（ ）4. 向一個(gè)有127個(gè)元素的順序表中插入一個(gè)新元素并保持原來(lái)順序不變，平均要移動(dòng) 個(gè)元素BA8 B63.5 C63 D7（ ）5. 鏈接存儲(chǔ)的存儲(chǔ)結(jié)構(gòu)所占存儲(chǔ)空間：AA分兩部分，一部分存放結(jié)點(diǎn)值，另一部分存放表示結(jié)點(diǎn)間關(guān)系的指針B只有一

23、部分，存放結(jié)點(diǎn)值C只有一部分，存儲(chǔ)表示結(jié)點(diǎn)間關(guān)系的指針D分兩部分，一部分存放結(jié)點(diǎn)值，另一部分存放結(jié)點(diǎn)所占單元數(shù)（ ）6. 鏈表是一種采用 存儲(chǔ)結(jié)構(gòu)存儲(chǔ)的線性表；BA順序 B鏈?zhǔn)?C星式 D網(wǎng)狀（ ）7. 線性表若采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí)，要求內(nèi)存中可用存儲(chǔ)單元的地址:DA必須是連續(xù)的 B部分地址必須是連續(xù)的C一定是不連續(xù)的 D連續(xù)或不連續(xù)都可以（ ）8 線性表L在 情況下適用于使用鏈?zhǔn)浇Y(jié)構(gòu)實(shí)現(xiàn)。BA需經(jīng)常修改L中的結(jié)點(diǎn)值 B需不斷對(duì)L進(jìn)行刪除插入 CL中含有大量的結(jié)點(diǎn) DL中結(jié)點(diǎn)結(jié)構(gòu)復(fù)雜（ ）9 單鏈表的存儲(chǔ)密度（ ）。BA大于1； B等于1； C小于1； D不能確定（ ）10 設(shè)a1、a2、a3為

24、3個(gè)結(jié)點(diǎn)，整數(shù)P0，3，4代表地址，則如下的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)稱為（ ）。A、P034P0a13a24a30A循環(huán)鏈表 B單鏈表 C雙向循環(huán)鏈表 D雙向鏈表第3章 棧和隊(duì)列一、基本內(nèi)容棧和隊(duì)列的結(jié)構(gòu)特性；在兩種存儲(chǔ)結(jié)構(gòu)上如何實(shí)現(xiàn)棧和隊(duì)列的基本操作以及棧和隊(duì)列在程序設(shè)計(jì)中的應(yīng)用。二、學(xué)習(xí)要點(diǎn)1掌握棧和隊(duì)列這兩種抽象數(shù)據(jù)類型的特點(diǎn)，并能在相應(yīng)的應(yīng)用問(wèn)題中正確選用它們。2熟練掌握棧類型的兩種實(shí)現(xiàn)方法，即兩種存儲(chǔ)結(jié)構(gòu)表示時(shí)的基本操作實(shí)現(xiàn)算法，特別應(yīng)注意棧滿和?？盏臈l件以及它們的描述方法。3熟練掌握循環(huán)隊(duì)列和鏈隊(duì)列的基本操作實(shí)現(xiàn)方法，特別注意隊(duì)滿和隊(duì)空的描述方法。三、基礎(chǔ)知識(shí)題3.2 說(shuō)明棧和線性表的異同點(diǎn)。

25、答：棧是限定僅在表尾進(jìn)行插入或刪除操作的線性表。3.3 寫出下列程序段的輸出結(jié)果（棧的元素類型SElem Type為char）。void main( )Stack S;Char x,y;InitStack(S);X=c;y=k;Push(S,x); Push(S,a); Push(S,y);Pop(S,x); Push(S,t); Push(S,x);Pop(S,x); Push(S,s);while(!StackEmpty(S) Pop(S,y);printf(y); ;Printf(x);答：stack3.4 簡(jiǎn)述以下算法的功能（棧的元素類型SElemType為int）。(1)Status

26、 algo1(Stack S) int i，n，A255； n=0； while (!StackEmpty(S) n+； Pop(S，An)； for (i=1；itop0 ST-top=0 ST-topm0 ST-top=m0（ ）4. 判定一個(gè)隊(duì)列QU（最多元素為m0）為滿隊(duì)列的條件是：BQU-rear QU-front = = m0 QU-rear QU-front 1= = m0 QU-front = = QU-rear QU-front = = QU-rear+1（ ）5數(shù)組用來(lái)表示一個(gè)循環(huán)隊(duì)列，為當(dāng)前隊(duì)列頭元素的前一位置，為隊(duì)尾元素的位置，假定隊(duì)列中元素的個(gè)數(shù)小于，計(jì)算隊(duì)列中元素的

27、公式為：Drf; （nfr）% n; nrf; （nrf）% n6. 設(shè)有4個(gè)數(shù)據(jù)元素a1、a2、a3和a4，對(duì)他們分別進(jìn)行棧操作或隊(duì)操作。在進(jìn)?；蜻M(jìn)隊(duì)操作時(shí)，按a1、a2、a3、a4次序每次進(jìn)入一個(gè)元素。假設(shè)棧或隊(duì)的初始狀態(tài)都是空?，F(xiàn)要進(jìn)行的棧操作是進(jìn)棧兩次，出棧一次，再進(jìn)棧兩次，出棧一次；這時(shí)，第一次出棧得到的元素是 A ，第二次出棧得到的元素是 B ；類似地，考慮對(duì)這四個(gè)數(shù)據(jù)元素進(jìn)行的隊(duì)操作是進(jìn)隊(duì)兩次，出隊(duì)一次，再進(jìn)隊(duì)兩次，出隊(duì)一次；這時(shí)，第一次出隊(duì)得到的元素是 C ，第二次出隊(duì)得到的元素是 D 。經(jīng)操作后，最后在棧中或隊(duì)中的元素還有 E 個(gè)。供選擇的答案： AD：a1 a2 a3 a4

28、 E： 1 2 3 0答：A、B、C、D、E分別為 、 、 、 、 7. 棧是一種線性表，它的特點(diǎn)是 A 。設(shè)用一維數(shù)組A1,n來(lái)表示一個(gè)棧，An為棧底，用整型變量T指示當(dāng)前棧頂位置，AT為棧頂元素。往棧中推入（PUSH）一個(gè)新元素時(shí)，變量T的值 B ；從棧中彈出（POP）一個(gè)元素時(shí)，變量T的值 C 。設(shè)棧空時(shí)，有輸入序列a，b，c，經(jīng)過(guò)PUSH，POP，PUSH，PUSH，POP操作后，從棧中彈出的元素的序列是 D ，變量T的值是 E 。供選擇的答案：A： 先進(jìn)先出 后進(jìn)先出 進(jìn)優(yōu)于出 出優(yōu)于進(jìn) 隨機(jī)進(jìn)出B，C： 加1 減1 不變 清0 加2 減2D： a,b b,c c,a b,a c,b

29、 a,cE： n+1 n+2 n n-1 n-2答：A、B、C、D、E分別為 、 、 、 、 8. 在做進(jìn)棧運(yùn)算時(shí)，應(yīng)先判別棧是否 A ；在做退棧運(yùn)算時(shí)，應(yīng)先判別棧是否 B 。當(dāng)棧中元素為n個(gè)，做進(jìn)棧運(yùn)算時(shí)發(fā)生上溢，則說(shuō)明該棧的最大容量為 C 。為了增加內(nèi)存空間的利用率和減少溢出的可能性，由兩個(gè)棧共享一片連續(xù)的內(nèi)存空間時(shí)，應(yīng)將兩棧的 D 分別設(shè)在這片內(nèi)存空間的兩端，這樣，只有當(dāng) E 時(shí)，才產(chǎn)生上溢。供選擇的答案：A，B：空 滿 上溢 下溢C： n-1 n n+1 n/2D： 長(zhǎng)度 深度 棧頂 棧底E：兩個(gè)棧的棧頂同時(shí)到達(dá)棧空間的中心點(diǎn) 其中一個(gè)棧的棧頂?shù)竭_(dá)?？臻g的中心點(diǎn) 兩個(gè)棧的棧頂在達(dá)?？臻g

30、的某一位置相遇 兩個(gè)棧均不空，且一個(gè)棧的棧頂?shù)竭_(dá)另一個(gè)棧的棧底答：A、B、C、D、E分別為 、 、 、 、 第4章 串一、基本內(nèi)容串的數(shù)據(jù)類型定義；串的三種存儲(chǔ)表示；定長(zhǎng)順序存儲(chǔ)結(jié)構(gòu)、塊鏈存儲(chǔ)結(jié)構(gòu)和堆分配存儲(chǔ)結(jié)構(gòu)；串的各種基本操作的實(shí)現(xiàn)及其應(yīng)用；串的模式匹配算法。二、學(xué)習(xí)要點(diǎn)1熟悉串的七種基本操作的定義，并能利用這些基本操作實(shí)現(xiàn)串的其他操作的方法。2熟練掌握在串的定長(zhǎng)順序存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)串的各種操作的方法。三、基礎(chǔ)知識(shí)題4.2 簡(jiǎn)述空串和空格串的區(qū)別。答：空格串是由一個(gè)或多個(gè)空格組成的串，它的長(zhǎng)度為串中空格字符的個(gè)數(shù)；空串用符號(hào)“”表示，它的長(zhǎng)度為0。4.3 設(shè)s=I AM A STUDENT,

31、t=GOOD,q=WORKER。求：StrLength(s), StrLength(t), SubString(s,8,7), SubString(t,2,1),Index(s,A), Index(s,t), Replace(s,STUDENT,q),Concat(Substring(s,6,2),Concat(t,SubString(s,7,8)。答：StrLength(s)=14 StrLength(t)=4 SubString(s,8,7)= STUDENTSubString(t,2,1)= O Index(s,A)=3 Index(s,t)=0Replace(s,STUDENT,q)I

32、 AM A WORKERConcat(t,SubString(s,7,8)A GOOD STUDENT4.4 已知下列字符串a(chǎn)=THIS, f=A SAMPLE,c=GOOD,d=NE,b= ,s=Concat(a,Concat(SubString(f,2,7),Concat(b,SubString(a,3,2),t=Replace(f,SubString(f,3,6),c), u=Concat(SubString(c,3,1),d),v=Concat(s,Concat(b,Concat(t,Concat(b,u),試問(wèn)：s,t,v,StrLength(s),Index(v,g),Index(

33、u,g)各是什么？答：v=THIS SAMPLE IS A GOOD ONEINDEX(v,g)=3INDEX(u,g)=04.12 編寫一個(gè)實(shí)現(xiàn)串的置換操作Replace(&S, T, V)的算法。解：int Replace(Stringtype &S,Stringtype T,Stringtype V);/將串S中所有子串T替換為 V,并返回置換次數(shù) for(n=0,i=1;i=Strlen(S)-Strlen(T)+1;i+) /注意i的取值范圍 if(!StrCompare(SubString(S,i,Strlen(T),T) /找到了與T匹配的子串 /分別把T的前面和后面部分保存為h

34、ead和tail StrAssign(head,SubString(S,1,i-1); StrAssign(tail,SubString(S,i+Strlen(T),Strlen(S)-i-Strlen(T)+1); StrAssign(S,Concat(head,V); StrAssign(S,Concat(S,tail); /把head,V,tail連接為新串 i+=Strlen(V); /當(dāng)前指針跳到插入串以后 n+; n+; /if return n; /Replace分析:i+=Strlen(V);這一句是必需的,也是容易忽略的.如省掉這一句,則在某些情況下, 會(huì)引起不希望的后果,雖

35、然在大多數(shù)情況下沒(méi)有影響。四、附加題4.1 選擇題（ ）1. 串是一種特殊的線性表，其特殊性體現(xiàn)在：B可以順序存儲(chǔ) 數(shù)據(jù)元素是一個(gè)字符 可以鏈?zhǔn)酱鎯?chǔ) 數(shù)據(jù)元素可以是多個(gè)字符（ ）2. 設(shè)有兩個(gè)串p和q，求q在p中首次出現(xiàn)的位置的運(yùn)算稱作：B連接 模式匹配 求子串 求串長(zhǎng)（ ）3. 設(shè)串s1=ABCDEFG，s2=PQRST，函數(shù)con(x,y)返回x和y串的連接串，subs(s, i, j)返回串s的從序號(hào)i開(kāi)始的j個(gè)字符組成的子串，len(s)返回串s的長(zhǎng)度，則con(subs(s1, 2, len(s2), subs(s1, len(s2), 2)的結(jié)果串是：DBCDEF BCDEFG B

36、CPQRST BCDEFEF第5章 數(shù)組與廣義表一、基本內(nèi)容數(shù)組的類型定義和表示方式；特殊矩陣和稀疏矩陣的壓縮存儲(chǔ)方法以及運(yùn)算的實(shí)現(xiàn)；廣義表的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)。二、學(xué)習(xí)要點(diǎn)1了解數(shù)組的兩種存儲(chǔ)表示方法，并掌握數(shù)組在以行為主的存儲(chǔ)結(jié)構(gòu)中的地址計(jì)算方法。2掌握對(duì)特殊矩陣進(jìn)行壓縮存儲(chǔ)時(shí)的下標(biāo)變換公式。3了解稀疏矩陣的兩種壓縮存儲(chǔ)方法的特點(diǎn)和適用范圍，領(lǐng)會(huì)以三元組表示稀疏矩陣時(shí)進(jìn)行矩陣運(yùn)算采用的處理方法。4掌握廣義表的結(jié)構(gòu)特點(diǎn)及其存儲(chǔ)表示方法，可根據(jù)自己的習(xí)慣，熟練掌握任意一種結(jié)構(gòu)的鏈表。三、基礎(chǔ)知識(shí)題5.1 假設(shè)有二維數(shù)組A68，每個(gè)元素用相鄰的6個(gè)字節(jié)存儲(chǔ)，存儲(chǔ)器按字節(jié)編址。已知A的起始存儲(chǔ)位置

37、（基地址）為1000，計(jì)算：（1）數(shù)組A的體積（存儲(chǔ)量）；（2）末尾元素A57的第一個(gè)字節(jié)地址為；（3）若按行存儲(chǔ)時(shí)，元素A14的第一個(gè)字節(jié)地址為；（4）若按列存儲(chǔ)時(shí)，元素A47的第一個(gè)字節(jié)地址為。答：（1）6*6*8=288（2）1000+288-6=1282（3）1000+(1-0)*8+(4-0)*6=1072（4）1000+(7-0)*6+(4-0)*6=12765.10 求下列廣義表操作的結(jié)果。(1) GetHead(p,h,w)(2) GetTail(b,k,p,h)(3) GetHead(a,b),(c,d)(4) GetTail(a,b),(c,d)(5) GetHeadGet

38、Tail(a,b),(c,d)(6) GetTailGetHead(a,b),(c,d)(7) GetHeadGetTailGetHead(a,b),(c,d)(8) GetTailGetHeadGetTail(a,b),(c,d)答：(1) p (2) (k,p,h) (3) (a,b) (4) (c,d) (5) (c,d) (6) (b) (7) b (8) (d)5.12 按教科書5.5節(jié)中圖5.8所示結(jié)點(diǎn)結(jié)構(gòu)，畫出下列廣義表的存儲(chǔ)結(jié)構(gòu)圖，并求它的深度。（1）（），a，（b，c），（），d），（e）；（2）（a），b），（），d），（e，f）；答：（1）深度為4（2）深度為4四、附加題

39、4.1 用三元組表表示下列稀疏矩陣： 答：（1） (3,2,3),(3,6,8),(5,4,6),(7,8,5),(8,1,2)（2） (1,6,-2),(2,5,9),(4,3,5),(6,5,3)第6章 樹(shù)和二叉樹(shù)一、基本內(nèi)容二叉樹(shù)的定義、性質(zhì)和存儲(chǔ)結(jié)構(gòu)；二叉樹(shù)的遍歷和線索化以及遍歷算法的各種描述形式；樹(shù)和森林的定義、存儲(chǔ)結(jié)構(gòu)與二叉樹(shù)的轉(zhuǎn)換、遍歷；樹(shù)的多種應(yīng)用。本章是課程的重點(diǎn)內(nèi)容之一。二、學(xué)習(xí)要點(diǎn)1熟練掌握二叉樹(shù)的結(jié)構(gòu)特性，了解相應(yīng)的證明方法。2熟悉二叉樹(shù)的各種存儲(chǔ)結(jié)構(gòu)的特點(diǎn)及適用范圍。3遍歷二叉樹(shù)是二叉樹(shù)各種操作的基礎(chǔ)。實(shí)現(xiàn)二叉樹(shù)遍歷的具體算法與所采用的存儲(chǔ)結(jié)構(gòu)有關(guān)。不僅要熟練掌握各種

40、遍歷策略的遞歸和非遞歸算法，了解遍歷過(guò)程中“?！钡淖饔煤蜖顟B(tài)，而且能靈活運(yùn)算遍歷算法實(shí)現(xiàn)二叉樹(shù)的其他操作。層次遍歷是按另一種搜索策略進(jìn)行的遍歷。4理解二叉樹(shù)線索化的實(shí)質(zhì)是建立結(jié)點(diǎn)與其在相應(yīng)序列中的前驅(qū)或后繼之間的直接聯(lián)系，熟練掌握二叉樹(shù)的線索化過(guò)程以及在中序線索樹(shù)上找給定結(jié)點(diǎn)的前驅(qū)和后繼的方法。二叉樹(shù)的線索化過(guò)程是基于對(duì)二叉樹(shù)進(jìn)行遍歷，而線索二叉樹(shù)上的線索又為相應(yīng)的遍歷提供了方便。5熟悉樹(shù)的各種存儲(chǔ)結(jié)構(gòu)和特點(diǎn)，掌握樹(shù)和森林與二叉樹(shù)的轉(zhuǎn)換方法。建立存儲(chǔ)結(jié)構(gòu)是進(jìn)行其他操作的前提，要掌握1至2種建立二叉樹(shù)和樹(shù)的存儲(chǔ)結(jié)構(gòu)的方法。6了解最優(yōu)樹(shù)的特性，掌握建立最優(yōu)樹(shù)和哈夫曼編碼的方法。三、基礎(chǔ)知識(shí)題6.1

41、 已知一棵樹(shù)邊的集合為,，請(qǐng)畫出這棵樹(shù)，并回答下列問(wèn)題。（1）哪個(gè)是根結(jié)點(diǎn)？ （2）哪些是葉子結(jié)點(diǎn)？（3）哪個(gè)是結(jié)點(diǎn)G的雙親？ （4）哪些是結(jié)點(diǎn)G的祖先？（5）哪些是結(jié)點(diǎn)G的孩子？ 6）哪些是結(jié)點(diǎn)E的子孫？（7）哪些是結(jié)點(diǎn)E的兄弟？哪些是結(jié)點(diǎn)F的兄弟？ABCDEFHIGJKMNL（8）結(jié)點(diǎn)B和N的層次號(hào)分別是什么？（9）樹(shù)的深度是多少？ （10）以結(jié)點(diǎn)C為根的子樹(shù)的深度是多少？答：（1） A （2）D,M,N,F,J,K,L (3）C （4）A,C （5）J,K （6）I,M,N （7）E的兄弟是D,F的兄弟是G和H （8）2，5 （9）5 （10）36.2 一棵度為2的樹(shù)與一棵二叉樹(shù)有何區(qū)別？答：度為2的樹(shù)從形式上看與二叉樹(shù)很相似，但它的子樹(shù)是無(wú)序的，而二叉樹(shù)是有序的。即，在一般樹(shù)中若某結(jié)點(diǎn)只有一個(gè)孩子，就無(wú)需區(qū)分其左右次序，而在二叉樹(shù)中即使是一個(gè)孩子也有左右之分。6.3 試分別畫出具有3個(gè)結(jié)點(diǎn)的樹(shù)和3個(gè)結(jié)點(diǎn)的二叉樹(shù)的所有不同形態(tài)。（1）（2）ABCABCCBAABCABC（一）（二）（三）（