多媒体网络《数据结构》期末考题(answer)

北京化工大学2009/学2年0第1一0学期《数据结构》期末试题班级： 姓名： 学号： 成绩：一、选择题（共40分）：1212345DAABC1112131415CBACD678910BABCB1617181920CCBDD、在长度为的顺序表的第（ww）个位置上插入一个元素，元素的移动次数为（）。、已知一个顺序存储的线性表，设每个结点占个存储单元，若第一个结点地址为，则第个结点的地址为（）。 1 —） k、将一棵有10个0结点的完全二叉树从上到下，从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的左孩子编号为（ ）。、设长度为的链队列用单循环链表表示，若只设尾指针，则出队操作的时间复杂度为（）。A．O（1）．O（lnoB）g．O（Cn）．O（2）nD2、一个栈的入栈序列是abc,,则栈的不可能的输出序列是（）。A．edcbaB．decba C．dceab ．Dabcde。、深度为的二叉树，结点数最多有（）个。A．2k-1．2k-B1．2Ck．kD、连通分量是（）的极大连通子图。A无向图B有向图.树.图、下述几种排序方法中，要求内存量最大的是（）。A插入排序.归并排序.选择排序 .冒泡排序

、若在单链表中所指结点不是最后结点，在之后插入所指结点，则执行C> = > ；=； .> =；-XP0、已知图的邻接矩阵，则从顶点0出发按深度优先遍历的结点序列是( )。1、若在线性表中采用折半查找法查找元素，该线性表应该( )。元素按值有序.采用顺序存储结构元素按值有序.采用顺序存储结构C．元素按值有序，且采用顺序存储结构D．元素按值有序，且采用链式存储结构2设语句十十的时间是单位时间，则语句：(=f<=n++) ++;的时间复杂度为()。．AO(l)．BO(n) ．CO(n2) ．DO(n3)、设表长=,函数 ，表中e有四个关键字，，5如)果=用1二0次探测法处理冲突，关键字为8的节点的地址是( )。、理冲突，关键字为8的节点的地址是( )。、4判定一个循环队列(空间个数为)为空的条件是一〉a5、假定在一棵二叉树中，双分支结点数为1，5单分支结点数为3，0则叶子结点数为()。

6、在数据结构中，从逻辑上可以把数据结构分成（ ）。动态结构和静态结构 .紧凑结构和非紧凑结构线性结构和非线性结构 .内部结构和外部结构7、有8个结点的无向连通图最少有（）条边。A．5 ． 6B ．7C． 8D8、有一个有序表｛，23，10，12，32，41，45，62，75，7，883，94，99，｝当采用折半查找法查找83时，经过（）次比较后查找成功。A．1 ．4B．2C．8D、判断线索二叉树中某结点有右孩子的条件是（）。20、栈与一般线性表的区别主要在（）方面。A元素个数 .元素类型 .逻辑结构 .插入、删除元素的位置二、填空：（每空1分，共20分）1．图有（ ）、（ ）等存储结构。2．在数据结构中我们所说的数据之间的关系即数据的（ ）结构和（ ）结构。3．数据对象是（ ）相同的数据的集合。4设某二叉树的先序序列为IJKLMNO,中序序列为JLKINMO,则该二叉树结点的后序序列为（ ）。5．我们学过限定性的线性表有（ ）和（ ），它们所采用的原则分别是（ ）和（ ）。6．当队列采用顺序存储结构时，经常发生假上溢现象，我们采取的解决办法是引入（ ）的概念，其入队和出队的关键表达式分别为（n（rear= ）（设循环队列的空间总数为M）。7二叉树中第层上最多有（ ）个结点（ ）；深度为的二叉树中最少有（ ）个结点（ =）条件时，此无向图称为完全图。8对于一个无向图，表示边的数目，表示顶点的数目，当和满足（）条件时，此无向图称为完全图。在各种查找方法中，平均查找长度与结点个数无关的查找方法是（ ）。0对个顶点的连通图来说，它的生成树一定有（ ）条边。1．1一个算法的效率可分为（ ）效率和空间效率。2带有头结点为 的单链表判空条件是假设结点的指针域为（ ）。三、操作题（34分）：（一）已知线性表序列为｛1，01，81，93，8，17，7，9｝，按要求完成以下操作：1．请生成一棵二叉平衡树，同时要求是二叉排序树。根结点为．写出希尔排序的过程。．写出快速排序的一趟排序结果（要求过程）。．建立一个初始堆（小根堆）。4418CD出下图的邻接矩阵、邻接表、逆邻接表;4A（三）利用迪杰斯特拉算法，求从图中出发到其余各顶点的最短路径长度。终点八、、从7到各终点的值一最短路径V3V1v315V1v315V4888V1v3V6V431V1v3v6v431V1v3v6v431V588V1v3V2V529V1v3v2v529V1v3v2v529V68V1v3v625V1v3V625V1v3v625VjV3V2V6V5V4S集合{v1,v3}{v1,v2,v3}{v1,v2,v3,v6}{v1,v2,v3,v5,v6}{v1,v2,v3,v4,v5,v6}四、写出操作的主要语句（6分）：1．对单链表进行操作：结点结构定义为：插入结点（在结点之前插入新元素，设搜索指针已指向