AAMU Math&CIS CMP507 Data Structure & Algorithm Homework #1 Due:1/26/98
1. What is computer science ?
Computer science is science, mathematics and logic, engineering,
communication and interdisciplinary
2. What is collating sequence ?
The order of internal value of characters in an encoding system
from lowest to highest.
3. What are the 5 methods to represent an integer ?
a. Unsigned
b. Sign-magnitude
c. 1's complement
d. 2's complement
e. Excess 2**(n-1)
4. What are the 7 categories of instructions ?
a. Input statement
b. Arithmetic and logical statment
c. Assignment statement
d. Selection statement
e. Iteration statement
f. Output statement
g. Control statement
5. What are the 4 aspects of a variable ?
a. Name (identifier, must start with alphabet)
b. Value (range depend on data type)
c. Memory address (an integer value, also called pointer)
d. Other attributes (such as type, dimensions, ..)
6. What is an algorithm ?
A step by step procedure to perform a specific task.
Algorithm means a precise method useable by a computer for the
solution of a problem. An algorithm must:
a. definite, means that it must be perfectly clear what should
be done.
b. effective: each step must be such that it can be done by a
person using pencil and paper in a finite amount of time.
c. produces one or more output.
d. may have zero or more inputs which are externally supplied.
e. terminates after a finite number of operations.
7. What are the phases of software development life cycle ?
- Request for Proposal (RFP)
- Proposal
- Requirements Analysis
- Feaiblity Study
- System Analysis
- System Design
- Program design
- HIPO/flowchart
- Coding
- Testing/Debugging
- Documentation
- Maintenance and Enhancement
- Data flow and test cases
- Graphics User Interface (GUI).
8. What is an abstracted data type ?
ADT is a way of packaging some
intermediate-level data structures and their operations into a
useful collection whose properties have been carefully studied
and with clean and simple interface. The ADT define "WHAT" and
not "HOW" to implement.
9. What is the linked representation ?
Linked data representations are especially useful for applications
in which it is difficult to predict the size and shape of the
data structures needed. The Linked representation can grow and
shrink piece-by-piece. A pointer is just the memory address of
a block of storage.
10. What is dereference ?
When we follow a pointer to the unit of storage
for which the pointer value is the address, we dereference the
pointer. i.e. indirect addressing.
11. What is aliases ?
Two pointers (names) point to the same memory location.
12. What is an inaccessible pointer ?
Means that nobody can access it to read its value or
stor a value into it.
13. What is a dangling pointer ?
A dangling pointer points the same location that other pointer
used to point to.
14. Compare the pro and con of dynamic and static memory allocation.
The static memory allocation can produce more efficient code.
Therefore save space and time. It is used when the size of
the meory needed is known.
The dynamic memory allocation provides the flexibility in the
situation that the size of memory required is not fixed. The
storage aloocated can shrink or expand while the program is
running.
15. Compare the pro and con of iteration and recursive functions.
Iteration is the looping construct used in almost every programming
language. It is easy to comprehend and easy and construct.
The iteration version of program is more efficient in terms of
space and time required.
Recursive function is simple and elegant. If the application is
recursive nature, then the recusive function reflects the construct
and algorithm of the aplication problem. But, the recursive function
requires more stack space and less efficient in execution.
16. What is top-down design ?
To decompose a complex problem into several
subproblems repeatedly until all the subproblems are simple enough
to have a simple solution.
17. Why recursive concept is important in computer science ?
Recursion is an important concept in computer science. It can
sometimes be used to formulate unusually simple and elegant
solutions to problems that are hard to solve otherwise. Recursion
is the best choice for those applications which are recursive nature.
18. What is the base case in a recursive program ?
The base case is the simple subproblem which has a simple solution.
The base case is can be used to stop the endlessly splitting the
problems into subproblems and calling itself recursively.
The base case can be solved by giving their solutions directly.
(without using any more recursive calls)
19. Write an iteration program in C to find Fibonacci(n).
int Fibonacci(int n)
{
int fn, fnm1, fnm2, i;
if(n==0 || n==1) return n;
fnm2 = 0; fnm1 = 1;
for(i=2; i<=n;i++) {
fn = fnm1 + fnm2;
fnm2 = fnm1; fnm1 = fn;
}
return fn;
}
20. Write a recursive function in C to find Factorial(n).
int Factorial(int n)
{
if(n==1) return 1;
return (n*Factorial(n-1));
}