2022考研计算机统考408数据结构部分试题解析

统考专业课真题答案
2023年考研专业课复习资料/真题/笔记/讲义等

A、试题:1,2,3,4是入栈顺序,请问一共有多少种可能的出栈顺序

B、解析:此题考查的是栈的后进先出的特性,也是栈这一部分内容常出的考题形式(已知入栈顺序,问出栈顺序的题型)。最简单的方式就是分为4种情况,1打头,2打头,3打头,4打头,在固定了第一个出栈的元素后,实际上就是考虑其他三个元素的组合情况,具体写出来后,发现共有14种情况。

C、难度分析:此题的难度属于中等偏下,本身就只有4个数,考查的也是最基础的栈的特性,非常直接清楚,做题也不需要拐弯抹角。

A、试题:编写程序判断一棵二叉树是否是一棵完全二叉树?

B、解析:此题首先需要了解的是完全二叉树的定义,即与深度相同的满二叉树对应位置的编号相同。所以可以从定义出发,编号是按照从上到下,从左到右的层次编号,所以可以使用层序遍历,利用队列,若左右孩子不空直接入队,否则对于空指针给一个特殊的标记,如“#”,也入队,输出出队顺序,若中间出现“#”则判断不是完全二叉树,否则判断是一棵完全二叉树。

C、难度分析:此题难度属于中等偏上,因为很多同学可能本身能够认识一棵完全二叉树,但是对于最原始的定义并不是很清晰,所以可能会把问题想得复杂,不一定能往层序遍历靠,难点在于切入角度这里,一旦想到使用队列实现层序遍历,代码层面其实非常容易。

A、试题:已知一个无向带权图,请你利用克鲁斯卡尔(或者普利姆)算法,画出该图的最小生成树,并且写出选边的顺序。

B、解析:此题就是单纯直接考察的最小生成树的算法,以克鲁斯卡尔为例,用三个字总结就是“只看边”,每次在未选择的所有边中选择权值最小的,在选择的过程中注意出现多条权值相同的边的情况,在不构成环的前提下,都可以选择,即最小生成树不一定唯一,直到选出n-1条边,把所有的结点都连接起来。

C、难度分析:此题难度属于简单,题目问的简洁明了,很直白的考察最小生成树算法,只要掌握了两个算法的过程和注意事项,对付此类题是轻轻松松。

查看全文

今年我考研 jinniankaoyan

考研热点推荐

热门课程

相关文章