自考數(shù)據(jù)結(jié)構(gòu)歷年試題及答案

自考數(shù)據(jù)結(jié)構(gòu)02331歷年試題及答案

全國(guó)自學(xué)考試數(shù)據(jù)結(jié)構(gòu)試題

、單項(xiàng)選擇題（本大題共15小題，每題2分，共30分）

在每題列出的四個(gè)備選項(xiàng)中只有一個(gè)是符合題目要求的，請(qǐng)將其代碼填寫在題后的括號(hào)內(nèi)。錯(cuò)選、多項(xiàng)選擇或未選均

無分。

1.以下程序段的時(shí)間復(fù)雜度為()9

s=0；

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

for(j=l；j<n；j++)

s+=iXj；

A.0(1)B.0(n)

C.0(2n)DOS?)

2.假設(shè)某個(gè)帶頭結(jié)點(diǎn)的單鏈表的頭指針為head,則判定該表為空表的條件是（)22

A.head二二NULL；B.head->next==NULL；

C.head!=NULL；D.head->next==head；

3.棧是一種操作受限的線性結(jié)構(gòu)，其操作的主要特征是（)32

A.先進(jìn)先出B.后進(jìn)先出

C.進(jìn)優(yōu)于出D.出優(yōu)于進(jìn)

4.假設(shè)以數(shù)組An］存放循環(huán)隊(duì)列的元素，其頭、尾指針分別為front和rear。假設(shè)設(shè)定尾指針指向隊(duì)列中的隊(duì)尾元素，頭

指針指向隊(duì)列中隊(duì)頭元素的前一個(gè)位置，則當(dāng)前存于隊(duì)列中的元素個(gè)數(shù)為（)

A.（rear-front-1）%nB.（rear-front）%n

C.（front-rear+1）%nD.（rear-front+n）%n

5.推斷兩個(gè)串大小的根本準(zhǔn)則是（）52

A.兩個(gè)串長(zhǎng)度的大小B.兩個(gè)串中首字符的大小

C.兩個(gè)串中大寫字母的多少D.對(duì)應(yīng)的第一個(gè)不等字符的大小

6.二維數(shù)組A4］5］按行優(yōu)先順序存儲(chǔ),假設(shè)每個(gè)元素占2個(gè)存儲(chǔ)單元，且第一個(gè)元素A0］0］的存儲(chǔ)地址為1000,則數(shù)組元

素A3]2]的存儲(chǔ)地址為()60

A.1012B.1017

C.1034D.1036

a00a01a02a03a04

a32

7.高度為5的完全二叉樹中含有的結(jié)點(diǎn)數(shù)至少為（)72

A16B.17

C.31D.32

8.已知在一棵度為3的樹中，度為2的結(jié)點(diǎn)數(shù)為4,度為3的結(jié)點(diǎn)數(shù)為3,則該樹中的葉子結(jié)點(diǎn)數(shù)為（)

A.5B.8

C.11D.18

9.以下所示各圖中是中序線索化二叉樹的是（)81A

NULLNULLNULL

D.

NULL也)、NULL

10.已知含6個(gè)頂點(diǎn)（vo,vi,V2,V3,v4,V5）的無向圖的鄰接矩陣如下圖，則從頂點(diǎn)V0出發(fā)進(jìn)行深度優(yōu)先遍歷可能得到的頂

點(diǎn)訪問序列為（）108

A.（Vo,Vl,V,V5>V4>V3）012345

200011000

1XL1101100

2V2110001

3V3010000

4V4000001

5V5001010

題10圖題11圖

B.(Vo,Vl,V2,V3,V4,v5)

C.(Vo,Vl,Vs,v2,v3,v4)

D.(vo,Vl,V4,V5,V2,v3)

11.如下圖有向圖的一個(gè)拓?fù)湫蛄惺?)

A.ABCDEF

B.FCBEAD

C.FEDCBA

D.DAEBCF

12.以下關(guān)鍵字序列中，構(gòu)成大根堆的是（）

A.5,8,1,3,9,6,2,7B.9,8,1,7,5,6,2,33

C.9,8,6,3,5,1,2,7D.9,8,6,7,5,1,2,3

13.對(duì)長(zhǎng)度為15的有序順序表進(jìn)行二分查找，在各記錄的查找概率均相等的情況下，查找成功時(shí)所需進(jìn)行的關(guān)鍵字比擬次

數(shù)的平均值為（）172

14.已知一個(gè)散列表如下圖，其散列函數(shù)為H（key）=key%ll,采納二次探查法處理沖突，則下一個(gè)插入的關(guān)鍵字49的地址

為（D）d197

|||||15|38|61|84|III

A.2B.3012345678910

C.8D.9題14圖

15.數(shù)據(jù)庫(kù)文件是由大量帶有結(jié)構(gòu)的（）206

A.記錄組成的集合B.字符組成的集合

C.數(shù)據(jù)項(xiàng)組成的集合D.數(shù)據(jù)結(jié)構(gòu)組成的集合

二、填空題（本大題共10小題，每題2分，共20分）

請(qǐng)?jiān)诿款}的空格中填上正確答案。錯(cuò)填、不填均無分。

16.估算算法時(shí)間復(fù)雜度時(shí)考慮的問題規(guī)模通常是指算法求解問題的—輸入量___。8

17.在雙向循環(huán)鏈表中插入一個(gè)新的結(jié)點(diǎn)時(shí)，應(yīng)修改4個(gè)揖性續(xù)的值。28

18.假設(shè)進(jìn)棧序列為a,b,c,且進(jìn)棧和出?？梢源┎暹M(jìn)行，則可能出現(xiàn)—5個(gè)不同的出棧序列。5

19.鏈串的結(jié)點(diǎn)大小定義為結(jié)點(diǎn)的數(shù)據(jù)域—中存放的字符個(gè)數(shù)。54

20.廣義表（a,（d,（c）））的深度為—3?67

21.在含有3個(gè)結(jié)點(diǎn)a,b,c的二叉樹中，前序序列為abc且后序序列為cba的二叉樹有4棵。4

22.假設(shè)用鄰接矩陣表示有向圖，則頂點(diǎn)i的入度等于矩陣中o第i列非零元素的個(gè)數(shù)107

23.對(duì)關(guān)鍵字序列（15,18,11,13,19,16,12,17,10,8）進(jìn)行增量為5的一趟希爾排序的結(jié)果為

15,12,11,10,8,16,18,17

24.索引順序查找的索引表由各分塊中的最大關(guān)鍵字及各分塊的起始位置—構(gòu)成。173

25.VSAM文件的完成依賴于操作系統(tǒng)中的分頁(yè)存取方法的功能。215

三、解答題（本大題共4小題，每題5分，共20分）

26.假設(shè)有一個(gè)形如

（\

ad18

a27a28

a81a82a88

的8X8矩陣，矩陣元素都是整型量(次對(duì)角線以上的元素都是0)。

假設(shè)將上述矩陣中次對(duì)角線及其以下的元素按行優(yōu)先壓縮存儲(chǔ)在一維數(shù)組B中，請(qǐng)答復(fù)以下問題:

(DB數(shù)組的體積至少是多少

(2)假設(shè)a18存儲(chǔ)在B0］中，a$6存儲(chǔ)在Bk］中，則k值為多少

(1)(1+8)X8/2=36存放次對(duì)角線以上的零為37

(2)12

27.對(duì)關(guān)鍵字序列(5,8,1,3,9,6,2,7)按從小到大進(jìn)行快速排序。

(1)寫出排序過程中前兩趟的劃分結(jié)果；

(2)快速排序是否是穩(wěn)定的排序方法

(1)

第一趟劃分結(jié)果；(2,3,1),5,(9,6,8,7)

第二趟劃分結(jié)果；(1,2,3),5,(9,6,8,7)

第三趟劃分結(jié)果；(L2,3),5,(7,6,8,9)

第四趟劃分結(jié)果；1,2,3,5,6,7,8,9

第一趟劃分過程

23159687

12359687

12357689

12356789

ti

(5,8,1,3,9,6,2,7)

1.(2,8,1,3,9,6,5,7)

2.(2,5,1,3,9,6,8,7)

3.(2,3,1,5,9,6,8,7)

4.(2,3,1,5,9,6,8,7)

第二趟劃分過程

(2,3,1,5,9,6,8,7)

1.(1,2,3,5,7,6,8,9)

(2)非穩(wěn)定

23159687

12235

57689

56789

.A；.

T1

第一趟：[2,3,1)5[9,6,8,7)

第二趟：1,2,3,5〔9,6,8,7)

第三趟：1,2,3,5,〔7,6,8〕，9

第四趟：1,2,3,5,6,7,8,9

28.假設(shè)通信電文使用的字符集為{a,b,c,d,e,f,g,h},各字符在電文中出現(xiàn)的頻度分別為：7,26,2,28,13,10,

3,11,試為這8個(gè)字符設(shè)計(jì)哈夫曼編碼。要求：

(1)畫出你所構(gòu)造的哈夫曼樹(要求樹中左孩子結(jié)點(diǎn)的權(quán)值不大于右孩子結(jié)點(diǎn)的權(quán)值)；

(2)按左分支為0和右分支為1的規(guī)則，分別寫出與每個(gè)字符對(duì)應(yīng)的編碼。

(1)

(2)

29.已知3階B一樹如下圖,

題29圖

非根[L2]P184

根[1,2]

(1)畫出將關(guān)鍵字6插入之后的B一樹;

四、算法閱讀題(本大題共4小題，每題5分，共20分)

30.假設(shè)以帶頭結(jié)點(diǎn)的單鏈表表示線性表，單鏈表的類型定義如下:

typedefintDataType;

typedefstructnode(

DataTypedata;

structnodeXnext;

}LinkNode,XLinkList;

閱讀以下算法，并答復(fù)以下問題：

(1)已知初始鏈表如下圖，畫出執(zhí)行f30(head)之后的鏈表；

head

題30圖

(2)簡(jiǎn)述算法f30的功能。

voidf30(LinkListhead)

{LinkListp,r,s;

if(head->next){

r=head->next;

p=r->next;

r->next=NULL;

while(p){

s=p;

p=p->next;

if(s->data%2==0){

s->next=head->next;

head->next=s;

}else{

s->next=r->next;

r->next=s;

r=s;

)

)

)

(1)

(2)

31.假設(shè)以二叉鏈表表示二叉樹，其類型定義如下：

typedefstructnode{

DataTypedata;

structnodeXIchild,Xrchild;〃左右孩子指針

}XBinTree;

閱讀以下算法，并答復(fù)以下問題：

(1)已知以T為根指針的二叉樹如下圖，

寫出執(zhí)行f31(T)之后的返回值；

(2)簡(jiǎn)述算法f31的功能。

intf31(BinTreeT)

{intd;

if(!T)return0;

d=f31(T->Ichild)+f31(T->rchild);

if(T->Ichild&T->rchild)

題31圖

returnd+1;

else

returnd;

(1)3

(2)統(tǒng)計(jì)度為2的結(jié)點(diǎn)個(gè)數(shù)

32.設(shè)有向圖鄰接表定義如下:

typedefstruct{

VertexNodeadjlistMaxVertexNum;

intn,e；//圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù)結(jié)構(gòu)為：|vertex|firstedgQ

}ALGraph；//鄰接表類型

adjvexnext

其中頂點(diǎn)表結(jié)點(diǎn)VertexNode

邊表結(jié)點(diǎn)EdgeNode結(jié)構(gòu)為：

閱讀以下算法，并答復(fù)以下問題：

(1)已知某有向圖存儲(chǔ)在如下圖的鄰接

表G中，寫出執(zhí)行f32(&G)的輸出；

⑵簡(jiǎn)述算法f32的功能。

intvisitedMaxNum];

voidDFS(ALGraphXG,inti){

EdgeNodeXp;

visitedi二TRUE

if(G->adjlisti].firstedge二二NULL)

printf(〃％c〃，G->adjlisti].vertex)；

else{

p=G->adjlisti].firstedge;

while(p!=NULL){

if(!visitedp->adjvex)

DFS(G,p->adjvex);

p=p->next;

)

)

}

voidf32(ALGraphXG){

inti;

for(i=0;i<G->n;i++)

visitedi=FALSE;

for(i=0;i<G->n;i++)

if(!visitedi)DFS(G,i)

)

(l)ABECD

⑵圖的深度優(yōu)先搜尋

33.以下算法f33的功能是對(duì)記錄序列進(jìn)行雙向冒泡排序。算法的根本思想為，先從前往后通過交換將關(guān)鍵字最大的記錄移

動(dòng)至后端，然后從后往前通過交換將關(guān)鍵字最小的記錄移動(dòng)至前端，如此反復(fù)進(jìn)行，直至整個(gè)序列按關(guān)鍵字遞增有序?yàn)?/p>

止。請(qǐng)?jiān)诳杖碧幪钊脒m宜的內(nèi)容，使其成為完整的算法。

defineMAXLEN100

typedefintKeyType;

typedefstruct(

KeyTypekey;

InfoTypeotherinfo;

}NodeType;

typedefNodeTypeSqListMAXLEN];

voidf33(SqListR,intn)

{inti,j,k;

NodeTypet;

i=0；

j=n-l;

while(i<j){

for((1))k=i;k<j;k++

if(Rk].key>Rk+1].key){

t=Rk];

Rk=Rk+1];

Rk+1=t;

)

j-；

for(k=j;k>i;k--)

if((2)){Rk].key<Rk-1].key

t=Rk];

Rk=Rk-1];

Rk-l=t;

)

⑶；i++

)

)

(1)

(2)

(3)

五、算法設(shè)計(jì)題(本大題10分)

34.假設(shè)以帶頭結(jié)點(diǎn)的單鏈表表示線性表，單鏈表的類型定義如下：

typedefintDataType;

typedefstructnode{

DataTypedata;

structnodeXnext;

}LinkNode,XLinkList;

編寫算法，刪除線性表中最大元素(假設(shè)最大值唯一存在)。函數(shù)原型為：

voidf34(LinkListhead)

{

LinkNodeXp,Xmax,Xq;

P=head->next;

max=head->next;

while(P)

P=p->next;

If(p->data>max->data)max=p;

)

x=max->data;

delete_L(LnodeXL,inti)

{LnodeXp,Xq;

intj;

Elemtypex;

P=L;j=O;

While(p->next!=null&&j<=i-1)

{p=p->next;j++；)

If(!P->next||i<l)

{Printf("\n刪除位置錯(cuò)誤！");return(-l);}

Else{q=p->next;x=q->data;

P->next=q->next;free(q);

Return(x);

)

}/Xdelete_LX/

全國(guó)202X年10月自學(xué)考試數(shù)據(jù)結(jié)構(gòu)試題

一、單項(xiàng)選擇題(本大題共15小題，每題2分，共30分〕在每題列出的四個(gè)備選項(xiàng)

中只有一個(gè)是符合題目要求的，請(qǐng)將其代碼填寫在題后的括號(hào)內(nèi)。錯(cuò)選、多項(xiàng)選擇或未選均

無分。

1.按值可否分解，數(shù)據(jù)類型通常可分為兩類，它們是(C)

A.靜態(tài)類型和動(dòng)態(tài)類型

B.原子類型和表類型

C.原子類型和結(jié)構(gòu)類型

D.數(shù)組類型和指針類型

2

舒舞岫I嬴圓岫，貨+%000,跑)二8/+8/1+2008fflh(/i);8888疝町

+3乙例犍柳洲是()

A.A￡(11)是0伍(11))

B.Bg(n)是0(f(n))

C.Ch(n)是O(nlogn)

D.Dh(n)是0(n2)

答案：C

3.指針p、q和r依次指向某循環(huán)鏈表中三個(gè)相鄰的結(jié)點(diǎn)，交換結(jié)點(diǎn)Xq和結(jié)點(diǎn)Xr在表中次序的程

序段是()

A.p->next=r；q->next=r->next；r->next=q；

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

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

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

答案：A

4.假設(shè)進(jìn)棧次序?yàn)閍,b,c,且進(jìn)棧和出?？梢源┎暹M(jìn)行，則可能出現(xiàn)的含3個(gè)元素的出棧序列

個(gè)數(shù)是()

A.3

B.5

C.6

D.7

答案：B

5.假設(shè)以數(shù)組A[n]存放循環(huán)隊(duì)列的元素，其頭指針front指向隊(duì)頭元素的前一個(gè)位置、尾指

針rear指向隊(duì)尾元素所在的存儲(chǔ)位置，則在少用一個(gè)元素空間的前提下，隊(duì)列滿的判定條件為()

A.rear==frontintstr(char+5)|

B.(front+1)%n==rear

char*p=5；

C.rear+l==front

D.(rear+1)%n==frontwhile(*p!=7\0)p++；

答案：Dreturnp-5;

6.串的操作函數(shù)str定義為:

A.3

B.4

C.5

D.6

答案：c

7.二維數(shù)組A[10]：6]采納行優(yōu)先的存儲(chǔ)方法，假設(shè)每個(gè)元素占4個(gè)存儲(chǔ)單元，已知元素

A[3][4]的存儲(chǔ)地址為1000,則元素A[4][3]的存儲(chǔ)地址為()

A.1020

B.1024

C.1036

D.1240

答案：A

8.對(duì)廣義表1=(a,())執(zhí)行操作tail(L)的結(jié)果是()

A.()

B.(())

C.a

D.

答案：B

9.已知二叉樹的中序序列和后序序列均為ABCDEF,則該二叉樹的先序序列為()

A.FEDCBA

考證素材

B.ABCDEF

C.FDECBA

D.FBDCEA

答案：A

10.已知森林知{Tl,T2,T3,T4,T5},各棵樹Ti(i=L2,3,4,5)中所含結(jié)點(diǎn)的個(gè)數(shù)分別

為7,3,5,1,2,則與F對(duì)應(yīng)的二叉樹的右子樹中的結(jié)點(diǎn)個(gè)數(shù)為()

A.2

B.3

C.8

D.11

答案：D

11.假設(shè)非連通無向圖G含有21條邊，則G的頂點(diǎn)個(gè)數(shù)至少為()

A.7

B.8

C.21

D.22

答案：B

12.如下圖的有向圖的拓?fù)湫蛄惺?)

A.c,d,b,a,e

B.c,a,d,b,e

C.c,d,e,a,b

D.c,a,b,d,e

答案：B

13.對(duì)關(guān)鍵字序列(6,1,4,3,1,2,8,5)進(jìn)行快速排序時(shí)，以第1個(gè)元素為基準(zhǔn)的一次劃

分的結(jié)果為()

A.(5,1,4,3,6,2,8,7)

B.(5,1,4,3,2,6,7,8)

C.(5,1,4,3,2,6,8,7)

D.(8,7,6,5,4,3,2,1)

答案：C

考證素材

考證素材

14.分塊查找方法將表分為多塊，并要求()

A.塊內(nèi)有序

B.塊間有序

C.各塊等長(zhǎng)

D.鏈?zhǔn)酱鎯?chǔ)

答案：B

15.便于進(jìn)行布爾查詢的文件組織方法是()

A.順序文件

B.索引文件

C.散列文件

D.多關(guān)鍵字文件

答案：D

二、填空題(本大題共10小題，每題2分，假設(shè)有兩個(gè)空格，每個(gè)空格1分，共20分)請(qǐng)

在每個(gè)空格中填上正確答案。錯(cuò)填、不填均無分。

1.數(shù)據(jù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的特點(diǎn)是借助一指針—表示數(shù)據(jù)元素之間的邏輯關(guān)系。

2.如果需要對(duì)線性表一再進(jìn)行.插入—或—?jiǎng)h除—操作，則不宜采納順序存儲(chǔ)結(jié)構(gòu)。

3.如下圖，可以利用一個(gè)向量空間同時(shí)完成兩個(gè)類型相同的棧。其中棧1為空的條件是

topl=0,棧2為空的條件是top2=n-l,則“棧滿”的判定條件是—topl〉top2(或top2=topl-l或

topl=top2+l)o1|Itop2

棧1棧2

4.靜態(tài)存儲(chǔ)分配的順序串在進(jìn)行插入、置換和—聯(lián)接一等操作時(shí)可能發(fā)生越界。

5.廣義表L=(a,(b,()))的深度為_3_。

6.任意一棵完全二叉樹中，度為1的結(jié)點(diǎn)數(shù)最多為」

7.求最小生成樹的克魯斯卡爾(Kruskal)算法耗用的時(shí)間與圖中一邊—的數(shù)目正相關(guān)。

考證素材

考證素材

8.在5階B樹中，每個(gè)結(jié)點(diǎn)至多含4個(gè)關(guān)鍵字，除根結(jié)點(diǎn)之外，其他結(jié)點(diǎn)至少含_2_個(gè)關(guān)鍵字。

9.假設(shè)序列中關(guān)鍵字相同的記錄在排序前后的相對(duì)次序不變，則稱該排序算法是一穩(wěn)定—的o

10.常用的索引順序文件是—ISAM—文件和—VSAM—文件。

三、解答題（本康就幡xl貫科怖防他齪mi+j<n+|慟4,卿腑

L叮怖A幀它/按僦糊酈=箱長(zhǎng)媯曲+1）/2的一維麴53中送帆

東即//桃sa[0]o

⑴口n二10,丈"在sa[p]Jj小I、hp1??|；

（2必優(yōu)aj解詞k川削ihij新騰粉尤

答案：⑴p二8（2分）

（2）k=苧+i+j-n-l仇k=苧+j-n-l）

（3分）

LtZr

2.由字符集｛s,t,a,e,i｝及其在電文中出現(xiàn)的頻度構(gòu)建的哈夫曼樹

如下圖。

請(qǐng)依據(jù)該哈夫曼樹進(jìn)行譯碼，寫出原來的電文。

答案：eatst（說明：每個(gè)字母1分）（5分〕

3.已知無向圖G的鄰接表如下圖,

（1）畫出該無向圖；

考證素材

考證素材

(2)畫出該圖的廣度優(yōu)先生成森林。

A

B

C

D

E

F

GZI

HIT

1

4,對(duì)序列(48,37,63,96,22,31,50,55,11)進(jìn)行升序的堆排序，寫出構(gòu)建的初始(大根

)堆及前兩趟重建堆之后的序列狀態(tài)。

初始堆：

第1趟：

第2趟：

答案：初始堆：(96,55,63,48,22,31,50,37,11)(2分)

第1趟：(63,55,50,48,22,31,11,37,96)(2分)

考證素材

考證素材

第2趟：(55,48,50,37,22,31,11,63,96](1分)

四、算法閱讀題(本大題共4小題，每題5分，共20分)

1.閱讀以下算法，并答復(fù)以下問題：

(1)無向圖G如下圖，寫出算法f30(&G)的返回值；

(2)簡(jiǎn)述算法f30的功能。

defineMaxNum20

intvisited[MaxNum]；

voidDFS(GraphXg,inti)；

/X從頂點(diǎn)vi出發(fā)進(jìn)行深度優(yōu)先搜索，訪問頂點(diǎn)vj時(shí)置visited[j]為IX/

intf30(GraphXg)

{inti,k；

for(i=0；i<g->n；i++)/Xg->n為圖g的頂點(diǎn)數(shù)目X/

visited[i]=0；

for(i=k=0；i<g->n;i++)

if(visited[i]==0)

{k++；

DFS(g,i)；

}

returnk；

}

(1)

(2)

答案：⑴3[3分)

[2)返回?zé)o向圖g中連通重量的個(gè)數(shù)。[2分)

2.假設(shè)學(xué)生成績(jī)按學(xué)號(hào)增序存儲(chǔ)在帶頭結(jié)點(diǎn)的單鏈表中，類型定義如下:

typedefstructNode(

intid;/X學(xué)號(hào)X/

intscore；/X成績(jī)X/

structNodeXnext；

}LNode,XLinkList；

閱讀算法f31,并答復(fù)以下問題：

⑵簡(jiǎn)述算法f31的功能。

voidf31(LinkListA,LinkListB)

{LinkListp,q;

p=A->next;

q=B->next;

while(p&q)

{if(p->id<q->id)

考證素材

考證素材

p=p->next;

elseif(p->id>q->id)

q=q->next;

else

{if(p->score<60)

if(q->score<60)

p->score=q->score;

elsep->score=60;

p=p->next;

q=q->next;

（1）-

⑵⑴設(shè)軸結(jié)構(gòu)為idscorenext，期汰ASlBklMj喇肺陽(yáng)田1(A,B)

答案.—

島端的齦

gE

?

⑴(3小

一掰-f170-—238-f3%-f460561,1A

（娜海鈿他1分搬3物t）

（2）G諫A懈肝0雌喇墻”也誡枇焉

此城（屋B小伽瑜咻即:kB4的毓陽(yáng)；60年則也60分。（2分）

考證素材

考證素材

3.閱讀以下算法，并答復(fù)以下問題：

(1)設(shè)串s="OneWor1dOneDrearn",t=nOne”,pos

是一維整型數(shù)組，寫出算法

f32(s,t,pos)執(zhí)行之后得到的返回值和pos中的值;

⑵簡(jiǎn)述算法f32的功能。

intstrlen(charXs)；/X返回串s的長(zhǎng)度X/

intindex(charXst,charXt)；

/X假設(shè)串t在串st中出現(xiàn)，則返回在串st中首次出現(xiàn)

的下標(biāo)值，否則返回TX/

intf32(charXs,charXt,intpos□)

{inti,j,k,Is,It;

ls=strlen(s);

lt=strlen(t);

if(ls==0||lt==0)return-1;

k=0;

i=0;

do{

j=index(s+i,t);

if(j>=0)

{pos[k++]=i+j;

i+=j+it;

}

}while(i+it<=is&j>=0

returnk;

}

(1)

(2)

考證素材

考證素材

答案：⑴2；pos[0]=0,pos[1]=8(說明:每個(gè)值1分)[3分)

〔2〕返回串t在s中出現(xiàn)的次數(shù)，并將每次出現(xiàn)的位置依次存放在數(shù)組pos中。(2分〕

4.二叉排序樹的存儲(chǔ)結(jié)構(gòu)定義為以下類型：

typedefintKeyType;

typedefstructnode{

KeyTypekey;/X關(guān)鍵字項(xiàng)X/

InfoTypeotherinfo;/X其它數(shù)據(jù)項(xiàng)X/

structnodeXlchild,Xrchild;/X左、右孩子指針X/

}BSTNode,XBSTree；

閱讀算法f33,并答復(fù)以下問題：

⑴對(duì)如下圖的二叉排序樹T,寫出f33(T,8)返回的指針?biāo)附Y(jié)點(diǎn)的關(guān)鍵字；

⑵在哪些情況下算法f33返回空指針

⑶簡(jiǎn)述算法f33的功能。

BSTNodeXf33(BSTreeT,KeyTypex)

{BSTNodeXp;

if(T==NULL)returnNULL;

p=f33(T->lchild,x);

if(p!=NULL)returnp;

if(T->key>x)returnT;

returnf33(T->rchild,x);

(1)

⑵

⑶

答案：mio[2分)

(2〕T是空樹或T中全部結(jié)點(diǎn)的關(guān)鍵字均不大于給定值X時(shí)，返回空指針。(2分)

(3)如果二叉排序樹T中存在含有關(guān)鍵字大于給定值x的結(jié)點(diǎn)，則返回指針指向它們中關(guān)鍵字最

小的結(jié)點(diǎn)，否則返回空指針。(1分)

五、算法設(shè)計(jì)題(此題10分〕

1.假設(shè)線性表采納順序存儲(chǔ)結(jié)構(gòu)，其類型定義如下:

defineListSize100

typedefstruct{

intdata[ListSize];

intlength;

}SeqList,XTable;

編寫算法，將順序表L中全部值為奇數(shù)的元素調(diào)整到表的前端。

答案：參考答案一：

voidf34(TableL)(或者參數(shù)說明為：SeqListXL,1分)

{inti,j,t;

i=0；[初始化，1分)

考證素材

考證素材

j=L->length-l;

while（i〈j）（循環(huán)操縱，1分）

{while（i<j&&L->data[i]%2）（1分）

i++；

while（i<j&&L->data[j]%2==0）[1分）

J—；

if（i〈j）（條件推斷，1分）

{t=L->data[i];1交換，2分）

L->data[i]=L-〉data[j];

L->data[j]=t;

i++;（i和j,1分）

J—；

）

}（其他，如“L-〉〃表達(dá)，1分）

）

參考答案二：

voidf34（SeqListXL）（或者參數(shù)說明為：TableL,1分）

{inti,j=0,t;（初始化,1分）

for（i=0;i〈L-〉length;i++）（循環(huán)操縱，2分）

if（L->data[i]%2）/X奇數(shù)X/（奇數(shù)處理框架，1分）

{if（i!=j）（防止同一元素交換，1分）

{t=L-〉data[i];（交換，2分）

L->data[i]=L->data[j];

L->data[j]=t;

j++；11分）

）（其他，如“L->〃表達(dá)，1分〕

全國(guó)202X年1月自學(xué)考試數(shù)據(jù)結(jié)構(gòu)試題

一、單項(xiàng)選擇題(本大題共15小題，每題2分，共30分)

在每題列出的四個(gè)備選項(xiàng)中只有一個(gè)是符合題目要求的，請(qǐng)將其代碼填寫在題后的括號(hào)內(nèi)。錯(cuò)選'多項(xiàng)選擇或

未選均無分。

1.假設(shè)一個(gè)算法的時(shí)間復(fù)雜度用T(n)表示，其中n的含義是1A)

A.問題規(guī)模B.語(yǔ)句條數(shù)

C.循環(huán)層數(shù)D.函數(shù)數(shù)量

2.具有線性結(jié)構(gòu)的數(shù)據(jù)結(jié)構(gòu)是[C)線性結(jié)構(gòu)有：順序表、棧和隊(duì)列、串

A.樹B.圖

C.棧和隊(duì)列D.廣義表

3.將長(zhǎng)度為n的單鏈表連接在長(zhǎng)度為m的單鏈表之后，其算法的時(shí)間復(fù)雜度為(B)

A.0(1)B.0(m)

C.O(n)D.O(m+n)

插入到長(zhǎng)度為m的單鏈表，需找到表尾，時(shí)間復(fù)雜度為。(m),連接的時(shí)間復(fù)雜度為0(1),所以總的時(shí)間復(fù)雜度為0(m)

4.在帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表中插入一個(gè)新結(jié)點(diǎn)，需要修改的指針域數(shù)量是〔C〕

考證素材

考證素材

A.2個(gè)B.3個(gè)

C.4個(gè)D.6個(gè)

voidDInsertBefore(DListNodeXp,DataTypex)〃在帶頭結(jié)點(diǎn)的雙鏈表中，將值為x的新結(jié)點(diǎn)插入結(jié)點(diǎn)Xp之前，

設(shè)pWNULL{DListNodeXs=malloc(sizeof(ListNode));①

s->data=x;②s-〉prior=p->prior;③s-〉next=p;④p->prior-〉next=sGp-〉prior=s;}⑥

5.假設(shè)以數(shù)組A60］存放循環(huán)隊(duì)列的元素,其頭指針是front-47，當(dāng)前隊(duì)列有50個(gè)元素，則隊(duì)列的尾指針值為(B)

A.3B.37

C.50D.97

對(duì)于循環(huán)向量中的循環(huán)隊(duì)列，寫出通過隊(duì)頭隊(duì)尾指針表示的隊(duì)列長(zhǎng)度公式。［front指向?qū)嶋H隊(duì)頭，rear指向?qū)嶋H隊(duì)

尾的下一元素位置。)當(dāng)rear》front時(shí)，隊(duì)列長(zhǎng)度L=rear-front；當(dāng)rear<front時(shí)，L=m+(rear-front)。這兩種

情況可統(tǒng)一為L(zhǎng)=(m+(rear-front))%m,這里m為向量的大小。此題中m=60

6.假設(shè)棧采納鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，則以下說法中正確的選項(xiàng)是［B)

A.需要推斷棧滿且需要推斷?？?/p>

B.不需要推斷棧滿但需要推斷?？?/p>

C.需要推斷棧滿但不需要推斷棧空

D.不需要推斷棧滿也不需要推斷?？?/p>

因?yàn)殒湕Ｖ械慕Y(jié)點(diǎn)是動(dòng)態(tài)分配的，可以不考慮上溢，所以無需定義stackFull運(yùn)算。

7.假設(shè)串str="Software",其子串的數(shù)目是［D)

A.8B.9

C.36D.37

8.設(shè)有一個(gè)10階的下三角矩陣A,采納行優(yōu)先壓縮存儲(chǔ)方法，au為第一個(gè)元素，其存儲(chǔ)地址為1000,每個(gè)元素占

一個(gè)地址單元，則硼的地址為［C)

A.1012B.1017

C.1032D.1039

在n階方陣A這個(gè)下三角矩陣中，第i(i從0開始)行［0Wi〈n)有i+1個(gè)元素，元素總數(shù)為：n(n+l)/2,并將元

素放在一個(gè)向量saO..n(n+l)/2-l］中。

假設(shè)i》j,則aij在左下三角矩陣中，sak］與aij的對(duì)應(yīng)關(guān)系是k=i(i+l)/2+j。

假設(shè)i〈j,則aij在右上三角矩陣中，sak］與aij的對(duì)應(yīng)關(guān)系是k=j(j+l)/2+i。

假設(shè)all為第一個(gè)元素，a85與a00為第一個(gè)元素時(shí)的a(85-(1『00))=a74位置一樣，k=7X8/2+4=32,則a85的

地址=1000+32=1032；

假設(shè)a44為第一個(gè)元素，a85與a00為第一個(gè)元素時(shí)的a(85-(44-00))=a41位置一樣，k=4X5/2+l=H,則a85的

地址=1000+11=1011；

9.同意結(jié)點(diǎn)共享的廣義表稱為［D)

A.純表B.線性表

C.遞歸表D.再入表

10.以下數(shù)據(jù)結(jié)構(gòu)中，不屬于二叉樹的是［A)

A.B樹B樹是一種平衡的多叉樹B.AVL樹AVL樹是自平衡二叉查找樹

C.二叉排序樹D.哈夫曼樹哈夫曼樹是最優(yōu)二叉樹

11.對(duì)下面有向圖給出了四種可能的拓?fù)湫蛄校渲绣e(cuò)誤的選項(xiàng)是(C)

C.5,1,6,3,4,2D.5,1,2,6,4,3

12.以vl為起始結(jié)點(diǎn)對(duì)以下圖進(jìn)行深度優(yōu)先遍歷，正確的遍歷序列是(D)

考證素材

考證素材

A.vl,v2,v3,v4,v5,v6,v7B.vl,v2,v5,v4,v3,v7,v6

C.vl,v2,v3,v4,v7,v5,v6D.vl,v2,v5,v6,v7,v3,v4

深度優(yōu)先遍歷類似于樹的前序遍歷。其特點(diǎn)是盡可能先對(duì)縱深方向進(jìn)行搜索。

13.以下排序算法中不穩(wěn)定的是［A)

A.快速排序B.歸并排序

C.冒泡排序D.直接插入排序

穩(wěn)定：直接插入、冒泡、歸并、基數(shù)不穩(wěn)定：直接選擇、希爾、快速、堆

14.一個(gè)有序表為表,3,9,12,32,41,45,62,75,77,82,95,100),當(dāng)采納折半查找方法查找值32時(shí)，查

找成功需要的比擬次數(shù)是〔B〕midl=45,mid2=9,mid3=32

A.2B.3

C.4D.8

15.采納ISAM組織文件的方法屬于(D)

A.鏈組織B.順序組織

C.散列組織D.索引組織

二、填空題(本大題共10小題，每題2分，共20分)

請(qǐng)?jiān)诿款}的空格中填上正確答案。錯(cuò)填'不填均無分。

16.數(shù)據(jù)元素及其關(guān)系在計(jì)算機(jī)存儲(chǔ)器內(nèi)的表示稱為—存儲(chǔ)結(jié)構(gòu)。

17.長(zhǎng)度為n的線性表采納單鏈表結(jié)構(gòu)存儲(chǔ)時(shí)，在等概率情況下查找第i個(gè)元素的時(shí)間復(fù)雜度是—01n)o

18.下面是在順序棧上完成的一個(gè)棧根本操作，該操作的功能是—取棧頂o

typedefstruct(

DataTypedatalOO］；

inttop；

}SeqStack；

DataTypef18(SeqStackXS)

{if(StackEmpty(S))

Error(，zStackisempty")；

returnS->dataS->top］；

}

19.在串匹配中，一般將主串稱為目標(biāo)串，將子串稱為—模式串o

20.已知廣義表C=(a(b,c),d),則：tail(head(tail(C)))=_()。

21.用6個(gè)權(quán)值分別為6、13、18、30、7和16的結(jié)點(diǎn)構(gòu)造一棵哈夫曼(Huffman)樹，該樹的帶權(quán)路徑長(zhǎng)度為

—221oWPL=30X1+18X2+16X3+13X4+6X5+7X5=30+36+48+52+30+35=231

22.已知有向圖如下所示，其中頂點(diǎn)A到頂點(diǎn)C的最短路徑長(zhǎng)度是—35o

考證素材

考證素材

23.對(duì)序列｛55,46,13,05,94,17,42｝進(jìn)行基數(shù)排序,第一趟排序后的結(jié)果是_42,13,94,55,05,46,17。

24.高度為3的3階B-樹最少的關(guān)鍵字總數(shù)是—5.oP182

一顆m523)階的B-樹，每個(gè)非根結(jié)點(diǎn)中所包含的關(guān)鍵字個(gè)數(shù)j滿足：「m/2」TWjWm-1。即每個(gè)非根結(jié)點(diǎn)至

少應(yīng)有rm/2nT個(gè)關(guān)鍵字，至多有m-1個(gè)關(guān)鍵字。

(注：rm/2-i是指不小于(即大于等于)m/2的最小整數(shù)。)

一顆高度為h的m階B-樹中最少可容納的關(guān)鍵字總數(shù)為：rm/2n-1,最少可容納的結(jié)點(diǎn)總數(shù)為

「m/2-I-1

-rm/2-|-1-

以h=3,m=3為例，相應(yīng)的B-樹最少可容納的關(guān)鍵字總數(shù)為廠m/2