Dynamic Memory
Which memory allocation technique provides better locality of reference for accessing array elements?
A
Allocating each element separately with malloc
B
Single malloc for contiguous array
C
Using static arrays
D
Allocating with calloc for zeroed memory
Correct Answer:
B. Single malloc for contiguous array
Contiguous allocation places array elements next to each other in memory, improving cache hits and CPU performance through spatial locality.
In competitive coding, when implementing dynamic trees, which traversal is most suitable for level-order?
A
Recursion with DFS
B
Stack-based iteration
C
Queue-based BFS using dynamic allocation
D
In-order traversal
Correct Answer:
C. Queue-based BFS using dynamic allocation
Level-order traversal requires BFS which uses a queue. Dynamic queue allocation handles arbitrary tree sizes efficiently.
What is the memory overhead when allocating 1000 integers vs 1 integer in a system with malloc metadata?
A
Negligible difference
B
Proportional to number of allocations
C
Fixed overhead per allocation regardless of size
D
Exponential with allocation count
Correct Answer:
C. Fixed overhead per allocation regardless of size
Each malloc() call has fixed metadata overhead (typically 8-16 bytes). Single allocation of 1000 ints has less overhead than 1000 separate allocations.
For a dynamic hash table with chaining, if collision occurs, the new element should be inserted where?
A
Always at the beginning of the chain
B
Always at the end of the chain
C
In sorted position
D
Depends on implementation, typically at beginning for O(1)
Correct Answer:
D. Depends on implementation, typically at beginning for O(1)
While both work, inserting at beginning provides O(1) insertion; end requires traversal. Choice depends on use case.
In implementing a dynamic doubly-linked list, what additional field is required compared to singly-linked list?
A
Data field
B
Previous pointer
C
Size field
D
Head pointer
Correct Answer:
B. Previous pointer
Doubly-linked list nodes require both next and previous pointers to enable bidirectional traversal unlike singly-linked lists.
If malloc() returns NULL, what should a program do?
A
Ignore and continue using the pointer
B
Check for NULL and handle the error appropriately
C
Always typecast the return value
D
Use global variables instead
Correct Answer:
B. Check for NULL and handle the error appropriately
NULL return from malloc indicates allocation failure; ignoring causes dereferencing NULL which leads to crash.
What is the correct way to store variable-length strings dynamically?
A
char str[MAX]; gets(str);
B
char *str = (char*)malloc(length+1); fgets(str, length+1, stdin);
C
char *str; scanf("%s", str);
D
char str[] = malloc(100);
Correct Answer:
B. char *str = (char*)malloc(length+1); fgets(str, length+1, stdin);
Proper way requires dynamic allocation with malloc, adding 1 for null terminator, and using fgets for safe input.
In competitive programming for graph problems, if adjacency list uses dynamic arrays, what is the time complexity of adding an edge?
A
O(1) amortized
B
O(n)
C
O(log n)
D
O(n²)
Correct Answer:
A. O(1) amortized
Using dynamic arrays (vectors in C++) with doubling strategy provides O(1) amortized time for appending edges.
Which scenario is most likely to cause a segmentation fault in dynamic memory?
A
Calling malloc() multiple times
B
Accessing memory beyond allocated size
C
Freeing NULL pointer
D
Calling realloc() on allocated memory
Correct Answer:
B. Accessing memory beyond allocated size
Buffer overflow by accessing beyond allocated boundaries causes segmentation fault as it accesses invalid memory pages.
For implementing a dynamic circular buffer of size n, how many pointers are minimally required?
A
1 pointer
B
2 pointers
C
3 pointers
D
4 pointers
Correct Answer:
B. 2 pointers
A circular buffer requires head and tail pointers minimum to track current positions in the circular structure.
