sdp4

Re-balancing of AVL tree costs

• O(logn)

• O(nlogn)

• O(1)

• O(n)

In what tree, for every node the height of its left subtree and right subtree differs at least by one

• Threaded binary tree

• BST

• AVL tree

• Complete tree

Which of the following is true about the total number of nodes in a binary tree with depth two?

• It is at most four

• It is at most seven

• There is no bound on the number of nodes

• It is at most two

Which of the following is not a valid binary search tree?

The result of postfix expression: 4 2 + 3 5 1 - * +

• 18

• 10

• 15

• 8

The infix expression A+((B-C)*D) is correctly represented in prefix notation as

• A+BC-D*

• ABC-D*+

• +A*-BCD

• A+B-C*D

The result of postfix expression: 5 7 + 6 2 - *

• 40

• 38

• 46

• 48

The prefix expression reverse to postfix: * + A B + C D

• A B + C D + * *

• A B + C D + *

• None of them

• A B + C D * +

What the result of the following expression: 2 3 8 * + 4 48 4 2 + / 6 * + -

• -26

• 12

• -20

• -10

By definition, a(n)______ graph contains edges that can be traversed in either direction.

• undirected

• directed

• disconnected

• connected

Which of the following algorithms use a dynamic programming approach (not greedy)?
Выберите один или несколько ответов:

• Floyd Algorithm

• Bellman-Ford Algorithm

• Dijkstra Algorithm

• Prim Algorithm

What is the Run-time of the Dijkstra’s original algorithm? (without min priority queue)

• O(E+V)

• O(E+VlogV)

• O(E^2)

• O(V^2)

Choose the algorithm with not greedy approach ….

• Prim Algorithm

• Dijkstra Algorithm

• Floyd Algorithm

• Kruskal Algorithm

The Floyd-Warshall algorithm for all-pair shortest paths computation is based on:

• Greedy paradigm

• Dynamic Programming paradigm

• None

• Divide-and-Conquer paradigm

The following heap : 18 15 9 14 11 2 7 6 12 3, add there 17 and choose right sequence:

• 18 17 9 14 15 2 7 12 6 3 11

• 18 15 9 14 11 2 7 6 12 3 17

• 18 17 9 14 15 2 7 6 11 12 3

• 18 17 9 14 15 2 7 6 12 3 11

In the deletion operation of max heap, the root is replaced by:

• Last element of the last level

• Next available value in the right sub-tree

• Next available value in the left sub-tree

• Any random value from the heap

Delete max element from the heap and choose the answer: 18 17 9 14 15 2 7 6 12 3 11

• 17 15 9 14 12 11 2 7 6 3

• 17 15 9 14 11 2 7 6 12 3

• 17 9 14 15 2 7 6 12 3 11

• 17 15 14 12 11 9 2 7 6 3

In a min heap

• A minimum values are sorted

• Parent nodes have less value than child nodes

• Maximum value is contained by the root node

• Child nodes have less value than parent nodes

The result of this postfix expression: 10 5 + 60 6 / * 8 – is

• 82

• 284

• 273

• 142

Please find the postfix expression from prefix: - * - + a b c / e f - g / h i

• a b + c - - e f / * g h i / -

• a b + c - e f / * g h - i / -

• a b + c - e f / * g h i / -

• a b + c - e f / * g h i / - -

Number of possible binary trees with 3 nodes is (Kahoot 100%)

• 9

• 3

• 14

• 5

The result of this postfix expression: 4 5 7 2 + - *

• -10

• -11

• -16

• -5

Which of the following statements about binary trees is true?

• A binary tree contains exactly two nodes.

• Exactly two paths exist between any two nodes in a binary tree.

• Every node of a binary tree has at most two children.

• Every node of a binary tree has at most two predecessors.

A binary tree T has 20 leaves. The number of nodes in T having two children is

• Any number between 10 and 20

• 18

• 19

• 17

Choose the Bipartite graph from the following graphs...

Each of the following indicates a reasonable way to implement graphs except

• a BST

• a Boolean matrix

• an adjacency list

• an edge list

Postfix expression is just a reverse of prefix expression.

• Верно

• Неверно

Choose the regular expression which -- "Search all string which start with "a"

• a*

• a+

• a$

• ^a

Which of the following algorithms use a greedy approach?

• Prim, Kruskal, Floyd

• Prim, Kruskal, Dijkstra

• Prim, Bellman-Ford, Floyd

• Prim, Kruskal, Bellman-Ford

Heap with n elements with the smallest element at the root, 7 smallest element can be found

• O(1)

• O(n)

• O(nlogn)

• O(logn)

Group A Group B

a) Dijkstra's single shortest path algo p) Dynamic Programming

b) Bellmen Ford's single shortest path algo q) Greedy Algorithm

c) Floyd Warshell's all pair shortest path algo. r) Backtracking

• a-q, b-p, c-p

• a-p, b-p, c-p

• a-r, b-q, c-p

• a-p, b-r, c-q

Time complexity of Depth First Traversal of is

• Θ(|V|*|E|)

• Θ(|V|)

• Θ(|V|+|E|)

• Θ(|E|)

The time complexity of heap sort in worst case is

• O(nlogn)

• O(n)

• O(n2)

• O(logn)

Which of the following algorithms has lowest worst case time complexity?

• Quick sort

• Selection sort

• Insertion sort

• Heap sort

BST: 50, 15, 62, 5, 20,58, 91, 3,8 The number of nodes in the left of the root is

• 4

• 5

• 3

• 7

Heap is an example of

• BST

• Complete BST

• Spanning tree

• General tree

What is the run-time complexity of the Floyd-Warshall algorithm? (worst case performance)

• O(V^2)

• O(V*E)

• O(V+E)

• O(V^3)

For all binary search trees, where d represents the depth of a tree and n represents the number of nodes, the worst-case complexity of searching for an element is

• O(n/d)

• O(n*d)

• O(d)

• O(n)

Which of the following statements is true of both depth-first and breadth-first searches?

• Their implementations each require a stack of nodes.

• From a given starting node, they will not necessarily explore all other nodes in a graph.

• Their implementations each require a queue of nodes.

• They can each be used calculate the shortest path between two nodes in a weighted graph.

BST run-time complexity of search function in worst case is

• O(n)

• O(logn)

• O(n^2)

• O(nlogn)

In a binary min heap containing n numbers, the smallest element can be found in time

• O(1)

• O(logn)

• O(n)

• none of this

A full binary tree n leaves contains

• n nodes,

• 2n-1 nodes

• n nodes

• 2n nodes

Which one of the following array represents a binary max-heap?

• 25,12,16,13,10,8,14,

• 25,14,12,14,10,8,16

• 25,14,16,13,10,8,12

• 25,12,16,13,10,8,14

In a binary max heap containing n numbers,the smallest element can be found in time

• O(n)

• O(logn)

• O(1)

• O(nlogn)

The maximum number of nodes on level i of a binary tree is

• 2i-1

• i+1

• 3i-1

• 2i+2

Which algorithms – can find vertices x & y if there are presented a path between them?

• DFS

• BFS

• Both BFS and DFS

• None of them

What is the run-time complexity of the Kruskal's algorithm? (average performance)

• O(ElogV)

• O(V^3)

• O(VlogE)

• O(V^2)

How does the use of parenthesis change the expression tree? Which graph below represents the equation 3+2*4-1

What is the result of the program below?

#include <stdio.h>

int main(){

char *ch;

while(x=0; x<=255; x++)

printf(“ASCII value of %d character %c\n”,x,x);

return 0;

}

• The code prints all ASCII values and its characters

• Error: x undeclared identifier

• The code generates an infinite loop

• Error: while statement missing

What is the output of the following program?

#include <stdio.h>

int main(){

char *nstring=”Hello”;

while(*nstring)

printf(“%c”, *nstring++); }

• ello

• Runtime error

• Compile error

• Hello

What will be the output of the program?

#include <stdio.h>

int main(){

int k, num=30;

k=(num>5 ? (num <= 10? 100 : 200):500);

printf("%d\n", num);

return 0;

}

• 30

• 500

• 200

• 100

What statement can print \n on the screen?

#include <stdio.h>

int main(){

printf("\\n");

return 0;

}

• None

• printf(“n\”);

• printf(“\\n”);

• printf(“n”);

• printf(“\n”);

How many times the program will print “Hello”?

#include<stdio.h>

int main(){

printf("Hello");

main();

return 0;

}

• 0

• Compilation error

• Unlimited times

• Till stack run over

What is the built library function to compare two strings?

• IsEqual();

• Strcmp();

• Strcompare();

• Strstr();

According to ANSI specification, how to declare main() function with command-line arguments?

• int char main(int argc, *argv)

• None

• int main(){

  int char (*argv argc);

  }

• int main(int argc, char *argv[])

Queue worst time complexity to delete some value…

• O(1)

• O(n^2)

• O(log n)

• O(n)

What is the worst time complexity of the hash table in Big O notation?

• O(n logn)

• O(n)

• O(1)

• O(log n)

Stack works by the principle

• LILO

• FIFO

• LIFO

• FILO

Linked list is generally considered as an example of ____ type of memory allocation.

• Compile time

• Static

• Dynamic

• Local

An algorithm is

• A loosely written code to make final code

• A step by step procedure to solve problem

• All of the above

• A piece of code to be executed

What is the best time complexity of the binary search?

• O(n)

• O(1)

• O(log n)

• O(n logn)

Which sorting algorithms is most efficient to sort string consisting of ASCII characters?

• Quick sort

• None

• Counting sort

• Merge sort

A pivot element to partition unsorted list is used in

• Quick sort

• Insertion sort

• Merge sort

• Selection sort

What is the gcc?

• The command to create new file

• The command to show all errors during compiling

• The command doesn’t exist

• The compiler

What is rmdir command in Unix OS?

• This command creates a directory

• This command copies a file

• This command removes a file

• This command removes(deletes) a directory

What is touch command in Unix OS?

• This command builds products based on rules contained in a file

• This command updates the last modification time of a file or directory

• These commands allow you to view the contents of a file without editing the file

• This family of commands allows you to open files for editing

“.” In Unix like systems

• Refers to the containing directory

• Refers to your home directory

• Refers to the root directory

• Refers to the current directory

The default executable generation on Unix for a C program is

• a.exe

• default.out

• a.out

• out.a

In the given below statement,what does the “arr” indicate? char *arr[30];

• arr is a pointer to an array

• arr is a array of 30 characters

• arr is a array of function

• arr is a array of 30 character pointers

What function is used to free the allocated memory for the program below?
#include <stdio.h>
#include<stdlib.h>
int main(){
int *k;
k=(int*) malloc(10* sizeof(int));
return 0; }

• clean k;

• delete k;

• free(k);

• memfree(k);

Which library functions help users to dynamically allocate memory?

• malloc(), memalloc()

• macalloc(), calloc()

• realloc(), calloc()

• malloc(), calloc()

Which header statement is missing in the given below program to get the desired output?
#include <stdio.h>
int main(){
double x=1234321;
if(isdigit(x)){
printf("%lf",x);
return 0;
}

• #include <ctype.h>

• #include <math.h>

• #include <string.h>

• #include <stdlib.h>

Accessing top element in stack is constant time operation

• Верно

• Неверно

Process of Removing element from the stack is called as…(C++)

• push

• pop

• delete

• clean

A linked list in which the last node of Linked list points to the first is called a______

• doubly LL

• singly LL

• hybrid LL

• circular LL

A doubly linked list performs traversal in____

• none

• either direction

• circular direction

• any direction

LL is used to implement the Stack then which of the following node is - Top of the Stack?

• middle node

• first node

• any node

• last node

What is the worst time complexity of the binary search algorithm?

• O(1)

• O(logn)

• none

• O(n)

What is the worst time complexity of the bubble sort?

• O(n^2)

• O(n)

• O(nlogn)

• O(n^3)

Which of the following sorting algorithms has the lowest worst-case complexity?

• Bubble Sort

• Selection Sort

• Quick Sort

• Merge Sort

What is make command in Unix OS?

• This command builds products based on rules contained in a makefile

• This command compiles a Java program

• This command is most commonly used to display the contents of a file on the terminal

• This is the compiler, which can take many options

What is ls command in UNIX OS?

• This command creates a directory

• This command renames an entity

• This command list the contents of a directory

• This command displays the path of the current directory

Unix command mv ___

• This command renames an entity

• This command removes(deletes) a directory

• This command removes a file

• This command copies a file

The keyboard used to transfer control from a function back to the calling function is

• switch

• return

• go back

• go to

What is the result of the program?
#include<stdio.h>
int main() {
int const a = 5;
a++;
printf("%d", a);
}

• Stack is run over

• None

• 5

• Compilation error

What value strcmp() function returns when two strings are the same?

• true

• 0

• -1

• 1

Stack time complexity to insert some value …

• O(1)

• O(n)

• O(logn)

• O(n/logn)

Which if the following is not a type of Linked list?

• hybrid LL

• singly LL

• doubly LL

• circular LL

Queue can be implemented using a list

• Верно

• Неверно

Which of the following container has search efficiency of O(1) (Best case)

• Doubly Linked List

• Hash table

• Heap

• Linked List

“/” in Unix like systems

• refers to the current directory

• refers to the containing directory

• refers to your home directory

• refers to the root directory

Unix command pwd_____

• This command removes a file

• This command creates a directory

• This command displays manual pages for various commands

• This command displays the path of the current directory

A linked-list is a dynamic structure

• Верно

• Неверно

What are two operators for ascending members of a structure and when are they used?

• none

• and->

• and this

• and-->

What is the malloc & calloc?

• allocate the dynamic memory

• allocate the dynamic memory and save zero there

• create new variable

• free dynamic memory

A local variable is stored in __

• heap segment

• stack segment

• code segment

• none

Which scanf(statement will you use to scan a float variable (a) and double variable (b)?

• scanf(“%f%lf”, &a, &b);

• scanf(“%lf%lf”, &a, &b);

• scanf(“%f%f”, &a, &b);

• scanf(“%Lf%Lf”, &a, &b);

A single line comment in C language source code can begin with __

• :

• /*

• ;

• //

Only top element can be accessed in stack

• верно

• неверно

Each Node contain minimum two fields one field called data field to store data. Another field _

• pointer to Node

• pointer to character

• pointer to an integer

• pointer to class

A hash table of length 10 uses quadratic function h(k)=k mod 10. After inserting 6 values into an empty hash table, the table is as shown below.
0
1
2 42
3 23
4 34
5
6 52
7 46
8
9 33
Which one of the following choices given a possible order in which the key values could have been inserted in the table?

• 46, 42, 34, 52, 23, 33

• 34, 42, 23, 52, 33, 46

• 42, 23, 34, 52, 46, 33

• 46, 34, 42, 23, 52, 33

How do you specify double constant 3.14 as a long double?

• %Lf

• %ld

• %f

• %lf

What built in library function to adjust the allocated dynamic memory size

• calloc

• malloc

• recalloc

• realloc

Queue works by the principle

• Last in First out

• none

• First in First out FIFO

• First in Last out

How to convert some data to the lower case in C programming language?

• toupper(); #include <ctype.h>

• tolower();, #include <stdlib.h>

• toupper(); #include <stdlib.h>

• tolower();, #include <ctype.h>

How to create the boolean type in C without usage of #include <stdbool.h>

• _Bool

• boolean

• _Boolean

• bool

“r+” in fopen function tries to open the file for …

• read & write

• append new content to the file

• only reading this file

• reading and append new content to the file

Linked list works by the FIFO method

• верно

• неверно

What is best time complexity of search operation in the LL?

• O(logn)

• none

• O(1)

• O(n)

What is the general formula for double hashing in the hast table?

• h( k, i) = ( h1(k) + i * h2(k)) mod m

• none

• h(x) = x mod m

• h (k, i) = ( h’(k) + i^2) mod m

What function can be used to free the memory allocated by calloc()?

• delete();

• strcat();

• free();

• memfree();

Identify the incorrect file opening mode from the following

• r

• x

• w

• a

In the stack process of inserting an element in the stack is called as _____

• push

• insert

• pop

• create

What is the output of the following program?
#include <stdio.h>
int main(){
int a[] = {2,1};
printf("%d", *a);


}

• 2

• 0

• 1

• Compile error

The merge sort algorithm is based on:

• Divide-and-Conquer paradigm

• Greedy paradigm

• Dynamic Programming paradigm

• None of these

Recursion uses more memory space than iteration because

• None of them

• it uses stack instead of queue & every recursive call has to be stored

• every recursive call has to be stored

• it uses stack instead of queue

Shell sort uses

• quick sort

• insertion sort

• selection sort

• merge sort

What is the result of the program below?
#include <stdio.h>
int main(){
int a=9, b=&a, *pointer=b+0;
printf("%u", *pointer);
}

• Address of pointer

• Compile error

• Segmentation fault

• 9

• 0

Add element “K” in the following max heap: g,c,f,b,a,d

• None of them

• c,g,b,a,d,f,k

• k,c,g,b,a,d,f

• c,g,b,a,k,d,f

What is the run-time complexity of the Floyd-Warshall algorithm?(best case performance)

• O(V*E)

• O(V+E)

• O(V^3)

• O(V^2)

The Dijkstra and the Bellman-Ford algorithms both determine

• the shortest path between all nodes in a graph

• the shortest path between two nodes in a graph

• whether a graph is directed or undirected

• the edge with the greatest weight in a graph

• whether or not a graph is a tree

Choose the algorithm with not-greedy approach

• Prim Algorithm

• Floyd Algorithm

• Dijkstra Algorithm

• Kruskal Algorithm

What are two operators for accessing members of a structure and when are they used?

• . and->

• . and this

• None

• . and--->

\ What is the difference between a and a+ modes?

• a - open for appending, a+ - open for reading and appending

• a - open for reading and appending, a+ - open for appending

• a -open for appending, a+ - open for reading and writing

• a - open for appending, a+ - open for writing and appending

The nodes of a ______linked list can be traversed_____.

• Singly, forward and backward

• Doubly, forward only

• Doubly, backward only

• Singly, forward only

What is the formula to calculate the load factor of hash table? (n number of elements, m size of table)

• ɻ= n/m

• ɻ =n*m

• ɻ =n/sqrt(m)

• ɻ =n/m^2

Which of the following is a balanced tree for the numbers 1-9? There may be more than one answer.