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

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

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

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

3.【問答題】15分|【問題1】（8分）根據(jù)題干說明，填充C代碼中的空（1）～（4）.【問題2】（2分）根據(jù)題干說明和C代碼，分析出kmp算法的時間復(fù)雜度為（5）（主串和子串的長度分別為It和Is，用O符號表示）。【問題3】（5分）根據(jù)C代碼，字符串"BBABBCAC"的next數(shù)組元素值為（6）（直接寫素值，之間用逗號隔開）。若主串為"AABBCBBABBCACCD"，子串為"BBABBCAC"，則函數(shù)Kmp的返回值是（7）。閱讀下列說明和C代碼，回答問題1至問題3，將解答寫在答題紙的對應(yīng)欄內(nèi)?！菊f明】模式匹配是指給定主串t和子串s，在主串t中尋找子串s的過程，其中s稱為模式。如果匹配成功，返回s在t中的位置，否則返回-1。KMP算法用next數(shù)組對匹配過程進(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的下一個字符；（2）否則，將j向右滑動到next[j]的位置，即j=next[j]。3．如果s中所有字符均已比較完畢，則返回匹配的起始位置（從1開始）；否則返回-1。其中，next數(shù)組根據(jù)子串s求解。求解next數(shù)組的代碼已由get_next函數(shù)給出。【C代碼】（1）常量和變量說明t，s：長度為lt和ls的字符串next:next數(shù)組，長度為ls（2）C程序

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

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

6.【問答題】15分|

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