[数据结构与算法]《数据结构与算法》线性结构复习题

1、判断题

1-1 通过对堆栈S操作：Push(S,1), Push(S,2), Pop(S), Push(S,3), Pop(S), Pop(S)。输出的序列为：123。 (1分)
F

1-2 若一个栈的输入序列为1，2，3，…，$N$，输出序列的第一个元素是 $i$，则第 $j$个输出元素是$j?i?1$ 。 (1分)
F

1-3 若一个栈的输入序列为{1, 2, 3, 4, 5}，则不可能得到{3, 4, 1, 2, 5}这样的出栈序列。 (1分)
T

1-4 栈顶元素和栈底元素有可能是同一个元素。 (1分)
T

1-5 在具有 个结点的单链表中，访问结点和增加结点的时间复杂度分别对应为$O(1)$和$O(N)$ 。 (1分)
F

1-6 线性表L如果需要频繁地进行不同下标元素的插入、删除操作，此时选择顺序存储结构更好。 (1分)
F

1-7 In a singly linked list of $N$ nodes, the time complexities for query and insertion are $O(1)$ and $O(N)$ ,respectively. (1分)
（翻译：在单链表的N个节点中，查询和插入的时间复杂度分别为$O(1)$和$O(n)$。）
F

1-8 If $N$ numbers are stored in a singly linked list in increasing order, then the average time complexity for binary search is $O(logN)$. (1分)
（翻译：如果N个数按递增顺序存储在单链表中，则二分查找的平均时间复杂度为$O(logN)$。1-10）
F

1-9 若用链表来表示一个线性表，则表中元素的地址一定是连续的。 (1分)
F

1-10 将$N$个数据按照从小到大顺序组织存放在一个单向链表中。如果采用二分查找，那么查找的平均时间复杂度是$O(logN)$。(1分)
F

1-11 将长度分别为m,n的两个单链表合并为一个单链表的时间复杂度为$O(m+n)$。 (1分)
F

1-12 在单链表中，要访问某个结点，只要知道该结点的指针即可。因此，单链表是一种随机存取结构。 (1分)
F

1-13 链表 - 存储结构
链表中逻辑上相邻的元素，其物理位置也一定相邻。 (1分)
F

1-14 链表是采用链式存储结构的线性表,进行插入、删除操作时，在链表中比在顺序存储结构中效率高。 (1分)
T

1-15 算法分析的两个主要方面是时间复杂度和空间复杂度的分析。 (1分)
T

1-16 对于某些算法，随着问题规模的扩大，所花的时间不一定单调增加。 (1分)
T

1-17 线性表的插入、删除总是伴随着大量数据的移动。 (1分)
F

1-18 算法可以没有输入，但是必须有输出。 (1分)
T

2、单选题

2-1 若元素a、b、c、d、e、f依次进栈，允许进栈、退栈操作交替进行，但不允许连续三次进行退栈工作，则不可能得到的出栈序列是？(2分)
A. b c a e f d
B. c b d a e f
C. d c e b f a
D. a f e d c b

2-2 有六个元素以6、5、4、3、2、1的顺序进栈，问哪个不是合法的出栈序列？ (2分)
A. 2 3 4 1 5 6
B. 3 4 6 5 2 1
C. 5 4 3 6 1 2
D. 4 5 3 1 2 6

2-3 若一个栈的入栈序列为1、2、3、…、$N$，输出序列的第一个元素是$i$，则第$j$个输出元素是： (2分)
A.$i?j?1$
B.$i?j$
C.$j?i?1$
D. 无法确定

2-4 将5个字母ooops按此顺序入栈，则有多少种不同的出栈顺序可以仍然得到ooops？ (2分)
A. 1
B. 3
C. 5
D. 6

2-5 设一个堆栈的入栈顺序是1、2、3、4、5。若第一个出栈的元素是4，则最后一个出栈的元素必定是： (2分)
A. 1
B. 3
C. 5
D. 1或者5

2-6 给定一个堆栈的入栈序列为{ 1, 2,··· ,$n$ }，出栈序列为{$p1,p2,???,pn$}。如果$p2=n$，则存在多少种不同的出栈序列？(2分)
A. 1
B. 2
C.$n?1$
D.$n$

2-7 以下不是栈的基本运算的是( )。 (2分)
A. 删除栈顶元素
B. 删除栈底元素
C. 判断栈是否为空
D. 将栈置为空栈

2-8 一个递归的定义可以用递归过程求解，也可以用非递归过程求解，但单从运行时间来看， 通常递归过程比非递归过程（ ）。(2分)
A. 较快
B. 较慢
C. 相同
D. 无法确定

2-9 设顺序栈的栈顶指针（int 类型）指向栈顶元素位置，则判断一个栈ST（最多元素为MaxSize）为栈满的条件是（）。(2分)
A. ST.top != -1
B. ST.top == -1
C. ST.top != MaxSize - 1
D. ST.top == MaxSize - 1

2-10 假设一个栈的输入序列是1，2，3，4，则不可能得到的输出序列是（ ）。 (2分)
A. 1,2,3,4
B. 4,1,2,3
C. 4,3,2,1
D. 1,3,4,2

2-11 设一个堆栈的入栈顺序是1、2、3、4、5。若第一个出栈的元素是4，则最后一个出栈的元素必定是____。 (2分)
A. 1
B. 3
C. 5
D. 1或者5

2-12 为解决计算机主机与打印机之间速度不匹配问题，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是？(2分)
A. 堆栈
B. 队列
C. 树
D. 图

2-13 某队列允许在其两端进行入队操作，但仅允许在一端进行出队操作。若元素a、b、c、d、e依次入此队列后再进行出队操作，则不可能得到的出队序列是：(2分)
A. b a c d e
B. d b a c e
C. e c b a d
D. d b c a e

2-14 现有队列 Q 与栈 S，初始时 Q 中的元素依次是{ 1, 2, 3, 4, 5, 6 }（1在队头），S 为空。若允许下列3种操作：
（1）出队并输出出队元素；（2）出队并将出队元素入栈；（3）出栈并输出出栈元素，则不能得到的输出序列是：(2分)
A. 1, 2, 5, 6, 4, 3
B. 2, 3, 4, 5, 6, 1
C. 3, 4, 5, 6, 1, 2
D. 6, 5, 4, 3, 2, 1

2-15 设一数列的顺序为1，2，3，4，5，6，通过队列操作可以得到（ ）的输出序列。 (2分)
A. 3,2,5,6,4,1
B. 1,2,3,4,5,6
C. 6,5,4,3,2,1
D. 4,5,3,2,6,1

2-16 关于栈和队列的下列说法正确的是（） (2分)
A. 栈的插入操作是在栈顶进行，插入时需将栈内所有元素后移；
B. 栈是后进先出的结构，出栈时除了栈顶元素，其余元素无需移动；
C. 循环队列的出队操作删除的是队头元素，采用循环队列存储时，其余队列元素均需要移动；
D. 链队列的入队操作在表尾进行，操作时间与队列长度成正比

2-17 设栈S和队列Q的初始状态均为空，元素a、b、c、d、e、f、g依次进入栈S。若每个元素出栈后立即进入队列
Q，且7个元素出队的顺序是b、d、c、f、e、a、g，则栈S的容量至少是：
(2分)
A. 1
B. 2
C. 3
D. 4

2-18 设栈S和队列Q的初始状态均为空，元素{1, 2, 3, 4, 5, 6, 7}依次进入栈S。若每个元素出栈后立即进入队列Q，
且7个元素出队的顺序是{2, 5, 6, 4, 7, 3, 1}，则栈S的容量至少是：
(2分)
A. 1
B. 2
C. 3
D. 4

2-19 下列属于线性数据结构的是( )。 (2分)
A. 队列
B. 树
C. 图
D. 二叉树

2-20 队列的“先进先出”特性是指（　）。
Ⅰ.最后插入队列中的元素总是最后被删除
Ⅱ.当同时进行插入、删除操作时，总是插入操作优先
Ⅲ.每当有删除操作时，总要先做一次插入操作
Ⅳ.每次从队列中删除的总是最早插入的元素
(2分)
A. Ⅰ
B. Ⅰ、Ⅳ
C. Ⅱ、Ⅲ
D. Ⅳ

2-21 一个队列的入队序列是1，2，3，4，则队列的输出序列是( ) 。 (2分)
A. 4，3，2，1
B. 1，2，3，4
C. 1，4，3，2
D. 3，2，4，1

2-22 已知初始为空的队列 Q 的一端仅能进行入队操作，另外一端既能进行入队操作又能进行出队操作。若 Q 的入
队序列是 1、2、3、4、5，则不能得到的出队序列是：
(2分)
A. 5、4、3、1、2
B. 5、3、1、2、4
C. 4、2、1、3、5
D. 4、1、3、2、5

2-23 栈和队列的共同点是( ) (2分)
A. 都是先进后出
B. 都是后进先出
C. 只允许在端点处插入和删除元素
D. 没有共同点

2-24 已知队列(13，2，11，34，4l，77，5，7，18，26，15)，第一个进入队列的元素是13，则第五个出队列的
元素是( )。
(2分)
A. 41
B. 5
C. 77
D. 13

2-25 线性表若采用链式存储结构时，要求内存中可用存储单元的地址 (2分)
A. 必须是连续的
B. 连续或不连续都可以
C. 部分地址必须是连续的
D. 一定是不连续的

2-26 在具有$N$个结点的单链表中，实现下列哪个操作，其算法的时间复杂度是 $O(N)$？ (2分)
A. 在地址为 $p$ 的结点之后插入一个结点
B. 删除开始结点
C. 遍历链表和求链表的第 $i$ 个结点
D. 删除地址为 $p$ 的结点的后继结点

2-27 线性表L在什么情况下适用于使用链式结构实现？ (2分)
A. 需不断对L进行删除插入
B. 需经常修改L中的结点值
C. L中含有大量的结点
D. L中结点结构复杂

2-28 链表不具有的特点是： (2分)
A. 插入、删除不需要移动元素
B. 方便随机访问任一元素
C. 不必事先估计存储空间
D. 所需空间与线性长度成正比

2-29 The following table shows how a linked list is stored in memory space with the head node c :

（翻译：下表显示了链表如何与头部节点c一起存储在内存空间中：）

Now f is stored at 1014H and is inserted into the linked list between a and e . Then the “Link” fields of a , e , and f are __, respectively.

（翻译：现在 f 存储在1014H，并插入到a和e之间的链表中。然后，a、e和f的“Link”字段分别为__。）
A. 1010H , 1014H , 1004H
B. 1010H , 1004H , 1014H
C. 1014H , 1010H , 1004H
D. 1014H , 1004H , 1010H

2-30 在单链表中，要删除某一指定结点，必须先找到该结点的（）。 (2分)
A. 直接前驱
B. 自身位置
C. 直接后继
D. 直接后继的后继

2-31 以下关于链式存储结构的叙述中，（）是不正确的。 (2分)
A. 结点除自身信息外还包括指针域，因此存储密度小于顺序存储结构
B. 逻辑上相邻的结点物理上不必邻接
C. 可以通过计算直接确定第i个结点的存储地址
D. 插入、删除运算操作方便，不必移动结点

2-32 对于一个具有 $N$ 个结点的单链表，在给定值为 的结点后插入一个新结点的时间复杂度为 (2分)
A.$O(1)$
B.$O(N/2)$
C.$O(N)$
D.$O(N^2)$

2-33 带头结点的单链表h为空的判定条件是： (2分)
A. h == NULL;
B. h->next == NULL;
C. h->next == h;
D. h != NULL;

2-34 链表 - 存储密度
链表的存储密度 ▁▁▁▁▁ 。
(2分)
A. 大于 1
B. 等于 1
C. 小于 1
D. 不能确定

2-35 在数据结构中，从逻辑上可以把数据结构分成（）。 (2分)
A. 动态结构和静态结构
B. 紧凑结构和非紧凑结构
C. 线性结构和非线性结构
D. 内部结构和外部结构

3、编程题

7-1 括号匹配 (10分)

给定一串字符，不超过100个字符，可能包括括号、数字、字母、标点符号、空格，编程检查这一串字符中的( ) ,[ ],{}是否匹配。
输入格式:
输入在一行中给出一行字符串，不超过100个字符，可能包括括号、数字、字母、标点符号、空格。
输出格式:
如果括号配对，输出yes，否则输出no。
输入样例1:sin(10+20)
输出样例1:yes
输入样例2:{[}]
输出样例2:no
编译器 PYTHON3

代码

# 用列表实现栈,创建一个栈，判断栈是否为空，入栈，出栈，取栈顶元素，求栈的大小
class Stack:
    # 1.构造方法，用列表模拟栈
    def __init__(self):
        self.items = []

    # 2.判断栈是否为空
    def isEmpty(self):
        return self.items == []

    # 3.入栈
    def push(self, item):
        self.items.append(item)

    # 4.出栈
    def pop(self):
        return self.items.pop()

    # 5.取栈顶元素
    def peek(self):
        return self.items[-1]

    # 6.求栈的大小
    def getSize(self):
        return len(self.items)


s = Stack()  # 初始化栈
mp = dict(zip('([{', ')]}'))  # 括号匹配字典
str = input()  # 输入串str
f = True
for c in str:  # 遍历字符串
    if c in '([{':  # 左括号入栈
        s.push(c)
    elif c in ')]}':  # 右括号出栈
        if s.isEmpty():  # 栈为空，匹配失败
            f = False
            break
        x = s.pop()  # 出栈
        if mp[x] != c:  # 匹配失败
            f = False
            break
if s.isEmpty() and f:  # 栈为空并且匹配成功
    print("yes")
else:
    print("no")

7-2 堆栈操作合法性 (10分)

假设以S和X分别表示入栈和出栈操作。如果根据一个仅由S和X构成的序列，对一个空堆栈进行操作，相应操作均可
行（如没有出现删除时栈空）且最后状态也是栈空，则称该序列是合法的堆栈操作序列。请编写程序，输入S和X序
列，判断该序列是否合法。
输入格式:
输入第一行给出两个正整数$N$和$M$，其中N是待测序列的个数，$M(<=50)$是堆栈的最大容量。随后$N$行，每行中给
出一个仅由S和X构成的序列。序列保证不为空，且长度不超过100。
输出格式:
对每个序列，在一行中输出YES如果该序列是合法的堆栈操作序列，或NO如果不是。
输入样例：

4 10
SSSXXSXXSX
SSSXXSXXS
SSSSSSSSSSXSSXXXXXXXXXXX
SSSXXSXXX

输出样例：

YES
NO
NO
NO

编译器 PYTHON3

代码

# 用列表实现栈,创建一个栈，判断栈是否为空，入栈，出栈，取栈顶元素，求栈的大小
class Stack:
    # 1.构造方法，用列表模拟栈
    def __init__(self):

        self.items = []

    # 2.判断栈是否为空
    def isEmpty(self):

        return self.items == []

    # 3.入栈
    def push(self, item):

        self.items.append(item)

    # 4.出栈
    def pop(self):

        return self.items.pop()

    # 5.取栈顶元素
    def peek(self):

        return self.items[-1]

    # 6.求栈的大小
    def getSize(self):

        return len(self.items)


# 判断字符串str在栈容量为m的操作是否合法
def isValid(str, m):
    s = Stack()  # 初始化栈
    n = 0  # 入栈字符个数
    for c in str:
        if c == 'S':  # 入栈
            s.push(c)
            n += 1
            if n > m:  # 超出栈容量
                return False
        else:  # 出栈
            if s.isEmpty():
                return False
            s.pop()
            n -= 1
    return s.isEmpty()
n, m = map(int, input().split())
for i in range(n):
    s = input()
    print("YES" if isValid(s, m) else "NO")

7-3 表达式转换 (10分)

算术表达式有前缀表示法、中缀表示法和后缀表示法等形式。日常使用的算术表达式是采用中缀表示法，即二元运算
符位于两个运算数中间。请设计程序将中缀表达式转换为后缀表达式。
输入格式:
输入在一行中给出不含空格的中缀表达式，可包含+、-、*、\以及左右括号()，表达式不超过20个字符。
输出格式:
在一行中输出转换后的后缀表达式，要求不同对象（运算数、运算符号）之间以空格分隔，但结尾不得有多余空格。
输入样例:2+3*(7-4)+8/4
输出样例:2 3 7 4 - * + 8 4 / +
编译器 PYTHON3

代码

# 用列表实现栈,创建一个栈，判断栈是否为空，入栈，出栈，取栈顶元素，求栈的大小
class Stack:
    # 1.构造方法，用列表模拟栈
    def __init__(self):
        self.items = []

    # 2.判断栈是否为空
    def isEmpty(self):
        return self.items == []

    # 3.入栈
    def push(self, item):
        self.items.append(item)

    # 4.出栈
    def pop(self):
        return self.items.pop()

    # 5.取栈顶元素
    def peek(self):
        return self.items[-1]

    # 6.求栈的大小
    def getSize(self):
        return len(self.items)


# 中缀表达式转后缀表达式
def in2post(infix):
    res = []  # 后缀列表
    opStack = Stack()  # 运算符栈
    # 优先级字典
    pre = {"(": 1, "+": 2, "-": 2, "*": 3, "/": 3};
    f = 1
    # 遍历中缀表达式列表,4种情况(,),运算符，操作数
    while infix:
        c = infix[0]
        if c == '(':  # 左括号入栈
            opStack.push(c)
            if infix[1] == '-':  # 符号位
                f = -1
                infix = infix[1:]
            elif infix[1] == '+':  # 可能为首的操作数前面会有一个‘+’号,若是则直接跳过
                infix = infix[1:]
        elif c == ')':  # 右括号出栈
            while True:
                tmp = opStack.pop()
                if tmp == "(":
                    break
                res.append(tmp)
        elif c in "+-*/":
            # 栈顶运算符的优先级大于等于当前运算符c的优先级就出栈
            while not opStack.isEmpty() and \
                            pre[opStack.peek()] >= pre[c]:
                res.append(opStack.pop())
            opStack.push(c)
        else:  # 4.操作数，直接加入结果列表
            data = ''
            while infix and ('0' <= infix[0] <= '9' or infix[0] == '.'):
                data += infix[0]
                infix = infix[1:]
            # print(n,infix,i,j,infix[i:j])
            if f == -1:
                res.append("-" + data)
                f = 1
            else:
                res.append(data)
            continue
        infix = infix[1:]
    # 操作符栈只要非空就出栈，加入结果列表
    while not opStack.isEmpty():
        res.append(opStack.pop())
    return " ".join(res)

# print(in2post("a + b * c"))
print(in2post('(' + input() + ')'))

7-4 有关队列操作 (10分)

请实现一个MyQueue类，实现出队，入队，显示队列，求队列长度。
实现入队方法 push(int x); 实现出队方法 pop(); 实现求队列长度方法 size();实现显示队列方法：show() 。
输入格式:
每个输入包含1个测试用例。
每个测试用例第一行给出一个正整数$n(n<=10^6)$，接下去n行每行一个数字，表示一种操作： 1 x ： 表示从队尾插入x，0<=x<=2^31-1。 2 ： 表示队首元素出队。 3 ： 表示求队列长度。4：表示显示队列中所有元素。
输出格式:
对于操作1，将要添加的元素添加到队列的尾部
对于操作2，若队列为空，则输出 “Invalid”,否则请输出队首元素，并将这个元素从队列中删除。
对于操作3，请输出队列长度。 每个输出项最后换行。
对于操作4，输出队列中每个元素，元素之间用空格分隔，最后一个元素后面没有空格。
输入样例:

在这里给出一组输入。例如：
9
1 23
1 34
342
1 56
23
1 90

输出样例:

在这里给出相应的输出。例如：
2
23 34
23
34
1

编译器 PYTHON3

代码

# 定义抽象类型队列MyQueue，FIFO（First In,First Out)
class MyQueue:
    # 1.构造方法,定义一个空的列表
    def __init__(self):

        self.items = []

    # 2.入队,队尾（列表尾部）入队
    def push(self, item):

        self.items.append(item)

    # 3.出队，队首（列表头部）出队
    def pop(self):

        return self.items.pop(0)

    # 4.显示队列
    def show(self):

        ls = [str(i) for i in self.items]
        print(" ".join(ls))

    # 6.求队列大小
    def getSize(self):

        return len(self.items)


# 测试程序
n = int(input())
q = MyQueue()
# n次队列操作
for i in range(n):
    s = input().split()
    if s[0] == '1':  # 入队
        x = int(s[1])
        q.push(x)
    elif s[0] == '2':  # 出队并输出
        if q.getSize() > 0:
            print(q.pop())
        else:
            print("Invalid")
    elif s[0] == '3':  # 输出队列大小
        print(q.getSize())
    else:  # 输出队列元素
        q.show()

7-5 约瑟夫环 (10分)

有n个人围成一圈（编号为1～n），从第1号开始进行1、2、3报数，凡报3者就退出，下一个人又从1开始报数……直
到最后只剩下一个人时为止。请问此人原来的位置是多少号?
输入格式:
测试数据有多组，处理到文件尾。每组测试输入一个整数$n（5\le n\le 100）$。
输出格式:
对于每组测试，输出最后剩下那个人的编号。
输入样例:

10
28
69

输出样例:

4
23
68

编译器 PYTHON3

代码

# 定义抽象类型队列MyQueue，FIFO（First In,First Out)
class MyQueue:
    # 1.构造方法,定义一个空的列表
    def __init__(self):

        self.items = []

    # 2.入队,队尾（列表尾部）入队
    def push(self, item):

        self.items.append(item)

    # 3.出队，队首（列表头部）出队
    def pop(self):

        return self.items.pop(0)

    # 4.显示队列
    def show(self):

        ls = [str(i) for i in self.items]
        print(" ".join(ls))

    # 6.求队列大小
    def getSize(self):

        return len(self.items)


# 约瑟夫环
# ls-姓名列表，n-报数
def hotPotato(ls, n):
    # 1.定义队列
    q = MyQueue()
    # 2.入队
    for i in ls:
        q.push(i)
    # 3.队列模拟游戏过程
    while q.getSize() > 1:
        # 报数在[1,n)的出队并入队
        for i in range(1, n):
            q.push(q.pop())
        # 报数n的出队
        q.pop()
        # print(q.pop(),end = " ")
    return q.pop()


# 多组测试数据
while True:
    try:
        # 输入数据，生成姓名列表
        n = int(input())
        ls = [i for i in range(1, n + 1)]
        # print(ls)
        print(hotPotato(ls, 3))
    except:
        break

7-6 银行业务队列简单模拟 (10分)

设某银行有A、B两个业务窗口，且处理业务的速度不一样，其中A窗口处理速度是B窗口的2倍 —— 即当A窗口每处
理完2个顾客时，B窗口处理完1个顾客。给定到达银行的顾客序列，请按业务完成的顺序输出顾客序列。假定不考虑
顾客先后到达的时间间隔，并且当不同窗口同时处理完2个顾客时，A窗口顾客优先输出。
输入格式:
输入为一行正整数，其中第1个数字N( 1000)为顾客总数，后面跟着N位顾客的编号。编号为奇数的顾客需要到A窗
口办理业务，为偶数的顾客则去B窗口。数字间以空格分隔。
输出格式:
按业务处理完成的顺序输出顾客的编号。数字间以空格分隔，但最后一个编号后不能有多余的空格。
输入样例:8 2 1 3 9 4 11 13 15
输出样例:1 3 2 9 11 4 13 15
编译器 PYTHON3

代码

'''
'''
#银行业务队列简单模拟,A和B两个窗口
8 2 1 3 9 4 11 13 15
A:1 3 9 11 13 15
B:2 4
1 3 2 9 11 4 13 15
*******************************/
'''


# 定义抽象类型队列MyQueue，FIFO（First In,First Out)
class MyQueue:
    # 1.构造方法,定义一个空的列表
    def __init__(self):

        self.items = []

    # 2.入队,队尾（列表尾部）入队
    def push(self, item):

        self.items.append(item)

    # 3.出队，队首（列表头部）出队
    def pop(self):

        return self.items.pop(0)

    # 4.显示队列
    def show(self):

        ls = [str(i) for i in self.items]
        print(" ".join(ls))

    # 5.求队列大小
    def getSize(self):

        return len(self.items)

# 银行业务队列模拟
# 1.读入数据入队
ls = list(map(int, input().split()))
n = ls[0]  # n位顾客
ls = ls[1:]  # n位顾客的编号列表
qa, qb = MyQueue(), MyQueue()  # 定义2个队列
for x in ls:
    if x % 2 == 1:  # 奇数编号在A队列处理
        qa.push(x)
    else:  # 偶数编号在A队列处理
        qb.push(x)
# 出队并放入
res = []
while True:
    # A队列和B队列都为空，就结束循环
    if qa.getSize() == 0 and qb.getSize() == 0:
        break
    # A队出2个
    if qa.getSize() > 0:
        res.append(str(qa.pop()))
    if qa.getSize() > 0:
        res.append(str(qa.pop()))
    # B队出1个
    if qb.getSize() > 0:
        res.append(str(qb.pop()))
print(" ".join(res))

7-7 单链表的创建及遍历 (10分)

读入n值及n个整数，建立单链表并遍历输出。
输入格式:
读入n及n个整数。
输出格式:
输出n个整数，以空格分隔（最后一个数的后面没有空格）。
输入样例:

在这里给出一组输入。例如：
2
10 5

输出样例:

在这里给出相应的输出。例如：
10 5

编译器 PYTHON3

代码

# 结点类，包括数据域data和引用域next
class Node:
    # 1.构造方法
    def __init__(self, initData):

        self.data = initData  # 数据域
        self.next = None  # 引用域初始化为空


# 无序表unorderedList
class unorderedList:
    # 1.构造方法
    def __init__(self):

        self.head = None  # 初始化表头
        self.tail = None  # 初始化表尾

    # 2.输出链表，用->连接 26->93->17->77->31
    def print(self):

        res = []
        p = self.head  # 从表头开始
        while p != None:
            res.append(p.data)
            p = p.next  # 访问下一个结点
        return res

    # 3.尾插法添加新结点
    def add_tail(self, item):

        # 1.创建新结点p
        p = Node(item)
        # 2.新结点p加入链表（分2种情况讨论）
        if self.head == None:  # 1)链表为空,则新结点为表头
            self.head = p
        else:  # 2)链表不为空，则把新结点加入表尾
            self.tail.next = p
        # 3.修改表尾
        self.tail = p


# 测试程序
myList = unorderedList()  # 1.创建链表
n = int(input())  # 读入结点个数
if n > 0:
    ls = list(input().split())  # 读入结点数据
    # 2.尾插法添加结点
    for x in ls:
        myList.add_tail(x)
    print(" ".join(myList.print()))  # 3.输出链表

7-8 两个有序链表序列的合并 (10分)

已知两个非降序链表序列S1与S2，设计函数构造出S1与S2合并后的新的非降序链表S3。
输入格式:
输入分两行，分别在每行给出由若干个正整数构成的非降序序列，用 表示序列的结尾（ 不属于这个序列）。数
字用空格间隔。
输出格式:

在一行中输出合并后新的非降序链表，数字间用空格分开，结尾不能有多余空格；若新链表为空，输出NULL。 输入样例:
1 3 5 -1
2 4 6 8 10 -1

输出样例:

1 2 3 4 5 6 8 10

编译器 PYTHON3

代码

l1 = list(map(int, input().split()))[:-1]
l2 = list(map(int, input().split()))[:-1]
n1, n2 = len(l1), len(l2)
l3 = []
i = j = 0
while i < n1 and j < n2:
    if l1[i] < l2[j]:
        l3.append(l1[i])
        i += 1
    else:
        l3.append(l2[j])
        j += 1
while i < n1:
    l3.append(l1[i])
    i += 1
while j < n2:
    l3.append(l2[j])
    j += 1
n3 = len(l3)
if n3 == 0:
    print("NULL")
else:
    for i in range(n3 - 1):
        print(l3[i], end=" ")
    print(l3[-1])

7-9 链表的逆置 (10分)

输入若干个不超过100的整数，建立单链表，然后将链表中所有结点的链接方向逆置，要求仍利用原表的存储空间。
输出逆置后的单链表。
输入格式:
首先输入一个整数T，表示测试数据的组数，然后是T组测试数据。每组测试数据在一行上输入数据个数n及n个不超过
100的整数。
输出格式:
对于每组测试，输出逆置后的单链表，每两个数据之间留一个空格。
输入样例:

1
11 55 50 45 40 35 30 25 20 15 10 5

输出样例:

5 10 15 20 25 30 35 40 45 50 55

编译器 PYTHON3

代码

# 结点类，包括数据域data和引用域next
class Node:
    # 1.构造方法
    def __init__(self, initData):
        self.data = initData  # 数据域
        self.next = None  # 引用域初始化为空


# 无序表unorderedList
class unorderedList:
    # 1.构造方法
    def __init__(self):

        self.head = None  # 初始化表头
        self.tail = None  # 初始化表尾

    # 2.输出链表，用->连接 26->93->17->77->31
    def print(self):

        res = []
        p = self.head  # 从表头开始
        while p != None:
            res.append(p.data)
            p = p.next  # 访问下一个结点
        return res

    # 3.尾插法添加新结点
    def add_tail(self, item):

        # 1.创建新结点p
        p = Node(item)
        # 2.新结点p加入链表（分2种情况讨论）
        if self.head == None:  # 1)链表为空,则新结点为表头
            self.head = p
        else:  # 2)链表不为空，则把新结点加入表尾
            self.tail.next = p
        # 3.修改表尾
        self.tail = p

    # 4.就地逆置链表
    def reverse(self):

        p = self.head  # p-
        r = None  # 逆置后链表的表头
        # 遍历原链表
        while p != None:
            q = p  # 新结点q
            p = p.next
            # q用头插法加入逆置后的链表r
            q.next = r
            r = q
        self.head = r  # 表头改为逆置后的表头r


# 测试程序
T = int(input())
# T组测试数据
for i in range(T):
    myList = unorderedList()  # 1.创建链表
    ls = list(input().split())  # 读入结点数据
    ls = ls[1:]
    # 2.尾插法添加结点
    for x in ls:
        myList.add_tail(x)
    myList.reverse()
    print(" ".join(myList.print()))  # 3.输出链表