|
考研2段

- 帖子
- 15
- 报考专业
- 未定
- 报考学校
- 未定
|
4#
大 中
小 发表于 2008-4-13 03:34 只看该作者
试将这样二元树构造出来;若已知先根和后根的遍历结果,能否构造这棵二元树,为什么?(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都采用顺序栈方式,并且共享一个存储区[O…maxsize-1],为了尽量利用空间,减少溢出的可能,可采用栈顶相向,迎面增长的存储方式。试设计S1,S2有关入栈和出栈的操作算法。
八.假设用于通讯的电文仅有6个字母abcdef组成,字母在电文中出现的频率分别为7,19,5,16,42,11。试为这6个字母设计哈夫曼编码
九.试写一算法,判断以邻接表方式存储的有向图中是否存在有顶点Vi到顶点Vj的路
(i<>j)。注意:算法中涉及的图的基本操作必须在存储结构上实现。(3)6 (4)7
3.在一个图中,所有顶点的度数之和等于所有边数______倍,在一个有向图中,所有顶点的入度之和等于所有顶点出度之和的_____倍
(1)1/2 (2)2 (3)1 (4)4
4.下列排序算法中,________,排序在某趟结束后不一定能选出一个元素放到其最终的位置上。
(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 s>0 then ( ) eles挂起调用的进程。唤醒操作signal(s)(又称V操作)定义为:
if 存在等待的进程 then 唤醒这个进程 else( )。
当s 被初始化为1时,代码段:( );
{临界区}
定义了一个临界区,( );这种临界区通常称为( )。
选择:A~D:①s:=0 ②s:=s+1 ③s:=s-1 ④s:=1 ⑤signal(s+1)
⑥wait(s-1) ⑦signal(s) ⑧wait(s)
E:①模块 ②类程 ③管程 ④线程
2.虚拟存储器的作用是允许( ),它通常使用( )作为它的一个主要组成部分,对它的调度算法与( )基本相似,即把要经常访问的数据驻留在高速存储器中,因为使用了虚拟存储器,指令执行时( )。在虚拟存储器系统中常使用相联存储器进行管理,它是( )寻址的。
选择:A:①直接使用外存代替内存。
②添加此地址字长允许的更多内存容量。
③程序直接访问比内存更大的地址空间。
④提高内存的访问速度。
B:①CDROM ②硬盘 ③软盘 ④寄存器
C:①cache ②DMA ③I/O ④中断
D:①所需数据一定在内存中找到 ②必须事先使用复盖技术 ③必须先进行“虚、实”地址变换
④必须将常用子程序先调入内存
E:①按地址 ②按内容 ③寄存器 ④计算
第一章 概述
本章主要介绍计算机的组成概貌及工作原理,旨在使读者对计算机总体结构有个概括的了解,为深入学习以后各章打下基础。计算机软硬件概念、计算机系统的层次结构、计算机的基本组成、冯?诺依曼计算机的特点、计算机的硬件框图及工作过程、计算机硬件的主要技术指标和本书结构及学习指南。
第一章 重点难点
计算机系统是一个非常复杂的系统,它由“硬件”和“软件”两大部分组成。读者必须清楚地认识到“硬件”和“软件”各自在计算机系统中的地位和作用,以及它们相互之间的依存关系。
本课程旨在介绍计算机系统的“硬件”组成。图1.1使读者一目了然地看到一个结构简单、清晰明了的计算机内部组成框图,并由此使读者领略全书的要点和各章节之间的相互关系。
图1.1 全书各章节之间的关系
本章重点要求读者掌握一个较细化的计算机组成框图,如图1.2所示。而且要求学生根据此图描述计算机内部的控制流和数据流的变化,从而初步认识计算机内部的解题过程。
由于本章的概念、名词较多,初学者也很难很快领会其确切含意。但只要循序渐进地认真学习以下各章节,读者便会自然而然地对初学的各个概念和名词加深理解和牢牢掌握。因此,学习时切忌急于求成,讲究的是按部就班,功到自然成。
本章的难点是:计算机如何区分同样以0、1代码的形式存在存储器中的指令和数据。
哈工大2004年计算机复试试题
2004年复试六门(操作系统编译原理 计算机网络 集合论与图论 数据库原理 计算机系统结构)每门25分 总分150分
这几门中只有 OS(最好是西安电子科大的汤子赢的)与编译(我是用清华的)是可以看自己学校的教材,但是其他的最好是看哈工大他们学校的教材。如果能借到笔记那最好。
现凭我的记忆将以上各门的考试内容(知识点)罗列如下,献给05年考研的同志们:(当然肯定不完整,欢迎大家可以补充)
大家可登陆 工大人自己的考研博客地址:http://kaoyanhit.blog.sohu.com/ 哈工大材料文本区:blog.sina.com.cn/hitkaoyan
进行全面收集哈工大各学院考研相关信息,接受咨询,历年录取信息、免费字下载、考研同仁经验互动交流。里面收集了好多不错的资料,一些经验之谈。并且正在不断更新中,请大家密切关注,参与评论。相信会对考研同学有所帮助
三、航天学院经验谈及历年录取分数线、比例、专业课复习策略、导师情况一览
哈工大5系(信息与通信工程专业)总体上来说不是很难的,因为只要你报考,付出努力的话,问题不是很大。
下面先说说信号系统的复习,哈工大信号的复习要采取本、基、面的策略。总体上来说,信号是非常简单的,考的都是基本概念,有一些题目你在看完考研的试卷后会觉得非常的基本。
纵观近三年的考题,信号的出题思路还是比较固定,变化不大。一般为7道大题。
一、回答问题,主要考一些基本概念。每年变化不大,在复习的过程中要抓住课本主线,①对一些关键的定理(如抽样定理,抽样后信号的频谱变化,Nyquist采样率);②LTI系统的定义特点,要熟悉;。大家可登陆 工大人自己的考研博客地址:http://kaoyanhit.blog.sohu.com/ 哈工大材料文本区:blog.sina.com.cn/hitkaoyan
其他学院陆续更新并发布。。请大家期待。
|