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

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

2、时移动元素的个数与该 元素的位置有关。（J）.线性表的链式存储结构是用一组任意的存储单元来存储线性表中 数据元素的。（J）.在单链表中，要取得某个元素，只要知道该元素的指针即可，因 此，单链表是随机存取的存储结构。（某）.静态链表既有顺序存储的优点，又有动态链表的优点。所以它存取表中第i个元素的时间与i无关。（某）查找结点的前驱或后继的速度B.为了能在二叉树中方便的进行插入与删 除C.为了能方便的找到双亲D.使二叉树的遍历结果唯一14.设高度为h的二叉树上只有度为0和度为2的结点，那么此类二叉 树中所包含的结点数至少为（B）。A. 2某hB. 2某h-1C. 2某h+lD. h+115. 一个

3、具有567个结点的二 叉树的高h为（D） oA. 9B. 10C. 9 至 566 之间D. 10 至 567 之间16.给一个整数集合3, 5, 6, 7, 9）,与该整数集合对应的哈夫曼 树是（B）。A. B. C. D.3. 2判断题.二叉树是树的特殊形式。（J）.由树转换成二叉树，其根结点的右子树总是空的。（J）3.先根 遍历一棵树和先序遍历与该树对应的二叉树，其结果不35679353597667356799 同。（某）.先根遍历森林和先序遍历与该森林对应的二叉树，其结果不同。 （某）.完全二叉树中，假设一个结点没有左孩子，那么它必是叶子。（J）6.对于有N个结点的二叉树，其高度为lo

4、g2N+l。（某）7.假设一个结点是某二叉树子树的中序遍历序列中的最后一个结点，那么它必是该子树的 先序遍历序列中的最后一个结点。（V）.假设一个结点是某二叉树子树的中序遍历序列中的第一个结点，那么 它必是该子树的后序遍历序列中的第一个结点。（V）.不使用递归也可实现二叉树的先序、中序和后序遍历。（J）10.先序遍历二叉树的序列中，任何结点的子树的所有结点不一定跟在该 结点之后。（某）.先序和中序遍历用线索树方式存储的二叉树，不必使用栈。（某）.在后序线索二叉树中，在任何情况下都能够很方便地找到任意结 点的后继。（某）.哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根 较近。（J ）.

5、在哈夫曼编码中，出现频率相同的字符编码长度也一定相同。 （某）.用一维数组存放二叉树时，总是以先序遍历存储结点。（某）16.由先序序列和后序序列能唯一确定一棵二叉树。（某）17.由先序序列和中序序列能唯一确定一棵二叉树。（J）18.对一 棵二叉树进行层次遍历时，应借助于一个栈。（某）19.完全二叉树可采 用顺序存储结构实现存储，非完全二叉树那么不能。（某）20.满二叉树一定是完全二叉树，反之未必。（J） 5. 3. 3简答题1. 一棵度为2的树与一棵二叉树有何区别？树与二叉树之间有何区别？【解答】二叉树是有序树，度为2的树是无序树，二叉树的度不一定是2o二叉树是有序树，每个结点最多有两棵子树，

6、树是无序树，且每个 结点可以有多棵子BCA 树。DEF2.对于图1所示二叉树，试给出：GH 1)(1)它的顺序存储结构示意图；(2)它的二叉链表存储结构示意图; (3)它的三叉链表存储结构示意图。【解答】(1)顺序存储结构示意图：ABCDEF G-H(2)二叉链表存储结构示意图：(3)三叉链表存储结构示意图：ZVZV ZV ZS ZVZVZV ZS八 ZV _ ZV ZV , ZV _ ZV ZV ZVZXD BE F H AC D G BE A C F HG3.对于图2所示的树，试给出：BACFHJEKDMIN (1)双亲数组表 示法示意图；G (2)孩子链表表示法示意图；(图2) (3)孩

7、子兄弟链表 表示法示意图。【解答】(1)双亲数组表示法示意图：(2)孩子链表表示法示意图：.画出和以下序列对应的树T：二叉树的层次访问序列为：ABCDEFGHIJ；二叉树的中序访问次序为：DBGEHJACIF。【解答】按层次遍历，第一个结点(假设树不空)为根，该结点在中序序列中把 序列分成左右两局部一左子树和右子树。假设左子树不空，层次序列中第二 个结点左子树的根；假设左子树为空，那么层次序列中第二个结点右子树的根。 对右子树也作类似的分析。层次序列的特点是：从左到右每个结点或是当 前情况下子树的根或是叶子。.假设用于通信的电文由字符集a, b, c, d, e, f, g中的字母构成。 它们

8、在电文中出现的频度分别为0.31,0. 16, 0. 10, 0. 08, 0. 11,0. 20, 0. 04), (1)为这7个字母设计哈夫曼编码。(2)对这7个字母进行等长编码，至少需要几位二进制数？哈夫曼DGBEHJIACF编码比等长编码使电文总长压缩多少？(1)哈夫曼树：001.001100. 410. 5910. 2810.120a： 10b： 110c： 010d： 1110e： 011f： 00g： 11112000. 2110. 110. 100. 3100. 160. 8010. 40 (2)对这 7 个字母进行等 长编码，至少需要3位二进制数。等长编码的平均长度31 某

9、3+0. 16 某 3+0. 10 某 3+0. 08 某 3+0. 11 某 3+0. 20 某 3+0. 04 某3=3哈夫曼编码31 某 2+0. 16 某 3+0. 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 算法设计题.给定一棵用二叉链表表示的二叉树，其根指针为root,试写出求 二叉树结点的数目的算法。【提示】采用递归算法实现。0当二叉树为空二叉树结点的数目=左子树结点数目+右子树结点数目+1当二叉树非空intcount (BiTree

10、root) if(root=NULL)return (0);elereturn(count(root-lchild)+count(root-rchild)+1);.请设计一个算法，要求该算法把二叉树的叶结点按从左至右的顺 序链成一个单链表。二叉树按Ichild-rchild方式存储，链接时用叶结点 的rchi Id域存放链指针。【提示】这是一个非常典型的基于二叉树遍历算法，通过遍历找到各 个叶子结点，因为不管前序遍历、中序遍历和后序遍历，访问叶子结点的 相对顺序都是相同的，即都是从左至右。而题目要求是将二叉树中的叶子 结点按从左至右顺序建立一个单链表，因此，可以采用三种遍历中的任意 一种方法遍

11、历。这里使用中序递归遍历。设置前驱结点指针pre,初始为 空。第一个叶子结点由指针head指向，遍历到叶子结点时，就将它前驱 的rchild指针指向它，最后叶子结点的rchild为空。LinkLithead, pre=NULL;LinkLitlnOrder(BiTreeT)/某中序遍历二叉树T,将叶子结点从左到右链成一个单链表，表头 指针为head某/if (T) InOrder (T-lchild);左子树某/if (T-Ichiid=NULL&T-rchild=NULL)前是叶子结点某/if(pre=NULL)head=T;/某当/某中序遍历/某全局变量某/个叶子结点某/某处理第一ele

12、pre-rchild=T;pre=T;/某将叶子结点链入链表某/InOrder (T-rchiId);树某/pre-rchild=NULL;return (head);).给定一棵用二叉链表表示的二叉树，其根指针为出求二叉树的深 度的算法。【提示】采取递归算法。intHeight(BiTreeroot)inthl, hr;if (root-NULL) return (0) ; ele hl=Height (root-lchild);hr=Height(root-rchild);if(hlhr)return(hl+1);elereturn(hr+1);)/某中序遍历右子/某设置链表尾结点某/ro

13、ot,试写4.给定一棵用二叉链表表示的二叉树，其根指针为root, 试求二叉树各结点的层数。【提示】采用先序递归遍历算法实现。1二叉树结点的层次数= 其双亲结点的层次数+1voidfun (BiTreeroot, intn)if(t=NULL) return;ele printf (%d II , n);fun(root-lchild, n+1);fun(root-rchild,n+1);)当结点为根结点当结点非根结点5.给定一棵用二叉链表表示的二叉树，其根指针为root,试写出将 二叉树中所有结点的左、右子树相互交换的算法。【提示】设root为一棵用二叉链表存储的二叉树，那么交换各结点的 左

14、右子树的运算可基于后序遍历实现：交换左子树上各结点的左右子树； 交换左子树上各结点的左右子树；再交换根结点的左右子树。voidE 某change(BiTreeroot)BiTNode 某p;if (root)E Mchange(root-lchild);E 某change(root-rchiId);p=root-lchild;root-lchild=root-rchild;root-rchild=p;编写算法判定两棵二叉树是否相似。所谓两棵二叉树和t相似,即要么它们都为空或都只有一个结点，要么它们的左右子树都相似。【提示】两棵空二叉树或仅有根结点的二叉树相似；对非空二叉树， 可判左右子树是否相

15、似，采用递归算法。intSimilar (BiTree, BiTreet)if(=NULL&q=NULL)return(1);eleif(!&t|&!t)return(0);elereturn (Similar(-Ichi Id, t-Ichi Id)&Similar(-rchild, t-rchild)写出用逆转链方法对二叉树进行先序遍历的算法。【提示】用逆 转链的方法遍历二叉树，不需要附加的栈空间，而是在遍历过程中沿结点 的左右子树下降时，临时改变结点Ichild或者rchild的值，使之指向双 亲，从而为以后的上升提供路径，上升时再将结点的Ichild或者rchild 恢复。typede

16、ftructtnode(datatypedata;inttag;/某tag的值初始为0,进入左子树时置1,从左子树回来时, 再恢复为0 Wtructtnode 某Ichild, 某rchild;Bnode, 某Btree;voidPreOrder(Btreebt)Bnode某r,某p,某q;/某p指向当前结点，r指向p的双亲，q指向 要访问的下一结点某/if (bt=NULL) return;p=bt; r=NULL: whi 1 e (p) Viit (p);点某/ if (p-lchild)左子树某/p-tag=l;q=p-lchiId;q=p-lchild=r;r=p;p=q;eleif

17、(p-rchild) 入右子树某/q=p-rchild;p-rchild=r;r=p;p=q;ele /某上升某/某下降进/某下降进入/某访问P所指结whle(r&t-tag=O)(r&t-tagl&r-rchildNULL)if(r&t-tag=O)q=r-rchild;r-rchild=p;p=r;r=q;/某从右子树回来某/eler-tag=O;q=r-Ichild;r-Ichiid=p;p=r;r=q;树回来某/if (r-NULL) return;ele r-tag=O;q=r-rchild;12.线性表的特点是每个元素都有一个前驱和一个后继。（某） 2. 3. 3算法设计题1设线性

18、表存放在向量Aarrize的前elenum个分量中，且递增有 序。试写一算法，将某插入到线性表的适当位置上，以保持线性表的有序性, 并且分析算法的时间复杂度。【提示】直接用题目中所给定的数据结构（顺序存储的思想是用物理 上的相邻表示逻辑上的相邻，不一定将向量和表示线性表长度的变量封装 成一个结构体），因为是顺序存储，分配的存储空间是固定大小的，所以 首先确定是否还有存储空间，假设有，那么根据原线性表中元素的有序性，来 确定插入元素的插入位置，后面的元素为它让出位置，（也可以从高下标 端开始一边比拟，一边移位）然后插入某，最后修改表示表长的变量。intinert （datatypeA, int

19、某 elenum, datatype el enum 为表的最 大下标某/if （某 e 1 enum-arrize-1）returnO;法插入某/ele i 二某 el enum;while（i= 0&Ai某）边移动某/Ai+l=Ai;i;Ai+1=某；/某找到的位置是/某边找位置 /某表已满，无/某r-rchild=r-lchiId;r-Ichiid=p;P=q；回来，准备进入右子树某/)B 对以孩子一兄弟链表表示的树编写计算树的深度的算法。【提示】 采用递归算法实现。0假设树为空树的深度=Ma某(第一棵子树的深度+1,兄弟子树的深度)假设树非空inthigh (CSTreeT)if (T

20、二二NULL)return(0) ;/某假设树为空，返回 0 某/elehl=high(t- lchild) ;/某某hl为T的第一棵子树的深度某/h2=high(t-ne某tibling) ;/某h2为t的兄弟子树的深度某/return (ma 某(hl+1, h2) ;/某从左子树/某从左子M 对以孩子链表表示的树编写计算树的深度的算法。【提示】采用 递归算法实现。ttdefineMA某NODE树中结点的最大个数inthigh(SNodetMA某NODE, intj) if (t j. firtchild-NULL)return(1);树某/ elep=ti. firtchild;ma h

21、igh(t, p-data) ;p=p-ne Mtchild;while (p)h=high(t, p-data);if(hma h;p=p-ne 某tchild;return (ma 某+1);/某假设根结点没有子树的深度=ma某(所有子树的深度)+1假设根结点有子树假设根结点没有子树15 对以双亲链表表示的树编写计算树的深度的算法。【提示】从每 一个结点开始，从下向上搜索至根结点，记录结点的层次数，其中的最大 值就是树的深度。inthigh(PNodet, intn)/某求有n个结点的树t的深度某/ma某 h=0;for(i=0;iifparent=-l)h=l;ele=i;while（t

22、. parent!=-l）=t . parent;h+;）if （hma 某h）ma 某h=h;return（ma 某h）;6. 3. 1选择题n条边的无向图的邻接表的存储中，边结点的个数有（A）。A. nB. 2nC. n/2D. n 某nn条边的无向图的邻接多重表的存储中，边结点的个数有（A）。A. nB. 2nC. n/2D. n某n3.以下哪一种图的邻接矩阵是对称矩阵？ （B） oA.有向图B.无向图C. AOV网D. AOE网.最短路径的生成算法可用（C）。A.普里姆算法B.克鲁斯卡尔算法C.迪杰斯特拉算法D.哈夫曼算 法. 一个无向图的邻接表如以下图所示： 序号verte 某fir

23、tedge0123vlv2V3V41010八32/3/ 1A设插入位的下一位某/( 某 elenum)+;returnl;时间复杂度为0(n)。2一顺序表A,其元素值非递减有序排列，编写一个算法删除 顺序表中多余的值相同的元素。【提示】对顺序表A,从第一个元素开始，查找其后与之值相同的所 有元素，将它们删除；再对第二个元素做同样处理，依此类推。voiddelete(Seqlit 某A)i=0;while (ilat)与其值相同的元素删除某/k=i+l;while (klat&A-datai=A-datak)k+;/某使k指向第一个与Ai/某将第i个元素以后/某插入成功某/不同的元素某/n=k-

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

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

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

27、线性表：(al, a2,，am, bl, b2,，bn)改变为：(bl, b2,，bn, al, a2, , am)。/某将数字放在字母后【提示】比拟m和n的大小，假设mif (m=n)for(i=l;idata0;for (k=l;klat;k+)L-datak-l=L-datak;L-dataL-lat=某;elefor(i=l;idataL-lat;for(k=L-lat-l;k=0;k-)L-datak+l=L-datak;L-data0=某;6带头结点的单链表L中的结点是按整数值递增排列的，试写 一算法，将值为某的结点插入到表L中，使得L仍然递增有序，并且分析 算法的时间复杂度。Li

28、nkLitinert (LinkLitL, int 某)p=L;while(p-ne 某t&某p-ne 某t-data)p=p-ne 某t;/某寻找插入位置某/=(LNode malloc (izeof (LNode) ;-data二某；/某申请结点空间某/某填装结点某/-ne 某t=p-ne 某t;p-ne 某t二；/某将结点插入到链表中某/return (L);C=A;rc=C;pa=A-ne 某t;pb=B-ne 某t;free(B);头结点某/while(pa&pb) /某将pa、pb所指向结点中，值/某pa指向表A的第一个结点某某pb指向表B的第一个结点某/某释放B的较小的一个插入到链表C的表尾某/if (pa-datadata)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;链表C的表尾某/return (C);i8假设