资源描述：
《《数据结构》期末试卷(C)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、专业班级姓名学号装订线天津理工大学考试试卷2006～2007年度第二学期《算法与数据结构》期末考试(补考)课程代码：1460300试卷编号：C命题日期：2007年7月14日答题时限：120分钟考试形式：闭卷笔试得分统计表：题号总分一二四五10010243630一）选择题(每题一分，共10分)1）循环队列A[m]的队头指针为front,则执行一数据元素入队后，front的值是（）。a)front=front+1b)front=(front+1)%(m-1)c)front=(front+1)%md)front=(front-1)%m2）若整数1,2,3,4,5依此进栈，只要栈不空，可在任何
2、时刻出栈，则出栈的序列不可能的是（）。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’,’b
3、b’]‘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]
4、,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)递减请将所选答案按题号填入下表：123456789101112131415二.填空题（每空2分，共24分）1）某矩阵存储一个
5、有向图，则第i个结点的入度是（）。2）有100个结点的完全二叉数的深度是（7）。3）已知某完全二叉树的第7层有8个叶结点，则其叶结点数最多是（120）个。4）树中所有叶结点的带权路径长度之和称为（）。5）ADT是指基于一个（）的数据类型以及这个类型上的一组操作。6）S[n]为一个循环队列，rear和front分别指向队头和队尾，则队列为满的条件是()。7）希尔排序算法的时间复杂度为（）。8）将中序表达式(A+B)*(C-D)/E转换为后序表达式＝（）。9）带头结点的单链循环表L为空，则L=（l->next==null）。10）双循环链表中，在指针P所指出的结点前插入由指针S所指出的结点
6、，需执行下列C语句：S->rlink=P；S->llink=P->llink；P->llink=S；(p->llink->rlink=s)。11)有向图的极大强连通子图称为（）。12)有向完全图有（）条边。3三.简答题（每题6分，共36分）1）已知稀疏矩阵A，1)试写出它的三元组表，：(3分)0100002)并画出带行指针向量的链式存储。(3分)。A=0000302000000000001000052）设,Key={1,4,9,16,25,36,34,49,64,81,100,121,144,6,17}。试画出：Hash函数为H(key)=keymod13；采用开散列法的存储结果。01
7、234567891011123）对数据表A=（50,12,80,31,1,5,44,58,61,10,76,29,35,200,166），写出采用快速排序算法完成前两趟的结果。4）图的边及权的表示为：e=(Vi,Vj,Wi)，其中Vi和Vj为一条边的两个结点，Wi为该边的权。现有某图G，其中:V=（A,B,C,D,E,F,G）;E=((A,B,2),(A,C,4),(A,D,5),(B,D,3),(B,E,10),(C,D,2),(C,F,5)
