问答题

试题三
阅读以下说明和流程图，从供选择的答案中选出应填入流程图（n）处的字句写在答题纸的对应栏内。
[说明]
一个印刷电路板的布线区域可分成n×m 个方格，如图3-1(a)所示，现在需要确定电路板中给定的两个方格的中心点之间的最短布线方案。电路只能沿水平或垂直方向布线，如图3-1(b)中虚线所示。为了避免线路相交，应将已布过线的方格作封锁标记，其他线路不允许穿过被封锁的方格。
[图3-1]

设给定印刷电路板的起始方格x 与目的方格y 尚未布线，求这两个方格间最短布线方案的基本思路是：从起始方格x 开始，先考查距离起始方格距离为1 的可达方格并用一个路径长度值标记，然后依次考查距离为2、3、...的可达方格，直到距离为k 的某一个可达方格就是目标方格y 时为止，或者由于不存在从x 到y 的布线方案而终止。布线区域中的每一个方格与其相邻的上、下、左、右四个方格之间的距离为1，依次沿下、右、上、左这四个方向考查，并用一个队列记录可达方格的位置。表3-1 给出了沿这四个方向前进1 步时相对于当前方格的相对偏移量。
[表3-1]

例如，设印刷电路板的布线区域可划分为一个6×8 的方格阵列，如图3-2(a)所示，其中阴影表示已封锁方格。从起始方格x(位置[3,2]，标记为0)出发，按照下、右、上、左的方向依次考查，所标记的可达方格如图3-2(a)所示，目标方格为y(位置[4,7]，标记为10)，相应的最短布线路径如图3-2(b)虚线所示。
[图3-2]

图3-3 和图3-4 所示的流程图即利用上述思路，在电路板方格阵列中进行标记，图中使用的主要符号如表3-2 所示。在图3-4 中，设置电路板初始格局即将可布线方格置为数值-1、已布线方格(即封锁方格)置为-9。设置方格阵列“围墙”的目的是省略方格位置的边界条件判定，方法是在四周附加方格，并将其标记为-9(与封锁标记相同)。
[表3-2]

[图3-3]

[图3-4]

● 供选择的答案
[a] Found ≠true 　[b] Found =true
[c] T = Endpos　　[d] Q.insert(T)
[e] T←Q.delete()　[f] CurPos = EndPos
[g] I ≥ 4 [h] Curpos←Q.delete()
[I] Grid [T.row,T.col] = -1 [j] Grid [T.row , T.col] ≠ -1

【参考答案】

(1)Grid[T.row，T.co1]=1
(2)T=EndPos
(3)Q.insert(T)......

(↓↓↓ 点击下方‘点击查看答案’看完整答案 ↓↓↓)

<上一题目录下一题>

热门试题

问答题

从下列的3道试题（试题五至试题七）中任选1道解答，如果解答的试题数超过1道，则题号小的1道解答有效。试题五阅读以下说明和C++代码，将应填入（n）处的字句写在答题纸的对应栏内。 [说明] 某绘图系统存在Point、Line、Square 三种图元，它们具有Shape 接口，图元的类图关系如图5-1 所示。现要将Circle 图元加入此绘图系统以实现功能扩充。已知某第三方库已经提供了XCircle 类，且完全满足系统新增的Circle 图元所需的功能，但XCircle 不是由Shape派生而来，它提供的接口不能被系统直接使用。代码5-1 既使用了XCircle 又遵循了Shape 规定的接口，既避免了从头开发一个新的Circle 类，又可以不修改绘图系统中已经定义的接口。代码5-2 根据用户指定的参数生成特定的图元实例，并对之进行显示操作。绘图系统定义的接口与XCircle 提供的显示接口及其功能如下表所示： [图5-1] [代码5-1] class Circle : public___(1)____{ private: _______(2)________m_circle; public: void display(){ m_circle._____(3)_____; } }; [代码5-2] class Factory{ public : _____(4)_____getShapeInstance(int type){ 生成特定类实例 switch (type){ case 0: return new point; case 1: return new Rectangle; case 2: return new line; case 3: return new Circle; default: return NULL; } } }; void main (int argc , char *argv[]){ if (argc ! =2){ cout << “error parameters !”< return; } int type = atoi (argv[ l ]); Factory factory; Shape *s; s = factory._____(5)____; if (s ==NULL){ cout <<”Error get the instance !” << endl; return; } c->display(); __(6)___; return; }

问答题

试题六阅读以下说明和Java 代码，将应填入（n）处的字句写在答题纸的对应栏内。 [说明] 某绘图系统存在Point、Line、Square 三种图元，它们具有Shape 接口，图元的类图关系如图6-1 所示。现要将Circle 图元加入此绘图系统以实现功能扩充。已知某第三方库已经提供了XCircle 类，且完全满足系统新增的Circle 图元所需的功能，但XCircle 不是由Shape派生而来，它提供的接口不能被系统直接使用。代码6-1 既使用了XCircle 又遵循了Shape 规定的接口，既避免了从头开发一个新的Circle 类，又可以不修改绘图系统中已经定义的接口。代码6-2 根据用户指定的参数生成特定的图元实例，并对之进行显示操作。绘图系统定义的接口与XCircle 提供的显示接口及其功能如下表所示： [图6-1] [代码6-1] class Circle ____(1)______{ private ___(2)___ pxc; public Circle () {pxc = new ___(3)___; } public void display(){ pxc. ___(4)___; } } [代码6-2] public class Factory{ public___(5)___getShape Instance(int tyoe){ 生成特定类实例 switch(type){ case 0:return new point(); case 1: return new Rectangle(); case 2: return new line(); case 3: return new Circle(); default: return null } } }; public class App{ public static viod main (String argv[]){ if (argv.length ! =1){ System.out.println (“error parameters !”); Return; } int type = (new Integer(argv[0])).intValue(); Factory factory = new Factory(); Shape s; S = factory.___(6)____; If (s == null){ System.out.println(“Error get instance !”); Return; } s.display(); return; } }

相关试题