1.4 过关全真模拟题解析

【试题1分析】数据的存储结构分顺序存储结构和链式存储结构，一个数据的逻辑结构可以有多种存储结构。顺序结构中数据元素所占的存储空间是连续的，而链式存储结构中，数据元素通过指针就联系在一起了，所以所占的存储空间不一定是连续的。

【答案】B

【试题2分析】队列（Queue）是指允许在一端进行插入，而在另一端进行删除的线性表。允许插入的一端称为队尾，允许删除的一端称为队头。在队列这种数据结构中，最先插入的元素将能够最先被删除；反之，最后插入的元素最后才能被删除。因此，队列又称“先进先出”或“后进后出”的线性表。

【答案】D

【试题3分析】链表采用的是链式存储结构，它的节点空间可以动态申请和释放；它的数据元素的逻辑次序靠节点的指针来指示，插入或删除不需要移动数据元素。但是链式存储结构也有不足之处，每个节点中的指针域需额外占用存储空间，它是一种非随机存储结构。

【答案】B

【试题4分析】栈是线性表的一种，它的特点是先进后出，并且只能在表的一端进行插入和删除操作。入栈和出栈都是在栈顶进行的，因此具有记忆作用。栈可以采用顺序存储，也可以采用链式存储。

【答案】B

【试题5分析】在任意一棵二叉树中，度为0的节点（即叶子节点）总是比度为2的节点多一个，所以该二叉树的叶子节点数等于n+1。

【答案】A

【试题6分析】二叉树前序遍历的简单描述为：若二叉树为空，则返回节点；否则先访问根节点，然后前序遍历左子树，最后前序遍历右子树。可见，前序遍历二叉树的过程是一个递归的过程。根据题目中给出的二叉树的结构可知前序遍历的结果是ABDYECFXZ。

【答案】C

【试题7分析】若数据表A中每个元素距其最终位置不远，说明数据表A按关键字值的排序是有序的。在待排序列基本有序的情况下，采用插入排序所用的时间最少。

【答案】B

【试题8分析】数据的逻辑结构是指反映数据元素之间逻辑关系的数据结构。数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构（也称数据的物理结构）。一般来说，一种数据的逻辑结构根据需要可以表示成多种存储结构，常用的存储结构有顺序、链接和索引等。

【答案】D

【试题9分析】算法分析是指对一个算法的运行时间和占用空间做定量的分析，计算相应的数量级。分析算法的目的就是要降低算法的时间复杂度和空间复杂度，提高算法的执行效率。

【答案】D

【试题10分析】队列是一种特殊的线性表示，只允许在表的一端插入元素；在表的另一端删除元素，插入元素的一端叫“队尾”，删除元素的一端叫“队头”；先插入的元素先被删除，是按“先进先出”的原则组织数据的。

【答案】A

【试题11分析】栈和队列都是操作受限的线性表，只允许在端点插入和删除。不同点是栈只允许在表的一端进行插入和删除操作，而队列允许在表的一端进行插入操作，而在另一端进行删除操作。

【答案】C

【试题12分析】在链式存储结构中，存储数据结构的存储空间可以不连续，各数据节点的存储顺序与数据元素之间的逻辑关系可以不一致，而数据之间的逻辑关系是由指针域来确定的。

【答案】B

【试题13分析】二分法查找只用于顺序存储的有序线性表，而顺序查找用于顺序存储的非有序线性表和线性链表。

【答案】A

【试题14分析】对线性表进行检索，要求线性表是按顺序方式存储的，并按关键码的大小排好序，而不按关键码检索频率排序。

【答案】A

【试题15分析】根据二分法的查找过程，首先将90与表中的中间元素50进行比较，由于90大于50，所以在线性表的后半部分查找。第二次比较的元素是后半部分的中间元素，即90，这时两者相等，即查找成功。

【答案】B

【试题16分析】线性表的存储通常有两种存储结构：顺序存储结构和链式存储结构。

【答案】A

【试题17分析】快速排序的基本思想是：经过一趟排序待排序记录分割成独立的部分，其中前半部分元素都比基准元素小，而后半部分元素都比基准元素大；再分别对这两个部分的记录继续进行排序，以达到整个序列有序。在上述序列中，比关键码33小的元素有4个，因此第一趟排序完成后关键码33被放到第5个数的位置上。

【答案】B

【试题18分析】数据的存储结构有顺序存储结构和链式存储结构两种，不同存储结构的数据处理效率不同。由于链表采用链式存储结构，元素的物理顺序并不连续，对于插入和删除无需移动元素，很方便，但当查找元素时就需要逐个元素查找，因此查找的时间相对更长。

【答案】C

【试题19分析】线性链表的节点包括节点内容以及指向下一节点的指针，因此其各个元素在存储空间的位置不一定是连续的，同样表头元素也不一定存储在其他元素的前面。

【答案】D

【试题20分析】一个算法应该有0个或多个输入，但是必须有一个或多个输出。

【答案】B