======Data Structures Knowledge Assessment======
=====Overview=====
We have been going full force with our explorations of linked lists these past few weeks. Just to make sure we are all retaining this information, please complete the following (via **gimmeh**) by the due date.
=====0x0: Sizing=====
Say we had the following variable declarations and initializations, on a program compiled and run on Lab46:
int num1, num2, *num3;
unsigned char value1, *value2;
num1 = 12;
num2 = 24;
num3 = &num1;
value2 = &value1;
*value2 = 73;
If we were to do the following:
num2 = num2 * 2;
value1 = value1 << 1;
How many bytes does **num2** occupy in memory before and after seeing its contained value double in size?
- before: 24, after: 48
- before: 2, after: 4
- before: 4, after: 4
- before: 2.4 billion, after: 4.8 billion
=====0x1: Array or Linked List=====
Of the following criteria, which would NOT be a reason to use an array?
- known quantity of values available upfront as the program starts execution
- ease of expansion should the data set grow beyond original expectations
- quick and linear lookup of individual elements, even accessible via arithmetic equation
- consistency of type among each and every element available in the container
=====0x2: Implementation Considerations=====
If you were tasked with implementing a program that had the following criteria/constraints:
* Variable quantity input values
* Ablity to expand indefinitely is expected
* Each input value consists of 2 different data types (int and float)
* Input needs to be arranged in descending order according to the int component
* Resources are somewhat limited (optimize for storing data over convenience of accessing data)
What would you use as your base to structure the data?
- array of floats (array index correlates to int value of input)
- 2D array of floats (one dimension is a float casted version of int, other is the float)
- singly linked list of custom nodes (containing int and float members)
- doubly linked list of custom nodes (containing int and float members)
=====0x3: What is the value=====
Let's say we had the following node structure:
struct node {
unsigned int id;
char *name;
struct node *up;
struct node *down;
};
And the following code that built a structure:
struct node *db, *pos, *tmp;
int i;
db = newnode(db, "Bill", 12340000);
db = append(db, "Jim", 56780000); // adds new node "down" from current end of list
db = append(db, "Bob", 24680000);
db = append(db, "Joe", 13570000);
db = append(db, "Fey", 12345678);
db = append(db, "Jon", 57345000);
db = append(db, "Tom", 34125678);
db = append(db, "Tim", 21345678);
tmp = removeid(db, 13570000); // removes and returns node that contains the indicated id
pos = db;
pos = pos -> down;
for (i = 0; i < 3; i++)
pos = pos -> down;
What is the name and id of the node **pos** is currently pointing at?
- Jon, 57345000
- Fey, 12345678
- Joe, 13570000
- Tom, 34125678