程序员笔记
本文由yanjiajin贡献
doc文档可能在WAP端浏览体验不佳。建议您优先选择TXT，或下载源文件到本机查看。
路由选择原理 路由选择基础知识 路由是将对象从一个地方转达发到另一个地方的一个中继过程 学习和维持网络拓朴结构知识的机制被认为是路由功能。 渡越数 据流经路由器进入接口 穿过路由器被移送到外出接口的过程，是另一项单独的功能，被 认为是交换/转发功能。路由设备必须同时具有路由和交换的功能才 可以作为一台有效的中继设备。 为了进行路由，路由器必须知道下面三项内容： 路由器必须确定它是否激活了对该协议组的支持； 路由器必须知道目的地网络； 路由器必须知道哪个外出接口是到达目的地的最佳路。 路由选择协议通过度量值来决定到达目的地的最佳路径。 小度量 值代表优选的路径；如果两条或更多路径都有一个相同的小度量值， 那么所有这些路径将被平等地分享。 通过多条路径分流数据流量被称 为到目的地的负载均衡。 执行路由操作所需要的被包含在路由器的路由表中， 它们由一个 或多个路由选择协议进程生成。路由表由多个路由条目组成，每个条 目指明了以下内容： 学习该路由所用的机制（动态或手动） 逻辑目的地 管理距离 度量值（它是度量一条路径的总"总开销"的一个尺度） 去往目的地下一 HOP 的中继设备（路由器）的地址； 路由的新旧程度 与要去往目的地网络相关联的接口 使用命令 SHOWIPROUTE 可看到以上内容 缺省管理距离的预先分配原则是： 人工设置的路由条目优先级高 于动态学到路由条目， 度量值算法复杂的路由选择协议优先级高于度 量值算法简单的路由选择协议。 路由器一般选择具有最小度量值的路径；CISCO 路由器的 IP 环 境中如果同时出现了多条度量值最低且相同的路径， 那么在这多条路 径上将启用负载均衡，CISCO 默认支持 4 条相同度量值的路径，通过 使用"maximum-paths"命令可以认 CISCO 路由器支持最多达 6 条相同 度量值路径。 RIP 是一种用在小到中型 TCP/IP 网络中采用的路由选择协议， 它采用跳数作为度量值，它的负载均衡功能是缺省启用的，RIP 决定 最佳路径时是不考虑带宽的！！ ！
IGRP 是一种用在中到大型 TCP/IP 网络中采用的路由选择协议， 它采用复合的度量值，它考虑了带宽、延迟、可靠性、负载和最大传 输单元（MTU） ，但缺省地使用了带宽和延时值。IGRP 也能进行负载 均衡 在路由器启动之后，它立刻试图与其相邻路由设备建立路由关 系。该初始通信的目的是为了识别相邻设备，并且开始进行通信并学 习网络相结构。 建立相邻关系的方法和对拓朴结
构的初始学习随路由 选择协议的不同而不同。 路由选择协议会交换定期的 HELLO 消息或定期的路由更新数据 包，以维持相邻设备间进行着通信。 在了解了网络拓朴结构， 且路由表中已包含了到已知地网络的最 佳路径后，向这些目的地的数据转发就可以开始了； ） 路由选择协议 有类别路由选取择（classfulrouting）概述 不随各网络地址发送子网掩码的路由选择协议被称为有类别的 选择协议（RIPv1、IGRP） 当采用有类别路由选择协议时，属于同一主类网络（A 类、B 类 和 C 类）有所有子网络都必须使用同一子网掩码。运行有类别路由选 择协议的路由选择协议的路由器将执行下面工作的一项以确定该路 由型网络部分： 如果路由更新是关于在接收接口上所配的同一主类网络的， 路由 器将采用配置在接口上的子网掩码； 如果路由更新是关于在接收接口上所配的不同主类的网络的， 路 由器将根据其所属地址类别采用缺省的子网掩码。 有类别归纳路由的生成是由有类别路由选择协议自动处理的 无类别路由选择概述 无类别路由选择协议包括开放最短路径优先（OSPF） 、EIGRP、 RIPV2、 中间系统到中间系统 （IS-IS） 和边界网关协议版本 4 （BGP4） 。 在同一主类网络中使用不同的掩码长度被称为可变长度的子网 掩码（VLSM） 。无类别路由选择路由选择协议支持 VLSM，因此可以更 为有效的设置子网掩码，以满足不同子网对不同主机数目的需求，可 以更充分的利用主机地址。 多数距离矢量型路由选择协议产生的定期的、 例行的路由更新只 传输到直接相连的路由设备。 在纯距离矢量型路由环境中，路由更新包括一个完整的路由表， 通过接收相邻设备的全路由表，路由能够核查所有已知路由，然后根 据所接收到的更新修改本地路由表。 解决路由问题的距离矢量法有时 被称为"传闻路由（routingbyrumor）"
CISCOIOS 支持几种距离矢量型路由选择协议， 凶手 RIPv1、 RIPv2 和 IGRP。CISCO 也直持 EIGRP，它是一种高级的距离矢量型路由选择 协议。 路由选择协议通常与协议组的网络层关联 大多数距离矢量型路由选择协议采用贝乐曼-福特算法来计算路 由。EIGRP 是一种高级的距离矢量路由协议，它采用弥散修正算法 （DUAL） Cisco 的 IP 距离矢量型路由选择协议的比较 特征 RIPv1RIPv2IGRPEIGRP 计数到无限ＸＸＸ 横向距离ＸＸＸＸ 抑制计时器ＸＸＸ 触发式更新，路由反向ＸＸＸＸ 负载均衡-等成本路径ＸＸＸＸ 负载均衡-非等成本路径ＸＸ VLSM 支持ＸＸ 路由算法贝尔曼-福特贝尔曼-福特贝尔曼-福特 DUAL 度量值跳数跳数复合复合 跳数限制 1515100100 易扩展性小小中大 注：IGRP 和
EIGRP 的跳数限制缺省为 100，但是可以配置到最大 为 255。 算法分析基础学习 在计算机解决问题的过程中，数据结构和算法是程序的两大要 素，二者相辅相成，缺一不可。算法与数据结构的好坏直接相关，一 种数据结构的优劣是由实现其各种运算的算法体现的。 对数据结构的 分析实质上也表现为对实现其多种运算的算法分析。 算法分析是一个 复杂的问题，它首先涉及到优劣准则的确定。判断一个算法的优劣主 要有以下几个标准： (1)正确性。要求算法能够正确地执行规定的功能。这是最重要 也是最基本的准则; (2)可使用性。算法应当是可读的，即可读性好。为了达到这个 要求，算法的逻辑必须是清晰的、简单的和结构化的; (3)健壮性。要求算法具有很好的容错性，即提供例外处理，能 够对不合理的数据进行检查，不会经常出现异常中断或死机现象; (4)效率。算法的效率主要指算法执行时计算机资源的消耗，包
括存储和运行时问的开销，前者叫做算法的空间代价，后者叫做算法 的时间代价。 时间代价是常用的评价指标，往往用时间复杂度来衡量。当一个 算法转换成程序并在计算机上执行时， 其运行所需要的时间总是取决 于下列因素： 硬件的速度。CPu 速度和存取数据的速度越快，则程序的执行时 间越短; 所选用的程序设计语言。程序设计语言的级别越高，其执行效率 就越低。比如汇编语言程序的执行效率往往要高于高级算法语言; 编译程序所生成目标代码的质量。对于代码优化较好的编译程 序，其所生成的程序质量较高。比如，代码效率优化过的 c++语言程 序比未经过优化的代码效率要高; 问题的规模。很显然，大规模的问题求解过程比小规模的问题更 耗费时间。 显然，在各种因素都不能确定的情况下，很难比较算法的执行时 间。也就是说，使用执行算法的绝对时间来衡量算法的效率是不合适 的。 为此， 可以将上述各种与计算机相关的软、 硬件因素都确定下来， 这样一个特定算法的运行工作量的大小就只依赖于问题的规模， 或者 说它是问题规模的函数。另一方面，要全面地评价一个算法的优劣， 不仅要考虑时间的耗费，还要考虑算法对存储器的耗费。特别是对于 大规模问题，对空间耗费的分析是必不可少的。因此，分别有基于时 间和空间的算法分析，即算法的时间复杂度分析和空间复杂度分析。 数据结构 1.数据结构中对象的定义，存储的表示及操作的实现. 2.线性:线性表、栈、队列、数组、字符串（广义表不考） 树：二叉树 集合：查找，排序 图 能力： 分析，解决问题的能力 过程： 确定问题的数据。 确定数
据间的关系。 确定存储结构（顺序－数组、链表－指针） 确定算法 编程 算法评价（时间和空间复杂度，主要考时间复杂度）
一、数组 1、存放于一个连续的空间 2、一维～多维数组的地址计算方式 已知 data[0][0]的内存地址，且已知一个元素所占内存空间Ｓ求 data[i][j]在内存中的地址。 公式： （add+S) 注意：起始地址不是 data[0][0]时候的情况。起始地址为 data[-3] 和情况； 3、顺序表的定义 存储表示及相关操作 4、顺序表操作中时间复杂度估计 5、字符串的定义（字符串就是线性表） ，存储表示 模式匹配算法（简单和 KMP（不考） ） 6、特殊矩阵：存储方法（压缩存储（按行，按列） ） 三对角：存储于一维数组 三对角问题：已知 Aij 能求出在一维数组中的下标 k;已知下标 k 求 Aij。 7、稀疏矩阵：定义，存储方式：三元组表、十字链表（属于图部分， 不考） 算法 数组中元素的原地逆置；对换 在顺序表中搜索值为 X 的元素； 在有序表中搜索值为 X 的元素； （折半查找） 在顺序表中的第 i 个位置插入元素 X； 在顺序表中的第 i 个位置删除元素 X； 两个有序表的合并；算法？ 线性表数据结构定义： Typedefstructlinear_list; 模式匹配 字符串相加 求子串 （i，j）<=>K 注意：不同矩阵所用的公式不同； 稀疏矩阵的转置（两种方式，后种为妙） 和数组有关的算法 例程：求两个长整数之和。 a=130******** b=87081299
数组: a:130******** b:87081299 由于以上的结构不够直观将其改为: a:1186125965031a[0]=11 b:899218078000b[0]=8
c 进位 01100111100
c:1176433044231c[0]的值由 c[max_s+1]决定! 注意:在求 C 前应该将 C 位赋 0.否则为随机数;较小的整数高位赋 0. 算法:已知 a，b 两个长整数，结果:c=a+b; 总共相加次数:max_s=max 程序: for 求 c 位数: if c[0]=max_s; else c[0]=max_s+1; 以下代码是我编的: /两长整数相加/ #include #include #definePRINprintf; intflag=0;/a[0]>b[0]?1:0/ /max/ change else }
add if c[0]=a[0]; else c[0]=a[0]+1;
} else if c[0]=b[0]; else c[0]=b[0]+1; } } voidprint main; chardb=; a[0]=strlen; b[0]=strlen; printf; printf;PRIN change; printf;PRIN printf; if else add; printf; print; } 时间复杂度计算: 确定基本操作 计算基本操作次数 选择 T lim/T)=c 0)为时间复杂度 上例子的时间复杂度为 O; 二:链表 1、知识点 逻辑次序与物理次序不一致存储方法； 单链表的定义：术语（头结点、头指针等）
注意带头结点的单链表与不带头结点的单链表区别。 （程序员考试一 般不考带头结点，因为稍难理解） 插入、删除、遍历（p==NULL 表明操作完成）等操作 循环链表：定义，存储表示，操作； 双向链表：定义，存储方法，操作； 单链表和循环链表区别
在最后一个指针域值不同。 2、操作 单链表：插入 X，删除 X，查找 X，计算结点个数 单链表的逆置（中程曾考） head->NULL/p->a1/p->a2/p->a3/p……an/NULL 注：p 代表指 针;NULL/p 代表头结点 ＝》head->NULL/p->an/p->an-1/p->an-2/p……a1/NULL 循环链表的操作：插入 X，删除 X，查找 X，计算结点个数； 用 p=head->next 来判断一次计算结点个数完成； 程序段如下： k=0; dowhile; 双向链表 多项式相加 有序链表合并 例程：已知两个字符串 S，T，求 S 和 T 的最长公子串； 1、逻辑结构：字符串 2、存储结构：数组 3、算法：精化（精细化工）老顽童注：此处“精细化工”说明好像不 对！ s="abaabcacb" t="abdcabcaabcda" 当循环到 s.len-1 时，有两种情况：s="abaabcacb"、s="abaabcacb" s.len-2 时，有三种情况：s="abaabcacb"、s="abaabcacb"、 s="abaabcacb" . . . 1s.len 种情况 程序思路： tag=0//没有找到 for
长度为 l 的 s 的子串在 s 中有（s.len-l+1）个。 子串 0:0～l-1 1:1～l 2:2～l+1 3:3～l+2 …… …… s.len-l:s.len-l～s.len-1 由上面可得：第 j 个子串为 j～l+j-1。 判断长度为 l 的 s 中的子串是否为 t 的子串: for 模式结构： tag=0; for }
栈和队列 1、知识点: 栈的定义:操作受限的线性表 特点:后进先出 栈的存储结构:顺序，链接 /push 栈的基本操作: “pop 栈定义： struct; 队列定义 特点:先进先出 /入队列 in_queue 队列的操作: “出队列 del_queue 队列存储结构: 链队列:
TypedefstructnodeNODE; TypedefstructQueue; 顺序队列: struct; 问题: 队列 ó线性表 假溢出<=循环队列 队列满，队列空条件一样<=浪费一个存储空间 递归 定义：问题规模为 N 的解依赖于小规模问题的解。问题的求解通过小 规模问题的解得到。 包括二个步骤： 1）递推 6!=>5!=>4!=>3!=>2!=>1!=>0! 2）回归 720<=120<=24<=6<=2<=1<=0 递归工作栈实现递归的机制。
2、有关算法： 1）顺序，链表结构下的出栈，入栈 2）循环，队列的入队列，出队列。 3）链队列的入队列，出队列。 4）表达式计算：后缀表达式 35+6/4368/+中缀表达式（3+5）/6-4（3+6/8） 由于中缀比较难处理，计算机内一般先将中缀转换为后缀。 运算：碰到操作数，不运算，碰到操符，运算其前两个操作数。 中缀=>后缀 5)迷宫问题 6)线性链表的递归算法一个链表=一个结点+一个链表 intfuction 树与二叉树 一、知识点: 1.树的定义:data_struct; 其中:D 中有一个根，把 D 和出度去掉，可以分成 M 个部分. D1，D2，D3，D4，D5…DM R1，R2，R3，R4，R5…RM 而子树 Ri 形成树.
1)递归定义高度 2)结点个数=1
O --0 OO --1 OOOO --2 此树的高度为 2 2.二叉树定义: 结点个数>=0. 3.术语:左右孩子，双亲，子树，度，高度等概念. 4.二叉树的性质 层次为 I 的二叉
树 I 层结点 2I 个 高度为 H 的二叉树结点 2H+1-1 个 H=E+1 个数为 N 的完全二叉树高度为_LOG2n_ 完全二叉树结点编号:从上到下，从左到右. i 结点的双亲:_i/2__i-1/2_1i 结点的左孩子:2i2i+123i 结点的 右孩子:2i+12i+245671 为起点 0 为起点 二叉树的存储结构: 1)扩展成为完全二叉树，以一维数组存储。 ABCDEFGHI 数组下标 0123456789101112 元素 ABCDEFGHI 2)双亲表示法 数组下标 012345678 元素 ABCDEFGHI 双亲-100122334 3)双亲孩子表示法 数组下标 012345…元素 ABCDEF…双亲-100122…左子 134…右子 2-15… 结构: typedefstructNODE; NODEtree[N];//生成 N 个结点的树 4)二叉链表 5)三叉链表 6)哈夫曼树
5.二叉树的遍历 先根“ 中根栈中根遍历根，再用相同的方法处理左子树，右子树. 后根/ 先，中序已知求树:先序找根，中序找确定左右子树. 层次遍历 6.线索二叉树 中序线索二树树目的:利用空指针直接得到中序遍历的结果. 手段:左指针为空，指向前趋，右指针为空，指向后继. 结点结构: ltagLchDatarchrtag Ltag=0，lch 指向左孩子，ltag=1，指向前趋结点 Rtag=0，rch 指向右孩子;rtag=1，指向后继结点 中序遍历:1)找最左结点 2)当该结点的 rtag=1，该结点的 rch 指向的就为后继 3)当 rtag=0，后继元素为右子树中最左边那个 N 个结点的二树有空指针 N+1 个 周六我去了周 SIR 的办公室，他很热情，我问的是中序线索化二叉树 的问题，关于这个问题我会在以后的笔记中作重点补充。我在这学校 从来没有碰到过像他这样热情的老师，真的，大一的时候我们学校就 开了 C，当时我就连#include这句话的意思都不晓得，别 说是让我写程序了（到这份上也不怕把丑事都抖出来了:《数据结构》 的课程设计也是哈科大的 littlebob 兄帮我做的，很遗憾，他高程就 差几分，希望他早日成功，我们都要向他学习）等于说我的 C 知识九 成都是在大二下学期的时候学的。而且全是自学的。拿这个周末来说 吧。我三天时间就看完了一本 C 语言大全。当然，并不是从头到尾， 只是根据自己的实际情况，重点是指针和数据结构那块。C 最要的便 是指针。程序员考试下午试题最重要的便是递归问题（1～2 道，没 有掌握就没希望了哦） 。我说这些并不是为了表明自己多么用功，只 是希望每位"学者"都有所侧重。
查找 一、知识点/静态查找->数组 1、什么是查找 “动态查找->链树
顺序查找，时间复杂度 O 折半查找：条件：有序；时间复杂度 O 索引查找：条件：第 I+1 块的所有元素都大于第Ｉ块的所有元素。 算法：根据 index 来确定 X 所在的块（i）时间复杂度：m/2 在第Ｉ块里顺序查找 X 时间复杂度：n/2 总的时间复杂度：/2 二叉排序树 1）定义：
左子树键值大于根节点键值；右子树键值小于 根的键值，其左右子树均为二叉排序树。 2）特点：中序遍历有序->（删除节点用到此性质） 3）二叉排序树的查找：如果根大于要查找的树，则前左子树前进， 如果根小于要查找的树，则向右子树前进。 4）结点的插入->二叉排序树的构造方法 5）结点删除（难点）1、右子树放在左子树的最右边 2、左子树放在右子树的最左边 avl 树（二叉平衡树） ：左右子树高度只能差１层，即｜h｜<=1 其子 树也一样。 B 树：n 阶 B 树满足以下条件 1）每个结点（除根外）包含有 N～2N 个关链字。2）所有叶子节点都在同一层。 3）B 树的所有子树也是一棵 B 树。 特点：降低层次数，减少比较次数。
排序 一、知识点 1、排序的定义 /内排序：只在内存中进行 2、排序的分类 “外排序：与内外存进行排序 内排序：/直接插入排序 1）插入排序 “shell 排序 /冒泡排序 2）交换排序 “快速排序 /简单选择排序 3）选择排序堆 “锦标赛排序 4）归并排序（二路）
5）基数排序（多关链字排序） 3、时间复杂度（上午题目常考，不会求也得记住啊兄弟姐妹们！ ） 1515 /稳定 1515 排序 “不稳定 1515 经整理得:选择、希尔、堆、快速排序是不稳定的；直接插入、冒泡、 合并排序是稳定的。 锦标赛排序方法：13161118213176 “/“/“/“/ 131136 “/“/ 113 “/ 3（胜出，将其拿出，并令其为正无穷&GoOn） 归并排序方法：13161118213176 “/“/“/“/ 13，1611，183，216，17 “/“/ 11，13，16，183，6，17，21 “/ 3，6，11，13，16，17，18，21 shell 排序算法：1）定义一个步长（或者说增量）数组 D[m]；其中： D[m-1]=1 2）共排 m 趟，其中第 i 趟增量为 D[i]，把整个序列分成 D[i]个子序 列，分别对这 D[i]个子序列进行直接插入排序。 程序如下：for } 快速排序 data di->13161118213176248<-j 先从后往前找，再从前往后找。 思想：空一个插入一个，i 空 j 挪，j 空 i 挪（这里的 i，j 是指 i，
j 两指针所指的下标） 。 一次执行算法：1）令 temp=d[0]，i=0，j=n-1; 2）奇数次时从 j 位置出发向前找第一个比 temp 小的元素，找到后放 到 i 的位置 i 往后挪。 3） 偶数次时从 i 开始往后找第一个比 temp 大的数，d[j]=d[i];j--;) （ 4）当 i=j 时，结束循环。d[i]=temp； 再用递归对左右进行快速排序，因为快速排序是一个典型的递归算 法。 堆排序 定义： d[n]满足条件： d[i]
调整 程序:flag=0; while } else flag=1;//是堆 } 堆排序过程： 基数排序 扑克:1)大小->分配 2)花
色->分配，收集 思想:分配再收集. 构建链表:链表个数根据关键字取值个数有关. 例:将下面九个三位数排序: 321214665102874699210333600 定义一个有十个元素的数组: a[0]aaaaaaaaa 第一趟:210321102333214665699 600874 结果:210600321102333214874665699
第二趟:600210321333665874699 102214 结果:600102210214321333665874699 第三趟:102210321600874 214333665 699 结果:102210214321333600665699874
枚举: 背包问题: 枚举策略：1)可能的方案：2N 2)对每一方案进行判断. 枚举法一般流程： while } 枚举策略: 例：把所有排列枚举出来 P6=6!. Min:123456 Max:654321 a1a2a3a4a5a6=>?=>? 比如:312654 的下和种情况=>314256 递归 递归算法通常具有这样的特征：为求解规模为 N 的问题，设法将它分 解成一些规模较小的问题， 然后从这些较小问题的解能方便地构造出 题目所需的解。 而这些规模较小的问题也采用同样的方法分解成规模 更小的问题，通过规模更小的问题构造出规模校小的问题的解，如此 不断的反复分解和综合，总能分解到最简单的能直接得到解的情况。 因此，在解递归算法的题目时，要注意以下几点: 1)找到递归调用的结束条件或继续递归调用条件. 2)想方设法将处理对象的规模缩小或元素减少. 3)由于递归调用可理解为并列同名函数的多次调用， 而函数调用的原 则是一层一层调用，一层一层返回.因此，还要注意理解调用返回后 的下一个语句的作用.在一些简单的递归算法中，往往不需要考虑递
调用返回后的语句处理.而在一些复杂的递归算法中，则需要考虑递 归调用返回后的语句处理和进一步的递归调用. 4)在读递归程序或编写递归程序时，必须要牢记递归函数的作用，这 样便于理解整个函数的功能和知道哪儿需要写上递归调用语句.当 然，在解递归算法的题目时，也需要分清递归函数中的内部变量和外 部变量. 表现形式: 定义是递归的 存储结构是递归的 由前两种形式得出的算法是递归的 一般流程:function) } 例 1：求一个链表里的最大元素. 大家有没想过这个问题用递归来做呢? 非递归方法大家应该都会哦? Max p=p->next; } returnq; } 下面真经来了，嘻嘻嘻~~~ max 大家有空想想下面这个算法：求链表所有数据的平均值，不许偷懒， 用递归试试哦! 递归程序员考试题目类型：1)就是链表的某些操作 2)二叉树
例 2.判断数组元素是否递增 intjidge 例 3.求二叉树的高度根) intdepth } 自己想想求二叉树结点个数 例 4.已知中序遍历和后序遍历，求二叉树.
设一二叉树的: 中序 S:EDFBAGJHCI ^start1^j^end1 后序 T:EFDBJHGICA ^start2^end2 nodecreate
例 5.组合问题 n 个数:求从中取 r 个数的所有组合. 设 n=5，r=3; 递归思想：先固定一位 5 5
，4 5，4，3 即：n-2 个数中取 r-2 个数的所有组合 … 程序: voidcombire}
回溯法: 回溯跟递归都是程序员考试里常出现的问题，大家必须掌握! 回溯法的有关概念: 1)解答树:叶子结点可能是解，对结点进行后序遍历. 2)搜索与回溯 五个数中任选三个的解答树: ROOT 虚根 //““ 12345 /“/“/“ 2345345455 /“/“/“ 3454554555 回溯算法实现中的技巧:栈 要搞清回溯算法，先举一个来说明栈在非递归中所起的作用。 A 过程：push->push->push->push 栈内结果:ABDE
/“popABD BCpopAB /“popA DF.. //“.. EGH.. /.. I 最后结果：EDBGFIHAC 简单算法: … if//树不空 while)//栈非空，出栈 } }//这就是传说中的回溯，嘻嘻……没吓着你吧 5 选 3 问题算法: 思想:进栈:搜索 出栈:回溯 边建树边遍历 基本流程: 太复杂了，再说我不太喜欢用 WORD 画图（有损形象） ，以后再整理! 程序:n=5;r=3 …… init//初始化栈 push//根进栈 while&&//有孩子 push;//孩子入栈 while)
背包问题:TW=20，w= 解的条件:1)该解答树的叶子结点 2)重量最大 解答树如下：ROOT
/“ 610758 /“/“/“ 10758758588 588 程序: temp_w 表示栈中重量和 … init;//初始化栈 i=0; While i++; IfReturn-1;//无解 Else max_w=0; while) } 请大家思考:四色地图问题，比如给中国地图涂色，有四种颜色，每 个省选一种颜色，相邻的省不能取同样的颜色.不许偷懒，不能选人 口不多于 xxxxＷ的"大国"哦!如果真的有一天台湾独立了，下场就是 这样了，一种颜色就打发了，不过台湾的程序员们赚到了，省事！呵 呵。 贪婪法: 不求最优解，速度快 例:哈夫曼树，最小生成树 装箱问题: 有 n 个物品，重量分别为 w[n]，要把这 n 个物品装入载重为 TW 的集 装箱内，需要几个集装箱? 思想 1:对 n 个物品排序 拿出第 1 个集装箱，从大到小判断能不能放。 2… 3… .…
.… 思想 2:对 n 个物品排序 用物品的重量去判断是否需要一只新箱子， 如果物品重量小于本箱子 所剩的载重量，则装进去，反之则取一只新箱子。 程序: count=1;qw[0]=TW; for } 用贪婪法解背包问题: n 个物品，重量:w[n]价值 v[i] 背包限重 TW，设计一个取法使得总价值最大. 方法: 0123…n-1 w0w1w2w3…wn-1 v0v1v2v3…vn-1 v0/w0…v/w 求出各个物品的"性价比" 先按性价比从高到低进行排序 已知:w[n]，v[n]，TW 程序: … for d[i]=v[i]/w[i];//求性价比 for } e[i]=x; d[x]=0; } temp_w=0;temp_v=0; for 分治法: 思想:把规模为 n 的问题进行分解， 分解成几个小规模的问题.然后在 得到小规模问题的解的基础上，通过某种方法组合成该问题的解.
例:数轴上有 n 个点 x[n]，求距离最小的两个点. 分:任取一点，可以把 x[i]这 n 个点分成两个部分 小的部分分点大的部分 _._.__.__……_._
.__._.__.._.__._._.__.. _._ 治:解=min
程序员考试下午试题（模拟） 一、 把一个字符串插入到另一个字符串的某个位置 （指元素个数） 之后 charinsert } } returngarget; } 二、辗转相除法求两个正整数的最大公约数 intf } 三、求一个链表的所有元素的平均值 typedefstructBack; typedefstructnodeNode; Backaveage（Nodehead） else retuenp; } main }
四、希尔排序 已知待排序序列 data[n]；希尔排序的增量序列为 d[m]，其中 d 序列 降序排列，且 d[m-1]=1。其方法是对序列进行 m 趟排序，在第 i 趟 排序中，按增量 d[i]把整个序列分成 d[i]个子序列，并按直接插入 排序的方法对每个子序列进行排序。 希尔排序的程序为： voidshellsort
voidshell } 五、求树的宽度 所谓宽度是指在二叉树的各层上， 具有结点数最多的那一层上的结点 总数。本算法是按层次遍历二叉树，采用一个队列 q，让根结点入队 列，最后出队列，若有左右子树，则左右子树根结点入队列，如此反 复，直到队列为空。 intWidth while // if if/当前层已遍历完毕/ } return; } 六、区间覆盖 设在实数轴上有 n 个点（x0，x1，……，xn-2，xn-1） ，现在要求用 长度为 1 的单位闭区间去覆盖这 n 个点，则需要多少个单位闭区间。 intcover if } returncount-1; }
start[count]=x[i] 七、围棋中的提子 在围棋比赛中，某一方（假设为黑方）在棋盘的某个位置（i，j）下 子后，有可能提取对方（白方的一串子） 。以 W[19][19]表示一个棋 盘，若 W[i][j]=0 表示在位置（i，j）上没有子，W[i][j]=1 表示该 位置上的是黑子，W[i][j]=-1 表示该位置上是白子。可以用回溯法 实现提子算法。 下列程序是黑棋（tag=1）下在（i，j）位置后判断是否可以吃掉某 些白子，这些确定可以提掉的白子以一个线性表表示。 问题相应的数据结构有： #definelength19/棋盘大小/ #definemax_num361/棋盘中点的数量/ structposition;/棋子位置/ structkilledp;/存储可以吃掉的棋子位置/ structstack;/栈/ intw[length][length];/棋盘中双方的棋子分布/ intvisited[length][length];/给已搜索到的棋子位置作标记， 初值 为 0，搜索到后为 1/ structkilledkill while } } voidpush
voidpop
structpositiongettop
intsearch
iftag)&& iftag)&& iftag)&& （5）; } 答案： （1） strlen+strlen 2） （ position+strlen 3） （ target[i]=s[i-strlen] （4）returna（5）returnf （6）q=aveage（7）p->ave=/p->num （1） j
多人都看过设计模式方面的书，大家有什么体会呢？ Bridge，Proxy，Factory 这些设计模式都是基于抽象类的。使用抽 象对象是这里的一个核心。 其实我觉得框架化编程的一个核心问题是抽象， 用抽象的对象构建程 序的主体框架，这是面向对象编程的普遍思想。用抽象构建骨架，再 加上多态就形成了一个完整的程序。由于 C＋＋语言本身实现了继承 和多态，使用这样的编程理念（理念啥意思？跟个风，嘿嘿）在 C＋ ＋中是十分普遍的现象，可以说 Virtual（多态）是 VC 的灵魂。 但是， 使用 C 语言的我们都快把这个多态忘光光了。 我常听见前辈说， 类？多态？我们用的是 C，把这些忘了吧。很不幸的是，我是一个固 执的人。这么好的东西，为啥不用呢。很高兴的，在最近的一些纯 C 代码中，我看见了 C 中的多态！下面且听我慢慢道来。
1.VC 中的 Interface 是什么 Interface：中文解释是接口，其实它表示的是一个纯虚类。不过我 所要说的是， VC 中的 Interface 其实就是 struct， 在 查找 Interface 的定义，你可以发现有这样的宏定义： #IfndefInterface #defineInterfacestruct #endif 而且，实际上在 VC 中，如果一个类有 Virtual 的函数，则类里面会 有 vtable，它实际上是一个虚函数列表。实际上 C＋＋是从 C 发展而 来的，它不过是在语言级别上支持了很多新功能，在 C 语言中，我们 也可以使用这样的功能，前提是我们不得不自己实现。 2．C 中如何实现纯虚类（我称它为纯虚结构） 比较前面，相信大家已经豁然开朗了。使用 struct 组合函数指针就 可以实现纯虚类。 例子：typedefstructMyVirtualInterface; 这样假设我们在主体框架中要使用桥模式。 （我们的主类是 DoMyAct， 接口具体实现类是 Act1，Act2）下面我将依次介绍这些“类”。 中 （C 的“类”在前面有说明，这里换了一个，是使用早期的数组的办法） 主类 DoMyAct：主类中含有 MyVirtualInterfacem_pInterface;主类 有下函数： DoMyAct_SetInterface DoMyAct_Do 子类 Act1：实现虚结构，含有 MyVirtualInterfacest[MAX];有以下 函数： MyVirtualInterfaceAct1_CreatInterface 子类 Act2 同上。 在 main 中，假设有一个对象 List。List 中存贮的是 MyVirtualInterface 指针，则有： if)!=NULL) List_AddObject;//AddAll
While) FREEALL。 在微系统里面，比如嵌入式，通常使用对象池的技术，这个时候可以 不用考虑释放的问题（对象池预先没有空间，使用 Attach，在某个 函数中申请一个数组并临时为对象池分配空间，这样函数结束，对象 池就释放了） 但是在 Pc 环境下，由于程序规模比较大，更重要的是一些特殊的要 求，使得对象的生命周期必须延续到申请的那个函数体以外，就不得
不使用 malloc，实际上即使在 C＋＋中，new 对象的自动释放始终是 一个令人头疼的问题， 新的标准引入了智能指针。 但是就我个人而言， 我觉得将内存释放的问题完全的交给机器是不可信任的， 它只能达到 准最佳。 你知道设计 Java 的垃圾回收算法有多困难吗？现实世界是错综复杂 的，在没有先验条件下，要想得到精确的结果及其困难。所以我说程 序员要时刻将 free 记在心上，有关程序的健壮性和自我防御将在另 外一篇文章中讲述。
3．纯虚结构的退化 下面我们来看看如果 struct 里面仅仅有一个函数是什么？这个时候 如果我们不使用 struct，仅仅使用函数指针又是什么？我们发现， 这样就退化为普通的函数指针的使用了。 所以说， 有的时候我觉得面向对象仅仅是一种形式， 而不是一种技术。 是一种观点，而不是一种算法。但是，正如炭，石墨和钻石的关系一 样，虽然分子式都是 C，但是组成方法不一样，表现就完全不一样了！ 有的时候，我们经常被编程中琐碎的事情所烦恼，而偏离了重心，其 实程序可进化的特性是很重要的。有可能，第一次是不成功的，但是 只要可进化，就可以发展。 4．进阶――类结构树，父类不是纯虚类的类 前面仅仅讲的是父类是纯虚结构的情况， 那么当类层次比较多的情况 下，出现父类不是纯虚结构怎么办呢。嘿嘿，其实在 C 中的实现比 C ＋＋要简单多了。因为 C 中各个函数是分散的。
在这里使用宏定义是一个很好的办法：比如两个类 Act1， ActByOther1“继承”Act1： MyVirtualInterfaceActByOther1_CreatInterface
defineActByOther1_Foo1Act1_Foo1//这就是继承 ActByOther1_Foo2（）//可以修改其实现 ActByOther1_DoByOther//当然就可以添加新的实现
计算机系统知识 内容简介： 1、问：T 循环冗余取决于 K 和 R 值，请问 R 值是怎么选择的? T 答：R 值就是生成多项式的阶数，也就是生成多项式的最高次， 比如生成多项式为：G（X）=TXP4P+XP3P+X+1，则 R=4。 2、 CRC 求余方法和数学除法相同？x4问： （X4+X3+X+1） =X3+X+1? 有没有负数？ T 答：TCRC 求余方法和通常的数学除法不同，这里采用是的模 2 除法， 即即以 2 为模， 加减时不进位， 不借位， 和逻辑异或运算一致。 那么 x4-（X4+X3+X+1）=X3+X+1，照此规则就不会产生负数。 （注意： 前面表示的 x4 其实应是 x 的 4 次方，其它同理） 3、问：讲一讲海明码的奇校验和偶校验。 T 答：对于海明码，我们了解下面这些就足够了 TT。T 要能纠正 字中的单个错误，所需的最小距离为 3。实现这种纠正的方法之一是 海明码。海明码是一种多重奇偶检错系统。它将用逻辑形式编码，以 便能够检错和
纠错。 用在海明码中的全部传输码字是由原来的和附加 的奇偶校验位组成的。 每一个这种奇偶位被编在传输码字的特定位置 上。实现得合适时，这个系统对于错误的数位无论是原有位中的，还 是附加校验位中的都能把它分离出来。 推求海明码时的一项基本考虑 是确定所需最少的校验位数 k。考虑长度为 m 位的，若附加了 k 个校 验位，则所发送的总长度为 m+k。满足条件：2PkP-1≥m+k。从理论上 讲， 校验位可放在任何位置， 但习惯上校验位被安排在 1、 4、 … 2、 8、 的位置上。图 1 列出了 m=4，k=3 时，位和校验位的分布情况。 码字位置 BB1B BB2B BB3B BB4B
BB5B BB6B BB7B 校验位 x x x 位 x x x x 复合码字 PB1B PB2B DB1B PB3B DB2B DB3B DB4B 图 1 海明码中校验位和位的定位 海明码的码距应该是 3，所以能纠正 1 位出错。而奇偶校验码的 码距才是 2，只能发现 1 位出错，但不能纠正（不知道那一位错） 。 无校验的码距是 1，它出任何一位出错后还是合法代码，所以也就无 法发现出错。 这是关于海明码的经典说法，即码距为 3，可以发现 2 位，或者 纠正 1 位错。应满足 2PkP-1≥m+k。 海明码的校验位 PBiB（i=1，2，3，…）在海明码的第 2Pi-1P 位置，数据位则依序从低到高占据汉明码中剩下的位置。我们来看看 数据位与校验位在汉明码中的位置： HB14BHB13BHB12BHB11BHB10BHB9BHB8BHB7BHB6BHB5BHB4BHB3BHB 2BHB1B DB9BDB8BDB7BDB6BDB5BDB4BPB4BDB3BDB2BDB1BPB3BDB0BPB2BPB1 B 基本数据类型和运算典型例题分析与解答 1 在 c 语言中，不允许有常量的数据类型是（） ①整型②结构型③字符型④字符串
【分析】C 语言中，允许出现整型、实型、字符型、字符串的常量， 其中整型常量又区分为短整型常量和长整型常量。 【答案】② 2 下列数据中，不属于常量的是（） ①123L②‘＼012‘③"12.3L"④12.3L 【分析】④中的数据不是常量，因为实型常量是不区分单精度和双精 度的，12.3 后跟字母 L 是错误的；①中是长整型常量；②中是以转 义字符方式出现的字符型常量；③中是字符串常量。 【答案】④ 3-12345E－3 代表的十进制实数是。 【分析】这是用指数形式表示的实型常量，对于指数形式“土 aaaaaE 土 bbb”的实数，其值为“土 aaaaax10 土 bbb”。 【答案】-12．345 4 字符串“““012“012”在内存中占用的字节数是 个。 【分析】 一个字符串所占用的内存字节数等到于其中字符的数目再加 1。题目中给出的字符串中‘““‘ 是 1 个转义字符；‘0‘、‘l‘、‘2‘分别都是单个字符；‘＼012‘是一个用 八进制数表示的转义字符，所以其中单个字符的数目为 5，该字符串 占用的内存字节数等于 5+l，其中增加的 1 个字
节用于存放“字符串 结束标记”符号‘＼0‘。 【答案】6 5 设短整型变量 x 的值为 12， 假定分配给 x 的内存单元地址是 0xff00， 和 0xff01，则在程序中能表示变量 x 的地址是（） ①0xff00②oxff01③&x④&12 【分析】C 语言规定，任何变量的地址，在程序中用“＆变量名”来表 示。 【答案】③ 6 下列说法中，错误的是（） ①变量的定义可以放在所有函数之外 ②变量的定义可以不放在本编译单位中，而放在其他编译单位中 ③变量的定义可以放在某个函数的函数头中 ④变量的定义可以放在某个复合语句的开头 【分析】①中定义的变量是正确的，这种变量是外部变量；②中定义 的变量是正确的， 这种变量在本编译单位中要说明为“外部参照型”变 量；④中定义的变量是允许的，这种变量称为内部变量，其作用域只 能是本复合语句。此外，在任何函数的函数体中都可以定义变量，所 定义的变量也是内部变量，其作用域是本函数。但是，在函数中定义
变量时， 只能在“函数体”的开头定义， 不能在“函数头部分”进行定义。 【答案】③ 7 变量的存储类型主要是指。 【分析】定义变量时的存储类型有 4 种选择：一是“自动型（auto）”， 这时变量被分配在可以重。 复使用的内存难栈区；二是“寄存器型（register)”，这时变量被分 配在主机（CPU）中的寄存器；三是“静态型（static）”，这时变量 被分配在不能重复使用的内存数据区； 四是“外部参照型 （extern） ”，这时仅说明该变量的定义是在其他编译单位，不在本编译单位中。由 上述分析，可以看出，定义变量时选择存储类型，主要是选择给变量 分配的单元在何处。 【答案】给变量分配的单元在何处 8 下列说法中，正确的是 ①自动型变量是分配在内存的数据区 ②寄存器型变量是分配在内存的数据区中 ③静态型变量是分配在内存的数据区中 ④外部参照型变量是分配在内存的数据区中 【分析】按照变量在定义时的存储类型，给变量分配内存将有 3 种方 式：一是内存的数据区，这个地方的单元是不能重复使用的，它指定 分配给“静态型（static）”变量；二是内存的堆栈区，这个地方的单 元是能重复使用的，它指定分配给‘启动型（auto）”变量；三是主机 （CPU） 中的寄存器对， 这个地方是可以重复使用的， 它指定分配给“寄 存器型（register）”变量；至于“外部参照型（extern）”变量不是 在本编译单位中定义的， 它只是用来说明需要在其他编译单位中去寻 找这个变量的定义，以便确定该变量的存储特性和数据类型。 【答案】③ 9 从变量的存储类型来看，不能对变量进行初始
化的是（） ①extern②auto③register④static 【分析】因为“外部参照型（extern)”变量的定义不是在这儿定义的， 这儿仅是说明该变量的定义在其他编译单位中， 所以这种存储类型的 变量不能初始化。 【答案】① 10 下列说法中，正确的是（） ①从变量的作用域角度，我们把变量分为“全局变量”和“局部变量” ②从不同编译单位的角度，我们把变量分为“内部变量”和“外部变量” ③外部变量总是全局变量，它的作用域是从定义点到本程序的末尾 ④静态型变量总是全局变量， 它的作用域是从定义点到本程序的末尾
【分析】①的分析：全局变量和局部变量是从变量的生存期角度来划 分的，在程序运行期间内始终存活的变量一律是全局变量；在程序运 行期间内，局部时间内存活的变量一律是局部变量。②的分析：内部 变量和外部变量是从变量的定义位置来划分的， 在函数内部定义的变 量一律是局部变量；在函数外部定义的变量一律是外部变量。④的分 析：静态型变量的存活期是整个程序的运行期，所以它是全局变量， 但是，如果该变量是在函数内部定义的，那它就是内部变量，内部变 量的作用域只能是所定义的函数内部，不是从定义点到程序的末尾。 【答案】③ 11 麦达式“13.5＞13L＜2.5”的值是。 【分析】注意这样的表达式在语法上是正确的。按照“关系运算将的 优先级和结合性”可知， 要先计算“＞”， 后计算“＜”。 计算“13． 5＞13L”， 结果为真（值为 1） ；接着计算“1＜2.5”，结果为 1。 【答案】l 12 设字符型变量 ch 中存放字符“A”，则执行“ch+++2”后，ch 中的字 符是。 【分析】按照多个运算符结合在一起时的确认规则：自左向右选择尽 可能多的合法运算符来看，表达式“ch+++2”应理解“+2”，由于“++”是 后缀运算符，所以先取出 ch 的值（字符“A”的 ASCll 代码值为 65） ， 执行“65+2”的运算，结果为 67。注意这是表达式的值，并不是变量由 中的值。由于变量 oh 还要进行“后缀”的“++”运算，所以变量 ch 的值 是“65+1”，其值为 66，是字符“B”。 【答案】B 13 关于表达式“2＞l＞0？3＞2＞l：4＞3＞2？5＞4＞3：6＞5＞4”的 准确说法是（） ①语法出错②表达式值为非 0③表达式值为 l④表达式值为 0 【分析】分析结出的表达式可知是一个条件表达式。按照条件运算符 和关系运算符的优先级来说，整个表达式相当于“（2＞1＞0）？ （3>2>1):（4＞3＞2）？（5＞4＞3）（6＞5＞4)”；再从条件运算符 ： 的结合性来说，整个表达式相当于“（2＞1＞0）？（3＞2＞1） ："， 所以该表达式的语法是正确的。 接下来我们
可以具体计算这个表达式 的值： 首先计算局部表达式“ （4＞3＞2） （5＞4＞3）（6＞5＞4） ？ ： ”， （4＞3＞2)的结果是=（1＞2）＝o；显然这个局部表达式的值就是表 达式"6＞5＞4".其值为 0，再计算整个表达式“（2＞1＞0）？（3＞2 ＞1） ：0”，其中（2＞1＞0）的结果是”的运算后，变量 ch2 中的字符 是。 【分析】按照圆括号优先的原则，先计算（ch1=‘b‘） ，则字符型变量 ch1 中存放的是字符‘B‘;由于（chl＝‘B‘）是一个赋值表达式，该表达
式的值就是赋予变量 chl 的值“B”，这个值是非以真） 。由于下面要进 行的运算是“逻辑或”，C 语言规定当出现“表达式 l：表达式 2”这样的 运算时，如果“表达式 1”的值为真，则这个结果为真，表达式 2 将不 再计算。按照这个原则，上述表达式中的“^，则该关系表达式的值是 ＿＿＿＿;如果某个逻辑表达式为假，则该逻辑表达式的值是 。 【分析】在 C 语言中，数据类型中没有设置逻辑型数据，而是用数值 型数据来代替。具体的规则如下： 当计算一个逻辑型表达式时，结果为真则值为肝结果为假则值为 0。 当把一个任意表达式作为逻辑表达式看待时，其值为非 0 则看作真； 其值为 0 时看作假。 【答案】10 18 设有整型变量 x，如果表达式“!x”值为 0，则 x 的值为； 如果表达式“！x”值为 1，则 x 的值为。 【分析】“!x”的值为 1，显然 x 的值为 0，这是很简单的。“!x”的值 为 0 时，则要具体分析 x 的值。一般读者很容易想到 x 的值为 1，这 个答案不能说是错误的，但是不完全。例如 x 的值为 2，“!x”的值也 为 0；x 的值为-1，“!x”的值也为见由此想到，C 语言中从逻辑角度来 判断某个表达式时，原为：表达式值为 0，代表假；表达式值为非 0， 代表真。 【答案】非 0 0 19 表达式“10L1.l”的数据类型是型。 【分析】C 语言规定的数据类型强制转换形式是： ，其结果是将指定 表达式值强制转换成指定的数据类型。 如果其中的表达式是常量或变 量，则可以不要圆括号，例如，“（数据类型符）变量运算符表达式”， 则只有“变量”的数据类型被转换，而不是“变量运算符表达式”的运算 结果值被转换。按照上述原则，题目中的“（Short)”仅将长整型常量 10 转换成短整型数据，再和单精度实数“1.1”运算，这时将利用运算 时的类型转换原则（就长不就短，数据长度小的转换成数据长度大 的） ，先将短整型的 10 转换成单精度数据，再进行运算，结果是单精 度型。 【答案】单精度 20 下列表达式中，不属十逗号表达式的是 ①a＝b，c②a，b＝c③a＝④a，(b＝c） 【分析】4 个备选
答案中的表达式都很简单，仅含有两个运算符：赋 值运算符和远号运算符。按照运算符的优先级别，“＝”优先于“，”，
所以赋值运算要先计算，这样备选答案①、②中显然最后计算的是远 号运算符， 当然是远号表达式； 备选答案④中赋值运算用圆括号括住， 显然是返号表达式；备选答案③中圆括号括住的是逗号运算符，所以 赋值运算要后算，这个表达式是赋值表达式。 【答案】③ 顺序结构、选择结构和循环结构的程序设计例题 1 在三种选择结构中，能用 2 个条件，控制从 3 个操作中选择一 个操作执行的选择结构是选择结构 【分析】能用 1 个条件，控制某个操作做或不做的选择结构是单分支 结构；能用 1 个条件，控制从 2 个操作中选择一个操作执行的选择结 构是双分支结构；能用 n 个条件，控制从 n＋l 个操作中选择一个操 作执行的选择结构是多分支结构。 【答案】多分支 2 在三种循环结构中，先执行循环操作内容”函数时，程序的开头必 须写一条包含命令为。 【分析】凡是使用系统函数的程序，都要在程序的开头写一条包含命 令，包含命令中的“头函数．h”是一个文件，其中有关于该系统函数 的定义。系统函数“getchar”是在名为“stdio．h； } 【分析】分析程序库中的“ch＝ch－32＋1；”语句，可知是将字符型 变量 ch 中的小写字母转换成对应的大写字母（－32）的后一个字母 （＋l） 。如果 ch 中的字母是‘a‘、‘b‘、 ，‘y‘，转换结果都不会出错， 但是，如果 ch 中的字母是‘Z‘，则-32 后是大写字母‘Z‘，再+l 后将不 是大写字母了。为了使其转换成‘A‘，需要用一个单分支结构来实现： 如果 ch 的值等于‘Z‘+l，则硬性将 ch 的值改成‘A‘。完成这个任务的 语句是一条单分支语句，正是所缺少的语句。 【答案】if（ch＝＝‘Z‘+l）h＝‘A‘； 9 不能正确计算下列分段函数的程序段是 -1x<0 y＝0x＝0 x>0 ①switch（x＜0）②if（x＞0） else }&ny＝-l ③y＝l；④y＝l； if（x＝＝0）if（x＜0） y＝0；y＝－l；
elseelse y＝－l；if（x＝＝0） y＝0; 【分析】先来分析备选答案①：表达式“x＜0”的值只有两种可能性， 成立值为 1、不成立值为 on 如果“x＜0”的值为 1（即 x＜0） ，则执行 “easel：”后的语句“y＝－l”后，退出 switch 语句，符合分段函数要 求。如果“x＜0”的值为 0（即 x＞＝0） ，则执行“case0：”后的 switch 语句。 switch 语句的表达式是“x＝＝0”， 该 结果也有两种： 成立为 1、 不成立为 0.如果“x＝＝0”的值为 1， 则执行“casel： ”后的语句“y＝0” 后，退出 switch 语句，符合分段函数要求。如果“x＝＝0”的
值为 0 （即 x＞0） ，则执行“case0：”后的语句“y=1”，也符合分段函数要求。 再分析备选答案②： 这是标准的用嵌套双分支结构来实现三分支的分 段函数，结果显然是能求解分段函数的。分析备选答案③：双分支语 句的条件是“x＝＝0”，条件成立时，y 值为 0，符合分段函数的要求， 条件不成立时，结果 y 值为－l，显然不符合分段函数的要求，所以 本题要选该答案。至于备选答案④，是能正确计算分段函数的，首先 置 y 为 1；接着用双分支结构处理“x＜0”和“x＞＝0”的两种情况：前 者使得 y 值为一 l；后者再执行一个单分支结构，如果“x＝＝0”则使 y 值为 0，否则不改变 y 值，保持 y 的原值 1，符合分段函数的要求。 【答案】③ 10 三种循环语句都能解决循环次数已经确定的次数型循环，其中 循环语句最适合。 【分析】当“for 语句；”中的表达式 1 为：整型变量 k＝l；表达式 2 为：整型变量 k＜＝n；表达式 3 为：整型变量 k++；则这个 for 循 环就是次数为 n 次的标准次数型循环结构。 【答案】for 11 执行下列程序段后的输出是 x＝l； whilex++，y＝x+++x； printf； ①6，10②5，8③4，6④3，4 【分析】我们可以使用逐步记录运行结果的方法来获得输出结果，记 录如下： x＝1； 进入循环， 条件满足执行循环体： 计算 x+十得 x 为 2， 计算 y＝x+++x， 得 y 为 4、x 为 3； 继续循环， 条件满足执行循环体： 计算 x+十得 x 为 4， 计算 y＝x+++x， 得 y 为 8、x 为 5；
继续循环，条件不满足退出循环； 输出 x 和 y 的值为 5，8。 【答案】② 12 执行下列程序段，其中的 do－while 循环一共执行＿次。 staticintx； dox+＝xx； while； 【分析】对静态型变量，不赋初值也有值，对整型变量，其值为 0。 执行循环语句 do-while 的循环体，x+＝xx 是 x＝x+＝0+＝0；再判断 控制循环的条件“x”，结果为 0，条件不成立，退出循环。所以循环仅 执行 1 次。 【答案】1 13 下列程序段的输出结果是 for for printf； ①②③④ 【分析】注意每次内层循环仅输出 1 个“”，所以只要分析出二重循环 的总次数即可。首先分析外层循环的次数：控制变量 i 的初值为 0； 终值为 0；步长为 1，所以外层循环次数为 1。再分析内层循环次数： 控制变量 j 的初值为 2；终值为 1；步长为-1，所以内层循环次数为 人内层循环体一共执行的次数等于外层循环次数乘以内层循环次数， 共计为 l2＝2。 【答案】① 14 执行下列程序段后的输出是。 x＝0； while for 【分析】 我们用执行程序并记录各变量值的方法来获得程序的输出结 果，记录如下： x＝0； 第一次执 while 循环，条件 x＜3 成立，执行 while
的循环体; 第一次执行 for 循环，条件 x＜4 成立，执行 for的循环体； 输出 x 的值问位整数，其值为 0)，然后 x++，x 值为 1； if－else 的条件 x＜3 成立，执订 continue，继续 for 循环，执行 x++，x 为 2；
第二次执行拉循环，条件 x＜4 成立，执行比 r 的循环体； 输出 x 的值 gotOLOOP； ①for；②x＝10； ③dox＝0；④x＝0； while；while; 【分析】先分析给出的程序段，很明显这段程序是用 goto 语句构成 的循环，控制循环的条件是“x＜1O”，循环要做的工作是“x＋＋”；当 x 值为 9 时，进行循环，通过“x＋＋”，使 x 值为 10 后，条件“x＜10” 将木再成立，退出循环，则此时 x 的值为 10。可以这样说，该段程 序的功能是使变量 x 的值为 10。以下来分析每个备选答案。分析备 选答案①：这是一个次数型、无循环体（循环体是空语句）的循环， 控制变量 x 的初值为 0，终值为 9，一共循环 10 次，每次对变量 x 加 1，结果变量 x 的值为 10。分析备选答案②：很明显，直接给变量 x 赋值为 10。分析备选答案③：这是一个当型循环语句，循环体是给 变量 x 赋值为 0， 控制循环的条件是“x＋＋＜10”， 1 次执行循环体， 第 变量 x 值为 0，控制循环的条“x＋＋＜10”成立，此时变量 x 值为 1， 继续循环，在循环体中又将变量 x 的值改为 0，显然，控制循环的条 件仍然成立， 继续循环， 由此看出， 这个循环是一个无限次的循环 （死 循环） ，木能完成使变量 x 值为 10 的功能，该答案符合题意。至于备 选答案④：进入 while 循环前的 x 值为 0，控制 while 循环的条件实 际上是 x＜9“x＜1O”，环要做的工作是“x＋＋”；当 x 值为 9 时，进行 循环，通过“x＋＋”，使 x 值为 10 后，条件“x＜10”将木再成立，退 出循环，则此时 x 的值为 10。可以这样说，该段程序的功能是使变 量 x 的值为 10。以下来分析每个备选答案。分析备选答案①：这是 一个次数型、无循环体（循环体是空语句）的循环，控制变量 x 的初 值为 0，终值为 9，一共循环 10 次，每次对变量 x 加 1，结果变量 x 的值为 10。分析备选答案②：很明显，直接给变量 x 赋值为 10。分 析备选答案③： 这是一个当型循环语句， 循环体是给变量 x 赋值为 0， 控制循环的条件是“x＋＋＜10”，第 1 次执行循环体，变量 x 值为 0， 控制循环的条件“x＋＋＜10”成立，此时变量 x 值为 1，继续循环，在 循环体中又将变量 x 的值改为 0，显然，控制循环的条件仍然成立， 继续循环，由此看出，这个循环是一个无限次的循环（死循环） ，木 能完成使变量 x 值为 10 的功能，该答案符合题意。“x＜10”，循环要 做的工作是
“x＋＋”；当 x 值为 9 时，进行循环，通过“x＋＋”，使 x 值为 10 后， 条件“x＜10”将木再成立， 退出循环， 则此时 x 的值为 10。 可以这样说，该段程序的功能是使变量 x 的值为 10。以下来分析每 个备选答案。分析备选答案①：这是一个次数型、无循环体（循环体 是空语句）的循环，控制变量 x 的初值为 0，终值为 9，一共循环 10
次，每次对变量 x 加 1，结果变量 x 的值为 10。分析备选答案②：很 明显，直接给变量 x 赋值为 10。分析备选答案③：这是一个当型循 环语句， 循环体是给变量 x 赋值为 0， 控制循环的条件是“x＋＋＜10”， 第 1 次执行循环体， 变量 x 值为 0， 控制循环的条件“x＋＋＜10”成立， 此时变量 x 值为 1，继续循环，在循环体中又将变量 x 的值改为 0， 显然，控制循环的条件仍然成立，继续循环，由此看出，这个循环是 一个无限次的循环（死循环） ，木能完成使变量 x 值为 10 的功能，该 答案符合题意。至于备选答案④：进入 while 循环前的 x 值为 0，控 制 while 循环的条件实际上是 x＜9（因为 x＋十是后缀） ，注意每次 循环后都会使得 x 加 1，当 x 为 8 时，由于条件“8＜9”，条件成立， 继续循环的同时 x 变为 9，再次循环后，条件“9＜9”不成立，退出循 环时，x 要再加 1，此时 x 值为 10。 【答案】③ 16 阅读下列程序，写出程序运行后的输出结果。 main 【分析】本程序的关键是 do－while 循环。控制循环的条件是 x 当前 值小于 999。从 k 所赋予的初值看，k 是从 100 开始的，直到”so 由 于控制循环的条件中 k 有一个后缀的++运算，所以，最后一次循环执 行时，k 值是 999。这个循环恰好是处理了所有的 3 位整数。 循环体中是单分支语句，条件成立时则输出此时的变量 k 值，显然这 个条件就是“k 能被 8 整除余 7，或者被 7 整除余算，因此可以写出所 缺少的条件。 【答案】|| 18 阅读下面列序，写出程序的主要功能。 main 【分析】这是标准的三分支结构，用嵌套的双分支语句实现 1，x＜ －10， 【答案】输入实数 x，按照下列公式计算并输出 y 值：y=2，－10<=x ＜=10， 3．10＜x。 19 编写一个程序，统计并输出能被 3 整除或能被 5 整除或能被 7 整 数的所有 3 位整数。 【分析】这是标准的次数型循环结构，控制变量 n 取值依次为 100、 101、…、999。循环体中判断 n 是否满足条件||||))，满足则输出 n， 这是一个单分支结构。
【答案】main 20 编写一个程序，依次输入 5 个学生的 7 门课程的成绩，每输入一 个学生的 7 门课程成绩后，立即统计并输出该学生的总分和平均分。 【分析】这是一个二重次数型循环结构。外