资源描述：
《数据结构期末复习资料.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、南京理工大学泰州科技学院课程考试试卷(学生考试用)课程名称：数据结构A学分：4教学大纲编号： 试卷编号：考试方式：闭卷满分分值：100考试时间：120分钟组卷日期：2011年12月10日组卷教师(签字)：朱保平审定人(签字)：学生班级：10计算机、10计信管09专升本学生学号：学生姓名：7.设单链表中结点的结构为（data,next）。已知指针p所指结点不是尾结点，若在指针p所指结点之后插入结点s，则应执行下列哪一个操作？A)s->next=p;p->next=s；B)s->next=p->next;p->next=s；C)s->
2、next=p->next;p=s;D)p->next=s;s->next=p;8.具有1998个结点的二叉树的最小深度为().A.10B.11C.12D.139.无向图G=（V，E），其中：V={a,b,c,d,e,f},E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)}对该图进行广度优先遍历，得到的顶点序列正确的是（）。A.a,b,e,c,d,fB.a,c,f,e,b,dC.a,e,b,c,f,dD.a,e,d,f,c,b10.在一棵二叉树中，度为2的结点有30个，度为1的结点有50个，则二叉树
3、总的结点数有()。A.109B.110C.111D.11211.若用起泡排序对序列{11,14,8,29,12,5,70,8,10,1,20}从大到小排序,需要()次比较。A.45B.46C.55D.6612．一棵具有2092个结点的完全二叉树，其度数为2的结点数为（）。A.1045B.1046C.1047D.104813．已知一组数为{3,4,5,6,7},用这组数构成的哈夫曼树的带权路径长度（）。A.57B.69C.71D.7214．一棵20阶B-树当插入一结点引起结点的分裂时，则右子树上有（）个结点。A.7B.8C.9D.1015
4、．设哈希表长为13，哈希函数是H(key)=key%11,表中已有数据的关键字为15,27,17,51共四个，现要将关键字为37的结点加到表中，用二次探测再散列解决哈希表解决冲突，则放入的位置是（）。A.3B.4C.5D.616．线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（）存储方式最节省运算时间。A.单链表B.仅有头指针的单循环链表C.双链表D.仅有尾指针的单循环链表一、选择题（每题2分，共40分）1．树最适合用来表示（）。A.有序数据元素B.无序数据元素C.元素之间具有分支层次关系的数据D.元素之间
5、无联系的数据2．一个堆是一棵（）二叉树。A.普通B.排序C.满D.完全3．已知关键字的序列，依次构造二叉树，当插入38时引起二叉树的不平衡，则它的旋转类型为（）。A.LRB.RLC.RRD.LL4．二叉树的先序和中序遍历序列分别是ABCDEFGH，CBEDFAGH，该二叉树是由（）棵树的森林转换而来的。A.2B.3C.4D.55．以下是平衡二叉树的是（）。A．B．C．D．6．有一个有序表为{8,15,20,22,32,41,45,62,75,77,82,85,97}，当二分查找值为22的数据时要进行（）次比较。A.2B.3C.4D.5第
6、1页共2页课程名称：数据结构A学分：试卷编号：2．根据下图所示的AOE网，顶点V1,V2,V3,V4,V5,V6,V7,V8,V9表示事件，弧a1,a2,a3,a4,a5,a6,a7,a8,a9,a10,a11,a12表示活动，请回答以下问题：(1)去掉边的方向后，画出最小生成树。（2分）(2)求出所有事件和活动的最早发生时间与最迟发生时间。（4分）(3)列出所有关键活动。（2分）3．设关键字输入序列为{22，31，15,13，41，70，56，27，54,18,11,49}（1）（2分）试构造平衡二叉树；（2）（４分）构造3阶B-树，
7、并分别写出删除31和56后的B-树。（3）（2分）HASH表表长为12，HASH函数为H（key）=key%11，试用二次探测再散列解决冲突的方法构造哈希表。4．（４分）试述顺序表和链表的定义，各有什么特点？当线性表很少进行插入和删除应采用何种表？为什么？当线性表经常进行插入和删除应采用何种表？为什么？四、算法设计（每题7分，共14分）1．试写出二叉树拷贝的递归算法，函数原型为copy(bitnode*t,bitnode*&s)。已知二叉树结点定义如下：typedefstructbitnode{intdata;bitnode*lt,*r
8、t;}bitnode;2．已知一带表头结点的单链表，结点类型为（data,next）。以head为头指针,每个结点的data域存放的是一个整数,且结点是按值非递增排列，请设计一个算法，插入结点x，插入后仍然
