Data Structures using C++-Sem 3-B.C.A-Sep-2019

Name   …………………………… Roll No ……………………….

SAINTGITS COLLEGE OF APPLIED SCIENCES

INTERNAL ASSESSMENT EXAMINATION, SEPTEMBER 2019

Department of  computer applications , Semester 3

DATASTRUCTURE USING C++

Total   : 80 marks                                                                        Time: 3Hours

Section A

Answer any 10 questions. Each question carries 2 marks.

     

1)                 What is FIFO and LIFO?

·         First In First Out-eg:QUEUE

·         Last In First Out-eg:STACK

·         Draw necessary figure

2)                 Define recursion.

·         The process in which a function calls itself directly or indirectly is called recursion and the corresponding function is called as recursive function. Using recursive algorithm, certain problems can be solved quite easily. Examples of such problems are Towers of Hanoi (TOH), Inorder/Preorder/Postorder Tree Traversals, DFS of Graph, et

3)                 Define Data structures. 

·         A data structure is a particular way of organizing data in a computer so that it can be used effectively.

·         Write Example: Array,Stack,Queue,Tree,Graph, etc.

4)                 What is doubly linked list?

·         A doubly linked list is a linked data structure that consists of a set of sequentially linked records called nodes. Each node contains three fields: two link fields (references to the previous and to the next node in the sequence of nodes) and one data field.

·         Figure

5)                 What is Complete binary trees?

·         A full binary tree (sometimes proper binary tree or 2-tree) is a tree in which every node other than the leaves has two children. A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible.

·         Figure

6)                 What you mean by file organization?

·         File Organization refers to the logical relationships among various records that constitute the file, particularly with respect to the means of identification and access to any specific record. In simple terms, Storing the files in certain order is called file Organization.

·         Name  different file organization.

7)                 Define circular queue.

·         Circular Queue is a linear data structure in which the operations are performed based on FIFO (First In First Out) principle and the last position is connected back to the first position to make a circle. It is also called 'Ring Buffer'. In a normal Queue, we can insert elements until queue becomes full.

·         figure

8)                 What is an algorithm?

·         An algorithm is a procedure or formula for solving a problem, based on conducting a sequence of specified actions. A computer program can be viewed as an elaborate algorithm.

·         Simple example

9)                 Define Binary tree?

·         A tree whose elements have at most 2 children is called a binary tree. Since each element in a binary tree can have only 2 children,  the left and right child.

·         figure

10)             Define Sparse matrix.

·         Sparse matrix is a matrix which contains very few non-zero elements.

·         example

11)             What is garbage collection?

·         Garbage collection (GC) is a form of automatic memory management. The garbage collector, or just collector, attempts to reclaim garbage, or memory occupied by objects that are no longer in use by the program.

12)             List different sorting techniques.

·         Bubble sort, insertion sort, merge sort, selection sort, quick sort

                                                                                                                    (10x2=20)

                                                    Section B

Answer any six of the following. Each question carries 5 marks.

13)             What are different applications of stacks?

·         Expression Evaluation

·         Expression Conversion

·         Backtracking

·         String Reversal

·         Explanation

14)             Differentiate sparse and dense matrix.

·         Dense matrices store every entry in the matrix. Sparse matrices only store the nonzero entries.

·         Example and explanation

15)             Explain different types of linkedlists.

·         Singly,Doubly,Circular,Circular doubly  Linked list.

·         Figure with Explanation.

16)             What are different file operations.

·         File Create operation.

·         File Delete operation.

·         File Open operation.

·         File Close operation.

·         File Read operation.

·         File Write operation.

·         File Append operation.

·         File Seek operation.

17)             Write advantages and disadvantages of doubly linkedlist.

·         Advantages over singly linked list

·         1) A DLL can be traversed in both forward and backward direction.

·         2) The delete operation in DLL is more efficient if pointer to the node to be deleted is given.

·         3) We can quickly insert a new node before a given node.

·         In singly linked list, to delete a node, pointer to the previous node is needed. To get this previous node, sometimes the list is traversed. In DLL, we can get the previous node using previous pointer.

·         Disadvantages over singly linked list
1) Every node of DLL Require extra space for an previous pointer. It is possible to implement DLL with single pointer though (See this and this).
2) All operations require an extra pointer previous to be maintained. For example, in insertion, we need to modify previous pointers together with next pointers. For example in following functions for insertions at different positions, we need 1 or 2 extra steps to set previous pointer.

18)             Explain different types of queues.

·         Priority queue,circular queue,simple queue,dequeue

·         Figure with explanation

19)             Define root,node,terminal node,degree.

·         Definition with figure

20)             Convert the infix expressionA+B*C/D into postfix.

·         Explain conversion steps (2.5+2.5)

21)             Differentiate linear binary search..

·         Input data needs to be sorted in Binary Search and not in Linear Search

·         Linear search does the sequential access whereas Binary search access data randomly.

·         Time complexity of linear search -O(n) , Binary search has time complexity O(log n).

·          Linear search performs equality comparisons and Binary search performs ordering comparisons

                                                                (6x5=30)

                                        

Section C.

Answer any two of the following.

Each question carries 15 marks

22)             Explain different file organization methods in detail.

·         Sequential ,direct,random,linked etc

·         Figures with explanation

23)             What is binary tree? Explain different traversal methods of Binary tree.

·         Definition (2)

·         Preorder,postorder,inorder algorithm(6)

·         Example  with explanation

24)             Explain different data structures.

·         Array,Stack,Queue,Linked List,Tree,Graph –defintion(8)

·         Figures with explanation(4)

·         Different typoes of Queues and linked list(3)

25)         (i). Explain the terms infix, postfix, prefix notation.(5)

                (ii).Write an algorithm for conversion of infix to postfix conversion.(5)

                (iii). Convert the infix expression to postfix   A+(B*C-(D/E ↑ F)*G)*H(5)

·          

_____________________