1：数据结构是一门研究非数值计算的程序设计问题中计算机的-----（1）-----以及它们之间的---（2）----和元算等的科学。 A B
（1） A, 数据元素 B 计算方法 C 逻辑存储 D数据映像 （2） A 结构 B 关系 C 运算 D算法
2：在数据结构中，从逻辑上可以把数据结构分为（ ）两类。 C
A动态结构和静态结构
B紧凑结构和非紧凑结构
C 线形结构和非线性结构
D内部结构和外部结构
3 数据的逻辑结构是（ ）关系的整体。 A A数据元素之间的逻辑 B数据项之间的逻辑 C 数据类型之间
D存储结构之间
4, 在计算机的存储器中表示时，物理地址和逻辑地址相同并且是连续的，称之为：（ ）。A逻辑结构
B顺序存储结构 C 链式存储结构
D以上都对
5 一个存储结点存储一个（ ） B
A 数据项 B数据元素 C数据结构
D数据类型 6 数据运算（
）。 A
A，效率与采用何种存储结构有关。 B是根据存储结构来定义的 C 有算术运算和关系元算两大类 D必须用程序设计语言来描述
7 数据结构在计算机内存中的表示是指：（
） A数据结构的存储结构
B数据结构 C 数据的逻辑结构
D数据元素之间的关系
答：A
8 在数据结构中，与所使用的计算机无关的是：（
）
A 逻辑结构
B存储结构 C逻辑结构和存储结构
D物理结构
答A
9 数据采用链式存储结构时，要求（ ）
A每个结点占用一片连续的存储区域 B所有结点占用一片连续的存储区域 C结点的最后一个数据域是指针类型
D 每个结点有多少个后继，就设多少个指针域 答：A
10：下列说法中，不正确的是（
） A数据元素是数据的基本单位
B数据项是数据中不可分割的最小克标识单位 C数据可由若干个数据元素构成 D 数据项可由若干个数据元素构成 答：D 11：（
）不是算法的基本特性。 A可行性
B程度有限 C在规定的时间内完成
D确定性
答：B
12：计算机中算法指的是解决某一种问题的有限运算序列，它必须具备输入，输出（
）
1
B
A可行性，可移植性和可扩充性 C确定性，有穷性和稳定性 答：B
13：一个算法具有（ A可行性 C确定性
）
B至少一个输入 D健壮性
）
B可行性，有穷性和确定性
D易读性，稳定性和确定性
14：下面关于算法的说法正确的是（ A 算法最终必须由计算机程序实现
B为解决某问题的算法同为该问题编写的程序含义是相同的。 C算法的可行性是指指令不能有二义性 D以上几个都是错误的。 答：B
15：算法的时间复杂度与（ A问题规模 答：A
16:算法的主要任务是分析（ A算法是否具有较好的可读性 B算法中是否存在语言错误 C算法的功能是否符合设计要求 D算法的执行时间和问题规模之间的关系 答：D
17：某算法的时间复杂度O(n^2)，表明该算法的（ A我那天规模是n^2 答：C
18：算法分析的目的是（
）
A找出数据结构的合理性 B研究算法中输入和输出的关系
C.分析算法的效率以求改进 D.分析算法的易读性和文档性
答：算法分析即算法效率分析，包括时间复杂度和空间复杂度分析，其目的是为了改进算法效率。本题答案为C。
19.下述函数中渐进时间复杂度最小是＿＿。
A.T1 (n)=nlbn+5000n B.T2(n)=n-8000n C.T3(n)=n-6000n D.T4(n)=2nlbn-7000lbn
答：T1 (n)＝O(nlbn), T2(n)= O(n), T3(n)=O(n), T4(n)=O(nlbn)。其中T1 (n) 和T4(n)时间复杂度的数量级相同，但当n足够大时，lbn>5000n /n-7000,即T1 (n) A.T1 (n)=nlbn+1000lbn B.T2(n)= n -1000lbn C.T3(n)=n-1000lbn D.T4(n)=2nlbn-1000lbn 答：T1 (n)＝O(nlbn), T2(n)= O(n), T3(n)=O(n), T4(n)=O(nlbn)。其中T1 (n) 和T4(n)时间复杂度的数量级相同，但当n足够大时，nlbn>2000lbn,即T1 (n) 1.数据的逻辑结构是指———————。答：数据元素之间的逻辑关系。 2.一个数据结构在计算机中的————称为存储结构。答：映像。 2 lbn 2 2 lbn 2 lbn lbn 2 ）有关。 B计算机硬件性能 C编译程序质量 D程序设计语言 ） ） B执行时间等于n^2 C执行时间与n^2成正比 D问题规模与n^2成正比 3.顺序存储方法是把逻辑上 (1) 存储在物理位置上 (2) 里；链式存储方法中节点间的逻辑关系是由 (3) 的。答：（1）相邻的节点（2）相邻的存储单元（3）附加的指针字段表示 4.数据结构是研究数据的 (1) 和 (2) 以及它们之间的相互关系，并对这种结构定义相应的 (3) ，设计出相应的 (4) ，而确保经过这些运算后所得到的新结构是原来的结构类型。 答：数据结构由三部分组成，即逻辑结构、存储结构以及算法。在求解应用时，先设计问题的数据结构，在此基础上设计相应的求解算法，算法与数据结构是密不可分的。所以本题答案为：（1）存储结构（或物理结构）（2）逻辑结构（3）运算（4）算法 5、一个算法具有五个特性：——、——、——、输入和输出。答：可行性、有穷性、确定性。 6.算法的执行时间是——的函数。答：问题规模。 7.以下为各算法所有语句频度之和的表达式，其中时间复杂度相同的是——。 A.TA(n)=2n+3n+1000 B.TB(n)=n-nlbn-1000 C．Tc(n)= 3 2 3 2 n2lbn+ n2 D:Td(n)= n2+1000 Td(n)= O(n^2) 答：Ta(n)=O(n^3) Tb(n) =O(n^3) 1.4.3 判断题 1．判断以下叙述的正确性。 （1）数据元素是数据的最小单位。 Tc(n)= O( n2lbn) （2）数据对象就是一组数据元素的集合。 （3）任何数据结构都具备三个基本运算：插入、删除与查找。 （4）数据是由一些类型相同的数据元素构成的 （5）数据的逻辑结构与各数据元素在计算机中如何存储有关 （6）如果数据元素值发生改变,则数据的逻辑结构也随之改变。 （7）逻辑结构相同的数据，可以采用多种不同的存储方法 （8）逻辑结构不相同的数据，要采用不同的存储方法来存储。 （9）逻辑结构相同的数据，结点类型也一定相同。 （10）数据的逻辑结构是指数据的各数据项之间的逻辑关系。 答：（1）数据项是数据的最小单位。错（2）这里未强调数据元素的性质相同。错 （3）如队列和栈结构不具备查找运算。错（4）正确（5）错误（6）错误（7）正确（8）错误（9）错误 （10）数据的逻辑结构是指数据的各数据元素之间的逻辑关系。错误 2. 判断以下叙述的正确性。 (1）顺序存储方式只能用于存储线性结构。(2)数据元素是数据的最小单位 (3)算法可以用不同的语言描述，如果用c语言或PASCAL语言等高级语言来描述，则算法实现上就是程序了。(4)数据结构是带有结构的数据元素的集合 (5)数据的逻辑结构是指各数据元素之间的逻辑关系，是用户根据需要而建立的。 (6)数据结构、数据元素、数据项在计算机中的映像（或表示）分别称为存储结构、结点和数据域。 (7)数据的物理结构是指数据在计算机内的实际的存储形式。 答： （1）错误。顺序存储方式也可以用于存储树形结构，如完全二叉树可用一维数组来存储。 （2）错误。数据元素是数据的基本单位，数据元素可以由数据项组成。 （3）错误。算法用各种计算机语言描述可表现为一个程序但并不等于程序。因为程序逻辑不一定满足有穷性。（4）正确（5）正确（6）正确（7）正确 1.4.4 简答题 1：数据运算是数据结构的一个重要方面。试举一例说明两个数据结构的逻辑结构和存储结构和存储方式完 3 全相同，只是对于运算的定义不同，因而两个结构具有显著不同的特性，是两个不同的结构。 答：在数据结构中这类例较多，如顺序表和字符串。下面以二叉树和二叉排序树进行说明。 二叉树的定义为：二叉树是有限的结点集合，这个集合或者是空，或者由一个根结点和两个互不相交的称为左子树和右子树的二叉树组成。 二叉排序树的定义为：二叉排序树或者是空树，或者是满足以下性质的二叉树。 （1）若它的左子树非空，则左子树上所有记录的值均小于根记录的值。 （2）若它的右子树非空，则右子树上所有记录的值均小于根记录的值。 （3）左右子树本生各又是一棵二叉排序树。 两者在逻辑结构和存储方式完全相同，因为二叉排序树完全采用地叉树的逻辑表示和存储方式。两者的运算有建立树、插入结点、删除结点、查找结点等。对于二叉树和二叉排序树，这些运算的定义是不同的，以查找结点为例，二叉树的时间复杂度为O(n),而二叉排序树的时间复杂度为O(lbn), 二叉树和二叉排序树是两个不同的结构。前者通常用于表示层次关系。，后者通常用于排序和查找。 2.当为解决某一问题而选择数据结构时，应从哪些方面考虑？ 答：通常从两方面考虑，第一是算法所需的存储空间量；第二是算法所需的时间。对算法所需的时间又涉及以下几点； （1） 程序运行时所需输入的数据总量。 （2） 计算机执行每条指令所需的时间。 （3） 程序中指令重复执行的次数。 3.按增长率由小到大的顺序排列下列各函数： 2^100, (2/3)^n ,n^n, n! ,lbn, n^lbn, n^(3/2), n^0.5 答：排序顺序如下： 单项选择题 1 线性表是 ＿＿。 A 一个有限序列，可以为空 B一个有限序列，不可以为空 C 一个无限序列，可以为空 D一个无限序列，不可以为空 答： A 2 在一个长度为n的顺序表中向第i个元素（0 A n-i B n-i+1 C n-i-1 D i 答： B 。在第i个元素之前插入一个新元素时，必须将第i个元素及之后的所有元素都后移，这样后移的元素个数是=n-i+1. 3 链表不具有的特点是＿＿。 A 可随机访问任一元素 B 插入删除不需要移动元素 C 不必事先估计存储空间 D 所需空间与线性表长度成正比 答：A。链表不同于线性表，它不适合随机存取元素。 4 线性表采用链表式存储结构时，其地址＿＿。 A 必须是连续的 B 一定是不连续的 C 部分地址必须是连续的 D 连续是否均可以 答：D。 链式存储结构并不需要地址是连续的，这是与顺序表存储结构最大的不同。 5 在线性表的下列存储结构中，读取元素花费时间最少的是＿＿。 A 单链表 B双链表 C循环链表 D顺序表 答：D 4