======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