Data Structure using C Language

Assignment A
Q.1 What is stack? Give the codes of Push and Pop operation in stack.

2    Convert the following infix notation to postfix notation: (A + B) * C /D

Ans      

Q.3     Write the algorithm and ‘C’ program for sorting the numbers in ascending order using quick sort.

4.    Define pointer. Give an example to access structure members using pointer.

5.     What is a Binary Tree? List out the traversal methods in a Binary Tree with illustration examples.

6.     What is data searching? Write a program to search the data using binary search?

7.    Explain any two techniques for hashing.

Assignment B
Case study
Suppose that a binary search tree stores, at each node, u, the height, u.height, of the subtree rooted at u, and the size, u.size of the subtree rooted at u.

Answer Section
Q.No 1: Show how, if we perform a left rotation at u, then these two quantities can be updated, in constant time, for all nodes affected by the rotation.

Q.No 2: Show how, if we perform a right rotation at u, then these two quantities can be updated, in constant time, for all nodes affected by the rotation.

Q.No 3: Explain why the same result is not possible if we try to also store the depth, u.depth, of each node u.

Assignment C

Which of the following data structure is not linear data structure?
 (A): array
 (B): linked list
 (C): graphs
 (D): stacks

When determining the efficiency of algorithm, the space factor is measured by
 (A): Counting the maximum memory needed by the algorithm
 (B): Counting the minimum memory needed by the algorithm
 (C): Counting the average memory needed by the algorithm
 (D): Counting the maximum disk space needed by the algorithm

The operation of processing each element in the list is known as
 (A): sorting
 (B): merging
 (C): Inserting
(D): traversal

Each array declaration need 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

For an algorithm the complexity of the average case is
 (A): Much more complicated to analyze than that of worst case
 (B): Much more simpler to analyze than that of worst case
 (C): Sometimes more complicated and some other times simpler than that of worst case
 (D): easier than best case

In linear search algorithm the Worst case occurs when
 (A): The item is somewhere in the middle of the array
 (B): The item is not in the array at all
 (C): The item is the last element in the array
 (D): The item is the last element in the array or is not there at all

If the values of a variable in one module is indirectly changed by another module, this situation is called
 (A): internal change
 (B): inter-module change
 (C): side effect
 (D): side-module update

The following sequence of operation is performed on stack : push(1),push(2),pop,push(1),push(2),pop,pop,pop,push(2),pop. The sequence of popped out values are ?
 (A): 2,2,1,1,2
 (B): 2,2,1,2,2
 (C): 2,1,2,2,1
 (D): 2,1,2,2,2

Which of the following is useful in traversing a given graph by breadth first search?
 (A): Stack
 (B): set
 (C): list
 (D): queue

The pre-order and post order traversal of a Binary Tree generates the same output. The tree can have maximum
 (A): three nodes
 (B): two nodes
 (C): one node
 (D): any number of nodes

The initial configuration of the queue is a,b,c,d (a is the front end). To get the configuration d,c,b,a one needs a minimum of ?
 (A): 2 deletions and 3 additions
 (B): 3 additions and 2 deletions
 (C): 3 deletions and 3 additions
 (D): 3 deletions and 4 additions

Breadth first search
 (A): scans all incident edges before moving to other vertex
 (B): scans adjacent unvisited vertex as soon as possible
 (C): is same as backtracking
 (D): scans last vertex first

Elements of an array are accessed by
 (A): accessing function is built in
 (B): mathematical function
 (C): index
 (D): memory address

If height of a tree is 10, the highest level of the tree is
 (A): 10
 (B): 9
 (C): 5
 (D): 1

The postfix expression for * + a b - c d is?
 (A): ab + cd - *
 (B): ab cd + - *
 (C): ab + cd * -
 (D): ab + - cd *

List pointer variable in linked list contains address of the
 (A): following node in the list
 (B): current node in the list
 (C): first node in the list
 (D): last node in the list

Which of the following traversal techniques lists the nodes of binary search tree in ascending order?
 (A): preorder
 (B): postorder
 (C): inorder
 (D): all of a, b and c

The process of accessing data stored in a serial access memory is similar to manipulating data on a
 (A): heap
 (B): queue
 (C): stack
 (D): binary tree

A binary tree T has n leaf nodes. The number of nodes of degree 2 in T is
 (A): log n
 (B): n-1
 (C): n
 (D): 2n

In a directed graph,
 (A): directions are fixed
 (B): underlying graph is fixed
 (C): both a and b
 (D): none of a and b

The number of possible ordered trees with three nodes A,B,C is?
 (A): 16
 (B): 12
 (C): 6
 (D): 10

The sum of degrees of all the vertices of a graph is --------the number of edges.
 (A): same
 (B): twice
 (C): odd multiple
 (D): thrice

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

A vertex of degree one is called
 (A): padent
 (B): isolated vertex
 (C): null vertex
 (D): colored vertex

Which of the following solves all pair shortest path problem?
 (A): Dijkstra algorithm
 (B): Krushkal algorithm
 (C): Prim Algorithm
 (D): Warshall's algorithm

Linked list are suitable for which of the following problems:
 (A): insertion sort
 (B): binary search
 (C): Radix sort
 (D): polynomial manipulation

Which of the following algorithm design technique is used in the quick sort algorithm?
 (A): Dynamic programming
 (B): Backtracking
 (C): Divide and conquer
 (D): Greedy method

A machine took 200 sec to sort 200 names. In 800 sec it can approximately sort
 (A): 400 names
 (B): 800 names
 (C): 750 names
 (D): 600 names

The value of first linked list address is :
 (A): 0
 (B): -1
 (C): 1
 (D): Null

The restriction while using binay search is:
 (A): List should be small in number
 (B): list should be large in number
 (C): list should be sorted
 (D): no restriction

The number of swapping needed to sort numbers 8,22,7,9,31,19,5,13 in ascending order using bubble sort is ?
 (A): 11
 (B): 12
 (C): 13
 (D): 14

If a node having two children is deleted from a binary tree, it is replaced by its
 (A): Inorder predecessor
 (B): Inorder successor
 (C): Preorder predecessor
 (D): preorder successor

The OS of a computer may periodically collect all the free memory space to form contiguous block of free space. This is called
 (A): Concatenation
 (B): garbage collection
 (C): collision
 (D): Dynamic Memory Allocation

A binary search tree whose left subtree and right subtree differ in hight by at most 1 unit is called ……
 (A): AVL tree
 (B): red black tree
 (C): binary tree
 (D): B tree

If h is any hashing function and is used to hash n keys in to a table of size m, where n<=m, the expected number of collisions involving a particular key x is :
 (A): less than 1.
 (B): less than n
 (C): less than m
 (D): less than n/2

B Trees are generally
 (A): very deep and narrow
 (B): very wide and shallow
 (C): very deep and very wide
 (D): cannot say

A technique for direct search is  Solve by www.solvezone.in contact for more details at 8882309876.
 (A): Binary Search
 (B): Linear Search
 (C): Tree Search
 (D): Hashing

If a node in a BST has two children, then its inorder predecessor has
 (A): no left child
 (B): no right child
 (C): two children
 (D): no child

A sort which relatively passes through a list to exchange the first element with any element less than it and then repeats with a new first element is called
 (A): insertion sort
 (B): selection sort
 (C): heap sort
 (D): quick sort

In a circular linked list
 (A): components are all linked together in some sequential manner.
 (B): there is no beginning and no end.
 (C): components are arranged hierarchically.
 (D): forward and backward traversal within the list is permitted.

…………… is not the component of data structure.
A) Operations
B) Storage Structures
C) Algorithms
D) None of above

Which is not a Data structure component?

Operation
storage
Algorithm
None of the above