西安交通大学17年5月补考《数据结构》作业考核试题

没有共同点 标准答案：

29 设某哈夫曼树中有199个结点，则该哈夫曼树中有（）个叶子结点。 99 100 101 102 标准答案：

30 设有向无环图G中的有向边集合E={<1，2>，<2，3>，<3，4>，<1，4>}，则下列属于该有向图G的一种拓扑排序序列的是（）。 1，2，3，4 2，3，4，1 1，4，2，3 1，2，4，3 标准答案：

二、判断题（共 20 道试题，共 40 分。） V 1 对连通图进行深度优先遍历可以访问到该图中的所有顶点。 错误 正确 标准答案：

2 哈夫曼树中没有度数为1的结点。 错误 正确 标准答案：

3 非空的双向循环链表中任何结点的前驱指针均不为空。 错误 正确 标准答案：

4 一棵m阶树中每个结点最多有m个关键码，最少有2个关键码。 错误 正确 标准答案：

5 向二叉排序树中插入一个结点需要比较的次数可能大于该二叉树的高度。 错误 正确 标准答案：

6 稀疏矩阵的压缩存储可以用一个三元组表来表示稀疏矩阵中的非0元素。 错误 正确 标准答案：

7 顺序表用一维数组作为存储结构，因此顺序表是一维数组。 错误 正确 标准答案：

8 有向图的邻接表和逆邻接表中表结点的个数不一定相等。 错误 正确 标准答案：

9 由树转化成二叉树，该二叉树的右子树不一定为空。 错误 正确 标准答案：

10 为度量一个搜索算法的性能，需要在时间和空间方面进行权衡。 错误 正确 标准答案：

11 二维数组是数组元素为一维数组的线性表，因此它是线性结构。 错误 正确 标准答案：

12 不论是入队列操作还是入栈操作，在顺序存储结构上都需要考虑“溢出”情况。 错误 正确 标准答案：

13 完全二叉树中的叶子结点只可能在最后两层中出现。 错误 正确 标准答案：

14 对链表进行插入和删除操作时不必移动链表中结点。 错误 正确 标准答案：

15 分块查找的平均查找长度不仅与索引表的长度有关，而且与块的长度有关。 错误 正确 标准答案：

16 对连通图进行深度优先遍历可以访问到该图中的所有顶点。 错误 正确 标准答案：

17 稀疏矩阵的压缩存储可以用一个三元组表来表示稀疏矩阵中的非0元素。

错误 正确 标准答案：

18 子串“”在主串“”中的位置为3。 错误 正确 标准答案：

19 设某堆中有n个结点，则在该堆中插入一个新结点的时间复杂度为O(log2n)。 错误 正确 标准答案：

20 线性表中的所有元素都有一个前驱元素和后继元素。 错误 正确 标准答案：