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

2005年－2006学年第二学期“数据结构”考试试题（A）姓名学号(序号)_答案隐藏班号要求：所有的题目的解答均写在答题纸上（每张答题纸上要写清楚姓名、班号和学号），需写清楚题目的序号。每张答题纸都要写上姓名和序号。一、单项选择题（每小题2分，共20分）1．数据的运算a。A.效率与采用何种存储结构有关B.是根据存储结构来定义的C.有算术运算和关系运算两大类D.必须用程序设计语言来描述答：A。2.链表不具备的特点是a。A.可随机访问任一结点B.插入删除不需要移动元素C.不必事先估计存储空间D.所需空间与其长度成正比答：参见本节要点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.一个栈的进栈序列是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.front答：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,66}B.{100,98,85,82,80,77,66,60,40,20,10}C.{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，在初始序列已基本有序的情况下，排序效率最高。A.直接选择排序B.昌泡排序C.快速排序D.堆排序答：B。二、填空题（每题2分，共10分）1.将f=1+++…(n3)转化成递归函数，其递归出口是①，递归体是②答：①f(1)=1②f(n)=f(n-1)+评分标准：每空1分2．广义表((),a,(a),((a)))的长度是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分）intm=0,i,j;for(i=1;i=n;i++)for(j=2*i;j=n;j++)m++;∑i=1```i=n/2(n-2i+1)(n+1)n/2-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)。评分标准：结论占3～4分，说明理由占6分，如果结论错误，但分析了一部分运算的时间复杂度，给1～5分。3.有一个有序表R[1..13]={2,3,5,10,32,41,45,62,75,77,85,95,100}，当用二分查找法查找关键字为75的结点时，经多少次比较后查找成功，依次与哪些关键字进行比较？（6分）解：1..13：R[(1+13)/2]=R[7]=4575，8..13：R[(8+13)/2]=R[10]=7775，8..9：R[(8+9)/2]=R[8]=6275，9..9：R[(9+9)/2]=R[9]=75经4次比较后查找成功，依次45、77、62和75关键字进行比较。评分标准：比较次数正确给3分，关键字正确给3分（顺序要正确）。部分正确给1～4分。4.设二叉排序树中关键字互不相同，证明，其中最小关键字结点必无左孩子，最大关键字结点必无右孩子。（8分）证明：因为假设最小元为min，若最小元min有左孩子min'，根据二叉排序树的定义得到min'min，与min是最小元矛盾，由此反证出最小元必无左孩子；同理可反证出最大元必无右孩子。评分标准：若说明了二叉排序树的性质，给4～6分。四、算法设计题（共40分）1．设计一个算法，将一个头结点为L的单链表（假设结点值为整数）分解成两个单链表L1和L2，使得L1链表中含有原链表L1中值为奇数的元素，而L2链表中含有原链表A中值为偶数的元素，且保持原来的相对顺序。（10分）解：采用尾插法建立表L1和L2。算法如下：voidsplit(LinkList*L,LinkList*&L1,LinkList*&L2){LinkList*p=L-next,*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(1≤k≤二叉树中结点个数)个结点的值。（15分）解：先序遍历序列中根结点对应的序号为1。当二叉树b为空时返回返回特殊字符(''为空格字符)，当k==n时表示找到了满足条件的结点，返回b-data；当k≠n时，在左子树中查找，若找到了返回该值，否则在右子树中查找，并返回其结果。对应的递归模型如下：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的初值为根结点对应的先序遍历序号即为1{ElemTypech;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分）提示：采用深度优先遍历或广度优先遍历求解，需写出相应的遍历算法。