1.6 习题 1.6.1 知识点：数据结构的定义 一、选择题 1 数据结构通常是研究数据的（ A ）及它们之间的相互联系。 A存储和逻辑结构 B存储结构 C顺序结构 D链式存储结构 2 数据在计算机存储器表示时，物理地址与逻辑地址相同并且是连续的，称之为（ C ） A存储结构 B逻辑结构 C 顺序存储结构 D链式存储结构 3 线性结构是数据元素之间存在一种（ D ）。 A一对多关系 B. 多对多关系 C 多对一关系 D 一对一关系 4 计算机部数据处理的基本单位是（ B ）。 A. 数据 B数据元素 C.数据项 D数据库 5 从逻辑上可以把数据结构分为（C ）两大类。【交通科技 1996】 A动态结构、静态结构 B顺序结构、链式结构 C线性结构、非线性结构 D初等结构、构造型结构二、填空题 1 数据结构按逻辑结构可分为四大类，它们分别是 集合 、 线性 、 树 、 图 。 2 数据的存储结构可用四种基本的存储方法表示，它们分别是 顺序 、 链式 、 散列 、 索引 。 三、 判断题 （ F）1 数据元素是数据的最小单位。 （ T ）2 记录是数据处理的最小单位。 （ F ）3 数据的逻辑结构是指数据的各数据项之间的逻辑关系。 （ T ）4 数据的物理结构是指数据在计算机的实际存储形式。 四、 简答题 1 简述什么是数据结构? 2 数据结构与数据类型有什么区别? 【工业 2001】 1.6.2 知识点：算法的概念 一、选择题 1 计算机算法指的是（C ） A计算方法B排序方法 C解决问题的有限运算序列D调度方法 2 算法分析的目的是（ （1）C ），算法分析的两个主要方面（ （2）A ） （1） A找出数据结构的合理性B研究算法中的输入与输出的关系 C分析算法的效率以求改进D分析算法的易查性和文档性 （2） A空间复杂度和时间复杂度B正确性和简明性 C可读性和文档性D数据复杂性和程序复杂性 3 设语句 X+的时间是单位时间，则语句： for（i=1;i=1;i+） for（ j=1;jAj+1） Aj与 Aj+1对换； 其中 n 为正整数，则最后一行的语句频度在最坏情况下是（ D ）【理工 1998】 AO（n） BO（nlog2 n） C O（n3） D O（n2） 二、填空题 1 以夹杂自然语言和程序语句的形式来描述解决问题的方法称为_伪码_。 2 一个算法的效率可分为_时间_效率和_空间_效率 3 有一个程序片断如下： for（i=0;in;i+） x=x+1; 则其时间复杂度为：_O（n）_ 4 有一个程序片断如下： for（i=0;in;i+） for（j=i;jn;j+） for（k=j;kn;k+） m=1; 则其时间复杂度为： O（n3） 5 有一个程序片断如下： for（i=0;i=2） j=j/2; 则其时间复杂度为： O（nlog2 n） 三、 判断题 （ T ）1 算法的优劣与算法描述语言无关，但与所用计算机有关。 （ T ）2 健壮的算法不会因非法的输入数据而出现莫名其妙的状态。 （ F ）3 程序一定是算法。 四、 简答题 1 如何判断一个算法的好坏? 2 调用下列 C 函数 f（n） 回答下列问题 ：（1） 试指出 f（n）值的大小，并写出 f（n）值的推导过程；（2） 假定 n= 5，试指出 f（5）值的大小和执行 f（5）时的输出结果。 C 函数： int f（int n） int i,j，k,sum= 0; for（i=l; ii-1; j-） for（k=1;k0）。【清华 1998】 A表元素 B字符 C数据元素 D数据项 E信息项二、判断题 （ T ）1 线性表中的每个结点最多只有一个前驱和一个后继。 （ F ）2 线性表中的每个结点都至少有一个前驱结点和后继结点。 （ F ）3 线性表是 N 个数的有限序列。 （ F）4 同一线性表的数据元素可以具有不同的特性。 （ T ）5 线性表的长度 n 就是表中数据元素的个数，当 n=0 时，称为空表。 （ T ）6 线性表是一个相当灵活的数据结构，它的长度可根据需要增长或缩短。 （ F ）7 对线性表中的数据元素只能进行访问，不能进行插入和删除操作。 2.7.2 知识点：线性表的顺序存储结构 一、选择题 1 在一个长度为 n 的顺序表中，在第 i 个元素（1 = i =n+1）之前插入一个新元素时需向后移动（ B ）个元素 An-1 Bn-i+1 Cn-i-1 Di 2 若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用（ D ）存储方式最节省时间。 A单链表 B双链表 C单向循环 D顺序表 3 一个数组第一个元素的存储地址是 100，每个元素的长度为 2，则第 5 个元素的地址是（ B ） A110 B108 C100 D120 4 下述哪一条是顺序存储结构的优点（ A ）。【北方交通 2001】 A存储密度大 B插入运算方便 C删除运算方便 D可方便地用于各种逻辑结构的存储表示 5 若长度为 n 的线性表采用顺序存储结构，在其第 i 个位置插入一个新元素的算法的时间复杂度为（ C ）（1=i=n+1）。【航空航天 1999】 AO（0） BO（1） CO（n） DO（n 2 ） 6 对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为（ C ）。【 2000】 AO（n） O（n） BO（n） O（1） CO（1） O（n） DO（1） O（1） 二、 填空题 1 线性表的顺序存储的缺点是在任意位置上_插入_数据与_删除_数据费时间。 2 设一线性表的顺序存储，总存储容量为 M，其元素存储位置的围为_0M-1_。 3 向一个长度为 n 的向量中删除第 i 个元素（1in）时，需向前移动_n-i_个元素。 三、 简答题 1 已知线性表的存储结构为顺序表，阅读下列算法，并回答问题： void f30 （SeqList *L） int i，j; for （i=j=0;ilength; i+） if（L-datai=0） if（i!=j）L-dataj=L-datai; j+； L-length=j; （1） 设线性表 L=（21，-7，-8，19，0，-11，34，30，-10），写出执行 f30（&L）后L状态；(21,19,0,34,30) （2） 简述算法 f30 的功能。删除顺序表中小于 0 的元素四、编程题 1 已知顺序表 La 中数据元素按非递减有序排列。试写一个算法，将 x 插入到 La 的合适位置上，保持该表的有序性。 2.7.3 知识点：线性表的链式存储结构 一、选择题 1 链表是一种采用（ B ）存储结构存储的线性表。 A顺序 B链式 C星式 D网状 2 存储的存储结构所占存储空间（ A ）。 A分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针。 B只有一部分，存放结点值。 C只有一部分，存储表示结点间关系的指针。 D分两部分，一部分存放结点值，另一部分存放结点所占单元数。 3 线性表若采用链式存储结构时，要求存中可用存储单元的地址（ D ）。 A必须是连续的 B部分地址必须是连续的 C一定是不连续的 D连续或不连续都可以 4 线性表在（ B ）情况下适用于使用链式结构实现。 A需经常修改中的结点值 B需不断对进行删除插入 C中含有大量的结点 D中结点结构复杂 5 对单链表表示法,以下