數據結構考試試題

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

《數據結構》試卷參考答案一、簡答問題：（每小題4分，共16分）1．

集合結構、線性結構、樹形結構、網狀結構2．

線性結構的前驅與后繼之間為一對一關系，非線性結構的前驅與后繼之間通常為一對多或多對多關系。3．

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

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

）內打√，否則打。1.（）

2.（√）

3.（√）

4.（）

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

2．A)

3.

A)

4.

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

97

2.

n+1

3.鏈域數目不同

4.哈希查找法

5.26–1

6.1168

7.p->next

、

s

8.(a,b)

、

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

10.直接插入五、構造題：（每小題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)為左子樹偏長。

六、算法設計題：（每小題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;

}}}

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

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

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

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

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

（3）求AOE網的關鍵路徑，其結果必定是唯一的其中哪個（些）是正確的？

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

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

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

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

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

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

《數據結構》試卷參考答案一、簡答題：（每小題3分，共15分）前驅與后繼之間通常為一對多或多對多的關系。順序表優(yōu)點：隨機查找，存儲密度大順序表缺點：插入、刪除不便，靜態(tài)分配，表長固定單鏈表優(yōu)點：插入、刪除方便，動態(tài)分配，表長靈活單鏈表缺點：查找不便，存儲密度小關鍵字相同的兩個記錄，排序前后其先后順序不變。typedefstructnode{ElemTypedata;structnode*next;}*LinkStack;當二叉排序樹接近平衡二叉樹或完全二叉樹時查找性能較好，當二叉排序樹為單邊單枝二叉樹時查找性能最差。二、判斷正誤：（每小題1分，共5分）正確在（）內打√，否則打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五、構造題：（每小題6分，共30分）

或：WPL=8×3+4×4+5×4+16×2+9×3+12×3+26×2=207[注]：哈夫曼樹的左右子樹可以互換。[解1]：[解2]：[注]：邊上的權值可以省略。初始堆：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[注]：如果采用大根堆，應適當減分。六、算法設計題：（共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;}}}

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

3．有一個含頭結點的雙向循環(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)中，用折半法查找關鍵碼值11，所需的關鍵碼比較次數為：

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

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

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

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

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