數(shù)據(jù)結(jié)構(gòu)與算法第十一單元測試題（判斷+多選）測試題

1、數(shù)據(jù)結(jié)構(gòu)與算法第十一單元測試題（判斷+多選）復(fù)制1.在使用除留余數(shù)法時(shí)，對(duì)p的選擇很重要。若p選的不好，容易產(chǎn)生同義詞。 判斷題 *對(duì)(正確答案)錯(cuò)2.二叉排序樹的后序序列是指，按后序(左子樹 右子樹 根結(jié)點(diǎn))的方式遍歷該二叉排序樹得到的序列。 判斷題 *對(duì)(正確答案)錯(cuò)3.動(dòng)態(tài)查找的常用方法是二叉排序樹。 判斷題 *對(duì)(正確答案)錯(cuò)4.靜態(tài)查找與動(dòng)態(tài)查找并沒有什么區(qū)別。 判斷題 *對(duì)錯(cuò)(正確答案)5動(dòng)態(tài)查找表屬于樹形結(jié)構(gòu)，因?yàn)檫@里涉及二叉排序樹。 判斷題 *對(duì)錯(cuò)(正確答案)6.裝填因子是哈希表的一個(gè)重要參數(shù)，它反映哈希表的裝滿程度。 判斷題 *對(duì)(正確答案)錯(cuò)7.若哈希表的裝填因子1，則可避

2、免沖突的產(chǎn)生。 判斷題 *對(duì)錯(cuò)(正確答案)8.負(fù)載因子(裝填因子)是哈希表的一個(gè)重要參數(shù),它反映哈希表的裝滿程度，該值越大則發(fā)生沖突可能性越大。 判斷題 *對(duì)(正確答案)錯(cuò)9.哈希函數(shù)是一個(gè)映像。 判斷題 *對(duì)(正確答案)錯(cuò)10.二叉排序樹的左子樹也應(yīng)該不一定是棵二叉排序樹。 判斷題 *對(duì)錯(cuò)(正確答案)11.哈希表的平均查找長度與處理沖突的方法無關(guān)。 判斷題 *對(duì)錯(cuò)(正確答案)12.二叉排序樹的右子樹也應(yīng)該一定是棵二叉排序樹。 判斷題 *對(duì)(正確答案)錯(cuò)13.靜態(tài)查找與動(dòng)態(tài)查找主要區(qū)別在于是否改變表內(nèi)的元素。 判斷題 *對(duì)(正確答案)錯(cuò)14.二叉排序樹的左子樹也應(yīng)該是棵二叉排序樹。 判斷題 *

3、對(duì)(正確答案)錯(cuò)15.二叉排序樹的右子樹也應(yīng)該是棵二叉排序樹。 判斷題 *對(duì)(正確答案)錯(cuò)16.二叉排序樹的查找方式跟順序表的折半查找類似。 判斷題 *對(duì)(正確答案)錯(cuò)17.中序遍歷二叉排序樹是降序序列。 判斷題 *對(duì)錯(cuò)(正確答案)18.對(duì)不同的關(guān)鍵字可能得到同一哈希地址，即keykey2面f(key1)=f(key2)這種現(xiàn)象稱沖突(collision)。具有相同函數(shù)值的關(guān)鍵詞對(duì)該哈希來說乘坐同義詞。(對(duì)) 單選題 *A 對(duì)(正確答案)B 錯(cuò)19.如果哈希表的長度足夠大，就可以避免發(fā)生沖突。 判斷題 *對(duì)錯(cuò)(正確答案)20.若對(duì)于關(guān)鍵字集合中的任何一個(gè)關(guān)鍵字，經(jīng)哈希函數(shù)映像到地址集合中任何一

4、個(gè)地址的概率是相等的。則稱此類哈希函數(shù)為均勻的(Uniform)哈希函數(shù)。 判斷題 *對(duì)(正確答案)錯(cuò)21.直接定址法就是取關(guān)鍵字或關(guān)鍵字的某個(gè)線性函數(shù)值為哈希地址。 判斷題 *對(duì)(正確答案)錯(cuò)22.關(guān)于二叉排序樹描述有誤的是（）。 *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)鍵字23.二叉排序的的哪些遍歷序列，不能得到一個(gè)升序序列，或非遞減有序序列。（） *A.先序序列(正確答案)B.中序遍歷C.

5、后序遍歷(正確答案)D.按層次遍歷序列(正確答案)24.已知一棵樹是二叉排序樹，則該樹具有（）的特點(diǎn)。 *A.若左子樹不為空，則左子樹上的所有結(jié)點(diǎn)的值(關(guān)鍵字)都小于根節(jié)點(diǎn)的值；(正確答案)B.若右子樹不為空，則右子樹上的所有結(jié)點(diǎn)的值(關(guān)鍵字)都大于根節(jié)點(diǎn)的值；(正確答案)C.左、右子樹都分別為二叉排序樹。(正確答案)D.其中序序列是一個(gè)非遞減有序序列。(正確答案)25.動(dòng)態(tài)查找表：邊查找，邊改變集合中的元素，改變的方式可以是（）。 *A.增加(正確答案)B.刪除(正確答案)C.交換D.移動(dòng)26.關(guān)于二叉排序樹描述正確的是（）。 *A.二叉排序的右子樹上結(jié)點(diǎn)的關(guān)鍵字小于左子樹上的結(jié)點(diǎn)的關(guān)鍵字B

6、.二叉排序的左子樹上結(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)鍵字(正確答案)27.二叉樹的先序遍歷和中序遍歷如下：先序遍歷:EFHIGJK；中序遍歷HFIEJKG。該二叉樹根的左子樹的根不可能是:()。多選題 *A.E(正確答案)B.FC.G(正確答案)D.H(正確答案)28.下面屬于構(gòu)造散列函數(shù)的方法是（） *A.直接定址法(正確答案)B.數(shù)字分析法(正確答案)C.除留余數(shù)法(正確答案)D.平方取中法(正確答案)29.下面屬于處理沖突的方法是（） *A.開放定址法(正確答案)B.再哈希法

7、(正確答案)C.除留余數(shù)法D.直接定址法30.關(guān)于裝填因子，以下說法正確的是（）。 *A.哈希表的平均查找長度與處理沖突的方法無關(guān)。B.若散列表的負(fù)載因子(裝填因子)1，則可避免沖突的產(chǎn)生。C.散列法的平均檢索長度不隨表中結(jié)點(diǎn)數(shù)目的增加而增加，而是隨負(fù)載因子的增大而增大。(正確答案)D.負(fù)載因子 (裝填因子)是散列表的一個(gè)重要參數(shù)，它反映散列表的裝滿程度。(正確答案)31.哈希表的平均查找長度與哪些（）因素有關(guān)。 *A.處理沖突的方法(正確答案)B.哈希函數(shù)(正確答案)C.裝填因子(正確答案)D.待存記錄的大小32.裝填因子的計(jì)算方法是（）。 *A.1-(表中未填入記錄的數(shù)目/哈希表的總長度)

8、(正確答案)B.表中未填入記錄的數(shù)目/哈希表的總長度C.(表中未填入的記錄數(shù)-1)/哈希表的總長度D.表中填入的記錄數(shù)/哈希表的總長(正確答案)33.關(guān)于二叉排序樹相關(guān)描述正確的是（）。 *A.二叉排序樹是應(yīng)用于動(dòng)態(tài)查找的結(jié)構(gòu)(正確答案)B.二叉排序樹的中序列是升序序列(正確答案)C.二叉排序樹的左子樹也是二叉排序樹(正確答案)D.二叉排序樹的定義具有遞歸性(正確答案)34.動(dòng)態(tài)查找概念不正確的是（）。 *A.動(dòng)態(tài)查找只查找不改變集合內(nèi)的元素(正確答案)B.動(dòng)態(tài)查找邊查找，邊改變集合內(nèi)的元素C.動(dòng)態(tài)查找與靜態(tài)查找都是不改變集合內(nèi)的元素(正確答案)D.上面沒有正確的說法(正確答案)35.二叉排序

9、樹的查找方式和（）相似，請(qǐng)將不是這個(gè)答案的選項(xiàng)選上。 *A.折半查找B.順序查找(正確答案)C.隨機(jī)查找(正確答案)D.跳躍式查找(正確答案)36.動(dòng)態(tài)查找的典型工具是（），請(qǐng)將不是這個(gè)答案的選項(xiàng)選上。 *A.二叉排序樹B.棧(正確答案)C.數(shù)組(正確答案)D.隊(duì)列(正確答案)37.下列關(guān)于查找表描述正確的是（）。 *A.查找表分為靜態(tài)查找表和動(dòng)態(tài)查找表(正確答案)B.動(dòng)態(tài)查找表邊查找，邊改變集合內(nèi)的元素(正確答案)C.靜態(tài)查找表只查找不改變集合中的元素(正確答案)D.其它選項(xiàng)說法都正確(正確答案)38.下面屬于構(gòu)造哈希函數(shù)的方法是（）。 *A.平方取中法(正確答案)B.再哈希法C.除留余數(shù)法

10、(正確答案)D.數(shù)字分析法(正確答案)39.查找哈希表，不是解決沖突的方法包括（）。 *A.數(shù)字分析法(正確答案)B.除留余數(shù)法(正確答案)C.直接地址法(正確答案)D.線性探測再散列法40.數(shù)據(jù)結(jié)構(gòu)與算法里，設(shè)哈希表長度為11,哈希函數(shù)H(K)=(K的第一個(gè)字母在字母表中的序號(hào))MOD11,若輸入順序?yàn)?D,BA,TN,M,CI,I,K,X,TA),采用內(nèi)散列表,處理沖突方法為線性探測法,要求構(gòu)造哈希表,在等概率情況下查找成功平均查找長度錯(cuò)誤的是()。 *A.4(正確答案)B.3(正確答案)C.20/9D.23/9(正確答案)41.數(shù)據(jù)結(jié)構(gòu)與算法里，關(guān)于哈希表的裝填因子，以下正確的有（）。 *A.裝填因子的值越小，發(fā)生沖突的概率越小(正確答案)B.裝填因子越大，表中填入的記錄越多，在填入的時(shí)候發(fā)生沖突的可能性就越大，在進(jìn)行查找時(shí)候，查找的次數(shù)也就越多。(正確答案)C.裝填因子=