數(shù)據(jù)結(jié)構(gòu)第一部分 選擇題

第一部分選擇題(30分)

一、項選擇題（本大題共15小題，每小題2分，共30分）在每小題列出的四個選項中只有一個選項是符合題目要求的，請將正確選項前的字母填在題后的括號內(nèi)。1．算法指的是（）A．計算機程序B．解決問題的計算方法C．排序算法D．解決問題的有限運算序列2．線性表采用鏈?zhǔn)酱鎯r，結(jié)點的存儲地址（）A．必須是不連續(xù)的B．連續(xù)與否均可C．必須是連續(xù)的D．和頭結(jié)點的存儲地址相連續(xù)3．將長度為n的單鏈表鏈接在長度為m的單鏈表之后的算法的時間復(fù)雜度為（）A．O（1）B．O（n）C．O（m）D．O（m+n）4．由兩個棧共享一個向量空間的好處是：（）A．減少存取時間，降低下溢發(fā)生的機率B．節(jié)省存儲空間，降低上溢發(fā)生的機率C．減少存取時間，降低上溢發(fā)生的機率D．節(jié)省存儲空間，降低下溢發(fā)生的機率5．設(shè)數(shù)組data[m]作為循環(huán)隊列SQ的存儲空間，front為隊頭指針，rear為隊尾指針，則執(zhí)行出隊操作后其頭指針front值為（）A．front=front+1B．front=(front+1)%(m-1)C．front=(front-1)%mD．front=(front+1)%m6．如下陳述中正確的是（）A．串是一種特殊的線性表B．串的長度必須大于零C．串中元素只能是字母D．空串就是空白串7．若目標(biāo)串的長度為n，模式串的長度為[n/3]，則執(zhí)行模式匹配算法時，在最壞情況下的時間復(fù)雜度是（）A．O（）B．O（n）C．O（n2）D．O（n3）8．一個非空廣義表的表頭（）A．不可能是子表B．只能是子表C．只能是原子D．可以是子表或原子9．假設(shè)以帶行表的三元組表表示稀疏矩陣，則和下列行表02335對應(yīng)的稀疏矩陣是（）10．在一棵度為3的樹中,度為3的結(jié)點個數(shù)為2,度為2的結(jié)點個數(shù)為1,則度為0的結(jié)點個數(shù)為()A．4B．5C．6D．711．在含n個頂點和e條邊的無向圖的鄰接矩陣中,零元素的個數(shù)為()A．eB．2eC．n2－eD．n2－2e12．假設(shè)一個有n個頂點和e條弧的有向圖用鄰接表表示,則刪除與某個頂點vi相關(guān)的所有弧的時間復(fù)雜度是()A．O(n)B．O(e)C．O(n+e)D．O(n*e)13．用某種排序方法對關(guān)鍵字序列（25，84，21，47，15，27，68，35，20）進(jìn)行排序時，序列的變化情況如下：20，15，21，25，47，27，68，35，8415，20，21，25，35，27，47，68，8415，20，21，25，27，35，47，68，84則所采用的排序方法是（）A．選擇排序B．希爾排序C．歸并排序D．快速排序14．適于對動態(tài)查找表進(jìn)行高效率查找的組織結(jié)構(gòu)是（）A．有序表B．分塊有序表C．三叉排序樹D．線性鏈表15．不定長文件是指（）A．文件的長度不固定B．記錄的長度不固定C．字段的長度不固定D．關(guān)鍵字項的長度不固定

第二部分非選擇題（共70分）二、填空題（本大題共10小題，每小題2分，若有兩個空格，每個空格1分，共20分）不寫解答過程，將正確的答案寫在每小題的空格內(nèi)。錯填或不填均無分。16．?dāng)?shù)據(jù)的邏輯結(jié)構(gòu)是從邏輯關(guān)系上描述數(shù)據(jù)，它與數(shù)據(jù)的無關(guān)，是獨立于計算機的。17．在一個帶頭結(jié)點的單循環(huán)鏈表中，p指向尾結(jié)點的直接前驅(qū)，則指向頭結(jié)點的指針head可用p表示為head=。18．棧頂?shù)奈恢檬请S著操作而變化的。19．在串S=“structure”中，以t為首字符的子串有個。20．假設(shè)一個9階的上三角矩陣A按列優(yōu)先順序壓縮存儲在一維數(shù)組B中，其中B[0]存儲矩陣中第1個元素a1,1,則B[31]中存放的元素是。21．已知一棵完全二叉樹中共有768結(jié)點，則該樹中共有個葉子結(jié)點。22．已知一個圖的廣度優(yōu)先生成樹如右圖所示，則與此相應(yīng)的廣度優(yōu)先遍歷序列為。

23．在單鏈表上難以實現(xiàn)的排序方法有和。24．在有序表（12，24，36，48，60，72，84）中二分查找關(guān)鍵字72時所需進(jìn)行的關(guān)鍵字比較次數(shù)為。25．多重表文件和倒排文件都?xì)w屬于文件。三、解答題（本大題共4小題，每小題5分，共20分）26．畫出下列廣義表的共享結(jié)構(gòu)圖形表示P=（（（z）,(x,y)）,((x,y),x),(z)）27．請畫出與下列二叉樹對應(yīng)的森林。

28．已知一個無向圖的頂點集為{a,b,c,d,e},其鄰接矩陣如下所示abcde(1)畫出該圖的圖形；（2）根據(jù)鄰接矩陣從頂點a出發(fā)進(jìn)行深度優(yōu)先遍歷和廣度優(yōu)先遍歷，寫出相應(yīng)的遍歷序列。

29．已知一個散列表如下圖所示：

35

20

33

48

590123456789101112其散列函數(shù)為h(key)=key%13,處理沖突的方法為雙重散列法，探查序列為：hi=(h(key)+*h1(key))%m=0,1,…，m－1其中h1(key)=key%11+1回答下列問題：（1）對表中關(guān)鍵字35，20，33和48進(jìn)行查找時，所需進(jìn)行的比較次數(shù)各為多少？（2）該散列表在等概率查找時查找成功的平均查找長度為多少？四、算法閱讀題（本大題共4小題，每小題5分，共20分）30．下列算法的功能是比較兩個鏈串的大小，其返回值為：comstr(s1,s2)=請在空白處填入適當(dāng)?shù)膬?nèi)容。intcomstr(LinkStrings1,LinkStrings2){//s1和s2為兩個鏈串的頭指針while(s1&&s2){if(s1－>date<s2－>date)return－1；if(s1－>date>s2－>date)return1；①；②；}if(③)return－1；if(④)return1；⑤；}①②③④⑤31．閱讀下面的算法LinkListmynote(LinkListL){//L是不帶頭結(jié)點的單鏈表的頭指針if(L&&L->next){q=L；L=L－>next；p=L；S1：while(p－>next)p=p－>next；S2：p－>next=q；q－>next=NULL；}returnL；}請回答下列問題：（1）說明語句S1的功能；（2）說明語句組S2的功能；（3）設(shè)鏈表表示的線性表為（a1,a2,…,an）,寫出算法執(zhí)行后的返回值所表示的線性表。32．假設(shè)兩個隊列共享一個循環(huán)向量空間（參見右下圖），其類型Queue2定義如下：typedefstruct{DateTypedata[MaxSize]；intfront[2],rear[2]；}Queue2；對于i=0或1，front[i]和rear[i]分別為第i個隊列的頭指針和尾指針。請對以下算法填空，實現(xiàn)第i個隊列的入隊操作。intEnQueue(Queue2*Q,inti,DateTypex){//若第i個隊列不滿，則元素x入隊列，并返回1；否則返回0if(i<0||i>1)return0；if(Q－>rear[i]==Q－>front[①]return0；Q－>data[②]=x；Q－>rear[i]=[③];return1；}①②③33．已知二叉樹的存儲結(jié)構(gòu)為二叉鏈表，閱讀下面算法。typedefstructnode{DateTypedata；Structnode*next；}ListNode；typedefListNode*LinkList；LinkListLeafhead=NULL；VoidInorder(BinTreeT){LinkLists；If(T){Inorder(T－>lchild)；If((!T－>lchild)&&(!T－>rchild)){s=(ListNode*)malloc(sizeof(ListNode))；s－>data=T－>data；s－>next=Leafhead；Leafhead=s；}Inorder(T－>rchild)；}}對于如下所示的二叉樹

（1）畫出執(zhí)行上述算法后所建立的結(jié)構(gòu)；（2）說明該算法的功能。五、算法設(shè)計題（本題共10分）34．閱讀下列函數(shù)arrange()intarrange(inta[],int1,inth,intx){//1和h分別為數(shù)據(jù)區(qū)的下界和上界inti,j,t；i=1；j=h；while(i<j){while(i<j&&a[j]>=x)j--；while(i<j&&a[j]>=x)i++；if(i<j){t=a[j]；a[j]=a[i]；a[i]=t；}}if(a[i]<x)returni；elsereturni－1；}（1）寫出該函數(shù)的功能；（2）寫一個調(diào)用上述函數(shù)實現(xiàn)下列功能的算法：對一整型數(shù)組b[n]中的元素進(jìn)行重新排列，將所有負(fù)數(shù)均調(diào)整到數(shù)組的低下標(biāo)端，將所有正數(shù)均調(diào)整到數(shù)組的高下標(biāo)端，若有零值，則置于兩者之間，并返回數(shù)組中零元素的個數(shù)。

數(shù)據(jù)結(jié)構(gòu)試題參考答案一、

單項選擇題（本大題共15小題，每小題2分，共30分） 1．D ２．Ｂ ３．Ｃ ４．Ｂ ５．Ｄ ６．Ａ ７．Ｃ ８，Ｄ ９，Ａ 10．Ｃ 11．Ｄ 12．Ｃ 13．Ｄ 14．Ｃ 15．Ｂ二、填空題（本大題共10小題，每小題2分，共20分） 16．存儲（或存儲結(jié)構(gòu)） 17.p－＞next－＞next 18．進(jìn)棧和退棧 19．12 20．a(chǎn)4,8 21．384 22．a(chǎn)befcdg 23．快速排序、堆排序、希爾排序 24．２ 25.多關(guān)鍵字三、解答題（本大題共4小題，每小題5分，共20分） 26．

圖1圖2 27．

28．該圖的圖形為：

深度優(yōu)先遍歷序列為：abdce廣度優(yōu)先遍歷序列為：abedc29．（１）對關(guān)鍵字35、20、33和48進(jìn)行查找的比較次數(shù)為３、２、１、１；（２）平均查找長度四、算法閱讀題（本大題共4小題，每小題5分，共20分）30．①S1=S1－>next②s2=s2－>next③s2(或s2!=NULL或s2&&!s1)