2023年下半年軟件設計師真題 答案解析(上午選擇 下午案例)全國計算機軟考

2023年下半年軟件設計師真題+答案解析（上午

選擇+下午案例完整版）

1、在程序運行過程中，CPU須要將指令從內存中取出并加以分析和執(zhí)行。CPU

依據(jù)（）來區(qū)分在內存中以二進制編碼形式存放的指令和數(shù)據(jù)。

A.指令周期的不同階段

B.指令和數(shù)據(jù)的尋址方式

C.指令操作碼的譯碼結果

D.指令和數(shù)據(jù)所在的存儲單元

答案：A

指令和數(shù)據(jù)是都存儲在內存中，傳統(tǒng)計算機CPU在執(zhí)行過程中依據(jù)指令周期的

不同階段來區(qū)分是指令還是數(shù)據(jù)，取指周期取出的是指令，執(zhí)行周期取出的是數(shù)

據(jù)。

2、計算機在一個指令周期的過程中，為從內存讀取指令操作碼，首先要將（）

的內容送到地址總線上。

A,指令寄存器（IR）

B.通用寄存器（GR）

C.程序計數(shù)器（PC）

D.狀態(tài)寄存器（PSW）

答案：C

PC（程序計數(shù)器）是用于存放下一條指令所在單元的地址。當執(zhí)行一條指令時，

處理器首先須要從PC中取出指令在內存中的地址，通過地址總線尋址獲得。

3、設16位浮點數(shù)，其中階符1位、階碼值6位、數(shù)符1位、尾數(shù)8位。若階碼

用移碼表示，尾數(shù)用補碼表示，則該浮點數(shù)所能表示的數(shù)值范圍是（）。

A.-264(1-2-8)264

B.-263~(1-2-8)263

C.-264?(1-2-(1-2-8)264?(1-2-8)264

D.-(1-2-8)263?(1-2-8)263

答案：B

詞如浮點數(shù)的階碼（包括1位階符）用R位的移碼表示，尾數(shù)（包括1位數(shù)符）用M

位的補碼表示，則浮點數(shù)表示的數(shù)值范圍如下。

4、已知數(shù)據(jù)信息為16位，最少應附加（）位校驗位，以實現(xiàn)海明碼糾錯。

A.3

B.4

C.5

D.6

答案：C

嘉明碼的構造方法是：在數(shù)據(jù)位之間插入k個校驗位，通過擴大碼距來實現(xiàn)檢

錯和糾錯。設數(shù)據(jù)位是n位，校驗位是k位，則n和k的必需滿意以下的關系。

2K-12n+k

數(shù)據(jù)為16位時，至少須要5位校驗位。

25-1216+5

5、將一條指令的執(zhí)行過程分解為取址、分析和執(zhí)行三步，依據(jù)流水方式執(zhí)行，

若取指時間t取址=4△t、分析時間t分析=24t、執(zhí)行時間t執(zhí)行=3^t,則執(zhí)行

完100條指令，須要的時間為（）

A.200

B.300

C.400

D.405

答案：D

第一條指令執(zhí)行時間+（指令數(shù)』）*各指令段執(zhí)行時間中最大的執(zhí)行時間。

4At+3At+2At+（100-1）X4At=405At

6、以下關于Cache與主存間地址映射的敘述中，正確的是（）。

A.操作系統(tǒng)負責管理Cache與主存之間的地址映射

B.程序員須要通過編程來處理Cache與主存之間的地址映射

C.應用軟件對Cache與主存之間的地址映射進行調度

D.由硬件自動完成Cache與主存之間的地址映射

答案：D

在程序的執(zhí)行過程中，Cache與主存的地址映射是由硬件自動完成的

7、可用于數(shù)字簽名的算法是（）。

A.RSA

B.IDEA

C.RC4

D.MD5

答案：A

IDEA算法和RC4算法都對稱加密算法，只能用來進行數(shù)據(jù)加密。MD5算法是消

息摘要算法，只能用來生成消息摘要無法進行數(shù)字簽名。

RSA算法是典型的非對稱加密算法，主要具有數(shù)字簽名和驗簽的功能。

8、（）不是數(shù)字簽名的作用。

A.接收者可驗證消息來源的真實性

B.發(fā)送者無法否認發(fā)送過該消息

C.接收者無法偽造或篡改消息

D.可驗證接收者合法性

答案：D

數(shù)字簽名是信息的發(fā)送者才能產生的別人無法偽造的一段數(shù)字串，這段數(shù)字串

同時也是對信息的發(fā)送者發(fā)送信息真實性的一個有效證明。不能驗證接收者的合

法性。

9、在網絡設計和實施過程中要實行多種平安措施，其中()是針對系統(tǒng)平安需

求的措施。

A.設備防雷擊

B.入侵檢測

C.漏洞發(fā)覺與補丁管理

D.流量限制

答案：C

10、()的愛護期限是可以延長的。

A.專利權

B.商標權

C.著作權

D.商業(yè)隱私權

答案：B

依藉《中華人民共和國商標法》第三十八條：注冊商標有效期滿，須要接著運

用的，應當在期滿前六個月內申請續(xù)展注冊。專利權和著作權到期后都無法延長,

而商業(yè)隱私權無期限限制。

11、甲公司軟件設計師完成了一項涉及計算機程序的獨創(chuàng)。之后，乙公司軟件設

計師也完成了與甲公司軟件設計師相同的涉及計算機程序的獨創(chuàng)。甲、乙公司于

同一天向專利局申請獨創(chuàng)專利。此情形下，（）是專利權申請人。

A.甲公司

B.甲、乙兩公司

C.乙公司

D.由甲、乙公司協(xié)商確定的公司

答案：D

專利審查指南的規(guī)定：

在審查過程中，對于不同的申請人同日（指申請日，有優(yōu)先權的指優(yōu)先權日）就

同樣的獨創(chuàng)創(chuàng)建分別提出專利申請，并且這兩件申請符合授予專利權的其他條件

的，應當依據(jù)專利法實施細則第四十一條第一款的規(guī)定，通知申請人自行協(xié)商確

定申請人。

12、甲、乙兩廠生產的產品類似，且產品都運用"B"商標。兩廠于同一天向商標

局申請商標注冊，且申請注冊前兩廠均未運用"B"商標。此情形下，（）能核

準注冊。

A.甲廠

B.由甲、乙廠抽簽確定的廠

C.乙廠

D.甲、乙兩廠

答案：B

依據(jù)商標法的規(guī)定，第29條，以及實施條例19條規(guī)定，同一天申請的，初步

審定并公告運用在先的。駁回其他人的申請。均未運用獲無法證明的，各自協(xié)商,

不愿協(xié)商或者協(xié)商不成的，抽簽確定，不抽簽的，視為放棄。

13、在FM方式的數(shù)字音樂合成器中，變更數(shù)字載波頻率可以變更樂音的（13）,

變更它的信號幅度可以變更樂音的（14）o

A.音調

B.音色

日問

D.音質

答案：A

14、在FM方式的數(shù)字音樂合成器中，變更數(shù)字載波頻率可以變更樂音的（13）,

變更它的信號幅度可以變更樂音的（14）o

A.音調

B.音域

C.音高

D.帶寬

答案：C

15、結構化開發(fā)方法中，（）主要包含對數(shù)據(jù)結構和算法的設計。

A.體系結構設計

B.數(shù)據(jù)設計

C.接口設計

D.過程設計

答案：D

16、在靈敏過程的開發(fā)方法中，（）運用了迭代的方法，其中，把每段時間（30

天）一次的迭代稱為一個“沖刺”，并按需求的優(yōu)先級別來實現(xiàn)產品，多個自組

織和自治的小組并行地遞增實現(xiàn)產品。

A.極限編程XP

B.水晶法

C.并列爭球法

D.自適應軟件開發(fā)

答案：C

極限編程（xp）：由價值觀、原則、實踐和行為四個部分組成。

水晶法：每一個不同的項目都須要一套不同的策略、約定和方法論。

并列爭球法：運用了迭代的方法，其中，把每段時間（30天）一次的迭代稱為

一個“沖刺”，并按需求的優(yōu)先級別來實現(xiàn)產品，多個自組織和自治的小組并行

地遞增實現(xiàn)產品。

17、某軟件項目的活動圖如下圖所示，其中頂點表示項目里程碑，連接頂點的

邊表示包含的活動，邊上的數(shù)字表示相應活動的持續(xù)時間（天），則完成該項目

的最少時間為（17）天?；顒覤C和BF最多可以晚起先（18）天而不會影響整個

項目的進度。

A.11

B.15

C.16

D.18

答案：D

18、A.0和7

B.0和11

C.2和7

D.2和11

答案：A

19、成本估算時，（）方法以規(guī)模作為成本的主要因素，考慮多個成本驅動因

子。該方法包括三個階段性模型，即應用組裝模型、早期設計階段模型和體系結

構階段模型。

A.專家估算

B.Wolverton

C.COCOM0

D.COCOMOII

答案：D

20、邏輯表達式求值時常采納短路計算方式?！?&"、"||"、“！”分別表示

邏輯與、或、非運算，“&&”、“||”為左結合，“！”為右結合，優(yōu)先級從

高到低為“！"、“&&”、“||”。對邏輯表達式“x&&（yll!z）”進行短路

計算方式求值時，（）。

A.x為真，則整個表達式的值即為真，不須要計算y和z的值

B.x為假，則整個表達式的值即為假，不須要計算y和z的值

C.x為真，再依據(jù)z的值確定是否須要計算y的值

D.x為假，再依據(jù)y的值確定是否須要計算z的值

答案：B

%:行邏輯與“&&”運算時，只有當兩個操作數(shù)的值為真，最終的結果才會為

真。因此一旦X的值為假，整個運算表達式的值則為假。

21、常用的函數(shù)參數(shù)傳遞方式有傳值與傳引用兩種。（）。

A.在傳值方式下，形參加實參之間相互傳值

B.在傳值方式下，實參不能是變量

C.在傳引用方式下，修改形參實質上變更了實參的值。

D.在傳引用方式下，實參可以是隨意的變量和表達式。

答案：C

傳值調用最顯著的特征就是被調用的函數(shù)內部對形參的修改不影響實參的值。

引用調用是將實參的地址傳遞給形參，使得形參的地址就是實參的地址。

22、二維數(shù)組a[l..N,1..N]可以按行存儲或按列存儲。對于數(shù)組元素a[i,j]

（l<=i,j<=N）,當（）時，在按行和按列兩種存儲方式下，其偏移量相同。

A.iWj

B.i=j

C.i>j

D.i<j

答案：B

23、實時操作系統(tǒng)主要用于有實時要求的過程限制等領域。實時系統(tǒng)對于來自外

部的事務必需在（）。

A.一個時間片內進行處理

B.一個周轉時間內進行處理

C.一個機器周期內進行處理

D.被控對象規(guī)定的時間內做出剛好響應并對其進行處理

答案：D

實時操作系統(tǒng)是保證在肯定時間限制內完成特定功能的操作系統(tǒng)。實時操作系

統(tǒng)有硬實時和軟實時之分，硬實時要求在規(guī)定的時間內必需完成操作，這是在操

作系統(tǒng)設計時保證的；軟實時則只要依據(jù)任務的優(yōu)先級，盡可能快地完成操作即

可。

24、假設某計算機系統(tǒng)中只有一個CPU、一臺輸入設備和一臺輸出設備，若系統(tǒng)

中有四個作業(yè)Tl、T2、T3和T4,系統(tǒng)采納優(yōu)先級調度，且T1的優(yōu)先級〉T2的優(yōu)

先級〉T3的優(yōu)先級打4的優(yōu)先級。每個作業(yè)Ti具有三個程序段：輸入「、計算Ci

和輸出Pi(i=l,2,3,4),其執(zhí)行依次為Ci-Pi。這四個作業(yè)各程序段并發(fā)

執(zhí)行的前驅圖如下所示。圖中①、②分別為(24),③、④、⑤分別為(25)o

A.12、P2

B.12、C2

C.Cl、P2

D.Cl、P3

答案：C

25、A.C2、C4、P4

B.12、13、C4

C.13、P3、P4

D.13、C4、P4

答案：D

題目告知我們一共有3個設備，分別是一個CPU、一臺輸入設備和一臺輸出設備,

其實輸入設備對應程序段輸入li，而CPU對應程序段計算Ci,輸出設備對應程序

段輸出Pi。而每個作業(yè)都分為這三段，各段間有個依次關系。再結合圖中已經給

出的結點，我們不難發(fā)覺，第一行是輸入，其次行是計算，而第三行的結點數(shù)輸

出結點。因此可以知道①、②分別為Cl、P3,③、④、⑤分別為13、C4、P4o

26、假設段頁式存儲管理系統(tǒng)中的地址結構如下圖所示，則系統(tǒng)（）。

A.最多可有256個段，每個段的大小均為2048個頁，頁的大小為8K

B.最多可有256個段，每個段最大允許有2048個頁，頁的大小為8K

C.最多可有512個段，每個段的大小均為1024個頁，頁的大小為4K

D.最多可有512個段，每個段最大允許有1024個頁，頁的大小為4K

答案：B

頁內地址為13位，頁號地址為11位，段號地址為8位。依據(jù)公式，可以分別

計算段號，頁號以及頁內地址最大的尋址空間。存儲管理系統(tǒng)中的地址長度均表

示為最大的尋址空間。

27、假設系統(tǒng)中有n個進程共享3臺掃描儀，并采納PV操作實現(xiàn)進程同步與互

斥。若系統(tǒng)信號量S的當前值為-1,進程Pl、P2又分別執(zhí)行了1次P（S）操作,

那么信號量S的值應為（）。

A.3

B.-3

C.1

D.-1

答案：B

當有進程運行時，其他進程訪問信號量，信號量就會減1。S=-l-2o

28、某字長為32位的計算機的文件管理系統(tǒng)采納位示圖（bitmap）記錄磁盤的

運用狀況。若磁盤的容量為300GB,物理塊的大小為1MB,那么位示圖的大小為

（）個字。

A.1200

B.3200

C.6400

D.9600

答案：D

磁盤的容量為300GB,物理塊的大小為1MB,則磁盤共300X1024/1個物理塊,

位示圖的大小為300X1024/（32）=9600個字。

29、某開發(fā)小組欲為一公司開發(fā)一個產品限制軟件，監(jiān)控產品的生產和銷售過程,

從購買各種材料起先，到產品的加工和銷售進行全程跟蹤。購買材料的流程、產

品的加工過程以及銷售過程可能會發(fā)生變更。該軟件的開發(fā)最不相宜采納（29）

模型，主要是因為這種模型（30）o

A.瀑布

B.原型

C.增量

D.噴泉

答案：A

30、某開發(fā)小組欲為一公司開發(fā)一個產品限制軟件，監(jiān)控產品的生產和銷售過程,

從購買各種材料起先，到產品的加工和銷售進行全程跟蹤。購買材料的流程、產

品的加工過程以及銷售過程可能會發(fā)生變更。該軟件的開發(fā)最不相宜采納（29）

模型，主要是因為這種模型（30）。

A.不能解決風險

B.不能快速提交軟件

C.難以適應變更的需求

D.不能理解用戶的需求

答案：C

對于較大型軟件系統(tǒng)的需求往往難以在前期確定，所以瀑布模型最不適合。

對于較大型軟件系統(tǒng)的需求往往難以在前期確定，所以瀑布模型最不適合。

31、()不屬于軟件質量特性中的可移植性。

A.適應性

B.易安裝性

C.易替換性

D.易理解性

答案：D

可移植性包含：適應性、易安裝性、共存性和易替換性四個特性。

32、對下圖所示流程圖采納白盒測試方法進行測試，若要滿意路徑覆蓋，則至少

須要(32)個測試用例。采納McCabe度量法計算該程序的環(huán)路困難性為(33)。

A.3

B.4

C.6

D.8

答案：C

33、A.1

B.2

C.3

D.4

答案：D

環(huán)形困難度V(G)=E-N+2,其中，E是流圖中邊的條數(shù)，N是結點數(shù)。

V(G)=E-N+2=10-8+2=4o

34、計算機系統(tǒng)的()可以用MTBF/(1+MTBF)來度量，其中MTBF為平均失

效間隔時間。

A.牢靠性

B.可用性

C.可維護性

D.健壯性

答案：A

35、以下關于軟件測試的敘述中，不正確的是()。

A.在設計測試用例時應考慮輸入數(shù)據(jù)和預期輸出結果

B,軟件測試的目的是證明軟件的正確性

C.在設計測試用例時，應當包括合理的輸入條件

D.在設計測試用例時，應當包括不合理的輸入條件

答案：B

軟腦測試的目的在于希望以最少的人力和時間發(fā)覺潛在的各種錯誤和缺陷。

36、某模塊中有兩個處理A和B,分別對數(shù)據(jù)結構X寫數(shù)據(jù)和讀數(shù)據(jù)，則該模塊

的內聚類型為（）內聚。

A.邏輯

B.過程

C.通信

D.內容

答案：C

假如一個模塊的全部成分都操作同一數(shù)據(jù)集或生成同一數(shù)據(jù)集，則稱為通信內

聚。

內聚有一下幾種：

功能內聚：完成一個單一功能，各個部分協(xié)同工作，缺一不行。

依次內聚：處理元素相關，而且必需依次執(zhí)行。

通信內聚：全部處理元素集中在一個數(shù)據(jù)結構的區(qū)域上。

過程內聚：處理元素相關，而且必需按特定的次序執(zhí)行。

瞬時內聚：所包含的任務必需在同一時間間隔內執(zhí)行（如初始化模塊）。

邏輯內聚：完成邏輯上相關的一組任務。

偶然內聚：完成一組沒有關系或松散關系的任務。

37、在面對對象方法中，不同對象收到同一消息可以產生完全不同的結果，這一

現(xiàn)象稱為（）。在運用時，用戶可以發(fā)送一個通用的消息，而實現(xiàn)的細微環(huán)節(jié)

則由接收對象自行確定。

A.接口

B.繼承

C.覆蓋

D.多態(tài)

答案：D

本題考察面對對象多態(tài)的概念。

多態(tài)實質上是將子類的指針對象或者引用對象傳遞給父類指針對象后，通過這個

父類指針對象調用的函數(shù)（此函數(shù)在父類中聲明為虛函數(shù)，且在各個子類中重寫

這個函數(shù)），不是父類中定義的，而是傳遞進來的子類對象中重寫的函數(shù)。

38、在面對對象方法中，支持多態(tài)的是（）。

A.靜態(tài)安排

B.動態(tài)安排

C.靜態(tài)類型

D.動態(tài)綁定

答案：D

動態(tài)綁定是實現(xiàn)多態(tài)的基礎。

39、面對對象分析的目的是為了獲得對應用問題的理解，其主要活動不包括（）。

A.認定并組織對象

B.描述對象間的相互作用

C.面對對象程序設計

D.確定基于對象的操作

答案：C

面對對象分析的任務是了解問題域所涉及的對象、對象間的關系和操作，然后

構造問題的對象模型。

40、如下所示的UML狀態(tài)圖中，（）時，不肯定會離開狀態(tài)B。

A.狀態(tài)B中的兩個結束狀態(tài)均達到

B.在當前狀態(tài)為B2時，事務e2發(fā)生

C.事務e2發(fā)生

D.事務el發(fā)生

答案：C

當e2發(fā)生時，假如當前狀態(tài)是B2,則會離開B；假如當前狀態(tài)不是B2,則不

會離開0

41、以下關于UML狀態(tài)圖中轉換(transition)的敘述中，不正確的是()。

A.活動可以在轉換時執(zhí)行也可以在狀態(tài)內執(zhí)行

B.監(jiān)護條件只有在相應的事務發(fā)生時才進行檢查

C.一個轉換可以有事務觸發(fā)器、監(jiān)護條件和一個狀態(tài)

D.事務觸發(fā)轉換

答案：C

轉換的五要素：

源狀態(tài)：即受轉換影響的狀態(tài)

目標狀態(tài)：當轉換完成后對象的狀態(tài)

觸發(fā)事務：用來為轉換定義一個事務，包括調用、變更、信號、時間四類事務

監(jiān)護條件：布爾表達式，確定是否激活轉換、

動作：轉換激活時的操作

42、下圖①②③④所示是UML(42)o現(xiàn)有場景：一名醫(yī)生(Doctor)可以治療

多位病人(Patient),一位病人可以由多名醫(yī)生治療，一名醫(yī)生可能多次治療同

一位病人。要記錄哪名醫(yī)生治療哪位病人時，須要存儲治療(Treatment)的日

期和時間。以下①②③④圖中(43)o是描述此場景的模型。

A.用例圖

B.對象圖

C.類圖

D.協(xié)作圖

答案：C

類圖描述的是類與類之間的關系

對象圖描述的是某個詳細的對象。

本圖描述的是類與類之間的關系。

43、

A.①

B.②

C.③

D.④

答案：c

44、(44)模式定義一系列的算法，把它們一個個封裝起來，并且使它們可以

相互替換，使得算法可以獨立于運用它們的客戶而變更。以下(45)狀況適合選

用該模式。

①一個客戶須要運用一組相關對象

②一個對象的變更須要變更其它對象

③須要運用一個算法的不同變體

④很多相關的類僅僅是行為有異

A.吩咐（Command）

B.責任鏈（ChainofResponsibility）

C.視察者（Observer）

D.策略（Strategy）

答案：D

45、A.①②

B.②③

C.③④

D.①④

答案：c

策.模式定義了一系列的算法，并將每一個算法封裝起來，而且使它們還可以

相互替換。策略模式讓算法獨立于運用它的客戶而獨立變更。

應用場景：

1、多個類只區(qū)分在表現(xiàn)行為不同，可以運用Strategy模式，在運行時動態(tài)選擇

詳細要執(zhí)行的行為。

2、須要在不同狀況下運用不同的策略(算法)，或者策略還可能在將來用其它方

式來實現(xiàn)。

3、對客戶隱藏詳細策略(算法)的實現(xiàn)細微環(huán)節(jié)，彼此完全獨立。

46、(46)模式將一個困難對象的構建與其表示分別，使得同樣的構建過程可以

創(chuàng)建不同的表示。以下(47)狀況適合選用該模式。

①抽象困難對象的構建步驟

②基于構建過程的詳細實現(xiàn)構建困難對象的不同表示

③一個類僅有一個實例

④一個類的實例只能有幾個不同狀態(tài)組合中的一種

A.生成器(Builder)

B.工廠方法(FactoryMethod)

C.原型(Prototype)

D.單例(Singleton)

答案：A

47、A.①②

B.②③

C.③④

D.①④

答案：

與成器模A式將一個困難對象的構建與它的表示分別，使得同樣的構建過程可以

創(chuàng)建不同的表示。

好用范圍

1當創(chuàng)建困難對象的算法應當獨立于該對象的組成部分以及它們的裝配方式時。

2當構造過程必需允許被構造的對象有不同表示時。

48、由字符a、b構成的字符串中，若每個a后至少跟一個b,則該字符串集合

可用正規(guī)式表示為（）。

A.(b|ab)*

B.(ab*)*

C.(a*b*)*

D.(a|b)*

答案：A

規(guī)式(aIb)*表示字符a和b組成的任何長度的字符串(a和b的位置隨意)。a*|

b*表示由若干個a組成的字符串，或者是由若干個b組成的任何長度的字符串。

a*b*薩表示由若干個a后跟若干個b所組成的任何長度的字符串(a在b前面)。

(ab)*表示每個ab所組成的任何長度的字符串(ab不能分別)。(a*b*)*表示由字符

a和b組成的任何長度的字符串(若干個a后面跟若干個b,b后面再跟若干個a)o

只有(a*b*)*與(aIb)*含義相同，因此正規(guī)式(aIb)*與(a*b*)*是等價的。

49、喬姆斯基(Chomsky)將文法分為4種類型，程序設計語言的大多數(shù)語法現(xiàn)

象可用其中的()描述。

A.上下文有關文法

B.上下文無關文法

C.正規(guī)文法

D.短語結構文法

答案：B

上下文無關文法：形式語言理論中一種重要的變換文法，用來描述上下文無關

語言，在喬姆斯基分層中稱為2型文法。由于程序設計語言的語法基本上都是上

下文無關文法，因此應用非常廣泛。

50、運行下面的C程序代碼段，會出現(xiàn)()錯誤。

intk=0;

for(;k<100;);

{k++；}

A.變量未定義

B.靜態(tài)語義

C.語法

D.動態(tài)語義

答案：D

在本題中，for語句后有“;”號，說明該循環(huán)語句的語句體為空，此時，循環(huán)

會是一個死循環(huán)，所以存在語義錯誤

51、在數(shù)據(jù)庫系統(tǒng)中，一般由DBA運用DBMS供應的授權功能為不同用戶授權,

其主要目的是為了保證數(shù)據(jù)庫的()。

A.正確性

B.平安性

C.一樣性

D.完整性

答案：B

DBMS是數(shù)據(jù)庫管理系統(tǒng)，主要用來保證數(shù)據(jù)庫的平安性和完整性。而DBA通

過授權功能為不同用戶授權，主要的目的是為了保證數(shù)據(jù)的平安性。

52、給定關系模式R(U,F),其中：U為關系模式R中的屬性集，F(xiàn)是U上的一

組函數(shù)依靠。假設U={A1,A2,A3,A4},F={A1-A2,A1A2—A3,Al-A4,A2

-A4},那么關系R的主鍵應為(52)o函數(shù)依靠集F中的(53)是冗余的。

A.A1

B.A1A2

C.A1A3

D.A1A2A3

答案：A

53、A.A1—A2

B.A1A2fA3

C.Al—A4

D.A2fA4

答案：C

本題中U1={A1、A2、A3、A4},構造出依靠關系圖之后，Al是入度為0的結點,

且從A1動身能遍歷全圖，因此A1為主鍵。

A1-A2,A2fA4利用傳遞率：A1-A4,因止匕A1-A4是冗余。

54、給定關系R(A,B,C,D)和關系S(A,C,E,F),對其進行自

然連接運算R?S后的屬性列為(54)個；與。R.B>S.E(R?S)等價的關系代數(shù)表達式

為(55)o

A.4

B.5

C.6

D.8

答案：C

55、A.*7(RXS)

B.n1.2,3,4,7,8（01=5A2>7A3=6（RXS））

CO2>’7'（RXS）

D.nl,2,3,4,7,8（Ol=5A2>'7'A3=6（RXS））

答案：B

關系R(A,B,C,D)和S(A,C,E,F)做自然連接時，會以兩個關系公共字段做等值

連接，然后將操作結果集中重復列去除，所以運算后屬性列有6個

56、下列查詢B=“大數(shù)據(jù)”且F=“開發(fā)平臺”，結果集屬性列為A、B、C、F

的關系代數(shù)表達式中，查詢效率最高的是()。

A.n1,2,3,8（。2='大數(shù)據(jù)'八1=57=6A8='開發(fā)平臺'（RXS））

B.Ji1,2,3,8(。1=5"3=6八8=,開發(fā)平臺，(。2='大數(shù)據(jù)，(口)XS))

C.五1,2,3,8(。2='大數(shù)據(jù)'A1=5A3=6(RX。4='開發(fā)平臺，(S))

D.n1,2,3,8(o1=5A3=6(。2='大數(shù)據(jù)，(R)X。4='開發(fā)平臺'(S)))

答案：D

57、拓撲序列是有向無環(huán)圖中全部頂點的一個線性序列，若有向圖中存在?。紇,

w＞或存在從頂點v到w的路徑，則在該有向圖的任一拓撲序列中，v肯定在w

之前。下面有向圖的拓撲序列是（）。

A.41235

B.43125

C.42135

D.41325

答案：A

拓撲排序通俗一點來講，其實就是依次遍歷沒有前驅結點的結點。而某一時刻

沒有前驅結點的結點有可能存在多個，所以一個圖的拓撲排序可能有多個。

4號結點沒有前戲，所以拓撲排序的第一個元素是4。當4訪問完了就可以訪問

1，1號訪問完了就可以訪問2,2號訪問完了就可以訪問3或5。所以拓撲排序

結果為：412（35）

58、設有一個包含n個元素的有序線性表。在等概率狀況下刪除其中的一個元素,

若采納依次存儲結構，則平均須要移動（58）個元素；若采納單鏈表存儲，則平

均須要移動（59）個元素。

A.1

B.(n-l)/2

C.logn

D.n

答案：B

若用依次表存儲，則最好狀況是刪除最終一個元素，此時不用移動任何元素，

干脆刪除，最差的狀況是刪除第一個元素，此時須要移動n-1個元素，所以平均

狀態(tài)是移動（n-l）/2。

若用鏈表存儲，干脆將須要刪除元素的前趨next指針指向后繼元素即可，不須

要移動元素，所以移動元素個數(shù)為0。

59、設有一個包含n個元素的有序線性表。在等概率狀況下刪除其中的一個元素,

若采納依次存儲結構，則平均須要移動（58）個元素；若采納單鏈表存儲，則平

均須要移動（59）個元素。

A.0

B.1

C.(n-l)/2

D.n/2

答案：A

若用依次表存儲，則最好狀況是刪除最終一個元素，此時不用移動任何元素，

干脆刪除，最差的狀況是刪除第一個元素，此時須要移動n-1個元素，所以平均

狀態(tài)是移動（n-l）/2。

若用鏈表存儲，干脆將須要刪除元素的前趨next指針指向后繼元素即可，不須

要移動元素，所以移動元素個數(shù)為0。

60、具有3個節(jié)點的二叉樹有（）種形態(tài)。

A.2

B.3

C.5

D.7

答案：C

61、以下關于二叉排序樹（或二叉查找樹、二叉搜尋樹）的敘述中，正確的是（）。

A,對二叉排序樹進行先序、中序和后序遍歷，都得到結點關鍵字的有序序列

B.含有n個結點的二叉排序樹高度為(log2n)+1

C.從根到隨意一個葉子結點的路徑上，結點的關鍵字呈現(xiàn)有序排列的特點

D.從左到右排列同層次的結點，其關鍵字呈現(xiàn)有序排列的特點

答案：D

62、下表為某文件中字符的出現(xiàn)頻率，采納霍夫曼編碼對下列字符編碼，則字符

序列“bee”的編碼為(62)；編碼的對應的字符序列為(63)。

字符abcdef1

頻率(％)4513121695

C.001100100

D.110011011

答案：A

63、A.bad

B.bee

C.face

D.bace

答案：C

64、兩個矩陣Am*n和Bn*p相乘，用基本的方法進行，則須要的乘法次數(shù)為

多個矩陣相乘滿意結合律，不同的乘法依次所須要的乘法次數(shù)不同?？?/p>

m*n*po

慮采納動態(tài)規(guī)劃方法確定Mi,M(i+1),…，Mj多個矩陣連乘的最優(yōu)依次，即所

須要的乘法次數(shù)最少。最少乘法次數(shù)用m[川表示，其遞歸式定義為：

0i2j

力~'min{m[i,k]+m[k+1,J]+%P也}?<J

其中i、j和k為矩陣下標，矩陣序列中Mi的維度為(pi-1)*pi采納自底向上的

方法實現(xiàn)該算法來確定n個矩陣相乘的依次，其時間困難度為(64)o若四個矩

陣Ml、M2、M3、M4相乘的維度序列為2、6、3、10、3,采納上述算法求解,

則乘法次數(shù)為(65)o

A.O(n2)

B.0(n2lgn)

C.0(n3)

D.O(n3lgn)

答案：c

四個矩陣分別為：

2*66*33*1010*3

先計算:Ml*M2 及M3*M4,計算次數(shù)分別為:

2*6*3=36,3*10*3=90。

然后結果相乘，計算次數(shù)為：

2*3*3=18。

36+90+18=144o

65、A.156

B.144

C.180

D.360

答案：B

四個矩陣分別為：

2*66*33*1010*3

先計算:Ml*M2 及M3*M4,計算次數(shù)分別為:

2*6*3=36,3*10*3=90。

然后結果相乘，計算次數(shù)為：

2*3*3=18。

36+90+18=144。

66、以下協(xié)議中屬于應用層協(xié)議的是(66),該協(xié)議的報文封裝在(67)o

A.SNMP

B.ARP

C.ICMP

D.X.25

答案：A

ARP和ICMP是網絡層協(xié)議,X.25是數(shù)據(jù)鏈路層協(xié)議，只有SNMP是應用層協(xié)議。

SNMP協(xié)議的報文是封裝在UDP協(xié)議中傳送。

67、以下協(xié)議中屬于應用層協(xié)議的是(66),該協(xié)議的報文封裝在(67)o

A.TCP

B.IP

C.UDP

D.ICMP

答案：c

ARP和ICMP是網絡層協(xié)議,X.25是數(shù)據(jù)鏈路層協(xié)議，只有SNMP是應用層協(xié)議。

SNMP協(xié)議的報文是封裝在UDP協(xié)議中傳送。

68、某公司內部運用wb.xyz作為訪問某服務器的地址，其中亞13是()。

A.主機名

B.協(xié)議名

C.書目名

D.文件名

答案：A

69、假如路由器收到了多個路由協(xié)議轉發(fā)的關于某個目標的多條路由，那么確定

采納哪條路由的策略是()。

A.選擇與自己路由協(xié)議相同的

B.選擇路由費用最小的

C.比較各個路由的管理距離

D.比較各個路由協(xié)議的版本

答案：C

對于多種不同的路由協(xié)議到一個目的地的路由信息，路由器首先依據(jù)管理距離

確定信任哪一個協(xié)議

70、與地址220.112.179.92匹配的路由表的表項是()。

答案：D

地址220.112.179.92中179的二制碼為10110011,假如網絡號采納22位，與

該地址匹配的路由表項則為220.112.177.6較2。

Softwareentitiesaremorecomplexfortheirsizethanperhapsanyotherhuman

construct,becausenotwopartsarealike(atleastabovethestatementlevel).Ifthey

are,wemakethetwosimilarpartsintoone,a(71),openorclosed.Inthisrespect

softwaresystemsdifferprofoundlyfromcomputers,buildings,orautomobiles,where

repeatedelementsabound.

Digitalcomputersarethemselvesmorecomplexthanmostthingspeoplebuild;they

haveverylargenumbersofstates.Thismakesconceiving,describing,andtesting

themhard.Softwaresystemshaveordersofmagnitudemore(72)thancomputers

do.

Likewise,ascaling-upofasoftwareentityisnotmerelyarepetitionofthesame

elementsinlargersize;itisnecessarilyanincreaseinthenumberofdifferent

elements.Inmostcases,theelementsinteractwitheachotherinsome(73)

fashion,andthecomplexityofthewholeincreasesmuchmorethanlinearly.

Thecomplexityofsoftwareisa(an)(74)property,notanaccidentalone.Hence

descriptionsofasoftwareentitythatabstractawayitscomplexityoftenabstract

awayitsessence.Mathematicsandthephysicalsciencesmadegreatstridesforthree

centuriesbyconstructingsimplifiedmodelsofcomplexphenomena,deriving

propertiesfromthemodels,andverifyingthosepropertiesexperimentally.This

workedbecausethecomplexities(75)inthemodelswerenottheessential

propertiesofthephenomena.Itdoesnotworkwhenthecomplexitiesarethe

essence.

Manyoftheclassicalproblemsofdevelopingsoftwareproductsderivefromthis

essentialcomplexityanditsnonlinearincreaseswithsize.Notonlytechnical

problemsbutmanagementproblemsaswellcomefromthecomplexity.

71、A.task

B.job

C.subroutine

D.program

答案：C

72、A.states

B.parts

C.conditions

D.expressions

答案：A

73、A.linear

B.nonlinear

C.parallel

D.additive

答案：B

74、A.surface

B.outside

C.exterior

D.essential

答案：D

75、A.fixed

B.included

C.ignored

D.stabilized

答案：C

下午試卷案例

第1題

閱讀下列說明，回答問題1至問題4,將解答填入答題紙的對應欄內。

【說明】

某證券交易所為了便利供應證券交易服務，欲開發(fā)一證券交易平臺，該平臺的主

要功能如F：

（1）開戶。依據(jù)客戶服務助理提交的開戶信息，進行開戶，并將客戶信息存入

客戶記錄中，賬戶信息（余額等）存入賬戶記錄中；

（2）存款?？蛻艨梢韵蚱滟~戶中存款，依據(jù)存款金額修改賬戶余額；

（3）取款?？蛻艨梢詮钠滟~戶中取款，依據(jù)取款金額修改賬戶余額；

（4）證券交易?？蛻艉徒浖o人均可以進行證券交易（客戶通過在線方式，經紀

人通過電話），將交易信息存入交易記錄中；

（5）檢查交易。平臺從交易記錄中讀取交易信息，將交易明細返回給客戶。

現(xiàn)采納結構化方法對該證券交易平臺進行分析與設計，獲得如圖1-1所示的上下

文數(shù)據(jù)流圖和圖1-2所示的0層數(shù)據(jù)流圖。

圖1-1上下文數(shù)據(jù)海圖

B1-2。層敷■據(jù)流圖

問題：1.1（3分）

運用說明中的詞語，給出圖1-1中的實體E1-臼的名稱。

問題：1.2（3分）

運用說明中的詞語，給出圖1-2中的數(shù)據(jù)存儲D1-D3的名稱。

問題：1.3（4分）

依據(jù)說明和圖中的術語，補充圖1-2中缺失的數(shù)據(jù)流及其起點和終點。

問題：1.4（5分）

實際的證券交易通常是在證券交易中心完成的，因此，該平臺的“證券交易”功

能需將交易信息傳遞給證券交易中心。針對這個功能需求，須要對圖1-1和圖1-2

進行哪些修改，請用200字以內的文字加以說明。

答案解析：

El：客戶服務助理，E2：客戶，E3：經紀人。

本題要求識別E1-E3詳細為哪個外部實體，通讀試題說明，可以了解到適合充當

外部實體的包括：客戶、客戶服務助理、經記人。詳細的對應關系，可以通過將

頂層圖與題目說明進行匹配得知。如：從圖中可看出E1會向交易平臺發(fā)出數(shù)據(jù)

流開戶信息;；而從試題說明依據(jù)客戶服務助理提交的開戶信息，進行開戶，并

將客戶信息存入客戶記錄中，賬戶信息存入賬戶記錄中可以看出，E1對應是客

戶服務助理。E2、E3同理可得。

答案解析：

D1：客戶記錄，D2：賬戶記錄，D3：交易記錄。

本題要求識別存儲，解決這類問題，以圖的分析為主，協(xié)作說明給存儲命名，因

為存儲相關的數(shù)據(jù)流一般呈現(xiàn)了這個存儲中究竟存了些什么信息，如從圖中可以

看到D1中有客戶信息，而D2中有賬戶信息，題目說明中又有依據(jù)客戶服務助

理提交的開戶信息，進行開戶，并將客戶信息存入客戶記錄中，賬戶信息存入賬

戶記錄中。自然D1應為客戶記錄，D2應為賬戶記錄。同理，D3為交易記錄。

答案解析：

數(shù)據(jù)流名稱：修改賬戶余額，起點：存款，終點：D2。

數(shù)據(jù)流名稱：修改賬戶余額，起點：取款，終點：D2。

數(shù)據(jù)流名稱：交易信息存入交易記錄，起點：證券交易，終點：D3o

缺失數(shù)據(jù)流1

名稱：修改賬戶余額，起點：存款，終點：D2。

理由：從試題說明客戶可以向其賬戶中存款，依據(jù)存款金額修改賬戶余額可以看

出，這個功能有操作依據(jù)存款金額修改賬戶余額。據(jù)此可以了解到從該功能應有

數(shù)據(jù)流存款至D2,而0層圖沒有。

缺失數(shù)據(jù)流2:

名稱：修改賬戶余額，起點：取款，終點：D2o

理由：從試題說明客戶可以從其賬戶中取款，依據(jù)取款金額修改賬戶余額可以看

出，這個功能有操作依據(jù)取款金額修改賬戶余額。據(jù)此可以了解到從該功能應有

數(shù)據(jù)流取款至D2,而0層圖沒有。

缺失數(shù)據(jù)流3

名稱：交易信息存入交易記錄，起點：證券交易，終點：D3。

理由：從試題說明客戶和經紀人均可以進行證券交易，將交易信息存入交易記錄

中可以看出，這個功能有操作將交易信息存入交易記錄中。據(jù)此可以了解到從該

功能應有數(shù)據(jù)流證券交易至D3,而。層圖沒有。

答案解析：

增加外部實體證券交易中心，原來證券交易中的交易信息的數(shù)據(jù)流終點改為證券

交易中心，數(shù)據(jù)流檢測交易中的起點改為證券交易中心。

本題強調實際的證券交易通常是在證券交易中心完成，這個證券交易中心屬于典

型的外部實體，所以須要增加外部實體證券交易中心。由于該平臺的證券交易功

能需將交易信息傳遞給證券交易中心，因此將原來證券交易中的交易信息的數(shù)據(jù)

流終點改為證券交易中心，數(shù)據(jù)流檢測交易中的起點改為證券交易中心。

第2題

【說明】

某賓館為了有效地管理客房資源，滿意不同客戶需求，擬構建一套賓館信息管理

系統(tǒng)，以便利賓館管理及客房預訂等業(yè)務活動。

［需求分析結果］

該崇統(tǒng)的部分功能及初步需求分析的結果如下：

（1）賓館有多個部門，部門信息包括部門號、部門名稱、電話、經理。每個部

門可以有多名員工，每名員工只屬于一個部門；每個部門只有一名經理，負責管

理本部門。

（2）員工信息包括員工號、姓名、崗位、電話、工資，其中，員工號唯一標識

員工關系中的一個元組，崗位有經理、業(yè)務員。

（3）客房信息包括客房號（如1301、1302等）、客房類型、收費標準、入住狀

態(tài)（已入住/未入?。?，其中客房號唯一標識客房關系中的一個元組，不同客房

類型具有不同的收費標準。

（4）客戶信息包括客戶號、單位名稱、聯(lián)系人、聯(lián)系電話、聯(lián)系地址，其中客

戶號唯一標識客戶關系中的一個元組。

（5）客戶預訂客房時，須要填寫預訂申請。預訂申請信息包括申請?zhí)?、客戶號?/p>

入住時間、入住天數(shù)、客房類型、客房數(shù)量，其中，一個申請?zhí)栁ㄒ粯俗R預訂申

請中的一個元組；一位客戶可以有多個預訂申請，但一個預訂申請對應唯一的一

位客戶。

（6）當客戶入住時，業(yè)務員依據(jù)客戶的預訂申請負責支配入住客房事宜。支配

信息包括客房號、姓名、性別、身份證號、入住時間、天數(shù)、電話，其中客房號、

身份證號和入住時間唯一標識一次支配。一名業(yè)務員可以支配多個預訂申請，一

個預訂申請只由一名業(yè)務員支配，而且可支配多間同類型的客房。

【概念模型設計】

依據(jù)需求階段收集的信息，設計的實體聯(lián)系圖如圖2-1所示。

及理客戶

A

員工客房

王

業(yè)務員預訂申請

圖24實體聯(lián)系圖

【關系模式設計】

部門（部門號，部門名稱，經理，電話）

員工（員工號，（a）,姓名，崗位，電話，工資）

客戶（（b）,聯(lián)系人，聯(lián)系電話，聯(lián)系地址）

客房（客房號，客房類型，收費標準，入住狀態(tài)）

預訂申請（（c）,入住時間，天數(shù)，客房類型，客房數(shù)量）

支配（申請?zhí)枺头刻?，姓名，性別，（d）,天數(shù)，電話，業(yè)務員）

問題：2.1（4分）

依據(jù)問題描述，補充四個聯(lián)系，完善圖2-1,的實體聯(lián)系圖。聯(lián)系名可用聯(lián)系1、

聯(lián)系2、聯(lián)系3和聯(lián)系4代替，聯(lián)系的類型為1:1、l:n和m:n（或1:1,和1:*

和*：*）o

問題：2.2（8分）

（1）依據(jù)題意，將關系模式中的空（a）?（d）補充完整，并填入答題紙對應

的位置上。

（2）給出“預訂申請”和“支配”關系模式的主鍵和外鍵。

問題：2.3（3分）

【關系模式設計】中的“客房”關系模式是否存在規(guī)范性問題，請用100字以內

文字說明你的觀點（若存在問題，應說明如何修改“客房”關系模式）。

答案解析：

1、經理與部門之間存在1:1的聯(lián)系。

2、部門與員工之間存在l:n的聯(lián)系。

3,客戶與預訂申請之間存在l:n的聯(lián)系。

4,業(yè)務員、客房、預訂申請之間存在l:m:n的聯(lián)系。

答案解析：

（a）部門號。

（b）客戶號、單位名稱

（c）申請?zhí)枴⒖蛻籼枴?/p>

（d）身份證號、入住時間。

預訂申請關系模式中的主鍵是申請?zhí)?，外鍵是申請?zhí)枴⒖蛻籼枴?/p>

支配關系模式中的主鍵是：（客房號、身份證號、入住時間），外鍵是：申請?zhí)枴?/p>

客房號、業(yè)務員。

答案解析：

依據(jù)試題中的描述，客房信息中客房號是唯一標識客房關系的一個元組，即可以

作為唯一的主鍵。在客房關系模式中，不存在其他部分依靠關系，但客房號。類

型。收費標準，存在傳遞函數(shù)依靠，所以冗余，添加異樣，修改異樣，刪除異樣

均存在。

第3題

【說明】

某種出售罐裝飲料的自動售貨機.（VendingMachine）的工作過程描述如下：

（1）顧客選擇所需購買的飲料及數(shù)量。

（2）顧客從投幣口向自動售貨機中投入硬幣（該自動售貨機只接收硬幣）。硬

幣器收集投入的硬幣并計算其對應的價值。假如所投入的硬幣足夠購買所需數(shù)量

的這種飲料且飲料數(shù)量足夠，則推出飲料，計算找零，顧客取走飲料和找回的硬

幣；假如投入的硬幣不夠或者所選購的飲料數(shù)量不足，則提示用戶接著投入硬幣

或重新選擇飲料及數(shù)量。

（3）一次購買結束之后，將硬幣器中的硬幣移走（清空硬幣器），等待下一次

交易。自動售貨機還設有一個退幣按鈕，用于退還顧客所投入的硬幣。已經勝利

購買飲料的錢是不會被退回的。

圖3-1用例圖

采納面對對象方法分析和設計該自動售貨機的軟件系統(tǒng)，得到如圖3-1所示的用

例圖，其中，用例''購買飲料”的用例規(guī)約描述如下。

參加者：顧客。

主要事務流：

1.顧客選擇須要購買的飲料和數(shù)量，投入硬幣；

2.自動售貨機檢查顧客是否投入足夠的硬幣；

3.自動售貨機檢查飲料儲存?zhèn)}中所選購的飲料是否足夠；

4.自動售貨機推出飲料；

5.自動售貨機返回找零。

各選事務流：

2a.若投入的硬幣不足，則給出提示并退回到1；

3a.若所選購的飲料數(shù)量不足，則給出提示并退回到1。

依據(jù)用例“購買飲料”得到自動售貨機的4個狀態(tài)：“空閑”狀態(tài)、“打算服務”

狀態(tài)、“可購買”狀態(tài)以及“飲料出售”狀態(tài)，對應的狀態(tài)圖如圖3-2所示。

所設計的類圖如圖3-3所示。

圖3-2狀態(tài)圖

K3-3類圖

問題：3.1（6分）

依據(jù)說明中的描述，運用說明中的術語，給出圖3-2中的S1?S4所對應的狀態(tài)

名。

問題：3.2（4分）

依據(jù)說明中的描述，運用說明中的術語，給出圖3-2中的E1?E4所對應的事務

名

問題：3.3（5分）

依據(jù)說明中的描述，運用說明中的術語、給出圖3-3中C1?C5所對應的類名。

答案解析：

S1：空閑，S2：打算服務，S3：飲料出售，S4：可購買。

本題系統(tǒng)中的狀態(tài)圖，是對狀態(tài)轉換的圖形化表達。從題目的說明部分可知，在

狀態(tài)轉換過程中，涉及到的狀態(tài)一共有四種：空閑、打算服務、可購買、飲料出

售。從狀態(tài)圖涉及的轉換可知S1~S4分別為：空閑、打算服務、飲料出售、可購

買。關于狀態(tài)轉換的分析如下：

（1）清空硬幣器后，自動售貨機等待下一次交易，進入空閑狀態(tài)。此時可隨意

的進行飲料選擇數(shù)量，一旦顧客投入硬幣，自動售貨機便進入打算服務狀態(tài)。

（2）當自動售貨機進行打算服務狀態(tài)時，起先計算硬幣價值，假如硬幣不夠則

提示顧客接著投入硬幣。假如硬幣足夠，則進入可購買狀態(tài)。

（3）進行可購買狀態(tài)后，自動售貨機推斷飲料數(shù)量。假如數(shù)量不夠，則返回打

算服務狀態(tài)提示用戶重新選擇飲料。假如數(shù)量足夠，則推出飲料進入飲料出售狀

態(tài)。

（4）進行飲料出售狀態(tài)后，自動售貨機計算找零，并返回進入空閑狀態(tài)等待下

一次交易。

答案解析：

E1：飲料數(shù)量不足，E2：硬幣數(shù)量足夠，E3：推出飲料，E4：返回找零。

答案解析：

C1：自動售貨機，C2：硬幣器，C3：飲料儲存?zhèn)}，C4：硬幣，C5：飲料。

第4題

閱讀下列說明和C代碼，回答問題1至問題3,將解答寫在答題紙的對應欄內。

【說明】

模式匹配是指給定主串t和子串s,在主串t中找尋子串s的過程，其中s稱為模

式。假如匹配勝利，返回s在t中的位置，否則返回。

KMP算法用next數(shù)組對匹配過程進行了優(yōu)化。KMP算法的偽代碼描述如下：

1.在串t和串s中，分別設比較的起始下標i=j=O。

2.假如串t和串s都還有字符，則循環(huán)執(zhí)行下列操作：

⑴假如j=-l或者t[i]=s[j],則將i和j分別加1,接著比較t和s的下一個字符;

（2）否則,將j向右滑動到next。]的位置，即上=1^皿。

3.假如s中全部字符均已比較完畢，則返回匹配的起始位置（從1起先）；否

則返回-L

其中，next數(shù)組依據(jù)子串s求解。求解next數(shù)組的代碼已由get_next函數(shù)給出。

【C代碼】

(1)常量和變量說明

t,s：長度為憫度Is的字符串

next:next數(shù)組，長度為Is

(2)C程序

#include<stdio.h>

#include<stdlib.h>

#include<string.h>

/*求next口的值*/

voidget_next(int*next,char*s,intIs){

inti=0,j=-l;

next[0]=-l;/*初始化next[0]*/

while。<ls){/*還有字符*/

if(j==-llls[i]==s[j]){/*匹配*/

j++；

i++；

if(s[i]==s[j])

next[i]=next[j];

else

Next[i]=j;

)

else

j=next[j];

)

)

intkmp(int*next,char*t,char*s,intIt,intIs)

{

Inti=0,j=0;

while(i<It&&(1)){

if(j==-lII(2)){

i++；

j++；

}else

(3);

)

if(j>=Is)

return(4);

else

return-1;

)

問題：4.1(8分)

依據(jù)題干說明，填充C代碼中的空(1)?(4).

問題：4.2（2分）

依據(jù)題干說明和C代碼，分析出kmp算法的時間困難度為（5）（主串和子串的

長度分別為It和Is,用0符號表示）。

問題：4.3（5分）

依據(jù)C代碼，字符串“BBABBCAC”的next數(shù)組元素值為（6）（干脆寫素值，

之間用逗號隔開）。若主串為"AABBCBBABBCACCD”，子串為“BBABBCAC”，

則函數(shù)Kmp的返回值是（7）。

答案解析：

(1)：j<ls

(2)：t[i]==s[j];

(3)：get_next(next,s,Is);

j=next[j]

(4)：i+l-ls

答案解析:

(5)0(ls+lt)

答案解析：

(6)[-1,-1,1,-