Deck 6: Problem Solving With Abstract Data Types

Question 1

Which of the following strings is a palindrome?

A)"bottle"
B)"beep"
C)"coco"
D)"r"

Answer 1

D

Question 2

The symbol AnBn is standard notation for the string that consists of ______.

A)an A,followed by an n,followed by a B,followed by an n
B)an equal number of A's and B's,arranged in a random order
C)n consecutive A's,followed by n consecutive B's
D)a pair of an A and a B,followed another pair of an A and a B

Answer 2

C

Question 3

Which of the following is a fully parenthesized expression?

A)x * y + z
B)(x * y)+ z
C)((x * y)+ z)
D)(x)* (y)+ (z)

Answer 3

C

Question 4

Which of the following is a prefix expression?

A)/ a + b c
B)a b c + /
C)a * b + c
D)a / (b +c)

Question 5

Which of the following is an infix expression?

A)/ a + b c
B)a b c + /
C)a b / + c
D)a / (b +c)

Question 6

If the string w is a palindrome,which of the following is true?

A)w minus its first character is a palindrome
B)w minus its last character is a palindrome
C)w minus its first and last characters is a palindrome
D)the first half of w is a palindrome
E)the second half of w is a palindrome

Question 7

The symbol • means ______.

A)separate
B)concatenate
C)multiply
D)select

Question 8

The correct grammar for the following language L: L = {w: w is of the form SⁿDⁿ for some n ≥ 0}
Is ______.

A) = S | | D
B) = empty string | S | | D
C) = S D
D) = empty string | S D

Question 9

In a grammar,the symbol x y means ______.

A)x or y
B)x followed by y
C)x or y or both
D)x multiplied by y

Question 10

In the Eight Queens problem,each column can contain ______.

A)exactly one queen
B)exactly two queens
C)at most two queens
D)at most three queens

Question 11

The statement: JavaPrograms = {strings w : w is a syntactically correct Java program}
Signifies that ______.

A)all strings are syntactically correct Java programs
B)all syntactically correct Java programs are strings
C)the JavaPrograms language consists of all the possible strings
D)a string is a language

Question 12

An empty string ______.

A)has a length of 0
B)has a length of 1
C)is not a valid string
D)has a negative value for its length

Question 13

______ is a problem-solving technique that involves guesses at a solution.

A)Recursion
B)Backtracking
C)Iteration
D)Induction

Question 14

In the recursive solution to the Eight Queens problem,the problem size decreases by ______ at each recursive step.

A)one square
B)two squares
C)one column
D)two columns

Question 15

A language is a set of strings of ______.

A)numbers
B)letters
C)alphabets
D)symbols

Question 16

Which of the following is a postfix expression?

A)/ a + b c
B)a b c + /
C)* a b c / +
D)a / (b +c)

Question 17

What is the value of the postfix expression: 6 7 + 8 2 - *?

A)-3
B)-10
C)48
D)78

Question 18

The Java ______ determines whether a given string is a syntactically correct Java program.

A)applet
B)editor
C)compiler
D)programmer

Question 19

In a grammar,the symbol x | y means ______.

A)x or y
B)x followed by y
C)x out of y
D)x divided by y

Question 20

Which of the following strings is NOT a palindrome?

A)"madam"
B)""
C)"adam"
D)"deed"

Question 21

Which of the following is NOT a valid postfix expression?

A)a b c - d *
B)a b - c d + -
C)a b c + /
D)a b * c + d *

Question 22

What is the value of the prefix expression: - * 3 8 + 6 5?

A)11
B)23
C)13
D)21

Question 23

The expression:
(a +b)/ c
is a fully parenthesized expression.

Question 24

Which of the following is NOT a valid prefix expression?

A)- + a b + c d
B)/ a + b c
C)* + * a b c d
D)* - a b c d

Question 25

Infix expressions do not need precedence rules.

Question 26

A string of length 1 is not a palindrome.

Question 27

The stricter the definition of a language,the easier it is for a compiler to recognize a syntactically legal expression.

Question 28

The empty string is a palindrome.

Question 29

______ can be used to prove properties about recursive algorithms.

A)Prefix notations
B)Postfix notations
C)Induction
D)Backtracking

Question 30

The Towers of Hanoi problem makes exactly ______ moves when it starts with N disks.

A)2ⁿ
B)2ⁿ - 1
C)N²
D)N³ - 1

Question 31

Which of the following is true about algebraic expressions?

A)parentheses are needed in all algebraic expressions
B)infix expressions do not require precedence rules
C)postfix expressions do not require association rules
D)fully parenthesized expressions are difficult to recognize and evaluate

Question 32

Which of the following is the prefix form of the infix expression: (8 + 6)/ (16 - 4)?

A)+ 8 6 / - 16 4
B)/ 8 6 + - 16 4
C)/ + ?- 8 6 16 4
D)/ + 8 6 - 16 4

Question 33

If the string w is a palindrome,the first and last characters of w are the same.

Question 34

Induction can be used to prove that a recursive algorithm is correct.

Question 35

Parentheses are not necessary in prefix expressions.

Question 36

Which of the following is the postfix form of the prefix expression: * + a b c?

A)a + b * c
B)a + b c *
C)a b + c *
D)a b * c +

Question 37

The following string is a valid prefix expression:
+ * a b c d

Question 38

Which of the following is the postfix form of the infix expression: a * b - (c +d)?

A)a b c d + - *
B)a b * c d + -
C)a b c - * d +
D)a b c - d + *

Question 39

According to the following statement:
JavaPrograms = {strings w : w is a syntactically correct Java program}
all strings are Java programs.

Question 40

What is the value of the infix expression: 8 * (5 - 2)?

A)16
B)24
C)38
D)40

Question 41

What is a fully parenthesized expression?

Question 42

What is backtracking?

Question 43

What is a recognition algorithm?

Question 44

What is meant by a grammar?

Question 45

For defining palindromes,why is it not enough to use just the empty string as a base case?

Question 46

Describe in your own words the language defined by this recursive definition:
< S > = @ | < W > | @ < S >
< W > = aab | aa < W > b

Question 47

Write a recursive definition for the set of positive odd numbers.

Question 48

What is the main benefit of using a grammar that is recursive?

Question 49

What are the two base cases in a recursive description of a palindrome?

Question 50

Explain how you would design a method,returning boolean,that determines if a string passed as a parameter satisfies this recursive definition.
< S > = < W > < W >
< W > = a | b | a < W > | b < W >

Question 51

What is an empty string?

Question 52

How can precedence and association rules be avoided in infix notation?

Question 53

When is the base case of the Eight Queens problem reached?

Question 54

What is the advantage of using prefix or postfix expressions instead of infix expressions?

Question 55

What is a closed-form formula?

Question 56

What is a prefix expression?

Question 57

According to the following statement:
JavaPrograms = {strings w : w is a syntactically correct Java program}
when is a given string a member of the language JavaPrograms?

Question 58

What is an infix expression?

Question 59

What is a postfix expression?

Question 60

What is the procedure for proving a statement by mathematical induction?