注意：所有答案必须写在答题本上，不得写在试题纸上，否则无效。一名词解释（共20分，每题4分）1算法及算法的特性2树的度及深度3完全二叉树4索引文件5强连通性二选择题（共30分，每题2分）1设核S和队列Q的初始状态均为空，元素ABCDEFG 依次进技S。若每个元素出校后立即进入队列Q，且7个元素的出队顺序是BDCFEAG，则核S的容量至少是：A.1B.2C.3D. 42已知一棵完全二叉树的第六层（根为第一层〉有8个叶子结点，则完全二叉树的结点个数最多是：A.39B.52C.111D.1193下列叙述中不符合m阶B树定义要求的是：A. 根结点最多有 m棵子树B. 所有叶结点在同一层上C. 各结点内关键字均升序或降序排列D. 叶结点之间通过指针链接4若无向图中含有7个顶点，贝。保证图在任何情况下都是连通的，需要的边数最少是：A.6B.15C.16D.215对一组数据（7,17,21,93,10,16）进行排序，若前三趟排序结果如下，则采用的排序方法是：第一趟：7,17,21,10,16,93第二趟：7,17,10,16,21,93第二趟：7,10,16,17,21,93A.冒泡排序B.希尔排序C.归并排序D.基数排序6已知一才果有2011个结点的树，其叶结点个数为116，该树对应的二叉树 中无右孩子的结点个数是：A.115B.116C.1895D.18967已知字符串S为“abaabaabacacaabaabcc".模式串t为“abaabc”，采 用KMP算法进行匹配，第一次出现“失自己”（s[i]!=t[i］）时，i=j习，则下次 开始匹配时，i和j的值分别是：A.i=l;j=O;B.i二5;j=O;C.i=5;j=2;D.i=6;j=2;8用哈希（散列〉方法处理冲突（碰撞〉时可能出现堆积（聚集）现象，下列选项 中，会受堆积现象直接影响的是 ：A.存储效率B.数列函数C.装填（装载〉因子D.平均查找长度9循环队列放在一维数组A[O···M-1］中，endl指向队头元素，end2指向 队尾元素的后一个位置。假设队列两端均可进行入队和出队操作，队列中最多 能容纳M-1个元素。初始时为空。下列判断队空和队满的条件中，正确的是：A .队空 ：endl== end2;队满：endl ==(end2+1) modMB.队空：endl==end2;队满：end2==(endl+1)mod(M-1)c.队空：end2==(endl+l)modM;队满：endl==(end2+1)modMD.队空：endl==(end2+1)modM；队满：end2==(end1+1)mod(M-1)10非空的循环单链表head的尾结点（由p所指向〉满足：A.P一＞next==N1JLL;B.p==NULL;C.p->next==head;D.p==head11查找效率最高的二叉排序树是：A. 所有结点的左子树都为空的二叉排序树B.所有结点的右子树都为空的二叉排序树c.平衡二叉树D.没有左子树的二叉排序树12下面关于求关键路径的说法不正确的是：A.求关键路径是以拓扑排序为基础的B.关键活动一定位于关键路径上C.一个事件的最早开始时间同 以该事件为 尾的弧的活动最早开始时间相同D.一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的差13在一个单链表中，若q结点是p结点的前驱结点，若在q和p之间插入结点 s，则执行：A.P甲＞next=s一＞next;s->next=p:B.s->next=p一＞next;p＞next=s;C.P一＞next=s;s一＞next=q;D.q一＞next=s;s->next=p;14设有一个对称矩阵A，采用压缩存储方式，以行序为主序存储，all为 第一个元素，其存储地址为1，每个元素占一个地址空间，则a85地址为：A.23B.33C.18D.4015就平均查找速度而言，下列几种查找速度从慢至快的关系是：A.JI顶序折半 哈希分块B. 分块 折半 哈希顺序C.顺序分块 折半哈希D. 顺序 哈希 分块折半三填空题（共20分，每题2分）1广义表A=(x，旬，b,c,d））的表尾是一一一注意：所有答案必须写在答题本上，不得写在试题纸上，否则无效。2在双循环链表中 ，删除指针 p所指结点的语句序列是一一一和一一一。3快速排序是一一一排序 改进后的结果。4求解一个图的单源和多源最短路径的算法分别是一一一和Floyd 算法。5通常称表示前驱和后继的指针叫做一一一’而这种使树中结点的空指针 成员存放前驱或后继信息的过程叫做一一一。6图的一一一优先搜索类似于树的层次遍历。7设给定权值总数有n个，其哈夫曼树的结点总数为一一一。8希尔排序快速排序和冒泡排序中一一一是稳定的排序方法。9堆排序的两个重要步骤其一是一一一’其二是调整堆。10KMP算法中，串＇ababaaababaa’的 next 数组为一一一。四应用题（共50分，第1-6题每题7分，第7题8分） l给定二叉树的两种遍历序列，分别是： 前序遍历序列：EBIDGCAHF;中序遍历序列：EIGDCBHFA,(1）试画出二叉树；(2）并给出二叉树的后序遍历序列。2下图是一个无向带权图，请按照Prim算法从A节点出发构造一棵最小 生成树，并画出其生成过程。3给定一组数列（10,18,16,25,6,9,16）分别代表字符A,B,C,D,E,F,G出 现的频率，试画出哈夫曼树的构造过程，并给出各字符的编码值。4已知长度为12的表（jan,feb,mar,apr,may,june,ju ly,aug,sep,oct,nov,dec），请按表中元素顺序构造一棵二叉平衡树，并简单的画出构造过程。其中 ，无旋转的调整可以直 接 画在一张图上 ，有旋转的调整请 单独 画图并备注清楚。5给定关键字序列：15,38,ll,84,49,20,7,33,l4,29,36。请写出以下3 种排序方法的第一趟排序结果(1）选择排序（2）快速排序（3）增量为4的希尔排 序；请写出建好一个大根堆的结果；请写出第一趟堆排序以后的结果。注意：所有答案必须写在答题本上，不得写在试题纸上，否则无效。6设散列表的长度为13，散列函数为H(k)=k%13，给定的关键码序列为19 ,13,22,02,68,15,84,26。试画出用线性探测法解决冲突时所构成的散列表，并求出平均查找长度ASL。7用迪杰斯特拉（Dijkstra）算法求下图中Vl顶点到其他个顶点的最短 距离和最短路径，请根据下表补充完整的求解过程。五程序设计题（共30分，每题10分）l设计一个求二叉树的宽度的算法。2已知一个带表头结点的线性链表，试写出用直接插入排序方法将其结点按递增顺序排序的算法，算法中要尽可能少用辅助存储空间。3请设计深度遍历图的非递归算法。考研高分咨询罗老师电话/微信：**咨询QQ：**