LÝ THUYẾT LẬP TRÌNH

32 flashcards · Other · by Minh Đức

1. các bước của binary search

   gán giá trị min = index của phần tử đầu tiên gán giá trị max = index cuối cùng biến guess = (max + min)/2 xong làm tròn xuống vòng lặp while với đk max > min check nếu number >arr[ guess:] max = guess - 1 nếu number <arr[ guess]: min = guess + 1 nếu number == arr[guess] break

2. asymptoptic notation

   big O: f(n) < g(n) big Omega: f(n) > g(n) big Theta: f(n) = g(n)

3. các bước của selection sort

   tạo các biến i,small,j outer loop i =0; i<n-1, i = small inner loop j = i+1; j<n check nếu arr[small] < arr[j] thì small = j 4 sau inner loop, swap arr[i] và arr[small]

4. các bước của insertion sort

   phần tử đầu tiên thì đã được sort sẵn khai báo biến value,và biến index outer for loop i =1; i<n; index = i , value = arr[i] inner while loop index > 0 && value < arr[index - 1] arr[index] = arr[index - 1] index = index - 1 sau innner while loop arr[index] = value

5. 2 quy tắc của đệ quy

   khi đệ quy luôn gọi lại hàm đệ quy nhưng giải quyết ở subproblem subproblem đến 1 mức base case có thể ko cần gọi lại hàm nhưng vẫn ra kết quả

6. cách làm của tower of hanoi

   chuyển n - 1 đĩa từ from_rod đến aux_rod chuyển đĩa thứ n từ from rod đến to_rod chuyễn n-1 đĩa từ aux_rod đến to_rod

7. ý chính của merge sort

   chia mảng thành 2 subarray sort 2 subarray bằng cách lại chia nhỏ nó ra và merge merge 2 subarray đã được sort

8. số phần tử của 2 sub array trong merge sort

   n1 = r - m n2 = m - l + 1

9. khi dùng merge sort cần dùng những hàm nào

   hàm merge để gộp các subarray hàm mergesort để có thể recursive

10. cách viết hàm mergesort

    if (l < r) m = ( l + r) / 2 mergesort (arr, l , m ) mergesort (arr, m + 1, r) merge (arr, l , m, r)

11. tham số của hàm merge là gì

    arr[], l , m , r

12. các bước của hàm merge

    tạo biến index i ,j ,k cho các subarray và original array tạo mảng L[n1] và H[n2] để sao chép các phần tử của subarray while ( i < n1 && j <n2 ) so sánh giữa L[i] và H[j], cái nào bé hơn thì gán cho arr[k] k ++, còn giữa i và j thì cái nào gán cái đó ++ sau đó gán tiếp những cái còn thừa của các subarray

13. ý chính của quick sort

    chọn phần tử rightmost làm pivot sau đó sắp xếp sao cho bên phải pivot toàn những phần tử nhỏ hơn, bên trái là các phần tử lớn hơn tiếp tục quicksort subarray bên trái và phải của pivot

14. điều kiện cho cả mergesort và quicksort là gì

    if ( l < r )

15. hàm quicksort cần 2 hàm nào

    hàm partition() để xếp pivot về đúng vị trí và sắp xếp các phần tử về 2 bên, hàm trả về index của pivot hàm quicksort() để có thể gọi đệ quy

16. parameter của hàm quicksort()

    arr[], int low , int high

17. cách viết hàm quicksort()

    if ( low < high ) int pi = partition(arr,int low, int high) quicksort (arr, low , pi - 1) quicksort (arr, pi + 1, high)

18. parameter của hàm partition()

    arr[], int low, int high

19. cách viết hàm partition()

    tạo i,j để làm 2 biến đếm với i = low - 1, j = low tạo biến pivot = arr[high] tạo 1 vòng for (j = low; j <= high - 1; j++) if ( arr [j] < pivot ) thì i++, swap arr[j] và arr[i] hết vòng for thì swap pivot với arr[i + 1] để đưa pivot về đúng vị trí return index của pivot để tiếp tục recursive i + 1

20. các node trong liên kết đơn gồm những gì

    data con trỏ kiểu struct trỏ đến node tiếp theo

21. để dùng dslk đơn, ta dùng cái j

    struct

22. ưu điểm của dslk đơn

    có kích thước động có thể dễ dàng thêm, xóa phần tử

23. nhược điểm của dslk đơn

    phải truy cập linear, ko thể truy cập ngẫu nhiên dùng index như mảng tốn thêm bộ nhớ để lưu con trỏ ko thân thiện vs bộ nhớ cache

24. các bước để tạo 1 node head với struct Node, int data, Node *next; và gán giá trị data của node head = 1

    đầu tiên phải tạo 1 node bằng cách cấp phát bộ nhớ cho nó node *head = new node(); sau đó gán giá giá trị cho node như với biến của struct. head -> data = 1;

25. cách để liên kết node head và node second

    head -> next = second

26. muốn tạo 1 biến int data mang dữ liệu của data của node head

    int data = head -> data

27. cách để duyệt dslk đơn

    tạo 1 node trung gian Node *p = new Node() sử dùng vòng for để duyệt hết for ( p = head; p != NULL; p = p->next)

28. cách truyền các phần tử vào subarray trong hàm merge

    L[i] = arr[left +i] H[j] = arr[mid+1 + j]

29. biến k trong hàm merge bằng cái gì

    left

30. với hash table , ta có thể :

    lưu cả key và value vào 1 index trong hash table

31. concept chính của hash table

    ta compute key được hash code, từ hash code ta lại tiếp tục compute để ra được index xong lưu cả key và value vào index đó

32. cách chính để hash từ key ra hash code

    nếu là number thì number % table size nếu là string thì tổng ascii của string đó % table size