Data Structures SEBI
Studied by 0 people
Call with Kai
Learn
Practice Test
Spaced Repetition
Match
Flashcards
Knowt Play1/487
There's no tags or description
Looks like no tags are added yet.
Name | Mastery | Learn | Test | Matching | Spaced | Call with Kai |
|---|
No study sessions yet.
488 Terms
What is an array
A collection of homogeneous elements stored in contiguous memory locations
What type of memory storage does an array use
Contiguous memory
Is array indexing zero based
Yes indexing usually starts from zero
What is the base address in arrays
Address of the first element of the array
How is address of arr i calculated
Base address plus i multiplied by size of element
What is a static array
Array whose size is fixed at compile time
Give example of static array in C
int arr[10]
What is a dynamic array
Array whose size is allocated at runtime
Name one dynamic array implementation in Java
ArrayList
Name one dynamic array implementation in C plus plus
Vector
What is time complexity of accessing an array element
O one
Why is array access O one
Direct access using index
What is time complexity of linear search in array
O n
When is linear search used
When array is unsorted
What is time complexity of binary search
O log n
What is prerequisite for binary search
Array must be sorted
What is worst case time complexity of insertion in array
O n
Why insertion worst case is O n
Elements need shifting
What is worst case time complexity of deletion in array
O n
When does deletion take O n time
Deleting from beginning of array
What is a two dimensional array
Array with rows and columns
How is 2D array stored in memory
Flattened into one dimensional memory
What is row major order
Elements stored row by row
Which language uses row major order by default
C language
What is column major order
Elements stored column by column
Which language uses column major order
Fortran
What is two pointer technique
Uses two indices moving towards each other
Give one use of two pointer technique
Reversing an array
What is sliding window technique
Maintains a window of elements for subarray problems
Give one use of sliding window
Finding subarray with given sum
What is Kadane algorithm used for
Finding maximum sum contiguous subarray
What is time complexity of Kadane algorithm
O n
What is Dutch National Flag algorithm used for
Sorting array of zeros ones and twos
What is time complexity of Dutch National Flag algorithm
O n
What is a sparse matrix
Matrix with most elements as zero
Why sparse matrix representation is used
To save memory space
What is triplet representation
Stores row column and value
What is array overflow
Insertion into a full static array
What is array underflow
Deletion from an empty array
What does arr represent in C
Constant pointer to first element
What is arr equivalent to
&arr[0]
What is equivalent of arr[i] in pointer arithmetic
*(arr plus i)
What is a linked list
Collection of nodes stored in non contiguous memory
How is linked list memory allocated
Dynamically at runtime
How does array memory differ from linked list
Array uses contiguous memory
What type of access does array support
Random access
What type of access does linked list support
Sequential access
What is access time of linked list
O n
Why linked list access is O n
Traversal required from head
What is insertion time in linked list if pointer is known
O one
Why insertion in array is O n
Shifting of elements required
What extra memory does linked list use
Extra space for pointer
What is a singly linked list
Each node has data and next pointer
What is a doubly linked list
Each node has data next and prev pointers
What advantage does doubly linked list have
Bidirectional traversal
What is a circular linked list
Last node points to head
What is application of circular linked list
Round robin CPU scheduling
What is a doubly circular linked list
No null pointers in list
What is worst case search time in singly linked list
O n
What is worst case search time in doubly linked list
O n
What is time to insert at beginning in singly linked list
O one
What is time to insert at beginning in doubly linked list
O one
What is time to insert at end without tail pointer
O n
What is time to insert at end with tail pointer
O one
What is delete at end time in singly linked list
O n
Why delete at end is O n in singly linked list
Must find previous node
What is delete at end time in doubly linked list if tail known
O one
What is time complexity of reversing singly linked list
O n
How many pointers needed to reverse singly linked list
Three pointers
Name the three pointers used in reversal
Prev curr and next
What is head insertion pointer logic
newNode next points to head
After insertion how is head updated
Head points to new node
What is trick to delete a node given pointer p
Copy next node data and bypass it
Which node cannot be deleted using trick
Last node
What is Floyd cycle detection algorithm
Detects loop in linked list
What are pointers used in Floyd algorithm
Slow and fast pointers
How many steps slow pointer moves
One step
How many steps fast pointer moves
Two steps
What indicates presence of cycle
Slow and fast pointers meet
What is a self referential structure
Structure containing pointer to same type
Why linked list node is self referential
Next points to same structure type
What does struct Node next represent
Address of next node
What is size of node on 32 bit system
Data plus pointer size
Why linked lists are good for sparse matrices
Saves space by storing non zero elements
Why linked lists suit polynomial representation
Efficient for many zero coefficients
What is a stack
Linear data structure following LIFO principle
What does LIFO stand for
Last in first out
Which element can be accessed in stack
Only the top element
What is push operation
Insertion of element at top of stack
What is pop operation
Removal of top element from stack
What is peek operation
Returns top element without removing it
What does isEmpty check
Whether stack is empty
What does isFull check
Whether stack is full
What is time complexity of push
O one
What is time complexity of pop
O one
What is time complexity of peek
O one
What is stack overflow
Push operation on full stack
In which implementation overflow occurs
Array based stack
What is stack underflow
Pop operation on empty stack
Which stack implementation avoids overflow
Linked list based stack
Note 
Flashcards (89)