2020福大計(jì)算機(jī)863數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計(jì)真題整理

皮卡丘砍木樁

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

來自Android客戶端

芭樂香蕉

明年考研的福大本科生給你頂一個(gè)！希望成為真正學(xué)長(zhǎng)^_^

來自iPhone客戶端

崢嶸68

請(qǐng)問 英語難嗎今年 求方法 英語很差 明年考

來自Android客戶端

ChrisPaul666

白皮書哪里可以買呢，21的出了么

來自Android客戶端

皮卡丘砍木樁

芭樂香蕉 發(fā)表于 2019-12-23 00:23
明年考研的福大本科生給你頂一個(gè)！希望成為真正學(xué)長(zhǎng)^_^

學(xué)弟加油！

來自Android客戶端

皮卡丘砍木樁

ChrisPaul666 發(fā)表于 2019-12-23 07:37
白皮書哪里可以買呢，21的出了么

21的我不清楚哈，聽說在改版了

來自Android客戶端

皮卡丘砍木樁

崢嶸68 發(fā)表于 2019-12-23 07:33
請(qǐng)問 英語難嗎今年 求方法 英語很差 明年考

今年我個(gè)人感覺英語不難。除了數(shù)學(xué)，其他都中規(guī)中矩

來自Android客戶端

皮卡丘砍木樁

ChrisPaul666 發(fā)表于 2019-12-23 07:37
白皮書哪里可以買呢，21的出了么

之前有一個(gè)昵稱盤小兔的學(xué)姐發(fā)的帖子，上面有寫獲取方式。你自己搜搜看吧

來自Android客戶端

Sun灬2019

普通211本科想跨考計(jì)算機(jī)，自己學(xué)過一些計(jì)算機(jī)的課，有一定的計(jì)算機(jī)基礎(chǔ)。因?yàn)槭强缈记蠓€(wěn)，考研還是決定報(bào)考個(gè)好點(diǎn)的211學(xué)校，有看過過暨南大學(xué)，福州大學(xué)啥的，現(xiàn)在還沒決定考哪個(gè)學(xué)校，學(xué)長(zhǎng)有什么推薦的學(xué)校嗎？以及對(duì)跨考生的建議？祝學(xué)長(zhǎng)順利上岸

來自Android客戶端

皮卡丘砍木樁

Sun灬2019 發(fā)表于 2019-12-24 12:30
普通211本科想跨考計(jì)算機(jī)，自己學(xué)過一些計(jì)算機(jī)的課，有一定的計(jì)算機(jī)基礎(chǔ)。因?yàn)槭强缈记蠓€(wěn)，考研還是決定報(bào) ...

性價(jià)比來說，福州大學(xué)更高一些。畢竟理工科學(xué)校，比較重視計(jì)算機(jī)學(xué)科發(fā)展，投入也比較大。暨南大學(xué)是綜合類學(xué)校，相對(duì)來說計(jì)算機(jī)學(xué)科重視不夠。從今年專業(yè)課難度來看，兩個(gè)學(xué)校難度差不多。報(bào)考人數(shù)可能暨南大學(xué)會(huì)多一些，錄取人數(shù)福大多一些。暨南大學(xué)就是有地理位置優(yōu)勢(shì)。

來自Android客戶端