Important Short Questions and Answers: Linear Data Structures

1. Write down the definition of data structures?

A data structure is a mathematical or logical way of organizing data in the memory that consider not only the items stored but also the relationship to each other and also it is characterized by accessing functions.

2. Binary Heap

The implementation we will use is known as a binary heap. Its use is so common for priority queue implementations that when the word heap is used without a qualifier

Structure Property

A heap is a binary tree that is completely filled, with the possible exception of the bottom level, which is filled from left to right. Such a tree is known as a complete binary tree

3. Define Algorithm?

Algorithm is a solution to a problem independent of programming language. It consist of set of finite steps which, when carried out for a given set of inputs, produce the corresponding output and terminate in a finite time.

4. What are the features of an efficient algorithm?

•  Free of ambiguity

•  Efficient in execution time

•  Concise and compact

•  Completeness

•  Definiteness

•  Finiteness

5. List down any four applications of data structures?

·        Compiler design

·        Operating System

·        Database Management system

·        Network analysis

6. What is meant by an abstract data type (ADT)?

An ADT is a set of operation. A useful tool for specifying the logical properties of a datatype is the abstract data type.ADT refers to the basic mathematical concept that defines the datatype. Eg.Objects such as list, set and graph along their operations can be viewed as ADT's.

7. What are the operations of ADT?

Union, Intersection, size, complement and find are the various operations of ADT.

8. What is meant by list ADT?

List ADT is a sequential storage structure. General list of the form a1, a2, a3.…., an and the size of the list is 'n'. Any element in the list at the position I is defined to be ai, ai+1 the successor of ai and ai-1 is the predecessor of ai.

9. What are the two parts of ADT?

• Value definition

• Operator definition

10. What is a Sequence?

A sequence is simply an ordered set of elements.A sequence S is sometimes written as the enumeration of its elements,such as S =If S contains n elements,then length of S is n.

11. Define len(S),first(S),last(S),nilseq ?

len(S) is the length of the sequence S.

first(S) returns the value of the first element of S last(S) returns the value of the last element of S

nilseq :Sequence of length 0 is nilseq .ie., contains no element.

12. What are the two basic operations that access an array?

Extraction:

Extraction operation is a function that accepts an array, a ,an index,i,and returns an element of the array.

Storing:

Storing operation accepts an array , a ,an index i , and an element x.

13. Define Structure?

A Structure is a group of items in which each item is identified by its own identifier ,each of which is known as a member of the structure.

14. Define Union ?

Union is collection of Structures ,which permits a variable to be interpreted in several different ways.

15. Define Automatic and External variables?

Automatic variables are variables that are allocated storage when the function is invoked.

External variables are variables that are declared outside any function and are allocated storage at the point at which they are first encountered for the remeinder of the program’s execution.

16. What is a Stack?

A Stack is an ordered collection of items into which new items may be inserted and from which items may be deleted at one end, called the top of the stack.

The other name of stack is Last-in -First-out list.

17.            What are the two operations of Stack?

• _ PUSH

• _ POP

18.            What is a Queue?

A Queue is an ordered collection of items from which items may be deleted at one end called the front of the queue and into which tems may be inserted at the other end called rear of the queue.Queue is called as First–in-First-Out(FIFO).

19. What is a Priority Queue?

Priority queue is a data structure in which the intrinsic ordering of the elements does determine the results of its basic operations. Ascending and Descending priority queue are the two types of Priority queue.

20. What is a linked list?

Linked list is a kind of series of data structures, which are not necessarily adjacent in memory. Each structure contain the element and a pointer to a record containing its successor.

21. What is a doubly linked list?

In a simple linked list, there will be one pointer named as 'NEXT POINTER' to point the next element, where as in a doubly linked list, there will be two pointers one to point the next element and the other to point the previous element location.

22. Define double circularly linked list?

In a doubly linked list, if the last node or pointer of the list, point to the first element of the list,then it is a circularly linked list.

23. What is a circular queue?

The queue, which wraps around upon reaching the end of the array is called as circular

queue.

24.            Define max and min heap?

·        A heap in which the parent has a larger key than the child's is called a max heap.

·        A heap in which the parent has a smaller key than the child is called a min heap.

25.  Write postfix from of the expression –A+B-C+D?

A-B+C-D+

26. Define Recursion?

Recursion is a function calling itself again and again.

27. What is a Fibonacci sequence?

Fibonacci sequence is the number of integers

0,1,1,2,3,5,8,13,21,34,……….

Each element in this sequence is the sum of the two preceding elements.

28.Name the two fields of Linked list?

• Info field

• Next field

29. What is a doubly linked list?

In a simple linked list, there will be one pointer named as 'NEXT POINTER' to point the next element, where as in a doubly linked list, there will be two pointers one to point the next element and the other to point the previous element location.

30. Name the three fields of Doubly Linked list?

• Info field

• Left field

• Right field

31. Define double circularly linked list?

In a doubly linked list, if the last node or pointer of the list, point to the first element of the list,then it is a circularly linked list.

32. What is the need for the header?

Header of the linked list is the first element in the list and it stores the number of elements in the list. It points to the first data element of the list.

33. List three examples that uses linked list?

• Polynomial ADT

• Radix sort

• Multi lists

34. Give some examples for linear data structures?

• Stack

• Queue

35. How do you test for an empty queue?

To test for an empty queue, we have to check whether READ=HEAD where REAR is a pointer pointing to the last node in a queue and HEAD is a pointer that pointer to the dummy header. In the case of array implementation of queue, the condition to be checked for an empty queue is

READ

36.            What are the postfix and prefix forms of the expression?

A+B*(C-D)/(P-R)

Postfix form: ABCD-*PR-/+ Prefix form: +A/*B-CD-PR

37.            Explain the usage of stack in recursive algorithm implementation?

In recursive algorithms, stack data structures is used to store the return address when a recursive call is encountered and also to store the values of all the parameters essential to the

current state of the procedure.

38. Write down the operations that can be done with queue data structure?

Queue is a first - in -first out list. The operations that can be done with queue are insert and remove.

39. What is a circular queue?

The queue, which wraps around upon reaching the end of the array is called as circular queue.

40. Define max heap?

A heap in which the parent has a larger key than the child's is called a max heap.

41. Define min heap?

A heap in which the parent has a smaller key than the child is called a min heap.