[北京語言大學(xué)]20秋《數(shù)據(jù)結(jié)構(gòu)》作業(yè)4
試卷總分:100    得分:100
第1題,下列四種排序中___的空間復(fù)雜度最大。
A、插入排序
B、冒泡排序
C、堆排序
D、歸并排序
正確答案:


第2題,
A、A
B、B
C、C
D、D
正確答案:


第3題,順序查找法適合于存儲結(jié)構(gòu)為___的線性表。
A、散列存儲
B、順序存儲或鏈?zhǔn)酱鎯?br/>C、壓縮存儲
D、索引存儲
正確答案:


第4題,由權(quán)值分別為11,8,6,2,5的葉子結(jié)點生成一棵哈夫曼樹，它的帶權(quán)路徑長度為___。
A、24
B、71
C、48
D、53
正確答案:


答案來源：（www.）,
A、A
B、B
C、C
D、D
正確答案:


第6題,設(shè)一組初始記錄關(guān)鍵字序列為（345,253,674,924,627），則用基數(shù)排序需要進(jìn)行___趟的分配和回收才能使得初始關(guān)鍵字序列變成有序序列。
A、3
B、4
C、5
D、8
正確答案:


第7題,如果最常用的操作是取第i個結(jié)點及其前驅(qū)，則采用___存儲方式最節(jié)省時間。
A、單鏈表
B、雙鏈表
C、單循環(huán)鏈表
D、順序表
正確答案:


第8題,設(shè)哈夫曼樹中的葉子結(jié)點總數(shù)為m，若用二叉鏈表作為存儲結(jié)構(gòu)，則該哈夫曼樹中總共有___個空指針域。
A、2m-1
B、2m
C、2m+1
D、4m
正確答案:


第9題,
A、A
B、B
C、C
D、D
正確答案:


答案來源：（www.）,若某表最常用的操作是在最后一個結(jié)點之后插入一個結(jié)點或刪除最后一個結(jié)點，則采用___存儲方式最節(jié)省運(yùn)算時間。
A、單鏈表
B、給出表頭指針的單循環(huán)鏈表
C、雙鏈表
D、帶頭結(jié)點的雙循環(huán)鏈表
正確答案:


第11題,設(shè)某棵二叉樹中有2000個結(jié)點，則該二叉樹的最小高度為___。
A、9
B、10
C、11
D、12
正確答案:


答案來源：（www.）,若有18個元素的有序表存放在一堆數(shù)組A[19]中，第一個元素放A[1]中，現(xiàn)進(jìn)行二分查找，則查找A[3]的比較序列的下標(biāo)依次為___。
A、1,2,3
B、9,5,2,3
C、9,5,3
D、9,4,2,3
正確答案:


第13題,若已知一個棧序列是1,2,3,...,n，其輸出序列為p1,p2,p3,...,pn，若p1=n，則pi為___。
A、i
B、n-i
C、n-i+1
D、不確定
正確答案:


第14題,下述哪一條是順序存儲結(jié)構(gòu)的優(yōu)點___。
A、插入運(yùn)算方便
B、可方便地用于各種邏輯結(jié)構(gòu)的存儲表示
C、存儲密度大
D、刪除運(yùn)算方便
正確答案:


答案來源：（www.）,線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)是一種___。
A、隨機(jī)存取的存儲結(jié)構(gòu)
B、順序存取的存儲結(jié)構(gòu)
C、索引存取的存儲結(jié)構(gòu)
D、Hash存取的存儲結(jié)構(gòu)
正確答案:


第16題,
A、A
B、B
C、C
D、D
正確答案:


第17題,
A、a
B、b
C、c
D、d
正確答案:


第18題,在一個長度為n的順序線性表中順序查找值為x的元素時，查找成功時的平均查找長度（即x與元素的平均比較次數(shù)，假定查找每個元素的概率都相等）為___。
A、n
B、n/2
C、(n+1)/2
D、(n-1)/2
正確答案:


第19題,線性表是具有n個___的有限序列。
A、字符
B、數(shù)據(jù)元素
C、數(shù)據(jù)項
D、表元素
正確答案:


答案來源：（www.）,
A、A
B、B
C、C
D、D
正確答案: