đề thi CTDL (hình như là của năm ngoái)

Đề thi Demo (anh em tham khảo,hình như là của năm ngoái."hình như" thui.)

Khuyến cáo: KHÔNG NÊN HỌC TỦ

CHÚC ANH EM THI TỐT

Bài 1 :

int F(x,n)

{

if(n==0) return 1;

if(n%2==0)

{

temp=F(x,n/2);

return temp*temp;

}

else

{

temp=F(x,n/2);

return temp*temp*x;

}

}

Gọi T(n) là thời gian tính của thuật toán nói trên .Giả thiết là các phép toán số học được thực hiện với thời gian bị chặn hằng số

a) Xây dựng công thức đệ quy cho T(n)

b) Giải công thức đệ quy đưa ra đánh giá T(n) trong kí hiệu 0

Bài 2

Đối với mỗi một trong các kiểu cấu trúc dữ liệu sau đây : Danh sach nối đơn(Signly-Linked list),Nối kép (Doubly-Linked list) ,Ngăn xếp dung mảng(Stack) ,Hàng đợi dung mảng ( Queue).hãy vẽ cấu trúc dữ liệu thu đc sau khi lần lượt bổ sung các phần tử của dãy các khóa 4,2,6,7,6,5 theo thứ tự trong dãy vào các cấu trúc này ( bắt đầu từ cấu trúc rỗng )

Bài3 :

a) Hãy trình diễn cách sử dụng ngăn xếp để chuyển biểu thức dạng trung tố sau đây về dạng biểu thức hậu tố x-y*z^u+v

b) Hãy trình diễn cách tính giá trị biểu thức hậu tố sau đây nhờ sử dụng ngăn xếp :

1 2 +3 1 +* 2 3 + 4 + /

Bài 4 Cho cây nhị phân sau .Hãy đưa ra thứ tự các đỉnh xđ bởi duyệt cây đã cho theo thứ tự trc ,thứ tự giữa ,thứ tự sau ( bài này quá dễ :)

Bài 5 Xét CTDL trên C để mô tả cây NP tìm kiếm sau đây

Struct TreeNode {

Float key;

struct TreeNode* leftPtr;

struct TreeNode* rightPtr;

};

Typedef struct TreeNode BSTree;

Hãy viết các hàm trên C sử dụng các CTDL trên để thực hiện các thao tác sau đây với cây nhị phân tìm kiếm

Tạo nút mới: BSTree *makeTreeNode(float value);

Bổ sung một nút mới vào BST: BSTree *insert(BSTree *cái_gì_đấy, float cái_gì_đấy);

Với cây nhị phân tìm kiếm đầu vào với tập các khóa S={3,2,5,4,7,6,1} thu đc nhờ thực hiện bổ sung vào cây với Cây nhị phân khởi tạo rỗng

“Cho chúng mày chết

Lại trượt trên 90% rồi. Vui quá”

$ Nghĩa ĐẠI CA $