第1页 / 共99页
第2页 / 共99页
第3页 / 共99页
第4页 / 共99页
第5页 / 共99页
第6页 / 共99页
第7页 / 共99页
第8页 / 共99页
广工数据结构上机答案.doc
数据结构习题集 第1章答案
◆1.16② 试写一算法，如果三个整数 X，Y 和 Z 的值不是依次非递增的，则通过交换，令
其为非递增。
要求实现下列函数：
void Descend(int &x, int &y, int &z); /* 按从大到小顺序返回 x，y 和 z 的值 */
void Descend(int &x, int &y, int &z)
/* 按从大到小顺序返回 x，y 和 z 的值 */
{
int t;
if(x<=y){t=x;x=y;y=t;}
if(y<=z){t=y;y=z;z=t;}
if(x<=y){t=x;x=y;y=t;}
printf("%d,%d,%d",x,y,z);
}
/*把 x,y,z 进行从大到小排序*/
◆1.17③ 已 知 k 阶 裴 波 那 契 序 列 的 定 义 为 f0=0,
fk-1=1;fn=fn-1+fn-2+...+fn-k,
法，k 和 m 均以值调用的形式在函数参数表中出现。
fk-2=0,
n=k,k+1,...试编写求 k 阶裴波那契序列的第 m 项值的函数算
f1=0,
...,
要求实现下列函数：
Status Fibonacci(int k, int m, int &f);
/* 如果能求得 k 阶斐波那契序列的第 m 项的值 f，则返回 OK；*/
/* 否则（比如，参数 k 和 m 不合理）返回 ERROR
*/
Status Fibonacci(int k, int m, int &f)
/* 求 k 阶斐波那契序列的第 m 项的值 f
{
int t[60],sum,i,j;
*/
if(k<2||m<0) return ERROR;
if(m
}
return OK;
}
◆1.18③ 假设有 A、B、C、D、E 五个高等院校进行田径对抗赛，各院校的单项成绩均以
存入计算机并构成一张表，表中每一行的形式为:
项目名称 性别 校名 成绩 得分
编写算法，处理上述表格，以统计各院校的男、女总分和团体总分，并输出。
要求实现下列函数：
void Scores(ResultType *result, ScoreType *score);
/* 求各校的男、女总分和团体总分, 并依次存入数组 score */
/* 假设比赛结果已经储存在 result[ ]数组中,
/* 并以特殊记录 {"", male, ' ', "", 0 }（域 scorce=0）*/
/* 表示结束
*/
*/
相关数据类型定义如下：
typedef enum {female,male} Sex;
typedef struct{
char *sport;
Sex
char schoolname; // 校名为'A','B','C','D'或'E'
char *result;
int score;
// 成绩
// 得分（7,5,4,3,2 或 1）
// 项目名称
gender;
// 性别（女：female；男：male）
} ResultType;
typedef struct{
int malescore;
// 男子总分
int femalescore; // 女子总分
int totalscore;
// 男女团体总分
} ScoreType;
void Scores(ResultType *result, ScoreType *score)
/* 求各校的男、女总分和团体总分, 并依次存入数组 score */
/* 假设比赛结果已经储存在 result[ ]数组中,
/* 并以特殊记录 {"", male, ' ', "", 0 }（域 scorce=0）*/
/* 表示结束
{
// ScoreType score;
*/
*/
int i=0;
while(result[i].sport!=NULL)
{
switch(result[i].schoolname)
{
/*使用 switch 语句记录各院校的成绩*/
2
case 'A':
score[0].totalscore+=result[i].score;
if(result[i].gender==male)
score[0].malescore+=result[i].score;
else
score[0].femalescore+=result[i].score;
break;
case 'B':
score[1].totalscore+=result[i].score;
if(result[i].gender==male)
score[1].malescore+=result[i].score;
else
score[1].femalescore+=result[i].score;
break;
case 'C':
score[2].totalscore+=result[i].score;
if(result[i].gender==male)
score[2].malescore+=result[i].score;
else
score[2].femalescore+=result[i].score;
break;
case 'D':
score[3].totalscore+=result[i].score;
if(result[i].gender==male)
score[3].malescore+=result[i].score;
else
score[3].femalescore+=result[i].score;
break;
case 'E':
score[4].totalscore+=result[i].score;
if(result[i].gender==male)
score[4].malescore+=result[i].score;
else
score[4].femalescore+=result[i].score;
break;
}
i++;
}
int j;
for( j=0;j<5;j++)
{
printf("the school %s: ", result[i].schoolname) ;
printf("total: %f",&score[i].totalscore);
/*输出各院校的男女总分和团体总分*/
3
printf("male: %f",&score[i].malescore);
printf("female: %f",&score[i].femalescore);
}
}
◆1.19④ 试 编 写 算 法 ， 计 算 i!×2^i 的 值 并 存 入 数 组 a[0..ARRSIZE-1] 的 第 i-1 个 分 量 中
(i=1,2,…,n)。假设计算机中允许的整数最大值为 MAXINT，则当 n>ARRSIZE 或对某个
k(1≤k≤n)使 k!×2^k>MAXINT 时，应按出错处理。注意选择你认为较好的出错处理方法。
要求实现下列函数：
Status Series(int ARRSIZE, int a[]);
/* 求 i!*2^i 序列的值并依次存入长度为 ARRSIZE 的数组 a； */
/* 若所有值均不超过 MAXINT，则返回 OK，否则返回 OVERFLOW */
/*当 ARRSIZE<0 时错误*/
Status Series(int ARRSIZE, int a[])
/* 求 i!*2^i 序列的值并依次存入长度为 ARRSIZE 的数组 a； */
/* 若所有值均不超过 MAXINT，则返回 OK，否则返回 OVERFLOW */
{ int last=1;
int i;
if(ARRSIZE<0)
return ERROR;
for(i=1;i<=ARRSIZE;i++)
{
a[i-1]=last*2*i;
if(a[i-1]>MAXINT) /*溢出判断*/
return OVERFLOW;
last=a[i-1];
} return OK;
}
◆1.20④ 试编写算法求一元多项式 P(x) = a0 + a1x + a2x^2 + ... + anx^n 的值 P(x0)，并确定
算法中每一语句的执行次数和整个算法的时间复杂度。注意选择你认为较好的输入和输出方
法。
要求实现下列函数：
float Polynomial(int n, int a[], float x0);
/* 求一元多项式的值 P(x0)。
/* 数组 a 的元素 a[i]为 i 次项的系数，i=0,1,...,n
float Polynomial(int n, int a[], float x)
/* 求一元多项式的值 P(x)。
/* 数组 a 的元素 a[i]为 i 次项的系数，i=0,...,n */
{
/*定义一个数 s，并赋初值 0*/
int i,j;
float s=0;
for(i=0;i<=n;i++)
*/
*/
*/
4
/*循环判断*/
{ float k=1;
if(i==0) k=1;
else
k=1;
for(j=1;j<=i;j++) k=x*k;
s=s+a[i]*k;
}
return s;
}
数据结构习题集 第2章答案
◆2.11② 设顺序表 L 中的数据元素递增有序。试写一算法，将 x 插入到 L 的适当位置上，
并保持该表的有序性。
要求实现下列函数：
void InsertOrderList(SqList &L, ElemType x)
/* 在有序的顺序表 L 中保序插入数据元素 x */
顺序表类型定义如下：
typedef struct {
ElemType *elem;
int length;
int listsize;
} SqList;
voidInsertOrderList(SqList &L, ElemType x)
// 在有序的顺序表 L 中保序插入数据元素 x
{
ElemType *p,*q;
p=L.elem;
while(*p
L.elem=(ElemType *)realloc(L.elem,L.listsize+10);
if(L.elem){
exit(OVERFLOW);
}
L.listsize+=10;
}
for(q=L.elem+L.length-1;q>=p;q--){
*(q+1)=*q;
}
*p=x;
++L.length;
}
◆2.12③ 设 A=(a1,…,am)和 B=(b1,…,bn)均为有序顺序表，A’和 B’分别为 A 和 B 中
除去最大共同前缀后的子表（例如，A=(x,y,y,z,x,z)，B=(x,y,y,z,y,x,x,z)，则两者中最
大的共同前缀为(x,y,y,z)， 在两表中除去最大共同前缀后的子表分别为 A’=(x,z)和
B’=(y,x,x,z)）。若 A’=B’=空表，则 A=B；若 A’=空表，而 B’≠ 空表，或者两者均不为
空表，且 A’的首元小于 B’的首元，则 AB。试写一个比较 A 和 B 大小的算法。（注意：在
算法中，不要破坏原表 A 和 B，也不一定先求得 A’和 B’才进行比较）。
要求实现下列函数：
char Compare(SqList A, SqList B);
/* 比较顺序表 A 和 B, */
/* 返回’<', 若 A
/* '=', 若 A=B; */
/* '>‘, 若 A>B */
顺序表类型定义如下：
typedef struct {
ElemType *elem;
int length;
int listsize;
} SqList;
6
charCompare(SqList A, SqList B)
// 比较顺序表 A 和 B,
// 返回'<', 若 A', 若 A>B
{
chara,b;
intla=1,lb=1;
while(la<=A.length&&lb<=B.length){
if(*(A.elem+la-1)>*(B.elem+lb-1)){return '>';}
elseif(*(A.elem+la-1)<*(B.elem+lb-1)){return '<';}
++la;
++lb;
}
if(A.length==B.length) return '='; //此处应先判断长度是否相等！！
if(la==A.length+1){return '<';}
if(lb==B.length+1){return '>';}
}
2.13② 试写一算法在带头结点的单链表结构上实现线性表操作 Locate(L,x)。
实现下列函数：
LinkList Locate(LinkList L, ElemType x);
// If ‘x’ in the linked list whose head node is pointed
// by ‘L’, then return pointer pointing node ‘x’,
// otherwise return ‘NULL’
单链表类型定义如下：
typedef struct LNode {
ElemType data;
struct LNode *next;
} LNode, *LinkList;
7
LinkList Locate(LinkList &L, ElemType x)
// If 'x' in the linked list whose head node is pointed
// by 'L', then return pointer ha pointing node 'x',
// otherwise return 'NULL'
{
LinkList p=L->next;
while(p){
if(x==p->data){
returnp;
}
p=p->next;
}
returnNULL;
}
2.14② 试写一算法在带头结点的单链表结构上实现线性表操作 Length(L)。
实现下列函数：
int Length(LinkList L);
// Return the length of the linked list
// whose head node is pointed by ‘L’
单链表类型定义如下：
typedef struct LNode{
ElemType data;
struct LNode *next;
} LNode, *LinkList;
intLength(LinkList L)
// Return the length of the linked list
// whose head node is pointed by 'L'
{
inti=0;
LinkList p=L;
8
相关推荐
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
最新资料
2022-2023学年河北省唐山市高三上学期期末数学试题及答案.doc
2022-2023学年河北省张家口市高三上学期期末数学试题及答案.doc
2022-2023学年河北省衡水市高三上学期期末语文试题及答案.doc
2022-2023学年河北省保定市高三上学期期末数学试题及答案.doc
2022-2023学年河北省张家口市高三上学期期末语文试题及答案.doc
2022-2023学年河北省石家庄市高三上学期期末语文试题及答案.doc
2020-2021年四川省凉山州西昌市高一物理上学期期中试卷及答案.doc
2020-2021年四川省遂宁市安居区高一英语上学期期中试卷及答案.doc
2020-2021年四川省西昌市高一英语上学期期中试卷及答案.doc
2021-2022年四川省广安市岳池县高一地理上学期期中试卷及答案.doc
2021-2022年四川省成都市郫都区高一物理上学期期中试卷及答案.doc
2021-2022年四川省广安市岳池县高一物理上学期期中试卷及答案.doc