Cấu trúc dữ liệu và giải thuật - IT05 (255)
Cho thuật toán sau:
int LinearSearch( float M[], int N, float X)
{
int k = 0;
M[N] = X;
while (M[k] !=X)//n+1
k++;
if (k<N) return k;
return -1;
}
Chọn câu đúng nhất trong trường hợp xấu nhất khi không tìm thấy phần tử nào có giá trị bằng X:
A. Số phép gán: Gmax = 1 Số phép so sánh: Smax = N + 2
B. Số phép gán: Gmax = 2 Số phép so sánh: Smax = N + 1
C. Số phép gán: Gmax = 2 Số phép so sánh: Smax = 2N + 2
D. Số phép gán: Gmax = 2 Số phép so sánh: Smax = N + 2
Đối với thuật toán sắp xếp chọn trực tiếp cho dãy phần tử sau (10 phần tử):
16 60 2 25 15 45 5 30 33 20
Cần thực hiện bao nhiêu lựa chọn phần tử nhỏ nhất để sắp xếp mảng M có thứ tự tăng dần
A. 8 lần
B. 10 lần
C. 7 lần
D. 9 lần
void RemoveHead ( LIST &Q ){
Node *p;
if (Q.Head != NULL)
{
p = Q.Head;
…[1] …
free(p);
if ( Q.Head == NULL )
Q.Tail = NULL;
}
}
Dòng lệnh cần thiết được đặt vào chỗ trống tại dòng số [1]:
A. Q.Head -> next = Q.Head;
B. Q.Head = NULL;
C. Q.Head = Q.Head -> next;
D. Q.Head -> next = NULL;
Các trường hợp chèn thêm một phần tử mới vào danh sách liên kết đơn gồm:
A. Chèn thêm vào đầu danh sách và vào cuối danh sách
B. Chèn thêm vào đầu danh sách, vào cuối danh sách và vào sau một phần tử q đã biết
C. Chèn thêm vào cuối danh sách và vào sau một phần tử q đã biết
D. Chèn thêm vào đầu danh sách và vào sau một phần tử q đã biết
Cho đoạn mã sau
stack <int> s; for (int i = 1; i <= 5; i++)
s.push(i);
while (!s.empty()) {
cout << s.top() << endl; s.pop(); }
Kết quả in lên màn hình là gì?
A. 1, 3, 5
B. 1, 2, 3, 4, 5
C. 2, 4, 5
D. 5, 4, 3, 2, 1
Cho khai báo cấu trúc:
struct NodeQueue
{
int info;
struct NodeQueue *next;
struct NodeQueue *pre;
};
struct Queue
{
NodeQueue *Rear, *Front;
}
Queue Q;
Đoạn mã sau đây thực hiện yêu cầu gì?
void initQueue(Queue &Q)
{
Q.Rear = NULL;
Q.Front = NULL;
}
A. Khởi tạo mảng rỗng
B. Khởi tạo hàng đợi rỗng
C. Khởi tạo danh sách rỗng
D. Khởi tạo Stack rỗng
Các ứng dụng cơ bản của hàng đợi gồm
A. Tất cả các phương án đều sai
B. Đảo ngược xâu ký dự
C. Tất cả các phương án đều đúng
D. Chuyển đổi cơ số
Cho đoạn mã sau, cho biết kết quả của x?
Stack S;
InitStack(S);
Push(S, “Green”);
Push(S, “Red”);
Push(S, “Yellow”);
Pop(S,x);
Pop(S, x);
A. Green
B. Tất cả các phương án đều đúng
C. Red
D. Yellow
Cho đoạn mã sau
stack <int> s; for (int i = 1; i <= 5; i++)
s.push(i);
Phần tử được lấy ra cuối cùng của Stack là gì?
Các thao tác được định nghĩa cho ngăn xếp một cách tổng quát
A. Push
B. Cả hai đáp án đều sai
C. Cả hai đáp án đều đúng
D. Pop
Cho khai báo Stack như sau:
struct Stack
{
int top
int nut[max];
};
Cho biết phần tử được lấy ra cuối cùng trong Stack sau là bảo nhiêu?
int a[] = {4, 5, 6, 7, 8};
int n = 5;
Stack s;
for(int i = 0; i<n; i++)
push(s, a[i]);
Cho s là Stack chứa các giá trị nguyên, Kết quả của đoạn mã sau là gì?
void main()
{
int n=53, du, b=2;
stack *s;
InitStack(s);
while(n!=0)
{
du = n%b;
Push(s, du);
n = n/b;
}
cout<<“Ket qua la:”;
while( !isEmpty(s))
{
cout<<Pop(s);
}
}
A. 00211
B. 11100
C. 110202
D. 102021
Đâu là định nghĩa của Hàng đợi
A. dạng danh sách đặc biệt trong đó các phép toán thêm vào một phần tử mới hoặc loại bỏ một phần tử trong danh sách chỉ được phép thực hiện ở một đầu của danh sách
B. Cả hai đáp án đều sai
C. Cả hai đáp án đều đúng
D. một kiểu danh sách trong đó được trang bị hai phép toán bổ sung một phần tử vào cuối danh sách và loại bỏ một phần tử ở đầu danh sách
Cho các phần tử 5, 10, 3, 42 lần lượt được bổ sung vào ngăn xếp (Stack). Phần tử nào được lấy ra đầu tiên
Cho đoạn mã cài đặt phương pháp duyệt NLR:
void NLR( Tree Root )
{
if ( root != NULL )
{
< Xử lý Root >; NLR ( Root -> Left );
NLR(Root->Left) ;
[1] ……….
}
}
Đoạn mã điền vào phần trống ở dòng số [1]
A. LRN ( Root -> Right );
B. LRN ( Root -> Left );
C. NLR ( Root -> Right );
D. NLR ( Root -> Left );
Cho biết kết quả khi CTC CreateTree_mang(T) được gọi trong chương trình chính
int insertNode(Tree &T, int x) { if (T != NULL ) { if (T->key == x) return -1; if (T->key > x) return insertNode(T->Left, x); else if (T->key < x) return insertNode(T->Right, x); } T = (Node *) malloc( sizeof (Node)); if (T == NULL ) return 0; T->key = x; T->Left = T->Right = NULL ; return 1; }
void DuyetCay ( Tree T) { if (T!= NULL ) { LNR(T-> Left ); printf( " %7d " ,T-> key ); LNR(T-> Right ); } }
void CreateTree_mang(Tree &T) { int x; int n=7; int a[] = { 8, 6, 10, 4, 9, 7, 11}; for ( int i=0;i<n;i++) { int check = insertNode(T, a[i]); if (check == -1) printf( "\n Node da ton tai!" ); else if (check == 0) printf( "\n Khong du bo nho" ); }
printf( " \n Duyet cay:" ); DuyetCay (T);
}
A. Duyet cay: 4 6 7 8 9 10 11
B. Duyet cay : 8 6 10 4 9 7 11
C. Duyet cay : 8 6 4 7 10 9 11
D. Duyet cay : 4 7 6 9 11 10 8
Bậc của cây có nghĩa là gì?
A. Cả hai phát biểu đều đúng
B. Là bậc nhỏ nhất của các nút trong cây
C. Là bậc lớn nhất của các nút trong cây
D. Cả hai phát biểu đều SAI
Cho cây NPTK, Cho biết kết quả duyệt cây theo thứ tự LRN là:
A. 46, 36, 33, 31, 30, 16, 14, 11, 8, 6
B. 6, 8, 11, 14, 16, 30, 31, 33, 36, 46
C. 8, 6, 14, 16, 11, 33, 31, 46, 36, 30
D. 30, 11, 6, 8, 16, 14, 36, 31, 33, 46
Cho các phần tử sau: 31, 19, 36, 20, 41, 17, 33, 32. Tạo cây NPTK từ các phần tử trên. Hãy cho biết sau khi xóa phần tử 33 trên cây sau đó áp dụng phương pháp duyệt RLN thì kết quả thu được thứ tự các phần tử là như thế nào
A. 31, 19, 36, 20, 41, 17, 32
B. 41, 32, 36, 20, 17, 19, 31
C. 31, 36, 41, 32, 19, 20, 17
D. 41, 36, 32, 31, 20, 19, 17
Bậc của nút trong cây có nghĩa là gì?
A. Là số nhánh con phải của nút đó
B. Là số nhánh con của nút đó
C. Là số nhánh con nhỏ nhất của nút con của nút đó
D. Là số nhánh con trái của nút đó
