《數據結構》模擬試題15

一、填空題(每小題2分，共18分)

1、數據的邏輯結構在計算機中的基本存儲結構有和0

2、算法的時間復雜度取決于o

3、隊列是的線性表，其操作數據的基本原則是o

4、設有一個二維數組A[0…9][0…9],若每個元素占2個基本存儲單元，A⑼⑼的地址是200,

若按列優先(以列為主)順序存儲，則A[6][6]的存儲地址是_______-

5、在高度為h的二叉樹的中只有度為0和度為2的結點，則該類二叉樹中所包含的結點數

至少為__________

6、對于一個有n個頂點和e條弧的有向圖，若采用正鄰接鏈表存儲，則表頭向量的大小

為，鄰接表中的結點總數為o

7、若采用分塊查找，要求線性表塊內,塊間o

8、對于文件，按其記錄的類型可將文件分為文件^文件。

9、外部排序的最基本方法是，其主要時間花費在方面。

二、單項選擇題(請將答案寫在題目后的括號中。每題2分，共18分)

1、下面程序段的時間復雜度是()0

for(i=l；i<=m；i++)

for(j=l5j<=n；j++)A[i](j]=i+j;

(A)O(m+n)(B)O(m)(C)O(n)(D)O(m*n)

2、判斷一個循環隊列Q(最多元素個數為m)為滿隊列的條件是()。

(A)Q.front==Q.rear；(B)Q.front!=Q.rear；

(C)Q.front==(Q.rear+l)%m；(D)Q.front!=(Q.rear+l)%m；

3、設有一個棧頂指針為top的順序棧S,則將元素p壓入棧S中的操作是()。

(A)S[top++]=p；(B)S[++top]=p；

(C)S[top—]=p；(D)S[-top]=p；

4、廣義表((a),((b),c),(((d))))的長度是，深度是-()

(A)3,4(B)3,3(C)4,3(D)4,4

5、在二叉樹中，指針P所指的結點是葉子結點的條件是()0

(A)P->Lchild!=NULL&&P->Rchild!=NULL；

(B)P->Lchild!=NULL&&P->Rchild==NULL；

(C)P->Lchild==NULL&&P->Rchild!=NULL；

(D)P->Lchild==NULL&&P->Rchild==NULL；

6、■—棵二叉樹，其先序遍歷序列是abdghcefi,中序遍歷序列是bgdhaecfi,則其后序遍歷

序列是()0

(A)ghdbiefca(B)ghdbeicfa

(C)ghdbeifca(D)gdheibfca

7、若以｛4,5,6,7,8｝作為葉子的權值構造Huffman樹(按左子樹根結點的權小于等于右子

樹根結點的權的次序構造)，則其帶權路徑長度WPL為()。

(A)60(B)61(C)73(D)69

8、在無權圖G的鄰接矩陣中，若(Vi,2)或＜Vi,Vj＞屬于G的邊集，則對應元素等

于_________^否則等于)

(A)1,1(B)1,0(C)0,1(D)0,0

9、設有一組記錄的關鍵字是(37,28,56,80,60,14,25,50),用快速排序法以第一個

記錄為基準得到的一次劃分結果是()o

(A)25,28,14,37,60,80,56,50(B)25,28,37,14,60,80,56,50

(C)25,28,14,37,60,56,80,50(D)25,28,37,14,56,80,60,50

三、分析題(每題6分，共30分)

1、設有一棵樹如下圖，請先將此樹轉換為二叉樹，然后給出該二叉樹的前序線

索樹和中序線索樹。

2、已知某有向圖的逆鄰接鏈表如下圖所示，請先畫出該有向圖，然后給出其鄰接矩陣和正

鄰接鏈表。

3,將關鍵字序列(17,19,13,7,15,9,25)依此插入到初態為空的二叉排序樹中，請

畫出建立二叉排序樹T的過程；然后畫出刪除13之后的二叉排序樹TL

4、線性表的關鍵字集合{21,25,28,19,42,57,15,43,17,36,49,27,65}

，共有13個元素，已知散列函數為：H(k)=kMOD13,采用線性探測法處理沖突，請給出

對應的散列表結構，并計算該表成功查找的平均查找長度。

5、已知數據序列為{35,29,22,16,17,9,38,27,13,45},請給出采用選擇排序方法

按非遞減要求進行排序的過程。

四、算法填空(每空2分，共20分)

請在下面各算法的空白處填上相應語句以實現算法功能。每個空白只能填一個語句。

1、在以L為頭結點的雙向鏈表中刪除所有值為key的結點，結點結構定義如下。

typedefstructLnode

{ElemTypedata;/*數據域，保存結點的值*/

structLnode*prior;/*指針域，指向直接后繼*/

structLnode*next;/*指針域，指向直接前趨*/

JDULNode;/*結點的類型*/

VoidDel_Node(DULNode*L,intkey)

{DULNode*q,*p=L->next;

while(p!=NULL)

{if(p->data==key)

{q=p->next;

if(p->next!=NULL)

{p->next->prior=p->prior;

elsep->prior->next=NULL;

)

2、設T是指向二叉樹根結點的指針變量，用非遞歸方法統計樹中葉子結點的數

目。

#defineMax_Node_Num50

TypedefstructBTNode

{ElemTypedata;/*數據域，保存結點的值*/

structBTNode*Lchild,*Rchild;/*指針域*/

JBTNode;/*結點的類型*/

Voidcount_leaf_node(BTNode*T)

{BTNode*Stack[Max_Node_Num],*p=T,*q;

inttop=0,leaf_num=0;/*leaf_num保存葉子結點的數目*/

if(T==NULL)printf(uTheBinaryTreeisEmpty!\n");

else{do

{if(p->Lchild==NULL&&p->Rchi1d==NULL);

q=p->Rchild;

if(q!=NULL);

p=p->Lchild;

)

while();

primf（“葉子結點的數目是：%d\n",leaf_num）;

)

3、用正鄰接鏈表保存有向圖，各結點的結構形式如下，所有的頂點結點放在數

組adjlist口中，統計圖中頂點的入度。

鏈表結點頂點結點

adjvexinfonextarcdataindegreefirstarc

Voidcount_indegree(ALGraph*G)

{intk;LinkNode*p;

for(k=0;k<G->vexnum;k++)

G->adjlist[k].indegree=O;

for(k=0;k<G->vexnum;k++)

{；

while(p!=NULL)

{G->adjlist[p->adjvex].indegree++;

4、H->R[s...m]中記錄關鍵字除H->R[s].key均滿足堆定義，調整H->R[s]的位置

使之成為小根堆。

VoidHeap_adjust(Sqlist*H,ints,intm)

{intj=s,k=2*j;/*計算H->R[j]的左孩子的位置*/

H->R[0]=H->R[j];/*臨時保存H->R[j]*/

for(k=2*j;k<=m;k=2*k)

{if((k<m)&&(H->R[k].key>H->R[k+l].key)

k++;/*選擇左、右孩子中關鍵字的最小者*/

if(H->R[O].key>H->R[k].key)

{H->R[j]=H->R[k];j=k;

；)

elsebreak;

五,編寫算法(要求給出相應的數據結構說明，14分)

設Hash函數為H(key)=keyMOD13,用鏈地址法解決沖突，請寫出進行散

列查找的算法。

《數據結構》模擬試題15參考答案

一、填空題（每小題2分，共18分）

1、順序（存儲）結構鏈式（存儲）結構

2、問題的規模

3、操作受限后進先出（先進后出）

4、232

5、2h-l

6、ne

7、順序存儲塊間有序

8、操作系統數據庫

9、歸并內、外存之間的數據交換

二、單項選擇題（請將答案寫在題目后的括號中。每題2分，共18分）

題號123456789

答案DCBADCDBA

三、分析題（每題6分，共30分）

1、解：轉換后得到的二叉樹如圖（a）,前序線索樹如圖（b）,中序線索樹如圖（c）。

2、J圖（a）轉換后的二叉樹在鄰接圖（b）前序線索樹鄰接鏈表力圖⑹中序線索樹

圖(a)有向圖

圖(b)有向圖

roo9oooo8

cooooo4oo

56oo4oo

oooooooooo

00J

co210oo

(c)鄰接矩陣

3、解：將關鍵字序列(17,19,13,7,15,9,25)依此插入到初態為空的二叉排序樹

中所得到的二叉排序樹T如圖(a)所示；刪除13之后的二叉排序樹T1如圖(b)所示。

圖(a)生成的二叉排序樹T的過程

圖(b)刪除13的二叉排序樹TI

4、解：根據所給定的散列函數和處理沖突方法，其地址計算過程如下：

H(31)=21MOD13=8H(25)=25MOD13=12H(28)=18MOD13=2

H(19)=19MOD13=6H(42)=42MOD13=3H(57)=57MOD13=5

H(15)=15MOD13=2沖突H(15)=(2+1)MOD13=3沖突

H(15)=(3+l)MOD13=4

H(43)=43MOD13=4沖突H(43)=(4+l)MOD13=5沖突

H(43)=(5+l)MOD13=6沖突H(43)=(6+l)MOD13=7

H(22)=22MOD13=9H(36)=36MOD13=10

H(49)=49MOD13=10沖突H(49)=(10+1)MOD13=11

H(27)=27MOD13=1H(65)=65MOD13=0

得到的散列表結構如下：

散列地址0123456789101112

關鍵字65272842155719433122364925

成功查找的平均查找長度：ASL=(1X9+2X2+2X3)/13=19/13

5、解：采用選擇排序號方法做非遞減排序的過程如下:

初始關鍵字：3529221617938271345

第一趟排序：9292216173538271345

第二趟排序：9132216173538272945

第三趟排序：9131622173538272945

第四趟排序：9131617223538272945

第五趟排序：91316172227383529