DOC PREVIEW
UNI CS 1520 - Lecture Notes

This preview shows page 1 out of 2 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 2 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 2 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

1. Most programming languages have a built-in array data structure to store a collection of same-type items. Arrays are implemented in RAM memory as a contiguous block of memory locations. Consider an array X thatcontains the odd integers:a) Any array element can be accessed randomly by calculating its address.For example, address of X[5] = 4000 + 5 * 4 = 4020. What is the generalformula for calculating the address of the ith element in an array?b) A Python list uses an array of references (pointers) to list items in their implementation of a list. Forexample, a list of strings containing the alphabet: 'a' 'b' 'c' 'z'0 1 2 3(len( )-1)...Since a Python list can contain heterogeneous data, how does storing references in the list aid implementation?2. Arrays in most HLLs are static in size (i.e., cannot grow at run-time), so arrays are constructed to hold the“maximum” number of items. For example, an array with 1,000 slots might only contain 3 items:0 1 2 3 99920 10 30scores:size: 3a) The physical size of the array is the number of slots in the array. What is the physical size of scores?b) The logical size of the array is the number of items actually in the array. What is the logical size of scores?c) The load factor is faction of the array being used. What is the load factor of scores? d) During run-time if an array fills up and we want to add another item, the program can usually: Create a bigger array than the one that filled up Copy all the items from the old array to the bigger array Add the new item Delete the smaller array to free up its memoryWhen creating the bigger array, how much bigger than the old array should it be?e) What is the O( ) of moving to a larger array?Data Structures Lecture 6 Name:_________________________Lecture 6 Page 1addressMemoryX[0]X[1]X[2]X[3]X[4]X[5]X[6] 1 3 5 7 911134000400440084012401640204024...3. The items in a list can be stored in an array (/list) or as dynamically allocated nodes in a linked structure.Abstract list: apples, bananas, bread, cereal, milkarray implementation: applesapplesbananasbananascerealcerealbreadbreadmilkmilk0 1 2 3 45singly-linkedlist implementation:a) Assume a sorted list of “n” items. What are the time complexity for the following operations?Test for equalitySize - number of items in listTraverse the list (“process” each item)Insert new itemDelete item at the ith positionDelete target itemRetrieve item at the ith positionSearch for target itemAverage caseWorst caseAverage caseWorst caseSingly-linked list implementationArray implementationOperation b) Assume an unsorted list of “n” items. What are the time complexity for the following operations?Test for equalitySize - number of items in listTraverse the list (“process” each item)Insert new itemDelete item at the ith positionDelete target itemRetrieve item at the ith positionSearch for target itemAverage caseWorst caseAverage caseWorst caseSingly-linked list implementationArray implementationOperationc) What advantages does an array implementation have over a linked list implementation?d) What advantages does a linked list implementation have over an array implementation?e) How does the space utilization compare between the array and linked list implementations? Data Structures Lecture 6 Name:_________________________Lecture 6 Page


View Full Document

UNI CS 1520 - Lecture Notes

Download Lecture Notes
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Lecture Notes and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Lecture Notes 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?