Geekerstar

《数据结构题集(C语言版)》习题解析(一)绪论
基础知识题1.1 简述下列术语:数据,数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。解:数据是对...
扫描右侧二维码阅读全文
10
2018/03

《数据结构题集(C语言版)》习题解析(一)绪论

基础知识题

1.1 简述下列术语:数据,数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。
解:
数据是对客观事物的符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。
数据元素是数据的基本单位,在计算机程序中通常作为一个整体进行考虑和处理。
数据对象是性质相同的数据元素的集合,是数据的一个子集。
数据结构是相互之间存在一种或多种特定关系的数据元素的集合。
存储结构是数据结构在计算机中的表示。
数据类型是一个值的集合和定义在这个值集上的一组操作的总称。
抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。是对一般数据类型的扩展。

1.2 试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。
解:
简单的说,数据结构定义了一组按某些关系结合在一起的数组元素,数据类型不仅定义了一组带结构的数据元素,而且还在其上定义了一组操作
参考答案:
抽象数据类型包含一般数据类型的概念,但含义比一般数据类型更广、更抽象。一般数据类型由具体语言系统内部定义,直接提供给编程者定义用户数据,因此称它们为预定义数据类型。抽象数据类型通常由编程者定义,包括定义它所使用的数据和在这些数据上所进行的操作。在定义抽象数据类型中的数据部分和操作部分时,要求只定义到数据的逻辑结构和操作说明,不考虑数据的存储结构和操作的具体实现,这样抽象层次更高,更能为其他用户提供良好的使用接口。

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

1.3

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

ADT Complex        //复数定义 a±bi
    {
        数据对象:D = {a, b | a,b为实数}
        数据关系:R = {<a, b>}
        基本操作:
            InitComplex(&C, re, im)
                操作结果:构造一个复数C,其实部和虚部分别为re和im
            DestroyCmoplex(&C)
                操作结果:销毁复数C
            Get(C, k, &e)
                初始条件:复数C已存在
                操作结果:用e返回复数C的第k元的值
            Put(&C, k, e)
                初始条件:复数C已存在
                操作结果:改变复数C的第k元的值为e
            IsAscending(C)
                初始条件:复数C已存在
                操作结果:如果复数C的两个元素按升序排列,则返回1,否则返回0
            IsDescending(C)
                初始条件:复数C已存在
                操作结果:如果复数C的两个元素按降序排列,则返回1,否则返回0
            Max(C, &e)
                初始条件:复数C已存在
                操作结果:用e返回复数C的两个元素中值较大的一个
            Min(C, &e)
                初始条件:复数C已存在
                操作结果:用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)
                初始条件:有理数R已存在
                操作结果:用e返回有理数R的第k元的值
            Put(&R, k, e)
                初始条件:有理数R已存在
                操作结果:改变有理数R的第k元的值为e
            IsAscending(R)
                初始条件:有理数R已存在
                操作结果:若有理数R的两个元素按升序排列,则返回1,否则返回0
            IsDescending(R)
                初始条件:有理数R已存在
                操作结果:若有理数R的两个元素按降序排列,则返回1,否则返回0
            Max(R, &e)
                初始条件:有理数R已存在
                操作结果:用e返回有理数R的两个元素中值较大的一个
            Min(R, &e)
                初始条件:有理数R已存在
                操作结果:用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.5

`1.6 在程序设计中,常用下列三种不同的出错处理方式:
(1)用exit语句终止执行并报告错误;
(2)以函数的返回值区别正确返回或错误返回;
(3)设置一个整型变量的函数参数以区别正确返回或某种错误返回。
试讨论这三种方法各自的优缺点。
解:
(1)exit常用于异常错误处理,它可以强行中断程序的执行,返回操作系统。
(2)以函数的返回值判断正确与否常用于子程序的测试,便于实现程序的局部控制。
(3)用整型函数进行错误处理的优点是可以给出错误类型,便于迅速确定错误。

1.7 在程序设计中,可采用下列三种方法实现输出和输入:
(1)通过scanf和printf语句;
(2)通过函数的参数显式传递;
(3)通过全局变量隐式传递。
试讨论这三种方法的优缺点。
解:
(1)用scanf和printf直接进行输入输出的好处是形象、直观,但缺点是需要对其进行格式控制,较为烦琐,如果出现错误,则会引起整个系统的崩溃。
(2)通过函数的参数传递进行输入输出,便于实现信息的隐蔽,减少出错的可能。
(3)通过全局变量的隐式传递进行输入输出最为方便,只需修改变量的值即可,但过多的全局变量使程序的维护较为困难。

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

(1) i=1; k=0;
    while(i<=n-1){
        @  k += 10*i;
           i++;
    }
(2) i=1; k=0;
    do {
        @  k += 10*i;
           i++;
    } while(i<=n-1);
(3) i=1; k=0;
    while (i<=n-1) {
              i++;
        @ k += 10*i;
    }
(4) k=0;
    for(i=1; i<=n; i++) {
        for(j=i; j<=n; j++)
            @  k++;
    }
(5) for(i=1; i<=n; i++) {
        for(j=1; j<=i; j++) {
            for(k=1; k<=j; k++)
                @  x += delta;
    }
(6) i=1; j=0;
    while(i+j<=n) {
            @  if(i>j) j++;
           else i++;
    }
(7) x=n; y=0;     // n是不小于1的常数
    while(x>=(y+1)*(y+1)) {
        @  y++;
    }
(8) x=91; y=100;
    while(y>0) {
        @  if(x>100) { x -= 10; y--; }
           else x++;
    }

解:

1.8

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;
    }

解:
15.jpg

1.10 按增长率由小至大的顺序排列下列各函数
1.10

解:

17.jpg

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

16.jpg

1.12 设有以下三个函数:

1.12
解:
(1)对
(2)错
(3)错
(4)对
(5)错

1.13

1.14 判断下列各对函数f(n)和g(n) ,当n--> ∞时,哪个函数增长更快?

1.14

解:
(1)g(n)快
(2)g(n)快
(3)f(n)快
(4)f(n)快

1.15 试用数学归纳法证明:
解:
1.15
22.jpg
23.jpg

算法设计题

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

#include <stdio.h>

/* 函数原型 */
void Algo_1_16(int i, int j, int k);

int main(int argc, char *argv[])
{
    int i, j, k;
    
    i = 3;
    j = 7;
    k = 1;
    
    printf("作为示范,设定依次读入的三个整数为:%d %d %d...\n", i, j, k);
    printf("这三个数从大到小的顺序为:");
    
    Algo_1_16(i, j, k);
    printf("\n");
    
    return 0;
}

/*
题1.16:将3个整数按从大到小顺序输出 
*/
void Algo_1_16(int i, int j, int k)
{
    int tmp;
    
    if(i<j)
    {
        tmp = i;
        i = j;
        j = tmp;
    }
    
    if(j<k)
    {
        tmp = j;
        j = k;
        k = tmp;    
    }
    
    if(i<j)
    {
        tmp = i;
        i = j;
        j = tmp;
    }    
    
    printf("%d %d %d\n", i, j, k);
}

1.17 已知k阶斐波那契序列的定义为
1.17
试编写求k阶斐波那契序列的第m项值的函数算法,k和m均以值调用的形式在函数参数表中出现。
解:
k>0为阶数,n为数列的第n项

#include <stdio.h>
#include <stdlib.h>                                            //提供malloc、realloc、free、exit原型
#include <Status.h>

/* 函数原型 */
int Algo_1_17_1(int k, int m);
int Algo_1_17_2(int k, int m);

int main(int argc, char *argv[])
{
    int k, m;
    
    k = 3;
    m = 10;
    
    printf("作为示范,求得 %d 阶斐波那契数列第 %d 项的值为:%d \n", k, m, Algo_1_17_1(k, m));
    
    printf("作为示范,求得 %d 阶斐波那契数列第 %u 项的值为:%d \n", k, 2*m, Algo_1_17_2(k, 2*m));
    
    printf("\n");
    
    return 0;
}

/*
题1.17:计算k阶斐波那契数列第m项的值
*/
/* 方法1:递归算法 */
int Algo_1_17_1(int k, int m)            //当m变大时,计算速度会递减 
{
    int i, value;
    
    if(k<2 || m<0)
        exit(OVERFLOW);
    
    if(m<k-1)
        return 0;
    else if(m==k-1)
        return 1;
    else
    {
        for(i=1,value=0; i<=k; i++)
            value += Algo_1_17_1(k, m-i);
        
        return value;
    }
}

/*
题1.17:计算k阶斐波那契数列第m项的值
*/
/* 方法2:递推(迭代)算法 */
int Algo_1_17_2(int k, int m)
{
    int i, j;
    int fib[m+1];
    
    if(k<1 || m<0)
        exit(OVERFLOW);
    
    i = 0;
    while(i<k-1)
    {
        fib[i] = 0;
        i++;        
    }
        
    fib[i] = 1;                            //i = k-1
    i++;
            
    while(i<=m)                            //i = k
    {    
        for(j=i-1,fib[i]=0; j>=i-k; j--)
            fib[i] += fib[j];
        i++;
    }
    
    return fib[m];
}

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

typedef enum {A, B, C, D, E} SchoolName;
typedef enum {FEMALE, MALE} SexType;
typedef enum {X, Y, Z} Event; 
typedef struct
{
    Event e;            //项目名称 
    SexType sex;        //性别 
    SchoolName school;//校名 
    int score;            //得分 
}Component;

typedef struct
{
    int malesum;        //男团总分
    int femalesum;    //女团总分
    int totalsum;        //团体总分
}Sum;

Component    report[n];    //n条记录 
Sum            result[5];

    //算法过程体中主要结构 
    for(i=0; i<n; i++)
    {
        //对result[report[i].school]进行处理 
    }
    
    for(s=A; s<=E; s++)
    {
        //printf(...);
    }

1.19 试编写算法
1.19

解:

#include <stdio.h>
#include <limits.h>                                            //提供宏INT_MAX 
#include <Status.h>

/* 宏定义 */
#define arrsize 20                                            //数组长度 
#define maxint INT_MAX                                        //最大的整数 

/* 函数原型 */
Status Algo_1_19(int i, int a[]);

int main(int argc, char *argv[])
{
    int i, a[arrsize];
    
    i = 5;
    
    printf("计算i!*2^i...\n");
    
    if(Algo_1_19(i, a)==OK)
        printf("作为示例,计算当i = %d 时,a[i-1] = %d\n", i, a[i-1]);
    printf("\n");
    
    return 0;
}
 
/*
题1.19:计算i!*2^i存入a[i-1],i起点为1
*/
Status Algo_1_19(int i, int a[])
{
    int j;
    
    if(i<1 || i>arrsize)
        return ERROR;
    
    for(j=1; j<=i; j++)
    {
        if(j==1)
            a[j-1] = 2;
        else
        {
            if(maxint/(2*j)<a[j-2])
                return OVERFLOW;
                
            a[j-1] = 2 * j * a[j-2];        
        }    
    }
    
    return OK;
}

1.20 试编写算法
1.29

解:

#include <stdio.h>
#include <math.h>                        //提供pow原型 

/* 函数原型 */
int Algo_1_20(int a[], int x, int n);

int main(int argc, char *argv[])
{
    int a[5] = {-2, 3, 6,-8, 7};
    int n = 5;
    int Xo = 3;
    
    printf("作为示范,设定项数n = 5,变量Xo = 3,计算Pn(Xo)...\n");
    printf("P%d(%d) = %d\n", n, Xo, Algo_1_20(a, Xo, n));
    printf("\n");

    return 0;
}

/*
题1.20:计算多项式Pn(Xo)的值
*/
int Algo_1_20(int a[], int x, int n)
{
    int i;
    int tmp;
    
    for(i=1,tmp=0; i<=n; i++)
        tmp += a[i-1]*pow(x, i-1);
    
    return tmp;
}

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

说明

本系列笔记为本人总结或整理,另外参考了网络上的一些资料并在显要位置注明了作者或来源。整理过程中难免有所疏漏,如有错误,欢迎指出!


如果您发现了文章有任何错误欢迎指正,有任何意见或建议,或者有疑问需要我提供帮助,也欢迎在下面留言,只需输入昵称+邮箱即可,网站或博客可选填。对于所有留言内容我会及时回复,非常期待与大家的交流![/scode]

版权声明:本文(除特殊标注外)为原创文章,版权归 Geekerstar 所有。

本文链接:http://www.geekerstar.com/technology/404.html

除了有特殊标注文章外欢迎转载,但请务必标明出处,格式如上,谢谢合作。

最后修改:2018 年 03 月 10 日 05 : 35 PM
如果觉得我的文章对你有用,请随意赞赏

发表评论