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:

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

#### 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