《数据结构》第一章 绪论

1.1 简述下列术语:数据,数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。

数据:数据是信息的载体,是描述客观事物属性的数、字符以及所有能输入到计算机中并被计算机程序识别和处理的符号的集合。
数据元素:是数据的基本单位,通常作为一个整体进行考虑和处理。一个数据元素可由若干个数据项组成。例如学生记录就是一个数据元素,他由学号、姓名、性别等数据项组成。
数据对象:是具有相同性质的数据元素的集合,是数据的一个子集。
数据结构:是相互之间存在一种或多种特定关系的数据元素的集合。数据结构包括三方面的内容:逻辑结构、存储结构和数据的运算。
存储结构:是数据结构在计算机的表示。
数据类型:数据类型是一个值的集合和定义在此集合上一组操作的总称。
抽象数据类型:是指一个数学模型以及定义在该模型上的一组操作。抽象数据类型的定义仅取决于它的一组逻辑特性,而与其在计算机内部如何表示和实现无关,即不论其内部结构如何变化,只要它的数学特性不变,都不影响其外部的使用。通常用(数据对象、数据关系、基本操作集)这样的三元组来表示抽象数据类型。

1.2 试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。

抽象数据类型包含一般数据类型的概念,但含义比一般数据类型更广、更抽象。一般数据类型由具体语言系统内部定义,直接提供给编程者定义用户数据,因此称它们为预定义数据类型。抽象数据类型通常由编程者定义,包括定义它所使用的数据和在这些数据上所进行的操作。在定义抽象数据类型中的数据部分和操作部分时,要求只定义到数据的逻辑结构和操作说明,不考虑数据的存储结构和操作的具体实现,这样抽象层次更高,更能为其他用户提供良好的使用接口。

1.3 设有数据结构(D,R),其中
     D=\left \{ d1,d2,d3,d4 \right \}, R=\left \{ r \right \}, r=\left \{ \left ( d1,d2 \right ),\left ( d2,d3 \right )\left ( d3,d4 \right ) \right \}
     试按图论中图的画法惯例画出其逻辑结构图。

1.4 试仿照三元组的抽象数据类型分别写出抽象数据类型复数和有理数的定义(有理数是其分子、分母均为自然数且分母不为零的分数)。

//复数
ADT Complex{
    数据对象:D={r,i|r,i为实数}
    数据关系:R={<r,i>}
    基本操作:
        InitComplex(&C,re,im)
            操作结果:构造一个复数C,其实部和虚部分别为re和im
        DestroyCmoplex(&C)
            操作结果:销毁复数C
        Get(C,k,&e)
            操作结果:用e返回复数C的第k元的值
        Put(&C,k,e)
            操作结果:改变复数C的第k元的值为e
        IsAscending(C)
            操作结果:如果复数C的两个元素按升序排列,则返回1,否则返回0
        IsDescending(C)
            操作结果:如果复数C的两个元素按降序排列,则返回1,否则返回0
        Max(C,&e)
            操作结果:用e返回复数C的两个元素中值较大的一个
        Min(C,&e)
            操作结果:用e返回复数C的两个元素中值较小的一个
}ADT Complex
//有理数
ADT RationalNumber{
    数据对象:D={s,m|s,m为自然数,且m不为0}
    数据关系:R={<s,m>}
    基本操作:
        InitRationalNumber(&R,s,m)
            操作结果:构造一个有理数R,其分子和分母分别为s和m
	DestroyRationalNumber(&R)
            操作结果:销毁有理数R
	Get(R,k,&e)
	    操作结果:用e返回有理数R的第k元的值
	Put(&R,k,e)
	    操作结果:改变有理数R的第k元的值为e
	IsAscending(R)
	    操作结果:若有理数R的两个元素按升序排列,则返回1,否则返回0
	IsDescending(R)
	    操作结果:若有理数R的两个元素按降序排列,则返回1,否则返回0
	Max(R,&e)
	    操作结果:用e返回有理数R的两个元素中值较大的一个
	Min(R,&e)
	    操作结果:用e返回有理数R的两个元素中值较小的一个
}ADT RationalNumber

1.5  试画出与下列程序段等价的框图。

(1) product=1; i=1;
     while(i<=n){
        product *= i;
        i++;
    }
(2) i=0;
    do {
        i++;
    } while((i!=n) && (a[i]!=x));
(3) switch {
        case x<y: z=y-x; break;
        case x=y: z=abs(x*y); break;
        default: z=(x-y)/abs(x)*abs(y);
    }

1.6 在程序设计中,常用下列三种不同的出错处理方式:
     (1) 用exit语句终止执行并报告错误;
     (2) 以函数的返回值区别正确返回或错误返回;
     (3) 设置一个整型变量的函数参数以区别正确返回或某种错误返回。
     试讨论这三种方法各自的优缺点。  

(1)在遇到错误时候,强行中断程序的执行,避免产生错误的结果,该种方法无法判断错误的位置和错误的类型。
(2)方法常用于程序的调试,判断局部程序是否正确
(3)方法可以根据返回的数值判断错误的类型,从而迅速排查错误

1.7 在程序设计中,可采用下列三种方法实现输出和输入:
     (1) 通过scanf和printf语句;
     (2) 通过函数的参数显式传递;
     (3) 通过全局变量隐式传递。
     试讨论这三种方法的优缺点。

(1)方法可以简单直观的输入输出变量,但同时需要控制格式。
(2)方法较容易控制输入输出,不易使程序出错
(3)方法可以方便变量的修改,但如果变量设置的过多,会导致程序难以维护

1.8 设n为正整数。试确定下列各程序段中前置以记号@的语句的频度:

(1) i=1; k=0;
    while(i<=n-1){
        @  k += 10*i;
           i++;
    }

频度:n-1

(2) i=1; k=0;
    do {
        @  k += 10*i;
           i++;
    } while(i<=n-1);

频度:n-1

(3) i=1; k=0;
    while (i<=n-1) {
              i++;
        @ k += 10*i;
    }

频度:n-1

(4) k=0;
    for(i=1; i<=n; i++) {
        for(j=i; j<=n; j++)
            @  k++;
    }

频度:\frac{n\left ( n+1 \right )}{2}=n+(n-1)+\cdots+1

(5)  for(i=1; i<=n; i++) {
        for(j=1; j<=i; j++) {
            for(k=1; k<=j; k++)
                @  x += delta;
    }

频度: \sum_{i=1}^{n}\frac{i(i+1)}{2}=1+\left ( 1+2 \right )+\cdots +\left ( 1+2+\cdots +n \right )

(6) i=1; j=0;
    while(i+j<=n) {
            @  if(i>j) j++;
           else i++;
    }

频度: n

(7) x=n; y=0;     // n是不小于1的常数
    while(x>=(y+1)*(y+1)) {
        @  y++;
    }

频度:\left \lfloor \sqrt{n} \right \rfloor

(8) x=91; y=100;
    while(y>0) {
        @  if(x>100) { x -= 10; y--; }
           else x++;
    }

频度:1100

1.9 假设n为2的乘幂,并且n>2,试求下列算法的时间复杂度及变量count的值(以n的函数形式表示)。

int Time(int n) {
       count = 0;
	x=2;
       while(x<n/2) {
	    x *= 2;	
            count++;
        }
        return count;
}

时间复杂度为:O\left ( log_{2}n \right )
count=log_{2}n-2

1.10 按增长率由小至大的顺序排序下列函数
2^{100}, \left ( 3/2 \right )^{n}, \left ( 2/3 \right )^{n}, \left ( 4/3 \right )^{n}, n^{n}, n^{3/2},n^{2/3}, \sqrt{n}, n!, n, log_{2}n, n/log_{2}n, log_{2}^{3}n, log_{2}\left ( log_{2}n \right ), nlog_{2}n, n^{log_{2}n}

2^{100}, , log_{2}\left ( log_{2}n \right )n , log_{2}^{3}n , log_{2}n , \left ( 2/3 \right )^{n} , nlog_{2}n, n/log_{2}n , \sqrt{n}n^{2/3}n^{3/2}, n, n!, , \left ( 4/3 \right )^{n}\left ( 3/2 \right )^{n} ,  n^{log_{2}n} ,n^{n}

1.11 已知有实现同一功能的两个算法,其时间复杂度分别为O\left ( 2^{n} \right )O\left ( n^{10} \right ),假设现实计算机可连续运算的时间为 秒(100多天),又每秒可执行基本操作(根据这些操作来估算算法时间复杂度) 次。试问在此条件下,这两个算法可解问题的规模(即n值的范围)各为多少?哪个算法更适宜?请说明理由。

2^{n_{1}}=(n_{2})^{10}=10^{12}, n_{1}=40, n_{2}=16
若n相同,第二种的算法代价要比第一种大很多,所以,在该规模下,第一种较便宜

1.12 设有以下三个函数:
      f\left ( n \right )=2ln^{4}+n^{2}+1000, g\left ( n \right )=15ln^{4}+500n^{3}, h\left ( n \right )=500n^{3.5}+nlogn
       请判断以下断言正确与否:
      (1) f(n)是O(g(n))
      (2) h(n)是O(f(n))
      (3) g(n)是O(h(n))
      (4) h(n)是O(n3.5)
      (5) h(n)是O(nlogn)

(1)正确,(2)错误,(3)错误,(4)正确,(5)错误

1.13 试设定若干n值,比较两函数n^{2}50nlog_{2}n的增长趋势,并确定n在什么范围内,函数n^{2}的值大于50nlog_{2}n的值

n^{2}的增长趋势较快,当n>450时,n^{2}>50nlog_{2}n,否则,50nlog_{2}n的值较大

1.14 判断下列各对函数f(n)和g(n),当n \to \infty时,哪个函数增长更快?
       (1). f\left ( n \right )=10n^{2}+ln\left ( n!+10^{n^{3}} \right ), g\left ( n \right )=2n^{4}+n+7

      f\left ( n \right )增长较快
       (2). f\left ( n \right )=\left ( ln\left ( n! \right )+5 \right )^{2}, g\left ( n \right )=13n^{2.5}

      f\left ( n \right )增长较快
       (3). f\left ( n \right )=n^{2.1}+\sqrt{n^{4}+1}, g\left ( n \right )=\left ( ln\left ( n! \right ) \right )^{2}+n

      g\left ( n \right )增长较快
       (4). f\left ( n \right )=2^{\left ( n^{3} \right )}+\left ( 2^{n} \right )^{2}, g\left ( n \right )=n^{\left ( n^{2} \right )}+n^{5}

      g\left ( n \right )增长较快

1.15 试用数学归纳法证明:
       (1) \sum_{i=1}^{n}i^{2}=n(n+1)(2n+1)/6 (n\geqslant 0)
       (2) \sum_{i=0}^{n}x^{i}=\left ( x^{n+1}-1 \right )/\left ( x-1 \right ) \left ( x\neq 1,n\geqslant 0 \right )
       (3) \sum_{i=1}^{n}2^{i-1}=2^{n}-1 \left ( n\geqslant 1 \right )
       (4) \sum_{i=1}^{n}\left ( 2i-1 \right )=n^{2} \left ( n\geq 1 \right )

1.16 试写一算法,自大至小依次输出顺序读入的三个整数X,Y和Z的值

#include <iostream>
using namespace std;
int main(){
	int x,y,z;
	cin>>x>>y>>z;
	if(x>y){
		if(x>z)
			if(y>z)
				cout<<x<<" "<<y<<" "<<z<<endl;
			else
				cout<<x<<" "<<z<<" "<<y<<endl;
		else
			cout<<z<<" "<<x<<" "<<y<<endl;
	}else{
		if(y>z)
			if(x>z)
				cout<<y<<" "<<x<<" "<<z<<endl;
			else
				cout<<y<<" "<<z<<" "<<x<<endl;
		else
			cout<<z<<" "<<y<<" "<<x<<endl;

	}
}

1.17 已知k阶斐波那契序列的定义为
           f_{0}=0,f_{1}=0,\cdots ,f_{k-2}=0,f_{k-1}=1;
          f_{n}=f_{n-1}+f_{n-2}+\cdots +f_{n-k},n=k,k+1,\cdots
        试编写求k阶斐波那契序列的第m项值的函数算法,k和m均以值调用的形式在函数参数表中出现。

#include <iostream>
using namespace std;
int fibonacci(int k,int m)
{
	if(m<0)
		exit(0);
	if(m>=0&&m<k-1)
		return 0;
	if(m==k-1)
		return 1;
	int x,*p;
	p=new int[k+1];
	int i,j;
	for(i=0;i<k+1;i++){
		if(i<k-1) p[i]=0;
		else p[i]=1;
	}
	for(i=k+1;i<m+1;i++){
		x=p[0];
		for(j=0;j<k;j++) 
			p[j]=p[j+1];
		p[k]=2*p[k-1]-x;
	}
	return p[k];
}

int main(){
	int a,b,c;
	cin>>a>>b;
	c=fibonacci(a,b);
	cout<<c;
	
	return 0;
}

1.18 假设有A,B,C,D,E五个高等院校进行田径对抗赛,各院校的单项成绩均已存入计算机,并构成一张表,表中每一行的形式为
        项目名称,性别,校名,成绩,得分
       编写算法,处理上述表格,以统计各院校的男、女总分和团体总分,并输出。

#include <iostream>
using namespace std;
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<n;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;
}
int main(){
	Component com[5];

	strcpy(com[1].event,"pro");
	com[1].school=A;
	com[1].score=90;
	com[1].sex=Female;

	strcpy(com[2].event,"pro");
	com[2].school=A;
	com[2].score=91;
	com[2].sex=Male;

	strcpy(com[3].event,"pro");
	com[3].school=A;
	com[3].score=92;
	com[3].sex=Male;

	strcpy(com[4].event,"pro");
	com[4].school=A;
	com[4].score=93;
	com[4].sex=Female;

	strcpy(com[5].event,"pro");
	com[5].school=A;
	com[5].score=94;
	com[5].sex=Male;

	Sum num=SumScore(A,com,5);

	cout<<num.FemaleSum<<" "<<num.MaleSum<<" "<<num.TotalSum<<endl;

	return 0;
}

1.19 试编写算法,计算i!*2^{i}的值并存入数组a[0..arrsize-1]的第i-1个分量中(i=1,2,\ldots{},n)。假设计算机中允许的整数最大值为maxint,则当n>arrsize或对某个k\left ( 1\leq k\leq n \right ),使k!*2^{k}>maxint时,应按出错处理。注意选择你认为较好的出错处理方法。

#include<iostream>
#include<stdlib.h>
using namespace std;
#define MAXINT 65535
#define ArrSize 100
int fun(int i);

int main()
{
	int i,k;
	int a[ArrSize];
	cout<<"请输入k:";
	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<<a[i]<<" ";
	}

	return 0;
}

1.20 试编写算法求一元多项式的值P_{x}=\sum_{i=0}^{n}a_{i}x^{i}的值,P_{n}\left ( x_{0} \right ),并确定算法中每一语句的执行次数和整个算法的时间复杂度。注意选择你认为较好的输入和输出方法。本题的输入为a_{i}\left ( i=0,1,\cdots ,n \right ),x_{0}和n,,输出为P_{n}\left ( x_{0} \right )

#include<iostream>
#include<stdlib.h>
using namespace std;
#define N  10
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];
}
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<<"The polynomail value is "<<polynomail(a,n,x,n)<<endl;
	return 0;
}