數(shù)據(jù)結(jié)構(gòu)試題

一、單選題

數(shù)據(jù)結(jié)構(gòu)試題

12、若需要利用形參直接訪問實參，則應(yīng)把形參變量說明為（B）參數(shù)。A指針B引用C值D變量1、在數(shù)據(jù)結(jié)構(gòu)的討論中把數(shù)據(jù)結(jié)構(gòu)從邏輯上分為(C）

13、下面程序段的時間復(fù)雜度為C)AC

內(nèi)部結(jié)構(gòu)與外部結(jié)構(gòu)B線性結(jié)構(gòu)與非線性結(jié)構(gòu)D

靜態(tài)結(jié)構(gòu)與動態(tài)結(jié)構(gòu)緊湊結(jié)構(gòu)與非緊湊結(jié)構(gòu).

for（inti=0;i〈m；i++）for（intj=0;j<n；j++2、采用線性鏈表表示一個向量時，要求占用的存儲空間地址D）

［i］［j]=i*j;A

必須是連續(xù)的B部分地址必須是連續(xù)的

AO(m

）BO(n

)CODO（m+n）C一定是不連續(xù)的D可連續(xù)可不連續(xù)3、采用順序搜索方法查找長度為n的順序表時，搜索成功的平均搜索長度為(D

14、下面程序段的時間復(fù)雜度為（B）intf（unsignedintn）｛A

B

/2C（D(

+1)/2

if（n==0｜|n==1)return1；4、在一個單鏈表中，若q結(jié)點是p結(jié)點的前驅(qū)結(jié)點，若在與之間插入結(jié)點，則執(zhí)行（D

elsereturnn*f）;｝A

→link=→;

→；

AO（1)BO（n）CO2）DO（nB

→link

=；

→link

=;

15、線性表若是采用鏈式存儲結(jié)構(gòu)時，要求內(nèi)存中可用存儲單元的地址（D。C

→link

=→;

→link

=;

A必須是連續(xù)的D

→link

=；

→link

=;

B

部分地址必須是連續(xù)的5、如果想在4092數(shù)據(jù)中只需要選擇其中最小的5，采用（C）方法最好。

C一定是不連續(xù)的A起泡排序B堆排序C錦標賽排序D快速排序

D

連續(xù)或不連續(xù)都可以6、設(shè)有兩個串

和,求p在t

中首次出現(xiàn)的位置的運算叫做(B）.

16、數(shù)據(jù)結(jié)構(gòu)的定義為(D，S)，其中D是（B）的集合.A

求子串B模式匹配C

串替換D串連接

A算法B數(shù)據(jù)元素C數(shù)據(jù)操作D邏輯結(jié)構(gòu)7、在數(shù)組中，每一個數(shù)組元素[i占用3存儲字，行下標i

從18，列下標j

從1

17、算法分析的目的是(A。所有數(shù)組元素相繼存放于一個連續(xù)的存儲空間中，則存放該數(shù)組至少需要的存儲字數(shù)是(C）.A80B100C240D2708、將一個遞歸算法改為對應(yīng)的非遞歸算法時，通常需要使用（A

ABCD

找出數(shù)據(jù)結(jié)構(gòu)的合理性研究算法中輸入和輸出的關(guān)系分析算法的效率以求改進分析算法的易懂性和文檔性A

棧B隊列C循環(huán)隊列D優(yōu)先隊列

18、在一個單鏈表中，若所指結(jié)點不是最后結(jié)點，在p后插入s指結(jié)點，則執(zhí)行(B9、一個隊列的進隊列順序是1,3,，則出隊列順序為（C)10、在循環(huán)隊列中用數(shù)組[0。-1]存放隊列元素，其隊頭和隊尾指針分別為和則當前隊列中的元素個數(shù)是(D)

As；p->link=s；Bs-〉link=p；Cs-〉link=p；p=s;Dp—19、設(shè)單鏈表中結(jié)點結(jié)構(gòu)(data,linkq所指結(jié)點是指針p所指結(jié)點的直接前驅(qū)，若A(

front

-

rear

+1）％

B(

rear

-

front

+1)%

在*q*p之間插入結(jié)點*s則應(yīng)執(zhí)行下列哪一個操作（B）C（front

-

rear

+)%

D（

—

+)％

Asp；Bq->link=s;s->link=p11、一個數(shù)組元素a［i］與（A)的表示等價。A*（a+i）Ba+iC*a+iD&a+i

Cp->link=s-s-〉link=pDps—

20、設(shè)單鏈表中結(jié)點結(jié)構(gòu)為（data，link)若想摘除結(jié)點＊p直接后繼,則應(yīng)執(zhí)行下列哪一個操作（A）

constintMaxsize=100;typedefintDataType;Ap—Cp—；

Bp=p—；p-；Dp=p—〉link

typedefstruct｛DataType21、設(shè)單循環(huán)鏈表中結(jié)點的結(jié)構(gòu)為（data,link，且rear是指向非空的帶表頭結(jié)點的單循環(huán)鏈表的尾結(jié)點的指針.若想刪除鏈表第一個結(jié)點，則應(yīng)執(zhí)行下列哪一個操作(D）As=rear;rear=rear—；deletesB〉link;deleterear;C；deleterear;Ds=rear—rear〉link;deletes；22、設(shè)單循環(huán)鏈表中結(jié)點的結(jié)構(gòu)為，且first為指向鏈表表頭的指針current鏈表當前指針，在循環(huán)鏈表中檢測current是否達到鏈表表尾的語句(D)AcurrentBfirst-〉link=currentCfirst=currentD〉link=first23、一個棧的入棧序列為a，b，c，出棧序列不可能的是(CAc,bBb,a，cCc,a,bDa24、棧的數(shù)組表示中,top為棧頂指針,棧空的條件是(A)Atop=0Btop=maxSizeCtop=maxSizeDtop=-125、棧和隊列的共同特點是C)。

Intfront，rear;｝Queue;若有一個Queue類型的隊列Q，試問判斷隊列滿的條件應(yīng)是下列哪一個語句D)AQ。front==；BQ.front。rear==Maxsize；CQ。front+Q.rear==Maxsize;DQ.front=Maxsize;31、設(shè)有一個遞歸算法如下:intfact(intn）{if（n〈=0)return1；elsereturnn*fact；}下面正確的敘述是(B)A計算fact(n）需要執(zhí)行n次遞歸Bfact（7)=5040C此遞歸算法最多只能計算到fact（8）D以上結(jié)論都不對32、設(shè)有一個遞歸算法如下intx（intn）{AC

都是先進后出B都是先進先出只允許在端點處插入和刪除D沒有共同點

if(n〈=3）return1elsereturnx）+x(n-4）+1;26序存儲的循環(huán)隊列的隊頭和隊尾指針分別為和的條件為(DAf+1==rBr+1==fCf==0Df=

｝試問計算x（x（8）)時需要計算（D次x函數(shù)。27、當利用大小為n的數(shù)組順序存儲一個隊列時,該隊列的最大長度為（B）

A8次B9

次C16

次D18AnBnCnDn+128、當利用大小為n的數(shù)組順序存儲一個棧時，假定用top=表示?？?，則向這個棧插入一個元素時,首先應(yīng)執(zhí)行（）語句修改top針。

33、設(shè)有廣義表，b,D為（B）,深度為（A）A∞B3C2D534、廣義表A(a(C）Atop++；B；Ctop=0；Dtop;

AaB(（))C

空表D）29、設(shè)鏈式棧中結(jié)點的結(jié)構(gòu)為（datalink），且top指向棧頂?shù)闹羔?。若想摘除鏈式棧的棧頂結(jié)點，并將被摘除結(jié)點的值保存到中，則應(yīng)執(zhí)行下列A）操作。Ax=toptop=topBtop=topx=top—；

35、下列廣義表是線性表的有C)AE（b,cBE（a,E）CEDE（a（))36、遞歸表、再入表、純表、線性表之間的關(guān)系為(C)Cx=top；top=topDx=top->data;

A再入表>歸表>表〉線性表B

遞歸表>性表〉再入表〉純表30、設(shè)循環(huán)隊列的結(jié)構(gòu)是：

C遞歸表〉再入表>表〉線性表D遞歸表〉再入表性表>表

37、某二叉樹的前序和后序序列正好相反則該二叉樹一定是（B）的二叉樹。

4、設(shè)有兩個串p和求pq首次出現(xiàn)的位置的運算稱為（模式匹配）A空或只有一個結(jié)點B高度等于其結(jié)點數(shù)C任一結(jié)點無左孩子D任一結(jié)點無右孩子38、對于任何一棵二叉樹，如果其終端結(jié)點數(shù)為n度為2結(jié)點為nA)，2

5、6、

棧、隊列邏輯上都是（線性存儲）結(jié)構(gòu)。線性結(jié)構(gòu)反映結(jié)點間的邏輯關(guān)系是（一對一）的，圖中的數(shù)據(jù)元素之間的關(guān)系是（多對多）的，樹形結(jié)構(gòu)中數(shù)據(jù)元素間的關(guān)系是(一對多）的。Ann+1Bn=n+1Cn2n+1Dn=2n+10=2200=220

7、

棧中存取數(shù)據(jù)的原則(后進先出），隊列中存取數(shù)據(jù)的原則（

先進先出）39、由權(quán)值分別為11,8，5葉子結(jié)點生成一棵哈夫曼樹，它的帶權(quán)路徑長度為(B）A24B73C48D5340、已知一個順序存儲的線性表，設(shè)每個結(jié)點需m個存儲單元，若第一個結(jié)點的地址為，

8、9、

串是由（零個或多個）字符組成的序列長度為零的串)稱為空串，（由一個或多個空格組成的串）稱為空格串。設(shè)目標串T="abccdcdccbaa"，模式P="cdcc"則第6)次匹配成功。則第I個結(jié)點的地址為(A）。Ada1+(I）*mBda1+I*mCda1Dda1+（I+1)*m41、34具有個結(jié)點的完全二叉樹的深度為（A)A5B6C7D842、對線性表進行折半搜索時,要求線性表必須（C）A以鏈接方式存儲且結(jié)點按關(guān)鍵碼有序排列B以數(shù)組方式存儲C以數(shù)組方式存儲且結(jié)點按關(guān)鍵碼有序排列D以鏈接方式存儲43、順序搜索算法適合于存儲結(jié)構(gòu)為B）的線性表。A散列存儲B順序存儲或鏈接存儲C壓縮存儲D索引存儲44、采用折半搜索算法搜索長度為的有序表時，元素的平均搜索長度為（C)

10、一維數(shù)組的邏輯結(jié)構(gòu)是（線性結(jié)構(gòu)存儲結(jié)構(gòu)是（順序存儲表示）。對于二維數(shù)組，有（行優(yōu)先順序）列優(yōu)先順序)兩種不同的存儲方式于一個二維數(shù)組采用按行優(yōu)先存放的方式，則任一數(shù)組元素［i][j］相對于A］［0]的地址為（＊i+j)11順序棧插入一個元素時(棧頂指針個位置待插入元寫）到這個位置上。從一個順序棧刪除元素時,需要前移一位（棧頂指針）。12個循環(huán)隊列中隊空的條件=Q判斷隊滿的條件(Q。rear+1)％MaxSize==q.front）13、對于一棵具有n個結(jié)點的樹,該樹中所有結(jié)點的度數(shù)之和為（n）。14、一棵高度為5的滿二叉樹中的結(jié)點數(shù)為（63）個，一棵高度為3四叉樹中的結(jié)點數(shù)為(85）個。15、若對一棵二叉樹從0開始進行結(jié)點編號,并按此編號把它順序存儲到一維數(shù)組中,即編號為0AO(n

）BO（nlogn）CO(logn)DO）22

的結(jié)點存儲到a[0],其余類推，則［i］元素的左子女結(jié)點(2*i+1，右子女結(jié)點為（245、對于一個具有n個頂點和e邊的無向圖,進行拓撲排序時，總的時間(A）AnBn+1CnDn+e46、判斷一個有向圖是否存在回路,除了可以利用拓撲排序方法外，還可以利用（C

＊i+2），雙親結(jié)點（i〉=1）為（「(i-1)/2┐）.16、在一個最大堆中，堆頂結(jié)點的值是所有結(jié)點中的（最大值），在一個最小堆中，堆頂結(jié)點的值是所有結(jié)點中的（最小值）。A

求關(guān)鍵路徑的方法B求最短路徑的Dijkstra方法

17、已知具有n個元素的一維數(shù)組采用順序存儲結(jié)構(gòu)，每個元素占存儲單元，第一個元素的C深度優(yōu)先遍歷算法D廣度優(yōu)先遍歷算法47、在10—樹中根結(jié)點所包含的關(guān)鍵碼個數(shù)最多為CA）A1B2C9D1048、對包含n個元素的散列表進行搜索，平均搜索長度為（C)AO（logn）BO）C不直接依賴于D上述都不對2二、填空題（)

地址為）+（i-1）*k。18、在霍夫曼編碼中，若編碼長度只允許小于等于4，則除掉已對兩個字符編碼為0和,還可以最多對（4）個字符編碼。19、設(shè)高度為的空二叉樹的高度-，只有一個結(jié)點的二叉樹的高度為，若設(shè)二叉樹只有度為2度為0結(jié)點，則該二叉樹中所含結(jié)點至少有（2h+1）個。20、由一棵二叉樹的前序序列和（中序序列）可唯一確定這棵二叉樹。1、數(shù)據(jù)的邏輯結(jié)構(gòu)被分為集合結(jié)構(gòu)、線性結(jié)構(gòu)、樹形結(jié)構(gòu)、圖形結(jié)構(gòu)2、數(shù)據(jù)的存儲結(jié)構(gòu)被分為順序結(jié)構(gòu)、鏈接結(jié)構(gòu)、索引結(jié)構(gòu)、散列結(jié)構(gòu)3、一種抽象數(shù)據(jù)類型包括（數(shù)據(jù)）和（操作）兩個部分。

四種四種

21、以折半搜索方法搜索一個線性表時，此線性表必須是（順序）存儲的(有序）表。22知完全二叉樹的第8層有個結(jié)點其葉子結(jié)點數(shù)樹的第7有個葉子結(jié)點,則整個二叉樹的結(jié)點數(shù)最多是（235

23、對于折半搜索所對應(yīng)的判定樹,它既是一棵(二叉搜索樹)，又是一棵（理想平衡樹24、假定對長度有序表進行折半搜,則對應(yīng)的判定樹高度為（５前５層的結(jié)點數(shù)為(３１的結(jié)點數(shù)為（１９)。25、在一個無向圖中，所有頂點的度數(shù)之和等于所有邊數(shù)(２)倍。在一個具有n個頂點的無向完全圖中，包含有（邊一個具有n個頂點的有向完全圖中，包含)條邊。26、對于一個具有n個頂點和e邊的連通圖，其生成樹中的頂點數(shù)和邊數(shù)分別為n）和（n27、設(shè)線性表中元素的類型是實型，其首地址為1024，則線性表中第6個元素的存儲位置是(1044)。28、在插入和選擇排序中，若初始數(shù)據(jù)基本正,則選擇(插入排序,若初始數(shù)據(jù)基本反序，則最好選擇（選擇排序).29、算法是對特定問題的求解步驟的一種描述，它是（指令）的有限序每一條(指令)表示一個或多個操作.30、對于一個具有n個頂點肯e條邊的無向圖,進行拓樸排序時，總的進間為（n)31、構(gòu)造哈希函數(shù)有三種方法，分別為（平方取中法)法、(折迭移位）法。32、處理沖突的三種方法，分別為(線性探測隨機探測)地址法33、對于含有n個頂點和e條邊的無向連通圖,利用普里姆算法產(chǎn)生的最小生成樹，其時間復(fù)雜度為（Ｏ2）斯卡爾算法產(chǎn)生的最小生成樹，其時間復(fù)雜度為（Ｏe）234、快速排序在平均情況下的時間復(fù)雜度為（Ｏn)）,在最壞情況下的時間復(fù)雜度為（Ｏ2(n））；快速排序在平均情況下的空間復(fù)雜度為（Ｏn）），在最壞情況下的空間復(fù)雜度2為（Ｏ（n））.35、假定一組記錄的排序碼為（４７９，５６,３８，４０，８０行歸并排序的過程中，第二趟排序后的結(jié)果是４６５６７９］[４０８０36、假定一組記錄的排序碼(４６，７５６，３８，４８０對其進行快速排序的第一次劃分的結(jié)果是４０］４６[５６７９８０］)。37、一個結(jié)點的子樹的（個數(shù)）稱為該結(jié)點的度。度為（零)的結(jié)點稱為葉結(jié)點或終端

41、在索引表中，每個索引項至少包含有(關(guān)鍵碼值）域和（子表地址)域這兩項.42、假定一個線性表為（”abcd”,”bkwte”ccdtaayb"）,若按照字符串的第一個字母進行劃分,使得同一個字母被劃分在一個子表中，則得到的a,b三個子表的長度分別為（３),(）,（２)。43、對于包含５０個關(guān)鍵碼的３階樹，其最小高度為（４為（５)。44、從一棵B-樹刪除關(guān)鍵碼的過程，若最終引起樹根結(jié)點的合并，則新樹比原樹的高度（減１）45、假定要對長度n=100的線性表進行散列存,并采用開散列法處理沖突，則對于長度的散列表，每個散列地址的同義詞子表的長度平均為(46、在散列存儲中，裝載因子又稱為裝載系數(shù)，若用m示散列表的長度表示待散列存儲的元素的個數(shù)，則α等于（n/m）.47、在有向圖的鄰接矩陣中，第行中“1"個數(shù)是第i個頂點的（出度列中“1”的個數(shù)是第個頂點的（入)。在無向圖的鄰接矩陣中，第行（列）中1”的個數(shù)是第i個頂點的（度）,矩陣中“1”的個數(shù)的一半是圖中的（邊數(shù)48、在對階B—樹,每個非根結(jié)點的關(guān)鍵碼數(shù)最少為）個，最多為（m-1個，其子樹棵數(shù)最少為(三、判斷題1、數(shù)據(jù)元素是數(shù)據(jù)的最小單位（╳2、數(shù)據(jù)的邏輯結(jié)構(gòu)是指各數(shù)據(jù)元素之間的邏輯關(guān)系，是用戶按使用需要建立的（√)。3、數(shù)據(jù)結(jié)構(gòu)是指相互之間存在一種或多種關(guān)系的數(shù)據(jù)元素的全體（）.4、從邏輯關(guān)系上講,數(shù)據(jù)結(jié)構(gòu)主要分為兩大類：線性結(jié)構(gòu)和非線性結(jié)構(gòu)（5、線性表的邏輯順序與物理順序總是一致的（╳）.6、二維數(shù)組是其數(shù)組元素為線性表的線性表（╳）.7、每種數(shù)據(jù)結(jié)構(gòu)都應(yīng)具備三種基本運算：插入、刪除、搜索√8、非空線性表中任意一個數(shù)據(jù)元素都有且僅有一個直接前驅(qū)元素(╳)9、空串與由空格組成的串沒有區(qū)別。(╳）10、將T在中首次出現(xiàn)的位置作為TS中的位置的操作稱為串的模式匹配(√）結(jié)點。度不為（

零)的結(jié)點稱為分支結(jié)點或非終端結(jié)點.樹中各結(jié)點度的（

最大值)

11、深度為h的非空二叉樹的第h層最多有2h-1個結(jié)點（╳）稱為樹的度。38、設(shè)=K(1<=i<=n,）且在排序前的序列中領(lǐng)先于R〈j若排序后ijij的序列中R仍領(lǐng)先于R則這種排序方法是(穩(wěn)定的不穩(wěn)定的ij40、在堆排序的過程中，對任一分支結(jié)點進行調(diào)整運算的時間復(fù)雜度為（Ｏn）），整個2

12、完全二叉樹就是滿二叉樹。(╳）13、已知一棵二叉樹的前序序列和中序序列可以唯一地構(gòu)造出該二叉樹）14、帶權(quán)連通圖的最小生成樹的權(quán)值之和一定小于它的其它生成樹的權(quán)值之和。(√)15、線性表的順序存儲結(jié)構(gòu)的特點是邏輯關(guān)系上相鄰的兩個元素在物理位置上也相鄰。排序過程的時間復(fù)雜度為（Ｏ（nlogn)）。2

（

√

）

succ16、若有一個結(jié)點是二叉樹中某個子樹的中序遍歷結(jié)果序列的最后一個結(jié)點，則它一定是該子樹的前序遍歷結(jié)果序列的最后一個結(jié)點)succ17、任一棵二叉搜索樹的平均搜索時間都小于用順序搜索法搜索同樣結(jié)點的順序表的平均搜索時間。(╳）

出棧序列?答案：可能的出棧序列有種，6457321是合理的出棧序列。3、簡單（直接）選擇排序是一種穩(wěn)定的排序方法嗎？試舉例說明？答案：是不穩(wěn)定的排序方法.下面就是不穩(wěn)定的例子。只要能舉出反例即可。｛275275*512061}118、最優(yōu)二叉搜索樹一定是平衡的二叉搜索樹?！蹋?/p>

{275*512275｝i

=219、AOE網(wǎng)是一種帶權(quán)的無環(huán)連通圖.(√）

｛061275512275｝

=320、對于同一組待輸入的關(guān)鍵碼集合，雖然各關(guān)鍵碼的輸入次序不同，但得到的二叉搜索樹都是相同的(╳）.

{061275275512}4、設(shè)有序順序表為{，20,30,40，50，60,70}采用折半搜索時，搜索成功的平均21、二叉排序樹可以是一棵空樹（

)

搜索長度是多少？22、線性表中所有結(jié)點的類型必須相同。(√

）

答案：ASL=（1＊1+2＊2+3＊4)/7=/723、n個結(jié)點的有向圖，若它有n(n－1)條邊，則它一定是強連通的。(√

)

5、在結(jié)點個數(shù)為的各棵樹中,高度最小的樹的高度是多少？它有多少個葉結(jié)點？多少個24、任何無環(huán)的有向圖，其結(jié)點都可以排在一個拓撲序列里。（√

）

分支結(jié)點？高度最大的樹的高度是多少？它有多少個葉結(jié)點？多少個分支結(jié)點？25、隊列邏輯上是一個下端口和上端能增加又能減少的線性表（╳

)

答案：結(jié)點個數(shù)為時，高度最小的樹的高度為1，有2；它有n葉結(jié)點，1個分支結(jié)26、二叉樹是樹的一種特殊情況√

）

點；高度最大的樹的高度為，n層；它有1個葉結(jié)點,n-1個分支結(jié)點。27接矩陣存儲一個圖時考慮壓縮存儲的情況下,所占用的存儲空間大小只與圖中頂點個數(shù)有關(guān)，而與圖的邊數(shù)無關(guān)（√）.28、鄰接表只能用于有向圖的存儲,鄰接矩陣對于有向圖和無向圖的存儲都適用)29、連通分量是無向圖中的極小連通子圖30、在ＡＯＥ網(wǎng)絡(luò)中一定只有一條關(guān)鍵路徑)31、關(guān)鍵活動不按期完成就會影響整個工程的完成時間.（√)32、平衡二叉樹的左右子樹深度之差的絕對值不超過)

6、一棵高度為h滿k叉樹有如下性質(zhì):第h層上的結(jié)點都是葉結(jié)點,其余各層上每個結(jié)點都有k非空子樹,如果按層次自頂向下，同一層自左向右順序從1開始對全部結(jié)點進行編號，試問：(1)各層的結(jié)點個數(shù)是多少？（2)編號為i的結(jié)點的父結(jié)點(若存在)的編號是多少？(3）編號為i的結(jié)點的第個孩子結(jié)點(若存在）的編號是多少?（4）編號為i的結(jié)點有右兄弟的條件是什么？其右兄弟結(jié)點的編號是多少?(5)若結(jié)點個數(shù)為，則高度h是n的什么函數(shù)關(guān)系？33、快速排序是對起泡排序的一種改進（

√

)

答案：(1）各層的結(jié)點個數(shù)是

i

(i=0，2，.。.。,h)34、直接選擇排序穩(wěn)定

╳

)

（2）編號為i結(jié)點的父結(jié)點（若存在）的編號是└(i+k）/k35、堆排序占用的輔助空間很大.(╳

）

（3）編號為i結(jié)點的第m個孩子結(jié)點（若存在）的編號是(＊k+m+136、在散列法中采取開散列法來解決沖突時，其裝載因子的取值一定在（０,１）之間）37、B—樹是一種動態(tài)索引結(jié)構(gòu)，它既適用于隨機搜索，也適用于順序搜索(╳）38、在散列法中，一個可用散列函數(shù)必須保證絕對不產(chǎn)生沖突）39、任何一個關(guān)鍵活動延遲,那么整個工程將會延遲）40、任何一個關(guān)鍵活動提前完成，那么整個工程將會提前完成)四、運算應(yīng)用題

（4）當(i-1）％k<>0有右兄弟，右兄弟的編號為i+1（5）若結(jié)點個數(shù)為n，則高度h和n的關(guān)系為：h=log）+1)(n=0k時h=-1)7、寫出下列中綴表達式的后綴形式：（1）A＊-B+（2）（A+B）*D+E（F+A＊D)+(3）A＆&?。‥〉F)｛注：按C++的優(yōu)先級)1、在一個有個元素的順序表的第

個元素（1

）之前插入一個新元素時，需要向

(4）（A&&!(（B<｜(C>D)）)|｜（C〈E）后移動多少個元素？答案：需要向后移動i

+1個元素

答案：各中綴表達式的后綴形式如下:2、當一個棧的進棧序列為,可能的出棧序列有多少種？否是合理的

(1）AB（2）AB+D＊+/+C+114C7787

（3)AB＆&EF>｜｜(4)ABC<CD>｜|!&！CE<｜｜8、畫出下列廣義表的圖形表示和它們的存儲表示：(1）D（AB（e）,，（b，c,d）)（2)J1(J2，J3（J1（J1

J1J12^答案:廣義表（1)的圖形表示為：D

廣義表（2的圖形表示為：

J2

01

2^A

B

C

J32^c

LJ2J3b

c

d

廣義表（1)的存儲表示為：D

AC

B0A1^0Be^0D22^01^

9、題目：11將下面的森林變換成二叉樹(7分AEDF

GHIJKL

0L11^廣義表(2）的存儲表示為:

AECFH

31257答案：其中的一個拓撲序列為:V1，V2，V3,V4，V5，V612、將給定的圖簡化為最小的生成樹,要求從頂點出發(fā)。(7)I

8

1

5J

2

3

3

15K

10

126

4

7

5答案：10、將算術(shù)表達式（(a+b（d+e）+f)*（g+h)轉(zhuǎn)化為二叉樹.(7分)

6

9

2

7答案：*1

5+

+

2

3

3

15+

+

*

f

g

h

6

4

2

7

5

c

+

6713、某子系統(tǒng)在通信聯(lián)絡(luò)中只可能出現(xiàn)8種字符，其出現(xiàn)的概率分別為，d答案：11、根據(jù)所給有向圖，寫出一個拓撲序列）

0。08，0.23,0。03,0。11設(shè)計赫夫曼編碼.答案:為方便起見，設(shè)各種字符的權(quán)值w=｛5,29,7，8,14,23，3,11}.因為n=8，所以要構(gòu)造的赫夫曼樹共有m=2n-1=2個結(jié)點.生成的赫夫曼樹為下圖所示。

0

1010

答案：結(jié)點個數(shù)為n時，高度最小的樹的高度1,有2層有n-1個葉結(jié)點1個分支結(jié)點；高度最大的樹的高度為n，有n層;它有1個葉結(jié)點，分支結(jié)點.16、對于一個高度為h的AVL樹，其最少結(jié)點數(shù)是多?反之，對于一個有個結(jié)點的AVL樹,23

0

1

29

01

其最大高度是多少?最小高度是多少？答案:設(shè)高度為h（空樹的高度為-的的最少結(jié)點為，則N=F-1.hhh+311

5

0

3

1

14

1078

F是斐波那契數(shù)。又設(shè)有n個結(jié)點,則其最大高度不超過＊log(n+1h2最小高度為「log(n+1）┐。2177-7設(shè)有序順序表中的元素依次為017,094，154，170，275,503，509,512，553612677，765，897，908。試畫出對其進行折半搜索時的判定樹，并計算搜索成功的平赫夫曼編碼為:概率為0。23的字符編碼為：00概率為0.11字符編碼為：010概率為0。05字符編碼為0110概率為0。03字符編碼為0111概率為0.29字符編碼為：10概率為0。14字符編碼為：110

均搜索長度和搜索不成功的平均搜索長度。509154677概率為0。07字符編碼為：1110概率為0。08字符編碼為:111114叉樹的前序遍歷的結(jié)果是ABECDFGHIJ中序遍歷的結(jié)果是，試畫出這棵二叉樹，并給出這棵二叉樹的后序遍歷序列A

017094170答案：折半搜索時的判定樹為：

553897512765B

F

ASL=1/14（1+2＊2+3*4+4*7)=45/14SUCCASL=1/15）=59/15UNSUCCE

G

18、試對下圖所示的AOE絡(luò)D

HJI答案：根據(jù)前序序列和中序序列能得到唯一的二叉樹，所得二叉樹如圖：這棵二叉樹的后序遍歷序列為：EDCBIHJGFA15結(jié)點個數(shù)為各棵樹中度最小的樹的高度是多少？它有多少個葉結(jié)點？多少個分支結(jié)點？高度最大的樹的高度是多少？它有多少個葉結(jié)點？多少個分支結(jié)點？

(1）這個工程最早可能在什么時間結(jié)束.（2）求每個事件的最早開始時間］和最遲開始時間(3）求每個活動的最早開始時間（）和最遲開始時間l(。(4）確定哪些活動是關(guān)鍵活.畫出由所有關(guān)鍵活動構(gòu)成的,出哪些活動加速可使整個工程提

<5380前完成。<5380

-1；答案：按拓樸有序的順序計算各個頂點的最早可能開始時間V和最遲允許開始時間V，然后再el

for（int

=1；i<=;

++)cout〈<計算各個活動的最早可能開始時間e最遲允許開始時間l，根據(jù)l否等于來確定關(guān)鍵活

cout〈endl;動,從而確定關(guān)鍵路徑。

｝VV

el

①00

③1919

②1515

④2937

⑤3838

⑥4343

｝調(diào)用語句為。答案：(1）122e

〈1，20

〈1,3〉0

<3,215

<2,4>19

<2,5>19

<3,515

〈4，6〉29

38

3334444L

17

0

15

27

19

27

37

2、給出遞歸過程的執(zhí)行結(jié)果l-e

17

0

0

8

0

12

8

void

int

)｛此工程最早完成時間為，關(guān)鍵路徑為<1,3>〈3，2，6〉19、已知有五個待排序的記,其關(guān)鍵字分別為256，

cout<〈%;if（int（/10))

(（n）);076,438用快速排序的方法將它們從小到大排列。答案：第一次排序:（076）,256，(751,937,863，694，301,439）第二次排序：076，(438，694，937)

｝調(diào)用語句為unknown582)。答案：2853、給出遞歸過程的執(zhí)行結(jié)果第三次排序：076，301，（694）

int

（int

｛第四次排序:076，256，438,694，第五次排序：076，256，438,694,742,751，937

intif(!

；）

=3；else

=(

-1）+520、設(shè)有150個記錄要存儲到散列表中，并利用線性探查法解決沖突，要求找到所需記

return

;錄的平均比較次數(shù)不超過2次。試問散列表需要設(shè)計多大？（設(shè)表的裝載因子，則有ASL=(1+1/（1succ答案：已知要存儲的記錄數(shù)為n=150,查找成功的平均查找長度為ASL≤，則有succsucc=1/2≤解得2/3,有:兩式聯(lián)立得:150/m≤，解得：≥所以散列表需要設(shè)計單.五、算法分析題1、給出下列遞歸過程的執(zhí)行結(jié)果

}執(zhí)行語句為cout〈<unknown（3)答案:184、設(shè)有一個二維數(shù)組[][[0]［0存放位置在644，[2放位置在（10)676，每個元素占一個空間，［3]存放在什么位置？腳注表示用10進制表示。）(10）（10)答案：設(shè)數(shù)組元素A[i］存放在起始地址為Loc（i,j)存儲單元中.因為：Loc(2,2）=Loc(0,0)+2*n+2=644+2*n+2=676所以：n=（676void

(int

)｛

所以：Loc（3,3）=Loc(0）+3*15+3=644+45+3=692if(

）｛

5、設(shè)單鏈表結(jié)構(gòu)為struct

{

int

；

{

→link

=;

pc=;

*

；

pb→

;}；下面的程序是以單鏈表為存儲結(jié)構(gòu),實現(xiàn)二路歸并排序的算,要求鏈表不另外占用存儲空

｝if（）

→link

=；間,排序過程中不移動結(jié)點中的元素只改各鏈結(jié)點中的指針排序后仍指示結(jié)果鏈表的第一個結(jié)點。在初始狀態(tài)下,所有待排序記錄鏈接在一個以r頭指針的單鏈表中。例,

else→link=;}；（2)歸并排序主程序在算法實現(xiàn)時,利用了一個隊列做為輔助存儲，存儲各有序鏈表構(gòu)成的歸并段的鏈頭指針。初始時,各初始歸并段為只有一個結(jié)點的有序鏈表。隊列的數(shù)據(jù)類型為，其可直接使用的相關(guān)操作有空隊列操作：(；指針x加到隊列的隊尾操作：EnQueue＊)；出隊頭元素,其值由函數(shù)返回的操作:ListNode＊（)；隊列空否的函數(shù)，空則返回1,不空則返回int解決方法提示：

voidmergesort(ListNode*r{ListNode，；Queue；if（！r）return;=;（rwhile（)｛t→；while（t！=0&＆→〈=→dataif()｛

){

；

=;

t

=→；｝?序首先對待排序的單鏈表進行一次掃描將它劃分為若干有序的子鏈表,其表頭指針

→link

=0；

=;

)

;存放在一個指針隊列中。?隊列不空時，從隊列中退出兩個有序子鏈表，對它們進行二路歸并，結(jié)果鏈表的表頭指針存放到隊列中.?果隊列中退出一個有序子鏈表后變成空隊列，則算法結(jié)束序子鏈表即為所求。在算法實現(xiàn)時有6處語句缺失，請閱讀程序后補上。

｝}while()）{r。;if（（））break;（1)兩路歸并算法

=.（）;void

merge（

＊&）｛

(

，，

(

t

）

；

;

｝if(

→

〈=→

)｛hc;

pa=→；=；｝

｝else｛；pc=；

pb=→；=；}

6、請讀下列程序，該程序是在單鏈表中刪除一個結(jié)點的算法，為空出的地方填上正確的語分）while（papb）

voiddemo2(LinkListhead,ListNode＊p）if(

→data

<=→data

)

{//head是帶頭結(jié)點的單鏈表，刪除P向的結(jié)點{

→link=；pa→link

pc=;

；

ListNodewhile（q&＆)q=q-}else

if（q)Error(＊pnothead”)；q->next=p-〉next

free（p);｝10、已知一完全二叉樹從根結(jié)點開始下自左向右連續(xù)編號的編號為，

0781

12151

3031

45571

6451

7201

8313

9365

10231

1112121閱讀以下程序請回答該程序所實現(xiàn)的功能：template〈classtype>voidlinkedtosequent(Bintreenode*t,type｛if（t!=Null)｛a［—（);linkedtosequent(t）;linkedtosequent(t＊i+2)；｝}主程序調(diào)用方式:linkedtosequent(t.root,a,0)答案：該程序的功能是：將用二叉鏈表表示的完全二叉樹轉(zhuǎn)換為二叉樹的順序(組)表示.8、設(shè)散列表為散列函數(shù)為H(key)key。用閉散列法解決沖,對下列關(guān)鍵碼序列12,23，45，57，20，03,78，31，15,36造表.（1)采用線性探查法尋找下一個空位，畫出相應(yīng)的散列表,并計算等概率下搜索成功的平均搜索長度和搜索不成功的平均搜索長度。（2)采用雙散列法尋找下一個空位,再散列函數(shù)為RH（）=(7＊％10+1,尋找

9、閱讀下面程序，指出其算法的功能并求出其時間復(fù)雜度。（1）intPrime(intinti=2,x=；while（i〈=x）{if(n％i==0)break；i++}if(i〉x)returnelsereturn｝(2)intsum1n)intp=1,s=0for(inti=1;i<=n；i++）｛p＊=i;s+=preturns下一個空位的公式為H=(H+（))%13,=H(ii1等概率下搜索成功的平均搜索長度。答案:使用散列函數(shù)H（key)=key13有：

散列表,并計算

｝答案序功能是判斷是否是一個素數(shù),若是則返回數(shù)值1否則返回數(shù)值0，該算法的時間復(fù)雜度為O（n）.（31）

（2）程序功能是計算∑

n

，該算法的時間復(fù)雜度為O(n)。i=1=5,H）=2）=10利用線性探查法造表:

10個帶表頭結(jié)點的雙向循環(huán)鏈表否對稱相等的算法如下所示,請在算法的填入正確的語句。

處0781

12151

3031

45571

6451

7201

8314

910231

11362

12121

int（DblListDL)｛intsym=1;DblNodep=DL—〉rLink，〉lLink;搜索成功的平均搜索長度為：ASL=1/10（1+1+1+1+1+1+4+1+2+1）=14/10succ搜索不成功的平均搜索長度為：ASL=1/13(2+1+3+2+1+5+4+3+2+1+5+4+3)=36/13unsucc利用雙散列法造表：H=(HRH）)％13,H=H（keyiii

While（p！=q＆p-〉lLink==q)&&if（p—）{p=p->rLink;q=q->lLink;｝elsesym=0

sym==1

）

returnsym11、閱讀下面程序，指出其算法的功能

答案:（1）定義鏈表結(jié)構(gòu)#include“stack。h”

struct

｛intBaseTrans(intB)｛inti,result=0;Stack<intwhile（N!=0％B;N=N/B；S.Push（i

char;;int

，＊

;while(！S。IsEmpty（)）{i=S（（result=resultreturnresult;

；初始時,所有結(jié)點的域的值都為。（2)定義函數(shù)}

＊

(

*f

；char&

）｛答案：該算法是將一個非負的十進制整數(shù)轉(zhuǎn)換為另一個基數(shù)為的B制數(shù)。12、閱讀下面程序，指出其算法的功能template〈classType

DoubleListNode，*;=→；/*跳過表頭結(jié)點*/while(！=NULL&&→！=x)=→;/＊搜索＊/void〉*t,int{

if(

）｛if（t!=Null）{

→

++

=→;

→→llink

=；

→

=→;/＊從鏈中摘下＊/〉rightchild）{

while(

！=f

＆&→freq

<→

）=→bs=1;

→llink;—

→

=→;

→llink

=；if（bs)〉rightchild,bs）;

→

=；/＊在后面插入*/}elsebs=0；

｝return

;｝｝答案:該算法是判別給定的以二叉鏈表存儲的二叉樹是否是二叉搜索樹用遞歸算法樹中的所有結(jié)點檢查是否左子樹上結(jié)點的關(guān)鍵碼都小于它的關(guān)鍵碼，右子樹上結(jié)點的關(guān)鍵碼都大于它的關(guān)鍵碼。如滿足上述條件，則是二叉搜索樹。六、綜合算法題1個實現(xiàn)下述要求的查找運算函數(shù)設(shè)有一個帶表頭結(jié)點的雙向鏈表每個結(jié)點有4個數(shù)據(jù)成員：指向前驅(qū)結(jié)點的指針、指向后繼結(jié)點的指針，存放字符數(shù)據(jù)

}2、已知A[n為整數(shù)數(shù)組，試寫出實現(xiàn)下列運算的遞歸算法：(1)求數(shù)組A的最大整數(shù)。（2)求n個整數(shù)的和.（3)求n個整數(shù)的平均值答案：＃include<iostream〉classRecurveArray{的成員

和訪問頻度所有結(jié)點的freq

初始時都為在鏈表上進行一次，

：)操作時，令元素值為

的結(jié)點的訪問頻度freq

加1，并將該結(jié)點前移，鏈接到與它的訪問頻

int*Elements;度相等的結(jié)點后面，使得鏈表中所有結(jié)點保持按訪問頻度遞減的順序排列，以使頻繁訪問的結(jié)點總是靠近表頭。

intArraySizeintCurrentSize;

publicRecurveArrayMaxSize=10ArraySize(MaxSize）,Elements(newint［MaxSize]){｝～RecurveArray）{delete］ElementsvoidInputArray()；

Cout<<”\nTheis。MaxSize）<〈end1Cout〈”\nTheSum："〈ra.Sum。MaxSize）<<end1;Cout<”\nTheave（ra。MaxSize)<<end1Return；｝int（int

3、試編寫一個函數(shù)計算＊2n

的值,結(jié)果存放于數(shù)組第n個數(shù)組元素中,0int）;

。若設(shè)計算機中允許的整數(shù)的最大值為maxInt則當n〉arraySize者對于某一floatAverage(int）;

個k(0使得kk

〉maxInt時，應(yīng)按出錯處理?？捎腥缦氯N不同的出錯處理方式:};voidRecurveArray:：InputArray({cout<<”InputthenumberArray:\nfor（inti=0ArraySize；i++)cin>>Elements[i］;}intRecurveArray（int）｛if(n==1)returnElements［0];inttemp=if（Elements[nreturnElements[n］;elsereturntemp;｝intRecurveArray::Sum（int）｛if（n==1returnElements[0];elsereturnElements[n-1]+Sum；}floatRecurveArray::Average(intn)｛if（n==1)return；elsereturn(（float)Elements[n-1]+＊Average(n-1}int（intargc，char*argv[］)｛intsize=1;cout<〈"No。ofElementswhile(sizecin〉>size;RecurveArray（sizeRa.InputArray()；

（1)用cerr<〈exit（1)語句來終止執(zhí)行并報告錯誤(2）用返回整數(shù)函數(shù)值0,