筆試題數(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;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)線(xiàn)性表中的個(gè)元素在存儲(chǔ)空間中的位置必須是連續(xù)的B)線(xiàn)性表中的表頭元素一定存儲(chǔ)在其他元素的前面C)線(xiàn)性表中的個(gè)元素在存儲(chǔ)空間中的位置不一定是連續(xù)的，但表頭元素一定存儲(chǔ)在其他元素的前面D)線(xiàn)性表中的個(gè)元素在存

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

3、6 D)1510.冒泡排序算法和快速排序算法的時(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ī)療儀器設(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

4、)對(duì)雙向鏈表，可以使用快速排序；15.已知某二叉樹(shù)的后序遍歷是DFBEGCA，中序遍歷的順序是DBFACEG，其前序遍歷順序是_16.下列代碼將兩個(gè)有序鏈表結(jié)合為一個(gè)，鏈表中的元素的排列順序?yàn)閺男〉酱?。?qǐng)補(bǔ)充其中的空缺。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. 比較哈希表和平衡二叉樹(shù)的特點(diǎn)，他們分別用在哪些場(chǎng)合.18.一個(gè)棧的入棧序列是 A,B,C,D,E 則棧的不

6、可能的輸出序列是（）A) EDCBA B)DECBA C)DCEAB D)ABCDE19.在排序的方法中，關(guān)鍵碼比較次數(shù)與記錄地初始排列無(wú)關(guān)的是（）A) Shell B)歸并排序 C)直接排序 D)選擇排序 20.以下反向遍歷array數(shù)組的方法有什么錯(cuò)誤？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.某火車(chē)站要通過(guò)一條棧道（先進(jìn)

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

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

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

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

11、處理的效率無(wú)關(guān)C)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)在計(jì)算機(jī)中所占的空間不一定是連續(xù)的D)一種數(shù)據(jù)的邏輯結(jié)構(gòu)可以有多種存儲(chǔ)結(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)線(xiàn)性鏈表 B)棧 C)循環(huán)鏈表 D)順序表44. 下列關(guān)于棧的敘述中正確的是（ ）A)在棧中只能插入數(shù)據(jù) B)在棧中只能刪除數(shù)據(jù)C)棧是先進(jìn)先出的線(xiàn)性表 D)棧是先進(jìn)后出的線(xiàn)性表45. 應(yīng)用程序在執(zhí)行過(guò)程中，需要通過(guò)打印機(jī)輸出數(shù)據(jù)時(shí)，一般先形成一個(gè)打印作業(yè)，將其存放在硬盤(pán)中的一個(gè)指定（ ）中，當(dāng)打印機(jī)空閑時(shí)，就會(huì)按先來(lái)先服務(wù)的方式從中取出待打印的作業(yè)

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

13、一個(gè)操作？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é)點(diǎn)（由p所指向）滿(mǎn)足：A) p->link=NULL; B) p=NULL;C) p->link=first; D) p=first;49.如何證明一個(gè)表是循環(huán)鏈表？52.如果一棵二叉樹(shù)節(jié)點(diǎn)的前序序列是 A、B、C，后序序列是C、B、A，則該二叉樹(shù)節(jié)點(diǎn)的中序序列是什么？ A) 必為

14、ABC B) 必為ACB C) 必為BCA D) 不能確定 53.什么是平衡二叉樹(shù)？54.下面的程序是一快速排序問(wèn)題，請(qǐng)?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.用二分法查找一個(gè)長(zhǎng)度為10的、排好序的線(xiàn)性表，查找不成功時(shí)，最多需要比較多少次？ A) 5 B) 2 C) 4 D) 1 57.下面那種排序法對(duì) 1234567 最快？ A) quick sort B) bubble sort C) merge sort58.解釋一下什么是哈夫曼編碼問(wèn)題？59.假設(shè)執(zhí)行語(yǔ)句Q的時(shí)間是O（1），則執(zhí)行下列程序段

17、的時(shí)間為（）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個(gè)葉結(jié)點(diǎn)的完全二叉樹(shù)，最多有（）個(gè)結(jié)點(diǎn)A247 B.248 C.249D.25063.下列排序算法中，在待排序數(shù)據(jù)有序的情況下，花費(fèi)時(shí)間最多的是（）A快速排序B.希爾排序C.冒泡排序D.堆排序64.有1000個(gè)無(wú)序的整數(shù)，希望使用最快的方式找出前50個(gè)最大的，最佳的選擇是（）A.冒泡排序B.基數(shù)排序C.堆排序D.快速排序65.下列哪個(gè)不是用來(lái)解決哈希表沖突的開(kāi)放地址法（）A.線(xiàn)性探測(cè)法

18、B.線(xiàn)性補(bǔ)償探測(cè)法C.拉鏈探測(cè)法 D.隨機(jī)探測(cè)法66.假設(shè)把整數(shù)關(guān)鍵碼K散列到有N個(gè)槽的散列表，以下哪些散列函數(shù)是好的散列函數(shù)_。Ah(k)= k/N; Bh(k)=1; Ch(k)=k mod N; Dh(k)=(k + Random(N)mod N,random(N)返回一個(gè)0到N-1的整數(shù)68.下面算法的時(shí)間復(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. 對(duì)于一個(gè)具有n個(gè)頂點(diǎn)的無(wú)向圖，若采用鄰接表表示，則存放表頭節(jié)點(diǎn)的數(shù)組大小為A

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

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

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

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

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

24、：輸入字符串為”aabbbca“，則去重后的字符串為”abc“90.如何判斷一個(gè)二叉樹(shù)是不是對(duì)稱(chēng)二叉樹(shù)。（對(duì)稱(chēng)必須是左右子樹(shù)對(duì)稱(chēng)，且對(duì)應(yīng)節(jié)點(diǎn)的值也相同）91.某個(gè)車(chē)站呈狹長(zhǎng)型，寬度只能容下一臺(tái)車(chē)，并且只有一個(gè)出入口，已知某時(shí)刻該車(chē)站狀態(tài)為空，從這一時(shí)刻開(kāi)始的出入記錄為：“進(jìn)，出，進(jìn)，進(jìn)，進(jìn)，出，出，進(jìn)，進(jìn)，進(jìn)，出，出”假設(shè)該車(chē)輛入棧的順序?yàn)?,2,3，則車(chē)輛的出棧順序?yàn)椋ǎ〢1,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中的元素按從小到大的順序排列，每次可以交換任意兩個(gè)元素，最少需要交換（）次A. 4

25、 B. 5 C. 6 D. 794.完全二叉樹(shù)和滿(mǎn)二叉樹(shù)的聯(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. 快速排序最壞情況下的時(shí)間復(fù)雜度是：( )A.

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

27、據(jù)的存儲(chǔ)結(jié)構(gòu)無(wú)關(guān)F. 算法的時(shí)間復(fù)雜度是指執(zhí)行算法程序所需要的時(shí)間G. 在單鏈表中，只要指出表中任何一個(gè)節(jié)點(diǎn)的位置，就可以從他出發(fā)依次訪(fǎng)問(wèn)到鏈表中其他所有節(jié)點(diǎn)H. 在一個(gè)單鏈表中，已知q所指結(jié)點(diǎn)是p所指節(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，若在p和q之間插入結(jié)點(diǎn)s，則執(zhí)行，s->next=p;q->next =s;I. 在一個(gè)單鏈表中，若刪除p所指節(jié)點(diǎn)的后續(xù)結(jié)點(diǎn)，則執(zhí)行p=p->next;p->next=p->next->nextJ. 使用鏈表，可隨機(jī)訪(fǎng)問(wèn)鏈表中的任何一個(gè)元素100.調(diào)用printf函數(shù)可以分解為九個(gè)過(guò)程，請(qǐng)寫(xiě)出他們的排列順序_.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í)，綜合性能最好的數(shù)據(jù)結(jié)構(gòu)是：A. 雙向鏈表 B. 分塊鏈表 C. 穿線(xiàn)二叉樹(shù) D. 堆103. 廣告系統(tǒng)為了做地理位置定向，將IPV4分割為627672個(gè)區(qū)間，并標(biāo)識(shí)了地理位置信息，區(qū)間之間無(wú)重疊，用二分查找將IP地址映射到地理位置信息，請(qǐng)問(wèn)在最壞的情況下，需要查找多少步？A17 B18 C19 D20104.以入棧順序作為輸入，出棧作為輸出，并以I代表入棧，O代表出棧，現(xiàn)將1,2,3,4順序入棧，

29、則棧操作序列IIIIOOOO后，輸出4321；與輸出1234相對(duì)應(yīng)的棧操作序列為IOIOIOIO.則若想得到輸出為2314，則棧操作序列應(yīng)為_(kāi).無(wú)法由棧操作序列而得到的輸出有_。105. 設(shè)一組初始記錄關(guān)鍵字序列為（20,18,22,16,30,19），則根據(jù)這些初始關(guān)鍵字序列建成的初始堆為_(kāi).106.線(xiàn)性有序表（a1,a2,a3,.a256）是從小到大排列的，對(duì)一個(gè)給定的值k，用二分法檢索表中與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í)

30、現(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è)鏈表，把這些學(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. 鏈

31、表struct studentint m_Num; /學(xué)號(hào)double m_dScore; /分?jǐn)?shù)struct student* m_pNext; /下一個(gè)1).構(gòu)造一個(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ù)雜度是O(n)，請(qǐng)?jiān)O(shè)計(jì)一個(gè)時(shí)間復(fù)雜度小于O(n)的算法，(假設(shè)計(jì)算結(jié)果可以使用long型存儲(chǔ))7.給定一個(gè)數(shù)組an，我們希望構(gòu)造數(shù)組bn，其中 bi = a0*a1.an-1/ai.在構(gòu)造過(guò)程不允許使用

32、除法。1.要求O(1)空間復(fù)雜度和O(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），如果表達(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

33、的浮點(diǎn)數(shù)組Pr10000（稱(chēng)之為主題概率數(shù)組），其中Pri表示Query或者Adword屬于主題ID為i的概率，而Query和Adword 的相似度簡(jiǎn)化定義為兩者主題概率數(shù)組的內(nèi)積：即sim(Query,Adword) = sum(QueryPri*AdwordPri) (0<=i<=10000)。在實(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_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）個(gè)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);編寫(xiě)代碼求時(shí)間復(fù)雜度最低的算法，并給出時(shí)間復(fù)雜度分析。10. 給一個(gè)單詞a，如果通過(guò)交換單詞中字母的順序可以得到另外的單詞b，那么b是a的兄弟單詞，比如單詞army和mary互為兄弟單詞?，F(xiàn)在要給出一種解決方案，對(duì)于用戶(hù)輸入的單詞，根據(jù)給定的字典找出輸入單詞有哪些兄弟單詞。請(qǐng)具體說(shuō)明數(shù)據(jù)結(jié)構(gòu)和查詢(xún)流程，要求時(shí)間和空間效率盡可能的高？11. 系統(tǒng)中維護(hù)了若干數(shù)據(jù)項(xiàng)，我們對(duì)數(shù)據(jù)項(xiàng)的分類(lèi)可以分為三級(jí)，首先我們按照一級(jí)分類(lèi)方法將數(shù)據(jù)項(xiàng)分為A，B，C若干類(lèi)別，每一個(gè)級(jí)分類(lèi)方法產(chǎn)生的類(lèi)別又可以按照二級(jí)分類(lèi)方法分為a,b,c若干子類(lèi)別，同樣，二級(jí)分類(lèi)方法產(chǎn)生的類(lèi)別又可按照

36、三級(jí)分類(lèi)方法分為i,ii,iii若干子類(lèi)別，每個(gè)三級(jí)分類(lèi)方法產(chǎn)生的子類(lèi)別中的數(shù)據(jù)項(xiàng)從1開(kāi)始的編號(hào)。我們需要對(duì)每個(gè)數(shù)據(jù)項(xiàng)輸出日志，日志的形式是key-value。寫(xiě)入日志的時(shí)候，用戶(hù)提供三級(jí)類(lèi)別名稱(chēng)，數(shù)據(jù)項(xiàng)編號(hào)和日志的key，共五個(gè)key值，例如write(A,a,i,1,key1)，獲取日志的時(shí)候，用戶(hù)提供三級(jí)類(lèi)別名稱(chēng)，數(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ě)入日志和讀出日志的時(shí)間復(fù)雜度？12.鏈表struct student int m_Num;/學(xué)號(hào)double m_dScore;/分?jǐn)?shù)

37、struct student *m_pNext;/下一個(gè);1）構(gòu)造一個(gè)有20名學(xué)生的單向鏈表。按順序每名學(xué)生的分?jǐn)?shù)值為1,1,2,3,5,8,132）求出他們的平均分13.冒泡排序（寫(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)

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

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

40、*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.對(duì)于一個(gè)m*n的int矩陣，其每行自左向右是升序排列的，其每列自上向下是升序排列的，現(xiàn)需要在其中查找整數(shù)elem，找到時(shí)返回elem所在位置。請(qǐng)1）先寫(xiě)出思路；2）自行定義函數(shù)接口然后編程實(shí)現(xiàn)，編程語(yǔ)言不限。28.下面程序段的時(shí)間復(fù)

41、雜度為（）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. 一個(gè)單向鏈表，不知道頭結(jié)點(diǎn)，現(xiàn)在有一個(gè)指針指向其中一個(gè)節(jié)點(diǎn)，問(wèn)如何從鏈表中刪除這個(gè)指針指向的節(jié)點(diǎn)？例如：?jiǎn)蜗蜴湵鞮（1->2->3->4->5）,現(xiàn)有指針P指向節(jié)點(diǎn)3，現(xiàn)在要?jiǎng)h除節(jié)點(diǎn)3，把鏈表L變成（1->2->4->5）30. 已知一顆二叉樹(shù)的中序序列和后序序列分別為BDCEAFHG和DECBHGFA，畫(huà)出這顆二叉樹(shù).31.給定一個(gè)沒(méi)有重復(fù)數(shù)據(jù)的整數(shù)數(shù)組，找出其中所有兩

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

43、,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.有一個(gè)數(shù)組，里面由若干整數(shù)組成，除了一個(gè)整數(shù)外，其他都出現(xiàn)兩次，如何快速找到這個(gè)整數(shù)。例如：【1，2,1,3,4,4,3】，輸出應(yīng)為2.36.給定兩個(gè)有序單鏈表，求這兩個(gè)單鏈表的交集鏈表，并維持交集依然有序。請(qǐng)給出代碼實(shí)現(xiàn)，自己定義數(shù)據(jù)結(jié)構(gòu)。如有鏈表：1->2