1、（a卷）第 9 頁 共 9 頁韓山師范學院2012年專升本插班生考試 計算機科學與技術 專業 數據結構 試卷 （a卷）題號一二三四五六總分評卷人得分得分評卷人一、 單項選擇題（每題1.5分，共30分）題號12345678910答案題號11121314151617181920答案1、數據的不可分割的最小單位是（ c ）。a數據元素 b數據對象 c數據項 d數據串2、一個算法應該具有一些重要特性，下列不是算法特性的是（ d ） 。 a有窮性 b確定性 c可行性 d健壯性 e至少一個輸出 3、下面關于線性表的表述中，（ b ）是錯誤的？ a若線性表采用順序存儲，必須占用一片連續的存儲單元。 b若線性

2、表采用順序存儲，便于進行插入和刪除操作。 c線性表采用鏈接存儲，占用的存儲單元不一定是連續的。 d線性表采用鏈接存儲，便于插入和刪除操作。4、下列哪個不是鏈表所具有的特點是（ a ）。 a可隨機訪問表中元素b插入、刪除不需要移動元素c線性鏈表必須有一個指針域d所需空間與線性長度成正比解析 鏈表是線性表的鏈式存儲，是用結點來存儲數據元素。線性表采用鏈表作為存儲結構時，不能進行數據元素的隨機訪問，其優點是插入和刪除操作不需要移動元素。5、若線性表的長度為 n，且采用順序存儲結構，則等概率刪除其第 i個元素的算法的時間復雜度為（ d ）(1<=i<=n)。 a. o(i) b. o(n-

3、i) c. o(1) d. o(n)6、靜態鏈表中指針表示的是（ b ）。 a 內存地址 b數組下標 c表頭地址 d下一元素地址7、下列關于串的敘述中正確的是 b 。a串中所含的字母個數稱為串的長度b串是一種特殊的線性表 c串中的字母不區分大小寫d由空格組成的串稱為空串8、設有一個采用壓縮存儲的9 階對稱矩陣a，以行序為主存儲，第一個元素a11的存儲地址為 0，每個元素占一個地址空間，則a86 的地址為（ ） 。 a. 26 b. 27 c. 36 d. 37e.46f.479、判斷一個帶表頭的循環鏈表h為空表的判定條件是（ a ）a.hnullb.h->next=nullc.h->

4、;nextnulld.h>next=h10、若一個棧的輸入序列為 1,2,3,n，輸出序列的第一個元素是 i，則第 j 個輸出元素是（ b ）。 a. 不確定的b. i-jc. j-i+1d. i-j-1 11、在一個單鏈表中,若q所指結點是p所指結點的前驅結點,若要刪除p所指的結點,則執行( b )。a. q->next=pb. q->next=p->next;c. p=q->next;d. p->next= q->next;12、廣義表a=(a,(b,c),(d,e),(f,g),則head(tail(head(tail(tail(a)式子的值為（

5、 c ）。 a. (f) b.f c. e d. (e)13、在一棵度為3的樹中,度數為3的結點有2個,度數為2的結點有2個，則度為0的結點個數為( a ) a7 b8 c9 d1014、在下述結論中，正確的是（ c ）只有一個結點的二叉樹的度為 0; 二叉樹的度為 2； 二叉樹的左右子樹可任意交換; 深度為 k 的完全二叉樹的結點個數小于或等于深度相同的滿二叉樹。a b c d 15、算術表達式 a+b*（c+d/e）轉為后綴表達式后為（ a ） aabcde/+*+ b ab+cde/+* cabcde/*+ dabcde*/+ 16、一個有 n 個結點的圖，最多有（ a ）個連通分量。

6、an bn-1 c1 d017、若目標串的長度為n，模式串的長度為n/4，則執行模式匹配算法時，在最壞情況下的時間復雜度是（ d ）ao（ nlogn） bo（n/4） co（n） do（n2）18、設一組初始記錄關鍵字序列(7，2，8, 6，3，10, 5)，以第一個關鍵字7為基準進行一趟快速排序的結果為（ b ）。a. 2，5，6，3，7, 8, 10 b. 5，2，3，6，7,10, 8c. 2，3，5，6, 7, 8，10 d. 5，2，6，3, 7， 8, 10 19、向二叉搜索樹中插入一個元素的時間復雜度是( b )。ao(n） bo(log2n) co(n*log2n)do(n+

7、log2n) e.o(n2) f.o(n3)20、一個遞歸算法必須包括（ c ）。a. 初始條件和遞歸部分 b.初始條件和迭代部分c.終止條件和遞歸部分 d.終止條件和迭代部分得分評卷人二、問答題（共10分）1、什么叫完全二叉樹（4分）， 深度為k的，有n個結點的二叉樹，當且僅當其每個結點都與深度為k的滿二叉樹中編號從1至n的結點一一對應時，稱之為完全二叉樹。2、簡述順序存儲隊列的假溢出的避免方法及隊列滿和空的條件。（6分）得分評卷人三、填空題（每空1分，共20分）1、根據線性表的鏈式存儲結構中每一個結點包含的指針個數，將線性鏈表分成_單鏈表_和_雙鏈表_；而又根據指針的連接方式，鏈表又可分成

8、_和_。2、對于一個具有n個頂點和e條邊的有向圖和無向圖，在其對應的鄰接表中，所含邊結點分別有_個和_個。3、數據結構中評價算法的兩個重要指標是算法的時間復雜度和空間復雜度。4、循環隊列的引入，目的是為了克服_ _。5、串是一種特殊的線性表，其特殊性表現在_數據元素是一個字符_ ；串的兩種最基本的存儲方式是_順序存儲方式_、_鏈式存儲方式_；兩個串相等的充分必要條件是 兩個串的長度相等且對應位置的字符相同_。6、設 n 行 n 列的下三角矩陣 a 已壓縮到一維數組 b1.n*（n+1）/2中，若按行為主序存儲，則 aij對應的 b 中存儲位置為_。7、二叉樹中某結點的左子樹深度減去右子樹深度稱

9、為該結點的_，平衡二叉樹的結點的可能取值是_。8、已知一個圖如右圖所示，若采用深度優先遍歷該圖，則遍歷的序列為 abcdegf 。9、設某棵二叉樹中度數為0的結點數為n0，度數為1的結點數為n1，則該二叉樹中度數為2的結點數為_n0-1_；若采用二叉鏈表作為該二叉樹的存儲結構，則該二叉樹中共有_個空指針域。10、直接插入排序用監視哨的作用是緩沖作用。得分評卷人四、判斷題（每小題1分，共10分）1、數據的邏輯結構說明數據元素之間的順序關系,它依賴于計算機的儲存結構。 （ ）2、鏈表中的頭結點僅起到標識的作用。( )3、為了很方便的插入和刪除數據，可以使用雙向鏈表存放數據。( )4、若輸入序列為

10、1，2，3，4，5，6，則通過一個棧可以輸出序列 1，5，4，6，2，3。（ ）5、完全二叉樹一定是滿二叉樹，滿二叉樹不一定是完全二叉樹。（ ）6、線性表中的所有元素都有一個前驅元素和后繼元素。（ ）7、kmp 算法的特點是在模式匹配時指示主串的指針不會變小。 （ ）8、若一個廣義表的表頭為空表，則此廣義表亦為空表。（ ）9、向二叉排序樹中插入一個結點需要比較的次數可能大于該二叉樹的高度。（ ）10、最小生成樹的 kruskal 算法是一種貪心法（greedy）。（ ）得分評卷人五、程序填空題（每個空1分，共10分）1、下列算法的功能是比較兩個鏈串的大小，其返回值為：請在空白處填入適當的內容。

11、comstr(s1,s2)=int comstr(linkstring s1,linkstring s2) /s1和s2為兩個鏈串的頭指針 while (s1&&s2) if (s1>date<s2>date) return1； if (s1>date>s2>date) return1； ； ； if ( ) return 1； if ( ) return 1； ；2、如下為二分查找的非遞歸算法，試將其填寫完整。int binsch(elemtype a , int n, keytype k)int low, high =0;_;_;while (low<=high)int mid=_；if (k=amid.key) return mid; else if (k<mid.key) _; else _; return -1; /查找失敗得分評卷人六、算法設計題（20分）1、設計判斷單鏈表中結點