# 13 - Past Paper Simulation - DS 1 (A)

1. Data structures are of varying types. They can be static or dynamic. State the meaning of static. (1 mark)

2. State one type of data structure that is always considered to be static (1 mark)

3. State the meaning of dynamic (in reference to data structures) (1 mark)

4. Joel is considering using a dynamic data structure in his A level project. State one disadvantage of using a dynamic data structure (1 mark)

5. Shemroy heads up a large company that runs flights across cities in Europe. It stores the prices of different flights in its computer system. State a data structure that would be suited to represent the data above. (1 mark)

6. State what the code print (times["StopB"] [4]) displays.
```A tourist tram runs between two cities. There are a number
of stops on the tram route labelled StopA, StopB and so on.

The timetable for the route is represented as a hash
table. For each entry in the hash table the key is
the bus stop code and the data attached to it is a
(zero indexed) array of the times a bus arrives at
the stop. The times are stored as strings.

An extract of the hash table is shown below:```

7. Code is to be added to check if the word is an actual English word. All English words are stored in a binary search tree. Give one advantage of storing the words in a binary search tree over an array. (1 mark)

8. Jesse has started his own luxury car tour company that does tours of the UK. A linked list stores the names of cities in a car tour in the order they are visited. Describe the term linked list. Also state what is missing from the last node.(2 marks)

9. Jesse has ammended the tour (see image below). The new itinerary is: City L, City O, City M and then City Z. Explain how City B is removed from the linked list and how City Z is added. Use the diagram to explain (4 marks)
```For your answer, use the following but substitute the correct City
names (e.g. City O or City Z)

Explain which city pointer has to be changed
to bypass or to point to another city as well
as which nodes, if any, need to be created.

For example, write in this format:

City B pointer changed to bypass City O pointer
and point to City O. A node is created holding
the data City B. City X is placed in the next
free node. City O remains in original position.
Pointer changed to point to City O node. The
last node points to a null node. ```

10. Winston's program stores records about its customers.Often an individual customer's record needs to be accessed. This is done by searching using Customer ID. Why is a hash table is better suited than a linked list to store customer records. (2 marks)

11. Define the term stack, stating why it is suited to holding a web browser?s history.(2 marks)

12. The following code is known to crash certain browsers! j.toString() converts j to a string. It is the JavaScript equivalent to str(j). What does Line 5 do? (2 marks)
```var total = "";
for (car j = 0; j <200000; j++)
{
total = total + j.toString();
history.pushState(0,0,total);
}```

13. Oliver loves cats. For a game he is creating, he is using a binary search tree to store the names of cats. Explain how you would determine if the name 'Pootle' is in the binary search tree (3 marks)
```Please write your answer in the following format:

For example:

if Pootle > Chichi then go left
If Pootle < Chichi then go right
Found Pootle```

14. A program has been created to traverse each directory and file represented in a tree. It does this using a depth-first traversal. State what order it will visit each of the secret files (not folders) as shown below. Note the format below. (3 marks)
```Please write your answer in the following format.

For instance, if the order was secret1.doc, followed by secret2.doc, followed by secret3.doc and so on, write:

[secret1,secret2,secret3,secret4,secret5,secret6]

Don't forget to