数据结构 第1章概论试题

第一章概论习题一、选择题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<n;i++)for(j=0;j<m;j++)s=s+a[i][j];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 】的关系。

第1章概论习题参考解答一、填空题1、数据的逻辑结构是数据元素之间的逻辑关系，通常有下列4类：（）、（）、（）、（）。

【答】集合、线性结构、树型结构和图状结构。

2、数据的存储结构是数据在计算机存储器里的表示，主要有4种基本存储方法：（）、（）、（）、（）。

【答】顺序存储方法、链接存储方法、索引存储方法和散列存储方法。

二、选择题1、一个算法必须在执行有穷步之后结束，这是算法的（）。

（A）正确性（B）有穷性（C）确定性（D）可行性【答】B。

2、算法的每一步，必须有确切的定义。

也就是说，对于每步需要执行的动作必须严格、清楚地给出规定。

这是算法的（）。

（A）正确性（B）有穷性（C）确定性（D）可行性【答】C。

3、算法原则上都是能够由机器或人完成的。

整个算法好像是一个解决问题的“工作序列”，其中的每一步都是我们力所能及的一个动作。

这是算法的（）。

（A）正确性（B）有穷性（C）确定性（D）可行性【答】D。

三、简答题1、算法与程序有何异同？【答】尽管算法的含义与程序非常相似，但两者还是有区别的。

首先，一个程序不一定满足有穷性，因此它不一定是算法。

例如，系统程序中的操作系统，只要整个系统不遭受破坏，它就永远不会停止，即使没有作业要处理，它仍处于等待循环中，以待一个新作业的进入。

因此操作系统就不是一个算法。

其次，程序中的指令必须是计算机可以执行的，而算法中的指令却无此限止。

如果一个算法采用机器可执行的语言来书写，那么它就是一个程序。

2、什么是数据结构？试举一个简单的例子说明。

【答】数据结构是指数据对象以及该数据对象集合中的数据元素之间的相互关系（即数据元素的组织形式）。

例如，队列的逻辑结构是线性表（先进先出）；队列在计算机中既可以采用顺序存储也可以采用链式存储；对队列可进行删除、插入数据元素以及判断是否为空队列、将队列置空等操作。

3、什么是数据的逻辑结构？什么是数据的存储结构？【答】数据元素之间的逻辑关系，也称为数据的逻辑结构。

第一部分数据构造概论及算法分析一、选择题1. 数据构造是一门研究计算机中__ __对象及其关系的学科。

〔1〕数值运算〔2〕非数值运算〔3〕集合〔4〕非集合2．数据构造的定义为(K, R), 其中K是__ __的集合。

〔1〕算法〔2〕数据元素〔3〕数据操作〔4〕逻辑构造3. 算法分析的目的是____。

〔1〕找出数据构造的合理性〔2〕研究算法中输入和输出的关系〔3〕分析算法的效率以求改进〔4〕分析算法的易懂性和文档性4.数据的不可分割的根本单位是....___。

A.元素B.结点C.数据类型D.数据项5. 以下算法suanfa2的时间复杂度为____。

int suanfa2(int n){ int t=1；while(t<=n)t=t*2；return t；}A.O(log2n)B.O(2n)C.O(n2)D.O(n)6.〔〕是具有一样特性数据元素的集合, 是数据的子集。

A 数据符号B 数据对象C 数据D 数据构造7. 与数据元素本身的形式、内容、相对位置、个数无关的是数据的( )。

A.存储构造B.逻辑构..C.算法D.操作8. 数据构造是研究数据的〔〕及它们之间的互相联络。

A.理想构造, 物理构造b、理想构造, 逻辑构造C、物理构造, 逻辑构造d、抽象构造, 逻辑构造9. 组成数据的根本单位是〔〕。

a、数据项b、数据类型c、数据元素d、数据变量10. 数据在计算机存储器内表示时, 物理地址与逻辑地址一样并且是连续的, 称之为:〔A〕存储构造〔B〕逻辑构造〔C〕顺序存储构造〔D〕链式存储构造11. 算法指的是〔〕A. 计算机程序B. 解决问题的计算方法C. 排序算法D. 解决问题的有限运算序列12. 以下算法suanfa1中语句"x=x*2；"的执行次数是〔〕。

void suanfa1(int n){ int i,j,x=1；for(i=1；i<=n；i++)for(j=i；j<=n；j++)x=x*2；printf("%d",x)；}A.n(n-1)/2B.n(n+1)/2C.n2D.⎡nlog2n⎤13.由____组成的集合是一个数据对象。

习题11.填空题（1）（___________）是指数据之间的相互关系，即数据的组织形式。

通常人们认为它包含三个方面的内容，分别为数据的（___________）、（___________）及其运算。

答案：数据结构逻辑结构存储结构（2）（___________）是数据的基本单位，在计算机程序中通常作为一个整体进行处理。

答案：数据元素（3）数据元素之间的不同逻辑关系代表不同的逻辑结构，常见的逻辑结构有（___________）、（___________）、（___________）和（___________）。

答案：集合线形结构树结构图结构（4）数据的存储结构考虑的是如何在计算机中存储各个数据元素，并且同时兼顾数据元素间的逻辑关系。

基本的存储结构通常有两大类：（___________）和（___________）。

答案：顺序存储结构链式存储结构（5）通常一个问题可以有多种不同的算法，但每个算法必须满足5个准则：输入、输出、（___________）、（___________）和（___________）。

答案：有穷性确定性可行性（6）通常通过衡量算法的（___________）复杂度和（___________）复杂度来判定一个算法的好坏。

答案：时间空间（7）常见时间复杂性的量级有：常数阶O（___________）、对数阶O（___________）、线性阶O（___________）、线性对数阶O（___________）、平方阶O（___________）、和指数阶O（___________）。

通常认为，当问题规模较大时，具有（___________）量级的算法是不可计算的。

答案：1 log n n n log n n2 2n指数（8）STL提供的标准容器有顺序容器、（___________）和（___________）。

答案：排序容器哈希容器（9）算法可认为是STL的精髓，所有算法都是采用（___________）的形式提供的。

习题1.1选择题1、数据结构是一门研究计算机解决实际问题中（ A ）以及它们之间的（ B ）和运算等的学科。

(1)A、数据元素 B、计算方法 C、逻辑存储 D、数据映像(2)A、结构 B、关系 C、运算 D、算法2、数据结构可以用二元组来表示，它包括（ A ）集合K和K上的（ C ）集合R。

A、数据元素B、存储结构C、元素之间的关系D、逻辑结构3、数据结构在计算机内存中的表示是指（ A ）。

A、数据的存储结构B、数据结构C、数据的逻辑结构D、数据元素之间的关系4、在数据结构中，与所使用的计算机无关的是数据的（ A ）结构。

A、逻辑B、存储C、逻辑和存储D、物理5、以下说法中正确的是（ D ）。

A、数据元素是数据的最小单位B、数据项是数据的基本单位C、数据结构是带结构的各数据项的集合D、一些表面上很不相同的数据可以有相同的逻辑结构1.2 填空题1、线性结构中元素之间存在（一对一）关系，树型结构中元素之间存在（一对多）关系，图型结构中元素之间存在（多对多）关系。

2、数据结构是研究数据的（逻辑结构）和（存储结构）以及它们之间的相互关系，并对这种结构定义相应的操作，设计出相应的（算法），而确保经过这些运算后所得到的新结构是原来的结构类型。

3、一个算法的时间复杂度是该算法包含的（简单操作次数）的多少，它是一个算法运行时间的（相对量度），一个算法的空间复杂度是指该算法在运行过程中临时占用的（存储空间）的大小。

4、一个算法的时间复杂度通常用问题规模的（最高数量级）形式表示，当一个算法的时间复杂度与问题的n大小无关时，则表示为（O（1））；成正比时，表示为（O（n）），成平方时，则表示为（O（n2））。

5、数据结构、数据元素和数据项在计算机中的映射（或表示）分别称为存储结构、结点和数据域。

这句话是（正确）。

（填写正确或错误）1.3 应用题1、给定的两个数据结构如图1-1所示，回答以下问题：(a)图1-1 用图形表示法表示的两种数据结构(1) 用二元组表示法给出该数据结构的逻辑结构？(2)判断属于哪一种逻辑结构？ 解：(a) D1=（K ，R ），其中： K={1,2,3,4,5,6} R={r}r={<1,2>,<2,3>,<3,4>,<4,5>,<5,6>} 线性结构 （b ）D2=（K ，R ），其中： K={a,b,c,d,e,f,g,h,i} R={r}r={<a,b>,<a,c>,<c,d>,<c,e>,<d,f>,<d,g>,<e,g>,<e,h>,<g,i>}图型结构 2、对下列几种用二元组表示的数据结构，画出对应的逻辑结构图形表示，并指出属于哪一种结构。

数据结构1 3章相关测试题（含答案）数据结构1-3章相关测试题（含答案）《数据结构》第1教学单元测试练习题一、挑选（60分后）1、以下说法正确的是()a、数据元素就是数据的最轻单位b、数据项就是数据的基本单位c、数据结构是带有结构的各数据项的集合d、数据结构是带有结构的数据元素的集合2、对顺序表上的插入、删除算法的时间复杂性分析来说，通常以（）为标准操作a、条件判断b、结点移动c、算术表达式d、赋值语句3、对于顺序表的优缺点，以下说法错误的是（）a、无须为则表示结点间的逻辑关系而减少额外的存储空间b、可以便利地随机存取表的任一结点c、填入和删掉运算较便利d、难导致一部分空间长期闲置而不能获得充分利用4、链表不具有的特点是：a、可以随机出访任一个元素b、填入删掉不须要移动元素c、不必事先估算存储空间d、所须要空间与线性表长度成正比5、循环链表主要优点就是（）a、不再需要头指针了b、已知某个结点的位置后，能够容易找到它的直接前趋c、从表中任一结点出发都能扫描到整个链表d、在进行插入、删除运算时，能更好地保证链表不断开6、以下说法正确的是a、线性结构的基本特征就是：每个结点存有且仅有一个轻易前渐趋和一个轻易后继b、线性表的各种基本运算在顺序存储结构上的实现均比在链式存储结构上的实现效率要低c、在线性表的顺序存储结构中，插入和删除元素时，移动元素的个数与该元素位置有关d、顺序存储的线性表的填入和删掉操作方式不须要代价非常大的代价，因为平均值每次操作方式只有近一半的元素须要移动7、以下观点错误的就是（）a、求表长、定位这二种运算在采用顺序存储结构时实现的效率不比采用链式存储结构时实现的效率低b、顺序存储的线性表可以随机存取c、由于顺序存储建议已连续约存储区域所以在存储管理上比较有效率d、线性表的链式存储结构强于顺序存储结构8、以下观点错误的就是（）a、线性表的元素可以是各种各样的，逻辑上相邻的元素在物理位置上不一定相邻b、在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上不一定相邻c、在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻d、线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素9、以下说法正确的是（）a、在单链表，任何两个元素的存储边线之间都存有紧固的联系，因为可以三步结点展开搜寻任何一个元素b、在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构c、顺序存储方式只能用于存储线性结构d、顺序存储方式的优点就是存储密度小、且填入、删掉运算效率高10、线性表l=(a1,a2,...,ai,...,an),以下观点恰当的就是()a、每个元素都存有一个轻易前驱和轻易后继b、线性表中至少必须存有一个元素c、表中诸元素的排列顺序必须是由小到大或由大到小的d、除第一个元素和最后一个元素外其余每个元素都存有一个数且仅有一个轻易前驱和轻易后继11、线性表若使用链表存储结构时，建议内存中需用存储单元的地址()a、必需是联系的b、部分地址必须是连续的c、一定是不连续的d、连续不连续都可以12、单链表中，增加头结点的目的是为了()a、并使单链表中至少存有一个结点b、标注表中结点中首结点的边线第1页共3页c、便利运算的同时实现d、表明单链集是线性表的链式存储同时实现13、率先垂范结点的单链表中head为觑的认定条件就是a、head==nullb、head->next==nullc、head->next==head14、空的单循环链表l的尾结点*p,满足a、p->next==nullb、p==nullc、p->next==ld、p==l15、算法的时间复杂度就是指（）a、继续执行算法程序所须要的时间b、算法继续执行过程中所须要的基本运算次数c、算法程序的长度d、算法程序中的指令条数16、算法的空间复杂度就是指（）a、执行算法程序所占的存储空间b、算法程序中的指令条数c、算法程序的长度d、算法执行过程中所需要的存储空间17、下列叙述中正确的是（）a、线性表就是线性结构b、栈和队列就是非线性结构c、线性链表就是非线性结构d、二叉树就是线性结构18、数据的存储结构就是指（）a、数据所占的存储空间量b、数据的逻辑结构在计算机中的表示c、数据在计算机中的顺序存储方式d、存储在外存中的数据19、下列属于线性数据结构的是()a、队列b、树c、图d、不确认20、单链表的每个结点中包括一个指针next，它指向该结点的后继结点。

第一章绪论一．填空题1.数据结构是一门研究非数值计算的程序设计问题中计算机的_____________ 以及它们之间的_________ 和操作等的学科。

2.数据结构包括数据的_____________ 结构、_____________ 结构和运算。

3.数据的物理结构被分为_________、________、__________和___________四种。

4.数据的逻辑结构是指数据元素之间的逻辑关系，根据数据元素之间关系的不同特性，逻辑结构通常有_______________ ，________________ ，________________ 和__________________四类基本结构。

5.一种抽象数据类型包括 ____________和_____________ 两个部分。

6.数据结构是指数据及其相互之间的______________。

当结点之间存在M 对N（M：N）的联系时，称这种结构为____________当结点之间存在1 对N（1：N）的联系时，称这种结构为____________。

7.数据结构被形式地定义为（D, R），其中D是___________ 的有限集合，R是D上的有限集合。

8. 数据的基本单位是________，它在计算机中是作为一个整体来处理的。

9.算法的特性有________，___________ ，____________ ，_______________ 和__________ 等五种特性。

10.通常从四个方面评价算法的质量：_________、_________、_________和_________。

11.算法的时间复杂度为(n3+n2log2n+14n)/n2，其数量级表示为________。

12.算法的效率可分为______________ 效率和__________________ 效率。

13.算法的时间复杂度为(3n3+2000n log2n+90)/n2，其数量级表示为________。

数据结构第一章考试题库(含答案)数据结构第一章考试题库(含答案)一、选择题1. 以下哪种数据结构是先进先出（FIFO）的？A. 栈B. 队列C. 链表D. 哈希表答案：B2. 在队列中，元素的插入操作称为什么？A. EnqueueB. DequeueC. PushD. Pop答案：A3. 哪种数据结构是一种不允许重复元素的集合？A. 栈B. 队列C. 链表D. 集合答案：D4. 以下哪种数据结构是后进先出（LIFO）的？A. 栈B. 队列C. 链表D. 哈希表答案：A5. 使用链表实现的栈或队列的时间复杂度是多少？A. O(1)B. O(n)C. O(log n)D. O(n^2)答案：A二、填空题1. 广度优先搜索（BFS）使用的数据结构是______。

答案：队列2. 深度优先搜索（DFS）使用的数据结构是______。

答案：栈3. 在二叉树中，每个节点最多有几个子节点？答案：24. 快速排序使用的分治策略是将数组分成几个子数组进行排序？答案：25. 哈希表的平均查找时间复杂度是多少？答案：O(1)三、简答题1. 请简要解释栈和队列的区别。

答案：栈是一种后进先出（LIFO）的数据结构，只能在栈顶进行插入和删除操作；队列是一种先进先出（FIFO）的数据结构，只能在队尾插入，在队头删除。

2. 请解释什么是链表。

答案：链表是一种动态数据结构，由一系列节点组成，每个节点包含数据和指向下一个节点的指针。

与数组不同，链表的节点在内存中可以不连续存储，通过指针来链接每个节点。

3. 请简述快速排序的思想和算法步骤。

答案：快速排序使用分治的思想，首先选择一个元素作为基准值，然后将数组划分为两个子数组，小于基准值的元素放在左侧，大于基准值的元素放在右侧。

然后对左右子数组递归地进行快速排序，直到排序完成。

4. 请解释什么是哈希表及其应用场景。

答案：哈希表是一种基于哈希函数进行查找的数据结构，通过将关键字映射到哈希表中的位置来实现高效的查找。

第1章绪论一、选择题1. 算法的计算量的大小称为计算的（）。

【北京邮电大学2000 二、3 （20/8分）】A．效率 B. 复杂性 C. 现实性 D. 难度2. 算法的时间复杂度取决于（）【中科院计算所1998 二、1 （2分）】A．问题的规模 B. 待处理数据的初态 C. A和B3.计算机算法指的是（1），它必须具备（2）这三个特性。

(1) A．计算方法 B. 排序方法 C. 解决问题的步骤序列 D. 调度方法(2) A．可执行性、可移植性、可扩充性 B. 可执行性、确定性、有穷性C. 确定性、有穷性、稳定性D. 易读性、稳定性、安全性【南京理工大学1999 一、1（2分）【武汉交通科技大学1996 一、1（4分）】4．一个算法应该是（）。

【中山大学1998 二、1（2分）】A．程序B．问题求解步骤的描述C．要满足五个基本特性D．A和C.5. 下面关于算法说法错误的是（）【南京理工大学2000 一、1（1.5分）】A．算法最终必须由计算机程序实现B. 为解决某问题的算法同为该问题编写的程序含义是相同的C. 算法的可行性是指指令不能有二义性D. 以上几个都是错误的6. 下面说法错误的是（）【南京理工大学2000 一、2 （1.5分）】(1）算法原地工作的含义是指不需要任何额外的辅助空间（2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界（4）同一个算法，实现语言的级别越高，执行效率就越低A．(1) B.(1),(2) C.(1),(4) D.(3)7．从逻辑上可以把数据结构分为（）两大类。

【武汉交通科技大学1996 一、4（2分）】A．动态结构、静态结构B．顺序结构、链式结构C．线性结构、非线性结构D．初等结构、构造型结构8．以下与数据的存储结构无关的术语是（）。

【北方交通大学2000 二、1（2分）】A．循环队列 B. 链表 C. 哈希表 D. 栈9．以下数据结构中，哪一个是线性结构（）？【北方交通大学2001 一、1（2分）】A．广义表 B. 二叉树 C. 稀疏矩阵 D. 串10．以下那一个术语与数据的存储结构无关？（）【北方交通大学2001 一、2（2分）】A．栈 B. 哈希表 C. 线索树 D. 双向链表11．在下面的程序段中，对x的赋值语句的频度为（）【北京工商大学2001 一、10（3分）】FOR i:=1 TO n DOFOR j:=1 TO n DOx:=x+1;A．O(2n) B．O(n) C．O(n2) D．O (log2n)12．程序段FOR i:=n-1 DOWNTO 1 DOFOR j:=1 TO i DOIF A[j]>A[j+1]THEN A[j]与A[j+1]对换；其中n为正整数，则最后一行的语句频度在最坏情况下是（）A. O（n）B. O(nlogn)C. O(n3)D. O(n2) 【南京理工大学1998一、1(2分)】13．以下哪个数据结构不是多型数据类型（）【中山大学1999 一、3（1分）】A．栈B．广义表C．有向图D．字符串14．以下数据结构中，（）是非线性数据结构【中山大学1999 一、4】A．树B．字符串C．队D．栈15. 下列数据中，（）是非线性数据结构。

习题知识点：数据结构的概念一、选择题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② 数据结构与数据类型有什么区别? 【哈尔滨工业大学2021】知识点：算法的概念一、选择题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<=n;i++）x++;时间复杂度为（C ）。

1.6 习题一、名词解释1.数据结构：相互之间存在一种或多种特定关系的数据元素的集合。

结构，就是数据之间的关系，即数据与数据之间的排列方式。

2.数据元素：是有一定意义数据的基本单位，可由若干个数据项组成，在计算机中通常作为整体处理，也可称为结点、记录。

如：在人类社会中，一个“人”是一个数据元素，是有一定意义的作为整体处理的基本单位，在社会关系里，一般都是拿某个人说事儿，不会拿某个人的胳膊或腿儿说事儿；但在医学结构上，人又由若干部分组成，比如四肢、心、肝、脾、肺、肾等。

3.数据项：是具有独立含义的最小标识单位。

如一个“人”有眼睛、耳朵、手等数据项，也可有姓名、年龄、性别等这些数据项。

一个记录可称为一个数据元素，而这个元素中的某一字段就是一个数据项。

4.逻辑结构有时也称数据结构，它是数据元素之间关系的描述，可以看作是从具体问题抽象出来的数学模型，与数据的存储无关，是独立于计算机的。

5.物理结构是数据的逻辑结构在计算机中的表示和实现，也称存储结构。

6.时间复杂度：当问题规模很大时，程序执行时间随问题规模增长程度的一个度量。

7.空间复杂度：是指程序运行从开始到结束所需的存储量。

二、判断题（1）数据元素是最小的项。

（×）（2）算法就是程序。

（×）（算法是解决问题的有限指令序列，它可以用某个具体的程序来表示，也可以用自然语言、流程图、伪代码表示。

即可以用程序来表达算法，但算法不见得就是程序。

目前，用来表达算法用得最多的是伪代码，因为伪代码比具体的程序要求宽松、易理解，同时又比自然语言更容易转换成可实现的程序。

）（3）数据结构是数据对象与对象中数据元素之间关系的集合。

（√）(4) 从逻辑关系上讲，数据结构主要分为两大类：线性结构和非线性结构。

(√ )(5) 数据的逻辑结构与数据元素本身的内容和形式无关。

(√ )三、填空题（1）算法的一个特性是确定性，即针对一组确定的输入，算法应始终得出一组确定的结果。

可编辑修改精选全文完整版第一章概论一、选择题1、研究数据结构就是研究（ D ）。

A. 数据的逻辑结构B. 数据的存储结构C. 数据的逻辑结构和存储结构D. 数据的逻辑结构、存储结构及其基本操作2、算法分析的两个主要方面是（ A ）。

A. 空间复杂度和时间复杂度B. 正确性和简单性C. 可读性和文档性D. 数据复杂性和程序复杂性3、具有线性结构的数据结构是（ D ）。

A. 图B. 树C. 广义表D. 栈4、计算机中的算法指的是解决某一个问题的有限运算序列.它必须具备输入、输出、（ B ）等5个特性。

A. 可执行性、可移植性和可扩充性B. 可执行性、有穷性和确定性C. 确定性、有穷性和稳定性D. 易读性、稳定性和确定性5、下面程序段的时间复杂度是（ C ）。

for(i=0;i<m;i++)for(j=0;j<n;j++)a[i][j]=i*j;A. O(m2)B. O(n2)C. O(m*n)D.O(m+n)6、算法是（ D ）。

A. 计算机程序B. 解决问题的计算方法C. 排序算法D. 解决问题的有限运算序列7、某算法的语句执行频度为（3n+nlog2n+n2+8）,其时间复杂度表示（ C ）。

A. O(n)B. O(nlog2n)C. O(n2)D.O(log2n)8、下面程序段的时间复杂度为（ C ）。

i=1;while(i<=n)i=i*3;A. O(n)B. O(3n)C. O(log3n)D. O(n3)9、数据结构是一门研究非数值计算的程序设计问题中计算机的数据元素以及它们之间的（）和运算等的学科。

A. 结构B. 关系C. 运算D. 算法10、下面程序段的时间复杂度是（A ）。

i=s=0;while(s<n){i++;s+=i;}A. O(n)B. O(n2)C. O(log2n)D. O(n3)11、抽象数据类型的三个组成部分分别为（ A）。

A. 数据对象、数据关系和基本操作B. 数据元素、逻辑结构和存储结构C. 数据项、数据元素和数据类型D. 数据元素、数据结构和数据类型12、通常从正确性、易读性、健壮性、高效性等4个方面评价算法的质量.以下解释错误的是（）。

第1章绪论一、填空题01、【操作对象】【关系和运算】02、【数据元素】【关系】03、【逻辑结构】【存储结构】【运算】04、【线性结构】【非线性结构】05、【一对一】【一对多】【多对多】06、【没有】【没有】07、【前驱】【1】【后续】【任意多个】08、【任意多个】09、【顺序】【链式】【索引】【散列】10、【集合】【线性结构】【树形结构】【图状结构】11、【插入】【删除】【修改】【查找】【排序】12、【时间】【空间】13、【时间复杂度】【空间复杂度】14、【映射】15、【有穷性】【确定性】【可行性】16、【n+1】【n】【n(n+3)/2】【n(n+1)/2】17、【n(n+1)(n+2)/6】【O(n3)】18、【O(n2 log)】19、【O(nn2 log)】20、【O(22log n)】21、【(n+3)(n-2)/2】22、【n(n-1)/2】二、判断题01-05、×××√×06-10、×√×××11-12、√×三、单项选择题B01 BD02 A03 C04 C05A06 C07 B08 A09 C10B11 A12 C13 D14 A15C16四、分析下面各程序段的时间复杂度01、O（nm ）02、O（2n）03、答：O（2n）04、答：O（n3 log）五、设有数据逻辑结构S=(D,R)，试按各小题所给条件画出这些逻辑结构的图示，并确定相对于关系R，哪些结点是开始结点，哪些结点是终端结点？01、此图为线性结构d1→d2→d3→d4d1—无直接前驱，是首结点d4—无直接后继是尾结点02、此图为树形结构d1—无直接前驱，是根结点d2,d5,d7,d9—无直接后继是叶子结点03、此图为图形结构d1，d2—无直接前驱，是开始结点d6,d7—无直接后继是终端结点六、简述题01、什么是数据结构?答：数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和运算等的学科。

第1章绪论答案二、判断题三．填空题1．数据元素数据元素间关系 2．集合线性结构树形结构图状结构或网状结构。

3．数据的组织形式，即数据元素之间逻辑关系的总体。

而逻辑关系是指数据元素之间的关联方式或称“邻接关系”。

4．表示（又称映像）。

5．（1）逻辑特性（2）在计算机内部如何表示和实现（3）数学特性。

6．算法的时间复杂度和空间复杂度。

7．（1）逻辑结构（2）物理结构（3）操作（运算）（4）算法。

8．（1）有穷性（2）确定性（3）可行性。

9．（1）n+1 （2）n （3）n(n+3)/2 （4）n(n+1)/2。

10．1+（1+2++（1+2+3）+…+（1+2+…+n）=n(n+1)(n+2)/6 O(n3)11. log2n 12. nlog2n 13. log2n2 14. (n+3)(n-2)/2 15. O(n)16.① (1)1 (2)1 (3)f(m,n-1) (4)n ② 9 17. n(n-1)/2四．应用题1．数据结构是一门研究在非数值计算的程序设计问题中，计算机的操作对象及对象间的关系和施加于对象的操作等的学科。

2．四种表示方法（1）顺序存储方式。

数据元素顺序存放，每个存储结点只含一个元素。

存储位置反映数据元素间的逻辑关系。

存储密度大，但有些操作（如插入、删除）效率较差。

（2）链式存储方式。

每个存储结点除包含数据元素信息外还包含一组（至少一个）指针。

指针反映数据元素间的逻辑关系。

这种方式不要求存储空间连续，便于动态操作（如插入、删除等），但存储空间开销大（用于指针），另外不能折半查找等。

（3）索引存储方式。

除数据元素存储在一地址连续的内存空间外，尚需建立一个索引表，索引表中索引指示存储结点的存储位置（下标）或存储区间端点（下标），兼有静态和动态特性。

（4）散列存储方式。

通过散列函数和解决冲突的方法，将关键字散列在连续的有限的地址空间内，并将散列函数的值解释成关键字所在元素的存储地址，这种存储方式称为散列存储。

数据结构试题库及答案第一章概论一、选择题1、研究数据结构就是研究（ D ）。

A. 数据的逻辑结构B. 数据的存储结构C. 数据的逻辑结构和存储结构D. 数据的逻辑结构、存储结构及其基本操作2、算法分析的两个主要方面是（ A ）。

A. 空间复杂度和时间复杂度B. 正确性和简单性C. 可读性和文档性D. 数据复杂性和程序复杂性3、具有线性结构的数据结构是（ D ）。

A. 图B. 树C. 广义表D. 栈4、计算机中的算法指的是解决某一个问题的有限运算序列，它必须具备输入、输出、（ B ）等5个特性。

A. 可执行性、可移植性和可扩充性B. 可执行性、有穷性和确定性C. 确定性、有穷性和稳定性D. 易读性、稳定性和确定性5、下面程序段的时间复杂度是（ C ）。

for(i=0;i<m;i++)for(j=0;j<n;j++)a[i][j]=i*j;A. O(m2)B. O(n2)C. O(m*n)D. O(m+n)6、算法是（ D ）。

A. 计算机程序B. 解决问题的计算方法C. 排序算法D. 解决问题的有限运算序列7、某算法的语句执行频度为（3n+nlog2n+n2+8）,其时间复杂度表示（ C ）。

A. O(n)B. O(nlog2n)C. O(n2)D. O(log2n)8、下面程序段的时间复杂度为（ C ）。

i=1;while(i<=n)i=i*3;A. O(n)B. O(3n)C. O(log3n)D. O(n3)9、数据结构是一门研究非数值计算的程序设计问题中计算机的数据元素以及它们之间的（）和运算等的学科。

A. 结构B. 关系C. 运算D. 算法10、下面程序段的时间复杂度是（）。

i=s=0;while(s<n){i++;s+=i;}A. O(n)B. O(n2)C. O(log2n)D. O(n3)11、抽象数据类型的三个组成部分分别为（）。

A. 数据对象、数据关系和基本操作B. 数据元素、逻辑结构和存储结构C. 数据项、数据元素和数据类型D. 数据元素、数据结构和数据类型12、通常从正确性、易读性、健壮性、高效性等4个方面评价算法的质量，以下解释错误的是（）。

第一章绪论
1、简述下列术语：数据、数据元素、数据对象、数据结构、数据存储、存储结构、数据类型和抽象数据类型。

2、数据的逻辑结构分为线性结构和非线性结构两大类。

线性结构包括数组、链表、栈、队列、优先级队列等; 非线性结构包括树、图等、这两类结构各自的特点是什么？
3、什么是算法? 算法的5个特性是什么? 试根据这些特性解释算法与程序的区别。

4、什么叫算法的时间复杂度？怎样表示算法的时间复杂度？
5、两个数据结构的逻辑结构和存储结构都相同，但是它们的运算集合中有一个运算的定义不一样，它们是否可以认作是同一个数据结构？为什么？
6、试画出与下列程序段等价的框图
(1)product = 1; i = 1;
while(i <= n){
product * = i ;
i++;
}
(2)i = 0;
do{
i++;
}while ((i!=n)&&(a[i])!=x);
7、已知如下程序段
for(i=n;n>=1;n--) {语句1}
{
x++； {语句2}
for(j=n;j<=i;j--)FOR j:=n {语句3}
y++; {语句4}
}；
求语句１到语句４的频度。

8、按增长率从小到大的顺序排列下列各组函数：
(5) int i, j, k, x = 0;
for (i = 0; i < n; i++) for (j = 0; j < i; j++) for (k = 0; k < j; k++)
x = x + 2;。

第一章概论自测题答案一、填空题1. 数据结构被形式地定义为（D, R），其中D是数据元素的有限集合，R是D上的关系有限集合。

2. 数据结构包括数据的逻辑结构、数据的存储结构和数据的运算这三个方面的内容。

3. 数据结构按逻辑结构可分为两大类，它们分别是线性结构和非线性结构。

4. 线性结构中元素之间存在一对一关系，树形结构中元素之间存在一对多关系，图形结构中元素之间存在多对多关系。

5．在线性结构中，第一个结点没有前驱结点，其余每个结点有且只有1个前驱结点；最后一个结点没有后续结点，其余每个结点有且只有1个后续结点。

6. 在树形结构中，树根结点没有前驱结点，其余每个结点有且只有1个前驱结点；叶子结点没有后续结点，其余每个结点的后续结点数可以任意多个。

7. 在图形结构中，每个结点的前驱结点数和后续结点数可以任意多个。

8．数据的存储结构可用四种基本的存储方法表示，它们分别是顺序、链式、索引和散列。

9. 数据的运算最常用的有5种，它们分别是插入、删除、修改、查找、排序。

10. 一个算法的效率可分为时间效率和空间效率。

11.任何一个C程序都由一个主函数和若干个被调用的其它函数组成。

二、单项选择题（B）1. 非线性结构是数据元素之间存在一种：A）一对多关系B）多对多关系C）多对一关系D）一对一关系（ C ）2. 数据结构中，与所使用的计算机无关的是数据的结构；A) 存储B) 物理C) 逻辑D) 物理和存储（C）3. 算法分析的目的是：A) 找出数据结构的合理性B) 研究算法中的输入和输出的关系C) 分析算法的效率以求改进D) 分析算法的易懂性和文档性（A）4. 算法分析的两个主要方面是：A) 空间复杂性和时间复杂性B) 正确性和简明性C) 可读性和文档性D) 数据复杂性和程序复杂性（ C ）5. 计算机算法指的是：A) 计算方法B) 排序方法C) 解决问题的有限运算序列D) 调度方法（B）6. 计算机算法必须具备输入、输出和等5个特性。

说明：此复习题为复习专用，其给定了期末考试的主要范围，并非给定考试原题，考试时相关的题目基本都要进行改动。

因此同学们请注意，不要去背答案，要将题理解并做会。

（请注意这决不是原题，只有弄会才可能通过）第1章绪论※1、数据结构主要研究的三个内容为、以及定义在该结构上的。

2、数据结构从逻辑结构上可分为线性结构与非线性结构，其中树、图属于。

3、数据结构被形式地定义为（D，R），其中D是的有限集，R是D上的有限集。

4、数据的结构在计算机内存中的表示是指（）A.数据的存储结构B.数据结构C.数据的逻辑结构D.数据元素之间的关系※5、给出以下给定的两个程序段中划波浪线的语句的执行频度（次数）。

（1）sum=0;for(i=0;i<n;i++)for(j=0; j<n; j++) sum+=a[i][j];（2）sum=0;for(i=0;i<n;i++)for(j=0; j<=i; j++) sum+=a[i][j];(3) sum=0;for(i=0;i<n;i++)for(j=0; j<m; j++) sum+=a[i][j];※6、分析以下各程序段的时间复杂度为（用大O记号表示）（1）i=s=0;while(s<n){ i++;s+=i;}（2）i=1;while(i<=n)i=i*3;第2章线性表1、n(n>=0)个元素的线性结构表示成(a1，a2,……a n)，a1称为______元素，a n称为______元素，i称为a i在线性表中的____________。

对任意一对相邻结点a i、a i+1(1<=i<n),a i称为a i+1的______，a i+1称为a i的______。

2、在表长为n的顺序表的第i个位置插入一元素（1<=i<=n+1，插入的新元素作为第i个元素），则涉及到的元素的移动次数为；若删除第i（1<=i<=n）个元素，则涉及到的元素的移动次数为。