VILASRAO DESHMUKH FOUNDATION GROUP OF INSTITUTIONS, LATUR
Plot No.165A, Additional MIDC, Near to Manjara Sugar, Barshi Road, Latur, Maharashtra 413531
(Approved by AICTE, New Delhi & recognized by Govt. of Maharashtra and affiliated to DBATU Lonere, Dist. Raigad)
T (02382) 267731/32/33 [Link]@[Link] Website: [Link] (DTE Code: 2254)
Department of Computer Engineering
Subject Name: Data Structures
Subject Code:BTCOC303 Date: 5/12/2023 Time:11.30 to 12.00pm
Max. Marks : 10
Q.1 Attempt any two of the following. Level/CO Marks
[Link] Selection sort algorithms sort 10 numbers by using selection sort CO1 5
method.
2. Write Short note on Skip Lists CO2 5
[Link] the difference between Sequential and Binary Searching with an CO1 5
example.
Model Answer Set for Data Structure CA 2 Examination
[Link] Selection sort algorithms sort 10 numbers by using selection sort method..
Ans:
Selection Sort Algorithm:
Selection sort is a simple comparison-based sorting algorithm. The idea is to repeatedly select
the smallest (or largest, depending on sorting order) element from the unsorted portion of the list
and swap it with the element at the beginning of the unsorted portion.
Steps of Selection Sort:
1. Start with the first element: Consider the first element in the array as the minimum.
2. Find the minimum element in the unsorted part of the array (from the current element to
the last).
3. Swap the found minimum element with the first element of the unsorted portion.
4. Move the boundary of the sorted portion one element ahead.
5. Repeat the process until the entire array is sorted.
Example: Sorting 10 Numbers Using Selection Sort
Let's say we have the following unsorted array:
[64, 25, 12, 22, 11, 90, 77, 52, 17, 36]
Pass 1:
Find the minimum element (11) in the whole array.
Swap 64 with 11.
Array after pass 1: [11, 25, 12, 22, 64, 90, 77, 52, 17, 36]
Pass 2:
Find the minimum element (12) in the remaining unsorted part of the array ([25, 12, 22,
64, 90, 77, 52, 17, 36]).
Swap 25 with 12.
Array after pass 2: [11, 12, 25, 22, 64, 90, 77, 52, 17, 36]
Pass 3:
Find the minimum element (17) in the remaining unsorted part ([25, 22, 64, 90, 77, 52,
17, 36]).
Swap 25 with 17.
Array after pass 3: [11, 12, 17, 22, 64, 90, 77, 52, 25, 36]
Pass 4:
Find the minimum element (22) in the remaining unsorted part ([22, 64, 90, 77, 52, 25,
36]).
No swap needed as 22 is already in its correct position.
Array after pass 4: [11, 12, 17, 22, 64, 90, 77, 52, 25, 36]
Pass 5:
Find the minimum element (25) in the remaining unsorted part ([64, 90, 77, 52, 25, 36]).
Swap 64 with 25.
Array after pass 5: [11, 12, 17, 22, 25, 90, 77, 52, 64, 36]
Pass 6:
Find the minimum element (36) in the remaining unsorted part ([90, 77, 52, 64, 36]).
Swap 90 with 36.
Array after pass 6: [11, 12, 17, 22, 25, 36, 77, 52, 64, 90]
Pass 7:
Find the minimum element (52) in the remaining unsorted part ([77, 52, 64, 90]).
Swap 77 with 52.
Array after pass 7: [11, 12, 17, 22, 25, 36, 52, 77, 64, 90]
Pass 8:
Find the minimum element (64) in the remaining unsorted part ([77, 64, 90]).
Swap 77 with 64.
Array after pass 8: [11, 12, 17, 22, 25, 36, 52, 64, 77, 90]
Pass 9:
Find the minimum element (77) in the remaining unsorted part ([77, 90]).
No swap needed, as 77 is already in its correct position.
Array after pass 9: [11, 12, 17, 22, 25, 36, 52, 64, 77, 90]
Pass 10:
The last element (90) is already in its correct position.
Final Sorted Array:
[11, 12, 17, 22, 25, 36, 52, 64, 77, 90]
This is the sorted array using the selection sort algorithm.
[Link] short note on Skip lists.
Ans:
Skip Lists:
Skip lists are a data structure that allows for fast search, insertion, and deletion operations. They
are an extension of a linked list with additional layers of pointers to speed up access to elements.
Key Features of Skip Lists:
1. Multiple Levels:
o A skip list consists of several levels, with each level being a subset of the level
below it.
o The bottom level is a standard linked list containing all elements.
o Higher levels contain fewer elements and serve as "shortcuts" for faster traversal.
2. Probabilistic Balancing:
o Skip lists use randomization to decide which elements appear at higher levels.
o This randomness ensures efficient average-case performance without requiring
complex rebalancing like in balanced trees.
3. Search Efficiency:
o Searching in a skip list involves starting at the highest level and moving
downward.
o This enables O(log n) average time complexity for search, similar to binary
search trees.
4. Space Usage:
o Skip lists require additional memory for pointers at higher levels but are still
space-efficient compared to trees.
Advantages of Skip Lists:
Simple Implementation: Easier to implement compared to balanced trees like AVL or
Red-Black trees.
Dynamic Updates: Insertions and deletions are straightforward and do not require
complex rebalancing.
Efficient: Provides logarithmic time complexity for search, insert, and delete operations.
Disadvantages:
Randomization Dependence: Performance depends on the quality of the random
number generator.
Extra Space: Requires additional pointers for each level, leading to higher memory
usage.
Applications:
Databases: Used in indexing for fast access.
Caching: As a backend for in-memory data stores like Redis.
Priority Queues: Can be adapted for implementing priority queues.
[Link] the difference between Sequential and Binary Searching with an
example.
Ans:
Difference Between Sequential Search and Binary Search
Aspect Sequential Search Binary Search
Searches each element one by one until the Divides the list into halves and
Definition
target is found or the list ends. searches in a sorted list.
Requires the list to be sorted
Precondition Works on both sorted and unsorted lists.
beforehand.
Slower for large lists. Time complexity: Faster for large lists. Time
Efficiency
O(n). complexity: O(log n).
Slightly more complex to
Implementation Simple to implement.
implement.
Target is in the middle of the list
Best Case Target is found at the first position (O(1)).
(O(1)).
Target is not present or is at the last Target is not present or is at one
Worst Case
position (O(n)). end of the list (O(log n)).
Use Cases Small lists or unsorted data. Large lists with sorted data.
Example
Given List: [10, 20, 30, 40, 50]
Target: 30
1. Sequential Search:
Start from the first element and compare each one with the target.
Steps:
1. Compare 10 with 30 → Not a match.
2. Compare 20 with 30 → Not a match.
3. Compare 30 with 30 → Match found.
Result: Found in 3 comparisons.
2. Binary Search:
Requires the list to be sorted.
Steps:
1. Find the middle element: 30 (at index 2).
2. Compare 30 with 30 → Match found.
Result: Found in 1 comparison.
