|
算法 + 數(shù)據(jù)結(jié)構(gòu)=程序 算法通常是決定程序效率的關(guān)鍵，但一切算法最終都要在相應(yīng)的數(shù)據(jù)結(jié)構(gòu)上實(shí)現(xiàn)。 數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)存儲(chǔ)、組織數(shù)據(jù)的方式，是指相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。許多算法的精髓就是在于選擇了合適的數(shù)據(jù)結(jié)構(gòu)作為基礎(chǔ)。
1、數(shù)據(jù)結(jié)構(gòu)要適應(yīng)問(wèn)題的狀態(tài)描述。在程序中，要涉及到狀態(tài)的存儲(chǔ)、轉(zhuǎn)換等。選擇的數(shù)據(jù)結(jié)構(gòu)必需先適用于描述狀態(tài)，并使對(duì)狀態(tài)的各種操作能夠明確地定義在數(shù)據(jù)結(jié)構(gòu)上。 2、數(shù)據(jù)結(jié)構(gòu)應(yīng)與所選擇的算法相適應(yīng)。數(shù)據(jù)結(jié)構(gòu)是為算法服務(wù)的，其選擇要充分考慮算法的各種操作。 數(shù)據(jù)結(jié)構(gòu)對(duì)算法的影響： 1、數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)能力。如果數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)能力強(qiáng)、存儲(chǔ)信息多，算法將會(huì)較好設(shè)計(jì)。反之對(duì)于過(guò)于簡(jiǎn)單的數(shù)據(jù)結(jié)構(gòu)，可能就要設(shè)計(jì)一套比較復(fù)雜的算法了。在這一點(diǎn)上，經(jīng)常體現(xiàn)時(shí)間與空間的矛盾。 2、定義在數(shù)據(jù)結(jié)構(gòu)上的操作?！皵?shù)據(jù)結(jié)構(gòu)”一詞之所以不同于“變量”，主要在于數(shù)據(jù)結(jié)構(gòu)上定義了基本操作，這些操作就好比工具，有了好的工具，算法設(shè)計(jì)也會(huì)比較輕松。 數(shù)據(jù)結(jié)構(gòu) 根據(jù)數(shù)據(jù)元素之間關(guān)系的不同特性，通?？梢詺w類(lèi)為下列四類(lèi)基本結(jié)構(gòu)： （1）集合結(jié)構(gòu)：元素間關(guān)系僅是同屬一個(gè)集合。 （2）線(xiàn)性結(jié)構(gòu)：元素間存在一對(duì)一的關(guān)系。 （3）樹(shù)形結(jié)構(gòu)：元素間的關(guān)系是一對(duì)多的關(guān)系。 （4）圖形結(jié)構(gòu)：元素間的關(guān)系是多對(duì)多的關(guān)系。 一、線(xiàn)性結(jié)構(gòu) 線(xiàn)性結(jié)構(gòu)是N個(gè)數(shù)據(jù)元素構(gòu)成的有限序列。線(xiàn)性結(jié)構(gòu)存儲(chǔ)方式分為順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)兩種。 順序存儲(chǔ)結(jié)構(gòu) 平時(shí)使用的數(shù)組就是這種結(jié)構(gòu)，比如Pascal：a:[1..100] oflongint; C++：int a[100]。 當(dāng)需要在順序存儲(chǔ)的線(xiàn)性表中插入一個(gè)數(shù)據(jù)元素時(shí)，需要順序移動(dòng)后續(xù)的元素以“騰”出某個(gè)合適的位置放置新元素。 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)
如果某一線(xiàn)性表，它的每一個(gè)數(shù)據(jù)元素分別是一個(gè)線(xiàn)性表，這樣的二維表在數(shù)據(jù)實(shí)現(xiàn)上通常使用二維數(shù)組。二維數(shù)組的一個(gè)形象比喻：多個(gè)縱隊(duì)形成的方塊 m * n。 數(shù)組地址計(jì)算問(wèn)題 題目描述：已知N*(N+1)/ 2個(gè)數(shù)據(jù)，按行的順序存入數(shù)組b[1],b[2],…中。其中第一個(gè)下標(biāo)表示行，第二個(gè)下標(biāo)表示列。若aij (i>=j,j=1,2,…,,n)存于b[k]中，問(wèn)：k,i,j之間的關(guān)系如何表示？ 答案：K=i*(i-1)/2+j 棧與卡特蘭數(shù)：略，可參考： NOIP初賽復(fù)習(xí)（三）棧與卡特蘭數(shù)>>> 隊(duì)列 先進(jìn)先出。允許插入的一端稱(chēng)為隊(duì)尾(rear)，允許刪除的一端稱(chēng)為隊(duì)頭(front)。 循環(huán)隊(duì)列 頭指針指向隊(duì)列中隊(duì)頭元素的前一個(gè)位置，尾指針指示隊(duì)尾元素在隊(duì)列中的當(dāng)前位置。 二、樹(shù)型結(jié)構(gòu) 基本概念：根、葉子、子樹(shù)。 結(jié)點(diǎn)的度：結(jié)點(diǎn)擁有的子樹(shù)數(shù) 二叉樹(shù)的遍歷和性質(zhì)：略，可參考： NOIP初賽復(fù)習(xí)（四）二叉樹(shù)的遍歷和性質(zhì)>>> 三、圖形結(jié)構(gòu) 圖常用的存儲(chǔ)結(jié)構(gòu)：鄰接矩陣
歐拉圖 歐拉通路(回路)：通過(guò)圖G的每條邊一次且僅一次，而且走遍每個(gè)結(jié)點(diǎn)的通路(回路)，就是歐拉通路(回路)。存在歐拉回路的圖就是歐拉圖。 歐拉回路要求邊不能重復(fù)，結(jié)點(diǎn)可以重復(fù)。筆不離開(kāi)紙，不重復(fù)地走完所有的邊，且走過(guò)所有結(jié)點(diǎn)，也就是所謂的一筆畫(huà)。 歐拉圖或通路的判定 1、無(wú)向連通圖G是歐拉圖，G不含奇數(shù)度結(jié)點(diǎn)(G的所有結(jié)點(diǎn)度數(shù)為偶數(shù))； 2、非平凡連通圖G含有歐拉通路，G最多有兩個(gè)奇數(shù)度的結(jié)點(diǎn)； 3、連通有向圖D含有有向歐拉回路(即歐拉圖)，D中每個(gè)結(jié)點(diǎn)的入度＝出度。 哈密頓圖 哈密頓通路(回路)：通過(guò)圖G的每個(gè)結(jié)點(diǎn)一次，且僅一次的通路(回路)，就是哈密頓通路(回路)。存在哈密頓回路的圖就是哈密頓圖。 每日練習(xí) 1、一個(gè)向量第一個(gè)元素的存儲(chǔ)地址是100,每個(gè)元素的長(zhǎng)度是2,則第5個(gè)元素的地址是( ) 。 A)110 B)108 C) 100 D) 109 2、設(shè)有一個(gè)含有13個(gè)元素的Hash表(0~12),Hash函數(shù)是:H(key)=key% 13,其中% 是求余數(shù)運(yùn)算。用線(xiàn)性探查法解決沖突,則對(duì)于序列(2、８、31、20、19、18、53、27),18應(yīng)放在第幾號(hào)格中( ) 。 A) 5 B) 9 C) 4 D) 0 3、在一個(gè)有向圖中,所有頂點(diǎn)的入度之和等于所有頂點(diǎn)的出度之和的( ) 倍。 A) 1/2 B)1 C) 2 D) 4 4、要使1...8號(hào)格子的訪(fǎng)問(wèn)順序?yàn)?/span>:8、2、6、5、7、3、1、4,則下圖中的空格中應(yīng)填入( )。
A) 6 B) 0 C) 5 D) 3 5、設(shè)棧S和隊(duì)列Q的初始狀態(tài)為空,元素e1,e2,e3,e4,e5,e6依次通過(guò)棧S,一個(gè)元素出棧后即進(jìn)入隊(duì)列Q,若出隊(duì)的順序?yàn)?/span>e2,e4,e3,e6,e5,e1,則棧S的容量至少應(yīng)該為( ) 。 A) 2 B) 3 C) 4 D) 5 6、若已知一個(gè)棧的入棧順序是1，2，3，…，n，其輸出序列為P1，P2，P3，…，Pn，若P1是n，則Pi是( ) A)i B)n-1 C)n-i+1 D)不確定 7、以下哪一個(gè)不是棧的基本運(yùn)算( ) A)刪除棧頂元素 B)刪除棧底的元素 C)判斷棧是否為空 D)將棧置為空棧 8、下面關(guān)于算法的錯(cuò)誤說(shuō)法是( ) A)算法必須有輸出 B)算法必須在計(jì)算機(jī)上用某種語(yǔ)言實(shí)現(xiàn) C)算法不一定有輸入 D)算法必須在有限步執(zhí)行后能結(jié)束 9、在順序表(2，5，7，10，14，15，18，23，35，41，52)中，用二分法查找12，所需的關(guān)鍵碼比較的次數(shù)為( ) A)2 B)3 C)4 D)5 10、無(wú)向圖G=(V，E)，其中V={a,b,c,d,e,f}E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)}對(duì)該圖進(jìn)行深度優(yōu)先遍歷,得到的頂點(diǎn)序列正確的是( ) A) a,b,e,c,d,f B)a,c,f,e,b,d C)a,e,b,c,f,d D)a,b,e,d,f,c 11、某數(shù)列有1000個(gè)各不相同的單元，由低至高按序排列；現(xiàn)要對(duì)該數(shù)列進(jìn)行二分法檢索（binary-search），在最壞的情況下，需檢視（?。﹤€(gè)單元。 A.1000 B. 10 C.100 D. 500 12、線(xiàn)性表若采用鏈表存貯結(jié)構(gòu)，要求內(nèi)存中可用存貯單元地址（ ） A.必須連續(xù) B. 部分地址必須連續(xù) C.一定不連續(xù) D. 連續(xù)不連續(xù)均可 13、下列敘述中，正確的是（?。?/span> A.線(xiàn)性表的線(xiàn)性存貯結(jié)構(gòu)優(yōu)于鏈表存貯結(jié)構(gòu) B.隊(duì)列的操作方式是先進(jìn)后出 C.棧的操作方式是先進(jìn)先出 D. 二維數(shù)組是指它的每個(gè)數(shù)據(jù)元素為一個(gè)線(xiàn)性表的線(xiàn)性表 14、設(shè)循環(huán)隊(duì)列中數(shù)組的下標(biāo)范圍是1～n，其頭尾指針?lè)謩e為f和r，則其元素個(gè)數(shù)為（ ） A.r-f B.r-f+1 C.(r-f) MOD n+1 D.(r-f+n) MOD n 15、表達(dá)式(1+34)*5-56/7 的后綴表達(dá)式為（ ）。 A）1+34*5-56/7 B） -*+1 34 5/56 7 C） 1 34 +5*56 7/- D） 1 34 5* +56 7/- E） 1 34+5 56 7-*/ 16、已知元素（8，25，14，87，51，90，6，19，20），問(wèn)這些元素以怎樣的順序進(jìn)入棧，才能使出棧的順序滿(mǎn)足：8在51前面；90在87的后面；20在14的后面；25在6的前面；19在90的后面。（ ）。（題意是全部進(jìn)棧，再依次出棧） A）20，6，8，51，90，25，14，19，87 B）51，6，19，20，14，8，87，90，25 C）19，20，90，7，6，25，51，14，87 D）6，25，51，8，20，19，90，87，14 E）25，6，8，51，87，90，19，14，20 17、假設(shè)我們用d=(a1,a2,...,a5),表示無(wú)向圖G的5個(gè)頂點(diǎn)的度數(shù)，下面給出的哪（些）組d 值合理（ ）。 A）{5，4，4，3，1} B）{4，2，2，1，1} C）{3，3，3，2，2} D）{5，4，3，2，1} E）{2，2，2，2，2} 18、完全二叉樹(shù)的結(jié)點(diǎn)個(gè)數(shù)為4 * N + 3，則它的葉結(jié)點(diǎn)個(gè)數(shù)為（ ）。 A. 2 * N B. 2 * N - 1 C. 2 * N + 1 D. 2 * N - 2 E. 2 * N + 2 19、二叉樹(shù)T的寬度優(yōu)先遍歷序列為AB C D E F G H I，已知A是C的父結(jié)點(diǎn)，D 是G 的父結(jié)點(diǎn)，F 是I 的父結(jié)點(diǎn)，樹(shù)中所有結(jié)點(diǎn)的最大深度為3（根結(jié)點(diǎn)深度設(shè)為0），可知F的父結(jié)點(diǎn)是（ ）。 A. 無(wú)法確定 B. B C. C D.D E. E 20、在所有排序方法中,關(guān)鍵字比較的次數(shù)與記錄的初始排列次序無(wú)關(guān)的是( ) 。 A) 希爾排序 B) 起泡排序 C) 插入排序 D) 選擇排序 21、已知，按中序遍歷二叉樹(shù)的結(jié)果為：abc 問(wèn)：有多少種不同形態(tài)的二叉樹(shù)可以得到這一遍歷結(jié)果，并畫(huà)出這些二叉樹(shù)。 22、根據(jù)Nocomachns定理，任何一個(gè)正整數(shù)n的立方一定可以表示成n個(gè)連續(xù)的奇數(shù)的和。例如： 13＝1 23＝3+ 5 33＝7+9+11 43＝13+15+17+19 在這里，若將每一個(gè)式中的最小奇數(shù)稱(chēng)為X，那么當(dāng)給出n之后，請(qǐng)寫(xiě)出X與n之間的關(guān)系表達(dá)式。 23、將數(shù)組{32, 74, 25, 53, 28, 43, 86, 47}中的元素按從小到大的順序排列，每次可以交換任意兩個(gè)元素，最少需要交換____次。 24、取火柴游戲的規(guī)則如下：一堆火柴有N 根，A、B 兩人輪流取出。每人每次可以取1根或2 根，最先沒(méi)有火柴可取的人為敗方，另一方為勝方。如果先取者有必勝策略則記為1，先取者沒(méi)有必勝策略記為0。當(dāng)N 分別為100，200，300，400，500 時(shí)，先取者有無(wú)必勝策略的標(biāo)記順序?yàn)?/span>___（回答應(yīng)為一個(gè)由0和/或1組成的字符串） 歷年真題 1．完全二叉樹(shù)有2*N-1的結(jié)點(diǎn)，則它的葉子結(jié)點(diǎn)數(shù)目是（ ）。 A．N-1 B．2*N C．N D．2N-1 E．N/2 2．將數(shù)組{8，23，4，16，77，-5，53，100}中元素從大到小按順序排序，每次可以交換任意兩個(gè)元素，最少要交換（ ）次。 A．4 B．5 C．6 D．7 E．8 3．遞歸過(guò)程和函數(shù)調(diào)用時(shí)，處理參數(shù)和返回地址，通常使用一種稱(chēng)為（ ）的數(shù)據(jù)結(jié)構(gòu)。 A．隊(duì)列 B．多維數(shù)組 C．線(xiàn)性表 D．鏈表 E．棧 4．對(duì)有序數(shù)組{5,13,19,21,37,56,64,75,88,92,100}進(jìn)行二分查找，等概率情況下，查找成功的平均查找長(zhǎng)度（平均比較次數(shù)）是（）。 A．35/11 B．34/11 C．33/11 D．32/11 E．34/10 5．設(shè)T是一棵有n個(gè)定點(diǎn)的樹(shù)，以下說(shuō)法正確的是（ ）。 A．T是聯(lián)通的，無(wú)環(huán)的 B．T是聯(lián)通的，有n-1條邊 C．T是無(wú)環(huán)的，有n-1條邊 D．以上都不對(duì) 6. 對(duì)有序數(shù)組{5, 13, 19, 21, 37, 56, 64, 75, 88，92，100}進(jìn)行二分查找，成功查找元素19的查找長(zhǎng)度（比較次數(shù)）是（ ）。 A.1 B. 2 C. 3 D. 4 7. 在32*32點(diǎn)陣的“字庫(kù)”中，漢字“北”與“京”的字模占用字節(jié)數(shù)之和是（ ）。 A. 512 B. 256 C. 384 D. 128 8. 在關(guān)系數(shù)據(jù)庫(kù)中, 存放在數(shù)據(jù)庫(kù)中的數(shù)據(jù)的邏輯結(jié)構(gòu)以( )為主 9. 歐拉圖G是指可以構(gòu)成一個(gè)閉回路的圖，且圖G的每一條邊恰好在這個(gè)閉回路上出現(xiàn)一次（即一筆畫(huà)成）。在以下各個(gè)描述中，不一定是歐拉圖的是（ ）。 A. 圖G中沒(méi)有度為奇數(shù)的頂點(diǎn) B. 包含歐拉環(huán)游的圖（歐拉環(huán)游是指通過(guò)圖中每邊恰好一次的閉路徑） C. 包含歐拉閉跡的圖（歐拉跡是指通過(guò)圖中每邊恰好一次的路徑） D. 存在一條回路，通過(guò)每個(gè)頂點(diǎn)恰好一次 E. 本身閉跡的圖 10．高度為n的均衡的二叉樹(shù)是指：如果去掉葉結(jié)點(diǎn)及相應(yīng)的樹(shù)枝，它應(yīng)該是高度為n-1的滿(mǎn)二叉樹(shù)。在這里，樹(shù)高等于葉結(jié)點(diǎn)的最大深度，根結(jié)點(diǎn)的深度為0，如果某個(gè)均衡的二叉樹(shù)共有2381個(gè)結(jié)點(diǎn)，則該樹(shù)的樹(shù)高為（）。 A. 10 B. 11 C. 12 D. 13 E. 210 – 1 11．將5個(gè)數(shù)的序列排序，不論原先的順序如何，最少都可以通過(guò)（）次比較，完成從小到大的排序。 A. 6 B. 7 C. 8 D. 9 E. 10 12. 在下列各種排序算法中，不是以“比較”作為主要操作的算法是（）。 A. 選擇排序 B. 冒泡排序 C. 插入排序 D. 基數(shù)排序 13．高度為n的均衡的二叉樹(shù)是指：如果去掉葉結(jié)點(diǎn)及相應(yīng)的樹(shù)枝，它應(yīng)該是高度為n-1的滿(mǎn)二叉樹(shù)。在這里，樹(shù)高等于葉結(jié)點(diǎn)的最大深度，根結(jié)點(diǎn)的深度為0，如果某個(gè)均衡的二叉樹(shù)共有2381個(gè)結(jié)點(diǎn)，則該樹(shù)的樹(shù)高為（）。 A. 10 B. 11 C. 12 D. 13 14．將5個(gè)數(shù)的序列排序，不論原先的順序如何，最少都可以通過(guò)（）次比較，完成從小到大的排序。 A.6 B. 7 C. 8 D. 9 15. 字符串“ababacbab”和字符串“abcba”的最長(zhǎng)公共子串是（）。 A. abcba B. cba C. abc D. ab E. bcba 16. 完全二叉樹(shù)的結(jié)點(diǎn)個(gè)數(shù)為4 * N + 3，則它的葉結(jié)點(diǎn)個(gè)數(shù)為（）。 A. 2 * N B. 2 * N - 1 C. 2 * N + 1 D. 2 * N - 2 E. 2 * N+ 2 17. 平面上有五個(gè)點(diǎn)A(5, 3), B(3, 5), C(2, 1),D(3, 3), E(5, 1)。以這五點(diǎn)作為完全圖G 的頂點(diǎn)，每?jī)牲c(diǎn)之間的直線(xiàn)距離是圖G 中對(duì)應(yīng)邊的權(quán)值。圖G 的最小生成樹(shù)中的所有邊的權(quán)值綜合為（）。 A. 8 B. 7+ 5 C. 9 D. 6+ 5 E. 4+2 2 + 5 18. 一位藝術(shù)史學(xué)家有20000 幅1024* 768 的真彩色（24位）圖像，如果將這些圖像以位圖形式保存在CD 光盤(pán)上（一張CD 光盤(pán)的容量按600M計(jì)算），大約需要（）張CD光盤(pán)。 A. 1 B. 10 C.100 D. 1000 E. 10000 19. 完全二叉樹(shù)的結(jié)點(diǎn)個(gè)數(shù)為11，則它的葉結(jié)點(diǎn)個(gè)數(shù)為（）。 20. 平面上有五個(gè)點(diǎn)A(5, 3), B(3, 5), C(2, 1), D(3, 3), E(5, 1)。以這五點(diǎn)作為完全圖G 的頂點(diǎn)，每?jī)牲c(diǎn)之間的直線(xiàn)距離是圖G中對(duì)應(yīng)邊的權(quán)值。以下哪條邊不是圖G 的最小生成樹(shù)中的邊（）。 A. AD B. BD C. CD D. DE E. EA 21.某大學(xué)計(jì)算機(jī)專(zhuān)業(yè)的必修課及其先修課程如下表所示：
請(qǐng)你判斷下列課程安排方案哪個(gè)（些）是合理的（ ）。 A. C0, C1, C2, C3,C4, C5, C6, C7 B. C0, C1, C2, C3, C4,C6, C7, C5 C. C0, C1, C6, C7,C2, C3, C4, C5 D. C0, C1, C6, C7, C5,C2, C3, C4 E. C0, C1, C2, C3,C6, C7, C5, C4 22. 滿(mǎn)二叉樹(shù)的葉結(jié)點(diǎn)個(gè)數(shù)為N，則它的結(jié)點(diǎn)總數(shù)為（ ）。 A.N B. 2 * N C. 2 * N – 1 D. 2 * N + 1 E. 2N – 1 23. 在下圖中，從頂點(diǎn)（ ）出發(fā)存在一條路徑可以遍歷圖中的每條邊一次，而且僅遍歷一次。
A.A點(diǎn) B. B點(diǎn) C. C點(diǎn) D. D點(diǎn) E. E點(diǎn) 數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)每日練習(xí)參考答案： 1B 2B 3B 4C 5B 6C 7B 8B 9C 10D 11B 12D 13D 14D 15C 16D 17BE 18E 19C 20BD 21：5種 22：n^2-n+1 23：5 24：11011 另：為感謝各位家長(zhǎng)一直以來(lái)對(duì)融科信息學(xué)的信任與支持，在雙十二來(lái)臨之際，特推出雙十二底價(jià)團(tuán)購(gòu)信息學(xué)課程，詳情點(diǎn)擊鏈接→融科教育雙十二同學(xué)“惠”，信息學(xué)課程底價(jià)瘋狂搶?zhuān)?/a>（←點(diǎn)擊鏈接，了解活動(dòng)詳情吧） 長(zhǎng)沙信息學(xué)競(jìng)賽 |
|
|
來(lái)自： 長(zhǎng)沙7喜 > 《信息課》
