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

Stack

Image
A stack is a fundamental data structure in computer science and programming that follows the Last-In, First-Out (LIFO) principle . It is named "stack" because it resembles a stack of items, like a stack of plates or books, where you can only add or remove items from the top. Stacks are used for various purposes in programming and are essential in many algorithms and applications. Let's delve into the details of stacks: Key Operations:  A stack typically supports two primary operations: Push: This operation adds an element to the top of the stack. It is analogous to placing an item on top of the stack. Pop: This operation removes and returns the top element of the stack. It is like taking the top item off the stack. Additionally, stacks often provide the following operations: Peek (or Top): This operation retrieves the top element without removing it. It allows you to examine the top item without modifying the stack. IsEmpty: This operation checks if the stack is empty.
Read more

Quick Sort

Quick sort is a popular sorting algorithm that uses a divide-and-conquer strategy to efficiently sort an array or list. It works by selecting a "pivot" element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. The sub-arrays are then recursively sorted. Here's a detailed algorithm for the Quick Sort algorithm: Algorithm: Quick Sort 1.Choose a pivot element from the array. This can be done in various ways, such as selecting the first element, the last element, or a random element. The choice of the pivot can affect the algorithm's performance. 2,Partition the array into two sub-arrays:     Elements less than the pivot (left sub-array).     Elements greater than the pivot (right sub-array). 3.Recursively apply the Quick Sort algorithm to the left and right sub-arrays. 4.Combine the sorted left sub-array, pivot, and sorted right sub-array to obtain the final sorted ar
Read more