数据结构作业题.doc
《数据结构作业题.doc》由会员分享,可在线阅读,更多相关《数据结构作业题.doc(11页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、【精品文档】如有侵权,请联系网站删除,仅供学习与交流数据结构作业题.精品文档.第一章1、设n为正整数,利用大O记号,将下列程序段的执行时间表示为n的函数。 (1) i=1; k=0;while(in) k=k+10*i;i+; (2) i=0; k=0; dok=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、按增长率由小至大的顺序排列下列各函数
2、:2100, (3/2)n,(2/3)n, nn ,n0.5 , 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号栈插入一个新元素时,
3、使top0增1得到新的栈顶位置,当向第1号栈插入一个新元素时,使top1减1得到新的栈顶位置。当top0+1 = top1时或top0 = top1-1时,栈空间满,此时不能再向任一栈加入新的元素。试定义这种双栈(Double Stack)结构的类型定义,并实现初始化、判栈空、判栈满、插入、删除算法。-1 top0 top1 m0 m-1【提示】类型定义:#define m 100;Typedef int dsType;/双栈的元素类型Typedef structint top2; /双栈的栈顶指针和栈底指针dsType Vm;/栈数组 DoubleStack;初始化空双栈算法:InitdSt
4、ack(DoubleStack &ds ) /初始化空双栈dsds.top0=-1;ds.top1=m;判栈空算法:int DStackEmpty(DoubleStack ds , int i) /判断双栈ds的第i(0或1)个栈是否为空,空则返回1,否则返回0if (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栈变化0F OP
5、TR栈与OPND栈初始化, # 进OPTR栈, 取第一个符号#1a操作数F a 进OPND栈, 取下一符号a#2+操作符F + #, 进OPTR栈, 取下一符号a#+3-3 分别写出顺序循环队列队列Q状态为“空”还是“满”的条件和计算队列中元素个数的公式。第四章 设有模式串T1,T2,T1=aaab,T2=abcabaa,目标串s为abc aaabbabcabaacbacba,(1)计算模式串T1的next(j) 和nextval(j)函数的值,并(按照nextval(j) )画出KMP算法匹配过程。(2)计算模式串T2的next(j) 和nextval(j)函数的值,并(按照nextval(
6、j) )画出KMP算法匹配过程。学号尾数为奇数做第(1)题;偶数做第(2)题第五章 5-1 设有一个二维数组Amn(按照列优先存储,m、n均大于5),假设A00存放位置在644(10),A23存放位置在676(10),每个元素占一个空间,问A44(10)存放在什么位置?脚注(10)表示用10进制表示。5-2假二维数组A9358,第一个元素的字节地址是1000,每个元素占6个字节。问下列元素的存储地址是什么?(1)a0000 (2)a8247 (3)按行优先存储(最左下标优先)时a3125的地址 (4)按照列优先存储(最右下标优先)时a1111的地址5-3矩阵(aij)nn的压缩存储方式,我们把
7、它们按行存放于一个一维数组B中:(1)设有一个nn的下三角矩阵A,如图(a)所示。为了节约存储,只存对角线或对角线以下的元素。若在一维数组B中从0号位置开始存放,则下三角矩阵中的任一元素aij在应存于一维数组的什么下标位置?给出计算公式。(2)设有一个nn的上三角矩阵A,如图(b)所示。为了节约存储,只存对角线及对角线以上的元素,若在一维数组B中从0号位置开始存放,则上三角矩阵中的任一元素aij在应存于一维数组的什么下标位置?给出计算公式。a11 a12 a13 a1n a22 a23 a2n a33 a3n ann图(b) 图(b)05-4 利用广义表和tail操作写出函数表达式,把以下各题
8、中的单元素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)的各棵树中,深度最小的树的深度是多少?它有多少个叶结点?多少个分支结点?深度最大的树的高度是多少?它有多少个叶结点?多少个分支结点? 6-2 如果一棵度为k的树有n1个度为1的结点,
9、有n2个度为2的结点, , nk个度为k的结点, 试问有多少个度为0的结点(叶子结点)? 试推导之。6-3 如果一棵含有n个结点的树中,只有度为k的分支结点和度为0的叶子结点。试问该树叶子结点的数目。6-4 使用 (1) 顺序表示和 (2) 二叉链表表示法,分别画出下图所示二叉树的存储表示。(3)分别求出该二叉树的先序、中序、后序遍历序列。6-5 试分别找出满足以下条件的所有二叉树:(1) 二叉树的前序序列与中序序列相同;(2) 二叉树的中序序列与后序序列相同;(3) 二叉树的前序序列与后序序列相同。6-6 请画出右图所示的森林所对应的二叉树,并分别按以下说明进行线索化。(1)先序全线索化 (
10、2)中序全线索化 (3)后续后继线索化121131411921054315768 6-7 已知一棵二叉树的前序遍历的结果是ABECDFGHIJ, 中序遍历的结果是EBCDAFHIGJ, 试画出这棵二叉树。【解答】当前序序列为ABECDFGHIJ,中序序列为EBCDAFHIGJ时,逐步形成二叉树的过程如下图所示: AAAAFBBFFBGECGECHIGJCDEFHIGJHDJHIJDIEBCD6-8画出和下列已知序列对应的树T:树的先根次序访问序列为:GFKDAIEBCHJ;树的后根次序访问序列为:DIAEKFCJHBG。6-9画出和下列已知序列对应的森林F: 森林的先序访问序列为:ABCDEF
11、GHIJKL;森林的中序访问序列为:CBEFDGAJIKLH。6-10 假定用于通信的电文仅由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的二进制表示形式是另一种编码方案。对于上述实例,比较两种方案的优缺点。101001019214002030710628051106173260 10C5C7C2100110C8C410C1C6C3带权路径长度WPL=(0.02+0
12、.03)*5+(0.06+0.07+0.10)*4+(0.32+0.19+0.21)*2=2.61.带权路径长度最短,是最优方案。若等长C1至C8编码分别为000111,平均长度为3,大于2.61。 c1 c2 c3 c4 c5 c6 c7 c8 0010 10 00000 0001 01 00001 11 0011 二、算法设计题:1、 编写递归算法,将二叉树(用二叉链表作为二叉树的存储表示)中所有结点的左、右子树相互交换。2、 编写递归算法,计算二叉树(用二叉链表存储表示)中叶子结点的数目。3、 编写按层次遍历二叉树的算法。第7章 图7-1在n个顶点的无向完全图中,边的条数为(n(n-1)
13、/2 )。画出4个顶点的无向完全图。1234567-2 下面判断下面的有向图是强连通图吗?若不是强连通图,有几个强连通分量?ABCDEFABCDEF G1 G2 G3G1不是强连通图,有6个强连通分量(每个顶点分别是1个强连通分量)G2是强连通图 (只有1个强连通分量,就是G2本身)56G3不是强连通图,有3个强连通分量.:12347-3 给出上图G3的邻接矩阵、邻接表、逆邻接表。DA(给出图G1的邻接矩阵、邻接表、逆邻接表、邻接多重表(十字链表)大家自己画G3)(1) 邻接矩阵EBFC310 A1 B2 C3 D4 E5 F(2) 邻接表4254140 A1 B2 C3 D4 E5 F(逆邻
14、接表)30105312data fin fout(3) 邻接多重表(十字链表)i j ilink jlink0 1 (A, B)0 A1 B2 C3 D4 E5 F0 3 (A, D)1 2 (B, C)1 4 (B, E)2 5 (C, F)3 1 (D, B)3 4 (D, E)5 4 (F, E)7-4 用邻接矩阵表示图时,矩阵元素的个数与顶点个数是否相关?与边的条数是否相关?用邻接矩阵表示图,矩阵元素的个数是顶点个数的平方(即n个顶点,矩阵是nn),与边的条数无关。矩阵中非零元素的个数与边的条数有关(无向图非零元素的个数是边数的2倍;有向图非零元素的个数等于边数)。【解答】7-5 有n
15、(n1)个顶点的无向连通图至少有多少条边?有n个顶点的有向强连通图至少有多少条边?试举例说明。n个顶点的无向连通图至少有n-1条边,n个顶点的有向强连通图至少有n条边。例如:7-6对于有n个顶点的无向图,采用邻接矩阵表示,如何判断以下问题: 图中有多少条边?任意两个顶点i和j之间是否有边相连?任意一个顶点的度是多少?用邻接矩阵表示无向图时,因为是对称矩阵,对矩阵的上三角部分或下三角部分检测一遍,统计其中的非零元素个数,就是图中的边数。如果邻接矩阵中Aij 不为零,说明顶点i与顶点j之间有边相连。此外统计矩阵第i行或第i列的非零元素个数,就可得到顶点i的度数。7-7对于如右图所示的有向图,试写出
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 作业题
限制150内