GIẢI ĐỀ CẤU TRÚC DỮ LIỆU GIẢI THUẬT

ĐỀ 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! 

b) loại bỏ nút có khóa 65

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)