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

2、i/180)+cos(60*pi/180)(其中pi=3.14)。表達(dá)式3*9%2+9%2*5的值為6。表達(dá)式6.0*(1/2)的值為0。程序就是算法用某種計(jì)算機(jī)語言表示出來的。一個(gè)變量同時(shí)只能被定義為一種類型。程序中用到的所有變量必須先定義后使用。變量代表內(nèi)存中具有特定屬性的一個(gè)存儲(chǔ)單元，它用來存放也就是變量的值，這些值是可以改變的。一個(gè)字符型變量只能存儲(chǔ)一個(gè)字符若a是實(shí)型變量，在執(zhí)行了a=5后，a仍為實(shí)型變量。若a和b類型相同，在執(zhí)行了a=b后，b中仍保留原值。編制C語言程序并上機(jī)運(yùn)行的一般過程是編輯、編譯、連接、運(yùn)行。C語言規(guī)定用戶標(biāo)識(shí)符由字母、數(shù)字和下劃線組成，且第一個(gè)字符必須是字母或

3、下劃線。begin不是C語言的關(guān)鍵字。順序結(jié)構(gòu)、選擇結(jié)構(gòu)和循環(huán)結(jié)構(gòu)的程序設(shè)計(jì)請(qǐng)寫出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每個(gè)常量表達(dá)式的值不能相同。3語句組可以為任意語句。4break可以省略，然后執(zhí)行完本組語句后緊接著執(zhí)行其后的i+1組語句。5多個(gè)case可以用一組執(zhí)行語句。6break的作用是跳出switch，執(zhí)行switch下面的語句

4、。 試說明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)體簡(jiǎn)述for語句的執(zhí)行過程及注意事項(xiàng)：計(jì)算機(jī)表達(dá)式1表達(dá)式2非0？執(zhí)行語句s計(jì)算機(jī)表達(dá)式3循環(huán)結(jié)束，執(zhí)行下面的語句注意事項(xiàng)：for語句中的3個(gè)表達(dá)式可以省略但后面的分號(hào)不能省略。試說明continue語句和break語句的作用及區(qū)別：break的功能是跳出本層循環(huán)（對(duì)多層循環(huán)而言），接著執(zhí)行下面的語句。c

5、ontinue語句的作用是執(zhí)行continue時(shí)，循環(huán)體中continue下面的語句都不執(zhí)行，重新進(jìn)行循環(huán)判斷以決定是否繼續(xù)進(jìn)行下次循環(huán)。Break和continue的區(qū)別在于：continue只結(jié)束本次循環(huán)重新進(jìn)行下次循環(huán)判斷，而break結(jié)束整個(gè)循環(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。有一段程序?yàn)椋簑hile（表達(dá)式）語句1；語句2；當(dāng)表達(dá)式的值為非零時(shí)，執(zhí)行語句1 ；當(dāng)表達(dá)式的值為零值時(shí)執(zhí)行語句2。do-while語句中while后的表達(dá)式的值最終應(yīng)達(dá)到0值，才能正常退出循環(huán)。在C語言程序的循環(huán)體內(nèi)，若遇到break語

6、句時(shí)，則立即停止當(dāng)前循環(huán)；若遇到continue語句時(shí)，則結(jié)束本次循環(huán)，進(jìn)行下一次循環(huán)判斷。C語言中，唯一的三目運(yùn)算符是？：，而&.&.是雙目運(yùn)算符。C語言中，運(yùn)算符優(yōu)先級(jí)最高的是&.&.。C語言中，是關(guān)系運(yùn)算符。C語言中，要求運(yùn)算符數(shù)據(jù)必須是整型的運(yùn)算符是%C語言中，語句x=！a=b；的執(zhí)行的次序是先執(zhí)行！，再執(zhí)行=，再執(zhí)行=。3個(gè)關(guān)于C語言的結(jié)論：可以用while語句實(shí)現(xiàn)的循環(huán)一定可以用for語句實(shí)現(xiàn)；可以用for語句實(shí)現(xiàn)的循環(huán)一定可以用while語句實(shí)現(xiàn)；可以用do-while語句實(shí)現(xiàn)的循環(huán)一定可以用while語句實(shí)現(xiàn)。C語言程序中，continue語句只

7、能用于循環(huán)結(jié)構(gòu)。C語言中，if和switch語句屬于程序流程控制語句。C語言中，語句while后一對(duì)圓括號(hào)中的表達(dá)式可以是任意表達(dá)式。C語言中，關(guān)于scanf（）函數(shù)正確的敘述是利用scanf（）函數(shù)可以給變量提供數(shù)據(jù)。C語言中，與語句while（！E）括號(hào)中的表達(dá)式含義等價(jià)的是E=0.C語言程序中，for循環(huán)語句中的表達(dá)式2為一非零常數(shù)且循環(huán)體內(nèi)無break語句及goto語句，則循環(huán)體的執(zhí)行次數(shù)為無窮次。設(shè)i是int型變量，f是float型變量，用下面的語句給這兩個(gè)變量輸入值：scanf（“i=%d，f=%f”，&i，&f）；為了把100和765.12分別賦給i和f，正確的輸

8、入為i=100，f=765.12回車。設(shè)變量m，n，a，b，c，d均為0，執(zhí)行（m=a=b）（n=c=d）后，m，n的值是1，0。設(shè)變量m，n，a，b，c，d均為1，執(zhí)行“（m=ab）&&（n=ab）”后m，n的值是0，1。若x和y都是int型變量，x=100，y=200，且有下面的程序片段：printf（“%d”，（x，y）；此程序片段的輸出結(jié)果是200。當(dāng)執(zhí)行以下程序段時(shí)x=-1；dox=x*xwhile（！x）；循環(huán)體將執(zhí)行一次。執(zhí)行語句：for（i=1；i+4；）后；變量i的值是5。數(shù)組若定義“int a5；”，試說明引用a、a0和&a1的含義。a代表數(shù)組名，a

9、0代表數(shù)組的第一個(gè)元素，&a1代表數(shù)組第二個(gè)元素的地址。在C語言數(shù)值表示中，a“a”相同嗎？不同，a表示一個(gè)字符，而“a” 表示一個(gè)字符串。已知：int s23；試說明數(shù)組s在內(nèi)存存儲(chǔ)所占的字節(jié)數(shù)。因?yàn)樽兞康臄?shù)據(jù)類型int在使用內(nèi)存空間的時(shí)候一個(gè)數(shù)據(jù)占用2個(gè)字節(jié)的存儲(chǔ)空間。而數(shù)組s23內(nèi)部有6個(gè)整型的數(shù)據(jù)，所以一共要占用12個(gè)字節(jié)。C語言默認(rèn)數(shù)組下標(biāo)的下界是0。在C語言中，二維數(shù)組元素在內(nèi)存中的存放順序是按行存入。若定義了一個(gè)二維數(shù)組int34；且改數(shù)組的起始地址為1000，則元素a13的地址為1014。（一個(gè)整型變量占兩個(gè)字節(jié)）已知：char str15；str數(shù)組的最后一個(gè)元素是s

10、tr14。字符串的結(jié)束標(biāo)志是0。二維數(shù)組的最小行、列下標(biāo)是0。一維數(shù)組定義中表示數(shù)組長(zhǎng)度的表達(dá)式可以是常量和符號(hào)常量，不得包含變量。同一數(shù)組中的所有元素所占字節(jié)數(shù)相同。引用數(shù)組元素越界時(shí)，編譯時(shí)不檢測(cè)“下標(biāo)出界”是否越界。C語言中用字符數(shù)組存放字符串類型。Static char str=“ok”；與static char c=ok；不一樣。在定義int a54；之后，對(duì)a的引用正確的是a00。在執(zhí)行char str10=“China0”；strlen（str）的結(jié)果是5。在C語言中，引用數(shù)組元素時(shí)，其數(shù)組下標(biāo)的數(shù)據(jù)類型允許是整型常量或整型表達(dá)式。字符串“That”小于字符串“The”。若有說明

11、：inta4=1,2,3,4,5,6,7,8,9,10,11,12；，則數(shù)組第一維的大小為3。若數(shù)組a有m列，則aij之前的數(shù)組元素個(gè)數(shù)為i*m+j。函數(shù)調(diào)用：strcat（strcpy（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ù)通過傳遞一定的信息來使用被調(diào)函數(shù)的功能。（1）無返回值的函數(shù)調(diào)用格式（2）有返回值的函數(shù)調(diào)用格式在調(diào)用一個(gè)函數(shù)之前，應(yīng)考慮

12、哪些問題？若被調(diào)函數(shù)和主調(diào)函數(shù)在一個(gè)編譯單位中，在書寫順序上被調(diào)函數(shù)在主調(diào)函數(shù)之前出現(xiàn)；或者被調(diào)函數(shù)雖然在主調(diào)函數(shù)之后出現(xiàn)，而被調(diào)函數(shù)的數(shù)據(jù)類型是整數(shù)型或字符型，可不對(duì)被調(diào)函數(shù)加以說明。試說明實(shí)參和形參的關(guān)系。形參和實(shí)參的關(guān)系總的來說是一一對(duì)應(yīng)的關(guān)系。具體是：1個(gè)數(shù)相等2順序一致3類型相符（或?qū)崊⒖梢越o形參正確的賦值）。從用戶角度看，函數(shù)分為庫函數(shù)和用戶自定義函數(shù)。若有一下函數(shù)調(diào)用語句：func（a+b，（x，y），fun（n+k，d，（a，b）；在此函數(shù)調(diào)用語句中實(shí)現(xiàn)的個(gè)數(shù)是3。輸入帶空格的字符串時(shí)，應(yīng)該用gets（）函數(shù)。求字符串長(zhǎng)度的函數(shù)是strlen（）。可以用strcpy函數(shù)將字符串

13、復(fù)制到字符數(shù)組中。變量的作用域是指變量的有效范圍，在作用域內(nèi)可以引用該變量。按作用域變量可以分為全局變量和局部變量。從函數(shù)形式看，函數(shù)分為無參函數(shù)和有參函數(shù)。函數(shù)的返回值是通過函數(shù)體中的return語句獲得。若被調(diào)函數(shù)定義為void類型，則被調(diào)函數(shù)不帶回任何值。調(diào)用函數(shù)在被調(diào)用函數(shù)之前時(shí)，一般要對(duì)被調(diào)用函數(shù)做函數(shù)聲明。C語言規(guī)定不能嵌套定義函數(shù)，但可以嵌套調(diào)用函數(shù)。在不同的函數(shù)中定義的變量名若相同，則他們表示不同的變量。C語言總是從主函數(shù)開始執(zhí)行。實(shí)參和形參占用不同的存儲(chǔ)單元。一個(gè)函數(shù)可以沒有形式參數(shù)。在進(jìn)行函數(shù)調(diào)用時(shí)，被調(diào)函數(shù)的形參被分配在內(nèi)存的動(dòng)態(tài)數(shù)據(jù)區(qū)。若函數(shù)類型和return語句中表達(dá)

14、式的值不一致，則以函數(shù)類型為準(zhǔn)。函數(shù)的嵌套調(diào)用是指調(diào)用一個(gè)函數(shù)的過程中，又調(diào)用另一個(gè)函數(shù)。若以數(shù)組元素作為函數(shù)的實(shí)參，則實(shí)參向形參傳送的是數(shù)組元素的值。C語言中，當(dāng)用數(shù)組名做形參時(shí)，形參數(shù)組改變可以使實(shí)參數(shù)組隨之改變。允許函數(shù)遞歸調(diào)用。函數(shù)形參的作用范圍只是局限于所定義的函數(shù)內(nèi)。函數(shù)調(diào)用時(shí)，只能把實(shí)參的值傳送給形參，形參的值不能傳送給實(shí)參。一個(gè)函數(shù)返回值的類型是由定義函數(shù)時(shí)指定的函數(shù)類型決定的。一個(gè)C源程序至少包括一個(gè)函數(shù)，主函數(shù)和其他函數(shù)不可調(diào)用。C語言程序的簡(jiǎn)單語句必須用分號(hào)（；）做為語句的結(jié)束符。函數(shù)定義的形參可以有一個(gè)、多個(gè)，也可以沒有。C語言程序總是從main函數(shù)開始執(zhí)行。C語言是由

15、主函數(shù)和若干子函數(shù)構(gòu)成。在一個(gè)源程序文件中定義的全局變量的有效范圍是從定義變量的位置開始到源程序文件結(jié)束。指針對(duì)指針變量做自加1操作后，一定增加一個(gè)字節(jié)嗎？為什么？不一定，和數(shù)據(jù)的類型有關(guān)。分析“*”在定義指針和引用指針變量時(shí)有什么不同？定義語句中“p”前面的“*”是說明p的類型是指針變量。而除定義語句外的其他語句中出現(xiàn)的“*p”里的“*”是對(duì)p所指變量的引用，即代表它指向的變量。試說明指針變量可以進(jìn)行哪些運(yùn)算。指針變量可以進(jìn)行賦值和簡(jiǎn)單的加減運(yùn)算。指針又可稱為地址。專門的指針運(yùn)算符是&和*。只有先定義一個(gè)指針型變量，才能將另一個(gè)變量的地址存放在改變量中。若指針變量p指向整型變量i，則

16、i變量又可用*p表示。若指針變量p指向float型數(shù)組a10，且a的首地址為1000，則執(zhí)行p+3后，p應(yīng)該指向地址為1012單元。malloc（）函數(shù)用來在內(nèi)存中分配一個(gè)指定長(zhǎng)度的存儲(chǔ)空間。C語言中，若int a5，i，*p=a；，則與&ai等價(jià)的指針表示是p+i，與ai等價(jià)的指針表示是*（p+i）。已知：int a=1,3,5,7,9，*ip=a；表達(dá)式*ip+2的值是5.已定義的一個(gè)指針變量可以存放定義相同類型的內(nèi)存單元的地址。指針變量作為形參時(shí)，實(shí)參也可以是不同類型的指針變量。指針說明時(shí)指定的數(shù)據(jù)類型是指針變量指向的存儲(chǔ)單元的數(shù)據(jù)類型。指針變量賦值時(shí)，賦的值是一般變量而不是地址

17、。指針變量的值是可以改變的。變量的指針是變量存儲(chǔ)單元的地址。指針變量是指存放變量地址的變量。若有定義：int x，*pb；則正確的賦值表達(dá)式是pb=&x。若有定義：char ch；（1）使指針p可以指向變量ch的定義語句是char *p=&ch。（2）使指針p指向變量ch的賦值語句是p=&ch。（3）通過指針p給變量ch讀入字符的scanf函數(shù)調(diào)用語句是scanf（“%c”，p）。（4）通過指針p給變量ch賦字符的語句是ch=*p。（5）通過指針p輸出ch中字符的語句是putchar（*p）。數(shù)據(jù)結(jié)構(gòu)概論通常將數(shù)據(jù)結(jié)構(gòu)表示為一個(gè)二元組（D，R），其中D和R分別表示什么？

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

19、段。算法的時(shí)間復(fù)雜度僅與問題的規(guī)模相關(guān)嗎？不是。算法的時(shí)間復(fù)雜度還與算法中的語句頻度、數(shù)據(jù)的狀態(tài)等因素有關(guān)。數(shù)據(jù)結(jié)構(gòu)是指邏輯結(jié)構(gòu)和物理結(jié)構(gòu)兩種，通常是指邏輯結(jié)構(gòu)。選擇合適的存儲(chǔ)結(jié)構(gòu)，通常考慮的指標(biāo)有邏輯結(jié)構(gòu)和數(shù)據(jù)類型兩個(gè)因素。數(shù)據(jù)結(jié)構(gòu)按節(jié)點(diǎn)間的關(guān)系，可分為4種，分別是集合、線性結(jié)構(gòu)、樹形結(jié)構(gòu)和網(wǎng)狀結(jié)構(gòu)。線性結(jié)構(gòu)反映節(jié)點(diǎn)間的關(guān)系是一對(duì)一的，樹形結(jié)構(gòu)反映節(jié)點(diǎn)間的關(guān)系是一對(duì)多的，網(wǎng)狀結(jié)構(gòu)反映節(jié)點(diǎn)間的關(guān)系是多對(duì)多的。數(shù)據(jù)的邏輯結(jié)構(gòu)是數(shù)據(jù)之間的外在聯(lián)系（與計(jì)算機(jī)存儲(chǔ)無關(guān)）。數(shù)據(jù)的邏輯結(jié)構(gòu)與數(shù)據(jù)元素的相對(duì)位置相關(guān)。數(shù)據(jù)的邏輯結(jié)構(gòu)與其所含數(shù)據(jù)元素的個(gè)數(shù)無關(guān)。數(shù)據(jù)元素之間的邏輯關(guān)系與存儲(chǔ)單元的相鄰關(guān)系無關(guān)。在

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

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

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

23、表中的數(shù)據(jù)元素，則應(yīng)該選擇哪種存儲(chǔ)結(jié)構(gòu)？為什么？應(yīng)該選擇順序存儲(chǔ)結(jié)構(gòu)。因?yàn)榫€性表的長(zhǎng)度基本穩(wěn)定，可以預(yù)先進(jìn)行分配，且要求盡快地存取表中的數(shù)據(jù)元素，而順序表中元素可以隨機(jī)存取。若頻繁地對(duì)線性表進(jìn)行插入與刪除操作，該線性表應(yīng)該采取什么存儲(chǔ)結(jié)構(gòu)？為什么？應(yīng)該選擇鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。對(duì)線性表進(jìn)行插入與刪除操作，順序表需要大量移動(dòng)元素，而鏈表只需要修改需要相應(yīng)的指針域就可以了。有哪些鏈表可僅由一個(gè)尾指針來唯一確定，即從尾指針出發(fā)能訪問到鏈表上任意一個(gè)節(jié)點(diǎn)？循環(huán)單鏈表和循環(huán)雙鏈表。在單鏈表、循環(huán)單鏈表和循環(huán)雙鏈表中，若僅知道指針p指向某節(jié)點(diǎn)，不知道頭指針，能否將節(jié)點(diǎn)*p從相應(yīng)的鏈表中刪除？若可以，且時(shí)間復(fù)雜度各

24、為多少？單鏈表不可以。循環(huán)單鏈表、循環(huán)雙鏈表可以。單鏈表時(shí)間復(fù)雜度O（n），循環(huán)單鏈表時(shí)間復(fù)雜度O（n），循環(huán)雙鏈表時(shí)間復(fù)雜度O（1）。線性表的兩種存儲(chǔ)結(jié)構(gòu)分別為順序表結(jié)構(gòu)和鏈表結(jié)構(gòu)。訪問一個(gè)線性表中具有定值元素的時(shí)間復(fù)雜度為O（n）。對(duì)于一個(gè)為n的順序存儲(chǔ)的線性表，在表頭插入元素的時(shí)間復(fù)雜性為O（n），在表尾插入元素的時(shí)間復(fù)雜性為O（1）。線性表是一個(gè)有限序列，可以為空。一個(gè)線性表是n個(gè)數(shù)據(jù)元素的有限序列。在一個(gè)順序表的表尾插入一個(gè)元素的時(shí)間復(fù)雜度為O（1）。在一個(gè)單鏈表中，若要在p所指向的節(jié)點(diǎn)插入一個(gè)新節(jié)點(diǎn)，則需要相繼修改2個(gè)指針域的值。在一個(gè)單鏈表中，若要在p所指向的節(jié)點(diǎn)插入一個(gè)新節(jié)點(diǎn)，

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

26、中，若一個(gè)元素的下標(biāo)為i，則它的前驅(qū)元素的下標(biāo)為i-1，后繼元素的下標(biāo)為i+1。一個(gè)線性表中，第一個(gè)元素的存儲(chǔ)地址是100，每個(gè)元素的長(zhǎng)度是2，則第五個(gè)元素的地址是108。棧、隊(duì)列和數(shù)組簡(jiǎn)述棧和隊(duì)列的相同點(diǎn)和不同點(diǎn)。相同點(diǎn)：都是存儲(chǔ)數(shù)據(jù)的線性表。不同點(diǎn)： 棧為L(zhǎng)IFO（后進(jìn)線出）線性表，插入、刪除操作均在表尾進(jìn)行。隊(duì)列為FIFO（先進(jìn)先出）線性表，插入在表尾進(jìn)行、刪除在表頭進(jìn)行。若進(jìn)棧的數(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，則此時(shí)

27、棧底元素為最先入棧的1、然后依次向上為2、3、4、4、3出棧后；5入棧，再出棧；6入棧，再出棧；這時(shí)得到序列為4、3、5、6；這時(shí)棧頂元素為2,2出棧后，1才能出棧，所以1不可能先于2出棧，因此不能得到此序列。（2）可以得到1、3、5、4、2、6的出棧列。1入棧，再出棧，1為第一個(gè)出棧元素；2入棧；3入棧，再出棧，3為第二個(gè)出棧元素；4、5一次入棧，此時(shí)，棧底元素為1,5成為棧頂元素，則5出棧，然后4出棧，然后2出棧；之后6入棧，再出棧；因此可以得到此出棧序列。向一個(gè)順序棧加一個(gè)元素時(shí)，首先若棧不滿棧頂指針上移，然后將元素加入到棧頂位置。從一個(gè)順序棧刪除元素時(shí)，首先判斷棧是否為空，然后若不為空

28、棧頂指針下移。一個(gè)順序棧存儲(chǔ)于一維數(shù)組am中，棧頂指針用top表示，當(dāng)棧頂指針等于-1時(shí)，則為空棧；棧頂指針等于m-1時(shí)，則為滿棧。在一個(gè)鏈棧中，若棧頂指針等于NULL則為空棧；在一個(gè)鏈隊(duì)列中，若隊(duì)首指針與隊(duì)尾指針的值相同，則表示該隊(duì)為空隊(duì)列。在具有n個(gè)單元的循環(huán)隊(duì)列中，隊(duì)滿時(shí)共有n-1個(gè)元素。已知二維數(shù)組A1：41:6采用行序?yàn)橹餍蚍绞酱鎯?chǔ)，每個(gè)元素占用三個(gè)存儲(chǔ)單元，并且A2,2的存儲(chǔ)地址為1200，元素A3,4的存儲(chǔ)地址是1224。若將n階三對(duì)角矩陣A按照行序?yàn)橹餍蚍绞綄⑺蟹橇阍卮娣旁谝粋€(gè)一維數(shù)組B中，則該三對(duì)角矩陣在B中共有3n-2個(gè)數(shù)據(jù)元素。隊(duì)列只能在隊(duì)首進(jìn)行刪除，在隊(duì)尾進(jìn)行插入。

29、隊(duì)列屬于數(shù)據(jù)結(jié)構(gòu)中存取受限制的線性結(jié)構(gòu)。鏈棧的所有操作都限制在表頭進(jìn)行，所有沒有必要設(shè)置頭結(jié)點(diǎn)。鏈棧與順序棧相比，通常不會(huì)出現(xiàn)棧滿的情況。順序棧是線性結(jié)構(gòu)，鏈棧也是線性結(jié)構(gòu)。一個(gè)棧的入棧序列是a、b、c、d、e，則棧的不可能的輸出序列是dceab。向順序棧中壓入新元素時(shí)，應(yīng)當(dāng)先移動(dòng)棧頂指針，再存入元素。當(dāng)利用大小為N的數(shù)組順序存儲(chǔ)一個(gè)棧時(shí)，假定用top=N表示?？眨瑒t向這個(gè)棧插入一個(gè)元素時(shí)，首先應(yīng)執(zhí)行top語句修改top指針。假定利用數(shù)組aN順序存儲(chǔ)一個(gè)棧，用top表示棧頂指針，top=-1表示?？?，并已知棧未滿，當(dāng)元素x進(jìn)棧時(shí)所執(zhí)行的操作為a+top=x。假定一個(gè)鏈?zhǔn)綏５臈ｍ斨羔樣胻op表示

30、，每個(gè)節(jié)點(diǎn)的結(jié)構(gòu)為datanext，所進(jìn)行的指針操作為top=top->next。一個(gè)隊(duì)列的入隊(duì)順序是1、2、3、4，則隊(duì)列的輸出順序是1、2、3、4。假定一個(gè)順序隊(duì)列的隊(duì)首和隊(duì)尾指針分別用front和rear表示，則判斷對(duì)空的條件為front=rear。判定一個(gè)循環(huán)隊(duì)列Q（最多元素為m0）為空的條件是Q->front=Q->rear。判定一個(gè)循環(huán)隊(duì)列Q（最多元素為m0）為隊(duì)滿的條件是Q->front=（Q->rear+1）%m。若將n階對(duì)稱矩陣A按照行序?yàn)橹餍蚍绞綄ㄖ鲗?duì)角線在內(nèi)的下三角形的所有元素存放在一個(gè)一維數(shù)組B中，則該對(duì)稱矩陣在B中占用了n（n+1）/

31、2個(gè)數(shù)組元素。判定一個(gè)棧（最多元素為m）為空的條件是ST->top=-1。判定一個(gè)棧ST（最多元素為m）為棧滿的條件是ST->top=m-1。棧結(jié)構(gòu)通常采用的兩種存儲(chǔ)結(jié)構(gòu)是順序線性結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。棧和隊(duì)列的共同點(diǎn)是只允許在端點(diǎn)處插入和刪除元素。在一個(gè)鏈隊(duì)中，假設(shè)f和r分別為隊(duì)首和隊(duì)尾指針，則插入s所指節(jié)點(diǎn)的運(yùn)算是r->next=s；r=s。在一個(gè)鏈隊(duì)中，假設(shè)f和r分別為隊(duì)首和隊(duì)尾指針，則刪除一個(gè)節(jié)點(diǎn)的運(yùn)算是f=f->next。樹和二叉樹指出樹和二叉樹的主要區(qū)別樹無序而二叉樹有序。對(duì)于一顆具有n個(gè)節(jié)點(diǎn)的樹，該樹中所有節(jié)點(diǎn)的度數(shù)之和為n-1。在一棵樹中根節(jié)點(diǎn)沒有前驅(qū)節(jié)點(diǎn)

32、，其余每個(gè)節(jié)點(diǎn)有且僅有一個(gè)直接前驅(qū)節(jié)點(diǎn)，可以有任意多個(gè)直接后繼節(jié)點(diǎn)。在一顆二叉樹中，假定度為2的節(jié)點(diǎn)數(shù)為5個(gè)，度為1的節(jié)點(diǎn)數(shù)為6個(gè)，則葉子節(jié)點(diǎn)數(shù)為6個(gè)。具有40個(gè)節(jié)點(diǎn)的完全二叉樹，它的高度為6。已知8個(gè)數(shù)據(jù)元素為34,76,45,18,26,54，92,65，按照依次插入節(jié)點(diǎn)的方法生成一顆二叉排序樹，則該樹的深度為5。二叉樹的5種基本形態(tài)是空二叉樹、只有根的二叉樹、只有左子樹的二叉樹、只有右子樹的二叉樹、左右子樹都有的二叉樹。若由3、6、8、12、10作為葉子節(jié)點(diǎn)的值生成一顆哈夫曼樹，則該樹的高度為4，帶權(quán)路徑長(zhǎng)度為87。任意一顆有n個(gè)節(jié)點(diǎn)的二叉樹，若它有m個(gè)葉子節(jié)點(diǎn)，則二叉樹上度為1的節(jié)點(diǎn)個(gè)

33、數(shù)為n-2m+1。若一顆二叉樹葉子樹為n，在該二叉樹中，左、右子樹皆非空的節(jié)點(diǎn)個(gè)數(shù)為n-1。由一個(gè)二叉樹的先序和中序或后序和中序遍歷結(jié)果可以唯一地確定一顆二叉樹。二叉樹中，任何一個(gè)節(jié)點(diǎn)的度數(shù)為2。一顆哈夫曼樹中存在度為1的節(jié)點(diǎn)。樹的先根遍歷順序與其對(duì)應(yīng)的二叉樹的先根遍歷序列相同。按二叉樹的定義，具有3個(gè)節(jié)點(diǎn)的二叉樹有5種。已知某二叉樹的后序遍歷序列是dabec，中序遍歷序列是debac，它的前序遍歷序列是cedba。樹中所有節(jié)點(diǎn)的度等于所有節(jié)點(diǎn)個(gè)數(shù)加-1。在一顆度為3的樹中，度為3的節(jié)點(diǎn)數(shù)為2個(gè)，度為2的節(jié)點(diǎn)數(shù)為1個(gè)，度為1 的節(jié)點(diǎn)數(shù)為2個(gè)，則度為0的節(jié)點(diǎn)數(shù)為6個(gè)。已知某二叉樹的后序遍歷序列是

34、DACBE，中序遍歷序列是DEBAC，則它的前序遍歷序列是EDBAC。在一顆二叉樹上第8層的節(jié)點(diǎn)數(shù)最多是128。在深度為5的滿二叉樹中，葉子節(jié)點(diǎn)的個(gè)數(shù)為16。設(shè)一顆完全二叉樹共有500個(gè)節(jié)點(diǎn)，則在該二叉樹中有250個(gè)葉子節(jié)點(diǎn)。若某二叉樹的前序是stuwv，中序是uwtvs，那么后序?yàn)閣uvts。任何一顆二叉樹的葉子節(jié)點(diǎn)在先序、中序和后序遍歷序列中的相對(duì)依次不發(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個(gè)節(jié)

35、點(diǎn)。在一非空二叉樹的中序遍歷序列中，根節(jié)點(diǎn)的右邊只有右子樹上的所有節(jié)點(diǎn)。在一顆具有n個(gè)節(jié)點(diǎn)的二叉樹中，所有節(jié)點(diǎn)的空子樹個(gè)數(shù)等于n+1。某二叉樹的前序序列和后序序列正好相反，則該二叉樹一定是高度等于其節(jié)點(diǎn)數(shù)的二叉樹。在有n個(gè)葉子節(jié)點(diǎn)的哈夫曼樹中，其節(jié)點(diǎn)總數(shù)為2n-1。從概念上講，樹與二叉樹是兩種不同的數(shù)據(jù)結(jié)構(gòu)，將樹轉(zhuǎn)化為二叉樹的基本目的是樹可以采用二叉樹的存儲(chǔ)結(jié)構(gòu)并利用二叉樹的已有算法解決樹的有關(guān)問題。圖一個(gè)帶權(quán)聯(lián)通圖的最小生成樹是否唯一？說明在什么情況下最小生成樹有可能不唯一。一個(gè)帶權(quán)聯(lián)通圖的最小生成樹不一定唯一。若是圖中同時(shí)存在若干個(gè)權(quán)值相同的邊，選擇不同點(diǎn)起點(diǎn)，可得到不同的最小生成樹，但這

36、些最小生成樹邊上權(quán)值之和均為定值。用鄰接矩陣表示圖時(shí)，矩陣元素的個(gè)數(shù)與頂點(diǎn)個(gè)數(shù)是否有關(guān)？與邊的條數(shù)是否有關(guān)？矩陣元素的個(gè)數(shù)與頂點(diǎn)個(gè)數(shù)有關(guān)，頂點(diǎn)個(gè)數(shù)為n，則矩陣元素的個(gè)數(shù)為n*n；矩陣元素的個(gè)數(shù)與邊的條數(shù)無關(guān)。簡(jiǎn)述圖的連通分量和圖的生成樹的區(qū)別。圖的連通分量是這個(gè)圖的最大連通子圖，就是其本身。圖的生成樹是含有該連通圖的全部頂點(diǎn)的有關(guān)極小連通子圖。在一個(gè)圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的2倍。n頂點(diǎn)的無向連通圖至少n-1條邊，至多n（n-1）/2條邊。在利用表示有向圖的鄰接矩陣中，對(duì)第i行的元素進(jìn)行累加，可得到第i個(gè)頂點(diǎn)的出度，而對(duì)第j列元素進(jìn)行累加，可得到第j個(gè)頂點(diǎn)的入度。一個(gè)連通圖的生成樹

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

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

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

40、于順序存儲(chǔ)結(jié)構(gòu)，且是有序。采用順序查找方法查找長(zhǎng)度為n的線性表時(shí)，每個(gè)元素的平均查找長(zhǎng)度為（n+1）/2。二叉排序樹上的查找長(zhǎng)度不僅與節(jié)點(diǎn)個(gè)數(shù)有關(guān)，也與二叉排序樹的樹形有關(guān)。常用的排序方法什么是內(nèi)部排序？什么是外部排序？?jī)?nèi)部排序是指待排序的數(shù)據(jù)量不大，在內(nèi)存中進(jìn)行的排序。外部排序是指待排序的數(shù)據(jù)量較大，內(nèi)存中一次放不下，借助于外存進(jìn)行排序。學(xué)習(xí)過的排序方法中哪些排序方法是穩(wěn)定的？直接插入排序、冒泡排序是穩(wěn)定的。排序的目的是為了對(duì)已排序的數(shù)據(jù)元素進(jìn)行查找運(yùn)算。若對(duì)一組記錄（46、79、56、38、40、80、35、50、74）進(jìn)行直接插入排序，當(dāng)把第8個(gè)記錄插入到前面已排序的有序表時(shí)，為尋找插入位置比較5次。具有24個(gè)記錄的序列，采用冒泡排序最少的比較次數(shù)是23次。在對(duì)n個(gè)元素進(jìn)行直接插入排序的過程中，最多需要進(jìn)行n-1趟。在對(duì)n個(gè)元素進(jìn)行直接冒泡排序的過程中，至少需要n-1趟完成。排序方法中，從未排序序列中挑選元素，并將其依次放入已排序序列的一端的方法，稱為選擇排序。冒泡排序算法在最好的情況下的元素交換次數(shù)為0。在所有排序方法中，關(guān)鍵字比較的次