2009年11月軟件設計師預測題及答案解析五
81. 利用逐點插入建立序列(52,43,73,88,76,18,38,61,45,39)對應的二叉排序樹之后，查找元素61要進行 （86） 次元素間的比較。
（86） A．3
B．4
C．6
D．8
參考答案：（86）A。
解析：利用逐點插入建立二叉排序樹是從空樹開始，通過查找將每個節點作為一個葉子插入。建立序列（50,72,43,85,75,20,35,45,65,30）的二叉排序樹如圖8所示。
 |
根據圖8所示的二叉排序樹可知，查找元素61要進行3次元素間的比較。
82. 為了在狀態空間樹中 （87） ，可以利用LC-檢索（Least Cost Search）快速找到一個答案節點。
（87） A．進行遍歷
B．找出最優的答案節點
C．找出任一個答案節點
D．找出所有的答案節點
參考答案：（87）B。
解析：在狀態空間樹中，定義 為節點的成本函數，g(X)為從節點向X到達一個答案節點所需做的附加工作的估計函數，h(X)為從根節點到節點X的成本，則用成本估計函數 選擇下一個E-節點的檢索策略總是選取 值最小的活節點作為下一個E-節點，因此這種檢索策略稱為最小成本檢索，簡稱LC-檢索（Least Cost Search）。
在狀態空間樹中找出最優的答案節點，就可以利用LC-檢索快速找到一個答案節點。根據定義在進行LC-檢索時，為避免算法過分偏向于做縱深檢查，應該在成本估計函數 中考慮根節點到當前節點的成本（距離）。
83. 圖9中不存在 （88） 。
 |
| 圖9 |
（88） A．歐拉路徑
B．歐拉回路
C．歐密爾頓路徑
D．哈密爾頓回路
參考答案：（88）B。
解析：通過連通圖G中每條邊一次且僅一次，遍歷圖中所有節點的回路稱為歐拉回路。
通過連通圖G中每條邊一次且僅一次，遍歷圖中所有節點的開路稱為歐拉開路（歐拉路徑）。
若G是連通圖，則存在歐拉回路的充要條件是所有節點的度數均為偶數度；存在歐拉開路的充要條件是當且僅當G中有且只有兩個節點的度數為奇數度。
由于圖3-6中有兩個節點的度數是奇數度，因此圖3-6中只存在歐拉路徑，但不符合歐拉回路的充要條件，即不存在歐拉回路。
通過連通圖G中每個節點一次且僅一次的回路稱為歐密爾頓回路。
通過連通圖G中每個節點一次且僅一次的開路稱為歐密爾頓開路（哈密爾頓路徑）。
84. 在最好和最壞情況下的時間復雜度均為O(nlogn)，但不穩定的排序算法是 （89） 。
（89） A．堆排序
B．快速排序
C．歸并排序
D．基數排序
參考答案：（89）A。
解析：堆排序在最好和最壞情況下的時間復雜度均為O(nlogn)但不穩定。
快速排序最好和最壞情況下的時間復雜度分別為O(n2)和O(nlogn)且不穩定。
歸并排序是在最好和最壞情況下的時間復雜度均為O(nlogn)且穩定的排序方法。
基數排序在最好和最壞情況下的時間復雜度均為O(d(n+rd))。
85. 利用動態規劃方法求解每對節點之間的最短路徑問題（all pairs shortest path problem）時，設有向圖G=
（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還大的節點的最短路徑，那么Pk(I,j)有以下兩種可能。
① Pk(I,j)經過編號為k的節點，此時Pk(I,j)可以分為從i到k和從k至j的兩段，易知Pk(I,j)的長度為Dk-1(I,k)+Dk-1(k,j)。
② Pk(I,j)不經過編號為k的節點，此時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。
解析：在計算機中，堆棧被定義為一段特殊的內存區。其存取數據的特點是先進后出（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。
解析：字符串最終存儲于字符數組中，存儲字符串的字符數組可以是程序主動引入的（定義或動態分配），也可以是字符串常量，由系統分配。其中字符數組用字符串初始化就是字符串存儲于由程序引入的字符數組的例子。給字符指針賦字符串則是系統自動分配字符率存儲空間的例子。給字符指針賦字符串并不是將一個長長的字符串存于字符指針變量中，而是將字符串常量存儲于常量區，并將存儲這個字符串的首字節地址賦給指針變量，讓指針變量指向字符率常量的首字符。對于以字符串作為字符數組初值的情況，要求字符數組足夠的大，能存得下字符串常量。這里有一個特別的規定，若數組的大小少于存儲字符串有效字符的字節個數，系統將報告錯誤；當字符數組的大小只能存儲字符串的有效字符，而不能存儲字符率結束標記符時，則存儲于字符數組中的內容是字符序列，因沒有存儲字符率結束標記符，存儲的內容就不是字符串。如代碼chara[5]＝"ABCDE"。
另外，給字符數組元素逐一賦字符初值，并在字符初值中沒有字符串結束標記符，則存于字符數組中的內容也不是字符率。如代碼chars[5]={’A’，’B’，’C’，’D’，’E’}。特別要注意當字符指針還未指向某個字符數組的元素時，不可以通過字符指針輸入字符串。如代碼char*s；scanf("%s"，s)。若寫成char*str；scanf("%s"，&str)更是錯誤的了。
由于C語言規定數組不能相互賦值，所以只能將字符串常量賦給某字符指針。如代碼char*s；s＝"ABCDE"是正確的。實際上，字符率"ABCDE"被存儲于常量區中，向指針變量賦的是字符指針，讓s指向其中的字符’A’。所以解答是C。
89．若有以下定義，則不能表示a數組元素的表達式是（94）
inta[10]＝｛1，2，3，4，5，6，7，8，9，1o},*p＝a；
（94）A.*p
B. a[10]
C. *a
D. a[p-a]
參考答案：（94）B。
解析：上述代碼定義了有10個元素的整型數組。，和定義指針變量p，并讓p指向數組元素a[0]。所以代碼*p是引用a[0]。由于數組a只有10個元素，最后一個元素是a[9]，表達式a[10]是錯誤的。數組名a可以作為a的首元素的指針，表達式*a就是a[0]，是對數組a的首元素a[0]的引用。指針p的值是a，表達式p-a。的值是0，所以a[p－a]就是a[0]。所以解答是B。
90.若有以下定義，則值為3的表達式是（95）
inta[]＝{1，2，3，4，5，6，7，8，9，10}，*p＝a；
（95）A. p＋＝2,*(p++)
B. p＋＝2，*++p
C. p＋＝3，*p++
D. p＋＝2，++*p
參考答案：（95）A。
解析：數組a有10個元素，分別有值1至10，指針變量p指向a[0]，A逗號表達式p＋＝2，*(P++)，先是P＋＝2使P指向a[2]，接著是*(P++)，以當時P所指變量a[2]取內容3為表達式的值，同時使p指向a[3]。B返號表達式p＋＝2，*++p，先是p＋＝2使p指向a[2]，以后是*++p，又使p增1，讓它指向a[3]，并取指針p所指變量a[3]的內容4作為表達式的值。C逗號表達式p＋＝3，*p++，先是p+=3使p指向a[3]，以后是*p++，表達式的值是a[3]為4，而使p指向a[4]。D逗號表達式p＋＝2，++*p，先是p＋＝2，使p指向a[2]，以后是++*p，因當時的*p就是a[2]，++a[2]使a[2]增1，變成4，并以4為表達式的值。所以只有p＋＝2，*(p++)的值是3。所以解答是A。
91. 若二叉樹的先序遍歷序列為ABCEDF，后序遍歷序列為CEBFDA，則其中序遍歷序列為 （96） 。
（96） A．CEFBDA B．CBEAFD C．CEBAFD D．CBEDFA
參考答案：（96）B。
解析：對于二叉樹遍歷序列有一個性質，包含有中序遍歷序列的任意兩個遍歷序列可以唯一確定該二叉樹。那么由題中的先序遍歷序列和后序遍歷序列就可以唯一確定此二叉樹，如圖10所示，再對其進行中序遍歷，中序遍歷序列為CBEAFD。
 |
| 圖10 |
92. 在C++中，使用靜態成員解決同一個類的不同對象之間的數據共享問題。以下關于一個類的靜態成員的敘述中，說法錯誤的是 （97） 。
（97） A．靜態成員變量可被該類的所有方法訪問
B．該類的對象共享其靜態成員變量的值
C．該類的靜態數據成員變量的值不可修改
D．該類的靜態方法只能訪問該類的靜態成員變量
參考答案：（97）D。
解析：靜態成員作為類的一種成員，它被類的所有對象共享，而不是屬于某個對象的。靜態成員可分為靜態成員變量和靜態方法。
靜態成員變量的值可以被更新。只要對靜態成員變量的值更新一次，所有對象的該靜態成員變量值都會被更新。
靜態成員函數可以直接訪問靜態成員，但不能直接訪問非靜態成員。
選項D“該類的靜態方法只能訪問該類的靜態成員變量”的說法不夠準確。
93. 在面向對象軟件開發過程中，采用設計模式 （98） 。
（98） A．以減少設計過程創建的類的個數
B．以保證程序的運行速度達到最優值
C．以復用成功的設計和體系結構
D．以允許在非面向對象程序設計語言中使用面向對象的概念
參考答案：（98）C。
解析：設計模式是對被用來在特定場景下，解決一般設計問題的類和相互通信的對象的描述。通常，一個設計模式有4個基本要素:模式名稱、問題（模式的使用場合）、解決方案和效果。
每一個設計模式系統地命名、解釋和評價了面向對象系統中一個重要的和重復出現的設計。設計模式使人們可以更加簡單方便地復用成功的設計和體系結構；將己證實的技術表述成設計模式，也會使新系統的開發者更加容易理解其設計思路。設計模式可以幫助開發者做出有利于復用的選擇，避免設計時損害系統復用性。
綜合以上分析，本試題的正確答案是選項C。
94. （99） 模式的設計意圖是：定義對象間的一種一對多的依賴關系，當一個對象的狀態發生改變時，所有依賴于它的對象都得到通知并被自動更新。
（99） A．Observer（觀察者）
B．Visitor（訪問者）
C．Interpreter（解釋器）
D．Adapter（適配器）
參考答案：（99）A。
解析：Observer（觀察者）模式的設計意圖是定義對象間的一種一對多的依賴關系，當一個對象的狀態發生改變時，所有依賴于它的對象都得到通知并被自動更新。
Visitor（訪問者）模式的設計意圖是表示一個作用于某對象結構中的各元素的操作。它可在不改變各元素的類的前提下定義作用于這些元素的新操作。
Interpreter（解釋器）模式的設計意圖是給定一個語言，定義它的文法的一種表示，并定義一個解釋器，這個解釋器使用該表示來解釋語言中的句子。
Adapter（適配器）模式是一種類對象結構型模式。通過將一個類的接口轉換成客戶希望的另外一個接口。Adapter模式使原本由于接口不兼容而不能一起工作的那些類可以一起工作。
95. 包（package）是UML的 （100） 。
（100） A．結構事物
B．分組事物
C．行為事物
D．注釋事物
參考答案：（100）B。
解析：UML的結構事物包括①類、②接口、③協作、④用例、⑤主動類、⑥構件和⑦節點等。
包（package）是UML的分組事物。它是一種把元素組織成組的通用機制，是一個構件（component）的抽象化概念。包中可以包含類、接口、構件、節點、協作、用例、圖及其他的包等元素。
UML的行為事物主要包括交互（Interaction）和狀態機（state machine）。其中，交互是協作中的一個消息集合，這些消息被類元角色通過關聯角色交換。當協作在運行時，受類元角色約束的對象，通過受關聯角色約束的連接交換消息實例。可見，作為行為事物，交互是一組對象之間為了完成一項任務（如操作），而進行通信的一系列消息交換的行為。狀態機是一個狀態和轉換的圖，作用是描述類元實例對事件接收的響應。狀態機可以附屬于某個類元（類或用例），還可以附屬于協作和方法。
注解（note）是UML的注釋事物，它是一種附加定義，用于告知被注解對象的性質、特征和用途等。
96．以下程序的輸出結果是（101）
#include
subl(chara，charb){charc；c＝a；a＝b；b=c；}
sub2(char*a，charb){charc；c＝*a；*a＝b；b＝c；}
sub3(char*a，char*b){charc；c＝*a；*a＝*b；*b＝c；}
main()
{chara，b；
a＝’A’；b＝’B’；sub3(&a，&b)；putchar(a);putchar(b);
a＝’A’；b＝’B’；Sub2(&a，b)；putchar(a);rutchar(b)；
a=’A’;b=’B’;sub1(a,b);putchar(a)；putchar(b)；
}
（101）A. BABBAB
B. ABBBBA
C. BABABA
D. BAABBA
參考答案：（101） A。
解析：在上述程序中，函數subl完成兩形參值的交換，這個交換不影響實參變量，這是一個沒有意義的函數。函數sub2將第二個形參的值置入由第一個指針形參所指的變量中，指針形參所指的變量由調用時的實參提供。函數sub3完成將兩個形參所指的變量的值交換。程序調用sub3，使變量a和b的值交換輸出BA；調用subZ，使變量b的值傳送到a，輸出BB；調用subl，變量a和b的值不改變，輸出AB。所以程序輸出BABBAB。正確解答是A。
97. 以下關于TCP/IP協議的敘述中，說法錯誤的是 （102） 。
（102） A．ICMP協議用于控制數據報傳送中的差錯情況
B．RIP協議根據交換的路由信息動態生成路由表
C．FTP協議在客戶/服務器之間建立起兩條連接
D．RARP協議根據IP地址查詢對應的MAC地址
參考答案：（102）D。
解析：在TCP/IP協議族中，網絡層主要有IP協議、ICMP協議、ARP協議和RARP協議等4個協議。其中，利用地址轉換協議（ARP）可根據IP地址查詢對應的MAC地址。而反向地址轉換協議（RARP）則把MAC地址轉換成對應的IP地址。
ICMP協議用于傳送有關通信問題的消息，例如，數據報不能到達目標站、路由器沒有足夠的緩存空間或路由器向發送主機提供最短路徑信息等。ICMP報文封裝在IP數據報中傳送，因而不保證可靠的提交。
FTP協議屬于TCP/IP協議族的應用層協議，利用FTP協議進行文件傳送時，在客戶/服務器之間一般需要建立一條控制連接（使用TCP 21端口）和一條數據連接（使用TCP 20端口）。
98. 以下能隔離ARP病毒的網絡互聯設備是 （103） 。
（103） A．集線器
B．路由器
C．網橋
D．交換機
參考答案：（103）B。
解析：地址解析協議（ARP）是數據鏈路層協議，但同時對上層（網絡層）提供服務，完成將IP地址轉換成以太網的MAC地址的功能。
ARP工作時，送出一個含有所希望的IP地址的以太網廣播數據包。當發出AM請求時，發送方填好發送方首部和發送方IP地址后，還要填寫目標E地址。當目標機器收到這個ARP廣播幀時，就會在響應報文中填上自己的48位主機地址。由此可以看出ARP廣播幀最初是以IP地址的形式來尋址發送的，所以需要工作在網絡層的網絡設備路由器來對其進行隔離。可見路由器能完成“隔離沖突域，隔離播域”的功能。
ARP協議的基本功能就是通過目標設備的IP地址，查詢目標設備的MAC地址，以保證通信的順利進行。如果系統ARP緩存表被修改不停的通知路由器一系列錯誤的內網IP或者干脆偽造一個假的網關進行欺騙的話，網絡就會出現通信中斷現象，這就是典型的ARP病毒攻擊現象。
由于路由器、三層交換機或帶三層交換模塊的網絡設備具有“隔離沖突域，隔離廣播域”的特性，因此這些網絡互聯設備能夠隔離ARP病毒。
集線器屬于物理層的網絡互聯設備，具有“共享沖突域，共享廣播域”的特性。網橋和以太網交換機屬于數據鏈路層的網絡互聯設備，具有“隔離沖突域，共享廣播域”的特性。這些網絡互聯設備都不能完成隔離ARP病毒的功能。
99. 使用IE瀏覽器瀏覽網頁時，出于安全方面的考慮，需要禁止執行Java Script，則可以在IE瀏覽器中設置“ （104） ”。
（104） A．禁用腳本
B．禁用cookie
C．禁用ActiveX控件
D．禁用沒有標記為安全的ActiveX控件
參考答案：（104）A。
解析：使用IE瀏覽器瀏覽網頁時，出于安全方面的考慮，需要禁止執行Java Script，可以在IE中禁用腳本。如果在IE中禁用ActiveX控件或者是禁用沒有標記為安全的ActiveX控件，則只能起到禁用控件的功能，而禁用cookie是禁止網站放置臨時存儲信息的cookie，并不能夠禁止執行Java Script腳本程序。
100. 以下網絡地址中，屬于私網地址（Private Address）的是 （105） 。
（105） A．172.15.22.5
B．118.168.22.5
C．172.31.22.5
D．192.158.22.5
參考答案：（105）C。
解析：Private Address是指私網地址，其主要的幾種地址類型及其相關功能見表5。
表5 私網地址類型及其功能表
|
類 型 |
功 能 |
備 注 |
|
① 0.0.0.0 |
表示所有在本機的路由表里沒有特定條目指明如何到達的主機IP和目的網絡地址的集合 |
如果用戶在網絡設置中配置了默認網關，那么Windows系統會自動產生一個目的地址為0.0.0.0的默認路由 |
|
② 255.255.255.255 |
限制廣播地址，是一個不能被路由器轉發的地址 |
用于指向同一廣播域內的所有IP設備 |
|
③ 127.0.0.1 |
本機環回測試地址，主要用于測試 |
在Windows系統中，這個地址有一個別名“Localhost” |
|
④ 224.0.0.1 |
組播地址224.0.0.1特指所有主機；組播地址224.0.0.2特指所有路由器 |
如果用戶的主機開啟了IRDP（Internet路由發現協議）功能，那么用戶的主機路由表中將出現這類IP地址 |
|
⑤ 169.254.x.x |
DHCP網段地址 |
如果用戶的主機啟用了DHCP功能以自動獲得一個IP地址，當用戶的DHCP服務器發生故障，或響應時間超出了一個系統規定的時間時，那么Windows系統會為用戶分配這個網段中的某個IP地址 |
|
⑥ 10.x.x.x、172.16.x. x~ 172.31.x.x、192.168.x.x |
這些私有地址被用于內部局域網的IP地址分配 |
這類地址將不會出現在Internet網中。另外，一些寬帶路由器常使用192.168.1.1作為其默認IP地址 |
本試題中，選項A的地址“172.15.22.5”是一個B類的公網IP地址；選項B的地址“118.168.22.5”是一個A類的公網IP地址；選項D的地址“192.158.22.5”是一個C類的公網IP地址。而選項C的地址“172.31.22.5”恰好是“172.31.0.0/24”網段的一個IP地址，因此，它是一個B類的私網IP地址。
【編輯推薦】
