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

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

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

B．O）

．On）

D．（n

3

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

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

2對應(yīng)的稀疏矩陣是（）

0

06

0

06

7

0

7

00A.

00

00B.0400

4000

0

00

03

00

60000

D

0

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

2

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

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

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

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

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

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

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

intfront[2],rear[2]；；對于i=0或1front[i]和rear[i]別為第i隊(duì)列的頭指針和尾指針以下算法填空，實(shí)現(xiàn)第i個(gè)列的入隊(duì)操作。intEnQueuei,DateTypex){//若第i隊(duì)列不滿，則元素x入隊(duì)列，并返回；否則返回0；－－>front[①；Q>data[②；Q>rear[i]=[③];；}①②③．已知二叉樹的存儲(chǔ)結(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）說明該算法的功能五、算法設(shè)計(jì)題（本題共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+