1) Define First-fit method
First-fit method is a method for choosing the free block for use, and the free list is traversed sequentially to find the first free block whose size is larger than or equal to the amount requested.
2) Define Compaction
The process of moving all the used nodes which are marked to one end of memory and all the available memory to the other end is called compaction.
3)Define Garbage collection. What are the phases in it?
Method of detecting and reclaiming free nodes is called garbage collection.
- Two phases:
- i) Marking Phase : Marks the nodes that are accessible with external pointer.
- ii) Collection Phase: Free the nodes that have not been marked.
Tuesday, November 29, 2005
GRAPHS (UNIT IV)
1) Define Graph.
A Graph consists of sets of nodes and a set of arcs. Each arc in a graph is specified by a pair of nodes.
2) What is a digraph?
If the pair of nodes that make up the arcs are ordered pairs, then the graph is called as a digraph.
3) Define the term incident.
A node n is incident to an arc x, if one of the two nodes in the ordered pair of nodes that constitutes x.
4) What is degree of node in a graph?
The degree of a node is the number of arcs incident to it.
5) What is indegree and outdegree?
Indegree of a node n is the number of arcs that have n as the head and the outdegree of n is the number of arcs that have n as the tail.
6) Define the term adjacent
A node n is adjacent to a node m, if there is an arc from m to n.
7) What is a weighted graph?
A graph in which there is a number associated with each arc is called as weighted graph.
8) What is cycle, cyclic graph and acyclic graph?
A path from a node to itself is called a cycle. A graph that has a cycle is called cyclic graph. The graph that do not have cycle is called acyclic graph.
9) What is capacity function?
Capacity function c(a,b), is defined as Let a, b are nodes. Adjacent(a,b) is tue , c(a,b) is the capacity of the pipe from a to b. If there is no pipe C(a,b)=0;
10) What is flow function?
The flow function f(a,b) is 0 if b is not adjacent to a, and the amount of water flowing from the pipe a to b otherwise.
11) What is a forest?
A forest may be defined as an acyclic graph in which every node has one or no predecessors.
12) What is a tree?
A tree may be defined as a forest in which only a single node called the root exists, and has no predecessors.
13) What is an ordered forest?
Any forest that consists of collection of trees that are ordered is called ordered forest.
14) What is a spanning forest?
Given a graph G, F is a spanning forest of G if
i) F is a subgraph of G containing all nodes of G
ii) F is an ordered forest containing trees t1, t2… tn
iii) Ti contains all nodes that are reachable in G from the root of Ti and are not contained in Tj for some j must exist whenever an arcexists.
16) Define DFS and BFS.
DFS visits all nodes that are reachable from s. BFS visits all the successors of a visited node before visiting any successors of any of those successors.
17) What is a minimum spanning tree?
Minimum spanning tree is one in which the sum of the weights of the tree edges is as small as possible
A Graph consists of sets of nodes and a set of arcs. Each arc in a graph is specified by a pair of nodes.
2) What is a digraph?
If the pair of nodes that make up the arcs are ordered pairs, then the graph is called as a digraph.
3) Define the term incident.
A node n is incident to an arc x, if one of the two nodes in the ordered pair of nodes that constitutes x.
4) What is degree of node in a graph?
The degree of a node is the number of arcs incident to it.
5) What is indegree and outdegree?
Indegree of a node n is the number of arcs that have n as the head and the outdegree of n is the number of arcs that have n as the tail.
6) Define the term adjacent
A node n is adjacent to a node m, if there is an arc from m to n.
7) What is a weighted graph?
A graph in which there is a number associated with each arc is called as weighted graph.
8) What is cycle, cyclic graph and acyclic graph?
A path from a node to itself is called a cycle. A graph that has a cycle is called cyclic graph. The graph that do not have cycle is called acyclic graph.
9) What is capacity function?
Capacity function c(a,b), is defined as Let a, b are nodes. Adjacent(a,b) is tue , c(a,b) is the capacity of the pipe from a to b. If there is no pipe C(a,b)=0;
10) What is flow function?
The flow function f(a,b) is 0 if b is not adjacent to a, and the amount of water flowing from the pipe a to b otherwise.
11) What is a forest?
A forest may be defined as an acyclic graph in which every node has one or no predecessors.
12) What is a tree?
A tree may be defined as a forest in which only a single node called the root exists, and has no predecessors.
13) What is an ordered forest?
Any forest that consists of collection of trees that are ordered is called ordered forest.
14) What is a spanning forest?
Given a graph G, F is a spanning forest of G if
i) F is a subgraph of G containing all nodes of G
ii) F is an ordered forest containing trees t1, t2… tn
iii) Ti contains all nodes that are reachable in G from the root of Ti and are not contained in Tj for some j must exist whenever an arc
16) Define DFS and BFS.
DFS visits all nodes that are reachable from s. BFS visits all the successors of a visited node before visiting any successors of any of those successors.
17) What is a minimum spanning tree?
Minimum spanning tree is one in which the sum of the weights of the tree edges is as small as possible
Searching (UNIT III)
1) What are internal keys or embedded keys and external keys?
The key that is contained with in the record at a specific offset from the start of the record is called internal key or embedded key. The separate tables of keys that include pointers to the records are called external keys.
2) What is a primary key and secondary key?
The set of keys that is uniquely used to differentiate any two records is called primary key. The fields of a record which may not be unique is used for a particular search is called secondary key.
3) What is a search algorithm?
Search algorithm is an algorithm that accepts an argument a and tries to find a record whose key is a. It may return the entire record or a pointer to that record. If there is no match it return NULL record or NULL pointer.
4) What is search and insertion algorithm?
If the search is unsuccessful, a new record will be added to the table with the argument as key. This type of algorithm is called search algorithm.
5) What is search table or dictionary?
A table of records in which a key is used for retrieval is called search table or dictionary.
6) What are internal searches and external searches?
Searches in which the entire table is constantly in main memory are called internal searches; whereas that in which most of the table is kept in auxiliary storage is called external searches.
7) What is an ordered table?
The table in which there is a presumed relation exists among the records or their associated keys are called ordered table. The table that does not have any such specific relationship is called unordered table.
8) Write the simple procedure for sequential search.
For (i=0;i
The key that is contained with in the record at a specific offset from the start of the record is called internal key or embedded key. The separate tables of keys that include pointers to the records are called external keys.
2) What is a primary key and secondary key?
The set of keys that is uniquely used to differentiate any two records is called primary key. The fields of a record which may not be unique is used for a particular search is called secondary key.
3) What is a search algorithm?
Search algorithm is an algorithm that accepts an argument a and tries to find a record whose key is a. It may return the entire record or a pointer to that record. If there is no match it return NULL record or NULL pointer.
4) What is search and insertion algorithm?
If the search is unsuccessful, a new record will be added to the table with the argument as key. This type of algorithm is called search algorithm.
5) What is search table or dictionary?
A table of records in which a key is used for retrieval is called search table or dictionary.
6) What are internal searches and external searches?
Searches in which the entire table is constantly in main memory are called internal searches; whereas that in which most of the table is kept in auxiliary storage is called external searches.
7) What is an ordered table?
The table in which there is a presumed relation exists among the records or their associated keys are called ordered table. The table that does not have any such specific relationship is called unordered table.
8) Write the simple procedure for sequential search.
For (i=0;i
Saturday, November 19, 2005
Sorting (UNIT III)
Two Mark Questions….
1) What is sorting?
Sorting is arranging or ordering the data in some logical order either increasing or decreasing.
2) What are the fundamental types of sorting?
i) Internal Sorting
ii) External Sorting
3) What is internal sorting?
If the data to be sorted remains in main memory and also the sorting is carried out in main memory it is called internal sorting.
4) What is external sorting?
If the data resides in auxiliary memory and is brought into main memory in blocks for sorting and then result is returned back to auxiliary memory is called external sorting.
5) What is stable sorting?
Sorting technique is said to be stable, if for all records i and j such that k[I]=k[j], if r[i] precedes r[j] in original file, r[i] precedes r[j] in sorted file also.
6) What is sorting by address?
In sorting the auxiliary table pointers may be used so that the pointers are moved instead of actual data. This reduces the time needed for sorting.
7) What are the factors to be considered while selecting a sorting method?
Three factors are:
i) Length of time for the programmer to code the sorting program.
ii) Amount of machine time necessary for running the program.
iii) Amount of space necessary for the program to execute.
8) List the names of some internal sorting methods.
i) Bubble sort
ii) Insertion sort
iii) Selection sort
iv) Shell sort
v) Quick sort
vi) Heap sort
9) Write about any one external sorting method?
Merge sort is an example of external sorting. This sorts the sub arrays and the sorted sub arrays are stored in an auxiliary table. Then the sorted sub arrays are brought in to main memory for merging and sorting.
10) What is bubble sort?
Bubble sort arranges the array of integers as x[i]<=x[j], 0<=I
This was given the name as each element bubbles to the proper position.
11) What is quick sort or partition exchange sort?
Quick sort moves the data item into the correct direction, with the following rules:
i) Select a pivot element, from the array x.
ii) Initialize the down and up as the lower bound and upper bound of array.
iii) Increment down pointer, until x[down]>a
iv) Decrement up pointer, until x[up]<=a v) If up>down, interchange x[down] with x[up]
vi) If up<=down, interchange x[up] with pivot.
12) What is Pivot?
The element around which a file is partitioned is called a pivot.
13) What are the different methods for choosing a pivot?
i) The median of the first, last and middle elements of the sub file to be sorted can be chosen as pivot.
ii) The mean sort uses the mean of the sub file as pivot for sorting.
iii) Bsort uses the middle element of subfile as pivot.
14) What is selection sort?
Selection sort is one in which successive elements are sorted in order and placed into their proper sorted position.
15) What is straight selection sort or push down sort?
Straight selection sort is an in-place sort, from which the largest element should be chosen and interchanged with the element at end.
16) What is binary tree sort?
In binary tree sort, a binary tree of descending priority queue is created first and inorder traversing of the tree gives a sorted list.
17) What is Heap sort?
Heap sort is also an in-place sort, which creates a binary search tree in which elements are to be sorted and stored.
18) What is descending heap/Max heap/Descending partially ordered queue?
Descending heap of size n is an almost complete binary tree of nodes such that the content of each node is less than or equal to the content of its father.
19) What is Ascending heap/Min heap?
Min heap is an almost complete binary tree such that the content of each node is greater than or equal to the content of its father.
20) What is the inequality/ condition for sequential representation of heap?
Info[j]<=info[(j-1)/2] for 0<=((j-1)/2)
Other Questions…
1) What is sorting and explain the various sorting methods.
2) Discuss about the efficiency considerations while selecting a sorting algorithm
3) What are the types of Exchange sorts. Explain algorithms with examples.
4) Explain bubble sort with example.
5) Explain Quick sort with example and their efficiency considerations.
6) What are the various ways of choosing a pivot in quick sort?
7) What is selection sort and write the general selection sort algorithm.
8) What is straight selection sort/ Push down sort?
9) Explain Binary tree sorts.
10) Explain with example- How sorting is performed in a heap with descending heap?
11) Write about simple insertion sort.
12) What is shell sort / Diminishing increment sort? Explain with example.
13) What is address calculation sort / Sorting by hasing?
14) Explain the external sorting methods.
15) Briefly explain about any four internal sorting methods.
16) Explain merge sort with example.
17) Explain Cook-Kim algorithm and what are the advantages of it?
18) Explain Radix sort / Radix exchange sort with example.
Works for You…
1) What is a sort decision tree?
2) What is sort by counting?
3) What is distribution sort?
4) What is odd-even transposition sort?
5) What is quadratic selection sort?
6) What is a tournament?
7) What is a almost complete ternary tree?
8) What is a ternary heap?
9) What is two way insertion sort?
10) What is merge insertion sort?
11) Sort the following list of numbers with the sorting methods mentioned with all steps in clear.
96 23 65 8 28 15 67 32
i) Bubble sort
ii) Quick sort
iii) Selection sort
iv) Heap sort
v) Simple insertion sort
vi) Shell sort
vii) Address calculation sort
viii) Merge sort
ix) Radix sort
1) What is sorting?
Sorting is arranging or ordering the data in some logical order either increasing or decreasing.
2) What are the fundamental types of sorting?
i) Internal Sorting
ii) External Sorting
3) What is internal sorting?
If the data to be sorted remains in main memory and also the sorting is carried out in main memory it is called internal sorting.
4) What is external sorting?
If the data resides in auxiliary memory and is brought into main memory in blocks for sorting and then result is returned back to auxiliary memory is called external sorting.
5) What is stable sorting?
Sorting technique is said to be stable, if for all records i and j such that k[I]=k[j], if r[i] precedes r[j] in original file, r[i] precedes r[j] in sorted file also.
6) What is sorting by address?
In sorting the auxiliary table pointers may be used so that the pointers are moved instead of actual data. This reduces the time needed for sorting.
7) What are the factors to be considered while selecting a sorting method?
Three factors are:
i) Length of time for the programmer to code the sorting program.
ii) Amount of machine time necessary for running the program.
iii) Amount of space necessary for the program to execute.
8) List the names of some internal sorting methods.
i) Bubble sort
ii) Insertion sort
iii) Selection sort
iv) Shell sort
v) Quick sort
vi) Heap sort
9) Write about any one external sorting method?
Merge sort is an example of external sorting. This sorts the sub arrays and the sorted sub arrays are stored in an auxiliary table. Then the sorted sub arrays are brought in to main memory for merging and sorting.
10) What is bubble sort?
Bubble sort arranges the array of integers as x[i]<=x[j], 0<=I
This was given the name as each element bubbles to the proper position.
11) What is quick sort or partition exchange sort?
Quick sort moves the data item into the correct direction, with the following rules:
i) Select a pivot element, from the array x.
ii) Initialize the down and up as the lower bound and upper bound of array.
iii) Increment down pointer, until x[down]>a
iv) Decrement up pointer, until x[up]<=a v) If up>down, interchange x[down] with x[up]
vi) If up<=down, interchange x[up] with pivot.
12) What is Pivot?
The element around which a file is partitioned is called a pivot.
13) What are the different methods for choosing a pivot?
i) The median of the first, last and middle elements of the sub file to be sorted can be chosen as pivot.
ii) The mean sort uses the mean of the sub file as pivot for sorting.
iii) Bsort uses the middle element of subfile as pivot.
14) What is selection sort?
Selection sort is one in which successive elements are sorted in order and placed into their proper sorted position.
15) What is straight selection sort or push down sort?
Straight selection sort is an in-place sort, from which the largest element should be chosen and interchanged with the element at end.
16) What is binary tree sort?
In binary tree sort, a binary tree of descending priority queue is created first and inorder traversing of the tree gives a sorted list.
17) What is Heap sort?
Heap sort is also an in-place sort, which creates a binary search tree in which elements are to be sorted and stored.
18) What is descending heap/Max heap/Descending partially ordered queue?
Descending heap of size n is an almost complete binary tree of nodes such that the content of each node is less than or equal to the content of its father.
19) What is Ascending heap/Min heap?
Min heap is an almost complete binary tree such that the content of each node is greater than or equal to the content of its father.
20) What is the inequality/ condition for sequential representation of heap?
Info[j]<=info[(j-1)/2] for 0<=((j-1)/2)
Other Questions…
1) What is sorting and explain the various sorting methods.
2) Discuss about the efficiency considerations while selecting a sorting algorithm
3) What are the types of Exchange sorts. Explain algorithms with examples.
4) Explain bubble sort with example.
5) Explain Quick sort with example and their efficiency considerations.
6) What are the various ways of choosing a pivot in quick sort?
7) What is selection sort and write the general selection sort algorithm.
8) What is straight selection sort/ Push down sort?
9) Explain Binary tree sorts.
10) Explain with example- How sorting is performed in a heap with descending heap?
11) Write about simple insertion sort.
12) What is shell sort / Diminishing increment sort? Explain with example.
13) What is address calculation sort / Sorting by hasing?
14) Explain the external sorting methods.
15) Briefly explain about any four internal sorting methods.
16) Explain merge sort with example.
17) Explain Cook-Kim algorithm and what are the advantages of it?
18) Explain Radix sort / Radix exchange sort with example.
Works for You…
1) What is a sort decision tree?
2) What is sort by counting?
3) What is distribution sort?
4) What is odd-even transposition sort?
5) What is quadratic selection sort?
6) What is a tournament?
7) What is a almost complete ternary tree?
8) What is a ternary heap?
9) What is two way insertion sort?
10) What is merge insertion sort?
11) Sort the following list of numbers with the sorting methods mentioned with all steps in clear.
96 23 65 8 28 15 67 32
i) Bubble sort
ii) Quick sort
iii) Selection sort
iv) Heap sort
v) Simple insertion sort
vi) Shell sort
vii) Address calculation sort
viii) Merge sort
ix) Radix sort
Monday, November 14, 2005
TREES... (UNIT II)
Two Mark Questions…
1) Define Binary Tree
Binary tree is a finite set of elements that is either empty or is partitioned into three disjoint subsets- The root, left subtree and right subtree.
2) What is a father node, and left and right sons?
If A is the root of a binary tree and B is the root of its left or right subtree, then A is said to be the father of B and B is said to be the left or right son of A.
3) What is a leaf node?
The node that do not have any sons is called leaf node.
4) Define the term ancestor.
Node n1 is said to be the ancestor of node n2, if n1 is either the father of n2 or father of some ancestor of n2.
5) Define the term descendent.
Node n2 is said to be the descendant of node n1, if n2 is either the left or right son of node n1 or son of some descendant of n1.
6) Define the term left descendant
A node n2 is the left descendant of node n1, if n2 is either the left son of n1 or a descendant of the left son of n1.
7) Define the term right descendant.
A node n2 is the right descendant of node n1, if n2 is either the right son of n1 or a descendant of the right son of n1.
8) Define the term brothers.
Two nodes are brothers if they are the left and right sons of the same father.
9) What is a strictly binary tree?
The binary tree in which every nonleaf node has nonempty left and right subtrees, is called a strictly binary tree. (Include a diagrammatic example)
10) Define level of a binary tree.
The level of a binary tree is defined as, The root of the tree has level 0, and the level of any other node in the tree is one more than the level of its father.
11) Define Depth.
The depth of a binary tree is the maximum level of any leaf in the tree. This is same as the length of the longest path from the root to any leaf.
12) What is a complete binary tree.
A complete binary tree of depth d is the strictly binary tree all of whose leaves are at level d.
13) What si a almost complete binary tree?
A binary tree of depth d is an almost complete binary tree if:
i) Each leaf in the tree is either at level d or level d-1.
ii) For any node nd in the tree with the right descendant at level d, all the left descendants that are leaves should also be at level d.
14) How almost complete binary tree nodes can be numbered?
The nodes in almost complete binary tree are numbered so that, the root is assigned the number 1, and the left son is assigned a number twice that of its father, and the right son is one more than twice the number assigned to its father. (give example diagram)
15) What are the basic operations on a binary tree?
Let p be a pointer to a node and x be the information. Now, the basic operations are:
i) info(p)
ii) father(p)
iii) left(p)
iv) right(p)
v) brother(p)
vi) isleft(p)
vii) isright(p)
viii) maketree(x)
ix) setleft(p,x)
x) setright(p,x)
16) What is traversal. What are the types of traversal?
Traversal means visiting of nodes. There are three types of traversal
i) Preorder (depth-first order)
ii) Postorder
iii) Inorder (symmetric order)
17) Explain the steps for Depth-first order traversal.
Visit the root
Traverse the left subtree
Traverse the right subtree.
18) Explain the steps for Symmetric order traversal.
Traverse the left subtree
Visit the root
Traverse the right subtree.
19) Explain the steps for postorder traversal.
Traverse the left subtree
Traverse the right subtree.
Visit the root
20) What is a binary search tree.
A binary tree in which all the elements in the left subtree of a node n are less than the contents of n, and all the elements in the right subtree of n are greater than or equal to the contents of n is called a binary search tree.
21) What are internal nodes and external nodes?
The non leaf nodes are called internal nodes where as leaf nodes are called external nodes.
22) What are the methods to indicate the non existent nodes in a binary tree, when a sequential representation is made?
One way is to use negative numbers as null indicators in a positive binary tree.
Another way is to use a used field to indicate whether the node is in use or not.
23) How can you say recursive procedure is efficient than non recursive?
There is no extra recursion
The automatic stacking and unstacking make it more efficient
There is no extraneous parameters ans local variables used.
24) What is a thread?
Thread is a pointer from the right field of leaf node to its inorder successor.
25) What is a right-in-threaded binary tree?
The right field of each leaf node other than the right most leaf node, if it has pointer to the next inorder successor, we call it as a right in-threaded binary tree.
26) What is a left in-threaded binary tree?
A left in-threaded binary tree is one in which each NULL left pointer is altered to contain a thread to that node’s inorder predecessor.
27) Define left and right pre-threaded binary tress.
Left and right prethreaded binary trees can be defined as the binary trees in which th null pointers of the nodes are replaced by their preorder succcessors and predecessors.
28) What are Heterogeneous binary trees?
Heterogeneous binary trees are the binary trees whose nodes may contain different data types. (eg: Binary tree representation of expressions- Draw a diagram)
29) What are \Huffman trees?
Huffman trees are the trees which are generated with the frequency of each alphabet for encoding a message in bit string format.
30) What is a tree?
A tree is a finite nonempty set of elements in which one element is called the root and the remaining elements are partitioned into m>=0 disjoint subsets, each of which is itself a tree. Each element in a tree is called node.
31) What is a ordered tree?
A ordered tree is defined as a tree in which the subtrees of each node form an ordered set.The first son of the ordered tree is the oldest son of that node, and the last son as youngest.
32) Define the term forest.
Forest is an ordered set of ordered trees.
Other questions:
1) Write the algorithm for creating a binary search tree, which eliminate duplicates.
2) What is the advantage of linear array representation of binary tree over dynamic node representation?
3) What is the advantage of dynamic node representation of binary tree over linear array representation ?
4) Write the procedure for maketree(x).
5) Write the procedure for setleft(p,x).
6) Write the procedure for setright(p,x).
7) What are the disadvantage of using the same representation for leaf nodes and non leaf nodes? How could they be rectified?
8) Write the procedure for sequential representation of a binary tree.
9) Write the recursive procedure for inorder, postorder and preorder traversals of binary tree.
10) Write the non recursive procedure for inorder traversal in a binary tree.
11) Write the procedure for traversing the right in-threaded binary tree.
12) Explain Huffman algorithm in Detail (16)
13) Write the procedure for finding the Kth element in a Binary tree representation of List.
14) Write the procedure for deleting an element in a Binary tree representation of List.
15) What are the application of trees?
Works for you….
1) If there are m nodes in a binary tree at level l, then there can be atmost 2m nodes at level l+1. Is this statement true or false. State the reason.
2) Derive the equation to find the total number of nodes in a complete binary tree.
3) If the total number of nodes in a complete binary tree is 15, what is the depth of the binary tree?
4) If the depth of a complete binary tree is 9, what is the totall number of nodes in it?
5) Only one almost complete binary tree can be drawn with n nodes. Is this statement true or false. If false, give two alternate representations for an almost complete binary tree with 10 nodes.
6) Create a binary search tree for the following list of numbers.
13, 12, 56, 8, 4 ,78, 7, 2, 9, 34, 22
7) Create a binary search tree for the following list of numbers and write the inorder, postorder and preorder traversal results.
15,9,18,5,4,17,14,6,7,21,33
8) Represent the expression (A+B*C)$((A+B)*C) using binary tree and write the inorder, postorder and preorder traversal results.
1) Define Binary Tree
Binary tree is a finite set of elements that is either empty or is partitioned into three disjoint subsets- The root, left subtree and right subtree.
2) What is a father node, and left and right sons?
If A is the root of a binary tree and B is the root of its left or right subtree, then A is said to be the father of B and B is said to be the left or right son of A.
3) What is a leaf node?
The node that do not have any sons is called leaf node.
4) Define the term ancestor.
Node n1 is said to be the ancestor of node n2, if n1 is either the father of n2 or father of some ancestor of n2.
5) Define the term descendent.
Node n2 is said to be the descendant of node n1, if n2 is either the left or right son of node n1 or son of some descendant of n1.
6) Define the term left descendant
A node n2 is the left descendant of node n1, if n2 is either the left son of n1 or a descendant of the left son of n1.
7) Define the term right descendant.
A node n2 is the right descendant of node n1, if n2 is either the right son of n1 or a descendant of the right son of n1.
8) Define the term brothers.
Two nodes are brothers if they are the left and right sons of the same father.
9) What is a strictly binary tree?
The binary tree in which every nonleaf node has nonempty left and right subtrees, is called a strictly binary tree. (Include a diagrammatic example)
10) Define level of a binary tree.
The level of a binary tree is defined as, The root of the tree has level 0, and the level of any other node in the tree is one more than the level of its father.
11) Define Depth.
The depth of a binary tree is the maximum level of any leaf in the tree. This is same as the length of the longest path from the root to any leaf.
12) What is a complete binary tree.
A complete binary tree of depth d is the strictly binary tree all of whose leaves are at level d.
13) What si a almost complete binary tree?
A binary tree of depth d is an almost complete binary tree if:
i) Each leaf in the tree is either at level d or level d-1.
ii) For any node nd in the tree with the right descendant at level d, all the left descendants that are leaves should also be at level d.
14) How almost complete binary tree nodes can be numbered?
The nodes in almost complete binary tree are numbered so that, the root is assigned the number 1, and the left son is assigned a number twice that of its father, and the right son is one more than twice the number assigned to its father. (give example diagram)
15) What are the basic operations on a binary tree?
Let p be a pointer to a node and x be the information. Now, the basic operations are:
i) info(p)
ii) father(p)
iii) left(p)
iv) right(p)
v) brother(p)
vi) isleft(p)
vii) isright(p)
viii) maketree(x)
ix) setleft(p,x)
x) setright(p,x)
16) What is traversal. What are the types of traversal?
Traversal means visiting of nodes. There are three types of traversal
i) Preorder (depth-first order)
ii) Postorder
iii) Inorder (symmetric order)
17) Explain the steps for Depth-first order traversal.
Visit the root
Traverse the left subtree
Traverse the right subtree.
18) Explain the steps for Symmetric order traversal.
Traverse the left subtree
Visit the root
Traverse the right subtree.
19) Explain the steps for postorder traversal.
Traverse the left subtree
Traverse the right subtree.
Visit the root
20) What is a binary search tree.
A binary tree in which all the elements in the left subtree of a node n are less than the contents of n, and all the elements in the right subtree of n are greater than or equal to the contents of n is called a binary search tree.
21) What are internal nodes and external nodes?
The non leaf nodes are called internal nodes where as leaf nodes are called external nodes.
22) What are the methods to indicate the non existent nodes in a binary tree, when a sequential representation is made?
One way is to use negative numbers as null indicators in a positive binary tree.
Another way is to use a used field to indicate whether the node is in use or not.
23) How can you say recursive procedure is efficient than non recursive?
There is no extra recursion
The automatic stacking and unstacking make it more efficient
There is no extraneous parameters ans local variables used.
24) What is a thread?
Thread is a pointer from the right field of leaf node to its inorder successor.
25) What is a right-in-threaded binary tree?
The right field of each leaf node other than the right most leaf node, if it has pointer to the next inorder successor, we call it as a right in-threaded binary tree.
26) What is a left in-threaded binary tree?
A left in-threaded binary tree is one in which each NULL left pointer is altered to contain a thread to that node’s inorder predecessor.
27) Define left and right pre-threaded binary tress.
Left and right prethreaded binary trees can be defined as the binary trees in which th null pointers of the nodes are replaced by their preorder succcessors and predecessors.
28) What are Heterogeneous binary trees?
Heterogeneous binary trees are the binary trees whose nodes may contain different data types. (eg: Binary tree representation of expressions- Draw a diagram)
29) What are \Huffman trees?
Huffman trees are the trees which are generated with the frequency of each alphabet for encoding a message in bit string format.
30) What is a tree?
A tree is a finite nonempty set of elements in which one element is called the root and the remaining elements are partitioned into m>=0 disjoint subsets, each of which is itself a tree. Each element in a tree is called node.
31) What is a ordered tree?
A ordered tree is defined as a tree in which the subtrees of each node form an ordered set.The first son of the ordered tree is the oldest son of that node, and the last son as youngest.
32) Define the term forest.
Forest is an ordered set of ordered trees.
Other questions:
1) Write the algorithm for creating a binary search tree, which eliminate duplicates.
2) What is the advantage of linear array representation of binary tree over dynamic node representation?
3) What is the advantage of dynamic node representation of binary tree over linear array representation ?
4) Write the procedure for maketree(x).
5) Write the procedure for setleft(p,x).
6) Write the procedure for setright(p,x).
7) What are the disadvantage of using the same representation for leaf nodes and non leaf nodes? How could they be rectified?
8) Write the procedure for sequential representation of a binary tree.
9) Write the recursive procedure for inorder, postorder and preorder traversals of binary tree.
10) Write the non recursive procedure for inorder traversal in a binary tree.
11) Write the procedure for traversing the right in-threaded binary tree.
12) Explain Huffman algorithm in Detail (16)
13) Write the procedure for finding the Kth element in a Binary tree representation of List.
14) Write the procedure for deleting an element in a Binary tree representation of List.
15) What are the application of trees?
Works for you….
1) If there are m nodes in a binary tree at level l, then there can be atmost 2m nodes at level l+1. Is this statement true or false. State the reason.
2) Derive the equation to find the total number of nodes in a complete binary tree.
3) If the total number of nodes in a complete binary tree is 15, what is the depth of the binary tree?
4) If the depth of a complete binary tree is 9, what is the totall number of nodes in it?
5) Only one almost complete binary tree can be drawn with n nodes. Is this statement true or false. If false, give two alternate representations for an almost complete binary tree with 10 nodes.
6) Create a binary search tree for the following list of numbers.
13, 12, 56, 8, 4 ,78, 7, 2, 9, 34, 22
7) Create a binary search tree for the following list of numbers and write the inorder, postorder and preorder traversal results.
15,9,18,5,4,17,14,6,7,21,33
8) Represent the expression (A+B*C)$((A+B)*C) using binary tree and write the inorder, postorder and preorder traversal results.
Friday, October 21, 2005
Linked List
TWO MARK QUESTIONS...
1) What is a linear linked list?
If each item of a list itself has the pointer to the next item, which gives an explicit ordering of elements is known as linear linked list. Each item contain the information field which contain the actual information and the next address field which is used to access the next item.
2) What is empty list or Null list?
The list having no items is called empty list or null list. The external pointer to empty list is null pointer. The empty list is initialized as list=null
3) Write the procedure for inserting an element in the list.
p=getnode( );
info(p)=x;
next(p)=list;
list=p;
4) Write the procedure for deleting an element from the list.
p=list;
list=next(p);
x=info(p);
freenode(p);
5) What are the disadvantages of representing a stack or queue by linked list?
A node in linked list occupies more storage than corresponding element as it needs an explicit pointer for next item.
Additional time is spent in managing the available list. When an node is deleted, modifications are needed to either the previous or next node or both.
6) What are the advantages of using a linked list rather than array?
While inserting or deleting element from the middle of an array, all the elements should be moved to avoid the empty locations. But, linked list does not need to move all elements, but only the node pointers of two nodes will have to be modified.
7) What is a header node?
The extra node kept in front of the list is called header node. It does not represent any item in the list. It could have the global information about the list.
8) What are the limitations of array implementation of linked list?
The number of nodes needed for execution of a program can not be predicted when the program is written.
The nodes declared at beginning should remain allocated to that program till the execution is complete.
9) What is a circular linked list?
Circular linked list is the list in which the end node of the list point to the header node.
10) What is dangling pointer?
If the link pointing the node is freed by free(pointer), the node will not be used further. But, it contain some illegal information. The value of p is a valid address and the pointer that points to it can be given a *P. This P is called dangling pointer.
OTHER QUESTIONS…
1) Write a program to implement stack using linked list. (16)
2) Write a program to implement queue using linked list (16)
3) Write the procedure to delete all occurrences of number 4 from the linked list.(8)
4) Write the procedure to insert an element in the ordered list. (4)
5) Explain the list implementation of priority queue. (6)
6) Explain about header nodes, and what are the uses of it? (6)
7) Explain how linked list could be represented in an array (10)
8) Write about how the dynamic allocation and freeing of nodes takes place with example. (8)
9) How will you implement a linked list with dynamic memory allocation? (16)
10) Compare the dynamic and array implementation of lists. (6)
WORKS FOR YOU…
1) Explain with necessary diagrams to represent how nodes could be added and deleted in a linked list, in the front, last and middle. (16)
2) Unordered lists are best suited for priority queue implementation. Is this statement true or false? State reasons for your answer. (6)
3) What is the average number of nodes accessed in searching for a particular element in an unordered list? In an ordered list? In an unordered array? In an ordered array?
1) What is a linear linked list?
If each item of a list itself has the pointer to the next item, which gives an explicit ordering of elements is known as linear linked list. Each item contain the information field which contain the actual information and the next address field which is used to access the next item.
2) What is empty list or Null list?
The list having no items is called empty list or null list. The external pointer to empty list is null pointer. The empty list is initialized as list=null
3) Write the procedure for inserting an element in the list.
p=getnode( );
info(p)=x;
next(p)=list;
list=p;
4) Write the procedure for deleting an element from the list.
p=list;
list=next(p);
x=info(p);
freenode(p);
5) What are the disadvantages of representing a stack or queue by linked list?
A node in linked list occupies more storage than corresponding element as it needs an explicit pointer for next item.
Additional time is spent in managing the available list. When an node is deleted, modifications are needed to either the previous or next node or both.
6) What are the advantages of using a linked list rather than array?
While inserting or deleting element from the middle of an array, all the elements should be moved to avoid the empty locations. But, linked list does not need to move all elements, but only the node pointers of two nodes will have to be modified.
7) What is a header node?
The extra node kept in front of the list is called header node. It does not represent any item in the list. It could have the global information about the list.
8) What are the limitations of array implementation of linked list?
The number of nodes needed for execution of a program can not be predicted when the program is written.
The nodes declared at beginning should remain allocated to that program till the execution is complete.
9) What is a circular linked list?
Circular linked list is the list in which the end node of the list point to the header node.
10) What is dangling pointer?
If the link pointing the node is freed by free(pointer), the node will not be used further. But, it contain some illegal information. The value of p is a valid address and the pointer that points to it can be given a *P. This P is called dangling pointer.
OTHER QUESTIONS…
1) Write a program to implement stack using linked list. (16)
2) Write a program to implement queue using linked list (16)
3) Write the procedure to delete all occurrences of number 4 from the linked list.(8)
4) Write the procedure to insert an element in the ordered list. (4)
5) Explain the list implementation of priority queue. (6)
6) Explain about header nodes, and what are the uses of it? (6)
7) Explain how linked list could be represented in an array (10)
8) Write about how the dynamic allocation and freeing of nodes takes place with example. (8)
9) How will you implement a linked list with dynamic memory allocation? (16)
10) Compare the dynamic and array implementation of lists. (6)
WORKS FOR YOU…
1) Explain with necessary diagrams to represent how nodes could be added and deleted in a linked list, in the front, last and middle. (16)
2) Unordered lists are best suited for priority queue implementation. Is this statement true or false? State reasons for your answer. (6)
3) What is the average number of nodes accessed in searching for a particular element in an unordered list? In an ordered list? In an unordered array? In an ordered array?
Thursday, October 06, 2005
Queue
Two mark Questions:
1) Define Queue.
A queue is an ordered collection of items from which items may be inserted at one end called rear end and into which items may be deleted at the other end called the front end.
2) Why queue is called FIFO list?
In a queue, the first element inserted at rear end will be the first element to be deleted at front end. So, queue is called First-in First-out list.
3) What are the difference between Stack and Queue?
Stack: The basic operations like Push and Pop can be done at only one end called top of stack.
Queue: The insertion can be done at rear end and deletion at front end.
Stack: The last element inserted will be the first to be deleted. Hence stack is LIFO list.
Queue: The First element inserted will be the first to be deleted. Hence, Queue is FIFO list.
4) What are the basic operations that could be performed on a Queue?
i) Insertion – insert(q,x) inserts x at the rear end.
ii) Removal – x=remove(q) remove the element in front end.
iii) Empty(q) – Checks whether queue has any elements or not.
5) What are the limitations of linear queue? How they can be rectified?
When an element is removed from linear queue, the location remains unused. Even if the queue is empty, new elements cannot be inserted. To avoid this, consider queue as a circle, having the first element immediately following the last element.
6) Define Priority Queue.
Priority queue is a data structure in which the intrinsic ordering of the elements determine the results of the basic operations like insertion and removal.
7) What are the two types of priority queues? Briefly explain.
Two types of priority queues are,
i) Ascending priority queue – In this queue, the items can be inserted arbitrarily and only the smallest item will be removed.
ii) Descending priority queue- This allows insertion of items arbitrarily, and only the maximum element from queue will be removed first.
8) What is the difference between queue and priority queue?
In queue the elements can be inserted only at rear end and can be removed only at front end. But in priority queue, elements can be arbitrarily inserted. But the complete queue is searched for removal of high priority element.
9) What are the limitations in priority queue? How it could be rectified?
Deletion of elements make a location empty. The search of items include the empty spaces too. This takes more time. To avoid this, use an empty indicator or shift elements forward when each element is deleted. We can also maintain priority queue as an array of ordered elements, to avoid risk in searching.
Other questions:
1) Define queue and explain the basic operations in Queue with algorithm(8)
2) Write a C program to create queue and to implement its basic operations using array(16)
3) Explain about priority queue (8)
Works for you….
1) Write a C program to implement the basic operations on Circular queue.
2) Define Deque. Write the algorithm for input restricted deque and output restricted deque.
1) Define Queue.
A queue is an ordered collection of items from which items may be inserted at one end called rear end and into which items may be deleted at the other end called the front end.
2) Why queue is called FIFO list?
In a queue, the first element inserted at rear end will be the first element to be deleted at front end. So, queue is called First-in First-out list.
3) What are the difference between Stack and Queue?
Stack: The basic operations like Push and Pop can be done at only one end called top of stack.
Queue: The insertion can be done at rear end and deletion at front end.
Stack: The last element inserted will be the first to be deleted. Hence stack is LIFO list.
Queue: The First element inserted will be the first to be deleted. Hence, Queue is FIFO list.
4) What are the basic operations that could be performed on a Queue?
i) Insertion – insert(q,x) inserts x at the rear end.
ii) Removal – x=remove(q) remove the element in front end.
iii) Empty(q) – Checks whether queue has any elements or not.
5) What are the limitations of linear queue? How they can be rectified?
When an element is removed from linear queue, the location remains unused. Even if the queue is empty, new elements cannot be inserted. To avoid this, consider queue as a circle, having the first element immediately following the last element.
6) Define Priority Queue.
Priority queue is a data structure in which the intrinsic ordering of the elements determine the results of the basic operations like insertion and removal.
7) What are the two types of priority queues? Briefly explain.
Two types of priority queues are,
i) Ascending priority queue – In this queue, the items can be inserted arbitrarily and only the smallest item will be removed.
ii) Descending priority queue- This allows insertion of items arbitrarily, and only the maximum element from queue will be removed first.
8) What is the difference between queue and priority queue?
In queue the elements can be inserted only at rear end and can be removed only at front end. But in priority queue, elements can be arbitrarily inserted. But the complete queue is searched for removal of high priority element.
9) What are the limitations in priority queue? How it could be rectified?
Deletion of elements make a location empty. The search of items include the empty spaces too. This takes more time. To avoid this, use an empty indicator or shift elements forward when each element is deleted. We can also maintain priority queue as an array of ordered elements, to avoid risk in searching.
Other questions:
1) Define queue and explain the basic operations in Queue with algorithm(8)
2) Write a C program to create queue and to implement its basic operations using array(16)
3) Explain about priority queue (8)
Works for you….
1) Write a C program to implement the basic operations on Circular queue.
2) Define Deque. Write the algorithm for input restricted deque and output restricted deque.
Saturday, October 01, 2005
Stack
Two mark Questions...
1. Define stack.
Stack is an ordered collection of items into which new items may be inserted and from which items may be deleted at one end, called the top of stack.
2. What is top of stack?
The end of stack, at which the items are added or deleted is called top of stack.
3. Why stack is called LIFO list?
The last element inserted into the stack is the first element to be deleted.For this reason, stack is called Last-In First-Out list.
4.What are the operations that can be performed on a stack?
i) Push- Adding an item to a stack. Push(S,i) adds an item i to the top of stack.
ii) Pop - Removes an item from stack. i=Pop(S) returns the top element to i.
5. What is empty stack?
The stack which contains no items in it is called Empty stack.
6. What causes underflow of stack? How it could be avoided?
If an illegal attempt is made to pop or access an item from empty stack, it causes stack underflow.
To avoid underflow, before any pop(S) or stacktop(S), check whether empty(S) is true or false.
7. What is nesting depth and parenthesis counts in an expression?
Nesting depth is the number of scope that have been opened, but not yet closed at that point.
Parenthesis count is the number of left parenthesis minus number of right parenthesis encountered at a particular point when the expression is scanned from left end.
8. What are the two conditions for admissible pattern of expression?
i. The Parenthesis count at the end of the expression is 0.
ii. The parenthesis count at each point in the expression is nonnegative
9. How an expression is validated if the delimiters are different?
The delimiters in an expression can be (,), [,] and {,}. But the scope ender must be same as scope opener. The number of scopes and type of scopes should be kept on account
Push scope opener to stack. When scope ender is encountered, check if the opener is matching. Otherwise, expression is invalid. At the end of expression, stack must be empty. Otherwise, expression is invalid
10. What are the limitations in the stack, When array used as home of stack?
The Array is finite collection of elements and in stack the number of elements is unlimited. As the stack dynamically changes the attempt to insert more elements than the array size cause overflow
11. Define Modularization?
Modularization is the concept of isolating the complex implementation into set of independent and easily identifiable units, to make the program easily understandable and modifiable.
12. What are the error conditions that could occur in stack implementation? How could they be rectified?
i) Overflow
ii) Underflow
To avoid overflow, the stack should be checked whether it is full or not before every push operation.
To avoid underflow, the stack should be checked for emptiness before every pop operation.
13. What is overflow in stack?
When array is used as home of stack, and when the stack contains as many elements as array, and as attempt is to push another element on stack, it cause overflow.
14. Why infix expression should be converted to Prefix / Postfix?
In Infix, operator precedence can be set only after scanning the expression for several times. But, conversion of Infix to Postfix or Prefix with use of stack, help to set precedence based on order of arrangement in a single scanning
15. Convert ((A+B) * C – (D – E)) $ (F + G) To Postfix and Prefix notation.
Prefix : $ - * + ABC – DE + FG.
Postfix : AB + C * DE -- FG + $
Other Questions:
1. Write the algorithm to check the validity of expression. (6)
2. Write the ADT For Stack (6)
3. Write a Program to implement the stack operations like push, pop and peep using arrays (16)
4. Convert 4$2*3-3+8/4/(1+1) to postfix using stack (10)
5. Write the algorithm to evaluate postfix expression (8)
6. Evaluate the following postfix expression using stack 653*+1-93/+
7. Write a program in C, to evaluate postfix expression (16)
8. Write the algorithm to convert Infix expression to postfix (8)
9. Write C program to convert Infix to Postfix (16)
Works For You........
1. Stack is static object. Is this statement true or False ? Comment the reason for your answer.
2. Write Parenthesis count at each point of the following expressions and check whether it is valid or not?
i) A+ ((( B-C) * (D-E) + F) / G)
ii) (a-b (C+D)) * (a - b)
iii) A- (B-C)(C-D) (D+(E*F)
3. Show contents of stack, at each point of the expression
i) (A+B})
ii) (A+B) -{C+D}-[F+G]
iii) {[A+B]}-[(C+D)]
iv) ((H) * {([J+K])})
v) ((( A ))))
4. Convert the following Infix expression to Postfix and Prefix
i) A+B* C+D/E + F/G
ii) ((X+Y) * (W+Z)) / (A*B) + (C/D)
iii) A+B+C+D+E
5. Evaluate the following Postfix expressions
i) AB + C - BA+ C$-
ii) ABC+* CBA-+*
(Assume A=1, B=2, C=3)
1. Define stack.
Stack is an ordered collection of items into which new items may be inserted and from which items may be deleted at one end, called the top of stack.
2. What is top of stack?
The end of stack, at which the items are added or deleted is called top of stack.
3. Why stack is called LIFO list?
The last element inserted into the stack is the first element to be deleted.For this reason, stack is called Last-In First-Out list.
4.What are the operations that can be performed on a stack?
i) Push- Adding an item to a stack. Push(S,i) adds an item i to the top of stack.
ii) Pop - Removes an item from stack. i=Pop(S) returns the top element to i.
5. What is empty stack?
The stack which contains no items in it is called Empty stack.
6. What causes underflow of stack? How it could be avoided?
If an illegal attempt is made to pop or access an item from empty stack, it causes stack underflow.
To avoid underflow, before any pop(S) or stacktop(S), check whether empty(S) is true or false.
7. What is nesting depth and parenthesis counts in an expression?
Nesting depth is the number of scope that have been opened, but not yet closed at that point.
Parenthesis count is the number of left parenthesis minus number of right parenthesis encountered at a particular point when the expression is scanned from left end.
8. What are the two conditions for admissible pattern of expression?
i. The Parenthesis count at the end of the expression is 0.
ii. The parenthesis count at each point in the expression is nonnegative
9. How an expression is validated if the delimiters are different?
The delimiters in an expression can be (,), [,] and {,}. But the scope ender must be same as scope opener. The number of scopes and type of scopes should be kept on account
Push scope opener to stack. When scope ender is encountered, check if the opener is matching. Otherwise, expression is invalid. At the end of expression, stack must be empty. Otherwise, expression is invalid
10. What are the limitations in the stack, When array used as home of stack?
The Array is finite collection of elements and in stack the number of elements is unlimited. As the stack dynamically changes the attempt to insert more elements than the array size cause overflow
11. Define Modularization?
Modularization is the concept of isolating the complex implementation into set of independent and easily identifiable units, to make the program easily understandable and modifiable.
12. What are the error conditions that could occur in stack implementation? How could they be rectified?
i) Overflow
ii) Underflow
To avoid overflow, the stack should be checked whether it is full or not before every push operation.
To avoid underflow, the stack should be checked for emptiness before every pop operation.
13. What is overflow in stack?
When array is used as home of stack, and when the stack contains as many elements as array, and as attempt is to push another element on stack, it cause overflow.
14. Why infix expression should be converted to Prefix / Postfix?
In Infix, operator precedence can be set only after scanning the expression for several times. But, conversion of Infix to Postfix or Prefix with use of stack, help to set precedence based on order of arrangement in a single scanning
15. Convert ((A+B) * C – (D – E)) $ (F + G) To Postfix and Prefix notation.
Prefix : $ - * + ABC – DE + FG.
Postfix : AB + C * DE -- FG + $
Other Questions:
1. Write the algorithm to check the validity of expression. (6)
2. Write the ADT For Stack (6)
3. Write a Program to implement the stack operations like push, pop and peep using arrays (16)
4. Convert 4$2*3-3+8/4/(1+1) to postfix using stack (10)
5. Write the algorithm to evaluate postfix expression (8)
6. Evaluate the following postfix expression using stack 653*+1-93/+
7. Write a program in C, to evaluate postfix expression (16)
8. Write the algorithm to convert Infix expression to postfix (8)
9. Write C program to convert Infix to Postfix (16)
Works For You........
1. Stack is static object. Is this statement true or False ? Comment the reason for your answer.
2. Write Parenthesis count at each point of the following expressions and check whether it is valid or not?
i) A+ ((( B-C) * (D-E) + F) / G)
ii) (a-b (C+D)) * (a - b)
iii) A- (B-C)(C-D) (D+(E*F)
3. Show contents of stack, at each point of the expression
i) (A+B})
ii) (A+B) -{C+D}-[F+G]
iii) {[A+B]}-[(C+D)]
iv) ((H) * {([J+K])})
v) ((( A ))))
4. Convert the following Infix expression to Postfix and Prefix
i) A+B* C+D/E + F/G
ii) ((X+Y) * (W+Z)) / (A*B) + (C/D)
iii) A+B+C+D+E
5. Evaluate the following Postfix expressions
i) AB + C - BA+ C$-
ii) ABC+* CBA-+*
(Assume A=1, B=2, C=3)
Tuesday, September 27, 2005
Structures & Unions
Two Mark Questions
1. Define structure.
Structure is a group of items, in which each is identified by its own identifier. Each item is the member of the structure
2. Explain about memory allocated for structure
The amount of memory, specified by the structure is sum of the storage of each element
3. Define Union
Union is a group of items, which permits variable to be interpreted in several different ways
4. Explain about memory allocated for Union
Compiler allocate sufficient storage to contain the largest member of the union. Only a single member of a union can exits at a single instant. All members of union use the same space, and it can be used by only member at a time.
5. How Structure can be passed to a function?
The structure can be passed to a function, only by passing the address of the structure by means of pointer. P ® X is used to refer to the member X of structure P
6. What are the difference between structure & Union?
Structure: Every member has its own memory space
Union: All members use the same memory space
1) Structure: Can handle all members as required at a time
Union : Can handle only one member at a time
2) Structure: All members can be initialized
Union : Only first member may be initialized
3)Structure: Difference Interpretations for the same memory location is not possible
Union : Different Interpretations for the same memory location are possible
4) Structure: More storage space required
Union : Conservation of memory is possible
Other Questions:
Define Structure. Give example (4)
Explain about Structure with in Structure, how the members can be accessed and give example (6)
Explain array of Structures, how a group of elements in array can be accessed and give example (6)
What are the difference between Structure and Union (5)
Works For You……….
Implements rational number using Structures with numerator and denominator, Write routines to ass, multiply, subtract numbers
Implement complex numbers using structures with real and complex parts. Write routines to add, multiply and negate numbers
Assume integer needs 4 bytes, Float needs 8 bytes, char needs 1 byte.
Struct nametype
{
Char Fname [10];
Char minit;
Char lname [15];
};
Struct person
{
struct nametype name;
int age;
float avgmark;
};
Struct person p[100];
If starting address of P is 100, what are the starting address of
i) P [20];
ii) P [5]. name . minit
iii) P [21]. avgmark
1. Define structure.
Structure is a group of items, in which each is identified by its own identifier. Each item is the member of the structure
2. Explain about memory allocated for structure
The amount of memory, specified by the structure is sum of the storage of each element
3. Define Union
Union is a group of items, which permits variable to be interpreted in several different ways
4. Explain about memory allocated for Union
Compiler allocate sufficient storage to contain the largest member of the union. Only a single member of a union can exits at a single instant. All members of union use the same space, and it can be used by only member at a time.
5. How Structure can be passed to a function?
The structure can be passed to a function, only by passing the address of the structure by means of pointer. P ® X is used to refer to the member X of structure P
6. What are the difference between structure & Union?
Structure: Every member has its own memory space
Union: All members use the same memory space
1) Structure: Can handle all members as required at a time
Union : Can handle only one member at a time
2) Structure: All members can be initialized
Union : Only first member may be initialized
3)Structure: Difference Interpretations for the same memory location is not possible
Union : Different Interpretations for the same memory location are possible
4) Structure: More storage space required
Union : Conservation of memory is possible
Other Questions:
Define Structure. Give example (4)
Explain about Structure with in Structure, how the members can be accessed and give example (6)
Explain array of Structures, how a group of elements in array can be accessed and give example (6)
What are the difference between Structure and Union (5)
Works For You……….
Implements rational number using Structures with numerator and denominator, Write routines to ass, multiply, subtract numbers
Implement complex numbers using structures with real and complex parts. Write routines to add, multiply and negate numbers
Assume integer needs 4 bytes, Float needs 8 bytes, char needs 1 byte.
Struct nametype
{
Char Fname [10];
Char minit;
Char lname [15];
};
Struct person
{
struct nametype name;
int age;
float avgmark;
};
Struct person p[100];
If starting address of P is 100, what are the starting address of
i) P [20];
ii) P [5]. name . minit
iii) P [21]. avgmark
Tuesday, September 13, 2005
Arrays
TWO MARK QUESTIONS:
1) Define Array
Array is a finite, ordered set of homogeneous elements.
Finite- Specific number of elements in the array.
Ordered- elements are arranged in sequential locations
Homogeneous-all elements in array must be of same type.
2) What are the basic operations that could be performed on an array? Explain.
The Basic Operations are
i) Extraction – It needs array and index from which the element need to be extracted. It return the element of array. X=a[i];
ii) Storing – It needs the array, index and the element to be stored. A[i]=x;
3) What is lower bound and upper bound in an array?
The smallest element of an array’s index is called its lower bound. The highest element of an array’s index is called its upper bound.
4) What is a one-dimensional array? What is the use of it?
One-dimensional array use a single index for reference of array elements. It is used when large number of items should be kept in memory and reference all elements in a uniform manner.
5) What are the advantages of using array?
i) It allows the programmer to declare single identifier and obtain a large amount of space.
ii) It allows programmers to reference each element of the group in a uniform manner, instead of using separate identifier for each.
6) What is base address in an array? How will you reference ith element in array?
The address of the first element in an array is called the base address of array. The ith element in an array could be referenced with
Baseaddress + (index * elementsize)
7) What are two-dimensional arrays?
The component type of a array can be another type. They use two indices for referring each element.
Two-dimensional array can be declared as datatype arrayname[index1][index2]
(eg) int a[3][5];
OTHER QUESTIONS:
1) Write the ADT specification for array. (6 marks)
2) What are the methods to implement array for varying length strings? (8 marks)
3) How will you pass an array to a function? Give example.(6 marks)
4) Explain about Character Strings in C. What are the operations that could be performed in Character strings? Write C function for each. (12 marks)
5) What are the different methods to implement two dimensional array in memory?
Works for you…
1) Write a C program to read 20 integers and to find the average of them. Also find how much each deviate from average.
2) Consider a 2 dimensional array declared as int a[10][15]. Assume each unit requires 1 unit for storage. If the base address is 1000, what is the address of a[4][5], a[9][9] and a[10][15].
1) Define Array
Array is a finite, ordered set of homogeneous elements.
Finite- Specific number of elements in the array.
Ordered- elements are arranged in sequential locations
Homogeneous-all elements in array must be of same type.
2) What are the basic operations that could be performed on an array? Explain.
The Basic Operations are
i) Extraction – It needs array and index from which the element need to be extracted. It return the element of array. X=a[i];
ii) Storing – It needs the array, index and the element to be stored. A[i]=x;
3) What is lower bound and upper bound in an array?
The smallest element of an array’s index is called its lower bound. The highest element of an array’s index is called its upper bound.
4) What is a one-dimensional array? What is the use of it?
One-dimensional array use a single index for reference of array elements. It is used when large number of items should be kept in memory and reference all elements in a uniform manner.
5) What are the advantages of using array?
i) It allows the programmer to declare single identifier and obtain a large amount of space.
ii) It allows programmers to reference each element of the group in a uniform manner, instead of using separate identifier for each.
6) What is base address in an array? How will you reference ith element in array?
The address of the first element in an array is called the base address of array. The ith element in an array could be referenced with
Baseaddress + (index * elementsize)
7) What are two-dimensional arrays?
The component type of a array can be another type. They use two indices for referring each element.
Two-dimensional array can be declared as datatype arrayname[index1][index2]
(eg) int a[3][5];
OTHER QUESTIONS:
1) Write the ADT specification for array. (6 marks)
2) What are the methods to implement array for varying length strings? (8 marks)
3) How will you pass an array to a function? Give example.(6 marks)
4) Explain about Character Strings in C. What are the operations that could be performed in Character strings? Write C function for each. (12 marks)
5) What are the different methods to implement two dimensional array in memory?
Works for you…
1) Write a C program to read 20 integers and to find the average of them. Also find how much each deviate from average.
2) Consider a 2 dimensional array declared as int a[10][15]. Assume each unit requires 1 unit for storage. If the base address is 1000, what is the address of a[4][5], a[9][9] and a[10][15].
Monday, September 12, 2005
Introduction to data structure
TWO MARK QUESTIONS:
1) What does data structure deal with?
Data structure deals with the study of
• Information organized in a computer,
• How it can be manipulated and
• How it can be utilized.
2) Define Bit.
The basic unit of information is Bit (Binary digit), whose values state one of two mutually exclusive possibilities.
3) What are the ways to express negative binary integers? How could they be obtained?
The two methods are
i) Ones complement method
ii) Twos complement method
Ones complement is obtained by changing each bit to opposite bit setting
Twos complement is obtained by adding 1 to the LSB of ones complement.
4) Represent –38 in ones complement and twos complement method.
Binary representation of 38 is 00100110
Ones complement is 11011001
Twos complement is 11011001+1=11011010
5) What is the general format of floating point number? Represent 3x10-3 in binary form. What are the advantages of floating point numbers?
The general format of floating point number is mantissa x base exponent
The floating point of 3x10-3 is 00000000000000000000001111111101
The advantage is even very small and very large numbers can be specified in 32 bits.
6) Define byte size and byte.
The number of bits necessary to represent a character in a particular computer is called byte size.
A group of bits used to represent character together form byte.
7) Define data type.
A method of interpreting bit pattern is data type.
8) Define bit, bit content, byte and word
The basic unit of information is bit, whose value asserts one of two mutually exclusive possibilities.
• The setting of a bit is called bit content
• Group of bits form larger units called byte.
• Several bytes group together to form words.
9) What are the uses of declaration?
i) For the programmer to specify how the contents of computer memory are to be interpreted by the program
ii) It specifies how much memory is required for the particular entity.
10) What is hardware implementation for data type specification?
If the data type implementation needs circuitry to perform necessary operations, and it is constructed as part of computer.
11) What is software implementation for data type specification?
A program consisting of already existing instructions is written to interpret bit strings in desired manner, to perform required operation.
12) Write the procedure to copy one string to another.
i=0;
while (source[i]!=’\0’)
{
MOVE ( Source[i],dest[i],1);
i++;
}
desat[i]=’\0’;
13) Write the procedure to concatenate two strings c1, c2 to c3.
i=0;
While (c1[i]!=’\0’)
{
MOVE (c1[i],c3[i],1);
i++;
}
j=0;
While (c2[j]!=’\0’)
{
MOVE (c2[j++],c3[i++],1);
}
c3[i]=’\0’;
14) What is abstract data type?
ADT is the tool for specifying logical properties of a data type. Abstract data types are data types created from existing data type and they adapt their operations too.
15) What are the two part of ADT? Explain.
i) Value definition – This defines collection of values for the ADT. It has two parts: The definition clause and the condition clause.
ii) Operator definition- Each operation is defined as a abstract function. The three parts of ADT function are: Header, Precondition and Post condition.
16) What is a header, precondition and postcondition in a ADT function.
i) Header – indicate this is a ADT operator definition. Declares variables.
ii) Precondition – Specify any restrictions that must be satisfied before the operation can be applied.
iii) Post condition – Specifies what the operation does.
17) Define sequence and subsequence.
Sequence is an ordered set of elements. A subsequence is a contiguous portion of a sequence.
18) Write short note on data types in C.
Basic data types in C are (i) int (ii) float (iii) char (iv) double.
Integer has three qualifiers- short, long and unsigned. short and long indicate the maximum size of variable’s vale. Unsigned integer is always possible.
19) Define pointer. How could it be declared?
Pointer is a variable that holds address of a data object or a function. Pointers allow the programmer to refer to the location of objects as well as the contents of the location.
The declaration is as, data type * pointer_name;
(eg) int *pi;
20) Explain pass by value and give example.
The values being passed from the function call are copied into the parameters of the called function at the time the function s invoked. The change in value of the parameter in called function will not affect the same variable in called function.
(eg) x=1;
printf(“%d\n”,x);
funct(x);
printf(“%d\n”,x);
…
…
funct(y)
int y;
{
++y;
printf(“%d\n”,y);
}
21) Explain pass by reference and give example.
If the calling function passes the address of the memory location, and the called function parameter values are changed, it also affects the calling function value. This is called pass by reference.
(eg) x=1;
printf(“%d\n”,x);
funct(&x);
printf(“%d\n”,x);
…
…
funct(py)
int *py;
{
++(*py);
printf(“%d\n”,*py);
}
22) What are the goals of data structure
i) To identify and develop mathematical entities and operations, that determine the way to solve problems.
ii)To determine representation for those abstract entities to implement abstract operations, with existing data types.
OTHER QUESTIONS
1) Explain ADT. (8)
2) Write the ADT for Rational numbers. (6 marks)
3) Write the ADT for varying length strings. (6 marks)
4) Explain Pointers. Give example of pass by value and pass by reference and explain. (16 marks).
Works for you….
1) Write an ADT specification for complex numbers a+bi where
Abs(a+bi) is sqrt(a*a+b*b)
(a+bi)+(c+di) is (a+c)+(b+d)i
(a+bi)*(c+di) is (a*c-b*d)+(a*d+b*c)i
-(a+bi) is (-a)+(-b)i
2) Prove that there are 2 power n different settings for n two-way switches. Suppose that we wanted to have m settings. How many switches would be necessary?
1) What does data structure deal with?
Data structure deals with the study of
• Information organized in a computer,
• How it can be manipulated and
• How it can be utilized.
2) Define Bit.
The basic unit of information is Bit (Binary digit), whose values state one of two mutually exclusive possibilities.
3) What are the ways to express negative binary integers? How could they be obtained?
The two methods are
i) Ones complement method
ii) Twos complement method
Ones complement is obtained by changing each bit to opposite bit setting
Twos complement is obtained by adding 1 to the LSB of ones complement.
4) Represent –38 in ones complement and twos complement method.
Binary representation of 38 is 00100110
Ones complement is 11011001
Twos complement is 11011001+1=11011010
5) What is the general format of floating point number? Represent 3x10-3 in binary form. What are the advantages of floating point numbers?
The general format of floating point number is mantissa x base exponent
The floating point of 3x10-3 is 00000000000000000000001111111101
The advantage is even very small and very large numbers can be specified in 32 bits.
6) Define byte size and byte.
The number of bits necessary to represent a character in a particular computer is called byte size.
A group of bits used to represent character together form byte.
7) Define data type.
A method of interpreting bit pattern is data type.
8) Define bit, bit content, byte and word
The basic unit of information is bit, whose value asserts one of two mutually exclusive possibilities.
• The setting of a bit is called bit content
• Group of bits form larger units called byte.
• Several bytes group together to form words.
9) What are the uses of declaration?
i) For the programmer to specify how the contents of computer memory are to be interpreted by the program
ii) It specifies how much memory is required for the particular entity.
10) What is hardware implementation for data type specification?
If the data type implementation needs circuitry to perform necessary operations, and it is constructed as part of computer.
11) What is software implementation for data type specification?
A program consisting of already existing instructions is written to interpret bit strings in desired manner, to perform required operation.
12) Write the procedure to copy one string to another.
i=0;
while (source[i]!=’\0’)
{
MOVE ( Source[i],dest[i],1);
i++;
}
desat[i]=’\0’;
13) Write the procedure to concatenate two strings c1, c2 to c3.
i=0;
While (c1[i]!=’\0’)
{
MOVE (c1[i],c3[i],1);
i++;
}
j=0;
While (c2[j]!=’\0’)
{
MOVE (c2[j++],c3[i++],1);
}
c3[i]=’\0’;
14) What is abstract data type?
ADT is the tool for specifying logical properties of a data type. Abstract data types are data types created from existing data type and they adapt their operations too.
15) What are the two part of ADT? Explain.
i) Value definition – This defines collection of values for the ADT. It has two parts: The definition clause and the condition clause.
ii) Operator definition- Each operation is defined as a abstract function. The three parts of ADT function are: Header, Precondition and Post condition.
16) What is a header, precondition and postcondition in a ADT function.
i) Header – indicate this is a ADT operator definition. Declares variables.
ii) Precondition – Specify any restrictions that must be satisfied before the operation can be applied.
iii) Post condition – Specifies what the operation does.
17) Define sequence and subsequence.
Sequence is an ordered set of elements. A subsequence is a contiguous portion of a sequence.
18) Write short note on data types in C.
Basic data types in C are (i) int (ii) float (iii) char (iv) double.
Integer has three qualifiers- short, long and unsigned. short and long indicate the maximum size of variable’s vale. Unsigned integer is always possible.
19) Define pointer. How could it be declared?
Pointer is a variable that holds address of a data object or a function. Pointers allow the programmer to refer to the location of objects as well as the contents of the location.
The declaration is as, data type * pointer_name;
(eg) int *pi;
20) Explain pass by value and give example.
The values being passed from the function call are copied into the parameters of the called function at the time the function s invoked. The change in value of the parameter in called function will not affect the same variable in called function.
(eg) x=1;
printf(“%d\n”,x);
funct(x);
printf(“%d\n”,x);
…
…
funct(y)
int y;
{
++y;
printf(“%d\n”,y);
}
21) Explain pass by reference and give example.
If the calling function passes the address of the memory location, and the called function parameter values are changed, it also affects the calling function value. This is called pass by reference.
(eg) x=1;
printf(“%d\n”,x);
funct(&x);
printf(“%d\n”,x);
…
…
funct(py)
int *py;
{
++(*py);
printf(“%d\n”,*py);
}
22) What are the goals of data structure
i) To identify and develop mathematical entities and operations, that determine the way to solve problems.
ii)To determine representation for those abstract entities to implement abstract operations, with existing data types.
OTHER QUESTIONS
1) Explain ADT. (8)
2) Write the ADT for Rational numbers. (6 marks)
3) Write the ADT for varying length strings. (6 marks)
4) Explain Pointers. Give example of pass by value and pass by reference and explain. (16 marks).
Works for you….
1) Write an ADT specification for complex numbers a+bi where
Abs(a+bi) is sqrt(a*a+b*b)
(a+bi)+(c+di) is (a+c)+(b+d)i
(a+bi)*(c+di) is (a*c-b*d)+(a*d+b*c)i
-(a+bi) is (-a)+(-b)i
2) Prove that there are 2 power n different settings for n two-way switches. Suppose that we wanted to have m settings. How many switches would be necessary?
Subscribe to:
Posts (Atom)