软件设计师下午考试历年c语言算法有哪些？ 有代码更好
最新回答
金泫雅
2024-04-19 06:46:10
试题五（共15分）
阅读以下说明和C代码，将应填入 （n） 处的字句写在答题纸的对应栏内。
【说明】
在一个简化的绘图程序中，支持的图形种类有点(point)和圆(circle)，在设计过程中采用面向对象思想，认为所有的点和圆都是一种图形(shape)，并定义了类型shape_t、point_t和circle_t分别表示基本图形、点和圆，并且点和圆具有基本图形的所有特征。
[C代码]
typedef enum { point,circle } shape_type; /* 程序中的两种图形：点和圆 */
typedef struct { /* 基本的图形类型 */
shape_type type; /* 图形种类标识：点或者圆 */
void (*destroy)(); /* 销毁图形操作的函数指针 */
void (*draw)(); /* 绘制图形操作的函数指针 */
} shape_t;
typedef struct { shape_t common; int x; int y; } point_t; /* 定义点类型，x、y为点坐标 */
void destroyPoint(point_t* this) { free(this); printf("Point destoryed!\n"); } /* 销毁点对象 */
void drawPoint(point_t* this) { printf("P(%d,%d)", this->x, this->y); } /* 绘制点对象 */
shape_t* createPoint(va_list* ap) { /* 创建点对象，并设置其属性 */
point_t* p_point;
if( (p_point = (point_t*)malloc(sizeof(point_t))) == NULL ) return NULL;
p_point->common.type = point; p_point->common.destroy = destroyPoint;
p_point->common.draw = drawPoint;
p_point->x = va_arg(*ap, int); /* 设置点的横坐标 */
p_point->y = va_arg(*ap, int); /* 设置点的纵坐标 */
return (shape_t*)p_point; /* 返回点对象指针 */
}
typedef struct { /* 定义圆类型 */
shape_t common;
point_t *center; /* 圆心点 */
int radius; /* 圆半径 */
} circle_t;
void destroyCircle(circle_t* this){
free( （1） ); free(this); printf("Circle destoryed!\n");
}
void drawCircle(circle_t* this) {
printf("C(");
（2） .draw( this->center ); /* 绘制圆心 */
printf(",%d)", this->radius);
}
shape_t* createCircle(va_list* ap) { /* 创建一个圆，并设置其属性 */
circle_t* p_circle;
if( (p_circle = (circle_t*)malloc(sizeof(circle_t))) == NULL ) return NULL;
p_circle->common.type = circle; p_circle->common.destroy = destroyCircle;
p_circle->common.draw = drawCircle;
（3） = createPoint(ap); /* 设置圆心 */
p_circle->radius = va_arg(*ap, int); /* 设置圆半径 */
return p_circle;
}
shape_t* createShape(shape_type st, ...) { /* 创建某一种具体的图形 */
va_list ap; /* 可变参数列表 */
shape_t* p_shape = NULL;
（4） (ap, st);
if( st == point ) p_shape = createPoint( &ap); /* 创建点对象 */
if( st == circle ) p_shape = createCircle(&ap); /* 创建圆对象 */
va_end(ap);
return p_shape;
}
int main( ) {
int i; /* 循环控制变量，用于循环计数 */
shape_t* shapes[2]; /* 图形指针数组，存储图形的地址 */
shapes[0] = createShape( point, 2, 3); /* 横坐标为2，纵坐标为3 */
shapes[1] = createShape( circle, 20, 40, 10); /* 圆心坐标(20,40)，半径为10 */
for(i=0; i<2; i++) { shapes[i]->draw(shapes[i]); printf("\n"); } /* 绘制数组中图形 */
for( i = 1; i >= 0; i-- ) shapes[i]->destroy(shapes[i]); /* 销毁数组中图形 */
return 0;
}
[运行结果]
P(2,3)
08上：
试题四（10 分）
阅读下列说明，回答问题 1 至问题 3，将解答填入答题纸的对应栏内。
[说明]
以下代码由 C 语言书写，在输入三个整数后，能够输出最大数和最小数。
int main( void )
{
int a, b, c, max, min;
printf( "input three numbers: " );
scanf( "%d%d%d", &a, &b, &c );
if( a > b ) /*判断 1*/
{
max = a;
min = b;
}
else
{
max = b;
min = a;
}
if( max < c ) /*判断 2*/
max = c;
else if( min > c ) /*判断 3*/
min = c;
printf( "max=%d\nmin=%d", max, min );
return 0;
}
08下
【问题 3】（2 分） 【问题 1】中伪代码的时间复杂度为 （6） （用 Ο 符号表示）。
试题五（共 15 分）
阅读下列说明和 C 函数，将应填入 （n） 处的字句写在答题纸的对应栏内。
【说明】
已知集合 A 和 B 的元素分别用不含头结点的单链表存储，函数 Difference()用于求解集合 A 与 B 的差集，并将结果保存在集合 A 的单链表中。例如，若集合 A={5，10，20，15，25，30}，集合 B={5，15，35，25}，如图 5-1(a)所示，运算完成后的结果如图 5-1(b)所示。
图 5-1 集合 A、B 运算前后示意图
链表结点的结构类型定义如下：
typedef struct Node{
ElemType elem;
struct Node *next;
}NodeType;
【C 函数】
void Difference(NodeType **LA, NodeType *LB)
{
NodeType *pa, *pb, *pre, *q;
pre = NULL;
(1) ;
while (pa) {
pb = LB;
while ( （2） )
pb = pb->next;
if ( （3） ) {
if (!pre)
*LA = （4） ;
else
（5） = pa->next;
q = pa;
pa = pa->next;
free(q);
}
else {
（6） ;
pa = pa->next;
}
}
}
09年
试题五（共 15 分）
阅读下列说明和 C 函数代码，将应填入 （n） 处的字句写在答题纸的对应栏内。
【说明】
对二叉树进行遍历是二叉树的一个基本运算。遍历是指按某种策略访问二叉树的每个结点，且每个结点仅访问一次的过程。函数 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所示。
图 5-1 链栈示意图
【C 函数】
int InOrder(BTree root) /* 实现二叉树的非递归中序遍历 */
{
BTree ptr; /* ptr 用于指向二叉树中的结点 */
StNode *q; /* 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*/
09年下：
试题七（共 15 分）
阅读以下说明和C程序，将应填入 （n） 处的字句写在答题纸的对应栏内。
【说明】
现有 n（n < 1000）节火车车厢，顺序编号为 1,2,3,...,n，按编号连续依次从 A 方向的 铁轨驶入，从 B 方向铁轨驶出，一旦车厢进入车站（Station）就不能再回到 A 方向的铁轨 上；一旦车厢驶入 B 方向铁轨就不能再回到车站，如图 7-1 所示，其中 Station 为栈结构， 初始为空且最多能停放 1000 节车厢。
图 7-1 车站示意图
下面的 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<stdio.h>
/*此处为栈类型及其基本操作的定义，省略*/
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; i<n; i++) /* 读入需要驶出的车厢编号序列,存入数组 state[] */
scanf("%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+1; 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;
}
追问
我是想问回溯啊 贪婪之类的 有吗？
萌傻
2024-04-19 00:12:55
热门标签
