高等教育自學(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ù)構(gòu)造中，數(shù)據(jù)的邏輯構(gòu)造可以分成〔〕A．內(nèi)部構(gòu)造與外部構(gòu)造

B．線性構(gòu)造與非線性構(gòu)造C．緊湊構(gòu)造與非緊揍構(gòu)造

D．動(dòng)態(tài)構(gòu)造與靜態(tài)構(gòu)造2．在以單鏈表為存儲(chǔ)構(gòu)造的線性表中，數(shù)據(jù)元素之間的邏輯關(guān)系用〔〕A．?dāng)?shù)據(jù)元素的相鄰地址表示

B．?dāng)?shù)據(jù)元素在表中的序號(hào)表示C．指向后繼元素的指針表示

D．?dāng)?shù)據(jù)元素的值表示3．設(shè)p指向單鏈表中的一個(gè)結(jié)點(diǎn)，s指向待插入的結(jié)點(diǎn)，那么下述程序段的功能是〔〕s->next=p->next;

p->next=s;

t=p->data;

p->data=s->data;

s->data=t;A．結(jié)點(diǎn)*p及結(jié)點(diǎn)*s的數(shù)據(jù)域互換B．在p所指結(jié)點(diǎn)的元素之前插入元素C．在p所指結(jié)點(diǎn)的元素之后插入元素D．在結(jié)點(diǎn)*p之前插入結(jié)點(diǎn)*s4．棧與隊(duì)列都是〔〕A．限制存取位置的線性構(gòu)造

B．順序存儲(chǔ)的線性構(gòu)造C．鏈?zhǔn)酱鎯?chǔ)的線性構(gòu)造

D．限制存取位置的非線性構(gòu)造5．假設(shè)數(shù)組s[0..n-1]為兩個(gè)棧s1與s2的共用存儲(chǔ)空間，且僅當(dāng)s[0..n-1]全滿時(shí)，各棧才不能進(jìn)展進(jìn)棧操作，那么為這兩個(gè)棧分配空間的最正確方案是：s1與s2的棧頂指針的初值分別為〔〕A．1與n+1

B．1與n/2C．－1與n

D．－1與n+16．執(zhí)行以下程序段后，串X的值為〔〕

S=abcdefgh;

T=xyzw;

substr(X,S,2,strlen(T));

substr(Y,S,stelen(T),2);

strcat(X,Y);A．cdefgh

B．cdxyzwC．cdefxy

D．cdefef7．多維數(shù)組之所以有行優(yōu)先順序與列優(yōu)先順序兩種存儲(chǔ)方式是因?yàn)椤病矨．?dāng)?shù)組的元素處在行與列兩個(gè)關(guān)系中

B．?dāng)?shù)組的元素必須從左到右順序排列C．?dāng)?shù)組的元素之間存在次序關(guān)系

D．?dāng)?shù)組是多維構(gòu)造，內(nèi)存是一維構(gòu)造8．從廣義表LS＝〔(p,q),r,s〕中分解出原子q的運(yùn)算是〔〕A．tail(head(LS))

B．head(tail(head(LS)))C．head(tail(LS))

D．tail(tail(head(LS)))9．在具有n個(gè)葉子結(jié)點(diǎn)的嚴(yán)格二叉樹中，結(jié)點(diǎn)總數(shù)為〔〕A．2n+1

B．2nC．2n-1

D．2n-210．假設(shè)<Vi,vj>是有向圖的一條邊，那么稱〔〕A．vi鄰接于vj

B．vj鄰接于viC．vi與vj相互鄰接

D．vi及vj不相鄰接11．在一個(gè)帶權(quán)連通圖G中，權(quán)值最小的邊一定包含在G的〔〕A．最小生成樹中

B．深度優(yōu)先生成樹中C．廣度優(yōu)先生成樹中

D．深度優(yōu)先生成森林中12．當(dāng)在二叉排序樹中插入一個(gè)新結(jié)點(diǎn)時(shí)，假設(shè)樹中不存在及待插入結(jié)點(diǎn)的關(guān)鍵字一樣的結(jié)點(diǎn)，且新結(jié)點(diǎn)的關(guān)鍵字小于根結(jié)點(diǎn)的關(guān)鍵字，那么新結(jié)點(diǎn)將成為〔〕A．左子樹的葉子結(jié)點(diǎn)

B．左子樹的分支結(jié)點(diǎn)C．右子樹的葉子結(jié)點(diǎn)

D．右子樹的分支結(jié)點(diǎn)13．希爾排序的增量序列必須是〔〕A．遞增的

B．隨機(jī)的C．遞減的

D．非遞減的14．如果在排序過程中，每次均將一個(gè)待排序的記錄按關(guān)鍵字大小參加到前面已經(jīng)有序的子表中的適當(dāng)位置，那么該排序方法稱為〔〕A．插入排序

B．歸并排序C．冒泡排序

D．堆排序15．設(shè)置溢出區(qū)的文件是〔〕A．索引非順序文件

B．ISAM文件C．VSAM文件

D．順序文件二、填空題〔本大題共10小題，每題2分，共20分〕

請(qǐng)?jiān)诿款}的空格中填上正確答案。錯(cuò)填、不填均無分。16．以下程序段的時(shí)間復(fù)雜度為________________。product=1;for(i=n;i>0;i--)for(j=i+1;j<SPAN>product*=j;17．指針p指向單鏈表中某個(gè)結(jié)點(diǎn)，那么語句p->next=p->next->next的作用是________________。18．假設(shè)元素只能按a,b,c,d的順序依次進(jìn)棧，且得到的出棧序列中的第一個(gè)元素為c，那么可能得到的出棧序列為________________，不可能得到的出棧序列為________________。19．假設(shè)鏈串結(jié)點(diǎn)中的指針占4個(gè)字節(jié)，每個(gè)字符占1個(gè)字節(jié)，那么結(jié)點(diǎn)大小為2的鏈串的存儲(chǔ)密度為________________。

20．右圖表示的廣義表為________________。21．假設(shè)一棵滿三叉樹中含有121個(gè)結(jié)點(diǎn)，那么該樹的深度為________________。22．假設(shè)以鄰接矩陣表示有向圖，那么鄰接矩陣上第i行中非零元素的個(gè)數(shù)即為頂點(diǎn)vi的________________。23．假設(shè)希望只進(jìn)展8趟排序便能在4800個(gè)元素中找出其中值最小的8個(gè)元素，并且要求排序過程中所進(jìn)展的關(guān)鍵字比擬次數(shù)盡可能少，那么應(yīng)該選用________________排序方法。24．在含20個(gè)關(guān)鍵字的3階B樹〔2－3樹〕上查找一個(gè)關(guān)鍵字，至多需要訪問___________次外存。25．文件上的兩類主要操作為________________與________________。三、解答題〔本大題共4小題，每題5分，共20分〕26．設(shè)棧S1的入棧序列為1234〔每個(gè)數(shù)字為13個(gè)元素〕，那么不可能得到出棧序列3142。但可通過增設(shè)棧S2來實(shí)現(xiàn)。例如，按以下圖中的箭頭指示，依次經(jīng)過棧S1與S2，便可得到序列3142。

如果用H1與H2分別表示棧S1與S2的進(jìn)棧操作，用P1與P2分別表示兩個(gè)棧的出棧操作，那么得到3142的一個(gè)操作步驟為H1，H1，H1，P1，H2，P2，P1，H2，P1，H2，P2，H1，P1，H2，P2，P2請(qǐng)仿照上例寫出利用兩個(gè)棧從1234得到4132的操作步驟。27．樹如右圖所示，〔1〕寫出該樹的后序序列；

〔2〕畫出由該樹轉(zhuǎn)換得到的二叉樹。

28．為關(guān)鍵字〔17，33，31，40，48〕構(gòu)造一個(gè)長度為7的散列表，設(shè)散列函數(shù)為h(key)=key%7,用開放定址法解決沖突的探查序列是hi=(h(key)+i(key%5+1))%7

0≤i≤6〔1〕畫出構(gòu)造所得的散列表；〔2〕求出在等概率情況下查找成功時(shí)的平均查找長度。29．R［1..8］中的元素依次為〔12，5，9，20，6，31，24，27〕，寫出按算法MergeSortDC對(duì)R進(jìn)展自頂向下的二路歸并排序過程中，前5次調(diào)用函數(shù)Merge(R,low,mid,high)時(shí)參數(shù)low,mid與high的值。

voidMergeSortDC(intR[],intlow,intmid,inthigh)

{

intmid;

if(low<HIGH)<SPAN>

{

mid=(low+high)/2;

MergeSortDC(R,low,mid);

MergeSortDC(R,mid+1,high);

Merge(R,low,mid,high);

}

}//MergeSortDC〔1〕第一次調(diào)用時(shí)的參數(shù)值；〔2〕第二次調(diào)用時(shí)的參數(shù)值；

〔3〕第三次調(diào)用時(shí)的參數(shù)值；〔4〕第四次調(diào)用時(shí)的參數(shù)值；〔5〕第五次調(diào)用時(shí)的參數(shù)值；四、算法閱讀題〔本大題共4小題，每題5分，共20分〕30．以下函數(shù)的功能是，對(duì)以帶頭結(jié)點(diǎn)的單鏈表作為存儲(chǔ)構(gòu)造的兩個(gè)遞增有序表〔表中不存在值一樣的數(shù)據(jù)元素〕進(jìn)展如下操作：將所有在Lb表中存在而La表中不存在的結(jié)點(diǎn)插入到La中，其中La與Lb分別為兩個(gè)鏈表的頭指針。請(qǐng)?jiān)诳杖碧幪钊脒m宜內(nèi)容，使其成為一個(gè)完整的算法。voidunion(LinkListLa,LinkListLb)

{

//本算法的功能是將所有Lb表中存在而La表中不存在的結(jié)點(diǎn)插入到La表中

LinkListpre=La,q;

LinkListpa=La->next;

LinkListpb=Lb->next;

free(Lb);

while(pa&&pd)

{

if(pa->datadata)

{

pre=pa;pa=pa->next;}

elseif(pa->data>pb->data)

{

(1)

;

pre=pb;

pb=pb->next;

(2)

;

}

else

{

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

}

}

if(pb)

(3)

;

}

(1)

(2)

(3)31．串的存儲(chǔ)構(gòu)造為動(dòng)態(tài)存儲(chǔ)分配的順序串。閱讀以下算法，并答復(fù)以下問題：

〔1〕寫出執(zhí)行函數(shù)調(diào)用strc(s,r)的返回結(jié)果，其中s=〃aba〃,r=〃abababa〃;〔2〕簡述函數(shù)strc的功能。intstrc(HString*sub,HString*str){inti=0,j,k,count=0;while(i<str->lengthCsub->length+1){j=i;k=0;while(klength&&str->ch[j]==sub->ch[k]){j++;k++;}if(k==sub->length){count++;i=j-sub->length+1;}elsei++;}returncount;}(1)(2)32．以下函數(shù)MDFSForest的功能是，對(duì)一個(gè)采用鄰接矩陣作存儲(chǔ)構(gòu)造的圖進(jìn)展深度優(yōu)先搜索遍歷，輸出所得深度優(yōu)先生成森林中各條邊。請(qǐng)?jiān)诳杖碧幪钊脒m宜內(nèi)容，使其成為一個(gè)完整的算法。#defineMaxMun20//圖的最大頂點(diǎn)數(shù)typedefstruct{

charvexs[MaxNum];//字符類型的頂點(diǎn)表

intedges[MaxNum][MaxNum];//鄰接矩陣

intn,e;//圖的頂點(diǎn)數(shù)與邊數(shù)}MGraph;//圖的鄰接矩陣構(gòu)造描述typedefenum{FALSE,TRUE}Boolean;Booleanvisited[MaxNum];

voidMDFSTree(MGraph*G,inti);

voidMDFSForest(MGraph*G)

{

inti,k;

for(i=0;in;i++)

visited[i]=

(1)

;

for(k=0;kn;k++)

if(!visited[k])MDFSTree(G,k);}voidMDFSTree(MGraph*G,inti)

{

intj;

visited[i]=TRUE;

for(j=0;jn;j++)

{

if(

(2)

)

{

printf(〃<%c,%c>〃G->vexs[i],G->vexs[j]);

(3)

;