2022年11月程序員考前模擬下午題（二）

精品文檔-下載后可編輯年11月程序員考前模擬下午題（二）2022年11月程序員考前模擬下午題（二）

1.【問(wèn)答題】15分|閱讀下列說(shuō)明和圖，回答問(wèn)題，將解答填入答題紙的對(duì)應(yīng)欄內(nèi)。閱讀以下說(shuō)明和流程圖，填補(bǔ)流程圖中的空缺（1）～（5），將解答填入答題紙的對(duì)應(yīng)欄內(nèi)?！菊f(shuō)明】指定網(wǎng)頁(yè)中，某個(gè)關(guān)鍵詞出現(xiàn)的次數(shù)除以該網(wǎng)頁(yè)長(zhǎng)度稱為該關(guān)鍵詞在此網(wǎng)頁(yè)中的詞頻。對(duì)新聞?lì)惥W(wǎng)頁(yè)，存在一組公共的關(guān)鍵詞。因此，每個(gè)新聞網(wǎng)頁(yè)都存在一組詞頻，稱為該新聞網(wǎng)頁(yè)的特征向量。設(shè)兩個(gè)新聞網(wǎng)頁(yè)的特征向量分別為：甲(a1,a2,…,ak)、乙(b1,b2,…,bk)，則計(jì)算這兩個(gè)網(wǎng)頁(yè)的相似度時(shí)需要先計(jì)算它們的內(nèi)積S=a1b1+a2b2+…+akbk。一般情況下，新聞網(wǎng)頁(yè)特征向量的維數(shù)是巨大的，但每個(gè)特征向量中非零元素卻并不多。為了節(jié)省存儲(chǔ)空間和計(jì)算時(shí)間，我們依次用特征向量中非零元素的序號(hào)及相應(yīng)的詞頻值來(lái)簡(jiǎn)化特征向量。為此，我們用（NA(i),A(i)|i=1,2,…,m）和（NB(j),B(j)|j=1,2,…,n）來(lái)簡(jiǎn)化兩個(gè)網(wǎng)頁(yè)的特征向量。其中：NA(i)從前到后描述了特征向量甲中非零元素A(i)的序號(hào)（NA(1)

2.【問(wèn)答題】15分|【說(shuō)明2】函數(shù)reverse(char*s，intlen)的功能是用遞歸方式逆置長(zhǎng)度為len的字符串s。例如，若串s的內(nèi)容為"abcd"，則逆置后其內(nèi)容變?yōu)?dcba"?！綜函數(shù)】閱讀下列說(shuō)明和圖，回答問(wèn)題，將解答填入答題紙的對(duì)應(yīng)欄內(nèi)。閱讀以下說(shuō)明和C函數(shù)，將應(yīng)填入（n）處的語(yǔ)句或語(yǔ)句成分寫在答題紙的對(duì)應(yīng)欄內(nèi)?！菊f(shuō)明1】函數(shù)deldigit(char*s)的功能是將字符串s中的數(shù)字字符去掉，使剩余字符按原次序構(gòu)成一個(gè)新串，并保存在原串空間中。其思路是：先申請(qǐng)一個(gè)與s等長(zhǎng)的臨時(shí)字符串空間并令t指向它，將非數(shù)字字符按次序暫存入該空間，最后再拷貝給s?！綜函數(shù)】

3.【問(wèn)答題】15分|【問(wèn)題1】（8分）根據(jù)題干說(shuō)明，填充C代碼中的空（1）～（4）.【問(wèn)題2】（2分）根據(jù)題干說(shuō)明和C代碼，分析出kmp算法的時(shí)間復(fù)雜度為（5）（主串和子串的長(zhǎng)度分別為It和Is，用O符號(hào)表示）?！締?wèn)題3】（5分）根據(jù)C代碼，字符串"BBABBCAC"的next數(shù)組元素值為（6）（直接寫素值，之間用逗號(hào)隔開(kāi)）。若主串為"AABBCBBABBCACCD"，子串為"BBABBCAC"，則函數(shù)Kmp的返回值是（7）。閱讀下列說(shuō)明和C代碼，回答問(wèn)題1至問(wèn)題3，將解答寫在答題紙的對(duì)應(yīng)欄內(nèi)。【說(shuō)明】模式匹配是指給定主串t和子串s，在主串t中尋找子串s的過(guò)程，其中s稱為模式。如果匹配成功，返回s在t中的位置，否則返回-1。KMP算法用next數(shù)組對(duì)匹配過(guò)程進(jìn)行了優(yōu)化。KMP算法的偽代碼描述如下：1．在串t和串s中，分別設(shè)比較的起始下標(biāo)i=j=0。2．如果串t和串s都還有字符，則循環(huán)執(zhí)行下列操作：（1）如果j=-l或者t[i]=s[j]，則將i和j分別加1，繼續(xù)比較t和s的下一個(gè)字符；（2）否則，將j向右滑動(dòng)到next[j]的位置，即j=next[j]。3．如果s中所有字符均已比較完畢，則返回匹配的起始位置（從1開(kāi)始）；否則返回-1。其中，next數(shù)組根據(jù)子串s求解。求解next數(shù)組的代碼已由get_next函數(shù)給出。【C代碼】（1）常量和變量說(shuō)明t，s：長(zhǎng)度為lt和ls的字符串next:next數(shù)組，長(zhǎng)度為ls（2）C程序

4.【問(wèn)答題】15分|【問(wèn)題1】（10分）根據(jù)題干說(shuō)明。填充C代碼中的空（1）～（5）?！締?wèn)題2】（5分）根據(jù)題干說(shuō)明和C代碼，算法采用的設(shè)計(jì)策略為（），該方法在遍歷圖的頂點(diǎn)時(shí)，采用的是（）方法（深度優(yōu)先或廣度優(yōu)先）。閱讀下列說(shuō)明和C代碼，回答問(wèn)題1至問(wèn)題2，將解答寫在答題紙的對(duì)應(yīng)欄內(nèi)?！菊f(shuō)明】一個(gè)無(wú)向連通圖G點(diǎn)上的哈密爾頓（Hamiltion）回路是指從圖G上的某個(gè)頂點(diǎn)出發(fā)，經(jīng)過(guò)圖上所有其他頂點(diǎn)一次且僅一次，最后回到該頂點(diǎn)的路徑。哈密爾頓回路算法的基礎(chǔ)如下：假設(shè)圖G存在一個(gè)從頂點(diǎn)V0出發(fā)的哈密爾頓回路V1--V2--V3--...--Vn-1--V0。算法從頂點(diǎn)V0出發(fā)，訪問(wèn)該頂點(diǎn)的一個(gè)未被訪問(wèn)的鄰接頂點(diǎn)V1，接著從頂點(diǎn)V1出發(fā)，訪問(wèn)V1一個(gè)未被訪問(wèn)的鄰接頂點(diǎn)V2，..。；對(duì)頂點(diǎn)Vi，重復(fù)進(jìn)行以下操作：訪問(wèn)Vi的一個(gè)未被訪問(wèn)的鄰接接點(diǎn)Vi+1；若Vi的所有鄰接頂點(diǎn)均已被訪問(wèn)，則返回到頂點(diǎn)Vi-1，考慮Vi-1的下一個(gè)未被訪問(wèn)的鄰接頂點(diǎn)，仍記為Vi；直到找到一條哈密爾頓回路或者找不到哈密爾頓回路，算法結(jié)束。【C代碼】下面是算法的C語(yǔ)言實(shí)現(xiàn)。（1）常量和變量說(shuō)明n:圖G中的頂點(diǎn)數(shù)c［］［］:圖G的鄰接矩陣K:統(tǒng)計(jì)變量，當(dāng)前已經(jīng)訪問(wèn)的頂點(diǎn)數(shù)為k+1x［k］:第k個(gè)訪問(wèn)的頂點(diǎn)編號(hào)，從0開(kāi)始Visited［x［k］］：第k個(gè)頂點(diǎn)的訪問(wèn)標(biāo)志，0表示未訪問(wèn)，1表示已訪問(wèn)（2）C程序

5.【問(wèn)答題】15分|閱讀下列說(shuō)明和C++代碼，將應(yīng)填入（）處的字句寫在答題紙的對(duì)應(yīng)欄內(nèi)。【說(shuō)明】某圖像預(yù)覽程序要求能夠查看BMP、JPEG和GIF三種格式的文件，且能夠Windows和Linux兩種操作系統(tǒng)上運(yùn)行。程序需具有較好的擴(kuò)展性以支持新的文件格式和操作系統(tǒng)。為滿足上述需求并減少所需生成的子類數(shù)目，現(xiàn)采用橋接（Bridge）模式進(jìn)行設(shè)計(jì)，得到如圖5-1所示的類圖。【C++代碼】

6.【問(wèn)答題】15分|

閱讀下列說(shuō)明和Java代碼，將應(yīng)填入（）處的字句寫在答題紙的對(duì)應(yīng)欄內(nèi)?！菊f(shuō)明】某圖像預(yù)覽程序要求能夠查看BMP、JPEG和G