Jump to Year/Set
2023 2023 (V2)2022 2022 (V4)2021 2020 2020 (V4)2020 2020 (SPECIAL)2019 2019 2019 (V4)2017 2016 2015
2023 100304

B.Tech. 3rd Semester Examination, 2023

Time 03 Hours
Full Marks 70
Instructions:
  • The marks are indicated in the right-hand margin.
  • There are NINE questions in this paper.
  • Attempt FIVE questions in all.
  • Question No. 1 is compulsory.

Q.1 Choose the correct answer of the following (Any seven question only):

Q1.1

What is the time complexity of the following code snippet?

for(i=0; i<n; i++) {
    for(j=0; j<i; j++) {
        int sum = i + j;
    }
}
a)

O(n)O(n)

b)

O(n2)O(n^2)

c)

O(logn)O(log n)

d)

O(1)O(1)

Q1.2

Which type of traversal of binary search tree outputs the value in sorted order?

a)

Pre-order

b)

In-order

c)

Post-order

d)

None of the above

Q1.3

Suppose a circular queue of capacity $ (n-1) $ elements is implemented with an array of n elements. Assume that the insertion and deletion operations are carried out using REAR and FRONT as array index variables, respectively. Initially, REAR=FRONT=0. The conditions to detect queue full and queue empty are

a)

Full: FRONT = (REAR-1) mod n. Empty: REAR=FRONT

b)

Full: FRONT = (REAR+1) mod n. Empty: REAR=(FRONT+1) mod n

c)

Full: REAR = FRONT. Empty: FRONT = (REAR+1) mod n

d)

Full: REAR = (FRONT+1) mod n. Empty: REAR=FRONT

Q1.4

Which of the following data structures can be used for parentheses matching?

a)

Tree

b)

Queue

c)

Stack

d)

Priority queue

Q1.5

What is the worst-case time complexity of inserting n elements into an empty linked list, if the linked list needs to be maintained in sorted order?

a)

Θ(n)\Theta(n)

b)

Θ(nlogn)\Theta(n log n)

c)

Θ(n2)\Theta(n^2)

d)

Θ(1)\Theta(1)

Q1.6

What will be the postfix expression for the given infix expression: $ (a+b)*c-d $

a)

*+abcd

b)

ab+c*d-

c)

ab+cd-*

d)

abc*+d-

Q1.7

What is the outcome of the prefix expression + - * 3 2 / 8 4 1 ?

a)

12

b)

11

c)

5

d)

4

Q1.8

Where will the new element be inserted in the linked list implementation of the queue?

a)

At the middle position of the linked list

b)

At the head position of the linked list

c)

At the tail position of the linked list

d)

None of the above

Q1.9

Let us consider a list of numbers (34, 16, 2, 93, 80, 77, 51) and a hash table size of 10. What is the order of elements (from index 0 to size-1) in the hash table?

a)

null, null, 77, 16, null, 34, 93, 2, 51, 80

b)

80, 51, 2, 93, 34, null, 16, 77, null, null

c)

77, 16, 34, 93, 2, 51, 80

d)

80, 51, 2, 93, 34, 16, 77

Q1.10

The height of a binary tree is the maximum number of edges in any root to leaf path. The maximum number of nodes in a binary tree of height h is:

a)

2h−12^h-1

b)

2h−1−12^{h-1}-1

c)

2h+1−12^{h+1}-1

d)

2h+12^{h+1}

Q.2 Solve both questions :

Q2.1

Why do we need an asymptotic notation? Explain the different asymptotic notations with definitions and examples.

Q2.2

Write the worst-case run time complexity of the following algorithms: linear search, bubble sort, merge sort, and push operation in the stack.

Q.3 Solve both questions :

Q3.1

Write push() and pop() functions of a stack.

Q3.2

Evaluate the following postfix expression using STACK. Show all the steps. 8, 2, /, 3, *, 4, -, 6, 2, /, +

Q.4 Solve both questions :

Q4.1

Write the algorithm to count the total elements in a singly linked list.

Q4.2

How a doubly linked list is better than a singly linked list? Explain deletion on a doubly linked list using an example.

Q.5 Solve both questions :

Q5.1

The following values are to be stored in a hash table: 25, 42, 96, 101, 102, 162, 197. Describe how the values are hashed by using the division method of hashing with a table size of 7. Use chaining as the method of collision resolution.

Q5.2

Apply the merge sort on the following numbers: 10, 15, 50, 17, 20, 25, 30, 16, 70, 6.

Q.6 Solve both questions :

Q6.1

Differentiate between stack and queue. Explain different types of queues with examples.

Q6.2

Write the properties of a binary search tree. Create a binary search tree using the following elements: 45, 15, 79, 90, 10, 55, 12, 20, 50.

Q.7 Solve both questions :

Q7.1

Consider the in-order and pre-order traversal of a binary search tree are (1, 2, 3, 4, 5, 6, 8, 10, 25) and (4, 3, 1, 2, 10, 8, 5, 6, 25) respectively. Construct a unique binary search tree for the given in-order and pre-order traversals.

Q7.2

Explain the insertion in the AVL tree using an example.

Q.8 Solve this question :

Q8.1

Explain the Heap sort algorithm. Create a heap for the following elements and then sort them: 13, 102, 405, 136, 15, 105, 390, 432, 28, 444.

Q.9 Write the short note on the following:

Q9.1
a)

Circular Queue

b)

Adjacency matrix

c)

Depth first search

d)

B tree

2023 V2 100304

B.Tech. 3rd Semester Examination, 2023

Time 03 Hours
Full Marks 70
Instructions:
  • The marks are indicated in the right-hand margin.
  • There are NINE questions in this paper.
  • Attempt FIVE questions in all.
  • Question No. 1 is compulsory.

Q.1 Choose the correct answer of the following (Any seven question only):

Q1.1

What is the time complexity of the following code snippet?

a)

O(n)O(n)

b)

O(n2)O(n^2)

c)

O(logn)O(log n)

d)

O(1)O(1)

Q1.2

Which type of traversal of binary search tree outputs the value in sorted order?

a)

Pre-order

b)

In-order

c)

Post-order

d)

None of the above

Q1.3

Suppose a circular queue of capacity (n−1)(n-1) elements is implemented with an array of n elements. Assume that the insertion and deletion operations are carried out using REAR and FRONT as array index variables, respectively. Initially, REAR=FRONT=0. The conditions to detect queue full and queue empty are

a)

Full: FRONT = (REAR-1) mod n. Empty: REAR=FRONT

b)

Full: FRONT = (REAR+1) mod n. Empty: REAR=(FRONT+1) mod n

c)

Full: REAR = FRONT. Empty: FRONT = (REAR+1) mod n

d)

Full: REAR = (FRONT+1) mod n. Empty: REAR=FRONT

Q1.4

Which of the following data structures can be used for parentheses matching?

a)

Tree

b)

Queue

c)

Stack

d)

Priority queue

Q1.5

What is the worst-case time complexity of inserting n elements into an empty linked list, if the linked list needs to be maintained in sorted order?

a)

Θ(n)\Theta(n)

b)

Θ(nlogn)\Theta(n log n)

c)

Θ(n2)\Theta(n^2)

d)

Θ(1)\Theta(1)

Q1.6

What will be the postfix expression for the given infix expression: (a+b)∗c−d(a+b)*c-d

a)

*+abcd

b)

ab+c*d-

c)

ab+cd-*

d)

abc*+d-

Q1.7

What is the outcome of the prefix expression + - * 3 2 / 8 4 1 ?

a)

12

b)

11

c)

5

d)

4

Q1.8

Where will the new element be inserted in the linked list implementation of the queue?

a)

At the middle position of the linked list

b)

At the head position of the linked list

c)

At the tail position of the linked list

d)

None of the above

Q1.9

Let us consider a list of numbers (34, 16, 2, 93, 80, 77, 51) and a hash table size of 10. What is the order of elements (from index 0 to size-1) in the hash table?

a)

null, null, 77, 16, null, 34, 93, 2, 51, 80

b)

80, 51, 2, 93, 34, null, 16, 77, null, null

c)

77, 16, 34, 93, 2, 51, 80

d)

80, 51, 2, 93, 34, 16, 77

Q1.10

The height of a binary tree is the maximum number of edges in any root to leaf path. The maximum number of nodes in a binary tree of height h is:

a)

2h−12^h-1

b)

2h−1−12^{h-1}-1

c)

2h+1−12^{h+1}-1

d)

2h+12^{h+1}

Q.2 Solve both questions :

Q2.1

Why do we need an asymptotic notation? Explain the different asymptotic notations with definitions and examples.

Q2.2

Write the worst-case run time complexity of the following algorithms: linear search, bubble sort, merge sort, and push operation in the stack.

Q.3 Solve both questions :

Q3.1

Write push() and pop() functions of a stack.

Q3.2

Evaluate the following postfix expression using STACK. Show all the steps. 8, 2, /, 3, *, 4, -, 6, 2, /, +

Q.4 Solve both questions :

Q4.1

Write the algorithm to count the total elements in a singly linked list.

Q4.2

How a doubly linked list is better than a singly linked list? Explain deletion on a doubly linked list using an example.

Q.5 Solve both questions :

Q5.1

The following values are to be stored in a hash table: 25, 42, 96, 101, 102, 162, 197. Describe how the values are hashed by using the division method of hashing with a table size of 7. Use chaining as the method of collision resolution.

Q5.2

Apply the merge sort on the following numbers: 10, 15, 50, 17, 20, 25, 30, 16, 70, 6.

Q.6 Solve both questions :

Q6.1

Differentiate between stack and queue. Explain different types of queues with examples.

Q6.2

Write the properties of a binary search tree. Create a binary search tree using the following elements: 45, 15, 79, 90, 10, 55, 12, 20, 50.

Q.7 Solve both questions :

Q7.1

Consider the in-order and pre-order traversal of a binary search tree are (1, 2, 3, 4, 5, 6, 8, 10, 25) and (4, 3, 1, 2, 10, 8, 5, 6, 25) respectively. Construct a unique binary search tree for the given in-order and pre-order traversals.

Q7.2

Explain the insertion in the AVL tree using an example.

Q.8 Solve this question :

Q8.1

Explain the Heap sort algorithm. Create a heap for the following elements and then sort them: 13, 102, 405, 136, 15, 105, 390, 432, 28, 444.

Q.9 Write the short note on the following:

Q9.1
  • Circular Queue
  • Adjacency matrix
  • Depth first search
  • B tree
a)

Circular Queue

b)

Adjacency matrix

c)

Depth first search

d)

B tree

2022 100304

End Semester Examination - 2022

Time 03 Hours
Full Marks 70
Instructions:
  • The marks are indicated in the right-hand margin.
  • There are NINE questions in this paper.
  • Attempt FIVE questions in all.
  • Question No. 1 is compulsory.

Q.1 Choose the correct answer of the following (Any seven question only):

Q1.1

In a stack, if a user tries to remove an element from empty stack it is called:

a)

underflow

b)

empty collection

c)

garbage collection

d)

overflow

Q1.2

Consider the binary max-heap implemented using an array. Which one of the following array represents the heap:

a)

25, 12, 16, 13, 10, 8, 14

b)

25, 12, 16, 13, 10, 8, 14

c)

25, 14, 16, 13, 10, 8, 12

d)

25, 14, 12, 13, 10, 8, 16

Q1.3

A hash function is defined as h(key) = key mod 7, with linear probing used to insert keys 44, 45, 79, 55, 91, 18, 63 into a table indexed from 0 to 6. What will be the location of key 18?

a)

3

b)

4

c)

5

d)

6

Q1.4

If the number of values to be sorted is already partially sorted, then ______ sorting can be efficient.

a)

merge

b)

insertion

c)

bubble

d)

selection

Q1.5

The time complexity of merge sort is:

a)

O(n)O(n)

b)

O(log⁡n)O(\log n)

c)

O(nlog⁡n)O(n\log n)

d)

O(n2)O(n^2)

Q1.6

State true or false: A: Binary search is used for searching in a sorted array. B: The time complexity of binary search is $ O(\log n) $.

a)

True, False

b)

False, True

c)

False, False

d)

True, True

Q1.7

In a circular linked list organization, insertion of a record involves modification of:

a)

One pointer

b)

Two pointers

c)

More than two pointers

d)

No pointer

Q1.8

Level order traversal of a rooted tree can be done by starting from the root and performing:

a)

pre-order traversal

b)

in-order traversal

c)

depth first search

d)

breadth first search

Q1.9

An Abstract Data Type (ADT) is:

a)

same as an abstract class

b)

a data type that cannot be instantiated

c)

a data type for which only the operations defined on it can be used, but none else

d)

all of the above

Q1.10

How many distinct BSTs can be constructed with 3 distinct keys?

a)

4

b)

5

c)

6

d)

7

Q.2 Solve both questions :

Q2.1

Explain different asymptotic notations (Big-O, $ \Omega $, $ \Theta $) used for comparing the time complexity of an algorithm with neat figures.

Q2.2

The run time of an algorithm is represented by the recurrence relation $ T(n) = 2T(n/2) + n $; $ n \ge 2 $ and with boundary condition $ T(1) = 0 $. What is the time complexity (in terms of $ \Theta $ notation).

Q.3 Solve both questions :

Q3.1

Discuss pre-order, in-order and post-order traversal techniques of binary tree. Write a C function for non-recursive pre-order traversal.

Q3.2

The pre-order traversal sequence of a Binary Search Tree (BST) is 30, 20, 10, 15, 25, 23, 39, 35, 42. Write step by step process to derive the BST and find post-order traversal also.

Q.4 Solve both questions :

Q4.1

Consider a circular queue of capacity n-elements implemented with an array. Write C functions for insertion and deletion operations.

Q4.2

Convert the given infix expression into postfix using stack: $ A + B / C * (D + E) - F $. For each input symbol clearly mention the action taken and status of the stack during conversion.

Q.5 Solve both questions :

Q5.1

Write a C function to delete last node from a singly linked list.

Q5.2

Create a max-heap by inserting following keys in the given order. Show each insertion step with clear illustration: 25, 35, 18, 9, 46, 70, 48.

Q.6 Solve both questions :

Q6.1

Write an algorithm for merge sort and discuss space and time complexity.

Q6.2

Define collision in hashing. Explain briefly different methodologies to resolve collision.

Q.7 Solve both questions :

Q7.1

Write algorithm to count leaf nodes in binary tree. What is the complexity of your algorithm?

Q7.2

Compare BFS and DFS traversal techniques for graph. Write an algorithm to perform BFS using queue.

Q.8 Solve both questions :

Q8.1

Differentiate between system defined data types and abstract data types with suitable examples.

Q8.2

What is doubly linked list? What are its applications? Explain how a node can be added as last node using appropriate pseudo code.

Q.9 Write short notes on any two of the following:

Q9.1

AVL Rotations

Q9.2

Open Addressing & Chaining

Q9.3

B-Tree

Q9.4

Priority Queue

2022 V4 100304

End Semester Examination - 2022

Time 03 Hours
Full Marks 70
Instructions:
  • The marks are indicated in the right-hand margin.
  • There are NINE questions in this paper.
  • Attempt FIVE questions in all.
  • Question No. 1 is compulsory.

Q.1 Choose the correct answer of the following (Any seven question only):

Q1.1

In a stack, if a user tries to remove an element from empty stack it is called:

a)

underflow

b)

empty collection

c)

garbage collection

d)

overflow

Q1.2

Consider the binary max-heap implemented using an array. Which one of the following array represents the heap:

a)

25, 12, 16, 13, 10, 8, 14

b)

25, 12, 16, 13, 10, 8, 14

c)

25, 14, 16, 13, 10, 8, 12

d)

25, 14, 12, 13, 10, 8, 16

Q1.3

A hash function is defined as h(key) = key mod 7, with linear probing used to insert keys 44, 45, 79, 55, 91, 18, 63 into a table indexed from 0 to 6. What will be the location of key 18?

a)

3

b)

4

c)

5

d)

6

Q1.4

If the number of values to be sorted is already partially sorted, then ______ sorting can be efficient.

a)

merge

b)

insertion

c)

bubble

d)

selection

Q1.5

The time complexity of merge sort is:

a)

O(n)O(n)

b)

O(log⁡n)O(\log n)

c)

O(nlog⁡n)O(n\log n)

d)

O(n2)O(n^2)

Q1.6

State true or false: A: Binary search is used for searching in a sorted array. B: The time complexity of binary search is $ O(\log n) $.

a)

True, False

b)

False, True

c)

False, False

d)

True, True

Q1.7

In a circular linked list organization, insertion of a record involves modification of:

a)

One pointer

b)

Two pointers

c)

More than two pointers

d)

No pointer

Q1.8

Level order traversal of a rooted tree can be done by starting from the root and performing:

a)

pre-order traversal

b)

in-order traversal

c)

depth first search

d)

breadth first search

Q1.9

An Abstract Data Type (ADT) is:

a)

same as an abstract class

b)

a data type that cannot be instantiated

c)

a data type for which only the operations defined on it can be used, but none else

d)

all of the above

Q1.10

How many distinct BSTs can be constructed with 3 distinct keys?

a)

4

b)

5

c)

6

d)

7

Q.2 Solve both questions :

Q2.1

Explain different asymptotic notations (Big-O, $ \Omega $, $ \Theta $) used for comparing the time complexity of an algorithm with neat figures.

Q2.2

The run time of an algorithm is represented by the recurrence relation $ T(n) = 2T(n/2) + n $; $ n \ge 2 $ and with boundary condition $ T(1) = 0 $. What is the time complexity (in terms of $ \Theta $ notation).

Q.3 Solve both questions :

Q3.1

Discuss pre-order, in-order and post-order traversal techniques of binary tree. Write a C function for non-recursive pre-order traversal.

Q3.2

The pre-order traversal sequence of a Binary Search Tree (BST) is 30, 20, 10, 15, 25, 23, 39, 35, 42. Write step by step process to derive the BST and find post-order traversal also.

Q.4 Solve both questions :

Q4.1

Consider a circular queue of capacity n-elements implemented with an array. Write C functions for insertion and deletion operations.

Q4.2

Convert the given infix expression into postfix using stack: $ A + B / C * (D + E) - F $. For each input symbol clearly mention the action taken and status of the stack during conversion.

Q.5 Solve both questions :

Q5.1

Write a C function to delete last node from a singly linked list.

Q5.2

Create a max-heap by inserting following keys in the given order. Show each insertion step with clear illustration: 25, 35, 18, 9, 46, 70, 48.

Q.6 Solve both questions :

Q6.1

Write an algorithm for merge sort and discuss space and time complexity.

Q6.2

Define collision in hashing. Explain briefly different methodologies to resolve collision.

Q.7 Solve both questions :

Q7.1

Write algorithm to count leaf nodes in binary tree. What is the complexity of your algorithm?

Q7.2

Compare BFS and DFS traversal techniques for graph. Write an algorithm to perform BFS using queue.

Q.8 Solve both questions :

Q8.1

Differentiate between system defined data types and abstract data types with suitable examples.

Q8.2

What is doubly linked list? What are its applications? Explain how a node can be added as last node using appropriate pseudo code.

Q.9 Write short notes on any two of the following:

Q9.1

AVL Rotations

Q9.2

Open Addressing & Chaining

Q9.3

B-Tree

Q9.4

Priority Queue

2021 100304

B.Tech Examination, 2021

Time 3 hours
Full Marks 70
Instructions:
  • The marks are indicated in the right-hand margin.
  • There are NINE questions in this paper.
  • Attempt FIVE questions in all.
  • Question No. 1 is compulsory.

Questions

Q1

Choose the correct answer of the following (any seven) :

Q2

Answer the following:

Q3

Answer the following:

Q4

Insert the following numbers, in the given sequence, in an empty B tree of order 5 and display the tree at every split : 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1. Now delete the following elements from the tree, in the given sequence, and display the tree at every merge.

[14 Marks]
Q5

Insert the following numbers, in the given sequence, in an empty B+ tree of order 3 and display the tree at every split : 10, 20, 30, 90, 80, 60, 70, 40, 50, 66, 16, 84, 21, 76. Now delete the following elements from the tree, in the given sequence, and display the tree at every merge.

[14 Marks]
Q6

Answer the following:

Q7

Differentiate between the following :

Q8

Explain in detail the Kruskal's and Prim's algorithms for constructing minimum spanning tree. For the weighted undirected graph given below, construct the minimum cost spanning tree for the given graph using Kruskal's algorithm and Prim's algorithm when the starting vertex is R1 :

[14 Marks]
Q9

Define the following :

2020 100304

B.Tech 3rd Semester Exam., 2020 (New Course)

Time 03 Hours
Full Marks 70
Instructions:
  • The marks are indicated in the right-hand margin.
  • There are NINE questions in this paper.
  • Attempt FIVE questions in all.
  • Question No. 1 is compulsory.

Q.1 Choose the correct answer of the following (any seven):

Q1.1

Which of the following is time complexity of the given code?
$ int\ a=0; $
$ for(i=0; i< N; i++) \{ $
$ \quad for(j=N; j>i; j--) \{ $
$ \quad \quad a = a + i + j; $
$ \quad \} $
$ \} $

a)

O(N)O(N)

b)

O(N∗log⁡(N))O(N * \log(N))

c)

O(N∗N)O(N * \sqrt{N})

d)

O(N∗N)O(N * N)

Q1.2

Which of the following is time complexity of the given code?
$ int\ i,\ j,\ k=0; $
$ for(i=n/2; i<=n; i++) \{ $
$ \quad for(j=2; j<=n; j=j*2) \{ $
$ \quad \quad k = k + n/2; $
$ \quad \} $
$ \} $

a)

O(N)O(N)

b)

O(N∗log⁡(N))O(N * \log(N))

c)

O(N∗N)O(N * \sqrt{N})

d)

O(N∗N)O(N * N)

Q1.3

Which of the following cases does not exist in complexity theory?

a)

Best case

b)

Worst case

c)

Average case

d)

Null case

Q1.4

The operation of processing each element in the list is known as

a)

sorting

b)

merging

c)

inserting

d)

traversal

Q1.5

Arrays are best data structures

a)

for relatively permanent collections of data

b)

for the size of the structure and the data in the structure are constantly changing

c)

Both (i) and (ii)

d)

None of the above

Q1.6

Each array declaration needs not give, implicitly or explicitly the information about

a)

the name of array

b)

the data type of array

c)

the first data from the set to be stored

d)

the index set of the array

Q1.7

In general, the binary search method needs not more than

a)

[log⁡2n]−1[\log_2 n] - 1

b)

[log⁡n]+1[\log n] + 1

c)

[log⁡2n][\log_2 n]

d)

[log⁡2n]+1[\log_2 n] + 1 comparisons.

Q1.8

State True or False:
A. Binary search is used for searching in a sorted array.
B. The time complexity of binary search is O(logn).

a)

True, False

b)

False, True

c)

False, False

d)

True, True

Q1.9

Which of the following is non-linear data structure?

a)

Stack

b)

Linked list

c)

String

d)

Tree

Q1.10

Which is the correct output for the following sequence of operations? push(5), push(8), pop, push(2), push(5), pop, pop, pop, push(1), pop

a)

85251

b)

85521

c)

82551

d)

81255

Q.2 Solve this question :

Q2.1

Analyse the time complexity of the given function and also write the recurrence relation of the function:
$ int\ DoSomething(int\ n) \{ $
$ \quad if(n<=2)\ return\ 1; $
$ \quad else\ return\ (DoSomething(floor(sqrt(n))) + n); $
$ \} $

Q.3 Solve this question :

Q3.1

Consider the following postfix expression : 873-/6254+*+-
The above expression is evaluated using stack. Show the content of stack after each step.

Q.4 Solve this question :

Q4.1

What are the different notations for comparing the time complexity of an algorithm? Explain each of them with neat figures.

Q.5 Solve this question :

Q5.1

Explain the queue and circular queue with examples. Also, write the differences between the two.

Q.6 Solve this question :

Q6.1

Let a and b be positive integers. Suppose a function F is defined recursively as follows:
$ F(a,b) = \begin{cases} 0 & \text{if } a < b \\ F(a-b,b) + 1 & \text{if } b \le a \end{cases} $
Find the values of the following: (a) $ F(2,3) $ (b) $ F(14,3) $

Q.7 Solve both questions :

Q7.1

Write the algorithm of prefix evaluation with example.

Q7.2

Write prefix notation of the following infix notation: $ A+B*C+D $

Q.8 Solve this question :

Q8.1

What do you mean by ADT? Explain the ADT stack with test cases for both pop and push.

Q.9 Write short notes on the following:

Q9.1

Hashing

Q9.2

Circular linked list

Q9.3

Adjacency list

Q9.4

AVL tree

2020 V4 100304

B.Tech 3rd Semester Exam., 2020 (New Course)

Time 03 Hours
Full Marks 70
Instructions:
  • The marks are indicated in the right-hand margin.
  • There are NINE questions in this paper.
  • Attempt FIVE questions in all.
  • Question No. 1 is compulsory.

Q.1 Choose the correct answer of the following (any seven):

Q1.1

Which of the following is time complexity of the given code?
$ int\ a=0; $
$ for(i=0; i< N; i++) \{ $
$ \quad for(j=N; j>i; j--) \{ $
$ \quad \quad a = a + i + j; $
$ \quad \} $
$ \} $

a)

O(N)O(N)

b)

O(N∗log⁡(N))O(N * \log(N))

c)

O(N∗N)O(N * \sqrt{N})

d)

O(N∗N)O(N * N)

Q1.2

Which of the following is time complexity of the given code?
$ int\ i,\ j,\ k=0; $
$ for(i=n/2; i<=n; i++) \{ $
$ \quad for(j=2; j<=n; j=j*2) \{ $
$ \quad \quad k = k + n/2; $
$ \quad \} $
$ \} $

a)

O(N)O(N)

b)

O(N∗log⁡(N))O(N * \log(N))

c)

O(N∗N)O(N * \sqrt{N})

d)

O(N∗N)O(N * N)

Q1.3

Which of the following cases does not exist in complexity theory?

a)

Best case

b)

Worst case

c)

Average case

d)

Null case

Q1.4

The operation of processing each element in the list is known as

a)

sorting

b)

merging

c)

inserting

d)

traversal

Q1.5

Arrays are best data structures

a)

for relatively permanent collections of data

b)

for the size of the structure and the data in the structure are constantly changing

c)

Both (i) and (ii)

d)

None of the above

Q1.6

Each array declaration needs not give, implicitly or explicitly the information about

a)

the name of array

b)

the data type of array

c)

the first data from the set to be stored

d)

the index set of the array

Q1.7

In general, the binary search method needs not more than

a)

[log⁡2n]−1[\log_2 n] - 1

b)

[log⁡n]+1[\log n] + 1

c)

[log⁡2n][\log_2 n]

d)

[log⁡2n]+1[\log_2 n] + 1 comparisons.

Q1.8

State True or False:
A. Binary search is used for searching in a sorted array.
B. The time complexity of binary search is O(logn).

a)

True, False

b)

False, True

c)

False, False

d)

True, True

Q1.9

Which of the following is non-linear data structure?

a)

Stack

b)

Linked list

c)

String

d)

Tree

Q1.10

Which is the correct output for the following sequence of operations? push(5), push(8), pop, push(2), push(5), pop, pop, pop, push(1), pop

a)

85251

b)

85521

c)

82551

d)

81255

Q.2 Solve this question :

Q2.1

Analyse the time complexity of the given function and also write the recurrence relation of the function:
$ int\ DoSomething(int\ n) \{ $
$ \quad if(n<=2)\ return\ 1; $
$ \quad else\ return\ (DoSomething(floor(sqrt(n))) + n); $
$ \} $

Q.3 Solve this question :

Q3.1

Consider the following postfix expression : 873-/6254+*+-
The above expression is evaluated using stack. Show the content of stack after each step.

Q.4 Solve this question :

Q4.1

What are the different notations for comparing the time complexity of an algorithm? Explain each of them with neat figures.

Q.5 Solve this question :

Q5.1

Explain the queue and circular queue with examples. Also, write the differences between the two.

Q.6 Solve this question :

Q6.1

Let a and b be positive integers. Suppose a function F is defined recursively as follows:
$ F(a,b) = \begin{cases} 0 & \text{if } a < b \\ F(a-b,b) + 1 & \text{if } b \le a \end{cases} $
Find the values of the following: (a) $ F(2,3) $ (b) $ F(14,3) $

Q.7 Solve both questions :

Q7.1

Write the algorithm of prefix evaluation with example.

Q7.2

Write prefix notation of the following infix notation: $ A+B*C+D $

Q.8 Solve this question :

Q8.1

What do you mean by ADT? Explain the ADT stack with test cases for both pop and push.

Q.9 Write short notes on the following:

Q9.1

Hashing

Q9.2

Circular linked list

Q9.3

Adjacency list

Q9.4

AVL tree

2020 PCC-IT-302 (100304)

B.Tech 3rd Semester Special Exam., 2020

Time 03 Hours
Full Marks 70
Instructions:
  • The marks are indicated in the right-hand margin.
  • There are NINE questions in this paper.
  • Attempt FIVE questions in all.
  • Question No. 1 is compulsory.

Q.1 Choose the correct answer of the following (any seven):

Q1.1

If the number of records to be sorted is small, then ______ sorting can be efficient.

a)

merge

b)

heap

c)

selection

d)

bubble

Q1.2

Which of the following is not a limitation of binary search algorithm?

a)

Must be a sorted array

b)

Requirement of sorted array is expensive when a lot of insertions and deletions are needed

c)

There must be a mechanism to access middle element directly

d)

Binary search algorithm is not efficient when the data elements are more than 1500

Q1.3

The complexity of the merge sort is

a)

O(n)O(n)

b)

O(log⁡n)O(\log n)

c)

O(n2)O(n^2)

d)

O(nlog⁡n)O(n\log n)

Q1.4

Which of the following is a hash function?

a)

A function has allocated memory to keys

b)

A function that computes the location of the key in the array

c)

A function that creates an array

d)

A function that computes the location of the values in the array

Q1.5

In simple hashing, what is the search complexity?

a)

O(n)O(n)

b)

O(log⁡n)O(\log n)

c)

O(nlog⁡n)O(n\log n)

d)

O(1)O(1)

Q1.6

In simple chaining, what data structure is appropriate?

a)

Singly linked list

b)

Doubly linked list

c)

Circular linked list

d)

Binary tree

Q1.7

Which is not true about insertion sort?

a)

Exhibits the worst case performance when the initial array is sorted in reverse order

b)

Worst case and average case performance is O(n2)O(n^2)

c)

Can be compared to the way a card player arranges his card from a card deck

d)

None of the above

Q1.8

Which of the below mentioned sorting algorithms is not stable?

a)

Selection sort

b)

Bubble sort

c)

Merge sort

d)

Insertion sort

Q1.9

A pivot element to partition unsorted list is used in

a)

merge sort

b)

bubble sort

c)

selection sort

d)

insertion sort

Q1.10

Which one of the following is divide and conquer approach?

a)

Insertion sort

b)

Merge sort

c)

Shell sort

d)

Heapsort

Q.2 Solve this question :

Q2.1

Write down breadth-first traversal and depth-first traversal of given graph taking 1 as source vertex.

Question Diagram

Q.3 Solve this question :

Q3.1

Construct a B-tree with minimum degree t as 3 and a sequence of integers 10, 20, 30, 40, 50, 60, 70, 80 and 90 in an initially empty B-tree. Show each step.

Q.4 Solve this question :

Q4.1

Write a function to perform merge sort on array of element mentioned. Also write recurrence relation for time complexity of algorithm.

Q.5 Solve this question :

Q5.1

What is AVL tree? Describe deletion operation in AVL tree with example.

Q.6 Solve this question :

Q6.1

Apply bubble sort on given array of integers: 26, 45, 13, 23, 12, 7, 38, 42. Show the content of array after every pass.

Q.7 Solve this question :

Q7.1

Write the algorithm to count leaf node in binary tree and check whether the tree is balanced or not.

Q.8 Solve both questions :

Q8.1

What is hash table? How can we use this structure to find all anagrams in a dictionary?

Q8.2

Write a function that inserts a given element in a binary search tree. If the element is already present, throw an exception 'duplicate value'.

Q.9 Write short notes on the following:

Q9.1

Linear and non-linear data structures

Q9.2

How to implement stack using queue

Q9.3

Heapsort

Q9.4

C++ STL

2020 SPECIAL PCC-IT-302 (100304)

B.Tech 3rd Semester Special Exam., 2020

Time 03 Hours
Full Marks 70
Instructions:
  • The marks are indicated in the right-hand margin.
  • There are NINE questions in this paper.
  • Attempt FIVE questions in all.
  • Question No. 1 is compulsory.

Q.1 Choose the correct answer of the following (any seven):

Q1.1

If the number of records to be sorted is small, then ______ sorting can be efficient.

a)

merge

b)

heap

c)

selection

d)

bubble

Q1.2

Which of the following is not a limitation of binary search algorithm?

a)

Must be a sorted array

b)

Requirement of sorted array is expensive when a lot of insertions and deletions are needed

c)

There must be a mechanism to access middle element directly

d)

Binary search algorithm is not efficient when the data elements are more than 1500

Q1.3

The complexity of the merge sort is

a)

O(n)O(n)

b)

O(log⁡n)O(\log n)

c)

O(n2)O(n^2)

d)

O(nlog⁡n)O(n\log n)

Q1.4

Which of the following is a hash function?

a)

A function has allocated memory to keys

b)

A function that computes the location of the key in the array

c)

A function that creates an array

d)

A function that computes the location of the values in the array

Q1.5

In simple hashing, what is the search complexity?

a)

O(n)O(n)

b)

O(log⁡n)O(\log n)

c)

O(nlog⁡n)O(n\log n)

d)

O(1)O(1)

Q1.6

In simple chaining, what data structure is appropriate?

a)

Singly linked list

b)

Doubly linked list

c)

Circular linked list

d)

Binary tree

Q1.7

Which is not true about insertion sort?

a)

Exhibits the worst case performance when the initial array is sorted in reverse order

b)

Worst case and average case performance is O(n2)O(n^2)

c)

Can be compared to the way a card player arranges his card from a card deck

d)

None of the above

Q1.8

Which of the below mentioned sorting algorithms is not stable?

a)

Selection sort

b)

Bubble sort

c)

Merge sort

d)

Insertion sort

Q1.9

A pivot element to partition unsorted list is used in

a)

merge sort

b)

bubble sort

c)

selection sort

d)

insertion sort

Q1.10

Which one of the following is divide and conquer approach?

a)

Insertion sort

b)

Merge sort

c)

Shell sort

d)

Heapsort

Q.2 Solve this question :

Q2.1

Write down breadth-first traversal and depth-first traversal of given graph taking 1 as source vertex.

Question Diagram

Q.3 Solve this question :

Q3.1

Construct a B-tree with minimum degree t as 3 and a sequence of integers 10, 20, 30, 40, 50, 60, 70, 80 and 90 in an initially empty B-tree. Show each step.

Q.4 Solve this question :

Q4.1

Write a function to perform merge sort on array of element mentioned. Also write recurrence relation for time complexity of algorithm.

Q.5 Solve this question :

Q5.1

What is AVL tree? Describe deletion operation in AVL tree with example.

Q.6 Solve this question :

Q6.1

Apply bubble sort on given array of integers: 26, 45, 13, 23, 12, 7, 38, 42. Show the content of array after every pass.

Q.7 Solve this question :

Q7.1

Write the algorithm to count leaf node in binary tree and check whether the tree is balanced or not.

Q.8 Solve both questions :

Q8.1

What is hash table? How can we use this structure to find all anagrams in a dictionary?

Q8.2

Write a function that inserts a given element in a binary search tree. If the element is already present, throw an exception 'duplicate value'.

Q.9 Write short notes on the following:

Q9.1

Linear and non-linear data structures

Q9.2

How to implement stack using queue

Q9.3

Heapsort

Q9.4

C++ STL

2019 051403

B.Tech Examination, 2019

Time 3 hours
Full Marks 70
Instructions:
  • The marks are indicated in the right-hand margin.
  • There are NINE questions in this paper.
  • Attempt FIVE questions in all.
  • Question No. 1 is compulsory.

Questions

Q1

Answer the following:

a)

Which of the following best describes an array?

a)

A data structure that shows a hierarchical behaviour

b)

Container of objects of similar types

c)

Container of objects of mixed types

d)

All of the above

[2 Marks]
b)

The process of removing an element from stack is called

a)

create

b)

push

c)

evaluation

d)

pop

[2 Marks]
c)

In a stack, if a user tries to remove an element from empty stack it is called

a)

underflow

b)

empty collection

c)

overflow

d)

garbage collection

[2 Marks]
d)

A linear collection of data elements where the linear node is given by means of pointer is called

a)

linked list

b)

node list

c)

primitive list

d)

None of the above

[2 Marks]
e)

What would be the asymptotic time complexity to add a node at the end of singly linked list, if the pointer is initially pointing to the head of the list?

a)

O(1)O(1)

b)

O(n)O(n)

c)

Θ(n)\Theta(n)

d)

Θ(1)\Theta(1)

[2 Marks]
f)

With what data structure can a priority queue be implemented?

a)

Array

b)

List

c)

Heap

d)

All of the above

[2 Marks]
g)

What is the functionality of the following piece of code?

public void fun(int x) {
    q1.offer(x);
}
a)

Perform push() with push as the costlier operation

b)

Perform push() with pop as the costlier operation

c)

Perform pop() with push as the costlier operation

d)

Perform pop() with pop as the costlier operation

[2 Marks]
h)

In a max-heap, element with the greatest key is always in which of the following nodes?

a)

Leaf node

b)

First node of left subtree

c)

Root node

d)

First node of right subtree

[2 Marks]
i)

What is the specialty about the in-order traversal of a binary search tree?

a)

It traverses in a non-increasing order

b)

It traverses in an increasing order

c)

It traverses in a random fashion

d)

None of the above

[2 Marks]
j)

Which of the following is not an application of priority queue?

a)

Huffman codes

b)

Interrupt handling in operating system

c)

Undo operation in text editors

d)

Bayesian spam filter

[2 Marks]
Q2

Answer the following:

a)

Explain array implementation of priority queues and list implementations of priority queues.

[7 Marks]
b)

Differentiate between row major and column major array index notations. How is index calculated in both? Explain your answer by using the example of an integer array a[10][10]a[10][10] and the element a[2][5]a[2][5] is to be accessed.

[7 Marks]
Q3

Answer the following:

a)

What is doubly linked list? What are its applications? Explain how an element can be deleted from the list using appropriate pseudocode.

[7 Marks]
b)

Consider two strings X=x1,x2,…,xnX = x_1, x_2, \dots, x_n and Y=y1,y2,…,ynY = y_1, y_2, \dots, y_n, where xi,1≤i≤nx_i, 1 \le i \le n and yj,1≤j≤my_j, 1 \le j \le m are the members of finite set symbols. Write an algorithm to generate a string by taking 1 element from each list. When any one string is exhausted, the output string should store rest of the elements of other string.

[7 Marks]
Q4

Answer the following:

a)

What do you understand by 'garbage'? Explain how garbage collection method is used for allocating and freeing memory storage.

[7 Marks]
b)

Suppose the following eight numbers are inserted in order into an empty binary search tree: $T : 50, 33, 44, 22, 77, 35, 60, 40$ Draw the tree T.

[7 Marks]
Q5

Answer the following:

a)

Discuss pre-order and post-order tree traversal techniques. Write the pseudo-code for these two traversal methods.

[7 Marks]
b)

Write the algorithms for insertion sort and merge sort with examples and discuss their complexities.

[7 Marks]
Q6

Answer the following:

a)

Write an algorithm to perform breadth first search (BFS). Compare the BFS and DFS search techniques.

[7 Marks]
b)

Explain the working of merge sort on the following data: ${10, 15, 0, 17, 20, 25, 30, 16, 70, 6}$ Show all intermediate steps. Also, mention its time complexity.

[7 Marks]
Q7

Answer the following:

a)

What is meant by a spanning tree of a graph? Give an algorithm to find a spanning tree. What is the complexity of your algorithm?

[7 Marks]
b)

What do you mean by tree traversal? Give a recursive algorithm for tree traversal. Determine the complexity of your algorithm.

[7 Marks]
Q8

Answer the following:

a)

Algorithm A requires n2n^2 days and algorithm B requires n3n^3 sec to solve a problem. Which algorithm would you prefer for a problem instance with n=106n = 10^6?

[7 Marks]
b)

Assume the recurrence relation T(n)=2T(n/2)+n,n≥2T(n) = 2T(n/2) + n, n \ge 2 with boundary condition T(1)=0T(1) = 0. What is the time complexity?

[7 Marks]
Q9

Answer the following:

a)

Write short notes on the following:

[14 Marks]
2019 100304

B.Tech 3rd Semester Exam., 2019 (New Course)

Time 03 Hours
Full Marks 70
Instructions:
  • The marks are indicated in the right-hand margin.
  • There are NINE questions in this paper.
  • Attempt FIVE questions in all.
  • Question No. 1 is compulsory.

Q.1 Choose the correct answer of any seven of the following questions:

Q1.1

Which of the following points is/are true about linked list data structure when it is compared with array?

a)

Arrays have better cache locality that can make them better in terms of performance.

b)

It is easy to insert and delete elements in linked list.

c)

The size of array has to be pre-decided, linked lists can change their size any time.

d)

All of the above

Q1.2

What is the functionality of the following code?
$ public\ void\ function(Node\ node)\ \{ $
$ \quad if(size==0)\ head=node; $
$ \quad else\ \{ $
$ \quad \quad Node\ temp,\ cur; $
$ \quad \quad for(cur=head; (temp=cur.getNext())! $ $=null; cur=temp); $
$ \quad \quad cur.setNext(node); $
$ \quad \} $
$ \quad size++; $
$ \} $

a)

Inserting a node at the beginning of the list

b)

Deleting a node at the beginning of the list

c)

Inserting a node at the end of the list

d)

Deleting a node at the end of the list

Q1.3

What is the space complexity for deleting a linked list?

a)

O(1)O(1)

b)

O(n)O(n)

c)

Either O(1)O(1) or O(n)O(n)

d)

O(log⁡n)O(\log n)

Q1.4

The situation when in a linked list START=NULL is

a)

underflow

b)

overflow

c)

housefull

d)

saturated

Q1.5

What would be the asymptotic time complexity to add a node at the end of singly linked list, if the pointer is initially pointing to the head of the list?

a)

O(1)O(1)

b)

O(n)O(n)

c)

Θ(n)\Theta(n)

d)

Θ(1)\Theta(1)

Q1.6

What kind of linked list is best to answer question like "What is the item at position n"?

a)

Singly linked list

b)

Doubly linked list

c)

Circular linked list

d)

Array implementation of linked list

Q1.7

A variation of linked list is circular linked list, in which the last node in the list points to first node of the list. One problem with this type of list is

a)

it wastes memory space since the pointer head already points to the first node and thus the list node does not need to point to the first node

b)

it is not possible to add a node at the end of the list

c)

it is difficult to traverse the list as the pointer of the last node is now not NULL

d)

All of the above

Q1.8

Each node in a linked list must contain at least

a)

three fields

b)

two fields

c)

four fields

d)

five fields

Q1.9

A linear list in which the last node points to the first node is

a)

singly linked list

b)

circular linked list

c)

doubly linked list

d)

None of the above

Q1.10

In a linked list, insertion can be done at

a)

beginning

b)

end

c)

middle

d)

All of the above

Q.2 Solve this question :

Q2.1

What is a Hash Table, and what is the average case and worst-case time for each of its operations? How can we use this structure to find all anagrams in a dictionary?

Q.3 Solve this question :

Q3.1

Describe insertion in max heap tree with example from the following list of numbers: 33, 42, 67, 23, 44, 49, 74

Q.4 Solve this question :

Q4.1

Sort the given values using quicksort and write time complexity of algorithm: 65, 70, 75, 80, 85, 60, 55, 50, 45

Q.5 Solve both questions :

Q5.1

Insert the following sequence of elements into an AVL tree, starting with an empty tree: 10, 20, 15, 25, 30, 16, 18, 19

Q5.2

Delete 30 in the AVL tree that you got.

Q.6 Solve both questions :

Q6.1

Write algorithm for quicksort and mention time and space complexity in each case.

Q6.2

Define collision in hashing. What are the different methodologies to resolve collision? Explain briefly.

Q.7 Solve this question :

Q7.1

Construct binary search tree and write pre- and post-order traversals of this tree: 8, 3, 1, 10, 6, 14, 4, 7, 13, 22, 5

Q.8 Solve both questions :

Q8.1

Write algorithm to count leaf node in binary tree and check whether tree is balanced or not.

Q8.2

Write a recursive and iterative version of insertion sort algorithm and mention time complexity.

Q.9 Write short notes on the following:

Q9.1

BFS

Q9.2

DFS

Q9.3

Binary search tree

Q9.4

Balance factor

2019 V4 100304

B.Tech 3rd Semester Exam., 2019 (New Course)

Time 03 Hours
Full Marks 70
Instructions:
  • The marks are indicated in the right-hand margin.
  • There are NINE questions in this paper.
  • Attempt FIVE questions in all.
  • Question No. 1 is compulsory.

Q.1 Choose the correct answer of any seven of the following questions:

Q1.1

Which of the following points is/are true about linked list data structure when it is compared with array?

a)

Arrays have better cache locality that can make them better in terms of performance.

b)

It is easy to insert and delete elements in linked list.

c)

The size of array has to be pre-decided, linked lists can change their size any time.

d)

All of the above

Q1.2

What is the functionality of the following code?
$ public\ void\ function(Node\ node)\ \{ $
$ \quad if(size==0)\ head=node; $
$ \quad else\ \{ $
$ \quad \quad Node\ temp,\ cur; $
$ \quad \quad for(cur=head; (temp=cur.getNext())! $ $=null; cur=temp); $
$ \quad \quad cur.setNext(node); $
$ \quad \} $
$ \quad size++; $
$ \} $

a)

Inserting a node at the beginning of the list

b)

Deleting a node at the beginning of the list

c)

Inserting a node at the end of the list

d)

Deleting a node at the end of the list

Q1.3

What is the space complexity for deleting a linked list?

a)

O(1)O(1)

b)

O(n)O(n)

c)

Either O(1)O(1) or O(n)O(n)

d)

O(log⁡n)O(\log n)

Q1.4

The situation when in a linked list START=NULL is

a)

underflow

b)

overflow

c)

housefull

d)

saturated

Q1.5

What would be the asymptotic time complexity to add a node at the end of singly linked list, if the pointer is initially pointing to the head of the list?

a)

O(1)O(1)

b)

O(n)O(n)

c)

Θ(n)\Theta(n)

d)

Θ(1)\Theta(1)

Q1.6

What kind of linked list is best to answer question like "What is the item at position n"?

a)

Singly linked list

b)

Doubly linked list

c)

Circular linked list

d)

Array implementation of linked list

Q1.7

A variation of linked list is circular linked list, in which the last node in the list points to first node of the list. One problem with this type of list is

a)

it wastes memory space since the pointer head already points to the first node and thus the list node does not need to point to the first node

b)

it is not possible to add a node at the end of the list

c)

it is difficult to traverse the list as the pointer of the last node is now not NULL

d)

All of the above

Q1.8

Each node in a linked list must contain at least

a)

three fields

b)

two fields

c)

four fields

d)

five fields

Q1.9

A linear list in which the last node points to the first node is

a)

singly linked list

b)

circular linked list

c)

doubly linked list

d)

None of the above

Q1.10

In a linked list, insertion can be done at

a)

beginning

b)

end

c)

middle

d)

All of the above

Q.2 Solve this question :

Q2.1

What is a Hash Table, and what is the average case and worst-case time for each of its operations? How can we use this structure to find all anagrams in a dictionary?

Q.3 Solve this question :

Q3.1

Describe insertion in max heap tree with example from the following list of numbers: 33, 42, 67, 23, 44, 49, 74

Q.4 Solve this question :

Q4.1

Sort the given values using quicksort and write time complexity of algorithm: 65, 70, 75, 80, 85, 60, 55, 50, 45

Q.5 Solve both questions :

Q5.1

Insert the following sequence of elements into an AVL tree, starting with an empty tree: 10, 20, 15, 25, 30, 16, 18, 19

Q5.2

Delete 30 in the AVL tree that you got.

Q.6 Solve both questions :

Q6.1

Write algorithm for quicksort and mention time and space complexity in each case.

Q6.2

Define collision in hashing. What are the different methodologies to resolve collision? Explain briefly.

Q.7 Solve this question :

Q7.1

Construct binary search tree and write pre- and post-order traversals of this tree: 8, 3, 1, 10, 6, 14, 4, 7, 13, 22, 5

Q.8 Solve both questions :

Q8.1

Write algorithm to count leaf node in binary tree and check whether tree is balanced or not.

Q8.2

Write a recursive and iterative version of insertion sort algorithm and mention time complexity.

Q.9 Write short notes on the following:

Q9.1

BFS

Q9.2

DFS

Q9.3

Binary search tree

Q9.4

Balance factor

2017 051403

B.Tech Examination, 2017

Time 3 hours
Full Marks 70
Instructions:
  • The marks are indicated in the right-hand margin.
  • There are NINE questions in this paper.
  • Attempt FIVE questions in all.
  • Question No. 1 is compulsory.

Questions

Q1

Answer the following:

a)

How many number of interchanges are required to sort 5, 1, 6 in ascending order using Bubble sort?

[2 Marks]
b)

What is the postfix form of the expression (A+B)∗(C∗D−E)∗F/G(A + B) * (C * D - E) * F / G?

[2 Marks]
c)

How many leaf nodes are present in a full binary tree with 2n+12n+1 nodes?

[2 Marks]
d)

A linear list of elements in which deletion can be done from one end (front) and insertion can take place only at the other end (rear) is known as .............

[2 Marks]
e)

What is LIFO?

[2 Marks]
f)

What are the minimum number of multiplications and additions required to evaluate the given polynomial P=4x3+3x2−15x+45P=4x^3+3x^2-15x+45?

[2 Marks]
g)

Which of the following sorting methods would be most suitable for sorting a list which is almost sorted?

[2 Marks]
h)

What values are automatically assigned to those array elements which are not explicitly initialized?

[2 Marks]
i)

What is the time complexity of Merge sort and Heap sort algorithms?

[2 Marks]
j)

What is complete binary Tree?

[2 Marks]
Q2

Answer the following:

a)

What is Binary Search Tree (BST)? Make a BST for the following sequence of numbers. 45, 36, 76, 23, 89, 115, 98, 39, 41, 56, 69, 48 Traverse the tree in Preorder, Inorder and Postorder.

[14 Marks]
Q3

Answer the following:

a)

What is an algorithm? What are the characteristics of a good algorithm?

[7 Marks]
b)

What is a sparse matrix? How is it stored in the memory of a computer?

[7 Marks]
Q4

Answer the following:

a)

Describe about the doubly linked list with an example. Write the advantages of linked list over array.

[6 Marks]
b)

Show the various passes of bubble sort on an unsorted list 11, 15, 2, 13, 6

[8 Marks]
Q5

Answer the following:

a)

Define a stack. Describe ways to implement stack.

[9 Marks]
b)

Differentiate between system defined data types and abstract data types with suitable examples.

[5 Marks]
Q6

Answer the following:

a)

Describe insertion sort with a proper algorithm. What is the complexity of insertion sort in worst case?

[7 Marks]
b)

Write an algorithm to insert a node in the beginning of the linked list.

[7 Marks]
Q7

Answer the following:

a)

For the given Binary Search Tree, perform the following sequence of operations: (A) Delete 44 (B) Delete 75 (C) Delete 25

[9 Marks]
b)

Write down the applications of stack and queue data structures.

[5 Marks]
Q8

Answer the following:

a)

Construct a binary tree whose nodes on inorder and preorder are given as follows: Inorder: 10, 15, 17, 18, 20, 25, 30, 35, 38, 40, 50 Preorder: 20, 15, 10, 18, 17, 30, 25, 40, 35, 38, 50

[8 Marks]
b)

What do you mean by hashing? Explain any three popular hash functions.

[6 Marks]
Q9

Answer the following:

a)

Write short notes on following (any two):

[14 Marks]
2016 051403

B.Tech Examination, 2016

Time 3 hours
Full Marks 70
Instructions:
  • The marks are indicated in the right-hand margin.
  • There are NINE questions in this paper.
  • Attempt FIVE questions in all.
  • Question No. 1 is compulsory.

Questions

Q1

Answer the following:

a)

There are 8, 15, 13 and 14 nodes in four different trees. Which one of them can form a full binary tree?

[2 Marks]
b)

Which data structure is used to perform recursion and why?

[2 Marks]
c)

List out the areas in which data structures are applied extensively.

[2 Marks]
d)

Sorting is not possible by using which of the following methods and why? Insertion, Selection, Exchange, Deletion

[2 Marks]
e)

What is FIFO?

[2 Marks]
f)

What is a postfix expression?

[2 Marks]
g)

Differentiate between linear and non-linear data structures.

[2 Marks]
h)

How do you insert a new item in a binary search tree?

[2 Marks]
i)

Differentiate between stack and array.

[2 Marks]
j)

What is an AVL tree?

[2 Marks]
Q2

Answer the following:

a)

Write binary search algorithm and trace to search element 91 in the following list: 13, 30, 62, 73, 81, 88, 91

[10 Marks]
b)

What are the limitations of binary search?

[4 Marks]
Q3

Answer the following:

a)

Draw a binary tree from its inorder and preorder traversal sequences given as follows: Inorder: d b g e h a c n f Preorder: a b d e g h c f n

[7 Marks]
b)

What is stack? How can stack be used to check whether an expression is correctly parenthesized or not? [Hint: () is correct but (( or )()( is not]

[7 Marks]
Q4

Answer the following:

a)

Convert the following infix expression into a postfix expression (show steps): $A * (B+D) / E - F(G + H/k)$

[7 Marks]
b)

How do you find the complexity of an algorithm? What is the relation between the time and the space complexities of an algorithm?

[7 Marks]
Q5

Answer the following:

a)

Write an algorithm to create a singly linked list. Explain the steps to do the following operations:

[14 Marks]
Q6

Answer the following:

a)

Arrange the given list of elements in ascending order using quick sort: 44, 33, 11, 55, 77, 90, 40, 60, 99, 22, 88, 66

[8 Marks]
b)

Define an array. How does an array differ from an ordinary variable? How are arrays represented in the memory?

[6 Marks]
Q7

Answer the following:

a)

Define hashing. Describe any two commonly used hash functions. Describe one method of collision resolution.

[14 Marks]
Q8

Answer the following:

a)

Write down the procedure for inserting and deleting elements from a circular queue implemented using arrays.

[8 Marks]
b)

What is a height balanced tree? Explain how the height is balanced after addition/deletion of nodes in it.

[6 Marks]
Q9

Answer the following:

a)

Write short notes on any two the following:

[14 Marks]
2015 051403

B.Tech Examination, 2015

Time 3 hours
Full Marks 70
Instructions:
  • The marks are indicated in the right-hand margin.
  • There are NINE questions in this paper.
  • Attempt FIVE questions in all.
  • Question No. 1 is compulsory.

Questions

Q1

Answer the following:

a)

If the sequence of operations—push(1), push(2), pop, push(1), push(2), pop, pop, pop, push(2), pop are performed on a stack, the sequence of popped out values is

a)

2, 2, 1, 1, 2

b)

2, 2, 1, 2, 2

c)

2, 1, 2, 2, 1

d)

2, 1, 2, 2, 2

[2 Marks]
b)

Queue can be used to implement

a)

radix sort

b)

quicksort

c)

recursion

d)

depth first search

[2 Marks]
c)

The number of binary trees with 3 nodes which when traversed in post-order gives the sequence A, B, C is

a)

3

b)

9

c)

7

d)

5

[2 Marks]
d)

A binary tree has nn leaf nodes. The number of nodes of degree 2 in this tree is

a)

log⁡2n\log_2 n

b)

n−1n-1

c)

nn

d)

2n2^n

[2 Marks]
e)

Sparse matrices have

a)

many zero entries

b)

many non-zero entries

c)

higher dimension

d)

None of the above

[2 Marks]
f)

The postfix expression for ∗+ab−cd*+ab-cd is

a)

ab+cd−∗ab+cd-*

b)

abcd+−∗abcd+-*

c)

ab+cd∗−ab+cd*-

d)

ab+−cd∗ab+-cd*

[2 Marks]
g)

The memory address of the first element of an array is called

a)

floor address

b)

foundation address

c)

first address

d)

base address

[2 Marks]
h)

The memory address of fifth element of an array can be calculated by the formula

a)

LOC(Array[5])=Base(Array)+W(5-lower bound)

b)

LOC(Array[5])=Base(Array[5])+(5-lower bound)

c)

LOC(Array[5])=Base(Array[4])+(5-upper bound)

d)

None of the above

[2 Marks]
i)

Which of the following data structures are indexed structures?

a)

Linear arrays

b)

Linked lists

c)

Both of the above

d)

None of the above

[2 Marks]
j)

Which of the following is not the required condition for binary search algorithm?

a)

The list must be sorted

b)

There should be the direct access to the middle element in any sublist

c)

There must be mechanism to delete and/or insert elements in list

d)

None of the above

[2 Marks]
Q2

Answer the following:

a)

What is a data structure? What is the need of data structures?

[7 Marks]
b)

Explain Big-Oh notation with the help of example.

[7 Marks]
Q3

Answer the following:

a)

Write suitable array declaration for the following:

  • 100 items of integer type
  • A string of 25 characters
  • An integer matrix of order 5×45 \times 4 Can an array be initialized? If yes, how?
[7 Marks]
b)

Write a program that sorts a given list of numbers using quicksort.

[7 Marks]
Q4

Answer the following:

a)

Explain overflow and underflow conditions of a stack with examples.

[7 Marks]
b)

What are priority queues? Write their applications.

[7 Marks]
Q5

Answer the following:

a)

Write a program that travels a linked list consisting of nodes of the following struct type:

struct student {
    char name[15];
    int roll;
    struct student *next;
};

While traversing, it counts the number of nodes in the list. Finally, the count is printed.

[7 Marks]
b)

Explain the merits and demerits of static and dynamic memory allocation techniques.

[7 Marks]
Q6

Answer the following:

a)

Define the following terms: (i) Root (ii) Leaf nodes (iii) Empty tree (iv) Sub-tree

[7 Marks]
b)

What are heap trees? Discuss a minheap and a maxheap tree with the help of examples. What are the operations that can be performed on a heap tree?

[7 Marks]
Q7

Answer the following:

a)

Explain the following graph theory terms: (i) Node (ii) Undirected graph (iii) Edge (iv) Connected graph (v) Directed graph (vi) Disconnected graph

[7 Marks]
b)

Write the Warshall's algorithm.

[7 Marks]
Q8

Answer the following:

a)

Write an explanatory note on AVL rotations.

[7 Marks]
b)

Write an algorithm for inserting a key K in a B-tree.

[7 Marks]
Q9

Answer the following:

a)

What is a sparse matrix? What are the methods to represent a sparse matrix?

[7 Marks]
b)

Use a stack to convert the following infix arithmetic expression into a postfix expression: $(A-B)*(C/D)+E$ Show the changing status of the stack in tabular form.

[7 Marks]

Made with ❤️ by Prit at GEC Sheikhpura

Install on iOS

To install BEU Connect on your iPhone:

1. Tap the Share button at the bottom of Safari.
2. Scroll down and tap "Add to Home Screen".