數(shù)據(jù)結(jié)構(gòu)B試題及答案

一、單項(xiàng)選擇題（2分×10=20分）1．若某線性表中最常用的操作是提取第i個(gè)元素及找第i個(gè)元素的前驅(qū)元素，則采用（D）存儲(chǔ)方式最省時(shí)間。A.單鏈表B.雙鏈表C.單向循環(huán)鏈表D.順序表2．將含有100個(gè)結(jié)點(diǎn)的完全二叉樹(shù)從根開(kāi)始自上向下，每層從左到右依次編號(hào)，且設(shè)根結(jié)點(diǎn)的編號(hào)為1，則編號(hào)69的結(jié)點(diǎn)的雙親的編號(hào)為（A）。A.34B.35C.33D.無(wú)法確定3.單循環(huán)鏈表的主要優(yōu)點(diǎn)是（D）。A.不再需要頭指針了B.已知某結(jié)點(diǎn)的位置后，很容易找到其前驅(qū)C.在進(jìn)行插入、刪除運(yùn)算時(shí)，能更好地保證鏈表不斷開(kāi)D.從表中任一結(jié)點(diǎn)出發(fā)都能掃描到整個(gè)鏈表4.在長(zhǎng)為n的順序表中，向第i個(gè)元素(1≤i≤n+1)前插入一個(gè)元素需要向后移動(dòng)（B）個(gè)元素。A.n-iB.n-i+1C.n-i-1D.i5.一個(gè)棧的入棧順序是1、2、3、4、5，則此棧不可能的輸出順序?yàn)椋–）。A.5、4、3、2、1C.4、3、5、1、2B.4、5、3、2、1D.1、2、3、4、56.串是一種特殊的線性表，其特殊性表現(xiàn)在（B）。A.可以順序存儲(chǔ)C可以鏈?zhǔn)酱鎯?chǔ)B.數(shù)據(jù)元素是一個(gè)字符D.數(shù)據(jù)元素是多個(gè)字符7.一棵5層滿二叉樹(shù)中，結(jié)點(diǎn)總數(shù)為（C）個(gè)。A.338.下列4棵二叉樹(shù)，（B）是平衡樹(shù)。B.32C.31D.30A.B.C.D.9.n個(gè)頂點(diǎn)的無(wú)向圖中最多有（A）條邊。A.n(n-1)/2B.n(n-1)C.n(n+1)D.n(n+1)/210.6個(gè)頂點(diǎn)的無(wú)向圖中，至少有（A）條邊才能保證是一個(gè)連通圖。A.5B.6C.7D.8二、判斷題（1分×10=10分）（F）1.線性結(jié)構(gòu)的基本特征是：每個(gè)結(jié)點(diǎn)有且僅有一個(gè)直接前驅(qū)和一個(gè)直接后繼。（F）2.二叉樹(shù)是樹(shù)的特殊情形。（T）3.存在這樣的二叉樹(shù)，其先序遍歷與中序遍歷得到的訪問(wèn)序列相同。（F）4.用一維數(shù)組存儲(chǔ)二叉樹(shù)時(shí)，總是以先序遍歷的順序存儲(chǔ)結(jié)點(diǎn)。（F）5.空串就是由空格組成的串。（F）6.在AOE網(wǎng)中，一定只有一條關(guān)鍵路徑。（T）7.m階B-樹(shù)每一個(gè)結(jié)點(diǎn)的子樹(shù)個(gè)數(shù)都小于或等于m.（T）8.插入排序是穩(wěn)定的。（T）9.順序存儲(chǔ)的線性表可以實(shí)現(xiàn)隨機(jī)存取。（F）10.二叉樹(shù)按某種順序線索化后，任一結(jié)點(diǎn)均有指向其直接前驅(qū)和直接后繼的線索。三、填空題（2分×8=16分）1．在單鏈表中，若要在指針p所指結(jié)點(diǎn)后插入指針s所指結(jié)點(diǎn)，則需要執(zhí)行下列兩條語(yǔ)句：s->next=p->next；p->next=s；2.在有頭結(jié)點(diǎn)的單鏈表L中，指針p所指結(jié)點(diǎn)是第一個(gè)結(jié)點(diǎn)的條件是p=L->next。3.棧是一種受限制的線性表，也叫LIFO結(jié)構(gòu)，LIFO的含義是后進(jìn)先出。4.對(duì)于隊(duì)，只能在刪除元素。隊(duì)尾插入元素，只能在隊(duì)頭5.抽象數(shù)據(jù)類型ADT可以用三元組（D，S，P）表示，它們分別表示：數(shù)據(jù)對(duì)象、數(shù)據(jù)關(guān)系和基本操作。四、簡(jiǎn)答和應(yīng)用題（38分）1.（8分）某二叉樹(shù)先序遍歷的結(jié)果是ABCDEFG，中序遍歷的結(jié)果是CBDAFGE.（1）（2）A畫(huà)出此二叉樹(shù)；寫(xiě)出其后先序遍歷的結(jié)果。BECDFG(5分)CDBGFEA(3分)2.（9分）已知如圖所示有向圖，（1）（2）（3）求各點(diǎn)的入度和出度；給出該圖的鄰接矩陣；給出該圖的鄰接表。(1)1:0,32:2,13:3,04:1,15:1,2(3)01→1→3→4^12→2^23^34→2^45→1→2^(2)0101100100000000010001100(各3分)3.給出下面稀疏矩陣的三元組。（5分）5行6列:(1,2,12),(2,1,9),(4,1,-1),(4,5,10),(5