資源描述：
《2010數(shù)據(jù)結(jié)構(gòu)試卷C.doc》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。
1、班級學(xué)號_________________________姓名___________________（第頁，共頁）-------------密--------封--------線--------密--------封--------線--------密--------封--------線--------密--------封--------線--------密--------封--------線--------密--------封--------線--------密--------封--------線--------密--------封--------線--------
2、----湖南城市學(xué)院2009—2010學(xué)年第1期《數(shù)據(jù)結(jié)構(gòu)》試卷C卷時間：120分鐘年級專業(yè)班級：0906601-02-03【考試】【閉卷】題型一二三四五六七八九十總分分數(shù)1020302416得分評卷人：合分人：核查人：一、判斷題（每空1分，共10分）1．串是由有限個字符構(gòu)成的連續(xù)序列，串長度為串中字符的個數(shù)，子串是主串中符構(gòu)成的有限序列。（）2．子串定位函數(shù)的時間復(fù)雜度在最壞情況下為O（n*m），因此子串定位函數(shù)沒有實際使用的價值。（）3．KMP算法的最大特點是指主串的指針不需要回溯。（）4．設(shè)模式串的長度為m，目標串的長度為n；當n≈m且處理只匹配一次的模式時，
3、樸素的匹配（即子串定位函數(shù)）算法所花的時間代價也可能會更為節(jié)省。（）5．如果一個串中的所有字符均在另一串中出現(xiàn)，則說前者是后者的子串。（）6．鏈表的刪除算法很簡單，因為當刪除鏈中某個結(jié)點后，計算機會自動將后續(xù)各個單元向前移動。（）7．用二叉鏈表法（link-rlink）存儲包含n個結(jié)點的二叉樹，結(jié)點的2n個指針區(qū)域中有n+1個為空指針。（）8．具有12個結(jié)點的完全二叉樹有5個度為2的結(jié)點。（）9．線性表在順序存儲時，邏輯上相鄰的元素未必在存儲的物理位置次序上相鄰。（）10．順序表結(jié)構(gòu)適宜于進行順序存取，而鏈表適宜于進行隨機存取。（）二、填空題（每空2分，共20分）1
4、．在散列存儲中，裝填因子的值越大，則____；的值越小，則____。2．中綴表達式9*x+(2.4／5.6-7.3)所對應(yīng)的后綴表達式為。3．二叉排序樹的查找長度不僅與有關(guān)，也與二叉排序樹的有關(guān)。4．每次直接或通過基準元素間接比較兩個元素，若出現(xiàn)逆序排列時就交換它們的位置，此種排序方法叫做排序；每次使兩個相鄰的有序表合并成一個有序表的排序方法叫做排序。5．在歸并排序中，進行每趟歸并的時間復(fù)雜度為，整個排序過程的時間復(fù)雜度為，空間復(fù)雜度為。三、選擇題（共30分，每小題3分）1．順序查找法適合于存儲結(jié)構(gòu)為____的線性表。A.散列存儲B.順序存儲或鏈接存儲C.壓縮存儲D
5、.索引存儲2.對線性表進行二分查找時，要求線性表必須____。A.以順序方式存儲B.以鏈接方式存儲C.以順序方式存儲，且結(jié)點按關(guān)鍵字有序排序D.以鏈接方式存儲，且結(jié)點按關(guān)鍵字有序排序3.采用順序查找方法查找長度為n的線性表時，每個元素的平均查找長度為____.A.nB.n/2C.(n+1)/2D.(n-1)/24．根據(jù)n個元素建立一棵二叉搜索樹時，其時間復(fù)雜度大致為()。A．O(lon2n)B．O(n)C．O(nlog2n)D．O(n2)5.向具有n個結(jié)點的堆中插入一個新元素的時間復(fù)雜度為()。A．O(1)B．O(n)C．O(log2n)D．O(nlog2n)6．對
6、長度為3的順序表進行搜索，若搜索第一個元素的概率為1／2，搜索第二個元素的概率為l／3，搜索第三個元素的概率為l／6，則搜索任一元素的平均搜索長度為()。A．5／3B．2C．7／3D．4／37．由于二叉樹中每個結(jié)點的度最大為2，所以二叉樹是一種特殊的樹，這種說法()。A.正確B.錯誤8．假定在一棵二叉樹中，雙分支結(jié)點數(shù)為15，單分支結(jié)點數(shù)為30個，則葉子結(jié)點數(shù)為()個。A．15B．16C．17D．479．按照二叉樹的定義，具有3個結(jié)點的不同形狀的二叉樹有()種。A.3B.4C.5D.610．按照二叉樹的定義，具有3個不同數(shù)據(jù)結(jié)點的不同的二叉樹有()種。A.5B.6C
7、.30D.32班級學(xué)號_________________________姓名___________________（第頁，共頁）-------------密--------封--------線--------密--------封--------線--------密--------封--------線--------密--------封--------線--------密--------封--------線--------密--------封--------線--------密--------封--------線--------密--------封--------
