全國計算機二級公共基礎學習知識復習

全國計算機二級公共基礎學習知識復習全國計算機二級公共基礎學習知識復習全國計算機二級公共基礎學習知識復習全國計算機二級公共基礎知識一、數(shù)據(jù)構(gòu)造與算法數(shù)據(jù)構(gòu)造指的是數(shù)據(jù)之間的互有關(guān)系，即數(shù)據(jù)的組織形式。數(shù)據(jù)構(gòu)造用來反應一個數(shù)據(jù)的內(nèi)部構(gòu)成，即一個數(shù)據(jù)由哪些成分構(gòu)成、以什么方式構(gòu)成、表現(xiàn)什么樣的構(gòu)造。數(shù)據(jù)構(gòu)造有邏輯上的數(shù)據(jù)構(gòu)造和物理上的數(shù)據(jù)構(gòu)造之分。邏輯上的數(shù)據(jù)構(gòu)造反應數(shù)據(jù)之間的邏輯關(guān)系，而物理上的數(shù)據(jù)構(gòu)造反應數(shù)據(jù)在計算機內(nèi)部的儲蓄安排。數(shù)據(jù)構(gòu)造是數(shù)據(jù)存在的形式。算法是解題的步驟，是指令的有限序列。它們規(guī)定認識決某一特定種類問題的一系列運算，是對解題方案的正確與圓滿的描繪。一個問題的解決方案要以算法為基礎。1.1見解介紹◆算法的時間復雜度：算法的時間復雜度是指履行算法所需要的計算工作量。算法的工作量用算法所履行的基本運算次數(shù)來胸懷，而算法所履行的基本運算次數(shù)是問題規(guī)模的函數(shù)，即算法的工作量=f(n)此中n是問題的規(guī)模。比方，兩個n階矩陣相乘所需要的基本運算(即兩個實數(shù)的乘法)次數(shù)為n3，即計算工作量為n3，也就是時間復雜度為n3?！羲惴ǖ目臻g復雜度：算法的空間復雜度一般是指履行這個算法所需要的內(nèi)存空間?！魯?shù)據(jù)的邏輯構(gòu)造數(shù)據(jù)元素相互之間的關(guān)系，稱為構(gòu)造。數(shù)據(jù)的邏輯構(gòu)造：是指反應數(shù)據(jù)元素之間邏輯關(guān)系的數(shù)據(jù)構(gòu)造?！魯?shù)據(jù)的儲蓄構(gòu)造數(shù)據(jù)的儲蓄構(gòu)造：是數(shù)據(jù)的邏輯構(gòu)造在計算機儲蓄空間中的寄存形式。也稱數(shù)據(jù)的物理構(gòu)造。各數(shù)據(jù)元素在計算機儲蓄空間中的地點關(guān)系與它們的邏輯關(guān)系不用然是同樣的。同一種數(shù)據(jù)的邏輯構(gòu)造能夠依據(jù)需要表示成任意一種或幾種不同樣的儲蓄構(gòu)造。數(shù)據(jù)的序次儲蓄方式：是將邏輯上相鄰的結(jié)點儲蓄在物理地點上亦相鄰的儲蓄單元里。也就是將所有儲蓄結(jié)點接踵存入在一個連續(xù)相鄰的儲蓄區(qū)里。數(shù)據(jù)的鏈式儲蓄方式：是在儲蓄每個結(jié)點信息的同時，增添一個指針來表示結(jié)點間的邏輯關(guān)系。該方式不要求邏輯上相鄰結(jié)點在物理地點上亦相鄰，結(jié)點間的邏輯關(guān)系是由附帶的指針字段表示的。所以，鏈式儲蓄構(gòu)造中的每個結(jié)點都由兩部分構(gòu)成：一部分用于儲蓄結(jié)點自己的信息，稱為數(shù)據(jù)域；另一部分用于儲蓄該結(jié)點的后繼結(jié)點(或前驅(qū)結(jié)點)的儲蓄單元地點，稱為指針域。指針域能夠包含一個或多個指針，這由結(jié)點之間的關(guān)系所決定?！艟€性構(gòu)造和非線性構(gòu)造假如在一個線性構(gòu)造中，一個數(shù)據(jù)元素都沒有，則稱該數(shù)據(jù)構(gòu)造為空數(shù)據(jù)構(gòu)造。線性構(gòu)造的邏輯特色：在一個非空的數(shù)據(jù)構(gòu)造中，除第一個數(shù)據(jù)元素只有一個后繼沒有前驅(qū)、最后一個數(shù)據(jù)元素只有一個前驅(qū)沒有后繼外，其余的每一個數(shù)據(jù)元素僅有一個前驅(qū)和一個后繼。線性構(gòu)造也稱為線性表。注：某個元素直接相鄰的前一個元素稱為此元素的前驅(qū)、直接相鄰的后一個元素稱為此元素的后繼。非線性構(gòu)造的邏輯特色：在一個非空的數(shù)據(jù)構(gòu)造中，某數(shù)據(jù)元素可能有多于一個前驅(qū)或后繼。如樹型構(gòu)造等。習題：（一）選擇題(單項選擇)1.算法的時間復雜度是指（D）A)算法的履行時間B)算法所辦理的數(shù)據(jù)量C)算法程序中的語句或指令條數(shù)D)算法在履行過程中所需要的基本運算次數(shù)1.2線性表線性表是由同一種類的數(shù)據(jù)元素構(gòu)成的一種線性的數(shù)據(jù)構(gòu)造。是一種最基本、最常用的數(shù)據(jù)構(gòu)造。線性表常用的儲蓄方式有兩種：序次儲蓄方式和鏈接儲蓄方式。線性表的數(shù)學定義：L=(a1,a2,a3,…,an)說明：線性表是擁有同樣種類的n(n≥0)個數(shù)據(jù)元素構(gòu)成的有限序列。L：為表的名稱。ai(i=1,2,…,n)：為表的元素，也稱為線性表中的一個結(jié)點。它能夠是一個數(shù)、一個字符、一個字符串，也能夠是一條記錄，還能夠夠是復雜的數(shù)據(jù)對象。a1是a2的前驅(qū)、a2是a1的后繼，a2是a3的前驅(qū)、a3是a2的后繼，…，挨次類推。n：為線性表的長度(元素個數(shù))，當n=0時稱線性表為空表。線性表的特色：在非空的線性表中：存在唯一的一個“第一個元素”(根結(jié)點)。存在唯一的一個“最后一個元素”(終端結(jié)點)。除第一個元素外，其余的元素均有唯一的前驅(qū)。除最后一個元素外，其余的元素均有唯一的后繼。1.3棧和行列棧和行列實質(zhì)上也是線性表，但是它們的操作遇到了限制。1.3.1棧棧是限制僅在表尾進行插入和刪除操作的線性表。表尾稱為棧頂(top)，表頭稱為棧底(bottom)。棧這類數(shù)據(jù)構(gòu)造，近似于子彈夾，底端是關(guān)閉的，最后壓入的子彈老是最初被彈出，最初壓入的子彈只好最后被彈出。棧頂元素老是最后被插入的元素，進而也是最初能被刪除的元素；棧底元素老是最初被插入的元素，進而也是最后能被刪除的元素。即棧是依據(jù)“先進后出”或“后進先出”的原則組織數(shù)據(jù)的。所以，棧也被稱為“先進后出”表或“后進先出”表。由此能夠看出，棧擁有記憶作用。1.3.2行列行列是指只贊成在表的一端插入元素、在另一端刪除元素的線性表。贊成插入的一端稱為隊尾(rear)，贊成刪除的一端稱為隊頭(front)。在行列這類數(shù)據(jù)構(gòu)造中，最初插入的元素將最初能夠被刪除，反之最后插入的元素將最后才能被刪除。所以，行列又稱為“先進先出”或“后進后出”的線性表。1.4樹和二叉樹1.4.1樹樹形構(gòu)造是數(shù)據(jù)構(gòu)造中一種很重要的非線性構(gòu)造。在樹形構(gòu)造中，所有數(shù)據(jù)元素之間的關(guān)系擁有明顯的層次特色。樹形構(gòu)造很像自然界中的樹，像一棵倒長的樹。在現(xiàn)實生活中，能用樹形構(gòu)造表示的例子好多。拜見下邊的圖形：樹形構(gòu)造的基本特色及基本術(shù)語：以以以下圖為例：樹的根：在樹形構(gòu)造中，沒有前驅(qū)的結(jié)點只有一個，稱為樹的根結(jié)點，簡稱為樹的根。如：上圖中的“R”。父結(jié)點：在樹形構(gòu)造中，每一個結(jié)點(除了樹的根結(jié)點)只有一個前驅(qū)，稱為父結(jié)點。如：上圖中的“R”是K、P、Q、D的父結(jié)點；“N”是X、Y的父結(jié)點。子結(jié)點：在樹形構(gòu)造中，每個結(jié)點能夠有多個后繼，稱為該結(jié)點的子結(jié)點。如：上圖中的K、P、Q、D是“R”的子結(jié)點；X、Y是“N”的子結(jié)點。葉子結(jié)點：在樹形構(gòu)造中，沒有后繼的結(jié)點稱為葉子結(jié)點，也稱終端結(jié)點。如：上圖中的C、M、F、E、X、G、S、L、Z、A均為葉子結(jié)點。結(jié)點的度：在樹形構(gòu)造中，一個結(jié)點所擁有的后繼個數(shù)稱為該結(jié)點的度。如：上圖中根結(jié)點R的度是4；結(jié)點T的度是3；結(jié)點P、Q、D、O、Y、W的度都為1。葉子結(jié)點的度為0。樹的度：在樹形構(gòu)造中，所有結(jié)點中的最大的度稱為樹的度。如：上圖中樹的度為4，因為結(jié)點R的度最大，是4。樹的深度：在樹形構(gòu)造中，樹的最大層數(shù)稱為樹的深度(或高度)。如：上圖中樹的深度是5。說明：樹形構(gòu)造擁有明顯的層次關(guān)系，即樹是一種層次構(gòu)造。在樹形構(gòu)造中一般按以下原則分層：1)根結(jié)點在第1層。2)其余結(jié)點的層數(shù)等于其父結(jié)點的層數(shù)加1。子樹：在樹形結(jié)中，以某結(jié)點的一個子結(jié)點為根構(gòu)成的樹稱為該結(jié)點的一棵子樹。如：上圖中，結(jié)點R有4棵子樹，它們分別以K、P、Q、D為根結(jié)點；結(jié)點P有1棵子樹，其根結(jié)點為N；結(jié)點T有3棵子樹，它們分別以W、Z、A為根結(jié)點。在樹形構(gòu)造中，子樹間互不訂交，葉子結(jié)點沒有子樹。叢林：叢林是M(M≥0)棵互不訂交的樹的會合。刪去一棵樹的根，就獲得一個叢林；反之，加上一個結(jié)點作樹根，叢林就變?yōu)橐豢脴洹?.4.2二叉樹(1)二叉樹的特色①非空二叉樹只有一個根結(jié)點。②二叉樹中的每個結(jié)點，最多有兩棵子樹，分另稱為該結(jié)點的左子樹與右子樹。當一個結(jié)點即沒有左子樹也沒有右子樹時，該結(jié)點就是葉子結(jié)點。在下邊的圖中，左面是只有根結(jié)點的二叉樹，右側(cè)是深度為4的二叉樹：(2)滿二叉樹與圓滿二叉樹1)滿二叉樹：滿二叉樹是指除最后一層外，每一層上的所有結(jié)點都有兩個子結(jié)點。就是說，在滿二叉樹中，每一層上的結(jié)點數(shù)都達到最大值，即在滿二叉樹的第k層上有2i-1(k≥1)個結(jié)點，且深度為k的滿二叉樹有2k-1(k≥1)個結(jié)點。在以以下圖中分別是深度為2、3、4的滿二叉樹：滿二叉樹中不存在度數(shù)為1的結(jié)點，每個分支結(jié)點均有兩棵深度同樣的子樹，且葉子結(jié)點都在最下一層。2)圓滿二叉樹：若一棵二叉樹最多只有最下邊的兩層上結(jié)點的度數(shù)能夠小于2，而且最下一層上的所有結(jié)點都集中在該層最左側(cè)的若干地點上，則此二叉樹稱為圓滿二叉樹。在以以下圖的4棵二叉樹中，分別是深度為3和4的圓滿二叉樹：滿二叉樹是圓滿二叉樹，圓滿二叉樹不用然是滿二叉樹。在滿二叉樹的最下一層上，從最右側(cè)開始連續(xù)刪去若干結(jié)點后獲得的二叉樹仍舊是一棵圓滿二叉樹。在圓滿二叉樹中，若某個結(jié)點沒有左子結(jié)點，則它必然沒有右子結(jié)點，即該結(jié)點必是葉子結(jié)點。(3)二叉樹的性質(zhì)假定定義根結(jié)點的層數(shù)為1(注意：有些資猜中規(guī)定根結(jié)點的層數(shù)為0)。性質(zhì)1：在二叉樹的第i層上，最多有2i-1(i≥1)個結(jié)點。性質(zhì)2：深度為k的二叉樹最多有2k-1(k≥1)個結(jié)點。性質(zhì)3：在任意二叉樹中，若度為0的結(jié)點(即葉子結(jié)點)的個數(shù)為n0，度為2的結(jié)點的個數(shù)為n2，則：n0=n2+1(對于圓滿二叉樹還好像手下性)性質(zhì)4：擁有n個結(jié)點的圓滿二叉樹，其深度為[log2n]+1。注：[log2n]表示取log2n的整數(shù)部分。性質(zhì)5：假如將一棵有n個結(jié)點的圓滿二叉樹自頂向下、同一層自左向右連續(xù)給結(jié)點編號1、2、3、…、n，則對于任意結(jié)點i(1≤i≤n)有以下結(jié)論：1)假如i=1，此結(jié)點為根結(jié)點，無前驅(qū)(即無父結(jié)點)；假如i>1，則該結(jié)點的父結(jié)點編號為Int(i/2)。也可表示成[i/2]，都表示取整數(shù)。2)假如2i>n，則結(jié)點i無左子結(jié)點，明顯也沒有右子結(jié)點，是葉子結(jié)點。假如2i≤n，則結(jié)點i的左子結(jié)點是編號為2i的結(jié)點。3)假如2i+1>n，則結(jié)點i無右子結(jié)點。假如2i+1≤n，則結(jié)點i的右子結(jié)點的編號為2i+1。(4)二叉樹的遍歷二叉樹的遍歷就是依據(jù)某種序次，接見二叉樹中的所有結(jié)點，使得每個結(jié)點僅被接見一次。一棵非空二叉樹是由根結(jié)點、左子樹和右子樹三部分構(gòu)成。所以遍歷一棵非空二叉樹的問題就能夠分解為三項“子任條”：①接見根結(jié)點(假定用D表示)。②遍歷左子樹(假定用L表示)。③遍歷右子樹(假定用R表示)。在遍歷二叉樹的過程中，一般先遍歷左子樹，此后再遍歷右子樹。在先左后右的原則下，依據(jù)接見根結(jié)點的序次，二叉樹的遍歷可分為三種：前序遍歷(DLR)、中序遍歷(LDR)、后序遍歷(LRD)。以以以下圖中的二叉樹為例：前序遍歷(DLR)：第一接見根結(jié)點，此后遍歷左子樹，最后遍歷右子樹。在遍歷左、右子樹時，仍舊先接見子樹的根結(jié)點，此后遍歷其左子樹，最后遍歷其右子樹。即，前序遍歷是指接見所有的根結(jié)點(包含子樹的根結(jié)點)都在遍歷其左、右子樹以前。前序遍歷的操作：若二叉樹為空，則結(jié)束反返回。不然：①接見根結(jié)點②前序遍歷左子樹③前序遍歷右子樹如，對上圖中的二叉樹進行前序遍歷的結(jié)果是：FCADBEGHP中序遍歷(LDR)：第一遍歷左子樹，此后接見根結(jié)點，最后遍歷右子樹。在遍歷左、右子樹時，仍舊先遍歷其左子樹，此后接見子樹的根結(jié)點，最后遍歷其右子樹。即，中序遍歷是指接見所有的根結(jié)點(包含子樹的根結(jié)點)都在遍歷其左子樹今后、在遍歷其右子樹以前。中序遍歷的操作：若二叉樹為空，則結(jié)束反返回。不然：①中序遍歷左子樹②接見根結(jié)點③中序遍歷右子樹如，對上圖中的二叉樹進行中序遍歷的結(jié)果是：ACBDFEHGP后序遍歷(LRD)：第一遍歷左子樹，此后遍歷右子樹，最后接見根結(jié)點。在遍歷左、右子樹時，仍舊先遍歷其左子樹，此后遍歷其右子樹，最后接見子樹的根結(jié)點。即，后序遍歷是指接見所有的根結(jié)點(包含子樹的根結(jié)點)都在遍歷其左、右子樹今后。后序遍歷的操作：若二叉樹為空，則結(jié)束反返回。不然：①后序遍歷左子樹②后序遍歷右子樹③接見根結(jié)點如，對上圖中的二叉樹進行后序遍歷的結(jié)果是：ABDCHPGEF1.5查找查找又稱檢索。查找是指在一個給定的數(shù)據(jù)構(gòu)造中查找某個指定的元素。平常，依據(jù)不同樣的數(shù)據(jù)構(gòu)造，應采納不同樣的查找方法。序次查找序次查找又稱序次搜尋或線性查找。序次查找一般是指在線性表中查找指定的元素。序次查找的基本思想：在n個結(jié)點構(gòu)成的線性表中，從線性表的一端開始，挨次將線性表中的元素與被查元素進行比較，若相等則表示找到，即查找成功；若線性表中所有的元素都與被查元素進行了比較但都不相等，則表示線性表中沒有要找的元素，即查找失敗。在序次查找中，查找成功時最多需要比較n次、最少比較1次、均勻比較次數(shù)約為表長的一半。查找失敗時比較n+1次。序次查找的時間復雜度為O(n)。對于無序表(即表中的元素的擺列是無序的)和鏈式儲蓄構(gòu)造的線性表(有序的和無序的)，只好用序次查找。序次查找的長處：算法簡單而合用范圍廣。對表中元素的擺列序次無要求，既能夠是按重點字擺列的有序表，也能夠是無序表；對表的儲蓄構(gòu)造也無任何要求，既合用于序次儲蓄的序次表，也合用于鏈接儲蓄的鏈表。序次查找的弊端：查找效率低，均勻查找長度較大。當n很大時不宜采納序次查找。二分查找二分查找又稱折半查找。它是一種查找效率較高的查找方法。該方法只合用于序次儲蓄構(gòu)造的有序表。平常是指有序表中的元素按值升序擺列(非遞減有序擺列)。二分查找不可以夠用于鏈式儲蓄構(gòu)造的線性表。二分查找的基本思想：拜見“C語言程序設計”或“VB程序設計”課件的相應內(nèi)容動畫。對于長度為n的有序線性表，查找成功時最多需要比較log2(n+1)次、最少比較1次、均勻查找長度近似log2n。當查找失敗時，比較log2n或log2(n+1)次。不論二分查找成功與否，其時間復雜度均為O(log2n)。二分查找的最壞性能和均勻性能相當湊近。1.6排序排序就是將文件中的記錄進行整理，使之依據(jù)重點字進行遞加或遞減的序次擺列起來，成為一個有序序列的過程。在本節(jié)所介紹的排序方法中，其排序的對象一般以為是序次儲蓄的線性表，在程序設計語言中就是一維數(shù)組。這里的排序算法，都是針對升序排序。互換排序互換排序是兩兩比較待排序記錄的重點字，若發(fā)現(xiàn)兩個記錄重點字的序次相反時即進行互換，直到?jīng)]有反序的記錄為止。下邊介紹兩種常用的互換排序。(1)冒泡排序冒泡排序的基本思想：拜見“C語言程序設計”或“VB程序設計”課件的相應內(nèi)容動畫。對于長度為n的線性表，在最壞狀況下，冒泡排序需要經(jīng)過n/2遍的掃描，比較次數(shù)為n(n-1)/2。冒泡排序算法的均勻時間復雜度為O(n2)，空間復雜度為O(1)。(2)迅速排序迅速排序的基本思想：拜見以以下圖：從線性表中采納一個元素，設為T，將線性表后邊小于T的元素移到前面，將線性表前面大于T的元素移到后邊，結(jié)果就把線性表分紅了兩部分(稱為兩個子表)，T插入到其分界限的地點處，這個過程稱為線性表的切割。經(jīng)過對線性表的一次切割，就以T為分界限，將線性表分紅了前后兩個子表，且前面子表中的所有元素均不大于T，后邊子表中的所有元素均不小于T。假如對切割后的各子表再按上述原則進行切割，而且這類切割過程能夠向來做下去，跟著對各子表不停地進行切割，區(qū)分出的子表會愈來愈多(一次只好對一個子表進行再切割辦理)，直到所有子表中的元素都排好序為止，則此時的線性表就變?yōu)榱擞行虮?。對于長度為n的線性表：在最壞狀況下，迅速排序比較次數(shù)為n(n-1)/2。算法的時間復雜度為O(n2)，空間復雜度為O(n)。在最好狀況下，迅速排序算法的時間復雜度為O(nlog2n)，空間復雜度為O(log2n)。迅速排序算法的均勻時間復雜度是O(nlog2n)，均勻比較次數(shù)不大于(n+1)log2n插入排序插入排序是每次將一個待排序的記錄按其重點字大小，插入到前面已排好的序列中的適合地點，直到所有記錄插入為止。(1)直接插入排序迅速排序的基本思想：請查察有關(guān)資料。對于長度為n的線性表：在最壞狀況下，直接插入排序比較次數(shù)為n(n-1)/2。算法的時間復雜度為O(n2)。(2)希爾排序希爾排序的基本思想：請查察有關(guān)資料。對于長度為n的線性表：在最壞狀況下希爾排序比較次數(shù)為O(n1.5)。1.6.3選擇排序選擇排序的基本思想是：每一遍在n-i+1(i=1,2,…,n-1)個待排序記錄中采納重點字最小的記錄作為有序序列中第i個記錄，直到所有記錄排完為止。(1)直接選擇排序選擇排序的基本思想：拜見“C語言程序設計”或“VB程序設計”課件的相應內(nèi)容動畫。在最壞狀況下，直接選擇排序比較次數(shù)為n(n-1)/2。(2)堆排序希爾排序的基本思想：請查察有關(guān)資料。在最壞狀況下，堆排序比較次數(shù)為O(nlog2n)。習題：（一）選擇題(單項選擇)1.以下表達中正確的選項是(D)A）棧是“先進先出”的線性表B）行列是“先進后出”的線性表C）循環(huán)行列是非線性構(gòu)造D）有序線性表既能夠采納序次儲蓄構(gòu)造，也能夠采納鏈式儲蓄構(gòu)造2.以下對于棧的表達中正確的選項是(A)A)棧頂元素最初被刪除B)棧頂元素最后才能被刪除C)棧底元素永久不可以夠被刪除D)以上三種說法都不對3.以下表達中正確的選項是(B)A)有一個以上根結(jié)點的數(shù)據(jù)構(gòu)造不用然是非線性構(gòu)造B)只有一個根結(jié)點的數(shù)據(jù)構(gòu)造不用然是線性構(gòu)造C)循環(huán)鏈表是非線性構(gòu)造D)雙向鏈表是非線性構(gòu)造4.支持子程序調(diào)用的數(shù)據(jù)構(gòu)造是(A)A)棧B)樹C)行列D)二叉樹5.某二叉樹有5個度為2的結(jié)點，則該二叉樹中的葉子結(jié)點數(shù)是(C)A）10B）8C）6D）4提示：在任意二叉樹中，若度為0的結(jié)點(即葉子結(jié)點)的個數(shù)為n0，度為2的結(jié)點的個數(shù)為n2，則：n0=n2+1即n0(葉子結(jié)點數(shù))=5+1=66.某二叉樹共有7個結(jié)點，此中葉子結(jié)點只有1個，則該二叉樹的深度為(假定根結(jié)點在第一層)(D)A)3B)4C)6D)77.以下排序方法中，最壞狀況下比較次數(shù)最少的是(D)A）冒泡排序B）簡單項選擇擇排序C）直接插入排序D）堆排序8.以下表達中正確的選項是(A)A)對長度為n的有序鏈表進行查找，最壞的狀況下需要的比較次數(shù)為nB)對長度為n的有序鏈表進行對分查找，最壞的狀況下需要的比較次數(shù)為（n/2）C)對長度為n的有序鏈表進行對分查找，最壞的狀況下需要的比較次數(shù)為(log2n)D)對長度為n的有序鏈表進行對分查找，最壞的狀況下需要的比較次數(shù)為(nlog2n)(二)填空題1.假定用一個長度為50的數(shù)組（數(shù)組元素的下標從0到49）作為棧的儲蓄空間，棧底指針bottom指向棧底元素，棧頂指針top指向棧頂元素，假如bottom=49,top=30(數(shù)組下標)，則棧中擁有________個元素。答案：202.一個行列的初始狀態(tài)為空?，F(xiàn)將元素A、B、C、D、E、F、5、4、3、2、1一次入隊，此后再一次退隊，則元素退隊的序次為________________________。答案：A、B、C、D、E、F、5、4、3、2、13.設某循環(huán)行列的容量為50，假如頭指針front=45(指向隊頭元素的前一個地點)，尾指針rear=10（指向隊尾元素），則該循環(huán)行列中共有_____個元素。答案：154.設二叉樹以下：AABCDEFGH對該二叉樹進行后序遍歷的結(jié)果為________________________。答案：E、D、B、G、H、F、C、A5.一棵二叉樹的中序遍歷結(jié)果為DBEAFC，前序遍歷結(jié)果為ABDECF，則后序遍歷結(jié)果為_________。答案：DEBFCA6.有序線性表能進行二分查找的前提是該線性表必然是________儲蓄。答案：序次二、軟件工程基礎計算機軟件是計算機系統(tǒng)中與硬件相互依存的另一部分，是包含程序、數(shù)據(jù)及有關(guān)文檔的圓滿會合。軟件由兩部分構(gòu)成：一是機器可履行的程序和數(shù)據(jù)；二是機器不可以履行的，與軟件開發(fā)、運轉(zhuǎn)、保護、使用等有關(guān)的文檔。軟件的分類軟件按功能能夠分為：應用軟件、系統(tǒng)軟件、支撐軟件(或工具軟件)。應用軟件：是為解決特定領(lǐng)域的應用而開發(fā)的軟件。系統(tǒng)軟件：是計算機管理自己資源，提升計算機使用效率并為計算機用戶供給各樣服務的軟件。支撐軟件：是介于系統(tǒng)軟件和應用軟件之間，輔助用戶開發(fā)軟件的工具性軟件。軟件生命周期平常將軟件產(chǎn)品從提出、實現(xiàn)、使用保護到停止使用退伍的過程稱為軟件生命周期。拜見以以下圖：構(gòu)造化分析方法構(gòu)造化分析的常用工具：數(shù)據(jù)流圖(DFD)：是描繪數(shù)據(jù)辦理過程的工具，是需求理解的邏輯模型的圖形表示，它直接支持系統(tǒng)的功能建模。數(shù)據(jù)詞典(DD)：是構(gòu)造化分析方法的核心。判斷樹判斷表構(gòu)造化設計方法常有的過程設計工具：圖形工具：程序流程圖，N-S圖，PAD圖(問題分析圖)，HIPO表格工具：判斷表。語言工具：PDL(偽碼)軟件設計的基本源理1)抽象：是一種思想工具，就是把事物實質(zhì)的共同特色提拿出來而不考慮其余細節(jié)。2)模塊化：是指把一個待開發(fā)的軟件分解成若干小的簡單的部分。如高級語言中的過程、函數(shù)、子程序等。每個模塊能夠達成一個特定的子功能，各個模塊能夠按必然的方法組裝起來成為一個整體，進而實現(xiàn)整個系統(tǒng)的功能。3)信息隱蔽：是指在一個模塊內(nèi)包含的信息(過程或數(shù)據(jù))，對于不需要這些信息的其余模塊來說是不可以夠接見的。4)模塊獨立性：是指每個模塊只達成系統(tǒng)要求的獨立的子功能，而且與其余模塊的聯(lián)系最少且接口簡單。模塊的獨立程度是談論設計利害的重要胸懷標準。權(quán)衡軟件的模塊獨立性使用耦合性和內(nèi)聚性兩個定性的胸懷標準。內(nèi)聚性：是一個模塊內(nèi)部各個元素間相互聯(lián)合的親密程度的胸懷。內(nèi)聚是從功能角度來胸懷模塊內(nèi)的聯(lián)系。內(nèi)聚性是信息隱蔽和局部化見解的自然擴展。一個模塊的內(nèi)聚性越強則該模塊的模塊獨立性越強。作為軟件構(gòu)造設計的設計原則，要求每一個模塊的內(nèi)部都擁有很強的內(nèi)聚性，它的各個構(gòu)成部分相互都親密有關(guān)。耦合性：耦合性是模塊間相互連結(jié)的親密程度的胸懷。一個模塊與其余模塊的耦合性越強則該模塊的模塊獨立性越弱。原則上講，模塊化設計老是希望模塊間的耦合表現(xiàn)為非直接耦合方式。但是，因為問題所固有的復雜性和構(gòu)造化設計的原則，非直接耦合常常是不存在的。耦合性與內(nèi)聚性是模塊獨立性的兩個定性標準，耦合性與內(nèi)聚性是相互聯(lián)系的。在程序構(gòu)造中，各模塊的內(nèi)聚性越強，則耦合性越弱。一般優(yōu)異的軟件設計，應盡量做到高內(nèi)聚，低耦合，即減弱模塊之間的耦合性和提升模塊內(nèi)的的內(nèi)聚性，有益于提升模塊的獨立性。軟件測試軟件測試是在軟件投入運轉(zhuǎn)前對軟件需求、設計、編碼的最后審查。軟件測試是為了發(fā)現(xiàn)錯誤而履行程序的過程。軟件測試應該制定明確的測試計劃并按計劃履行。軟件測試的目的：是發(fā)現(xiàn)錯誤。軟件測試方法和技術(shù)：若從能否需要履行被測軟件的角度，能夠分為靜態(tài)測試和動向測試方法。若依據(jù)功能區(qū)分能夠分為白盒測試和黑盒測試方法。靜態(tài)測試：包含代碼檢查、靜態(tài)構(gòu)造分析、代碼質(zhì)量胸懷等。靜態(tài)測試不實質(zhì)運轉(zhuǎn)軟件，主要經(jīng)過人工進行。動向測試：是鑒于計算機的測試，是為了發(fā)現(xiàn)錯誤而履行程序的過程。需要精心設計一批測試用例，并利用這些測試用例去運轉(zhuǎn)程序，以發(fā)現(xiàn)程序錯誤的過程。測試用例的格式為：[(輸入值集),(輸出值集)]白盒測試：也稱構(gòu)造測試或邏輯驅(qū)動測試。它是依據(jù)軟件產(chǎn)品的內(nèi)部工作過程，檢查內(nèi)部成分，以確認每種內(nèi)部操作符合設計規(guī)格要求。白盒測試把測試對象看作一個翻開的盒子，贊成測試人員利用程序內(nèi)部的邏輯構(gòu)造及有關(guān)信息來設計或選擇測試用例，對程序所有的邏輯路徑進行測試。經(jīng)過在不同樣點檢查程序的狀態(tài)來認識實質(zhì)的運轉(zhuǎn)狀態(tài)能否與預期的一致。所以，白盒測試是在程序內(nèi)部進行，主要用于達成軟件內(nèi)部操作的考證。白盒測試的主要方法有邏輯覆蓋、基本路徑測試等。黑盒測試：也稱功能測試或數(shù)據(jù)驅(qū)動測試。黑盒測試是對軟件已經(jīng)實現(xiàn)的功能能否知足需求進行測試和考證。黑盒測試圓滿不考慮程序內(nèi)部的邏輯構(gòu)造和內(nèi)部特色，只依據(jù)程序的需乞降功能規(guī)格說明，檢查程序的功能能否符合它的功能說明。所以，黑盒測試是在軟件接口處進行，達成功能考證。黑盒測試只檢查程序功能能否依據(jù)需求規(guī)格說明書的規(guī)定正常使用，程序能否能適合地接收輸入數(shù)據(jù)而產(chǎn)生正確的輸出信息，而且保持外面信息(如數(shù)據(jù)庫或文件)的圓滿性。黑盒測試主要診療功能不對或遺漏、界面錯誤、數(shù)據(jù)構(gòu)造或外面數(shù)據(jù)庫接見錯誤、性能錯誤、初始化和停止條件錯誤。黑盒測試方法主要有等價類區(qū)分法、界限值分析法、錯誤推斷法、因果圖等，主要用于軟件確認測試。程序調(diào)試在對程序進行了成功的測試今后，將進入程序調(diào)試(平常稱Debug，即排錯)。程序調(diào)試的任務是診療和更正程序中的錯誤。它與軟件測試不同樣，軟件測試是盡可能多地發(fā)現(xiàn)軟件中的錯誤，并找出軟件錯誤的詳盡地點。軟件測試貫串整個軟件生命期，調(diào)試主要在開發(fā)階段。習題：（一）選擇題(單項選擇)1.軟件按功能能夠分為：應用軟件、系統(tǒng)軟件和支撐軟件（或工具軟件）。下邊屬于應用軟件的是(C)A)編譯程序B)操作系統(tǒng)C)教務管理系統(tǒng)D)匯編程序2.軟件按功能可分為：應用軟件、系統(tǒng)軟件、和支撐軟件（或工具軟件）。下邊屬于系統(tǒng)軟件的是(B)A)編寫軟件B)操作系統(tǒng)C)教務管理系統(tǒng)D)閱讀器、3.軟件(程序)調(diào)試的任務是(A)A)診療和更正程序中的錯誤B)盡可能多的發(fā)現(xiàn)程序中的錯誤C)發(fā)現(xiàn)并更正程序中的所有錯誤D)確立程序中錯誤的性質(zhì)4.下邊表達中錯誤的選項是(A)A)軟件測試的目的是發(fā)現(xiàn)錯誤并更正錯誤B)對被調(diào)試的程序進行“錯誤定位”是程序調(diào)試的必需步驟C)程序調(diào)試平常也稱為DebugD)軟件測試應嚴格履行測試計劃，除去測試的任意性5.耦合性和內(nèi)聚性是對模塊獨立性胸懷的兩個標準。以下表達中正確的選項是(B)A)提升耦合性、降低內(nèi)聚性有益于提升模塊的獨立性B)降低耦合性、提升內(nèi)聚性有益于提升模塊的獨立性C)耦合性是指一個模塊內(nèi)部各個元素間相互聯(lián)合的親密程度D)內(nèi)聚性是指模塊間相互連結(jié)的親密程度6.數(shù)據(jù)流圖(DFD圖)是(C)A)軟件綱領(lǐng)設計的工具B)軟件詳盡設計的工具C)構(gòu)造化方法的需求分析工具D)面向?qū)ο蠓椒ǖ男枨蠓治龉ぞ?.軟件生命周期可分為定義階段，開發(fā)階段和保護階段。詳盡設計屬于(B)A)定義階段B)開發(fā)階段C)保護階段D)上述三個階段8.在軟件開發(fā)中，需求分析階段產(chǎn)生的主要文檔是(D)A)軟件集成測試計劃B)軟件詳盡設計說明書C)用戶手冊D)軟件需求規(guī)格說明書9.構(gòu)造化程序所要求的基本構(gòu)造不包含(B)A)序次構(gòu)造B)GOTO跳轉(zhuǎn)C)選擇(分支)構(gòu)造D)重復(循環(huán))構(gòu)造10.下邊描繪中錯誤的選項是(A)A)系統(tǒng)整體構(gòu)造圖支持軟件系統(tǒng)的詳盡設計B)軟件設計是將軟件需求變換為軟件表示的過程C)數(shù)據(jù)構(gòu)造與數(shù)據(jù)庫設計是軟件設計的任務之一D)PAD圖是軟件詳盡設計的表示工具(二)填空題1.軟件測試可分為白盒測試和黑盒測試。基本路徑測試屬于______________測試。答案：白盒2.符合構(gòu)造化原則的三種基本控制構(gòu)造是：選擇構(gòu)造、循環(huán)構(gòu)造和______________。答案：序次構(gòu)造3.軟件是________、數(shù)據(jù)和文檔的會合。答案：程序4.對軟件設計的最小單位(模塊或程序單元)進行的測試平常為_______測試。答案：單元或模塊三、數(shù)據(jù)庫設計基礎計算機應用的三大領(lǐng)域：科學計算、數(shù)據(jù)辦理、過程控制。數(shù)據(jù)庫系統(tǒng)的基本見解數(shù)據(jù)(Data)：就是描繪事物的符號記錄。數(shù)據(jù)庫(DB)：是數(shù)據(jù)的會合，它擁有一致的構(gòu)造形式并寄存于一致的儲蓄介質(zhì)內(nèi)，是多種應用數(shù)據(jù)的集成，并可被各個應用程序所共享。數(shù)據(jù)庫中的數(shù)據(jù)擁有“集成”、“共享”的特色。數(shù)據(jù)庫管理系統(tǒng)(DBMS)：是數(shù)據(jù)庫的機構(gòu)，是一種系統(tǒng)軟件，負責數(shù)據(jù)庫中的數(shù)據(jù)組織、數(shù)據(jù)控制、數(shù)據(jù)保護、控制及保護和數(shù)據(jù)服務等。數(shù)據(jù)庫管理系統(tǒng)是數(shù)據(jù)庫系統(tǒng)的核心。數(shù)據(jù)庫管理系一致般供給相應的數(shù)據(jù)語言(DataLanguage)來達成相應的功能：數(shù)據(jù)定義語言(DDL)：負責數(shù)據(jù)的模式定義與數(shù)據(jù)的物理存取建立。數(shù)據(jù)控制語言(DML)：負責數(shù)據(jù)的控制，包含查問及增、刪、改等操作。數(shù)據(jù)控制語言(DCL)：負責數(shù)據(jù)圓滿性、安全性的定義與檢查以及并發(fā)控制、故障恢復等功能，包含系統(tǒng)初出發(fā)序、文件讀寫與保護程序、存取路徑管理程序、緩沖區(qū)管理程序、安全性控制程序、圓滿性檢查程序、并發(fā)控制程序、事務管理程序、運轉(zhuǎn)日記管理程序、數(shù)據(jù)庫恢復程序等。數(shù)據(jù)庫管理員(DBA)：因為數(shù)據(jù)庫的共享性，所以對數(shù)據(jù)庫的規(guī)劃、設計、保護、督查等需要有專人管理，稱他們?yōu)閿?shù)據(jù)庫管理員。數(shù)據(jù)庫系統(tǒng)(DBS)：由數(shù)據(jù)庫(數(shù)據(jù))、數(shù)據(jù)庫管理系統(tǒng)(軟件)、數(shù)據(jù)庫管理員(人員)、系統(tǒng)硬件平臺(硬件)、系統(tǒng)軟件平臺(軟件)這五部分構(gòu)成，稱為數(shù)據(jù)庫系統(tǒng)。數(shù)據(jù)庫應用系統(tǒng)(DBAS)：是數(shù)據(jù)庫系統(tǒng)再加上應用軟件及應用界面這三者所構(gòu)成。E-R模型該模型將現(xiàn)實世界的要求轉(zhuǎn)變?yōu)閷嶓w、聯(lián)系、屬性等幾個基本見解，以及它們間的兩種基本聯(lián)接關(guān)系，而且能夠用一種圖特別直觀地表示出來。下邊是E-R模型的基本見解。當前較為出名的見解模型有E-R模型、擴大的E-R模型、面向?qū)ο竽Ｐ图爸^詞模型等。實體：現(xiàn)實世界中的事物能夠抽象成為實體。實體是見解世界中的基本單位，它們是客觀存在的且又相互區(qū)其余事物。凡是有共性的實體可構(gòu)成一個會合稱實體集。如學生A和學生B，他們都是實體，他們又都是學生，進而構(gòu)成一個學生實體集。屬性：現(xiàn)實世界中的事物均有一些特色，這些特色能夠用屬性來表示。屬性刻畫了實體的特色。一個實體常常能夠有若干個屬性。聯(lián)系：現(xiàn)實世界中事物間的關(guān)系稱為聯(lián)系。在見解世界中聯(lián)系反應了實體集間的必然關(guān)系。如工人與設施間的操作關(guān)系，上、下級間的領(lǐng)導關(guān)系等。實體集間的聯(lián)系有多種，就實體集的個數(shù)而言有：1)兩個實體集間的聯(lián)系。2)多個實體集間的聯(lián)系。3)一個實體集內(nèi)部的聯(lián)系：是一個實體集內(nèi)的不同樣實體間的聯(lián)系。實體集間聯(lián)系的個數(shù)能夠是單個也能夠是多個，包含：一對一的聯(lián)系，簡記為1:1一對多或多對一的聯(lián)系，簡記為1:M或M:1(此中M也能夠小寫)多對多的聯(lián)系，簡記為M:N或m:nE-R模型由上邊三個基本見解構(gòu)成。由實體、聯(lián)系、屬性三者聯(lián)合起來才能表示現(xiàn)實世界。E-R圖：E-R模型能夠用一種特別直觀的圖的形式表示，這類圖稱為E-R圖。在E-R圖中我們分別用下邊不同樣的幾何圖形表示E-R模型中的三個見解與兩個聯(lián)接關(guān)系。1)實體集表示法用矩形表示實體集，在矩形內(nèi)寫上該實體集的名字。照實體集學生(student)、課程(course)可表示為：2)屬性表示法用橢圓形表示屬性，在橢圓形內(nèi)寫上該屬性的名稱。如學生有屬性：學號(S#)、姓名(Sn)及年紀(Sa)，可表示為：3)聯(lián)系表示法用菱形表示聯(lián)系，在菱形內(nèi)寫上聯(lián)系名。如學生與課程間的聯(lián)系SC，可表示為：上邊是三個基本見解分別用三種幾何圖形表示。下邊是它們之間的聯(lián)接關(guān)系的圖形表示。4)實體集或聯(lián)系與屬性間的聯(lián)接關(guān)系屬性依賴于實體集，屬性也依賴于聯(lián)系，所以它們之間分別有聯(lián)接關(guān)系。拜見以以下圖：此中：C#(課程號)、Cn(課程名)、P#(預修課號)5)實體集與聯(lián)系間的聯(lián)接關(guān)系以以以下圖表示實體集與聯(lián)系間的聯(lián)接關(guān)系：還能夠夠在線段邊上注明其對應的函數(shù)關(guān)系，如1:1、1:n、n:m等。以以下圖表示student與course間有多對多聯(lián)系：兩個實體集間聯(lián)系叫二元聯(lián)系，多個實體集間聯(lián)系叫多元聯(lián)系。以以下圖聯(lián)系FPU是一種三元聯(lián)系(工廠、產(chǎn)品與用戶間的聯(lián)系)：下邊是實體間多種聯(lián)系圖：(a)圖：企業(yè)員工(enployee)間上、下級管理(manage)的聯(lián)系。即一個實體集內(nèi)部能夠有多種聯(lián)系。(b)圖：教師(T)與學生(S)之間能夠有講課(E)聯(lián)系也能夠有管理(M)聯(lián)系。即實體集間能夠有多種聯(lián)系。下邊是E-R圖的一個實例圖關(guān)系模型關(guān)系模型采納二維表來表示，簡稱表。二維表由表框架(Frame)及表的元組(Tuple)構(gòu)成。表框架由n個命名的屬性(Attribute)構(gòu)成，n稱為屬性元數(shù)(Arity)。每個屬性有一個取值范圍，稱為值域(Domain)。表框架對應了關(guān)系的模式，即種類的見解。在表框架中按行能夠寄存數(shù)據(jù)，每行數(shù)據(jù)稱為元組，實質(zhì)上，一個元組是由n個元組重量所構(gòu)成，每個元組重量是表框架中每個屬性的投影值。一個表框架能夠寄存m個元組，m稱為表的基數(shù)(Cardinality)。一個n元表框架及框架內(nèi)m個元組構(gòu)成了一個圓滿的二維表。關(guān)系框架與關(guān)系元組構(gòu)成了一個關(guān)系。一個語義有關(guān)的關(guān)系會合構(gòu)成一個關(guān)系數(shù)據(jù)庫。關(guān)系的框架稱為關(guān)系模式，而語義有關(guān)的關(guān)系模式會合構(gòu)成了關(guān)系數(shù)據(jù)庫模式。知足下邊7個性質(zhì)的二維表稱為關(guān)系(Relation)：1)元組個數(shù)有限性：二維表中元組個數(shù)是有限的。2)元組的唯一性：二維表中元組均不同樣。3)元組的序次沒關(guān)性：二維表中元組的序次能夠任意互換。4)元組重量的原子性：二維表中元組的重量是不可以切割的基本數(shù)據(jù)項。5)屬性名唯一性：二維表中屬性名各不同樣。6)屬性的序次沒關(guān)性：二維表中屬性與序次沒關(guān)，可任意互換。7)重量值域的同一性：二維表屬性的重量擁有與該屬性同樣的值域。以二維表(關(guān)系)為基本構(gòu)造所建立的模型稱為關(guān)系模型。在關(guān)系模型中的一個重要見解是鍵(Key)或碼。鍵擁有表記元組