全國(guó)計(jì)算機(jī)二級(jí)vb公共基礎(chǔ)知識(shí)總結(jié)(已修改)
2025-06-12 04:30 本頁(yè)面
【正文】 公共基礎(chǔ)知識(shí) 二級(jí)公共基礎(chǔ)知識(shí)總結(jié)(30分：10選擇+5填空) 第一章 數(shù)據(jù)結(jié)構(gòu)與算法 一． 算法 ?。菏墙忸}方案的準(zhǔn)確而完整的描述。算法不等于程序，也不等于計(jì)算方法。 ?。骸。?）確定性，算法中每一步驟都必須有明確定義，不允許有模棱兩可的解釋，不允許有多義性； ?。?）有窮性，算法必須能在有限的時(shí)間內(nèi)做完，即能在執(zhí)行有限個(gè)步驟后終止；?。?）可行性，算法原則上能夠精確地執(zhí)行；?。?）擁有足夠的情報(bào)?！ 。阂皇菍?duì)數(shù)據(jù)對(duì)象的運(yùn)算和操作；二是算法的控制結(jié)構(gòu)?！。阂粋€(gè)計(jì)算機(jī)系統(tǒng)能執(zhí)行的所有指令的集合?！。核阈g(shù)運(yùn)算、邏輯運(yùn)算、關(guān)系運(yùn)算、數(shù)據(jù)傳輸?！。喉樞蚪Y(jié)構(gòu)、選擇結(jié)構(gòu)、循環(huán)結(jié)構(gòu)?！。毫信e法、歸納法、遞推、遞歸、減半遞推技術(shù)、回溯法?！。ㄋ惴ㄐ实亩攘浚。?）算法時(shí)間復(fù)雜度：指執(zhí)行算法所需要的計(jì)算工作量。即算法執(zhí)行過程中所需要的基本運(yùn)算次數(shù)。通常，一個(gè)算法所用的時(shí)間包括編譯時(shí)間和運(yùn)行時(shí)間。?。?）算法空間復(fù)雜度：指執(zhí)行這個(gè)算法所需要的內(nèi)存空間。包括算法程序所占的空間，輸入的初始數(shù)據(jù)所占的空間，算法執(zhí)行過程中所需的額外空間?！ 《?數(shù)據(jù)結(jié)構(gòu) ?。褐赶嗷ビ嘘P(guān)聯(lián)的數(shù)據(jù)元素的集合。 ?。ㄒ卜Q數(shù)據(jù)物理結(jié)構(gòu)）：數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)空間中的存放形式 、鏈接、索引、散列。 ?。ò锤髟刂g前后件關(guān)系的復(fù)雜度劃分）：?。?）線性結(jié)構(gòu)的條件：①有且只有一個(gè)根結(jié)點(diǎn)； ②每一個(gè)結(jié)點(diǎn)最多有一個(gè)前件，也最多有一個(gè)后件。?。?）非線性結(jié)構(gòu)：不滿足線性結(jié)構(gòu)條件的數(shù)據(jù)結(jié)構(gòu)?！。骸 ? （1）線性表 ?、?記錄：由若干項(xiàng)數(shù)據(jù)元素組成的數(shù)據(jù)元素?、?文件：由多個(gè)記錄構(gòu)成的線性表。 ?、?線性表的順序存儲(chǔ)結(jié)構(gòu)基本特點(diǎn)： a) 線性表中所有元素所占的存儲(chǔ)空間是連續(xù)的； b) 線性表中各數(shù)據(jù)元素在存儲(chǔ)空間中是按邏輯順序依次存放的 ?、?線性鏈表（線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)） 數(shù)據(jù)結(jié)構(gòu)中的每一個(gè)結(jié)點(diǎn)對(duì)應(yīng)于一個(gè)存儲(chǔ)單元，這種存儲(chǔ)單元稱為存儲(chǔ)結(jié)點(diǎn)，簡(jiǎn)稱結(jié)點(diǎn)?！〗Y(jié)點(diǎn)由兩部分組成： a) 用于存儲(chǔ)數(shù)據(jù)元素值，稱為數(shù)據(jù)域； b) 用于存放指針，稱為指針域，用于指向前一個(gè)或后一個(gè)結(jié)點(diǎn)?！ 镌阪?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，存儲(chǔ)數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)空間可以不連續(xù)，各數(shù)據(jù)結(jié)點(diǎn)的存儲(chǔ)順序與數(shù)據(jù)元素之間的邏輯關(guān)系可以不一致，而數(shù)據(jù)元素之間的邏輯關(guān)系是由指針域來(lái)確定的?！ 镦?zhǔn)酱鎯?chǔ)方式即可用于表示線性結(jié)構(gòu)，也可用于表示非線性結(jié)構(gòu)。 ★鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)需要更多地存儲(chǔ)空間?。?）?！、?限定在一端（即棧頂）進(jìn)行插入與刪除的線性表。 ?、?棧頂位置用指針top表示。棧底位置用指針bottom表示?！、?棧按照“先進(jìn)后出”（FILO）或“后進(jìn)先出”（LIFO）組織數(shù)據(jù)，棧具有記憶作用?！ 、?棧的存儲(chǔ)方式有順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)?！、?棧的基本運(yùn)算： a) 入棧運(yùn)算，在棧頂位置插入元素； b) 退棧運(yùn)算，刪除元素(取出棧頂元素并賦給一個(gè)指定的變量)； c) 讀棧頂元素，將棧頂元素賦給一個(gè)指定的變量，此時(shí)指針無(wú)變化?！ ? ⑥ 棧的元素個(gè)數(shù)=bottomtop+1 （3）隊(duì)列?、?指允許在一端（隊(duì)尾）進(jìn)入插入，而在另一端（隊(duì)頭）進(jìn)行刪除的線性表。 ?、?用rear指針指向隊(duì)尾，用front指針指向隊(duì)頭元素的前一個(gè)位置?！ 、?隊(duì)列是“先進(jìn)先出”（FIFO）或“后進(jìn)后出”（LILO）的線性表?！ 、?隊(duì)列運(yùn)算包括： a) 入隊(duì)運(yùn)算：從隊(duì)尾插入一個(gè)元素； b) 退隊(duì)運(yùn)算：從隊(duì)頭刪除一個(gè)元素?！、?隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)一般采用隊(duì)列循環(huán)的形式?！ ⊙h(huán)隊(duì)列s=0表示隊(duì)列空；s=1且front=rear表示隊(duì)列滿?！ 、?循環(huán)隊(duì)列的元素個(gè)數(shù)： frontrear時(shí)，元素個(gè)數(shù)=rearfront； frontrear時(shí)，元素個(gè)數(shù)=n（循環(huán)隊(duì)列容量）front+rear 7．非線性結(jié)構(gòu) （1）樹 ?、?每一個(gè)結(jié)點(diǎn)只有一個(gè)前件，稱為父結(jié)點(diǎn)。 ?、?沒有前件的結(jié)點(diǎn)只有一個(gè)，稱為樹的根結(jié)點(diǎn)，簡(jiǎn)稱樹的根?！ 、?每一個(gè)結(jié)點(diǎn)可以有多個(gè)后件，稱為該結(jié)點(diǎn)的子結(jié)點(diǎn)。 ?、?沒有后件的結(jié)點(diǎn)稱為葉子結(jié)點(diǎn)?！、?一個(gè)結(jié)點(diǎn)所擁有的后件的個(gè)數(shù)稱為該結(jié)點(diǎn)的度，所有結(jié)點(diǎn)中最大的度稱為樹的度?！、?樹的最大層次稱為樹的深度?！ 。?）二叉樹 ?、?特點(diǎn)： a) 非空二叉樹只有一個(gè)根結(jié)點(diǎn)； b) 每一個(gè)結(jié)點(diǎn)最多有兩棵子樹，且分別稱為該結(jié)點(diǎn)的左子樹與右子樹?！ 、?滿二叉樹是指除最后一層外，每一層上的所有結(jié)點(diǎn)有兩個(gè)子結(jié)點(diǎn)，則k層上有2k1個(gè)結(jié)點(diǎn)深度為m的滿二叉樹有2m1個(gè)結(jié)點(diǎn)?！⊥耆鏄涫侵赋詈笠粚油?，每一層上的結(jié)點(diǎn)數(shù)均達(dá)到最大值，在最后一層上只缺少右邊的若干結(jié)點(diǎn)?！ 、?基本性質(zhì)： a) 在二叉樹的第k層上，最多有2k1(k≥1)個(gè)結(jié)點(diǎn)； b) 深度為m的二叉樹最多有2m1個(gè)結(jié)點(diǎn)； c) 度為0的結(jié)點(diǎn)（即葉子結(jié)點(diǎn)）=度為2的結(jié)點(diǎn)數(shù)+1； d) 二叉樹總結(jié)點(diǎn)數(shù)=度為0的結(jié)點(diǎn)數(shù)+度為1的結(jié)點(diǎn)數(shù)+度為2的結(jié)點(diǎn)數(shù) e) 具有n個(gè)結(jié)點(diǎn)的二叉樹，其深度至少為[log2n]+1,其中[log2n]表示取
公司管理相關(guān)推薦
鄂ICP備17016276號(hào)-1