1、2012年韓山師范學(xué)院本科插班生考試試卷計(jì)算機(jī)科學(xué)與技術(shù)專業(yè) 數(shù)據(jù)結(jié)構(gòu)試卷(A卷)一、單項(xiàng)選擇題(每題2分，共40分)1、 下列選項(xiàng)中不是算法的必須具有的重要特性的是。有窮性 B.正確性 C.確定性 D.可行性2、 下列關(guān)于算法漸近階表達(dá)式中，時(shí)間復(fù)雜度最高的是。5n2 B. n3/2C. 2n D. nlogn E. n23、數(shù)據(jù)是對客觀事物的符號表示，在計(jì)算機(jī)科學(xué)中，數(shù)據(jù)的含義廣泛，如圖 像、聲音等都屬于數(shù)據(jù)范疇，數(shù)據(jù)不意義的最小不可分割的單位 是。A.數(shù)據(jù)元素B.數(shù)據(jù)對象C.數(shù)據(jù)結(jié)構(gòu)D.數(shù)據(jù)項(xiàng) E.位4、 下列有關(guān)線性表的敘述中，正確的是。線性表中的元素必須具有相同的特性線性表中的元素都

2、有且僅有一個(gè)直接前驅(qū)線性表中的元素都有且僅有一個(gè)直接后繼以上表述都不正確5、在一個(gè)長度為n有序的鏈?zhǔn)酱鎯?chǔ)的線性表中插入一個(gè)元素，使其保持有序，其操作的時(shí)間復(fù)雜度是。A. O(n) B. O(1)C.O(an)D.O(n2)6、關(guān)于線性表的結(jié)點(diǎn)的存儲(chǔ)地址表述正確的是。A.必須是不連續(xù)的B.連續(xù)與否由其存儲(chǔ)方式確定C.必須是連續(xù)的D.和頭結(jié)點(diǎn)的存儲(chǔ)地址相連續(xù)7、如下陳述中正確的是。B.串的長度必須大于零D.空串與空格串是相同的概念的邏輯結(jié)構(gòu)。D.隊(duì)列A.串是一種特殊的線性表C.串元素中的字母不區(qū)分大小寫8、數(shù)組的邏輯結(jié)構(gòu)不同于下列A.線性表 B.棧 C.樹9、設(shè)S為一個(gè)長度為n的字符串，其中的字符

3、各不相同，則S中的互異 的非平凡子串(非空且不同于S本身)的個(gè)數(shù)為。A. 2n-1B. n2C. (w+n)/2D. (n2+n)/2-1E. (n2-n)/2-1F.以上都不對10、中綴表達(dá)式(A + B) *D + E/ (F +A*D) +C的后綴形式是nextC. top-next=top D. top-next=top-next17、設(shè)森林F中有三棵樹，第一，第二，第三棵樹的結(jié)點(diǎn)個(gè)數(shù)分別為n1，n2和n3。則與森林F對應(yīng)的二叉樹根結(jié)點(diǎn)的右子樹上的結(jié)點(diǎn)個(gè)數(shù)是。A. n1+n2 B. n1+n3 C. n2+n3 D. n1+n2+n318、設(shè)一組權(quán)值集合W=2, 3, 4, 5, 6,

4、則由該權(quán)值集合構(gòu)造的哈夫曼樹 中帶權(quán)路徑長度之和為。A. 430 B. 45C. 50D. 5519、 設(shè)無向圖的頂點(diǎn)個(gè)數(shù)為n,則該圖最多有 條邊。A. n-1B. n C. n(n-1)D. n(n+1)/2 E. n(n-1)/220、 在二叉排序樹中插入一個(gè)關(guān)鍵字值的平均時(shí)間復(fù)雜度為。A. O(1ogn) B.O(n) C. O(nlogn) D. O(n2)。二、名詞解析(每題3分，共6分)1、平衡二叉樹：2、哈夫曼(Huffman)樹:三、填空題(每空2分，共18分)1、 在完全二叉樹的第6層上最少有 個(gè)結(jié)點(diǎn)，最多有 個(gè)結(jié)點(diǎn)。2、 普里姆(Prime)算法的時(shí)間復(fù)雜度為，它對 圖較為

5、適合。3、順序查找n個(gè)元素的順序表，若查找成功，則比較關(guān)鍵字的次數(shù)最多為次；當(dāng)使用監(jiān)視哨時(shí)，若查找失敗，則比較關(guān)鍵字的次數(shù)為。4、設(shè)有一組初始記錄關(guān)鍵字序列為（49, 38, 65, 85,97, 76, 13, 90,27,50）,則以d=3為增量的一趟希爾排序結(jié)束后的結(jié)果為5、設(shè)某無向圖G中有n個(gè)頂點(diǎn)，用鄰接矩陣A作為該圖的存儲(chǔ)結(jié)構(gòu)，則頂點(diǎn)i與頂點(diǎn)j互為鄰接點(diǎn)的條件是，無向圖的鄰接 矩陣具有 特性。6、若不考慮基數(shù)排序，則在排序過程中，主要進(jìn)行的兩種基本操作是關(guān)鍵字的 和記錄的。7、在一個(gè)帶頭結(jié)點(diǎn)的單循環(huán)鏈表中，p指向尾結(jié)點(diǎn)的直接前驅(qū)，則指向頭結(jié) 點(diǎn)的指針 head可用p表示為head=。

6、8、 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)包括 的表示和 的表示。9、 散列檢索技術(shù)的關(guān)鍵是 和。四、判斷題（每小題1分，共8分） TOC o 1-5 h z 1、調(diào)用一次深度優(yōu)先遍歷可以訪問到圖中的所有頂點(diǎn)。（）2、完全二叉樹一定是滿二叉樹，滿二叉樹不一定是完全二叉樹。（）3、順序存儲(chǔ)結(jié)構(gòu)的主要缺點(diǎn)是不利于插入或刪除操作。（）4、數(shù)組不適合作為任何二叉樹的存儲(chǔ)結(jié)構(gòu)。（）5、 任何一個(gè)遞歸過程都可以轉(zhuǎn)換成非遞歸過程。（）6、 設(shè)一棵樹T可以轉(zhuǎn)化成二叉樹BT,則二叉樹BT中一定沒有右子樹。（）7、帶權(quán)無向圖的最小生成樹的權(quán)值必是固定的。（）8、在AOE圖中，關(guān)鍵路徑上某個(gè)活動(dòng)的時(shí)間縮短，整個(gè)工程的時(shí)間也就必定縮短。（

7、）五、程序填空題（每個(gè)空1分，共12分）1、如下的算法是從串s中刪除所有與t相同的子串，并返回刪除次數(shù)。int SubString_Delete（Stringtype &s,Stringtype t）從串s中刪除所有與t相同的子串，并返回刪除次數(shù)for(n=0,i=1;i=s0-t0+1;i+)(for(j=1;j (2)/找到了與t匹配的子串(for(k=i;k=s0-t0;k+) sk=sk+t0;左移刪除s0-=t0;(3)/forreturn 4);/Delete_SubString2、n個(gè)頂點(diǎn)的有向圖用鄰接矩陣array表示，下面是其拓?fù)渑判蛩惴ǎ?補(bǔ)充完整。注：(1)圖的頂點(diǎn)號從

8、0開始計(jì)；(2)indegree是有n個(gè)分量的一 維數(shù)組，放頂點(diǎn)的入度；(3)函數(shù)crein用于算頂點(diǎn)入度；(4)有三個(gè) 函數(shù)push(data),pop( ),check()其含義為數(shù)據(jù)data進(jìn)棧，退棧和測 試棧是否空(不空返回1，否則0)。crein( array ,indegree,n)(for (i=0;in;i+)indegreei= _(1)_ for(i=0,in;i+)for (j=0;jn; j+)indegreei+= (2) _;topsort (array,indegree,n)(count= (3)_for (i=0;in;i+)if (4) _) push(i)while (check()(vex=pop();printf(vex);count+;for (i=0;in;i+)(k=(5)if ( (6)(indegreei-;if (7)push(i);if( )printf( “圖有回路”);六、算法設(shè)計(jì)題(每題8分，16分)1、設(shè)計(jì)一個(gè)算法將無向圖的鄰接矩陣轉(zhuǎn)為對應(yīng)鄰接表的算法。typedef struct (int vertexm;int edgemm;gadjmatrix;typedef struct node1(int info;int adjvertex;struct node1 *nextarc;glink