|
友情提示：本站提供全國400多所高等院校招收碩士、博士研究生入學考試歷年考研真題、考博真題、答案，部分學校更新至2012年，2013年；均提供收費下載。 下載流程： 考研真題 點擊“考研試卷””下載; 考博真題 點擊“考博試卷庫” 下載
1
目錄
I 考查目標........................................................................................ 2
II 考試形式和試卷結構 ..................................................................2
III 考查內容..................................................................................... 2
IV. 題型示例及參考答案.................................................................3
2
全國碩士研究生入學統一考試
數據結構考試大綱
I 考查目標
全國碩士研究生入學統一考試模式識別與智能系統、計算機技術、軟件工程、農業信息
化碩士專業學位《數據結構》考試是為江蘇大學招收以上碩士生設置的具有選拔性質的考試
科目。其目的是科學、公平、有效地測試考生是否具備攻讀模式識別與智能系統、計算機技
術、軟件工程、農業信息化專業碩士所必須的基本素質、一般能力和培養潛能,以利用選拔
具有發展潛力的優秀人才入學,為國家的經濟建設培養具有良好職業道德、法制觀念和國際
視野、具有較強分析與解決實際問題能力的專業人才?？荚囈罂忌容^系統地掌握數據結
構課程的概念、基本原理和方法,能夠運用所學的基本原理和基本方法分析、判斷和解決有
關理論問題和實際問題。
具體來說,要求考生：
1. 理解數據結構的基本概念；掌握數據的邏輯結構、存儲結構及其差異,以及各種基
本操作的實現。
2. 掌握基本的數據處理原理和方法的基礎上,能夠對算法進行設計與分析。
3. 能夠選擇合適的數據結構和方法進行問題求解。
II 考試形式和試卷結構
一、試卷滿分及考試時間
試卷滿分為 150 分,考試時間 180 分鐘。
二、答題方式
答題方式為閉卷、筆試。
三、試卷內容與題型結構
單項選擇題 10 題,每小題 1 分, 共 10 分
填空題 題數不定,每空 1 分, 共 10 分
應用題 題數不定, 共 80 分
簡答題 題數不定, 共 30 分
算法設計題 題數不定, 共 20 分
III 考查內容
1 緒論
1.1 數據結構的基本概念和術語
1.2 算法的定義、性能標準和復雜度
2 線性表
2.1 線性表的定義
2.2 線性表的順序表示和實現
2.3 線性表的鏈表表示和實現
2.4 線性表的應用
3 棧和隊列
3.1 棧和隊列的基本概念
3
3.2 棧和隊列的順序存儲結構
3.3 棧和隊列的鏈式存儲結構
3.4 棧和隊列的應用
4 串、數組和廣義表
4.1 字符串的定義、存儲結構和操作,模式匹配算法
4.2 數組的定義和順序存儲結構,特殊矩陣和稀疏矩陣的壓縮存儲
4.3 廣義表的定義和存儲結構
5. 樹和森林
5. 1 樹的定義和術語,樹的表示形式和基本操作
5. 2 二叉樹的定義、性質和基本操作
5. 3 二叉樹的順序存儲結構和鏈式存儲結構
5. 4 二叉樹的遍歷
5. 5 線索二叉樹
5. 6 哈夫曼樹和哈夫曼編碼
5. 7 樹的存儲結構,樹、森林和二叉樹的轉換,樹和森林的遍歷
5. 8 等價類及其表示
6 圖
6. 1 圖的定義、術語和基本操作
6. 2 圖的存儲結構(鄰接矩陣、鄰接表)
6. 3 圖的深度優先遍歷、廣度優先遍歷和連通分量
6. 4 最小生成樹、最短路徑、拓撲排序和關鍵路徑
7 查找
7. 1 查找的基本概念
7. 2 順序查找法、折半查找法和索引順序表上的查找
7. 3 二叉排序樹的定義,二叉排序樹上的查找、插入和刪除,二叉排序樹查找的性能分析
7. 4 平衡二叉樹的定義,平衡旋轉,平衡二叉樹的插入和刪除
7. 5 散列表的基本概念、構造和分析
8 內部排序
8. 1 排序的基本概念
8. 2 交換排序(冒泡排序,快速排序)
8. 3 插入排序(直接插入排序,折半插入排序,希爾排序)
8. 4 選擇排序(直接選擇排序,錦標賽排序,堆排序)
8. 5 兩路歸并排序
8. 6 基數排序
8. 7 各種內部排序算法的比較和應用
IV. 題型示例及參考答案
4
一、單項選擇題(每小題 1 分,共 10 分)
1. 設有數組 A[i,j],數組的每個元素長度為 3 字節,i 的值為 1 到 8,j 的值為 1 到 10,數組從內
存首地址 SA 開始順序存放,當以列為主存放時,元素 A[5,8]的存儲首地址為( )。
(A) SA+180 (B) SA+141 (C) SA+222 (D) SA+225
2. 在雙向鏈表指針 p 的結點前插入一個指針 q 的結點操作是( )。
(A) p->Llink=q;q->Rlink=p;p->Llink->Rlink=q;q->Llink=q；
(B) q->Rlink=p;q->Llink=p->Llink;p->Llink->Rlink=q;p->Llink=q;
(C) p->Llink=q;p->Llink->Rlink=q;q->Rlink=p;q->Llink=p->Llink;
(D) q->Llink=p->Llink;q->Rlink=q;p->Llink=q;p->Llink=q;
3. 一棵二叉樹高度為 h,所有結點的度或為 0,或為 2,則這棵二叉樹最少有( )結點。
(A) 2h (B) 2h+1 (C) 2h-1 (D) h+1
4. 當在一個有序的順序存儲表上查找一個數據時,既可用折半查找,也可用順序查找,但前
者比后者的查找速度( )。
(A) 取決于表遞增還是遞減 (B) 必定快 (C) 不一定 (D) 在大部分情況下要快
5. 串的長度是指( )。
(A)串中所含不同字母的個數 (B)串中所含非空格字符的個數
(C)串中所含不同字符的個數 (D)串中所含字符的個數
6. 下面說法錯誤的是( )。
(A) 算法原地工作的含義是指不需要任何額外的輔助空間
(B) 在相同的規模 n 下,復雜度 O(n)的算法在時間上總是優于復雜度 O(2
n
)的算法
(C) 所謂時間復雜度是指最壞情況下,估算算法執行時間的一個上界
(D) 同一個算法,實現語言的級別越高,執行效率就越低
7. 以下錯誤的是 ( )
(i) 靜態鏈表既有順序存儲的優點,又有動態鏈表的優點。所以,它存取表中第 i 個元素
的時間與 i 無關。
(ii) 靜態鏈表中能容納的元素個數的最大數在表定義時就確定了,以后不能增加。
(iii) 靜態鏈表與動態鏈表在元素的插入、刪除上類似,不需做元素的移動。
(A) (i),(ii) (B) (i) (C) (i),(ii),(iii) (D) (ii)
8. 已知廣義表 LS＝((a,b,c),(d,e,f)),運用 head 和 tail 函數取出 LS 中原子 e 的運算是
( )。
(A) head(tail(head(tail(LS))) (B) tail(head(LS))
(C) head(tail(LS)) (D) head(tail(tail(head(LS))))
9. 對于順序存儲的線性表,訪問結點和增加結點的時間復雜度為( )。
(A)O(n) O(n) (B) O(n) O(1) (C) O(1) O(n) (D) O(1) O(1)
10. 若棧采用順序存儲方式存儲,現兩個棧共享空間 V[1..m],top[j]表示第 j 個棧(j=1,2)棧頂指
針,棧 1 的底設在 V[1],棧 2 的底設在 V[m],則棧滿的條件是( )。
(A) top[2] – top[1] = = m (B) top[2] – top[1] = = 1
(C) top[2] – top[1] = = 0 (D) top[2] + top[1] = = m
二、填空題(每空 1 分,共 10 分)
1. 循環隊列用下標范圍是 0 到 m 的數組 V 存放其元素值,已知其頭、尾指針分別是 f 和 r,f
是隊首元素的前一個位置,r 是隊尾元素位置,若用犧牲一個單元的辦法來區分隊滿和隊
空,則隊滿的條件為 。
2. 有一個 100×200 的元素值為整型的稀疏矩陣,非零元素有 20 個,設每個整型數占 2 字節,
則用三元組順序表表示該矩陣時,所需的字節總數是 。
3. 如果按關鍵碼值遞增的順序依次將99個關鍵碼值插入到二叉排序樹中,則對這樣的二叉
5
排序樹檢索時,在等概率而且查找成功的情況下的平均查找長度 ASL 為 。
4. 下面程序段中帶下劃線的語句的執行次數的數量級是 。
i=1; while (i,< V4,V5,60>, <
V4,V3,20>,< V3,V5,15>,< V2,V6,10>, < V2,V3,50>, < V1,V2,5>}。要求：
（1） 畫出該有向網。
（2） 畫出該有向網的鄰接矩陣。
（3） 求基于你的鄰接矩陣的從頂點 V1 出發的 DFS 序列以及 DFS 生成樹。
（4） 給出該有向網的所有拓撲有序序列。
（5） 用 dijkstra 算法,求從源點 V1 出發到其它各終點的最短路徑以及長度,請給出執行算
法過程中各步的狀態,可用下面給出的表格形式表示。
4. (12 分)有一結點的關鍵字序列 F={26,36,41,38,44,15,68,12,06,51,25},
散列函數為：H(K)= K % 11,其中 K 為關鍵字,散列地址空間為 0～10。要求：
（1） 畫出相應的閉散列表。發生沖突時,以線性探測法解決。
（2） 該散列表的裝填因子 α 是多少？
（3） 在等概率情況下查找成功時的平均查找長度 ASL 是多少？
（4） 用線性探測法解決沖突時,如何處理被刪除的結點？為什么？
5.(8 分)已知長度為 10 的表{16,3,7,12,9,28,25,18,14,20},按表中元素順序依次插入一棵初始時
為空的平衡二叉排序樹中,畫出每一步插入后平衡二叉排序樹的形態。若做了某種旋轉,說
明旋轉的類型。
6.(20 分)已知關鍵字序列 F={22,12,26,40,18,38,14,20,30,16,28}。要求：
（1） 將該序列調整為“小頂”堆,并給出調整過程。請從時間和空間兩方面對簡單選擇排
序、樹形選擇排序和堆排序作一比較。
6
（2） 若采用鏈式基數排序方法排序,請寫出第一趟“分配”之后各隊列的狀態和第一趟“收
集”之后的關鍵字序列。并請簡要說出基數排序方法和其他排序方法有什么區別？
（3） 要求最后排序結果是按關鍵字從小到大的次序排列,請給出冒泡排序的前 3 趟排序結
果。
四、簡答題(共 30 分)
1. (6 分)線性表的順序存儲結構和鏈式存儲結構各有哪些優缺點？
2. (8 分)畫出對長度 n 為 10 的遞增有序表{A[1]、A[2]、……、A[10]}進行折半查找的判定
樹。當實現插入排序過程時,可以用折半查找來確定第 i 個元素在前 i-1 個元素中的可能插
入位置,這樣做能否改善插入排序的時間復雜度？為什么？
3. (8 分)快速排序的平均時間復雜度是多少？快速排序在所有同數量級的排序方法中,其平
均性能好。但在什么情況下快速排序將蛻化為起泡排序,此時的時間復雜度又是多少？為
改進之,通常可以怎么做？
4. (8 分)請簡要敘述求最小生成樹的 Prim 算法的思想(或步驟)。并指出對具有 n 個頂點和 e
條邊的連通網而言,Prim 算法和Kruskal算法各自適合于什么情況下的連通網？其時間復雜
度又各為多少？
五、算法設計題(共 20 分)
1.(10 分) 給定( 已生成) 一個帶表頭結點的單鏈表, 設 head 為頭指針, 結點的結構為
(data,next),data 為整型元素,next 為指針,試寫出算法：按遞減次序輸出單鏈表中各結點的數
據元素,并釋放結點所占的存儲空間。(要求：不允許使用數組作輔助空間)
2.(10 分)以二叉鏈表作為二叉樹的存儲結構,試編寫遞歸算法,求二叉樹中以元素值為 item 的
結點為根的子樹的深度(假設樹中一定存在值為 item 的結點)。
注意：
(1)可用(類)Pascal 語言或(類)C 語言或 C++語言描述你的算法；
(2)請簡要描述你的算法思想；
(3)若你的算法是(類)Pascal 或(類)C 語言編寫,則請給出相應的存儲結構描述；
(4)若你的算法是用 C++語言描述,則可參考使用以下給出的相關存儲結構的類定義,算
法中可以使用類中已列出的成員函數。若在你的算法中使用了未列出的成員函數,則要寫出
該成員函數的完整算法描述
//單鏈表的類定義
template class linklist; //單鏈表前視聲明
template class node{//單鏈表結點類
friend class linklist ; //定義單鏈表類 linklist 為結點類的友元
private:
node *next; //鏈指針域
public:
type data; //數據域
node (node *pnext = NULL) {next = pnext;}//構造函數,用于構造頭結點
};
template class linklist{ //單鏈表類定義
private:
node *head; //指向頭結點的頭指針
public:
linklist ( ){ head = new node ( ); head->next=NULL; }//構造函數
~linklist ( ); //析構函數
7
};
//二叉鏈表的類定義：
template class BinaryTree; //二叉鏈表類前視聲明,以便使用友元
template class BinTreeNode { //結點類
friend class BinaryTree;
private:
BinTreeNode *leftChild, *rightChild; //結點的左、右孩子指針域
Type data; //結點的數據域
public:
BinTreeNode ( ) : leftChild (NULL), rightChild (NULL) { } //構造函數,構造一個空結點
BinTreeNode (Type d, BinTreeNode *lp = NULL, BinTreeNode *rp =NULL ) :
data (d), leftChild (lp), rightChild (rp) { }
//構造函數,構造一個數據域的值為 d 的結點
};
template class BinaryTree { //二叉鏈表類
private:
BinTreeNode *root; //二叉樹根結點指針
public:
BinaryTree ( ) : root (NULL) { } //構造函數
~BinaryTree ( ) { destroy ( root ); } //析構函數
};
參考答案
一、單項選擇題
1. A；2. B；3. C；4. D；5. D；6. C；7. B；8. A；9. C；10. B；
二、填空題
1. (r-f+m+1)%(m+1)
2. 20*3*2+6=126
3. (99+1)/2=50
4. O(nlog2n)
5. (9+1)/2+(6+1)/2=17/2=8.5
6. log3(244+1)的上取整或 log3244 下取整+1
7. 長度相等,對應位置的字符相同
8. n
9. abc+*d-
10. 500 (n2=499,n0=n2+1=499+1=500)
三、應用題
1.
(1)二叉樹
8
D FE
CB
A
JH KG
L
I
(2)森林
D
F
E
C
B
A
J
H
K
G L
I
(3)中序全線索二叉樹
D FE
CB
A
JH KG
L
I
NULL
NULL
(4)雙親孩子鏈表
A -1
B 1
E 1 ^
I 1 ^
D 2
H 2 ^
G 5 ^
L 5 ^
1
2
3
4
5
6
7
8
2 ^43
^65
^87
2.
(1)
9
(2)
(3)
WPL=(3+6)*4+(8+10+15)*3+(19+21)*2=36+99+80=215
3.
(1)
V1
510
V3
V6
V2
V5
V4
20
30
100
60
15
50
(2)
10
1 2 3 4 5 6
1 0 5 ∞ ∞ ∞ ∞
2 ∞ 0 50 ∞ ∞ 10
3 ∞ ∞ 0 ∞ 15 ∞
4 ∞ ∞ 20 0 60 ∞
5 ∞ ∞ ∞ ∞ 0 ∞
6 ∞ ∞ ∞ 30 100 0
(3)
DFS 序列：V1,V2,V3,V5,V6,V4
DFS 生成樹：
V1 5
10
V3
V6
V2
V5
V430
15
50
(4)拓撲序列：V1,V2,V6,V4,V3,V5
(5)
V1 (1) (2) (3) (4) (5)
V2 (V1,V2)
5
X X X X
V3 ∞ (V1,V2,V3)
55
(V1,V2,V3)
55
(V1,V2,V3)
55
X
V4 ∞ ∞ (V1,V2,V6,V4)
45
X X
V5 ∞ ∞ (V1,V2,V6,V5)
115
(V1,V2,V6,V4,V5)
105
(V1,V2,V3,V5)
70
V6 ∞ (V1,V2,V6)
15
X X X
u
(u,v)
長度
V2
(V1,V2)
5
V6
(V1,V2,V6)
15
V4
(V1,V2,V6,V4)
45
V3
(V1,V2,V3)
55
V5
(V1,V2,V3,V5)
70
4.
(1)
關鍵字 26 36 41 38 44 15 68 12 06 51 25
HASH 函數值 4 3 8 5 0 4 2 1 6 7 3
比較次數 1 1 1 1 1 3 1 1 2 3 8
H(k)=k%11, 數組范圍：0~10
下標 0 1 2 3 4 5 6 7 8 9 10
關鍵字 44 12 68 36 26 38 15 06 41 51 25
沖突關鍵字 25 15 06 51
11
(2)
α=n/m=11/11=1
(3)
1 1 23
() (1 7 2 1 3 2 8 1)
11 11
i
ASL c
n
? ? ? ? ? ? ? ? ? ??
(4)
不能真正地“物理”刪除,只能做“刪除標記”,否則將截斷在它之后填入散列表的同義詞結
點的查找路徑。
5.
{16,3,7,12,9,28,25,18,14,20}
12
7 18
93 2516
14 20 28
12
7 25
93 2816
14 18
20
12
7 25
93 2816
12
7 16
93 28
7
3 12
9 16
7
3 16
12
9
7
3 16
16
3
7
LR LL
RL LR
平衡
平衡
平衡
平衡
7
3 12
9 16
28
12
7 16
93 28
25
RR
平衡
6. (1)
(2)
12
鏈式基數排序和其他排序方法的最大區別是各關鍵字之間沒有發生比較。
(3)
初始 22 12 26 40 18 38 14 20 30 16 28
(1) 12 22 26 18 38 14 20 30 16 28 40
(2) 12 22 18 26 14 20 30 16 28 38
(3) 12 18 22 14 20 26 16 28 30
四、簡答題
1.
順序存儲結構 鏈式存儲結構
優
點
存取第 i 個元素方便(隨機存取),O(1) (1) 插入、刪除不需移動元素,只修改指針,修
改指針的時間復雜度為 O(1)；
(2) 不需要預先分配空間,可根據需要動態申
請空間；
(3) 表容量只受可用內存空間的限制。
缺
點
(1) 在作插入或刪除操作時,需移動大量
元素；
(2) 由于難以估計,必須預先分配較大的
空間,往往使存儲空間不能得到充分
利用；
(3) 表的容量難以擴充。
(1) 存取第 i 個元素不方便,是 O(n)
2.
（1） 長度 n 為 10 的遞增有序表折半查找的判定樹
如左所示。
（2） 不能改善插入排序的時間復雜度
（3） 原因：插入排序中,用折半查找確定待插入元
素位置,比直接插入排序減少了比較次數,但數
據移動次數沒有改變,排序的時間復雜度也未
改變。
3.
1 93
82
5
6
7 104
13
快速排序的平均時間復雜度為 O(nlogn)。
在關鍵字有序或基本有序的情況下,快速排序將蛻化為起泡排序。
此時的時間復雜度是 O(n
2
)。
為改進之,通?？梢圆捎谩叭呷≈蟹ā?取三者中其關鍵字為中間值的記錄為樞軸,只要將該
記錄和待排序表的第一個關鍵字互換即可,算法不變。
4.算法思想：設 N=(V,{E})是連通網,TE 是 N 上最小生成樹中邊的集合
(1)初始令 U={u0},(u0?V), TE=?
(2)在所有 u?U,v?V-U 的邊(u,v)?E 中,找一條代價最小的邊(u0,v0)
(3)將(u0,v0)并入集合 TE,同時 v0 并入 U.即 TE=TE+{(u0,v0)},U=U+{v0}
(4)重復上述(2),(3)操作直至 U=V 為止,則 T=(V,{TE})為 N 的最小生成樹
對具有 n 個頂點和 e 條邊的連通網而言:
Prim 算法適合于邊稠密的連通網,其時間復雜度為 O(n
2
),與頂點數有關
Kruskal 算法適合于邊稀疏的連通網,其時間復雜度為 O(elog2e),與邊的條數有關
五、算法設計題
1.
算法思想：對鏈表進行遍歷,在每趟遍歷中查找出整個鏈表的最大值元素,輸出并釋放結點所
占空間；再查次最大值元素,輸出并釋放空間,如此下去,直至鏈表為空,最后釋放頭結點所占存
儲空間。
void MiniDelete(linklist head)
∥head是帶頭結點的單鏈表的頭指針,本算法按遞增順序輸出單鏈表中各結點的數據元素,并
釋放結點所占的存儲空間。
{
while(head->next!=null) ∥循環到僅剩頭結點。
{pre=head； ∥pre 為元素最大值結點的前驅結點的指針。
p=pre->next； ∥p 為工作指針
while(p->next!=null)
{if(p->next->data>=pre->next->data)pre=p；∥記住當前最大值結點的前驅
p=p->next；
}// while(p->next!=null)
cout data；∥輸出元素最大值結點的數據。
q=pre->next；pre->next=q->next; delete q；∥刪除元素值最大的結點 q,釋放結點空
間
}∥ while(head->next!=null)
delete head；∥釋放頭結點。
}// MiniDelete
2.(10 分)
算法思想：在樹中先找值為 item 的結點 p,然后再求以 p 為根的子樹的深度。
int GetSubDepth(BinaryTree p,Type item){
if (p->data = = item) {//找到值為 item 的結點 p
return GetDepth(p);//求以 p 為根的子樹的深度
}
else {//在左、右子樹中繼續尋找值為 item 的結點
if (p->leftChild != NULL) GetSubDepth(p->leftChild, item );
14
if (p->rightChild != NULL) GetSubDepth(p->rightChild, item );
}
}// GetSubDepth
int GetDepth(BinaryTree p){//求子樹 p 的深度
int m,n;
if ( p= = NULL) return 0;//空樹的深度是 0
else {//不是空樹
m=GetDepth(p->leftChild); //求 p 的左子樹的深度
n=GetDepth(p->rightChild); //求 p 的右子樹的深度
return (m>n?m:n)+1;//樹 p 的深度是其左、右子樹深度大者加 1
}
}//GetDepth
免責聲明：本文系轉載自網絡，如有侵犯，請聯系我們立即刪除，另：本文僅代表作者個人觀點，與本網站無關。其原創性以及文中陳述文字和內容未經本站證實，對本文以及其中全部或者部分內容、文字的真實性、完整性、及時性本站不作任何保證或承諾，請讀者僅作參考，并請自行核實相關內容。
|
文章搜索
您現在的位置： 
