2016年哈工大计算机科学与技术专业854考研真题 I．数据结构部分 一、单项选择题 1. 具有2015个结点的完全二叉树，叶子节点个数为（1）。 A.1006 B.1007 C.1008 D.1009 2. 算术表达式a*(b+c)-d化为后缀表达式为（2）。 A.abcd+*- B.abc+*-d C.abc+*d- D.ab+c*d- 3. 某队列允许在某两端进入入队操作，但仅允许在一端进行出队操作，元素a、b、c、d、e依次入队，则不可能得到的顺序是（3）。 A.bacde B.dbace C.dbcae D.ecbad 4. 在有N个叶子结点的哈夫曼树中，其结点总数为（4）。 A.不确定 B.2N-1 C.2N+1 D.2N 5. 一个只有度为0和2的二叉树，有5个叶子结点，该二叉树最小层数是（5），最大层数是（5）。 A.3，4 B.4，5 C.5，6 D.6，7 6. 若邻接表中有奇数个边表结点，则一定是（6）。 A.图中有奇数个结点 B.图中有偶数个结点 C.图为无向图 D.图为有向图 7. 下面给出的四种排序中（7）排序是不稳定性排序。 A.插入 B.冒泡 C.二路归并 D.堆 8. 当初始序列已按关键字有序时，用直接插入算法进行排序，需要比较次数为（8）。 2A.n-1 B.log2n C.2log2n D.n 9. 设散列表中有m个存储单元，散列函数H(key)=key%p，则p最好选择（9）。 A.小于等于m的最大奇数 B.小于等于m的最大素数 C.小于等于m的最大偶数 D.小于等于m的最大合数 10. 哈希查找中k个关键字具有同一哈希值，若用线性探测法将这k个关键字对应的记录存入哈希表中，至少要进行（10）次探测。 A.k B.k+1 C.k(k+1)/2 D.1+k(k+1)/2 二、填空题 11. 在单链表中设置头结点的作用是 ，对于一个具有n个结点的单链表，在已知的结点*p后插入一个新结点的时间复杂度为 ，在给定值为x的结点后插入一个新结点的时间复杂度为 。 12. 完整的存储一个n*n对称矩阵所需的存储单元数为 ，采用上三角形式的压缩方式，存储一个对称矩阵所需的存储单元数为 。 13. 设一棵二叉树中的中序遍历序列为DBCA，后序遍历序列为DBAC，则这棵二叉树的前序遍历序列为 。 14. 设图有37条边，其最小的顶点数为 ，最多的顶点数为 。 15. 解决Hash冲突的两种常用方法为 、 。 三、简答题 16. 设有一优先级队列插入时可以任意优先级的元素，删除时只能删除最大优先级元素，写出用以下存储结构实现时的时间复杂度。 无序数组 有序数组 无序单链表 有序双链表 最大堆 插入时间复杂度 删除时间复杂度 17. 设有一组关键字T=(12,2,16,30,8,28,4,10,20,6,18)，设内存工作区可存放4条记录，用置换选择排序的方法生成初试归并段： （1） 一共可以生成多少个初始归并段？ （2） 对其进行归并排序，写出每一步结果，并给出最终输出结果。 四、算法设计题 按下列要求设计算法： （1） 描述算法设计的基本思想； （2） 根据设计思想，采用C或C++或Java语言描述算法； （3） 分析算法时间复杂度和空间复杂度。 18. 有一长度为n的整数序列a[n]，其元素按先严格递减后平桥递增的顺序排列，请设计一个时间上尽可能高效的算法FindMin()查找最小值元素，并分析时间复杂度和空间复杂度。 19. 二叉树采用二叉链表表示法，并增加一个你父结点指针parent域，以及flag域（可以取0，1，2三个值，取0时表示访问根结点，取1表示访问左孩子，取2时表示访问右孩子），在该存储结构上，设计一个算法实现非递归不用栈的后序遍历算法。 II．计算机组成原理部分 五、填空题 1. 计算机通电后执行的第一条微指令地址（微程序入口）来自 ，控制实现取令操作，然后由 产生后继微地址。 2. 十六进制整数FEH分别表示的是反码、补码、移码，对应的十进制值是 、 、 。 3. 某机共有156条指令，采用一地址格式，则指令字需取 位才能直接寻址64K个存储单元。完成一条这种形式的加法指令，需访问 次存储器。 4. 设x为17/35，则[2x]补为 ，[2x]补为 。 5. 已知接收到的海明码为0100111（按配偶原则配置），试问欲传送的信息是 六、选择题 1. 计算机与日常使用的袖珍计算器的本质区别在于（1）。 A.运算速度的高低 B.存储器容量的大小 C.规模的大小 D.自动化程度的高低 2. 开设计算机组成原理这门课的主要目的是为了研究（2）。 A.计算机系统的层次结构和组成 B.计算机系统的软件和硬件 C.计算机的工作过程 D.计算机的设计和工作原理 。 1 本文来源：https://www.wddqw.com/doc/49abb54d443610661ed9ad51f01dc281e53a56bd.html