《數(shù)據(jù)結(jié)構(gòu)》習(xí)題及答案

1、一、單項(xiàng)選擇題一、單項(xiàng)選擇題1、一棵二叉樹有10個葉結(jié)點(diǎn)，僅有1個孩子的結(jié)點(diǎn)有5個，則此二叉樹共有（）個結(jié)點(diǎn)。A）23B）24C）25D）26答案（）4線性表是（）。A一個有限序列，可以為空B一個有限序列，不可以為空C一個無限序列，可以為空D一個無限序列，不可以為空答案（A）5設(shè)有一個棧，元素的進(jìn)棧次序?yàn)锳，B，C，D，E，下列（）是不可能的出棧序列。AA，B，C，D，EBB，C，D，E，ACE，A，B，C，DDE，D，C，B，A答案（

2、C）7G=（V，E）是含n個結(jié)點(diǎn)的帶權(quán)無向圖，T=（V，TE）是它的最小生成樹，其中TE是（）A）由E的任意n1條邊組成B）有E中權(quán)值最小的n1條邊組成C）由E中n1條不構(gòu)成回路的邊組成D）所有生成樹中權(quán)值權(quán)值之和最小的n1條邊組成答案（D）9用順序存儲的方法將完全二叉樹中的所有結(jié)點(diǎn)逐層存放在數(shù)組R[1...n]中，結(jié)點(diǎn)R[i]若有左子女，則左子女是結(jié)點(diǎn)（）。AR[2i1]BR[2i]CR[i2]DR[2i1]答案（B）10由帶權(quán)為9，

3、2，5，7的四個葉了結(jié)點(diǎn)構(gòu)造一棵哈夫曼樹，該樹的帶權(quán)路徑長度為（）。A23B37C46D442、若進(jìn)棧序列為3，5，7，9，進(jìn)棧過程中可以出棧，則不可能的一個出棧次序是（）。(a)7539(b)9753(c)7593(d)9573答案（）3、一個有n個頂點(diǎn)的無向完全圖有（）條邊。A）n(n1)B）n(n1)2C）n1D）n答案（）4、單循環(huán)鏈表中L為頭指針，則p所指結(jié)點(diǎn)為尾結(jié)點(diǎn)的條件為（）A）pnext=NULLB）p=NULLC）pn

4、ext=LD）p=L答案（）5、循環(huán)隊(duì)列滿的條件是（）A）sq.rear=sq.frontB）sq.rear=sq.front1C）sq.rear1=sq.frontD）((sq.rear1)%maxsize)==sq.front答案（）棧空的條件是（）；如果棧不為空，則退棧操作為：p=ls；()；free(p)。5、設(shè)有二維數(shù)組intm[10[20]每個元素（整數(shù)）占2個存儲單元，數(shù)組的起始地址為2000，元素m[5][10]的存儲位

5、置為（）。7、無向圖中的極大連通子圖稱為該圖的（）。8、設(shè)有向圖G有n個頂點(diǎn)v1v2v3…vn，它的鄰接矩陣為A，頂點(diǎn)vi的入度ID（vi）為（）；頂點(diǎn)vi的出度OD（vi）為()。10、3個結(jié)點(diǎn)可構(gòu)成（）棵不同形態(tài)的樹，（）棵不同形態(tài)的二叉樹。2設(shè)有滿足二分查找法要求的查找表R（鍵值按遞增順序排列），查找區(qū)間為[l，h]要查找的鍵值為K，首先被比較元素的位置為=(lh)DIV2，若R[].keyK，則h改為（1）。3設(shè)有向圖G有n個頂

6、點(diǎn)v1v2v3…vn，它的鄰接矩陣為A，頂點(diǎn)vi的入度ID（vi）為（Vi所對應(yīng)列元素的和）；頂點(diǎn)vi的出度OD（vi）為(Vi所對應(yīng)行元素的和).5對100個記錄進(jìn)行折半查找，最多比較次數(shù)和最少比較次數(shù)分別是（7）和（1）。7無向圖中的極大連通子圖稱為該圖的（連通分量）。8二叉排序樹的平均查找長度與樹的形態(tài)有關(guān)，在最壞情況下，二叉排序樹的形態(tài)是（單支鏈）。103個結(jié)點(diǎn)可構(gòu)成（2）棵不同形態(tài)的樹，（5）棵不同形態(tài)的二叉樹。1在有m個葉子

7、的赫夫曼樹中，其總結(jié)點(diǎn)個數(shù)為（）。2在僅有尾指針R且?guī)в蓄^結(jié)點(diǎn)的單循環(huán)鏈表中，指針P所指結(jié)點(diǎn)是第一個元素結(jié)點(diǎn)的條件是P=（）。4無向圖中的極大連通子圖稱為該圖的（）。5在帶有頭結(jié)點(diǎn)的單循環(huán)鏈表L中，指針P所指結(jié)點(diǎn)為尾結(jié)點(diǎn)的條件是（）。6設(shè)有向圖G有n個頂點(diǎn)v1v2v3…vn，它的鄰接矩陣為A，頂點(diǎn)vi的入度ID（vi）為（）；頂點(diǎn)vi的出度OD（vi）為().7如果含n個頂點(diǎn)的圖是一個環(huán)，則它有（）棵生成樹。10循環(huán)隊(duì)列的隊(duì)空條件是（）