数据结构期末考试试卷.docx
数据结构期末考试试卷一、判断题（每题1分，共10分）1 .线性表的逻辑顺序与存储顺序总是一致的。（错）2 .线索二叉树中，任一结点均有指向前趋和后继的线索。（错）3 .栈、队列、数组和串都是线性结构。（对）4 .KMP算法是一个不需要回溯的字符串模式匹配算法。（对）5 .图的生成树是该图的极小连通子图。（对）6 .树的后序遍历序列与其对应二叉树的后序遍历序列相同。（错）7 .二叉排序树的充要条件是任一结点的值均大于其左孩子的值，小于其右孩子的值。（错）8 .如果某排序算法是不稳定，则该排序算法没有实用价值。（错）9 .稀疏矩阵压缩存储后，就会失去随机存取功能。（对）10 .归并排序可以使用递归和非递归两种方法实现。（对）二、填空题（共20分,每空2分）1.设源串s=bababaaba,模式串p="babaa”,按照KMP算法进行模式匹配,当“sis2s3s4,f=".P2P3P4而也工05时，s5应与_P3_比较。2,下列算法的时间复杂性是O-ointfun（intn）inti=l,s=l;while（s<n）s+=+i;returni;）3 .表达式3/（x+2）-8所对应的后缀表达式是3X2+/8-。4 .假设以一维数组+作为n阶对称距阵A的存储空间，以行序为主序存储A的下三角，则元素A的值存储在S_41中。5 .下列函数的功能是实现两个字符串的比较，试根据字符串比较运算的定义，完善该函数：intstrcmp（chars,chart）i11ti；for（i=0;si&&ti;i+）if（si!=tli）return_si-ti；return_Slil-Uil;6 .最坏情况下，堆排序的时间复杂性为nlo氏n。7 .具有100个结点的完全二叉树，其叶子结点数为50o8 .利用拓扑排序算法可以判断一个有向图是否存在回路。9 .对于具有100个记录的文件，用顺序查找法查找索引表和块内元素，假定每块长度均为10个元素，则平均查找长度为10。三,简要回答下列问题(共30分)1 .评价一个排序算法好坏的标准是什么？你知道有哪些排序算法？试比较它们各自的性能。(10分)正确性：逻辑健壮性：多类数据测试可读性：格式结构化高效，低存储：空间/时间复杂度2 .图的存储方法主要有哪些？试举例具体说明图的存储结构；并说明Prim,Krurkal,Dijkstra,FlOyed算法的功能。(10分)图的存储方法有两种1：邻接表2：邻接矩阵PrimKruskal求最小生成树算法Dijkstra求图中从某个源点到其余各顶点的最短路径Floyd求每一个顶点之间的最短路径问题3 .已知一组关键字为(26,36,41,38,44,15,68,12,06,51,25),Hash函数定义为：H(key)=key%13o用拉链法解决冲突，建立HaSh表，分别计算查找成功和查找失败情况下的平均查找长度。(10分)查找成功：ASL=(7*1+1*2+1*3+1*4)/11=16/11查找失败时：ASL=(l+2+l÷l+l+l+4)13=11/13四.试编写折半查找算法。(10分)intSeqList:BinFind(inte)(intIow=O;inthigh=m_Data.size()-l;whilc(low<=high)(intmid=(Iow+high)2;if(m_Datamid=e)returnmid;if(m-Datamid<e)low=mid+l;elsehigh=mid-l;return-1;五、设有整型数组X,试编写算法：将负数集中在数组X的一端，正数集中在数组X的另一端。（10分）/C版voidPartition(intdata9intn)(inti=0,j=n-1;while(i<j)(while(datai<0)i+;if(i>n)return;while(datajj>0)j-;if(j<0)return;inttmp=datai;datai=datajj;dataj=tmp;)/C+版voidSeqList:Exchange()(inti=0;intj=m_Data.size()-1;while(i<j)(while(m_Datai<0)i+;if(i=m_Data.size()return;while(m-Dataj>0)j-;if(j<0)return;inttmp=m_Datai;m_Datai=m_Datajl;m_Dataj=tmp;)六、设采用邻接矩阵存储有向图，试编写算法：计算有向图中每个结点的入度和出度，入度和出度分别存入数组in和。Ut中。(10分)voidMGraph:InOutDegree(intin,intout)(for(inti=0;i<m_N;i+)for(intj=0;j<m_N;j+)(f(*m-Es)iU!=0&&(*m-Es)ij!=Inf)(outi+;inj+；七.设采用二叉链表存储二叉排序树，试编写算法：在二叉排序树中求任意两个不同结点的共同祖先。(IO分)BSTNode*BSTree:FindAncestor(intnodel,intnode2)intsmall=nodel;if(small<node2)small=node2;intbig=nodel+node2-small;BSTNodc*p=m_Root;while(p)(if(p->data>small&&p->data<big)returnp;if(p>>data<small)p=p->rchild;if(p->data>big)p=p->lchild;returnp;
