每个空格对应一个序号,有A、B、C、D四个选项,请选择一个最恰当的选项作为解答。
3. 一棵完全二叉树上有1001个结点,其中叶子结点的个数是
。
A B C D
C
这棵完全--X.树的高度为
根据二叉树的性质,从第1层到第 9层共有结点2
9 -1=511个。第10层全部是叶子结点,因此处于第10层的叶子结点数为 1001-511=490。同时注意到,第9层有2
9-1 -490/2=11个叶子结点。因此共有490+11 =501个叶子结点。
也可以用另外一种方法来做。设二叉树的总结点数为n,叶子结点数为n
0 ,度为1的结点数为n
1 ,度为2的结点数为n
2 ,根据二叉树的性质有:n
0 =n
2 +1,n=n
1 +2n
2 +1,于是可得,n=n
1 +2n
0 -1,由于在完全二叉树中,度为1的结点总数n
1 要么为0要么为1,此题中显然为0,这样才能保证等式两边都是奇数,因此1001=2n
0 -1,解得n
0 =501。
5. 关于各种非空线索二叉树中空指针的个数有如下说法:
①任一非空先序线索二叉树有2个空指针。
②任一非空中序线索二叉树有2个空指针。
③任一非空后序线索二叉树有2个空指针。其中说法准确的个数是
。
A B C D
B
非空先序线索二叉树有1或2个空指针,如图13-39所示。
易知,先序序列的最后一个结点一定是叶子结点,该结点无后继,于是其右指针为空。先序序列的第一个结点一定是根结点,其无前驱,若根结点无左子树,显然其左指针为空,同时注意到,第一个结点的右指针、最后一个结点的左指针以及夹在第一个结点(根结点)和最后一个结点之间的任一结点的左右指针不是指向其左右子树便是指向前驱或后继的线索,均非空,于是该树中共有2个空指针;若根结点有左子树,那么根结点的左指针指向其左子树,同时也注意到,第一个结点(根结点)的右指针、最后一个结点的左指针以及夹在第一个结点和最后一个结点之间的任一结点的左右指针不是指向其左右子树便是指向前驱或后继的线索,均非空,于是该树中便只有一个非空指针。因此①错误。
易知,任一非空中序线索二叉树中,中序遍历的第一个结点肯定是左子树为空的结点,它无前驱,其左指针为空;最后一个结点肯定是右子树为空的结点,它无后继,其右指针为空;第一个结点的右指针、最后一个结点的左指针以及夹在第一个结点和最后一个结点之间的任一结点的左右指针不是指向其左右子树便是指向前驱或后继的线索,均非空。因此,空指针一定是2个。因此②准确。
非空后序线索二叉树有1或2个空指针(如图13—40所示)。
其推理论证类似于非空先序线索二叉树,在此不再赘述。因此③不准确。
著名的软件工程专家Boehm于1983年提出了软件工程的七条基本原理:用分阶段的生命周期计划严格管理、 10 、实行严格的产品控制、采用现代程序设计技术、明确责任、 11 、承认不断改进软件工程实践的必要性。(注意,答案须按顺序排列。) PERT图常用于管理项目进度,某PERT图如图13-13所示。其中,4号顶点的最迟开始时间、8号顶点的最早开始时间两个信息未知。 那么,4号顶点的最迟开始时间、8号顶点的最早开始时间分别为 16 、 17 ,该PERT图的关键路径为 18 。 19. 现有下列说法:
①模型是对现实的简化,建模是为了更好地理解所开发的系统。
②用例图定义了系统的功能需求,它是从系统的外部看系统功能,并不描述系统内部对功能的具体实现。
③白盒测试仅与程序的内部结构有关,完全可以不考虑程序的功能要求。
④软件技术复审是对用户和测试人员的一种质量保证活动。错误的是
。
A B C D
D
软件技术复审是由软件开发人员实施的一种质量保证活动。
质量成本可以被划分为与预防、鉴定及失败相关的成本;而失败成本包括内部失败成本和外部失败成本。其中: 质量计划属于: 21 。测试设备属于: 22 。测试属于: 23 。设备校准和维护属于: 24 。修复属于: 25 。退换产品属于: 26 。 31 表示了类间“is-a”的关系,而 32 表示了类之间的“contains-a”关系。 若要封装对象,并提供不同的接口时,可采用 33 ;若要将请求封装成对象,则可采用 34 ;若要将可互换的行为封装起来,并采用委托的方式来决定使用哪一个,则可采用 35 。 若每一条指令都可以分解为取指,分析和执行三步。已知取指时间t取指 =8△t,分析时间t分析 =3△t,执行时间t执行 =12△t。如果按照流水线方式执行指令,从头到尾执行完 100条指令至少需 41 △t。如果取指时间t取指 =8△t,分析时间t分析 =12△t,执行时间 t执行 =3△t,则从头到尾执行完100条指令至少需 42 △t。42.
A B C D
D
采用流水线方式时,系统在同一时刻可以进行第k条指令的取指,第k+ 1条指令的分析,第k+2条指令的执行,所以效率大大提高了。采用流水线的执行示意图如图13-45所示。
平时大家看到的都是这样的示意图,但是平时我们看到的图都是笼统的。这里把所有周期都定为统一长度。这样流水线的总时间为:(n+2)×周期。如此题中为
(100+2)×12=1224
但这不是最少的,为什么?先看另一个流水线总时间计算公式:
T
总 =第一条指令顺序执行时间+(指令条数-1)×周期
其中,k是流水线的段数,t
i 是各段的时间,n是总任务数。
这个公式是怎么来的呢?请大家结合该题数据:取指时间t
取指 =8△t,分析时间t
分析 = 3△t,执行时间t
执行 =12△t,如图13-46所示。
其中黑的区域表示分析段空闲,根据这种方式算出来的总时间为
8+3+12+(100-1)×12=1211
这种方式的总时间为什么比图13-45的方式要少呢?这是因为在图13-45中,限定了各段的时间一样,都为最慢的那段的时间,而图13-46的方式却没有,其在执行第一条指令时,取指段节省12-8=4的时间,分析段又节省12-3=9的时间,所以总共节省了 13的时间。按图13-45方式来执行时,第一条指令的取指和分析段有时间空闲,黑色区域表示空闲,如图13-47所示。
如果取指时间t
取指 =8△t,分析时间t
分析 =12△t,执行时间t
执行 =3△t,此时时空图将变成如图13-48所示。
容易看出,执行100条指令的时间不变。
45. 在一个分页存储管理系统中,页表内容如表13-6所示,若页的大小为2K,则地址转换机构将逻辑地址0转换成的物理地址为
。
表13-6 页 表 页号
块号
0
2
1
1
2
6
3
3
4
7
A B C D
B
在页式存储管理系统中,物理地址为页面对应的物理块号与页内地址拼接的结果,逻辑地址为0,也就是说逻辑页号为0,页内位移也为0,故物理块号为2,块号位移为 0,地址为2×2K+0,答案为B。
减少指令执行周期数是RISC计算机性能提高的基础,它是通过 46 、指令控制部件 47 微代码和 48 等来实现的。 现需要一个32M×8规格的存储器,现只有规格为1M×8的存储器芯片,则需要 49 个这样的存储器芯片。 存储芯片的地址长度需要 50 位,主存储器的地址长度需要 51 位。 有一矩阵“int a[50][50]”以行为序进行存储,有一个虚拟存储系统,物理内存共有 3页,其中1页用来存放程序,其余2页用于存放数据。假设程序已在内存中占1页,其余 2页空闲。 程序A: for(i=0; i<=49;i++) for(j=0; j<=49;j++) A[i][j]=0; 程序B: for(i=0; i<=49; i++) for(j=0; j<=49; j++) A[i][j]=0; 若每页可存放50个整数,执行程序A会发生 52 次缺页,执行程序B会发生 53 次缺页。 某仓库有两名发货员,一名审核员。当顾客提货时,只要发货员空闲,允许顾客进入仓库提货,顾客离开时,审核员检验顾客提货是否正确。其工作流程如图13-15所示。为了利用PV操作正确地协调他们之间的工作,设置了两个信号量S1和S2,且S1的初值为 2,S2的初值为1。图中的a应填写 54 ;图中的b、c和d应分别填写 55 。 在主机控制下进行的输入/输出操作称为 58 操作,在外围机控制下进行的输入/输出操作称为 59 。 61. 设关系R和S的属性个数为3和5,那么
与
等价。
A.π2 <4(R×S) B.π2 <7(R×S) C.σ2 <4(R×S) D.σ2 <7(R×S)
A B C D
D
此题主要考察两个知识点。一个是区别投影操作和选择操作。
①选择:从关系中找出满足给定条件的所有元组,其中的条件是以逻辑表达式给出的,该逻辑表达式的值为真的元组被选取。这是从行的角度进行的运算,即水平方向抽取元组。经过选择运算得到的结果元组可以形成新的关系,其关系模式不变,但其中元组的数目小于等于原关系中元组的数目,它是原关系的一个子集。
选择运算记为σ
F (R),其中R为一个关系,F是布尔函数,该函数可以包含比较运算符 (<、=、>、≤、≥、≠)和逻辑运算符(∧、∨、┒)。
②投影:从关系中挑选若干属性组成新的关系。这是从列的角度进行的运算,相当于对关系进行垂直分解。投影可以得到一个新关系,其关系所包含的属性个数往往比原关系少,或者属性的排列顺序不同。如果新关系中包含重复元组,则要删除重复元组。
投影运算记为π
X (R),其中R是一个关系,X是一组属性名或属性序号组,属性序号是对应属性在关系中的顺序编号。
本题中的自然连接
的作用是选出R关系中第2列元素小于S中第4列元素的记录,所以应用选择,此时我们可以排除答案A和B。
考察的第二个知识点就是6连接与笛卡儿操作有何关系。θ连接的定义如下:
这里,r是关系R的元数。所以θ连接条件2<4,在笛卡儿积中应改为2<7,所以答案应为D。
给定关系模式R(U,F),U={A,B,C,D,E,F},F={B→F,D→A,A→E, AE→B},那么属性A的闭包为 62 ,R的候选关键字为 63 。 职员关系模式为E(Eno,Ename,Dept,Eage,Eaddr),其中Eno表示职员号,Ename表示职员名,Dept表示职员所在部门,Eage表示年龄,Eaddr表示职员的家庭住址。建立“开发部”职员的视图DS_E(DS表示开发部)如下,要求进行修改、插入操作时保证该视图只有开发部的职员。 CREATE VIEW DS_E AS SELECT Eno,Ename,Dept,Eage,Eaddr FROM E WHERE 64 如下SQL语句可以查询开发部姓“王”职员的姓名和家庭住址。 SelectEname,Eaddr From DS_E Where 65 ; 若视频图像每帧的数据量为8.4 MB,帧速率为25帧/秒,则显示10 s的视频信息,其原始数据量为 67 MB。考虑存储和传输的要求,可使用 68 标准对原始视频进行有效的压缩。 XP is 71 of interesting twists that encourage one to think--for example, how about "Test and then code"? I've worked with software companies and a few IT organizations in 72 programmer performance was measured on lines of code delivered and testing was measured on defects found-- 73 side was motivated to reduce the number of defects prior to testing. XP uses two types of testing: unit and functional. 74 , the practice for unit testing involves developing the test for the feature prior to writing the code and further states that the tests should be automated. Once the code is written, it is immediately 75 to the test suite bringing instant feedback.