2017《数据结构》期末考试试题及答案

第PAGE\*MERGEFORMAT1页共NUMPAGES\*MERGEFORMAT19页2017《数据结构》期末考试及答案HYPERLINK\l_Toc4497_WPSOffice_Level1《数据结构》期末考试试题及答案12HYPERLINK\l_Toc17981_WPSOffice_Level1试题1答案7HYPERLINK\l_Toc5810_WPSOffice_Level1《数据结构》期末考试试题及答案29HYPERLINK\l_Toc1215_WPSOffice_Level1试题2答案14HYPERLINK\l_Toc26248_WPSOffice_Level1《数据结构》期末考试试题及答案316HYPERLINK\l_Toc2142_WPSOffice_Level1试题3答案21《数据结构》期末考试试题及答案1一、                  单选题（每题2分，共20分）1.    栈和队列的共同特点是()。A.只允许在端点处插入和删除元素B.都是先进后出C.都是先进先出D.没有共同点2.    用链接方式存储的队列，在进行插入运算时().A.仅修改头指针　B.头、尾指针都要修改C.仅修改尾指针D.头、尾指针可能都要修改3.    以下数据结构中哪一个是非线性结构？()A.队列　　B.栈C.线性　　D.二叉树4.    设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每个元素占一个空间，问A[3][3](10)存放在什么位置？脚注(10)表示用10进制表示。A．688B．678C．692D．6965.    树最适合用来表示()。A.有序数据元素B.无序数据元素C.元素之间具有分支层次关系的数据D.元素之间无联系的数据6.    二叉树的第k层的结点数最多为().A．2k-1B.2K+1C.2K-1　　　D.2k-17.    若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二分查找，则查找A［3］的比较序列的下标依次为()A.1，2，3B.9，5，2，3C.9，5，3D.9，4，2，38.    对n个记录的文件进行快速排序，所需要的辅助存储空间大致为A.O（1）　　B.O（n）　　C.O（1og2n）D.O（n2）9.    对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用H（K）=K%9作为散列，则散列地址为1的元素有（）个，A．1B．2C．3D．410.设有6个结点的无向图，该图至少应有()条边才能确保是一个连通图。A.5B.6C.7D.8二、                  填空题（每空1分，共26分）1.       通常从四个方面算法的质量：_________、_________、_________和_________。2.       一个算法的时间复杂度为(n3+n2log2n+14n)/n2，其数量级表示为________。3.       假定一棵树的广义表表示为A（C，D（E，F，G），H（I，J）），则树中所含的结点数为__________个，树的深度为___________，树的度为_________。4.       后缀算式923+-102/-的值为__________。中缀算式（3+4X）-2Y/3对应的后缀算式为_______________________________。5.       若用链表存储一棵二叉树时，每个结点除数据域外，还有指向左孩子和右孩子的两个指针。在这种存储结构中，n个结点的二叉树共有________个指针域，其中有________个指针域是存放了地址，有________________个指针是空指针。6.       对于一个具有n个顶点和e条边的有向图和无向图，在其对应的邻接表中，所含边结点分别有_______个和________个。7.       AOV网是一种___________________的图。8.       在一个具有n个顶点的无向完全图中，包含有________条边，在一个具有n个顶点的有向完全图中，包含有________条边。9.       假定一个线性表为(12,23,74,55,63,40)，若按Key%4条件进行划分，使得同一余数的元素成为一个子表，则得到的四个子表分别为____________________________、___________________、_______________________和__________________________。10.   向一棵B_树插入元素的过程中，若最终引起树根结点的分裂，则新树比原树的高度___________。11.   在堆排序的过程中，对任一分支结点进行筛运算的时间复杂度为________，整个堆排序过程的时间复杂度为________。12.   在快速排序、堆排序、归并排序中，_________排序是稳定的。三、                  运算题（每题6分，共24分）在如下数组A中链接存储了一个线性表，表头指针为A[0].next，试写出该线性表。A01234567data 6050789034 40next357204 12.       请画出图10的邻接矩阵和邻接表。图103.   已知一个图的顶点集V和边集E分别为：V={1,2,3,4,5,6,7};E={(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15,(3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25};用克鲁斯卡尔算法得到最小生成树，试写出在最小生成树中依次得到的各条边。4.       画出向小根堆中加入数据4,2,5,8,3时，每加入一个数据后堆的变化。四、                  阅读算法（每题7分，共14分）1.    LinkListmynote(LinkListL){//L是不带头结点的单链表的头指针if(L&&L->next){q=L；L=L－>next；p=L；S1：while(p－>next)p=p－>next；S2：p－>next=q；q－>next=NULL；}returnL；}请回答下列问题：（1）说明语句S1的功能；（2）说明语句组S2的功能；（3）设链表表示的线性表为（a1,a2,…,an）,写出算法执行后的返回值所表示的线性表。2.    voidABC(BTNode*BT){ifBT{ABC(BT->left);ABC(BT->right);cout<data<<'';}}该算法的功能是：五、                  算法填空（共8分）二叉搜索树的查找——递归算法:boolFind(BTreeNode*BST,ElemType&item){if(BST==NULL)returnfalse;//查找失败else{if(item==BST->data){item=BST->data;//查找成功return___________;}elseif(itemdata)returnFind(______________,item);elsereturnFind(_______________,item);}//if} 六、                  编写算法（共8分）统计出单链表HL中结点的值等于给定值X的结点数。intCountX(LNode*HL,ElemTypex)试题1答案一、                     单选题（每题2分，共20分）1.A2.D3.D4.C5.C6.D7.D8.C9.D10.A二、                     填空题（每空1分，共26分）1.    正确性易读性强壮性高效率2.    O(n)3.    9334.    -134X*+2Y*3/-5.    2nn-1n+16.    e2e7.    有向无回路8.    n(n-1)/2n(n-1)9.    （12，40）（）（74）（23,55，63）10. 增加111. O(log2n)O(nlog2n)12. 归并三、                     运算题（每题6分，共24分）1.    线性表为：（78，50，40，60，34，90）2.    邻接矩阵：邻接表如图11所示：图113.    用克鲁斯卡尔算法得到的最小生成树为：(1,2)3,(4,6)4,(1,3)5,(1,4)8,(2,5)10,(4,7)204.    见图124444422255285283452843          图12四、                     阅读算法（每题7分，共14分）1.    （1）查询链表的尾结点（2）将第一个结点链接到链表的尾部，作为新的尾结点（3）返回的线性表为（a2,a3,…,an,a1）2.    递归地后序遍历链式存储的二叉树。五、                     算法填空（每空2分，共8分）trueBST->leftBST->right六、                     编写算法（8分）intCountX(LNode*HL,ElemTypex){inti=0;LNode*p=HL;//i为计数器while(p!=NULL){if(P->data==x)i++;p=p->next;}//while,出循环时i中的值即为x结点个数returni;}//CountX《数据结构》期末考试试题及答案2一、           单选题（每小题2分，共8分）1、在一个长度为n的顺序线性表中顺序查找值为x的元素时，查找成功时的平均查找长度（即x与元素的平均比较次数，假定查找每个元素的概率都相等）为()。AnBn/2C(n+1)/2D(n-1)/22、在一个单链表中,若q所指结点是p所指结点的前驱结点,若在q与p之间插入一个s所指的结点,则执行()。As→link=p→link;p→link=s;Bp→link=s;s→link=q;Cp→link=s→link;s→link=p;Dq→link=s;s→link=p;3、     栈的插入和删除操作在（）进行。A栈顶B栈底C任意位置D指定位置4、     由权值分别为11，8，6，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（）A24B71C48D53二、           填空题（每空1分，共32分）1、数据的逻辑结构被分为__________、___________、________和________四种。2、一种抽象数据类型包括______________和_____________两个部分。3、在下面的数组a中链接存储着一个线性表，表头指针为a[o].next，则该线性表为_________________________________________________。012345678 60564238 7425 4376201 datanext 4、在以HL为表头指针的带表头附加结点的单链表和循环单链表中，判断链表为空的条件分别为________________和____________________。5、用具有n个元素的一维数组存储一个循环队列，则其队首指针总是指向队首元素的___________，该循环队列的最大长度为__________。6、当堆栈采用顺序存储结构时，栈顶元素的值可用———————表示；当堆栈采用链接存储结构时，栈顶元素的值可用_______________表示。7、一棵高度为5的二叉树中最少含有_________个结点，最多含有________个结点；一棵高度为5的理想平衡树中，最少含有_________个结点，最多含有_________个结点。8、在图的邻接表中，每个结点被称为____________，通常它包含三个域：一是_____________；二是___________；三是_____________。9、在一个索引文件的索引表中，每个索引项包含对应记录的_________和___________两项数据。10、假定一棵树的广义表表示为A（B（C，D（E，F，G），H（I，J））），则树中所含的结点数为_________个，树的深度为_________,树的度为________,结点H的双亲结点为________,孩子结点为_______________。11、在堆排序的过程中，对任一分支结点进行筛运算的时间复杂度为_________,整个堆排序过程的时间复杂度为________________。12、在对m阶的B_树插入元素的过程中，每向一个结点插入一个索引项（叶子结点中的索引项为关键字和空指针）后，若该结点的索引项数等于______个，则必须把它分裂为_______个结点。 三、           运算题（每小题6分，共24分）1、已知一组记录的排序码为（46，79，56，38，40，80,95，24），写出对其进行快速排序的每一次划分结果。2、一个线性表为B=（12，23，45，57，20，03，78，31，15，36），设散列表为HT[0..12]，散列函数为H（key）=key%13并用线性探查法解决冲突，请画出散列表，并计算等概率情况下查找成功的平均查找长度。3、已知一棵二叉树的前序遍历的结果序列是ABECKFGHIJ，中序遍历的结果是EBCDAFHIGJ，试写出这棵二叉树的后序遍历结果。4、已知一个图的顶点集V各边集G如下：V={0，1，2，3，4，5，6，7，8，9}；E={（0，1），（0，4），（1，2），（1，7），（2，8），（3，4），（3，8），（5，6），（5，8），（5，9），（6，7），（7，8），（8，9）}当它用邻接矩阵表示和邻接表表示时，分别写出从顶点V0出发按深度优先搜索遍历得到的顶点序列和按广度优先搜索遍历等到的顶点序列。假定每个顶点邻接表中的结点是按顶点序号从大到小的次序链接的。图深度优先序列广度优先序列邻接矩阵表示时  邻接表表示时  四、           阅读算法，回答问题（每小题8分，共16分） 1、假定从键盘上输入一批整数，依次为：786345309134–1，请写出输出结果。#include#includeconstintstackmaxsize=30;typedefintelemtype;structstack{elemtypestack[stackmaxsize];inttop;};#include“stack.h”voidmain(){stacka;initstack(a);intx;cin>>x;while(x!=-1){push(a,x);cin>>x;}while(!stackempty(a))cout<voidBinTree：：unknown(BinTreeNode*t){BinTreeNode*p=t,*temp;if(p!=NULL){temp=p→leftchild;p→leftchild=p→rightchild;p→rightchild=temp;unknown(p→leftchild);undnown(p→rightchild);}}该算法的功能是：________________________________五、           算法填空，在画有横线的地方填写合适的

内容

财务内部控制制度的内容财务内部控制制度的内容人员招聘与配置的内容项目成本控制的内容消防安全演练内容

（10分）对顺序存储的有序表进行二分查找的递归算法。intBinsch(ElemTypeA[],intlow,inthigh,KeyTypeK){if(low<=high){intmid=1if(K==A[mid].key)returnmid;elseif(K=0；i--)for(j=0；jnext;p->next=Q.front->next;（B）、p=Q.front->next;Q.front->next=p->next;（C）、p=Q.rear->next;p->next=Q.rear->next;（D）、p=Q->next;Q->next=p->next;9．Huffman树的带权路径长度WPL等于（）（A）、除根结点之外的所有结点权值之和（B）、所有结点权值之和（C）、各叶子结点的带权路径长度之和（D）、根结点的值10．线索二叉链表是利用（）域存储后继结点的地址。（A）、lchild（B）、data（C）、rchild（D）、root填空题逻辑结构决定了算法的，而存储结构决定了算法的。栈和队列都是一种的线性表，栈的插入和删除只能在进行。线性表（a1,a2,…,an）的顺序存储结构中，设每个单元的长度为L，元素ai的存储地址LOC(ai)为已知一双向链表如下(指针域名为next和prior)：yxeqp现将p所指的结点插入到x和y结点之间，其操作步骤为：；；；；5．n个结点无向完全图的的边数为，n个结点的生成树的边数为。6．已知一有向无环图如下：BACDFEG任意写出二种拓扑排序序列：、。7．已知二叉树的中序遍历序列为BCA，后序遍历序列为CBA，则该二叉树的先序遍历序列为，层序遍历序列为。应用题设散列函数H(k)=k%13,设关键字系列为{22,12,24,6,45,7,8,13,21},要求用线性探测法处理冲突。(6分)(1)构造HASH表。(2)分别求查找成功和不成功时的平均查找长度。给定表（19,14,22,15,20,21,56,10）.（8分）按元素在表中的次序，建立一棵二叉排序树对(1)中所建立的二叉排序树进行中序遍历，写出遍历序列。画出对(2)中的遍历序列进行折半查找过程的判定树。已知二个稀疏矩阵A和B的压缩存储三元组表如下：ABijVijV13-525224633725241342-152-9529558写出A-B压缩存储的三元组表。（5分）已知一维数组中的数据为（18,12,25,53,18）,试写出插入排序（升序）过程。并指出具有n个元素的插入排序的时间复杂度是多少？(5分)已知一网络的邻接矩阵如下，求从顶点A开始的最小生成树。(8分，要有过程)ABCDEF（1）求从顶点A开始的最小生成树。（2）分别画出以A为起点的DFS生成树和BFS生成树。6．已知数据六个字母及在通信中出现频率如下表：ABCDEF0.150.150.10.10.20.3把这些字母和频率作为叶子结点及权值，完成如下工作(7分，要有过程)。画出对应的Huffman树。计算带权路径长度WPL。求A、B、C、D、E、F的Huffman编码。已知有如下的有向网：A25364106122EBDC求顶点A到其它各顶点的最短路径（采用Dijkstra算法，要有过程）。（6分）设计题（30分，每题10分,用C语言写出算法，做在答题纸上）已知线性表（a1,a2,…,an）以顺序存储结构为存储结构，其类型定义如下：#defineLIST_INIT_SIZE100//顺序表初始分配容量typedefstruct{Elemtype*elem;//顺序存储空间基址intlength;//当前长度（存储元素个数）}SqList;设计一个算法，删除其元素值为x的结点（假若x是唯一的）。并求出其算法的平均时间复杂度。其算法函数头部如下：StatusListDelete(Sqlist&L,Elemtypex){……}an…a2a12．设顺序栈如左图所示。其中结点定义如下：toptypedefstruct{Elemtype*base;//栈底指针Elemtype*top;//栈顶指针}Stack;设计算法，将栈顶元素出栈并存入e中．base3．设二叉链树的类型定义如下：typedefintElemtype;typedefstructnode{Elemtypedata;structnode*lchild,*rchild;}BinNode,*BinTree;试写出求该二叉树叶子结点数的算法:StatusCountLeaves(BinTree&root,int&n){//nisthenumberofleaves……}试题3答案选择题（每题1分）C2、D3、A4、D5、C6、D7、A8、B9、C10、C填空题设计、实现特殊、栈顶LOC（a1）+(i-1)*Lp->next=q->next;q->next->prior=p;q->next=p;p->prior=q;n(n-1)/2、n-1ADCBFEG、ABCDEFFGABC、ABC应用题1.（1）Hash表（4分）地址0123456789101112关键安132164572282412探测次数171231311（2）查找成功的平均查找长度：（1分）（5*1+1*2+2*3+1*7）/9=20/9查找不成功的平均查找长度：（1分）（2+1+9+8+7+6+5+4+3+2+1）/13=2.（1）、构造（3分）1914221015205621(2)、1014151920212256（2分）（3）、（3分）3、(5分，每行0.5)ijv13-524633741342-15218558初始关键字：[18]12255318第一趟：[1218]255318第二趟：[121825]5318第三趟：[12182553]18第四趟：[1218182553]（4分）O（n2）（1分）。5、7分（1）4分AB1C325D4EF（2）4分6、(1)3分EFABCD（2）WPL=0.1*3+0.1*3+0.2*2+0.15*3+0.15*3+03*21=(1分)（3）A：010B：011C：110D：111E：00F；10（3分）7、A-B：（A、B）1分A-C：（A、D、C）2分A-D：（A、D）1分A-E：（A、D、E）2分设计题（30分）1、(10分)StatusListDelete(Sqlist&L,ElemTypex){inti,j;for(i=0;ilength;i++)if(L->elem[i]==x)break;if(i=L->length)returnERROR;for(j=i;jlengthi-1;j++)L->elem[j]=L->elem[j+1];L->length--;}（8分）平均时间复杂度：（2分）设元素个数记为n，则平均时间复杂度为：2、（10分）voidpop(Stack&S,Elemtype&e){if(S.top==S.base)returnERROR;S.top--;e=*s.top;}3、（10分）voidCountLeaves(BinTreeT,int&n){if(T){if((!(T->lchild)&&!(T->rchild))n++;CountLeaves(T->lchild,n);CountLeaves(T->rchild,n);}}