UCSD--DataStructure--LeCode/Midterm Main notes at main · Cmint9/UCSD--DataStructure--LeCode · GitHub

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
Here are the notes for the Midterm and the problems from the UCSD Course:

# Question 1: The following code finds the number of digits in an integer. Identify the correct algorithm to find the maximum number of digits in an integer array.

FindLen(value) {
   if (value == 0)
      return 1
   digits = 0
   while (value != 0) {
      digits = digits + 1
      value = value / 10
   }
   return digits
}

Correct Answer:
FindMaxLen(listOfAges, listSize) {
   maxDigits = 0
   for (i = 0; i < listSize; i++) {
      digitCount = FindLen(listOfAges[i])
      if (digitCount > maxDigits)
         maxDigits = digitCount
   }
   return maxDigits
}

Reason to pick the wrong answer: "digitCount = FindLen(listOfAges[i])" it should be call function 'FindLen' not 'FindMaxLen'.


# Question 2: Given the list (11, 22, 25), which is the correct way to add 32 to the list in ascending order?

correct Answer:   InsertAfter(list, 25, 32)
  InsertAfter(list, 32)
  Prepend(list, 32, 25)
  Prepend(list, 32)

Reason to pick the wrong answer: it should have 25 before 32, hence is (list,25,32)


# Question 3: Identify the commands for the following list operations.
Check that there are no items in a list
Insert 10, 50, 30, 40, and 20 at the end of the list
Arrange the items in ascending order

Correct answer:

IsEmpty(list)

Append(list, 10)

Append(list, 50)

Append(list, 30)

Append(list, 40)

Append(list, 20)

Sort(list)
Reason to pick the wrong answer: It should be use "Append", not "Prepend".


# Question 4: Which XXX would complete the following Python insertion sort algorithm?
def insertion_sort(num_list):
    for i in range(1, len(num_list)):
        j = i
        XXX:
            temp = num_list[j]
            num_list[j] = num_list[j - 1]
            num_list[j - 1] = temp
            j -= 1

Correct Answer:  while num_list[j] < num_list[j - 1] and j > 0
Reason to pick the wrong answer: from the code, we can know they need do compare, and we
need to know how to compare them correctly.


#Question 5: For forward traversal of a singly-linked list, the ListTraverseRecursive(node) function must _____.
Wrong answer:   call ListTraverseRecursive(node⇢next), then visit the node
Correct Answer: visit the node, then call ListTraverseRecursive(node⇢next)
                 Call ListTraverseRecursive(node), then visit the node
                 visit the node, then call ListTraverseRecursive(node)

Reason to pick the wrong answer: is that it should be visited first to see how many nodes there are and which nodes.
Then can call the function to traverse the nodes.


Question 6:What is the runtime complexity notation for the following algorithm?

LowNum(listOfAgeGroups, listSize, myAge) {
   for (ctr = 0; ctr < listSize; ++ctr) {
      if (listOfAgeGroups[ctr] == myAge)
         return ctr
      }
   }
 }

Reasons to pick the wrong answer: for loop through the ctr, and being compared it should be O(N) not O(1).


Question 7: The lower bound of an algorithm’s runtime complexity is _____.
You Answered: ≥ the best case
Correct Answer:≤ the best case
               ≤ the worst case
               ≥ the worst case

Reason to pick the wrong answer: the lower bound that's means it should be the smallest nuber or range.
Hence, we should pick the answer smaller and equal to the best case.

Question 8: Which of the following statements is correct?
               The queue ADT supports the insertion and deletion of items at the front and the back.
Correct Answer: The list ADT supports the printing of the list contents, but the queue ADT does not.
You Answered: The queue ADT supports the removal of items from one end and the adding of items to the other end but the list ADT does not.
              The queue ADT supports the printing of the list content,s but the list ADT does not.