In this chapter, we saw that duplicate elimination is straightfor- ward when creating a binary search tree. Describe how you’d perform duplicate elimination when using only a one-dimensional array. Compare the performance of array-based duplicate elimination with the performance of binary-search-tree-based duplicate elimination.

What will be an ideal response?


First, sort the array—this makes all the duplicates be adjacent. Then, walk through the array with a source and destination index, copying only the first of a sequence of duplicates from the source to the destination. Once the source index reaches the end of the array, remove the elements after the destination index from the array. This yields the same efficiency as inserting them into a balanced binary search tree.

Computer Science & Information Technology

You might also like to view...

Word provides default tab stops at 0.5" intervals.

Answer the following statement true (T) or false (F)

Computer Science & Information Technology

Jim wants to change the size of one of the icons in his document. He knows that once he sees the squares at each corner of the selection, he can make that change. What do you tell him is the name of those squares so that he can look for the appropriate command on the options bar?

a. transform controls b. shape and size tools c. resize options d. layer options

Computer Science & Information Technology

?_____ is the process of drawing a series of increasingly detailed data flow diagrams (DFDs), until all functional primitives are identified.

A. ?Leveling B. ?Balancing C. ?Indexing D. ?Looping

Computer Science & Information Technology

Chrome, Opera and Safari are examples of what type of program or app?

A. browser B. hotspot C. LMS D. file sharing

Computer Science & Information Technology