数据结构课习题参考答案

教材为复旦大学出版

目录

一、

1.1 比较2个线性链表的C函数 3

1.2 写一个倒置顺序存贮的线性表的C函数 3

1.3 写一个在线性表中，使线性表中没有值相同的结点的函数。 4

1.4 编写一个求解给定多项式的值的C函数。 5

1.5 实现多项式乘法 6

1.7 车厢出站问题 9

1.8 编写对任一栈作进栈和出栈运算的C函数 10

1.10 写出表达式等价的后缀表达式。 12

1.11编写一个统计给定的线性链表的结点个数的C函数。 15

1.12 编写一个将给定的线性链表逆转的C函数。 16

1.13编写一个插入值的c函数。 18

1.14编写一个删除链表中结点的前趋结点的C函数。 19

1.15试编写一个将两个链表归并成一个线性链表的C函数。 20

1.17 用环形链表解1。6题 23 1．18 将给定的线性链表改成环形链表 24 1． 19将给定的线性链表改成一个带表头的环形链表 25 1．20 编写用hash函数h（Xi）＝Xi，对X1，X2 X800进行hash存储的程序 26 1． 21求广义表的深度。 27

2．1试编写一个在两个顺序字符串中寻找最大公共子串的C函数。 29 2． 2试编写一个实现STRINS（S1，I，S2）的C函数。 31

2．3 按照2.2题的要求，编一个实现STRDEL（S，I，J）的C函数。 32

3．1编写一个二分插入排序的C程序 33

3．2编写一个对给定链表进行插入排序的C程序。 34

3．5采用顺序存储实现，即用数组存放排序过程中以排好序的链表的头指针。 36

3． 6采用顺序存储的结构即数组实现。 38

3．7编写一个实现快速排序的非递归的C函数。 39

3．8对于分别写出用下列排序方法对线性表进行排序的结果。 40

4．3将n阶三对角阵（即半带宽为1的带状矩阵）A按行序列序存放在一维数组b[3*n-2]中。若aij(|i-j|<=1)存放在b[k]中，请求出求解k的计算公式。 42

4．4如果把广义的Anab按行序列序存放在一维数组b[(a+b-1)*n-(a+b-2)]中，元素aij存放在b[k]中，那么请写出计算k的计算公式。 42

4．5试编写一个求解两个三元数组相加的C函数。 42

4．6试编写一个将十字链表转置的C函数. 44

5．1请分别给出对树进行前序、后序、层次序遍历后的结点序列。 45

5．2试叙述将m棵有序树组成的有序树林转换成相应的二叉树的逆变换。 46

5．3试编写一个把树中每个结点的左右子结点进行对换的C函数。 47

5．4编写一个利用栈来实现后序遍历一棵给定的二叉树的C函数。 49

5．5题目： 51

试为下面各小题分别编写一个C函数：

（1） 按前序输出T的结点值。

（2） 按后序输出T的结点值。

（3） 输出树T的叶子结点值。

教材为复旦大学出版

（4） 求出树T的次数。

5．6试编写一个把树T按标准形式进行存贮的C函数。 53

5．7 已知树T中结点的中序和后序，编写一个把T按标准形式存储的C函数 54

5．8 判断给定的二叉树是否为完全二叉树 55

5．9 判断两棵给定的二叉树是否相似 55

5．10 把树T转换成由标准形式进行存储的树T 55

5．11试编写一个寻找结点a的父结点的C函数。 56

5．12试编写一个按前序遍历穿线树的C函数。 58

6．1画出由集合中结点所构成的查找树，画出删除后的查找树。 60

6．2试编写一个用平分法构造出由集合中结点所构成的丰满查找树的C函数。 60

6．5编写一个判断给定二叉树T是否为平衡树的C函数。 62

6．6试画出Adelson插入方法的右改组的转换图。 65

6．9试画出用Hu-Tucker算法构造出的最佳叶子查找树。 66

6．10 画出每次插入后的B－树 67

6．12 修改皇后问题 70

6．13 马的周游路线 76

7．1对于图题7.1（P235）的无向图，给出： 79

（1） 表示该图的邻接矩阵。

（2） 表示该图的邻接表。

（3） 图中每个顶点的度。

7．2对于图题7.1的无向图，给出： 79

（1）从顶点1出发，按深度优先搜索法遍历图时所得到的顶点序

（2）从顶点1出发，按广度优先法搜索法遍历图时所得到的顶点序列。

7．3对于图题7.3的有向图，给出： 84

（1） 表示该图的邻接矩阵。

（2） 表示该图的邻接表。

（3） 图中每个顶点的入度和出度。

7．4对于图题7.3的有向图，给出： 85

（1） 从顶点1出发，按深度优先搜索法遍历图时的所得的顶点序列。

（2） 从顶点1出发，按广度优先搜索法遍历图时的所得的定点序列。

7．5对于图题7.1的无向图，试问它是（1）连通图吗？（2）完全图吗？ 85

7．6对于图题 7.3的有向图，试问它是（1）弱连通图吗？（2）强连通图吗？ 86

7．7图题7-7是有向图，试问其中哪个图是 86

（1） 弱连通的？

（2） 强连通的？

7．8具有N个顶点的连通无向图至少有几条边？ 86

7．9具有N个顶点的强连通有向图至少有几条边？ 86

7．10分别写出用深度和广度优先搜索法遍历完全无向图的顶点序列。 87

7．11改写以深度优先搜索法遍历给定的连通图的dfs程序。 87

7．12在图题7.1中，从顶点1出发，分别画出其dfs生成树和bfs生成树。 88

教材为复旦大学出版

1.1：比较2个线性链表的C函数

1． 存储法：用两个数组存放线性表。

2． 存储结构：一般的顺序存储方式。

3． 源程序：

int comp(int a[],int as,int b[],int bs)

{

int tmp=as>bs?as:bs;

int i;

for(i=0;i<tmp;i++)

{

if(a[i]>b[i]) return 1;

if(a[i]<b[i]) return -1;

}

if(as>bs) return 1;

if(bs>as) return -1;

return 0;

}

4.测试用例：

1． A[3]={1,2,3} B[3]={1,2,3} output : 0;

2． A[3]={1.2.3} B[3]={1,1,3} output: 1;

3． A[3]={1,2,3} B[3]={1,2,4} output: -1

4． A[3]={1,2,3} B[4]={1,2,3,0} output: -1;

5． A[4]={1,2,3,0} B[3]={1,2,3} output: 1;

6． A[4]={1,2,3,0} B[3]={1,3,2} output:-1;

1.2

写一个倒置顺序存贮的线性表的C函数。要求用最少的附加存贮空间来完成。

< …… 此处隐藏：11656字，全部文档内容请下载后查看。喜欢就下载吧 ……