数据结构期末复习资料

1、南京理工大学泰州科技学院课程考试试卷（学生考试用）第2 页共2 页7.设单链表中结点的结构为（data,next ）。已知指针p所指结点不是尾结点，若在指针p所指结点之课程名称：数据Z构 A 学分： 4 教学大纲编号： 试卷编号： 考试方式：闭卷满分分值：100考试时间：120 分钟组卷日期：2011年12月10日 组卷教师（签字）：朱保平 审定人（签字）： 学生班级：10计算机、10计信管09专升本 学生学号： 学生姓名： 一、选择题（每题 240分）1 .树最适合用来表示（）。A.有序数据元素B.无序数据元素C.元素之间具有分支层次关系的数据D.元素之间无联系的数据2 . 一个堆是一棵（）

2、二叉树。A.普通B.排序C.满D.完全3 .已知关键字的序列30,18,40,35,38,依次构造二叉树，当插入38时引起二叉树的不平衡，则它的旋转类型为（）。A. LRB. RLC. RRD. LL4 .二叉树的先序和中序遍历序列分别是ABCDEFGHCBEDFAGH亥二叉树是由（）棵树的森林转换而来的。A. 2B. 3C. 4D. 55.以下是平衡二叉树的是（）。6.有一个有序表为8,15,20,22,32,41,45,62,75,77,82,85,97,当二分查找值为22的数据时要进行（）次比较。A. 2B.3C.4D. 5后插入结点s,则应执行下列哪一个操作？A）s->next=

3、p;p->next=s ;B）s->next=p->next; p->next=s ;C）s->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,

4、c,f,dD. a,e,d,f,c,b10 .在一棵二叉树中，度为 2的结点有30个，度为1的结点有50个，则二叉树总的结点数有（）。A. 109B. 110C.111D. 11211 .若用起泡排序对序列11,14,8,29,12,5,70,8,10,1,20从大到小排序，需要（）次比较。A. 45B.4 6C.55D. 6612 . 一棵具有2092个结点的完全二叉树，其度数为2的结点数为（）。A.1045B. 1046C.1047D. 104813 .已知一组数为 3,4,5, 6, 7,用这组数构成的哈夫曼树的带权路径长度（）。A. 57B.69C.71D. 7214 . 一棵20阶B

5、-树当插入一结点引起结点的分裂时，则右子树上有（）个结点。A. 7B. 8C.9D. 1015 .设哈希表长为13,哈希函数是 H（key尸key%11,表中已有数据的关键字为15,27,17,51 共四个，现要将关键字为37的结点加到表中，用二次探测再散列解决哈希表解决冲突，则放入的位置是（）。A. 3B. 4C. 5D.616 .线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（）存储方式最节省运算时间。A.单链表 B.仅有头指针的单循环链表C.双链表D.仅有尾指针的单循环链表课程名称：数据Z构A 学分： 试卷编号： 17.在有n个结点的二叉链表中，值为非空的链

6、域的个数为（）A. n-1B. 2n-1C. n+1D.2n+118.对图进行深度优先遍历时,通常采用（）来实现算法。A.栈B.队列C.树D.图19.以卜小是堆的序列是（）。A)100, 85, 98, 77, 80,60, 82, 40, 20,10, 66B)100, 98, 85, 82, 80,77, 66, 60, 40,20, 10C)10, 20, 40, 60, 66,'77, 80, 82, 85,98, 100D)100, 85, 40, 77, 80,60, 66, 98, 82,10, 2020.已知关键字的序列10,20,8,32,50,6,48,76,19,

7、25,将它们构造二叉排序树所得二叉树的树高为（）。A. 3B. 4C.5D. 6二、填空题（每空 2分，共20分）1 . 一个深度为k的，具有最少结点数的完全二叉树按层次，（同层次从左向右）用自然数依此对结点编号，则编号最小的叶子的序号是 ;编号是i的结点所在的层次号是 （根所在的层次号规定为1层）。2 .已知关键字的集合20,18,45,6,77,41,51,19,40,55,90,2,增量为3, 一趟希尔排序后的结果为3 .树根的层次是1,则深度为9的完全二叉树至少有 个结点，拥有2000个结点的二叉树的最 大层次数是。4 .已知有向图 G =（V,E）,其中 V =a,b,c,d , E

8、 =（ a,c）, （b,d）,（c,d）。写出一个拓扑序 列。5 .已知四棵树的森林，其第一棵，第二棵，第三棵，第四棵树的结点数分别为10, 9, 8, 7,由它们构造的二叉树，对应根的左子树上结点数为 ,右子树上的结点数为 。6 .假定对数据序列25,10,8,15,40,5,12,24,30,45,20 进行快速排序，第一趟快速排序后结果 为,第二趟快速排序后结果为 。三、问答题（共26分）1.假设一棵二叉树的中序序列为DBFEGAJHKCNOLIM后序序列为 DFGEBJKHNOLMICA（1）画出该树；（2分）（2）写出先序序列；（2分）（3）写出对应该二叉树的森林；（2分）2.根据

9、下图所示的 AOE 网，顶点 Vi,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） （4分）构造3阶B-树，并分别写出删除 31和56后的B-树。（3） （2分）HASH表表长为12,

10、HASH函数为H （key） =key%11 ,试用二次探测再散列解决冲突的 方法构造哈希表。4 . （4分）试述顺序表和链表的定义，各有什么特点？当线性表很少进行插入和删除应采用何种表？为 什么？当线性表经常进行插入和删除应采用何种表？为什么？四、算法设计（每题 7分，共14分）1 .试写出二叉树拷贝的递归算法，函数原型为copy（bitnode *t,bitnode*&s）。已知二叉树结点定义如下：typedef struct bitnodeint data;bitnode *lt,*rt;bitnode;2 .已知一带表头结点的单链表，结点类型为（ data,next ）。以he

11、ad为头指针，每个结点的data 域 存放的是一个整数，且结点是按值非递增排列，请设计一个算法，插入结点x,插入后仍然保持按值非递增排列。函数原型为int insertx（lnode *&head,int x）。南京理工大学泰州科技学院课程考试答案ABDEFGCHJKILNOM课程名称：数据Z构A 学分：4 教学大纲编号： 试卷编号： 考试方式：闭卷满分分值:100考试时间:120 分钟组卷日期： 2011 年12月20 日 组卷教师： 审定人（签字）： 学生班级:10计算机、10计信管09专升本 学生学号:学生姓名：、选择题（每是2分，共40分）1（3）（2 分）AC/|/BEG H

12、 K|DFJ2. （1） 2分I/L O|NI. C 2. DII. C12. A二、填空题（每空3. B4. B 5. B 6. C13. A 14. D 1 5, A 16.2分，共20分）7. B 8. B 9. A 10. CD 17. A 18. A 19. D 20. C1. 2“+1og2+12.6, 18, 2, 20, 19, 40, 51,77, 41, 55, 90, 453. 256 20004. abcd 或 acbd 或 bacd5. 9 246.20,10,8,15,24,5,12,25,30,45,40三、问答题（共26分）1.（2分）A/B/D E/F G12

13、,10,8,15,5,20,24,25,30,45,40C/H I/ J K L M/ N O（3） 2 分第1 页 共1 页课程名称：_ 学分： 试卷编号： _4. 4分(1)试述顺序表和链表的定义，各有什么特点？当线性表很少进行插入和删除应采用何种表？为什么？当线性表经常进行插入和删除应米用何种表？为什么？(1)顺序表是用一组地址连续的空间存放数据元素，逻辑相邻物理相邻；优点可以随机存取，缺点是 插入和删除元素是大量移动数据元素；链表是用一组地址任意的空间存放数据元素，逻辑相邻物理不一 定相邻；优点插入和删除元素时不需要移动数据元素；缺点是不能随机存取。(2)当线性表很少进行插入和删除应采

14、用顺序表，因为可发随机存取；当线性表经常进行插入和删除应采用链表，因为插入和删除元素时不需要移动数据元素，只需修 改指针值。四、算法设计1 . 7分void copy(bitnode *t,bitnode *&s) if(t=NULL)s=NULL;elses=new bitnode;s->data=t->data;copy(t->lt,s->lt);copy(t->rt,s->rt);2.7分int insertx(lnode *&head,int x)lnode *pr,*p=head->next;while(p&&p->data<x)pr=p;p=p->next;lnode s=ne