《大连东软数据结构题库完整》由会员分享,可在线阅读,更多相关《大连东软数据结构题库完整(50页珍藏版)》请在金锄头文库上搜索。
1、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
2、动态结构、静态结构 B顺序结构、链式结构 C线性结构、非线性结构 D初等结构、构造型结构二、填空题 1 数据结构按逻辑结构可分为四大类,它们分别是 集合 、 线性 、 树 、 图 。 2 数据的存储结构可用四种基本的存储方法表示,它们分别是 顺序 、 链式 、 散列 、 索引 。 三、 判断题 ( F)1 数据元素是数据的最小单位。 ( T )2 记录是数据处理的最小单位。 ( F )3 数据的逻辑结构是指数据的各数据项之间的逻辑关系。 ( T )4 数据的物理结构是指数据在计算机的实际存储形式。 四、 简答题 1 简述什么是数据结构? 2 数据结构与数据类型有什么区别? 【工业 2001】
3、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 为正整数,则最后一行的语句频度在最坏情况下
4、是( 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)
5、 三、 判断题 ( 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数据
6、元素 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 个
7、元素(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 的线性表采用顺序存
8、储结构,在其第 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_
9、个元素。 三、 简答题 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
10、插入到 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 对单链表表示法,以下