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

數(shù)據(jù)結(jié)構(gòu)

1.采用折半搜索算法長度為n的有序表時，元素的平均搜索長度為()

A)0(n2)

B)O(nlog2n)

C)O(log2n)

D)O(n)

2.下面程序的時間復(fù)雜度為()

for(inti=0;i<m;i++)

(

for(intj=O;j<n;j++)

(

a[i]U]=i*j；

)

)

A)0(m2);

B)O(n2);

C)O(m*n);

D)O(m+n);

3.下列敘述中，對的的是()

A)線性表中的個元素在存儲空間中的位置必須是連續(xù)的

B)線性表中的表頭元素一定存儲在其他元素的前面

C)線性表中的個元素在存儲空間中的位置不一定是連續(xù)的，但表頭元素一定存儲在其他元素

的前面

D)線性表中的個元素在存儲空間中的位置不一定是連續(xù)的，且各元素的存儲順序也是任意的

4.已知二叉樹后序遍歷序列是edcfba,中序遍歷序列deacbf,它的前序遍歷序列是();

5.假如進(jìn)棧序列為el,e2,e3,e4,則也許的出棧序列是();

6,對長度為n的字符串進(jìn)行字符定位運(yùn)算的時間復(fù)雜度為();

A)O(l)

B)0(根號n)

C)O(nlog2n)

D)O(n)

7.n個頂點(diǎn)的連通圖中邊得條數(shù)至少為()

8.合并兩個已經(jīng)排好序的長度為n的Array<int>,最壞情況下需要比較多少次()

A)2n

B)2n-1

C)2n+1

D)n2

9.深度為5的滿二叉樹中，葉子結(jié)點(diǎn)的個數(shù)為()

A)32

B)31

C）16

D）15

10.冒泡排序算法和快速排序算法的時間復(fù)雜度分別是什么？

11.請簡述數(shù)組和鏈表數(shù)據(jù)結(jié)構(gòu)的特點(diǎn)及應(yīng)用的場合？

12.下列哪些數(shù)據(jù)結(jié)構(gòu)最適合醫(yī)療儀器設(shè)備中的大型數(shù)據(jù)量的插入，查找（）

A）數(shù)組

B）哈希表

C）紅黑樹/二叉平衡樹

D）鏈表

13.下列哪些排序算法的平均時間復(fù)雜度是。（nlog2n）（）,哪些是穩(wěn)定的排序（）

A）冒泡排序

B）希爾排序

C）快速排序

D）插入排序

E）堆排序

14.下列口那些說法是對的的：（）

A）二分查找法在一個長度為1000的有序整數(shù)數(shù)組查找一個整數(shù)，比較的次數(shù)不超過100次

B）在二叉樹中查找元素的時間復(fù)雜度為。（Iog2n）；

C）對單向鏈表，可以使用冒泡排序;

D）對雙向鏈表，可以使用快速排序;

15.已知某二叉樹的后序遍歷是DFBEGCA,中序遍歷的順序是DBFACEG,其前序遍歷順序是

16.下列代碼將兩個有序鏈表結(jié)合為一個，鏈表中的元素的排列順序?yàn)閺男〉酱?。請補(bǔ)充其

中的空缺。

structnode

(

structnode*pnext;

intval;

)；

structnode*splice(structnode*plhs,structnode*prsh)

(

if()

returnprhs?prhs:plhs;

structnode*phead,*plast;

if()

(

phead=plast=prhs;

plhs=plhs->pnext;

)

else

(

phead=plast=plhs;

prhs=prhs->pnext;

)

while()

{

if(plhs->val<prhs->val)

(

plast->pnext=plhs;

plast=plhs;

plhs=plhs->pnext;

}

else

(

plast->pnext=prhs;

plast=prhs;

prhs=prhs->pnext;

)

)

plast->pnest=;

return;

)

17.比較哈希表和平衡二叉樹的特點(diǎn)，他們分別用在哪些場合.

18.一個棧的入棧序列是A,B,C,D,E則棧的不也許的輸出序列是()

A)EDCBA

B)DECBA

ODCEAB

D)ABCDE

19.在排序的方法中，關(guān)鍵碼比較次數(shù)與記錄地初始排列無關(guān)的是()

A)Shell

B)歸并排序

Q直接排序

D)選擇排序

20以下反向遍歷array數(shù)組的方法有什么錯誤？

vectorarray;

array.push_back(l);

array.push_back(2);

array.push_back(3);

for(vector::size_typei=array.size()-l;i>=O;-i)

(

cout?array[i]?endl;

)

21.某火車站要通過一條棧道(先進(jìn)后出)來調(diào)換進(jìn)入車站的列車順序，若進(jìn)站的列車順序

為A,B,C,則下列哪個出棧順序不也許？

A)ABC

B)ACB

C)CAB

D)CBA

22.棧是一種是自能在某一端插入和刪除的特殊線性表。他按照后進(jìn)先出的原則存儲數(shù)據(jù)，

先進(jìn)入的數(shù)據(jù)被壓入棧底，最后進(jìn)入的數(shù)據(jù)在棧頂，

若6元素進(jìn)入棧S的順序?yàn)锳.B.C.D.E.F出棧順序?yàn)锽.D.C.F.E.A,則S棧最小容量為？

A)3B)4C)5D)6

24.若完全二叉樹的結(jié)點(diǎn)個數(shù)為2的N次方-1,則葉子結(jié)點(diǎn)個數(shù)為：

A)N-1

B)2*N

C)2(N-1)次方

D)2N次方

25.排序算法是穩(wěn)定是指：關(guān)鍵碼相同的記錄排序前后相應(yīng)位置不發(fā)生改變，下面哪種排序

算法是不穩(wěn)定的？

A)插入排序

B)冒泡排序

C)快速排序

D)歸并排序

26.下列說法中錯誤的是：

A)插入排序某些情況下復(fù)雜度為0(N)。

B)排序二叉樹元素查找的復(fù)雜度也許為0(N).

C)對于有序列表的排序最快的是快速排序。

D)在有序列表中通過二分查找的復(fù)雜度一定是。(nlog2n)。

27.棧和隊列的共同特點(diǎn)是()

28.棧通常采用的兩種存儲結(jié)構(gòu)是（）

29.下列關(guān)于棧的敘述對的的是（）

A）棧是非線性結(jié)構(gòu)

B）棧是一種樹狀結(jié)構(gòu)

C）棧具有先進(jìn)先出的特性

D）棧有后進(jìn)先出的特性

30.鏈表不具有的特點(diǎn)是（）

A）不必事先估計存儲空間

B）可隨機(jī)訪問任一元素

C）插入刪除不需要移動元素

D）所需空間與線性表長度成正比

31.用鏈表表達(dá)線性表的優(yōu)點(diǎn)是（）

32.循環(huán)鏈表的重要優(yōu)點(diǎn)是（）

33.線性表L=（al,a2,a3,...ai,........an）,下列說法對的的是（）

A）每個元素都有一個直接前件和直接后件

B）線性表中至少要有一個元素

C）表中諸元素的排列順序必須是由小到大或由大到小

D）除第一個和最后一個元素外，其余每個元素都有一個且只有一個直接前件和直接后件

34.線性表若采用鏈?zhǔn)酱鎯Y(jié)構(gòu)時，規(guī)定內(nèi)存中可用存儲單元的地址（）

A）必須是連續(xù)的

B）部分地址必須是連續(xù)的

C）一定是不連續(xù)的

D）連續(xù)不連續(xù)都可以

35.樹是結(jié)點(diǎn)的集合，它的根結(jié)點(diǎn)數(shù)目是（）

36.在深度為5的滿二叉樹中，結(jié)點(diǎn)的個數(shù)為（）

37.具有3個結(jié)點(diǎn)的二叉樹有（）種形態(tài)

38.設(shè)一棵二叉樹中有3個葉子結(jié)點(diǎn)，有8個度為1的結(jié)點(diǎn)，則該二叉樹中總的結(jié)點(diǎn)數(shù)為（）

39.算法一般都可以用哪幾種控制結(jié)構(gòu)組合而成（）

40.下列敘述對的的是（）

A）算法的執(zhí)行效率與數(shù)據(jù)的存儲結(jié)構(gòu)無關(guān)

B）算法的空間復(fù)雜度是指算法程序中指令（或語句）的條數(shù)

C）算法的有窮性是指算法必須能在執(zhí)行有限個環(huán)節(jié)之后終止

D）算法的時間復(fù)雜度是指執(zhí)行算法程序所需要的時間

41.數(shù)據(jù)結(jié)構(gòu)作為計算機(jī)的一門學(xué)科，重要研究數(shù)據(jù)的邏輯結(jié)構(gòu)、對各種數(shù)據(jù)結(jié)構(gòu)進(jìn)行的運(yùn)

算，以及（）

42.下列敘述中，錯誤的是（）

A）數(shù)據(jù)的存儲結(jié)構(gòu)與數(shù)據(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)可以有多種存儲結(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è)進(jìn)行打印。

46.下列關(guān)于隊列的敘述中對的的是()

A)在隊列中只能插入數(shù)據(jù)B)在隊列中只能刪除數(shù)據(jù)

C)隊列是先進(jìn)先出的線性表D)隊列是先進(jìn)后出的線性表

47.有一個C語言用來刪除單鏈表的頭元素的函數(shù)，請找出其中的問題并加以糾正。

voidRemoveHead(node*head)

(

free(head)

head=head->next

48.設(shè)單鏈表中節(jié)點(diǎn)的結(jié)構(gòu)為：

typedefstructnode

(

Elemtypedata;〃數(shù)據(jù)

structnode*Link;//節(jié)點(diǎn)后繼指針

JListnode;

(1)已知指針p所指節(jié)點(diǎn)不是尾節(jié)點(diǎn)，若在*p之后插入節(jié)點(diǎn)*s,則應(yīng)執(zhí)行下列哪一個操作?

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所指向)滿足：

A)p->link==NULL;B)p==NULL;

C)p->link==first;D)p==first;

49.如何證明一個表是循環(huán)鏈表？

52.假如一棵二叉樹節(jié)點(diǎn)的前序序列是A、B、C,后序序列是C、B、A,則該二叉樹節(jié)點(diǎn)的

中序序列是什么？

A)必為ABCB)必為ACBC)必為BCAD)不能擬定

53.什么是平衡二叉樹？

54.下面的程序是一快速排序問題，請?zhí)羁铡?/p>

#include<iostream>

#include<stdio.h>

voidimproveqsort(int*list,intrnjntn)

(

int/*

for(i=0;i<10;i++)

printf(”％3d“,list[i]);*/

if(m<n)

(

i=m;j=n+l;k=list[m];

while(i<j)

for(i=i+l,i<n.i++)

if(list[i]>=k)

break;

for(j=j-lj>mzj-)

if(list[j]<=k)

break;

if(i<j)

{t=list[i];list[i]=list[j];list[j]=t;}

}

t=list[m];list[m]=list[j];list[j]=t;

improveqsort();

improveqsort();

)

}

main()

(

intlist[10];

intn=9,m=O,i;

printf("input10number:");

for(i=0;i<10;i++)

printf("\n")；

improveqsort(list,m,n);

for(i=0;i<10;i++)

printf("%5d",list[i]);

printf("\n");

55.以下哪種排序?qū)儆诜€(wěn)定排序？

A)歸并排序B)快速排序C)希爾排序D)堆排序

56.用二分法查找一個長度為10的、排好序的線性表，查找不成功時，最多需要比較多少次?

A)5B)2C)4D)1

57.下面那種排序法對1234567最快？

A)quicksortB)bubblesortC)mergesort

58.解釋一下什么是哈夫曼編碼問題？

59.假設(shè)執(zhí)行語句Q的時間是。(1),則執(zhí)行下列程序段的時間為()

for(inti=l;i<=n;i++)

for(intj=i;j<=n;j++)

Q；

A.O(n)B.O(n2)C.O(n*i)D.0(n+l)

61.一棵有124個葉結(jié)點(diǎn)的完全二叉樹，最多有()個結(jié)點(diǎn)

A.247B.248C.249D.250

63.下列排序算法中，在待排序數(shù)據(jù)有序的情況下，花費(fèi)時間最多的是()

A.快速排序

B.希爾排序

C.冒泡排序

D.堆排序

64.有1000個無序的整數(shù)，希望使用最快的方式找出前50個最大的，最佳的選擇是()

A.冒泡排序

B.基數(shù)排序

C.堆排序

D.快速排序

65.下列哪個不是用來解決哈希表沖突的開放地址法()

A.線性探測法

B.線性補(bǔ)償探測法

C.拉鏈探測法

D.隨機(jī)探測法

66.假設(shè)把整數(shù)關(guān)鍵碼K散列到有N個槽的散列表，以下哪些散列函數(shù)是好的散列函數(shù)_

A.h(k)=k/N;

B.h伙)=1;

C.h(k)=kmodN;

D.h(k)=(k+Random(N))modN,random(N)返回一個0到N-1的整數(shù)

68.下面算法的時間復(fù)雜度是,

intf(unsignedintn)

if(n==O||n==l)

return1;

elsereturnn*f(n-l);

)

A.O(l)

B.O(n)

C.O(nA2)

D.O(n!)

69.對于一個具有n個頂點(diǎn)的無向圖，若采用鄰接表表達(dá)，則存放表頭節(jié)點(diǎn)的數(shù)組大小為

A.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)中最大的元素maxh(S)=10,那么S的大

小的盼望是

A.5

B.10

C.512

D.1024

71.對于順序存儲的線性數(shù)組，訪問結(jié)點(diǎn)和增長，刪除結(jié)點(diǎn)的時間復(fù)雜度為一.

A.O(n),O(n)

B.O(n),O(l)

C.O(l),O(n)

D.O(1),O(1)

75.遞歸式的先序遍歷一個n節(jié)點(diǎn)，深度為d的二叉樹，需要棧空間的大小為一.

A.O(n)

B.O(d)

C.O(logn)

D.(nlogn)

76.關(guān)于排序算法的以下說法，錯誤的是一

A.快速排序的平均時間復(fù)雜度為O(nlogn),最壞的時間復(fù)雜度為0(n2)

B.堆排序的平均時間復(fù)雜度為O(nlogn),最壞的時間復(fù)雜度為O(nlogn)

C.冒泡排序的平均時間復(fù)雜度為0(n2),最壞的時間復(fù)雜度為0(n2)

D.歸并排序的平均時間復(fù)雜度為。(nlogn),最壞的時間復(fù)雜度為0(n2)

77.某二叉樹的前序遍歷序列為-+a*b-cd/ef,后序遍歷序列為abcd-*+ef/-,問其中序遍歷序

列是一.

78.某緩存系統(tǒng)采用LRU淘汰算法，假定緩存容量為4,并且初始為空，那么在順序訪問以

下數(shù)據(jù)項的時候1,5,1,352,4,1,2出現(xiàn)緩存直接命中的次數(shù)是1最后緩存中即將準(zhǔn)

備淘汰的數(shù)據(jù)項是.

79.有兩個較長的單向鏈表a和b,為了找出結(jié)點(diǎn)node滿足nodeina并且nodeinb。請設(shè)計

空間使用盡量小的算法。

80.當(dāng)存儲數(shù)據(jù)量超過單節(jié)點(diǎn)數(shù)據(jù)管理能力的時候，可以采用的辦法有數(shù)據(jù)庫sharding的

解決方案，也就是按照一定規(guī)律把數(shù)據(jù)

分散存儲在多個數(shù)據(jù)管理結(jié)點(diǎn)N中(節(jié)點(diǎn)編號為0,1,2…N-1).假設(shè)存儲的數(shù)據(jù)是a,請完畢

為數(shù)據(jù)a計算存儲節(jié)點(diǎn)的程序。

#defineN5

inthashfintelement){

returnelement*;

}

intshardinglndex(inta){

intp=hash(a);

returnp;

82.具有100個結(jié)點(diǎn)的二叉樹中，若用二叉鏈表存儲，其指針域部分用來指向結(jié)點(diǎn)的左右孩

子，其余一個指針域?yàn)榭?/p>

A.50

B.99

C.100

D.1O1

83.請實(shí)現(xiàn)一個快速排序算法，僅考慮被排序?qū)ο鬄檎麛?shù)的情況。

84.一顆二叉樹高度為h,所有節(jié)點(diǎn)的度或?yàn)?,或?yàn)?,則這顆二叉樹最少有()結(jié)點(diǎn)

A.2h

B.2h-1

C.2h+1

D.h+1

85.在百度或淘寶搜索時，每鍵入字符都會出現(xiàn)搜索建議，實(shí)現(xiàn)這類技術(shù)后臺采用的數(shù)據(jù)結(jié)

構(gòu)是.

86.設(shè)哈弗曼樹中的葉子結(jié)點(diǎn)總數(shù)為m,若用二叉鏈表作為存儲結(jié)構(gòu)，則該哈弗曼樹中總共

有()個空指針域：

A.2m-1

B.2m

C.2m+1

D.4m

87.后綴式ab+cd+/可用下面哪個表達(dá)式來表達(dá)：

A.a+b/c+d

B.a+b/(c+d)

C.a+b+c/d

D.(a+b)/(c+d)

88.給定一個數(shù)組11315762139194,每次操作可以互換不含反復(fù)數(shù)字的多對數(shù)，求至少

需要多少次操作才干使數(shù)組遞增有序，

比如互換(11,3)(15,7)(6,2)只算一次操作，而互換(11,3).(3,2)算兩次操作

A.6

B.5

C.2

D.3

89.寫一個函數(shù)，去除一個字符串中的所有反復(fù)字符，規(guī)定在原字符串上進(jìn)行操作，不可以

使用庫函數(shù)，空間復(fù)雜度。(1)。

例如：輸入字符串為”aabbbca“，則去重后的字符串為“abc“

90.如何判斷一個二叉樹是不是對稱二叉樹。(對稱必須是左右子樹對稱，且相應(yīng)節(jié)點(diǎn)的值也

相同)

91.某個車站呈狹長型，寬度只能容下一臺車，并且只有一個出入口，已知某時刻該車站狀

態(tài)為空，從這一時刻開始的出入記錄為：

“進(jìn)，出，進(jìn)，進(jìn)，進(jìn)，出，出，進(jìn)，進(jìn)，進(jìn)，出，出”假設(shè)該車輛入棧的順序?yàn)?,2,3……,

則車輛的出棧順序?yàn)?)

A.1,2,3,4,5

B.1,2,4,5,7

C.1,4,3,7,6

D.1,4,3,7,2

92.將數(shù)組｛8,23,4,16,77,-5,53,100｝中的元素按從小到大的順序排列，每次可以互換任意兩個

元素，最少需要互換()次

A.4

B.5

C.6

D.7

94.完全二叉樹和滿二叉樹的聯(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ī)算法RAND

C.先進(jìn)后出算法FIL。

D.替換最近最少使用的塊算法LRU

97.快速排序最壞情況下的時間復(fù)雜度是：()

A.0(nlog(n))

B.0(n2)

C.O(log(n))

D.0(n)

98.一個文本文獻(xiàn)，大約有10000行，每行一個詞，規(guī)定記錄出其中最頻繁出現(xiàn)的前十個詞

(Ie表達(dá)單詞的平均長度)，給出時間復(fù)雜度分析。()

A.max(O(n*le),O(n*lgl0))

B.min(O(n*le),O(n*lgl0))

C.O(n*le)

D.O(n*lglO)

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ù)據(jù)的存儲結(jié)構(gòu)無關(guān)

F.算法的時間復(fù)雜度是指執(zhí)行算法程序所需要的時間

G.在單鏈表中，只要指出表中任何一個節(jié)點(diǎn)的位置，就可以從他出發(fā)依次訪問到鏈表中其

他所有節(jié)點(diǎn)

H.在一個單鏈表中，已知q所指結(jié)點(diǎn)是p所指節(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，若在p和q之間插入結(jié)點(diǎn)

s,貝!I執(zhí)行，s->next=p;q->next=s;

I.在一個單鏈表中，若刪除p所指節(jié)點(diǎn)的后續(xù)結(jié)點(diǎn)，則執(zhí)行p=p->next;p->next=p->next->next

J.使用鏈表，可隨機(jī)訪問鏈表中的任何一個元素

100.調(diào)用printf函數(shù)可以分解為九個過程，請寫出他們的排列順序.

A.call指令

B.EBP出棧

C.函數(shù)參數(shù)壓棧

D.收回局部變量空間

E.EBP壓棧

F.在棧上保存局部變量

G.函數(shù)參數(shù)出棧

H.ret指令

I.打印輸出字符串

102.在以下幾種數(shù)據(jù)結(jié)構(gòu)中，在執(zhí)行數(shù)量相稱的查找，刪除和插入操作時，綜合性能最佳的

數(shù)據(jù)結(jié)構(gòu)是：

A.雙向鏈表

B.分塊鏈表

C.穿線二叉樹

D.堆

103.廣告系統(tǒng)為了做地理位置定向，將IPV4分割為627672個區(qū)間，并標(biāo)記了地理位置信

息，區(qū)間之間無重疊，用二分查找將IP地址映射到地理位置信息，

請問在最壞的情況下，需要查找多少步？

A.17

B.18

C.19

D.20

104.以入棧順序作為輸入，出棧作為輸出，并以I代表入棧，。代表出棧，現(xiàn)將1,2,3,4順序

入棧，則棧操作序列IIIIOOOO后，輸出4321；與輸出1234相相應(yīng)

的棧操作序列為I0I0I0Q則若想得到輸出為2314,則棧操作序列應(yīng)為—.無法由棧操作序

列而得到的輸出有。

105.設(shè)一組初始記錄關(guān)鍵字序列為(20,18,22,16,30,19),則根據(jù)這些初始關(guān)鍵字序列建成

的初始堆為.

106.線性有序表(al,a2,a3j”.a256)是從小到大排列的，對一個給定的值k,用二分法檢索

表中與K相等的元素，在查找不成功的情況下，最多需要檢索次。

編程

1單鏈表

1：編程實(shí)現(xiàn)一個單鏈表的建立。

2：編程實(shí)現(xiàn)一個單鏈表的側(cè)長。

3：編程實(shí)現(xiàn)一個單鏈表的打印。

4:編程實(shí)現(xiàn)一個單鏈表刪除節(jié)點(diǎn)。

5：編程實(shí)現(xiàn)單鏈表的插入。

6：編程實(shí)現(xiàn)單鏈表的逆置。

2雙鏈表

1：編程實(shí)現(xiàn)雙鏈表的建立。

2：編程實(shí)現(xiàn)雙鏈表的側(cè)長。

3：編程實(shí)現(xiàn)雙鏈表的打印。

4：編程實(shí)現(xiàn)雙鏈表刪除節(jié)點(diǎn)。

5：編程實(shí)現(xiàn)雙鏈表的插入。

1：編程實(shí)現(xiàn)隊列的入隊。

2：編程實(shí)現(xiàn)隊列的出隊。

3：編程實(shí)現(xiàn)隊列的側(cè)長。

4：編程實(shí)現(xiàn)隊列的打印。

1.一個學(xué)生的信息：姓名，學(xué)號，性別，年齡等信息，用一個鏈表，把這些學(xué)生信息連在

一起，給出一個age,在這些鏈表中刪除學(xué)生年齡等于age的學(xué)生信息。

2.請用C或C++寫出一個冒泡排序程序，規(guī)定輸入10個整數(shù)，輸出排序結(jié)果。

3.請用C或C++寫出一個shell排序程序，規(guī)定輸入10個整數(shù)，輸出排序結(jié)果。

4.鏈表

structstudent

(

intm_Num;〃學(xué)號

doublem_dScore;〃分?jǐn)?shù)

structstudent*m_pNext;〃下一個

1).構(gòu)造一個有20名學(xué)生的單向鏈表。按順序每名學(xué)生的分?jǐn)?shù)值為，1,2,3,5,8,13…

2).求出他們的平均分。

5.請實(shí)現(xiàn)一個快速排序的算法。僅考慮排序的對象為整數(shù)的情況。

6.計算a的n次方是許多加密算法的基本操作，蠻力計算方法的時間復(fù)雜度是O(n),請設(shè)

計一個時間復(fù)雜度小于O(n)的算法，(假設(shè)計算結(jié)果可以使用long型存儲)

7.給定一個數(shù)組a[n],我們希望構(gòu)造數(shù)組b[n],其中b[i]=a[0]*a[l]...a[n-l]/a[i].在構(gòu)造過程

不允許使用除法。

1.規(guī)定0(1)空間復(fù)雜度和0(n)時間復(fù)雜度。

2.除遍歷計數(shù)器與a[n]b[n]外，不可使用新的變量(涉及棧臨時變量，堆空間和全局靜態(tài)變

量等)；

8.給定一個如下輸入格式的字符串，(1,(2,3),(4,(5,6),7))括號內(nèi)的元素可以是數(shù)字,

也可以是另一個括號。請實(shí)現(xiàn)一個算法消除嵌套的括號，

比如把上面的表達(dá)式變成：(123,4,5,6,7),假如表達(dá)式有誤請報錯。

9.相似度計算用于衡量對象之間的相似限度，在數(shù)據(jù)挖掘，自然語言解決中是一個基礎(chǔ)性計

算。在廣告檢索服務(wù)中往往也會判斷網(wǎng)民檢索Query和廣告Adword的

主題相似度。假設(shè)Query或者Adword的主題屬性定義為一個長度為10000的浮點(diǎn)數(shù)組

Pr[10000](稱之為主題概率數(shù)組)，其中Pr[i]表達(dá)Query或者Adword屬于主

題ID為i的概率，而Query和Adword的相似度簡化定義為兩者主題概率數(shù)組的內(nèi)積：即

sim(Query,Adword)=sum(QueryPr[i]*AdwordPr[i])(0<=i<=10000)?在

實(shí)際應(yīng)用場景中，由于大多數(shù)主題概率都為0,所以主題概率數(shù)組往往比較稀疏，在實(shí)現(xiàn)時

會以一個緊湊型數(shù)組topic_info_t0的方式保存，其中100<=數(shù)組大小

<=1000,并按照topicjd遞增排列，0<=topic_id<10000,0<topic_pr<l?

structtopic_info_t

(

inttopicjd;

floattopic_pr;

)；

現(xiàn)在給出Query的topicjnfo_t數(shù)組和N(N>=5000)個Adwords的topic_info_t數(shù)組，現(xiàn)規(guī)

定出與的相似度最大值。即

QueryAdwordsmax(sim(Query;Adword[i]))

(0<=i<N).

floatmax_sim(constvector<topic_info_t>&query_topic_info,

constvector<topic_info_t>adwords_topic_info[],

intadwords_number);

編寫代碼求時間復(fù)雜度最低的算法，并給出時間復(fù)雜度分析。

10.給一個單詞a,假如通過互換單詞中字母的順序可以得到此外的單詞b,那么b是a的

兄弟單詞，比如單詞army和mary互為兄弟單詞。

現(xiàn)在要給出一種解決方案，對于用戶輸入的單詞，根據(jù)給定的字典找出輸入單詞有哪些兄弟

單詞。請具體說明數(shù)據(jù)結(jié)構(gòu)和查詢流程，規(guī)定期間和空間效率盡也許

的高？

11.系統(tǒng)中維護(hù)了若干數(shù)據(jù)項，我們對數(shù)據(jù)項的分類可以分為三級，一方面我們按照一級

分類方法將數(shù)據(jù)項分為A,B,C……若干類別，每一個級分類方法產(chǎn)生的類

別又可以按照二級分類方法分為a,b,c…若干子類別，同樣，二級分類方法產(chǎn)生的類別又可

按照三級分類方法分為i,ii,iii…若干子類別，每個三級分類方法產(chǎn)生

的子類別中的數(shù)據(jù)項從1開始的編號。我們需要對每個數(shù)據(jù)項輸出日記，日記的形式是

key-valueo寫入日記的時候，用戶提供三級類別名稱，數(shù)據(jù)項編號和日

志的key,共五個key值，例如write（A,a,i,l,keyl）,獲取日記的時候，用戶提供三級類別名

稱，數(shù)據(jù)項編號，共四個key值，返回相應(yīng)的所有key-value,

例如get_log（A,a,i,l）,請描述一種數(shù)據(jù)結(jié)構(gòu)來存儲這些日記，并計算出寫入日記和讀出日記

的時間復(fù)雜度？

12.鏈表

structstudent

{

intm_Num;〃學(xué)號

doublem_dScore;〃分?jǐn)?shù)

structstudent*m_pNext;〃下一個

}；

1）構(gòu)造一個有20名學(xué)生的單向鏈表。按順序每名學(xué)生的分?jǐn)?shù)值為1,1,2,3,5,8,13…

2）求出他們的平均分

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位，規(guī)定期間復(fù)雜度為O(N),

空間復(fù)雜度為O(l)o

17.一個單向鏈表，不知道頭結(jié)點(diǎn)，一個指針指向其中一個節(jié)點(diǎn)，問如何刪除這個指針指向

的結(jié)點(diǎn).

18.編程得到以下算式的結(jié)果(規(guī)定計算的效率最高)

算式:1-2+3-4+5-6......N

19.請寫出一個程序，把一段字符串里面的某個字符(也許出現(xiàn)幾次)過濾掉，比如“abcdefg”

過濾掉e變成"abcdfg”。

規(guī)定算法復(fù)雜度。(n),空間復(fù)雜度。⑴(10)。

20.編寫一個按單詞反轉(zhuǎn)字符串的函數(shù)，如給定輸入hereis.com后變成.comishere

21.列出你知道的排序算法,并使用其中的任意一種排序算法實(shí)現(xiàn)int*sort(intarray[],int

length),array是一個待排整形數(shù)組，length是數(shù)組長度，

將排序結(jié)果以整型指針的形式輸出。

22.編寫一個函數(shù)，計算兩個正整數(shù)的最小公倍數(shù)，規(guī)定用輾轉(zhuǎn)相除法。

23.已知兩個鏈表Listl和List2,均為增序，請把他們合并成一個鏈表，規(guī)定仍為增序，請

用遞歸實(shí)現(xiàn)。

24.編程求10000以內(nèi)的素數(shù)，規(guī)定對算法進(jìn)行適當(dāng)優(yōu)化。

25.（八皇后問題）在一個8*8的國際象棋棋盤上擺放八個皇后，使其不能互相襲擊，即任

意兩個皇后都不能處在同一行，同一列或同一斜線上。

請編程求出所有可行的擺法，規(guī)定用回溯法寫出程序。

26.給定一個單鏈表和一個整數(shù)K,規(guī)定每隔K個元素翻轉(zhuǎn)鏈表：

structnode

（

intkey;

structnode*next;

｝；

typedefnode*List;

實(shí)現(xiàn)該函數(shù)：int*kReverse（List*Head,intk）

比如：原始鏈表為：l->2->3->4->5->6

k=2翻轉(zhuǎn)為:2->1->4->3->6->5

k=3翻轉(zhuǎn)為:3->2->1->6->5->4

k=4翻轉(zhuǎn)為:4->3->2->1->5->6

27.對于一個m*n的int矩陣，其每行自左向右是升序排列的，其每列自上向下是升序排列

的，現(xiàn)需要在其中查找整數(shù)elem,找屆時返回elem所在位置。

請1）先寫出思緒；2）自行定義函數(shù)接口然后編程實(shí)現(xiàn)，編程語言不限。

28.下面程序段的時間復(fù)雜度為（）

for(inti=O;i<m;i++)

for(intj=0;j<n;j++)

(

a[i]U]=i*j;

)

)

A.O(mA2)

B.O(nA2)

C.O(m*n)

D.O(m+n)

29.一個單向鏈表，不知道頭結(jié)點(diǎn)，現(xiàn)在有一個指針指向其中一個節(jié)點(diǎn)，問如何從鏈表中刪

除這個指針指向的節(jié)點(diǎn)？例如：單向鏈表L(1->2->3->4->5),

現(xiàn)有指針P指向節(jié)點(diǎn)3,現(xiàn)在要刪除節(jié)點(diǎn)3,把鏈表L變成(1->2->4->5)

30.已知一顆二叉樹的中序序列和后序序列分別為BDCEAFHG和DECBHGFA,畫出這顆二叉

樹.

31.給定一個沒有反復(fù)數(shù)據(jù)的整數(shù)數(shù)組，找出其中所有兩個數(shù)相加之和等于2023的整數(shù)對，

并且打印出來。(請寫出你的思緒，然后用代碼實(shí)現(xiàn)出來)

32.已知兩個集合A[5,2,7,4,3,9,9]B[5,3,1,9,2,6,2],寫一段代碼順序打

印出這兩個集合中反復(fù)的元素。嘗試使你的代碼時間復(fù)雜度最優(yōu),

請在代碼之前寫出你的思緒。

33.己知字母順序是［d,g,c,f,b,e,a］請對輸入的一組字符串input［3］={"dca”,“dfa”,

“cgd”},按照字母順序進(jìn)行排序并打印，本例的輸出為：

1：dca

2：dfa

3：cgd

如何檢測上述代碼是達(dá)成質(zhì)量標(biāo)準(zhǔn)的？

34.createafunctionforstringpadstart(Stringstring,intminlength,charpadChar);

returnastring,oflengthatleastminlength,consistingofstringprependedwithasmanycopies

ofpadCharasarenecessarytoreach

thatlength.

forexample:

padStart("7〃3'0')returns"007”

padStart(z/2023,：3/0,)returns//2023,/

35.有一個數(shù)組，里面由若干整數(shù)組成，除了一個整數(shù)外，其他都出現(xiàn)兩次，如何快速找到

這個整數(shù)。例如：［1,