2017年北邮803计算机学科基础综合真题参考答案学生整理 - CSDN文库

5星 · 超过95%的资源需积分: 9 98 浏览量更新于2023-03-16 评论 12 收藏 166KB PDF 举报

身份认证购VIP最低享 7 折!

领优惠券(最高得80元）

资源详情

资源评论

资源推荐

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

本内容试读结束，登录后可阅读更多

下载后可阅读完整内容，剩余5页未读，立即下载

评论2

朝雨暮雪

2017-12-19

有参考价值

wJs9528-1

粉丝: 23
资源: 4

会员权益专享

图片转文字

全年可省5，000元立即开通

最新资源

资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！点击此处反馈