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

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

　　(89) A.堆排序

　　B.快速排序

　　C.歸并排序

　　D.基數(shù)排序

　　參考答案：(89)A。

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

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

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

　　85. 利用動態(tài)規(guī)劃方法求解每對節(jié)點之間的最短路徑問題(all pairs shortest path problem)時，設(shè)有向圖G=共有n個節(jié)點，節(jié)點編號1～n，設(shè)C是G的成本鄰接矩陣，用Dk(I,j)即為圖G 中節(jié)點i到j(luò)并且不經(jīng)過編號比k還大的節(jié)點的最短路徑的長度(Dn(i,j)即為圖G中節(jié)點i到j(luò)的最短路徑長度)，則求解該問題的遞推關(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)過編號比k還大的節(jié)點的最短路徑，那么Pk(I,j)有以下兩種可能。

　　① Pk(I,j)經(jīng)過編號為k的節(jié)點，此時Pk(I,j)可以分為從i到k和從k至j的兩段，易知Pk(I,j)的長度為Dk-1(I,k)+Dk-1(k,j)。② Pk(I,j)不經(jīng)過編號為k的節(jié)點，此時Pk(I,j)的長度為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)用于保護被中斷程序現(xiàn)場等場合。

　　(91) A.隊列

　　B.堆棧

　　C.雙鏈表

　　D.數(shù)組

　　參考答案：(91)B。

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

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

　　(92) A. a[p]

　　B. P[a]

　　C. *(P+2)

　　D. P+2

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

　　88.下面各語句中，能正確進行賦字符串操作的語句是(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。

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

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