北京交通大學2001年數據結構考研試題

來源：時間：2007-06-06 13:36:19

2001年碩士研究生入學考試試卷（北方交大）(f)
一．選擇題
1：以下數據結構中，哪一個是線形結構？
A）廣義表 B）二叉樹 C）稀疏矩陣 D）串
2：以下那一個術語與數據結構無關？
A）棧 B）哈希表 C）線索樹 D）雙向鏈表
3：有六個元素6，5，4，3，2，1 的順序進棧，問下列哪一個不是合法的出棧序列？
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：下述哪一條是順序存儲結構的優點？
A）存儲密度大 B）插入運算方便
C）刪除運算方便 D）可方便地用與各種邏輯結構的存儲表示
5：下面關于串的的敘述中，哪一個是不正確的？
A）串是字符的有限序列
B）空串是空格構成的串
C）模式匹配是串的一種重要運算
D）串既可以采用順序存儲，也可以采用鏈式存儲
6：由3 個結點可以構造出多少種不同的有向樹？
A）2 B）3 C）4 D）5
7：有3 個結點可以構造出多少種不同的二叉樹？
A）2 B）3 C）4 D）5
8：下列排序方法中，哪一個是穩定的排序二叉樹？
A）直接選擇排序 B）二分法插入排序
C）希爾排序 D）快速排序
9：對n 個記錄文件進行堆排序，最壞情況下的執行時間是多少？
A）O（log2n） B）O（n） C）O（nlog2n） D）O（n*n）
10：對包含n 個元素的散列表進行檢索，平均檢索長度______________。
A）為O（log2n） B）為O（n）
C）為O（nlog2n） D）不直接依賴與n
11：下列哪一種圖的的鄰接矩陣？
A）有向圖 B）無向圖
CD）AOV網 D） AOE網
12：用鏈接方式存儲的隊列，在進行刪除運算時_____________。
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.下面有關線性表的敘述中，錯誤的是哪一個？
A)線性表采用順序存儲，必須占用一片連續的存儲單元。
B)線性表采用順序存儲，便于進行插入和刪除操作。
C)線性表采用鏈接存儲，不必占用一片連續的存儲單元。
D)線性表采用鏈接存儲，便于插入和刪除操作。
15．用直接插入排序方法對下面四個序列進行排序（由小到大），元素比較次數最少的是_。
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.設森林F中有三棵樹，第一，第二棵樹的結點個數分別為M1，M2，和M3。與森林F對應的二叉樹根結點的右子樹上的結點個數是___________。
A）M1 B）M1 M2 C）M3 D）M2 M3
17.下面關于B和B 樹的敘述中，不正確的是_。
A）B樹和B 樹都是平衡的多叉樹。
B）B樹和B 樹都可用于文件的索引結構。
C）B樹和B 樹都能有效地支持順序檢索。
D）B樹和B 樹都能有效地支持隨機索。
18．對下列關鍵字序列用快速排序法進行排序時，速度最快的情是_.
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,散列函數為H(K)=K mod 17。采用線性探測法處理沖突，并將關鍵字序列26，25，72，38，8，18，59依次存儲到散列表中。
19.元素59存在散列表中的地址是_。
A)8 B)9 C)10 D)11
20.存放元素59需要搜索的次數是_。
A）2 B）3 C）4 D）5
21.二叉樹的先序遍歷和中序遍歷如下：
先序遍歷：EFHIGJK
中序遍歷： HFIEJKG
該二叉樹的右子樹的根是（）
A）E B)Ｆ　Ｃ）Ｇ　Ｄ）Ｈ
22.在完全二叉樹中，若一個節點是葉節點，則它沒（）。
A)左子結點 B) 右子結點　
　C)左子結點和右子結點　 D) 左子結點，右子結點和兄弟結點
23．在下列存儲形式中，哪一個不是樹的存儲形式？（）
A) 雙親表示法 B) 孩子鏈表表示法Ｃ）孩子兄弟表示法 D) 順序存儲表示法
24．圖中有關路徑的定義是（）
A) 由頂點和相鄰頂點序偶構成的邊所形成的序列
B) 由不同頂點所形成的序列
C) 由不同邊所形成的序列
D) 上述定義都不是
25．在二叉樹結點的先序序列，中序序列和后序序列中，所有葉子結點的先后順序（　　　）
A)都不相同　　　　　　　　　　B)　完全相同　
C)先序和中序相同，而與后序不同　D)　　中序和后序相同，而與先序不同
二．填空題
１．假設根結點的層數為１，具有ｎ各結點的二叉樹的最大高度是＿＿＿＿。
２．在順序表（８，１１，１５，１９，２５，２６，３０，３３，４２，４８，５０）　中，用二分（折半）法查找關鍵碼值20，序做的關鍵碼比較數為_______.
３．設下三角矩陣
|-a11 -|
| a21 a22 |
A = | a31 a32 a33 |
| ………………. |
|-An1 an2 an3 …… ann -|

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

結束

特別聲明：①凡本網注明稿件來源為"原創"的，轉載必須注明"稿件來源：育路網"，違者將依法追究責任；

②部分稿件來源于網絡，如有侵權，請聯系我們溝通解決。