4. Let us consider the recurrence T(n) = T( n / 2 ) + T( n / 2 ) + 1 for any positive integer n. Use mathematical induction to show that T(n) ≤ cn for some positive number c. (10分)

7. 使用 linked list 實作 stack，運用以下 C 語言程式：typedef struct node { int value; node *next;}void push (node **top, int new_value) { // assume top is not nullnode new_node = (node ) malloc (sizeof (node));// (A) 實作以下敘述 (5 分)// add new_node to stack by top}int pop (node **top) { // assume top is not nullint value;node deleting_node = top;// (B) 實作以下敘述(5 分)// remove the deleting node from stack, get the value of deleting nodefree(deleting_node);return value;}

4. Let us consider the recurrence \( T(n) = T(\lfloor n / 2 \rfloor) + T(\lceil n / 2 \rceil) + 1 \) for any positive integer \( n \). Use mathematical induction to show that \( T(n) \leq cn \) for some positive number \( c \). (10分)

相關申論題

相關試卷