第三章 线性数据的组织和存储 2024-2025学年高中信息技术粤教版（2019）选修1

第三章 线性数据的组织和存储2024—2025学年高中信息技术粤教版（2019）选修1

 

一、选择题

1．假设队列的空间足够，队首指针head和队尾指针tail经过“出队、入队、出队、出队、入队、入队、出队”这一系列操作后，head=7，tail=9。则操作前的head和tail的值分别为（   ）

A．11  12 B．2  5 C．3  6 D．3  5

2．一个序列的入栈顺序为 a，b，c，d，e，则该序列的出栈顺序不可能为（ ）

A．b，a，d，c，e B．d，c，b，a，e C．d，c，e，a，b D．c，b，a，e，d

3．队列的特点（   ）

A．先进先出 B．先进后出 C．插入操作只能在队头进行 D．删除操作只能在队尾进行

4．向一个栈顶指针为head的链式栈中插入一个指针r指向的节点时（节点指针域为next），则应执行的操作是（   ）

A．head.next=r B．r.next=head;head=r

C．r.next=head.next;head.next=r D．r.next=head;head=head.next

5．用 I 表示进栈操作，O 表示出栈操作，若元素进栈的顺序为 PQRST，为了得到 PSRTQ 的出栈顺序，则由 I 和 O 表示的操作串是

A．IOIIIOOIOO B．IOIIOIOOIO C．IIIIOOIOOO D．IOIIIIOOOO

6．队列Q和栈S的初始值均为空，数字入栈先后顺序为1、2、3、4、5。P表示入栈，T表示元素出栈以后入队。在进行PPTTPPTPT操作后，队列中从队首到队尾的元素依次为（   ）

A．2、1、3、4 B．2、1、4、5 C．1、2、4、5 D．2、1、4、3

7．若用1表示进栈操作，用0表示出栈操作，若元素的进栈顺序是“q，w，e，r，t”，为了得到出栈序列“ewrtq”，则应进行的操作序列为(　　)

A．1101010100 B．1110010100 C．1110011000 D．1110100100

8．下列关于队列和栈的说法，不正确的是（   ）

A．队列是一种先进先出的线性表，可在队尾进行插入操作

B．栈的特性是″先进后出，后进先出″

C．某栈的入栈的顺序为″abc″，出栈顺序只有3种

D．队列和栈都是线性数据结构，都可以用数组来实现

9．下列关于栈的说法，不正确的是（   ）

A．只允许对栈顶元素进行插入和删除操作 B．数据入栈、出栈顺序为先进后出

C．不可以根据位置访问栈中元素 D．栈的特性和队列的特性相仿

10．有如下python程序段，执行该程序段后，输出结果不可能的是（   ）

import random as rd

st=[1]*10;top=0

for i in range(5):

    num=rd.randint(1,6)

    if num>=st[top]:

        top+=1;st[top]=num

    elif num%2==0:

        top-=1

while top>=0:

    print(st[top],end="");top-=1

A．6 3 3 1 1 1 B．1 C．4 2 2 D．6 6 6 1

11．已知栈st中从栈底到栈顶的元素依次为a、b、c，元素d正等待进栈，以下出栈序列不可能的是（   ）

A．c,b,d,a B．c,d,a,b C．c,d,b,a D．c,b,a,d

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．有1个栈初始为空，其元素入栈顺序依次为a，b，c，d，e，f，g，经若干次入栈和出栈操作后，栈底至栈顶元素分别为b，d，f，则第3个出栈元素为（    ）

A．g B．c C．e D．a

14．有一个栈，栈底到栈顶的元素依次为 c,a,b,g,e,f。已经出栈的元素可以重新入栈（不考

虑入栈顺序）。经过5次出栈、5次入栈后，栈中的元素不可能为（   ）

A．a,b,c,e,f,g B．c,b,a,g,f,e C．c,a,b,g,e,f D．c,a,g,b,f,e

15．有如下程序段：

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

16．有如下Python程序段：

a="Python"；q=[0]*6

head,tail=0,0

i=len（a）-1

while i>=0:

if i%3!=0:

q[tail]=a[i]

else:

q[tail]=q[head]

head+=1

tail+=1

i-=1