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

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

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

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

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

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

7、）五、程序填空題（每個空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個頂點的有向圖用鄰接矩陣array表示，下面是其拓撲排序算法，試 補充完整。注：(1)圖的頂點號從

8、0開始計；(2)indegree是有n個分量的一 維數(shù)組，放頂點的入度；(3)函數(shù)crein用于算頂點入度；(4)有三個 函數(shù)push(data),pop( ),check()其含義為數(shù)據data進棧，退棧和測 試棧是否空(不空返回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( “圖有回路”);六、算法設計題(每題8分，16分)1、設計一個算法將無向圖的鄰接矩陣轉為對應鄰接表的算法。typedef struct (int vertexm;int edgemm;gadjmatrix;typedef struct node1(int info;int adjvertex;struct node1 *nextarc;glink