數(shù)據(jù)結(jié)構(gòu)（本）期末綜合練習(xí)

1、數(shù)據(jù)結(jié)構(gòu)（本）試題A第頁（共7頁）1數(shù)據(jù)結(jié)構(gòu)（本）期末綜合練習(xí)數(shù)據(jù)結(jié)構(gòu)（本）期末綜合練習(xí)2011年12月期末綜合練習(xí)一期末綜合練習(xí)一一、單項(xiàng)選擇題一、單項(xiàng)選擇題1數(shù)據(jù)的物理結(jié)構(gòu)（）。A與數(shù)據(jù)的邏輯結(jié)構(gòu)無關(guān)B僅僅包括數(shù)據(jù)元素的表示C只包括數(shù)據(jù)元素間關(guān)系的表示D包括數(shù)據(jù)元素的表示和關(guān)系的表示2深度為5的完全二叉樹共有20個(gè)結(jié)點(diǎn)，則第5層上有（）個(gè)結(jié)點(diǎn)(根所在結(jié)點(diǎn)為第一層)。A3B8C5D63從n個(gè)數(shù)中選取最大元素（）。A基本操作是數(shù)據(jù)元素間

2、的交換B算法的時(shí)間復(fù)雜度是O(n2)C算法的時(shí)間復(fù)雜度是O(n)D需要進(jìn)行(n1)次數(shù)據(jù)元素間的比較4已知一個(gè)圖的邊數(shù)為m，則該圖的所有頂點(diǎn)的度數(shù)之和為（）。A2mBmC2m1Dm25線性表的順序結(jié)構(gòu)中，（）。A邏輯上相鄰的元素在物理位置上不一定相鄰B數(shù)據(jù)元素是不能隨機(jī)訪問的C邏輯上相鄰的元素在物理位置上也相鄰D進(jìn)行數(shù)據(jù)元素的插入、刪除效率較高6數(shù)據(jù)結(jié)構(gòu)中，與所使用的計(jì)算機(jī)無關(guān)的是數(shù)據(jù)的（）結(jié)構(gòu)。A物理B存儲(chǔ)C邏輯與物理D邏輯7帶頭結(jié)點(diǎn)

3、的單向鏈表為空的判斷條件是（）（設(shè)頭指針為head）。Ahead==NULLBheadnext==NULLCheadnext==headDhead!=NULL8鏈表所具備的特點(diǎn)是（）。A可以隨機(jī)訪問任一結(jié)點(diǎn)B占用連續(xù)的存儲(chǔ)空間C插入刪除不需要移動(dòng)元素結(jié)點(diǎn)D可以通過下標(biāo)對鏈表進(jìn)行直接訪問9線性結(jié)構(gòu)中數(shù)據(jù)元素的位置之間存在（）的關(guān)系。A一對一B一對多C多對多D每一個(gè)元素都有一個(gè)直接前驅(qū)和一個(gè)直接后繼10線性表只要以（）方式存儲(chǔ)就能進(jìn)行折半查

4、找。A鏈接B順序C關(guān)鍵字有序的順序D二叉樹11設(shè)順序存儲(chǔ)的線性表長度為n，要?jiǎng)h除第i個(gè)元素，按課本的算法，當(dāng)i=（）時(shí)，移動(dòng)元素的次數(shù)為3A3Bn2Cn3D412散列查找的原理是（）。A在待查記錄的關(guān)鍵字值與該記錄的存儲(chǔ)位置之間建立確定的對應(yīng)關(guān)系B按待查記錄的關(guān)鍵字有序的順序方式存儲(chǔ)C按關(guān)鍵字值的比較進(jìn)行查找D基于二分查找的方法數(shù)據(jù)結(jié)構(gòu)（本）試題A第頁（共7頁）3圖123空串的長度為（）。A0B1C2D324元素2，4，6，8按順序依次

5、進(jìn)棧，則該棧的不可能輸出序列是（）（進(jìn)棧出?？梢越惶孢M(jìn)行）。A8，6，4，2B2，4，6，8C4，2，8，6D8，6，2，425串函數(shù)StrCmp(“abA””aba”)的值為（）。A1B0C“abAaba”D126排序方法中，從未排序序列中挑選元素，并將其依次放入已排序序列（初始為空）的一端的方法，稱為（）排序。A歸并B插入C選擇D快速27設(shè)有一個(gè)10階的對稱矩陣A，采用壓縮存儲(chǔ)方式將其下三角部分以行序?yàn)橹餍虼鎯?chǔ)到一維數(shù)組b中。（矩陣

6、A的第一個(gè)元素為a11，數(shù)組b的下標(biāo)從1開始），則矩陣元素a53對應(yīng)一維數(shù)組b的數(shù)組元素是（）。Ab[18]Bb[8]Cb[13]Db[10]28一棵哈夫曼樹總共有23個(gè)結(jié)點(diǎn)，該樹共有（）個(gè)葉結(jié)點(diǎn)（終端結(jié)點(diǎn)）A10B13C11D1229已知如圖2所示的一個(gè)圖，若從頂點(diǎn)a出發(fā)，按深度優(yōu)先搜索法進(jìn)行遍歷，則可能得到的一種頂點(diǎn)序列為（）。AabecdfBacfebdCaebcfdDaedfcbbdfeca圖230隊(duì)列的插入操作在（）進(jìn)行。A隊(duì)

7、頭B隊(duì)尾C隊(duì)頭或隊(duì)尾D在任意指定位置二、填空題二、填空題1通常數(shù)據(jù)的邏輯結(jié)構(gòu)包括集合、線性、____、____四種類型。2一棵二叉樹沒有單分支結(jié)點(diǎn)，有6個(gè)葉結(jié)點(diǎn)，則該樹總共有________個(gè)結(jié)點(diǎn)。3通?？梢园涯吵鞘兄懈鞴徽军c(diǎn)間的線路圖抽象成________結(jié)構(gòu)。4設(shè)一棵完全二叉樹，其最高層上最右邊的葉結(jié)點(diǎn)的編號(hào)為奇數(shù)，該葉節(jié)點(diǎn)的雙親結(jié)點(diǎn)的編號(hào)為10，該完全二叉樹一共有________個(gè)結(jié)點(diǎn)。5設(shè)有一個(gè)單向鏈表，結(jié)點(diǎn)的指針域?yàn)閚ext