2009数据结构期末试卷1234B答案

你一定要坚强，即使受过伤，流过泪，也能咬牙走下去。因为，人生，就是你一个人的人生。==============================================================================命运如同手中的掌纹，无论多曲折，终掌握在自己手中==============================================================徐州工程学院数据结构期末试卷B答案2008—2009学年第二学期课程名称数据结构试卷类型期末考试形式闭卷考试时间100分钟命题人戴磊2009年4月14日使用班级07计本1-207计单教研室主任年月日教学院长年月日姓名班级学号.题号一二三四五六七八总分总分2015151040得分一、填空题（共8小题，每空1分，共计20分）1．数据的逻辑结构被分为集合、线性结构、树形结构和图状结构4种。2．链表最后一个结点的指针指向链表的头节点，这样的链表称为_循环_链表；链表的每个结点都有两个指针域，一个指针指向前一结点，另一个指针指向后一结点，这样的链表称为_双向_链表。3．某二叉树结点的中序遍历序列为A，B，C，D，E，F，G，后序遍历序列为B，D，C，A，F，G，E，则该二叉树结点的前序遍历序列为__E;A;C;B;D;G;F___，该二叉树对应的树林包括___2_____棵树。5．按照锦标赛排序的思想，决出8个选手的名次排列，共需要进行___11___场比赛（考虑最坏的情况）。6．Hanoi塔、求一个数的阶乘、二叉树遍历等类似问题的解决一般通过使用_递归_来解决。7．在进行直接插入排序时，其数据比较次数与数据的初始排列__有___关；而在进行直接选择排序时，其数据比较次数与数据的初始排列__无___关。8．设r指向单链表的最后一个结点，要在最后一个结点之后插入s所指的结点，需执行的三条语句是__R->next=s______；r=s;r->next=null;。9.在有序表（12，24，36，48，60，72，84）中折半查找关键字72时所需进行的关键字比较次数为__2___。

10.在线形表的散列存储中，处理冲突有开放定址法和链地址法两种方法。11.在一棵二叉树中，第五层的结点数最多为16个。12.用冒泡法对n个关键码排序，在最好情况下，只需做_____n-1________次比较和_______0_____次移动；在最坏的情况下要做______n(n-1)/2___________次比较。二、选择题（共15小题，每题1分，共计15分）1．在数据结构的讨论中把数据结构从逻辑上分为（C）A内部结构与外部结构B静态结构与动态结构C线性结构与非线性结构D紧凑结构与非紧凑结构2．算法分析的两个主要方面是（A）。A．空间复杂性和时间复杂性B．正确性和简明性C．可读性和文档性D．数据复杂性和程序复杂性3．一个非空广义表的表头（

D

）

A．不可能是子表

B．只能是子表

C．只能是原子

D．可以是子表或原子4．在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行(B)A．s->next=p；p->next=sB．s->next=p->next；p->next=sC．s->next=p->next；p=sD．p->next=s；s->next=p5．将一个递归算法改为对应的非递归算法时，通常需要使用（A）。A．栈 B．队列 C．循环队列 D．优先队列6．图的邻接矩阵表示法适用于表示（C）A．无向图B．有向图C．稠密图D．稀疏图7．深度为5的二叉树其结点数最多为C。A、16；B、30；C、31；D、32。8．设单循环链表中结点的结构为（data,next）,且rear是指向非空的带表头结点的单循环链表的尾结点的指针。若想删除链表第一个结点，则应执行下列哪一个操作（D）A．s=rear；rear=rear->next；deletes；B．rear=rear->next；deleterear；C．rear=rear->next->next；deleterear； D．s=rear->next->next；rear->next->next=s->next；deletes；9．线性表采用链式存储时，结点的存储地址（

B

）

A．必须是不连续的B．连续与否均可

C．必须是连续的D．和头结点的存储地址相连续10．根据集合{25，30，16，48}，按照依次插入结点的方法生成一棵二叉搜索树，在等概率情况下成功查找一个元素的平均查找长度为（A）A．2B．2.5C．3D．411.含n个顶点和e条边的无向图的邻接矩阵中,零元素的个数为(

D

)

A．e

B．2e

C．n2－e

D．n2－2e12.对线性表进行折半搜索时，要求线性表必须（C）A．以链接方式存储且结点按关键码有序排列 B．以数组方式存储 C．以数组方式存储且结点按关键码有序排列 D．以链接方式存储

A．选择排序

B．希尔排序

C．归并排序

D．快速排序13.从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为(D)排序法。A．二路归并B．选择C．shellD．插入14.若一个图的边集为{<1,2>,<1,4>,<2,5>,<3,1>,<3,5>,<4,3>},则从顶点1开始对该图进行深度优先搜索，得到的顶点序列可能为(C)。A、1，2，5，4，3；B、1，2，3，4，5；C、1，2，5，3，4；D、1，4，3，2，5。15.在以下的叙述中，正确的是(B)。A．线性表的线性存储结构优于链表存储结构B．二维数组是其数据元素为线性表的线性表C．栈的操作方式是先进先出D．队列的操作方式是先进后出三、判断题（对的打√，错的打×共15小题，每题1分，共计15分）1、单链表从任何一个结点出发，都能访问到所有结点。(×)2、将一棵树转换成二叉树后，根结点没有左子树。(×)3、哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。(√)4、在树结构里，有且仅有一个结点没有前驱；非根结点有且仅有一个双亲，且存在一条从根到该结点的路径（√）。5、线性的数据结构可以顺序存储，也可以链接存储。非线性的数据结构只能链接存储。（×）6、在AOE网中，关键路径是唯一的。(×)7、向二叉排序树插入一个新结点时，新结点一定成为二叉排序树的一个叶子结点。(√)8、对有向图G，如果从任一顶点出发进行一次深度优先或广度优先搜索就能访问每个顶点，则该图一定是完全图。（×）9、在一个有向图的拓朴序列中，若顶点a在顶点b之前，则图中必有一条弧<a,b>。（×）10、在散列法中，一个可用散列函数必须保证绝对不产生冲突。（╳）11、完全二叉树的某结点若无左孩子，则它必是叶结点。(√)12、所谓平衡二叉树是指左右子树的高度差的绝对值不大于1的二叉树。（）13、AOE网所表示的工程至少所需的时间等于从源点到汇点的最短路径的长度。(×)14、若一个栈的输入序列为123…n，其输出序列的第一个元素为n，则其输出序列的每个元素ai一定满足ai=n-i+1。(i=1,2,...,n)。(√)15、在采用线性探测法处理冲突的散列表中，所有的同义词在表中相邻。（×）。四、算法填空题：将折半查找的非递归算法中的空白处进行正确填写。（每空2分，共计10分）intSearch_Bin(SSTableST,KeyTypekey){intlow=_______；high=ST.length；（1）While(low<=high){(2)mid=_________________；(3)if(EQ(key,ST.elem[mid].key)return__________；elseif(LT(key,ST.elem[mid].key))__________________；(4)else__________________；(5)}return0；}//Search_Bin五、综合应用题（每题10分，共计40分）１．下图为某无向图的邻接表，分别写出从A出发深度优先搜索和广度优先搜索的结果，并画出该无向图的逻辑结构图。12123456789105^B37^C267^D^E1^F3^G23^H910^I8^J8^深度优先搜索（DFS）结果为：AEBCFGDHIJ广度优先搜索（BFS）结果为：AEBCGFDHIJ这是有着4个连通分量的非连通图。AEBCFGHIDJ２．已知哈希表地址空间为0..14，哈希函数为H(k)=kmod13，采用线性探测法处理冲突。将下面各数依次存入该散列表中，并求出在等概率下的平均查找长度和失败的查找长度。240,29,345,189,100,20,21,35,3,208,78,99,45,35001234567891011121314208783502932403451891002021359945240mod13=629mod13=3345mod13=6(冲突，地址7)189mod13=7(冲突，地址8)100mod13=9 20mod13=7(冲突，地址10)21mod13=8(冲突，地址11)35mod13=123mod13=3(冲突，地址4)208mod13=078mod13=0(冲突，地址1)99mod13=8(冲突，地址13)45mod13=6(冲突，地址14)350mod13=12(冲突，地址2)查找成功的ASL=1/14*(1*5+2*4+4*2+6*2+9)=3查找失败的ASL=1/14*(6+5+4+3+2+1+15+14+13+12+11+10+9)=7.5３．在一个空AVL树内，依次插入关键字(46,15,20,35,28,58,18,50,54)，分别画出46，15，20，35插入完和所有关键字都插入完的AVL树。，并求出查找成功状态下的平均查找长度（10分）(1×1+2×2+4×3+2×4)/9=25/94.判断以下序列是否