数据结构深大经典题

7.3.习题自测

第一章 数据结构绪论

1. 写出算法的特征

2. 写出for (i=n; i>0; i/=2); 的时间复杂度

第二章 线性表

1. 循环队列的队首和队尾下标分别为f, r, 最大长度为n, 写出判断队满和队空的条件

2. 向量A中已有n个元素，写出删除其第i个位置元素的算法

3. 在顺序表中插入和删除一个结点需平均移动多少个结点？具体的移动次数取决于哪两个

因素？

4. 设线性表的n个结点定义为(a0,a1,?,an-1)，重写顺序表上实现的插入和删除算法：

InsertList和DeleteList。

5. 设A和B是两个单链表，其表中元素递增有序。试写一算法将A和B归并成一个按元素

值递增有序的单链表C。

第三章 栈和队列

1. 设将整数1,2,3,4依次进栈，但只要出栈时栈非空，则可将出栈操作按任何次序夹入其

中，请回答下述问题： ⑴. 若入、出栈次序为Push(1)，Pop()，Push(2)，Push(3)，Pop()，Pop()，Push(4)，Pop()，

则出栈的数字序列为何（这里Push(i)表示进栈，Pop()表示出栈）？ ⑵. 能否得到出栈序列1423和1432？并说明为什么不能得到或者如何得到。 ⑶. 请分析1,2,3,4的24种排列中，哪些序列是可以通过相应的入出栈操作得到的。

第四章 串

1. 现有模式abaabc，写出每个字母的next值。

2. 假设主串abcabadabaabc，模式串如上，说明kmp算法的匹配过程。

3. 回文是指正读和反读均相同的字符序列，如\和\均是回文，但\不是回

文。试写一个算法判定给定的字符向量是否为回文。（提示：将一半字符入栈）。

第六章 树与二叉树

1. 若二叉树的先序和中序遍历结果分别是a, b, d, e, c, f, g, h和d, e, b, a, f, c,

h, g, 求其后序遍历的结果

2. 二叉树的中序和后序遍历结果分别为4, 5, 2, 1, 6, 3, 8, 7和5, 4, 2, 6, 8, 7, 3,

1, 求其先序遍历的结果

3. 树用孩子兄弟链接法存储，结点结构为：

struct Node {char data, struct Node *child, *brother;}

写C函数void PreOrder(struct Node *root), 先根遍历树。Root是指向树根的指针。

4、假设对一段电文“abcdcbcacab”进行Huffman编码。画出对应的Huffman树，并写出每

个字符的Huffman编码。

5. a, b, c, d, f的使用频度分别是17%, 15%, 19%, 22%, 27%, 构造Huffman树，写出它

们的Huffman编码。

第七章 图

1. 无向网N={V,E}，V={0,1,2,3,4,5}，E={(0,1,10)，(0,4,19)，(0,5,21)，(1,2,5)，

(1,3,6)，(1,5,11)，(2,3,6)，(3,4,18)，(3,5,14)，(4,5,33)}，E中每个元组的第三个元素表示权。 ⑴. 画出该网；

⑵. 写出该网的邻接矩阵；

⑶. 用Prim算法求最小生成树，依次写出树的生长过程； ⑷. 用Kruskal算法求最小生成树，依次写出树的生长过程。

2．有向网N={V,E}，V={0,1,2,3,4}，E={<0,1,1>，<0,3,3>，<0,4,10>，<1,2,5>，<2,4,1>，

<3,2,2>，<3,4,6>}，E中每个元组的第三个元素表示权。 ⑴. 画出该网。

⑵. 用Dijkstra算法求最短路径，写出顶点0到其它各顶点的最短路径长度、路径及产生

过程。

⑶. 求关键路径，写出计算过程。

3. 某图的表示意如下，按拓扑排序算法，写出电脑拔出的拓扑排序结果

0: ->5->2->1^ 1: ->4->3->2^ 2: ->3^ 3: ->4^ 4: ^ 5: ->4^

4. 写C函数int OutDegree(int Adj[][N], int vi), 返回有向图顶点vi的出度。Adj, N

分别是图的邻接矩阵和顶点数。

5. 按顺序输入顶点对：(1,2)，(1,6)，(2,6)，(1,4)，(6,4)，(1,3)，(3,4)，(6,5)，(4,5)，

(1,5)，(3,5)，根据建立无向图的邻接表算法CreateALGraph画出相应的邻接表。并写出在该邻接表上，从顶点4开始搜索所得的深度优先遍历序列和广度优先遍历序列。

第九章 查找

1. 往一棵空的AVL树中依次插入关键码2, 1, 3, 5, 8, 4, 7, 6, 分别画出每个关键码插

入完成后的AVL树。

2. 画出在初始为空的AVL树中依次插入30, 45, 50, 46, 55, 49, 40时该树的生长全过程，

并在有“旋转”时说出“旋转”的类型。

3. 假设关键字输入顺序为80, 20, 10, 8, 27, 32, 68, 95, 87,63, 46，散列函数采用除

留余数法，其表达式为：H(Key)=Key。

⑴. 用拉链法解决冲突，画出插入所有关键字后的链表结构（假设链表头插入）。 ⑵. 计算该表查找成功的平均查找长度。

第十章 内部排序

1. 分别用直接插入、希尔（第一次增量为3）、快速排序、归并排序、堆排序算法对整数序

列3, 17,12, 8, 70,89, 75, 65, 77,9 进行升序排序，写出每一趟的排序结果。

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库数据结构深大经典题在线全文阅读。