数据结构高手来帮忙（简答题、算法题）

来源：百度知道 编辑：UC知道 时间：2024/06/28 20:13:12
三、 判断题（10分）
1、顺序存储方式只能用于存储线性结构。（ ）
2、数组不适合作为二叉树的存储结构。（ ）
3、串是一种数据对象和操作都特殊的线性表。（ ）
4、线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。（ ）
5、栈和队列都是限制存取点的线性结构。（ ）
6、一个广义表可以为其它广义表所共享。（ ）
7、树的度是指树内结点的度。（ ）
8、一棵一般树的结点的先根次序遍历和后根次序遍历分别与其相应二叉树的结点前序遍历和后序遍历是一致的。（ ）
9、无向图的邻接矩阵一定是对称矩阵，有向图的邻接矩阵一定是非对称矩阵。（ ）
10、排序算法中的比较次数与初始元素序列的排列无关。（ ）

四、 问答题（30分）
1、 设目标串t=“abaabcc”，模式串P=“aabc”，试描述根据穷举模式匹配算法进行匹配的过程。
2、 设用于通讯的电文由8个字母组成，字母在电文中出现的频率分别为7，9，2，6，32，3，21，10，试为这8个字母设计不等长Huffman编码，并给出该电文的总码数（要求画出Huffman编码数）。
3、 试将关键码18，5，9，13，11，28，20，16，17，依次插入到一棵初始为空AVL树中，画出每插入一个关键码后的AVL树，并标明平衡化旋转类型。
4、 对下图所示的图，画出用普里姆算法生成其最小生成树的过程。
○B
1 9

○A 6 ○C

5 3
○D
4 7

三、 判断题（10分）
1、顺序存储方式只能用于存储线性结构。（ N ）
2、数组不适合作为二叉树的存储结构。（ N ）
3、串是一种数据对象和操作都特殊的线性表。（ Y ）
4、线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。（ Y ）
5、栈和队列都是限制存取点的线性结构。（ Y ）
6、一个广义表可以为其它广义表所共享。（ N ）
7、树的度是指树内结点的度。（ Y ）
8、一棵一般树的结点的先根次序遍历和后根次序遍历分别与其相应二叉树的结点前序遍历和后序遍历是一致的。（ N ）
9、无向图的邻接矩阵一定是对称矩阵，有向图的邻接矩阵一定是非对称矩阵。（ N ）
10、排序算法中的比较次数与初始元素序列的排列无关。（ X ）

1、 设目标串t=“abaabcc”，模式串P=“aabc”，试描述根据穷举模式匹配算法进行匹配的过程。

abaabcc
aabc d=0, fail
aabc d=1, fail
aabc d=2, success, return 2

2、 设用于通讯的电文由8个字母组成，字母在电文中出现的频率分别为7，9，2，6，32，3，21，10，试为这8个字母设计不等长Huffman编码，并给出该电文的总码数（要求画出Huffman编码数）。

假设：
a:7 b:9 c:2 d:6 e:32 f:3 g:21 h:10
排序：
(c:2) (f:3) (d:6) (a:7) (b:9) (h:10) (g:21) (e:32)
按优先级合并：
((c[0],f[1]):5) (d:6) (a:7) (b:9) (h:10) (g:21) (e:32)
(a:7) (b:9) (h:10) (((c[00],f[01]),d[1]):11) (g:21) (e:32)
(h:10) (((c[00],f[01]),d[1]):11) ((a[0],b[1]):1