Chương 3: Các kiểu dữ liệu trừu tượng

Chương 3: Các kiểu dữ liệu trừu tượng

Câu 43: Danh sách liên kết được định nghĩa như sau :
a.Danh sách liên kết là 1 cấu trúc dữ liệu bao gồm 1 tập các phần tử, trong đó mỗi phần tử là 1 phần của 1 nút có chứa một liên kết tới nút kế tiếp.
Câu 44: Mảng được định nghĩa như sau:
a.Mảng là 1 tập hợp cố định các thành phần có cùng 1 kiểu dữ liệu, được lưu trữ kế tiếp nhau và có thể được truy cập thông qua một chỉ số.
Câu 45: Cách truy cập phần tử của danh sách liên kết là:
a.Tuần tự
Câu 46: Đối với danh sách liên kết, để thay đổi vị trí 1 phần tử, ta cần thay đổi:
a. Các liên kết của 1 số phần tử liên quan.
Câu 47: Kích thước của danh sách liên kết :
a.Không cần khai báo trước.
Câu 48: Danh sách liên kết gồm:
a. Liên kết vòng, liên kết kép.
Câu 49: Ngăn xếp ( Stack) được định nghĩa :
a. Là 1 cấu trúc dữ liệu có 2 thao tác cơ bản: bổ sung (push) và loại bỏ phần tử (pop), trong đó việc loại bỏ sẽ tiến hành loại phần tử mới nhất được đưa vào danh sách.
Câu 50: Để thêm một phần tử vào stack ta thêm vào vị trí?
a. Đầu cuả stack
Câu 51: Danh sách tuyến tính dạng ngăn xếp làm việc theo nguyên tắc
a. FILO(first in last out)
Câu 52: Để loại bỏ một phần tử ra khỏi Queue ta loại ở ?
a. Cuối của Queue
Câu 53: 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:
a. Ngăn xếp (stack)
Câu 54: Định nghĩa danh sách tuyến tính Hàng đợi (Queue)
a. Hàng đợi là kiểu danh sách tuyến tính trong đó, phép bổ sung một phần tử vào hàng đợi được thực hiện ở một đầu, gọi là lối sau (rear) và phép loại bỏ một phần tử được thực hiện ở đầu kia, gọi là lối trước (front).
Câu 55: Khi loại bỏ một phần tử ra khỏi hàng đợi Thì:
a. Nếu hàng đợi rỗng thì không thể thực hiện việc loại bỏ
Câu 56: Khi bổ sung một phần tử mới vào hàng đợi cần kiểm tra
a. Hàng đợi có đầy không
Câu 57: : Để đưa thêm một phần tử vào Queue ta thêm vào vị trí nào?
a. Vào đầu Queue
Câu 58: Hàng đợi còn được gọi là danh sách kiểu
a. FIFO
Câu 59: Hàng đợi có thể được cài đặt bằng:
a. Cả danh sách liên kết và bằng mảng.
Câu 60: Ngăn xếp có thể được cài đặt bằng:
a. a. Cả danh sách liên kết và bằng mảng.
Câu 61: Khi khai báo một cấu trúc node bao gồm mấy thành phần:
a. 2
Câu 62: Cho đoạn ký tự “ happy” thì đoạn ký tự có được khi sử dụng ngăn xếp là:
a.yppah
Câu 63: Cho đoạn ký tự “ stack” thì đoạn ký tự có được khi sử dụng ngăn xếp là:
a.kcats
Câu 64: Cho đoạn ký tự “queue” thì đoạn ký tự có được khi sử dụng ngăn xếp là :
a.eueuq
Câu 65: Cho biểu thức sau : 3*(((5-2)*(7+1)-6)) dạng nào sau đây của biêủ thức được viết dưới dạng hậu tố :
a. 3 5 2 – 7 1 + * 6 - *
Câu 66: Tính giá trị của biểu thức theo hậu tố là ứng dụng của :
a. Ngăn xếp
Câu 67: Trong ứng dụng tính giá trị biểu thức theo trung tố của ngăn xếp khi gặp “( “có nghĩa là :
a. Bỏ qua
Câu 68: Trong ứng dụng tính giá trị biểu thức theo trung tố của ngăn xếp khi gặp “) “có nghĩa là :
a. Lấy 3 phần tử trên đỉnh ra khỏi ngăn xếp rồi tính và đưa kết quả vào ngăn xếp
Câu 69: Trong ứng dụng tính giá trị biểu thức theo hậu tố của ngăn xếp khi gặp toán tử thì:
a. Lấy 2 phần tử trên đỉnh của ngăn xếp ra và tính sau đó đưa kết quả vào ngăn xếp

Câu 70 : Đảo xâu ký tự là một ứng dụng của :
a. Ngăn xếp.
Câu 71: Để cài đặt ngăn xếp bằng mảng, khi ngăn xếp chưa có phần tử nào thì ta quy ước top sẽ có giá trị:
a.-1
Câu 72: Để cài đặt ngăn xếp bằng mảng, khi ngăn xếp n phần tử nào thì ta quy ước top sẽ có giá trị:
a. n-1
Câu 73: Đối với hàng đợi việc bổ sung và loại bỏ phần tử được thực hiện như thế nào?
a. Ở 2 đầu khác nhau.
Câu 74* : Đoạn chương trình sau mô tả thao tác:
struct node {
int item;
struct node *next;
};
typedef struct node *listnode;
a. Khai báo một danh sách liên kết mà mỗi nút chứa một phần tử là số nguyên
Câu 75*: Đoạn chương trình sau mô tả thao tác:
int StackFull(stack s){
return (s.top = = MAX-1);
}
a.Kiểm tra ngăn xếp đầy
Câu 76*: Dòng lệnh sau mô tả thao tác:
listnode p;
a. Khai báo biến P
Câu 77*: Dòng lệnh sau mô tả thao tác:
p = (listnode)malloc(sizeof(struct node));
a. Cấp phát bộ nhớ cho p
Câu 78*: Dòng lệnh sau mô tả thao tác:
free(p);
a. Giải phóng bộ nhớ đã cấp phát cho nút p
Câu 79*: Đoạn chương trình sau mô tả thao tác:
void Insert_Begin(listnode *p, int x){
listnode q;
q = (listnode)malloc(sizeof(struct node));
q-> item = x;
q-> next = *p;
*p = q;
}
a. Chèn một nút vào đầu danh sách.
Câu 79*: Đoạn chương trình sau mô tả thao tác:
void Insert_Begin(listnode *p, int x){
listnode q;
q = (listnode)malloc(sizeof(struct node));
q-> item = x;
q-> next = *p;
*p = q;
}
a. Chèn một nút vào đầu danh sách.
Câu 81*: Đoạn chương trình sau mô tả thao tác:
void Insert_Middle(listnode *p, int position, int x){
int count=1, found=0;
listnode q, r;
r = *p;
while ((r != NULL)&&(found==0)){
if (count == position){
q = (listnode)malloc(sizeof(struct node));
q-> item = x;
q-> next = r-> next;
r-> next = q;
found = 1;
}
count ++;
r = r-> next;
}
if (found==0)
printf(“Khong tim thay vi tri can chen !”);
}
a. Chèn một nút vào trước nút r của danh sách
Câu 82* : Đoạn chương trình sau mô tả thao tác:
void Remove_Begin(listnode *p){
listnode q;
if (*p == NULL) return;
q = *p;
*p = (*p)-> next;
q-> next = NULL;
free(q);
}
a. Xóa 1 nút ở đầu danh sách.
Câu 83* : Đoạn chương trình sau mô tả thao tác:
void Remove_End(listnode *p){
listnode q, r;
if (*p == NULL) return;
if ((*p)-> next == NULL){
Remove_Begin(*p);
return;
}
r = *p;
while (r-> next != NULL){
q = r;
r = r-> next;
}
q-> next = NULL;
free(r);
}
a. Xóa 1 nút ở cuối danh sách.
Câu 84*: Đoạn chương trình sau mô tả thao tác:
void Remove_Middle(listnode *p, int position){
int count=1, found=0;
listnode q, r;
r = *p;
while ((r != NULL)&&(found==0)){
if (count == position){
q = r-> next;
r-> next = q-> next;
q-> next = NULL;
free (q);
found = 1;
}
count ++;
r = r-> next;
}
if (found==0)
printf(“Khong tim thay vi tri can xoa !”);
}
a. Xóa 1 nút trước nút r trong danh sách.
Câu 85*: Đoạn chương trình sau mô tả thao tác:
r = p;
while (r-> next != null){
//thực hiện các thao tác cần thiết
r = r-> next;
}
a.Duyệt toàn bộ danh sách
Câu 86*: Đoạn chương trình sau mô tả thao tác:
void Push(stack *s, int x){
if (StackFull(*s)){
printf(“Ngan xep day !”);
return;
}else{
s-> top ++;
s-> nut[s-> top] = x;
return;
}
}
a. Thao tác bổ sung 1 phần tử vào ngăn xếp
Câu 87*: Đoạn chương trình sau mô tả thao tác:
int Pop(stack *s){
if (StackEmpty(*s)){
printf(“Ngan xep rong !”);
}else{
return s-> nut[s-> top--];
}
}
a. Thao tác lấy 1 phần tử ra khỏi ngăn xếp.
Câu 88* : Đoạn chương trình sau mô tả thao tác:
void QueueInitialize(queue *q){
q-> head = 0;
q-> tail = MAX-1;
q-> count = 0;
return;
}
a. Khởi tạo hàng đợi.
Câu 89* : Đoạn chương trình sau mô tả thao tác:
int QueueEmpty(queue q){
return (q.count <= 0);
}
a. Kiểm tra hàng đợi rỗng
Câu 90*: Đoạn chương trình sau mô tả thao tác:
void Put(queue *q, int x){
if (q-> count == MAX)
printf(“Hang doi day !”);
else{
if (q->tail == MAX-1 )
q->tail=0;
else
(q->tail)++;
q->node[q->tail]=x;
q-> count++;
}
return;
}
a. Thêm 1 phần tử vào hàng đợi.
Câu 91*: Đoạn chương trình sau mô tả thao tác:
int Get(queue *q){
int x;
if (QueueEmpty(*q))
printf("Hang doi rong !");
else{
x = q-> node[q-> head];
if (q->head == MAX-1 )
q->head=0;
else
(q->head)++;
q-> count--;
}
return x;
}
a. Lấy phần tử ra khỏi hàng đợi.
Câu 93*: Đoạn chương trình sau mô tả thao tác:
int StackEmpty(stack s){
return (s.top = = -1);
}
a..Kiểm tra ngăn xếp rỗng.
Câu 94*: Đoạn chương trình sau mô tả thao tác:
#define MAX 100
typedef struct {
int head, tail, count;
int node[MAX];
} queue;
a. Khai báo bằng mảng cho 1 hàng đợi chứa các số nguyên với tối đa 100 phần tử.
Câu 95**: Hình 1 mô tả thao tác nào của danh sách:






a.Chèn 1 nút vào cuối danh sách
Câu 96**: Hình 2 mô tả thao tác của danh sách:








a. Chèn 1 nút vào trước nút r trong danh sách
Câu 97**: Đoạn chương trình sau mô tả thao tác:
struct node{
double heso;
int luythua;
struct node *next;
};
typedef struct node *listnode;
a. Sử dụng danh sách liên kết để biểu diễn 1 đa thức.
Câu 98**: Để danh sách liên kết có thể biểu thị đa thức, mỗi nút của danh schs phải có thành phần:
a. Trường heso kiểu thực,trường mũ, trường con trỏ tiếp.
Câu 99**: Đoạn chương trình sau mô tả thao tác:
struct node {
int item;
struct node *next;
};
typedef struct node *stacknode;
typedef struct {
stacknode top;
}stack;
a. Khai báo ngăn xếp bằng danh sách liên kết
Câu 100**: Đoạn chương trình sau mô tả thao tác:
struct node {
int item;
struct node *next;
};
typedef struct node *queuenode;
typedef struct {
queuenode head;
queuenode tail;
}queue;
a. Khai báo hàng đợi bằng danh sách liên kết
Câu 101**: Khi cài đặt hàng đợi bằng danh sách liên kết, ta sử dụng 2 biến để lưu trữ gi?
a. Điểm đầu, điểm cuối.
Câu 102**: Thao tác khởi tạo hàng đợi thực hiện việc gán giá trị null cho nút đầu và cuối của hàng đợi, cho biết hàng đợi đang ở trạng thái nào:
a. Rỗng
Câu 103**: Để thực hiện được thao tác duyệt toàn bộ danh sách trong cài đặt ngăn xếp bằng danh sách, ta cần một biến tạm r trỏ tới vị trí nào của danh sách:
a. Đầu danh sách.