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

2016年哈工大计算机科学与技术专业854考研真题I．数据结构一、选择题1.设n是描述问题规模的非负整数，下面程序片段的时间复杂度是（）。

Int x = n * n;While (x >= 1) {X = x / 2;}A.O(log2n)B.O(n)C.O(nlog2n)D.O(n1/2)2.需要分配一个较大的存储空间并且插入和删除操作不需要移动，元素满足以上特点的线性表存储结构是（）。

A.单向链表B.静态链表C.线性链表D.顺序表3.已知字符串S为”ababcabcacbab”，模式串T为”abcac”。

若采用KMP算法进行模式匹配，则需要（）遍（趟匹配），就能确定T是S的子串。

A. 3B. 4C. 5D. 64.已知某棵二叉树的前序序列是1,2,3,4，则不可能为该二叉树的中序序列的是（）。

A.1,2,3,4B.2,3,4,1C.1,4,3,2D.3,1,4,25.将森林F转换为对应的二叉树T，F中任何一个没有右兄弟的结点，在T中（）。

A.没有左子树B.没有右子树C.没有左子树和右子树D.以上都不对6.一个含有n个顶点和e条边的无向图，在其邻接矩阵存储结构中共有（）个零元素。

A. eB.2eC.n2-2eD.n2-e7.在一棵高度为2和7阶B树中，所含关键字的个数最少是（）。

A. 5B.7C.8D.148.设待排序的元素个数为n，则基于比较的排序最坏情况下的时间复杂度的下界为（）。

A.log2nB.nC.nlog2nD.n29.下面关于B树和B+树的叙述中，不正确的是（）。

A.B树和B+树都能有效地支持随机检索B.B树和B+树都能有效地支持顺序检索C.B树和B+树都是平衡的多路树D.B树和B+树都可以用于文件的索引结构10.若待排序关键字序列在排序前已按其关键字递增顺序排列，则采用（）方法比较次数最少。

A.插入排序B.快速排序C.堆排序D.选择排序二、填空题11.在一棵n个结点的二叉树中，所有结点的空子树个数为11 。

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考研真题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 结点。

2005年哈工大计算机科学与技术专业854考研真题I．数据结构一、填空题1.设有两个算法在同一机器上运行，其执行时间分别为100n2和2n，要使前者快于后者，n至少为（1）。

2.在AOE（Activity On Edge）网中，从原点到汇点路径上各个活动的时间总和最长的路径称为（2）。

3.在等概率情况下，对具有n个元素的顺序列进行顺序查找，查找成功（即表中有关键字等于给定值K的记录）的平均查找长度为（3-1）；查找不成功（即表中无关键字等于给定值K的记录）的平均查找长度为（3-2）。

4.高度为h的堆中，最多有（4-1）个元素；最少有（4-2）个元素。

5.求具有最小带权外路径长度的扩充二元树的算法称为（5）算法。

6.每次使用两个有序表合并成一个有序表，这种排序方法叫做（6）排序。

7.若一个具有n个顶点，e条边的无向图是一个森林，则该森林中比有（7）棵树。

8.设森林F对应的二元树B，它有m个结点，B的根为P，P的右子树结点个数为n，则森林F中第一棵树的结点个数是（8）。

二、选择题1.将长度为n的单向链表链接在长度为m的单向链表之后的算法的时间复杂性为（1）。

A.O(1)B.O(n)C.O(m)D.O(m+n)2.对于一个线性表既要求能够进行较快速的插入和删除，又要求存储结构能反映数据之间的逻辑关系，则应该用（2）。

A.顺序存储方式B.链式存储方式C.散列存储方式D.以上均可以3.下述编码哪一组不是前缀码（3）。

A.{00,01,10,11}B.{0,1,00,11}C.{0,10,110,111}D.{000,001,010,101}4.当n足够大时，下述函数中渐近时间最小的是（4）。

A.T(n)=nlogn-1000lognB.T(n)=nlog3-1000lognC.T(n)=n2-1000lognD.T(n)=2nlogn-1000logn5.设有一个n行n列的对称矩阵A，将其下三角部分按行存放在一个一维数组B中，A[0][0]存放在B[0]中，那么第i行对角元素A[i][i]存放于B中（5）处。

哈尔滨工程大学计算机科学与技术学院816计算机专业基础综合（自命题①数据结构，②计算机组成原理）历年考研真题汇编最新资料，WORD格式，可编辑修改！目录【数据结构】.................................................................................................................... 错误!未定义书签。

2005年哈尔滨工程大学计算机科学与技术学院816数据结构考研真题.... 错误!未定义书签。

2004年哈尔滨工程大学计算机科学与技术学院816数据结构考研真题 (9)2003年哈尔滨工程大学计算机科学与技术学院816数据结构考研真题 (13)2002年哈尔滨工程大学计算机科学与技术学院816数据结构考研真题 (17)2001年哈尔滨工程大学计算机科学与技术学院816数据结构考研真题 (19)【计算机组成原理】 (23)2008年哈尔滨工程大学计算机科学与技术学院819计算机组成原理考研真题 (23)2005年哈尔滨工程大学计算机科学与技术学院819计算机组成原理考研真题 (28)2004年哈尔滨工程大学计算机科学与技术学院819计算机组成原理考研真题 (31)2003年哈尔滨工程大学计算机科学与技术学院819计算机组成原理考研真题 (35)说明：2016年公布的专业目录中，科目名称改为“816计算机专业基础综合（自命题①数据结构，②计算机组成原理）”，本书收录2001～2008年的真题，以供参考。

2004年哈尔滨工程大学计算机科学与技术学院816数据结构考研真题2003年哈尔滨工程大学计算机科学与技术学院816数据结构考研真题哈尔滨工程大学2003年数据结构试题一、判断题(每小题一分，共十分)1．数据结构，数据元素，数据项在计算机中的映象（表示）分别称为存储结构，结点，数据域。

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

哈工大854数据结构大纲
哈工大854数据结构课程的大纲主要包括以下内容：
1. 数据结构基础概念，介绍数据结构的基本概念、术语和基本
操作，包括数据的存储方式、数据的逻辑结构和物理结构等。

2. 线性表，介绍线性表的定义、基本操作和实现方式，包括顺
序表、链表和线性表的应用。

3. 栈和队列，介绍栈和队列的定义、基本操作和实现方式，包
括顺序栈、链式栈、顺序队列、链式队列和栈和队列的应用。

4. 树和二叉树，介绍树和二叉树的定义、基本操作和实现方式，包括二叉树的遍历、线索二叉树、树和二叉树的应用。

5. 图，介绍图的定义、基本操作和实现方式，包括图的遍历、
最小生成树、最短路径和图的应用。

6. 查找，介绍查找的基本概念和常用的查找算法，包括顺序查找、二分查找、哈希查找和查找的应用。

7. 排序，介绍排序的基本概念和常用的排序算法，包括插入排序、选择排序、冒泡排序、快速排序、归并排序和排序的应用。

8. 动态存储管理，介绍动态存储管理的基本概念和常用的存储
管理算法，包括分配与回收、内存碎片整理和动态存储管理的应用。

9. 高级数据结构，介绍高级数据结构的概念和应用，包括平衡
二叉树、B树、红黑树、哈希表和高级数据结构的应用。

以上是哈工大854数据结构课程大纲的主要内容。

通过学习这
些内容，学生可以掌握数据结构的基本概念、常用数据结构的实现
方式和操作方法，以及数据结构在实际问题中的应用。

2017中国人民大学计算机科学与技术(855)、软件工程(856) 真题(回忆版)学硕(855)计算机专业基础综合数据结构一、选择题(5个*3分)1、出栈顺序2、next数组3、2016个结点的八叉树，高度是多少4、顶点为n、边数为e的有向图，求拓扑排序的时间复杂度二、简答题(4个*5分)1、长度为2016的顺序表：(1)第i个位置删除和插入元素，需要移动多少个元素；(2)插入和删除，平均需要移动多少个元素。

2、普里姆算法求最小生成树，按顺序写出边。

3、给出a、b、c、d、e、f、g、h八个结点和每个结点的权值：(1)构造哈夫曼树，要求左子树根的权值小于等于右子树根的权值；(2)求出每个结点的哈夫曼编码。

4、哈希表：除留余数法的Hash函数，冲突处理方法分别用线性探查法和链地址法，分别求出两种方法的平均查找长度三、算法题(15分)1)图以邻接矩阵形式存储，写出完整的图的定义；2)输出一条由顶点v到顶点u的简单路径；3)输出全部简单路径。

离散数学一、自然推理系统两道1、命题逻辑：给出前提和结论。

2、谓词逻辑：符号化下述语句，并进行推理证明。

二、集合论1、偏序关系：告诉一个偏序关系，求最大元、最小元、极大元、极小元。

2、等价关系：已知R是等价关系，关系S满足<a,b>∈{∃c|<a,c>∈R∧<c,b>∈R }，证明S也是等价关系。

三、代数结构1、证明阶数小于6的群，都是交换群。

2、a,b,c都是群G中的元素，证明|abc|=|bca|=|cab|。

硕士研究生入学考试初试专业课资料
计算机专业基础
计算机考研历年真题(1991年-2008年) 友情分享！余人玫瑰手留余香！
第 3 页共 3 页
第共
第 3 页共 3 页
七、依次读入数据元素序列{a，b，c，d，e，f，g}j进栈每进一个元素，机器可要求下一个元素进栈或弹栈，如此进行则栈空时弹出的元素构成的序列是以下那些序列？（
{d ，e，c，f，b，g，a}， {f，e，g，d，a，c，b}
（低电平有效）作访作读
作读写命令信号（高电平为读，低电平为写）。

有一系统程序编译后为
根数据线，允许输出，允许写，片选
允许写，
允许输出，片选
允许输出，片选，允许写。