商丘學(xué)院軟件工程專業(yè)大二2017年數(shù)據(jù)結(jié)構(gòu)與算法周考二測(cè)試

1、商丘學(xué)院軟件工程專業(yè)大二 2017 年數(shù)據(jù)結(jié)構(gòu)與算法周考二測(cè)試您的姓名： 填空題 *1、隊(duì)列具有先進(jìn)先出的特性，那么入隊(duì)的 O，P，Q 順序的三個(gè)元素，出隊(duì)順序是（）。 單選題 *A:OA:O，P，Q(正確答案B:O，Q，P C:Q，P，OD:O，Q，P2、循環(huán)隊(duì)列最大容量是 MAX，隊(duì)頭是 front，隊(duì)尾是 rear，采用人為浪費(fèi)一個(gè)單元的形式，則隊(duì)的長(zhǎng)度是（）。 單選題 *A:(rearfront)%MAXA:(rearfront)%MAXB: (rearfront+MAX)%MAX(正確答案) C: rearfront+MAXD:都不對(duì)3、單鏈表中刪除 p 指針指向結(jié)點(diǎn)的后繼(假設(shè)存在

2、)的語(yǔ)句序列正確的是（）。 單選題 *A:p-next=p-next;A:p-next=p-next;B:p-next=p-next-next;(正確答案C:p-next=p;D:p=p-next;4、串的 KMP 算法是由三個(gè)科學(xué)家同時(shí)發(fā)現(xiàn)的，對(duì)原有的算法改進(jìn)點(diǎn)在于（）。單選題 *A:A:指向主串的指針不需要回溯，只模式串滑動(dòng)盡可能遠(yuǎn)的距離后繼續(xù)進(jìn)行模式匹配(正確答案)B:主串的指針要回溯到之前的某個(gè)位置，同時(shí)模式串滑動(dòng)盡可能遠(yuǎn)的距離后繼續(xù)進(jìn)行模式匹配C:某個(gè)字符匹配失敗時(shí)，主串與模式都不需要回溯指針D:時(shí)間復(fù)雜度可提高到 O(n*m),n 和 m 表示主串和模式串的長(zhǎng)度。5、在樹的概念中，

3、樹的某結(jié)點(diǎn)的直接后繼稱為該結(jié)點(diǎn)的（）。 單選題 *A:A:孩子(正確答案) B:雙親C: 子孫D:祖先6、度為 0 的結(jié)點(diǎn)又稱為（）。 單選題 *A:A:葉子(正確答案) B:根結(jié)點(diǎn)C:分支結(jié)點(diǎn)內(nèi)部結(jié)點(diǎn)7、結(jié)點(diǎn)的度是指（）。 單選題 *A:A:結(jié)點(diǎn)掛接的子樹的數(shù)目(正確答案) B:零C:葉子的個(gè)數(shù)無(wú)正確答案8、樹是一種常用的數(shù)據(jù)結(jié)構(gòu)，樹的邏輯結(jié)構(gòu)是（）。 單選題 *A:A:一對(duì)多(正確答案B:一對(duì)一C:二對(duì)一多對(duì)多9、二叉樹如果有根結(jié)點(diǎn)，只能有（）個(gè)。 單選題 *A: A: 一(正確答案) B: 兩C:D:10、滿二叉樹的葉子結(jié)點(diǎn)都在（）。 單選題 *A:A:最后一層(正確答案) B:可以在不

4、同的的層C:沒有葉子結(jié)點(diǎn)D:都不對(duì)11、一顆二叉樹度為 2 的結(jié)點(diǎn)的個(gè)數(shù)是 6，則問度為 0 的結(jié)點(diǎn)的個(gè)數(shù)是（）。 單選題 *A:6A:6B:7(正確答案C:8D:512、當(dāng)二叉樹的結(jié)點(diǎn)個(gè)數(shù) n 是 0 的時(shí)候表示，它是（）。 單選題 *A: A: 滿二叉樹B:空二叉樹(正確答案)C:C:完全二叉樹D:哈夫曼樹13、左子樹、右子樹、根結(jié)點(diǎn)的遍歷順序稱為（）單選題 *A:A:中序遍歷B:先序遍歷C:后序遍歷(正確答案)D:都不對(duì)14、左子樹、根結(jié)點(diǎn)、右子樹的遍歷順序稱為（）單選題 *A:A:中序遍歷(正確答案B:先序遍歷C:后序遍歷D:都不對(duì)15、根結(jié)點(diǎn)、左子樹、右子樹的遍歷順序稱為（）單選題

5、*中序遍歷B:先序遍歷(正確答案C:后序遍歷D:都不對(duì)16、對(duì)于二叉樹，每個(gè)結(jié)點(diǎn)都訪問，且只訪問一次是（）的概念。 單選題 *A:A:遍歷(正確答案B:訪問C:探測(cè)回溯A: E F D C B AB:D F E C B 正確答案C:F E D C BAD:E D F C BA17A: E F D C B AB:D F E C B 正確答案C:F E D C BAD:E D F C BA18、給定一組數(shù)據(jù)6，8，7，10，3，12以它構(gòu)造一棵赫夫曼樹，則樹深度為()， 帶權(quán)路徑長(zhǎng)度 WPL 的值是（）。 單選題 *A:5 96A:5 96B:6 96C:4116(正確答案D:4 9819、加設(shè)樹

6、 T 的度為 4，其度為 1，2，3 和 4 的結(jié)點(diǎn)個(gè)數(shù)分別是 4，2，2，1 則 T中的葉子數(shù)有（）個(gè)。 單選題 *A: 5A: 5B: 6C:10(正確答案D: 820、有 n 個(gè)終端結(jié)點(diǎn)的哈夫曼樹的結(jié)點(diǎn)總數(shù)為（）。 單選題 *A:2nA:2nB:不確定C:2n+1D:2n-1(正確答案)哈希表采用“再哈希法”處理沖突，則（）單選題 *A: A: 不容易產(chǎn)生“聚集”(正確答案) B: 任然容易產(chǎn)生“聚集”C: 必然產(chǎn)生“聚集”D: 以上說(shuō)法都不對(duì)哈希表的查找是依靠（）單選題*A:A:哈希函數(shù)(正確答案B:逐一比對(duì)C: 折半比較D: 集合14H(key)=key%11,15，38，61，84

7、 共四個(gè)，現(xiàn)要將關(guān)鍵字為 49 的結(jié)點(diǎn)加到表中，用二次探測(cè)再散列法解決沖突，則放入的位置是（）。 單選題 *A: 8A: 8B:9(正確答案C: 5D: 3二叉排序樹的（）單選題 *A: A: 左子樹(正確答案) B: 右子樹C: 左子樹和右子樹D: 都不對(duì)關(guān)于查找的效率問題，下面說(shuō)法中正確的是（）單選題 *A: A: 順序查找一定沒有折半查找快B: B: 順序查找比折半查找快C: 折半查找不一定比順序查找快(正確答案) D: 就平均效率而言，順序查找的效率更高二叉排序樹是一顆特殊的二叉樹，其中序序列是一個(gè)（） *A:A:倒序序列B:升序序列(正確答案C: 亂序序列D: 都不對(duì)折半查找要求是順

8、序存儲(chǔ)且（） *A: A: 記錄有序(正確答案) B: 記錄無(wú)序C: 記錄隨機(jī)排放D: 都不對(duì)14H(key)=key%11,15，38，61，84 共四個(gè)，現(xiàn)要將關(guān)鍵字為 49 的結(jié)點(diǎn)加到表中，用二次探測(cè)再散列法解決沖突，則放入的位置是（）。 單選題 *A: 8A: 8B:9(正確答案C: 5D: 3ABCDEFG，它的中序遍歷序列可能是（）選題 *A: CABDEFGA: CABDEFGB: ABCDEFGB: ABCDEFG(正確答案) C: DACEFBGD: ADCFEG數(shù)據(jù)結(jié)構(gòu)與算法內(nèi)，折半查找的時(shí)間復(fù)雜度是（）單選題 *A: O(1)A: O(1)B: O(log2n)(正確答案

9、) C: O(n*n)D: O(n)以下屬于哈希函數(shù)的構(gòu)造方法的是（）單選題 *A: A: 直接定址法(正確答案) B: 哈希再散列法C: 線性探測(cè)再散列法D:二次探測(cè)再散列法kk中，至少要進(jìn)行多少次探測(cè)？（）單選題*A: k-1 A: k-1 次B: k 次C: k+1 次D: k(k+1)/2 次(正確答案)33、某二叉樹的所有結(jié)點(diǎn)的度不是 0 就是 2，則（）。 *A:A:該二叉樹是滿二叉樹B:該二叉樹不一定是滿二叉樹(正確答案)C:該二叉樹的度為 0 的結(jié)點(diǎn)一定是葉子(正確答案)D: D: 該二叉樹若有 n 層，則最少的結(jié)點(diǎn)數(shù)是 2*n-1(正確答案)34、在下列結(jié)論中，正確的是（）。

10、 *A:A:只有一個(gè)結(jié)點(diǎn)的二叉樹的度為 0(正確答案) B:二叉樹的度小于等于 2(正確答案)C:二叉樹的左右子樹不可任意交換(正確答案)D:深度為 K 的完全二叉樹的結(jié)點(diǎn)個(gè)數(shù)小于或等于深度相同的滿二叉樹(正確答案)35、已知某二叉樹的中序序列是形： A+B*C-D/E，后序序列是為 ABC*+DE/-，則其先序序列不可能是（）。 *A:-A+B*C/DEA:-A+B*C/DE(正確答案) B:-A+B*CD/E(正確答案) C:-+*ABC/DE(正確答案) D: -+A*BC/DE36、二叉樹的中序遍歷序列是 E、B、A、C、F、D，若 A 是根結(jié)點(diǎn)，則 E 結(jié)點(diǎn)不可能在（）。 *A:A:

11、左子樹B: 右子樹(正確答案)C:右子樹的第二層(正確答案) D:右子樹的根節(jié)點(diǎn)(正確答案)37、在樹中，度不為 0 的結(jié)點(diǎn)(根除外)可以稱為（）。 *A:A:葉子B:終端結(jié)點(diǎn)分支結(jié)點(diǎn)(正確答案)內(nèi)部結(jié)點(diǎn)(正確答案)38、下列選項(xiàng)中關(guān)于二叉樹的遍歷和恢復(fù)說(shuō)法正確的是（）。 *A:A:先序序列和中序序列已知，可以恢復(fù)二叉樹(正確答案) B:中序序列和后序序列已知，可以恢復(fù)二叉樹(正確答案) C:先序序列和后序序列已知，可以恢復(fù)二叉樹D:無(wú)正確答案裝填因子的計(jì)算方法是（）*A: 1-(A: 1-(表中未填入記錄的數(shù)目/哈希表的總長(zhǎng)度)(正確答案) B: 表中未填入記錄的數(shù)目/哈希表的總長(zhǎng)度C: (

12、表中未填入的記錄數(shù)-1)/哈希表的總長(zhǎng)度D: 表中填入的記錄數(shù)/哈希表的總長(zhǎng)(正確答案)下面屬于構(gòu)造散列函數(shù)的方法是（）*A:A:直接定址法(正確答案B:數(shù)字分析法(正確答案) C:除留余數(shù)法(正確答案)D:平方取中法(正確答案)靜態(tài)查找表中，對(duì)順序表的查找方式有（）*A:A:順序查找(正確答案B:折半查找(正確答案) C: 分塊查找D:隨機(jī)查找42、以下是 C 語(yǔ)言中的字符串處理函數(shù)的，且?guī)в袃蓚€(gè)參數(shù)的是（）。 *A:strcatA:strcat(正確答案)B:strcpy(正確答案)C:strlenC:strlenD:strcmp(正確答案)43. 關(guān)于二叉排序樹描述有誤的是（）。 *A:

13、 A: 二叉排序的右子樹上結(jié)點(diǎn)的關(guān)鍵字小于左子樹上的結(jié)點(diǎn)的關(guān)鍵字(正確答案) B: 二叉排序的左子樹上結(jié)點(diǎn)的關(guān)鍵字小于右子樹上的結(jié)點(diǎn)的關(guān)鍵字C: 二叉排序的根節(jié)點(diǎn)的關(guān)鍵大于右子樹上結(jié)點(diǎn)的關(guān)鍵字(正確答案)D: 二叉排序的根節(jié)點(diǎn)的關(guān)鍵大于左子樹上結(jié)點(diǎn)的關(guān)鍵字44、由于隊(duì)列是先進(jìn)先出的特性，入隊(duì)的順序是 A、B、C 則出隊(duì)的順序不可能是（）。 *A:AA:A、C、B(正確答案) B:A、B、CC:C、A、正確答案)、A(正確答案)45、各結(jié)點(diǎn)層次的最大值(根結(jié)點(diǎn)算第一層)，這個(gè)概念不是說(shuō)（）的。 *A:A:樹的深度B:樹的高度C:樹的度(正確答案)D:結(jié)點(diǎn)的度(正確答案)46、度為 0 的結(jié)點(diǎn)可以

14、稱為（）。 *A:A:葉子(正確答案)B:終端結(jié)點(diǎn)(正確答案) C:分支結(jié)點(diǎn)D:根結(jié)點(diǎn)47、滿二叉樹的葉子一定只能出現(xiàn)在最后一層。 判斷題 *對(duì)對(duì)(正確答案)錯(cuò)48、非空左斜樹的先序遍歷序列和后序遍歷序列正好相反。 判斷題 *對(duì)對(duì)(正確答案)錯(cuò)49、若二叉樹不空，二叉樹的先序序列中第一個(gè)結(jié)點(diǎn)一定是根結(jié)點(diǎn)。 判斷題 *對(duì)對(duì)(正確答案)錯(cuò)50、某完全二叉樹有 13 個(gè)度為 2 的結(jié)點(diǎn)，1 個(gè)度為 1 的結(jié)點(diǎn)，則可以推算出該完全二叉樹總共有 28 個(gè)結(jié)點(diǎn)。 判斷題 *對(duì)對(duì)(正確答案)錯(cuò)51、若輸入序列為 1,2,3,4,5,6,則通過(guò)一個(gè)?？梢暂敵鲂蛄?4,2,5,6,3,1。 判斷題 *對(duì)對(duì)錯(cuò)(正確答案)52 靜態(tài)查找與動(dòng)態(tài)查找并沒有什么區(qū)別。 判斷題 *對(duì)對(duì)錯(cuò)(正確答案)判斷題*對(duì)對(duì)(正確答案)錯(cuò)判斷題 *對(duì)對(duì)錯(cuò)(正確答案)strcpychar*判斷題 *對(duì)對(duì)(正確答案)錯(cuò)56、字符串的處理函數(shù) strlen 是系統(tǒng)