湖南科技大学数据结构综合应用题

计算机——《数据结构》第1页共13页1．简述栈的基本操作2．给定权值组W={1，3，78，14，20，28}，建立哈夫曼树。3．试求下面的网络的最小生成树4.对一组关键字49，7，50，5，94，16，90，29，71，使用希尔排序，写出对31d时的一趟排序的结果。1-4题答案：1、栈的基本操作有：栈的建立，判栈满，判栈空，压栈，退栈和取栈顶元素等。2、3、4、5．写出队列的基本操作。6．对下面的二叉树（１）其中序遍历序列为（２）其后序遍历序列为7．给定一组关键字序列12，7，51，32，23，试构造一棵查找树。8．对一组关键字49，7，50，5，94，16，90，29，71，使用快速排序，试给出第一次划分过程。5-8题答案：5．队列的基本操作有：队列的建立，判队空，判队满，入队、出队及取队首元素等。6BDAEC15610569138101abdhc5eg144786628382014184131324565698649575094169029715716492950909471计算机——《数据结构》第2页共13页6．（１）中序遍历序列：dgbaechf（２）后序遍历序列：gdbehfca7．8．4975059416902971headtail4975059416902971headtail2975059416904971headtail2974959416905071headtail2971659449905071headtail2971654994905071headtail9．//设元素的类型为T，aList是存储顺序表的数组，maxSize是其最大长度；//p为新元素value的插入位置，插入成功则返回true，否则返回falsetemplateclassTboolarrListT::insert(constintp,constTvalue){inti;if(curLen=maxSize){//检查顺序表是否溢出coutThelistisoverflowendl;returnfalse;}if(p0||pcurLen){//检查插入位置是否合法coutInsertionpointisillegalendl;returnfalse;}for(i=curLen;ip;i--)aList[i]=aList[i-1];//从表尾curLen-1起往右移动直到paList[p]=value;//位置p处插入新元素curLen++;//表的实际长度增1returntrue;}12７513223计算机——《数据结构》第3页共13页36415210．图如下，请画出Kruskal算法构造最小生成树的过程。11．一份电文中共使用的字符有A，B，C，D，E，它们出现的频率依次为4，7，5，2，9。试画出其对应的Huffman树12．用拉链法建立Hash表，Hash函数为H(key)=keymod11,Hash表长度为10，现有一组关键字（61，18，30，72，13，24，12，11），请画出相应的Hash表。13．怎样将一棵树转化成等价的二叉树？试画出下列树所对应的二叉树，要求有中间过程图。9-13题答案：10、4566235561124356124356112435621124356321124356计算机——《数据结构》第4页共13页11、12、61mod11=618mod11=730mod11=772mod11=613mod11=224mod11=112mod11=111mod11=013、树转化为二叉树的方法如下：①将树中的各兄弟之间加一条连线。②对于任一结点，除保留宽经与最左边孩子的连线外，删除它与其它孩子之间的分支。③以树的根这轴心，将整棵树按顺时针方向旋转大约45○。0123456789432112435654321124356EBCDA271811976542611830^72^13^2412^11^计算机——《数据结构》第5页共13页14、画出具有三个结点的二叉树的所有形态。15、图如右，请画出prim算法构造最小生成树的过程。16、对于如下无向图，请画出其深度优先搜索和广度优先搜索生成的树（画出一棵即可）。17、用线性探测法建立Hash表，Hash函数为H(key)=keymod11,Hash表长度为10，现有一组关键字（61，18，30，72，13，24），请画出相应的Hash表。18、//设元素的类型为T；aList是存储顺序表的数组；p为即将删除元素的位置//删除成功则返回true，否则返回falsetemplateclassT//顺序表的元素类型为TboolarrListT::delete(constintp){inti;if(curLen=0){//检查顺序表是否为空coutNoelementtodelete\nendl;returnfalse;}36412536412536412513542计算机——《数据结构》第6页共13页if(p0||pcurLen-1){//检查删除位置是否合法coutdeletionisillegal\nendl;returnfalse;}for(i=p;icurLen-1;i++)aList[i]=aList[i+1];//从位置p开始每个元素左移直到curLencurLen--;//表的实际长度减1returntrue;}14-18题答案：14、15、16、注意：生成树是不唯一的，应该是一个生成树森林。所以此题还存在其它画法。ACBCBACBACBABCA11315131225513124255131263442551312613542计算机——《数据结构》第7页共13页设从结点1出发开始深度优先搜索，得到如下一棵深度优先生成树：设从结点1出发开始广度优先搜索，得到如下一棵广度优先生成树：17、012345678913246118307261mod11=618mod11=730mod11=872mod11=6→7→8→913mod11=224mod11=2→319．设一棵二叉树的先序遍历序列为：ABDFCEGH中序遍历序列为：BFDAGEHC（1）画出这棵二叉树。（5分）（2）画出这棵二叉树的后序线索树。（5分）（3）画出由这棵二叉树转换成的树（或森林）。（5分）20．设有正文AADBAACACCDACACAAD,字符集为A,B,C,D,设计一套二进制编码，使得上述正文的编码最短。（要求画出Huffman树并写出编码）（15分）21．已知一个无向图如下图所示，用Kruskal算法生成最小树（假设以①为起点，要求画出构造过程）。（10分）22．对于以下的图，写出它的四个不同的拓扑有序序列。（10分）1354213542计算机——《数据结构》第8页共13页++*+fhg*+abc+deBACEDFNPGHJMOLIK23．采用哈希函数H（k）=3*kmod13并用线性探测开放地址法处理冲突，在数列地址空间［0..12］中对关键字序列22,41,53,46,30,13,1,67,51。（1）构造哈希表（画示意图）；（5分）（2）求装填因子；（1分）（3）等概率下成功的和不成功的平均查找长度。（4分）24．数据结构与数据类型有什么区别？24.“数据结构”这一术语有两种含义，一是作为一门课程的名称；二是作为一个科学的概念。作为科学概念，目前尚无公认定义，一般认为，讨论数据结构要包括三个方面，一是数据的逻辑结构，二是数据的存储结构，三是对数据进行的操作（运算）。而数据类型是值的集合和操作的集合，可以看作是已实现了的数据结构，后者是前者的一种简化情况。25．将算术表达式（（a+b）+c*(d+e)+f）*(g+h)转化为二叉树。25.该算术表达式转化的二叉树如右图所示。26．将下列由三棵树组成的森林转换为二叉树。（只要求给出转换结果）HGDACJIBFEMPONKOL计算机——《数据结构》第9页共13页27.设一棵二叉树的先序、中序遍历序列分别为先序遍历序列：ABDFCEGH中序遍历序列：BFDAGEHC（1）画出这棵二叉树。（2）画出这棵二叉树的后序线索树。（3）将这棵二叉树转换成对应的树（或森林）。27.28.已知下列字符A、B、C、D、E、F、G的权值分别为3、12、7、4、2、8，11，试填写出其对应哈夫曼树HT的存储结构的初态和终态。29.对有五个结点{A,B,C,D,E}的图的邻接矩阵，05001020060010301000（1）．画出逻辑图；（2）．画出图的十字链表存储；（3）．基于邻接矩阵写出图的深度、广度优先遍历序列；30.30.一带权无向图的邻接矩阵如下图，试画出它的一棵最小生成树。AEDCBHGFAEDCBHGFnullABMFD(3)CEMHG计算机——《数据结构》第10页共13页设顶点集合为{1，2，3，4，5，6}，由右边的逻辑图可以看出，在{1，2，3}和{4，5，6}回路中，各任选两条边，加上（2，4），则可构成9棵不同的最小生成树。31.试写出用克鲁斯卡尔（Kruskal）算法构造下图的一棵最小支撑（或生成）树的过程。V（G）={1，2，3，4，5，6，7}E（G）={（1，6，4），（1，7，6），（2，3，5），（2，4，8），（2，5，12），（1，2，18）}32.设哈希(Hash)表的地址范围为0～17，哈希函数为：H(K)=KMOD16,K为关键字，用线性探测再散列法处理冲突，输入关键字序列:(10,24,32,17,31,30,46,47,40,63,49)造出哈希表，试回答下列问题：(1)画出哈希表示意图；(2)若查找关键字63，需要依次与哪些关键字比较?(3)若查找关键字60，需要依次与哪些关键字比较?(4)假定每个关键字的查找概率相等，求查找成功时的平均查找长度。（1）散列地址01234567891011121314151617关键字3217634924401030314647比较次数11631211133（2）查找关键字63，H（k）=63MOD16=15，依次与31，46，47，32，17，63比较。（3）查找关键字60，H（k）=60MOD16=12，散列地址12内为空，查找失败。（4）ASLsucc=23/1133.选取哈希函数Ｈ（key）=keymod7,用链地址法解决冲突。试在０-６的散列地址空间内对关键字序列｛31,23,17,27,19,11,13,91,61,41｝构造哈希表，并计算在等概率下成功查找的平均查找长度。1211111312345612564318412810202515523767计算机——《数据结构》第11页共13页ASLsucc=15/1034.设散列函数H(k)=Kmod7,散列表的地址空间为0-6，对关键字序列{32,13,49,18,22,38,21}按链地址法处理冲突的办法构造哈希表，并指出查找各关键字要进行几次比较。查找时，对关键字49,22,38,32,13各比较一次，对21,18各比较两次35.设有5个互不相同的元素a、b、c、d、e，能否通过7次比较就将其排好序？如果能，请列出其比较过程；如果不能，则说明原因。可以做到。取a与b进行比较，c与d进行比较。设ab,cd(ab和cd情况类似)，此时需2次比较，取b和d比较，若bd，则有序abd；若bd时则有序cdb，此时已进行了3次比较。再把另外两个元素按折半插入排序方法，插入到上述某个序列中共需4次比较，从而共需7次比较。36.请阅读下列算法，回答问题PROCEDUREsort（r，n）BEGINFORi:=2TOnDOBEGINx:=r(i)；r(O):=x；j:=i-1；WHILEx.keyr(j).keyDOBEGINr(j+1):=r(j);j:=j-1END;r(j+1):=xENDEND;问题一：这是什么类型的排序算法，该排序算法稳