数据结构期末复习题带答案.doc

一、选择题（每题2分，共20分） 1、二分查找，要求被查找的表是（ A ） A 顺序表 B 分块有序表 C 链表 D 无限制 2、一完二叉树有30个接点，则该树有（C ） 层。(根为0层) log2n+1 A 3 B 4 C 5 D 6 3、下列排序算法中，第一趟排序后，其最大的或最小的数一定在最终的位置上的是（ D） A 归并排序 B 直接插入排序 C 快速排序 D 冒泡排序 4、设八栈序列为A,B,C,D,则栈可能产生的出栈序列是（ A） A、 A C D B B、 C A D B C、 D C A B D、 D A B C 5、如有一颗二叉树按先序遍历所得结果为（? ） A A、C G B E F D A B D B、A B C G D E F C E F C、C G B A E D F G D、G C B E F D A 6、下面哪个结构属于线形结构 （C ） A 二叉排序树 B 线索树 C 队列 D 图 7、栈和队列都是 （ ）都是运算受限的线性表 A 没有限制的线形表 B 没有限制的非线形表 CD 8、在线性表操作中，常对某元素插入或删除。则采用什么存贮结构最节省运算时间（A ） 线性表 （顺序表 链表（单双 循环链表）） A、单链表 B、散列表 C、二叉链表 D、顺序表 9、设H为带头结点单向循环链表的头指针，P为移动指针，指针域为link，则表尾的判断条件是（D ） A、H-link = H B、P = H C、P-link = nil D、P-link = H 10、先序遍历能得到A，B，C序列的不同二叉树，最多有几种（ ） A、4 B、5 C、6 D、7 二、填空题（每题2分，共20分） 1、在单链表中，欲删除某一指定结点时，必须找到该结点的前驱结点结点。 2、 和 是操作点受限的线性表。 栈和队列 3、二分查找的条件是 。 有序顺序存储结构 4、深度为K的二叉树中结点总数最多为 。 2^k-1 5、在有n（n0）个结点的二叉链表中，空链域的个数为 个。 n+1 6、在对有15个数据的有序表中作二分查找时，有 2个结点查找长度为3。 7、在单链表中，若要在指针P所指结点后插入指针S所指结点，则需执行下列语句： 。 s=p-next;p-next=s; 8、举出插入排序的两种排序法： 。 9、快速排序的时间复杂度是 。| 109．对一组数据（84，47，25，15，21）排序，数据的排列次序在排序的过程中的变化为 （1） 84 47 25 15 21?（2） 15 47 25 84 21?（3） 15 21 25 84 47?（4） 15 21 25 47 84 则采用的排序是 _______。?? A. 选择???? B. 冒泡???? C. 快速?????D. 插入 110．具有12个关键字的有序表，折半查找的平均查找长度_______。 ?A. 3.1???? B. 4???? C. 2.5?????? D. 5 111．折半查找的时间复杂性为_______。 A. O（n2）??B. O（n）??C. O（nlogn）? D.?O（logn） ? 112．关于杂凑查找说法不正确的有几个_______。?????????????????? （1）采用链地址法解决冲突时，查找一个元素的时间是相同的 （2）采用链地址法解决冲突时，若插入规定总是在链首，则插入任一个元素的时间是相同的 （3）用链地址法解决冲突易引起聚集现象 （4）再哈希法不易产生聚集 A. 1????? B. 2?????? C. 3?????? D. 4 113．假定有k个关键字互为同义词，若用线性探测法把这k个关键字存入散列表中，至少要进行_______次探测？??? A．k-1次???? B. k次????? C. k+1次?????D. k（k+1）/2次 114．散列表的地址区间为0-17,散列函数为H(K)=K mod 17。采用线性探测法处理冲突，并将关键字序列26，25，72，38，8，18，59依次存储到散列表中。元素59存放在散列表中的地址是_______。 A．?8???????? B.?? 9??????? C.?10?????? D.?11 ? 115 (1). 求从指定源点到其余各顶点的迪杰斯特拉（Dijkstra）最短路径算法中弧上权不能为负的原因是在实际应用中无意义； (2). 利用Dijkstra求每一对不同顶点之间的最短路径的算法时间是O(n3 ) ；（图用邻接矩阵表示） (3). Floyd求每对不同顶点对的算法中允许弧上的权为负，但不能有权和为负的回路。 上面不正确的是_______。 A．(1),(2),(3)???????? B．(1)????????? C．(1),(3)??????