2020北京理工大学计算机考研813真题.docx

新祥旭考研官网 http:/www.xxxedu.net/北理工考研辅导班：2020 北京理工大学计算机考研 813 真题一、数据结构1. 填空题1） 一颗二叉树使用二叉链表存储，使用_遍历可以求出树的深度。2）m 阶 B-树的非根非叶节点的孩子节点至少有_个3） 一个循环队列（size 为 100），rear 和 front 分别是 6 和 13，这个队列的长度是_.4） 一个关于链表操作的时间复杂度的问题，比较简单，我忘了剩下的题就记不清了。2.判断题1)静态链表的插入和删除操作比动态链表的要快。2）从平均时间复杂度来看，折半查找要比二叉排序树查找快。其他简单的我都忘了。3.选择题好像有两道题是考适合的数据结构的。（比如用下面哪一种数据结构表示队列最合适）其他的记不清了。下面都是大题。4.给了两个堆的操作函数：（20 分）PercolateUp(T,N,I):对长度为 N 的堆的 I 位置进行向上筛选使得以 I 为根的堆成为一个小顶堆。PercolateDown(T,N,I):对长度为 N 的堆的 I 位置进行向下筛选使得以 I 为根的堆成为一个小顶堆。新祥旭考研官网 http:/www.xxxedu.net/1）使用上面的函数说明如何根据一个序列建立一个小顶堆。然后给了一个序列，让写出最终建立的小顶堆。2）使用上面的函数说明如何在一个小顶堆中插入一个元素。然后给了一个序列，让写出插入一个元素后建立的小顶堆。3）使用上面的函数说明如何在一个小顶堆中删除一个非堆顶元素。然后给了一个序列，让写出删除一个非堆顶元素后建立的小顶堆。4） 使用上面的函数说明如何在一个小顶堆中修改一个元素。然后给了一个序列，让写出修改一个元素后建立的小顶堆。5.这道题 28 分还是 38 分。错不起。给了一个平衡二叉树的结点定义，然后又给了平衡二叉树的几个操作函数(LR,LL,RR,RL 旋转操作函数)。1) 请写出 LLRotation(L)的代码。2) 程序填空题：平衡二叉树的 Insert 操作。3）给了一个序列，写出最后建立的平衡二叉树。6.1）给了这些符号：+ - * / ( ) 在栈外的运算符优先级，让写出这些符号在栈内的运算符优先级。2）给了一个中缀表达式，让把其转换为后缀表达式的过程写出来（每一步中栈中运算符和当前输入符号还有后缀表达式都要写）。3）还是写运算符优先级。7.给了一个链表算法，让写出其时间复杂度并改进。这道题很简单。新祥旭考研官网 http:/www.xxxedu.net/二、计算机组成1. 填空题1）两个八位补码数加法，若溢出使用上限或者下限表示运算结果表示，写出运算结果。2）用 4K*8 的 DRAM 芯片组成 8K*16 的存储器，问 DRAM 芯片的数据线和地址线一共有几根；若 DRAM 的地址增加一根，存储器容量增大几倍？2. 选择题1）*系统使用 16 位指令，32 位数据，目的是：A增加系统安全性B降低系统复杂度C.增加指令存储密度D2）忘了。3）忘了。4）指令系统扩展的题。指令长 32 位，一个地址长 12 位，已知二地址指令有 250 条，则一地址指令最多有多少条。5） 给了磁盘的转速和一个磁道上的扇区数目以及每个扇区的字节数，让算数据传输率。下面是两道大题。3. 给了各类指令的执行路径以及每个阶段所需时间。让求：1）单周期指令系统中如何规定 CPU 时钟周期？新祥旭考研官网 http:/www.xxxedu.net/2）若访存和取指都缩短到 100ps，问系统加速比是多少。3）计算系统吞吐率。4. cache 组相连映射。1) 写出标记、组索引和块内地址所占位数。2) 给了一个 int 数组，问访问这个数组 8 次，cache 命中率是多少。