2017年北邮803计算机学科基础综合真题参考答案学生整理
5星 · 超过95%的资源 需积分: 9 66 浏览量
2017-12-01
19:39:54
上传
评论 12
收藏 166KB PDF 举报 
2017 年北邮 803 计算机综合真题请自行从北邮研招网下载
1. A
解析：算法的时间复杂度是指执行算法所需要的计算工作量，问题规模越大，通常时间
复杂度越大。
常见的时间复杂度：
O(1),O(log2n),O(n),O(nlog2n),O(n^a),O(2^n)
2. B
解析：最优情况是一个链表的最小元素比另一个链表的最大元素大，此时只需要比较 n
次。
3. A
解析：带尾指针的单循环链表作为队列，插入只需要在尾指针的后面一个元素（即头结
点）之间插入，删除只需要删除尾指针当前所指元素，因此复杂度均为 O（1）。
4. D
解析：数组中枚举了下标，故存储单元数=(15*10*10)*5=7500。
很多同学可能不知道数组可以用负数表示，因为很多 C 语言初级教材中规定数组的下标
不能为负，而在 C 语言标准里允许数组下标为负，只是不建议这样写（因为可能访问到关键
区域）。
当下标为负时表示下标为 0 的地址之前的元素，比如：
int A[20];
int A1=&(A[10]);
此时 A1[-1]表示的就是 A[9].
5. C
解析：当 n 为 2 时，高度最小，为 2；当树为一条链时高度最大，为 n。
6. C
解析：ABD 均可以作为树的存储形式，而 C 层次顺序无法表示结点之间的父子关系，
因而无法作为树的存储形式。
7. D
解析：强连通图指的是有向图中任意两个结点都可达，边数最多时每个结点都和其它结
点有一条有向边，即总共 n*(n-1)条边。
8. A
解析：有向图中结点的入度之和一定等于出度之和；
邻接矩阵是对称矩阵，图不一定连通，比如全 0 的邻接矩阵；
连通分量指的是无向图中的极大连通子图，对于连通图，极大连通子图就是其本
身，极小连通子图就是其生成树；
用邻接表存储图所用的空间大小和顶点边都有关，邻接表既要存储当前结点，也
要存储该结点的边。
9. D
解析：当所找元素为第 1 个元素时，顺序查找次数少于折半查找；当所找元素为最后一
个元素时，折半查找次数少于顺序查找。
10. B
解析：排序算法的稳定性指的是所排序元素中的相同元素的相对顺序不变；选择排序复
杂度为 O(n^2)但不稳定；数据有序的情况下快速排序效率最差，达到 O(n^2)。
11. C
12. B
评论2
最新资源