2020福大計算機863數據結構與程序設計真題整理

皮卡丘砍木樁 · 發表于 2019-12-23 00:06

2020年的考研終于落幕了，我今年報考的是福大計算機專碩（今年都叫電子信息了，底下有三個方向，計算機技術、軟件工程、人工智能）回想起來這一年還是蠻多感慨的，平時也經常來逛考研幫，感謝考研幫上的學長學姐，特別是那個昵稱盤小兔的學姐，19年的分享帖子寫的很好，而且只要有給他留言都會得到回復。今天就趁著剛考完，知識點還熱乎，我就大概回憶一下真題，給后面考研的21學弟學妹們有一個大概的方向。
?? 今年總體來說英語是中規中矩，然后政治依然是應驗了那句話-政治考多少分不是取決于你多努力，而且取決于肖秀榮的發揮。今年政治是真的絕了，肖老爺子的4套卷命中了很多。就是數學有點坑爹，今年的數學其難無比，考完數學整個人心態都蹦了，差點就不去參加專業課考試了，還好最后堅持下去了。
??言歸正傳，說說專業課吧。今年很多學校后面臨時改考408計算機專業基礎綜合，也就是統考那個。福大依然還是自主命題，考的是863數據結構和程序設計。主要就是C++和數據結構（算法我覺得也算屬于數據結構）。福大16年以及之前的真題有考選擇題，17、*、19連續三年都是大題，今年又是破天荒的考了選擇題。大概分值分布如下：10道選擇題，一題3分，然后合計是30分。程序設計題（C++），3道閱讀程序題12分，3道程序填空題*分，然后合計是30分。數據結構考的題目是6道應用題，合計是60分。最后就是3道算法題了，1道10分，合計是30分。這就是150分卷子的真題分布。
???總體來說，今年福大的專業課題目難度有點低，前面有60-70分的送分題。前面10道選擇題，因為內容比較多，記得不是很清楚。但是除了2道比較難一點，其余的都算簡單。主要是考數據結構和C++的一些基本知識，印象中有：問函數中變量的范圍，受限雙端隊列，連通圖，線索二叉樹，指針的聲明這些。
??C++程序閱讀和填空主要是考察了構造函數、析構函數的概念，還有就是逆序輸出和二分查找這樣的題。
?
?? 數據結構應用題，大概記得如下：
1、給出一段堆排序操作的代碼，讓你證明把完全二叉樹調整為一個二叉堆為什么時間復雜度為O(n)。（白皮書出現過，以前也有這個類似的題目）
2、哈夫曼樹的構造，要求寫出詳細構造過程，并計算節省了多少位編碼。（求散列的編碼和正常差多少，白皮書上面出現過）。
3、給出一個中綴表達式，要求用棧轉化成后綴表達式，（白皮書原題）
4、一棵近似滿二叉樹若第6層(第一層高度算1)有8個葉子節點，問該樹最多含有多少個節點.
5、給出parent[e]的意義:若e點為所在樹的根，那么parent[e]就是該樹的節點總數的相反數。若e點不是所在樹的根節點，則paren[e]為e點所在樹的根結點。（白皮書上練習過得題目，主要就是考察并查集了。考試之前葉神有提起過幾次，所以印象比較深）
6、 A*L樹，如果*節點是分支節點，若把*刪除以后新形成了一棵A*L樹B,問若把*點再加入B中，是否會變成A。若會請證明，不會請舉反例。（白皮書和最后六套卷練習幾次），還有一個就是問無相連通圖變成最小生成樹，無向圖的最小邊一定在生成樹中。
?
算法題：
1、皮卡丘砍木樁，喜歡從短的到長的砍，木樁按照重量從小到大排序，每次排序時只能對相鄰的木樁進行交換，求最少交換次數。（冒泡排序改進問題吧，王曉東課件和書本說過）
2、有n個股票經紀，彼此之間有的可以互相通信，有的無法通信，其中任何兩個人通信所需的時間不同。求選取哪一個經紀人可以保證其與其余任意一個經紀人通信耗時最短。（單源路徑最短問題）
3、在X軸上水平放置著 N 個條形圖，這 N 個條形圖就組成了一個柱狀圖，每個條形圖都是一個矩形，每個矩形*相同的寬度，均為1單位長度，但是它們的高度并不相同。計算柱狀圖中以X軸為底邊的最大矩形的面積（王曉東老師課本原原本本的題目，一字不改）
?? 總的來說，今年福大計算機專業課難度不高，大家考完都還是比較激動，我們那個考場有幾個提前半個小時就交卷了。這個倒是出乎以前對福大專業課的認識。
??最后說下對專業課這塊的復習心得吧，主要復習用書
1、王曉東數據結構（C語言描述）修訂版或者今年新出了一個第四版
2、錢能的C++程序設計清華大學出版社但是我后面還是聽學長學姐的使用的是譚浩強老師的C++程序設計，感覺還過得去。
3、輔助用書強烈推薦福大計算機白皮書了，這個也是去年考上的學長學姐極力推薦的。今年用起來感覺很贊，特別是今年福大計算機的真題很多都出自白皮書的原題或者類似題，我都懷疑命題老師是不是看著白皮書出題的。
?最后祝自己能夠取得一個好成績，順利進入福大復試吧。也祝愿21的學弟學妹們，考研加油，考研順利！

來自Android客戶端