数据结构试卷(5).doc

数据结构试卷(五)一、选择题(20分)( )。(A)数据项  (B)数据类型  (C)数据元素  (D)(50,40,95,20,15,70,60,45),则以增量d=4的一趟希尔排序结束后前4条记录关键字为( )。(A)40,50,20,95  (B)15,40,60,20(C)15,20,40,45  (D)45,40,15,(25,50,15,35,80,85,20,40,36,70),其中含有5个长度为2的有序子表,则用归并排序的方法对该记录关键字序列进行一趟归并后的结果为( )。(A)15,25,35,50,20,40,80,85,36,70(B)15,25,35,50,80,20,85,40,70,36(C)15,25,35,50,80,85,20,36,40,70(D)15,25,35,50,80,20,36,40,70,(“DATASTRUCTURE”,5,9)的返回值为( )。(A)“STRUCTURE”    (B)“DATA”(C)“ASTRUCTUR”    (D)“DATASTRUCTURE”,现要求插入一个新结点后使得单链表仍然保持有序,则该操作的时间复杂度为( )。(A)O(log2n)  (B)O(1)  (C)O(n2)  (D)O(n),度数为1的结点数为Nl,……,度数为m的结点数为Nm,则N0=( )。(A)Nl+N2+……+Nm    (B)l+N2+2N3+3N4+……+(m-1)Nm(C)N2+2N3+3N4+……+(m-1)Nm  (D)2Nl+3N2+……+(m+1),则用二分查找查找元素X最多需要比较( )次。(A)25  (B)10  (C)7    (D)={(a,b),(a,e),(a,c),(b,e),(e,d),(d,f),(f,c)},则从顶点a出发可以得到一种深度优先遍历的顶点序列为( )。(A)abedfc  (B)acfebd  (C)aebdfc    (D)、2、3、……、n,经过栈的作用后输出序列的第一个元素是n,则输出序列中第i个输出元素是( )。(A)n-i  (B)n-1-i  (C)n+1-i    (D)不能确定10设一组初始记录关键字序列为(45,80,55,40,42,85),则以第一个记录关键字45为基准而得到一趟快速排序的结果是( )。(A)40,42,45,55,80,83  (B)42,40,45,80,85,88(C)42,40,45,55,80,85  (D)42,40,45,85,55,80二、填空题(共20分)[0:n-1],其中第一个栈项指针top1的初值为-1,第二个栈顶指针top2的初值为n,则判断共享栈满的条件是____________________。。,如果按照行的顺序将下三角矩阵中的元素(包括对角线上元素)存放在n