Untitled Deck Flashcards
What is the time complexity for the queue operations (enqueue and dequeue) for a singly linked list with head and rear pointers?
O(1)
What is the time complexity for inserting and deleting in an ordered singly linked list with a head pointer?
O(n)
In the worst case, what is the time complexity for insert and delete operations in a binary search tree with a root pointer?
O(n)
What is the time complexity for the stack operations (push and pop) using a singly linked list with a head pointer?
O(1)
If a list can be traversed forward and backward, what type of linked list is it?
A doubly linked list
What is the complexity to delete a node from the end of a linked list?
O(n)
How many pointers must be modified to delete a node from the end of a circular linked list?
1 pointer
How many pointers must be modified to delete a node from the middle of a doubly linked list?
2 pointers
How many pointers must be modified to delete a node from the beginning of a singly linked list?
1 pointer
When does stack underflow occur?
When the stack is empty
In the context of function calls, when does a function become tail recursive?
Whenever there is a pending operation to be performed
Which data structure is used to convert an infix expression into a postfix expression?
A stack
Which data structure is appropriate for processing batch computer programs submitted to the computer centre?
A priority queue
What is the typical time requirement for enqueue and dequeue operations in a linked queue?
O(1)
In an input-restricted deque, where can insertions and deletions take place?
Insertions can be done only at one end, while deletions can be done from both ends
If operating system interrupts need to be handled in the order of arrival, which queue is appropriate?
A FIFO (First-In-First-Out) queue
When is a binary tree T considered an extended binary tree?
When each node in T has either no children or exactly two children
What do we call nodes at the same level that share the same parent?
Siblings
What is the maximum number of nodes at the kth level of a binary tree?
2^k
Which traversal algorithm is used to extract prefix notation from an expression tree?
Pre-order traversal
What is another name for a two-way threaded binary tree?
A fully threaded binary tree
In a threaded binary tree, if the thread appears in the right field, what does it point to?
The in-order successor of the node
In splay trees, which operations perform rotation?
The zig and zag operations
When does the zig operation occur in a splay tree?
It happens when the parent of the node (P) is the root of the splay tree
What does int **e; declare?
A variable e that holds the address of an integer pointer variable of three stars
How many bytes are typical for memory addresses?
4 bytes or 8 bytes
Which base is often used to print memory addresses?
Base 16 (hexadecimal)
With 4 bits, which range of positive integers can be represented?
0 to 15
How can a number in base b be represented in digit form?
As b₃ b₂ b₁ b₀
What is the result of the bitwise operation 0101 | 1010?
1111
