第4题： 阅读下列说明，回答问题1和问题2，将解答填入答题纸的对应栏内。
【说明】
现需在某城市中选择一个社区建一个大型超市，使该城市的其它社区到该超市的距离总和最小。用图模型表示该城市的地图，其中顶点表示社区，边表示社区间的路线，边上的权重表示该路线的长度。现设计一个算法来找到该大型超市的最佳位置：即在给定图中选择一个顶点，使该顶点到其它各顶点的最短路径之和最小。算法首先需要求出每个顶点到其它任一顶点的最短路径，即需要计算任意两个顶点之间的最短路径；然后对每个顶点，计算其它各顶点到该顶点的最短路径之和；最后，选择最短路径之和最小的顶点作为建大型超市的最佳位置。
​【问题1】（12分）
本题采用Floyd-Warshall算法求解任意两个顶点之间的最短路径。 已知图G 的顶点集合为V= {1，2，...，n } ，W= ｛Wij｝n*n 为权重矩阵。设 d (k)ij=为从顶点i到顶点 j的一条最短路径的权重。当k = 0时，不存在中间顶点，因此d(0)ij=wij当k >0 时，该最短路径上所有的中间顶点均属于集合 {1，2， ...， k｝若中间顶点包括顶点 k ，则d(k)ij=d(k-1)ik+d(k-1)kj若中间顶点不包括顶点则d(k-1)ij=d(k-1)i于是得到如下递归式

因为对于任意路径，所有的中间顶点都在集合{1，2， ...， n｝ 内，因此矩阵D(n)=｛d(n)ij｝n*n 给出了任意两个顶点之间的最短路径，即对所有i， j ∈V，d(n)ij表示顶点i到顶点 j的最短路径。
下面是求解该问题的伪代码，请填充其中空缺的 (1)至(6)处。 伪代码中的主要变量说明如下：
W：权重矩阵
n： 图的顶点个数
SP：最短路径权重之和数组，SP[i]表示顶点i到其它各顶点的最短路径权重之和，i从1到n
min_SP：最小的最短路径权重之和
min_v：具有最小的最短路径权重之和的顶点
i：循环控制变量
j：循环控制变量
k：循环控制变量

​【问题2】（3分）
​【问题3】中伪代码的时间复杂度为（7）用Ο 符号表示）。
答案解析与讨论：www.cnitpm.com/st/380806315.html

第5题： 阅读下列说明和C 函数代码，将应填入（n）处的字句写在答题纸的对应栏内。
【说明】
对二叉树进行遍历是二叉树的一个基本运算。遍历是指按某种策略访问二叉树的每个结点，且每个结点仅访问一次的过程。函数InOrder()借助栈实现二叉树的非递归中序遍历运算。
设二叉树采用二叉链表存储，结点类型定义如下：
typedef struct BtNode{
ElemTypedata;/*结点的数据域，ElemType的具体定义省略*/
struct BtNode *lchild，*rchild;/*结点的左、右孩子指针域*/
}BtNode， *BTree;

在函数InOrder()中，用栈暂存二叉树中各个结点的指针，并将栈表示为不含头结点的单向链表（简称链栈），其结点类型定义如下：
typedef struct StNode{  /*链栈的结点类型*/
BTree elem;  /*栈中的元素是指向二叉链表结点的指针*/
struct StNode *link;
}StNode;
假设从栈顶到栈底的元素为 en、en-1、…、e1，则不含头结点的链栈示意图如图 5-1所示。

【C函数】

答案解析与讨论：www.cnitpm.com/st/3808115165.html

第6题： 阅读下列说明和C++代码，将应填入 （n） 处的字句写在答题纸的对应栏内。
【说明】
现欲实现一个图像浏览系统，要求该系统能够显示BMP、JPEG 和GIF三种格式的文件，并且能够在Windows和Linux两种操作系统上运行。系统首先将BMP、JPEG 和GIF三种格式的文件解析为像素矩阵，然后将像素矩阵显示在屏幕上。系统需具有较好的扩展性以支持新的文件格式和操作系统。为满足上述需求并减少所需生成的子类数目，采用桥接（Bridge）设计模式进行设计所得类图如图6-1所示。

采用该设计模式的原因在于：系统解析BMP、GIF与JPEG文件的代码仅与文件格式相关，而在屏幕上显示像素矩阵的代码则仅与操作系统相关。
【C++代码】

现假设该系统需要支持10种格式的图像文件和5种操作系统，不考虑类Matrix，若采用桥接设计模式则至少需要设计（7）个类。
答案解析与讨论：www.cnitpm.com/st/3808215536.html