Name of the University : Uttarakhand Open University
Degree : M.Sc
Department : Information Technology
Subject Code/Name : MIT2001 Data Structure & Algorithm
Semester : II
Document Type :Model Old Question Paper
Website : uou.ac.in
Download Model/Sample Question Paper : https://www.pdfquestion.in/uploads/uou.ac.in/4630.-MIT-2001.pdf
Data Structure & Algorithm :
M.Sc. IT-10 (Master of Science in Information Technology)
Second Semester Examination 2012
Time : 3 Hour
Max. Marks: 60
Related : Uttarakhand Open University MIT4004 Artificial Intelligence M.Sc Question Bank : www.pdfquestion.in/4644.html
Note : The Question paper has been divided in three Sections – A, B and C. Answers
the Questions as per instructions given in each section.
Section ‘A’
(Long Answer’s Question)
Answer any two questions. Each question carries 15 marks. (2×15=30)
1. What is a data structure? What are the types of data structures? What are the notations of measurement of performance of an algorithm?
2. What is Bubble sort? Write an algorithm for sorting an array of N elements using bubble sort. Sort this array using bubble sort – 15, 18, 4, 5, 2
3. What are the types of linked list? Explain with diagram. Write an algorithm to delete element (node) from “pos” position in linked list.
4. Define the properties of complete binary tree. Create a tree from given orders of traversal pre-order = {11, 5, 3, 8, 16, 14, 18, 17, 20} in-order = {3, 5, 8, 11, 14, 16, 17, 18, 20}.
Section ‘B’
(Short Answer’s Question)
MIT-2001 2
Answer any four questions. Each question carries 5 marks. (4×5=20)
1. What is an array? Write a program to count the elements of array.
2. Write short notes on following
a. Structures
b. Pointers
3. Convert this infix equation to postfix using stack – (A+B^D)/(E-F) +G
4. Write algorithms for PUSH and POP operations of stack using array.
5. What is the difference between sequential (linear) search and binary search? Show the steps of searching element ‘5’ using binary search technique in this array – 2, 5, 8, 15, 20
6. What is Recursion? Write a program to generate Fibonacci series using recursion.
7. Explain malloc (), calloc (), realloc () and free () functions for dynamic memory allocation.
8. Explain megre sort using an example.
Section ‘C’
(Objective Answer’s Question)
Answer all questions. Each question carries 01 mark. (10×1=10)
Write true/false for –
1. Array is a non-linear data structure.
2. Structure is a user defined data type.
3. Big O notation is used to denote worse case complexity
4. In-order traversal of binary tree is always in sorted order.
5. A Complete binary tree with depth 2 can have 9 nodes.
6. Size of pointer is
A) 1 byte B) 2 byte
C) 4 byte D) depends on type of variable whose address it holds
7. Which of the following is not an abstract data type
A) array B) stack C) queue D) pointer
8. Suppose A[10][20] is an integer array. Find out the address
A) 464 B) 282 C) 524 D) 312
9. Queue is based on the concept of
A) LIFO B) FIFO C) FILO D) none
10. Binary search calculates the mid position to search element
Second Semester Examination-2015 :
Data Structure through ‘C’ Language :
Time : 3 Hours
Maximum Marks : 60
Note : This paper is of sixty (60) marks divided into three (03) sections A, B, and C. Attempt the questions contained in these sections according to the detailed instructions given therein.
Section – A : (Long Answer Type Questions)
Note : Section ‘A’ contains four (04) long-answer-type questions of fifteen (15) marks each. Learners are required to answer any two (02) questions only. (2×15=30)
1. (a) Write a complete programme in C to create a single linked list. Write functions to do the following operations (10)
(i) Insert a new node at the end
(ii) Delete the first node
(b) Explain the bubble sort method. (5)
2. (a) What do you understand by tree traversal ? Write a procedure for traversing a binary tree in pre-order and execute it on the following tree. (10)
(b) Define the following terms using suitable examples. (5)
(i) Degree of Tree.
(ii) Height of Tree
(iii) Siblings
(iv) A Full binary Tree
(v) A Complete Binary Tree
3. (a) What is circular queue? Write down routines for inserting and deleting elements from a circular queue implemented using arrays. (10)
(b) What is a binary search tree? List its advantages. (5)
4. (a) Show the detailed contents of stack for a given postfix expression 623 +- 382 / +*2 & 3 + and evaluate the expression. (10)
(b) Explain the working of a Deques. (5)
Section – B : (Short Answer Type Questions)
Note : Section ‘B’ contains eight (08) short-answer-type questions of five (05) marks each. Learners are required to answer any four (04) questions only. (4×5=20)
1. State the need of Data Structures
2. Define the terms node, address, null pointer and next pointer for linked list.
3. Discuss the following terms :
(i) Connected graph
(ii) Disconnected graph
4. Define data type and abstract data type. Comment upon the significance of abstract data type.
5. What are the applications of stack.
6. Suppose an array arr[15] stores numeric values only, write algorithms to
(i) Calculate the average of the values in arr.
(ii) Print the even numbers stored in arr.
7. Compare linear linked list and double linked list with diagrams.
8. Write a short note on dynamic memory allocation.