2012年1月11日
2012年01月11日
中国 科学技术大学
一九九八年招收硕士学位研究生入学考试试题
试题名称:程序设计
要求: 算法设计题目要求写注解,否则扣分. 写出正确的设计思想和伪代码给分.
一. 填空(15分,每空1分)
1. n个顶点的无向图的邻接矩阵至少有____非零元素;n个顶点的有向图是强连通图至少有____条边.
2. 折半查找的存储结构必须是_____,并且其中存储的关键字必须____;查找成功与不成功的最大比较次数是____.(设关键字总数为n)
3. 设广义表L=( ( ),( (y), B), L),则L的长度是______,深度是_____,head(L)是______, tail(L)是______.
4. 设高度为h的二叉树无度为1的结点,则此类二叉树至少有____个结点,至多有_____个结点.
5. 若要将内存中建立的二叉树(不一定是完全二叉树),写到磁盘文件中,则采用_____表示为宜.
6. 假定有k个关键字互为同义词,若用线性探测法把这k个关键字存入散列表中,至少要进行___次探测.
7. 在基于关键字比较且时间为O( n n)的排序中,若要求排序是稳定的,则可选用___排序;若要求就地排序(及辅助空间为O(1)),则可选用___排序 .
二. 请在下列各题中选择一个正确的答案(每个选择2分,共20分)
1. 在一颗m阶的B树中:
(1) 若在某结点中插入一个新关键字而引起结点的分裂,则该结点中原有关键字的个数是:
(a) m个(b) m 1个(c) m 2 个
(2) 若在某结点中删除一个新关键字而导致结点的合并,则该结点中原有关键字的个数是:
(a) 个(b) 个(c) 个
2. 用ISAM组织文件适合于
(a) 磁带机(b) 磁盘
3. 是否存在这样的二叉树,对它采用任何次序的遍历,其遍历产生的节点序列相同?
(a) 存在(b) 不存在
4. 若一个有向图的邻接矩阵中,主对角线以下的元素均为零,则该图的拓扑有序序列:
(a) 不存在(b) 存在
5. 对外部排序的k路平衡归并,采用败者树时,归并效率与k
(a) 有关(b) 无关
6. 设二叉排序树中关键字由1至1000的整数构成,现要检索关键字为363的结点,下述关键字序列哪一个不可能是二叉排序树上搜索到的序列?
(a) 2, 252, 401, 398, 330, 344, 397, 363
(b) 924, 220, 911, 244, 898, 258, 362, 363
(c) 952, 202, 911, 240, 912, 245, 363
(d) 2, 399, 387, 219, 266, 382, 381, 278, 363
7. 已知待排序的n个元素可分为n/k个组,每个组包含k个元素,且任一组内的各元素均分别大于前一组的所有元素并小于后一组内的所有元素,若采用基于比较的排序,其时间下界应为:
(a) O(n n)(b) O(n k)(c) O(k n)(d) O(k k)
8. 下述二叉树中,哪一种满足性质:从任一结点出发到根的路径上所经过的结点序列按其关键字有序:
(a) 二叉排序树(b) 哈夫曼树(c) AVL树(d) 堆
9. 将两个各有n个元素的有序表归并成一个有序表,其最多的比较次数是:
(a) 2n(b) n(c) 2n 1
三. (共15分)Fibonacci树是一种特殊的二叉树,下面给出构造该树的一种算法:
procedureFibonacciTree(d:integer ; Var T:binarytree)
{//d是 Fibonacci树的深度
if d=0 then T := nil
else
{new(T);
if d=1 then { T^.leftptr:=nil; T^.rightptr:=nil }
else {// d>=2
FibonacciTree(d 2, T^.leftptr);
FibonacciTree(d 1, T^.rightptr); }
}
}
(1) 画出深度为4的Fibonacci树(即用d=4调用上述算法的结果) (7分)
(2) 从你画的树中分析深度d的Fibonacci树中结点总数和Fibonacci数的关系.Fibonacci数定义如下:
= 1 , = 1
= + n>1
(3) 你所画出的Fibonacci树是否为平衡二叉树?若是,它是否为同样深度的平衡二叉树中节点数目最少的一种? (4分)
四. 证明若二叉排序数中的一个结点存在两个孩子,则它的中序后继节点没有左孩子, 则它的中序前趋节点没有右孩子. (10分)
五. (共25分) 设数组A[1..n]含有n个互不相同的数,若 i A[j] , 则偶对(i,j)称为A的一个逆.
(1) 列出数组[3, 4, 9, 7, 1]的五个逆;(2分) (2) 元素取自集合{1, 2, 3, … n } 的所有数组中,哪一个数组具有最多的逆,其中数是多少? (3分)
(3) 插入排序的运行时间和数组中逆的数目有何关系? (3分)
(4) 写一个算法将两个有序段 r[low..mid] 和 r[mid + 1..high] 归并成一个有序段,并要求在归并的同时求出归并前r[low..high]中逆的总数. (15分)
(5) 利用(4)中的归并算法来对r[1..n]进行归并排序,并同时求出原数组r[1..n]中逆的总数,其时间复杂度是多少? (2分)
六. (共15分) 一个有向图G=(V,E)的平方图 满足下述性质:
(u,w) ∈ 当且仅当存在某个顶点v∈ V, 使得(u,v) ∈ E 且 (v,w) ∈ E.
写一个算法从给定的G求出 , G 和可 分别用两个邻接表表示.
中国科学技术大学
一九九八年招收硕士学位研究生入学考试试题
试题名称:编译原利于操作系统
一. (10分) 某操作系统下合法的文件名为
device:name.extension
其中第一部分( device: )和第三部分( .extension )可省略,若device,name和extension都是字母串,长度不限,但至少为1,画出识别这种文件名的确定有限自动机.
二. (10分) 下面文法是否为LL(1)文法? 说明理由.
S ---> A B | P Q xA ---> x yB ---> b c
P ---> d P |εQ ---> a Q |ε
三. (10分) 把表达式
-( a + b ) * ( c + d ) + ( a + b + c )
翻译成四元式.
四. (10分) UNIX下的C编译命令cc的选择项g和O的解释如下,其中dbx的解释是“dbx is an utility for source-level debugging and excution of programs written in C ”.试说明为什么用了选择项g后,选择项O遍被忽略.
-gProduce additional symbol table information for
dbx(l) and dbxtool(l) and pass lg option to ld(l)
(so as to include the g library, that is :
/usr/lib/libg.a). When this option is given, the O and R options are suppressed.
-O[level]Optimize the object code. Ignored when either g, -go,
or a is used. …
五. (10分) 下面程序在SUN工作站上运行时陷入死循环,试说明原因.如果将第6行的long *p 改成 short *p, 并且将第16行long k改成short k后,loop中的循环体执行一次便停止了.试说明原因.
Main()
{
addr();
loop();
}
long *p;
loop()
{long i,j;
j=0;
for(i=0;ic:二分查找;d:二叉排序树
2. 对一般二叉树而言,求节点按某种序列的前趋节点变得容易的线索二叉树是___和____.
a: 前序线索二叉树;b: 中序线索二叉树;c: 后序线索二叉树
3. 若一个有向图具有拓扑排序序列,那么它的邻接矩阵必定为____.
a: 对称矩阵;b: 稀疏矩阵;c: 三角矩阵;d: 一般矩阵
4. 采用开址定址法解决冲突的哈希查找中,发生集聚的原因主要是____.
a: 数据元素过多;b: 负载因子过大;c: 哈希函数选择不当;
d: 解决冲突的算法选择不好.
5. 对n个关键字的文件进行内部排序,在最好情况下,最快的排序方法是____;相应的时间复杂度为_____;该算法的稳定性是_______.
A: ①快速排序;②插入排序;③归并排序;④选择排序
B: ① O( );② O(n);③ O(n n);④ O(n
发表评论
-
[转载]【引用】毛衣编织小技巧
2012-01-20 11:26 684[转载]【引用】毛衣编织小技巧 2012年01月18日 ... -
初二期末测试题
2012-01-20 11:26 619初二期末测试题 17小时 ... -
erefde_快乐急速青春
2012-01-20 11:26 658erefde_快乐急速青春 2012年01月11日 山东 ... -
2012-01-16
2012-01-20 11:26 4522012-01-16 2012年01月16日 ... -
c/c++连接mysql数据库-justinzhang-博客园
2012-01-19 16:06 1320c/c++连接mysql数据库-justinzhang-博客园 ... -
[转]iOS In-app Pursechase
2012-01-19 16:06 1059[转]iOS In-app Pursechase 2012年 ... -
开始研究Directshow
2012-01-19 16:06 2465开始研究Directshow 2011年09月19日 重 ... -
【转】 Android Suspend/resume 过程分析.
2012-01-19 16:06 1115【转】 Android Suspend/resume 过程分析 ... -
评论:什么力量让我们如此害怕
2012-01-17 05:57 598评论:什么力量让我们如 ... -
关于国金证券
2012-01-17 05:57 652关于国金证券 2011年10月22日 一、主要概况 国金 ... -
DOM――获取页面信息
2012-01-17 05:57 788DOM――获取页面信息 2011年10月24日 1、获得 ... -
《论语》解读之3-15《德行之要谦恭谨慎》
2012-01-16 04:45 773《论语》解读之3-15《德 ... -
打造新中式空间
2012-01-16 04:45 599打造新中式空间 2011年1 ... -
2011-12-13
2012-01-16 04:45 5422011-12-13 2011年12月13日 ... -
还生活在父母之命的年代吗?
2012-01-16 04:44 650还生活在父母之命的年 ...
相关推荐
11,串口读取温度2012年1月9日.pdf
自己研究结合VS2010旗舰版与VSS2005,完成了我们办公室8台机器的日常联机完成项目的修改,签入,签出等。达到资源自动整合。
Alexandre_Belloni_boottime_optimizations_2012年11月6日在ELC_Europe上做的报告1
计算机网络(本科)小蓝本答案两栏排版2012年7月6日11点用.pdf
修改时间: 2012年1月11日, 8:26:44 MD5: 44E8DD7E572209212F7931F534FA4148 SHA1: A7B268B8B7CEAC52CF21FC1077ED8658A991898C CRC32: 576185F8 官方原程序验证信息: 文件: NXPowerLiteSetup50_6.exe 大小: ...
2012年国际工业设计与加工工艺学术会议(ICIDP2012)将于2012年10月19日—21日在中国上海召开。ICIDP2012是中国在工业设计与加工工艺领域发起,跨越艺术与科学领域的一个高水平国际学术会议。国际工业设计与加工工艺...
以前的sniffer,现在的A3,A3为sniffer最新的替代产品,嗅探功能更强大。此版本为自2012年1月11日最新版本
Intel英特尔Core i3/Core i5/Core i7系列CPU显示驱动14.46.9.5394版For XP-64(2012年1月11日发布)
3.已知2012年1月1日为星期日,使用面向对象的方法设计一个查询星期几或者直接输出月历的程序。具体要求:设计一个日期类,含有年月日以及星期,通过按键输入执行相应的操作:(1)查询2012-2020年间的任何一天是星期...
mars Android开发视频教程源码 网上有太多 大多不全也没有说明 现在整理了下目前能找到的源码 ...第四季 只有4、6、8、10、11、12 第五季 第1-5课已有 所有已有源码都按课程顺序排好了 不需要资源分即可下载
据此我站定于每月1到5日汇总分析银川二手房上月价格分析数据: 数据监控日期:2012年4月1日-2012年4月28日 报告发布日期:2012年5月7日 去除关键信息失实,价格或面积信息未填写的房源,去除中介用户重发但未修改...
Telerik的Silverlight5控件包,开发者版本,非试用版,2012-10-...修改时间: 2012年11月26日 星期一, 8:05:56 MD5: 328015A027E66F6E412D41975FCBC3FC SHA1: 40516742FFE52E282E66EBCA6DE8E55ED7DBB164 CRC32: FD787480
Powershell将信息存储在对象中,每个对象都会有一个具体的类型,简单的文本会以System.String类型...2012年1月11日 15:19:49 PS C:Powershell> $date.GetType().FullName System.DateTime 每一个类型都 可以包含一些
3. 已知2012年1月1日为星期日,使用面向对象的方法设计一个查询星期几或者直接输出月历的程序。具体要求:设计一个日期类,含有年月日以及星期,通过按键输入执行相应的操作:(1)查询2012-2020年间的任何一天是...
2012年3月21日-2012年08月31日实施阶段(Do)、2012年09月01日-2012年10月20日检查阶段(Check);2012年10月21日-2012年12月25日处理阶段(Action)。 QC小组概况表 表一 小组名称 QC 小组 课题名称 降低建筑工程...
特别说明:Easycrm 自2012年1月1日起,原本免费版继续提供论坛技术支持,另外提供商业版! Easycrm 2012 v3.0.1 更新: 新增: 01.新的UI界面,更简洁的表单设计; 02.整合下拉框,原多个数据表改为单表...
程序员的数学1,(日)结城浩著;管杰译 ,P232 人民邮电电出版社
2012年09月11日 - 重建配置文件的时候,自动备份旧配置文件,防止误删 - 开启MySQL性能元数据信息库引擎(performance_schema) - 优化xServer.bat脚本性能 2012年08月30日 - 更新MySQL版本为5.5.27 - 更新FileZilla...
2012年11月11日 V2.3版本发布 1.增加了易讯网。 2.增加了1号网。 3.修正了腾讯微团购。 2012年11月11日 V2.2版本发布 1.增加了腾讯微卖场。 2012年11月10日 V2.1版本发布 1.优化代码,优化了读取比价...
数据由一个匿名个人在2012年10月和2012年11月期间收集的两个月数据组成,其中包括每天5分钟间隔执行的步骤数。 数据 可以从课程网站下载此作业的数据: 数据集:[52K] 此数据集中包含的变量是: 步数:每隔5分钟...