為幫助廣大軟考中級軟件設(shè)計師考生更好備考，信管網(wǎng)特整理匯總了軟件設(shè)計師部分真題、答案及解析供考生查閱，并提供免費在線模擬答題、歷年真題免費下載等服務(wù)，了解軟件設(shè)計師更多備考信息請關(guān)注信管網(wǎng)。

相關(guān)推薦：

點擊查看/下載：軟件設(shè)計師歷年真題匯總

點擊查看：軟件設(shè)計師在線培訓(xùn)課程 丨 免費試聽課程

免費練習(xí)：軟件設(shè)計師考試題庫(模擬試題、章節(jié)練習(xí)、每日一練)

一、綜合知識

1、以下關(guān)于無向連通圖 G 的敘述中， 不正確的是( ) 。

A.G中任意兩個頂點之間均有邊存在

B.G中任意兩個頂點之間存在路徑

C.從G中任意頂點出發(fā)可遍歷圖中所有頂點

D.G的臨接矩陣是對稱矩陣

信管網(wǎng)參考答案：A

查看解析：m.xiexiliangjiufa.com/st/395464935.html

2、 兩個遞增序列 A 和 B 的長度分別為 m 和 n(m且 m 與 n 接近)， 將二者歸井為一個長度為 m+n 的遞增序列。 當元素關(guān)系為( ) ， 歸并過程中元素的比較次數(shù)最少。

信管網(wǎng)參考答案：A

查看解析：m.xiexiliangjiufa.com/st/395484793.html

3、 求解兩個長度為 n 的序列 X 和 Y 的一個最長公共序列(如序列 ABCBDAB和 BDCABA 的一個最長公共子序列為 BCBA) 可以采用多種計算方法。 如可以采用蠻力法， 對 X 的每一個子序列， 判斷其是否也是 Y 的子序列， 最后求出最長的即可， 該方法的時間復(fù)雜度為(1) 。 經(jīng)分析發(fā)現(xiàn)該問題具有最優(yōu)子序列， 可以定義序列成都分別為 i 和 j 的兩個序列 X 和 Y 的最長公共子序列的成都為 C[I,j]，如下式所示。

采用自底向上的方法實現(xiàn)該算法，則時間復(fù)雜度為(2)。

(1)A. O(n2)

B. O(n2lgn)

C. O(n3)

D. O(n2^)

(2)A. O(n2)

B. O(n2lgn)

C. O(n3)

D. O(n2^)

信管網(wǎng)參考答案：D、A

查看解析：m.xiexiliangjiufa.com/st/3954929299.html

4、現(xiàn)需要對一個基本有序的數(shù)組進行排序。此時最適宜采用的算法為(1)排算法， 時間復(fù)雜度為(2) 。

(1)A. 插入

B. 快速

C. 歸并

D. 堆

(2)A. O(n)

B. O(nlgn)

C. O(n2)

D. O(n2lgn)

信管網(wǎng)參考答案：A、A

查看解析：m.xiexiliangjiufa.com/st/3955120942.html

5、比于 TCP ， UDP 的優(yōu)勢為( ) 。

A. 可靠傳輸

B. 快消較小

C. 擁塞控制

D. 流量控制

信管網(wǎng)參考答案：B

查看解析：m.xiexiliangjiufa.com/st/3955225402.html

二、案例分析：

閱讀下列說明，回答問題1至問題3，將解答填入對應(yīng)欄內(nèi)。

【說明】

快速排序是一種典型的分治算法。采用快速排序?qū)?shù)組a[p..r]排序的3個步驟如下。

1.分解：選擇一個樞軸(pivot)元素劃分數(shù)組。將數(shù)組a[p..r]劃分為兩個子數(shù)組 (可能為空)a[p..q-1]和a[q+1..r]，使得a[q]大于等于a[p..q-1)中的每個元素，小于 a[q+1..r]中的每個元素。q的值在劃分過程中計算。

2.遞歸求解：通過遞歸的調(diào)用快速排序，對子數(shù)組a[p..q-1]和a[q+1..r]分別排序。

3.合并：快速排序在原地排序，故不需合并操作。

【問題1】

下面是快速排序的偽代碼，請?zhí)钛a其中的空缺;偽代碼中的主要變量說明如下。

a：待排序數(shù)組

p，r: 數(shù)組元素下標，從p到r

q: 劃分的位置

x：樞軸元素

i：整型變量，用于描述數(shù)組下標。下標小于或等于i的元素的值小于或等于樞軸元素的值

j：循環(huán)控制變量，表示數(shù)組元素下標

quicksort (a，p，r){

if (p

q=partition(a，p，r) ;

quicksort(a，p，q-1);

quicksort(a，q+1，r);

}

}

partition(a，p，r){

x=a[r];i=p-1;

for(j=p;j≤r-1;j++){

if (a[j]≤x){

i=i+1;

交換a[i]和a[j]

}

}

交 (1) 和 (2) //注：空(1)和空(2)答案可互換，但兩空全部答對方可得分 return (3)

}

【問題2】

(1)假設(shè)要排序包含n個元素的數(shù)組，請給出在各種不同的劃分情況下，快速排序的時間復(fù)雜度，用o記號。最佳情況為 (4) ，平均情況為 (5) ，最壞情況為 (6) 。

(2)假設(shè)要排序的n個元素都具有相同值時，快速排序的運行時間復(fù)雜度屬于哪種情況? (7) 。(最佳，平均、最壞)

【問題3】

(1)待排序數(shù)組是否能被較均勻地劃分對快速排序的性能有重要影響，因此樞軸元素的選取非常重要。有人提出從待排序的數(shù)組元素中隨機地取出一個元素作為樞軸元素，下面是隨機化快速排序劃分的偽代碼——利用原有的快速排序的劃分操作，請?zhí)畛淦渲械目杖碧?。其中，random(i，j)表示隨機取i到j(luò)之間的一個數(shù)，包括i和j。

randomized- partition(a，p，r){

i=random(p，rl);

交換 (8) 和 (9) ;//注：空(8)和空(9)答案可互換，但兩空全部答對方可得分

return partition (a，p，r);

}

(2)隨機化快速排序是否能夠消除最壞情況的發(fā)生? (10) 。(是或否)

查看答案與解析：m.xiexiliangjiufa.com/st/2456720911.html