数据结构 (第3卷)期末考试.doc

密封线学号姓名不准超过密封线，否则试卷作废，成绩记零分。系级班学号姓名数据结构 课程 考试试卷（第3 卷）考试专业班级 考试形式闭卷 考试时间120 分钟考试学期 考试类型 命题教师 题号一二三四五六七八总分分值20 26 2430100一、单选题（本题共10小题，每题2分，共20分）1. 组成数据的基本单位是（C）。（A） 数据项 （B）数据类型 （C）数据元素 （D）数据变量2. 线性表的链接实现有利于（A ）运算。（A）插入 （B）读表元 （C）查找 （D）定位3. 中序遍历一棵二叉排序树所得到的结点访问序列是键值的（D）序列。（A）递增或递减 （B）递减 （C）递增 （D）无序4. SubStr(DATA STRUCTURE,5,9)=(A )。（A）STRUCTURE （B）DATA （C）ASTRUCTUR （D） DATA STRUCTURE5. 下列哪一种形态不为树（ A）。ABABCD A (a) (b) (c) (d)6. 下列哪种排序需要的附加存储开销最大（C ）。（A）快速排序 （B）堆排序 （C）归并排序 （D）插入排序7. 对任何一棵树T，设n0,n1,n2,nm分别是度为0，1，2，,m的结点，则n0=（B）。（A）n1+n2+nm （B）1+n2+2n3+3n4+（m-1）nm（C）n2+2n3+3n4+（m-1）nm （D）2n1+3n2+(m+1)nm 8.在双向循环链表中，在p所指的结点之后插入s指针所指的结点，其操作是（ ）。 （A）p-next=s; s-prior=p; p-next-prior=s; s-next=p-next;（B）s-prior=p; s-next=p-next; p-next=s; p-next-prior=s;（C）p-next=s; p-next-prior=s; s-prior=p; s-next=p-next;（D）s-prior=p; s-next=p-next; p-next-prior=s; p-next=s;9. 在内部排序中，排序时不稳定的有（A ）。（A）快速排序 （B）冒泡排序（C）归并排序 （D）直接插入排序10. 设有1000个元素，用折半查找时，最大比较次数为（ B），最小比较次数为（D ）。（A）25 （B）10 （C）7 （D）1二、填空题（每空2分，共26分）1.在一个长度为n的顺序表中插入一个元素，平均需移动 个元素，时间复杂度是 。2.双向循环链表的主要优点是既可以找到节点的前驱，也可以找到节点的后驱 。3.上三角矩阵压缩存储的下标对应k= i(2n-i+1)/2+j-i+1(i= i+1 ;j-) if(Rjnext!=p; pf=pf-next); =p-next;free(p);return head;2. 已知数组r有n个元素，并已经由小到大排序。下面的函数search的功能是采用折半查找法查找值为e的元素，并返回其下标，如果找不到，返回-1。完成下面程序。（10分） int search(elem r,int n, int e)int i1,i2,k;i1=0; i2=n-1;while(i1= i2)k=( i1+ i2)/2;if(rk=e) ;if(erk)i2= ;else ;return-1;3. 以下算法是将线性表L中所有负数元素删除，返回被删除的元素个数。完成以下算法。（10分） typedef structint elem100;int length;SQ;int deln(SQ *L)/*算法思路是，对每个元素做以下循环，如果第i个元素大于等于0，且前面有c个小于0的元素，则将它前移c个位置*/int i,c; /*c将记录小于0的元素个数*/for(i=0,c=0;ilength;i+) if( 0)x-ei- =x-ei; x-length= ;return c;设顺序表的数据类型为： typedef struct elemtype *elem； int length； int listsize； Sqlist；模拟试题答案3一、一、选择题1.C.A.D4.A5.A 6.C7.B8.B9.A10.B二、填空题1.n/2,O(n)2.既可以方便地找到一个结点的后继，又可以方便地找到一个结点的前驱3.i(2n-i+1)/2+j-i+1(i3)4.2345.单左子树二叉树或孤立结点6.87.出度即OD(i)8.时间，空间9.i+1,exchang=Ture,i=i+1,exchange=False 三、应用题1.2.3.I4