User Tools

Site Tools


haas:fall2013:common:data-a00-20121005235959

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?

  1. before: 24, after: 48
  2. before: 2, after: 4
  3. before: 4, after: 4
  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?

  1. known quantity of values available upfront as the program starts execution
  2. ease of expansion should the data set grow beyond original expectations
  3. quick and linear lookup of individual elements, even accessible via arithmetic equation
  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:

  • 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?

  1. array of floats (array index correlates to int value of input)
  2. 2D array of floats (one dimension is a float casted version of int, other is the float)
  3. singly linked list of custom nodes (containing int and float members)
  4. 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?

  1. Jon, 57345000
  2. Fey, 12345678
  3. Joe, 13570000
  4. Tom, 34125678
haas/fall2013/common/data-a00-20121005235959.txt · Last modified: 2012/10/01 22:00 by 127.0.0.1