清華大學(xué)美術(shù)學(xué)院2021考研

交叉學(xué)科編程方向

981專業(yè)基礎(chǔ)—信息技術(shù)基礎(chǔ)

考題解析

?

伴隨著專業(yè)一的統(tǒng)考改革，交叉編程方向的專業(yè)二進(jìn)行了一些變動(dòng)。C++和數(shù)據(jù)結(jié)構(gòu)兩大核心考點(diǎn)沒變，在命題的側(cè)重點(diǎn)上更加“務(wù)實(shí)”，更加“直接”。題目的難度分布上也與往年類似，最難的題出自數(shù)據(jù)結(jié)構(gòu)最后一題。

C++在題型上，取消了代碼填空和類的實(shí)現(xiàn)，取代為三道代碼實(shí)現(xiàn)?？疾斓膫?cè)重點(diǎn)在考生解決問題的邏輯能力，審題的細(xì)心和考慮問題的全面性，難度偏簡單。

?

數(shù)據(jù)結(jié)構(gòu)的考核上，取消了名詞解釋和判斷題，取代改三道簡答題，知識點(diǎn)的考察更加的細(xì)致和綜合，強(qiáng)調(diào)對數(shù)據(jù)結(jié)構(gòu)和算法的理解。難度中等。

?

1C++：

●●●?考題?●●●

1. 任何一個(gè)四位正整數(shù)，在它的四位數(shù)字排列中，最大值和最小值相減得到一個(gè)數(shù)值，這個(gè)數(shù)值的最大值和最小值相減，也可以得到一個(gè)數(shù)字。反復(fù)這個(gè)過程，最終總會(huì)得到4176這個(gè)數(shù)字

a)?輸入：任意一個(gè)四位正整數(shù)（保證四位數(shù)值不完全一致）

b)?輸出：反復(fù)運(yùn)算幾次才能得到這個(gè)數(shù)字，輸出次數(shù)

2.?回形順時(shí)針實(shí)現(xiàn)矩陣

a)?輸入，8?行 3 列

b)?輸出：

00000000

34444441

22222221

3.?回形順時(shí)針輸出矩陣

a)?輸入 4 4（四行四列）

1?2 3 4

5?6 7 8

9?10 11 12

13 14 15 16

輸出

1?2 3 4 8 12 16 15 14 13 9 5 6 7 11 10

C++這一部分的改動(dòng)，對同學(xué)們的復(fù)習(xí)實(shí)則影響不大。第1題的命題思路很像2018年真題“相親數(shù)”。披著“數(shù)論”的外衣，提出一個(gè)概念或規(guī)律，仔細(xì)讀下來底層邏輯很簡單。

2，3題目命題思路類似2010的區(qū)域填充，和“矩陣”本身關(guān)系不大，考察的是處理輸入和輸出的格式。相信大多數(shù)同學(xué)們也都選擇了C++三道題為主要的拿分題。

和以往的命題風(fēng)格不同的是，本次特別增加了輸入格式和輸出格式，其中也蘊(yùn)含了一些細(xì)節(jié)，

如輸入條件的判斷：第1題：保證四位數(shù)值不完全一致；第2題：輸入內(nèi)容包含了數(shù)值和字符串等。

?

復(fù)習(xí)建議：

C++考查弱化了C++語言技術(shù)細(xì)節(jié)，強(qiáng)化了解題邏輯。對同學(xué)們來說C++的備考也變得更加輕松和有針對性，對教材的依賴減輕，對技術(shù)細(xì)節(jié)的比如指針和模版類等的記憶負(fù)擔(dān)也減輕了。同學(xué)們應(yīng)在日后的復(fù)習(xí)中，多刷題，多多積累題目邏輯，培養(yǎng)題目的敏感性；

另外一定要提前練習(xí)手寫代碼，去規(guī)避一些容易出現(xiàn)的筆誤陷阱。?

??

2算法與數(shù)據(jù)結(jié)構(gòu)：

題型以簡答為主，難度中等。綜合分析看來，數(shù)據(jù)結(jié)構(gòu)以往題型：名詞解釋過于簡單，判斷題的隨機(jī)性和不確定性較大，單從T/F去判斷學(xué)生對數(shù)據(jù)結(jié)構(gòu)的完整理解其實(shí)過于武斷，相比而言，簡單題是考查知識點(diǎn)的最客觀的途徑。

第一題側(cè)重于對算法基本思想和概念的理解，難度簡單。

●●● 題目?●●●

1. nlogn=O(lognn)是否正確，為什么？

2.?逆波蘭表達(dá)式

3.?Kmp next數(shù)組求解

第一小題，考查了算法復(fù)雜度分析，對大O記號的理解，教材位于第一章。

第二小題逆波蘭表達(dá)式已經(jīng)出現(xiàn)在三年的真題中（2017，2018，2020），屬于基礎(chǔ)概念考察。教材位于棧章節(jié)。

第三小題考查了串匹配算法中的經(jīng)典實(shí)現(xiàn)KMP算法，next數(shù)組是其算法思想的核心，位于教材較后的位置，串章節(jié)。

?

第二大題整體側(cè)重于對數(shù)據(jù)結(jié)構(gòu)的理解和不同數(shù)據(jù)結(jié)構(gòu)之間的聯(lián)系。涉及向量，棧，堆和排序算法。

●●● 題目?●●●

1. 向量如何構(gòu)造棧，有什么注意點(diǎn)

2. 二叉堆的構(gòu)造，如何保證o(n)

3. 歸并排序和快速排序?yàn)槭裁丛谶f歸到一定深度時(shí)要換成樸素的排序算法，影響因素有哪些？

第一小題：棧的特點(diǎn)

第二小題：堆，F(xiàn)loyd建堆法

第三小題：排序算法的優(yōu)化，歸并和快排本質(zhì)都是基于分治思想實(shí)現(xiàn)的，從分治復(fù)雜度角度分析即可。

?

第三題側(cè)重算法應(yīng)用

●●● 題目?●●●

用BFS判斷是否為二部圖，寫出算法和時(shí)間復(fù)雜度

算法設(shè)計(jì)考查了圖算法。因?yàn)槠渲猩婕暗亩繄D屬于拓展的數(shù)據(jù)結(jié)構(gòu)，需要同學(xué)們在教材以外自行拓展，相應(yīng)增加了難度。在了解二部圖定義后，題目就轉(zhuǎn)化為了BFS求解聯(lián)通域的基本問題，在教材射程以內(nèi)。

和往年的數(shù)據(jù)結(jié)構(gòu)優(yōu)化思路有所不同，今年側(cè)重于算法應(yīng)用以及與數(shù)據(jù)結(jié)構(gòu)的結(jié)合。?

?

復(fù)習(xí)建議：

數(shù)據(jù)結(jié)構(gòu)的知識點(diǎn)貫穿全書，算法復(fù)雜度分析，向量，棧，堆向來是往年的高頻考點(diǎn)。算法思想和基本概念的考查都仍以教材為重，對于教材中涉及的和數(shù)據(jù)結(jié)構(gòu)密切相關(guān)的算法，應(yīng)著重復(fù)習(xí)。在數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)上由于教材的描述過于細(xì)致和繁瑣，不適合命題，因此同學(xué)們應(yīng)掌握提煉思想的能力，并適當(dāng)?shù)倪M(jìn)行一些拓展。

?

3總結(jié)

總體來說專業(yè)二的難度不大，同學(xué)們得高分還是很容易的，此時(shí)的比拼就在于選題策略和細(xì)心上。盡管題型有所改變，但就復(fù)習(xí)路徑來說，變化不大，同學(xué)們按照基本的知識體系框架，按部就班地進(jìn)行即可。

最后祝愿大家取得理想的成績，馬到功成～