Lab46 Wiki

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
======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:

<code c>
int num1, num2, *num3;
unsigned char value1, *value2;

num1 = 12;
num2 = 24;
num3 = &num1;

value2 = &value1;

*value2 = 73;
</code>

If we were to do the following:

<code c>
num2 = num2 * 2;
value1 = value1 << 1;
</code>

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:

<code c>
struct node {
   unsigned int id;
   char *name;
   struct node *up;
   struct node *down;
};
</code>

And the following code that built a structure:

<code c>
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;
</code>

What is the name and id of the node **pos** is currently pointing at?

  - Jon, 57345000
  - Fey, 12345678
  - Joe, 13570000
  - Tom, 34125678
Lab46 Wiki

User Tools

Site Tools

Page Tools
