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

1、精選優(yōu)質(zhì)文檔-傾情為你奉上數(shù)據(jù)結(jié)構(gòu)（C語言版）（第2版）課后習(xí)題答案李冬梅 目 錄專心-專注-專業(yè)第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)畫等通過特殊編碼定義后的數(shù)據(jù)。數(shù)據(jù)元素：是數(shù)據(jù)的基本單位，在計(jì)算機(jī)中通常作為一個(gè)整體進(jìn)行考慮和處理。在有些情況下，數(shù)據(jù)元素也稱為元素、結(jié)點(diǎn)、記錄等。數(shù)據(jù)元素用于完整地描述一個(gè)對(duì)象，如一個(gè)學(xué)生記錄，樹中棋盤的一個(gè)格局（狀

2、態(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ù)元素的集合。換句話說，數(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ǔ)無關(guān)，是獨(dú)立于計(jì)算機(jī)的。因此，數(shù)據(jù)的邏輯結(jié)構(gòu)可以看作是從具體問題

3、抽象出來的數(shù)學(xué)模型。存儲(chǔ)結(jié)構(gòu)：數(shù)據(jù)對(duì)象在計(jì)算機(jī)中的存儲(chǔ)表示，也稱為物理結(jié)構(gòu)。抽象數(shù)據(jù)類型：由用戶定義的，表示應(yīng)用問題的數(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è)表來說，只有一個(gè)開始結(jié)點(diǎn)(它的前面無記錄)和一個(gè)終端結(jié)點(diǎn)(它的后面無記錄)，其他的結(jié)點(diǎn)則各有一個(gè)也只有一個(gè)直

4、接前趨和直接后繼。學(xué)生記錄之間的這種關(guān)系就確定了學(xué)生表的邏輯結(jié)構(gòu)，即線性結(jié)構(gòu)。這些學(xué)生記錄在計(jì)算機(jī)中的存儲(chǔ)表示就是存儲(chǔ)結(jié)構(gòu)。如果用連續(xù)的存儲(chǔ)單元(如用數(shù)組表示)來存放這些記錄，則稱為順序存儲(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)系外，別無其他關(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)

5、行排列，將組成一個(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ì)位置來表示數(shù)據(jù)元素之間的邏輯關(guān)系，通常借助程序設(shè)計(jì)語言的數(shù)組類型來描述。（2）鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)要求所有的元素依次存放在一片連續(xù)的存儲(chǔ)空間中，而

6、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，無需占用一整塊存儲(chǔ)空間。但為了表示結(jié)點(diǎn)之間的關(guān)系，需要給每個(gè)結(jié)點(diǎn)附加指針字段，用于存放后繼元素的存儲(chǔ)地址。所以鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)通常借助于程序設(shè)計(jì)語言的指針類型來描述。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ù)無關(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)

7、數(shù)據(jù)項(xiàng)的類型要一致C每個(gè)數(shù)據(jù)元素都一樣D數(shù)據(jù)元素所包含的數(shù)據(jù)項(xiàng)的個(gè)數(shù)要相等答案：B（4）以下說法正確的是（ ）。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問題的規(guī)模B待處理數(shù)據(jù)的初態(tài)C計(jì)算機(jī)的配置DA和B答案：D解釋：算法的時(shí)間復(fù)雜度不僅與問題的規(guī)模有關(guān)，還與問題的其他因素有關(guān)。如某些排序的算法，其執(zhí)行時(shí)間與待排序記錄的初始狀態(tài)有關(guān)。為此，有時(shí)會(huì)對(duì)算法有最好、最壞以及

8、平均時(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(y>0)if(x>100) x=x-10;y-;else x+;答案：O(1)解釋：程序的執(zhí)行次數(shù)為常數(shù)階。（2）for (i=0; i<n; i+)for (j=0; j<m; j+)aij=0;答案：O(m*n)解釋：語句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;答案：O(n2

9、)解釋：語句s+=Bij;的執(zhí)行次數(shù)為n2。（4）i=1; while(i<=n) i=i*3;答案：O(log3n) 解釋：語句i=i*3;的執(zhí)行次數(shù)為?log3n?。（5）x=0;for(i=1; i<n; i+) for (j=1; j<=n-i; j+)x+;答案：O(n2)解釋：語句x+;的執(zhí)行次數(shù)為n-1+n-2+1= n(n-1)/2。（6）x=n; ext=s; (*s).next=(*p).next;Cs->next=p->next; p->next=s->next;Ds->next=p->next; p->next

10、=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)

11、 在雙向循環(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

12、; p->next=q; p->next->prior=q;答案：C2算法設(shè)計(jì)題（1）將兩個(gè)遞增的有序鏈表合并為一個(gè)遞增的有序鏈表。要求結(jié)果鏈表仍使用原來兩個(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表中的元素，這樣確保合并后表中無重復(fù)的元素。當(dāng)一個(gè)表到達(dá)表尾結(jié)點(diǎn)，為空時(shí)，將非空表

13、的剩余元素直接鏈接在Lc表的最后。算法描述void MergeList(LinkList &La,LinkList &Lb,LinkList &Lc)想摘除棧頂結(jié)點(diǎn)，并將刪除結(jié)點(diǎn)的值保存到x中,則應(yīng)執(zhí)行操作（ ）。Ax=top->data;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）

14、設(shè)有一個(gè)遞歸算法如下? ? int fact(int n) ? 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，說明元素從數(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)先出原則。

15、（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ì)尾指針

16、是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. 沒有共同點(diǎn)答案：C解釋：棧只允許在棧頂處進(jìn)行插入和刪除元素，隊(duì)列只允許在隊(duì)尾插入元素和在隊(duì)頭刪除元素。（15）一個(gè)遞歸算法必須包括（）。A. 遞歸部分 B. 終止條件和遞歸部分C. 迭代

17、部分 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)。試編寫雙棧初始化，判斷?？铡M、進(jìn)棧和出棧等算法的函數(shù)。雙棧數(shù)據(jù)結(jié)構(gòu)的定義如下：Typedef structint top2,bot2; IOIIOIOO B. IOOIOIIO C. IIIOIOIO D. IIIOOIOO通過對(duì)的分析，寫出一個(gè)算法，判定所給的操作序列是否合法。若合法，返回true，否則返回false（假定被判定的操作序列已存入

18、一維數(shù)組中）。答案：A和D是合法序列，B和C 是非法序列。設(shè)被判定的操作序列已存入一維數(shù)組A中。int Judge(char A) M-1實(shí)現(xiàn)循環(huán)隊(duì)列，其中M是隊(duì)列長(zhǎng)度。設(shè)隊(duì)頭指針 front和隊(duì)尾指針rear，約定front指向隊(duì)頭元素的前一位置，rear指向隊(duì)尾元素。定義front=rear時(shí)為隊(duì)空，(rear+1)%m=front 為隊(duì)滿。約定隊(duì)頭端入隊(duì)向下標(biāo)小的方向發(fā)展，隊(duì)尾端入隊(duì)向下標(biāo)大的方向發(fā)展。算法描述#define M 隊(duì)列可能達(dá)到的最大長(zhǎng)度typedef structelemtp dataM;int front,rear;cycqueue;elemtp delqueue (

19、cycqueue Q) 100,1.100，設(shè)每個(gè)數(shù)據(jù)元素占2個(gè)存儲(chǔ)單元，基地址為10，則LOC5,5=（ ）。A808 B818 C1010 D1020答案：B解釋：以行序?yàn)橹鳎瑒tLOC5,5=（5-1）*100+（5-1）*2+10=818。（7）設(shè)有數(shù)組Ai,j，數(shù)組的每個(gè)元素長(zhǎng)度為3字節(jié)，i的值為1到8，j的值為1到10，數(shù)組從內(nèi)存首地址BA開始順序存放，當(dāng)用以列為主存放時(shí)，元素A5,8的存儲(chǔ)首地址為（ ）。ABA+141 BBA+180 CBA+222 DBA+225答案：B解釋：以列序?yàn)橹?，則LOC5,8=（8-1）*8+（5-1）*3+BA=BA+180。（8）設(shè)有一個(gè)10階的對(duì)

20、稱矩陣A，采用壓縮存儲(chǔ)方式，以行序?yàn)橹鞔鎯?chǔ)，a11為第一元素，其存儲(chǔ)地址為1，每個(gè)元素占一個(gè)地址空間，則a85的地址為（ ）。A13 B32 C33 D40答案：C（9）若對(duì)n階對(duì)稱矩陣A以行序?yàn)橹餍蚍绞綄⑵湎氯切蔚脑?包括主對(duì)角線上所有元素)依次存放于一維數(shù)組B1.(n(n+1)/2中，則在B中確定aij（i<j）的位置k的關(guān)系為（ ）。Ai*(i-1)/2+j Bj*(j-1)/2+i Ci*(i+1)/2+j Dj*(j+1)/2+i答案：B（10）二維數(shù)組A的每個(gè)元素是由10個(gè)字符組成的串，其行下標(biāo)i=0,1,8,列下標(biāo)j=1,2,10。若A按行先存儲(chǔ)，元素A8,5的起始地址

21、與當(dāng)A按列先存儲(chǔ)時(shí)的元素（ ）的起始地址相同。設(shè)每個(gè)字符占一個(gè)字節(jié)。AA8,5 BA3,10 C. A5,8 DA0,9答案：B解釋：設(shè)數(shù)組從內(nèi)存首地址M開始順序存放，若數(shù)組按行先存儲(chǔ)，元素A8,5的起始地址為：M+（8-0）*10+（5-1）*1=M+84；若數(shù)組按列先存儲(chǔ)，易計(jì)算出元素A3,10的起始地址為：M+（10-1）*9+（3-0）*1=M+84。故選B。（11）設(shè)二維數(shù)組A1. m，1. n（即m行n列）按行存儲(chǔ)在數(shù)組B1. m*n中，則二維數(shù)組元素Ai,j在一維數(shù)組B中的下標(biāo)為（ ）。A(i-1)*n+j B(i-1)*n+j-1 Ci*(j-1) Dj*m+i-1答案：A解釋

22、：特殊值法。取i=j=1，易知A1,1的的下標(biāo)為1，四個(gè)選項(xiàng)中僅有A選項(xiàng)能確定的值為1，故選A。（12）數(shù)組A0.4,-1.-3,5.7中含有元素的個(gè)數(shù)（ ）。A55 B45 C36 D16答案：B解釋：共有5*3*3=45個(gè)元素。（13）廣義表A=(a,b,(c,d),(e,(f,g)，則Head(Tail(Head(Tail(Tail(A)的值為（ ）。A(g) B(d) Cc Dd答案：D解釋：Tail(A)=(b,(c,d),(e,(f,g)；Tail(Tail(A)=( (c,d),(e,(f,g)； Head(Tail(Tail(A)= (c,d)；Tail(Head(Tail(T

23、ail(A)=(d)；Head(Tail(Head(Tail(Tail(A)=d。（14）廣義表(a,b,c,d)的表頭是（ ），表尾是（ ）。Aa B( ) C(a,b,c,d) D(b,c,d)答案：C、B解釋：表頭為非空廣義表的第一個(gè)元素，可以是一個(gè)單原子，也可以是一個(gè)子表，(a,b,c,d)的表頭為一個(gè)子表(a,b,c,d)；表尾為除去表頭之外，由其余元素構(gòu)成的表，表為一定是個(gè)廣義表，(a,b,c,d)的表尾為空表( )。（15）設(shè)廣義表L=(a,b,c)，則L的長(zhǎng)度和深度分別為（ ）。A1和1 B1和3 C1和2 D2和3 答案：C解釋：廣義表的深度是指廣義表中展開后所含括號(hào)的層數(shù)，

24、廣義表的長(zhǎng)度是指廣義表中所含元素的個(gè)數(shù)。根據(jù)定義易知L的長(zhǎng)度為1，深度為2。2應(yīng)用題 （1）已知模式串t=abcaabbabcab寫出用KMP法求得的每個(gè)字符對(duì)應(yīng)的next和nextval函數(shù)值。答案：模式串t的next和nextval值如下：j1 2 3 4 5 6 7 8 9 10 11 12 t串a(chǎn) b c a a b b a b c a bnextj0 1 1 1 2 2 3 1 2 3 4 5nextvalj0 1 1 0 2 1 3 0 1 1 0 5（2）設(shè)目標(biāo)為t=“abcaabbabcabaacbacba”,模式為p=“abcabaa” 計(jì)算模式p的naxtval函數(shù)值； 不

25、寫出算法,只畫出利用KMP算法進(jìn)行模式匹配時(shí)每一趟的匹配過程。答案： p的nextval函數(shù)值為。（p的next函數(shù)值為）。 利用KMP(改進(jìn)的nextval)算法，每趟匹配過程如下： 第一趟匹配： abcaabbabcabaacbacba abcab(i=5,j=5) 第二趟匹配： abcaabbabcabaacbacba abc(i=7,j=3) 第三趟匹配： abcaabbabcabaacbacba a(i=7,j=1) 第四趟匹配： abcaabbabcabaac bacba (成功) abcabaa(i=15,j=8)（3）數(shù)組A中，每個(gè)元素Ai,j的長(zhǎng)度均為32個(gè)二進(jìn)位,行下標(biāo)從-

26、1到9，列下標(biāo)從1到11，從首地址S開始連續(xù)存放主存儲(chǔ)器中，主存儲(chǔ)器字長(zhǎng)為16位。求： 存放該數(shù)組所需多少單元？ 存放數(shù)組第4列所有元素至少需多少單元？ 數(shù)組按行存放時(shí)，元素A7,4的起始地址是多少？ 數(shù)組按列存放時(shí)，元素A4,7的起始地址是多少？答案：每個(gè)元素32個(gè)二進(jìn)制位，主存字長(zhǎng)16位，故每個(gè)元素占2個(gè)字長(zhǎng)，行下標(biāo)可平移至1到11。（1）242 （2）22 （3）s+182 （4）s+142(4)請(qǐng)將香蕉banana用工具 H( )Head( )，T( )Tail( )從L中取出。L=(apple,(orange,(strawberry,(banana),peach),pear)答案：H

27、（H（T（H（T（H（T（L）3算法設(shè)計(jì)題（1）寫一個(gè)算法統(tǒng)計(jì)在輸入字符串中各個(gè)不同字符出現(xiàn)的頻度并將結(jié)果存入文件（字符串中的合法字符為A-Z這26個(gè)字母和0-9這10個(gè)數(shù)字）。題目分析 由于字母共26個(gè)，加上數(shù)字符號(hào)10個(gè)共36個(gè)，所以設(shè)一長(zhǎng)36的整型數(shù)組，前10個(gè)分量存放數(shù)字字符出現(xiàn)的次數(shù)，余下存放字母出現(xiàn)的次數(shù)。從字符串中讀出數(shù)字字符時(shí)，字符的ASCII代碼值減去數(shù)字字符 0的ASCII代碼值，得出其數(shù)值(0.9)，字母的ASCII代碼值減去字符A的ASCII代碼值加上10，存入其數(shù)組的對(duì)應(yīng)下標(biāo)分量中。遇其它符號(hào)不作處理，直至輸入字符串結(jié)束。算法描述void Count（） 是字符串輸入

28、結(jié)束標(biāo)志InvertStore(A); Ai+ = ch;m, 1.n 含有m*n 個(gè)整數(shù)。 寫一個(gè)算法判斷a中所有元素是否互不相同?輸出相關(guān)信息(yes/no)； 試分析算法的時(shí)間復(fù)雜度。題目分析判斷二維數(shù)組中元素是否互不相同，只有逐個(gè)比較,找到一對(duì)相等的元素，就可結(jié)論為不是互不相同。如何達(dá)到每個(gè)元素同其它元素比較一次且只一次？在當(dāng)前行，每個(gè)元素要同本行后面的元素比較一次（下面第一個(gè)循環(huán)控制變量p的for循環(huán)），然后同第i+1行及以后各行元素比較一次，這就是循環(huán)控制變量k和p的二層for循環(huán)。算法描述int JudgEqual(ing amn,int m,n) 算法討論對(duì)數(shù)組中元素各比較一次

29、，比較次數(shù)為n。最佳情況(已排好,正數(shù)在前,負(fù)數(shù)在后)不發(fā)生交換，最差情況(負(fù)數(shù)均在正數(shù)前面)發(fā)生n/2次交換。用類c編寫，數(shù)組界偶是0.n-1?？臻g復(fù)雜度為O(1).第5章 樹和二叉樹1選擇題（1）把一棵樹轉(zhuǎn)換為二叉樹后，這棵二叉樹的形態(tài)是（ ）。 A唯一的 有多種C有多種，但根結(jié)點(diǎn)都沒有左孩子 有多種，但根結(jié)點(diǎn)都沒有右孩子答案：A 解釋：因?yàn)槎鏄溆凶蠛⒆?、右孩子之分，故一棵樹轉(zhuǎn)換為二叉樹后，這棵二叉樹的形態(tài)是唯一的。（2）由3個(gè)結(jié)點(diǎn)可以構(gòu)造出多少種不同的二叉樹？（ ）A2 B3 C4 D5 答案：D解釋：五種情況如下：（3）一棵完全二叉樹上有1001個(gè)結(jié)點(diǎn)，其中葉子結(jié)點(diǎn)的個(gè)數(shù)是（ ）。A

30、250 B 500 C254 D501 答案：D解釋：設(shè)度為0結(jié)點(diǎn)（葉子結(jié)點(diǎn)）個(gè)數(shù)為A，度為1的結(jié)點(diǎn)個(gè)數(shù)為B，度為2的結(jié)點(diǎn)個(gè)數(shù)為C，有A=C+1，A+B+C=1001，可得2C+B=1000，由完全二叉樹的性質(zhì)可得B=0或1，又因?yàn)镃為整數(shù)，所以B=0，C=500，A=501，即有501個(gè)葉子結(jié)點(diǎn)。（4）一個(gè)具有1025個(gè)結(jié)點(diǎn)的二叉樹的高h(yuǎn)為（ ）。A11 B10 C11至1025之間 D10至1024之間答案：C解釋：若每層僅有一個(gè)結(jié)點(diǎn)，則樹高h(yuǎn)為1025；且其最小樹高為?log21025?+?1=11，即h在11至1025之間。（5）深度為h的滿m叉樹的第k層有（ ）個(gè)結(jié)點(diǎn)。(1=<

31、k=<h) Amk-1 Bmk-1 Cmh-1 Dmh-1答案：A解釋：深度為h的滿m叉樹共有mh-1個(gè)結(jié)點(diǎn)，第k層有mk-1個(gè)結(jié)點(diǎn)。（6）利用二叉鏈表存儲(chǔ)樹，則根結(jié)點(diǎn)的右指針是（ ）。A指向最左孩子 B指向最右孩子 C空 D非空答案：C解釋：利用二叉鏈表存儲(chǔ)樹時(shí)，右指針指向兄弟結(jié)點(diǎn)，因?yàn)楦?jié)點(diǎn)沒有兄弟結(jié)點(diǎn)，故根節(jié)點(diǎn)的右指針指向空。（7）對(duì)二叉樹的結(jié)點(diǎn)從1開始進(jìn)行連續(xù)編號(hào)，要求每個(gè)結(jié)點(diǎn)的編號(hào)大于其左、右孩子的編號(hào)，同一結(jié)點(diǎn)的左右孩子中，其左孩子的編號(hào)小于其右孩子的編號(hào)，可采用（ ）遍歷實(shí)現(xiàn)編號(hào)。A先序 B. 中序 C. 后序 D. 從根開始按層次遍歷答案：C解釋：根據(jù)題意可知按照先左孩子

32、、再右孩子、最后雙親結(jié)點(diǎn)的順序遍歷二叉樹，即后序遍歷二叉樹。（8）若二叉樹采用二叉鏈表存儲(chǔ)結(jié)構(gòu)，要交換其所有分支結(jié)點(diǎn)左、右子樹的位置，利用（ ）遍歷方法最合適。A前序 B中序 C后序 D按層次答案：C解釋：后續(xù)遍歷和層次遍歷均可實(shí)現(xiàn)左右子樹的交換，不過層次遍歷的實(shí)現(xiàn)消耗比后續(xù)大，后序遍歷方法最合適。（9）在下列存儲(chǔ)形式中，（ ）不是樹的存儲(chǔ)形式？A雙親表示法 B孩子鏈表表示法 C孩子兄弟表示法 D順序存儲(chǔ)表示法答案：D解釋：樹的存儲(chǔ)結(jié)構(gòu)有三種：雙親表示法、孩子表示法、孩子兄弟表示法，其中孩子兄弟表示法是常用的表示法，任意一棵樹都能通過孩子兄弟表示法轉(zhuǎn)換為二叉樹進(jìn)行存儲(chǔ)。（10）一棵非空的二叉樹

33、的先序遍歷序列與后序遍歷序列正好相反，則該二叉樹一定滿足（ ）。A所有的結(jié)點(diǎn)均無左孩子 B所有的結(jié)點(diǎn)均無右孩子C只有一個(gè)葉子結(jié)點(diǎn) D是任意一棵二叉樹答案：C解釋：因?yàn)橄刃虮闅v結(jié)果是“中左右”，后序遍歷結(jié)果是“左右中”，當(dāng)沒有左子樹時(shí)，就是“中右”和“右中”；當(dāng)沒有右子樹時(shí)，就是“中左”和“左中”。則所有的結(jié)點(diǎn)均無左孩子或所有的結(jié)點(diǎn)均無右孩子均可，所以A、B不能選，又所有的結(jié)點(diǎn)均無左孩子與所有的結(jié)點(diǎn)均無右孩子時(shí)，均只有一個(gè)葉子結(jié)點(diǎn)，故選C。（11）設(shè)哈夫曼樹中有199個(gè)結(jié)點(diǎn)，則該哈夫曼樹中有（ ）個(gè)葉子結(jié)點(diǎn)。A99B100C101D102答案：B解釋：在哈夫曼樹中沒有度為1的結(jié)點(diǎn)，只有度為0（葉

34、子結(jié)點(diǎn)）和度為2的結(jié)點(diǎn)。設(shè)葉子結(jié)點(diǎn)的個(gè)數(shù)為n0，度為2的結(jié)點(diǎn)的個(gè)數(shù)為n2，由二叉樹的性質(zhì)n0=n2+1，則總結(jié)點(diǎn)數(shù)n= n0+n2=2*n0-1，得到n0=100。（12）若X是二叉中序線索樹中一個(gè)有左孩子的結(jié)點(diǎn)，且X不為根，則X的前驅(qū)為（ ）。AX的雙親 BX的右子樹中最左的結(jié)點(diǎn) CX的左子樹中最右結(jié)點(diǎn) DX的左子樹中最右葉結(jié)點(diǎn)答案：C（13）引入二叉線索樹的目的是（ ）。A加快查找結(jié)點(diǎn)的前驅(qū)或后繼的速度 B為了能在二叉樹中方便的進(jìn)行插入與刪除C為了能方便的找到雙親 D使二叉樹的遍歷結(jié)果唯一答案：A（14）設(shè)F是一個(gè)森林，B是由F變換得的二叉樹。若F中有n個(gè)非終端結(jié)點(diǎn)，則B中右指針域?yàn)榭盏慕Y(jié)

35、點(diǎn)有（ ）個(gè)。An?1BnCn + 1Dn + 2答案：C（15）n（n2）個(gè)權(quán)值均不相同的字符構(gòu)成哈夫曼樹，關(guān)于該樹的敘述中，錯(cuò)誤的是（?）。A該樹一定是一棵完全二叉樹B樹中一定沒有度為1的結(jié)點(diǎn)C樹中兩個(gè)權(quán)值最小的結(jié)點(diǎn)一定是兄弟結(jié)點(diǎn)D樹中任一非葉結(jié)點(diǎn)的權(quán)值一定不小于下一層任一結(jié)點(diǎn)的權(quán)值答案：A解釋：哈夫曼樹的構(gòu)造過程是每次都選取權(quán)值最小的樹作為左右子樹構(gòu)造一棵新的二叉樹，所以樹中一定沒有度為1的結(jié)點(diǎn)、兩個(gè)權(quán)值最小的結(jié)點(diǎn)一定是兄弟結(jié)點(diǎn)、任一非葉結(jié)點(diǎn)的權(quán)值一定不小于下一層任一結(jié)點(diǎn)的權(quán)值。2應(yīng)用題（1）試找出滿足下列條件的二叉樹 先序序列與后序序列相同 中序序列與后序序列相同 先序序列與中序序列相

36、同 中序序列與層次遍歷序列相同答案：先序遍歷二叉樹的順序是“根左子樹右子樹”，中序遍歷“左子樹根右子樹”，后序遍歷順序是：“左子樹右子樹根，根據(jù)以上原則有 或?yàn)榭諛?，或?yàn)橹挥懈Y(jié)點(diǎn)的二叉樹? 或?yàn)榭諛洌驗(yàn)槿我唤Y(jié)點(diǎn)至多只有左子樹的二叉樹? 或?yàn)榭諛?，或?yàn)槿我唤Y(jié)點(diǎn)至多只有右子樹的二叉樹 或?yàn)榭諛洌驗(yàn)槿我唤Y(jié)點(diǎn)至多只有右子樹的二叉樹（2）設(shè)一棵二叉樹的先序序列： A B D F C E G H ，中序序列： B F D A G E H C畫出這棵二叉樹。畫出這棵二叉樹的后序線索樹。將這棵二叉樹轉(zhuǎn)換成對(duì)應(yīng)的樹（或森林）。答案：ABFDCEHG? （3） 假設(shè)用于通信的電文僅由8個(gè)字母組成，字母在電文

37、中出現(xiàn)的頻率分別為，。 試為這8個(gè)字母設(shè)計(jì)赫夫曼編碼。 試設(shè)計(jì)另一種由二進(jìn)制表示的等長(zhǎng)編碼方案。 對(duì)于上述實(shí)例，比較兩種方案的優(yōu)缺點(diǎn)。答案：方案1；哈夫曼編碼先將概率放大100倍，以方便構(gòu)造哈夫曼樹。 w=7,19,2,6,32,3,21,10，按哈夫曼規(guī)則：【（2,3），6, (7,10)】, 19, 21, 32（100）（40） （60）19 21 32 （28）（17） （11） 7 10 6 （5） 2 3 0 1 0 1 0 119 21 32 0 10 1 0 17 10 6 0 12 3方案比較：字母編號(hào)對(duì)應(yīng)編碼出現(xiàn)頻率10002001301040115100610171108

38、111字母編號(hào)對(duì)應(yīng)編碼出現(xiàn)頻率111002003111104111051061111170181101方案1的WPL2+4+5+=+=方案2的WPL3+=3結(jié)論：哈夫曼編碼優(yōu)于等長(zhǎng)二進(jìn)制編碼?（4）已知下列字符A、B、C、D、E、F、G的權(quán)值分別為3、12、7、4、2、8，11，試填寫出其對(duì)應(yīng)哈夫曼樹HT的存儲(chǔ)結(jié)構(gòu)的初態(tài)和終態(tài)。答案：初態(tài):weightparentlchildrchild13000212000370004400052000680007110008000900010000110001200013000終態(tài)：weightparentlchildrchild1380021212003

39、71000449005280068100071111008595199114810151236112013971227132101347011123算法設(shè)計(jì)題以二叉鏈表作為二叉樹的存儲(chǔ)結(jié)構(gòu)，編寫以下算法：（1）統(tǒng)計(jì)二叉樹的葉結(jié)點(diǎn)個(gè)數(shù)。題目分析如果二叉樹為空，返回0，如果二叉樹不為空且左右子樹為空，返回1，如果二叉樹不為空，且左右子樹不同時(shí)為空，返回左子樹中葉子節(jié)點(diǎn)個(gè)數(shù)加上右子樹中葉子節(jié)點(diǎn)個(gè)數(shù)。算法描述 int LeafNodeCount(BiTree T)if(T=NULL)return 0; c; 隊(duì)列 C. 樹 D圖 答案：B解釋：廣度優(yōu)先遍歷通常借助隊(duì)列來實(shí)現(xiàn)算法，深度優(yōu)先遍歷通常借助棧

40、來實(shí)現(xiàn)算法。（9）用鄰接表表示圖進(jìn)行深度優(yōu)先遍歷時(shí)，通常借助（ ）來實(shí)現(xiàn)算法。A棧 B. 隊(duì)列 C. 樹 D圖 答案：A解釋：廣度優(yōu)先遍歷通常借助隊(duì)列來實(shí)現(xiàn)算法，深度優(yōu)先遍歷通常借助棧來實(shí)現(xiàn)算法。（10）深度優(yōu)先遍歷類似于二叉樹的（ ）。A先序遍歷 B中序遍歷 C后序遍歷 D層次遍歷答案：A（11）廣度優(yōu)先遍歷類似于二叉樹的（ ）。A先序遍歷 B中序遍歷 C后序遍歷 D層次遍歷答案：D（12）圖的BFS生成樹的樹高比DFS生成樹的樹高（ ）。A小 B相等 C小或相等 D大或相等答案：C解釋：對(duì)于一些特殊的圖，比如只有一個(gè)頂點(diǎn)的圖，其BFS生成樹的樹高和DFS生成樹的樹高相等。一般的圖，根據(jù)圖的

41、BFS生成樹和DFS樹的算法思想，BFS生成樹的樹高比DFS生成樹的樹高小。（13）已知圖的鄰接矩陣如圖所示，則從頂點(diǎn)v0出發(fā)按深度優(yōu)先遍歷的結(jié)果是（ ）。 ? 圖 鄰接矩陣（14）已知圖的鄰接表如圖所示，則從頂點(diǎn)v0出發(fā)按廣度優(yōu)先遍歷的結(jié)果是（ ），按深度優(yōu)先遍歷的結(jié)果是（ ）。圖 鄰接表A0 1 3 2B0 2 3 1C0 3 2 1D0 1 2 3答案：D、D（15）下面（ ）方法可以判斷出一個(gè)有向圖是否有環(huán)。A深度優(yōu)先遍歷 B拓?fù)渑判?C求最短路徑 D求關(guān)鍵路徑答案：B2應(yīng)用題（1）已知圖所示的有向圖，請(qǐng)給出： 每個(gè)頂點(diǎn)的入度和出度； 鄰接矩陣； 鄰接表； 逆鄰接表。 ? 圖 有向圖

42、圖 無向網(wǎng)答案：（2）已知如圖所示的無向網(wǎng)，請(qǐng)給出： 鄰接矩陣； 鄰接表； 最小生成樹答案： ab4c3ba4c5d5e9ca3b5d5h5db5c5e7f6g5h4eb9d7f3fd6e3g2gd5f2h6（3）已知圖的鄰接矩陣如圖所示。試分別畫出自頂點(diǎn)1出發(fā)進(jìn)行遍歷所得的深度優(yōu)先生成樹和廣度優(yōu)先生成樹。圖 鄰接矩陣（4）有向網(wǎng)如圖所示，試用迪杰斯特拉算法求出從頂點(diǎn)a到其他各頂點(diǎn)間的最短路徑，完成表。? 圖 鄰接矩陣 圖 有向網(wǎng)表D終點(diǎn)i=1i=2i=3i=4i=5i=6b15(a,b)15(a,b)15(a,b)15(a,b)15(a,b)15(a,b)c2(a,c)d12(a,d)12(

43、a,d)11(a,c,f,d)11(a,c,f,d)e10(a,c,e)10(a,c,e)f6(a,c,f)g16(a,c,f,g)16(a,c,f,g)14(a,c,f,d,g)S終點(diǎn)集a,ca,c,fa,c,f,ea,c,f,e,da,c,f,e,d,ga,c,f,e,d,g,b（5）試對(duì)圖所示的AOE-網(wǎng)： 求這個(gè)工程最早可能在什么時(shí)間結(jié)束； 求每個(gè)活動(dòng)的最早開始時(shí)間和最遲開始時(shí)間； 確定哪些活動(dòng)是關(guān)鍵活動(dòng)圖 AOE-網(wǎng)答案：按拓?fù)溆行虻捻樞蛴?jì)算各個(gè)頂點(diǎn)的最早可能開始時(shí)間Ve和最遲允許開始時(shí)間Vl。然后再計(jì)算各個(gè)活動(dòng)的最早可能開始時(shí)間e和最遲允許開始時(shí)間l，根據(jù)l - e = 0? 來確定關(guān)鍵活動(dòng)，從而確定關(guān)鍵路徑。1 ? 2 ?3 ? 4 ?5 ?6 ?Ve019152938 43Vl01915373843<1, 2><1, 3><3, 2><2, 4><2, 5><3, 5><4, 6><5, 6>e00151919152938l170152719273738