北航961计算机2010-2018高清版真题及答案.zip

一、单项选择题
ABCBD ACBDC
二、简答题
1.链式存储结构。原因：线性表在处理过程中长度会动态地变化，说明对线性表的操作使以增加和删除数据为主。而顺序存储结构在增加和删除数据的时候需要整体移动数据的位置，比较复杂，所以宜采用链式存储结构。
2.最少有73个，最多有235个。
3.
（1）矩阵中不为0的元素的二分之一。
（2）矩阵中对应该顶点的行或列中非零元素的个数。
（3）矩阵中i对应的行和j对应的列的交点元素是否为0。为0的话就不存在边，不为0则存在边。
4. ①折半插入排序比较次数取决于每一趟的折半次数，而折半次数只取决于元素个数而与序列的初始状态无关。②当排序序列元素个数较小时。
三、综合题
1. 交换双向链表中某个指定结点与其直接后继结点的位置。
2. 三个。如下图
6
2 3 4 5 5
1 1 1 1 1 1 1 1 1 1

3 .前序：ABDEGCFH 后序：DGEBHFCA
4.深度优先：ACBDE 广度优先：ACEBD
四 、算法设计题