第1页 / 共57页
第2页 / 共57页
第3页 / 共57页
第4页 / 共57页
第5页 / 共57页
第6页 / 共57页
第7页 / 共57页
第8页 / 共57页
广工数据结构anyview2019最新完整参考答案(含题目).docx
/*【题目】试写一算法，如果三个整数 a，b 和 c 的值
不是依次非递增的，则通过交换，令其为非递增。
***********/
void Descend(int &a, int &b, int &c)
/* 通过交换，令 a >= b >= c */
{
int d;
if(a<=b&&b<=c){d=a,a=c,c=d;}
}
/*【题目】试编写算法求一元多项式
P(x) = a0 + a1x + a2x^2 + ... + anx^n
的值 P(x0)，并确定算法中每一语句的执行次数和整个算法
的时间复杂度。
**********/
float Polynomial(int n, int a[], float x)
/* 求一元多项式的值 P(x)。
/* 数组 a 的元素 a[i]为 i 次项的系数，i=0,...,n */
{
*/
int i;
float P=a[n]*x+a[n-1];
for(i=n-1;i>=1;i--){
P=P*x+a[i-1];
}
if(n==0)P=a[n];
return P;
}
/*【题目】已知 k 阶裴波那契序列的定义为
f(0)=0, f(1)=0, ..., f(k-2)=0, f(k-1)=1;
f(n)=f(n-1)+f(n-2)+...+f(n-k), n=k,k+1,...
试编写求 k 阶裴波那契序列的第 m 项值的函数算法，
k 和 m 均以值调用的形式在函数参数表中出现。
**********/
Status Fibonacci(int k, int m, int &f)
/* 求 k 阶斐波那契序列的第 m 项的值 f */
{
int a[20],i,j;
if(m<0||k<=1)return ERROR;
for(i=0;i<=m;i++){a[i]=0;}
for(i=0;i<=m;i++){
if(i<=k-2)a[i]=0;
else if(i<=k-1)a[i]=1;
else for(j=i-k;j<=i-1;j++){
a[i]+=a[j];
}
}
f=a[m];
return OK;
}
/*【题目】试编写算法，计算 i!×2^i 的值并存入数组
a[0..n-1]的第 i-1 个分量中 (i=1,2,…,n)。假设计
算机中允许的整数最大值为 MAXINT，则当对某个 k
(1≤k≤n)使 k!×2^k>MAXINT 时，应按出错处理。注意
选择你认为较好的出错处理方法。
**********/
Status Series(int a[], int n)
/* 求 i!*2^i 序列的值并依次存入长度为 n 的数组 a；
/* 若所有值均不超过 MAXINT，则返回 OK，否则 OVERFLOW */
{
*/
int i;
for(i=1;i<=n;i++){
if(i==1)a[0]=1*2;
else a[i-1]=2*a[i-2]*i;
}
for(i=0;i<=n-1;i++){
if(a[i]>MAXINT)return OVERFLOW;
}
return OK;
}
/*【题目】假设有 A、B、C、D、E 五个高等院校进行田径对抗赛，
各院校的单项成绩均以存入计算机并构成一张表，表中每一行
的形式为：
项目名称 性别 校名 成绩 得分
编写算法，处理上述表格，以统计各院校的男、女总分和团体
总分，并输出。
**********/
void Scores(ResultType *result, ScoreType *score)
/* 求各校的男、女总分和团体总分, 并依次存入数组 score */
/* 假设比赛结果已经储存在 result[ ]数组中,
/* 并以特殊记录 {"", male, ' ', "", 0 }（域 scorce=0）*/
/* 表示结束
{
*/
*/
int i = 0;
while(result[i].sport != NULL){
switch(result[i].schoolname){
case 'A' : score[0].totalscore += result[i].score;
if(male == result[i].gender){
score[0].malescore += result[i].score;
}else{
score[0].femalescore += result[i].score;
}
break;
case 'B' : score[1].totalscore += result[i].score;
if(male == result[i].gender){
score[1].malescore += result[i].score;
}else{
score[1].femalescore += result[i].score;
}
break;
case 'C' : score[2].totalscore += result[i].score;
if(male == result[i].gender){
score[2].malescore += result[i].score;
}else{
score[2].femalescore += result[i].score;
}
break;
case 'D' : score[3].totalscore += result[i].score;
if(male == result[i].gender){
score[3].malescore += result[i].score;
}else{
score[3].femalescore += result[i].score;
}
break;
case 'E' : score[4].totalscore += result[i].score;
if(male == result[i].gender){
score[4].malescore += result[i].score;
}else{
score[4].femalescore += result[i].score;
}
break;
}
i++;
}
}
/*【题目】试写一算法，对序列 S 的第 i 个元素赋以值 e。
序列的类型定义为：
typedef struct {
ElemType *elem;
int
length;
} Sequence;
***********/
Status Assign(Sequence &S, int i, ElemType e)
/* 对序列 S 的第 i 个元素赋以值 e，并返回 OK。 */
/* 若 S 或 i 不合法，则赋值失败，返回 ERROR
*/
{
if(S.elem[0]==0)return ERROR;
else if(S.lengthdata=x;
S->next=NULL;
return S;
}
/*【题目】链表的结点和指针类型定义如下
typedef struct LNode {
ElemType data;
struct LNode *next;
} LNode, *LinkList;
试写一函数，构建长度为 2 且两个结点的值依次为 x 和 y 的链表。
**********/
LinkList CreateLinkList(ElemType x, ElemType y)
/* 构建其两个结点的值依次为 x 和 y 的链表。*/
/* 若构建失败，则返回 NULL。
*/
{
LNode *p,*S;
p=(LNode*)malloc(sizeof(LNode));
if(p==NULL)return NULL;
S=p;
S->data=x;
p=(LNode*)malloc(sizeof(LNode));
if(p==NULL)return NULL;
p->data=y;
S->next=p;
p->next=NULL;
return S;
}
/*【题目】链表的结点和指针类型定义如下
typedef struct LNode {
ElemType data;
struct LNode *next;
} LNode, *LinkList;
试写一函数，构建长度为 2 的升序链表，两个结点的值
分别为 x 和 y，但应小的在前，大的在后。
**********/
LinkList CreateOrdLList(ElemType x, ElemType y)
/* 构建长度为 2 的升序链表。 */
/* 若构建失败，则返回 NULL。 */
{
LNode *p1,*p2;
p1=(LNode*)malloc(sizeof(LNode));
if(p1==NULL)return NULL;
p2=(LNode*)malloc(sizeof(LNode));
if(p2==NULL)return NULL;
p1->data=x;
p2->data=y;
if(x<=y){
p1->next=p2;
p2->next=NULL;
return p1;
}
else {
p2->next=p1;
p1->next=NULL;
return p2;
}
}
/*【题目】试写一算法，实现顺序栈的判空操作
StackEmpty_Sq(SqStack S)。
顺序栈的类型定义为：
typedef struct {
ElemType *elem; // 存储空间的基址
int top;
int size;
int increment;
// 栈顶元素的下一个位置，简称栈顶位标
// 当前分配的存储容量
// 扩容时，增加的存储容量
// 顺序栈
} SqStack;
***********/
Status StackEmpty_Sq(SqStack S)
/* 对顺序栈 S 判空。
/* 若 S 是空栈，则返回 TRUE；否则返回 FALSE */
{
*/
if(S.top==0)return TRUE;
else return FALSE;
}
/*【题目】试写一算法，实现顺序栈的取栈顶元素操作
GetTop_Sq(SqStack S, ElemType &e)。
顺序栈的类型定义为：
typedef struct {
ElemType *elem;
int top;
int size;
int increment;
// 存储空间的基址
// 栈顶元素的下一个位置，简称栈顶位标
// 当前分配的存储容量
// 扩容时，增加的存储容量
// 顺序栈
} SqStack;
***********/
Status GetTop_Sq(SqStack S, ElemType &e)
/* 取顺序栈 S 的栈顶元素到 e，并返回 OK； */
/* 若失败，则返回 ERROR。
*/
{
if(S.top==0)return ERROR;
e=S.elem[S.top-1];
return OK;
}
/*【题目】试写一算法，实现顺序栈的出栈操作
Pop_Sq(SqStack &S, ElemType &e)。
顺序栈的类型定义为：
typedef struct {
ElemType *elem;
int top;
int size;
int increment;
// 存储空间的基址
// 栈顶元素的下一个位置，简称栈顶位标
// 当前分配的存储容量
// 扩容时，增加的存储容量
// 顺序栈
} SqStack;
***********/
Status Pop_Sq(SqStack &S, ElemType &e)
/* 顺序栈 S 的栈顶元素出栈到 e，并返回 OK；*/
/* 若失败，则返回 ERROR。
{
*/
if(S.top==0)return ERROR;
e=S.elem[S.top-1];
S.top--;
S.size-=S.increment;
return OK;
}
/*【题目】若顺序栈的类型重新定义如下。试编写算法，
构建初始容量和扩容增量分别为 size 和 inc 的空顺序栈 S。
typedef struct {
ElemType *elem; // 存储空间的基址
ElemType *top;
int size;
int increment;
// 当前分配的存储容量
// 扩容时，增加的存储容量
// 栈顶元素的下一个位置
} SqStack2;
***********/
Status InitStack_Sq2(SqStack2 &S, int size, int inc)
/* 构建初始容量和扩容增量分别为 size 和 inc 的空顺序栈 S。*/
/* 若成功，则返回 OK；否则返回 ERROR。
{
*/
if(size<0||inc<0)return ERROR;
ElemType *newbase;
newbase=(ElemType*)malloc(size*sizeof(ElemType));
if(newbase==NULL)return ERROR;
S.elem=newbase;
S.size=size;
S.increment=inc;
S.top=S.elem; //关键
return OK;
}
/*【题目】若顺序栈的类型重新定义如下。试编写算法，
实现顺序栈的判空操作。
typedef struct {
ElemType *elem; // 存储空间的基址
ElemType *top;
int size;
int increment;
// 当前分配的存储容量
// 扩容时，增加的存储容量
// 栈顶元素的下一个位置
} SqStack2;
***********/
Status StackEmpty_Sq2(SqStack2 S)
/* 对顺序栈 S 判空。
/* 若 S 是空栈，则返回 TRUE；否则返回 FALSE */
{
*/
if(S.top==S.elem)return TRUE;
else return FALSE;
}
/*【题目】若顺序栈的类型重新定义如下。试编写算法，
实现顺序栈的入栈操作。
typedef struct {
ElemType *elem; // 存储空间的基址
ElemType *top;
int size;
int increment;
// 当前分配的存储容量
// 扩容时，增加的存储容量
// 栈顶元素的下一个位置
} SqStack2;
***********/
Status Push_Sq2(SqStack2 &S, ElemType e)
/* 若顺序栈 S 是满的，则扩容，若失败则返回 ERROR。*/
/* 将 e 压入 S，返回 OK。
*/
{
ElemType *p;
if(S.top-S.elem<=S.size*(sizeof(ElemType))){
*(S.top)=e;
S.top++;
return OK;
}
else{
p=(ElemType*)realloc(S.elem,(S.size+S.increment)*sizeof(ElemType));
if(NULL==p)return ERROR;
S.elem=p;
S.size+=S.increment;
*(S.top)=e;
S.top++;
return OK;
}
return ERROR;
}
/*【题目】若顺序栈的类型重新定义如下。试编写算法，
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
