2012韓山師范學(xué)院專升本插班生考試《數(shù)據(jù)結(jié)構(gòu)》試卷

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

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

3、i) c. o(1) d. o(n)6、靜態(tài)鏈表中指針表示的是（ b ）。 a 內(nèi)存地址 b數(shù)組下標(biāo) c表頭地址 d下一元素地址7、下列關(guān)于串的敘述中正確的是 b 。a串中所含的字母個數(shù)稱為串的長度b串是一種特殊的線性表 c串中的字母不區(qū)分大小寫d由空格組成的串稱為空串8、設(shè)有一個采用壓縮存儲的9 階對稱矩陣a，以行序為主存儲，第一個元素a11的存儲地址為 0，每個元素占一個地址空間，則a86 的地址為（ ） 。 a. 26 b. 27 c. 36 d. 37e.46f.479、判斷一個帶表頭的循環(huán)鏈表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所指結(jié)點是p所指結(jié)點的前驅(qū)結(jié)點,若要刪除p所指的結(jié)點,則執(zhí)行( 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的樹中,度數(shù)為3的結(jié)點有2個,度數(shù)為2的結(jié)點有2個，則度為0的結(jié)點個數(shù)為( a ) a7 b8 c9 d1014、在下述結(jié)論中，正確的是（ c ）只有一個結(jié)點的二叉樹的度為 0; 二叉樹的度為 2； 二叉樹的左右子樹可任意交換; 深度為 k 的完全二叉樹的結(jié)點個數(shù)小于或等于深度相同的滿二叉樹。a b c d 15、算術(shù)表達式 a+b*（c+d/e）轉(zhuǎn)為后綴表達式后為（ a ） aabcde/+*+ b ab+cde/+* cabcde/*+ dabcde*/+ 16、一個有 n 個結(jié)點的圖，最多有（ a ）個連通分量。

6、an bn-1 c1 d017、若目標(biāo)串的長度為n，模式串的長度為n/4，則執(zhí)行模式匹配算法時，在最壞情況下的時間復(fù)雜度是（ d ）ao（ nlogn） bo（n/4） co（n） do（n2）18、設(shè)一組初始記錄關(guān)鍵字序列(7，2，8, 6，3，10, 5)，以第一個關(guān)鍵字7為基準(zhǔn)進行一趟快速排序的結(jié)果為（ 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、向二叉搜索樹中插入一個元素的時間復(fù)雜度是( 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個結(jié)點的二叉樹，當(dāng)且僅當(dāng)其每個結(jié)點都與深度為k的滿二叉樹中編號從1至n的結(jié)點一一對應(yīng)時，稱之為完全二叉樹。2、簡述順序存儲隊列的假溢出的避免方法及隊列滿和空的條件。（6分）得分評卷人三、填空題（每空1分，共20分）1、根據(jù)線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)中每一個結(jié)點包含的指針個數(shù)，將線性鏈表分成_單鏈表_和_雙鏈表_；而又根據(jù)指針的連接方式，鏈表又可分成

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

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

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

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; /查找失敗得分評卷人六、算法設(shè)計題（20分）1、設(shè)計判斷單鏈表中結(jié)點