中國人民公安大學(xué)2005年碩士研究生入學(xué)考試
試題(數(shù)據(jù)結(jié)構(gòu))
請將所有答案標(biāo)明題號(hào)，寫在答題本上，試題紙上請勿答題。嚴(yán)禁在答題紙密 封線以外留下姓名、考號(hào)等任何標(biāo)記，否則該卷無效。
一、 名詞解釋(每小題5分，共30分)
1. 描述線性表中三個(gè)概念的區(qū)別：頭指針、頭結(jié)點(diǎn)、首元結(jié)點(diǎn)(第1個(gè)元素結(jié)點(diǎn) )。
2. 數(shù)據(jù)結(jié)構(gòu)
3. 二叉排序樹
4. 關(guān)鍵路徑
5. 稀疏矩陣
6. 連通圖
二、 單項(xiàng)/多項(xiàng)選擇題(每空3分，共30分)
1. 具有N個(gè)結(jié)點(diǎn)的二叉樹的二叉鏈表結(jié)構(gòu)中，指針域?yàn)镹ULL的數(shù)目應(yīng)為( )；
A) N B) 2N
C) N+1； D) 2N+1
2. 假定有T1、T2、T3、T4、T5五個(gè)元素進(jìn)棧，進(jìn)棧次序?yàn)門1T2T3T4T5，不可能 的出棧序列有( )；
A)T1T2T3T4T5 B)T5T4T3T2T1
C)T1T2T5T3T4 D)T3T2T4T5 T1
E)T3T5T2T4 T1 F)T2T4 T3T5 T1
3. 表達(dá)式(15-3)*6/3*(20+6)的逆波蘭式，正確的是( )；
A)15 3 6 3 20 6-*/*+ B)15 3-6 *3/20 6+*
C)15 3 - 6 3 20 6+*/* D)15 3-6 3*20 6+*/
4. 下列各函數(shù)是按照增長率由大至小的順序排列的是( )；
A) B)
C) D)
5. 已知L是帶表頭結(jié)點(diǎn)的單鏈表，其P結(jié)點(diǎn)既不是首結(jié)點(diǎn)(第一結(jié)點(diǎn))，也不是尾 結(jié)點(diǎn)：
1) 刪除P結(jié)點(diǎn)的直接后繼結(jié)點(diǎn)的語句序列是( )；
2) 刪除P結(jié)點(diǎn)的語句序列是( )；
3) 刪除首結(jié)點(diǎn)的語句序列是( )；
4) 刪除尾結(jié)點(diǎn)的語句序列是( )；
A) P=P→next ;
B) P→next=P ;
C) P→next=P→next→next ;
D) P=P→next→next ;
E) while P !=NULL { P=P→next ;}
F) while P→next !=NULL { P=P→next ;}
G) while P→next !=Q {P=P→next ;}
H) while P→next→next !=Q { P=P→next ;}
I) Q=NULL ;
J) Q=P ;
K) Q=P→next ;
L) P=L ;
M) L=L→next ;
N) free(Q);
6. N個(gè)結(jié)點(diǎn)的集合，利用二叉排序樹查找方法的平均查找長度(ASL)的計(jì)算公式 為( )；
A)N+1 B)log2N
C)(N+1)/2 D)1+4 log2N
7. 對(duì)下列關(guān)鍵字序列按照起泡排序算法進(jìn)行排序，則兩趟排序后的結(jié)果可能為 ( )。
(Kay, Eva, Amy, Roy, Dot, Jon, Kim, Boy)
A)(Amy, Eva, Dot, Jon, Kay, Boy, Kim, Roy)
B)(Amy, Boy, Dot, Eva, Jon, Kay, Kim, Roy)
C)(Eva, Amy, Kay, Dot, Jon, Kim, Boy, Roy)
D)(Eva, Amy, Dot, Roy, Jon, Boy, Kim, Kay)
三、 填空題(每題2分，共20分)
1. 在順序存儲(chǔ)結(jié)構(gòu)的線性表中，插入或刪除一個(gè)元素需要平均移動(dòng) 【1】 元 素，具體移動(dòng)元素個(gè)數(shù)與 【2】 有關(guān)。
2. 假設(shè)二維數(shù)組A[6][8]，每個(gè)元素用相鄰的4個(gè)字節(jié)存儲(chǔ)，存儲(chǔ)器按字節(jié)編址 ，已知A的開始存儲(chǔ)位置為100，則數(shù)組的存儲(chǔ)容量為 【3】 字節(jié)；按列優(yōu)先順序存儲(chǔ) 的元素A[2][5]的第一個(gè)字節(jié)的地址為 【4】 。
3. 一棵深度為5，18個(gè)結(jié)點(diǎn)的完全二叉樹，編號(hào)為10的結(jié)點(diǎn)的右兒子的編號(hào) 【 5】 ，其雙親結(jié)點(diǎn)的編號(hào)為 【6】 。
4. 在一棵有14個(gè)結(jié)點(diǎn)的完全二叉樹中，所含葉子結(jié)點(diǎn)的數(shù)目為 【7】 個(gè)。
5. 對(duì)稀疏矩陣的壓縮存儲(chǔ)，一般包括三元組表和 【8】 兩種基本方法。如圖 (A)所示的稀疏矩陣，試給出它所對(duì)應(yīng)的三元組線性表 【9】 ；
6. 如圖(B)所示的有向圖，該圖有 【10】 個(gè)強(qiáng)連通分量。
四、 簡答題(每題8分，共40分)
1. 對(duì)長度為n的記錄序列進(jìn)行快速排序時(shí)，所需進(jìn)行的比較次數(shù)依賴于這n個(gè)元 素的初始序列?，F(xiàn)假設(shè)n=7，試問在的情況下需進(jìn)行多少次比較？請說明理由。
2. 試證明：具有n個(gè)結(jié)點(diǎn)的二叉樹的最小深度為 。
3. 在串操作中，執(zhí)行以下函數(shù)會(huì)產(chǎn)生怎樣的輸出結(jié)果？
void demonstrate(){
StrAssign(s, ‘THIS IS A BOOK’);
Replace(s, SubString(s, 3, 7), ‘ESE ARE’);
StrAssign(t, Concat(s, ‘S’));
StrAssign(u, ‘XYXYXYXYXYXY’);
StrAssign(v, SubString(u, 6, 3));
StrAssign(w, ‘W’);
printf(‘t=’, t, ‘v=’, v, ’u=’, Replace(u, v, w));
} //demonstrate
4. 判別下面的一個(gè)序列是否為堆。如果不是，則把它調(diào)整為堆，畫出生成堆的 調(diào)整過程(要求記錄交換次數(shù)最少，且堆頂元素為最小值)。
(12，70，48，86，24，56，30，92，65，38)
5. 試列出如圖(C)中全部可能的拓?fù)溆行蛐蛄小?BR> 圖 (C)
五、 綜合設(shè)計(jì)題(每題15分，共30分)
1. 試?yán)肈ijkstra算法求圖(D)中從頂點(diǎn)a到其他各頂點(diǎn)間的最短路徑，寫出執(zhí) 行算法過程中各步的狀態(tài)。
圖 (D)
2. 假設(shè)用于通信的電文只使用A，B，C，D，E，F(xiàn)這六個(gè)字母組成，字母在電文 中出現(xiàn)的頻率依次為4，2，6，8，3，2。按照要求完成如下任務(wù)：
1)試為這6個(gè)字母設(shè)計(jì)哈夫曼編碼和等長二進(jìn)制編碼方案，給出兩種編碼的對(duì)照 表。
2)求出這兩種編碼的帶權(quán)路徑長度WPL，比較兩種方案的優(yōu)缺點(diǎn)。
3)給出哈夫曼樹的邏輯結(jié)構(gòu)。
試題(數(shù)據(jù)結(jié)構(gòu))
請將所有答案標(biāo)明題號(hào)，寫在答題本上，試題紙上請勿答題。嚴(yán)禁在答題紙密 封線以外留下姓名、考號(hào)等任何標(biāo)記，否則該卷無效。
一、 名詞解釋(每小題5分，共30分)
1. 描述線性表中三個(gè)概念的區(qū)別：頭指針、頭結(jié)點(diǎn)、首元結(jié)點(diǎn)(第1個(gè)元素結(jié)點(diǎn) )。
2. 數(shù)據(jù)結(jié)構(gòu)
3. 二叉排序樹
4. 關(guān)鍵路徑
5. 稀疏矩陣
6. 連通圖
二、 單項(xiàng)/多項(xiàng)選擇題(每空3分，共30分)
1. 具有N個(gè)結(jié)點(diǎn)的二叉樹的二叉鏈表結(jié)構(gòu)中，指針域?yàn)镹ULL的數(shù)目應(yīng)為( )；
A) N B) 2N
C) N+1； D) 2N+1
2. 假定有T1、T2、T3、T4、T5五個(gè)元素進(jìn)棧，進(jìn)棧次序?yàn)門1T2T3T4T5，不可能 的出棧序列有( )；
A)T1T2T3T4T5 B)T5T4T3T2T1
C)T1T2T5T3T4 D)T3T2T4T5 T1
E)T3T5T2T4 T1 F)T2T4 T3T5 T1
3. 表達(dá)式(15-3)*6/3*(20+6)的逆波蘭式，正確的是( )；
A)15 3 6 3 20 6-*/*+ B)15 3-6 *3/20 6+*
C)15 3 - 6 3 20 6+*/* D)15 3-6 3*20 6+*/
4. 下列各函數(shù)是按照增長率由大至小的順序排列的是( )；
A) B)
C) D)
5. 已知L是帶表頭結(jié)點(diǎn)的單鏈表，其P結(jié)點(diǎn)既不是首結(jié)點(diǎn)(第一結(jié)點(diǎn))，也不是尾 結(jié)點(diǎn)：
1) 刪除P結(jié)點(diǎn)的直接后繼結(jié)點(diǎn)的語句序列是( )；
2) 刪除P結(jié)點(diǎn)的語句序列是( )；
3) 刪除首結(jié)點(diǎn)的語句序列是( )；
4) 刪除尾結(jié)點(diǎn)的語句序列是( )；
A) P=P→next ;
B) P→next=P ;
C) P→next=P→next→next ;
D) P=P→next→next ;
E) while P !=NULL { P=P→next ;}
F) while P→next !=NULL { P=P→next ;}
G) while P→next !=Q {P=P→next ;}
H) while P→next→next !=Q { P=P→next ;}
I) Q=NULL ;
J) Q=P ;
K) Q=P→next ;
L) P=L ;
M) L=L→next ;
N) free(Q);
6. N個(gè)結(jié)點(diǎn)的集合，利用二叉排序樹查找方法的平均查找長度(ASL)的計(jì)算公式 為( )；
A)N+1 B)log2N
C)(N+1)/2 D)1+4 log2N
7. 對(duì)下列關(guān)鍵字序列按照起泡排序算法進(jìn)行排序，則兩趟排序后的結(jié)果可能為 ( )。
(Kay, Eva, Amy, Roy, Dot, Jon, Kim, Boy)
A)(Amy, Eva, Dot, Jon, Kay, Boy, Kim, Roy)
B)(Amy, Boy, Dot, Eva, Jon, Kay, Kim, Roy)
C)(Eva, Amy, Kay, Dot, Jon, Kim, Boy, Roy)
D)(Eva, Amy, Dot, Roy, Jon, Boy, Kim, Kay)
三、 填空題(每題2分，共20分)
1. 在順序存儲(chǔ)結(jié)構(gòu)的線性表中，插入或刪除一個(gè)元素需要平均移動(dòng) 【1】 元 素，具體移動(dòng)元素個(gè)數(shù)與 【2】 有關(guān)。
2. 假設(shè)二維數(shù)組A[6][8]，每個(gè)元素用相鄰的4個(gè)字節(jié)存儲(chǔ)，存儲(chǔ)器按字節(jié)編址 ，已知A的開始存儲(chǔ)位置為100，則數(shù)組的存儲(chǔ)容量為 【3】 字節(jié)；按列優(yōu)先順序存儲(chǔ) 的元素A[2][5]的第一個(gè)字節(jié)的地址為 【4】 。
3. 一棵深度為5，18個(gè)結(jié)點(diǎn)的完全二叉樹，編號(hào)為10的結(jié)點(diǎn)的右兒子的編號(hào) 【 5】 ，其雙親結(jié)點(diǎn)的編號(hào)為 【6】 。
4. 在一棵有14個(gè)結(jié)點(diǎn)的完全二叉樹中，所含葉子結(jié)點(diǎn)的數(shù)目為 【7】 個(gè)。
5. 對(duì)稀疏矩陣的壓縮存儲(chǔ)，一般包括三元組表和 【8】 兩種基本方法。如圖 (A)所示的稀疏矩陣，試給出它所對(duì)應(yīng)的三元組線性表 【9】 ；
6. 如圖(B)所示的有向圖，該圖有 【10】 個(gè)強(qiáng)連通分量。
四、 簡答題(每題8分，共40分)
1. 對(duì)長度為n的記錄序列進(jìn)行快速排序時(shí)，所需進(jìn)行的比較次數(shù)依賴于這n個(gè)元 素的初始序列?，F(xiàn)假設(shè)n=7，試問在的情況下需進(jìn)行多少次比較？請說明理由。
2. 試證明：具有n個(gè)結(jié)點(diǎn)的二叉樹的最小深度為 。
3. 在串操作中，執(zhí)行以下函數(shù)會(huì)產(chǎn)生怎樣的輸出結(jié)果？
void demonstrate(){
StrAssign(s, ‘THIS IS A BOOK’);
Replace(s, SubString(s, 3, 7), ‘ESE ARE’);
StrAssign(t, Concat(s, ‘S’));
StrAssign(u, ‘XYXYXYXYXYXY’);
StrAssign(v, SubString(u, 6, 3));
StrAssign(w, ‘W’);
printf(‘t=’, t, ‘v=’, v, ’u=’, Replace(u, v, w));
} //demonstrate
4. 判別下面的一個(gè)序列是否為堆。如果不是，則把它調(diào)整為堆，畫出生成堆的 調(diào)整過程(要求記錄交換次數(shù)最少，且堆頂元素為最小值)。
(12，70，48，86，24，56，30，92，65，38)
5. 試列出如圖(C)中全部可能的拓?fù)溆行蛐蛄小?BR> 圖 (C)
五、 綜合設(shè)計(jì)題(每題15分，共30分)
1. 試?yán)肈ijkstra算法求圖(D)中從頂點(diǎn)a到其他各頂點(diǎn)間的最短路徑，寫出執(zhí) 行算法過程中各步的狀態(tài)。
圖 (D)
2. 假設(shè)用于通信的電文只使用A，B，C，D，E，F(xiàn)這六個(gè)字母組成，字母在電文 中出現(xiàn)的頻率依次為4，2，6，8，3，2。按照要求完成如下任務(wù)：
1)試為這6個(gè)字母設(shè)計(jì)哈夫曼編碼和等長二進(jìn)制編碼方案，給出兩種編碼的對(duì)照 表。
2)求出這兩種編碼的帶權(quán)路徑長度WPL，比較兩種方案的優(yōu)缺點(diǎn)。
3)給出哈夫曼樹的邏輯結(jié)構(gòu)。