2010數(shù)據(jù)結(jié)構(gòu)試卷a

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

1、班級學(xué)號_________________________姓名___________________（第頁，共頁）-------------密--------封--------線--------密--------封--------線--------密--------封--------線--------密--------封--------線--------密--------封--------線--------密--------封--------線--------密--------封--------線-

2、-------密--------封--------線------------湖南城市學(xué)院2009—2010學(xué)年第1期《數(shù)據(jù)結(jié)構(gòu)》試卷A卷時間：120分鐘年級專業(yè)班級：0906601-02-03【考試】【閉卷】題型一二三四五六七八九十總分分?jǐn)?shù)1020302416得分評卷人：合分人：核查人：一、判斷題（共10分，每小題1分）（）1、數(shù)據(jù)元素是數(shù)據(jù)的最小單位。（）2、串是由有限個字符構(gòu)成的連續(xù)序列，串長度為串中字符的個數(shù)，子串是主串中符構(gòu)成的有限序列。（）3、子串定位函數(shù)的時間復(fù)雜度在最壞情況下為O（n*

3、m），因此子串定位函數(shù)沒有實際使用的價值。（）4、在線性鏈表中刪除中間的結(jié)點時，只需將被刪結(jié)點釋放。（）5、鄰接表只能用于有向圖的存儲，鄰接矩陣對于有向圖和無向圖的存儲都適用。（）6、遞歸定義的數(shù)據(jù)結(jié)構(gòu)通常用遞歸算法來實現(xiàn)對它的操作。（）7、在一棵二叉樹中，假定每個結(jié)點只有左子女，沒有右子女，對它分別進(jìn)行前序遍歷和按層遍歷，則具有相同的結(jié)果。（）8、已知指針P指向鍵表L的某結(jié)點，執(zhí)行語句P=P->next不會刪除該鏈表中的結(jié)點。（）9、對一個連通圖進(jìn)行一次深度優(yōu)先搜索可以遍訪圖中的所有頂點。（）10

4、、進(jìn)行折半搜索的表必須是順序存儲的有序表。二、填空題（共20分，每空1分）1、數(shù)據(jù)結(jié)構(gòu)被形式地定義為（D,R），其中D是數(shù)據(jù)元素的有限集合，R是D上的關(guān)系有限集合。2、算法的五個重要特性是__有窮性__,__確定性__,__可行性__,__輸出性__,_輸入性___。3、在圖形結(jié)構(gòu)中，每個結(jié)點的前驅(qū)結(jié)點數(shù)和后續(xù)結(jié)點數(shù)可以任意個。4、在樹形結(jié)構(gòu)中，樹根結(jié)點沒有前驅(qū)結(jié)點，其余每個結(jié)點有且只有一個個直接前驅(qū)結(jié)點，葉子結(jié)點沒有后續(xù)結(jié)點，其余每個結(jié)點的直接后續(xù)結(jié)點可以任意個。5、在具有n個單元的循環(huán)隊列中，隊

5、滿時共有n-1個元素。6、向棧中壓入元素的操作是先移動棧頂指針，后存入元素。7、零個字符的串稱為空串；只有空白字符的串稱為空白串。8、如果含n個頂點的圖形成一個環(huán)，則它有n棵生成樹。9、有向圖中的結(jié)點前驅(qū)后繼關(guān)系的特征是一個節(jié)點可能有若干個前驅(qū)，也有可能有若干個后繼。10、折半查找的存儲結(jié)構(gòu)僅限于_順序存儲結(jié)構(gòu)___，且是__有序的__。三、選擇題（共30分，每小題2分）1.一個向量（即一批地址連續(xù)的存儲單元）第一個元素的存儲地址是100，每個元素的長度為2，則第5個元素的地址是____。A.110

6、B.108C.100D.1202.線性表的順序存儲結(jié)構(gòu)是一種___的存儲結(jié)構(gòu)，而鏈?zhǔn)酱鎯Y(jié)構(gòu)是一種___的存儲結(jié)構(gòu)。A．隨機存取B．索引存取C．順序存取D．散列存取3.線性表的邏輯順序與存儲順序總是一致的，這種說法___。A.正確B.不正確4．設(shè)有兩個串p和q，求q在p中首次出現(xiàn)的位置的運算稱作____。A.連接B.模式匹配C.求子串D.求串長5．設(shè)串s1=’ABCDEFG’，s2=’PQRST’，函數(shù)con(x,y)返回x和y串的連接串，subs(s,i,j)返回串s的從序號i的字符開始的j個字符

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

8、下標(biāo)i從0到7，列下標(biāo)j從0到9，從首地址SA開始連續(xù)存放在存儲器內(nèi)，該數(shù)組按列存放時，元素A[4][7]的起始地址為____。A.SA+141B.SA+180C.SA+222D.SA+2258.由于二叉樹中每個結(jié)點的度最大為2，所以二叉樹是一種特殊的樹，這種說法____。班級學(xué)號_________________________姓名___________________（第頁，共頁）-------------密--------封--------線--------密-