浙江省绍兴市诸暨中学2021-2022学年高二上学期期中考试信息技术试题（选考）含答案

诸暨中学2021学年高二期中考试技术试卷（选考）

信息技术部分（共50分）

一、选择题（本大题共10题，每小题2分，共计20分。在每小题列出的四个选项中只有一项是最符合题目要求的）

1.计算机中的算法指的是解决某一个问题的有限运算序列，它必须具备输入（0个或多个输入）、输出（一个或多个输出）、（      ）等5个特性。

A. 可执行性、可移植性和可扩充性    B. 可执行性、有穷性和确定性  

C. 确定性、有穷性和稳定性     D. 易读性、稳定性和确定性

2.下面程序段的时间复杂度是（     ）。

 for(i=0;i<m;i++)

  for(j=0;j<n;j++)

   a[i][j]=i*j;

1. O(m2)　  B. O(n2)   C. O(m*n)  D. O(m+n)

3.数据结构是一门研究非数值计算的程序设计问题中计算机的数据元素以及它们之间的（   ）和运算等的学科。

A. 结构   B. 关系   C. 运算   D. 算法

4.设计一个判别表达式中括号是否配对的算法，采用（   ）数据结构最佳。

A. 顺序表  B. 链表       C. 队列       D. 栈

5.五节车厢以编号1，2，3，4，5顺序进入铁路调度站（栈），可以得到（    ）的编组。

 A. 3，4，5，1，2   B. 2，4，1，3，5  

C. 3，5，4，2，1   D. 1，3，5，2，4

6.用顺序存储的方法，将完全二叉树中所有结点按层逐个从左到右的顺序存放在一维数组R[1..N]中，若结点R[i]有右孩子，则其右孩子是（     ）。

A. R[2i-1]   B. R[2i+1]  C. R[2i]  D. R[2/i]

7.设一棵二叉树的中序遍历序列：badce，后序遍历序列：bdeca，则二叉树先序遍历序列为（    ）。

A. adbce  B. decab     C. debac     D. abcde

8.若以{4,5,6,7,8}作为权值构造哈夫曼树，则该树的带权路径长度为（     ）。

A. 67　   B. 68   C. 69   D. 70

9.一棵具有124个叶子结点的完全二叉树，最多有（   ）个结点。

A. 247   B.248   C.249   D.250

10.有一个有序表为{1,3,9,12,32,41,45,62,75,77,82,95,100},当折半查找值为82的结点时，（     ）次比较后查找成功。

A. 8      B. 4      C. 2      D.1

二、非选择题（本大题共4小题，每空2分，共计30分。第11题共3空；第12题共5空；第13题4空；第14题3空。）

第11题.推算某一天是星期几，可使用蔡勒公式计算。

蔡勒公式：w=y+[y/4]+[c/4]-2c+[26(m+1)/10]+d-1；相关参数如下：

w：星期； w对7取模得：0-星期日，1-星期一，2-星期二，3-星期三，4-星期四，5-星期五，6-星期六

c：世纪（年份的前两位数）

y：年（年份后两位数）

m：月（m大于等于3，小于等于14，即在蔡勒公式中，某年的1、2月要看作上一年的13、14月来计算，比如2003年1月1日要看作2002年的13月1日来计算）

d：日

[ ]代表取整，即只要整数部分。

输入年、月、日，求出这一天是星期几？如2003年1月1日是星期三。

请完善下面代码：

t="日一二三四五六"

y=int(input("请输入年份："))

m=int(input("请输入月份："))

d=int(input("请输入日："))

if m<=2:

             （1）       

    y=y-1

c=y//100

         （2）       

w=y+y//4+c//4-2*c+26*(m+1)//10+d-1

w=w%7

print("星期"+     （3）      )

第12题.小华规划自驾旅游路线，出发地为杭州，目的地为北京，规划过程中经过了多次更改。

第一次依次加入的途径地为上海、苏州、南京、济南、石家庄；

第二次在南京和济南之间加入了途径地青岛，取消了途径地南京;

第三次则在石家庄和北京之间加入了途径地天津。

请使用链表编程实现其更改过程，并输出三次更改路线后的结果。

完善代码如下：

a=["杭州","上海","苏州","南京","济南","石家庄","北京","青岛","天津"]

head=0

b=[-1,-1,-1,-1,-1,-1,-1,-1,-1]

for i in range(6):       #第一次规划

           （1）       

k=head                #第二次规划

while k!=-1:

    if a[k]=="南京":

        break

            （2）         

         （3）        

b[k]=7

k=head            

while k!=-1:

    if a[k]=="南京":

        break

    q=k

    k=b[k]

         （4）            

k=head                 #第三次规划   

while k!=-1:

    if a[k]=="石家庄":

        break

    k=b[k]

b[8]=b[k]

b[k]=8

k=head

while(k!=-1):

    print(a[k],end=" ")

            （5）           

第13题.设某银行有A,B两个业务窗口，且处理业务的速度不一样，其中A窗口处理速度是B窗口的2倍，即A窗口每处理完2个顾客，B窗口处理完1个顾客。给定到达银行的顾客序列，请按业务完成的顺序输出顾客序列。假设不考虑顾客先后到达的时间间隔，并且当不同窗口同时处理完2个顾客时，A窗口顾客优先输出。输入第一个数字是顾客总人数，后面是n位顾客的编号，编号为奇数的顾客需要到A窗口处理，为偶数的顾客则需要去B窗口处理。输出为按业务处理完成的顺序输出顾客的编号（数字间以空格分隔，但最后一个编号之后不能有空格）。

例如输入：8 2 1 3 9 4 11 13 15  输出为1 3 2 9 11 4 13 15

请完善程序代码：

list_A=[]

list_B=[]

n=int(input("请输入n总人数："))

for i in range(n):

    x=int(input())

    if x%2==1:

              （1）          

    else:

        list_B.append(x)

len_A=len(list_A)

len_B=len(list_B)

flag_space=0

i=0

j=0

while        （2）           :

    if i<len_A:

        if        （3）            :

            print(" ",end="")

        print(list_A[i],end="")

        i+=1

        flag_space+=1

    if i<len_A:

        if        （3）            :

            print(" ",end="")

        print(list_A[i],end="")

        i+=1

        flag_space+=1

    if j<len_B:

        if        （3）            :

            print(" ",end="")

        print(list_B[j],end="")

               （4）          

        flag_space+=1

第14题.输入中缀表达式，输出计算结果。如输入：9+(5-4)*4+8  输出：21

def js(x,y,ch):

    if ch=="+":

        return(x+y)

    elif ch=="-":

        return(y-x)

    elif ch=="*":

        return(x*y)

    else:

        return(y/x)

op={"+":1,"-":1,"*":2,"/":2}

expression = input("请输入中缀表达式")

expression = "("+expression+")"

result =[0]*100;top2=-1    # 操作数栈

stack = [""]*100;top=-1   # 操作符栈

for item in expression:

    if item in ["+","-","*","/"]:

        while top>=-1:

            if top==-1:

                top+=1

                         （1）            

                break

            else:

                if            （2）              :

                    top+=1

                    stack[top]=item

                    break

                else:

                    a=result[top2];top2-=1

                    b=result[top2];top2-=1

                               （3）             

                    top-=1

                    top2+=1

                    result[top2]=c

    elif item=="(":

        top=top+1

        stack[top]=item

    elif item==")":

        while top>=0:

            if stack[top]=="(":

                top-=1

                break

            else:

                a=result[top2];top2-=1

                b=result[top2];top2-=1

                c=js(a,b,stack[top])

                top-=1

                top2+=1

                result[top2]=c

    else:

        top2+=1

        result[top2]=int(item)

print(result[0])