CS5343 Dec 7, 2021 - Set 1

docx

School

University of Texas, Dallas *

*We aren’t endorsed by this school

Course

5343

Subject

Computer Science

Date

Feb 20, 2024

Type

docx

Pages

10

Uploaded by MasterRhinoceros3614

Report
CS5343 Algorithms and Data Structures Exam-2 Dec 7, 2021 Please write using PEN First Name:__________________________ Last Name: ______________________________ Student #:________________________ 1. (10 points) You are given a single linked list. The list has at least 3 nodes. The number of nodes in the list is odd. Write a recursive algorithm to find the middle node. You can only traverse the list once, so you cannot count the number of nodes in the list. Your function can have up to 2 arguments (not more). You cannot use global variables or static variables. Also do not modify the list structure. You may write the main function start the recursive function. Then write the recursive function. The list is defined as follows: Node { Int val; Node *next; } Main() { Mid( ………………………. ); Mid( tmp1, tmp2 ) {
2. (10 points) Binary tree node is defined as follows: Node { Int Val; Node *rchild; Node *lchild; } You are given a binary tree. Write a recursive algorithm that would return the mirror image of the tree. Do not use any more arguments or global variables. Mirror (root1, root2 ) {
3. (10 points) In a directed graph, give the algorithm to determine if the graph is strongly connected or weakly connected. 4. The following is a red-black tree. (10 points) a. Delete the node 17 and then 18. Show the steps and the final tree after deletions.
Your preview ends here
Eager to read complete document? Join bartleby learn and gain access to the full version
  • Access to all documents
  • Unlimited textbook solutions
  • 24/7 expert homework help
b. In the following tree insert 22 and then 24. Show the steps and the final tree after insert
5. Use Dijkstra’s algorithm to show the SPT for the following graph. Use the node A as the starting point. Show each step (10 points)
6. (4 points) Explain transitive closure use a figure to explain it. 7. Define the terms degree, in-degree and out-degree of a graph. Show by an example of each. (6 points)
Your preview ends here
Eager to read complete document? Join bartleby learn and gain access to the full version
  • Access to all documents
  • Unlimited textbook solutions
  • 24/7 expert homework help
8. Find the Minimum spanning tree from A, using Kruskal’s Algorithm for the following graph. (10 points)
9. (10 points) Radix sort (LSD) the following list of 5 digit numbers showing each step in the sort. 62203, 4007, 31932, 42745, 61962, 25, 3, 927, 4207, 213
10. (10 points)Consider the set of initially unrelated elements 6, 7, 8, 9, 11, 10, 13, 12, 15, 14, 18, 17, 16. Draw the final forest of up-trees that results from the following sequence of operations using on union-by-size. Break ties by keeping the first argument as the root. Union(6,8), Union(9,10), Union(15,13), Union(15,9), Union (12,14), Union(12,6), Union(18,12), Union(7,17), Union(15,12). 11. 10 points) Demonstrate the insertion of keys 32, 14, 50, 261, 270, 450, 324, 17, 10 into a hash table. The collisions resolved by quadratic probing.
Your preview ends here
Eager to read complete document? Join bartleby learn and gain access to the full version
  • Access to all documents
  • Unlimited textbook solutions
  • 24/7 expert homework help
Let the hash table have 7 slots, and the hash function is h(k) = sum of each digit of K.

Related Documents

two_layer_nn.pdf
Assignment 6 Analyze Skilled Dialogue and an IEP Meeting.pdf
midterm1-23w-soln.pdf
DAD 220 3-2 Table Joins.pdf
midterm1-23w.pdf
exam-11-february-winter-2013-questions-and-answers.pdf
CS5343 - Mid Term - Spring 2021.docx
Program Evaluation.docx
final_exam.txt
Quiz5__CS434001-Advanced_Database_Systems.pdf
info102lab1questions.pdf
Barnacle Lab work.docx
Recommended textbooks for you
Text book image
Programming Logic & Design Comprehensive
Computer Science
ISBN:9781337669405
Author:FARRELL
Publisher:Cengage
Text book image
Programming with Microsoft Visual Basic 2017
Computer Science
ISBN:9781337102124
Author:Diane Zak
Publisher:Cengage Learning
Text book image
Systems Architecture
Computer Science
ISBN:9781305080195
Author:Stephen D. Burd
Publisher:Cengage Learning
Text book image
Np Ms Office 365/Excel 2016 I Ntermed
Computer Science
ISBN:9781337508841
Author:Carey
Publisher:Cengage
Text book image
C++ for Engineers and Scientists
Computer Science
ISBN:9781133187844
Author:Bronson, Gary J.
Publisher:Course Technology Ptr
Text book image
EBK JAVA PROGRAMMING
Computer Science
ISBN:9781337671385
Author:FARRELL
Publisher:CENGAGE LEARNING - CONSIGNMENT
SEE MORE TEXTBOOKS
Recommended textbooks for you
Text book image
Programming Logic & Design Comprehensive
Computer Science
ISBN:9781337669405
Author:FARRELL
Publisher:Cengage
Text book image
Programming with Microsoft Visual Basic 2017
Computer Science
ISBN:9781337102124
Author:Diane Zak
Publisher:Cengage Learning
Text book image
Systems Architecture
Computer Science
ISBN:9781305080195
Author:Stephen D. Burd
Publisher:Cengage Learning
Text book image
Np Ms Office 365/Excel 2016 I Ntermed
Computer Science
ISBN:9781337508841
Author:Carey
Publisher:Cengage
Text book image
C++ for Engineers and Scientists
Computer Science
ISBN:9781133187844
Author:Bronson, Gary J.
Publisher:Course Technology Ptr
Text book image
EBK JAVA PROGRAMMING
Computer Science
ISBN:9781337671385
Author:FARRELL
Publisher:CENGAGE LEARNING - CONSIGNMENT
SEE MORE TEXTBOOKS