Model Question Paper-Data Structures CST 201 KTU

 Model Question Paper

QP CODE: PAGES:3

Reg No:_______________

Name:_________________

APJ ABDUL KALAM TECHNOLOGICAL UNIVERSITY THIRD SEMESTER B.TECH

DEGREE EXAMINATION, MONTH & YEAR

Course Code: CST 201

Course Name: DATA STRUCTURES

Max.Marks:100 Duration: 3 Hours

PART A

Answer all Questions. Each question carries 3 Marks

1. Calculate the frequency count of the statement x = x+1; in the following code segment

for (i = 0; i< n; i++)

for (j = 0; j< n; j*=2)

x = x + 1;

2. What is the relevance of verification in System Life Cycle?

3. Write an algorithm to insert a new element in a particular position of an array.

4. Convert the expression ((A/(B-D+E))*(F-G)*H) to postfix form. Show each step in the conversion including the stack contents

5. Write an algorithm to count the number of occurrences of a character in a linked list (each node contains only one character)

6. Write an algorithm for best-fit method of memory allocation

7. Draw the binary tree whose sequential representation is given below

8. Find the Depth First Search of the following Graph

9. Write an algorithm to arrange n numbers in nonincreasing order.

10. Let the size of a hash table is 10. The index of the hash table varies from 0 to 9. Assume the keys 73, 54, 15, 48, 89, 66, 37, 18, 41, 22, 62 are mapped using modulo operator.

Show how the keys are distributed using chaining method.

1 2 3  4 5 6 7 8 9 10 11 12 13 14 15

A B C - D E - - - -      F G   -  -  -

8. Find the Depth First Search of the following Graph


9. Write an algorithm to arrange n numbers in nonincreasing order.

10. Let the size of a hash table is 10. The index of the hash table varies from 0 to 9. Assume

the keys 73, 54, 15, 48, 89, 66, 37, 18, 41, 22, 62 are mapped using modulo operator.

Show how the keys are distributed using chaining method.

Part B

Answer any one Question from each module. Each question carries 14 Marks

11. a) Explain the System Life Cycle in detail (10)

b) How the performance of an algorithm is evaluated? (4)

OR

12. a) Write algorithms for Linear Search and Binary Search and Compare their time

complexities (10)

b) Between O(nlogn) and O(logn) which one is better and why? (4)


13. a) Write algorithms to insert and delete elements from a double ended queue.

Demonstrate with examples (10)

b) Compare and contrast Circular Queue with a Normal Queue (4)

OR

14. a) Write an algorithm to insert and delete elements from a Priority Queue (8)

b) Discuss an algorithm to convert an infix expression to a prefix expression (6)


15. a) Write an algorithm to multiply two polynomials represented using linked list (10)

b) How doubly linked list can be used to find palindromes ? (4)

OR

16. a) How is memory compaction (de-allocation) done in memory management ? (8)

b) Discuss the advantages and disadvantages of First-fit, Best-fit and Worst-fit allocation

schemes (6)


17. a) List the properties of Binary Search Tree. Write an algorithm to search an element

from a Binary Search Tree (10)

b) Write an iterative algorithm for in-order traversal of a Binary Tree (4)

OR

18. a) Give algorithms for DFS and BFS of a graph and explain with examples (8)

b) How graphs can be represented in a Computer? (6)


19. a) Write algorithms for Merge sort and Quick Sort. (10)

b) Illustrate the working of Quick sort on the following input 38, 8, 0, 28, 45, -12, 89, 66,

42 (4)

OR

20. a) With examples discuss the different hash functions used for hashing (10)

b) Apply the hash function h(x) = x mod 7 for linear probing on the data 2341, 4234,

2839, 430, 22, 397, 3920 and show the resulting hash table (4)

Comments

Post a Comment

Popular posts from this blog

Data Structures CST 201 KTU Third Semester Syllabus Notes and Solved Questions- Dr Binu V P 984739060

Dr BinuV P -About Me About The Course Syllabus Data Structures Lab CSL 201 ( Do the Programs to Understand the Concept Well) Model Question Paper CST 201 Data Structures University Question Papers CST 201 Data Structures Module-1 Basic Concepts of Data Structures 1.1 System Life Cycle 1.2 Algorithms , Performance Analysis  1.3 Space Complexity, Time Complexity  1.4 Asymptotic Analysis and Notations  1.5 Complexity Calculation of Simple Algorithms Module-2 Arrays and Searching  2.1 Polynomial representation using Arrays  2.2 Sparse matrix  2.3 Stacks  2.4 Queues 2.5 Circular Queues  2.6 Priority Queues 2.7 Double Ended Queues 2.8 Infix to  Postfix Conversion  2.9  Evaluation of Postfix Expression 2.10 Linear Search  2.11 Binary Search Module-3 Linked List and Memory Management 3.1 Linked List -Self Referential Structures  3.2 Dynamic Memory Allocation  3.3 Singly Linked List-Operations on Linked List 3.4 Doubly Linked List 3.5 Circular Linked List  3.6 Stack using Linked List  3.7 Queue
Read more

Depth First Search DFS

Image
Depth-First Search (DFS) is a fundamental graph traversal algorithm that explores as far as possible along each branch before backtracking. It's often used to explore and analyze the connectivity of graphs, find paths, and solve problems related to connected components. Algorithm: The DFS algorithm operates on a graph, starting from an initial vertex. It maintains a stack (or uses recursion) to keep track of the vertices to visit. Initialization: Create a boolean array to mark visited vertices. Initialize all vertices as not visited. DFS Function: Choose a starting vertex (if the graph is disconnected, this process is repeated for unvisited vertices). Mark the chosen vertex as visited. Explore the chosen vertex's neighbours: If a neighbour is not visited, recursively call the DFS function on that neighbour. Repeat until all reachable vertices are visited. Here's a simplified recursive implementation in pseudocode: procedure DFS(vertex): mark vertex as visited for ea
Read more

Binary Search Tree ( BST) and operations

Image
A binary search tree (BST) is a data structure that organizes elements in a hierarchical structure, allowing for efficient search, insertion, and deletion operations. Here are the key properties and operations associated with a binary search tree: Properties of a Binary Search Tree: Binary Tree Structure:      Each node in the tree has at most two children: a left child and a right child.      The left subtree of a node contains only nodes with values less than the node's value.      The right subtree of a node contains only nodes with values greater than the node's value. Ordering Property:      For any node n , all nodes in its left subtree have values less than n, and all nodes in its right subtree           have values greater than n . No Duplicates:     A binary search tree does not allow duplicate values. Example: Figure  shows a binary search tree. Notice that this tree is obtained by inserting the values 13, 3, 4, 12, 14, 10, 5, 1, 8, 2, 7, 9, 11, 6, 18 in that order,
Read more