推 claire1204 :好快> <" 11/12 12:31
→ EternalChaos:我要從星期一的開始打XD 11/12 12:38
課程名稱︰資料結構
課程性質︰資管系必修
課程教師︰陳郁方
開課學院：管理學院
開課系所︰資管系
考試日期（年月日）︰2010/11/8
考試時限（分鐘）：180分鐘
是否需發放獎勵金：是
（如未明確表示，則不予發放）
試題：
1.Using ADT Polynomial described in Program Assignment 1 to compute
(3x^5+4x-6)*(4x^4-3x+3)+(12x^3+5x^6-4) [10pt]
[Hint] write a psedocode in the following form
Polynomial p1,p2;
//your implementation here
cout << p1.getPoly();
2.Recall that we have discussed the problem of "Organizing a Parade" : One is
asked to organize a parade, which consists of bands and floats in a single
line. The only rule is that one band cannot be put immediately after another.
[20pt]
A. Let P(n) be the number of ways to organize the parades.Write a recursive
function in C++ to compute P(n).
[Hint] int P(int n) { // your implementation here }
B.Let F(n) be the number of parades of length n that end with a float and B(n)
be the number of parades of length n that end with a band. Justify the
correctness of your implementation using B(n) and F(n) (i.e., explain why the
value returned by your function is indeed P(n) using B(n) and F(n)).
C.Explain why your implementation satisfies the 4 principles of a recursive
design.
D.Do the box-trace for P(5).
E.Explain what is tail-recursion. Is P(n) a tail-recursive function?
3.Write C++ headers of ADT List (Array-based and Pointer-based). Implement the
insert function and all the needed constructors (including copy constructors
and destructors). Assume a class ListException is already defined and can be
used directly. For efficiency concern, do not call the remove function in all
the implementations.
A.Array-based implementation and using exception. [15pt]
B.Poiner-based implementation and using exception (use pure linked lists, not
the variations). [25pt]
[Hint] ADT list has the following operations: isEmpty, getLength,insert,
remove and retrieve
4.Given the C++ header file of a Queue (queue.h) as follows. Implement the
enqueue and dequeue functions. Assume a class QueueException is already
defined and can be used directly. You should use the circular array-based
implementation. [20pt]
//queue.h
typedef int QueueItemType;
const int MAX_QUEUE=100;
class Queue
{
public:
Queue():front(0), back(MAX_QUEUE-1), isFull(False);
bool isEmpty() const;
void enqueue(const QueueItemType& newItem) throw(QueueException);
void dequeue() throw(QueueException);
private:
QueueItemType items[MAX_QUEUE];
int front;
int back;
bool isFull;//implement the version using a flag instead of a counter.
};
5.Write a C++ function converting an infix expression to
A. a postfix expression[10pt]
B. a prefix expression[10pt]
using STL (standard template library)
[Hint] Yo should use stack or queue in the implementation.
string toPrefix(string infix){
//your implementation here }
int precedence(char e){
if(e == '*' || e == '/') return 2;
else return 1; }
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.245.126