哈尔滨工业大学1999年研究生入学考试试题---数据结构 考研试题下载

哈尔滨工业大学计算机学院免费试题下载 哈尔滨工业大学1999年研究生入学考试试题-数据结构词分析（15分）1.广义表2.最小生成树 3.散列表 4.堆 5.随机文件二.试分别画出具有3个结点的树和3个结点的二元树的所有不同形态（同构的算一个）。（6分）三.本题给出一个子程序的框图，如图2，试填完完善此算法框图。该子程序用来寻找第一个均出现在三个整数单向链表F1，F2，F3中的相同整数。假定调用该子程序前，这三个整数链表已按从小到大的次序排序，单向链表的形式如下图1的例子所示。（15分）（注：在图2中的框图中：found和exit均为布尔型的变量，可取值为true和false。Val是整型变量，用来存放F1，F2，F3中无相同的整数found 的值为false，否则found的值为true。F1.link表示访问found结点的link域）。四 假设一株二元树，按其后根顺序的结点排序为：H，I，D，J，E，B，F，G，C，A而按中根顺序的结点排序为：H，D，I，B，E，J，A，C，F，G（1）试画出这株二元树。（7分）（2）画出它的线索二元树。（7分）五 已知集合S=7，3，4，6，19，14，16，9，22，11，试按照自左而右的顺序依次取出S中的每个元素，逐步建立一株对应于S的二元查找树。试画出所得到的二元查找树（不要求给算法）。（8分）六 本题给出的是将数组a的元素a1,a3,an从大到小排序的子程序的框图，如图3，填空完善此算法框图。该子程序采用改进的选择排序方法，该方法基本于以下思想：在选择第一大元过程中：a1与aj ( j = n , n 1,2)逐个比较，若发现aj1a1,则aj1与a1交换，交换后新的aj1有性质aj1= at ( j1t ai ( j2 j1 ),aj2与at (j2 t = 0 )个，依次为aj1,aj2,ajk,哈尔滨工业大学2000年研究生入学考试试题-数据结构一 名词解释：（12分）1抽象数据类型；2算法的时间复杂性；3散列法(hashing)；4索引文件。二填空：(12分)1在单链表中设置头结点的作用是_。2n个顶点的连通无向图，其边的条数至少为_。3线索二元树的左线索指向其_，右线索指向其_。4树在计算机内的表示方式有_，_，_。5排序（sorting）有哪几种方法_，_，_，_，_。三判断下列叙述是否正确，若你认为正确，请画“ “，否则画” “。1存在这样的二元树，对它采用任何次序的遍历，结果相同。（ ）2二元树就是结点度为2的树。（ ）3若连通图上各边权值均不相同，则该图的最小生成树是唯一的。（ ）4无向图的邻接矩阵一定是对称矩阵，但有向图的邻接矩阵一定是非对称矩阵。（ ）5完全二元树中，若一个结点没有左儿子，则必是树叶。（ ）四 堆与二元查找树的区别？（6分）五快速分类法的基本思想是什么？（6分）六设F=T1,T2,T3是森林，试画出所有对应的二元树，其森林如图所示：（6分）七 依次读入数据元素序列a，b，c，d，e，f，gj进栈每进一个元素，机器可要求下一个元素进栈或弹栈，如此进行则栈空时弹出的元素构成的序列是以下那些序列？（8分）d ，e，c，f，b，g，a， f，e，g，d，a，c，be，f，d，g，b，c，a c，d，b，e，f，a，g八 已知一个非空二元树，其按中根和后根遍历的结果分别为：中根：C G B A H E D J F I后根：G B C H E J I F D A 试将这样二元树构造出来；若已知先根和后根的遍历结果，能否构造这棵二元树，为什么？（8分） 九已知一个无向图如下图所示，要求分别用Prim和Kruskal算法生成最小树（假设以 为起点，试画出构造过程）。（8分）十试编写一个算法，他能由大到小遍历一棵二元树。（10分）十一。假设二元树用左右链表示，试编写一算法，判别给定二元树是否为完全二元树？（14分）哈尔滨工业大学2001年研究生入学考试试题-数据结构考试科目：数据结构报考专业：计算机科学与技术一填空（总分：10分，每一题2分）1对于一个具有n个结点的单链表，在已知的结点*p后插入一个新结点的时间复杂度为_, 在给定为x的结点后插入一个新结点的时间复杂度为_。2广义表（a，（a，b），d，e，( (I,j,), k) ）的长度是_, 深度是_。3对于一个具有n个结点的二员树，当它为一棵_二元树时具有最小高度，当它为一棵_时，具有最大高度。4在顺序文件中，要存取第I个记录，必须先存取_个记录。5求最短路径的dijkstra算法的时间复杂度为_。二选择填空：（总分10分，每小题2分）1若某线性表最常用的操作是存取任意指定序号的元素和最后进行插入和删除运算，则利用_存储方式最节省时间。（1）顺序表； （2）双链表；（3）头结点的双循环链表；（4）单循环链表2在一棵三元树中度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数为_个（1）4 （2）5 链表L是否是递减的。六判断以下序列是否为堆，如果不是，则把它调整为堆。(1)(12,24,33,65,33,56,48,92,86,70)(2)(25,56,20,23,40,38,29,61,35,76,28,100)七设有两个栈S1,S2都采用顺序栈方式，并且共享一个存储区Omaxsize-1,为了尽量利用空间，减少溢出的可能，可采用栈顶相向，迎面增长的存储方式。试设计S1,S2有关入栈和出栈的操作算法。八假设用于通讯的电文仅有6个字母abcdef组成，字母在电文中出现的频率分别为7，19，5，16，42，11。试为这6个字母设计哈夫曼编码九试写一算法，判断以邻接表方式存储的有向图中是否存在有顶点Vi到顶点Vj的路（ij）。注意：算法中涉及的图的基本操作必须在存储结构上实现。（3）6 （4）7 3在一个图中，所有顶点的度数之和等于所有边数_倍，在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的_倍（1）1/2 （2）2 （3）1 （4）44下列排序算法中，_,排序在某趟结束后不一定能选出一个元素放到其最终的位置上。（1）选择 （2）冒泡 （3）归并 （4）堆5散列文件使用散列函数将记录的关键字值计算转化为记录的关键字值计算转化为记录的存放地址，因为散列函数是一对一的关系，则选择好的_方法是散列文件的关键。（1）散列函数 （2）除余法中的质数（3）冲突处理 （4）散列函数和冲突处理三 回答下列问题 （总分15分，每小题3分）1数据结构与数据类型有什么区别？2什么是循环队列？3简述线索二元树的概念。4何为有向图的遍历？5什么是索引顺序文件？四分别画出和下列树对应的各个二元树。五试设计一个算法，判断b哈尔滨工业大学2000年研究生入学考试试题-操作系统考试科目：操作系统 一简答题：（共30分）1什么是操作系统？它有什么基本特征？（6分）2试比较进程和程序的区别。（6分）3在用户和操作系统之间存在哪几种类型的接口？它们的主要功能是什么？（6分）4解释下列概念：（12分）进程、线程、同步机构、临界区、文件、设备驱动程序二举例说明在分页系统下的地址转换过程（8分）三什么是死锁？产生的原因是什么？如何解除死锁？（8分）四什么是DAM方式？它与中断方式的主要区别是什么？（8分）五在一个请求页式存储管理系统中，进程P共有5页，访问串为：3，2，1，0，3，2，4，3，2，1，0，4时 ，试采用LRU置换算法和LFU置换算法，计算当分配给该进程的页面数分别为3和4时，访问过程中发生的缺页次数和缺页率，比较所得的结果，浅释原因。（15分）六在一个分时操作系统中，用户提交了一个作业，作业的内容包括：（1）请求内存（memory）；（2）计算并将结果存于内存memory ；（3）请求打印机printer；（4）将memory中的内容在打印机上输出；（5）释放printer；（6）释放memory；（7）结束。试从分时操作系统对资源管理的观点论述该作业从提交开始到结束为止，操作系统为其提供服务与控制的全部过程。（15分）七汽车司机与售票员之间必须协同工作，一方面，只有售票员把车门关好了司机才能开车，因此，售票员关好车门应通知司机开车。另一方面，只有当司机已经停下，售票员才能开门上下客，故司机停车后应通知售票员。假定某辆公共汽车上有两名售票员与一名司机，汽车当前正在始发站停车上客，试设必要的信号灯及赋初值，写出他们的同步过程。（用管程或信号灯均可）（16分）哈尔滨工业大学2001年研究生入学考试试题-操作系统一判断改错题（10分）（判断下列叙述是否正确，认为正确在括号内打“”；若不正确打“”，并改正。）1 现代操作系统的两个基本特征是中断处理和系统资源共享。（ ）2临界区是进程执行程序中对临界资源访问的那一段程序代码。（ ）3可执行目标程序是在经重定位后装入产生的。（ ）4采用spooling技术，就可使独占设备增加，使用户同时面对独立的同类设备。（ ）5打开文件的目的是把该文件的有关目录表复制到主存中约定的区域，以建立用户和该文件的联系。（ ）二填空（15分）1操作系统是对计算机进行（ ）的程序，是（ ）和用户的接口。2操作系统中进程的状态有许多种，但最基本的代表其生命周期的三种状态为（ ）、（ ）、（ ）。这三种状态间的转换称为（ ）。3调度算法中，FIFO算法，也称为（ ）法，它总是将处理机分配给（ ）进入就绪队列的进程。4存储管理的目的是（ ）和（ ），它的功能是（ ）、（ ）和（ ）。6通道是一种硬件设施，它是一种专用的、有很强（ ）的部件。7文件的安全管理，主要是通过设置（ ）来控制用户对文件的访问。三简答题（30分）1程序顺序执行与并发执行有什么不同？2父进程创建子进程是否等价于主进程调用子程序？为什么？3什么是“内存碎片”？应怎样解决“内存碎片”问题？4缓冲技术主要包括哪几种方式？5文件具有哪三大基本特征？6选择调度方式和调度算法是，应遵循的准则是什么？四单项选择题（15分）1对于给定的信号量s ，等待操作wait（s）（又称P操作）定义为：if s0 then ( ) eles挂起调用的进程。唤醒操作signal(s)(又称V操作)定义为：if 存在等待的进程 then 唤醒这个进程 else（ ）。当s 被初始化为1时，代码段：（ ）；临界区定义了一个临界区，（ ）；这种临界区通常称为（ ）。选择：AD：s:=0 s:=s+1 s:=s-1 s:=1 signal(s+1)wait(s-1) signal(s) wait(s) E:模块 类程 管程 线程2虚拟存储器的作用是允许（ ），它通常使用（ ）作为它的一个主要组成部分，对它的调度算法与（）基本相似，即把要经常访问的数据驻留在高速存储器中，因为使用了虚拟存储器，指令执行时（）。在虚拟存储器系统中常使用相联存储器进行管理，它是（）寻址的。选择：直接使用外存代替内存。添加此地址字长允许的更多内存容量。程序直接访问比内存更大的地址空间。提高内存的访问速度。：硬盘软盘寄存器：cache中断：所需数据一定在内存中找到必须事先使用复盖技术必须先进行“虚、实”地址变换必须将常用子程序先调入内存：按地址按内容寄存器计算进程是操作系统中的一个重要概念，进程是一个具有一定独立功能的程序在某个数据集合上的一次（）。进程是一个（）概念，而程序是一个（）的概念。进程的最基本状态有（）个。在一个单处理机系统中，若有个用户进程，在非管态的某一时刻，处于就绪状态的用户进程最多有（）个。选择：单独操作关联操作进行活动并发活动：静态动态逻辑物理：物理逻辑动态静态：五在请求分页系统中，其页表项中包含哪些数据项？它们的作用是什么？请举一个例子说明页表的作用。（分）六设有进程和并发执行，都需要享用资源、。使用资源情况如下：申请资源申请资源申请资源申请资源R1 申请资源 申请资源R2 试判断是否会产生死锁，并加以解释及说明产生死锁的原因与必要条件。（10分）七设在批处理系统中有四道作业。它们进入系统的时间及运行时间如下：作业号 进入时刻（h） 运行时间（h）100 002 50 0.503 00 0.104 50 0.20设系统每次只选择一个作业装人主机，分别给出在下列算法中这组作业的运行顺序、平均周转时间和平均带权周转时间FCFS算法、SF算法（最短者优先） 、 HRN算法（最高响应比者优先） （10分）. 哈尔滨工业大学计算机部分计算机原理重点第一章概述本章主要介绍计算机的组成概貌及工作原理,旨在使读者对计算机总体结构有个概括的了解,为深入学习以后各章打下基础。计算机软硬件概念、计算机系统的层次结构、计算机的基本组成、冯?诺依曼计算机的特点、计算机的硬件框图及工作过程、计算机硬件的主要技术指标和本书结构及学习指南。第一章重点难点计算机系统是一个非常复杂的系统，它由“硬件”和“软件”两大部分组成。读者必须清楚地认识到“硬件”和“软件”各自在计算机系统中的地位和作用，以及它们相互之间的依存关系。本课程旨在介绍计算机系统的“硬件”组成。图1.1使读者一目了然地看到一个结构简单、清晰明了的计算机内部组成框图，并由此使读者领略全书的要点和各章节之间的相互关系。图1.1 全书各章节之间的关系本章重点要求读者掌握一个较细化的计算机组成框图，如图1.2所示。而且要求学生根据此图描述计算机内部的控制流和数据流的变化，从而初步认识计算机内部的解题过程。由于本章的概念、名词较多，初学者也很难很快领会其确切含意。但只要循序渐进地认真学习以下各章节，读者便会自然而然地对初学的各个概念和名词加深理解和牢牢掌握。因此，学习时切忌急于求成，讲究的是按部就班，功到自然成。本章的难点是:计算机如何区分同样以0、1代码的形式存在存储器中的指令和数据。 哈工大2004年计算机复试试题2004年复试六门（操作系统编译原理 计算机网络 集合论与图论 数据库原理 计算机系统结构）每门25分 总分150分这几门中只有 OS（最好是西安电子科大的汤子赢的）与编译（我是用清华的）是可以看自己学校的教材，但是其他的最好是看哈工大他们学校的教材。如果能借到笔记那最好。现凭我的记忆将以上各门的考试内容（知识点）罗列如下，献给05年考研的同志们：（当然肯定不完整，欢迎大家可以补充）题型：单选题（一题1分）填空填（一空一般为1分）问答题（大题 一般5分）名词解释（编译 2分/题）判断题（1分/题）一操作系统OS1、OS的作用、功能和特征（大题）2、进程与程序的区别（大题）3、分页与分段存储管理的区别（大题）4、文件代表系统的 硬件 软件 硬件资源 软件资源（单选）5、PCB是进程存在的唯一标识（单选）6、内存存储管理的目的：提高内存利用率和方便用户（单选）7、死锁（好象也考了，我忘了）二编译原理1、词法分析程序的任务（填空）2、参数传递的四种方式：（填空）2分3、名词解释：句柄，素短语，算符优先文法4、一个文法是LL（1）文法当且仅当（填空）5、给出一个文法：构造该文法的LR（0）项目集规范族及识别活前缀的DFA（大题）三计算机网络1、常用的物理介质：（三个空）2、典型的MAC帧有（三个空）3、拥塞控制的两个阶段：（填空）4、202.118.224.0/21有几个C类网络（单选）5、给出一个IP叫你判断它是哪类（A、B、C、D）网络。（单选）6、以下不是路由协