2010軟考軟件設(shè)計(jì)師考前練習(xí)試題及答案解析(1)

　　84. 在最好和最壞情況下的時(shí)間復(fù)雜度均為O(nlogn)，但不穩(wěn)定的排序算法是 (89) 。

　　(89) A.堆排序

　　B.快速排序

　　C.歸并排序

　　D.基數(shù)排序

　　參考答案：(89)A。

　　解析：堆排序在最好和最壞情況下的時(shí)間復(fù)雜度均為O(nlogn)但不穩(wěn)定�！】焖倥判蜃詈煤妥顗那闆r下的時(shí)間復(fù)雜度分別為O(n2)和O(nlogn)且不穩(wěn)定。

　　歸并排序是在最好和最壞情況下的時(shí)間復(fù)雜度均為O(nlogn)且穩(wěn)定的排序方法。

　　基數(shù)排序在最好和最壞情況下的時(shí)間復(fù)雜度均為O(d(n+rd))。

　　85. 利用動(dòng)態(tài)規(guī)劃方法求解每對(duì)節(jié)點(diǎn)之間的最短路徑問題(all pairs shortest path problem)時(shí)，設(shè)有向圖G=共有n個(gè)節(jié)點(diǎn)，節(jié)點(diǎn)編號(hào)1～n，設(shè)C是G的成本鄰接矩陣，用Dk(I,j)即為圖G 中節(jié)點(diǎn)i到j(luò)并且不經(jīng)過編號(hào)比k還大的節(jié)點(diǎn)的最短路徑的長(zhǎng)度(Dn(i,j)即為圖G中節(jié)點(diǎn)i到j(luò)的最短路徑長(zhǎng)度)，則求解該問題的遞推關(guān)系式為 (90) 。

　　(90) A.Dk(I,j)=Dk-1(I,j)+C(I,j)

　　B.Dk(I,j)=Dk-1(I,k)+Dk-1(k,j)

　　C.Dk(I,j)=min{Dk-1(I,j),Dk-1(I,j)+C(I,j)}

　　D.Dk(I,j)=min{Dk-1(I,j),Dk-1(I,k)+Dk-1(k,j)}

　　參考答案：(90)D。

　　解析：設(shè)Pk(I,j)表示從i到j(luò)并且不經(jīng)過編號(hào)比k還大的節(jié)點(diǎn)的最短路徑，那么Pk(I,j)有以下兩種可能。

　　① Pk(I,j)經(jīng)過編號(hào)為k的節(jié)點(diǎn)，此時(shí)Pk(I,j)可以分為從i到k和從k至j的兩段，易知Pk(I,j)的長(zhǎng)度為Dk-1(I,k)+Dk-1(k,j)。② Pk(I,j)不經(jīng)過編號(hào)為k的節(jié)點(diǎn)，此時(shí)Pk(I,j)的長(zhǎng)度為Dk-1(I,j)。

　　因此，求解該問題的遞推關(guān)系式為：Dk(I,j)=min{Dk-1(I,j),Dk-1(I,k)+Dk-1(k,j)}。

　　86. 通常， (91) 應(yīng)用于保護(hù)被中斷程序現(xiàn)場(chǎng)等場(chǎng)合。

　　(91) A.隊(duì)列

　　B.堆棧

　　C.雙鏈表

　　D.數(shù)組

　　參考答案：(91)B。

　　解析：在計(jì)算機(jī)中，堆棧被定義為一段特殊的內(nèi)存區(qū)。其存取數(shù)據(jù)的特點(diǎn)是先進(jìn)后出(FILO)。這一特點(diǎn)使它最常用于保護(hù)被中斷程序的現(xiàn)場(chǎng)等應(yīng)用場(chǎng)合。

　　87.若有說明語句“inta[10]，*p=a;”，對(duì)數(shù)組元素的正確引用是(92)

　　(92) A. a[p]

　　B. P[a]

　　C. *(P+2)

　　D. P+2

　　參考答案：(91)C�！〗馕觯涸贑語言中，約定數(shù)組名單獨(dú)出現(xiàn)在表達(dá)式中時(shí)，它表示數(shù)組首元素的指針。有inta[10]，則a可以作為&a[0]使用。另有整型指針變量p，代碼p=a實(shí)現(xiàn)p指向數(shù)組a的首元素。則表達(dá)式*(p+2)是引用數(shù)組元素a[2]。表達(dá)式a[p]和p[a]都是不正確的，下標(biāo)必須是整型表達(dá)式，不可以是指針表達(dá)式。表達(dá)式p+2是指針表達(dá)式，它的值是&p[2]。所以只有表達(dá)式*(p+2)引用數(shù)組a的元素a[2]。所以解答是C。

　　88.下面各語句中，能正確進(jìn)行賦字符串操作的語句是(93)

　　(93) A. chars[5]={"ABCDE"};

　　B. chars[5]={’A’,’B’,’C’,’D’,’E’};

　　C. char*s;s="ABCDE";

　　D. char*s;scanf("%"，s);

　　參考答案：(93)C。

　　解析：字符串最終存儲(chǔ)于字符數(shù)組中，存儲(chǔ)字符串的字符數(shù)組可以是程序主動(dòng)引入的(定義或動(dòng)態(tài)分配)，也可以是字符串常量，由系統(tǒng)分配。其中字符數(shù)組用字符串初始化就是字符串存儲(chǔ)于由程序引入的字符數(shù)組的例子。給字符指針賦字符串則是系統(tǒng)自動(dòng)分配字符率存儲(chǔ)空間的例子。給字符指針賦字符串并不是將一個(gè)長(zhǎng)長(zhǎng)的字符串存于字符指針變量中，而是將字符串常量存儲(chǔ)于常量區(qū)，并將存儲(chǔ)這個(gè)字符串的首字節(jié)地址賦給指針變量，讓指針變量指向字符率常量的首字符。對(duì)于以字符串作為字符數(shù)組初值的情況，要求字符數(shù)組足夠的大，能存得下字符串常量。這里有一個(gè)特別的規(guī)定，若數(shù)組的大小少于存儲(chǔ)字符串有效字符的字節(jié)個(gè)數(shù)，系統(tǒng)將報(bào)告錯(cuò)誤;當(dāng)字符數(shù)組的大小只能存儲(chǔ)字符串的有效字符，而不能存儲(chǔ)字符率結(jié)束標(biāo)記符時(shí)，則存儲(chǔ)于字符數(shù)組中的內(nèi)容是字符序列，因沒有存儲(chǔ)字符率結(jié)束標(biāo)記符，存儲(chǔ)的內(nèi)容就不是字符串。如代碼chara[5]="ABCDE"�！×硗�，給字符數(shù)組元素逐一賦字符初值，并在字符初值中沒有字符串結(jié)束標(biāo)記符，則存于字符數(shù)組中的內(nèi)容也不是字符率。如代碼chars[5]={’A’，’B’，’C’，’D’，’E’}。特別要注意當(dāng)字符指針還未指向某個(gè)字符數(shù)組的元素時(shí)，不可以通過字符指針輸入字符串。如代碼char*s;scanf("%s"，s)。若寫成char*str;scanf("%s"，&str)更是錯(cuò)誤的了。

　　由于C語言規(guī)定數(shù)組不能相互賦值，所以只能將字符串常量賦給某字符指針。如代碼char*s;s="ABCDE"是正確的。實(shí)際上，字符率"ABCDE"被存儲(chǔ)于常量區(qū)中，向指針變量賦的是字符指針，讓s指向其中的字符’A’。所以解答是C。