《数据结构》期末试卷(C).doc

2006~2007年度第二学期《算法与数据结构》期末考试(补考)课程代码:1460300试卷编号:C命题日期:2007年7月14日答题时限:120分钟考试形式:闭卷笔试得分统计表:题号总分一二四五**********一)选择题(每题一分,共10分)1)循环队列A[m]的队头指针为front,则执行一数据元素入队后,front的值是()。front=front+1b)front=(front+1)%(m-1)c)front=(front+1)%md)front=(front-1)%m2)若整数1,2,3,4,5依此进栈,只要栈不空,可在任何时刻出栈,则出栈的序列不可能的是()。a)2,3,4,1,5b)1,5,3,4,2c)2,3,1,4,5d)1,5,4,3,23)指针P和Q指向双循环链表L的两个元素,P所指元素是Q所指元素的直接后继的条件是()。a)P==Qb)Q->rlink==P->rlinkc)P->rlink==Qd)Q->rlink==P4)下列序列是执行第一趟快速排序得到的序列的是()。a)[‘da’,’ax’,’ed’,’de’,’bb’]’ff’[‘ha’,’gc’]b)[‘cd’,’ed’,’ax’,’da’]’ff’[‘ha’,’gc’,’bb’]c)[‘gc’,’ax’,’ed’,’cd’,’bb’]‘ff’[‘da’,’ha’]d][‘ax’,’bb’,’cd’,’da’,]’ff’[‘ed’,’gc’,’ha’]5)数据表中有10000个元素,若仅找出其中的10个最大元素,则采用最节省时间的算是()。a)快速排序b)希尔排序c)直接选择排序d)堆排序6)折半(二分)查找法要求查找表中各元素的键值排列顺序必须是()。a)无序b)有序c)递增d)递减7)对键值序列(12,13,11,18,60,15,7,18,25,100,23,231),用筛选法建堆,则开始调整的键值必须是()。a)100b)12c)60d)158)对有18个元素的有序表a[1],a[2],…..a[17],a[18]作折半(二分)查找,则查找a[3]的比较序列的下标为()。a)1,2,3b)9,5,2,3c)9,5,3d)9,4,2,39)广义表L=((a,b),(c,d),e),取出元素c的操作是()。a)head(tail(head(L)))b)head(head(tail(L)))c)tail(tail(tail(L)))d)tail(head(tail(L)))10)折半(二分)查找法要求查找表中各元素的键值排列顺序必须是()。a)无序b)有序c)递增d)递减请将所选答案按题号填入下表:(每空2分,共24分)1)某矩阵存储一个有向图,则第i个结点的入度是()。2)有100个结点的完全二叉数的深度是(7)。3)已知某完全二叉树的第7层有8个叶结点,则其叶结点数最多是(120)个。4)树中所有叶结点的带权路径长度之和称为()。5)ADT是指基于一个()的数据类型以及这个类型上的一组操作。6)S[n]为一个循环队列,rear和front分别指向队头和队尾,则队列为满的条件是()。7)希尔排序算法的时间复杂度为()。8)将中序表达式(A+B)*(C-D)/E转换为后序表达式=()。9)带头结点的单链循环