数据结构练习题及答案.doc

第1章 绪论一、 判断题1. 数据的逻辑结构与数据元素本身的内容和形式无关 （√）2. 一个数据结构是由一个逻辑结构和这个逻辑结构上的一个基本运算集构成的整体 （√）3. 数据元素是数据的最小单位 （×）4. 数据的逻辑结构和数据的存储结构是相同的 （×）5. 程序和算法原则上没有区别，所以在讨论数据结构时可以通用 （×）6. 从逻辑关系上讲，数据结构主要分为线性结构和非线性结构两类 （√）7. 数据的存储结构是数据的逻辑结构的存储映象 （√）8. 数据的物理结构是指数据在计算机内实际的存储形式 （√）9. 数据的逻辑结构是依赖于计算机的 （×）10. 算法是对解题方法和步骤的描述。

（√）二、填空题1. 数据有逻辑结构和 存储结构 两种结构2. 数据逻辑结构除了集合以外，还包括线性结构、树形结构和图形结构 3. 数据结构按逻辑结构可分为两大类，它们是线性结构和非线性结构 4. 树形结构 和图形结构 合称为非线性结构5. 在树形结构中，除了树根结点以外，其余每个结点只有1个前驱结点6. 在图形结构中，每个结点的前驱结点数和后继结点数可以任意多个 7. 数据的存储结构又叫物理结构 8. 数据的存储结构形式包括顺序存储、链式存储、索引存储和散列存储 9. 线性结构中的元素之间存在一对一 的关系10. 树形结构中的元素之间存在一对多 的关系11. 图形结构的元素之间存在多对多 的关系12. 数据结构主要研究数据的逻辑结构、存储结构和算法（或运算） 3个方面的内容13. 数据结构被定义为（D，R），其中D是数据的有限集合，R是D上的关系 有限集合14. 算法是一个有穷指令 的集合15. 算法效率的度量可以分为事先估算法和事后统计法 。

16. 一个算法的时间复杂度是算法 输入规模 的函数17. 算法的空间复杂度是指该算法所耗费的存储空间 ，它是该算法求解问题规模的n的函数18. 若一个算法中的语句频度之和为T(n)=6n+3nlog2n,则算法的时间复杂度为O（ nlog2n） 19. 若一个算法的语句频度之和为T(n)=3n+nlog2+n2,则算法的时间复杂度为O（n2） 20. 数据结构是一门研究非数值计算的程序问题中计算机的操作对象，以及它们之间的关系和运算的学科三、选择题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．分两部分，一部分存放结点的值，另一个部分存放表示结点间关系的指针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. 以下任何两个结点之间都没有逻辑关系的是（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．易读性 C．健壮性 D．高效性16. 算法在发生非法操作时可以作出相应处理的特性称为算法的（C）A．正确性 B．易读性 C．健壮性 D．高效性17. 下列时间复杂度中最坏的是（D）。

A．O（1） B.O（n） C.O( log2n) D.O(n2)18. 下列算法的时间复杂度是（D）for(i=0;i

（√）4. 顺序存储方式的优点是存储密度大，插入、删除效率高 （×）5. 线性链表的删除算法简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向前移动 （×）6. 顺序表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型 （×）7. 线性表链式存储的特点是可以用一组任意的存储单元存储表中的数据元素 （√）8. 线性表采用顺序存储，必须占用一片连续的存储单元 （√）9. 顺序表结构适宜进行顺序存取，而链表适宜进行随机存取 （×）10. 插入和删除操作是数据结构中是最基本的两种操作，所以这两种操作在数组中也经常使用×）二、填空题1. 顺序表中逻辑上相邻的元素在物理位置上必须相邻2. 线性表中结点的集合是有限的，结点间的关系是一对一关系3. 顺序表相对于链表的优点是节省存储和随机存取4. 链表相对于顺序表的优点是插入、删除方便。

5. 当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快速度存取线性表中的元素时，应采用 顺序 存储结构6. 顺序表中访问任意一个结点的时间复杂度均为O（1）7. 链表相对于顺序表的优点是插入、删除方便；缺点是存储密度小8. 在双向链表中要删除已知结点*P，其时间复杂度为O（1）9. 在单向链表中要在已知结点*P之前插入一个新结点，需找到*P的直接前驱结点的地址，其查找的时间复杂度为O(n)10. 在单向链表中需知道头指针才能遍历整个链表11. 线性表中第一个结点没有直接前驱，称为开始结点12. 在一个长度为n的顺序表中删除第i个元素，要移动 n-i 个元素13. 在一个长度为n的顺序表中，如果要在第i个元素前插入一个元素，要后移 n-i+1 个元素14. 在无头结点的单向链表中，第一个结点的地址存放在头指针中，而其他结点的存储地址存放在 前趋 结点的指针域中15. 线性表的元素总数不确定，且经常需要进行插入和删除操作，应采用 链子 存储结构16. 性表中的链式存储中，元素之间的逻辑关系是通过 指针 决定。

17. 在双向链表中，每个结点都有两个指针域，它们一个指向其 前趋 结点，另一个指向其后继结点18. 对一个需要经常进行插入和删除操作的线性表，采用 链式 存储结构为宜19. 双向链表中，设P是指向其中待删除的结点，则需要执行的操作为p->prior->next=p->next；p->next->prior=p->prior 20. 在如图所示的链表中，若在指针P所在的结点之后插入数据域值为a和b的两个结点，则可用语句S->next->next=p->next和P-> next=S；来实现该操作 p ∧ 。