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

专业 班级 姓名 学号 装 订 线天津理工大学考试试卷2006 2007年度第二学期算法与数据结构 期末考试(补考)课程代码： 1460300 试卷编号： C 命题日期： 2007年 7月 14 日答题时限： 120 分钟 考试形式：闭卷笔试得分统计表： 题号总分一 二 四五 10010243630一）选择题(每题一分，共10分)1）循环队列Am的队头指针为front,则执行一数据元素入队后，front的值是（）。a) front=front+1 b)front=(front+1)%(m-1) c) front =( front +1)%m d)front=( front -1)%m2）若整数 1,2,3,4,5依此进栈，只要栈不空，可在任何时刻出栈，则出栈的序列不可能的是（ ）。 a) 2,3,4,1,5 b) 1,5,3,4,2 c) 2,3,1,4,5 d) 1,5,4,3,23）指针P和Q指向双循环链表L的两个元素，P所指元素是Q所指元素的直接后继的条件是（ ）。 a) P=Q b) Q-rlink=P-rlink c) P-rlink=Q d) Q-rlink=P4)下列序列是执行第一趟快速排序得到的序列的是( )。a)da,ax,ed,de,bbffha,gc b) cd,ed,ax,daffha,gc,bb c) gc,ax,ed,cd,bbffda,ha d ax,bb,cd,da,ffed,gc,ha5）数据表中有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) 100 b) 12 c) 60 d) 158) 对有18个元素的有序表a1,a2,.a17,a18作折半（二分）查找，则查找a3的比较序列的下标为( )。a) 1,2,3 b) 9,5,2,3 c) 9,5,3 d) 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）某矩阵存储一个有向图，则第i个结点的入度是（ ）。2）有100个结点的完全二叉数的深度是（ 7 ）。3）已知某完全二叉树的第7层有8个叶结点，则其叶结点数最多是（ 120 ）个。4）树中所有叶结点的带权路径长度之和称为（ ）。5）ADT是指基于一个（ ）的数据类型以及这个类型上的一组操作。6）Sn为一个循环队列，rear 和front 分别指向队头和队尾，则队列为满的条件是( )。7）希尔排序算法的时间复杂度为（ ）。8）将中序表达式(A+B)*(C-D)/E转换为后序表达式（ ）。9）带头结点的单链循环表L为空，则L=（ l-next=null ）。10）双循环链表中，在指针P所指出的结点前插入由指针S所指出的结点，需执行下列C语句：S-rlink=P；S-llink=P-llink；P-llink=S；( p-llink-rlink=s )。11)有向图的极大强连通子图称为（ ）。12)有向完全图有（ ）条边。三.简答题（每题6分，共36分）1）已知稀疏矩阵A， 1) 试写出它的三元组表，：(3分)0 1 0 0 0 0 2)并画出带行指针向量的链式存储。(3分)。 A = 0 0 0 0 3 02 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 5 2）设,Key=1,4,9,16,25,36,34,49,64,81,100,121,144,6,17。试画出：Hash函数为H(key)=keymod 13；采用开散列法的存储结果。 0 1 2 3 4 5 6 7 8 9 10 11 12 3）对数据表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),(D,F,8),(D,G,4),(D,E,7),(F,G,1),(E,G,6)。画出该图的最小生成树。并将其转换为二叉树。5）已知一棵二叉树先序遍历的结点序列为：A,B,E,F,G,C,D；中序遍历的结点序列为：E,G,F,B,C,D,A。 （1）请画出这棵二叉树；（3分） （2）请画出这棵二叉树的中序线索树。（3分）6）对数据表A=(70,12,20,31,150,44,66,200,30,80,79,23,126)采用堆排序方法。画出排完两个较大的两个数后的堆的示意图。（3分+3分）四）编程序题（共30分）（下列算法可使用教科书中的结构描述）1）用二叉链表存储二叉树，试用C编写一递归算法：中序遍历二叉树，并将结点按遍历的先后次序采用头插入方法建立一带头结点的单链表，并画出单链表的示意图。（10分）答:2）知带