数据结构 题库答案汇总
D
研究数据结构就是研究数据的逻辑结构、存储结构及其基本操作。
数据的逻辑结构：主要分为线性结构和非线性结构。线性结构：数据结构的元素之间存在一对一线性关系，所有结点都最多只有一个直接前趋结点和一个直接后继结点。非线性结构：各个结点之间具有多个对应关系，一个结点可能有多个直接前趋结点和多个直接后继结点。
数据的存储结构：指的是逻辑结构在计算机存储空间中的存放形式（也称为物理结构）。
数据的基本操作：就是研究非数值计算的程序设计问题中，计算机操作对象以及他们之间的关系和操作。
A
算法分析的两个主要方面是时间复杂度和空间复杂度。
时间复杂度通常是衡量算法的优劣的，衡量算法的时间严格来讲是很难衡量的，由于不同的机器性能不用环境都会造成不同的执行时间空间复杂度是对一个算法在运行过程中临时占用存储空间大小的度量，也是使用大O表示法。
D
广义表是一种非线性表，每个节点元素可以是单个元素(原子)，也可以是广义表(子表)
B
算法的五个基本特性分别是：输入、输出、有穷性、确定性和可行性。
输入/输出：算法具有零个或多个输入，算法至少具有一个或多个输出。
有穷性：是指算法在执行有限的步骤后，自动结束而不会出现无限循环，并且每个步骤在可接受的时间内完成。
确定性：算法的每个步骤都有明确的含义，不会出现二义性。
可行性：算法的每一步都必须是可行的，也就是说，每一步都通过执行有限次数完成。
C
D
C
C
B
A
A
D
B
log2n
树形结构
答案： O(1) O(log2N) O(N) O(Nlog2N) O(N2) O(N3) O(2N)
数据结构被形式地定义为（D, R），其中D是数据元素的有限集合，R是D上的关系有限集合。
数据结构包括数据的逻辑结构、数据的存储结构和数据的运算这三个方面的内容。
数据结构按逻辑结构可分为两大类，它们分别是线性结构和非线性结构
线性结构中元素之间存在一对一关系，树形结构中元素之间存在一对多关系，图形结构中元素之间存在多对多关系。
在线性结构中，第一个结点没有前驱结点，其余每个结点有且只有 1个前驱结点；最后一个结点没有后续结点，其余每个结点有且只有1个后续结点。
在树形结构中，树根结点没有前驱结点，其余每个结点有且只有1个前驱结点；叶子结点没有后续结点，其余每个结点的后续结点数可以任意多个。
在图形结构中，每个结点的前驱结点数和后续结点数可以任意多个。
数据的存储结构可用四种基本的存储方法表示，它们分别是顺序、链式、索引、散列。
数据的运算最常用的有5种，它们分别是插入、删除、修改、查找、排序。
一个算法的效率可分为时间效率和空间效率。
任何一个C程序都由一个主函数和若干个被调用的其它函数组成。
【解答】B
非线性结构包括树结构和图结构,其中树结构是一对多,而图结构是多对多的.
C
C
A
C
B
答：简单地说，数据结构定义了一组按某些关系结合在一起的数据元素。数据类型不仅定义了一组带结构的数据元素，而且还在其上定义了一组操作。
答：线性结构反映结点间的逻辑关系是一对一的，非线性结构反映结点间的逻辑关系是多对多的。
O(m*n)；O(n2)；O(n2)；O(log3n)
C
A
D
B
A
A
C
C
A
C
C
A
D
B
D
A
C
A
D
这个题比较有迷惑性，很多同学觉得插入位置应该是n个
然后计算0+1+2+...+n-1的累加和除以次数n得到平均值(n-1)/2
乍一看，没问题，但实际上插入是有n+1个位置的，即包括表的两端
所以应该计算0+1+2+...+n的累加和除以次数n得到平均值n/2
D
[解析] 在不带头结点的单链表head中，head指向第一个元素结点，head=NULL表示该链表为空，所以答案为A。
A
A
C
A
C
B
D
答案：q->next=p->next p->next=q
答案：线性结构 长度
写出带头结点的双向循环链表L为空表的条件 L->prior=L->next=L 。
head->next==NULL
答案：q->next
答案：(1)p=p->next (2)p->data
答案：(1)s->next=p->next (2)p->next=s
答案：(1)p->next!=NULL (2)p->next=q->next
答案：求单链表head的长度
答案：void invent(Lnode *head)
{Lnode *p,*q;
if(!head->next) return ERROR;
p=head->next; q=p->next; p->next =NULL;
while(q)
{p=q; q=q->next; p->next=head->next; head->next=p;}
}
答案：void merge(Lnode *L1, Lnode *L2)
{Lnode *p = L1, *q = L2 ;
while(p->next!=L1)
p=p->next;
while(q->next!=L2)
q=q->next;
q->next=L1; p->next =L2;
}
答案：void assending(Lnode *head)
{Lnode *p,*q , *r, *s;
p=head->next; q=p->next; p->next=NULL;
while(q)
{r=q; q=q->next;
if(r->data<=p->data)
{r->next=p; head->next=r; p=r; }
else
{while(!p && r->data>p->data)
{s=p; p=p->next; }
r->next=p; s->next=r;}
p=head->next; }
}
答案：
void linklist_c(Lnode *head)
{Lnode *p; p=head;
if(!p) return ERROR;
while(p->next!=NULL)
p=p->next;
p->next=head;
}
设单链表的长度（数据结点数）为N，则该算法的时间主要花费在查找链表最后一个结点上（算法中的while循环），所以该算法的时间复杂度为O（N）。
答案：
(1) (a2, a4, …, ) (2)将循环单链表中偶数结点位置的元素值写入顺序表A
答案：
void Insert_sq(Sqlist va[], ElemType x)
{int i, j, n;
n=length(va[]);
if(x>=va[n-1])
va[n]=x;
else
{i=0;
while(x>va[i]) i++;
for(j=n-1;j>=I;j--)
va[j+1]=va[j];
va[i]=x; }
n++;
}
答案：
(3,7,2,1,8) 删除顺序表中重复的元素
void Delete_list(Lnode *head, ElemType x, ElemType y) {
Lnode *p, *q;
if (!head) return ERROR;
p = head; q = p;
while(!p) {
if ((p->data>x) && (p->data<y)) {
if(p==head) {
head=p->next;
free(p);
p=head;
q=p;
}
else {
q->next=p->next;
free(p);
p=q->next;
}
}
else {
q=p;
p=p->next;
}
}
}
void delete(List* head, int a, int b) {
List *p, *q;
q = head;
p = head->next;
while (p != head) {
if(p->data > a && p->data < b) {
q->next = p->next;
free(p);
p = q->next;
}
else {
p = p->next;
q = q->next;
}
}
}
C
C
D
B
D
B
A
A
A
B
B
B
C
A
C
A
C
D
A
C
C
A
C
A
这道题结合操作系统的知识点进行了考察，为解决计算机与打印机之间速度不匹配的问题，采用SPOOLING技术。
SPOOLING （即外部设备联机并行操作），即Simultaneous Peripheral Operations On-Line的缩写，它是关于慢速字符设备如何与计算机主机交换信息一种技术，通常称为“假脱机技术”。SPOOLING技术实际上是一种外围设备同时联机操作技术，称为排队转储技术。它在输入和输出之间增加了“输入井”和“输出井”的排队转储环节。
SPOOLING技术中用到的缓冲区就是缓冲队列，不会改变打印数据的输出顺序。
缓冲队列就是模拟现实生活中的排队，一般是先来后到，比如疫情期间我们去核酸采样点进行核酸检测就要排队，对应的数据结构就是队列，队列具有先进先出的性质。
本题选B。
C
A
D
答案：3
答案：(rear-front+M)%M
答案：n-1
答案：61
15
答案：（1）Push(S,N%8) （2）!StackEmpty(S)
答案：（1）6,4,2,5,3,1 （2）将队列倒置
答案：void EnQueue(Lnode *rear, ElemType e)
{ Lnode *new;
New=(Lnode *)malloc(sizeof(Lnode));
If(!new) return ERROR;
new->data=e; new->next=rear->next;
rear->next=new; rear =new;
}
void QueueInvent(Queue q)
{ ElemType x;
makeEmpty(SqStack s);
while(!isEmpty(Queue q))
{x=deQueue(Queue q);
push(SqStack s, ElemTypex);}
while(!isEmpty(SqStack s))
{x=pop(SqStack s);
enQueue(Queue q, ElemType x);}
}
答案：出栈的可能序列：
ABCD ABDC ACDB ACBD ADCB BACD BADC BCAD BCDA
CBDA CBAD CDBA DCBA
C
A
C
A
B
ëlog2nû+1
A
B
模式匹配
i-j+1
i-t->len+1
答案：.串比较算法
答案：串的模式匹配算法
C
B
C
D
A
A
B
B
C
D
B
B
B
C
B
A
Loc(A[0][0])+(i*N+j)*k
(x,y,z)
C
B
B
D
A
B
C
C
A
B
B
C
C
B
A
B
B
C
D
A
C
A
最小
最大值
bt!=NULL
InOrderTraverse(bt->rchild);
depth(t->rchild)
hl>hr
答案：交换二叉树结点左右子树的递归算法
答案：二叉树后序遍历递归算法
结点a 为根结点
结点b d f h i j k为叶子结点
结点 a c g为k得祖先
j得兄弟只有i
树得深度为4
答案：二叉树形态
WPL=12*1+(4+5+6)*3+(1+2)*4=12+45+12=69
答案：(1)树形态：
(2)带权路径长度：WPL=(6+7+9)*2+5*3+(2+3)*4=44+15+20=79
答案：
答案：(1)树形态：
(2)带权路径长度：WPL=30*1+16*2+9*3+5*4+(1+3)*5=30+32+27+20+20=129
28
/ \
11 16
/ \ / \
5 6 7 9
c / \ b e
2 4
d a
a:011
b:10
c:00
d:010
e:11
森林中的叶子结点在二叉树中依旧是叶子节点
答案：先序：FDBACEGIHJ
中序：ABCDEFGHIJ
后序：ACBEDHJIGF
答案： （以先序遍历的方法为例）
void count_preorder(Bitree *t, int *n)
{
if(t!=NULL)
{*n++;
count_preorder(t->lchild);
count_preorder(t->lchild); }
}
B
B
A
B
B
B
A
B
为了区分队列空间全占满还是为空, 循环队列规定最多只能有MaxSize-1个队列元素，当循环队列中只剩下一个空存储单元时，队列就已经满了
B
B
A
A
A
B
D
B
C
D
D
B
简单图是没有平行边且没有自环的图
平行边：对无向图，关联一对顶点的无向边如果多于1条，则称这些边为平行边；对有向图，关联一对顶点的有向边如果多于1条，并且这些边的始点与终点相同(也就是它们的的方向相同)，称这些边为平行边
自环（Loop）是一条顶点与自身连接的边。
没有平行边且没有自环，但是两个顶点可以你指向我，我指向你
所以最多的情况就是这个图中任意两个顶点两两相连，且都是互相指向
C
A
B
B
A
D
B
B
B
C
B
答案：n-1条
答案：极小连通子图
答案：邻接矩阵
答案：深度优先搜索
答案：1
答案：拓扑排序
第i列非零元素的个数
n*(n-1)/2
将第i行所有元素置为0
出度
答案：实现图的深度优先遍历算法
答案：(1)广度优先遍历序列：1; 2, 3, 4; 5; 6
(2)最小生成树（prim算法）
答案： (1)图形态 (2)深度优先搜索树
答案：1，5，2，3，6，4 1，5，6，2，3，4 5，1，2，3，6，4
5，1，6，2，3，4 5，6，1，2，3，4
答案：(1)最早发生时间和最迟发生时间： (2)关键路径：
答案：
|
终点 |
从v0到各终点的d值和最短路径的求解过程 |
|||
|
i=1 |
i=2 |
i=3 |
i=4 |
|
|
v1 |
12 (v0,v1) |
12 (v0,v1) |
7 (v0,v4,v1) |
|
|
v2 |
4 (v0,v2) |
|
|
|
|
v3 |
9 (v0,v3) |
8 (v0,v2,v3) |
7 (v0,v4,v3) |
7 (v0,v4,v3) |
|
v4 |
5 (v0,v4) |
5 (v0,v4) |
|
|
|
vj |
v2 |
v4 |
v1 |
v3 |
|
s |
{v0,v2} |
{v0,v4} |
{v0,v4,v1} |
{v0,v4,v3} |
答案：prim算法求最小生成树如下：
答案：拓扑排序如下：
v1, v2, v4, v6, v5, v3, v7, v8 v1, v2, v4, v6, v5, v7, v3, v8
v1, v2, v6, v4, v5, v3, v7, v8 v1, v2, v6, v4, v5, v7, v3, v8
v1, v6, v2, v4, v5, v3, v7, v8 v1, v6, v2, v4, v5, v7, v3, v8
答案：(1)求ve和vl (2)关键路径
答案：(1) 是强连通图 (2) 邻接矩阵和邻接表为：
答案：
(1)图形态：
(2)prim算法求最小生成树：
v0,v2,v5,v1,v3,v4,v6,v7;
v0,v1,v4,v2,v3,v5,v6,v7;
v0,v1,v2,v5,v3,v4,v6,v7;
答案：kruskal算法的最小生成树
答案：
|
终点 |
最短路径求解过程 |
||||
|
b |
6 (a,b) |
5 (a,c,b) |
|
|
|
|
c |
3 (a,c) |
|
|
|
|
|
d |
¥ |
6 (a,c,d) |
6 (a,c,d) |
|
|
|
e |
¥ |
7 (a,c,e) |
7 (a,c,e) |
7 (a,c,e) |
|
|
f |
¥ |
¥ |
¥ |
9 (a,c,d,f) |
9 (a,c,d,f) |
|
vj |
c |
b |
d |
e |
f |
|
S |
{a,c} |
{a,c,b} |
{a,c,d} |
{a,c,e} |
{a,c,d,f} |
B
A
A
C
D
A
C
B
A
A
B
B
C
A
B
D
D
C
D
C
C
A
C
A
A
C
B
C
D
A
D
B
D
C
B
A
D
C
D
C
D
C
B
A
C
C
D
B
A
A
A
链栈特点是动态申请内存空间，只要内存空闲空间够，就可以一直申请下去，所以出现上溢的情况很少，这是它的优点。
链栈是一种数据存储结构，可以通过单链表的方式来实现，使用链栈的优点在于它能够克服用数组实现的顺序栈空间利用率不高的特点，但是需要为每个栈元素分配额外的指针空间用来存放指针域。
D
C
C
C
A
B
B
D
A
B
C
C
A
B
D
C
B
C
C
B
C
C
C
B
C
A
B
C
C
A
B
D
C
B
C
B
C
B
由于下标从0开始，先计算偏移量，i*n+j，再乘以字节既是(i*n+j)*k,最后加上第一个数组元素的地址，所以是(i*n+j)*k+Loc(a[0][0])，选B。
这里要注意的是下标是从0开始的还是从1开始的，从1开始时，i,j都需要-1，从0开始时，不用减。
C
B
C
B
C
D
B
C
D
B
B
B
D
C
A
B
C
C
D
B
1.满二叉树情况下叶子结点最多了，h层高的满二叉树叶子结点公式为：2^(h-1)个
2.高度为8的完全二叉树至少有2的7次方个，即128
3.二叉树的度表示节点的子树或直接继承者的数目，二叉树的度是一个子树或单子树。2度是两个孩子，或者左和右子树有两个叉树，最大度数为2。
完全二叉树在满二叉树的基础之上/2,[127/2]=64
D
B
C
B
A
C
D
B
B
C
B
D
B
B
因为n个顶点构成的环共有n条边，去掉其中任意一条便是一棵生成树，所以共有n种情况。
C
B
C
C
C
C
C
C
B
D
D
A
C
B
B
A
D
D
A
B
C
A
B
B
n个顶点的无向图，每个顶点都相当于一个根节点，可以生产一棵树，故有n棵生成树
C
B
C
C
A
A
D
C
D
A
A
D
D
D
B
C
【解析】
这个题有一定的迷惑性，有的同学认为Dijkstra算法可以优化到O(nlogn)的复杂度，但是这个题已经声明存储方式是邻接矩阵而非邻接表，所以复杂度是O(n^2)
A
A
C
D
C
B
A
C
D
D
B
B
A
C
B
C
B
C
C
B
C
D
C
D
C
A
D
B
D
A
D
5趟排序之后不能确定序列一定有序，对冒泡排序来说，要么是完成n-1趟一定有序，要么中间某一趟不会进行交换操作从而确定提前排好序了，所以答案是6。
C
D
B
A
C
B
C
B
B
C
D
C
D
C
A
D
B
D
A
C
B
D
D
A
C
A
B
C
D
B
减小装填因子可以提高散列表的查找效率；处理冲突（碰撞）时可以减少，但不能“避免”产生聚集（堆积）现象，故选 B
III错在“避免”二字。
B
C
C
B
A
C
B
A
D
B
D
A
C
（画图举例子既可以出来了，比如1 2 3 4 5，查找3，mid为3，比较一次就找到，找到的最多元素个数为1，就是3，再比如查找4，mid一开始在3处，然后在4处，比较成功，比较两次就找到，找到的最多元素个数为2）
经过1次折半查找最多能找到1个元素
经过2次折半查找最多能找到2个元素
经过3次折半查找最多能找到4个元素
...
经过n次折半查找最多能找到2^(n-1)个元素
B
B
B
C
A
B
B
参考答案：C
答案解析：内层循环条件 j<=n 与外层循环的变量无关，每次循环 j 自增 1，每次内层循环都执行 n 次。外层循环条件为 k<=n，增量定义为 k*=2，可知循环次数为 2k <=n，即 k<=log2n。
所以内层循环的时间复杂度是 O(n)，外层循环的时间复杂度是 O(log2n)。对于嵌套循环，根
据乘法规则可知，该段程序的时间复杂度 T(n)=T1(n)*T2(n)=O(n)*O(log2n)=O(nlog2n)。
参考答案：D
答案解析：m、n 是两个升序链表，长度分别为 m 和 n。在合并过程中，最坏的情况是两个链表中的元素依次进行比较，比较的次数最少是 m 和 n 中的最小值。
参考答案：B
答案解析：考查时间复杂度的计算。
该程序中使用了递归运算。本题中递归的边界条件是 n<=1，每调用一次 fact()，传入该层 fact()的参 数值减 1（注意不是 n 减 1），因此执行频率最高的语句是 return n*fact(n-1)，一共执行了 n-1 次，而每一层 fact(i)运算只包含一次乘法。如果采用递归式来表示时间复杂度，则：
时间复杂度为 O(n)。
解答：A。程序中，执行频率最高的语句为“x=2*x”。设该语句执行了t次，则2 t+1=n/2，
故t=log2(n/2)-1=log2n-2= O(log2n)。
参考答案：
(1)算法的基本设计思想：
算法分3步完成。第1步，采用两个指针交替前行，找到单链表的中间结点；第2步，将单链表的后半段结点原地逆置；第3步，从单链表前后两段中依次各取一个结点，按要求重排。
(2)算法实现：
(3)算法的时间复杂度：
参考答案的时间复杂度为O(n)。
C语言下标为0，按行优先存储。
方法一：画图
本题选A。
方法二：计算
也可以直接计算：
第一步：计算 m1,1 到 m6,6 的元素个数。
12+11+10+9+8+1=51
第二步：修正下标从0开始，需要减一。
51−1=50
本题选A。
解答：
关于图的存储结构，我们学过邻接矩阵、邻接表、十字链表和邻接多重表。
这边要求压缩稀疏矩阵，所以建议使用 O(|V|+|E|) 的存储结构存储， O(|V|^2) 空间复杂度的邻接矩阵排除，剩选项A和C，十字链表空间复杂度为 O(|V|+|E|) ，正确。剩下的两个概念三元组表和二叉链表在图的存储结构中我们并没有接触过，但是我们可以排除二叉链表，二叉链表就是有两个指针的链表啊，不就是二叉树吗？树是图的一种特例，图的存储结构能存储树，但树的存储结构不能存储图，排除选项C，只剩选项A了。
三元组表的结点存储了行row、列col、值value三种信息，即两个顶点和边权，是主要用来存储稀疏矩阵的一种数据结构。也就是三元组表存储系数矩阵的空间复杂度为 O(|V|+|E|) ，正确。
二叉链表又名左孩子右兄弟表示法，可用于表示树或森林。
本题选A。
B
参考答案：B
答案解析：考查树结点数的特性。
设树中度为 i（i=0，1，2，3，4）的结点数分别为 Ni，树中结点总数为 N，则树中各结点的度之和等于 N-1，即 N = 1+N1+2N2+3N3+4N4 = N0+ N1+N2+N3+N4，根据题设中的数据，即可得到 N0 = 82，即树 T 的叶结点的个数是 82。
A
方法一：推理
因为每个非叶结点都有2个子结点，所以二叉树T只有度为0和度为2的结点，可得：
n0=k
n0=n2+1
n=n0+n2
解得 n=2k−1 。
本题选A。
方法二：画图举例
一棵非空完全二叉树T的所有叶结点均位于同一层，且每个非叶结点都有2个子结点。可得这棵二叉树为满二叉树。
直接画出一个高度为3的满二叉树。
k=4,n=7 可得 n=2k−1 。
本题选A。
解答：C。叶结点数为n，则度为2的结点数为n-1,度为1的结点数为0或1，本题中为1（总结点数为偶数），故而即2n=768。
参考答案：C
答案解析：考查完全二叉树的特点。
完全二叉树比起满二叉树只是在最下面一层的右边缺少了部分叶结点，而最后一层之上是个满二叉树，并且只有最后两层上有叶结点。第 6 层有叶结点则完全二叉树的高度可能为 6 或 7，显然树高为 7时结点更多。若第 6 层上有 8 个叶结点，则前六层为满二叉树，而第 7 层缺失了 8×2＝16 个叶结点，故完全二叉树的结点个数最多为 27-1-16=111 个结点。
解答：
将一棵树T转化为对应的二叉树BT，用的是“左孩子右兄弟”规则，即每个结点的左指针指向它的第一个孩子，右指针指向它在树中相邻的右兄弟。
方法一：推理
树T的后序遍历是先孩子后根，是一个自底向上的遍历顺序，对应二叉树BT中的一个从左到右的遍历顺序，即中序遍历。如果不能理解中序遍历是从左到右的，将二叉树中所有结点都向下进行投影，投影得到的序列就是中序遍历序列。
本题选B。
方法二：画图举例
当然方法一比较抽象，比较难想。我们可以直接画出一棵树，写出其后根遍历序列，将他转化为二叉树，观察这个后根遍历序列与二叉树的哪个遍历序列一致。
但是这个举例又非常有讲究，要具有区分度又不能太复杂，我们先尝试构造出一棵高度为2的满三叉树。
很明显，这里BT的中序遍历序列与T的后根遍历序列相同。
本题选B。
方法一：取交集
前序遍历为“根左右”，中序遍历为“左根右”，非空二叉树的先序序列与中序序列相同，取交集，都为“根右”，所以只有右子树。B正确。非叶结点只有右子树是一棵非空二叉树的先序序列与中序序列相同的充分必要条件。但非叶结点的度均为1是一棵非空二叉树的先序序列与中序序列相同的必要不充分条件。
本题选B。
方法二：构造二叉树
这里第一步先构造二叉树，本人拓展一下给出以下结论：
- 已知某二叉树的前序遍历序列和中序遍历序列，能确定唯一的二叉树。
- 已知某二叉树的后序遍历序列和中序遍历序列，能确定唯一的二叉树。
- 已知某二叉树的层序遍历序列和中序遍历序列，能确定唯一的二叉树。
已知二叉树的前序遍历序列与中序遍历序列相同。我们可以构造出二叉树。
前序遍历序列和中序遍历序列均为a, b, c。
所有非叶结点只有右子树。B正确。非叶结点只有右子树是一棵非空二叉树的先序序列与中序序列相同的充分必要条件。但非叶结点的度均为1是一棵非空二叉树的先序序列与中序序列相同的必要不充分条件。
本题选B。
B
方法一：模拟
后序序列是先左子树，接着右子树，最后父结点，递归进行。根结点左子树的叶结点首先被访问，它是e。接下来是它的父结点a，然后是a的父结点c。接着访问根结点的右子树。它的叶结点b首先被访问，然后是b的父结点d，再者是d的父结点g。最后是根结点f。因此d与a同层，B正确。
本题选B。
方法二：环线法
按照箭头标记填入序列。
本题选B。
方法一：枚举
先序序列为满足二叉树递归遍历顺序为“根左右”的输出序列。
其实只要枚举一半就行，本人枚举了左子树结点数大于右子树结点数的所有情况，另一半对称，总计 7×2=14 。
但注意，如果结点个数为奇数个，需要考虑左子树结点数等于右子树结点数的情况。
本题选B。
方法二：计算
可以发现，暴力枚举需要非常小心，稍有不慎就会遗漏。如果先序序列为入栈顺序，中序序列为出栈顺序，由先序序列和中序序列可以唯一的确定一棵二叉树，出栈序列为 �=4 的卡特兰数： 
。
本题选B。
参考答案：B
答案解析：利用三叉树的 6 个叶子结点的权构建最小带权生成树，最小的带权路径长度为(2 + 3) * 3 + (4 + 5) * 2 + (6 + 7) * 1 = 46。
方法一：模拟
T 的带权（外部）路径长度最小是 (2+3)×3+(4+5)×2+(6+7)×1=46 。
本题选B。
方法二：贪心
下面提供秒题解法。
题目要求“最小”，四个选项中A选项最小，直接选A？
如果是这样你就错了， (2+3+4+5+6+7)×1=27 ，A选项表示一棵六叉树。
与 T 为三叉树矛盾，所以我们只能在剩余三个选项中选最小值。
本题选B。
参考答案：A
答案解析：考查树的遍历、及由遍历序列确定二叉树的树形。
前序序列和后序序列不能唯一确定一棵二叉树，但可以确定二叉树中结点的祖先关系：当两个结点 的前序序列为 XY 与后序序列为 YX 时，则 X 为 Y 的祖先。考虑前序序列 a,e,b,d,c、后序序列 b,c,d,e,a， 可知 a 为根结点，e 为 a 的孩子结点；此外，a 的孩子结点的前序序列 e,b,d,c、后序序列 b,c,d,e，可知 e 是 bcd 的祖先，故根结点的孩子结点只有 e。本题答案为 A。
B
解析
1：简单选择 最好时间 O(n^2) 平均时间O(n^2) 最坏时间 O(n^2)
2：直接插入 最好时间 O(n) 平均时间O(n^2) 最坏时间 O(n^2)
3：冒泡排序 最好时间 O(n) 平均时间O(n^2) 最坏时间 O(n^2)
4：希尔排序 最好时间 O(n) 平均时间O(logn) 最坏时间 O(n^s) 1<s<2
5：快速排序 最好时间 O(nlogn) 平均时间O(nlogn) 最坏时间O(n^2)
6：堆排序 最好时间 O(nlogn) 平均时间O(nlogn) 最坏时间O(nlogn)
7：归并排序 最好时间 O(nlogn) 平均时间O(nlogn) 最坏时间O(nlogn)
解答：C。由前序和后序遍历序列可知3为根结点，故（1,2）为左子树，（4）为右子树，
C不可能。或画图即可得出结果。
解答：
这道题就是考察知识点的联想与转化，想到了就很好做。
方法一：推理
第一步：将表达式转化为二叉树。
第二步：合并二叉树中的重复结点转化为图。
本题选A。
方法二：贪心
假设所有元素都可以复用，只需要统计表达式中有几种不同的元素和操作， �,�,+,×,÷ 总共5种。
本题选A。
方法三：选项排序 + 贪心
下面提供秒题解法：
题目要求“至少”，四个选项中A最小。
本题选A。
无向图边数的两倍等于各顶点度数的总和。由于其他顶点的度均小于3，所以它们的度至多为2，可列出方程：
解得：
本题选B。
参考答案：C
答案解析：考查图的连通性。
要保证无向图 G 在任何情况下都是连通的，即任意变动图 G 中的边，G 始终保持连通，首先需要 G的任意六个结点构成完全连通子图 G1，需 15 条边，然后再添一条边将第 7 个结点与 G1 连接起来，共需 16 条边。
B
参考答案：C
答案解析：各顶点的度是矩阵中此结点对应的横行和纵列非零元素之和。
本题考察度的定义：某顶点的度为以该顶点为端点的边的数目。
我们将顶点依次编号为 1,2,3,4 。
方法一：观察邻接矩阵
顶点 1 的度为包含 1 为端点的边数，即第一行和第一列非零元素的个数。
顶点 2 的度为包含 2 为端点的边数，即第二行和第二列非零元素的个数。
顶点 3 的度为包含 3 为端点的边数，即第三行和第三列非零元素的个数。
顶点 4 的度为包含 4 为端点的边数，即第四行和第四列非零元素的个数。
本题选C。
方法二：画出有向图
本题选C。
方法一：代入选项
深度优先搜索就是一个“一条路走到黑”的搜索策略，直到无路可走才开始回溯，找到前一个能够继续搜索的结点重复上述步骤。
注意本图为有向图，只能按照箭头的方向走。
由于本题图中分支很多，如果正向枚举所有深度优先搜索序列会非常复杂，所以这里采用带入选项检查策略。
很明显，D选项走到 V2 后无法走到 V3 ，错误。
本题选D。
方法二：观察选项
如果你连深度优先搜索是什么都不知道，那只能猜了，观察选项，只有D选项序列有序，其它为乱序。
这种猜法就是赌命题组设置错误选项很无脑，就和很多人喜欢用123456作为密码一样。别笑，我还真用123456当密码过，而且不止一次。
本题选D。
D
方法：枚举
根据顶点集和边集画出有向图：
由于图比较简单，很容易枚举出所有深度优先遍历序列，为了不要混乱，按照顶点下标从小到大的顺序枚举：
本题选D。
参考答案：D
答案解析：D 选项是深度优先遍历不是广度优先遍历的顺序。
方法一：模拟
广度优先搜索就是用一圈一圈扩散的方式进行搜索。
我们依次以A、B、C、D四个选项中序列的第一个元素为起点画出下面这个广度优先搜索过程，用颜色由深入浅标记这个扩散过程，颜色相同的结点在同一层，输出序列中，颜色相同的结点的关键字即同一层结点的关键字一定相邻。
本题选D。
方法二：找错误选项
我发现命题组设置错误选项一般比较无脑，D选项出现了无脑的a, b, c, d这种顺序，明显就是一个深度优先搜索顺序，直接排除。
本题选D。
参考答案：C
答案解析：考查不同存储结构的图遍历算法的时间复杂度。
广度优先遍历需要借助队列实现。邻接表的结构包括：顶点表；边表（有向图为出边表）。当采用邻接表存储方式时，在对图进行广度优先遍历时每个顶点均需入队一次（顶点表遍历），故时间复杂度为O(n)，在搜索所有顶点的邻接点的过程中，每条边至少访问一次（出边表遍历），故时间复杂度为 O(e)，算法总的时间复杂度为 O(n+e)。
参考答案：A
答案解析：考查最小生成树、及最小生成树算法的性质。
对于 I，最小生成树的树形可能不唯一（这是因为可能存在权值相同的边），但是代价一定是唯一的，I 正确。对于 II，如果权值最小的边有多条并且构成环状，则总有权值最小的边将不出现在某棵最小生成树中，II 错误。对于 III，设 N 个结点构成环，N-1 条边权值相等，则从不同的顶点开始普里姆算法会得到 N-1 中不同的最小生成树，III 错误。对于 IV，当最小生成树唯一时（各边的权值不同），普里姆算法和克鲁斯卡尔算法得到的最小生成树相同，IV 错误。
方法一：模拟 + 枚举 + 取差集
Kruskal算法：首先将边从图中剥离然后按照边权值从小到大排序。然后从小到大依次将边复原到图中，插入后检查是否成环，如果成环，丢弃插入的边，重复上述过程直到有顶点都连通。
Kruskal过程模拟如下图所示：
D
方法一：枚举
枚举所可能的拓扑序列。
每次找入度为0的点依次剥离，如下图所示：
总共有4种可能的输出序列。
A、B、C均能够找到对应的输出序列。
本题选D。
方法二：代入选项
带入选项中的拓扑序列检查是否符合题目中的有向图。
A、B、C均符合。
本题选D。
方法一：深度优先搜索
如果在拓扑序列中顶点u在顶点v前面，则在深度优先搜索中顶点v先访问完成。按照访问顶点的结束时间从大到小输出即为拓扑序列。
所以每个顶点在搜索过程中需要记录一个状态，用color表示，该状态有3种情况：
- 未访问：还没有搜索到这个顶点，记为WHITE；
- 访问中：搜索过这个顶点，但还没有回溯到该顶点，该顶点还有相邻顶点没有访问完成，记为GRAY；
- 访问完成：搜索过并且回溯到这个顶点，且该顶点的所有相邻顶点均已访问完成，记为BLACK。
拓扑排序过程 TOPOLOGICAL-SORT 的伪代码如下：
DFS(u, L)
u.color = GRAY
for each vertex v ∈ G.Adj[u]
if v.color == WHITE
DFS(v, L)
if valid == FALSE
return
else if v.color == GRAY
valid = FALSE
return
u.color = BLACK
insert u onto the front of L
TOPOLOGICAL-SORT(G)
let L be a new linked-list
valid = TRUE
for each vertex u ∈ G.V
u.color = WHITE
for each vertex u ∈ G.V
if valid == TRUE
if u.color == WHITE
DFS(u, L)
else break
if valid == FALSE
error "G has cycles"
return
else return L
由于深度优先搜索运行时间为O(n+e)，其它开销为常数，因此过程 TOPOLOGICAL-SORT 的运行时间为 O(n+e) 。
本题选B。
方法二：广度优先搜索
若一个顶点的所有前驱顶点均已输出到拓扑序列中，则该顶点的入度为0。重复寻找入度为0的顶点，输出该顶点并将该顶点及从该顶点发出的边从图中删除。
拓扑排序过程 TOPOLOGICAL-SORT 的伪代码如下：
TOPOLOGICAL-SORT(G)
let L be a new linked-list
for each vertex u ∈ G.V
u.in-degree = 0
for each vertex u ∈ G.V
for each v ∈ G.Adj[u]
v.in-degree = v.in-degree + 1
Q = ∅
for each vertex u ∈ G.V
if u.in-degree == 0
ENQUEUE(Q, u)
insert u onto the rear of L
while Q ≠ ∅
u = DEQUEUE(Q)
for each vertex v ∈ G.Adj[u]
v.in-degree = v.in-degree - 1
if v.in-degree == 0
ENQUEUE(Q, v)
insert v onto the rear of L
for each vertex u ∈ G.V
if u.in-degree ≠ 0
error "G has cycles"
return
return L
由于广度优先搜索运行时间为O(n+e)，其它开销为常数，因此过程 TOPOLOGICAL-SORT 的运行时间为 O(n+e) 。
本题选B。
参考答案：D
答案解析：按照拓扑排序的算法，每次都选择入度为 0 的结点从图中删去，此图中一开始只有 结点 3 的入度为 0；删掉 3 结点后，只有结点 1 的入度为 0；删掉结点 1 后，只有结点 4 的 入度为 0；删掉 4 结点后，结点 2 和结点 6 的入度都为 0，此时选择删去不同的结点，会得出不同的拓扑序列，分别处理完毕后可知可能的拓扑序列为 314265 和 314625，选 D。
每次找入度为0的点依次剥离，如下图所示：
解答：C。Ⅰ.回路对应于路径，简单回路对应于简单路径；Ⅱ．刚好相反；Ⅲ．拓扑有序的必要条件。故选C。
参考答案：B
答案解析：考查拓扑排序序列。
题中图有三个不同的拓扑排序序列，分别为 abced，abecd，aebcd。
本题选C。
方法二：贪心
下面提供秒题解法：
观察选项，B和C中都有12，二选一。
B和C的区别在哪里呢，B选项最早开始时间和最晚开始时间相等，C选项最早开始时间和最晚开始时间不相等。意味着什么？B选项表示的边在关键路径上，C选项表示的边在不关键路径上。
这里图中关键路径很容易找出来。即
和 
，很明显，活动 d 不在关键路径上。
本题选C。
参考答案：C
答案解析：根据 AOE 网的定义可知，关键路径上的活动时间同时减少，可以缩短工期。
方法一：完整推理
折半查找判定树实际上是一棵二叉搜索树，它的中序遍历序列是一个单调序列。
折半查找即二分查找，假设搜索的有序数组为 A[1:n] ，目标元素为 target，二分查找伪代码如下：
向下取整：
BINARY-SERACH(A, n, target){
left = 1
right = n;
while(left <= right) {
mid = ⌊(left + right) / 2⌋
if (A[mid] == target) {
return mid;
} else if(nums[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
error "not found"
}
向上取整：
BINARY-SERACH(A, n, target){
left = 1
right = n;
while(left <= right) {
mid = ⌈(left + right) / 2⌉
if (A[mid] == target) {
return mid;
} else if(nums[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
error "not found"
}
方法一：构造
A选项二叉树10个结点。
B选项二叉树11个结点。
C选项二叉树9个结点。
D选项二叉树10个结点。
我们尝试构造一棵含10个元素的折半查找判定树，每个结点存储数组元素下标。
设有长度为10的升序序列 A[1:10] ，即满足 a1<a2<a3<a4<a5<a6<a7<a8<a9<a10 。为了方便讨论，考虑下标序列 {1,2,3,4,5,6,7,8,9,10} 。
折半查找规则要统一，要不全部折半向下取整，要不全部折半向上取整。下面分情况讨论。
折半向下取整：
根结点元素下标为⌊(1 + 10) / 2⌋ = 5，下标序列 {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}分为{1, 2, 3, 4}, {5}, {6, 7, 8, 9, 10}。对于左子树，根结点元素下标为⌊(1 + 4) / 2⌋ = 2。{1, 2, 3, 4}可以分为{1}, {2}, {3, 4}。对于右子树，根结点元素下标为⌊(6 + 10) / 2⌋ = 8。{6, 7, 8, 9, 10}可以分为{6, 7}, {8}, {9, 10}。递归执行上述过程直到折半查找判定树构造完成。
折半向上取整：
根结点元素下标为⌈(1 + 10) / 2⌉ = 6，下标序列{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}分为{1, 2, 3, 4, 5}, {6}, {7, 8, 9, 10}。对于左子树，根结点元素下标为⌈(1 + 5) / 2⌉ = 3。{1, 2, 3, 4, 5}可以分为{1, 2}, {3}, {4, 5}。对于右子树，根结点元素下标为⌈(7 + 10) / 2⌉ = 9。{7, 8, 9, 10}可以分为{7, 8}, {9}, {10}。递归执行上述过程直到折半查找判定树构造完成。
此折半查找判定树与选项A中的二叉树一致。
本题选A。
方法二：代入选项
考虑升序序列 A[1:n] ，其中 n 为对应二叉搜索树的结点个数，可以在树结点上依次填上相应的元素下标，符合折半查找规则的二叉树树即为所求。
折半查找规则要统一，要不全部折半向下取整，要不全部折半向上取整。
B选项中，观察以元素下标 2 为根结点的子树，二分查找区间为 [1, 2]，⌈(1 + 2) / 2⌉ = 2；观察以元素下标 7 为根结点的子树，二分查找区间为 [7, 8]，⌊(7 + 8) / 2⌋ = 7，错误。
C选项，观察以元素下标 2 为根结点的子树，二分查找区间为 [1, 4]，⌊(1 + 4) / 2⌋ = 2；观察以元素下标 8 为根结点的子树，二分查找区间为 [6, 9]，⌈(6 + 9) / 2⌉ = 8，错误。
D选项，观察以元素下标 7 为根结点的子树，二分查找区间为 [6, 7]，⌈(6 + 7) / 2⌉ = 7；观察以元素下标 5 为根结点的子树，二分查找区间为 [1, 10]，⌊(1 + 10) / 2⌋ = 5，错误。
只有A选项符合折半查找规则，正确。
本题选A。
方法三：确定性
本题考察算法的确定性。
折半查找规则要统一，要不全部折半向下取整，要不全部折半向上取整。也就是只有一个孩子结点的子树孩子结点固定在一侧，可以断言：下面两个命题必然有一个为真。
- 对于任意一个结点，其左子树结点个数大于或等于其右子树结点个数。
- 对于任意一个结点，其左子树结点个数小于或等于其右子树结点个数。
命题1对应折半向上取整的情况，命题2对应折半向下取整的情况。
观察最下面一层子树，只有选项A和D符合要求，均满足命题1，继续扩大范围观察，观察根结点所在子树，即整棵树，发现D中出现了右子树结点比左子树结点多的情况，违反命题1，排除。只有A符合要求。
本题选A。
参考答案：B
答案解析：考查折半查找的过程。
具有 n 个结点的判定树的高度为ëlog2nû + 1，长度为 16，高度为 5，所以最多比较 5 次。
B
本题考察B树的基本性质。
方法一：公式法
方法二：构造法
方法一：性质 + 贪心
本题选D。
方法二：公式法
本题选D。
方法三：选项排序 + 贪心
本题选D。
参考答案：A
答案解析：一棵高度为 2 的 5 阶 B 树，根结点只有到达 5 个关键字的时候才能产生分裂，成为高度为 2 的 B 树。
方法一：公式法
本题选A。
方法二：构造法
m 阶B树每个结点（除根结点）关键字数量 n 为 ⌈m/2⌉−1≤n≤m−1 。本题要求为5阶B树， 2≤n≤4 。
又该B树的高度为2，根结点至少有两棵子树，很容易构造出题目要求的B树。
该B树总共5个关键字。
本题选A。
方法三：选项排序 + 贪心
下面提供秒题解法。
题目要求“最少”，四个选项中A选项最少。
本题选A。
参考答案：D
答案解析：考查 B-树的删除操作。
对于上图所示的 3 阶 B-树，被删关键字 78 所在结点在删除前的关键字个数=1=é3/2ù-1，且其左兄弟结点的关键字个数=2≥é3/2ù，属于“兄弟够借”的情况，则需把该结点的左兄弟结点中最大的关键字上移到双亲结点中，同时把双亲结点中大于上移关键字的关键字下移到要删除关键字的结点中，这样就达到了新的平衡，如下图所示。
参考答案：D
答案解析：考查 m 阶 B-树的定义。
A、B 和 C 都是 B-树的特点，而选项 D 则是 B+树的特点。注意区别 B-树和 B+树各自的特点。
B
树是B树的一种变形形式。 B+ 树上的叶结点存储关键字以及相应记录的指针，叶结点中将关键字按大小顺序排列，并且相邻叶结点按大小顺序相互链接起来。所有分支结点（可视为索引的索引）中仅包含它的各个子结点（即下一级索引块）中关键字的最大值及指向其子结点的指针。
B+ 树支持两种查找运算：一种是从最小关键字开始的顺序查找，另一种是从根结点开始的多路查找。
在搜索树中查找关键字的时间复杂度与树高 ℎ 有关为 O(ℎ)=O(logn) ，结点越茂盛，树高越低，搜索越快。所以 B+ 树和B树比二叉搜索树更适合运用于数据量很大的系统。对于文件系统， B+ 树相比B树结构更加合理，功能更加强大，适合用于数据库系统。
本题选B。
B+树和B树的区别主要有两点：
- B+树的非叶结点不存储关键字，只作索引使用，而B树的非叶结点存储关键字。所以B+树的所有叶结点中包含了全部的关键字信息，但B树不一定。
- B+树上的叶结点存储关键字以及相应记录的指针，叶结点中将关键字按大小顺序排列，并且相邻叶结点按大小顺序相互链接起来。所以B+树支持两种查找运算：一种是从最小关键字开始的顺序查找，另一种是从根结点开始的多路查找。但B树只支持从根结点开始的多路查找。
本题选A。
方法一：推理
我们先构造出插入所有元素后的散列表。
一般我们说计算成功查找长度需要统计的情况数量为散列表中元素数量。计算失败查找长度需要统计的情况数量为散列表中槽位数量。
但是这里命题组挖坑了，散列函数式模7的，但是散列表的长度为11，实际上剩下的4个槽位是永远不可能散列到的。也就是这里计算失败查找长度需要统计的情况数量为散列函数中是模数。
可以计算出0-6号槽位的失败需要探测的次数，如下图所示。
本题选C。
方法二：观察选项
下面提供秒题解法：
观察选项，C和D中整数部分均为6，二选一，正确概率50%。
个人偏向凑整，因为命题组编写题目的时候数字都是凑好的，算出小数点你不慌吗？
本题选C。
C
我们先构造出插入所有元素后的散列表。
可以计算出查找关键字22, 43, 15成功需要探测的次数，如下图所示。
查找22的探测次数为1：
查找43的探测次数为2：
查找15的探测次数为3：
平均查找长度为求查找长度的数学期望：
ASL成功=(3+2+1)/3=2
参考答案：D
答案解析：产生堆积现象，即产生了冲突，它对存储效率、散列函数和装填因子均不会有影响，而平均查找长度会因为堆积现象而增大，选 D。
用线性探测法为例，处理冲突（碰撞）时可能出现堆积（聚焦）现象，平均查找长度会变长。
A、B和C选项均与处理冲突无关。
本题选D。
解答：B。
减小装填因子可以提高散列表的查找效率；处理冲突（碰撞）时可以减少，但不能“避免”产生聚集（堆积）现象，故选 B
III错在“避免”二字。
本题选B。
解答：
方法一：计算 next 数组
第一步：计算出模式串的next数组。默认next数组是优化后的next数组。
本人自编口诀优化前的next数组：第一格负一，第二格零，前缀等于后缀取最长。
当然实际代码中很多人习惯用优化前的next数组求解，优化后的next数组中每个值为优化前的next数组中每个值加一。
本人自编口诀优化后的next数组：第一格零，第二格一，前缀等于后缀取最长再加一。
移动位数 = 已匹配字符数 - 失配位置对应的匹配值（优化前next数组） = 5 - 2 = 3。模式串向后移动3格，重新进行匹配，这次匹配成功。
移动位数 = 失配位置 - 失配位置对应的匹配值（优化后next数组） = 6 - 3 = 3。模式串向后移动3格，重新进行匹配，这次匹配成功。
或 j 指针跳转指向模式串第 next[j] 个字符重新与主串第 i 个字符进行比较，next[6] = 3 ， j 指针跳转到模式串第3个字符的位置。
第二步：遍历主串对模式串进行匹配。
第一次匹配在主串第六个位置出现失配，找到之前匹配的子串为abaab，最长相同前缀与后缀为ab，将前缀的ab移动到后缀ab的位置。
或者查表next数组失配字符c，其next值为3，c位于模式串中第6位，移动位数 = 失配位置 - 失配位置对应的匹配值 （优化后next数组）= 6 - 3 = 3。模式串向后移动3格，重新进行匹配，这次匹配成功。
匹配9次，失配1次，总比较次数：9+1=10。
本题选B。
方法二：模拟
以下以 T = bacbababaabcbab 和 P = ababaca 为例。P 中绿色（含浅绿色和深绿色）表示对应字符匹配，红色表示对应字符失配，灰色表示未比较，浅绿色表示已匹配部分的最长的相等的前缀，深绿色表示已匹配部分的最长的相等的后缀。T 中黄色表示对应字符已经比较过，灰色表示未比较。
若已匹配部分为空，则 P 继续偏移一个位置，即偏移 s 增加 1。如图中第 1 趟、第 3 趟和第 4 趟匹配。
若已匹配部分不为空，已匹配长度为 x = i - 1，找出已匹配部分的最长的相等的前缀和后缀，（寻找已匹配部分的最长的相等的前缀和后缀时，从长度为 x - 1 的前缀和后缀开始判断更好。）该长度为 y，则下一次匹配从后缀开始位置开始，即偏移 s 增加 x - y。如图中第 2 趟和第 5 趟匹配。这步跳转用到了等式的传递性，因为 
且 
，所以 
。KMP 算法强大的地方就在这里，相比朴素字符串匹配算法，偏移 s 不仅实现了跳跃式增长，而且下一趟匹配中当前这趟的前缀部分的无需重新比较。
接下来进入下一轮匹配，从 P 中未比较的灰色部分开始继续比较，重复上述过程直到找到一个匹配或者比较超出 T 的范围为止。
该模拟方法无需计算 next 数组，next 数组本质就是基于这个原理进行计算的。此外，由于 next 数组有多种计算方式，不同计算方式结果不同，并不方便真题进行考察。
假设已经比较了 k 趟。
这里有个注意点，第 i 趟比较后匹配次数不是第 i 趟所有匹配的字符数，例如第 2 趟匹配中，前缀 ab 是无需重新比较的，所以第 2 趟比较后匹配次数 = 4，而不是 6，这一点一定要细心。
还有一种更快捷的计算方法：
后一种计算方式更为简便。
本题选B。
方法三：贪心
贪心找到最多匹配的情况，同样画出上图。虽然这个方法不严谨，好在本题足够简单，只有开始头指针对齐的一次和完全匹配的一次，总共出现一次失配。
匹配9次，失配1次，总比较次数：9+1=10。
本题选B。
C
本题代码为一步一跳的线性查找代码的优化，三步一跳找到目标元素或者目标元素附近再进行进一步检查。
但本质上仍然是从前往后的线性遍历，时间复杂度仍为 O(n) 。
既然是从前往后的线性遍历，当然是当 x 接近数组开头处时，比较次数更少。
本题选B。
参考答案：D
答案解析：考查折半插入和直接插入的区别。
折半插入排序与直接插入排序都是将待插入元素插入前面的有序子表，区别是：确定当前记录在前面有序子表中的位置时，直接插入排序是采用顺序查找法，而折半插入排序是采用折半查找法。排序的总趟数取决于元素个数 n，两者都是 n-1 趟。元素的移动次数都取决于初试序列，两者相同。使用辅助空间的数量也都是 O(1)。折半插入排序的比较次数与序列初态无关，为 O(nlog2n)；而直接插入排序的比较次数与序列初态有关，为 O(n)~O(n2)。
D
先看第一趟，1从最开始的5号位移动到0号位，说明第一趟步长是5，直接排除A,B；再看第二趟，2从第一趟排序结果的第4位移动到1号位，说明第二趟步长是3
void shellsort(int[] arr, int length) {
int index = 0;
int value = 0;
for(int flag = length/2; flag>0; flag /= 2;) {
for(int i=flag; i<length; i++) {
index = i;
value = arr[index];
if(value < arr[index-flag]) {
while((index-flag > 0 ||index-flag == 0) && value < arr[index-flag]) {
arr[index] = arr[index-flag];
index = index - flag;
}
arr[index] = value;
}
}
}
}
这道题考察希尔排序的特征，希尔排序中间过程是间隔有序的。
需要考察的间隔很多，我们可以直接参考选项，第一趟排序的间隔只有3和5，我们先考察3，从数组第一个元素开始为1, 5, 4, ...到这里就没必要查下去了，数组已经不单调了。直接排除A和B。
下面考察C和D，只需要观察第二题排序的间隔。我们先考察2，从数组第一个元素开始为1, 6, 3, ...到这里就没必要查下去了，数组已经不单调了。直接排除C。
现在A、B和C都被排除，只能选D，当然不放心的话你也可以验证一下D，完全符合希尔排序的特征。
A
希尔排序是插入排序的一种，又称“缩小增量排序”，是直接插入排序算法的一种更高效的改进版本。
参考答案：B
答案解析：首先，第二个元素为1，是整个序列中的最小元素，所以可知该希尔排序为从小到大排序。然后考虑增量问题，若增量为2，第 1+2 个元素4明显比第1个元素9要大，A 排除；若增量为3，第 i、i+3、i+6 个元素都为有序序列(i=1,2,3)，符合希尔排序的定义；若增量为4，第1个元素9比第1+4个元素7要大，C排除；若增量为5，第1个元素9比第1+5个元素8要大，D排除，选B。
我们依次检查每个增量，每个增量序列必须单调递增。
A错误。间隔2的序列为：9, 4, ... ，非单调递增，错误。
B正确。间隔3的序列为：9, 13, 20、 1, 7, 23、4, 8, 15，全部单调递增。
C错误。间隔4的序列为：9, 7, ...，非单调递增。
D错误。间隔5的序列为：9, 8, ...，非单调递增。
本题选B。
解答：
这道题关键的难点在于理解一“趟”，就是递归的一轮，画出递归树，就是递归树中的一层。
第一步：
检查快速排序，首先利用快速排序的性质，快速排序每一趟至少能够保证一个元素落在最终位置，即枢轴一定落在最终位置。这里进行了两趟快速排序，至少两个元素落在最终位置。
我们求出排好序后的序列为：2, 5, 12, 16, 28, 32, 60, 72，然后依次和四个选项进行比对，看有没有不符合要求的。
A中有两个落位。
B中有两个落位。
C中有三个落位。
D中有两个落位。
均符合。
第二步：
检查枢轴左边的元素是否都小于枢轴，右边元素是否都大于枢轴。
均符合。
到这里一般人就卡住了，找不到正确答案吗？
第三步：
画出递归树，明显选项D无法构造。
如果第一趟枢轴为12，第二趟左右两段分别递归产生新的枢轴，明显左边段枢轴缺失。
如果第一趟枢轴为32，第二趟左右两段分别递归产生新的枢轴，明显右边段枢轴缺失。
无法构造出递归树。
本题选D。
参考答案：C
答案解析：快排的阶段性排序结果的特点是，第 i 趟完成时，会有 i 个以上的数出现在它最终将要出现的位置，即它左边的数都比它小，它右边的数都比它大。题目问第二趟排序的结果，即要找不存在 2 个这样的数的选项。A 选项中 2、3、6、7、9 均符合，所以 A 排除；B选项中，2、9 均符合，所以 B 排除；D 选项中 5、9 均符合，所以D选项排除；最后看C选项，只有9一个数符合，所以C不可能是快速排序第二趟的结果。
其它方法
第一步：
检查快速排序，首先利用快速排序的性质，快速排序每一趟至少能够保证一个元素落在最终位置，即枢轴一定落在最终位置。这里进行了两趟快速排序，至少两个元素落在最终位置。
我们求出排好序后的序列为：2, 3, 4, 5, 6, 7, 9，然后依次和四个选项进行比对，看有没有不符合要求的。
A中有5个落位，待定。
B中有2个落位，待定。
C中有1个落位，错误。
D中有2个落位，待定。
由于这里C选项已经确定错误，无需进行第二步。
第二步是判断枢轴左边元素是否都小于枢轴，右边元素是否都大于枢轴。
第三步是画出序列对应的递归树，判断是否为快速排序的递归树。
本题过于简单，到第一步就结束了。
本题选C。
解答：A。内部排序采用顺序存储结构。
参考答案：D
答案解析：考查快速排序。
递归次数与各元素的初始排列有关。如果每一次划分后分区比较平衡，则递归次数少，如果划分后分区不平衡，则递归次数多。递归次数与处理顺序无关。
A
画出建堆过程：
对应Python测试代码：
array = [-6,-1,-5,-9,-8,-4,-7]
heapq.heapify(array)
print(array)
建堆的时间复杂度 O(n) 。
解答：
删除8后，用小根堆最后一个元素占位，然后需要维护堆的性质，设根结点下标为1，调用MIN-HEAPIFY(A, 1)，MIN-HEAPIFY伪代码如下：
MIN-HEAPIFY(A, i)
l = LEFT(i)
r = RIGHT(i)
if l ≤ A.heap-size and A[l] < A[i]
smallest = l
else smallest = i
if r ≤ A.heap-size and A[r] < A[smallest]
smallest = r
if smallest ≠ i
exchange A[i] with A[smallest]
MIN-HEAPIFY(A, smallest)
总共发生3次比较。
本题选C。
解答：B。首先与10比较，交换位置，再与25比较，不交换位置。比较了二次。
参考答案：A
答案解析：考查小根堆的调整操作。
小顶堆在逻辑上可以用完全二叉树来表示，根据关键序列得到的小顶堆的二叉树形式为下图左图：
插入关键字 3 时，先将其放在小顶堆的末端，再将该关键字向上进行调整，得到的结果上图右边所示。所以，调整后的小顶堆序列为：3，5，12，8，28，20，15，22，19。
参考答案：C
答案解析：基数排序的第 1 趟排序是按照个位数字来排序的，第 2 趟排序是按然十位数字的大小进行排序的，答案是 C 选项。
本题考察基数排序，直接进行模拟即可，按照从低位到高位的顺序进行。
本题选C。
tips：本题中 007 没有简单写作 7 ，如果遇到高位缺失的情况，要记得自己补 0 。
本题将归并排序和插入排序进行了对比。
归并排序的程序代码比插入排序的程序代码更长。1错误。
归并排序的平均时间复杂度为 O(nlogn) ，插入排序的平均时间复杂度为 O(n^2) 。3正确。
归并排序的空间复杂度为 O(n) ，插入排序的空间复杂度为 O(1) 。2错误。
本题选B。
能够将顺序存储的顺序表修改为链式存储的顺序表进行同样排序的算法有插入排序、选择排序、冒泡排序、归并排序，时间复杂度没有变化。所以1、2、3正确。
希尔排序和堆排序都利用了顺序存储的随机访问特性，而链式存储不支持这种性质，所以时间复杂度会增加，4、5错误。
本题选D。
C
除了基数排序外，其它三种排序都是基于比较的排序算法，元素的移动次数与关键字的初始排列次序有关。
参考答案：A
答案解析：考查各种内部排序算法的性质。
对于Ⅰ，简单选择排序每次选择未排序列中的最小元素放入其最终位置。对于Ⅱ，希尔排序每次是对划分的子表进行排序，得到局部有序的结果，所以不能保证每一趟排序结束都能确定一个元素的最终位置。对于Ⅲ，快速排序每一趟排序结束后都将枢轴元素放到最终位置。对于Ⅳ，堆排序属于选择排序，每次都将大根堆的根结点与表尾结点交换，确定其最终位置。对于Ⅴ，二路归并排序每趟对子表进行两两归并从而得到若干个局部有序的结果，但无法确定最终位置。
参考答案：A
答案解析：考查各种排序算法的过程。
看第一趟可知仅有 88 被移到最后.
如果是希尔排序，则 12，88，10 应变为 10，12，88。因此排除希尔排序。
如果是归并排序，则应长度为 2 的子序列是有序的，由此可排除归并。
如果是基数排序，则 16，5，10 应变为 10，5，16，由此排除基数。
可以看到，每一趟都有一个元素移到其最终位置，符合冒泡排序特点。
参考答案：B
答案解析：考查各排序算法的特点。
解答本题之前要对不同排序算法的特点极为清楚。对于起泡排序和选择排序而言，每一趟过后都能确定一个元素的最终位置，而由题目中所说，前两个元素和后两个元素均不是最小或最大的两个元素并按序排列。答案 D 中的二路归并排序，第一趟排序结束都可以得到若干个有序子序列，而此时的序列中并没有两两元素有序排列。插入排序在每趟排序结束后能保证前面的若干元素是有序的，而此时第二趟排序后，序列的前三个元素是有序的，符合其特点。
方法一：推理
我们依次分析每个选项：
数据规模肯定要考虑啊，一般情况下，数据规模小的时候用插入排序，数据规模大的时候用快速排序。
数据的存储方式肯定要考虑啊，数据用数组存还是用链表存，适用的排序算法完全不一样。
算法的稳定性肯定要考虑啊，一般情况下，要求稳定的排序用归并排序，没有要求稳定的排序用归并排序或用快速排序均可，优先考虑用快速排序。
数据的初始状态肯定要考虑啊，一般情况下，数据基本有序用直接插入排序。
本题选D。
方法二：断言
下面提供秒题解法：
这道题需要考虑吗？直接全选。
本题选D。
10TB意思是数据量非常大，不适合用内部排序，只能用外部排序，外部排序通常采用归并排序的方法。
本题选D。
答案：A
以最小堆为例，
B，堆不保证节点的个数正好能构成满二叉树
C，最小堆只保证父节点比孩子节点小，并不是二叉排序树
D，堆不保证平衡
A
最大（最小）堆是一棵每一个节点的键值都不小于（大于）其孩子（如果存在）的键值的树。大顶堆是一棵完全二叉树，同时也是一棵最大树。小顶堆是一棵完全完全二叉树，同时也是一棵最小树。
结果中， 是数组形式存储的树。只有A符合定义。
答案：C
根据堆的删除规则，删除操作只能在堆顶进行，也就是删除0元素。
然后让最后一个节点放在堆顶，做向下调整工作，让剩下的数组依然满足最小堆。
删除0后用8填充0的位置，为[8,3,2,5,7,4,6]
然后8和其子节点3,2比较，结果2最小，将2和8交换，为：[2,3,8,5,7,4,6]
然后8的下标为2，其两个孩子节点下标分别为2*2+1=5,2*2+2=6
也就是4和6两个元素，经比较，4最小，将8与4交换，为[2,3,4,5,7,8,6]
这时候8已经没有孩子节点了，调整完成。
C
堆排序的时间，主要由建立初始堆和反复重建堆这两部分的时间开销构成，它们均是通过调用Heapify实现的。时间复杂度O(n*logn)
如果从底部最后的父节点开始建堆，那么我们可以大概算一下： 假如有N个节点，那么高度为H=logN，最后一层每个父节点最多只需要下调1次，倒数第二层最多只需要下调2次，顶点最多需要下调H次，而最后一层父节点共有2^(H-1)个,倒数第二层公有2^(H-2),顶点只有1(2^0)个，所以总共的时间复杂度为s = 1 * 2^(H-1) + 2 * 2^(H-2) + ... + (H-1) * 2^1 + H * 2^0 将H代入后s= 2N - 2 - log2(N)，近似的时间复杂度就是O(N)。
答案：C
可以看出答案都是小堆关键码序列，根据小堆的定义，
K[i]<= K[2i]
K[i]<= K[2i+1]
C选项中关键码序列用完全二叉树表示后很容易看出，结点值d大于了左子结点值c
小根堆中最大的数一定是放在叶子节点上，堆本身是个完全二叉树，完全二叉树的叶子节点的位置大于[n/2]
首先要明白：中括号取整，就是不大于这个数的最大整数
第二要看清下标是从1开始的。那么
1
2 3
4 5 6 7
...............n
n不论是左子树还是右子树，n的父结点一定是 [n/2]，注意中括号的取整规则，正数就是下取整
那么 [n/2] 这个结点还是有子结点的，从 [n/2] + 1 开始一直到 n 都是叶子结点，叶子结点就可能会是最大值，所以选D
看见前边有人回答说没有考虑n ==2 这种情况，诚然，如果n == 2的话，d选项就是3了，但是人家说的是可能。只要具备可能性就行了。
A
直白地讲
小顶堆：父节点上的值比左右孩子上的值小，且所有子树都满足，如：
12
36 24
85 47 30 53
91
大顶堆：父节点上的值比左右孩子上的值大，且所有子树都满足，如：
91
47 85
24 36 53 30
16
二叉排序树：若左孩子不为null，则其值比父节点小；若右孩子不为null。则其值比父节点大。且所有子树都满足。也就是说根节点值比左子树上的都大，比右子树上的都小。所有子树都满足。如：
30
25 35
17 26 33 39
13 （1）（2）
注意：（1）为26的左孩子节点，要比26小，但要比26的父节点25大，所以此处不能填。（2）处为26右孩子节点，比26大，但作为30的左子树，不能大于30.若大于30的值插入，则在右子树上开始查找，如插入31.则31比35小，在35左子树，与33比，小，则继续往33的左子树上比较，若左子树为null，则插入。
所以插入的情况肯定是作为叶子节点插入。
C
依次进行取模运算求出哈希地址：
74 应该放在下标为4 的位置，由于25 已经放在这个地方，所以74往后移动，放在了下标 为5的位置上了。 由于是等概率查找，所以结果为：1/6*（1+3+1+1+2+4）= 2.0
D
（1）选择一个Hash函数，使得每个键字能有一个唯一的地址；
（2）当不同键字具有相同的地址，此时选择一种冲突处理方法至关重要
第一个关键字直接插入，第二个关键字要做1次探测，所以类推n个关键词要做0+1+2+...+(n-1) = n*(n-1) / 2 答案是D
D
与开放定址法相比，拉链法有如下几个优点：
(1)拉链法处理冲突简单，且无堆积现象，即非同义词决不会发生冲突，因此平均查找长度较短；
(2)由于拉链法中各链表上的结点空间是动态申请的，故它更适合于造表前无法确定表长的情况；
(3)开放定址法为减少冲突，要求装填因子α较小，故当结点规模较大时会浪费很多空间。而拉链法中可取α≥1，且结点较大时，拉链法中增加的指针域可忽略不计，因此节省空间；
(4)在用拉链法构造的散列表中，删除结点的操作易于实现。只要简单地删去链表上相应的结点即可。而对开放地址法构造的散列表，删除结点不能简单地将被删结点的空间置为空，否则将截断在它之后填人散列表的同义词结点的查找路径。这是因为各种开放地址法中，空地址单元(即开放地址)都是查找失败的条件。因此在用开放地址法处理冲突的散列表上执行删除操作，只能在被删结点上做删除标记，而不能真正删除结点。
B
A：处理冲突方法：开放地址法和拉链法
B：拉链法的节点空间动态申请更适合无法确定表长的情况
C：想象其中有链表
D：规模较小，查找比较容易，用开放地址法能省空间
正确答案：D
哈希表是一个在时间和空间上做出权衡的经典例子。如果没有内存限制，那么可以直接将键作为数组的索引。那么所有的查找时间复杂度为O(1)；如果没有时间限制，那么我们可以使用无序数组并进行顺序查找，这样只需要很少的内存。
在平衡二叉树中插入结点要随时保证插入后整棵二叉树是平衡的，所以可能需要通过一次或多次树旋转来重新平衡这个树
答案：B
单旋转法为hash表的生成方法
常见哈希冲突解决办法：
1.开放地址法 2.线性探测法 3.链地址法（拉链法） 4.二次探测法
5.伪随机探测法 6.再散列（双重散列，多重散列） 7.建立一个公共溢出区
单旋转法是建立散列函数的一种方法， ，将最后一位数，旋转放置到第一位
常见的散列函数有，直接定址法，数字分析法，平法取中法，取余法，折叠法，随机法
答案是B
D是错误的，Random(N)返回0-N的整数，在查找的时候会出现问题，再次使用Random(N)不一定和上次存储产生的数字一样，这样子就会发生找不到的情况。
答案：B
哈希表（Hash Table）是一种根据关键字直接访问内存存储位置的数据结构。通过哈希表，数据元素的存放位置和数据元素的关键字之间建立起某种对应关系。
A，hash函数可以把字符串等任意长度的输入映射成固定长度的整数，也就是哈希值
B，与A说法相反，错误
C，哈希表建立了哈希值与原值信息存储之间的联系，可以通过哈希值查找到原值信息
D，不同的信息产生相同的哈希值叫哈希冲突。设计哈希函数应尽量避免哈希冲突。因此一般很难冲突。
D
因为有n个顶点，所以有n*n个元素，2*e个非零元素（无向图，对称），所以有n*n-2*e个零元素。
B
n个顶点的树一定有n-1条边，所以需要去掉m-(n-1)=m-n+1条边
选A
森林转二叉树的过程是这样的：
（1）把每棵树转换为二叉树。
（2）第一棵二叉树不动，从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树的根结点的右孩子，用线连接起来。
所以转换后的二叉树的左子树节点的个数加根节点的个数就是第一棵树的节点个数，即二叉树总节点个数m减去根节点右子树节点个数n。
B
因为是无向图，所有顶点度的和必须为偶数
答案：A
1，每条边连接两个顶点，所有顶点的度之和等于边数的2倍，是偶数，正确
2，如两个顶点一条边的图就不满足这个条件，错
3，如三个顶点三条边连成一个三角形的图每个顶点度为2，错
答案为B。
思路： 按照途径中间城市的个数依此累加
6个城市，顶多4个中间城市，因为先经过A再经过B和先经过B再经过A是不一样的，所以用排列数
途径0个中间城市： A(0,4) = 1
途径1个中间城市： A(1,4) = 4
途径2个中间城市： A(2,4) = 12
途径3个中间城市： A(3,4) = 24
途径4个中间城市： A(4,4) = 24
总路径数为：1+4+12+24+24=65
C,图的遍历分为递归和非递归实现，即为深度遍历和广度遍历
答案：A
邻接表顶点数就是图的定点数.一个顶点就是一个表头，共有n个顶点，则共有n个表头，即表头向量大小为n
（i）邻接矩阵表示法，如图：
（ii）关联矩阵表示法
（iii）弧表示法
（iv）邻接表表示法：
这是寻找欧拉回路问题
无向图中，G有欧拉通路的充分必要条件为：G连通，G中只有两个奇度顶点(它们分别是欧拉通路的两个端点)。
所以
答案：B
无向图: 图连通，所有点都是偶数度，或者只有两个点是奇数度。当所有点是偶数度时欧拉路起点可以是任意
点；当有两个奇数度点时起点必须是奇数度点。
有向图: 图连通，所有点出度=入度，或者有一个点入度-出度=1，有一个点出度-入度=1。同样，当所有点
出度=入度时任意点可作为起点；而后者必须以出度-入度=1的点做起点，入度-出度=1的点做终点。
A
无向连通图最少边为n-1，最多边为n*(n-1)/2
选B
设度为0的结点数为n0，度为1的结点数为n1，度为2的结点数为n2，二叉树的总结点为n
则n0+n1+n2 = n ....（1）
对任意数，分支数b=n-1，对二叉树来说，所有的分支是由度为1和2的结点出发的，故b=n1+2*n2
则2*n2 + n1 + 1 = n ...（2）
将n2=10，n1=5代入（1）（2）得度为0的结点个数n0=11
B
首先我们观察题目：二叉搜索树，后序遍历两个知识点。
二叉搜索树，用于搜索，因此 内部节点没有重复的元素 。另外， 满足二叉树的性质，左子树都比自己小，右子树都比自己大。 那么 可想而知，如果按照后序遍历，先左后右最后自己的顺序来遍历树，数组的最后一个元素肯定是自己（父节点），然后剩余的部分分成两个部分，第一部分都比自己小（左子树部分），第二部分都比自己大（右子树部分），因此套用这个关系就可以循环检验出是否是二叉搜索树的后序遍历了。
B
由后序序列知E为根节点，再由中序遍历知左子树为ABCD，右子树为FGH
由后序遍历BDCA知，A为BDC父节点，BDC为右子树，其中C为BD父节点，B为C的左孩子，D为C右孩子，该树左半部分完成
由中序序列和后序序列知FGH序列不变，则H的左孩子为G，G的左孩子为F，H为E的右孩子，该树可知其层次次序序列为EAHCGBDF,故选B
C
A :若根节点有左孩子，则必然根节点不是最小值；所以A错误
B :若根节点有右孩子，则必然根节点小于右孩子这个叶子结点，所以B错误
C：当根节点只有右孩子时，可能为根节点 即为只有右孩子的父节点；
当根孩子只有左孩子，可能为叶子结点
D;只需举出反类即可：不可能为具有右孩子的这个树的右孩子节点
B
先转化为对应的二叉树，如图
C
n个结点的二叉树，度只可能是0，1，2，分别设其对应的结点个数为n0,n1,n2,则有n=n0+n1+n2;
又n结点的树只有n-1条边，故n-1=n1+2*n2
两式联合起来，可等到等式n0=n2+1
这里主要深入理解树的构造方式。
C
平衡二叉树是一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
高度为5的话， 根的左子树高4， 右子树高3
经推倒可以得出，高度与最小节点数对应关系是：
1 -> 1
2 -> 2
3 -> 4
4 -> 7
5 -> 12
B
答案选B。为了让先搜索结点的邻结点也先搜索，只能使用先进先出的队列的思想。宽度优先搜索算法常用于图。
m叉赫夫曼树只有度为m和度为0的结点，按题意为二叉赫夫曼树，故
结点总数为n0+n2，
又对于每个度为2的结点都有2个分支，而度为0的结点没有分支，故结点总数为2n2+1（加的1指根结点），
则n0+n2=2n2+1，得到n0=n2+1，n2=n0-1，
则总结点数为2n0-1=2×4-1=7。
故选C。
A
由后序序列和中序序列可以唯一确定一棵二叉树，这是由两种遍历序列的特点所决定的。
后序序列的最后一个节点是根节点，中序序列中根节点将序列分为左右子树的中序序列；在后序序列中找到左右子树的序列，其最后一个节点是左右子树的根节点，如此递归就能确定整个二叉树的形态。
其算法实现步骤如下：
- 根据后序序***定树的根节点
- 根据根节点在中序序列中划分出二叉树的左、右子树包含哪些节点。然后根据左右子树节点在后序序列中的次序可以确定子树的根节点，即回到步骤 1.
- 如此重复上述步骤，知道每棵子树仅有一个节点为止，如下图所示。
从而可以得到其前序遍历序列为 cedba
B
根据二叉树性质，深度为h的二叉树最多有(2^h)-1个结点。也可以手动计算1+2+4+8+16=31
答案选B。
前序遍历确定根节点，中序遍历确定左右子树。
A， （BDEG，CFH）
（B，（D，EG））；（C，（ ，FH））
（E，（G ，））； （F，（H，））
答案：C
任意一棵二叉树中，度为0的结点总比度为2的结点多一个。
因此度为0的节点（叶子节点）有8个
公有8+10+7=25个
正确答案：D
哈希表是一个在时间和空间上做出权衡的经典例子。如果没有内存限制，那么可以直接将键作为数组的索引。那么所有的查找时间复杂度为O(1)；如果没有时间限制，那么我们可以使用无序数组并进行顺序查找，这样只需要很少的内存。
在平衡二叉树中插入结点要随时保证插入后整棵二叉树是平衡的，所以可能需要通过一次或多次树旋转来重新平衡这个树
答案：D
二叉树第k层最多有2的(k-1)次方个节点
第六层最多有32个节点
第五层最多有16个节点
第四层最多有8个节点
第三层最多有4个节点
第二层最多有2个节点
第一层最多有1个节点
完全二叉树的叶节点只可能出现在后两层
如果完全二叉树有6层，则前5层是满二叉树，总节点数目为16+8+4+2+1+8=39
如果完全二叉树有7层，则前6层是满二叉树，
前六层总节点数目为32+16+8+4+2+1=63
第六层有8个叶子节点，则有32-8=24个非叶子节点
第七层最多有24*2个叶子节点
总节点数目为63+24*2=111
B
解法一
深度为h的二叉树最多有2^h-1个节点，因此h最小取9
解法二
《严蔚敏数据结构C语言版》第120页：结点的层次从根开始定义起，根为第一层，根的孩子为第二层。。。。。。树中结点的最大层次称为树的深度或高度。
第124页：性质4:具有n个结点的完全二叉树的深度为㏒2（n）向下取整 +1。
B
A
B
C
A
C
A
B
D
C
C
D
A
所探测的这些关键字可能是在处理其它关键字冲突过程中放入该位置的。
D
D
A
B
A
A
D
A
B
B
D
B
D
C
D
解析：计算的时候 low=0；high=18；
C
解析：不断递归调用
D
B
这里的“确保”意思是，6个顶点不管怎么连（平行边除外），你是找不出非连通图的情况的，首先5个顶点的全连通图需要的边为n*（n-1）/2=10，再加一条边与另一个顶点相连接，总共11条边，不管你怎么连，都可以确保这个图是连通的（不存在平行边）。
D
B
C
A
A
C
解析：区别：树的高度的定义，只有一个节点的树的高度为 0（则该题选择 B）
B
C
解析：pivotpos==i 时则不交换，i++
B
B
A
A
解析：每次进行一次交换，只需要一个 temp 的位置即可
A
注意：10 的时候 pivotpos++
B
D
C
注意：存在 vi→vj，必然有 vj→vi，但是到达的路径长度没有限制
B
D
堆排序 O(1)
快速排序 O(logn)
归并排序 O(n)
C
D
B
最差情况下是O(n) 如果是最一般最基础的二叉树的话, 因为深度不平衡,所以会发展成单链的形状,就是一条线 n个点那么深 如果是深度平衡的二叉树 o(logn)
C
A
B
A
C
A
A
B
A
A
D
B
B
A
因为深度优先遍历的思想类似于树的先序遍历。其遍历过程可以描述为：从图中某个顶点v出发，访问该顶点，然后依次从v的未被访问的邻接点出发继续深度优先遍历图中的其余顶点，直至图中所有与v有路径相通的顶点都被访问完为止。
C
C
D
A
A
A
D
B
A
C
C
A
B
D
B
B
C
B
A
C
C
B
D
C
C
C
B
B
C
B
C
A
A
A
A
C
D
D
C
B
C
A
C
C
D
A
A
D
B
B
B
D
A
D
D
C
B
D
D
解析：本题考点是线性表相关基本概念。 "线性表的链式存储结构优于顺序存储结构"这种说法是不准确的，可能在某种情况下是对的。比如在随机查找时，顺序表比较有优势。
参考答案A。
本题考点是二叉树的基本特点。 二叉树的每个结点至多只有二棵子树(不存在度大于2的结点)，二叉树的子树有左右之分，次序不能颠倒。某二叉树的前序和后序序列正好相同，则该二叉树一定是空或只有一个结点的二叉树。
参考答案B。
本题考点是数据结构相关基本概念。 数据元素之间的关联方式不可以由存储结点之间的关联方式直接表达。
参考答案A。
本题考点是循环队列的基本操作。 循环队列中，由于入队时尾指针向前追赶头指针；出队时头指针向前追赶尾指针，造成队空和队满时头尾指针均相等。因此，无法通过条件front==rear来判别队列是"空"还是"满"。循环队列的出队操作为sq.front=(sq.ftont+1)% maxsize。
因此，
参考答案D。
本题考点是算法稳定性的度量。 假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，ri=rj，且ri在rj之前，而在排序后的序列中，ri仍在rj之前，则称这种排序算法是稳定的；否则称为不稳定的。归并排序，冒泡排序是稳定的。
参考答案C。
本题考点是最小堆的基本概念。 堆是一种经过排序的完全二叉树，其中任一非终端节点的数据值均不大于（或不小于）其左孩子和右孩子节点的值。最大堆和最小堆是二叉堆的两种形式。 最大堆：根结点的键值是所有堆结点键值中最大者。 最小堆：根结点的键值是所有堆结点键值中最小者。
参考答案D。
本题考点是队列的出队操作。 队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。出队操作的语句为front=(front+1)%(m+1)。
参考答案A。
本题考点是树形结构的特点。 树形结构的特点是一个结点最多有一个直接前趋。
本题考点是进栈和出栈的特点。 栈是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。栈是一种后进先出的数据结构。
因此，本题答题要点如下：
能得到dcba：push，push，push，push，pop,，pop,，pop，pop
但不能得到adbc: 因为d出来的时候 b,c还在栈内，次序必然b在下c在上，因此紧跟d下一个出栈的必然是c而不是b。
本题考点是二叉树的前序、中序和后序遍历算法的基本思想。 遍历是对树的一种最基本的运算，所谓遍历二叉树，就是按一定的规则和顺序走遍二叉树的所有结点，使每一个结点都被访问一次，而且只被访问一次。由于二叉树是非线性结构，因此，树的遍历实质上是将二叉树的各个结点转换成为一个线性序列来表示。
先序遍历是首先访问根，再先序遍历左（右）子树，最后先序遍历右（左）子树。
中序遍历是首先中序遍历左（右）子树，再访问根，最后中序遍历右（左）子树。
后序遍历是首先后序遍历左（右）子树，再后序遍历右（左）子树，最后访问根。
因此，本题答题要点如下：
前序序列：CABEFDHG；
中序序列：BAFECHDG；
后序序列：BFEAHGDC；
参考答案B。
本题考点是数组的数据元素类型的定义。 数组的读、写运算可以读取或修改一个数据元素的一部分或一个整体，当数据元素本身不是原子项时，我们可以修改一个数据元素的一部分。
参考答案D。 本题考点是加工型运算的判别。 清空栈不是加工型运算。
参考答案C。
本题考点是平均查找长度的计算方法。 为确定记录在查找表中的位置，需和给定值进行比较的关键字个数的期望值称为查找算法在查找成功时的平均查找长度。按照此方法计算可得，本题参考答案是C。
参考答案B。 本题考点是数据结构中相关基本概念。 算法是解决问题的步骤；程序是算法的代码实现。算法要依靠程序来完成功能；程序需要算法作为灵魂。
参考答案B。
本题考点是队列的基本操作。 队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。顺序队列的出队操作为sq.front=sq.front+1。
参考答案D。本题考点是队列的基本运算。 获取队头元素不是加工型运算。
参考答案A。
本题考点是图的深度优先遍历。 假设给定图G的初态是所有顶点均未曾访问过。在G中任选一顶点v为初始出发点(源点)，则深度优先遍历可定义如下：首先访问出发点v，并将其标记为已访问过；然后依次从v出发搜索v的每个邻接点w。若w未曾访问过，则以w为新的出发点继续进行深度优先遍历，直至图中所有和源点v有路径相通的顶点(亦称为从源点可达的顶点)均已被访问为止。若此时图中仍有未访问的顶点，则另选一个尚未访问的顶点作为新的源点重复上述过程，直至图中所有顶点均已被访问为止。
参考答案C。本题考点是加工型运算、引用型运算的功能。 插入是加工型运算。
本题考点是堆的定义和建立方法。 n个关键字序列Kl，K2，…，Kn称为堆，当且仅当该序列满足如下性质(简称为堆性质)： (1) ki≤K2i且ki≤K2i+1 或(2)Ki≥K2i且ki≥K2i+1(1≤i≤ n/2 ) 若将此序列所存储的向量R[1..n]看做是一棵完全二叉树的存储结构，则堆实质上是满足如下性质的完全二叉树：树中任一非叶结点的关键字均不大于(或不小于)其左右孩子(若存在)结点的关键字。根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最小者的堆称为小根堆。根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最大者，称为大根堆。
因此，本题答题要点如下：
因为不满足（ai<a2i 和ai<a2i+1）如a1=16,a3=10，所以不是小顶堆。 可以调整为堆：（4，15，10，16，19，23，36，20）
本题考点是二分查找算法的定义及过程。 二分查找又称折半查找，优点是比较次数少，查找速度快，平均性能好；其缺点是要求待查表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。
因此
：
参考答案C。 本题考点是二叉树中各层结点个数的计算方法。二叉树中第i层上的结点个数最多为2i-1。
参考答案C。本题考点是二叉树的性质。结点有n个，于是子树总数为2n，所以的边数为n-1，因此结点的空子树数量为2n-(n-1)= n+1。
参考答案C。
本题考点是有向图中顶点度的概念。有向图的某个顶点v，把以v为终点的边的数目，称为v的入度；以v为始点的边的数目，称为v的出度；v的度则定义为该顶点的入度和出度之和。
参考答案B。
本题考点是有向图顶点度数与弧数的关系。有向图的某个顶点v，把以v为终点的边的数目，称为v的入度；以v为始点的边的数目，称为v的出度；v的度则定义为该顶点的入度和出度之和。显然，在一个有向图中，所有顶点的度数之和等于所有弧数的2倍。
参考答案B。
本题考点是广义表与二叉树的转换。二叉树中的度就是分支的数目。没有分叉的二叉树节点的度就是0度。如果一个节点只有一个分叉就是1度。两个分叉就是2度。该广义表转换为二叉树后，度为1的结点是b，e，g。
参考答案C。
本题考点是完全二叉树中结点的个数。在一棵深度为h的完全二叉树中，所含结点个数不大于2^h -1。回答此题可以用实例来验证，例如当h=2时，完全二叉树最多有3个结点。
参考答案B。
本题考点是折半查找的基本思想。二分查找又称折半查找，优点是比较次数少，查找速度快，平均性能好；其缺点是要求待查表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。
参考答案C。 本题考点是数据结构的基本概念。二叉树是每个节点最多有两个子树的树结构，不是数据的存储结构。
参考答案C。
本题考点是循环链表的优点。插入和删除方便的存储结构是链表，这是因为链表插入和删除时不需要移动元素就能实现。只在表的首、尾进行插入操作的线性表用尾指针表示的单循环链表最适宜，减少了移动指针的次数。
参考答案B。
本题考点是二分查找的性能。100个元素的排序数组分别进行二分查找和顺序查找，在查找失败的情况下，顺序查找最多比较100次，二分查找最多比较7次。
参考答案C。
本题考点是栈的应用。栈是一种后进先出的数据结构，5在6之后进栈，肯定要在6之前出栈。
参考答案A。
本题考点是循环队列的基本操作。循环队列的出队列操作是在队头进行的，会使队头位置发生变化。
参考答案A。
本题考点是链表的操作。根据链表结点类型的定义可以看出，该链表是一个双向链表。删除双链表中结点p(由p指向的结点)的操作是： q=p->left; r=p->right; q->right=r; r->left=q;
参考答案D。
本题考点是堆排序的时间复杂度。在上述算法中，堆排序的时间复杂度是O(nlogn)，其他算法的时间复杂度都是O(n2)。
参考答案C。
本题考点是三元树中结点数的计算。树中结点数等于所有结点度数的和加1。所以：2+1+2+X=2*3+1*2+2*1+X*0+1，所以X=6。
参考答案B。
本题考点是二叉树的性质。叶子结点个数 = 度为2的结点个数 + 1。
参考答案C。
本题考点是图的基本性质。在一个图中，所有顶点的度数之和等于所有边的2倍，这是因为一条边一定是连接两个顶点。。
参考答案C。
本题考点是具有记忆功能的数据结构。由栈的定义可知，栈是一种后进先出的线性表，所以栈具有记忆功能。
参考答案D。
本题考点是栈的定义。栈是一种后进先出（先进后出）的线性表，可以进行插入和删除数据。
参考答案C。
本题考点是队列的定义。队列是一种先进先出的线性表，可以进行插入和删除数据。
参考答案D。
本题考点是线性链表的特点。线性链表中的各元素在存储空间中的位置不一定是连续的，且各元素的存储顺序也是任意的。
参考答案A。
本题考点是线性表的性质。线性表是一种线性结构。栈、队列和线性链表都是线性结构。二叉树是一种非线性结构。
参考答案D。
本题考点是循环链表的特点。循环链表最大的特点是只要指出表中任何一个结点的位置，就可以从它出发依次访问到表中其他所有结点。
参考答案C。
本题考点是单链表的基本操作。线性表（a1,a2,…,an）以链接方式存储时，该线性表就是一个单链表。单链表访问第i位置元素的时间复杂性为O（n），因为需要从首元素开始逐个向后访问。
参考答案C。
本题考点是双向链表的插入操作。在双向链表指针p的结点前插入一个指针q的结点操作是： q->Rlink=p; q->Llink=p->Llink; p->Llink->Rlink=q; p->Llink=q;
参考答案B。
本题考点是单链表的基本操作。在单链表指针为p的结点之后插入指针为s的结点的操作是： s->next=p->next; p->next=s;
参考答案B。
本题考点是单链表的基本操作。由于单链表带有头结点，因此从头结点的下一个结点开始存储元素，所以判定该表为空表的条件是看头结点的下一个结点是否为空。
参考答案C。
本题考点是线性表操作的性能分析。对于顺序存储的线性表，例如数组，访问结点时是随机访问方式，直接利用下标就可以定位要访问哪个元素，时间复杂度为O(1)。增加、删除结点时需要移动大量其他元素，时间复杂度为O(n)。
参考答案B。
本题考点是递归的使用。首先计算f(1)的值，当x=1时，函数返回值是x* f(x-1)；即1*f(0)，而f(0)=2，因此，f(1)的值为2。再计算f(f(1))=f(2)，当x=2时，函数返回值是2*f(1)=2*2=4。
参考答案D。
本题考点是栈的应用。栈的一个重要应用就是判别表达式中括号是否匹配，基本思想是遇到左括号进栈，遇到右括号时不进栈，并弹出栈顶的左括号，如果最终无元素进栈，并且栈中也无左括号，则匹配成功。
本题参考答案是D。本题考点是队列的基本操作。链接方式存储的队列，一般都是在队头进行删除运算，头指针需要修改，但当删除队列中最后一个元素时，头、尾指针都需要修改。
参考答案B。
本题考点是二叉树的基本性质。当一个二叉树为空树时，此时，它的度小于2。
参考答案D。
本题考点是二叉树高度的计算方法。对于有n个结点的二叉树，其高度是不确定的，与结点的排列方式有关，最大为n（每个节点就只有一棵子树的时候），最小是完全二叉树的时候，当然也有其他情况可以满足，最小为log2n，其他情况的都是在这两种之间，不大于最大不小于最小。
本题考点是二叉树遍历方式的种类。
二叉树的遍历有三种方式，如下：
1）前序遍历（DLR），首先访问根结点，然后遍历左子树，最后遍历右子树。简记根-左-右。
2）中序遍历（LDR），首先遍历左子树，然后访问根结点，最后遍历右子树。简记左-根-右。
3）后序遍历（LRD），首先遍历左子树，然后遍历右子树，最后访问根结点。简记左-右-根。
本题考点是图的遍历。
从图中某一顶点出发，按某种搜索方法访遍其余顶点，且使每一顶点仅被访问一次。这一过程称为图的遍历。遍历图的基本搜索方法有两种：深度优先搜索DFS（Depth First Search）和广度优先搜索BFS（Broad First Search）。这两种方法都适用于有向图和无向图。
空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度，记做(n)=O(f(n))。
本题考点是二叉树的特性。由于二叉树的前序序列是先访问根结点再访问左右子树得到的，二叉树的后序序列是先访问左右子树最后访问根结点得到的，因此，高度等于其结点数的二叉树的前序和后序正好相反。
栈既然是一种线性表，所以线性表的顺序存储和链式存储结构同样适用于栈。
本题考点是开放定址法中增量序列的取法。
开放定址法就是从发生冲突的那个单元开始，按照一定的次序，从散列表中查找出一个空闲的存储单元，把发生冲突的待插入元素存入到该单元中的一类处理冲突的方法。增量序列的取法主要有线性探测再散列，二次探测再散列，伪随机数序列三种。
队列的特点是：先进先出；
单链的特点是：迭代的时候只能向前，不能回头；
在只知道头指针的情况下：
入队：首先要遍历单链，找到尾指针，时间复杂度O(n);
出队：直接访问头指针即可，时间复杂度O(1);
只知道尾指针的情况下，出入队时间均为O(1)，因为是循环链表，尾指针所指的下一个元素就是头指针所指元素，所以出队时不需要遍历整个队列。
本题考点是无向图的遍历方法。
应首先根据9条边画出该无向图，然后根据无向图深度优先和广度优先搜索法的定义进行遍历，得到结点序列。 深度优先搜索法:0-->2-->3-->4-->5-->1 广度优先搜索法:0-->1-->2-->4-->5-->3
参考答案C。
本题考点是非空循环链表的特性。因为是非空循环链表，所以尾结点的下一个结点应该是头结点。
参考答案B。
考点是栈空的条件。判断栈空的条件是栈顶元素是否为0。
参考答案C。
本题考点是无向完全图的特性。4个点，最多可以连出6条线。n顶点完全图的边数为C（n，2）= n*（n-1）/2，
参考答案A。
本题考点是栈的基本原理。由于输入序列中d在c之后输入，若在e输入之前d和c还未输出，那么将来输出时d一定在c之前输出。
参考答案C。
本题考点是向量中存储地址的计算方法。向量首地址是100，那么第i个元素的地址是100+(i-1)*2。
参考答案B。
本题考点是二叉树的遍历方法。由二叉树的前、中根序列可以确定这棵二叉树，再运用后根遍历方法得到后序序列。或者可以用排除法，因为先根序列为abdefcg，中根为defbagc，可以看出a为根结点，defb和gc分别为左、右子树，那么a必然是后根遍历序列的末结点，这样可排除C选项。再对defb和gc采用上述方法进行判定，可以排除A和D。
参考答案D。
本题考点是二叉树的特性。最少k个，最多2^k-1个，因为没有说明这是什么二叉树。如果是满二叉树那就是2^k-1个。如果是完全二叉树，那最少是2^k个，最多2^k-1个。如果既不是满二叉树，也不是完全二叉树，那普通二叉树深度为k时的结点数量就是最少k个，最多2^k-1个。
参考答案是B。
本题考点是连通图的基本概念。六个顶点在一条线上时，最少5条边，连通而不存在回路。
参考答案A。
本题考点是顺序表存储地址计算方法。由于第一个结点的地址为da1，那么第二个结点的地址就是da1+(2-1)*m=da1+m，以此类推，第i个结点的地址为da1+(i-1)*m。
参考答案A。
本题考点是操作顺序表时时间复杂度的计算方法。假设顺序表L,长度为n，求第i个节点L[i],直接前驱L[i-1],因此为O（1），答案B需要移动n-i个节点，因此为O(n)，答案C也需要移动n-i个节点，答案D根据排序方法不同最慢O(n2)，最快O(nlogn)。
参考答案C。
本题考点是直接插入排序算法的时间复杂度。直接插入排序的做法是：每次从无序表中取出第一个元素，把它插入到有序表的合适位置，使有序表仍然有序。插入过程的时间复杂度是O(N2)。
A。
本题考点是各种排序算法的时间复杂度。快速排序的平均时间为O(nlogn)，速度最佳。
D
本题考点是排序方法稳定性的判定。假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，ri=rj，且ri在rj之前，而在排序后的序列中，ri仍在rj之前，则称这种排序算法是稳定的；否则称为不稳定的。上述选项只有基数排序满足稳定性的定义。
参考答案D。
本题考点是排序算法所需辅助空间的计算。快速排序为O(logn )，为栈所需的辅助空间；归并排序所需辅助空间最多，其空间复杂度为O(n)；链式基数排序需附设队列首尾指针，则空间复杂度为O(rd )。希尔排序空间复杂度是O（1） 因为只有一个缓冲单元。
参考答案B。
本题考点是二叉树遍历的应用。表达式通常用二叉树的中序来表示，得到的表达式是中缀表达式。
参考答案D。
本题考点是构造哈希函数的方法。二分查找是查找算法，不能用来构造哈希函数。
参考答案D。
本题考点是哈希表中常用的处理冲突的方法。哈希表中常用的处理冲突的方法有开放定址法、再哈希法、链地址法和建立公共溢出区方法四种。
参考答案D。
本题考点是二叉排序树的特点。二叉排序树又称二叉查找树，亦称二叉搜索树。 它或者是一棵空树；或者是具有下列性质的二叉树：
（1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值；
（2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值；
（3）左、右子树也分别为二叉排序树；
参考答案A。
本题考点是二叉树的构造方法。3个结点的二叉树有5种形态：两层树：根左右；三层树： 根左（第二层）左（第三层）、根左（第二层）右（第三层）、根右（第二层）左（第三层）、根右（第二层）右（第三层）。
参考答案B。
本题考点是栈的特性。由于输入序列中c在b之后输入，若在d输入之前b和c还未输出，那么将来输出时c一定在b之前输出。
参考答案A。
本题考点是图的遍历过程。图进行深度优先遍历时采用栈作为存储结构，广度优先遍历时采用队列作为存储结构。
参考答案A。
本题考点是单链表的删除操作。要删除单链表中的某结点，只要令该结点的前驱结点的next指向该结点的后继结点即可。
参考答案A。
本题考点是关键路径的时间复杂度的求法。设AOE网有n个顶点，e条边，在求事件可能的最早发生时间及允许的最迟发生时间，以及活动的最早开始时间和最晚开始时间时，都要对图中所有顶点及每个顶点边表中所有的边结点进行检查，时间花费为O（N+E）。
参考答案D。
本题考点是单链表的查找操作。如果查找的是第一个是比较1次，第二个是2次，第n个是n次，要查找的元素每个概率相等即每个为1/n，所以平均是(1/n)(1+2+3+……n)=(1+n)/2次。查找失败是即是每个都查找了一遍都没找到所以是n次。
参考答案D。
本题考点是数据结构的种类。线性结构、图、树和集合等都属于数据结构，环形结构不属于数据结构。
参考答案D。
本题考点是算法的特性。一般说来，算法必须具备以下五个重要特性：确定性、可行性、输入、输出和有穷性，判断不是算法的特性。
参考答案A。
本题考点是线性表中插入元素平均效率的计算方法。0,1,2,3,4,5,6,...n-1,n，每一个的可能是1/(n+1)。
参考答案B。
本题考点是空栈的判断条件。栈顶元素为0的栈是空栈。
本题考点是顺序表的删除操作。具体移动次数取决于待删除元素所在的位置，比如删除倒数第1个，则移动次数为0，删除倒数第2个则移动次数为1，依此类推，删除倒数第i个，则需移动i-1次。而平均移动次数则取决于表长n、各待删除元素的位置及其被删除概率。设pi为删除第i个元素的概率，则平均移动次数为：p1*(n-1)+p2*(n-2)+p3*(n-3)+......+pn*0，如果是等概率，则pi=1/n，则平均移动次数为：(1/n)*(n-1)+(1/n)*(n-2)+...+(1/n)*1 = (1/n)*(1+2+...+(n-1)) = (n - 1) / 2。
本题考点是单链表的基本操作。双链表中，在任一结点可以向两边遍历。而在单链表中，只能从前往后遍历，不可以逆向，所以必须知道单链表的头指针才能遍历整个单链表。
顺序表相对于链表主要优点有随机存取访问快、操作简单、容易实现等。
上述数据希尔排序过程如下：
上述数据快速排序的基本过程如下：
参考答案：C
按上三角存储，m7,2 对应的是 m2,7，在它之前有：
参考答案：C
森林的先根遍历对应它自己转化后二叉树的先序遍历，森林的后根遍历对应它自己转化后 二叉树的中序遍历，所以先根和后根可以唯一确定森林转化后的二叉树，如下：
后序遍历为：b,f,e,d,c,a
参考答案：B
参考答案：A
参考答案：D
参考答案：D
参考答案：B
D。通过模拟出入栈操作， 可以判断入栈序列in和出栈序列 out 是否合法。因此，已知 in 序列可以判断 out 序列是否为可能的出栈序列； 已知 out 序列也可以判断in序列是否为 可能的入栈序列，A和B错误。如果每个元素入栈后立即出栈， 则 in 序列和 out 序列相同， C错误。如果所有元素都入栈后才依次出栈， 则 in 序列和 out 序列互为倒序， D 正确。
D。 图 1 是满足条件的二叉树 T1, 图 2 是满足条件的 二叉树 T2， 结点中有值表示这个结点是编码字符。 T1 和 T2 的结点数不同， A错误。 T1的高 度等于 T2 的高度， B错误。 出现频次不同的字符在 T1 中也可能处千相同的层， C错误。 对 千定长编码集， 所有字符一定都在 T2 中处于相同的层， 而且都是叶子结点。
归并的含义是将两个或两个以上的有序表合并成一个新的有序表”， 而二路归并是将两个有序表合并为一个新的有序表。
D。【解析】直接插入排序和快速排序的特点如下表所示。
可见， I、II、III、IV 都是采用直接插入排序而不采用快速排序的可能原因。
解答：
设原来插入新结点前指向 p 的直接后继结点的指针为 q ，题目要求在 p 和 q 之间插入新的结点 s 。
双向链表插入结点的时候要修改四个指针，这四个指针的修改顺序没有强制要求，也就是有 4!=24 种连接顺序，但是这里注意要按照题目要求的顺序连线。
初始为图(a)。四个指针的初始状态为：
p->next = q; q->prev = p; s->next = null; s->prev = null;
最终状态为：
p->next = s; q->prev = s; s->next = q; s->prev = p;
先按照题目要求执行前两步：
s->next = q; 注意此时 q = p->next，即 s->next = p->next; 此时变为图(b)。
p->next = s; 此时变为图(c)。
还有两条线没有连，目标是得到图(d)。还需要连接 s->prev = p; 和 q->prev = s; 注意此时 q = s->next，即 s->next->prev = s; 找了一圈发现没有这种写法，命题组在这里加大了难度，把写法复杂化，我们只能逐一分析选项了。按照选项的指针在图(c)上运行：
A选项，等价于 q->prev = p; s->prev = p; 第一句错误。
B选项，等价于 s->prev = s; s->prev = p; 第一句错误。
C选项，等价于 s->prev = p; q->prev = s; 正确。
D选项，等价于 s->prev = null; q->prev = p; 第一句和第二句均错误。
本题选C。
解答：
三元组存储矩阵的表示方法出现在2017年第3题，三元组表的表项存储了行row、列col、值value三种信息，我们还需要知道矩阵 M 的规模 rows × cols，即 M 的行数 rows 和 M 的列数 cols，这个信息应该直接给出，即 I 和 III 。
本题选A。
解答：
构建哈夫曼树：
每个关键字的查找长度为：
注意，题目要求求加权平均长度，这里的权重就是频次。
加权平均长度为 (3×3+3×4+3×5+3×6+2×8+2×10)/(3+4+5+6+8+10)=2.5 。
如果不考虑权重，会错误计算为 (3+3+3+3+2+2)/6≈2.67 ，从而误选C。
本题选B。
方法一：递归法
首先按照后序遍历左右根的递归遍历顺序自下而上，从左到右将 f, d, b, e, c, a 填入二叉树。
然后按照先序遍历根左右的递归顺序输出先序序列 a, e, d, f, b, c 。
本题选A。
方法二：环线法
首先构造环线按后序遍历顺序填入后序序列 f, d, b, e, c, a 。
然后按照环线进行先序遍历输出先序序列 a, e, d, f, b, c 。
本题选A。
注：补充一下二叉树前序遍历、中序遍历、后序遍历的特征：
按照箭头方向遍历。
- 前序遍历顺序为“根左右”，在第一次访问某结点时输出该结点的关键字。
- 中序遍历顺序为“左根右”，在第二次访问某结点时输出该结点的关键字。
- 后序遍历顺序为“左右根”，在第三次访问某结点时输出该结点的关键字。
解答：
无向连通图 G 中各边的权值均为 1 ，G 可以视为无权图，可以用广度优先搜索求单源最短路径，在求无权图的单源最短路径问题中，广度优先搜索比Dijkstra算法更加高效。III正确。
I 和 II 是最小生成树算法，也可直接排除。
本题选B。
解答：
I. 插入操作可能会导致关键字上溢，关键字上溢到根结点，树的高度加一。I 正确。
II.
- 如果删除的关键字位于叶结点：
- 在叶结点中删除该关键字，该叶结点一定发生变化。分析到这里，可以不用进行继续分析。继续分析简写如下，如果删除该结点后关键字个数 n≥⌈m/2⌉−1 ，没有后续操作，如果该结点删除关键字后关键字个数 n<⌈m/2⌉−1 ，需要从兄弟结点借一个关键字，又分兄弟够借和兄弟不够借两种情况，这里不进行继续分析。无论上述哪种情况，此时叶结点一定发生变化。
- 如果删除的关键字位于非叶结点：
- 用被删除关键字的后继关键字替换被删除关键字，该后继关键字为于被删除关键字的右子树的最下层最左边，即一定位于叶结点，该叶结点一定发生变化。分析到这里，可以不用进行继续分析。继续分析简写如下，如果该结点删除关键字后关键字个数 n≥⌈m/2⌉−1 ，没有后续操作，如果删除该结点后关键字个数 n<⌈m/2⌉−1 ，需要从兄弟结点借一个关键字，又分兄弟够借和兄弟不够借两种情况，这里不进行继续分析。此时叶结点一定发生变化。
综上，无论删除关键字是位于叶结点还是位于非叶结点，一定有叶结点发生变化。II 正确。
III. B树中所有结点均可以存储关键字，若查找的关键字位于非叶结点，则不可能查找到叶结点。III错误。
IV. 插入新的关键字，插入后进行调整，新插入的关键字不一定位于叶结点中。可以用依次将关键字5, 6, 9, 14, 8, 2, 12, 15, 13插入初始为空的4阶B树进行模拟，最后13位于非叶结点中。也就是插入关键字后若被插入关键字所在的结点需要进行调整（结点发生分裂），且被插入的关键字此时恰为该结点的第 ⌈m/2⌉ 个关键字，则该关键字会上溢到该结点的父结点，如此迭代，也就是在这种情况下被插入的关键字最终一定位于非叶结点中。
综上，I 和 II 正确。
本题选B。
解答：
由于元素数量过大，不方便画图，采用公式法。
若采用折半查找法查找一个顺序表中不存在的元素，最大比较次数为对应二叉搜索树的高度，设结点数为 � ，
二叉搜索树高度为 ℎ=⌈log(n+1)⌉=⌊logn⌋+1 。
代入 n=600 ，解得 ℎ=10 。
本题选B。
解答：
本题为送分题，牢记八大排序表格。
稳定的排序有：插入排序、冒泡排序、归并排序、基数排序。
不稳定的排序有：选择排序、希尔排序、快速排序、堆排序。
本题选C。
解答：
快速排序一个非常重要的性质是枢轴左边的关键字全部小于或等于枢轴，枢轴右边的关键字全部大于或等于枢轴。
由于序列比较长，正向推导不容易观察，可以代入选项后分析。
A选项，枢轴为11 ，左边 68 > 11 。该选项错误。
B选项，枢轴为70 ，右边 23 < 70 。该选项错误。
C选项，枢轴为80，右边 48 < 80 。该选项错误。
D选项，枢轴为81。该选项正确。
本题选D。
参考答案： C
B
参考答案：D
数据元素是数据的基本单位
数据项是数据的最小单位
数据结构是带有结构的各数据元素的集合
O(log2n)。
语句y++;的执行次数为 log2n。
参考答案：B
顺序表中的数据连续存储，所以要求的地址 = 第一个元素的地址 +（i-1）个元素 × 每个元素的长度
第5 个元素的地址为：100+2*4=108 。
参考答案：A
在顺序表中插入一个结点的时间复杂度都是O(n2)
排序的时间复杂度为O(n2 )或O(n log2 n)。
顺序表是一种随机存取结构，访问第 i 个结点和求第 i 个结点的直接前驱都可以直接通过数组的下标直接定位，时间复杂度是O(1) 。
参考答案：A
当第一个有序表中所有的元素都小于（或大于）第二个表中的元素，只需要用第二个表中的第一个元素依次与第一个表的元素比较，总计比较n次。
栈是后进先出的线性表，一个栈的入栈序列是1， 2， 3，… ， n ，且输出序列的第一个元素为n ，说明1 ，2，3 ，, ， n 一次性全部进栈， 再进行出栈，所以p1=n ，p2=n-1 ，…，pi=n-i+1 。
参考答案：D
对于非循环队列，尾指针和头指针的差值便是队列的长度
对于循环队列，差值可能为负数， 所以需要将差值加上MAXQSIZE （ n ），然后与MAXQSIZE （ n ）求余，即（ n + r - f ) % n 。
参考答案：A
先储存栈顶的data，再将栈顶指向下一个结点：x=top->data；top=top->link；
参考答案：D
入队时，rear先+1再对数组长度取余。数组A[0…m] 中共含有 m+1 个元素，故在求模运算时应为 %（m+1）。
参考答案：D
设度为0 结点（叶子结点）个数为n0，度为1 的结点个数为n1，度为2 的结点个数为n2，有n0=n2+1，n0+n1+n2=1001
由完全二叉树的性质可得n1=0 或1，即有501 个叶子结点。
参考答案：C
若每层仅有一个结点，则树高h 为1025 ；且其最小树高为log 2 (1025) + 1=11 ，即h 在11 至1025 之间。
参考答案：C
利用二叉链表存储树时，规则为：兄弟相连、长兄为父、孩子靠左、兄弟靠右，右指针是指向兄弟结点，因为根节点没有兄弟结点，故根节点的右指针指向空。
参考答案：C
根据题意可知按照先左孩子、再右孩子、最后双亲结点的顺序遍历二叉树，即后序遍历二叉树。
参考答案：B
度为4，不是二叉树！！！
先求总节点个数为：根节点+子节点
根节点个数为1 + 子节点个数为204+103+12+101 = 123
非叶子结点总数为20+10+1+10 =41个
故叶结点=123-41=82个
参考答案：C
因为先序遍历结果是“中左右” ，后序遍历结果是“左右中” ，当没有左子树时，就是“中右”和“右中” ；当没有右子树时，就是“中左”和“左中” 。则所有的结点均无左孩子或所有的结点均无右孩子均可，所以A、B 不能选，又所有的结点均无左孩子与所有的结点均无右孩子时，均只有一个叶子结点，故选C。
参考答案：B
在哈夫曼树中只有度为0（叶子结点）和度为2 的结点。设叶子结点的个数为n0，度为2 的结点的个数为n2，由二叉树的性质n0=n2+1 ，则总结点数n=n0+n2=2*n0-1 ，得到n0=100 。
参考答案：C
按照中序遍历的顺序，X的上一个刚刚访问过的结点就应为X左子树最右的结点
参考答案：A
以二叉链表作为存储结构时，只能得到节点的左右孩子信息，结点的任意序列中的前驱和后继信息只能在遍历的动态过程中才能得到，为了查找结点的前驱或后继，引入线索二叉树。
参考答案：C
森林转换为二叉树,"兄弟相连、长兄为父、孩子靠左、头根为根 "，F有n个非终端节点,所以转换为二叉树后所有的空的右指针域就是n个根节点没有兄弟,根结点的右指针域也为空，二叉树中右指针域为空的节点有(n+1)个。
参考答案：
1、先找出根结点，先序遍历规则为DLR，所以A为根节点；根据中序遍历LDR将二叉树分为 BFD 和GEHC；再根据先序遍历，可知B、C为A的左右子树，同理可画出这棵二叉树
2、后序遍历为LRD，所以后序遍历为 F D B G H E C A
3、如图
参考答案：D
图的广度优先遍历算法类似于二叉树的按层次遍历。
参考答案：C
对于一些特殊的图，比如只有一个顶点的图，其BFS 生成树的树高和DFS 生
成树的树高相等。一般的图，根据图的BFS 生成树和DFS 树的算法思想， BFS 生成树的树高比DFS 生成树的树高小。
参考答案：C
按深度优先遍历:先访问所在结点，再访问它的邻接点,访问过的跳过找下一个未访问的结点，直到访问完所有的结点。即0-1-3-4-2-5-6
参考答案：D、D
参考答案：B
判断有没有环的方法：深度优先排序、广度优先排序、拓扑排序
参考答案：
参考答案：C
总查找次数 N=1+2+3+…+n=n(n+1)/2 ，则平均查找长度为 N/n=(n+1)/2 。
参考答案：D
折半查找要求线性表必须采用顺序存储结构， 且表中元素按关键字有序排列。
参考答案：C
分块查找的优点是： 在表中插入和删除数据元素时， 只要找到该元素对应的块，就可以在该块内进行插入和删除运算。由于块内是无序的，故插入和删除比较容易，无需进行大量移动。如果线性表既要快速查找又经常动态变化，则可采用分块查找。
参考答案：A
表中共10 个元素， 第一次取(1+10)/2 =5 ，与第五个元素20 比较， 58 大于20，再取(6+10)/2 =8 ，与第八个元素70 比较，依次类推再与30 、50 比较，最终查找失败。
参考答案：B
22 个记录的有序表，其折半查找的判定树深度为log2 (22) + 1=5 ，且该判定树不是满二叉树，即查找失败时至多比较5 次，至少比较4 次
参考答案：C
二叉排序树不一定是平衡树，它是只要求了左右子树与根结点存在大小关系，但是对左右子树之间没有层次差异的约束，因此通过二叉排序树进行查找不一定能够满足logn的。
只有是一棵平衡的二叉排序树时，其查找时间性能才和折半查找类似。
参考答案：C
A 、B、C、D 四个选项构造二叉排序树都以100 为根，易知A 、B、D 三个序列中100 的左孩子为80,如图1 ，而C 选项中100 的左孩子为60，如图2
参考答案：C
由题意可知，A的平衡因子为1，又由于A的右孩子的平衡因子为1，左孩子的平衡因子为0，由此可知，A的右孩子上仅有右孩子，A的左孩子上无左右孩子，在平衡二叉树中插入一个结点后造成不平衡，说明插入结点只能插在A的右孩子的左孩子上，这种情形属于在右子树的左子树上插入结点的情形，即RL型。
参考答案：C
一个M阶的B-树有以下基本性质：
根结点的子女数为[2, M]；
每个非根节点所包含的关键字个数 j 满足：m/2 - 1 <= j <= m - 1；
除根结点以外的所有结点（不包括叶子结点）的度数正好是关键字总数加1，故内部子树个数 k 满足：m/2<= k <= m ；
所有的叶子结点都位于同一层。
由于根节点至少有两颗子树，选项C不正确
参考答案：C
B树只能支持随机检索，而B+树是有序的树，既能支持随机检索，又能支持顺序检索。
参考答案：C
哈希函数都要视情况而选择
参考答案：A
在同义词构成的单链表中，查找该单链表表中不同元素，所消耗的时间不同。
参考答案：D
关键字15 放入位置4，关键字38 放入位置5，关键字61 放入位置6，关键字84放入位置7 ，再添加关键字49，计算得到地址为5，冲突，用二次探测法解决冲突得到新地址为6 ，仍冲突，再用用二次探测法解决冲突，得到新地址为4，仍冲突，再用用二次探测法解决冲突，得到新地址为9，不冲突，即将关键字49 放入位置9。
1、画出判定树
2、查找元素54，需依次与30, 63, 42, 54 元素比较；
3、查找元素90，需依次与30, 63,87, 95 元素比较；
4、求ASL 之前，需要统计每个元素的查找次数。判定树的前3 层共查找1＋ 2 × 2＋ 4×3=17 次；最后一层只有5个元素，5× 4=20 次，
所以ASL ＝ （ 17＋ 20 ）/12＝ 37/12
1、
2、查找63, 首先要与地址值为 H(63)=63%16=15 的关键字比较，即63 与31 比较 , 不匹配，然后用线性探测法，与32,17,46,47,63 相比，一共比较 6 次.
3、查找60, 首先要与H(60)=60%16=12 号单元内容比较，因为12 号单元为空 ，所以应当只比较这一次即可。
4、ASL=（1× 6＋ 2×1＋ 5× 3+6×1 ）/11＝ 29/11
平均查找长度： ASL =（ 1+1+1+2+3+4+1+2 ） /8=15/8
C
D
B
对关键字进行冒泡排序，关键字逆序时比较次数最多。
参考答案：D
比较次数最多时，第一次比较n-1 次，第二次比较n-2 次, 最后一次比较1次，即(n-1)+(n-2)+ … +1= n(n-1)/2 。
B
快速排序的平均时间复杂度为O(nlog 2n) ，但在最坏情况下，即关键字基本排好序的情况下，时间复杂度为O(n^2)。
B
C
B
先建立初堆，然后再调整
C
堆排序、希尔排序的空间复杂度为O(1) ，快速排序的空间复杂度为O(log 2n)，归并排序的空间复杂度为O(n) 。
C
不稳定排序有：希尔排序、简单选择排序、快速排序、堆排序；
稳定排序有：直接插入排序、折半插入排序、冒泡排序、归并排序、基数排序。
D
局部排序 选择堆排序
A
快速排序的每趟排序能将作为枢轴的元素放到最终位置；
冒泡排序的每趟排序能将最大或最小的元素放到最终位置；
堆排序的每趟排序能将最大或最小的元素放到最终位置。
A
链式存储：结点内存储单元地址一定连续；相邻结点存储空间不一定连续；
顺序存储：结点内存储单元地址一定连续；相邻结点存储空间一定连续；
D
循环队列：指定是用顺序表表示的队列
链表：指定是使用链式存储的方式
哈希表：指定使用散列表存储的方式
栈：是线性结构中的受限性表；特点是后进先出，栈顶进，栈顶出
A、B、C描述的均为物理结构即数据的存储结构，D是逻辑结构，所以选D。
C
将数据逻辑结构映射成存储数据时,需要存储所有数据元素的值和数据元素之间关系。
C
有序表是表中元素有顺序，并没有具体要求如何存取，所以是逻辑结构
A
D
B
可读性：有助于人们阅读理解
正确性：算法能正确的解决问题
健壮性：对非法输入能进行相应处理
效率与存储量需求：效率高
A
A
常用的时间复杂度所耗费的时间由小到大依次是：
O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(2^n) < O(n!) < O(n^n)
B
考察线性表的定义（关键词：数据元素、相同特性、有限、有序）
A无序；C序列有无穷个；D邻接表是图的一种存储结构
C
考察线性表的定义：线性表（linear list）是数据结构的一种，一个线性表是n个具有相同特性的数据元素的有限序列。
A
一对一，开头元素没有直接前驱，结尾元素没有直接后继
A
A
链表不支持指定序号读取元素（非随机访问）。顺序表支持随机访问，且在结尾插入删除元素，不需要移动其他元素，满足要求。
C
(1)顺序表随机存取，效率更高
(2)链表首先需要遍历，且链表有复杂的指针操作，严格来说更麻烦。顺序表可以随机访问，交换操作更简便。
(3)都需要遍历，打印，一样复杂
C
读取顺序表中的元素，给出指定下标即可，复杂度为O(1)，插入算法的复杂度为O(n)。
B
存储空间顺序表利用一片连续空间存储相同类型的元素，所占用的存储空间由元素的数据类型和元素个数共同决定，存放顺序不影响空间大小。
A 顺序表结点没有像链表一样的指针域，数据域占总空间的比例大，因此存储密度大。
B、C 为链表的优点
D 顺序表方便存储一对一的线性逻辑结构，像数和图这样的一对一或一对多的逻辑结构，通常不用于顺序存储。
D
顺序表使用连续空间表示元素之间的逻辑结构，所以在原有空间不足时需要重新申请一块新的更大的连续空间，即 m + n 个。
A
A 顺序表的数组表示通过数组下标查询元素，复杂度为O(1)，B、C顺序表的插入删除操作平均复杂度为O(n)。
C
A 只有线性表的顺序存储结构的逻辑顺序与物理顺序一致。
B 完全二叉树和满二叉树比较适合顺序存储，而存储一般的二叉树时，空间利用率低。
D 数据结构中有三种基本操作，分别是插入、删除和查找，但不是每种都符合。比如，二维数组没有删除，栈没有查找。
D
顺序表支持随机存取，即可以通过起始地址加上对应的下表获取指定元素。
B
顺序表支持随机存取，可以通过起始地址加下标的方式获取指定元素。静态链表也是链表，没法指定序号获取元素。
C
C
D
B
删除单链表中最后一个元素后，尾指针要更新，必须先遍历到倒数第二个结点才行，O(n)复杂度。
D
最快排序nlogn，简历单链表n，最复杂为n*nlogn
D
链接地址相当于->next指针，a->f->e
首先要构造出这条链表，题目已经降低难度告诉你表头元素为c，正向构造单链表为：
c(1008H)→a(1000H)→e(1010H)→b(1004H)→d(100CH)→NULL
当然命题组可以加大难度，不告诉你表头元素为c这个条件，那么就需要从d的链接地址为NULL从表尾到表头逆向构造链表。如果进一步加大难度，可以添加一些不在链表中的干扰元素。
按照题意，插入f(1014H)到a和e之间，单链表变为：
c(1008H)→a(1000H)→f(1014H)→e(1010H)→b(1004H)→d(100CH)→NULL
a指向f，链接地址为1014H；e指向b，链接地址为1004H；f指向e，链接地址为1010H。
本题选D。
注意：如果没有按照题目要求a, e, f的顺序输出链接顺序，而是按照链表a, f, e的顺序输出链接顺序，会误选C，所以审题一定要仔细。
B
静态链表的特点：不需要移动元素，只需要修改指针；需要一次性分配较大量空间，存储结构可以反应数据之间的逻辑关系。
B
链表能反应逻辑关系，插入删除O(1)；顺序存储插入删除O(n)；散列存储不能反应逻辑关系。
C
静态链表使用数组实现。指针是相对指针，是数组下标
D
双链表双向访问
A
A 查找x的时候，链表与顺序表一样，都要遍历；链表删除元素为O(1)，顺序表删除需要移动元素，O(n)
B 链表O(n)，顺序表O(1)
C 都是遍历k个元素
D 涉及随机存取，顺序表更优
C
每个链表的时间复杂度如下：
A：（1）O(1)，（2）O(n)需要定位到倒数第二个结点，（3）O(1)，（4）O(1)
B：（1）O(n)，（2）O(1)，（3）O(n)需要定位到第一个结点，（4）O(1)
C：（1）O(1)，（2）O(1)，（3）O(1)，（4）O(1)
D：（1）O(1)，（2）O(n)需要定位到倒数第二个结点，（3）O(1)，（4）O(1)
D
空表或长度为1的表均符合条件
A
因为结点是一个一个申请的，所以栈满出现的概率变低；
栈空与不空与存储方式没有关系，看具体业务；
栈的删除、插入操作都在栈顶，不会在中间位置。相比于顺序表纯粹定位的方式，链式存储下删除、插入更复杂了，因为需要维护各种指针。
D
栈顶结点的数据域交给x；栈顶后移一位
C
top == -1 表示栈空，top = 0时，还没有存值，所以得出结论：先指针加1，再赋值，即C。
B
已d为开头的序列有：decba、dceba、dcbea、dcbae
C
栈是线性结构，排除B、D；
栈是逻辑概念，没有限定具体实现方式，排除A
B
第一次：3+2= 5，S1：5，8，5（栈顶）；S2：*，-（栈顶）
第二次：8-5= 3，S1：5，3（栈顶）；S2：*（栈顶）
第三次：5*3= 15，S1：15；S2：空
这道题很简单，模拟计算过程就行，唯一要注意的是先弹出的是a，后弹出的b，且计算时b op a，b在前，a在后。审题务必仔细。
B
出栈序列有：123，213，321，231，132
B
栈和队列都是线性结构，一对一。
抽象数据类型包含相关操作，栈和队列不一样；存储结构栈和队列都可以自己选，没有必须一样；运算就是操作，不一样；
A
两个栈顶碰到了（差值为1）就是栈满。top大于top1，所以栈满的条件：top2 - top1 == 1
C
（1）错误。阶乘，尾递归都能很好的转换为普通循环
（3）错误。出现顺序不能确定
（4）错误。只允许在一端进行操作
I. 将递归改写成非递归有很多种方式，可以用数组，栈，散列表等等，并非必须使用栈，比如经典的斐波那契数列问题，可以用借助数组用动态规划实现，进一步可以用滚动数组优化，最后只需要3个变量即可实现。I错误。
II. 这里利用了栈先进后出的特性，例如函数A中执行过程中嵌套了函数B（也可以是自身），那么这个时候先要把函数A中的一些变量记录下来，就是压入栈中，然后再调用函数B，等函数B执行完毕返回后，回到函数A继续执行，此时将栈中保存的函数A的变量弹出。II正确。
Ⅲ．入栈次序，出栈序列有卡特兰数种，并不唯一，所以无法确定。Ⅲ错误。
Ⅳ．栈是一种受限的线性表，只允许在其一端进行操作。Ⅳ错误。
综上，Ⅰ、Ⅲ、Ⅳ错误。
本题选C。
B
栈只能在栈顶进行插入、删除操作
D
A：abcd入栈，dc出栈，e入栈，eb出栈，f入栈，fa出栈
B：abc入栈，cb出栈，d入栈，da出栈，e入栈，e出栈，f入栈，f出栈
C：ab入栈，b出栈，c入栈，ca出栈，de入栈，e出栈，f入栈，fd出栈
B
与普通顺序栈相比，他们的存取时间都是O(1)，随机存取，好处是节省了存储空间，两个站一起使用空间，利用率更高；因为一次可以申请更大空间，所以上溢的可能性降低，下溢肯定是不变的，没元素了还出元素，就是下溢。
C
P3第一个输出，则P1、P2出栈的相对顺序为P2P1，P2P1为2,3……n中的两个值，P1不可能为2
D
A的出栈序列：1243
B的出栈序列：3241
C的出栈序列：1324
D的出栈序列：1342
A
C
C选项不可能以6 5 顺序出栈（除非6第一个出栈）
B
A[0...5]：大小为6
删除一个：front = (front + 1) % 6 = 0
加入一个：rear = (rear + 1) %6 = 2
加入一个：rear = (rear + 1) %6 = 3
C
队列先进先出，按次序出队，按次序入栈，即按1,2,3,4,5,6依次入栈。C选项：3先出栈，则2比1先出栈。
方法一：模拟
A的操作顺序为①①②②①①③③。
B的操作顺序为②①①①①①③。
C无法找到合适的操作序列。
D的操作顺序为②②②②②①③③③③③。
本题选C。
方法二：单调性
由于只能通过栈改变序列中某子串单调性一次，所以输出序列中没有按照先进先出顺序出队的子串一定通过栈要被反转。
A中子串3, 4没有按序出队，被反转成4, 3，正确。
B中子串1没有按序出队，被反转成1，正确。
C中子串1, 2没有按序出队，但没有被反转，错误。
D中子串1, 2, 3, 4, 5, 6没有按序出队，被反转成6, 5, 4, 3, 2, 1，正确。
本题选C。
如果本题加大难度，输入序列为乱序，需要进行元素值和元素下标的一对一映射，写代码需要建立两个键值哈希表，一个键为元素值，值为元素下标，另一个键为元素下标，值为元素值。
A
入队时需要去到链表尾部，保证成环。O(n)
B
D
队列的操作：
InitQueue(&Q)：初始化队列，构造一个空队列
QueueEmpty(&Q)：判断队列是否为空，为空返回true
EnQueue(&Q, x)：队列未满，则入队
DeQueue(&Q, &x)：若队列未空则出队，用x返回
GetHead(Q, &x)：若队列未空，则读队头元素交给x
C
循环队列长度：
队列长度：[MaxSize - (Q.front - Q.rear)] % MaxSize ，即本地长度 =[21 - (8-3)] % 21 = 16
A
（1）复杂度高不适合（2）复杂度低单操作麻烦不适合
A：入队O(n)，入队要去队尾；出队O(1)
B：入队O(1)；出队O(1)
C：入队O(1)；出队O(1)
D：入队O(1)；出队O(1)
B
①，正确，FIFO
②，错误，没有优先级，按顺序操作
③，错误，删除的时候队列里有元素就行
④，正确，FIFO
D
循环队列解决了假溢出，其它特点依然存在
B
(规律)输出首先双端队列：ab...X...d...的输入序列，且现在输出了d，a,b,X没有输出，则输出序列一定不存在X在a,b中间的情况。因为输入的时候a,b相邻，出的时候只能从一边出。排除AC
A
B
本题没有说指针位置，考虑所有情况下复杂度最低、最简便的。
使用单向循环链表，设尾指针，复杂度最低且最简便。
答案：A
解释：特殊值法。设n=0，易知仅调用一次fact(n)函数，故选A。
或者用3
答案：B
解释：元素出队的序列是e2、e4、e3、e6、e5和e1，可知元素入队的序列是e2、e4、e3、e6、e5和e1，即元素出栈的序列也是e2、e4、e3、e6、e5和e1，而元素e1、e2、e3、e4、e5和e6依次进入栈，易知栈S中最多同时存在3个元素，故栈S的容量至少为3。
答案：C
解释：初始栈顶指针top为n+1，说明元素从数组向量的高端地址进栈，又因为元素存储在向量空间V[1..n]中，所以进栈时top指针先下移变为n，之后将元素x存储在V[n]。
本题考察栈先进后出的性质，调用函数入口为main()，main()入栈，接着调用S(1)，S(1)入栈，S(1)需要递归调用S(0)，S(0)入栈，题目要求“自栈底到栈顶保存的信息”，即main()→S(1)→S(0)，如果是“自栈顶到栈底保存的信息”就要反过来。
本题选A。
评：这道题的代码含义不理解，递归计算 
。
哈夫曼树是构造哈夫曼编码过程的图形化展示，哈夫曼树有许多重要的性质，哈夫曼树是一棵完满二叉树，每个结点的度只能为 0 或 2。
我们先根据选项构造出对应的完满二叉树，再检查该完满二叉树是否为哈夫曼树。
为了更加贴近哈夫曼树：
- 任意一个结点的左孩子权值小于或等于右孩子权值。
- 一个非叶结点的权值等于其左孩子权值和右孩子权值之和。
选项A的根结点的左孩子10的左右孩子权值出现了两种情况，意味着这两条路径一定不会出现在同一棵哈夫曼树中。错误。
选项B的根结点24的左右孩子权值出现了两种情况，意味着这两条路径一定不会出现在同一棵哈夫曼树中。错误。
选项C虽然成功构造出了一棵完满二叉树，但这棵完满二叉树不是一棵哈夫曼树，错误原因有两点：
- 第一点：哈夫曼树中不会出现权值为 0 的结点，因为哈夫曼树对应哈夫曼编码，每个叶结点的权值表示词频或出现几率，权只为 0 表示该单词不存在，显然哈夫曼编码不可能对不存在的单词进行统计。也就是哈夫曼树中每个结点的权值为正数。
- 第二点：哈夫曼编码是一种贪心编码，每次选择词频最小的两个字符，我们假设 0 合法，我们用 0、 10、3 和 11 这四个关键字尝试还原这棵哈夫曼树，我们发现还原失败。其实也可直接观察，第一次选中 0 和 10，第二次选中 3 和 11，明显有第一次选中的 10 大于第二次选中的 3，不符合哈夫曼编码。也就是说，如果命题组加大难度，将选项C修改为 24, 10, 9 和 24, 14, 11，虽然没有违反第一点，但违反第二点，仍然错误。
选项D的这棵完满二叉树是一棵哈夫曼树，可以进行如下验证。
本题选D。
这道题只能逐个分析选项。
A选项中，根结点的度不一定为2，A错误。
B选项中，一棵平衡二叉树是一棵二叉搜索树，由于中序遍历可得到一个降序序列，树中最小元素一定是最右结点，即无右子树，但可能有左子树，所以不一定是叶结点，B错误。
C选项中，AVL树的插入分两步，第一步是按照二叉搜索树的规则插入元素，该元素此时是叶结点，第二步是调整二叉搜索树为AVL树，如果此时二叉搜索树不平衡，需要进行旋转，旋转后该元素所在结点不一定是叶结点，C错误。
D正确。
本题选D。
解答：
第一次出现“失配”（s[i] ≠ t[j]）时，i = j = 5，隐藏含义是主串和模式串下标都从0开始，这个条件非常重要。
方法一：计算 next 数组后模拟
第一步：计算出模式串的next数组。
本人自编口诀优化前的next数组：第一格负一，第二格零，前缀等于后缀取最长。
这里由于主串和模式串下标都从0开始，没必要用优化后的next数组求解。优化后的next数组增加的1和下标都从0开始相比下标都从1开始减少的1正好相抵。
第二步：遍历主串对模式串进行匹配。
第一次匹配在模式串下标为5的位置出现失配，找到之前匹配的子串为abaab，最长相同前缀与后缀为ab，将前缀的ab移动到后缀ab的位置。
或者查表next数组失配字符c，其下标为5，其next值为next[5] = 2，已匹配字符数为5，移动位数 = 已匹配字符数 - 失配位置对应的匹配值 = 5 - 2 = 3。模式串向后移动3格，从失配位置开始重新进行匹配，此时 i = 5, j = 2。
或者查表next数组失配字符c，其下标为5，其next值为next[5] = 2，j指针直接跳转到模式串下标为2的位置，从失配位置开始重新进行匹配，此时 i = 5, j = 2。
本题选C。
方法三：贪心
贪心找到最多匹配的情况，同样画出上图。虽然这个方法不严谨，好在本题足够简单，从失配位置开始重新进行匹配，很容易看到i = 5, j = 2。
本题选C。
补充本人对本题完整KMP匹配过程的模拟。
typedef int ElemType;
∥链表数据的类型定义
typedef struct LNode{
∥链表结点的结构定义
ElemType
data;
∥结点数据
struct Lnode *link;
∥结点链接指针
} *LinkList;
int Search_k(LinkList list, int k){
∥查找链表 list 倒数第 k 个结点，并输出该结点 data 域的值
LinkList p = list->link, q = list->link; ∥指针 p、q 指示第一个结点
int count = 0;
while(p != NULL){ ∥遍历链表直到最后一个结点
if(count < k) count++;
∥计数，若 count < k 只移动 p
else q = q->link; p = p->link;
∥之后让 p、q 同步移动
} ∥while
if(count < k)
return 0; ∥查找失败返回 0
else { ∥否则打印并返回 1
printf(“%d”,q->data);
return 1;
}
} ∥Search_k
解答：
⑴
⑵ 根据上述思路，C代码如下（含测试用例）：
#include <stdio.h>
#include <string.h>
#define MAXV 11
typedef struct { // 图的类型定义
int numVertices, numEdges; // 图中顶点数和有向边数
char VerticesList[MAXV]; // 顶点表，MAXV为已定义常量
int Edge[MAXV][MAXV]; // 邻接矩阵
} MGraph;
int printVertices(MGraph G) {
int indegrees[G.numVertices];
int outdegrees[G.numVertices];
memset(indegrees, 0, sizeof(indegrees));
memset(outdegrees, 0, sizeof(outdegrees));
// 遍历无向图统计所有点的出度和入度
for (int i = 0; i < G.numVertices; i++) {
for (int j = 0; j < G.numVertices; j++) {
outdegrees[i] += G.Edge[i][j];
indegrees[j] += G.Edge[i][j];
}
}
int count = 0;
// 遍历indegrees和outdegrees数组统计出度大于入度的顶点
for (int i = 0; i < G.numVertices; i++) {
if (outdegrees[i] > indegrees[i]) {
printf("%c", G.VerticesList[i]);
count++;
}
}
return count;
}
int main() {
MGraph G;
G.numEdges = 5;
G.numVertices = 4;
memset(G.VerticesList, 0, sizeof(G.numVertices));
char V[4] = {'a', 'b', 'c', 'd'};
for (int i = 0; i < G.numVertices; i++) {
G.VerticesList[i] = V[i];
}
memset(G.Edge, 0, sizeof(G.numVertices));
int M[4][4] = {{0, 1, 0, 1}, {0, 0, 1, 1}, {0, 0, 0, 1}, {0, 0, 0, 0}};
for (int i = 0; i < G.numVertices; i++) {
for (int j = 0; j < G.numVertices; j++) {
G.Edge[i][j] = M[i][j];
}
}
int count = printVertices(G);
printf("%d", count);
return 0;
}
复杂度分析
- 时间复杂度： O(n^2) ，其中 n 为图中点个数。因为需要遍历整个邻接矩阵，所以为 O(n^2) 。
- 空间复杂度： O(n) ，开辟了 O(n) 大小的辅助数组。
时间复杂度无法优化，我们考虑优化空间复杂度，去掉辅助数组，边遍历边统计。修改后C代码如下（含测试用例）：
#include <stdio.h>
#include <string.h>
#define MAXV 11
typedef struct { // 图的类型定义
int numVertices, numEdges; // 图中顶点数和有向边数
char VerticesList[MAXV]; // 顶点表，MAXV为已定义常量
int Edge[MAXV][MAXV]; // 邻接矩阵
} MGraph;
int printVertices(MGraph G) {
int count = 0, indegree = 0, outdegree = 0;
// 遍历无向图统计所有点的出度和入度
for (int i = 0; i < G.numVertices; i++) {
indegree = 0; // i的入度
outdegree = 0; // i的出度
for (int j = 0; j < G.numVertices; j++) {
outdegree += G.Edge[i][j];
indegree += G.Edge[j][i];
}
if (outdegree > indegree) {
printf("%c", G.VerticesList[i]);
count++;
}
}
return count;
}
int main() {
MGraph G;
G.numEdges = 5;
G.numVertices = 4;
memset(G.VerticesList, 0, sizeof(G.numVertices));
char V[4] = {'a', 'b', 'c', 'd'};
for (int i = 0; i < G.numVertices; i++) {
G.VerticesList[i] = V[i];
}
memset(G.Edge, 0, sizeof(G.numVertices));
int M[4][4] = {{0, 1, 0, 1}, {0, 0, 1, 1}, {0, 0, 0, 1}, {0, 0, 0, 0}};
for (int i = 0; i < G.numVertices; i++) {
for (int j = 0; j < G.numVertices; j++) {
G.Edge[i][j] = M[i][j];
}
}
int count = printVertices(G);
printf("%d", count);
return 0;
}
复杂度分析
- 时间复杂度： O(n^2) ，其中 n 为图中点个数。因为需要遍历整个邻接矩阵，所以为 O(n^2) 。
- 空间复杂度： O(1) ，使用了常数个辅助变量。
(1)可生成 3 个初始归并段(2 分)
1、37,51,63,92,94,99(2 分)
2、14,15,23,31,48,56,60,90,166(2 分)
3、 8,17,43,100(2 分)
(2)最大可能长度为 n，最小可能长度为 m。(各占 1 分)
解答：
注意本题二叉树以静态数组的方式表示，数组起始下标为0。
先画出二叉树，然后将其填充为完全二叉树，按照层序遍历顺序填写编号：
如果根结点下标为0（适用于C/C++语言数组）有 ：
left_child_id = parent_id * 2 + 1;
right_child_id = parent_id * 2 + 2;
如果根结点下标为1，这时候题目会写明条件。
为了方便解答，结构体中的Elemtype默认为int。
方法一：递归
利用二叉搜索树的性质：设 x 是二叉搜索树中的一个结点。如果y是x左子树中的一个结点，那么y.key≤x.key，如果y是x右子树中的一个结点，那么y.key≥x.key。
C代码如下（含测试用例）：
#include <stdio.h>
#include <string.h>
#include <limits.h>
#define MAX_SIZE 20011
#define false 0
#define true 1
typedef int bool;
typedef struct { // MAX_SIZE为已定义常量
int SqBiTNode[MAX_SIZE]; // 保存二叉树结点值的数组
int ElemNum; // 实际占用的数组元素个数
}SqBiTree;
bool helper(SqBiTree T, int i, long long lower, long long upper) {
if (i >= T.ElemNum || T.SqBiTNode[i] == -1) { // 越界或者为空结点
return true;
}
if (T.SqBiTNode[i] <= lower || T.SqBiTNode[i] >= upper) {
return false;
}
return helper(T, 2 * i + 1, lower, T.SqBiTNode[i]) && helper(T, 2 * i + 2, T.SqBiTNode[i], upper);
}
bool isValidBST(SqBiTree T) {
return helper(T, 0, LONG_MIN, LONG_MAX);
}
int main() {
int a1[10] = {40, 25, 60, -1, 30, -1, 80, -1, -1, 27};
SqBiTree bt1;
memset(bt1.SqBiTNode, 0, sizeof(bt1.SqBiTNode));
bt1.ElemNum = 10;
for (int i = 0; i < bt1.ElemNum; ++i) {
bt1.SqBiTNode[i] = a1[i];
}
int ans1 = isValidBST(bt1);
if (ans1 == true) {
printf("T1 is a binary search tree\n");
} else {
printf("T1 is not a binary search tree\n");
}
int a2[11] = {40, 50, 60, -1, 30, -1, -1, -1, -1, -1, 35};
SqBiTree bt2;
memset(bt2.SqBiTNode, 0, sizeof(bt2.SqBiTNode));
bt2.ElemNum = 11;
for (int i = 0; i < bt2.ElemNum; ++i) {
bt2.SqBiTNode[i] = a2[i];
}
int ans2 = isValidBST(bt2);
if (ans2 == true) {
printf("T2 is a binary search tree\n");
} else {
printf("T2 is not a binary search tree\n");
}
return 0;
}
复杂度分析
- 时间复杂度： O(n) ，其中 n 为二叉树的结点个数。在递归调用的时候二叉树的每个结点最多被访问一次，因此时间复杂度为 O(n) 。
- 空间复杂度： O(n) ，其中 n 为二叉树的结点个数。递归函数在递归过程中需要为每一层递归函数分配栈空间，所以这里需要额外的空间且该空间取决于递归的深度，即二叉树的高度。最坏情况下二叉树为一条链，树的高度为 n ，递归最深达到 n 层，故最坏情况下空间复杂度为 O(n) 。
方法二：中序遍历
利用二叉搜索树的性质的推论：中序遍历为单调递增序列。
递归遍历：
考虑保存整个中序遍历序列，最后进行检查。
C代码如下（含测试用例）：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_SIZE 20011
#define false 0
#define true 1
typedef int bool;
typedef struct { // MAX_SIZE为已定义常量
int SqBiTNode[MAX_SIZE]; // 保存二叉树结点值的数组
int ElemNum; // 实际占用的数组元素个数
}SqBiTree;
void inorder(SqBiTree T, int i, int *a, int *j) {
if (i >= T.ElemNum || T.SqBiTNode[i] == -1) { // 越界或者为空结点
return;
}
inorder(T, 2 * i + 1, a, j);
a[(*j)++] = T.SqBiTNode[i];
inorder(T, 2 * i + 2, a, j);
}
bool isValidBST(SqBiTree T){
int *a = (int *)malloc(sizeof(int) * MAX_SIZE);
int j = 0;
inorder(T, 0, a, &j);
for(int k = 0; k < j - 1; k++) {
if(a[k] >= a[k + 1]) {
return false;
}
}
return true;
}
int main() {
int a1[10] = {40, 25, 60, -1, 30, -1, 80, -1, -1, 27};
SqBiTree bt1;
memset(bt1.SqBiTNode, 0, sizeof(bt1.SqBiTNode));
bt1.ElemNum = 10;
for (int i = 0; i < bt1.ElemNum; ++i) {
bt1.SqBiTNode[i] = a1[i];
}
int ans1 = isValidBST(bt1);
if (ans1 == true) {
printf("T1 is a binary search tree\n");
} else {
printf("T1 is not a binary search tree\n");
}
int a2[11] = {40, 50, 60, -1, 30, -1, -1, -1, -1, -1, 35};
SqBiTree bt2;
memset(bt2.SqBiTNode, 0, sizeof(bt2.SqBiTNode));
bt2.ElemNum = 11;
for (int i = 0; i < bt2.ElemNum; ++i) {
bt2.SqBiTNode[i] = a2[i];
}
int ans2 = isValidBST(bt2);
if (ans2 == true) {
printf("T2 is a binary search tree\n");
} else {
printf("T2 is not a binary search tree\n");
}
return 0;
}
复杂度分析
- 时间复杂度： O(n) ，其中 n 为二叉树的结点个数。二叉树的每个结点最多被访问三次，因此时间复杂度为 O(n) 。
- 空间复杂度： O(n) ，其中 n 为二叉树的结点个数。递归栈最深为 n ，中序遍历数组大小为 n ，因此需要额外的 O(n) 的空间。
优化空间复杂度，使用一个变量 prev 记录前驱。由于非空二叉树T的结点值均为正数，初始化 prev=0 。
C代码如下（含测试用例）：
#include <stdio.h>
#include <string.h>
#define MAX_SIZE 20011
#define false 0
#define true 1
typedef int bool;
typedef struct { // MAX_SIZE为已定义常量
int SqBiTNode[MAX_SIZE]; // 保存二叉树结点值的数组
int ElemNum; // 实际占用的数组元素个数
}SqBiTree;
bool inorder(SqBiTree T, int i, int* prev) {
if (i >= T.ElemNum || T.SqBiTNode[i] == -1) { // 越界或者为空结点
return true;
}
if (!inorder(T, 2 * i + 1, prev)) {
return false;
}
if (prev > T.SqBiTNode[i]) {
return false;
}
prev = T.SqBiTNode[i];
return inorder(T, 2 * i + 2, prev);
}
bool isValidBST(SqBiTree T) {
int prev = 0;
return inorder(T, 0, prev);
}
int main() {
int a1[10] = {40, 25, 60, -1, 30, -1, 80, -1, -1, 27};
SqBiTree bt1;
memset(bt1.SqBiTNode, 0, sizeof(bt1.SqBiTNode));
bt1.ElemNum = 10;
for (int i = 0; i < bt1.ElemNum; ++i) {
bt1.SqBiTNode[i] = a1[i];
}
int ans1 = isValidBST(bt1);
if (ans1 == true) {
printf("T1 is a binary search tree\n");
} else {
printf("T1 is not a binary search tree\n");
}
int a2[11] = {40, 50, 60, -1, 30, -1, -1, -1, -1, -1, 35};
SqBiTree bt2;
memset(bt2.SqBiTNode, 0, sizeof(bt2.SqBiTNode));
bt2.ElemNum = 11;
for (int i = 0; i < bt2.ElemNum; ++i) {
bt2.SqBiTNode[i] = a2[i];
}
int ans2 = isValidBST(bt2);
if (ans2 == true) {
printf("T2 is a binary search tree\n");
} else {
printf("T2 is not a binary search tree\n");
}
return 0;
}
复杂度分析
- 时间复杂度： O(n) ，其中 n 为二叉树的结点个数。二叉树的每个结点最多被访问三次，因此时间复杂度为 O(n) 。
- 空间复杂度： O(n) ，其中 n 为二叉树的结点个数。递归栈最深为 n ，因此需要额外的 O(n) 的空间。
迭代遍历：
迭代遍历是对递归遍历的改进，如果中途检测到不符合二叉搜索树性质，可以直接终止，加速程序运行，但无法降低算法时间复杂度。
C代码如下（含测试用例）：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#define MAX_SIZE 20011
#define false 0
#define true 1
typedef int bool;
typedef struct { // MAX_SIZE为已定义常量
int SqBiTNode[MAX_SIZE]; // 保存二叉树结点值的数组
int ElemNum; // 实际占用的数组元素个数
}SqBiTree;
bool isValidBST(SqBiTree T) {
int *stk = (int *)malloc(sizeof(int) * MAX_SIZE);
int top = 0; // 栈顶指针
int prev = -1; // 初始前驱下标
int curr = 0; // 初始指向根结点
while (top > 0 || (curr < T.ElemNum && T.SqBiTNode[curr] != -1)) {
while (curr < T.ElemNum && T.SqBiTNode[curr] != -1) {
stk[top++] = curr;
curr = curr * 2 + 1;
}
curr = stk[--top];
// 如果中序遍历得到的结点的值小于前驱，说明不是二叉搜索树
if (T.SqBiTNode[curr] < (prev == -1 ? INT_MIN : T.SqBiTNode[prev])) {
return false;
}
prev = curr;
curr = curr * 2 + 2;
}
return true;
}
int main() {
int a1[10] = {40, 25, 60, -1, 30, -1, 80, -1, -1, 27};
SqBiTree bt1;
memset(bt1.SqBiTNode, 0, sizeof(bt1.SqBiTNode));
bt1.ElemNum = 10;
for (int i = 0; i < bt1.ElemNum; ++i) {
bt1.SqBiTNode[i] = a1[i];
}
int ans1 = isValidBST(bt1);
if (ans1 == true) {
printf("T1 is a binary search tree\n");
} else {
printf("T1 is not a binary search tree\n");
}
int a2[11] = {40, 50, 60, -1, 30, -1, -1, -1, -1, -1, 35};
SqBiTree bt2;
memset(bt2.SqBiTNode, 0, sizeof(bt2.SqBiTNode));
bt2.ElemNum = 11;
for (int i = 0; i < bt2.ElemNum; ++i) {
bt2.SqBiTNode[i] = a2[i];
}
int ans2 = isValidBST(bt2);
if (ans2 == true) {
printf("T2 is a binary search tree\n");
} else {
printf("T2 is not a binary search tree\n");
}
return 0;
}
复杂度分析
- 时间复杂度： O(n) ，其中 n 为二叉树的结点个数。二叉树的每个结点最多被访问三次，因此时间复杂度为 O(n) 。
- 空间复杂度： O(n) ，其中 n 为二叉树的结点个数。栈最多存储 n 个结点，因此需要额外的 O(n) 的空间。
Morris遍历：
Morris遍历是对迭代遍历的进一步优化。
Morris是就是著名的计算机科学家J.H.Morris，他还与D.E.Knuth和V.R.Pratt一起提出了KMP算法。
Morris中序遍历伪代码如下：
PRINT-BINARY-TREE(T)
x = T.root
y = NIL // rightmost node in x's left subtree
while x ≠ NIL
y = x.left
if y ≠ NIL
while y.right ≠ NIL and y.right ≠ x
y = y.right
if y.right == NIL
y.right = x
x = x.left
continue
else y.right = NIL
print x.key
x = x.right
本质是构造出类似中序遍历线索二叉树的二叉树，构造线索指向后继（下图中用虚线表示）。但注意，若能通过二叉树的孩子指针找到后继的线索（例如二叉树T1中关键字25所在结点到关键字27所在结点的线索），则该线索无需构造，如下图所示：
二叉树静态数组的Morris遍历难度比指针结点表示的二叉树大，由于没有空指针和指针变换，考虑用空结点记录中序遍历后继指针指向。为了区分指针和数字，且避开缺省值-1，下标值从-2开始储存。因为这里所有元素为正，即 x.key≥1 ，我们要存储下标，因为树不为空，所以 y.right 的下标大于等于0，要避开所有正数和缺省-1，结构体SqBiTNode数组中没有填充的部分默认为0，也要完美避开，存负的下标值-2，这样就符合小于等于-2，正好没有产生任何冲突。
由于 x 左子树的最右结点不可能右孩子，所以完全可以直接用空结点存储中序遍历后继结点下标，但是如果是需要记录会发生冲突的线索比如后序遍历的后继线索，这样做就会出现冲突，一旦出现冲突，就需要开辟 O(n) 的数组记录。用静态数组表示的二叉树的Morris遍历的空间复杂度为 O(1) 不简单是巧合。
修改指针这部分是真的复杂，目前想到的办法通过正负号来区分里面存的是下标还是元素值，保证此算法是一个原地算法。这个思路可以参考2018年第41题，其最优解为原地哈希，都是运用负号进行标记，两者原地构造存储有异曲同工之妙。
这里默认MAX_SIZE足够大，不会造成记录后继指针指向时数组越界。
C代码如下（含测试用例）：
#include <stdio.h>
#include <string.h>
#define MAX_SIZE 20011
#define false 0
#define true 1
typedef int bool;
typedef struct { // MAX_SIZE为已定义常量
int SqBiTNode[MAX_SIZE]; // 保存二叉树结点值的数组
int ElemNum; // 实际占用的数组元素个数
}SqBiTree;
bool isValidBST(SqBiTree T) {
int prev = -1; // 前驱结点下标，初始化为NIL
int x = 0; // 初始指向根结点下标，初始化为根结点下标 x = T.root
int y = -1; // x 左子树的最右结点下标，初始化为NIL y = NIL
while (x < T.ElemNum && T.SqBiTNode[x] != -1) { // while x != NIL
y = 2 * x + 1; // y = x.left
if (y < T.ElemNum && T.SqBiTNode[y] != -1) { // if y != NIL
while (T.SqBiTNode[2 * y + 2] != -1 && T.SqBiTNode[2 * y + 2] != 0 && -T.SqBiTNode[2 * y + 2] - 2 != x) { // while (y.right != NIL && y.right != x)
y = T.SqBiTNode[2 * y + 2] < -1 ? -T.SqBiTNode[2 * y + 2] - 2 : 2 * y + 2; // y = y.right
}
if (T.SqBiTNode[2 * y + 2] == -1 || T.SqBiTNode[2 * y + 2] == 0) { // if (y.right == NIL)
T.SqBiTNode[2 * y + 2] = -(x + 2); // y.right = x
x = 2 * x + 1; // x = x.left
continue;
} else {
T.SqBiTNode[2 * y + 2] = -1; // y.right = NIL
}
}
if (T.SqBiTNode[x] < (prev == -1 ? -MAX_SIZE : T.SqBiTNode[prev])) { // 比较当前结点和前驱结点的值检查是否违反二叉搜索树性质
return false;
}
prev = x; // 更新前驱结点下标
x = T.SqBiTNode[2 * x + 2] < -1 ? -T.SqBiTNode[2 * x + 2] - 2 : 2 * x + 2; // x = x.right
}
return true;
}
int main(int argc, const char * argv[]) {
int a1[10] = {40, 25, 60, -1, 30, -1, 80, -1, -1, 27};
SqBiTree bt1;
memset(bt1.SqBiTNode, 0, sizeof(bt1.SqBiTNode));
bt1.ElemNum = 10;
for (int i = 0; i < bt1.ElemNum; ++i) {
bt1.SqBiTNode[i] = a1[i];
}
int ans1 = isValidBST(bt1);
if (ans1 == true) {
printf("T1 is a binary search tree\n");
} else {
printf("T1 is not a binary search tree\n");
}
int a2[11] = {40, 50, 60, -1, 30, -1, -1, -1, -1, -1, 35};
SqBiTree bt2;
memset(bt2.SqBiTNode, 0, sizeof(bt2.SqBiTNode));
bt2.ElemNum = 11;
for (int i = 0; i < bt2.ElemNum; ++i) {
bt2.SqBiTNode[i] = a2[i];
}
int ans2 = isValidBST(bt2);
if (ans2 == true) {
printf("T2 is a binary search tree\n");
} else {
printf("T2 is not a binary search tree\n");
}
return 0;
}
复杂度分析
- 时间复杂度： O(n) ，其中 n 为二叉树的结点个数。二叉树的每个结点最多被访问三次，因此时间复杂度为 O(n) 。
- 空间复杂度： O(1) ，中间过程额外需要常数个变量。
解答：
K-SMALLEST-ELEMENTS(A, n, k)
for i = 1 to k
min_id = i
for j = i to n
if A[j] < A[min_id]
min_id = j;
exchange A[min_id] with A[i]
return A[1 : k]
// Call function
K-SMALLEST-ELEMENTS(A, n, 10)
复杂度分析：
- 时间复杂度： O(n) ，需要遍历 10 次数组。
- 空间复杂度： O(1) ，中间过程额外需要常数个变量。
如果这里将 10 修改为 k ，则：
- 时间复杂度： O(nk) ，需要遍历 k 次数组。
- 空间复杂度： O(1) ，中间过程额外需要常数个变量。
评分：5分，虽然当 k 为常数时时间复杂度和空间复杂度表面上均为最优，实际上时间复杂度不是最优，但是可以进行大幅优化。
当然这里可以进行优化，每次记录两个变量，找出最小值和次小值，这样只需要遍历 k/2 次数组。
- 时间复杂度： O(nk) ，需要遍历 k 次数组。
- 空间复杂度： O(1) ，中间过程额外需要常数个变量。
评分：6分，虽然当 k 为常数时时间复杂度和空间复杂度表面上均为最优，实际上时间复杂度不是最优，但是可以进行大幅优化。
进一步优化，直接记录 k 个变量，或者一个长度为 k 的辅助数组，使用插入排序或者冒泡排序的方法，找出最小的 k 个数，这样只需要遍历 1 次数组。
- 时间复杂度： O(nk) ，需要遍历 k 次数组。
- 空间复杂度： O(n) ，中间过程额外需要大小为 k 的辅助数组。
评分：6分，虽然当 k 为常数时时间复杂度和空间复杂度表面上均为最优，实际上时间复杂度和空间复杂度都不是最优，都可以进行大幅优化。
以上这些优化手段都无法降低时间复杂度。
伪代码如下：
MAX-HEAPIFY(A, i, n)
l = LEFT(i)
r = RIGHT(i)
if l ≤ n and A[l] > A[i]
largest = l
else largest = i
if r ≤ n and A[r] > A[largest]
largest = r
if largest ≠ i
exchange A[i] with A[largest]
MAX-HEAPIFY(A, largest)
BUILD-MAX-HEAP(A, n)
for i = ⌊n / 2⌋ down to 1 // 也可用floor函数表示向下取整
MAX-HEAPIFY(A, i, n)
K-SMALLEST-ELEMENTS(A, n, k)
BUILD-MAX-HEAP(A, k)
for i = k + 1 to n
if A[i] < A[1]
A[1] = A[i]
MAX-HEAPIFY(A, 1, k)
return A[1 : 10]
// Call function
K-SMALLEST-ELEMENTS(A, n, 10)
复杂度分析：
- 时间复杂度： O(n) ，由于堆大小为常量，所以建堆，维护堆的代价为 O(1) ，仅需要遍历一遍数组，该算法时间复杂度为 O(n) 。
- 空间复杂度： O(1) ，该算法原地建堆，使用了常数个辅助变量，该算法的空间复杂度为 O(1) 。
如果这里将 10 修改为 k ，则：
- 时间复杂度： O(nlogk) ，所以建堆的代价为 O(k) ，每次维护堆的代价为 O(logk) ，仅需要遍历一遍数组，总共 n 个元素，该算法时间复杂度为 O(nlogk) 。
- 空间复杂度： O(1) ，该算法原地建堆，使用了常数个辅助变量，该算法的空间复杂度为 O(1) 。
评分：9分，虽然当 k 为常数时时间复杂度为最优，实际上时间复杂度不是最优，可以继续进行优化。
当然，这里也可以使用优先队列，本质思想是一致的。
如果使用二叉堆作为优先队列，为插入建堆，明显不如直接用堆好。
- 时间复杂度： O(nlogk) ，插入建堆的代价为 O(klogk) ，每次维护堆的代价为 O(logk) ，仅需要遍历一遍数组，总共 n 个元素，该算法时间复杂度为 O(nlogk) 。
- 空间复杂度： O(k) ，该算法用了大小为 k 的堆的辅助数组，该算法的空间复杂度为 O(k) 。
用二叉堆作为优先队列并不能对时间复杂度进行优化。
评分：8分，虽然当 k 为常数时时间复杂度和空间复杂度表面上均为最优，实际上时间复杂度和空间复杂度都不是最优，可以继续进行优化。
当然可以使用更高级的数据结构实现优先队列，比如用Emde Boas树实现，时间复杂度降为 O(nloglogk) ，但是仍然可以继续进行优化。
方法三：选择算法（快速排序思想）
题目已经给出重要提示：“平均情况下的比较次数尽可能少”，明显指向随机化选择算法。也是本题的最优解。
为什么给出这个结论呢？“平均情况下”意思是不需要考虑最坏情况，哪些算法最坏情况下的时间复杂度和平均情况下的时间复杂度有区别呢？我们很容易想到快速排序，那么快速排序是如何进行优化的呢？其中一个最常规的方法就是随机化，当然同理，如果学过《算法导论》的同学马上能联想到选择算法。还有一个条件就是“比较次数尽可能少”，这个什么意思呢？绝大部分排序算法都是基于比较的排序算法，其中性能最好的就是快速排序，这道题没有要求我们对所有数进行排序，所以没必要使用平均情况下时间复杂度为 O(nlogn) 的随机化快速排序算法，只需要使用平均情况下时间复杂度为 O(n) 的随机化选择算法算法。两者思路非常相近，都使用了随机化和划分数组技巧。
牢记：408题目中每一个条件都是有用的！
其实选择算法在2016年第43题已经进行过考察，也就是吃透真题非常重要，往年考过的知识点很有可能再考。
虽然RANDOMIZED-SELECT和RANDOMIZED-QUICKSORT代码非常相似，但这方法绝对不是能在没有学习过RANDOMIZED-SELECT算法的情况下在考场上随机应变能想出来的，如果你做到了，完全可以说是天才。408非常强调平时积累的。
递归版伪代码如下：
PARTITION(A, p, r)
x = A[r] // the pivot
i = p - 1
for j = p to r - 1
if A[j] ≤ x
i = i + 1
exchange A[i] with A[j]
exchange A[i + 1] with A[r]
return i + 1 // new index of pivot
RANDOMIZED-PARTITION(A, p, r)
i = RANDOM(p, r)
exchange A[i] with A[r]
return PARTITION(A, p, r)
RANDOMIZED-SELECT(A, p, r, i)
if p == r
return A[p] // 1 ≤ i ≤ r - p + 1 when p == r means that i = 1
q = RANDOMIZED-PARTITION(A, p, r)
k = q - p + 1
if i == k
return A[q] // the pivot value is the answer
else if i < k
return RANDOMIZED-SELECT(A, p, q - 1, i)
else return RANDOMIZED-SELECT(A, q + 1, r, i - k)
K-SMALLEST-ELEMENTS(A, n, k)
RANDOMIZED-SELECT(A, 1, n, k)
return A[1 : k]
// Call function
K-SMALLEST-ELEMENTS(A, n, 10)
复杂度分析：
- 时间复杂度： O(n) ，用RANDOMIZED-SELECT选出第 10 小的数，而且已经用这个数作为枢轴对数组进行划分，下标前 10 的元素即为最小的 10 个数，时间复杂度 O(n) 。
- 空间复杂度： O(logn) ，平均情况下递归栈深度为 O(logn) 。
迭代版伪代码如下：
PARTITION(A, p, r)
x = A[r] // the pivot
i = p - 1
for j = p to r - 1
if A[j] ≤ x
i = i + 1
exchange A[i] with A[j]
exchange A[i + 1] with A[r]
return i + 1 // new index of pivot
RANDOMIZED-PARTITION(A, p, r)
i = RANDOM(p, r)
exchange A[i] with A[r]
return PARTITION(A, p, r)
RANDOMIZED-SELECT(A, n, i)
p = 1
r = n
q = 0
k = 0
while TRUE
q = RANDOMIZED-PARTITION(A, p, r);
k = q - p + 1;
if i == k
return A[q] // the pivot value is the answer
elseif i < k
r = q - 1
else p = q + 1
i = i - k
K-SMALLEST-ELEMENTS(A, n, k)
RANDOMIZED-SELECT(A, n, k)
return A[1 : k]
// Call function
K-SMALLEST-ELEMENTS(A, n, 10)
复杂度分析：
- 时间复杂度： O(n) ，用RANDOMIZED-SELECT选出第 10 小的数，而且已经用这个数作为枢轴对数组进行划分，下标前 10 的元素即为最小的 10 个数，时间复杂度 O(n) 。
- 空间复杂度： O(1) ，由于RANDOMIZED-SELECT和PARTITION都是原地算法，该算法的空间复杂度为 O(1) 。
如果这里将 10 修改为 k ，则：
- 时间复杂度： O(n) ，用RANDOMIZED-SELECT选出第 k 小的数，而且已经用这个数作为枢轴对数组进行划分，下标前 k 的元素即为最小的 k 个数，时间复杂度 O(n) 。
- 空间复杂度： O(1) ，由于RANDOMIZED-SELECT和PARTITION都是原地算法，该算法的空间复杂度为 O(1) 。
可以发现，此算法时间复杂度和空间复杂度不受参数 k 影响，性能非常优秀。
评分：10分，时间复杂度和空间复杂度均为最优。
总结
本题本质就是Top-K问题，对排序算法思想进行了深入考察，Top-K问题非常经典，并不要求最终数组完全有序，只需要部分有序或者部分相对有序，所以充分利用排序算法的性质就能实现。
解答：
本题提到了EL路径，即欧拉路径。EL正是大名鼎鼎的欧拉(Euler)的缩写。
欧拉路径(Euler path)：如果图G中的一个路径包括每个边恰好一次，则该路径称为欧拉路径。
欧拉路径问题简称“一笔画”问题，这个问题我们小学二年级就应该学过，我还记得当时有个著名的七桥问题。
题目中给的是无向图，那么如何判断一个无向图能不能一笔画呢？有下面定理：
无向图存在欧拉路径的充要条件：度为奇数的点的数量为0个或2个。
当然，你完全可以不知道这些，因为题目条件已经毫无保留的告诉你了：“当G中度为奇数的顶点个数为不大于2的偶数时”。不就是无向图存在欧拉路径的充要条件吗？
⑴ 这样思路就有了：
- 第一步：统计所有点的度。
- 第二步：统计所有点中度为奇数的点的个数。
- 第三步：检查度为奇数的点个数是否为0或者2。
这道题称为408史上最简单算法题毫不过分，只因为第一次考图就离谱的送分，一送还送15分，但我估计要送就送这么一次，以后的考生就没这么好运了。
同学们可以用下面几张图玩一下一笔画。
⑵ 根据上述思路，C代码如下（含测试用例）：
#include <stdio.h>
#include <string.h>
#define MAXV 11
typedef struct { // 图的定义
int numVertices, numEdges; // 图中实际的顶点数和边数
char VerticesList[MAXV]; // 顶点表，MAXV为已定义常量
int Edge[MAXV][MAXV]; // 邻接矩阵
}MGraph;
int IsExistEL(MGraph G) {
int degrees[G.numVertices];
memset(degrees, 0, sizeof(degrees));
// 遍历无向图统计所有点的度
for (int i = 0; i < G.numVertices; i++) {
for (int j = 0; j < G.numVertices; j++) {
degrees[i] += G.Edge[i][j];
}
}
int count = 0;
// 遍历degrees数组统计度为奇数的点的个数
for (int i = 0; i < G.numVertices; i++) {
if (degrees[i] % 2 != 0) {
count++;
}
}
// 检查度为奇数的点个数是否为0或者2
if (count == 0 || count == 2) {
return 1; // 存在EL路径
} else {
return 0; // 不存在EL路径
}
}
int main() {
// 以图(a)为例
MGraph G;
G.numEdges = 6;
G.numVertices = 5;
memset(G.VerticesList, 0, sizeof(G.numVertices));
char V[5] = {'a', 'b', 'c', 'd', 'e'};
for (int i = 0; i < G.numVertices; i++) {
G.VerticesList[i] = V[i];
}
memset(G.Edge, 0, sizeof(G.numVertices));
int M[5][5] = {{0, 1, 0, 0, 1}, {1, 0, 1, 1, 0}, {0, 1, 0, 1, 0}, {0, 1, 1, 0, 1}, {1, 0, 0, 1, 0}};
for (int i = 0; i < G.numVertices; i++) {
for (int j = 0; j < G.numVertices; j++) {
G.Edge[i][j] = M[i][j];
}
}
if (IsExistEL(G)) {
printf("There is a Euler path. ");
} else {
printf("There is no Euler path. ");
}
return 0;
}
复杂度分析
- 时间复杂度： O(n^2) ，其中 n 为图中点个数。因为需要遍历整个邻接矩阵，所以为 O(n^2) 。
- 空间复杂度： O(n) ，开辟了 O(n) 大小的辅助数组。
如果到这里就结束了，这道题也太简单了吧，明显需要进行优化。时间复杂度无法优化，我们考虑优化空间复杂度，去掉辅助数组，边遍历边统计。修改后C代码如下（含测试用例）：
#include <stdio.h>
#include <string.h>
#define MAXV 11
typedef struct { // 图的定义
int numVertices, numEdges; // 图中实际的顶点数和边数
char VerticesList[MAXV]; // 顶点表，MAXV为已定义常量
int Edge[MAXV][MAXV]; // 邻接矩阵
}MGraph;
int IsExistEL(MGraph G) {
int degree = 0;
int count = 0;
// 遍历无向图统计所有点的度
for (int i = 0; i < G.numVertices; i++) {
degree = 0; // 重置
// 计算点i的度
for (int j = 0; j < G.numVertices; j++) {
degree += G.Edge[i][j];
}
// 检查点i的度是否为奇数
if (degree % 2 != 0) {
count++;
}
}
// 检查度为奇数的点个数是否为0或者2
if (count == 0 || count == 2) {
return 1; // 存在EL路径
} else {
return 0; // 不存在EL路径
}
}
int main() {
// 以图(a)为例
MGraph G;
G.numEdges = 6;
G.numVertices = 5;
memset(G.VerticesList, 0, sizeof(G.numVertices));
char V[5] = {'a', 'b', 'c', 'd', 'e'};
for (int i = 0; i < G.numVertices; i++) {
G.VerticesList[i] = V[i];
}
memset(G.Edge, 0, sizeof(G.numVertices));
int M[5][5] = {{0, 1, 0, 0, 1}, {1, 0, 1, 1, 0}, {0, 1, 0, 1, 0}, {0, 1, 1, 0, 1}, {1, 0, 0, 1, 0}};
for (int i = 0; i < G.numVertices; i++) {
for (int j = 0; j < G.numVertices; j++) {
G.Edge[i][j] = M[i][j];
}
}
if (IsExistEL(G)) {
printf("There is a Euler path. ");
} else {
printf("There is no Euler path. ");
}
return 0;
}
复杂度分析
- 时间复杂度： O(n^2) ，其中 n 为图中点个数。因为需要遍历整个邻接矩阵，所以为 O(n^2) 。
- 空间复杂度： O(1) ，使用了常数个临时变量。
解答：
⑴ 为了区分两个25不同，将后一个25标粗，int a[] = {25, -10, 25, 10, 11, 19}。这道题的思想不复杂，采用了计数排序思想，简单描述就是要count数组用于计算数组中有几个元素小于当前元素，比这个元素小的元素越多，这个元素权重越大，这个元素最终也越靠后，然后就能以此为依据进行排序。我们很容易计算出count[] = {5, 0, 4, 1, 2, 3}，可得：
b = {-10, 10, 11, 19, 25, 25}。
⑵ 由for循环代码可知，每个元素需要和它后面的元素都比较一次，得到 (n−1)+(n−2)+⋯+1=n(n−1)/2 。
⑶ 很显然，这个算法不稳定，观察代码：
if (a[i] < a[j]) count[j]++;
else count[i]++;
本质就是：
if (a[i] < a[j]) count[j]++;
else if (a[i] >= a[j]) count[i]++;
调整前后相同元素的权重，给后面的元素权重大一点，移动下等于情况就行，即：
if (a[i] <= a[j]) count[j]++;
else if (a[i] > a[j]) count[i]++;
简化为：
if (a[i] <= a[j]) count[j]++;
else count[i]++;
所以只需要修改第6行代码为：
if (a[i] <= a[j]) count[j]++;
这样就能解决问题。
tips：这种题如果上来没看出门道，按照代码执行顺序模拟一遍就能看出题目想表达的意思了，考场上要做到沉着冷静。
解答：
方法一：暴力法
用i、j、k三个指针分别表示当前指向数组集合 S1 、 S2 和 S3 中的位置，枚举所有的三元组，取所有三元组中的最小距离。
C代码如下（含测试用例）：
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
int findMinDist(int s1[], int s2[], int s3[], int n1, int n2, int n3) {
int min_dist = INT_MAX;
int dist;
for (int i = 0; i < n1; i++) {
for (int j = 0; j < n2; j++) {
for (int k = 0; k < n3; k++) {
dist = abs(s1[i] - s2[j]) + abs(s2[j] - s3[k]) + abs(s3[k] - s1[i]);
if (dist < min_dist) {
min_dist = dist;
}
}
}
}
return min_dist;
}
int main(int argc, const char * argv[]) {
int s1[3] = {-1, 0, 9};
int s2[4] = {-25, -10, 10, 11};
int s3[5] = {2, 9, 17, 30, 41};
int ans = findMinDist(s1, s2, s3, 3, 4, 5);
printf("%d\n", ans);
return 0;
}
复杂度分析
- 时间复杂度： O(n1n2n3) ，其中 n1、n2 和 n3 分别为S1、S2和S3的长度。
- 空间复杂度： O(1) ，中间过程额外需要常数个变量。
如果用暴力法应该能拿到一半多一点的分，也就是本题13分能拿到7-8分。
方法二：同向多指针（滑动窗口变体）
这道题难度非常大，称为408史上第二难算法题毫不过分，本题需要用到多指针或指针数组。
使用i、j、k三个指针分别指向三个数组的首个元素，每次移动三个指针中指向元素最小的指针（三个指针可能交替移动），移动后检查有没有产生更短的距离。这里为同向三指针，将所有元素放到一个数轴上，求最左和最右指针的最小距离，可以理解为广义的求滑动窗口最小值。
C代码如下（含测试用例）：
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
int findMinDist(int s1[], int s2[], int s3[], int n1, int n2, int n3) {
int min_dist = INT_MAX;
int dist;
int i = 0, j = 0, k = 0;
while (i < n1 && j < n2 && k < n3) {
dist = abs(s1[i] - s2[j]) + abs(s2[j] - s3[k]) + abs(s3[k] - s1[i]);
if (dist < min_dist) {
min_dist = dist;
}
if (s1[i] < s2[j]) {
if (s1[i] < s3[k]) { // s1[i]
i++;
} else { // s3[k]
k++;
}
} else {
if (s2[j] < s3[k]) { // s2[j]
j++;
} else { // s3[k]
k++;
}
}
}
return min_dist;
}
int main(int argc, const char * argv[]) {
int s1[3] = {-1, 0, 9};
int s2[4] = {-25, -10, 10, 11};
int s3[5] = {2, 9, 17, 30, 41};
int ans = findMinDist(s1, s2, s3, 3, 4, 5);
printf("%d\n", ans);
return 0;
}
复杂度分析
- 时间复杂度： O(n1+n2+n3) ，其中 n1、n2 和 n3 分别为S1、S2和S3的长度。
- 空间复杂度： O(1) ，中间过程额外需要常数个变量。
解答：
⑴ 题目要求：“若任一个字符的编码都不是其它字符编码的前缀，则称这种编码具有前缀特性。”
看到这里马上联想到前缀无关编码和哈夫曼树，或者前缀无关编码对应的二叉树。哈夫曼树是某一最优前缀无关编码对应的二叉树。
注：《数据结构（C语言版）》和《算法导论》第三版中称为前缀编码(prefix codes)，《算法导论》第四版和《计算理论导论》第三版中都已经改成前缀无关编码(prefix-free codes)，个人认为称为前缀无关编码更加准确，充分表达出定义中“不是”的含义。
这里可以构造一棵度为2的哈夫曼树，字符保存在叶结点中，左指针路径上标0，右指针路径上标1，从根结点到叶结点路径上的0或1组成的串即为该字符的前缀无关编码。
字符保存在叶结点中，左指针路径上标0，右指针路径上标1，从根结点到叶结点路径上的0或1组成的串即为该字符的前缀无关编码。
⑵ 按序遍历0/1串，对应从哈夫曼树中找一条从根结点开始的路径，到叶结点终止，输出叶结点对应的字符。然后重新从根结点开始重复这个过程。
⑶ 构造二叉树，由于任意一个字符编码不是另一个字符编码的前缀，字符信息只能存在叶结点中。如果构造成功，那么某字符集的不等长编码具有前缀特性。
本题选B。
方法二：画图举例
如果记不得哈夫曼树和二叉树的性质怎么办？还是画图和举例，直接构造一棵哈夫曼树。
构造的哈夫曼树越简单越好。
很明显，新构造出的结点有 n−1 个， n+n−1=115 ，解得 n=58 。
本题选C。
解答：
方法一：推理
AVL树首先是二叉搜索树，遵循二叉搜索树的性质。
如果从 T1 中删除一个结点 z ，不考虑平衡调整。
从二叉搜索树 T1 中删除结点 z 分三种情况：
- 情况一：如果 z 没有孩子结点，直接删除， z 的父结点指向 z 的指针置为NIL。如图(a)所示。
- 情况二：如果 z 只有一个孩子结点，将这个孩子结点提升到 z 的位置，z 的父结点指向 z 的指针改为指向这个孩子结点。如图(b)所示。
- 情况三：如果 z 有两个孩子结点，找出 z 的后继 y ，让 y 占据 z 的位置， z 的右子树变为 y 的右子树，z 的左子树变为 y 的左子树。由于 y 是 z 的后继，所以 y 不可能有左孩子。
- 如果 y 是 z 的右孩子，用 y 替换 z 。
- 如果 y 在 z 的右子树中且 y 不是 z 的右孩子，先用 y 的右孩子结点替换 y ，然后用 y 替换 z 。
下面具体分情况讨论。
- 情况一：如果 z 没有孩子结点，直接删除。再插入 z 后， T1 与 T3 可能相同也可能不相同。
- 如果删除 z 后仍为AVL树，不需要进行旋转调整，再插入 z 后， z 还在原来位置，此时 T3 与 T1 相同。
- 如果删除 z 后仍为AVL树不平衡，需要进行旋转调整，此时AVL树结构发生变化，子树根结点发生变化，重新插入 z 的路径发生变化，插入后 z 所在子树不需要进行旋转调整，推理过程如下：删除 z 前最下面叶结点的深度为 2 ， z 的深度为 1 ， z 的父结点深度为 0 ，删除 z 后进行调整， z 的父结点和另一侧叶结点深度相同均为 1 ，再插入 z ，此时 z 的深度为 2 ，原先最下面叶结点深度为 1 ，符合AVL树性质，不需要进行旋转调整。此时 T3 与 T1 不相同。
- 情况二：如果 z 只有一个孩子结点，将这个孩子结点提升到 z 的位置，z 的父结点指向 z 的指针改为指向这个孩子结点。
- 如果删除 z 后仍为AVL树且左右高度差为 0 ，不需要进行旋转调整，再重新插入 z 后， z 变为叶结点。T1 与 T3 一定不相同。
- 如果删除 z 后仍为AVL树且左右高度差为 1 且 z 的父结点位于较高的一侧，再重新插入 z 后，仍为AVL树，不需要进行旋转调整， z 变为叶结点。T1 与 T3 一定不相同。
- 如果删除 z 后仍为AVL树且左右高度差为 1 且 z 的父结点位于较低的一侧，再重新插入 z 后，AVL树不平衡，需要进行旋转调整，调整后 T1 与 T3 可能相同。
分析到情况二结果已经出来了，且情况三更加复杂，不需要进行继续分析。I正确，II错误，III错误。
本题选A。
方法二：画图举例
可以发现，严格按照性质分析结果过于复杂，还是画图举例：
I正确，II错误，III错误。
本题选A。
方法三：断言
下面提供秒题解法：
看到绝对词排除，II、III都有一定，太绝对，错误。
为什么敢玩的这么大胆，因为这里涉及AVL树的插入删除，其中包含二叉搜索树的插入和删除以及AVL树的旋转，情况非常复杂多变，过于绝对的选项大概率能够举出反例。
I正确，II错误，III错误。
本题选A。
解答：
注意：题目中单链表带头结点，头结点不存储关键字。
思路一：开辟一个长度为 n 的辅助数组，将所有结点存入，然后直接操作数组下标，重新构建链表。该算法空间复杂度为 O(n) ，但是这里题目已经明确要求设计一个空间复杂度为 O(1) 的算法，所以不能使用。
所以本题只能使用一个原地算法。目前主流的解法如下：
寻找链表中点 + 反转链表 + 合并链表
目标链表即为将原链表的左半端和反转后的右半端合并后的结果。这样可以分为三步。
第一步：找到原链表的中点，本题为下中位数点 
，即第 
个结点，为什么是找下中位数点，这道题将链表分成两段，左半段为 
，右半段为 
，这样能够满足当 n 为偶数时，左半段结点个数和右半段结点个数相等，当 n 为奇数时，左半段结点个数比右半段结点个数多 1。为什么要求当 n 为奇数时左半段结点个数比右半段结点个数多 1，因为第一个元素 a1 是左半段元素，这样交替后最后一个元素一定是左半段的元素，恰巧比右半段多出一个。
使用快慢指针可以方便找出链表中位于中位数位置的结点，该步时间复杂度 O(n) 。
第二步：将原链表的右半段反转。
反转链表有三种方法，递归法，迭代法，头插法。这三种方法中，迭代法是最优解。
这里使用迭代法实现链表的反转，该步时间复杂度 O(n) 。
第三步：将两条链表合并。
因为两链表长度相差不超过一，交叉合并，该步时间复杂度 O(n) 。
综上，该算法的时间复杂度为 O(n)+O(n)+O(n)=O(n) 。
C代码如下（含测试用例）：
#include <stdio.h>
#include <stdlib.h>
typedef struct node {
int data;
struct node *next;
} NODE;
void reorderList(NODE* h) {
NODE *p, *q, *r, *s;
// 第一步：寻找h中间结点
p = q = h;
while (q->next != NULL) {
p = p->next;
q = q->next;
if (q->next != NULL) {
q = q->next;
}
}
q = p->next;
p->next = NULL;
// 第二步：将链表后半段反转
while (q != NULL) {
r = q->next;
q->next = p->next;
p->next = q;
q = r;
}
// 第三步：合并链表
s = h->next;
q = p->next;
p->next = NULL;
while (q != NULL) {
r = q->next;
q->next = s->next;
s->next = q;
s = q->next;
q = r;
}
}
NODE* createLinkedList(int *a, int n) {
NODE* head = (NODE *)malloc(sizeof(struct node));
NODE* tail = head;
for (int i = 0; i < n; i++) {
NODE* p = (NODE *)malloc(sizeof(struct node));
p->data = a[i];
p->next = NULL;
tail->next = p;
tail = tail->next;
}
return head;
}
int main() {
int a[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
NODE* head = createLinkedList(a, 9);
reorderList(head);
NODE* curr = head;
printf("head");
while (curr != NULL) {
printf("->%d", curr->data);
curr = curr->next;
}
return 0;
}
说实话，标准答案的指针利用率非常高，缺点也很明显，可读性很差。
这道题实际上是三个基础算法的组合，本人把三段代码拆分三个方法。
C代码如下（含测试用例）：
#include <stdio.h>
#include <stdlib.h>
typedef struct node {
int data;
struct node *next;
} NODE;
NODE* middleNode(NODE* head) {
NODE* slow = head;
NODE* fast = head;
while (fast->next != NULL && fast->next->next != NULL) {
slow = slow->next;
fast = fast->next->next;
}
return slow;
}
NODE* reverseList(NODE* head) {
NODE* prev = NULL;
NODE* curr = head;
while (curr != NULL) {
NODE* nextTemp = curr->next;
curr->next = prev;
prev = curr;
curr = nextTemp;
}
return prev;
}
void mergeList(NODE* l1, NODE* l2) {
NODE* l1_tmp;
NODE* l2_tmp;
while (l1 != NULL && l2 != NULL) {
l1_tmp = l1->next;
l2_tmp = l2->next;
l1->next = l2;
l1 = l1_tmp;
l2->next = l1;
l2 = l2_tmp;
}
}
void reorderList(NODE* head) {
if (head == NULL || head->next == NULL) {
return;
}
NODE* mid = middleNode(head->next);
NODE* l1 = head->next;
NODE* l2 = mid->next;
mid->next = NULL;
l2 = reverseList(l2);
mergeList(l1, l2);
}
NODE* createLinkedList(int *a, int n) {
NODE* head = (NODE *)malloc(sizeof(struct node));
NODE* tail = head;
for (int i = 0; i < n; i++) {
NODE* p = (NODE *)malloc(sizeof(struct node));
p->data = a[i];
p->next = NULL;
tail->next = p;
tail = tail->next;
}
return head;
}
int main() {
int a[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
NODE* head = createLinkedList(a, 9);
reorderList(head);
NODE* curr = head;
printf("head");
while (curr != NULL) {
printf("->%d", curr->data);
curr = curr->next;
}
return 0;
}
C++代码如下（含测试用例）：
#include <iostream>
using namespace std;
typedef struct node {
int data;
struct node *next;
} NODE;
NODE* middleNode(NODE* head) {
NODE* slow = head;
NODE* fast = head;
while (fast->next != nullptr && fast->next->next != nullptr) {
slow = slow->next;
fast = fast->next->next;
}
return slow;
}
NODE* reverseList(NODE* head) {
NODE* prev = nullptr;
NODE* curr = head;
while (curr != nullptr) {
NODE* nextTemp = curr->next;
curr->next = prev;
prev = curr;
curr = nextTemp;
}
return prev;
}
void mergeList(NODE* l1, NODE* l2) {
NODE* l1_tmp;
NODE* l2_tmp;
while (l1 != nullptr && l2 != nullptr) {
l1_tmp = l1->next;
l2_tmp = l2->next;
l1->next = l2;
l1 = l1_tmp;
l2->next = l1;
l2 = l2_tmp;
}
}
void reorderList(NODE* head) {
if (head == nullptr || head->next == nullptr) {
return;
}
NODE* mid = middleNode(head->next);
NODE* l1 = head->next;
NODE* l2 = mid->next;
mid->next = nullptr;
l2 = reverseList(l2);
mergeList(l1, l2);
}
NODE* createLinkedList(int *a, int n) {
NODE* head = new NODE();
NODE* tail = head;
for (int i = 0; i < n; i++) {
NODE* p = new NODE();
p->data = a[i];
p->next = nullptr;
tail->next = p;
tail = tail->next;
}
return head;
}
int main() {
int a[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
NODE* head = createLinkedList(a, 9);
reorderList(head);
NODE* curr = head;
cout << "head";
while (curr != nullptr) {
cout << "->"<< curr->data;
curr = curr->next;
}
return 0;
}
复杂度分析
- 时间复杂度： O(n) 。
- 空间复杂度： O(1) 。
解答：
⑴ 该队列应选择链式存储结构。由于入队时，允许增加队列占用空间，出队后，整个队列所占用的空间只增不减，链式存储方便开辟新的空间。出队元素所占用的空间可重复使用，所以构造成循环链表。只需要维护队头指针和队尾指针，同时每个结点维护属性 key记录该结点的关键字，就能保证入队操作和出队操作的时间复杂度始终保持为 O(1) 。
方法一： Q.front 指向结点存储队列中的关键字。
⑵ 设队列 Q 头指针为 Q.front ，队尾指针为 Q.rear 。
初始状态： Q.front 和 Q.rear 均指向一个空结点。如图(a)所示。
判断队空 IS-EMPTY 伪代码如下：
IS-EMPTY(Q)
if Q.front == Q.rear
return TRUE
else return FALSE
判断队满 IS-FULL 伪代码如下：
IS-FULL(Q)
if Q.front == Q.rear->next
return TRUE
else return FALSE
⑶ 第一个元素 1 入队后：如图(b)所示。
⑷ 入队操作和出队操作的基本过程：
入队操作 ENQUEUE 伪代码如下：
ENQUEUE(Q, x)
Q.rear.key = x // 加入x
if IS-FULL(Q) == TRUE // 如果队满，需要增加新空结点
create a new node p
Q.rear->next = p
p->next = Q.front
Q.rear = Q.rear->next
第二个元素 2 入队后：如图(c)所示。
出队操作 DEQUEUE 伪代码如下：
DEQUEUE(Q)
if IS-EMPTY(Q) == TRUE
error "queue is empty" // 如果队空，报错
else
p = Q.front
Q.front = Q.front->next;
return p.key;
队头元素 1 出队后：如图(d)所示。
方法二： Q.rear 指向结点存储队列中的关键字。
⑵ 设队列 Q 头指针为 Q.front ，队尾指针为 Q.rear 。
初始状态： Q.front 和 Q.rear 均指向一个空结点。如图(a)所示。
判断队空 IS-EMPTY 伪代码如下：
IS-EMPTY(Q)
if Q.front == Q.rear
return TRUE
else return FALSE
判断队满 IS-FULL 伪代码如下：
IS-FULL(Q)
if Q.front == Q.rear->next
return TRUE
else return FALSE
⑶ 第一个元素 1 入队后：如图(b)所示。
⑷ 入队操作和出队操作的基本过程：
入队操作 ENQUEUE 伪代码如下：
ENQUEUE(Q, x)
if IS-FULL(Q) == TRUE // 如果队满，需要增加新空结点
create a new node p
Q.rear->next = p
p->next = Q.front
Q.rear = Q.rear->next
Q.rear.key = x // 加入x
第二个元素 2 入队后：如图(c)所示。
出队操作 DEQUEUE 伪代码如下：
DEQUEUE(Q)
if IS-EMPTY(Q) == TRUE
error "queue is empty" // 如果队空，报错
else
Q.front = Q.front->next;
return Q.front.key;
队头元素 1 出队后：如图(d)所示。
答案解析
（1）
对于关键字20，我们计算(20*3)%11=60%11=5。所以，20的散列地址是5.
对于关键字3，我们计算(3*3)%11=9%11=9。所以，3的散列地址是9,
对于关键字11，我们计京(11*3)%11=33%11=0。所以。11的教列地址是0。
对于关键字18，我们计算(18*3)%11=54%11=10。所以，18的散列地址是10.
对于关键字9，我们计算(9*3)%11=27%11=5。但是，地址5己经被关键字20占用了，所以我们需要使用二次探查来找到一个新的地址。我们计算(5+1^2) % 11=6%11=6。所以，9的散列地址是6。
对于关键字14，我们计算(14*3)%11=42%11=9。但是，地址9已经被关键字3占用了，所以我们需要使用二次探查来找到一个新的地址。我们计算(9+1*2)%11=10%11=10。但是地址10也被18占用了，再次使用二次探查来找到一个新的地址。我们计算(9+2^2)%11=13%11=2。所以，14的散列地址是2.
对于关键字7，我们计算(7*3)%11=21%11=10。但是，地址10已经被关键字18占用了，所以我们需要使用二次探查来找到一个新的地址，我们计算(10+1^2) %11=11%11=0。但是，地址0已经被关键字1占用了，所以我们需要继续使用二次探查。我们计算(10+2^2)%11=14%11=3。所以，7的散列地址是3。
散列地址 0 1 2 3 4 5 6 7 8 9 10
关健字 11 14 7 20 9 3 18
冲突次数 1 3 2 l 2 l 1
最后，我们汁算散列表的填装因子，即散列表中已经被填充的位置的数量除以散列表的总长度。在这个例子中，填装因子是了7/11。
（2）
1、首先，我们计算14的散列地址：H(14)-(14*3)%11=42%11= 9.
2、我们查看散列表中索引为9的位置，发现那里存储的是关键字3，而不是14，这意味着我们遇到了冲突。
3、由于我们使用的是二次探查，所以我们计算下一个散列地址：H1=(H0+1^2)%11=(9+1)%11=10。发现那里存储的是关键字18，而不是14，这意味着我们遇到了冲突。
4、所以我们计算下一个散列地址：H1=(H0+2*2)%11=(9＋4)%11=2。发现那里存储的正是我们要找的关键字14。
（3）
1、首先。我们计算8的散列地址：H(8) =(8*3)%11=24%11=2,
2、我们查看散列表中索引为2的位置。发现那里存储的是关键字18，而不是8，这意味着我们遇到了冲突。
3、由于我们使用的是二次探查，所以我们计算下一个散列地址：H1=(H0+1^2)%11=(2+1)%11=3.
4、我们查看散列表中索引为3的位置。发现那里存储的是关键字7，而不是8，这意味着我们又遇到了冲突。
5、我们继续使用二次探查,计算下一个散列地址：H2=(H0+2^2)%11=(2+4)%11=6
6、我们查看散列表中索引为6的位置，发现那里存储的是关键字9而不是8，这意味着我们又遇到了冲突。
7、我们继续使用二次探查，计算下一个散列地址：H3=(H0+3^2)%11=(2+9)%11=0,
8、我们查看最列表中索引为0的位置，发现那里寡储的是关键字11，而不是8，这意味着我们又适到了冲突。
9、我们继续使用二次探查，计算下一个散列地址：H4=(H0 +4^2) %11=(2+16)%11=7.
10、我们查看散列表中索引为7的位置，发现那里是空的。所以我们可以确认查找失败，散列地址是7.
答案解析
（1）初始化：首先，我们需要一个数组来存储每个顶点的入度。我们遍历邻接矩阵，计算每个顶点的入度
初始一个计数器作为变量用于记录有多少个入度为0的节点
遍历每个节点：首先计算每个顶点的入度，然后在每次迭代中找在并移除入度为0的顶点。如果在任何时刻存在多个入度为0的顶点。那么就返回0。表示存在多个有效的拓扑序列。如果成功完成了拓扑排序，那么就返回1，表示存在唯一的拓扑序列。
（2）
int uniquely(MGraph G){
int inDegree[MAXV]={0};
// 计算每个顶点的入度
for(int =0; i<G.numVertices; i++) {
for(int j=0; j<G.numVertices; j++) {
if(G.Edge[i][j] != 0)
inDegree[i]++;
}
}
// 对每个顶点进行处理
for(int =0; i<G.numVertices; i++) {
int zeroInDegreeCount = 0; // 入度为0的顶点数量
int zeroInDegreeIndex = -1; // 入度为0的顶点索引
// 找到入度为0的顶点
for(int j=0; j<G.numVertices; j++) {
if(inDegree[j] == 0) {
zeroInDegreeCount++;
zeroInDegreeIndex = j;
}
}
// 如果存在多个入度为0的顶点，则返回0
if(zeroInDegreeCount > 1) {
return 0;
}
// 如果没有找到入度为0的顶点，则返回0
if(zeroInDegreeCount == 0) {
return 0;
}
// 将找到的入度为0的顶点从图中移除
inDegree[zeroInDegreeIndex] = -1;
for(int j=0; j<G.numVertices; j++) {
if(G.Edge[zeroInDegreeIndex][j] == 1) {
inDegree[j]--;
}
}
}
// 如果成功完成了拓扑排序，则返回1
return 1;
}
这段代码的功能是:把q指向的节点插入到h的后面。所以，选项D是正确的。
这段代码的解析如下:
1. q=p->next ; q指向p的下一个节点。
2. p->next=q->next ; p跳过q，直接指向q的下一个节点。
3. q->next = h->next; q的下一个节点设置为h 的下一个节点。
4. h->next = q; h的下一个节点设置为q。
所以，这段代码的功能是把q(原本是p的下一个节点〉移动到链表的第二个位置〈即h的下一个节点)。
答案是D选项:把q指向的节点插入到h的后面。这是因为执行代码后，q(原本是p的下一个节点)被移动到了链表的第二个位置(即h的下一个节点)。
将中缀表达式x+y*(z-u)/v转换为后缀表达式的过程如下:
1，扫描整个中缀表达式。
2．如果遇到操作数（这里是x, y，z，u, v)，则直接输出（添加到后缀表达式中)。
3，知果遇到运算符(这里是+，*，-，/)，则查看操作符栈顶的元素，如果栈顶运算符的优先级高于或等于当前运算符，则弹出栈顶运算符并输出，然后将当前运算符压入栈中。如果栈顶运算符的优先级低于当前运算符，或者栈为空，则直接将当前运算符压入栈中。
4，如果遇到左括号(这里是"(")，则直接压栈中。
5．如果遇到右括号（这里是")")，则依次弹出并输出栈顶的运算符，直到遇到左括号为止，然后弹出左括号（但不输出
6. 重复步骤2-5，直到中缀表达式的所有字符都被扫描完。
7．如果操作符栈中还有元素，则依次弹出并输出。
对于给定的表达式x+y*(z-u)/v，其等价的后缀表达式按照运算的优先级顺序(括号，乘法和除法，加法和减法）来确定，所以，我们首先得到z和u的差zu-，然后将其与y相乘得到yzu-*，然后除以v得到yzu-*v/，最后加上x 得到xyzu-*v/+
解法1
在二叉树的中序遍历中，节点的顺序是“左孩子-父节点-右孩子""。所以，对于给定的中序遍历...p，v，q...，我们可以得出以下结论:
p是v的左孩子，因为p在v之前。
q是v的右孩子，因为q在v之后。
因此,p没有右孩子，q没有左孩子。所以,在确答案是选项A: p没有右孩子，q没有左孩子。这是因为在中序遍历中，如果一个节点后面紧跟着另一个节点，那么第一个节点就没有右孩子，第二个节点就没有左孩子。所以，根据给定的中序遍历...p，v，q...、我们可以得出p没有右孩子，q没有左孩子。因此，选项A是正确的。
解法2。构造特殊的二叉树:
A. p没有右孩子，q没有左孩子逾历结果为p v q
B. p没有右孩子，q有左孩子，遍历结果为p v 1 q，所以错误
C. p有右孩子，q没有左孩子，追历结果为p 1 v q，所以错误
D. p有右孩子，q有左孩子，遍历结果为p 1 v 2 q，所以错误
答案解析
根据邻接多重表画出图为
所以顶点B、D的度为3,2
答案解析
折半查找(也称为二分查找)是一种在有序数组中查找特定元素的搜索算法。
查找过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束:如果某一部分确定不包含该元素，则不需要再对其进行搜索，直接在另一部分进行查找。
根据这个定义，我们可以看出以下几点
- 折半查找需要随机访问元素,因此它适用于数组和静态链表,但不适用于链表，因为链表不支持高效的随机访问
- 折半查找需要在有序的数据结构中进行，因此它不适用于无序的数组或链表。所以，不适合直接使用折半查找的是:
I，有序链表:因为链表不支持高效的随机访问。
II.无序数组:因为折半查找需要在有序的数据结构中进行。
III．有序静态链表、虽然静态链表支持随机访问，但是在实际应用中，静态链表的使用并不广泛,因此在大多数情况下,我们不会在静态链表上使用折学查找,
IV，无序静态值表:因为折半查找需要在有序的数据结构中进行。
因此，正确答案是D:I、II、III、IV.
快速排序算法的基本思想是。通过一趟排序将待排记录分割成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小.然后分别对这两部分继续进行排序，以达到整个序列有序的目标。
在这个问题中，我们在第一趟排序后，将数组M除枢轴外的N-1个元素划分为均不空的P和Q两块。对于这种情况,我们可以得出以下结论:
A、P与Q块间有序;这是正确的。在快速排序中，我们选择一个枢轴，然后将所有小于枢轴的元素放在枢轴的左边(即Р块)，将所有大于枢轴的元素放在枢轴的右边（即Q块）。因此。Р块中的所有元素都小于Q块中的所有元素，所以P与Q块间是有序的。
B、P与均块内有序:这是错误的。在快速排序的一趟排序过程中，我们只是根据是否小于或大于枢轴来划分元素,而并没有对Р块或Q块内的元素进行排序。因此，虽然Р块和Q块间有序，但Р块和Q块内部可能是无序的。
C、P和Q的元素个数大致相等:这是错误的。在快速排尽中，P块和Q块的元素个数取决于选取的枢轴。如果枢轴恰好是中位数，那么Р块和Q块的元素个数会大致相等。但如果枢轴偏离中位数。那么Р块和Q块的元素个数可能会有很大的不同.
D、Р和Q中均不存在相等的元素:这是错误的。在快速排序中，我们只是将元素划分为小于枢轴的部分和大于枢轴的部分。如果原数组中存在相等的元素，都么在划分后的Р块或Q块中仍然可能右在相等的元素。
方法一：构造
按照题目条件构造哈夫曼树。
每次取最小的两个子树的根结点合并。过程如下图所示：
左指针标0，右指针标1，从根结点到叶结点的路径即为该字符的哈夫曼编码。
本题选A。
方法二：代入选项
从选项构造哈夫曼树，检查是否符合哈夫曼编码性质。
选项B中a的编码是d的编码的前缀，错误。
选项C中a的编码是b的编码的前缀，错误。
选项D构造出的哈夫曼树不符合WPL最小规则，错误。
但其实这样做可能更加麻烦，需要画出4棵哈夫曼树依次进行检查。
检查后只有A符合要求。
本题选A。
二叉排序树中序遍历序列单调递增序列。
中序遍历有两种方法，本人分别命名为投影法和环线法。
有 x1<x3<x5<x4<x2 。
本题选C。
补充一下二叉树前序遍历、中序遍历、后序遍历递归版的特征：
- 前序遍历顺序为“根左右”，在第一次访问某结点时输出该结点的关键字。
- 中序遍历顺序为“左根右”，在第二次访问某结点时输出该结点的关键字。
- 后序遍历顺序为“左右根”，在第三次访问某结点时输出该结点的关键字。
函数的主体为while循环，sum +=++i 的时间复杂度为 O(1) ，所以函数运行时间与while循环迭代次数有关。
方法一：精确计算
本题选B。
方法二：渐近计算
本题选B。
解答：
方法一：直接分割序列
哈夫曼编码是前缀编码，各个编码的前缀各不相同，因此直接拿编码序列与哈夫曼编码一一比对即可。序列可分割为0100 011 001 001 011 11 0101，译码结果是 a f e e f g d，D正确。
本题选D。
方法二：构造出哈夫曼树分割序列
当然，也可以构造出哈夫曼树，每次从根结点走到叶结点，输出对应字符。
序列可分割为0100 011 001 001 011 11 0101，译码结果是 a f e e f g d，D正确。
本题选D。
本题为送分题，修改p的前驱结点的next指针指向p的后继结点，修改p的后继结点的prev指针指向p的前驱结点，最后释放p占用的内存。
本题选D。
队列为先进先出，这里要求出队顺序为1~9，相当于利用多个队列作为归并段，然后多路归并成一个有序数组，每个归并段单调递增。题目要求 n 最少，所以采用贪心策略，尽量少创建队列，我们很容易模拟出这个过程：
很明显，最后有4个队列（归并段）。
当然，这个答案不唯一，我是按照从上到下的方式选择入队队列，也可以按照别的顺序选择，但是必须要求每个队列队头到队尾升序排序。
最后一步归并排序也很简单，每次选择所有队列中最小的队头元素出队。
本题选C。
方法一：计算
每棵树的结点数比边数多一，设有 x 棵树，每棵树有 ni(1≤i≤x) 个结点，则有：
两式相减得： x=10 。
本题选C。
方法二：归纳法
下面提供秒题解法。
每棵树的结点数比边数多一，一棵树就相差1，两棵树就相差2， k 棵树就相差 k 。
25−15=10 。
本题选C。
Dijkstra算法使用贪心策略，每次选择距离起点最近的顶点进行继续搜索，并更新起点到各个顶点的距离。
根据Dijkstra算法，点集 S 初始为空，从顶点 1 到其余各顶点的最短路径如下表所示：
本题选B。
方法一：定义法
本题为多层循环，用定义法求解 ：
本题选C。
方法二：公式法
本题为多层循环中嵌套循环指针无关类型题。
外层循环时间复杂度为 O(logn) ，内层循环时间复杂度为 O(n) 。
由公式
可得总时间复杂度为 
。
本题选C。
方法一：模拟
本题考察中缀表达式转后缀表达式，需要利用栈作为辅助。
没有必要扫描完整个表达式，只需要扫描到 f 即可，过程模拟如下：
本题选B。
方法二：观察表达式
其实我们没有必要老老实实模拟整个流程，只需要观察中缀表达式即可， a/b+(c∗d−e∗f)/g 扫描到 f 时，此时 f 还没有被输出，观察前面与 f 相关的操作，也是没有能够输出的操作，这些操作都暂存在栈中，依次为 +(−∗ ，越靠近栈顶的优先级越高，显然在括号中 ∗ 比 − 的优先级高，栈顶的是 ∗ 。
本题选B。
循环队列中区分队空和队满，有三种处理方式：
① 牺牲一个单元来区分队空和队满，入队时少用一个队列单元，这是一个较为普遍的做法，约定以“队头指针在队尾指针的下一个位置作为队满的标志”。
队满条件：(Q.rear + 1) % MaxSize == Q.front
队空条件：Q.front == Q.rear
队列中元素的个数：(Q.rear - Q.front + MaxSize) % MaxSize
② 类型中增设表示元素个数的数据成员size：
队满条件：Q.size == MaxSize
队空条件：Q.size == 0
队列中元素的个数：Q.size
③ 类型中增设用于区分队满还是队空的数据成员tag，入队标记tag = 1，出队标记tag = 0：
队满条件：Q.front == Q.rear && tag == 1
队空条件：Q.front == Q.rear && tag == 0
队列中元素的个数：(Q.rear - Q.front + MaxSize) % MaxSize
以上三种方法本人简记为：
① 空一法（空格法）
② 计数法
③ 标记法（标志法）
A[0..M-1]数组的容量为M，队列中最多能容纳 M-1 个元素，很明显采用了空一法。
把变量名对着题目改一遍，很明显A选项符合条件。
本题选A。
中序线索化先进行中序遍历， x 左线索指向中序序列中 x 的前驱，x 右线索指向中序序列中 x 的后继。
中序遍历可以用投影法或者环线法。
得到中序遍历序列为d, e, b, x, a, c。
本题选D。
方法一：性质
将森林F转换为对应的二叉树T，即二叉树T用左孩子右兄弟法表示森林。森林F中的叶结点一定没有孩子结点，转化为二叉树T没有左孩子，所以F中叶子的个数等于T中左孩子指针为空的结点个数。
本题选C。
方法二：画图
如果仅仅利用性质分析觉得过于抽象，直接画图举例：
F中叶子的个数为5。
A选项，T中叶结点的个数为3，错误。
B选项，T中度为1的结点个数为2，错误。
C选项，T中左孩子指针为空的结点个数为5，正确。
D选项，T中右孩子指针为空的结点个数为3，错误。
本题选C。
方法一：观察选项
D选项中110是1100的前缀，不是前缀编码。
本题选D。
方法二：哈夫曼树
直接画出每种编码方案对应的哈夫曼树，遵循路径左0右1的规则。
最后检查所有编码必须存储在叶结点。
下图用黄色结点标记存储编码。
本题选D。
方法一：分段分析
这道题思维上有一定难度。
- 先分析 3 后面的元素，即 n=4,5,…,n ， p3=n 都是可以实现的，即该元素在进栈后立即出栈。
- 再分析 3 自身，一个元素不可能出栈两次，可以直接排除。
- 最后分析 3 前面的元素 1 和 2 。
- 若 p1=1 且 p2=3 ，出栈序列可以为 1,3,2,… 此时 p3=2 。
- 若 p1=2 且 p2=3 ，出栈序列可以为 2,3,1,… 此时 p3=1 。
综上，只有 3 自身被排除， p3 可能取值的个数共计 n−1 。
本题选C。
方法二：找规律
若 n=3 ，则出栈序列有5种，分别是 1,2,3 、 1,3,2 、 2,1,3 、 2,3,1 、 3,2,1 。当 p2=3 时，有2种情况，分别是1,3,2 和2,3,1 ，p3 可能取值的个数是2。
若 n=4 ，则出栈序列有14种，分别是
当 p2=3 时，有5种情况，分别是 4,3,2,1 、2,3,4,1 、 2,3,1,4 、 1,3,4,2 和1,3,2,4 ，p3 可能取值的个数是3。
综上，可以猜测若 p2=3 ，则 p3 可能取值的个数是 n−1 。
本题选C。
方法一：模拟
本题要求模拟平衡二叉树（AVL树）的插入过程。
将AVL树调整平衡的方法主要有旋转法和中序遍历法。
旋转法
观察插入不平衡结点的在所在子树上的路径：
- 先经过一个左指针，再经过一个左指针，对应LL平衡旋转。LL平衡旋转为右单旋转。
- 先经过一个右指针，再经过一个右指针，对应RR平衡旋转。RR平衡旋转为左单旋转。
- 先经过一个左指针，再经过一个右指针，对应LR平衡旋转。LR平衡旋转为先左后右双旋转。
- 先经过一个右指针，再经过一个左指针，对应RL平衡旋转。RL平衡旋转为先右后左双旋转。
由于关键字是从小到大插入，出现的都是RR平衡旋转。
中序遍历法
下面介绍中序遍历法，中序遍历法本质是利用AVL树的性质从结果出发直接找出调整后AVL树的根结点。
第一步：标记出插入不平衡结点从所在子树上的根结点到插入结点路径上的3个元素，标记3个元素为橙色，再标记3个橙色元素中间元素为红色，红色元素即为调整后子树的根结点，左边橙色元素为调整后子树左子树根结点，右边橙色元素为调整后子树右子树根结点。
第二步：写出子树的中序遍历序列，调整前后AVL树的中序遍历序列保持不变，将剩余结点加入到调整后的子树中。
此时，所有关键字都已经插入到AVL树中。
题目要求考察平衡因子为 0 的分支结点，所以我们只需要考察AVL树中所有的非叶结点，即结点 2、4 和 6 ，其左右子树高度相同，平衡因子为 0 ，所以平衡因子为 0 的分支结点总共有 3 个。
本题选D。
方法二：贪心
当然，模拟完整的AVL树插入过程非常麻烦，由于AVL树一定是平衡的，总共 7 个结点，我们很容易构造出一棵满二叉树，满二叉树的根结点和两个孩子结点为符合题目要求的结点，总共有 3 个结点。
题目要求考察平衡因子为 0 的分支结点，所以我们只需要考察AVL树中所有的非叶结点，其左右子树高度相同，平衡因子为 0 ，所以平衡因子为 0 的分支结点总共有 3 个。
本题选D。
后序线索二叉树的遍历序列即二叉树后序遍历序列，根据题意，很容易画出示意图：
X 的右线索指的是 X 的父结点。
本题选A。
二叉排序树又称二叉搜索树，本题考察二叉搜索树的性质。
方法一：性质
很明显，本题要求我们分两种情况讨论。
若 v 是 T1 的叶结点，为情况一，直接删除，再插入 v ， v 会复原到原来的位置，则 T1 与 T3 相同。
若 v 不是 T1 的叶结点，为情况二或情况三，再插入 v ， v 会变成叶结点，则 T1 与 T3 不同。
仅II、III正确。
本题选C。
方法二：断言
二叉搜索树的删除非常复杂，如果没有掌握也没有关系。
若 v 是 T1 的叶结点，插入 v ， v 还是叶结点，则 T1 与 T3 相同。
若 v 不是 T1 的叶结点，插入 v ， v 会变成叶结点，则 T1 与 T3 不同。
仅II、III正确。
虽然这样推导不严谨，但足够高效就行。
本题选C。
The road of your choice, you have to go on !
粤ICP备16082171号-1
