CS133 Finals

1.

1 point

It is a list in which the last node's link points to the first node of the list.

Doubly Linked list

Circularly linked list

Multilinked list

Singly linked list

2.

1 point

Which of the following is the infix expression of the expression tree of Figure 2?
B2

( A + B ) + D * C * ( F * ( G + H))

C * (A + B) + D * (F * (G + H))

C * (A * B) + D * (F * (G + H))

D * (A + B) + C * (F * (G + H))

3.

1 point

It is a repetitive process in which algorithm calls itself.

Recursion

Repetition

Iteration

4.

1 point

A linear list in which data can only be inserted at one end called the rear, and deleted from the other end, called the front.

stack

linked list

queue

tree

5.

1 point

Defined as the structure of file in a sequence of words characters organized into lines.

text file

block file

source file

linear file

6.

1 point

See algorithm 1. What would be returned if fxm is called as fxm(5,3)?

5

0

-3

6

7.

1 point

See algorithm 1. What would be returned if fxm is called as fxm(2,7)?
algo1

6

-3

0

3

8.

1 point

It is a node with an outdegree of zero.

siblings

Root

Ancestor

Leaf

9.

1 point

Given the postfix expression: A B * C D + - E +. What is the infix expression?

A * ( B - C ) + ( D + E )

A* B - ( C + D ) + E

A * B - C + D + E

(A * B) - C + ( D + E )

10.

1 point

Queues may be implemented using arrays or _______.

stacks

binary trees

linked list

graphs

11.

1 point

In a Binary Search Tree, the node with the largest value is found at the ____.

leaf

rightmost leaf

root

leftmost leaf

12.

1 point

The most commonly used notation for asymptotic complexity for estimating the rate of function growth that was introduced in 1894 by Paul Bachman.

big-Omega notation

big-Oh notation

little-Oh notation

big-Theta notation

13.

1 point

Consists of a nonempty set V of vertices and a possibly empty set E of edges, each edge being a set of two vertices from V

directed graph

digraph

multiple graph

simple graph

14.

1 point

What is the postfix equivalent of: A + B * C - D / E ?

ABC-+DE*/

ABC+*DE-/

ABC*+DE/-

ABC*+DE-/

15.

1 point

An algorithm for traversing a graph that was developed by John Hopcroft and Robert Tarjan.

breadth-first search

height-first search

width-first search

depth-first search

16.

1 point

Entries in a stack are "ordered". What is the meaning of this statement?

A collection of Stacks can be sorted.

Stack entries may be compared with the '<' operation.

The entries must be stored in a linked list.

There is a first entry, a second entry, and so on.

17.

1 point

See algorithm 2. What would be returned if fxm is called as fxm(12)?
algo5

19

45

0

21

18.

1 point

A/an _______ tree, originally called admissible tree, is one in which the height of the left and right subtrees of every node differ by at most one.

AVL

Huffman

LAV

ALV

19.

1 point

What is the preorder traversal of the binary tree in Figure 1?

A B C D E F G H I J K

A B F C G D E H I J K

A B C D E F G H J I K

D C E B A F H G I J K

20.

1 point

Queue is a _____.

LIFO list

FIFO list

FOFI list

FCSF list

21.

1 point

Enqueue operation inserts an element at the ____ of the queue.

front

middle

rear

top

22.

1 point

The sorting algorithm that problem remains which value to chose as the pivot or bound value.

insertion

merge

selection

quicksort

23.

1 point

What is the inorder traversal of the binary tree in Figure 1?
b1

D C E B A H F G I J K

A B F C G D E H I J K

D C E B A F H G I J K

D E C B H K J I G F A

24.

1 point

These are provided to create, write, read, rewind, and delete files.

records

system calls

file system

platform

25.

1 point

A sequence of words organized into loader record blocks

Compiler

Source file

Linker

Object file

26.

1 point

An algorithm used for finding a minimum spanning tree of a graph.

WFI Algorithm

Dijktra's Algorithm

Kuskal's Algorithm

Ford Algorithm

27.

1 point

A sequence of subroutines and functions, each of which is further organized as declarations followed by executable statement.

Source file

Linker

Compiler

Object file

28.

1 point

What kind of binary search tree traversal produces an ordered list?

preorder

postorder

breadth first

inorder

29.

1 point

In a Binary Search Tree, the node with the smallest value is found at the ____

root

rightmost leaf

leaf

leftmost leaf

30.

1 point

An algorithm used for finding the shortest path in a graph.

Dijktra's Algorithm

Kuskal's Algorithm

Tarjan's Algorithm

Hopcroft-Tarjan Algorithm

31.

1 point

Creating a/an ________ whenever a function is called allows a system to handle recursion properly.

function call

stack and queue

data structures

activation record

32.

1 point

The sorting starts by considering the two first elements of the array data, and if they are out of order, and interchange takes place.

insertion

bubble

quicksort

selection

33.

1 point

It consists of a finite set of elements called nodes and a finite set of directed lines called branches.

Tree

Graph

Pictograph

Data and Link

34.

1 point

An ordered collection of data in which each element contains the location of the next element.

Tree

Stack

Linked List

Queue

35.

1 point

The retrieve stack operation copies the item at the:

bottom of the stack

end of the stack

middle of the stack

top of the stack

36.

1 point

A sort method done by scanning an array of unsorted data from the bottom up, and two adjacent elements are interchanged if they are found to be out of order with respect to each other

selection

insertion

bubble

merge

37.

1 point

Which of the following is the postfix expression of the expression tree in Figure 2?

C A B * + D F G H + * * +

C A B + * D F G H + * + *

C A B + * D F G H + * * +

C A B + * D F G H * * + +

38.

1 point

If the character 'D', 'C', 'B', 'A' are placed in a stack (in that order), and then removed one at a time, and
placed a queue in what order will they be removed from the queue?

ABCD

ABDC

DCAB

DCBA

39.

1 point

See algorithm 2. What would be returned if fxm is called as fxm(10)?
algo4

0

19

45

21

40.

1 point

See algorithm 1. What would be returned if fun is called as fxm(15,3)?
algo3

9

-3

6

-6

41.

1 point

An aggregation of atomic and composite data types into a set with defined relationships.

data structure

linked list

atomic data

abstract data type

42.

1 point

Which of the following is a TRUE statement?

Linked lists allow random access of data and arrays do not.

Both arrays and linked lists allow random access of data

Arrays allow random accessing of data and linked lists do not.

Both arrays and linked lists do not allow random access of data.

43.

1 point

It is a sequence of characters organized into lines

source file

text file

object file

file heading

44.

1 point

A data structure in which the limitation of a tree which is of a hierarchical type is lifted. It is collection of nodes or vertices and the connections between.

graph

array

tree

linked list

45.

1 point

An undirected graph is said to be _____ when there is a path between any two vertices of the graph.

disconnected

minimal

connected

cycle

46.

1 point

Sorting by attempting to localize the exchanges of array elements by finding a misplaced element first and putting in its final place.

insertion

quicksort

selection

bubble

47.

1 point

Consists of a nonempty set V of vertices and a set E of arcs, where each arc is a pair of vertices from V.

pseudograph

directed graph

multiple graph

simple graph

48.

1 point

One difference between a queue and a stack is:

Stacks require linked lists, but queues do not.

Queues use two ends of the structure, stacks use only one.

Stack use two ends of the structure, queues use only one.

Queues require linked lists, but stacks do not.

49.

1 point

A graph is called a _____ if each of its edges has an assigned number.

multigraph

weighted graph

numbered graph

circuit

50.

1 point

What is the postorder traversal of the binary tree in Figure 1?
B3

A B F C G D E H I J K

D C E B A F H G I J K

D E C B H K J I G F A

A B C D E F G H I J K