数据结构练习题

数据结构练习题目录

第一章 结论 ..................................................................................................................... - 1 - 第二章 线性表 .................................................................................................................. - 8 - 第四章 串 .......................................................................................................................- 11 - 第五章 栈和队列 ............................................................................................................- 12 - 第六章 数组和广义表 .....................................................................................................- 15 - 第七章 树和二叉树 ........................................................................................................- 17 - 第三章 排序 ...................................................................................................................- 28 - 第八章 查找 ...................................................................................................................- 34 - 第九章 图 .......................................................................................................................- 37 -

第一章 结论

1. 算法的时间复杂度与下列哪项无关？（ ）

A．问题的规模 B．处理策略 C．待处理数据的初态 D．计算机的性能

解析：时间复杂度：O（f(n)），其是f(n)的函数。

时间性能（时间复杂度）：

以算法运行时间开销来度量

改进 与具体机器相关

以算法中语句的执行次数来衡量

简化 计算麻烦

以算法中语句的执行次数的数量级来替代

数量级：如果变量n的函数f(n)和g(n)满足：lim f(n)/g(n)=常数k(k≠?,0)，则称f(n)和g(n)是同一数量级的，并用f(n)=O(g(n))的形式来表示。

O(1)

2. 从逻辑上可以把数据结构分为哪两大类？（ ）

A．动态结构、静态结构 B．顺序结构、链式结构 C．线性结构、非线性结构 D．初等结构、构造型结构

解析：逻辑上分线性和非线性，物理上即存储结构答案则是B，记住下述结构。

记住下述相关术语间关系：

数据（data）—— 能够输入到计算机中并能被计算机处理的符号的集合。（广义） 分解

数据元素（data element）—— 构成数据的基本单位（具有完整的独立意义）。

描述 在某些场合还被称为元素、记录、结点、顶点等。

数据项（字段）—— 元素的具体信息

数据结构（data structure）——构成数据元素之间的结构关系。 线性结构

树形结构（树型结构） 图结构（网状结构） 集合 逻辑结构 —— 线性、树形（树型）、图（网状）、集合

存储结构 —— 数据结构在内存中的实现形式 同样的逻辑结构≠同样的存储结构 运算（判断存储结构的好坏）

有关数据结构几个方面的联系图 逻辑结构 运算定义 抽象 算法性能 数据 类型 存储结构 运算实现（算法） 算法分析 （ADT） 3. 设有数组A[i,j]，数组的每个元素长度为3字节，i的值为1 到8 ，j的值为1 到10，

- 1 -

数组从内存首地址BA开始顺序存放，当用以列为主存放时，元素A[5，8]的存储首地 址为（ ）

A．BA+141 B．BA+180 C．BA+222 D．BA+225

解析：BA+((8-1)*8+5-1)*3=B

4. 数据

解析：描述客观事物的数字、字符以及所有能输入到计算机中，并能被计算机接受的各种符号集合。

5. 递归

解析：若一个对象部分地包含它自己，或用它自己定义自己，则成这个对象是递归的；若一个函数直接或间接地调用自己，则成这个函数是递归函数。

6. 数据元素

解析：表示一个事物的一组数据，是数据的基本单位。

7. 数据结构是一门研究什么内容的学科？

解析：数据结构是一门研究在非数值计算的程序设计问题中，计算机的操作对象，及对象间的关系，和施加于对象的操作等的学科。

8. 简述评价一个好的算法需要考虑的因素。

解析：主要有四个方面。一是算法的正确性；二是算法的易读性；三是算法的健壮性；四是算法的时空效率（运行）。

9. 已知如下程序段，试计算语句1、2的频度及整个程序段的时间复杂性。 for(i = 1; i < n; i++) {

x += 1; 语句1 for(j = 1; j < n; j++)

y += 1; 语句2 }

解析： 因为，语句1位于第一层循环语句内，其频度为n；语句2位于第二层循环内，其频度为n*n；由此可见，当n趋于无穷时，整个程序的时间复杂性由语句2的频度决定，语句2为基本操作；所以，程序的时间复杂性为O(n2)。 补充：理解语句频度和复杂度的例子：

例子：求解以下程序段的时间复杂度：for（i=1; i<=n; i++） x=x+1;

语句执行次数： 1次 i=1 0 i < n n+1次

非0 n次 x=x+1

n次 i++ 共：3n+2次

数量级为：lim f(n)/g(n)= lim (3n+2)/n = 3，则时间复杂度为为O (n)

练习：(1) for (i=1; i

for (j=1; j<= i; j++) x++; ---- O(n2)

- 2 -

(2) i = 1;

while (i

10. 解答问题。设有数据逻辑结构为： B = (K, R), K = {k1, k2, ?, k9}

R={, , ,, , ,, , , , } （1）．画出这个逻辑结构的图示。 （2）．相对于关系r, 指出所有的开始接点和终端结点。

解析：

，开始结点：（入度为0）K1，K2，终端结点（出度为0）

K6，K7。

11. 下面关于算法说法错误的是（ ） A．算法最终必须由计算机程序实现

B．为解决某问题的算法同为该问题编写的程序含义是相同的 C．算法的可行性是指指令不能有二义性 D．以上几个都是错误的

解析：答案D

算法算法 —— 特定问题的求解方法，指令的有限序列 满足5个特征 ? 有穷：必须在执行有穷步骤后结束 ? 确定（无二义性）：每一步骤是确切定义的，相同的输入只能有相同的输出 ? 输入 >=0个 ? 输出 >=1个

? 可行性：能够精确执行的基本操作

12. 以下与数据的存储结构无关的术语是（ ）

A．循环队列 B．链表 C．哈希表 D．栈

解析：

D 存储结构指物理结构：顺序结构和链式结构。

栈是限制了插入删除点的线性表,只是逻辑结构而无关存储结构 A指的是在顺序表上存储的队列 B就是链接存储 C就是散列存储

13. 抽象数据类型

解析：指逻辑概念上的数据类型和这个类型上的操作集合。

14. 算法的时间复杂度

解析：算法的执行时间等于所有语句执行时间的总和，是算法所处理的数据元素

个数n的函数表示为O（f(n)）。

- 3 -

15. 数据元素之间的关系在计算机中有几种表示方法？各有什么特点？

解析：两种表示方法

（1）顺序存储方式。数据元素顺序存放，每个存储结点只含一个元素。存储位置反映数据元素间的逻辑关系。存储密度大，但有些操作（如插入、删除）效率较差。

（2）链式存储方式。每个存储结点除包含数据元素信息外还包含一组（至少一个）指针。指针反映数据元素间的逻辑关系。这种方式不要求存储空间连续，便于动态操作（如插入、删除等），但存储空间开销大（用于指针），另外不能折半查找等。 实际上，有4种表示方法，本教材没讲全，若考到此题，只写前两种即可。 四种表示方法 （1）顺序存储方式。 （2）链式存储方式。 （3）索引存储方式。除数据元素存储在一地址连续的内存空间外，尚需建立一个索引表，索引表中索引指示存储结点的存储位置（下标）或存储区间端点（下标），兼有静态和动态特性。 （4）散列存储方式。通过散列函数和解决冲突的方法，将关键字散列在连续的有限的地址空间内，并将散列函数的值解释成关键字所在元素的存储地址，这种存储方式称为散列存储。其特点是存取速度快，只能按关键字随机存取，不能顺序存取，也不能折半存取。

16. 在给定的逻辑结构及其存储表示上可以定义不同的运算集合，从而得到不同的数据结构。这样说法对吗？举例说明之。

解析：正确。栈和队列的逻辑结构相同，其存储表示也可相同（顺序存储和链式

存储），但由于其运算集合不同而成为不同的数据结构。

17. 试给出下面两个算法的运算时间。 （1） for(i = 0; i < n; i++)x += 1; （2） for(i = 0; i < n; i++)

for(j = 0; j < n; j++) y += 1;

解析：（1）程序只有一层循环， x += 1即为基本操作，时间复杂度为O(n)； （2）程序有两层循环， y += 1为基本操作，时间复杂度为O(n2)。

18. 以下数据结构中，哪一个是线性结构？（ ）

A．广义表 B．二叉树 C．稀疏矩阵 D．串

解析：线性结构是一个数据元素的有序(次序)集合。答案D，特别注意C不是线

性结构，因为没满足线性结构的几个条件。

19. 下列数据处理中不可分割的最小单位是（ ）

A．数据元素 B．数据类型 C．数据项 D．数据记录

【此教材上概念有点乱，大家看下面的整理】

- 4 -

本文来源：https://www.bwwdw.com/article/jrsv.html