Question

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

三、 判断题（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
2

○F ○G

5、 对于给定的一组关键码47，33，61，82，72，11，25，47，57，2，要求写出采用希尔排序方法作升序时每一趟的运算结果。

五、 算法题（40分）
1、 设在长度大于1的循环链表上，P为指向表中某结点X的指针，编写算法删除X的直接前驱结点。
2、 设二叉树采用链表表示，各结点结构为leftchild data rightchild,编写算法输出二叉树前序遍历中的前k个结点值（k<n）。
3、 给定使用邻接矩阵存储的带权有向图G，编写算法对该图中所有顶点进行拓扑排序。

Answer 1

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]):16) (g:21) (e:32)
((a[0],b[1]):16) ((h[0],((c[100],f[101]),d[11])):21) (g:21) (e:32)
(g:21) (e:32) (((a[00],b[01]),(h[10],((c[1100],f[1101]),d[111]))):37)
(((a[00],b[01]),(h[10],((c[1100],f[1101]),d[111]))):37) ((g[0],e[1]):43)
((((a[000],b[001]),(h[010],((c[01100],f[01101]),d[0111]))),(g[10],e[11])):80)
a:000 3*7=21
b:001 3*9=37
c:01100 5*2=10
d:0111 4*6=24
e:11 2*32=64
f:01101 5*3=15
g:10 2*21=42
h:010 3*10=30

Answer 2

三、 判断题（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]):16) (g:21) (e:32)
((a[0],b[1]):16) ((h[0],((c[100],f[101]),d[11])):21) (g:21) (e:32)
(g:21) (e:32) (((a[00],b[01]),(h[10],((c[1100],f[1101]),d[111]))):37)
(((a[00],b[01]),(h[10],((c[1100],f[1101]),d[111]))):37) ((g[0],e[1]):43)
((((a[000],b[001]),(h[010],((c[01100],f[01101]),d[0111]))),(g[10],e[11])):80)
a:000 3*7=21
b:001 3*9=37
c:01100 5*2=10
d:0111 4*6=24
e:11 2*32=64
f:01101 5*3=15
g:10 2*21=42
h:010 3*10=30
总频数 243

回头慢慢补