17年数据结构考研真题解析
第一题：
解析：
我们说递归要找出口，这道题的出口是sum<n，经过观察可以得知：sum=1+2+3+。。。+k
设第k次循环跳出，则有sum=1+2+3+。。。+k=
<n
k<
,很显然答案选B
第二题：
解析：
第一句：你都采用非递归方式了，还必须使用栈，完全是错的。1错
第二句：例如s(n)=s(n-1)+1，栈内就要依次存s(n),s(n-1),s(n-2)。。。2对
第三句：确定了入栈次序，可能得到很多种出栈次序。3错
第四句：前半段对，栈只允许对栈顶元素进行操作。4错
答案选C
第三题：
解析：
这道题当一个结论记一下就好了：适合存储稀疏矩阵的是三元组表和十字链表
邻接矩阵适用于存储稠密矩阵，排除BD
二叉链表是和数有关的，排除C
三元组表：(1,3,6)
十字链表
第四题:
解析：
先序序列：根左右
中序序列：左根右
要想两者相同，根左和左根相同，而根是一定存在的，只能没有左的时候，序列就剩下了根右，此时两种序列是相同的，此时没有左子树，只有右子树，答案选B
第五题：
解析：
我们可以把图中所有的点都标上数字；写出的数字版的后续序列，然后一一对应就行了。
最后得出二叉树如下：如图所示，与a同层的结点是d
第六题：
解析：
从头开始读这个编码序列，读到一个序列和前面的编码相同，就能的出一个字母。
第七题：
解析：
在无向图中，边和度关系是1条边对应2个度。
题目里面是16条边，代表总共的度是32。
n4=3,n3=4,剩下的顶点的度小于3，即为n2，n1，n0
32 = 4×3+3×4 +n2×2+n1×1
我们说要使顶点个数最少，则尽量让度大的顶点个数最多，即剩下的点全是度是2的点。
32 = 4×3+3×4 +n2×2，求出n2 = 4个
图G顶点个数是3+4+4=11个
答案选A。
第八题
解析：
当结点个数是奇数时：例如：0,1,2
不管向上取整还是向下取整，mid都能指向最中间的数折半，例如0,1,2时，mid指向的就是1,此时左右两个子树高度差为0；
当结点个数是偶数时：例如：0,1,2,3
此时左右两个子树高度差是：1；
第九题：
解析：
这道题当作结论来记：关系数据库系统中的索引适合使用B+树
索引表和顺序表很像：
B+树也是一个顺序表。
第十题：
解析：
对于硬件本身关注的是程序执行的效率，也就是时间复杂度，而不是程序代码的多少，只有程序员阅读的时候才会关注代码的多少，所以第一句错误。
直接选择排序的空间复杂度是O(1)
归并排序的空间复杂度是O(n),它需要从新开辟一个新的同等大小的数组来存排序后的序列。
显然直接选择排序的空间复杂度更少，所以第二句错误。
归并排序的时间复杂度是O(nlogn)
直接插入排序的时间复杂度是O（n^2）
显然归并排序的算法效率更高，答案选B
第十一题：
解析：
考察顺序存储和链式存储的比较，显然顺序存储具有随机查询的特点，能一次定位到目标元素，因此这种存储方式适合查询时，跳来跳去的情况，链式存储适合多次修改(增删)。
插入排序，选择排序，起泡排序都是相邻两个元素进行比较，此时顺序存储和链式存储的时间效率没有太大区别。
希尔排序每次需要找到增量d的元素进行比较，堆排序每次比较的两个元素间隔也比较大，因此使用顺序存储能更快的找出要比较的元素。
答案选D
