2020年PKU计算机基础801:数据结构与算法真题精解
本资源是一份2020年北京大学计算机基础801考试的真题,主要涉及数据结构和算法部分。以下是对题目及知识点的详细解析: 1. 第一个问题考察的是带头节点的双向循环链表的特性。在带头节点的链表中,当链表为空时,头节点的前驱指针`L.pre`应指向自身,而后继指针`L.next`应也指向自身,形成循环。因此,正确答案是**C. L.pre==L&&L.next==L**。 2. 三叉树的问题涉及到节点数的计算。在一个三叉树中,每个节点最多有3个子节点。叶节点没有子节点,因此对于一个有1、2、3个子树的节点,其叶节点数可以通过子节点数的两倍加1来计算,即总叶节点数为**y+2*z+1**,选**C**。 3. 树的前序遍历为SABEFGCDHIJ,后序遍历为BEFGACHJIDS。E的兄弟节点是与E处于同一层,但不在前序遍历中顺序相邻的节点。观察后序遍历,E的兄弟节点是其父节点的其他孩子,即F和G,H,所以选择**A. J,G,H**。 4. 在解析算术表达式3*2^(4+2*2-6*3)的过程中,遇到运算符"*"时,需要先计算括号内的表达式,得到的结果会入栈。当扫描到数字6时,表达式变为3*2^(8-6*3),此时数字栈和符号栈分别是**3, 2, 4, 8, (*)^(-)**,选**C**。 5. 拓扑排序是一种线性化的有向无环图(DAG)的排序,如果存在从`vj`到`vi`的路径,则表示`vi`依赖于`vj`,不符合拓扑排序的定义,因为拓扑排序遵循有向边的方向。所以,不可能出现的情况是**D. 有从vj到vi的路径**。 6. 广度优先搜索(BFS)和拓扑排序都是用于检测有向图中是否存在环路的算法,因为它们都依赖于节点的邻接关系。深度优先搜索(DFS)虽然能遍历图,但不一定能发现环路。最短路径算法如Dijkstra或Floyd-Warshall通常用于寻找两点之间的最短路径,而不是检测环路。所以判断出有环路的算法组合是**B. 12**,即广度优先搜索和深度优先搜索。 7. 散列表冲突是指不同的关键字映射到了同一个哈希地址上,常见的冲突解决方法包括:开放寻址法、链地址法、再哈希法等。 8. 对于排序过程的判断,数组21, 48, 67, 89, 34, 76, 12, 15, 67在排序过程中呈现的逐步变化,可以看到数值在跳跃,这不符合冒泡排序和插入排序的特点,因为它们都是稳定排序,不会发生相邻元素值跳跃。堆排序和快速排序可能会有这样的现象,但根据给出的信息无法确定具体是哪种。归并排序通常不会造成相邻元素的大幅度变化,因此可能是**A. 堆排序**或**B. 快速排序**,但题目未提供足够信息确定。 9. 关于磁盘索引问题: - 如果线性索引常驻内存,由于每个索引占用8字节,256KB内存可存放256*1024/8=32768个索引。每个记录需要16字节,加上索引,一个页块可存放的记录数为1024/(16+8)=48。考虑到每个页块的第1个记录用于索引,实际存放记录数为47。 - 使用二级索引,1024字节可以存放1024/1024=1个二级索引项。每个二级索引对应文件中的多个记录,具体数量取决于一级索引的大小和每个记录的关键码范围。 10. 交换排序(如冒泡排序、快速排序)对0,1,2元素的排序,主要通过不断比较和交换元素位置实现。算法思想是重复遍历数组,每次遍历都将最大或次大的元素移动到适当位置。时间复杂度为O(n^2),因为最坏情况下需要进行n(n-1)/2次比较和交换。对于这种只有3种元素的情况,交换排序通常能更快完成,因为可以提前终止循环,但具体复杂度分析仍取决于实际实现细节。 总结:这份题目涵盖了链表结构、树的性质、算术表达式处理、图论算法、散列冲突处理、排序方法识别以及磁盘索引和排序算法的讨论,全面检验了考生对数据结构、算法基础的理解和应用能力。
![](https://csdnimg.cn/release/download_crawler_static/86331212/bg1.jpg)
下载后可阅读完整内容,剩余5页未读,立即下载
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://profile-avatar.csdnimg.cn/default.jpg!1)
- 粉丝: 23
- 资源: 307
我的内容管理 展开
我的资源 快来上传第一个资源
我的收益
登录查看自己的收益我的积分 登录查看自己的积分
我的C币 登录后查看C币余额
我的收藏
我的下载
下载帮助
![](https://csdnimg.cn/release/wenkucmsfe/public/img/voice.245cc511.png)
最新资源
- 解决本地连接丢失无法上网的问题
- BIOS报警声音解析:故障原因与解决方法
- 广义均值移动跟踪算法在视频目标跟踪中的应用研究
- C++Builder快捷键大全:高效编程的秘密武器
- 网页制作入门:常用代码详解
- TX2440A开发板网络远程监控系统移植教程:易搭建与通用解决方案
- WebLogic10虚拟内存配置详解与优化技巧
- C#网络编程深度解析:Socket基础与应用
- 掌握Struts1:Java MVC轻量级框架详解
- 20个必备CSS代码段提升Web开发效率
- CSS样式大全:字体、文本、列表样式详解
- Proteus元件库大全:从基础到高级组件
- 74HC08芯片:高速CMOS四输入与门详细资料
- C#获取当前路径的多种方法详解
- 修复MySQL乱码问题:设置字符集为GB2312
- C语言的诞生与演进:从汇编到系统编程的革命
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035111.png)
![](https://csdnimg.cn/release/wenkucmsfe/public/img/green-success.6a4acb44.png)