DATA STRUCTURE
2015/2016, 2012/2013 (19ab)
1aDefine an Array
Ans:
Array is a particular way method of storing element of indexed data element of data are store sequentially within the each element is referenced by an index subscript
1b. Mention two type of array
Ans:
Two types of Array
(i)Bound Array
(ii)Unbound Array
1c.using a FORTRAN program declare an array of the following
i.One dimensional array
ii.Two Dimensional Array
iii.Describe how to access the content of an Array
Ans:
One dimensional array
Integer L (10)
Do 10 L = 1, 10
READ (* *) L EE (L)
CONTINUE
Stop
END
Two Dimensional Array
INTEGER Boy (2,2)
Do 4 R = 1, 2
Do 5 L = 1,2
READ (* *) boy
5 CONTINUE
4 CONTINUE
Describe how to access the content of an Array
INTEGER L (10)
Do 10 L = 1, 10
READ (* * ) LEE (L)
B = LEE (L)
10 CONTINUE
2a. Define Stack
Ans:
A stack is an order collection of items in which new item may be inserted and from which item may be deleted at one end called the top of the stack.
2b. List primitive operation on stack
Ans:
Primitive operation on stack
- Push: add an item into stack
- POP: remove an item from the stack
- Top: determined the top of the stack
2c.
Abstract push (s, elf)
Stack (eltypes) s,
Eltypeelt
Post condition s = = <elt> + s
Abstract eltype pop
Stack (eltype)
Precondition empty (s) = = false
Post condition pop = = first *=(s)
S = = sub (s, len (s))
2d. Differentiate between a depth first search and breadth first search
Ans:
Depth first search is a tree reach the element for array from the root
While
Breadth first search reach for the element close to the root
3a. Define a Graph
Ans:
A graph is a mathematical structure consisting of a set of vertex ( also called nodes ) (e1, e2, ----en) of edges.
An edge is a pair of var (V1, V2) I, j, E (I, m) vertex are called the edge end point
3b.Differentiate between a directed graph and undirected graph
Ans:
A directed graph can have as most undirected graph
while
An undirected graph can have (2) edges one of each unorder pair
4a. Define Data Structure
Ans:
Data structure: this is an abstraction of real life problem or a mathematical model of a real life problem.
4b. Differentiate between the following and give examples of each
(i)Real numbers and Integer number
(ii)Character and String
(iii)Binary number and Decimal number
Ans:
Real numbers: this is a floating point notation 4 real number is represented by a number called a mantissa, time base raised to an integer power called exponent. Ex 38887.53
While
Integer number: these are whole numbers
Character: it is the representation of such non numeric object, still another method of interpreting bit string. Ex: in some computers, the eight bit 0010010 are used to represent the character A.
While
String: this are letter with an apostrophe either double quote or single quote
Binary number: this is the most widely use method for interpreting bit setting as non-negatives integers. Ex: 2 which is equal.
While
Decimal number: these are numbers with point in between.
4c. What is an Abstract data type?
Ans:
This is an abstraction of a real life problem.
5a. Define a list
Ans:
A list is a dynamic data structure with a wide range of application. The number of nodes on a list may vary dramatically as element are inserted and removed.
5b. Differentiate between the following
(i)Linear linked listed and Circular linked listed
(ii)Circular linked list and Doubly linked
Ans:
Linear linked listed: the number of nodes on a list may vary dramatically as element are inserted and removed
While
Circular linked list: In circular limited list, the head returns back to the nodes
Circular linked listed: the diagram below shows circular linked list.
While
Doubly linked list can be seen diagrammatically
5c.Demonstrate the implementation of a priority queue
Ans:
The priority queue is a data structure in which the intrinsic ordering of the elements determines the result of its basic operations. There are two types of priority queues. An ascending priority queue and a descending priority queue.
6a. Define Queue?
Ans:
Queue: this is an ordered collection of item from which items may be deleted at one end called the front of the queue and to which items may be inserted at the other called the rear of the queue
6b. State possible operation on queue
Ans:
- Insertion
- Deletion
- The queue front
6c.Describe Queue as an Abstract data types
Ans:
Abstract typed of < eltype> queue (eltype);
Abstract empty (q)
Queue (eltype) q
Post condition empty = = ( len (q) = 0)
Abstract eltype remove (q)
Queue (eltype)
Precondition empty (q) = = false
Post condition remove = = first (q)
q = = sub (q’ 1, len (q’)
Abstract insert (q, el)
Queue (eltype) q
eltypeelt
post condition q = q + <elt
7a Define a tree?
Ans:
Tree: a tree is a finite non-empty set of elements in which one element is called the roots and the remaining element are portioned into m>=0 disjoint subset, each of which is itself a tree.
7b. Differentiate between Binary tree and Binary search
Ans:
Binary tree: in binary tree, each node has two children. This assertion makes many tree operations simple and efficient.
While
Binary search: in Binary search a binary tree where any left child node has a value less than its parent node and any right child node has a value greater than or equal to that of its parent node.
7c. using postorder, preorder and inorder draw the tree of the following
a) a e f g h I kb)1 4 8 5 6 3 9
Ans:
a) a e f g h I kb)1 4 8 5 6 3 9
Post order 9
k83
fl1456
aegh