Purdue CS24000 Fall 2018 Midterm II Solutions

Posted on Edited on In Views: Symbols count in article: 5.7k Reading time ≈ 5 mins.

Purdue University CS24000 is an undergraduate-level course that teaches students programming principles and techniques for problem-solving in the C programming language. Here are the solution and study notes for the Fall 2018 Midterm 2 exam.

CS24000 Syllabus

Below are extracted from the Spring 2024 CS24000 course syllabus:

Disclosure: This blog site is reader-supported. When you buy through the affiliate links below, as an Amazon Associate, I earn a tiny commission from qualifying purchases. Thank you.

  • Reference: Beej’s Guide to C Programming; Brian “Beej” Hall; 2007
  • Course Outcomes: A student who successfully fulfills the course requirements will have the ability to:
    • write quality code that is readable, maintainable, and well commented
    • create, compile, and execute C programs using industry standard tools including the GNU Compiler Collection
    • apply debugging techniques to analyze, identify, and fix errors
    • assess and address security-related issues in code bases written in C
    • produce code that appropriately and properly utilizes pointers
    • solve problems through the application of explicit memory management
    • design and implement programs in C that utilize dynamic data structures such as linked lists and trees
  • Lectures:

Fall 2018 Midterm 2 Exam

Exam Solutions and Notes

Problem 1 (30 pts)

(a) Code without using array brackets:

1
2
3
4
5
6
7
8
9
10
11
int reverse(int *source, int *dest, int n) {
    int sum = 0;
    int* srcptr = source;
    int* dstptr = dest;

    for (int i = 0; i < n; i++) {
        *(dstptr + i) = *(srcptr + n - 1 - i);
        sum += *(dstptr + i);
    }
    return sum;
}}

In summary, the reverse function reverses the order of elements in the source array, stores them in the dest array, and calculates the sum of the reversed elements.

(b) The atomic weight of Aluminum is 26.981.

(c) Structure for a singly-linked list node containing an integer:

1
2
3
4
typedef struct single_node {
    int data;
    struct single_node *next;
} single_node_t;

(d) Function to prepend a node to a singly-linked list:

1
2
3
4
5
6
7
8
void push(single_node_t **head, single_node_t *node) {
    assert(head != NULL);
    assert(node != NULL);
    assert(node->next == NULL);
    node->next = *head;
    *head = node;
    return;
}

(e) Function to remove the first node from a singly-linked list:

1
2
3
4
5
6
7
8
9
10
single_node_t *pop(single_node_t **head) {
    assert(head != NULL);
    if (*head == NULL) {
        return NULL;
    }
    
    single_node_t *tmp = *head;
    *head = (*head)->next;
    return tmp;
}

Problem 2 (40 pts)

(a) Structure for a doubly-linked list node containing a string and an integer:

1
2
3
4
5
6
typedef struct double_node {
    char *name;
    int age;
    struct double_node *prev;
    struct double_node *next;
} double_node_t;

(b) Function to create a new doubly-linked list node:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
double_node_t *create(char *name, int age) {
    double_node_t *new_node = malloc(sizeof(double_node_t));
    if (new_node == NULL) {
        // Handle memory allocation failure
        return NULL;
    }

    unsigned_int name_len = strlen(name) + 1;
    new_node->name = malloc(name_len * sizeof(char));
    if (new_node->name == NULL) {
        // Handle memory allocation failure
        free(new_node);
        return NULL;
    }

    strcpy(new_node->name, name);
    new_node->age = age;
    new_node->prev = NULL;
    new_node->next = NULL;
    return new_node;
}

(c) Function to delete a node from a doubly-linked list:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void delete(double_node_t *node) {
    if (node == NULL) {
        return;
    }
    
    if (node->prev) {
        node->prev->next = node->next;
    }
    
    if (node->next) {
        node->next->prev = node->prev;
    }
    
    free(node->name);
    free(node);
}

(d) Function to insert a new node after a given node in a doubly-linked list:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void insert(double_node_t *node, double_node_t *new_node) {
    if (node == NULL || new_node == NULL) {
        return;
    }
    
    new_node->prev = node;
    new_node->next = node->next;
    
    if (node->next) {
        node->next->prev = new_node;
    }
    
    node->next = new_node;
}

Problem 3 (30 pts)

(a) Structure for a binary tree node:

1
2
3
4
5
6
typedef struct tree_node {
    int value;
    bool invalid;
    struct tree_node *left;
    struct tree_node *right;
} tree_node_t;

(b) The size of the tree_node_t structure on a 64-bit architecture system is 24 bytes (4 bytes for int, 1 byte for bool, and 8 bytes for each pointer).

(c) Function to mark a node as invalid:

1
2
3
4
5
6
void delete_node(tree_node_t *node) {
    if (node) {
        node->invalid = true;
    }
    return;
}

(d) Function to remove a node from a binary tree (assuming it's not the root):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
void free_node(tree_node_t *node) {
    if (node) {
        tree_node_t *parent = get_parent(node);

        // Case 1: Node has no children
        if (!node->left && !node->right) {
            if (parent->left == node) {
                parent->left = NULL;
            } else {
                parent->right = NULL;
            }
        }
        // Case 2: Node has only one child
        else if (!node->left || !node->right) {
            tree_node_t *child = node->left ? node->left : node->right;
            if (parent->left == node) {
                parent->left = child;
            } else {
                parent->right = child;
            }
        }
        // Case 3: Node has two children
        else {
            // Find the right most child of the left child
            tree_node_t *predecessor = node->left;
            while (predecessor->right) {
                predecessor = predecessor->right;
            }
            
            // Adjust the predecessor and its parent's children links
            tree_node_t *predecessor_parent = get_parent(predecessor);
            if (predecessor_parent != node) {
                predecessor_parent->right = predecessor->left;
                predecessor->left = node->left;
            }
            predecessor->right = node->right;
            
            // Promote it as the new child of the removed node's parent
            if (parent->left == node) {
                parent->left = predecessor;
            } else {
                parent->right = predecessor;
            }
        }

        free(node);
    }
}

(e) Recursive function to delete invalid nodes from a binary tree:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int flush_tree(tree_node_t *root, void (*my_del)(tree_node_t *)) {
    if (root == NULL) {
        return 0;
    }
    
    int deleted = 0;
    
    // recursively traverse the tree in postfix (L-R-N) fashion
    deleted += flush_tree(root->left, my_del);
    deleted += flush_tree(root->right, my_del);
    
    if (root->invalid) {
        my_del(root);
        deleted++;
    }
    
    return deleted;
}