COMP2521-Exercises - The practise exercises for Final Practical part of test PDF

Preview

Summary

The practise exercises for Final Practical part of test...

Description

Linked Lists 1. ListIsOrdered: determines whether a linked list is sorted in either ascending, descending or no order. Returns true if list is sorted, and false otherwise.

2. NumDupesInOrderedList: returns the number of duplicate elements in the linked list. The number of duplicate elements is the minimum number of elements that would need to be removed to obtain a list with no duplicates.

3. ReverseDLList: reverses a doubly linked list

4. ListDeleteLargest: deletes the largest value from a list and returns that value.

5. ListSetUnion: take two lists representing two sets and return a new list that represent the union of those sets (no duplicates).

6. ListSetIntersection: takes two lists repreenting two sets and return a new list that represents the intersection of those sets (only duplicates).

7. ListIsPalindromic: determines whether a linked list is palindromic.

Trees and BSTs 1. BSTreeInsert: inserts a given value into a BST, if it does not already exist, and returns the root of the updated BST.

2. BSTreePostfix: prints out the values of a BST in postfix order

3. BSTreeGetSmallest: returns a pointer to the node containing the smallest value in a BST. If the tree is empty, return NULL.

4. TreeHeight: returns the height of a BST. The height of a tree is the number of edges on the longest path from the root node to a lead node. The height of an empty tree is considered to be -1.

5. BSTreeNodeDepth: returns the depth of the node containing the given key in the tree if it exists, or -1 otherwise.

6. TreeSumOdds: returns the sum of all the odd values in a BST.

7. TreeIsPerfectlyBalanced: determines whether a BST is perfectly balanced. A tree is perfectly balanced if, for every node, the difference in size between its left and right subtrees does not exceed 1.

Graphs 1. DepthFirstSearch (recursive)

2. BreadthFirstSearch

3. ShortestDistance: returns the number of edges on the shortest path between two vertices. If there is no path return -1.

4. NumReachable: returns the number of vertices that are reachable from a source vertex, including the source vertex itself.

5. FurthestReachable: returns the furthest vertex that is reachable from a source vertex. If there are multiple furthest vertices, return the one with the largest vertex number. If the source vertex is not connected to any other vertices, return the source vertex.

6. NumWithin: returns the number of vertices that are within a given distance of the source vertex....