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

22國2001年10月高數(shù)據(jù)結(jié)構(gòu)試題：02331題(30分)一、單項選擇（本大題共小題每小題2分共30）在每小題列出的四個選項中只有一個選項是符合題目要求的，將正確選項前的字母填在題后的括號內(nèi)。．算法指的是（）A計算機程序．排序算法

B解決問題的計算方法D．決題的有限運算序列．線性表采用鏈式存儲時，結(jié)點的存儲地址（）A必須是不連續(xù)的B連續(xù)與否均可．必須是連續(xù)的D．頭點的存儲地址相連續(xù)．將長度為的單鏈表鏈接在長度為m的單鏈表之后的算法的時間復雜度為（）AO）．（n．（）D．Om+n）．由兩個棧共享一個向量空間的好處是）A減少存取時間，降低下溢發(fā)生的機率B節(jié)省存儲空間，降低上溢發(fā)生的機率．減少存取時間，降低上溢發(fā)的機率D．省儲空間，降低下溢發(fā)生的機率．設數(shù)組作循環(huán)隊列的儲空間，front為頭指針，為尾指針，則執(zhí)行出隊操作后其頭指針值（）Afront=front+1Bfront=(front+1)%(m-1)．D．．如下陳述中正確的是（）A串是一種特殊的線性表B串的長度必須大于零．串中元素只能是字母D．空串就是空白串．若目標串的長度為n，模式串的長度為[n/3]，則執(zhí)行模式匹配法時，在最壞情況下的時間復雜度是（）nAO（）3

B．O）

．On）

D．（n

3

）．一個非空廣義表的表頭（）A不可能是子表B只能是子表．只能是原子

D．以子表或原子．假設以帶行表的三元組表表示稀疏矩陣，則和下列行表23

2對應的稀疏矩陣是（）

0

06

0

06

7

0

7

00A.

00

00B.0400

4000

0

00

03

00

60000

D

0

10在一棵度為樹中度結(jié)點個數(shù)為2,為2的點個數(shù)為則度為0的點個數(shù)為()A4B．．D．7．在含n個頂點和條邊的無向圖的鄰接矩陣,元素的個數(shù)為()AeB．2eC．－．n

2

－2e12假設一個有個點和e條弧的有向圖用鄰接表表示,則刪除與某個頂點v相關的所有i弧的時間復雜度是)AO(n)BO(e)C．D．O(n*e)13用某種排序方法對關鍵字序列25，21，，，，，3520）進行排序時，序列的變化情況如下：，，2125，47，，35，84，，2125，35，，68，84，，2125，27，，68，84則所采用的排序方法是（）A選擇排序希爾排序C．并排序D快速排序14適于對動態(tài)查找表進行高效率查找的組織結(jié)構(gòu)是（）A有序表B分塊有序表．叉序樹D．線性鏈表15不定長文件是指（）A文件的長度不固定B．記錄的長度不固C．段的長度不固定D關鍵字項的長度不固定共分二、填空題（本大題共0小，每小題2分，若有兩個空格，每個格，共分不寫解答過程，將正確的答案寫在小題的空格內(nèi)。錯填或不填均無分。16數(shù)的邏輯結(jié)構(gòu)是從邏輯關系上描述數(shù)據(jù)它與數(shù)的無是立于計算機的。17在一個帶頭結(jié)點的單循環(huán)鏈表中指尾結(jié)點的直接前驅(qū)，則指向頭結(jié)點的指針h可用p表為

。18棧頂?shù)奈恢檬请S著操作而變化的。19在串“”，以t首字符的子串有個。20假設一個9階上三角矩陣A按優(yōu)先順序壓存儲在一維數(shù)組B中其中存儲

矩陣中第個素則B[31]中存放的元素是。1,121已知一棵完全二叉樹中共有768結(jié)，則該樹中共有22已知一個圖的廣度優(yōu)先生成樹如右圖所示，則與此相應的廣度優(yōu)先遍歷序列為。

個葉子結(jié)點。23在單鏈表上難以實現(xiàn)的排序方法有和。24在有序表，24，，48，6072）中二分查找關鍵字時所需進行的關鍵字比較次數(shù)為。25多重表文件和倒排文件都歸屬于文。三、解答題（本大題共4小，每小題分，共20分26畫出下列廣義表的共享結(jié)構(gòu)圖形表示）,(x,y)）27請畫出與下列二叉樹對應的森林。28已知一個無向圖的頂點集{b,c,其接矩陣如下所示ace

(1)畫出該圖的圖形；（2根據(jù)鄰接矩陣從頂a出發(fā)進行深度優(yōu)先遍歷和廣度優(yōu)先遍歷出應的遍歷序列。29已知一個散列表如下圖所示：5912459101112其散列函數(shù)為h(key)=key%13,處理沖突的方法為雙重散列法，探查序列：=(h(key)+i*h1(key))%mi?－i其中回答下列問題：（1對表中關鍵字35，33進行查找時，所需進行的比較次數(shù)各為多少？（2該散列表在等概率查找時查找成功的平均查找長度為多少？四算法閱讀題（本大題共4小，每小題分，20分）

30下列算法的功能是比較兩個鏈串的大小，其返回值為：當22)=當11當s2請在空白處填入適當?shù)膬?nèi)容。intcomstr(LinkStrings1,LinkStrings2){//s1s2為個鏈串的頭指針if(s1－>date<s2－－；if(s1－>date>s2－>date)return1；①；②；}if(③)return1if(④)return1；⑤；}①②③④⑤．閱讀下面的算法mynote(LinkListL){//L是不頭結(jié)點的單鏈表的頭指針if(L&&L->next){；－>next；p=L：：}

－－；p－；q－；}L；請回答下列問題：（1）說明語句S1功能；（2）說明語句組S2的功能；（3）設鏈表表示的線性為,a,?寫出算法執(zhí)行后的返回值所表示的線性1表。．假設兩個隊列共享一個循環(huán)向量空間（參見右下圖其類型定如下：struct{DateTypedata[MaxSize]；

intfront[2],rear[2]；；對于i=0或1front[i]和rear[i]別為第i隊列的頭指針和尾指針以下算法填空，實現(xiàn)第i個列的入隊操作。intEnQueuei,DateTypex){//若第i隊列不滿，則元素x入隊列，并返回；否則返回0；－－>front[①；Q>data[②；Q>rear[i]=[③];；}①②③．已知二叉樹的存儲結(jié)構(gòu)為二叉鏈表，閱讀下面算法。node{DateTypedata*；}ListNodeListNode*；Leafhead=NULL；VoidInorder{；If(T){Inorder(T－；If－>lchild)&&(!T－>rchild)){s=(ListNode*)malloc(sizeof(ListNode))；s－－>datas－；；}Inorder(T－>rchild)}}對于如下所示的二叉樹

（1）畫出執(zhí)行上述算法所建立的結(jié)構(gòu)；（2）說明該算法的功能五、算法設計題（本題共10分．閱讀下列函數(shù)inta[],int1,inth,intx){//1別為數(shù)據(jù)區(qū)的下界和上界inti,j,t；i=1；j=hwhile(i<j){while(i<j&&a[j]>=x)j--；while(i<j&&a[j]>=x)i+