数据结构的作业

第一章作业：1.熟悉类C语言的书写规范，特别要注意值参和变参的区别，输入、输出的方式以及错误处理2.试依照复数的抽象数据类型写出抽象数据类型有理数的描述（有理数是其分子、分母均为整数且分母不为零的分数）。3.设n为正整数。试写出下列程序段中带记号@的语句的频度及算法时间复杂度。(1)i=1;k=0;(2)x=91;y=100;while(i=n-1)while(y0){@k=k+10*i;@{if(x100)i=i+1;{x=x-10;y=y-1}}elsex=x+1}第二章作业：1.指出以下算法中的错误和低效（即费时）之处，并将它改为一个既正确又高效的算法。ProcDeleteK(VARa:sqlist;i,k:integer);{从顺序存储结构的线性表a中删除自第i个元素起的K个元素}If(i1)cor(ia.last)thenerror(‘Argumentinvalid’)elseforcount:=1tokdo【forj:=a.lastdowntoi+1doa.elem[j-1]:=a.elem[j];a.last:=a.last-1】ENDP;{deleteK}2.设顺序表Va中的数据元素递增有序。试写一算法，将X插入到顺序表的适当位置上，以保持该表的有序性。3.用单链表实现Locate(L,x)函数。（可参考P26算法2.5)4.上机题：设单链表Va中的数据元素递增有序。试编写程序，将数据X插入单链表Va，要求插入后保持该表的有序性。5.写出双向链表删除第i个结点的算法。6.写出求双向循环链表长度的算法。（注：头结点不算）第三章作业：1.上机题：编写程序，判别表达式中（、）是否配对出现。2.写出下列程序段的输出结果（栈的元素类型为：char).vars:stack;x,y:char;beginx:=‘c’;y:=‘k’;push(s,x);push(s,‘a’);push(s,y);x:=pop(s);push(s,‘t’);push(s,x);x:=pop(s);push(s,‘s’);whilenotempty(s)do【y:=pop(s);write(y)】;writeln(x);end;第四章作业:1.用4.1.2提供的7种串的基本操作来实现insert(s,pos,t)和delete(s,pos,len)操作.2.上机题：编写程序，完成静态存储串时的insert(s,pos,t)或delete(s,pos,len)操作。3.课堂练习：执行以下程序段，写出运行结果。procp;creat(s,’thisisabook’);replace(s,substr(s,3,7),’eseare’);creat(t,concat(s,’s’));creat(u,’xyxyxyxyxyxy’);creat(v,substr(u,6,3));creat(w,’w’);writeln(t,v,replace(u,v,w))endp;{p}第五章作业：1.假设有二维数组a:array[1..6,0..7]ofelemtp;每个数据元素占6个字节,存储器按字节编址。a的基地址为1000,则：(1)数组a的体积；(2)数组a的最后一个元素的第一个字节的地址；(3)按行存储时，a[2,4]的第一个字节的地址；(4)按列存储时，a[5,7]的第一个字节的地址；第六章作业：1.一棵度为2的树与一棵二叉树有何区别？2.试分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。3.已知一棵度为k的树中有n1个度为1的结点，n2个度为2的结点，……，nk个度为k的结点，问该树中有多少个叶子结点。4.对题2所得的3个结点的二叉树的5种不同形态，分别写出先序、中序、后序的遍历序列。5.一棵含有n个结点的k叉树，可能达到的最大深度和最小深度各为多少？6.上机题：按先序次序建立以下二叉树，然后分行输出它的先序、中序、后序序列。ABFCJM7.写出下列各树的先根序列,后根序列,并且画出对应的二叉树.AABCABCABCDEFGHIJK8.画出第7题的森林相应的二叉树.9.画出和下列已知序列对应的树T:树的先根次序访问序列为:GFKDAIEBCHJ,而且树的后根次序访问序列为:DIAEKFCJHBG。10.画出和下列二叉树相应的森林:AABCABCABDCHEKFGJMI11.假设用于通讯的电文仅由8个字母组成,字母在电文中出现的频率分别为0.07、0.19、0.02、0.06、0.32、0.03、0.21、0.10。试为这8种字母设计哈夫曼编码。第七章作业：1.请给出下图的:(1)每个顶点的入度和出度.(2)强连通分量(3)邻接矩阵(4)邻接表(5)逆邻接表(6)十字链表1365422.写出以数组为存储结构,函数firstadj(G,v)的算法.3.写出以数组为存储结构,函数nextadj(G,v,w)的算法.4.上机题:建立下图(以数组或邻接表为存储结构),然后输出图的深度优先序列、广度优先序列。ACEGFBHD5.对下图用普里姆算法、克鲁斯卡尔算法构造最小生成树.（画出构造过程）。3145237946636.请列出下图中全部可能的拓朴有序序列.1253647.对于下图所示的AOE网,计算各事件的ve(i)和vl(i),各活动的e(i)和l(i);列出关键活动和关键路径.123465a1=6a2=6a3=1a5=2a6=7a7=4a4=28.用迪杰斯特拉(Dijkstra)算法求下图中从顶点1到其它各顶点的最短路径，画出各步的状态。11234561053129.用弗洛伊德（Floyd）算法求下图所示有向图中各顶点之间的最短路径。ABC610218第九章作业:1.画出对长度为10的有序表进行折半查找的判定树,并求出等概率时查找成功的平均查找长度.2.有一含有5个记录的有序序列及权值如下：关键字：ABCDE权值：18256(1)画出对以上有序序列进行折半查找的判定树，并计算它的PH值。(2)构造它的次优查找树并加以适当调整，计算它的PH值。3.有关键字序列{5，37，90，53,60}表;(1)构造它的二叉排序树;(画出构造过程)(2)构造它的平衡二叉排序树;(画出构造、调整过程）4.某系部学生的学号由6位十进制组成：C1C2C3C4C5C6。其中c1c2为入学年份的后两位；c3为专业号；c4c5c6为同一系部的学生的顺序编号。假设某系部在校生为500人，请用直接定址法为该系部学生设计一个哈希表。5.有学生的生日数据如下：年.月.日75.10.0375.11.2376.03.0276.07.1275.04.2176.02.15...请以生日日期为关键字，设计一个长度为1000的哈希表，使其冲突尽量少。6.上机题：建立一棵二叉排序树，输入序列为（45，24，53，12，24，90），然后中序遍历此树，得到一个关键字的有序序列。7.在地址空间为0~13的散列区中,对以下关键字序列构造两个哈希表:(Jan,Feb,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,Dec)(1)用线性探测开放定址法处理冲突;(2)用链地址法处理冲突;(3)求出以上两个哈希表在等概率情况下，查找成功、查找不成功时的平均查找长度（用公式计算）。设哈希函数为H(key)=|key的第一个字母在字母表的序号/2|第十章作业:1.有一组待排序的记录的关键字初始排列如下:(32,54,12,24,32`,47)(1)请用直接插入排序算法对其进行排序.(画出每趟排序示图)(2)请用希尔排序算法对其进行排序.(画出每趟排序示图,d=2,1)(3)请用快速排序算法对其进行排序.(画出每趟排序示图)(4)请用树型选择排序算法对其进行排序.(画出排序示图)(5)请用堆排序算法对其进行排序.(画出排序示图)(6)请用归并排序算法对其进行排序.(画出排序示图)(7)请用链式基数排序算法对其进行排序.(画出排序示图)2.上机题：编写快速排序算法的程序，每趟排序的枢轴依“三者取中”法来选取。测试数据：{49,38,65,97，76，13，27，49`}