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