2020年计算机专业基础回忆版1
需积分: 0 4 浏览量
2022-08-04
12:12:08
上传
评论
收藏 721KB PDF 举报
2020 计算机专业基础真题回忆
1 / 5
电子科技大学 2020 年计算机专业基础回忆版
写在前面：
这份回忆版试题集中了上百位考场上学长学姐们的回忆。其中我们可以发现，题
量与 2019 年保持持平，区别：2019 年操作系统题量大，2020 年数据结构题量大；
2019 年计算机操作系统是卷 1，数据结构是卷 2，2020 年正好相反。
复习建议：
1.在 2014 年之后的题目中，820 题目可以看到往年 408 题目的影子。因此好好
练习 408 题目很重要。
2.我们可以发现往年的算法题都在剑指 offer 这本书中有所体现。学有余力的同
学可以看看剑指 offer 一书中的线性表与树的题目。
3.对比往年真题可以发现，数据结构相对以前考的更加灵活，图相关的知识点考
察更加丰富，今年对深度优先搜索考察得更加细致，甚至考到有向图深搜判断是
否存在环。因此全面复习，对知识点理解要加深是之后复习的方向！
数据结构
一、填空题（10 个空）
1.n 个结点的完全二叉树的叶子结点的个数为__________。
2.一个带有头结点的单链表，在 p 指针所指结点后插入 q 指针所指结点的代码为
________。
3.深度优先遍历采用的是__________数据结构，广度优先遍历采用的是
___________数据结构。
4.能二分查找的前提条件是___________和______________。
5.平衡二叉树的平衡因子只可能是____________中之一。
6.线性表经常插入删除，适合采用_________存储结构。
7.________和_________排序的空间复杂度为 O(n)，O（logn）， 时间复杂度为
O(nlogn).
二、选择题（10 道）
1.给一串数，经过三趟排序后形成另一串数，问用的什么排序算法。
A．冒泡排序 B.直接插入排序 C.简单选择排序 D.归并排序
2.赫夫曼树，前缀编码问题
3.先序访问序列 ABCEFIJDGHKL、中序访问序列 BECIJFAGKHLD 求后序访问序列（）
4.求关键路径（比较常规），还问了路径长度
5.哪种算法不能求无权图的最短路径（）
A.Kruskal 算法 B.广度优先搜索 C. Dijkstra 算法 D.关键路径
6.要求找到入口和出口，以下哪个不一定能求解迷宫（）
A. 深度优先搜索 B.广度优先搜索 C.随机搜索 D.用栈保存分直接点然后逐一
遍历
评论0