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. 下列数据中，（ ）是非线性数据结构。
A．栈 B. 队列 C. 完全二叉树 D. 堆 16．连续存储设计时，存储单元的地址（ ）。
A．一定连续 B．一定不连续 C．不一定连续 D．部分连续，部分不连续 17．以下属于逻辑结构的是（ ）。
A．顺序表 B. 哈希表 C.有序表 D. 单链表 18.一个数据对象是（ ）的集合。
A.相同类型的数据项 B.相同类型的数据元素
C.不同类型的数据项 D.不同类型的数据元素 19. ( )是数据的基本单位。
A.数据项 B.关键字 C.数据元素 D.数据类型 20.数据结构在计算机中的表示称为数据( )。 A.对象 B.的存储结构 C.类型 D.元素 21.下列程序段的时间复杂度为( )。 { for(i=0；i<5；i++) for(j=0；j A.O(5) B.O(5+n) C.O(n5 ) D.O(n) 22．数据结构是一门研究非数值计算的程序设计问题中计算机的（①）以及它们之间 2 的（②）和运算等的学科。 ①A．操作对象 B．计算方法 C．逻辑存储 D．数据映象 ②A．结构 B．关系 C．运算 D．算法 23．数据结构被形式地定义为（K，R），其中K是（①）的有限集合，R是K上的（②） 的有限集合。 ①A．算法 B．数据元素 C．数据操作 D．逻辑结构 ②A．操作 B．映象 C．存储 D．关系 24．在数据结构中，从逻辑上可以把数据结构分成（①）。 A．动态结构和静态结构 B．紧凑结构和非紧凑结构 C．线性结构和非线性结构 D．内部结构和外部结构 25．线性表的顺序存储结构是一种（①）的存储结构，线性表的链式存储结构是一种 （②）的存储结构。 A．随机存取 B．顺序存取 C．索引存取 D．散列存取 26．算法分析的目的是（①），算法分析的两个主要方面是（②）。 ①A．找出数据结构的合理性 B．研究算法中的输入和输出的关系 C．分析算法的效率以求改进 D．分析算法的易懂性和文档性 ②A．空间复杂性和时间复杂性 B．正确性和简明性 C．可读性和文档性 D．数据复杂性和程序复杂性 27．计算机算法指的是（①），它必具备输入、输出和（②）等五个特性。 ①A．计算方法 B．排序方法 C．解决问题的有限运算序列 D．调度方法 ②A．可行性、可移植性和可扩充性 B．可行性、确定性和有穷性 C．确定性、有穷性和稳定性 D．易读性、稳定性和安全性 28．线性表的逻辑顺序与存储顺序总是一致的，这种说法（①）。 A．正确 B．不正确 二、填空题 1．数据的物理结构包括 的表示和 的表示。 3 2. 对于给定的n个元素,可以构造出的逻辑结构有 （1） ， （2） ， （3） ， __（4）四种。 3．数据的逻辑结构是指 。 4．一个数据结构在计算机中 称为存储结构。 5．抽象数据类型的定义仅取决于它的一组__（1）_，而与_（2）_无关，即不论其内 部结构如何变化，只要它的_（3）_不变，都不影响其外部使用。 6．数据结构中评价算法的两个重要指标是 7. 数据结构是研讨数据的_（1）_和_（2）_，以及它们之间的相互关系，并对与这 种结构定义相应的_（3）_，设计出相应的（4）_。 8． 一个算法具有5个特性: （1） 、 （2） 、 （3） ，有零个或多个输入、有一 个或多个输出。 9． 下面程序段的时间复杂度为________。(n>1) sum=1； for (i=0;sum 10．计算机执行下面的语句时，语句s的执行次数为 _______ 。 FOR(i=l；i 11.下面程序段中带下划线的语句的执行次数的数量级是： i：=1； WHILE i 三、基础知识题 1．数据结构是一门研究什么内容的学科？ 2．数据元素之间的关系在计算机中有几种表示方法？各有什么特点？ 3．数据类型和抽象数据类型是如何定义的。二者有何相同和不同之处，抽象数据类 型的主要特点是什么？使用抽象数据类型的主要好处是什么？ 4．回答问题（每题2分） （1）在数据结构课程中，数据的逻辑结构，数据的存储结构及数据的运算之间存 在着怎样的关系？ （2）若逻辑结构相同但存储结构不同，则为不同的数据结构。这样的说法对吗？ 举例说明之。 （3）在给定的逻辑结构及其存储表示上可以定义不同的运算集合，从而得到不同 的数据结构。这样说法对吗？举例说明之。 （4）评价各种不同数据结构的标准是什么？ 4 5．评价一个好的算法，您是从哪几方面来考虑的？ 6．解释和比较以下各组概念 抽象数据类型及数据类型 数据结构、逻辑结构、存储结构 抽象数据类型 算法的时间复杂性（5） 算法（6）频度 7. 根据数据元素之间的逻辑关系，一般有哪几类基本的数据结构？ 8．对于一个数据结构，一般包括哪三个方面的讨论？ 9. 当你为解决某一问题而选择数据结构时，应从哪些方面考虑？ 10. 若将数据结构定义为一个二元组（D，R）,说明符号D，R 应分别表示什么？ 11．数据结构与数据类型有什么区别？ 12．数据的存储结构由哪四种基本的存储方法实现？ 13．若有100个学生，每个学生有学号，姓名，平均成绩，采用什么样的数据结构最 方便，写出这些结构？ 14. 运算是数据结构的一个重要方面。试举一例，说明两个数据结构的逻辑结构和存 储方式完全相同，只是对于运算的定义不同。因而两个结构具有显著不同的特性，是两个不同的结构。 15. 在编制管理通讯录的程序时, 什么样的数据结构合适? 为什么? 16. 试举一例，说明对相同的逻辑结构,同一种运算在不同的存储方式下实现，其运 算效率不同。 17. 有实现同一功能的两个算法A1和A2，其中A1的时间复杂度为Tl=O(2)，A2的 时间复杂度为T2=O(n2)，仅就时间复杂度而言，请具体分析这两个算法哪一个好。 18．设计一数据结构，用来表示某一银行储户的基本信息： 账号、姓名、开户年月 日、储蓄类型、存入累加数、利息、帐面总数。 5 n