数据结构
一.是非题
(正确的打“√”,错误的打“×”。)
1. 数据结构可用三元式表示(D,S,P)。其中: D 是数据对象,S 是 D 上的关系集,
P 是对 D 的基本操作集。×
2. 线性表的链式存储结构具有可直接存取表中任一元素的优点。 ×
3. 队列是数据对象特定的线性表。×
4. 二叉树是一棵结点的度最大为二的树。 ×
5. 邻接表可以用以表示无向图,也可用以表示有向图。√
6. 可从任意有向图中得到关于所有顶点的拓扑次序。×
7. 一棵无向连通图的生成树是其极大的连通子图。×
8. 二叉排序树的查找长度至多为 log
2
n。×
9. 对于一棵 m 阶的 B
-
树,树中每个结点至多有 m-1 个关键字。除根之外的所有非终端
结点至少有m/2 -1 个关键字。√
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. (( ),( ),( ))
2. 递归程序可借助于( b )转化为非递归程序。
a:线性表 b: 栈 c:队列 d:数组
3. 在下列数据结构中( c )具有先进先出(FIFO)特性,( b )具有先进后出(FILO)特
性。
a:线性表 b:栈 c:队列 d:广义表
4. 假设用于通讯的电文仅由 6 个字符组成,字母在电文中出现的频率分别为 7, 19, 22,
1