How much time will it take to sort the array

Assignment Help Data Structure & Algorithms
Reference no: EM131032724

1. In general which of the following algorithms requires the most extra memory when running?

a) Insertion sort

b) Merge sort

c) Quick sort

d) Shell sort

e) All wold use the same amount of extra memory.

2. Which of the following algorithms runs in 0(AP) average time?

a. insertion sort

b) merge sort

c) quick sort

d) heap sort

e) none of the above

3. Which of the following algorithms runs in 0(N log N) average time but quadratic worst-case time?

a) insertion sort

b) merge sort

c) heap sort

d) Shell sort

e) quick sort

4. The -median-of-three" partitioning strategy is often used in a QuickSort implementation because:

a) The Quicksort always needs three pivot values

b) It helps prevent "degenerate input" sequences from degrading the algorithm's performance. C) The array is usually of an unknown length

d) It prevents empty arrays from crashing the system

e) The median value will never have to be swapped to a new location.

5. Which algorithm provides the best "real-world" performance on data that is already sorted or "mostly" sorted

a) InsertionSort

b) MergeSort

c) HeapSort

d) ShellSort

e) QuickSort

6. Which algorithm provides the most consistent performance when sorting data. (The actual number of operations is the most independent of the input order of the data.)

a) InsertionSort

b) HeapSort

C) QuickSort

d) None are affected significantly by the original ordering.

e) All can vary greatly, depending on order of the supplied data.

7. If an arbitrary item is added to the end of an already sorted list, how much time will it take to sort the array again using insertion sort?

a) o( 1 )

b) 0( log N )

c) 0( N )

d) O (N log N )

e) 0( N2 )

8. Which of the following is true about the height of a node?

a) The height of a node is always one less than the height of its parent

b) The height of an empty tree is 1

C) The height of a leaf is always 0

d) The maxim height of a tree can be larger than its maximum depth

e) all of the above are false

9. Insertions and lookups on a Hash-map may operate in 0(1) time whereas Search Tree's require 0(log n) time. BRIEFLY explain: How/why Hash-maps may operate in a lower computation complexity than Tress and why Trees might still be preferable over Hash-maps in many cases.

10. List the following algorithms in order from Slowest to Fastest (in terms of their general "real world" AND theoretical average performance) and provide the key reason why each successive algorithm is faster than its predecessor; no more than 5 or so words! If there is a "tie", indicate such briefly mention why.

QuickSort, BubbleSort, MergeSort, HeapSort, SelectionSort, ShellShort, InsertionSort, CountingSort.

11. The first stage of a Heap-Sort is to represent an input sequence as a "Binary Heap", Given a list (4, 3, 1, 2, 9, .6,. 7, 8, 5)

a) Show the "Binary MAX Heap" Representation (assuming the items are added to the heap in the order given) as both a tree and as a new array.

"Heap" Array:

9

8

7

6

5

4

3

2

1

 

b) Show the Heap after the removal of the largest element (eg. the first item positioning of the "Heap Sort".)

"Heap" Array:

9

8

7

6

5

4

3

2

1

 

12. The two nodes marked *'s in the tree below have a height difference greater than one (two, to be precise). Does the tree have the structural properties of a valid AVL tree? Why or why not?

536_Tree Graph.png

The next four questions relate to the tree below:

1215_Tree Graph1.png

1. Which of the following traversals yields ABCDE?

a) inorder

b) level (bredth) order

C) postorder

d) preorder

e) two of the above

2. Which of the following is an inorder traversal of the tree?

a) ABCDE

b) ABDCE

c) BDECA

d) EDCBA

e) none of the above

13. Using the following tree:

449_Tree Graph2.png

a) Show a post-order traversal (the nodes as they are displayed) of the above tree

b) Show a pre-order traversal (the nodes as they are displayed) of the above tree

C) Show an in-order traversal (the nodes as they are displayed) of the above tree

14. Show the resulting .AVL Tree after the insertion of the following elements - in order - into a new AVL tree: 30, 20, 10, 5, 6, 15, 2

15. Assuming a Quick Sort, where a first element of any "sub array" is always the pivot show the resulting array after the first "pivot value" has been swapped into it's correct location (ie, after the first partitioning of the array into the first two "sub arrays"):

[4, 1, 7, 8, 6, 9, 3, 5, 0]

16. Assuming an radix sort is used to sort the elements below. Show each of the resulting "intermediate" arrays as the array is placed into sorted order.

[123, 122, 222, 111, 132, 133]

17. Assume characters have the following values: a=1, b=2, c=3, d=4, e=5 and a string hashing function that simply adds the character values and mods with 5: (0k Chark)mod 5

For example "abae" = (1+2+1+5)965 => 4

Show the addition of the following strings to a "Closed" Hash table (in order):

"abc" , "bbb" , "cb", "ee", "abcde"

0

 

1

 

2

abc

3

cb

4

bbb

5

ee

6

abcde

18. Show the addition of the following strings to an "Open" Hash table (in order): "abc", "bbb", "cb" , "ee", "abcde"

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Reference no: EM131032724

Questions Cloud

Impact of credit crises on us financial market liquidity : BUS422 - Spring2015 - Impact of Lehman Brother's bankruptcy on Individual wealth and impact of credit crises on US Financial market liquidity.
Determine the power input to the ice machine : Water enters the ice machine at 55°F and leaves as ice at 25°F. For an ice production rate of 15 lbm/h, determine the power input to the ice machine (169 Btu of heat needs to be removed from each lbm of water at 55°F to turn it into ice at 25°F).
Describe data collection and analysis methods : The initial research proposal will consist of the following SIX (6) items: Identify a business research topic and Define the research questions for the identified problem or opportunity
Discuss how you will eliminate bias from your observation : Discuss whether you will be using this tool to observe social/emotional development, physical development, cognitive development, or language development. Explain the purpose for using this tool to assess your chosen domain.
How much time will it take to sort the array : If an arbitrary item is added to the end of an already sorted list, how much time will it take to sort the array again using insertion sort?
Impact of social media on contemporary businesscommunication : You are required to write an essay on "The impact of social media on contemporary business communication." How have these changes impacted the way modern business operates today
Discuss the importance of senior management : Discuss the importance of senior management in setting the tone at the top for honesty and integrity within a company. Identify at least two consequences of management not establishing a code of ethics.
Evaluate the performance of capital projects : Determine the rate of return you could expect from your investment and the method you would use to evaluate the investment decision.
What is the purpose of a swot and pest analysis : What relevant legislation does your organisation adhere to that could affect strategic planning? What is the purpose of a SWOT and PEST analysis? Why is it important to have knowledge of the competitors

Reviews

Write a Review

 

Data Structure & Algorithms Questions & Answers

  Write a program that creates an array of structures

Write a program that creates an array of structures of type Student. The structures must include the following data members.

  Write a xml schema for the validation of the document notes.

write a XML schema for the validation of the document notes.xml. Write the schema according to the following three approaches;1.- Based on the document structure2.- Structured (bottom-up design)3.- Type-based (top-down design)

  Give time algorithm that outputs satisfying assignment

Find out  whether there is an assignment of true/false values to the literals such that at least a*m clauses will be true. Note that 3-SAT(1) is exactly the 3-SAT problem. Give an O(m*n)-time algorithm that outputs a satisfying assignment for 3-S..

  What is the logarithm base-2 of zero? of one

What is the logarithm base-2 of zero? of one?

  Question about hardware requirements

When you purchase a new software package, why does it state minimum RAM and hard drive space your computer must have for you to run this program?

  1 describe the jsp life cycledraw a diagram of the various

1. describe the jsp life cycle.draw a diagram of the various events and transformations.for each part of the cycle

  Find combination of projection and inverse projection map

Find the combination of projection and inverse projection maps which finds all authors by whom I have horror books

  What is meant by multiple indexing

What is meant by multiple indexing? How do insertion and deletion operations for a sorted data file differ from those for an unsorted data file that has a sorted index? What are the external table operations for which the hashing of an index file i..

  Analyze algorithm to determine length of longest substring

Explain and analyze the algorithm to determine the length of longest substring that appears both forward and backward in an input string T[1 . n].

  Consider the character frequencies in the huffman tree

The total length of the encoding with the above frequencies and the derived Huffman tree is:

  Work out the matching determined by the coda

There are six students, A, B, C, D, E, and F, and three colleges, X, Y, and Z, each with room for two students. The student preferences are given in Table 1 and the college preferences are given in Table 2. Work out the matching generated by SODA. ..

  Advanced systems analysis and design

Produce a system specification indicating functional and non-functional requirements - Generate suitable prioritised Use Cases for the system.

Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd