数据结构试题及答案

2. 在树形结构中，树根结点没有 前

驱 结点，其余每个结点有且只有 一 个前驱结点；叶子结点没有 子 结点，其余每个结点的后续结点数可以 任意多个

3．在顺序表中访问任意一结点的时间复杂度均为 O（1） ，因此，顺序表也称为 随机存取的数据结构。

4．栈是一种特殊的线性表，允许插入和删除运算的一端称为 栈顶 。不允许插入和删除运算的一端称为 栈底 。

5．三元素组表中的每个结点对应于稀疏矩阵的一个非零元素，它包含有三个数据项，分别表示该元素的 行标 、 列标 和元素值。

6. 若n为主串长，m为子串长，则串的古典匹配算法最坏的情况下需要比较字符的总次数为 。

7．一棵深度为6的满二叉树有 31 个分支结点和 32 个叶子。

8. n个顶点e条边的图，若采用邻接表存储，则空间复杂度为 。

9. 假设在有序线性表a[20]上进行折半查找，则比较一次查找成功的结点数为 1 ；比较两次查找成功的结点数为 2 ；比较四次查找成功的结点数为 ；平均查找长度为 。

1、逻辑结构、存储结构

2、前驱、1、 后续、任意多个

3、O(1) 、随机存取

4、栈顶、栈底

5、行下标、列下标

6、(n-m+1)*m

7、n1+n2=0+ n2= n0-1=31、 26-1 =32 。

注：满二叉树没有度为1的结点，所以分支结点数就是二度结点数。

8、O(n+e)

9、1、2、8、3.7

三、判断题（每小题1分，共12分）

（错 ）1. 链表的每个结点中都恰好包含一个指针。

（ ）2. 线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。

（ ）3. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。

（ ）4. 线性表的逻辑顺序与存储顺序总是一致的。

（ 对 ）5. 栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。

（对 ）6. 对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表。

（对 ）7. 栈和队列的存储方式既可是顺序方式，也可是链接方式。

（ 错 ）8. 队列是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。（先进先出型或后进后出）

（ ）9. 二叉树中每个结点的两棵子树的高度差等于1。

（ ）10.二叉树中每个结点有两棵非空子树或有两棵空子树。

（ ）11. 二叉树中所有结点，如果不存在非空左子树，则不存在非空右子树。

（ ）12. 具有12个结点的完全二叉树有5个度为2的结点。

四、问答题（每小题5分，共20分）

1. 简述线性结构与非线性结构的不同点。

2．试比较顺序存储结构和链式存储结构的优缺点。在什么情况下用顺序表比链表好？