You have 10,000 students, each with a unique ID from 0 to 9,999. Your most common task is to instantly retrieve a student's record using their ID as the index e.g., get_student_data(501). Which data structure is the only one that can guarantee O(1) time for this specific task?, Array, Linked List, Stack, Queue, You're building an image filter. An image is a 10,000 x 10,000 grid of pixels. You need to perform an operation on every pixel, and you need to be able to instantly access any pixel's neighbors e.g., pixel[x][y+1]. What is the primary reason an Array (or 2D Array) is the ideal choice?, Because inserting new pixels is fast., Because you need to process pixels in a LIFO order., Because it provides O(1) random access based on coordinates (indexes)., Because it uses non-contiguous memory, which is more flexible., You must implement a Queue, but you are only allowed to use one Stack and the system's recursive Call Stack. How can you enqueue an item?, It is impossible., push the item onto the Stack., Create a recursive function. In the function, pop an item, call the function again, and then push the item back., pop all items, push the new item, then push all the old items back., You are using a Singly Linked List. You are given a pointer to a node N in the middle of the list. Your task is to delete(N). What is the problem?, You can't do it. To delete N, you need a pointer to the node before it (prev). You must traverse from the head to find prev., There is no problem, you just set N = None., You can't do it because you don't have a tail pointer., You must use a "fast" and "slow" pointer., You are asked to implement a Queue, but the only data structure you are allowed to use is two Stacks (stack_in and stack_out). How do you dequeue an item?, pop from stack_in., If stack_out is empty, pop every item from stack_in and push them to stack_out. Then pop from stack_out, push to stack_in, then pop from stack_out., It is impossible to make a FIFO (Queue) structure from two LIFO (Stack) structures., You have an Array-based list of 1000 items. Which operation would be the slowest and cause the most performance impact?, my_list.append(newItem) (Adding to the end), my_list.pop() (Removing from the end), item = my_list[500] (Reading from the middle), my_list.insert(0, newItem) (Adding to the beginning), You are given a string "HELLO" and you need to reverse it to "OLLEH". You can only use a Stack. What is the correct algorithm?, push 'H', push 'E', push 'L', push 'L', push 'O'. Then pop five times into a new string., push 'O', push 'L', push 'L', push 'E', push 'H'. Then pop five times into a new string., push all letters. Then peek five times into a new string., enqueue all letters. Then dequeue five times., You have a Singly Linked List with 1,000,000 nodes, but you do not know the size. How can you find the middle node in only one pass (one traversal)?, It's impossible. You must traverse once to get the size (n=1,000,000), then traverse a second time to n/2., Use a "fast" pointer and a "slow" pointer. Move fast 2 steps at a time and slow 1 step at a time. When fast reaches the end, slow will be at the middle., Use a Doubly Linked List, which has a prev pointer., Load the entire list into an Array, then find the middle element at arr[n/2]., You are implementing a Circular Queue with a fixed-size Array of capacity = 5. front is at index 2. rear is at index 4. The queue is [ , , 30, 40, 50 ]. You then enqueue(60). Where do front and rear point now?, front=2, rear=0., front=3, rear=0., front=2, rear=5. (Crash), front=0, rear=0., You need to store 50 million floating-point numbers. You have two choices: an Array or a Linked List. From a memory-usage perspective, why is the Array the superior choice?, Because the Array can grow dynamically., Because the Array stores data in non-contiguous memory., Because the Array only stores the data, while the Linked List must store the data plus a "next" pointer for every single number., Because delete_from_beginning is O(1) in an array., You write a recursive function that forgets to include a "base case" (a condition to stop). The function just calls itself forever. What will be the specific error that crashes your program?, "Queue Overflow", "Index Out of Bounds", "Stack Overflow", "No Error, it will just be slow", You need to reverse a Singly Linked List "in-place" (without creating a new list). You use three pointers: prev, current, and next_node. What is the correct "reversal" step inside the loop?, prev.next = current, current.next = next_node, current.next = prev, next_node.next = current, You are implementing a Circular Queue and only using front and rear pointers (no size variable). front=2 and rear=2. What is the state of the queue?, It is full., It is empty., It has exactly one item., It is impossible to tell., You have a Linked List containing 100 items. What is the time complexity to find and retrieve the 50th item in the list?, O(1), O(n), O(log n), O(n2), A CPU cache (like L1) is extremely fast. It works by pulling data from main memory. For it to be fast, the data it pulls must be located next to each other in memory. Which data structure "respects" this principle of locality of reference?, An Array, because its elements are in contiguous memory., A Linked List, because its nodes can be anywhere (non-contiguous)., A Hash Table., A Stack, because it is LIFO., You are implementing a Stack using a Linked List. For O(1) push and pop, where should your operations occur?, push at the tail and pop from the head., push at the head and pop from the head, push at the tail and pop from the tail., It's impossible to get O(1) for both., You are parsing the mathematical expression "5 3 + 8 *". This is "Reverse Polish Notation." The algorithm is: read an item. If it's a number, push it. If it's an operator, pop two numbers, do the math, and push the result. What is the final result on the stack?, push 5, push 3. pop 3, pop 5. Push (5+3)=8. push 8. pop 8, pop 8. Push (8*8)=64. Result: 64., push 5, push 3. pop 3, pop 5. Push (5+3)=8. pop 8. push 8. Error., push 5, push 3. push '+'. push 8. push '*'. Error., It's impossible to calculate this with a Stack., A student implements a Queue using a standard Python list. They use my_list.append(item) for enqueue and my_list.pop(0) for dequeue. Why is this a bad implementation?, append() is an O(n) operation., pop(0) is an O(n) operation, Both operations are O(n)., This implementation will cause a "Stack Overflow.", You are trying to implement delete_by_value() in a singly Linked List. Your code finds the node to delete. What else do you need to perform the deletion?, You must also have a pointer to the tail node., You must also have a pointer to the previous node., You must also have the size of the list., You only need the current node., You need to implement a Stack in Python. You want push and pop to both be O(1). What is the simplest way to achieve this using a built-in data structure?, Use a list, with push as my_list.append(item) and pop as my_list.pop()., Use a list, with push as my_list.insert(0, item) and pop as my_list.pop(0)., Use a Linked List with only a head pointer., Use a Circular Queue..

Linear Data Structures

autors:
Drukāt
Iegult

Līderu saraksts

Vizuālais stils

Iespējas

Pārslēgt veidni

)
Atjaunot automātiski saglabāto: ?