計算機軟件基礎(chǔ)

計算機軟件基礎(chǔ)C語言基礎(chǔ)C語言有哪些數(shù)據(jù)類型？整型、實型、字符型。為什么程序中的變量使用前必須先定義？C程序用到的變量都必須進行定義，即事先定義其類型。變量一經(jīng)定義，系統(tǒng)就給分配存儲空間，以存放相應(yīng)常量。算法和程序的區(qū)別是什么？算法是有窮的，程序是無窮的;算法和程序的描述方法不一樣，程序是用計算機語言描述的；算法一般不可執(zhí)行，程序可以執(zhí)行算法是解決問題的方法、步驟和思路。C語言源程序的文件的后綴是C，經(jīng)過編譯后生成文件的后綴是OBJ，經(jīng)過連接后生成文件的后綴是exe。C程序開發(fā)的四個步驟依次是提出問題、構(gòu)造模型、選擇方法、編寫程序。數(shù)學(xué)式sin35°+xcos60的C語言表達式為Sin(35*pi/180)+cos(60*pi/180)(其中pi=3.14)。表達式3*9%2+9%2*5的值為6。表達式6.0*(1/2)的值為0。程序就是算法用某種計算機語言表示出來的。一個變量同時只能被定義為一種類型。程序中用到的所有變量必須先定義后使用。變量代表內(nèi)存中具有特定屬性的一個存儲單元，它用來存放也就是變量的值，這些值是可以改變的。一個字符型變量只能存儲一個字符若a是實型變量，在執(zhí)行了a=5后，a仍為實型變量。若a和b類型相同，在執(zhí)行了a=b后，b中仍保留原值。編制C語言程序并上機運行的一般過程是編輯、編譯、連接、運行。C語言規(guī)定用戶標(biāo)識符由字母、數(shù)字和下劃線組成，且第一個字符必須是字母或下劃線。begin不是C語言的關(guān)鍵字。順序結(jié)構(gòu)、選擇結(jié)構(gòu)和循環(huán)結(jié)構(gòu)的程序設(shè)計請寫出switch語句的一般格式及注意事項。一般格式：Switch（表達式）｛case常量表達式1：語句組1；break；Case常量表達式2：語句組2；break；……Case常量表達式n：語句組n；break；Default：語句組n+1；｝1switch中表達式可以是任意類型，常用的是字符或整型。2每個常量表達式的值不能相同。3語句組可以為任意語句。4break可以省略，然后執(zhí)行完本組語句后緊接著執(zhí)行其后的i+1組語句。5多個case可以用一組執(zhí)行語句。6插入一個新節(jié)點，則需要相繼修改4個指針域的值。線性結(jié)構(gòu)的特征：有且只有一個根節(jié)點，它無前件；有且只有一個終端節(jié)點，它無后件；除根節(jié)點和終端節(jié)點以外，其他節(jié)點有且只有一個前件，也有且只有一個后件。在單鏈表中，增加頭節(jié)點的目的是方便運算的實現(xiàn)。用鏈表表示線性表的優(yōu)點是便于插入和刪除操作。在線性表的順序存儲中，元素之間的邏輯關(guān)系是通過物理存儲位置決定的；在線性表的鏈接存儲中，元素之間的邏輯關(guān)系是通過鏈域的指針值決定的。在雙向鏈表中，每個節(jié)點包含兩個指針域，一個指向前驅(qū)結(jié)點，另一個指向后繼結(jié)點。在線性表的順序存儲中，若一個元素的下標(biāo)為i，則它的前驅(qū)元素的下標(biāo)為i-1，后繼元素的下標(biāo)為i+1。一個線性表中，第一個元素的存儲地址是100，每個元素的長度是2，則第五個元素的地址是108。棧、隊列和數(shù)組簡述棧和隊列的相同點和不同點。相同點：都是存儲數(shù)據(jù)的線性表。不同點：棧為LIFO（后進線出）線性表，插入、刪除操作均在表尾進行。隊列為FIFO（先進先出）線性表，插入在表尾進行、刪除在表頭進行。若進棧的數(shù)據(jù)元素序列依次為1、2、3、4、5、6，能否得到4、3、5、6、1、2和1、3、5、4、2、6的出棧列？并舉例說明為什么不能得到或如何得到。（1）不能得到4、3、5、6、1、2的出棧列。最先出棧的是4，則此時棧底元素為最先入棧的1、然后依次向上為2、3、4、4、3出棧后；5入棧，再出棧；6入棧，再出棧；這時得到序列為4、3、5、6；這時棧頂元素為2,2出棧后，1才能出棧，所以1不可能先于2出棧，因此不能得到此序列。（2）可以得到1、3、5、4、2、6的出棧列。1入棧，再出棧，1為第一個出棧元素；2入棧；3入棧，再出棧，3為第二個出棧元素；4、5一次入棧，此時，棧底元素為1,5成為棧頂元素，則5出棧，然后4出棧，然后2出棧；之后6入棧，再出棧；因此可以得到此出棧序列。向一個順序棧加一個元素時，首先若棧不滿棧頂指針上移，然后將元素加入到棧頂位置。從一個順序棧刪除元素時，首先判斷棧是否為空，然后若不為空棧頂指針下移。一個順序棧存儲于一維數(shù)組a[m]中，棧頂指針用top表示，當(dāng)棧頂指針等于-1時，則為空棧；棧頂指針等于m-1時，則為滿棧。在一個鏈棧中，若棧頂指針等于NULL則為空棧；在一個鏈隊列中，若隊首指針與隊尾指針的值相同，則表示該隊為空隊列。在具有n個單元的循環(huán)隊列中，隊滿時共有n-1個元素。已知二維數(shù)組A[1：4][1:6]采用行序為主序方式存儲，每個元素占用三個存儲單元，并且A[2,2]的存儲地址為1200，元素A[3,4]的存儲地址是1224。若將n階三對角矩陣A按照行序為主序方式將所有非零元素存放在一個一維數(shù)組B中，則該三對角矩陣在B中共有3n-2個數(shù)據(jù)元素。隊列只能在隊首進行刪除，在隊尾進行插入。隊列屬于數(shù)據(jù)結(jié)構(gòu)中存取受限制的線性結(jié)構(gòu)。鏈棧的所有操作都限制在表頭進行，所有沒有必要設(shè)置頭結(jié)點。鏈棧與順序棧相比，通常不會出現(xiàn)棧滿的情況。順序棧是線性結(jié)構(gòu)，鏈棧也是線性結(jié)構(gòu)。一個棧的入棧序列是a、b、c、d、e，則棧的不可能的輸出序列是dceab。向順序棧中壓入新元素時，應(yīng)當(dāng)先移動棧頂指針，再存入元素。當(dāng)利用大小為N的數(shù)組順序存儲一個棧時，假定用top==N表示?？眨瑒t向這個棧插入一個元素時，首先應(yīng)執(zhí)行top——語句修改top指針。假定利用數(shù)組a[N]順序存儲一個棧，用top表示棧頂指針，top==-1表示?？眨⒁阎獥Ｎ礉M，當(dāng)元素x進棧時所執(zhí)行的操作為a[++top]==x。假定一個鏈?zhǔn)綏５臈ｍ斨羔樣胻op表示，每個節(jié)點的結(jié)構(gòu)為datanext，所進行的指針操作為top=top->next。一個隊列的入隊順序是1、2、3、4，則隊列的輸出順序是1、2、3、4。假定一個順序隊列的隊首和隊尾指針分別用front和rear表示，則判斷對空的條件為front==rear。判定一個循環(huán)隊列Q（最多元素為m0）為空的條件是Q->front==Q->rear。判定一個循環(huán)隊列Q（最多元素為m0）為隊滿的條件是Q->front==（Q->rear+1）%m。若將n階對稱矩陣A按照行序為主序方式將包括主對角線在內(nèi)的下三角形的所有元素存放在一個一維數(shù)組B中，則該對稱矩陣在B中占用了n（n+1）/2個數(shù)組元素。判定一個棧（最多元素為m）為空的條件是ST->top==-1。判定一個棧ST（最多元素為m）為棧滿的條件是ST->top==m-1。棧結(jié)構(gòu)通常采用的兩種存儲結(jié)構(gòu)是順序線性結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)。棧和隊列的共同點是只允許在端點處插入和刪除元素。在一個鏈隊中，假設(shè)f和r分別為隊首和隊尾指針，則插入s所指節(jié)點的運算是r->next=s；r=s。在一個鏈隊中，假設(shè)f和r分別為隊首和隊尾指針，則刪除一個節(jié)點的運算是f=f->next。樹和二叉樹指出樹和二叉樹的主要區(qū)別樹無序而二叉樹有序。對于一顆具有n個節(jié)點的樹，該樹中所有節(jié)點的度數(shù)之和為n-1。在一棵樹中根節(jié)點沒有前驅(qū)節(jié)點，其余每個節(jié)點有且僅有一個直接前驅(qū)節(jié)點，可以有任意多個直接后繼節(jié)點。在一顆二叉樹中，假定度為2的節(jié)點數(shù)為5個，度為1的節(jié)點數(shù)為6個，則葉子節(jié)點數(shù)為6個。具有40個節(jié)點的完全二叉樹，它的高度為6。已知8個數(shù)據(jù)元素為34,76,45,18,26,54，92,65，按照依次插入節(jié)點的方法生成一顆二叉排序樹，則該樹的深度為5。二叉樹的5種基本形態(tài)是空二叉樹、只有根的二叉樹、只有左子樹的二叉樹、只有右子樹的二叉樹、左右子樹都有的二叉樹。若由3、6、8、12、10作為葉子節(jié)點的值生成一顆哈夫曼樹，則該樹的高度為4，帶權(quán)路徑長度為87。任意一顆有n個節(jié)點的二叉樹，若它有m個葉子節(jié)點，則二叉樹上度為1的節(jié)點個數(shù)為n-2m+1。若一顆二叉樹葉子樹為n，在該二叉樹中，左、右子樹皆非空的節(jié)點個數(shù)為n-1。由一個二叉樹的先序和中序或后序和中序遍歷結(jié)果可以唯一地確定一顆二叉樹。二叉樹中，任何一個節(jié)點的度數(shù)為2。一顆哈夫曼樹中存在度為1的節(jié)點。樹的先根遍歷順序與其對應(yīng)的二叉樹的先根遍歷序列相同。按二叉樹的定義，具有3個節(jié)點的二叉樹有5種。已知某二叉樹的后序遍歷序列是dabec，中序遍歷序列是debac，它的前序遍歷序列是cedba。樹中所有節(jié)點的度等于所有節(jié)點個數(shù)加-1。在一顆度為3的樹中，度為3的節(jié)點數(shù)為2個，度為2的節(jié)點數(shù)為1個，度為1的節(jié)點數(shù)為2個，則度為0的節(jié)點數(shù)為6個。已知某二叉樹的后序遍歷序列是DACBE，中序遍歷序列是DEBAC，則它的前序遍歷序列是EDBAC。在一顆二叉樹上第8層的節(jié)點數(shù)最多是128。在深度為5的滿二叉樹中，葉子節(jié)點的個數(shù)為16。設(shè)一顆完全二叉樹共有500個節(jié)點，則在該二叉樹中有250個葉子節(jié)點。若某二叉樹的前序是stuwv，中序是uwtvs，那么后序為wuvts。任何一顆二叉樹的葉子節(jié)點在先序、中序和后序遍歷序列中的相對依次不發(fā)生改變。若T2是由有序樹T轉(zhuǎn)化而來的二叉樹，那么T中節(jié)點的前序就是T2中節(jié)點的前序。若T2是由有序樹T轉(zhuǎn)化而來的二叉樹，那么T中節(jié)點的后序就是T2中節(jié)點的中序。樹最適合用來表示元素之間具有分支層次關(guān)系的數(shù)據(jù)。深度為5的二叉樹至多有31個節(jié)點。在一非空二叉樹的中序遍歷序列中，根節(jié)點的右邊只有右子樹上的所有節(jié)點。在一顆具有n個節(jié)點的二叉樹中，所有節(jié)點的空子樹個數(shù)等于n+1。某二叉樹的前序序列和后序序列正好相反，則該二叉樹一定是高度等于其節(jié)點數(shù)的二叉樹。在有n個葉子節(jié)點的哈夫曼樹中，其節(jié)點總數(shù)為2n-1。從概念上講，樹與二叉樹是兩種不同的數(shù)據(jù)結(jié)構(gòu)，將樹轉(zhuǎn)化為二叉樹的基本目的是樹可以采用二叉樹的存儲結(jié)構(gòu)并利用二叉樹的已有算法解決樹的有關(guān)問題。圖一個帶權(quán)聯(lián)通圖的最小生成樹是否唯一？說明在什么情況下最小生成樹有可能不唯一。一個帶權(quán)聯(lián)通圖的最小生成樹不一定唯一。若是圖中同時存在若干個權(quán)值相同的邊，選擇不同點起點，可得到不同的最小生成樹，但這些最小生成樹邊上權(quán)值之和均為定值。用鄰接矩陣表示圖時，矩陣元素的個數(shù)與頂點個數(shù)是否有關(guān)？與邊的條數(shù)是否有關(guān)？矩陣元素的個數(shù)與頂點個數(shù)有關(guān)，頂點個數(shù)為n，則矩陣元素的個數(shù)為n*n；矩陣元素的個數(shù)與邊的條數(shù)無關(guān)。簡述圖的連通分量和圖的生成樹的區(qū)別。圖的連通分量是這個圖的最大連通子圖，就是其本身。圖的生成樹是含有該連通圖的全部頂點的有關(guān)極小連通子圖。在一個圖中，所有頂點的度數(shù)之和等于所有邊數(shù)的2倍。n頂點的無向連通圖至少n-1條邊，至多n（n-1）/2條邊。在利用表示有向圖的鄰接矩陣中，對第i行的元素進行累加，可得到第i個頂點的出度，而對第j列元素進行累加，可得到第j個頂點的入度。一個連通圖的生成樹是該圖的最小連通子圖。若這個連通圖有n個頂點，則它的生成樹有n-1條邊。一個無向圖有n個頂點和e條邊，則所有頂點的度的和為2e。當(dāng)無向圖G的頂點度數(shù)的最大值大于或等于頂點數(shù)的2倍時，G至少有一條回路。已知一個圖的鄰接矩陣表示，刪除所有從第i個節(jié)點出發(fā)的邊的方法是將第i行的值置0。在圖的鄰接表示存儲結(jié)構(gòu)上執(zhí)行深度優(yōu)先遍歷類似于二叉樹的先序遍歷。在圖的鄰接表示存儲結(jié)構(gòu)上執(zhí)行廣度優(yōu)先遍歷類似于二叉樹的按層次遍歷。一個圖的鄰接矩陣表示法是唯一的，而鄰接表表示法是不唯一的。在一個具有n個頂點的有向完全圖中，所含的邊數(shù)為n（n-1）。n個頂點的連通圖中邊的條數(shù)至少為n-1條。表示圖常用的存儲結(jié)構(gòu)為鄰接矩陣和鄰接鏈表。對于一個具有n個頂點和e條邊的有向圖和無向圖，在其對應(yīng)的鄰接表中，所含邊節(jié)點分別有e個和2e個。在一個圖中，所有定點的度數(shù)之和等于所有邊數(shù)的兩倍。在一個有向圖中，所有定點的入度之和等于所有頂點的出度之和的1倍。一個有n個頂點的無向圖最多有n（n-1）/2條邊。常用的查找方法假定對節(jié)點個數(shù)n=50的有序表進行折半查找，則對應(yīng)的折半查找判定樹高度為6，最后一層的節(jié)點個數(shù)為19。對于節(jié)點個數(shù)為n的線性表，若順序查找關(guān)鍵字為k的節(jié)點，則成功查找的時間復(fù)雜度為O（n）。在插入排序和選擇排序中，若原始數(shù)據(jù)已基本有序，則較適合選用插入排序。在最好情況下，對于具有n個元素的正序序列，若采用冒泡排序，所需的比較次數(shù)為n-1。對有序表進行折半查找的過程可用判定樹來描述，其判定樹的形態(tài)只取決于元素的輸入順序。順序查找法適合于存儲結(jié)構(gòu)為順序存儲或鏈接存儲的線性表。對節(jié)點個數(shù)為18的順序存儲有序表，若采用折半查找，則查找第15個節(jié)點的成功查找次數(shù)為3。在一顆深度為h的具有n個節(jié)點的二叉排序樹中，查找所有節(jié)點的最大查找次數(shù)為h。設(shè)有一個長度為100的已排好序的表，用折半查找進行查找，若查找不成功，至少比較7次。從一顆二叉排序樹中查找一個元素時，若元素的值等于根節(jié)點的值，則表明查找成功，若元素的值小于根節(jié)點的值，則繼續(xù)向左子樹查找，若元素的值大于根節(jié)點的值，則繼續(xù)向右子樹查找。二分查找的存儲結(jié)構(gòu)僅限于順序存儲結(jié)構(gòu)，且是有序。采用順序查找方法查找長度為n的線性表時，每個元素的平均查找長度為（n+1）/2。二叉排序樹上的查找長度不僅與節(jié)點個數(shù)有關(guān)，也與二叉排序樹的樹形有關(guān)。常用的排序方法什么是內(nèi)部排序？什么是外部排序？內(nèi)部排序是指待排序的數(shù)據(jù)量不大，在內(nèi)存中進行的排序。外部排序是指待排序的數(shù)據(jù)量較大，內(nèi)存中一次放不下，借助于外存進行排序。學(xué)習(xí)過的排序方法中哪些排序方法是穩(wěn)定的？直接插入排序、冒泡排序是穩(wěn)定的。排序的目的是為了對已排序的數(shù)據(jù)元素進行查找運算。若對一組記錄（46、79、56、38、40、80、35、50、74）進行直接插入排序，當(dāng)把第8個記錄插入到前面已排序的有序表時，為尋找插入位置比較5次。具有24個記錄的序列，采用冒泡排序最少的比較次數(shù)是23次。在對n個元素進行直接插入排序的過程中，最多需要進行n-1趟。在對n個元素進行直接冒泡排序的過程中，至少需要n-1趟完成。排序方法中，從未排序序列中挑選元素，并將其依次放入已排序序列的一端的方法，稱為選擇排序。冒泡排序算法在最好的情況下的元素交換次數(shù)為0。在所有排序方法中，關(guān)鍵字比較的次數(shù)與記錄的初始排列次序無關(guān)的是選擇排序。在待排序的元素序列基本有序的前提下，效率最高的排序方法是插入排序。排序方法中，從未排序序列中挑選元素，并將其依次放入已排序序列的一端的方法稱為選擇排序。設(shè)待排序數(shù)據(jù)元素序列有n個記錄，應(yīng)用冒泡排序方法，進行一趟排序，所需比較和交換記錄的最多次數(shù)分別為n-1、n-1。在插入排序、選擇排序、冒泡排序中，排序時不穩(wěn)定的有選擇排序。在插入和選擇排序中，若初始數(shù)據(jù)基本正序，則選用插入排序；若初始數(shù)據(jù)基本反序，則選用選擇排序。對n個元素的序列進行冒泡排序時，最少的比較次數(shù)是n-1。軟件工程概論什么是軟件危機？軟件危機產(chǎn)生的原因及其主要表現(xiàn)是什么？軟件危機是指軟件開發(fā)和維護工程中遇到的一系列嚴重問題，主要包括2個方面：如何高效的開發(fā)軟件以滿足日益增長的應(yīng)用需求；如何維護數(shù)量不斷膨脹的已有軟件。軟件開發(fā)與程序設(shè)計有什么不同？軟件開發(fā)是指一個軟件項目的開發(fā)，如市場調(diào)查，需求分析，可行性分析，初步設(shè)計，詳細設(shè)計，形成文檔，建立初步模型，編寫詳細代碼，測試修改，發(fā)布等。程序設(shè)計是軟件開發(fā)中的一個子過程。就是根據(jù)前期的調(diào)查，分析，設(shè)計文檔來進行程序設(shè)計。應(yīng)該按什么原則來劃分軟件生存周期的階段？按照軟件產(chǎn)品從開發(fā)、使用、維護、直至被淘汰的過程定義人家的生存周期。分為軟件定義、軟件開發(fā)和軟件維護三個階段。一般來說，應(yīng)該從技術(shù)、經(jīng)濟和操作三個方面研究目標(biāo)系統(tǒng)的可行性。模塊的獨立程序度可以由兩個定性標(biāo)準(zhǔn)度量，這兩個標(biāo)準(zhǔn)分別是耦合和內(nèi)聚。軟件過程包