數(shù)據(jù)結(jié)構(gòu)選擇題答案及相關(guān)知識(shí)點(diǎn)

1、1、在一棵具有 5 層的滿二叉樹(shù)中結(jié)點(diǎn)總數(shù)為（A ）。A) 31B）32C） 33D）16(2n) - 1,N = 2 k-1(N 總結(jié)點(diǎn)數(shù)， k 層數(shù) )2、串的邏輯結(jié)構(gòu)與（A ）的邏輯結(jié)構(gòu)不相同。A）線性表B）棧C）隊(duì)列D）集合串的邏輯結(jié)構(gòu)和線性表極為相似， 區(qū)別僅在于串的數(shù)據(jù)對(duì)象約束為字符集。P713、下列序列中，執(zhí)行第一趟快速排序后得到的序列是（A）。A） d,a,e,d,bfh,gB) c,e,a,dfh,g,bC) g,a,e,c,bfd,hD) a,b,c,d,fe,g,h左大右小4、n 個(gè)頂點(diǎn)的強(qiáng)連通圖至少有（C ）條邊。A） nB）n+1C）n-1D）n(n-1)單節(jié)點(diǎn)除外，

2、 so,-15、設(shè)單鏈表中指針 p 指著結(jié)點(diǎn) A，若要?jiǎng)h除 A 之后的結(jié)點(diǎn)（若存在），則需要修改指針的操作為（ A ）。A） p-next=p-next-next B） p=p-nextC） p=p-nexe-nextD） p-next=p無(wú)限刪除6、對(duì)下圖 V4 的度為（C ）。A）1B ）2C ）3D ）4v1v2v3v47、在一棵度為 3 的樹(shù)中，度為 3 的結(jié)點(diǎn)個(gè)數(shù)為 2，度為 2 的結(jié)點(diǎn)個(gè)數(shù)為 1，則度為 0 的結(jié)點(diǎn)個(gè)數(shù)為（ C ）。A）4B）5C）6D）7圖 1-7設(shè)度為 0 的結(jié)點(diǎn) 個(gè)數(shù)為 n0 ，度為 1 的結(jié)點(diǎn) 個(gè)數(shù)為 n1 ，度為 2 的結(jié)點(diǎn) 個(gè)數(shù)為 n2，度為 3 的個(gè)數(shù)

3、 n3樹(shù)中結(jié)點(diǎn)總數(shù)n0+ n1 + n2 + n3 ，所有邊的數(shù)量為0 * n0 + 1 * n1 + 2 * n2 +3 * n3樹(shù)中結(jié)點(diǎn)比邊多1 個(gè)，合并這兩個(gè)式子就可以得到：n0 = 1 + n2 + 2 * n38、在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為（C ）。A）動(dòng)態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)B）緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)C）線性結(jié)構(gòu)和非線性結(jié)構(gòu)D）內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu) 分兩大類：線性結(jié)構(gòu)和 非線性結(jié)構(gòu)數(shù)據(jù)的存儲(chǔ)方法 有四種： 順序存儲(chǔ)方法、 鏈接存儲(chǔ)方法、 索引存儲(chǔ)方法 和散列存儲(chǔ)方法 ( hash 存儲(chǔ) )9、用一維數(shù)組 A 進(jìn)行順序存儲(chǔ)時(shí)，若起始地址為loc(A1) ，元素長(zhǎng)度為

4、c，則 A 的第 i個(gè)數(shù)組單元在存放地址loc(Ai)，等于（B）。A）loc(A1)+i*cB）loc(A1)+(i-1)*cC）loc(A1)+i*c+1D）loc(A1)+(i+1)*c10、（ C ）在進(jìn)行插入操作時(shí)，常產(chǎn)生假溢出現(xiàn)象。A）順序棧B）循環(huán)隊(duì)列C）順序隊(duì)列D）鏈隊(duì)列循環(huán)隊(duì)列產(chǎn)生是為了解決順序隊(duì)列的假溢出11、下列各種數(shù)據(jù)結(jié)構(gòu)中屬于線性結(jié)構(gòu)的有（A ）。A）棧B)二叉樹(shù)C) 廣義表D)圖數(shù)據(jù)元素之間的關(guān)系稱為結(jié)構(gòu) ：1. 集合； 2. 線性結(jié)構(gòu)； 3.樹(shù)形結(jié)構(gòu)； 4. 圖 / 網(wǎng)狀結(jié)構(gòu)12、倘若在對(duì)串的插入、刪除運(yùn)算中，期望運(yùn)算速度最快，則應(yīng)采用（B ）。A）順序表示法B）

5、單字符為結(jié)點(diǎn)的單鏈表表示法C）等量分塊表示法D）不等量分塊表示法13、廣義表 head(a,b),(c,d)的運(yùn)算結(jié)果為（D）。A） (a,b)B）(c,d)C）空表D）（ a,b ）,(c,d)）14、n 個(gè)頂點(diǎn)的圖的最小生成樹(shù)必定 （D），是不正確的描述。A）不唯一B）權(quán)的總和唯一C）不含回路D）有 n 條邊15、采用鏈結(jié)構(gòu)存儲(chǔ)線性表時(shí)，其地址（B）。A）必須是連續(xù)的B）連續(xù)不連續(xù)都可以C）部分地址必須是連續(xù)D）必須是不連續(xù)的16、隊(duì)列的操作的原則是（A）。A）先進(jìn)先出B)后進(jìn)先出C) 只能進(jìn)行插入D)只能進(jìn)行刪除U字走法，不是 Y17、設(shè)給定問(wèn)題的規(guī)模為變量n，解決該問(wèn)題的算法所需時(shí)間為

6、Tn=O(f(n),Tn 表示式中記號(hào)O表示（A）。A）一個(gè)數(shù)量級(jí)別B）一個(gè)平均值C）一個(gè)最大值D）一個(gè)均方值18、線性表的鏈接實(shí)現(xiàn)有利于（A）運(yùn)算。A）插入B）讀元素C）查找D）定位20、下面程序段的時(shí)間復(fù)雜度是(A ) 。s =0;for( i =0; in; i+)for(j=0;jLchild=NullB) D-ltag=1C) D-Rchild=NullD) D-ltag=0L Tag0 lchild域指示節(jié)點(diǎn)的左孩子 ;1 lchild域指示節(jié)點(diǎn)的前驅(qū) R tag0 rchild域指示節(jié)點(diǎn)的左孩子 ;1 rchild域指示節(jié)點(diǎn)的前驅(qū) 沒(méi)有前趨結(jié)點(diǎn)并沒(méi)有左子樹(shù)就沒(méi)有左孩子，通常沒(méi)有頭

7、結(jié)點(diǎn)的情況下，中序遍歷的第一個(gè)結(jié)點(diǎn)就滿足條件。29、棧進(jìn)行插入和刪除操作的特點(diǎn)是（A）。A） LIFOB） FIFOC） FCFSD） HPFLIFO = “l(fā)ast in first out”30、與無(wú)向圖相關(guān)的術(shù)語(yǔ)有（C）。A）強(qiáng)連通圖B ）入度C）路徑D ）弧32、若采用鄰接矩陣法存儲(chǔ)一個(gè) n 個(gè)頂點(diǎn)的無(wú)向圖，則該鄰接矩陣是一個(gè)（ D ）。A）上三角矩陣B)稀疏矩陣C) 對(duì)角矩陣D)對(duì)稱矩陣34、棧進(jìn)行插入和刪除操作的特點(diǎn)是（A）。A） LIFOB） FIFOC） FCFSD） HPF39、在循環(huán)隊(duì)列中，若 front 與 rear 分別表示對(duì)頭元素和隊(duì)尾元素的位置，則判斷循環(huán)隊(duì)列空的條

8、件是 ( C ) 。A）front=rear+1B）rear=front+1C）front=rearD）front=0此時(shí)我們約定：少用一個(gè)元素，“隊(duì)列頭指針在隊(duì)列尾指針的下一位置”作為隊(duì)列呈“滿”狀態(tài)的標(biāo)志。43、在有 n 個(gè)葉結(jié)點(diǎn)的哈夫曼樹(shù)中其結(jié)點(diǎn)總數(shù)為： （D）。（ A ）不確定（ B ）2 n（ C） 2 n + 1（ D） 2 n 1無(wú)論哈夫曼樹(shù)是幾叉，其特點(diǎn)是一致的（假設(shè)為m 叉），即樹(shù)中只存在度為 0 的結(jié)點(diǎn)（即葉結(jié)點(diǎn)） 和度為 m 的結(jié)點(diǎn)。不妨設(shè)度為 0 的結(jié)點(diǎn)個(gè)數(shù)為 x，度為 m 的結(jié)點(diǎn)個(gè)數(shù)為 y，則存在一個(gè)等式 x+y=my+1 ，即 x=(m-1)y+1 ，x+y是樹(shù)的總

9、結(jié)點(diǎn)個(gè)數(shù)。就這道題來(lái)說(shuō)，假設(shè)哈夫曼樹(shù)是二叉的話，則度為0 的結(jié)點(diǎn)個(gè)數(shù)為N，度為 2 的結(jié)點(diǎn)個(gè)數(shù)為N-1 ，則結(jié)點(diǎn)總數(shù)為2N-1 。44、（C）在進(jìn)行插入操作時(shí)，常產(chǎn)生假溢出現(xiàn)象。A）順序棧B）循環(huán)隊(duì)列C）順序隊(duì)列D）鏈隊(duì)列1-10 這個(gè)要記一下 , 重復(fù)就重復(fù)48、某二叉樹(shù)結(jié)點(diǎn)的中序序列為ABCDEFG，后序序列為BDCAFGE，則其左子樹(shù)中結(jié)點(diǎn)數(shù)目為： (C )A）3B）2C）4D） 5后序最后一個(gè)為根節(jié)點(diǎn)49、在數(shù)據(jù)結(jié)構(gòu)中假定在一棵二叉樹(shù)中， 度為 2 的結(jié)點(diǎn)數(shù)為 15 個(gè)，度為 1 的結(jié)點(diǎn)數(shù)為 32 個(gè)，則葉子結(jié)點(diǎn)數(shù)為（B）個(gè)。A）15B）16C）17D）47每個(gè)分枝下面都有一個(gè)結(jié)點(diǎn)，所

10、以總結(jié)點(diǎn)數(shù)N=2*15+1*32+0*葉子數(shù) +1( 根節(jié)點(diǎn)） =63二叉樹(shù)中除了雙分支結(jié)點(diǎn)，單分支結(jié)點(diǎn)就是葉子結(jié)點(diǎn)。所以葉子數(shù) =63-15-32=16.50、樹(shù)最適合用來(lái)表示 (C )。A）有序數(shù)據(jù)元素B）無(wú)序數(shù)據(jù)元素C）元素之間具有分支層次關(guān)系的數(shù)據(jù)D）元素之間無(wú)聯(lián)系的數(shù)據(jù)51、在順序存儲(chǔ)結(jié)構(gòu)的線性表中第 i 個(gè)元素 (1=inext =NULLC）head-next =headD）head!=NULL61、二維數(shù)組 A33 按行優(yōu)先順序存儲(chǔ)， 若數(shù)組元素 A11 的存儲(chǔ)地址為 1087，A22 的存儲(chǔ)地址為1095，則數(shù)組元素A00的存儲(chǔ)地址為（A）。A ）1079B）1080C）10

11、78D）1060（1095-1087）/4 =2； A00 = A11 -8 = 107962、在按層次遍歷二叉樹(shù)的算法中，需要借助的輔助數(shù)據(jù)結(jié)構(gòu)是（A）A）隊(duì)列B）棧C）線性表D）有序表63、對(duì)線性表進(jìn)行折半查找時(shí)，要求線性表必須（B）。A ）以順序方式存儲(chǔ)B）以順序方式存儲(chǔ)，且結(jié)點(diǎn)按關(guān)鍵字有序排列C）以鏈?zhǔn)椒绞酱鎯?chǔ)D）以鏈?zhǔn)椒绞酱鎯?chǔ)，且結(jié)點(diǎn)按關(guān)鍵字有序排列64、節(jié)點(diǎn)的帶權(quán)路徑是指從根節(jié)點(diǎn)到該節(jié)點(diǎn)的路徑長(zhǎng)度乘以該節(jié)點(diǎn)的權(quán)值，樹(shù)的帶權(quán)路徑長(zhǎng)度是指樹(shù)中所有葉子節(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和，已知葉子節(jié)點(diǎn)a,b,c 的權(quán)分別是 2,5,7左邊給出的樹(shù)的帶權(quán)路徑長(zhǎng)度為（A ）A）21B） 14cC）22D）

12、28(2+5)*2+7=21ab65、對(duì)一棵有 n 個(gè)節(jié)點(diǎn)的二叉樹(shù)按上述方法對(duì)節(jié)點(diǎn)進(jìn)行編號(hào)，如果編號(hào)為 i(inext = NULLB）p = NULLC）p-next =headD）p = headAB68、設(shè)無(wú)向圖的鄰接鏈表如圖所示， 則該圖的邊的數(shù)目是（）ABCD(1) 完全二叉樹(shù) 只有最下面的兩層結(jié)點(diǎn)度小于 2 ，并且最下面一層的結(jié)點(diǎn)都集中在該層最左邊的若干位置的二叉樹(shù)；(2) 滿二叉樹(shù) 除了葉結(jié)點(diǎn)外每一個(gè)結(jié)點(diǎn)都有左右子葉且葉結(jié)點(diǎn)都處在最底層的二叉樹(shù) ,。(3) 平衡二叉樹(shù) 一棵空樹(shù)或左右兩個(gè)子樹(shù)的高度差的絕對(duì)值不超過(guò) 1 ，并且左右兩個(gè)子樹(shù)都是一棵平衡二叉樹(shù)。66、若用鄰接矩陣表示一

13、個(gè)有向圖，則其中每一列包含的 1的個(gè)數(shù)為（ B ）。A ）圖中每個(gè)頂點(diǎn)的入度B）圖中每個(gè)頂點(diǎn)的出度A） 4B）5C） 10D）20VV69、下面的算法中（A）是用來(lái)構(gòu)造最小生成樹(shù)的算法。A ）普里姆（ Prim）算法B ） 迪 杰 斯 特 拉（ Dijkstra ）算法VVC）弗洛伊德（Floyd ）算法D）拓?fù)渑判駼:是從一個(gè)頂點(diǎn)到其余各頂點(diǎn)的最短路徑算法，解決的是有向圖中最短路徑問(wèn)題。C: 是一種用于尋找給定的加權(quán)圖中多源點(diǎn)之間最短路徑的算法。D: 對(duì)一個(gè)有向無(wú)環(huán)圖G 進(jìn)行拓?fù)渑判?，是將G 中所有頂點(diǎn)排成一個(gè)線性序列，使得圖中任意一對(duì)頂點(diǎn)u 和 v，若邊 +-(u,v) E(G) ，則 u 在線性序列中出現(xiàn)在v 之前。70、設(shè)有一個(gè)棧，元素依次進(jìn)棧的順序?yàn)锳 、B、 C、D、E。下列 (C)是不可能的出棧序列。A ）A,B,C,D,EB）B,C,D,E,AC）E,A,B,C,DD）E,D,C,B,A71、若有序表的關(guān)鍵字