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

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

3、定性 _ , _可行性_ _ , _輸出性 _ , _ 輸入性_。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)隊列中，隊滿時共有 n-1 個元素。6、向棧中壓入元素的操作是先 移動棧頂指針 ，后 存入元素 。7、 零個字符的串 稱為空串； 只有空白字符的串 稱為空白串。8、如果含n個頂點的圖形成一個環(huán)，則它有 n 棵生成樹。9、有向圖中的結(jié)點前驅(qū)后繼關(guān)系的特征是 一個節(jié)點可能有若干個前驅(qū)，也有可

4、能有若干個后繼 。10、折半查找的存儲結(jié)構(gòu)僅限于_ 順序存儲結(jié)構(gòu) _，且是_ 有序的 _。三、選擇題（共30分，每小題2分）1. 一個向量（即一批地址連續(xù)的存儲單元）第一個元素的存儲地址是100，每個元素的長度為2，則第5個元素的地址是_b _。A. 110 B. 108 C. 100 D. 1202. 線性表的順序存儲結(jié)構(gòu)是一種_ a_的存儲結(jié)構(gòu)，而鏈?zhǔn)酱鎯Y(jié)構(gòu)是一種_ c_ _的存儲結(jié)構(gòu)。A隨機存取 B索引存取 C順序存取 D散列存取3. 線性表的邏輯順序與存儲順序總是一致的，這種說法_b_ _。A. 正確 B. 不正確4設(shè)有兩個串p和q，求q在p中首次出現(xiàn)的位置的運算稱作_b_。A. 連

5、接 B. 模式匹配C. 求子串 D. 求串長5設(shè)串s1=ABCDEFG，s2=PQRST，函數(shù)con (x,y)返回x和y串的連接串，subs(s,i,j)返回串s的從序號i的字符開始的j個字符組成的子串，len(s)返回串s的長度，則con (subs (s1,2,len (s2), subs (s1,len (s2),2)的結(jié)果串是_d_。A. BCDEF B. BCDEFGC. BCPQRST D. BCDEFEF6. 二維數(shù)組A中，每個元素A的長度為3個字節(jié)，行下標(biāo)i從0到7，列下標(biāo)j從0到9，從首地址SA開始連續(xù)存放在存儲器內(nèi)，該數(shù)組按行存放時，數(shù)組元素A74的起始地址為_c_。A.

6、 SA+141 B. SA+144 C. SA+222 D. SA+2257. 二維數(shù)組A中，每個元素A的長度為3個字節(jié)，行下標(biāo)i從0到7，列下標(biāo)j從0到9，從首地址SA開始連續(xù)存放在存儲器內(nèi)，該數(shù)組按列存放時，元素A47的起始地址為_b_。A. SA+141 B. SA+180 C. SA+222 D. SA+2258. 由于二叉樹中每個結(jié)點的度最大為2，所以二叉樹是一種特殊的樹，這種說法_b_。A. 正確 B. 錯誤9. 假定在一棵二叉樹中，雙分支結(jié)點數(shù)為15，單分支結(jié)點數(shù)為30個，則葉子結(jié)點數(shù)為 b 個。 A15 B16 C17 D4710. 按照二叉樹的定義，具有3個結(jié)點的不同形狀的二

7、叉樹有_c_種。A. 3 B. 4 C. 5 D. 611. 按照二叉樹的定義，具有3個不同數(shù)據(jù)結(jié)點的不同的二叉樹有_c_種。A. 5 B. 6 C. 30 D. 3212. 在一個圖中，所有頂點的度數(shù)之和等于所有邊數(shù)的_c_倍。A. 1/2 B. 1 C. 2 D. 4 13任何一個無向連通圖的最小生成樹 b 。A.只有一棵B.有一棵或多棵C.一定有多棵D.可能不存在14在一個有向圖中，所有頂點的入度之和等于所有頂點的出度之和的_b_倍。A. 1/2 B. 1 C. 2 D. 415. 解決散列法中出現(xiàn)的沖突問題常采用的方法是 d 。A.數(shù)字分析法、除余法、平方取中法 B.數(shù)字分析法、除余法

8、、線性探測法C.數(shù)字分析法、線性探測法、多重散列法 D.線性探測法、多重散列法、鏈地址法四、簡答題（共24分，每小題6分）1、根據(jù)二叉樹的定義，具有三個結(jié)點的二叉樹有5種不同的形態(tài)，請將它們分別畫出。如圖6.10所示a圖6.10 樹形5種aaaacccccbbbbbb2、.試比較順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)的優(yōu)缺點。在什么情況下用順序表比鏈表好？答： 順序存儲時，相鄰數(shù)據(jù)元素的存放地址也相鄰（邏輯與物理統(tǒng)一）；要求內(nèi)存中可用存儲單元的地址必須是連續(xù)的。優(yōu)點：存儲密度大（1？），存儲空間利用率高。缺點：插入或刪除元素時不方便。2分鏈?zhǔn)酱鎯r，相鄰數(shù)據(jù)元素可隨意存放，但所占存儲空間分兩部分，一部分存

9、放結(jié)點值，另一部分存放表示結(jié)點間關(guān)系的指針2分優(yōu)點：插入或刪除元素時很方便，使用靈活。缺點：存儲密度?。?），存儲空間利用率低。4分順序表適宜于做查找這樣的靜態(tài)操作；鏈表宜于做插入、刪除這樣的動態(tài)操作。若線性表的長度變化不大，且其主要操作是查找，則采用順序表；若線性表的長度變化較大，且其主要操作是插入、刪除操作，則采用鏈表。3EBEFAECDKGHIJ圖6.12假設(shè)一棵二叉樹的先序序列為EBADCFHGIKJ和中序序列為ABCDEFGHIJK。解：方法是：由前序先確定root，由中序可確定root的左、右子樹。然后由其左子樹的元素集合和右子樹的集合對應(yīng)前序遍歷序列中的元素集合，可繼續(xù)確定root的左右孩子。將他們分別作為新的root，不斷遞歸，則所有元素都將被唯一確定，問題得解4、畫出下列網(wǎng)絡(luò)的最小生成樹。答： iaedbchHf圖1 一棵二叉樹ji五、綜合題（共16分，每小題8分）1、由如圖1所示的二叉樹，回答以下問題：（1）畫出該二叉樹的中序線索二叉樹；（2）畫出該二叉樹的后序線索二叉樹；（3）畫出該二叉樹對應(yīng)的森林。解：中序線索二叉樹如圖1（左）所示；后序線索二叉樹如圖1（右）所示；該二叉樹轉(zhuǎn)換后的的森林如圖1所示。圖1a 11dhjbk