Computer System Structures Interview Questions Part5

59) Question: From the given data
Bytes/Sector = 500
Sectors/Track = 50
Tracks/Platter = 150
Platters/ Hard Disk = 10
Data Transfer rate = 10 millisecs per byte
Total number of millisecs taken to transfer all the bytes in the hard disk?
1) 500 x 50 x 10 x 10
2) 500 x 50 x 150 x 10
3) 500 x 50 x 150 x 10 x10
4) 500 x 150 x 10 x10
Answer: 3
60) From the given data
Bytes/Sector = 500
Sectors/Track = 50
Tracks/Platter = 150
Platters/ Hard Disk = 10
Data Transfer rate = 10 millisecs per byte
Total number of millisecs taken to transfer the bytes from one single platter?
1) 500 x 50 x 150 x 10
2) 500 x 50 x 10
3) 500 x 150 x 50 x 10
4) 500 x 150 x 10 x10
Answer: 1
61) From the given data
Bytes/Sector = 500
Sectors/Track = 50
Tracks/Platter = 150
Platters/ Hard Disk = 10
Data Transfer rate = 10 millisecs per byte
Total number of milliseconds taken to transfer all the bytes from a cylinder cylinder?
1) 500 x 50 x 10 x 10
2) 500 x 150 x 50
3) 500 x 150 x 10 x10
4) 50 x 150 x 10 x10
Answer: 1
62) In a Hard disk,
Bytes per sector = 512
Sectors/track = 63
Number of Magnetic disks = 5
Tracks / platter = 50
Total number of bytes in a cylinder is ________
13) 512X 63X 5
14) 512X 50X 5
15) 512X 63 X 50
16) 512 X 5
Answer: 1
63) In a Hard disk,
Bytes per sector = 512
Sectors/track = 63
Number of Magnetic disks = 5
Tracks / platter = 50
The total number of bytes/platter is _____
17) 512X 63X 5
18) 512X 50X 5
19) 512X 63 X 50
20) 512 X 5
Answer: 3
64) In a Hard disk,
Bytes per sector = 512
Sectors/track = 63
Number of Magnetic disks = 5
Tracks / platter = 50
The total number of cylinders in the hard disk is_______.
1) 63
2) 50
3) 512
4) 63 X 5
Answer: 2
65)The size of single unit of allocation on disk is called ____.
5) Sector size
6) Page size
7) Segment size
8) File size
Answer: 1
66) MS-DOS supports multiprogramming fully. True / False?
Answer: False
67) Which of the following is crucial time while accessing data on the disk?

1) Seek time
2) Rotational time
3) Transmission time
4) Waiting time

Ans: 1

68) A __________ is software that manages the time of a microprocessor to ensure that all time critical events are processed as efficiently as possible. This software allows the system activities to be divided into multiple independent elements called tasks.

1) Kernel
2) Shell
3) Processor
4) Device Driver

Ans: - 1

Computer System Structures Interview Questions Part4

47) ________ is/are only storage media that the CPU can access directly.
1) Main memory
2) Storage memory
3) both
4) None
Answer: 1
Level:1

48) _________ is the extension of main memory that provides large non volatile storage capacity.
1) Secondary storage
2) RAM
3) Cache
4) None
Answer: 1
Level:1

49) Which of the following is a volatile storage medium?
1) Hard disc
2) RAM
3) Magnetic tapes
4) Compact disc
Answer: 2
Level:1

50) Which of the following is a non- volatile storage medium?
1) Cache
2) RAM
3) CPU Registers
4) Hard disc
Answer: 4
Level:1

51) DMA stands for______
1) Direct Memory Access
2) Directory Memory Access
3) Differential Memory Access
4) All the above
Answer: 1
Level:1

52) A _____ is a memory that stores data while they are transferred between two devices or between a device and an application.
1) Buffer
2) Cache
3) Hard disc
4) Compact disc
Answer: 1
Level:1

53) Question: From the given data
Bytes/Sector = 500
Sectors/Track = 50
Tracks/Platter = 150
Platters/ Hard Disk = 10
Total number of bytes in the hard disk?
1) 500 x 50 x 10
2) 500 x 50 x 150
3) 500 x 50 x 150 x 10
4) 500 x 150 x 10
Answer: 3
54) Question: From the given data
Bytes/Sector = 500
Sectors/Track = 50
Tracks/Platter = 150
Platters/ Hard Disk = 10

Total number bytes in a platter?
1) 500 x 50 x 150
2) 500 x 50 x 10
3) 500 x 150 x 50 x 10
4) 500 x 150 x 10
Answer: 1
55) Question: From the given data
Bytes/Sector = 500
Sectors/Track = 50
Tracks/Platter = 150
Platters/ Hard Disk = 10
Total number of bytes per cylinder?
1) 500 x 50 x 10
2) 500 x 150 x 50
3) 500 x 150 x 10
4) 50 x 150 x 10
Answer: 1
56) Question: From the given data
Bytes/Sector = 750
Sectors/Track = 100
Tracks/Platter = 150
Platters/ Hard Disk = 50
Total number of bytes in the hard disk?
1) 750 x 100 x 50
2) 750 x 100 x 150
3) 750 x 100 x 150 x 50
4) 750 x 150 x 50
Answer: 3
57) From the given data
Bytes/Sector = 750
Sectors/Track = 100
Tracks/Platter = 150
Platters/ Hard Disk = 50
Total number bytes in a platter?
1) 750 x 100 x 150
2) 750 x 100 x 50
3) 750 x 150 x 100 x 50
4) 750 x 150 x 50
Answer: 1
58) From the given data
Bytes/Sector = 750
Sectors/Track = 100
Tracks/Platter = 150
Platters/ Hard Disk = 50
Total number of bytes per cylinder?
1) 750 x 100 x 50
2) 750 x 150 x 100
3) 750 x 150 x 50
4) 100 x 150 x 50
Answer: 1

Computer System Structures Interview Questions Part3

24) Recursion or large arrays of local variables avoided by kernel programmers because The kernel stack is usually a limited resource. A stack overflow crashes the entire machine.
T/F
Answer: True
Exp: by def
Level:1


25) What is the purpose of system calls?
a) system calls allow user-level processes to request services of the operating system.
b) system calls acts as traps.
c) both a and b
d) none of the above
answer : a
Exp: by def
Level:1


26) What are the major activities of an operating system in regard to process management?
a. The creation and deletion of both user and system processes
b. The suspension and resumption of processes
c. The provision of mechanisms for process synchronization
d. The provision of mechanisms for process communication
e. The provision of mechanisms for deadlock handling

a) a,b,c
b) a,b,d
c) a,b,c,e
d) a,b,c,d,e
answer:d
Level:1

27) What are the major activities of an operating system in regard to memory management?
a. Keep track of which parts of memory are currently being used and by whom.
b. Decide which processes are to be loaded into memory when memory space becomes available.
c. Allocate and deallocate memory space as needed.
d. Interrupt processes when executing

1) a and b
2) a,b and c
3) a and c
4) Only c

Answer:2
Level:1

28) The major activities of an operating system in regard to secondary-storage management?
a) Free-space management.
b) Storage allocation.
c) Interrupt processes while executing
d) Disk scheduling.


1) a and b
2) a,b and c
3) a,b and d
4) Only c

Answer:3
Level:1




29) Which of the following are true regarding the command interpreter?
a) the command interpreter reads commands from the user or from a file of commands and executes them
b) command interpreter is subject to changes
c) acts as an interface between primary and secondary memory

1) a and b
2) a,b and c
3) a and c
4) Only a

. Answer:1
It reads commands from the user or from a file of commands
and executes them, usually by turning them into one or more system
calls. It is usually not part of the kernel since the command interpreter
is subject to changes.
Level:2

30) What system calls have to be executed by a command interpreter or shell in order to start a new process in unix?
a) fork
b) ps
c) fork followed by exec
d) none of the above
Answer:c
process. The fork call clones the currently executing process, while the exec call overlays a new process based on a different executable over the calling process.
Level:1


31) Which of the following are trueregarding system programs and system calls?
a) System programs can be thought of as bundles of useful
system calls.
b) system calls provide basic functionality to users so that users do not need to write their own programs to solve common problems.
c) system calls can be defined by the user

1) a and b
2) a,b and c
3) a,b and d
4) Only b

Answer:1
Level:2

32) What is the main advantage of the layered approach to system design?
a) the system is easier to debug and modify because changes affect only limited sections of the system rather than touching all sections of the operating system.
b) Information is kept only where it is needed and is accessible only within a defined and restricted area, so any bugs affecting that data must be limited to a specific module or layer. c) microkernel approach helps increases the degree of multiprogramming.

1) a,b,c
2) a,b
3) Only a
4) None

Answer: 2
Level:2

33) what are the services provided by an operating system.
a. Program execution.
b. I/O handling
c. File-system manipulation.
d. commmunications
e. error detection

a) a,b,c,d
b) b,c,d,e
c) a,b,c,d,e
d) b,c,e
Answer:c
Level:1

34) What are the main advantages of the microkernel approach to system design?

a) adding a new service does not require modifying the kernel
(b) it is more secure as more operations are done in user mode than in kernel mode
(c) microkernel approach helps increases the degree of multiprogramming.
d) a simpler kernel design and functionality typically results in a more reliable operating system.



1) a,b,d
2) b,c,d
3) a,b,c,d
4) Only a

Answer:1
Level:2

35) some systems store the operating system in firmware, and others on disk?
for PDAs,cellular telephones etc a disk with a file system may be not be available for the device.hence they are stored in firmaware.
T/F.
Answer: True
Level:2

36) How could a system be designed to allow a choice of operating systems to boot from? What would the bootstrap program need to do?
a) during boot-up, a special program (which we will call the boot manager) will determine which operating system to boot into.
b) the boot-strap loader will load the operating system selected at the start-up.
c) only a
d) both a and b.

Answer:c

Exp: Consider a system that would like to run both Windows
XP and three different distributions of Linux (e.g., RedHat, Debian, and
Mandrake). Each operating system will be stored on disk. During system
boot-up, a special program (which we will call the boot manager) will
determine which operating system to boot into. This means that rather
initially booting to an operating system, the boot manager will first run
during system startup. It is this boot manager that is responsible for
determining which system to boot into. Typically boot managers must
be stored at certain locations of the hard disk to be recognized during
system startup. Boot managers often provide the user with a selection of
systems to boot into; boot managers are also typically designed to boot
into a default operating system if no choice is selected
Level:2


37) The following are the secondary storage media.
1) Magnetic tapes
2) Magnetic disks
3) Ram
4) None

Answer: 1 and 2
Level:1

38) Which of the following are Non volatile storage devices
a) Magnetic Tapes
b) Main memory
c) Optical disk
d) Secondary Memory

1) a and b
2) a,b and c
3) a,b and d
4) Only c

Answer: 3
Level:1

39) Electronic disk, Main memory, Magnetic disk and Cache are volatile. True/False
Answer: False
Level:1

40) ______: a secondary storage device, which holds data in bulk and it, holds data in magnetic medium of the disk.
1) Hard disc
2) Compact disc
3) RAM
4) CPU Registers
Answer: 1
Level:1

41) A ________ is a secondary (optical) storage device.
1) Hard disc
2) Compact disc
3) RAM
4) CPU Register
Answer: 2
Level:1

42) ________ is the type of memory access in main memory (RAM).
1) Sequential access
2) DMA
3) Both
4) None
Answer: 2
Level:1

43) Which of the following is a volatile storage medium?
1) Hard disc
2) Cache
3) Magnetic tapes
4) Compact disc
Answer: 2
Level:1

44) The _________ is the additional time waiting for the disc to rotate the desired sector to the disc head
1) Rotational latency
2) Bandwidth
3) Seek time
4) None
Answer: 1
Level:1

45) ________: keep in memory only those instructions and data that are needed at any given time.
Needed when the process is larger than the amount of memory allocated to it.
1) Overlays
2) Studs
3) Cache
4) None
Answer: 1
Level:2

46) For Virtual memory implementation the OS uses ________
1) Compact disc
2) Floppy drives
3) Hard disc
4) Cache
Answer: 3
Level:2

Computer System Structures Interview Questions Part12

10) the memory hierarchy is
a. Registers, cache, main memory, magnetic disk, CDROM, tape
b. Cache, , main memo ry, magnetic disk, Registers, CDROM, tape
c. Cache, Registers, main memory, magnetic disk, CDROM, tape
4) Main memory, Registers, cache, magnetic disk, CDROM, tape
Answer: 1
Exp: internal architecture
Level:2


11) The CPU uses poling to watch the control bit, constantly looping to see whether the device is ready. This method of operations is called___________
1) Progrmmed I/O
2) I/O interrupt
3) I/O operation request
4) None
Answer: 1
Exp: by the definition of the Programmed I/O
Level:2

12) The memory buffer used to accommodate a speed differential is called a _____
1) Main memory
2) Cache memery
3) CPU Register
4) Optical disk
Answer: 2
Exp: by def
Level:1


13) The set of tracks that are at one arm position forms a ________
1) sector
2) cylinder
3) platter
4) Spindel
Answer: Cylinder
Exp: by def
Level:1


14) ____ is the rate at which data flow between the drive and the computer.
1) bit rate
2) transfer rate
3) data rate
4) None
Answer: Transfer rate
Exp: by def
Level:1
15) The positioning time is also called ___
a. Seek time
b. Rotational latency
c. Transfer rate
d. Random access time
Answer:4
Exp: ( by definition of random access time)
Level:1


16) Time to move the disc arm to the desired cylinder is called____
1) seek time
2) wait time
3) turn around time
4) None
Answer: Seek time
Exp: ( by definition of the seek time)
Level:1

17) The time for the desired sector to rotate to the disc head is called ____
1) seek time
2) rotational latency
3) sweep time
4) None
Answer: Rotational latency
Exp: ( by definition of rotational latency)
Level:1

18) Even though disc platters are coated with a thin protective layer, sometimes the head will damage the magnetic surface. This accident is called______
1) system crash
2) hardware crash
3) head crash
4) None
Answer: Head crash
Exp: by def
Level:1


19) EIDE stands for
1) Extended indexed directory extensions
2) Enhanced Integrated Drive Electronics
3) Enhanced Integrated Disk Electronics
4) None
Answer: 2
Exp: acronym
Level:2


20) Cache memory is divided into (and loaded in) blocks also called ________
a. Cache blocks
b. Cache lines
c. Both the above
d. None of the above
Answer: 2
Exp: by def
Level:1


21) Modem can convert
1) Digital data to analog signals
2) Analog signals to digital signals.
3) Both the above
4) 2 only
Answer: 3
Exp:n by def

Level:1

22) ______________is the rapid switching of the CPU between processes given the illusion of all processes running concurrently.
a. Multiprogramming
b. Multitasking
c. Timesharing
d. None
Answer: a and b
Exp: by def
Level:1

23) Which of the following instructions (or instruction sequences) should only be allowed in kernel mode?
1. Disable all interrupts.
2. Read the time of day clock.
3. Set the time of day clock.
4. Change the memory map.
5. Write to the hard disk controller register.
6. Write all buffered blocks associated with a file back to disk (fsync).
1) 1,3,4,5 need to be restricted to kernel mode.
2) 1, 6, 3, 2
3) 1, 2, 3, 4, 5
4) 3, 4, 1, 2
Answer: 1
Exp: properties of the kernel mode
Level:2

Computer System Structures Interview Questions Part1

1) Which program gets loaded first when a computer is booted?
1) Operating System
2) Bootstrap loader
3) Device drivers
4) All of the above

Answer: 2
Exp: Bootstrap loader is the first program to be loaded into main memory from the ROM
Level:2

2) System Call is also known as?
1) Monitor call
2) User call
3) Software call
4) None of the above

Answer: 1
Exp: by def
Level:2


3) Modern OS are
1) procedure driven
2) Interrupt driven
3) Function call driven
4) None of the above

Answer: 2
Exp: derived from today’s application OS
Level:2


4) Exception is also known as
1) Interrupt
2) Handler
3) Trap
4) None of the above
Answer: 1 and 3
Exp: alternate names
Level:2


5) The smallest addressable portion of a disc is called
1) Track
2) Cylinder
3) Sector
4) Platter

Answer:3
Exp: by def
Level:1

6) SCSI stands for
1) Super Computer- Systems Interface
2) Small Computer- Systems Interface
3) Single Computer- Systems Interface
4) Simple Computer- Systems Interface

Answer: 2
Exp: by def
Level:1

7) DMA stands for
1) Disc Memory Allocation
2) Direct Memory Allocation
3) Dynamic Memory Allocation
4) Disc Memory Access

Answer: 3
Exp: by def
Level:1


8) DRAM stands for
1) Direct Random Access Memory
2) Dynamic Random Access Memory
3) Distributed Random Access Memory
4) Dynamic Random Allocation of Memory

Answer: 2
Exp: acronym
Level:1


9) An instruction will be stored in _____________
1) Instruction Register
2) Program Counter
3) Stack Pointer
4) Data Segment
Answer: 1
Exp: by def of instruction register
Level:1

Sorting Interview Questions Part 9

36. According to the max-heap property, each node in a tree has a key which is _______ than or equal to the key of its parent.
Ans. less

37. A sort algorithm that repeatedly looks through remaining itemsto find the least one and moves it to its final location is
a. Quick sort
b. Insertion sort
c. Selection sort
d. Merge sort
Ans. c

38. __________ is a specialization of selection sort.
a. quick sort
b. selection sort
c. bingo sort
d. strand sort
Ans. c
Bingo sort is a variant of selection sort that orders items by repeatedly looking through remaining items to find the greatest value and moving all items with that value to their final location. This is more efficient if there are many duplicate values.

39. __________ can be seen as a variant of selection sort in which sorted items are arranged in a heap to quickly find the next item.
a. heap sort
b. bingo sort
c. shell sort
d.none of the above
Ans. a

40. ___________ is a kind of quicksort
a. balanced quicksort
b. multikey quicksort
c. retrospective sort
d. all the above
Ans. d

41. ___________ is a part of or used in quicksort.
a. divide and conquer
b. partition
c. recursion
d. all the above
Ans. d

42. Insertion sort is also known as __________.
Ans. Linear insertion sort




43. Given the following sequence of elements 11,2,9,13,57,25,17,1,90,3 what will be the output after MAX_HEAPIFY(A,2) where heap-size[A]=10.
a. 11,2,9,13,25,57,17,1,90,3
b. 11,2,9,90,57,25,17,1,13,3
c. 11,90,9,13,57,25,17,1,2,3
d. 90,57,25,13,11,9,17,1,2,3
ans. c

44. Given the following set of elements 16,4,10,14,7,9,3,2,8,1 what will be the output after MAX_HEAPIFY(A,2) where heap-size[A]=10.
a. 16,4,10,14,7,9,3,2,8,1
b. 16,14,10,4,7,9,3,2,8,1
c. 16,14,10,8,7,9,3,2,4,1
d. 16,14,10,8,7,3,9,2,4,1
Ans. c

45. Give the output of MAX_HEAPIFY(A,3) in the array A=( 27,17,3,16,13,10,1,5,7,12,4,8,9,0).
a. 27,17,3,16,13,10,1,5,7,12,4,8,9,0
b. 27,17,10,16,13,3,1,5,7,12,4,8,9,0
c. 27,17,10,16,13,9,1,5,7,12,4,8,3,0
d. 27,17,3,16,13,7,1,5,10,12,4,8,9,0
Ans. c





46. If the sequence: (2,2) (0,4) (1,4) (0,1) (1,2) (0,6) (2,1) (1,1) were sorted using a
stable sort by ascending order on the first key and then using the same method were
sorted again on the second key, the result would be:
8.a). (0,4) (0,1) (0,6) (1,4) (1,2) (1,1) (2,2) (2,1)
8.b). (0,1) (2,1) (1,1) (2,2) (1,2) (0,4) (1,4) (0,6)
8.c). (2,1) (1,1) (0,1) (2,2) (1,2) (1,4) (0,4) (0,6)
8.d). (0,1) (1,1) (2,1) (1,2) (2,2) (0,4) (1,4) (0,6) ***
8.e). (0,1) (0,4) (0,6) (1,1) (1,2) (1,4) (2,1) (2,2)


47. Mergesort always runs faster than bubblesort. (T/F)
false -- depends on the constants and the size of the input. Given a large enough input, mergesort will most likely run faster than bubblesort.
48. Selection sort and quicksort both fall into the same category of sorting algorithms. What is this category?
A. O(n log n) sorts
B. Divide-and-conquer sorts
C. Interchange sorts
D. Average time is quadratic
Ans:c

Sorting Interview Questions Part 8

21. If p < r then
q Partition (A, p, r)
Recursive call to Sort (A, p, q)
Recursive call to Sort (A, q + r, r)
Which sorting algorithm does SORT represent
a.Selection sort b.quick sort c.Bubble sort d.Merge sort
Ans:b
22. _____Sort chooses as pivot one of the items in the array to be sorted.
a.Selection sort b.quick sort c.Bubble sort d.Merge sort
Ans:b
23.Selection sort is
a.inplace
b.noninplace
c.out place
d.none
Ans:a
24.Bubble sort is
a.inplace
b.noninplace
c.out place
d.none
Ans:a
25.Which of the following are stable algorithms
a.Bubble b.Insertion c.Both d.none
Ans:c

26. An array in sorted order is in __________.
a.Max-heap
b.Min-heap
c.Random heap
d.none
Ans:a

27. Assuming all the elements to be distinct, where in the Max-heap might the smallest element reside ?

a.In the root position
b.In the left sub tree of the root
c.In the right sub tree of the root
d.In some leaf node
Ans:d

28. Assuming all the elements to be distinct, where in the Min-heap might the smallest element reside ?

a.In the root position
b.In the left sub tree of the root
c.In the right sub tree of the root
d.In some leaf node
Ans:a

29. Assuming all the elements to be distinct, where in the Max-heap might the largest element reside ?

a.In the root position
b.In the left sub tree of the root
c.In the right sub tree of the root
d.In some leaf node
Ans:a

30. Assuming all the elements to be distinct, where in the Min-heap might the largest element reside ?

a.In the root position
b.In the left sub tree of the root
c.In the right sub tree of the root
d.In some leaf node
Ans:d

31.Which of the following is useful in implementing quick sort
a.Stack
b.List
c.Queue
d.Set
Ans:a

32.Which of the following algorithm design technique is used for quick sort
a.Dynamic programming
b.Backtracking
c.Divide and conquer
d.Greedy method
Ans:c

33. If the records that it's sorting are in main memory then the sort is called as
a. internal
b. external
c. stable
d. none of this
Ans. a

34. An array of elements is sorted by choosing a pivot element & by partition.The sorting process is called
a. Partition exchange sort
b. Quick sort
c. a and b
d. selection sort
Ans. c

35. In min-heap property,each node in a tree has a key which is _______ than or equal to the key of its parent.
Ans. greater

Sorting Interview Questions Part 7

11. In bubble sort algorithm the number of comparison is irrespective of data set i.e., input whether best or worst.(T/F)
Ans:True
12. The basic procedures related to heap are
a.Heapify, which runs in O(lg n) time.
b.Build-Heap, which runs in linear time.
c.Heap Sort, which runs in O(n lg n) time.
d.Extract-Max, which runs in O(lg n) time.
Ans:a,b,c,d
13. Heapify runs in O(lg n) time while build-heap runs in _____time.
Ans: linear
14. A process picks the largest child key and compares it to the parent key and if parent key is larger then the process quits, otherwise it swaps the parent key with the largest child key, so that the parent now becomes larger than its children.Such a process is called
a.Heap sort
b.Heapify
c.Build heap
d.none
Ans:b
15. Process (A, i)
1. l ← left [i]
2. r ← right [i]
3. if l ≤ Process-size [A] and A[l] > A[i]
4. then largest ← l
5. else largest ← i
6. if r ≤ Process -size [A] and A[i] > A[largest]
7. then largest ← r
8. if largest ≠ i
9. then exchange A[i] ↔ A[largest]
10. Process (A, largest)
The above process indicates
a.Heap sort
b.Heapify
c.Build heap
d.none
Ans:b

16.The output of heapify of the following tree is




a. 15 8 4 7 5 3 1 2 6 b. 8 15 4 7 5 3 1 2 6 c. 15 8 4 7 5 3 1 6 2 d. 15 8 4 5 7 3 1 2 6
Ans:a
17. Process (A)
1. BUILD_HEAP (A)
2. for i ← length (A) down to 2 do
exchange A[1] ↔ A[i]
heap-size [A] ← heap-size [A] - 1
Heapify (A, 1)
The process here denotes
a.Selection sort b.Heap sort c.Bubble sort d.none
Ans:b

18. The time taken for build heap is
a.O(n)
b.O(log n)
c.O(nlogn)
d.none
Ans:a
The HEAPSORT procedure takes time O(n lg n), since the call to BUILD_HEAP takes time O(n) and each of the n -1 calls to Heapify takes time O(lg n).
19. Process (A1, A2, A)
i.← j 1
A1[m+1], A2[n+1] ← INT_MAX
For k ←1 to m + n do
if A1[i] < A2[j]
then A[k] ← A1[i]
i ← i +1
else
A[k] ← A2[j]
j ← j + 1
SORT (A)
A1[1 . . n/2 ] ← A[1 . . n/2 ]
A2[1 . . n/2 ] ← A[1 + n/2 . . n]
Process (A1)
Process (A1)
Process (A1, A2, A)
Which sorting algorithm does SORT represent
a.Selection sort b.Heap sort c.Bubble sort d.Merge sort
Ans:d
20.Quick sort is recursive.(T/F)
Ans:True

Sorting Interview Questions Part 6

1. Divide-and-conquer is a
a.top-down technique
b.Bottom-up technique
c.Both
d.none
Ans:a
2.The technique for designing algorithms that consists of dividing the problem into smaller subproblems hoping that the solutions of the subproblems are easier to find and then composing the partial solutions into the solution of the original problem is _____
Ans:Divide and conquer
3. Divide-and-conquer paradigm consists of following major phases:Arrange them in order
a.Solve the sub-problem recursively (successively and independently), and then
b.Breaking the problem into several sub-problems that are similar to the original problem but smaller in size,
c.Combine these solutions to subproblems to create a solution to the original problem.
a. bac
b. abc
c. cab
d. none
Ans:a
4. Bubble sort requires extra memory.(T/F)
Ans:False
5. Insertion sort is an example of
a.incremental sort
b.decremental sort
c.non-stable sort
d.none
Ans:a
Insertion sort is an example of an incremental algorithm; it builds the sorted sequence one number at a time.
6. An algorithm considering the elements one at a time, inserting each in its suitable place among those already considered (keeping them sorted) is called
a.selection sort
b.insertion sort
c.bubble sort
d.none
Ans:b
7.The following process depicts which sorting algorithm: first find the smallest in the array and exchange it with the element in the first position, then find the second smallest element and exchange it with the element in the second position, and continue in this way until the entire array is sorted.
a.selection sort
b.insertion sort
c.bubble sort
d.none
Ans:a
8. Selection sort is quadratic in both the worst and the average case, and requires no extra memory.(T/F)
Ans:True
9. For each i from 1 to n - 1, there are ____ exchanges for selection sort.
a.1
b.n-1
c.n
d.none
Ans:a
10.For each i from 1 to n - 1, there is _______comparisons for selection sort.
a.n
b.n-i
c.i
d.n-1
Ans:b
For each i from 1 to n - 1, there is one exchange and n - i comparisons, so there is a total of n -1 exchanges and (n -1) + (n -2) + . . . + 2 + 1 = n(n -1)/2 comparisons. These observations hold no matter what the input data is.

Sorting Interview Questions Part 5

68. Which of these is the correct big-O expression for 1+2+3+...+n?
A. O(log n)
B. O(n)
C. O(n log n)
D. O(n²)
Ans:d


69. Consider the following polynomial

aknk+ak-1nk-1+………….a0 .

What is the Big –O representation of the above polynomial?
(a)O(n) (b) O(nk) (c) O(nk+1) (d) O(log k)
Ans:b
70. Consider the program segment given below:
Int i,j,sum;
for ( i=0 ; i < n; i++) {
for (j = 1,sum=a[0]; j < = i; j++)
Sum+=a[j];
printf(“ sum for sub-array through %d is %d”,i , sum);
}

The running time of the above algorithm is

(a) n. (b) n log n . (c) log n. (d) n2.
Ans:d


71. Consider the following algorithm:

Step 1 : If S has zero or one element, return S immediately; it is already sorted. Otherwise, split S into two parts S1 and S2, such that S1 contains the first [n/2] elements of S, and S2 contains the remaining elements of S.
Step 2: Recursively sort sequences S1 and S2
Step 3: put back the elements into S by merging the sorted sequences S1 and S2 into a sorted sequence.

Which of the following describe(s) the above algorithm?

(a) Sorting by insertion
(b) Sorting by selection
(c) Sorting by exchange
(d) Divide and conquer
Ans:d


72. Consider the following algorithm :
abc(data[])
Transform data into a heap
for ( i=data.length-1; i> 1 ; i--)
Swap the root with the element in position i;
Restore the heap property for the tree data[0],…….. data[i-1];
Which of the following are not the intermediate functions of the above algorithm?
(a) Transforming data into either an ascending order or descending order of a heap
(b) Transforming data into a maximum heap
(c) The 1st step of the sorting process is exchanging the last element and the first element, and decreasing the array size by one.
(d) Finally, get either the ascending order or the descending order of nodes
Ans: b

Sorting Interview Questions Part 4

61.How many passes are required to sort the set of integers using the bubble sort algorithm? {20,60,50,37,16,92,70,35}.

(a) 6 (b) 7 (c) 8
(d) 9 (e) 5
Ans. b

62.Consider the following pseudo code algorithm
found = false;
i=1;
while (i =< n ) and ( not found)
{
if key=k[i] then
{
search =i;
found =true;
else
i++;
}
}
if not found
{
search=0;
}
What is the above algorithm intended to do?
(a) Sequential Search (b) Depth First Algorithm
(c) Shell sort algorithm (d) Index sequential search
(e) Breadth first search
Ans. a

63. Consider the following (iv) conditions:
(i) Sorts which cannot be performed in the main memory, can be done on disk or tape. These are also quite important. This type of sorting is called external sorting.
(ii) The simplest algorithms usually take O(n2) time to sort in objects and are only useful for sorting short lists.
(iii) One of the most popular sorting algorithm is quicksort; which takes O(log n) time on average.
(iv) Merge sort is well suited for external sorting.
Which of the above conditions are applied for the sorting algorithm?
a. (i),(ii) and (iii) only
b. (i),(ii) and (iv) only
c. (ii),(iii) and (iv) only
d. (i) and (iii) only

Ans. b

64. Which sorting method(s) runs fastest for file which is already sorted?
a.Selection sort
b.insertion sort
c.quick sort
d.bubble sort
Ans:b
65.
(i) Quick Sort can be implemented in recursive way.
(ii) Heap Sort is the best sorting method compared to bubble, selection, insertion sort on the basis of complexity.

Correct statement(s) is/are?
A(i) only
b (ii) only
c.(i) and (ii)
d.none
Ans:c
66. In calculating the time complexity of an algorithm, we use some rules.

Rule 1.
If T1 (N)=O(f(N)) and T2(N)=O(g(N)) then
Statement 1 T1(N) + T2 (N)=Max(O(f(N)),O(g(N)))
Statement 2 T1(N)* T2(N)=O(f(N)*g(N))
Rule 2
If T1(N)=O(f(N)) and T2(N)=O(g(N)) then
Statement 1 T1(N)+ T2(N)=Min(O(f(N)),O(g(N)))
Statement 2 T1(N)* T2(N)=O(f(N))+O(g(N))
Rule 3
O(C f(N))=O(f(N)) if C is a constant
Rule 4
If T1 (N)=O(f(N)) and T2(N)=O(g(N)) and If g(N) < = f(N) then
T1(N)+ T2(N)=O(f(N))

What are the correct rules out of the above?
a.Rule 1 , Rule 2 and Rule 3 only
b.Rule 1 and Rule 4 only
c.Rule 1 , Rule 3 and Rule 4 only
d.Rule 2, Rule 3 and Rule 4 only
Ans:c



67. What is the name of the following algorithm?

Initialize marker to 1 (2nd element in the list)
If element[marker1] < element [marker1-1] , store element[marker1] in a temporary location temp, initialize marker2 to marker1-1 (the location just before marker1).
While element [marker2] > temp and marker2 >= 0 shift element [marker2] to location marker2+1. [this slides the element over to make room to its left) Decrease marker2 by 1.
Insert temp into the location just vacated by a shift.
Increase marker1 by 1.
a. Insertion sort b. bubble sort c. selection sort d. none
Ans: d

Sorting Interview Questions Part 3

41.Sorting is not useful for
a. report generation
b. minimizing the storage needed
c. making searching easier and efficient
d. responding to queries easily
Ans. b


42. Choose the correct statements
a. Internal sorting is used if the number of items to be sorted is very large
b. External sorting is used if the number of items to be sorted is very large
c. External sorting does not need auxiliary storage
d. Internal sorting need auxiliary storage
Ans. b


43. A sorting technique that guarantees that records with the same primary key occurs in the same order in the sorted list as in the original unsorted list is said to be
a. stable b. consistent c. external d. linear
Ans. a


44.The running time of an algorithm is given by
T(n) = T(n-1) + T(n-2) – T(n-3),if n>3
= n,otherwise.
The order is
a. n b. log n c. n^n d. n^2
Ans. a
Let us find what is T(4) and T(5)
T(4) = T(3) + T(2) – T(1) = 3+2-1=4
T(5) = T(4)+ T(3) –(2) = 4+3-2=5
By induction it can be proved that T(n) = n.Hence order is n.


45.The order of an algorithm that finds whether a given Boolean function of ‘n’ variables,produces a 1 is
a. constant b. linear c. logarithmic d. exponential
Ans. d
In the worst case it has to be check all the 2^n possible input combinations,which is exponential .


46.You want to check whether a given set of items is sorted or not.Which of the following sorting methods will be the most efficient if it is already in sorted order?
a. Bubble sort b. Selection sort c. Insertion sort d.Merge sort
Ans. c


47. The average number of comparisons performed by the merge sort algorithm,in merging two sorted lists of length 2 is
a. 8/3 b. 8/5 c. 11/7 d.11/6
Ans. a
Merge sort combines 2 given sorted lists into one sorted list.For this problem let the final sorted order be a,b,c and d.The 2 lists(of length 2 each) should fall into one of the following 3 categories:
i)a,b and c,d ii)a,c and b,d iii)a,d and b,c
The number of comparisons needed in each case will be 2,3,3.So,average number of comparisons will be (2+3+3)/3=8/3.


48.Which of the following sorting methods will be the best if the number of swappings done is the only measure of efficiency?
a. bubble sort b. selection sort c. insertion sort d.quick sort
Ans. b


49.You are asked to sort 15 numbers randomly.You should prefer
a. bubble sort b. quick sort c. merge sort d. heap sort
Ans. a


50. As part of the maintenance work,you are entrusted with the work of rearranging the library books in a shelf in proper order,at the end of each day.The ideal choice will be
a. bubble sort b. insertion sort c. selection sort d. heap sort
Ans. b


51. Which of the following algorithms exhibits the unnatural behavior that,minimum number of comparisons are neede if the list to be sorted is in the reverse order and maximum number of comparisons are neede if they are already in order.
a. heap sort b. radix sort c. binary insertion sort d. there can’t be any such sorting method.
Ans. c


52.Which of the following sorting methods sorts a given set of items that is already in order or in reverse order with equal speed?
a. Heap sort b. Quick sort c. Insertion sort d. selection sort
Ans. b


53. A machine needs a minimum of 100 sec to sort 1000 names by quick sort.The minimum time needed to sort 100 names will be approx
a. 50.2 sec b. 6.7 sec c.72.7 sec d. 11.2 sec
Ans. b
In the best case quick sort algorithm makes nlogn comparisons.so,1000 * log(1000) = 9000 comparisons,which takes 100s.To sort 100 names a minimum of 100 * log(100)=600 comparisons are needed.This takes 100*600/9000 = 6.7 sec


54.A machine took 200 sec to sort 200 names,using bubble sort.In 800 sec,it can approximately sort
a. 400 names b. 800 names c. 750 names d. 850 names
Ans. a
For sorting 200 anmes bubble sort makes 200 * 199/2 = 19900 comparisons.So,the time needed for 1 comparison is 200 sec approx.In 800 sec it can make 80,000 comparisons.We have to find n,such that n(n-1)/2=80,000.solving n is approx 400.


55.The correct order of arrangement of the names Bradman,Lamb,May,Boon,Border,Underwood and Boycott,so that the quicksort algorithm makes the least number of comparisons is
a. Bradman,Border,Boon,Boycott,May,Lamb,Underwood
b. Bradman,Border,Boycott,Boon,May,Underwood,Lamb
c. Underwood,Border,Boon,Boycott,May,Lamb,Bradman
d. Bradman,May,Lamb,Border,Boon,Boycott,Underwood
Ans. a and b
Let the first element be the pivot element always.The best way is the one that splits the list into two equal parts each time.This is possible if the pivot elemnt is the median.Consider the given set of names or the equivalent set 1,2,3,4,5,6,7.4 is the median and hence should be the pivot element.Since the first element is the pivot element,4 should be the first element.so after the first pass,4 will be put in the correct place and we are left with 2 sublists 1,2,3 and 5,6,7.Since 2 is the median of 1,2,3 the list should be rearranged as 2,1,3 or 2,3,1.For similar reasons 5,6,7 should be rearranged as 6,5,7 or 6,7,5.Hence the answer.

56. Which of the following is/are correct in connection with sorting methods?
(a) Bubble sort uses sorting by an insertion technique to sort a file of numbers.
(b) Quick sort uses sorting by an exchange technique to sort a file of numbers.
(c) Shell sort uses sorting by an exchange technique to sort a file of numbers.
(d) Heap sort does not use sorting by an exchange technique to sort a file of numbers.
Ans. b


{2,8,13,6,7,27,18}
57)the maximum heap is created using the above set of integers, what would be the value at the 6th
position of the heap?
(a) 2 (b) 8 (c) 6
(d) 13 (e) 7
Ans. b

58.If one uses the quick sort algorithm to sort the following integers, how many pivot values are
required? You may assume that the pivot element is always selected as the last element of the respective
sub arrays. {50,22,11,78,16,95,7,75,51,41}.

(a) 7 (b) 8 (c) 4
(d) 6 (e) 5
Ans. d

59.If one uses the quick sort algorithm to sort the following set of integers how many pivot values are required?You may assume that the pivot element is always selected as the first element of the respective
sub arrays. {50,22,11,78,16,95,7,75,51,41}.

(a) 7 (b) 8 (c) 4
(d) 6 (e) 5
Ans. e

60.If one uses the bubble sort algorithm in ascending order ,in which of the following pairs will the data values not interchange during the first pass? {20,60,50,37,16,92,70,35}.
(a) 20,60 (b) 60,50 (c) 60,37
(d) 50,37 (e) 60,16
Ans. a

Sorting Interview Questions Part 2

25.Selectionsort and quicksort both fall into the same category of sorting algorithms. What is this category?
A. O(n log n) sorts
B. Divide-and-conquer sorts
C. Interchange sorts
D. Average time is quadratic.
Ans:C
26. Which of the following is applicable for any constant ‘c’
a.c*log n=O(1)
b.c*log n =O(logn)
c.c*log n =O(nlogn)
d.c*log n =O(n)
Ans:b
27.Which of the following is applicable for any constants‘c,k’
a.c*(n^k)=O(n^k)
b.c*(n^k) =O(logn)
c.c*(n^k) =O(nlogn)
d.c*(n^k) =O(1)
Ans:a
28.The process of combining two or more sorted files into a third sorted file is _____
Ans:merging


29.Which Sort Algorithm has same time complexity as Heap sort in all cases?
a.Merge sort
b.Bubble sort
c.Selection sort
d.none of these
Ans:a


30.Selection sort is faster than bubble sort(T/F)
Ans:True
Because a selection sort looks at progressively smaller parts of the array each time (as it knows to ignore the front of the array because it is already in order), a selection sort is slightly faster than bubble sort, and can be better than a modified bubble sort.

31.The worst-case time complexity of heap sort is same as the average-case time complexity of quick sort.
a. True
b. False
Ans. b

32.Which of the following statements is FALSE?
a. Merge Sort is an unstable sort
b. Worst case time complexity of Merge Sort is O(NlogN)
c. Merge Sort takes more space than Quick Sort
d. Average case time complexity of Merge Sort is O(NlogN)
Ans. c

33.Both merge sort and quick sort are in-place sorts.
a. True
b. False
Ans. b

34.Sorting is not possible by using which of the following methods?
(a) Insertion
(b) Selection
(c) Exchange
(d) Deletion

Ans:d
Using insertion we can perform insertion sort, using selection we can perform selection sort, using exchange we can perform the bubble sort (and other similar sorting methods). But no sorting method can be done just using deletion.

35.What are the methods available in storing sequential files ?
a.Straight merging,
b.Natural merging,
c.Polyphase sort,
d. all the above
Ans: d

36.An algorithm is made up of 2 modules M1 and M2.If order of M1 is f(n) and M2 is g(n) then the order of the algorithm is
a.max(f(n),g(n))
b.min(f(n),g(n))
c.f(n)+g(n)
d.f(n)*g(n)
Ans:a
By definition of order,there exists constants c1,c2,n1,n2 such that
T(n)<=c1*f(n),for all n>=n1
T(n)<=c2*g(n),for all n>=n2
Let N=max(n1,n2) and C=max(c1,c2),so
T(n)<=c*f(n),for all n>=N
T(n)<=c*g(n),for all n>=N
Adding
T(n)<=c/2 (f(n)+g(n))
Let max(f(n),g(n))=f(n)
T(n)<=c/2 (f(n)+f(n))<=c*f(n)
So order is f(n) which is max(f(n),g(n)) by the assumption.


37.The concept of order (Big O) is important because
a.It can be used to decide the best algorithm that solves a given problem
b.It determines the maximum size of a problem that can be solved in a given system in a given amount of time.
c.it is the lower bound of the growth rate of the algorithm
d. a and b
Ans: d

38.The running time T(n) where n is the input size of a recursive algorithm is
T(n)=c+T(n-1),if n>1
d,if n<=1
The order of the algorithm is
a.n*n b.n c.n^3 d.n^n
Ans:b

By recursively applying the relation we can arrive at
T(n-1)=c(n-1)+d
So,order is n


39.There are four different algorithms A1,A2,A3 and A4 to solve a given problem with the order log(n),loglog(n),nlog(n),n/log(n) respectively.Which is the best algorithm?
a. A1 b.A2 c.A3 d.A4
Ans. b


40.The time complexity of an algorithm T(n),where n is the input size is given by
T(n)=T(n-1)+1/n,if n>1
= 1,otherwise
The order of this algorithm is
a. log n b. n c. n^2 d. n^n
Ans. a

Sorting Interview Questions Part 1

1.Which of the following algorithms can be used for sorting large data sets based on time complexity?
a. Bubble sort b. Merge sort c. Heap sort d. Quick sort
Ans:c
Heap sort does not require massive recursion or multiple arrays.


2. Which of the following algorithms is the slowest
a. Bubble sort b. Merge sort c. Quick sort d. Heap sort
Ans:a
The bubble sort works by comparing each item in the list with the item next to it, and swapping them if required. The algorithm repeats this process until it makes a pass all the way through the list without swapping any items


3.The sorting algorithms belonging to quadratic complexity includes
a. bubble sort b. insertion sort c .selection sort d. All the above
Ans:d
4. The sorting algorithms not having complexity O(n log n)includes
a. heap sort b. quick sort c. bubble sort d.merge sort
Ans: a

5.An algorithm to find the shortest paths from a single source vertex to all other vertices in a weighted,directed graph..
a.Dijkstra’s b.Prim’s c. Kruskal d.none of the above
Ans:a

6.Time complexity of Dijkstra’s algorithm
a.O(VlogV) b.O(E+VlogV) c.O(ElogV) d.none of the above
Ans:b

7.In the time complexity O(E+VlogV) V is the number of _____
Ans:vertices

8.In the time complexity O(E+VlogV) E is the number of _____
Ans:edges

9.In Dijkstra’s algorithm,all weights must be nonnegative(T/F)
Ans:True

10.A step-by-step problem-solving procedure, especially an established, recursive computational procedure for solving a problem in a finite number of steps is called
a.Structure b.Queue c.Algorithm d.Data structure
Ans:c


11.Big O notation is used for
a.Asymptotic upper bound
b. Asymptotic lower bound
c. Tight bound
d.none of these
Ans:a


12. θ notation is used for
a.Asymptotic upper bound
b. Asymptotic lower bound
c. Tight bound
d.none of these
Ans:c

13.Ω notation is used for
a.Asymptotic upper bound
b. Asymptotic lower bound
c. Tight bound
d.none of these
Ans:b



14.For inplace sorting no extra memory is required.(T/F)
Ans:True

15.Which of the following do not use inplace sorting
a.Selection b.Bubble c.Insertion d.Merge
Ans: d

16.The operations which directly affect the output of an algorithm are ______
Ans:Key operations

17.Number of times a key operation executes is
a.Complexity b.Frequency count c.Time d.None
Ans:b

18.What are the advantages of sorting
a.Used in algorithms as a key subroutine.
b.Used for engineering issues.
c.Both
d.None
Ans:c


19.A sorting technique where some of the records are in auxiliary storage is
a.Internal sorting
b.External sorting
c.inplace sorting
d.Non inplace sorting
Ans:b

20.A sorting technique where the records are in main memory is
a.Internal sorting
b.External sorting
c.inplace sorting
d.Non inplace sorting
Ans:a

21.Each item in a file is called a record.(T/F)
Ans:True

22.A sort takes place either on the records themselves or on an auxiliary table of pointers.(T/F)
Ans:True

23.Suppose the amount of data stored in the records is so large that the overhead involved in moving the actual data is prohibitive,then the auxiliary table of pointers may be used so that these pointers are moved instead of the actual data,this is called _______
Ans:sorting by address

24.Which of the following is applicable for any constant ‘c’
a.c=O(1)
b.c=O(logn)
c.c=O(nlogn)
d.c=O(n)
Ans:a

Linear Search Interview Questions Part 2

23.The average successful search time for sequential search on ‘n’ items is
a. n/2
b. (n-1)/2
c. (n+1)/2
d. log (n) + 1
Ans. c
If the search key matches the very first item, with one comparison we can terminate.If it is second,two comparisons ,etc.So,average is (1+2+3+…+n)/n , i.e.,(n+1)/2

24. 6 files F1,F2,F3,F4,F5 and F6 have 100,200,50,80,120,150 number of records respectively.In what order should they be stored so as to optimize access time .Assume each file is accessed with the same frequency.
a. F3,F4,F1,F5,F6,F2
b. F2,F6,F5,F1,F4,F3
c. F1,F2,F3,F4,F5,F6
d. Ordering is immaterial as all files are accessed with the same frequency
Ans. a
Since the access is sequential,greater the distance,greater will be the access time.Since all the files are referenced with equal frequency,overall access time can be reduced by arranging them as in option (a).

25. For small arrays, _____________ is a good solution because it's straightforward.
a. binary search
b. linear search
c. fibonacci search
d. none of the above
Ans. b

26. If the loop in a linear search finishes without finding a match,the search is failed and _____ is returned.
Ans. -1
If the loop finishes without finding a match, the search failed and -1 is returned.



27. What is the output of the following program using linear search
#include
using namespace std;

int LinearSearch(const int *Array, const int Size, const int ValToSearch)
{
bool NotFound = true;
int i = 0;

while(i < Size && NotFound)
{
if(ValToSearch != Array[i])
i++;
else
NotFound = false;
}

if( NotFound == false )
return i;
else
return -1;
}

int main()
{
int Number[] = { 67, 278, 463, 2, 4683, 812, 236, 38 };
int Quantity = sizeof(Number) / sizeof(int);
int NumberToSearch = 0;

cout << "Enter the number to search: "; cin >> NumberToSearch;
int i = LinearSearch(Number, Quantity, NumberToSearch);

if(i == -1)
cout << NumberToSearch << " was not found in the collection\n\n";
else
{
cout << NumberToSearch << " is at the " << i+1;
if( i == 0 )
cout<< "st position of the collection\n\n";
else if( i == 1 )
cout<< "nd position of the collection\n\n";
else if( i == 2 )
cout<< "rd position of the collection\n\n";
else
cout<< "th position of the collection\n\n";
}

return 0;
}


Enter the number to search: 278
a. 278 is at the 1st position of the collection
b. 278 is at the 2nd position of the collection
c. 278 is at the 3rd position of the collection
d. 278 was not found in the collection
Ans:b


28.For the above program what is the output for
Enter the number to search: 288
a. 288 is at the 1st position of the collection
b. 288 is at the 2nd position of the collection
c. 288 is at the 3rd position of the collection
d. 288 was not found in the collection
Ans:d

Linear Search Interview Questions Part 1

1.The sequential search, also known as the linear search.

2.Every element in the data set is examined in the order presented until the value being searched for is found, the following technique is called as
a. Binary search.
b. Quick search.
c. Linear search.
d. None of these.
Ans:c

3.Best case time complexity of Sequential search is
a. O(1)
b. O(n)
c. O(n×n)
d. None of these.
Ans:a
4.Average case time complexity of Sequential search is
e. O(1)
f. O(n)
g. O(n×n)
h. None of these.
Ans:b
5. Worst case time complexity of Sequential search is
i. O(1)
j. O(n)
k. O(n×n)
l. None of these.
Ans:b
6. Best case time complexity of linear search is
m. O(1)
n. O(n)
o. O(n×n)
p. None of these.
Ans:a
7.Average case time complexity of Linear search is
q. O(1)
r. O(n)
s. O(n×n)
t. None of these.
Ans:b
8.Worst case time complexity of Linear search is
u. O(1)
v. O(n)
w. O(n×n)
x. None of these.
Ans:b
9. Efficiency is usually measured in terms of abstract computations, such as data moves and the memory used. True.

10.Sorting is the process of putting items in a predetermined order, such as increasing or decreasing order.


11.The simplest form of search is …
y. Binary search
z. Linear search
aa. Both
bb. None of these
Ans:b

12.Linear search is applicable to a table organized in
cc. Array
dd. Linked list
ee. Tree
ff. None of these
Ans:a,b
13.Sequential search is applicable to a table organized in
gg. Array
hh. Linked list
ii. Tree
jj. None of these
kk. Ans:a,b

14.The algorithm for sequential search is…
ll. for(i=0;iif (key != k (i))
return (i);
return (-1);
mm. for(i=0;iif (key == k (i))
return (i);
return (-1);
nn. None of these
oo. All of these
Ans:b

15.An efficient linear search method involves inserting the argument key at the end of the array before beginning the search, thus guaranteeing that the key will be found. The algorithm for this is …
pp. for(i=0;iif (key == k (i))
return (i);
return (-1);
qq. k(n) = key;
for (i=0;key != k(i);i++);
if( ireturn( i );
else
return (-1);
rr. None of these
ss. All of these
Ans:b

16.The efficiency of searching a list is ___________ by adding a sentinel node containing the argument key at the end of the list.
tt. Decreased
uu. Improved (as the for loop condition is simplified “k(p) != key”)
vv. None of these
ww. All of these
Ans:b

17.An efficient linear search method involves inserting the argument key at the end of the array before beginning the search, thus guaranteeing that the key will be found. The extra key inserted at the end of the array is called as
xx. Metical
yy. Sentinel
zz. Ultimo
aaa. All of these
Ans:b

18.The sentinel method of linear search requires an…
bbb. Additional external pointer
ccc. Additional internal pointer
ddd. None of these
eee. All of these
Ans:a
19.Linear search is a kind of _____________ .
Ans. search

20.Transpose sequential search is a kind of ___________
fff. linear search
ggg. binary search
hhh. sequential search
iii. none of the above
Ans:a,c
21._______________ is a part of or used in linear search.
Ans. move-to-front heuristic.

22.______________ is a part of or used in sequential search.
Ans. move-to-front heuristic.

Hashing Interview Question Part 3

24. Which of the following are not hash functions?
a. division
b. coupling
c. folding
d. extraction
e. mid square
Ans. c



25. The following paragraph is connected with hashing:
The process of mapping large amounts of data into a smaller table is called …… (i) ……. A good hash function should satisfy two criteria, namely quickness to compute and minimisation of the number of …… (ii) ……. Minimization of …… (iii) …… can be achieved by choosing a hash function that spreads the incoming data as evenly as possible over the hash table.

Correct terms for the blanks positions are:
(a) (i) indexing (ii) collisions (iii) couplings
(b) (i) hashing (ii) collisions (iii) couplings
(c) (i) hashing (ii) collisions (iii) collisions
(d) (i) indexing (ii) collisions (iii) collisions

Ans. c


26. What is the best definition of a collision in a hash table?
a. Two entries are identical except for their keys.
b. Two entries with different data have the exact same key.
c. Two entries with different keys have the same exact hash value.
d. Two entries with the exact same key have different hash values.
Ans. c
27. The phenomenon wherein two keys that hash into different values compete with each other in successive rehashes is called ____________ .
Ans. primary clustering
28. ________ is a collision resolution technique that puts all the elements that hash to the same slot in a linked list.
a. chaining
b. open addressing
c. closed addressing
d. hashing
Ans. a
29. Given a hash table T with m slots that stores n elements,the load factor is
a. α = m*n
b. α = n/m
c. α = m+n
d. α = m/n
Ans. b
30. If a hash table in which collision are resolved by chaining, a successful search takes ______ time on the average, under the assumption of simple uniform hashing.
a. Q(1+a)
b. θ(1+α)
c. Ω(1+α)
d. O(1+α)
Ans. a
31. Inserting an element into an open-address hash table with load factor a requires at most ______ probes on average, assuming uniform hashing.
a. 1/(1+α)
b. 1/(1-α)
c. 1+α
d. 1/α
Ans. b

32. One of the collision resolution techniques and the methods used is open addressing include __________ .
Ans. Overflow block

33. The collision resolution techniques and methods used in closed addressing include
i)linked list
ii) binary tree
iii) overflow block
The correct options are
a. i and ii only
b. i only
c. ii only
d. i,ii and iii only
Ans. a

Hashing Interview Question Part 2

11. A hash table that grows to handle more items is called
a.optimal hashing
b.dynamic hashing
c.minimal perfect hashing
d.none
Ans:b
12. The associated hash function must change as the table grows in dynamic hashing.(T/F)
Ans:True
13. A hash table in which the hash function is the last few bits of the key and the table refers to buckets is called
a.optimal hashing
b.dynamic hashing
c.minimal perfect hashing
d.Extendible hashing
Ans:d
14. A dynamic hashing table that grows one slot at a time is called
a.linear hashing
b.dynamic hashing
c.minimal perfect hashing
d.Extendible hashing
Ans:a
15.Linear hashing is also known as
a.Decremental hashing
b.Incremental hashing
c.Extendible hashing
d.none
Ans:b
16. A dictionary implemented with two hash tables of equal size, T1 and T2, and two different hash functions, h1 and h2.
a.optimal hashing
b.dynamic hashing
c.minimal perfect hashing
d.2-left hashing
Ans:d
17. A variant of a hash table in which keys are added by hashing with two hash functions is called
a.optimal hashing
b.2-choice hashing
c.minimal perfect hashing
d.2-left hashing
Ans:b
18. The average-case cost of a successful search is__________ for 2-choice hashing where m is the number of keys and n is the size of the array
a. O(2 + (m-1)/n)
b.O(1+(m-1)/n)
c.O(3+(m-1)/n)
d.none
Ans:a
19. A conceptual method of open addressing for a hash table is called
a.Universal hashing
b.Uniform hashing
c.Optimal hashing
d.none
Ans:b
20. The assumption or goal that items are equally likely to hash to any value is called
a.Simple uniform hashing
b.Uniform hashing
c.Optimal hashing
d.none
Ans:a
21. A method of open addressing for a hash table in which a collision is resolved by searching the table for an empty place at intervals given by a different hash function, thus minimizing clustering is called
a.double hashing
b.Uniform hashing
c.Optimal hashing
d.none
Ans:a
22.Double hashing is also known as rehashing(T/F)
Ans:True
23. A scheme that chooses randomly from a set of hash functions is called
a.double hashing
b.Uniform hashing
c.Optimal hashing
d.universal hashing
Ans:d

Hashing Interview Question Part 1

1. A function that maps keys to integers, usually to get an even distribution on a smaller set of values is called ______
Ans: Hash function
2. A dictionary in which keys are mapped to array positions by hash functions is called
a.hash table
b.view table
c.Both
d.none
Ans:a
3.A hash function f defined as f(key) = key mod 7, with linear probing, is used to insert the keys 37,38,72,48,98,11,56,into a table indexed from 0 to 6. 11 will be stored in the location
a.3 b.4 c.5 d.6
Ans:c
f(37)=37 mod 7 =2.
So,37 will be put in location 2.f(38)=3.
So,38 will be in third location.
F(72)=2. This results in a collision. With linear probing as the collision resolving strategy, the alternate location for 72 will be the location 4. Continuing this way, the final configuration will be 98,56,37,38,72,11,48.
Hence the answer.

4. Having the keys of more than one item map to the same position is called a __________
Ans: collision.
5. A hash function that maps each different key to a distinct integer is called
a.perfect hashing
b.internal hashing
c.external hashing
d.none
Ans:a
6. Usually all possible keys must be known beforehand in perfect hashing.(T/F)
Ans:True
7. A hash table that uses a perfect hash has
a. 1 collision
b.no collisions
c.Multiple collisions
d.none
Ans:b
8.Perfect hashing is also called
a.optimal hashing
b.dynamic hashing
c.cuckoo hashing
d.none
Ans:a
9. A perfect hashing function that maps each different key to a distinct integer and has the same number of possible integers as keys is called
a.optimal hashing
b.dynamic hashing
c.minimal perfect hashing
d.none
Ans:c
10. A minimal perfect hashing function for keys in S such that if k1, k2 ∈ S and k1 > k2, then f(k1) > f(k2) is called ____
Ans:Order preserving minimal perfect hashing

Greedy Strategy Interview Question Part 5

44. The minimum spanning tree of a graph give the shortest distance between any 2 specified nodes.(True or False)
Ans. False
Minimal spanning tree assures that the total weight of the tree is kept at its minimum. But it doesn’t mean that the distance between any two nodes involved in the minimum-spanning tree is minimum.

45. Dijkstra’s algorithm solves the _____________ shortest path problem.
Ans. single- source

46. The time required to run Dijkstra’s algorithm is ___________
a. O( ElogV)
b. O( |E| logV)
c. O( |E| log |V| )
d. O( log V)
Ans. c


47. Dijkstra algorithm finds the shortest path from a source to all the other nodes in a
weighted graph. Can you use Dijksta algorithm to find the shortest path from a source
node to all the other nodes in non-weighted graph?
a) No, because I wouldn’t know which edge to include in the cloud at each step
b) Yes, I could associate weight 0 to each edge and apply Dijkstra
c) No, because I wouldn’t be able to label the nodes
d) Yes, I could associate weight 1 to each edge and apply Dijkstra ***
e) None of the above




48. Suppose I want to find a spanning tree of a ring graph (see an example of ring graph
below) represented by an adjacency list. Can I use a BFS traversal? What would be the
complexity of BFS traversal as a function of n (number of nodes)?
a) yes, for a ring with n nodes the complexity would be always O(n) ***
b) yes, for a ring with n nodes the complexity would be always O(n2)
c) yes, for a ring with n nodes the complexity would be O(n2) in the worst case
d) yes, for a ring with n nodes the complexity would be O(n log n)
e) no, BFS is an algorithm to visit the nodes, not to construct a spanning tree. I could use
Prim to construct a spanning tree


49. What would be the complexity of Prim algorithm on a graph with n nodes and m
edges, if the priority queue is implemented with a sorted sequence based on an array.
a) O(n2+ n)
b) O(n2 + m)
c) O( n + mn)
d) O( n + n2)
Ans:c

50. You are given the following graph. If you use Dijkstra algorithm from node v you
will obtain a shortest path spanning tree from v. Which of the following algorithms
could also create a shortest path spanning tree starting from node v?
a) DFS and BFS
b) Prim and BFS
c) BFS only
d) DFS only
Ans:b

Greedy Strategy Interview Question Part 4

32. Lossless compression refers to
a. data that can be uncompressed exactly as it was before compression
b. Huffman coding
c. The assumption that data need not be stored perfectly
d. a and b
Ans. d
Huffman coding is an example of lossless compression wherein the characters are converted into a binary code such that the original text can be retrieved as it was.


33. State whether the following statement is true or false
The basic idea in Huffman coding is to assign short codewords to those input blocks with low probabilities and long codewords to those with high probabilities.
Ans. False
The basic idea in Huffman coding is to assign short codewords to those input blocks with high probabilities and long codewords to those with low probabilities.

34. Dijkstra’s Algorithm determines
a. Shortest Path between every pair of vertices
b. Paths between every pair of vertices
c. Paths between every pair of vertices
d. Shortest path only between a given source and multiple destinations
Ans. d

35. Which is an example of a minimum spanning tree algorithm?
a. Kruskal's
b. Huffman
c. Euler's
d. Fibonacci
Ans. a

36.. Kruskal's Algorithm can be solved on the Bases of __________.
a. Cost
b. Nodes
c. Edges
d. Tree
Ans. a

37. Huffman code is a
a. fixed-to-variable length code
b. variable-to-fixed length code
c. variable-to-variable length code
d. fixed-to-fixed length code
Ans. a

38. An edge of a spanning tree is called a ________
Ans. branch

39. An edge in the graph that is not in the spanning tree is called a ________
a. tree
b. branch
c. chord
d. root
Ans. c

40. Spanning trees are important because of following reasons.
i)Spanning trees construct a sparse sub graph that tells a lot about the original graph.
ii)Spanning trees a very important in designing efficient routing algorithms.
iii)Some hard problems (e.g., Steiner tree problem and traveling salesman problem) can be solved approximately by using spanning trees.
iv)Spanning trees have wide applications in many areas, such as network design, etc. Which of the following options are correct?
a. i,ii and iii
b. i and iii
c. all the above
d. ii and iv
Ans. c
41. A minimum spanning tree is a graph that has the following properties:
● it spans the graph
● it is a minimum
State whether the above statement is true or false.
Ans. True
42. Which of the following algorithms solves the all-pair shortest path problem?
a. Dijkstra’s algorithm
b. Floyd’s algorithm
c. Prim’s algorithm
d. Warshall’s algorithm
Ans. b
Dijkstra’s algorithm solves single source shortest path problem.Warshall’s algorithm finds transitive closure of a given graph.Prim’s algorithm constructs a minimum cost spanning tree for a given weighted graph
43. In kruskal’s algorithm
i)the selection function chooses edges in increasing order of their length
ii)cycle has to be formed
iii)result is a forest of trees that grows until all the trees merge into one.
The correct options are
a. i and ii
b. i,ii and iii
c. i and iii
d. ii and iii
Ans. c
In kruskal's algorithm the selection function chooses edges in increasing order of length without worrying too much about their connection to previously chosen edges, except that never to form a cycle. The result is a forest of trees that grows until all the trees in a forest (all the components) merge in a single tree

Greedy Strategy Interview Question Part 3

23. ___________ is to be sent with Huffman code for its decompression.
a. Original string
b. only tree
c. Only frequent occurring characters
d. Coded string
Ans. d
24. In Huffman coding,the code with highest frequency character contains _________ bit(s).
a. Maximum
b. Minimum
c. One
d. Equal
Ans. b
25. Greedy algorithms are
a. simple and straightforward
b. longsighted in approach
c. many problems can be solved correctly by greedy approach
d. all of the above
Ans. a
Greedy algorithms are simple and straightforward. They are shortsighted in their approach in the sense that they take decisions on the basis of information at hand without worrying about the effect these decisions may have in the future. They are easy to invent, easy to implement and most of the time quite efficient. Many problems cannot be solved correctly by greedy approach. Greedy algorithms are used to solve optimization problems
26. To construct the solution in an optimal way,Greedy algorithm maintains two sets. One contains ___________ and the other contains ___________ .
Ans. chosen items and rejected items .
27. The greedy algorithm consists of following functions.
1. A function that checks whether chosen set of items provide a solution.
2. A function that checks the feasibility of a set.
3. The selection function tells which of the candidates is the most promising.
4. An objective function, which does not appear explicitly, gives the value of a solution.
The correct options are
a. 1 and 2
b. 2 and 4
c. 1,2 and 3
d. All the above
Ans. d
The greedy algorithm consists of four (4) function.
1. A function that checks whether chosen set of items provide a solution.
2. A function that checks the feasibility of a set.
3. The selection function tells which of the candidates is the most promising.
4. An objective function, which does not appear explicitly, gives the value of a solution.

28. The ____________ and _________________ are two ingredients in the problem that lend to a greedy strategy .
Ans. Greedy-choice property and optimal substructure.
The "greedy-choice property" and "optimal substructure" are two ingredients in the problem that lend to a greedy strategy.
29. A greedy strategy usually progresses in a _____________, making one greedy choice after another.
a. bottom-up fashion
b. linear fashion
c. top-down fashion
d. none of the above
Ans. c
A greedy strategy usually progresses in a top-down fashion, making one greedy choice after another, reducing each problem to a smaller one.
30. Greedy-Choice Property says that a globally optimal solution can be arrived at by making a ________ optimal choice.
Ans. locally
Greedy-Choice Property says that a globally optimal solution can be arrived at by making a locally optimal choice .
31. A spanning tree of a graph is any tree that includes every ________ in the graph.
Ans. vertex

Greedy Strategy Interview Question Part 2

11. Lossless encoding techniques include
i) Run length encoding
ii) Huffman encoding
iii) Transform coding
The correct option is
a. i
b. i and ii
c. all of the above
d. only ii
Ans. b
12. Disjoint sets are __________ sets.
Ans. mutually exclusive/independent
13. The disjoint set is an abstract data type that supports ___________ and _________ operations.
Ans. Union and find
14. Union(x,y) is an operation in disjoint set which means merge the set containing x with the set containing y. (True or False)
Ans. True
15.Find(x) should return some representation of the set containing x. (True or False)
Ans. True
16.Running time of find(i) is proportional to the _________of the tree containing node i.
Ans. height
17. Minimum spanning tree gives shortest distance between
a. any two nodes
b. source and destination
c. source and any node
d. none
Ans. b
In minimum spanning tree,we get the shortest path between the source and the destination.
18. The shortest path algorithm gives minimum distance between
a. any two nodes
b. source and destination
c. all of the above
d. source and any node
Ans. a
19. The cost of a path between two vertices is the sum of the _________ of the edges in that path.
Ans. costs
20. Huffman’s coding technique uses ____________ algorithm.
Ans. Greedy algorithm
21. Huffman coding uses __________
a. tree
b. graph
c. linked list
d. stack
Ans. a
22. The data structure used for the implementation of Kruskal’s algorithm is
a. Graph
b. Linked list
c. stack
d. disjoint set
Ans. d

Greedy Strategy Interview Question Part 1

1. Huffman’s greedy algorithm
a is a lossy compression technique
b. computes frequency of occurrence of characters
c. assigns binary codes to a string of characters
d. b and c
Ans. d

2. Huffman’s greedy algorithm has a total running time of
a. O(log n)
b.O(n)
c. O(nlogn)
d. O(n*n)
Ans. c

3. Greedy algorithms are used for
i)optimization problems
ii)always make a locally optimal choice
iii)widely applied:Dijkstra’s algorithm and MST
The correct options are
a)i and ii
b)i and iii
c)all of the above
d)only i
Ans. c
4. A graph may have ________ number of spanning trees.
Ans. many
5. Kruskal’s algorithm is also known as _________ algorithm.
Ans. Greedy algorithm
6. Kruskal’s algorithm works faster on sparse graphs.( True or False).
Ans. True
7. Every spanning tree on n points contains exactly
a. n edges
b. n-1 edges
c. n(n-1) edges
d. n-2 edges
Ans . b
8. the time required by Kruskal’s algorithm is _______ where E stands for edges and V for vertices
a. O( |E| + log |V| )
b. O( ElogV)
c. O( |E|log|V| )
d. O( log |V| )
Ans. c
9. A minimum spanning tree is a minimum-weight tree in a ________ graph which contains all of the graph’s vertices.
Ans. weighted
10. Travelling salesman problem can be best solved by using a
a. Minimum spanning tree algorithm
b. Dijkstra algorithm
c. Floyd algorithm
d. None of the above
Ans. a

Selection Sort Interview Question Part 3

27. What is the output of selection sort for the following numbers after the 8th pass?
3 6 9 2 7 10 1 5 8 4
a. 1 2 3 4 5 6 10 9 8 7
b. 1 2 3 4 5 6 7 9 8 10
c.1 2 3 4 5 6 7 8 9 10
d. 1 2 3 4 7 10 9 6 8 5
Ans:c

28. What is the output of selection sort for the following numbers after the 9th pass?
3 6 9 2 7 10 1 5 8 4
a. 1 2 3 4 5 6 10 9 8 7
b. 1 2 3 4 5 6 7 9 8 10
c.1 2 3 4 5 6 7 8 9 10
d. 1 2 3 4 7 10 9 6 8 5
Ans:c


29. What is the output of selection sort after the 1st pass given the following sequence of numbers: 7 3 5 1 9 8 4 6
a. 1 7 5 3 9 8 4 6
b. 1 3 7 5 9 8 4 6
c. 1 3 4 7 9 8 5 6
d. 1 3 4 5 9 8 7 6
Ans:a

30. What is the output of selection sort after the 2nd pass given the following sequence of numbers: 7 3 5 1 9 8 4 6
a. 1 7 5 3 9 8 4 6
b. 1 3 7 5 9 8 4 6
c. 1 3 4 7 9 8 5 6
d. 1 3 4 5 9 8 7 6
Ans:b

31. What is the output of selection sort after the 3rd pass given the following sequence of numbers: 7 3 5 1 9 8 4 6
a. 1 7 5 3 9 8 4 6
b. 1 3 7 5 9 8 4 6
c. 1 3 4 7 9 8 5 6
d. 1 3 4 5 9 8 7 6
Ans:c

32. What is the output of selection sort after the 4th pass given the following sequence of numbers: 7 3 5 1 9 8 4 6
a. 1 7 5 3 9 8 4 6
b. 1 3 7 5 9 8 4 6
c. 1 3 4 7 9 8 5 6
d. 1 3 4 5 9 8 7 6
Ans:d

33. What is the output of selection sort after the 5th pass given the following sequence of numbers: 7 3 5 1 9 8 4 6
a. 1 7 5 3 9 8 4 6
b. 1 3 7 5 9 8 4 6
c. 1 3 4 7 9 8 5 6
d. 1 3 4 5 6 8 7 9
Ans:d

34. What is the output of selection sort after the 6th pass given the following sequence of numbers: 7 3 5 1 9 8 4 6
a. 1 3 4 5 6 7 8 9
b. 1 3 7 5 9 8 4 6
c. 1 3 4 7 9 8 5 6
d. 1 3 4 5 9 8 7 6
Ans:a

Selection Sort Interview Question Part 2

14.The efficiency of selection sort is
a.n*(n/2)
b.n*n
c.n(n-1)/2
d.none
Ans:a
The first loop goes from 0 to n, and the second loop goes from x to n, so it goes from 0 to n, then from 1 to n, then from 2 to n and so on. The multiplication works out so that the efficiency is n*(n/2), though the order is still O(n^2).
15.The frequency count of selection sort is
a.n*n
b.n(n-1)/2
c.n
d.logn
Ans:b
(n-1)+(n-2)+……+3+2+1=n(n+1)/2 – n =n(n-1)/2

16.The total number of iterations in selection sort is
a.n-1
b.n
c.n*n
d.2*n
Ans:a


17. For a List with L elements numbered from 0 to L-1 , the selection sort algorithm is

Set marker to L-1 (begin with the last element in the list)
While marker>0
Find the largest element in the range numbered from 0 to marker.
Swap that element with the element at location marker.
Increase marker back by 1
Assume the initial list is 3, 9, 1,7 ,2

What are the correct intermediate output values during the process of sorting?
a.3, 2, 1, 7, 9
b.3, 9, 1, 2, 7
c.1, 2, 3, 7, 9
d.9, 3, 1, 2, 7
Ans:a

18. Consider the following selection sort algorithm and the integer data set given thereafter.
For a list with L elements numbered from 0 to L-1, the selection sort algorithms is :
1. Set marker to L-1 (beginning with the last element in the list)
2. While marker >0 ;
i. Find the largest element in the range numbered from 0 to marker.
ii. Swap the largest element with the element at the location marker.
iii. Increase marker back by 1
Data set: { 4 10 2 8 3 }
If the above algorithm works on the given data set , what would not be the pair of swapping values during the
process of sorting?
(a) (3,10) (b) (4,2) (c) (2,3) (d) (10,2)
Ans: d

19. Let there be a list with L elements numbered from 0 to L-1, and consider the following algorithm:

Step 1: set marker1 to L-1 (begin with the location of the last element in the list)
Step 2: While marker > 0
Step 3: find the largest element in the range numbered from 0 to marker
Step 4: swap that element with the element at location marker.
Step 5: Increase marker by 1
The above algorithm describes
(a) Bubble sort. (b) Selection sort. (c) Insertion sort. (d)Merge sort
Ans:b
20.What is the output of selection sort for the following numbers after the first pass?
3 6 9 2 7 10 1 5 8 4
a. 1 6 9 3 7 10 2 5 4 8
b. 1 6 9 3 7 2 10 5 8 4
c.1 6 9 3 7 10 2 5 8 4
d. 1 6 9 7 3 10 2 5 8 4
Ans:c

21. What is the output of selection sort for the following numbers after the 2nd pass?
3 6 9 2 7 10 1 5 8 4
a. 1 6 9 3 7 10 2 5 4 8
b. 1 2 9 6 7 10 3 5 8 4
c.1 6 9 3 7 10 2 5 8 4
d. 1 2 6 9 7 10 3 5 8 4
Ans:b

22. What is the output of selection sort for the following numbers after the 3rd pass?
3 6 9 2 7 10 1 5 8 4
a. 1 2 3 6 7 10 9 5 8 4
b. 1 2 9 6 7 10 3 5 8 4
c.1 6 9 3 7 10 2 5 8 4
d. 1 2 6 9 7 10 3 5 8 4
Ans:a

23. What is the output of selection sort for the following numbers after the 4th pass?
3 6 9 2 7 10 1 5 8 4
a. 1 2 3 6 7 10 9 5 8 4
b. 1 2 9 6 7 10 3 5 8 4
c.1 6 9 3 7 10 2 5 8 4
d. 1 2 3 4 7 10 9 6 8 5
Ans:d

24. What is the output of selection sort for the following numbers after the 5th pass?
3 6 9 2 7 10 1 5 8 4
a. 1 2 3 6 7 10 9 5 8 4
b. 1 2 9 6 7 10 3 5 8 4
c.1 2 3 4 5 10 9 7 8 6
d. 1 2 3 4 7 10 9 6 8 5
Ans:c

25. What is the output of selection sort for the following numbers after the 6th pass?
3 6 9 2 7 10 1 5 8 4
a. 1 2 3 4 5 6 10 9 8 7
b. 1 2 9 6 7 10 3 5 8 4
c.1 2 3 4 5 10 9 7 8 6
d. 1 2 3 4 7 10 9 6 8 5
Ans:a

26.What is the output of selection sort for the following numbers after the 7th pass?
3 6 9 2 7 10 1 5 8 4
a. 1 2 3 4 5 6 10 9 8 7
b. 1 2 3 4 5 6 7 9 8 10
c.1 2 3 4 5 10 9 7 8 6
d. 1 2 3 4 7 10 9 6 8 5
Ans:b

Selection Sort Interview Question Part 1

1.What is the output of selection sort after the 1st iteration given the following sequence of numbers: 14 9 4 18 45 2 37 63
a. 4 14 9 18 45 2 37 63
b. 2 9 14 18 45 4 37 63
c. 4 9 14 18 45 2 37 63
d.2 14 9 18 45 4 37 63
Ans:d


2. What is the worst case complexity for selection sort algorithm
a.O(n) b.O(n*n) c.O(nlogn) d.O(logn)
Ans:b

3.What is the average case complexity for selection sort algorithm
a.O(n) b.O(n*n) c.O(nlogn) d.O(logn)
Ans:b

4.What is the output of selection sort after the 2nd iteration given the following sequence of numbers: 16 3 46 9 28 14
a.3 9 46 16 28 14
b.3 9 14 16 28 46
c.3 9 16 14 46 28
d.none of the above
Ans:a



5.What is the best case complexity for selection sort algorithm
a.O(n) b.O(n*n) c.O(nlogn) d.O(logn)
Ans:b

6.The following loop is used for
For i<- 1 to N
For j<- i+1 to N
If(a(i)>a(j))
{
Temp=a(i);
A(i)=a(j);
A(j)=temp;
}
a.bubble sort b.selection sort c.insertion sort d.merge sort
Ans:b

7.Here is an array of six integers:
5 3 8 9 1 7
This array after the FIRST iteration in a selection sort (sorting from smallest to largest) is
a. 5 1 8 4 3 7
b. 1 8 5 4 3 7
c.1 5 8 4 3 7
d. 1 5 8 4 7 3
Ans:c
8.In a selectionsort of n elements, how many times is the swap function called in the complete execution of the algorithm?
A. 1
B. n - 1
C. n log n
D. n²
Ans:B
9.A sorting technique in which successive elements are selected in order and placed into their proper sorted positions is called
a.selection sort
b.quick sort
c.bubble sort
d.merge sort
Ans:a


10.The selection sort that uses descending priority queue as an unordered array is_____
Ans:straight selection sort

11.Straight selection sort is also called
a.Push-down sort
b. Push-up sort
c.both
d.none
Ans:a

12.The types of selection sort are
a.General selection sort b.Pull-up selection sort c. Push-up selection sort d.none
Ans:a


13.In which cases are the time complexities same in selection sort?
a. Worst and Best
b. Best and Average
c. Worst and Average
d. Worst, average and Best
Ans:d

Quick Sort Interview Question Part 2

17. Which of the following statement(s) best describes the quicksort algorithm
(a)Partitioning the file into two subfiles, selecting some pivot value, sorting the two sub-files sequentially.
(b)Selecting some pivot value, partitioning the file into N sub-files and sorting independently, merging all sub-files into single file.
(c)Selecting some pivot value, partitioning the file into two sub-files, sorting the two sub-files independently in recursive way.
(d)Partitioning the file into two sub-files, sorting these two sub-files independently, then partitioning two sub-files into four sub-files, sorting these four sub-files independently. This process is repeating until entire file becomes sorted.
Ans:c


18. If one chooses the middle key as the pivot, what would be the Big-O value for the Best case of the Quick Sort Algorithm? (a) n*n (b) n (c) a constant (d) n log n
Ans:d


19. Which of the following is/are correct in connection with the time complexity of the quick sort algorithm in the worst case, best case and average case respectively? (a) n*n, n, nlog n (b) nlog n, nlog n, nlog n (c) n*n, nlog n, nlog n (d) n, n, nlog n
Ans:c
20. The basic quicksort algorithm is recursive and consists of four steps, but the following steps are in incorrect order.
(i) Pick any element v in S. This element is called pivot.
(ii) Return the result of Quicksort(L), followed by v, followed by quicksort(R)
(iii) Partition S – {v} (the remaining elements in S) into two disjoint groups: L={x S – {v} | x =< v} and R={x S – {v} | x >v }
(iv) If the number of elements in S is 0 or 1 then return.

Which of the following is the correct order of steps in the quicksort algorithm?
(a) (iv), (iii),(i),(ii)
(b) (i),(ii),(iii),(iv)
(c) (iv), (i),(iii),(ii)
(d) (i),(iii),(ii),(iv)
Ans:c


21. Which of the following activities is/are not relevant to the quick sort algorithm?
(a) Initially divide the entire file into N sub-files.
(b) Choose a pivot value and store it in a correct place.
(c) The sorting technique is sorting by exchange.
(d) The sorting technique is sorting by selection.
Ans:a,d
22. If the last element is chosen as the pivot at each iteration, the Quick-sort tree for
the sequence in question 1 will have height:
a)1
b) 2
c) 3
d)4
Ans:c


23. If Quick-sort were implemented so that the element at position n/2 is chosen as
the pivot, which of the following sequences would be the worst input?
a) 1 2 3 4 5 6 7
b) 2 3 4 1 5 6 7
c) 7 6 5 4 3 2 1
d) 5 6 7 1 2 3 4
e) 6 4 2 7 1 3 5
Ans:d

24. Given a large amount of highly random data which fits into the computers RAM,
the best choice for sorting would be:
a) Bubble-sort
b) Insertion-sort
c) Merge-sort
d) Quick-sort
Ans:d

25. In Quick sort , after the completion of every pass the pivot/key element moves to the ________ position. a.first b.second c.middle d.exact sorted position
Ans:d

Quick Sort Interview Question Part 1

1.Quick sort is 1.in-place 2.non in-place 3.stable 4.non-stable a.1 and 3 b.1 and 4 c.2 and 3 d.2 and 4
Ans:b


2.What is the average case complexity for quick sort algorithm a.O(n) b.O(n*n) c.O(nlogn) d.O(logn)
Ans:c


3.What is the worst case complexity for quick sort algorithm a.O(n) b.O(n*n) c.O(nlogn) d.O(logn)
Ans:b

4.What is the best case complexity for quick sort algorithm a.O(n) b.O(n*n) c.O(nlogn) d.O(logn)
Ans:c

5.Quick sort is also known as a. Pointer sort b.External sorting c.Both d.none
Ans:c

6.What is the output of quick sort after the 1st iteration given the following sequence of numbers: 65 70 75 80 85 60 55 50 45 a. 60 45 50 55 65 85 80 70 75 b.60 45 50 55 65 85 80 75 70 c. 45 60 50 55 65 85 80 75 70 d. 60 45 50 65 55 85 80 75 70
Ans:b

7.Which sorting technique is also called partition exchange sort? a.selection sort b.quick sort c.bubble sort d.merge sort
Ans:b

8. In which cases are the time complexities same in quick sort? a. Worst and Best b. Best and Average c. Worst and Average d. Worst, average and Best
Ans:b

9. Quick sort uses ___________. a. Divide and Conquer Technique b. Greedy Approach c. Back Tracking d. None of the above
Ans. a

10. What pattern of splits gives the worst-case performance for quick sort? a. Ascending order. b. Descending order.
c. Any order.
d. None of the above.
Ans. b

11.In quick sort the pivot value is usually the
a.first element
b.last element
c.middle element
d.any element
Ans: d

12. What is the output of quick sort after the 2nd iteration given the following sequence of numbers: 65 70 75 80 85 60 55 50 45
a. 60 45 50 55 65 85 80 70 75
b.60 45 50 55 65 85 80 75 70
c.55 45 50 60 65 70 80 75 85
d. 60 45 50 65 55 85 80 75 70
Ans:c

13.What is the output of quick sort after the 3rd iteration given the following sequence of numbers: 65 70 75 80 85 60 55 50 45
a. 60 45 50 55 65 85 80 70 75 b.60 45 50 55 65 85 80 75 70 c.55 45 50 60 65 70 80 75 85 d. 50 45 55 60 65 70 80 75 85
Ans:d

14.What is the output of quick sort after the 4th iteration given the following sequence of numbers: 65 70 75 80 85 60 55 50 45
a. 45 50 55 60 65 70 75 80 85
b.60 45 50 55 65 85 80 75 70
c.55 45 50 60 65 70 80 75 85
d. 50 45 55 60 65 70 80 75 85
Ans:a

15. Which of the following statements about Quick sort is/are incorrect?
a. Average running time is O(N log N).
b. The best case always occurs when the pivot partitions the set of numbers to be sorted into two equal-sized subsets.
c. The worst case always occurs when the pivot partitions the set of numbers to be sorted into two equal-sized subsets.
d. The worst case always occurs when the smallest item is selected from the items to be sorted as the pivot.
Ans. c



16. Which statement(s) is/are correct for the Quick sort algorithm?
(i) Quick Sort is still best sorting algorithms, known for sequential computers
(ii) It works by partitioning the file into two sub files and sorting two sub files independently.
(iii) The pivot value can be chosen in an arbitrary way.
a.(i) only
b.(i) and (iii) only
c.(i), (ii) and (iii).
d.(ii) and (iii)
Ans:c

Merge Sort Interview Question Part 2

16. Given the initial sequence : 3,41,52,26,38,57,9,49 ,at the last step in the merge sort .the sequences to be merged are
a.{ 3,26,52,41} and {38,49,57,9}
b.{ 3,26,41,52} and {9,38,49,57}
c. {3,9,41,52} and {26,38,49,57}
d. {3,9,26,38} and {41,49,52,57}
Ans. b

17. Mergesort makes two recursive calls. Which statement is true after these recursive calls finish, but before the merge step?
a. The array elements form a heap
b. Elements in each half of the array are sorted among themselves
c. Elements in the first half of the array are less than or equal to elements in the second half of the array
d. . Elements in the first half of the array are greater than or equal to elements in the second half of the array
Ans. b
18. Given the initial sequence: {85 24 63 47 17 31 96 50}, at the last step in the
merge sort, the sequences to be merged are:
a). {24 47 63 85} and {17 31 50 96}
b). {17 24 31 47} and {50 63 85 96}
c). {24 85} {47 63} {17 31} and {50 96}
d). {17 24 31 47 63 85 96} and {50}
e). depends on choice of pivot
Ans. a
19.On each iteration,the size of the sorted lists in a merge sort
a. doubles
b. halves
c.remains the same
d. increases 4 times
Ans. a
On each iteration, the size of the sorted lists doubles, form 1 to 2 to 4 to 8 to 16 ...to n.

20. What is the output of merge sort after the 1st pass given the following sequence of numbers: 12 13 1 5 7 9 11 14
a. 12 13 1 5 7 9 11 14
b. 1 5 12 13 7 9 11 14
c. 1 5 7 9 11 12 13 14
d. 1 5 7 9 12 13 11 14
Ans:a


21. What is the output of merge sort after the 2nd pass given the following sequence of numbers: 12 13 1 5 7 9 11 14
a. 12 13 1 5 7 9 11 14
b. 1 5 12 13 7 9 11 14
c. 1 5 7 9 11 12 13 14
d. 1 5 7 9 12 13 11 14
Ans:b

22. What is the output of merge sort after the 3rd pass given the following sequence of numbers: 12 13 1 5 7 9 11 14
a. 12 13 1 5 7 9 11 14
b. 1 5 12 13 7 9 11 14
c. 1 5 7 9 11 12 13 14
d. 1 5 7 9 12 13 11 14
Ans:c


23. In every pass, maximum number of comparisons in the merge sort is _________.
a.n-1
b.n
c.log n
d.n*n
Ans:a

24.What does the following pseudocode do?

function sort(m)
var list left, right
if length(m) ≤ 1
return m
else
middle = length(m) / 2
for each x in m up to middle
add x to left
for each x in m after middle
add x to right
left = sort(left)
right = sort(right)
result = app(left, right)
return result
end if
a. quick sort
b. selection sort
c. insertion sort
d. merge sort
Ans. d