数据构造期末考试试题(含答案).docx

《数据构造期末考试试题(含答案).docx》由会员分享，可在线阅读，更多相关《数据构造期末考试试题(含答案).docx（10页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据构造期末考试试题(含答案)2005年2006学年第二学期“数据构造考试试题A姓名学号(序号)_答案隐藏班号要求：所有的题目的解答均写在答题纸上每张答题纸上要写清楚姓名、班号和学号，需写清楚题目的序号。每张答题纸都要写上姓名和序号。一、单项选择题每题2分，共20分1数据的运算a。A.效率与采用何种存储构造有关B.是根据存储构造来定义的C.有算术运算和关系运算两大类D.必须用程序设计语言来描绘答：A。2.链表不具备的特点是a。A.可随机访问任一结点B.插入删除不需要移动元素C.不必事先估计存储空间D.所需空间与其长度成正比答：参见本节要点3。此题答案为：A。3.在顺序表中删除一个元素的时间复杂

2、度为c。A.O(1)B.O(log2n)C.O(n)D.O(n2)答：C。4下面线性表的存储构造中具有随机存取功能的是d。A.不带头结点的单链表B.带头结点的单链表C.循环双链表D.顺序表解D。5.一个栈的进栈序列是a，b，c，d，e，则栈的不可能的输出序列是c。A.edcbaB.decbaC.dceabD.abcde答：C。6.循环队列qu的队空条件是d。A.(qu.rear+1)%MaxSize=(qu.front+1)%MaxSizeB.(qu.rear+1)%MaxSize=qu.front+1C.(qu.rear+1)%MaxSize=qu.frontD.qu.rear=qu.fro

3、nt答：D。7.两个串相等必有串长度相等且b。A.串的各位置字符任意B.串中各位置字符均对应相等C.两个串含有一样的字符D.两个所含字符任意答：B。8.用直接插入排序对下面四个序列进行递增排序，元素比拟次数最少的是c。A.94,32,40,90,80,46,21,69B.32,40,21,46,69,94,90,80C.21,32,46,40,80,69,90,94D.90,69,80,46,21,32,94,40答：C。9.下面序列不是堆大根或小根的是d。A.100,85,98,77,80,60,82,40,20,10,66B.100,98,85,82,80,77,66,60,40,20,1

4、0C.10,20,40,60,66,77,80,82,85,98,100D.100,85,40,77,80,60,66,98,82,10,20答：D。10.下面排序方法中，b，在初始序列已基本有序的情况下，排序效率最高。A.直接选择排序B.xx排序C.快速排序D.堆排序答：B。二、填空题每题2分，共10分1.将f=1+(n3)转化成递归函数，其递归出口是，递归体是答：f(1)=1f(n)=f(n-1)+评分标准：每空1分2广义表(),a,(a),(a)的长度是4，深度是3。答：43评分标准：每空1分3.具有n个结点的二叉树采用二叉链存储构造，共有n+1个空指针域。答：n+1。4.在有n个顶点的

5、有向图中，每个顶点的度最大可达2(n-1)n-1。答：2(n-1)。5.外排序的基本方法是归并法。它一般要经历文件预处理和多路归并两个阶段。答：产生初始归并段或顺串多路归并评分标准：每空1分三、问答题共30分1设n是偶数，试计算运行下列程序段后m的值并给出该程序段的时间复杂度需写出经过。6分intm=0,i,j;for(i=1;i3.有一个有序表R1.13=2,3,5,10,32,41,45,62,75,77,85,95,100，当用二分查找法查找关键字为75的结点时，经多少次比拟后查找成功，依次与哪些关键字进行比拟？6分解：1.13：R(1+13)/2=R7=4575，8.9：R(8+9)/

6、2=R8=62next,*r1,*r2;L1=L;r1=L1;L2=(LinkList*)malloc(sizeof(LinkList);r2=L2;while(p!=NULL)if(p-data%2=1)/为奇数r1-next=p;r1=p;p=p-next;else/为偶数r2-next=p;r2=p;p=p-next;r1-next=r2-next=NULL;评分标准：根据算法的正确性评分，不考虑算法的时间复杂度。2假设二叉树采用二叉链存储构造存储，设计一个算法，求先序遍历序列中第k(1k二叉树中结点个数)个结点的值。15分解：先序遍历序列中根结点对应的序号为1。当二叉树b为空时返回返回

7、特殊字符(为空格字符)，当k=n时表示找到了知足条件的结点，返回b-data；当kn时，在左子树中查找，若找到了返回该值，否则在右子树中查找，并返回其结果。对应的递归模型如下：f(b,k,n)=当b=NULL时返回特殊字符f(b,k,n)=b-data当k=nf(b,k,n)=(ch=f(b-lchild,k,n+1)=?f(b-rchild,k,n+1):ch)其他情况对应的递归算法如下：ElemTypePreNode(BTNode*b,intk,intn)/n的初值为根结点对应的先序遍历序号即为1ElemTypech;if(b=NULL)return;if(n=k)return(b-data);ch=PreNode(b-lchild,k,n+1);/遍历左子树if(ch!=)return(ch);/在左子树中找到后返回ch=PreNode(b-rchild,k,n+1);/遍历右子树return(ch);/返回右子树中的遍历结果评分标准：假如先求出先序序列放在一个数组中，再取第k个元素也正确。另外，根据算法的正确性评分，不考虑算法的时间复杂度。3.假设图G采用邻接表存储，设计一个算法，判定无向图G能否连通。若连通则返回1；否则返回0。15分提示：采用深度优先遍历或广度优先遍历求解，需写出相应的遍历算法。