第一章 概论习题
一、选择题
1．数据结构是具有【 B 】的数据元素的集合。
A．相同性质 B．相互关系 C．相同运算 D．数据项 2．在计算机的存储结构中，逻辑上相邻的结点存储在物理位置上也相邻的连续存储单元里，称之为【 B 】。
A．逻辑结构 B．顺序存储结构 C．链式存储结构 D．散列存储结构 3．语句for(i=1;i<=n;i++) x++;的时间复杂度为【 B 】。
A．O(1) B．O(n) C．O(n2) D．O(n3) 4．下面不属于数据的存储结构的是【 D 】。
A．散列存储 B．链式存储 C．索引存储 D．压缩存储 5．数据结构研究的是数据的【 A 】及它们之间的相互关系。
A．存储结构和逻辑结构 B．存储和抽象 C．理想与抽象 D．理想与逻辑 6．下面程序段的时间复杂度是【 D 】。 for(i=0;i<2*n;i++) for(j=1;j<3*n;j++) A[i][j]=0;
A．O(n) B．O(5n) C．O(6n2) D．O(n2) 7．数据的逻辑结构有两大类，分别是【 B 】。
A．顺序存储结构和链式存储结构 B．线性结构和非线性结构 C．压缩结构和非压缩结构 D．有序结构和无序结构 8．以下与数据的存储结构无关的术语是【 D 】。
A．循环队列 B．链表 C．哈希表 D．栈 9．算法分析的两个主要方面是【 A 】。
A．空间复杂度和时间复杂度 B．正确性和简明性
C．可读性和文档性 D．数据复杂性和程序复杂性 10．下面程序段的时间复杂度是【 D 】。 S=0;
for(i=0;i A．O(1) B．O(m+n) C．O(log2mn) D．O(m*n) 11．能够输入计算机并能被计算机处理的符号统称为【 A 】。 A．数据 B．数据元素 C．数据结构 D．数据类型 12．以下属于逻辑结构的是【 C 】。 A．顺序表 B．哈希表 C．有序表 D．单链表 13．线性结构的数据元素之间存在着【 A 】的关系。 A．一对一 B．一对多 C．多对一 D．多对多 14．对于数据结构，以下叙述中不正确的是【 A 】。 A．相同的逻辑结构，对应的存储结构也必相同 B．数据结构由逻辑结构、存储结构和运算三方面组成 C．数据存储结构就是数据逻辑结构在存储器中的实现 D．对数据基本运算的实现与存储结构有关 15．下列程序的时间复杂度为【 A 】。 i=0; s=0; while(s A．O( ) B．O( ) C．O(n) D．O(n2) 16．下列说法正确的是【 C 】。 A．数据是数据元素的基本单位 B．数据元素是数据项中不可分割的最小标识单位 C．数据可由若干个数据元素构成 D．数据项可由若干个数据元素构成 17．下列选项中，不属于线性结构特征的是【 D 】。 A．数据元素之间存在线性关系 B．结构中只有一个开始结点 C．结构中只有一个终端结点 D．每个结点都仅有一个直接前趋 18．下列叙述中，不正确的是【 A 】。 A．算法解决的只能是数值计算问题 B．同一问题可以有多种不同算法 C．算法的每一步操作都必须明确无歧义 D．算法必须在执行有限步后结束 二、填空题 1．下面程序段的时间复杂度是 O（n） 。 i=1; j=0; while(i+j<=n) if(i>j) j++; else i++; } 2．数据元素及其关系在计算机内的存储方式，称为数据的 存储结构或物理结构 。 3．一个算法的 时间复杂度 是该算法的时间耗费，它是该算法所求解问题规模n的函数。 4．下面算法的时间复杂度为 O(n2) 。 void fun(int n) { int i,j,x=0; for(i=1;i 8．数据的链式存储结构的特点是借助 指针 表示数据元素之间的逻辑关系。 9． 数据类型 是一个值的集合以及在这些值上定义的一组操作的总称。 10．表示逻辑关系的存储结构可以有四种方式，即顺序存储方式、链式存储方式、 索引存储方式 和散列存储方式。 三、解答题 1．试举一个数据结构的例子，叙述其逻辑结构、存储结构两方面的内容。 答：以顺序表为例： 顺序表的逻辑结构：在数据元素非空的有限集合中，存在唯一的一个被称作“第一个”的数据元素。存在唯一的一个被称作“最后一个”的数据元素，除第一个外，集合中每个数据元素均只有一个直接前趋，除最后一个外，集合中的每个数据元素均只有一个直接后继。 顺序表的存储结构：在内存中用一片连续的存储区域存储线性表的数据元素。使逻辑上相邻的数据元素在物理存储时也相邻。