《湖北省计算机类专业人才培养合作联盟联合考试卷(数据结构B卷)》由会员分享，可在线阅读，更多相关《湖北省计算机类专业人才培养合作联盟联合考试卷(数据结构B卷)（10页珍藏版）》请在金锄头文库上搜索。
1、密封线 学院 专业 级 学号 姓名 密封线一、判断题 (每小题1分，共10分)1 数据的逻辑结构与各数据元素在计算机中如何存储有关。2.凡是为空的单链表都是不含任何节点的。3对顺序栈进行进栈、出栈操作，不涉及元素的前、后移动问题。4含有n个字符的字符串中所有子串的个数为n*(n+1)/2 + 1。5递归算法的执行效率比功能相同的非递归算法的执行效率高。6.在n（n 3）阶三对角矩阵中，每一行都有三个非零的元素。7霍夫曼树中不存在度为1的节点。8.强连通图不能进行拓扑排序。9.二叉排序树是用来进行排序的。10.排序的稳定性是指排序算法中比较的次数保持不变，且算法能够终止。二、填空题 (每小题1分
2、，共10分)1.一个算法具备的5个特性分别是可行性、有穷性、_、输入和输出。2.在有n个元素的顺序表中的任意位置插入一个元素所需移动元素的平均次数为_。3.栈是一种具有_特性的线性表。4.无论是顺序队列还是链式队列，插入和删除运算的时间复杂度都是_。5.递归函数f(1)=1，f(n) = f(n-1) + n(n1)的递归出口是_。6.完全二叉树中节点个数为n，则编号最大的分支节点的编号是_。7.对n个顶点的连通图来说，它的生成树一定有_边。8.采用哈希存储方法时，用于计算节点存储地址的是_。9.对二叉排序树进行_遍历，可以得到按关键字从小到大排列的节点顺序。10在排序过程中，不比较关键字大小
3、的排序方法是_。三、单向选择题 （每小题2分，共30分）1.算法的时间复杂度与_有关。A、问题规模B、计算机硬件性能C、编译程序质量D、程序设计语言2.链表不具有的特点是_。A、可随机访问任一元素B、插入删除不需要移动元素C、不必事先估计存储空间D、所需空间与线性表长度成正比密封线 学院 专业 级 学号 姓名 3.已知一个栈的进栈顺序是1，2，3，.，n， 其输出序列是P1, P2,., Pn, 若P1=n，则Pi的值为_。A、iB、n-iC、n-i+1D、不确定4.设顺序循环队列中数组的下标是0N-1，其头、尾指针分别为f（指向队头元素的前一个位置）和r（指向队尾元素），则其元素个数为_。A
4、、r-fB、r-f-1C、(r-f)%N+1D、(r-f+N)%N5.将递归算法转换成对应的非递归算法时，通常需要使用_保存中间结果。A、队列B、栈C、链表D、树6.若3叉树中有a个度为1的节点、b个度为2的节点、c个度为3的节点，则该树有_个叶子节点。A、1 + 2b + 3cB、1 + 2b + 3cC、2b + 3cD、1 + b + 2c7.若二叉树的中序遍历序列是abcdef，且c为根节点，则_。A、c左子树中有两个节点B、二叉树有两个度为0的节点C、二叉树的高度为5D、以上都不对8.无向图的邻接矩阵是一个_。A、对称矩阵B、零矩阵C、上三角矩阵D、对角矩阵9.在如图1所示的平衡二叉
5、树中插入关键字50后，得到一棵新平衡二叉树，在新平衡二叉树中，关键字37所在的节点的左右孩子节点中保存的关键字分别是_。A、13，50B、24，50C、24, 53D、24, 90图1 一棵平衡二叉树10.如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是_。A、完全图B、连通图C、有回路D、一棵树11.采用分块查找时，若线性表中共有625个元素，查找每个元素的概率相同，假设采用顺序查找来确定节点所在的块，则每块分为_个节点最佳。A、9B、25C、6D、512.具有5层节点的AVL树至少有_个节点。A、10B、12C、15D、1713.N条记录中按关键字大小找出Top
6、K(k N)条记录，使用下列_方法最节省时间。A、堆排序B、希尔排序密封线 学院 专业 级 学号 姓名 C、快速排序D、基数排序14.若表R在排序前已按关键字正序排列，则_方法的比较次数最少。A、直接插入排序B、快速排序C、归并排序D、简单选择排序15.用某种排序方法对线性表25,84,21,47,15,27,68,35,20进行排序时，排序过程如下：(1)25,84,21,47,15,27,35,68,20(2)21,25,47,84,15,27,35,68,20(3)15,21,25,27,35,47,68,84,20(4)15,20,21,25,27,35,47,68,84其所采用的排序
7、方法是_。A、简单选择排序B、希尔排序C、归并排序D、快速排序四、综合应用题 (每小题6分，共30分)1以数据集合2， 5， 7， 9， 13为权值构造一棵霍夫曼树，并计算其带权路径长度。图2 带权无向图2.给定如图2所示的带权无向图G，给出采用克鲁斯卡尔算法构造的最小生成树的过程。3. 从空二叉排序树开始，依次读入关键字序列(7, 16, 4, 8, 20, 9, 18, 5) 构造一棵二叉排序树，画出该二叉排序树，并计算在等概率情况下，该二叉排序树查找成功时的平均查找长度ASL。4. 以关键字序列265,301,751,129,937,863,742,694,076,438为例，写出使用快
8、速排序算法的各趟排序后，关键字序列的状态。5. 对含有n个互不相同元素的线性表，试设计程序同时找最大值和最小值元素。五、算法设计题（每小题10分，共20分）1. 有3个带头结点并且节点值递增的单链表h1、h2和h3，他们的节点个数分别为m、n和k，单链表的节点类型如下：typedef struct nodeint data ; struct node * next ; LinkList ;试设计一个算法：void merge(LinkList * &h, LinkList * h1, LinkList * h2, LinkList * h3)，将h1、h2和h3的所有节点归并成一个新的递增单链
9、表h，要求空间复杂度为O(1)，时间复杂度为O(m + n + k)。2. 试写一递归算法，从大到小输出二叉排序树中所有其值不小于x的关键字。13-14-1数据结构B卷参考答案判断题（101 = 10）1、 错误2、错误3、正确4、错误5、错误6、错误7、正确8、正确9、错误10、错误填空题（101 = 10）1、确定性2、n/23、后进先出或先进后出4、O(1)5、f(1)=16、n/27、n-18、哈希函数9、中序10、基数排序单向选择题（152 = 30）1、A2、A3、C4、D5、B6、D7、A8、A9、C10、B11、B12、B13、A14、A15、C综合应用题（56 = 30）1、
10、 构造的霍夫曼树如图所示：（3分）霍夫曼树WPL = （2+5）*3 + （7+9+13）*2 = 79 （3分）2、 采用克鲁斯卡尔算法构造最小生成树的过程如下: (a) (b) (c) (d) (e) (f)(每步1分)3、ASL = (1 + 2 2+ 3 3 + 2 4) / 8 = 22 / 8 = 2.75（二叉排序树3分，计算3分）4、快速排序过程如下：初始状态：265,301,751,129,937,863,742,694,076,438第1趟：076,129,265,751,937,863,742,694,301,438第2趟：076,129,265,751,937,863,
11、742,694,301,438第3趟：076,129,265,438,301,694,742,751,863,937第4趟：076,129,265,301,438,694,742,751,863,937（每趟1.5分）5、算法设计如下：void FindElem(KeyType A, KeyType &min, KeyType &max)int i;min = max = A0;for(i = 1; i n; i+)if(Ai max)max = Ai;算法设计题（210 = 20）1、 参考答案void subMerge(LinkList * &h, LinkList * h1, LinkList * h2)/ Merge two single listLinkList * p1 = h1-next, *p2 = h2-next, *t;h=h1; t=h;while(p1 != NULL & p2 != NULL) if(p1-data data) t-next = p1; t = p1; p1=p1-next;else t-next = p2; t = p2; p2=p2-next;if(p1 != NULL) t-next = p1;if(p2 != NULL) t-
