数据结构期末考试题

1、命题人：葛建梅 教研室主任（签字）：系主任签字：日期：2008年12月5日课程教研室软件使用专业计算机科学与技术（工、师）、软件工程年级07级班级学号考生姓名考试地点aa装订线aa北华大学计算机科学技术学院2008-2009学年第一学期数据结构课程期末考试试卷（1 ）题号一二三四五六七八总分得分评卷人核分：大题得分一、填空题（每题2分，共14分） 1 1下面程序段的时间复杂度是 。for （i=1; ivn; i+ ）for （j=1; jvn; j+）Bij=35;2. 顺序队列在实现时，通常将数组看成是一个首尾相连的环，这样做的目的是为避免产生 象。判断一个循环队列队满的条件是 （设Qfr

2、ont代表队头静态指针，Q.rear代表队尾静态指针，Maxsize代表该循环队列的空间大小）。3. 在一个长度为n的顺序表中的第i个元素（1< i< n）之前插入一个元素时，需向后移动元素。4. 如果某二叉树的先序遍历序列为 abcde,中序为badec,那么该二叉树的后序为。5. 一棵二叉树的第i （i> 1）层最多有 结点；一棵深度为k的满二叉树共有非终端结点。6. 已知一个有向图的邻接矩阵表示，计算第 i个结点出度的方法是 。删除所有以第i个结点为弧头的弧的方法是 。7. 在各种查找方法中，平均查找长度与结点个数n无关的查法方法是。大题得分:二、选择题（每小题2分，共

3、16 分）1.数据结构是一门研究非数值计算的程序设计问题中计算机的以及它们之间的第2页共5页口操作等的学科。A.操作对象 B.计算方法C.逻辑存储D .数据映像A.结构B.关系C.运算D .算法2.一个栈的入栈序列是a, b, c,d,e,则栈的不可能的输出序列是A. abcdeB. edcbaC. edabcD. cbade课程教研室使用专业年级班级学号考生姓名考试地点aa装订线aa3. 带头结点的单链表L为不空的判定条件是 。A. L >next =nullB L = nullC L! = nullD L >next != null4. 判断下列叙述中哪个不正确A. 将一棵树转

4、换成二叉树后，根结点没有左子树；B. 用二叉树的先序遍历和中序遍历可以导出后序遍历；C. 一棵深度为K且有2k-1个结点的二叉树称为满二叉树D. 哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近5. 按二叉树的定义，具有 3个结点的二叉树有 种形态A. 3 B. 4C. 5D. 66.在一个具有n个顶点的无向图中，要连通全部顶点至少需要条边。D. n/2C. n-1A. nB. n+l7.C. ACBDEFGHACBDFEHGD.8.在待排序的兀素序列基本有序的前提下，效率最咼的排序方法是A.插入排序B.选择排序C. 快速排序D. 归并排序大题得分三、分析解答（1至4小题每题6分，

5、5至6小题每题8分，共40分）地址一致。二维数组A的每个元素是由4个字符组成的串，行下标的范围从 09,列下标的范围是从09,则存放A至少需要多少个字节，A的第3列和第7行共占多少个字节，若 A按1题得分行优先方式存储，元素A63的起始地址与当A按列优先方式存储时的哪个元素的起始命题人：葛建梅 教研室主任(签字)：系主任签字：日期：2008年12月5日课程教研室使用专业年级班级学号考生姓名考试地点aa装订线aa2题得分1 2已知一棵树如下图，请将此树转化为对应的二叉树，画出转化后的二叉树及二叉链表第4页共5页5.5题得分(3)设V5,V7弧称为活动a,计算：e (a)和 L(a)6题得分-6.

6、依据下列关键字序列25, 15, 一！:(1)请画出此二叉排序树。21, 23, 40, 48, 32, 22构成一棵二叉排序树厂3.已知某系统在通信联络中出现的 abcdef六种字符，其频率为(13, 12, 35, 15, 9, 16),3题得分，Ij试构造一棵Huffman树，并写出每种字符的 Huffman编码。 4.已知关键字序列503, 17, 512, 908, 897, 275, 170, 653, 426 ，请给出采用希尔排-4题得分 :lIMKin IMIII 序法(d1=4,d2=2,d3=1)对该序列作升序排列时的每一趟的结果。已知AOE网如下，按关键路径算法：(1)找

7、出其关键路径。(2) 计算：Ve (v5)、VI (v3)(2)若在二叉排序树中查找，则查找成功与查找不成功的平均查找长度分别是多少?命题人：葛建梅 教研室主任（签字）：系主任签字：日期：2008年12月5日课程教研室使用专业年级班级学号考生姓名考试地点aa装订线aa；大题得分 四、算法设计（每小题10分，共30分） rwiiisi mrrrnLJ i.某大学图书馆中有一批图书，按其价格从低到高的次序构成了一个单链表存于计算机中，! I:1题得分得链表的每个结点指出同样价格书的数量，现在要清理书库，将价格为C元的图书清出库,IJ：即从单链表中删除价格为 C元的结点。单链表存储结构与按此存储结构

8、的算法如下，请在空格上填写适当的语句，完成该算法。typedef struct LNode floatcost;intnum;Struct LNode *next; LNode, *LinkList;void Delbooks ( LinkList &L, float c) q=L; p=q->next;while (&& p !=null ) q=p; p=p->next; if ( p!=null ) ; 2题得分 4 11： -S IU2.设二叉树采用二叉链表存储结构，PrintElement是对数据元素打印输出的应用函数。下面算法是用类C语言描述的，

9、实现了按中序遍历二叉树T的递归算法，对每个数据元素调用函数PrintElement输出该结点的值。请在空格上填写适当的语句，完成该算法typedef struct BiTNode char data;struct BitNode *Lchild, * Rchild; BitNode, *BiTree;课程教研室使用专业年级班级学号考生姓名考试地点aa装订线aaStatus InOrderTraverse ( BiTree T) if () if ( InOrderTraverse ( T->Lchild )if ( )if ( ) return OK;return ERROR ;else

10、 return Ok;Status PrintElement ( char e ) ;return Ok ;3.假设图采用邻接表存储表示，设计一个广度优先遍历算法。图与队列的存储结构如下, 请依据此存储结构用类C语言编写算法。void BFSTraverse(ALGraph G, Status(*Visit)(int v) #define MAX_VERTEX_NUM 20 typedef struct ArcNode int adjvex;struct ArcNode *nextarc;ArcNode;typedef struct VNode Vertextype data;ArcNode *firstarc;VNode, Ad