UVT licenta quiz question bank

Discrete Structures and Algorithms Algorithms and Data Structures #10

What is the complexity of inserting a new item in a sorted linked list of integers, such that the list remains sorted?

○

O(1).

○

Θ(1).

✓

O(n).

○

Θ(log n).

Discrete Structures and Algorithms Algorithms and Data Structures #11

What data structure can we use to implement an iterative pre-order tree traversal?

○

Queue

✓

Stack

○

Hash Table

○

Red-black tree.

Discrete Structures and Algorithms Algorithms and Data Structures #12

What is the complexity of computing the median ?

✓

Θ(n).

○

$Θ(n$ log $n)$ .

○

Θ(1).

○

$Θ(n^2)$ .

Discrete Structures and Algorithms Algorithms and Data Structures #13

In a red-black tree which of the following is not necessarily true? There may be several correct answers.

✓

The root is red.

○

The root is black.

✓

Every path from the root to leaves has the same number of red nodes.

✓

A black parent can only have red children.

Discrete Structures and Algorithms Algorithms and Data Structures #14

Which of the following is correct? There may be several correct answers.

○

The worst-case complexity of insert, delete, search operations in a binary search tree is O(log n).

✓

The worst-case complexity of insert, delete, search operations in an AVL tree is O(log n).

○

The worst-case complexity of insert, delete, search operations in a splay tree is O(log n).

✓

The worst-case complexity of insert, delete, search operations in a red-black tree is O(log n).

Discrete Structures and Algorithms Algorithms and Data Structures #15

Which of the following sorting algorithm is not subject to the $Ω(n\ log\ n)$ lower bound for sorting?

✓

Counting sort.

○

Heapsort.

✓

Radix Sort.

○

MergeSort.

Discrete Structures and Algorithms Algorithms and Data Structures #16

Consider two strings A = "abcca" and B = "abacbcaa". Let x be the length of the longest common subsequence (not necessarily contiguous) between A and B and let y be the number of such longest common subsequences between A and B. Then x + 100y = . . ..

○

304.

○

305.

○

405.

✓

205.

Discrete Structures and Algorithms Algorithms and Data Structures #17

Suppose we sort n ≥ 3 values using quicksort, and after the first pivoting there are equally many numbers on the left of the pivot as they are on the right. Which of the following are true? There may be multiple answers.

○

All the elements could have been the pivot.

✓

The pivot is the median

✓

The pivot is not the maximum.

○

none of the other statements.

Discrete Structures and Algorithms Algorithms and Data Structures #18

What is the second operation needed for inserting a value x at the front of a singly linked list? We assume the list is represented by one pointer head only.

○

allocate a node with the value x.

✓

x.next = head.

○

head.prev = x

○

head = x.

○

none of the other options.

Discrete Structures and Algorithms Algorithms and Data Structures #19

A binary min-heap is a data structure which models an almost complete binary tree which has the heap property: For every node N with a parent P, the key of P is smaller than the key of N.
The array-based implementation of a binary min-heap with n nodes is an array $A[0...2m − 1]$ with two extra attributes:
the capacity $A.length$ = $2m − 1$ and the size $A.size = n$ , such that $A.size ≤ A.length$ .
The elements in the nodes of the binary min-heap are stored in the first $n$ elements of $A$ :
the root is stored in $A[0]$ , and if $N$ is the left (resp. right) child of a node $P$ stored in $A[i]$ then $N$ is stored in $A[2 · i + 1]$ (resp. $A[2 · i + 2]$ ).
For $0 ≤ i, j < n$ we define the relation $grandpa(i, j)$ if $A[j]$ stores the parent of the parent of $A[i]$ .
What is the formula which defines the relation $grandpa(i, j)$ in a binary min-heap ?

✓

$(4 · j + 3 ≤ i) ∧ (i ≤ 4 · j + 6)$

○

$(4 · i + 3 ≤ j) ∧ (j ≤ 4 · i + 6)$ .

○

$j = ⌊i/4⌋$ .

○

$(4 · j + 1 ≤ i) ∧ (i ≤ 4 · j + 2)$

Discrete Structures and Algorithms Algorithms and Data Structures #20

A binary min-heap is a data structure which models an almost complete binary tree which has the heap property: For every node N with a parent P, the key of P is smaller than the key of N.
The array-based implementation of a binary min-heap with n nodes is an array $A[0...2m − 1]$ with two extra attributes: the capacity $A.length$ = $2m − 1$ and the size $A.size = n$ , such that $A.size ≤ A.length$ .
The elements in the nodes of the binary min-heap are stored in the first $n$ elements of $A$ :
the root is stored in $A[0]$ , and if $N$ is the left (resp. right) child of a node $P$ stored in $A[i]$ then $N$ is stored in $A[2 · i + 1]$ (resp. $A[2 · i + 2]$ ).
What is the maximum number of nodes in a binary min-heap with depth $h$ ?

✓

$2^{h+1} − 1$

○

$2^h$ .

○

$h^2 − 1$ .

○

$2^{h−1} + 1$ .

Discrete Structures and Algorithms Algorithms and Data Structures #21

A binary min-heap is a data structure which models an almost complete binary tree which has the heap property: For every node N with a parent P, the key of P is smaller than the key of N.
The array-based implementation of a binary min-heap with n nodes is an array $A[0...2m − 1]$ with two extra attributes: the capacity $A.length$ = $2m − 1$ and the size $A.size = n$ , such that $A.size ≤ A.length$ .
The elements in the nodes of the binary min-heap are stored in the first $n$ elements of $A$ :
the root is stored in $A[0]$ , and if $N$ is the left (resp. right) child of a node $P$ stored in $A[i]$ then $N$ is stored in $A[2 · i + 1]$ (resp. $A[2 · i + 2]$ ).
i) If $A$ is a binary min-heap then $A$ is sorted in the ascending order of the keys from its nodes? True / False
ii) If $A$ is sorted in the ascending order of the keys from its nodes then $A$ is a binary min-heap? True/False

○

(i) True (ii) False

✓

(i) False (ii) True

○

(i) False (ii) False

○

(i) True (ii) True

Discrete Structures and Algorithms Algorithms and Data Structures #22

A binary min-heap is a data structure which models an almost complete binary tree which has the heap property: For every node N with a parent P, the key of P is smaller than the key of N.
The array-based implementation of a binary min-heap with n nodes is an array $A[0...2m − 1]$ with two extra attributes: the capacity $A.length$ = $2m − 1$ and the size $A.size = n$ , such that $A.size ≤ A.length$ .
The elements in the nodes of the binary min-heap are stored in the first $n$ elements of $A$ :
the root is stored in $A[0]$ , and if $N$ is the left (resp. right) child of a node $P$ stored in $A[i]$ then $N$ is stored in $A[2 · i + 1]$ (resp. $A[2 · i + 2]$ ).
For $0 ≤ i, j < n$ we define the relation $grandpa(i, j)$ if $A[j]$ stores the parent of the parent of $A[i]$ .
What is the runtime complexity of the deletion of the node with minimum key from a binary min-heap with $n$ nodes?

✓

$O($ log $n)$

○

$O(1)$

○

$Θ(n$ log $n)$

○

$Θ(n)$

Discrete Structures and Algorithms Computational Logic #1

Consider the predicate logic language that contains the following symbols:
• variables, indicated with lower case letters
• function symbols $F$ : $+$ binary infix, $−$ unary prefix, $∗$ binary infix.
• predicate symbols $P: =,<, ≤$ all binary, infix.
• constant symbols $C: 0, 1$ .
Which of the following are terms over this language?

○

$(0 ∗ x) − 1$ ,

○

$1 + (z ∗ x) < 0$ ,

✓

$x + ((−1) ∗ 0)$ ,

✓

$0 ∗ (y + 1)$ .

Discrete Structures and Algorithms Computational Logic #2

For the following propositional formulae, and for the truth valuation {P, ¬Q}:

○

((P ⇒ Q) ∧ ((¬Q) ∧ P)) evaluates to $\mathbb{T}$ ,

✓

((P ⇒ Q) ⇒ (Q ⇒ P) evaluates to $\mathbb{T}$ ,

✓

((¬(P ∨ Q)) ∧ (¬Q)) evaluates to $\mathbb{F}$ .

Discrete Structures and Algorithms Computational Logic #3

Which of the following statements are true:

✓

if a propositional formula is valid then it is satisfiable,

○

if a propositional formula is not valid then it is satisfiable,

✓

if a propositional formula is not valid then its negation is satisfiable,

○

if a propositional formula is not valid, then its negation is valid.

Discrete Structures and Algorithms Computational Logic #4

What is the relation between propositions
$(F ∧ G) ⇒ H$ and
$F ⇒ (G ⇒ H)$ .

✓

they are logically equivalent,

✓

the first one is a logical consequence of the second one,

✓

the second one is a logical consequence of the first one,

○

they are not related in any of the ways above.

Discrete Structures and Algorithms Computational Logic #5

The formula: $P ⇔ Q$ is _____ the formulas: $Q ⇒ R, R ⇒ (P ∧ Q), P ⇒ (Q ∨ R)$ .

○

logically equivalent to the conjunction of

✓

a logical consequence of

○

logically equivalent to the disjunction of

Discrete Structures and Algorithms Computational Logic #6

Which of the following formulae are in Disjunctive Normal Form?

✓

$P$ ,

✓

$¬P ∨ Q$ ,

✓

$P ∧ ¬Q ∧ S$ ,

✓

$(P ∧ ¬Q ∧ S) ∨ ¬S$ .

Discrete Structures and Algorithms Computational Logic #7

What is a resolvent of clauses {P, ¬Q, R} and {¬P, Q, S}?

○

$∅$ ,

✓

$\{P, ¬P, R, S\}$ ,

○

$\{R, S\}$ .

Discrete Structures and Algorithms Computational Logic #8

To establish whether a formula $G$ is a logical consequence of formulae $F_1, . . . , F_n$ , which of the following methods can be applied:

○

check that $(F_1 ∧ . . . ∧ F_n) ⇒ G$ is unsatisfiable,

○

check that $¬F_1 ∨ . . . ∨ ¬F_n ∨ G$ is unsatisfiable,

✓

check that $¬F_1 ∨ . . . ∨ ¬F_n ∨ G$ is valid,

✓

check that $F_1 ∧ . . . ∧ F_n ∧ ¬G$ is unsatisfiable.

Discrete Structures and Algorithms Computational Logic #9

There is a formula which is logically equivalent to

which contains only propositional connectives taken from:

✓

$\{¬, ∨\}$ ,

○

$\{∨, ∧\}$ ,

✓

$\{|\}$ , where $|$ is the NAND connective (i.e. $P|Q = ¬(P ∧ Q)$ ).

✓

$\{⊥, ⇒\}$ .

Discrete Structures and Algorithms Computational Logic #10

The clause set corresponding to the formula $(¬P ⇒ (Q ∧ R)) ⇒ (P ⇒ ¬Q)$ is:

✓

$\{\{¬P, ¬Q\}\}$ ,

○

$\{\{P, ¬Q\}, \{P, R\}, \{¬Q, R\}\}$ ,

○

$\{\{P, ¬Q, ¬R\}, \{P, Q, R\}, \{¬P, ¬Q, R\}\}$ .

Discrete Structures and Algorithms Computational Logic #11

Consider the clause set containing the following clauses:
$(1) \{P, Q, ¬R\},$
$(2) \{¬P, R\}$ ,
$(3) \{P, ¬Q, S\}$ ,
$(4) \{¬P, ¬Q, ¬R\}$ ,
$(5) \{P, ¬S\}$ .
The formula corresponding to this clause set is:

○

valid,

✓

satisfiable,

○

unsatisfiable.

Discrete Structures and Algorithms Computational Logic #12

The Davis-Putnam method returns the answer satisfiable:

○

when the empty clause is generated,

✓

when the empty clause set is generated,

✓

when no new clauses can be generated, and the empty clause is not in the clause set.

Question Bank