综合练习 - 浙教版（2019）高中信息技术 选修1数据与数据结构（Word版，有答案）

综合练习 - 浙教版（2019）高中信息技术选修1 一、选择题 1．有如下 Python 程序段 def bianli(head): pt = head while pt != -1: print(data[pt][0],data[pt][1],"->",end='') pt = data[pt][1] print() data = [['A',1],['B',2],['C',3],['D',-1]] head = 0 bianli(head) #遍历链表，显示初始状态为“A 1 ->B 2 ->C 3 ->D -1 ->” qt = head pt = data[qt][1] bianli(head) #遍历链表，显示最终状态为“A 2 ->C 1 ->B 3 ->D -1 ->” 执行该程序段后，链表遍历结果由初始状态变为最终状态，上述程序段中方框处可选代码为： ①data[data[qt][1]][1] = pt ②data[qt][1] = data[pt][1] ③data[pt][1] = data[data[pt][1]][1] 则方框处代码的正确顺序是（ ）A．①②③ B．①③② C．②①③ D．②③① 2．已知一个有7个节点的单向链表，设有头指针head和尾指针tail，如右图所示，下列操作需要遍历多个节点的是（ ） A．删除该链表中的最后一个节点 B．删除该链表中的第一个节点 C．在该链表第一个节点前插入一个新节点 D．在该链表最后一个节点后插入一个新节点 3．用两个列表a、b分别保存单向链表中的数据区域和指针区域。如下图所示，在节点x与节点y之间插入一个新节点，操作步骤正确的是（ ） ①b[i]= b[y] ②b[i]= b[x] ③b[y]= i ④b[x]=i ⑤b[i]= x ⑥b[i]= y A．③⑥ B．④② C．①③ D．②④ 4．用栈的数据结构编写进制转换中的“除二取余法”的程序段如下： st=[-1]*100 top=-1 n=int(input("请输入一个十进制数： ")) while n>0: while top!=-1: print(st[top],end="") top-=1 方框处的代码由以下四部分组成： ①n=n//2 ②top+=1 ③x=n%2 ④st[top]=x 下列选项中，代码顺序正确的是（ ） A．③④②① B．③①②④ C．①②③④ D．①③④② 5．某二分查找算法的 python 程序段如下， 运行该段代码后， 输出的结果不可能是（ ） import random a = [10,20,30,40,50,60,70,80] key = random.choice(a); i,j = 0,len(a)-1 ; s = "" while i<=j: m = (i+j)//2 if key == a[m]: s = s+"M"; break elif key < a[m]: j = m-1; s = s+"L" else: i = m+1; s = s+"R" print(s) A．LLM B．LRM C．RRRM D．RRLM 6．某对分查找算法的Python程序段如下： key=int(input("请输入待查数据值：")) d=[17,18,20,23,24,25,28,32,34,35] f=False;s="" i=0;j=len(d)-1 while i<=j: m=(i+j)//2 s=s+","+str(d[m]) if d[m]==key: f=True break if key < d[m]: j=m-1 else: i=m+1 if f==True: print("查找成功！遍历的数据"+s) else: print("没有找到！") 输入待查数据值为 23，执行该程序段，则输出的结果是（ ） A．25,20,24,23 B．24,18,20,23 C．25,20,23 D．24,20,23 7．有如下Python程序代码： s="ABCDEF";head=0;tail=0 que=[""]*100 for i in range(len(s)): if i%2==0: que[tail]=s[i] else: que[tail]=s[len(s)-i] tail=tail+1 for i in range(len(s)): print(que[head],end="") head=head+1 以上程序运行后，打印出列表的情况是：（ ） A．ABCDEF B．FEDCBA C．ACEFDB D．AFCDEB 8．已知一棵二叉树的前序遍历序列为：A-B-D-C-E，后序遍历序列为：D-B-E-C-A，则该二叉树是否 能唯一确定？中序遍历序列是？（ ） A．能唯一确定，中序遍历序列为：B-D-A-E-C B．不能唯一确定， 中序遍历序列可能为： B-D-A-E-C C．能唯一确定，中序遍历序列为：D-C-B-A-E D．不能唯一确定， 中序遍历序列可能为： D-C-B-A-E 二、填空题 9．递增数列用二分法查找时，先以_____位置的元素作为比较对象，如果要找的元素值小于该中点元素，则将待查序列_____为左半部分，否则为右半部分。每一次比较后都可以将查找区间缩小一半。 10．数组 d 的初始值如表所示 ... ...