数据结构复习及答案
一.是非题
(正确的打“√”,错误的打“×”。)
1. 数据结构可用三元式表示(D,S,P)。其中:D 是数据对象,S 是 D 上的关系,
P 是对 D 的基本操作集。×
2. 线性表的链式存储结构具有可直接存取表中任一元素的优点。 ×
3. 字符串是数据对象特定的线性表。
4. 二叉树是一棵结点的度最大为二的树。 ×
5. 邻接多重表可以用以表示无向图,也可用以表示有向图。×
6. 可从任意有向图中得到关于所有顶点的拓扑次序。×
7. 一棵无向连通图的生成树是其极大的连通子图。×
8. 二叉排序树的查找长度至多为 log
2
n。×
9. 对于一棵 m 阶的 B
-
树.树中每个结点至多有 m 个关键字。除根之外的所有非终端结点至
少有┌m/2┐个关键字。×
10.对于目前所知的排序方法,快速排序具有最好的平均性能。
11. 顺序存储方式的优点是存储密度大,且插入、删除运算效率高。×
12. 二维数组是其数据元素为线性表的线性表。
13. 连通图 G 的生成树是一个包含 G 的所有 n 个顶点和 n-1 条边的子图。×
14. 折半查找不适用于有序链表的查找。
15. 完全二叉树必定是平衡二叉树。
16. 中序线索二叉树的优点是便于在中序下查找直接前驱结点和直接后继结点。
17. 队列是与线性表完全不同的一种数据结构。×
18. 平均查找长度与记录的查找概率有关。
19. 二叉树中每个结点有两个子结点,而对一般的树,则无此限制,所 以,二叉树是树的
特殊情形。×
20. 算法的时间复杂性越好,可读性就越差;反之,算法的可读性越好,则时间复杂性就越
差。×
二.选择题
1. 若广义表 LS 满足 GetHead(LS)==GetTail(LS),则 LS 为( b )。
A. ( ) B. (( )) C. (( ),( )) D. (( ),( ),( ))
3. 在下列数据结构中( c )具有先进先出(FIFO)特性,( b )具有先进后出(FILO)
特性。
a:线性表 b:栈 c:队列 d:广义表
4. 假设用于通讯的电文仅由 6 个字符组成,字母在电文中出现的频率分别为 7, 19, 22, 6,
32, 14。 若为这 6 个字母设计哈夫曼编码(设生成新的二叉树的规则是按给出的次序从左
至右的结合,新生成的二叉树总是插入在最右),则频率为 7 的字符编码是( g ),频率为
32 的字符编码是( c )。