数据结构考试题5

要求：所有的题目的解答均写在答题纸上，需写清楚题目的序号。每张答题纸都要写学号。上姓名和一、单项选择题 ( 每小题 2 分，共 20 小题，共计 40 分)1.某算法的空间复杂度为0(1) ，则 。A. 该算法执行不需要任何辅助空间C. 该算法执行不需要任何空间D. 该算法执行所需全部空间大小与问题规模n 无关2. 在长度为n 的顺序表中插入一个元素，对应算法的时间复杂度为_。A.O(1)B.O(log2n)C.O( n) D.O( n2)3. 设线性表中有 n 个元素，以下运算中， _ 在单链表上实现要比在顺序表上实现效率更高。A. 删除指定位置元素的后一个元素B. 在最后一个元素的后面插入一个新元素C. 顺序输出前 k 个元素D. 交换第 i 个元素和第 n-i+1 个元素的值 ( i=1， 2, ， n)4.以下数据结构中元素之间为非线性关系的是_ 。A.栈B.队列C.线性表 D.以上都不是5.若一个栈用数组 data1.n 存储，初始栈顶指针top 为 n+1 ，则以下元素 x 进栈的正确操作是 _ 。A. top+;datatop=xB. datatop=x;top+;D.datatop=x;top -;C.top- ;datatop=x;front 和队尾指针rear ，在队不满时进队操作仅会改6.若某循环队列有队首指针变 _ 。A.frontB.rearC.front 和 rearD.以上都不队7. 设循环队列中数组的下标是0? N-1 ，其队头、队尾指针分别为f 和 r ( f 指向队首元素的前一位置， r 指向队尾元素 ) ，则其元素个数为 _ 。A.99B.100C.101D.199A.r-fB.r-f-1C.(r-f) % N+1D.(r-f+N) % N8.设树 T 的度为 4, 其中度为1、 叶子 2、3、4 的结点个数分别为4、 2、 1、1，贝 U T 中结点个数是。的A.5B.6C.7D.89. 一棵哈夫曼树中共有 199个结点，它用于多少个字符的编码_10.设森林 F 中有 4 棵树，第1、 2、3、 4 棵树的结点个数分别为a、 b、c、 d，将森林F 转换为一颗二叉树B, 则二叉树 B 根结点的左子树上的结点个数是_ 。A.a-1B.aC. a+b+cD.b+c+d11. 下列关于图的叙述中，正确的是_ 。I.回路是简单路径.存储稀疏图，用邻接矩阵比邻接表更省空间川.若有向图中存在拓扑序n列，则该图不存在回路A. 仅 nB.仅 i、 nC. 仅川D.仅 I、川12. 以下关于有向图的说法中，正确的是_ 。A. 强连通图是任何顶点到其他所有顶点都有边B. 完全有向图一定是强连通图C. 有向图中任一顶点的入度等于出度D. 有向图边集的子集和顶点集的子集可构成原有向图的子图13. 无向图的邻接矩阵是一个_ 。A. 对称矩阵B.零矩阵C. 上三角矩阵D.对角矩阵14. 如果从无向图的任一顶点出发进行一次广度优先遍历即可访问所有顶点，则该图 _. r 曰 疋是。A. 完全图B.连通图C.有回路D. 一棵树15. 用 Dijkstra 算法求一个带权有向图G 中从顶点 0 出发的最短路径，在算法执行的某时刻， S= 0,2,3,4 ，下一步选取的目标顶点可能是_ 。A. 顶点 2B.顶点 3C. 顶点 4D.顶点 716. _哈希表中出现冲突是指。A. 两个元素具有相同的序号B. 两个元素的关键字不同，而其他属性相同C. 数据元素过多D. 两个元素的关键字不同，而对应的哈希函数值( 存储地址 ) 相同17. 适合于折半查找的数据组织方式是_ 。A. 以链表存储的线性表B.以顺序表存储的任意线性表C.以链表存储的有序线性表D.以顺序表存储的有序线性表18. 对有 n 个记录的表进行直接插入排序，在最好情况下需比较_ 次关键字。A.n-1B.n+1C.n/2D.n(n -1)/219. 若数据元素序列 11,12,15,7,8,9,23,1,5 是采用下列排序方法之一得到的第二趟排序后的结果，则该排序算法只能是 _ 。A. 冒泡排序B.直接插入排序C.选择排序D. 二路归并排序20. 对一组数据 (25,84,21,47,15,27,68,35,20) 进行排序，前 3 趟的排序结果如下：第 1 趟： 20, 15, 21, 25, 47, 27, 68, 35, 84欢迎下载3第 2趟： 15,20,21,25,35,27,47,68,84第 3趟： 15,20,21,25,27,35,47, 68,84则所采用的排序方法是_ 。A. 简单选择排序B. 希尔排序C. 二路归并排序D.快速排序、问答题（共 4 小题，共计 35 分）1.（ 10 分）对于如图1 所示的带权无向图，直接给出利用普里姆算法（从顶点0 开始构造）和克鲁斯卡尔算法构造出的最小生成树的结果（注意：按求解的顺序给出最小生成树的所有边，每条边用2. （ 10 分）假设一棵二叉排序树的关键字为单个字母，其后序遍历序列为ACDBFIJHGE ，回答以下问题：（1） 画出该二叉排序树。（ 6 分）（2） 求在等概率下的查找成功的平均查找长度。（2 分）（3） 求在等概率下的查找不成功的平均查找长度。（2 分）3. （ 8 分）已知序列 15,5,16,2,25,8,20,9,18,12 ，给出采用二路归并排序法对该序列作升序排序时的每一趟的结果。4. （ 7 分）简要回答下列关于堆排序中堆的一些问题：（1） 通常堆采用顺序还是链式存储结构？（3 分）（2） 设有一个小根堆，即堆中任意结点的关键字均小于它的左孩子和右孩子的关键字。其中具有最大关键字的结点可能在什么地方？（4分）三、算法设计题（共2 小题，共计 25 分）1.（ 10 分）某带头结点的非空单链表L 中所有元素为整数，结点类型定义如下:typedef struct node int data;struct node *next; LinkNode;设计一个尽可能高效的算法，将所有小于零的结点移到所有大于等于零的结点的前面。2. （ 15 分）假设二叉树中有 n 个结点，每个结点值为单个字符，而且所有结点值均不相同，采用二叉链存储结构存储，其结点类型定义如下：typedef struct node char data;欢迎下载4struct node *lchild,*rchild; BTNode;请完成以下任务：（1） 设计一个算法，在二叉树b 中查找 x 结点（指结点值为x 的结点），若找到该结点，返回其地址，否则返回NULL 。给出你设计的算法的时间复杂度。（8 分）（2） 设计一个算法，利用（1）小题设计的算法输出二叉树b 中 x 结点的所有子孙结点值。（ 7 分）欢迎下载5“数据结构”考试试题（A ）参考答案、单项选择题（每小题2 分，共 20 小题，共计 40 分）1. B2. C3. A4. D5. C6. B7. D8. D9. B10. A11. C12. B13. A14. B15. D16. D17. D18. A19. B20. D问答题（共 4 小题， 共计 35 分）1. （ 10 分）答案：利用普里姆算法从顶点0 出发构造的最小生成树为：（ 0,1 ），（0,3 ），（1,2 ），（ 2,5 ），（ 5,4），（ 5 分）。利用克鲁斯卡尔算法构造出的最小生成树为：（ 0,1），（0,3 ），（1,2 ），（5,4），（ 2,5 ） ，（ 5分）。说明：顺序错误不给分。2.（ 10 分）答案：（1）该二叉排序树的后序遍历序列为ACDBFIJHGE ，则中序遍历序列为ABCDEFGHIJ ，由后序序列和中序序列构造的二叉排序树如图2 所示。（ 6 分）(2)ASL 成功 =(1 X1+2X2+4 X 3+2 X 4+1 X 5)/10=3 。 ( 2分)(3)ASL 不成功 =(6 X3+3X4+2X5)/11=40/11=3.64 。 ( 2分)欢迎下载63. （ 8 分）答案：采用二路归并排序法排序的各趟结果如图3 所示。（每趟2 分）欢迎下载7排序前 :15,5, 16,2, 25,8, 20,9, 18,12 length=1:5, 15,2, 16,8, 25,9, 20,12,18 length=2:2, 5,15, 16,8, 9, 20,25,12,18 length=4:2, 5,8, 9, 15,16,20,25,12,18 length=8:2, 5,8, 9, 12,15,16,18,20,25 排序后 ： 2, 5,8, 9, 12,15,16,18,20,25图 3 各趟排序结果4.（ 7 分）答案：（1） 通常堆采用顺序存储结构。（3 分）（2） 小根堆中具有最大关键字的结点只可能出现在叶子结点中。因为最小堆的最小关键字的结点必是根结点，而最大关键字的结点由偏序关系可知，只有叶子结点可能是最大关键字的结点。（4 分）算法设计题（共2 小题，共计 25 分）欢迎下载81. ( 10 分) 答案：void Move(LinkNode *&L) LinkNode *p=L-next,*pre=L; while (p!=NULL & p-datanext;while (p!=NULL) if (p-datanext=p-next;p-next=L-next;L-next=p;p=pre-next;else pre=p; p=p-next;2. ( 15 分) 答案：(1)(7 分)BTNode *Findx(BTNode *b,char x) BTNode *p;if (b=NULL)return NULL;/跳过小于 0 的结点/若*p 结点值小于 0/从链表中删除 *p 结点/将*p 结点插入到头结点之后p 指向 *pre 之后结点， pre 不变/若*p 结点值不小于0/pre 、p 同步后移一个结点/ /在二叉树 b 中查找 x 结点欢迎下载9else if (b_data=x) return b;p=Findx(b-lchild,x);if (p!=NULL)return p;return Findx(b-rchild,x);算法的时间复杂度为0( n) ( 1 分) 。(2)( 7 分)void Sons(BTNode *b,char x)/输出 x 结点的子孙，初始时b 指向 x 结点 if (b!=NULL) if (b-data!=x)printf(%c ,b-data);Sons(b-lchild,x);Sons(b-rchild,x);void OutSons(BTNode *b,char x) /输出二叉树b 中 x 结点的所有子孙结点值 BNode *p= Findx(b,x);if (p!=NULL)Sons(p,x);欢迎下载10