數(shù)據(jù)結(jié)構(gòu)模擬卷(含答案)經(jīng)典習(xí)題

千里之行，始于足下讓知識(shí)帶有溫度。第第2頁/共2頁精品文檔推薦數(shù)據(jù)結(jié)構(gòu)模擬卷(含答案)經(jīng)典習(xí)題練習(xí)題

一、單項(xiàng)挑選題

1.若將數(shù)據(jù)結(jié)構(gòu)形式定義為二元組(K，R)，其中K是數(shù)據(jù)元素的有限集合，則R是K上()

A.操作的有限集合

B.映象的有限集合

C.類型的有限集合

D.關(guān)系的有限集合

2.在長度為n的挨次表中刪除第i個(gè)元素(1≤i≤n)時(shí)，元素移動(dòng)的次數(shù)為()

A.n-i+1

B.i

C.i+1

D.n-i

3.若不帶頭結(jié)點(diǎn)的單鏈表的指針為head，則該鏈表為空的判定條件是()

A.head==NULL

B.head->next==NULL

C.head!=NULL

D.head->next==head

4.引起循環(huán)隊(duì)列隊(duì)頭位置發(fā)生變化的操作是()

A.出隊(duì)

B.入隊(duì)

C.取隊(duì)頭元素

D.取隊(duì)尾元素

5.若進(jìn)棧序列為1，2，3，4，5，6，且進(jìn)棧和出棧可以穿插舉行，則不．可能浮現(xiàn)的出棧序列是()

A.2，4，3，1，5，6

B.3，2，4，1，6，5

C.4，3，2，1，5，6

D.2，3，5，1，6，4

1

6.字符串通常采納的兩種存儲(chǔ)方式是()

A.散列存儲(chǔ)和索引存儲(chǔ)

B.索引存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)

C.挨次存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)

D.散列存儲(chǔ)和挨次存儲(chǔ)

7.數(shù)據(jù)結(jié)構(gòu)是（）

A．一種數(shù)據(jù)類型

B．?dāng)?shù)據(jù)的存儲(chǔ)結(jié)構(gòu)

C．一組性質(zhì)相同的數(shù)據(jù)元素的集合

D．互相之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合

8.算法分析的目的是（）

A．分辨數(shù)據(jù)結(jié)構(gòu)的合理性

B．評(píng)價(jià)算法的效率

C．討論算法中輸入與輸出的關(guān)系

D．鑒別算法的可讀性

9.在線性表的下列運(yùn)算中，不．轉(zhuǎn)變數(shù)據(jù)元素之間結(jié)構(gòu)關(guān)系的運(yùn)算是

（）

A．插入B．刪除

C．排序D．定位

10.下列圖示的挨次存儲(chǔ)結(jié)構(gòu)表示的二叉樹是()

2

11.設(shè)串sl=″DataStructureswithJava″,s2=″it″，則子串定位函數(shù)

index(s1,s2)的值為(）

A．15B．16

C．17D．18

12.二維數(shù)組A[8][9]按行優(yōu)先挨次存儲(chǔ)，若數(shù)組元素A[2][3]的存儲(chǔ)

地址為1087，A[4][7]的存儲(chǔ)地址為1153，則數(shù)組元素A[6][7]的存儲(chǔ)地址為（）

A．1213B．1209

C．1211D．1207

13.在按中序遍歷二叉樹的算法中，需要借助的輔助數(shù)據(jù)結(jié)構(gòu)是

（）

A．隊(duì)列B．棧

C．線性表D．有序表

3

14.在隨意一棵二叉樹的前序序列和后序序列中，各葉子之間的相對(duì)

次序關(guān)系（）

A．不一定相同B．都相同

C．都不相同D．互為逆序

15.若采納孩子兄弟鏈表作為樹的存儲(chǔ)結(jié)構(gòu)，則樹的后序遍歷應(yīng)采納

二叉樹的（）

A．層次遍歷算法B．前序遍歷算法

C．中序遍歷算法D．后序遍歷算法

16.若用鄰接矩陣表示一個(gè)有向圖，則其中每一列包含的″1″的個(gè)

數(shù)為（）

A．圖中每個(gè)頂點(diǎn)的入度B．圖中每個(gè)頂點(diǎn)的出度

C．圖中弧的條數(shù)D．圖中連通重量的數(shù)目

17.圖的鄰接矩陣表示法適用于表示（）

A．無向圖B．有向圖

C．稠密圖D．稀疏圖

18.若有序表的關(guān)鍵字序列為（b,c,d,e,f,g,q,r,s,t），則在二分查找關(guān)鍵

字b的過程中，先后舉行比較的關(guān)鍵字依次為（）A．f,c,bB．f,d,b

C．g,c,bD．g,d,b

19.下面程序段的時(shí)光復(fù)雜度為()

s=0；

4

for(i=1；inext=s->next；s->next=p；

B.s->next=p；q->next=s->next；

C.p->next=s->next；s->next=q；

D.s->next=q；p->next=s->next；

21.在計(jì)算機(jī)內(nèi)實(shí)現(xiàn)遞歸算法時(shí)所需的輔助數(shù)據(jù)結(jié)構(gòu)是()

A.棧

B.隊(duì)列

C.樹

D.圖

22.通常將鏈串的結(jié)點(diǎn)大小設(shè)置為大于1是為了()

A.提高串匹配效率

B.提高存儲(chǔ)密度

C.便于插入操作

D.便于刪除操作

23.帶行規(guī)律的三元組表是稀疏矩陣的一種()

A.挨次存儲(chǔ)結(jié)構(gòu)

B.鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

C.索引存儲(chǔ)結(jié)構(gòu)

D.散列存儲(chǔ)結(jié)構(gòu)

24.用二叉鏈表表示具有n個(gè)結(jié)點(diǎn)的二叉樹時(shí)，值為空的指針域的個(gè)

5

數(shù)為()

A.n-1

B.n

C.n+l

D.2n

25.為便于判別有向圖中是否存在回路，可借助于()

A.廣度優(yōu)先搜尋算法

B.最小生成樹算法

C.最短路徑算法

D.拓?fù)渑判蛩惴?/p>

26.連通網(wǎng)的最小生成樹是其全部生成樹中()

A.頂點(diǎn)集最小的生成樹

B.邊集最小的生成樹

C.頂點(diǎn)權(quán)值之和最小的生成樹

D.邊的權(quán)值之和最小的生成樹

27.按排序過程中依據(jù)的原則分類，迅速排序?qū)儆?)

A.插入類的排序辦法

B.挑選類的排序辦法

C.交換類的排序辦法

D.歸并類的排序辦法

28.在長度為32的有序表中舉行二分查找時(shí)，所需舉行的關(guān)鍵字比較次數(shù)最多為()

A.4

B.5

C.6

D.7

29.假設(shè)在構(gòu)建散列表時(shí)，采納線性探測(cè)解決矛盾。若延續(xù)插入的n個(gè)關(guān)鍵字都是同義

詞，則查找其中最后插入的關(guān)鍵字時(shí)，所需舉行的比較次數(shù)為()

A.n-1

B.n

6

C.n+l

D.n+2

30.若有序表的關(guān)鍵字序列為（b,c,d,e,f,g,q,r,s,t），則在二分查找關(guān)鍵

字b的過程中，先后舉行比較的關(guān)鍵字依次為（）A．f,c,bB．f,d,b

C．g,c,bD．g,d,b

二、填空題

1.數(shù)據(jù)的規(guī)律結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)器內(nèi)的表示，稱為數(shù)據(jù)的____________。

2.已知雙向循環(huán)鏈表結(jié)點(diǎn)中，域prior指向前一結(jié)點(diǎn)，域next指向后一結(jié)點(diǎn)，則刪除當(dāng)前結(jié)點(diǎn)指針p的前驅(qū)結(jié)點(diǎn)(存在)應(yīng)執(zhí)行的語句是____________。

3.棧下溢是指在____________時(shí)舉行出棧操作，棧上溢是指在____________時(shí)舉行入棧操作。

4.已知substr(s,i,len)函數(shù)的功能是返回串s中第i個(gè)字符開頭長度為len的子串，strlen(s)函數(shù)的功能是返回串s的長度。若s=”ABCDEFGHIJK″,t=”ABCD″,執(zhí)行運(yùn)算substr(s,strlen(t),strlen(t))后的返回值為____________。

5.已知徹低二叉樹T的第5層惟獨(dú)7個(gè)結(jié)點(diǎn)，則該樹共有____________個(gè)葉子結(jié)點(diǎn)

6.在有向圖中，以頂點(diǎn)v為盡頭的弧的數(shù)目稱為v的____________,以頂點(diǎn)v為源點(diǎn)的弧的數(shù)目稱為v的_____________。

7

7.假設(shè)以數(shù)組seqn［m］存放循環(huán)隊(duì)列的元素，設(shè)變量rear和quelen分離指示循環(huán)隊(duì)列中隊(duì)尾元素的位置和元素的個(gè)數(shù)。寫出普通狀況下隊(duì)頭元素位置的表達(dá)式。

假如用變量front和quelen分離指示循環(huán)隊(duì)列中隊(duì)頭元素的位置和元素的個(gè)數(shù)，則寫出普通狀況下隊(duì)尾元素位置的表達(dá)式。

8.已知二叉樹如下，寫出它的先序序列、中序序列和后序序列

9.稱算法的時(shí)光復(fù)雜度為O(f(n))，其含義是指算法的執(zhí)行時(shí)光和_______的數(shù)量級(jí)相同。

10.在一個(gè)長度為n的單鏈表L中，刪除鏈表中*p的前驅(qū)結(jié)點(diǎn)的時(shí)光復(fù)雜度為_________，刪除*p結(jié)點(diǎn)的時(shí)光復(fù)雜度為_____________。

11.假設(shè)為循環(huán)隊(duì)列分配的向量空間為Q[20]，若隊(duì)列的長度和隊(duì)頭指針值分離為13和17，則當(dāng)前尾指針的值為______。

12.一棵含999個(gè)結(jié)點(diǎn)的徹低二叉樹的深度為_______,深度為10的滿二叉樹有________個(gè)結(jié)點(diǎn)。

13.含n個(gè)頂點(diǎn)的無向連通圖中至少含有______條邊。

8

14..已知有向圖G的定義如下：

G=(V，E)

V={a，b，c，d，e}

E={，，，，，，}

(1)畫出G的圖形；

(2)寫出G的所有拓?fù)湫蛄小?/p>

15.線性表的鏈接存儲(chǔ)比挨次存儲(chǔ)的優(yōu)點(diǎn)是：________________操作不需移動(dòng)結(jié)點(diǎn)。

16.孩子兄弟鏈表表示的樹結(jié)構(gòu)，其后根遍歷結(jié)果同二叉樹的___________.全都。

17.哈夫曼樹又稱__________.其定義是______________________

18隊(duì)列是一種__________線性表，而棧是____________線性表。

19.畫出與如圖所示森林對(duì)應(yīng)的二叉樹。

20.下列線索化的樹稱為___________________，畫出中序線素二叉樹的線索表示。

9

21.

填寫語句完成對(duì)挨次表的初始化

#defineLIST_INIT_SIZE100

typedefstruct{

ElemType*elem;//存儲(chǔ)空間起始地址

intlength;//線性表長度

intlistSize;//分配容量

}SqList;

StatusinitList_Sq(SqList

if(!l.elem)exitERROR;

__________________________;

__________________________;

returnOK;

}

22.普通而言，若二叉樹的結(jié)點(diǎn)，其左子樹的全部結(jié)點(diǎn)小于根結(jié)點(diǎn)，

10

而右子樹的全部結(jié)點(diǎn)大于根結(jié)點(diǎn)，則二叉樹稱為________________;假如結(jié)點(diǎn)的左子樹深度和右子樹深度之差的肯定值不超過1，則二叉樹稱為________________.

三、解答題

1.已知二叉樹的先序序列和中序序列分離為HDACBGFE和ADCBHFEG。

（1）畫出該二叉樹；

（2）畫出與（1）求得的二叉樹對(duì)應(yīng)的森林。

2.從空樹起，依次插入關(guān)鍵字37，50，42，18，48，12，56，30，23，構(gòu)造一棵二叉排序樹。

（1）畫出該二叉排序樹；

（2）畫出從（1）所得樹中刪除關(guān)鍵字為37的結(jié)點(diǎn)之后的二叉排序樹。

3.已知用有序鏈表存儲(chǔ)整數(shù)集合的元素。閱讀算法f3，并回答下列

問題：

（1）寫出執(zhí)行f3（a,b）的返回值，其中a和b分離為指向存儲(chǔ)集合{2，4，5，7，9，12}和{2，4，5，7，9,12}的鏈表的頭指針；（2）簡(jiǎn)述算法f3的功能；

（3）寫出算法f3的時(shí)光復(fù)雜度。

intf3(LinkListha,LinkListhb)

{

11

//LinkList是帶有頭結(jié)點(diǎn)的單鏈表

//ha和hb分離為指向存儲(chǔ)兩個(gè)有序整數(shù)集合的鏈表的頭指針

LinkListpa,pb;

pa=ha->next;

pb=hb->next;

while(pa

pb=pb->next;

}

if(pa==NULL

elsereturn0;

}

4.已知稀疏矩陣采納三元組表表示，其形式說明如下：

#defineMaxSize100//稀疏矩陣的最大行數(shù)

typedefstruct{

inti,j,v;//行號(hào)、列號(hào)、元素值

}TriTupleNode;

typedefstruct{

TriTupleNodedata[MaxSize];

intm,n,t;//矩陣的行數(shù)、列數(shù)和非零元個(gè)數(shù)

}RTriTupleTable;

12

下列算法f4的功能是，以行優(yōu)先的挨次輸入稀疏矩陣的非零元（行號(hào)、列號(hào)、元素值），建立稀疏矩陣的三元組表存儲(chǔ)結(jié)構(gòu)。請(qǐng)?jiān)诳杖碧幪钊牒线m內(nèi)容，使其成為一個(gè)完整的算法。（注：矩陣的行、列下標(biāo)均從1起計(jì)）

voidf4(RTriTupleTable

scanf(″%d%d%d″,

k=1;//k指示當(dāng)前輸入的非零元的行號(hào)

for(i=0;①；i++)

{scanf(″%d%d%d″,②，

③，_________④_____________;

}

}

5.已知二叉樹的存儲(chǔ)結(jié)構(gòu)為二叉鏈表，其類型定義如下：

typedefstructNodeType{

DataTypedata;

structNodeType*lchild,*rchild;

}BinTNode,*BinTree;

閱讀算法f5，并回答下列問題：

(1)對(duì)于如圖所示的二叉樹，畫出執(zhí)行算法f5的結(jié)果；

13

（2）簡(jiǎn)述算法f5的功能。

BinTreef5(BinTreebt1)

{

BinTreebt2;

if(bt1==NULL)

bt2=NULL;

else{

bt2=(BinTNode*)malloc(sizeof(BinTNode));

bt2->data=bt1->data;

bt2->rchild=f5(bt1->lchild);

bt2->lchild=f5(bt1->rchild);

}

returnbt2;

}

6.已知圖的鄰接表表示的形式說明如下：

#defineMaxNum50//圖的最大頂點(diǎn)數(shù)

typedefstructnode{

14

intadjvex;//鄰接點(diǎn)域

structnode*next;//鏈指針域

}EdgeNode;//邊表結(jié)點(diǎn)結(jié)構(gòu)描述

typedefstruct{

charvertex;//頂點(diǎn)域

EdgeNode*firstedge;//邊表頭指針

}VertexNode;//頂點(diǎn)表結(jié)點(diǎn)結(jié)構(gòu)描述

typedefstruct{

VertexNodeadjlist［MaxNum］;//鄰接表

intn,e;//圖中當(dāng)前的頂點(diǎn)數(shù)和邊數(shù)

}ALGraph;//鄰接表結(jié)構(gòu)描述

下列算法輸出圖G的深度優(yōu)先生成樹(或森林)的邊。閱讀算法，并在空缺處填入合適的內(nèi)容，使其成為一個(gè)完整的算法。

typedefenum{FALSE,TRUE}Boolean;

Booleanvisited［MaxNum］;

voidDFSForest(ALGraph*G){

inti;

for(i=0;in;i++)visited［i］=(1);

for(i=0;in;i++)if(!visited［i］)DFSTree(G,i);

}

voidDFSTree(ALGraph*G,inti){

15

EdgeNode*p;

visited［i］=TRUE;

p=G->adjlist［i］.firstedge;

while(p!=NULL){

if(!visited［p->adjvex］){

printf(″″,G->adjlist［i］.vertex,

G->adjlist［p->adjvex］.vertex);

(2);

}

(3);

}

}

參考答案

16

二。填空題

1.存儲(chǔ)結(jié)構(gòu)（或存儲(chǔ)映像）

2.p->prior=p->prior->prior;

p->prior->next=p;

3.棧