数据结构习题练习（一）-绪论

数据结构习题练习目录
参考：数据结构实验与习题答案是参考书给的，有疑问我的我会备注一下。
分析都是个人观点，但都是我确定的，
不过有些可能会因为我头发长见识短不知道的，麻烦评论提醒一下。

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

选择题

1. 数据结构是一门研究非数值计算的程序设计问题中计算机的①以及它们之间的②和运算等的学科。
   ① A．操作对象 Ｂ．计算方法 Ｃ．逻辑存储 Ｄ．数据映象
   ② A．结构 Ｂ．关系 Ｃ．运算 Ｄ．算法
2. 数据结构被形式地定义为（K，R），其中 K 是①的有限集合，R 是 K 上的②有限集合。
   ① A．算法 Ｂ．数据元素 Ｃ．数据操作 Ｄ．逻辑结构
   ② A．操作 Ｂ．映象 Ｃ．存储 Ｄ．关系
3. 在数据结构中，从逻辑上可以把数据结构分成①。
   A．动态结构和静态结构 Ｂ．紧凑结构和非紧凑结构
   Ｃ．线性结构和非线性结构 Ｄ．内部结构和外部结构
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;ifor (j=0;jA[i][j]=0;
8. 下面程序段的时间复杂度是①。
   i=s=0;
   while (s{ i++; /i=i+1/
   s+=i; /s=s+1/
   }
9. 下面程序段的时间复杂度是①。
   s=0;
   for (i=0;ifor (j=0;js+=B[i][j];
   sum=s;
10. 下面程序段的时间复杂度是①。
    i=1;
    while (i<=n)
    i=i*3;

程序设计题

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

选择题分析

1. 数据结构是一门研究非数值计算的程序设计问题中计算机的①以及它们之间的②和运算等的学科。
   ① A．操作对象 Ｂ．计算方法 Ｃ．逻辑存储 Ｄ．数据映象
   ② A．结构 Ｂ．关系 Ｃ．运算 Ｄ．算法
   这题属于死记硬背的东西，我也想不出解释的东西。
   .
2. 数据结构被形式地定义为（K，R），其中 K 是①的有限集合，R 是 K 上的②有限集合。
   ① A．算法 Ｂ．数据元素 Ｃ．数据操作 Ｄ．逻辑结构
   ② A．操作 Ｂ．映象 Ｃ．存储 Ｄ．关系
   同上，记下来吧*2。
   .
3. 在数据结构中，从逻辑上可以把数据结构分成①。
   A．动态结构和静态结构 Ｂ．紧凑结构和非紧凑结构
   Ｃ．线性结构和非线性结构 Ｄ．内部结构和外部结构
   同上，记下来吧*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;ifor (j=0;jA[i][j]=0;
   这是两层循环，还是定长循环，里面的赋值语句时间复杂度为O(1)，因此就是两层的乘积。
   .
8. 下面程序段的时间复杂度是①O(n^1/2)。
   i=s=0;
   while (s{ i++; /i=i+1/
   s+=i; /s=s+1/
   }
   题目错了，s+=i与s=s+1不等效，应该是注释错了。
   这题我也不清楚，我还以为是O(n)。
   .
9. 下面程序段的时间复杂度是①O(n²)。
   s=0;
   for (i=0;ifor (j=0;js+=B[i][j];
   sum=s;
   和第7题一样。
   .
10. 下面程序段的时间复杂度是①O(log₃n)。
    i=1;
    while (i<=n)
    i=i*3;
    就是i³ = n，那么i = log₃n，是个数学问题。

程序设计题分析

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