Data Structure Midterm - Dr. A. Ebrahimi Spring 2003

Q1a) Name 4 data structures and give one application for each

Q1b) Give one advantage of static data structures versus dynamic data structures

Q1c) Give one advantage of dynamic data structure versus static data structures

Q1d) write the order on notations for the following searching algorithm. Write them from smallest to the largest. Hashing, bubble sort, linear search, binary search, and quick sort.

Q2a) Sort the following data according to Bubble sort float box[]= {10, 2 , 8, 3, 4, 1};

Q2b) Sort the above data according any other sorts you are familiar.

Q2c) What is the best case of bubble sort? The Program places the largest number to Q2d) Write a sort program that uses the following: assume the swap function is available swap (box[p], box[p+1]); use the index p and q. The size of array is n=6;

Q2e) What is wrong with the following swap function if it is used in the sort program and how would you resolve the problem.

swap (int x, int y) { int temp; temp=x; x=y; y=temp; }

Q3a) Apply the Linear search for the following data float box[]= {10, 2 , 8, 3, 4, 1};

Search for the number 8 and number 5. Explain the steps. How many comparison you need to search for the number 8.

Q3b) Assume the box is sorted how many comparison you need to search for the 5?

Q3c) Write a binary search using the box, x as the search key, begin, end, and middle.

The size is n=6

Q3d) Convert the above program using recursive function and call it

recbinsearch (box, begin,end);

Q4a) Convert the following infix expression to postfix expression

((2+3)-5) * 4

Q4b) Evaluate the expression 4 3 - 5 *. Show your stack after each push and after each pop.

Q4c) Write a program that uses stack with the following function push (int x) int pop( ). int sempty() and isfull( )

Data is in the string postfix=”4 3 - 5 *”; remember that string end with null and there is an space between operands and operators. For simplicity all numbers are only one digit.

Q4d) Write a program that converts the character 123 onto number 123.

Q5a) Write a function that generate four numbers randomly 1 to 4.

Q5b) How do you test that a queue is empty and how about the queue is full

Q5c) Write a function that show the code for enqueue. Use the myqueue as your variable array, begin as an index to the beginning and the variable end as an index to the end.

Q5d) write a function for the dequeue( ) according to the above variables.

System Design Dr. A. Ebrahimi, Midterm Spring 2003 Answer 5

Q1a) Compare the sequential file with random access file in terms of deletion and modification. Why is sequential file insufficient?

Q1b) Show the code that makes a file available, access it, rename it, and delete it from the system.

Q1c) Show the code for making a file accessible as a random access file. Show the construct for positioning the marker for reading and writing. What do you need to make deletion or modification work with random access? What is the constraint?

Q1d) Show the code to modify a price with a new price using array.

For the above, do not write the entire program, just the necessary code.

Q2a) Create a GUI using the ten commandments of HTML, including href, table, form, list, and input.

Q2b) What is Object-Oriented design paradigm and name its components. How OO will enhance design and implementation of a system?

Q3a) Write a CGI, ASP, or Java program that takes a name as input from Web page and displays telephone number back to a Web page.

Q3b) What do you need to make the above server program to work?

Q4a) Explain how a database like Access or DB2 can be used with a programming language such as VB, C++, etc. Show the code for connection, insertion, deletion, and modification.

Q4b) Write a command of SQL and show how it can be incorporated it in your program.

Q5a) Name and explain five important steps in design, analysis and implementation of a system.

Q5b) What are five important steps you need to make your system Web-oriented? Indicate the client and server side. Include some of the system commands.

Q6a) Give one example for each of the following: validation for input, computation, and output.

Q6b) Give two steps in making your system secure. Write a simple code to demonstrate the security.

Q6c) Write a simple program to encrypt a file.