Q9: Convert given binary tree into threaded binary tree. Analyze time and space complexity of the algorithm.

Other Questions in Data Structures and Algorithms Laboratory

See All Available Questions

Q1: Consider telephone book database of N clients. Make use of a hash table implementation to quickly look up client’s telephone number. Make use of two collision handling techniques and compare them using number of comparisons required to find a set of telephone numbers.
Q4: To create ADT that implements the 'set' concept. a. Add (new Element) - Place a value into the set b. Remove (element) - Remove the value c. Contains (element) - Return true if element is in collection d. Size() - Return number of values in collection e. Iterator() - Return an iterator used to loop over collection f. Intersection of two sets g. Union of two sets h. Difference between two sets i. Subset
Q5: A book consists of chapters, chapters consist of sections, and sections consist of subsections. Construct a tree and print the nodes. Find the time and space requirements of your method.
Q6: Beginning with an empty binary search tree, construct a binary search tree by inserting the values in the order given. After constructing the binary tree: i. Insert a new node ii. Find the number of nodes in the longest path from root iii. Find the minimum data value in the tree iv. Change the tree so that the roles of the left and right pointers are swapped at every node v. Search for a value
Q13: Represent a given graph using adjacency matrix/list to perform DFS and using adjacency list to perform BFS. Use the map of the area around the college as the graph. Identify the prominent landmarks as nodes and perform DFS and BFS on that.
Q14: There are flight paths between cities. If there is a flight between city A and city B then there is an edge between the cities. The cost of the edge can be the time that flight takes to reach city B from A, or the amount of fuel used for the journey. Represent this as a graph. The node can be represented by the airport name or name of the city. Use adjacency list representation of the graph or use adjacency matrix representation of the graph. Check whether the graph is connected or not. Justify the storage representation used.
Q18: Given sequence k = k1 < k2 < ... < kn of n sorted keys, with a search probability pi for each key ki. Build the Binary search tree that has the least search cost given the access probability for each key?
Q19: A Dictionary stores keywords and its meanings. Provide facility for adding new keywords, deleting keywords, updating values of any entry. Provide facility to display whole data sorted in ascending/ Descending order. Also find how many maximum comparisons may require for finding any keyword. Use Height balance tree and find the complexity for finding a keyword.
Q22: Read the marks obtained by students of second year in an online examination of a particular subject. Find out maximum and minimum marks obtained in that subject. Use heap data structure. Analyze the algorithm.
Q23: Department maintains a student information. The file contains roll number, name, division and address. Allow user to add, delete information of student. Display information of particular student. If record of student does not exist an appropriate message is displayed. If it is, then the system displays the student details. Use sequential file to maintain the data.
Q24: Company maintains employee information as employee ID, name, designation and salary. Allow user to add, delete information of employee. Display information of particular employee. If employee does not exist an appropriate message is displayed. If it is, then the system displays the employee details. Use index sequential file to maintain the data.