User Tools

Site Tools


haas:spring2013:common:data-a01-20121019235959

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?

  1. size: 1, value: 146
  2. size: 1, value: -111
  3. size: 2, value: 730
  4. size: 73, value: 'A'+81

0x1: Array or Linked List

Of the following criteria, which WOULD be a reason to use a linked list?

  1. known quantity of values available upfront as the program starts execution
  2. quick and linear lookup of individual elements, even accessible via arithmetic equation
  3. dynamic expansion during runtime, and no initial size may be known to the program
  4. 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?

  1. array of floats
  2. array of structs (containing float and int)
  3. doubly linked list of custom nodes (containing int and float)
  4. 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?

  1. Jon, 57345000
  2. Fey, 12345678
  3. Joe, 13570000
  4. Tom, 34125678
haas/spring2013/common/data-a01-20121019235959.txt · Last modified: 2012/10/15 13:47 by 127.0.0.1