Table of Contents
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