数据结构期末考试题.doc

《数据结构期末考试题.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、课程教研室软件使用专业计算机科学与技术（工、师）、软件工程年级07级班级学号考生姓名考试地点————————¤—————¤———————————装订线————————¤———————¤——————北华大学计算机科学技术学院2008-2009学年第一学期《数据结构》课程期末考试试卷（1）题号一二三四五六七八总分得分评卷人核分：大题得分一、填空题（每题2分，共14分）1.下面程序段的时间复杂度是________。for(i=1;i

2、看成是一个首尾相连的环，这样做的目的是为避免产生_____________现象。判断一个循环队列队满的条件是__________________（设Q.front代表队头静态指针，Q.rear代表队尾静态指针，Maxsize代表该循环队列的空间大小）。3.在一个长度为n的顺序表中的第i个元素(1≤i≤n)之前插入一个元素时，需向后移动_________个元素。4．如果某二叉树的先序遍历序列为abcde，中序为badec，那么该二叉树的后序为________。5.一棵二叉树的第i(i≥1)层最多有_______________

3、__个结点；一棵深度为k的满二叉树共有_______________个非终端结点。6.已知一个有向图的邻接矩阵表示，计算第i个结点出度的方法是__________________。删除所有以第i个结点为弧头的弧的方法是__________________________。7.在各种查找方法中，平均查找长度与结点个数n无关的查法方法是______________。二、选择题（每小题2分，共16分）1.数据结构是一门研究非数值计算的程序设计问题中计算机的___①_____以及它们之间的___②_____和操作等的学科。①A．操作

4、对象B．计算方法C.逻辑存储D．数据映像②A.结构B．关系C.运算D．算法2.一个栈的入栈序列是a，b，c，d，e，则栈的不可能的输出序列是________。A．abcdeB．edcbaC．edabcD．cbade2.大题得分课程教研室使用专业年级班级学号考生姓名考试地点————————¤—————¤—————————装订线————————¤———————¤—————————3.带头结点的单链表L为不空的判定条件是________。A.L－>next=nullB.L=nullC.L!=nullD.L－>next!=null4

5、.判断下列叙述中哪个不正确A.将一棵树转换成二叉树后，根结点没有左子树；B.用二叉树的先序遍历和中序遍历可以导出后序遍历；C.一棵深度为K且有2K-1个结点的二叉树称为满二叉树D.哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近.5．按二叉树的定义，具有3个结点的二叉树有_____种形态A.3B.4C.5D.66．在一个具有n个顶点的无向图中，要连通全部顶点至少需要________条边。A．nB．n+lC．n-1D．n／27．已知图G如下，求出该图的拓扑排序序列_________________。A．CABDEF

6、GHB．ABCDEFGHC．ACBDEFGHD．ACBDFEHG8．在待排序的元素序列基本有序的前提下，效率最高的排序方法是________。A．插入排序B．选择排序C．快速排序D．归并排序三、分析解答（1至4小题每题6分，5至6小题每题8分，共40分）1．二维数组A的每个元素是由4个字符组成的串，行下标的范围从0~9，列下标的范围是从0~9，则存放A至少需要多少个字节，A的第3列和第7行共占多少个字节，若A按行优先方式存储，元素A[6][3]的起始地址与当A按列优先方式存储时的哪个元素的起始地址一致。三、XXXXXXXXX

7、XX（每小题分，共分）1.2.四、XXXXXXXXXXXX（x–x小题每题分，xx小题5分，共40分）1.2.大题得分1题得分课程教研室使用专业年级班级学号考生姓名考试地点————————¤—————¤—————————装订线————————¤———————¤————————2.已知一棵树如下图，请将此树转化为对应的二叉树，画出转化后的二叉树及二叉链表。3.已知某系统在通信联络中出现的abcdef六种字符，其频率为（13，12，35，15，9，16），试构造一棵Huffman树，并写出每种字符的Huffman编码。4．已知关

8、键字序列{503，17，512，908，897，275，170，653，426}，请给出采用希尔排序法（d1=4,d2=2,d3=1）对该序列作升序排列时的每一趟的结果。5.已知AOE网如下，按关键路径算法:（1）找出其关键路径。（2）计算：Ve(v5)、Vl(v3)（3）设