选修1 数据与数据结构 月考模拟预测卷

( ※※请※※不※※要※※在※※装※※订※※线※※内※※答※※题※※ ) ( …………○…………外…………○…………装…………○…………订…………○…………线…………○………… ) ( …………○…………内…………○…………装…………○…………订…………○…………线…………○……………………○…………内…………○…………装…………○…………订…………○…………线…………○………… ) ( 学校:___________姓名：___________班级：___________考号：___________ ) ( …………○…………外…………○…………装…………○…………订…………○…………线…………○………… ) 保密★启用前 选修1 数据与数据结构 （月考模拟卷） 考试分数：100分；考试时间：90分钟 姓名： 班级： 分数： （满分：100分 时间：90分钟） 题型 选择题 非选择题题 总计 题数 12题 3题 15题 分数 100分 得分 1． 选择题 1.  下图中的数据属于（　　） A． 结构化数据 B．半结构化数据 C．非结构化数据 D．准结构化数据 2.下列关于数据的说法，错误的是（ ） A．计算机的出现淘汰了手工处理数据的方式 B．数据的呈现形式不是单一的 C．事物的特征可使用不同的数据进行描述 D．互联网技术加速了数据的产生和传输 3. 下列有关数据结构的说法正确的是（ ） A．数组是一种适合用于组织、存储涉及频繁插入与删除的数据结构 B．链表中数据元素的逻辑顺序是通过链表中的指针链接次序实现的 C．链表在访问、插入和删除元素时，算法效率比数组高 D．树结构中，每个子节点的父节点可以有多个 4 . 数据存储的主要方式有（ ）。 A．本地存储 B．云端存储 C．本地存储和云端存储 D．以上都不对 5 . 半结构化数据包括（ ） A．Excel表格 B．银行账户上的消费记录 C．检查身体后得到的体检报告 D．HTML文档 6 . 有1个栈，栈底到栈顶的元素依次为a，b，c，d，e，f，g，有1个队列，初始为空。约定：P操作是指出栈后入队，Q操作是指仅出栈，R操作是指队列中1个元素出队后入队，S操作是指队列中1个元素出队。则经过PQPSRQPR系列操作后，队列中队首到队尾的元素依次为（ ） A．GFEDC B．GEC C．CE D．C 7 . 二维数组a的大小为n行m列，若a的存储方式为行优先存储，存储a中每个元素所需的存储空间为x，数组元素a[0][0]的存储位置为s，则数组元素a[i][j]的存储位置为（ ） A．s+（i*n+j）*x B．s+（i*m+j）*x C．s+（i+j*n）*x D．s+（i+j*m）*x 8 . 在Python中，如何使用列表模拟数组（ ） A．通过列表的索引访问元素，如同数组下标 B．列表中的元素类型必须一致 C．列表的存储方式与数组完全相同 D．列表长度一旦定义就不能改变 9 . 使用列表d模拟链表结构，每个节点包含数据区域（数据均为整型，范围为0~9）和指针区域，h为头指针。若d=[[1,2],[4,4],[3,3],[2,1],[5,-1]]，h=0，遍历该链表得到的数据为（ ） A．1、2、3、4、5 B．1、3、2、4、5 C．1、4、5 D．1、3、4、2、5 10 . 链表中的节点通常包含哪两部分（ ） A．数据域和控制域 B．数据域和指针域 C．指令域和地址域 D．标志域和内容域 11 . 下列哪个特性不属于数组的特点（ ） A．所有元素的数据类型相同 B．可以通过下标直接访问任意元素 C．存储空间固定不变 D．插入和删除元素操作高效 12 . 创建一个空链表时，通常会设置什么来表示链表的起始（ ） A．尾指针 B．头指针指向一个空节点 C．头指针指向NULL或-1 D．无需设置特殊标记 A．GFEDC B．GEC C．CE D．C 13 . 有如下Python代码，函数Linkinsert功能是在升序链表lst中按序插入数据data def Linkinsert(lst, data, head): p=head lst.append([data,-1]) if data<=lst[head][0]: lst[-1][1]=head head=len(lst)-1 else: q=lst[p][1] while ① and data>lst[q][0]: p=q q=lst[p][1] ② lst[-1][1]=q return head 则划线处应填写的代码是（ ） A．①q!=-1 ②lst[p][1]=len(lst)-1 B．①q!=-1 ②lst[p][1]=len(lst) C．①p!=-1 ②lst[q][1]=len(lst)-1 D．①p!=-1 ②lst[q][1]=len(lst) 二．非选择题 14.最幸运的人。某公司开展工会活动，其中有一个游戏是“谁是最幸运的人”，游戏规则如下：参加活动的员工每人领取一个编号（1～n），然后让他们按编号顺序围成一圈，由公司老总掷骰子的方法决定报数m（1～6），游戏开始时，从编号1号的人开始1～m报数，凡报到m的人退圈，接着由退圈的下一位开始重新从1开始报数，直到圈上最后只剩下一个人为止，他就是最幸运的人，将获得一份神秘礼物。程序运行界面如图所示。 输入活动人数n:100 报数m为:6 依次退圈的人的编号为: 6 12 18 24 30 36 42 48 54 60 66 72 78 84 90 96 2 9 16 23 31 38 45 52 59 67 74 81 88 95 3 11 20 28 37 46 55 63 71 80 89 98 7 17 27 39 49 58 69 79 91 100 13 25 35 50 62 75 86 99 14 29 43 57 73 87 4 21 40 56 76 93 10 33 53 77 97 22 47 70 1 32 64 92 26 65 5 44 85 41 94 61 19 8 83 15 51 34 82 最幸运的人(编号)是：68 使用链表方式实现的Python程序如下，请回答下列问题： import random list1=[] n=int(input(′输入活动人数n:′)) m=random.randint(1,6) #报数 print(′报数m为:′,m) for i in range(n-1): #初始化单向循环链表        list1.append([i+1,i+1]) #指针域存放后继节点的索引        ① head=0 left=n print(′依次退圈的人的编号为:′) while left>1: #删除节点直到只剩下1节点为止        for i in range(m-2):              head=list1[head][1]              t=list1[head][1]              print(list1[t][0],end=" ")              ②        head=list1[head][1]　#新一轮报数起点重新定位为删除节点的后继节点        left-=1 print(" 最幸运的人(编号)是:",③ ) （1）若活动人数为10人，报数为5，则最幸运的人的编号为____。 （2）请在程序划线处填入合适的代码。 划线①处应填入的代码为：____；划线②处应填入的代码为：____；划线③处应填入的代码为：____。 15.小美手里有如图a所示的各种面值的人民币及张数，她购物时习惯优先使用大额面值的人民币。 面值（元）        10 5 50 20 100 2 1 数量（张）        5 2 7 3 4 11 7 图a 例如某次消费金额为561元，在不找零的情况下完成支付，其方案为100元4张，50元3张，10元1张，1元1张。小美编写Python 程序，此方案执行结果如图b 所示。 请输入各纸币的面值：10, 5, 50, 20, 100, 2, 1 请输入各面值纸币对应的张数：5, 2, 7, 3, 4, 11, 7 请输入消费金额：561 消费561元的选择方案为： [[100, 4], [50, 3], [10, 1], [1, 1]] 图b （1）小美手上有4张10元，10张5元，50张1元，共消费36元，根据题意选择10元、5元、1元的张数分别为_________（填数字，用逗号隔开）。 （2）定义如下 linkedlist (faceval, num) 函数，功能为构建按纸币面值降序的有序链表，函数返回 money, 其中 faceval 数据项为纸币的面值，num 数据项为各面值纸币对应的张数。例如 faceval=["10", "5", "20"], num=["2", "5", "1"]，请在划线处填入合适的代码。 def linkedlist(faceval,num):             n=len(faceval)             money=[]             money.append([int(faceval[0]),int(num[0]),-1])             head=0             for i in range(1,n):                        q=p=head                        while p!=-1 and money[p][0]>int(faceval[i]):                                    q=p                                    p=money[p][2]                        if p==head:                                    money.append([int(faceval[i]),int(num[i]),head])                                    head=len(money)-1                        else:                       money. append ((          ))                                    money[q][2]=len(money)-1             return money,head （3）实现计算过程的 Python 程序如下，请在划线处填入合适的代码。 Def   find (monetary, head) : select=[] cur=sortmoney[head] while head!=-1: if monetary<cur[0]: head=cur[2] cur=sortmoney[head] continue i=1 while i<=cur[1]: monetary=monetary-cur[0] if      ①________: select. append ([cur[0], i]) if monetary==0: return select ②_______ if head!=-1: cur=sortmoney[head] break else: return -1 i=i+1 return -1 fv=input ("请输入各纸币的面值：") . split (', ')     #split (', ') 将字符串以逗号分割为列表 num=input ("请输入各面值纸币对应的张数：") . split (', ') sortmoney, head=linkedlist (fv, num) consume=int (input ("请输入消费金额：") ) choice=        ③________ if choice!=-1: print ("消费", consume, "元的选择方案为：", choice) else: print ("无符合要求的方案！ ") 原创精品资源学科网独家享有版权，侵权必究！6 原创精品资源学科网独家享有版权，侵权必究！6 学科网（北京）股份有限公司 学科网（北京）股份有限公司 学科网（北京）股份有限公司 学科网（北京）股份有限公司 $$ ( ※※请※※不※※要※※在※※装※※订※※线※※内※※答※※题※※ ) ( …………○…………外…………○…………装…………○…………订…………○…………线…………○………… ) ( …………○…………内…………○…………装…………○…………订…………○…………线…………○……………………○…………内…………○…………装…………○…………订…………○…………线…………○………… ) ( 学校:___________姓名：___________班级：___________考号：___________ ) ( …………○…………外…………○…………装…………○…………订…………○…………线…………○………… ) 保密★启用前 选修1 数据与数据结构 （月考模拟卷） 考试分数：100分；考试时间：90分钟 姓名： 班级： 分数： （满分：100分 时间：90分钟） 题型 选择题 非选择题题 总计 题数 12题 3题 15题 分数 100分 得分 1． 选择题 1.B． 解析：图中的数据展示了一种结构化与非结构化之间的数据形态，具有一定的层级和标签，但不如结构化数据严格，故归类为半结构化数据。 2. A． 解析：计算机并未完全淘汰手工处理数据的方式，某些场景下手工处理仍有其适用性和必要性。 3. B． 解析：链表通过每个节点中的指针链接来维持元素间的逻辑顺序，而不是物理位置上的顺序。 4. C． 解析：数据存储的主要方式包括本地存储和云端存储两种，两者各有优缺点，广泛应用于不同场景。 5. D． 解析：HTML文档是典型的半结构化数据，因为它有一定的结构（如标签），但不如XML等格式严格。 6. B． 解析：按照操作顺序执行，PQPSRQPR： - P: `g`出栈入队，栈变为`abcdef`，队列变为`g` - Q: `g`出队，队列为空 - P: `f`出栈入队，栈变为`abcde`，队列变为`f` - S: `f`出队，队列为空 - R: `f`重新入队，队列变为`f` - Q: `f`出队，队列为空 - P: `e`出栈入队，栈变为`abcd`，队列变为`e` - R: `e`出队重新入队，队列变为`e` - P: `d`出栈入队，栈变为`abc`，队列变为`ed` - Q: `d`出队，队列变为`e` 最终队列为`e`，但考虑到R操作的重复描述，实际队列应为`g`出队后未正确记录，最终队列应为`g`出栈后直接入队的结果，故正确答案应为`GEC`，此题可能存在描述或理解偏差，但基于给出的操作步骤，最合理的解释是B选项。 7. A． 解析：行优先存储时，元素的位置计算公式为基地址加上行号乘以列数再乘以每个元素的存储空间，加上列号乘以存储空间。 8. A． 解析：Python列表模拟数组的关键在于可以通过索引访问元素，尽管列表在内部实现上与数组有所不同。 9. B． 解析：根据链表结构d，遍历过程为：1→2→4→3→2→1→5，去除重复节点后为1、3、2、4、5。 10. B． 解析：链表节点通常包含存储数据的数据域和指向下一个节点的指针域。 11. D． 解析：数组在插入和删除元素时通常需要移动后续元素，因此效率不高。 12. C． 解析：创建空链表时，通常将头指针设置为指向一个特殊值，如NULL或-1，表示链表为空。 13. A． 解析：链表插入操作中，需在查找插入位置时确保指针未到达链表末尾（q!=-1），并在找到位置后将原节点的next指针指向新插入节点，此处应为lst[p][1]=len(lst)-1，因为新节点已追加至链表末尾。 二．非选择题 14. （1）2 若活动人数为10人，报数为5，则最幸运的人的编号为2。 解析：在这个游戏中，报数为5意味着每轮都会从当前报数的人开始数5个就有人退出，直到剩下最后一个。对于10个人，报数顺序为5、10，因此第5号人首先退出，然后从6号人重新开始报数，接下来是11号（实际上是1号，因为是循环链表），这样循环下去，最后留下的是2号人。 （2）划线①处应填入的代码为：`list1.append(head)`；划线②处应填入的代码为：`del list1[t]`；划线③处应填入的代码为：`list1[head][0]`。 15. （1）3，1，1 小美手上有4张10元，10张5元，50张1元，共消费36元，根据题意选择10元、5元、1元的张数分别为3, 1, 1。 解析：最优选择策略是从大额到小额依次减少使用，尽量避免使用小额货币。首先使用3张10元，达到30元，然后使用1张5元达到35元，最后使用1张1元达到36元。 （2）在函数`linkedlist(faceval, num)`中，划线处应填入的代码为：`[int(faceval[i]), int(num[i]), p]`。 （3）实现计算过程的 Python 程序中，划线处应填入的代码为： ① `monetary>=0` ② `monetary+=cur[0]*i` ③ `find(consume, head)` 解析： ① 当`monetary >= 0`时，表示当前面值的货币还能继续使用，因此将该面值和使用的张数加入到解决方案中。 ② 如果当前货币不足以支付剩余金额，需要回溯，将已经减掉的金额加回去，尝试使用下一个较小面值的货币。 ③ 调用`find`函数，传入消费金额和链表的头指针，以获取支付方案。 原创精品资源学科网独家享有版权，侵权必究！6 原创精品资源学科网独家享有版权，侵权必究！6 学科网（北京）股份有限公司 学科网（北京）股份有限公司 学科网（北京）股份有限公司 学科网（北京）股份有限公司 $$