第1题
阅读下列说明和c函数代码,将应填入 (n) 处的字句写在答题纸的对应栏内。
【说明】
对二叉树进行遍历是二叉树的一个基本运算。遍历是指按某种策略访问二叉树的每个结点,且每个结点仅访问一次的过程。函数InOrder。()借助栈实现二叉树的非递归中序遍历运算。
设二叉树采用二叉链表存储,结点类型定义如下:
typedef struct BtNode{
ElemTypedata; /*结点的数据域,ElemType的具体定义省略*/
struct BtNode*ichiid,*rchild; /*结点的左、右弦子指针域*/
)BtNode,*BTree;
在函数InOrder()中,用栈暂存二叉树中各个结点的指针,并将栈表示为不含头结点
的单向链表(简称链栈),其结点类型定义如下:
typedef struct StNode{ /*链栈的结点类型*/
BTree elem; /*栈中的元素是指向二叉链表结点的指针*/
struct StNode*link;
}S%Node;
假设从栈顶到栈底的元素为en、en-1、…、e1,则不含头结点的链栈示意图如图5—5
所示。
【C函数】
int InOrder(BTree root) /*实现二叉树的非递归中序遍历*/
{
BTree ptr; /*ptr用于指向二又树中的结点*/
StNode*q; /*q暂存链栈中新创建或待删除的结点指针+/
StNode*stacktop=NULL; /*初始化空栈的栈顶指针stacktop*/
ptr=root; /*ptr指向二叉树的根结点*/
while( (1 ) I I 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*/
第2题
阅读下列说明,回答问题l和问题2,将解答填入答题纸的对应栏内。
【说明】
现需在某城市中选择一个社区建一个大型超市,使该城市的其他社区到该超市的距离总和最小。用图模型表示该城市的地图,其中顶点表示社区,边表示社区间的路线,边上的权重表示该路线的长度。
现设计一个算法来找到该大型超市的最佳位置:即在给定图中选择一个顶点,使该顶点到其他各顶点的最短路径之和最小。算法首先需要求出每个顶点到其他任一顶点的最短路径,即需要计算任意两个顶点之间的最短路径;然后对每个顶点,计算其他各顶点到该顶点的最短路径之和;最后,选择最短路径之和最小的顶点作为建大型超市的最佳位置。
下面是求解该问题的伪代码,请填充其中空缺的(1)至(6)处。伪代码中的主要变量说明如下:
W:权重矩阵
n:图的顶点个数
sP:最短路径权重之和数组,SP[i]表示顶点i到其他各顶点的最短路径权重之和,i从1到n
rain_SP:最小的最短路径权重之和
min_v:具有最小的最短路径权重之和的顶点
i:循环控制变量
j:循环控制变量
k:循环控制变量
LOCATE-SHOPPINGMALL(W,n)
1 D(0)=W
2 for(1)
3 for i=1 t0 n
4 for j=1 t0 n
5
6 (2)
7 else
8 (3)
9 for i=1 to n
10 sP[i] =O
11 for j=1 to n
12 (4)
13 min sP=sP[1]
14 (5)
15 for i=2 t0 n
16 if min sP>sP[i]
17 min sP=sP[i]
18 min V=i
19 return (6)
第3题
阅读下列函数说明和C函数,将应填入(n)处。
【函数3说明】
函数DeleteNode(Bitree * r,int e)的功能是:在树根结点指针为r的二叉查找(排序)树上删除键值为e的结点,若删除成功,则函数返回0,否则函数返回-1。二叉查找树结点的类型定义为:
typedef struct Tnode{
int data; /*结点的键值*/
struct Tnode * Lchild,*Rchild; /*指向左、右子树的指针*/
} * Bitree;
在二叉查找树上删除一个结点时,要考虑三种情况:
①若待删除的结点p是叶子结点,则直接删除该结点;
②若待删除的结点p只有一个子结点,则将这个子结点与待删除结点的父结点直接连接,然后删除结点P;
③若待删除的结点p有两个子结点,则在其左子树上,用中序遍历寻找关键值最大的结点s,用结点s的值代替结点p的值,然后删除结点s,结点s必属于上述①、②情况之一。
【函数3】
int DeleteNode(Bitree * r,int e){
Bitree p=*r,pp,s,c;
while((1)){ /*从树根结点出发查找键值为e的结点*/
pp=p;
if(e<p->data)p=p->Lchild;
else p=p->Rchild;
{
if(!p)return-1; /*查找失败*/
if(p->Lchild &&p->Rchild){/*处理情况③*/
s=(2); pp=p;
while((3)){pp=s;s=s->Rchild;}
p->data=s->data;p=s;
}
/*处理情况①、②*/
if((4))c=p->Lchild;
else c=p->Rchild;
if(p==*r)*r=c;
else if((5))pp->Lchild=c;
else pp->Rchild=c;
free(p);
return 0;
}
第5题
阅读以下说明和数据流图,回答问题1~3问题。
[说明]
干部信息管理系统(CMIS)是用于对干部信息进行管理的特定系统。利用该系统,干部科可以对本单位干部信息进行管理,根据不同命令对信息进行增、删、改、内部调动,打印人事表格,进行统计、检索。干部科输入的系统命令需要合法性检查才能被接受、处理。系统命令可以是检索命令、统计命令、打印命令、维护命令中的任何一种。干部科的输入的干部信息数据包括输入信息、检索项、统计项、打印项、维护项等条目。一个完整的输入信息应包括干部的档号、干部的姓名、干部的性别、干部的年龄、干部的级别、干部的职称、干部的政治面貌等内容。系统进行检索处理时可以根据干部的档号、姓名或年龄进行简单检索,也可以根据“档号+姓名”或者“性别+年龄”进行组合检索。系统进行统计处理时,可以根据干部的性别、年龄或职称进行简单统计,也可以根据“年龄+职称”或“性别+职称”进行综合统计。通过系统授权,用户可以对系统进行维护。当用户需要对系统进行维护时,输入维护命令,得到合法性确认后,可以对系统数据库信息进行修改维护。维护命令包括:增加命令,根据输入信息增加干部信息;修改命令,根据修改项修改干部信息;检索命令,根据检索项检索干部信息。系统可以输出统计信息、人事表格、检索信息以供干部科用户使用。
干部信息管理系统的顶层图如图9-1所示;干部信息管理系统的第0层DFD图如图9-2所示,其中,加工3的细化图如图9-3所示。
数据流图9-1缺少了一条数据流(在图9-2中也未给出该数据流),请给出此数据流的起点和终点,并采用说明中的词汇给出此数据流名。
第6题
阅读以下说明和C++代码,填入(n)处。
[说明]
以下C++代码使用虚函数实现了同一基类shape派生出来的Class rectangle、Class triangle、Class circle实现了计算矩形、圆形面积的计算。仔细阅读以下代码,将(n)处语句补充完整。
[代码5-1]
include<iostream.h>
define PI 3.14159
class shape {//基类
protected:
(1);
public:
(2);
(3);
};
[代码5-2]
class rectangle: public shape {
public:
rectangle (int x2,int y2,int r2): (4) {};
double area ( ) {return x*y; };
};
class circle: public shape {
public:
circle (int x3,int y3,int r3):(5){};
double area ( ) {return r*r*PI; };
};
[代码5-3]
void main ( )
{
rectangle r (10,20,0);
circle c (0,0,30);
shape (6);
cout<<"长方形面积="<<s1->area ( ) <<endl;
cout<<"圆形面积="<<s2->area ( ) <<endl;
}
[运行结果]
长方形面积=200
圆形面积=2827.43
第8题
阅读下列说明以及图10-7和图10-8,回答问题1、问题2和问题3。
[说明]
某高等院校的教学管理具有选课管理和成绩管理两大功能。选课管理主要完成以下工作:(1)录入与生成新学期课程表;(2)学生选课注册;(3)查询,学生、教师、教学管理员可以查询课程表,获得课程信息、学生选课信息和学生、教师信息;(4)选课注册信息的统计与报表生成。成绩管理主要的功能为: (1)成绩录入:教学管理员录入学生考试成绩;(2)成绩查询:教师、教学管理员可以查询学生考试成绩。。学生只允许查询自己的考试成绩,不允许查询他人的成绩;(3)成绩统计与报表生成:教学管理员进行成绩统计,打印统计报表。把学生选课注册信息传送给财务系统,以便计算学生应交纳的费用。
根据需要,系统设计的用例有“选课管理”、“成绩管理”、“查询课程信息”、“选课注册”、“管理开设课程”等用例。其中部分用例说明如下:
“查询课程信息”:学生、教师或教学管理员启动查询课程信息时,该用例开始运行。根据输入的查询要求(查询主题或关键字),显示有关的课程信息;
“选课注册”。当学生登录进行选课注册时,该用例开始运行,它提供了选择课程、注册、修改注册、删除注册等功能。学生登录需要用户标识(ID)和口令;
“管理开设课程”。 当教学管理员登录系统进行产生选课信息操作时, 该用例开始运行。 它首先检查用户标识(ID)和口令,然后从数据库中取出学生的选课注册数据,按照要求进行分类统计,生成选课注册报表。
活动者“学生”与用例“选课注册”的交互关系如下:当“学生”登录系统进入选课注册活动时,首先要输入用户标识(ID)和口令,经系统的“注册表单”接口对象验证,如果正确无误,则“学生”可以进行查询活动或选课活动,否则拒绝进入。若“学生”发出“查询”请求,系统的“选课注册表单”接口对象响应信息给“学生”,及发送增加或删除学生选课数据的消息。 “开设课程”对象响应该消息,找出数据库中的相关数据,增加或删除学生的姓名和所选的课程名,或做相应的修改,并把增加或删除学生课操作成功或失败的信息反馈给“选课注册表单”接口对象,“选课注册表单”接口对象再反馈给“学生”。如果“学生”按下“确认”键,则选课操作得到确认,发出提交请求。“选课注册表单”接口对象响应该请求,并发出“存储”消息。“开设课程”对象响应“存储”消息,进行数据库存储操作,选课数据存入数据库。若“学生”结束选课,发出“退出”系统请求,“注册表单”接口对象响应请求,关闭系统。
图10-7为系统的顶层UML用例图。图10-8为选课注册顺序图。
用例图解释了活动者与用例之间的交互关系。根据系统设计说明,将系统的顶层用例图补充完整。
第9题
从下列的3道式题(试题五至试题七)中任选1道解答。
如果解答的试题数超过1道,则题号小的1道解答有效。
阅读以下说明和C++码,将应填入(n)处的字名写在的对应栏内。
[说明] 利用c++的各种控制语句编写一个万年历程序,要求:显示任何年份的日历,日历以月份顺序排列,每月以星期顺序排列,类似于一般挂历上的格式。本程序包含如下两个函数:Leap ()用于判定指定的年份是闰年,Week ()用于计算year年份的1月1日是星期几,其判定规则为:
(1) 如果year 年份为1994年,则为星期六。
(2) 如果year 年份大于1994年,则星期值weekno 按下列公式计算:
differ=(year-1994)*(365%6)+(year-1993)/4-(year-2001)/100+(year-2001)/400 date=6+differ%7
weekno=(date6)? date-7:date
(3) 如果year 年份小于1994年,则星期值weekno 按下列公式计算:
differ=(1994-year)*(365%7)+(1996-year)/4-(2001-year)/100+(2000-year)/400 weekno=6-dder%7
include "iostream. h"
include "iomanip. h"
int leap(int n)
{
if( (1) )
return 0
else
return 1;
}
int week( int year )
{
int a1, differ, date, weekno;
if (year = = 1994)
a1 =0;
else if (year > 1994)
a1=1;
else a1= -1;
switch(a1)
{
case 0: return 6; break;
case 1:
{
(2)
date = 6 + differ% 7; weekno = ( date > 6) ? date - 7 date;
}
return weekno; break;
case - 1:
{
differ = ( 1994 - year) * (365%7) + (1996 - year)/4 - (2001 - year)/100 + (2000 - year)/400;
weekno =6-differ%7; } return weekno; break;
}
}
void main( )
}
int i,year,m2,n,j;
cout < < “Please input 某年数:”;
cin> >year;
if ( ! leap(year) )
(3);
else
m2 =28;
int month [12]: {31 ,m2,31,30,31,30,31,31,30,31,30,31 };
(4)
for ( i=0; i<12; i+ + )
{
cout< < < <end1< <setw(4*n) < <";
for(j=1 ;j< =month [i] ;j+ +)
{
cout< <setw(4) < <j;
n+ +;
if(n> =7)
{
(5)
cout < < end1;
}
}
}
}
为了保护您的账号安全,请在“上学吧”公众号进行验证,点击“官网服务”-“账号验证”后输入验证码“”完成验证,验证成功后方可继续查看答案!