2010湖南城市學(xué)院數(shù)據(jù)結(jié)構(gòu)試卷a

《2010湖南城市學(xué)院數(shù)據(jù)結(jié)構(gòu)試卷a》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、班級(jí)學(xué)號(hào)_________________________姓名___________________（第頁，共頁）-------------密--------封--------線--------密--------封--------線--------密--------封--------線--------密--------封--------線--------密--------封--------線--------密--------封--------線--------密--------封--------線--------密--------封--------線------------湖南城市學(xué)院2

2、009—2010學(xué)年第1期《數(shù)據(jù)結(jié)構(gòu)》試卷A卷時(shí)間：120分鐘年級(jí)專業(yè)班級(jí)：0906601-02-03【考試】【閉卷】題型一二三四五六七八九十總分分?jǐn)?shù)1020302416得分評(píng)卷人：合分人：核查人：一、判斷題（共10分，每小題1分）（X）1、數(shù)據(jù)元素是數(shù)據(jù)的最小單位。（X）2、串是由有限個(gè)字符構(gòu)成的連續(xù)序列，串長度為串中字符的個(gè)數(shù)，子串是主串中符構(gòu)成的有限序列。（X）3、子串定位函數(shù)的時(shí)間復(fù)雜度在最壞情況下為O（n*m），因此子串定位函數(shù)沒有實(shí)際使用的價(jià)值。（X）4、在線性鏈表中刪除中間的結(jié)點(diǎn)時(shí)，只需將被刪結(jié)點(diǎn)釋放。（X）5、鄰接表只能用于有向圖的存儲(chǔ)，鄰接矩陣對(duì)于有向圖和無向圖的存儲(chǔ)都

3、適用。（√）6、遞歸定義的數(shù)據(jù)結(jié)構(gòu)通常用遞歸算法來實(shí)現(xiàn)對(duì)它的操作。（√）7、在一棵二叉樹中，假定每個(gè)結(jié)點(diǎn)只有左子女，沒有右子女，對(duì)它分別進(jìn)行前序遍歷和按層遍歷，則具有相同的結(jié)果。（√）8、已知指針P指向鍵表L的某結(jié)點(diǎn)，執(zhí)行語句P=P->next不會(huì)刪除該鏈表中的結(jié)點(diǎn)。（√）9、對(duì)一個(gè)連通圖進(jìn)行一次深度優(yōu)先搜索可以遍訪圖中的所有頂點(diǎn)。（√）10、進(jìn)行折半搜索的表必須是順序存儲(chǔ)的有序表。二、填空題（共20分，每空1分）1、數(shù)據(jù)結(jié)構(gòu)被形式地定義為（D,R），其中D是數(shù)據(jù)元素的有限集合，R是D上的關(guān)系有限集合。2、算法的五個(gè)重要特性是__有窮性__,__確定性__,__可行性__,__輸出性__

4、,_輸入性___。3、在圖形結(jié)構(gòu)中，每個(gè)結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)數(shù)和后續(xù)結(jié)點(diǎn)數(shù)可以任意個(gè)。4、在樹形結(jié)構(gòu)中，樹根結(jié)點(diǎn)沒有前驅(qū)結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且只有一個(gè)個(gè)直接前驅(qū)結(jié)點(diǎn)，葉子結(jié)點(diǎn)沒有后續(xù)結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)的直接后續(xù)結(jié)點(diǎn)可以任意個(gè)。5、在具有n個(gè)單元的循環(huán)隊(duì)列中，隊(duì)滿時(shí)共有n-1個(gè)元素。6、向棧中壓入元素的操作是先移動(dòng)棧頂指針，后存入元素。7、零個(gè)字符的串稱為空串；只有空白字符的串稱為空白串。8、如果含n個(gè)頂點(diǎn)的圖形成一個(gè)環(huán)，則它有n棵生成樹。9、有向圖中的結(jié)點(diǎn)前驅(qū)后繼關(guān)系的特征是一個(gè)節(jié)點(diǎn)可能有若干個(gè)前驅(qū)，也有可能有若干個(gè)后繼。10、折半查找的存儲(chǔ)結(jié)構(gòu)僅限于_順序存儲(chǔ)結(jié)構(gòu)___，且是__有序的__。

5、三、選擇題（共30分，每小題2分）1.一個(gè)向量（即一批地址連續(xù)的存儲(chǔ)單元）第一個(gè)元素的存儲(chǔ)地址是100，每個(gè)元素的長度為2，則第5個(gè)元素的地址是__b__。A.110B.108C.100D.1202.線性表的順序存儲(chǔ)結(jié)構(gòu)是一種_a_的存儲(chǔ)結(jié)構(gòu)，而鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是一種__c__的存儲(chǔ)結(jié)構(gòu)。A．隨機(jī)存取B．索引存取C．順序存取D．散列存取3.線性表的邏輯順序與存儲(chǔ)順序總是一致的，這種說法_b__。A.正確B.不正確4．設(shè)有兩個(gè)串p和q，求q在p中首次出現(xiàn)的位置的運(yùn)算稱作_b___。A.連接B.模式匹配C.求子串D.求串長5．設(shè)串s1=’ABCDEFG’，s2=’PQRST’，函數(shù)con(x,y

6、)返回x和y串的連接串，subs(s,i,j)返回串s的從序號(hào)i的字符開始的j個(gè)字符組成的子串，len(s)返回串s的長度，則con(subs(s1,2,len(s2)),subs(s1,len(s2),2))的結(jié)果串是__d__。A.BCDEFB.BCDEFGC.BCPQRSTD.BCDEFEF6.二維數(shù)組A中，每個(gè)元素A的長度為3個(gè)字節(jié)，行下標(biāo)i從0到7，列下標(biāo)j從0到9，從首地址SA開始連續(xù)存放在存儲(chǔ)器內(nèi)，該數(shù)組按行存放時(shí)，數(shù)組元素A[7][4]的起始地址為__c__。A.SA+141B.SA+144C.SA+222D.SA+2257.二維數(shù)組A中，每個(gè)元素A的長度為3個(gè)字節(jié)，行下

7、標(biāo)i從0到7，列下標(biāo)j從0到9，從首地址SA開始連續(xù)存放在存儲(chǔ)器內(nèi)，該數(shù)組按列存放時(shí)，元素A[4][7]的起始地址為__b__。A.SA+141B.SA+180C.SA+222D.SA+225班級(jí)學(xué)號(hào)_________________________姓名___________________（第頁，共頁）-------------密--------封--------線--------密--------封--------線------