二、填空题。（每空1分，共10分）(1)数据结构是一门研究非数值计算的程序设计问题中计算机的数据以及它们之间的关系和运算等的学科.（2)数据结构包括数据的________逻辑结构结构和物理结构________结构。(３)数据结构从逻辑上划分为三种基本类型:____线性数据结构＿______、＿＿__树型结构＿___＿＿和＿____图结构__＿＿__。（4）数据的物理结构被分为＿_＿顺序存储[1]__＿___、___链式存储[2]___＿_、____索引存储[3]__＿＿＿_和＿＿____散列表（Hash）存储__＿＿＿四种。（5）一种抽象数据类型[4]包括____＿变量的取值范围_＿＿__和____操作的类别_＿___两个部分。(6)数据的逻辑结构是指数据元素间的逻辑关系，数据的存储结构是指数据元素存储方式或者数据元素的物理关系。（７）数据结构是指数据及其相互之间的＿___关系_＿＿＿__＿＿__.当结点[5]之间存在M对N（Ｍ：N）的联系时,称这种结构为＿＿___＿__网状结构＿_______。当结点之间存在１对Ｎ（1：N）的联系时，称这种结构为_＿___树结构__________。(8）对算法从时间和空间两方面进行度量，分别称为空间复杂度和时间复杂度分析。（9）算法的效率可分为_____＿空间__＿_＿＿___效率和＿_____时间＿________效率.（10） for（ｉ=1，t＝1,s=0；i(１1）线性表[6]是n个元素的__＿___＿__有限序列_＿___＿＿_＿__＿_______＿。(12)线性表的存储结构有＿___＿____顺序存储和链式存储_＿__＿___＿_＿__＿____＿_。（１3）设线性表中有n个数据元素，则在顺序存储结构上实现顺序查找的平均时间复杂度为__＿_＿Ｏ（n）______,在链式存储结构上实现顺序查找的平均时间复杂度为＿__＿Ｏ（n）_______.（14)设顺序线性表中有ｎ个数据元素，则第i个位置上插入一个数据元素需要移动表中＿__n-ｉ+1_＿＿_个数据元素；删除第i个位置上的数据元素需要移动表中＿_＿n—i____个元素.（15)若频繁地对线性表进行插入与删除操作，该线性表应采用____＿链式_＿_______存储结构.(1６）链式存储结构中的结点包含_＿___＿数据＿＿________域和_____指针____＿＿_＿_＿域。（17)对于一个长度为n的单链存储的线性表，在表头插入元素的时间复杂度为___Ο(1)_＿_＿__，在表尾插入元素的时间复杂度为_____Ο（ｎ）_＿_＿_＿＿。（１8）栈的插入和删除只能在栈的栈顶[7]进行,后进栈的元素必定先出栈，所以又把栈称为__＿_FILO__＿＿_＿__表；队列的插入和删除运算分别在队列的两端进行,先进队列的元素必定先出队列,所以又把队列称为 ___＿_FＩFO_＿____表。(１9）ｓ=” I am a ｍａn” 长度为_＿＿_10___＿___ 。（２0)s1=”hｅllo “,s２＝"bｏy”，s1,s2连接后为:________hｅllo boy_＿＿____＿___＿__ 。（21)s=”ｔhiｓ is tｈe main ｓｔring”,suｂ=”string”，sｔriｎdex（s,suｂ)是:__＿___＿13＿＿__＿__。(22）inｔ a［10］[10],已知a=1000,sizeof(int）=2，求a［３］[３]地址:__＿____1066__＿＿______＿ .（23）设有两个串ｐ和q，求q在p中首次出现的位置的运算称为___＿____模式匹配[8]_＿_＿_＿＿_.（24）在树型结构中,树根结点没有_＿___＿前趋____＿_结点，其余每个结点有且仅有＿____＿一＿＿____个前驱结点;树叶结点没有______后继____＿_结点，其余每个结点的___＿_＿后继_____＿结点数不受限制。(25)在一棵二叉树[9]中，度为0的结点的个数为ｎ0，度为２的结点的个数为n2,则：n0 =＿＿____n2 +1______.（26）由分别带权为3,9，6，2，5的共五个叶子结点构成一棵哈夫曼树[10],则带权路径长度为＿_＿_＿_55__＿__＿。（27）在图G的邻接表[11]表示中，每个顶点邻接表中所含的结点数，对于无向图[12]来说等于该顶点的______度数______,对于有向图[13]来说等于该顶点的__＿＿＿_出度[14]数_＿＿__＿。（28）假定一个图具有n个顶点和ｅ条边，则采用邻接矩阵[15]表示的空间复杂性为______Ｏ(ｎ2 )_____＿,采用邻接表表示的空间复杂性为____＿_O（n+ｅ)____＿_。（29）对于长度为ｎ的线性表,若进行顺序查找，则时间复杂度为＿_＿__＿O（n)__＿_;若采用折半法查找，则时间复杂度为_____＿Ｏ(log２n)____。（30）假设在有序线性表A[1..２0]上进行折半查找，则比较一次查找成功的结点数为____１_＿_____,则比较二次查找成功的结点数为_＿__2__＿____，则比较三次查找成功的结点数为__＿_４＿＿__＿_＿，则比较四次查找成功的结点数为_____８__＿__＿,则比较五次查找成功的结点数为___＿5_＿_＿___,平均查找长度[16]为___＿＿loｇ2（n+1)-１__＿_＿＿.（31）在一棵二叉排序树中,每个分支结点[17]的左子树上所有结点的值一定＿____小于＿__＿__该结点的值，右子树上所有结点的值一定＿＿_＿大于_＿____＿该结点的值.(32）对一棵二叉排序树进行中序遍历[18]时，得到的结点序列是一个___＿___增序序列_＿______＿_＿____。(33)对于线性表(7０,3４，５５，23,65，41,２0)进行散列存储时，若选用H(Ｋ）＝K %7作为散列函数，则散列地址[19]为0的元素是＿____70＿___＿____，散列地址为６的是____34,20，55___＿＿＿___。(34)在线性表的散列存储中，装填因子ａ又称为装填系数，若用ｍ表示散列表的长度，n表示待散列存储的元素的个数，则ａ等于＿___ｎ/m＿______。(3５)散列表中解决冲突的两种方法是____开放地址法_＿＿______和＿__＿链地址法＿__＿＿____。(3６)在散列存储中，装填因子a的值越大，则_＿_____产生冲突的可能性就越大__＿____＿＿___；a的值越小，则_____产生冲突的可能性就越小_________＿_.（37）散列法存储的基本思想是由________关键码直接_＿__＿＿_＿______决定数据的存储地址.（３８)构造哈希函数[20]的方法有(写二个)_＿___＿__＿__＿＿_直接定址法，数字分析法，平方取中法,折叠法,除留余数法，随机数法_＿＿_____＿___＿_____＿________＿_______＿_____。（39）在分块查找中首先查找 _____索引__＿__＿__，然后再查找相应的__＿__＿块＿__＿_＿___。（40)散列表的查找效率主要取决于散列表造表时选择的_____哈希函数＿__＿____ 和_＿____装填因子_＿＿_＿＿＿_＿。（41）对两棵具有相同关键字集合而形状不同的二叉排序树，__＿＿中序＿_＿＿_＿＿ 遍历它们得到的序列的顺序是一样的。（42）当待排序的记录数较大,排序码较随机且对稳定性不作要求时,宜采用__＿___快速＿___＿____排序；当待排序的记录数较大,存储空间允许且要求排序是稳定时，宜采用______归并__＿______排序。（43)在堆排序[21]的过程中，对任一分支结点进行筛运算的时间复杂度为___O（ｌoｇ2n）＿＿_＿_,整个堆排序过程的时间复杂度为___＿O（nlｏg2n）__＿_。（４４)当向一个大根堆插入一个具有最大值的元素时,需要逐层____向上_＿___调整，直到被调整到____＿根结点______＿位置为止。（４5）对一组初始关键字序列（４0，50，９5，20，15，7０,60，45，10）进行冒泡排序[22],则第一趟需要进行相邻记录的比较的次数为＿＿__8_＿____,在整个排序过程中最多需要进行__＿__8____＿趟排序才可以完成。（46)在在插入排序[23]、选择排序[24]、快速排序[25]、堆排序、归并排序和基数排序中,平均比较次数最少的排序是___快速__＿＿＿_＿，需要内存容量最多的是__＿＿归并______.(４7)堆排序是不稳定，空间复杂度为____O(1）＿＿___。在最坏情况下，其时间复杂度也为___O（ｎlog２ｎ)______。（48）若待排序的文件中存在多个关键字相同的记录，经过某种排序方法排序后，具有相同关键字的记录间的相对位置保持不变，则这种排序方法是＿＿_＿稳定_____＿_的排序方法。(49）在对一组记录(５0，40，9５，20,１5,70，６0，45，80）进行直接插入排序时，当把第7个记录60插入到有序表[26]时，为寻找插入位置需比较＿＿＿_３_＿＿__次。(50）二路归并[27]排序的时间复杂度是___O(ｎlog2n）_＿____。(51）对于n个记录的集合进行归并排序，所需的附加空间消耗是＿＿_Ｏ(n）＿_____.（５2）设表中元素的初始状态[28]是按键值递增的,分别用堆排序、快速排序、冒泡排序和归并排序方法对其仍按递增顺序进行排序,则_＿____冒泡排序_________最省时间，____快速排序_______＿最费时间。