Cấu trúc dữ liệu và giải thuật - CĐ(2010)

Môn Thi Cấu Trúc Dữ Liệu Và giải thuật

Đề :90 min

Bài 1:

a, Trình bày sự khác biệt giữa mảng cấp phát tĩnh và mảng cấp phát động? khi nào dùng mảng cấp phát tĩnh, khi nào dùng mảng cấp phát đọng?cho VD.

b, đánh giá thời gian thực hiện của thuật toán sau:

          double fastpower (double x, int n)

          {

                   double tract;

                   if (n==0) return 1;

                   tract = fastpower (x, n/2);

                  

                   if ( n% 2==0) return tract*tract;

                   else return tract*tract*x;

}

Thuật toán thực hiện tính x­­­­ⁿ

Bài 2:

a, trong các phương pháp sắp xếp : lựa chọn, chèn, đổi chỗ, quicksort , mẻgwsort thì phương pháp nào là hợp nhất để sắp xếp trên mảng với số lượng phần tử lớn? giải thích lựa chon của bạn.

b, cho mảng : A={ 14, 45, 21, 12, 7 ,87, 25, 56, 91, 64, 33, 41, 72, 89, 62}

hãy minh họa lần lặp thứ nhất của thuật toán sắp xếp nổi bọt trên A

( bài nay làm nhầm đi sắp xếp luôn, hehe làm tốn thời gian )

Bài 3.

A, hàng đợi vòng là j? tác dụng của việc tổ chức hàng đợi vòng?

B, Áp dụng thuật toán định giá trị của biểu thức hậu tố bằng stack để tính giá trị biểu thức dưới dạng hậu tố sau

( cần nêu rõ bước trung gian trong qua trình tính )

15  2  3  +  /  2  ^  4  12  2  -  %  +

Bài 4:cho đồ thị dưới đây

a, biểu diễn đồ thị dùng ma trận kề.

b, thực hiện thuật toán PRIM và đưa ra cây khung có trọng số min( có nêu rõ từng bước)

kick vao hinh de nhin ro.

Bài 5: viết hàm nhận đầu vào là 1 ma trận kề biểu diễn cho 1 đồ thị vô hướng , và số lượng đỉnh trên đồ thị.

Hàm kiểm tra xem đồ thị có liên thông hay không. Nếu có thì hàm trả về giá trị là 1, nếu không liên thông hàm trả về giá trị 0.

Int ktlienthong ( int Adj[100] [100] , int n)

{

// thân hàm

}

Với n là số đỉnh (0<n<=100)

Đánh giá thời gian thực hiên thuật toán trên theo O-lớn.