A. 快速排序 B. 堆排序 C. 归并排序 D. 冒泡排序

(68) 在基于关键码比较的排序算法中，____ C _____算法在最坏情况下，关键码比较次数不高于O(nlog2n)。

A. 起泡排序

B. 直接插入排序 D. 快速排序

C. 二路归并排序

(69) 一组记录为{46，79，56，38，84，40}，则采用冒泡排序法按升序排列时第一趟排序结果是___ B _____ 。

A. 46,79,56,38,40,84 ,56,38,79,40,84 C. 38,40,46,56,84,79 ,46,79,56,40,84

(70) 每次从无序表中取出一个元素，把它插入到有序表中的适当位置，此种排序方法叫做___ A _____ 排序。

A. 插入 B. 堆 C.快速 D.归并

(71) 每次从无序表中挑选出一个最小或最大元素，把它交换到有序表的一端，此种排序方法叫做___ B _____排序。

A. 插入 B. 堆 C.快速 D.归并

(72) 设一组初始记录关键字序列(5，2，6，3，8)，以第一个记录关键字5为基准进行一趟快速排序的结果为____ C ____。

A. 2，3，5，8，6 C. 3，2，5，6，8

B. 3，2，5，8，6 D. 2，3，6，5，8

(73) 下列排序方法中，哪一种方法的比较次数与纪录的初始排列状态无关___ D _____。

A. 直接插入排序 B. 起泡排序 C. 快速排序 D. 直接选择排序

(74) 设有关键码初始序列{Q，H，C，Y，P，A,M,S,R,D,F,X}，新序列{F，H，C，D，P，A，M，Q，R，S，Y,X}是采用____ C ____ 方法对初始序列进行第一趟扫描的结果。

A. 直接插入排序 B．二路归并排序 C．以第一元素为分界元素的快速排序 D．基数排序

(75) 在待排序文件已基本有序的前提下，下述排序方法中效率最高的是__ C ____。

A. 直接插入排序 B. 直接选择排序 C． 快速排序 D． 归并排序

(76) 若需在O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选排序方法是___ C _____ 。

A. 快速排序 B． 堆排序 C． 归并排序 D． 直接插入排序

(77) 将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是___ B _______。

A． n B． 2n-1 C． 2n D． n-1

(78) 下列排序算法中，____ C ____ 算法可能会出现下面情况：初始数据有序时，花费的间反而最多。

A. 堆排序 B．冒泡排序 C．快速排序 D． SHELL排序

二、填空题。(每空1分，共10分)

(1) 数据结构是一门研究非数值计算的程序设计问题中计算机的 数据 以及它们之间的 关系

和运算等的学科。

(2) 数据结构包括数据的 逻辑结构 结构和 物理结构 结构。

(3) 数据结构从逻辑上划分为三种基本类型：____线性数据结构_______、____树型结构______和_____图结构______。

(4) 数据的物理结构被分为___顺序存储______、___链式存储_____、____索引存储______和______散列表（Hash）存储_____四种。

(5) 一种抽象数据类型包括_____变量的取值范围_____和 ____操作的类别_____两个部分。

(6) 数据的逻辑结构是指 数据元素间的逻辑关系 ，数据的存储结构是指 数据元素存储方式或者数据元素的物理关系 。

(7) 数据结构是指数据及其相互之间的____关系__________。当结点之间存在M对N（M：N）的联系时，称这种结构为________网状结构________。当结点之间存在1对N（1：N）的联系时，称这种结构为_____树结构__________。 (8) 对算法从时间和空间两方面进行度量，分别称为 空间复杂度和时间复杂度 分析。

(9) 算法的效率可分为______空间_________效率和______时间_________效率。

(10) for(i=1，t=1，s=0；i<=n；i++) {t=t*i；s=s+t；}的时间复杂度为___Ο(n)______。 (11) 线性表是n个元素的_________有限序列____________________。

(12) 线性表的存储结构有_________顺序存储和链式存储____________________。

(13) 设线性表中有n个数据元素，则在顺序存储结构上实现顺序查找的平均时间复杂度为_____Ｏ(n)______，在链式存储结构上实现顺序查找的平均时间复杂度为____ O(n)_______。

(14) 设顺序线性表中有n个数据元素，则第i个位置上插入一个数据元素需要移动表中___ n-i+1____个数据元素；删除第i个位置上的数据元素需要移动表中___ n-i ____个元素。

(15) 若频繁地对线性表进行插入与删除操作，该线性表应采用_____链式_________存储结构。 (16) 链式存储结构中的结点包含______数据__________域和_____指针__________域。

(17) 对于一个长度为n的单链存储的线性表，在表头插入元素的时间复杂度为___Ο(1)______，在表尾插入元素的时间复杂度为_____Ο(n)_______。

(18) 栈的插入和删除只能在栈的栈顶进行，后进栈的元素必定先出栈，所以又把栈称为____ FILO ________表；队列的插入和删除运算分别在队列的两端进行，先进队列的元素必定先出队列，所以又把队列称为 _____ FIFO ______表。

(19) s=” I am a man” 长度为____10_______ 。

(20) s1=”hello “,s2=”boy”,s1,s2连接后为：________ hello boy ______________ 。 (21) s=”this is the main string”,sub=”string”,strindex(s,sub)是：_______13_______。 (22) int a[10][10],已知a=1000,sizeof(int)=2,求a[3][3]地址：_______1066___________ 。 (23) 设有两个串p和q，求q在p中首次出现的位置的运算称为________模式匹配________。

(24) 在树型结构中，树根结点没有______前趋______结点，其余每个结点有且仅有______一______个前驱结点；树叶结点没有______后继______结点，其余每个结点的______后继______结点数不受限制。

(25) 在一棵二叉树中，度为0的结点的个数为n0 ，度为2的结点的个数为n2 ，则：n0 =______n2 +1______。 (26) 由分别带权为3,9,6,2,5的共五个叶子结点构成一棵哈夫曼树，则带权路径长度为______ 55______。

(27) 在图G的邻接表表示中，每个顶点邻接表中所含的结点数，对于无向图来说等于该 顶点的 ______度数______，对于有向图来说等于该顶点的______出度数______。

(28) 假定一个图具有n个顶点和e条边，则采用邻接矩阵表示的空间复杂性为______O(n2 ) ______， 采用邻接表表示的空间复杂性为______ O(n+e) ______。

(29) 对于长度为n的线性表，若进行顺序查找，则时间复杂度为______ O(n)____；若采用折半法查找，则时间复杂度为______ O(log2n)____。

(30) 假设在有序线性表A[1..20]上进行折半查找，则比较一次查找成功的结点数为____1_______，则比较二次查找成功的结点数为____2_______，则比较三次查找成功的结点数为____4_______，则比较四次查找成功的结点数为_____8______，则比较五次查找成功的结点数为____5_______，平均查找长度为_____ log2(n+1)-1______。 (31) 在一棵二叉排序树中，每个分支结点的左子树上所有结点的值一定_____小于______该结点的值，右子树上所有结点的值一定____大于_______该结点的值。

(32) 对一棵二叉排序树进行中序遍历时，得到的结点序列是一个_______增序序列_______________。

(33) 对于线性表（70，34，55，23，65，41，20）进行散列存储时，若选用H（K）=K %7作为散列函数，则散列地址为0的元素是_____70_________，散列地址为6的是____34,20,55_________。

(34) 在线性表的散列存储中，装填因子又称为装填系数，若用m表示散列表的长度，n表示待散列存储的元素的个数，则等于____ n/m _______。

(35) 散列表中解决冲突的两种方法是____开放地址法_________和____链地址法_________。

(36) 在散列存储中，装填因子a的值越大，则_______产生冲突的可能性就越大____________；a的值越小，则_____产生冲突的可能性就越小___________。

(37) 散列法存储的基本思想是由________关键码直接______________决定数据的存储地址。

(38) 构造哈希函数的方法有(写二个)______________直接定址法，数字分析法，平方取中法，折叠法，除留余数法，随机数法_________________________________________。

(39) 在分块查找中首先查找 _____索引________，然后再查找相应的______块_________。

(40) 散列表的查找效率主要取决于散列表造表时选择的_____哈希函数________ 和______装填因子_________。 (41) 对两棵具有相同关键字集合而形状不同的二叉排序树，____中序_______ 遍历它们得到的序列的顺序是一样的。

(42) 当待排序的记录数较大，排序码较随机且对稳定性不作要求时，宜采用______快速_________排序；当待排序的记录数较大，存储空间允许且要求排序是稳定时，宜采用______归并_________排序。

(43) 在堆排序的过程中，对任一分支结点进行筛运算的时间复杂度为___ O(log2n)_____，整个堆排序过程的时间复杂度为____ O(nlog2n)____。

(44) 当向一个大根堆插入一个具有最大值的元素时，需要逐层____向上_____调整，直到被调整到_____根结点_______位置为止。

(45) 对一组初始关键字序列（40，50，95，20，15，70，60，45，10）进行冒泡排序，则第一趟需要进行相邻记录的比较的次数为____8______，在整个排序过程中最多需要进行_____8_____趟排序才可以完成。

(46) 在在插入排序、选择排序、快速排序、堆排序、归并排序和基数排序中，平均比较次数最少的排序是___快速_______，需要内存容量最多的是____归并______。

(47) 堆排序是不稳定，空间复杂度为 ____ O(1)_____。在最坏情况下，其时间复杂度也为___ O(nlog2n)______。

(48) 若待排序的文件中存在多个关键字相同的记录，经过某种排序方法排序后，具有相同关键字的记录间的相对位置保持不变，则这种排序方法是____稳定_______的排序方法。

(49) 在对一组记录(50,40,95，20，15,70,60,45,80)进行直接插入排序时，当把第7个记录60插入到有序表时，为寻找插入位置需比较____3_____次。

(50) 二路归并排序的时间复杂度是___ O(nlog2n)______。

(51) 对于n个记录的集合进行归并排序，所需的附加空间消耗是___ O(n)______。

(52) 设表中元素的初始状态是按键值递增的，分别用堆排序、快速排序、冒泡排序和归并排序方法对其仍按递增顺序进行排序，则______冒泡排序_________最省时间，____快速排序________最费时间。

三、判断题。(每小题1分，共10分) ( × )1．数据元素是数据的最小单位。 ( × )2．数据项是数据的基本单位。 ( √ )3．顺序存储的线性表可以随机存取。

( √ )4．线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性， 因此，是属于同一数据对象。

( × )5．在单链表中，任何两个元素的存储位置之间都有固定的联系，因为可以从头结点查找任何一个元素。 ( × )6．在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。 ( × )7．链表的每个结点中，都恰好包含一个指针。 ( × )8．数组是同类型值的集合。

( √ )9．使用三元组表示稀疏矩阵的元素，有时并不能节省存储时间。

( √ )10. 线性表可以看成是广义表的特例，如果广义表中的每个元素都是原子，则广义表便成为线性表。 ( √ )11. 由树转换成二叉树，其根结点的右子树总是空的。 ( × )12. 后序遍历树和中序遍历与该树对应的二叉树，其结果不同。

( × )13. 若有一个结点是某二叉树子树的中序遍历序列中的最后一个结点，则它必是该子 树的前序遍历序列中的最后一个结点。

( √ )14.若一个树叶是某子树的中序遍历序列中的最后一个结点，则它必是该子树的前序 遍历序列中的最后一个结点。

( × )15. 已知二叉树的前序遍历和后序遍历序列并不能唯一地确定这棵树，因为不知道树 的根结点是哪一个。 ( × )16. 在哈夫曼编码中，当两个字符出现的频率相同时，其编码也相同，对于这种情况应作特殊处理。 ( √ )17. 有回路的图不能进行拓扑排序。

( × )18. 连通分量是无向图中的极小连通子图。

( √ )19. 散列法存储的基本思想是由关键码的值决定数据的存储地址。

( √ )20. 散列表的查找效率取决于散列表造表时选取的散列函数和处理冲突的方法。 ( √ )21. m阶B-树每一个结点的子树个数都小于或等于m。

( √ )22. 中序遍历二叉排序树的结点就可以得到排好序的结点序列。

( √ )23. 在二叉排序树上插入新的结点时，不必移动其它结点，仅需改动某个结点的指针， 由空变为非空即可。

( √ )24. 当待排序的元素很多时，为了交换元素的位置，移动元素要占用较多的时间，这是影响时间复杂性的主要因素。

( √ )25. 对于n个记录的集合进行快速排序，所需要的平均时间是O(nlog2 n)。 ( √ )26. 对于n个记录的集合进行归并排序，所需要的平均时间是O(nlog2 n)。 ( √ )27. 堆中所有非终端结点的值均小于或等于（大于或等于）左右子树的值。 ( × )28. 磁盘上的顺序文件中插入新的记录时，必须复制整个文件。 ( × )29. 在索引顺序文件中插入新的记录时，必须复制整个文件。 ( × )30. 索引顺序文件是一种特殊的顺序文件，因此通常存放在磁带上。

四、简答题。(共6小题，每小题约5分，共32分)

1. 简述下列术语：数据、数据项、数据元素、数据逻辑结构、数据存储结构、数据类型和算法。

数据：数据是信息的载体，是计算机程序加工和处理的对象，包括数值数据和非数值数据。 数据项：数据项指不可分割的、具有独立意义的最小数据单位，数据项有时也称为字段或域。

数据元素：数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理，一个数据元素可由若干个数据项组成。

数据逻辑结构：数据的逻辑结构就是指数据元素间的关系。

数据存储结构：数据的物理结构表示数据元素的存储方式或者数据元素的物理关系。 数据类型：是指变量的取值范围和所能够进行的操作的总和。 算法：是对特定问题求解步骤的一种描述，是指令的有限序列。

2. 简述栈和线性表的区别。

答：一般线性表使用数组来表示的。线性表一般有插入、删除、读取等对于任意元素的操作。

而栈只是一种特殊的线性表。栈只能在线性表的一端插入（称为入栈,push）或者读取栈顶元素或者称为“弹出、出栈”(pop)。

3. 简述栈和队列这两种数据结构的相同点和不同点。

答：相同点：栈和队列都是特殊的线性表，只在端点处进行插入，删除操作。

不同点：栈只在一端（栈顶）进行插入，删除操作；队列在一端（top）删除，一端(rear)插入。

4. 如果进栈的元素序列为A，B，C，D，则可能得到的出栈序列有多少种? 写出全部的可能序列。

答：可能序列有14种：ABCD; ACBD; ACDB; ABDC; ADCB; BACD; BADC; BCAD; BCDA; BDCA; CBAD; CBDA; CDBA; DCBA。

5. 如果进栈的元素序列为1，2，3，4，5，6，能否得到4，3，5，6，1，2和1，3，5，4，2，6的出栈序列?并说明为什么不能得到或如何得到。

答：不能得到4，3，5，6，1，2，最先出栈的是4,则按321的方式出，不可能得到1在2前的序列，可以得到1，3，5，4，2，6，按如下方式进行push(1), pop(), push(2), push(3), pop(), push(4), push(5), pop(), pop(), pop(), push(6), pop()。

6. 设s=“I AM A STUDENT”,t=“GOOD”，q=“WORKER”。

求：StrLength (s)， StrLength (t)，SubStr( s，8，7)，SubStr(t，2，1)，StrIndex(s,“A”)，StrIndex (s，t)，StrRep(s，“STUDENT”，q)，SubStr (SubStr (s，6，2)，StrConcat (t，SubStr(s，7，8)))。