※ [本文轉錄自 NTU-Exam 看板 #1Lko34Bp ]
作者: rod24574575 (天然呆) 看板: NTU-Exam
標題: [試題] 103下 林軒田 資料結構與演算法 期中考+解答
時間: Fri Jul 31 15:16:17 2015
課程名稱︰資料結構與演算法
課程性質︰必修
課程教師：林軒田
開課學院：電資學院
開課系所︰資工系
考試日期（年月日）︰2015.04.21
考試時限（分鐘）：120分鐘
試題 :
Midterm Examination Problem Sheet
TIME: 04/21/2015, 14:20-16:20
This is a open-book exam. You can use any printed materials as your reference
during the exam. Any electronic devices are not allowed.
Any form of cheating, lying or plagiarism will not be tolerated. Students
can get zero scores and/or get negative scores and/or fail the class and/or be
kicked out of school and/or receive other punishments for those kinds of
misconducts.
Both English and Chinese (if suited) are allowed for answering the questions.
We do not accept any other languages.
┌─────────────────────────────────────┐
│There are 5 problems in the exam, each worth 40 points─the full credit is│
│200 points. Some problems come with two sub-problems to help you get │
│partial credits, making a total of 9 sub-problems. For the 9 problems, 3 │
│of them are marked with * and are supposedly simple; 4 of them are marked │
│with ** and are supposedly regular; 2 of them are marked with *** and are │
│supposedly difficult. │
└─────────────────────────────────────┘
1. C and C++
(a) (20%, *) Give a concrete example in C/C++ to explain in your own words
on how memory leak could happen.
Ans: int &func(){
int *res = new int(1126);
return (*res);
}
int a = func();
In the code above, "res" is allocated in func, and then (*res) is
copied to a. So the space pointed by res can never be freed, and
becomes "garbage" (memory leak) in the memory.
(b) (20%, *) Suppose we use the following class to represent the homework
scores of a student in DSA class:
1 class myScore {
2 public:
3 myScore(int n = 10){ size = n; hwScore = new int[size]; }
4 ~myScore(){ delete[] hwScore; }
5 string name;
6 int *hwScore;
7 };
Draw the memory layout after running the following code snippet, and
explain the potential hazards/problems of the code.
1 myScore a(6);
2 a.name = "John"; a.hwScore[0] = 85; a.hwScore[1] = 90;
3 myScore b = a;
4 b.name = "Mary"; b.hwScore[0] = 70;
Ans: a b
┌────────┐ ┌────────┐
name│ "John" │ name│"John" → "Mary"│
├────────┤ ├────────┤
hwScore│ │ hwScore│ │
└────┼───┘ └────┼───┘
│ ┌────────┘
│ ↓
│ ┌───┬──┬──┬──┬──┬──┐
└──→│85→70│ 90 │ 0 │ 0 │ 0 │ 0 │
└───┴──┴──┴──┴──┴──┘
The copy constructor called at "myScore b = a" copies the address
of a.hwScore to b.hwScore, making the two objects share the same
array which is wrong and dangerous (In destructor, there can be
double-free)
2. arrays and linked lists
(a) (20%, **) Assume that you have a vector of N integers that are between
1 and M. Write down the pseudo code of an O(N)-time O(M)-space
algorithm that determines whether all the integers are different from
each other (that is, whether they are all distinct).
Ans: ‧ initialize an array count[1…M] with 0
‧ for i ← 1 to N
count[i-th element of vector] increased by 1
if count[i-th element of vector] > 1
return FALSE
‧ return TRUE
(b) (20%, *) Suppose we have a singly linked list with each node defined by
the following class:
1 class node {
2 public:
3 string data;
4 node *next;
5 }
Write a C/C++ function invert(node *head) that can invert the list
pointed to by head and return the pointer to the inverted list without
doing any dynamic memory allocation.
(Hint: Note that your function should not need more than 20 lines.)
Ans: node *invert(node *head) {
node *current = head; node *prev = NULL;
while(current->next != NULL){
node *tmp = curent->next;
current->next = prev;
prev = current;
current = tmp;
}
current->next = prev;
return current;
}
3. stacks and queues
(a) (20%, **) Show how a stack can be used to evaluate the postfix
expression
9 8 7 2 3 * - / - 5 2 - * 3 /
step by step. All the operators within the expression are binary, and
you should draw the stack status after each step.
Ans: word stack
9 9
8 98
7 987
2 9872
3 98723
* 9876
- 981
/ 98
- 1
5 15
2 152
- 13
* 3
3 33
/ 1
(b) (20%, **) Suppose you have a deque D that stores N elements (d_0, d_1,
..., d_(N-1)), in this order, and an initially empty queue Q. Give a
pseudo-code description of a function that uses only D and Q (and no
other variables or objects) such that the elements within D are
reversed─that is, are stored like (d_(N-1), d_(N-2), ..., d_0) in D.
Ans: ‧ while not D.empty()
Q.enqueue(D.pop_back())
‧ while not Q.empty()
D.push_back(Q.dequeue())
4. the evil complexity
┌───────────────────────────────────┐
│The notation f(n) = O(g(n)) applies to functions f(n) and g(n) from N │
│to R+∪{0}, and f(n) = O(g(n)) if and only if there exists n_0 ≧ 1 │
│and c > 0 such that ∀n ≧ n_0, f(n) ≦ cg(n). Please only use the │
│definition above in your proof. │
└───────────────────────────────────┘
(a) (20%, **) Prove or disprove the following statement: If f(n) = O(g(n)),
then (f(n))^2 = O((g(n))^2).
Ans: if f(n) = O(g(n))
∃ n_0 ≧ 1 and c > 0 s.t.
f(n) ≦ c·g(n) for n ≧ n_0
then by f(n) ≧ 0 (f(n): N → R+∪{0})
for n ≧ n_0, (f(n))^2 ≦ c·g(n)·f(n)
≦ c·g(n) · c·g(n)
＝ (c^2)·(g(n))^2
let n_1 = n_0, c_1 = c^2
from above, for n ≧ n_1, (f(n))^2 ≦ c_1·(g(n))^2
that is, (f(n))^2 ＝ O((g(n))^2)
(b) (20%, ***) Prove or disprove the following statement:
If |f(n) - g(n)| = O(1), then 2^(f(n)) = O(2^(g(n))).
Ans: if |f(n) - g(n)| = O(1)
∃ n_0 ≧ 1 and c > 0 s.t.
|f(n) - g(n)| ≦ c for n ≧ n_0
then
f(n) - g(n) ≦ |f(n) - g(n)| ≦ c
that is
f(n) ≦ g(n) + c
=> 2^(f(n)) ≦ 2^(g(n))·2^c
let n_1 = n_0, c_1 = c^2
from above, for n ≧ n_1, 2^(f(n)) ≦ c_1·2^(g(n))
that is, 2^(f(n)) ＝ O(2^(g(n)))
5. (40%, ***) Given a sorted (ordered) vector a with N distinct integers where
a[0] < a[1] < ... < a[N-1]. The N integers define N+1 non-overlapping ranges
(-∞, a[0]], (a[0], a[1]], ..., (a[N-1], ∞) in R. Given a value x, a common
task is to determine the range that x falls in. Write down the pseudo code
of a (logN)-time algorithm that determines the range. For simplicity, you
can assume that x is different from all elements in a. (Hint: Think about
binary search and finding the largest a[n] that is smaller than x)
Ans: func. find Range (a, N, X)
if x ≦ a[0]
return (-∞, a[0]]
else if x > a[N-1]
return (a[N-1], ∞)
else
left ← 0
right ← N-1
while(left < right - 1){
mid ← floor((left + right) / 2)
if a[mid] ≧ x
right ← mid
else
left ← mid
}
return (a[left], a[right])