計算機軟考：軟件設計師練習試題及答案解析(6)

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

　　(89) A.堆排序

　　B.快速排序

　　C.歸并排序

　　D.基數排序

　　參考答案：(89)A。

　　解析：堆排序在最好和最壞情況下的時間復雜度均為O(nlogn)但不穩(wěn)定。

　　快速排序最好和最壞情況下的時間復雜度分別為O(n2)和O(nlogn)且不穩(wěn)定。

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

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

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

　　解析：設Pk(I,j)表示從i到j并且不經過編號比k還大的節(jié)點的最短路徑，那么Pk(I,j)有以下兩種可能。

　　① Pk(I,j)經過編號為k的節(jié)點，此時Pk(I,j)可以分為從i到k和從k至j的兩段，易知Pk(I,j)的長度為Dk-1(I,k)+Dk-1(k,j)。

　�、� Pk(I,j)不經過編號為k的節(jié)點，此時Pk(I,j)的長度為Dk-1(I,j)。

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

　　86. 通常， (91) 應用于保護被中斷程序現場等場合。

　　(91) A.隊列

　　B.堆棧

　　C.雙鏈表

　　D.數組

　　參考答案：(91)B。

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

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

　　(92) A. a[p]

　　B. P[a]

　　C. *(P+2)

　　D. P+2

　　參考答案：(91)C。

　　解析：在C語言中，約定數組名單獨出現在表達式中時，它表示數組首元素的指針。有inta[10]，則a可以作為&a[0]使用。另有整型指針變量p，代碼p=a實現p指向數組a的首元素。則表達式*(p+2)是引用數組元素a[2]。表達式a[p]和p[a]都是不正確的，下標必須是整型表達式，不可以是指針表達式。表達式p+2是指針表達式，它的值是&p[2]。所以只有表達式*(p+2)引用數組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。

　　解析：字符串最終存儲于字符數組中，存儲字符串的字符數組可以是程序主動引入的(定義或動態(tài)分配)，也可以是字符串常量，由系統(tǒng)分配。其中字符數組用字符串初始化就是字符串存儲于由程序引入的字符數組的例子。給字符指針賦字符串則是系統(tǒng)自動分配字符率存儲空間的例子。給字符指針賦字符串并不是將一個長長的字符串存于字符指針變量中，而是將字符串常量存儲于常量區(qū)，并將存儲這個字符串的首字節(jié)地址賦給指針變量，讓指針變量指向字符率常量的首字符。對于以字符串作為字符數組初值的情況，要求字符數組足夠的大，能存得下字符串常量。這里有一個特別的規(guī)定，若數組的大小少于存儲字符串有效字符的字節(jié)個數，系統(tǒng)將報告錯誤;當字符數組的大小只能存儲字符串的有效字符，而不能存儲字符率結束標記符時，則存儲于字符數組中的內容是字符序列，因沒有存儲字符率結束標記符，存儲的內容就不是字符串。如代碼chara[5]="ABCDE"。

　　另外，給字符數組元素逐一賦字符初值，并在字符初值中沒有字符串結束標記符，則存于字符數組中的內容也不是字符率。如代碼chars[5]={’A’，’B’，’C’，’D’，’E’}。特別要注意當字符指針還未指向某個字符數組的元素時，不可以通過字符指針輸入字符串。如代碼char*s;scanf("%s"，s)。若寫成char*str;scanf("%s"，&str)更是錯誤的了。

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