數(shù)據(jù)結(jié)構(gòu)考試復(fù)習(xí)題庫(kù)

單項(xiàng)選擇題向一個(gè)有128個(gè)元素的順序表中插入一個(gè)新元素并保持原來(lái)順序不變,平均要移動(dòng) ()個(gè)元素.64 B.63 C.63.5 D.7【答案】A線(xiàn)性表是具有n個(gè)()的有限序列(n^0)o表元素B.字符 C.數(shù)據(jù)元素 D.數(shù)據(jù)項(xiàng)【答案】C以下哪種排序方法在最壞的情況下的時(shí)間復(fù)雜度是 O(n*log2n)().A.直接插入排序 B.堆排序C. 簡(jiǎn)單項(xiàng)選擇擇排序 D. 快速排序【答案】B數(shù)組A[5][6]的每個(gè)元素占5個(gè)單元,將其按行優(yōu)先次序存儲(chǔ)在起始地址為 1000的連續(xù)的內(nèi)存單元中,那么元素A[4][4]的地址為().1140 B.1145 C.1120 D.1125【答案】A從一個(gè)棧頂指針為HS的鏈棧中刪除一個(gè)結(jié)點(diǎn)時(shí),用x保存被刪結(jié)點(diǎn)的值,那么執(zhí)行().x=HS;HS=HS->next;x=HS->data;HS=HS->next;x=HS->data;x=HS->data;HS=HS->next;【答案】D含6個(gè)頂點(diǎn)(vo,vi,V2,V3,V4,V5)的無(wú)向圖的鄰接矩陣如下圖,那么從頂點(diǎn) V.出發(fā)進(jìn)行深度優(yōu)先遍歷可能得到的頂點(diǎn)訪問(wèn)序列為().A.(V0,V1,V2,V5,V4,V3)B.(V0,V1,V2,V3,V4,V5)C.(V0,V1,V5,V2,V3,V4)D.(V0,V1,V4,V5,V2,V3)【答案】A7.如下陳述中正確的選項(xiàng)是 ().A.串是一種特殊的線(xiàn)性表B.串的長(zhǎng)度必須大于零C.串中元素只能是字母D.空串就是空白串【答案】A在一個(gè)長(zhǎng)度為n的順序表中插入一個(gè)元素時(shí),等概率情況下的平均移動(dòng)元素的次數(shù)是 ()A.n/2B.(n-1)/2C.n*(n-1)/2 D. (n+1)/2【答案】A數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)包括順序、鏈接、散列和()4種根本類(lèi)型.向量B.數(shù)組C.集合 D.索引【答案】D在含n個(gè)頂點(diǎn)和e條邊的無(wú)向圖的鄰接矩陣中,零元素的個(gè)數(shù)為().A.e B.2e C.n2-e D.n2-2e【答案】D引入二叉線(xiàn)索樹(shù)的目的是 ().加快查找結(jié)點(diǎn)的前驅(qū)或后繼的速度為了能在二叉樹(shù)中方便的進(jìn)行插入與刪除為了能方便的找到雙親使二叉樹(shù)的遍歷結(jié)果惟一【答案】A

對(duì)一棵m階B-樹(shù),以下選項(xiàng)錯(cuò)誤的選項(xiàng)是B.除根結(jié)點(diǎn)和葉結(jié)點(diǎn)外,每個(gè)結(jié)B.除根結(jié)點(diǎn)和葉結(jié)點(diǎn)外,每個(gè)結(jié)點(diǎn)至少有 [m/2]棵子樹(shù)C.有k棵子樹(shù)的結(jié)點(diǎn)必有k個(gè)關(guān)鍵字(k<=m)D.根結(jié)點(diǎn)至少有兩棵子樹(shù)【答案】CTOC\o"1-5"\h\z循環(huán)隊(duì)列用數(shù)組A[M]存放元素,其頭尾指針?lè)謩e為 front和rear,那么當(dāng)前隊(duì)列中的元素個(gè)數(shù)是 ()A.rear-front+1B.rear-front-1C.rear-frontD.(rear-front+M)%M【答案】D判斷兩個(gè)串大小的根本準(zhǔn)那么是 ().A.兩個(gè)串長(zhǎng)度的大小 B. 兩個(gè)串中首字符的大小C.兩個(gè)串中大寫(xiě)字母的多少 D.對(duì)應(yīng)的第一個(gè)不等字符的大小【答案】D在線(xiàn)性表的以下運(yùn)算中,不改變數(shù)據(jù)元素之間結(jié)構(gòu)關(guān)系的運(yùn)算是 ().A.插入B.刪除C.排序D.定位【答案】D對(duì)用鄰接矩陣表示的連通圖進(jìn)行深度或廣度優(yōu)先遍歷時(shí)的時(shí)間復(fù)雜度為 ().A.O(n2) B.O(n)C.O(e2) D.O(e+n)【答案】A對(duì)用鄰接表表示的連通圖進(jìn)行深度或廣度優(yōu)先遍歷時(shí)的時(shí)間復(fù)雜度為 ().A.O(n2) B.O(e2)C.O(n+e) D.O(n2)【答案】C一棵有124個(gè)葉子結(jié)點(diǎn)的完全二叉樹(shù),至多有()個(gè)結(jié)點(diǎn).A.251B.250C.248 D.247【答案】D如果最常用的操作是提取第i個(gè)結(jié)點(diǎn)及其前驅(qū),那么采用()存儲(chǔ)方式最節(jié)省時(shí)間A.單鏈表 B.順序表 C.循環(huán)鏈表 D.雙鏈表【答案】B計(jì)算機(jī)算法指的是().A.計(jì)算方法 B.排序方法C.解決問(wèn)題的有限運(yùn)算序列 D.調(diào)度方法在一個(gè)單鏈表中q所指的結(jié)點(diǎn)是p所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn),假設(shè)在q和p之間插入st吉點(diǎn),那么執(zhí)行()A.s->next=p->next;p->next=s;p->next=s->next;s->next=p;q->next=s;s->next=p;p->next=s;s->next=q;【答案】C對(duì)關(guān)鍵字集合K={53,30,37,12,45,24,96}, 從一棵空二叉樹(shù)開(kāi)始逐個(gè)插入關(guān)鍵字, 建立二叉排序樹(shù),假設(shè)希望得到的二叉排序樹(shù)的高度最小,應(yīng)選用以下輸入序列 ().A.4A.45,24,53,12,37,96,30B.37,24,12,30,53,45,96C.1C.12,24,30,37,45,53,96BD.30,24,12,37,45,96,532323.有8個(gè)結(jié)點(diǎn)的無(wú)向圖最多有)條邊A.14B.28C.56D.112【答案】B在一非空二叉樹(shù)的中序遍歷序列中 ,根結(jié)點(diǎn)的右邊〔〕.A.只有右子樹(shù)上的所有結(jié)點(diǎn) B.只有右子樹(shù)上的局部結(jié)點(diǎn)C.只有左子樹(shù)上的局部結(jié)點(diǎn) D.只有左子樹(shù)上的所有結(jié)點(diǎn)【答案】A稀疏矩陣一般的壓縮存儲(chǔ)有兩種,即 〔〕.A.一維數(shù)組和二維數(shù)組 B .一維數(shù)組和三元組C.二維數(shù)組和十字鏈表 D .三元組和十字鏈表【答案】D含n個(gè)關(guān)鍵字的二叉排序樹(shù)的平均查找長(zhǎng)度主要取決于 〔〕.A.關(guān)鍵字的個(gè)數(shù) B.樹(shù)的形態(tài)C.關(guān)鍵字的取值范圍D.關(guān)鍵字的數(shù)據(jù)類(lèi)型【答案】B對(duì)表〔21,36,40,44,58,64,79,73〕進(jìn)行排序,使用以下〔〕方法最好.A.簡(jiǎn)單項(xiàng)選擇擇排序 B.堆排序C.冒泡排序 D.歸并排序【答案】CTOC\o"1-5"\h\z將一棵有100個(gè)結(jié)點(diǎn)的完全二叉樹(shù)從根的這一層開(kāi)始,每一層從左到右依次對(duì)結(jié)點(diǎn)進(jìn)行編號(hào),根結(jié)點(diǎn)編號(hào)為1,那么編號(hào)為 49的結(jié)點(diǎn)的左孩子的編號(hào)為 〔〕.A.98B.99C.50D.48【答案】A在一棵6階的B-樹(shù)中,除根結(jié)點(diǎn)外,每個(gè)結(jié)點(diǎn)中的至少有 〔〕個(gè)關(guān)鍵字.A〕5 B〕4 C〕3 D〕2【答案】D具有15個(gè)結(jié)點(diǎn)的二叉樹(shù)的最小深度是 〔〕.A.4 B.5 C.3 D.6【答案】A向一個(gè)棧頂指針為HS的鏈棧中插入一個(gè)s所指結(jié)點(diǎn)時(shí),那么執(zhí)行〔〕.HS->next=s;s->next=HS->next;HS->next=s;s->next=HS;HS=s;s->next=HS;HS=HS->next;【答案】B設(shè)森林F中有三棵樹(shù),第一,第二,第三棵樹(shù)的結(jié)點(diǎn)個(gè)數(shù)分別為 N1,N2和N3.與森林F對(duì)應(yīng)的二叉樹(shù)根結(jié)點(diǎn)的右子樹(shù)上的結(jié)點(diǎn)個(gè)數(shù)是〔〕.A.N1B.N1+N2C.N3 D.N2+N3【答案】D二維數(shù)組A[4][5]按行優(yōu)先順序存儲(chǔ),假設(shè)每個(gè)元素占2個(gè)存儲(chǔ)單元,且第一個(gè)元素A[0][0]的存儲(chǔ)地址為1000,那么數(shù)組元素A[3][2]的存儲(chǔ)地址為〔〕.A.1012 B.1017 C.1034 D.1036【答案】C在循環(huán)雙鏈表的p所指接點(diǎn)之前插入s所指接點(diǎn)的操作是 〔〕.p->prior=s;s->next=p;p->prior->neft=s;s->prior=p->prior;p->prior=s;p->prior->next=s;s->next=p;s->prior=p->prior;s->next=p;s->prior=p->prior;p->prior=s;p->prior->next=s;

s->next=p;s->prior=p->prior;p->prior->next=s;p->prior=s;【答案】D要求每個(gè)結(jié)點(diǎn)的編號(hào)大于其左右孩子的編要求每個(gè)結(jié)點(diǎn)的編號(hào)大于其左右孩子的編號(hào), 同一個(gè)結(jié)點(diǎn)的左右孩子中,其左孩子的編號(hào)小次序的遍歷實(shí)現(xiàn)編號(hào).于其右孩子的編號(hào),那么可采用〔〕D.從根開(kāi)始的層次遍歷A.先序D.從根開(kāi)始的層次遍歷【答案】C36.在36.在有向圖的頂點(diǎn)的拓?fù)湫蛄兄?如果A.圖中有弧<V,Vj>C.圖中沒(méi)有弧<V,Vj>【答案】DB.D.Vi在Vj之前,那么以下情況一定不會(huì)出現(xiàn)的是

圖中V到Vj有一條路徑圖中有弧<Vj,Vi>A.4 B.A.4 B.5C.8D.9【答案】C38.假設(shè)一個(gè)棧的入棧序列是1,2,3, ..n,其輸出序列為p1,p2,p3,??-???.,pn,右p1=n,那么pi為()A.i B.n+i C.n-i+1D.不確定37.假設(shè)在9階B-樹(shù)中插入關(guān)鍵字引起結(jié)點(diǎn)分裂,那么該結(jié)點(diǎn)在插入前含有的關(guān)鍵字個(gè)數(shù)為〕.【答案】C對(duì)稀疏矩陣進(jìn)行壓縮存儲(chǔ)是為了 〔〕.A.便于進(jìn)行矩陣運(yùn)算B.便于輸入和輸出 C.節(jié)省存儲(chǔ)空間D.降低運(yùn)算的時(shí)間復(fù)雜度【答案】C有向圖中一個(gè)頂點(diǎn)的度是該頂點(diǎn)的 〔 〕.A.入度B.出度C.入度與出度之和 D.〔入度+出度〕/2【答案】C在一棵度為3的樹(shù)中,度為2的結(jié)點(diǎn)數(shù)為4,度為3的結(jié)點(diǎn)數(shù)為3,那么該樹(shù)中的葉子結(jié)點(diǎn)數(shù)為 〔〕A.5 B.8 C.11 D.18【答案】C適于對(duì)動(dòng)態(tài)查找表進(jìn)行高效率查找的組織結(jié)構(gòu)是 〔〕A.有序表B.分塊有序表 C.三叉排序樹(shù) D.線(xiàn)性鏈表【答案】C在一棵7階B-樹(shù)中,除根結(jié)點(diǎn)外,每個(gè)結(jié)點(diǎn)中最多有〔〕個(gè)關(guān)鍵字.A.6 B.5 C.4 D.3【答案】A以下排序方法中,要求附加的內(nèi)存容量最大的是 〔〕.A.冒泡排序 B.快速排序 C.堆排序D.歸并排序【答案】D具有9個(gè)葉結(jié)點(diǎn)的二叉樹(shù)中有 〔〕個(gè)度為2的結(jié)點(diǎn).A.8 B.9 C.10 D.11【答案】A在數(shù)據(jù)結(jié)構(gòu)中,從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成 〔〕.A.動(dòng)態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu) B.緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)C.線(xiàn)性結(jié)構(gòu)和非線(xiàn)性結(jié)構(gòu) D.內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)【答案】C47.以下排序算法中,〔〕A.堆排序B.冒泡排序算法可能會(huì)出現(xiàn)下面情況：初始數(shù)據(jù)有序,花費(fèi)時(shí)間反而最多C.快速排序 D.Shell排序【答案】C由3個(gè)結(jié)點(diǎn)可以構(gòu)造出〔〕種不同的二叉樹(shù).TOC\o"1-5"\h\z2 B.3 C.4 D.5【答案】D存儲(chǔ)無(wú)向圖的鄰接矩陣一定是一個(gè) 〔 〕.A.上三角矩陣B.稀疏矩陣C. 對(duì)稱(chēng)矩陣D.對(duì)角矩陣【答案】C具有5個(gè)頂點(diǎn)的無(wú)向完全圖有〔〕條邊.A.6. B.10. C.16 D.20【答案】B樹(shù)的先根序列等同于與該樹(shù)對(duì)應(yīng)的二叉樹(shù)的 〔〕.A.先序序列 B.中序序列C.后序序列 D.層序序列【答案】A在一棵度為3的樹(shù)中,度為3的結(jié)點(diǎn)個(gè)數(shù)為2,度為2的結(jié)點(diǎn)個(gè)數(shù)為1,那么度為0的結(jié)點(diǎn)個(gè)數(shù)為〔〕.A.4 B.5 C.6 D.7【答案】C假設(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〕【答案】C算法分析的目的是〔〕.A.找出數(shù)據(jù)結(jié)構(gòu)的合理性 B.研究算法中的輸入和輸出的關(guān)系C.分析算法的效率以求改良 D.分析算法的易懂性和文檔性【答案】C有8個(gè)結(jié)點(diǎn)的無(wú)向連通圖最少有〔〕條邊.A.5B.6C.7D.8【答案】C研究數(shù)據(jù)結(jié)構(gòu)就是研究 〔〕.數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)以及其數(shù)據(jù)在運(yùn)算上的實(shí)現(xiàn)【答案】D非線(xiàn)性結(jié)構(gòu)是數(shù)據(jù)元素之間存在一種 〔〕.A.一對(duì)多關(guān)系 B.多對(duì)多關(guān)系C.多對(duì)一關(guān)系D.一對(duì)一關(guān)系【答案】B某二叉樹(shù)的先序序列和后序序列正好相反,那么該二叉樹(shù)一定是 〔〕的二叉樹(shù)A.空或只有一個(gè)結(jié)點(diǎn) B.高度等于其結(jié)點(diǎn)數(shù)C.任一結(jié)點(diǎn)無(wú)左孩子 D.任一結(jié)點(diǎn)無(wú)右孩子【答案】BTOC\o"1-5"\h\z高度為5的完全二叉樹(shù)中含有的結(jié)點(diǎn)數(shù)至少為 〔〕.A.16 B.17 C.31 D.32【答案】A由同一關(guān)鍵字集合構(gòu)造的各棵二叉排序樹(shù) 〔

其形態(tài)不一定相同,但平均查找長(zhǎng)度相同其形態(tài)不一定相同,平均查找長(zhǎng)度也不一定相同其形態(tài)均相同,但平均查找長(zhǎng)度不一定相同其形態(tài)均相同,平均查找長(zhǎng)度也都相同【答案】B算法分析的兩個(gè)主要方面是 ().正確性和簡(jiǎn)單性 B.可讀性和文檔性C.數(shù)據(jù)復(fù)雜性和程序復(fù)雜性 D.時(shí)間復(fù)雜度和空間復(fù)雜度【答案】D對(duì)關(guān)鍵字序列(56,23,78,92,88,67,19,34)進(jìn)行增量為3的一趟希爾排序的結(jié)果為 ().(19, 23, 56, 34,78,67, 88, 92) B.(23,56, 78, 66, 88,92,19,34)C.(19, 23, 34, 56,67,78, 88, 92) D.(19,23, 67, 56, 34,78,92,88)【答案】D()不是哈希查找中的沖突處理方法.A.鏈地址法 B.再哈希法C.除留余數(shù)法 D?隨機(jī)探測(cè)法【答案】C在一個(gè)順序表中,假設(shè)表的第一個(gè)元素的存儲(chǔ)地址是 210,每一個(gè)元素的長(zhǎng)度為3,那么第5個(gè)元素的存儲(chǔ)地址是 ().A.219B.222C.225D.228【答案】B在單鏈表中刪除結(jié)點(diǎn)的時(shí)間復(fù)雜度為 ().A.O(1) B.O(n2)C.O(n)D(logn)【答案】C設(shè)有一個(gè)10階的對(duì)稱(chēng)矩陣A,采用壓縮存儲(chǔ)方式,以行序?yàn)橹鞔鎯?chǔ), a1,1為第一個(gè)元素,其存儲(chǔ)地址為 1,每個(gè)元素占1個(gè)地址空間,那么a8,4的地址為().A.15 B.32 C.34 D.33【答案】B線(xiàn)性表采用鏈?zhǔn)酱鎯?chǔ)時(shí),結(jié)點(diǎn)的存儲(chǔ)地址 ().A.必須是不連續(xù)的B.連續(xù)與否均可必須是連續(xù)的和頭結(jié)點(diǎn)的存儲(chǔ)地址相連續(xù)【答案】BTOC\o"1-5"\h\z以下關(guān)鍵字序列中,構(gòu)成大根堆的是 ().A.5, 8, 1, 3, 9,6,2,7 B.9,8,1,7,5,6,2,3C.9, 8, 6, 3, 5,l,2,7 D.9,8,6,7,5,1,2,3【答案】D在連通圖的廣度優(yōu)先遍歷算法中,需要借助的輔助數(shù)據(jù)結(jié)構(gòu)是 ().A.隊(duì)列B.棧C.線(xiàn)性表D.有序表【答案】A引起循環(huán)隊(duì)列隊(duì)頭位置發(fā)生變化的操作是 ().A.出隊(duì)A.出隊(duì)【答案】AB.入隊(duì)C.取隊(duì)頭元素D.取隊(duì)尾元素文文檔來(lái)源為：從網(wǎng)絡(luò)收集整理.word版本可編輯.歡送下載支持AA.n-i B.n-i+1 C.n-i-1 D.i評(píng)價(jià)一個(gè)算法時(shí)間性能的主要標(biāo)準(zhǔn)是 ().A.算法易于調(diào)試B.算法易于理解C.算法的穩(wěn)定性和正確性 D.算法的時(shí)間復(fù)雜度【答案】D在長(zhǎng)度為n的順序表中插入一個(gè)元素時(shí),等概率情況下的平均移動(dòng)元素的次數(shù)是 ().A.(n-1)/2 B.n/2 C.n*(n-1)/2 D.(n+1)/2【答案】B一個(gè)順序存儲(chǔ)線(xiàn)性表,假設(shè)第 1個(gè)結(jié)點(diǎn)的地址d,第3個(gè)的地址是5d,那么第n個(gè)結(jié)點(diǎn)的地址為().A.[2*(n-1)+1]*d B.2*(n-1)*d C.[2*(n-1)-1]*d D.(n+1)*d【答案】A在一個(gè)長(zhǎng)度為n的順序存儲(chǔ)線(xiàn)性表中,刪除第i個(gè)元素(0<iV1)時(shí),需要從后向前依次前移 ()個(gè)元素.A.n-iB.n-i+1C.n-i-1D.i【答案】A在長(zhǎng)度為n的順序表中刪除一個(gè)元素時(shí),等概率情況下的平均移動(dòng)元素的次數(shù)是 ().A.(n-1)/2 B.n/2 C.n*(n-1)/2 D.(n+1)/2【答案】A如果T1是由有序樹(shù)T轉(zhuǎn)換而來(lái)的二叉樹(shù),那么T中結(jié)點(diǎn)的前序就是T1中結(jié)點(diǎn)的().A.前序 B.中序 C.后序 D.層次序【答案】ATOC\o"1-5"\h\z查找哈希表,不會(huì)產(chǎn)生沖突的哈希函數(shù)是 ().A.鏈地址法 B.直接地址法 C.除留余數(shù)法 D.隨機(jī)探測(cè)法【答案】B用某種排序方法對(duì)關(guān)鍵字序列(25, 84, 21,47,15,27,68,35, 20)進(jìn)行排序時(shí),序列的變化情況如下：20, 15, 21, 25, 47, 27, 68, 35, 8415, 20, 21, 25, 35, 27, 47, 68, 8415, 20, 21, 25, 27, 35, 47, 68, 84那么所采用的排序方法是 ().A.選擇排序 B.希爾排序C.歸并排序 D.快速排序【答案】D非空的循環(huán)單鏈表head的尾結(jié)點(diǎn)p滿(mǎn)足().A.P->next==NULLB.p==NULLC.P->next==headD.P==head【答案】C從一個(gè)具有n個(gè)結(jié)點(diǎn)的單鏈表中查找其值等于 x結(jié)點(diǎn)時(shí),在查找成功的情況下,需平均比擬 ()個(gè)結(jié)點(diǎn).A.nB.n/2 C.(n-1)/2 D.(n+1)/2【答案】D在有向圖的頂點(diǎn)的拓?fù)湫蛄兄?如果 Vi在Vj之前,那么以下情況一定不會(huì)出現(xiàn)的是 ().A.圖中有弧<V,Vj> B. 圖中V到Vj有一條路徑C.圖中沒(méi)有弧<V,Vj> D. 圖中有弧<Vj,Vi>【答案】D非空的循環(huán)單鏈表head的尾結(jié)點(diǎn)p滿(mǎn)足().A.P->next==NULLB.p==NULLC.P->next==headD.P==head【答案】C在一個(gè)長(zhǎng)度為n的順序存儲(chǔ)線(xiàn)性表中,向第i個(gè)元素(1<i<命前插入一個(gè)新元素時(shí),需要從后向前依次后移 ()個(gè)元素文文檔來(lái)源為：從網(wǎng)絡(luò)收集整理.word版本可編輯.歡送下載支持.【答案】B以下所示各圖中是中序線(xiàn)索化二叉樹(shù)的是 ().【答案】A以下程序段的時(shí)間復(fù)雜度為 ().s=0;for(i=1；i<n；i++)for(j=1;j<n；j++)s+=i*j；TOC\o"1-5"\h\zO(1)B.O(n)C.O(2n)D.O(n 2)【答案】D在一個(gè)有向圖中,所有頂點(diǎn)的入度之和等于所有頂點(diǎn)的出度之和的 ()倍.A.1/2B.1C.2D.4【答案】B鏈表不具有的特點(diǎn)是 ().A.可隨機(jī)訪問(wèn)任一元素 B.插入刪除不需要移動(dòng)元素C.不必事先估計(jì)存儲(chǔ)空間 D.所需空間與線(xiàn)性表的長(zhǎng)度成正比【答案】A對(duì)于如以下圖所示的帶權(quán)有向圖,從頂點(diǎn) 1到頂點(diǎn)5的最短路徑為().(1,4,5)B ?(1,2,3,5)C.(1,4,3,5)D .(1,2,4,3,5)【答案】D一個(gè)線(xiàn)性表第一個(gè)元素的存儲(chǔ)地址是 100,每個(gè)元素的長(zhǎng)度為4,那么第5個(gè)元素的地址是().110 B.116 C.100 D.120【答案】B頭指針指向假設(shè)以數(shù)組A[n]存放循環(huán)隊(duì)列的元素,其頭、尾指針?lè)謩e為front和rear.假設(shè)設(shè)定尾指針指向隊(duì)列中的隊(duì)尾元頭指針指向隊(duì)列中隊(duì)頭元素的前一個(gè)位置,那么當(dāng)前存于隊(duì)列中的元素個(gè)數(shù)為 ().A.(rear-front-1)%n B.(rear-front)%nC.(front-rear+1)%nD.(rear-front+n)%n【答案】D下面的關(guān)鍵字序列中,()不是堆.A.(32,54,43,72,66) B.(63,24,53,11,20)C.(11,53,20,24,63) D.(32,43,54,66,72)【答案】C一個(gè)順序棧的第10個(gè)元素的存儲(chǔ)地址是240,第15個(gè)元素的存儲(chǔ)地址是210,那么第25個(gè)元素的存儲(chǔ)地址是 ()A.144B.150C.336D.330【答案】B假設(shè)有向圖含n個(gè)頂點(diǎn)及e>弧,那么表示該圖的鄰接表中包含的弧結(jié)點(diǎn)個(gè)數(shù)為 ().A.n B.e C.2e D.n-e【答案】B在一個(gè)鏈隊(duì)中,假設(shè)f和r分別為隊(duì)首和隊(duì)尾指針,那么插入 s所指結(jié)點(diǎn)的運(yùn)算時(shí)().A.f->next=s;f=s;B.r->next=s;r=s;C.s->next=r;r=s;D.s->next=f;f=s;【答案】B95.按序列｛26,38,54,9,47,13,20)構(gòu)造一棵二叉排序樹(shù),其深度為 ().A.3B.4 C.5 D.6【答案】B數(shù)據(jù)結(jié)構(gòu)是一門(mén)研究非數(shù)值對(duì)象以及它們之間的 ()的學(xué)科.A.結(jié)構(gòu)B.關(guān)系C.運(yùn)算D.算法【答案】BTOC\o"1-5"\h\z在一個(gè)具有n個(gè)結(jié)點(diǎn)的有序單鏈表中插入一個(gè)新結(jié)點(diǎn)并仍然有序的時(shí)間復(fù)雜度是 ()A.O(1)B.O(n) C.O(n2) D.O(nlog2n)【答案】B以下排序方法中,穩(wěn)定的是 ().A.歸并排序B.快速排序C.堆排序 D.希爾排序【答案】A如果某圖的鄰接矩陣是對(duì)角線(xiàn)元素均為零的上三角矩陣,那么此圖是 ()A.有向完全圖 B.連通圖C.強(qiáng)連通圖 D.有向無(wú)環(huán)圖【答案】D組成數(shù)據(jù)的根本單位是 ().A.數(shù)據(jù)項(xiàng)B.數(shù)據(jù)類(lèi)型C.數(shù)據(jù)元素D.數(shù)據(jù)變量【答案】C循環(huán)隊(duì)列用數(shù)組A[M]存放元素,其頭尾指針?lè)謩e為 front和rear,那么當(dāng)前隊(duì)列中的元素個(gè)數(shù)是 ()A.rear-front+1B.rear-front-1C.rear-frontD.(rear-front+M)%M【答案】Dn個(gè)結(jié)點(diǎn)的完全有向圖含有邊的數(shù)目 ().A.n*n B.n(n+1) C.n/2D.n*(n-1)【答案】D任何一個(gè)無(wú)向連通圖的最小生成樹(shù) ().A.只有一棵 B.有一棵或多棵C.一定有多棵 D.可能不存在以下查找算法中,平均查找長(zhǎng)度與元素個(gè)數(shù) n不直接相關(guān)的查找方法是 ()A.分塊查找 B.順序查找C.二分查找 D.散列查找【答案】D在以下排序方法中,關(guān)鍵字比擬的次數(shù)與記錄的初始排列次序無(wú)關(guān)的是 ().A.冒泡排序 B.簡(jiǎn)單項(xiàng)選擇擇排序 C.直接插入排序D. 快速排序【答案】B鏈表不具有的特點(diǎn)是().可隨機(jī)訪問(wèn)任一元素插入刪除不需要移動(dòng)元素不必事先估計(jì)存儲(chǔ)空間所需空間與線(xiàn)性表長(zhǎng)度成正比【答案】A有40個(gè)結(jié)點(diǎn)的完全二叉樹(shù)存儲(chǔ)在數(shù)組T [1..40] 中,數(shù)組T中第一個(gè)葉子結(jié)點(diǎn)是 ()A.T[19] B.T[20] C.T[21]D.T[22]

【答案】C由同一關(guān)鍵字集合構(gòu)造的各棵二叉排序樹(shù) 〔〕.其形態(tài)不一定相同,但平均查找長(zhǎng)度相同其形態(tài)不一定相同,平均查找長(zhǎng)度也不一定相同其形態(tài)均相同,但平均查找長(zhǎng)度不一定相同其形態(tài)均相同,平均查找長(zhǎng)度也都相同【答案】B對(duì)于一個(gè)具有5個(gè)頂點(diǎn)的無(wú)向圖,假設(shè)采用鄰接矩陣表示,那么該矩陣的大小〔〕A.10 B.20 C.16 D.25【答案】D用鄰接表表示圖進(jìn)行深度優(yōu)先遍歷時(shí),通常是采用〔〕來(lái)實(shí)現(xiàn)算法的.A.棧B.隊(duì)列C.樹(shù)D.圖【答案】A在有n個(gè)葉子結(jié)點(diǎn)的哈夫曼樹(shù)中,其結(jié)點(diǎn)總數(shù)為〔〕.A.不確定B.2nC.2n+1D.2n-1【答案】D對(duì)于一個(gè)頭指針為H的帶頭結(jié)點(diǎn)的單鏈表,判定該表為空表的條件是 〔〕A.H==NULLB.H!=NULLC.Htnext==HD.HRnext==NULL【答案】D任何一個(gè)無(wú)向連通圖的最小生成樹(shù) 〔〕A.只有一棵 B.有一棵或多棵 C.一定有多棵 D.可能不存在【答案】B在以下對(duì)順序表進(jìn)行的操作中,算法時(shí)間復(fù)雜度為 0〔1〕的是〔〕.訪問(wèn)第i個(gè)元素的前驅(qū)〔1<in〕在第i個(gè)元素之后插入一個(gè)新元素〔1in〕刪除第i個(gè)元素〔1in〕對(duì)順序表中元素進(jìn)行排序【答案】ATOC\o"1-5"\h\z線(xiàn)性表采用順序存儲(chǔ)的缺點(diǎn)是 〔〕..插入和刪除操作效率低D.插入和刪除操作效率低D.只能順序訪問(wèn)B.存儲(chǔ)結(jié)構(gòu)不同C.元素的邏輯順序和物理順序不一致【答案】B隊(duì)和棧的主要區(qū)別是 〔〕.A.邏輯結(jié)構(gòu)不同C.C.所包含的運(yùn)算個(gè)數(shù)不同【答案】DD.限定插入和刪除的位置不同將將遞歸算法轉(zhuǎn)換成對(duì)應(yīng)的非遞歸算法時(shí),通常使用 〔〕A.棧B.隊(duì)列C.鏈表D.矩陣【答案】A線(xiàn)性表L=〔a1,a2,???an〕以下說(shuō)法正確的選項(xiàng)是 〔〕.每個(gè)元素都有一個(gè)直接前驅(qū)和一個(gè)直接后繼線(xiàn)性表中至少要有一個(gè)元素表中諸元素的排列順序必須是有小到大或者由大到小除第一個(gè)和最后一個(gè)元素外,其余每個(gè)元素都有一個(gè)且僅有一個(gè)直接前驅(qū)和直接后繼.【答案】D非空的循環(huán)單鏈表head的尾結(jié)點(diǎn)〔由P指向〕滿(mǎn)足〔〕.A.p->next=NULLB.p=NULLC.p->next=head D.p=head【答案】C任何一棵二叉樹(shù)的葉結(jié)點(diǎn)在先序、中序和后序遍歷序列中的相對(duì)次序 〔〕.A.不發(fā)生改變 B.發(fā)生改變 C.不能確定 D.以上都不對(duì)【答案】A不帶權(quán)的無(wú)向圖的鄰接矩陣 〔〕.A.不一定是對(duì)稱(chēng)矩陣 B. 是對(duì)角線(xiàn)元素非零的對(duì)稱(chēng)矩陣C.是上三角矩陣D. 是對(duì)角線(xiàn)元素為零的對(duì)稱(chēng)矩陣【答案】D數(shù)據(jù)結(jié)構(gòu)是一門(mén)研究計(jì)算機(jī)中〔〕對(duì)象及其關(guān)系的學(xué)科.A.數(shù)值運(yùn)算 B.非數(shù)值運(yùn)算C.集合 D.非集合【答案】BTOC\o"1-5"\h\z如下圖有向圖的一個(gè)拓?fù)湫蛄惺?〔〕.A.ABCDEFB.FCBEADC.FEDCBAD.DAEBCF【答案】B8個(gè)數(shù)據(jù)元素為〔34,76,45,18,26,54,92,65〕,根據(jù)依次插入結(jié)點(diǎn)的方法生成一棵二叉排序樹(shù)后,最后兩層上的結(jié)點(diǎn)總數(shù)為 〔〕.A.1 B.2 C.3 D.4【答案】B假設(shè)以帶行表的三元組表表示稀疏矩陣,那么和以下行表02335對(duì)應(yīng)的稀疏矩陣是〔〕.【答案】A用鄰接表表示圖進(jìn)行廣度優(yōu)先遍歷時(shí),通常是采用 〔〕來(lái)實(shí)現(xiàn)算法的.TOC\o"1-5"\h\zA.棧B.隊(duì)列C. 樹(shù)D. 圖【答案】B在含n個(gè)頂點(diǎn)和e條邊的無(wú)向圖的鄰接矩陣中,零元素的個(gè)數(shù)為 〔 〕.A.eB.2eC.n 2-eD.n2-2e【答案】D在一個(gè)鏈隊(duì)中,假設(shè)f和r分別為隊(duì)首和隊(duì)尾指針,那么刪除一個(gè)結(jié)點(diǎn)的運(yùn)算時(shí) 〔〕.A.r=f->next; B.r=r->next;C.f=f->next; D.f=r->next;【答案】C一個(gè)n階對(duì)稱(chēng)矩陣,如果以行或列為主序放入內(nèi)存,那么容量為〔〕.A.n*n B.n**/2 C.〔n+1〕*〔n+1〕/2 D.n*〔n+1〕/2【答案】D用折半查找法查找表〔a1,a2,…,an〕,需要比擬4次才能找到的元素是 〔〕.A.a1和a8 B.a 4和a7 C.a 2和a& D.a 4和a〕.【答案】C棧S?多能容納4個(gè)元素,現(xiàn)有6個(gè)元素按a,b,c,d,e,f 的順序進(jìn)棧,下面序列〔〕是可能的出棧序列

A.edcbafB.bcefadC.cbedafD.adfebc【答案】CTOC\o"1-5"\h\z將長(zhǎng)度為n的單鏈表鏈接在長(zhǎng)度為m的單鏈表之后的算法的時(shí)間復(fù)雜度為 ().A.O(1) B.O(n) C.O(m) D.O(m+n)【答案】C以數(shù)組Q[0..m-1]存放循環(huán)隊(duì)列中的元素,變量rear和qulen分別指示循環(huán)隊(duì)列中隊(duì)尾元素的實(shí)際位置和當(dāng)前隊(duì)列中元素的個(gè)數(shù),隊(duì)列第一個(gè)元素的實(shí)際位置是 ().A.rear—qulenB.rear—qulen+mC.m—qulenD.1+(rear+m—qulen)%m【答案】B評(píng)價(jià)一個(gè)算法時(shí)間性能的主要標(biāo)準(zhǔn)是 ().A.算法易于調(diào)試B.算法易于理解C.算法的穩(wěn)定性和正確性 D.算法的時(shí)間復(fù)雜度【答案】D由兩個(gè)棧共享一個(gè)向量空間的好處是 ().減少存取時(shí)間,降低下溢發(fā)生的機(jī)率節(jié)省存儲(chǔ)空間,降低上溢發(fā)生的機(jī)率減少存取時(shí)間,降低上溢發(fā)生的機(jī)率節(jié)省存儲(chǔ)空間,降低下溢發(fā)生的機(jī)率B具有7具有7個(gè)頂點(diǎn)的無(wú)向圖至少應(yīng)有A.5 B.6 C.7 D.8【答案】B樹(shù)最適合用來(lái)表示().A.有序數(shù)據(jù)元素C.元素之間具有分支層次關(guān)系的數(shù)據(jù)【答案】C棧結(jié)構(gòu)通常采用的兩種存儲(chǔ)結(jié)構(gòu)是A.順序存儲(chǔ)結(jié)構(gòu)和鏈表存儲(chǔ)結(jié)構(gòu)C.鏈表存儲(chǔ)結(jié)構(gòu)和數(shù)組【答案】A常對(duì)數(shù)組進(jìn)行的兩種根本操作是A.建立與刪除 B.索引和修改【答案】C()條邊才能保證是一個(gè)連通圖無(wú)序數(shù)據(jù)元素D.元素之間無(wú)聯(lián)系的數(shù)據(jù)().散列方式和索引方式D.線(xiàn)性存儲(chǔ)結(jié)構(gòu)和非線(xiàn)性存儲(chǔ)結(jié)構(gòu)().查找和修改 D.查找與索引數(shù)據(jù)結(jié)構(gòu)中,與所使用的計(jì)算機(jī)無(wú)關(guān)的是數(shù)據(jù)的 ()結(jié)構(gòu).A.順序B.物理 C.邏輯 D.物理和存儲(chǔ)【答案】C可用帶表頭結(jié)點(diǎn)的鏈表來(lái)表示表,也可用不帶表頭結(jié)點(diǎn)的鏈表來(lái)表示表,前者的主要好處是 ()A.可以加快對(duì)表的遍歷 B. 使空表和非空表的處理統(tǒng)一提升存取結(jié)點(diǎn)的速度 D. 節(jié)省存儲(chǔ)空間【答案】B假設(shè)進(jìn)棧序列為a,b,c,d ,進(jìn)棧過(guò)程中可以出棧,那么 ()不可能是一個(gè)出棧序列.A.cbadB.bdcaC.cdbaD.adbc【答案】D填空題數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)結(jié)構(gòu)包括順序、 〔〕、索引和散列等四種.【答案】鏈接設(shè)關(guān)鍵字序列{7,12,26,30,47,58,66,70,82,90} ,當(dāng)用折半查找方法查找時(shí),所需比擬的次數(shù)為 3次的關(guān)鍵字分別是〔〕.【答案】7265882假定一個(gè)線(xiàn)性表為{12,23,74,55,63,40,82,36} ,假設(shè)按key%徐件進(jìn)行劃分,使得同一余數(shù)的元素成為一個(gè)子表,那么包含74的子表長(zhǎng)度為〔〕.【答案】2和二分查找相比,順序查找的優(yōu)點(diǎn)是除了不要求表中數(shù)據(jù)元素有序之外,對(duì)〔〕結(jié)構(gòu)也無(wú)特殊要求.【答案】存儲(chǔ)設(shè)雙向循環(huán)鏈表每個(gè)結(jié)點(diǎn)結(jié)構(gòu)為 〔data,llink,rlink〕,那么結(jié)點(diǎn)*p的前驅(qū)結(jié)點(diǎn)的地址為〔〕.【答案】p->llinkn個(gè)頂點(diǎn)的連通無(wú)向圖的生成樹(shù)含有 〔〕條邊.【答案】n-1TOC\o"1-5"\h\z在一個(gè)最大堆中,堆頂結(jié)點(diǎn)的值是所有結(jié)點(diǎn)中的 〔〕.【答案】最大值假定對(duì)長(zhǎng)度n=50的有序表進(jìn)行折半搜索,那么對(duì)應(yīng)的判定樹(shù)中最底下一層的結(jié)點(diǎn)數(shù)為 〔〕個(gè).【答案】19對(duì)于帶頭結(jié)點(diǎn)的鏈棧top,取棧頂元素的操作是 〔〕.【答案】*y=top->next->data假定一棵三叉樹(shù)〔即度為3的樹(shù)〕的結(jié)點(diǎn)個(gè)數(shù)為50,那么它的最小高度為 〔〕.假定樹(shù)根結(jié)點(diǎn)的深度為0.【答案】4二維數(shù)組是一種非線(xiàn)性結(jié)構(gòu),其中的每一個(gè)數(shù)組元素最多有 〔〕個(gè)直接前驅(qū)〔或直接后繼〕.【答案】?jī)蓚€(gè)在堆排序中,對(duì)任意一個(gè)分支結(jié)點(diǎn)進(jìn)行調(diào)整運(yùn)算的時(shí)間復(fù)雜度為 〔〕.【答案】O〔log2n〕隊(duì)列的刪除操作在〔〕進(jìn)行.【答案】隊(duì)頭〔或隊(duì)首〕設(shè)圖G=〔V,E〕,V={1,2,3,4},E={<1,2>,<1,3>,<2,4>,<3,4>} ,從頂點(diǎn)1出發(fā),對(duì)圖G進(jìn)行廣度優(yōu)先搜索的序列有〔〕種.【答案】2向一棵二叉搜索樹(shù)中插入一個(gè)元素時(shí),假設(shè)元素的值小于根結(jié)點(diǎn)的值,那么應(yīng)把它插入到根結(jié)點(diǎn)的 〔〕上【答案】左子樹(shù)快速排序在平均情況下的時(shí)間復(fù)雜度為 〔〕.【答案】O〔nlog2n〕17.由關(guān)鍵字序列(42,97,75,23,68,34)建成的最大堆是〔〕.【答案】97,68,75,23,42,3418.對(duì)于關(guān)鍵字序列(12 ,13,11,18,60,15,7,18,25,100〕,用篩選法建堆,必須從關(guān)鍵字為 〔〕的結(jié)點(diǎn)開(kāi)始.【答案】6019.從有序表〔12,18,30,43,56,78,82,95〕中折半搜索元素56時(shí),其搜索長(zhǎng)度為〔〕.【答案】3TOC\o"1-5"\h\z設(shè)有二叉樹(shù)根結(jié)點(diǎn)的層次為0,一棵高度為 h的滿(mǎn)二叉樹(shù)中的葉子結(jié)點(diǎn)個(gè)數(shù)是 〔〕.【答案】2h在一個(gè)最小堆中,堆頂結(jié)點(diǎn)的值是所有結(jié)點(diǎn)中的 〔〕.【答案】最小值在長(zhǎng)度為n的順序表中刪除一個(gè)元素時(shí),等概率情況下的平均移動(dòng)元素的次數(shù)是 〔〕.【答案】〔n-1〕/2由關(guān)鍵字序列〔57,24,76,63,18,31,15 〕生成的一棵二叉排序樹(shù),其等查找概率情況下查找成功的平均查找長(zhǎng)度為〔〕.【答案】18/7數(shù)據(jù)結(jié)構(gòu)包括邏輯結(jié)構(gòu)、 〔〕和數(shù)據(jù)的運(yùn)算三個(gè)方面.【答案】存儲(chǔ)結(jié)構(gòu)在一棵n#B樹(shù)上,每個(gè)非根結(jié)點(diǎn)的關(guān)鍵碼數(shù)最多為〔〕個(gè).【答案】m-1在雙向鏈表中,每個(gè)結(jié)點(diǎn)除了數(shù)據(jù)域外,還有兩個(gè)指針域,它們分別指向〔〕.【答案】前趨結(jié)點(diǎn)和后繼結(jié)點(diǎn)一般來(lái)說(shuō),深度優(yōu)先生成樹(shù)的高度比廣度優(yōu)先生成樹(shù)的高度要 〔〕.【答案】高遞歸工作棧起到兩個(gè)作用,其一是將遞歸調(diào)用時(shí)的實(shí)際參數(shù)和返回地址傳遞給下一層遞歸；其二是保存本層的形式參數(shù)和〔〕.【答案】局部變量在一個(gè)堆的順序存儲(chǔ)中,假設(shè)一個(gè)元素的下標(biāo)為 i〔0<i<n-1〕,那么它的右子女元素的下標(biāo)為 〔〕.【答案】2i+2數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)包括線(xiàn)性結(jié)構(gòu)和 〔〕結(jié)構(gòu)兩大類(lèi).【答案】非線(xiàn)性隊(duì)列是具有〔〕特性的線(xiàn)性表.【答案】先進(jìn)先出根本數(shù)據(jù)類(lèi)型是計(jì)算機(jī)已經(jīng)實(shí)現(xiàn)了的 〔〕.【答案】數(shù)據(jù)結(jié)構(gòu)n個(gè)頂點(diǎn)且含有環(huán)路的無(wú)向連通圖中,至少含有 〔〕條邊.【答案】n假設(shè)設(shè)L是指向帶表頭的單鏈表,語(yǔ)句L->link=L->link->link 的作用是〔〕單鏈表中的第一個(gè)結(jié)點(diǎn).【答案】刪除8個(gè)數(shù)據(jù)元素為〔34,76,45,18,26,54,92,65〕,根據(jù)依次插入結(jié)點(diǎn)的方法生成一棵二叉排序樹(shù)后,最后兩層上的結(jié)點(diǎn)總數(shù)為〔〕.【答案】2大小為肝勺順序存儲(chǔ)的循環(huán)隊(duì)列sq隊(duì)滿(mǎn)的條件為〔〕.【答案】〔sq.rear+1〕%M==sq.front假設(shè)設(shè)順序棧的最大容量為MaxSize,top==-1表示?？?那么判斷棧滿(mǎn)的條件是 〔〕.【答案】top==MaxSize-1假定一個(gè)順序表的長(zhǎng)度為40,并假定順序搜索每個(gè)元素的概率都相同,那么在搜索成功情況下的平均搜索長(zhǎng)度為〔〕.【答案】20.5在程序運(yùn)行過(guò)程中不能擴(kuò)充的數(shù)組是 〔〕分配的數(shù)組.這種數(shù)組在聲明它時(shí)必須指定它的大小.【答案】靜態(tài)設(shè)有程序段為for〔i=1;i<10;i++〕for〔j=1;j<=i;j++〕{p=i*j;printf〔"％4d n〞,p〕;}那么執(zhí)行p=i*j的次數(shù)為〔〕.【答案】45一棵高度為5的完全二叉樹(shù)中,最多包含有〔〕個(gè)結(jié)點(diǎn).假定樹(shù)根結(jié)點(diǎn)的高度為0.【答案】63第i〔i=1,2, ??-,n-1〕趟從參加排序的序列中取出第i個(gè)元素,把它插入到由第0個(gè)至第i-1個(gè)元素組成的有序表中適當(dāng)?shù)奈恢?此種排序方法叫做〔〕排序.【答案】直接插入設(shè)棧S和隊(duì)列Q的初始狀態(tài)為空,元素A,B,C,D,E,和F依次通過(guò)棧S,且一個(gè)元素出棧后即進(jìn)入隊(duì)列Q,假設(shè)6個(gè)元素出隊(duì)列的順序是B,D,C,F,E,A,那么棧S的容量至少是〔〕.【答案】3假設(shè)設(shè)串S='documentHash.doc\0〞,那么該字符串S的長(zhǎng)度為〔〕.【答案】16在對(duì)晰B樹(shù)插入元素的過(guò)程中,每向一個(gè)結(jié)點(diǎn)插入一個(gè)關(guān)鍵碼后,假設(shè)該結(jié)點(diǎn)的關(guān)鍵碼個(gè)數(shù)等于 〔〕個(gè),那么必須把它分裂為2個(gè)結(jié)點(diǎn).【答案】m棧是一種限定在表的一端進(jìn)行插入和刪除的線(xiàn)性表,又被稱(chēng)為 〔〕表.【答案】后出先進(jìn)在無(wú)向圖G勺鄰接矩陣表示中,第j列中非零元的個(gè)數(shù)等于該頂點(diǎn)的 〔〕.【答案】度在一個(gè)鏈?zhǔn)疥?duì)列中,假設(shè)隊(duì)頭指針與隊(duì)尾指針的值相同,那么表示該隊(duì)列至多有 〔〕個(gè)結(jié)點(diǎn).【答案】一假定一棵二叉樹(shù)的結(jié)點(diǎn)數(shù)為18,那么它的最小高度為〔〕.假定樹(shù)根結(jié)點(diǎn)的高度為0.【答案】4在單鏈表中,除了表頭結(jié)點(diǎn)外,任意結(jié)點(diǎn)的存儲(chǔ)位置由其直接〔〕結(jié)點(diǎn)的指針域的值所指示.【答案】前驅(qū)TOC\o"1-5"\h\z由分別帶權(quán)為9,6,2,5,7的五個(gè)葉子結(jié)點(diǎn)構(gòu)造的哈夫曼樹(shù)的帶權(quán)路徑長(zhǎng)度為 〔〕.【答案】65對(duì)長(zhǎng)度為20的有序表進(jìn)行二分查找的判定樹(shù)的高度為 〔〕.【答案】5快速排序在平均情況下的空間復(fù)雜度為 〔〕.【答案】O〔log2n〕在一個(gè)鏈?zhǔn)疥?duì)列中,假設(shè)隊(duì)頭指針與隊(duì)尾指針的值相同,那么表示該隊(duì)列至多有 〔〕個(gè)結(jié)點(diǎn).【答案】1隊(duì)列是一種限定在表的一端插入,在另一端刪除的線(xiàn)性表,它又被稱(chēng)為〔〕表.【答案】先進(jìn)先出當(dāng)用長(zhǎng)度為MaxSize的數(shù)組順序存儲(chǔ)一個(gè)棧時(shí),假設(shè)用top==MaxSize表示棧空,那么表示棧滿(mǎn)的條件為 〔〕.【答案】top==0假設(shè)進(jìn)棧序列為a,b,c,且進(jìn)棧和出?？梢源┎暹M(jìn)行,那么可能出現(xiàn) 〔〕個(gè)不同的出棧序列.【答案】5假設(shè)設(shè)一個(gè)n的矩陣A的開(kāi)始存儲(chǔ)地址LOC〔0,0〕及元素所占存儲(chǔ)單元數(shù)d,按行存儲(chǔ)時(shí)其任意一個(gè)矩陣元素 a[i][j] 的存儲(chǔ)地址為〔〕.【答案】LOC〔0,0〕+〔i*n+j〕*d如果n個(gè)頂點(diǎn)的圖是一個(gè)環(huán),那么它有〔〕棵生成樹(shù).【答案】n設(shè)有程序段為：for〔i=1;i<=10;i++〕for〔j=1;j<=i;j++〕p=i*j;那么執(zhí)行p=i*j的次數(shù)為〔〕.【答案】45在單鏈表中某X吉點(diǎn)后插入S吉點(diǎn)的操作是〔〕.【答案】s->next=p->next;p->next=s;以順序搜索方法從長(zhǎng)度為n的順序表或單鏈表中搜索一個(gè)元素的漸進(jìn)時(shí)間復(fù)雜度為 〔〕.【答案】O〔n〕在直接選擇排序中,記錄比擬次數(shù)的時(shí)間復(fù)雜度為 〔〕.【答案】O〔n2〕棧下溢是指在〔〕時(shí)進(jìn)行出棧操作.【答案】棧空在單鏈表設(shè)置表頭結(jié)點(diǎn)的作用是插入和刪除表中第一個(gè)元素時(shí)不必對(duì) 〔〕進(jìn)行特殊處理.【答案】表頭指針一維數(shù)組所占用的空間是連續(xù)的.但數(shù)組元素不一定順序存取,通常是按元素的 〔〕存取的.【答案】下標(biāo)〔或順序號(hào)〕利用三元組表存放稀疏矩陣中的非零元素,那么在三元組表中每個(gè)三元組元素對(duì)應(yīng)一個(gè)非零元素的行號(hào)、列號(hào)和〔〕.【答案】值克魯斯卡爾算法適用于求〔〕的網(wǎng)的最小生成樹(shù).【答案】邊稀疏用鏈表表示線(xiàn)性表,表中元素之間的邏輯關(guān)系是通過(guò)鏈表中結(jié)點(diǎn)的 〔〕來(lái)實(shí)現(xiàn)的.【答案】指針將一棵樹(shù)根據(jù)左子女-右兄弟表示法轉(zhuǎn)換成對(duì)應(yīng)的二叉樹(shù),那么該二叉樹(shù)中樹(shù)根結(jié)點(diǎn)肯定沒(méi)有 〔〕子女.【答案】右由帶權(quán)為9,6,2,5,7的五個(gè)葉子結(jié)點(diǎn)構(gòu)造的哈夫曼樹(shù),其根結(jié)點(diǎn)的權(quán)值為 〔〕.【答案】2911個(gè)頂點(diǎn)的連通網(wǎng)絡(luò)泄'10條邊,其中權(quán)值為1,2,3,4,5 的邊各2條,那么網(wǎng)絡(luò)N的最小生成樹(shù)各邊的權(quán)值之和為〔〕.【答案】30線(xiàn)性表是由n〔nA0〕個(gè)〔〕組成的有限序列.【答案】數(shù)據(jù)元素給定一組數(shù)據(jù)對(duì)象的關(guān)鍵碼為｛46,79,56,38,40,84〕,對(duì)其進(jìn)行一趟快速排序處理,得到的右子表中有〔〕個(gè)對(duì)象.【答案】3將一個(gè)n階對(duì)稱(chēng)矩陣的上三角局部或下三角局部壓縮存放于一個(gè)一維數(shù)組中,那么一維數(shù)組需要存儲(chǔ) 〔〕個(gè)矩陣元素.【答案】n〔n+1〕/2對(duì)于一棵具有n個(gè)結(jié)點(diǎn)的樹(shù),該樹(shù)中所有結(jié)點(diǎn)的度數(shù)之和為 〔〕.【答案】n-1在使用Kruskal算法構(gòu)造連通網(wǎng)絡(luò)的最小生成樹(shù)時(shí),只有當(dāng)一條候選邊的兩個(gè)端點(diǎn)不在同一個(gè) 〔〕上,才會(huì)被加入到生成樹(shù)中.【答案】連通分量設(shè)序列｛25,36,40,45,48,56,60,68,72,85〕 ,當(dāng)用折半查找方法查找36時(shí),所需比擬的次數(shù)為 〔〕.【答案】2哈希查找是通過(guò)〔〕來(lái)確定記錄的存儲(chǔ)地址的.【答案】哈希函數(shù)對(duì)n個(gè)數(shù)據(jù)對(duì)象進(jìn)行堆排序,總的時(shí)間復(fù)雜度為 〔〕.【答案】O〔nlog2n〕在線(xiàn)性表的散列存儲(chǔ)中,裝載因子 又稱(chēng)為裝載系數(shù),假設(shè)用誠(chéng)示散列表的長(zhǎng)度,n表示待散列存儲(chǔ)的元素的個(gè)數(shù),那么等于〔〕.【答案】n/m設(shè)圖的頂點(diǎn)數(shù)為n,那么求解最短路徑的Dijkstra算法的時(shí)間復(fù)雜度為〔〕.【答案】O〔n2〕一棵3階BW中含有50個(gè)關(guān)鍵碼,那么該樹(shù)的最大高度為〔〕.【答案】5從一棵二叉搜索樹(shù)中搜索一個(gè)元素時(shí),假設(shè)給定值大于根結(jié)點(diǎn)的值,那么需要向 〔〕繼續(xù)搜索.【答案】右子樹(shù)鏈接存儲(chǔ)表示的結(jié)點(diǎn)存儲(chǔ)空間一般在程序的運(yùn)行過(guò)程中進(jìn)行動(dòng)態(tài)地 〔〕和釋放.【答案】分配線(xiàn)性表的鏈接存儲(chǔ)只能通過(guò)〔〕順序訪問(wèn).【答案】鏈接指針直接插入排序在初始有序時(shí),進(jìn)行〔〕次關(guān)鍵字比擬.【答案】n-1假設(shè)將一棵樹(shù)A〔B〔C,D,E〕,F〔G〔H〕,I〕〕 根據(jù)左子女-右兄弟表示法轉(zhuǎn)換為二叉樹(shù),該二叉樹(shù)中度為 2的結(jié)點(diǎn)的個(gè)數(shù)為〔〕個(gè).【答案】2每次直接或通過(guò)基準(zhǔn)元素間接比擬兩個(gè)元素,假設(shè)出現(xiàn)逆序排列就交換它們的位置,這種排序方法叫做 〔〕排序.【答案】交換單鏈表中邏輯上相鄰的結(jié)點(diǎn)而在物理位置上 〔〕相鄰.【答案】不一定鏈表只適用于〔〕查找.【答案】順序在堆排序中,如果n個(gè)對(duì)象的初始堆已經(jīng)建好,那么到排序結(jié)束,還需要從堆頂結(jié)點(diǎn)出發(fā)調(diào)用 〔〕次調(diào)整算法.【答案】n-1向一個(gè)順序棧插入一個(gè)元素時(shí),首先使〔〕后移一個(gè)位置,然后把待插入元素寫(xiě)入到這個(gè)位置上.【答案】棧頂指針在帶表頭結(jié)點(diǎn)的單鏈表中刪除某一指定結(jié)點(diǎn),必須找到該結(jié)點(diǎn)的 〔〕結(jié)點(diǎn).【答案】前一個(gè)在一棵高度為3的四叉樹(shù)中,最多含有 〔〕個(gè)結(jié)點(diǎn),假定樹(shù)根結(jié)點(diǎn)的高度為 0.【答案】85在含有3個(gè)結(jié)點(diǎn)a,b,c的二叉樹(shù)中,前序序列為abc且后序序列為cba的二叉樹(shù)有〔〕棵.【答案】4設(shè)圖G=〔V,E〕,V={V0,V1,V2,V3〕,E=〔〔V0,V1〕,〔V0,V2〕,〔V0,V3〕,〔V1,V3〕〕 ,那么從頂點(diǎn)V0開(kāi)始的圖G的不同深度優(yōu)先序列有〔〕種.【答案】4在一般情況下用直接插入排序、選擇排序和冒泡排序的過(guò)程中,所需記錄交換次數(shù)最少的是 〔〕.【答案】選擇排序在鏈表的結(jié)點(diǎn)中,數(shù)據(jù)元素所占的存儲(chǔ)量和整個(gè)結(jié)點(diǎn)所占的存儲(chǔ)量之比稱(chēng)作 〔〕.【答案】存儲(chǔ)密度用鄰接矩陣存儲(chǔ)圖,占用的存儲(chǔ)空間與圖中的 〔〕數(shù)有關(guān).【答案】頂點(diǎn)對(duì)稱(chēng)矩陣的行數(shù)與列數(shù)〔〕且以主對(duì)角線(xiàn)為對(duì)稱(chēng)軸,aj=a.,因此只存儲(chǔ)它的上三角局部或下三角局部即可.【答案】相等在直接選擇排序中,記錄移動(dòng)次數(shù)的時(shí)間復(fù)雜度為 〔〕.【答案】O〔n〕對(duì)關(guān)鍵字序列〔15,18,11,13,19,16,12,17,10,8〕進(jìn)行增量為5的一趟希爾排序的結(jié)果為〔〕.【答案】〔15,12,11,10,8,16,18,17,13,19〕完全二叉樹(shù)有200個(gè)結(jié)點(diǎn),那么整個(gè)二叉樹(shù)有〔〕個(gè)度為1的結(jié)點(diǎn).【答案】1普里姆算法適用于求〔〕的網(wǎng)的最小生成樹(shù).【答案】邊稠密在一個(gè)堆的順序存儲(chǔ)中,假設(shè)一個(gè)元素的下標(biāo)為 i〔0<i<n-1〕,那么它的左子女元素的下標(biāo)為 〔〕.【答案】2i+1假設(shè)用鄰接矩陣表示有向圖,那么頂點(diǎn) i的入度等于矩陣中〔〕.【答案】所對(duì)應(yīng)列中的非零元素個(gè)數(shù)鏈隊(duì)列l(wèi)q為空的條件為〔〕.【答案】Lq->rear==lq.frontTOC\o"1-5"\h\z長(zhǎng)度為11的有序表進(jìn)行折半查找時(shí),在等查找概率情況下查找成功的平均查找長(zhǎng)度為 〔〕.【答案】3第i〔i=0,1,...,n-2〕 趟從參加排序的序列中第i個(gè)至第n-1個(gè)元素中挑選出一個(gè)最小元素,把它交換到第 i個(gè)位置,此種排序方法叫做〔〕排序.【答案】直接選擇快速排序在最壞情況下的時(shí)間復(fù)雜度為 〔〕.【答案】O〔n2〕由關(guān)鍵字序列｛36,96,84,18,52,27｝ 建成的最小堆是〔〕.【答案】〔18,36,27,96,52,84〕深度為10的完全二叉樹(shù),至少有〔〕個(gè)結(jié)點(diǎn).【答案】512在一棵二叉樹(shù)中,假定雙分支結(jié)點(diǎn)數(shù)為 5個(gè),單分支結(jié)點(diǎn)數(shù)為6個(gè),那么葉子結(jié)點(diǎn)數(shù)為 〔〕個(gè).【答案】6向一個(gè)棧頂指針為top的鏈?zhǔn)綏Ｖ胁迦胍粋€(gè)新結(jié)點(diǎn)*?時(shí),應(yīng)執(zhí)行〔〕和top=p操作.【答案】p->link=top假設(shè)用<x,y>表示樹(shù)的邊〔其中x是y的雙親〕,一棵樹(shù)的邊集為｛<b,d>,<a,b>,<c,g>,<c,f>,<c,h>,<a,c>｝,該樹(shù)的度是〔〕.【答案】3設(shè)待排序的表為〔42,55,12,47,94,06,18,63〕,利用快速排序方法對(duì)其進(jìn)行排序,經(jīng)第一趟排序后,表的狀態(tài)為〔〕.【答案】〔18,06,12,42,94,47,55,63〕估算算法時(shí)間復(fù)雜度時(shí)考慮的問(wèn)題規(guī)模通常是指算法求解問(wèn)題的 〔〕.【答案】輸入量在一棵三叉樹(shù)中,度為3的結(jié)點(diǎn)數(shù)有2個(gè),度為2的結(jié)點(diǎn)數(shù)有1個(gè),度為1的結(jié)點(diǎn)數(shù)為2個(gè),那么度為0的結(jié)點(diǎn)數(shù)有〔〕個(gè).【答案】6TOC\o"1-5"\h\zn〔n>0〕個(gè)頂點(diǎn)的連通無(wú)向圖各頂點(diǎn)的度之和最少為 〔〕.【答案】2〔n-1〕對(duì)n個(gè)元素的序列進(jìn)行冒泡排序時(shí), 〔〕情況下比擬次數(shù)最少,比擬次數(shù)為 〔〕.【答案】初始數(shù)據(jù)有序 n-1在程序運(yùn)行過(guò)程中可以擴(kuò)充的數(shù)組是 〔〕分配的數(shù)組.這種數(shù)組在聲明它時(shí)需要使用數(shù)組指針.【答案】動(dòng)態(tài)一棵3階醐中含有50個(gè)關(guān)鍵碼,那么該樹(shù)的最小高度為 〔〕.【答案】4僅允許在表的同一端進(jìn)行插入和刪除運(yùn)算的線(xiàn)性表被稱(chēng)為 〔〕.【答案】棧鏈表與順序表、索引表、散列表等都是數(shù)據(jù)邏輯結(jié)構(gòu)的 〔〕表示.【答案】存儲(chǔ)如果一個(gè)對(duì)象局部地包含自己,或自己定義自己,那么稱(chēng)這個(gè)對(duì)象是 〔〕的對(duì)象.【答案】遞歸在有向圖的鄰接表表示中,每個(gè)頂點(diǎn)鄰接表中所含的結(jié)點(diǎn)數(shù)等于該頂點(diǎn)的 〔〕.【答案】出度給定一組數(shù)據(jù)對(duì)象的關(guān)鍵碼為〔46,79,56,38,40,84〕,那么利用堆排序方法建立的初始堆〔最大堆〕為〔〕.【答案】〔84,79,56,38,40,46〕設(shè)關(guān)鍵字序列〔17,8,13,25,24,16,3 ,19,1〕,用希爾排序法按升序排序,用初始增量 4進(jìn)行一趟排序后的結(jié)果是〔〕.【答案】1,8,3,19,17,16,13,25,24設(shè)循環(huán)隊(duì)列用數(shù)組A[m]表示,隊(duì)頭、隊(duì)尾指針?lè)謩e是front和rear,那么判定隊(duì)滿(mǎn)的條件為〔〕.【答案】〔rear+1〕%M==front求解帶權(quán)連通圖最小生成樹(shù)的 Prim算法使用圖的〔〕作為存儲(chǔ)結(jié)構(gòu).【答案】鄰接矩陣在堆排序中,對(duì)n個(gè)記錄建立初始堆需要調(diào)用〔〕次調(diào)整算法.【答案】n/2一棵二叉樹(shù)的先根序列為ABDFCE,中根序列為DFBACE,那么后根序列為 〔〕.【答案】FDBECA用折半查找法查找一個(gè)線(xiàn)性表中的元素時(shí),此線(xiàn)性表必須是 〔〕.【答案】有序的在有向圖的鄰接矩陣表示中,第 j列元素之和等于第j個(gè)頂點(diǎn)的〔〕.【答案】入度在鏈表中進(jìn)行插入和〔〕操作的效率比在順序存儲(chǔ)結(jié)構(gòu)中進(jìn)行相同操作的效率高.【答案】刪除算法的一個(gè)特性是〔〕,即算法必須執(zhí)行有限步就結(jié)束.【答案】有窮性每次使兩個(gè)相鄰的有序表合并成一個(gè)有序表,這種排序方法叫做 〔〕排序.【答案】二路歸并向一個(gè)鏈?zhǔn)綏２迦胍粋€(gè)新結(jié)點(diǎn)時(shí),首先把棧頂指針的值賦給新結(jié)點(diǎn)的指針域,然后把新結(jié)點(diǎn)的存儲(chǔ)位置賦給〔〕.【答案】棧頂指針根據(jù)n個(gè)元素建立一棵二叉搜索樹(shù)的漸進(jìn)時(shí)間復(fù)雜度大致為 〔〕.【答案】O〔nlog2n〕抽象數(shù)據(jù)類(lèi)型的特點(diǎn)是〔〕、信息隱蔽、使用與實(shí)現(xiàn)別離.【答案】數(shù)據(jù)封裝在雙向循環(huán)鏈表中插入一個(gè)新的結(jié)點(diǎn)時(shí),應(yīng)修改〔〕個(gè)指針域的值.【答案】四在有向圖中,以頂點(diǎn)v為終點(diǎn)的邊的數(shù)目稱(chēng)為v的〔〕.【答案】入度將一個(gè)n階對(duì)稱(chēng)矩陣A的上三角局部按行壓縮存放于一個(gè)一維數(shù)組 B中,A[0][0]存放于B[0]中,那么A[I][J]在I<J時(shí)將存放于數(shù)組B的〔〕位置.【答案】〔2n-I-1〕*I/2+J如果某二叉樹(shù)的中根序列為vxuyzw,層次序列為uvwxyz,那么先根序列為〔〕.【答案】uvxwyz對(duì)用鄰接表表示的連通圖進(jìn)行深度或廣度優(yōu)先遍歷時(shí)的時(shí)間復(fù)雜度為 〔〕.【答案】O〔n+e〕下面程序段的時(shí)間復(fù)雜度是 〔〕.for〔i=1;i<n-1;i++〕{y=y+1;for〔j=1;j<〔2*n〕;j++〕x=x+1;}【答案】O〔n2〕由分別帶權(quán)為9,2,5,7的四個(gè)葉子結(jié)點(diǎn)構(gòu)造的哈夫曼樹(shù)的帶權(quán)路徑長(zhǎng)度為 〔〕.【答案】44向一個(gè)循環(huán)隊(duì)列中插入元素時(shí),需要首先移動(dòng) 〔〕指針,然后再向所指位置寫(xiě)入新元素.【答案】隊(duì)尾鏈表對(duì)于數(shù)據(jù)元素的插入和刪除不需要移動(dòng)結(jié)點(diǎn),只需要改變相應(yīng)結(jié)點(diǎn)的 〔〕的值.【答案】指針域有一個(gè)10階三角矩陣A,采用壓縮方式〔以行序?yàn)橹鞔鎯?chǔ)〕存儲(chǔ)在一維數(shù)組B中,假設(shè)A[1,1]存儲(chǔ)在B[1]中,那么A[5,8]存儲(chǔ)在B〔〕.【答案】38判斷題TOC\o"1-5"\h\z線(xiàn)性表的邏輯順序總是與其物理順序一致. 〔〕【答案】錯(cuò)線(xiàn)性表的順序存儲(chǔ)優(yōu)于鏈?zhǔn)酱鎯?chǔ). 〔〕【答案】錯(cuò)在長(zhǎng)度為n的順序表中,求第i個(gè)元素的直接前驅(qū)算法的時(shí)間復(fù)雜度為 0〔1〕.〔〕【答案】對(duì)假設(shè)一棵二叉樹(shù)中的結(jié)點(diǎn)均無(wú)右孩子,那么該二叉樹(shù)的中根遍歷和后根遍歷序列正好相反. 〔〕【答案】錯(cuò)順序表和一維數(shù)組一樣,都可以按下標(biāo)隨機(jī)〔或直接〕訪問(wèn).〔〕【答案】對(duì)內(nèi)部排序是指排序過(guò)程在內(nèi)存中進(jìn)行的排序. 〔〕【答案】對(duì)當(dāng)待排序序列初始有序時(shí),簡(jiǎn)單項(xiàng)選擇擇排序的時(shí)間復(fù)雜性為 O〔n〕.〔〕【答案】錯(cuò)用鄰接矩陣存儲(chǔ)一個(gè)圖時(shí),在不考慮壓縮存儲(chǔ)的情況下,所占用的存儲(chǔ)空間大小只與圖中的頂點(diǎn)個(gè)數(shù)有關(guān), 而與圖的邊數(shù)無(wú)關(guān).〔〕【答案】對(duì)任何一棵二叉樹(shù)的葉結(jié)點(diǎn)在三種遍歷中的相對(duì)次序是不變的. 〔 〕【答案】對(duì)假設(shè)將一批雜亂無(wú)章的數(shù)據(jù)按堆結(jié)構(gòu)組織起來(lái) ,那么堆中數(shù)據(jù)必然按從小到大的順序線(xiàn)性排列. 〔〕【答案】錯(cuò)如果采用如下方法定義一維字符數(shù)組：intmaxSize=30;char*a=newchar[maxSize];TOC\o"1-5"\h\z那么這種數(shù)組在程序執(zhí)行過(guò)程中不能擴(kuò)充. 〔〕【答案】錯(cuò)使用三元組表示稀疏矩陣中的非零元素能節(jié)省存儲(chǔ)空間. 〔〕【答案】對(duì)對(duì)稀疏矩陣進(jìn)行壓縮存儲(chǔ)是為了節(jié)省存儲(chǔ)空間. 〔〕【答案】對(duì)當(dāng)向一個(gè)最小堆插入一個(gè)具有最小值的元素時(shí),該元素需要逐層向上調(diào)整,直到被調(diào)整到堆頂位置為止. 〔〕【答案】對(duì)哈希查找法中解決沖突問(wèn)題的常用方法是除留余數(shù)法. 〔〕【答案】錯(cuò)對(duì)具有n個(gè)結(jié)點(diǎn)的堆進(jìn)行插入一個(gè)元素運(yùn)算的時(shí)間復(fù)雜度為O〔n〕.〔〕【答案】錯(cuò)堆排序是一種穩(wěn)定的排序算法.〔〕【答案】錯(cuò)如果有向圖中各個(gè)頂點(diǎn)的度都大于2,那么該圖中必有回路.〔〕【答案】錯(cuò)在一個(gè)順序存儲(chǔ)的循環(huán)隊(duì)列中,隊(duì)頭指針指向隊(duì)頭元素的后一個(gè)位置.〔〕【答案】錯(cuò)對(duì)平衡二叉樹(shù)進(jìn)行中根遍歷,可得到結(jié)點(diǎn)的有序排列. 〔〕【答案】對(duì)在一棵二叉樹(shù)中,假定每個(gè)結(jié)點(diǎn)只有左子女,沒(méi)有右子女,對(duì)它分別進(jìn)行前序遍歷和中根遍歷,那么具有相同的結(jié)果.〔〕【答案】錯(cuò)拓?fù)渑判蚴侵附Y(jié)點(diǎn)的值是有序排序的. 〔〕【答案】錯(cuò)在散列法中采取開(kāi)散列〔鏈地址〕法來(lái)解決沖突時(shí) ,其裝載因子的取值一定在〔0,1〕之間.〔〕【答案】錯(cuò)在一棵具有n個(gè)結(jié)點(diǎn)的線(xiàn)索二叉樹(shù)中,每個(gè)結(jié)點(diǎn)的指針域可能指向子女結(jié)點(diǎn), 也可能作為線(xiàn)索,使之指向某一種遍歷次序的前驅(qū)或后繼結(jié)點(diǎn),所有結(jié)點(diǎn)中作為線(xiàn)索使用的指針域共有 n個(gè).〔〕【答案】錯(cuò)TOC\o"1-5"\h\z圖的深度優(yōu)先搜索是一種典型的回溯搜索的例子,可以通過(guò)遞歸算法求解. 〔〕【答案】對(duì)對(duì)二叉排序樹(shù)進(jìn)行中根遍歷,可得到結(jié)點(diǎn)的有序排列. 〔〕【答案】對(duì)任何一棵二叉樹(shù)的葉結(jié)點(diǎn)在三種遍歷中的相對(duì)次序是不變的. 〔〕【答案】對(duì)邊數(shù)很少的稀疏圖,適宜用鄰接矩陣表示. 〔〕【答案】錯(cuò)二叉樹(shù)是一棵無(wú)序樹(shù).〔〕【答案】錯(cuò)對(duì)于一棵具有n個(gè)結(jié)點(diǎn),其高度為h的二叉樹(shù),進(jìn)行任一種次序遍歷的時(shí)間復(fù)雜度為 O〔n〕.〔〕【答案】對(duì)TOC\o"1-5"\h\z當(dāng)待排序序列初始有序時(shí),快速排序的時(shí)間復(fù)雜性為 O〔n〕.〔 〕【答案】錯(cuò)順序表的空間利用率高于鏈表. 〔〕【答案】對(duì)采用不同的遍歷方法,所得到的無(wú)向圖的生成樹(shù)是不同的. 〔〕【答案】對(duì)有回路的有向圖不能完成拓?fù)渑判? 〔〕【答案】對(duì)存在這樣的二叉樹(shù),對(duì)它采用任何次序的遍歷,結(jié)果相同. 〔〕【答案】對(duì)TOC\o"1-5"\h\z裝載因子是散列表的一個(gè)重要參數(shù),它反映了散列表的裝滿(mǎn)程度. 〔〕【答案】對(duì)算法分析的目的是找出數(shù)據(jù)結(jié)構(gòu)的合理性. 〔〕【答案】錯(cuò)單鏈表可以實(shí)現(xiàn)隨機(jī)存取.〔〕【答案】錯(cuò)邊數(shù)很多的稠密圖,適宜用鄰接矩陣表示. 〔〕【答案】對(duì)理想情況下哈希查找的等概率查找成功的平均查找長(zhǎng)度是 O〔1〕.〔〕【答案】對(duì)邊數(shù)很少的稀疏圖,適宜用鄰接表表示. 〔〕【答案】對(duì)對(duì)于同一組關(guān)鍵碼互不相同的記錄,假設(shè)生成二叉搜索樹(shù)時(shí)插入記錄的次序不同那么得到不同形態(tài)的二叉搜索樹(shù).〔〕【答案】對(duì)TOC\o"1-5"\h\z強(qiáng)連通分量是有向圖中的極大強(qiáng)連通子圖. 〔〕【答案】對(duì)哈希查找法中解決沖突問(wèn)題的常用方法是除留余數(shù)法. 〔 〕【答案】錯(cuò)順序查找法適用于存儲(chǔ)結(jié)構(gòu)為順序或鏈接存儲(chǔ)的線(xiàn)性表. 〔 〕【答案】對(duì)假設(shè)讓元素1,2,3依次進(jìn)棧,那么出棧次序1,3,2是不可能出現(xiàn)的情況. 〔〕【答案】錯(cuò)在線(xiàn)性鏈表中刪除中間的結(jié)點(diǎn)時(shí),只需將被刪結(jié)點(diǎn)釋放. 〔〕【答案】錯(cuò)線(xiàn)性表假設(shè)采用鏈?zhǔn)酱鎯?chǔ)表示,在刪除時(shí)不需要移動(dòng)元素.〔〕【答案】對(duì)對(duì)任何用頂點(diǎn)表示活動(dòng)的網(wǎng)絡(luò)〔AO㈣〕進(jìn)行拓?fù)渑判虻慕Y(jié)果都是唯一的. 〔〕【答案】錯(cuò)鄰接矩陣適用于稠密圖〔邊數(shù)接近于頂點(diǎn)數(shù)的平方〕,鄰接表適用于稀疏圖〔邊數(shù)遠(yuǎn)小于頂點(diǎn)數(shù)的平方〕.〔〕【答案】對(duì)TOC\o"1-5"\h\z算法和程序原那么上沒(méi)有區(qū)別,在討論數(shù)據(jù)結(jié)構(gòu)時(shí)二者是通用的. 〔〕【答案】錯(cuò)在一棵B樹(shù)中,所有葉結(jié)點(diǎn)都處在同一層上,所有葉結(jié)點(diǎn)中空指針數(shù)等于所有關(guān)鍵碼的總數(shù)加 1.〔〕【答案】對(duì)循環(huán)鏈表的結(jié)點(diǎn)與單鏈表的結(jié)點(diǎn)結(jié)構(gòu)完全相同,只是結(jié)點(diǎn)間的連接方式不同. 〔〕【答案】對(duì)能夠在鏈接存儲(chǔ)的有序表上進(jìn)行折半查找,其時(shí)間復(fù)雜度與在順序存儲(chǔ)的有序表上相同. 〔〕【答案】錯(cuò)在一棵二叉樹(shù)中,假定每個(gè)結(jié)點(diǎn)只有左子女,沒(méi)有右子女,對(duì)它分別進(jìn)行中序遍歷和后序遍歷,那么具有相同的結(jié)果.〔〕【答案】對(duì)一個(gè)無(wú)向連通圖的生成樹(shù)是圖的極小的連通子圖. 〔〕【答案】對(duì)對(duì)稀疏矩陣進(jìn)行壓縮存儲(chǔ)是為了節(jié)省存儲(chǔ)空間. 〔〕【答案】對(duì)快速排序的時(shí)間復(fù)雜性不受數(shù)據(jù)初始狀態(tài)影響,恒為 O〔nlog2n〕.〔〕【答案】錯(cuò)兩個(gè)棧共享一片連續(xù)內(nèi)存空間時(shí),為提升內(nèi)存利用率,減少溢出時(shí)機(jī),應(yīng)把兩個(gè)棧的棧底分別設(shè)在這片內(nèi)存空間的兩端.〔〕【答案】對(duì)TOC\o"1-5"\h\z只有用面向?qū)ο蟮挠?jì)算機(jī)語(yǔ)言才能描述數(shù)據(jù)結(jié)構(gòu)算法. 〔〕【答案】錯(cuò)如果無(wú)向圖中每個(gè)頂點(diǎn)的度都大于等于 2,那么該圖中必有回路.〔〕【答案】對(duì)順序存儲(chǔ)方式只適用于存儲(chǔ)線(xiàn)性表. 〔〕【答案】錯(cuò)假設(shè)一棵二叉樹(shù)中的結(jié)點(diǎn)均無(wú)右孩子,那么該二叉樹(shù)的中根遍歷和后根遍歷序列正好相同. 〔〕【答案】對(duì)鄰接表只能用于有向圖的存儲(chǔ),鄰接矩陣對(duì)于有向圖和無(wú)向圖的存儲(chǔ)都適用. 〔〕【答案】錯(cuò)完全二叉樹(shù)的某結(jié)點(diǎn)假設(shè)無(wú)左孩子,那么它必是葉結(jié)點(diǎn). 〔〕【答案】對(duì)在一棵二叉樹(shù)中,假定每個(gè)結(jié)點(diǎn)只有左子女,沒(méi)有右子女,對(duì)它分別進(jìn)行前序遍歷和后序遍歷,那么具有相同的結(jié)果.〔〕【答案】錯(cuò)折半查找所對(duì)應(yīng)的判定樹(shù),既是一棵二叉查找樹(shù),又是一棵理想平衡二叉樹(shù). 〔〕【答案】對(duì)存儲(chǔ)無(wú)向圖的鄰接矩陣是對(duì)稱(chēng)的,因此可以只存儲(chǔ)鄰接矩陣的下〔上〕三角局部. 〔〕【答案】對(duì)在對(duì)雙向循環(huán)鏈表做刪除一個(gè)結(jié)點(diǎn)操作時(shí),應(yīng)先將被刪除結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)鏈接好再執(zhí)行刪除結(jié)點(diǎn)操作.〔〕【答案】對(duì)在用單鏈表表示的鏈?zhǔn)疥?duì)列Q中,隊(duì)頭指針為Q->front,隊(duì)尾指針為Q->rear,那么隊(duì)空條件為Q->front==Q->rear.〔〕【答案】錯(cuò)TOC\o"1-5"\h\z對(duì)稀疏矩陣進(jìn)行壓縮存儲(chǔ)是為了便于進(jìn)行矩陣運(yùn)算. 〔〕【答案】錯(cuò)理想情況下哈希查找的等概率查找成功的平均查找長(zhǎng)度是 O〔1〕.〔 〕【答案】對(duì)在任意一棵二叉樹(shù)的前序序列和后序序列中,各葉子之間的相對(duì)次序關(guān)系都相同. 〔 〕【答案】對(duì)遞歸調(diào)用算法與相同功能的非遞歸算法相比,主要問(wèn)題在于重復(fù)計(jì)算太多,而且調(diào)用本身需要分配額外的空間和傳遞數(shù)據(jù)和限制,所以時(shí)間與空間開(kāi)銷(xiāo)通常都比擬大. 〔〕【答案】對(duì)采用不同的遍歷方法,所得到的無(wú)向圖的生成樹(shù)總是相同的. 〔 〕【答案】錯(cuò)TOC\o"1-5"\h\z對(duì)于同一組記錄,生成二叉搜索樹(shù)的形態(tài)與插入記錄的次序無(wú)關(guān). 〔〕【答案】錯(cuò)對(duì)一個(gè)有向圖進(jìn)行拓?fù)渑判?一定可以將圖的所有頂點(diǎn)按其關(guān)鍵碼大小排列到一個(gè)拓?fù)溆行虻男蛄兄? 〔〕【答案】錯(cuò)鏈?zhǔn)綏Ｅc順序棧相比,一個(gè)明顯的優(yōu)點(diǎn)是通常不會(huì)出現(xiàn)棧滿(mǎn)的情況. 〔〕【答案】對(duì)對(duì)于兩棵具有相同記錄集合而具有不同形態(tài)的二叉搜索樹(shù),按中序遍歷得到的結(jié)點(diǎn)序列是相同的. 〔〕【答案】對(duì)在用散列表存儲(chǔ)關(guān)鍵碼集合時(shí),可以用雙散列法尋找下一個(gè)空位置.在設(shè)計(jì)再散列函數(shù)時(shí),要求計(jì)算出的值與表的大/J、m互質(zhì).〔〕【答案】對(duì)邊數(shù)很少的稀疏圖,適宜用鄰接矩陣表示. 〔〕【答案】錯(cuò)遞歸的算法簡(jiǎn)單、易懂、容易編寫(xiě),而且執(zhí)行效率也高. 〔〕【答案】錯(cuò)如果采用如下方式定義一維字符數(shù)組：constintmaxSize=30;chara[maxSize];TOC\o"1-5"\h\z那么這種數(shù)組在程序執(zhí)行過(guò)程中不能擴(kuò)充. 〔〕【答案】對(duì)鏈隊(duì)列的出隊(duì)操作總是需要修改尾指針. 〔〕【答案】錯(cuò)棧和隊(duì)列都是順序存取的線(xiàn)性表,但它們對(duì)存取位置的限制不同. 〔〕【答案】對(duì)數(shù)據(jù)的邏輯結(jié)構(gòu)是指各數(shù)據(jù)元素之間的邏輯關(guān)系,是用戶(hù)根據(jù)應(yīng)用需要建立的.【答案】對(duì)直接選擇排序是一種穩(wěn)定的排序方法. 〔〕【答案】錯(cuò)當(dāng)從一個(gè)最小堆中刪除一個(gè)元素時(shí),需要把堆尾元素填補(bǔ)到堆頂位置,然后再按條件把它逐層向下調(diào)整,直到調(diào)整到適宜位置為止.〔〕【答案】對(duì)TOC\o"1-5"\h\z線(xiàn)性表的邏輯順序總是與其物理順序一致. 〔 〕【答案】錯(cuò)將f=1+1/2+1/3+ ???+1/n轉(zhuǎn)化為遞歸函數(shù)時(shí),遞歸局部為f〔n〕=f〔n-1〕+1/n ,遞歸結(jié)束條件為f〔1〕=1 .〔〕【答案】對(duì)對(duì)平衡二叉樹(shù)進(jìn)行中根遍歷,可得到結(jié)點(diǎn)的有序序列. 〔 〕【答案】對(duì)雙向循環(huán)鏈表的結(jié)點(diǎn)與單鏈表的結(jié)點(diǎn)結(jié)構(gòu)相同,只是結(jié)點(diǎn)間的連接方式不同. 〔〕【答案】錯(cuò)在順序表中,邏輯上相鄰的元素在物理位置上不一定相鄰. 〔〕【答案】錯(cuò)數(shù)組是一種靜態(tài)的存儲(chǔ)空間分配,就是說(shuō),在程序設(shè)計(jì)時(shí)必須預(yù)先定義數(shù)組的數(shù)據(jù)類(lèi)型和存儲(chǔ)空間大小,由編譯程序在編譯時(shí)進(jìn)行分配. 〔〕【答案】錯(cuò)線(xiàn)索二叉樹(shù)中的每個(gè)結(jié)點(diǎn)通常包含有5個(gè)數(shù)據(jù)成員.〔〕【答案】對(duì)對(duì)于一棵具有n個(gè)結(jié)點(diǎn),其高度為h的任何二叉樹(shù),進(jìn)行任一種次序遍歷的時(shí)間復(fù)雜度均為 0〔h〕.〔〕【答案】錯(cuò)TOC\o"1-5"\h\z當(dāng)輸入序列已經(jīng)根本有序時(shí),起泡排序需要比擬關(guān)鍵碼的次數(shù),比快速排序還要少. 〔〕【答案】對(duì)順序查找法適用于存儲(chǔ)結(jié)構(gòu)為順序或鏈接存儲(chǔ)的線(xiàn)性表. 〔〕【答案】對(duì)插入與刪除操作是數(shù)據(jù)結(jié)構(gòu)中最根本的兩種操作,因此這兩種操作在數(shù)組中也經(jīng)常被使用. 〔〕【答案】錯(cuò)哈夫曼樹(shù)是帶權(quán)路徑長(zhǎng)度最短的樹(shù),路徑上權(quán)值較大的結(jié)點(diǎn)離根較近. 〔〕【答案】對(duì)在一個(gè)有向圖中,所有頂點(diǎn)的入度之和等于所有頂點(diǎn)的出度之和. 〔〕【答案】對(duì)在用循環(huán)單鏈表表示的鏈?zhǔn)疥?duì)列中,可以不設(shè)隊(duì)頭指針,僅在鏈尾設(shè)置隊(duì)尾指針. 〔〕【答案】對(duì)向一棵醐插入關(guān)鍵碼的過(guò)程中,假設(shè)最終引起樹(shù)根結(jié)點(diǎn)的分裂,那么新樹(shù)比原樹(shù)的高度減少 1.〔〕【答案】錯(cuò)多維數(shù)組是一種復(fù)雜的數(shù)據(jù)結(jié)構(gòu),數(shù)組元素之間的關(guān)系既不是線(xiàn)性的也不是樹(shù)形的. 〔〕【答案】對(duì)在二叉排序樹(shù)中插入新結(jié)點(diǎn)時(shí),新結(jié)點(diǎn)總是作為葉子結(jié)點(diǎn)插入. 〔 〕【答案】對(duì)邊數(shù)很少的稀疏圖,適宜用鄰接表表示.〔 〕【答案】對(duì)鏈隊(duì)列的出隊(duì)操作總是需要修改尾指針. 〔 〕【答案】錯(cuò)在一棵二叉樹(shù)中,假定每個(gè)結(jié)點(diǎn)只有左子女,沒(méi)有右子女,對(duì)它分別進(jìn)行前序遍歷和按層遍歷,那么具有相同的結(jié)果. 〔〕【答案】對(duì)二叉樹(shù)中每個(gè)結(jié)點(diǎn)的兩棵子樹(shù)的高度差等于 1.〔〕【答案】錯(cuò)二叉樹(shù)中不存在度大于2的結(jié)點(diǎn),當(dāng)某個(gè)結(jié)點(diǎn)只有一棵子樹(shù)時(shí)無(wú)所謂左、右子樹(shù).〔〕【答案】錯(cuò)鏈隊(duì)列的出隊(duì)操作是不需要修改尾指針的. 〔〕【答案】錯(cuò)圖的廣度優(yōu)先搜索算法通常采用非遞歸算法求解. 〔〕【答案】對(duì)拓?fù)渑判蚴侵附Y(jié)點(diǎn)的值是有序排序的.〔〕【答案】錯(cuò)數(shù)據(jù)的邏輯結(jié)構(gòu)與數(shù)據(jù)元素本身的內(nèi)容和形式無(wú)關(guān).【答案】對(duì)在樹(shù)的存儲(chǔ)中,假設(shè)使每個(gè)結(jié)點(diǎn)帶有指向雙親結(jié)點(diǎn)的指針,這為在算法中尋找雙親結(jié)點(diǎn)帶來(lái)方便. 〔〕【答案】對(duì)二叉樹(shù)中每個(gè)結(jié)點(diǎn)的關(guān)鍵字值大于其左非空子樹(shù)〔假設(shè)存在的話(huà)〕所有結(jié)點(diǎn)的關(guān)鍵字值,且小于其右非空子樹(shù)〔假設(shè)存在的話(huà)〕所有結(jié)點(diǎn)的關(guān)鍵字值.〔〕【答案】錯(cuò)TOC\o"1-5"\h\z邊數(shù)很多的稠密圖,適宜用鄰接表表示. 〔〕【答案】錯(cuò)從一棵B樹(shù)刪除關(guān)鍵碼的過(guò)程中,假設(shè)最終引起樹(shù)根結(jié)點(diǎn)的合并,那么新樹(shù)比原樹(shù)的高度增加 1.〔〕【答案】錯(cuò)在索引順序結(jié)構(gòu)的搜索中,對(duì)索引表既可以采取順序搜索,也可以采用折半搜索. 〔〕【答案】對(duì)算法和程序都應(yīng)具有下面一些特征：有輸入,有輸出,確定性,有窮性,有效性. 〔〕【答案】錯(cuò)對(duì)一個(gè)連通圖進(jìn)行一次深度優(yōu)先搜索可以遍訪圖中的所有頂點(diǎn). 〔〕【答案】對(duì)對(duì)于一棵具有n個(gè)結(jié)點(diǎn)的任何二叉樹(shù),進(jìn)行前序、中序或后序的任一種次序遍歷的空間復(fù)雜度為 O〔log2n〕.〔〕【答案】錯(cuò)用字符數(shù)組存儲(chǔ)長(zhǎng)度為n的字符串,數(shù)組長(zhǎng)度至少為n+1o〔〕【答案】對(duì)TOC\o"1-5"\h\z線(xiàn)性表假設(shè)采用鏈?zhǔn)酱鎯?chǔ)表示時(shí),其存儲(chǔ)結(jié)點(diǎn)的地址可連續(xù)也可不連續(xù). 〔〕【答案】對(duì)在二叉排序樹(shù)中插入新結(jié)點(diǎn)時(shí),新結(jié)點(diǎn)總是作為葉子結(jié)點(diǎn)插入. 〔〕【答案】對(duì)在線(xiàn)索二叉樹(shù)中每個(gè)結(jié)點(diǎn)通過(guò)線(xiàn)索都可以直接找到它的前驅(qū)和后繼. 〔〕【答案】錯(cuò)進(jìn)行折半查找的表必須是順序存儲(chǔ)的有序表. 〔〕【答案】對(duì)在索引順序結(jié)構(gòu)上實(shí)施分塊搜索,在等概率情況下,其平均搜索長(zhǎng)度不僅與子表個(gè)數(shù)有關(guān),而且與每一個(gè)子表中的對(duì)象個(gè)數(shù)有關(guān).〔〕【答案】對(duì)圖中各個(gè)頂點(diǎn)的編號(hào)是人為的,不是它本身固有的,因此可以根據(jù)需要進(jìn)行改變. 〔〕【答案】對(duì)數(shù)據(jù)元素是數(shù)據(jù)的最小單位.【答案】錯(cuò)在長(zhǎng)度為n的順序表中,求第i個(gè)元素的直接前驅(qū)算法的時(shí)間復(fù)雜度為 0〔1〕.〔 〕【答案】對(duì)算法設(shè)計(jì)題1.設(shè)二叉樹(shù)bt采用二叉鏈表結(jié)構(gòu)存儲(chǔ).試設(shè)計(jì)一個(gè)算法輸出二叉樹(shù)中所有非葉子結(jié)點(diǎn),并求出非葉子結(jié)點(diǎn)的個(gè)數(shù).【答案】intcount=0;voidalgo2〔BTNode*bt〕｛if〔bt〕｛if〔bt->lchild||bt->rchild〕｛printf〔bt->data〕;count++;

algo2(bt->lchild);algo2(bt->rchild);))2.閱讀以下函數(shù)arrange()intarrange(inta[],int1,inth,intx){//1和h分別為數(shù)據(jù)區(qū)的下界和上界inti,j,t；i=1；j=h；while(i<j){while(i<j&&a[j]>=x)j-- ；while(i<j&&a[j]>=x)i++if(i<j){t=a[j]；a[j]=a[i]；a[i]=t；))if(a[i]<x) returni；elsereturni—1；)寫(xiě)出該函數(shù)的功能；寫(xiě)一個(gè)調(diào)用上述函數(shù)實(shí)現(xiàn)以下功能的算法：對(duì)一整型數(shù)組 b[n]中的元素進(jìn)行重新排列,將所有負(fù)數(shù)均調(diào)整到數(shù)組的低下標(biāo)端,將所有正數(shù)均調(diào)整到數(shù)組的高低標(biāo)端,假設(shè)有零值,那么置于兩者之間,并返回?cái)?shù)組中零元素的個(gè)數(shù).【答案】(1)該函數(shù)的功能是：調(diào)整整數(shù)數(shù)組 a[]中的元素并返回分界值i,使所有vx的元素均落在a[1..i]上,使所有>x的元素均落在a[i+1..h]上.(2)(2)intf(intb[],intn){intp,q;p=arrange(b,0,n—1,0)；q=arrange(b,p+1,n—1,1)；或intf(intb[],intn){intp,qp=arrange(b,0,n—1,1)；q=arrange(b,0,p,0)returnq—p； returnp—q；} )假設(shè)線(xiàn)性表以帶表頭結(jié)點(diǎn)的循環(huán)單鏈表表示.試設(shè)計(jì)一個(gè)算法,在線(xiàn)性表的第 k個(gè)元素前插入新元素y.假設(shè)表長(zhǎng)小于k,那么插在表尾.【答案】voidalgo1(LNode*h,intk,ElemTypey) {q=h;P=h->next;j=1;while(p!=h&&j<k){q=p;p=p->next;j++;}s=(LNode*)malloc(sizeof(Lnode));s->data=y;q->next=s;s->next=q;)二叉排序樹(shù)的類(lèi)型定義如下：typedefstructBSTNode(//二叉排序樹(shù)的結(jié)點(diǎn)結(jié)構(gòu)intdata;//數(shù)據(jù)域structBSTNode*lchild,*rchild;//左、右孩子指針)BSTNode,*BSTree;設(shè)計(jì)遞歸算法,統(tǒng)計(jì)一棵二叉排序樹(shù) T中值小于a的結(jié)點(diǎn)個(gè)數(shù).【答案】intf34(BSTreeroot)(intcount;BSTNode*p;p=root;if(p&&p->data<a)count++;f34(p->lchild);returncount;)設(shè)二叉樹(shù)T采用二叉鏈表結(jié)構(gòu)存儲(chǔ),試設(shè)計(jì)算法求出二叉樹(shù)中離根最近的第一個(gè)葉子結(jié)點(diǎn). (注：結(jié)點(diǎn)按從上往下,自左至右次序編號(hào))【答案】BTNode*Firstleaf(BTNode*bt)(InitQueue(Q);// 初始化隊(duì)列Qif(bt)(EnQueue(Q,bt);;while(!EmptyQueue(Q)){DeQueue(Q,p);if(!p->lchild