数据结构课堂习题1

1、数据结构课堂习题、综合题1 .已知如图所示的AOE网，试求：(1) 每个事件的最早发生时间和最晚发生时间;(2) 每个活动的最早开始时间和最晚开始时间;(3) 给出关键路径。2 .已知以二维数组表示的图的邻接矩阵如下图所示012345601000100000101000000000000110010000001000000100001)并判别此图为有向图还是无向图2)求所有顶点的度数之和3)根据数组分别写出至序号为0的顶点开始进行遍历所得到的深度优先序列和广度优先序列。3 .给定集合6,9,16,17,15,3,14,2huffman树:(1)用口表示外部结点，用。表示内部结点，构造相应的(2

2、)计算它的带权路径长度：(3)写出它的huffman编码：4 .画出下图所示的树对应的二叉树I'J,K5 .从空树开始，逐个读入并插入下列关键字：(40,82,26,22,95,30,71,27),构造一颗二叉排序树，并求出在等概率情况下检索成功的平均检索长度。(7分)二、算法设计题1 .在带头结点的单链表L中删除第i个元素，并将删除的元素保存到变量*e中。intDelList(LinkListL,inti,ElemType*e)(Node*pre,*r;intk;pre=L;k=0;while(pre->next!=NULL&&k<i-1)/*寻找被删除结

3、点i的前驱结点i-1使p指向它*/(Pre=pre->nextk=k+1;)if(!(pre->next)(printf("删除结点的位置i不合理!");returnERROR;)r=pre->next;pre->next=r->next;/*修改指针，删除结点r*/*e=r->data;free(r);/*释放被删除的结点所占的内存空间*/printf("成功删除结点!");returnOK;2 .已知二叉树按照二叉链表方式存储，编写算法，计算二叉树中叶子结点的数目intLeafCount(BitreeT)/求二叉树

4、中叶子结点的数目；/叶子结点if()return0;/空树没有叶子elseif(!T->lchild&&!T->rchild)returnelsereturn/LeafCount3 .定义有序表抽象数据类型，并据此类型设计折半查找算法typedefstructintkey;floatinfo;JD;intbinsrch(JDr,intn,intk)intlow,high,mid,found;low=1;high=n;found=0;while()&&(found=0)mid=;if(k>rmid.key);elseif(k=rmid.key)f

5、ound=1;else;if(found=1)return(mid);elsereturn(0);一、综合题(共40分)1.二叉树的先序遍历序列ABDECF里中序遍历序列是DBEACGIg出这棵二叉树，并给出后序遍历序列。2 .在一个链队列Q中，假定front和rear分别为队首和队后指针，写出进行S结点进队执行的操作(s为指针)。3 .一组记录的关键码为(46,79,56,38,40,84,27)利用快速排序的方法，求以第一个记录为基准得到的一次划分结果，并说明算法的稳定性。4 .已知以邻接表表示的图的存储结构如下图所示。1)判别此图为有向图还是无向图。2)求所有顶点的度数之和。3)根据邻接

6、表分别写出以序号为v1的顶点开始进行遍历所得到的深度优先序列和广度优先序列。5 .已知一组关键字(9,14,21,17,68,20,2,27,55,11,10,69)哈希函数为：H(key尸keyMOD13,哈希表长为m=16设每个记录的查找概率相等，用链地址法处理冲突。1 .请构造哈希表。2 .求平均查找长度ASL6 .已知一个图如下图所示(1)请根据狄杰斯特拉算法求出从顶点1到其余各顶点的最短路径，并给出最短路径的求解过程。(2)若去掉该图中的方向，请用克鲁斯卡尔算法构造出最小生成树。二、算法设计题(每空2分，20分)。1 .在顺序表L中第i个数据元素之前插入一个元素e。插入前表长n=L-

7、>last+1,i的合法取值范围是10i&L->last+2intInsList(SeqList*L,inti,ElemTypee)intk;if(i<1)|(i>L->last+2)/*首先判断插入位置是否合法*/printf("插入位置i值不合法");return(ERROR);if(L->last>=MAXSIZE-1)printf("表已满无法插入");return(ERROR);for(k=L->last;k>=i-1;k-)/*为插入元素而移动位置*/return(OK);2 .建

8、立二叉链表方式存储的二叉树voidCreateBiTree(BiTree*bt)charch;ch=getchar();if(ch='.')*bt=NULL;elseCreateBiTree(&(*bt)->LChild);CreateBiTree(&(*bt)->RChild);Whenyouareoldandgreyandfullofsleep,Andnoddingbythefire,takedownthisbook,Andslowlyread,anddreamofthesoftlookYoureyeshadonce,andoftheirshad

9、owsdeep;Howmanylovedyourmomentsofgladgrace,Andlovedyourbeautywithlovefalseortrue,Butonemanlovedthepilgrimsoulinyou,Andlovedthesorrowsofyourchangingface;Andbendingdownbesidetheglowingbars,Murmur,alittlesadly,howlovefledAndpaceduponthemountainsoverheadAndhidhisfaceamidacrowdofstars.Thefurthestdistance

10、intheworldIsnotbetweenlifeanddeathButwhenIstandinfrontofyouYetyoudon'tknowthatIloveyou.ThefurthestdistanceintheworldIsnotwhenIstandinfrontofyouYetyoucan'tseemyloveButwhenundoubtedlyknowingthelovefrombothYetcannotbetogether.ThefurthestdistanceintheworldIsnotbeingapartwhilebeinginloveButwhenIplainlycannotresisttheyearningYetpretendingyo