0
GIẢI ĐỀ CẤU TRÚC DỮ LIỆU GIẢI THUẬT
Posted by chazo1994
on
08:08
in
Lập trình
 |
| ĐỀ BÀI |
BÀI 1
gọi T(n) là thời gian tính của bài toán
ta có thời gian tính mỗi bài toán con là T(n/2)
và có 2 bài toán con!
vậy thời gian tình của thuật toán đệ quy là
T(n)=2*T(n/2)+n+7=2*T(n/2)+O(n)
ta có a=2; b=2; k=1;
áp dụng định lý thợ rút gọn ta có a=b^k;
suy ra T(n)=O(nlogn);
BÀI 2
#include<iostream>
using namespace std;
struct linkedlist
{
int data;
struct linkedlist *next;
};
typedef struct linkedlist node;
int deletep(node *p)
{
int temp = p->data;
node *t = p->next;
p->data = t->data;
p->next = t->next;
delete t;
t = NULL;
return temp;
}
BÀI 3
a)biểu thức hậu tố!
28 4 2 + * 24 38 - 28 14 / * /
b) trình diễn thuật toán:
khởi tạo ngăn xếp rỗng
b1: duyệt biểu thức từ trái qua phải
b2: nếu gặp toán hạng thì (push) đưa giá trị của nó vào ngăn xếp
b3: nếu gặp phép toán thì thực hiện phép toán này với hai toán hạng được lấy ra (pop) từ ngăn xếp
b4: cất giữ (push) giá trị tính được vào ngăn xếp
b5: tiếp tục duyệt cho đến khi trong ngăn xếp chỉ còn một giá trj duy nhất đó là kết quả của biểu thức
BÀI 4
a) cây nhị phân tìm kiếm!
b1: tìm nút có khóa chứa giá trị nhỏ nhất trong cây con phải của nut 65 là nut có khóa 68
b2: gỡ nút có khóa 68 khỏi cây
b3: nối con phải của nút 68 vào cha của nút 68
b4: thay thế nút 68 vào nút 65.
BÀI 5
Function max_heap_check(A(1..n))
begin
integer i;
for i=1 to [n/2] do
if A[i]>A[2*i] or A[i]>A[2*i+1] then
return false;
endif;
endfor;
return true;
end;
đánh giá thời gian tính:
gọi T(n) là thời gian tính của thuật toán ta có:
T(n)<=[n/2]+6
=> T(n)=O(n)
