Breaking

बुधवार, 29 जनवरी 2020

DATA STRUCTURE Short Question Answer

  1. Answer :
    A data structure is a way of organizing data that considers not only the items stored, but also their relationship to each other. Advance knowledge about the relationship between data items allows designing of efficient algorithms for the manipulation of data.
  2. Answer :
    It must rich enough in structure to reflect the actual relationship of data in real world. The structure should be simple enough for efficient processing of data.
  3. Answer :
    STACK:
    i) Stack is a ordered collection of items.
    ii) Stack is a dynamic object whose size is constantly changing as items are pushed and popped.
    iii) Stack may contain different data types.
    iv) Stack is declared as a structure containing an array to hold the element of the stack, and an integer to indicate the current stack top within the array.
    ARRAY:
    i) Array is an ordered collection of items.
    ii) Array is a static object i.e. no of item is fixed and is assigned by the declaration of the array.
    iii) It contains same data types.
    iv) Array can be home of a stack i.e. array can be declared large enough for maximum size of the stack.
  4. Answer :
    The definition which defines an object in terms of simpler cases of itself is called recursive definition.
  5. Answer :
    In sequential search each item in the array is compared with the item being searched until a match occurs. It is applicable to a table organized either as an array or as a linked list.
  6. Answer :
    When a function is called
    i) arguments are passed.
    ii) local variables are allocated and initialized.
    ii) transferring control to the function.
  7. Answer :
    i) Return address is retrieved.
    ii) Function’s data area is freed.
    iii) Branch is taken to the return address.
  8. Answer :
    A linked list is a linear collection of data elements, called nodes, where the linear order is given by pointers. Each node has two parts first part contain the information of the element second part contains the address of the next node in the list.
  9. Answer :
    It is a technique in which the operating system periodically collects all the deleted space onto the free storage list.
    It takes place when there is minimum amount of space left in storage list or when CPU is ideal.
    The alternate method to this is to immediately reinsert the space into free storage list which is time consuming.
  10. Answer :
    When new data is to be inserted into the data structure but there is no available space i.e. free storage list is empty this situation is called overflow.
    When we want to delete data from a data structure that is empty this situation is called underflow
  11. Answer :
    i) The no of nodes needed can’t be predicted when the program is written.
    ii) The no of nodes declared must remain allocated throughout its execution.
  12. Answer :
    A queue is an ordered collection of items from which items may be deleted at one end (front end) and items inserted at the other end (rear end).
    It obeys FIFO rule there is no limit to the number of elements a queue contains
  13. Answer :
    The priority queue is a data structure in which the intrinsic ordering of the elements (numeric or alphabetic)
    Determines the result of its basic operation. It is of two types:
    i) Ascending priority queue- Here smallest item can be removed (insertion is arbitrary).
    ii) Descending priority queue- Here largest item can be removed (insertion is arbitrary)
  14. Answer :
    i) A node in a linked list (info and next field) occupies more storage than a corresponding element in an array.
    ii) Additional time spent in managing the available list
  15. Answer :
    After a call to free(p) makes a subsequent reference to *p illegal, i.e. though the storage to p is freed but the value of p(address) remain unchanged .so the object at that address may be used as the value of *p (i.e. there is no way to detect the illegality).Here p is called dangling pointer.
    To avoid this it is better to set p to NULL after executing free(p).The null pointer value doesn’t reference a storage location it is a pointer that doesn’t point to anything.
  16. Answer :i) We cannot reach any of the nodes that precede node (p)
  17. ii) If a list is traversed, the external pointer to the list must be persevered in order to reference the list again.
  18. Answer :In linear list the next field of the last node contain a null pointer, when a next field in the last node contain a pointer back to the first node it is called circular list.Advantages – From any point in the list it is possible to reach at any other point
  19. Answer :i) We can’t traverse the list backward.
    1. ii) If a pointer to a node is given we cannot delete the node.
    2. Answer :
      It is a collection of data elements called nodes,
      where each node is divided into three parts:
      1. An info field that contains the information stored in the node.
      2. Left field that contain pointer to node on left side.
      3. Right field that contain pointer to node on right side.
    3. Answer :
      • Compiler Design,
      • Operating System,
      • Database Management System,
      • Statistical analysis package,
      • Numerical Analysis,
      • Graphics,
      • Artificial Intelligence,
      • Simulation.


      Answer :
      RDBMS – Array (i.e. Array of structures)
      Network data model – Graph
      Hierarchical data model – Trees
    4. Answer :
      The heterogeneous linked list contains different data types in its nodes and we need a link, pointer to connect them. It is not possible to use ordinary pointers for this. So we go for void pointer. Void pointer is capable of storing pointer to any type as it is a generic pointer type.
    5. Answer :
      Two. One queue is used for actual storing of data and another for storing priorities.
    6. Answer :
      Stack. Because of its LIFO (Last In First Out) property it remembers its ‘caller’ so knows whom to return when the function has to return. Recursion makes use of system stack for storing the return addresses of the function calls.
      Every recursive function has its equivalent iterative (non-recursive) function. Even when such equivalent iterative procedures are written, explicit stack is to be used.
    7. Answer :Polish and Reverse Polish notations
    8. Answer :Prefix Notation:^ – * +ABC – DE + FG
      1. postfix Notation:AB + C * DE – – FG + ^
      2. Question 27. Difference Between Calloc And Malloc ?
    9. Answer :
      malloc: allocate n bytes.
      calloc: allocate m times n bytes initialized to 0.
    10. Answer :Linked List is one of the fundamental data structures. It consists of a sequence of ? nodes, each containing arbitrary data fields and one or two (”links”) pointing to the next and/or previous nodes. A linked list is a self-referential datatype because it contains a pointer or link to another data of the same type. Linked lists permit insertion and removal of nodes at any point in the list in constant time, but do not allow random access.
    11. Answer :Each entry in a linked list is called a node. Think of a node as an entry that has three sub entries. One sub entry contains the data, which may be one attribute or many attributes. Another points to the previous node, and the last points to the next node. When you enter a new item on a linked list, you allocate the new node and then set the pointers to previous and next nodes.
    12. Answer :A Queue is a sequential organization of data. A queue is a first in first out type of data structure. An element is inserted at the last position and an element is always taken out from the first position.
    13. Answer :The symbol “*” tells the computer that you are declaring a pointer. Actually it depends on context.
    14. In a statement like int *ptr; the ‘*’ tells that you are declaring a pointer.
    15. In a statement like int i = *ptr; it tells that you want to assign value pointed to by ptr to variable i.
    16. The symbol “*” is also called as Indirection Operator/ Dereferencing Operator.
    17. Answer :Yes, a pointer is a variable and can be used as an element of a structure and as an attribute of a class in some programming languages such as C++, but not Java. However, the contents of a pointer is a memory address of another location of memory, which is usually the memory address of another variable, element of a structure, or attribute of a class.
    18. Answer :There are two main parts, variable identifier and data type and the third type is optional which is type qualifier like signed/unsigned.
    19. Answer :NULL can be value for pointer type variables.
    20. VOID is a type identifier which has not size.
    21. NULL and void are not same. Example: void* ptr = NULL;
    22. Answer :STACK follows LIFO. Thus the item that is first entered would be the last removed.
    23. In array the items can be entered or removed in any order. Basically each member access is done using index. No strict order is to be followed here to remove a particular element.
    24. Array may be multidiamensional or onediamensional but stack should be onediamensional. but both are linear data structure.
    25. Answer :Create two pointers, each set to the start of the list. Update each as follows:
    26. while (pointer1) 
    27. {pointer1 = pointer1->next;
    28. pointer2 = pointer2->next;
    29. if(pointer2)pointer2=pointer2->next;
    30. if (pointer1 == pointer2) 
    31. {
    32. print (”circularn”);}}

    33. Question 36. Whether Linked List Is Linear Or Non-linear Data Structure?Answer :According to Access strategies Linked list is a linear one.
    34. According to Storage Linked List is a Non-linear one\

    35. Question 37. State The Difference Between Arrays And Linked Lists?
    36. Answer :
    37. Question 38. Define A Stack?
    38. Answer :Stack is an ordered collection of elements in which insertions and deletions are restricted to one end. The end from which elements are added and/or removed is referred to as top of the stack. Stacks are also referred as piles, push-down lists and last-in-first-out (LIFO) lists.

    39. Question 39. List Out The Basic Operations That Can Be Performed On A Stack ?
    40. Answer :The basic operations that can be performed on a stack are
    41. Push operation.
    42. Pop operation.
    43. Peek operation.
    44. Empty check.
    45. Fully occupied check.

    46. Question40. State The Different Ways Of Representing Expressions?
    47. Answer :The different ways of representing expressions are
    48. Infix Notation.
    49. Prefix Notation.
    50. Postfix Notation.

    51. Question 41. Define A Priority Queue?
    52. Answer :Priority queue is a collection of elements, each containing a key referred as the priority for that element. Elements can be inserted in any order (i.e., of alternating priority), but are arranged in order of their priority value in the queue. The elements are deleted from the queue in the order of their priority (i.e., the elements with the highest priority is deleted first). The elements with the same priority are given equal importance and processed accordingly.

    53. Question 42. State The Difference Between Queues And Linked Lists?Answer :The difference between queues and linked lists is that insertions and deletions may occur anywhere in the linked list, but in queues insertions can be made only in the rear end and deletions can be made only in the front end.

    54. Question 43. Define A Deque?
    55. Answer :Deque (Double-Ended Queue) is another form of a queue in which insertions and deletions are made at both the front and rear ends of the queue. There are two variations of a deque, namely, input restricted deque and output restricted deque. The input restricted deque allows insertion at one end (it can be either front or rear) only. The output restricted deque allows deletion at one end (it can be either front or rear) only.

    56. Question 44. Why You Need A Data Structure?
    57. Answer :A data structure helps you to understand the relationship of one data element with the other and organize it within the memory. Sometimes the organization might be simple and can be very clearly visioned.
    58. Eg; List of names of months in a year –Linear Data Structure, List of historical places in the world- Non-Linear Data Structure. A data structure helps you to analyze the data, store it and organize it in a logical and mathematical manner.

    59. Question 45. What Do You Mean By Shortest Path?
    60. Answer :A path having minimum weight between two vertices is known as shortest path, in which weight is always a positive number.\

    61. Question 46. What Are The Tasks Performed During Postorder Traversal?
    62. Answer :
    63. Traverse the left sub-tree.
    64. Traverse the right sub-tree.
    65. Process the root node.

    66. Question 47. What Are The Tasks Performed During Inorder Traversal?
    67. Answer :
    68. Traverse the left sub-tree.
    69. Process the root node.
    70. Traverse the right sub-tree.

    71. Question 48. What Are The Tasks Performed During Preorder Traversal?
    72. Answer :Process the root node.
    73. Traverse the left sub-tree.
    74. Traverse the right sub-tree.

    75. Question 49. What Are The Tasks Performed While Traversing A Binary Tree?Answer :
    76. Visiting a node.
    77. Traverse the left sub-tree.
    78. Traverse the right sub-tree.

    79. Question 50. What Are The Different Binary Tree Traversal Techniques?
    80. Answer :Preorder traversal.
    81. Inorder traversal.
    82. Postorder traversal.
    83. Levelorder traversal.

    84. Question 51. What Is Meant By Binary Tree Traversal?
    85. Answer :Traversing a binary tree means moving through all the nodes in the binary tree, visiting each node in the tree only once.

    86. Question 52. State The Properties Of A Binary Tree?
    87. Answer :The maximum number of nodes on level n of a binary tree is 2n-1, where n≥1.
    88. The maximum number of nodes in a binary tree of height n is 2n-1, where n≥1.
    89. For any non-empty tree, nl=nd+1 where nl is the number of leaf nodes and nd is the number of nodes of degree 2.

    90. Question 53. Define A Right-skewed Binary Tree?
    91. Answer :A right-skewed binary tree is a tree, which has only right child nodes.

    92. Question 54. Define A Complete Binary Tree?
    93. Answer :A complete binary tree is a tree in which every non-leaf node has exactly two children not necessarily to be on the same level.

    94. Question 55. Define A Full Binary Tree ?
    95. Answer :A full binary tree is a tree in which all the leaves are on the same level and every non-leaf node has exactly two children.

    96. Question 56. Define Non-terminal Nodes In A Tree?
    97. Answer :All intermediate nodes that traverse the given tree from its root node to the terminal nodes are referred as non-terminal nodes.

    98. Question 57. Define Terminal Nodes In A Tree?
    99. Answer :A node that has no children is called a terminal node. It is also referred to as leaf node.

    100. Question 58. Define A Path In A Tree?
    101. Answer :A path in a tree is a sequence of distinct nodes in which successive nodes are connected by edges in the tree.

    102. Question 59. Define A Binary Tree?
    103. Answer :A binary tree is a finite set of nodes which is either empty or consists of a root and two disjoint binary trees called the left sub-tree and right sub-tree.

    104. Question 60. Define Forest?
    105. Answer :A tree may be defined as a forest in which only a single node (root) has no predecessors. Any forest consists of a collection of trees.

    106. Question 61. What Do You Mean By Level Of The Tree?
    107. Answer :The root node is always considered at level zero, then its adjacent children are supposed to be at level 1 and so on.
    108. Here, node A is at level 0, nodes B and C are at level 1 and nodes D and E are at level 2.

    1. Question62. Define Depth And Height Of A Tree?
    2. Answer :The depth of the tree is the depth of the deepest leaf. The height of the tree is equal to the height of the root. Always depth of the tree is equal to height of the tree.

    3. Question 63. Define Depth And Height Of A Node?
    4. Answer :For any node ni, the depth of ni is the length of the unique path from the root to ni. The height of ni is the length of the longest path from ni to a leaf.

    5. Question 64. Define Parent Node?
    6. Answer :The node which is having further sub-branches is called the parent node of those sub-branches.
    7. Here C is the parent node of D and E.




    1. Question 65. Define Internal Nodes?
    2. Answer :The nodes other than the root and the leaves are called internal nodes.




    1. Question 66. Define Leaves?
    2. Answer :These are the terminal nodes of the tree. The nodes with degree 0 are always the leaves.Here C and B are the leave nodes.





    1. Question 67. Define Degree Of The Node?
    2. Answer :The total number of sub-trees attached to that node is called the degree of the node.




    1. Question 68. Define Root?
    2. Answer :This is the unique node in the tree to which further sub-trees are attached.





    1. Question 69. Define A Tree?
    2. Answer :A tree is a collection of nodes. The collection can be empty; otherwise, a tree consists of a  distinguished node r, called the root, and zero or more nonempty (sub) trees T1, T2,…,Tk, each of whose roots are connected by a directed edge from r.

    3. Question 70. Why We Need Cursor implementation Of Linked Lists?

    4. Answer :Many languages such as BASIC and FORTRAN do not support pointers. If linked lists are required and pointers are not available, then an alternative implementation must be used known as cursor implementation.

    5. Question 71. List The Applications Of Queues?
    6. Answer :Jobs submitted to printer
    7. Real life line
    8. Calls to large companies
    9. Access to limited resources in Universities
    10. Accessing files from file server

    11. Question 72. List The Applications Of Stacks?
    12. Answer :
    13. Towers of Hanoi
    14. Reversing a string
    15. Balanced parenthesis
    16. Recursion using stack
    17. Evaluation of arithmetic expressions
    18. a
    19. Question 73. What Are The Types Of Queues?
    20. Answer :Linear Queues – The queue has two ends, the front end and the rear end. The rear end is where we insert elements and front end is where we delete elements. We can traverse in a linear queue in only one direction ie) from front to rear.

    21. Circular Queues – Another form of linear queue in which the last position is connected to the first position of the list. The circular queue is similar to linear queue has two ends, the front end and the rear end. The rear end is where we insert elements and front end is where we delete elements. We can traverse in a circular queue in only one direction ie) from front to rear.

    22. Double-Ended-Queue – Another form of queue in which insertions and deletions are made at both the front and rear ends of the queue.

    23. Question 74. Difference Between Abstract Data Type, Data Type And Data Structure?
    24. Answer :An Abstract data type is the specification of the data type which specifies the logical and mathematical model of the data type.
    25. A data type is the implementation of an abstract data type.
    26. Data structure refers to the collection of computer variables that are connected in some specific manner.
    27. i.e) Data type has its root in the abstract data type and a data structure comprises a set of computer variables of same or different data types.


    28. Question 75. State The Difference Between Queues And Linked Lists?
    29. Answer :The difference between queues and linked lists is that insertions and deletions may occur anywhere in the linked list, but in queues insertions can be made only in the rear end and deletions can be made only in the front end.

कोई टिप्पणी नहीं:

एक टिप्पणी भेजें