2 2 votes Which of the following data structures would programmer be least likely to use to implement an abstract data type that must include an efficient implementation of the operation " find the maximum"? Ordered array. Binary search. Heap. Ordered linked list. Programming in C + – richa116 2.3k views answer comment Share Follow Print See all 3 Comments 3 3 Comments reply monanshi commented Dec 23, 2015 reply Follow flag Is binary search a DS? 4 4 replyShare srestha commented Dec 23, 2015 reply Follow flag why not? 0 0 replyShare Shashank Kumar commented Jan 4, 2016 reply Follow flag Here Binary Search => Binary Search Tree which is obviously a data structure. 0 0 replyShare Please log in or register to add a comment.
5 5 votes the answer should be d. ordered linked list.(if ordering is done in ascending order then it will take O(n) time to retrieve max value as it need to traverse the link list) the question is asking least likely to be used not most likely. Abhishekcs10 answered Dec 22, 2015 Abhishekcs10 comment Share Follow See all 8 Comments 8 8 Comments reply Show 5 previous comments Abhishekcs10 commented Dec 24, 2015 i edited by Abhishekcs10 Dec 24, 2015 reply Follow flag there is no need to search since the array is sorted(ordered). Just access the last element of array and that is the maximum. and if u mean any k-th smallest element then also O(1)...:p 0 0 replyShare srestha commented Dec 24, 2015 reply Follow flag ok, min and max will take O(1) and middle element searched in O(n). 0 0 replyShare Pranay Datta 1 commented Dec 25, 2015 reply Follow flag if linked list ascending then O(n) but if descending then O(1) , the question does not say anything about it . and about binary search they does not tell that we are applying it on a order list or a unordered list if ordered list then O(logn) if not then it may or may not able to find the max value , then binary search will be the least likely to use . 0 0 replyShare Please log in or register to add a comment.
–2 –2 votes I think it will be array (A) Array could take O(n) time (B) Binary search takes O(log n) times (C) Heap takes O(n log n) times (D) ordered linked list maximum could take O(n) times srestha answered Dec 22, 2015 • edited Dec 23, 2015 by srestha srestha comment Share Follow See all 2 Comments 2 2 Comments reply Anurag_s commented Dec 23, 2015 reply Follow flag Heap For max O(1),for building O(n), balancing logn 0 0 replyShare srestha commented Dec 23, 2015 reply Follow flag yes , but it may not be max heap, it may be min heap. then u have to come leaf node in (log n) times. and then search among leaves in O(n) times, as in heap any one element among leaves could be large. So, it takes O(n log n) times to find maximum in min heap. But in binary search we perform only performed when list is sorted. So, only for finding the element it will take O(log n) times right? 0 0 replyShare Please log in or register to add a comment.
