GoConqr hat ein neues Design! Sag uns, wie es dir gefällt.

Kostenlos registrieren

Karteikarten

Data Structures Final

Mia Neri Data Structures Computer Science Englisch 72 Karten

Karten in diesem Stapel (72)

  1. 1Which data structure requires more than constant average time for insertions.Search Tree
  2. 2How are elements deleted in linear probing.They are marked delete
  3. 3Which are equal in a probing hash table?Insertion and unsuccessful search
  4. 4What kind of list do linear probing, quadratic probing, and separate chaining use:Linked Lists
  5. 5What does primary clustering occur in?Linear Probing
  6. 6Can rehashing be used in linear probing, quadratic probing, and separate chaining?Yes
  7. 7Every node in a min binary heap hasThe node is no larger than its children
  8. 8The running time of Build Heap isO(n) worst case and average case
  9. 9N elements are inserted one by one into an initially empty binary heap. The total running time isO(n log n) worst case and O(n) average case
  10. 10Which operation is not supported in constant time by a double ended queueInsert
  11. 11Is Find efficiently supported by a priority queue?No
  12. 12Which data structure is used to check for balanced parenthesis?Queue
  13. 13Which data structure maintains the event set in an event driven simulation?Priority Queue
  14. 14Which data structure is generally used to implement a symbol table?Hash Table
  15. 15What can be used as an efficient priority queue?Binary Search Tree
  16. 16Does the binary heap implement a priority queue?Yes
  17. 17Which data structure is used by the compiler to implement recursionStack
  18. 18A sentinel is used by which data structureBinary Heap
  19. 19Percolate Up and Down are used for BinaryBinary Heaps
  20. 20Which operation can be used to implement the other three for the skew heapMerge
  21. 21Is a binomial queue a binary treeNo
  22. 22Which of operation is not efficiently supported by a singly linked listInsertion before the current position
  23. 23What does the header node of a linked list doSimplifies deletion, simplifies insertion, uses only constant extra space
  24. 24Insertion of a node into a doubly linked list requires how many changes to various next and previous pointersIt requires 2 next and two previous pointers
  25. 25Is the backup operation supported in constant time by the doubly linked list, but not the singly linked listYes
  26. 26For the linked list implementation of the stack, where are the pushes and pops performedPush in front of the first element, pop the first element
  27. 27With the linked list implementation of the queue, where are the enqueue and dequeues performedEnqueue after the last element, Dequeue the first element new line new line
  28. 28What is the worst case complexity of inorder tree traversalO(n)
  29. 29What is the worst case complexity of level order tree traversalO(n)
  30. 30What is the worst case complexity of preorder tree traversalO(n)
  31. 31What is the worst case complexity of postorder tree traversalO(n)
  32. 32What is the maximum number of nodes in a binary tree with L leavesNo maximum
  33. 33Is it true that the height of a leaf is always zeroYes
  34. 34Does level order tree traversal use a stackNo
  35. 35Is it true that deleting a rule entails the root pointer changing if it does not have two children yes what is the maximum amount of rotations in an N item AVL tree1
  36. 36What data structure has the strongest height guarantee B-tree of Order5
  37. 37In addition to the data and left and right pointers for any implementation, what must be stored in each node of a splay tree?Needs nothing else
  38. 38What is the amortized cost of an operation using rotate to rootO(n)
  39. 39What is the worst case height of a splay tree(N - 1)
  40. 40What splay tree rotation in effect distinguishes it from rotate to rootZig-zag only
  41. 41How is the deletion performed in a splay treeA single splay is performed which places the deleted node at the root; It is deleted and the two subtrees are reattached by using a second splay
  42. 42Is the rank in a splay tree stored at allNo
  43. 43What can be done as an alternative to preserve the logarithmic amortized time bound for the splay tree?Do not splay if an access path has fewer than log N nodes
  44. 44What is the basic algorithm used for external sortingMerging
  45. 45What data structure does not yield an efficient comparison based sortHash Tables
  46. 46What algorithm requires the most extra space, on average, when implemented as in the text?Mergesort
  47. 47What algorithm runs in quadratic average timeInsertion sort
  48. 48Which of the following algorithms runs in O(n log n) average time but quadratic worst-case timeQuicksort
  49. 49Which of the following algorithms, implemented as in the text, runs in O(n) time when presented with an array of n identical elements?Quicksort
  50. 50Which of the following algorithms has the largest Big-Oh differential between average case and worst case performanceQuickselect
  51. 51How much extra space is used by heapsortO(1)
  52. 52Which sorting algorithm has the same average and worst case time bounds as heapsort?Mergesort
  53. 53For quicksort, what do i and j do when they see keys equal to the pivot?i stops and j stops
  54. 54What is replacement selectionConstructing the runs so they have expected length of 2M
  55. 55Does an AVL tree have a height that is logarithmic?Yes
  56. 56Do binary heaps have a height that is logarithmic?Yes
  57. 57Does a B-tree of order four not have a logarithmic height?No
  58. 58Are reflexive, symmetric, and transitive properties required for an equivalence relation?They are all required
  59. 59What is sufficient to ensure a bound of O(M log n ) for M operations?A path compression, union by height, and union by size are all required.
  60. 60What is path compression?A path compression is performed during fines to make fines faster
  61. 61Are arcs and edges the same thing?Yes
  62. 62Is a weighted shortest path in a cyclic graph not known to be solvable in linear time?Yes
  63. 63What type of weighted path does not use a queue?A positive weighted shortest path algorithm
  64. 64What algorithm solves the unweighted single source shortest path problem?Breadth first search
  65. 65What algorithm solves the positive weighted single source shortest path problem?Dijkstra’s Algorithm
  66. 66If the shortest path algorithm is run and a vertex is not reachable from the starting point, what happens?A distance of infinity is reported
  67. 67Is it true that every acyclic of the graph has at least one topological ordering?Yes
  68. 68Is it true that every acyclic graph has at most one topological ordering?No
  69. 69What algorithm is used to compute minimum space trees?Kruskals
  70. 70What strategy does not directly invoke recursion?Dynamic Programming
  71. 71The seed of a linear congruential generator is?The initial value
  72. 72Which is a bad case for randomized quick select?There are no bad inputs

Informationen

Beschreibung
Computer Science Data Structures Karteikarten am Data Structures Final, erstellt von Mia Neri am 30/11/2022.
Erstellt von
Mia Neri
Aufrufe
1
Bewertung

Feedback

Worum geht es?

Wie gefällt dir das neue Design?

Dein Eindruck