软题库 学习课程
当前位置:信管网 >> 在线考试中心 >> 信息系统项目管理师题库 >> 试题查看
试卷年份2009年下半年
试题题型【分析简答题】
试题内容

阅读以下说明和C程序,将应填入 (n) 处的字句写在答题纸的对应栏内。
【说明】
现有n(n<1000)节火车车厢,顺序编号为1,2,3,„,n,按编号连续依次从A方向的铁轨驶入,从B方向铁轨驶出,一旦车厢进入车站(Station)就不能再回到A方向的铁轨上;一旦车厢驶入B方向铁轨就不能再回到车站,如图7-1所示,其中Station为栈结构,初始为空且最多能停放1000节车厢。

下面的C程序判断能否从B方向驶出预先指定的车厢序列,程序中使用了栈类型STACK,关于栈基本操作的函数原型说明如下:
void InitStack(STACK *s):初始化栈。
void Push (STACK *s,int e):将一个整数压栈,栈中元素数目增1。 void Pop (STACK *s):栈顶元素出栈,栈中元素数目减1。
int Top (STACK s):返回非空栈的栈顶元素值,栈中元素数目不变。 int IsEmpty (STACK s):若是空栈则返回1,否则返回0。
【C程序】
#include
/*此处为栈类型及其基本操作的定义,省略*/
int main(){
STACK station;
int state[1000];
int n;                                /*车厢数*/
int begin, i, j, maxNo;           /*maxNo为A端正待入栈的车厢编号*/
printf("请输入车厢数:");
scanf("%d",&n);
printf(“请输入需要判断的车厢编号序列(以空格分隔):”);
if(n<1)return-1;
for (i=0; iscanf("%d",&state[i]);
(1) /*初始化栈*/
maxNo=1;
for(i=0; i<n; ){  /*检查输出序列中的每个车厢号state[i]是否能从栈中获取*/
if( (2) ){    /*当栈不为空时*/
if (state[i]=Top(station)) {    /*栈顶车厢号等于被检查车厢号*/
printf("%d",Top(station));
Pop(&station);i++;

else
if ( (3) ) {
printf(“error\n”);
return 1;

else{
begin= (4)
for(j=begin+l;j <=state [i];j++) {
Push(&station, j);
}


else{   /*当栈为空时*/
begin=maxNo;
for(j=begin; j<=state[i];j++) {
Push(&station, j);

maxNo= (5)


printf("OK");
return 0;

查看答案

相关试题

4题: 阅读下列说明,回答问题1至问题2,将解答填入答题纸的对应栏内。
【说明】
0-1背包问题可以描述为:有n个物品,对i=1,2,…,n,第i个物品价值为vi ,重量为wi(vi,和wi为非负数),背包容量为W(W为非负数),选择其中一些物品装入背包,使装入背包物品的总价值最大,即,且总重量不超过背包容量,即,其中,xi∈{0,1},xi=0表示第i个物品不放入背包,xi=1表示第i个物品  放入背包。
​【问题1】(8分)
用回溯法求解此0-1背包问题,请填充下面伪代码中(1)~(4)处空缺。
回溯法是一种系统的搜索方法。在确定解空间后,回溯法从根结点开始,按照深度优先策略遍历解空间树,搜索满足约束条件的解。对每一个当前结点,若扩展该结点己经不满足约束条件,则不再继续扩展。为了进一步提高算法的搜索效率,往往需要设计一个限界函数,判断并剪枝那些即使扩展了也不能得到最优解的结点。现在假设已经设计了BOUND(v,w,k,W)函数,其中v, w, k和W分别表示当前已经获得的价值、当前背包的重量、己经确定是否选择的物品数和背包的总容量。对应于搜索树中的某个结点,该函数值表示确定了部分物品是否选择之后,对剩下的物品在满足约束条件的前提下进行选择可能获得的最大价值,若该价值小于等于当前已经得到的最优解,则该结点无需再扩展。
下面给出0-1背包问题的回溯算法伪代码。
函数参数说明如下:
W:背包容量;n:物品个数;w:重量数组;v:价值数组;fw:获得最大价值时背包的重量;fp:背包获得的最大价值;X:问题的最优解。
变量说明如下:
cw:当前的背包重量;cp:当前获得的价值;k:当前考虑的物品编号;Y:当前已获得的部分解。

​【问题2】(7分)
考虑表4-1的实例,假设有3个物品,背包容量为22。图4-1中是根据上述算法构造的搜索树,其中结点的编号表示了搜索树生成的顺序,边上的数字1/0分别表示选择/不选择对应物品。除了根结点之外,每个左孩子结点旁边的上下两个数字分别表示当前背包的重量和已获得的价值,右孩子结点旁边的数字表示扩展了该结点后最多可能获得的价值。为获得最优解,应该选择物品 (5) ,获得的价值为 (6) 。

对于表4-1的实例,若采用穷举法搜索整个解空间,则搜索树的结点数为 (7) ,而用了上述回溯法,搜索树的结点数为 (8) 。
答案解析与讨论:www.cnitpm.com/st/3808721842.html

5题: 阅读下列说明和C++代码,将应填入 (n) 处的字句写在答题纸的对应栏内。
【说明】
现欲构造一文件/目录树,采用组合(Composite)设计模式来设计,得到的类图如5-1所示:


答案解析与讨论:www.cnitpm.com/st/3808810811.html

6题: 阅读下列说明和Java代码,将应填入 (n) 处的字句写在答题纸的对应栏内。
【说明】
现欲构造一文件/目录树,采用组合(Composite)设计模式来设计,得到的类图如6-1所示:


答案解析与讨论:www.cnitpm.com/st/38089467.html