【软件设计师】知识点与试题

http://edu.csai.cn/zt/ztda/


2010 ， 下
上 http://training.51cto.com/art/201011/230700.htm(试题)
http://training.51cto.com/art/201011/232662.htm(答案)

下 http://training.51cto.com/art/201011/231194.htm

存储器的组成？
2K*4 的存储器芯片组成 16K*8的存储器， 如何编址？
1.DMA
Direct Memory Access(存储器直接存储)
这是指一种高速的数据传输操作，允许在外部设备和存储器之间直接读写数据，既不通过CPU，也不需要CPU干预。整个数据传输操作在一个称为"DMA控制器"的控制下进行的。CPU除了在数据传输开始和结束时做一点处理外，在传输过程中CPU可以进行其他的工作。这样，在大部分时间里，CPU和输入输出都处于并行操作。因此，使整个计算机系统的效率大大提高。

2.字长是CPU的主要技术指标之一
指的是CPU一次能并行处理的二进制位数

3.某计算机的字长是32位，其内存容量是1GB，若内存空间按字编址，那么其地址范围是？
某计算机的字长是32位（4个字节）；
其内存容量是1GB，按字编址，那么就是 (1/4)G = 256M。

256M 即为 256 * 1024 * 1024；
需用地址线：8条、10条、10条，共28条地址线。
地址共有 28 位二进制数，写成16进制，就是 7 位数。

所以本题的正确答案是：A. 0000000～FFFFFFF

4. ARP: 地址解析协议

5.一个含有n个顶点和e条边的简单无向图，在其邻接矩阵存储结构中共有__(6)__个零元素。
(6)A．e B．2e C．n2-e D．n2-2e

6. 具有最小带权路径长度的二叉树称作哈夫曼树，即最优二叉树

7. 结点的度， 结点所拥有的子节点的个数

8. 树的度和图的度（入度 出度）

9. 前序遍历也叫做先根遍历、先序遍历，可记做根左右。
　 中序遍历，也叫中根遍历，顺序是 左子树，根，右子树
后序遍历，也叫后根遍历，遍历顺序，左子树，右子树，根

10.
设顺序存储的某线性表共有123个元素，按分块查找的要求等分为3块。若对索引表采用顺序查找方法来确定子块，且在确定的子块中也采用顺序查找方法，则在等概率的情况下，分块查找成功的平均查找长度为__(11)__。
123个元素分成A\B\C三块，每块41个元素

对于A块里面的元素，查找过程的第一步是首先找到A块，再在A块中找到某个元素

由于是顺序查找，找到A块只需一步

然后再在A块中查找指定元素
由于是顺序查找，因此找到第一个元素需要一步，找到第二个元素需要2步
一次类推，找到第41个元素需要41步

因此，A块中个元素查找长度之分别为2，3，4，···42

对于B块，原理一样，但是找到B块本身需要比找到A块多一步，因为是顺序查找
因此，B块中各个元素查找长度为3，4，5，···43

同理，C块中各个元素查找长度为4，5，6，···44

所以平均查找长度为
2+3+3+...+42
+3+4+5+...+43
+4+5+6+...+44
再除以元素总数123
最后结果是23

11.

CBFFFH(835583)-A4000H(671744)+1=28000H(163840)


按字节编址=>一个存储单元大小是1B 1个字节

A4000H和CBFFFH都是表示十六进制的数据，H表示的就是十六进制，所以A4000H到CBFFFH共有的字节数为:CBFFFH(835583)-A4000H(671744)+1=28000H(163840),些等式中尾数为H的表示十六进制数，而括号中的数是其相应的十进制数，所以它们中间共有163840个字节，而163840/1024=160,从而得出A4000H到CBFFFH中共有 160*1024个字节。

将大地址加上1就等于CC000H,再将大地址减去小地址,即为:
CC000H-A4000H=28000H (12-10=2, 12-4=8)
H代表16进制

大写B表示Byte，小写b表示bit。So，1B=8b

12.
中断响应时间是指：
从发出中断请求到进入中断处理所用的时间

13.
单指令流多数据流计算机(Single Instrtuction Multiple Data，SIMD)是指由一个控制部件和多个处理单元同时完成一条指令的执行。因此，SIMD以同步方式，在同一时间内执行同一条指令。

14.首先来了解一下磁记录原理。磁记录数据时磁表面存储器是通过磁头来进行读写的。磁头线圈中通入一定方向和大小的脉冲电流，磁化磁头的导磁体，从而建立起一定方向和强度的磁场。当磁介质从磁头下经过时，从磁头间隙处将其磁化。由于剩磁效应的存在，当磁场消失后，磁介质表面仍存在剩磁。线圈中电流方向不同，磁介质上被磁化的方向不同，用以代表"1"和"0"。随着电流的变化以及磁介质磁头间的相对运动，就可以把二进制信息序列转化为介质表面的磁化单元序列。读出过程则是逆过程，即把记录的磁化单元序列还原成电流脉冲序列。因此，不难得出答案：单个磁头在向盘片的磁性涂层上写入数据时，是以串行方式写入的。

15.
容量为64块的Cache采用组相联方式映像，字块大小为128字节，每4块为一组，若主容量为4096块，且以字编址，那么主存地址为（____）位，主存区号为（____）位。

解：

组相联的地址构成为：区号+组号+块号+块内地址。

主存的每个分区大小与整个Cache大小相等，故此主存需要分的区数为：4096/64=64，因为26＝64，因此需要6位来表示区号。

每4块为一组，故共有组数 64/4 = 16 ，因为24＝16，因此需要4位表示组号。

每组4块，故表示块号需要2位。

块内地址共128字节，27＝128，所以块内地需要7位表示。

所以：主存地址的位数＝6+4+2+7 ＝ 19

主存区号的位数＝6

16.DFD-->Data Flow Diagram 数据流图
：箭头，表示数据流；
〇：圆或椭圆，表示加工；
=：双杠(带一边开口,一边闭合)，表示数据存储；
□：方框，表示数据的源点或终点。

17.
路径测试的英文是path testing，是指根据路径设计测试用例的一种技术，经常用于状态转换测试中。

基本路径测试法是在程序控制流图的基础上，通过分析控制构造的环路复杂性，导出基本可执行路径集合，从而设计测试用例的方法。设计出的测试用例要保证在测试中程序的每个可执行语句至少执行一次。

18.项目管理工具
Gantt图：是用图形(特别是条形图)描述项目进度的图表。每一个条形符号代表不同的意义。例如，关键任务的条形符号或颜色可能与非关键任务的不同。概要任务(活动或阶段)的符号可能与其他任务不同。
Pert图：用流程图来表示所有任务的现行依赖关系。Pert的意思是计划评价与审查技术，是一种网络图。
项目管理工具通常都支持PERT和Gantt图。 PERT是计划评价与评审技术。该技术把网络方法用于工作计划安排的评审和检查。通常以带箭头的边表示活动，边的起讫结点表示活动的开始事件和结束事件，边的长度表示该活动的工作量或工期，各结点的顺序反映了各个活动在时序上的制约关系。利用PERT的网络图能求出关键路径和松弛时间，并能对计划的各个活动和资源分配等进行调整。 Gantt图是一种二维横道图，它广泛用于各种工程活动的进度计划管理。图的横坐标为时间轴，每个活动用一条水平线段表示，其起讫点对应的横坐标值即为该活动的开始和结束时间。尽管新的项目管理方法和技术会改变人们已经习惯的工作方式，学习和掌握新工具也要花费一些时间，但是使用自动项目管理工具比用手工方法管理有许多优点

19.加工逻辑可以用结构化语言、判定表、判定树等多种形式表示，也可将它们结合起来表示。

20. 面向对象开发方法（ObjectOriented，OO）又称：快速原型法

21. 要把数据流图（DFD）转化为软件结构，首先必须研究DFD的类型。各种软件系统，不论DFD如何庞大和复杂，一般可分为变换型和事务型。
变换型的DFD是由输入、变换和输出组成，变换型数据处理的工作过程一般分为三步：取得数据、变换数据和给出数据，这三步体现了变换型DFD的基本思想。变换是系统的主加工，变换输入端的数据流为系统的逻辑输入，输出端为逻辑输出
若某个加工将它的输入流分离成许多发散的数据流，形成许多加工路径，并根据输入的值选择其中一条路径来执行，这种特征的DFD称为事务型的数据流图，这个加工称为事务处理中心

22. http://technet.microsoft.com/zh-cn/library/cc771298(WS.10).aspx
vpn中的隧道是由隧道协议形成的，vpn使用的隧道协议主要有三种：点到点隧道协议（pptp）、第二层隧道协议（l2tp）以及ipsec。

23.
在UNIX操作系统中，若用户键入的命令参数的个数为1时，执行cat $1命令；若用户键入的命令参数的个数为2时，执行cat >> $2 < $1命令。请将下面所示的Shell程序的空缺部分补齐。

case （25） in
1) cat $1 ；；
2) cat >> $2 < $1；；
*) echo 'default…'
esac

（25）A. $$ B. $@ C. $# D. $*

在UNIX操作系统中，shell定义变量$$、$@、$#和$*的含义如下：

$$表示当前命令的进程标识数。

$@与$*基本相同，但当用双引号转义时，"$@"还是能分解成多个参数，但"$*"则合并成一个参数。

$#表示位置参数的个数，不包括命令名。

$*表示所有位置参量，即相当于$1,$2,$3,…

试题（25）的正确答案是C。


24.
进程PA不断的向管道写数据，进程PB从管道中读数据并加工处理，如图4所示。如果采用PV操作来实现进程PA和PB的管道通信，并且保证这两个进程并发执行的正确性，则至少需要__(26)__。

图4 进程图

（26）A.1个信号量，信号量的初值是0 　　　　　　　B.2个信号量，信号量的初值是0、1
　　　C.3个信号量，信号量的初值是0、0、1　　　　 D.4个信号量，信号量的初值是0、0、1、1

25.
●在UML 提供的图中，可以采用__(30)__对逻辑数据库模式建模；__(31)__用于接口、类和协作的行为建模，并强调对象行为的时间顺序；__(32)__用于系统的功能建模，并强调对象的控制流。
（30）A.用例图　　　　　　 B.构件图　　　　　　　　 C.活动图　　　　　　 D.类图
（31）A.协作图　　　　　　 B.状态图 　　　　　　　　C.序列图 　　　　　　D.对象图
（32）A .状态图 　　　　 　B.用例图 　　　　　　　　C.活动图 　　　　　　D.类图

参考答案：
（30）D（31）B (32) C

26
● 在一颗完全二叉树中，其根的序号为1，__(33)__可判定序号为p和q的两个接点是否在同一层。
（33）A．Llog2P」=Llog2q」　　　　　B．log2P = log2q
　　C．Llog2P」+1=Llog2q」　　　　D．Llog2P」=＋Llog2q」+1

参考答案：
A

27.
堆（heap）定义如下：
n个元素的序列{k[1],k[2],……，k[n]}当仅当满足下列的关系时，称之为堆
k[i] <=k[2i]&&k[i] <=k[2i+1]
或
k[i]> =k[2i]&&l[i]> =k[2i+1]
i=1,2,3,……n/2的下取整

具体的说：若将和次序列对应的一维数组（即以一维数组作此序列的存储结构）看成时一个完全二叉树，则堆的含义表明，完全二叉树中所有非终端结点的值均不大于（或不小于）其左，右孩子结点的值。

28.
　　二叉排序树(Binary Sort Tree)又称二叉查找(搜索)树(Binary Search Tree)。其定义为：二叉排序树或者是空树，或者是满足如下性质的二叉树：
①若它的左子树非空，则左子树上所有结点的值均小于根结点的值；
②若它的右子树非空，则右子树上所有结点的值均大于根结点的值；
③左、右子树本身又各是一棵二叉排序树。
　　上述性质简称二叉排序树性质(BST性质)，故二叉排序树实际上是满足BST性质的二叉树。

29.
　形态匀称的二叉树称为平衡二叉树 (Balanced binary tree) ，其严格定义是：
　　一棵空树是平衡二叉树；若 T 是一棵非空二叉树，其左、右子树为 TL 和 TR ，令 hl 和 hr 分别为左、右子树的深度。当且仅当
　　　①TL 、 TR 都是平衡二叉树；
　　　② ｜ hl － hr ｜≤ 1；
时，则 T 是平衡二叉树。

30.大顶堆
堆顶元素是最大的，它的叶子都比它小，以叶子为根，也作同样的规则

31.
广义表长度是数第一层括号内的逗号数目
可以看到，只有一个元素，就是((a,b,(),c),d),e,((f),g)
所以长度是1
深度是数括号数目，深度是4

32.
●__(38)__是多媒体内容描述接口标准。
（38）A.MPEG-1　　　　　　 B.MPEG-2 　　　　　C.MPEG-4　　　　　 D.MPEG-7
参考答案：
D

33.
● 未经压缩的数字音频数据传输率的计算公式为__(39)__。
(39) A.采样频率（HZ）×量化位数（bit）×声道数×1/8
　　 B.采样频率（HZ）×量化位数（bit）×声道数
　　 C.采样频率（HZ）×量化位数（bit）×1/8
　　 D.采样频率（HZ）×量化位数（bit）×声道数×1/16

参考答案：
B

34.
● 彩色打印机所采用的颜色空间是__(40)__。
(40)A. RGB彩色空间 　　　　B.CMY彩色空间　　　　　 C.YUV彩色空间 　　　　D.HSV彩色空间
参考答案：
B

35.
● MPEG视频中的时间冗余信息可以采用__(41)__的方法进行压缩编码
(41) A.帧间预测和变换编码　　　　　　　 B.霍夫曼编码和运动补偿
　　 C.变换编码和行程编码　　　　　　　 D.帧间预测和运动补偿

参考答案：
D

36.
解法：从函数依赖集出发，把所有属性分为4类
1、L类：全部出现在函数依赖的左半部
2、R：全部出现在函数依赖的右半部
3、LR：出现在函数依赖的左右两边
4、N：不出现在函数依赖中
可能成为候选键的有L类，LR类和N类
对于L类，求出它的闭包，若包含所有属性，则说明其为候选键，且为唯一候选键。
对于LR类，求出其闭包，若包含所有属性，则为候选键，若不包含，在找出其中一个属性结合。
对于N类，直接加至候选键即可。

37.
● 关系模式R（U，F），其中U＝{W,X,Y,Z},F={WX→Y,W→X, X→Z,Y→W}。关系模式R的候选建是__(45)__、__(46)__是无损连接并保持函数依赖的分解。
（45）A.W和 Y　　　　　B. WY　　　　　　　　C.WX　　　　　　　　　 D.WZ
（46）A.p={R1(WY),R2(XZ)}　　　　　　　 B.p={R1(WZ),R2(XY)}
　　　C.p={R1(WXY),R2(XZ)}　　　　　　　D.p={R1(WX),R2(YZ)}

参考答案：
（45）A（46）C

38.
OMT法是目前最为成熟和实用的方法之一。它从三个方面对系统进行建模，每个模型从一个侧面反映系统的特性，三个模型分别是：对象模型、动态模型和功能模型。

39.
● 以关键字比较为基础的排序算法在最坏情况下的计算时间下界为O（nlogn）。下面的排序算法中，最坏情况下计算时间可以达到O（nlogn）的是__(59)__，该算法采用的设计方法是__(60)__。
（59）A.归并算法　　 　 B.插入算法　　　　　 C.选择算法　　　　　　 D.冒泡算法
（60）A.分治法　　　　　B.贪心法　　　　　　 C.动态规划法　　　　　 D.回溯法

参考答案：
（59）A（60）A

40.
● 以太网100BASE－TX标准规定的传输介质是__(61)__。
(61)A.3类UTP　　　　　　B.5类UTP　　　　　　 C.单模光纤　　　　　　 D. 多模光纤

参考答案：
B
41.
● 许多网络通信需要进行组播，以下 选项中不采用组播协议的应用是__(62)__。在IPV4中把__(63)__类地址作为组播地址。
（62）A.VOD　　　　　　 B.NetMeeting　　　　 C.CSCW　　　　　　　　 D.FTP
（63）A. A　　　　　　　B.B　　　　　　　　　C.D　　　　　　　　　　D.E

42.
● 将双绞线制作成交叉线（一端按ELA/TIA568A线序，另一端按ELA/TIA568B线序），该双绞线连接的两个设备可为__(64)__。
(64)A.网卡与网卡　　　　　　　 B.网卡与交换机
　　C.网卡与集线器　　　　　　 D.交换机的以太口与下以级交换机UPLLINK口
参考答案：
A