《数据结构课 堂习 题1资料》由会员分享，可在线阅读，更多相关《数据结构课 堂习 题1资料（5页珍藏版）》请在金锄头文库上搜索。
1、数据结构课堂习题一、综合题。1. 已知如图所示的AOE-网，试求：（1） 每个事件的最早发生时间和最晚发生时间；（2） 每个活动的最早开始时间和最晚开始时间；（3） 给出关键路径。2. 已知以二维数组表示的图的邻接矩阵如下图所示。0123456001000001001011020000100300100004010100050000001600000001）并判别此图为有向图还是无向图。2）求所有顶点的度数之和。3）根据数组分别写出至序号为0的顶点开始进行遍历所得到的深度优先序列和广度优先序列。3. 给定集合6，9，16，17，15，3，14，2 (1) 用表示外部结点，用表示内部结点，构造相
2、应的huffman树：(2) 计算它的带权路径长度：(3) 写出它的huffman编码：4.画出下图所示的树对应的二叉树。ADBCHEGFKJI5. 从空树开始，逐个读入并插入下列关键字：（40，82，26，22，95，30，71，27），构造一颗二叉排序树，并求出在等概率情况下检索成功的平均检索长度。（7分）二、算法设计题1. 在带头结点的单链表L中删除第i个元素，并将删除的元素保存到变量*e中。int DelList(LinkList L,int i,ElemType *e) Node *pre,*r;int k;pre=L;k=0;while(pre-next!=NULL & knext
3、 ;k=k+1;if(!(pre-next) printf(删除结点的位置i不合理!);return ERROR;r=pre-next;pre-next=r-next; /*修改指针，删除结点r*/ *e=r-data; free(r); /*释放被删除的结点所占的内存空间*/printf (成功删除结点!);return OK;2.已知二叉树按照二叉链表方式存储，编写算法，计算二叉树中叶子结点的数目。int LeafCount(Bitree T) /求二叉树中叶子结点的数目if( ) return 0; /空树没有叶子else if(!T-lchild & !T-rchild) return
4、 ; /叶子结点else return /LeafCount3.定义有序表抽象数据类型，并据此类型设计折半查找算法。typedef struct int key; float info;JD; int binsrch(JD r,int n,int k) int low,high,mid,found; low=1; high=n; found=0; while( )&(found=0) mid= ; if(krmid.key) ; else if(k=rmid.key) found=1; else ; if( found= =1 ) return(mid); else return(0);一、综
5、合题（共40分）1二叉树的先序遍历序列ABDECFG,是中序遍历序列是DBEACGF,画出这棵二叉树,并给出后序遍历序列。2在一个链队列Q中,假定front和rear分别为队首和队后指针,写出进行S结点进队执行的操作（s为指针）。3一组记录的关键码为（46，79，56，38，40，84，27）利用快速排序的方法，求以第一个记录为基准得到的一次划分结果,并说明算法的稳定性。4. 已知以邻接表表示的图的存储结构如下图所示。1) 判别此图为有向图还是无向图。2) 求所有顶点的度数之和。3) 根据邻接表分别写出以序号为v1的顶点开始进行遍历所得到的深度优先序列和广度优先序列。5. 已知一组关键字(9,
6、14,21,17,68,20,2,27,55,11,10,69) 哈希函数为：H(key)=key MOD 13, 哈希表长为m=16，设每个记录的查找概率相等， 用链地址法处理冲突。1请构造哈希表。2求平均查找长度ASL。6已知一个图如下图所示(1) 请根据狄杰斯特拉算法求出从顶点1到其余各顶点的最短路径，并给出最短路径的求解过程。(2) 若去掉该图中的方向，请用克鲁斯卡尔算法构造出最小生成树。二、算法设计题（每空2分，20分）。1.在顺序表L中第i个数据元素之前插入一个元素e。 插入前表长n=L-last+1，i的合法取值范围是 1iL-last+2 int InsList(SeqList
7、 *L,int i,ElemType e) int k;if(iL-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. 建立二叉链表方式存储的二叉树。void CreateBiTree(BiTree *bt)char ch;ch = getchar(); if(ch=.) *bt=NULL; else ； ； CreateBiTree(&(*bt)-LChild); CreateBiTree(&(*bt)-RChild);
