2013年韓山師范學院本科插班生《數(shù)據結構》試卷

1、wordword格式-感謝下載支持wordword格式-感謝下載支持2013 年韓ft師范學院本科插班生考試試卷計算機科學與技術專業(yè) 數(shù)據結構 試卷 （A卷）一、 單項選擇題（每題1.5分，共30分1、數(shù)據的不可分割的最小單位是（。A數(shù)據元素B數(shù)據對象C數(shù)據項D數(shù)據串2、一個算法應該具有一些重要特性，下列不是算法特性的是（） 。A有窮性B確定性C可行性D健壯性E至少一個輸3、下面關于線性表的表述中（）是錯誤的？ A若線性表采用順序存儲，必須占用一片連續(xù)的存儲單元B若線性表采用順序存儲，便于進行插入和刪除操作。 C線性表采用鏈接存儲，占用的存儲單元不一定是連續(xù)的D線性表采用鏈接存儲，便于插入和刪

2、除操作。4、下列哪個不是鏈表所具有的特點是（。 A可隨機訪問表中元素B插入、刪除不需要移動元C線性鏈表必須有一個指針域D所需空間與線性長度成正比5、若線性表的長度為n，且采用順序存儲結構，則等概率刪除其第i個元素的算法的時復雜度為（）(1=inext=NULLC.H-nextNULL D.Hnext=H10、若一個棧的輸入序列為 1,2,3,n，輸出序列的第一個元素是 i，則第 j 個輸出元素是（。A.不確定的B. i-jC. j-i+1D. i-j-111、在一個單鏈表中,若q所指結點是p所指結點的前驅結點,若要刪除p所指的結點,則行()。A. q-next=pC. p=q-next;B.

3、q-next=p-next;D. p-next= q-next;12A=(a,(b,c),(d,e),(f,g),Head(Tail(Head(Tail(Tail(A)（。A. (f)B.fC. eD. (e)13在一棵度為3的樹中,度數(shù)為3的結點有2個,度數(shù)為2的結點有2個則度為0的結個數(shù)為()A7B8C914、在下述結論中，正確的是（）只有一個結點的二叉樹的度為 0; 二叉樹的度為 2； 二叉樹的左右子樹可意交換;深度為 K 的完全二叉樹的結點個數(shù)小于或等于深度相同的滿二叉樹。ABCD15、算術表達式a+b*（c+d/e）轉為后綴表達式后為（） Aabcde/+*+B ab+cde/+*C

4、abcde/*+16、一個有n 個結點的圖，最多有（）個連通分量。AnBn-1C1D017、若目標串的長度為 n，模式串的長度為n/4，則執(zhí)行模式匹配算法時，在最壞情況的時間復雜度是（）AO（nlogn）BO（n/4）CO（n）DO（n2）18、設一組初始記錄關鍵字序列(7，2，8,6，3，10,5)，7趟快速排序的結果為（ 。A. 2，5，6，3，7,8, 10B. 5，2，3，6，7,10, 8C. 2，3，5，6, 7, 8，10D. 5，2，6，3, 7， 8, 1019、向二叉搜索樹中插入一個元素的時間復雜度是()AO(n）BO(logn)CO(n*logn)22DO(n+logn)

5、E.O(n2)F.O(n3)220、一個遞歸算法必須包括（。A.初始條件和遞歸部分B.初始條件和迭代部C.終止條件和遞歸部分D.終止條件和迭代部得分評卷人得分評卷人1、什么叫完全二叉樹4分，2、簡述順序存儲隊列的假溢出的避免方法及隊列滿和空的條件。（6 分）得分評卷人三得分評卷人1根據線性表的鏈式存儲結構中每一個結點包含的指針個數(shù)將線性鏈表分成 和；而又根據指針的連接方式，鏈表又可分成和 。2、對于一個具有n個頂點和e條邊的有向圖和無向圖，在其對應的鄰接表中，所含邊結分別有個和個。3、數(shù)據結構中評價算法的兩個重要指標是算法的和。4、循環(huán)隊列的引入，目的是為了克服 5串是一種特殊的線性表其特殊性

6、表現(xiàn)在 。 方式是、；兩個串相等的充分必要條件是 。6nn 列的下三角矩陣 A 已壓縮到一維數(shù)組 存儲，則Aij對應的 B 中存儲位置為。7、二叉樹中某結點的左子樹深度減去右子樹深度稱為該結點的 二叉樹的結點的可能取值是。_，平衡8、已知一個圖如右圖所示，若采用深度優(yōu)先遍歷該圖，則遍8、已知一個圖如右圖所示，若采用深度優(yōu)先遍歷該圖，則遍歷 的 序 列為。90N1N012的結點數(shù)為若采用二叉鏈表作為該二叉樹的存儲結構，則該二叉樹中共有 個空指針域。10、直接插入排序用監(jiān)視哨的作用是。得分評卷人四、判斷題得分評卷人1數(shù)據的邏輯結構說明數(shù)據元素之間的順序關系,它依賴于計算機的儲存結構（）word 格

7、式-可編輯-感謝下載支持2、鏈表中的頭結點僅起到標識的作用。()3、為了很方便的插入和刪除數(shù)據，可以使用雙向鏈表存放數(shù)據。()4、若輸入序列為 則通過一個?？梢暂敵鲂蛄衱ord 格式-可編輯-感謝下載支持2、鏈表中的頭結點僅起到標識的作用。()3、為了很方便的插入和刪除數(shù)據，可以使用雙向鏈表存放數(shù)據。()4、若輸入序列為 則通過一個?？梢暂敵鲂蛄小＃ǎ?（）6（）word word 格式-可編輯-感謝下載支持7、KMP算法的特點是在模式匹配時指示主串的指針不會變小。 （）8、若一個廣義表的表頭為空表，則此廣義表亦為空表（）9、向二叉排序樹中插入一個結點需要比較的次數(shù)可能大于該二叉樹的高度（ 1

8、、最小生成樹的 Kruskal 算法是一種貪心法（Greedy（）得分評卷人得分評卷人1、下列算法的功能是比較兩個鏈串的大小，其返回值為：comstr(s1,s2)=1當scomstr(s1,s2)=0當 1 2請在空白處填入適當?shù)膬热?。ss請在空白處填入適當?shù)膬热荨?當1 2ss12int comstr(LinkString s1,LinkString s2)/s1 和 s2 為兩個鏈串的頭指針while (s1&s2)if (s1datedate) if (s1dates2date)return1；if()return1；if()return1；2、如下為二分查找的非遞歸算法，試將其填寫完整。IntBinsch(ElemTypeA , int n,KeyTypeK)int low, high =0;while (low=high)int mid=if (K=Amid.key)return mid;else if (Kmid.key)else return -1;/查找失敗得分評卷人六、算法設計題（20得分評卷人1、設計判斷單鏈表中