數(shù)據(jù)結(jié)構(gòu)B期末考試B卷及參考答案

一、單項選擇題（每小題2分，共30分）.下列關(guān)于棧的敘述中，正確的是（）。A.棧底元素一定是最后入棧的元素 B.棧操作遵循先進后出的原則C.棧頂元素一定是最先入棧的元素 D,以上三種說法都不對.在數(shù)據(jù)結(jié)構(gòu)中，與所使用的計算機硬件無關(guān)的是數(shù)據(jù)的（）結(jié)構(gòu)。A.邏輯 B.存儲C.邏輯和存儲 D.物理.以下說法正確的是（）。A.數(shù)據(jù)項是數(shù)據(jù)的基本單位8.數(shù)據(jù)元素是數(shù)據(jù)的最小單位C.數(shù)據(jù)結(jié)構(gòu)是帶結(jié)構(gòu)的數(shù)據(jù)項的集合D.一些表面上很不相同的數(shù)據(jù)可以有相同的邏輯結(jié)構(gòu).六個元素按照6,5,4,3,2,1的順序入棧，下列哪一個是合法的出棧序列？（）A.546132 B.453126 C.346512 D.234156.設(shè)樹的度為4,其中度為1、2、3、4的結(jié)點個數(shù)分別是4、2、1、2,則樹中葉子個數(shù)為（）A.8 B.9 C.10 D.11.分別用以下序列構(gòu)造二叉排序樹，與用其他三個序列構(gòu)造的結(jié)果不同的是（）A.（100,80,90,60,120,110,130） B.（100,120,110,130,80,60,90）C.（100,60,80,90,120,110,130） D.（100,80,60,90,120,130,110）.下列陳述中正確的是（）A.二叉樹是度為2的有序樹.二叉樹中結(jié)點只有一個孩子時無左右之分C.二叉樹中必有度為2的結(jié)點D.二叉樹中最多只有兩棵子樹，并且有左右之分.在含n個頂點和e條邊的無向圖的鄰接矩陣中，零元素的個數(shù)為（）A.eB.2eC.n2—e D.n2—2e.棧和隊列都是（）A.限制存取位置的線性結(jié)構(gòu)B.順序存儲的線性結(jié)構(gòu)C.鏈式存儲的線性結(jié)構(gòu)D.限制存取位置的非線性結(jié)構(gòu).在具有n個葉子結(jié)點的嚴格二叉樹（即結(jié)點的度要么是0要么是2）中，結(jié)點總數(shù)為（）A.2n+1B.2nC.2n-1D.2n-2.在循環(huán)雙鏈表的p所指的結(jié)點之前插入s所指結(jié)點的操作是（）。p->prior=s；s->next=p；p->prior->next=s；s->prior=p->priorp->prior=s；p->prior->next=s；s->next=p；s->prior=p->priorB卷第1頁/共9頁s->next=p；s->prior=p->prior；p->prior=s；p->prior->next=ss->next=p；s->prior=p->prior；p->prior->next=s；p->prior=s.單鏈表中，增加一個頭結(jié)點的目的是為了（）。A.使單鏈表至少有一個結(jié)點 B,標識表結(jié)點中首結(jié)點的位置C.方便算法的實現(xiàn) D.說明單鏈表是線性表的鏈式存儲.對一個滿二叉樹，m個葉子，n個結(jié)點，深度為％則（）。A.n=h+mBh+m=2nCm=h-1Dn=2h-1.采用鄰接表存儲的圖的廣度優(yōu)先遍歷算法類似于二叉樹的（）。A.先序遍歷 B.中序遍歷 C.后序遍歷 D.按層遍歷.n個結(jié)點的有向圖，至少需要（）條有向邊（?。┎拍軜?gòu)成強連通圖。A.2n B.nC.n(n-1) D.n-1二、判斷題（在你認為正確的題后寫上“對”；在你認為是錯誤的題后寫上“錯”并予以改正，但要符合原義，改動應(yīng)少，每小題1分，共15分）.對于一個線性表，采用順序存儲方式進行插入和刪除結(jié)點時效率太低，采用鏈式存儲方式更好。（）.在順序表中，最后一個元素有一個后繼。（）.使用雙向鏈表可隨機訪問任一結(jié)點。（）.在單鏈表中,給定任一結(jié)點的地址p，則可用下述語句將新結(jié)點$插入結(jié)點p的后面：p—>next；（）.完全二叉樹不一定是平衡二叉樹。（）.堆排序是非穩(wěn)定的排序算法。（）.抽象數(shù)據(jù)類型與計算機內(nèi)部表示和實現(xiàn)無關(guān)。（）.順序存儲方式插入和刪除時效率太低，因此它不如鏈式存儲方式好。（）.線性表采用鏈式存儲結(jié)構(gòu)時，結(jié)點和結(jié)點內(nèi)部的存儲空間可以是不連續(xù)的。（）.對稀疏矩陣進行壓縮存儲的目的是便于輸入和輸出。（）.起泡排序算法在最好情況下的時間復雜度為O（n）o（）.串是一種特殊的線性表，其特殊性體現(xiàn)在數(shù)據(jù)元素可以是多個字符。（）.空串和空白串是相同的。（）.任意一棵二叉樹中的度可以小于2o（）.順序查找法適合于存儲結(jié)構(gòu)為順序存儲或鏈式存儲的線性表。（）三、填空題（每空1分，共15分）.如果M有5個兄弟，而N是M的雙親，則N的度是⑴B卷第2頁/共9頁.如果二叉樹中有20個葉子節(jié)點，30個度為1的結(jié)點，則該二叉樹的總結(jié)點數(shù)為(2)。.若用n表示圖中的頂點數(shù)目，則有 (3) 條邊的無向圖被稱為完全圖。.在二叉樹的第i(i>=1)層上至多有 (4) 個結(jié)點。.克魯斯卡爾算法的時間復雜度是 ⑸ ，它適合求 (6)圖的最小生成樹。TOC\o"1-5"\h\z.高度為6的完全二叉樹，其結(jié)點最少有 ⑺個。.圖的存儲常采用 (8)和(9) 兩種方法。.深度為5的二叉樹至多有 (10) 個結(jié)點。.具有10個頂點的無向圖，邊的總數(shù)最多為 (11)。.數(shù)據(jù)邏輯結(jié)構(gòu)包括 (12) 、 (13)和(14) 三種類型。.直接插入排序中使用的監(jiān)視哨的作用是 (15)。四、算法填空(每空2分，共10分)1.完成以下中序遍歷二叉樹的算法typedefstructBitNode{TelemTypedata; 〃結(jié)點的值structBiTNode*lchild,*rchild;〃左右孩子}BiTNode,*BiTree;voidinorder(BiTreebt){if(bt){ (1) ;visit(bt->data);⑵ ；}}2.以下算法實現(xiàn)在單向鏈表中第i個元素之前插入一個新結(jié)點，結(jié)點值為e。statusListinsert_L(Linklist&L,inti,Elemtypee){p=L;j=0;〃插入位置可為1，因此其前一位置j從0開始while(p&&j<i-1)〃查找第i-1個結(jié)點B卷第3頁/共9頁{p=p->next;++j;}if(!p||j>i-1)returnERROR;//表空和i>表長||i<1操作非法s=(Linklist)malloc(sizeof(LNodes));(5)=e；=p->next; //插入=s;returnOK;}五、綜合題（每小題6分，共30分）1.請寫出如圖1所示二叉樹的先序遍歷序列、中序遍歷序列和后序遍歷序列。（6分）ABDCG圖12.已知如圖2所示的有向圖，請給出：（共6分）頂點123456入度出度①每個頂點的入度和出度；（3分）②右圖的鄰接矩陣；（3分）23465圖23.已知有向圖的鄰接表如圖3所示。（6分）1)畫出該有向圖;2)寫出從頂點A出發(fā)3)寫出從頂點A出發(fā)深度優(yōu)先遍歷結(jié)點訪問次序（用字母表示）;廣度優(yōu)先遍歷結(jié)點訪問次序（用字母表示）。B卷第4頁/共9頁012345圖31~5JXXXJ6-10WXXX11~15VXXVV三、填空題(每空1分，共15分)1~5VXXXV6~10VVXXX11~15VXXVV4.已知一組記錄為(46,1~5JXXXJ6-10WXXX11~15VXXVV三、填空題(每空1分，共15分)1~5VXXXV6~10VVXXX11~15VXXVV劃分次序劃分結(jié)果第一次[38??..]46[56??..]第二次第三次第四次第五次第六次5.已知某系統(tǒng)在通信聯(lián)絡(luò)中只可能出現(xiàn)10種字符(從字母A到字母J),各字符出現(xiàn)的概率分別為A(0.02),B(0.03),C(0.1),D(0.19),E(0.07),F(0.08),G(0.13),H(0.22),I(0.04),1(0.12),畫出哈夫曼樹，并寫出各字符的哈夫曼編碼。(6分)一、單項選擇題(每小題2分，共30分)1~5BADBD6-10CDDAC11~15DCDDB二、判斷題(正確的劃“J”，錯誤的劃“X”，每小題1分，共15分)162693n(n-1)/242i-15O(eloge)6稀疏圖7328鄰接矩陣9鄰接表1031114512線性結(jié)構(gòu)B卷第5頁/共9頁13樹形結(jié)構(gòu)14圖狀結(jié)構(gòu)15免去查找過程中每一步都要檢測整個表是否查找完畢，提高查找效率四、算法填空（每空2分，共10分）1inorder(bt->lchild)2inorder(bt->rchild)3s->data4s->next5p->next五、綜合題（每小題6分，共30分）.右圖所示二叉樹的先序遍歷序列為ABDGCEF、中序遍歷序列DGBEFCA和后序遍歷序列GDFECBAo（前序、中序和后序各2分，共6分）.已知如右圖所示的有向圖，請給出：（共6分）①每個頂點的入度和出度（3分）頂點123456入度122123出度213311②鄰接矩陣為（3分）V（G）白白區(qū)|回回回TOC\o"1-5"\h\z0 110 0 00 0 0 0 0 10101101 0 0 0 1 10 0 0 0 0 10 0 1 0 0 0B卷第6頁/共9頁

.已知有向圖的鄰接表如右圖所示。(此題共6分)1)畫出該有向圖；(2分)2)寫出從頂點A出發(fā)，深度優(yōu)先遍歷結(jié)點訪問次序(用字母表示)；(2分，答案不唯一)ACDBEF3)寫出從頂點A出發(fā)，廣度優(yōu)先遍歷結(jié)點訪問次序(用字母表示)。(2分，答案不唯一)ACEFDB.已知一組記錄為(46,79,56,38,40，80,95,24)，寫出對其進行快速排序的每一次劃分結(jié)果。劃分次序劃分結(jié)果第一次[244038]46[56809579]第二次24[4038]46[56809579]第三次24384046[56809579]第四次2438404656[809579]第五次243840465679[8095]第六次2438404656798095.已知某系統(tǒng)在通信聯(lián)絡(luò)中只可能出現(xiàn)10種字符(從字母A到字母J),各字符出現(xiàn)的概率分別為A(0.02),B(0.03),C(0.1),D(0.19),E(0.07),F(0.08),G(0.13),H(0.22),I(0.04),J(0.12),畫出哈夫曼樹，并寫出各字符的哈夫曼編碼。(本題答案不唯一，只要滿足要求即可)。B卷第7頁/共9頁答：哈夫曼樹為(3分)：A BA B各字母的編碼為(各字母的編碼長度應(yīng)與答案相同并滿足相關(guān)要求，每個編碼0.3分))：A(00000),B(00001),C(100),D(001),E(1011),F(0001),G