大连东软 数据结构题库

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．找出数据结构的合理性

C．分析算法的效率以求改进

（2） A．空间复杂度和时间复杂度

C．可读性和文档性

B．研究算法中的输入与输出的关系 D．分析算法的易查性和文档性 B．正确性和简明性

D．数据复杂性和程序复杂性

3② 设语句 X++的时间是单位时间，则语句： for

（i=1;i<=n;i++） x++;

时间复杂度为（ C ）。

A．O（1） B．O （n） C．O （n2） D．O （n3）

4② 算法的计算量的大小称为计算的（ B ）。【北京邮电 2000】 A．效率 B．复杂性 C．现实性 D．难度

5② 算法的时间复杂度取决于（ C ）【中科院计算所 1998】 A．问题的规模 B．待处理数据的初态 C．A 和 B 6② 下面关于算法说法错误的是（ A ）【南京理工 2000】 A．算法最终必须由计算机程序实现

B．为解决某问题的算法同为该问题编写的程序含义是相同的 C．算法的可行性是指指令不能有二义性 D．以上几个都是错误的

7② 下面说法错误的是（ D ）【南京理工 2000】

（1） 算法原地工作的含义是指不需要任何额外的辅助空间

（2） 在相同的规模 n 下，复杂度 O（n）的算法在时间上总是优于复杂度 O（2n）的算法 （3） 所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界 （4） 同一个算法，实现语言的级别越高，执行效率就越低 A．（1） B．（1）,（2） C．（1）,（4） D．（3） 8② 程序段 for（i=n-1;i>=1;i++） for（ j=1;j<= i;j++）

if（ A[j]>A[j+1]） A[j]与 A[j+1]对换；

其中 n 为正整数，则最后一行的语句频度在最坏情况下是（ D ）【南京理工 1998】 A．O（n） B．O（nlog2 n） C． O（n3） D． O（n2） 二、填空题

1① 以夹杂自然语言和程序语句的形式来描述解决问题的方法称为____伪码________。 2① 一个算法的效率可分为___时间______效率和__空间_______效率． 3② 有一个程序片断如下：

for（i=0;i

则其时间复杂度为：_O（n）________ 4② 有一个程序片断如下： 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;k

（\）; }

return （sum）;

} 【华中理工 2000】

2.7 习题

2.7.1 知识点：线性表的逻辑结构

一、选择题

1① 线性表 L=（a1, a 2 ,…,a n ）,下列说法正确的是 （D ）。

A．每个元素都有一个直接前驱和一个直接后继。 B．线性表中至少要有一个元素。

C．表中诸元素的排列顺序必须是由小到大或由大到小。

D．除第一个和最后一个元素外,其余每个元素都有一个且仅有一个直接前驱和直接后继。 2① 在线性表的下列运算中，不改变数据元素之间结构关系的运算是（ D ）。

A．插入 B．删除

C．排序 D．定位

3① 线性表是具有n 个（C ）的有限序列（n>0）。【清华 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 ）个元素． A．n-1

B．n-i+1

C．n-i-1

D．i

2① 若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用（ D ）存储方式最节省时间。

A．单链表 B．双链表 C．单向循环 D．顺序表

3② 一个数组第一个元素的存储地址是 100，每个元素的长度为 2，则第 5 个元素的地址是（ B ）

A．110 B．108 C．100 D．120

4① 下述哪一条是顺序存储结构的优点（ A ）。【北方交通 2001】

A．存储密度大 B．插入运算方便

C．删除运算方便 D．可方便地用于各种逻辑结构的存储表示

5③ 若长度为 n 的线性表采用顺序存储结构，在其第 i 个位置插入一个新元素的算法的时间复杂度为（ C ） （1<=i<=n+1）。【北京航空航天 1999】

A．O（0） B．O（1） C．O（n） D．O（n 2 ）

6③ 对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为（ C ）。【青岛 2000】

A．O（n） O（n） B．O（n） O（1） C．O（1） O（n） D．O（1） O（1） 二、 填空题

1① 线性表的顺序存储的缺点是在任意位置上___插入_____数据与____删除_____数据费时间。 2① 设一线性表的顺序存储，总存储容量为 M，其元素存储位置的范围为__0~M-1__________。 3① 向一个长度为 n 的向量中删除第 i 个元素（1≤i≤n）时，需向前移动____n-i______个元素。 三、 简答题

1③ 已知线性表的存储结构为顺序表，阅读下列算法，并回答问题： void f30 （SeqList *L） { int i，j;

for （i=j=0;ilength; i++） if（L->data[i]>=0）{

if（i!=j）L->data[j]=L->data[i]; j++； } L->length=j; } （1） （2）

设线性表 L=（21，-7，-8，19，0，-11，34，30，-10），写出执行 f30（&L）后L状态；(21,19,0,34,30) 简述算法 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① 对单链表表示法,以下说法错误的是（C ）。

A．数据域用于存储线性表的一个数据元素。

B．指针域（或链域）用于存放一个指向本结点所含数据元素的直接后继所在结点的指针。 C．所有数据通过指针的链接而组织成单链表。

D．NULL 称为空指针，它不指向任何结点只起标志作用。 6① 以下说法正确的是（D ）。

A．顺序存储方式的优点是存储密度大且插入、删除运算效率高 B．链表的每个结点中都恰好包含一个指针 C．线性表的顺序存储结构优于链式存储结构

D．顺序存储结构属于静态结构而链式结构属于动态结构 7① 以下说法错误的是（D ）。

A．求表长、定位这两种运算在采用顺序存储结构时实现的效率不比采用链式存储结构时实现的效率低 B．顺序存储的线性表可以随机存取

C．由于顺序存储要求连续的存储区域,所以在存储管理上不够灵活 D．线性表的链式存储结构优于顺序存储结构 8① 不带头结点的单链表 head 为空的判定条件是（ A ）。

A．head= =NULL B．head->next= =NULL C．head->next= =head D．head!=NULL

9① 带头结点的单链表 head 为空的判定条件是（ B ）。

A．head= =NULL B．head->next= =NULL C．head->next= =head D．head!=NULL

10② 在头指针为 head 的非空单循环链表中，指针 p 指向尾结点，下列关系成立的是（ A ）。

A．p->next= =head B．p->next->next= =head C．p->next= =NULL D．p= =head

本文来源：https://www.bwwdw.com/article/bvfv.html