主要内容： ① 程序设计语言的基本概念。
② 程序设计语言的特点与分类。
③ 汇编程序和解释程序的工作原理及其区别。④ 编译程序的基本工作原理。
⑤ 算法的基本概念和算法的时间复杂度分析和空间复杂度分析。
⑥ 迭代算法的基本思想及其用法。
⑦ 穷举算法的基本思想。
⑧ 递推与递归算法的基本思想。
⑨ 回溯法、贪心法、分治法、动态规划法的基本思想。
软件设计师专题六： 程序设计语言基础和算法设计(20080409)在线专题授课音视频
（本课程正式学员可登录学习系统，进入对应课程，在窗口左边的“课程资料室”内进行在线浏览。）迭代法
f(x)=0
| f(x) |<μ，μ 为很小的数
分治法
function Binary_search(L, a, b, x)
if (a>b) return(-1);
else{
m=(a+b)/2;
if (x= = L[m]) return(m);
else if (x>L[m])
return (Binary_search(L, m+1, b, x));
else return (Binary_search(L, a, m-1, x));
}}
回溯法
N个数，取r个组合
假设N=5，r=3.
专题六： 程序设计语言基础和算法设计例题
例题1【2006年软考试题】
试题五(15分)
阅读下列说明、图和C代码，将应填入 （n） 处的字句写在答题纸的对应栏内。
【说明5-1】
B树是一种多叉平衡查找树。一棵m阶的B树，或为空树，或为满足下列特性的m叉树：
① 树中每个结点至多有m棵子树；
② 若根结点不是叶子结点，则它至少有两棵子树；
③ 除根之外的所有非叶子结点至少有 棵子树；
④ 所有的非叶子结点中包含下列数据信息
(n，A0，K1，A1，K2，A2，…，Kn，An)
其中：Ki(i=1，2，……，n)为关键字，且Ki<Ki+1(i=1，2，…，n-1)；Ai(i=0，1，…，n)为指向子树根结点的指针，且指针Ai-1所指子树中所有结点的关键字均小于Ki，Ai+1所指子树中所有结点的关键字均大于Ki，n为结点中关键字的数目。
⑤ 所有的叶子结点都出现在同一层次上，并且不带信息（可以看作是外部结点或查找失败的结点，实际上这些结点不存在，指向这些结点的指针为空）。
例如，一棵4阶B树如图5-1所示（结点中关键字的数目省略）。
图5-1 4阶B树示例
B树的阶M、bool类型、关键字类型及B树结点的定义如下：
#define M 4 /*B树的阶*/
typedef enum {FALSE = 0,TRUE = 1} bool;
typedef int ElemKeyType;
typedef struct BTreeNode{
int numkeys; /*结点中关键字的数目*/
struct BTreeNode *parent ; /*指向父结点的指针，树根的父结点指针为空*/
struct BTreeNode *A[M]; /*指向子树结点的指针数组*/
ElemKeyType K[M]; /*存储关键字的数组,K[0]闲置不用*/
}BTreeNode;
函数SearchBtree(BTreeNode* root, ElemKeyType akey, BTreeNode **ptr)的功能是：在给定的一棵M阶B树中查找关键字akey所在结点，若找到则返回TRUE，否则返回FALSE。其中,root是指向该M阶B树根结点的指针，参数ptr返回akey所在结点的指针，若akey不在该B树中，则ptr返回查找失败时空指针所在结点的指针。例如，在图5-1所示的4阶B树中查找关键字25时，ptr返回指向结点e的指针。
注：在结点中查找关键字akey时采用二分法。
【函数5-1】
bool SearchBtree(BTreeNode* root, ElemKeyType akey, BTreeNode **ptr)
{
int lw, hi, mid;
BTreeNode *p = root;
*ptr = NULL;
while ( p ) {
lw = 1; hi = (1) ;
while (lw <= hi) {
mid = (lw + hi) / 2;
if (p -> K[mid] == akey){
*ptr = p;
return TRUE;
}
else
if ( (2) )
hi = mid - 1;
else
lw = mid + 1;
}
*ptr = p;
p = (3) ;
}
return FALSE;
}
例题2 2007年下半年考题
试题四(共15分)
阅读下列说明和图，回答问题1至问题3，将解答填入答题纸的对应栏内。
【说明】
某机器上需要处理n个作业job1, job2, …, jobn，其中：
(1) 每个作业jobi(1≤i≤n)的编号为i，jobi有一个收益值p[i]和最后期限值d[i]；
(2) 机器在一个时刻只能处理一个作业，而且每个作业需要一个单位时间进行处理，一旦作业开始就不可中断，每个作业的最后期限值为单位时间的正整数倍；
(3) job1～jobn的收益值呈非递增顺序排列，即p[1]≥p[2]≥…≥p[n]；
(4) 如果作业jobi在其期限之内完成，则获得收益p[i]；如果在其期限之后完成，则没有收益。
为获得较高的收益，采用贪心策略求解在期限之内完成的作业序列。图4-1是基于贪心策略求解该问题的流程图。
图4-1 贪心策略流程图
(1) 整型数组J[]有n个存储单元，变量k表示在期限之内完成的作业数，J[1..k]存储所有能够在期限内完成的作业编号，数组J[1..k]里的作业按其最后期限非递减排序，即d[J[1]]≤ … ≤d[J[k]]。
(2) 为了方便于在数组J中加入作业，增加一个虚拟作业job0，并令d[0] = 0，
J[0] = 0。
(3) 算法大致思想：先将作业job1的编号1放入J[1]，然后，依次对每个作业jobi (2≤i≤n)进行判定，看其能否插入到数组J中，若能，则将其编号插入到数组J的适当位置，并保证J中作业按其最后期限非递减排列，否则不插入。
jobi能插入数组J的充要条件是：jobi和数组J中已有作业均能在其期限之内完成。
(4) 流程图中的主要变量说明如下：
i：循环控制变量，表示作业的编号；
k：表示在期限内完成的作业数；
r：若jobi能插入数组J，则其在数组J中的位置为r+1；
q：循环控制变量，用于移动数组J中的元素。
【问题1】（9分）
请填充图4-1中的空缺(1)、(2)和(3)处。
【问题2】(4分)
假设有6个作业job1, job2, …, job6；
完成作业的收益数组p=(p[1],p[2],p[3],p[4],p[5],p[6]) = (90,80,50,30,20,10)；
每个作业的处理期限数组d=(d[1],d[2],d[3],d[4],d[5],d[6]) = (1,2,1,3,4,3)。
请应用试题中描述的贪心策略算法，给出在期限之内处理的作业编号序列 (4) （按作业处理的顺序给出），得到的总收益为 (5) 。
【问题3】(2分)
对于本题的作业处理问题，用图4-1的贪心算法策略，能否求得最高收益？ (6) 。用贪心算法求解任意给定问题时，是否一定能得到最优解？ (7) 。
例题3 2007年上半年考题
背包问题
试题六
阅读下列程序说明和C代码，将应填入_（n）_处的字句写在答卷的对应栏内。
【程序６说明】
本程序从n种不同重量、不同价值的物品中选取一部分物品。要求在不超过限定重量limw的前提下，使被选取的那些物品的总价值较大。这里约定limw不超过n种物品的重量总和也没有一种物品的重量超过limw，并且各物品的价值都大于0。
程序中，n种物品被顺序编号为0、1、2、、n-1。
【程序６】
#include <stdio.h>
#define N 100
double limw
int opts[N] /* 存储临时最佳的选择方案，当opts[i]为1，物品i在解中 */
struct elem { double weight
double value
} a[N] /* 物品的重量和价值信息 */
int k n
struct { int flg /* 物品的考虑状态：0：不选，1：将被考虑，2：曾被选中 */
double tw /* 已达到的总重量 */
double tv /* 期望的总价值 */
｝twv[N] /* 当前候选解中各物品的考虑状态，以及候选解的状态 */
main()
{ double maxv find()
printf(“Enter number of matter. ”) scanf(“d” &n)
printf(“Enter limit of weight. ”) scanf(“1f” &limw)
printf(“Enter weight and values of matters. ”)
for (k = 0 k < n k) scanf(“1f1f” &a[k].weight &a[k].value)
maxv = find(an)
for(k = 0 k < n k) if(opts[k]) printf(“4d” k)
printf(“\nTotal value = 1f\n” maxv)
}
next(int i double tw double tv) /* 将考虑i号物品 */
{ twv[i].flg = 1 twv[i].tw = tw twv[i].tv = tv }
look(int i int *f double *tw double *tv) / * 取i 号物品在解中的状态信息 * /
{ *f = twv[i].flg *tw = twv[i].tw *tv = twv[i].tv }
double find (struct elem *a int n )
{ int i k f
double maxv tw tv totv = 0.0
maxv = 0
for(k=0 k < n k) ____(1)____
next(0 0.0 totv)
i = 0
while(i >= 0) {
look(i &f &tw &tv)
switch (f) {
case 1: twv[i].flg /* 先考虑被选中 */
if(____(2)____ <= limw) /* 选中可行吗？ */
if(i < n-1) { /* 后面还有物品吗？ */
next(____(3)____) /* 置i1物品的状态 */
i
}
else if (tv > maxv) { /* 是一个更好的候选解吗？ */
maxv = tv
for(k = 0 k < n k)
opts[k] = twv[k].flg != 0
}
break
case 0: i break /* 回退 */
default: /* f == 2 */
twv[i].flg = 0
if (____(4)____) /* 不选i号物品可行吗？ */
if(i < n-1) { /* 后面还有物品吗？ */
next(____(5)____)
i
}
else {
maxv = tv – a[i].value
for(k = 0 k < n k)
opts[k] = twv[k].flg != 0
i
}
break
}
}
参考答案
试题五【2006软考试题】
（1） p -> numkeys
（2） p -> K[mid] > akey
（3） p -> A[hi]
【2007年下半年考题】
试题四 【2007年上半年考题】
（1）k=0
（2）j<=N
（3）k++
（4）d[i]+6
（5）O(2n)
背包问题