课程名称︰资料结构 课程性质︰资管系必修 课程教师︰陈郁方 开课学院：管理学院 开课系所︰资管系 考试日期（年月日）︰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