資源描述：
《《數(shù)據(jù)結(jié)構(gòu)》樣卷及答案.doc》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、1．D２．Ｂ３．Ｃ４．Ｂ５．Ｄ《數(shù)據(jù)結(jié)構(gòu)》樣卷及答案第一部分選擇題(30分)一、單項選擇題（本大題共15小題，每小題2分，共30分）在每小題列出的四個選項中只有一個選項是符合題目要求的，請將正確選項前的字母填在題后的括號內(nèi)。1．算法指的是（D）A．計算機程序B．解決問題的計算方法C．排序算法D．解決問題的有限運算序列2．線性表采用鏈?zhǔn)酱鎯r，結(jié)點的存儲地址（B）A．必須是不連續(xù)的B．連續(xù)與否均可C．必須是連續(xù)的D．和頭結(jié)點的存儲地址相連續(xù)3．將長度為n的單鏈表鏈接在長度為m的單鏈表之后的算法的時間復(fù)
2、雜度為（C）A．O（1）B．O（n）C．O（m）D．O（m+n）4．由兩個棧共享一個向量空間的好處是：（B）A．減少存取時間，降低下溢發(fā)生的機率B．節(jié)省存儲空間，降低上溢發(fā)生的機率C．減少存取時間，降低上溢發(fā)生的機率D．節(jié)省存儲空間，降低下溢發(fā)生的機率5．設(shè)數(shù)組data[m]作為循環(huán)隊列SQ的存儲空間，front為隊頭指針，rear為隊尾指針，則執(zhí)行出隊操作后其頭指針front值為（D）A．front=front+1B．front=(front+1)%(m-1)C．front=(front-1)%m
3、D．front=(front+1)%m６．Ａ７．Ｃ８，Ｄ９，Ａ10．Ｃ11．Ｄ6．如下陳述中正確的是（A）A．串是一種特殊的線性表B．串的長度必須大于零C．串中元素只能是字母D．空串就是空白串7．若目標(biāo)串的長度為n，模式串的長度為[n/3]，則執(zhí)行模式匹配算法時，在最壞情況下的時間復(fù)雜度是（C）A．O（）B．O（n）C．O（n2）D．O（n3）8．一個非空廣義表的表頭（D）A．不可能是子表B．只能是子表C．只能是原子D．可以是子表或原子9．假設(shè)以帶行表的三元組表表示稀疏矩陣，則和下列行表02335對
4、應(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．Ｃ13．Ｄ14．Ｃ15．Ｂ12．假設(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，
5、68，35，20）進行排序時，序列的變化情況如下：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)查找表進行高效率查找的組織結(jié)構(gòu)是（）A．有序表B．分塊有序表C．三叉排序樹D．線性鏈表15．不定長文件是指（）A．文件的長度不固定B．記錄的長度不固定C．字段的長度不固定D．關(guān)鍵字項的長度不固定第二部分非選擇題
6、（共70分）二、填空題（本大題共10小題，每小題2分，若有兩個空格，每個空格1分，共20分）不寫解答過程，將正確的答案寫在每小題的空格內(nèi)。錯填或不填均無分。16．存儲（或存儲結(jié)構(gòu)）17.p－>next－>next18．進棧和退棧19．1220．a(chǎn)4,821．38422．a(chǎn)befcdg23．快速排序、堆排序、希爾排序24．２25.多關(guān)鍵字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可
7、用p表示為head=。18．棧頂?shù)奈恢檬请S著操作而變化的。19．在串S="structure"中，以t為首字符的子串有個。20．假設(shè)一個9階的上三角矩陣A按列優(yōu)先順序壓縮存儲在一維數(shù)組B中，其中B�存儲矩陣中第1個元素a1,1,則B?中存放的元素是。21．已知一棵完全二叉樹中共有768結(jié)點，則該樹中共有個葉子結(jié)點。22．已知一個圖的廣度優(yōu)先生成樹如右圖所示，則與此相應(yīng)的廣度優(yōu)先遍歷序列為。23．在單鏈表上難以實現(xiàn)的排序方法有和。24．在有序表（12，24，36，48，60，72，84）中二分查
8、找關(guān)鍵字72時所需進行的關(guān)鍵字比較次數(shù)為。25．多重表文件和倒排文件都歸屬于文件。三、解答題（本大題共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ā)進行深度優(yōu)先遍歷和廣度優(yōu)先遍歷，寫出相應(yīng)的遍歷序列。29．已知一個散列表如
