高中信息技术浙教版（2019）选修1 验收卷(六)　综合练习(B)（课件 练习含答案，2份打包）

(课件网) 第六章　大数据时代数据的组织 验收卷(六)　综合练习(B) (考试时间40分钟　满分50分) 一、选择题(本题共12小题，每小题2分，共24分) 1.下列关于数据结构的说法，正确的是(　　) D 解析　A选项数组中未使用到的空间导致内存浪费。B选项若删除的是头节点，只要修改头指针即可。C选项实现“后�———�按钮的功能是栈的功能。D选项栈是一种受限的数据结构，只能在一端进行操作。 A.数组的最大元素数量在定义时就已确定，因此在操作过程中不会导致内存浪费 B.删除链表节点时，链表中必定存在某个节点的指针区域发生变化 C.浏览器采用队列结构组织网页数据从而实现“后�———�按钮的功能 D.栈结构只有一端开放，数据进、出操作都只能在开放的一端进行 B 2.幼儿园中 8 个小朋友，依次编号(1－8)玩游戏，按编号顺序排队围成一圈，由编号 1 号的小朋友开始报数，报数报到 3 的小朋友出列，下一个编号的小朋友又从 1 开始报数，一直反复直到剩下最后一人，请问在该问题上采用的适合数据结构和剩下的小朋友的编号是(　　) A.二叉树7 B.队列7 C.栈4 D.链表 4 解析　本题考查数据结构的相关知识。适合的数据结构应为队列，出队的顺序为：3，6，1，5，2，8，4，最后剩下的一人编号为 7。 B 3.在利用栈来判断一个表达式的括号(只有小括号)是否匹配的过程中，当遇到表达式中的一个左括号时，就让其进栈，遇到一个右括号时，就对栈进行一次出栈操作；当栈最后为空，表示括号是配对的，否则是不配对的。现有表达式“(a＋b)*c＋((d－e)*f＋g)*h”，针对该表达式设计栈的大小至少为(　　) A.1 B.2 C.3 D.4 解析　遇到第一个左括号进栈，遇到第一个右括号时，栈中的左括号出栈。遇到第二个和第三个左括号，依次进栈。遇到第二个右括号，依次出栈，遇到第三个右括号，又依次出栈。此时栈为空，表达式中的括号配对成功。整个过程中，栈中最多有2个左括号，所以栈的大小至少为2。 D 4.有一棵树，节点的度和个数如下表所示。 解析　树中所有节点的度之和加1为节点总数，因此1*4＋2*3＋3*2＋4*1＝21。节点数为x＋4＋3＋2＋1＝x＋10，因此可以得到叶子节点数为11个。 度 0 1 2 3 4 节点个数 x 4 3 2 1 则叶子节点x的个数为(　　) A.8 B.9 C.10 D.11 B 5.已知某二叉树的中序遍历结果为BFDGAEHC，层序遍历(从上往下、从左往右)结果为ABCDEFGH，则下列有关该二叉树的说法，正确的是(　　) A.该二叉树是完全二叉树 B.用数组存储该二叉树时，节点F对应的数组下标为9 C.该二叉树有4个叶子节点 D.该二叉树的前序遍历结果为ABDFGCHE 解析　A为整棵树的根节点，从中序遍历来看，B和C分别是整棵树的左右节点。FDG是节点B的右子树，EH是节点C的左子树。第3层左边第1个节点为D，因此F是D的左子树，G是D的右子树。第3层左边第2个节点为E，因此H为E的右子树。画出树的形态如图所示。该树只有3个叶子节点，前序遍历为ABDFGCEH。 6.有如下Python程序段： import random a＝[8，10，2，7，11，9，16] c＝[0]*len(a) head＝0；tail＝0 for i in range(len(a)): 　t＝random.randint(0，1) 　 if tail－head<2 or t＝＝0： 　c[tail]＝a[i] 　tail＝tail＋1 　elif a[i]>c[head]： 　 head＝head＋1 print(c[head：tail]) 解析　若队列中数据元素小于2或者t的值为0，则将a[i]入队，否则当a[i]大于c[head]时出队，a中元素既可以不入队，也可以不出队(t为1，且a[i]小于等于c[head])。A选项8，10入队，2和7可以不入队，11让8出队，队列中只剩下1个元素，9入队，接着t的值为0，16入队。B选项8，10入队后，接着t的值依次为1，1，0，0，0。C选项队首为8，当遍历到11时，要么让8出队，要么产生的t为0，11入队，因此C ... ...