数据结构复习之运算操作题(答案解析).pdf

习题习题 4-1运算运算题题。1有 6 个元素 A、B、C、D、E、F 依次进栈，允许任何时候出栈，能否得到下列的每个出栈序列，若能，给出栈操作的过程，若不能，简述其理由。（1）CDBEFA （2）ABEDFC （3）DCEABF （4）BAEFCD 2有 4 个元素 a,b,c,d 依次进栈，任何时候都可以出栈，请写出所有可能的出栈序列和所有不存在的序列。3用一维数组 a7顺序储一个循环队列，队首和队尾指针分别用 front 和 rear 表示，当前队列中已有 5 个元素：23，45，67，80，34，其中，23 为队首元素，front 的值为 3，请画出对应的存储状态，当连续做 4 次出队运算后，再让 15，36，48 元素依次进队，请再次画出对应的存储状态。4用于顺序存储一个队列的数组的长度为 N,队首和队尾指针分别为 front 和 rear,写出求此队列长度(即所含元素个数)的公式.参考答案（从简）1，(1)能:push(S,A),push(S,B),push(S,C),pop(S),push(S,D),pop(S),pop(S),push(S,E),pop(S),push(S,F),pop(S),pop(S).(2)能:push(S,A),pop(S),push(S,B),pop(S),push(S,C),push(S,D),push(S,E),pop(S),pop(S),push(S,F),pop(S),pop(S).(3)不能:当 E 出栈时，AB 必需在栈内，而后继 A 出栈先于 B，不符合后进先出原则。(4)不能:当 F 出栈时，CD 必需在栈内，而后继 C 出栈先于 D，不符合后进先出原则。2，所有可能的出栈序列:abcd;abdc;acbd;acdb;adcb;bacd;badc;bcad;bcda;bdca;cbad;cbda;cdba;dcba.所有不存在的序列:adbc;bdac;cabd;cadb;cdab;dabc;dacb;dbac;dbca;dcab.3，0 1 2 3 4 5 6-80 34 23 45 67 rear front 34 15 36 48 front rear4，队列长度 L 的计算公式为：L=(N+rear-front)%N 说明：当 rearfront 时，L=rear-front=(N+rear-front)%N;当 rearfront 时，队列被分为两个部分，前部分在数组的尾部，其元素个数为 N-1-front,后部分在数组的首部，其元素个数为 rear+1,所以：L=(rear+1+N-1-front)%N=(N+rear-front)%N;习题习题 6-1运算运算题题1.已知一组元素为(46,25,78,62,12,37,70,29),画出按元素排列顺序输入生成的一棵二叉搜索树,再以广义表的形式给出该二叉搜索树.2.已知一棵搜索树的广义表表示为 28(12(,16),49(34(30),72(63),若从中依次删除 72,12,49,28,等 4 个结点,试分别画出每删除一个结点后得到的图形表示的二叉搜索树,并写出对应的广义表表示.3.从空堆中开始依次向小根堆中插入集合38,64,52,15,73,40,48,55,26,12中的每个元素,试以顺序表的形式给出每插入一个元素后堆的状态.4.已知一个堆为12,15,40,38,26,52,48,64,若从堆中依次删除 4 个元素,请给出每删除一个元素后的堆的状态.5.有 7 个带权结点,其权值分别为 3,7,8,2,6,10,14,试以它们为叶子结点构造一棵哈夫曼树,给出其广义表表示.并计算出带权路径长度 WPL.*6.在一份电文中共使用 5 种字符,即 a.b.c.d.e,它们的出现频率依次为 4,7,5,2,9,试画出对应的哈夫曼编码和传送电文的总长度.*7.一棵二叉树的广义表表示为 A(B(,D(G,),)C(E(,H),F),试画出对应的图示二叉树*9.一组关键字为(36,75,83,54,12,67,60,40,92,72),试依次插入结点分别生成一棵二叉搜索树，并求查找每个元素的平均查找长度.1.广义表：46(52(12,37(29),78(62(,70)3.3838 6438 64 5215 38 52 6415 38 52 64 7315 38 40 64 73 5215 38 40 64 73 52 4815 38 40 55 73 52 48 6415 26 40 38 73 52 48 64 5512 15 40 38 26 52 48 64 55 732.删除 72 删除 12 删除 49 删除 28 7.9.ASL=(1+22+23+34+25)/104.删除 1215 26 40 38 64 52 48删除 1526 38 40 48 64 52删除 2638 48 40 52 64删除 3840 48 64 525.广义表：(2,3),6),10),(7,8),14)WPL=(10+14)2+(6+7+8)3+(2+3)46.字符编码码长a00004b012c0013d00014e11电文总长=44+72+53+24+91 习题习题 7-1运算运算题题1、如图 7-13（a）和图 7-13（b）所示，求：、1、每一个图的二元组表示。、2、图 7-13（a）中每个顶点的度，以及每个顶点的所有邻接点和所有边。、3、图 7-13（b）中每个顶点的入度、出度和度，以及每顶点的所有入边的出边。、4、图 7-13（a）中从 v0 到 v4 的所有简单路径及相应路径长度。、5、图 7-13（b）中从 v0 到 v4 的所有简单路径及相应带权路径长度。2、根据图 7-13（a）和图 7-13（b），画出：、1、每个图的邻接邻接矩阵。、2、每个图的邻接表。、3、每个图的边集数组。3、如图 7-14 所示，按下列条件分别写出从顶点 v0 出发按深度优先搜索遍历得到的顶点序列和按广度优先搜索遍历得到的顶点序列。、1、假定它们均采用邻接矩阵表示。、2、假定它们均采用邻接表表示，并且每个顶点邻接表中的结点都是按顶点序号从大到小的次序链接的。4、已知一个图的二元组表示如下：V=0，1，2，3，4，5，6，7，8E=（0，3），（0，4），（1，2），（1，4），（2，4），（2，5），（3，6），（3，7），（4，7），（5，8），（6，7），（7，8）、1、画出对应的图形。、2、假定从顶点 0 出发，给出邻接矩阵表示图的深度优先和广度优先搜索遍历的顶点序列。、3、假定从顶点 0 出发，给出邻接表表示的图的深度优先和广度优先搜索遍历的顶点序列，假定每个顶点邻接表中的结点都是按顶点序号从大到小的次序链接的。答案3.依照矩阵和邻接表所产生的两种遍历序列各自相等。a 图：深度优先遍历：0 1 2 8 3 4 5 6 7 9广度优先遍历：0 1 4 2 7 3 8 6 9 5b 图：深度优先遍历：0 1 4 5 8 7 2 3 6广度优先遍历：0 1 3 4 2 6 7 5 84.深度优先遍历：0 3 6 7 4 1 2 5 8广度优先遍历：0 3 4 6 7 1 2 8 5 （a）无向图 （b）有向图 图 713 运算题图 1 （a）无向图 （b）有向图 图 714 运算题图 2 习题习题 8-1运算运算题题1、如图形 8-18 所示,针对有向图操作如下。（1）画出最小生成树并求出它的权。（2）从顶点 v0 出发，要据普里姆算法求出最小生成树的过程中，把依次得到的各条边按序写出来。（3）根据克鲁斯卡算法求出最小生成树的过程中，把依次得到的各条边写出来。2、如图 8-19 所示，利用狄克特拉算法求从顶点 V0 到其余各顶点的最短路径，并画出对应的图形表示。3、已知一个图的二元组表示为：V=0，1，2，3，4，5，6，7 E=（0，1）8，（0，3）2，（0，5）10，（1，2）6，（1，4）20，（1，6）12，（2，4）10，（2，7）15，（3，5）5，（3，6）7，（4，7）4，（5，6）6，（6，7）8（1）按照克鲁斯卡尔算法求出最小生成树，写出依次得到的各条边。（2）按照狄克斯特算法求从顶点 0 到其余各顶点的最短路径。(1)(0,3)，(4,7)，(3,5)，(5,6)，(1,2)，(0,1)，(6,7)(2)03：(0,3)05：(0,3)，(3,5)01：(0,1)06：(0,3)，(3,6)02：(0,1)，(1,2)07：(0,3)，(3,6)，(6,7)04：(0,3)，(3,6)，(6,7)，(7,4)4、如图形 8-20 所示，利用弗洛伊德算法求每对顶点之间的最短路径，即仿照如图形 8-8 的运算过程，给出从邻接矩阵出发每加入一个中间每加入一个中间点后矩阵状态。5 如图形 8-21 所示，试给出一种拓扑序列，若在它的邻接表存储结构中，每个顶点邻接表中的边结点都是按照终点序号从大到小链接的，则按此给出唯一一种拓扑序列。6 一个 AOV 网的二元组表示为：V=0，1，2，3，4，5，6，7，8，9，10 E=,图 818 无向带权图 (1)(2)普里姆算法的边的序列：(0,1)，(1,6)，(6,2)，(2,3)，(3,4)，(4,5)(3)克鲁斯卡算法的边的序列：(1,6)，(2,3)，(0,1)，(6,2)，(3,4)，(4,5)图 819 有向带权图不画图了，只写出边的序列。以下各点的最短路径是按顺序生成的：03：05：01：,06：,04：,02：,07：,图 820 有向带权图图 821 AOV 网 答案:1 4 0 2 3 5 7 6 8 9 在此 AOV 网的邻接表存储中,若各顶点邻接表中的边结点是按照邻接顶点序号从大到小链接的,请写出按此邻接表和介绍表和介绍的拓扑排序算法得到得到的拓扑排序算法得到的拓扑序列。提示：先画出图形再运算。答案:1 0 2 4 3 5 7 6 8 9 107、如图形 8-22 所示的 AOV 网，求：（1）每个事件的最早发生时间和最迟发生时间。（2）完成整个工程至少需要多长时间。（3）每项活动的最早开始时间和最迟开始时间以及开始时间余量。（4）画出由所有关键活动所构成的图。（5）哪些活动加速可使整个工程提前完成？答案:(1)设 ve(i)和 vl(i)分别表示事件 i 的最早发生时间和最迟发生时间。ve(0)=0ve(1)=ve(0)+a1=5ve(2)=ve(0)+a2=6 ve(3)=Max ve(1)+a3,ve(2)+a4 =Max 8,12 =12 ve(4)=Max ve(2)+a5,ve(3)+a6 =Max 9,15 =15 ve(5)=ve(3)+a7=16 ve(6)=Max ve(3)+a8,ve(4)+a9 =Max 16,16 =16 ve(7)=ve(4)+a10=17 ve(8)=Max ve(6)+a12,ve(7)+a13 =Max 21,19 =21 ve(9)=Max ve(5)+a11,ve(8)+a14 =Max 20,23 =23 vl(9)=23 vl(8)=vl(9)a14=21 vl(7)=vl(8)a13=19 vl(6)=vl(8)a12=16 vl(5)=vl(9)a11=19 vl(4)=Min vl(6)a9,vl(7)-a10 =Min 15,17 =15 vl(3)=Min vl(5)a7,vl(6)a8,vl(4)a3 =Min 15,12,12 =12 vl(2)=Min vl(3)a4,vl(4)a5 =Min 6,12 =6 vl(1)=vl(3)a3=9vl(0)=0(2)因为 ve(9)=23，所以完成整个工程至少的时间为 23。(3)设 e(i)和 l(i)分别为活动 i 的最早开始时间和最迟开始时间，则 l(i)e(i)为每个活动的开始时间余量。活动 i 由弧表示。根据(1)题所得的结果和关系 e(i)=ve(j)、l(i)=vl(k)w，得出下表：活动ell-eve(0)=0vl(1)a1=4 4ve(0)=0vl(2)a2=00ve(1)=5vl(3)a3=94ve(2)=6vl(3)a4=60ve(2)=6vl(4)a5=126ve(3)=12vl(4)a6=120ve(3)=12vl(5)a7=153ve(3)=12vl(6)a8=120ve(4)=15vl(6)a9=150ve(4)=15vl(7)a10=172ve(5)=16vl(9)a11=193ve(6)=16vl(8)a12=160ve(7)=17vl(8)a13=192ve(7)=21vl(9)a14=210 图 822 AOE 网 (4)e(i)等于 l(i)的活动(即开始时间剩余量为 0 的活动)为关键活动，所以图中的关键活动为：，。所以图中的关键路径有两条：，它们的路径长度都为 23。所有关键活动所构成的图为：(5)关键活动决定整个工程的持续时间。所以加速关键活动，可以整个工程提前完成。9-1运算运算题题1.若查找有序表 A30中每一元素的概率相等,试分别求出进行顺序,二分和分块(若被分为 5 块,每块 6 个元素)查找每一个元素时的平均查找长度.2.一个待散列存储的数据集合为32,75,29,63,48,94,25,46,18,70,56,散列地址空间为 HT13,若采用除留余数法构造散列函数和线性探查法处理冲突,试求每一元素的散列地址,画出最后得到的散列表,求平均查找长度.3.设有一个含有 200 个元素的表待散列存储,用线性探查法处理冲突,按关键字查询时找到一个元素的平均查找长度(即平均探查次数)不能超过 1.5,则散列表的长度应至少为多少?1.若进行顺序查找，将 n=30 代入公式 ASL=(n+1)/2 得 ASL=15.5。若进行二分(折半)查找，将 n=30 代入公式 ASL=得 ASL=4.1也可以通过二叉判定树来确定 ASL。若进行分块查找，由于原表有序，所以可分两种情况讨论：若用顺序查找确定所在块，则将 s=6，n=30 代入公式 ASL=(n/s+s)/2+1 中，得 ASL=6.5若用二分查找确定所在块，则将 s=6，n=30 代入公式 得 ASL=5.62.一次探测成功时，H(key)=key%13线性探测再散列的哈希函数为 Hi=(H(key)+di)%m(di=1，2，3，m-1 且 1im-1)32%13=6 探测 1 次75%13=10 探测 1 次29%13=3 探测 1 次63%13=11 探测 1 次48%13=9 探测 1 次94%13=3 有冲突，再探测 H1=(3+1)%13=4 探测 2 次25%13=12 探测 1 次46%13=7 探测 1 次18%13=5 探测 1 次70%13=5 有冲突，再探测 H1=(5+1)%13=6 有冲突，再探测 H2=(6+2)%13=8探测 3 次 56%13=4 有冲突，再探测 H1=(4+1)%13=5 有冲突，再探测 H2=(5+2)%13=7 有冲突，再探测 H3=(7+3)%13=10 有冲突，再探测 H4=(10+4)%13=1 探测 5 次ASL=(1+1+1+1+1+2+1+1+1+3+5)/11=1.63X3275296348942546187056H(X)61031193127554冲突后线性探查的次数124处理冲突后的实际地址4810 1 2 3 4 5 6 7 8 9 10 11 1256299418324670487563253.对于线性探测再散列，ASL，=n/m，n 为记录数，m 为哈希表长(散列表长)。联立以上两式得：10-1运算运算题题已知一组元素的排序码为：（46，74，16，53，14，26，40，38，86，65，27，34）1利用直接插入排序的方法写出每次向前面有序表插入一个元素后的排列结果。2利用直接选择排序方法写出每次选择和交换后的排列结果。3利用堆排序的方法写出在构成初始堆和利用堆排序的过程中，每次筛运算后的排列结果，并画出初始堆所对应的完全二叉树。4利用快速排序的方法写出每一层划分后的排列结果，并画出此快速排列得到的二叉搜索树。5利用归并排序的方法写出每一趟二路归并排序后的结果。运算操作题10-1-1红色数字为已经排好序的部分第 1 趟：46 74 16 53 14 26 40 38 86 65 27 34第 2 趟：16 46 74 53 14 26 40 38 86 65 27 34第 3 趟：16 46 53 74 14 26 40 38 86 65 27 34第 4 趟：14 16 46 53 74 26 40 38 86 65 27 34第 5 趟：14 16 26 46 53 74 40 38 86 65 27 34第 6 趟：14 16 26 40 46 53 74 38 86 65 27 34第 7 趟：14 16 26 38 40 46 53 74 86 65 27 34第 8 趟：14 16 26 38 40 46 53 74 86 65 27 34第 9 趟：14 16 26 38 40 46 53 65 74 86 27 34第 10 趟：14 16 26 27 38 40 46 53 65 74 86 34第 11 趟：14 16 26 27 34 38 40 46 53 65 74 86 运算操作题10-1-3排序前的建堆是从完全二叉树的底部往上筛选的过程，排序时的调堆是从完全二叉树顶部向下筛选的过程。因为题目要求按关键字升序排列，所以建大根堆比较方便。初始堆的建堆过程：46 74 16 53 14 34 40 38 86 65 27 2646 74 16 53 65 34 40 38 86 14 27 2646 74 16 86 65 34 40 38 53 14 27 2646 74 40 86 65 34 16 38 53 14 27 2646 86 40 74 65 34 16 38 53 14 27 2686 74 40 53 65 34 16 38 46 14 27 26运算操作题10-1-2红色数字为已经排好序的部分，蓝色数字为每趟结束前被交换的数据（和最后一个红色数字交换）第 1 趟：14 74 16 53 46 26 40 38 86 65 27 34第 2 趟：14 16 74 53 46 26 40 38 86 65 27 34第 3 趟：14 16 26 53 46 74 40 38 86 65 27 34第 4 趟：14 16 26 27 46 74 40 38 86 65 53 34第 5 趟：14 16 26 27 34 74 40 38 86 65 53 46第 6 趟：14 16 26 27 34 38 40 74 86 65 53 46第 7 趟：14 16 26 27 34 38 40 74 86 65 53 46第 8 趟：14 16 26 27 34 38 40 46 86 65 53 74第 9 趟：14 16 26 27 34 38 40 46 53 65 86 74第 10 趟：14 16 26 27 34 38 40 46 53 65 86 74第 11 趟：14 16 26 27 34 38 40 46 53 65 74 86运算操作题10-1-4选取每一块的第一个记录为枢轴第一次划分：34 27 16 38 14 26 40 46 86 65 53 74第二次划分：26 27 16 14 34 38 40 46 74 65 53 86第三次划分：14 16 26 27 34 38 40 46 53 65 74 86第四次划分：14 16 26 27 34 38 40 46 53 65 74 86第五次划分：14 16 26 27 34 38 40 46 53 65 74 86二叉排序树（二叉搜索树）为：运算操作题10-1-5第 1 趟：46 74|16 53|14 26|38 40|65 86|27 34第 2 趟：16 46 53 74|14 26 38 40|27 34 65 86第 3 趟：14 16 26 38 40 46 53 74|27 34 65 86第 4 趟：14 16 26 27 34 38 40 46 53 65 74 86 初始堆所对应的完全二叉树：堆排序：第 1 趟：26 74 40 53 65 34 16 38 46 14 27 86第 2 趟：26 65 40 53 27 34 16 38 46 14 74 86第 3 趟：14 53 40 46 27 34 16 38 26 65 74 86第 4 趟：26 46 40 38 27 34 16 38 53 65 74 86第 5 趟：14 38 40 26 27 34 16 46 53 65 74 86第 6 趟：16 38 34 26 27 14 40 46 53 65 74 86第 7 趟：14 27 34 26 16 38 40 46 53 65 74 86第 8 趟：16 27 14 26 34 38 40 46 53 65 74 86第 9 趟：16 26 14 27 34 38 40 46 53 65 74 86第 10 趟：14 16 26 27 34 38 40 46 53 65 74 86第 11 趟：14 16 26 27 34 38 40 46 53 65 74 86您好，欢迎您阅读我的文章，本 WORD 文档可编辑修改，也可以直接打印。阅读过后，希望您提出保贵的意见或建议。阅读和学习是一种非常好的习惯，坚持下去，让我们共同进步。