贵州大学2014-2015学年第一学期考试试卷(共9页)

1、精选优质文档-倾情为你奉上贵州大学2014-2015学年第一学期考试试卷 B数据结构与算法注意事项：1. 请考生按要求在试卷装订线内填写姓名. 学号和年级专业。2. 请仔细阅读各种题目的回答要求，在规定的位置填写答案。3. 不要在试卷上乱写乱画，不要在装订线内填写无关的内容。4. 满分100分，考试时间为120分钟。题 号一二三四总 分统分人得 分得 分评分人一. 选择题（共10分,每题1分）1. 在数据结构中，从逻辑上可以把数据结构分成( C )。A.动态结构和静态结构 B.紧凑结构和非紧凑结构C.线性结构和非线性结构 D.内部结构和外部结构2对顺序存储的线性表，设其长度为n，在任何位置上删

2、除操作都是等概率的，则删除一个元素大约要移动表中元素的个数是( D )。 An2 B(n+1)2 Cn-1D(n-1)23以下的叙述中，正确的是(B )。A.线性表的顺序存储结构优于链式存储结构 B.二维数组是其数据元素为线性表的线性表C.栈的操作方式是先进先出 D.队列的操作方式是先进后出4在表达式中进行括号匹配检验时，采用( B )数据结构最佳。A线性表的顺序存储结构 B栈C线性表的链式存储结构 D队列5循环队列的最大容量为MAXSIZE，队尾指针是rear，对头指针是front，则队空的条件是 ( B )。A. Q. front=maxsize B. Q. rear=Q. front C

3、. Q. rear=maxsize D. (Q. rear+1)%maxsize=Q. front6在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入s结点，则执行（ C ）。A. s->next = p->next; p->next=s;B. p->next = s->next; s->next = p;C. q->next = s; s->next = p; D. p->next = s; s->next = q;7AOE网是一种（ D ）A有向图 B无向图 C无向无环图D有向无环图 8一棵深度为k的平衡二叉

4、树，其每个非终端结点的平衡因子均为0，则该树共有（ B ）个结点。A.2k-1-1 B.2k-1 C.2k-1+1 D.2k-19先将整个待排序元素序列分割成若干个子序列（由相隔某个“增量”的元素组成的），分别进行直接插入排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序( A )。 A快速排序 B起泡排序 C直接选择排序 D希尔排序10采用折半查找方法进行查找，数据文件应为（ D ），且限于（ ）。 A随机表 顺序存储结构 B有序表 链式存储结构 C有序表 顺序存储结构 D随机表 链式存储结构 得 分评分人二. 填空题（共15分,每空1分）1. 栈和队列都是一

5、种 _特殊_ 的线性表，栈的插入和删除只能在_栈顶 进行。2. 对一棵二叉排序树进行中序遍历时，得到的结点序列是一个_有序序列_。对一棵由算术表达式组成的二叉语法树进行后序遍历得到的结点序列是该算术表达式 、后缀表达式_。3. 已知二叉树有45个叶子结点，则该二叉树的总结点数至少是 89 。4. n个结点无向完全图的的边数为 n（n-1）/2 ， n个结点的生成树的边数为 n-1 。5. 队列的插入操作是在队列的 队尾 进行，删除操作是在队列的_队头_进行。6. 若对一棵完全二叉树从1开始进行结点的编号，并按此编号把它顺序存储到一维数组A中，即编号为2的结点存储到A1中。其余类推，则A i 元

6、素的左孩子元素为2i+2_，右孩子元素为_2i+3_，双亲元素为_i+1_。7. 从顶点出发，对如下无向图进行遍历深度优先遍历(Depth-First Search)序列为 ALBECDWX ，广度优先遍历(Breadth-First Search)序列为 ALCBERWX 。8. 在有序表（12,24,36,48,60,72,84）中二分查找关键字24时所需进行的关键字比较次数为_2_。得 分评分人三. 应用题（共55分）1. 已知数据8个字母及在通信中出现频率如下表：（10分）ABCDEFGH0.070.080.290.110.230.030.050.14把这些字母和频率作为叶子结点及其权

7、值，完成如下工作：（1）画出对应的Huffman树；（2）计算带权路径长度WPL；（3）求A、B、C、D、E、F、G、H的Huffman编码。(1) 哈夫曼树如下，每画对一个叶子，给0.5分，结构1分，共5分（2）WPL=0.02*5+ 0.04*5+0.06*4+0.08*4+0.1*4+0.3*2+0.4*1=2.26（1分）（3）A: 1000 B:1001 C:11 D:001 E:01 F:0000 G:0001 H:101（每个0.5分，共4分）2. 设散列函数H(k)=k % 13，设关键字序列为22,12,24,6,45,7,8,13,21。（9分）(1) 请画出所构造的散列表

8、。(2) 在(1)的基础上，请画出用链地址法处理冲突的哈希表；(3) 利用性探测法处理冲突，在记录查找等概率情况下，分别计算查找成功和查找不成功的平均查找长度。（1）Hash表（2分）地址0123456789101112关键字132164572282412比较次数171221311（2）链地址法处理冲突的哈希表（3分）(3)地址0123456789101112关键字132164572282412查找成功次数次数171221311查找不成功次数32111110987654查找成功的平均查找长度：（2分） （5*1+2*2+1*3+1*7）/9=19/9查找不成功的平均查找长度：（2分） （3+2

9、+1+1+1+1+10+9+8+7+6+5+4）/13=58/133. 给定表（19,14,22,15,20,21,56,10）.（9分）(1)按元素在表中的次序，建立一棵二叉排序树(2)对(1)中所建立的二叉排序树进行中序遍历，写出遍历序列。(3)画出对(2)中的遍历序列进行折半查找过程的判定树。（1）、构造（3分） 19 14 22 10 15 20 56 21(2)、10 14 15 19 20 21 22 56（3分）（3）、折半查找过程的判定树（3分）4. 如图所示AOV有向网G：（10分）(1) 写出有向网G的邻接矩阵；(2) 采用迪杰斯特拉(Dijkstra)算法，求顶点从到其余

10、各顶点的最短路径。(1) 邻接矩阵：（4分）5. 如图所示的AOE网络G: （9分）(1). 写出所有拓扑排序序列；(2). 该工程的工期是多少？(3). 求解关键活动，并画出由所有关键活动构成的关键路径。(1)ACBDEF或ACBEDF (1分)(2) 工程的工期为43天（1分）(3) 每个事件的最早开始时间vei、最迟开始时间vli，以及每个活动最早开始时间ek、最迟开始时间lk如下表（5分）顶点ve(i)Vl(i)活动e(k)l(k)l(k)-e(k)100201717219191500031515415150429371019278538381919190643431115271262

11、9378538380 则关键活动为：15、4、19、5 （1分）关键活动图为：（1分）6. 关键字序列46,58,45,15,35,90,24,62：（8分）（1）写出按递增序列的直接插入排序法的算法过程；（2）按关键字序列顺序，建立一棵二叉排序树；(1) （写一行0.5分，共4分）46,58,45,15,35,90,24,6246,58,45,15,35,90,24,6245,46,58,15,35,90,24,6215,45,46,58, 35,90,24,6215,35,45,46,58, 90,24,6215,35,45,46,58, 90,24,6215, 24,35,45,46,5

12、8,90,6215,24,35,45,46,58 ,62,90（2）二叉排序树如下（写一个结点0.5分，共4分）得 分评分人四. 算法设计（共20分）1. 线性表的链式存储结构如下：（12分）typedef struct LNode ElemType data; Struct LNode *next; LNode, *LinkList;设计算法，在单链表中进行插入和删除操作。根据设计思想，采用C语言描述算法，关键之处给出注释。Status ListInsert_L(LinkList &L, int i, ElemType e) /在带头结点的单链表L中第i个位置之前插入元素eStatu

13、s ListDelete_L(LinkList &L, int i, ElemType &e)/在带头结点的单链表L中，删除第i个元素，并用e返回其值Status ListInsert_L(LinkList &L, int i, ElemType e) /在带头结点的单链表L中第i个位置之前插入元素ep=L;j=0;while(p&&j<i-1) /寻找第i-1个结点 p=p->next; +j;if(!p|j>i-1) return ERROR; /i小于1或者大于表长加1s=(LinkList)malloc(siazeof(LNod

14、e); /生成新结点s->data=e;s->next=p->next;p->next=s;return OK;.6分.Status ListDelete_L(LinkList &L, int i, ElemType &e)/在带头结点的单链表L中，删除第i个元素，并用e返回其值p=L;j=0;while(p->next&&j<i-1) /寻找第i个结点，并令p指向其前前驱 p=p->next; +j;if(!(p->next)&&j<i-1) return ERROR; /删除位置不合理q=p->next; p->next=q->next; /删除并释放结点e=q->data;free(q);return OK;.6分.2. 已知某二叉树如右图所示，其二叉链树的类型定义如下：（8分）typedef struct BiTNodeTElemtype data;struct BiTNode *lchild, *rchild; BiTNode, *BiTree;设计一个算法用来输出度为2的节点：Status DispLeaf2(Bitree T)