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

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

1、2005年2006学年第二学期“数据构造考试试题A姓名 学号(序号)_ 答案隐藏 班号 要求：所有的题目的解答均写在答题纸上每张答题纸上要写清楚姓名、班号和学号，需写清楚题目的序号。每张答题纸都要写上姓名和序号。一、单项选择题每题2分，共20分1数据的运算a 。答：A。2. 链表不具备的特点是a 。答：参见本节要点3。此题答案为：A。3. 在顺序表中删除一个元素的时间复杂度为c。A.O(1) B.O(log2n)C.O(n) D.O(n2)答：C。4以下线性表的存储构造中具有随机存取功能的是 d 。A. 不带头结点的单链表 B. 带头结点的单链表C. 循环双链表 D. 顺序表解D。5. 一个栈

2、的进栈序列是a，b，c，d，e，那么栈的不可能的输出序列是c 。答：C。6. 循环队列qu的队空条件是d。A. (qu.rear+1)%MaxSize=(qu.front+1)%MaxSizeB. (qu.rear+1)%MaxSize=qu.front+1答：D。7. 两个串相等必有串长度相等且b。答：B。8. 用直接插入排序对下面四个序列进展递增排序，元素比拟次数最少的是 c 。A.94,32,40,90,80,46,21,69 B.32,40,21,46,69,94,90,80C.21,32,46,40,80,69,90,94 D.90,69,80,46,21,32,94,40答：C。9

3、. 以下序列不是堆大根或小根的是d。A.100,85,98,77,80,60,82,40,20,10,66 B.100,98,85,82,80,77,66,60,40,20,10C.10,20,40,60,66,77,80,82,85,98,100 D.100,85,40,77,80,60,66,98,82,10,20答：D。10. 以下排序方法中，b ，在初始序列已根本有序的情况下，排序效率最高。答：B。二、填空题每题2分，共10分1. 将f=1+(n3)转化成递归函数，其递归出口是，递归体是答： f(1)=1 f(n)=f(n-1)+评分标准：每空1分2广义表(),a,(a),(a)的长度

4、是 4 ，深度是3。答：43评分标准：每空1分3. 具有n个结点的二叉树采用二叉链存储构造，共有 n+1 个空指针域。答：n+1。4. 在有n个顶点的有向图中，每个顶点的度最大可达2(n-1) n-1 。答：2(n-1)。5. 外排序的根本方法是归并法。它一般要经历文件预处理和 多路归并两个阶段。答：产生初始归并段或顺串多路归并评分标准：每空1分三、问答题共30分1设n是偶数，试计算运行以下程序段后m的值并给出该程序段的时间复杂度需写出过程。6分int m=0,i,j;for (i=1;i=n;i+) for (j=2*i;j=n;j+) m+;i=1i=n/2(n-2i+1)(n+1)n/2

5、-2*(1+2+n/2)=(n+1)n/2-2*(n/2+1)*n/2/2=(n+1)n/2-(n/2+1)*n/2=n2/42. 如果对线性表的运算只有4种，即删除第一个元素，删除最后一个元素，在第一个元素前面插入新元素，在最后一个元素的后面插入新元素，那么最好使用以下哪种存储构造，需说明理由：10分1只有表尾指针没有表头指针的循环单链表2只有表尾指针没有表头指针的非循环双链表3只有表头指针没有表尾指针的循环双链表4既有表头指针也有表尾指针的循环单链表解此题答案为3，原因是在该链表上实现这4种运算的时间复杂度均为O(1)。评分标准：结论占34分，说明理由占6分，如果结论错误，但分析了一局部运

6、算的时间复杂度，给15分。3. 有一个有序表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)/2=R8=6275，9.9：R(9+9)/2=R9=75经4次比拟后查找成功，依次45、77、62和75关键字进展比拟。评分标准：比拟次数正确给3分，关键字正确给3分顺序要正确。局部正确给14分。4. 设二叉排序树中关键字互不一样，证明，其中最小关键字结点必无左孩子，最大关键字结点必无右孩子。8分证明：

7、因为假设最小元为min，假设最小元min有左孩子min，根据二叉排序树的定义得到minnext,*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二叉树中结

8、点个数)个结点的值。15分解：先序遍历序列中根结点对应的序号为1。当二叉树b为空时返回返回特殊字符( 为空格字符)，当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)其他情况对应的递归算法如下：ElemType PreNode(BTNode *b,int k,int n)/n的初值为根结点对应的先

9、序遍历序号即为1ElemType ch;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分提示：采用深度优先遍历或广度优先遍历求解，需写出相应的遍历算法。