數(shù)據(jù)結(jié)構(gòu)課后答案

第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è)格局（狀態(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(chǎn)’，‘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)可以看作是從具體問題抽象出來的數(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è)直接前趨和直接后繼。學(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)行排列，將組成一個(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ǔ)空間中，而鏈?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．?dāng)?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．?dāng)?shù)據(jù)元素所包含的數(shù)據(jù)項(xiàng)的個(gè)數(shù)要相等答案：B（4）以下說法正確的是（）。A．?dāng)?shù)據(jù)元素是數(shù)據(jù)的最小單位B．?dāng)?shù)據(jù)項(xiàng)是數(shù)據(jù)的基本單位C．?dāng)?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ī)的配置 D．A和B答案：D解釋：算法的時(shí)間復(fù)雜度不僅與問題的規(guī)模有關(guā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(y>0)if(x>100){x=x-10;y--;}elsex++;答案：O(1)解釋：程序的執(zhí)行次數(shù)為常數(shù)階。（2）for(i=0;i<n;i++)for(j=0;j<m;j++)a[i][j]=0;答案：O(m*n)解釋：語句a[i][j]=0;的執(zhí)行次數(shù)為m*n。（3）s=0;fori=0;i<n;i++)for(j=0;j<n;j++)s+=B[i][j];sum=s;答案：O(n2)解釋：語句s+=B[i][j];的執(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;//n>1y=0;while(x≥(y+1)*(y+1))y++;答案：O()解釋：語句y++;的執(zhí)行次數(shù)為

。第2章線性表1．選擇題（1）順序表中第一個(gè)元素的存儲(chǔ)地址是100，每個(gè)元素的長(zhǎng)度為2，則第5個(gè)元素的地址是（）。A．110B．108C．100D．120答案：B解釋：順序表中的數(shù)據(jù)連續(xù)存儲(chǔ)，所以第5個(gè)元素的地址為：100+2*4=108。（2）在n個(gè)結(jié)點(diǎn)的順序表中，算法的時(shí)間復(fù)雜度是O(1)的操作是（）。A．訪問第i個(gè)結(jié)點(diǎn)（1≤i≤n）和求第i個(gè)結(jié)點(diǎn)的直接前驅(qū)（2≤i≤n）B．在第i個(gè)結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)（1≤i≤n）C．刪除第i個(gè)結(jié)點(diǎn)（1≤i≤n）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)，訪問第i個(gè)結(jié)點(diǎn)和求第i個(gè)結(jié)點(diǎn)的直接前驅(qū)都可以直接通過數(shù)組的下標(biāo)直接定位，時(shí)間復(fù)雜度是O(1)。（3）向一個(gè)有127個(gè)元素的順序表中插入一個(gè)新元素并保持原來順序不變，平均要移動(dòng)的元素個(gè)數(shù)為（）。A．8B．63.5C．63D．7答案：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．大于1B．等于1C．小于1D．不能確定答案：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ù)是（）。A．nB．2n-1C．2nD．n-1答案：A解釋：當(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+1C．n-i-1D．I答案：B(10)線性表L=(a1，a2,……an)，下列說法正確的是（）。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ù)雜度是（）。A．O(1)B．O(n)C．O(n2)D．O(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)以下說法錯(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ī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)在雙向鏈表存儲(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->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->next;p->next->prior=q;p->next=q;D．q->prior=p;q->next=p->next;p->next=q;p->next->prior=q;答案：C第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，5D．2，3，5，4，1答案：C解釋：棧是后進(jìn)先出的線性表，不難發(fā)現(xiàn)C選項(xiàng)中元素1比元素2先出棧，違背了棧的后進(jìn)先出原則，所以不可能出現(xiàn)C選項(xiàng)所示的情況。（2）若已知一個(gè)棧的入棧序列是1，2，3，…，n，其輸出序列為p1，p2，p3，…，pn，若p1=n，則pi為（）。A．iB．n-iC．n-i+1D．不確定答案：C解釋：棧是后進(jìn)先出的線性表，一個(gè)棧的入棧序列是1，2，3，…，n，而輸出序列的第一個(gè)元素為n，說明1，2，3，…，n一次性全部進(jìn)棧，再進(jìn)行輸出，所以p1=n，p2=n-1，…，pi=n-i+1。（3）數(shù)組Ｑ［ｎ］用來表示一個(gè)循環(huán)隊(duì)列，ｆ為當(dāng)前隊(duì)列頭元素的前一位置，ｒ?yàn)殛?duì)尾元素的位置，假定隊(duì)列中元素的個(gè)數(shù)小于ｎ，計(jì)算隊(duì)列中元素個(gè)數(shù)的公式為（）。A．r-fB．(n+f-r)%nC．n+r-fD．（n+r-f)%n答案：D解釋：對(duì)于非循環(huán)隊(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解釋：x=top->data將結(jié)點(diǎn)的值保存到x中，top=top->link棧頂指針指向棧頂下一結(jié)點(diǎn)，即摘除棧頂結(jié)點(diǎn)。（5）設(shè)有一個(gè)遞歸算法如下

intfact(intn){

//n大于等于0

if(n<=0)return1;

elsereturnn*fact(n-1);

}則計(jì)算fact(n)需要調(diào)用該函數(shù)的次數(shù)為（）。

A．

n+1

B．

n-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ī)間速度不匹配問題，通常設(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ū)問題應(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)該是（）。A．2B．3C．4D．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è)棧以向量V[1..n]存儲(chǔ)，初始棧頂指針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)棧，又因?yàn)樵卮鎯?chǔ)在向量空間V[1..n]中，所以進(jìn)棧時(shí)top指針先下移變?yōu)閚，之后將元素x存儲(chǔ)在V[n]。（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ù)組A[0..m]中，則入隊(duì)時(shí)的操作為（）。A.rear=rear+1B.rear=(rear+1)%(m-1)C.rear=(rear+1)%mD.rear=(rear+1)%(m+1)答案：D解釋：數(shù)組A[0..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解釋：最大容量為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.迭代部分D.終止條件和迭代部分答案：B第4章串、數(shù)組和廣義表1．選擇題（1）串是一種特殊的線性表，其特殊性體現(xiàn)在（）。A．可以順序存儲(chǔ)B．?dāng)?shù)據(jù)元素是一個(gè)字符C．可以鏈?zhǔn)酱鎯?chǔ)D．?dāng)?shù)據(jù)元素可以是多個(gè)字符若答案：B（2）串下面關(guān)于串的的敘述中，（）是不正確的？A．串是字符的有限序列B．空串是由空格構(gòu)成的串C．模式匹配是串的一種重要運(yùn)算D．串既可以采用順序存儲(chǔ)，也可以采用鏈?zhǔn)酱鎯?chǔ)答案：B解釋：空格常常是串的字符集合中的一個(gè)元素，有一個(gè)或多個(gè)空格組成的串成為空格串，零個(gè)字符的串成為空串，其長(zhǎng)度為零。（3）串“ababaaababaa”的next數(shù)組為（）。A．012345678999B．012121111212C．011234223456D．0123012322345答案：C（4）串“ababaabab”的nextval為（）。A．010104101B．010102101C．010100011D．010101011答案：A（5）串的長(zhǎng)度是指（）。A．串中所含不同字母的個(gè)數(shù)B．串中所含字符的個(gè)數(shù)C．串中所含不同字符的個(gè)數(shù)D．串中所含非空格字符的個(gè)數(shù)答案：B解釋：串中字符的數(shù)目稱為串的長(zhǎng)度。（6）假設(shè)以行序?yàn)橹餍虼鎯?chǔ)二維數(shù)組A=array[1..100,1..100]，設(shè)每個(gè)數(shù)據(jù)元素占2個(gè)存儲(chǔ)單元，基地址為10，則LOC[5,5]=（）。A．808B．818C．1010D．1020答案：B解釋：以行序?yàn)橹?，則LOC[5,5]=[（5-1）*100+（5-1）]*2+10=818。（7）設(shè)有數(shù)組A[i,j]，數(shù)組的每個(gè)元素長(zhǎng)度為3字節(jié)，i的值為1到8，j的值為1到10，數(shù)組從內(nèi)存首地址BA開始順序存放，當(dāng)用以列為主存放時(shí)，元素A[5,8]的存儲(chǔ)首地址為（）。A．BA+141B．BA+180C．BA+222D．BA+225答案：B解釋：以列序?yàn)橹?，則LOC[5,8]=[（8-1）*8+（5-1）]*3+BA=BA+180。（8）設(shè)有一個(gè)10階的對(duì)稱矩陣A，采用壓縮存儲(chǔ)方式，以行序?yàn)橹鞔鎯?chǔ)，a11為第一元素，其存儲(chǔ)地址為1，每個(gè)元素占一個(gè)地址空間，則a85的地址為（）。A．13B．32C．33D．40答案：C（9）若對(duì)n階對(duì)稱矩陣A以行序?yàn)橹餍蚍绞綄⑵湎氯切蔚脑?包括主對(duì)角線上所有元素)依次存放于一維數(shù)組B[1..(n(n+1))/2]中，則在B中確定aij（i<j）的位置k的關(guān)系為（）。A．i*(i-1)/2+jB．j*(j-1)/2+iC．i*(i+1)/2+jD．j*(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ǔ)，元素A[8,5]的起始地址與當(dāng)A按列先存儲(chǔ)時(shí)的元素（）的起始地址相同。設(shè)每個(gè)字符占一個(gè)字節(jié)。A．A[8,5]B．A[3,10]C.A[5,8]D．A[0,9]答案：B解釋：設(shè)數(shù)組從內(nèi)存首地址M開始順序存放，若數(shù)組按行先存儲(chǔ)，元素A[8,5]的起始地址為：M+[（8-0）*10+（5-1）]*1=M+84；若數(shù)組按列先存儲(chǔ)，易計(jì)算出元素A[3,10]的起始地址為：M+[（10-1）*9+（3-0）]*1=M+84。故選B。（11）設(shè)二維數(shù)組A[1..m，1..n]（即m行n列）按行存儲(chǔ)在數(shù)組B[1..m*n]中，則二維數(shù)組元素A[i,j]在一維數(shù)組B中的下標(biāo)為（）。A．(i-1)*n+jB．(i-1)*n+j-1C．i*(j-1)D．j*m+i-1答案：A解釋：特殊值法。取i=j=1，易知A[1,1]的的下標(biāo)為1，四個(gè)選項(xiàng)中僅有A選項(xiàng)能確定的值為1，故選A。（12）數(shù)組A[0..4,-1..-3,5..7]中含有元素的個(gè)數(shù)（）。A．55B．45C．36D．16答案：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)C．cD．d答案：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(Tail(A))))=(d)；Head(Tail(Head(Tail(Tail(A)))))=d。（14）廣義表((a,b,c,d))的表頭是（），表尾是（）。A．a(chǎn)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)度和深度分別為（）。A．1和1B．1和3C．1和2D．2和3答案：C解釋：廣義表的深度是指廣義表中展開后所含括號(hào)的層數(shù)，廣義表的長(zhǎng)度是指廣義表中所含元素的個(gè)數(shù)。根據(jù)定義易知L的長(zhǎng)度為1，深度為2。2．應(yīng)用題（1）已知模式串t=‘a(chǎn)bcaabbabcab’寫出用KMP法求得的每個(gè)字符對(duì)應(yīng)的next和nextval函數(shù)值。答案：模式串t的next和nextval值如下：j123456789101112t串a(chǎn)bcaabbabcabnext[j]011122312345nextval[j]011021301105（2）設(shè)目標(biāo)為t=“abcaabbabcabaacbacba”,模式為p=“abcabaa”=1\*GB3①計(jì)算模式p的naxtval函數(shù)值；=2\*GB3②不寫出算法,只畫出利用KMP算法進(jìn)行模式匹配時(shí)每一趟的匹配過程。答案：=1\*GB3①p的nextval函數(shù)值為0110132。（p的next函數(shù)值為0111232）。=2\*GB3②利用KMP(改進(jìn)的nextval)算法，每趟匹配過程如下：第一趟匹配：abcaabbabcabaacbacbaabcab(i=5,j=5)第二趟匹配：abcaabbabcabaacbacbaabc(i=7,j=3)第三趟匹配：abcaabbabcabaacbacbaa(i=7,j=1)第四趟匹配：abcaabbabcabaacbacba(成功)abcabaa(i=15,j=8)（3）數(shù)組A中，每個(gè)元素A[i,j]的長(zhǎng)度均為32個(gè)二進(jìn)位,行下標(biāo)從-1到9，列下標(biāo)從1到11，從首地址S開始連續(xù)存放主存儲(chǔ)器中，主存儲(chǔ)器字長(zhǎng)為16位。求：=1\*GB3①存放該數(shù)組所需多少單元？=2\*GB3②存放數(shù)組第4列所有元素至少需多少單元？=3\*GB3③數(shù)組按行存放時(shí)，元素A[7,4]的起始地址是多少？=4\*GB3④數(shù)組按列存放時(shí)，元素A[4,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（H（T（H（T（H（T（L）））））））第5章樹和二叉樹A．Ｂ．C．有多種，但根結(jié)點(diǎn)都沒有左孩子Ｄ．有多種，但根結(jié)點(diǎn)都沒有右孩子答案：A解釋：因?yàn)槎鏄溆凶蠛⒆?、右孩子之分，故?個(gè)結(jié)點(diǎn)可以構(gòu)造出多少種不同的二叉樹？（）A．2B．3C．4D．5答案：D一棵完全二叉樹上有1001個(gè)結(jié)點(diǎn)，其中葉子結(jié)點(diǎn)的個(gè)數(shù)是（）A．250B．500C．254D．501答案：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)。一個(gè)具有1025個(gè)結(jié)點(diǎn)的二叉樹的高h(yuǎn)為（）A．11B．10C．11至1025之間D．10至1024之間答案：C解釋：若每層僅有一個(gè)結(jié)點(diǎn)，則樹高h(yuǎn)為1025；且其最小樹高為

log21025

+

1=11，即h在11至1025之間。深度為h的滿m叉樹的第k層有（）個(gè)結(jié)點(diǎn)。(1=<k=<h)A．mk-1B．mk-1C．mh-1D．mh-1答案：A解釋：深度為h的滿m叉樹共有mh-1個(gè)結(jié)點(diǎn)，第k層有mk-1個(gè)結(jié)點(diǎn)。利用二叉鏈表存儲(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)的右指針指向空。對(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ù)題意可知按照先左孩子、再右孩子、最后雙親結(jié)點(diǎn)的順序遍歷二叉樹，即后序遍歷二叉樹。若二叉樹采用二叉鏈表存儲(chǔ)結(jié)構(gòu)，要交換其所有分支結(jié)點(diǎn)左、右子樹的位置，利用（）遍歷方法最合適。A．前序B．中序C．后序D．按層次答案：C解釋：后續(xù)遍歷和層次遍歷均可實(shí)現(xiàn)左右子樹的交換，不過層次遍歷的實(shí)現(xiàn)消耗比后續(xù)大，后序遍歷方法最合適。在下列存儲(chǔ)形式中，（）不是樹的存儲(chǔ)形式？A．雙親表示法B．孩子鏈表表示法C．孩子兄弟表示法D．順序存儲(chǔ)表示法答案：D解釋：樹的存儲(chǔ)結(jié)構(gòu)有三種：雙親表示法、孩子表示法、孩子兄弟表示法，其中孩子兄弟表示法是常用的表示法，任意一棵樹都能通過孩子兄弟表示法轉(zhuǎn)換為二叉樹進(jìn)行存儲(chǔ)。一棵非空的二叉樹的先序遍歷序列與后序遍歷序列正好相反，則該二叉樹一定滿足（）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)。A．99 B．100C．101 D．102答案：B解釋：在哈夫曼樹中沒有度為1的結(jié)點(diǎn)，只有度為0（葉子結(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。若X是二叉中序線索樹中一個(gè)有左孩子的結(jié)點(diǎn)，且X不為根，則X的前驅(qū)為（）A．X的雙親B．X的右子樹中最左的結(jié)點(diǎn)C．X的左子樹中最右結(jié)點(diǎn)D．X的左子樹中最右葉結(jié)點(diǎn)答案：C引入二叉線索樹的目的是（）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é)點(diǎn)有（）個(gè)。A．n?1 B．n C．n+1 D．n+2答案：C（15）n（n≥2）個(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試找出滿足下列條件的二叉樹=1\*GB3①先序序列與后序序列相同=2\*GB3②中序序列與后序序列相同=3\*GB3③先序序列與中序序列相同=4\*GB3④中序序列與層次遍歷序列相同先序遍歷二叉樹的順序是“根—左子樹—右子樹”，中序遍歷“左子樹—根—右子樹”，后序遍歷順序是：“左子樹—右子樹―根＂，根據(jù)以上原則有=1\*GB3①或?yàn)榭諛?，或?yàn)橹挥懈Y(jié)點(diǎn)的二叉樹=2\*GB3②

或?yàn)榭諛?，或?yàn)槿我唤Y(jié)點(diǎn)至多只有左子樹的二叉樹．=3\*GB3③

或?yàn)榭諛?，或?yàn)槿我唤Y(jié)點(diǎn)至多只有右子樹的二叉樹．=4\*GB3④或?yàn)榭諛?，或?yàn)槿我唤Y(jié)點(diǎn)至多只有右子樹的二叉樹2設(shè)一棵二叉樹的先序序列：ABDFCEGH，中序序列：BFDAGEHC=1\*GB3①畫出這棵二叉樹。=2\*GB3②畫出這棵二叉樹的后序線索樹。=3\*GB3③將這棵二叉樹轉(zhuǎn)換成對(duì)應(yīng)的樹（或森林）。答案：ABABFD=3\*GB3③CEHG

=1\*GB3①=2\*GB3②3假設(shè)用于通信的電文僅由8個(gè)字母組成，字母在電文中出現(xiàn)的頻率分別為0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10。=1\*GB3①試為這8個(gè)字母設(shè)計(jì)赫夫曼編碼。=2\*GB3②試設(shè)計(jì)另一種由二進(jìn)制表示的等長(zhǎng)編碼方案。=3\*GB3③對(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）192132（28）（17）（11）7106（5）2301010101213210101106123方案比較：字母編號(hào)對(duì)應(yīng)編碼字母編號(hào)對(duì)應(yīng)編碼出現(xiàn)頻率10000.0720010.1930100.0240110.0651000.3261010.0371100.2181110.10字母編號(hào)對(duì)應(yīng)編碼出現(xiàn)頻率111000.072000.193111100.02411100.065100.326111110.037010.21811010.10方案1的WPL＝2(0.19+0.32+0.21)+4(0.07+0.06+0.10)+5(0.02+0.03)=1.44+0.92+0.25=2.61方案2的WPL＝3(0.19+0.32+0.21+0.07+0.06+0.10+0.02+0.03)=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)。答案：

weightparentlchildrchild13000212000370004400052000680007110008

0009

00010

00011

00012

00013

000初態(tài):

終態(tài)：

weightparentlchildrchild13800212120037100044900528006810007111100859519911481015123611201397122713210134701112第6章圖A．nB．n(n-1)C．n(n+1)D．n2n(n-1)。n個(gè)頂點(diǎn)的連通圖用鄰接距陣表示時(shí)，該距陣至少有個(gè)非零元素。A．nB．2(n-1)C．n/2D．n2G是一個(gè)非連通無向圖，共有28條邊，則該圖至少有個(gè)頂點(diǎn)。A．7B．8C．9D．10若從無向圖的任意一個(gè)頂點(diǎn)出發(fā)進(jìn)行一次深度優(yōu)先搜索可以訪問圖中所有的頂點(diǎn)，則該圖一定是圖。A．非連通B．連通C．強(qiáng)連通D．有向任意一個(gè)頂點(diǎn)出發(fā)有到各個(gè)頂點(diǎn)的路徑，所以該無向圖是連通圖。圖的BFS生成樹的樹高比DFS生成樹的樹高A．小B．相等C．小或相等D．大或相等對(duì)于一些特殊的圖，比如只有一個(gè)頂點(diǎn)的圖，其BFS生成樹的樹高和DFS生成樹的樹高相等。一般的圖，根據(jù)圖的BFS生成樹和DFS樹的算法思想，BFS生成樹的樹高比DFS生成樹的樹高小。（13）已知圖的鄰接矩陣如圖6.30所示，則從頂點(diǎn)v0出發(fā)按深度優(yōu)先遍歷的結(jié)果是（）。

圖6.30鄰接矩陣（14）已知圖的鄰接表如圖6.31所示，則從頂點(diǎn)v0出發(fā)按廣度優(yōu)先遍歷的結(jié)果是（），按深度優(yōu)先遍歷的結(jié)果是（）。圖6.31鄰接表A．0132 B．0231 C．0321 D．0123下面方法可以判斷出一個(gè)有向圖是否有環(huán)。A．深度優(yōu)先遍歷B．拓?fù)渑判駽．求最短路徑D．求關(guān)鍵路徑2．應(yīng)用題（1）已知圖6.32所示的有向圖，請(qǐng)給出：=1\*GB3①每個(gè)頂點(diǎn)的入度和出度；=2\*GB3②鄰接矩陣；=3\*GB3③鄰接表；=4\*GB3④逆鄰接表。

圖6.32有向圖圖6.33無向網(wǎng)答案：（2）已知如圖6.33所示的無向網(wǎng)，請(qǐng)給出：=1\*GB3①鄰接矩陣；=2\*GB3②鄰接表；=3\*GB3③最小生成樹答案：=1\*GB3①=3\*GB3③=2\*GB3②a→b4→c3b→a4→c5→d5→e9c→a3→b5→d5→h5d→b5→c5→e7→f6→g5→h4e→b9→d7→f3f→d6→e3→g2g→d5→f2→h6（3）已知圖的鄰接矩陣如圖6.34所示。試分別畫出自頂點(diǎn)1出發(fā)進(jìn)行遍歷所得的深度優(yōu)先生成樹和廣度優(yōu)先生成樹。圖6.28鄰接矩陣圖6.28鄰接矩陣（4）有向網(wǎng)如圖6.35所示，試用迪杰斯特拉算法求出從頂點(diǎn)a到其他各頂點(diǎn)間的最短路徑，完成表6.9。

圖6.34鄰接矩陣圖6.35有向網(wǎng)表6.9D終點(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(a,d)11(a,c,f,d)11(a,c,f,d)e∞10(a,c,e)10(a,c,e)f∞6(a,c,f)g∞∞16(a,c,f,g)16(a,c,f,g)14(a,c,f,d,g)S終點(diǎn)集{a,c}{a,c,f}{a,c,f,e}{a,c,f,e,d}{a,c,f,e,d,g}{a,c,f,e,d,g,b}（5）試對(duì)圖6.36所示的AOE-網(wǎng)：=1\*GB3①求這個(gè)工程最早可能在什么時(shí)間結(jié)束；=2\*GB3②求每個(gè)活動(dòng)的最早開始時(shí)間和最遲開始時(shí)間；=3\*GB3③確定哪些活動(dòng)是關(guān)鍵活動(dòng)圖6.36AOE-網(wǎng)圖6.36AOE-網(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)鍵路徑。123456Ve01915293843Vl01915373843<1,2><1,3><3,2><2,4><2,5><3,5><4,6><5,6>e00151919152938l170152719273738-e1700801280 此工程最早完成時(shí)間為43。關(guān)鍵路徑為<1,3><3,2><2,5><5,6>第7章查找對(duì)n個(gè)元素的表做順序查找時(shí)，若查找每個(gè)元素的概率相同，則平均查找長(zhǎng)度為。A．(n-1)/2B．n/2C．(n+1)/2D．n答案：C解釋：總查找次數(shù)N=1+2+3+…+n=n(n+1)/2，則平均查找長(zhǎng)度為N/n=(n+1)/2。適用于折半查找的表的存儲(chǔ)方式及元素排列要求為。A．鏈接方式存儲(chǔ)，元素?zé)o序B．鏈接方式存儲(chǔ)，元素有序C．順序方式存儲(chǔ)，元素?zé)o序D．順序方式存儲(chǔ)，元素有序答案：D解釋：折半查找要求線性表必須采用順序存儲(chǔ)結(jié)構(gòu)，而且表中元素按關(guān)鍵字有序排列。答案：C解釋：分塊查找的優(yōu)點(diǎn)是：在表中插入和刪除數(shù)據(jù)元素時(shí)，只要找到該元素對(duì)應(yīng)的塊，就可以在該塊內(nèi)進(jìn)行插入和刪除運(yùn)算。由于塊內(nèi)是無序的，故插入和刪除比較容易，無需進(jìn)行大量移動(dòng)。如果線性表既要快速查找又經(jīng)常動(dòng)態(tài)變化，則可采用分塊查找。折半查找有序表（4，6，10，12，20，30，50，70，88，100）。若查找表中元素58，則它將依次與表中比較大小，查找結(jié)果是失敗。A．20，70，30，50B．30，88，70，50C．20，50D．30，88，50答案：A解釋：表中共10個(gè)元素，第一次取(1+10)/2=5，與第五個(gè)元素20比較，58大于20，再取(6+10)/2=8，與第八個(gè)元素70比較，依次類推再與30、50比較，最終查找失敗。對(duì)22個(gè)記錄的有序表作折半查找，當(dāng)查找失敗時(shí)，至少需要比較次關(guān)鍵字。A．3B．4C．5D．6答案：B解釋：22個(gè)記錄的有序表，其折半查找的判定樹深度為

log222

+

1=5，且該判定樹不是滿二叉樹，即查找失敗時(shí)至多比較5次，至少比較4次。折半搜索與二叉排序樹的時(shí)間性能A．相同B．完全不同C．有時(shí)不相同D．?dāng)?shù)量級(jí)都是O(log2n)答案：C分別以下列序列構(gòu)造二叉排序樹，與用其它三個(gè)序列所構(gòu)造的結(jié)果不同的是A．（100，80，90，60，120，110，130）B．（100，120，110，130，80，60，90）C．（100，60，80，90，120，110，130）D．(100，80，60，90，120，130，110)答案：C解釋：A、B、C、D四個(gè)選項(xiàng)構(gòu)造二叉排序樹都以100為根，易知A、B、D三個(gè)序列中第一個(gè)比100小的關(guān)鍵字為80，即100的左孩子為80，而C選項(xiàng)中100的左孩子為60，故選C。在平衡二叉樹中插入一個(gè)結(jié)點(diǎn)后造成了不平衡，設(shè)最低的不平衡結(jié)點(diǎn)為A，并已知A的左孩子的平衡因子為0右孩子的平衡因子為1，則應(yīng)作型調(diào)整以使其平衡。A．LLB．LRC．RLD．RR答案：C下列關(guān)于m階B-樹的說法錯(cuò)誤的是A．根結(jié)點(diǎn)至多有m棵子樹B．所有葉子都在同一層次上C．非葉結(jié)點(diǎn)至少有m/2(m為偶數(shù))或m/2+1（m為奇數(shù)）棵子樹D．根結(jié)點(diǎn)中的數(shù)據(jù)是有序的答案：D下面關(guān)于B-和B+樹的敘述中，不正確的是A．B-樹和B+樹都是平衡的多叉樹B．B-樹和B+樹都可用于文件的索引結(jié)構(gòu)C．B-樹和B+樹都能有效地支持順序檢索D．B-樹和B+樹都能有效地支持隨機(jī)檢索答案：Cm階B-樹是一棵A．m叉排序樹B．m叉平衡排序樹C．m-1叉平衡排序樹D．m+1叉平衡排序樹答案：B下面關(guān)于哈希查找的說法，正確的是A．哈希函數(shù)構(gòu)造的越復(fù)雜越好，因?yàn)檫@樣隨機(jī)性好，沖突小B．除留余數(shù)法是所有哈希函數(shù)中最好的C．不存在特別好與壞的哈希函數(shù)，要視情況而定D．哈希表的平均查找長(zhǎng)度有時(shí)也和記錄總數(shù)有關(guān)答案：C設(shè)哈希表長(zhǎng)為14，哈希函數(shù)是H(key)=key%11，表中已有數(shù)據(jù)的關(guān)鍵字為15，38，61，84共四個(gè)，現(xiàn)要將關(guān)鍵字為49的元素加到表中，用二次探測(cè)法解決沖突，則放入的位置是用二次探測(cè)法解決沖突得到新地址為6，仍沖突，再用用二次探測(cè)法解決沖突，得到新地址為4，仍沖突，再用用二次探測(cè)法解決沖突，得到新地址為9，不沖突，即將關(guān)鍵字49放入位置9。()。A．不一定都是同義詞B．一定都是同義詞C．一定都不是同義詞D．都相同答案：A解釋：所探測(cè)的這些關(guān)鍵字可能是在處理其它關(guān)鍵字沖突過程中放入該位置的。2．應(yīng)用題假定對(duì)有序表：（3，4，5，7，24，30，42，54，63，72，87，95）進(jìn)行折半查找，試回答下列問題：=1\*GB3①畫出描述折半查找過程的判定樹；=2\*GB3②若查找元素54，需依次與哪些元素比較？=3\*GB3③若查找元素90，需依次與哪些元素比較？=4\*GB3④假定每個(gè)元素的查找概率相等，求查找成功時(shí)的平均查找長(zhǎng)度。答案：=1\*GB3①先畫出判定樹如下（注：mid=(1+12)/2=6）：30563374287424547295=2\*GB3②查找元素54，需依次與30,63,42,54元素比較；=3\*GB3③查找元素90，需依次與30,63,87,95元素比較；=4\*GB3④求ASL之前，需要統(tǒng)計(jì)每個(gè)元素的查找次數(shù)。判定樹的前3層共查找1＋2×2＋4×3=17次；但最后一層未滿，不能用8×4，只能用5×4=20次，所以ASL＝1/12（17＋20）＝37/12≈3.08在一棵空的二叉排序樹中依次插入關(guān)鍵字序列為12，7，17，11，16，2，13，9，21，4，請(qǐng)畫出所得到的二叉排序樹。 答案：121721116214913驗(yàn)算方法：用中序遍歷應(yīng)得到排序結(jié)果：2,4,7,9,11,12,13,16,17,21已知如下所示長(zhǎng)度為12的表：（Jan,Feb,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,Dec）=1\*GB3①試按表中元素的順序依次插入一棵初始為空的二叉排序樹，畫出插入完成之后的二叉排序樹，并求其在等概率的情況下查找成功的平均查找長(zhǎng)度。=2\*GB3②若對(duì)表中元素先進(jìn)行排序構(gòu)成有序表，求在等概率的情況下對(duì)此有序表進(jìn)行折半查找時(shí)查找成功的平均查找長(zhǎng)度。=3\*GB3③按表中元素順序構(gòu)造一棵平衡二叉排序樹，并求其在等概率的情況下查找成功的平均查找長(zhǎng)度。答案：對(duì)圖7.31所示的3階B-樹，依次執(zhí)行下列操作，畫出各步操作的結(jié)果。=1\*GB3①插入90=2\*GB3②插入25=3\*GB3③插入45=4\*GB3④刪除60圖7.313圖7.313階B-樹設(shè)哈希表的地址范圍為0～17，哈希函數(shù)為：H（key）=key%16。用線性探測(cè)法處理沖突，輸入關(guān)鍵字序列：（10，24，32，17，31，30，46，47，40，63，49），構(gòu)造哈希表，試回答下列問題：=1\*GB3①畫出哈希表的示意圖；=2\*GB3②若查找關(guān)鍵字63，需要依次與哪些關(guān)鍵字進(jìn)行比較？=3\*GB3③若查找關(guān)鍵字60，需要依次與哪些關(guān)鍵字比較？=4\*GB3④假定每個(gè)關(guān)鍵字的查找概率相等，求查找成功時(shí)的平均查找長(zhǎng)度。答案：=1\*GB3①畫表如下：012345678910111213141516173217634924401030314647=2\*GB3②查找63,首先要與H(63)=63%16=15號(hào)單元內(nèi)容比較，即63與31比較,不匹配;然后順移，與46,47,32,17,63相比，一共比較了6次！=3\*GB3③查找60,首先要與H(60)=60%16=12號(hào)單元內(nèi)容比較，但因?yàn)?2號(hào)單元為空（應(yīng)當(dāng)有空標(biāo)記），所以應(yīng)當(dāng)只比較這一次即可。=4\*GB3④對(duì)于黑色數(shù)據(jù)元素，各比較1次；共6次；對(duì)紅色元素則各不相同，要統(tǒng)計(jì)移位的位數(shù)?！?3”需要6次，“49”需要3次，“40”需要2次，“46”需要3次，“47”需要3次，所以ASL=1/11（6＋2＋3×3+6）＝23/11設(shè)有一組關(guān)鍵字（9，01，23，14，55，20，84，27），采用哈希函數(shù)：H（key）=key%7，表長(zhǎng)為10，用開放地址法的二次探測(cè)法處理沖突。要求：對(duì)該關(guān)鍵字序列構(gòu)造哈希表，并計(jì)算查找成功的平均查找長(zhǎng)度。答案：散列地址0123456789關(guān)鍵字14192384275520

比較次數(shù)11123412

平均查找長(zhǎng)度：ASLsucc=（1+1+1+2+3+4+1+2）/8=15/8以關(guān)鍵字27為例：H（27）=27%7=6（沖突）H1=（6+1）%10=7（沖突）H2=（6+22）%10=0（沖突）H3=（6+33）%10=5所以比較了4次。設(shè)哈希函數(shù)H（K）=3Kmod11，哈希地址空間為0～10，對(duì)關(guān)鍵字序列（32，13，49，24，38，21，4，12），按下述兩種解決沖突的方法構(gòu)造哈希表，并分別求出等概率下查找成功時(shí)和查找失敗時(shí)的平均查找長(zhǎng)度ASLsucc和ASLunsucc。=1\*GB3①線性探測(cè)法；=2\*GB3②鏈地址法。答案：=1\*GB3①散列地址012345678910關(guān)鍵字

4

12493813243221

比較次數(shù)

1

1121212

ASLsucc=（1+1+1+2+1+2+1+2）/8=11/8ASLunsucc=（1+2+1+8+7+6+5+4+3+2+1）/11=40/11=2\*GB3②ASLsucc=（1*5+2*3）/8=11/8ASLunsucc=（1+2+1+2+3+1+3+1+3+1+1）/11=19/11第8章排序從未排序序列中依次取出元素與已排序序列中的元素進(jìn)行比較，將其放入已排序序列的正確位置上的方法，這種排序方法稱為。A．歸并排序B．冒泡排序C．插入排序D．選擇排序答案：C從未排序序列中挑選元素，并將其依次放入已排序序列（初始時(shí)為空）的一端的方法，稱為。A．歸并排序B．冒泡排序C．插入排序D．選擇排序答案：D對(duì)n個(gè)不同的關(guān)鍵字由小到大進(jìn)行冒泡排序，在下列情況下比較的次數(shù)最多。A．從小到大排列好的B．從大到小排列好的C．元素?zé)o序D．元素基本有序答案：B解釋：對(duì)關(guān)鍵字進(jìn)行冒泡排序，關(guān)鍵字逆序時(shí)比較次數(shù)最多。對(duì)n個(gè)不同的排序碼進(jìn)行冒泡排序，在元素?zé)o序的情況下比較的次數(shù)最多為。A．n+1B．nC．n-1D．n(n-1)/2答案：D解釋：比較次數(shù)最多時(shí)，第一次比較n-1次，第二次比較n-2次……最后一次比較1次，即(n-1)+(n-2)+…+1=n(n-1)/2?？焖倥判蛟谙铝星闆r下最易發(fā)揮其長(zhǎng)處。A．被排序的數(shù)據(jù)中含有多個(gè)相同排序碼B．被排序的數(shù)據(jù)已基本有序C．被排序的數(shù)據(jù)完全無序D．被排序的數(shù)據(jù)中的最大值和最小值相差懸殊答案：C解釋：B選項(xiàng)是快速排序的最壞情況。對(duì)n個(gè)關(guān)鍵字作快速排序，在最壞情況下，算法的時(shí)間復(fù)雜度是。A．O(n)B．O(n2)C．O(nlog2n)D．O(n3)答案：B解釋：快速排序的平均時(shí)間復(fù)雜度為O(nlog2n)，但在最壞情況下，即關(guān)鍵字基本排好序的情況下，時(shí)間復(fù)雜度為O(n2)。若一組記錄的排序碼為（46,79，56，38，40，84），則利用快速排序的方法，以第一個(gè)記錄為基準(zhǔn)得到的一次劃分結(jié)果為。A．38，40，46，56，79，84B．40，38，46，79，56，84C．40，38，46，56，79，84D．40，38，46，84，56，79答案：C下列關(guān)鍵字序列中，是堆。A．16，72，31，23，94，53B．94，23，31，72，16，53C．16，53，23，94，31，72D．16，23，53，31，94，72答案：D解釋：D選項(xiàng)為小根堆堆是一種排序。A．插入B．選擇C．交換D．歸并答案：B堆的形狀是一棵。A．二叉排序樹B．滿二叉樹C．完全二叉樹D．平衡二叉樹答案：C若一組記錄的排序碼為（46，79，56，38，40，84），則利用堆排序的方法建立的初始堆為。A．79，46，56，38，40，84B．84，79，56，38，40，46C．84，79，56，46，40，38D．84，56，79，40，46，38答案：B下述幾種排序方法中，要求內(nèi)存最大的是。A．希爾排序B．快速排序C．歸并排序D．堆排序答案：C解釋：堆排序、希爾排序的空間復(fù)雜度為O(1)，快速排序的空間復(fù)雜度為O(log2n)，歸并排序的空間復(fù)雜度為O(n)。下述幾種排序方法中，是穩(wěn)定的排序方法。A．希爾排序B．快速排序C．歸并排序D．堆排序答案：C解釋：不穩(wěn)定排序有希爾排序、簡(jiǎn)單選擇排序、快速排序、堆排序；穩(wěn)定排序有直接插入排序、折半插入排序、冒泡排序、歸并排序、基數(shù)排序。數(shù)據(jù)表中有10000個(gè)元素，如果僅要求求出其中最大的10個(gè)元素，則采用()算法最節(jié)省時(shí)間。A．冒泡排序B．快速排序C．簡(jiǎn)單選擇排序D．堆排序答案：D下列排序算法中，不能保證每趟排序至少能將一個(gè)元素放到其最終的位置上。A．希爾排序B．快速排序C．冒泡排序D．堆排序答案：A解釋：快速排序的每趟排序能將作為樞軸的元素放到最終位置；冒泡排序的每趟排序能將最大或最小的元素放到最終位置；堆排序的每趟排序能將最大或最小的元素放到最終位置。2．應(yīng)用題設(shè)待排序的關(guān)鍵字序列為{12，2，16，30，28，10，16*，20，6，18}，試分別寫出使用以下排序方法，每趟排序結(jié)束后關(guān)鍵字序列的狀態(tài)。=1\*GB3①直接插入排序②折半插入排序=3\*GB3③希爾排序（增量選取5，3，1）=4\*GB3④冒泡排序=5\*GB3⑤快速排序=6\*GB3⑥簡(jiǎn)單選擇排序=7\*GB3⑦堆排序=8\*GB3⑧二路歸并排序答案：=1\*GB3①直接插入排序[212]1630281016*20618[21216]30281016*20618[2121630]281016*20618