|
友情提示：本站提供全國400多所高等院校招收碩士、博士研究生入學考試歷年考研真題、考博真題、答案，部分學校更新至2012年，2013年；均提供收費下載。 下載流程： 考研真題 點擊“考研試卷””下載; 考博真題 點擊“考博試卷庫” 下載
2016年全國碩士研究生入學考試招生單位自命題試卷 A卷
861（A 卷）第 1 頁，共 7 頁
安徽工業大學 2016 年碩士研究生招生專業基礎課試卷（A 卷）
科目名稱： 數據結構 科目代碼： 861 滿分： 150 分
考生請注意：所有答案必須寫在答題紙上，做在試題紙或者草稿紙上的一律無效！
一、單項選擇題（2 分*15=30 分）
1、在循環雙鏈表的 p 所指結點之后插入 s 所指結點的操作是_____。
A. p->next=s; s->prior=p; p->next->prior=s; s->next=p->next;
B. p->next=s; p->next->prior=s; s->prior=p; s->next=p->next;
C. s->prior=p; s->next=p->next; p->next=s; p->next->prior=s;
D. s->prior=p; s->next=p->next; p->next->prior=s; p->next =s;
2、假設以數組 A[m]存放循環隊列的元素,其頭尾指針分別為 front 和
rear，則當前隊列中的元素個數為_____。
A．(rear-front+m)%m B．rear-front+1
C．(front-rear+m)%m D．(rear-front)%m
3、一個 100*90 的稀疏矩陣，非 0 元素有 10 個整型數，設每個整型數占 2
字節，則用三元組表示該矩陣時，所需的字節數是_______。
A. 60 B. 66 C. 18000 D. 33
4、表達式 a*(b+c)-d 的后綴表達式是______ 。
A．abcd*+- B．abc+*d- C．abc*+d- D．-+*abcd
5、已知廣義表 LS＝((a,b,c),(d,e,f)),運用 Head 和 Tail 函數取出 LS 中
原子 e 的運算是______。
2016年全國碩士研究生入學考試招生單位自命題試卷 A卷
861（A 卷）第 2 頁，共 7 頁
A. Head (Tail (LS)) B. Head (Tail (Head (Tail (LS))))
C. Tail (Head (LS)) D. Head (Tail (Tail (Head (LS))))
6、若某線性表中最常用的操作是在最后一個元素之后插入一個元素和刪
除第一個元素，則采用____存儲方式最節省運算時間。
A. 單鏈表 B. 僅有頭指針的單循環鏈表
C. 雙鏈表 D. 僅有尾指針的單循環鏈表
7、一棵三叉樹中，已知度為 3 的結點數等于度為 2 的結點數，且樹中葉
結點的數目為 13，則度為 2 的結點數目為_______
A．4 B．2 C．3 D．5
8、設森林中有 3 棵樹，其中第 1、第 2 和第 3 棵樹的結點個數分別為 n1、
n2、n3，則與森林對應的二叉樹中根結點的右子樹上的結點個數是
_________。
A．n1 B．n1+ n2 C． n3 D．n2+n3
9、二叉樹在線索化后，下列問題中相對較難解決的是 。
A．先序線索二叉樹中求先序后繼 B．中序線索二叉樹中求中序后繼
C．中序線索二叉樹中求中序前趨 D．后序線索二叉樹中求后序后繼
10、若 n 個頂點的連通圖是一個環，則它有 棵生成樹
A．n B．n-1 C．2n D．n+2
11、有 n 個頂點有向圖，至少需要 條弧才能保證是連通的。
A．n B．n-1 C．2n D．n+2
2016年全國碩士研究生入學考試招生單位自命題試卷 A卷
861（A 卷）第 3 頁，共 7 頁
12、用 DFS 遍歷一個有向無環圖，并在 DFS 算法退棧返回時打印出相應頂
點，則輸出的頂點序列是___________。
A． 逆拓撲有序 B. 拓撲有序 C. 無序 D. DFS 遍歷序列
13、一組記錄的鍵值為（46，74，18，53，14，20，40，38，86，65），
利用堆排序的方法建立的初始堆為 。
A．（14，18，38，46，65，40，20，53，86，74）
B．（14，38，18，46，65，20，40，53，86，74）
C．（14，18，20，38，40，46，53，65，74，86）
D．（14，86，20，38，40，46，53，65，74，18）
14、初始序列已經有序，用直接插入排序算法進行排序，需要比較次數
為 。
A．n2
B．3(n-1) C．n-1 D．n
15、一個圖中包含 k 個連通分量，若按深度優先（DFS）搜索方法訪問所
有結點，則必須用 次深度優先遍歷算法。
A）k B）1 C）k-1 D）k+1
二、填空題（2*10=20 分）
1、已知 n 個結點的二叉樹具有最小路徑長度時，其深度為 k，那么第 k 層
上的結點數為___
2、已知完全二叉樹的第 8 層有 10 個結點，則該二叉樹有_ __個度為 2 的
結點。
2016年全國碩士研究生入學考試招生單位自命題試卷 A卷
861（A 卷）第 4 頁，共 7 頁
3、分別采用堆排序、快速排序、插入排序和歸并排序對初始狀態為遞增
序列的表按遞增順序排序，最省時間的是 算法，最費時是 算法。
4、 法構造的哈希函數肯定不會發生沖突
5、最短路徑的 Floyd 算法的時間復雜度為
6、快速排序的遞歸算法在平均情況下的空間復雜度為
7、已知某二叉樹的后序遍歷序列是 DACBE，中序序列是 DEBAC，則它
的前序遍歷序列是
8、n 個頂點連通圖用鄰接矩陣表示時，該矩陣至少有 個非零元素
9、由帶權為 9，27，18，6，15 的 5 個葉子結點構成一棵哈夫曼樹，則帶
權路徑長度為_____
三、判斷題（對打√ ，錯打× 1 分*10 =10 分）
1、非空的二叉樹一定滿足：某結點若有左孩子，則其中序前驅一定沒
有右孩子（ ）
2、一個樹的葉結點，在先序遍歷和后序遍歷下，皆以相同的相對位置
出現。（）
3、在由 n 個元素組成的有序表上進行折半查找時，對任一個元素進行
查找的長度都不會大于 log2n+1 （ ）
4、哈希函數越復雜，隨機性越好，沖突的概率越小。（ ）
5、在 n 個頂點的無向圖中，若邊數大于 n-1，則該圖必是連通圖。（ ）
6、快速排序算法在數據表為有序時所花費的時間最少。（ ）
2016年全國碩士研究生入學考試招生單位自命題試卷 A卷
861（A 卷）第 5 頁，共 7 頁
7、有向圖 G 的拓撲序列惟一，則其弧數必為 n-1（其中 n 為 G 的頂點
數）。（ ）
8、對于一個堆，無論按二叉樹的層次遍歷還是先序遍歷，都不一定能
得到有序序列。（ ）
9、Hash 表的平均查找長度與處理沖突的方法無關。（ ）
10、線性表的鏈接存儲結構優于順序存儲結構。（ ）
四、應用題（30 分，每小題 5 分）
1、假定一組數據 (30，25，40，18，27，36，50)，按此順序生成一棵二
叉排序樹，并求出在該二叉排序樹上查找成功時的平均查找長度 ASL
2、對于下圖所示的無向連通圖，請用 Prim 算法構造其最小生成樹，設算
法從圖中頂點 1 開始處理。
3、畫出廣義表 L=((x,a),(x,a,(b,e)))存儲結構圖，并利用求表頭 head
和求表尾 tail 給出求解元素 b 過程
4、試圖的鄰接矩陣如下：利用 Dijkstra 算法求源點 1 到
其他各頂點的最短路徑，要求給出相應的求解步驟
V0 V1 V2 V3 V4 V5
0 5
61 4
2 3
6 8
15
13
124
12 9
12
5
20
10
∞ ∞ 10 ∞ 30 100
∞ ∞ 5 ∞ ∞ ∞
∞ ∞ ∞ 50 ∞ ∞
∞ ∞ ∞ ∞ ∞ 10
∞ ∞ ∞ 20 ∞ 60
2016年全國碩士研究生入學考試招生單位自命題試卷 A卷
861（A 卷）第 6 頁，共 7 頁
5、對于序列{ 57,40,38,11,13,34,48,75,6,19,9,7}，從中選出最小的四
個元素：6,7,9,11。若采用堆排序共需要進行多少次比較？為什么？
6、請寫出下列遞歸算法的結果： 若 m=2,n=6,則其返回結果為（ ）
int Ackerman(int m,int n)
{ if (m==0) return(n+1);
else if (m!=0 && n==0) return(Ackerman(m-1,1));
else return(Ackerman(m-1,Ackerman(m,n-1)));}
五、算法設計題（60 分，每小題 12 分）
1、一個帶頭結點的單鏈表 A，其數據元素是字符字母字符、數字字符、其
他字符，設計算法將 A 表分成三個帶頭結點的循環單鏈表 A、B 和 C，分別
含有字母、數字和其它符號的同一類字符，利用原表空間。
2、設具有 n 個結點的完全二叉樹采用順序結構存儲在順序表 BT[1..n]中，
試編寫非遞歸先序遍歷算法。(設 bt 類型為 datatype)
3、編寫算法實現帶頭結點的單鏈表作為存儲結構的兩個遞增有序表 La ，
Lb 進行如下操作：將所有在 Lb 表中存在而 La 表中不存在的結點插入到
La 中，其中 La 和 Lb 分別為兩個鏈表的頭指針。
4、設計一個算法，從具有 n 個頂點的無向圖中刪除一條邊(u,v)。已知無
2016年全國碩士研究生入學考試招生單位自命題試卷 A卷
861（A 卷）第 7 頁，共 7 頁
向圖采用鄰接表方法存儲,u 和 v 分別是一條邊對應的兩個頂點的序號。
5、設計算法在二叉鏈表結構下二叉排序樹 bst 中，求關鍵字 K 所在結點
的層次。 （試題完）
免責聲明：本文系轉載自網絡，如有侵犯，請聯系我們立即刪除，另：本文僅代表作者個人觀點，與本網站無關。其原創性以及文中陳述文字和內容未經本站證實，對本文以及其中全部或者部分內容、文字的真實性、完整性、及時性本站不作任何保證或承諾，請讀者僅作參考，并請自行核實相關內容。
|
文章搜索
您現在的位置： 
