资源简介

第六单元　数据结构
信息技术(50分)
一、选择题(本大题共12小题，每小题2分，共24分。每小题列出的四个备选项中只有一个是符合题目要求的，不选、多选、错选均不得分)
1.已知一棵完全二叉树的节点总数为10，则有关该二叉树的说法正确的是(　　)
A.树的度为10 B.树的层数为3
C.最后一层有3个节点 D.叶子节点数为3
2.现有一棵二叉树的前序遍历为ABCDEF，中序遍历为BCADFE，则该二叉树的后序遍历为(　　)
A.CBFEDA B.BCFEDA
C.CBDFEA D.BCEFDA
3.用一维数组表示二叉树，如下表所示：
0 1 2 3 4 5 6 7 8 9 10
A B C D E F G
下列有关该二叉树的说法正确的是(　　)
A.该树中共有4个叶子节点
B.该树是完全二叉树，其深度为4
C.该树的中序遍历为B－F－D－G－A－C－E
D.该二叉树的结构图为(如图所示)
4.某二叉树的树形结构如图所示，其前序遍历结果为BADCFGE，则字符“G”所在的位置为(　　)
A.① B.②
C.③ D.④
5.创建一个容量为3的队列，元素2，3，5，1，3，5，2依次等待入队。入队规则为：
①若当前待入队元素已经在队列中，则跳过该元素，否则转②
②若当前队列已满，将队首元素出队列，否则转③
③将当前待入队元素入队列
操作完成后，队列中的元素为(　　)
A.2，3，5，1 B.1，2，3，5
C.2，3，5 D.5，1，2
6.某种特殊的队列Q，支持以下3个操作：操作Q1，若队列非空，队首元素出队，并输出；操作Q2，若队列非空，队首元素出队；操作Q3，一个元素入队；以上任意一种操作后，若队列非空，新的队首元素仍为队列中所有元素的最小值。若队列Q初始状态为空，依次进行Q3、Q2、Q1、Q2、Q3、Q1、Q3七次操作后，下列说法正确的是(　　)
A.当前队列中的元素个数为2
B.输出的元素个数为2
C.第一个输出的元素肯定比当前队首元素大
D.队列初始状态是否为空对输出结果有影响
7.用“除二取余”法将十进制转换为二进制数，用栈的方法操作，需要把得到的余数依次入栈，除尽后再把余数出栈即可。若要将十进制数n(0≤n<64)转换为二进制数，则设置栈的长度至少为(　　)
A.3 B.4
C.5 D.6
8.用I表示进栈操作，O表示出栈操作，若元素进栈的顺序为PQRST，为了得到PSRTQ的出栈顺序，则由I和O表示的操作串是(　　)
A.IOIIIOOIOO B.IOIIOIOOIO
C.IIIIOOIOOO D.IOIIIIOOOO
9.有一个空栈，若元素“P”、“y”、“t”、“h”、“o”、“n”依次入栈，其中“o”第一个出栈。则当所有元素全部出栈后，下列说法正确的是(　　)
A.出栈的最后一个元素一定为“P”
B.出栈的最后一个元素一定为“n”
C.元素“h”一定比“P”、“y”、“t”先出栈
D.元素“P”、“y”、“t”、“h”、“o”的出栈序列是不确定的
10.有如下Python程序段：
a＝[3，6，10，5，9，4]
q＝[0]*len(a)
k＝int(input(″输入k的值：″))
head＝tail＝0
s＝ans＝0
for i in a：
q[tail]＝i
tail＝tail＋1
s＋＝i
if ansans＝s
while ik：
s－＝q[head]
head＝head＋1
执行该程序段后，输入k的值为2，变量ans的值是(　　)
A.18 B.19
C.21 D.22
11.有如下Python程序段：
a＝[2，1，5，7，3]
n＝len(a)
s1＝[－1]*n；top1＝－1
s2＝[－1]*n；top2＝－1
for i in range(n)：
while top1！＝－1 and a[i]top2＋＝1；s2[top2]＝s1[top1]；top1－＝1
top1＋＝1；s1[top1]＝a[i]
while top2！＝－1：
top1＋＝1；s1[top1]＝s2[top2]；top2－＝1
运行该程序段后，下列表达式不成立的是(　　)
A.top1＝＝5 B.top2＝＝－1
C.s1[0]＝＝1 D.s1[3]＝＝2
12.有如下Python程序段：
sz＝[″94″，″98″，″156″，″80″，″87″，″178″]
dt＝[0，1，0，1，0，0]
st＝[]；top＝0
st.append(top)
for i in range(1，len(sz))：
flag＝False
while len(st)>0 and dt[st[top]]＝＝1 and dt[i]＝＝0：
if sz[st[top]]　　　 　st.pop()
　　　 　top＝top－1
else：
　　　 　flag＝True；break
if not flag：
top＋＝1
st.append(i)
执行该程序段后，st中的元素个数为(　　)
A.6 B.2
C.4 D.3
二、非选择题(本大题共3小题，其中第13小题7分，第14小题10分，第15小题9分，共26分)
13.给定一个只包括'('，')'，'{'，'}'，'['，']'的字符串s，判断字符串是否有效。有效字符串需满足：左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。
程序运行的结果如图所示：
(1)实现上述功能的Python程序如下，请在划线处填入合适的代码。
dic＝{″(″：″)″，″[″：″]″，″{″：″}″}
s＝input(″输入的字符串是：″)
st＝[″″]*len(s)
top＝－1
dic1＝{}
for i in dic：
dic1[dic[i]]＝i
flag＝True
for i in s：
if ①________：
top＋＝1
st[top]＝i
if i in dic1：
if top＝＝－1 or ②________：
flag＝False
　　　　 break
else：
　　　 　③________
if ：
print(″字符串有效！″)
else：
print(″字符串无效！″)
(2)加框处的代码有错，请改正。
14.一批集装箱陆续送达码头，要求叠放到指定的若干位置，每个位置最多可叠放5个集装箱，且轻的在上，重的在下。工作人员根据每个送达的集装箱的重量，利用临时位置经过最少的移动次数放到合适的位置，若移动次数相同，优先选择编号小的位置(临时位置不考虑集装箱重量大小关系)。
例如：共有8个集装箱，要求叠放到2个位置。已依次送达6号、2号、3号、5号，叠放情况如图a所示。
新送达的集装箱为7号，重量为28。
·若叠放到位置0，需要移动3次：①2号→临时位置②7号→位置0③2号→位置0
·若叠放到位置1，需要移动5次：①5号→临时位置②3号→临时位置③7号→位置1④3号→位置1⑤5号→位置1
叠放到位置0的移动次数<叠放到位置1的移动次数，所以叠放到位置0。
编写Python程序实现上述功能，请回答下列问题：
已送达集装箱信息： {6：29，2：18，3：20，5：19} 当前集装箱叠放情况： 位置0：[6，2] 位置1：[3，5] 请输入到达的集装箱编号：7 请输入到达的集装箱重量：28 移动过程为： 2→临时位置 7→位置0 2→位置0 叠放结果： 位置0：[6，7，2] 位置1：[3，5]
图b
(1)函数judge(x，st)的功能是：返回x号集装箱放入某位置时需移动的次数。列表st存储了该位置从下到上已叠放的集装箱编号。请在划线处填入合适的代码。
#goods存储了已送达集装箱的信息，如：{6：29，2：18，3：20，5：19}。
def judge(x，st)：
if len(st)＝＝5：
return－1
cnt＝0
i＝len(st)－1
while i>＝0 and____________：
cnt＋＝1
i－＝1
return cnt*2＋1
(2)当某个集装箱送达时，输入其编号和重量，将该集装箱放到移动次数最少的位置，并输出移动过程。程序执行结果的部分截图如图b所示。请在划线处填入合适的代码。
goods＝{}
n＝8
k＝(n－1)//5＋1
p＝[[]for i in range(k)]
for i in range(n)：
#输出当前集装箱叠放情况，代码略
x＝int(input('请输入到达的集装箱编号：'))
weight＝int(input('请输入到达的集装箱重量：'))
goods[x]＝weight
min_steps＝999
for j in range(k)：
t＝judge(x，p[j])
if ①________：
　 　　　minp＝j
　　 　　min_steps＝t
print('移动过程为：')
tmp＝[]
for j in range(②________)：
print(p[minp][－1]，'→临时位置')
tmp.append(p[minp].pop())　#删除p[minp]的最后一个元素，并追加到tmp
p[minp].append(x)
print(x，'→'，'位置'＋str(minp))
while ③________：
print(tmp[－1]，'→'，'位置'＋str(minp))
p[minp].append(tmp.pop())
#输出叠放结果，代码略
(3)若送达的集装箱编号和重量依次为4：20，2：18，1：23，3：20，7：28，6：29，0：17，5：19，根据要求叠放到位置0和位置1，则位置1从下往上叠放的集装箱编号依次为________。
15.某餐厅餐桌设置如下表：
餐桌型号 2人小桌 4人方桌 6人大方桌 12人大圆桌
餐桌数量 8 15 10 4
平均就餐时间(分钟) 25 45 60 80
有客人来就餐时其叫号系统会自动生成一个号码，并根据人数安排餐桌型号；当对应餐桌型号有空桌时，按餐桌编号(由小到大)即时分配餐桌安排客人就餐；当对应餐桌型号没有空桌时，客人按先后顺序排队。程序部分运行界面如下：
(1)定义如下gettype函数，功能为输入客人人数，返回对应桌型，请在程序划线处填入合适代码。
def gettype(num)：
type＝－1
for i in range(len(size))：
if num<＝size[i]：
　　　 　type＝i
　　　 　__________
return type
(2)定义如下checktable()函数，功能为输入桌型，返回对应桌型空桌的编号，返回值类型为列表，请在程序划线处填入合适代码。
def checktable(n)：
ans＝[]
for i in range(nums[n])：
if____________：
　　 　　ans.append(i)
return ans
(3)解决上述问题的主程序如下，请在程序划线处填入合适代码。
size＝[2，4，6，12]　#每种桌型最大就餐人数
nums＝[8，15，10，4]　#每种桌型的餐桌数量
times＝[25，45，60，80]　#每种桌型平均就餐时间
flags＝[[True]*nums[i] for i in range(4)]　
#标记每张桌子的初始状态
s_time＝10*60*60　#开始营业时间——10点整，转化为秒
e_time＝14*60*60　#结束营业时间——14点整，转化为秒
maxn＝50　#假设队列已经足够深
qc＝[[0]*maxn for i in range(4)]　#循环队列
now_time＝s_time
id＝0
head，tail＝[0]*4，[0]*4
while now_timenumber＝getinfo()　#调用函数getinfo()，获取客人人数
if number>0：
id＋＝1
type＝gettype(number)#根据就餐人数确定餐桌类型
if type！＝－1：
　　　 　qc[type][tail[type]]＝id
　　　 　tail[type]＝(tail[type]＋1)%maxn
　　　 　qc_len＝①________
　　　 　print(id，″号客人，给您安排的是″，size[type]，″人桌，前面还有″，qc_len－1，″人在等位″)
else：
　　 　　print(id，″号客人，非常抱歉，没有适合您的桌型！″)
for i in range(4)：
tables＝checktable(i)
if ②________：
　　　 　flags[i][tables[0]]＝False　#入座第一个空桌
　　　 　print(qc[i][head[i]]，″号客人请用餐→″，size[i]，″人桌″，tables[0]，″号″)
　　 　　head[i]＝(head[i]＋1)%maxn
now_time＋＝1
#更新每张餐桌的就餐情况，代码略
第六单元　数据结构
1.C　[本题考查树的性质。A选项二叉树的最大度为2，因此树的度也是2。B选项总节点数10介于7和15之间，因此该树层数为4。C选项由于是满二叉树，因此前3层为完全二叉树，前3层共有7节点，最后一层有3个节点。D选项由于最后一层有3个节点，因此该层的父亲节点有2个，第3层共有4个节点，因此第3层还有2个叶子节点。]
2.A　[本题考查二叉树的遍历。根据前序遍历和中序遍历的规则画出二叉树，前序遍历的第一个元素“A”为根节点，树分为(BC)A(DEF)。“BC”确定节点B为根节点，C是右子树。“DEF”中，节点D为根节点，“EF”是节点“D”的右子树。“EF”中E为根节点，F是右子树。得到后序遍历结果为CBFEDA。]
3.C　[本题考查二叉树的基本知识。第3层节点的索引号为3，4，5，可见B没有左子树，但有右子树，因此不可能是满二叉树，B也不是叶子节点。二叉树形态如图所示。]
4.C　[前序遍历是根左右，F为根，G在F的后面，因此G为F的右子树。]
5.D　[本题考查队列结构及其操作，各数据入队时状态如图所示。]
6.D　[操作Q3、Q2之后，队列为空。Q3、Q1，队列为空。因此队列中元素个数为1，Q1操作出队并输出元素，输出的元素个数为1。C选项没有可比性。D选项若队列不为空，则Q3、Q2、Q1、Q2输出的结果不一样。]
7.D　[十进制数n(0≤n＜64)转换为二进制数，得到最大的是6位二进制数。]
8.A　[本题考查栈的操作。P入后马上出，QRS入，SR出，栈中只有Q，T入后马上出，Q再出。]
9.C　[本题考查栈的性质。o出栈时，n还没有入栈，因此n可能是最后一个出栈，也可能在其他元素出栈过程中，入栈后再出栈。o出栈时，P，y，t，h均已在栈中，故元素出栈序列是确定的。]
10.C　[遍历数组a并累加数组元素值，求队列的最大值；当遍历到的当前值小于队首或是长度大于k，将队首元素出队。s的值依次为[3，6，10]＝19，[6，10，5]＝21，[5，9]＝14，[5，9，4]＝18。]
11.A　[本题考查栈的基本应用。遍历列表a中数据，若栈s1不空，且s1栈顶元素大于等于a[i]时，不断地将s1中元素出栈，并入栈s2中，将a[i]入栈s1。因此栈s1中元素有1，3，栈s2中有元素[2，7，5]，最后将栈s2中元素出栈并加入到栈s1中，因此栈s1中最终结果为[1，3，5，7，2]。]
12.B　[本题考查数组的索引和栈的算法实现。st.pop()表示出栈，st.append(i)表示元素i入栈，st[top]是栈顶元素。栈中存储的元素的编号，一开始栈中有一个元素，″94″对应的下标0入栈。对sz的第2个元素开始遍历。dt[1]＝＝1，没有出栈动作，″98″下标1入栈；条件满足，但是″156″不比栈顶元素″98″大，flag＝True，″156″下标2不会入栈；dt[3]＝＝1，没有出栈动作，″80″下标3入栈；接下来条件满足，″87″比栈顶元素″80″大，″80″对应的下标3出栈，接下来的栈顶元素是″98″，flag＝True，没有入栈动作；最后栈中只有[0，5]共2个元素。]
13.(1)①i in dic　②i！＝dic[st[top]]　③top－＝1 (2)flag and top＝＝－1
解析　本题考查栈的操作。(1)①如果是括号的左半部分，则入栈，否则出栈。②出栈前判断栈是否为空，为空，说明右半部分先出现，顺序不对。若不为空，在字典dic中查找栈顶元素对应的右半分部，如果不相等，说明中间的顺序不对。③如果相等，出栈。(2)除了flag的值外，还要判断左半部分是否比右半部分多，即栈是否为空。
14.(1)goods[x]>goods[st[i]]　(2)①t！＝－1 and t0 或 tmp
(3)6，1，3，5
解析　本题考查栈的应用。插入元素后，维护栈底到栈顶的降序排列。(1)judge函数计算将goods[x]插入到栈st需要移动元素的操作次数。参数x是集装箱编号，即字典goods的键，因此在访问栈顶元素时goods[st[i]]与goods[x]比较为非直接与x比较。(2)从k个位置选择移动次数最少的栈并插入元素。第①空获取当前栈p[j]插入编号为x的元素所需的移动次数与全局最小次数min_steps比较并更新min_steps。若栈已满将无法插入数据。第②空输出移动的过程。先将栈p[minp]大于goods[x]的元素暂存到临时栈中，这里需出栈的元素个数恰为min_steps//2。第③空将临时栈中的全部元素重新压入栈p[minp]中，因此len(tmp)>0时均需要执行入栈。(3)编号4、2依次在位置0入栈；3、7依次在位置1入栈；随后7插入到位置0的栈底、6插入到位置1栈底；最后0入栈位置0，5入栈位置1，从下到上的编号依次为：6 1 3 5。
15.(1)break　(2)flags[n][i]＝＝True　(3)①(tail[type]－head[type]＋maxn)%maxn　②len(tables)>0 and head[i]！＝tail[i]或tables and head[i]！＝tail[i]
解析　本题考查循环队列的基本应用。(1)gettype函数功能为输入客人人数，返回对应桌型。size数组存储每种桌型最大就餐人数，从小桌开始枚举，找到相应的规格就结束查找。(2)checktable函数功能找到对应桌型的空桌编号。nums每种桌型的餐桌数量，flags二维数组标记每种桌型每张桌子的初始状态，n为桌型编号，nums[n]表示该种桌型中最多就餐桌位，在flags[n]列表中从头开始(循环变量i从0至nums[n]－1中枚举)查找值为True(空桌)的编号，并将这些编号添加到列表ans中，因此答案为flag[n][j]＝＝True。(3)①求队列长度，qc存储循环列表的信息，type表示餐桌类型，qc[type]就是存储该类型的循环列表，循环队列长度公式(tail－head＋maxn)%maxn，因此①答案为(tail[type]－head[type]＋maxn)%maxn。②输出安排就餐情况。变量i表示每种桌型，安排座位的条件有两个，一是这种桌型有客人来，即qc[i]队列不为空；二是这种桌型有空位，tables调用checktable(i)函数，获取空位列表。

展开更多......

收起↑