四川大學(xué)《數(shù)據(jù)結(jié)構(gòu)2264》21秋在線作業(yè)1答卷

1、數(shù)據(jù)結(jié)構(gòu)226421秋在線作業(yè)1-00001試卷總分:100 得分:100一、單選題 (共 25 道試題,共 50 分)對(duì)線性表進(jìn)行二分法查找，其前提條件是（ ）。線性表以鏈接方式存儲(chǔ)，并且按關(guān)鍵碼值排好序線性表以順序方式存儲(chǔ)，并且按關(guān)鍵碼值的檢索頻率排好序線性表以順序方式存儲(chǔ)，并且按關(guān)鍵碼值排好序線性表以鏈接方式存儲(chǔ)，并且按關(guān)鍵碼值的檢索頻率排好序答案:C2.對(duì)一棵有100個(gè)結(jié)點(diǎn)的完全二叉樹按層編號(hào)，根結(jié)點(diǎn)編號(hào)為1，則編號(hào)為49的結(jié)點(diǎn)的父結(jié)點(diǎn)的編號(hào)為（ ）。2459899答案:A3.樹最適合用來表示（ ）。有序數(shù)據(jù)元素?zé)o序數(shù)據(jù)元素元素之間具有分支層次關(guān)系的數(shù)據(jù)元素之間無聯(lián)系的數(shù)據(jù)答案:C4.

2、設(shè)有6個(gè)結(jié)點(diǎn)的無向圖，該圖至少應(yīng)有（ ）條邊才能確保是一個(gè)連通圖。5678答案:A5.若用鄰接矩陣表示一個(gè)有向圖，則其中每一列包含的1的個(gè)數(shù)為（ ）。圖中每個(gè)頂點(diǎn)的入度圖中每個(gè)頂點(diǎn)的出度圖中每個(gè)頂點(diǎn)的度圖中連通分量的數(shù)目答案:A6.對(duì)于關(guān)鍵字序列（ ）進(jìn)行散列存儲(chǔ)時(shí)，若選用H（ ）=K%7作為散列函數(shù)，則散列地址為0的元素有（ ）個(gè)。1234答案:D7.對(duì)關(guān)鍵字序列（ ）進(jìn)行增量為3的一趟希爾排序的結(jié)果為（ ）。(19, 23, 56, 34, 78, 67, 88, 92)(23, 56, 78, 66, 88, 92, 19, 34)(19, 23, 34, 56, 67, 78, 88,

3、 92)(19, 23, 67, 56, 34, 78, 92, 88)答案:D8.若有18個(gè)元素的有序表存放在一維數(shù)組A19中，第一個(gè)元素放A1中，現(xiàn)進(jìn)行二分查找，則查找A3的比較序列的下標(biāo)依次為（ ）。1，2，39，5，2，39，5，39，4，2，3答案:D9.以下數(shù)據(jù)結(jié)構(gòu)中哪一個(gè)是非線性結(jié)構(gòu)？（ ）隊(duì)列棧線性表二叉樹答案:D10.設(shè)森林F對(duì)應(yīng)的二叉樹為B，它有m個(gè)結(jié)點(diǎn)，B的根為p，p的右子樹上的結(jié)點(diǎn)個(gè)數(shù)為n，森林F中第一棵樹的結(jié)點(diǎn)個(gè)數(shù)是（ ）。m-n-1n+1m-n+1m-n答案:D11.二維數(shù)組A89按行優(yōu)先順序存儲(chǔ)，若數(shù)組元素A23的存儲(chǔ)地址為1087，A47的存儲(chǔ)地址為1153，則

4、數(shù)組元素A67的存儲(chǔ)地址為（ ）。1207120912111213答案:A12.如表r有100000個(gè)元素，前99999個(gè)元素遞增有序，則采用（ ）方法比較次數(shù)較少。直接插入排序快速排序歸并排序選擇排序答案:A13.設(shè)Huffman樹的葉子結(jié)點(diǎn)數(shù)為m，則結(jié)點(diǎn)總數(shù)為（ ）。2m2m-12m+1m+1答案:B14.帶有頭結(jié)點(diǎn)的單循環(huán)鏈表的頭指針為head，則該鏈表為空的判定條件是（ ）。head= =NULhead-next= =NULLhead!=NULLhead-next= =head答案:D15.中綴表達(dá)式2+X*（ ）的后綴形式是（ ）。3 Y X 2 + * +Y 3 + X * 2 +

5、2 X Y 3 * + +2 X Y 3 + * +答案:D16.k層（ ）二叉樹的結(jié)點(diǎn)總數(shù)最多為（ ）。2k-12K+12K-12k-1答案:A17.對(duì)線性表，在下列哪種情況下應(yīng)當(dāng)采用鏈表表示？（ ）經(jīng)常需要隨機(jī)地存取元素經(jīng)常需要進(jìn)行插入和刪除操作表中元素需要占據(jù)一片連續(xù)的存儲(chǔ)空間表中元素的個(gè)數(shù)不變答案:B18.由權(quán)值分別為3,8,6,2的葉子生成一棵哈夫曼樹，它的帶權(quán)路徑長(zhǎng)度為（ ）。11351953答案:B19.在數(shù)據(jù)結(jié)構(gòu)中，數(shù)據(jù)元素可由（ ）。實(shí)體域數(shù)據(jù)項(xiàng)字段答案:C20.數(shù)據(jù)的基本單位是（ ）。數(shù)據(jù)項(xiàng)數(shù)據(jù)類型數(shù)據(jù)元素?cái)?shù)據(jù)變量答案:A21.AOV網(wǎng)是一種（ ）。有向圖無向圖無向無環(huán)圖有

6、向無環(huán)圖答案:D22.含有10個(gè)結(jié)點(diǎn)的二叉樹中，度為0的結(jié)點(diǎn)數(shù)為4，則度為2的點(diǎn)數(shù)為（ ）。3456答案:A23.從二叉搜索樹中查找一個(gè)元素時(shí)，其時(shí)間復(fù)雜度大致為（ ）。O(n)O(1)O(log2n)O(n2)答案:C24.下列關(guān)于數(shù)據(jù)結(jié)構(gòu)的敘述中，正確的是（ ）。數(shù)組是不同類型值的集合遞歸算法的程序結(jié)構(gòu)比迭代算法的程序結(jié)構(gòu)更為精煉樹是一種線性結(jié)構(gòu)用一維數(shù)組存儲(chǔ)一棵完全二叉樹是有效的存儲(chǔ)方法答案:D25.若有序表為（ ），則在二分查找關(guān)鍵字b的過程中，先后進(jìn)行比較的關(guān)鍵字依次為（ ）。f,c,bf,d,bg,c,bg,d,b答案:A二、多選題 (共 4 道試題,共 20 分)26.以下哪些是

7、隊(duì)列的基本運(yùn)算？（ ）在隊(duì)列第i個(gè)元素之后插入一個(gè)元素從隊(duì)頭刪除一個(gè)元素判斷一個(gè)隊(duì)列是否為空讀取隊(duì)頭元素的值將隊(duì)列中的元素排序答案:BCD27.對(duì)一個(gè)算法的評(píng)價(jià)，主要包括如下（ ）方面的內(nèi)容。健壯性和可讀性并行性正確性時(shí)空復(fù)雜度界面友好性答案:ACD28.棧和隊(duì)列的共同特點(diǎn)是（ ）。只允許在端點(diǎn)處插入和刪除元素都是先進(jìn)后出都是先進(jìn)先出沒有共同點(diǎn)都可以采用順序存儲(chǔ)方式和鏈?zhǔn)酱鎯?chǔ)方式答案:AE29.若進(jìn)棧序列為1，2，3，4，5，6，且進(jìn)棧和出?？梢源┎暹M(jìn)行，則不可能出現(xiàn)的出棧序列為（ ）。3，2，6，1，4，53，4，2，1，6，51，2，5，3，4，65，6，4，2，3，16，5，4，3，2，

8、1答案:ACD三、判斷題 (共 15 道試題,共 30 分)30.在線性鏈表中刪除某個(gè)結(jié)點(diǎn)時(shí)，只需將被刪結(jié)點(diǎn)釋放。答案:錯(cuò)誤31.對(duì)任何用頂點(diǎn)表示活動(dòng)的網(wǎng)絡(luò)（ ）進(jìn)行拓?fù)渑判虻慕Y(jié)果都是唯一的。答案:錯(cuò)誤32.進(jìn)行折半搜索的表必須是順序存儲(chǔ)的有序表。答案:正確33.一個(gè)廣義表（ ）,（ ）,c),（ ）) 的表尾是（ ）,c),（ ）)。答案:錯(cuò)誤34.鄰接表只能用于有向圖的存儲(chǔ)，鄰接矩陣對(duì)于有向圖和無向圖的存儲(chǔ)都適用。答案:錯(cuò)誤35.若一棵二叉樹的任一非葉子結(jié)點(diǎn)的度為2，則該二叉樹為滿二叉樹。答案:錯(cuò)誤36.為度量一個(gè)搜索算法的效率，需要在時(shí)間和空間兩個(gè)方面進(jìn)行分析。答案:正確37.二維數(shù)組是數(shù)組元素為一維數(shù)組的線性表，因此二維數(shù)組元素之間是線性結(jié)構(gòu)。答案:錯(cuò)誤38.在用循環(huán)單鏈表表示的鏈?zhǔn)疥?duì)列中，可以不設(shè)隊(duì)頭指針，僅在鏈尾設(shè)置隊(duì)尾指針。答案:正確39.數(shù)據(jù)的邏輯結(jié)構(gòu)是指各數(shù)據(jù)元素之間的邏輯關(guān)系，是用戶根據(jù)應(yīng)用需要建立的。答案:正確40.線性表的長(zhǎng)度是線性表所占用的存儲(chǔ)空間的大小。答案:錯(cuò)誤