02筆試題-數(shù)據(jù)結(jié)構(gòu)部分

1、數(shù)據(jù)結(jié)構(gòu) 1. 采用折半搜索算法長(zhǎng)度為 n 的有序表時(shí)，元素的平均搜索長(zhǎng)度為() A) O(n2) B) O(nlog2n) C) O(log2n) D) O(n) 2. 下面程序的時(shí)間復(fù)雜度為() for(int i=0;im;i+) for(int j=0;j,最壞情況下需要比較多少次 () A)2n B) 2n-1 C) 2n+1 D) n2 9. 深度為 5 的滿二叉樹(shù)中，葉子結(jié)點(diǎn)的個(gè)數(shù)為() A) 32 B) 31 C) 16 D) 15 10. 冒泡排序算法和快速排序算法的時(shí)間復(fù)雜度分別是什么 11. 請(qǐng)簡(jiǎn)述數(shù)組和鏈表數(shù)據(jù)結(jié)構(gòu)的特點(diǎn)及應(yīng)用的場(chǎng)合 12. 下列哪些數(shù)據(jù)結(jié)構(gòu)最適合醫(yī)療儀

2、器設(shè)備中的大型數(shù)據(jù)量的插入，查找 （） A） 數(shù)組 B） 哈希表 C） 紅黑樹(shù)/二叉平衡樹(shù) D） 鏈表 13下列哪些排序算法的平均時(shí)間復(fù)雜度是 O（nlog2n）（）,哪些是穩(wěn)定的排 序（）A）冒泡排序 B） 希爾排序 C） 快速排序 D） 插入排序 E） 堆排序 14. 下列哪些說(shuō)法是正確的：（） A）二分查找法在一個(gè)長(zhǎng)度為 1000 的有序整數(shù)數(shù)組查找一個(gè)整數(shù)，比較的次 數(shù)不超過(guò) 100 次 B）在二叉樹(shù)中查找元素的時(shí)間復(fù)雜度為 O（log2n）; C） 對(duì)單向鏈表，可以使用冒泡排序； D） 對(duì)雙向鏈表，可以使用快速排序； 15. 已知某二叉樹(shù)的后序遍歷是 DFBEGCA 中序遍歷的順序是

3、 DBFACEG 其 前序遍歷順序是 _ 16. 下列代碼將兩個(gè)有序鏈表結(jié)合為一個(gè)，鏈表中的元素的排列順序?yàn)閺男?到大。請(qǐng)補(bǔ)充其中的空缺。 struct node struct node *pnext; int val; ; struct node* splice(struct node* plhs,struct node* prsh) if( _ ) return prhsprhs:plhs; struct node* phead,*plast; if( _ ) phead = plast = prhs; plhs = plhs-pnext; else phead = plast = plh

4、s; prhs = prhs-pnext; while( _ ) if(plhs-val val) plast-pnext = plhs; plast = plhs; plhs = plhs-pnext; else plast-pnext = prhs; plast = prhs; prhs = prhs-pnext; plast-pnest = _ ; return _ ; 17. 比較哈希表和平衡二叉樹(shù)的特點(diǎn)， 他們分別用在哪些場(chǎng)合 . 18. 一個(gè)棧的入棧序列是 A,B,C,D,E 則棧的不可能的輸出序列是() A) EDCBA B) DECBA C) DCEAB D) ABCDE 19

5、. 在排序的方法中，關(guān)鍵碼比較次數(shù)與記錄地初始排列無(wú)關(guān)的是() A) Shell B) 歸并排序 C) 直接排序 D) 選擇排序 20. 以下反向遍歷 array 數(shù)組的方法有什么錯(cuò)誤 vector array; (1) ; (2) ; (3) ; for(vector:size_type i=()-1;i=0;-i) cout arrayi next 48. 設(shè)單鏈表中節(jié)點(diǎn)的結(jié)構(gòu)為： typedef struct node Elemtype data;何證明一個(gè)表是循環(huán)鏈表 52. 如果一棵二叉樹(shù)節(jié)點(diǎn)的前序序列是 A、B、 C， 該二叉樹(shù)節(jié)點(diǎn)的中序序列是什么 A)必為 ABC B)必為 AC

6、B C 必為BCA 53. 什么是平衡二叉樹(shù) 54. 下面的程序是一快速排序問(wèn)題，請(qǐng)?zhí)羁铡?后序序列是 C、B、A,則 D）不能確定 #include #include void improveqsort(int *list,int m,int n) int k,t,i,j; /* for (i=0;i10;i+) printf(%3d,listi);*/ if(mn) i=m;j=n+1;k=listm; while(ij) for(i=i+1,i=k) break; for(j=j-1,jm,j-) if(listj=k) break; if(ij) t=listi;listi=listj

7、;listj=t; t=listm;listm=listj;listj=t; improveqsort( ); improveqsort( ); main() int list10; int n=9, m=0,i; printf(input 10 number:); for(i=0;i10;i+) scanf(%d,&listi); printf(n); improveqsort(list,m,n); for(i=0;i10;i+) printf(%5d,listi); printf(n); 55. 以下哪種排序?qū)儆诜€(wěn)定排序 A)歸并排序 B)快速排序 C 希爾排序 D)堆排序 56. 用二分

8、法查找一個(gè)長(zhǎng)度為 10 的、排好序的線性表，查找不成功時(shí)，最多 需要比較多少次 A) 5 B) 2 C) 4 D) 1 57. 下面那種排序法對(duì) 1234567 最快 A) quick sort B) bubble sort C) merge sort 58. 解釋一下什么是哈夫曼編碼問(wèn)題 59. 假設(shè)執(zhí)行語(yǔ)句 Q 的時(shí)間是 0( 1),則執(zhí)行下列程序段的時(shí)間為() for(int i = 1;i = n;i+) for(int j = i; j next二p;q-next =s; I. 在一個(gè)單鏈表中，若刪除 p 所指節(jié)點(diǎn)的后續(xù)結(jié)點(diǎn)，則執(zhí)行 p=p-next;p-next=p-next-ne

9、xt J. 使用鏈表，可隨機(jī)訪問(wèn)鏈表中的任何一個(gè)元素 100. 調(diào)用 printf 函數(shù)可以分解為九個(gè)過(guò)程,請(qǐng)寫(xiě)出他們的排列順序 指令 出棧 C. 函數(shù)參數(shù)壓棧 D. 收回局部變量空間 壓棧 F. 在棧上保留局部變量 G. 函數(shù)參數(shù)出棧 指令 I打印輸出字符串 102. 在以下幾種數(shù)據(jù)結(jié)構(gòu)中，在執(zhí)行數(shù)量相當(dāng)?shù)牟檎遥瑒h除和插入操作時(shí)， 綜合性能最好的數(shù)據(jù)結(jié)構(gòu)是： A. 雙向鏈表 B. 分塊鏈表 C. 穿線二叉樹(shù) D. 堆 103. 廣告系統(tǒng)為了做地理位置定向，將 IPV4 分割為 627672 個(gè)區(qū)間，并標(biāo)識(shí) 了地理位置信息，區(qū)間之間無(wú)重疊，用二分查找將 IP 地址映射到地理位置信 息， 請(qǐng)問(wèn)在

10、最壞的情況下，需要查找多少步 A 17 B 18 C 19 D20 104. 以入棧順序作為輸入，出棧作為輸出，并以 I 代表入棧，0 代表出棧， 現(xiàn)將 1,2,3,4 順序入棧，則棧操作序列 IIIIOO00 后，輸出 4321;與輸出 1234 相 對(duì)應(yīng) 的棧操作序列為 I0I0I0I0 則若想得到輸出為 2314,則棧操作序列應(yīng)為 無(wú)法由棧操作序列而得到的輸出有 _ 。 105. 設(shè)一組初始記錄關(guān)鍵字序列為( 20,18,22,16,30,19)，則根據(jù)這些初始 關(guān)鍵字序列建成的初始堆為 _ . 106. 線性有序表(a1,a2,a3,.a)5 是從小到大排列的，對(duì)一個(gè)給定的值 k,用二

11、分法檢索表中與 K 相等的元素，在查找不成功的情況下，最多需要檢索 _ 次。 編程 1 單鏈表 1 ：編程實(shí)現(xiàn)一個(gè)單鏈表的建立。 2：編程實(shí)現(xiàn)一個(gè)單鏈表的側(cè)長(zhǎng)。 3：編程實(shí)現(xiàn)一個(gè)單鏈表的打印。 4：編程實(shí)現(xiàn)一個(gè)單鏈表刪除節(jié)點(diǎn)。 5：編程實(shí)現(xiàn)單鏈表的插入。 6：編程實(shí)現(xiàn)單鏈表的逆置。 2 雙鏈表 1：編程實(shí)現(xiàn)雙鏈表的建立。 2：編程實(shí)現(xiàn)雙鏈表的側(cè)長(zhǎng)。 3：編程實(shí)現(xiàn)雙鏈表的打印。 4：編程實(shí)現(xiàn)雙鏈表刪除節(jié)點(diǎn)。 5：編程實(shí)現(xiàn)雙鏈表的插入。 1：編程實(shí)現(xiàn)隊(duì)列的入隊(duì)。 2：編程實(shí)現(xiàn)隊(duì)列的出隊(duì)。 3：編程實(shí)現(xiàn)隊(duì)列的側(cè)長(zhǎng)。 4：編程實(shí)現(xiàn)隊(duì)列的打印。 1.一個(gè)學(xué)生的信息：姓名，學(xué)號(hào)，性別，年齡等信息，用一個(gè)鏈

12、表，把這些 學(xué)生信息連在一起，給出一個(gè) age,在這些鏈表中刪除學(xué)生年齡等于 age 的學(xué)生 信息。 2請(qǐng)用 C 或 C+寫(xiě)出一個(gè)冒泡排序程序，要求輸入 10 個(gè)整數(shù)，輸出排序結(jié) 果。 3請(qǐng)用 C 或 C+寫(xiě)出一個(gè) shell 排序程序， 要求輸入 10 個(gè)整數(shù)，輸出排序結(jié) 果。 4. 鏈表 struct student int m_Num;造一個(gè)有 20 名學(xué)生的單向鏈表。按順序每名學(xué)生的分?jǐn)?shù)值為， 1,2,3,5,8,13. 2).求出他們的平均分。 5. 請(qǐng)實(shí)現(xiàn)一個(gè)快速排序的算法。僅考慮排序的對(duì)象為整數(shù)的情況。 6. 計(jì)算 a 的 n 次方是許多加密算法的基本操作,蠻力計(jì)算方法的時(shí)間復(fù)雜

13、度 是 0(n)，請(qǐng)?jiān)O(shè)計(jì)一個(gè)時(shí)間復(fù)雜度小于 0(n)的算法，(假設(shè)計(jì)算結(jié)果可以使用 long 型存儲(chǔ)) 7給定一個(gè)數(shù)組 a n，我們希望構(gòu)造數(shù)組 bn，其中 bi = a0*a1.a n- 1/ai. 在構(gòu)造過(guò)程不允許使用除法 1要求 0（1）空間復(fù)雜度和 0（n）時(shí)間復(fù)雜度。 2 .除遍歷計(jì)數(shù)器與 anbn 外，不可使用新的變量（包括棧臨時(shí)變量，堆空 間和全局靜態(tài)變量等）； 8. 給定一個(gè)如下輸入格式的字符串， （ 1， （2,3） ，（4，（5,6），7）括 號(hào)內(nèi)的元素可以是數(shù)字，也可以是另一個(gè)括號(hào)。請(qǐng)實(shí)現(xiàn)一個(gè)算法消除嵌套的括 號(hào)， 比如把上面的表達(dá)式變成：（ 1,2,3,4,5,6,7）

14、，如果表達(dá)式有誤請(qǐng)報(bào)錯(cuò)。 9. 相似度計(jì)算用于衡量對(duì)象之間的相似程度，在數(shù)據(jù)挖掘，自然語(yǔ)言處理中 是一個(gè)基礎(chǔ)性計(jì)算。在廣告檢索服務(wù)中往往也會(huì)判斷網(wǎng)民檢索 Query 和廣告 Adword 的 主題相似度。假設(shè) Query或者 Adword 的主題屬性定義為一個(gè)長(zhǎng)度為 10000 的浮點(diǎn)數(shù)組 Pr10000 （稱之為主題概率數(shù)組），其中 Pri表示 Query或者 Adword 屬于主 題 ID 為 i 的概率，而 Query 和 Adword 的相似度簡(jiǎn)化定義為兩者主題概率 數(shù)組的內(nèi)積：即 sim（Query,Adword） = sum（QueryPri*AdwordPri） （0二i=100

15、00。在 實(shí)際應(yīng)用場(chǎng)景中，由于大多數(shù)主題概率都為 0，所以主題概率數(shù)組往往比較 稀疏，在實(shí)現(xiàn)時(shí)會(huì)以一個(gè)緊湊型數(shù)組 topic_info_t 的方式保存，其中 100=數(shù)組 大小 =1000,并按照 topic_id 遞增排列， 0=topic_id10000,0topic_pr=5000)個(gè) Adwords 的 topic_info_t 數(shù)組，現(xiàn)要求出 Query 與 Adwords 的相似度最大值。即 max(sim(Query,Adwordi) (0=iN). float max_sim(const vector&query_topic_info, const vectoradwords_

16、topic_info, int adwords_number); 編寫(xiě)代碼求時(shí)間復(fù)雜度最低的算法，并給出時(shí)間復(fù)雜度分析。 10. 給一個(gè)單詞 a,如果通過(guò)交換單詞中字母的順序可以得到另外的單詞 b, 那么 b 是 a 的兄弟單詞，比如單詞 army 和 mary 互為兄弟單詞。 現(xiàn)在要給出一種解決方案,對(duì)于用戶輸入的單詞,根據(jù)給定的字典找出輸 入單詞有哪些兄弟單詞。請(qǐng)具體說(shuō)明數(shù)據(jù)結(jié)構(gòu)和查詢流程,要求時(shí)間和空間效 率盡可能 的高 11. 系統(tǒng)中維護(hù)了若干數(shù)據(jù)項(xiàng),我們對(duì)數(shù)據(jù)項(xiàng)的分類可以分為三級(jí),首先我 們按照一級(jí)分類方法將數(shù)據(jù)項(xiàng)分為 A, B, C若干類別，每一個(gè)級(jí)分類方法產(chǎn) 生的類 別又可以按照

17、二級(jí)分類方法分為 a,b,c 若干子類別，同樣，二級(jí)分類方法 產(chǎn)生的類別又可按照三級(jí)分類方法分為 i,ii,iii 若干子類別,每個(gè)三級(jí)分類方法 產(chǎn)生 的子類別中的數(shù)據(jù)項(xiàng)從 1 開(kāi)始的編號(hào)。我們需要對(duì)每個(gè)數(shù)據(jù)項(xiàng)輸出日志, 日志的形式是 key-value。寫(xiě)入日志的時(shí)候，用戶提供三級(jí)類別名稱，數(shù)據(jù)項(xiàng)編 號(hào)和日 志的key,共五個(gè)key值， 例如 write(A,a,i,1,key1)，獲取日志的時(shí)候，用戶 提供三級(jí)類別名稱,數(shù)據(jù)項(xiàng)編號(hào),共四個(gè) key 值,返回對(duì)應(yīng)的所有 key-value, 例如 get_log（A,a,i,1）,請(qǐng)描述一種數(shù)據(jù)結(jié)構(gòu)來(lái)存儲(chǔ)這些日志，并計(jì)算出寫(xiě)入 日志和讀出日志

18、的時(shí)間復(fù)雜度 12. 鏈表 struct student in t m_Num;泡排序（寫(xiě)出具體算法）：答題需注意程序的有效性，可行 性，健壯性并體現(xiàn)嚴(yán)格，規(guī)范的過(guò)程。 14. 單鏈表反序（寫(xiě)出具體算法）：答題需注意程序的有效性，可行性，健 壯性并體現(xiàn)嚴(yán)格，規(guī)范的過(guò)程。 15. 請(qǐng)寫(xiě)一個(gè)函數(shù)，功能是把一段字符串倒序：答題需注意程序的有效性， 可行性，健壯性并體現(xiàn)嚴(yán)格，規(guī)范的過(guò)程。 16. 設(shè)計(jì)一個(gè)算法，把一個(gè)含有 N 個(gè)元素的數(shù)組循環(huán)右移 K 位，要求時(shí)間復(fù) 雜度為 O（ N） ,空間復(fù)雜度為 O（ 1）。 17. 一個(gè)單向鏈表，不知道頭結(jié)點(diǎn)，一個(gè)指針指向其中一個(gè)節(jié)點(diǎn)，問(wèn)如何刪 除這個(gè)指針指向的結(jié)點(diǎn) . 18. 編程得到以下算式的結(jié)果 （要求計(jì)算的效率最高） 算式： 1-2+3-4+5-6 . N 19. 請(qǐng)寫(xiě)出一個(gè)程序， 把一段字符串里面的某個(gè)字符（可能出現(xiàn)幾次）過(guò)濾 掉，比如“ abcdefg 過(guò)濾掉e 變成“ abcdfg” 要求算法復(fù)雜度 0（n）,空間復(fù)雜度 0（1） （10）。 20. 編寫(xiě)一個(gè)按單詞反轉(zhuǎn)字符串的函數(shù)， 如給定輸入 here is 后變成 is here 21. 列出你知道的排序算法,并使用其中的任意一種排序算法實(shí)現(xiàn) int