数据结构作业题教材

1、第一章1、设 n为正整数，利用大 O记号，将下列程序段的执行时间表示为n 的函数。(1) i=1; k=0;while(in) k=k+10*i;i+;(2) i=0; k=0; do k=k+10*i; i+; while(in);(3) i=1; j=0; while(i+jj) j+; else i+;(4) x=n; / n1while (x=(y+1)*(y+1) y+;(5) x=91; y=100;while(y0) if(x100)x=x-10;y-;else x+;2、按增长率由小至大的顺序排列下列各函数：2100, (3/2)n ， (2/3)n ， nn ,n0.5 ,

2、n! ，2n ，lgn ,nlgn, n(3/2)2-7 针对带表头结点的单链表，试编写下列函数。(1) 定位函数 Locate ：在单链表中寻找第 i 个结点。若找到，则函数返回第 i 个结点的地址；若找 不到，则函数返回 NULL。(2) 求最大值函数 max：通过一趟遍历在单链表中确定值最大的结点。3-1.将编号为 0 和 1 的两个栈存放于一个数组空间Vm 中，栈底分别处于数组的两端。当第 0 号栈的栈顶指针 top0等于-1时该栈为空，当第 1号栈的栈顶指针 top1等于 m时该栈为空。两个栈均从两端向中间增长。当向第 0号栈插 入一个新元素时， 使top0增1得到新的栈顶位置， 当

3、向第 1号栈插入一个新元素时， 使top1减 1得到新的栈顶位置。 当 top0+1 = top1 时或 top0 = top1 - 1 时，栈空间满， 此时不能再向任一栈加入新的元素。 试定义这种双栈 (Double判栈满、插入、删除算法Stack）结构的类型定义，并实现初始化、判栈空、0 m-1-1 top0 top1 m 类型定义：#define m 100；Typedef int dsType； /双栈的元素类型Typedef structint top2 ; /双栈的栈顶指针和栈底指针dsType Vm ;/栈数组 DoubleStack ；初始化空双栈算法：InitdStack(D

4、oubleStack &ds ) /初始化空双栈 dsds.top0=-1;ds.top1=m;判栈空算法：int DStackEmpty(DoubleStack ds , int i) /判断双栈 ds的第 i(0或 1)个栈是否为空，空则返回 1，否则返回 0 if (i=0 & ds.top0=-1)return 1;if (i=1 & ds.top1=m)return 1;return 0;3-2. 试利用算符优先法，画出对如下中缀算术表达式求值时运算符栈和操作数栈的变化。 a + b * （c - d） e# （ #表示结束符）步序扫描项项类型动作OPND 栈变化OPTR 栈变化0O

5、PTR 栈与 OPND 栈初始化 , #进 OPTR 栈, 取第一个符号#1a操作数a 进OPND栈, 取下一符号a#2+操作符 + # ,进 OPTR 栈, 取下一符号a#+3-3 分别写出顺序循环队列队列 Q 状态为“空”还是“满”的条件和计算队列中元素个数的公式。第四章设有模式串 T1,T2，T1=aaab，T2=abcabaa，目标串 s为abc aaabbabcabaacbacb，a1)计算模式串 T1 的 next(j) 和 nextval(j) 函数的值 ,并(按照 nextval(j) )画出 KMP 算法匹配过程。2)计算模式串 T2 的 next(j) 和 nextval(

6、j) 函数的值 ,并(按照 nextval(j) )画出 KMP 算法匹配过程。学号尾数为奇数做第(1)题；偶数做第( 2)题第五章5- 1 设有一个二维数组 Am n(按照列优先存储， m、n均大于 5)，假设 A00存放位置在 644(10)，A23 存放位置 在 676(10)，每个元素占一个空间，问 A44 (10)存放在什么位置？脚注 (10)表示用 10 进制表示。5- 2 假二维数组 A9 3 5 8，第一个元素的字节地址是 1000，每个元素占 6个字节。问下列元素的存储地址是什么？(1) a0000 (2)a8247( 3)按行优先存储(最左下标优先)时a3125的地址(4)

7、按照列优先存储(最右下标优先)时a1111的地址5- 3 矩阵 (aij)n n 的压缩存储方式 ,我们把它们按行存放于一个一维数组B 中:(1) 设有一个 n n的下三角矩阵 A，如图 (a)所示。为了节约存储，只存对角线或对角线以下的元素。若在一维数组B中从 0号位置开始存放，则下三角矩阵中的任一元素aij 在应存于一维数组的什么下标位置？给出计算公式。(2) 设有一个 n n的上三角矩阵 A，如图 (b)所示。为了节约存储，只存对角线及对角线以上的元素，若在一维数组B中从 0号位置开始存放，则上三角矩阵中的任一元素aij 在应存于一维数组的什么下标位置？给出计算公式。图(b)5- 4 利

8、用广义表和 tail 操作写出函数表达式，把以下各题中的单元素banana从广义表中分离出来：(1) L1(apple, pear, banana, orange)(2) L2(apple, pear), (banana, orange)(3) L3(apple), (pear), (banana), (orange)5- 5 画出广义表 L 的存储结构图并求出它的深度：L=( ( ), a,(b,c),( ),d),(e) )第六章6- 1 在结点个数为 n (n1)的各棵树中，深度最小的树的深度是多少？它有多少个叶结点？多少个分支结点？深度最大 的树的高度是多少？它有多少个叶结点？多少个分

9、支结点？6- 2 如果一棵度为 k的树有 n1个度为 1的结点, 有n2个度为 2的结点, , nk个度为 k的结点, 试问有多少个度为 0的结点(叶子结点) ? 试推导之。 6-36-4 序、如果一棵含有 n 个结点的树中，只有度为 k 的分支结点和度为 0 的叶子结点。试问该树叶子结点的数目。 使用 (1) 顺序表示和 (2) 二叉链表表示法，分别画出下图所示二叉树的存储表示。( 3)分别求出该二叉树的先6-56-6试分别找出满足以下条件的所有二叉树(1) 二叉树的前序序列与中序序列相同(2) 二叉树的中序序列与后序序列相同(3) 二叉树的前序序列与后序序列相同。 请画出右图所示的森林所对

10、应的二叉树1)先序全线索化2)中序全线索化10, 并分别按以下说明进行线索化。( 3)后续后继线索化12111314156- 7 已知一棵二叉树的前序遍历的结果是 【解答】当前序序列为ABECDFGHIJ, 中序遍历的结果是 EBCDAFHIGJ, 试画出这棵二叉树。T:树的先根次序访问序列为：6- 8 画出和下列已知序列对应的树 DIAEKFCJHBG 。6- 9 画出和下列已知序列对应的森林 CBEFDGAJIKLH 。F: 森林的先序访问序列为：GFKDAIEBCHJ ；树的后根次序访问序列为：ABCDEFGHIJKL ；森林的中序访问序列为：中序、后序遍历序列。6-10 假定用于通信的

11、电文仅由 8个字母 c1, c2, c3, c4, c5, c6, c7, c8 组成, 各字母在电文中出现的频率分别为 0.07, 0.19,0.02, 0.06,0.32, 0.03, 0.21, 0.10 。试为这 8个字母设计不等长 Huffman 编码, 并给出该电文的总码数。使用07 的二进制表示形式是另一种编码方案。对于上述实例，比较两种方案的优缺点。C332210107C1C802110064是最优方案。若等7- 1在 n个顶点的无向完全图中，边的条数为（第 7 章 图n（n- 1）/2 ）。画出 4 个顶点的无向完全图。带权路径长度 WPL=（0.02+0.03）*5+（0.

12、06+0.07+0.10）*4+（0.32+0.19+0.21）*2=2.61. 带权路径长度最短， 长 C1 至 C8 编码分别为 000111，平均长度为 3，大于 2.61 。c1c2c3c4c5c6c7c80010100000000010100001110011二、算法设计题：1、 编写递归算法，将二叉树（用二叉链表作为二叉树的存储表示）中所有结点的左、右子树相互交换。2、 编写递归算法，计算二叉树（用二叉链表存储表示）中叶子结点的数目。3、编写按层次遍历二叉树的算法。7- 2 下面判断下面的有向图是强连通图吗？若不是强连通图，有几个强连通分量？G1 不是强连通图，有 6 个强连通分量

13、（每个顶点分别是 1 个强连通分量）G2 是强连通图 （只有 1 个强连通分量，就是 G2 本身 ）G3 不是强连通图，有 3 个强连通分量 .：7-3 给出上图 G3 的邻接矩阵、邻接表、逆邻接表。（1） 邻接矩阵010100001010Edge0000010100100000000000103（给出图 G1 的邻接矩阵、邻接表、逆邻接表、邻接多重表（十字链表）（2） 邻接表012345逆邻接表）（3）邻接多重表（十字链表）7- 4 用邻接矩阵表示图时，矩阵元素的个数与顶点个数是否相关？与边的条数是否相关？ 用邻接矩阵表示图，矩阵元素的个数是顶点个数的平方（即 n 个顶点，矩阵是 nn），与

14、边的条数无关。矩阵中非零元素的个数与边的条数有关（无向图非零元素的个数是边数的2 倍；有向图非零元素的个数等于边数） 。【解答】7- 5 有 n（ n1）个顶点的无向连通图至少有多少条边？有n 个顶点的有向强连通图至少有多少条边？试举例说明。n个顶点的无向连通图至少有 n-1条边， n个顶点的有向强连通图至少有 n条边。例如：7- 6 对于有 n 个顶点的无向图，采用邻接矩阵表示，如何判断以下问题： 图中有多少条边？任意两个顶点 i 和 j 之间 是否有边相连？任意一个顶点的度是多少？用邻接矩阵表示无向图时，因为是对称矩阵，对矩阵的上三角部分或下三角部分检测一遍，统计其中的非零元素 个数，就是

15、图中的边数。如果邻接矩阵中 Aij 不为零，说明顶点 i与顶点 j 之间有边相连。此外统计矩阵第 i 行或 第 i 列的非零元素个数，就可得到顶点 i 的度数。7-7 对于如右图所示的有向图，试写出：(1) 从顶点出发进行深度优先搜索所(2) 从顶点出发进行广度优先搜索所1) 从顶点出发进行深度优先遍历不唯一，7-8 利用普里姆( prim 和克鲁斯卡尔 (Kruskal) 算法，求下图的最小生成树。prim 算法147-9 试对右图所示的 AOE 网络，解答下列问题。(1) 这个工程最早可能在什么时间结束。(2) 求每个事件的最早开始时间 Vei 和最迟开 Vli 。(3) 求每个活动的最早

16、开始时间 e(i) 和最迟开始(4) 确定哪些活动是关键活动。 画出由所有关键 的图，指出哪些活动加速可使整个工程提前完成。按拓扑有序的顺序计算各个顶点的最早可能开始时间始时间 时间 l(i) 。活动构成Ve 和最迟允许开始时间 Vl 。然后再计算各个活动的最早可能开始时间 e和最迟允许开始时间 l，根据 l - e = 0? 来确定关键活动，从而确定关键路径。123456Ve01915293843Vl01915373843e00151919152938l170152719273738l- e1700801280源点终点最短路径最短路径长度AB(A,B)(A,B)(A,B)(A,B)10101

17、010C(A,C)(A,C)(A,C)(A,C)18181818D(A,B,D)(A,B,D)(A,B,D)151515E(A,B,D,E)(A,B,D,E)17177-10 以右图为例，按 Dijkstra 算法计算得到的从顶点 (A) 到其它各个顶点的此工程最早完成时间为 43。关键路径为 第八章 查找表习题8- 1 设有序顺序表中的元素依次为 017, 094, 154, 170, 275, 503, 509, 512, 553, 612, 677, 765, 897, 908 。试画出对其进行折 半查找时的二叉判定树 , 并计算查找成功的平均查找长度和查找不成功的平均搜索长度。8- 2

18、 设有一个输入数据的序列是 46, 25, 78, 62, 12, 37, 70, 29 , 试画出从空树起，逐个输入各个数据而生成的二叉排序树。8- 3 将关键码 DEC, FEB, NOV, OCT, JUL, SEP, AUG , APR, MAR, MAY , JUN, JAN 依次插入到一棵初始为空的 AVL 树 (平衡二叉树)中，画出每插入一个关键码后的 AVL 树，并标明平衡旋转的类型。8- 4设散列表为 HT13, 散列函数为 H (key) = key %13。用闭散列法解决冲突 , 对下列关键码序列 12, 23, 45, 57, 20, 03, 78, 31, 15, 3

19、6 造表。采用线性探查法寻找下一个空位 , 画出相应的散列表 , 并计算等概率下搜索成功的平均搜索长度和 搜索不成功的平均搜索长度。(2) 采用双散列法寻找下一个空位 , 再散列函数为 RH (key) = (7* key) % 10 + 1, 寻找下一个空位的公式为 Hi = (Hi-1 + RH ( key) % 13, H1 = H ( key)。画出相应的散列表 , 并计算等概率下搜索成功的平均搜索长度。第九章作业1、设待排序的排序码序列为 说明做了多少次排序码比较。12, 2, 16, 30, 28, 10, 16*, 20, 6, 18, 试分别写出使用以下排序方法每趟排序后的结果

20、。并(1) 直接插入排序(2)(5)(8)希尔排序 (增量为 直接选择排序 二路归并排序5,2,1)(3)(6)起泡排序基数排序(4)(7)快速排序堆排序解答】(1)直接插入排序初始排列 0 123456789排序码比较次数i =1 12 216302810*16*206181*i =2 2 12 1630281016*206181i =3 2 1216 302810*16*206181i =4 2 121630 2810*16*206182*i =5 2 12162830 1016*206185*i =6 2 1012162830 16*206183i = 7 21012 1616 28i

21、= 8 21012 1616* 20i = 9 2610 1216 16* 2610 12*16 16*(2) 希尔排序 (增量为5,2,1)初始排列012 34 512216 3028 10d = 530 20618328 30 618320 2830 18818 202830 6789排序码比较次数*16*206181+1+1+1+1 = 510 2 16 6 18 12 16* 20 30 28 (1+1+2+1) + (1+1d = 2+1+1) = 910 2 166 16* 12 18 20 30 281+1+3+1+3+1+1d = 1+1+2 = 142 6 10 12 161

22、6* 18 20 28 30希尔(shell)本人采取的增量序列为n/2 , n/2 /2 , n/2 /2 /2 , ,1。一般地，增量序列可采用 n , n ,n , , 1。大量实验表明，取=0.45454 的增量序列比取其他的增量序列的优越性更显著。 计算 0.45454n 的 一个简单方法是用整数算术计算 (5*n-1)/11。需要注意，当 1/2 时，增量序列可能不以 1结束，需要加以判断和调整。(3) 起泡排序初始排列0123456789排序码比较次数i = 0 12216302810*16*20618 9*i = 12 12616302810162018 8i = 226 12

23、1016302816*1820 7i = 32610 121616*30281820 6i = 4261012 1616*18302820 5i = 526101216 16 *18203028 4i = 626101216*16* 18202830 326101216*16*18202830(4)快速排序PivotPvtpos0123456789排序码比较次数120,1,2,3 12216302810*16*20618 9pospos pospos60,1 6210 12 2816*16*203018 2pospos284,5,6,7,8 2 6 10 12 2816*16*203018 5

24、pos pospospospos184,5,6261012 1816*16*20 28 30 3pos pos pos16 4261012 16 16 * pos18 20 2830126101216* 16 18202830左子序列递归深度为1，右子序列递归深度为3。(5) 直接选择排序初始排列0123456789排序码比较次数i = 0 12216302810*16*20618 9i = 12 1216302810*16*20618 8i = 226 16302810*16*201218 7i = 32610 302816*16*201218 6i = 4261012 2816*16*203018 5i = 526101216 28*16*203018 4i = 62610121616* 28203018 3i = 7261012