奧鵬東北師范大學(xué)2020年9月《數(shù)據(jù)結(jié)構(gòu)》考前練兵.doc

1、單選題L內(nèi)排序方法的穩(wěn)定性是指()。A.該排序算法不允許有相同的關(guān)鍵字記錄B.該排序算法允許有相同的關(guān)鍵字記錄C.平均時間為0(nlog2n )的排序方法D.以上都不對答案：D2.順序文件采用順序結(jié)構(gòu)實(shí)現(xiàn)文件的存儲,對大型的順序文件的少量修 改，要求重新復(fù)制整個文件，代價很高，采用()的方法可降低所需的 代價。A.附加文件B.按關(guān)鍵字大小排序C.按記錄輸入先后排序D.連續(xù)排序答案：A3 .在對n個元素的序列進(jìn)行排序時，堆排序所需要的附加存儲空間是 OoA. 0(log2n )B. 0( 1 )C. 0(n )D. 0(nlog2n )答案：B4 .在n個結(jié)點(diǎn)的線索二叉樹中線索的數(shù)目為()。A.

2、 nTB. nC. n+1D. 2n答案：C5,插入、刪除只能在同一端進(jìn)行的線性表，稱為（）。A.隊(duì)列B.循環(huán)隊(duì)列C.棧D.循環(huán)棧 答案：C6 .在下述幾種排序方法中，不穩(wěn)定的排序方法是（）。A.直接插入排序B.冒泡排序C.直接選擇排序D.歸并排序 答案：C7 .用DFS遍歷一個無環(huán)有向圖，并在DFS算法退棧返回時打印相應(yīng)的頂 點(diǎn)，則輸出的頂點(diǎn)序列是（）。A.逆拓?fù)溆行? .拓?fù)溆行駽.無序的D.部分有序的 答案：A8. AVL樹中任一結(jié)點(diǎn)的平衡因子的絕對值都應(yīng)小于等于（）。A. 0B. 1C. 2D. 3答案：B9 .數(shù)據(jù)結(jié)構(gòu)中的任一數(shù)據(jù)元素至多只有一個前驅(qū)和一個后繼，該數(shù)據(jù)結(jié)構(gòu)是（）A.線

3、性表B.廣義表C.樹形結(jié)構(gòu)D.圖結(jié)構(gòu) 答案：A10 .求圖的最?。ù鷥r）生成樹問題，考慮的是下面的哪一種圖（）。A.無向圖B.有向圖C.帶權(quán)的無向圖D.帶權(quán)的有向圖答案：C11 .設(shè)有n個結(jié)點(diǎn)的AVL樹，其平均查找長度為（）。A. 0 （ 1 ）B. 0 （log2n）C. 0 （n）D. 0 （nlog2n）答案：B12 .在下列排序算法中，哪一個算法的時間復(fù)雜度與記錄初始排列無關(guān)OoA.直接插入排序B.冒泡排序C.快速排序D.直接選擇排序答案：D13.由3個結(jié)點(diǎn)可以構(gòu)造出多少種不同形態(tài)的有向樹？（）A. 2B. 3C. 4D. 5答案：A14.對于3個結(jié)點(diǎn)a、b、c,可構(gòu)成不同的二叉樹的棵

4、數(shù)為（）。A. 24B. 28C. 30D. 32答案：C15.采用鄰接表存儲的圖的廣度優(yōu)先遍歷類似于二叉樹的()。A.前序遍歷B.中序遍歷C.后序遍歷D.層次遍歷答案：D16,設(shè)二維數(shù)組A0. m-1 0. n-1按行優(yōu)先順序存儲且每個元素占c 個單元，則元素的地址為()。A. L0C(A0 0) + (j*m+i)*cB. L0C(A0 0) + (i*n+j)*cC. L0C(A0 0) + (j-l)*m+i-l*cD. LOC (A0 0) + (i-l)*n+j-l*c答案：B17.若X是中序線索二叉樹中一個有左子女的結(jié)點(diǎn)，且X不為根，則X 的中序前驅(qū)為()。A. X的雙親B.X的

5、右子樹中最左下的結(jié)點(diǎn) C.X的左子樹中最右下的結(jié)點(diǎn)D. X的左子樹中最右下的葉結(jié)點(diǎn) 答案：C18.若由森林轉(zhuǎn)化得到的二叉樹是非空的二叉樹，則二叉樹形狀是()。A.根結(jié)點(diǎn)無右子樹的二叉樹B.根結(jié)點(diǎn)無左子樹的二叉樹C.根結(jié)點(diǎn)可能有左子樹和必有右子樹D.各結(jié)點(diǎn)只有一個子女的二叉樹 答案：C23.設(shè)有100個關(guān)鍵字,用折半查找法進(jìn)行查找時,最大比較次數(shù)為（）。19 .有n個頂點(diǎn)的無向連通圖的邊數(shù)最少為（）。A. n/2B. n-lC. nD. n+1答案：B20 .平衡的二叉排序樹（AVL樹）屬于（）的數(shù)據(jù)結(jié)構(gòu)。A.動態(tài)B.靜態(tài)C.線性D.無結(jié)構(gòu)答案：A21 .設(shè)有一個10階的對稱矩陣A,采用壓縮存儲

6、方式，以行序?yàn)橹鞔鎯? all為第一個元素，其存儲地址為100,每個元素占一個地址空間，則 a 85的地址為（）。A. 112B. 132C. 118D. 140答案：B22.在有向圖G的拓?fù)湫蛄兄?，若頂點(diǎn)Vi在Vj之前，則下列情形不可 能出現(xiàn)的是（）。A.G 中有弧VVi , Vj >B.G中有一條從Vi到Vj的路徑C.G中沒有弧VVi , Vj >D.G中有一條從Vj到Vi的路徑答案：DA. 6B. 7C. 25D. 50 答案：B24.數(shù)組A 6, 7的每個元素占5個字節(jié)，將其按列優(yōu)先次序存儲在起始地址為1000的內(nèi)存單元中，則元素A5,5的地址是（）。A. 1165B. 1

7、170C. 1175D.1180 答案：C25一個順序棧一旦被說明，其占用空間的大?。ǎ?。A.可以改變B.不能固定C.已固定D.動態(tài)變化答案：C26.設(shè)有2500個無序的記錄，希望以最快的速度挑選出其中前10個排 序碼最大的記錄，最好選用的排序方法是（）。A.直接插入排序B.堆排序C.冒泡排序 D.快速排序 答案：B27.求頂點(diǎn)間的最短路徑問題，考慮的是下面的哪一種圖（）。A.無向圖B.有向圖C.帶權(quán)的無向圖D.帶權(quán)的有向圖答案：D28.用折半查找法查找表的元素的速度比順序查找法（）。A.必定快B.必定慢C.相等D.不能確定答案：D29 . head指向的帶表頭結(jié)點(diǎn)的單鏈表為空的判定條件是（）

8、。A. head = = NULLB. head->next = = headC. head ! = NULLD.head->next = = NULL答案：D30 .下列序列中，（）是執(zhí)行第一趟按遞減序快速排序后所得的序列。A. 68,11 , 18 ,69 70 23 ,93, 73B. 68,11 , 69 ,23 70 18,93,73C. 93,73 70 68,11, 69, 23, 18 D. 68,11 , 69,23,18 70 93,73答案：C31 .四個元素進(jìn)入隊(duì)列QU的順序是U、V、X、Y,進(jìn)行DeQueue （QU, x） 操作后，隊(duì)頭元素是（）。A.U

9、B. VC.XD. Y答案：B32.若設(shè)根結(jié)點(diǎn)的層數(shù)為0,則具有37個結(jié)點(diǎn)的完全二叉樹的深度（或 高度）為（）。A. 4B. 5C. 6D. 7 答案：B33.在線索二叉樹中，p所指結(jié)點(diǎn)沒有左子樹的充要條件是（）。A.p->lchild = = NULLB.p->ltag = = 1C. p->ltag = = 1 且 p->lchild = = NULLD.p->ltag = = 0答案：B34.在查找過程中，僅進(jìn)行查找操作，沒有引起表本身的改動，這種查找則稱為（）。A.靜態(tài)查找B.動態(tài)查找C.內(nèi)查找D.外查找答案：A35.完全二叉樹是下列情況的哪一種（）oA.

10、 一定是滿二義樹B.可能是滿二義樹C. 一定不是滿二義樹D.不是二叉樹答案：B36.若有向圖的鄰接矩陣中，主對角線以下元素均為零，則該圖的拓?fù)?有序序列（）。A.存在B.不存在C.不一定存在D.可能不存在答案：A37.將一棵有100個結(jié)點(diǎn)的完全二叉樹從上到下、從左到右依次對結(jié)點(diǎn) 進(jìn)行編號,根結(jié)點(diǎn)的編號為1,則編號為49的結(jié)點(diǎn)的右子女編號為()。A. 48B. 50C. 98D. 99答案：D38.快速排序算法在下述哪種情況下效率最高()oA.被排序的數(shù)據(jù)已完全有序B.被排序的數(shù)據(jù)中含有多個相同的排序碼C.被排序的數(shù)據(jù)已基本有序D.被排序的數(shù)據(jù)完全無序答案：D39.任何一棵二叉樹的葉結(jié)點(diǎn)在前序、

11、中序和后序遍歷序列中的相對次 序()。A.不發(fā)生改變B.發(fā)生改變C.稍有改變D.不能確定答案：A40 .在一個圖中，所有頂點(diǎn)的度數(shù)之和等于圖的邊數(shù)的幾倍()。A. 1/2B. 1C. 2D. 4答案：C41 .下列排序算法中，在每一趟都能選出一個元素放到其最終位置上， 并且其時間性能受數(shù)據(jù)初始特性影響的是()。A.直接插入排序B ,快速排序C.直接選擇排序D.堆排序答案：B42 .一個棧的入棧序列是a、b、c,則棧的不可能的輸出序列是（）。A. acbB. abcC. bcaD. cab答案：D43 .遞歸過程的實(shí)現(xiàn)需用到（）。A.線性表B.鏈表C.棧D .隊(duì)列 答案：C44 .若X是中序線索

12、二叉樹中一個有右子女的結(jié)點(diǎn)，且X不為根，則X 的中序后繼為（）。A.X的雙親B.X的右子樹中最左下的結(jié)點(diǎn) C.X的左子樹中最右下的結(jié)點(diǎn)D. X的右子樹中最左下的葉結(jié)點(diǎn) 答案：B45 .順序查找法適合于存儲結(jié)構(gòu)為下列哪一種方式的線性表（）。A.散列存儲B.順序存儲或鏈接存儲C.壓縮存儲D .索引存儲 答案：B46 .廣義表運(yùn)算式tail ( ( ( a , b ) , ( c , d )的操作結(jié)果 是()。A. ( c , d )B. c , dc. ( ( c , d )D. d答案：C47 .設(shè)散列地址空間為。nrl, key為關(guān)鍵字，用p去除key,將得到 的余數(shù)作為key的散列地址，即h

13、(key) = key % p。為了減少發(fā)生沖 突的頻率，一般取p為()。A.小于等于m的最大奇數(shù) B.小于等于m的最大偶數(shù) C.小于等于m的最大素數(shù) D.小于等于m的最大合數(shù) 答案：C48 .有一個100*90的稀疏矩陣，非零元素有10個，設(shè)每個整型數(shù)占2字節(jié)，則用三元組表示該矩陣時，所需的字節(jié)數(shù)是()。A. 60B. 66C. 18000D. 33答案：A49.算法的計算量的大小稱為計算的。A.效率B.復(fù)雜性C.現(xiàn)實(shí)性D.難度答案：B50.在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成（）。A.動態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)B .緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu) C.線性結(jié)構(gòu)和非線性結(jié)構(gòu) D.內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu) 答案：

14、c5L head指向的非空的單循環(huán)鏈表的尾結(jié)點(diǎn)（由p所指向）滿足（）。A.p->next = = NULLB. p 二二 NULLC. p->next = = headD. p = = head 答案：C52.廣義表（a , b , c , d ）的表頭是（）。A. aB.()C. ( a , b , c , d )D. ( b , c , d )答案：c53 .在棧中存取數(shù)據(jù)的原則是()。A.先進(jìn)先出 B.后進(jìn)先出 C .后進(jìn)后出 D.隨意進(jìn)出 答案：B54 .在查找過程中，若同時還要做增、刪工作，這種查找則稱為（）。A.靜態(tài)查找B.動態(tài)查找C.內(nèi)查找D.外查找答案：B55,下列

15、排序算法中，其中（）是穩(wěn)定的。A.堆排序，起泡排序B.快速排序，堆排序C.歸并排序，起泡排序D.直接選擇排序，歸并排序 答案：C56 .對于二維數(shù)組A4 4,數(shù)組的起始位置LOC（A00）=1000,元素長度為 2,則 L0C（A33）為（）。A. 1000B.1010C. 1008 D.1020 答案：D57 .下列四個序列中，哪一個是堆（）。A. 75,65,30,B. 75,65,45,C. 75,45,65,D. 75,45,65,15 , 25 ,10 , 30 ,30 , 15 ,10 , 25 ,45 , 20 ,25 , 20 ,25 , 20 ,30 , 20 ,101510

16、15答案：C58 .如果BT是由有序樹T轉(zhuǎn)換而來的二叉樹,那么T中結(jié)點(diǎn)的后根序列 就是BT中結(jié)點(diǎn)的（）序列。A.前序B.中序C.后序D.層次次序 答案：B59. B+樹應(yīng)用在（）文件系統(tǒng)中。A. ISAMB. VSAMC.順序 D.散列 答案：B60 .設(shè)有n個結(jié)點(diǎn)的最佳二叉排序樹，對于成功的查找，最少的比較次 數(shù)為()。A. 0 ( 1 )B. 0 (log2n)C. 0 (n)D. 0 (nlog2n)答案：A61 .有m個葉結(jié)點(diǎn)的哈夫曼樹所具有的結(jié)點(diǎn)數(shù)為()。A. mB. m+1C. 2m- 1D. 2m答案：c62.對下列四種排序方法，在排序中關(guān)鍵字比較次數(shù)同記錄初始排列無 關(guān)的是()

17、oA.直接插入排序B.冒泡排序C.快速排序D.歸并排序答案：D63 .設(shè) si = "abc” , JBJ strlen(sl)=()。A. 0B. 1C. 2D. 3答案：D64 .已知一個順序存儲的線性表，設(shè)每個結(jié)點(diǎn)占c個單元，若第一個結(jié) 點(diǎn)的地址為LOC（aO）,則第i個結(jié)點(diǎn)的地址為（）。A. LOC(aO) + (i-l)*cB. LOC(aO)+i*cC. LOC(aO)-i*cD. LOC(aO) + (i+l)*c 答案：B65 .在下面的排序方法中，其比較次數(shù)與待排序記錄的初始排列狀態(tài)無 關(guān)的是（）。A.直接插入排序B.快速排序C.直接選擇排序D.歸并排序 答案：C6

18、6 . ISAM是索引順序存取方法，該方法是專為下面的哪一種設(shè)備設(shè)計的OoA.磁帶B.磁盤C.光盤D.外存儲器 答案：B67 .在下列情況中，可稱為二叉樹的是（）。A.每個結(jié)點(diǎn)至多有兩棵子樹的樹B.哈夫曼樹C.每個結(jié)點(diǎn)至多有兩棵子樹的有序樹D.每個結(jié)點(diǎn)只有一棵右子樹答案：B68 .稀疏矩陣常用的壓縮存儲方法有兩種，它們是（）。A.二維數(shù)組和三維數(shù)組B.三元組和散列C.三元組和十字鏈表D.散列和十字鏈表 答案：C69 .數(shù)據(jù)序列（8 , 9 , 10 , 4 , 5 , 6 , 20 , 1 , 2 ）只能是下列 排序算法中的（）的兩趟排序后的結(jié)果。A.直接選擇排序B.冒泡排序C.直接插入排序D

19、.堆排序 答案：C70 .下述二叉樹中，哪一種滿足性質(zhì)：從任一結(jié)點(diǎn)出發(fā)到根的路徑上所經(jīng)過的結(jié)點(diǎn)序列按其關(guān)鍵字有序。（）A.二義排序樹B.哈夫曼樹C. AVL 樹D.堆答案：D71 .在k叉樹中，無父母的結(jié)點(diǎn)稱為（）。A.根B.葉C.祖先D.子孫 答案：A72 .設(shè)根結(jié)點(diǎn)層次為1,某二叉樹的結(jié)點(diǎn)前序序列和后序序列正好相反, 則該二叉樹一定是（）。A.空或只有一個結(jié)點(diǎn) B.高度等于其結(jié)點(diǎn)數(shù)C .任一結(jié)點(diǎn)無左子女 D.任一結(jié)點(diǎn)無右子女 答案：B73 .折半查找要求結(jié)點(diǎn)（）。A .無序、順序存儲 B.無序、鏈接存儲 C .有序、順序存儲 D.有序、鏈接存儲 答案：c74 .下面關(guān)于串的敘述中，哪一個是

20、不正確的？（）A.串是字符的有限序列B ,空串是由空格構(gòu)成的申C.模式匹配是串的一種重要運(yùn)算D.吊既可以采用順序存儲，也可以采用鏈?zhǔn)酱鎯?答案：B75 .一個存儲結(jié)點(diǎn)存放一個。oA.數(shù)據(jù)項(xiàng)B.數(shù)據(jù)元素 C.數(shù)據(jù)結(jié)構(gòu) D.數(shù)據(jù)類型 答案：B76 .散列函數(shù)有一個共同的性質(zhì)，即函數(shù)值應(yīng)當(dāng)以下面的哪一項(xiàng)來取其值域的每個值（）。A.同等概率B.最大概率C.最小概率D.平均概率答案：A77.廣義表 A=(a, b, ( c, d ) , (e, ( f , g ),則式子 head (tail (head ( tail ( tail ( A )的值為()。A. ( g )B. ( d )C. cD. d

21、 答案：D78.從一個棧頂指針top的鏈棧中刪除一個結(jié)點(diǎn)時，用x保存被刪除的 元素，執(zhí)行（）。A. x = top; top = top->next;B.top = top->next; x = top->data;C.x = top->data;D.x = top->data; top = top->next;答案：D79 .下面的排序方法中，輔助空間為0（ n ）的是（）。A.希爾排序B.堆排序C.選擇排序 D,歸并排序 答案：D80 .倒排文件中倒排表是指（）。A.主關(guān)鍵字索引B.次關(guān)鍵字索引C.物理順序與邏輯順序不一致D.多關(guān)鍵字索引答案：B81 .

22、（）的遍歷仍需要棧的支持。A.前序線索二義樹 B.中序線索二叉樹 C .后序線索二叉樹D.前三種均需要 答案：C82 . head指向的不帶表頭結(jié)點(diǎn)的單鏈表為空的判定條件是（）。A. head = = NULLB.head->next = = headC. head ! = NULLD. head->next = = NULL答案：A83.二叉樹在線索化后，仍不能有效求解的問題是（）。A.前序線索二義樹中求前序后繼B.中序線索二義樹中求中序前驅(qū)C.中序線索二義樹中求中序后繼D.后序線索二義樹中求后序后繼答案：D84 .在下述幾種排序方法中，輔助空間需要最多的是（）。A.直接插入排序

23、B.快速排序C.直接選擇排序D.歸并排序答案：D85 .算法分析的兩個主要方面是（）oA.正確性與健壯性B.可讀性與可用性C.時間復(fù)雜度與空間復(fù)雜度D.數(shù)據(jù)復(fù)雜性與程序復(fù)雜性答案：C86.下列哪項(xiàng)不是利用查找表中數(shù)據(jù)元素的關(guān)系進(jìn)行查找的方法（）oA.有序表的查找B.二義排序樹的查找C. AVL 樹D.散列查找答案：D87.采用順序查找方法查找長度為n的線性表時，每個元素的平均查找 長度為（）。A. nB. （n-l）/2C. n/2D. （n+l）/2答案：D88.若要求盡可能快地對序列進(jìn)行穩(wěn)定的排序，則應(yīng)選（）。A.快速排序B.歸并排序C.起泡排序D.希爾排序答案：B89.某二叉樹結(jié)點(diǎn)的前序

24、序列為ECBAD,中序序列為EBCDA,則該二叉樹 結(jié)點(diǎn)的后序序列為（）。A. ABCEDB. DECABC. DEABCD. BDACE答案：D90.串是一種特殊的線性表，其特殊性體現(xiàn)在（）。A.可以順序存儲B.數(shù)據(jù)元素是一個字符C.可以鏈接存儲D.數(shù)據(jù)元素可以是多個字符 答案：B91.一個算法應(yīng)該是。A.程序B.問題求解步驟的描述C.要滿足五個基本特性D. A 和 C答案：BA.加快查找結(jié)點(diǎn)的前驅(qū)或后繼的速度B ,為了能方便地找到雙親C.為了能在二叉樹中方便地進(jìn)行插入與刪除D ,使二叉樹的遍歷結(jié)果唯一答案：A93 .在待排序的元素序列基本有序的前提下，效率最高的排序方法是0。A.直接插入排

25、序B.快速排序C.直接選擇排序D.歸并排序 答案：A94 .設(shè)有n個結(jié)點(diǎn)的二叉排序樹，對于成功的查找，最多的比較次數(shù)為OoA. 0 ( 1 )B. 0 (log2n)C. 0 (n)D. 0 (nlog2n)答案：C95 .判斷線索二叉樹中某結(jié)點(diǎn)p有右子女的條件是()。A.p->rtag = = 0B.p->rtag = = 1c.p ! = NULLD. p->lchild ! = NULL答案：A96 .設(shè)有兩個串si和s2,求s2在si中首次出現(xiàn)的位置的運(yùn)算稱為()oA.求子吊B .求串長C.聯(lián)接D.模式匹配 答案：D97 .一個隊(duì)列的入隊(duì)序列是a、b、c、d,則隊(duì)列的

26、輸出序列是（）。A. abedB. debaC. adebD. cbda答案：A98.分塊查找要求表中的結(jié)點(diǎn)（）。A.全部無序B.塊之間無序C.全部有序D.塊之間有序答案：D99.堆的形狀是一棵（）。A.二又排序樹B.滿二義樹C.完全二叉樹D. AVL 樹答案：C100.若設(shè)根結(jié)點(diǎn)的層數(shù)為0,則高（或深）度為4的二叉樹至多含有的結(jié) 點(diǎn)數(shù)為（）。A. 10B. 16C. 31D. 32答案：C10L二叉樹在中序線索化后，仍不能有效求解的問題是（）。A.求指定結(jié)點(diǎn)的前序后繼B.求指定結(jié)點(diǎn)的中序前驅(qū)C.求指定結(jié)點(diǎn)的中序后繼D.求指定結(jié)點(diǎn)的后序后繼答案：D102 .在隊(duì)列中存取數(shù)據(jù)的原則是（）。A.先

27、進(jìn)先出 B.后進(jìn)先出 C.先進(jìn)后出 D ,隨意進(jìn)出 答案：A103 .存放在外存中的數(shù)據(jù)的組織結(jié)構(gòu)是（）。A.數(shù)組B.表C.文件D.鏈表答案：C104 .靜態(tài)鏈表中的指針表示的是（）。A.內(nèi)存地址B.數(shù)組下標(biāo)C.下一元素地址D.左、右子女地址 答案：B105 .在一個單鏈表中，在p所指結(jié)點(diǎn)之后插入s所指結(jié)點(diǎn)，則執(zhí)行（）oA.s->next = p; p->next = s;1.5- >next = p->next; p->next = s;C. s->next = p->next; p = s;D. p->next = s; s->next

28、 = p->next; 答案：B106 .在下面的敘述中，正確的是（）。A .樹的先根遍歷序列與其對應(yīng)的二義樹的前序遍歷序列相同 B .樹的先根遍歷序列與其對應(yīng)的二義樹的中序遍歷序列相同 C .樹的先根遍歷序列與其對應(yīng)的二義樹的后序遍歷序列相同 D .樹的后根遍歷序列與其對應(yīng)的二義樹的后序遍歷序列相同答案：A107 . 一棵左子樹為空的二叉樹在前序線索化后，其中空的鏈域的個數(shù) 是：()A.不確定B. 0C. 1D. 2答案：D108.下列排序方法中，哪一個是穩(wěn)定的排序方法？()A.直接選擇排序B.直接插入排序C.希爾排序D.快速排序答案：B109 .一個有n個結(jié)點(diǎn)的圖，連通分量的個數(shù)最多

29、為()。A. 0B. 1C. nTD. n答案：D110 .線性表若采用鏈?zhǔn)酱鎯Y(jié)構(gòu)時，要求內(nèi)存中可用存儲單元的地址 ()。A.必須是連續(xù)的B.部分地址必須是連續(xù)的C. 一定是不連續(xù)的D.連續(xù)或不連續(xù)都可以答案：D11L “堆積”問題是由于()引起的。A.同義詞之間發(fā)生沖突B.散列函數(shù)C.不同的同義詞子表結(jié)合在一起D.散列表“溢出”答案：C112.在索引順序文件中，（）。A .主文件是無序的 B.主文件是有序的 C.不適宜隨機(jī)查找 D.索引是稠密索引 答案：B113.設(shè)根結(jié)點(diǎn)的層數(shù)為0,若高度為h的二叉樹上只有度為0和度為2 的結(jié)點(diǎn)，則此二叉樹上所包含的結(jié)點(diǎn)數(shù)至少為（）。A. h+1B.2h-

30、lC. 2hD. 2h+l 答案：D114.下列描述中正確的是（）oA.線性表的邏輯順序與存儲順序總是一致的B.每種數(shù)據(jù)結(jié)構(gòu)都具備查找、插入和刪除三種基本運(yùn)算C.數(shù)據(jù)結(jié)構(gòu)實(shí)質(zhì)上包括邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)兩方面的內(nèi)容D.選擇合適的數(shù)據(jù)結(jié)構(gòu)是解決應(yīng)用問題的關(guān)鍵步驟 答案：D115.在具有n個結(jié)點(diǎn)的完全二叉樹中，若設(shè)根結(jié)點(diǎn)的編號為1,則編號 為i（i>l）的結(jié)點(diǎn)的雙親結(jié)點(diǎn)的編號是（）。A. 2iB. 2i+l116 .線索二叉樹是一種（）結(jié)構(gòu)。A.邏輯B.物理C.邏輯和存儲D.線性答案：B117 .下面哪些方法可以判斷出一個有向圖是否有環(huán)（回路）？（）A.廣（寬）度優(yōu)先遍歷B.拓?fù)渑判駽.求最短路

31、徑D.求關(guān)鍵路徑 答案：B118 .判斷線索二叉樹中某結(jié)點(diǎn)p有左子女的條件是（）。A.p ! = NULLB.p->lchild != NULLC.p->ltag = = 0D.p->ltag = = 1答案：c119 .每一個（存儲）結(jié)點(diǎn)不僅含有一個數(shù)據(jù)元素，還包含一組指針，該存 儲方式是（）。A.順序存儲 B.鏈接存儲 C.索引存儲 D.散列存儲 答案：B120 .散列文件使用哈希函數(shù)將記錄的關(guān)鍵字值計算轉(zhuǎn)化為記錄的存儲 地址，因?yàn)楣：瘮?shù)是一對一的關(guān)系，則選擇好的0方法是散列文件 的關(guān)鍵。A.哈希函數(shù)B.除余法中的質(zhì)數(shù)C.沖突處理D.哈希函數(shù)和沖突處理 答案：D121.

32、非線性結(jié)構(gòu)的邏輯特征是一個結(jié)構(gòu)可能有（）。A. 一個前驅(qū)和一個后繼B.多個前驅(qū)和一個后繼C. 一個前驅(qū)和多個后繼D.多個前驅(qū)和多個后繼答案：D122.在鏈隊(duì)列中，假設(shè)f和r分別為隊(duì)首和隊(duì)尾指針，則刪除一個結(jié)點(diǎn) 的操作是（）。A. r = f->next;B.r = r->next;C.f = f->next;D.f = r->next;答案：c123.單鏈表的存儲密度（）。A.大于1B.等于1C.小于1D.不能確定答案：C124.最佳二叉排序樹屬于（）的數(shù)據(jù)結(jié)構(gòu)。A.動態(tài)B.靜態(tài)C.線性 D.無結(jié)構(gòu) 答案：BA.圖的遍歷是從給定的源點(diǎn)出發(fā)每個頂點(diǎn)僅被訪問一次B.遍歷的基

33、本方法有兩種：深度優(yōu)先遍歷和廣度優(yōu)先遍歷C.圖的深度優(yōu)先遍歷不適用于有向圖D.圖的深度優(yōu)先遍歷是一個遞歸過程答案：C126. 一棵左右子樹均不空的二叉樹在前序線索化后，其中空的鏈域的個 數(shù)是：()。A.不確定B. 0C. 1D. 2答案：C127.一個有向無環(huán)圖的拓?fù)渑判蛐蛄?)是唯一的。A. 一定B.不一定C.可能D.三者均不對答案：B128.假定有k個關(guān)鍵字互為同義詞，若采用線性探查法把這k個關(guān)鍵字存入散列表中，至少需要進(jìn)行多少次探測？。A. k-1 次B.k次C. k+1 次D.k(k+l)/2 次答案：D129.若由樹轉(zhuǎn)化得到的二叉樹是非空的二叉樹，則二叉樹形狀是()。A.根結(jié)點(diǎn)無右子

34、樹的二叉樹B.根結(jié)點(diǎn)無左子樹的二叉樹C.根結(jié)點(diǎn)可能有左子樹和右子樹 D.各結(jié)點(diǎn)只有一個子女的二叉樹 答案：A125.下列說法不正確的是（）。130.將一個A 1. 100, 1. 100的三對角矩陣，按行優(yōu)先次序存入一 維數(shù)組B1L.298中,A中元素A 66, 65在數(shù)組B中的位置K為（）。A. 193B. 195C. 197D. 199答案：B131.若一組記錄的排序碼為 46,79,56,38,40,84 ,則利用堆排序的 方法建立的初始堆為（）。A. 79, 46, 56, 38, 40, 84B. 84, 79, 56, 38, 40, 46C. 84, 79, 56, 46, 40

35、, 38D. 84, 56, 79, 40, 46, 38答案：B132.順序表中邏輯上相鄰的結(jié)點(diǎn)其物理位置也（）。A. 一定相鄰B.不必相鄰C.按某種規(guī)律排列D.無要求答案：A133.某二叉樹結(jié)點(diǎn)的中序序列為DGBAECHF,后序序列為GDBEHFCA,則 該二叉樹結(jié)點(diǎn)的前序序列為（）。A. AHFECGDBB. AHFCEBDGC. ABDGCEFHD. BDGAECHF答案：C134 .下列哪一種圖的鄰接矩陣是對稱矩陣？（）A.有向圖B.無向圖C. AOV 網(wǎng)D. AOE 網(wǎng) 答案：B135.n個結(jié)點(diǎn)的線索二叉樹上含有的線索數(shù)為（）。A. nTB. nC. n +1D. 2n 答案：c1

36、36.下述文件中適合于磁帶存儲的是（）。A.順序文件B.索引文件C.散列文件D.多關(guān)鍵字文件答案：A137.如果要求一個線性表既能較快地查找、又能適應(yīng)動態(tài)變化的要求,則可采用的查找方法是（）。A.順序查找B.折半查找C.分塊查找D.基于屬性的查找答案：C138 .在排序方法中，從未排序序列中挑選記錄，并將其依次放入已排序 序列（初始時為空）的一端的方法，稱為（）。A.希爾排序 B.插入排序 C.歸并排序 D.選擇排序 答案：D139 .在一個單鏈表中，已知q所指結(jié)點(diǎn)是p所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，若在P之前插入s所指結(jié)點(diǎn)，則執(zhí)行()。A.p->next = s; s->next = q;1

37、.5- >next = p->next; p->next = s;C. p->next = s->next; s->next = p;D. q->next = s; s->next = p;答案：D140.樹最適合用來表示()。A.有序數(shù)據(jù)元素B.無序數(shù)據(jù)元素C.元素之間具有分支層次關(guān)系的數(shù)據(jù)D.元素之間無聯(lián)系的數(shù)據(jù)答案：C14L下面關(guān)于算法說法錯誤的是O。A.算法最終必須由計算機(jī)程序?qū)崿F(xiàn)B .為解決某問題的算法同為該問題編寫的程序含義是相同的C.算法的可行性是指指令不能有二義性D.以上兒個都是錯誤的答案：D142.有n個頂點(diǎn)的有向圖的邊數(shù)最多為

38、()。A. nB. n(n-l)C. n(n-l)/2D. 2n答案：B143. 一個棧的入棧序列是a、b、c、d,則棧的不可能的輸出序列是()oA. acbdB. abedC. dbeaD. adeb答案：c144 .排序趟數(shù)與序列的原始狀態(tài)有關(guān)的排序方法是（）排序法。A.直接插入B.直接選擇C.冒泡D.歸并 答案：C145 .有n個頂點(diǎn)的無向圖的邊數(shù)最多為（）。A. nB. n（n-l）C. n（n-l）/2D. 2n答案：C146.對關(guān)鍵碼序列28 , 16 , 32, 12, 60, 2, 5, 72快速排序（從小到大序），一次劃分的結(jié)果為（）。A. ( 2 , 5 ,B. ( 5 ,

39、 16 , C. ( 2 , 16 , D. ( 5 , 16 , 答案：B12 , 16 )28 ( 60 ,28 ( 60 ,28 ( 60 ,28 ( 32 ,32 ,32 ,32 ,60 ,72 )72 )72 )72 )147.下面說法不正確的是（）。A.廣義表的表頭總是一個廣義表B.廣義表的表尾總是一個廣義表C.廣義表常采用鏈接存儲結(jié)構(gòu)D.廣義表可以是一個多層次的結(jié)構(gòu) 答案：A148 .用ISAM組織文件適合于（）oA.磁帶B.磁盤C .光盤D.外存儲器 答案：B149 .在k叉樹中，結(jié)點(diǎn)度數(shù)的最大值為（）。A. k-1B. kC. k+1D. k*n 答案：B150.若對n階對稱

40、矩陣A按行優(yōu)先順序?qū)⑵湎氯切蔚脑兀òㄖ鲗?角線上的所有元素）依次存放于一維數(shù)組B l.n（n+l）/2 中，則在 B中確定aij （ i < j）的位置k的關(guān)系為（）。A. i*(i-l)/2+jB. j*(j-l)/2+iC. i*(i+l)/2+jD. j*(j+l)/2+i 答案：B判斷題1 .在二叉樹中插入結(jié)點(diǎn)，則此二叉樹便不再是二叉樹了。A.錯誤B.正確答案：A2 .采用二叉鏈表作為存儲結(jié)構(gòu)，樹的先根遍歷和其相應(yīng)的二叉樹的前序 遍歷的結(jié)果是一樣的。3 .樹（森林）的結(jié)點(diǎn)的先根遍歷和后根遍歷分別與它相應(yīng)二又樹的結(jié)點(diǎn) 前序遍歷和后序遍歷是一致的。A.錯誤B.正確 答案：A4

41、.哈希表（散列表）的結(jié)點(diǎn)中只包含數(shù)據(jù)元素自身的信息，不包含任何指 針。A.錯誤B.正確答案：A5 .結(jié)構(gòu)的存儲密度定義為數(shù)據(jù)本身所占的存儲量與整個結(jié)構(gòu)所占的存 儲量之比。A.錯誤B.正確答案：B6 .無向圖的鄰接矩陣一定是對稱矩陣,有向圖的鄰接矩陣一定是非對稱 矩陣。A.錯誤B.正確答案：A7 .在有向圖中，度為0的頂點(diǎn)稱為終端頂點(diǎn)（或葉子）。8 .倒排文件的優(yōu)點(diǎn)是維護(hù)簡單。A .錯誤B.正確答案：BA .錯誤B.正確答案：A9 .倒排文件是對次關(guān)鍵字建立索引oA .錯誤 B.正確 答案：B10 .二叉樹的中序遍歷序列中，任意一個結(jié)點(diǎn)均處在其右子女結(jié)點(diǎn)（若 存在）的前面。A.錯誤 B.正確 答

42、案：B11 .二叉樹是度為2的有序樹。A .錯誤 B.正確 答案：A12 .廣義表的同級元素（直屬于同一個表中的各元素）具有線性關(guān)系。A .錯誤 B.正確 答案：B13 .分塊查找在等概率查找情況下，其平均查找長度不僅與表中元素個數(shù)有關(guān)，而且與每塊中的元素個數(shù)有關(guān)。14 .二叉排序樹刪除一個結(jié)點(diǎn)后，仍是二叉排序樹。A.錯誤B.正確答案：BA .錯誤B.正確答案：A15 .中序線索二叉樹的優(yōu)點(diǎn)是便于在中序下查找前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)oA .錯誤 B.正確 答案：B16 .任何無向圖都存在生成樹。A .錯誤B.正確答案：A17 .最佳二叉排序樹是靜態(tài)的，而平衡二叉排序樹（AVL樹）是動態(tài)的。A.錯誤B

43、.正確答案：B18 .排序的穩(wěn)定性是指排序算法中的比較次數(shù)保持不變，且算法能夠終 止。A .錯誤 B.正確 答案：A19 .對有序的單鏈表可以進(jìn)行折半查找。A.錯誤B.正確 答案：A20 .無向圖的鄰接矩陣可用一維數(shù)組存儲。21 .數(shù)組不適合作為任何二叉樹的存儲結(jié)構(gòu)。A .錯誤 B.正確 答案：A22 .拓?fù)渑判蛩惴▋H適用于有向無環(huán)圖。A .錯誤B.正確答案：A23 .對n個記錄的文件進(jìn)行堆排序，最壞情況下的執(zhí)行時間是0（nlog2n ）。A.錯誤B.正確答案：B24 .有向圖的鄰接矩陣是對稱的。A .錯誤 B.正確 答案：A25 .在平衡的二叉排序樹中，向某個平衡因子不為零的結(jié)點(diǎn)的樹中插入一

44、新結(jié)點(diǎn)，必引起平衡旋轉(zhuǎn)。A.錯誤B.正確答案：A26 .數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)的各數(shù)據(jù)項(xiàng)之間的邏輯關(guān)系。27 .廣義表的取表尾運(yùn)算，其結(jié)果通常是一個表，但有時也可是一個單元素值。A.錯誤B.正確答案：A28 .空串與空格串是相同的。A.錯誤 B.正確 答案：A29 .通常使用隊(duì)列來處理函數(shù)或過程的調(diào)用。A .錯誤 B.正確 答案：A30 .廣義表的取表尾運(yùn)算，其結(jié)果仍是一個廣義表。A .錯誤 B.正確 答案：B31 .所謂取廣義表的表尾就是返回廣義表中最后一個元素。A.錯誤B.正確 答案：A32 .對無序表用折半查找比順序查找快。A .錯誤B.正確答案：A33 .循環(huán)隊(duì)列也存在空間溢出問題。A

45、 .錯誤 B.正確 答案：B34 .二叉樹的葉結(jié)點(diǎn)，在前序遍歷、中序遍歷和后序遍歷下皆以相同的 相對位置出現(xiàn)。A.錯誤 B.正確 答案：B35 .倒排文件與多重表文件的次關(guān)鍵字索引結(jié)構(gòu)是不同的。A .錯誤 B.正確 答案：B36 .文件是記錄的集合，每個記錄由一個或多個數(shù)據(jù)項(xiàng)組成，因而一個文件可看作由多個記錄組成的數(shù)據(jù)結(jié)構(gòu)。A.錯誤B.正確答案：B37 .為了方便的插入和刪除數(shù)據(jù)，可以使用雙向鏈表來存放數(shù)據(jù)。A.錯誤B.正確答案：B38 .二叉樹按某種次序線索化后，任一結(jié)點(diǎn)均有指向其前序結(jié)點(diǎn)和后繼 結(jié)點(diǎn)的線索。A.錯誤B.正確答案：A39 .當(dāng)一棵具有m個葉結(jié)點(diǎn)的二叉樹的WPL值為最小時，稱其

46、樹為Huffman樹，且其二叉樹的形狀必是唯一的。A.錯誤B.正確答案：A40 .若一個廣義表的表頭為空表，則此廣義表亦為空表。A.錯誤B.正確答案：A41 .二叉樹的前序遍歷序列中，任意一個結(jié)點(diǎn)均處在其子女結(jié)點(diǎn)（若存 在）的前面。A.錯誤B.正確 答案：B42 .數(shù)據(jù)的邏輯結(jié)構(gòu)說明數(shù)據(jù)元素之間的順序關(guān)系，它依賴于計算機(jī)的 存儲結(jié)構(gòu)。43 .棧和隊(duì)列都是限制存取點(diǎn)的線性結(jié)構(gòu)。A.錯誤B.正確答案：AA .錯誤B.正確 答案：B44 .從邏輯結(jié)構(gòu)上看，n維數(shù)組的每個元素均屬于n個向量。A .錯誤 B.正確 答案：B45 .對于任何數(shù)據(jù)結(jié)構(gòu)，鏈接存儲結(jié)構(gòu)一定優(yōu)于順序存儲結(jié)構(gòu)。A .錯誤B.正確答案

47、：A46 . AOV網(wǎng)的含義是以頂點(diǎn)表示活動的網(wǎng)。A.錯誤B.正確答案：B47 .順序存儲方式只能用于存儲線性結(jié)構(gòu)。A .錯誤B.正確答案：A48 .快速排序總比簡單的排序方法快。A .錯誤 B.正確 答案：A49 .二叉樹的前序遍歷并不能唯一確定這棵樹形，但是，如果還知道該 樹的根結(jié)點(diǎn)是哪一個，則可以確定這棵二叉樹。A .錯誤B.正確 答案：A50 .若一個有向圖的鄰接矩陣對角線以下的元素均為零，則該圖的拓?fù)?有序序列必定存在。A.錯誤B.正確 答案：B51 .最小生成樹問題是構(gòu)造帶權(quán)連通圖（網(wǎng)）的最小代價生成樹。A.錯誤 B.正確 答案：B52 .順序存儲結(jié)構(gòu)的主要缺點(diǎn)是不利于插入、刪除操

48、作。A .錯誤 B.正確 答案：B53 . ( 101, 88, 46, 70, 34, 39, 45, 58, 66, 10)是堆。A .錯誤 B.正確 答案：B54 .有向圖中頂點(diǎn)Vi的度等于其鄰接矩陣?yán)锏趇行中的1的個數(shù)。A.錯誤B.正確 答案：A55 .二叉樹的后序遍歷序列中，任意一個結(jié)點(diǎn)均處在其子女結(jié)點(diǎn)（若存 在）的后面。A .錯誤B.正確答案：A56 .空串是由空格構(gòu)成的串。A.錯誤B.正確答案：A57 .兩個串相等的充分必要條件是兩個串的長度相等且對應(yīng)位置的字符 相同。A.錯誤B.正確答案：B58,有n個頂點(diǎn)的無向圖，采用鄰接矩陣表示，圖中的邊數(shù)等于鄰接矩 陣中非零元素之和。A.

49、錯誤B.正確答案：A59 .需要借助于一個棧來實(shí)現(xiàn)DFS算法。A.錯誤B.正確答案：B60 .鏈表中的表頭結(jié)點(diǎn)使得插入、刪除操作簡單。A.錯誤B.正確答案：B61 .對于查找運(yùn)算來說，鏈接存儲結(jié)構(gòu)一定優(yōu)于順序存儲結(jié)構(gòu)。62 .二叉樹中除葉結(jié)點(diǎn)外，任一結(jié)點(diǎn)X ,其左子樹根結(jié)點(diǎn)的值小于該結(jié) 點(diǎn)X的值；其右子樹根結(jié)點(diǎn)的值大于等于該結(jié)點(diǎn)X的值，則此二叉樹一 定是二叉排序樹。A.錯誤B.正確答案：A63,線性表的特點(diǎn)是每個元素都有一個前驅(qū)和一個后繼。A.錯誤B.正確答案：A64.直接訪問文件也能順序訪問，只是一般效率不高。A.錯誤B.正確答案：A65.對大小均為n的有序表和無序表分別進(jìn)行順序查找，在等概

50、率查找 的情況下，對于查找成功，它們的平均查找長度是相同的，而對于查找 失敗，它們的平均查找長度是不同的。A.錯誤B.正確答案：B66 .在查找樹（二叉排序樹）中插入一個新結(jié)點(diǎn)，總是插入到葉結(jié)點(diǎn)下 面O67 .二叉樹的遍歷結(jié)果不是唯一的。A .錯誤 B.正確 答案：B68 .哈夫曼樹的結(jié)點(diǎn)個數(shù)不能是偶數(shù)。A .錯誤B.正確答案：B69 .用一維數(shù)組存儲二叉樹時，總是以前序遍歷順序存儲結(jié)點(diǎn)。A.錯誤B.正確答案：A70 .程序一定是算法。A ,錯誤B.正確答案：A71 .兩個棧共用靜態(tài)存儲空間，對接使用方式減少了空間溢出的可能性。A .錯誤 B.正確 答案：B72 .二叉樹中每個結(jié)點(diǎn)至多有兩個子

51、結(jié)點(diǎn)，而對一般的樹則無此限制。因此，二叉樹是樹的特殊情形。73 .在中序線索二叉樹中，每一非空的線索均指向其祖先結(jié)點(diǎn)。A .錯誤 B.正確 答案：B74 .棧是實(shí)現(xiàn)過程和函數(shù)等子程序所必需的結(jié)構(gòu)。A .錯誤B.正確答案：B75 .數(shù)據(jù)結(jié)構(gòu)的運(yùn)算（操作）是定義在數(shù)據(jù)的邏輯結(jié)構(gòu)之上的。A.錯誤B.正確答案：B76 .數(shù)據(jù)對象是具有相同性質(zhì)的數(shù)據(jù)元素的集合。A ,錯誤B.正確答案：B77 .廣義表中的元素或者是一個不可分割的原子，或者是一個非空的廣 義表。A.錯誤 B.正確 答案：A78 .二叉樹中序線索化后，不存在空指針域。A .錯誤B.正確答案：A79 .對一棵二叉排序樹按前序方法遍歷得到的結(jié)點(diǎn)

52、序列是從小到大的序 列。A.錯誤B.正確答案：A80 .存放在磁盤、磁帶上的文件，既可以是順序文件，也可以是索引結(jié) 構(gòu)或其他結(jié)構(gòu)類型的文件。A.錯誤B.正確答案：A81 .當(dāng)廣義表中的每個元素都是原子時，廣義表便成了線性表。A.錯誤B.正確答案：B82 .完全二叉樹肯定是平衡二叉排序樹。A.錯誤B.正確答案：A83 .哈希表與哈希文件的唯一區(qū)別是哈希文件引入了 “桶”的概念。84 .串是一種數(shù)據(jù)對象和操作都特殊的線性表。A.錯誤B.正確答案：B85 .將一棵樹轉(zhuǎn)成二叉樹，根結(jié)點(diǎn)沒有右子樹。A .錯誤 B.正確 答案：B86 .數(shù)組是同類型值的集合。A.錯誤B.正確 答案：A87 .串只能按順序存儲方式進(jìn)行存儲。A.錯誤 B.正確 答案：A88 .鏈表與順序存儲結(jié)構(gòu)相比，在鏈表中進(jìn)行插入、刪除操作的效率高。A .錯誤B.正確 答案：B89