数据结构复习习题和答案.doc

《数据结构复习习题和答案.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第一章绪论一、单项选择题1．数据结构是一门研究非数值计算的程序设计问题中计算机的①以及它们之间的②和操作等的学科。①A.操作对象B．计算方法C·逻辑存储D.数据映象②A.结构B．关系C．运算．D.算法2．数据结构被形式地定义为（D，R），其中D是①的有限集合，R是D上的②有限集合。①A.算法B.数据元素C．数据操作D．逻辑结构②A.操作B.映象C、存储D.关系3．在数据结构中，从逻辑上可以把数据结构分成（）。A.动态结构和静态结构B．紧凑结构和非紧凑结构C.线性结构和非线性结构D．内部结构和外部结构4·算

2、法分析的目的是①，算法分析的两个主要方面是②。①A.找出数据结构的合理性B．研究算法中的输入和输出的关系C.分析算法的效率以求改进D.分析算法的易懂性和文档性②A.空间复杂性和时间复杂性B．正确性和简明性C．可读性和文档性D．数据复杂性和程序复杂性5．计算机算法指的是①，它必具备输入、输出和②等五个特性。①A.计算方法B．排序方法C.解决问题的有限运算序列D．调度方法②A.可行性、可移植性和可扩充性B.可行性、确定性和有穷性C.确定性、有穷性和稳定性D．易读性、稳定性和安全性6.线性表的逻辑顺序与存储顺序

3、总是一致的，这种说法（）。A.正确B．不正确7.线性表若采用链式存储结构时，要求内存中可用存储单元的地址（）。A.必须是连续的B．部分地址必须是连续的C.一定是不连续的D.连续或不连续都可以8．数据结构通常是研究数据的（）及它们之间的相互联系。A．存储和逻辑结构B．存储和抽象C．理想与抽象D．理想与逻辑9．数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为（）。A．存储结构B．逻辑结构C．顺序存储结构D．链式存储结构11．非线性结构是数据元素之间存在一种（）。A．一对多关系B．多对多关

4、系C．多对一关系D．一对一关系12．非线性结构中，每个结点（）。A．无直接前趋B．只有一个直接前驱和后继C．只有一个直接前趋和个数受限制的直接后继D．有个数不受限制的直接前趋和后继13．除了考虑存储数据结构本身所占用的空间外，实现算法所用辅助空间的多少称为（）。A．时间效率B．空间效率C．硬件效率D．软件效率14．链式存储的存储结构所占存储空间（）。A．分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针B．只有一部分，存放结点值C．只有一部分，存储表示结点间关系的指针D．分两部分，一部分存放结点

5、值，另一部分存放结点所占单元数15．设语句x＋十的时间是单位时间，则语句：for（i＝l；i＜＝n；i＋＋）X＋＋；的时间复杂度为（）。A．O（l）B．O（n）C．O（n2）D．O（n3）一、填空题1．数据元素之间的关系称为（结构），通常分为4种（集合）（线性结构）（树形结构）（图状结构或网状结构）。2．在线性结构中，第一个结点（无）前驱结点，其余每个结点有且只有（1）个前驱结点；最后一个结点（无）后续结点，其余每个结点有且只有（1）个后续结点。3．在树形结构中，树根结点没有（前驱）结点，其余每个结点有且

6、只有（1）个前驱结点；叶子结点没有（后继）结点，其余每个结点的后继结点可以（多个）。4．在图形结构中，每个结点的前驱结点数和后续结点数可以（多个）。5．线性结构中元素之间存在（一对一）关系，树形结构中元素之间存在（一对多）关系，图形结构中元素之间存在（多对多）关系。6．下面程序段的时间复杂度是（O(mn)）。for（i＝0；i

7、（非线性结构）。9．数据的存储结构分为（顺序存储结构）和（链式存储结构）。10．一个算法的效率可分为（时间）效率和（空间）效率。11.数据元素是数据的（基本）单位，（数据项）是数据的最小单位。12．数据对象是（性质）相同数据元素的集合。三、阅读理解题设n为正整数，利用大“O”记号，将下列程序段的执行时间表示为n的函数。x＝0；for(i=l;i＜n;i＋＋)for（j=i+1;j＜＝n;j＋＋）x++;答案：n(n+1)/2,即O(n2)第2章线性表一、单项选择题：1．线性表的的顺序存储结构是一种()的存

8、储结构，线性表的链式存储结构是一种（）的存储结构。A·随机存取B.顺序存取C．索引存取D．散列存取2．在以下的叙述中，正确的是()。A.线性表的顺序存储结构优于链表存储结构B．二维数组是其数据元素为线性表的线性表C．栈的操作方式是先进先出D.队列的操作方式是先进后出3．不带头结点的单链表head为空的判定条件是()。A.head==NULLB．head－＞next==NULLC．head－＞next==headD．head！=