数据结构练习题1：基本概念

1.可以用（抽象数据类型）定义一个完整的数据结构。

分析： 1）抽象数据类型（ADT）描述了数据的逻辑结构和抽象运算，通常用数据对象、数据关系和基本操作集这样的三元组来表示，从而构成一个完整的数据结构定义。

2）抽象数据类型的两个重要特征：数据抽象和数据封装。 ①数据抽象：用ADT描述程序处理的实体时，强调的是其本质的特征、其所能完成的功能以及它和外部用户的接口。（即外界使用它的方法） ②数据封装：将实体的外部特性和其内部实现细节分离，并且对外部用户隐藏其内部实现细节。

抽象数据类型的理解

1.数据的逻辑结构独立于其存储结构。 分析：数据的逻辑结构从实际问题出发，只采用抽象表达方式，独立于存储结构，数据的存储方式有多种选择。而数据的存储结构是逻辑结构在计算机上的映射，它不能独立于逻辑结构而存在。

2.数据结构的三要素：逻辑结构、存储结构和运算。 问题：逻辑结构的存储方式有多种选择什么意思？ 是指既能顺序存储又能链式存储。

3.下面属于逻辑结构的是 A 顺序表 B 哈希表 C 有序表 D 单链表

4.以下与数据的存储结构有关的术语是 A.有序表 B.线性表 C.有向图 D.顺序表

5.以下与数据的存储结构无关的术语是 A 循环队列 B 链表 C 哈希表 D 栈

逻辑结构与存储结构： 3-5 CDD

有序表、线性表、有向图既能顺序存储，又能链式存储，是逻辑结构。 顺序表、循环队列、顺序栈为顺序存储。 属于逻辑结构 = 与存储结构无关 = 既能顺序存储又能链式存储 与存储结构有关 = 只能顺序存储或只能链式存储 栈逻辑结构对应的顺序存储结构为顺序栈，对应的链式存储结构为链栈。 队列的顺序存储结构是循环队列，链式存储结构是链队列，又叫做单链表。 线性表逻辑结构对应的顺序存储结构为顺序表，对应的链式存储结构为链表。

特殊案例： 有序表是指关键字有序的线性表，仅描述元素之间的逻辑关系，既可以顺序存储（使用数组）也可以链式存储（使用指针），不受存储结构制约，由于有序受到逻辑制约，属于逻辑结构。 哈希表，是个大数组，顺序存储。

问题1：如何区分数据结构和数据类型？

数据类型的运算主要是算数运算、逻辑运算等。 而数据结构运算主要是对数据的增删改查等。 数据类型和数据结构的区别

问题2：抽象数据类型有哪些？ 栈、队列、树、图、集合、映射。 问题3：哈希表是散列存储，为什么做题时不考虑这种存储方式？

6.存储数据时存储的是数据元素的值和数据元素之间的关系。

7.链式存储设计时，各个不同结点存储空间可以不连续，但结点内的存储单元地址必须连续。

typedef struct LNode {

int value; // value中存放结点值域，默认是int型

struct Lnode *next;//指向后继结点的指针

}LNode; // 定义单链表结点类型

上述定义了一个结构体，包括两部分，一是值域，二是指针域；每当定义一个结点都会产生这两个区域。如下图：

这个value与next域必须是挨着的，称这个结点为内部。 结点内部一定是连续的。若第一个结点占用两个地址，那么value域的起始地址是1，则指针域的地址就是2。同理若第二个结点的value地址是10，则next域就是11。

参考：链式存储设计时，链表结点内的存储单元地址是如何分布的

1.下列叙述中正确的是 A)算法的效率只与问题的规模有关，而与数据的存储结构无关 B)算法的时间复杂度是指执行算法所需要的计算工作量 C)数据的逻辑结构与存储结构是一一对应的 D)算法的时间复杂度与空间复杂度一定相关

2.算法的有穷性是指 A）算法程序的运行时间是有限的 B）算法程序所处理的数据量是有限的 C）算法程序的长度是有限的 D）算法只能被有限的用户使用

3.下列叙述中正确的是 A）一个逻辑数据结构只能有一种存储结构 B）数据的逻辑结构属于线性结构，存储结构属于非线性结构 C）一个逻辑数据结构可以有多种存储结构，且各种存储结构不影响数据处理的效率 D）一个逻辑数据结构可以有多种存储结构，且各种存储结构影响数据处理的效率

4.算法的空间复杂度是指 A)算法程序的长度 B)算法程序中的指令条数 C)执行算法程序所占的存储空间 D)算法执行过程中所需要的存储空间

5.在下列选项中，哪个不是一个算法一般应该具有的基本特征 A、确定性 B、可行性 C、无穷性 D、拥有足够的情报

6.被计算机加工的数据元素不是孤立的，它们彼此之间一般存在某种关系，通常把数i元素之间的这种关系称为 A 规则 B 结构 C 集合 D 运算

7.设有如下遗产继承规则:丈夫和妻子可以互相继承遗产，子女可以继承父亲和母亲的遗产，子女间不能相互继承，则表示该遗产继承关系最合适的数据结构应该是 A 树 B 图 C 线性表 D 集合

8.下面关于抽象数据类型的描述错误的是 A.数据封装 B.用例驱动 C.信息隐藏 D.使用与实现分离

9.数据结构中，与所使用的计算机无关的是数据的 A 存储结构 B 物理结构 C 逻辑结构 D 物理和存储结构

10.下列关于算法的时间复杂度陈述正确的是 A 算法的时间复杂度是指执行算法程序所需要的时间 B 算法的时间复杂度是指算法程序的长度 C 算法的时间复杂度是指算法执行过程中所需要的基本运算次数 D 算法的时间复杂度是指算法程序中的指令条数

综合选择题：1-5 BADCC 6-10 BBBCC

1…在数据元素内数据项之间也有关系，在讨论数据的逻辑结构时应考虑。 × 逻辑结构看的是数据元素之间的关系

2.同一个算法，实现语言级别越高，算法执行的效率越低。√ 级别越高，需要额外执行的条件就越多，效率也就越低。

3.集合中任何两个数据元素之间都没有逻辑关系，而且组织形式松散。√ 除同属于一个集合外，没有其他任何关系。

O(1) t=a[i]; a[i]=a[n-i-1]; a[n-i-1]=t}

该算法仅需要借助一个变量t，与问题规模n的大小无关，所以其空间复杂度为O(1)

很值得看的理解： 时间复杂度和空间复杂度计算 时间复杂度分析（含王道绪论习题）

6.以下关系式中，错误的是 D A f(n) =O(g(n)) B g(n) = O(f(n)) C h(n) = O( n 2 n^2 n2) D h(n) = O(nlog2n)

已知f(n)=O(g(n)),则必能推出g(n)=O(f(n))

7. A.O(1) B.O(n) C.O( n − 1 n^{-1} n−1) D.O( n 2 n^2 n2) 答案选B n趋与无穷，f(n)/n为常数

8.设n是描述问题规模的非负整数，下列程序段的时间复杂度是 B

A.O(logn) B.O( n 1 / 2 n^1/2 n1/2) C.O(n) D.O( n 2 n^2 n2)

9.下列程序段的时间复杂度是