RIYA PANCHAL (SEMESTER - 9)
Que 1) Answer For Following:
1. What is a Linked list?
- Linked list is a type of linear data structure, which contains nodes. Each node contains a link
to the next node reference in the list. The first element of the list is called the Head. Linked list
make insertion , deletion and traversal operations easier, Random access from the Linked list
is not possible
2. What is a Binary Search Tree?
- A binary search tree (BST) is a sorted binary tree. In BST each node has a key and its value,
where we can easily search for any key. Each node contains two child key which also contain
sub childs or sub tree.
- The left subtree of a node contains only nodes with keys lesser than the node’s key.
- The right subtree of a node contains only nodes with keys greater than the node’s key.
- We can perform search, insert and traversal operation on Binary Search Tree
3. What is searching?
- Searching means finding the required information from a collection of items or from a lists or
any data structure. Main purpose of searching is to find if a given value exists or not.
- There are two types of searching technique
1) Sequential Search 2) Binary Search
4. What is sorting?
- Sorting means Organizing data in ascending and descending order.
- Sorting data allows us to retrieve information faster and easier.
- There are some types of sorting techniques
1) Quick sort 2) Merge Sort 3) Bubble Sort
Que 2) Answer For Following:
1. What do you mean by Array? Describe the storage structure of Array.
Also explain various types of Array in detail.
- Array is a data structure containing a collection of elements or values.
- The size of an array is fixed in most languages.
- Arrays are called Homogeneous Data Structures because they store elements of the same
type.
We have to define the type of array at declaration time. Array can not allowed to store value of
different type in one array
- Array elements are stored at contiguous locations, this location has a unique number called
index. We can access a particular element of an array by its index value.
- When you define the size of the array, all of that space in memory is “reserved” from that time.
- To insert new element at 0 index, we move all the element from insertion place to right and
new element will be placed at 0 index
- Now the array is full we can’t insert new elements into an array. To insert new element we
have to copy all elements into a larger array. This operation is very expensive, time
consuming.
- After deleting the element from a particular index we have to move all elements that come
after the element that we deleted to the left side.
- There are two types of array
1) Single dimensional arrays
2) Multi dimensional arrays
- A dimensional is used representing the elements of the array for example
1)Single dimensional
- It is also called linear array
- In it each element is represented by a single subscript (eg: a[1] = 100).
- The elements are stored in consecutive memory locations.
- We can access the element of the single-dimensional array by providing the index of
the element with the array name.
2)Multi dimensional
- The Two Dimensional array is used for representing the elements of the array in the
form of the rows and columns and these are used for representing the Matrix.
- int a[2][2] - this will represent array contains 2 row and 2 column
- A two-dimensional array can be initialized by providing a list of the single-dimensional
arrays.
- The individual element can be accessed by providing both row and column index of the
array (eg: a[1][2] = 20)
Que 3) Answer For Following:
1. What is a Circular Linked List? State the Advantage and Disadvantage of
Circular Linked list over Doubly Linked list and Singly Linked list.
- A circular linked list is a sequence of elements in which every element has a link to its next
element in the sequence and the last element has a link to the first element.
- It is similar to the single linked list except that the last node points to the first node in the list.
- There is no NULL at the end. A circular linked list can be a singly circular linked list or
doubly circular linked list.
- The circular linked list has no beginning and no ending and there is no null value present in
the next part of any of the nodes. We can traverse a circular linked list until we reach the
same node where we started. It is the main difference between circular linked list and Linked
list.
- In circular doubly linked list we can traverse both directions.
- In circular doubly linked list each node has 2 pointers, Next and Back to points to Next and
the previous Node respectively, plus the next of last points to first Node(and vice versa) and
create circular path from both directions
Operations can be performed on a Circular linked list
- Insert a node at the beginning, at the end, and at a given location.
- Traversal in a circular list
- Deletion a node from the beginning, end, and given location
- Searching a data in a circular list
Advantages of Circular Linked Lists:
- In Circular Linked List, end node will point to first Node whereas in singly linked list it won’t
point to first Node.
- It doesn’t contain a NULL pointer
- Data structures such as stacks and queues are implemented with the help of the circular
linked lists.
- In the circular linked list we will traverse the node only one time. whereas in a doubly linked
list it's possible we will traverse the node more than one time.
- In a circular list, any node can be the starting point means we can traverse each node from
any point.
Disadvantage of Circular linked list:
- It's not easy to reverse a circular linked list.
- It may go in an infinite loop if not handled proper validation in code.
- It is not possible to access the random element because they are stored at random locations,
and we can only access them sequentially.
- It is not easy to maintain just like maintaining the doubly linked list
Que 4) Answer For Following:
1. _____ is not the operation that can be performed on a queue.
ANS - d. Traversal
[Link] of the following data structures can’t store the non-homogeneous data elements?
ANS - a. Arrays
3. Any node is the path from the root to the node is called……
ANS - c. Ancestor Node
4. Which data structure is used in breadth first search of a graph to hold nodes?
ANS - b. Queue
5. To represent hierarchical relationship between elements, which data structure is suitable?
ANS - c. Tree
6. A data structure where element can be added or removed at either end but not in the middle is
called…..
ANS - d. De-queue
7. In _____, search starts at the beginning of the list and checks every element in the list.
ANS - a. Linear Search
8. Which of the following data structures are indexed data structures?
ANS - a. Linear Arrays
SECTION - 2
Que 1) Perform Following Practicals. (Any Four)
***************************** Practical Files are attached with mail *****************************