Bác nào giỏi môn CTDL và Giải thuật giúp em cái!! [Archive]

View Full Version : Bác nào giỏi môn CTDL và Giải thuật giúp em cái!!

jk2tuoi2518

20-12-2010, 22:04

ĐỀ KIỂM TRA TRẮC NGHIỆM
Thời gian 30 phút Số câu: 15
________________________________________
Kiến thức cơ bản
Câu 1: Cấu trúc dữ liệu nào sử dụng kiểu dữ liệu con trỏ để cài đặt?
A : List

B :Linked List

C : Queue

D Stack

________________________________________
Con trỏ
Câu 2: Phương án nào thực hiện đúng nhất thủ tục tạo mới danh sách liên kết đơn L rỗng?
A : New(L);
L := NIL;
B New(L);
L^.NEXT := L;
C : New(L);
L^.NEXT := NIL;
D: L:=NIL;

________________________________________
Độ phức tạp
Câu 3: Những thao tác nào trên danh sách có thời gian thực hiện O(n) nếu nó được cài đặt bằng mảng?
A : INSERT(X: ELEMENTTYPE; P: POSITION; VAR L: LIST);
DELETE(P: POSITION; VAR L: LIST);
B : NEXT(P: POSITION; L:LIST): POSITION;
LOCATE(X: ELEMENTTYPE; L: LIST):POSITION;
C : NEXT(P: POSITION; L:LIST): POSITION;
DELETE(P: POSITION; VAR L: LIST);
LOCATE(X: ELEMENTTYPE; L: LIST):POSITION;
PREVIOUS(P: POSITION; L:LIST): POSITION;
INSERT(X: ELEMENTTYPE; P: POSITION; VAR L: LIST);
PREVIOUS(P: POSITION; L:LIST): POSITION;
Câu 4: Phương án nào gồm hai thao tác có thời gian thực hiện khác nhau trên danh sách liên kết đơn? (hai phương án đúng)
A INSERT(X: ELEMENTTYPE; P: POSITION; VAR L: LIST);
DELETE(P: POSITION; VAR L: LIST);
B NEXT(P: POSITION; L:LIST): POSITION;
LOCATE(X: ELEMENTTYPE; L: LIST):POSITION;
C NEXT(P: POSITION; L:LIST): POSITION;
DELETE(P: POSITION; VAR L: LIST);
D LOCATE(X: ELEMENTTYPE; L: LIST):POSITION;
PREVIOUS(P: POSITION; L:LIST): POSITION;
E INSERT(X: ELEMENTTYPE; P: POSITION; VAR L: LIST);
PREVIOUS(P: POSITION; L:LIST): POSITION;
Chon Nhieu phuong an tuy y
________________________________________
Cài đặt DS liên kết
Câu 5: Đoạn mã nào thể hiện đúng nhất phép bổ sung phần tử X vào trước phần tử ở vị trí P danh sách liên kết đơn L?
a)
http://i498.photobucket.com/albums/rr350/jk2tuoi/Cau5.jpg
Đây là hình ảnh câu 5 các bác xem rùi hỗ trợ em cái:plaster:

b)

c)

d)

Câu 6: Đoạn mã nào thể hiện đúng nhất phép bổ sung phần tử X vào sau phần tử ở vị trí P danh sách liên kết vòng L?
a)

b)

c)

d)

________________________________________
Stack
Câu 7: Trạng thái nào của stack xuất hiện trong quá trình chuyển biểu thức 12/(2+1)/3+5-2 về dạng RPN (Reverse Polish Notation)?
a)

b)

c)

d)

________________________________________
Tính giá trị biểu thức
Câu 8: Lựa chọn nào biểu thị dạng postfix của biểu thức 2*4+(17-5)/3/2?
a)

b)

c)

d)

________________________________________
Duyệt cây
Câu 9:

a)

b)

c)

d)

________________________________________
Mã Huffman
Câu 10: Độ dài mong đợi (Expected Length) khi mã hóa xâu "CU RUA NGHIN TUOI" theo phương pháp Huffman?
57

56

55

54

53

Câu 11: Độ dài mong đợi (Expected Length) khi mã hóa xâu "NUOC NON NGHIN DAM" theo phương pháp Huffman?
59

58

57

56

________________________________________
Cây tìm kiếm nhị phân
Câu 12: Thời gian chạy của phép bổ sung một phần tử vào Cây tìm kiếm nhị phân (BST) trong trường hợp tốt nhất là
O(1)

O(log(n))

O(n^2)

O(n)

________________________________________
heap
Câu 13: Mảng nào dưới đây là heap
(50, 38, 27, 49, 16)

(50, 16, 27, 38, 49)

(50, 38, 49, 16, 27)

(16, 27, 38, 49, 50)

________________________________________
Đường đi ngắn nhất
Câu 14:

a)

b)

c)

d)

________________________________________
Thời gian chạy
Câu 15: Thời gian chạy của giải thuật sắp xếp chọn (SELECTION SORT) là
O(1)

O(n.log(n))

O(n^2)

O(n)

jk2tuoi2518

20-12-2010, 22:05

Mấy câu ko có hình ảnh các bác giúp em cái thuật toán nhé:D

hidingrig

20-12-2010, 22:06

15 D :surrender:

Baby dont cry

20-12-2010, 22:07

Cấu trúc dữ liệu và giải thuật hôm rồi thi cuối kì làm đc có 1,5 trên tổng 4 câu... Thôi đi ra... :go:

trantienvi

20-12-2010, 22:09

Chủ thớt mấy câu 5->.... có thấy j đâu mà trả lời,up lại đi, câu cú ghi gần nhau đọc mún lòi con mắt ra

tieuphong29785

20-12-2010, 23:15

Co đúng là CTDU và giải thuật ko đó? Em đọc xong chẳng hiểu cái mô gì ? không biết là ngày xưa em có học đúng môn đó không hay là học cái gì nữa không biết :(

Ánh Dương™

20-12-2010, 23:26

Sao mình học SQL thôi nhỉ ... TC học đánh code lấy ra từ 1 bảng ..... Để sau này xài ASP chả biết như bác này sau này làm sao liên thông ?

thange398

20-12-2010, 23:35

cố mà học đi bạn trẻ nếu học cntt thì thi tốt nghiệp chắc chắn có môn này đấy :)

caothucuchuoi

20-12-2010, 23:43

môn này mình được ông thầy Trưởng khoa dạy mà vẫn không hiểu cái cm gì cả :lmao:

c12051991

20-12-2010, 23:46

em sắp thi môn này mà chả có tý gì trong đầu

longthanhhm

20-12-2010, 23:46

học lại đê!
hồi xưa cũng học lại môn này :(

quangredlight

20-12-2010, 23:47

P/s : lần sau bác đừng đặt tên topic là bác nào giỏi thì làm cái này cái nọ, nghe phản cảm lắm, ở đời chẳng có ai giỏi cả, chỉ có ai biết hay không thôi. Nhiều cái em muốn giúp nhưng thấy tên topic là "bác nào giỏi..." thì em hết cả hứng. (Đây là ý kiến cá nhân em thôi, còn nếu bác thích đặt thế thì em cũng chẳng ý kiến gì nữa)

Câu 1: Cấu trúc dữ liệu nào sử dụng kiểu dữ liệu con trỏ để cài đặt?
B :Linked List
C : Queue
D Stack

Cả 3 kiểu này em đều chơi con trỏ được, mà thực ra cả 4 kiểu chơi con trỏ đều được
________________________________________
Con trỏ
Câu 2: Phương án nào thực hiện đúng nhất thủ tục tạo mới danh sách liên kết đơn L rỗng?
C : New(L);
L^.NEXT := NIL;

________________________________________
Độ phức tạp
Câu 3: Những thao tác nào trên danh sách có thời gian thực hiện O(n) nếu nó được cài đặt bằng mảng?
C : NEXT(P: POSITION; L:LIST): POSITION;
DELETE(P: POSITION; VAR L: LIST);
LOCATE(X: ELEMENTTYPE; L: LIST):POSITION;
PREVIOUS(P: POSITION; L:LIST): POSITION;
INSERT(X: ELEMENTTYPE; P: POSITION; VAR L: LIST);
PREVIOUS(P: POSITION; L:LIST): POSITION;
Câu 4: Phương án nào gồm hai thao tác có thời gian thực hiện khác nhau trên danh sách liên kết đơn? (hai phương án đúng)
Trông hoa cả mắt

Câu 5: Đoạn mã nào thể hiện đúng nhất phép bổ sung phần tử X vào trước phần tử ở vị trí P danh sách liên kết đơn L?
Câu 6: Đoạn mã nào thể hiện đúng nhất phép bổ sung phần tử X vào sau phần tử ở vị trí P danh sách liên kết vòng L?
Câu 7: Trạng thái nào của stack xuất hiện trong quá trình chuyển biểu thức 12/(2+1)/3+5-2 về dạng RPN (Reverse Polish Notation)?
Câu 8: Lựa chọn nào biểu thị dạng postfix của biểu thức 2*4+(17-5)/3/2?
Câu 9:
Câu 10: Độ dài mong đợi (Expected Length) khi mã hóa xâu "CU RUA NGHIN TUOI" theo phương pháp Huffman?
Không biết
Câu 11: Độ dài mong đợi (Expected Length) khi mã hóa xâu "NUOC NON NGHIN DAM" theo phương pháp Huffman?
Không biết
________________________________________
Cây tìm kiếm nhị phân
Câu 12: Thời gian chạy của phép bổ sung một phần tử vào Cây tìm kiếm nhị phân (BST) trong trường hợp tốt nhất là
O(log(n))
Câu 15: Thời gian chạy của giải thuật sắp xếp chọn (SELECTION SORT) là
O(n^2)

jk2tuoi2518

20-12-2010, 23:48

môn này mình được ông thầy Trưởng khoa dạy mà vẫn không hiểu cái cm gì cả :lmao:
ÔNg tùng hả bác Trưởng cái ông nói lắm đúng ko tính như đàn bà:hell_boy:

tamchec

20-12-2010, 23:52

15 D :surrender:

QuickSort đã O(nlog(n)) rồi bác ạ. Cái này là O(n2)

jk2tuoi2518

20-12-2010, 23:53

Em up cho các bác xem nhé
có gì giúp em:D

jk2tuoi2518

21-12-2010, 00:00

Em up tí ảnh 2 câu 7,8,9 các bác cho em cái đáp án nhé:D

lostninja

21-12-2010, 00:02

1. B
15. C thì phải

jk2tuoi2518

21-12-2010, 00:03

1. B
15. C thì phải
Thank bác :D các bác tiếp tục đi ạ

tssghost

21-12-2010, 00:07

1 B - linked list mới dùng con trỏ, 3 cái kia đều dùng mảng

2 C : New(L);
L^.NEXT := NIL;

3 A

4 C, D

mấy câu dưới có thuật toán, bác viết chương trình rồi nhập biểu thức vào nó tự tính ra xem. Lâu rồi lười làm :D

tamchec

21-12-2010, 00:10

Câu 5: Đoạn mã nào thể hiện đúng nhất phép bổ sung phần tử X vào trước phần tử ở vị trí P danh sách liên kết đơn L?
G/sử head là con trỏ đầu trong ds L:
tmp = head;
while(tmp.next().index !=P) tmp = tmp.next();
tmp2 = tmp.next();
tmp.next = X;
X.next = tmp2;

Câu 6: Đoạn mã nào thể hiện đúng nhất phép bổ sung phần tử X vào sau phần tử ở vị trí P danh sách liên kết vòng L?
Tương tự câu 5

Tính giá trị biểu thức
Câu 8: Lựa chọn nào biểu thị dạng postfix của biểu thức 2*4+(17-5)/3/2?
4 2 * 17 5 - 3 / 2 / +

Câu 13: Mảng nào dưới đây là heap
(50, 38, 27, 49, 16)

(50, 16, 27, 38, 49)

(50, 38, 49, 16, 27)

(16, 27, 38, 49, 50)
Câu này thấy 2 đáp án cuối đều đúng :(

nmadtu

21-12-2010, 00:44

nhìn đống chữ kia nhức hết cả đầu rồi, bác ko bỏ vào <code> ý cho nó rõ >"<</code>

jk2tuoi2518

21-12-2010, 12:34

Em bỏ đc vào code đã tốt:((

jk2tuoi2518

21-12-2010, 12:35

Câu 5: Đoạn mã nào thể hiện đúng nhất phép bổ sung phần tử X vào trước phần tử ở vị trí P danh sách liên kết đơn L?
G/sử head là con trỏ đầu trong ds L:

Câu 6: Đoạn mã nào thể hiện đúng nhất phép bổ sung phần tử X vào sau phần tử ở vị trí P danh sách liên kết vòng L?
Tương tự câu 5

Tính giá trị biểu thức
Câu 8: Lựa chọn nào biểu thị dạng postfix của biểu thức 2*4+(17-5)/3/2?
4 2 * 17 5 - 3 / 2 / +

Câu 13: Mảng nào dưới đây là heap
(50, 38, 27, 49, 16)

(50, 16, 27, 38, 49)

(50, 38, 49, 16, 27)

(16, 27, 38, 49, 50)
Câu này thấy 2 đáp án cuối đều đúng :(
Em cảm ơn bác rất nhiều ạ.mẹ cái thằng thấy cho đề chắc nghiệm mà đáp án làm toàn ra sai ( Rõ ràng là sách nói vây) con bạn em học pro môn này mà làm kiểm tra 4 điểm đéo hiểu luôn.Cãi nhau thằng già bắt đầu dở bài cùi

Mr.Win

21-12-2010, 13:18

nhìn pascal hoa hết cả mắt mình học cấu trúc dữ liệu này ổng dạy trên C++ :shot:

forcefx

21-12-2010, 13:22

môn này mình được ông thầy Trưởng khoa dạy mà vẫn không hiểu cái cm gì cả :lmao:

bác học KHTN à :byebye:

xonglennao

21-12-2010, 13:26

Câu 7 : Mình không thấy đáp án nào hợp lý

câu 8 : D

Câu 9 : D

Câu 10 : 57

Câu 11 : 55 ( Đáp án có số 55 không ? )

beheaded style

21-12-2010, 13:33

em sắp thi môn này mà chả có tý gì trong đầu

không cần phải học bợn ạh tích đức nhiều là qua hết thôi(kinh nghiệm của mềnh):sexy::sexy:

baolan2005

21-12-2010, 13:38

Trường mình dạy môn này không ra mấy cái đề như vậy đâu, chủ yếu là tư duy lý thuyết thôi. Chứ ra mấy cái này là chết chắc :D

xonglennao

21-12-2010, 13:44

câu 13 ý, chỉ có cái cuối là đúng thôi.

heap nó phải như này
---------38--------
-----27------49----
---16----------50--

Heap là cha lớn ( nhỏ ) hơn 2 phần tử con cơ mà . Cái của bạn là cây nhị phân tìm kiếm rồi .

nmadtu

21-12-2010, 13:52

Heap là cha lớn ( nhỏ ) hơn 2 phần tử con cơ mà . Cái của bạn là cây nhị phân tìm kiếm rồi .

chết, nhầm rồi :shot:

jk2tuoi2518

21-12-2010, 14:09

Câu 7 : Mình không thấy đáp án nào hợp lý

câu 8 : D

Câu 9 : D

Câu 10 : 57

Câu 11 : 55 ( Đáp án có số 55 không ? )

tHANK Bác Rất nhiều

12c1demon

21-12-2010, 14:23

hình như câu 7 là B các bác ợ

jk2tuoi2518

21-12-2010, 14:27

hình như câu 7 là B các bác ợ
Hình như hay chính xác bác Em cảm ơn bác trước đã nhé:D

tamchec

21-12-2010, 14:36

hình như câu 7 là B các bác ợ

Câu này ko có đáp án nào chính xác :-s

jk2tuoi2518

23-12-2010, 23:46

SUtsssssss

yreimm0308n90

24-12-2010, 00:53

Tớ điểm quá trình 9. Thi lần 1 được 3, lần 2 được 7 :D
Số mình cũng lạ điểm quá trình lúc nào cũng cao mà điểm thi toàn như điên :D