第一篇：2011年上半年软考程序员上午试卷(参考答案+解析版)(第1题—第63题 )
2011年上半年软考程序员上午试卷（参考答案+解析版）
（第1题—第63题)
小刘整理，谢谢支持！
2011年上半年软考程序员上午试卷（参考答案+解析版）—第1题
2011年上半年软考程序员上午试卷（参考答案+解析版）—第2题
●某单位的员工工资表如下图所示。当员工基本工资小于2000元时，绩效工资=基本工资X9%X业绩点；当员工基本工资大于等于2000元时，绩效工资=基本工资x8%x 业绩点。若要计算绩效工资，可先在F3单元格中输入（3）并向垂直方向拖动填充柄至F9单元格，则可自动算出每个员工的绩效工资；若要计算各项平均值，则先在C10单元格中输入(4)．拖动填充柄至F10单元格。
(3)A.IF(C3<2000,C3*9%*E3,C3*8%*E3)B.IF(C3<2000,C3*8%*E3,C3*9%*E3)C.=IF(C3<2000,C3*9%*E3,C3*8%*E3)D.=IF(C3<2000,C3*8%*E3,C3*9%*E3)
(4)
A.=AVERAGE(C3:C9)，然后向水平方向 B．=AVERAGE(C3:G3)．然后向垂直方向 C．AVERAGE(C3:C9)，然后向水平方向 D.AVERAGE(C3:G3)，然后向垂直方向
2011年上半年软考程序员上午试卷（参考答案+解析版）—第3题
●(5)一负责电子邮件的接收，这样当用户的电子邮件到来时，由其负责将邮件移到用户的电子信箱内，并通知用户有新邮件。
(5)A．用户计算机 B．邮件服务器 C．个人计算机 D．ASP主机
2011年上半年软考程序员上午试卷（参考答案+解析版）—第4题
●计算机启动时，可以通过存储在(6)中的引导程序引导操作系统。(6)A.RAM B.ROM C.Cache D.CPU
2011年上半年软考程序员上午试卷（参考答案+解析版）—第5题
●寄存器间接寻址是指在(7)中存取操作数。
(7)A．通用寄存器 B．程序计数器 C．主存单元 D．外存储器
2011年上半年软考程序员上午试卷（参考答案+解析版）—第6题
●CPU从主存中取出一条指令并完成执行的时间称为(8)。
(8)A．时钟周期 B．机器周期 C．指令周期 D．总线周期
2011年上半年软考程序员上午试卷（参考答案+解析版）—第7题
●若SRAM芯片的存储容量为 64K X16位，则其地址线与数据线数目应为(9)。使得访问其指定存储单元时，能将地址信号和数据信号一次性地并行传输。(9)A．16 和16 B．64 和16 C．16和 64 D．6和8
2011年上半年软考程序员上午试卷（参考答案+解析版）—第8题
●(10)是指CPU-次可以处理的二进制数的位数，它直接关系到计算机的计算精度、速度等指标；运算速度是指计算机每秒能执行的指令条数，通常用(11)为单位来描述。(10)A．字长 B．主频 C．运算速度 D．存储容量
(11)A.MB B.HZ C.MIPSD.BPS
2011年上半年软考程序员上午试卷（参考答案+解析版）—第9题
●要表示256级灰度图像，表示每个像素点的数据最少需要(12)个二进制位。(12)A.4 B．8 C．16 D．256
2011年上半年软考程序员上午试卷（参考答案+解析版）—第10题
●某种SoundBlaster声卡属于 8位声卡，这里的“8位”是指(13)。
（13）A．声音最大量化位数是8 B．MIDI 通道数是8 C．可以产生的音色数是28 D．声道数为8
2011年上半年软考程序员上午试卷（参考答案+解析版）—第11题
●下列软件产品中，专门用于音频信息处理的工具软件是(14).(14)A.3Ds Max B.PhotoShop C.Audition D.Authorware
2011年上半年软考程序员上午试卷（参考答案+解析版）—第12题
●一个公司面临的网络攻击来自多方，一般采用安装防火墙的方法防范(15)。(15)A．外部攻击 B．内部攻击 C．网络监听 D．病毒入侵
2011年上半年软考程序员上午试卷（参考答案+解析版）—第13题
●Windows 系统中内置了一些用户组，其中，对计算机拥有不受限制的完全访问权的用户组是(16)。
(16)A.Guests B.PowerUsers C.Users D.Administrators
2011年上半年软考程序员上午试卷（参考答案+解析版）—第14题
●软件合法复制品（光盘）所有人不享有_(17)。
(17)A．软件著作权 B．必要的修改权C．软件装机权 D．软件备份权
2011年上半年软考程序员上午试卷（参考答案+解析版）—第15题
●商标权权利人是指(18)。(18)A．商标设计人 B．商标制作人 C．商标使用人 D．注册商标所有人
2011年上半年软考程序员上午试卷（参考答案+解析版）—第16题
●在IEEE754浮点表示法中，阶码采用__(19)表示。
(19)A．原码 B．反码 C．补码 D．移码
2011年上半年软考程序员上午试卷（参考答案+解析版）—第17题
●某机器的字长为8，符号位占 1位，数据位占7位，采用补码表示时的最小整数为(20)。
(20)A.-28 B.-27 C.-27+1 D.-28+ 2011年上半年软考程序员上午试卷（参考答案+解析版）—第18题
●在计算机中，(21)。(21)A．指令和数据都采用十进制存储 B．指令和数据都采用二进制存储
C．指令用十进制存储，数据采用二进制存储 D．指令用二进制存储，数据采用十进制存储
2011年上半年软考程序员上午试卷（参考答案+解析版）—第19题
●采用虚拟存储器的主要目的是__(22)。
(22)A．扩大可使用的主存空间 B．扩大可使用的外存空间 C．提高访问主存的速度 D．提高访问外存的速度
2011年上半年软考程序员上午试卷（参考答案+解析版）—第20题
●在Windows 系统中，可通过文件扩展名判别文件类型，例如，(23)是一种可执行文件的扩展名。当用户双击一个文件名时，Windows 系统通过建立的(24)来决定使用什么程序打开该文件。(23)A.xml B.txt C.obj D.exe(24)(24)A．文件 B．临时文件 C．文件关联 D．子目录
2011年上半年软考程序员上午试卷（参考答案+解析版）—第21题
●在Windows系统中，当用户选择C:Documents目录中的一个文件图标，并执行“剪切”命令后，被“剪切”的文件会放在(23)中；若用户要浏览“图片收藏”文件夹中存放的图像文件的大致内容，则可选择“查看”菜单栏中的(24)命令。
(23)A．回收站 B．剪贴板 C．USB盘 D．C:Documents(24)(24)A．详细信息 B．图标 C．缩略图 D．平铺
2011年上半年软考程序员上午试卷（参考答案+解析版）—第22题
●(25)支持网络系统的功能，并具有透明性。
(25)A．批处理操作系统 B.分时操作系统C．实时操作系统 D．分布式操作系统(26)2011年上半年软考程序员上午试卷（参考答案+解析版）—第23题
●某段式存储管理系统中的地址结构如下图所示，若系统以字节编址，则该系统允许的最大段长为(26)KB;(27)是错误的段号。(26)A.16 B.32 C.64 D.128(27)(27)A.0 B.64 C.128 D.256
●标识符在高级语言源程序中的作用不包括(28)。
2011年上半年软考程序员上午试卷（参考答案+解析版）—第24题(28)A．为变量命名 B．为注释标记位置C．为函数命名 D．为数据类型命名
2011年上半年软考程序员上午试卷（参考答案+解析版）—第25题
2011年下半年软考程序员上午试卷（参考答案版）—第25题
●表达式“a*(b-(c+d))”的后缀式为
(29)。(29)A.cd+ab-* B.ab*c-d+C．abcd+-* D.abcd*-+
2011年上半年软考程序员上午试卷（参考答案+解析版）—第26题
●对C/C++程序进行处理时，可先将(31)，然后进行链接以形成可执行程序。(31)A．C程序翻译成汇编程序 B．C-r+程序翻译成C程序 C．C程序翻译成C++程序 D.C++程序翻译成目标程序
2011年上半年软考程序员上午试卷（参考答案+解析版）—第27题
●以下语言中，不用于网页编程或网页制作的语言是(32)。(32)A.Shell B.JavaScript C.PHP D.HTML
2011年上半年软考程序员上午试卷（参考答案+解析版）—第28题
●若匹配Email地址的正则式为“＼w+([-+．]＼w+)*@＼w+（[一．]＼w+）*＼.＼w+([-．]＼W+)*“ 其中，w等同于[0-9 A-Z a-z]（即数字或英文字母中的一个），则(33)为非法的 Email地址。
(33)A.999@qq.com B.amy+OOO@qq..com.C.amy.000@220.191.102.14 D.a-b-c@163.com
2011年上半年软考程序员上午试卷（参考答案+解析版）—第29题
●函数g和 f的定义如下所示，其中，a是全局变量。若在函数g中以引用调用(call by reference)方式调用函数f(a)，则函数g的返回值为(34)，此时变量a的值为(35)。
(34)A.25 B.12 C.10 D.8(35)A.2 B.3 C.4 D.52011年上半年软考程序员上午试卷（参考答案+解析版）—第30题
●若二维数组arr[1..8，1..6]的首地址为base，数组元素按列存储，且每个元素占用4个存储单元，则元素arr[5,5]在该数组空间的地址为(36)。
(36)A.base+(4*8+4)*4
B.base+(5*8+5)*4 C.base+(4*6+4)*4 D.base+(5*6+5)*4
2011年上半年软考程序员上午试卷（参考答案+解析版）—第31题
●设线性表(59，53，46，48，37，31，25)采用散列(Hash)法进行存储和查找，散列函数为H(Key)=Key MOD 7(MOD表示整除取余运算)。若用链地址法解决冲突（即将相互冲突的元素存储在同一个单链表中）构造散列表，则散列表中与哈希地址(37)对应的单链表最长。(37)A．2 B．3 C．4 D．6
2011年上半年软考程序员上午试卷（参考答案+解析版）—第32题
●设递增序列A为a1，a2，?，an，递增序列 B为b1，b2，?，bm，且m>n，则将这两 个序列合并为一个长度为m+n的递增序列时，当(38)时，归并过程中元素的比较次 数最少。
(38)A.an >bm B.an 2011年上半年软考程序员上午试卷（参考答案+解析版）—第33题 ●已知某带权有向图G（顶点数为6，顶点编号为1 至6）的邻接表如下所示，其中表结点的结构为： 则图G 中含有的弧数为__(39)。(39)A．9 B．11 C．15 D．18 2011年上半年软考程序员上午试卷（参考答案+解析版）—第34题 ●当二叉树的结构形如一(40)时，其后序遍历序列和中序遍历序列相同。 2011年上半年软考程序员上午试卷（参考答案+解析版）—第35题 2011年上半年软考程序员上午试卷（参考答案+解析版）—第36题 ●输入受限的双端队列是指只有一端可以进行入队操作而从两端都可以进行出队 操作的队列，如下图所示。对于输入序列1 2 3 4，经过一个初始为空且输入受限的双端 队列后，不能得到的输出序列为(42)。 2011年上半年软考程序员上午试卷（参考答案+解析版）—第37题 2011年上半年软考程序员上午试卷（参考答案+解析版）—第38题 ●以下关于类和对象的叙述中，正确的是__(44)。 (44)A．对象是类的实例 B．每个类都必须创建一个实例 C．每个类只能创建一个实例 D．类的实例化是指对类进行初始化 2011年上半年软考程序员上午试卷（参考答案+解析版）—第39题 ●在统一建模语言(UML)中，一(45)月于描述系统与外部系统及用户之间的交互。 (45)A．对象图 B．类图 C．用例图 D．序列图 2011年上半年软考程序员上午试卷（参考答案+解析版）—第40题 ●面向对象软件开发过程中，面向对象分析阶段包含一系列活动，而(46)活动不属于面向对象分析阶段。 (46)A．识别分析类 B．构建分析模型 C．评估分析模型 D．确定接口规格 2011年上半年软考程序员上午试卷（参考答案+解析版）—第41题 ●在面向对象开发方法中，(47)机制模拟现实世界中的遗传现象，实现类之间共享数据和方法。 (47)A．封装 B．继承 C．多态 D．抽象接口 2011年上半年软考程序员上午试卷（参考答案+解析版）—第42题 ●UML图中，(48)属于动态交互图，它们关注系统的动态特性；(49)属于静态结构视图，它们关注系统的静态结构。(48)A．序列图和通信图 B．序列图和类图 C．类图和对象图 D．组件图和通信图(49)A．序列图和通信图 B．序列图和类图 C．类图和对象图 D．组件图和通信图 2011年上半年软考程序员上午试卷（参考答案+解析版）—第43题 ●在数据流图(DFD)中，顶层数据流图仅包含一个(50)。(50)A．数据处理 B．数据存储 C．数据流 D．数据源或者数据汇点 2011年上半年软考程序员上午试卷（参考答案+解析版）—第44题●下图所示的流程中，最少需要(51)个测试用例就可以完成路径覆盖。 (51)A．1 B．2 C．3 D．4 2011年上半年软考程序员上午试卷（参考答案+解析版）—第45题 ●实体一关系图(E-R图)用于结构化分析过程中的(52)建模。(52)A．功能 B．数据 C．行为 D．组织 2011年上半年软考程序员上午试卷（参考答案+解析版）—第46题 ●在程序中有一个错误处理模块，它接收出错信号，对不同类型的错误打印出不同的出错信息，则该模块设计时内聚类型为(53)。(53)” A．逻辑内聚 B．信息内聚 C．功能内聚 D．过程内聚 2011年上半年软考程序员上午试卷（参考答案+解析版）—第47题 ●黑盒测试不能发现(54)。 (54)A．不正确或遗漏的功能 B．初始化或终止性错误 C．内部数据结构不合理 D．性能不满足要求 2011年上半年软考程序员上午试卷（参考答案+解析版）—第48题 ●敏捷软件开发方法的特点不包括(55)。 (55)A．较之于过程和工具，更注重人及其交互 B．较之于详尽的文档，更注重可运行软件的价值 C．较之于响应需求变化，更注重严格遵循计划 D．较之于合同谈判，更注重与客户的合作 2011年上半年软考程序员上午试卷（参考答案+解析版）—第49题 ●用户界面设计原则中不包括(56)。 (56)A．不要将实现技术暴露给用户 B．整个软件中应采用统一规范且易于理解的行业术语 C．软件给出的错误信息应尽量包括错误表现和问题，以及解决方法和建议 D．软件运行时底层软件发现的错误应由底层代码向界面发送错误信息 2011年上半年软考程序员上午试卷（参考答案+解析版）—第50题 ●对应用软件产品所进行的β 测试，是(57)进行的测试。 (57)A．在开发环境下由开发者 B．在开发环境下由测试人员 C．在应用环境下由开发者 D．在应用环境下由部分用户 2011年上半年软考程序员上午试卷（参考答案+解析版）—第51题 ●某银行数据库中，信贷额度关系模式为Credit-in（用户账号，信贷额度，已用 金额，信誉指数），用户关系模式为User（用户账号，用户姓名，地址，电话）a．查询每个用户还能使用的剩余金额的SQL语句为： SELECT用户账号，用户姓名，(58)FROM Credit-in, User WHERE(59)； (58)A．“信贷额度一已用金额”as剩余金额 B．信贷额度一已用金额as剩余金额 C．“信贷额度一已用金额”at剩余金额 D．信贷额度一已用金额at剩余金额 (59)A．”Credit-in.用户账号”=“User.用户账号” B．“Credit-in用户账号”AND“User.用户账号” C．Credit-in.用户账号-User.用户账号 D． Credit-in.用户账号AND User.用户账号 b．查询用户地址包含“科技二路”的用户姓名及电话的SQL语句为： SELECT用户姓名，电话 FROM User WHERE(60)； (60)A．地址IN（科技二路）B．地址like’科技二路’ C．地址IN（'科技二路'）D．地址like’%科技二路%' c．将信誉指数大于60的用户的信贷额度上调、10%的SQL语句为： UPDATE Credit-in(61)WHERE(62)； (61)A．SET信贷额度=信贷额度*1.1 B．Modify 信贷额度一信贷额度*1.1 C．SET信贷额度=’信贷额度*1.1'D．Modify 信贷额度='信贷额度*1.1'(62)A．．信誉指数>60' B．信誉指数>' 60' C． 信誉指数≤60 D．信誉指数>60 2011年上半年软考程序员上午试卷（参考答案+解析版）—第52题 ●某隧道长1.1公里，现需要在隧道两侧安装照明灯和广告牌，若起点、终点以及从起点到终点每隔50米都需要安装一盏照明灯，并且在相邻照明灯之间需要安装一幅广告牌，则共需安装照明灯(63)盏、广告牌(64)幅。(63)A．40 B．42 C．44 D．46(64)A．38 B．40 C．42 D．4 42011年上半年软考程序员上午试卷（参考答案+解析版）—第53题 ●某保险公司推出的电脑损坏保险业务如下所述：每台参保电脑每年需交付 200元，当电脑损坏时，可以获得理赔金额1700元。据统计，每年约有10%的电脑损坏需要理赔，则该保险公司每年平均从每台参保电脑获益(65)元。(65)A.10 B.30 C.50 D.100 2011年上半年软考程序员上午试卷（参考答案+解析版）—第54题 ●在www.xiexiebang.com 2011年上半年软考程序员上午试卷（参考答案+解析版）—第55题 HTML中(67)用于定义文档的标题。 (67)A.font B.title C.align D.head 2011年上半年软考程序员上午试卷（参考答案+解析版）—第56题 ●下列接入网技术中，通过电话线接入的是(68)。(68)A.HFC B.ADSL C.FTTx D.Wi-Fi 2011年上半年软考程序员上午试卷（参考答案+解析版）—第57题 ●在电子邮件系统中，Outlook Express 是__(69)。 (69)A．邮件客户端 B．邮件服务器 C．邮件传输代理 D．邮件协议 2011年上半年软考程序员上午试卷（参考答案+解析版）—第58题 ●利用Windows 系统中的事件查看器将查看的事件分为__(70)。 (70)A．用户访问事件、安全性事件和系统事件 B．应用程序事件、安全性事件和系统事件 C．网络攻击事件、安全性事件和记帐事件 D．网络连接事件、安全性事件和服务事件 2011年上半年软考程序员上午试卷（参考答案+解析版）—第59题 ●This printer is equipped with an 8-bit parallel(71)port for PCs.(71)A.plug B.insert C.link D.interface 2011年上半年软考程序员上午试卷（参考答案+解析版）—第60题 ●OS can use(72)memory to run processes that require more main memory than is actually available.(72)A.virtual B.imaginary C.abstract D.false 2011年上半年软考程序员上午试卷（参考答案+解析版）—第61题 ●Unit testing refers to that each(73)is tested to ensure that it operates correctly.(73)A.subsystem B.device C.application D.module 2011年上半年软考程序员上午试卷（参考答案+解析版）—第62题 ●More and more persons who use the Intemet had created a(74)or web based diary.(74)A.blog B.DBMS C.profile D, photo-set 2011年上半年软考程序员上午试卷（参考答案+解析版）—第63题 ●(75)means thata source program file can be compiled and executed on different computers.(75)A.Portability B.Usablity C.Recovery D.Mobility （参考答案） 1—5 BD、CA、B、B、C 6—10 C、A、AC、B、A 11—15 C、A、D、A、D 16—20 D、B、B、A、DC 21—25 BC、D、CD、B、C 26—30 D、A、B、AD、A 31—35 C、B、A、A、B 36—40 D、B、A、C、D 41—45 B、AC、A、D、B 46—50 A、C、C、D、D 51—55 BCDAD、DD、B、D、B 56—60 B、A、B、D、A 61—63 D、A、A 附：程序员2011年下半年真题(下载链接) 2012上半年软考网络工程师试题及参考答案 pu中高速缓存CACHE与主存的数据交换是由（1）实现的 答案 A：硬件 ● 内存编址0000****-0000****的容量是（2）答案 D：8k ● 相联寄存器按（3）访问 答案 C：内容 ● 下图（4）在关键路径上 答案 B：C ● 在美国注册未在中国注册版权的商品在中国销售？（5）答案 ？：需要像美国公司支付使用版权费 ● 以太网使用曼彻斯特编码，其编码效率为（6）%，在快速以太网中使用4B/5B编码，其编码效率为（7）% 答案 50%；80% ● 操作系统中权限最小的是？（8）答案 Everyone ● OSPF是通过（9）与邻居保持连接的，关于OSPF拓扑数据库，下面选项中正确的是（10）9：hello 10：A．每一个路由器都包含了拓扑数据库的所有选项 B．在同一区域中的所有路由器包含同样的拓扑数据库 C．使用Dijkstra算法来生成拓扑数据库 D．使用LSA分组来更新和维护拓扑数据库 答案 9： hello 10：D ● 甲向乙发送数据时，乙通过什么验证（11）11：A 甲的公匙 B 甲的私匙 C乙的公匙 B 乙的私匙 ● 钓鱼网站叙述错误的是（12）答案 12： 钓鱼网站是一个网络游戏 地址192.168.37.192/25属于（13）；172.17.17.255/23属于（14）答案 13： 14： ● Windows身份认证中最安全的是（15）答案 15： WINDOWS身份认证 ● rip协议是（16），最大跳数是（17），rip网络之间采用（18）来确定网络 答案 16：距离矢量 17：15 18：最短路径 ● ARP的作用是（19），ARP在（20）中传送 19：A．由IP地址查找对应的MAC地址 B．由MAC地址查找对应的IP地址 C．由IP地址查找对应的端口号 D．由MAC地址查找对应的端口号 20：A．以太帧 B．IP数据报 C．UDP报文 D．TCP报文 答案 19：B 20：A ● 下列属于私网地址的是（21）答案 21：A ● -------------------（22）22：A：被分成了62个子网 B被分成了62 个主机地址 C被分成了 32个子网 D被分成了32个主机地址 ●B 802.11使用的协议是（23）答案 23： ● 属于摘要算法的是（24）答案 24：MD5 ● SMTP在传输过程中使用的是什么（25）答案 25：ASCLL ● 嗅探器改变了端口，使之能（26） 答案 26：可以捕获网络接口上的每个数据分组 ● 用户在浏览网页-------（27）----下图是利用抓包软件捕获的数据截图，（28）说法是正确的 答案 27：ARP-A 28： ● FTP上传命令是（29）答案 29：put ● ipv6的地址类型分为（30）答案 30： ● Web中能实现安全传输的是（31）答案 31：HTTPS ● 路由器命令“Router(config)# access-list 1 deny 192.168.*.*”的含义是（32） 32：A．不允许源地址为192.168.*.*的分组通过 B．允许源地址为192.168.*.*的分组通过 C．不允许目标地址为192.168.*.*的分组通过 D．允许目标地址为192.168.*.*的分组通过 答案 32：A ● E1信道数据速率是（33），T1数据信道速率是（34）答案 33：2.048 34：1.544 ● 无线局域网的两种工作模式，其中的（35）模式是一种点对点连接的网络，不需要无线接入点和有线 网络的支持。802.11n的数据数率是（36）答案 35： 36：300M ● IIS中包含的组建是（37）答案 37：FTP ● -----------------------（38）---------Dhcpdiscover是（39）发送的 答案 38： 39：广播 ● 设信道带宽为3400HZ，采用PCM编码，采样周期为125μs，每个样本量化为256个等级，则信道的数据率 为（40） 40A．10Kb/s B．16Kb/s C．56Kb/s D．64Kb/s 答案：D：64kb/s ● 网络中采用DHCP不能实现的是（41）答案：提高域名解析速度 ● 如果一个公司有2000台主机，则必须给它分配（42）个C类网络。为了使该公司网络在路由表中只占一行，指定给它的子网掩码应该是（43）42 A．2 B．8 C．16 D．24 A．255.192.0.0 B．255.240.0.0 C．255.255.240.0 D．255.255.248.0 答案：BD ● ICMP命令是（44），当网络出现阻塞时，路由器会发出（45）答案：？ 源抑制 ● 和route print 作用相同的命令是（46）答案：netstar – r 100base-t在综合布线时，布线距离最大为（47）米 答案：100 ● 关于三层交换机叙述错误的是（48）答案：三层交换机只能根据第三层协议交换 ● TCP是互联网中的传输层协议，使用（49）次握手协议建立连接-----（50） 答案：3 SYN/ACK ？ ● 安全电子邮件（51）答案：PGP ● LINUX中（52）命令是结束进程的 答案：kill ● LINUX中（53）命令是关闭系统的 答案：shutdown ● LINUX的DNS服务器设置文件是（54）答案：/etc/resolv.conf ● FTP控制连接的默认端口是（55）答案：21 ● 某公司与开发人员签订了合同，有明确的交付时间和对软件的要求，应用那种开发方法（56）● 程序设计的继承性是（57） ● 通过交换机连接的一组工作站（58） A．组成一个冲突域，但不是一个广播域 B．组成一个广播域，但不是一个冲突域 C．既是一个冲突域，又是一个广播域 D．既不是冲突域，也不是广播域 答案：B ● 建筑物园区布线系统是指(59)A．由终端到信息插座之间的连线系统 B．楼层接线间的配线架和线缆系统 C．各楼层设备之间的互连系统 D．连接各个建筑物的通信系统 答案：D ● 网络管理功能是（60） 答案：配置管理-故障管理-性能管理-安全管理-计费管理 剩下10K中文题只收集了相关内容无顺序 61.AP的功能……无线接入 62.无线空中接口 WIMAX 63.查询主DNS查不到 应查根DNS服务器 64.DNS中定义邮件的字段 这题选MX 是邮件交换记录 65.软件开发模型好像是选螺旋 66.网络的可用性是指什么 这题应选时间那个选项 67.MOV R1 #45 这个是属于立即数寻址和直接寻址.68.数据流图…………选输入输出 69.管理站与代管理站……应选B代向管发 70.冲突糟时间？答案不清楚，我选的C 英文题： 传输层（transport）使用TCP协议进行传输，每个分组的传输路径（path）是不同的，所以在接收端在收到分组（segments）后要发送一个确认分组给发送端。在自动重传时间到了没有收到确认分组的话，发送端将自动重传。 每个连接的自动重传时间是不固定的。如果定时间短了，就会发生接收端的确认（acknowledge）分组没有到达发送端，而重传时间到了，发送端就会重传，如果时间长了，就会影响传输时间。自动重传时间是动态的（dynamic）下午题 试题一 （1）A(2)B(3)C(4)6(5)4(6)A(7)D(8)B(9)C(10)192.168.100.254(11)255.255.255.0(12)ACCESS(13)99(14)trunk(15)192.168.1.254 试题二(1)dhcpd.conf(2)/etc(3)7200(4)255.255.255.0(5)192.168.1.1(6)192.168.1.255(7)218.30.19.50(8)61.134.1.4(9)fixup(10)题目中的mac地址，我没有记下来，但是有个问题：我肯定做错了，在linux中，mac中见的分隔符不应该是“-”(11)192.168.1.102 试题三(1)c 问2：负载均衡、备份(2)abc.com(3)61.153.172.31(4)通过ip查找域名 问5：启用循环(5): B(6): A 试题四(1)网络(2)AH(3)ESP(4)传输(5)S1(6)192.168.1.2(7)192.168.2.2(8)severB(9)192.168.1.0(10)192.168.2.0(11)202.113.110.1 试题五(1)192.168.10.2(2)255.255.255.0(3)rip(4)192.168.10.0(5)192.168.30.0(6)192.168.40.0(7)212.34.17.9(8)255.255.255.224(9)设置一条通往分公司内网的静态路由(10)设置认证方式为预共享方式(11)202.100.2.3(12)vpntest 程序员考试：http:// 2016年软考程序员试题及答案解析 一、选题题 1.二进制语言是属于()A.面向机器语言 B.面向问题语言 C.面向过程语言 D.面向汇编语言 【解析】人们研制了许许多多计算机程序设计语言，其中二进制语言直接来自计算机的指令系统，与具体计算机紧密相关，所以是一种面向机器语言。面向问题语言是为了易于描述和求解某类特定领域的问题而专门设计的一种非过程语言。面向过程语言是一种能方便描述算法过程的计算机程序设计语言。有汇编语言，但没有面向汇编语言。汇编语言也是一种面向机器的语言，与机器语言比较，汇编语言用有助于记忆的符号来代表二进制代码。所以解答是A。 【答案】A 2.下列语言中不属于面向过程的语言是()A.高级语言 B.低级语言 C.C语言 D.PASCAL语言 【解析】C语言和PASCAL等程序设计语言都是高级语言，它们用于描述复杂加工的处理过程，所以也称它们是面向过程语言。低级语言是指机器语言和汇编语言，低级语言是面向机器的语言，而不是面向问题的语言。所以解答是B。【答案】B 3.下列字符中属于键盘符号的是()A.B.n C.t D.b 【解析】键盘符号是指键盘上有标记，并能在显示器上直接以其标记字样显示的字符。有许多键盘上有标记的符号，它们不是用于直接显示的，键入这种字符用于表示特定的意义，如常用的回车符。为了能让C程序标记这种符号，程序采用转义字符的方式书写这种字符。如'n'、't'、'b'都不是键盘字符，在C语言中，它们都得用转义字符来表达。只有字符才是键盘字符。所以解答是A。但在C 程序员考试：http:// 程序中，反斜杠字符已特别用作转义字符的引导符，它也得用转义字符的表达形式书写，将它写成’’。【答案】A 4.下列字符列中，不是用来表达转义字符是()A.B.' C.074 D. 【解析】转义字符有三种书写形式：反斜社字符后接上某个规定的字符;反斜杠字符后接上13个八进制数字符;反斜社字符和字符X之后接上1至2个十六进制数字符。后两种分别八进制数和十六进制数直接给出字符的ASCll代码值。而074是八进制整数，不是转义字.所以解答是C。【答案】C 5.不是C语言提供的合法关键字是()A.switch B.begin C.case D.default 【解析】因C语言的关键字表中没有begin，它不是C语言的关键字。所以解答是B。【答案】B 6.下列字符列中，能作为单个标识符是()l A.?a B.a=2 C.a.3 D.a___3 【解析】在C语言中，规定标识符是这样一种字符序列，由英文字母或下线字符开始，后接任1个英文字母、下线字符和数字符组成。所以问题所列的字符列只有a_3是标识符，其余都l是标识符，一个是由字符’?’开头、一个中间有字符’=’，另一个有字符’.’。所以解答是D。【答案】D 7.在C语言中，下列说法中错误的是()A.函数定义可以分为两个部分：函数说明部分和函数体 B.主函数可以调用任何非主函数 程序员考试：http:// C.任何非主函数可以调用其它任何非主函数 D.程序可以从任何函数开始执行 【解析】每个C函数的定义分两部分，函数说明部分和函数体，所以叙述A.是正确的叙述。C语言中，函数可以递归调用，主函数可以调用程序中的任何函数，当然可以调用任何非主教的其它函数，所以叙述B.是一个正确的叙述。同样理由，叙述C.也是正确的。C语言规，C程序只有一个主函数，并总是从主函数开始执行，不能从非主函数开始执行。所以，说程可以从任何函数开始执行是错误的。所以解答是D。【答案】D 8.下列字符列中，可以作为“字符串常量”的是()A.ABC B.ABC” C.’abc’ D.’a’ 【解析】C程序中，一个字符率常量是表示一个字符序列，书写时，用双引号字符前后括住这个字符序列。所以只有”ABC”是一个正确的字符率常量，其余都不是。其中，ABC可作为标识符，字符列’abc’不能出现在C程序中，’a’是一个字符常量。所以解答是B。【答案】B 9.在以字节存储字符的系统中，’n’在内存占用的字节数是()A.1 B.2 C.3 D.4 【解析】一般来说，一个字符在内存中只占1个字节，’n’是转义字符，其意义是换行符，它作为一个字符存储，在内存也只占五个字节。所以解答是A。【答案】A 10.字符串”XyZ”在内存占用的字节数是()A.3 B.4 C.6 D.8 程序员考试：http:// 【解析】字符串中的每个字符占1个字节，但C程序在存储字符串时，要在最后一个有效字符后面接上1个字符串结束的标记符' '。这样，存储字符串常量”xyZ”需要4个字节。所以解答是B。【答案】B 程序员 http:// 程序员考试考点分析与真题详解（第4版） 第 1 章 数据结构与算法 数据结构是指数据对象及其相互关系和构造方法，一个数据结构S可以用一个二元组表示为S=（D,R）。其中，D是数据结构中的数据的非空有限集合，R是定义在D上的关系的非空有限集合。在数据结构中，结点与结点间的相互关系称为数据的逻辑结构，数据在计算机中的存储形式称为数据的存储结构。 数据结构按逻辑结构不同分为线性结构和非线性结构两大类，其中非线性结构又可分为树形结构和图结构，而树形结构又可分为树结构和二叉树结构。 按照考试大纲的要求，在数据结构与算法方面，要求考生掌握以下知识点。 1.常用数据结构 数组（一维数组、二维数组、静态数组、动态数组）、线性表、链表（单向链表、双向链表、环形链表）、队列、栈、树（二叉树、查找树）和图（邻接矩阵、邻接表）等的定义、存储和操作。 2.常用算法 （1）排序算法、查找算法、数值计算算法、字符串处理算法、递归算法、最小生成树、拓扑排序和单源点最短路径求解算法、图的相关算法。 （2）算法与数据结构的关系、算法效率、算法设计、算法描述（流程图、伪代码、决策表）、算法的复杂性。 1.1 算法设计概述 程序员 http:// 算法是在有限步骤内求解某一问题所使用的一组定义明确的规则。通俗地说，就是计算机解题的过程。在这个过程中，无论是形成解题思路还是编写程序，都是在实施某种算法。前者是推理实现的算法，后者是操作实现的算法。一个算法应该具有以下5个重要的特征。 （1）有穷性：一个算法（对任何合法的输入值）必须总是在执行有穷步之后结束，且每一步都可在有穷时间内完成。 （2）确定性：算法中每一条指令必须有确切的含义，读者理解时不会产生二义性。在任何条件下，算法只有唯一的一条执行路径，即对于相同的输入只能得出相同的输出。 （3）输入：一个算法有零个或多个输入，以确定运算对象的初始情况。所谓零个输入是指算法本身定出了初始条件。这些输入取自于某个特定对象的集合。 （4）输出：一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的。 （5）可行性：一个算法是可行的，即算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。 算法设计要求正确性、可读性、健壮性、高效率与低存储量需求。 效率指的是算法执行的时间。对于解决同一问题的多个算法，执行时间短的算法效率高。存储量需求指算法执行过程中所需要的最大存储空间。两者都与问题的规模有关。 算法的复杂性是算法效率的度量，是算法运行所需要的计算机资源的量，是评价算法优劣的重要依据。可以从一个算法的时间复杂度与空间复杂度来评价算法的优劣。当将一个算法转换成程序并在计算机上执行时，其运行所需要的时间取决于下列因素。 （1）硬件的速度。例如，使用486还是使用586.（2）书写程序的语言。实现语言的级别越高，其执行效率就越低。 程序员 http:// （3）编译程序所生成目标代码的质量。对于代码优化较好的编译程序其所生成的程序质量较高。 （4）问题的规模。例如，求100以内的素数与求1 000以内的素数其执行时间必然是不同的。 显然，在各种因素都不能确定的情况下，很难比较出算法的执行时间。也就是说，使用执行算法的绝对时间来衡量算法的效率是不合适的。为此，可以将上述的各种与计算机相关的软、硬件因素都确定下来，这样一个特定算法的运行工作量大小就只依赖于问题的规模（通常用正整数n表示），或者说它是问题规模的函数。 1.时间复杂度 一个程序的时间复杂度是指程序运行从开始到结束所需要的时间。 一个算法是由控制结构和原操作构成的，其执行时间取决于两者的综合效果。为了便于比较同一问题的不同算法，通常的做法是：从算法中选取一种对于所研究的问题来说是基本运算的原操作，以该操作重复执行的次数作为算法的时间度量。在一般情况下，算法中原操作重复执行的次数是规模n的某个函数T（n）。 许多时候要精确地计算T（n）是困难的，我们引入渐近时间复杂度在数量上估计一个算法的执行时间，也能够达到分析算法的目的。 定义（大Ο记号）：如果存在两个正常数c和n0,对于所有的n,当n≥n0时有： f（n）≤ cg（n） 则有： f（n）= Ο（g（n）） 也就是说，随着n的增大，f（n）渐近的不大于g（n）。例如，一个程序的实际执行 程序员 http:// 时间为T（n）=2n3+n2+5,则T（n）=Ο（n3）。T（n）和n3的值随n的增大渐近地靠拢。 使用大Ο记号表示的算法的时间复杂度，称为算法的渐近时间复杂度。 通常用Ο（1）表示常数计算时间。常见的渐近时间复杂度有： Ο（1）<Ο（log2n）<Ο（n）<Ο（nlog2n）<Ο（n2）<Ο（n3）<Ο（2n） 2.空间复杂度 一个程序的空间复杂度是指程序运行从开始到结束所需的存储量。 程序运行所需的存储空间包括以下两部分。 （1）固定部分：这部分空间与所处理数据的大小和个数无关。主要包括程序代码、常量、简单变量和定长成分的结构变量所占的空间。 （2）可变部分：这部分空间大小与算法在某次执行中处理特定数据的大小和规模有关。例如，100个数据元素的排序算法与1 000个数据元素的排序算法所需的存储空间显然是不同的。 算法由数据结构来体现，所以看一个程序首先要搞懂程序实现中所使用的数据结构，如解决装箱问题就使用链表这种数据结构。数据结构是算法的基础，数据结构支持算法，如果数据结构是递归的，算法也可以用递归来实现，如二叉树的遍历。经常采用的算法有迭代法、递推法、递归法、穷举法、贪婪法、分治法和回溯法等，根据考试大纲的要求，对程序员级别的考试，需要考生掌握递归法。 1.2 线性表 线性表是最简单和最常用的一种数据结构，线性表是由相同类型的结点组成的有限序 程序员 http:// 列。一个由n个结点a0,a1,…，an-1组成的线性表可记为（a0,a1,…，an-1）。线性表的结点个数为线性表的长度，长度为0的线性表称为空表。对于非空线性表，a0是线性表的第一个结点，an-1是线性表的最后一个结点。线性表的结点构成一个序列，对序列中两相邻结点ai和ai+1,称ai是ai+1的前驱结点，ai+1是ai的后继结点。其中a0没有前驱结点，an-1没有后继结点。 线性表中结点之间的关系可由结点在线性表中的位置所确定，通常用（ai,ai+1）（0≤i≤n–2）表示两个结点之间的先后关系。例如，如果两个线性表有相同的数据结点，但它们的结点在线性表中出现的顺序不同，则它们是两个不同的线性表。 线性表的结点可由若干个成分组成，其中能唯一标识该结点的成分称为关键字，或简称键。为了讨论方便，往往只考虑结点的关键字，而忽略其他成分。 1.线性表的基本运算 线性表包含的结点个数可以动态地增加或减少，可以在任何位置上插入或删除结点。线性表常用的运算可分成几类，每类有若干种运算，如下所示。 1）查找运算 在线性表中查找具有给定键值的结点。 2）插入运算 在线性表的第i（0≤i≤n–1）个结点的前面或后面插入一个新结点。 3）删除运算 删除线性表的第i（0≤i≤n–1）个结点。 4）其他运算 统计线性表中结点的个数； 程序员 http:// 输出线性表各结点的值； 复制线性表； 线性表分拆； 线性表合并； 线性表排序； 按某种规则整理线性表。 2.线性表的存储 线性表常用的存储方式有顺序存储和链接存储。 1）顺序存储 顺序存储是最简单的存储方式，通常用一个数组，从数组的第一个元素开始，将线性表的结点依次存储在数组中，即线性表的第i个结点存储在数组的第i（0≤i≤n–1）个元素中，用数组元素的顺序存储来体现线性表中结点的先后次序关系。 顺序存储线性表的最大优点就是能随机存取线性表中的任何一个结点。缺点主要有两个：一是数组的大小通常是固定的，不利于任意增加或减少线性表的结点个数；二是插入和删除线性表的结点时，要移动数组中的其他元素，操作复杂。 2）链接存储 链接存储是用链表存储线性表（链表），最简单的是用单向链表，即从链表的第一个结点开始，将线性表的结点依次存储在链表的各结点中。链表的每个结点不但要存储线性表结点的信息，还要用一个域存储其后继结点的指针。单向链表通过链接指针来体现线性表中结点的先后次序关系。 链表存储线性表的优点是线性表的每个结点的实际存储位置是任意的，这给线性表的插 程序员 http:// 入和删除操作带来方便，只要改变链表有关结点的后继指针就能完成插入或删除的操作，不需移动任何表元。链表存储方式的缺点主要有两个：一是每个结点增加了一个后继指针成分，要花费更多的存储空间；二是不方便随机访问线性表的任一结点。 3.线性表上的查找 线性表上的查找运算是指在线性表中找某个键值的结点。根据线性表中的存储形式和线性表本身的性质差异，有多种查找算法，例如顺序查找、二分法查找、分块查找、散列查找等。其中二分法查找需要线性表是一个有序序列。 4.在线性表中插入新结点 1）顺序存储 设线性表结点的类型为整型，插入之前有n个结点，把值为x的新结点插在线性表的第i（0≤i≤n）个位置上。完成插入主要有以下步骤。 检查插入要求的有关参数的合理性； 把原来的第n–1个结点至第i个结点依次往后移一个数组元素的位置； 把新结点放在第i个位置上； 修改线性表的结点个数。 在具有n个结点的线性表上插入新结点，其时间主要花费在移动结点的循环上。若插入任一位置的概率相等，则在顺序存储线性表中插入一个新结点，平均移动次数为n/2.2）链接存储 在链接存储线性表中插入一个键值为x的新结点，分以下4种情况。 在某指针p所指结点之后插入； 插在首结点之前，使待插入结点成为新的首结点； 程序员 http:// 接在线性表的末尾； 在有序链表中插入，使新的线性表仍然有序。 5.删除线性表的结点 1）顺序存储 在有n个结点的线性表中，删除第i（0≤i≤n–1）个结点。删除时应将第i+1个表元至第n–1个结点依次向前移一个数组元素的位置，共移动n–i–1 个结点。完成删除主要有以下几个步骤。 检查删除要求的有关参数的合理性； 把原来第i+1个表元至第n–1个结点依次向前移一个数组元素的位置； 修改线性表表元个数。 在具有n个结点的线性表上删除结点，其时间主要花费在移动表元的循环上。若删除任一表元的概率相等，则在顺序存储线性表中删除一个结点，平均移动次数为n/2.2）链接存储 对于链表上删除指定值结点的删除运算，需考虑几种情况：一是链表为空链表，不执行删除操作；二是要删除的结点恰为链表的首结点，应将链表头指针改为指向原首结点的后继结点；其他情况，先要在链表中寻找要删除的结点，从链表首结点开始顺序寻找。若找到，执行删除操作，若直至链表末尾没有指定值的结点，则不执行删除操作。完成删除由以下几个步骤组成。 如链表为空链表，则不执行删除操作； 若链表的首结点的值为指定值，更改链表的头指针为原首结点的后继结点； 在链表中找指定值的结点； 程序员 http:// 将找到的结点删除。 1.2.1 栈 栈是一种特殊的线性表，栈只允许在同一端进行插入和删除运算。允许插入和删除的一端称为栈顶，另一端称为栈底。称栈的结点插入为进栈，结点删除为出栈。因为最后进栈的结点必定最先出栈，所以栈具有后进先出的特征。 1.顺序存储 可以用顺序存储线性表来表示栈，为了指明当前执行插入和删除运算的栈顶位置，需要一个地址变量top指出栈顶结点在数组中的下标。 2.链接存储 栈也可以用链表实现，用链表实现的栈称为链接栈。链表的第一个结点为顶结点，链表的首结点就是栈顶指针top,top为NULL的链表是空栈。 1.2.2 队列 队列也是一种特殊的线性表，只允许在一端进行插入，另一端进行删除运算。允许删除运算的那一端称为队首，允许插入运算的一端称为队尾。称队列的结点插入为进队，结点删除为出队。因最先进入队列的结点将最先出队，所以队列具有先进先出的特征。 1.顺序存储 可以用顺序存储线性表来表示队列，为了指明当前执行出队运算的队首位置，需要一个指针变量head（称为头指针），为了指明当前执行进队运算的队尾位置，也需要一个指针变量tail（称为尾指针）。 若用有N个元素的数组表示队列，随着一系列进队和出队运算，队列的结点移向存放队列数组的尾端，会出现数组的前端空着，而队列空间已用完的情况。一种可行的解决办法 程序员 http:// 是当发生这样的情况时，把队列中的结点移到数组的前端，修改头指针和尾指针。另一种更好的解决办法是采用循环队列。 循环队列就是将实现队列的数组a[N]的第一个元素a[0]与最后一个元素a[N–1]连接起来。一般地，用tail指向队尾元素的下一个位置（注意，并不是指向最后一个元素本身），用head指向队头元素。队空的初态为 head=tail=0.在循环队列中，当tail 赶上head时，队列满。反之，当head赶上tail时，队列变为空。这样队空和队满的条件都同为head=tail,这会给程序判别队空或队满带来不便。因此，可采用当队列只剩下一个空闲结点的空间时，就认为队列已满，用这种简单办法来区别队空和队满。即对空的判别条件是head=tail,队满的判别条件是head=（tail+1）%N.2.链接存储 队列也可以用链接存储线性表实现，用链表实现的队列称为链接队列。链表的第一个结点是队列首结点，链表的末尾结点是队列的队尾结点，队尾结点的链接指针值为NULL.队列的头指针head 指向链表的首结点，队列的尾指针tail指向链表的尾结点。当队列的头指针head值为NULL时，队列为空。 1.2.3 数组 在计算机中存储一个矩阵时，可使用二维数组。例如，M×N阶矩阵可用一个数组a[M][N]来存储（可按照行优先或列优先的顺序）。如果一个矩阵的元素绝大部分为零，则称为稀疏矩阵。若直接用一个二维数组表示稀疏矩阵，则会因存储太多的零元素而浪费大量的内存空间。因此，通常采用三元组数组或十字链表两种方法来存储稀疏矩阵。 1.三元组数组 稀疏矩阵的每个非零元素用一个三元组来表示，即非零元素的行号、列号和它的值。然 程序员 http:// 后按某种顺序将全部非零元素的三元组存于一个数组中。 如果只对稀疏矩阵的某些单个元素进行处理，则宜用三元组表示。 2.十字链表 在十字链表中，矩阵的非零元素是一个结点，同一行的结点和同一列的结点分别顺序循环链接，每个结点既在它所在行的循环链表中，又在它所在列的循环链表中。每个结点含5个域，分别为结点对应的矩阵元素的行号、列号、值，以及该结点所在行链表后继结点指针、所在列链表后继结点指针。 为了处理方便，通常对每个行链表和列链表分别设置一个表头结点，并使它们构成带表头结点的循环链表。为了方便引用某行某列，全部行链表的表头结点和全部列链表的表头结点分别组成数组，这两个数组的首结点指针存于一个十字链表的头结点中，最后由一个指针指向该头结点，如图1-1所示。 图1-1 十字链表 如果对稀疏矩阵某行或某列整体进行某种处理，可能会使原来为零的元素变为非零，而原来为非零的元素可能变成零。对于这种场合，稀疏矩阵宜用十字链表来表示。 1.2.4 字符串 程序员 http:// 字符串是由某字符集上的字符所组成的任何有限字符序列。当一个字符串不包含任何字符时，称它为空字符串。一个字符串所包含有效字符的个数称为这个字符串的长度。一个字符串中任一连续的子序列称为该字符串的子串。 字符串通常存于足够大的字符数组中，每个字符串的最后一个有效字符之后有一个字符串结束标志，记为' '.通常，由系统提供的库函数形成的字符串末尾会自动添加' ',但当由用户的应用程序来形成字符串时，必须由程序自行负责在最后一个有效字符之后添加' ',以形成字符串。 对字符串的操作通常有： 统计字符串中有效字符的个数； 把一个字符串的内容复制到另一个字符串中； 把一个字符串的内容连接到另一个足够大的字符串的末尾； 在一个字符串中查找另一个字符串或字符； 按字典顺序比较两个字符串的大小。 1.3 树 1.3.1 二叉树 1.二叉树的基本概念 二叉树是一个有限的结点集合，该集合或者为空，或者是由一个根结点及其两棵互不相交的左、右叉子树所组成的。二叉树的结点中有两棵子二叉树，分别称为左子树和右子树。因二叉树可以为空，所以二叉树中的结点可能没有子结点，也可能只有一个左子结点（或右子结点），也可能同时有左右两个子结点。如图1-3所示的是二叉树的4种可能形态（如 程序员 http:// 果把空树计算在内，则共有5种形态）。 图1-3 二叉树的4种不同形态 与树相比，二叉树可以为空，空的二叉树没有结点（树至少有一个结点）；在二叉树中，结点的子树是有序的，分左、右两棵子二叉树。 二叉树常采用类似树的标准存储结构来存储，其结点类型可以用C语言定义如下： typedef struct Btnode{ char data;/*数据*/ strucrt Btnode *lchild;/*左孩子*/ struct Btnode *rchild;/*右孩子*/ }BTNODE; 2.二叉树的性质 二叉树具有下列重要性质（此处省略了推导过程，有兴趣的读者可自行推导）。 性质1:在二叉树的第i层上最多有2i–1个结点（i≥1）。 性质2:深度为k的二叉树最多有2k–1个结点（k≥1）。 性质3:对任何一棵二叉树，如果其叶子结点数为n0,度为2的结点数为n2,则n0=n2+1.一棵深度为k且有2k–1个结点的二叉树称为满二叉树。如图1-4就是一棵满二叉树，对结点进行了顺序编号。 如果深度为k，有n个结点的二叉树中的结点能够与深度为k的顺序编号的满二叉树从1到n标号的结点相对应，则称这样的二叉树为完全二叉树。例如图1-5（a）是一棵完全二叉树，而（b）、（c）是两棵非完全二叉树。显然，满二叉树是完全二叉树的特例。 程序员 http:// 图1-4 满二叉树的例子 图1-5 完全二叉树、非完全二叉树的例子 根据完全二叉树的定义，显然，在一棵完全二叉树中，所有的叶子结点都出现在第k层或k-1层（最后两层）。 性质4:具有n个结点的完全二叉树的深度为[log2n]+1（注：[m]表示不大于m的最大整数，如[4]= 4、[4.1]= 4、[4.9]=4,下同）。 性质5:如果对一棵有n个结点的完全二叉树的结点按层序编号（从第1层到第[log2n]+1层，每层从左到右），则对任一结点i（1≤i≤n），有： （1）如果i=1，则结点i无双亲，是二叉树的根；如果i>1,则其双亲是结点[i/2]。 （2）如果2i>n，则结点i为叶子结点，无左孩子；否则，其左孩子是结点2i。 （3）如果2i+1>n，则结点i无右孩子；否则，其右孩子是结点2i+1。 3.二叉树的遍历 树的所有遍历方法也同样适用于二叉树，此外，由于二叉树自身的特点，还有中序遍历方法。 （1）前序遍历（先根遍历，先序遍历）：首先访问根结点，然后按前序遍历根结点的左子树，再按前序遍历根结点的右子树。 （2）中序遍历（中根遍历）：首先按中序遍历根结点的左子树，然后访问根结点，再按中序遍历根结点的右子树。 程序员 http:// （3）后序遍历（后根遍历，后序遍历）：首先按后序遍历根结点的左子树，然后按后序遍历根结点的右子树，再访问根结点。 例如，图1-6所示的二叉树，其前序遍历、中序遍历和后序遍历结果分别如下。 （1）前序遍历：1,2,4,5,7,8,3,6。 （2）中序遍历：4,2,7,8,5,1,3,6。 （3）后序遍历：4,8,7,5,2,6,3,1。 以上3种遍历方法都是递归定义的，可通过递归函数分别给以实现。 性质6：一棵二叉树的前序序列和中序序列可以唯一地确定这棵二叉树。 根据性质6，给定一棵二叉树的前序遍历序列和中序遍历序列，我们可以写出该二叉树的后序遍历序列。例如，某二叉树的前序遍历序列为ABHFDECKG、中序遍历序列为HBDFAEKCG，则构造二叉树的过程如图1-7所示。 程序员 http:// 图1-7 已知前序遍历序列和中序序列，求二叉树的过程 1.3.2 二叉排序树 二叉排序树又称为二叉查找树，其定义为：二叉排序树或者是一棵空树，或者是具有如下性质（BST性质）的二叉树。 （1）若它的左子树非空，则左子树上所有结点的值均小于根结点； （2）若它的右子树非空，则右子树上所有结点的值均大于根结点； （3）左、右子树本身又各是一棵二叉排序树。 例如，图1-8就是一棵二叉排序树。 根据二叉排序树的定义可知，如果中序遍历二叉排序树，就能得到一个排好序的结点序列。二叉排序树上有查找、插入和删除3种操作。下面，我们假设二叉排序树的结点只存储结点的键值，其类型与前面的二叉树的结点类型相同。 1.静态查找 程序员 http:// 静态查找是在二叉排序树上查找键值为key的结点是否存在，可按以下步骤在二叉排序树ST上找值为key的结点： （1）如果二叉排序树ST为空二叉树，则查找失败，结束查找； （2）如果二叉排序树根结点的键值等于key,则查找成功，结束查找； （3）如果key小于根结点的键值，则沿着根结点的左子树查找，即根结点的左子树作为新的二叉排序树ST继续查找； （4）如果key大于根结点的键值，则沿着根结点的右子树查找，即将根结点的右子树作为新的二叉排序树ST继续查找。 2.动态查找 在二叉排序树上，为插入和删除操作而使用的查找称为动态查找，动态查找应得到两个指针，一个指向键值为key的结点，另一个指向该结点的父结点。为此，查找函数可设4个参数：查找树的根结点指针root、待查找值key、存储键值为key结点的父结点的指针pre,存储键值为key以及结点的指针p.但函数要考虑以下几种不同的情况： （1）二叉排序树为空，查找失败，函数使*p=NULL,*pre=NULL; （2）二叉排序树中没有键值为key的结点，函数一直寻找至查找路径的最后一个结点，*pre指向该结点，*p=NULL,如果插入键值为key的结点，就插在该结点下； （3）查找成功，*p指向键值为key的结点，*per指向它的父结点。 3.插入结点 首先利用动态查找函数确定新结点的插入位置，然后分以下几种情况作为相应的处理： （1）如果相同键值的结点已在二叉排序中，则不再插入； （2）如果二叉排序为空树，则以新结点为二叉排序树； 程序员 http:// （3）根据要插入结点的键值与插入后的父结点的键值比较，就能确定新结点是父结点的左子结点，还是右子结点，并进行相应的插入。 4.删除结点 删除二叉排序树上键值为key的结点的操作可按以下步骤进行。 （1）调用查找函数确定被删结点的位置； （2）如果被删除结点不在二叉排序树上，则函数返回。否则，按以下情况分别处理。 ①如果被删除的结点是根结点，又可分以下两种情况。 l被删除结点无左子树，则以被删除结点的右子树作为删除后的二叉排序树； l被删除结点有左子树，则用被删除结点的左子结点作为根结点，并把被删除结点的右子树作为被删除结点的左子树按中序遍历的最后一个结点的右子树。 ②如果被删除结点不是根结点，且被删除结点无左子结点，则，l被删除结点是它父结点的左子结点，则把被删除结点的右子树作为被删除结点父结点的左子树； l被删除结点是它父结点的右子结点，则把被删除结点的右子树作为被删除结点父结点的右子树； ③如果被删除结点不是根结点，且被删除结点无左子结点，则被删除结点的右子树作为被删除结点的左子树按中序遍历的最后一个结点的右子树，同时进行以下操作： l被删除结点是它父结点的左子结点，则把被删除结点的左子树作为被删除结点父结点的左子树； 被删除结点是它父结点的右子结点，则把被删除结点的左子树作为被删除结点父结点的右子树。 程序员 http:// 1.3.3 最优二叉树 树的路径长度是从树根到树中每一结点的路径长度之和。在结点数目相同的二叉树中，完全二叉树的路径长度最短。在一些应用中，赋予树中结点的一个有某种意义的实数，这些数字称为结点的权。结点到树根之间的路径长度与该结点上权的乘积，称为结点的带权路径长度。树中所有叶子结点的带权路径长度之和，称为树的带权路径长度（树的代价），通常记为： 其中n表示叶子结点的数目，wi和li分别表示叶子结点ki的权值和根到结点ki之间的路径长度。 在权为wl,w2,…，wn的n个叶子所构成的所有二叉树中，带权路径长度最小（即代价最小）的二叉树称为最优二叉树或哈夫曼树。 假设有n个权值，则构造出的哈夫曼树有n个叶子结点。n个权值分别设为 w1,w2,…，wn,则哈夫曼树的构造规则如下： （1）将w1,w2,…，wn看成是有n 棵树的森林（每棵树仅有一个结点）； （2）在森林中选出两个根结点权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和； （3）从森林中删除选取的两棵树，并将新树加入森林。 重复第（2）步和第（3）步，直到森林中只剩一棵树为止，该树即为所求的哈夫曼树。 例如，如果叶子结点的权值分别为1、2、3、4、5、6,则构造哈夫曼树的过程如图1-9所示。 程序员 http:// 图1-9 哈夫曼树的构造过程 在构造哈夫曼树的过程中，每次都是选取两棵最小权值的二叉树进行合并，因此使用的是贪心算法。 给定结点序列 （1）用字符ci作为叶子，pi作为ci的权，构造一棵哈夫曼树，并将树中左分支和右分支分别标记为0和1; （2）将从根到叶子路径上的标号依次相连，作为该叶子所表示字符的编码。该编码即为最优前缀码。 给定字符集的哈夫曼树生成后，求哈夫曼编码的具体实现过程是：依次以叶子结点c[i]（0≤i≤n–1）为出发点，向上回溯至根为止。向上时走左分支则生成代码0,走右分支则生成代码1.需要注意以下几个问题： （1）由于生成的编码与要求的编码反序，将生成的代码先从后往前依次存放在一个临时串中，并设一个指针start指示编码在该串中的起始位置（start初始时指示串的结束位置）； 程序员 http:// （2）当某字符编码完成时，从临时串的start处将编码复制到该字符相应的位串bits中即可； （3）因为字符集大小为n,故变长编码的长度不会超过n,加上一个结束符“ ”,bits的大小应为n+1.给定一个序列的集合，若不存在一个序列是另一个序列的前缀，则该序列集合称为前缀码。相反，给定一个序列的集合，若不存在一个序列是另一个序列的后缀，则该序列集合称为后缀码。平均码长或文件总长最小的前缀编码称为最优的前缀码，最优的前缀码对文件的压缩效果亦最佳。 平均码长 = 式中pi为第i个字符的概率，li为码长。 利用哈夫曼树很容易求出给定字符集及其概率（或频度）分布的最优前缀码。哈夫曼编码是一种应用广泛且非常有效的数据压缩技术，该技术一般可将数据文件压缩掉20%~90%,其压缩效率取决于被压缩文件的特征。 1.4 图 在线性结构（例如队列和栈）中，除第一个结点没有前驱，最后一个结点没有后继之外，每一个结点都有唯一的一个前驱和后继。在树形结构（如树和二叉树）中，除根结点没有前驱外，一个结点只有一个前驱，但可以有若干个后继。在图结构中，一个结点的前驱和后继的个数都是任意的。 1.4.1 图的基础知识 程序员 http:// 1.图的基本概念 图G由两个集合V和E组成，记为G=（V,E），其中V是顶点的有穷非空集合，E是V中顶点偶对（称为边）的有穷集合。通常，也将图G的顶点集和边集分别记为V（G）和E（G）。E（G）可以是空集。若E（G）为空，则图G只有顶点而没有边。 图分为有向图和无向图两种。如图1-10（a）所示是一个有向图，在有向图中，一条有向边是由两个顶点组成的有序对，有序对通常用尖括号表示。 如图1-10（b）所示是一个无向图，无向图中的边均是顶点的无序对，无序对通常用圆括号表示。在无向图G中，如果i≠j,i、j∈V,（i,j）∈E,即i和j是G的两个不同的顶点，（i,j）是G中一条边，顶点i和顶点j是相邻的顶点，边（i,j）是与顶点i和j相关联的边。 如果限定任何一条边或弧的两个顶点都不相同，则有n个顶点的无向图最多有n（n–1）/2条边，这样的无向图称为无向完全图。一个有向图最多有n（n–1）条弧，这样的有向图称为有向完全图。 如果同为无向图或同为有向图的两个图G1=（V1,E1）和G2=（V2,E2），满足V2V1且 E2E1,则称图G2是图G1的子图。 在无向图中，一个顶点的度等于与其相邻接的顶点个数。在有向图中，一个顶点的入度 程序员 http:// 等于邻接到该顶点的顶点个数，其出度等于邻接于该顶点的个数。 在图G=（V,E）中，如果存在顶点序列（V0,V1,…，Vk），其中V0=P,Vk=Q,且（V0,V1），（V1,V2），…，（Vk-1,Vk）都在E中，则称顶点P到顶点Q有一条路径，并用（V0,V1,…，Vk）表示这条路径，路径的长度是路径的边数，这条路径的长度为k.若G是有向图，则路径也是有向的。 在有向图G中，若对于V（G）中任意两个不同的顶点Vi和Vj,都存在从Vi到Vj及从Vj到Vi的路径，则称G是强连通图。 有向图的极大强连通子图称为G的强连通分量。强连通图只有一个强连通分量，即其自身。非强连通的有向图有多个强连通分量。 2.图的存储结构 最常用的图的存储结构有邻接矩阵和邻接表。 1）邻接矩阵 邻接矩阵反映顶点间的邻接关系，设G=（V,E）是具有n（n≥1）个顶点的图，G的邻接矩阵M是一个n行n列的矩阵，若（i,j）或 由邻接矩阵的定义可知，无向图的邻接矩阵是对称的，有向图的邻接矩阵不一定对称。对于无向图，其邻接矩阵第i行元素的和即为顶点i的度。对于有向图，其邻接矩阵第i行元素之和为顶点i的出度，而邻接矩阵第j列元素之和为顶点j的入度。 程序员 http:// 若将图的每条边都赋上一个权，则称这种带权图为网（络）。如果图G=（V,E）是一个网，若（i,j）或 2）邻接表 在图的邻接表表示中，为图的每个顶点建立一个链表，且第i个链表中的结点代表与顶点i相关联的一条边或由顶点i出发的一条弧。有n个顶点的图，需用n个链表表示，这n个链表的头指针通常由顺序线性表存储。例如，图1-10（a）和图1-10（b）的邻接表分别如图1-11（a）和图1-11（b）所示。 图1-11 图的邻接表表示 在无向图的邻接表中，对应某结点的链表的结点个数就是该顶点的度。在有向图的邻接表中，对应某结点的链表的结点个数就是该顶点的出度。 3.图的遍历 和树的遍历类似，图的遍历也是从某个顶点出发，沿着某条搜索路径对图中每个顶点各做一次且仅做一次访问。它是许多图的算法的基础。深度优先遍历和广度优先遍历是最为重要的两种遍历图的方法。它们对无向图和有向图均适用。 1）深度优先遍历 在G中任选择一顶点V为初始出发点（源点），则深度优先遍历可以定义如下：首先，访问出发点V,并将其标记为已访问过；然后，依次从V出发搜索V的每个邻接点W.若W 程序员 http:// 未曾访问过，则以W为新的出发点继续进行深度优先遍历，直至图中所有和源点V有路径相通的顶点（亦称为从源点可达的顶点）均已被访问为止。若此时图中仍有未访问的顶点，则另选一个尚未访问的顶点作为新的源点重复上述过程，直至图中所有的顶点均已被访问为止。 图的深度优先遍历类似于树的前序遍历。对于无向图，如果图是连通的，那么按深度优先遍历时，可遍历全部顶点，得到全部顶点的一个遍历序列。如果遍历序列没有包含所有顶点，那么该图是不连通的。 2）广度优先遍历 广度优先遍历的过程是：首先访问出发顶点V;然后访问与顶点V邻接的全部未被访问过的顶点W0,W1,…，Wk-1;接着再依次访问与顶点W0,W1,…，Wk-1邻接的全部未被访问过的顶点。依此类推，直至图的所有顶点都被访问到，或出发顶点V所在的连通分量的全部顶点都被访问到为止。 从广度优先搜索遍历过程知，若顶点V在顶点W之前被访问，则对V相邻顶点的访问就先于只与W相邻的那些顶点的访问。因此，需要一个队列来存放被访问过的顶点，以便按顶点的访问顺序依次访问这些顶点相邻接的其他还未被访问过的顶点。 1.4.2 最小生成树 如果连通图G的一个子图是一棵包含G的所有顶点的树，则该子图称为G的生成树。生成树是连通图包含图中的所有顶点的极小连通子图。值得注意的是，图的生成树并不唯一。从不同的顶点出发进行遍历，可以得到不同的生成树。 含有n个顶点的连通图的生成树有n个顶点和n–1条边。对一个带权的图（网），在一棵生成树中，各条边的权植之和称为这棵生成树的代价。其中代价最小的生成树称为最小 程序员 http:// 代价生成树（简称最小生成树）。 MST性质：设G=（V,E）是一个连通网络，U是顶点集V的一个真子集。若（u,v）是G中所有的一个端点在U（u∈U）里、另一个端点不在U（即v∈V–U）里的边中，具有最小权值的一条边，则一定存在G的一棵最小生成树包括此边（u,v）。 求连通的带权无向图的最小代价生成树的算法有普里姆（Prim）算法和克鲁斯卡尔（Kruskal）算法。 1.普里姆算法 设已知G=（V,E）是一个带权连通无向图，顶点V={0,1,2,…，n–1}.设U是构造生成树过程中已被考虑在生成树上的顶点的集合。初始时，U只包含一个出发顶点。设T是构造生成树过程中已被考虑在生成树上的边的集合，初始时T为空。如果边（i,j）具有最小代价，且i∈U,j∈V–U,那么最小代价生成树应包含边（i,j）。把j加到U中，把（i,j）加到T中。重复上述过程，直到U等于V为止。这时，T即为要求的最小代价生成树的边的集合。 普里姆算法的特点是当前形成的集合T始终是一棵树。因为每次添加的边是使树中的权尽可能小，因此这是一种贪心的策略。普里姆算法的时间复杂度为O（n2），与图中的边数无关，所以适合于稠密图。 2.克鲁斯卡尔算法 设T的初始状态只有n个顶点，而无边的森林T=（V,φ），按边长递增的顺序选择E中的n–1安全边（u,v）并加入T,生成最小生成树。所谓安全边，是指两个端点分别是森林T里两棵树中顶点的边。加入安全边，可以将森林中的两棵树连接成一棵更大的树，因为每一次添加到T中的边均是当前权值最小的安全边，MST性质也能保证最终的T是一棵最小生成树。 程序员 http:// 克鲁斯卡尔算法的特点，是当前形成的集合T除最后的结果外，始终是一个森林。克鲁斯卡尔算法的时间复杂度为O（elog2e），与图中的顶点数无关，所以较适合于稀疏图。 1.4.3 最短路径 带权图的最短路径问题即求两个顶点间长度最短的路径。其中，路径长度不是指路径上边数的总和，而是指路径上各边权值的总和。路径长度的具体含义取决于边上权值所代表的意义。 1.单源最短路径 已知有向带权图（简称有向网）G=（V,E），找出从某个源点s∈V到V中其余各顶点的最短路径，称为单源最短路径。 目前，求单源最短路径主要使用迪杰斯特拉（Dijkstra）提出的一种按路径长度递增序产生各顶点最短路径的算法。若按长度递增的次序生成从源点s到其他顶点的最短路径，则当前正在生成的最短路径上除终点以外，其余顶点的最短路径均已生成（将源点的最短路径看成是已生成的源点到其自身的长度为0的路径）。 迪杰斯特拉算法的基本思想是：设S为最短距离已确定的顶点集（看成红点集），V-S是最短距离尚未确定的顶点集（看成蓝点集）。 （1）初始化：初始化时，只有源点s的最短距离是已知的（SD（s）=0），故红点集S={s},蓝点集为空。 （2）重复以下工作，按路径长度递增的次序产生各顶点的最短路径：在当前蓝点集中选择一个最短距离最小的蓝点来扩充红点集，以保证算法按路径长度递增的次序产生各顶点的最短路径。当蓝点集中仅剩下最短距离为∞的蓝点，或者所有的蓝点已扩充到红点集时，s到所有顶点的最短路径就求出来了。 程序员 http:// 需要注意的是： （1）若从源点到蓝点的路径不存在，则可假设该蓝点的最短路径是一条长度为无穷大的虚拟路径。 （2）从源点s到终点v的最短路径简称为v的最短路径；从s到v的最短路径长度简称为v的最短距离，并记为SD（v）。 根据按长度递增的次序产生最短路径的思想，当前最短距离最小的蓝点k的最短路径是： 源点，红点1,红点2,……，红点n,蓝点k 距离为： 源点到红点n最短距离 + <红点n,蓝点k>的边长。 为求解方便，可设置一个向量D[0…n–1],对于每个蓝点v∈V–S,用D[v]记录从源点s到达v且除v外中间不经过任何蓝点（若有中间点，则必为红点）的“最短”路径长度（简称估计距离）。若k是蓝点集中估计距离最小的顶点，则k的估计距离就是最短距离，即若D[k]=min{D[i] i∈V–S},则D[k]=SD（k）。 初始时，每个蓝点v的D[c]值应为权w 程序员 http:// 2.每一对顶点之间的最短路径 对图中每对顶点u和v,找出u到v的最短路径问题。这一问题可用每个顶点作为源点调用一次单源最短路径问题的迪杰斯特拉算法予以解决。 但更常用的是弗洛伊德（Folyd）提出的求每一对顶点之间的最短路径的算法。设G=（V,E）是有n个顶点的有向图，顶点集合V={0,1,…，n–1}.图用邻接矩阵M表示。Floyd算法的基本思想是递推地产生一个矩阵序列C0,C1,C2,…，Cn,其中C0是已知的带权邻接矩阵a,Ck（i,j）（0≤i,j 设在第k次递推之前已求得Ck-1（i,j）（0≤i,j （1）如果从顶点i到顶点j的最短路径不经过顶点k,则由Ck（i,j）定义知，从i到j中间的顶点序号不大于k的最短路径长度还是Ck-1（i,j）即Ck（i,j）=Ck-1（i,j）。 （2）如果从顶点i到顶点j的最短路径要经过顶点k,则这样的一条路径是由 i到k和由k到j的两条路径所组成的。由于Ck-1（i,k）和Ck-1（k,j）分别表示i到k和从k到j的中间顶点序号不大于k-1的最短路径长度，若Ck-1（i,k）+Ck-1（k,j） 程序员 http:// 1.5 排序与查找 所谓排序，就是要整理文件中的记录，使之按关键字递增（或递减）的次序排列起来。当待排序记录的关键字均不相同时，排序结果是唯一的，否则排序结果不是唯一的。 在待排序的文件中，若存在多个关键字相同的记录，经过排序后这些具有相同关键字的记录之间的相对次序保持不变，该排序方法是稳定的；若具有相同关键字的记录之间的相对次序发生变化，则称这种排序方法是不稳定的。 要注意的是，排序算法的稳定性是针对所有的输入实例而言的。即在所有可能的输入实例中，只要有一个实例使得算法不满足稳定性要求，则该排序算法就是不稳定的。 1.5.1 插入排序 插入排序的基本思想是，每步将一个待排序的记录按其排序码值的大小，插到前面已经排好的文件中的适当位置，直到全部插入完为止。插入排序方法主要有直接插入排序和希尔排序。 1.直接插入排序 直接插入排序的过程是，在插入第i个记录时，R1,R2,…，Ri-1已经排好序，将第i个记录的排序码ki依次和R1,R2,…，Ri-1的排序码逐个进行比较，找到适当的位置。 使用直接插入排序，对于具有n个记录的文件，要进行n–1趟排序。各种状态下的时间复杂度如表1-1所示。 表1-1 直接插入排序有关数据 程序员 http:// 说明：初始文件按关键字递增排序，简称“正序”,初始文件按关键字递减排序，简称“反序”.2.希尔排序 希尔（Shell）排序的基本思想是，先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。所有距离为dl的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2 一般取d1=n/2,di+1=di/2.如果结果为偶数，则加1,保证di为奇数。 例如，要对关键码{72,28,51,17,96,62,87,33,45,24}进行排序，这里n=10,首先取d1=n/2=5.则排序过程如图1-12所示。 图1-12 希尔排序的过程 希尔排序是不稳定的，希尔排序的执行时间依赖于增量序列，有人在大量实验的基础上指出，当n在某个特定范围内时，希尔排序的平均时间复杂度为O（n1.3）。 1.5.2 选择排序 选择排序的基本思想是每步从待排序的记录中选出排序码最小的记录，顺序存放在已排序的记录序列后面，直到全部排完。选择排序中主要使用直接选择排序和堆排序。 程序员 http:// 直接选择排序的过程是，首先在所有记录中选出排序码最小的记录，把它与第一个记录交换，然后在其余的记录内选出排序码最小的记录，与第二个记录交换……，依次类推，直到所有记录排完为止。 无论文件初始状态如何，在第i趟排序中选出最小关键字的记录，需进行n–i次比较，因此，总的比较次数为n（n–1）/2=O（n2）。当初始文件为正序时，移动次数为0;文件初态为反序时，每趟排序均要执行交换操作，总的移动次数取最大值3（n–1）。直接选择排序的平均时间复杂度为O（n2）。直接选择排序是不稳定的。 1.5.3 交换排序 交换排序的基本思想是，两两比较待排序记录的排序码，并交换不满足顺序要求的那些偶对，直到满足条件为止。交换排序的主要方法有冒泡排序和快速排序。 1.冒泡排序 冒泡排序将被排序的记录数组R[1…n]垂直排列，每个记录R[i]看成是重量为ki的气泡。根据轻气泡不能在重气泡之下的原则，从下往上扫描数组R,凡扫描到违反本原则的轻气泡，就使其向上“飘浮”.如此反复进行，直到最后任何两个气泡都是轻者在上，重者在下为止。 冒泡排序的具体过程如下。 第一步，先比较k1和k2,若k1>k2,则交换k1和k2所在的记录，否则不交换。继续对k2和k3重复上述过程，直到处理完kn-1和kn.这时最大的排序码记录转到了最后位置，称第一次起泡。共执行n–1次比较。 与第一步类似，从k1和k2开始比较，到kn-2和kn-1为止，共执行n–2次比较。称第二次起泡。 依此类推，共进行n–1次起泡，完成整个排序过程。 程序员 http:// 若文件的初始状态是正序的，一趟扫描即可完成排序。所需的关键字比较次数为n–1次，记录移动次数为0.因此，冒泡排序最好的时间复杂度为O（n）。 若初始文件是反序的，需要进行n–1趟排序。每趟排序要进行n–i次关键字的比较（1≤i≤n-1），且每次比较都必须移动记录3次来达到交换记录位置的目的。在这种情况下，比较次数达到最大值n（n–1）/2=O（n2），移动次数也达到最大值3n（n–1）/2=O（n2）。因此，冒泡排序的最坏时间复杂度为O（n2）。 虽然冒泡排序不一定要进行n–1趟，但由于它的记录移动次数较多，故平均时间性能比直接插入排序要差得多。冒泡排序是就地排序，且它是稳定的。 2.快速排序 快速排序采用了一种分治的策略，通常称其为分治法。其基本思想是，将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题，然后将这些子问题的解组合为原问题的解。 快速排序的具体过程如下。 第一步，在待排序的n个记录中任取一个记录，以该记录的排序码为准，将所有记录分成两组，第一组各记录的排序码都小于等于该排序码，第二组各记录的排序码都大于该排序码，并把该记录排在这两组中间。 第二步，采用同样的方法，对左边的组和右边的组进行排序，直到所有记录都排到相应的位置为止。 例如，要对关键码{7,2,5,1,9,6,8,3}进行排序，选择第一个元素为基准。第一趟排序的过程如图1-13所示。 要注意的是，在快速排序中，选定了第一个元素为基准，接着就拿最后一个元素和第一 程序员 http:// 个元素比较，如果大于第一个元素，则保持不变，再拿倒数第二个元素和基准比较；如果小于基准，则进行交换。交换之后，再从前面的元素开始与基准比较，如果小于基准，则保持不变；如果大于基准，则交换。交换之后，再从后面开始比较，依此类推，前后交叉进行。 然后，再采取同样的办法对{3,2,5,1,6}和{8,9}分别进行排序，具体过程如图1-14所示。 图1-13 第一趟排序过程 图1-14 各趟排序过程 快速排序的时间主要耗费在划分操作上，对长度为k的区间进行划分，共需k–1次关键字的比较。 最坏情况是每次划分选取的基准都是当前无序区中关键字最小（或最大）的记录，划分的结果是基准左边的子区间为空（或右边的子区间为空），而划分所得的另一个非空的子区间中记录数目，仅仅比划分前的无序区中记录个数减少一个。因此，快速排序必须进行n-1次划分，第i次划分开始时区间长度为n–i+1,所需的比较次数为n–i（1≤i≤n-1），故总的比较次数达到最大值n（n-1）/2=O（n2）。如果按上面给出的划分算法，每次取当前无序区的第1个记录为基准，那么当文件的记录已按递增次序（或递减次序）排列时，每次划分所取的基准就是当前无序区中关键字最小（或最大）的记录，则快速排序所需的比较次数反而最多。 在最好情况下，每次划分所取的基准都是当前无序区的“中值”记录，划分的结果是基准 程序员 http:// 的左、右两个无序子区间的长度大致相等。总的关键字比较次数为O（nlog2n）。 因为快速排序的记录移动次数不大于比较的次数，所以快速排序的最坏时间复杂度应为O（n2），最好时间复杂度为O（nlog2n）。 尽管快速排序的最坏时间为O（n2），但就平均性能而言，它是基于关键字比较的内部排序算法中速度最快者，快速排序亦因此而得名。它的平均时间复杂度为O（nlog2n）。快速排序在系统内部需要一个栈来实现递归。若每次划分较为均匀，则其递归树的高度为O（log2n），故递归后需栈空间为O（log2n）。在最坏的情况下，递归树的高度为O（n），所需的栈空间为O（n）。快速排序是不稳定的。 1.5.4 归并排序 归并排序是将两个或两个以上的有序子表合并成一个新的有序表。初始时，把含有n个结点的待排序序列看为有n个长度都为1的有序子表所组成，将它们依次两两归并得到长度为2的若干有序子表，再对它们进行两两合并。直到得到长度为n的有序表，排序结束。 例如，需要对关键码{72,28,51,17,96,62,87,33}进行排序，其归并过程如图1-15所示。 归并排序是一种稳定的排序，可用顺序存储结构。也易于在链表上实现。对长度为n的文件，需进行log2n趟二路归并，每趟归并的时间为O（n），故其时间复杂度无论是在最好情况下还是在最坏情况下均是O（nlog2n）。归并排序需要一个辅助向量来暂存两个 程序员 http:// 有序子文件归并的结果，故其辅助空间复杂度为O（n），显然它不是就地排序。 1.5.5 基数排序 设单关键字的每个分量的取值范围均是C0≤kj≤Crd–1（0≤j （1）若关键字是十进制整数，则按个、十等位进行分解，基数rd=10,C0=0,C9=9,d为最长整数的位数。 （2）若关键字是小写的英文字符串，则rd=26,C0='a',C25='z',d为字符串的最大长度。 基数排序的基本思想是：从低位到高位依次对待排序的关键码进行分配和收集，经过d趟分配和收集，就可以得到一个有序序列。 基数排序的具体实现过程如下：设有r个队列，队列的编号分别为0,1,2,…，r–1.首先按最低有效位的值把n个关键字分配到这r个队列中；然后从小到大将各队列中的关键字再依次收集起来；接着再按次低有效位的值把刚刚收集起来的关键字分配到r个队列中。重复上述收集过程，直至最高有效位，这样便得到一个从小到大的有序序列。为减少记录移动的次数，队列可以采用链式存储分配，称为链式基数排序。每个队列设有两个指针，分别指向队头和队尾。 例如，需要对{288,371,260,531,287,235,56,299,18,23}进行排序，因为这些数据最高位为百位，所以需要3趟分配和收集。第1趟分配和收集（按个位数）的过程如图1-16所示；第2趟分配与收集（按十位数）的过程如图1-17所示；第3趟分配与收集（按百位数）的过程如图1-18所示。 程序员 http:// 图1-16 第1趟分配与收集 图1-17 第2趟分配与收集 图1-18 第3趟分配与收集 基数排序的时间复杂度为O（d（r+n）），所需的辅助存储空间为O（n+rd），基数排序是稳定的。 1.5.6 顺序查找 顺序查找的基本思想是，从表的一端开始，顺序扫描线性表，依次将扫描到的结点关键字和给定值k相比较。若当前扫描到的结点关键字与k相等，则查找成功；若扫描结束后，仍未找到关键字等于k的结点，则查找失败。顺序查找方法既适用于线性表的顺序存储结构，程序员 http:// 也适用于线性表的链式存储结构。 成功时顺序查找的平均查找长度如下： 在等概率的情况下，pi=1/n（1≤i≤n），故成功的平均查找长度为（n+…+2+1）/n=（n+1）/2，即查找成功时的平均比较次数约为表长的一半。若k值不在表中，则须进行n+1次比较之后才能确定查找失败。 若事先知道表中各结点的查找概率不相等和它们的分布情况，则应将表中的结点按查找概率由小到大地存放，以便提高顺序查找的效率。 顺序查找的优点是算法简单，且对表的结构无任何要求，无论是用向量还是用链表来存放结点，也无论结点之间是否按关键字排序，它都同样适用。缺点是查找效率低，因此，当n较大时不宜采用顺序查找。 1.5.7 二分法查找 二分法查找又称折半查找，它是一种效率较高的查找方法。二分法查找要求线性表是有序表，即表中的结点按关键字排序，并且要用向量作为表的存储结构。 二分法查找的基本思想如下（设R[low,…，high]是当前的查找区间）。 （1）确定该区间的中点位置：mid=[（low+high）/2]; （2）将待查的k值与R[mid].key比较，若相等，则查找成功并返回此位置，否则须确定新的查找区间，继续二分查找，具体方法如下： 若R[mid].key>k,则由表的有序性可知R[mid,…，n].key均大于k,因此若表中存在关键字等于k的结点，则该结点必定是在位置mid左边的子表R[low,…，mid-1]中。因此，程序员 http:// 新的查找区间是左子表R[low,…，high],其中high=mid-1.若R[mid].key （3）下一次查找时针对新的查找区间进行，重复步骤（1）和（2）。 （4）在查找过程中，low逐步增加，而high逐步减少。如果high 因此，从初始的查找区间R[1,…，n]开始，每经过一次与当前查找区间中点位置上的结点关键字比较，就可以确定查找是否成功，不成功则当前的查找区间就缩小一半。这一过程重复直至找到关键字为k的结点，或者直至当前的查找区间为空（即查找失败）时为止。 例如，我们要在{11,13,17,23,31,36,40,47,52,58,66,73,77,82,96,99}中查找58的过程如图1-19所示（粗体表示mid位置）。在上述序列中查找35的过程如图1-20所示。 图1-19 二分法查找58 图1-20 二分法查找35 二分法查找过程可用二叉树来描述：把当前查找区间的中间位置上的结点作为根，左子表和右子表中的结点分别作为根的左子树和右子树。由此得到的二叉树，称为描述二分查找的判定树或比较树。要注意的是，判定树的形态只与表结点的个数n相关，而与输入实例中R[1,…，n].key的取值无关。 设内部结点的总数为n=2h–1,则判定树是深度为h=log2（n+1）的满二叉树。树中第k层上的结点个数为2k–1,查找它们所需的比较次数是k.因此在等概率假设下，二分法查 程序员 http:// 找成功时的平均查找长度约为log2（n+1）–1.二分法查找在查找失败时所需比较的关键字个数不超过判定树的深度，在最坏情况下查找成功的比较次数也不超过判定树的深度，即为[log2 n]+1.二分法查找的最坏性能和平均性能相当接近。 虽然二分法查找的效率高，但是要将表按关键字排序。而排序本身是一种很费时的运算。即使采用高效率的排序方法也要花费o（nlog2n）的时间。二分法查找只适用顺序存储结构。为保持表的有序性，在顺序结构里插入和删除都必须移动大量的结点。因此，二分法查找特别适用于那种一经建立就很少改动，而又经常需要查找的线性表。 对那些查找少而又经常需要改动的线性表，可采用链表作为存储结构，进行顺序查找。链表上无法实现二分法查找。 1.5.8 分块查找 分块查找（Blocking Search）又称索引顺序查找。它是一种性能介于顺序查找和二分法查找之间的查找方法。二分法查找表由分块有序的线性表和索引表组成。表R[1,…，n]均分为b块，前b–1块中结点个数为s=[n/b],第b块的结点数允许小于等于s;每一块中的关键字不一定有序，但前一块中的最大关键字必须小于后一块中的最小关键字，即表是分块有序的。 抽取各块中的最大关键字及其起始位置构成一个索引表ID[l,…，b],即ID[i]（1≤i≤b）中存放第i块的最大关键字及该块在表R中的起始位置。由于表R是分块有序的，所以索引表是一个递增有序表。 分块查找的基本思想是：索引表是有序表，可采用二分法查找或顺序查找，以确定待查的结点在哪一块。 由于块内无序，只能用顺序查找。分块查找是两次查找过程。整个查找过程的平均查找 程序员 http:// 长度是两次查找的平均查找长度之和。如果以二分查找来确定块，则分块查找成功时的平均查找长度为ASL1 = log2（b+1）–1+（s+1）/2≈log2（n/s+1）+s/2;如果以顺序查找确定块，分块查找成功时的平均查找长度为ASL2 =（b+1）/2+（s+1）/2=（s2+2s+n）/（2s）。 注意，当块中的结点数选定为时ASL2取极小值。，即当采用顺序查找确定块时，应将各 分块查找的优点是：在表中插入或删除一个记录时，只要找到该记录所属的块，就可以在该块内进行插入和删除运算；因块内记录的存放是任意的，所以插入或删除比较容易，无须移动大量记录。 分块查找的主要代价是增加一个辅助数组的存储空间和将初始表分块排序的运算。 1.6 递归法 递归是一种特别有用的工具，不仅在数学中广泛应用，在日常生活中也常常遇到。例如一个画家所制作的如图1-21所示的一幅画便是一种递归的图形。 递归是设计和描述算法的一种有力的工具，由于它在复杂算法的描述中被经常采用，能采用递归描述的算法通常有这样的特征：为求解规模为N的问题，设法将它分解成规模较小的问题，然后从这些小问题的解中方便地构造出大问题的解，并且这些规模较小的问题也能采用同样的分解和综合方法，分解成规模更小的问题，并从这些更小问题的解中构造出规 程序员 http:// 模较大问题的解。特别地，当规模N=1时，能直接得解。 递归算法包括“递推”和“回归”两部分。递推就是为得到问题的解，将它推到比原问题简单的问题的求解。如f（n）=n!,为计算f（n），将它推到f（n-1），即f（n）=nf（n-1），这就是说，为计算f（n），将问题推到计算f（n–1），而计算f（n–1）比计算f（n）简单，因为f（n–1）比f（n）更接近于已知解0!=1.使用递推时应注意： （1）递推有终止的条件。所谓“终止条件”就是在此条件下问题的解是明确的，缺少终止条件便会使算法失效。例如n!,当n=0时，0!=1为递推的终止条件。 （2）“简单问题”表示离递推终止条件更为接近的问题。简单问题与原问题解的算法是一致的，其差别主要反映在参数上。例如，f（n–1）与f（n）其参数相差1.参数变化，使问题递推到有明确解的问题。 回归是指当“简单问题”得到解后，回归到原问题的解上来。例如，当计算完f（n–1）后，回归计算nf（n–1），即得n!的值。使用回归应注意： （1）递归到原问题的解时，算法中所涉及的处理对象应是关于当前问题的，即递归算法所涉及的参数与局部处理对象是有层次的。当解一问题时，有它的一套参数与局部处理对象。当递推进入一“简单问题”时，这套参数与局部对象便隐蔽起来，在解“简单问题”时，又有它自己的一套。但当回归时，原问题的一套参数与局部处理对象又活跃起来了。 （2）回归到原问题以得到问题的解，回归并不引起其他操作，如下例所示。 计算n!.其公式为： 程序员 http:// 程序片段如下： 【程序1-1】 int factorial（int n） { if（！n）return（1）； else return（n*factorial（n-1））； } 图的深度优先搜索、二叉树的前序、中序和后序遍历等可采用递归实现。 1.6.1 斐波纳契数列 问题描述：编写计算斐波纳契（Fibonacci）数列，数列大小为n。 无穷数列1,1,2,3,5,8,13,21,35,…称为斐波纳契数列，其递归定义如下： 由斐波纳契数列的递归定义可知，当n大于1时，这个数列第n项的数值是它前面两项之和。由于递归算法的执行过程分递推和回归两个阶段，在递推阶段，程序把较复杂的问题（规模为n）的求解推到比原问题简单一些的问题（规模小于n）的求解，在回归阶段，程序由在规模很小时求得的解得到较复杂问题的解。因此，对于斐波纳契数列的求解，要得到数列第n项的值，就必须求得数列第n–1项的值。同理，要求得数列第n–1项的值，就必须求得数列第n–2项的值，依次递推下去，最后需要求得数列第1项和第0项的值，递推部分结束。又当n等于0和1时，其数值为1,根据这些值可求出数列第2项的值，再根据数列第2项的值可得到第3项的值，依次回归，最后可依次得到数列第n– 2、n–1和n 程序员 http:// 项的值。由这个例子，我们可以很清楚地了解递归的形式和过程。该问题程序实现如下： 【程序1-2】 # include< stdio.h > int F（int n） {if（n==0）return 1; if（n==1）return 1; if（n>1）return F（n-1）+F（n-2）； /*递归*/ } main（）{ int i,n,m; printf（“please input n: n”）； scanf（“%d”,&n）； printf（“the Fibonacci is : ”）； for（i=0;i<=n;i++）{ m=F（i）； printf（“%d,”,m）； } } 1.6.2 斐波纳契数列 问题描述：编写计算斐波纳契（Fibonacci）数列，数列大小为n。 无穷数列1,1,2,3,5,8,13,21,35,…称为斐波纳契数列，其递归定义如下： 程序员 http:// 由斐波纳契数列的递归定义可知，当n大于1时，这个数列第n项的数值是它前面两项之和。由于递归算法的执行过程分递推和回归两个阶段，在递推阶段，程序把较复杂的问题（规模为n）的求解推到比原问题简单一些的问题（规模小于n）的求解，在回归阶段，程序由在规模很小时求得的解得到较复杂问题的解。因此，对于斐波纳契数列的求解，要得到数列第n项的值，就必须求得数列第n–1项的值。同理，要求得数列第n–1项的值，就必须求得数列第n–2项的值，依次递推下去，最后需要求得数列第1项和第0项的值，递推部分结束。又当n等于0和1时，其数值为1,根据这些值可求出数列第2项的值，再根据数列第2项的值可得到第3项的值，依次回归，最后可依次得到数列第n– 2、n–1和n项的值。由这个例子，我们可以很清楚地了解递归的形式和过程。该问题程序实现如下： 【程序1-2】 # include< stdio.h > int F（int n） {if（n==0）return 1; if（n==1）return 1; if（n>1）return F（n-1）+F（n-2）； /*递归*/ } main（）{ int i,n,m; printf（“please input n: n”）； 程序员 http:// scanf（“%d”,&n）； printf（“the Fibonacci is : ”）； for（i=0;i<=n;i++）{ m=F（i）； printf（“%d,”,m）； } } 1.7 本章例题分析 例题1（2011年5月试题36） 若二维数组arr[18,16]的首地址为base,数组元素按列存储，且每个元素占用4个存储单元，则元素arr[5,5]在该数组空间的地址为（36）。 （36）A.base+（4*8+4）*4 B.base+（5*8+5）*4 C.base+（4*6+4）*4 D.base+（5*6+5）*4 例题分析 在本题中，题目告诉我们二维数组arr是一个8行6列的数组，那么每一列有8个元素，而按列存储的意思就是先将第一列的元素全部存放完后，再开始存放第二列的元素，一次类推。 另外从题目给出的二维数组arr[18,16]我们可以看出，下标是从1开始的，因此元素arr[5,5]描述的是第5行第5列的元素，那么在存储该元素前，应该先存储完前4列的所有元素，并且第5列的前4个元素也都已经存放，所有元素arr[5,5]在该数组空间的地址为 程序员 http:// base+（4*8+4）*4.例题答案：（36）A 例题2（2011年5月试题37） 设线性表（59,53,46,48,37,31,25）采用散列（Hash）法进行存储和查找，散列函数为H（Key）=Key MOD 7（MOD表示整除取余运算）。若用链地址法解决冲突（即将相互冲突的元素存储在同一个单链表中）构造散列表，则散列表中与哈希地址 （37） 对应的单链表最长。 （37）A.2 B.3 C.4 D.6 例题分析 根据题目给出的散列函数我们可以分别计算出关键字（59,53,46,48,37,31,25）对应的散列地址分别为（3,4,4,6,2,3,4）。 在链地址方法中，散列表地址域的每个元素都是一个指针，指向一个单链表表，这个单链表存储所有该散列地址上的同义词，比如本题中的59和31就是同义词，因为他们的散列地址都是3.那么很显然，对应散列地址为4的元素有3个，而对应其它散列地址的元素个数都小于3,因此最长的单链表对应散列地址4.所以本题答案选C.例题答案：（37）C 例题3（2011年5月试题38） 设递增序列A为a1,a2,…，an,递增序列B为b1,b2,…，bm,且m>n,则将这两个序列合并为一个长度为m+n的递增序列时，当（38）时，归并过程中元素的比较次数最少。 （38）A.an >bm B.an C.a1>b1 D.a1 例题分析 程序员 http:// 题目告诉我们两个序列都是递增序列，那么如果一个序列的最小值大于另一个序列的最大值时，归并过程的比较次数最少，所以本题答案选B.例题答案：（38）B 例题4（2011年5月试题39） 已知某带权有向图G（顶点数为6,顶点编号为1至6）的邻接表如下所示，其中表结点的结构为： 则图G中含有的弧数为（36）。 （39）A.9 B.11 C.15 D.18 例题分析 根据题目给出的表结点的结构我们可以知道，其中各结点中最左边的是邻接顶点编号，而最中间是边上的权值，右边是指向下一个邻接顶点的指针。根据题目给出的邻接表，我们可以得到如图1-22所示的有向图，所以图G中含有9条弧。 程序员 http:// 图1-22 有向图 例题答案：（39）A 例题5（2011年5月试题40） 当二叉树的结构形如 （40） 时，其后序遍历序列和中序遍历序列相同。 （40） 例题分析 本题主要考查二叉树的遍历。 中序遍历的思想是：如果二叉树为空，则直接返回。否则，首先按中序遍历根结点的左子树，然后访问根结点，最后再按中序遍历根结点的右子树。 后序遍历的思想是：如果二叉树为空，则直接返回。否则，首先按后序遍历根结点的左子树，然后按后序遍历根结点的右子树，最后再访问根结点。 对于选项A的中序遍历，首先应该遍历根结点的左子树，因此其中序遍历序列为从下至上，而其后续遍历也同样先遍历根结点的左子树，因此其后序遍历序列也为从下至上。 例题答案：（40）A 例题6（2011年5月试题41） 对长度为n的有序表进行二分（折半）查找时，无论查找指定的一个元素是否成功，最多只与表中的（41） 个元素进行比较即可。 程序员 http:// （41） 例题分析 二分（折半）查找的基本思想为：在有序表中，先确定待查元素所在的区域，再逐步缩小这个区域，直到在区域中找到该元素（查找成功）或者区域缩小为0也没有找到该元素（查找失败）为止。通常采用如下递归步骤： （1）将区域分为左、中、右三个部分，其中区域中间的元素单独处于中间区域，该元素左、右两边的元素分别属于左、右区域，则左、右区域所包含的元素相等（或相差1个），数量为原区域元素的一半； （2）比较给定关键字与中央区域元素的关键字，如果相等则查找成功，该元素即为所求； （3）如果给定关键字较大，那么待查元素只可能出现在中间元素右边，则继续对右区域执行步骤1~4; （4）否则给定关键字较小，则待查元素只可能出现在中间元素左边，继续查找左区域即可。 在二分（折半）查找时，无论查找成功与否，最多只与表中的个元素进行比较，例如对含有12个元素的有序表{1,4,10,16,17,18,23,29,33,40,50,51}进行折半查找，如果要查找17,那么首先应该与第6个元素比较，由于17小于18,那么应该在前半部分查找，那么接着应该与第3个元素比较，由于大于10,那么应该接着与16比较，最后与17比较，然后查找成功，一共比较了4次。如果要查找19,那么首先应该与第6个元素比较，由于19大于18,那么应该在后半部分查找，那么接着应该与第9个元素比较，由于大于33,那么应该接着与29比较，最后与23比较，然后查找失败，一共也比较了4次，即 2010下半年软考网络工程师考试试题参考答案(上午)一 1-10 CDAAD ADCAC 11-20 DBADB BBACC 21-30 ADBAC BDCCB 31-40 CBADD ABCDD 41-50 BABAB CCDBC 51-60 ACDBC BDDAB 61-70 BBDCD AAADB 71-75 DBCBA第二篇：2012软考网工上午题和参考答案下午答案完整版范文
第三篇：2016年软考程序员试题及答案解析
第四篇：软考教材分享：程序员考试考点分析与真题详解(第4版 )
第五篇：2010下半年软考试题上午题和答案
点击咨询 