选修1 数据与数据结构 期中模拟预测卷

( ※※请※※不※※要※※在※※装※※订※※线※※内※※答※※题※※ ) ( …………○…………外…………○…………装…………○…………订…………○…………线…………○………… ) ( …………○…………内…………○…………装…………○…………订…………○…………线…………○……………………○…………内…………○…………装…………○…………订…………○…………线…………○………… ) ( 学校:___________姓名：___________班级：___________考号：___________ ) ( …………○…………外…………○…………装…………○…………订…………○…………线…………○………… ) 保密★启用前 选修1 数据与数据结构 （月考模拟卷） 考试分数：100分；考试时间：90分钟 姓名： 班级： 分数： （满分：100分 时间：90分钟） 题型 选择题 非选择题题 总计 题数 12题 3题 15题 分数 100分 得分 1． 选择题  1.将英文单词“student”中的每个字符按次序以单链表的形式进行存储，操作过程中漏掉了字符 e，存储状态如图所示： 现将字符e存放于1111H处，并按正确的次序插入单链表中，则元素d、e、n的“链接地址”依次是（       ） A．100CH，1014H，1111H B．100CH，1111H，1014H C．1111H，100CH，1014H D．1111H，1014H，100CH 2. 如果要在一个已有的链表中删除一个节点，需要修改哪些节点的指针（ ） A．只需要修改该节点的前驱节点 B．只需要修改该节点的后继节点 C．需要修改该节点的前驱节点和后继节点 D．不需要修改任何节点的指针，直接释放该节点的内存 3 . 有如下程序段： a=[[2,2,1],[8,0,4],[3,3,0],[6,-1,2],[8,1,-1]] ans=head=3 p=a[head][2] while p!=-1: if a[ans][0] < a[p][0] : ans=p p=a[p][2] print(ans,a[ans][0],sep=",") 则程序运行后，下列说法正确的是（ ） A．链表数据值依次为2->8->3->6->8 B．程序输出结果为4,8 C．a[0][2]的值为1，双向链表a的头节点数据值为2 D．a[1][1]的值为0，双向链表a的尾节点数据值为8 4 . 有一组含有9个元素的有序链表：1->3->5->6->8->11->15->18->20，现为该链表增设关键节点，建立索引，下列说法不正确的是（ ） A．一级索引中的关键节点为1,5,8,15,20 B．二级索引中的关键节点为1,8,20 C．若要在建立的一级索引的基础上插入元素7，则需要比较3次即可找到7插入的位置 D．若要在建立的二级索引的基础上查找元素18，则需要比较4次就可以找到元素18 5 . 语句Dim a&(1 To 20)，b#(2,-1 To 1)定义两个数组，其类型分别为： （ ） A．二维单精度实型数组和二双精度型数组 B．二维长整型数组和二维单精度实型数组 C．一维单精度实型数组和二维整型数组 D．一维长整型数组和二维双精度型数组 6 . 有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 7. 利用栈求逆波兰表达式（表达式由操作数和运算符组成）的方法是:从左往右扫描该表达式，遇到操作数时入栈；遇到运算符时，把处于栈上方的两个元素依次出栈，用运算符计算，并把计算结果压入栈中。如此反复操作，直至表达式扫描结束。当用该算法求逆波兰表达式abcd-*e/+f-的值时（abcdef表示不同的操作数），所使用的栈的深度至少为（ ） A．3 B．4 C．5 D．6 8 . 栈s的最大长度为3，初始为空，经过一系列的入栈、出栈操作，若元素入栈的顺序是a，b，c，d，e，则可能的出栈序列为（ ） A．a，e，d，c，b B．c，a，b，d，e C．a，d，c，e，b D．e，d，c，b，a 9 . 下列关于线性表的描述，正确的是（ ） A．链表在访问、插入、删除节点操作时，算法效率比数组高 B．栈是一种“先进先出，后进后出”的线性表结构 C．循环队列是首尾相连的队列，数据入队时无需考虑是否会“溢出” D．字符串是元素个数有限的线性表结构 10 . 某单向队列存储空间足够，使用head记录队首元素所在的位置，tail记录队尾元素的下一个位置，经过“出队，入队，出队，出队，入队，出队”操作后，head=6，tail=8，则在操作前队列中元素的个数是（ ） A．0 B．2 C．4 D．6 11 . 队列在Python中，用（ ）实现队列的创建，队列的基本操作：（ ）（ ）（ ）（ ）线性数据结构又称线性表。 A．随机；入队；出队；求队长；判队空 B．列表；入队；出队；求队长；判队空 C．列表；随机；出队；求队长；判队空 D．入队；随机；列表；求队长；判队空 12 . 在日常幻灯片的放映中，可以通过超级链接方式进行幻灯片之间的任意跳转。和这种跳转方式相似的数据结构是（　　） A．数 B．链表 C．队列 D．栈 13 . 有如下程序段： bt=["A","B","C","D",None,"E","F"] result=[] stack=[] i=0 while stack or (i<len(bt) and bt[i] is not None): if i < len(bt) and bt[i] is not None: stack.append(i) i=2*i+1 else: i=stack.pop() result.append(bt[i]) i=2*i+2 print("-".join(result)) 则程序运行后输出的结果为（ ） A． A-B-D-C-E-F B．D-B-E-F-C-A C．D-B-A-E-C-F D．A-B-C-D-E-F 二．非选择题 14.在Python语言中，可以使用列表来模拟链表节点的插入操作。以下Python程序段用二维列表来定义单向链表。如要在该链表中插入节点，可以通过程序来修改相应节点的指针达到目的。 （1）如下图所示，请根据程序补充完整未插入数据前的链表数据区域的值（依次填写）① _________、 _________、 _________、 _________。此时链表的头指针的值是② _________。 （2）实现链表插入的 Python 程序如下，请在程序划线处填入合适的代码。 data=[[8,-1],[7,4],[5,5],[6,0],[1,3],[2,1]]       # 定义单向链表 head=2 leng=len(data) pos=int(input("请输入要插入的位置（0~%d）之间："%(leng))) val=int(input("请输入要插入的数据值：")) data.append([val,leng]) # 插入节点： p=head if pos== ___________:       # 加在链表最前面，作为首节点 data[leng][1]=p head=_________             # 更新头指针 else: q=data[p][1] c=0 while c < pos-1 and q!=-1: p=q q=data[p][1] c+=1 __________             # 更新指针 data[p][1]=leng # 用列表形式来显示插入后的链表： p=head s=[ ] while p!=-1: s.append(              ) p=data[p][1] print(s) 15.小明对入栈、出栈规则研究发现， 若有 n 个数字 1，2，3，……，n 按由小到大的顺 序入栈，则出栈序列必须遵循下述原则： 当数字 x 出栈后，则在x后出栈的小于x 的 所有数字必定以降序排列，比x大的数字可以夹杂在该降序序列中。现编写 Python 程 序，按上述原则验证一个随机产生的出栈序列是否可能， 程序运行界面如图所示。 (1) 根据题意，若有 7 个数字入栈， 则出栈序列“3→2→5→4→7→1→6”是______ (单选，填字母： A.可能 / B.不可能) (2) 实现上述功能的Python程序代码如下，程序中加框处代码有错，请改正_________。 (3)请在划线①②处填入合适代码__________、________。 import random n=int(input('请输入入栈元素的个数：')) data=[i+1 for i in range(n)] random.shuffle(data)                  #将序列的所有元素随机排序 s=” ” for i in range(n): print('随机产生的出栈序列为： '+s[1:]) flag=True;i=0 while i<n-1 and flag: ① for j in range(i+1,n): if data[j]<data[i]: if data[j]<x: x=data[j] else: ②#去除最后多余的'→' break i+=1 if flag: print('该出栈序列是可能的！') else: print('该出栈序列是不可能的！ ') 原创精品资源学科网独家享有版权，侵权必究！6 原创精品资源学科网独家享有版权，侵权必究！6 学科网（北京）股份有限公司 学科网（北京）股份有限公司 学科网（北京）股份有限公司 学科网（北京）股份有限公司 $$ ( ※※请※※不※※要※※在※※装※※订※※线※※内※※答※※题※※ ) ( …………○…………外…………○…………装…………○…………订…………○…………线…………○………… ) ( …………○…………内…………○…………装…………○…………订…………○…………线…………○……………………○…………内…………○…………装…………○…………订…………○…………线…………○………… ) ( 学校:___________姓名：___________班级：___________考号：___________ ) ( …………○…………外…………○…………装…………○…………订…………○…………线…………○………… ) 保密★启用前 选修1 数据与数据结构 （月考模拟卷） 考试分数：100分；考试时间：90分钟 姓名： 班级： 分数： （满分：100分 时间：90分钟） 题型 选择题 非选择题题 总计 题数 12题 3题 15题 分数 100分 得分 1． 选择题 1.C 解析：本题考查的是链表的读取。将字母e插入后，其链接地址如下图: 故，d、e、n的“链接地址”依次是111H、100CH、1014H。选项C正确。 2.C． 解析：在链表中删除一个节点，不仅要处理该节点的前驱节点的next指针（使其不再指向被删除节点），还需要处理被删除节点的后继节点（如果存在的话），将其前驱节点的指针调整为指向被删除节点的前驱节点，从而保持链表的连续性。 3. B． 解析：这个程序段实际上模拟了一个链表的遍历过程，其中`a`数组存储了链表节点的信息，每个子列表的第二个元素是值，第三个元素是下一个节点的索引。程序从索引为3的节点开始遍历，并寻找具有最大值的节点索引。在这个例子中，遍历过程如下： - 开始于索引3（值为6），p指向a[3][2]，即索引0。 - 索引0处的值为2，小于当前最大值6，不更新ans。 - p变为a[0][2]，即索引1。 - 索引1处的值为8，大于当前最大值6，更新ans为1。 - p变为a[1][2]，即索引-1，结束循环。 最终输出ans的值（即最大值所在的索引）和该索引处的值，即4,8。 4. D．解析：二级索引是基于一级索引构建的，进一步减少查找次数。一级索引的关键节点为1,5,8,15,20，二级索引的关键节点为1,8,20。如果在二级索引基础上查找18，从8开始比较，只需比较3次（8之后的15和20）就能找到18，而不是4次。 5. D． 解析：`Dim a&(1 To 20)`定义了一个一维数组a，类型为长整型（&符号在某些编程语言中代表长整型），范围是从1到20。`b#(2,-1 To 1)`定义了一个二维数组b，类型为双精度浮点型（#符号在某些语言中代表双精度），形状为3行（索引从2到0，即-1到1）。 6. B． 解析：程序首先构建了一个栈`s`用于存储降序排列的元素，同时使用队列`q`暂存被移除的元素。经过一轮处理后，栈`s`中的元素为降序排列的数组元素，队列`q`则按原数组顺序存储了其余元素。第一行输出为栈`s`的内容降序，即7,6,5,4,3,2,1，第二行输出队列`q`的内容，即a的原始顺序7,3,6,4,2,1,5。因此，输出结果的第2行第3个数字是2。 7. B． 解析：逆波兰表达式求解过程中，栈中至少需要存放两个操作数以进行运算。对于给定的表达式abcd-*e/+f-，最深的情况是当进行到最后一项减法运算时，栈中需要有abcd和e的值（a*b-c/d-e），共五个元素，但由于运算过程中会不断弹出元素进行计算，最小深度发生在开始和结尾操作，最少需要保留两个操作数等待运算，故栈的深度至少为4。 8. C． 解析：栈的最大长度为3，意味着任何时候栈中最多只能有3个元素。入栈顺序为a，b，c，d，e，由于d入栈时栈已满（a，b，c已在栈中），d无法直接入栈，必须先出栈一些元素。按照栈的特性，应该先出栈b和c，再出栈a，然后d才能入栈。接着e尝试入栈，又需要先出栈d和a，然后e入栈。因此，可能的出栈序列是a，d，c，b，e，与选项C匹配。 9. D． 解析：字符串是由字符组成的有限序列，满足线性表的定义，即数据元素的有限序列。 10. C． 解析：队列操作后，head=6表示队首位置在索引6，tail=8表示队尾的下一个位置是索引8，因此队列中实际有8-6=2个空位。由于初始为空，经过一系列操作后，队列中元素的个数应为总长度减去空位数，即总长度(10) - 空位数(2) = 8。但这是操作后的状态，操作前的队列长度应为操作后长度减去所有入队操作的影响，即8 - (入队次数)。由于题目明确指出进行了3次入队操作，故操作前队列中有8 - 3 = 5个元素。但此处计算有误，正确的逻辑应是：每进行一次出队，队列长度减1，每进行一次入队，队列长度加1。由于最后head=6，tail=8，表明队列中有2个元素（队尾在8，队首在6，相差2），加上出队3次、入队3次的净影响为0（出队入队次数相同），因此操作前队列中元素的个数应为2，选项C正确。 11. B． 解析：在Python中，队列通常可以用列表实现，通过append方法实现入队，pop(0)或popleft方法实现出队，len方法求队长，判断队列是否为空可以直接检查列表长度是否为0。 12. B． 解析：幻灯片间的任意跳转类似于链表中的节点跳转，可以从任一节点跳到另一个节点，这与链表的灵活性相似。 13. B． 解析：这个程序段实现了一个特殊的遍历过程，模拟了二叉树的前序遍历（非递归）。遍历的顺序是根节点 -> 左子树 -> 右子树，通过栈来保存待访问的节点索引。根据给定的二叉树数组，程序运行后输出的结果是前序遍历的顺序，即D-B-E-F-C-A。 二．非选择题 14. data[leng][1]=qdata[p][0]leng 解析：本题主要考査Pyton程序的综合应用。(1)根据定义的单向链表data-[8,-1],[7,4].[5,51,[6,0].[1,31.[2,1]，可知补充完整未插入数据前的链表数据区域初始值从5开始，然后指向链表下标为5的节点数据为2，然后指向下标为1的节点，依次得到2-7-1一6。由head-2，可知此时链表的头指针的值是2。(2)⑥此处是在头部插入节点，即加在链表最前面，作为首节点，故判断条件是p0s--0，故填0。⑦datal[leng][]-p表示将新插入的节点连接到头节点p后，需要更新新的头节点指针，即head-leng，故此处填lcng。⑧循环结束后，即找到了需要插入的位置即p和q之间，将插入的节点指向q，节点p指向插入的节点，故填datalleng][]-q。⑨此处通过while循环用列表形式来显示插入后的链表，节点中索引为0代表节点值，索引为!代表指向下一个节点的指针，此处是更新p的值，指向下一个节点的指针故填data[p][0]。 15. B s+=’→’+str(data[i])x=data[i]flag-False 解析：本题主要考査栈数据结构及Python程序的综合应用。(1)根据提干原则:当数字x出栈后，则在x后出栈的小于x的所有数字必定以降序排列，比x大的数字可以夹杂在该降序序列中。3出栈后比3小的2、1是降序排列;当2出栈后比2小的1是降序排序;当5出栈后比5小的4、1是降序排列;当4出栈后比4小的1是降序排列;当7出栈后比7小的1、6没有按降序排列，故该出栈序列不可能，选B洗项。(2)加框处的代码是“s+=str(data[i]+一”。输出s变量是用的是s[1:]，结合运行界面应“去掉最后多余的“一”，可知加框处修改为"s+=-'+sur(datali])”。(3)处下边有一行代码“ifdataj]<x”，此行代码之上没有变量x的定义和赋值。python中变量使用前需要赋值声明，由此推断处和x有关。再结合上下文代码和题意，可知此处填写为x=data 。x表示当前比较到的最小值，初始化为出栈的值。最后的i语句会根据dag变量的值判断出栈序列是否可能。整个whilc语句块中都没有改变lag值的地方，由此推测此处和nag有关。该处属于的else语句块是不可能为出栈序列的情况，同时由break语句可推测此处设置fag设置为False。 原创精品资源学科网独家享有版权，侵权必究！6 原创精品资源学科网独家享有版权，侵权必究！6 学科网（北京）股份有限公司 学科网（北京）股份有限公司 学科网（北京）股份有限公司 学科网（北京）股份有限公司 $$