本帖最后由 yaamiao 于 2016-12-30 08:59 編輯
【2017年南京郵電大學_數據結構初試_回憶版】
本來只想發這個的，但是想了想還是整合了自己復習一年來收集的各年份的數據結構初試試卷，以及答案解析！！！（雖然是自己寫的orz雖然字寫的賊丑orz但是你不會做又找不到答案的時候可以參考一下下....）
絕大部分試卷來源于論壇dalao 陳楊@chenyangnjit
剩余一部分是自己網上收集的！
2017年的回憶版是自己回憶的！
答案解析是自己寫的筆記，供大家找不到答案的時候參考用的！絕不代表完全正確和最優解！！（嘛~絕大部分都是正確的啦(`?ω?′)ゞ ）
回憶版，不提供具體題目，可能會有偏差，請勿廣泛傳播（意思就是說傳播的時候低調點orz） 照著前2-3年南郵數據結構出題的尿性，我是抱著10判斷10選擇5解答4算法的題型準備的，而且重點抓了這兩年出題的形勢，一些面試遞歸題啊，一些九幾年的北郵、西電數據結構試卷啊，歷年南郵的試卷題目啊，王道書上的基本概念和一些習題啊（后期發現編程題沒時間做了...）。結果發了卷子居然變成沒有判斷，20個選擇，8個解答題，3個編程題。對手工模擬以及一些書本知識的理論加強了考察，而實際編程的份額居然被弱化了... 實際操作起來不是很困難，解答題有些內容沒復習過就懵逼了，算法題有一題把樹看成了二叉樹，用左右子樹的結構體寫的一身勁....（我已經是一條廢狗了orz）
下面不多說，上題目 一、選擇題【對！它上面寫的就是選擇題！寫成單選題好嘛！強迫癥受不了啊！】 20個選擇（20*2=40）考完就忘，選擇是啥？有這種題？十分基礎，沒什么難題。實在不會就舉個特例...
二、解答題【題號不對應，共8個解答（8*10=80）】 1>.for(i=1;i<=n;i++){ for(j=1;j<=i;j++){ for(k=1;k<=j;k++){ K++; } } } 問k++這條語句的執行頻度是多少？問該算法的時間復雜度是多少？
2>.給12個數，要求建立小根堆，并給出詳細的過程
3>.給出一個有序序列，要求1.畫出二叉判定樹 2.求ASL成功
4>.B-樹的插入，插入一個數，我記得只做了兩次分裂就搞定了
B-樹的刪除，刪除的是非葉子結點，直接與最左下交換然后刪除它就結束了，沒有合并。
5>.散列表的填寫，給了一個散列表，表長11，里面給你填了三個數，用除留取余發構造散列函數，給了四個數讓你順序填入散列表中，用二次探測法解決沖突。
6>.“計數排序法”，（就是一種每次從一個數組存儲的序列中依次挑出每一個數）問你這種排序方法給n個元素排序要比較多少次 問你這種排序方法和簡單選擇排序相比，誰更好？（我寫的是因為計數排序法要多用一個數組來保存排序數據，所以空間復雜度是O（n），于是果斷覺得簡單選擇好！！）
7>.證明深度優先遍歷一個連通圖的每條邊，總是能得到一棵樹（這題我題目沒看懂，感覺往生成樹的方向寫？）
8>.棧的應用：給了一串中序操作數和操作符，讓你求值并寫出棧的變化過程，最后還問了最小棧容量是多少。（這串操作數我回憶一下，貌似是1422*21/-3^2+ 大概是這個形式，具體的實在記不清了= = 反正加減乘除乘方都有了）
三、算法設計題（一共3題 3*10=30） 1.運用數據結構中所學知識，設計一個算法求樹的帶權路徑長度。
2.運用數據結構中所學知識，設計一個算法求二叉樹中指定結點的深度。
3.運用數據結構中所學知識，設計一個算法將一個圖的鄰接表表示轉換成鄰接矩陣表示。
這三道算法題都不難，就算沒有做過類似題目考中了也不用慌，抓住基本數據結構體，知道怎么調用里面的成員，比多背多做兩個題賭他出原題的效果好（但是我看錯題了orz）
【總結】 做了十幾年的南郵數據結構真題，有很多卷子都是學長學姐們傳遞出來的，我非常感謝他們，“計利當計天下利”我想將這根接力棒傳遞下去。 這幾年南郵數據結構真題的出題形式不是很固定，千萬不要研究過多出題重點，比如說前三年必考的一道遞歸算法題，今年完全消失；比如說99年到10年前后每年必考的圖的四大應用手工模擬，近三年完全沒有涉及（今年我記得就給了個選擇題） 以現在的出題模式來看，他出什么題的可能都有，沒有什么必出題，沒有什么絕對重點，今年考10分的簡答題，明年可能完全不考orz。如果說真的有什么重點，這幾年排序年年考，每年固定一道大題；B-樹這幾年年年考，固定處大題；這幾年二叉樹的算法題年年考，每年固定一道大題。我不想給大家壓重點，因為他的出題根本沒有什么規律，什么都可能出現，什么都可能消失。希望大家端正心態，“全面與重點相結合”，不能因小失大也不能因為思想上的傾向錯失了另一種傾向。 祝大家復習順利(`?ω?′)ゞ ！
| 
發表于 2016-12-26 19:57
收藏
分享
支持
反對
樓主
