典型数据结构面试题

数据结构

1. 在一个单链表中p 所指结点之前插入一个s(值为e)所指结点时，可执行如下操作：

q=head;

while(q->next!=p) q=q->next;

s= new Node; s->data=e;

q->next= ; //填空

s->next= ; //填空

2.线性表的顺序存储结构是一种 C 的存储结构，而链式存储结构是一种_A__的存储结构。

A．随机存取B．索引存取C．顺序存取D．散列存取

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

A. 必须是连续的

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

C. 一定是不连续的

D. 连续或不连续都可以

4.在一个单链表中，已知q 所指结点是p 所指结点的前驱结点，若在q 和p 之间插入s 结点，则执行__C__。

A. s->next=p->next; p->next=s;

B. p->next=s->next; s->next=p;

C. q->next=s; s->next=p;

D. p->next=s; s->next=q;

5.在一个单链表中，若p 所指结点不是最后结点，在p 之后插入s 所指结点，则执行

_B___。

A. s->next=p; p->next=s;

B. s->next=p->next; p->next=s;

C. s->next=p->next; p=s; C. p->next=s; s->next=p;

6.在一个单链表中，若删除p 所指结点的后续结点，则执行__A__。

A. p->next= p->next->next；

B. p= p->next; p->next= p->next->next；

C. p->next= p->next;

D. p= p->next->next；

7.链表不具备的特点是_A___。

A 可随机访问任何一个元素C 无需事先估计存储空间大小

B 插入、删除操作不需要移动元素 D 所需存储空间与线性表长度成正比

8.以下关于线性表的说法不正确的是 C 。

A 线性表中的数据元素可以是数字、字符、记录等不同类型。

B 线性表中包含的数据元素个数不是任意的。

C 线性表中的每个结点都有且只有一个直接前趋和直接后继。D

存在这样的线性表：表中各结点都没有直接前趋和直接后继。

9.在一个长度为n 的顺序表中删除第i个元素，要移动个元素。如果要在第i 个元素前插入一个元素，要后移()个元素。N-I N-I+1

答案1.q->next=s; s->next=p;

2.A/C（这题是考察对概念的理解，可参考第7 题，“顺序表才能随即存取，而链表不可以”）

3.D

4.C

5.B

6.A

7.A(此题绝对选A，因为链表只能根据他的前一个结点才能找到下一个结点，不具备随即访问元素的功能)

8.C 9.n-i; n-i+1

第一章数据结构与算法

一.算法的基本概念

计算机解题的过程实际上是在实施某种算法，这种算法称为计算机算法。

1.算法的基本特征：可行性，确定性，有穷性，拥有足够的情报。

2.算法的基本要素：算法中对数据的运算和操作、算法的控制结构。

3.算法设计的基本方法：列举法、归纳法、递推、递归、减半递推技术、回溯法。

4.算法设计的要求：正确性、可读性、健壮性、效率与低存储量需求

二.算法的复杂度

1.算法的时间复杂度：指执行算法所需要的计算工作量

2.算法的空间复杂度：执行这个算法所需要的内存空间

三.数据结构的定义

1.数据的逻辑结构：反映数据元素之间的关系的数据元素集合的表示。数据的逻辑结构包

括集合、线形结构、树形结构和图形结构四种。

2.数据的存储结构：数据的逻辑结构在计算机存储空间种的存放形式称为数据的存储结构。常用的存储结构有顺序、链接、索引等存储结构。

四.数据结构的图形表示：

在数据结构中，没有前件的结点称为根结点；没有后件的结点成为终端结点。插入和删除

是对数据结构的两种基本运算。还有查找、分类、合并、分解、复制和修改等。

五.线性结构和非线性结构

根据数据结构中各数据元素之间前后件关系的复杂程度，一般将数据结构分为两大类型：

线性结构和非线性结构。

线性结构：非空数据结构满足：有且只有一个根结点；每个结点最多有一个前件，最多只

有一个后件。非线性结构：如果一个数据结构不是线性结构，称之为非线性结构。常见

的线性结构：线性表、栈、队列

六.线性表的定义

线性表是n 个元素构成的有限序列（A1，A2，A3……）。表中的每一个数据元素，除了第一个以外，有且只有一个前件。除了最后一个以外有且只有一个后件。即线性表是一个空表，或可以表示为（a1,a2,……an）, 其中ai(I=1,2,……n)是属于数据对象的元素，通常也称其为线性表中的一个结点。

非空线性表有如下一些特征：

（1）有且只有一个根结点a1,它无前件；

（2）有且只有一个终端结点an，它无后件；

（3）除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。线性表中结点的个数n 称为线性表的长度。当n=0时称为空表。

七.线性表的顺序存储结构

线性表的顺序表指的是用一组地址连续的存储单元依次存储线性表的数据元素。

线性表的顺序存储结构具备如下两个基本特征：

1.线性表中的所有元素所占的存储空间是连续的；

2.线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。

即线性表逻辑上相邻、物理也相邻，则已知第一个元素首地址和每个元素所占字节数，则

可求出任一个元素首地址。

假设线性表的每个元素需占用K个存储单元，并以所占的第一个单元的存储地址作为数据元素的存储位置。则线性表中第i+1个数据元素的存储位置LOC(ai+1)和第i 个数据元素的存储位置LOC(ai)之间满足下列关系:

LOC(ai+1)=LOC(ai)+K

LOC(ai)=LOC(a1)+(i-1)*K①

其中，LOC(a1)是线性表的第一个数据元素a1 的存储位置，通常称做线性表的起始位置或

基地址。

因为在顺序存储结构中，每个数据元素地址可以通过公式①计算得到，所以线性表的顺序

存储结构是随机存取的存储结构。

在线性表的顺序存储结构下，可以对线性表做以下运算：

插入、删除、查找、排序、分解、合并、复制、逆转

八.顺序表的插入运算

线性表的插入运算是指在表的第I个位置上，插入一个新结点x，使长度为n 的线性表

（a1,a2…ai…an）变成长度为n+1 的线性表(a1,a2…x,ai…an).

该算法的时间主要花费在循环的结点后移语句上，执行次数是n-I+1。

当I=n+1,最好情况，时间复杂度o(1) 当I=1,最坏情况，时间复杂度o(n)

算法的平均时间复杂度为o(n)

九.顺序表的删除运算

线性表的删除运算是指在表的第I个位置上，删除一个新结点x，使长度为n 的线性表

（a1,a2…ai…an）变成长度为n-1 的线性表(a1,a2…ai-1,ai+1…an).

当I=n,时间复杂度o(1),当I=1,时间复杂度o(n),平均时间复杂度为o(n)

十.栈及其基本运算

1.什么是栈？栈实际上也是一个线性表，只不过是一种特殊的线性表。栈是只能在表的一端进行插入和删除运算的线性表，通常称插入、删除这一端为栈顶（TOP），另一端为栈底（BOTTOM）。当表中没有元素时称为空栈。栈顶元素总是后被插入的元素，从而也是最先被删除的元素；栈底元素总是最先被插入的元素，从而也是最后才能被删除的元素。假设栈S=（a1,a2,a3,……an），则a1 称为栈底元素，an 称为栈顶元素。栈中元素按

a1,a2,a3……an 的次序进栈，退栈的第一个元素应该是栈顶元素。即后进先出。

2.栈的顺序存储及其运算

用S（1：M）作为栈的顺序存储空间。M为栈的最大容量。

栈的基本运算有三种：入栈、退栈与读栈顶元素。

入栈运算：在栈顶位置插入一个新元素。

首先将栈顶指针进一（TOP+1），然后将新元素插入到栈顶指针指向的位置。

退栈运算：指取出栈顶元素并赋给一个指定的变量。

首先将栈顶元素赋给一个指定的变量，然后将栈顶指针退一（TOP-1）

读栈顶元素：将栈顶元素赋给一个指定的变量。栈顶指针不会改变。

十一.队列及其基本运算

1.什么是队列

队列是只允许在一端删除，在另一端插入的顺序表，允许删除的一端叫做对头，允许插入

的一端叫做对尾。

队列的修改是先进先出。往队尾插入一个元素成为入队运算。从对头删除一个元素称为退

队运算。

2.循环队列及其运算

在实际应用中，队列的顺序存储结构一般采用循环队列的形式。所谓循环队列，就是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间。在循环队列中，，用队尾指针rear指向队列中的队尾元素，用排头指针front指向排头元素的前一个位置，因此，从排头指针front指向的后一个位置直到队尾指针rear 指向的位置之间所有的元素均为队列中的元素。

在实际使用循环队列时，为了能区分队满还是队列空，通常需要增加一个标志S：

队列空，则S=0，rear=front=m队列满，则S=1，rear=front=m

循环队列主要有两种基本运算：入队运算和退队运算

n入队运算

指在循环队列的队尾加入一个新元素，首先rear=rear+1,当rear=m+1 时，置rear=1,然后将新元素插入到队尾指针指向的位置。当S=1，rear=front,说明队列已满，不能进行入队运算，称为“上溢”。

n退队运算

指在循环队列的排头位置退出一个元素并赋给指定的变量。首先front=front+1,并当

front=m+1时，置front=1,然后将排头指针指向的元素赋给指定的变量。当循环队列为空

S=0，不能进行退队运算，这种情况成为“下溢”。

十二.线性单链表的结构及其基本运算

1.线性单链表的基本概念

一组任意的存储单元存储线性表的数据元素，因此，为了表示每个数据元素ai 与其直接后继数据元素ai+1 之间的逻辑关系，对数据元素ai 来说，除了存储其本身的信息之外，还需存储一个指示其直接后继的信息（即直接后继的存储位置）。这两部分信息组成数据元素ai 的存储映象，成为结点。它包括两个域：其中存储数据元素信息的域称为数据域，存储直接后继存储位置的域称为指针域。指针域中存储的信息称做指针或链。N 个结点链结成一个链表，即为线性表(a1,a2,……,an)的链式存储结构。又由于此链表的每个结点中只包含一个指针域，故又称线性链表或单链表。

有时，我们在单链表的第一个结点之前附设一个结点，称之为头结点，它指向表中第一个结点。头结点的数据域可以不存储任何信息，也可存储如线性表的长度等类的附加信息，头结点的指针域存储指向第一个结点的指针（即第一个元素结点的存储位置）。

在单链表中，取得第I 个数据元素必须从头指针出发寻找，因此，单链表是非随机存取的

存储结构链表的形式：单向，双向

2.线性单链表的存储结构

3 带链

3.带列的栈与队列

栈也是线性表，也可以采用链式存储结构。

队列也是线性表，也可以采用链式存储结构。

三.线性链表的基本运算1.线性链表的插入2.线性链表的删除

四.双向链表的结构及其基本运算

在双向链表的结点中有两个指针域，其一指向直接后继，另一指向直接前驱。

十五.循环链表的结构及其基本运算

是另一种形式的链式存储结构，它的特点是表中最后一个结点的指针域指向头结点，整个

链表形成一个环。因此，从表中任一结点出发均可找到表中其他结点。

十六.树的定义

树是一种简单的非线性结构。树型结构的特点：

1.每个结点只有一个前件，称为父结点，没有前件的结点只有一个，称为树的根结点。

2.每一个结点可以有多个后件结点，称为该结点的子结点。没有后件的结点称为叶子结点

3.一个结点所拥有的后件个数称为树的结点度

4.树的最大层次称为树的深度。

十七.二叉树的定义及其基本性质

1.二叉树是另一种树型结构，它的特点是每个结点至多只有二棵子树（即二叉树中不存在

度大于2 的结点），并且，二叉树的子树有左右之分，其次序不能任意颠倒。

2.二叉树的基本性质

①在二叉树的第I 层上至多有2i-1 个结点。

②深度为k 的二叉树至多有2k-1个结点(k>=1)

③在任意一个二叉树中，度为0的结点总是比度为2 的结点多一个；

④具有n 个结点的二叉树，其深度至少为[log2n]+1。

一棵深度为k 且有2k-1 个结点的二叉树称为满二叉树。这种树的特点是每一层上的结点数

都是最大结点数。

3.满二叉树与完全二叉树

满二叉树：除最后一层以外，每一层上的所有结点都有两个子结点。在满二叉树的第K 层

上有2K-1 个结点，且深度为M 的满二叉树右2M-1 个结点

完全二叉树：除最后一层以外，每一层上的结点数均达到最大值；在最后一层上只缺少右

边的若干结点。具有N个结点的完全二叉树的深度为[log2n]+1

完全二叉树总结点数为N，

若N 为奇数，则叶子结点数为（N+1）/2若N 为偶数，则叶子结点数为N/2

4.二叉树的存储结构

二叉树通常采用链式存储结构

二叉树具有下列重要特性：

性质1 在二叉树的第i 层上至多有2i-1 个结点(i≥1)。

利用归纳法容易证得此性质。

i=1 时，只有一个根结点。显然，2i-1=20=1 是对的。

现在假定对所有的j，1≤j

明j=i 时命题也成立。

由归纳假设：第i-1层上至多有2i-2 个结点。由于二叉树的每个结点的度至多为2，故在第i 层上的最大结点数为第i-1层上的最大结点数的2 倍，即2*2i-2=2i-1。

性质2 深度为k 的二叉树至多有2k-1 个结点，(k≥1)。

由性质1 可见，深度为k 的二叉树的最大结点数为

k k

∑(第i 层上的最大结点数) =∑2i-1=2k-1

i=1 i=1

性质3 对任何一棵二叉树T，如果其终端结点数为n0，度为2 的结点数为n2，则

n0=n2+1。

设n1 为二叉树T 中度为1 的结点数。因为二叉树中所有结点的度均小于或等于2所以

其结点总数为

n=n0+n1+n2(6—1)

再看二叉树中的分支数。除了根结点外，其余结点都有一个分支进入，设B 为分支总数，则n=B+1。由于这些分支是由度为1或2 的结点射出的，所以又有B=n1+2n2。

n=n1+2*n2+1 (6—2)

于是得由式(6—1)和(6—2)得n0=n2+1

十八.二叉树的遍历

就是遵从某种次序，访问二叉树中的所有结点，使得每个结点仅被访问一次。一般先左后右。

1.前序遍历DLR 首先访问根结点，然后遍历左子树，最后遍历右子树。

2.中序遍历LDR 首先遍历左子树，然后根结点，最后右子树

3.后序遍历LRD 首先遍历左子树，然后遍历右子树，最后访问根结点。

十九.顺序查找与二分查找

1.顺序查找在两种情况下只能用顺序查找：线性表为无序表、链式存储结构的有序表

2.二分查找只适用于顺序存储的有序表（从小到大）。

对于长度为N 的有序线性表，在最坏情况下，二分查找只需要比较log2N次，而顺序查找要比较N 次。排序：指将一个无序序列整理成按值非递减顺序排列的有序序列。二十.交换类排序法

冒泡排序与快速排序法属于交换类的排序方法

1.冒泡排序法假设线性表的长度为N，则在最坏的情况下，冒跑排序需要经过N/2遍的从前往后的扫描和N/2遍的从后往前的扫描，需要的比较次数为N（N-1）/2

2.快速排序法

二十一.选择类排序法1.简单选择排序法2.堆排序法

二十三.插入类排序法1.简单插入排序法2.希尔排序法

最坏情况下

最好情况下

说明

交换排序

冒泡排序

n(n-1)/2

最简单的交换排序。在待排序的元素序列基本有序的前提下，效率最高

快速排序

n(n-1)/2

O(Nlog2N)

插入排序

简单插入排序

n(n-1)/2

每个元素距其最终位置不远时适用

希尔排序

O(n1.5)

选择排序

简单选择排序

n(n-1)/2

堆排序

O(nlog2n)

适用于较大规模的线性表

练习：

1.栈和队列的共同特点是（只允许在端点处插入和删除元素）

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

3.栈底至栈顶依次存放元素A、B、C、D，在第五个元素E 入栈前，栈中元素可以出栈，则出栈序列可能是（DCBEA）

4.栈通常采用的两种存储结构是（线性存储结构和链表存储结构）

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

A.栈是非线性结构

B.栈是一种树状结构

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

D.栈有后进先出的特征

6.链表不具有的特点是（B）A.不必事先估计存储空间 B.可随机访问任一元素

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

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

7.用链表表示线性表的优点是（便于插入和删除操作）

8.在单链表中，增加头结点的目的是（方便运算的实现）

9.循环链表的主要优点是（从表中任一结点出发都能访问到整个链表）

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

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

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

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

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

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

A.必须是连续的

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

C.一定是不连续的

D.连续不连续都可以

12.线性表的顺序存储结构和线性表的链式存储结构分别是（随机存取的存储结构、顺序存取的存储结构）

13.树是结点的集合，它的根结点数目是（有且只有1）

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

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

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

17.已知二叉树后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是（cedba）

18.已知一棵二叉树前序遍历和中序遍历分别为ABDEGCFH和DBGEACHF，则该二叉树的后

序遍历为（DGEBHFCA）

19.若某二叉树的前序遍历访问顺序是abdgcefh，中序遍历访问顺序是dgbaechf，则其后序遍历的结点访问顺序是（gdbehfca）

20.数据库保护分为：安全性控制、完整性控制、并发性控制和数据的恢复。

1.在计算机中，算法是指（解题方案的准确而完整的描述）

1.在下列选项中，哪个不是一个算法一般应该具有的基本特征（无穷性）

说明：算法的四个基本特征是：可行性、确定性、有穷性和拥有足够的情报。

3.算法一般都可以用哪几种控制结构组合而成（顺序、选择、循环）

3.算法的时间复杂度是指（算法执行过程中所需要的基本运算次数）

3.算法的空间复杂度是指（执行过程中所需要的存储空间）

4.算法分析的目的是（分析算法的效率以求改进）

5.下列叙述正确的是（C）

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

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

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

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

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

8.数据结构中，与所使用的计算机无关的是数据的（C）

A．存储结构B．物理结构C．逻辑结构D．物理和存储结构

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

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

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

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

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

11.数据的存储结构是指（数据的逻辑结构在计算机中的表示）

12.数据的逻辑结构是指（反映数据元素之间逻辑关系的数据结构）

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

14.下列数据结构具有记忆功能的是（C）A．队列B．循环队列C．栈D．顺序表

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

A．线性链表B．栈C．循环链表D．顺序表

16. 递归算法一般需要利用（队列）实现。

17. 下列关于栈的叙述中正确的是（D）A．在栈中只能插入数据B．在栈中只能删除数据C．栈是先进先出的线性表D．栈是先进后出的线性表

18.栈底至栈顶依次存放元素A、B、C、D，在第五个元素E 入栈前，栈中元素可以出栈，则出栈序列可能是（DCBEA）

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

18.由两个栈共享一个存储空间的好处是（节省存储空间，降低上溢发生的机率）

19.应用程序在执行过程中，需要通过打印机输出数据时，一般先形成一个打印作业，将其存放在硬盘中的一个指定（队列）中，当打印机空闲时，就会按先来先服务的方式从中取出待打印的作业进行打印。

18.下列关于队列的叙述中正确的是（C）A．在队列中只能插入数据B．在队列中只能删除数据C．队列是先进先出的线性表D．队列是先进后出的线性表

23.下列叙述中，正确的是（D）A．线性链表中的各元素在存储空间中的位置必须是连续的B．线性链表中的表头元素一定存储在其他元素的前面C．线性链表中的各元素在存储空间中的位置不一定是连续的，但表头元素一定存储在其他元素的前面D．线性链表中的各元素在存储空间中的位置不一定是连续的，且各元素的存储顺序也是任意的

24.下列叙述中正确的是（A）A．线性表是线性结构B．栈与队列是非线性结构

C．线性链表是非线性结构D．二叉树是线性结构

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

A．每个元素都有一个直接前件和直接后件B．线性表中至少要有一个元素

C．表中诸元素的排列顺序必须是由小到大或由大到小D．除第一个元素和最后一个元素外，其余每个元素都有一个且只有一个直接前件和直接后件

26.线性表若采用链式存储结构时，要求内存中可用存储单元的地址（连续不连续都可以）

27. 链表不具有的特点是（B）A．不必事先估计存储空间B．可随机访问任一元素C．插入删除不需要移动元素D．所需空间与线性表长度成正比

28.非空的循环单链表head的尾结点（由p 所指向），满足（p->next=head）

28.与单向链表相比，双向链表的优点之一是（更容易访问相邻结点）

28.在（D）中，只要指出表中任何一个结点的位置，就可以从它出发依次访问到表中其他所有结点。A．线性单链表B．双向链表C．线性链表D．循环链表

31. 以下数据结构属于非线性数据结构的是（C）A．队列B．线性表C．二叉树D．栈

32.树是结点的集合，它的根结点数目是（有且只有1）

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

33.在一棵二叉树上第8 层的结点数最多是（128）注：2K-1

34.在深度为5 的满二叉树中，叶子结点的个数为（16）注：2n-1

35.在深度为5 的满二叉树中，共有（31）个结点。注：2n－1

33.设一棵完全二叉树共有699个结点，则在该二叉树中的叶子结点数为（350）

说明：完全二叉树总结点数为N，若N 为奇数，则叶子结点数为（N+1）/2；若N 为偶数，则叶子结点数为N/2。

38. 设有下列二叉树，对此二叉树中序遍历的结果是（B）

A．ABCDEF B．DBEAFC C．ABDECF D．DEBFCA

39.已知二叉树后序遍历序列是dabec，中序遍历序列debac，它的前序遍历序列是（cedba）

40.已知一棵二叉树前序遍历和中序遍历分别为ABDEGCFH和DBGEACHF，则该二叉树的后序遍历为（DGEBHFCA）

40.若某二叉树的前序遍历访问顺序是abdgcefh，中序遍历访问顺序是dgbaechf，则其后序

遍历的结点访问顺序是（gdbehfca）

42.串的长度是（串中所含字符的个数）

42.设有两个串p 和q，求q 在p 中首次出现位置的运算称做（模式匹配）

42.N 个顶点的连通图中边的条数至少为（N-1）

42.N 个顶点的强连通图的边数至少有（N）

43.对长度为n 的线性表进行顺序查找，在最坏情况下所需要的比较次数为（N）

42.最简单的交换排序方法是（冒泡排序）

42.假设线性表的长度为n，则在最坏情况下，冒泡排序需要的比较次数为（n(n-1)/2）

49. 在待排序的元素序列基本有序的前提下，效率最高的排序方法是（冒泡排序）

50.在最坏情况下，下列顺序方法中时间复杂度最小的是（堆排序）

51.希尔排序法属于（插入类排序）

52.堆排序法属于（选择类排序）

53.在下列几种排序方法中，要求内存量最大的是（归并排序）

54.已知数据表A 中每个元素距其最终位置不远，为节省时间，应采用（直接插入排序）

55. 算法的基本特征是可行性、确定性、有穷性和拥有足够的情报。

数据结构常见笔试题

1.栈和队列的共同特点是（只允许在端点处插入和删除元素） 2.栈通常采用的两种存储结构是（线性存储结构和链表存储结构） 3.链表不具有的特点是（B） A.不必事先估计存储空间 B.可随机访问任一元素 C.插入删除不需要移动元素 D.所需空间与线性表长度成正比 4.用链表表示线性表的优点是（便于插入和删除操作） 5.在单链表中，增加头结点的目的是（方便运算的实现） 6.循环链表的主要优点是（从表中任一结点出发都能访问到整个链表） 7.线性表若采用链式存储结构时，要求内存中可用存储单元的地址（D） A.必须是连续的 B.部分地址必须是连续的 C.一定是不连续的 D.连续不连续都可以 8.线性表的顺序存储结构和线性表的链式存储结构分别是（随机存取的存储结构、顺序存取的存储结构） 9.具有3个结点的二叉树有（5种形态） 10.设一棵二叉树中有3个叶子结点，有8个度为1的结点，则该二叉树中总的 结点数为（13）(n 0 = n 2 +1) 11.已知二叉树后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是（cedba） 12.若某二叉树的前序遍历访问顺序是abdgcefh，中序遍历访问顺序是dgbaechf，则其后序遍历的结点访问顺序是（gdbehfca） 13.数据库保护分为：安全性控制、完整性控制、并发性控制和数据的恢复。

1.在计算机中，算法是指（解题方案的准确而完整的描述） 2.算法一般都可以用哪几种控制结构组合而成（顺序、选择、循环） 3.算法的时间复杂度是指（算法执行过程中所需要的基本运算次数） 4.算法的空间复杂度是指（执行过程中所需要的存储空间） 5.算法分析的目的是（分析算法的效率以求改进） 6.下列叙述正确的是（C） A．算法的执行效率与数据的存储结构无关 B．算法的空间复杂度是指算法程序中指令（或语句）的条数 C．算法的有穷性是指算法必须能在执行有限个步骤之后终止 D．算法的时间复杂度是指执行算法程序所需要的时间 7.数据结构作为计算机的一门学科，主要研究数据的逻辑结构、对各种数据结构进行的运算，以及（数据的存储结构） 8.数据结构中，与所使用的计算机无关的是数据的（C） A．存储结构 B．物理结构 C．逻辑结构 D．物理和存储结构 9.下列叙述中，错误的是（B） A．数据的存储结构与数据处理的效率密切相关 B．数据的存储结构与数据处理的效率无关 C．数据的存储结构在计算机中所占的空间不一定是连续的 D．一种数据的逻辑结构可以有多种存储结构 10.数据的存储结构是指（数据的逻辑结构在计算机中的表示） 11.数据的逻辑结构是指（反映数据元素之间逻辑关系的数据结构） 12.根据数据结构中各数据元素之间前后件关系的复杂程度，一般将数据结构分为（线性结构和非线性结构） 13.下列数据结构具有记忆功能的是（C） A．队列 B．循环队列 C．栈 D．顺序表 14.递归算法一般需要利用（栈）实现。 15.由两个栈共享一个存储空间的好处是（节省存储空间，降低上溢发生的机率）

力 扣 数 据 结 构 与 算 法

前端如何搞定数据结构与算法(先导篇) 「观感度：?」 「口味：锅包肉」 「烹饪时间：20min」 本文已收录在Github? 为什么要学习数据结构与算法？ 在0202年的今天，由于每天被无数的信息轰炸，大多数人已经变得越来越浮躁了，并且丧失了独立思考的能力。 你可能会经常听到这样的感慨： 技术人究竟能走多远？我遇到了天花板 35岁的程序员要如何面对中年危机？ 技术更新太快，好累，学不动了 然后，你也变得焦虑起来。那你有没有静下心来想过，如何才能抵御年龄增长并且使自己增值呢？ 无非是终身学习，持续修炼自己的内功。内功也就是基础知识和核心概念，这些轰轰烈烈发展的技术本质，其实都是基础知识，也就是我们在大学里学过的基础课-程。 操作系统 计算机组成原理 计算机网络 编译原理

设计模式 数据结构与算法 这也就是为什么越靠谱的面试官越注重你基础知识的掌握程度，为什么越牛的的企业越重视你的算法能力。因为当你拥有了这些，你已经比大多数人优秀了。你的天花板由你自己来决定，大家口中的中年危机可能并不会成为你的危机。新技术来临时，你对它的本质会看得更加透彻，学起来会一通百通。这样的人才，公司培养你也会花费更少的成本。 (不过，一辈子做个开开心心的 CRUD Boy 也是一种选择。) 数据结构与算法之间的关系 Rob Pikes 5 Rules of Programming中的第五条是这样说的： Data dominates. If youve chosen the right data structures and organized things well, the algorithms will almost always be self-evident. Data structures, not algorithms, are central to programming. 数据占主导。如果您选择了正确的数据结构并组织得当，那么这些算法几乎总是不言而喻的。数据结构而非算法是编程的核心。 瑞士计算机科学家，Algol W，Modula，Oberon 和 Pascal 语言的设计师 Niklaus Emil Wirth 写过一本非常经典的书《Algorithms + Data Structures = Programs》，即算法 + 数据结构 = 程序。 我们可以得出结论，数据结构与算法之间是相辅相成的关系。数据结构服务于算法，算法作用于特定的数据结构之上。 数据结构与算法好难，怎么学？

腾讯校园招聘数据结构笔试试题

腾讯校园招聘数据结构笔试试题 (一)不定项选择题(25*4) 1. 使用深度优先算法遍历下图，遍历的顺序为（） A ABCDEFG B ABDCFEG C ABDECFG D ABCDFEG 2. 输入序列ABCABC经过栈操作变成ABCCBA，下面哪些是可能的栈操作( ) A. push pop push pop push pop pushpush push pop pop pop B. push push push push push push poppop pop pop pop pop C. push push push pop pop pop pushpush pop pop push pop D. push push push push pop pushpop push pop pop pop pop 3. 下列关键码序列哪些是一个堆( ) A. 90 31 53 23 16 48 B 90 48 31 53 16 23 C 16 53 23 90 3148 D.1631 23 90 53 48 4. 稀疏矩阵压缩的存储方法是：（） A 三元组 B 二维数组 C 散列 D 十字链表 5. 二叉树的后序排列DBEFCA，中序排列DBAECF，那么对其做先序线索化二叉树，节点E的线索化指向节点（） A BC B A C C DF D CF 6. 线性结构的是（） A 串 B 链式存储栈C顺序存储栈 D 顺序存储二叉树 7. Linux命令是哪些（） A ls B mkdir Cmagnify D man 8. Unix系统中，适合任意两个进程通信的是（） A FIFO B PIPE C Message Queue D sharememory 9. Windows系统中，不适合进程通讯的是（） A 临界区 B 互斥量 C 信号量 D 事件 10. 下面的内存管理模式中，会产生外零头的是（） A 页式 B段式C 请求页式 D 请求段式 11. Linux执行ls，会引起哪些系统调用（） A nmap B read C execve D fork 12. a 是二维数组，a[j]的指针访问方式为：（） A *(a+i+j) B *(*(a+i)+j) C *(a+i)+j D *a+i+j 13 输出以下结果： #define add(a,b) a+b;

数据结构面试专题

数据结构面试专题 1、常用数据结构简介 数据结构是指相互之间存在着一种或多种关系的数据元素的集合和该集合中数据元素间的关系组成。常用的数据有：数组、栈、队列、链表、树、图、堆、散列表。 1）数组：在内存中连续存储多个元素的结构。数组元素通过下标访问，下标从0开始。优点：访问速度快；缺点：数组大小固定后无法扩容，只能存储一种类型的数据，添加删除操作慢。适用场景：适用于需频繁查找，对存储空间要求不高，很少添加删除。 2）栈：一种特殊的线性表，只可以在栈顶操作，先进后出，从栈顶放入元素叫入栈，从栈顶取出元素叫出栈。应用场景：用于实现递归功能，如斐波那契数列。 3）队列：一种线性表，在列表一端添加元素，另一端取出，先进先出。使用场景：多线程阻塞队列管理中。 4）链表：物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表的指针地址实现，每个元素包含两个结点，一个是存储元素的数据域，一个是指向下一个结点地址的指针域。有单链表、双向链表、循环链表。优点：可以任意加减元素，不需要初始化容量，添加删除元素只需改变前后两个元素结点的指针域即可。缺点：因为含有大量指针域，固占用空间大，查找耗时。适用场景：数据量小，需频繁增加删除操作。 5）树：由n个有限节点组成一种具有层次关系的集合。二叉树（每个结点最多有两个子树，结点的度最大为2，左子树和右子树有顺序）、红黑树（HashMap底层源码）、B+树（mysql 的数据库索引结构） 6）散列表（哈希表）：根据键值对来存储访问。 7）堆：堆中某个节点的值总是不大于或不小于其父节点的值，堆总是一棵完全二叉树。8）图：由结点的有穷集合V和边的集合E组成。 2、并发集合了解哪些？ 1）并发List，包括Vector和CopyOnWriteArrayList是两个线程安全的List，Vector读写操作都用了同步，CopyOnWriteArrayList在写的时候会复制一个副本，对副本写，写完用副本替换原值，读时不需要同步。 2）并发Set，CopyOnWriteArraySet基于CopyOnWriteArrayList来实现的，不允许存在重复的对象。 3）并发Map，ConcurrentHashMap，内部实现了锁分离，get操作是无锁的。

[第1题-60题汇总]微软数据结构+算法面试100题

精选微软等公司数据结构 精选微软等公司数据结构++算法面试100题 -----[第1题-60题总] 资源说明： 此份，是为微软等公司数据结构+算法面试100题，之前60题的汇总。 总结整理了前第1题-第60题。特此并作此一份上传。以飨各位。:)。 -------------------------------- 相关资源，包括答案，下载地址： [答案V0.2版]精选微软数据结构+算法面试100题[前20题]--答案修正 https://www.doczj.com/doc/6310984171.html,/source/2813890 //此份答案是针对最初的V0.1版本，进行的校正与修正。 [答案V0.1版]精选微软数据结构+算法面试100题[前25题] https://www.doczj.com/doc/6310984171.html,/source/2796735 [第二部分]精选微软等公司结构+算法面试100题[前41-60题]： https://www.doczj.com/doc/6310984171.html,/source/2811703 [第一部分]精选微软等公司数据结构+算法经典面试100题[1-40题] https://www.doczj.com/doc/6310984171.html,/source/2778852 更多资源，下载地址： http://v_july_https://www.doczj.com/doc/6310984171.html,/ 很快，我将公布第21-40题的答案，敬请期待。:).. 如果你对以下的前第1-60题，有好的思路，和算法，欢迎跟帖回复， 或者，联系我，发至我的邮箱， zhoulei0907@https://www.doczj.com/doc/6310984171.html,。 My CSDN Blog：https://www.doczj.com/doc/6310984171.html,/v_JULY_v My sina Blog：https://www.doczj.com/doc/6310984171.html,/shitou009 帖子维护地址： [整理]算法面试：精选微软经典的算法面试100题[前1-60题] https://www.doczj.com/doc/6310984171.html,/u/20101023/20/5652ccd7-d510-4c10-9671-307a56006e6d.html -------------------------------------- July、2010、/11.12.请享用。:)。 1

经典数据结构面试题(含答案)

.栈通常采用的两种存储结构是______________________ .用链表表示线性表的优点是_______________________ 8.在单链表中，增加头结点的目的是___________________ 9.循环链表的主要优点是________________________- 12.线性表的顺序存储结构和线性表的链式存储结构分别是__________________________ 13.树是结点的集合，它的根结点数目是_____________________ 14.在深度为5的满二叉树中，叶子结点的个数为_______________ 15.具有3个结点的二叉树有（_____________________ 16.设一棵二叉树中有3个叶子结点，有8个度为1的结点，则该二叉树中总的结点数为____________________ 17.已知二叉树后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是____________________________ 18.已知一棵二叉树前序遍历和中序遍历分别为ABDEGCFH和DBGEACHF，则该二叉树的后序遍历为______________________ 19.若某二叉树的前序遍历访问顺序是abdgcefh，中序遍历访问顺序是dgbaechf，则其后序遍历的结点访问顺序是_______________________ 20.数据库保护分为：安全性控制、完整性控制、并发性控制和数据的恢复。 在计算机中，算法是指_______________________ 算法一般都可以用哪几种控制结构组合而成_____________________ .算法的时间复杂度是指______________________ 5. 算法的空间复杂度是指__________________________ 6. 算法分析的目的是__________________________

SQL数据库面试题目及其答案

1．触发器的作用？ 答： 触发器是一中特殊的存储过程，主要是通过事件来触发而被执行的。 它可以强化约束，来维护数据的完整性和一致性，可以跟踪数据库内的操作从而不允许未经许可的更新和变化。可以联级运算。如，某表上的触发器上包含对另一个表的数据操作，而该操作又会导致该表触发器被触发。 2．什么是存储过程？用什么来调用？ 答： 存储过程是一个预编译的SQL语句，优点是允许模块化的设计，就是说只需创建一次，以后在该程序中就可以调用多次。如果某次操作需要执行多次SQL，使用存储过程比单纯SQL语句执行要快。可以用一个命令对象来调用存储过程。 3．索引的作用？和它的优点缺点是什么？ 答： 索引就一种特殊的查询表，数据库的搜索引擎可以利用它加速对数据的检索。它很类似与现实生活中书的目录，不需要查询整本书内容就可以找到想要的数据。索引可以是唯一的，创建索引允许指定单个列或者是多个列。 缺点是它减慢了数据录入的速度，同时也增加了数据库的尺寸大小。 3。什么是内存泄漏？ 答： 一般我们所说的内存泄漏指的是堆内存的泄漏。堆内存是程序从堆中为其分配的，大小任意的，使用完后要显示释放内存。当应用程序用关键字new等创建对象时，就从堆中为它分配一块内存，使用完后程序调用free或者delete 释放该内存，否则就说该内存就不能被使用，我们就说该内存被泄漏了。

4．维护数据库的完整性和一致性，你喜欢用触发器还是自写业务逻辑？为什 么？ 答： 我是这样做的，尽可能使用约束，如check,主键，外键，非空字段等来约束，这样做效率最高，也最方便。其次是使用触发器，这种方法可以保证，无论什么业务系统访问数据库都可以保证数据的完整新和一致性。最后考虑的是自写业务逻辑，但这样做麻烦，编程复杂，效率低下。 5．什么是事务？什么是锁？ 答： 事务就是被绑定在一起作为一个逻辑工作单元的SQL语句分组，如果任何一个语句操作失败那么整个操作就被失败，以后操作就会回滚到操作前状态，或者是上有个节点。为了确保要么执行，要么不执行，就可以使用事务。 要将有组语句作为事务考虑，就需要通过ACID测试，即原子性，一致性，隔离性和持久性。 锁： 在所以的DBMS中，锁是实现事务的关键，锁可以保证事务的完整性和并发性。与现实生活中锁一样，它可以使某些数据的拥有者，在某段时间内不能使用某些数据或数据结构。当然锁还分级别的。 6．"什么叫视图？游标是什么？ 答： 视图是一种虚拟的表，具有和物理表相同的功能。可以对视图进行增，改，查，操作，试图通常是有一个表或者多个表的行或列的子集。对视图的修改不影响基本表。它使得我们获取数据更容易，相比多表查询。 游标：

阿里校园招聘历年经典面试题汇总：算法工程师

阿里校园招聘历年经典面试题汇总：算法工程师 （1）、jvm 原理 （2）、minor GC 与 Full GC （3）、HashMap 实现原理 （4）、java.util.concurrent 包下使用过哪些 （5）、concurrentMap 和 HashMap 区别 （6）、信号量是什么，怎么使用？ （7）、阻塞队列了解吗？怎么使用？ （8）、JAVA NIO 是什么？ （9）、类加载机制是怎样的 （10）、什么是幂等性 （11）、有哪些 JVM 调优经验 （12）、分布式 CAP 了解吗？ （13）、hdfs怎么添加Datanode,添加后hdfs会有什么操作？ （14）、Hbase 跟关系数据库对比优缺点？为什么 Hbase 索引速度快 （15）、Hbase 大压缩与小压缩区别 （16）、Hive 与 Hbase 的使用场景 （17）、简单说说Spark功能，spark 与hive有无依赖关系？ （18）、zookeeper 有什么应用场景，怎么选举的？3 个节点挂掉一个能正常工作吗？ （19）、Hbase 中 zookeaper 作用 （20）、Hbase 写操作什么时候返回 （21）、mysql 有哪些存储引擎？各自特点 （22）、用过哪些设计模式？怎样实现线程安全单例模式？ （23）、用过哪些RPC框架？ （24）、什么是AOP？ （25）、决策树算法怎么实现的？ （26）、java垃圾回收会出现不可回收的对象吗？怎么解决内存泄露问题？怎么

定位问题源？ （27）、终止线程有几种方式？终止线程标记变量为什么是 valotile 类型？（28）、用过哪些并发的数据结构？ cyclicBarrier 什么功能？信号量作用？数据库读写阻塞怎么解决？ （29）、乐观锁与悲观锁，怎么实现乐观锁？ （30）、开发过分布式框架？怎么实现分布式事务？ （31）、spark streaming与storm区别？ （32）、找到最大子数组的 start,和end下标 （33）、用过 CDH中什么任务调度？ （34）、spark streaming时间间隔设置很小会出现什么状况？ （35）、搜索引擎了解多少？你认为搜索引擎的难点在哪里？ （36）、RPC 了解吗？怎么监控 RPC 状态，找出出现问题的 RPC 连接？（37）、spring 框架了解多少？ （38）、flume应用场景 （39）、找出一串字符中第一个不重复字符的下标。 点击查看详细面经〉〉〉〉〉〉〉〉〉〉〉〉 更多精品干货>>>>>>>>>>> 更多阿里机器学习/数据挖掘经典面试题 其他名企机器学习/数据挖掘经典面试题

经典数据结构面试题(含答案)

栈和队列的共同特点是__________________________ .栈通常采用的两种存储结构是______________________ .用链表表示线性表的优点是_______________________ 8.在单链表中，增加头结点的目的是___________________ 9.循环链表的主要优点是________________________- 12.线性表的顺序存储结构和线性表的链式存储结构分别是 __________________________ 13.树是结点的集合，它的根结点数目是_____________________ 14.在深度为5的满二叉树中，叶子结点的个数为_______________ 15.具有3个结点的二叉树有（_____________________ 16.设一棵二叉树中有3个叶子结点，有8个度为1的结点，则该二叉树中总的结点数为____________________ 17.已知二叉树后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是 ____________________________ 18.已知一棵二叉树前序遍历和中序遍历分别为ABDEGCFH和DBGEACHF，则该二叉树的后序遍历为______________________ 19.若某二叉树的前序遍历访问顺序是abdgcefh，中序遍历访问顺序是dgbaechf，则其后序遍历的结点访问顺序是_______________________ 20.数据库保护分为：安全性控制、完整性控制、并发性控制和数据的恢复。 在计算机中，算法是指_______________________ 算法一般都可以用哪几种控制结构组合而成_____________________ .算法的时间复杂度是指______________________ 5. 算法的空间复杂度是指__________________________ 6. 算法分析的目的是__________________________

数据结构算法面试100题

数据结构+算法面试100题~~~摘自CSDN，作者July 1.把二元查找树转变成排序的双向链表（树） 题目： 输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。 要求不能创建任何新的结点，只调整指针的指向。 10 / / 6 14 / / / / 4 8 12 16 转换成双向链表 4=6=8=10=12=14=16。 首先我们定义的二元查找树节点的数据结构如下： struct BSTreeNode { int m_nValue; // value of node BSTreeNode *m_pLeft; // left child of node BSTreeNode *m_pRight; // right child of node }; 2.设计包含min函数的栈（栈） 定义栈的数据结构，要求添加一个min函数，能够得到栈的最小元素。 要求函数min、push以及pop的时间复杂度都是O(1)。 参见C:\Users\Administrator\Desktop\demo\Stack 分析：min时间复杂度要达到O(1)，需要我们在栈中存储最小元素 3.求子数组的最大和（数组） 题目： 输入一个整形数组，数组里有正数也有负数。 数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。求所有子数组的和的最大值。要求时间复杂度为O(n)。 例如输入的数组为1, -2, 3, 10, -4, 7, 2, -5，和最大的子数组为3, 10, -4, 7, 2，因此输出为该子数组的和18。 分析：根据dp思想 #include #define N 8 int main() { int i, a[N] = {1, -2, 3, 10, -4, 7, 2, -5}; int from[N], result[N], max;

算法大全-面试题-数据结构

一、单链表 目录 1.单链表反转 2.找出单链表的倒数第4个元素 3.找出单链表的中间元素 4.删除无头单链表的一个节点 5.两个不交叉的有序链表的合并 6.有个二级单链表，其中每个元素都含有一个指向一个单链表的指针。写程序把这个二级链表称一级单链表。 7.单链表交换任意两个元素（不包括表头） 8.判断单链表是否有环？如何找到环的“起始”点？如何知道环的长度？ 9.判断两个单链表是否相交 10.两个单链表相交，计算相交点 11.用链表模拟大整数加法运算 12.单链表排序 13.删除单链表中重复的元素 首先写一个单链表的C#实现，这是我们的基石： public class Link { public Link Next; public string Data; public Link(Link next, string data) { this.Next = next; this.Data = data; } } 其中，我们需要人为地在单链表前面加一个空节点，称其为head。例如，一个单链表是1->2->5，如图所示： 对一个单链表的遍历如下所示： static void Main(string[] args) { Link head = GenerateLink(); Link curr = head; while (curr != null)

{ Console.WriteLine(curr.Data); curr = curr.Next; } } 1.单链表反转 这道题目有两种算法，既然是要反转，那么肯定是要破坏原有的数据结构的：算法1：我们需要额外的两个变量来存储当前节点curr的下一个节点next、再下一个节点nextnext： public static Link ReverseLink1(Link head) { Link curr = head.Next; Link next = null; Link nextnext = null; //if no elements or only one element exists if (curr == null || curr.Next == null) { return head; } //if more than one element while (curr.Next != null) { next = curr.Next; //1 nextnext = next.Next; //2 next.Next = head.Next; //3 head.Next = next; //4 curr.Next = nextnext; //5 } return head; } 算法的核心是while循环中的5句话 我们发现，curr始终指向第1个元素。 此外，出于编程的严谨性，还要考虑2种极特殊的情况：没有元素的单链表，以及只有一个元素的单链表，都是不需要反转的。

典型数据结构面试题

数据结构 1?在一个单链表中p所指结点之前插入一个s (值为e)所指结点时，可执行如下操作： q=head; while (q->next!=p)q=q->next; s= newNode;s->data=e; q->next=;// 填空 s->next=;// 填空 2.线性表的顺序存储结构是一种的存储结构，而链式存储结构是一种___的 存储结构。 A.随机存取 B.索引存取 C.顺序存取 D.散列存取 3.线性表若采用链式存储结构时，要求内存中可用存储单元的地址___。 A.必须是连续的 B.部分地址必须是连续的 C.一定是不连续的 D.连续或不连续都可以 4?在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p 之间插入s结点，则执行_。 A.s->next=p->next;p->next=s; B.p->next=s->next;s->next=p;

C.q->next=s;s->next=p; D.p->next=s;s->next=q; 5.在一个单链表中，若p 所指结点不是最后结点，在p 之后插入s 所指结点，则执行__。 A.s->next=p;p->next=s; B.s->next=p->next;p->next=s; C.s->next=p->next;p=s; C. p->next=s;s->next=p; 6.在一个单链表中，若删除p 所指结点的后续结点，则执行__。 A.p->next= p->next->next； B.p= p->next;p->next= p->next->nex；t C.p->next= p->next; D.p= p->next->next； 7.链表不具备的特点是__。 A 可随机访问任何一个元素 B 插入、删除操作不需要移动元素 C无需事先估计存储空间大小D所需存储空间与线性表长度成正比 8.以下关于线性表的说法不正确的是。 A 线性表中的数据元素可以是数字、字符、记录等不同类型。 B 线性表中包含的数据元素个数不是任意的。 C 线性表中的每个结点都有且只有一个直接前趋和直接后继。 D 存在这样的线性表：表中各结点都没有直接前趋和直接后继。 9?在一个长度为n的顺序表中删除第i个元素，要移动个元素。如果要在第 i 个元素前插入一个元素，要后移（）个元素。N-I N-I+1

2021年经典数据结构面试题含答案

栈和队列共同特点是__________________________ .栈普通采用两种存储构造是______________________ .用链表表达线性表长处是_______________________ 8.在单链表中，增长头结点目是___________________ 9.循环链表重要长处是________________________- 12.线性表顺序存储构造和线性表链式存储构造分别是__________________________ 13.树是结点集合，它根结点数目是_____________________ 14.在深度为5满二叉树中，叶子结点个数为_______________ 15.具备3个结点二叉树有（_____________________ 16.设一棵二叉树中有3个叶子结点，有8个度为1结点，则该二叉树中总结点数为 ____________________ 17.已知二叉树后序遍历序列是dabec，中序遍历序列是debac，它前序遍历序列是 ____________________________ 18.已知一棵二叉树前序遍历和中序遍历分别为ABDEGCFH和DBGEACHF，则该二叉树后序遍历为______________________

19.若某二叉树前序遍历访问顺序是abdgcefh，中序遍历访问顺序是dgbaechf，则其后序遍历结点访问顺序是_______________________ 20.数据库保护分为：安全性控制、完整性控制、并发性控制和数据恢复。 在计算机中，算法是指_______________________ 算法普通都可以用哪几种控制构造组合而成_____________________ .算法时间复杂度是指______________________ 5. 算法空间复杂度是指__________________________ 6. 算法分析目是__________________________ 11. 数据存储构造是指_________________________ 12. 数据逻辑构造是指（_______________________________ 13. 依照数据构造中各数据元素之间先后件关系复杂限度，普通将数据构造分为 __________________________________ 16. 递归算法普通需要运用_______________________实现。

22道数据结构算法面试题

微软的22道数据结构算法面试题（含答案）1、反转一个链表。循环算法。 1 List reverse(List l) { 2 if(!l) return l; 3 list cur = l.next; 4 list pre = l; 5 list tmp; 6 pre.next = null; 7 while ( cur ) { 8 tmp = cur; 9 cur = cur.next; 10 tmp.next = pre; 11 pre = tmp; 12 } 13 return tmp; 14 } 2、反转一个链表。递归算法。 1 List resverse(list l) { 2 if(!l || !l.next) return l; 3 4 List n = reverse(l.next); 5 l.next.next = l; 6 l.next=null; 7 } 8 return n; 9 } 3、广度优先遍历二叉树。 1 void BST(Tree t) { 2 Queue q = new Queue(); 3 q.enque(t); 4 Tree t = q.deque(); 5 while(t) { 6 System.out.println(t.value); 7 q.enque(t.left);

9 t = q.deque(); 10 } 11 } ---------------------- 1class Node { 2 Tree t; 3 Node next; 4 } 5class Queue { 6 Node head; 7 Node tail; 8 public void enque(Tree t){ 9 Node n = new Node(); 10 n.t = t; 11 if(!tail){ 12 tail = head = n; 13 } else { 14 tail.next = n; 15 tail = n; 16 } 17 } 18 public Tree deque() { 19 if (!head) { 20 return null; 21 } else { 22 Node n = head; 23 head = head.next; 24 return n.t; 25 } 26} 4、输出一个字符串所有排列。注意有重复字符。 1char[] p; 2void perm(char s[], int i, int n){ 3 int j; 4 char temp; 5 for(j=0;j

经典数据结构面试题(含答案)

栈与队列得共同特点就是_＿___＿_______＿＿__＿_______＿ 、栈通常采用得两种存储结构就是_＿____＿__________＿_＿__ 、用链表表示线性表得优点就是_＿＿＿______＿______＿＿＿___ ８、在单链表中，增加头结点得目得就是＿___＿__＿_＿______＿_＿ ?9、循环链表得主要优点就是＿_＿___＿____________＿＿_＿_- １2、线性表得顺序存储结构与线性表得链式存储结构分别就是＿__＿＿______＿＿＿____＿_＿___＿＿ 13、树就是结点得集合,它得根结点数目就是_＿＿＿_＿_____________＿_ １4、在深度为5得满二叉树中,叶子结点得个数为_＿________＿_＿＿_ ?15、具有3个结点得二叉树有（___＿____＿___＿＿____＿__ １6、设一棵二叉树中有3个叶子结点,有8个度为1得结点，则该二叉树中总得结点数为＿__＿__＿＿______＿_＿___ 1７、已知二叉树后序遍历序列就是dabec,中序遍历序列就是debac，它得前序遍历序列就是＿＿____________＿_______＿__＿_＿ 18、已知一棵二叉树前序遍历与中序遍历分别为ABDＥＧＣFＨ与DBＧEACＨF,则该二叉树得后序遍历为＿___________＿___＿____＿ １９、若某二叉树得前序遍历访问顺序就是abｄgceｆh,中序遍历访问顺序就是ｄgbaec ｈｆ，则其后序遍历得结点访问顺序就是___＿_＿________＿＿＿_＿_＿_＿ ?２0、数据库保护分为:安全性控制、完整性控制、并发性控制与数据得恢复。 在计算机中,算法就是指_________＿_______＿_＿___ 算法一般都可以用哪几种控制结构组合而成＿_＿_____＿______＿____＿ 、算法得时间复杂度就是指_＿_＿_＿＿___＿＿_＿__＿_____ 5、算法得空间复杂度就是指_＿__＿_＿__＿__＿__＿＿___＿＿_＿＿＿ ?6、算法分析得目得就是＿＿___＿____________＿__＿__＿_ １１、数据得存储结构就是指＿＿___＿_______＿__＿__＿____＿ 1２、数据得逻辑结构就是指（__＿___＿＿__＿＿_＿＿____＿_＿_＿＿_____＿ ?13、根据数据结构中各数据元素之间前后件关系得复杂程度，一般将数据结构分为__＿___＿____＿＿＿_____＿__＿__＿_＿_＿____ １６、递归算法一般需要利用___＿______＿_＿＿__＿＿_＿＿__实现。 28、非空得循环单链表ｈeaｄ得尾结点(由p所指向),满足(______＿__＿__＿_______＿ 29、与单向链表相比,双向链表得优点之一就是__＿____＿_＿_____＿_＿＿___＿___＿_--

数据结构及算法招聘笔试及面试

数据结构及算法招聘笔试及面试 一、综述： 招聘考试中笔试偏基础知识考察，面试偏项目经验和算法的灵活应用的考察。考察的内容可以分为知识型题目和智力测试类的题目，平时可以充分准备知识型的题目，而智力测试类的题目在知名大公司的考察较多，可以多看一些典型的题目，争取能在应试中将其转换为记忆力的测试。 在软件类的应聘考试中要坚持“两个中心，三个基本点”。“两个中心”是以数据结构与算法为中心。对于计算机专业的人才来说，数据结构，算法应该是基石，也就是重中之重。这一点在牛企中更为突出，像百度，微软，google这样的企业，对这“两个中心”的要求更是高。“三个基本点”分别为程序设计语言，操作系统，数据库及网络。程序设计语言无论是java或者c++，你都要精通，也就是说要非常熟练。高水平的公司，对应聘者的综合素质跟专业知识要求都很高，专业知识方面数据结构算法尤为重要，所以大家如果有志于目前牛气的公司的话，一定要真的做到“精通” 数据结构与算法，其中排序算法最最重要。这里说的精通不但要能快速书写基本的典型的算法，而且要真正理解，灵活运用，做到举一反三，考察往往不是原原本本的考察知识点，而是进行略微的变化再考察，如果理解的不深刻，往往调到陷阱中。所以，大家要养成“反思”的习惯，即经常思考所学的知识。同时要多读书，多读经典的书籍，例如：《编程之美》，《C陷阱与缺陷》，《C和指针》，《计算机程序设计艺术（共四卷）》《数据结构C语言版》。 二：考察点 结合数据结构的知识点，主要考察的内容如下： 1、数据结构本质的理解：数据结构是解决复杂程序的建模问题的，如何将现实世界中的复杂多样的关系（1：1，1：n，n:m）在计算机的简单的一维内存结构中进行处理，如何利用现有的计算机资源高效的解决问题。逻辑结构、存储结构的关系。 2、算法的渐近时间复杂度和渐近空间复杂度的估计。 3、线性表的单链表和双向链表的操作 4、栈和队列应用，主要是递归算法如何转换为非递归算法。 5、串的模式匹配算法，数组的地址下标计算，和特殊矩阵的压缩存储，特别是稀疏矩阵的三元组存储结构和一次定位的快速转秩算法。 6、二叉树的5条性质，二叉树的四种遍历算法的递归和非递归实现，及其时间和空间复杂度。哈夫曼树的概念、存储结

数据结构与算法面试题

目录 1. 数组 (3) 2. 链表 (5) 3. 栈 (9) 4. 队列 (10) 5. 堆（优先队列） (12) 6. 二叉树 (15) 7. 二叉查找树 (24) 8. 字典树 (26) 9. 平衡树（AVL） (26) 10. 红黑树 (26) 11. B树/B+树 (28) 12. 哈希 (29) 13. 图 (31) 14. 字符串 (33) 15. 排序 (36) 16. 二分查找 (40) 17. 跳跃列表 (41) 18. 动态规划 (42) 1.数组 应用场景： 1）数据比较少 2）经常做的运算是按序号访问数据元素 面试题 选择题： 1）对于长度为n的线性表，建立其对应的单链表的时间复杂度为（）。 O(1) O(log2n) O(n) O(n^2) 2）下列哪些不是线性表？ 队列 栈 关联数组 链表 3）稀疏矩阵一般的压缩存储方法有两种,即() 二维数组和三维数组 三元组和散列 三元组和十字链表 散列和十字链表 4）将10阶对称矩阵压缩存储到一维数组A中，则数组A的长度最少为

100 40 55 80 5） 设A是n*n的对称矩阵，将A的对角线及对角线上方的元素以列为主的次序存放在一维数组B[1..n（n+1）/2]中，对上述任一元素aij (1≤i，j≤n，且i≤j)在B中的位置为（） i（i-1）/2+j j（j-1）/2+i j（j-1）/2+i-1 i（i-1）/2+j-1 6）若有定义: int c[4][5],( *pc)[5]; pc=c; 那么，下列对数组C的元素引用正确的是( )。 pc+1 * (pc+3) * (pc+1) +3 * (*pc+2) 问答题： 1）数组和链表的区别 思路： 从逻辑结构上来看，数组必须实现定于固定的长度，不能适应数据动态增减的情况，即数组的大小一旦定义就不能改变。当数据增加是，可能超过原先定义的元素的个数；当数据减少时，造成内存浪费；链表动态进行存储分配，可以适应数据动态地增减的情况，且可以方便地插入、删除数据项。 从内存存储的角度看；数组从栈中分配空间（用new则在堆上创建），对程序员方便快速，但是自由度小；链表从堆中分配空间，自由度大但是申请管理比较麻烦。 从访问方式类看，数组在内存中是连续的存储，因此可以利用下标索引进行访问；链表是链式存储结构，在访问元素时候只能够通过线性方式由前到后顺序的访问，所以访问效率比数组要低。 2）输入一个整型数组，数组里有正数也有负数。数组中一个或连续的多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为O(n) 思路： Step1.从头到尾逐个累加数组中的每个数字，初始化和为0；（nCurrSum=0，nGreatestNum=int.MinValue） Step2.首先加上第一个数字，从第二个数字开始累加，依次将累加和保存到一个临时变量（nCurrSum）中； Step3.如果当前累加和（nCurrSum）小于0，那抛弃前面的子数组和，从下一个数字开始重新累加；相反，则将当前累加和（nCurrSum）与返回累加和（nGreatestNum）进行比较，如果nCurrSum>nGreatestNum，则更新nGreatestNum。