跳至主要內容

Quiz Instructions

AI悦创原创2023年10月26日墨尔本大学CSPython一对一辅导unimelb墨尔本大学CSPython一对一辅导unimelb大约 30 分钟...约 8972 字

Section 1 -- Multiple Choice (5 marks)

Question 1

EN

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

Question 2

EN

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

Question 3

EN

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

Question 4

EN

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

Question 5

EN

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

Section 2 -- Short Answer (12 marks)

Question 6

Suppose that the pattern

    now#or#never

is being used to search the text T given by

        0    0    1    1    2    2    3
        01234567890123456789012345678901234
    T = not#now#not#never#not#now#nor#never
    P = now#or#never

using the KMP algorithm that was presented in lectures.

The first alignment of the pattern is at offset 0 in T, and is where the pattern matching process commences, as shown in the diagram.

Trace the KMP algorithm as it operates from then on, and indicate the character offsets in T (using the numbers above the target string as a guide) of the third, fifth, and seveth alignments of the pattern.

1

The offset associated with the third alignment is?

Question 7

Consider the seven-character string "baa#bab", and an eight-element suffix array S[8] constructed for it. Fill in the values of the specified elements of S[].

When constructing the suffix array, assume that character '#' is smaller than any of the alphabetic characters, and that '$' is the special symbol appended to the string that is smaller than all of the normal characters.

1

The value of S[0] is

Question 8

The following declarations are exactly the same as the ones used in the file lists.h that was discussed in class.

    typedef struct node node_t;

    struct node {
        data_t data;
        node_t *next;
    };

    typedef struct {
        node_t *head;
        node_t *foot;
    } list_t;

A student wrote the following function to reverse the nodes in a list by reassigning all the pointers, so that the node (and data item) that used to be at the head of the list is now at the foot, and the node (and data item) that used to be at the foot of the list is now at the head. But four of the student's assignment statements have been lost.

Match the line locations on the left with the correct assignment statements on the right.

line A

Question 9

The first phase of heapsort converts the input array to an initial heap.

Suppose that an eight-element input array is given by

    A[] = { 10, 15, 16, 14, 20, 17, 22, 29 }

and gets converted to a heap by the first phase of heapsort.

Match the initial heap array locations on the left with the elements that they contain on the right.

A[0] has the value

Section 3 -- Programming (15 marks)

Question 10

EN

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.

Question 11

EN

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.

Question 12

EN

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.

Question 13

EN

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.

Question 14

EN

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.

Section 4 -- Algorithms (8 marks)

The next four questions relate to the following problem description. Read it carefully, and then move on to the questions.

A group of students are discussing how to compute the k th smallest value in an input array containing n values, where 0 ≤ k < n/2.

For example if the input array is:

    A[] = { -9, 17, 18, 12, 35, 24, 17 }

then when k=2, the value required is 17, because if A[] was sorted, then A[2] would be 17.

The input data is provided in an unsorted array, and represents a multi-set of items, meaning that duplicate values might exist. The process that determines the k th largest value is not permitted to reorder the elements in the input array, and they must remain in their original locations.

The next several questions involve a range of different algorithms that might be used to solve this problem, given these constraints.

All of the analyses that are given are precise. If a student says they can solve the problem in O(n log k), the algorithm that they are thinking of will require a number of steps that is directly proportional to n log k on at least some input arrays; and an algorithm that takes (say) O(n) time in the worst case will not be regarded as being a correct answer.

Note that the space required by an algorithm is the extra space required, and does not count the space occupied by the input array. The analyses of extra space are also all precise.

Question 15

Student A says, "this problem is easy to solve, and a solution can always be achieved in O(n + k**n) worst-case time, with O(1) extra space required".

Use the answer box below to describe in English or pseudocode the approach that Student A is thinking of.

You must give enough detail in your answer that the marker can be sure that the approach you are describing (a) will solve the problem, and (b) is consistent with the stated analysis.

Question 16

Student B says, "this problem is easy to solve, and a solution can always be achieved in O(n + k log n) worst-case time, with O(n) extra space required."

Use the answer box below to describe in English or pseudocode the approach that Student B is thinking of.

You must give enough detail in your answer that the marker can be sure that the approach you are describing (a) will solve the problem, and (b) is consistent with the stated analysis.

Question 17

Student C says, "this problem is easy to solve, and a solution can always be achieved in O(k + (nk) log k) time in the worst case, with O(k) extra space required".

Use the answer box below to describe in English or pseudocode the approach that Student C is thinking of.

You must give enough detail in your answer that the marker can be sure that the approach you are describing (a) will solve the problem, and (b) is consistent with the stated analysis.

Question 18

Students B and C then start arguing about whose algorithm will execute the fastest, and you need to stop them fighting. What should you tell them? And why?

You must give enough detail in your answer that the marker can be sure that you understand the interaction between the two formulas that have been provided. Note that you can answer this question even if you do not know what algorithms Students B and C are talking about.

Question 19

Working Space -- Will Not Be Marked

You may use this answer box for any working-out that you wish to do.

The contents of this box will NOT be marked.

公众号:AI悦创【二维码】

AI悦创·编程一对一

AI悦创·推出辅导班啦,包括「Python 语言辅导班、C++ 辅导班、java 辅导班、算法/数据结构辅导班、少儿编程、pygame 游戏开发、Web、Linux」,全部都是一对一教学:一对一辅导 + 一对一答疑 + 布置作业 + 项目实践等。当然,还有线下线上摄影课程、Photoshop、Premiere 一对一教学、QQ、微信在线,随时响应!微信:Jiabcdefh

C++ 信息奥赛题解,长期更新!长期招收一对一中小学信息奥赛集训,莆田、厦门地区有机会线下上门,其他地区线上。微信:Jiabcdefh

方法一:QQ

方法二:微信:Jiabcdefh

你认为这篇文章怎么样?
  • 0
  • 0
  • 0
  • 0
  • 0
  • 0
评论
  • 按正序
  • 按倒序
  • 按热度
通知
关于编程私教&加密文章