数据结构习题练习(一)-绪论

数据结构习题练习目录
参考:数据结构实验与习题

答案是参考书给的,有疑问我的我会备注一下。
分析都是个人观点,但都是我确定的,
不过有些可能会因为我头发长见识短不知道的,麻烦评论提醒一下。

排版很挤,但我写的时候有空行,WordPress不显示没办法,
先用斜体区分一下,我后面想办法处理。
加上句号来占位换行了。

选择题

  1. 数据结构是一门研究非数值计算的程序设计问题中计算机的①以及它们之间的②和运算等的学科。
    ① A.操作对象 B.计算方法 C.逻辑存储 D.数据映象
    ② A.结构 B.关系 C.运算 D.算法
  2. 数据结构被形式地定义为(K,R),其中 K 是①的有限集合,R 是 K 上的②有限集合。
    ① A.算法 B.数据元素 C.数据操作 D.逻辑结构
    ② A.操作 B.映象 C.存储 D.关系
  3. 在数据结构中,从逻辑上可以把数据结构分成①。
    A.动态结构和静态结构 B.紧凑结构和非紧凑结构
    C.线性结构和非线性结构 D.内部结构和外部结构
  4. 线性表的顺序存储结构是一种①的存储结构,线性表的链式存储结构是一种②的存储结构。
    A.随机存取 B.顺序存取 C.索引存取 D.散列存取
  5. 算法分析的目的是①,算法分析的两个主要方面是②。
    ① A. 找出数据结构的合理性 B. 研究算法中的输入和输出的关系
    C. 分析算法的效率以求改进 D. 分析算法的易懂性和文档性
    ② A. 空间复杂性和时间复杂性 B. 正确性和简明性
    C. 可读性和文档性 D. 数据复杂性和程序复杂性
  6. 计算机算法指的是①,它必具备输入、输出和②等五个特性。
    ① A. 计算方法 B. 排序方法
    C. 解决问题的有限运算序列 D. 调度方法
    ② A. 可行性、可移植性和可扩充性 B. 可行性、确定性和有穷性
    C. 确定性、有穷性和稳定性 D. 易读性、稳定性和安全性
  7. 线性表的逻辑顺序与存储顺序总是一致的,这种说法①。
    A. 正确 B. 不正确
  8. 线性表若采用链式存储结构时,要求内存中可用存储单元的地址①。
    A. 必须是连续的 B. 部分地址必须是连续的
    C. 一定是不连续的 D. 连续或不连续都可以
  9. 在以下的叙述中,正确的是①。
    A. 线性表的线性存储结构优于链表存储结构
    B. 二维数组是其数据元素为线性表的线性表
    C. 栈的操作方式是先进先出
    D. 队列的操作方式和先进后出
  10. 每种数据结构都具备三个基本运算:插入、删除和查找,这种说法①。
    A. 正确 B. 不正确

填空题

  1. 数据逻辑结构包括①、②和③三种类型,树形结构和图形结构合称为④。
  2. 在线性结构中,第一个结点①前驱结点,其余每个结点有且只有②个前驱结点;最后一个结点③后续结点,其余每个结点有且只有④个后续结点。
  3. 在树形结构中,树根结点没有①结点,其余每个结点有且只有②个前驱结点,叶子结点没有③结点,其余每个结点的后续结点可以④。
  4. 在图形结构中,每个结点的前驱结点数和后续结点数可以①。
  5. 线性结构中元素之间存在①关系,树形结构中元素之间存在②关系,图形结构中元素
    之间存在③关系。
  6. 算法的五个重要特性是_ ___
  7. 下面程序段的时间复杂度是①。
    for (i=0;i<n;i++)
    for (j=0;j<m;j++)
    A[i][j]=0;
  8. 下面程序段的时间复杂度是①。
    i=s=0;
    while (s<n)
    { i++; /i=i+1/
    s+=i; /s=s+1/
    }
  9. 下面程序段的时间复杂度是①。
    s=0;
    for (i=0;i<n;i++)
    for (j=0;j<n;j++)
    s+=B[i][j];
    sum=s;
  10. 下面程序段的时间复杂度是①。
    i=1;
    while (i<=n)
    i=i*3;

程序设计题

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

选择题分析

  1. 数据结构是一门研究非数值计算的程序设计问题中计算机的①以及它们之间的②和运算等的学科。
    A.操作对象 B.计算方法 C.逻辑存储 D.数据映象
    ② A.结构 B.关系 C.运算 D.算法
    这题属于死记硬背的东西,我也想不出解释的东西。
    .
  2. 数据结构被形式地定义为(K,R),其中 K 是①的有限集合,R 是 K 上的②有限集合。
    ① A.算法 B.数据元素 C.数据操作 D.逻辑结构
    ② A.操作 B.映象 C.存储 D.关系
    同上,记下来吧*2。
    .
  3. 在数据结构中,从逻辑上可以把数据结构分成①。
    A.动态结构和静态结构 B.紧凑结构和非紧凑结构
    C.线性结构和非线性结构 D.内部结构和外部结构
    同上,记下来吧*3。
    线性结构大概就是各结点最多只有一个直接前驱和直接后继,
    非线性结构当然就是想多少前驱后继就多少咯。

    .
  4. 线性表的顺序存储结构是一种①的存储结构,线性表的链式存储结构是一种②的存储结构。
    A.随机存取 B.顺序存取 C.索引存取 D.散列存取
    答案为AB
    随机存取表示能直接存取某位置的元素,大概就是知道了数组名,就能直接存取任一位置数据,
    顺序存取跟它相反,像线性链表,知道头结点后还需要一个个读取才能找到特定位置。
    线性表的顺序存储结构就是数组,链式存储结构就是线性链表。

    .
  5. 算法分析的目的是①,算法分析的两个主要方面是②。
    ① A. 找出数据结构的合理性 B. 研究算法中的输入和输出的关系
    C. 分析算法的效率以求改进 D. 分析算法的易懂性和文档性
    A. 空间复杂性和时间复杂性 B. 正确性和简明性
    C. 可读性和文档性 D. 数据复杂性和程序复杂性
    首先可以肯定的是,算法两个重要特征就是空间复杂度和时间复杂度,所以2大概率是A,
    那么由2推1,就是要改进效率了。

    .
  6. 计算机算法指的是①,它必具备输入、输出和②等五个特性。
    ① A. 计算方法 B. 排序方法
    C. 解决问题的有限运算序列 D. 调度方法
    ② A. 可行性、可移植性和可扩充性 B. 可行性、确定性和有穷性
    C. 确定性、有穷性和稳定性 D. 易读性、稳定性和安全性
    这个题也是死记硬背的内容,
    不过也很好记,每个特性的意义看一下,就能记下来了,
    目的都是维护算法正确性的。

    .
  7. 线性表的逻辑顺序与存储顺序总是一致的,这种说法①。
    A. 正确 B. 不正确
    线性表的数组存储,逻辑和存储顺序是一样的,因为数组存储在一段连续的内存空间中,
    但链表存储,存储顺序就不连续了,内存里面到处都是。

    .
  8. 线性表若采用链式存储结构时,要求内存中可用存储单元的地址①。
    A. 必须是连续的 B. 部分地址必须是连续的
    C. 一定是不连续的 D. 连续或不连续都可以
    链式存储对地址没有要求,只要有地址就行了,要是就两个结点,多存储几次,总能碰到连续的是吧。
    .
  9. 在以下的叙述中,正确的是①。
    A. 线性表的线性存储结构优于链表存储结构
    B. 二维数组是其数据元素为线性表的线性表
    C. 栈的操作方式是先进先出
    D. 队列的操作方式和先进后出
    数组是线性表,那么一维数组和二维数组都是线性表,
    二维数组里面每个元素都是一维数组,
    那么二维数组就是线性表的线性表了。

    .
  10. 每种数据结构都具备三个基本运算:插入、删除和查找,这种说法①。
    A. 正确 B. 不正确
    例如C语言的二维数组,行列长度都是相等的,不能插入删除某个位置。

填空题分析

  1. 数据逻辑结构包括①线性结构、②树形结构和③图形结构三种类型,树形结构和图形结构合称为④非线性结构
    线性结构前面讲过了,就是前驱后继最多一个,
    树形结构就是前驱最多一个,后继随便,
    图形结构就是前驱随便,后继也随便,
    大概也是死记硬背的题目吧。

    .
  2. 在线性结构中,第一个结点①没有 前驱结点,其余每个结点有且只有②一 个前驱结点;最后一个结点③没有 后续结点,其余每个结点有且只有④一 个后续结点。
    送分题,只要随便找一个线性结构举例就行了,像链表,栈,队列都是。
    .
  3. 在树形结构中,树根结点没有①前驱结点,其余每个结点有且只有②一个前驱结点,叶子结点没有③后继结点,其余每个结点的后续结点可以④任意多个
    这题得扣字眼,题中有前驱和后续(我更习惯后继)的字眼,
    那么1就填前驱,3就后继,
    2 4就是把树拿出来看看就明白了。
    我觉得难点在4,看了答案我才明白它说的还是数量,不过这也能根据前文推出。

    .
  4. 在图形结构中,每个结点的前驱结点数和后续结点数可以①任意多个
    把图拿出来看看就明白了,
    这题有说结点,比上题更亲民一点。
    .
  5. 线性结构中元素之间存在①一对一关系,树形结构中元素之间存在②一对多关系,图形结构中元素之间存在③多对多关系。
    我讨厌这种题目,我还以为是前后、父子、平等这种关系,可恶。
    就是三种结构的定义。

    .
  6. 算法的五个重要特性是输入、输出、确定性、有穷性、可行性
    这是死记硬背的地方了,我最讨厌的就是这种。
    .
  7. 下面程序段的时间复杂度是①O(n*m)
    for (i=0;i<n;i++)
    for (j=0;j<m;j++)
    A[i][j]=0;
    这是两层循环,还是定长循环,里面的赋值语句时间复杂度为O(1),因此就是两层的乘积。
    .
  8. 下面程序段的时间复杂度是①O(n1/2)
    i=s=0;
    while (s<n)
    { i++; /i=i+1/
    s+=i; /s=s+1/
    }
    题目错了,s+=i与s=s+1不等效,应该是注释错了。
    这题我也不清楚,我还以为是O(n)。

    .
  9. 下面程序段的时间复杂度是①O(n2)
    s=0;
    for (i=0;i<n;i++)
    for (j=0;j<n;j++)
    s+=B[i][j];
    sum=s;
    和第7题一样。
    .
  10. 下面程序段的时间复杂度是①O(log3n)
    i=1;
    while (i<=n)
    i=i*3;
    就是i3 = n,那么i = log3n,是个数学问题。

程序设计题分析

  1. 试写一算法,自大到小依次输出顺序读入的三个数 X,Y 和 Z 的值.
    本来想写点厉害的,脑子好像有点空,写出来除了难看懂没有特别的,就无脑输出了。
// 三个数以三个参数的形式传入函数
void printOrder(int x, int y, int z){
  if(x<=y && x<=z){
    if(y > z)
      printf("%d, %d, %d", y, z, x);
    else
      printf("%d, %d, %d", z, y, x);
  }
  else if(x<=y && x>=z)
    printf("%d, %d, %d", y, x, z);
  else if(x>=y && x>=z){
    if(y>z)
      printf("%d, %d, %d", x, y, z);
    else
      printf("%d, %d, %d", x, z, y);
  }
  else if(x>=y && x<=z)
    printf("%d, %d, %d", z, x, y);
}

You may also like...

发表评论

邮箱地址不会被公开。 必填项已用*标注