1.数据结构与算法练习题及详解

1、数据结构与算法1. 关于算法的描述，以下选项中正确的是A、以上三种描述都不对B、算法的空间复杂度是指算法程序中指令（或语句）的条数 C、算法的有穷性是指算法必须能在执行有限个步骤之后终止D、算法的执行效率与数据的结构无关2. 以下选项中不属于线性数据结构的是A、线性表 B、栈C、队列 D、二叉树3. 某棵二叉树上第五层的最大节点数是A、15 B、32C、8 D、164. 以下选项中描述正确的是A、线性表是线性结构 B、树是线性结构C、线性链表是非线性结构 D、栈与队列是非线性结构5. 设一颗完全二叉树共有 699 个结点，则该节点的叶子结点数是A、349 B、255 C、351 D、3506.

2、 关于算法的空间复杂度，以下选项中描述正确的是A、算法执行过程中所需要的空间B、算法程序所占的 C、算法程序的长度空间D、算法程序中的指令条数7. 关于栈的描述，以下选项中能够正确的是A、在栈中只能数据B、在栈中只能删除数据 C、栈是先进后出的线性表 D、栈是先进先出的线性表8. 在数据结构中，从逻辑上可以把数据结构分成A、线性结构和非线性结构 B、动态结构和静态结构C、结构和外部结构D、紧凑结构和非紧凑结构9. 关于算法的控制结构组合，以下描述正确的是A、顺序，选择，循环 B、循环，分支，递归 C、顺序，循环，嵌套 D、循环，递归，选择10. 设有一个已按各元素的值排好序的线性表（长度大于

3、2），对给定的值 k，分别用顺序查找法和二分查找法查找，比较的次数分别是 s 和 b，在查找不成功的情况下，s 和 b 的关系是A、sb B、sb C、s=b D、sb。A、算法的长度是有限的B、算法程序的运行时间是有限的 C、算法只能被有限的用户使用D、算法程序所处理的数据量是有限的30. 下列数据结构中，能够按照“先进后出”原则存取数据的是A、二叉树 B、队列C、循环队列 D、栈11. C算法的基本特征，具体如下：1、确定性：每一步指令必须有确定的含义。不可存在二义性，且算法只有一个出口；2、有穷性：是指算法有有穷个步骤，并且执行需有穷时间；和3、可行性：算法原则上能够精确地运行，而且人们

4、用笔和纸做有限次运算后即可完成；4、拥有足够的。12C排序法属于类排序法,实在简单13. D排序法的基础上改进的。在队列中可以14. D数据和删除数据，队列是先进先出的线性表所谓算法是指解题方案的准确而完整的描述15. D栈和队列的共同点是只允许在端点处16. C和删除数据请查考 26 集17. B中的方法。归并排序存在大量的数据拷贝，因此占用内存量最大。18. C在数据结构中，数据元关。19. D间的前后件关系是逻辑结构，而与它们在计算机中的位置无顺序构的20. A结构的地址在内存中是连续的所以可以通过计算地址实现随机存取，而链式地址不一定连续，只能通过第 1 个结点的指针顺序存取；结栈的元

5、素存取规则为：先进后出，后进先出。在本题中已经存放了 ABCD 四个元素，因此出栈的可能性只能是 D 在C 的前面，C 在 B 的前面，B 在 A 的前面，而符合这个顺序的只有 A选项。21. C线性单链表、双向链表与循环链表的结构及其基本运算，头结点不仅标识了表中首结点的位置，而且根据单链表(包含头结点)的结构，只要掌握了表头，就能够加头结点目的是为了便于运算的实现。22. D整个链表，因此增算法分析是指对一个算法的运行时间和占用空间做定量的分析，计算相应的数量级。分析算法的目的就是要降低算法的时间复杂度和空间复杂度，提高算法的执行效率。D数据表 A 中每个元素距其位置不远，代表其数据大体是符合顺序的，因此采用直接排序既可以节省时间。A用链表表示线性表的优点是便于25. B和删除操作在教学26. D中讲过主程序与子程序之间的调用关系是通过栈的形式来保存每一次调用。算法的时间复杂度是指算法执行过程中所需要的基本运算次数B二叉树的深度为 12。因为叶子节点为 1 个，按二叉树理论得出（任意一棵二叉树中度为 0的节点总是比度为 2 的节点多一个），故得出此二叉树度为 2 的节点为 0 个。12（总节点）-1（度为 0）- 0（度为 2）=11（度为 1）。故证明此二叉树每层只有 1 个节点，总共