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

1、1、在一棵具有5層的滿二叉樹中結(jié)點(diǎn)總數(shù)為（ A ）。A) 31 B）32C）33 D）16(2n) - 1,N = 2k-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ù)對象約束為字符集。P713、下列序列中，執(zhí)行第一趟快速排序后得到的序列是（A）。A）d,a,e,d,bfh,g B) c,e,a,dfh,g,bC) g,a,e,c,bfd,h D) a,b,c,d,fe,g,h左大右小4、n個(gè)頂點(diǎn)的強(qiáng)連通圖至少有（ C ）條邊。A）n B）n+1 C）n-1 D）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-next D）p-next=p無限刪除6、對下圖V4的度為（ C ）。A）1 B）2 C）3 D）4 v1 v2 v3 v47、在一棵度為3的樹中，度為3的結(jié)點(diǎn)個(gè)數(shù)為2，度為2的結(jié)點(diǎn)個(gè)數(shù)為1，則度為0的結(jié)點(diǎn)個(gè)數(shù)為（ C ）。A）4 B）5C）6 D）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ù)n3樹中結(jié)點(diǎn)總數(shù)n0+ n1 + n2 + n3，所有邊的數(shù)量

3、為0 * n0 + 1 * n1 + 2 * n2 + 3 * n3樹中結(jié)點(diǎn)比邊多1個(gè)，合并這兩個(gè)式子就可以得到：n0 = 1 + n2 + 2 * n38、在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為（ C ）。 A）動態(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ù)的存儲方法有四種： 順序存儲方法 、 鏈接存儲方法 、 索引存儲方法和散列存儲方法(hash存儲)9、用一維數(shù)組A進(jìn)行順序存儲時(shí)，若起始地址為loc(A1)，元素長度為c，則A的第i個(gè)數(shù)組單元在存放地址loc(Ai)，等于（ B ）

4、。A）loc(A1)+i*c B）loc(A1)+(i-1)*cC）loc(A1)+i*c+1 D）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) 二叉樹C) 廣義表 D) 圖數(shù)據(jù)元素之間的關(guān)系稱為結(jié)構(gòu)：1.集合；2.線性結(jié)構(gòu)；3.樹形結(jié)構(gòu)；4.圖/網(wǎng)狀結(jié)構(gòu)12、倘若在對串的插入、刪除運(yùn)算中，期望運(yùn)算速度最快，則應(yīng)采用（ B ）。A）順序表示法 B）單字符為結(jié)點(diǎn)的單鏈表表示法C）等量分塊表示法 D）不等量分塊表

5、示法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)的圖的最小生成樹必定（ D ），是不正確的描述。A）不唯一 B）權(quán)的總和唯一C）不含回路 D）有n條邊15、采用鏈結(jié)構(gòu)存儲線性表時(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è)給定問題的規(guī)模為變量n，解決該問題的算法所需時(shí)間為Tn=O(f(n),Tn表示式中記號O表

6、示（ A ）。A）一個(gè)數(shù)量級別 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=Null B) D-ltag=1C) D-Rchild=Null D) 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ū)沒有前趨結(jié)點(diǎn)并沒有左子樹就沒有左孩子，通常沒有頭結(jié)點(diǎn)的情況下，中序遍歷的

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

8、front=rear+1 B）rear=front+1 C）front=rear D）front=0 此時(shí)我們約定：少用一個(gè)元素，“隊(duì)列頭指針在隊(duì)列尾指針的下一位置”作為隊(duì)列呈“滿”狀態(tài)的標(biāo)志。43、在有n個(gè)葉結(jié)點(diǎn)的哈夫曼樹中其結(jié)點(diǎn)總數(shù)為：（ D ）。（A）不確定 （B）2 n （C）2 n + 1 （D）2 n 1無論哈夫曼樹是幾叉，其特點(diǎn)是一致的（假設(shè)為m叉），即樹中只存在度為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是樹的總結(jié)點(diǎn)個(gè)數(shù)。就這道題來說，假設(shè)哈夫曼樹是二叉的話，則度為0的結(jié)

9、點(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、某二叉樹結(jié)點(diǎn)的中序序列為ABCDEFG，后序序列為BDCAFGE，則其左子樹中結(jié)點(diǎn)數(shù)目為：( C )A）3 B）2 C）4 D）5后序最后一個(gè)為根節(jié)點(diǎn)49、在數(shù)據(jù)結(jié)構(gòu)中假定在一棵二叉樹中，度為2的結(jié)點(diǎn)數(shù)為15個(gè)，度為1的結(jié)點(diǎn)數(shù)為32個(gè)，則葉子結(jié)點(diǎn)數(shù)為（ B ）個(gè)。A）15 B）16 C）17 D）47每個(gè)分枝下面都有一個(gè)結(jié)點(diǎn)，所以總結(jié)點(diǎn)數(shù)N=2*15+1*32+0*葉子數(shù)+1(根節(jié)點(diǎn)）=63二叉樹中

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

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

12、述方法對節(jié)點(diǎn)進(jìn)行編號，如果編號為i(inext = NULL B）p = NULL C）p-next =head D）p = head68、設(shè)無向圖的鄰接鏈表如圖所示，則該圖的邊的數(shù)目是（B）A）4 B）5 C）10 D）20V2V1V4V369、下面的算法中（ A ）是用來構(gòu)造最小生成樹的算法。A）普里姆（Prim）算法B）迪杰斯特拉（Dijkstra）算法C）弗洛伊德（Floyd）算法 D）拓?fù)渑判駼: 是從一個(gè)頂點(diǎn)到其余各頂點(diǎn)的最短路徑算法，解決的是有向圖中最短路徑問題。C: 是一種用于尋找給定的加權(quán)圖中多源點(diǎn)之間最短路徑的算法。D: 對一個(gè)有向無環(huán)圖G進(jìn)行拓?fù)渑判?，是將G中所有頂點(diǎn)排成一個(gè)線性序列，使得圖中任意一對頂點(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,E B）B,C,D,E,A C）E,A,B,C,D D）E,D,C,B,A71、若有序表的關(guān)鍵字序列為（b,c,d,e,f,g,q