計算機軟件基礎(chǔ)

1、For personal use only in study and research; not for commercial useFor personal use only in study and research; not for commercial useC語言基礎(chǔ)C語言有哪些數(shù)據(jù)類型？整型、實型、字符型。為什么程序中的變量使用前必須先定義？C程序用到的變量都必須進行定義，即事先定義其類 型。變量一經(jīng)定義，系統(tǒng)就給分配 存儲空間，以存放相應常量。算法和程序的區(qū)別是什么？算法是有窮的，程序是無窮的；算法和程序的描述方法不一樣，程序是 用計算機語言描述的；算法一般不 可執(zhí)行，程序可以執(zhí)

2、行算法是解決問題的方法、步驟和 思路。C語言源程序的文件的后綴是C，經(jīng)過編譯后生成文件的后綴是OBJ，經(jīng)過連接后生成文件的后綴是 exe。C程序開發(fā)的四個步驟依次是提出問題、構(gòu)造模型、選擇方法、 編寫程序。數(shù)學式sin35° +xcos60的C語言 表達式為Sin(35*pi/180)+cos(60*pi/180)(其 中 pi=3.14) |。表達式3*9%2+9%2*5 的值為6o表達式6.0*(1/2)的值為0。程序就是算法用某種計算機語言 表示出來的|一個變量同時只能被定義為一種 類型。程序中用到的所有變量必須先定義后使用。變量代表內(nèi)存中具有特定屬性的一個存儲單元，它用來存放

3、也就是 變量的值，這些值是可以改變的 。一個字符型變量只能存儲一個字符若a是實型變量，在執(zhí)行了a=5后，a仍為實型變量。若a和b類型相同，在執(zhí)行了 a=b 后，b中仍保留原值。編制C語言程序并上機運行的一般過程是編輯、編譯、連接、運 行。C語言規(guī)定用戶標識符由字母、數(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:語句組

4、n; break ;Default :語句組 n+1打 1switch 中表達 式可以是任意類 型，常用的是字 符或整型。2每 個常量表達式的 值不能相同。3語句組可以為任意語句。4break可以省略，然后 執(zhí)行完本組語句 后緊接著執(zhí)行其后的i+1組語句。5多個case 可以用一組執(zhí)行語句。6break的作用是跳出switch ,執(zhí)行switch下面的語句。試說明while 語句和do-while 語句的異同：二者相同點在于都可 以進行次數(shù)確定的循環(huán)體的次數(shù)。 不同點在于do-while現(xiàn)執(zhí)行循環(huán) 中的語句，然后再判斷條件是否為 真，若為真則繼續(xù)循環(huán)；若為假則 終止循環(huán)。因此，do-while

5、 循環(huán) 至少要執(zhí)行一次循環(huán)語句。而 while則是先判斷條件后執(zhí)行循 環(huán)體 簡述for語句的執(zhí)行過程及注意 事項：計算機表達式1表達式2非0?執(zhí)行語句s計算機表達式 3循環(huán)結(jié)束，執(zhí)行下面的語句 注意事項：for語句中的3個表達 式可以省略但后面的分號不能省 略。試說明continue 語句和break語 句的作用及區(qū)別:break的功能是 跳出本層循環(huán)(對多層循環(huán)而言)， 接著執(zhí)行下面的語句。continue語句的作用是執(zhí)行 continue時， 循環(huán)體中continue 下面的語句都 不執(zhí)行，重新進行循環(huán)判斷以決定 是否繼續(xù)進行下次循環(huán)。Break和 continue的區(qū)別在于：contin

6、ue只結(jié)束本次循環(huá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語言提供的選擇結(jié)構(gòu)語句有if和 switch。有一段程序為：while (表達式)語句1;語句2;當表達式的值為非零時，執(zhí)行語句 1;當表達式的值為零值時執(zhí)行 語 句 2。do-while 語句中 while 后的表達 式的值最終應達到|0值，才能正常 退出循環(huán)。在C語言程序的循環(huán)體內(nèi)，若遇到break |語句時，則立即停止當前循 環(huán)；若遇到continue |語句時，則 結(jié)束本次循環(huán)，進行下一次循環(huán)判 斷。C語言中，唯一的三目運算符 是鼻，而&&

7、是聖目運算符。C語言中，運算符 優(yōu)先級最高 的是&&。C語言中，二是關(guān)系運算符。C語言中，要求運算符數(shù)據(jù)必須是 整型的運算符是%C語言中，語句x= ! a=b ;的執(zhí)行 的次序是先執(zhí)行！,再執(zhí)行=,再 執(zhí)行=。3個關(guān)于C語言的結(jié)論:可以用 while語句實現(xiàn)的循環(huán)一定可以 用for語句實現(xiàn)；可以用for語句 實現(xiàn)的循環(huán)一定可以用while 語句實現(xiàn)；可以用 do-while 語句實 現(xiàn)的循環(huán)一定可以用while 語句實現(xiàn)。C語言程序中，continue語句只能 用于循環(huán)結(jié)構(gòu)|C語言中，if和switch 語句屬于 程序流程控制語句 。C語言中，語句while后一對圓括 號中的表

8、達式可以是任意表達式 。C語言中，關(guān)于 sca nf ()函數(shù)正 確的敘述是 利用 scanf () 函數(shù)可 以給變量提供數(shù)據(jù)。C語言中，與語句 while (! E)括 號中的表達式含義等價的是E=0.C語言程序中，for循環(huán)語句中的中的存放順序是按行存入。語句部分；般要對被調(diào)用函數(shù)做函數(shù)聲明。表達式2為一非零常數(shù)且循環(huán)體若定義了一個二維數(shù)組C語言規(guī)定不能嵌套定義函數(shù)，但內(nèi)無break語句及goto語句，_則int34;且改數(shù)組的起始地址函數(shù)聲明：可以嵌套調(diào)用函數(shù)。循環(huán)體的執(zhí)行次數(shù)為無窮次。為1000，則元素a13的地址為其形式為：函數(shù)類型函數(shù)名（）;在不同的函數(shù)中定義的變量名若設(shè)i是int

9、型變量，f是float 型變量，用下面的語句給這兩個變量1014（ 個整型變量占兩個字節(jié)）已知：char str15; str 數(shù)組的函數(shù)的調(diào)用：主要函數(shù)通過傳遞一 定的信息來使用被調(diào)函數(shù)的功能。相同，則他們|表示不同的變量|C語言總是從主函數(shù)開始執(zhí)行。輸入值：seanf “ i=%d，f=%f ”，最后一個元素是|str14 |（1）無返回值的函數(shù)調(diào)用格式（2）實參和形參占用不同的存儲單元 。& , &f)；為了把 100 和 765.12字符串的結(jié)束標志是 0 '有返回值的函數(shù)調(diào)用格式一個函數(shù)可以沒有形式參數(shù)。分別賦給i和f，正確的輸入為二維數(shù)組的最小行、列下標是0

10、。在調(diào)用一個函數(shù)之前，應考慮哪在進行函數(shù)調(diào)用時，被調(diào)函數(shù)的形i=100 ,仁765.12 v 回車|一維數(shù)組定義中表示數(shù)組長度的些問題？若被調(diào)函數(shù)和主調(diào)函數(shù)參被分配在內(nèi)存的動態(tài)數(shù)據(jù)區(qū)。設(shè)變量m n, a, b, c, d均為0,表達式可以是常量和符號常量，不在一個編譯單位中，在書寫順序上若函數(shù)類型和return語句中表達執(zhí)行 (m=a=b) II ( n二 c=d)后，得包含變量|被調(diào)函數(shù)在主調(diào)函數(shù)之前出現(xiàn)；或式的值不一致，則|以函數(shù)類型為m n的值是1 , 0。同一數(shù)組中的所有元素所占字節(jié)者被調(diào)函數(shù)雖然在主調(diào)函數(shù)之后準。設(shè)變量m n, a, b, c, d均為1,數(shù)相同。出現(xiàn)，而被調(diào)函數(shù)的數(shù)

11、據(jù)類型是整函數(shù)的嵌套調(diào)用是1指調(diào)用一個函執(zhí)行“(m=a> b) && ( n=a> b)” 后引用數(shù)組元素越界時，編譯時不檢數(shù)型或字符型，可不對被調(diào)函數(shù)加數(shù)的過程中，又調(diào)用另一個函數(shù)。m n的值是0, 1。測"下標出界"是否越界。以說明。若以數(shù)組元素作為函數(shù)的實參，則若x和y都是int型變量，x=100 ,C語言中用字符數(shù)組存放字符串試說明實參和形參的關(guān)系。形參實參向形參傳送的是1數(shù)組元素的y=200，且有下面的程序片段：類型。和實參的關(guān)系總的來說是一一對值。printf“'d', ( x, y);此程序Static char s

12、tr=“ ok" 與應的關(guān)系。具體是：1個數(shù)相等2C語言中，當用數(shù)組名做形參時，片段的輸出結(jié)果是 200。static char c=' o' k' 不順序一致3類型相符（或?qū)崊⒖梢孕螀?shù)組改變可以使實參數(shù)組隨當執(zhí)行以下程序段時一樣。給形參正確的賦值）。之改變。x=-1 ；在定義int a54;之后，對 a從用戶角度看，函數(shù)分為庫函數(shù)和允許函數(shù)遞歸調(diào)用。do x=x*x + while (! x);循環(huán)體的引用正確的是|a00 |用戶自定義函數(shù)|函數(shù)形參的作用范圍只是局限于將執(zhí)行一次1在執(zhí)行 char str10=“ China0 "若有一下函數(shù)調(diào)用

13、語句：func所定義的函數(shù)內(nèi)。執(zhí)行語句：for （ i=1 ; i+ v 4；）strlen ( str )的結(jié)果是5。(a+b, (x , y), fun (n+k, d, (a,函數(shù)調(diào)用時，只能把實參的值傳送后；變量i的值是5。在C語言中，引用數(shù)組元素時，其b）；在此函數(shù)調(diào)用語句中實現(xiàn)的給形參，形參的值不能傳送給實1數(shù)組數(shù)組下標的數(shù)據(jù)類型允許是整型個數(shù)是3。參。若定義“ int a5;"，試說明引常量或整型表達式。輸入帶空格的字符串時，應該用一個函數(shù)返回值的類型是由定義用a、a0和&a1的含義。a代字符串“ That ”小于字符串“ The ”。gets （）函數(shù)。函數(shù)時

14、指定的函數(shù)類型決定的。表數(shù)組名，a0代表數(shù)組的第一個若有說明：inta4=求字符串長度的函數(shù)是|strlen一個C源程序至少包括一個函數(shù)，元素，&a1代表數(shù)組第二個元素1,2,3,4,5,6,7,8,9,10,11,12主函數(shù)和其他函數(shù)不可調(diào)用。的地址。;，則數(shù)組第一維的大小為3?？梢杂胹trcpy函數(shù)將字符串復制C語言程序的簡單語句 1必須用分在C語言數(shù)值表示中， a' “ a"若數(shù)組a有m列，則aij之前到字符數(shù)組中。號（；）做為語句的結(jié)束符1相同嗎？不同，a '表示一個字符，的數(shù)組元素個數(shù)為i*m+j。變量的作用域是指變量的有效范函數(shù)定義的形參可以有一個

15、、多而"a"表示一個字符串。函數(shù)調(diào)用：strcat (strcpy (str1 ,圍，在作用域內(nèi)可以引用該變量。個，也可以沒有。已知：int s23;試說明數(shù)組str2 ) , str3 )的功能是將串str2按作用域變量可以分為全局變量C語言程序總是從main函數(shù)開始s在內(nèi)存存儲所占的字節(jié)數(shù)。因為復制到串str1 中后再將串 str3和局部變量。執(zhí)行。變量的數(shù)據(jù)類型int在使用內(nèi)存連接到串str1之后。從函數(shù)形式看，函數(shù)分為無參函數(shù)C語言是由主函數(shù)和若干子函數(shù)空間的時候一個數(shù)據(jù)占用2個字節(jié)的存儲空間。而數(shù)組s23內(nèi)函數(shù)寫出函數(shù)定義、函數(shù)聲明、函數(shù)調(diào)和有參函數(shù)。函數(shù)的返回值

16、是通過函數(shù)體中的構(gòu)成。在一個源程序文件中定義的全局部有6個整型的數(shù)據(jù)，所以一共要用的一般格式及注意事項。return |語句獲得。變量的有效范圍是|從定義變量的占用12個字節(jié)。函數(shù)定義:若被調(diào)函數(shù)定義為|void類型，則位置開始到源程序文件結(jié)束1。c語言默認數(shù)組下標的下界是0。函數(shù)類型函數(shù)名（形式參數(shù)列表）被調(diào)函數(shù)不帶回任何值。指針在C語言中，二維數(shù)組元素在內(nèi)存說明部分；調(diào)用函數(shù)在被調(diào)用函數(shù)之前時，一對指針變量做自加1操作后，一定增加一個字節(jié)嗎？為什么？不一定，和數(shù)據(jù)的類型有關(guān)。分析“ *"在定義指針和引用指針 變量時有什么不同？定義語句中“ p"前面的“ * "

17、是說明p的類型 是指針變量。而除定義語句外的其 他語句中出現(xiàn)的“ *p"里的“ *” 是對p所指變量的引用，即代表它 指向的變量。試說明指針變量可以進行哪些運 算。指針變量可以進行賦值和簡單 的加減運算。指針又可稱為地址。專門的指針運算符是 &和*。只有先定義一個指針型變量,才能 將另一個變量的地址存放在改變 量中。若指針變量p指向整型變量i,則i變量又可用*p表示。若指針變量p指向float 型數(shù)組a10，且a的首地址為 1000，則執(zhí)行p+3后，p應該指向地址為1012單元。malloc （）函數(shù)用來在內(nèi)存中分配 一個指定長度的存儲空間。C 語言中，若 int a5 ,

18、i , *p=a ;, 則與&ai等價的指針表示是 p+i，與ai等價的指針表示是*（p+i ）。已知：int a= 1,3,5,7,9,*ip=a ;表達式*ip+2的值是5.已定義的一個指針變量可以存放定義相同類型的內(nèi)存單元的地址。指針變量作為形參時，實參也可以 是不同類型的指針變量。指針說明時指定的數(shù)據(jù)類型是指 針變量指向的存儲單元的數(shù)據(jù)類 型。指針變量賦值時，賦的值是一般變 量而不是地址|指針變量的值是可以改變的。變量的指針是變量存儲單元的地 址。指針變量是指存放變量地址的變量。若有定義：int x, *pb ;則正確的 賦值表達式是pb=&x。若有定義：char ch

19、 ; （ 1）使指針 p可以指向變量 ch的定義語句是 char *p=&ch 。（ 2）使指針p指向 變量ch的賦值語句是 p=&ch。（ 3） 通過指針p給變量ch讀入字符的 scanf 函數(shù)調(diào)用語句是scanf “ ” p）。（4）通過指針p給變 量ch賦字符的語句是 ch=*p。（ 5） 通過指針p輸出ch中字符的語句 是 putchar （*p ）。數(shù)據(jù)結(jié)構(gòu)概論通常將數(shù)據(jù)結(jié)構(gòu)表示為一個二元 組（D, R）,其中D和R分別表示 什么？ D代表數(shù)據(jù)節(jié)點的集合，R是D上的關(guān)系。什么是數(shù)據(jù)的邏輯結(jié)構(gòu)？什么是 數(shù)據(jù)的物理結(jié)構(gòu)？ 一般情況下， 兩者之間有什么關(guān)系？這種關(guān)系 是如何

20、反映的？數(shù)據(jù)的邏輯結(jié)構(gòu)是數(shù)據(jù)間的外在聯(lián)系（與計算機存 儲無關(guān)）；數(shù)據(jù)的物理結(jié)構(gòu)是數(shù)據(jù) 在計算機中的存儲表示，也稱數(shù)據(jù)的存儲結(jié)構(gòu)。一般情況下，二者的 關(guān)系是相互運算，如何把邏輯結(jié)構(gòu) 數(shù)據(jù)存入計算機；如何把機內(nèi)表示 的數(shù)據(jù)取出來參加運算，在邏輯結(jié) 構(gòu)和物理結(jié)構(gòu)之間轉(zhuǎn)換以及其他 運算過程中，數(shù)據(jù)如何組織才能即 節(jié)省時間，又節(jié)約空間，更重要的 是機內(nèi)表示的數(shù)據(jù)取出來后要完 全體現(xiàn)其邏輯結(jié)構(gòu)。什么是算法？算法與程序有何區(qū) 別與聯(lián)系？算法就是解決特定問題的的方法。而程序是通過某種語 言將算法的具體實現(xiàn)手段。算法的時間復雜度僅與問題的規(guī) 模相關(guān)嗎？不是。算法的時間復雜 度還與算法中的語句頻度、數(shù)據(jù)的 狀態(tài)等

21、因素有關(guān)。數(shù)據(jù)結(jié)構(gòu)是指邏輯結(jié)構(gòu)和物理結(jié)| 構(gòu)兩種，通常是指邏輯結(jié)構(gòu)。選擇合適的存儲結(jié)構(gòu)，通?？紤]的 指標有|邏輯結(jié)構(gòu)和數(shù)據(jù)類型 兩個 因素。數(shù)據(jù)結(jié)構(gòu)按節(jié)點間的關(guān)系，可分為4種，分別是|集合、線性結(jié)構(gòu)、樹| 形結(jié)構(gòu)和網(wǎng)狀結(jié)構(gòu)。| 線性結(jié)構(gòu)反映節(jié)點間的關(guān)系是二對一的，樹形結(jié)構(gòu)反映節(jié)點間的關(guān) 系是一對多的，網(wǎng)狀結(jié)構(gòu)反映節(jié)點 間的關(guān)系是多對多的。數(shù)據(jù)的邏輯結(jié)構(gòu)是數(shù)據(jù)之間的外 在聯(lián)系（與計算機存儲無關(guān)）。數(shù)據(jù)的邏輯結(jié)構(gòu)與數(shù)據(jù)元素的相 對位置相關(guān)。數(shù)據(jù)的邏輯結(jié)構(gòu)與其所含數(shù)據(jù)元素的個數(shù)無關(guān)。數(shù)據(jù)元素之間的邏輯關(guān)系與存儲單元的相鄰關(guān)系無關(guān)。在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù) 據(jù)結(jié)構(gòu)分為線性結(jié)構(gòu)和非線性結(jié) 構(gòu)。數(shù)據(jù)

22、結(jié)構(gòu)是一門研究操作對象以 及他們之間的關(guān)系和運算等的學 科。算法分析的目的是 分析算法的效 率以求改進。算法分析的兩個主要方面是空間復雜性和時間復雜性 | 計算機算法是指可讀性科文檔性。線性表簡述單鏈表、循環(huán)單鏈表、循環(huán) 雙鏈表的結(jié)構(gòu)特點。（1）單鏈表的 結(jié)構(gòu)：由節(jié)點構(gòu)成，每個節(jié)點有兩 個成員：數(shù)據(jù)域和指針域。單鏈表 的特點：每個節(jié)點都只有一個指向 直接后繼節(jié)點的指針，最后一個節(jié) 點的指針域為空，單鏈表是只有一 個鏈域的鏈表。（2）循環(huán)單鏈表結(jié) 構(gòu)：由節(jié)點構(gòu)成，每個節(jié)點有兩個 成員：數(shù)據(jù)域和指針域。循環(huán)單鏈 表特點：鏈表中最后一個節(jié)點的指 針域指向頭結(jié)點，整個鏈表形成一 個環(huán)。（3）循環(huán)雙鏈表

23、結(jié)構(gòu)：由節(jié) 點構(gòu)成，每個節(jié)點包括三個域：數(shù)據(jù)域、前驅(qū)指針域和后繼指針域。 循環(huán)雙鏈表特點：節(jié)點的next指針域指向后繼節(jié)點，prior指針域 指向前驅(qū)節(jié)點。簡述順序表和鏈表的主要優(yōu)、缺 點及適用范圍。（1）順序表用一組 地址連續(xù)的存儲單元存放線性表 中的數(shù)據(jù)，表中元素的物理關(guān)系和 邏輯關(guān)系是一致的。表中元素可以 隨機存取，但在程序執(zhí)行之前必須 給出空間長度，容易造成空間浪費 或者空間不夠的情況。鏈表用一組 任意的存儲單元存儲線性表的數(shù) 據(jù)元素，利用指針實現(xiàn)了用不相鄰 的存儲單元存放邏輯上相鄰的元 素。存儲空間動態(tài)分配，不會產(chǎn)生 溢出，但空間利用率低，節(jié)點訪問 需要從表頭開始依次訪問。（2）順

24、序表適用于經(jīng)常進行查找運算的 數(shù)據(jù)，或者對數(shù)據(jù)量事先固定的問 題。鏈表適用于經(jīng)常進行插入、刪除等數(shù)據(jù)量變化較大的動態(tài)問題。 比較線性表的順序存儲結(jié)構(gòu)與鏈 式存儲結(jié)構(gòu)存儲空間開銷大小， 并說明理由。順序存儲結(jié)構(gòu)存儲空 間開銷小，鏈式存儲結(jié)構(gòu)存儲空間 開銷大。存儲空間開銷大小可以用 存儲密度衡量。存儲密度=節(jié)點數(shù) 據(jù)域所占空間/節(jié)點所占空間。節(jié) 點存儲密度越大，空間利用率越 高，則存儲空間開銷越小。 順序存 儲結(jié)構(gòu)每個節(jié)點占一個空間，即存儲數(shù)據(jù)域的空間，而鏈式存儲結(jié)構(gòu) 每個節(jié)點所占兩個空間，即存儲數(shù) 據(jù)域的空間和存儲指針域的空間。 對于線性表的順序存儲結(jié)構(gòu)與鏈 式存儲而言，若線性表的長度基 本穩(wěn)定

25、，且很少進行插入與刪除 操作，但要盡快地存取表中的數(shù) 據(jù)元素，則應該選擇哪種存儲結(jié) 構(gòu)？為什么？應該選擇順序存儲結(jié)構(gòu)。因為線性表的長度基本穩(wěn) 定，可以預先進行分配，且要求盡 快地存取表中的數(shù)據(jù)元素，而順序 表中元素可以隨機存取。若頻繁地對線性表進行插入與刪 除操作，該線性表應該采取什么 存儲結(jié)構(gòu)？為什么？應該選擇鏈式存儲結(jié)構(gòu)。對線性表進行插入與 刪除操作，順序表需要大量移動元 素，而鏈表只需要修改需要相應的 指針域就可以了。有哪些鏈表可僅由一個尾指針來 唯一確定，即從尾指針出發(fā)能訪 問到鏈表上任意一個節(jié)點？循環(huán)單鏈表和循環(huán)雙鏈表。在單鏈表、循環(huán)單鏈表和循環(huán)雙 鏈表中，若僅知道指針p指向某節(jié)點，

26、不知道頭指針，能否將節(jié) 點*p從相應的鏈表中刪除？若可以，且時間復雜度各為多少？單鏈表不可以。循環(huán)單鏈表、循環(huán)雙 鏈表可以。單鏈表時間復雜度O（n），循環(huán)單鏈表時間復雜度O（n），循環(huán)雙鏈表時間復雜度O（1）。線性表的兩種存儲結(jié)構(gòu)分別為順序表結(jié)構(gòu)和鏈表結(jié)構(gòu) 。訪問一個線性表中具有定值元素的時間復雜度為 O（ n）。對于一個為n的順序存儲的線性表，在表頭插入元素的時間復雜性為O（n），在表尾插入元素的時間 復雜性為0（ 1 ）。線性表是一個有限序列，可以為 空。一個線性表是 n個數(shù)據(jù)元素的有 限序列。在一個順序表的表尾插入一個元素的時間復雜度為 0（ 1 ）。在一個單鏈表中，若要在p所指向 的節(jié)

27、點插入一個新節(jié)點，則需要相 繼修改2個指針域的值。在一個單鏈表中，若要在p所指向 的節(jié)點插入一個新節(jié)點，則此算法 的時間復雜度為 O （ n）。在一個帶頭節(jié)點的雙向循環(huán)鏈表中，若要在p所指向的節(jié)點之前插 入一個新節(jié)點，則需要相繼修改|4 個指針域的值。線性結(jié)構(gòu)的特征：有且只有一個 根節(jié)點，它無前件；有且只有一個 終端節(jié)點，它無后件；除根節(jié)點和 終端節(jié)點以外，其他節(jié)點有且只有 一個前件，也有且只有一個后件。 在單鏈表中，增加頭節(jié)點的目的是 方便運算的實現(xiàn)。用鏈表表示線性表的優(yōu)點是便于插入和刪除操作。在線性表的順序存儲中，元素之間 的邏輯關(guān)系是通過物理存儲位置 決定的；在線性表的鏈接存儲中， 元素

28、之間的邏輯關(guān)系是通過鏈域的指針值決定的。在雙向鏈表中，每個節(jié)點包含兩個 指針域，一個指向前驅(qū)結(jié)點，另一 個指向后繼結(jié)點。在線性表的順序存儲中，若一個元 素的下標為i，則它的前驅(qū)元素的 下標為i丄，后繼元素的下標為 i+i。一個線性表中，第一個元素的存儲 地址是100，每個元素的長度是 2, 則第五個元素的地址 是108。棧、隊列和數(shù)組簡述棧和隊列的相同點和不同點。 相同點：都是存儲數(shù)據(jù)的線性表。不同點：棧為LIFO （后進線出） 線性表，插入、刪除操作均在表尾 進行。隊列為 FIFO （先進先出） 線性表，插入在表尾進行、刪除在 表頭進行。若進棧的數(shù)據(jù)元素序列依次為1、2、3、4、5、6，能否

29、得到 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 出

30、棧，然后4出棧，然后2出棧； 之后6入棧，再出棧；因此可以得 到此出棧序列。向一個順序棧加一個元素時，首先若棧不滿棧頂指針上移，然后將元素加入到棧頂位置。| 從一個順序棧刪除元素時，首先判 斷棧是否為空，然后若不為空棧 頂指針下移。一個順序棧存儲于一維數(shù)組am中，棧頂指針用top表示，當棧頂 指針等于二時，則為空棧；棧頂 指針等于|m-1時，則為滿棧。 在一個鏈棧中，若棧頂指針等于 NULL則為空棧；在一個鏈隊列中， 若隊首指針與隊尾指針的值相同， 則表示該隊為|空隊列。在具有n個單元的循環(huán)隊列中，隊 滿時共有|n-1個元素。已知二維數(shù)組 A1 : 41:6采用 行序為主序方式存儲，每個元素占

31、用三個存儲單元，并且A2,2的存儲地址為1200，元素A3,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。向順序棧中壓入新元素時，應當先移動棧頂指針，再存入元素。當利用大小為 N的數(shù)組順序

32、存儲 一個棧時，假定用 top=N表示棧 空，則向這個棧插入一個元素時， 首先應執(zhí)行|top語句修改top指針。假定利用數(shù)組 aN順序存儲一個棧，用top表示棧頂指針，top=-1表示?？眨⒁阎獥Ｎ礉M，當元素 x進棧時所執(zhí)行的操作為 a+top=x。假定一個鏈式棧的棧頂指針用 top表示，每個節(jié)點的結(jié)構(gòu)為 datanext，所進行的指針操作為 top=top->next 。一個隊列的入隊順序是1、2、3、4,則隊列的輸出順序是|1、2、3、4。假定一個順序隊列的隊首和隊尾指針分別用front和rear表示，則判斷對空的條件為 front=rear 。判定一個循環(huán)隊列Q （最多元素為m0

33、 ） 為空的條件是Q->fro nt=Q->rear。判定一個循環(huán)隊列 Q （最多元素為m0為隊滿的條件是Q->fr on t=(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)和鏈式存儲結(jié) 構(gòu)。棧和隊列的共同點是只允許在端點處插入和刪除元素

34、。在一個鏈隊中，假設(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,

35、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ù)

36、為2。一顆哈夫曼樹中存在度為1的節(jié)點。樹的先根遍歷順序與其對應的二 叉樹的先根遍歷序列相同。按二叉樹的定義，具有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è)一顆完全二叉樹共有

37、 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

38、。 某二叉樹的前序序列和后序序列 正好相反，則該二叉樹一定是高度 等于其節(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)？

39、矩陣元素的 個數(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

40、-1條 邊。一個無向圖有n個頂點和e條邊， 則所有頂點的度的和為 |2e_當無向圖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)為 鄰接矩 陣和鄰接鏈表|對于一

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

42、序序列，若采用冒泡排序，所 需的比較次數(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é)點的

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

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

45、將其依次放入已排序序列 的一端的方法稱為|選擇排序。 設(shè)待排序數(shù)據(jù)元素序列有n個記錄，應用冒泡排序方法，進行一趟 排序，所需比較和交換記錄的最多 次數(shù)分別為 n-1、n-1。在插入排序、選擇排序、冒泡排序 中，排序時不穩(wěn)定的有選擇排序。 在插入和選擇排序中，若初始數(shù)據(jù) 基本正序，則選用插入排序；若初 始數(shù)據(jù)基本反序，則選用 選擇排 序。對n個元素的序列進行冒泡排序時，最少的比較次數(shù)是n-1。軟件工程概論什么是軟件危機？軟件危機產(chǎn)生的原因及其主要表現(xiàn)是什么？軟件危機是指軟件開發(fā)和維護工程括2個方面：如何高效的開發(fā)軟件 以滿足日益增長的應用需求；如何維護數(shù)量不斷膨脹的已有軟件。軟件開發(fā)與程序設(shè)計有什么不 同？軟件開發(fā)是指一個軟件項目 的開發(fā)，如市場調(diào)查，需求分析， 可行性分析，初步設(shè)計，詳細設(shè)計， 形成文檔，建立初步模型，編寫詳 細代碼，測試修改，發(fā)布等。程序 設(shè)計是軟件開發(fā)中的一個子過程。就是根據(jù)前期的調(diào)查，分析，設(shè)計 文檔來進行程序設(shè)計。應該按什么原則來劃分軟件生存 周期的階段？ 按照軟件產(chǎn)品從開 發(fā)、使用、維護、直至被淘汰的過 程定義人家的生存周期。分為軟件 定義、軟件開發(fā)和軟件維護三個階 段。一般來說，應該從技術(shù)、經(jīng)濟和操 作三個方面研究目標系統(tǒng)的可行 性。模塊的獨立程序度可以由兩個定 性標準度量，這兩個標準分別是耦 合和內(nèi)聚。軟件過程包括3