Chapter 3 Data Structures

Question 1

What is a data structure?

Answer 1

A way of bundling data so it has well-defined rules for access, change, and scope.

Question 2

What is an elementary data type?

Answer 2

A simple data value like integers, reals, characters, or booleans.

Question 3

Difference between arrays and lists?

Answer 3

Arrays are fixed-type, fixed-size; lists can be variable-type and dynamic.

Question 4

What is a record?

Answer 4

A fixed collection of variables (attributes) under a common name.(not allowed to gain or lose entries after being created)

Question 5

Why arrays are O(1) access?

Answer 5

Because element positions can be computed directly using memory offset.

Question 6

What is a pointer?

Answer 6

A variable that stores the memory address of another variable. Pointer can have the value of NIL (pointer to ‘nowhere”

Question 7

Why arrays can’t store different types?

Answer 7

Because they use fixed-size memory blocks for each entry.

Question 8

What is a linked list?

Answer 8

A data structure of nodes (triplets: previous, key, next) linked together.

Question 9

What is the head of a list?

Answer 9

The first node (triplet) in a linked list.

Question 10

What is a doubly linked list?

Answer 10

Collection of such (previous,key,next) list-triplets we can traverse by some index like an array.

Question 11

Accessing the i-th item in a list?

Answer 11

O(n) since you must traverse from the head to the i-th node.

Question 12

Adding an item to the end of a list?

Answer 12

O(1) if you use the tail pointer.

Question 13

What is a queue?

Answer 13

A FIFO (first-in-first-out) data structure.This has O(1) cost for allowing elements to be added or removed.

Question 14

What is a stack?

Answer 14

A FILO (first-in-last-out) data structure. Has O(1) cost for pushing or popping elements from the top of the stack

Question 15

What is a rooted binary tree?

Answer 15

A tree with a starting root node where each node has ≤ 2 children.

Question 16

Structure of a binary tree node?

Answer 16

(left, key, right) triplet.

Question 17

What is a graph?

Answer 17

A set of vertices and edges representing relationships.

Question 18

What is an adjacency matrix?

Answer 18

A 2D array showing vertex connections in a graph.

Question 19

What is an adjacency list?

Answer 19

An array of lists storing only adjacent vertices.

Question 20

What is a hash function?

Answer 20

A function that maps data (keys) to integer indexes.

Question 21

What is a hash table?

Answer 21

A structure using a hash function to store and access data in O(1) time.

Question 22

What is a hash collision?

Answer 22

When two keys map to the same hash table index.

Question 23

How to resolve hash collisions?

Answer 23

By chaining (linked lists) or open addressing (probing).

Question 24

What is chaining?

Answer 24

Storing colliding entries in a linked list at each hash table slot.

Question 25

What is open addressing?

Answer 25

Finding another free slot via probing when a collision occurs.

Question 26

What is merge sort?

Answer 26

Sorting algorithm using a list of time complexity O(nlogn) which uses a divide and conquer approach. The array is recursively split in half and when elements are by themselves and uses comparison of these subproblems to sort them and rebuild the full list.

Question 27

What is an array?

Answer 27

Fixed data structure with elements of the same data type(reason is for memory allocation) . Has O(1) time to access and writing on an index even in multi-dimensional arrays?

Question 28

How should a multi-dimensional array be organised in memory? Is getting to (and writing on) x[i,j] still O(1)

Answer 28

Access is still O(1) because: x[i] is O(1) list indexing x[i][j] is another O(1) indexing on the inner list

Question 29

What is NIL ?(think of pointers)

Answer 29

This is a pointer to nowhere. This is well defined by if attempting to modify it it will cause nan error

Question 30

Explain what a list-triplet is for a doubly-linked list?

Answer 30

Previous : A pointer to some data that immediately precedes r in some ordering Key: Value of interest Next: a pointer ti sine data , that immediately succeeds r in some ordering

Question 31

Can we index a linked-list

Answer 31

No, in a linked list we cannot direct index into the i-th element, we must start at the head and follow the .next pointers one-by-one. Nodes are not stored contiguously in memory (in singly or doubly-linked list.

Question 32

What are the algorithms and there time complexities for a linked-list (list operations

Answer 32

ListAccess. : Return the key of the i-th element of a list of interest O(i) -can technically say O(n) if i=n List Search: return the list-triplet with key value, if it exists, otherwise return NIL, O(n) worst case

Question 33

What are lists?

Answer 33

Data structure which has O(1) cost of adding/removing items. Both stack sand queues have operations similar to this. This data structure can hold different data types and does NOT have a fixed length like an array.

Question 34

Trees vs arrays Discuss how you would implement a rooted binary tree using arrays.

Answer 34

1) Use indexing such that left child of node at index i -> 2i , right child -> 2i+1 , Parent -> lower bound of i/2 Advantages : - fast access of index Space -efficient for complete trees Dis: - wastes space for unbalanced trees - not dynamic

Question 35

Write down two limitations of worst-case asymptotic analysis of algorithmic running time.

Answer 35

ignores typical performance (average or practical cases ) Disregards input distribution

Question 36

Write down two advantages and two disadvantages of linked lists compared to arrays

Answer 36

Advantages : - dynamic size (can grow or shrink without allocating extra memory) - Efficient Insertion / Deletion because of use of pointers as only they need to be updated( elements dont need to be shifted like in arrays) Disadvantages : - Slower data access speeds - Inefficient memory allocation(extra memory usage)