南開19春學(xué)期（1709、1803、1809、1903）《數(shù)據(jù)結(jié)構(gòu)》在線作業(yè)1答案

1、19春學(xué)期（1709、1803、1809、1903）數(shù)據(jù)結(jié)構(gòu)在線作業(yè)-0003試卷總分:100 得分:0一、 單選題 (共 30 道試題,共 60 分)1.堆是一種()排序。A.插入B.選擇C.交換D.歸并正確答案:B2.已知圖的鄰接矩陣，根據(jù)算法，則從頂點(diǎn)0出發(fā)，按深度優(yōu)先遍歷的結(jié)點(diǎn)序列是（ ）A.0 2 4 3 1 5 6B.0 1 3 5 6 4 2C.0 4 2 3 1 6 5D.0 1 3 4 2 5 6正確答案:D3.折半搜索與二叉搜索樹的時(shí)間性能()A.相同B.完全不同C.有時(shí)不相同D.數(shù)量級(jí)都是O（log2n）正確答案:C4.任何一個(gè)無向連通圖的最小生成樹()A.只有一棵B.一

2、棵或多棵C.一定有多棵D.可能不存在正確答案:A5.快速排序在下列哪種情況下最易發(fā)揮其長處()A.被排序的數(shù)據(jù)中含有多個(gè)相同排序碼B.被排序的數(shù)據(jù)已基本有序C.被排序的數(shù)據(jù)完全無序D.被排序的數(shù)據(jù)中的最大值和最小值相差懸殊正確答案:C6.線性表在（）情況下適用于使用鏈?zhǔn)浇Y(jié)構(gòu)實(shí)現(xiàn)。A.需經(jīng)常修改中的結(jié)點(diǎn)值B.需不斷對進(jìn)行刪除插入C.中含有大量的結(jié)點(diǎn)D.中結(jié)點(diǎn)結(jié)構(gòu)復(fù)雜正確答案:B7.具有n(n>0)個(gè)結(jié)點(diǎn)的完全二叉樹的深度為（ ）A.B.C.D.正確答案:C8.有8個(gè)結(jié)點(diǎn)的無向連通圖最少有（）條邊A.5B.6C.7D.8正確答案:C9.下列關(guān)鍵字序列中，()是堆A.16,72,31,23,9

3、4,53B.94,23,31,72,16,53C.16,53,23,94，31,72D.16,23,53,31,94,72正確答案:D10.把一棵樹轉(zhuǎn)換為二叉樹后，這棵二叉樹的形態(tài)是（）A.唯一的B.有多種C.有多種，但根結(jié)點(diǎn)都沒有左孩子D.有多種，但根結(jié)點(diǎn)都沒有右孩子正確答案:A11.引入二叉線索樹的目的是（ ）A.加快查找結(jié)點(diǎn)的前驅(qū)或后繼的速度B.為了能在二叉樹中方便的進(jìn)行插入與刪除C.為了能方便的找到雙親D.使二叉樹的遍歷結(jié)果唯一正確答案:A12.已知一棵二叉樹的前序遍歷結(jié)果為ABCDEF,中序遍歷結(jié)果為CBAEDF,則后序遍歷的結(jié)果為()A.CBEFDAB.FEDCBAC.CBEDFA

4、D.不定正確答案:A13.向一個(gè)有127個(gè)元素的順序表中插入一個(gè)新元素并保持原來順序不變，平均要移動(dòng)（）個(gè)元素A.8B.63.5C.63D.7正確答案:B14.深度優(yōu)先遍歷類似于二叉樹的()A.先序遍歷B.中序遍歷C.后序遍歷D.層次遍歷正確答案:A15.二叉樹是非線性數(shù)據(jù)結(jié)構(gòu)，所以（）A.它不能用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)B.它不能用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)存儲(chǔ)C.順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)都能存儲(chǔ)D.順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)都不能使用正確答案:C16.判定一個(gè)棧ST（最多元素為m0）為空的條件是（）A.ST->top<>0B.ST->top=0C.ST->top<>m

5、0D.ST->top=m0正確答案:B17.判定一個(gè)隊(duì)列QU（最多元素為m0）為滿隊(duì)列的條件是（）A.QU->rear QU->front = = m0B.QU->rear QU->front 1= = m0C.QU->front = = QU->rearD.QU->front = = QU->rear+1正確答案:A18.對有n個(gè)記錄的表作快速排序，在最壞情況下，算法的時(shí)間復(fù)雜度是()A.O(n)B.O(n2)C.O(nlog2n)D.O(n3)正確答案:B19.線性表若采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí)，要求內(nèi)存中可用存儲(chǔ)單元的地址（）A.必須是連續(xù)的

6、B.部分地址必須是連續(xù)的C.一定是不連續(xù)的D.連續(xù)或不連續(xù)都可以正確答案:D20.串是一種特殊的線性表，其特殊性體現(xiàn)在（）A.可以順序存儲(chǔ)B.數(shù)據(jù)元素是一個(gè)字符C.可以鏈?zhǔn)酱鎯?chǔ)D.數(shù)據(jù)元素可以是多個(gè)字符正確答案:B21.用鄰接表表示圖進(jìn)行深度優(yōu)先遍歷時(shí)，通常是采用()來實(shí)現(xiàn)算法的A.棧B.隊(duì)列C.樹D.圖正確答案:A22.廣度優(yōu)先遍歷類似于二叉樹的()A.先序遍歷B.中序遍歷C.后序遍歷D.層次遍歷正確答案:D23.在表長為的鏈表中進(jìn)行線性查找，它的平均查找長度為（ ）A.B.（）C.D.正確答案:B24.設(shè)F是一個(gè)森林，B是由F變換得的二叉樹。若F中有n個(gè)非終端結(jié)點(diǎn)，則B中右指針域?yàn)榭盏慕Y(jié)點(diǎn)

7、有()個(gè)A.n-1B.nC.n+1D.n+2正確答案:C25.將5個(gè)不同的數(shù)據(jù)進(jìn)行排序，至多需要比較()次A.8B.9C.10D.25正確答案:C26.棧中元素的進(jìn)出原則是（）A.先進(jìn)先出B.后進(jìn)先出C.棧空則進(jìn)D.棧滿則出正確答案:B27. 設(shè)a1、a2、a3為3個(gè)結(jié)點(diǎn)，整數(shù)P0，3，4代表地址，則如下的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)稱為（）A.循環(huán)鏈表B.單鏈表C.雙向循環(huán)鏈表D.雙向鏈表正確答案:B28.不含任何結(jié)點(diǎn)的空樹（）A.是一棵樹B.是一棵二叉樹C.是一棵樹也是一棵二叉樹D.既不是樹也不是二叉樹正確答案:C29.已知圖的鄰接表如下所示，根據(jù)算法，則從頂點(diǎn)0出發(fā)按深度優(yōu)先遍歷的結(jié)點(diǎn)序列是（）A.0

8、1 3 2B.0 2 3 1C.0 3 2 1D.0 1 2 3正確答案:D30.已知圖的鄰接表如下所示，根據(jù)算法，則從頂點(diǎn)0出發(fā)按廣度優(yōu)先遍歷的結(jié)點(diǎn)序列是（）A.0 3 2 1B.0 1 2 3C.0 1 3 2D.0 3 1 2正確答案:A二、 判斷題 (共 20 道試題,共 40 分)1.棧和鏈表是兩種不同的數(shù)據(jù)結(jié)構(gòu)。A.錯(cuò)誤B.正確正確答案:A2.棧和隊(duì)列的存儲(chǔ)方式既可是順序方式，也可是鏈接方式。A.錯(cuò)誤B.正確正確答案:B3.棧是一種對所有插入、刪除操作限于在表的一端進(jìn)行的線性表，是一種后進(jìn)先出型結(jié)構(gòu)。A.錯(cuò)誤B.正確正確答案:B4.具有12個(gè)結(jié)點(diǎn)的完全二叉樹有5個(gè)度為2的結(jié)點(diǎn)。A.

9、錯(cuò)誤B.正確正確答案:B5.線性表在物理存儲(chǔ)空間中也一定是連續(xù)的。A.錯(cuò)誤B.正確正確答案:A6.二叉樹中每個(gè)結(jié)點(diǎn)的兩棵子樹的高度差等于1。A.錯(cuò)誤B.正確正確答案:A7.棧和隊(duì)列是一種非線性數(shù)據(jù)結(jié)構(gòu)。A.錯(cuò)誤B.正確正確答案:A8.順序表結(jié)構(gòu)適宜于進(jìn)行順序存取，而鏈表適宜于進(jìn)行隨機(jī)存取。A.錯(cuò)誤B.正確正確答案:A9.一個(gè)棧的輸入序列是12345，則棧的輸出序列不可能是12345。A.錯(cuò)誤B.正確正確答案:A10.鏈表的每個(gè)結(jié)點(diǎn)中都恰好包含一個(gè)指針。A.錯(cuò)誤B.正確正確答案:A11.二叉樹中所有結(jié)點(diǎn)個(gè)數(shù)是2k-1-1，其中k是樹的深度。A.錯(cuò)誤B.正確正確答案:A12.用二叉鏈表法（link-rlink）存儲(chǔ)包含n個(gè)結(jié)點(diǎn)的二叉樹，結(jié)點(diǎn)的2n個(gè)指針區(qū)域中有n+1個(gè)為空指針。A.錯(cuò)誤B.正確正確答案:B13.線性表在順序存儲(chǔ)時(shí)，邏輯上相鄰的元素未必在存儲(chǔ)的物理位置次序上相鄰。A.錯(cuò)誤B.正確正確答案:A14.兩個(gè)棧共享一片連續(xù)內(nèi)存空間時(shí)，為提高內(nèi)存利用率，減少溢出機(jī)會(huì)，應(yīng)把兩個(gè)棧的棧底分別設(shè)在這片內(nèi)存空間的兩端。A.錯(cuò)誤B.正確正確答案:B15.二叉樹中每個(gè)結(jié)點(diǎn)有兩棵非空子樹或有兩棵空子樹。A.錯(cuò)誤B.正確正確答案:A16.線性表的邏輯順序與存儲(chǔ)順序總是一致的。A.錯(cuò)誤B.正確正確答案:A17.隊(duì)是一種插入與刪除操作分別在表的兩端進(jìn)行的線性表，是一種先進(jìn)后出型結(jié)構(gòu)