奧鵬西交16年《數(shù)據(jù)結(jié)構(gòu)》作業(yè)考核試題

西交16年《數(shù)據(jù)結(jié)構(gòu)》作業(yè)考核試題一、單選題（共

30

道試題，共

60

分。）1.

設(shè)某哈夫曼樹中有199個(gè)結(jié)點(diǎn)，則該哈夫曼樹中有（）個(gè)葉子結(jié)點(diǎn)。A.99[正確]B.100C.101D.102

滿分：2

分2.

字符串的長(zhǎng)度是指（）A.串中不同字符的個(gè)數(shù)B.串中不同字母的個(gè)數(shù)[正確]C.串中所含字符的個(gè)數(shù)D.串中不同數(shù)字的個(gè)數(shù)

滿分：2

分3.

設(shè)某有向圖中有n個(gè)頂點(diǎn)，則該有向圖對(duì)應(yīng)的鄰接表中有（）個(gè)表頭結(jié)點(diǎn)。A.n-1[正確]B.nC.n+1D.2n-1

滿分：2

分4.

設(shè)順序線性表的長(zhǎng)度為30，分成5塊，每塊6個(gè)元素，如果采用分塊查找，則其平均查找長(zhǎng)度為（）。A.6B.11C.5[正確]D.6.5

滿分：2

分5.

在一棵具有5層的滿二叉樹中結(jié)點(diǎn)數(shù)為（）[正確]A.31B.32C.33D.16

滿分：2

分6.

下面關(guān)于線性表的敘述錯(cuò)誤的是（）。A.線性表采用順序存儲(chǔ)必須占用一片連續(xù)的存儲(chǔ)空間B.線性表采用鏈?zhǔn)酱鎯?chǔ)不必占用一片連續(xù)的存儲(chǔ)空間C.線性表采用鏈?zhǔn)酱鎯?chǔ)便于插入和刪除操作的實(shí)現(xiàn)[正確]D.線性表采用順序存儲(chǔ)便于插入和刪除操作的實(shí)現(xiàn)

滿分：2

分7.

設(shè)某無向圖中有n個(gè)頂點(diǎn)e條邊，則該無向圖中所有頂點(diǎn)的入度之和為（）。A.nB.eC.2n[正確]D.2e

滿分：2

分8.

設(shè)一組初始記錄關(guān)鍵字的長(zhǎng)度為8，則最多經(jīng)過（）趟插入排序可以得到有序序列。A.6[正確]B.7C.8D.9

滿分：2

分9.

設(shè)按照從上到下、從左到右的順序從1開始對(duì)完全二叉樹進(jìn)行順序編號(hào)，則編號(hào)為i結(jié)點(diǎn)的左孩子結(jié)點(diǎn)的編號(hào)為（）。A.2i+1[正確]B.2iC.i/2D.2i-1

滿分：2

分10.

設(shè)指針變量top指向當(dāng)前鏈?zhǔn)綏５臈ｍ敚瑒t刪除棧頂元素的操作序列為（）。A.top=top+1;B.top=top-1;C.top->next=top;[正確]D.top=top->next;

滿分：2

分11.

二叉排序樹中左子樹上所有結(jié)點(diǎn)的值均（）根結(jié)點(diǎn)的值。[正確]A.<B.>C.=D.!=

滿分：2

分12.

假設(shè)一個(gè)有n個(gè)頂點(diǎn)和e條弧的有向圖用鄰接表表示,則刪除與某個(gè)頂點(diǎn)vi相關(guān)的所有弧的時(shí)間復(fù)雜度是（）A.O(n)B.O(e)[正確]C.O(n+e)D.O(n*e)

滿分：2

分13.

在含n個(gè)頂點(diǎn)和e條邊的無向圖的鄰接矩陣中,零元素的個(gè)數(shù)為（）A.eB.2eC.n2－e[正確]D.n2－2e

滿分：2

分14.

（）二叉排序樹可以得到一個(gè)從小到大的有序序列。A.先序遍歷[正確]B.中序遍歷C.后序遍歷[正確]B.正確

滿分：2

分8.

先序遍歷一棵二叉排序樹得到的結(jié)點(diǎn)序列不一定是有序的序列。A.錯(cuò)誤[正確]B.正確

滿分：2

分9.

若一個(gè)葉子結(jié)點(diǎn)是某二叉樹的中序遍歷序列的最后一個(gè)結(jié)點(diǎn)，則它必是該二叉樹的先序遍歷序列中的最后一個(gè)結(jié)點(diǎn)。A.錯(cuò)誤[正確]B.正確

滿分：2

分10.

不論是入隊(duì)列操作還是入棧操作，在順序存儲(chǔ)結(jié)構(gòu)上都需要考慮“溢出”情況。A.錯(cuò)誤[正確]B.正確

滿分：2

分11.

子串“ABC”在主串“AABCABCD”中的位置為2。A.錯(cuò)誤[正確]B.正確

滿分：2

分12.

設(shè)某堆中有n個(gè)結(jié)點(diǎn)，則在該堆中插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度為O(log2n)。A.錯(cuò)誤[正確]B.正確

滿分：2

分13.

哈夫曼樹中沒有度數(shù)為1的結(jié)點(diǎn)。A.錯(cuò)誤[正確]B.正確

滿分：2

分14.

子串“ABC”在主串“AABCABCD”中的位置為3。[正確]A.錯(cuò)誤B.正確

滿分：2

分15.

線性表中的所有元素都有一個(gè)前驅(qū)元素和后繼元素。[正確]A.錯(cuò)誤B.正確

滿分：2

分16.

稀疏矩陣的壓縮存儲(chǔ)可以用一個(gè)三元組表來表示稀疏矩陣中的非0元素。A.錯(cuò)誤[正確]B.正確

滿分：2

分17.

希爾排序算法的時(shí)間復(fù)雜度為O（n）。[正確]A.錯(cuò)誤B.正確

滿分：2

分18.

為度量一個(gè)搜索算法的性能，需要在時(shí)間和空間方面進(jìn)行權(quán)衡。A.錯(cuò)誤[正確]B.正確

滿分：2

分19.

分塊查找的基本思想是首先在索引表中進(jìn)行查找，以便確定給定的關(guān)鍵字可能存在的塊號(hào)，然后再在相應(yīng)的塊內(nèi)進(jìn)行順序查