数据结构题集（C语言版）答案 - 严蔚敏编著

1.18 假设有A B C D

E五个高等院校进行田径对抗赛 各院校的单项成绩均已存入计算机 并构成一张表

表中每一行的形式为 项目名称 性别 校名 成绩 得分 编写算法 处理上述表格

以统计各院校的男、女总分和团体总分 并输出

解：

typedef enum{A B C D

E} SchoolName;

typedef enum{Female Male} SexType; typedef struct{

char event[3]; //项目 SexType sex;

SchoolName school; int score; } Component; typedef struct{

int MaleSum; //男团总分 int FemaleSum; //女团总分 int TotalSum; //团体总分 } Sum;

Sum SumScore(SchoolName sn Component a[] int n) {

Sum temp;

temp.MaleSum=0; temp.FemaleSum=0;

temp.TotalSum=0; int i;

for(i=0;i

if(a[i].school==sn){

if(a[i].sex==Male) temp.MaleSum+=a[i].score; if(a[i].sex==Female) temp.FemaleSum+=a[i].score; } }

temp.TotalSum=temp.MaleSum+temp.FemaleSum; return temp; }

1.19 试编写算法

计算的值并存入数组a[0..arrsize-1]的第i-1个分量中(i=1 2 ... n)

假设计算机中允许的整数最大值为maxint 则当n>arrsize或对某个 使时

应按出错处理

注意选择你认为较好的出错处理方法

解：

#include #include #define MAXINT 65535 #define ArrSize 100 int fun(int i);

int main() {

int i k;

int a[ArrSize]; cout<<\ cin>>k;

if(k>ArrSize-1) exit(0); for(i=0;i<=k;i++){ if(i==0) a[i]=1; else{

if(2*i*a[i-1]>MAXINT) exit(0); else a[i]=2*i*a[i-1]; } }

for(i=0;i<=k;i++){

if(a[i]>MAXINT) exit(0); else cout<

return 0; }

1.20 试编写算法求一元多项式的值的值

并确定算法中每一语句的执行次数和整个算法的时间复杂度 注意选择你认为较好的输入和输出方法 本题的输入为 和 输出为

解：

#include #include #define N 10

double polynomail(int a[] int i double x int n); int main() {

double x; int n i;

int a[N];

cout<<\输入变量的值x:\ cin>>x;

cout<<\输入多项式的阶次n:\ cin>>n;

if(n>N-1) exit(0);

cout<<\输入多项式的系数a[0]--a[n]:\ for(i=0;i<=n;i++) cin>>a[i];

cout<<\n x

n)<

double polynomail(int a[] int i double x int n)

{

if(i>0) return a[n-i]+polynomail(a i-1 x n)*x;

else return a[n]; }

本算法的时间复杂度为o(n)

第2章 线性表

2.1 描述以下三个概念的区别：头指针 头结点

首元结点（第一个元素结点）

解：头指针是指向链表中第一个结点的指针 首元结点是指链表中存储第一个数据元素的结点 头结点是在首元结点之前附设的一个结点 该结点不存储数据元素 其指针域指向首元结点

其作用主要是为了方便对链表的操作

它可以对空表、非空表以及首元结点的操作进行统一处理

2.2 填空题

解：(1) 在顺序表中插入或删除一个元素 需要平均移动表中一半元素

具体移动的元素个数与元素在表中的位置有关

(2) 顺序表中逻辑上相邻的元素的物理位置必定紧邻 单链表中逻辑上相邻的元素的物理位置不一定紧邻

(3) 在单链表中 除了首元结点外

任一结点的存储位置由其前驱结点的链域的值指示

(4) 在单链表中设置头结点的作用是插入和删除首元结点时不用进行特殊处理

2.3 在什么情况下用顺序表比链表好？

解：当线性表的数据元素在物理位置上是连续存储的时候 用顺序表比用链表好

其特点是可以进行随机存取

2.4 对以下单链表分别执行下列各程序段 并画出结果示意图