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

數(shù)據(jù)結(jié)構(gòu)輔導(dǎo)試題一一、簡答問題：四類數(shù)據(jù)結(jié)構(gòu)線性結(jié)構(gòu)與非線性結(jié)構(gòu)有何差別？簡述算法的定義與特性。設(shè)有1000個無序元素，僅要求找出前10個最小元素，在下列排序方法中（歸并排序、基數(shù)排序、快速排序、堆排序、插入排序）哪一種方法最好，為什么？二、判斷正誤：（每小題1分，共5分）正確在（）內(nèi)打√，否則打r。（）二叉排序樹或是一棵空樹，或是具有下列性質(zhì)的二叉樹：若它的左子樹非空，則根結(jié)點的值大于其左孩子的值，若它的右子樹非空，則根結(jié)點的值大于其右孩子的值。（）索引順序表的特點是塊內(nèi)可無序，塊間要有序。（）子串是主串中任意個連續(xù)字符組成的序列。（）線性結(jié)構(gòu)只能用順序結(jié)構(gòu)存放，非線性結(jié)構(gòu)只能用鏈表存放。（）快速排序的樞軸元素可以任意選定。三、單項選擇題：(每小題1分，共4分)1．棧S最多能容納4個元素?，F(xiàn)有6個元素按A、B、C、D、E、F的順序進棧,問下列哪一個序列是可能的出棧序列?A)E、D、C、B、A、FB)B、C、E、F、A、DC)C、B、E、D、A、FD)A、D、F、E、B、C2．將一棵有100個結(jié)點的完全二叉樹從根這一層開始，每一層從左到右依次對結(jié)點進行編號，根結(jié)點編號為1，則編號為49的結(jié)點的左孩子的編號為：A、98 B、99 C、50 D、483.對下列關(guān)鍵字序列用快速排序法進行排序時，速度最快的情形是：A）{21、25、5、17、9、23、30}B）{25、23、30、17、21、5、9}B）{21、9、17、30、25、23、5}D）{5、9、17、21、23、25、30}4.設(shè)森林F中有三棵樹，第一、第二和第三棵樹的結(jié)點個數(shù)分別為M1、M2和M3。與森林F對應(yīng)的二叉樹根結(jié)點的右子樹上的結(jié)點個數(shù)是：A）M1B）M1+M2C）M3D）M2+M3四、填空題：(每小題2分,共20分)設(shè)一哈希表表長M為100，用除留余數(shù)法構(gòu)造哈希函數(shù)，即H（K）=KMODP（P<=M）,為使函數(shù)具有較好性能，P應(yīng)選N個結(jié)點的二叉樹采用二叉鏈表存放，共有空鏈域個數(shù)為單鏈表與多重鏈表的區(qū)別是在各種查找方法中，平均查找長度與結(jié)點個數(shù)無關(guān)的是深度為6（根層次為1）的二叉樹至多有個結(jié)點。已知二維數(shù)組A[20][10]采用行序為主方式存儲,每個元素占2個存儲單元,并且A[10][5]的存儲地址是1000,則A[18][9]的存儲地址是在一個單鏈表中p所指結(jié)點之后插入s所指結(jié)點時,應(yīng)執(zhí)行s->next=和p->next=的操作.8．廣義表((a,b),c,d)的表頭是,表尾是9．循環(huán)單鏈表LA中，指針P所指結(jié)點為表尾結(jié)點的條件是10．在一個待排序的序列中，只有很少量元素不在自己最終的正確位置上，但離他們的正確位置都不遠，則使用排序方法最好。五、構(gòu)造題：（每小題5分，共25分）已知一棵二叉樹，其中序序列DBCAFGE，后序序列DCBGFEA，構(gòu)造該二叉樹。設(shè)哈希表長度為11，哈希函數(shù)H（K）=（K的第一字母在字母表中的序號）MOD11，若輸入順序為（D，BA，TN，M，CI，I，K，X，TA），處理沖突方法為線性探測再散列或鏈地址法，要求構(gòu)造哈希表，并求出等概率情況下查找成功平均查找長度。有一組關(guān)鍵字{50，52，85，22，96，17，36，55}，請用快速排序，寫出第一趟排序結(jié)果。已知葉子結(jié)點值2，3，5，6，9，11，構(gòu)造哈夫曼樹，計算其帶權(quán)路徑長度。畫出8個結(jié)點的折半判定樹。六、算法設(shè)計題：（每小題15分，共30分）（僅要求給出子程序）1．編寫算法，判斷帶頭結(jié)點的雙向循環(huán)鏈表L是否對稱。（15分）對稱是指：設(shè)各元素值a1,a2,...,an,則有ai=an-i+1，即指：a1=an，a2=an-1。。。。。。。結(jié)點結(jié)構(gòu)為：priordatanext二叉排序樹T用二叉鏈表表示，其中各元素均不相同。寫出遞歸算法，按遞減順序打印各元素的值。（10分）寫出完成上述要求的非遞歸算法。（5分）

《數(shù)據(jù)結(jié)構(gòu)》試卷參考答案一、簡答問題：（每小題4分，共16分）1．

集合結(jié)構(gòu)、線性結(jié)構(gòu)、樹形結(jié)構(gòu)、網(wǎng)狀結(jié)構(gòu)2．

線性結(jié)構(gòu)的前驅(qū)與后繼之間為一對一關(guān)系，非線性結(jié)構(gòu)的前驅(qū)與后繼之間通常為一對多或多對多關(guān)系。3．

解決特定問題的有限指令序列。有限性、確定性、可行性、有0個或多個輸入數(shù)據(jù)、有1個或多個輸出結(jié)果。4．

堆排序。因為一趟堆排序排定一個元素，只需進行前10趟堆排序就可以了。其它排序方法均需進行完全排序。二、判斷正誤：（每小題1分，共5分）正確在（

）內(nèi)打√，否則打。1.（）

2.（√）

3.（√）

4.（）

5.（√）三、單項選擇題：(每小題1分，共4分)1．C)

2．A)

3.

A)

4.

D)四、填空題：(每小題2分,共20分)1．

97

2.

n+1

3.鏈域數(shù)目不同

4.哈希查找法

5.26–1

6.1168

7.p->next

、

s

8.(a,b)

、

(c,d)9.P->next==LA

10.直接插入五、構(gòu)造題：（每小題5分，共25分）1．

2．

012345678910KTABAMDCIX

TNIASL=20/9

012345678910

ASL=15/93．

{36，17，22，50，96，85，52，55}4．

WPL=11×2+6×2+9×2+5×3+2×4+3×4

=87[注]：哈夫曼樹的左右子樹可以互換。5．

[注]：如果求中點時采用向上取整，則二叉樹的形態(tài)為左子樹偏長。

六、算法設(shè)計題：（每小題15分，共30分）

（僅要求給出子程序）1．[解答]：intjudge(DLinkListL){p=L->next;

q=L->prior;while(p!=q)

{if(p->data!=q->data)return0;if(p->next==q)return1;p=p->next;q=q->prior;

}return1;}[注]：可以不用返回值，而用打印信息。2．

[解答]：（1）voidprint_1(BiTreeT){if(T!=NULL)

{print_1(T->RChild);

printf(“%c”,T->data);

print_1(T->LChild);

}}（2）void

Print_2（BiTreeT）{InitStack(&S);p=T;while(p!=NULL||!IsEmpty(S)){while(p!=NULL)

{Push(&S,

p);p=p->RChild;

}if(!IsEmpty(S))

{Pop(&S,

&p);

printf(“%c”,

p->data);

p=p->LChild;

}}}

數(shù)據(jù)結(jié)構(gòu)輔導(dǎo)試題二一、簡答題：（每小題3分，共15分）什么情況下二叉排序樹的查找性能較好？什么情況下二叉排序樹的查找性能最差？比較順序表與單鏈表的優(yōu)缺點。請寫出棧的鏈?zhǔn)酱鎯Y(jié)構(gòu)的類型定義。在起泡排序過程中，有的關(guān)鍵字在某趟排序中可能朝著與最終排序相反的方向移動，試舉例說明之。簡述參數(shù)傳遞的主要方式及其特點。二、判斷正誤：（每小題1分，共5分）正確在（）內(nèi)打√，否則打r。()（1）在拓樸序列中，如果結(jié)點Vi排在結(jié)點Vj的前面，則一定存在從Vi到Vj的路徑。()（2）在采用線性探測法處理沖突的散列表中，所有同義詞在表中一定相鄰。()（3）在一個小根堆中，具有最大值的元素一定是葉結(jié)點。()（4）索引順序表的特點是塊間可無序，但塊內(nèi)一定要有序。()（5）哈夫曼樹中沒有度為1的結(jié)點，所以必為滿二叉樹。三、單項選擇題：(每小題1分，共5分)1．對于只在表的首、尾進行插入操作的線性表，宜采用的存儲結(jié)構(gòu)為:

A)順序表B)用頭指針表示的單循環(huán)鏈表

C)用尾指針表示的單循環(huán)鏈表D)單鏈表2．假設(shè)以第一個元素為分界元素，對字符序列（Q,H,C,Y,P,A,M,S,R,D,F,X）進行快速排序，則第一次劃分的結(jié)果是：A)(A,C,D,F,H,M,P,Q,R,S,X,Y)B)(A,F,H,C,D,P,M,Q,R,S,Y,X)C)(F,H,C,D,P,A,M,Q,R,S,Y,X)D)(P,A,M,F,H,C,D,Q,S,Y,R,X)3．下面是三個關(guān)于有向圖運算的敘述：

（1）求有向圖結(jié)點的拓撲序列，其結(jié)果必定是唯一的

（2）求兩個指向結(jié)點間的最短路徑，其結(jié)果必定是唯一的

（3）求AOE網(wǎng)的關(guān)鍵路徑，其結(jié)果必定是唯一的其中哪個（些）是正確的？

A)只有（1）B)（1）和（2）C)都正確D)都不正確4．若進棧序列為a,b,c，則通過入出棧操作可能得到的a,b,c的不同排列個數(shù)為:

A)4B)5C)6D)75.以下關(guān)于廣義表的敘述中,正確的是：

A)廣義表是由0個或多個單元素或子表構(gòu)成的有限序列

B)廣義表至少有一個元素是子表

C)廣義表不能遞歸定義D)廣義表不能為空表

四、填空題：(每小題2分,共20分)1．一棵含有101個結(jié)點的完全二叉樹存儲在數(shù)組A[1..101]中,對1≤k≤101,若A[k]是非葉結(jié)點,則k的最小值是:，k的最大值是:。2.設(shè)s=’YOUAREJUDGINGITRIGHTORWRONG’，順序執(zhí)行下列操作：SubString(sub1,s,1,8);SubString(sub2,s,20,5);StrCat(sub1,sub2);則最后sub1的值為：。3.若一個算法中的語句頻度之和為T(n)=3720n+4nlogn，則算法的時間復(fù)雜度為________________。4．廣義表((((a),b),c),d)的表頭是，表尾是。5．已知有向圖的鄰接矩陣，要計算i號結(jié)點的入度，計算方法是：將累加。6．要在一個單鏈表中p所指結(jié)點之后插入一個子鏈表，子鏈表第一個結(jié)點的地址為s，子鏈表最后一個結(jié)點的地址為t,則應(yīng)執(zhí)行操作：和。7.用帶頭結(jié)點的循環(huán)鏈表表示的隊列,若只設(shè)尾指針rear,則隊空的條件是。8．已知二維數(shù)組A[10][20]采用行序為主方式存儲，每個元素占2個存儲單元,并且A[0][0]的存儲地址是1024,則A[6][18]的地址是9．在表示二叉樹的二叉鏈表中,共有個空鏈域。10．n個頂點的連通無向圖至少有條邊，至多有條邊。五、構(gòu)造題：（每小題6分，共30分）1．已知二叉樹的中序序列為DBGEAFC，后序序列為DGEBFCA，給出對應(yīng)的二叉樹。2．已知一個圖的頂點為A、B、C、D，其鄰接矩陣的上三角元素全為0（包括主對角線元素），其他元素均為1。請畫出該圖，并給出其鄰接表。3．給定權(quán)值{8，12，4，5，26，16，9}，構(gòu)造一棵帶權(quán)路徑長度最短的二叉樹，并計算其帶權(quán)路徑長度。4．圖2表示一個地區(qū)的通訊網(wǎng)，邊表示城市間的通訊線路，邊上的權(quán)值表示架設(shè)線路花費的代價，請找出能連通每個城市、且總代價最省的n-1條線路。圖25．對關(guān)鍵字序列(72，87，61，23，94，16，05，58)進行堆排序，使之按關(guān)鍵字遞減次序排列。請寫出排序過程中得到的初始堆和一趟排序后的序列狀態(tài)。六、算法設(shè)計題：（共25分）設(shè)有一個由正整數(shù)組成的單鏈表L（含頭結(jié)點），編寫完成下列功能的算法：找出最小值結(jié)點P，若最小值是奇數(shù)，則刪除結(jié)點P。[15分]已知樹用孩子兄弟鏈表存儲，root指向根結(jié)點。編寫算法，逐層遍歷這棵樹。[10分]

《數(shù)據(jù)結(jié)構(gòu)》試卷參考答案一、簡答題：（每小題3分，共15分）前驅(qū)與后繼之間通常為一對多或多對多的關(guān)系。順序表優(yōu)點：隨機查找，存儲密度大順序表缺點：插入、刪除不便，靜態(tài)分配，表長固定單鏈表優(yōu)點：插入、刪除方便，動態(tài)分配，表長靈活單鏈表缺點：查找不便，存儲密度小關(guān)鍵字相同的兩個記錄，排序前后其先后順序不變。typedefstructnode{ElemTypedata;structnode*next;}*LinkStack;當(dāng)二叉排序樹接近平衡二叉樹或完全二叉樹時查找性能較好，當(dāng)二叉排序樹為單邊單枝二叉樹時查找性能最差。二、判斷正誤：（每小題1分，共5分）正確在（）內(nèi)打√，否則打r。(r)（1）(r)（2）(√)（3）(r)（4）(r)（5）三、單項選擇題：(每小題1分，共5分)1．C)2．C)3．D)4．B)5.A)四、填空題：(每小題2分,共20分)1．12.’YOUARERIGHT’3.O(nlogn)4．(((a),b),c)，(d)5．i列元素6．t->next=p->next，p->next=s7.rear->next==rear8．13009．n+110．n-1五、構(gòu)造題：（每小題6分，共30分）

或：WPL=8×3+4×4+5×4+16×2+9×3+12×3+26×2=207[注]：哈夫曼樹的左右子樹可以互換。[解1]：[解2]：[注]：邊上的權(quán)值可以省略。初始堆：05，23，16，58，94，72，61，87一趟排序后的序列狀態(tài)：87，23，16，58，94，72，61，05篩成堆后為：16，23，61，58，94，72，87，05[注]：如果采用大根堆，應(yīng)適當(dāng)減分。六、算法設(shè)計題：（共25分）[15分]voidmin(LinkListL){if(L->next==NULL)return;q=L;r=L->next;m=r->data;while(r->next!=NULL){if(r->next->data<m){m=r->next->data;q=r;}r=r->next;}p=q->next;if(m%2==1){q->next=p->next;free(p);}}[10分]voidlayer(CSTreeroot){InitQueue(&Q);EnterQueue(&Q,root);while(!Empty(Q)){DelQueue(&Q,&p);visit(p);p=p->FirstChild;while(p!=NULL){EnterQueue(&Q,p);p=p->NextSibling;}}}

數(shù)據(jù)結(jié)構(gòu)輔導(dǎo)試題三一、簡答題（15分，每小題3分）簡要說明算法與程序的區(qū)別。在哈希表中，發(fā)生沖突的可能性與哪些因素有關(guān)？為什么？說明在圖的遍歷中，設(shè)置訪問標(biāo)志數(shù)組的作用。說明以下三個概念的關(guān)系：頭指針，頭結(jié)點，首元素結(jié)點。在一般的順序隊列中，什么是假溢出？怎樣解決假溢出問題？二、判斷題（10分，每小題1分）正確在括號內(nèi)打√，錯誤打×()（1）廣義表(((a),b),c)的表頭是((a),b)，表尾是(c)。()（2）在哈夫曼樹中，權(quán)值最小的結(jié)點離根結(jié)點最近。()（3）基數(shù)排序是高位優(yōu)先排序法。()（4）在平衡二叉樹中，任意結(jié)點左右子樹的高度差（絕對值）不超過1。()（5）在單鏈表中，給定任一結(jié)點的地址p，則可用下述語句將新結(jié)點s插入結(jié)點p的后面：p->next=s;s->next=p->next;()（6）抽象數(shù)據(jù)類型（ADT）包括定義和實現(xiàn)兩方面，其中定義是獨立于實現(xiàn)的，定義僅給出一個ADT的邏輯特性，不必考慮如何在計算機中實現(xiàn)。()（7）數(shù)組元素的下標(biāo)值越大，存取時間越長。()（8）用鄰接矩陣法存儲一個圖時，在不考慮壓縮存儲的情況下，所占用的存儲空間大小只與圖中結(jié)點個數(shù)有關(guān)，而與圖的邊數(shù)無關(guān)。()（9）拓撲排序是按AOE網(wǎng)中每個結(jié)點事件的最早發(fā)生時間對結(jié)點進行排序。()（10）長度為1的串等價于一個字符型常量。三、單項選擇題（10分,每小題1分）1．排序時掃描待排序記錄序列，順次比較相鄰的兩個元素的大小，逆序時就交換位置。這是哪種排序方法的基本思想？A、堆排序 B、直接插入排序 C、快速排序 D、冒泡排序2．已知一個有向圖的鄰接矩陣表示，要刪除所有從第i個結(jié)點發(fā)出的邊，應(yīng)該：A）將鄰接矩陣的第i行刪除B）將鄰接矩陣的第i行元素全部置為0C）將鄰接矩陣的第i列刪除D）將鄰接矩陣的第i列元素全部置為0

3．有一個含頭結(jié)點的雙向循環(huán)鏈表，頭指針為head,則其為空的條件是：head->priro==NULLB.head->next==NULLC.head->next==headD.head->next->priro==NULL4.在順序表(3,6,8,10,12,15,16,18,21,25,30)中，用折半法查找關(guān)鍵碼值11，所需的關(guān)鍵碼比較次數(shù)為：

A)2B)3C)4D)5

5.以下哪一個不是隊列的基本運算？A）從隊尾插入一個新元素B）從隊列中刪除第i個元素C）判斷一個隊列是否為空D）讀取隊頭元素的值6.在長度為n的順序表的第i個位置上插入一個元素（1≤i≤n+1），元素的移動次數(shù)為：

A)n–i+1B)n–iC)iD)i–17．對于只在表的首、尾兩端進行插入操作的線性表，宜采用的存儲結(jié)構(gòu)為:

A)順序表B)用頭指針表示的循環(huán)單鏈表

C)用尾指針表示的循環(huán)單鏈表D)單鏈表8．對包含n個元素的哈希表進行查找，平均查找長度為：A)O(log2n)B)O(n)C)O(nlog2n)D)不直接依賴于n9．將一棵有100個結(jié)點的完全二叉樹從根這一層開始，每一層從左到右依次對結(jié)點進行編號，根結(jié)點編號為1，則編號最大的非葉結(jié)點的編號為：A、48 B、49 C、50 D、5110．某二叉樹結(jié)點的中序序列為A、B、C、D、E、F、G，后序序列為B、D、C、A、F、G、E，則其左子樹中結(jié)點數(shù)目為：A）3B）2C）4D）5四、填空題（10分，每空1分）1．填空完成下面一趟快速排序算法：intQKPass(RecordTyper[],intlow，inthigh){x=r[low]；while(low<high){while(low<high&&r[].key>=x.key)high--；if(low<high){r[]=r[high]；low++;}while(low<high&&r[].key<x.key)low++;if(low<high){r[]=r[low]；high--;}}r[low]=x；returnlow;}2.假設(shè)用循環(huán)單鏈表實現(xiàn)隊列，若隊列非空，且隊尾指針為R,則將新結(jié)點S加入隊列時，需執(zhí)行下面語句：；；R=S；3．通常是以算法執(zhí)行所耗費的和所占用的來判斷一個算法的優(yōu)劣。4．已知一個3行、4列的二維數(shù)組A（各維下標(biāo)均從1開始），如果按“以列為主”的順序存儲，則排在第8個位置的元素是：5．高度為h的完全二叉樹最少有個結(jié)點。五、構(gòu)造題（20分）1．（4分）已知數(shù)據(jù)結(jié)構(gòu)DS的定義如下，請給出其邏輯結(jié)構(gòu)圖示。DS=(D,R)D={a,b,c,d,e,f,g}R={T}T={<a,b>,<a,g>,<b,g>,<c,b>,<d,c>,<d,f>,<e,d>,<f,a>,<f,e>,<g,c>,<g,d>,<g,f>}2．（6分）對以下關(guān)鍵字序列建立哈希表：（SUN,MON,TUE,WED,THU,FRI,SAT）,哈希函數(shù)為H(K)=（K中最后一個字母在字母表中的序號）MOD7。用線性探測法處理沖突，要求構(gòu)造一個裝填因子為0.7的哈希表，并計算出在等概率情況下查找成功的平均查找長度。3.（6分）將關(guān)鍵字序列（3，26，12，61，38，40，97，75，53，87）調(diào)整為大根堆。4．（4分）已知權(quán)值集合為：{5，7，2，3，6，9}，要求給出哈夫曼樹，并計算其帶權(quán)路徑長度WPL。六、算法分析題（10分）閱讀下面程序，并回答有關(guān)問題。其中BSTree為用二叉鏈表表示的二叉排序樹類型。簡要說明程序功能。（5分）n個結(jié)點的滿二叉樹的深度h是多少？（3分）假設(shè)二叉排序樹*bst是有n個結(jié)點的滿二叉樹,給出算法的時間復(fù)雜度。（2分）intProc(BSTree*bst,KeyTypeK){BSTreef,q,s;s=(BSTree)malloc(sizeof(BSTNode));s->key=K;s->lchild=NULL;s->rchild=NULL;if(*bst==NULL){*bst=s;return1;}f=NULL;q=*bst;while(q!=NULL){if(K<q->key){f=q;q=q->lchild;}else{f=q;q=q->rchild;}}if(K<f->key)f->lchild=s;e