北京交通大學(xué)2001年數(shù)據(jù)結(jié)構(gòu)考研試題

來源：時(shí)間：2007-06-06 13:36:19

2001年碩士研究生入學(xué)考試試卷（北方交大）(f)
一．選擇題
1：以下數(shù)據(jù)結(jié)構(gòu)中，哪一個(gè)是線形結(jié)構(gòu)？
A）廣義表 B）二叉樹 C）稀疏矩陣 D）串
2：以下那一個(gè)術(shù)語與數(shù)據(jù)結(jié)構(gòu)無關(guān)？
A）棧 B）哈希表 C）線索樹 D）雙向鏈表
3：有六個(gè)元素6，5，4，3，2，1 的順序進(jìn)棧，問下列哪一個(gè)不是合法的出棧序列？
A）5 4 3 6 1 2 B）4 5 3 1 2 6 C）3 4 6 5 2 1 D）2 3 4 1 5 6
4：下述哪一條是順序存儲(chǔ)結(jié)構(gòu)的優(yōu)點(diǎn)？
A）存儲(chǔ)密度大 B）插入運(yùn)算方便
C）刪除運(yùn)算方便 D）可方便地用與各種邏輯結(jié)構(gòu)的存儲(chǔ)表示
5：下面關(guān)于串的的敘述中，哪一個(gè)是不正確的？
A）串是字符的有限序列
B）空串是空格構(gòu)成的串
C）模式匹配是串的一種重要運(yùn)算
D）串既可以采用順序存儲(chǔ)，也可以采用鏈?zhǔn)酱鎯?chǔ)
6：由3 個(gè)結(jié)點(diǎn)可以構(gòu)造出多少種不同的有向樹？
A）2 B）3 C）4 D）5
7：有3 個(gè)結(jié)點(diǎn)可以構(gòu)造出多少種不同的二叉樹？
A）2 B）3 C）4 D）5
8：下列排序方法中，哪一個(gè)是穩(wěn)定的排序二叉樹？
A）直接選擇排序 B）二分法插入排序
C）希爾排序 D）快速排序
9：對(duì)n 個(gè)記錄文件進(jìn)行堆排序，最壞情況下的執(zhí)行時(shí)間是多少？
A）O（log2n） B）O（n） C）O（nlog2n） D）O（n*n）
10：對(duì)包含n 個(gè)元素的散列表進(jìn)行檢索，平均檢索長度______________。
A）為O（log2n） B）為O（n）
C）為O（nlog2n） D）不直接依賴與n
11：下列哪一種圖的的鄰接矩陣？
A）有向圖 B）無向圖
CD）AOV網(wǎng) D） AOE網(wǎng)
12：用鏈接方式存儲(chǔ)的隊(duì)列，在進(jìn)行刪除運(yùn)算時(shí)_____________。
A）僅修改頭指針 B）僅修改尾指針
C）頭，尾指針都要修改 D）頭，尾指針可能都要修改
13.下面過程是二叉樹的何種遍歷方法？
Procedure traverse(p:pointer);
Begin
If p<>nil
Then begin.
Process(p);
Traverse(p^.left);
Travrse(p^.right)
end
end
A)中序 B）前序 C)后序D)層次
14.下面有關(guān)線性表的敘述中，錯(cuò)誤的是哪一個(gè)？
A)線性表采用順序存儲(chǔ)，必須占用一片連續(xù)的存儲(chǔ)單元。
B)線性表采用順序存儲(chǔ)，便于進(jìn)行插入和刪除操作。
C)線性表采用鏈接存儲(chǔ)，不必占用一片連續(xù)的存儲(chǔ)單元。
D)線性表采用鏈接存儲(chǔ)，便于插入和刪除操作。
15．用直接插入排序方法對(duì)下面四個(gè)序列進(jìn)行排序（由小到大），元素比較次數(shù)最少的是_。
A)94,32,40,90,80,46,21,69 B)32,40,21,46,69,94,90,80
C)21,32,46,40,80,69,90,94 C)90,69,80,46,21,32,94,40
16.設(shè)森林F中有三棵樹，第一，第二棵樹的結(jié)點(diǎn)個(gè)數(shù)分別為M1，M2，和M3。與森林F對(duì)應(yīng)的二叉樹根結(jié)點(diǎn)的右子樹上的結(jié)點(diǎn)個(gè)數(shù)是___________。
A）M1 B）M1 M2 C）M3 D）M2 M3
17.下面關(guān)于B和B 樹的敘述中，不正確的是_。
A）B樹和B 樹都是平衡的多叉樹。
B）B樹和B 樹都可用于文件的索引結(jié)構(gòu)。
C）B樹和B 樹都能有效地支持順序檢索。
D）B樹和B 樹都能有效地支持隨機(jī)索。
18．對(duì)下列關(guān)鍵字序列用快速排序法進(jìn)行排序時(shí)，速度最快的情是_.
A){21,25,5,17,9,23,30} B){25,23,30,17,21,5,9}
C){21,9,17,30,25,23,5} C){5,9,17,21,23,25,30}
19-20 題列描述:
散列表的地址間為0-17,散列函數(shù)為H(K)=K mod 17。采用線性探測(cè)法處理沖突，并將關(guān)鍵字序列26，25，72，38，8，18，59依次存儲(chǔ)到散列表中。
19.元素59存在散列表中的地址是_。
A)8 B)9 C)10 D)11
20.存放元素59需要搜索的次數(shù)是_。
A）2 B）3 C）4 D）5
21.二叉樹的先序遍歷和中序遍歷如下：
先序遍歷：EFHIGJK
中序遍歷： HFIEJKG
該二叉樹的右子樹的根是（）
A）E B)Ｆ�。茫恰。模�
22.在完全二叉樹中，若一個(gè)節(jié)點(diǎn)是葉節(jié)點(diǎn)，則它沒（）。
A)左子結(jié)點(diǎn) B) 右子結(jié)點(diǎn)　
　C)左子結(jié)點(diǎn)和右子結(jié)點(diǎn)　 D) 左子結(jié)點(diǎn)，右子結(jié)點(diǎn)和兄弟結(jié)點(diǎn)
23．在下列存儲(chǔ)形式中，哪一個(gè)不是樹的存儲(chǔ)形式？（）
A) 雙親表示法 B) 孩子鏈表表示法Ｃ）孩子兄弟表示法 D) 順序存儲(chǔ)表示法
24．圖中有關(guān)路徑的定義是（）
A) 由頂點(diǎn)和相鄰頂點(diǎn)序偶構(gòu)成的邊所形成的序列
B) 由不同頂點(diǎn)所形成的序列
C) 由不同邊所形成的序列
D) 上述定義都不是
25．在二叉樹結(jié)點(diǎn)的先序序列，中序序列和后序序列中，所有葉子結(jié)點(diǎn)的先后順序（　　�。�
A)都不相同　　　　　　　　　　B)　完全相同　
C)先序和中序相同，而與后序不同　D)　　中序和后序相同，而與先序不同
二．填空題
１．假設(shè)根結(jié)點(diǎn)的層數(shù)為１，具有ｎ各結(jié)點(diǎn)的二叉樹的最大高度是＿＿＿＿。
２．在順序表（８，１１，１５，１９，２５，２６，３０，３３，４２，４８，５０）　中，用二分（折半）法查找關(guān)鍵碼值20，序做的關(guān)鍵碼比較數(shù)為_______.
３．設(shè)下三角矩陣
|-a11 -|
| a21 a22 |
A = | a31 a32 a33 |
| ………………. |
|-An1 an2 an3 …… ann -|

如果按行序?yàn)橹餍蚪迪氯窃谹(I j) 存儲(chǔ)在一個(gè)一維數(shù)組B[ 1……n(n 1)/2]中，對(duì)人一個(gè)三角矩陣元素Aij ,它在數(shù)組B中的下標(biāo)為_______.
４．當(dāng)現(xiàn)行標(biāo)的元素總數(shù)基本穩(wěn)定，且很少進(jìn)行插入和刪除操作，但要求以最快的速度存取線性表中的元素時(shí)，應(yīng)采用_______存儲(chǔ)結(jié)構(gòu) 。
５．隊(duì)列是限制插入只能在表的一端，而刪除在表的另一端進(jìn)行的線性表，其特點(diǎn)是_____.
６．在一棵二叉樹中，度為零的結(jié)點(diǎn)的個(gè)數(shù)為N0,度為2的結(jié)點(diǎn)的個(gè)數(shù)為N2,擇優(yōu)N0 =_____
７．設(shè)有字母序列{Q,D,F,X,A,P,N,B,Y,M,C,W},請(qǐng)寫出按2路歸并排序方法對(duì)該序列進(jìn)行一趟掃描后的結(jié)果___________.
８．對(duì)于具有144 個(gè)紀(jì)錄的文件，若采用分塊查找法，且每塊長度為8，則平均查找長度為_______.
９．線性表L=（a1,a2,……,an）用數(shù)組表示，假定刪除表中任意元素的概率相同，則刪除一個(gè)元素平均需要移動(dòng)元素的個(gè)數(shù)是________.
三請(qǐng)?jiān)O(shè)計(jì)算法將不帶頭結(jié)點(diǎn)的單鏈表就地逆置。
四請(qǐng)?jiān)O(shè)計(jì)算法按層次順序遍歷二叉樹。

結(jié)束

特別聲明：①凡本網(wǎng)注明稿件來源為"原創(chuàng)"的，轉(zhuǎn)載必須注明"稿件來源：育路網(wǎng)"，違者將依法追究責(zé)任；

②部分稿件來源于網(wǎng)絡(luò)，如有侵權(quán)，請(qǐng)聯(lián)系我們溝通解決。