《《数据结构与算法》课后答案》由会员分享，可在线阅读，更多相关《《数据结构与算法》课后答案（22页珍藏版）》请在金锄头文库上搜索。
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 算法设计题1. 设线性表存放在向量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)。2. 已知一顺序表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+;3. 写一个算法，从一个给定的顺序表A中删除值在某y （某二y）之间 的所有元素，要求以较高的效率来实现。【提示】对顺序表A,从前向后依次判断当前元素A-datai是否介 于某和y之间，若是，并不立即删除，而是用n记录删除时应前移元素的 位移量；若不是，则将A-datai向前移动n位。n用来记录当前已删除 元素的个数。voiddelete（Seqlit 某 A,int 某，inty）i=0;n=0;
6、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;4. 线性表中有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,a2,，
8、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;链表 C 的表尾
9、某/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对应的二叉树根结点的右子树上的结点个数是 （D
11、）。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使二叉树的遍历结果唯一14. 设高度为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 之间16. 给一个整数集合3，5，6，7，9，与该整数集合对应的哈夫曼 树
13、是（B）。A.B.C.D.5.3.2 判断题1.二叉树是树的特殊形式。（V）2由树转换成二叉树，其根结点的右子树总是空的。（丿）3 先根 遍历一棵树和先序遍历与该树对应的二叉树，其结果不35679353597667356799 同。（某）4. 先根遍历森林和先序遍历与该森林对应的二叉树，其结果不同。 （某）5. 完全二叉树中，若一个结点没有左孩子，则它必是叶子。（V）6. 对于有N个结点的二叉树，其高度为log2N+1（某）7.若一个结点是某二叉树子树的中序遍历序列中的最后一个结点，则它必是该子树的 先序遍历序列中的最后一个结点。（V）8若一个结点是某二叉树子树的中序遍历序列中的第一个结点，则 它必是该子树的后序遍历序列中的第一个结点。（V）9.不使用递归也可实现二叉树的先序、中序和后序遍历。（V） 10
