数据结构与算法第五套试卷小题

1.希尔排序

方法论： 增量为n，则分为n组

2.归并排序

注意题目，进行一趟归并排序后结果：->说明分为n个小块后，进行一次归并的结果

答案：
原序列共分成5段有序,第1段：25,50.第2段：15,35.第3段：80,85.第4段：20,40.第5段：36,70.第1段与第2段归并,结果为：15,25,35,50.第3段与第4段归并结果为：20,40,80,85.第5段落单了,则原样照抄.结果为A

3.字符串substr操作注意事项

首位比如5是T，但是需要多算前面那个字符（当作从1开始即可）

3.树

1.总结点数和边数的关系： n=e+1；
2.边数与指针数： e=指针数；
3.m叉树总指针数： N1+2*N2+…+mNm；
同时也等于N1+N2+…+Nm-1；
（关键：指针数边数顶点数-1）

4.树的DFS，BFS遍历：

5.共享栈

共享栈说明是环状的，所以栈满为：top1+1==top2

6.图

在图的邻接表中用顺序存储结构存储表头结点的优点是：可以随机访问到任意一个顶点的简单链表
邻接矩阵的行为图的出度；
邻接矩阵的列为图入度；

7.i,j到0，0的个数

中间有： i*(i+1)/2+j-1
**原因：*我们按行顺序存放元素，那么第i行（从0开始计数）的元素个数为i+1个（包括对角线上的元素）。因此，前i行一共有1+2+…+i = i(i+1)/2个元素。

对于第i行的第j个元素 (i >= j)，它是该行的第j+1个元素(因为是从0开始的)，加上前面i行的元素个数，就得到了它在连续存储单元中的位置。

7.栈队列

栈为FILO表，队列为FIFO队列；

8.快排思想：

设一组初始记录关键字序列为(45，80，55，40，42，85)，则以第一个记录关键字45为基准
(A)40，42，45，55，80，83
(B)42，40，45，80，85，88
(C)42，40，45，55，80，85
(D)42，40，45，85，55，80
参考答案是:C

1.首先拿45作基准值，然后左右遍历——>2.右边找到42，覆盖左边left的45,然后left前进一位——>3.left前进后发现80>基准值45，将right所指的42覆盖，right往后退一次——>4.依次重复

9.堆

小根堆条件：ki<=k2i&&ki<=k2i+1（根节点小于它的左右子树节点）
大根堆条件：ki>=k2i&&ki>=k2i+1