Font size
WorksheetsA2 CS P2 - Knowledge check mmd
Total questions: 120
Worksheet time: 2hrs 55mins
Procedural programming lays stress on?
Data
Functions
Object
Class
________ is wrapping of data into a single unit called class.
Abstraction
Polymorphism
Encapsulation
Inheritance
__________ refers to the act of representing essential details.
Polymorphism
Abstraction
Inheritance
Encapsulation
__________ is the process in which objects of one class can link and share some common properties from the objects of another class.
Abstraction
Inheritance
Polymorphism
Encapsulation
__________ is the process of using a function for more than one purpose. It allows the use of different internal structures of the object by keeping the same external interface.
Inheritance
Polymorphism
Abstraction
Encapsulation
An _________ is an instance or of a copy of a class.
Class
Object
Attribute
A ________ is blue print that defines certain characteristics and behavior. It is simply a representation of different types of objects.
Class
Object
Attribute
Characteristics
Select all the given characteristic of OOP
Data structures are designed such that they characterize the objects.
C input/output is based on library and the processes are carried out by including functions.
Programs are divided into what are known as objects.
Emphasis is on data rather than procedure
(from Greek meaning “many forms”) is the quality that allows one interface to access a general class of actions.
Polymorphism
Inheritance
Encapsulation
Object-Oriented Programming
Is the process by which one object can acquire the properties of another object.
Polymorphism
Inheritance
Encapsulation
Object-Oriented Programming
A programming mechanism that binds together code and the data it manipulates, and that keeps both safe from outside interference and misuse.
Polymorphism
Inheritance
Encapsulation
Object-Oriented Programming
What is the returned value of recMethod(5)?
68
70
75
82
What is printed as a result of the call stringMaker("COMPSCI")?
COMPSCI
COMPSC
COMPS
COMP
COM
CO
C
COMPSCI
OMPSCI
MPSCI
PSCI
SCI
CI
I
CO
COM
COMP
COMPS
COMPSC
COMPSCI
C
CO
COM
COMP
COMPS
COMPSC
COMPSCI
What is returned as a result of the call mystery(4,6)?
2
3
4
1
Which of the following is not done by abstraction?
Identifies essential details
Disregards non-essential information
Breaks the problem down into smaller tasks
Which of the following is not done by decomposition?
Allows multiple people to work on the problem together
Disregards non-essential information
Breaks the problem down into smaller tasks
When designing a building that must be accessible for wheelchairs, which of the following characteristics is non-essential?
Number of doors
Number of walls
Number of wall paintings
When drawing a dog, which of the following characteristics is non-essential?
Dogs have 4 paws
Dogs have fur
Dogs have brown fur
Indicate constant time complexity in terms of Big-O notation
O(n)
O(1)
O(log n)
O (n^2)
Indicate exponential time complexity in terms of big-O notation
O (n)
O (n^2)
O (2^n)
O (log n)
Find the slowest time complexity
O (n)
O (n^2)
O (n!)
O (2^n)
Which notation is consistent for every execution?
O (n)
O (n^2)
O (1)
O (2^n)
The O (n!) is so inefficient, there is no practical use for it
True
False
Which notation grows in proportion to the size of the input
O (n)
O (n^2)
O (1)
O (2^n)
Which notation would you usually use for a nested loop?
O (n)
O (n^2)
O (1)
O (2^n)
Indicate polynomial time complexity in terms of big-O notation
O (n!)
O (1)
O (n^2)
O (log n)
When calculating the Big-O for an algorithm, which of the following rules is not true?
Focus on the dominant term
Disregard any constants
Focus only on polynomials
Count the number of assignments
A linear function takes the form
f(n) = an + b
f(n) = an2 +bn + c
f(n) = alog2n
f(n) = a + b
A quadratic function takes the form
f(n) = an + b
f(n) = an2 +bn + c
f(n) = alog2n
f(n) = a + b
A logarithmic function takes the form
f(n) = an + b
f(n) = an2 +bn + c
f(n) = alog2n
f(n) = a + b
1 + 3n + n
3 + n
3n
1 + 3n
Which line best represents the time complexity n!
Orange
Blue
Green
Red
Pink
Which line best represents the time complexity log n
Orange
Blue
Green
Red
Pink
Which line best represents the time complexity n
Orange
Blue
Green
Red
Pink
Which of the following usees FIFO method
Queue
stack
linklist
binary tree
This form of access is used to add and remove nodes from a queue.
LIFO, Last In First Out
FIFO, First In First Out
Both a and b
none
Consider the following operation performed on a stack of size 5.
Push(1);
Pop();
Push(2);
Push(3);
Pop();
Push(4);
Pop();
Pop();
Push(5);
After the completion of all operation, the number of elements present on stack are
1
2
3
4
The following circular queue can accommodate a maximum six elements with the following data
front = 2 rear = 4
queue = ____; L ; M; N; ___; ___
What will happen after ADD O operation takes place?
front = 2 rear = 5
queue = ______; L, M, N, O, ___
ront = 3 rear = 5
queue = L, M, N, O, ___
front = 3 rear = 4
queue = ______; L, M, N, O, ___
ront = 2 rear = 4
queue = L, M, N, O, ___
What method is used to add an element to a Queue?
dequeue()
enqueue()
push()
pop()
What method is used to add an element to a Stack?
dequeue()
enqueue()
push()
pop()
What method is used to remove an element from a Queue?
dequeue()
enqueue()
push()
pop()
What method is used to view the next element to be removed from a stack?
dequeue()
NextItem()
peek()
pop()
Which method is called in a PUSH() method
IsEmpty()
IsFull()
Which method is called in a POP() method
IsEmpty()
IsFull()
If I want to find out if an item is in a queue or a stack - what do I call?
Contains(item)
IsContains(item)
Peek(item)
Find(item)
What is the reason for using a circular queue instead of a regular queue?
running time of enqueue is improved
reuse empty space
you can traverse the elements more efficiently
none of the above
Circular queue is also known as
circular buffer
ring buffer
curve buffer
rotating buffer
One difference between stack and queue?
queues require dynamic memory,but stack do not
stacks use two ends of the structure,queue use only one
stacks requires dynamic memory ,but queues do not
queues uses two ends of the structure,stack use only one
If the element "A B C D" are placed in a stack and are deleted one at a time
in what order will they be removed?
ABCD
DBCA
DCBA
DABC
If FRONT= REAR then the queue is?
overflow
underflow
empty
null
Entries in a stack are “ordered”. What is the meaning of this statement?
a collection of stacks is sortable
stack entries may be compared with the '<' operation
the entries are stored in a linked list
there is a Sequential entry that is one by one
Consider Stack is implemented using the array.
#define MAX 10
struct STACK
{
int arr[MAX]
int top = ___________;
}
What will be the initial value with which top is initialized.
0
-1
garbage
1
A data structure in which elements can be inserted or deleted at/from
both the ends but not in the middle is?
queue
circular queue
dequeue
priority queue
In linked list implementation of a queue,the important condition for a queue to be empty is?
REAR is NULL
FRONT is 1
REAR is 1
FRONT is NULL
Which algorithm requires a pivot
Flow chart
Bubble sort
Quick sort
Bin packing
Where every vertex is directly connected to all other vertices by a single edge is a....
simple graph
tree
spanning tree
complete graph
Dijkstra's algorithm finds...
Minimum spanning tree
Minimum distance between two vertices
Hamiltonian cycle
Route through all the vertices
When using Dijkstra's algorithm you must show all working values
True - show all values
True - unless they are higher
False - only the final value is required
12, 6, 8, 1, 3
How many searches would it take to find the number 1?
Which of these sorting algorithms is the most efficient?
Merge sort
Bubble sort
Insertion sort
Selection sort
Which of these sorting algorithms uses recursion?
Merge sort
Bubble sort
Insertion sort
Selection sort
For which algorithm would it be best to use a conditional loop?
Finding largest number in a list
Calculating average of a list of numbers
Counting occurrences of an item in a list
Checking if an item is in a list
For which algorithm would it be best to use an unconditional loop?
Validating username and password
Adding up numbers in a list
Finding first occurrence of a number in a list
Validating user input for date of birth
What would the list [9, 6, 12, 7, 3, 16, 10] look like after one iteration of the Bubble sort algorithm (smallest to biggest)?
[6, 9, 7, 3, 12, 10, 16]
[3, 9, 6, 12, 7, 16, 10]
[3, 6, 7, 9, 10, 12, 16]
[9, 6, 12, 3, 7, 16, 10]
Which of these algorithms is an example of a divide-and-conquer type algorithm?
Bubble sort
Binary search
Linear search
Count occurrences
What is the standard Scientific measurement for measuring algorithm efficiency?
Big-O notation
Scientific notation
Floating-point
Mbps
This is the main loop from an algorithm (shown in pseudocode.) Which algorithm is it?
Insertion sort
Bubble sort
Merge sort
Binary search
What is the value of the ROOT node in this Tree?
35
24
42
20
Root
data structure similar to a graph, with no loops.
an object in a graph also known as a vertex
a join of relationship between nodes - also know as an arc
the starting node in a rooted tree structure from which all other nodes branch off./
Tree
data structure similar to a graph, with no loops.
an object in a graph also known as a vertex
a join of relationship between nodes - also know as an arc
the starting node in a rooted tree structure from which all other nodes branch off./
How many leaf are there in the tree?
1
3
4
7
Which of these tree traversal methods is used to output the contents of a binary tree in ascending order?
Pre-Order
In-Order
Post-Order
Monastic Orders
What are the 3 depth traversals for a tree data structure?
Pre-, In- and Post-order
Pro-, In- and Past-order
Pre-, Out- and Post-order
Pre-, In- and New-order
When traversing a binary tree, which diagram is post-order?
When traversing a binary tree, which diagram is pre-order?
A Data Structure is:
A C++ vector
A way of organizing, storing and performing operations on data.
A function in any programming language
A sequence of steps to solve a problem.
Given a sequence of number below:
50,60,40,70,45,55,30,80,65,35,25,75,85
When creating a binary search tree, what is the height of the tree?
3
4
5
6
Given a binary search tree, insert 27, 15, 63, 99, 70 and 85 (in this order) into the binary search tree. What is the post-order traversal?
5,15,27,34,47,54,63,70,72,75,83,85,88,94,99,101
72,54,34,5,27,15,47,63,70,83,75,88,85,101,94,99
15,27,5,47,34,70,63,54,75,85,99,94,101,88,83,72
15,27,5,47,34,63,54,70,75,85,99,94,101,88,83,72
none of the above
Hashing gives each item
A sequential address
A logarithmic address
No address
A unique address
A hash table is
an abstract data structure
an array
an integer
made of pine
Address <----- key MOD(numberOfSlots)
IF KEY = 5432 and numberOfSlots = 1000
Address = ?
5
432
543
5432
when an algorithm generates the same address for different primary keys it is known as
Knock
Bang
Collisions
DoubleHash
What is the status after adding 10
What is the status after adding 7
Which data structure cannot have elements of different data types?
Array
Tuple
Record
Stack
Queue
In terms of data structures, what does mutable mean?
A mutable structure is one which can only have data added to it
A mutable structure is one which is fixed in size
A mutable structure is one which allows data to be added, edited, deleted or moved
When a collision occurs with a hashing function, what is one method for dealing with the collisions?
creating a new list at that index
creating a new array
creating a new hash table
creating a new binary tree
Which word describes lot of collisions with using hashing?
contiguous
traffic
clustering
mutable
Linear Probing in relation to Hash Tables...
is checking the length of a Hash Table
is a process of going through each Index one by one looking for a desired value
Assigning the next empty key value to resolve a collision
a personal part of someones medical history
Which of the following is/are the advantages of Linked list?
Insertion and deletion of elements can be done efficiently
It uses dynamic memory allocation
Memory utilization is efficient compared to arrays
Which of the following is/are not the dis-advantage of Linked list?
Linked list does not support random access
Memory is required to store next field
Searching takes time compared to arrays
None of the above
Give syntax to create a node for Single linked list?
newnode=(struct node *)malloc(sizeof(struct node*));
newnode=(struct node )malloc(sizeof(struct node));
newnode=(struct node *)malloc(sizeof(struct node));
newnode=(struct node )malloc(sizeof(struct node*));
Give routine to insert at the beginning in a linked list whose structure is by struct node, with list head as L and pointer variable as next
newnode->next=next;
L=newnode;
newnode->next=node;
L=newnode;
newnode->next=L;
L=newnode;
newnode->L=next;
L=newnode;
How to insert a node after a position P in singly linked list?
Newnode -> data = P ;
Newnode -> next = p ->next ;
P -> next = newnode ;
Newnode -> data = x ;
Newnode -> next = p ->next ;
P -> next = L ;
Newnode -> data = x ;
Newnode -> next = p ->node ;
P -> nextnode = next ;
Newnode -> data = x ;
Newnode -> next = p ->next ;
P -> next = newnode ;
Which of the following is application of Singly Linked List?
moving pages forward and backward in browser
Giving chance to each player in a multi player game
Implementing Stack
Which of the following is application of Doubly Linked List?
moving pages forward and backward in browser
Giving chance to each player in a multi player game
Implementing Stack
Which of the following is application of Cicularly Linked List?
moving pages forward and backward in browser
Giving chance to each player in a multi player game
Implementing Stack
The main advantage of using a _______ linked list is that it makes searching twice as efficient.
a)Singly
b)doubly
c)circular
d)None
Choose the correct statement in the below comparison of an array and a linked list?
a.The size of an array is similar to size of linked list is variable.
b.In array, the data elements are stored in continuous memory locations but in linked list, it is non continuous memory locations.
c. Addition, removal of data is tedious in linked list whereas in arrays it is easy.
d. None
What is the worst case time complexity of linear search algorithm?
A - Ο(1)
B - Ο(n)
C - Ο(log n)
D - Ο(n2)
What data structure is used for breadth first traversal of a graph?
A - queue
B - stack
C - list
D - none of the above
If the array is already sorted, which of these algorithms will exhibit the best performance
A - Merge Sort
B - Insertion Sort
C - Quick Sort
D - Heap Sort
What about recursion is true in comparison with iteration?
A - very expensive in terms of memory.
B - low performance.
C - every recursive program can be written with iteration too.
D - all of the above are true!
Quick sort running time depends on the selection of
A - size of array
B - pivot element
C - sequence of values
D - none of the above!
A pivot element to partition unsorted list is used in
A - Merge Sort
B - Quick Sort
C - Insertion Sort
D - Selection Sort
