《数据结构习题.doc》由会员分享，可在线阅读，更多相关《数据结构习题.doc（43页珍藏版）》请在迅下文库上搜索。
1、. .第1章 绪论一、 判断题1. 数据的逻辑构造与数据元素本身的容和形式无关。 2. 一个数据构造是由一个逻辑构造和这个逻辑构造上的一个根本运算集构成的整体。3. 数据元素是数据的最小单位。 4. 数据的逻辑构造和数据的存储构造是一样的。 5. 程序和算法原那么上没有区别，所以在讨论数据构造时可以通用。 6. 从逻辑关系上讲数据结构习题.doc，数据构造主要分为线性构造和非线性构造两类。 7. 数据的存储构造是数据的逻辑构造的存储映象。 8. 数据的物理构造是指数据在计算机实际的存储形式。 9. 数据的逻辑构造是依赖于计算机的。 10. 算法是对解题方法和步骤的描述。 二、填空题1. 数据有逻辑构造和存储构造两
2、种构造。2. 数据逻辑构造除了集合以外，还包括线性构造、树形构造和图形构造。3. 数据构造按逻辑构造可分为两大类，它们是线性构造和非线性构造。4. 树形构造和图形构造合称为非线性构造。5. 在树形构造中，除了树根结点以外，其余每个结点只有1个前驱结点。6. 在图形构造中，每个结点的前驱结点数和后继结点数可以任意多个。7. 数据的存储构造又叫物理构造。8. 数据的存储构造形式包括顺序存储、链式存储、索引存储和散列存储。9. 线性构造中的元素之间存在一对一的关系。10. 树形构造中的元素之间存在一对多的关系。11. 图形构造的元素之间存在多对多的关系。12. 数据构造主要研究数据的逻辑构造、存储构
3、造和算法或运算3个方面的容。13. 数据构造被定义为D，R，其中D是数据的有限集合数据结构习题，R是D上的关系有限集合。14. 算法是一个有穷指令的集合。15. 算法效率的度量可以分为事先估算法和事后统计法。16. 一个算法的时间复杂度是算法输入规模的函数。17. 算法的空间复杂度是指该算法所消耗的存储空间，它是该算法求解问题规模的n的函数。18. 假设一个算法中的语句频度之和为T(n)=6n+,那么算法的时间复杂度为O 。19. 假设一个算法的语句频度之和为T(n)=3n+nlog2+n2,那么算法的时间复杂度为On2。20. 数据构造是一门研究非数值计算的程序问题中计算机的操
4、作对象，以及它们之间的关系和运算的学科。三、选择题1. 数据构造通常是研究数据的A及它们之间的相互关系。A存储构造和逻辑构造B存储和抽象 C联系和抽象 D联系与逻辑2. 在逻辑上可以把数据构造分成C。A动态构造和静态构造 B紧凑构造和非紧凑构造C线性构造和非线性构造D部构造和外部构造。3. 数据在计算机存储表示时，物理地址和逻辑地址一样并且是连续的，称之为C。A存储构造 B逻辑构造 C顺序存储构造 D链式存储构造4. 非线性构造中的每个结点D。A无直接前驱结点B无直接后继结点C只有一个直接前驱结点和一个直接后继结点D可能有多个直接前驱结点和多个直接后继结点5. 链式存储构造所占存储空间A。A分
5、两局部，一局部存放结点的值，另一个局部存放表示结点间关系的指针。B只有一局部，存放结点的值。 C只有一局部，存储表示结点间关系的指针。D分两局部，一局部存放结点的值，另一局部存放结点所占单元素6. 算法的计算量大小称为算法的C。A现实性 B难度 C时间复杂性 D效率7. 数据的根本单位B。A数据构造 B数据元素 C数据项 D文件8. 每个结点只含有一个数据元素，所有存储结点相继存放在一个连续的存储空间里数据结构习题，这种存储构造称为A构造。A顺序构造B链式构造C索引构造 D散列构造9. 每一个存储结点不仅含有一个数据元素，还包含一组指针，该存储方式是B。A顺序B链式 C索引 D散列10. 以下任何两个结点
6、之间都没有逻辑关系的是D。A图形构造 B线性构造 C树形构造 D集合11. 在数据构造中，与所使用的计算机无关的是C。A物理构造 B存储构造C逻辑构造 D逻辑和存储构造12. 以下4种根本逻辑构造中，数据元素之间关系最弱的是A。A集合 B线性构造 C树形构造D图形构造13. 与数据元素本身的形式、容、相对位置、个数无关的是数据的A。A逻辑构造 B存储构造 C逻辑实现 D存储实现14. 每一个存储结点只含有一个数据元素，存储结点存放在连续的存储空间，另外有一组指明结点存储位置的表，该存储方式是C存储方式。A顺序B链式 C索引 D散列 15. 算法能正确的实现预定功能的特性称为算法的A。A正确性B
7、易读性C强健性D高效性16. 算法在发生非法操作时可以作出相应处理的特性称为算法的C。A正确性B易读性C强健性D高效性17. 以下时间复杂度中最坏的是D。AO1B.OnC.O( log2n)D.O(n2)18. 以下算法的时间复杂度是D。for(i=0;in;i+)for(j=o;-next=p-next；p-next-prior=p-. 在如下列图的链表中，假设在指针P所在的结点之后插入数据域值为a和b的两个结点，那么可用语句S-next-next=p-next和P- next=S；来实现该操作。 p a b s三、 选择题1. 在具有n个结点的单向链表中，实现 A
8、的操作，其算法的时间复杂度都是O(n). A.遍历链表或求链表的第i个结点B.在地址为P的结点之后插入一个结点C.删除开场结点 D.删除地址为P的结点的后继结点2. 设a、b、c为3个结点，p、10、20分别代表它们的地址，那么如下的存储构造称为 B 。 p a 10 b 20 c A循环链表 B单向链表 C双向循环链表 D双向链表3. 单向链表的存储密度 C 。A.大于1B.等于1C.小于1D.不能确定4. 一个顺序存储的线性表，设每个结点占m个存储单元，假设第一个结点的地址为B，那么第i个结点的地址为 A 。A.B+(i-1)m B.B+im C.B-im D.B+(i+1)m5. 在有n个结点的顺序表上做插入、删除结点运算的时间复杂度为 B 。AO1 B.On C. O(n2) D.O( log2n)6. 设f