Data Structures

Card Set Information

Data Structures
2014-08-15 19:37:46
array hashtable linkedlist binarysearchtree binarytree heap
Cards to remember basics on data structures.
Show Answers:

  1. What information do you need to know in order for access time of an array to be O(1)?
    Index of element.
  2. Without the index of an element what is the access time the element if we are using an array?
    O(n). Worst case, we must search the whole list for the element.
  3. What is time complexity of deleting elements in an array if we know the index of the element we want to delete?
    • In the worst case we have O(n) as we might have to shift all the elements by one to fill the empty gap in the array.
    • In the average case we still have O(n) as we need to shift n/2 elements.
    • In the best case we have to delete from the end which is O(1).
  4. What data structure would be good for securely handling username and password data?
    A hash table
  5. If we had a list of characters in a file, what kind a data structure could we have to represent the frequency a character shows up in the file?
    We could have a 2d array like so:{ ('a', 3), ('b', 1) ...} Where the first dimension held the characters ascii value and where the second dimension held the characters frequency.ORWe could use a hash table where the character acted as the key to a certain slot and the frequency was the value at that slot.
  6. What is the average case and worst case for accessing elements in a hash table where we only know the keys?
    • Avg case: O(1)
    • Worst case: O(n) if we are not using chaining as we will get collisions.
  7. What are hash tables good for?
    Hash tables are good for doing a quick search on things.For instance if we have an array full of data (say 100 items). If we knew the position that a specific item is stored in an array, then we could quickly access it.For instance, we just happen to know thatthe item we want it is at position 3; I can apply:myitem=myarray[3];With this, we don't have to search through each element in the array, we just access position 3.The question is, how do we know that position 3 stores the data that we are interested in?This is where hashing comes in handy. Given some key, we can apply a hash function to it to find an index or position that we want to access.
  8. Describe the data structure that could hold a heap tree.
    Heaps come as min or max heaps, where parents are either bigger or smaller than the children. We could use an 1d array where for some node i its left child was 2i, and the right child was 2i+1
  9. What is the easiest way to improve search efficiency of data?
    To put it in a data structure that allows more efficient searching.
  10. List known data structures with their access times for elements with respect to searching by value.
    • The below table assumes the data has already
    • been organized into the specified data structure.

    • Data Structure | Searching Efficiency
    • ==============================
    • Hash Table        avg ~ O(1) worst ~ O(n)
    • Binary Trees      worst ~ O(lg n)
    • Array                   worst ~ O(n)
    • Linked List          worst ~ O(n)
  11. Which data structure has a higher look up time: A hash table or a array. Assume both cases when a) we know the index of the array and b) we know the value of the element.
    In both cases a hash table has a higher look up time.
  12. Suppose we wanted to find the first non-repeated character in a given string. We would do this by organizing a data structure and count the frequencies of each character. Then for each char in the string we would see if any had a frequency of 1.

    In terms of memory requirements what is the difference if we use an array VS a hash table?
    An array would need an element for every possible value of a character. This would amount relatively reasonable 128 elements if you process a ASCII strings, but if you have to process strings that could potentially contain any Unicode character, you would need more than 100,000 elements. In contrast a hash table would require storage for only the characters that exist in the string given.

    Arrays are a better choice for long strings and hash tables are better for shorter strings.
  13. Write an efficient function that deletes characters from an ASCII string. Use the prototype

    string removeChars(string str, string remove);

    where any character existing in remove must be deleted from str. For example, given a str of "Battle of the Vowels: Hawaii vs. Grozny" and a remove of "aeiou", the function should transform str to "Bttl f th Vwls: Hw vs. Grzny". Justify any design decisions you make, and discuss the efficiency of your solution.
  14. Write a function that reverses the order of the words in a string. For ex, your function should transform the string "Do or do not, there is no try." to "try. no is there not, do or Do". Assume that all words are space delimited and treat punctuation the same as letters.
  15. Write two conversion routines. The first routine converts a string to a signed integer. You may assume that the string contains only digits and the minus character ('-'), that is a properly formatted integer number is within range of an int type. The second routine converts a signed integer stored as an int back to a string.