ImageVerifierCode 换一换
格式:DOC , 页数:15 ,大小:48.50KB ,
资源ID:499011      下载积分:2000 积分
快捷下载
登录下载
邮箱/手机:
温馨提示:
如需开发票,请勿充值!快捷下载时,用户名和密码都是您填写的邮箱或者手机号,方便查询和重复下载(系统自动生成)。
如填写123,账号就是123,密码也是123。
特别说明:
请自助下载,系统不会自动发送文件的哦; 如果您已付费,想二次下载,请登录后访问:我的下载记录
支付方式: 支付宝扫码支付 微信扫码支付   
注意:如需开发票,请勿充值!
验证码:   换一换

加入VIP,免费下载
 

温馨提示:由于个人手机设置不同,如果发现不能下载,请复制以下地址【http://www.mydoc123.com/d-499011.html】到电脑端继续下载(重复下载不扣费)。

已注册用户请登录:
账号:
密码:
验证码:   换一换
  忘记密码?
三方登录: 微信登录  

下载须知

1: 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。
2: 试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓。
3: 文件的所有权益归上传用户所有。
4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
5. 本站仅提供交流平台,并不能对任何下载内容负责。
6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

版权提示 | 免责声明

本文([计算机类试卷]国家二级C语言(数据结构与运算)机试模拟试卷5及答案与解析.doc)为本站会员(feelhesitate105)主动上传,麦多课文库仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知麦多课文库(发送邮件至master@mydoc123.com或直接QQ联系客服),我们立即给予删除!

[计算机类试卷]国家二级C语言(数据结构与运算)机试模拟试卷5及答案与解析.doc

1、国家二级 C语言(数据结构与运算)机试模拟试卷 5及答案与解析 一、选择题 1 某二叉树的中序遍历序列为 CBADE,后序遍历序列为 CBADE,则前序遍历序列为 ( A) EDABC ( B) CBEDA ( C) CBADE ( D) EDCBA 2 下列叙述中正确的是 ( A)在循环队列中,队头指针和队尾指针的动态变化决定队列的长度 ( B)在循环队列中,队尾指针的动态变化决定队列的长度 ( C)在带链的队列中,队头指针与队尾指针的动态变化决定队列的长度 ( D)在带链的栈中,栈顶指针的动态变化决定栈中元素 的个数 3 设栈的存储空间为 S(1:60),初始状态为 top=61。现经过一

2、系列正常的入栈与退栈操作后, top=1,则栈中的元素个数为 ( A) 60 ( B) 59 ( C) 0 ( D) 1 4 设顺序表的长度为 n。下列排序方法中,最坏情况下比较次数小于 n(n-1)/2的是 ( A)堆排序 ( B)快速排序 ( C)简单插入排序 ( D)冒泡排序 5 在长度为 n的顺序表中查找一个元素,假设需要查找的元素有一半的机会在表中,并且如果元素在表中,则出现在表中每个位置上的可能性是相同的。则在平均情况下需要 比较的次数大约为 ( A) (3 n)/4 ( B) n ( C) n/2 ( D) n/4 6 设一棵树的度为 3,其中度为 3, 2, 1的结点个数分别为

3、 4, 1, 3。则该棵树中的叶子结点数为 ( A) 10 ( B) 11 ( C) 12 ( D)不可能有这样的树 7 设栈的存储空间为 S(1:50),初始状态为 top=0。现经过一系列正常的入栈与退栈操作后, top=51,则栈中的元素个数为 ( A)不可能 ( B) 50 ( C) 0 ( D) 1 8 设顺序表的长度为 n。下列算法中,最坏情况下比较次数等于 n(n-1)/2的是 ( A)快速排序 ( B)堆排序 ( C)顺序查找 ( D)寻找最大项 9 设表的长度为 n。下列算法中,最坏情况下比较次数小于 n的是 ( A)二分查找法 ( B)堆排序 ( C)快速排序 ( D)顺序

4、查找法 10 下列叙述中错误的是 ( A)循环链表是循环队列的存储结构 ( B)二叉链表是二叉树的存储结构 ( C)栈是线性结构 ( D)循环队列是队列的存储结构 11 设一棵树的度为 4,其中度为 4, 3, 2, 1的结点个数分别为 2, 3, 3, 0。则该棵树中的叶子结点数为 ( A) 16 ( B) 15 ( C) 17 ( D)不可能有这样的树 12 循环队列的存储空间为 Q(1:100),初始状态为 front=rear=100。经过一系列正常的入队与退队操作后, front=rear=99,则循环队列中的元素个数为 ( A) 0或 100 ( B) 1 ( C) 2 ( D)

5、99 13 设顺序表的长度为 n。下列算法中,最坏情况下比较次数小于 n的是 ( A)寻找最大项 ( B)堆排序 ( C)快速排序 ( D)顺序查找法 14 设栈的顺序存储空间为 S(1:m),初始状态为 top=m+1。现经过一系列正常 的入栈与退栈操作后, top=0,则栈中的元素个数为 ( A)不可能 ( B) m+1 ( C) 1 ( D) m 15 某二叉树的后序遍历序列与中序遍历序列相同,均为 ABCDEF,则按层次输出(同一层从左到右)的序列为 ( A) FEDCBA ( B) CBAFED ( C) DEFCBA ( D) ABCDEF 16 循环队列的存储空间为 Q(1:20

6、0),初始状态为 front=rear=200。经过一系列正常的入队与退队操作后, front=rear=1,则循环队列中的元素个数为 ( A) 0或 200 ( B) 1 ( C) 2 ( D) 199 17 设栈的顺序存储空间为 S(1:m),初始状态为 top=0。现经过一系列正常的入栈与退栈操作后, top=m+1,则栈中的元素个数为 ( A)不可能 ( B) m+1 ( C) 0 ( D) m 18 下列排序法中,最坏情况下时间复杂度最小的是 ( A)堆排序 ( B)快速排序 ( C)希尔排序 ( D)冒泡排序 19 某二叉树的前序遍历序列与中序遍历序列相同,均为 ABCDEF,则按

7、层次输出(同一层从左到右)的序列为 ( A) ABCDEF ( B) BCDEFA ( C) FEDCBA ( D) DEFABC 20 下列叙述中正确的是 ( A)对数据进行压缩存储会降低算法的空间复杂度 ( B)算法的优化主要通过程序的编制技巧来实现 ( C)算法的复杂度与问题的规模无关 ( D)数值型算法只需考虑计算结果的可靠性 21 设数据结构 B=(D,R),其中 D=a,b,c,d,e,f R=(a,b),(b,c),(c,d),(d,e),(e,f),(f,a) 该数据结构为 ( A)非线性结构 ( B)循环队列 ( C)循环链表 ( D)线性结构 22 下列排序法中,每经 过一

8、次元素的交换会产生新的逆序的是 ( A)快速排序 ( B)冒泡排序 ( C)简单插入排序 ( D)简单选择排序 23 某带链的队列初始状态为 front=rear=NULL。经过一系列正常的入队与退队操作后, front=rear=10。该队列中的元素个数为 ( A) 1 ( B) 0 ( C) 1或 0 ( D)不确定 24 某完全二叉树按层次输出(同一层从左到右)的序列为 ABCDEFGH。该完全二叉树的前序序列为 ( A) ABDHECFG ( B) ABCDEFGH ( C) HDBEAFCG ( D) HDEBFGCA 25 下列叙述中正确的是 ( A)有的二叉树也能用顺序存储结构表

9、示 ( B)有两个指针域的链表就是二叉链表 ( C)多重链表一定是非线性结构 ( D)顺序存储结构一定是线性结构 26 下列各排序法中,最坏情况下时间复杂度最小的是 ( A)堆排序 ( B)快速排序 ( C)希尔排序 ( D)冒泡排序 27 某带链队列初始状态为 front=rear=NULL。经过一系列正常入队与退队操作后, front=10, rear=5。该队列中的元素个数为 ( A)不确定 ( B) 5 ( C) 4 ( D) 6 国家二级 C语言(数据结构与运算)机试模拟试卷 5答案与解析 一、选择题 1 【正确答案】 A 【试题解析】 后序遍历次序是 “左右根 ”,中序遍历次序是

10、“左根右 ”。由定义可知: 后序遍历中最后一个就是树根结点,即 E结点; 在中序遍历中,根结点左边的是左子树集,右边的是右子树集,即 CBAD是根结点 E的左子树集合。问题就会转化为:求后序遍历是 CBAD,中序遍历是 CBAD的子树,方法同上。因为中序遍历中, D结点右边没有结点了,所以 D结点不包含右子树,否则就会被分为 2个子问题。以下是这道题的详细推理过 程:步骤 1:由 CBADE得出根结点为 E,由中序遍历可知 CBADE,右子树为空;步骤 2:由 CBAD得出左子树集合的根节点为 D,由中序可知 CBAD,右子树为空;步骤 3:同理,二叉树更新后如下图所示。 【知识模块】 数据结

11、构与运算 2 【正确答案】 A 【知识模块】 数据结构与运算 3 【正确答案】 A 【试题解析】 栈是向上增长的,每次压入一个元素,栈的 TOP指针向上移动一位,即 top-1。当压入第一个元素时, TOP指针指向 60+1-1 = 60;当压入第二个元素时, TOP指针指向 60+1-2 = 59; ;以此类推,当压入第 N个元素时,TOP指针指向 60+1-N = 1,则 N=60。所以选项 A正确。 【知识模块】 数据结构与运算 4 【正确答案】 A 【试题解析】 假设线性表的长度为 n,则在最坏情况下,冒泡排序需要经过 n/2遍的从前往后扫描和 n/2遍的从后往前扫描,需要比较次数为

12、n(n-1)/2。快速排序法的最坏情况比较次数也是 n(n-1)/2。简单插入排序,无论是否最坏都需要 n(n-1)/2比较。堆排序,无论是否最坏都需要比较 O(nlog2n)次。所 以选项 A正确。 【知识模块】 数据结构与运算 5 【正确答案】 A 【试题解析】 在长度为 n的顺序表中查找一个元素,最好的情况是目标在第一个,一次找到;最坏的情况是目标在最后一个, n次找到。那么平均长度为:(1+2+.+n)/n=(n(n+1)/2)/n=(n+1)/2 本题需要查找的元素有一半的机会在表中,则在平均情况下需要比较的次数大约为 (1+n)/2+1)/2=(3 n)/4。所以选项 A正确。 【

13、知识模块】 数据结构与运算 6 【正确答案】 A 【试题解析】 因为任一棵树中 ,结点总数总分支数目 1,所以:n0+4+1+3=(n0*0 + 3*4 + 2*1 + 1*3)+1,计算结果 n0=10。其中, n0表示叶子结点。所以选项 A正确。 【知识模块】 数据结构与运算 7 【正确答案】 A 【试题解析】 栈是向上增长的,每次压入一个元素,栈的 TOP指针向上移动一位,即 top-1。对于这个题目,由于 top初始值等于 0,此时入栈一个元素, top值减 1,即 0-1=-1,发生下溢错误,所以选项 A正确。 【知识模块】 数据结构与运算 8 【正确答案】 A 【试题解析】 假设线

14、性表的长度为 n,则在最坏情况下,快速排序法的最坏情况比较次数也是 n(n-1)/2;堆排序,无论是否最坏都是比较 O(nlog2n)次,所以选项A正确。 【知识模块】 数据结构与运算 9 【正确答案】 A 【试题解析】 二分法查找只适用于顺序存储的有序表。二分查找的基本方法是:将被查元素 x与线性表的中间项进行比较,若中间项的值等于 x,则说明查到;若小于中间项的值则在线性表的前半部分;以相同的方法进行查找;若大于中间项的值,则在线性表的后半部分以相同的方法进 行查找。在最坏情况下,二分查找需要比较 log2n次。所以选项 A正确。 【知识模块】 数据结构与运算 10 【正确答案】 A 【试

15、题解析】 循环队列属于逻辑结构,其实质还是顺序存储,只是使用指针进行首尾的联结,其实现的存储方式可分为:分散的链表和连续的线性表,与其逻辑结构实现功能无关。所以选项 A正确。 【知识模块】 数据结构与运算 11 【正确答案】 A 【试题解析】 因为任一棵树中 ,结点总数总分支数目 1,所以: n0+2+3+3+0=( n0*0 + 4*2 + 3*3 + 2*3+1*0) +1。计算得出 n0=16。其中, n0表示叶子结点,所以选项 A正确。 【知识模块】 数据结构与运算 12 【正确答案】 A 【试题解析】 循环队列中,由于入队时尾指针 rear向前追赶头指针 front;出队时头指针 f

16、ront向前追赶尾指针 rear,造成队空和队满时头尾指针均相等。因此,无法通过条件 front=rear来判别队列是 “空 ”还是 “满 ”。对于这个题目来说,经过一系列正常的入队与退队操作后, front=rear=99,此时,要么队列为空(元素个数为 0),要么队列为满(元素个数 为 100),因此选项 A正确。 【知识模块】 数据结构与运算 13 【正确答案】 A 【试题解析】 如果顺序表是线性存储的(不包括线性的链式表),那么元素要不就是从大到小,要不就是小到大的顺序,假设第一个数就是最大值,那么需要比较 1次, n-1应该是最坏情况下要比较的次数,所以选项 A正确。 【知识模块】

17、数据结构与运算 14 【正确答案】 A 【试题解析】 栈是向上增长的,每次压入一个元素,栈的 TOP指针向上移动一位,即 top-1。对于这个题目,由于 top初始值等于 m+1,此时入 栈一个元素, top值减 1,即 m+1-1=m,依次类推,当栈满时, top的值等于 1,不会出现 top的值等于 0。所以选项 A正确。 【知识模块】 数据结构与运算 15 【正确答案】 A 【试题解析】 后序遍历次序:左右根;中序遍历次序:左根右。由定义可知: 后序遍历中最后一个是树的根结点,即 F结点; 在中序遍历中,根结点左边的是左子树集,右边的是右子树集,即 ABCDE是根结点 F的左子树集合。问

18、题就会转化为:求后序遍历是 ABCDE,中序遍历是 ABCDE的子树。方法同上,因为中序遍历中, E结点右边没有结点 了,所以 E结点不包含右子树,否则就会被分为 2个子问题。以下是这道题的详细推理过程:步骤 1:由 ABCDEF得出根结点为 F,由中序遍历可知 : ABCDEF,右子树为空;步骤 2:由 ABCDE得出左子树集合的根节点为 E,由中序可知: ABCDE,右子树为空;步骤 3:同理,二叉树更新后如下。 所以按层次输出 (同一层从左到右 )的序列为 FEDCBA。 【知识模块】 数据结构与运算 16 【正确答案】 A 【知识模块】 数据结构与运算 17 【正确答案】 A 【试题解

19、析】 栈是向上增长的,每 次压入一个元素,栈的 TOP指针向上移动一位,即 top-1。对于这个题目,由于 top初始值等于 0,此时入栈一个元素, top值减 1,即 0-1=-1,出现下溢错误,所以选项 A正确。 【知识模块】 数据结构与运算 18 【正确答案】 A 【试题解析】 假设线性表的长度为 n,则在最坏情况下,冒泡排序需要经过 n/2遍的从前往后扫描和 n/2遍的从后往前扫描,需要比较次数为 n(n-1)/2。快速排序法的最坏情况比较次数也是 n(n-1)/2。简单插入排序,无论是否最坏都需要 n(n-1)/2比较。堆排序,无论是否最 坏情况都是比较 O(nlog2n)次。所以选

20、项 A正确。 【知识模块】 数据结构与运算 19 【正确答案】 A 【试题解析】 前序遍历次序:根左右;中序遍历次序:左根右。由定义可以知道: 前序遍历中第一个就是树根结点,即 A结点; 在中序遍历中,根结点左边的是左子树集,右边的是右子树集,即 BCDEF是根结点 A的右子树集合。问题就会转化为:求前序遍历是 BCDEF,中序遍历是 BCDEF的子树,方法同上。详细推理过程:步骤 1:由 ABCDEF得出根结点为 A,由中序遍历可知:左子树为空, ABCDE F ;步 骤 2:由 BCDEF得出右子树集合的根节点为 B,由中序可知:左子树为空, BCDEF;步骤 3:同理,二叉树更新后如下。

21、 所以按层次输出 (同一层从左到右 )的序列为 ABCDEF,选项 A正确。 【知识模块】 数据结构与运算 20 【正确答案】 A 【知识模块】 数据结构与运算 21 【正确答案】 A 【试题解析】 该逻辑结构为非线性结构,在 R=(a,b),(b,c),(c,d),(d,e),(e,f),(f,a)中,各结点之间形成一个循环链。 【知识模块】 数据结构与运算 22 【正确答案】 A 【试题解析】 冒泡排序只交换相邻元素,但不是每次移动都产生新的逆序。简单插入排序的元素移动不会产生新的逆序。快速排序每一次交换移动都会产生新的逆序,因为当不会有新的逆序产生时,本轮比较结束。故选项 A正确。 【知

22、识模块】 数据结构与运算 23 【正确答案】 A 【试题解析】 循环队列用数组 A0;m-1存放其元素值,已知其头尾指针分别是front和 rear,则当前队列的元素个数是 (rear-front+m)%m=1,所以选项 A正确。 【知识模块】 数据结构 与运算 24 【正确答案】 A 【试题解析】 完全二叉树的特点是除最后一层外,每一层上的节点数均达到最大值;在最后一层上只缺少右边的若干结点。根据上述的特点,完全二叉树按层次输出(同一层从左到右)的序列为 ABCDEFGH,可以得到其结构如下: 所以此完全二叉树的前序序列是 ABDHECFG,选项 A正确。 【知识模块】 数据结构与运算 25

23、 【正确答案】 A 【试题解析】 完全二叉树如果 “根 ”从 1开始编号,则第 i结点的左孩子编号为2i,右孩子为 2i+1,双亲编号为( i/2)下取整,空间紧密 ,适合顺序存储结构。所以选项 A正确。 小提示:取整是指取不超过实数 x的最大整数,称为 x的整数部分。上取整就是对实数取大于当前实数的第一个整数;下取整就是对当前实数去掉小数取整。 【知识模块】 数据结构与运算 26 【正确答案】 A 【试题解析】 快速排序、冒泡排序最坏情况下时间复杂度是 O(n2);希尔排序最坏情况下时间复杂度是 O(n1.2) 。堆排序最坏情况下时间复杂度是 O(nlog2n),所以选项 A正确。 【知识模块】 数据结构与运算 27 【正确答案】 A 【试题解析】 循环 队列用数组 A0:m-1存放其元素值,已知其头尾指针分别是front和 rear,则当前队列的元素个数是 (rear-front+m)%m=(5-10+m)%m=(m-5)%m。因为本题中的 m值不确定,所以 (m-5)%m的值不能确定。所以选项 A正确。 【知识模块】 数据结构与运算

copyright@ 2008-2019 麦多课文库(www.mydoc123.com)网站版权所有
备案/许可证编号:苏ICP备17064731号-1