Tuesday, 7 March 2017

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: ,

Thursday, 2 March 2017

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

Data structures & Algorithms - Multiple Choice Questions (MCQs) - Objective Set 1
1. Two main measures for the efficiency of an algorithm are
a. Processor and memory
b. Complexity and capacity
c. Time and space
d. Data and space
 Answer (C)

2. The time factor when determining the efficiency of algorithm is measured by
a. Counting microseconds
b. Counting the number of key operations
c. Counting the number of statements
d. Counting the kilobytes of algorithm

 Answer (B)
 
3. The space factor when determining the efficiency of algorithm is measured by
a. Counting the maximum memory needed by the algorithm
b. Counting the minimum memory needed by the algorithm
c. Counting the average memory needed by the algorithm
d. Counting the maximum disk space needed by the algorithm

  Answer (A)
4. Which of the following case does not exist in complexity theory
a. Best case
b. Worst case
c. Average case
d. Null case

  Answer (D)
5. The Worst case occur in linear search algorithm when 
a. Item is somewhere in the middle of the array
b. Item is not in the array at all
c. Item is the last element in the array
d. Item is the last element in the array or is not there at all

  Answer (D)
6. The Average case occur in linear search algorithm
a. When Item is somewhere in the middle of the array
b. When Item is not in the array at all
c. When Item is the last element in the array
d. When Item is the last element in the array or is not there at all

  Answer (A)
7. The complexity of the average case of an algorithm is 
a. Much more complicated to analyze than that of worst case
b. Much more simpler to analyze than that of worst case
c. Sometimes more complicated and some other times simpler than that of worst case
d. None or above
 Answer (A)

 
8. The complexity of linear search algorithm is
a. O(n)
b. O(log n)
c. O(n2)
d. O(n log n)

  Answer (A)
9. The complexity of Binary search algorithm is 
a. O(n)
b. O(log n )
c. O(n2)
d. O(n log n)

  Answer (B)
10. The complexity of Bubble sort algorithm is 
a. O(n)
b. O(log n)
c. O(n2)
d. O(n log n)

  Answer (C)
11. The complexity of merge sort algorithm is
a. O(n)
b. O(log n)
c. O(n2)
d. O(n log n)

  Answer (D)
12. The indirect change of the values of a variable in one module by another module is called
a. internal change
b. inter-module change
c. side effect
d. side-module update

  Answer (C)
13. Which of the following data structure is not linear data structure?
a. Arrays
b. Linked lists
c. Both of above
d. None of above

 Answer (D) 
14. Which of the following data structure is linear data structure?
a. Trees
b. Graphs
c. Arrays
d. None of above
 Answer (C)

 
15. The operation of processing each element in the list is known as
a. Sorting
b. Merging
c. Inserting
d. Traversal

  Answer (D)
16. Finding the location of the element with a given value is:
a. Traversal
b. Search
c. Sort
d. None of above

  Answer (B)
17. 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 none of above situation

  Answer (A)
18. Linked lists are best suited
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 none of above situation

  Answer (B)
19. Each array declaration need not give, implicitly or explicitly, the information about
a. the name of array
b. the data type of array
c. the first data from the set to be stored
d. the index set of the array

  Answer (C)
20. The elements of an array are stored successively in memory cells because
a. by this way computer can keep track only the address of the first element and the addresses of other elements can be calculated
b. the architecture of computer memory does not allow arrays to store other than serially
c. both of above
d. none of above
 Answer (A)
Q 21 - Which of the following usees FIFO method
A - Queue
B - Stack
C - Hash Table
D - Binary Search Tree
Answer (A)
Q 22 - Queue data structure works on
A - LIFO
B - FIFO
C - FILO
D - none of the above
Answer (A)

Q 23 - Minimum number of moves required to solve a Tower of Hanoi puzzle is
A - 2n2
B - 2n-1
C - 2n - 1
D - 2n - 1
Answer(C)

Q 24 - What is not true about insertion sort?
A - Exhibits the worst case performance when the initial array is sorted in reverse order.
B - Worst case and average case performance is Ο(n2)
C - Can be compared to the way a card player arranges his card from a card deck.
D - None of the above!
Answer(D)

All given options are true about insertion sort.
Q 25 - Which of the following is example of in-place algorithm?
A - Bubble Sort
B - Merge Sort
C - Insertion Sort
D - All of the above
Answer(B)
Only Merge sort requires extra space
Q 26 - Which of the below mentioned sorting algorithms are not stable?
A - Selection Sort
B - Bubble Sort
C - Merge Sort
D - Insertion Sort
Answer(A)

Except selection sort, all other soring algorithms are stable.
Q 27 - Which of these algorithmic approach tries to achieve localized optimum solution −
A - Greedy approach
B - Divide and conquer approach
C - Dynamic approach
D - All of the above
Answer(A)
Q 28 - If there's no base criteria in a recursive program, the program will
A - not be executed.
B - execute until all conditions match.
C - execute infinitely.
D - obtain progressive approach.
Answer(C)
Q 29 - A balance factor in AVL tree is used to check
A - what rotation to make.
B - if all child nodes are at same level.
C - when the last rotation occured.
D - if the tree is unbalanced.
 Answer(D)
The balance factor (BalanceFactor = height(left-sutree) − height(right-sutree)) is used to check if the tree is balanced or unbalanced.

Q 30 - If the data collection is in sorted form and equally distributed then the run time complexity of interpolation search is −
A - Ο(n)
B - Ο(1)
C - Ο(log n)
D - Ο(log (log n))
Answer(D)
Runtime complexity of interpolation search algorithm is Ο(log (log n)) as compared to Ο(log n) of BST in favourable situations.


Posted by at No comments:
Labels:
Subscribe to: Posts (Atom)