======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 **value1** occupy in memory, and what value is contained there following the execution of the above code?
- size: 1, value: 146
- size: 1, value: -111
- size: 2, value: 730
- size: 73, value: 'A'+81
=====0x1: Array or Linked List=====
Of the following criteria, which WOULD be a reason to use a linked list?
- known quantity of values available upfront as the program starts execution
- quick and linear lookup of individual elements, even accessible via arithmetic equation
- dynamic expansion during runtime, and no initial size may be known to the program
- 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:
* Fixed quantity floating point input values
* Tracking a float value tied to some integer index/key
* Each input value consists of a float
* Random input values are paired with a linearly increasing index/key
* Performance is important
Which is best for your base to structure the data?
- array of floats
- array of structs (containing float and int)
- doubly linked list of custom nodes (containing int and float)
- linked stack
=====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); // creates a new node, returns start of list
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 **tmp** is currently pointing at?
- Jon, 57345000
- Fey, 12345678
- Joe, 13570000
- Tom, 34125678