# FYBCA STUDENTS

### Trees in Data structures

**USEFUL FOR FYBSC (IT), FYBCA STUDENTS**** **

** **

Trees |

### Binary Trees

The simplest form of tree is a **binary tree**. A binary tree consists of

- a
*node*(called the**root**node) and - left and right sub-trees.

Both the sub-trees are themselves binary trees.

A binary tree

The nodes at the lowest levels of the tree (the ones with no sub-trees) are called **leaves**.

In an *ordered binary tree*,

- the keys of all the nodes in the left sub-tree are less than that of the root,
- the keys of all the nodes in the right sub-tree are greater than that of the root,
- the left and right sub-trees are themselves ordered binary trees.

Posted By-: Vissicomp Technology Pvt. Ltd.

Website -: http://www.vissicomp.com

### Interview Questions in Data structures

**USEFUL FOR FYBSC (IT), FYBCA STUDENTS**** **

**1.) **Convert the expression ((A + B) * C – (D – E) ^ (F + G)) to equivalent Prefix and Postfix notations.

i.) **Prefix Notation:** – * +ABC ^ – DE + FG

ii.) **Postfix Notation:** AB + C * DE – FG + ^ –

**2.) **Sorting is not possible by using which of the following methods? (Insertion, Selection, Exchange, Deletion)

**An.) Sorting is not possible in Deletion.** Using insertion we can perform insertion sort, using selection we can perform selection sort, using exchange we can perform the bubble sort (and other similar sorting methods). But no sorting method can be done just using deletion.

**3.) **List out few of the applications that make use of Multilinked Structures?

(i) Sparse matrix,

(ii) Index generation.

**4.) **In tree construction which is the suitable efficient data structure? (Array, Linked list, Stack, Queue)

**An.)**Linked list is the suitable efficient data structure

**5.) **Classify the Hashing Functions based on the various methods by which the key value is found.

- Direct method,
- Subtraction method,
- Modulo-Division method,
- Digit-Extraction method,
- Mid-Square method,
- Folding method,
- Pseudo-random method

**6.) **What are the types of Collision Resolution Techniques and the methods used in each of the type?

**Open addressing (closed hashing),**the methods used include: Overflow block.**Closed addressing (open hashing),**The methods used include: Linked list, Binary tree

**7.) **Whether Linked List is linear or Non-linear data structure?

**An.) **

According to Access strategies Linked list is a linear one.

According to Storage Linked List is a Non-linear one

** **

Posted By-: Vissicomp Technology Pvt. Ltd.

Website -: http://www.vissicomp.com

### Interview questions of Data structures in C

**USEFUL FOR FYBSC (IT), FYBCA STUDENTS**** **

** **

1.) What is the difference between a Stack and an Array?

**Stack**

- Stack is a dynamic object whose size is constantly changing as items are pushed and popped.
- Stack may contain different data types.
- Stack is declared as a structure containing an array to hold the element of the stack, and an integer to indicate the current stack top within the array.
- Stack is a ordered collection of items.

**Array**

- Array is an ordered collection of items.
- Array is a static object.
- It contains same data types.
- Array can be home of a stack i.e. array can be declared large enough for maximum size of the stack.

2. What is sequential search?

In sequential search each item in the array is compared with the item being searched until a match occurs. It is applicable to a table organized either as an array or as a linked list.

3. What are the disadvantages array implementations of linked list?

The no of nodes needed can’t be predicted when the program is written.

The no of nodes declared must remain allocated throughout its execution.

4. Define circular list?

In linear list the next field of the last node contain a null pointer, when a next field in the last node contain a pointer back to the first node it is called circular list.

5. What does abstract Data Type Mean?

Data type is a collection of values and a set of operations on these values. Abstract data type refers to the mathematical concept that defines the data type.

6. Define double linked list?

- It is a collection of data elements called nodes, where each node is divided into three parts
- An info field that contains the information stored in the node.
- Left field that contain pointer to node on left side.
- Right field that contain pointer to node on right side.

7. What are the methods available in storing sequential files?

- Straight merging
- Natural merging
- Polyphase sort
- Distribution of Initial runs

Posted By-: Vissicomp Technology Pvt. Ltd.

Website -: http://www.vissicomp.com

** **

### Hashing technique in Data structures in C

**USEFUL FOR FYBSC (IT), FYBCA STUDENTS**** **

** **

1. 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. 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), where w is the number of words per memory cell for the array

b. LOC(Array[5])=Base(Array[5])+(5-lower bound), where w is the number of words per memory cell for the array

c. LOC(Array[5])=Base(Array[4])+(5-Upper bound), where w is the number of words per memory cell for the array

d. None of above

3. Which of the following data structures are indexed structures?

a. linear arrays

b. linked lists

c. both of above

d. none of above

4. 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 sub list

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

d. none of above

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

a. must use a sorted array

b. requirement of sorted array is expensive when a lot of insertion 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 1000.

6. Two dimensional arrays are also called

a. tables arrays

b. matrix arrays

c. both of above

d. none of above

7. A variable P is called pointer if

a. P contains the address of an element in DATA.

b. P points to the address of first element in DATA

c. P can store only memory addresses

d. P contain the DATA and the address of DATA

Posted By-: Vissicomp Technology Pvt. Ltd.

Website -: http://www.vissicomp.com

### Hashing technique in Data structures in C

**USEFUL FOR FYBSC (IT), FYBCA STUDENTS**** **

**What is hashing technique?**** Describe in brief.**

** **

- In general, in all searching techniques, search time is dependent on the number of items. Sequential search, binary search and all the search trees are totally dependent on number of items and many key comparisons are involved.
- Hashing is a technique where search time is independent of the number of items or elements. In this technique a hash function is used to generate an address from a key. The hash function takes a key as input and returns the hash value of that key which is used as an address index in the array.

- We can write hash function as follows

h(k)=a;

Where h is hash function, k is the key, a is the hash value of the key.

While choosing a hash function we should consider some important points.

- It should be easy to compute
- It should generate address with minimum collision.

** **

Posted By-: Vissicomp Technology Pvt. Ltd.

Website -: http://www.vissicomp.com

### Data structures in C

**USEFUL FOR FYBSC (IT), FYBCA STUDENTS**** **

** **

1. 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. 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), where w is the number of words per memory cell for the array

b. LOC(Array[5])=Base(Array[5])+(5-lower bound), where w is the number of words per memory cell for the array

c. LOC(Array[5])=Base(Array[4])+(5-Upper bound), where w is the number of words per memory cell for the array

d. None of above

** **

3. Which of the following data structures are indexed structures?

a. linear arrays

b. linked lists

c. both of above

d. none of above

** **

4. Two dimensional arrays are also called

a. tables arrays

b. matrix arrays

c. both of above

d. none of above

** **

**5. **Which of the following data structure can’t store the non-homogeneous data elements?

a. Arrays

b. Records

c. Pointers

d. None

** **

**6. **Which of the following data structure store the homogeneous data elements?

a. Arrays

b. Records

c. Pointers

d. None

** **

**7. **Binary search algorithm cannot be applied to

a. sorted linked list

b. sorted binary trees

c. sorted linear array

d. pointer array

Posted By-: Vissicomp Technology Pvt. Ltd.

Website -: http://www.vissicomp.com