-
《数据结构与算法》线性结构复习题
1、判断题
1-1 通过对堆栈S操作：Push(S,1), Push(S,2), Pop(S), Push(S,3), Pop(S), Pop(S)。输出的序列为：123。 (1分)
F1-2 若一个栈的输入序列为1，2，3，…， N N N，输出序列的第一个元素是 i i i，则第 j j j个输出元素是 j − i − 1 j-i-1 j−i−1 。 (1分)
F1-3 若一个栈的输入序列为{1, 2, 3, 4, 5}，则不可能得到{3, 4, 1, 2, 5}这样的出栈序列。 (1分)
T1-4 栈顶元素和栈底元素有可能是同一个元素。 (1分)
T1-5 在具有 个结点的单链表中，访问结点和增加结点的时间复杂度分别对应为 O ( 1 ) O(1) O(1)和 O ( N ) O(N) O(N) 。 (1分)
F1-6 线性表L如果需要频繁地进行不同下标元素的插入、删除操作，此时选择顺序存储结构更好。 (1分)
F1-7 In a singly linked list of N N N nodes, the time complexities for query and insertion are O ( 1 ) O(1) O(1) and O ( N ) O(N) O(N) ,respectively. (1分)
（翻译：在单链表的N个节点中，查询和插入的时间复杂度分别为 O ( 1 ) O(1) O(1)和 O ( n ) O(n) O(n)。）
F1-8 If N N N numbers are stored in a singly linked list in increasing order, then the average time complexity for binary search is O ( l o g N ) O(logN) O(logN). (1分)
（翻译：如果N个数按递增顺序存储在单链表中，则二分查找的平均时间复杂度为 O ( l o g N ) O(logN) O(logN)。1-10）
F1-9 若用链表来表示一个线性表，则表中元素的地址一定是连续的。 (1分)
F1-10 将 N N N个数据按照从小到大顺序组织存放在一个单向链表中。如果采用二分查找，那么查找的平均时间复杂度是 O ( l o g N ) O(logN) O(logN)。(1分)
F1-11 将长度分别为m,n的两个单链表合并为一个单链表的时间复杂度为 O ( m + n ) O(m+n) O(m+n)。 (1分)
F1-12 在单链表中，要访问某个结点，只要知道该结点的指针即可。因此，单链表是一种随机存取结构。 (1分)
F1-13 链表 - 存储结构
链表中逻辑上相邻的元素，其物理位置也一定相邻。 (1分)
F1-14 链表是采用链式存储结构的线性表,进行插入、删除操作时，在链表中比在顺序存储结构中效率高。 (1分)
T1-15 算法分析的两个主要方面是时间复杂度和空间复杂度的分析。 (1分)
T1-16 对于某些算法，随着问题规模的扩大，所花的时间不一定单调增加。 (1分)
T1-17 线性表的插入、删除总是伴随着大量数据的移动。 (1分)
F1-18 算法可以没有输入，但是必须有输出。 (1分)
T2、单选题
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 b2-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 62-3 若一个栈的入栈序列为1、2、3、…、 N N N，输出序列的第一个元素是 i i i，则第 j j j个输出元素是： (2分)
A. i − j − 1 i-j-1 i−j−1
B. i − j i-j i−j
C. j − i − 1 j-i-1 j−i−1
D. 无法确定2-4 将5个字母ooops按此顺序入栈，则有多少种不同的出栈顺序可以仍然得到ooops？ (2分)
A. 1
B. 3
C. 5
D. 62-5 设一个堆栈的入栈顺序是1、2、3、4、5。若第一个出栈的元素是4，则最后一个出栈的元素必定是： (2分)
A. 1
B. 3
C. 5
D. 1或者52-6 给定一个堆栈的入栈序列为{ 1, 2,··· , n n n }，出栈序列为{ p 1 , p 2 , ⋅ ⋅ ⋅ , p n p1,p2,···,pn p1,p2,⋅⋅⋅,pn}。如果 p 2 = n p2=n p2=n，则存在多少种不同的出栈序列？(2分)
A. 1
B. 2
C. n − 1 n-1 n−1
D. n n n2-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 - 12-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,22-11 设一个堆栈的入栈顺序是1、2、3、4、5。若第一个出栈的元素是4，则最后一个出栈的元素必定是____。 (2分)
A. 1
B. 3
C. 5
D. 1或者52-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 e2-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, 12-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,12-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. 42-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. 42-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，12-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、52-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. 132-25 线性表若采用链式存储结构时，要求内存中可用存储单元的地址 (2分)
A. 必须是连续的
B. 连续或不连续都可以
C. 部分地址必须是连续的
D. 一定是不连续的2-26 在具有 N N N个结点的单链表中，实现下列哪个操作，其算法的时间复杂度是 O ( N ) O(N) O(N)？ (2分)
A. 在地址为 p p p 的结点之后插入一个结点
B. 删除开始结点
C. 遍历链表和求链表的第 i i i 个结点
D. 删除地址为 p p 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一起存储在内存空间中：）
Nowfis stored at1014Hand is inserted into the linked list betweenaande. Then the “Link” fields ofa,e, andfare __, respectively.（翻译：现在 f 存储在1014H，并插入到a和e之间的链表中。然后，a、e和f的“Link”字段分别为__。）
A. 1010H , 1014H , 1004H
B. 1010H , 1004H , 1014H
C. 1014H , 1010H , 1004H
D. 1014H , 1004H , 1010H2-30 在单链表中，要删除某一指定结点，必须先找到该结点的（）。 (2分)
A. 直接前驱
B. 自身位置
C. 直接后继
D. 直接后继的后继2-31 以下关于链式存储结构的叙述中，（）是不正确的。 (2分)
A. 结点除自身信息外还包括指针域，因此存储密度小于顺序存储结构
B. 逻辑上相邻的结点物理上不必邻接
C. 可以通过计算直接确定第i个结点的存储地址
D. 插入、删除运算操作方便，不必移动结点2-32 对于一个具有 N N N 个结点的单链表，在给定值为 的结点后插入一个新结点的时间复杂度为 (2分)
A. O ( 1 ) O(1) O(1)
B. O ( N / 2 ) O(N/2) O(N/2)
C. O ( N ) O(N) O(N)
D. O ( N 2 ) O(N^2) O(N2)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")- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
7-2 堆栈操作合法性 (10分)
假设以
S和X分别表示入栈和出栈操作。如果根据一个仅由S和X构成的序列，对一个空堆栈进行操作，相应操作均可
行（如没有出现删除时栈空）且最后状态也是栈空，则称该序列是合法的堆栈操作序列。请编写程序，输入S和X序
列，判断该序列是否合法。
输入格式:
输入第一行给出两个正整数 N N N和 M M M，其中N是待测序列的个数， M ( < = 50 ) M(<=50) M(<=50)是堆栈的最大容量。随后 N N N行，每行中给
出一个仅由S和X构成的序列。序列保证不为空，且长度不超过100。
输出格式:
对每个序列，在一行中输出YES如果该序列是合法的堆栈操作序列，或NO如果不是。
输入样例：4 10 SSSXXSXXSX SSSXXSXXS SSSSSSSSSSXSSXXXXXXXXXXX SSSXXSXXX- 1
- 2
- 3
- 4
- 5
输出样例：
YES NO NO NO- 1
- 2
- 3
- 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) # 判断字符串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")- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
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() + ')'))- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
7-4 有关队列操作 (10分)
请实现一个MyQueue类，实现出队，入队，显示队列，求队列长度。
实现入队方法 push(int x); 实现出队方法 pop(); 实现求队列长度方法 size();实现显示队列方法：show() 。
输入格式:
每个输入包含1个测试用例。
每个测试用例第一行给出一个正整数 n ( n < = 1 0 6 ) n (n <= 10^6) n(n<=106)，接下去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- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
输出样例:
在这里给出相应的输出。例如： 2 23 34 23 34 1- 1
- 2
- 3
- 4
- 5
- 6
编译器 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()- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
7-5 约瑟夫环 (10分)
有n个人围成一圈（编号为1～n），从第1号开始进行1、2、3报数，凡报3者就退出，下一个人又从1开始报数……直
到最后只剩下一个人时为止。请问此人原来的位置是多少号?
输入格式:
测试数据有多组，处理到文件尾。每组测试输入一个整数 n （ 5 ≤ n ≤ 100 ） n（5≤n≤100） n（5≤n≤100）。
输出格式:
对于每组测试，输出最后剩下那个人的编号。
输入样例:10 28 69- 1
- 2
- 3
输出样例:
4 23 68- 1
- 2
- 3
编译器 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- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
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))- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
7-7 单链表的创建及遍历 (10分)
读入n值及n个整数，建立单链表并遍历输出。
输入格式:
读入n及n个整数。
输出格式:
输出n个整数，以空格分隔（最后一个数的后面没有空格）。
输入样例:在这里给出一组输入。例如： 2 10 5- 1
- 2
- 3
输出样例:
在这里给出相应的输出。例如： 10 5- 1
- 2
编译器 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.输出链表- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
7-8 两个有序链表序列的合并 (10分)
已知两个非降序链表序列S1与S2，设计函数构造出S1与S2合并后的新的非降序链表S3。
输入格式:
输入分两行，分别在每行给出由若干个正整数构成的非降序序列，用 表示序列的结尾（ 不属于这个序列）。数
字用空格间隔。
输出格式:在一行中输出合并后新的非降序链表，数字间用空格分开，结尾不能有多余空格；若新链表为空，输出NULL。 输入样例: 1 3 5 -1 2 4 6 8 10 -1- 1
- 2
- 3
输出样例:
1 2 3 4 5 6 8 10- 1
编译器 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])- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
7-9 链表的逆置 (10分)
输入若干个不超过100的整数，建立单链表，然后将链表中所有结点的链接方向逆置，要求仍利用原表的存储空间。
输出逆置后的单链表。
输入格式:
首先输入一个整数T，表示测试数据的组数，然后是T组测试数据。每组测试数据在一行上输入数据个数n及n个不超过
100的整数。
输出格式:
对于每组测试，输出逆置后的单链表，每两个数据之间留一个空格。
输入样例:1 11 55 50 45 40 35 30 25 20 15 10 5- 1
- 2
输出样例:
5 10 15 20 25 30 35 40 45 50 55- 1
编译器 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.输出链表- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
-
相关阅读:
学个Antenna：Matlab天线工具箱知多少（二）
【RuoYi-Vue-Plus】扩展笔记 06 - 数据源 Druid 修改为 HikariCP
057_末晨曦Vue技术_处理边界情况之强制更新和创建低开销的静态组件
C++哈希
从零玩转之JPOM自动化部署本地构建 + SSH 发布 java 项目
发布项目到github上
前端知识记录
分布式动态路由的实现
redis 配置与优化
mybatis自定义数组类型处理器用于pgsql数组类型字段
- 原文地址：https://blog.csdn.net/XQC_KKK/article/details/125391620