CSI 319 Midterm, Fall 2010

Here is nel 48s declar ation of array-implemented stack ae Stacl > . ekN contains the de laration of class Stack Basic operations Constructor constructs an empty stack Empty checks if stack is empty Push ' modifies stack by adding a value at He top = Pop Smodifies stack by removing the value ut the ee stack Top i retrieves the top of the stack without Cbangine Class Invariant: : ‘ » positions my 1 The stack elements (if any) are stored in can cuuuve p my Array, besinniny at position 0 2. -1 <= my Top < STACK CAPACIEY #itndef STACK #define STACK const int STACK_CAPACITY = 128: typedef int StackElement; class Stack ¢ a o***** Function Members *****/ public: // --- Constructor --- Stack(); NK // --- is the Stack empty ? --- bool EmptyQ const; \ // --- Add a value to the stack --- void Push (const StackElement value); \ // --- Return value at the top of the stack --- StackElement TopQ const; // --- Remove value at the top of the stack --- void popQ; /***** Tata Members *****/ private: StackElement myArray[STACK_CAPACITY]; int myTop; }; // end of class declaration #endif a) Develop the routines defined into the class STACK. } Pe Question #2 (10 pout 1 s) A string ts said to be a 1 the order of its charac qers oalindr , palindrome if it does not change wher is veversed. For example, are palindromes . SiMe y I nes. Write a function that, #iven a string, returns true if the sting isa palindrome and false otherwise Question #3 (10 points) d deletions May be additions an BGaLON a of the A double ended queue (dequeue) is a linear list in aaa ments from either en made at either end. Write algorithms to add and delete ele queue Question #4 (10 points) Convert the following arithmetic expres sions from infix to postfix & prefix: ((a*b—c/d**e)+f%g* (h* kK) (a*~b—-c+d-(-e/f** g**h%1)) Question #5 (10 points) Answer the following: sui ee a ASAE RS b) The value of He 44 Sed? is: c) Convert (a— (b+c))/d*e% f to postfix & prefix. d) Convert (G/HI(I*S)) * (D-E/F) to postfix & prefix. a) The value of Question no 0 poi » Ama nati 1s given in the following table Gy F e = 3 er of rows ant Write a function, that given an array of rows and columns with the numb the number of columins, will zero both the inverse diagonal and the part below the inverse diagonal of that array. : 4 ‘ Question #7 (12 points) “ut ; - a) What is the decimal value of the following binary number 1011-1010 2 b) Assume that stack has stacktype as int, and stack-capacity ~ 5. Give he contents of top & all array data member s of s after the code segment is executed. i) stack s; s.push (123); ii) stack s; iii) stack s; s.push (101); for (int i = 0; i<-4; i++) es, s.push (456); i=s.topQ; s.push(2 * i+ 4); We s-popQ; s.push (218); s.popQ; s.push(789); s.pop(); s.popQ; s.popQ; s.push (2*3+1); s.push(i*2 + 5)3 c) Assume that the base address of an array A[S5][3] of type double is 240 and the storage is column wise. What will be the addresses of the following data items in the array: A[3][2] and A[4][1] ? Question #8 (10 points) Write a C++ code to determine the highest value in a circular linked list of integer numbers with first node pointed to by first. i Question #9 (8 Points): é -xpression: For the following circular doubly-linked list, find the value of cach ©xP! [] 2 (ele 4 SS) i a | +—-—>| a) p2->data b) p2->next->next->data c) pl->prev->prev->prev->next d) pl->next->next e) pl->prev->next->next->prev f) pl->prev->prev->data g) pl->prev->prev->prev->prev h) pl->prev->prev->next->data Question #10: (10 pts) , than after ‘ ‘tis (4,5, 6 Write a C++ code to reverse a linked list. For example if the list is (4, reversing it becomes {6, 5, 4}. - Y 4 | ie) e GOOD LUCK ES rete