选修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 . 有1个空栈，数据“8,9,3,2,4”按顺序依次入栈。约定：A操作是指一个数入栈，P操作是指一个数出栈。进行APAAAPPA系列栈操作后，栈中元素从栈底到栈顶依次为（ ） A．9 4 B．8 3 2 C．9 3 2 D．8 4 5 . 下列说法或用法正确的是( ） A．OPTION BASE 6 B．OPTION BASE 语句的位置可以任意 C．DIM A(6,3 TO 7)定义的是二维数组 D．数组元素的下标不能是负数。 6. 设有数组定义语句：Dim a(5) As Integer，Listl 为列表框控件。下列给数组元素赋值的语句，错误的是（ ）。 A．a(3)=3 B．a(3)=VAL(InputBox(“InputData”） C．a(3)=Listl.ListIndex D．a=Array(1,2,3,4,5,6) 7 . 有如下Python程序段，其功能是将一个单向链表转换成原链表的逆序链表： lst=[[15,4],[30,-1],[8,0],[5,2],[19,1]] head=3 p=head q=-1 while p!=-1: tmp=lst[p][1] head=q 上述程序段执行后lst内容变为[[15,2],[30,4],[8,3],[5,-1],[19,0]]。方框处可选代码有：①q=p ②p=tmp ③lst[p][1]=q，则方框处的语句依次为（ ） A．①②③ B．②③① C．③①② D．③②① 8.使用列表模拟单向链表，链表中p节点的a[p][0]存储数据，a[p][1]存储其后继节点的指针。编写Python程序删除链表中所有的偶数项（头节点为该链表的第1项），部分代码如下： p=head #head指向该链表的头节点 while p!=-1: q=a[p][1] if （1） : （2） p=a[p][1] 上述程序段划线处可选语句为 ①q!=-1 ②a[q][1]!=-1 ③a[q][1]=a[p][1] ④a[p][1]=a[q][1] 则（1）（2）处填入的语句依次为（ ） A．①③ B．①④ C．②③ D．②④ 9 . 现采用新的排队方案为小明、小红、小丽、小辉四人排队， Python程序段如下： linklist=[["小明",1],["小红",2],["小丽",3],["小辉",-1]] def reset(head): if linklist[head][1]==- 1 or head==- 1: return head else: new_head=reset(linklist[head][1]) linklist[linklist[head][1]][1]=head linklist[head][1]=- 1 return new head p=h=reset(0) while p!=- 1: print(linklist[p][0],end="") p=linklist[p][1] 执行该程序段后，输出的结果是（ ） A．小明小红小丽小辉 B．小明小辉小丽小红 C．小辉小丽小红小明 D．小明小丽小红小辉 10 . 有Python程序段如下: s=[0]*10 q=[0]*10 a=[7,3,6,4,2,1,5] n, top, head, tail=len(a),0,0,0 s[top]=a[0] for i in range(1,n): while top ! =-1 and a[i]>s[top]: q[tail]=s[top] tail+=1 top-=1 top+=1 s[top]=a[i] while top!=-1: print(s[top], end=" ") top-=1 print()#输出换行 while head !=tail: print(q[head], end=" ") head+=1 该程序段运行后，输出结果的第2行的第3个数字是（ ） A．1 B．2 C．3 D．4 11. 现有栈S和队列Q，初始状态均为空，现将数据元素a1，a2，a3，a4，a5，a6依次进入队列Q，再将出队的元素依次进入栈S，若出栈的顺序为a2，a4，a3，a6，a5，a1，则栈S的容量至少应该为（ ） A．2 B．3 C．4 D．5 12 . 假设队列空间足够，队列中的元素个数为5。约定：T为入队操作，Q为出队操作，则经过TTQQTQTQQ 一系列操作之后，队首指针head，队尾指针tail的值可能为（ ） A．head=11，tail=7 B．head=7，tail=11 C．head=9，tail=12 D．head=12，tail=9 13 . 下列关于队列和栈的说法，不正确的是（ ） A．队列是一种先进先出的线性表，可在队尾进行插入操作 B．栈的特性是″先进后出，后进先出″ C．某栈的入栈的顺序为″abc″，出栈顺序只有3种 D．队列和栈都是线性数据结构，都可以用数组来实现 二．非选择题 14.小明来到探险岛寻宝，岛上共有N个宝藏（标号为0至N-1）。每个宝藏有一条路连接下一个宝藏，宝藏号和下一个宝藏号使用链表存储。小明想知道，从其中一个宝藏出发，最多可以找到多少个宝藏。 例如，共有5个宝藏，输入“1，3，4，4，1，”表示0~4各宝藏点连接的下一个宝藏依次是：1，3，4，4，1（如下表）。则最多可以找到4个宝藏，路径为：0号1号3号4号。 宝藏号 0 1 2 3 4 下一个宝藏号 1 3 4 4 1 程序代码如下： s=input("请输入宝藏连接的情况：") t=0;c="";a=[] for i in s:    if i!=",":        c+=i    else:        a.append([t,int(c)])        c=""        ________①        max=0 for head in range(0,t):     #枚举寻找宝藏起点    g=[]    p=head    while p not in g:        g.append(p)        ______②            if len(g)>max :        ______③           print(max) （1)       若有 4 个宝藏，且每个宝藏的连接情况为：2,0,0,1，那么小明最多可以挖到的宝藏数是 ____________。 （2)       请将代码补充完整。 15.某信息仅包含大写字母，字符数不超过n*n（n*n为密钥矩阵规模，n>0），加密过程如图a所示： 图a 图b （1）已知密钥矩阵按图a中所示，若原文为“OK”，则加密后的密文是_________，若输入的密文是“10，1，24，2，”，则原文是_________。 （2）根据上述加密算法编写解密程序，运行界面如图c所示。请在划线①②③处填上合适的代码。 图c def   getmm（x，n）:   #获取位置编号x的位置密钥值         row=（x-1）%n        col=（x-1）//n        if①_______：                     row=n-1-row        return key[row][col] #生成规模为n*n的密钥矩阵，存入二维矩阵key中 n=int（input（"请输入密钥矩阵规模n:"）） key=[[i*n+j+l for j in range(n)] for i in range(n)] #密文解密 p=input("请输入密文: ") mw=[] bmz=[] t=0 for i in range (1en(p)): #依次读取密文字符串中的数值，结果存入到列表mw中 s=p[i] if s!=",": .②_________ else: mw. append (t) t=0 k=len (mw) for i in range(k//2) :   #对密文解密，结果存入列表bmz中 bmz. append (mw [2*i]- ③_________ yw=" for i in range (k//2):   #转换为字母输出 yw=ywtchr (bmz [i]-1+ord("A")) print("原文为:"+yw) 原创精品资源学科网独家享有版权，侵权必究！6 原创精品资源学科网独家享有版权，侵权必究！6 学科网（北京）股份有限公司 学科网（北京）股份有限公司 学科网（北京）股份有限公司 学科网（北京）股份有限公司 $$ ( ※※请※※不※※要※※在※※装※※订※※线※※内※※答※※题※※ ) ( …………○…………外…………○…………装…………○…………订…………○…………线…………○………… ) ( …………○…………内…………○…………装…………○…………订…………○…………线…………○……………………○…………内…………○…………装…………○…………订…………○…………线…………○………… ) ( 学校:___________姓名：___________班级：___________考号：___________ ) ( …………○…………外…………○…………装…………○…………订…………○…………线…………○………… ) 保密★启用前 选修1 数据与数据结构 （月考模拟卷） 考试分数：100分；考试时间：90分钟 姓名： 班级： 分数： （满分：100分 时间：90分钟） 题型 选择题 非选择题题 总计 题数 12题 3题 15题 分数 100分 得分 1． 选择题 1.D 解析：树是一种非线性结构，而数组、链表和队列都是线性结构。 2. C． 解析：链表的每个节点包含数据和指向下一个节点的指针，因此不需要连续的内存空间。"撤销"操作通常与栈相关联，而非队列；排队就餐更贴近队列的特性而非栈；树的每个节点可能有多个相邻节点，而不是正好一个前后相邻节点。 3. D． 解析：栈和队列都是线性表，但它们对插入和删除操作进行了限制，栈是后进先出（LIFO），队列是先进先出（FIFO）。 4. C． 解析：根据操作序列APAAAPPA，可以这样理解： - A表示入栈，P表示出栈。 - 操作序列执行过程：A(8)入栈，P(8)出栈，P之后无操作，A(9)入栈，A(3)入栈，A(2)入栈，P(2)出栈，P(3)出栈，P(9)不出栈因为此时栈中只剩一个元素。 - 因此，最终栈中元素从栈底到栈顶依次为9、3、2。 5. C． 解析：此语句定义了一个二维数组，其中第一维下标为0到5（共6个），第二维下标为3到7（共5个）。 6. D． 解析：此语句试图将一个数组赋值给变量a，但a已经被定义为一个具有特定大小的数组，不能直接用Array函数创建的新数组覆盖。 7. C． 解析：为了反转链表，首先需要将当前节点的后继节点指针储存起来（③），然后将当前节点的后继指针指向其前驱节点（q，此时q应为之前的p值，故①在③之后执行），最后移动p指针到其原来的后继节点（②）。 8. B 解析：为了删除链表中的所有偶数项，需要在遍历时检查当前节点的值（a[q][0]）是否为偶数，这里是通过检查条件①q!=-1来保证p没有遍历到链表末尾。如果当前节点的值是偶数，则需要调整指针，使得当前节点的后继绕过当前偶数节点直接指向偶数节点的后继，即执行④a[p][1]=a[q][1]。 9. C． 解析：这段代码实现了一个链表的逆序操作，通过递归调用reset函数改变每个节点的指向，最终打印链表会从原链表的尾部开始输出，即逆序输出，因此输出结果为小辉、小丽、小红、小明。 10. B． 解析：程序段首先构建了一个降序栈`s`，同时使用队列`q`暂存被移除的元素。第一行输出为栈`s`的内容降序，即7,6,5,4,3,2,1，第二行输出队列`q`的内容，即a的原始顺序7,3,6,4,2,1,5。因此，输出结果的第2行第3个数字是2。 11. B． 解析：为了满足出栈顺序a2，a4，a3，a6，a5，a1，需要确保a2和a4先进栈，a3随后，之后a6入栈但a5和a1还需等待。因此，至少需要栈的容量为3，以便在a6入栈时，栈内已有a2和a4，且a3可以暂时出栈再入栈。 12. B． 解析：根据操作序列TTQQTQTQQ，队列初始为空，head=0，tail=0。每执行一次T（入队），tail加1；每执行一次Q（出队），head加1。因此，执行完这些操作后，head和tail的差值应为5（入队5次，出队5次），考虑到初始head=0，tail=0，最终head=5，tail=10。但根据题干，head=5时tail应为11，故选项B正确，head=7是笔误，正确解读应为head=5时tail=11，但基于给定选项，B最接近正确解读。 13. C． 解析：对于栈来说，如果入栈顺序是"abc"，理论上可以有多种出栈顺序，具体来说，有7种不同的出栈序列，分别是：abc, acb, bac, bca, cab, cba，因此选项C表述不正确。 二．非选择题 14. t+=1p=a[p][1]max=len(g) 解析：本题主要考查Python程序的综合应用。①数组a保存当前节点，以二维数组的形式，保存宝藏号和下一个宝藏号。此处变量(递增，即到下一个宝藏点，故填t+-1。②将宝藏p加到列表g中后，更新p的值为下一个宝藏号，故填p-a[p][]。③变量max保存最多宝藏数，当len(g)>max时，则更新max的值为max-len(g)。④若有4个宝藏，且每个宝藏的连接情况为:2.0.0.1，那么小明最多可以挖到的宝藏数是4个，路径为:3号一1号一2号一0号。 15. col%2=-1或其他等价答案t=t*10+int(s)或其他等价答案16,1.15,2.getmm(mw[2*i+1],n) 解析：本题考查的是数组的综合应用。0的编码值为15，位置编号!，其秘钥值!，加密值为15+1=16;K的编码值为11，位置编号2，其秘钥值4，加密值为11+4=15，故若原文为“OK”，则加密后的密文是16，1，15，2，;若输入的密文是”10，1，24，2，”，则第一位的编码值为:10-1-9对应字母为1，第二位的编码值为:24-4=20对应字母为T，故原文是:IT。(2)row表示行号，col表示列号，依据秘钥矩阵图，当列号为奇数时，从下往上访问，故第一空应为:co%2-1或其他等价答案;读取的字符不为",”则拼接到数字!后，故第二空为:t-t*10+int(s)或其他等价答案;列表索引从0开始，故索引号为偶数里存放的是加密值，奇数存放的是位置编号，依据加密原理倒推，可知编码值-加密值-秘钥值。函数gcmm(x，n)是获取位置编号x的位置密钥值，故第三空应为:getmm(mw[2*i+1],n)。 原创精品资源学科网独家享有版权，侵权必究！6 原创精品资源学科网独家享有版权，侵权必究！6 学科网（北京）股份有限公司 学科网（北京）股份有限公司 学科网（北京）股份有限公司 学科网（北京）股份有限公司 $$