Tuesday, 7 March 2017

Data structures & Algorithms - Multiple Choice Questions (MCQs) - Objective Set 3

1. The memory address of the first element of an array is called
 a. floor address
 b. foundation address
 c. First address
 d. base address

Answer
 d. base address
 

2. The memory address of fifth element of an array can be calculated by the formula
a. LOC(Array[5]=Base(Array)+w(5-lower bound), where w is the number of words per memory cell for the array
b. LOC(Array[5])=Base(Array[5])+(5-lower bound), where w is the number of words per memory cell for the array
c. LOC(Array[5])=Base(Array[4])+(5-Upper bound), where w is the number of words per memory cell for the array
d. None of above
Answer
a. LOC(Array[5]=Base(Array)+w(5-lower bound), where w is the number of words per memory cell for the array
 


3. Which of the following data structures are indexed structures?
a. linear arrays
b. linked lists
c. both of above
d. none of above
 Answer
a. linear arrays
4. Which of the following is not the required condition for binary search algorithm?
a. The list must be sorted
b. there should be the direct access to the middle element in any sublist
c. There must be mechanism to delete and/or insert elements in list
d. none of above
 Answer
 c. There must be mechanism to delete and/or insert elements in list
5. Which of the following is not a limitation of binary search algorithm?
a. must use a sorted array
b. requirement of sorted array is expensive when a lot of insertion and deletions are needed
c. there must be a mechanism to access middle element directly
d. binary search algorithm is not efficient when the data elements are more than 1000.
 Answer
d. binary search algorithm is not efficient when the data elements are more than 1000
6. Two dimensional arrays are also called
a. tables arrays
b. matrix arrays
c. both of above
d. none of above
Answer
c. both of above

7. A variable P is called pointer if
a. P contains the address of an element in DATA.
b. P points to the address of first element in DATA
c. P can store only memory addresses
d. P contain the DATA and the address of DATA
 Answer
a. P contains the address of an element in DATA.


8. Which of the following data structure can't store the non-homogeneous data elements?
a. Arrays
b. Records
c. Pointers
d. None
 Answer
a. Arrays
9. Which of the following data structure store the homogeneous data elements?
a. Arrays
b. Records
c. Pointers
d. None
 Answer
b. Records
10. Each data item in a record may be a group item composed of sub-items; those items which are indecomposable are called
a. elementary items
b. atoms
c. scalars
d. all of above
 Answer
d. all of above
11. The difference between linear array and a record is
a. An array is suitable for homogeneous data but hte data items in a record may have different data type
b. In a record, there may not be a natural ordering in opposed to linear array.
c. A record form a hierarchical structure but a lienear array does not
d. All of above
 Answer
d. All of above

12. Which of the following statement is false?
a. Arrays are dense lists and static data structure
b. data elements in linked list need not be stored in adjecent space in memory
c. pointers store the next data element of a list
d. linked lists are collection of the nodes that contain information part and next pointer
 Answer
 c. pointers store the next data element of a list
13. Binary search algorithm can not be applied to
a. sorted linked list
b. sorted binary trees
c. sorted linear array
d. pointer array
 Answer
a. sorted linked list
14. When new data are to be inserted into a data structure, but there is no available space; this situation is usually called
a. underflow
b. overflow
c. housefull
d. saturated
 Answer
b. overflow
 

15. The situation when in a linked list START=NULL is
a. underflow
b. overflow
c. housefull
d. saturated
 Answer
a. underflow
16. Which of the following is two way list?
a. grounded header list
b. circular header list
c. linked list with header and trailer nodes
d. none of above
 Answer
d. none of above
17. Which of the following name does not relate to stacks?
a. FIFO lists
b. LIFO list
c. Piles
d. Push-down lists
 Answer
a. FIFO lists
18. The term "push" and "pop" is related to the
a. array
b. lists
c. stacks
d. all of above
 Answer
c. stacks
19. A data structure where elements can be added or removed at either end but not in the middle
a. Linked lists
b. Stacks
c. Queues
d. Deque
 Answer
Deque

20. When inorder traversing a tree resulted E A C K F H D B G; the preorder traversal would return
a. FAEKCDBHG
b. FAEKCDHGB
c. EAFKHDCBG
d. FEAKDCHBG
Answer
b. FAEKCDHGB


















Posted by at No comments:
Labels:

Data structures & Algorithms - Multiple Choice Questions (MCQs) - Objective Set 2




1. Which of the following is not the type of queue?

 A) Ordinary queue

 B) Single ended queue

 C) Circular queue

 D) Priority queue
2. The property of binary tree is

 A) The first subset is called left subtree

 B) The second subtree is called right subtree

 C) The root cannot contain NULL

 D) The right subtree can be empty
3. State true or false.

 i) The degree of root node is always zero.

 ii) Nodes that are not root and not leaf are called as internal nodes.
A) True, True

 B) True, False

 C) False, True

 D) False, False
4. Any node is the path from the root to the node is called

 A) Successor node

 B) Ancestor node

C) Internal node

D) None of the above
5. State true of false.

 i) A node is a parent if it has successor nodes.

 ii) A node is child node if out degree is one.

 A) True, True

 B) True, False

 C) False, True

 D) False, False
6. ………………. is not an operation performed on linear list

 a) Insertion b) Deletion c) Retrieval d) Traversal

 A) only a,b and c

 B) only a and b

 C) All of the above

 D) None of the above
7. Which is/are the application(s) of stack

 A) Function calls

 B) Large number Arithmetic

 C) Evaluation of arithmetic expressions

 D) All of the above
8. A …………… is an acyclic digraph, which has only one node with indegree 0, and other nodes have in-degree 1.

 A) Directed tree

 B) Undirected tree

 C) Dis-joint tree

 D) Direction oriented tree
9. …………………. Is a directed tree in which outdegree of each node is less than or equal to two.

 A) Unary tree

 B) Binary tree

 C) Trinary tree

 D) Both B and C
10. State true or false.

 i) An empty tree is also a binary tree.

 ii) In strictly binary tree, the out-degree of every node is either o or 2.

 A) True, False

 B) False, True

 C) True, True

 D) False, False
11. Which of the following data structures are indexed structures?

 A. Linear arrays

 B. Linked lists

 C. Queue

 D. Stack
12. Which of the following data structure store the homogeneous data elements?

 A. Arrays

 B. Records

 C. Pointers

 D. Lists
13. When new data are to be inserted into a data structure, but there is not available space; this situation is usually called ....

 A. Underflow

 B. overflow

 C. houseful

 D. saturated
14. A data structure where elements can be added or removed at either end but not in the middle is called ...

 A. linked lists

 B. stacks

 C. queues

 D. dequeue
15. Operations on a data structure may be .....

 A. creation 

 B. destruction

 C. selection

 D. all of the above
16. The way in which the data item or items are logically related defines .....

 A. storage structure

 B. data structure

 C. data relationship

 D. data operation 
17. Which of the following are the operations applicable an primitive data structures?

 A. create

 B. destroy

 C. update

 D. all of the above
18. The use of pointers to refer elements of a data structure in which elements are logically adjacent is ....

 A. pointers

 B. linked allocation

 C. stack 

 D. queue
19. Arrays are best data structures

 A. for relatively permanent collections of data

 B. for the size of the structure and the data in the structure are constantly changing

 C. for both of above situation

 D. for non of above situation
20. Which of the following statement is false?

 A. Arrays are dense lists and static data structure.

 B. Data elements in linked list need not be stored in adjacent space in memory

 C. Pointers store the next data element of a list.

 D. Linked lists are collection of the nodes that contain information part and next pointer.

Answers:


 1. B) Single ended queue
2. D) The right ..... empty
3. C) False, True
4. B) Ancestor node
5. B) True, False 
6. D) None of the above
7. D) All of the above
8. A) Directed tree
9. B) Binary tree
10. C) True, True
11. A. Linear arrays 
12. B. Records
13. B. overflow 
14. D. dequeue
15. D. all of the above 
16. B. data structure
17. D. all of the above 
18. B. linked allocation
20. C. Pointers store the next data element of a list. 
Posted by at No comments:
Labels:

Sunday, 5 March 2017

Stack data structure with program

Stacks

Stack is an abstract data type with a bounded(predefined) capacity. It is a simple data structure that allows adding and removing elements in a particular order. Every time an element is added, it goes on the top of the stack, the only element that can be removed is the element that was at the top of the stack, just like a pile of objects. A stack is an Abstract Data Type (ADT), commonly used in most programming languages. It is named stack as it behaves like a real-world stack, for example – a deck of cards or a pile of plates, etc.

A real-world stack allows operations at one end only. For example, we can place or remove a card or plate from the top of the stack only. Likewise, Stack ADT allows all data operations at one end only. At any given time, we can only access the top element of a stack.


Basic features of Stack
This feature makes it LIFO data structure. LIFO stands for Last-in-first-out. Here, the element which is placed (inserted or added) last, is accessed first. In stack terminology, insertion operation is called PUSH operation and removal operation is called POP operation.
  1. Stack is an ordered list of similar data type.
  2. Stack is a LIFO structure. (Last in First out).
  3. push() function is used to insert new elements into the Stack and pop() is used to delete an element from the stack. Both insertion and deletion are allowed at only one end of Stack called Top.
  4. Stack is said to be in Overflow state when it is completely full and is said to be in Underflow state if it is completely empty.


Applications of Stack
·         To reverse a word. You push a given word to stack - letter by letter - and then pop letters from the stack.
·         An "undo" mechanism in text editors; this operation is accomplished by keeping all text changes in a stack.
o    Undo/Redo stacks in Excel or Word.
·         Language processing :
o    space for parameters and local variables is created internally using a stack.
o    compiler's syntax check for matching braces is implemented by using stack.
·         A stack of plates/books in a cupboard.
·         A garage that is only one car wide. To remove the first car in we have to take out all the other cars in after it.
·         Wearing/Removing Bangles.
·         Back/Forward stacks on browsers.
·         Support for recursion
o    Activation records of method calls.


Implementation of Stack

Stack can be easily implemented using an Array or a Linked List. Arrays are quick, but are limited in size and Linked List requires overhead to allocate, link, unlink, and deallocate, but is not limited in size. Here we will implement Stack using array.


Program

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
#include <stdio.h>
#include <conio.h>
#define MAXSIZE 5

typedef struct stack /* Structure definition for stack */
{
    int stk[MAXSIZE];
    int top;
}STACK ;
STACK s;

/* Function declaration/Prototype*/

void push (void);
int pop(void);
void display (void);
main ()
{
    int choice,option;
    //clrscr ();
    option = 1;
    s.top = -1;
    
    printf ("STACK OPERATIONn");
    while (option)
    {
        printf ("------------------------------------------n");
        printf (" 1 --> PUSH n");
        printf (" 2 --> POP n");
        printf (" 3 --> DISPLAY n");
        printf (" 4 --> EXIT n");
        printf ("------------------------------------------n");
        
        printf ("Enter your choicen");
        scanf ("%d", &choice);
        
        switch (choice)
        {
            case 1: push();
            break;
            case 2: pop();
            break;
            case 3: display();
            break;
            case 4: return 0;
        }
        
        fflush (stdin);
        printf ("Do you want to continue(Type 0 or 1)?n");
        scanf ("%d", &option);
    }
    
}

/*Function to add an element to the stack*/
void push ()
{
    int num;
    if (s.top == (MAXSIZE - 1))
    {
        printf ("Stack is Fulln");
        return;
    }
    else
    {
        printf ("Enter the element to be pushedn");
        scanf ("%d", &num);
        s.top = s.top + 1;
        s.stk[s.top] = num;
    }
    return;
}

/*Function to delete an element from the stack*/
int pop ()
{
    int num;
    if (s.top == - 1)
    {
        printf ("Stack is Emptyn");
        return (s.top);
    }
    else
    {
        num = s.stk[s.top];
        printf ("poped element is = %dn", s.stk[s.top]);
        s.top = s.top - 1;
    }
    return(num);
}

/*Function to display the status of the stack*/
void display ()
{
    int i;
    if (s.top == -1)
    {
        printf ("Stack is emptyn");
        return;
    }
    else
    {
        printf ("nThe status of the stack isn");
        for (i = s.top; i >= 0; i--)
        {
            printf ("%dn", s.stk[i]);
        }
    }
    printf ("n");
}
Posted by at No comments:
Labels: ,
Subscribe to: Posts (Atom)