Quiz Instructions

Setting the pointer to a malloc()'ed chunk of memory to NULL after free()'ing it is:

A. necessary, as the final step of freeing up the memory the pointer variable had been referencing

B. mandatory, otherwise the program will not compile

C. mandatory, otherwise the program will have runtime errors

D. unnecessary, because it is automatically set to NULL anyway

E. a good programming habit, to protect your program from accessing the memory the pointer had been pointing to

Suppose that 8-bit two's complement numbers are being employed. What bit pattern corresponds to the decimal integer value −50 (negative fifty):

A. 11001111

B. 00110010

C. 11001110

D. 11001101

C. 01001110

In the 32-bit floating point system (for float variables) that was explored using the floatbits.c program the following bit patterns are observed for the three given values, expressed as four 8-bit bytes:

    2.0 =  01000000 00000000 00000000 00000000
    3.0 =  01000000 01000000 00000000 00000000
    4.0 =  01000000 10000000 00000000 00000000

The bit pattern corresponding to the decimal number 5.0 is most likely to be:

A. 01000000 11000000 00000000 00000000

B. 01000001 10100000 00000000 00000000

C. 01000000 10100000 00000000 00000000

D. 01000000 10101000 00000000 00000000

E. 01000000 10010000 00000000 00000000

The best description of a FILE* pointer is that it stores the address of:

A. The next unprocessed byte from the file that is being read

B. An integer file number that is assigned by a call to fopen()

C. The first byte from the file that is being read

D. A structure that is created by a call to fopen()

E. The complete set of bytes from the file that is being read, including the ones that have already been processed

Suppose that some algorithm requires that a sequence p insertion operations and q search operations be performed on a dictionary data structure, with insertions and search operations interleaved in an unknown order, and with the dictionary empty at the beginning of the sequence.

Which of the following is the most correct and precise statement about the overall data structure time required to carry out the total sequence of p + q dictionary operations:

A. If a sorted array is used to store the data, the cost attributable to the dictionary will be O((p + q) q) in the worst case

B. If a sorted array is used to store the data, the cost attributable to the dictionary will be O(p2 + q log p) in the worst case

C. If an unsorted array is used to store the data, the cost attributable to the dictionary will be O(p + q2) in the worst case

D. If a binary search tree is used to store the data, the cost attributable to the dictionary will be O((p + q) log p) in the worst case

E. If a hash table is used to store the data, the cost attributable to the dictionary will be O(p + q) in the worst case

The offset associated with the third alignment is？

The value of S[0] is

A program is being written to manipulate data about books in libraries. Each book has a unique integer book number assigned to it, an author, a title, a publisher, a year of publication, a count of the total number of times it has been borrowed, and an array storing the integer library card numbers of the (up to) ten people who borrowed it most recently. The book title, author, and publisher strings may contain up to forty characters.

The library itself might contain as many as 100,000 books.

Give suitable #define, typedef, and then variable declarations to represent the books being held by the library.

Be sure to select "Preformatted" for the LMS text box before you enter each answer, and (if necessary) again after you have typed your answer. You will need to use spaces for indentation, as tabs cannot be typed into the LMS text box.

Suppose that an integer array is being used to store sequences of values that are strictly positive, for example:

    {1,1,1,2,2,2,2,2,5,4,4,1,1,1,1,1,1,3,3,3,0}

The last value in the array is always zero, and provides a sentinel, meaning that a buddy variable is not required.

A student notices that there are often repeated values straight after each other, and suggests that the data could be restructured into a packed form, with negative numbers introduced to indicate repetitions of the previous (positive) value. For example, the same data would be represented in this packed form as:

    {1,-2,2,-4,5,4,-1,1,-5,3,-2,0}

In this packed representation each negative value –n means that the immediately preceding value from the array should be duplicated another n times. For example, the first three values of the original array, {1,1,1}, are represented by the first two values of the packed array, {1,-2}.

Write a function

    void pack(int A[])

that carries out that transformation, replacing the sequence of positive values in A[] by the corresponding packed form.

Because the packing process can never make the total number of elements larger, A[] is guaranteed to already be large enough to contain the packed sequence. That means that you do not need to and should not declare any further arrays within your function. Don't forget to place a sentinel value at the end of the packed array.

Be sure to select "Preformatted" for the LMS text box before you enter each answer, and (if necessary) again after you have typed your answer. You will need to use spaces for indentation, as tabs cannot be typed into the LMS text box.

The next three questions relate to the following declarations. Study them carefully and the other information provided here, and then move on to the questions.

A set of simplified declarations is being used to represent binary search trees in which each stored element is of type data_t:

    typedef struct tree tree_t;
  
    struct tree {
        data_t  data;      // the data stored at this node
        tree_t *left;      // left subtree of node
        tree_t *rght;      // right subtree of node
    };

Two objects of type data_t can be compared in the usual manner by calling the function:

   int cmp_data(data_t *d1, data_t *d2)

A tree_t can store duplicate elements by simply inserting the second instance of any value as if it was very slightly greater than the first instance of that value. For example, the tree constructed by inserting the strings

    "fat", "cat", "fat", "bat", "eat", "rat", "fat", "cat"

would be:

                   fat
                /       \
           cat             fat
          /   \               \
       bat     eat             rat
              /                /
           cat              fat

The "handle" to access a tree is of type tree_t *, and an empty tree is represented by the value NULL.

You only need to submit the required function, but may include other functions too if you decide to break the process into smaller parts. Do not submit a main program.

In the context of the declarations that have been provided, write a function

   int sum_tree(tree_t *t);

that applies another function

    int get_int(data_t *d)

to each data item stored in the tree, and calculates and returns the sum of the integer values generated by the calls to get_int(), added up over all of the data_t elements stored in the tree. If t is empty then sum_tree(t) should return zero. You do not need to write get_int(), and may call it without knowing anything about its operation.

Include a comment prior to each main block of code to indicate your intentions.

Be sure to select "Preformatted" for the LMS text box before you enter each answer, and (if necessary) again after you have typed your answer. You will need to use spaces for indentation, as tabs cannot be typed into the LMS text box.

In the context of the declarations that have been provided, write a function

    tree_t *bst_insert(tree_t *t, data_t *d);

that creates a new tree node that stores the data value indicated by *d, and inserts it into the correct place in t, returning the new address of the root of the tree.

For example, a typical calling sequence for this function might be:

    tree_t *t=NULL;
    data_t d;
    while (get_value(&d)) {
        // now insert d into t
        t = bst_insert(t, &d); 
    }
    // t now contains all of the data

Include a comment prior to each main block of code to indicate your intentions.

Before starting to answer this question, you should read the next question too. You may find it convenient to develop a single helper function that can assist with both bst_insert() and the bst_merge() function required by the next question.

Be sure to select "Preformatted" for the LMS text box before you enter each answer, and (if necessary) again after you have typed your answer. You will need to use spaces for indentation, as tabs cannot be typed into the LMS text box.

In the context of the declarations that have been provided, write a function

    tree_t *bst_merge(tree_t *t1, tree_t *t2);

that constructs and returns a single tree containing the union (the merge) of the elements in t1 and t2, by combining them and at the same time destroying the original trees.

For example, a typical calling sequence for this function might be:

    tree_t *t1=NULL, *t2=NULL;
    ...        // construct tree t1
    ...        // construct tree t2
    t1 = bst_merge(t1, t2);
    t2 = NULL; // this tree not required now

Include a comment prior to each main block of code to indicate your intentions.

Be sure to select "Preformatted" for the LMS text box before you enter each answer, and (if necessary) again after you have typed your answer. You will need to use spaces for indentation, as tabs cannot be typed into the LMS text box.