Answers by Kapil / GATE Overflow for GATE CSE

4 votes

91

GATE Overflow | Data Structures | Test 1 | Question: 1
The following C function takes a singly-linked list of integers as a parameter and rearranges the elements of the list. The function is called with the list containing the integers 1,2,3,4,5,6,7 in the given order. What will be the contents of the list after the function completes ... 2,1,3,4,5,6,7 2,1,4,3,6,5,7 1,3,2,5,4,7,6 2,3,4,5,6,7,1

The following C function takes a singly-linked list of integers as a parameter and rearranges the elements of the list. The function is called with the list containing th...

553 views

answered Oct 21, 2016

6 votes

92

TCP-Congestion Control

1.4k views

answered Oct 21, 2016

9 votes

93

Pipeline Efficiency
Will it be 6 or 7?

Will it be 6 or 7?

4.3k views

answered Oct 21, 2016

6 votes

94

Basic doubt in B+ Tree Indexing
Q : One basic doubt that is coming to my mind is whether number of splits in the process of insertion in B+ Tree indexing going to change if we consider left biasing and right biasing approach.Plz present any example to show if possible..

Q : One basic doubt that is coming to my mind is whether number of splits in the process of insertion in B+ Tree indexing going to change if we consider left biasing and ...

1.1k views

answered Oct 19, 2016

3 votes

95

Memory
This is physically addressed so We have to search in TLB first but my question is if it is a HIT in TLB why do we need to search in Cache It should be only TLB(hit)*{Tlb access time + memory access time} and if there is miss in TLB then we look in the cache and Secondary meory Am I correct or Something is missing???

This is physically addressed so We have to search in TLB first but my question is if it is a HIT in TLB why do we need to search in Cache It should be only TLB(hit)...

532 views

answered Oct 19, 2016

9 votes

96

Operating System
Difference between with clear example Hadrware Interrupt, External Interrupt Software Interrupt, Internal Interrupt

Difference between with clear exampleHadrware Interrupt, External InterruptSoftware Interrupt, Internal Interrupt

1.3k views

answered Oct 19, 2016

16 votes

97

Operating System
Consider a paging system which stores its two-level page table in memory and its 16 most recently referenced entries in a TLB. If, a memory access takes 80 nsec, a TLB lookup takes 20 nsec and a page swap time takes 5000 nsec, how long does a data item take to access if the TLB hit rate is 95% and the page fault rate is 10% ?

Consider a paging system which stores its two-level page table in memory and its 16 most recently referenced entries in a TLB. If, a memory access takes 80 nsec, a TLB lo...

3.9k views

answered Oct 17, 2016

6 votes

98

Doubt in some basic things synchronisation
I have some fundamental doubts regarding the conditions which need to be followed for a correct synchronisation solution i.e. about mutual exclusion , progress and bounded wait. I m asking these. Plz address to these doubts but give a ... for the fact whether the bounded wait condition is satisfied or not? Also plz support your answer with proper reason..

I have some fundamental doubts regarding the conditions which need to be followed for a correct synchronisation solution i.e. about mutual exclusion , progress and bounde...

1.3k views

answered Oct 14, 2016

1 votes

99

GATE Overflow | Data Structures | Test 1 | Question: 29
Which of the following is false? Arrays are better than linked lists for sorting due to better data locality. Asymptotic time complxity for FindMax is same on an unsorted array as that on a singly linked list. A doubly linked list ... as of a singly linked list. Given a fixed maximum size, a circular queue is preferrable to a normal queue

Which of the following is false?Arrays are better than linked lists for sorting due to better data locality.Asymptotic time complxity for FindMax is same on an unsorted a...

897 views

answered Oct 13, 2016

1 votes

100

GATE Overflow | Data Structures | Test 1 | Question: 6
In an administrative office it is required to keep track of the application requests. An applicant can push his application forward by paying extra money. What would be an appropraite datastructure for storing the applications? Stack Queue Linked Lists Priority Queue

In an administrative office it is required to keep track of the application requests. An applicant can push his application forward by paying extra money. What would be a...

391 views

answered Oct 13, 2016

3 votes

101

GATE Overflow | Data Structures | Test 1 | Question: 10
With 5 distinct nodes, the maximum no. of binary trees that can be formed is _____

With 5 distinct nodes, the maximum no. of binary trees that can be formed is _____

839 views

answered Oct 13, 2016

4 votes

102

GATE Overflow | Data Structures | Test 1 | Question: 19
What is the chromatic number of the following graph?

What is the chromatic number of the following graph?

509 views

answered Oct 13, 2016

2 votes

103

GATE Overflow | Data Structures | Test 1 | Question: 21
A vertex having no incident edge is called --------- pendent vertex end vertex isolated vertex none of these

A vertex having no incident edge is called -pendent vertex end vertexisolated vertex none of these

617 views

answered Oct 13, 2016

6 votes

104

GATE Overflow | Data Structures | Test 1 | Question: 24
You are given a linked list, $L$ of $n$ integers, and another linked list, $P$, of $k$ integers where $k <<< n$. $L$ is sorted in ascending order but $P$ is not necessarily sorted. The operation $\text{print_lots}(L,P)$ will ... space is available) ______________ ? $\Theta(n)$ $\Theta(n \log k)$ $\Theta(n k)$ $\Theta (n k\log k)$

You are given a linked list, $L$ of $n$ integers, and another linked list, $P$, of $k$ integers where $k <<< n$. $L$ is sorted in ascending order but $P$ is not necessari...

1.1k views

answered Oct 13, 2016

5 votes

105

GATE Overflow | Data Structures | Test 1 | Question: 20
Consider a complete graph on 10 vertices. Minimum no. of edge removals required to make a tree out of it will be ____

Consider a complete graph on 10 vertices. Minimum no. of edge removals required to make a tree out of it will be ____

635 views

answered Oct 13, 2016

2 votes

106

GATE Overflow | Data Structures | Test 1 | Question: 18
The maximum number of possible edges in an undirected simple graph with $100$ vertices and $5$ components is ___

The maximum number of possible edges in an undirected simple graph with $100$ vertices and $5$ components is ___

525 views

answered Oct 13, 2016

7 votes

107

GATE Overflow | Data Structures | Test 1 | Question: 27
Consider a complete graph of 10 vertices. The minimum no. of edge removals required to make the graph disconnected is ______

Consider a complete graph of 10 vertices. The minimum no. of edge removals required to make the graph disconnected is ______

672 views

answered Oct 13, 2016

5 votes

108

GATE Overflow | Algorithms | Test 1 | Question: 28
Match the following i. Dijkstra's Algorithm a. All pairs shortest path ii. Bellman Ford Algorithm b. Greedy iii. Floyd-Warshall Algorithm c. Reweighting iv. Johnson Algorithm d. Single source shortest path i - c, ii - d, iii - a, iv - b i - d, ii - a, iii - c, iv - b i - b, ii - d, iii - a, iv - c i - d, ii - b, iii - a, iv - c

Match the following i.Dijkstra's Algorithma.All pairs shortest pathii.Bellman Ford Algorithmb.Greedyiii.Floyd-Warshall Algorithmc.Reweightingiv.Johnson Algorithmd.Single ...

468 views

answered Oct 12, 2016

6 votes

109

GATE Overflow | Algorithms | Test 1 | Question: 19
Is an array that is sorted in decreasing order a max-heap? always yes always no sometimes only yes but not in presence of duplicates

Is an array that is sorted in decreasing order a max-heap?always yesalways nosometimes onlyyes but not in presence of duplicates

657 views

answered Oct 12, 2016

6 votes

110

GATE Overflow | Algorithms | Test 1 | Question: 8
Is the following implementation of hashCode() legal assming a hashtable of size 20? public int hashCode(x) { return 17; } yes no because it fills only one slot no because it does not ensure uniform filling no because the hashcode is independent of the key

Is the following implementation of hashCode() legal assming a hashtable of size 20?public int hashCode(x) { return 17; }yesno because it fills only one slotno because it ...

710 views

answered Oct 12, 2016

1 votes

111

GATE Overflow | Algorithms | Test 1 | Question: 5
If k is a non-negative constant, then the solution to the recurrence $T(n) = \begin{cases} 1 & \quad n=1 \\ 3T(n/2) + n & \quad n>1 \end{cases} $ for $n$, a power of 2 is $T(n) = 3^{\log_2 n} - 2n$ $T(n) = 2 \times 3^{\log_2 n} - 2n$ $T(n) = 3 \times 3^{\log_2 n} - 2n$ $T(n) = 3 \times 3^{\log_2 n} - 3n$

If k is a non-negative constant, then the solution to the recurrence$T(n) = \begin{cases} 1 & \quad n=1 \\ 3T(n/2) + n & \quad n>1 \end{cases} $for $n$, a power of 2 is ...

934 views

answered Oct 12, 2016

5 votes

112

GATE Overflow | Algorithms | Test 1 | Question: 23
About how many compares will Quicksort() make when sorting an array of N items that are all equal? $\Theta(\lg N)$ $\Theta(N\lg N)$ $\Theta(\lg \lg N)$ $\Theta(N/\lg N)$

About how many compares will Quicksort() make when sorting an array of N items that are all equal?$\Theta(\lg N)$$\Theta(N\lg N)$$\Theta(\lg \lg N)$$\Theta(N/\lg N)$

832 views

answered Oct 12, 2016

3 votes

113

#OS

293 views

answered Oct 8, 2016

2 votes

114

Asymtotic
If f(n)=O(g(n)) for f,g are non decreasing functions ,then f(n)*log2(f(n)c) =O(g(n) * log2g(n)) , c is power of f(n) is a)Always true b) Never c) Sometimes true , sometimes not depending on f,g d) Sometimes true, sometimes false depending on c

If f(n)=O(g(n)) for f,g are non decreasing functions ,thenf(n)*log2(f(n)c) =O(g(n) * log2g(n)) , c is power of f(n) isa)Always trueb) Neverc) Sometimes true , sometimes ...

506 views

answered Oct 7, 2016

5 votes

115

made easy test series

958 views

answered Oct 7, 2016

5 votes

116

Let M range over Turing machine descriptions. Consider the set REG and let the complement of REG be Co-REG.

Let M range over Turing machine descriptions. Consider the set REG= {M | L(M) is a regular set} and let the complement of REG be Co-REG. Which of the following is true?(A...

1.4k views

answered Oct 6, 2016

4 votes

117

Halting Problem of Turing Machines
Can anyone provide the proof of halting problem of turing machines by contradiction ? If possible, give example, how is it reduced to other turing problems ?

Can anyone provide the proof of halting problem of turing machines by contradiction ? If possible, give example, how is it reduced to other turing problems ?

2.1k views

answered Oct 4, 2016

6 votes

118

MADE EASY TEST SERIES
Consider the following language. L = {wxwy | x,y,w∈(a+b)+} How many states are there in equivalent NFA for above L?

Consider the following language.L = {wxwy | x,y,w∈(a+b)+}How many states are there in equivalent NFA for above L?

468 views

answered Oct 2, 2016

6 votes

119

online

681 views

answered Oct 2, 2016

8 votes

120

Online

1.5k views

answered Oct 1, 2016

tags	tag:apple
author	user:martin
title	title:apple
content	content:apple
exclude	-tag:apple
force match	+apple
views	views:100
score	score:10
answers	answers:2
is accepted	isaccepted:true
is closed	isclosed:true