考研論壇
標題: 2015年南京郵電大學數據結構初試真題 [打印本頁]
作者: 琴魂醉 時間: 2014-12-28 21:49
標題: 2015年南京郵電大學數據結構初試真題
本帖最后由 琴魂醉 于 2014-12-29 16:08 編輯
2015年數據結構初試題目
只能記得這么多題目了...盡力了...
判斷題（共15題*2分）
1.消除遞歸不一定需要使用棧，此說法
2.稀疏矩陣壓縮存儲后，必會失去隨機存取功能
3.完全二叉樹中，若一個結點沒有左孩子，則它必是葉結點
4.連通分量是無向圖的極大強連通子圖
5.在9階B-樹中，除葉子以外的任意結點的分支數介于5和9之間
6.在平衡二叉樹中，向某個平衡因子不為零的結點的樹中插入一新結點，必引起平衡旋轉
7.10個葉子結點的哈弗曼樹，其高度最小為58.隊列和棧不可以使用散列存儲
選擇題（共15題*2分）
1.以下屬于邏輯結構的是（ ）。
A．順序表 B. 哈希表 C.有序表 D. 單鏈表
2.下列數據中，（ ）是非線性數據結構。
A．棧 B. 隊列 C. 完全二叉樹 D. 堆
3.某線性表中最常用的操作是在最后一個元素之后插入一個元素和刪除第一個元素，則采用（ ）儲方式最節省運算時間。
A．單鏈表 B．僅有頭指針的單循環鏈表 C．雙鏈表 D．僅有尾指針的單循環鏈表
4.循環隊列存儲在數組A[0..m]中，則入隊時的操作為（ ）。
A. rear=rear+1 B. rear=(rear+1) mod (m-1)
C. rear=(rear+1) mod m D. rear=(rear+1)mod(m+1)
5.二叉樹在線索后，仍不能有效求解的問題是（ ）。
A. 先序線索二叉樹中求先序后繼 B．中序線索二叉樹中求中序后繼
C．中序線索二叉樹中求中序前驅 D．后序線索二叉樹中求后序后繼
6.下面幾個符號串編碼集合中，不是前綴編碼的是（ ）。
A．{0,10,110,1111} B．{11,10,001,101,0001} C．{00,010,0110,1000}
D．{b,c,aa,ac,aba,abb,abc}
7.用有向無環圖描述表達式(A+B)*（（A+B）/A），至少需要頂點的數目為( )。
A．5 B．6 C．8 D．9
8.下列關于AOE 網的敘述中，不正確的是（ ）。
A．關鍵活動不按期完成就會影響整個工程的完成時間
B．任何一個關鍵活動提前完成，那么整個工程將會提前完成
C．所有的關鍵活動提前完成，那么整個工程將會提前完成
D．某些關鍵活動提前完成，那么整個工程將會提前完成
9.m 階B-樹是一棵( )
A. m 叉排序樹 B. m 叉平衡排序樹 C. m-1 叉平衡排序樹 D. m+1 叉平衡排序樹
10.關于雜湊查找說法不正確的有幾個( ) 【南京理工大學 2000 一、16 （1.5 分）】
A. 采用鏈地址法解決沖突時，查找一個元素的時間是相同的
B. 采用鏈地址法解決沖突時，若插入規定總是在鏈首，則插入任一個元素的時間是相同的
C. 用鏈地址法解決沖不易引起聚集現象
D. 再哈希法不易產生聚集
11.在下列排序算法中,哪一個算法一趟不能確定一個元素的最終位置（ ）。
A． 直接插入 B. 冒泡排序 C. 快速排序 D. 簡單選擇排序
簡答題（共5題*10分）
1.舉例說明順序隊的“假溢出”現象，并給出解決方案
2.什么是算法?算法有哪些特征?
在程序設計算法中引入“程序步”，是不是"程序步"越少執行效率越高?
3.設T是具有n 個內結點的擴充二叉樹，I 是它的內路徑長度，E 是它的外路徑長度。
（1）試利用歸納法證明E=I+2n, n>=0.
（2）利用（1）的結果試說明：成功查找的平均比較次數s 與不成功查找的平均比較次數u 之間的關系可用公式表示s=(1+1/n)u-1,n>=1。
4.一個圖有0,1,2,3,4,5共6個結點,插入邊(1,0)(1,3)(2,1)(2,3)(3,0)(3,2)(3,4)(4,1)(4,5)
（1）畫出對應的鄰接矩陣
（2）寫出所有強連通分量
5.試畫出從空樹開始，由字符序列(t,d,e,s,u,g,b,j,a,k)構成的二叉平衡樹，并為每一次的平衡處理指明旋轉類型。再次插入字符a，畫出此時的平衡二叉樹
編程題（共4題*10分）
1.實現利用隊列將棧中元素逆置并說明算法
2.已知無向圖采用鄰接表存儲方式，試寫出刪除邊（i，j）的算法。
3.有線性表(a1,a2,…,an),采用單鏈表存儲，頭指針為H，每個結點中存放線性表中一個元素，現查找某個元素值等于X 的結點。分別寫出下面三種情況的查找語句。要求時間盡量少。
（1）線性表中元素無序。（2）線性表中元素按遞增有序。 （3）線性表中元素按遞減有序。
4.給定集合S，S的冪集是指以集合S的所有子集為元素構成的集合，利用遞歸算法編程求集合S的冪集
作者: chenyangnjit 時間: 2014-12-28 22:21
感謝分享
作者: 風兒2015 時間: 2014-12-29 00:14
你還記得好清
作者: 框了框 時間: 2014-12-29 00:21
記得很準
作者: chenhaoma 時間: 2014-12-29 10:27
真厲害 編程題感覺簡單了 簡答題感覺*疼
作者: chenhaoma 時間: 2014-12-29 10:35
我覺得我要是今年考數據結構 肯定得歇菜了
作者: 考研論壇審核 時間: 2014-12-29 16:21
謝謝，已收錄
作者: 鏡水木心 時間: 2014-12-30 15:33
頂一下！
作者: V小羽 時間: 2015-1-4 22:11
在這都能看到南郵的。。
作者: 鐵血上校 時間: 2015-1-10 15:09
樓主記準考證后了吧，也算完成我的一個心愿，我就不再發了。最后一次論壇說話了，感謝論壇，再見南郵！
作者: wenxia789 時間: 2015-9-21 08:15
非常感謝
作者: wenxia789 時間: 2015-9-21 08:38
非常感謝
作者: smileArielle 時間: 2015-9-22 20:07
贊一個
作者: 『愚至零傷 時間: 2015-9-25 20:39
作者: kaoyantaiyuan 時間: 2015-9-30 15:58
不錯不錯
作者: a1091904405 時間: 2015-10-15 00:25
其他年份真題樓主還有么？有沒有答案呀
作者: GodLoveGalaxy 時間: 2015-10-20 22:25
謝謝
作者: 粒穩穩 時間: 2015-10-22 21:12
擴充二叉樹是啥……
作者: 微雨傾晨 時間: 2015-11-17 23:17
樓主印象太深了
作者: Ducati2 時間: 2015-11-18 11:28
粒穩穩 發表于 2015-10-22 21:12
擴充二叉樹是啥……
不存在度為1的結點
作者: 下雨的晚上 時間: 2015-11-18 12:15
頂一下！！
| 歡迎光臨 考研論壇 (http://www.5522pp.com/) |
Powered by Discuz! X3.2 |