What is an elementary data type?
The basic types of data that serve as the building blocks for data manipulation.
What is a composite data type?
Data types which are collections of elementary data types.
What is an abstract data type?
An abstract data type (ADT) is a logical description of how we view the data and possible operations. We are concerned only with what the data is representing and not how it is constructed.
What is a queue?
A queue is a abstract data structure which operates on a first-in, first-out principle, meaning the element that has been in the queue the longest is the next to be removed.
- Some queues use pointers to store where in the data the queue begins and ends,
- Some queues are circular and can reuse spaces dequeued from the front,
- Some queue have a priority system and items with a higher priority will be placed before those with lower ones.
What are the 4 distinct operations of a queue?
- enQueue(item): add an item to the rear,
- deQueue(): remove and return an item from the front,
- isEmpty(): indicates if the queue is empty,
- isFull(): indicates if the queue is full.
What is the difference between static and dynamic data structures?
Static data structures are fixed in size, they cannot grow, shrink, or be freed during execution.
Dynamic data structures can grow and shrink. They allocate and deallocate memory from the heap (an area of memory especially used for this purpose), excessive allocation of memory, without deallocation, may cause overflow.
What is a list?
A list is a collection of items that are finite in number and in a particular order.
- A dynamic data structure such as list is useful for implementing other ADTs such as queues, stacks and trees.
What are the distinct operations of a list?
- isEmpty(): Test for empty list,
- append(item): Add a new item to the end of a list,
- remove(item): Remove first occurrence of an item from list,
- count(item): Return the number of occurrences of item in list,
- len(item): Return the number of items in the list,
- index(item): Return the position of item,
- insert(pos,item): Add a new item at position pos,
- pop(): Remove and return the last item in the list,
- pop(pos): Remove and return the item at position pos.
What is a stack?
A stack is a abstract data structure which operates on a last-in, first-out principle, meaning the element that has been in the queue the shortest is the next to be removed.
What are the 4 distinct operations of a stack?
- push(item) – adds item to the top of the stack,
- pop() – removes and returns the item on the top of the stack,
- isEmpty(): indicates if the queue is empty,
- isFull(): indicates if the queue is full.
What is the call stack?
The call stack is a system level data structure which provides the mechanism for passing parameters and return addresses to subroutines.
How are calls to subroutines executed?
- The parameters are saved onto the stack,
- Local variables are saved onto the stack,
- The address to which execution returns after the end of the subroutine is reached is saved onto the stack,
- Execution is transferred to the subroutine code.
How are subroutines executed?
- Stack space is allocated for local variables,
- The subroutine code executes,
- The return address is retrieved,
- The parameters are popped,
- Execution is transferred back to the return address.
What is a stack frame?
A stack frame contains all the parameters, the return address and the local variables for a single call to a subroutine which has not yet completed.
What is a hash table?
A hash table is an abstract data type used to store the unique addresses (calculated from the data itself through a specific algorithm) of data items rom a large data set in order to give us the ability to find any record very quickly.
What is a collision in the context of hashing?
A collision happens when an algorithm generates the same address for different primary keys.
How do hash tables deal with collisons?
One method is to put the item in the next free slot in the table. Another is to skip to a slot which is a specific amount (the skip factor) of slots away and attempting to store it there, repeating this if it can’t.
What is the load factor of a hash table?
The load factor is the ratio of the number of stored elements (n) to the number of available buckets (b). It is calculated as:
load_factor = n / b
What is the ideal hash table size?
The table size needs to be large enough so that the load factor is not more than about 50%-70% of table size.
Additionally, it is beneficial if the table is a prime number so that all slots can be filled no matter the skip factor.
How does the mid-square hashing algorithm work?
- First square the item (assume it is numeric),
- Extract some portion of the resulting digits,
- Perform the mod (remainder) step to get an address,
- Example: Assume a table size of 11, and a number 56 to be stored:
562 = 3136
Middle 2 digits = 13
Address = 13 mod 11 = 2
How does the folding hashing algorithm work?
- Divide the item into equal-size pieces (the last piece may not be of equal size)
Add the pieces together
Perform the mod (remainder) step to get an address
Example: Assume a table size of 11, and a number 34721062 to be stored
34 + 72 + 10 + 62 = 178
Address = 178 mod 11 = 2
How can you hash alphanumeric data?
Alphanumeric data may be converted to numeric data by using the ASCII code for each character, then applying a hashing algorithm to the resulting series of digits.
How do hash tables deal with deletions?
Items to be deleted must be replaced with a dummy item or marker, for example the word “Deleted”. When searching for an item which hashes to that spot, if it is not found, the search will continue until it is found or a free space located.If a new item is to be added, it will replace the deleted item.
What is a dictionary?
- A dictionary is an abstract data type made up of associated pairs,
- Each pair has a key and a value,
- The value is accessed via the key.
- Multiple items with the same key are not allowed, but the value associated with a key could be a list, dictionary or other data structure which can store multiple values
-
Unit 1 - Fundamentals of Programming32
-
Unit 2 - Problem Solving34
-
Unit 3 - Data Representation82
-
Unit 4 - Hardware and Software51
-
Unit 5 - Computer Organisation and Architecture74
-
Unit 6 - Communication Technology and Consequences55
-
Unit 7 - Data Structures51
-
Unit 8 - Algorithms19
-
Unit 9 - Regular Languages48
-
Unit 10 - The Internet88
-
Unit 11 - Fundamentals of Databases40
-
Unit 12 - OOP and Functional Programming44
-
Unit 13 - Appendices25
