計(jì)算機(jī)二級(jí)公共基礎(chǔ)知識(shí)匯總-wenkub
2023-04-09 12:08:07 本頁(yè)面
【正文】 環(huán)使用。 隊(duì)列及其基本運(yùn)算 隊(duì)列是指允許在一端（隊(duì)尾）進(jìn)入插入，而在另一端（隊(duì)頭）進(jìn)行刪除的線性表。即棧是按照“先進(jìn)后出”或“后進(jìn)先出”的原則組織數(shù)據(jù)的。插入、刪除運(yùn)算不方便。 *：順性表的插入運(yùn)算時(shí)需要移動(dòng)元素，在等概率情況下，平均需要移動(dòng)n/2個(gè)元素。 線性表的順序存儲(chǔ)結(jié)構(gòu)具有兩個(gè)基本特點(diǎn)：（1）線性表中所有元素所占的存儲(chǔ)空間是連續(xù)的；（2）線性表中各數(shù)據(jù)元素在存儲(chǔ)空間中是按邏輯順序依次存放的。線性表是由n(n≥0)個(gè)數(shù)據(jù)元素組成的一個(gè) 有限序列，表中的每一個(gè)數(shù)據(jù)元素，除了第一個(gè)外，有且只有一個(gè)前件，除了最后一個(gè)外，有且只有一個(gè)后件?！ 。ㄗ⑨?）前后件關(guān)系：一般情況下，在具有相同特征的數(shù)據(jù)元素集合中，各個(gè)數(shù)據(jù)元素之間存在某種關(guān)系（即聯(lián)系），這種關(guān)系反映了該集合中的數(shù)據(jù)元素所固有的一種結(jié)構(gòu)。 ?。?）線性結(jié)構(gòu)（非空的數(shù)據(jù)結(jié)構(gòu)）條件：1）有且只有一個(gè)根結(jié)點(diǎn)（注釋2）；2）每一個(gè)結(jié)點(diǎn)最多有一個(gè)前件，也最多有一個(gè)后件。 答：模式邏輯模式概念模式 ?。?）對(duì)各種數(shù)據(jù)結(jié)構(gòu)進(jìn)行的運(yùn)算。 3）索引存儲(chǔ)：除建立存儲(chǔ)結(jié)點(diǎn)信息外，還建立附加的索引表來(lái)標(biāo)識(shí)結(jié)點(diǎn)的地址。由此得到的存儲(chǔ)表示稱為順序存儲(chǔ)結(jié)構(gòu)?！ 。?）在對(duì)數(shù)據(jù)進(jìn)行處理時(shí)，各數(shù)據(jù)元素在計(jì)算機(jī)中的存儲(chǔ)關(guān)系，即數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)。算法中各種運(yùn)算總是要施加到各個(gè)運(yùn)算對(duì)象上，而這些運(yùn)算對(duì)象又可能具有某種初始狀態(tài)，這就是算法執(zhí)行的起點(diǎn)或依據(jù)。算法必須在有限的時(shí)間內(nèi)完成。每一條指令的含義明確，無(wú)二義性。 ?。?）可行性。 *：算法不等于程序，也不等于計(jì)算方法。算法 算法是指解題方案的準(zhǔn)確而完整的描述。程序的編制不可能優(yōu)于算法的設(shè)計(jì)（注釋1）。針對(duì)實(shí)際問(wèn)題而設(shè)計(jì)的算法，執(zhí)行后能夠得到滿意的結(jié)果。并且在任何條件下，算法只有唯一的一條執(zhí)行路徑，即相同的輸入只能得出相同的輸出。有兩重含義，一是算法中的操作步驟為有限個(gè)，二是每個(gè)步驟都能在有限時(shí)間內(nèi)完成。因此，一個(gè)算 法執(zhí)行的結(jié)果總是與輸入的初始數(shù)據(jù)有關(guān)，不同的輸入將會(huì)有不同的結(jié)果輸出。 *：綜上所述，所謂算法，是一組嚴(yán)謹(jǐn)?shù)囟x運(yùn)算順序的規(guī)則，并且每一個(gè)規(guī)則都是有效的，且是明確的，此順序?qū)⒃谟邢薜拇螖?shù)下終止。 ?。?）算法時(shí)間復(fù)雜度是指執(zhí)行算法所需要的計(jì)算工作量，可以用執(zhí)行算法的過(guò)程中所需基本運(yùn)算的執(zhí)行次數(shù)來(lái)度量。 例：1) 數(shù)據(jù)結(jié)構(gòu)是指相互有關(guān)聯(lián)的數(shù)據(jù)元素的集合。 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)有順序、鏈接、索引等?！ ?）鏈接存儲(chǔ)?！ ?：數(shù)據(jù)的邏輯結(jié)構(gòu)反映數(shù)據(jù)元素之間的邏輯關(guān)系，數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)（也稱數(shù)據(jù)的物理結(jié)構(gòu)）是數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)空間中的存放形式。 數(shù)據(jù)結(jié)構(gòu)的圖形表示 一個(gè)數(shù)據(jù)結(jié)構(gòu)除了用二元關(guān)系表示外，還可以直觀地用圖形表示。 *：常見(jiàn)的線性結(jié)構(gòu)有線性表、棧、隊(duì)列和線性鏈表等。在數(shù)據(jù)處理領(lǐng)域中，通常把數(shù)據(jù)元素之間這種固有的關(guān)系簡(jiǎn)單地用前后件關(guān)系（即直接前驅(qū)與直接后繼關(guān)系）來(lái)描述。線性表中數(shù)據(jù)元素的個(gè)數(shù)稱為線性表的長(zhǎng)度。 *：由此可以看出，在線性表的順序存儲(chǔ)結(jié)構(gòu)中，其前后件兩個(gè)元素在存儲(chǔ)空間中是緊鄰的，且前件元素一定存儲(chǔ)在后件元素的前面，可以通過(guò)計(jì)算機(jī)直接確定第i個(gè)結(jié)點(diǎn)的存儲(chǔ)地址。 （2）順序表的刪除運(yùn)算：在一般情況下，要?jiǎng)h除第i（1≤i≤n）個(gè)元素時(shí)，則要從第i+1個(gè)元素開(kāi)始，直到第n個(gè)元素之間共ni個(gè)元素依次向前移動(dòng)一個(gè)位置。 棧和隊(duì)列 棧及其基本運(yùn)算 棧是限定在一端進(jìn)行插入與刪除運(yùn)算的線性表。 棧具有記憶作用。尾指針（Rear）指向隊(duì)尾元素，頭指針（front）指向排頭元素的前一個(gè)位置（隊(duì)頭）。在循環(huán)隊(duì) 列中，用隊(duì)尾指針rear指向隊(duì)列中的隊(duì)尾元素，用排頭指針front指向排頭元素的前一個(gè)位置，因此，從頭指針front指向的后一個(gè)位置直到隊(duì)尾指針 rear指向的位置之間，所有的元素均為隊(duì)列中的元素。(2)線性表的順序存儲(chǔ)結(jié)構(gòu)下，線性表的存儲(chǔ)空間不便于擴(kuò)充。另一部分用于存放指針，稱為指針域，用于指向該結(jié)點(diǎn)的前一 個(gè)或后一個(gè)結(jié)點(diǎn)(即前件或后件)，如下圖所示： 線性鏈表分為單鏈表、雙向鏈表和循環(huán)鏈表三種類型。 *：在線性鏈表中插入元素時(shí)，不需要移動(dòng)數(shù)據(jù)元素，只需要修改相關(guān)結(jié)點(diǎn)指針即可，也不會(huì)出現(xiàn)“上溢（注釋1）”現(xiàn)象?！ ?4)將一個(gè)線性鏈表按要求進(jìn)行分解?！ ?8)線性鏈表的查找?！? 與前面所討論的線性鏈表相比，循環(huán)鏈表具有以下兩個(gè)特點(diǎn)：1)在鏈表中增加了一個(gè)表頭結(jié)點(diǎn)，其數(shù)據(jù)域?yàn)槿我饣蛘吒鶕?jù)需要來(lái)設(shè)置，指針域指向線性表的第一 個(gè)元素的結(jié)點(diǎn)，而循環(huán)鏈表的頭指針指向表頭結(jié)點(diǎn)。二是由于在循環(huán)鏈表中設(shè)置了一個(gè)表頭結(jié)點(diǎn)，在任何情況下，循環(huán)鏈表中至少有一個(gè)結(jié)點(diǎn)存在，從而使空表與非空表的運(yùn)算統(tǒng)一?！ ∽⑨?：在鏈表中，即使知道被訪問(wèn)結(jié)點(diǎn)的序號(hào)i，也不能像順序表中那樣直接按序號(hào)i訪問(wèn)結(jié)點(diǎn)，而只能從鏈表的頭指針出發(fā)，順著鏈域逐個(gè)結(jié)點(diǎn)往下搜索，直至搜索到第i個(gè)結(jié)點(diǎn)為止。 在樹(shù)結(jié)構(gòu)中，每一個(gè)結(jié)點(diǎn)只有一個(gè)前件，稱為父結(jié)點(diǎn)。 在樹(shù)結(jié)構(gòu)中，一個(gè)結(jié)點(diǎn)所擁有的后件的個(gè)數(shù)稱為該結(jié)點(diǎn)的度，所有結(jié)點(diǎn)中最大的度稱為樹(shù)的度。 *：根據(jù)二叉樹(shù)的概念可知，二叉樹(shù)的度可以為0(葉結(jié)點(diǎn))、1(只有一棵子樹(shù))或2(有2棵子樹(shù))。 性質(zhì)4 具有n個(gè)結(jié)點(diǎn)的二叉樹(shù)，其深度至少為[log2n]+1，其中[log2n]表示取log2n的整數(shù)部分。 *：根據(jù)完全二叉樹(shù)的定義可得出：度為1的結(jié)點(diǎn)的個(gè)數(shù)為0或1。 ②若2k≤n，則編號(hào)為k的左子結(jié)點(diǎn)編號(hào)為2k。 二叉樹(shù)的存儲(chǔ)結(jié)構(gòu) 在計(jì)算機(jī)中，二叉樹(shù)通常采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。 *：一般二叉樹(shù)通常采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，對(duì)于滿二叉樹(shù)與完全二叉樹(shù)來(lái)說(shuō)，可以按層序進(jìn)行順序存儲(chǔ)（注釋1） 。并且，在遍歷左右子樹(shù)時(shí)，仍然先訪問(wèn)根結(jié)點(diǎn)，然后遍歷左子樹(shù)，最后遍歷右子樹(shù)。 (3)后序遍歷(LRD)：若二叉樹(shù)為空，則結(jié)束返回。 查找結(jié)果：（查找成功：找到；查找不成功：沒(méi)找到。 在平均情況下，利用順序查找法在線性表中查找一個(gè)元素，大約要與線性表中一半的元素進(jìn)行比較，最壞情況下需要比較n次。 二分法查找 思想：先確定待查找記錄所在的范圍，然后逐步縮小范圍，直到找到或確認(rèn)找不到該記錄為止。最壞的情況下，需要比較log2n次。 注釋1：允許相鄰元素值相等。 選擇類排序法（方法：簡(jiǎn)單選擇排序，堆排序）。主要應(yīng)注重和考慮下述一些因素：符號(hào)名能反映它所代表的實(shí)際東西，應(yīng)有一定的實(shí)際含義。 ?。?）數(shù)據(jù)說(shuō)明。 3）使用注釋來(lái)說(shuō)明復(fù)雜數(shù)據(jù)的結(jié)構(gòu)。 1）在一行內(nèi)只寫一條語(yǔ)句； 5）避免使用臨時(shí)變量而使程序的可讀性下降； 9）盡量減少使用“否定”條件語(yǔ)句； 確保每一個(gè)模塊的獨(dú)立性； （4）輸入和輸出。 3）輸入格式要簡(jiǎn)單，使得輸入的步驟和操作盡可能簡(jiǎn)單； 7）在以交互式輸入/輸出方式進(jìn)行輸入時(shí)，要在屏幕上使用提示符明確提示輸入的請(qǐng)求，同時(shí)在數(shù)據(jù)輸入過(guò)程中和輸入結(jié)束時(shí)，應(yīng)在屏幕上給出狀態(tài)信息；是當(dāng)今主導(dǎo)的程序設(shè)計(jì)風(fēng)格。 結(jié)構(gòu)化程序設(shè)計(jì)（面向過(guò)程的程序設(shè)計(jì)方法） 結(jié)構(gòu)化程序設(shè)計(jì)方法的主要原則可以概括為：自頂向下，逐步求精，模塊化，限制使用goto語(yǔ)句。 ?。?）逐步求精。模塊化是把程序要解決的總目標(biāo)分解為分目標(biāo)，再進(jìn)一步分解為具體的小目
高考資料相關(guān)推薦
鄂ICP備17016276號(hào)-1