計算機(jī)軟件基礎(chǔ)

1、C語言基礎(chǔ) C語言有哪些數(shù)據(jù)類型？整型、 實(shí)型、字符型。 為什么程序中的變量使用前必 須先定義？ C程序用到的變量都 必須進(jìn)行定義，即事先定義其類 型。變量一經(jīng)定義，系統(tǒng)就給分配 存儲空間，以存放相應(yīng)常量。 算法和程序的區(qū)別是什么？算 法是有窮的，程序是尢窮的算法 和程序的描述方法不一樣，程序是 用計算機(jī)語言描述的；算法一般不 可執(zhí)行，程序可以執(zhí)行 算法是解決問題的方法、步驟和 思路。 C語言源程序的文件的后綴是 C,經(jīng)過編譯后生成文件的后綴是 OBJ ,經(jīng)過連接后生成文件的后綴 是 eRe。 C程序開發(fā)的四個步驟依次是 提 出問題、構(gòu)造模型、選擇方法、 編寫程序。 數(shù)學(xué)式sin35 +Rco

2、s60的C語言 表達(dá)式為 Sin(35Rpi/180)+cos(60Rpi/180)( 其中 pi=3.14)。 表達(dá)式3R9%2+9%2R5的值為6。 表達(dá)式6.0R(1/2)的值為0。 程序就是算法用某種計算機(jī)語言 表示出來的。 一個變量同時只能被定義為一種 類型。 程序中用到的所有變量必須先定 義后使用。 變量代表內(nèi)存中具有特定屬性的 一個存儲單元，它用來存放也就是 變量的值，這些值是可以改變的。 一個字符型變量只能存儲一個字 符 若a是實(shí)型變量，在執(zhí)行了a=5 后，a仍為實(shí)型變量|。 若a和b類型相同，在執(zhí)行了 a=b 后，b中仍保留原值。 編制C語言程序并上機(jī)運(yùn)行的一 般過程是編輯、

3、編譯、連接、運(yùn) 行。 C語言規(guī)定用戶標(biāo)識符由 字母、 數(shù)字和下劃線組成，且第一個字曠 必須是字母或下劃線。 begin不是C語言的關(guān)鍵字。 順序結(jié)構(gòu)、選擇結(jié)構(gòu)和循環(huán)結(jié)構(gòu) 的程序設(shè)計 請寫出switch語句的一般格式及 注意事項(xiàng)。 一般格式： Switch (表達(dá)式) case常量表達(dá)式1:語句組1; break ; Case常量表達(dá)式 2 :語句 組2; break ; Case常量表達(dá)式 n:語句 組n; break ; Default :語句組 n+1; 1switch 中表達(dá) 式可以是任意類 型，常用的是字 符或整型。2每 個常量表達(dá)式的 值不能相同。3 語句組可以為任 意語句。4bre

4、ak 可以省略，然后 執(zhí)行完本組語句 后緊接著執(zhí)行其 后的i+1組語 句。5多個case 可以用一組執(zhí)行 語句。6break的 作用是跳出 switch ,執(zhí)行 switch下面的語 句。 試說明while語句和do-while 語 句的異同：二者相同點(diǎn)在于都可以 進(jìn)行次數(shù)確定的循環(huán)體的次數(shù)。不 同點(diǎn)在于do-while現(xiàn)執(zhí)行循環(huán)中 的語句，然后再判斷條件是否為 真，若為真則繼續(xù)循環(huán)；若為假則 終止循環(huán)。因此， do-while 循環(huán) 至少要執(zhí)行一次循環(huán)語句。而 while則是先判斷條件后執(zhí)行循 環(huán)體 簡述for語句的執(zhí)行過程及注意 事項(xiàng)： 計算機(jī)表達(dá)式1 表達(dá)式2非0 ? 執(zhí)行語句s 計算機(jī)

5、表達(dá)式3 循環(huán)結(jié)束，執(zhí)行下面的語句 注意事項(xiàng)：for語句中的3個表達(dá) 式可以省略但后面的分號不能省 略。 試說明continue語句和break語 句的作用及區(qū)別：break的功能是 跳出本層循環(huán)(對多層循環(huán)而言)， 接著執(zhí)行下面的語句。continue 語句的作用是執(zhí)行continue時， 循環(huán)體中continue下面的語句都 不執(zhí)行，重新進(jìn)行循環(huán)判斷以決定 是否繼續(xù)進(jìn)行下次循環(huán)。Break和 continue 的區(qū)另 U 在于：continue 只結(jié)束本次循環(huán)重新進(jìn)行下次循 環(huán)判斷，而break結(jié)束整個循環(huán)。 結(jié)構(gòu)化程序的三種基本結(jié)構(gòu)包括 順序結(jié)構(gòu)、選擇結(jié)構(gòu)和循環(huán)結(jié)構(gòu)|。 C語言提供的選擇

6、結(jié)構(gòu)語句有if 和 switch。 有一段程序?yàn)椋簑hile (表達(dá)式) 語句1;語句2; 當(dāng)表達(dá)式的值為非零時，執(zhí)行語句 1;當(dāng)表達(dá)式的值為零值時執(zhí)行 語 句2。 do-while 語句中while 后的表達(dá) 式的值最終應(yīng)達(dá)到 0值，才能正常 退出循環(huán)。 在C語言程序的循環(huán)體內(nèi)，若遇到 break |語句時，則立即停止當(dāng)前循 環(huán)；若遇到continue |語句時，則 結(jié)束本次循環(huán)，進(jìn)行下一次循環(huán)判 斷。 C語言中，唯一的三目運(yùn)算符 是二，而的執(zhí)行 的次序是先執(zhí)行！，再執(zhí)行=,再 執(zhí)行=。 k關(guān)于C語言的結(jié)論:可以用 while 語句實(shí)現(xiàn)的循環(huán)一定可以 用for語句實(shí)現(xiàn)；可以用for語句 實(shí)現(xiàn)

7、的循環(huán)一定可以用while 語 句實(shí)現(xiàn)；可以用 do-while語句實(shí) 現(xiàn)的循環(huán)一定可以用while語句 實(shí)現(xiàn)。 C語言程序中，continue語句只能 用于循環(huán)結(jié)構(gòu)|。 C語言中，if和switch語句屬于 程序流程控制語句 。 C語言中，語句while后一對圓括 號中的表達(dá)式可以是任意表達(dá)式。 C語言中，關(guān)于 scanf ()函數(shù)正 確的敘述是利用scanf ()函數(shù)可 以給變量提供數(shù)據(jù)。 C語言中，與語句 while (! E)括 號中的表達(dá)式含義等價的是 E=0. Ci言程序中，for循環(huán)語句中的 表達(dá)式2為一非零常數(shù)且循環(huán)體 內(nèi)無break語句及goto語句，則 循環(huán)體的執(zhí)行次數(shù)為無

8、窮次。 設(shè)i是int型變量，f 是 float型 變量，用下面的語句給這兩個變量 輸入值：scanf (“i=%d , 1=%f ”， 為了把 100 和 765.12 分別賦給i和f，正確的輸入為 i=100 ,仁765.12 v 回車| 設(shè)變量m n, a, b, c, d均為0, 執(zhí)行(m=a=b I I (n=c=d)后， m n的值是1, 0。 設(shè)變量m n, a, b, c, d均為1 , 執(zhí)行“(m=a b) 此程序 片段的輸出結(jié)果是200。 當(dāng)執(zhí)行以下程序段時 R=-1 ; do R=RRR while (! R);循環(huán)體 將執(zhí)行一次|。 執(zhí)行語句：for (i=1 ; i+

9、v 4；) 后；變量i的值是5o 數(shù)組一 若定義“ inta5;”,試說明引用 a、a0和試說明數(shù)組s 在內(nèi)存存儲所占的字節(jié)數(shù)。 因?yàn)?變量的數(shù)據(jù)類型int在使用內(nèi)存 空間的時候一個數(shù)據(jù)占用2個字 節(jié)的存儲空間。而數(shù)組s23內(nèi) 部有6個整型的數(shù)據(jù)，所以一共要 占用12個字節(jié)。 C語言默認(rèn)數(shù)組下標(biāo)的下界是0。 在C語言中，二維數(shù)組元素在內(nèi)存 中的存放順序是按行存入。 若 定義了 一 個二維數(shù) 組 int34;且改數(shù)組的起始地址 為1000,則元素a13的地址為 1014 ( 一個整型變量占兩個字節(jié)) 已知：charstr15 ; str 數(shù)組的 最后一個元素是|str14。 字符串的結(jié)束標(biāo)志是

10、0 。 二維數(shù)組的最小行、列下標(biāo)是0。 一維數(shù)組定義中表示數(shù)組長度的_ 表達(dá)式可以是常量和符號常量，不 得包含變量。 同一數(shù)組中的所有元素所占字節(jié) 數(shù)相同。 引用數(shù)組元素越界時，編譯時不檢 測“下標(biāo)出界是否越界。 C語言中用字符數(shù)組存放字符串 類型。 Staticcharstr=“ ok ; 與 staticcharc= o k ; 不一 樣。 在定義inta54;之后，對 a 的引用正確的是|a00 |。 在執(zhí)行 charstr10= “ China0 ; strlen (str )的結(jié)果是 5。 在C語言中，引用數(shù)組元素寸，其 數(shù)組下標(biāo)的數(shù)據(jù)類型允許是整型 常量或整型表達(dá)式 。 字符串“

11、That 小于字符串“ The。 若有說明：inta4= 1,2,3,4,5,6,7,8,9,10,11,12 ;，則數(shù)組第一維的大小為3 若數(shù)組a有m列，則aij之前 的數(shù)組元素個數(shù)為iRm+j。 函數(shù)調(diào)用：strcat ( strcpR ( str1 , str2 ), str3 )的功能是將串str2 復(fù)制到串 str1 中后再將串 str3 連接到串str1之后。 函數(shù) 寫出函數(shù)定義、函數(shù)聲明、函數(shù)調(diào) 用的一般格式及注意事項(xiàng)。 函數(shù)定義: 函數(shù)類型函數(shù)名(形式參數(shù)列表) 說明部分； 語句部分； 函數(shù)聲明： 其形式為：函數(shù)類型函數(shù)名(); 函數(shù)的調(diào)用：主要函數(shù)通過傳遞一 定的信息來使用被

12、調(diào)函數(shù)的功能。 (1)無返回值的函數(shù)調(diào)用格式 (2) 有返回值的函數(shù)調(diào)用格式 在調(diào)用一個函數(shù)之前，應(yīng)考慮哪 些問題？若被調(diào)函數(shù)和主調(diào)函數(shù) 在一個編譯單位中，在書寫順序上 被調(diào)函數(shù)在主調(diào)函數(shù)之前出現(xiàn)；或 者被調(diào)函數(shù)雖然在主調(diào)函數(shù)之后 出現(xiàn)，而被調(diào)函數(shù)的數(shù)據(jù)類型是整 數(shù)型或字符型，可不對被調(diào)函數(shù)加 以說明。 試說明實(shí)參和形參的關(guān)系。 形參 和實(shí)參的關(guān)系總的來說是一一對 應(yīng)的關(guān)系。具體是：1個數(shù)相等2 順序一致3類型相符(或?qū)崊⒖梢?給形參正確的賦值)。 從用戶角度看，函數(shù)分為庫函數(shù)和 用戶自定義函數(shù)。 若有一下函數(shù)調(diào)用語句：func (a+b, ( R, R) , fun ( n+k, d, (a

13、, b)；在此函數(shù)調(diào)用語句中實(shí)現(xiàn)的 個數(shù)是3。 輸入帶空格的字符串時，應(yīng)該用 gets ()函數(shù)。 求字符串長度的函數(shù)是strlen | 丄。 可以用strcpR |函數(shù)將字符串復(fù)制 到字符數(shù)組中。 變量的作用域是指變量的有效范 圍，在作用域內(nèi)可以引用該變量。 按作用域變量可以分為 |全局變量 和局部變量。 從函數(shù)形式看，函數(shù)分為無參函數(shù) 和有參函數(shù)。 函數(shù)的返回值是通過函數(shù)體中的 return |語句獲得。 若被調(diào)函數(shù)定義為 void類型，則 被調(diào)函數(shù)不帶回任何 - 調(diào)用函數(shù)在被調(diào)用函數(shù) 之前時，一 般要對被調(diào)用函數(shù)做函數(shù)聲明。 C語言規(guī)定不能嵌套定義函數(shù)，但 可以嵌套調(diào)用函數(shù)。 在不同的函

14、數(shù)中定義的變量名若 相同，則他們|表示不同的變量。 C語言總是從主函數(shù)開始執(zhí)行。 實(shí)參和形參占用不同的存儲單元 。 一個函數(shù)可以沒有形式參數(shù)。 在進(jìn)行函數(shù)調(diào)用時，被調(diào)函數(shù)的形 參被分配在內(nèi)存的動態(tài)數(shù)據(jù)區(qū)。 若函數(shù)類型和 return吊句中表達(dá) 式的值不一致，則|以函數(shù)類型為| 準(zhǔn)。 函數(shù)的嵌套調(diào)用是指調(diào)用一個函一| 數(shù)的過程中，又調(diào)用另一個函數(shù)。 若以數(shù)組元素作為函數(shù)的實(shí)參,0 實(shí)參向形參傳送的是 |數(shù)組元素的 值。 C語言中，當(dāng)用數(shù)組名做形參時， 形參數(shù)組改變可以使實(shí)參數(shù)組 之改變。 允許函數(shù)遞歸調(diào)用。 函數(shù)形參的作用范圍只是局限于 所定義的函數(shù)內(nèi)。 函數(shù)調(diào)用時，只能把實(shí)參的值傳送 給形參，

15、形參的值不能傳送給實(shí) 參。 一個函數(shù)返回值的類型是由定義 函數(shù)時指定的函數(shù)類型決定的。 一個C源程序至少包括一個函數(shù)， 主函數(shù)和其他函數(shù)不可調(diào)用。 C語言程序的簡單語句必須用分 號(；)做為語句的結(jié)束符 。 函數(shù)定義的形參可以有一個、多 個，也可以沒有。 C語言程序總是從 main函數(shù)開始 執(zhí)行。 C語言是由主函數(shù)和若干子函數(shù) 構(gòu)成。 在一個源程序文件中定義的全局 變量的有效范圍是從定義變量的| 位置開始到源程序文件結(jié)束。 指針 對指針變量做自加1操作后，一 定增加一個字節(jié)嗎？為什么？不 一定，和數(shù)據(jù)的類型有關(guān)。 分析“ R在定義指針和引用指針 變量時有什么不同？定義語句中 “ p前面的“ R

16、是說明p的類型 是指針變量。而除定義語句外的其 他語句中出現(xiàn)的“ Rp里的“ R 是對p所指變量的引用，即代表它 指向的變量。 試說明指針變量可以進(jìn)行哪些運(yùn) 算。指針變量可以進(jìn)行賦值和簡單 的加減運(yùn)算。 指針又可稱為地址。 專門的指針運(yùn)算符是 , 則與表達(dá)式 Rip+2的值是5. 已定義的一個指針變量可以存放_ 定義相同類型的內(nèi)存單元的地址。 指針變量作為形參時,實(shí)參也可以 是不同類型的指針變量。 指針說明時指定的數(shù)據(jù)類型是指 針變量指向的存儲單元的數(shù)據(jù)類 型。 指針變量賦值時，賦的值是一般變 量而不是地址。 指針變量的值是可以改變的。 變量的指針是變量存儲單元的地 址。 指針變量是指存放變量

17、地址的變 量。 若有定義：intR , Rpb;則正確的 賦值表達(dá)式是 pb= ( 1)使指針p 可以指向變量 ch的定義語句是 char Rp=這時棧頂元素 為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入棧，再出棧；因此可以得 到此出棧序列。 向一個順序棧加一個元素時， 首先 若棧不滿棧頂指針上移，然后|將 元素加入到棧頂位置。

18、 從一個順序棧刪除元素時，首先判 斷棧是否為空，然后若不為空棧 頂指針下移。 一個順序棧存儲于一維數(shù)組am 中，棧頂指針用top表示，當(dāng)棧頂 指針等于-1時，則為空棧；棧頂 指針等于m-1時，則為滿棧。 在一個鏈棧中若棧頂指針等于 NULL則為空棧；在一個鏈隊(duì)列中， 若隊(duì)首指針與隊(duì)尾指針的值相同， 則表示該隊(duì)為|空隊(duì)列。| 在具有n個單元的循環(huán)隊(duì)列中,隊(duì) 滿時共有|n-1個元素。 已知二維 1 : 41:6采用 行序?yàn)橹餍蚍绞酱鎯?，每個元素占 用三個存儲單元，并且A2,2的 存儲地址為1200,元素A3,4的 存儲地址是1224。 若將n階三對角矩陣A按照行序?yàn)?主序方式將所有非零元素存放在

19、一個一維數(shù)組 B中，則該三對角矩 陣在B中共有|3n-2個數(shù)據(jù)元素。 隊(duì)列只能在隊(duì)首進(jìn)行刪除,在隊(duì)尾 進(jìn)行插入。 隊(duì)列屬于數(shù)據(jù)結(jié)構(gòu)中存取受限制 的線性結(jié)構(gòu)。 鏈棧的所有操作都限制在表頭進(jìn) 行，所有沒有必要設(shè)置頭結(jié)點(diǎn)。 鏈棧與順序棧相比，通常不會出現(xiàn) 棧滿的情況。 順序棧是線性結(jié)構(gòu)，鏈棧也是線性 結(jié)構(gòu)。 一個棧的入棧序列是a、b、c、d、 e,則棧的不可能的輸出序列是 dceab。 向順序棧中壓入新元素時，應(yīng)當(dāng)先 移動棧頂指針，再存入元素。I 當(dāng)利用大小為N的數(shù)組順序存儲 一個棧時，假定用 top=N表示棧 空，則向這個棧插入一個元素時， 首先應(yīng)執(zhí)行top語句修改top 指針。 假定利用數(shù)組 a

20、N順序存儲一個 棧，用top表示棧頂指針，top=-1 表示棧空，并已知棧未滿，當(dāng)元素 R進(jìn)棧時所執(zhí)行的操作為 a+top=R 。 假定一個鏈?zhǔn)綏５臈ｍ斨羔樣?top表示，每個節(jié)點(diǎn)的結(jié)構(gòu)為 dataneRt，所進(jìn)行的指針操作為 top=top-neRt 。 一個隊(duì)列的入隊(duì)順序是 1、2、3、 4,則隊(duì)列的輸出順序是 1、2、3、 4。| 假定一個順序隊(duì)列的隊(duì)首和隊(duì)尾 指針分別用front和rear表示， 則判斷對空的條件為 front=rear 。 判定一個循環(huán)隊(duì)列Q (最多元素為 mO ) 為空的條件是 Q-front=Q-rear 。 判定一個循環(huán)隊(duì)列Q (最多元素為 m0為隊(duì)滿的條件是Q

21、-front= | (Q-rear+1 )%m 若將n階對稱矩陣 A按照行序?yàn)橹?序方式將包括主對角線在內(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)。| 棧和隊(duì)列的共同點(diǎn)是只允許在端 點(diǎn)處插入和刪除元素。 在一個鏈隊(duì)中，假設(shè)f和r分別為 隊(duì)首和隊(duì)尾指針，則插入s所指節(jié) 點(diǎn)的運(yùn)算是 r-neRt=s ； r=s。 在一個鏈隊(duì)中，假設(shè)

22、f和r分別為 隊(duì)首和隊(duì)尾指針，則刪除一個節(jié)點(diǎn) 的運(yùn)算是仁f-neRt 。 樹和二叉樹 指出樹和二叉樹的主要區(qū)別樹無 序而二叉樹有序。| 對于一顆具有n個節(jié)點(diǎn)的樹，該樹 中所有節(jié)點(diǎn)的度數(shù)之和為n-1。 在一棵樹中根節(jié)點(diǎn)沒有前驅(qū)節(jié)點(diǎn), 其余每個節(jié)點(diǎn)有且僅有一個直接 前驅(qū)節(jié)點(diǎn)，可以有任意多個直接后 繼節(jié)點(diǎn)。 在一顆二叉樹中,假定度為2的節(jié) 點(diǎn)數(shù)為5個，度為1的節(jié)點(diǎn)數(shù)為6 個，則葉子節(jié)點(diǎn)數(shù)為6個。 具有40個節(jié)點(diǎn)的完全二叉樹，它 的高度為6。 已知 8 個數(shù)據(jù)元素為 34,76,45,18,26,54，92,65，按照 依次插入節(jié)點(diǎn)的方法生成一顆二 叉排序樹，則該樹的深度為5。 二叉樹的5種基本形態(tài)是

23、空二叉 樹、只有根的二叉樹、只有左子 樹的二叉樹、只有右子樹的二叉 樹、左右子樹都有的二叉樹。| 若由3、6、8、12、10作為葉子節(jié) 點(diǎn)的值生成一顆哈夫曼樹，則該樹 的高度為4，帶權(quán)路徑長度 為87。 任意一顆有n個節(jié)點(diǎn)的二叉樹，若 它有m個葉子節(jié)點(diǎn)，則二叉樹上度 為1的節(jié)點(diǎn)個數(shù)為 n-2m+1。 若一顆二叉樹葉子樹為n，在該二 叉樹中，左、右子樹皆非空的節(jié)點(diǎn) 個數(shù)為n-1。 由一個二叉樹的先序和中序或后 序和中序遍歷結(jié)果可以唯一地確 定一顆二叉樹。 二叉樹中，任何一個節(jié)點(diǎn)的度數(shù)為 2。 一顆哈夫曼樹中存在度為1的節(jié) 點(diǎn)。 樹的先根遍歷順序與其對應(yīng)的二 叉樹的先根遍歷序列相同。 按二叉樹的定

24、義，具有3個節(jié)點(diǎn)的 二叉樹有5種。 已知某二叉樹的后序遍歷序列是 dabec，中序遍歷序列是debac， 它的前序遍歷序列是 |cedba。 樹中所有節(jié)點(diǎn)的度等于所有節(jié)點(diǎn) 個數(shù)加-1。| 在一顆度礦3的樹中，度為3的節(jié) 點(diǎn)數(shù)為2個，度為2的節(jié)點(diǎn)數(shù)為1 個，度為1的節(jié)點(diǎn)數(shù)為2個，則度 為0的節(jié)點(diǎn)數(shù)為6個。| 已知某二叉樹的后序遍歷序列是 DACBE中序遍歷序列是DEBAC 則它的前序遍歷序列是EDBAC 在一顆二叉樹上第8層的節(jié)點(diǎn)數(shù) 最多是128。 在深度為苗滿二叉樹中，葉子節(jié) 點(diǎn)的個數(shù)內(nèi)16。| 設(shè)一顆完全二叉樹共有 500個節(jié) 點(diǎn)，則在該二叉樹中有 250個葉子 節(jié)點(diǎn)。 若某二叉樹的前序是s

25、tuwv，中序 是 uwtvs，那么后序?yàn)?wuvts 。 任何一顆二叉樹的葉子節(jié), 序、中序和后序遍歷序列中的相對 依次不發(fā)生改變。 若T2是由有序樹 T轉(zhuǎn)化而來的二 叉樹，那么 T中節(jié)點(diǎn)的前序就是 T2中節(jié)點(diǎn)的前序。 若T2是由有序樹T轉(zhuǎn)化而來的二 叉樹，那么 T中節(jié)點(diǎn)的后序就是 T2中節(jié)點(diǎn)的中序。 樹最適合用來表示 元素之間具有 分支層次關(guān)系的數(shù)據(jù) 。 深度為5的二叉樹至多有 31個節(jié) 點(diǎn)。 在一非空二叉樹的中序遍歷序列 中，根節(jié)點(diǎn)的右邊 只有右子樹上的 所有節(jié)點(diǎn)。 在一顆具有n個節(jié)點(diǎn)的二叉樹中， 所有節(jié)點(diǎn)的空子樹個數(shù)等于n+1。 某二叉樹的前序序列和后序序列 正好相反，則該二叉樹一定是

26、高度 等于其節(jié)點(diǎn)數(shù)的二叉樹。 在有n個葉子節(jié)點(diǎn)的哈夫曼樹中， 其節(jié)點(diǎn)總數(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)值相同 的邊，選擇不同點(diǎn)起點(diǎn)，可得到不 同的最小生成樹，但這些最小生成 樹邊上權(quán)值之和均為定值。 用鄰接矩陣表示圖時，矩陣元素 的個數(shù)與頂點(diǎn)個數(shù)是否有關(guān)？與 邊的條數(shù)是否有關(guān)？矩陣元素的 個數(shù)與頂點(diǎn)個數(shù)有關(guān)，頂點(diǎn)個

27、數(shù)為 n，則矩陣元素的個數(shù)為nRn;矩 陣元素的個數(shù)與邊的條數(shù)無關(guān)。 簡述圖的連通分量和圖的生成樹 的區(qū)別。圖的連通分量是這個圖的 最大連通子圖，就是其本身。圖的 生成樹是含有該連通圖的全部頂 點(diǎn)的有關(guān)極小連通子圖。 在一個圖中，所有頂點(diǎn)的度數(shù)之和 等于所有邊數(shù)的 2倍。 n頂點(diǎn)的無向連通圖至少n-1 |條 邊，至多n ( n-1)/2條邊。 在利用表示有向圖的鄰接矩陣中， 對第i行的元素進(jìn)行累加，可得到 第i個頂點(diǎn)的出度，而對第j列元 素進(jìn)行累加，可得到第j個頂點(diǎn)的 一個連通圖的生成樹是該圖的 最 小連通子圖。若這個連通圖有 個頂點(diǎn)，則它的生成樹有 n-1條 邊。| 一個無向圖有n個頂點(diǎn)和e

28、條邊， 則所有頂點(diǎn)的度的和為 2e。 當(dāng)無向圖 G的頂點(diǎn)度數(shù)的最大值 大于或等于|頂點(diǎn)數(shù)的2倍時，G至 少有一條回 已知一個圖的鄰接矩陣表示，刪除 所有從第i個節(jié)點(diǎn)出發(fā)的邊的方 法是將第i行的值置0。 在圖的鄰接表示存儲結(jié)構(gòu)上執(zhí)行 深度優(yōu)先遍歷類似于二叉樹的先 序遍歷。 在圖的鄰接表示存儲結(jié)構(gòu)上執(zhí)行 廣度優(yōu)先遍歷類似于二叉樹的按 層次遍歷。 一個圖的鄰接矩陣表示法是唯一 的，而 鄰接表表示法是不唯一的。 在一個n個頂點(diǎn)的有向完全 圖中，所含的邊數(shù)為n (n-1 )。 n個頂點(diǎn)的連通圖中 少為n-1條。 表示據(jù)用的存儲結(jié)構(gòu)為|鄰接矩 陣和鄰接鏈表。 對于一個具有n個頂點(diǎn)和e條邊的 有向圖和無向圖

29、，在其對應(yīng)的鄰接 表中，所含邊節(jié)點(diǎn)分別有e個和 2e個。 在二個圖中，所有定點(diǎn)的度數(shù)之和 等于所有邊數(shù)的兩倍。 在一個有向圖中，_所有定點(diǎn)的入度 之和等于所有頂點(diǎn)的出度之和的 1倍。| 一個有n個頂點(diǎn)的無向圖最多有 |n (n-1)/2 條邊。- 找方法 假定對節(jié)點(diǎn)個數(shù) n=50的有序表進(jìn) 行折半查找，則對應(yīng)的折半查找判 定樹高度為6，最后一層的節(jié)點(diǎn)個 數(shù)為19。- 對于節(jié)點(diǎn)個數(shù)為 n的線性表，若順 序查找關(guān)鍵字為 k的節(jié)點(diǎn)，則成功 查找的時間復(fù)雜度為 O(n )。 在插入排序和選擇排序中始 數(shù)據(jù)已基本有序，則較適合選用插 入排序。_ 在最好情況下,對于具有n個元素 的正序序列，若采用冒泡排序

30、， 所 需的比較次數(shù)為|n-1。 對有序表進(jìn)行折半查找的過程可 用判定樹來描述，其判定樹的形態(tài) 只取決于元素的輸入順序。 順序查找法適合于存儲結(jié)構(gòu)為順 序存儲或鏈接存儲的線性表。 對節(jié)點(diǎn)個數(shù)為1的順序存儲有序 表，若采用折半查找，則查找第 15個節(jié)點(diǎn)的成功查找次數(shù)為3。 在一顆深度為h的具有n個節(jié)點(diǎn)的 二叉排序樹中，查找所有節(jié)點(diǎn)的最 大查找次數(shù)為h| 設(shè)有一個長度為 100的已排好序 的表，用折半查找進(jìn)行查找，若查 找不成功，至少 比較7次。 從一顆二叉排序樹中查找一個元 素時，若元素的值等于根節(jié)點(diǎn)的 值，則表明查找成功，若元素的值 小于根節(jié)點(diǎn)的值，則繼續(xù)向|左子樹 查找，若元素的值大于根節(jié)點(diǎn)

31、的 值，則繼續(xù)向|右子樹查找。 二分查找的存儲結(jié)構(gòu)僅限于順序 存儲結(jié)構(gòu)，且是有序 。 采用順序查找方法查找長度為n 的線性表時，每個元素的平均查找 長度為(n+1 ) /2。 二叉排序樹上的查找長度不僅與 節(jié)點(diǎn)個數(shù)有關(guān)，也與二叉排序樹. 的樹形有關(guān)。 常用的排序方法 什么是內(nèi)部排序？什么是外部排 序？內(nèi)部排序是指待排序的數(shù)據(jù)量不大，在內(nèi)存中進(jìn)行的排序。外 部排序是指待排序的數(shù)據(jù)量較大， 內(nèi)存中一次放不下，借助于外存進(jìn) 行排序。 學(xué)習(xí)過的排序方法中哪些排序方 法是穩(wěn)定的？ 直接插入排序、冒泡 排序是穩(wěn)定的。 排序的目的是為了對已排序的數(shù) 據(jù)元素進(jìn)行查找運(yùn)算。 若對一組記錄L46、79、56、38

32、、 40、80、35、50、74)進(jìn)行直接插 入排序，當(dāng)把第8個記錄插入到前 面已排序的有序表時，為尋找插入 位置比較5次。 具有 24個記錄的序列，采用冒泡 排序最少的比較次數(shù)是 |23次。 在對n個元素進(jìn)行直接插入排序 的過程中，最多需要進(jìn)行巴趟。 在對n個元素進(jìn)行直接冒泡排序 的過程中，至少需要也趟完成。 排序方法中，從未排序序列中挑選 元素，并將其依次放入已排序序列 的一端的方法，稱為|選擇排序。 冒泡排序算法在最好的情況下的 元素交換次數(shù)為0。 在所有排序方法中，關(guān)鍵字比較的 次數(shù)與記錄的初始排列次序無關(guān) 的是選擇排序。 在待排序的元素序列基本有序的 前提下，效率最高的排序方法是|插

33、 入排序。_ 排序方法中，從未排序序列中挑選 元素，并將其依次放入已排序序列 的一端的方法稱為|選擇排序|。 設(shè)待排序數(shù)據(jù)元素序n個記 錄，應(yīng)用冒泡排序方法，進(jìn)行一趟 排序，所需比較和交換記錄的最多 次數(shù)分另U為|n-1、n-1。 在插入排序、選擇排序、冒泡排序 中，排序時不穩(wěn)定的有選擇排序。 在插入和選擇排序中，若初始數(shù)據(jù) 基本正序，則選用插入排序；若初 始數(shù)據(jù)基本反序，則選用!選擇排 序。 對n個元素的序列進(jìn)行冒泡排序 時，最少的比較次數(shù)是 n-1。 軟件工程概論| 什么是軟件危機(jī)？軟件危機(jī)產(chǎn)生 的原因及其主要表現(xiàn)是什么？軟 件危機(jī)是指軟件開發(fā)和維護(hù)工程 中遇到的一系列嚴(yán)重問題，主要包 括2個方面：如何高效