Font size
WorksheetsCTDLGT_T03(Stack,Queue)
Total questions: 54
Worksheet time: 1hrs 21mins
Nêu khái niệm ngăn xếp (Stack)
Các phần tử được lưu trữ thành một danh sách liên tiếp nhau. Việc thêm 1 phần tử vào danh sách được thực hiện ở một đầu (cuối hàng) Việc lấy ra 1 phần tử của danh sách được thực hiện ở đầu khác (cuối hàng)
Các phần tử được lưu trữ thành một danh sách liên tiếp nhau. Việc thêm 1 phần tử vào danh sách được thực hiện ở một đầu (đầu hàng) Việc lấy ra 1 phần tử của danh sách được thực hiện ở đầu khác (cuối hàng)
Các phần tử được lưu trữ thành một danh sách liên tiếp nhau. Việc thêm hay loại lấy một phần tử ra khỏi danh sách đều được thực hiện ở một đầu gọi là đỉnh của ngăn xếp.
Các phần tử được lưu trữ thành một danh sách liên tiếp nhau. Việc thêm 1 phần tử vào danh sách được thực hiện ở một đầu (cuối hàng) Việc lấy ra 1 phần tử của danh sách được thực hiện ở đầu khác (đầu hàng)
Nêu khái niệm Hàng đợi (Queue):
Các phần tử được lưu trữ thành một danh sách liên tiếp nhau. Việc thêm hay loại lấy một phần tử ra khỏi danh sách đều được thực hiện ở một đầu gọi là đỉnh của ngăn xếp.
Các phần tử được lưu trữ thành một danh sách liên tiếp nhau. Việc thêm 1 phần tử vào danh sách được thực hiện ở một đầu (cuối hàng). Việc lấy ra 1 phần tử của danh sách được thực hiện ở đầu khác (đầu hàng)
Các phần tử được lưu trữ thành một danh sách liên tiếp nhau. Việc thêm 1 phần tử vào danh sách được thực hiện ở một đầu (đầu hàng) Việc lấy ra 1 phần tử của danh sách được thực hiện ở đầu khác (cuối hàng)
Các phần tử được lưu trữ thành một danh sách liên tiếp nhau. Việc thêm 1 phần tử vào danh sách được thực hiện ở một đầu (cuối hàng) Việc lấy ra 1 phần tử của danh sách được thực hiện ở đầu khác (cuối hàng)
Stack tuân theo cấu trúc LIFO. LIFO là viết tắt của cụm từ Tiếng Anh gì?
(a)
Queue tuân theo cấu trúc FIFO. FIFO là viết tắt của cụm từ Tiếng Anh gì?
(a)
Stack tuân theo cấu trúc LIFO có nghĩa là gì?
Phần tử được đưa vào trong danh sách sau cùng sẽ được lấy ra trước tiên.
Phần tử đưa vào trong danh sách trước tiên sẽ được lấy ra sau cùng
Các phần tử vào trong danh sách trước sẽ được lấy ra trước.
Tất cả các phương án đều sai
Queue tuân theo cấu trúc FIFO có nghĩa là gì?
Phần tử được đưa vào trong danh sách sau cùng sẽ được lấy ra trước tiên.
Phần tử đưa vào trong danh sách trước tiên sẽ được lấy ra sau cùng
Các phần tử vào trong danh sách trước sẽ được lấy ra trước.
Tất cả các phương án đều đúng
Trong thuật toán chuyển đổi một số nguyên từ hệ thập phân sang hệ nhị phân, người ta sẽ dùng cấu trúc dữ liệu nào dưới đây để lưu số dư của các phép chia.
Queue
Stack
Array
Tree
Ngăn xếp được ứng dụng trong thuật toán “chuyển đổi một biểu thức toán học ở dạng Trung tố sang Hậu tố”. Hãy cho biết biểu thức hậu tố nhận được sau khi chúng ta cho chạy giải thuật “chuyển biểu thức từ trung tố sang hậu tố” với input là: 2 + 3 * 4 - 5
2 3 + * 4 5 -
2 3 4 5 * + -
2 3 4 * 5 + -
2 3 4 * + 5 -
Trong ứng dụng quản lý danh sách bệnh nhân đang chờ tại một phòng khám X. Hãy lựa chọn cấu trúc dữ liệu phù hợp nhất để lưu danh sách bệnh nhân này; biết rằng các bệnh nhân đến đăng ký trước sẽ được vào khám trước.
Queue
Stack
Array
Tree
Ngăn xếp được ứng dụng trong thuật toán “Tính giá trị của một biểu thức hậu tố”. Hãy cho biết giá trị tại đỉnh của ngăn xếp sau khi thực hiện thuật toán “Tính giá trị của một biểu thức hậu tố” với input là: 2 9 4 * + 5 -
30
31
32
33
Cho Stack có các phép toán:
push(X): Thêm phần tử X vào Stack
pop() : Lấy 1 phần tử ra khỏi Stack
Hãy cho biết phần tử ở đỉnh của Stack có giá trị bằng bao nhiêu sau khi thực hiện lần lượt các phép toán sau: push(5); push(3); pop(); push(4); push(6); pop()
3
4
5
6
Cho Queue có các phép toán:
EnQueue(X): Thêm phần tử X vào Queue
DeQueue() : Lấy 1 phần tử ra khỏi Queue
Hãy cho biết phần tử ở đầu của Queue có giá trị bằng bao nhiêu sau khi thực hiện lần lượt các phép toán sau: EnQueue(5); EnQueue(3); DeQueue(); EnQueue(4); EnQueue(6);
A. 3
4
5
6
Cho Queue có các phép toán:
EnQueue(X): Thêm phần tử X vào Queue
DeQueue() : Lấy 1 phần tử ra khỏi Queue
Hãy cho biết phần tử ở đầu của Queue có giá trị là ký tự nào, sau khi thực hiện thuật toán dưới đây với input là: “This**is***Queue*”
Thuật toán
Input: Xâu S
Đọc lần lượt từng ký tự từ trái qua phải của xâu S; Nếu ký tự đọc được là ‘*’ thì lấy 1 phần tử ra khỏi Queue. Ngược lại thì thêm phần tử đọc được vào Queue.
T
h
u
Q
Cho Stack có các phép toán:
push(X): Thêm phần tử X vào Stack
pop() : Lấy 1 phần tử ra khỏi Stack
Hãy cho biết phần tử ở đỉnh của Stack có giá trị là ký tự nào, sau khi thực hiện thuật toán dưới đây với input là: “This**is***Stack*”
Thuật toán
Input: Xâu S
Đọc lần lượt từng ký tự từ trái qua phải của xâu S; Nếu ký tự đọc được là ‘*’ thì lấy 1 phần tử ra khỏi Stack. Ngược lại thì thêm phần tử đọc được vào Stack.
T
S
c
k
Nhà logic học Balan Lukasiewicz đã đưa ra dạng biểu thức số học theo ký pháp hậu tố (postfix notation). Và ứng dụng ngăn xếp để thực hiện phép toán. Giả sử có biểu thức sau:(1 + 5) * ( 8 - (4 - 1)) Chuyển biểu thức này về dạng hậu tố cách nào sau đây là đúng
1 5 + * 8 4 1 - -
1 5 8 4 1- -+ *
1 5 8 4 1+ - - *
1 5 + 8 4 1 - - *
Khi đổi một số nguyên từ hệ thập phân sang hệ nhị phân thì người ta dùng phép chia liên tiếp cho 2 và lấy các số dư (là các chữ số nhị phân) theo chiều ngược lại. Cơ chế sắp xếp này chính là cơ chế hoạt động của cấu trúc dữ liệu.
Mảng (array)
Bản ghi( Record)
Hàng đợi(Queue)
Ngăn xếp (stack)
Cho Stack gồm 5 phần tử {12, 15, 18, 25, 30}, trong đó 30 là phần tử ở đỉnh Stack. Để thay số 18 bằng số 23 vào trong Stack ta phải làm thế nào?
Pop(12), Pop(15), Pop(18)
Pop(30), Pop(25), Pop(18), Push(23), Push(25), Push(30)
Pop(30), Pop(25), Pop(18), Push(23), Push(15), Push(12)
Pop(12), Pop(15), Pop(18), Push(23), Push(15), Push(12)
Cho Stack gồm 5 phần tử {2, 10, 12, 15, 20}, trong đó 20 là phần tử ở đỉnh Stack. Để lấy ra phần tử thứ 3 trong Stack ta phải làm thế nào?
Pop(2), Pop(10), Pop(12)
Pop(20), Pop(15), Pop(12)
Pop(2), Pop(10), Pop(12), Push(10), Push(2)
Pop(20), Pop(15), Pop(12), Push(10), Push(2)
Tính giá trị các biểu thức hậu tố sau 2 3 5 + * 1 2 + 4 *+
42
52
28
-28
Không có lỗi
Stack không được khởi tạo đúng cách
Phương thức Peek() không trả về giá trị
Phương thức Pop() cần có tham số
Giả sử có một Stack S chứa lần lượt 3 phần tử [1,2,3] với phần tử có giá trị là 1 ở đáy của Stack S . Sau khi thực hiện lần lượt các lệnh sau : S.Pop() ; S.Pop() ; và S.Push (4) ; Stack S sẽ chứa các phần tử là :
1,2,4
1,4
4,2,1
4
Giả sử có một Stack rỗng s. Thực hiện các lệnh sau s.Push(1), s.Push(2) và s.Pop(). Giá trị phần tử Top của Stack s là:
1
2
Không có giá trị
Không xác định được
1
2
3
4
Giả sử có Queue Q ban đầu rỗng. Hãy cho biết giá trị các phần tử trong q sau khi thực hiện đoạn mã sau for (int i = 0; i <= 16; i++) {if (i % 3 == 0) Q.Enqueue(i); else if (i % 4 == 0) Q.Dequeue();}
0,3,6,9,12,15
9,12,15
0,4,8,16
0,3,4,6,8,9,12,15,16
Giả sử có Queue q chứa 3 phần tử [1,2,3] với phần từ có giá trị là 1 ở đầu hàng đợi. Sau khi thực hiện q.Dequeue() ; q.Dequeue() ; và q.Enqueue(4) ; Các phần tử còn lại trong Queue q là ?
1,2,4
1,4
4,2,1
3,4
Nếu các phần tử 'T', 'H', 'E', 'V' và 'A' được thêm lần lượt theo thứ tự vào trong một hàng đợi q và các phần tử này bị xóa lần lượt thì thứ tự khi xóa sẽ như thế nào?
T H E V A
H E V A T
A V E H T
T A H V E
Biểu thức hậu tố nào là đúng từ biểu thức trung tố sau : 3 + 4 * 5
3 4 5 + *
3 4 5 * +
3 4 + 5*
3 4 * 5 +
Giá trị của biểu thức hậu tố: 6 3 2 4 + - * bằng bao nhiêu?
1
40
74
-18
Nếu trình tự các hoạt động được thực hiện trên một ngăn xếp như sau:
push(1)
push(3)
pop
push(2)
push(2)
pop
pop
pop
push(3)
pop
Thì thứ tự các giá trị nào là đúng?
3, 2, 2, 3, 1
3, 2, 1, 3, 2
2, 3, 2, 3, 1
1, 3, 2, 2, 3
Hãy xem xét các hoạt động sau được thực hiện trên một ngăn xếp có kích thước 5:
Push(a)
Pop()
Push(b)
Push(c)
Pop()
Push(d)
Pop()
Pop()
Push(e)
Câu nào sau đây là đúng?
Các hoạt động trên ngăn xếp được thực hiện đầy đủ
Xảy ra tràn dưới (Underflow)
Xảy ra tràn trên (Overflow)
Không có trường hợp nào trong 3 trường hợp đó
Nếu các phần tử “A”, “B”, “C” và “D” được đặt trong một ngăn xếp và bị xóa từng phần tử một, thì phần tử cuối cùng bị xóa sẽ là phần tử nào?
A
B
C
D
Chuyển đổi dạng Infix sang Postfix:
v * w + (x * y) + z
vw*xy*+z+
vw*xy+*z*
vw+xy*z+
none
Chuyển đổi dạng Infix sang Postfix:
A * B + C / D
AB*CD/+
*AB/CD+
A*BC+/D
ABCD+/*
Phân tích đoạn mã sau và xác định thứ tự các ngăn xếp từ ngắn nhất đến dài nhất:
stack1.push(12);
stack2.push(24);
stack3.push(11);
stack1.push(37);
stack2.push(59);
stack3.push(46);
stack1.pop();
stack1.pop();
stack2.pop();
stack1.emplace(12);
stack2.emplace(20);
stack3.emplace(41);
stack1.emplace(19);
stack2.emplace(23);
stack3.emplace(10);
stack1.swap(stack2);
stack2.swap(stack3);
Stack2, stack1, stack3
Stack1, stack2, stack3
Stack3, stack2, stack1
None of the above
Đây là khai báo cấu trúc dữ liệu gì ?
Const max = N ;
Type
A = Record front, rear : 0..max;
E : Array[1..max] Of Item;
End;
Var Q : A;
Ngăn xếp (stack)
Hàng đợi (queue)
Con trỏ (pointer)
Mảng (array)
Giả sử Q là Hàng đợi các phần tử của nó có kiểu Item thủ tục sau làm nhiệm vụ gì?
Procedure Initialize(Var Q : Queue);
Begin With Q Do
begin
front := 1;
rear := 0;
end;
End;
Khởi tạo một hàng đợi rỗng
Kiểm tra hàng đợi có rỗng hay không
Thêm một phần tử vào hàng đợi
Loại bỏ một phần tử ra khỏi hàng đợi
Giả sử Q là Hàng đợi, các phần tử của nó có kiểu Item, Hàm sau làm nhiệm vụ gì?
Function F(Q : Queue) : Boolean;
Begin F:= (Q.rear = max);
End;
Kiểm tra hàng đợi đầy.
Khởi tạo một hàng đợi rỗng
Kiểm tra hàng đợi có rỗng hay không
Thêm một phần tử vào hàng đợi
Giả sử Q là Hàng đợi các phần tử của nó có kiểu Item Hàm sau làm nhiệm vụ gì? Function Empty(Q : Queue) : Boolean; Begin Empty := (Q.rear = 0); End;
Kiểm tra hàng đợi có rỗng hay không
Khởi tạo một hàng đợi rỗng
Thêm một phần tử vào hàng đợi
Kiểm tra hàng đợi đầy.
Giả sử Q là Hàng đợi các phần tử của nó có kiểu Item, X là một phần tử có cùng kiểu với các phần tử của hàng đợi. Thủ tục sau làm nhiệm vụ gì? Procedure Q1(Var Q : Queue; X : Item); Begin If Full(Q) Then write('Hang day') Else With Q Do begin rear := rear + 1; E[rear] := X; end; End;
Khởi tạo một hàng đợi rỗng
Kiểm tra hàng đợi đầy.
Kiểm tra hàng đợi có rỗng hay không
Thêm một phần tử vào hàng đợi
Giả sử Q là Hàng đợi các phần tử của nó có kiểu Item, X là một phần tử có cùng kiểu với các phần tử của hàng đợi. Thủ tục sau làm nhiệm vụ gì? Procedure DeleteQ(Var Q : Queue; Var X : Item); Begin If Empty(Q) Then write('Hang rong') Else With Q Do begin X := E[front]; if front = rear then begin & vbCrLf & _ front := 1; rear : = 0; {khởi tạo lại hàng đợi} end else front := front + 1; end; End;
Loại bỏ một phần tử ra khỏi hàng đợi
Thêm một phần tử vào hàng đợi
Kiểm tra hàng đợi có rỗng hay không
Kiểm tra hàng đợi đầy.
Khi loại bỏ một phần tử ra khỏi hàng đợi Thì:
Cần khởi tạo lại hàng đợi
Nếu hàng đợi chỉ có một phần tử thì không thể thực hiện việc loại bỏ
Nếu hàng đợi đầy thì không thể thực hiện việc loại bỏ
Nếu hàng đợi rỗng thì không thể thực hiện việc loại bỏ
Khi bổ sung một phần tử mới vào hàng đợi cần kiểm tra
Hàng đợi có bao nhiêu giá trị bằng 0
Hàng đợi có bao nhiêu phần tử
Hàng đợi có rỗng không
Hàng đợi có đầy không
Cho hàm H(n) (với n là số nguyên không âm)định nghĩa đệ quy như sau: H(n) =1 nếu n>=10 H(n)=2n+ H(n+2) nếu n<10 Tính H(5)
41
40
42
43
Cấu trúc dữ liệu hàng đợi dùng để làm gì?
a. Tổ chức quản lý và phân phối tiến trình trong các hệ điều hành
b. Tổ chức xoá các quá trình tìm kiếm theo chiều rộng
c. Khử đệ quy
d. Tổ chức lưu bộ đệm bàn phím
Các thao tác cơ bản với queue
a. Xoá một phần tử từ hàng đợi: dequeue()
b. Tất cả các đáp án trên
c. Kiểm tra xem hàng đợi đầy hay không: isFull()
d. Thêm một phần tử vào hàng đợi: enqueue()
e. Lấy phần tử ở đầu hàng đợi, mà không xoá phần tử này: peek()
Việc chèn thêm 1 phần tử vào một hàng đợi bị đầy gọi là gì?
underflow
overflow
front
rear
Điều kiện cần thiết được kiểm tra trước khi chèn một phần tử vào hàng đợi liên kết (a linked queue) là gì?
Underflow
Overflow
Front value
Rear value
Một hàng đợi các ký tự hiện chứa a, b, c, d. Nội dung của hàng đợi sẽ là gì sau thao tác sau:
Delete,
Add W,
Add X,
Delete,
Add Y.
A,B,C,W,Y
A,B,C,D,W
C,D,W,X,Y
W,Y,X,C,D
Nếu front=rear thì hàng đợi thế nào?
full
undeflow
overflow
empty
Nếu các số 5, 10, 3, 42 được đưa vào hàng đợi theo thứ tự, thì phép lấy ra lần thứ hai sẽ trả về số nào?
5
10
3
42
Hàng đợi đơn (Simple Queue) được triển khai bằng cách sử dụng một mảng có kích thước 10. Chỉ số mảng bắt đầu bằng 0, front là 6 và rear là 9. Việc chèn phần tử tiếp theo diễn ra ở chỉ số mảng nào?
0
7
9
Không thể chèn thêm phần tử vì mảng đã đầy ở cuối
Cho Hàng đợi dịch vòng (Circular Queue) sau đây có thể chứa tối đa sáu phần tử với dữ liệu sau
front = 2, rear = 4
queue = _______; L, M, N, ___, ___
Điều gì sẽ xảy ra sau khi thực hiện thao tác ADD O ?
front = 2 rear = 5
queue = ______; L, M, N, O, ___
front = 3 rear = 5
queue = L, M, N, O, ___
front = 3 rear = 4
queue = ______; L, M, N, O, ___
front = 2 rear = 4
queue = L, M, N, O, ___
Nếu các phần tử “A”, “B”, “C” và “D” được xếp vào hàng đợi và bị xóa từng phần tử một thì chúng sẽ bị xóa theo thứ tự nào?
ABCD
DCBA
DCAB
ABDC
Hàng đợi dịch vòng (Circular Queue) được triển khai bằng cách sử dụng một mảng có kích thước 10. Chỉ số mảng bắt đầu bằng 0, front là 6 và rear là 9. Việc chèn phần tử tiếp theo diễn ra ở chỉ số mảng nào?
0
7
9
10
