2016年哈工大计算机科学与技术专业854考研真题

哈工大854计算机基础
哈尔滨工业大学854计算机基础课程是一门面向计算机科学专
业本科生的必修课程。

该课程主要介绍计算机硬件组成、操作系统、计算机网络、数据库等方面的基础知识和技术，为学生进一步学习计算机系统结构、算法设计和软件开发等课程打下坚实的基础。

该课程包括以下主要内容：
1.计算机的发展历程和基本概念：介绍计算机的起源、发展历程、计算机的基本组成和工作原理等内容。

2.计算机的硬件组成：介绍计算机的CPU、存储器、输入输出设备等硬件组成，以及它们之间的工作原理和相互作用。

3.操作系统：介绍操作系统的基本概念、功能和类型，以及涉及到的进程管理、内存管理、文件系统等方面的知识。

4.计算机网络：介绍计算机网络的基本概念、协议和体系结构，以及局域网、广域网、互联网等网络类型和应用。

5.数据库：介绍数据库的基本概念、数据模型和管理系统，以及关系型数据库、非关系型数据库等不同类型的数据库。

通过学习该课程，学生将能够深入了解计算机硬件和软件的基础知识和技术，为他们未来的学习和工作奠定坚实的基础。

- 1 -。

一、学院概况哈工大计算机专业创建于1956年，是我国成立最早的计算机专业之一。

哈工大计算机科学与技术一级学科在2007年被评为我国首批国家级一级重点学科，包含3个二级学科：计算机应用技术、计算机体系结构、计算机软件与理论，6个博士学位授权学科点和6个硕士学位授权学科点。

自2000年哈工大计算机学院成立以来，计算机学科进入强盛发展时期，在学科建设、科学研究和人才培养等方面不断取得令人鼓舞的成绩，在2007年教育部组织的学科评估中，哈工大计算机科学与技术学科名列第五。

学院现有教职工203人，其中教授39人（中国工程院院士1人，博士生导师28人，国家教学名师1人，省教学名师1人），副教授及副高级职称71人。

学院师资队伍实力雄厚，学术思想活跃，设备条件良好，保证了高水平学生的培养。

学院下设3个本科专业：计算机科学与技术、信息安全、生物信息技术。

学院具有较强的综合实力，承担着多项国家自然科学基金、国家有关部委重点项目课题。

教学、科研和实验环境完善。

近五年来，学院承担科研项目373项，科研经费3.11亿元。

获奖科研成果29项，其中国家科技发明二等奖1项，国家科技进步一等奖1项，二等奖10项；获省部级科技进步一等奖4项，二等奖9项；发表论文2193篇，其中被SCI收录306篇，EI收录504篇，ISTP收录176篇。

国家精品课4门；出版专著教材28部。

学院重视学生素质的全面提高，努力培养学生的各种能力，为学生创造多学科交叉的学习条件和环境。

学院使所培养的学生以基础知识扎实、专业知识面宽广、工作作风优良、动手能力强而在国内同行中享有盛名，受到用人单位的广泛赞扬。

他们中有的已成为学术研究领域的带头人，著名公司、企业的技术中坚力量，如中国工程院院士王天然、中国工程院院士、北京邮电大学校长方滨兴、香港理工大学计算机终身教授张大鹏、曾任中国科学院计算所所长高文、北京大学校长助理李晓明、北京航空航天大学副校长怀进鹏、国家863计划计算机软硬件技术主题专家女将军黄永勤、中国科学院软件研究所所长李明树、国务院学位委员会计算机科学与技术学科评议组成员徐晓飞。

2002年哈工大计算机科学与技术专业854考研真题I．数据结构一、填空题1.具有n个顶点的开放树，边的总数有（1）条。

2.由三个结点组成的二元树共有（2）各不同的结构形态。

3.N个元素的线性表，采用顺序存储结构，插入一个元素要平均移动表中（3-1）个元素，删除一个元素最坏情况下要移动（3-2）个元素。

4.一个二元树第5层结点最多有（4）个。

5.若在一个表中共有625个元素，且查找每个元素的概率相同，那么在采用分块查找时，每块的最佳长度为（5-1），此时的平均查找长度为（5-2）。

6.具有n个叶结点的哈夫曼（Huffman）树中，其结点总数为（6）。

7.在折半查找中，要求被查找元素必须采用（7-1）存储结构，且（7）。

8.堆分类（heap sort）的时间复杂性为（8-1）。

基数分类的的时间复杂性为（8-2）。

9.一个无向图有n个顶点，e条边，则所有顶点的度数之和为（9）。

10.设F是一个森林，B是由F按自然对应关系转换而得到的二元树，F中有n个非终结结点，则B中右子树为空的结点有（10）个。

二、选择题1.下三角矩阵A m*n按行优先顺序压缩存储在数组Sa[(n+1)*n/2]中，若非零元素a ij(0<=i,j<n)存放在Sa[k]中则i,j和k之间的关系为（1）。

A.k=i*n+jB.k=j*n/2+iC.k=(i+1)*i/2+jD.k=(j-1)*n/2+i-12.将一株有100个结点的完全二元树从上到下，从左到右依次进行编号，根结点的编号为1，则编号为49的结点的右孩子编号为（2）。

A.98B.99C.50D.没有右孩子3.数据在计算机中存储器内表示时，物理地址和逻辑地址相同并且是连续的，称之为（3）。

A.逻辑结构B.顺序存储结构C.链式存储结构D.以上都对4.一株非空二元树的所有叶结点在先根、中根和后根遍历序列中的相对顺序（4）。

A.发生改变B.不发生改变C.不能确定D.以上都不对5.对于一个具有n个顶点e条边的无向图，若采用邻接表表示，则表向量（顶点表）的大小为（5-1），所有关于顶点的邻接表（边表）的结点总数为（5-2）。

2016年硕士研究生入学考试大纲考试科目名称：计算机基础考试科目代码：[854] 本考试科目考试时间180分钟，满分150分。

包括数据结构与计算机组成原理两部分，每部分各75分。

数据结构部分（75分）一、考试要求1. 要求考生全面系统地掌握数据结构与算法的基本概念、数据的逻辑结构和存储结构及操作算法，并能灵活运用；能够利用数据结构和算法的基本知识，为应用问题设计有效的数据结构和算法；能够分析算法的复杂性。

2. 要求能够用C/C++/Java等程序设计语言描述数据结构和算法。

注：考试内容范围主要以参考书目1为标准，带*号部分不在考试范围之内。

二、考试内容1）数据结构与算法的概念a:数据结构与算法及其相关的基本概念b: 算法及其复杂性分析2)线性表a:线性结构及其操作算法b: 线性表的应用及算法3)树与二叉树a:二叉树的定义、性质、表示、遍历算法b: 树的表示、操作算法c: 森林与二叉树关系d: 树与二叉树的应用及算法4)图及其相关算法a:图的相关概念b: 图的存储结构与搜索算法c: 图的应用及算法5)查找与排序a:查找与排序的相关概念b:典型算法的描述及复杂性分析c: 查找与排序算法的应用6)外部排序与文件a:外部排序的相关概念及其基本方法b:文件的组织方式、特点及应用三、试卷结构1)题型结构a:填空题(0—15分)b:选择题(0—30分)c:简答题(0—30分)d:算法设计题(0—30分)注：题型分数在以上范围内浮动，总分为75分2)注意事项算法设计题，必须包含算法的基本思想、存储结构设计和算法的描述四、参考书目1．廖明宏，郭福顺，张岩，李秀坤，数据结构与算法（第4版），高等教育出版社，2007.112．严蔚敏，吴伟民，数据结构（C语言版），清华大学出版社，2002.09计算机组成原理部分（75分）一、考试要求要求考生全面掌握计算机组成的基本原理、概念和方法，系统深入地理解计算机系统中总线、存储器、运算器、控制器、I/O系统等的组织结构和工作原理，掌握计算机硬件系统的基本分析与逻辑设计方法，理解计算机硬件系统各组成部分之间的关系，建立计算机系统的整体概念。

2013年哈工大计算机科学与技术专业854考研真题I．数据结构部分一、单项选择题1.有一个100*90整型数的稀疏矩阵非0元素有10个，设每个整型数点2字节，则用三元组表示该矩阵时，所需的字节数为（1）。

A.60B.66C.180D.332.下列内部排序算法中，其比较次数与序列初始状态无关的是（2）。

A.快速排序B.直接插入排序C.二路归并D.选择排序3.若度数为m的哈夫曼树中，其叶子结点的个数为n，则非叶子结点的个数为（3）。

A.n-1B.n/(m-1)C.(n-1)/(m-1)D.(n+1)/(m+1)-14.长度为12有序表，按折半查找法对该表进行查找，以等概率查找表内各元素，则查找成功时所需要的平均比较次数为（4）。

A.35/12B.36/12C.39/12D.43/125.设有K个关键字互为同义词，若用线性探测法把这K个关键字存入散列表中，至少要进行（5）次探测。

A.K-1B.KC.K+1D.K(K+1)/26.有n个初始归并段，采用K路归并时，所需要的归并遍数是（6）。

A.log n kB.log2kC.log2nD.log k n7.有n个顶点，e条边的有向图采用邻接存储，若删除与顶点V i相关的所有边，其时间复杂度为（7）。

A.O(n)B.O(e)C.O(max(n, e))D.O(n*e)8.在平衡二叉树中插入一个结点造成不平衡，设最低的不平衡结点为A，并已知插入后A的左子树根的平衡度为0，右子树根的平衡度为1，则应作（8）型的调整达到平衡。

A.LLB.LRC.RLD.RR9.一棵具有n个非叶子结点完全二叉树的线索树，含有多少条线索（9）。

A.2n+1或2nB.2n+2或2n+1C.2n+1或2n-1D.2n+2或2n-210.在某森林的二叉树表示中，结点M和结点N是同一父节点的左儿子和右儿子，则在该森林中（10）。

A.M、N具有同一双亲B.M、N可能没有共同祖先C.M是N的儿子D.M是N的左兄弟二、填空题11.高度为h的完全二叉树至少有（11）个结点。

2016年哈工大计算机科学与技术专业854考研真题I．数据结构部分一、单项选择题1.具有2015个结点的完全二叉树，叶子节点个数为（1）。

A.1006B.1007C.1008D.10092.算术表达式a*(b+c)-d化为后缀表达式为（2）。

A.abcd+*-B.abc+*-dC.abc+*d-D.ab+c*d-3.某队列允许在某两端进入入队操作，但仅允许在一端进行出队操作，元素a、b、c、d、e依次入队，则不可能得到的顺序是（3）。

A.bacdeB.dbaceC.dbcaeD.ecbad4.在有N个叶子结点的哈夫曼树中，其结点总数为（4）。

A.不确定B.2N-1C.2N+1D.2N5.一个只有度为0和2的二叉树，有5个叶子结点，该二叉树最小层数是（5），最大层数是（5）。

A.3，4B.4，5C.5，6D.6，76.若邻接表中有奇数个边表结点，则一定是（6）。

A.图中有奇数个结点B.图中有偶数个结点C.图为无向图D.图为有向图7.下面给出的四种排序中（7）排序是不稳定性排序。

A.插入B.冒泡C.二路归并D.堆8.当初始序列已按关键字有序时，用直接插入算法进行排序，需要比较次数为（8）。

A.n-1B.log2nC.2log2nD.n29.设散列表中有m个存储单元，散列函数H(key)=key%p，则p最好选择（9）。

A.小于等于m的最大奇数B.小于等于m的最大素数C.小于等于m的最大偶数D.小于等于m的最大合数10.哈希查找中k个关键字具有同一哈希值，若用线性探测法将这k个关键字对应的记录存入哈希表中，至少要进行（10）次探测。

A.kB.k+1C.k(k+1)/2D.1+k(k+1)/2二、填空题11.在单链表中设置头结点的作用是，对于一个具有n个结点的单链表，在已知的结点*p后插入一个新结点的时间复杂度为，在给定值为x的结点后插入一个新结点的时间复杂度为。

12.完整的存储一个n*n对称矩阵所需的存储单元数为，采用上三角形式的压缩方式，存储一个对称矩阵所需的存储单元数为。

2006年哈工大计算机科学与技术专业854考研真题I．数据结构一、填空题1.由二元树的前序和后序序列（1）唯一确定这颗二元树。

2.在一个堆的顺序存储中，若一个结点的下标为i(0<i<=n-1)，则它的左儿子的下标为（2-1），右儿子的下标为（2-2）。

3.以折半查找方法从长度为10的有序表中查找一个元素时，查找成功的平均长度为（4）。

4.高度为K的完全二元树中，结点数n和K之间的关系是（4）。

5.同一棵二元查找树中插入一个元素时，若元素的值小于根结点的元素值，则应把它插入到根结点的（5）上。

6.举出两种磁带文件的分类方法：（6-1）和（6-2）。

7.按二元树的定义，具有三个结点的二元树共有（7）各形态。

二、选择题1.已知一个序列为{21,39,35,12,17,43}，则利用堆分类方法建立的初始堆为（1）。

A.39,21,35,12,17,43B.43,39,35,12,17,21C.43,39,35,21,17,12D.43,35,39,17,21,122.算法性能分析的两个主要方面是（2）。

A.数据复杂性和程序复杂性B.可读性和健壮性C.时间复杂性和空间复杂性D.正确性和简单性3.已知一个栈的输入序列顺序为1,2,3,4,…,n，输出序列为P1,P2,P3,…,P n。

若P n=n，则P i(1<i<n)为（3）。

A.iB.n-iC.n-i-1D.不确定4.在（4）算法中，第一趟排序后，最大的或最小的数一定在其最终位置上。

A.归并排序B.插入排序C.快速排序D.冒泡排序5.从二元查找树中查找一个元素时，其平均时间复杂性为（5）。

A.O(n)B.O(1)C.O(log n)D.O(n2)6.设结点X和结点Y的二元树T中的两个结点，若在前序序列中X在Y之前，而在后序序列中X在Y之后，则X与Y的关系是（6）。

A.X是Y的左兄弟B.X是Y的右兄弟C.Y是X的祖先D.Y是X的后代7.在一个长度为n的线性表中的第i个元素(0<0<=n-1)之前插入一个新元素时，需向后移动（7）个元素。

2004年哈工大计算机科学与技术专业854考研真题I．数据结构一、填空题1.用下标从0开始的n个元素的数组实现循环队列时，为实现下列变量m加1后，m仍在数组有效下标范围内，则m= （1）。

2.若二元树的一个叶结点是某子树的中根遍历序列中的第一个结点，则它必然是该子树的后根遍历序列中的（2）个结点。

3.对具有17个元素有序表A[1…17]作折半查找，在查找其元素值等于A[8]的元素时，被比较的元素下标依次是（3）。

4.快速分类的最大和最小递归深度分别是（4）和（5）。

5.外部分类过程主要分为两个阶段：（6）阶段和（7）阶段。

6.已知下面这些字母在某字典中A出现的概率为0.08，B出现的概率为0.04，I出现的概率为0.15，C出现的概率是0.20，E出现的概率是0.12，F出现的概率是0.16，R出现的概率是0.15，K出现的概率是0.10，若采用霍夫曼（Huffman）编码，则E的编码是（8）（要求概率小的作为左分支）。

7.索引文件在存储器上分两个区，分别为（9）和（10）。

二、选择题1.已知一算术表达式的中缀形式为a-(b+c/d)*e，其后缀形式为（1）。

A.–a+b*c/dB.–a+b*cd/eC.-+*bac/deD.Abcd/+e*-2.在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印机缓冲区，主机将数据依次写入缓冲区，而打印机则从缓冲区中取出数据打印，该缓冲区是一个（2）结构。

A.栈B.队列C.线性表D.以上都不是3.设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5和e6依次通过栈，一个元素出栈后即进入队列Q，若6个元素出队的序列是e2、e4、e3、e6、e5、e1，则栈S的容量至少应该是（3）。

A. 6B. 4C. 3D. 24.在下列叙述中，不正确的是（4）。

A.关键活动不按期完成就会影响整个工程的完成时间B.任何一个关键活动提前完成，将使整个工程提前完成C.某些关键活动若提前完成，则整个工程提前完成D.所有关键活动都提前完成，则整个工作将提前完成5.若需在O(nlogn)时间内完成对数组的分类，且要求分类是稳定的，则可选择的分类方法是：（5）。

哈尔滨工程大学计算机科学与技术学院计算机专业基础综合自命题数据结构计算机组成原理历考研真题汇编新编 Document number【980KGB-6898YT-769T8CB-246UT-18GG08】目 录说明：2016年公布的专业目录中，科目名称改为“816计算机专业基础综合（自命题①数据结构，②计算机组成原理）”，本书收录2001～2008年的真题，以供参考。

哈尔滨工程大学计算机科学与技术学院816计算机专业基础综合（自命题①数据结构，②计算机组成原理）历年考研真题汇编 最新资料，WORD 格式，可编辑修改！哈尔滨工程大学2003年数据结构试题一、判断题(每小题一分，共十分)1．数据结构，数据元素，数据项在计算机中的映象（表示）分别称为存储结构，结点，数据域。

对2．线性表的逻辑顺序与存储顺序总是一致的。

错3．广义表的表头或是元素或是一个广义表，而表尾总是一个广义表。

对4．拓扑排序是一种内部排序的算法。

错5．字符串是一种特殊的线性表，其特殊性体现在数据元素是一个字符。

对6．若线索二叉树有n个结点，则必有n+1条不空的指向树中结点的线索。

错7．稀疏矩阵的压缩存储方法一般有三元组和十字链表两种。

对8．在AOE网中，一定有不止一条关键路径。

错9．二维数组是其数据元素为线性表的线性表。

对10．一个栈的输入序列是12345，则输出序列43512是可能的。

错二、单项选择（每小题2分，共20分）1．数据结构从逻辑上可以分成线性和非线性两种结构。

2．哈希（Hash）法查找的基本思想是根据关键字值来决定记录的存储位置。

3．利用栈求表达式（（A-B）-C）-(D-(E-F)),操作数栈须有 4 项。

4．图的广度优先搜索算法类似于二叉树的按层遍历操作。

5．在所有排序方法中关键字比较次数与记录初始排列次序有关的是插入排序。

6．二维数组A的行下标从1到8，列下标从1到10，若每个元素占3个单元，则该数组按“以列序为主序”存放时，A[5][8]的起始位置是 180 7．表达式a*(b+c)-d的后缀表示（逆波兰式）是 abc+*d－8．在一个具有n个结点的单链表中查找，查找成功时需要平均计较(n+1)/2 结点。

854计算机考研题库854计算机考研题库是广大计算机考研学子备战考试的重要工具之一。

它囊括了各个知识点的题目，涵盖了计算机科学与技术的各个领域，对于考生来说是一本宝库。

本文将从题库的特点、使用方法以及对考生的帮助等方面展开论述。

首先，854计算机考研题库具有题目全面、难度适中的特点。

该题库覆盖了计算机科学与技术领域的各个知识点，包括计算机组成原理、数据结构与算法、操作系统、计算机网络、数据库等。

无论是基础知识还是专业知识，都能在题库中找到相应的题目进行练习。

而且，题库中的题目难度适中，既有一些基础题目用于巩固知识，也有一些较难的题目用于拓展思维，帮助考生提高解题能力。

其次，854计算机考研题库的使用方法多样灵活。

考生可以根据自己的需求选择不同的使用方式。

一种常见的方法是按照知识点进行刷题，将每个知识点的题目都进行逐一练习，以便全面掌握知识。

另一种方法是按照题目类型进行刷题，例如选择题、填空题、编程题等，这样可以针对不同类型的题目进行有针对性的练习。

还有一种方法是按照难度进行刷题，先从简单的题目开始，逐渐提高难度，以此来增强解题能力。

不同的使用方法可以根据个人情况进行灵活选择，以达到最佳的学习效果。

此外，854计算机考研题库对考生有着重要的帮助。

首先，通过刷题可以帮助考生巩固知识点，加深对知识的理解。

在解题过程中，考生需要回顾和应用所学的知识，从而巩固记忆。

其次，刷题可以帮助考生熟悉考试的题型和考点。

通过大量的题目练习，考生可以熟悉不同类型的题目，了解考试的出题规律，提高应试能力。

此外，刷题还可以帮助考生发现自己的薄弱环节，及时进行针对性的复习和补充，提高自己的综合能力。

然而，单纯依靠刷题是不够的，考生还需要结合其他学习方法进行综合提高。

例如，可以结合课堂学习，通过听讲和做笔记来加深对知识的理解；可以进行小组讨论和互助学习，通过与他人的交流来拓宽自己的思路；可以进行模拟考试，检验自己的学习效果。

综合运用各种学习方法，才能更好地备战考试。