Data Structures

Step 1: Understanding postfix evaluation.
In postfix expressions, operands are pushed onto a stack. When an operator appears, the top two operands are popped, the operation is performed, and the result is pushed back.
Step 2: Evaluating the expression step by step.

Step 3: Applying operators.

Step 4: Final computation.

Step 5: Final conclusion.
The value of the given postfix expression is 10.

Step 1: Understand the recursive calls.
The function makes recursive calls only when . For , the function simply returns 1 without making further calls.
Step 2: Expand the call .

Step 3: Expand and .

Step 4: Count the number of times is called.
From the expansions above:
- One call to comes from
- One call to comes from inside
- One call to comes from inside
Total number of calls to =
Step 5: Final conclusion.
Therefore, when is executed, the function is called exactly 3 times.

Step 1: Understanding singly linked lists.
In a singly linked list, each node contains a data field and a pointer to the next node only. There is no pointer to the previous node.
Step 2: Analyzing given operations.
- Deleting the first node requires only updating the head pointer.
- Inserting at the beginning requires only updating the head pointer.
- Inserting at the end can be done directly using the tail pointer.
Step 3: Identifying the operation requiring traversal.
To delete the last node, we must find the second-last node so that its next pointer can be set to \texttt{NULL}. This requires traversing the list from the head.
Step 4: Final conclusion.
Therefore, deleting the last node of a singly linked list requires traversal.

Step 1: Understanding Bellman-Ford algorithm.
The Bellman-Ford algorithm computes the shortest paths from a single source to all other vertices by repeatedly relaxing all edges in the graph.
Step 2: Determining the number of edges.
In a completely connected (complete) graph with vertices, the number of edges is:
Step 3: Analyzing the number of iterations.
The Bellman-Ford algorithm relaxes all edges exactly times.
Step 4: Computing total time complexity.

Step 5: Final conclusion.
Hence, the time complexity of the Bellman-Ford algorithm on a complete graph is .

Step 1: Understanding binary tree links.
In a binary tree, each node has exactly two child pointers: one left child pointer and one right child pointer. Therefore, for a tree with nodes, the total number of child pointers is .
Step 2: Counting non-null links.
In any tree with nodes, there are exactly edges (links connecting parent and child nodes). These edges correspond to the non-null child pointers in the binary tree.
Step 3: Calculating null links.
Out of the total child pointers, are non-null. Hence, the number of null links is:
Step 4: Final conclusion.
Thus, an arbitrary binary tree with nodes contains exactly null links.

Step 1: Understanding binary search.
Binary search works by comparing the target element with the middle element of the sorted array. Based on this comparison, the algorithm discards half of the array and continues searching in the remaining half.
Step 2: Analyzing the work done at each step.
At each step, the size of the problem reduces from to . Apart from this reduction, only a constant amount of work is done for comparison.
Step 3: Forming the recurrence relation.
Since the problem size is halved and only constant time is spent at each level, the recurrence relation is:
Step 4: Final conclusion.
Therefore, the correct recurrence relation representing binary search is .