圣才考研网小编在考试结束后及时为大家搜集整理了北京理工大学2020计算机基础考研真题，想要估分的考生不要错过哦！更多考研动态｜模拟试题｜历年真题请关注圣才考研网！

2020年考研计算机真题

  一、数据结构

  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为根的堆成为一个小顶堆。

  1)使用上面的函数说明如何根据一个序列建立一个小顶堆。然后给了一个序列，让写出最终建立的小顶堆。2)使用上面的函数说明如何在一个小顶堆中插入一个元素。然后给了一个序列，让写出插入一个元素后建立的小顶堆。3)使用上面的函数说明如何在一个小顶堆中删除一个非堆顶元素。然后给了一个序列，让写出删除一个非堆顶元素后建立的小顶堆。4)使用上面的函数说明如何在一个小顶堆中修改一个元素。然后给了一个序列，让写出修改一个元素后建立的小顶堆。

  5.这道题28分还是38分。。。错不起。给了一个平衡二叉树的结点定义，然后又给了平衡二叉树的几个操作函数(LR,LL,RR,RL旋转操作函数)。1)请写出LLRotation(L)的代码。2)程序填空题：平衡二叉树的Insert操作。3)给了一个序列，写出最后建立的平衡二叉树。

  6.1)给了这些符号：+-*/()在栈外的运算符优先级，让写出这些符号在栈内的运算符优先级。2)给了一个中缀表达式，让把其转换为后缀表达式的过程写出来(每一步中栈中运算符和当前输入符号还有后缀表达式都要写)。3)还是写运算符优先级。

  7.给了一个链表算法，让写出其时间复杂度并改进。这道题很简单。

  二、计算机组成

  1.填空题

  1)两个八位补码数加法，若溢出使用上限或者下限表示运算结果表示，写出运算结果。

  2)用4K*8的DRAM芯片组成8K*16的存储器，问DRAM芯片的数据线和地址线一共有几根;若DRAM的地址增加一根，存储器容量增大几倍?

  2.选择题

  1)***系统使用16位指令，32位数据，目的是：A.增加系统安全性B.降低系统复杂度C.增加指令存储密度D…

  2)忘了。

  3)忘了。

  4)指令系统扩展的题。指令长32位，一个地址长12位，已知二地址指令有250条，则一地址指令最多有多少条。

  5)给了磁盘的转速和一个磁道上的扇区数目以及每个扇区的字节数，让算数据传输率。

  下面是两道大题。

  3.给了各类指令的执行路径以及每个阶段所需时间。让求：

  1)单周期指令系统中如何规定CPU时钟周期?

  2)若访存和取指都缩短到100ps，问系统加速比是多少。

  3)计算系统吞吐率。

  4.cache组相连映射。

  1)写出标记、组索引和块内地址所占位数。

  2)给了一个int数组，问访问这个数组8次，cache命中率是多少。