1.2 历年试题分析

试题1

下列关于栈叙述正确的是（ ）。

A.栈顶元素最先被删除

B.栈顶元素最后才能被删除

C.栈底元素永远不能被删除

D.以上三种说法都不对

【分析】栈是允许在同一端进行插入和删除操作的特殊线性表。允许进行插入和删除操作的一端称为栈顶（Top），另一端为栈底（Bottom）；栈底固定，而栈顶浮动；栈中元素个数为0时称为空栈。插入一般称为进栈（PUSH），删除则称为退栈（POP）。栈也称为先进后出表。

【答案】A

试题2

下列叙述中正确的是（ ）。

A.有一个以上根节点的数据结构不一定是非线性结构

B.只有一个根节点的数据结构不一定是线性结构

C.循环链表是非线性结构

D.双向链表是非线性结构

【分析】循环链表是另一种形式的链式存储结构。它的特点是表中最后一个节点的指针域指向头节点，整个链表形成一个环。双向链表也叫双链表，是链表的一种，它的每个数据节点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个节点开始，都可以很方便地访问它的前驱节点和后继节点；循环链表和双向链表都是线性结构。有一个以上根节点的结构一定是非线性结构。

【答案】B

试题3

某二叉树共有7个节点，其中叶子节点只有1个，则该二叉树的深度为（ ）（假设根节点在第1层）。

A.3

B.4

C.6

D.7

【分析】二叉树是一种很有用的非线性结构，它具有以下两个特点：

1）非空二叉树只有一个根节点；

2）每一个节点最多有两棵子树，且分别称为该节点的左子树与右子树。

根据二叉树的概念可知，二叉树的度可以为0（叶子节点）、1（只有一棵子树）或2（有2棵子树）。由于只有一个叶子节点，所以该二叉树没有分叉，7个节点连成一线，深度为7。

【答案】D

试题4

下列叙述正确的是（ ）。

A.算法就是程序

B.设计算法时只需要考虑数据结构的设计

C.设计算法时只需要考虑结果的可靠性

D.以上三种说法都不对

【分析】算法是求解问题的方法。程序设计时要设计算法，但算法不是程序。设计算法除了要考虑数据结构外，还要考虑算法的可行性、可靠性等。

【答案】D

试题5

下列关于线性链表的叙述中，正确的是（ ）。

A.各数据节点的存储空间可以不连续，但它们的存储顺序与逻辑顺序必须一致

B.各数据节点的存储顺序与逻辑顺序可以不一致，但它们的存储空间必须连续

C.进行插入与删除时，不需要移动表中的元素

D.以上三种说法都不对

【分析】节点的存储顺序和逻辑顺序不一定一致，存储空间也不一定连续。插入和删除元素的时候，不需要移动表中的元素。

【答案】C

试题6

下列关于二叉树的叙述中，正确的是（ ）。

A.叶子节点总是比度为2的节点少一个

B.叶子节点总是比度为2的节点多一个

C.叶子节点数是度为2的节点数的两倍

D.度为2的节点数是度为1的节点数的两倍

【分析】二叉树叶子节点总是比度为2的节点多一个，这是二叉树的性质。

【答案】B

试题7

下列叙述中正确的是（ ）。

A.栈是一种先进先出的线性表

B.队列是一种后进先出的线性表

C.栈与队列都是非线性结构

D.以上三种说法都不对

【分析】栈和队列都是特殊的线性表，栈（Stack）只能在表的一端进行插入和删除运算，所以，栈是一种“先进后出”的线性表；而队列（Queue）只允许在一端删除，在另一端插入，所以，队列是一种“先进先出”的线性表。

【答案】D

试题8

一棵二叉树共有25个节点，其中5个是叶子节点，则度为1的节点数为（ ）。

A.4

B.10

C.6

D.16

【分析】从题干中我们知道，在该二叉树中有5个叶子节点，由二叉树的性质之一：任何一棵二叉树，度为0的节点（也就是叶子节点）总是比度为2的节点多一个。可以得出，该二叉树度为2（有2棵子树）的节点数为4个，而该二叉树总共有25个节点，所以，度为1的节点数为：25-5-4＝16个。

【答案】D

试题9

下列链表中，其逻辑结构属于非线性结构的是（ ）。

A.二叉链表

B.循环链表

C.双向链表

D.带链的栈

【分析】此题目主要考查数据结构中的非线性结构的基本知识。其中，循环链表、双向链表、带链的栈都是线性结构，二叉链表是非线性链表。

【答案】A

试题10

设循环队列的存储空间为Q（1：35），初始状态为front=rear=35。现经过一系列入队与出队运算后，front=15，rear=15，则循环队列中的元素个数为（ ）。

A.15

B.16

C.20

D.0或35

【分析】此题目主要考查数据结构中队列的存储规则，队列的元素个数为rear-front，如果差是非正数，加队列的长度。当队首与队尾指向同一空间时，队列可能为空，也可能为满，所以选择D。

【答案】D

试题11

下列关于栈的叙述中，正确的是（ ）。

A.栈底元素一定是最后入栈的元素

B.栈顶元素一定是最先入栈的元素

C.栈操作遵循先进后出的原则

D.以上三种说法都不对

【分析】栈的存储原则是先进后出，所以选择C。

【答案】C