阅读下列说明，回答问题 1 和问题 2，将解答填入答题纸的对应栏内。 【说明】
现需在某城市中选择一个社区建一个大型超市，使该城市的其它社区到该超市的距离总和最小。用图模型表示该城市的地图，其中顶点表示社区，边表示社区间的路线，边上的权重表示该路线的长度。
现设计一个算法来找到该大型超市的最佳位置：即在给定图中选择一个顶点，使该顶点到其它各顶点的最短路径之和最小。算法首先需要求出每个顶点到其它任一顶点的最短路径，即需要计算任意两个顶点之间的最短路径；然后对每个顶点，计算其它各顶点到该顶点的最短路径之和；最后，选择最短路径之和最小的顶点作为建大型超市的最佳位置。 【问题 1】（12 分）
本题采用 Floyd-Warshall 算法求解任意两个顶点之间的最短路径。已知图 G 的顶点集合为V=2,..., } ， W =
ij}*为权重矩阵。设
d
(k)ij
为从顶点 i 到顶点 j 的一条最短路径的权重。当 k=0 时，不存在中间时，该最短路径上所有的中间顶点均属于集合 {1, 2,..., } 。 若中间顶
顶点，因此
d
(0)ij
= wij ；当 k>
点包括顶点k，则递归式。
d
(k)ij
=
d(k?1)ik+
d(k?1)kj；若中间顶点不包括顶点k ，则
d
(k)ij
=
d(k?1)ij。于是得到如下
Wij k=0
d(k)ij= min(d(k?1)ij)，d(k?1)ik+d(k?1)kj k>0 (n) 因为对于任意路径，所有的中间顶点都在集合{1, 2,..., } 内，因此矩阵D(n)={dij}n*n给出了任意两个顶点之间的最短路径，即对所有i，j∈V ，dij表示顶点i到顶点j的最短路径。
下面是求解该问题的伪代码，请填充其中空缺的 (1)至(6)处。伪代码中的主要变量说明如下： W：权重矩阵 n：图的顶点个数
SP：最短路径权重之和数组，SP[i]表示顶点 i 到其它各顶点的最短路径权重之和，i从 1 到 n min_SP：最小的最短路径权重之和
min_v：具有最小的最短路径权重之和的顶点 i：循环控制变量 j：循环控制变量 k：循环控制变量
LOCATE -SHOPPINGMALL(W, n) 1 D(0) = W 2 for （1） 3 for i = 1 to n 4 for j = 1 to n 5 if
(n)d(k?1)ij≤
d(k?1)ik+
d(k?1)kj
6 （2）
7 else
8 （3） 9 for i = 1 to n 10 SP[i] = 0 11 for j = 1 to n 12 （4） 13 min_SP = SP[1] 14 （5） 15 for i = 2 to n
16 if min_SP > SP[i] 17 min_SP = SP[i] 18 min_v = i 19
return （6） （用Ο符号表示）。
【问题 2】（3 分）
【问题 1】中伪代码的时间复杂度为 （7）
试题五（共 15 分）
阅读下列说明和 C 函数代码，将应填入 【说明】
对二叉树进行遍历是二叉树的一个基本运算。遍历是指按某种策略访问二叉树的每个结点，且每个结点仅访问一次的过程。函数 InOrder()借助栈实现二叉树的非递归中序遍历运算。
设二叉树采用二叉链表存储，结点类型定义如下： typedef struct BtNode{
ElemType data; /*结点的数据域，ElemType 的具体定义省略*/
struct BtNode *lchild,*rchild; /*结点的左、右孩子指针域*/ }BtNode, *BTree;
在函数 InOrder()中，用栈暂存二叉树中各个结点的指针，并将栈表示为不含头结点的单向链表（简称链栈），其结点类型定义如下：
typedef struct StNode{
BTree elem; /*链栈的结点类型*/
struct StNode *link; /*栈中的元素是指向二叉链表结点的指针*/
}StNode;
假设从栈顶到栈底的元素为 en、en-1、…、e1，则不含头结点的链栈示意图如图 5-1所示。
（n）
处的字句写在答题纸的对应栏内。
从下列的 3 道试题（试题五至试题七）中任选 1 道解答。 如果解答的试题数超过 1 道，则题号小的 1 道解答有效。 图 5-1 链栈示意图
【C 函数】
int InOrder(BTree root) /* 实现二叉树的非递归中序遍历 */ {
BTree ptr;
StNode *q;
/* ptr 用于指向二叉树中的结点 */
/* q 暂存链栈中新创建或待删除的结点指针*/
StNode *stacktop = NULL; /* 初始化空栈的栈顶指针 stacktop */
ptr = root; /* ptr 指向二叉树的根结点 */ while ( （1） || stacktop != NULL) {
while (ptr != NULL) {
q = (StNode *)malloc(sizeof(StNode)); if (q == NULL)
return -1;
q->elem = ptr;
(2) ;
stacktop = q; /*stacktop 指向新的栈顶*/ ptr = （3） ;
}
q = stacktop;
/*进入左子树*/
（4） ; /*栈顶元素出栈*/
visit(q); /*visit 是访问结点的函数，其具体定义省略*/ ptr = （5） ; /*进入右子树*/
free(q); /*释放原栈顶元素的结点空间*/ } return 0; }/*InOrder*/ 试题六（共 15 分）
阅读下列说明和 C++代码，将应填入 （n） 【说明】
现欲实现一个图像浏览系统，要求该系统能够显示 BMP、JPEG 和 GIF 三种格式的文件，并且能够在 Windows 和 Linux 两种操作系统上运行。系统首先将 BMP、JPEG 和 GIF三种格式的文件解析为像素矩阵，然后将像素矩阵显示在屏幕上。系统需具有较好的扩展性以支持新的文件格式和操作系统。为满足上述需求并减少所需生成的子类数目，采用桥接（Bridge）设计模式进行设计所得类图如图 6-1 所示。
处的字句写在答题纸的对应栏内。
图 6-1
幕上显示像素矩阵的代码则仅与操作系统相关。 【C++代码】
class Matrix{ //各种格式的文件最终都被转化为像素矩阵
//此处代码省略 };
class ImageImp{ public:
virtual void doPaint(Matrix m) = 0; //显示像素矩阵 m };
class WinImp : public ImageImp{ public:
void doPaint(Matrix m){ /*调用 windows 系统的绘制函数绘制像素矩阵*/ } };
class LinuxImp : public ImageImp{ public:
void doPaint(Matrix m){ /*调用 Linux 系统的绘制函数绘制像素矩阵*/ } };
类图
采用该设计模式的原因在于：系统解析 BMP、GIF 与 JPEG 文件的代码仅与文件格式相关，而在屏
class Image { public:
void setImp(ImageImp *imp){ （1） = imp;} virtual void parseFile(string fileName) = 0; protected:
（2） *imp; };
class BMP : public Image{ public:
void parseFile(string fileName){
//此处解析 BMP 文件并获得一个像素矩阵对象 m （3） ;// } };
class GIF : public Image{
//此处代码省略 };
class JPEG : public Image{
//此处代码省略 };
void main(){
//在 windows 操作系统上查看 demo.bmp 图像文件 Image *image1 = （4） ; ImageImp *imageImp1 = （5） ; （6）
image1->parseFile(\ }
现假设该系统需要支持 10 种格式的图像文件和 5 种操作系统，不考虑类 Matrix，若采用桥接设计模式则至少需要设计 （7） 试题七（共 15 分）
阅读下列说明和 Java 代码，将应填入 【说明】
现欲实现一个图像浏览系统，要求该系统能够显示 BMP、JPEG 和 GIF 三种格式的文件，并且能够在 Windows 和 Linux 两种操作系统上运行。系统首先将 BMP、JPEG 和 GIF三种格式的文件解析为像素矩阵，然后将像素矩阵显示在屏幕上。系统需具有较好的扩展性以支持新的文件格式和操作系统。为满足上述需求并减少所需生成的子类数目，采用桥接（Bridge）设计模式进行设计所得类图如图 7-1 所示。
（n）
处的字句写在答题纸的对应栏内。
个类。
显示像素矩阵 m
软件设计师考试历年试题
