02笔试题数据结构部分.docx

02笔试题数据结构部分.docx

《02笔试题数据结构部分.docx》由会员分享，可在线阅读，更多相关《02笔试题数据结构部分.docx（31页珍藏版）》请在冰点文库上搜索。

02笔试题数据结构部分

数据结构

1.采用折半搜索算法长度为n的有序表时，元素的平均搜索长度为（）

A）O（n2）

B）O（nlog2n）

C）O（log2n）

D）O（n）

2.下面程序的时间复杂度为（）

for（inti=0;i

{

for（intj=0;j

{

a[i][j]=i*j;

}

}

A）O（m2）;

B）O（n2）;

C）O（m*n）;

D）O（m+n）;

3.下列叙述中，正确的是（）

A）线性表中的个元素在存储空间中的位置必须是连续的

B）线性表中的表头元素一定存储在其他元素的前面

C）线性表中的个元素在存储空间中的位置不一定是连续的，但表头元素一定存储在其他元素的前面

D）线性表中的个元素在存储空间中的位置不一定是连续的，且各元素的存储顺序也是任意的

4.已知二叉树后序遍历序列是edcfba，中序遍历序列deacbf，它的前序遍历序列是（）;

5.如果进栈序列为e1,e2,e3,e4，则可能的出栈序列是（）;

6.对长度为n的字符串进行字符定位运算的时间复杂度为（）;

A）O

（1）

B）O（根号n）

C）O（nlog2n）

D）O（n）

7.n个顶点的连通图中边得条数至少为（）

8.合并两个已经排好序的长度为n的Array,最坏情况下需要比较多少次（）

A）2n

B）2n-1

C）2n+1

D）n2

9.深度为5的满二叉树中，叶子结点的个数为（）

A）32

B）31

C）16

D）15

10.冒泡排序算法和快速排序算法的时间复杂度分别是什么？

11.请简述数组和链表数据结构的特点及应用的场合？

12.下列哪些数据结构最适合医疗仪器设备中的大型数据量的插入，查找（）

A）数组

B）哈希表

C）红黑树/二叉平衡树

D）链表

13.下列哪些排序算法的平均时间复杂度是O（nlog2n）（），哪些是稳定的排序（）

A）冒泡排序

B）希尔排序

C）快速排序

D）插入排序

E）堆排序

14.下列哪些说法是正确的：

（）

A）二分查找法在一个长度为1000的有序整数数组查找一个整数，比较的次数不超过100次

B）在二叉树中查找元素的时间复杂度为O（log2n）；

C）对单向链表，可以使用冒泡排序；

D）对双向链表，可以使用快速排序；

15.已知某二叉树的后序遍历是DFBEGCA，中序遍历的顺序是DBFACEG，其前序遍历顺序是_________________

16.下列代码将两个有序链表结合为一个，链表中的元素的排列顺序为从小到大。

请补充其中的空缺。

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->valval）

{

plast->pnext=plhs;

plast=plhs;

plhs=plhs->pnext;

}

else

{

plast->pnext=prhs;

plast=prhs;

prhs=prhs->pnext;

}

}

plast->pnest=___________________;

return________________________;

}

17.比较哈希表和平衡二叉树的特点，他们分别用在哪些场合.

18.一个栈的入栈序列是A,B,C,D,E则栈的不可能的输出序列是（）

A）EDCBA

B）DECBA

C）DCEAB

D）ABCDE

19.在排序的方法中，关键码比较次数与记录地初始排列无关的是（）

A）Shell

B）归并排序

C）直接排序

D）选择排序

20.以下反向遍历array数组的方法有什么错误？

vectorarray;

array.push_back

（1）;

array.push_back

（2）;

array.push_back（3）;

for（vector:

:

size_typei=array.size（）-1;i>=0;--i）

{

cout<

}

21.某火车站要通过一条栈道（先进后出）来调换进入车站的列车顺序，若进站的列车顺序为A，B，C，则下列哪个出栈顺序不可能？

A）ABC

B）ACB

C）CAB

D）CBA

22.栈是一种是自能在某一端插入和删除的特殊线性表。

他按照后进先出的原则存储数据，先进入的数据被压入栈底，最后进入的数据在栈顶，

若6元素进入栈S的顺序为A.B.C.D.E.F出栈顺序为B.D.C.F.E.A,则S栈最小容量为？

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

24.若完全二叉树的结点个数为2的N次方-1，则叶子结点个数为：

A）N-1

B）2*N

C）2（N-1）次方

D）2N次方

25.排序算法是稳定是指：

关键码相同的记录排序前后对应位置不发生改变，下面哪种排序算法是不稳定的？

A）插入排序

B）冒泡排序

C）快速排序

D）归并排序

26.下列说法中错误的是：

A）插入排序某些情况下复杂度为O（N）。

B）排序二叉树元素查找的复杂度可能为O（N）.

C）对于有序列表的排序最快的是快速排序。

D）在有序列表中通过二分查找的复杂度一定是O（nlog2n）。

27.栈和队列的共同特点是（）

28.栈通常采用的两种存储结构是（）

29.下列关于栈的叙述正确的是（）

A）栈是非线性结构

B）栈是一种树状结构

C）栈具有先进先出的特征

D）栈有后进先出的特征

30.链表不具有的特点是（）

A）不必事先估计存储空间

B）可随机访问任一元素

C）插入删除不需要移动元素

D）所需空间与线性表长度成正比

31.用链表表示线性表的优点是（）

32.循环链表的主要优点是（）

33.线性表L＝（a1,a2,a3,……ai,……an），下列说法正确的是（）

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

B）线性表中至少要有一个元素

C）表中诸元素的排列顺序必须是由小到大或由大到小

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

34.线性表若采用链式存储结构时，要求内存中可用存储单元的地址（）

A）必须是连续的

B）部分地址必须是连续的

C）一定是不连续的

D）连续不连续都可以

35.树是结点的集合，它的根结点数目是（）

36.在深度为5的满二叉树中，结点的个数为（）

37.具有3个结点的二叉树有（）种形态

38.设一棵二叉树中有3个叶子结点，有8个度为1的结点，则该二叉树中总的结点数为（）

39.算法一般都可以用哪几种控制结构组合而成（）

40.下列叙述正确的是（）

A）算法的执行效率与数据的存储结构无关

B）算法的空间复杂度是指算法程序中指令（或语句）的条数

C）算法的有穷性是指算法必须能在执行有限个步骤之后终止

D）算法的时间复杂度是指执行算法程序所需要的时间

41.数据结构作为计算机的一门学科，主要研究数据的逻辑结构、对各种数据结构进行的运算，以及（）

42.下列叙述中，错误的是（）

A）数据的存储结构与数据处理的效率密切相关

B）数据的存储结构与数据处理的效率无关

C）数据的存储结构在计算机中所占的空间不一定是连续的

D）一种数据的逻辑结构可以有多种存储结构

46.根据数据结构中各数据元素之间前后件关系的复杂程度，一般将数据结构分为（）

43.下列数据结构中，按先进后出原则组织数据的是（）

A）线性链表

B）栈

C）循环链表

D）顺序表

44.下列关于栈的叙述中正确的是（）

A）在栈中只能插入数据

B）在栈中只能删除数据

C）栈是先进先出的线性表

D）栈是先进后出的线性表

45.应用程序在执行过程中，需要通过打印机输出数据时，一般先形成一个打印作业，将其存放在硬盘中的一个指定（）中，

当打印机空闲时，就会按先来先服务的方式从中取出待打印的作业进行打印。

46.下列关于队列的叙述中正确的是（）

A）在队列中只能插入数据B）在队列中只能删除数据

C）队列是先进先出的线性表D）队列是先进后出的线性表

47.有一个C语言用来删除单链表的头元素的函数，请找出其中的问题并加以纠正。

voidRemoveHead（node*head）

{

free（head）

head=head->next

}

48.设单链表中节点的结构为：

typedefstructnode

{

Elemtypedata;//数据

structnode*Link;//节点后继指针

}Listnode;

（1）已知指针p所指节点不是尾节点，若在*p之后插入节点*s，则应执行下列哪一个操作？

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）非空的循环单链表first的尾节点（由p所指向）满足：

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

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

49.如何证明一个表是循环链表？

52.如果一棵二叉树节点的前序序列是A、B、C，后序序列是C、B、A，则该二叉树节点的中序序列是什么？

A）必为ABCB）必为ACBC）必为BCAD）不能确定

53.什么是平衡二叉树？

54.下面的程序是一快速排序问题，请填空。

#include

#include

voidimproveqsort（int*list,intm,intn）

{

intk,t,i,j;/*

for（i=0;i<10;i++）

printf（"%3d",list[i]）;*/

if（m

{

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

while（i

{

for（i=i+1,i

if（list[i]>=k）

break;

for（j=j-1,j>m,j--）

if（list[j]<=k）

break;

if（i

{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=0,i;

printf（"input10number:

"）;

for（i=0;i<10;i++）

scanf（"%d",&list[i]）;

printf（"\n"）;

improveqsort（list,m,n）;

for（i=0;i<10;i++）

printf（"%5d",list[i]）;

printf（"\n"）;

}

55.以下哪种排序属于稳定排序？

A）归并排序B）快速排序C）希尔排序D）堆排序

56.用二分法查找一个长度为10的、排好序的线性表，查找不成功时，最多需要比较多少次？

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

57.下面那种排序法对1234567最快？

A）quicksortB）bubblesortC）mergesort

58.解释一下什么是哈夫曼编码问题？

59.假设执行语句Q的时间是O

（1），则执行下列程序段的时间为（）

for（inti=1;i<=n;i++）

for（intj=i;j<=n;j++）

Q;

A.O（n）B.O（n2）C.O（n*i）D.O（n+1）

61.一棵有124个叶结点的完全二叉树，最多有（）个结点

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

63.下列排序算法中，在待排序数据有序的情况下，花费时间最多的是（）

A．快速排序

B.希尔排序

C.冒泡排序

D.堆排序

64.有1000个无序的整数，希望使用最快的方式找出前50个最大的，最佳的选择是（）

A.冒泡排序

B.基数排序

C.堆排序

D.快速排序

65.下列哪个不是用来解决哈希表冲突的开放地址法（）

A.线性探测法

B.线性补偿探测法

C.拉链探测法

D.随机探测法

66.假设把整数关键码K散列到有N个槽的散列表，以下哪些散列函数是好的散列函数___。

A．h（k）=k/N;

B．h（k）=1;

C．h（k）=kmodN;

D．h（k）=（k+Random（N））modN,random（N）返回一个0到N-1的整数

68.下面算法的时间复杂度是____.

intf（unsignedintn）

{

if（n==0||n==1）

return1;

elsereturnn*f（n-1）;

}

A.O

（1）

B.O（n）

C.O（n^2）

D.O（n!

）

69.对于一个具有n个顶点的无向图，若采用邻接表表示，则存放表头节点的数组大小为

A.n

B.n+1

C.n-1

D.n+边数

70.考虑一个特殊的hash函数h,能将任一字符串hash成一个整数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.对于顺序存储的线性数组，访问结点和增加，删除结点的时间复杂度为____.

A.O（n）,O（n）

B.O（n）,O

（1）

C.O

（1）,O（n）

D.O

（1）,O

（1）

75.递归式的先序遍历一个n节点，深度为d的二叉树，需要栈空间的大小为____.

A.O（n）

B.O（d）

C.O（logn）

D.（nlogn）

76.关于排序算法的以下说法，错误的是____

A.快速排序的平均时间复杂度为O（nlogn），最坏的时间复杂度为O（n2）

B.堆排序的平均时间复杂度为O（nlogn），最坏的时间复杂度为O（nlogn）

C.冒泡排序的平均时间复杂度为O（n2），最坏的时间复杂度为O（n2）

D.归并排序的平均时间复杂度为O（nlogn），最坏的时间复杂度为O（n2）

77.某二叉树的前序遍历序列为-+a*b-cd/ef，后序遍历序列为abcd-*+ef/-，问其中序遍历序列是_____.

78.某缓存系统采用LRU淘汰算法，假定缓存容量为4，并且初始为空，那么在顺序访问以下数据项的时候1,5,1,3,5,2,4,1,2出现缓存直接命中的次数是___________,最后缓存中即将准备淘汰的数据项是______.

79.有两个较长的单向链表a和b，为了找出结点node满足nodeina并且nodeinb。

请设计空间使用尽量小的算法。

80.当存储数据量超出单节点数据管理能力的时候，可以采取的办法有数据库sharding的解决方案，也就是按照一定规律把数据

分散存储在多个数据管理结点N中（节点编号为0,1,2…N-1）.假设存储的数据是a，请完成为数据a计算存储节点的程序。

#defineN5

inthash（intelement）{

returnelement*2654435761;

}

intshardingIndex（inta）{

intp=hash（a）;

________________________________

returnp;

}

82.具有100个结点的二叉树中，若用二叉链表存储，其指针域部分用来指向结点的左右孩子，其余____个指针域为空

A.50

B.99

C.100

D.101

83.请实现一个快速排序算法，仅考虑被排序对象为整数的情况。

84.一颗二叉树高度为h，所有节点的度或为0，或为2，则这颗二叉树最少有（）结点

A.2h

B.2h-1

C.2h+1

D.h+1

85.在XX或淘宝搜索时，每键入字符都会出现搜索建议，实现这类技术后台采用的数据结构是__________________.

86.设哈弗曼树中的叶子结点总数为m，若用二叉链表作为存储结构，则该哈弗曼树中总共有（）个空指针域：

A.2m-1

B.2m

C.2m+1

D.4m

87.后缀式ab+cd+/可用下面哪个表达式来表示:

A.a+b/c+d

B.a+b/（c+d）

C.a+b+c/d

D.（a+b）/（c+d）

88.给定一个数组11315762139194，每次操作可以交换不含重复数字的多对数，求至少需要多少次操作才能使数组递增有序，

比如交换（11,3）（15,7）（6,2）只算一次操作，而交换（11,3），（3,2）算两次操作

A.6

B.5

C.2

D.3

89.写一个函数，去除一个字符串中的所有重复字符，要求在原字符串上进行操作，不可以使用库函数，空间复杂度O

（1）。

例如：

输入字符串为”aabbbca“，则去重后的字符串为”abc“

90.如何判断一个二叉树是不是对称二叉树。

（对称必须是左右子树对称，且对应节点的值也相同）

91.某个车站呈狭长型，宽度只能容下一台车，并且只有一个出入口，已知某时刻该车站状态为空，从这一时刻开始的出入记录为：

“进，出，进，进，进，出，出，进，进，进，出，出”假设该车辆入栈的顺序为1,2,3……，则车辆的出栈顺序为（）

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.将数组{8,23,4,16,77，-5,53,100}中的元素按从小到大的顺序排列，每次可以交换任意两个元素，最少需要交换（）次

A.4

B.5

C.6

D.7

94.完全二叉树和满二叉树的联系和区别？

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．先进先出算法FIFO

B．随机算法RAND

C．先进后出算法FILO

D．替换最近最少使用的块算法LRU

97.快速排序最坏情况下的时间复杂度是：

（）

A.O（nlog（n））

B.O（n2）

C.O（log（n））

D.O（n）

98.一个文本文件，大约有10000行，每行一个词，要求统计出其中最频繁出现的前十个词（le表示单词的平均长度）,给出时间复杂度分析。

（）

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.关于数据结构和算法，以下说法正确的是（）

A.数据的逻辑结构与所使用的计算机无关

B.数据的存储结构与数据处理的效率密切相关

C.数据的存储结构在计算机中所占的空间不一定是连续的

D.一种数据的逻辑结构只对应一种存储结构

E.算法的执行效率与数据的存储结构无关

F.算法的时间复杂度是指执行算法程序所需要的时间

G.在单链表中，只要指出表中任何一个节点的位置，就可以从他出发依次访问到链表中其他所有节点

H.在一个单链表中，已知q所指结点是p所指节点的前驱结点，若在p和q之间插入结点s，则执行，s->next=p;q->next=s;

I.在一个单链表中，若删除p所指节点的后续结点，则执行p=p->next;p->next=p->next->next

J.使用链表，可随机访问链表中的任何一个元素

100.调用printf函数可以分解为九个过程，请写出他们的排列顺序_________.

A.call指令

B.EBP出栈

C.函数参数压栈

D.收回局部变量空间

E.EBP压栈

F.在栈上保留局部变量

G.函数参数出栈

H.ret指令

I.打印输出字符串

102.在以下几种数据结构中，在执行数量相当的查找，删除和插入操作时，综合性能最好的数据结构是：

A.双向链表

B.分块链表

C.穿线二叉树

D.堆

103.广告系统为了做地理位置定向，将IPV4分割为627672个区间，并标识了地理位置信息，区间之间无重叠，用二分查找将IP地址映射到地理位置信息，

请问在最坏的情况下，需要查找多少步？

A．17

B．18

C．19

D．20

104.以入栈顺序作为输入，出栈作为输出，并以I代表入栈，O代表出栈，现将1,2,3,4顺序入栈，则栈操作序列IIIIOOOO后，输出4321；与输出1234相对应

的栈操作序列为IOIOIOIO.则若想得到输出为2314，则栈操作序列应为____.无法由栈操作序列而得到的输出有_____。

105.设一组初始记录关键字序列为（20,18,22,16,30,19），则根据这些初始关键字序列建成的初始堆为______________.

106.线性有序表（a1,a2,a3,….a256）是从小到大排列的，对一个给定的值k，用二分法检索表中与K相等的元素，在查找不成功的情况下，最多需要检索______次。

编程

1单链表

1：

编程实现一个单链表的建立。

2：

编程实现一个单链表的侧长。

3：

编程实现一个单链表的打印。

4：

编程实现一个单链表删除节点。

5：

编程实现单链表的插入。

6：

编程实现单链表的逆置。

2双链表

1：

编程实现双链表的建立。

2：

编程实现双链表的侧长。

3：

编程实现双链表