文 彥 考 研
讓丨夢(mèng)想丨有跡可循
這是20計算機考研 第 8 篇文章
小魚(yú)學(xué)姐
2017年考入電子科技大學(xué)計算機技術(shù)專(zhuān)業(yè)，專(zhuān)業(yè)課成績(jì)129分，研究生入學(xué)后便開(kāi)始做考研輔導，截止目前已輔導三十多名學(xué)生，擅長(cháng)進(jìn)行大綱、考點(diǎn)剖析，知識點(diǎn)與習題相結合，用通俗的事例讓學(xué)生理解相關(guān)術(shù)語(yǔ)，耐心細致、深受好評。
以下內容由小魚(yú)學(xué)姐分享，小彥整理。
電子科技大學(xué)計算機考研--數據結構習題講解
大家好~我是電子科大計算機學(xué)院的17級的小魚(yú)學(xué)姐，這篇文章我們繼續講解數據結構的課后習題：
01
以下關(guān)于數據結構的說(shuō)法中，正確的是（ ）
A.數據的邏輯結構獨立于其存儲結構
B.數據的存儲結構獨立于其邏輯結構
C.數據的邏輯結構唯一決定了存儲結構
D.數據結構僅由邏輯結構和存儲結構決定
這個(gè)題的正確答案應該是A。
解析：首先，我們再讀一下題目，讓選出關(guān)于DS正確的選項，然后看四個(gè)選項，A和B都在說(shuō)邏輯結構和存儲結構是否獨立，C是邏輯結構能否決定存儲結構，D是決定了數據結構的因素有哪些。關(guān)于邏輯結構和存儲結構，在上一篇文章中已經(jīng)分析了相關(guān)的知識點(diǎn)，這里我們再來(lái)詳細解釋一下它們之間的關(guān)系，首先邏輯結構就是數據元素之間的關(guān)系，它不會(huì )去考慮在內存中是怎么存儲的，所以和存儲沒(méi)有關(guān)系，所以由此可知邏輯結構是獨立于存儲結構的。那么存儲結構（物理結構）和邏輯結構相關(guān)嗎，答案是肯定的，因為存儲結構是邏輯結構的一種體現，一種邏輯結構可能對應多種物理結構，但是這個(gè)物理結構必須是邏輯結構在計算機上的映射，不能獨立于邏輯結構之外單獨存在，所以B選項錯誤。C選項存儲結構是由邏輯結構以及相關(guān)的運算操作共同決定的，所以C選項錯誤。D選項是考查的數據結構的三個(gè)要素，缺一不可，還有一個(gè)是數據的運算。
02
鏈式存儲設計時(shí)，結點(diǎn)內的存儲單元地址（ ）
A.一定連續
B.一定不連續
C.不一定連續
D. 部分連續，部分不連續
正確答案應該選擇：A一定連續。
解析：這個(gè)題目是容易做錯的題，因為審查題目不夠細致，也是很多同學(xué)迷惑的地方，感覺(jué)答案是不是錯了。如果我把這個(gè)題目修改一下：
鏈式存儲設計時(shí)，結點(diǎn)間的存儲單元地址（ ）
A, 一定連續
B.一定不連續
C.不一定連續
D.部分連續，部分不連續
此時(shí)，答案會(huì )截然不同，修改后的題目，可能90%以上的同學(xué)都能做對。因為每個(gè)結點(diǎn)之間的地址是不確定的，每個(gè)結點(diǎn)占用兩個(gè)存儲空間，一個(gè)用來(lái)存儲數據，一個(gè)用來(lái)存儲下一個(gè)結點(diǎn)的地址，這個(gè)地址可能就在下一個(gè)存儲單元，也可能隔了很多個(gè)存儲單元。用一幅圖展示一下：
這是鏈表的兩個(gè)結點(diǎn)，那么它在內存中的存儲形式為：
從內存地址分布可知，一個(gè)結點(diǎn)會(huì )占用兩個(gè)連續的內存單元，所以結點(diǎn)內部地址一定是連續的，但是結點(diǎn)和結點(diǎn)之間的地址是不確定的，可能連續，也可能不連續。
*接下來(lái)，說(shuō)兩個(gè)知識點(diǎn)，一個(gè)是算法的五個(gè)重要的特性和一個(gè)好的算法追求的目標（或者是算法設計的要求）
首先應該先了解什么是算法？
它是對特定問(wèn)題求解步驟的一種描述，是指令的有限序列，一條指令表示一個(gè)或多個(gè)操作。
算法設計的五個(gè)特性：
有窮性：算法應在執行有窮步后結束，并且每一步都可以在有限的時(shí)間內完成。
確定性：每步定義都是確切、無(wú)歧義的，也就是對于相同的輸入只能得出相同的輸出。
可行性：算法中描述的操作都可通過(guò)已經(jīng)實(shí)現的基本運算執行有限次實(shí)現
輸入： 有0個(gè)或多個(gè)輸入，可以沒(méi)有輸入。（我們在學(xué)習各種語(yǔ)言的時(shí)候，一般第一個(gè)代碼都是輸出Hello World，所以可以沒(méi)有輸入，但是必須至少有一個(gè)輸出）
輸出： 有一個(gè)或多個(gè)輸出(處理結果)
算法設計的要求
正確性：
程序不含語(yǔ)法錯誤；
程序對于幾組輸入數據能夠得出滿(mǎn)足要求的結果；
對精心選擇帶有刁難性的幾組數據能得出滿(mǎn)足要求的結果；
程序對于一切合法的輸入數據都能產(chǎn)生滿(mǎn)足要求的結果。
可讀性：易于閱讀和交流，其次是機器運行。
健壯性：
當輸入數據非法時(shí)，算法能適當地作出反應或進(jìn)行處理，保證不會(huì )產(chǎn)生莫名其妙的輸出結果。
處理出錯的方法是返回一個(gè)表示錯誤或錯誤性質(zhì)的值，以便在更高的抽象層次上進(jìn)行處理，不應中斷程序的執行。
高效率和低存儲量需求：
兩者都與問(wèn)題的規模有關(guān)。效率就是該算法所執行的試卷，低存儲量需求是在執行算法的過(guò)程中，需要的最大的存儲空間。
這兩個(gè)知識點(diǎn)在真題中經(jīng)常出現，簡(jiǎn)單一點(diǎn)的是直接考察，但是同學(xué)們千萬(wàn)不要記混淆，出題一般是填空或者是選擇，但是選擇有時(shí)候是從側面考查，不直接問(wèn)你目標包括哪些，而是寫(xiě)了一段代碼，問(wèn)這是為了滿(mǎn)足算法的什么，這種考法就需要我們真正的理解每一個(gè)特性以及目標的含義。例如：
03
在數組中插入一個(gè)元素時(shí)，下列代碼，是符合算法的（ ）
if (i<0)
print(數組越界)
這個(gè)題當時(shí)給的選項是特性和目標摻雜在一起的，很顯然這個(gè)是考查的目標中的健壯性，數據非法的時(shí)候也能做出相應的反應或者相應的處理，不會(huì )產(chǎn)生莫名其妙的錯誤。所以不僅僅要記住內容，還要去真正的理解每個(gè)性質(zhì)表達的含義。
*時(shí)間復雜度vs時(shí)間頻度
一個(gè)算法的效率，是通過(guò)時(shí)間復雜度和空間復雜度面熟的。
時(shí)間頻度，從頻度兩個(gè)字可知，是指算法中語(yǔ)句的頻度之和，是指語(yǔ)句被重復執行的次數，既然是次數就不能存在錯誤，一次和十次是不一樣的。但是時(shí)間復雜度是一個(gè)數量級，用O( )表示，既然是數量級，那么和相應的系數就沒(méi)有關(guān)系，例如O(N)和100000O(N)的時(shí)間復雜度是一樣的。
下篇文章我們繼續分析一些易錯題，以及相應的知識點(diǎn)，把數據結構第一章的分析完后，再進(jìn)行操作系統第一部分的講解。加油o~
同學(xué)們仍有疑惑的話(huà)，歡迎掃碼加入下方考研群，或添加微信，與老師一對一交流。
來(lái)文彥，考上研！報名方式：淘寶搜文彥考研
電子科大計算機考研群號：612630835
我是文彥考研，wyky66666，加小彥微信 獲取更多考研干貨~
文彥成電考研微信公眾號：uestcwykycom
公眾號更多閱讀：
20屆電子科大計算機|你有一份復習攻略，請查收~
20屆成電計算機 | 計算機考研新形勢之（一）：預面試
20屆成電計算機 | 計算機考研新形勢之（二）：初試+復試筆試
20成電計算機 | 暑假來(lái)襲，課后作業(yè)第一彈！
20屆成電計算機 | 計算機考研新形勢之（三）：學(xué)碩/專(zhuān)碩、