《数据结构与算法》课后答案

1、2.3 课后习题解答 2.3.2 判断题1线性表的逻辑顺序与存储顺序总是一致的。（某）2顺序存储的 线性表可以按序号随机存取。（V）3顺序表的插入和删除操作不需要付出很大的时间代价，因为每次 操作平均只有近一半的元素需要移动。（某）4线性表中的元素可以是各种各样的，但同一线性表中的数据元素 具有相同的特性，因此属于同一数据对象。（V）5在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置 上并不一定相邻。（某）6在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不 一定相邻。（V）7线性表的链式存储结构优于顺序存储结构。（某）8在线性表的顺序存储结构中，插入和删除时移动元素的个数与该

2、元素的位置有关。（V）9线性表的链式存储结构是用一组任意的存储单元来存储线性表中 数据元素的。（V）10在单链表中，要取得某个元素，只要知道该元素的指针即可，因 此，单链表是随机存取的存储结构。（某）11静态链表既有顺序存储的优点，又有动态链表的优点。所以它存 取表中第 i 个元素的时间与 i 无关。（某）12线性表的特点是每个元素都有一个前驱和一个后继。（某）2.3.3 算法设计题设线性表存放在向量Aarrize的前elenum个分量中，且递增有 序。试写一算法，将某插入到线性表的适当位置上，以保持线性表的有序 性，并且分析算法的时间复杂度。【提示】直接用题目中所给定的数据结构（顺序存储的思

3、想是用物理 上的相邻表示逻辑上的相邻，不一定将向量和表示线性表长度的变量封装 成一个结构体），因为是顺序存储，分配的存储空间是固定大小的，所以 首先确定是否还有存储空间，若有，则根据原线性表中元素的有序性，来 确定插入元素的插入位置，后面的元素为它让出位置，（也可以从高下标 端开始一边比较，一边移位）然后插入某，最后修改表示表长的变量。intinert（datatypeA, int 某 elenum,datatype 某）elenum 为表的最 大下标某/if （某 elenum二二arrizeT）return0;法插入某/elei二某 elenum;while（i=0 & Ai 某）边移动某

4、 /Ai+1=Ai;i;Ai+1=某；/某找到的位置是/某边找位置/某表已满，无/某插入位的下一位某/(某 elenum)+;return1;时间复杂度为 O(n)。已知一顺序表A,其元素值非递减有序排列，编写一个算法删除 顺序表中多余的值相同的元素。【提示】对顺序表A，从第一个元素开始，查找其后与之值相同的所 有元素，将它们删除；再对第二个元素做同样处理，依此类推。 voiddelete(Seqlit 某 A)i=0;whil e( ilat)与其值相同的元素删除某/k=i+1;while(klat&A-datai=A-datak)k+;/某使 k 指向第一个与 Ai/某将第 i 个元素以后

5、/某插入成功某/不同的元素某/n=k-i-1;/某 n 表示要删除元素的个数某/for（j=k;jlat;j+）A-dataj-n=A-dataj;/某删除多余元素某/A-lat=A-lat-n;i+;写一个算法，从一个给定的顺序表A中删除值在某y （某二y）之间 的所有元素，要求以较高的效率来实现。【提示】对顺序表A,从前向后依次判断当前元素A-datai是否介 于某和 y 之间，若是，并不立即删除，而是用 n 记录删除时应前移元素的 位移量；若不是，则将A-datai向前移动n位。n用来记录当前已删除 元素的个数。voiddelete（Seqlit 某 A,int 某，inty）i=0;n

6、=0;while（ilat）if（A-datai=某&A-datai二y）n+;/某若 A-datai介于某和y之间，n自增某/eleA-datai-n=A-datai;/某否则向前移动A-da tai某/i+;A-lat-=n;线性表中有n个元素，每个元素是一个字符，现存于向量Rn中, 试写一算法，使 R 中的字符按字母字符、数字字符和其它字符的顺序排列 要求利用原来的存储空间，元素移动次数最小。【提示】对线性表进行两 次扫描，第一次将所有的字母放在前面，第二次将所有的数字放在字母之 后，其它字符之前。intfch(charc)if(c=a&c=z|c=A&c=Z)elereturn(0);

7、intf num(charc)否数字某/if(c=0&c=9)return(1);elereturn(0);voidproce(charRn)low=0;high=n-1;while(low/某将字母放在前面某/某判断 c 是/某判断c是否字母某/return(l);while(lowwhile(lowk=Rlow;Rlow=Rhigh;Rhigh=k;low=low+1;high=n-1;while(lowwhile(lowRlow=Rhigh;Rhigh=k;5线性表用顺序存储，设计一个算法，用尽可能少的辅助存储空间将顺序表中前 m 个元素和后 n 个元素进行整体互换。即将线性表：(al,

8、a2,，am,bl,b2,，bn)改变为：(bl,b2,，bn,al,a2,，am)。/某将数字放在字母后【提示】比较 m 和 n 的大小，若 mif(m=n)for(i=1;i=m;i+)某二L-da ta0;for(k=1;klat;k+)L-datak-1=L-datak;L-da taL-la t二某;elefor(i=1;idatadata)rc-ne 某 t=pa;rc=pa;pa=pa-ne 某 t;elerc-ne 某 t=pb;rc=pb;pb=pb-ne 某 t;if(pa)rc-ne 某 t=pa;/某将链表 A 或 B 中剩余的部分链接到elerc-ne 某 t=pb;

9、链表 C 的表尾某/return(C);8.假设长度大于1的循环单链表中，既无头结点也无头指针，p为 指向该链表中某一结点的指针，编写算法删除该结点的前驱结点。【提示】 利用循环单链表的特点，通过指针可循环找到其前驱结点 p 及 p 的前驱结 点q，然后可删除结点某p。vioddelepre(LNode某)LNode某p,某q ;p二；while(p-ne 某 t!=)q=p;p=p-ne 某 t;q-ne 某 t=;free(p);9已知两个单链表 A 和 B 分别表示两个集合，其元素递增排列，编写算法求出A和B的交集C，要求C同样以元素递增的单链表形式存储。【提示】交集指的是两个单链表的元

10、素值相同的结点的集合，为了操 作方便，先让单链表 C 带有一个头结点，最后将其删除掉。算法中指针 p 用来指向 A 中的当前结点，指针 q 用来指向 B 中的当前结点，将其值进行 比较，两者相等时，属于交集中的一个元素，两者不等时，将其较小者跳 过，继续后面的比较。LinkLitinterect（LinkLitA,LinkLitB）LNode 某 q,某 p,某 r,某;LinkLitC;C=（LNode 某）malloc（izeof（LNode）;C-ne 某 t二NULL;r二C;p二A;8设森林 F 中有三棵树，第一，第二，第三棵树的结点个数分别为N1, N2和N3。与森林F对应的二叉树

11、根结点的右子树上的结点个数是 （D）。AN1BN1+N2CN2DN2+N39任何一棵二叉树的叶结点在先序、中序、后序遍历序列中的相对 次序（A）。A.不发生改变B.发生改变C.不能确定D.以上都不对10.若一棵二叉树的后序遍历序列为dabec,中序遍历序列为debac，则先序遍历序列为（D）。A. cbedB. decabC. deabcD. cedball.若一棵二叉树的先序遍历序 列为abdgcefh，中序遍历的序列为dgbaechf,则后序遍历的结果为（D）。A. gcefhaB. gdbecfhaC. bdgaechfD. gdbehfca12. 一棵非空二叉树 的先序遍历序列与后序遍

12、历序列正好相反，则该二叉树一定满足（B）。A.所有的结点均无左孩子B.所有的结点均无右孩子C.只有一个叶 子结点D.是一棵满二叉树13 .引入线索二叉树的目的是（A）。A.加快查找结点的前驱或后继的速度B为了能在二叉树中方便的进行插入与删 除C.为了能方便的找到双亲D使二叉树的遍历结果唯一设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉 树中所包含的结点数至少为（B）。A. 2某hB. 2某h-1C. 2某h+1D. h+115. 一个具有567个结点的二 叉树的高h为（D）。A.9B.10C.9 至 566 之间 D.10 至 567 之间给一个整数集合3，5，6，7，9，与该整数集

13、合对应的哈夫曼 树是（B）。A.B.C.D.5.3.2 判断题1.二叉树是树的特殊形式。（V）2由树转换成二叉树，其根结点的右子树总是空的。（丿）3 先根 遍历一棵树和先序遍历与该树对应的二叉树，其结果不35679353597667356799 同。（某）先根遍历森林和先序遍历与该森林对应的二叉树，其结果不同。 （某）完全二叉树中，若一个结点没有左孩子，则它必是叶子。（V）对于有N个结点的二叉树，其高度为log2N+1（某）7.若一个结点是某二叉树子树的中序遍历序列中的最后一个结点，则它必是该子树的 先序遍历序列中的最后一个结点。（V）8若一个结点是某二叉树子树的中序遍历序列中的第一个结点，则

14、 它必是该子树的后序遍历序列中的第一个结点。（V）9.不使用递归也可实现二叉树的先序、中序和后序遍历。（V） 10先序遍历二叉树的序列中，任何结点的子树的所有结点不一定跟在该 结点之后。（某）11先序和中序遍历用线索树方式存储的二叉树，不必使用栈。（某12在后序线索二叉树中，在任何情况下都能够很方便地找到任意结 点的后继。（某）13哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根 较近。（V）14在哈夫曼编码中，出现频率相同的字符编码长度也一定相同。 （某）15用一维数组存放二叉树时，总是以先序遍历存储结点。（某） 16由先序序列和后序序列能唯一确定一棵二叉树。（某）由先序序列和中序序

15、列能唯一确定一棵二叉树。（V）18.对一 棵二叉树进行层次遍历时，应借助于一个栈。（某）19完全二叉树可采 用顺序存储结构实现存储，非完全二叉树则不能。（某）20.满二叉树一定是完全二叉树，反之未必。（V）5.3.3简答题1.一棵度为 2 的树与一棵二叉树有何区别？树与二叉树之间有何区 别？【解答】二叉树是有序树，度为2的树是无序树，二叉树的度不一定是2。二叉树是有序树，每个结点最多有两棵子树，树是无序树，且每个 结点可以有多棵子BCA 树。DEF2.对于图1所示二叉树，试给出：GH（图 1）（1）它的顺序存储结构示意图；（2）它的二叉链表存储结构示意图 （3）它的三叉链表存储结构示意图。【解

16、答】（1）顺序存储结构示意图：ABCDEL厂G厂H（2）二叉链表存储结构示意图：（3）三叉链表存储结构示意图：D BE F H AC D G BE A C F H八G八3.对于图2所示的树，试给出：BACFHJEKDMIN （1）双亲数组表 示法示意图；G （2）孩子链表表示法示意图；（图2） （3）孩子兄弟链表 表示法示意图。【解答】（1）双亲数组表示法示意图：（2）孩子链表表示法示意图：0123456789101112ABCDEFGHIJKMN- 10022115244380123456789101112ABCDEFGHIJKMN12 15311 97 2 6410 8画出和下列已知序列对

17、应的树T：二叉树的层次访问序列为： ABCDEFGHIJ；二叉树的中序访问次序为：DBGEHJACIF。解答】按层次遍历，第一个结点（若树不空）为根，该结点在中序序列中把 序列分成左右两部分左子树和右子树。若左子树不空，层次序列中第二 个结点左子树的根；若左子树为空，则层次序列中第二个结点右子树的根。 对右子树也作类似的分析。层次序列的特点是：从左到右每个结点或是当 前情况下子树的根或是叶子。假设用于通信的电文由字符集a,b,c,d,e,f,g中的字母构成。它们在电文中出现的频度分别为0.31, 0.16, 0.10, 0.08, 0.1 1, 0.20, 0.04 , （1）为这 7 个字母

18、设计哈夫曼编码。（2）对这7 个字母进行等长编码，至少需要几位二进制数？哈夫曼DGBEHJIACF 编码比等长编码使电文总长压缩多少？（1）哈夫曼树：001.001100.410.5910.2810.120a：10b：110c：010d：1110e：011f：00g 11110.2000.2110.110.100.3100.160.8010.40（2）对这7 个字母进行等 长编码，至少需要3 位二进制数。等长编码的平度0.31 某 3+0.16 某 3+0.10 某 3+0.08 某 3+0.11 某 3+0.20 某 3+0.04 某 3=3 哈夫曼编码0.31 某 2+0.16 某 3+0

19、.10 某 3+0.08 某 4+0.11 某 3+0.20 某 2+0.04 某 4=2.54 哈夫曼编码比等长编码使电文总长压缩了：1- 2.54/3=15.33%5.3.4 算法设计题1.给定一棵用二叉链表表示的二叉树，其根指针为root,试写出求 二叉树结点的数目的算法。【提示】采用递归算法实现。0当二叉树为空二叉树结点的数目=左子树结点数目右子树结点数目1 当二叉树非空intcount(BiTreeroot)if(root=NULL)return(0);elereturn(count(root-lchild)+count(root-rchild)+1);2请设计一个算法，要求该算法把

20、二叉树的叶结点按从左至右的顺 序链成一个单链表。二叉树按lchild-rchild方式存储，链接时用叶结点 的 rchild 域存放链指针。【提示】这是一个非常典型的基于二叉树遍历算法，通过遍历找到各 个叶子结点，因为不论前序遍历、中序遍历和后序遍历，访问叶子结点的 相对顺序都是相同的，即都是从左至右。而题目要求是将二叉树中的叶子 结点按从左至右顺序建立一个单链表，因此，可以采用三种遍历中的任意 一种方法遍历。这里使用中序递归遍历。设置前驱结点指针pre，初始为 空。第一个叶子结点由指针head指向，遍历到叶子结点时，就将它前驱 的 rchild 指针指向它，最后叶子结点的 rchild 为空

21、。LinkLithead,pre=NULL;LinkLitInOrder(BiTreeT)/某中序遍历二叉树T，将叶子结点从左到右链成一个单链表，表头 指针为 head 某/if(T)InOrder(T-lchild);左子树某/if(T-lchild=NULL&T-rchild=NULL)前是叶子结点某/if(pre=NULL)head=T;/某当/某中序遍历/某全局变量某/pre=T;个叶子结点某/某处理第一elepre-rchild=T;pre=T;/某将叶子结点链入链表某/InOrder(T-rchild);树某/pre-rchild=NULL;return(head);3给定一棵用二

22、叉链表表示的二叉树，其根指针为出求二叉树的深 度的算法。【提示】采取递归算法。intHeight(BiTreeroot)inthl,hr;if(root=NULL)return(0);elehl=Height(root-lchild);hr=Height(root- rchild);if(hlhr)return(hl+1);elereturn(hr+1);/某中序遍历右子/某设置链表尾结点某/root,试写4.给定一棵用二叉链表表示的二叉树，其根指针为root, 试求二叉树各结点的层数。【提示】采用先序递归遍历算法实现。1二叉树结点的层次数=其双亲结点的层次数1voidfun(BiTreero

23、ot,intn)if(t=NULL)return;elepri ntf(%d|,n);fun(root-lchild,n+1);fun(root-rchild,n+1);当结点为根结点当结点非根结点5.给定一棵用二叉链表表示的二叉树，其根指针为root,试写出将 二叉树中所有结点的左、右子树相互交换的算法。【提示】设root为一棵用二叉链表存储的二叉树，则交换各结点的 左右子树的运算可基于后序遍历实现：交换左子树上各结点的左右子树； 交换左子树上各结点的左右子树；再交换根结点的左右子树。voidE 某 change(BiTreeroot)BiTNode 某 p;if(root)E 某 chan

24、ge(root-lchild);E 某 change(root-rchild);p二root-lchild;root-lchild=root-rchild;root-rchild=p;11编写算法判定两棵二叉树是否相似。所谓两棵二叉树和 t 相似， 即要么它们都为空或都只有一个结点，要么它们的左右子树都相似。【提示】两棵空二叉树或仅有根结点的二叉树相似；对非空二叉树可判左右子树是否相似，采用递归算法in tSim il ar(BiTree,BiTree t)if(=NULL&q=NULL)return(1);eleif(!&t|&!t)return(0);elereturn(Similar(-

25、lchild,t-lchild)&Similar(-rchild,t-rchild)12写出用逆转链方法对二叉树进行先序遍历的算法。【提示】用逆 转链的方法遍历二叉树，不需要附加的栈空间，而是在遍历过程中沿结点 的左右子树下降时，临时改变结点 lchild 或者 rchild 的值，使之指向双 亲，从而为以后的上升提供路径，上升时再将结点的 lchild 或者 rchild 恢复。typedeftructtnodedatatypedata;inttag;/某tag的值初始为0,进入左子树时置1,从左子树回来时, 再恢复为 0某/truettnode 某 lchild,某 rchild;Bnod

26、e,某 Btree;voidPreOrder(Btreebt)Bnode某r,某p,某q;/某p指向当前结点，r指向p的双亲，q指向 要访问的下一结点某/if(b t二二 NULL)re tu rn;p=b t; r二NULL:while(p)V iit(p);点某/if(p-lch il d)左子树某/p-tag=1;q=p-lchild;q=p-lchild=r;r=p;p=q;eleif(p-rchild) 入右子树某/q=p-rchild;p-rchild=r;r=p;p=q;ele/某上升某/某下降进/某下降进入/某访问 p 所指结whle(r&t-tag=0) (r&t-tag=1

27、&r-rchild=NULL)if(r&t-tag=0) q=r-rchild;r-rchild=p;p=r;r=q;/某从右子树回来某/eler-tag=0;q=r-lchild;r-lchild=p;p=r;r=q; 树回来某/if(r=NULL)return;eler-tag=0;q=r-rchild;r-rchild=r-lchild;r-lchild=p;p=q;回来，准备进入右子树某/13对以孩子兄弟链表表示的树编写计算树的深度的算法。【提示】 米用递归算法实现。0若树为空树的深度=Ma 某(第一棵子树的深度1，兄弟子树的深度)若树非空 inthigh(CSTreeT)if(T二二NULL)return(0);/某