數(shù)據(jù)結(jié)構(gòu)期末試卷2.doc

承諾：我將嚴(yán)格遵守考場(chǎng)紀(jì)律，知道考試違紀(jì)、作弊的嚴(yán)重性，還知道請(qǐng)他人代考或代他人考者將被開除學(xué)籍和因作弊受到記過及以上處分將不授予學(xué)士學(xué)位，愿承擔(dān)由此引起的一切后果。專業(yè) 班級(jí) 學(xué)號(hào) 學(xué)生簽名： 試卷編號(hào)：（A）卷 數(shù)據(jù)結(jié)構(gòu) 課程 課程類別：必 開卷(范圍)（ A4紙一張 ）：考試日期： 題號(hào)一二三四五六七八九十總分累分人簽名題分30203812100得分考生注意事項(xiàng)：1、本試卷共 7 頁(yè)，總分100分，考試時(shí)間120 分鐘。2、考試結(jié)束后，考生不得將試卷、答題紙和草稿紙帶出考場(chǎng)。得分評(píng)閱人 一、 選擇題(每題 2 分，共30分)1. 假設(shè)某算法語句總的執(zhí)行次數(shù)為T(n)=6n4+n+n2,那么該算法的時(shí)間復(fù)雜性量級(jí)為( C )。A) O(2) B) O(n5) C) O(n4) D) O(1)2. 線性表采用順序存儲(chǔ)結(jié)構(gòu)時(shí)，其地址( A )。A) 必須是連續(xù)的 B) 部分地址必須是連續(xù)的C) 一定是不連續(xù)的 D) 連續(xù)與否均可以3. 從物理結(jié)構(gòu)上可以把數(shù)據(jù)結(jié)構(gòu)分為（ B ）兩大類。A動(dòng)態(tài)結(jié)構(gòu)、靜態(tài)結(jié)構(gòu) B順序結(jié)構(gòu)、鏈?zhǔn)浇Y(jié)構(gòu) C線性結(jié)構(gòu)、非線性結(jié)構(gòu) D初等結(jié)構(gòu)、構(gòu)造型結(jié)構(gòu)4. 在順序線性表（a1,a2,a29,a30）中，在a20之前插入一個(gè)新的結(jié)點(diǎn)，需要將( A )個(gè)結(jié)點(diǎn)后移。A) 11 B) 20 C) 19 D) 105. 帶頭結(jié)點(diǎn)的單循環(huán)鏈表為空的條件是( C )。A) head-next=NULL B) head=NULLC) head-next=head D) head!=NULL6. 棧S最多能容納4個(gè)元素。現(xiàn)在6個(gè)元素按A、B、C、D、E、F的順序進(jìn)棧，下列哪一個(gè)序列是不可能的出棧序列？( B ) A) A、B、C、D、E、F B) A、F、E、D 、C、B C) C、B、E、D、A、F D) C、D、B、F、 E、 A7. 深度為K的二叉樹最多有( C )個(gè)結(jié)點(diǎn)。A) 2K B) 2K1 C) 2K 1 D) 2K +18. n個(gè)頂點(diǎn)的無向完全圖的弧數(shù)為( D )。A) n (n-1) B) nn C) 2n D) n (n-1) /29. 在一個(gè)圖中，圖的邊數(shù)等于所有頂點(diǎn)的度數(shù)之和的( A )倍。 A) 1/2 B) 1 C) 2 D) 4 10. 圖的廣度優(yōu)先遍歷類似于二叉樹的（ C ）A) 先序遍歷 B) 中序遍歷 C) 層次遍歷 D) 后序遍歷11. 在有n個(gè)葉子結(jié)點(diǎn)的哈夫曼樹中，其結(jié)點(diǎn)總數(shù)為 ( C ) 。A) 不確定 B) 2n C) 2n+1 D) 2n-112. 將一棵有100個(gè)結(jié)點(diǎn)的完全二叉樹從根這一層開始，每一層從左到右依次對(duì)結(jié)點(diǎn)進(jìn)行編號(hào)，根結(jié)點(diǎn)編號(hào)為1，則編號(hào)為36的結(jié)點(diǎn)的左孩子的編號(hào)為( B )A) 71 B) 72 C) 73 D) 3713. 利用逐點(diǎn)插入法建立序列(50，72，43，85，75，20，35，45，65，30)對(duì)應(yīng)的二叉排序樹以后，查找元素35要進(jìn)行（ A ）元素間的比較。A) 4次 B) 5次 C) 7次 D) 10次14. 在順序表 ( 3, 6, 8, 10, 12, 15, 16, 18, 21, 25, 30 ) 中，用折半法查找關(guān)鍵碼值11，所需的關(guān)鍵碼比較次數(shù)為：(B) A) 2 B) 3 C) 4 D) 515. 鏈表適用于（ A ）查找(備注：上次有同學(xué)問過我這個(gè)題目，上次給的答案是錯(cuò)誤的)A) 順序 B) 二分法 C) 順序，也能二分法 D) 隨機(jī)二、 填空題（每空1分,共20分）1. 通常是以算法執(zhí)行所耗費(fèi)的 時(shí)間 和所占用的空間來判斷一個(gè)算法的優(yōu)劣。2. 隊(duì)列中允許進(jìn)行刪除的一端為 隊(duì)頭 。3. 在順序隊(duì)列中，雖然仍有空閑，但不能進(jìn)行入隊(duì)操作，這被稱為是 假溢出 。4. n個(gè)頂點(diǎn)的連通圖的生成樹有 n-1 條邊。5. 后綴算式79 2 20 + - 6 2 / *的值為_ 171 _。中綴算式（8-X*Y）-4*Y/7對(duì)應(yīng)的后綴算式為_8 X Y* - 4 Y*7/- 。6. 若要求一個(gè)稀疏圖G的最小生成樹，最好用 克魯斯卡爾 算法來求解。A1A2A4A5A6A7A3圖17. 若進(jìn)棧序列為a, b, c，則通過入出棧操作可能得到的a, b, c的不同排列個(gè)數(shù)為: 5 （備注：abc acb cba bac bca） 8. 有一棵樹如圖1所示，回答下面的問題：（1） 這棵樹的根結(jié)點(diǎn)是 （9）A1 ;（2） 這棵樹的葉子結(jié)點(diǎn)是 （10）A2,A4,A5,A7 （3） 結(jié)點(diǎn)A3的度是 （11） 2 （4） 這棵樹的度是 （12） 3 （5） 這棵樹的深度是 （13） 4 （6） 結(jié)點(diǎn)A3的子女是 （14） A5,A6 （7） 結(jié)點(diǎn)A3的父結(jié)點(diǎn)是 （15） A1 9. 設(shè)一棵完全二叉樹有678個(gè)結(jié)點(diǎn)，則共有 （16）339 個(gè)葉子結(jié)點(diǎn)。10. 假定一棵二叉樹的結(jié)點(diǎn)數(shù)為18，則它的最小深度為_5 ，最大深度為_18 。11. 若要求一個(gè)稠密圖G的最小生成樹，最好用 普里姆 算法來求解。12. n個(gè)頂點(diǎn)e條邊的圖，若采用鄰接矩陣存儲(chǔ)，則空間復(fù)雜度為 n2 。已知數(shù)據(jù)結(jié)構(gòu)DS的定義如下，請(qǐng)給出其邏輯結(jié)構(gòu)圖示。（5分）DS = (D, R) D = a, b, c, d, e, f R = T T = , , , , , , 已知二叉樹的中序序列為DBGEAFC，后序序列為DGEBFCA，給出對(duì)應(yīng)的二叉樹。（5分）1. 已知葉子結(jié)點(diǎn)值7，17，5，6，9，23，構(gòu)造哈夫曼樹，計(jì)算其帶權(quán)路徑長(zhǎng)度.（10分）2. 已知無向圖如圖2所示，（10分）（1）給出圖的鄰接矩陣。（2）根據(jù)鄰接矩陣從0開始，給出一棵廣度優(yōu)先生成樹。圖2圖3 3. 給定網(wǎng)G 如圖3所示 ，找出網(wǎng)G的最小生成樹，畫出其邏輯結(jié)構(gòu)圖；（4分）三、 編程題（共16分）1、 寫一算法，從順序表中插入自第i個(gè)元素開始的k個(gè)元素。（已知給定抽象數(shù)據(jù)類型及算法參數(shù)，k個(gè)元素值放在數(shù)組a中，請(qǐng)補(bǔ)充完成下面算法）typedef Struct Sqlist int *elem; int length; int listsize; Sqlist;Status Insert(Sqlist &L,int i, int k，int a) 2、 寫算法輸出二叉樹中所有葉子結(jié)點(diǎn)。已知二叉樹抽象數(shù)據(jù)類型為：Typedef Struct Node int data;struct node *lchild,*rchild; Node,*BitNode;承諾：我將嚴(yán)格遵守考場(chǎng)紀(jì)律，知道考試違紀(jì)、作弊的嚴(yán)重性，還知道請(qǐng)他人代考或代他人考者將被開除學(xué)籍和因作弊受到記過及以上處分將不授予學(xué)士學(xué)位，愿承擔(dān)由此引起的一切后果。專業(yè) 班級(jí) 學(xué)號(hào) 學(xué)生簽名： 試卷編號(hào)：（B)卷 數(shù)據(jù)結(jié)構(gòu) 課程 課程類別：必 閉卷 考試日期： 題號(hào)一二三四五六七八九十總分累分人簽名題分2030301010100得分考生注意事項(xiàng)：1、本試卷共 8 頁(yè)，總分100分，考試時(shí)間120分鐘。2、考試結(jié)束后，考生不得將試卷、答題紙和草稿紙帶出考場(chǎng)。3、所有答案必須寫在答題紙上，寫在試卷上無效。一、選擇題(每題2分，共20分) 1單鏈表的一個(gè)存儲(chǔ)結(jié)點(diǎn)包含（D）。 A數(shù)據(jù)域或指針域 B指針域或鏈域 C指針域和鏈域 D數(shù)據(jù)域和指針域2. 線性表是具有n個(gè)（ C ）的有限序列（n0）。 A表元素 B字符 C數(shù)據(jù)元素 D數(shù)據(jù)項(xiàng) 3對(duì)順序表上的插入、刪除算法的時(shí)間復(fù)雜性分析來說，通常以（ B ）為標(biāo)準(zhǔn)操作來考慮。 A條件判斷 B結(jié)點(diǎn)移動(dòng) C算術(shù)表達(dá)式 D賦值語句4循環(huán)鏈表主要優(yōu)點(diǎn)是 （ D ）A不再需要頭指針了B已知某個(gè)結(jié)點(diǎn)的位置后，能夠容易找到它的直接前趨C在進(jìn)行插入、刪除運(yùn)算時(shí)，能更好地保證鏈表不斷開D從表中任一結(jié)點(diǎn)出發(fā)都能掃描到整個(gè)鏈表5棧和隊(duì)都是（ C ）A順序存儲(chǔ)的線性結(jié)構(gòu) B. 鏈?zhǔn)酱鎯?chǔ)的非線性結(jié)構(gòu)C限制存取點(diǎn)的線性結(jié)構(gòu) D限制存取點(diǎn)的非線性結(jié)構(gòu)6下列哪一種圖的鄰接矩陣是對(duì)稱矩陣（ B ）A有向圖 B無向圖 CAOV網(wǎng) DAOE網(wǎng)7. 二維數(shù)組A68采用行優(yōu)先的存儲(chǔ)方法，若每個(gè)元素各占10個(gè)存儲(chǔ)單元，且第1個(gè)元素的A00地址為1000，則元素A47的地址為( B )A. 1282 B. 1390C. 1270 D. 12768. 在深度為6的完全二叉樹中 （ D ）A.最少有31個(gè)結(jié)點(diǎn)，最多有64個(gè)結(jié)點(diǎn)B.最少有32個(gè)結(jié)點(diǎn)，最多有64個(gè)結(jié)點(diǎn)C.最少有31個(gè)結(jié)點(diǎn)，最多有63個(gè)結(jié)點(diǎn)D.最少有32個(gè)結(jié)點(diǎn)，最多有63個(gè)結(jié)點(diǎn)9具有n個(gè)頂點(diǎn)的連通圖至少有（ A ）條邊。 A. n-1 B. n C. n+1 D. 2n10具有3個(gè)結(jié)點(diǎn)的二叉樹的有（ B ）種不同形態(tài)。A. 6 B. 5 C. 3 D. 4二、填空題(每空2分，共30分)1.通常從_正確性 _、_可讀性 _、_健壯性 _、_高效性_ _等幾方面評(píng)價(jià)算法的(包括程序)的質(zhì)量。2.程序段“for(i=l;i=n;i+)k+;for(j=1;j=n;j+)L+=k;”的時(shí)間復(fù)雜度T(n)= _ O（n2）_。3.在循環(huán)隊(duì)列中用數(shù)組A0.m-1 存放隊(duì)列元素，其隊(duì)頭和隊(duì)尾指針分別為front和rear，則當(dāng)前隊(duì)列中的元素個(gè)數(shù)是( rear - front + m) % m 。4.在有n個(gè)結(jié)點(diǎn)的二叉鏈表中，值為非空的鏈域的個(gè)數(shù)為 n-1 。 5.組成串的數(shù)據(jù)元素只能是 字符 ，則INDEX（DATASTRUCTURE，STR）的值為 5 。6.一個(gè)n*n的對(duì)稱矩陣，如果以行或列為主主序存入內(nèi)存，則其存儲(chǔ)容為 n*(n+1) /2 。7.由權(quán)值分別為7，19，2，6，32,3,21,10的葉子結(jié)點(diǎn)生成一棵哈夫曼樹，它的樹高是 6 ，帶權(quán)路徑長(zhǎng)度為 261 。8.若一棵二叉樹具有10個(gè)度為2的結(jié)點(diǎn)，5個(gè)度為1的結(jié)點(diǎn)，則度為0的結(jié)點(diǎn)個(gè)數(shù)是 11 。9.n個(gè)頂點(diǎn)的無向完全圖中含邊的數(shù)目為 n*(n-1) /2 。10.含有n個(gè)記錄的表在等概率情況下順序查找成功的平均查找長(zhǎng)度為（n+1）/2 。三、問答題(共30分)1. （5分）假設(shè)以有序?qū)Ρ硎緩碾p親結(jié)點(diǎn)到孩子結(jié)點(diǎn)的一條邊，若已知樹中邊的集合為,請(qǐng)回答下列問題：（1）哪個(gè)結(jié)點(diǎn)是根結(jié)點(diǎn)？（2）哪些結(jié)點(diǎn)是葉子結(jié)點(diǎn)？（3）哪些結(jié)點(diǎn)是k的祖先？（4）哪些結(jié)點(diǎn)是j的兄弟？（5）樹的深度是多少？2.（5分）已知二叉樹的先序序列和中序序列分別為ABECDFGHIJ和EBCDAFHIGJ，(1)畫出該二叉樹;（2分）(2)寫出該二叉樹的后序序列。（3分）3.（4分）寫出有向圖的所有拓?fù)渑判蛐蛄?。GABCDE ACDBFFEKJGHI解：（1）ABCDEG （2）ABCEDG4.（4分）請(qǐng)畫出與下列森林對(duì)應(yīng)的二叉樹。ACDBFEKJGHI5.（8分）已知一個(gè)無向圖的鄰接表如下圖所示。 V5V1V2V3V411234525433445221 （1）畫出該圖的圖形；（2分）（2）求出每個(gè)頂點(diǎn)的度；（2分）（3）根據(jù)鄰接表從頂點(diǎn) V1 出發(fā)進(jìn)行深度優(yōu)先遍歷和廣度優(yōu)先遍歷，寫出相應(yīng)的遍歷序列。（4分）6. （4分）連通網(wǎng)絡(luò)如圖所示。試按 (頂點(diǎn)1，頂點(diǎn)2，權(quán)值)的格式，應(yīng)用克魯斯卡爾算法給出在構(gòu)造最小生成樹過程中順序選出的各條邊。( 頂點(diǎn)1 ， 頂點(diǎn)2 ， 權(quán)值 )( 1 , 3 , 1 )( 4 , 6 , 2 )( 2 , 5 , 3 )( 3 , 6 , 4 )( 2 , 3 , 5 )四、算法填空題(每空2分，共10分). 請(qǐng)讀下列程序，該程序是在單鏈表中刪除一個(gè)結(jié)點(diǎn)的算法，為空出的地方填上正確的語句。 void demo2(LinkList head,ListNode *p) /head 是帶頭結(jié)點(diǎn)的單鏈表，刪除P指向的結(jié)點(diǎn) ListNode *q=head； while(q& （1）q-next!=p ) q=q-next； if (!q) Error(“*p not in head”); （2）q-next=p-next； （3） free(p)； 2.假設(shè)稱正讀和反讀相同的字符序列為“回文”，例如，abba和abcba是回文，abcde和ababab則不是回文。下面算法是判別讀入一個(gè)以為結(jié)束符的字符序列是否是“回文”。int Palindrome_Test() InitStack(S); InitQueue(Q); while(c=getchar()!=) (4)Push(S