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

1、數(shù)據(jù)結(jié)構(gòu)1.采用折半搜索算法長度為n的有序表時，元素的平均搜索長度為（）A)O(n2) B)O(nlog2n) C)O(log2n) D)O(n)2.下面程序的時間復(fù)雜度為（）for(int i=0;i<m;i+)for(int j=0;j<n;j+)aij = i * j; A)O(m2); B)O(n2); C)O(m*n); D)O(m+n);3.下列敘述中，正確的是（）A)線性表中的個元素在存儲空間中的位置必須是連續(xù)的B)線性表中的表頭元素一定存儲在其他元素的前面C)線性表中的個元素在存儲空間中的位置不一定是連續(xù)的，但表頭元素一定存儲在其他元素的前面D)線性表中的個元素在存

2、儲空間中的位置不一定是連續(xù)的，且各元素的存儲順序也是任意的4.已知二叉樹后序遍歷序列是edcfba，中序遍歷序列deacbf，它的前序遍歷序列是（）;5.如果進(jìn)棧序列為 e1,e2,e3,e4 ，則可能的出棧序列是（）;6.對長度為n的字符串進(jìn)行字符定位運算的時間復(fù)雜度為（）;A)O(1) B)O(根號n) C)O(nlog2n) D)O(n)7.n個頂點的連通圖中邊得條數(shù)至少為（）8.合并兩個已經(jīng)排好序的長度為n的Array<int>,最壞情況下需要比較多少次（）A)2n B)2n-1 C)2n+1 D)n29.深度為5的滿二叉樹中，葉子結(jié)點的個數(shù)為（）A)32 B)31 C)1

3、6 D)1510.冒泡排序算法和快速排序算法的時間復(fù)雜度分別是什么？11.請簡述數(shù)組和鏈表數(shù)據(jù)結(jié)構(gòu)的特點及應(yīng)用的場合？12.下列哪些數(shù)據(jù)結(jié)構(gòu)最適合醫(yī)療儀器設(shè)備中的大型數(shù)據(jù)量的插入，查找（）A)數(shù)組 B)哈希表 C)紅黑樹/二叉平衡樹 D)鏈表13.下列哪些排序算法的平均時間復(fù)雜度是O(nlog2n)（），哪些是穩(wěn)定的排序（）A)冒泡排序 B)希爾排序 C)快速排序 D)插入排序 E)堆排序14.下列哪些說法是正確的：（）A)二分查找法在一個長度為1000的有序整數(shù)數(shù)組查找一個整數(shù)，比較的次數(shù)不超過100次B)在二叉樹中查找元素的時間復(fù)雜度為O(log2n)；C)對單向鏈表，可以使用冒泡排序；D

4、)對雙向鏈表，可以使用快速排序；15.已知某二叉樹的后序遍歷是DFBEGCA，中序遍歷的順序是DBFACEG，其前序遍歷順序是_16.下列代碼將兩個有序鏈表結(jié)合為一個，鏈表中的元素的排列順序為從小到大。請補充其中的空缺。struct nodestruct node *pnext;int val;struct node* splice(struct node* plhs,struct node* prsh)if(_)return prhs?prhs:plhs;struct node* phead,*plast;if(_)phead = plast = prhs;plhs = plhs->p

5、next;elsephead = plast = plhs;prhs = prhs->pnext;while(_)if(plhs->val < prhs->val)plast->pnext = plhs;plast = plhs;plhs = plhs->pnext;elseplast->pnext = prhs;plast = prhs;prhs = prhs->pnext;plast->pnest = _;return _;17. 比較哈希表和平衡二叉樹的特點，他們分別用在哪些場合.18.一個棧的入棧序列是 A,B,C,D,E 則棧的不

6、可能的輸出序列是（）A) EDCBA B)DECBA C)DCEAB D)ABCDE19.在排序的方法中，關(guān)鍵碼比較次數(shù)與記錄地初始排列無關(guān)的是（）A) Shell B)歸并排序 C)直接排序 D)選擇排序 20.以下反向遍歷array數(shù)組的方法有什么錯誤？vector array;array.push_back(1);array.push_back(2);array.push_back(3);for(vector:size_type i=array.size()-1;i>=0;-i)cout << arrayi << endl;21.某火車站要通過一條棧道（先進(jìn)

7、后出）來調(diào)換進(jìn)入車站的列車順序，若進(jìn)站的列車順序為A，B，C，則下列哪個出棧順序不可能？A)ABC B)ACB C)CAB D)CBA22.棧是一種是自能在某一端插入和刪除的特殊線性表。他按照后進(jìn)先出的原則存儲數(shù)據(jù)，先進(jìn)入的數(shù)據(jù)被壓入棧底，最后進(jìn)入的數(shù)據(jù)在棧頂，若6元素進(jìn)入棧S的順序為 A.B.C.D.E.F 出棧順序為B.D.C.F.E.A,則S棧最小容量為？A) 3 B) 4 C) 5 D) 624.若完全二叉樹的結(jié)點個數(shù)為2的N次方-1，則葉子結(jié)點個數(shù)為：A) N-1 B)2*N C)2（N-1）次方 D) 2N次方25.排序算法是穩(wěn)定是指：關(guān)鍵碼相同的記錄排序前后對應(yīng)位置不發(fā)生改變，下

8、面哪種排序算法是不穩(wěn)定的？A)插入排序 B)冒泡排序 C)快速排序 D)歸并排序26.下列說法中錯誤的是：A)插入排序某些情況下復(fù)雜度為O(N)。B)排序二叉樹元素查找的復(fù)雜度可能為O(N).C)對于有序列表的排序最快的是快速排序。D)在有序列表中通過二分查找的復(fù)雜度一定是O(nlog2n)。27.棧和隊列的共同特點是（ ）28.棧通常采用的兩種存儲結(jié)構(gòu)是（ ）29.下列關(guān)于棧的敘述正確的是（ ）A)棧是非線性結(jié)構(gòu) B)棧是一種樹狀結(jié)構(gòu)C)棧具有先進(jìn)先出的特征 D)棧有后進(jìn)先出的特征30.鏈表不具有的特點是（ ）A)不必事先估計存儲空間 B)可隨機(jī)訪問任一元素C)插入刪除不需要移動元素 D)所

9、需空間與線性表長度成正比31.用鏈表表示線性表的優(yōu)點是（ ）32.循環(huán)鏈表的主要優(yōu)點是（ ）33.線性表L（a1,a2,a3,ai,an），下列說法正確的是（ ）A)每個元素都有一個直接前件和直接后件B)線性表中至少要有一個元素C)表中諸元素的排列順序必須是由小到大或由大到小D)除第一個和最后一個元素外，其余每個元素都有一個且只有一個直接前件和直接后件34.線性表若采用鏈?zhǔn)酱鎯Y(jié)構(gòu)時，要求內(nèi)存中可用存儲單元的地址（ ）A)必須是連續(xù)的 B)部分地址必須是連續(xù)的C)一定是不連續(xù)的 D)連續(xù)不連續(xù)都可以35.樹是結(jié)點的集合，它的根結(jié)點數(shù)目是（ ）36.在深度為5的滿二叉樹中，結(jié)點的個數(shù)為（ ）37

10、.具有3個結(jié)點的二叉樹有（ ）種形態(tài)38.設(shè)一棵二叉樹中有3個葉子結(jié)點，有8個度為1的結(jié)點，則該二叉樹中總的結(jié)點數(shù)為（ ） 39. 算法一般都可以用哪幾種控制結(jié)構(gòu)組合而成（ ） 40. 下列敘述正確的是（ ）A)算法的執(zhí)行效率與數(shù)據(jù)的存儲結(jié)構(gòu)無關(guān)B)算法的空間復(fù)雜度是指算法程序中指令（或語句）的條數(shù)C)算法的有窮性是指算法必須能在執(zhí)行有限個步驟之后終止D)算法的時間復(fù)雜度是指執(zhí)行算法程序所需要的時間41. 數(shù)據(jù)結(jié)構(gòu)作為計算機(jī)的一門學(xué)科，主要研究數(shù)據(jù)的邏輯結(jié)構(gòu)、對各種數(shù)據(jù)結(jié)構(gòu)進(jìn)行的運算，以及（ ）42. 下列敘述中，錯誤的是（ ）A)數(shù)據(jù)的存儲結(jié)構(gòu)與數(shù)據(jù)處理的效率密切相關(guān)B)數(shù)據(jù)的存儲結(jié)構(gòu)與數(shù)據(jù)

11、處理的效率無關(guān)C)數(shù)據(jù)的存儲結(jié)構(gòu)在計算機(jī)中所占的空間不一定是連續(xù)的D)一種數(shù)據(jù)的邏輯結(jié)構(gòu)可以有多種存儲結(jié)構(gòu)46. 根據(jù)數(shù)據(jù)結(jié)構(gòu)中各數(shù)據(jù)元素之間前后件關(guān)系的復(fù)雜程度，一般將數(shù)據(jù)結(jié)構(gòu)分為（ ）43. 下列數(shù)據(jù)結(jié)構(gòu)中，按先進(jìn)后出原則組織數(shù)據(jù)的是（ ）A)線性鏈表 B)棧 C)循環(huán)鏈表 D)順序表44. 下列關(guān)于棧的敘述中正確的是（ ）A)在棧中只能插入數(shù)據(jù) B)在棧中只能刪除數(shù)據(jù)C)棧是先進(jìn)先出的線性表 D)棧是先進(jìn)后出的線性表45. 應(yīng)用程序在執(zhí)行過程中，需要通過打印機(jī)輸出數(shù)據(jù)時，一般先形成一個打印作業(yè)，將其存放在硬盤中的一個指定（ ）中，當(dāng)打印機(jī)空閑時，就會按先來先服務(wù)的方式從中取出待打印的作業(yè)

12、進(jìn)行打印。46.下列關(guān)于隊列的敘述中正確的是（ ）A)在隊列中只能插入數(shù)據(jù) B)在隊列中只能刪除數(shù)據(jù) C)隊列是先進(jìn)先出的線性表 D)隊列是先進(jìn)后出的線性表47.有一個C語言用來刪除單鏈表的頭元素的函數(shù)，請找出其中的問題并加以糾正。 void RemoveHead(node* head) free(head) head=head->next48.設(shè)單鏈表中節(jié)點的結(jié)構(gòu)為： typedef struct nodeElemtype data; /數(shù)據(jù)struct node* Link; /節(jié)點后繼指針Listnode;（1）已知指針p所指節(jié)點不是尾節(jié)點，若在*p之后插入節(jié)點*s，則應(yīng)執(zhí)行下列哪

13、一個操作？A)s->link=p;p->link=s; B) s->link=p->link;p->link=s;C)s->link=p->link;p=s; D) p->link=s;s->link=p; (2) 非空的循環(huán)單鏈表 first 的尾節(jié)點（由p所指向）滿足：A) p->link=NULL; B) p=NULL;C) p->link=first; D) p=first;49.如何證明一個表是循環(huán)鏈表？52.如果一棵二叉樹節(jié)點的前序序列是 A、B、C，后序序列是C、B、A，則該二叉樹節(jié)點的中序序列是什么？ A) 必為

14、ABC B) 必為ACB C) 必為BCA D) 不能確定 53.什么是平衡二叉樹？54.下面的程序是一快速排序問題，請?zhí)羁铡?#include <iostream>#include <stdio.h>void improveqsort(int *list,int m,int n)int k,t,i,j; /*for (i=0;i<10;i+)printf("%3d",listi);*/if(m<n)i=m;j=n+1;k=listm;while(i<j)for(i=i+1,i<n.i+)if(listi>=k)brea

15、k;for(j=j-1,j>m,j-)if(listj<=k)break;if(i<j)t=listi;listi=listj;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;i<10;i+)scanf("%d",&listi);printf("n");improveqsort(lis

16、t,m,n);for(i=0;i<10;i+)printf("%5d",listi);printf("n");55.以下哪種排序?qū)儆诜€(wěn)定排序？ A) 歸并排序 B) 快速排序 C) 希爾排序 D) 堆排序56.用二分法查找一個長度為10的、排好序的線性表，查找不成功時，最多需要比較多少次？ A) 5 B) 2 C) 4 D) 1 57.下面那種排序法對 1234567 最快？ A) quick sort B) bubble sort C) merge sort58.解釋一下什么是哈夫曼編碼問題？59.假設(shè)執(zhí)行語句Q的時間是O（1），則執(zhí)行下列程序段

17、的時間為（）for(int i = 1;i <= n;i+)for(int j = i; j <= n; j+)Q;A.O(n) B.O(n2) C.O(n*i) D.O(n+1)61. 一棵有124個葉結(jié)點的完全二叉樹，最多有（）個結(jié)點A247 B.248 C.249D.25063.下列排序算法中，在待排序數(shù)據(jù)有序的情況下，花費時間最多的是（）A快速排序B.希爾排序C.冒泡排序D.堆排序64.有1000個無序的整數(shù)，希望使用最快的方式找出前50個最大的，最佳的選擇是（）A.冒泡排序B.基數(shù)排序C.堆排序D.快速排序65.下列哪個不是用來解決哈希表沖突的開放地址法（）A.線性探測法

18、B.線性補償探測法C.拉鏈探測法 D.隨機(jī)探測法66.假設(shè)把整數(shù)關(guān)鍵碼K散列到有N個槽的散列表，以下哪些散列函數(shù)是好的散列函數(shù)_。Ah(k)= k/N; Bh(k)=1; Ch(k)=k mod N; Dh(k)=(k + Random(N)mod N,random(N)返回一個0到N-1的整數(shù)68.下面算法的時間復(fù)雜度是_.int f(unsigned int n) if(n=0|n=1) return 1; else return n*f(n-1);A.O(1) B.O(n) C.O(n2) D.O(n!)69. 對于一個具有n個頂點的無向圖，若采用鄰接表表示，則存放表頭節(jié)點的數(shù)組大小為A

19、.n B.n+1 C.n-1 D.n+邊數(shù)70.考慮一個特殊的hash函數(shù)h,能將任一字符串hash成一個整數(shù)k，其概率為P(k)=2(-k)。k=1,2。對一個位未知大小的字符串集合S中的每一個元素取hash值所組成的集合為h(S)。若h(S)中最大的元素max h(S)=10，那么S的大小的期望是_.A.5 B.10 C.512 D.102471.對于順序存儲的線性數(shù)組，訪問結(jié)點和增加，刪除結(jié)點的時間復(fù)雜度為_.A.O(n),O(n) B.O(n),O(1) C.O(1),O(n)D.O(1),O(1)75.遞歸式的先序遍歷一個n節(jié)點，深度為d的二叉樹，需要?？臻g的大小為_.A.O(n)

20、B.O(d) C.O(logn) D.(nlogn)76.關(guān)于排序算法的以下說法，錯誤的是_A.快速排序的平均時間復(fù)雜度為O(nlogn)，最壞的時間復(fù)雜度為O(n2)B. 堆排序的平均時間復(fù)雜度為O(nlogn)，最壞的時間復(fù)雜度為O(nlogn)C. 冒泡排序的平均時間復(fù)雜度為O(n2)，最壞的時間復(fù)雜度為O(n2)D. 歸并排序的平均時間復(fù)雜度為O(nlogn)，最壞的時間復(fù)雜度為O(n2)77. 某二叉樹的前序遍歷序列為-+a*b-cd/ef，后序遍歷序列為abcd-*+ef/-，問其中序遍歷序列是_.78.某緩存系統(tǒng)采用LRU淘汰算法，假定緩存容量為4，并且初始為空，那么在順序訪問以

21、下數(shù)據(jù)項的時候1,5,1,3,5,2,4,1,2出現(xiàn)緩存直接命中的次數(shù)是_,最后緩存中即將準(zhǔn)備淘汰的數(shù)據(jù)項是_.79.有兩個較長的單向鏈表a和b，為了找出結(jié)點node滿足node in a并且node in b。請設(shè)計空間使用盡量小的算法。80. 當(dāng)存儲數(shù)據(jù)量超出單節(jié)點數(shù)據(jù)管理能力的時候，可以采取的辦法有數(shù)據(jù)庫sharding的解決方案，也就是按照一定規(guī)律把數(shù)據(jù)分散存儲在多個數(shù)據(jù)管理結(jié)點N中（節(jié)點編號為0,1,2N-1）.假設(shè)存儲的數(shù)據(jù)是a，請完成為數(shù)據(jù)a計算存儲節(jié)點的程序。#define N 5int hash(int element)return element *2654435761;i

22、nt shardingIndex(int a)int p=hash(a);_return p;82.具有100個結(jié)點的二叉樹中，若用二叉鏈表存儲，其指針域部分用來指向結(jié)點的左右孩子，其余_個指針域為空A.50 B.99 C.100 D.10183.請實現(xiàn)一個快速排序算法，僅考慮被排序?qū)ο鬄檎麛?shù)的情況。84. 一顆二叉樹高度為h，所有節(jié)點的度或為0，或為2，則這顆二叉樹最少有（）結(jié)點A.2h B.2h-1 C.2h+1 D.h+185.在百度或淘寶搜索時，每鍵入字符都會出現(xiàn)搜索建議，實現(xiàn)這類技術(shù)后臺采用的數(shù)據(jù)結(jié)構(gòu)是_.86.設(shè)哈弗曼樹中的葉子結(jié)點總數(shù)為m，若用二叉鏈表作為存儲結(jié)構(gòu)，則該哈弗曼樹中

23、總共有（）個空指針域：A.2m-1 B.2m C.2m+1 D.4m87.后綴式ab+cd+/可用下面哪個表達(dá)式來表示:A.a+b/c+d B.a+b/(c+d) C.a+b+c/d D.(a+b)/(c+d)88.給定一個數(shù)組 11 3 15 7 6 2 13 9 19 4，每次操作可以交換不含重復(fù)數(shù)字的多對數(shù)，求至少需要多少次操作才能使數(shù)組遞增有序，比如交換（11,3）（15,7）（6,2）只算一次操作，而交換（11,3），（3,2）算兩次操作A.6 B.5 C.2 D.389.寫一個函數(shù)，去除一個字符串中的所有重復(fù)字符，要求在原字符串上進(jìn)行操作，不可以使用庫函數(shù)，空間復(fù)雜度O（1）。例如

24、：輸入字符串為”aabbbca“，則去重后的字符串為”abc“90.如何判斷一個二叉樹是不是對稱二叉樹。（對稱必須是左右子樹對稱，且對應(yīng)節(jié)點的值也相同）91.某個車站呈狹長型，寬度只能容下一臺車，并且只有一個出入口，已知某時刻該車站狀態(tài)為空，從這一時刻開始的出入記錄為：“進(jìn)，出，進(jìn)，進(jìn)，進(jìn)，出，出，進(jìn)，進(jìn)，進(jìn)，出，出”假設(shè)該車輛入棧的順序為1,2,3，則車輛的出棧順序為（）A1,2,3,4,5 B1,2,4,5,7 C1,4,3,7,6 D1,4,3,7,292.將數(shù)組8,23,4,16,77，-5,53,100中的元素按從小到大的順序排列，每次可以交換任意兩個元素，最少需要交換（）次A. 4

25、 B. 5 C. 6 D. 794.完全二叉樹和滿二叉樹的聯(lián)系和區(qū)別？95.以下序列中不符合堆定義的是（）A（102，87，100,79,82,62,84,42,22,12,68）B(102,100,87,84,82,79,68,62,42,22,12)C（12,22,42,62,68,79,82,84,87,100,102）D（102,87,42,79,82,62,68,100,84,12,22）96.使用cache命中率最高的替換算法是（）A先進(jìn)先出算法FIFO B隨機(jī)算法RANDC先進(jìn)后出算法FILO D替換最近最少使用的塊算法LRU97. 快速排序最壞情況下的時間復(fù)雜度是：( )A.

26、O( nlog(n) B. O(n2) C. O(log(n) D. O(n)98.一個文本文件，大約有10000行，每行一個詞，要求統(tǒng)計出其中最頻繁出現(xiàn)的前十個詞（le表示單詞的平均長度）,給出時間復(fù)雜度分析。（）A.max(O(n*le),O(n*lg10)B.min(O(n*le),O(n*lg10)C.O(n*le)D.O(n*lg10)99. 關(guān)于數(shù)據(jù)結(jié)構(gòu)和算法，以下說法正確的是（）A. 數(shù)據(jù)的邏輯結(jié)構(gòu)與所使用的計算機(jī)無關(guān)B. 數(shù)據(jù)的存儲結(jié)構(gòu)與數(shù)據(jù)處理的效率密切相關(guān)C. 數(shù)據(jù)的存儲結(jié)構(gòu)在計算機(jī)中所占的空間不一定是連續(xù)的D. 一種數(shù)據(jù)的邏輯結(jié)構(gòu)只對應(yīng)一種存儲結(jié)構(gòu)E. 算法的執(zhí)行效率與數(shù)

27、據(jù)的存儲結(jié)構(gòu)無關(guān)F. 算法的時間復(fù)雜度是指執(zhí)行算法程序所需要的時間G. 在單鏈表中，只要指出表中任何一個節(jié)點的位置，就可以從他出發(fā)依次訪問到鏈表中其他所有節(jié)點H. 在一個單鏈表中，已知q所指結(jié)點是p所指節(jié)點的前驅(qū)結(jié)點，若在p和q之間插入結(jié)點s，則執(zhí)行，s->next=p;q->next =s;I. 在一個單鏈表中，若刪除p所指節(jié)點的后續(xù)結(jié)點，則執(zhí)行p=p->next;p->next=p->next->nextJ. 使用鏈表，可隨機(jī)訪問鏈表中的任何一個元素100.調(diào)用printf函數(shù)可以分解為九個過程，請寫出他們的排列順序_.A.call指令 B.EBP出棧

28、C.函數(shù)參數(shù)壓棧 D.收回局部變量空間 E.EBP壓棧F.在棧上保留局部變量 G.函數(shù)參數(shù)出棧 H.ret指令 I.打印輸出字符串102.在以下幾種數(shù)據(jù)結(jié)構(gòu)中，在執(zhí)行數(shù)量相當(dāng)?shù)牟檎?，刪除和插入操作時，綜合性能最好的數(shù)據(jù)結(jié)構(gòu)是：A. 雙向鏈表 B. 分塊鏈表 C. 穿線二叉樹 D. 堆103. 廣告系統(tǒng)為了做地理位置定向，將IPV4分割為627672個區(qū)間，并標(biāo)識了地理位置信息，區(qū)間之間無重疊，用二分查找將IP地址映射到地理位置信息，請問在最壞的情況下，需要查找多少步？A17 B18 C19 D20104.以入棧順序作為輸入，出棧作為輸出，并以I代表入棧，O代表出棧，現(xiàn)將1,2,3,4順序入棧，

29、則棧操作序列IIIIOOOO后，輸出4321；與輸出1234相對應(yīng)的棧操作序列為IOIOIOIO.則若想得到輸出為2314，則棧操作序列應(yīng)為_.無法由棧操作序列而得到的輸出有_。105. 設(shè)一組初始記錄關(guān)鍵字序列為（20,18,22,16,30,19），則根據(jù)這些初始關(guān)鍵字序列建成的初始堆為_.106.線性有序表（a1,a2,a3,.a256）是從小到大排列的，對一個給定的值k，用二分法檢索表中與K相等的元素，在查找不成功的情況下，最多需要檢索_次。編程1 單鏈表1：編程實現(xiàn)一個單鏈表的建立。2：編程實現(xiàn)一個單鏈表的側(cè)長。3：編程實現(xiàn)一個單鏈表的打印。4：編程實現(xiàn)一個單鏈表刪除節(jié)點。5：編程實

30、現(xiàn)單鏈表的插入。6：編程實現(xiàn)單鏈表的逆置。2 雙鏈表1：編程實現(xiàn)雙鏈表的建立。2：編程實現(xiàn)雙鏈表的側(cè)長。3：編程實現(xiàn)雙鏈表的打印。4：編程實現(xiàn)雙鏈表刪除節(jié)點。5：編程實現(xiàn)雙鏈表的插入。1：編程實現(xiàn)隊列的入隊。2：編程實現(xiàn)隊列的出隊。3：編程實現(xiàn)隊列的側(cè)長。4：編程實現(xiàn)隊列的打印。1. 一個學(xué)生的信息：姓名，學(xué)號，性別，年齡等信息，用一個鏈表，把這些學(xué)生信息連在一起，給出一個age，在這些鏈表中刪除學(xué)生年齡等于age的學(xué)生信息。2. 請用C或 C+ 寫出一個冒泡排序程序，要求輸入10個整數(shù)，輸出排序結(jié)果。3. 請用C或 C+ 寫出一個shell排序程序，要求輸入10個整數(shù)，輸出排序結(jié)果。4. 鏈

31、表struct studentint m_Num; /學(xué)號double m_dScore; /分?jǐn)?shù)struct student* m_pNext; /下一個1).構(gòu)造一個有20名學(xué)生的單向鏈表。按順序每名學(xué)生的分?jǐn)?shù)值為，1,2,3,5,8,13.2).求出他們的平均分。5. 請實現(xiàn)一個快速排序的算法。僅考慮排序的對象為整數(shù)的情況。6. 計算a的n次方是許多加密算法的基本操作，蠻力計算方法的時間復(fù)雜度是O(n)，請設(shè)計一個時間復(fù)雜度小于O(n)的算法，(假設(shè)計算結(jié)果可以使用long型存儲)7.給定一個數(shù)組an，我們希望構(gòu)造數(shù)組bn，其中 bi = a0*a1.an-1/ai.在構(gòu)造過程不允許使用

32、除法。1.要求O(1)空間復(fù)雜度和O(n)時間復(fù)雜度。2.除遍歷計數(shù)器與anbn外，不可使用新的變量（包括棧臨時變量，堆空間和全局靜態(tài)變量等）；8.給定一個如下輸入格式的字符串，（1，（2,3），（4，（5,6），7）括號內(nèi)的元素可以是數(shù)字，也可以是另一個括號。請實現(xiàn)一個算法消除嵌套的括號，比如把上面的表達(dá)式變成：（1,2,3,4,5,6,7），如果表達(dá)式有誤請報錯。9.相似度計算用于衡量對象之間的相似程度，在數(shù)據(jù)挖掘，自然語言處理中是一個基礎(chǔ)性計算。在廣告檢索服務(wù)中往往也會判斷網(wǎng)民檢索Query和廣告Adword的主題相似度。假設(shè)Query或者Adword的主題屬性定義為一個長度為10000

33、的浮點數(shù)組Pr10000（稱之為主題概率數(shù)組），其中Pri表示Query或者Adword屬于主題ID為i的概率，而Query和Adword 的相似度簡化定義為兩者主題概率數(shù)組的內(nèi)積：即sim(Query,Adword) = sum(QueryPri*AdwordPri) (0<=i<=10000)。在實際應(yīng)用場景中，由于大多數(shù)主題概率都為0，所以主題概率數(shù)組往往比較稀疏，在實現(xiàn)時會以一個緊湊型數(shù)組topic_info_t的方式保存，其中100<=數(shù)組大小<=1000,并按照topic_id遞增排列，0<=topic_id<10000,0<topic_p

34、r<1。struct topic_info_tint topic_id;float topic_pr;現(xiàn)在給出Query的topic_info_t數(shù)組和N（N>=5000）個Adwords的topic_info_t數(shù)組，現(xiàn)要求出Query與Adwords的相似度最大值。即max(sim(Query,Adwordi)(0<=i<N).float max_sim(const vector<topic_info_t>&query_topic_info,const vector<topic_info_t>adwords_topic_info,in

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

36、三級分類方法分為i,ii,iii若干子類別，每個三級分類方法產(chǎn)生的子類別中的數(shù)據(jù)項從1開始的編號。我們需要對每個數(shù)據(jù)項輸出日志，日志的形式是key-value。寫入日志的時候，用戶提供三級類別名稱，數(shù)據(jù)項編號和日志的key，共五個key值，例如write(A,a,i,1,key1)，獲取日志的時候，用戶提供三級類別名稱，數(shù)據(jù)項編號，共四個key值，返回對應(yīng)的所有key-value，例如get_log(A,a,i,1)，請描述一種數(shù)據(jù)結(jié)構(gòu)來存儲這些日志，并計算出寫入日志和讀出日志的時間復(fù)雜度？12.鏈表struct student int m_Num;/學(xué)號double m_dScore;/分?jǐn)?shù)

37、struct student *m_pNext;/下一個;1）構(gòu)造一個有20名學(xué)生的單向鏈表。按順序每名學(xué)生的分?jǐn)?shù)值為1,1,2,3,5,8,132）求出他們的平均分13.冒泡排序（寫出具體算法）：答題需注意程序的有效性，可行性，健壯性并體現(xiàn)嚴(yán)格，規(guī)范的過程。14.單鏈表反序（寫出具體算法）：答題需注意程序的有效性，可行性，健壯性并體現(xiàn)嚴(yán)格，規(guī)范的過程。15.請寫一個函數(shù)，功能是把一段字符串倒序：答題需注意程序的有效性，可行性，健壯性并體現(xiàn)嚴(yán)格，規(guī)范的過程。16.設(shè)計一個算法，把一個含有N個元素的數(shù)組循環(huán)右移K位，要求時間復(fù)雜度為O（N）,空間復(fù)雜度為O（1）。17.一個單向鏈表，不知道頭結(jié)點

38、，一個指針指向其中一個節(jié)點，問如何刪除這個指針指向的結(jié)點.18.編程得到以下算式的結(jié)果（要求計算的效率最高） 算式：1-2+3-4+5-6.N19.請寫出一個程序，把一段字符串里面的某個字符（可能出現(xiàn)幾次）過濾掉，比如“abcdefg”過濾掉e變成“abcdfg”。要求算法復(fù)雜度O(n)，空間復(fù)雜度O(1)(10)。20.編寫一個按單詞反轉(zhuǎn)字符串的函數(shù)，如給定輸入 here is 后變成 is here21.列出你知道的排序算法，并使用其中的任意一種排序算法實現(xiàn)int *sort(int array,int length),array是一個待排整形數(shù)組，length是數(shù)組長度，將排序結(jié)果以整型

39、指針的形式輸出。22. 編寫一個函數(shù)，計算兩個正整數(shù)的最小公倍數(shù)，要求用輾轉(zhuǎn)相除法。23已知兩個鏈表List1和List2，均為增序，請把他們合并成一個鏈表，要求仍為增序，請用遞歸實現(xiàn)。24.編程求10000以內(nèi)的素數(shù)，要求對算法進(jìn)行適當(dāng)優(yōu)化。25.（八皇后問題）在一個8*8的國際象棋棋盤上擺放八個皇后，使其不能互相攻擊，即任意兩個皇后都不能處于同一行，同一列或同一斜線上。請編程求出所有可行的擺法，要求用回溯法寫出程序。26.給定一個單鏈表和一個整數(shù)K，要求每隔K個元素翻轉(zhuǎn)鏈表：struct nodeint key;struct node * next;typedef node *List;實

40、現(xiàn)該函數(shù)：int *kReverse(List *Head,int k)比如：原始鏈表為：1->2->3->4->5->6k=2翻轉(zhuǎn)為:2->1->4->3->6->5k=3翻轉(zhuǎn)為:3->2->1->6->5->4k=4翻轉(zhuǎn)為:4->3->2->1->5->627.對于一個m*n的int矩陣，其每行自左向右是升序排列的，其每列自上向下是升序排列的，現(xiàn)需要在其中查找整數(shù)elem，找到時返回elem所在位置。請1）先寫出思路；2）自行定義函數(shù)接口然后編程實現(xiàn)，編程語言不限。28.

41、下面程序段的時間復(fù)雜度為（）for(int i=0;i<m;i+)for(int j =0 ;j<n;j+)aij=i*j;AO(m2) BO(n2) CO(m*n) DO(m+n)29. 一個單向鏈表，不知道頭結(jié)點，現(xiàn)在有一個指針指向其中一個節(jié)點，問如何從鏈表中刪除這個指針指向的節(jié)點？例如：單向鏈表L（1->2->3->4->5）,現(xiàn)有指針P指向節(jié)點3，現(xiàn)在要刪除節(jié)點3，把鏈表L變成（1->2->4->5）30. 已知一顆二叉樹的中序序列和后序序列分別為BDCEAFHG和DECBHGFA，畫出這顆二叉樹.31.給定一個沒有重復(fù)數(shù)據(jù)的整數(shù)數(shù)

42、組，找出其中所有兩個數(shù)相加之和等于2013的整數(shù)對，并且打印出來。（請寫出你的思路，然后用代碼實現(xiàn)出來）32. 已知兩個集合A5，2，7，4，3，9，9 B5，3，1，9，2，6，2，寫一段代碼順序打印出這兩個集合中重復(fù)的元素。嘗試使你的代碼時間復(fù)雜度最優(yōu)，請在代碼之前寫出你的思路。33. 已知字母順序是d，g，c，f，b，e，a 請對輸入的一組字符串input3=“dca”，“dfa”，“cgd”,按照字母順序進(jìn)行排序并打印，本例的輸出為：1：dca2：dfa3：cgd如何檢測上述代碼是達(dá)到質(zhì)量標(biāo)準(zhǔn)的？34.create a function for string padStart(Stri

43、ng string,int minlength,char padChar);return a string,of length at least minlength,consisting of string prepended with as many copies of padChar as are necessary to reachthat length.for example :padStart (“7”,3,0)returns “007”padStart (“2010”,3,0)returns “2010”35.有一個數(shù)組，里面由若干整數(shù)組成，除了一個整數(shù)外，其他都出現(xiàn)兩次，如何快速找到這個整數(shù)。例如：【1，2,1,3,4,4,3】，輸出應(yīng)為2.36.給定兩個有序單鏈表，求這兩個單鏈表的交集鏈表，并維持交集依然有序。請給出代碼實現(xiàn)，自己定義數(shù)據(jù)結(jié)構(gòu)。如有鏈表：1->2->4->8和2->3->4-&g