数据结构第1章绪论

第1章绪论一、选择题1. 算法的计算量的大小称为计算的（）。

【北京邮电大学2000 二、3 （20/8分）】A．效率 B. 复杂性 C. 现实性 D. 难度2. 算法的时间复杂度取决于（）【中科院计算所 1998 二、1 （2分）】A．问题的规模 B. 待处理数据的初态 C. A和B3.计算机算法指的是（1），它必须具备（2）这三个特性。

(1) A．计算方法 B. 排序方法 C. 解决问题的步骤序列 D. 调度方法(2) A．可执行性、可移植性、可扩充性 B. 可执行性、确定性、有穷性C. 确定性、有穷性、稳定性D. 易读性、稳定性、安全性【南京理工大学 1999 一、1（2分）【武汉交通科技大学 1996 一、1（ 4分）】4．一个算法应该是（）。

【中山大学 1998 二、1（2分）】A．程序 B．问题求解步骤的描述 C．要满足五个基本特性 D．A和C.5. 下面关于算法说法错误的是（）【南京理工大学 2000 一、1（1.5分）】A．算法最终必须由计算机程序实现B.为解决某问题的算法同为该问题编写的程序含义是相同的C. 算法的可行性是指指令不能有二义性D. 以上几个都是错误的6. 下面说法错误的是（）【南京理工大学 2000 一、2 （1.5分）】(1）算法原地工作的含义是指不需要任何额外的辅助空间（2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界（4）同一个算法，实现语言的级别越高，执行效率就越低A．(1) B.(1),(2) C.(1),(4) D.(3)7．从逻辑上可以把数据结构分为（）两大类。

【武汉交通科技大学 1996 一、4（2分）】A．动态结构、静态结构 B．顺序结构、链式结构C．线性结构、非线性结构 D．初等结构、构造型结构8．以下与数据的存储结构无关的术语是（）。

【北方交通大学 2000 二、1（2分）】A．循环队列 B. 链表 C. 哈希表 D. 栈9．以下数据结构中，哪一个是线性结构（）？【北方交通大学 2001 一、1（2分）】A．广义表 B. 二叉树 C. 稀疏矩阵 D. 串10．以下那一个术语与数据的存储结构无关？（）【北方交通大学 2001 一、2（2分）】A．栈 B. 哈希表 C. 线索树 D. 双向链表11．在下面的程序段中，对x的赋值语句的频度为（）【北京工商大学 2001 一、10（3分）】FOR i:=1 TO n DOFOR j:=1 TO n DOx:=x+1;A． O(2n) B．O(n) C．O(n2) D．O(log2n)12．程序段 FOR i:=n-1 DOWNTO 1 DOFOR j:=1 TO i DOIF A[j]>A[j+1]THEN A[j]与A[j+1]对换；其中 n为正整数，则最后一行的语句频度在最坏情况下是（）A. O（n）B. O(nlogn)C. O(n3)D. O(n2)【南京理工大学1998一、1(2分)】13．以下哪个数据结构不是多型数据类型（）【中山大学 1999 一、3（1分）】A．栈 B．广义表 C．有向图 D．字符串14．以下数据结构中，（）是非线性数据结构【中山大学 1999 一、4】A．树 B．字符串 C．队 D．栈15. 下列数据中，（）是非线性数据结构。

一、单选题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、数据的逻辑结构可以分为 ______ 两类。

A、紧凑结构和非紧凑结构B、动态结构和静态结构C、线性结构和非线性结构D、内部结构和外部结构7、数据的逻辑结构是指 ______ 关系的整体。

A、数据项之间逻辑B、数据元素之间逻辑C、数据类型之间D、存储结构之间8、以下是数据结构中 ______ 属非线性结构。

A、串B、栈C、队列D、平衡二叉树9、以下属于逻辑结构是 ______。

A、双链表B、单链表C、顺序表D、有序表10、以下不属于存储结构是______。

A、顺序表B、线性表C、邻接表D、单链表11、在计算机中存储数据时，通常不仅要存储各数据元素的值，而且还有存储 ______。

A、数据元素之间的关系B、数据元素的类型C、数据的处理方法D、数据的存储方法12、数据结构在计算机内存中的表示是指 ______。

A、数据的逻辑结构B、数据结构C、数据元素之间的关系D、数据的存储结构13、在数据的存储中，一个节点通常存储一个 ______。

A、数据结构B、数据元素C、数据项D、数据类型14、在决定选取任何类型的存储结构时，一般不多考虑 ______。

A、各节点的值如何B、节点个数的多少C、对数据有哪些运算D、所用编程语言实现这种结构是否方便15、数据在计算机的存储器中表示时，逻辑上相邻的两个元素对应的物理地址也是相邻的，这种存储结构称之为 ______。

31.顺序存储方式只能用于存储线性结构。（×） 32.顺序存储方式的有点是存储密度大，且插入、删除运算效率高。（×）
单元 3 栈和队列 1.一个顺序栈一旦被声明，其占用空间的大小（ ）。
A. 已固定 B. 动态变化 C. 可以改变 D. 不能固定 2.链栈和顺序栈相比，有一个比较明显的缺点，即（ ）。 A. 不会出现栈空的情况 B. 插入操作更加方便 C. 删除操作更加方便 D. 通常不会出现栈满的情况 3.用单链表表示的链式队列的队头在链表的（ ）位置。 A. 链头 B. 任意位置 C. 链尾 D. 链中 4.在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印数据缓 冲区，主机将要输出的数据依次写入缓冲区中，而打印机则从缓冲区中取出数据 打印，该缓冲区应该是一个（ ）结构。 A. 数组 B. 堆栈 C. 队列 D. 线性表 5.循环队列 A[m] 存放其元素，用 front 和 rear 分别表示队头及队尾，则循环队 列满的条件是（ ）。
12.一个栈的进栈序列是 5，6，7，8，则栈的不可能的出栈序列是（ ）。（进 出栈操作可以交替进行）
A. 8，7，6，5 B. 7，6，8，5 C. 7，6，5，8 D. 5，8，6，7 13.栈的插入删除操作在（ ）进行。 A. 栈底 B. 栈顶 C. 指定位置 D. 任意位置 14.栈和队列的相同点是（ ）。 A. 逻辑结构与线性表相同，都是操作规则受到限制的线性表 B. 逻辑结构与线性表不同 C. 都是后进后出 D. 都是后进先出 15.以下说法正确的是（ ）。 A. 栈的特点是先进先出，队列的特点是先进后出 B. 栈和队列的特点都是先进后出
14.算法是在数据结构的基础上对特定问题求解步骤的一种描述，也是若干条指 令组成的优先序列（√）。 15.算法可以用不同的语言描述，如果用 C 语言等高级语言来描述，则算法实际 上就是程序了（×）。 16.程序一定是算法（×）。 17.数据的物理结构是指数据在计算机内的实际存储形式（√）。 18.数据结构中评价算法的两个重要指标是时间复杂度和空间复杂度（√）。 19.在顺序存储结构中，有时也存储数据结构中元素之间的关系（×）。

· 数据抽象 用ADT描述程序处理的实体时，强
调的是其本质的特征、其所能完成的功 能以及它和外部用户的接口（即外界使 用它的方法）。
· 数据封装 将实体的外部特性和其内部实现细
节分离，并且对外部用户隐藏其内部实 现细节。
精选ppt
17
• 抽象数据类型的形式描述为：
ADT = ( D，S，P ) 其中：D 是数据对象，
其中：C是含两个实数的集合﹛C1，C2﹜，分别表示复数的 实部和虚部。R={P}，P是定义在集合上的一种关系{〈C1， C2〉}。
精选ppt
10
● 数据结构包括： 1. 数据逻辑结构：是对数据元素之间存在的
逻辑关系的描述，它可以用一个数据元素的集 合和定义在此集合上的若干关系表示。
2. 数据物理结构：是数据逻辑结构在计算机 中的表示和实现（逻辑结构在存储器中的映 象），故又称数据“存储结构”。它包含数据 元素的映象和关系的映象。
人的标志。
精选ppt
4
算法的设计，依赖于计算机如何存储人的名 字和对应的电话号码，或者说依赖于名字和其 电话号码的结构。
数据的结构，直接影响算法的选择和效率。
上述的问题是一种数据结构问题。可将名字 和对应的电话号码设计成：二维数组、表结构、 向量。
比如，名字和其电话号码逻辑上可安排成N 元向量的形式，它的每个元素是一个数对(ai ， bi)， 1≤i≤n
• 一类是不可分割的“原子”型数据元素，如： 整数“5”，字符 “N” 等；
• 另一类是由多个款项构成的数据元素，其中 每个款项被称为一个“数据项”。数据项是 数据结构中讨论的“最小单位”。
姓名 学号 性别
班号
出生日期
入学成绩
年月日
精选ppt