Showing 4-6 out of 16
FE-May18-Sol.pdf-Page 1 of 4 Computer Science
FE-May18-Sol.pdf-Page 1 of 4 Computer Science
FE-May18-Sol.pdf-Page 1 of 4 Comput...
FE-May18-Sol.pdf-Page 1 of 4 Computer Science
Page 4
Summer 2018
Data Structures Exam, Part A
Page
4
of
4
3)
(10 pts) DSN (Stacks)
(a)
(6 pts)
Convert the following infix expression to postfix using a stack.
Show the contents of the
stack at the indicated points (1, 2, and 3) in the infix expression.
1
2
3
A
+
B
*
(
( C
/ D
)
+
E *
F
)
*
G
*
+
(
(
*
*
*
+
+
+
1
2
3
Resulting postfix expression:
A
B
C
D
/
E
F
*
+
*
G
*
+
Grading:
1 point for each stack, 3 points for the whole expression (partial credit allowed.)
(b)
(4 pts) Whenever a recursive function is called, the function calls go onto a call stack. The
depth of the call stack is the number of different recursive calls on the stack at a particular point
in time, which indicates the number of different recursive calls that have started, but have not
completed. What is the maximum stack depth of the call stack when the function fib(10) is
executed? Is this maximum stack depth equal to the number of times the recursive function, fib,
is called? Assume the implementation of the Fibonacci function shown below:
int fib(int n) {
if (n < 2) return n;
return fib(n-1) + fib(n-2);
}
Maximum Stack Depth:
10
(Grading: 2 pts for 10 or 9, 1 pt to be within 3, 0 pts otherwise)
Is Max Stack Depth equal to the # of recursive calls?
YES
NO
(Circle the correct answer.)
Grading: 2 pts correct, 0 otherwise
Page 5
Page
1
of
4
Computer Science Foundation Exam
May 19, 2018
Section I B
DATA STRUCTURES
SOLUTION
NO books, notes, or calculators may be used,
and you must work entirely on your own.
Name:
___________________________________________
UCFID:
___________________________________________
NID:
Question #
Max Pts
Category
Score
1
10
DSN
2
5
ALG
3
10
ALG
TOTAL
25
You must do all 3 problems in this section of the exam.
Problems will be graded based on the completeness of the solution steps and not
graded based on the answer alone.
Credit cannot be given unless all work is shown
and is readable. Be complete, yet concise, and above all be neat. For each coding
question, assume that all of the necessary includes (stdlib, stdio, math, string) for that
particular question have been made.
Page 6
Summer 2018
Data Structures Exam, Part B
Page
2
of
4
1)
(10 pts) DSN (Binary Search Trees)
Complete writing function shown below
recursively
, so that it takes in a pointer to the root of a binary
search tree,
root
,
and an integer,
value
, and returns the number of nodes in the tree that are divisible by
value
. The struct used to store a node is shown below.
typedef struct bstNode {
struct bstNode *left, *right;
int data;
} bstNode;
int countDiv(bstNode *root, int value){
if (root == NULL) return 0;
//2 pts
// 4 pts, 2 pts for each recursive call.
int res = countDiv(root->left, value) +
countDiv(root->right, value);
// 2 pts for checking divisibility, 1 pt for adding 1
if (root->data % value == 0)
res++;
// 1 pt for returning.
return res;
}
Ace your assessments! Get Better Grades
Browse thousands of Study Materials & Solutions from your Favorite Schools
University of Pune
University_of_Pune
School:
Computer_Science_I
Course:
Great resource for chem class. Had all the past labs and assignments
Leland P.
Santa Clara University
Introducing Study Plan
Using AI Tools to Help you understand and remember your course concepts better and faster than any other resource.
Find the best videos to learn every concept in that course from Youtube and Tiktok without searching.
Save All Relavent Videos & Materials and access anytime and anywhere
Prepare Smart and Guarantee better grades
Know more
Students also viewed documents
lab 18.docx
lab_18.docx
Course
Course
3
Module5QuizSTA2023.d...
Module5QuizSTA2023.docx.docx
Course
Course
10
Week 7 Test Math302....
Week_7_Test_Math302.docx.docx
Course
Course
30
Chapter 1 Assigment ...
Chapter_1_Assigment_Questions.docx.docx
Course
Course
5
Week 4 tests.docx.do...
Week_4_tests.docx.docx
Course
Course
23
Week 6 tests.docx.do...
Week_6_tests.docx.docx
Course
Course
106
