【计算机类职业资格】国家二级C语言机试(数据结构与算法)模拟试卷5及答案解析.doc
《【计算机类职业资格】国家二级C语言机试(数据结构与算法)模拟试卷5及答案解析.doc》由会员分享,可在线阅读,更多相关《【计算机类职业资格】国家二级C语言机试(数据结构与算法)模拟试卷5及答案解析.doc(13页珍藏版)》请在麦多课文档分享上搜索。
1、国家二级 C 语言机试(数据结构与算法)模拟试卷 5 及答案解析(总分:78.00,做题时间:90 分钟)一、选择题(总题数:39,分数:78.00)1.设二叉树共有 375 个结点,其中度为 2 的结点有 187 个。则度为 1 的结点个数是(分数:2.00)A.0B.1C.188D.不可能有这样的二叉树2.在带链队列中,经过一系列正常的操作后,如果 front=rear,则队列中的元素个数为(分数:2.00)A.0 或 1B.0C.1D.队列满3.设一棵树的度为 3,其中没有度为 2 的结点,且叶子结点数为 5。该树中度为 3 的结点数为(分数:2.00)A.1B.2C.3D.不可能有这样
2、的树4.设二叉树共有 500 个结点,其中叶子结点有 250 个。则度为 2 的结点个数是(分数:2.00)A.0B.1C.249D.不可能有这样的二叉树5.T 列叙述中正确的是(分数:2.00)A.带链栈的栈底指针是固定的B.带链栈的栈底指针是随栈的操作而动态变化的C.若带链队列的队头指针与队尾指针相同,则队列为空D.若带链队列的队头指针与队尾指针相同,则队列中至少有一个元素6.带链队列空的条件是(分数:2.00)A.front=rear=NULLB.front=rear=1C.front=NULL 且 rear=1D.front=1 且 rear=NULL7.设一棵树的度为 3,其中没有度
3、为 2 的结点,且叶子结点数为 6。该树中度为 3 的结点数为(分数:2.00)A.1B.2C.3D.不可能有这样的树8.下列叙述中正确的是(分数:2.00)A.循环队列是线性结构B.循环队列是线性逻辑结构C.循环队列是链式存储结构D.循环队列是非线性存储结构9.设某棵树的度为 3,其中度为 3、2、1 的结点个数分别为 3、0、4。则该树中的叶子结点数为(分数:2.00)A.7B.8C.6D.不可能有这样的树10.设有一个栈与一个队列的初始状态均为空。现有一个序列 A,B,C,D,E,F,G,H。先分别将序列中的前 4个元素依次入栈,后 4 个元素依次入队;然后分别将栈中的元素依次退栈,再将
4、队列中的元素依次退队。最后得到的序列为(分数:2.00)A.D,C,B,A,E,F,G,HB.D,C,B,A,H,G,F,EC.A,B,C,D,E,F,G,HD.A,B,C,D,H,G,F,E11.下叙述中错误的是(分数:2.00)A.具有两个根结点的数据结构一定属于非线性结构B.具有两个以上指针域的链式结构一定属于非线性结构C.具有两个以上叶子结点的数据结构一定属于非线性结构D.具有一个根结点且只有一个叶子结点的数据结构也可能是非线性结构12.下列结构中属于线性结构链式存储的是(分数:2.00)A.双向链表B.循环队列C.二叉链表D.二维数组13.下列叙述中错误的是(分数:2.00)A.循环
5、链表中有一个表头结点B.循环链表的存储空间是连续的C.循环链表实现了空表与非空表运算的统一D.循环链表的表头指针与循环链表中最后一个结点的指针均指向表头结点14.度为 3 的一棵树共有 30 个结点,其中度为 3、1 的结点个数分别为 3、4。则该树中的叶子结点数为(分数:2.00)A.14B.15C.16D.不可能有这样的树15.在长度为 97 的顺序有序表中作二分查找,最多需要的比较次数为(分数:2.00)A.7B.96C.48D.616.下列结构中属于非线性结构的是(分数:2.00)A.二叉链表B.二维数组C.循环队列D.双向链表17.从表中任何一个结点位置出发就可以不重复地访问到表中其
6、他所有结点的链表是(分数:2.00)A.循环链表B.双向链表C.单向链表D.二叉链表18.设二叉树的前序序列与中序序列均为 ABCDEFGH,则该二叉树的后序序列为(分数:2.00)A.HGFEDCBAB.ABCDEFGHC.ABCDHGFED.DCBAHGFE19.设某棵树的度为 3,其中度为 3、1、O 的结点个数分别为 3、4、15。则该树中总结点数为(分数:2.00)A.22B.30C.35D.不可能有这样的树20.下列叙述中正确的是(分数:2.00)A.矩阵是非线性结构B.数组是长度固定的线性表C.对线性表只能作插入与删除运算D.线性表中各元素的数据类型可以不同21.在快速排序法中,
7、每经过一次数据交换(或移动)后(分数:2.00)A.能消除多个逆序B.只能消除一个逆序C.不会产生新的逆序D.消除的逆序个数一定比新产生的逆序个数多22.线性表的长度为 n。在最坏情况下,比较次数为 n 一 1 的算法是(分数:2.00)A.顺序查找B.有序表的插入C.寻找最大项D.同时寻找最大项与最小项23.设某棵树的度为 3,其中度为 2、1、0 的结点个数分别为 3、4、15。则该树中总结点数为(分数:2.00)A.22B.30C.35D.不可能有这样的树24.下列叙述中错误的是(分数:2.00)A.向量是线性结构B.非空线性结构中只有一个结点没有前件C.非空线性结构中只有一个结点没有后
8、件D.只有一个根结点和一个叶子结点的结构必定是线性结构25.在希尔排序法中,每经过一次数据交换后(分数:2.00)A.能消除多个逆序B.只能消除一个逆序C.不会产生新的逆序D.消除的逆序个数一定比新产生的逆序个数多26.设二叉树的后序序列与中序序列均为 ABCDEFGH,则该二叉树的前序序列为(分数:2.00)A.HGFEDCBAB.ABCDEFGHC.ABCDHGFED.DCBAHGFE27.下列叙述中正确的是(分数:2.00)A.循环队列是队列的链式存储结构B.能采用顺序存储的必定是线性结构C.所有的线性结构都可以采用顺序存储结构D.具有两个以上指针的链表必定是非线性结构28.下列叙述中正
9、确的是(分数:2.00)A.算法的复杂度是指算法所处理的数据量B.算法的复杂度是指算法程序中指令的数量C.算法的复杂度是指算法控制结构的复杂程度D.算法的复杂度包括时间复杂度与空间复杂度29.设二叉树的前序序列为 ABDEGHCFIJ,中序序列为:DBGEHACIFJ。则按层次输出(从上到下,同一层从左到右)的序列为(分数:2.00)A.ABCDEFGHIJB.DGHEBIJFCAC.JIHGFEDCBAD.GHIJDEFBCA30.设循环队列的存储空间为 Q(1:50),初始状态为 front=rear=50。经过一系列正常的操作后,front1=rear。为了在该队列中寻找值最大的元素,在
10、最坏情况下需要的比较次数为(分数:2.00)A.0B.1C.48D.4931.设顺序表的长度为 40,对该表进行冒泡排序。在最坏情况下需要的比较次数为(分数:2.00)A.780B.820C.40D.4132.设表的长度为 n。在下列算法中,最坏情况下时间复杂度最高的是(分数:2.00)A.堆排序B.希尔排序C.有序链表查找D.循环链表中寻找最大项33.设循环队列的存储空间为 Q(1:50),初始状态为 front=rear=50。经过一系列正常的操作后,front=rear1。为了在该队列中寻找值最大的元素,在最坏情况下需要的比较次数为(分数:2.00)A.0B.1C.49D.5034.设二
11、叉树的前序序列为ABDEGHCFIJ,中序序列为 DBGEHACIFJ。则后序序列为(分数:2.00)A.DGHEBIJFCAB.JIHGFEDCBAC.GHIJDEFBCAD.ABCDEFGHIJ35.设顺序表的长度为 16,对该表进行简单插入排序。在最坏情况下需要的比较次数为(分数:2.00)A.15B.30C.60D.12036.下列结构中为非线性结构的是(分数:2.00)A.树B.向量C.二维表D.矩阵37.设表的长度为 n。在下列结构所对应的算法中,最坏情况下时间复杂度最低的是(分数:2.00)A.堆排序B.有序链表查找C.希尔排序D.循环链表中寻找最大项38.设循环队列的存储空间为
12、 Q(1:m),初始状态为 front=rear=m。经过一系列正常的操作后,front=1,rear=m。为了在该队列中寻找值最大的元素,在最坏情况下需要的比较次数为(分数:2.00)A.mB.m1C.m2D.139.设二叉树的后序序列为 DGHEBIJFCA,中序序列为 DBGEHACIFJ。则前序序列为(分数:2.00)A.ABDEGHCFIJB.JIHGFEDCBAC.GHIJDEFBCAD.ABCDEFGHIJ国家二级 C 语言机试(数据结构与算法)模拟试卷 5 答案解析(总分:78.00,做题时间:90 分钟)一、选择题(总题数:39,分数:78.00)1.设二叉树共有 375 个
13、结点,其中度为 2 的结点有 187 个。则度为 1 的结点个数是(分数:2.00)A.0 B.1C.188D.不可能有这样的二叉树解析:解析:二叉树的每个结点至多只有二棵子树(不存在度大于 2 的结点),二叉树的子树有左右之分,次序不能颠倒。二叉树的第 i 层至多有 2 i1 个结点;深度为 k 的二叉树至多有 2 k1 个结点;对任何一棵二叉树 T,如果其终端结点数为 n 0 ,度为 2 的结点数为 n 2 ,则 n 0 =n 2 +1。本题中,度为 2 的结点有 187 个,叶子结点应该有 187+1=188 个,度为 1 的结点个数=375187188=0。2.在带链队列中,经过一系列
14、正常的操作后,如果 front=rear,则队列中的元素个数为(分数:2.00)A.0 或 1 B.0C.1D.队列满解析:解析:队列是一种特殊的线性表,特殊之处在于它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作,和栈一样,队列是一种操作受限制的线性表。进行插入操作的端称为队尾,进行删除操作的端称为队头。队列的链式存储也称为链队列。为了便于操作,可给链队列添加 1 个头结点,并令头指针指向头结点。队列为空的判断条件是头指针和尾指针的值相同,且均指向头结点。当队列为空(0)或 1 时,front=rear。3.设一棵树的度为 3,其中没有度为 2 的结点,且叶
15、子结点数为 5。该树中度为 3 的结点数为(分数:2.00)A.1B.2 C.3D.不可能有这样的树解析:解析:树的度是指一棵树中,最大的结点的度称为树的度。本题中树的度为 3,那么树中最少有一个结点的度为 3。而树中没有度为 2 的结点,叶子结点数为 5,度为 1 的结点下面只有一个叶子结点。因此,该树中含 2 个度为 3 的结点满足题目要求。4.设二叉树共有 500 个结点,其中叶子结点有 250 个。则度为 2 的结点个数是(分数:2.00)A.0B.1C.249 D.不可能有这样的二叉树解析:解析:二叉树的每个结点至多只有二棵子树(不存在度大于 2 的结点),二叉树的子树有左右之分,次
16、序不能颠倒。二叉树的第 i 层至多有 2 i1 个结点;深度为 k 的二叉树至多有 2 k1 个结点;对任何一棵二叉树 T,如果其终端结点数为 n 0 ,度为 2 的结点数为 n 2 ,则 n 0 =n 2 +1。本题中,叶子结点有 250 个,度为 2 的结点数为 n 2 =n 0 1=2501=249。5.T 列叙述中正确的是(分数:2.00)A.带链栈的栈底指针是固定的B.带链栈的栈底指针是随栈的操作而动态变化的 C.若带链队列的队头指针与队尾指针相同,则队列为空D.若带链队列的队头指针与队尾指针相同,则队列中至少有一个元素解析:解析:栈(stack)又名堆栈,它是一种运算受限的线性表。
17、其限制是仅允许在表的一端进行插入和删除运算。这一端被称为栈顶,相对地,把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈,它是把新元素放到栈顶元素的上面,使之成为新的栈顶元素;从一个栈删除元素又称作出栈或退栈,它是把栈顶元素删除掉,使其相邻的元素成为新的栈顶元素。带链栈的栈底指针是随栈的操作而动态变化的;若带链队列的队头指针与队尾指针相同,则队列可能为 0 也可能为 1。6.带链队列空的条件是(分数:2.00)A.front=rear=NULL B.front=rear=1C.front=NULL 且 rear=1D.front=1 且 rear=NULL解析:解析:带链队列空的条件有
18、两个:一个是 front=rear,一个是他们都等于空。7.设一棵树的度为 3,其中没有度为 2 的结点,且叶子结点数为 6。该树中度为 3 的结点数为(分数:2.00)A.1B.2C.3D.不可能有这样的树 解析:解析:树的度是指一棵树中,最大的结点的度称为树的度。本题中树的度为 3,也就是最少有一个度为 3 的结点。要求没有度为 2 的结点,且叶子结点为 6,如果要有度为 3 的结点,那么最多只有 5 个叶子结点;而画不出 6 个叶子结点。因此这样的树是没有的。8.下列叙述中正确的是(分数:2.00)A.循环队列是线性结构 B.循环队列是线性逻辑结构C.循环队列是链式存储结构D.循环队列是
19、非线性存储结构解析:解析:为充分利用向量空间,克服“假溢出”现象的方法是:将向量空间想象为一个首尾相接的圆环,并称这种向量为循环向量。存储在其中的队列称为循环队列(Circular Queue)。线性结构是一个有序数据元素的集合。常用的线性结构有:线性表,栈,队列,双队列,数组,串。常见的非线性结构有:二维数组,多维数组,广义表,树(二叉树等),图。9.设某棵树的度为 3,其中度为 3、2、1 的结点个数分别为 3、0、4。则该树中的叶子结点数为(分数:2.00)A.7 B.8C.6D.不可能有这样的树解析:解析:树的度是指一棵树中,最大的结点的度称为“树的度”。根据题目可知本树中没有度为 2
20、 的结点。树的总结点=(度 1*个数+度 2*个数)+1,这里我们设总结点数为 n,那么 n=3*3+2*0+1*4+1=14。树的叶子结点数等于总结点减去所有度不为 0 的结点,也就是 1434=7。10.设有一个栈与一个队列的初始状态均为空。现有一个序列 A,B,C,D,E,F,G,H。先分别将序列中的前 4个元素依次入栈,后 4 个元素依次入队;然后分别将栈中的元素依次退栈,再将队列中的元素依次退队。最后得到的序列为(分数:2.00)A.D,C,B,A,E,F,G,H B.D,C,B,A,H,G,F,EC.A,B,C,D,E,F,G,HD.A,B,C,D,H,G,F,E解析:解析:栈(s
21、tack)又名堆栈,它是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算。因此栈的出栈顺序是先入后出,所以顺序是 D,C,B,A。 队列是一种特殊的线性表,特殊之处在于它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作,和栈一样,队列是一种操作受限制的线性表。进行插入操作的端称为队尾,进行删除操作的端称为队头。因此,队的出队顺序是,先入先出,所以顺序是 E,F,G,H。最后的顺序是:D,C,B,A,E,F,G,H。11.下叙述中错误的是(分数:2.00)A.具有两个根结点的数据结构一定属于非线性结构B.具有两个以上指针域的链式结构一定属于非线性结
- 1.请仔细阅读文档,确保文档完整性,对于不预览、不比对内容而直接下载带来的问题本站不予受理。
- 2.下载的文档,不会出现我们的网址水印。
- 3、该文档所得收入(下载+内容+预览)归上传者、原创作者;如果您是本文档原作者,请点此认领!既往收益都归您。
下载文档到电脑,查找使用更方便
5000 积分 0人已下载
下载 | 加入VIP,交流精品资源 |
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 计算机 职业资格 国家 二级 语言 数据结构 算法 模拟 试卷 答案 解析 DOC
