1、软件水平考试（中级）软件设计师上午（基础知识）试题模拟试卷 68及答案与解析 1 系统 “抖动 ”现象的发生是由 _引起的。 （ A）置换算法选择不当 （ B）交换的信息量过大 （ C）内存容量不足 （ D）请求页式管理方案 2 下列是关于缓冲技术的说法： 引入缓冲技术的主要原因包括：缓和 CPU与I/O设备之间速度不匹配的矛盾；减少对 CPU的中断频率；放宽对中断响应时间的限制；提高 CPU和 I/O设备之间的并行性。 一般从磁盘中开辟一块区域作为缓冲区。 缓冲可分为单缓冲、双缓 冲和循环缓冲。 Spooling系统用到了缓冲技术。 其中正确的有 _个。 （ A） 0 （ B） 1 （ C）
2、 2 （ D） 3 3 已知有 n个进程共享一个互斥段，如果最多允许 m个进程 (m n)同时进入互斥段，则信号量的变化范围是 _。 （ A） -m 1 （ B） -m 0 （ C） -(n-m) m （ D） -(m-1) n 4 若对象 A可以给对象 B发送消息，那么 (6)。 （ A）对象 B可以看见对象 A （ B）对象 A可看见对象 B （ C）对象 A， B相互不可见 （ D）对象 A， B相互可见 5 在面向对象软件开发过程中，采用设计模式 (44)。 （ A）允许在非面向对象程序设计语言中使用面向对象的概念 （ B）以复用成功的设计和体系结构 （ C）以减少设计过程创建的类的个
3、数 （ D）以保证程序的运行速度达到最优值 6 由权值为 9， 2， 5， 7的四个叶子构造一棵哈夫曼树，该树的带权路径长度为(13)。 （ A） 23 （ B） 37 （ C） 44 （ D） 46 7 关系模式 R(S， T， J)中，每个属性均不可分，存在函数依赖有： (S， J)T ，(S， T)J ， TJ ，则下述说法正确的 是 _。 （ A）关系模式 R满足 1NF，但不满足 2NF （ B）关系模式 R满足 2NF，但不满足 3NF （ C）关系模式 R满足 3NF，但不满足 BCNF （ D）关系模式 R满足 BCNF，但不满足 4NF 8 一棵树高为 k的完全二叉树至少有
4、_个结点。 （ A） 2k-1 （ B） 2k-1-1 （ C） 2k-1 （ D） 2k 9 已知一个线性表 (38， 25， 74， 63， 52， 48)，假定采用散列函数 h(key)=key%7计算散列地址，并散列存储在散列表 A06 中，若采用线性探测方法解决冲 突，则在该散列表上进行等概率成功查找的平均查找长度为 (50)。 （ A） 1.5 （ B） 1.7 （ C） 2 （ D） 2.3 10 利用逐点插入建立序列 (50， 72， 43， 85， 75， 20， 35， 45， 65， 30)对应的二叉排序树以后，查找元素 30要进行 (57)次元素间的比较。 （ A） 4
5、 （ B） 5 （ C） 6 （ D） 7 11 对于二维数组 a0 4,1 5，设每个元素占 1个存储单元，且以列为主序存储，则元素 a2,2相对于数组空间起始地址的偏移量是 _。 （ A） 5 （ B） 7 （ C） 10 （ D） 15 12 页式存储系统的逻辑地址是由页号和页内地址两部分组成的。假定页面的大小为 4KB，地址变换过程如图 3-8所示，图中逻辑地址用十进制数表示。图中有效地址经过变换后，十进制数物理地址 a应为 _。 （ A） 33220 （ B） 8644 （ C） 4548 （ D） 2500 13 在 UNIX操作系统中，当用户执行如下命令 Link(“/user/
6、include/myfile.sh“，“/usr/userwang/youfile.sh“)则文件名 “/usr/userwang/youfile.sh“存放在 _。 （ A） user目录文件中 （ B） include目录文件中 （ C） userwang目录文件中 （ D） youfile.sh的文件内容中 14 若指令流水线把一条指令分为取指、分析和执行三部分，月 -三部分的时间分别是， t取指 =2ns， t分析 =2ns， t执行 =1ns。则 100条指令全部执行完毕需 _ ns。 （ A） 163 （ B） 183 （ C） 193 （ D） 203 15 下面函数中渐进时间最
7、小的是 _。 （ A） T1(n)=n+nlogn （ B） T2(n)=2n+nlogn （ C） T3(n)=n2-logn （ D） T3(n)=n+100logn 16 按制定标准的不同层次和适应范围，标准可分为国际标准、国家标准、行业标准和企业标准等， (9)制定的标准是国际标准。 （ A） ISO和 IEC （ B） ISO和 IEEE （ C） ANSI和 ISO （ D） IEEE和 GJB 17 在 CCITT建议的 E1载波中，每一帧包含 (64)位。 （ A） 254 （ B） 255 （ C） 256 （ D） 257 18 准确地解决 “软件系统必 须做什么 ”是 (
8、14)阶段的任务。 （ A）可行性研究 （ B）详细设计 （ C）需求分析 （ D）编码 19 某系统中有 3个并发进程，都需要同类资源 4个，试问该系统不会发生死锁的最少资源数是 (32)。 （ A） 9 （ B） 10 （ C） 11 （ D） 12 20 对序列 49， 38， 65， 97， 76， 13， 27， 50采用快速排序方法进行排序，以第一个元素为基准元素得到的划分结果是 (55)。 （ A） 13， 27， 38， 49， 76， 97， 65， 50 （ B） 27， 38， 13， 49， 76， 97， 65， 50 （ C） 27， 38， 13， 49， 50，
9、 76， 65， 97 （ D） 27， 13， 38， 49， 76， 97， 65， 50 21 在软件的可行性研究牛，可以从不同的角度对进行研究，其中是从软件的功能可行性角度考虑的是 (16)。 （ A）经济可行性 （ B）技术可行性 （ C）操作可行性 （ D）法律可行性 22 当数据分组从低层向高层传送时，分组的头要被 (28)。 （ A）加上 （ B）去掉 （ C）重新处置 （ D）修改 23 已知一个线性表 (38， 25， 74， 63， 52， 48)，假定采用 h(k)=k%6计算散列地址进行散列存储，若用线性探测的开放定址法处理冲突，则在该散列表上进行查找的平均查找长度为
10、 (44)。 （ A） 1.5 （ B） 1.7 （ C） 2 （ D） 2.3 24 假定磁盘块的大小为 1KB，对于 16GB的硬盘，其文件分配表 FAT需要占用的存储空间为 (18)。 （ A） 12M （ B） 24M （ C） 48M （ D） 96M 25 假设 个有 n个顶点和 e条弧的有向图用邻接表表示，则删除与某个顶点 vi(下标 )相关的所有弧的时间复杂度是 (55)。 （ A） O(n) （ B） O(e) （ C） O(n+e) （ D） O(n*e) 26 若项目集 IK含有 A. ，则在状态 k时，仅当面临的输入符号 a FOLLOW(A)时，才采取 “A.” 动作
11、的一定是 (19)。 （ A） LALR 文法 （ B） LR(0)文法 （ C） CLR(1)文法 （ D） SLR(1)文法 27 进程 P通过缓冲区 K不断向 n个进程 Qi(1in)发送消息，消息大小与缓冲区 K一样。为了使每个接收进程都应该接收到与发送次序一样的消息序列，需要配置(23)。 （ A） 2个信号量，初值分别为 1， 0 （ B） 2个信号量，初值分别为 1， n， （ C） 3个信号量，初值分别为 1， 0， 0 （ D） 3个信号量，初值分别为 1， 1， 0 28 yacc是一个生成编译程序的工具，它的输入是文法 G的产生式规则，它的输出是文法 G的 (29)。 （
12、 A）优先分析器 （ B） LL(1)分析器 （ C） LR(1)分析器 （ D） LALR(1)分析器 29 JPEG静态图像编码是 (36)。 （ A）有损数据压缩编码 （ B）无损数据压缩编码 （ C）不压缩数据的编码 （ D）通道 (或称信道 )编码 30 某软件公司出资、组织、并安排公司的研发人员具体开发了一 套人事方面的管理软件，由该软件公司对开发完成的软件承担责任。该软件的开发者是 (21)。 （ A）公司的员工为软件的开发者 （ B）公司的员工为开发者，公司视为作者 （ C）软件公司是软件的开发者 （ D）软件公司和研发人员是软件的共同开发者 31 已知 G4=(VTa， ，
13、， (， )， VN=S,L， L， S,P)，其中 P为， S(L)|a| LSL L ， SL| FOLLOW(S)是 (29)。 （ A） ， ， ， （ B） ， #， （ C） a， ， ， （ D） a， ， ， # 32 已知 G4=(VTa， ， ， (， )， VN=S， L， L， S,P)，其中 P为， S(L) a LSL L,SL FIRST(SL)是 (29)。 （ A） ,， （ B） (， a （ C） (， a， ,) （ D） (， a， , ， ) 33 在 MPEG-1 Video压缩标准中定义 了 I、 P、 B图像，如果要使运动速度极快的影视 (例如
14、飞机翻跟斗 )不模糊，需要 (39)。 （ A）增加 I图像的帧数 /秒 （ B）增加 P图像的帧数 /秒 （ C）增加 B图像的帧数 /秒 （ D）使用其他技术 34 文法 GS： SxSx|y 所描述的语言是 _(n0)。 （ A） (xyx)n （ B） xyxn （ C） xynx （ D） xnyxn 35 从基本的 CPU工作原理来看，若 CPU执行 MOV R1， R0指令 (即将寄存器R0的内容传送到寄存器 R1中 )，则 CPU首先要完成的操作是 _(其 中 PC为程序计数器； M为主存储器； DR为数据寄存器； IR 为指令寄存器； AR为地址寄存器 )。 （ A） (R0
15、)R1 （ B） PCAR （ C） MDR （ D） DRIR 36 甲、乙两人在同一时间就同样的发明创造提交了专利申请，专利局将分别向各申请人通报有关情况，并提出多种解决这一问题的办法，不可能采用 (21)的办法。 （ A）两申请人作为一件申请的共同申请人 （ B）其中一方放弃权利并从另一方得到适当的补偿 （ C）两件申请都不授予专利权 （ D）两件申请都授予专利权 37 我国著作权法中， (12)系指同一概念。 （ A）出版权与版权 （ B）著作权与版权 （ C）作者权与专有权 （ D）发行权与版权 38 要在网络上发布彩色动画文件，可以采用的存储格式是 (59)。 （ A） BMP （
16、 B） JPEG （ C） MP3 （ D） GIF 39 某计算机系统由下图所示的部件构成，假定每个部件的千小时可靠度 R均为0.9，则该系统的千小时可靠度约为 (2)。 （ A） 0.882 （ B） 0.951 （ C） 0.9 （ D） 0.99 40 指令流水线将一条指令的执行过程分为四步，其中第 1、 2和 4步的经 过时间为 t，如下图所示。若该流水线顺序执行 50条指令共用 153 t，并且不考虑相关问题，则该流水线的瓶颈第 3步的时间为 (5) t。 （ A） 2 （ B） 3 （ C） 4 （ D） 5 41 在面向对象的语言中， (21)。 （ A）类的实例化是指对类的实
17、例分配存储空间 （ B）每个类都必须创建一个实例 （ C）每个类只能创建一个实例 （ D）类的实例化是指对类进行初始化 42 在 Windows操作系统中，采用 (69)命令来测试到达目标所经过的路由器数目及IP 地址。 （ A） ping （ B） tracert （ C） arp （ D） nslookup 43 编译器对高级语言源程序的处理过程可以划分为词法分析、语法分析、语义分析、中间代码生成、代码优化、目标代码生成等几个阶段，其中， (20)并不是每种编译器都必需的。 （ A）词法分析和语法分析 （ B）语义分析和中间代码生成 （ C）中间代码生成和代码优化 （ D）代码优化和目标代
18、码生成 44 用户可以通过 http： /和 http： /访问在同一台服务器上(70)不同的两个 Web站点。 （ A） IP 地址 （ B）端 口号 （ C）协议 （ D）虚拟目录 45 下面关于栈和队列的叙述，错误的是 ( )。 （ A）栈和队列都是操作受限的线性表 （ B）队列采用单循环链表存储时，只需设置队尾指针就可使入队和出队操作的时间复杂度都为 O(1) （ C）若队列的数据规模 n可以确定，则采用顺序存储结构比链式存储结构效率更高 （ D）利用两个栈可以模拟一个队列的操作，反之亦可 46 QHTML元素中， ( )属性用于定义超链接被鼠标点击后所显示的颜色。 （ A） alin
19、k （ B） background （ C） bgcolor （ D） vlink 47 以下关于面向对象设计的叙述中，错误的是 ( )。 （ A）高层模块不应该依赖于底层模块 （ B）抽象不应该依赖于细节 （ C）细节可以依赖于抽象 （ D）高层模块无法不依赖于底层模块 48 需求分析的任务是借助于当前系统的物理模型导出目标系统的逻辑模型，解决目标系统 “做什么 ”的问题。 (16)并不是需求分析的实现步骤之一。 （ A）获得当前系统的物理模型 （ B）抽象出当前系统的逻辑模型 （ C）建立目标系统的逻辑模型 （ D）建立目标系统的物理模型 49 某 幅图像具有 640480个像素点，若每个
20、像素具有 8位的颜色深度，经 5： 1压缩后，其图像数据需占用的存储空间为 (14)字节。 （ A） 61440 （ B） 307200 （ C） 384000 （ D） 3072000 50 程序语言的大多数语法现象可用上下文无关文法描述。对于一个上下文无关文法 G=(N,T,P,S)，其中 N是非终结符号的集合， T是终结符号的集合， P是产生式集合， S是开始符号。令集合 V=N T，那么 G所描述的语言是 (29)的集合。 （ A）从 S出发推导出的包含 V中所有符号的串 （ B） T中所有符 号组成的串 （ C） N中所有符号组成的串 （ D）从 S出发推导出的仅包含 T中符号的串
21、51 某 C语言子程序如下。 其中 x， y是两个已定义的整型变量。表 2-4给出了可供选择的 4组测试数据组，则实现条件覆盖至少应采用的测试数据组是 (31)。（ A） 和 组 （ B） 、 和 组 （ C） 、 和 组 （ D） 、 和 组 52 CMM模型将软件过程的成熟度分为 5个等级。属于 4级以上的关键过程域是(34)。 （ A）软件配置管理 （ B）集成软件管理 （ C）软件产品工程 （ D）软件质量管理 53 为实现图像信息的压缩，建立了若干种国际标准。其中，既是 DVD的标准，也是高清晰度电视 (HDTV)的标准是 (14)。 （ A） MPEG-1 （ B） MPEG-2
22、（ C） MPEG-4 （ D） MPEG-7 54 关于诊疗科、医师、患者和治疗观察关系模式如下所示，其中带实下画线的表示主键，虚下画线的表示外键，双下画线的表示既是主键又是外键。 诊疗科 (诊疗科代码，诊疗科名称 ) 医师 (医师代码，医师姓名，诊疗科代码 ) 患者 (患者编号，患者姓名 ) 治疗观察 (医师代码，患者编号 ) (55)表示上述关系模式的 E-R图 。图中 * *、 1 *和 1 1分别表示多对多、 1对多和 1对 1的联系。55 若需将一个栈 S中的元素逆置，则以下处理方式中正确的是 (63)。 （ A）将栈 S中元素依次出栈并入栈 T，然后将栈 T中元素依次出栈并进入栈
23、 S （ B）直接交换栈顶元素和栈底元素 （ C）将栈 S中元素依次出栈并入队，然后使该队列元素依次出队并进入栈 S （ D）直接交换栈顶指针和栈底指针 56 某软件开发从详细设计到集成测试各阶段所需的工作量估计 (按软件工程师人月数估计 )如表 5-1所示，这几个阶段分配的软件工程师和程序员人数如表 5-2所示。假设编码与单元测试阶段，软件工程师的生产率是程序员的 2倍。若在该项目的这几个阶段都增加一名软件工程师，并假定各个开发阶段串行工作，则这几个阶段可以缩短 (35)个月完成任务。（ A） 1.2 （ B） 2.8 （ C） 3.6 （ D） 4.2 57 (24)操作需要特权指令执行。
24、 （ A）读取当前日期 （ B）消除一块内存 （ C）关闭中断 （ D）存取某地址单元的内容 58 若某个计算机系统中，内存地址与 I/O地址统一编址，访问内存单元和 I/O设备是靠 _采区分的。 A数据总线上输出的 数据 B不同的地址代码 C内存与 I/O设备使用不同的地址总线 D不同的指令 59 设有下面 4条路由： 172.30.129.0/24、 172.30.130.0/24、 172.30.132.0/24和172.30.133/24，如果进行路由汇聚，能覆盖这 4条路由的地址是 (68)。 （ A） 172.30.128.0/21 （ B） 172.30.128.0/22 （ C
25、） 172.30.130.0/22 （ D） 172.30.132.0/23 60 已知 RSA算法公钥是 (e=7， n=20)，私钥是 (d=3， n=20)，如果接到的密文 C=7加密，则解密后的明文是 (69)。 （ A） 3 （ B） 4 （ C） 343 （ D） 823543 61 全双工以太网传输技术的特点是 _。 （ A）能同时发送和接收帧、不受 CSMA/CD限制 （ B）能同时发送和接收帧、受 CSMA/CD限制 （ C）不能同时发送和接收帧、不受 CSMA/CD限制 （ D）不能同时发送和接收帧、受 CSMA/CD限制 62 已知关系 R、 S，如图 13-1所示。 那
26、么 RS的结果是 (21)。 （ A） a1 （ B） a2 （ C） a3 （ D） a1 63 (49)语言不是面向对象的程序设计语言。 （ A） Java （ B） C+ （ C） Smalltalk （ D） Fortran77 64 设输入序列为 1、 2、 3、 4、 5，依次执行进栈、进栈、进栈、出栈、进栈、进栈、出栈、出栈，则栈顶栈底分别是 _。 （ A） 5和 4 （ B） 4和 3 （ C） 3和 2 （ D） 2和 1 65 下列地址中， _是一个合法的单播地址。 （ A） 192.168.24.59/30 （ B） 255.255.255.255 （ C） 172.31
27、.128.255/18 （ D） 224.1.5.2 66 某完全二叉树层序序列为 ABCDEF，则该完全二叉树的中序序列为 _。 （ A） DBEAFC （ B） DEBFCA （ C） DEBCFA （ D） DBEACF 67 要使 4个连续的 C类网络汇聚成一个超网，则子网掩码应该为 _。 （ A） 255.240.0.0 （ B） 255.255.0.0 （ C） 255.255.252.0 （ D） 255.255.255.252 68 软件能力成熟度模型 (CMM)将软件能力成熟度自 低到高依次划分为初始级、可重复级、定义级、管理级和优化级。其中 (29)对软件过程和产品都有定量
28、的理解与控制。 （ A）可重复级和定义级 （ B）定义级和管理级 （ C）管理级和优化级 （ D）定义级、管理级和优化级 69 UP(统一过程 )是用例驱动的、以架构为核心、迭代和增量的软件过程框架，它提供了一种 (32)的特性。 （ A）演进 （ B）敏捷 （ C）测试驱动 （ D）持续集成 70 使用白盒测试方法时，应根据 (17)和指定的覆盖标准确定测试数据。 （ A）程序的内部逻辑 （ B）程序结构的复杂 性 （ C）使用说明书 （ D）程序的功能 71 Sequential circuit is a common logic device whose output values, a
29、t a given instant, depend upon its input values and the internal state at that instant, and whose internal state depends upon the(66)preceding input values and the preceding internal state. A sequential circuit can assume a finite number of internal states and may therefore be regarded, from an abst
30、ract(67), as a finite(68).Combinational circuit is another logic device whose output values, at any given instant, depend upon the input values at that instant. A combinational circuit is a(69)of a sequential circuit whose internal state is not taken(70). （ A） directly （ B） immediately （ C） instantl
31、y （ D） snapshot （ A） idea （ B） observation （ C） point of view （ D） viewport （ A） automaton （ B） robot （ C） manipulator （ D） man-machine system （ A） counterexample （ B） specification （ C） particular （ D） special case （ A） calculation （ B） in account （ C） audit （ D） attention 一、主观题 76 阅读下列说明和有关的图表，回答问
32、题 1至问题 3。 【说明】 A公司决定为该市车站开发自动售票系统，系统的要求如下： (1)乘客能按以 下 3步操作购票：选定目的地；投入钱币；获得一张票； (2)当且仅当乘客选定目的地后，系统才接收受投钱；每次投入的钱只购买一张票； (3)只要投入的钱不少于所需的票价，且票库中有所要求的票，则应尽快出票； (4)如需找钱，则应在出票的同时退还多余的钱； (5)如果乘客投入的钱不够票价，或者票库中没有所要求的票时，系统将全额退钱，并允许乘客另选目的地，继续购票； (6)出票前乘客可以按 取消 按钮取消购票，系统将全额退出该乘客投入的钱，并允许乘客另选目的地，继续购票； (7)出票结束 (包括退
33、还多余的钱 )后，系统 应保存销售记录，并等待乘客购票。 该系统还要求快速响应和操作同步，所以它应是一个实时系统。为此， A公司在该系统的数据流程图中附加了过程控制部分，形成转换图。在该图中，控制流 (事件流 )用虚线表示，数据流用实线表示。图中的数据流并没有画全，需要考生填补。转换图如图 1-14所示。 对售票全过程进行的控制可以用系统内部各个状态之间的迁移来描述，从而形成状态迁移图。在状态迁移图中，用双线框表示状态，用有向边表示状态的迁移。引起状态迁移的事件及由该事件引起的动作，在有向边旁用 “ ”形式注明。状态迁移图如图1-15所示 。 该公司还制作了一个过程启动表，用以表明状态迁移图中
34、的 4个动作与转换图中的 4个过程之间的 “启动 ”关系，即说明哪个动作将启动哪个过程。用 1表示启动，用 0表示不启动。启动的过程将根据获得的输入数据产生输出数据，未启动的过程则不会产生输出数据。该表中没有列出的过程，其执行与否与事件无关。过程启动表如表 1-2所示。76 转换图中缺少哪 3条数据流 ?请指明每条数据流的名称、起点和终点。 77 在状态迁移图中， a、 b、 c分别表示什么事件 ?请用转换图中给出的事件名解答。 78 在过程启动表中， d、 e处应 填什么 ?请分别用 4位二进制码表示。 软件水平考试（中级）软件设计师上午（基础知识）试题模拟试卷 68答案与解析 1 【正确答
35、案】 A 【试题解析】 导致页面频繁调入 /调出 (即抖动 )的根本原因是置换算法不当。 2 【正确答案】 D 【试题解析】 在现代 OS中，几乎所有的 I/O设备都使用了缓冲区，因为要提高I/O 速度和设备的利用率，在很大程度上都需要借助缓冲技术来实现。缓冲区是操作系统为暂存数据而在内存中开辟的一块区域。缓冲可分为单缓冲、双缓冲和循环缓冲，如图 6-41所示。 引入缓冲技术的主要 原因有：缓和 CPU与 I/O 设备之间速度不匹配的矛盾；减少对 CPU的中断频率；放宽对中断响应时间的限制；提高 CPU和 I/O 设备之间的并行性；提高外设利用率，尽可能使外设处于忙状态。 根据实现方式的不同，
36、缓冲技术可分为硬件缓冲和软件缓冲，硬件缓冲是利用专门的硬件寄存器作为缓冲，而软件缓冲则是通过操作系统来实现的。 Spooling系统用到了缓冲技术，它用到了两个缓冲区：输入缓冲区和输出缓冲区。前者暂存由输入设备送来的数据，以后再传送到输入井；后者暂存从输出井送来的数据，以后再传送给输出设备。 3 【正确答案 】 C 【试题解析】 当没有进程使用互斥段时，可以让 m个进程同时进入，表明有 m个资源可用，于是信号量的上限为 m。当 m个进程都进入之后，如果剩余的 n-m个进程也请求进入互斥段，那么信号量的值就为 -(n-m)，表示有 n-m个进程在等待该资源。 4 【正确答案】 B 【试题解析】
37、消息的对象间通信中指一个对象通过向另一对象发送消息来请求其服务。一个消息通常包括接收对象名、调用的操作名和适当的参数 (如有必要 )。消息只告诉接收对象需要完成什么操作，但并不能指示接收者怎样完成操作。消息完全向接收者解释， 接收者独立决定采用什么方法来完成所需的操作。因此， A可以看见 B， B不一定能看见 A。 5 【正确答案】 B 【试题解析】 采用设计模式可复用面向对象软件的基础来构造可复用的面向对象设计。设计模式确定了所包含的类和实例，它们的角色、协作方式以及职责分配。每一个设计模式都集中于一个特定的面向对象设计问题或设计要点，描述了什么时候使用它，在另一些设计约束条件下是否还能使用
38、，以及使用的效果和如何取舍。 6 【正确答案】 C 【试题解析】 哈夫曼树的形状如图 8-4所示。 该树的带权路径长度 =91+72+23+53=44 7 【正确答案】 C 【试题解析】 此题最大的陷阱就是 “(S， T)J ， TJ” ，有些读者一看到这种形式，就立即做出判断 “这个关系不满足 2NF，因为它存在部分函数依赖 ”。但这种断定是错误的，因为他们忘记了一个重要的前提，那就是： 2NF要求每一个 “非主属性 ”完全函数依赖于码。该关系模式的候选码是 (S， J)和 (S， T)，所有的属性都是主属性，所有该关系模式至少是 3NF，又因为 TJ 的左部未包含该关系的某一候选码，所以它
39、不是 BCNF。正确答案应为 C。 8 【正确答案】 C 【试题解析】 一棵高为 k 的完全二叉树，当第 k 层只有最左边一个结点时具有最少的结点。根据二叉树的性质，第 1层到第 k-1层共有结点 2k-1-1个，因此它至少有 2k-1-1+1=2k-1个结点。 9 【正确答案】 C 【试题解析】 按照散列函数 h(key)： key%7和线性探测方法解决冲突，将线性表(38,25,74,63,52,48)散列存储在散列表 A06 中，如图 8-10所示。10 【正确答案】 B 【试题解析】 利用逐点插入法建立二叉树是从空树开始，通过查找将每个节点作为一个叶子插入。 按上述次序建立的二叉排序树如图 8-11所示。11 【正确答案】 B 【试题解析】 此类题型以前考过多次，为了让大家能更好地理解题目的意思以及解题的思想，图 3-81给出了二维数组 a0 4, 1 5的结构。因为以列为主序存储，所以 a0, 1存储在 1号存储单元， a1, 1存储在 2号存储单元 以此类推， a2, 2
