Xin đề thi môn cấu trúc dữ liệu và giải thuật

#1

Ai có đề thi môn này không?ở BKHN thì càng tốt,mình không biết đề sẽ hỏi code hay thuật toán ?

#2

Nhập xuất Danh sách sinh viên
Thêm đầu thêm cuối
Xóa .

=>>> Đó là những gì mình làm bài KTr giữa kì trong trường :smiley:

1 Like
#3

cảm ơn bạn! bạn ơi,bạn ghi rõ đề bài cho mình được không ? không hiểu đề bài lắm!!

#4

Bạn Học thầy nào.nếu thầy dũng thì t biết đó

2 Likes
#5

chuẩn men,thầy dũng code đây

#6

Các bác cho em hỏi là môn cấu trúc dữ liệu và giải thuật này học với thi là phải viết bằng C/C++ hoàn chỉnh 1 chương trình hay bằng giả ngữ ạ. Tại kì sau mới được học với xem qua 1 sách toàn viết bằng giả ngữ đại ý chung chung.

1 Like
#7

mình nghĩ nếu thế thì thi bằng viết code c/c++, nhưng mà lập trình trên giấy thì chỉ cần code sơ qua thôi, lỗi là điều không thể thoát khỏi

#8

Cho mình xin đề với !

#9

Bài 1. Xét thuật toán tính giá trị của f(x,n)= thể hiện trong hàm F(x,n) sau đây:

int F(int x, int n)
{
if (n= =0) return 1;
else if (n % 2 = = 0) return F(x,n/2)*F(x,n/2);
else return F(x,n/2)*F(x,n/2)*x;
}

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

a. Xác định công thức đệ quy cho T(n).
b. Giải công thức đệ quy để đưa ra đánh giá của T(n) trong tình huống tồi nhất.

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 sách nối đơn, danh sách nối kép, hàng đợi dùng mảng.Hãy vẽ cấu trúc dữ liệu có đượ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

Bài 3.
a. Biểu diễn cách sử dụng ngăn xếp để chuyển biểu thức dạng trung tố về dạng hậu tố: a – b * c ^ d – f
b. Hãy trình diễn cách tính giá trị của biểu thức hậu tố sau sử dụng ngăn xếp: 1 2 + 3 1 + * 1 1 + 1 - /

Bài 4. Cho cây nhị phân ở hình bên.Hãy đưa ra thứ tự các đỉnh xác định bởi duyệt cây theo thứ tự trước, giữa, sau.

Ấn vào hình để xem hình to hơn

Tên: Screenshot from 2012-05-07 21:42:53.png
Xem: 306
KT : 16,5 KB
ID : 2803

Bài 5. Cho mảng A=(0,2,4,3,8,9,6,5,7) biểu diễn 1 Min-heap.
a. Vẽ cây nhị phân tương ứng với Min-heap đã cho.
b. Trình bày các thao tác cần thực hiện trên cây để bổ sung thêm key=1 vào min-heap nói trên để thu được 1 min-heap mới.

Bài 6.

struct TreeNode {
float key;
struct TreeNode * LeftPtr;
struct TreeNode * RightPtr;
};
typedef struct TreeNode BSTree;

a. Hãy viết hàm C sử dụng cấu trúc dữ liệu trên để thực hiện các thao tác sau đây với cây nhị phân.
● Tạo một nút mới.

BSTree *makeTreeNode(float value);

● Bổ sung một nút mới vào cây nhị phân tìm kiếm.

BSTree *insert(BSTree * nodePtr, float item);

b) Vẽ cây nhị phân tìm kiếm đối 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 lần lượt các khóa theo thứ tự đã cho vào cây nhị phân.Khởi tạo ban đầu là rỗng

mới sưu tầm được, đang cày cuốc :satisfied:

4 Likes
#10

giữa kì : 1. viết hàm đệ quy tính tổng (x+y+z)^n
2. viết hàm nối 2 danh sách theo thứ tự tăng dần

#11

à, nếu học thầy dũng thì học kĩ phần độ phức tạp của thuật toán nhé, tuy thầy dạy qua loa phần này nhưng đi thi câu nào cũng có 1 ý tính độ phức tạp

#12

thi xong rồi, thảm sát tại phòng thi :smile: :smile: :smile:

#13

anh còn đề cấu truc DL giữa kì của thầy Dũng không cho em tham khảo với

#14

anh ơi anh còn nhớ cấu trúc đề thi cuối kì của thầy không ạ? thầy nói thi ôn hết không định hướng bọn em cũng hoang mang

#15

anh ơi giờ anh còn nhớ cấu trúc đề thi cuối kì của thầy không ạ?

#16

anh ơi anh còn nhớ cấu trúc đề thi cuối kì của thầy DŨng k ạ?

#17

Bài 1.
a) Đánh giá độ phức tạp của hàm đệ quy sau theo O- lớn

void fn(int n)
{
	if ( n <= 0) return 1;
	return fn(n-1) + fn(n-1);
}

b) Cho biểu thức trung tố sau

        2*a/(b-c)*b + 2/b

Hãy xây tìm biểu thức dạng hậu tố và dựng cây biểu thức tương ứng.
c) Trong một văn bản HTML các tag là hợp lệ nếu đủ thẻ mở vè thẻ đóng.
VD
Hãy mô tả thuật toán dùng để kiểm tra văn bản HTML có hợp lệ hay không,và nếu không hợp lệ thì tag nào là tag ko hợp lệ đầu tiên.

Bài 2.Phần tử trung vị là phần tử có giá trị không nhỏ hơn, cũng không lớn hơn các phần tử còn lại. Ví dụ:

  • Cho danh sách 4 phần tử sau: 3,7,2,9 thì phần tử trung vị là 3

  • Cho danh sách 5 phần tử sau: 3,5,7,2,9 thì phần tử trung vị là 5
    Gỉa sử ta cần đặt STACK để thực hiện các thao tác

  • push: đẩy 1 phần tử vào STACK

  • pop: lấy ra 1 phần tử khỏi STACK

  • getMedian : trả về trung vị của phần tử

  • size : trả về số lượng phần tử trong STACK
    Hãy mô tả cấu trúc dữ liệu cũng như cách thực hiện các thao tác này sao cho **thời gian thực hiện của các thao tác không quá 0(1)

Các bác giúp e vs ạ

1 Like
#18

1a là O(F(n)), không cần tới theta thì ghi là 2 mũ thôi.
1c xài stack đi :smiley:

Lấy trung vị trong O(1)? Mà định nghĩa cũng trật lất.

1 Like
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?