Assignment A

Ql): Define array? Write a program to store 10 salesmen’s amount in an array and find out total sale & best sales amount.

Ans:

Q2.) With your own example explain breadth first traversal technique, and analyze its complexity.

Q3.) With the help of a program and a numerical example explain the Depth First Traversal of a tree.

Q4.) Describe with sample code snippets the following operations on Binary Search Trees (BST):

A) Insertion

B) Searching

Q5.) With the help of a suitable numerical example, explain the inorder, preorder and postorder traversals on a Binary Search Tree.

Assignment B

**Q1: Case Study**

Bubble sort is a simple sorting algorithm. It works by repeatedly stepping through the list to be sorted, comparing each pair of adjacent items and swapping them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted. The algorithm gets its name from the way smaller elements “bubble” to the top of the list. Because it only uses comparisons to operate on elements, it is a comparison sort.

a) Consider the following values sorted in an array. Sort it in ascending order using Bubble sort technique showing all the iterations:

15, 43, 5, 18, 27, 3,10

b) Also write a C function to sort one dimensional integer array in ascending order using Bubble Sort technique.

Q2) .Assume that you have two build two different Data structures based on the clients requirements:

■ One client is running a school and requires storing student information in a sequential manner, which data structure do you use, write an outline diagram for it.

■ Next client is a cinema theatre owner and would prefer to fill in seats as and when customers come to hall, mention the data structure preferred and represent it diagrammatically.

Q3): What do you mean by a Graph? How graphs are represented? Explain

Q4). Explain the theory of Minimum spanning trees.

**Assignment C**

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. Which of the following data structures are indexed structures?

a.) linear arrays

b.) linked lists

c.) both of above

d.) none of above

3. 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 above

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

5. Two dimensional arrays are also called

a.) tables arrays

b.) matrix arrays

c.) both of above

d.) none of above

6. 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

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

a.) Arrays

b.) Records

c.) Pointers

d.) None

8. Which of the following data structure store the homogeneous data elements?

a.) Arrays

b.) Records

c.) Pointers

d.) None

9. The difference between linear array and a record is

a.) An array is suitable for homogeneous data but the data items in a record may have different data type

b.) In a record, there may not be a natural ordering in opposed to linear array.

c.) A record form a hierarchical structure but a linear array does not

d.) All of above

10. Which of the following statement is false?

a.) Arrays are dense lists and static data structure

b.) data elements in linked list need not be stored in adjacent space in memory

c.) pointers store the next data element of a list

d.) linked lists are collection of the nodes that contain information part and next pointer

11. Binary search algorithm can not be applied to

a.) sorted linked list

b.) sorted binary trees

c.) sorted linear array

d.) pointer array

12. When new data are to be inserted into a data structure, but there is no available space; this situation is usually called

a.) underflow

b.) overflow

c.) housefull

d.) saturated

13. The situation when in a linked list START=NULL is

a.) underflow b.) Overflow

c.) Housefull

d.) saturated

14. Which of the following is two way list?

a.) grounded header list

b.) Circular header list

c.) Linked list with header and trailer nodes

d.) none of above

15. Which of the following name does not relate to stacks?

a.) FIFO lists

b.) LIFO list

c.) Piles

d.) Push-down lists

16. The term “push” and “pop” is related to the

a.) array

b.) Lists

c.) Stacks

d.) All of above

17. A data structure where elements can be added or removed at either end but not in the middle

a.) Linked lists b.) Stacks

c.) Queues

d.) Deque

18. When in order traversing a tree resulted EACKFHDBG; the preorder traversal would return

a.) FAEKCDBHG

b.) FAEKCDHGB

c.) EAFKHDCBG

d.) FEAKDCHBG

19. The complexity of linear search algorithm is

a.) 0(n)

b.) O(logn)

c.) 0(n2)

d.) 0(nlogn]

20. The complexity of Binary search algorithm is

a.) O(n)

b.) O(log n]

c.) O(n2]

d.) O(n log n]

21. The complexity of Bubble sort algorithm is

a.) O(n)

b.) O(log n)

c.) O(n2)

d.) O(n log n]

22. The complexity of merge sort algorithm is

a.) O(n)

b.) O(log n]

c.) O(n2)

d.) O(n log n)

23. The indirect change of the values of a variable in one module by another module is called

a.) internal change

b.) inter-module change

c.) side effect

d.) side-module update

24. Which of the following data structure is not linear data structure?

a.) Arrays

b.) Linked lists

c.) Both of above

d.) None of above

25. Which of the following data structure is linear data structure?

a.) Trees

b.) Graphs

c.) Arrays

d.) None of above

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

a.) Sorting

b.) Merging

c.) Inserting

d.) Traversal

27. Finding the location of the element with a given value is:

a.) Traversal

b.) Search

c.) Sort

d.) None of above

28. 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.) for both of above situation

d.) for none of above situation

29. Linked lists are best suited

a.) for relatively permanent collections of data

b.) for the size of the structure and the data in the structure are constantly changing

c.) for both of above situation

d.) for none of above situation

30. 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

31. The elements of an array are stored successively in memory cells because

a.) by this way computer can keep track only the address of the first element and the addresses of other elements can be calculated

b.) the architecture of computer memory does not allow arrays to store other than serially

c.) both of above

d.) none of above

32. In a Stack the command to access nth element from the top of the stack s will be

a.) S[Top-n]

b.) S [Top+n] c.) S [top-n-1]

d.) None of the above

33. In a balance binary tree the height of two sub trees of every node can not differ by more than

a.) 2

b.) 1

c.) 0

d.) 3

34. The result of evaluating prefix expression */b+-dacd, where a = 3, b = 6, c = 1, d = 5 is

a.) 0

b.) 5

c.) 10

d.) 15

35. In an array representation of binary tree the right child of root will be at location of

a.) 2

b.) 5

c.) 3

d.) 0

36. What is the postfix expression for the following infix: (a + b*(c – a) – d)

A. d b c a-*a + –

B. a b c a d–* +

C. a b c a-* + d-

D. None of the above.

37. What is the value of the postfix expression 6 3 2 4- + *

A. Something between-15 and-100

B. Something between -5 and -15

C. Something between 5 and -5

D. Something between 5 and 15

E. Something between 15 and 100

38. One difference between a queue and a stack is:

A. Queues require linked lists, but stacks do not

B. Stacks require linked lists, but queues do not

C. Queues use two ends of the structure; stacks use only one.

D. Stacks use two ends of the structure, queues use only one.

39. For the following tree, what is the order of nodes visited using an in-order traversal?

A. 12 3 7 10 111430 40

B. 12 3 14 7 10 1140 30

C. 13 2 7 10 40 30 1114

D. 142 13 1110 7 30 40

40. Given a binary tree with 18 nodes, what is the minimum possible depth of the tree?

A. 1

B. 2

C. 3

D. 4

E. 5