UGC NET SOLVED PAPER

COMPUTER NETWORK

====================================================
                                                  UNIT-1
====================================================

--------------- have a single communication channel that is shared by all the users on the network.

a. Point-to-poit

b. Broadcast networks

c. Protocol

d. PAN
====================================================
Question 2

A node, which is more powerful, and can handle local information processing or graphics processing is called a------------------.

a. Workstation

b. Server

c. Network Operating System

d. Peer system
====================================================
Question 3

Computer networks may be classified according to the -------------- at which they operate according to some basic reference models that are considered to be standards in the industry such as the----------- OSI reference model and the -----------TCP/IP model.

a. network layer, seven layer, four layers

b. transport layer, five layer, six layer

c. Physical layer, five layer, four layer

d. Physical layer, four layer, four layer
====================================================
Question 4

The term Computer Network is used to mean an interconnected collection of------------------------

a. Mini computers

b. Super computers

c. autonomous computers

d. Micro computers
====================================================
Question 5

The world wide Internet is a well known example of ------------------.

a. PAN

b. Subnet

c. Intra-Network

d. inter-network

====================================================
                                      UNIT-2
====================================================
Question 1

Match the following.

Physical Layer        Choose... Dialogues control Routing Packet Raw bits Data encryption

Network Layer     Choose... Dialogues control Routing Packet Raw bits Data encryption

Session Layer      Choose... Dialogues control Routing Packet Raw bits Data encryption

Presentation Layer   Choose... Dialogues control Routing Packet Raw bits Data encryption
====================================================
Question 2

------------------- is a set of rules governing the format and meaning of the packets, or messages that are exchanged by the peer entities within a layer.

a. Interface

b. Reference model

c. protocol

d. None of these
====================================================
Question 3
-------------, is a technique of conversion between the representation of digital data in user equipment and the corresponding signals transmitted over a communications channel.

a. Line coding

b. Demodulation

c. Modulation

d. Segmentation
====================================================
Question 4

In OSI-ISO architecture -------------------- layer is concerned with transmitting raw bits over the communication channel .

a. Data link Layer

b. Physical Layer

c. Session Layer

d. All of these
====================================================
Question 5

Which Layer is Responsible for Congestion Control ?

a. Network Layer

b. Datalink Layer

c. Transport Layer

d. Application layer
====================================================
                                                 UNIT=3
=====================================================

Question 1

E-mail is an example of _______________ mode of communication where one party can send a note to another person and the recipient need not be online to receive the e-mail.

a. asynchronous
b. synchronous
c. full duplex
d. either A) or B)
=====================================================

Question 2

Videoconferencing is an example for ___________________ communication

a. Simplex
b. Half duplex
c. Full duplex
d. serial
=====================================================
Question 3
What are the advantages of synchronous communication. 1. it reduces overhead bits 2. The character is self contained & Transmitter and receiver need not be synchronized 3. It overcomes the two main deficiencies of the asynchronous method, that of inefficiency and lack of error detection. 4. Transmitting and receiving clocks are independent of each other

a. 1,2, and 3
b. 1 and 3
c. 1,2 and 4
d. 1,2,3 and 4
=====================================================
Question 4
_____________ results from interference of different frequencies sharing the same medium.
a. Intermodulation
b. Cross talk
c. Impluse
d. Thermal noise
=====================================================
Question 5
______________ is/ are caused by the random motion of the electrons in a wire and is unavoidable.

a. Dispersion
b. Thermal noise
c. Delay distortion
d. all of these
=====================================================
                                               UNIT=4
=====================================================
Question 1

FDM Choose... Light streaming digital communication analog communication internet

TDM Choose... Light streaming digital communication analog communication internet

WDM Choose... Light streaming digital communication analog communication internet

Packet switching Choose... Light streaming digital communication analog communication internet
=====================================================

Question 2

Following are the advantages of tree topology i)Point-to-point wiring for individual segments. ii)Supported by several hardware and software venders. iii) Easy to install and wire

a. i) only

b. i) and ii) only

c. iii) only

d. i) ,ii) and iii)
=====================================================
Question 3

The most well-Known use of _________________ is internet

a. Packet switching

b. circuit switching

c. message switching

d. multiplexing
=====================================================
Question 4

The type of network topology in which all of the nodes of the network are connected to a common transmission medium which has exactly two endpoints is called ________________________

a. Bus

b. Ring

c. Tree

d. Mesh
=====================================================
Question 5

_______________ combines characteristics of linear bus and star topologies.

a. Ring topology

b. A hybrid topology

c. A tree topology

d. mesh topology

=====================================================
                                                     UNIT=5
=====================================================
Question 1

CAT3 cable Choose... 16 to 100 MHz 250 MHz to 600 MHz high speed computer communication 2 GHz t0 40 GHz

CAT5 cable Choose... 16 to 100 MHz 250 MHz to 600 MHz high speed computer communication 2 GHz t0 40 GHz

CAT6 & CAT 7 cable Choose... 16 to 100 MHz 250 MHz to 600 MHz high speed computer communication 2 GHz t0 40 GHz

wireless transmission Choose... 16 to 100 MHz 250 MHz to 600 MHz high speed computer communication 2 GHz t0 40 GHz

=====================================================

Question 2

The key concern in the design of transmission system is _____________ and _____________

a. data rate ,distance

b. speed, accuracy

c. accuracy, simplicity

d. distance , cost
=====================================================
Question 3

Transmission medias are classified into two main categories, which are ______________ and _______________.

a. twisted pair, coaxial

b. guided , unguided

c. analog, digital

d. synchronous, Asynchronous
=====================================================
Question 4

Which of the following transmission media suffers more from transmission impairment.

a. coaxial cable

b. Optical fiber

c. twisted pair

d. wave guides
=====================================================
Question 5

Which of these is an example for unguided transmission ?

a. coaxial cable

b. optical fibers

c. wireless

d. twisted pairs
=====================================================
                                                 UNIT-6
====================================================
Question 1

State true or false
i) The Hamming Distance for the codes generated using either even or odd parity will be 2. ii) The DLL translates the physical layers raw bit stream into discrete units called packets iii) The network layer wants messages to be delivered to the remote peer in the exact same order as they are sent. iv) The data link layer is split into MAC and LLC sub layers.

a. true, true, true true

b. true, false , true, false

c. true, false, true, true

d. true, true, false, false
====================================================
Question 2

The DLL translates the physical layer's raw bit stream into discrete units called __________________

a. packets

b. messages

c. frames

d. TPDU
====================================================
Question 3

The data link layer is split into __________________ and ___________________ sub layers.

a. MAC , LLC

b. MCC , LAC

c. MCM , LCM

d. CRC , MLC
====================================================
Question 4

The Hamming Distance for the codes generated using either even or odd parity will be__________________

a. 2

b. 4

c. 1

d. 0
====================================================
Question 5   Which layer transfers data between adjacent network nodes in a wide area network or between nodes on the same local area network segment.

a. physical layer

b. Data link layer

c. Network layer

d. Session layer
====================================================
                                                    UNIT-7
====================================================

Question 1

Match the following

preamble Choose... 1 byte 2 byte error checking 10101010

SOF Choose... 1 byte 2 byte error checking 10101010

checksum Choose... 1 byte 2 byte error checking 10101010

Length Choose... 1 byte 2 byte error checking 10101010
====================================================

Question 2

preamble field of 802.3 frame is encoded using __________________ encoding

a. Manchester

b. differential Manchester

c. Bi polar

d. uni polar
====================================================

Question 3

Pure ALOHA has a maximum throughput of __________________

a. 16.4 %

b. 18.4 %

c. 17.4 %

d. 1 %
====================================================

Question 4

What is the pattern of a preamble ?

a. 11110000

b. 11111111

c. 00000000

d. none of these
====================================================
Question 5

Who defined ALOHA protocol ?

a. Claude shanon

b. Nyquist

c. Abramson

d. Newton
====================================================
                                               UNIT-8
====================================================
Question 1
How many levels of priority is defined in IPV4 protocol?

a. 4

b. 2

c. 8

d. 6
====================================================

Question 2

State true or false i) Low bandwidth lines cause congestion ii) Slow processors cause congestion. iii) Adding more memory increase congestion

a. true, true, false

b. false ,true, false

c. true, false , false

d. true , true, true
====================================================
Question 3

Where are routing tables placed ?

a. in network interface card

b. in routers memory

c. in server memory

d. in a subnet's memory
====================================================
Question 4

Which of these is/are the properties of routing algorithm ?

a. correctness

b. simplicity

c. stability

d. all of these
====================================================
Question 5

__________________is a static algorithm in which every incoming packet is sent out on every outgoing line except the one it arrives on.

a. Flooding

b. Congestion

c. Link state routing

d. Distance vector
====================================================
                                              UNIT=9
====================================================
Question 1

How many bits are reserved for future use in TCP protocol ?

a. 4

b. 6

c. 7

d. 2
====================================================
Question 2

Packet lifetime can be restricted to a known maximum by using this /these method.

a. Restricted subnet design

b. putting a hop counter in each packet

c. time stamping each packet

d. all of these
====================================================
Question 3

State true or false

1. TCP protocol is a connection less protocol. 2. Automatic repeat request schemes may be used to retransmit lost or corrupted data. 3. Automatic repeat request may keep the network in a congested state. 4. TPDU is an acronym for transfer product data unit.

a. true true true true

b. False true false false

c. false true true false

d. true false false true
====================================================
Question 4

State true or false i. The connection establishment protocol introduced by Tomlinson is known as a three way handshake. ii. Asymmetric release is the way the telephone system works. iii. The 16-bit checksum field is used for error-checking of the header and data.

a. false, false, false

b. true, true, true

c. true, false, false

d. false, false, true
====================================================
Question 5
TPDU is an acronym for _________________

a. Transport protocol data unit

b. trasferent product data unit

c. transitive product data unit

d. transfer protocol digital unit
====================================================
Question 6
Two main important protocols of transport layer are ________________ and __________________.
a. SMTP, HTTP

b. TCP, UDP

c. UDP, HTTP

d. SMTP, UDP
====================================================
Question 7

Which of these function belongs to transport layer ?

a. routing of packets

b. congestion control

c. email

d. none of these
====================================================
Question 8

Which of these is a minimal message-oriented transport layer protocol.

a. UDP

b. SMTP

c. HTTP

d. TCP/IP
====================================================
Question 9

Which of these layer is responsible for flow control ?

a. Network layer

b. Transport Layer

c. session layer

d. Application Layer
====================================================
Question 10

Which of these protocol guarantees reliable and in-order delivery of data from sender to receiver. ?

a. TCP/IP

b. UDP

c. STP

d. TDP
====================================================
Question 11

_________________ is/are used for error detection.

a. Parity bit

b. checksum

c. both A) and B)

d. neither A) nor B).
====================================================
                                             UNIT-10
====================================================
Question 1

Match the following

Network layer Choose... Gateway HUB Switch Router

Data link layer Choose... Gateway HUB Switch Router

Transport layer Choose... Gateway HUB Switch Router

Physical layer Choose... Gateway HUB Switch Router
====================================================
Question 2

DSL stands for _________________

. a. data subscriber lines

b. dual subscriber lines

c. digital subscriber lines

d. delay subscriber lines
====================================================
Question 3

Hubs are classified as _______________ and _________________ hubs.

a. active, passive

b. synchronous, asynchronous

c. simplex, half duplex

d. one way , multi way
====================================================
Question 4

In ___________________ configuration, the switch begins to forward the packet as soon as it is received. No error checking is performed on the packet, so the packet is moved through very quickly.

a. cut-free

b. franment-free

c. store-and-forward

d. cut-through
====================================================
Question 5

State true or false i. Both hubs and switches come in managed and unmanaged versions. ii. A bridge unlike repeaters will not start retransmission until it has received the complete packet. iii. The looping problem cannot be avoided by using the Spanning Tree Algorithm (STA).

a. true, true, true

b. false, true, false

c. true, true, false

d. false, false, false
====================================================
Question 6

Which of these cable is/are used to connect devices to hubs and switches.

a. crossover

b. straight-through

c. co-axial

d. both A) and B)
====================================================
Question 7

Which of these device operate at the network layer of OSI/ISO reference model.

a. HUB

b. ROUTER

c. SWITCH

d. ALL OF THESE
====================================================
Question 8
Which of these is a feature of hubs ?

a. Hubs amplify the incoming signal.

b. Hubs understand frames, packets or headers

c. All lines coming into a Hub must operate at a same speed.

d. all of these
====================================================
Question 9

_______________ are fast multi-port bridges that provide an economical way to resolve network congestion.

a. Switches

b. Gateways

c. Routers

d. Brouters
====================================================

NOTE: ALL ANSWERS ARE IN RED COLOR .

============================================================

Unit 01 - Quiz Questions
==========================

1._____ is a collection of programs written to service other programs.

a. System software

b. Real time software

c. Business software

d. Embedded software
============================================================

2._____ is a set of application programs.

a. Software

b. Hardware

c. Algorithm

d. Pseudo code
============================================================
3. The role of computer software has undergone significant change over a time span of little more than _____ years.

a. 30

b. 40

c. 50

d. 60
============================================================
4.Software delivers the most important product of our time i.e. _____.
a. Money

b. Information

c. Knowledge

d. Wealth
============================================================
5. Software is a _____ element.

a. Physical

b. Static

c. Dynamic

d. Logical
============================================================
Unit 02 - Quiz Questions

============================================================
1.Software Engineering is a sub discipline of _____.
a. Computer science engineering

b. Electronics engineering

c. Mechanical engineering

d. Civil engineering
============================================================
Question 2

The cost of software engineering includes roughly _____ % of development costs and _____ % of testing costs.
a. 50, 50

b. 60, 40

c. 40, 60

d. 70, 30
============================================================
Question 3

Software Engineering is the systematic approach to the development, operation, maintenance and retirement of software. This definition is given by _____.

a. Bauer

b. Boehm

c. IEEE

d. Charles Babbage

============================================================
Question 4

Rapid Application Development (RAD) assumes the use of _____ generation techniques.

a. fourth

b. first

c. second

d. third

============================================================
Question 5

_____ model is also called as the classic life cycle or the Waterfall model.

a. Iterative Development

b. Incremental Development

c. Spiral Development

d. Linear Sequential Development
============================================================

UNIT-3
============================================================

The specifications, called _____ govern how the component is to interact with other components and systems.

a. Contracts

b. Agreements

c. Bonds

d. Requirements

============================================================
Question 2

The _____ of a software system is a measure of how well users think it provides the services that they require.

a. Reliability

b. Fault tolerance

c. Fault avoidance

d. Fault detection
============================================================
Question 3
_____ is a measure of the frequency of occurrence with which unexpected behavior is likely to occur.

a. Probability of Failure on Demand (POFOD)

b. Availability (AVAIL)

c. Rate of Failure Occurrence (ROCOF)

d. Mean Time to Failure (MTTF)

============================================================
Question 4

_____ is a measure of the likelihood that the system will fail when a service request is made.

a. Rate of Failure Occurrence (ROCOF)

b. Probability of Failure on Demand (POFOD)

c. Mean Time to Failure (MTTF)

d. Availability (AVAIL)
============================================================
Question 5

_____ is a measure of the time between observed system failures.

Choose one answer. a. Probability of Failure on Demand (POFOD)

b. Rate of Failure Occurrence (ROCOF)

c. Availability

d. Mean Time to Failure (MTTF)

============================================================
UNIT-4

============================================================

Question 1
In _____ design, the sub-systems making up the system and their relationships are identified and documented.

a. Architectural

b. Abstract

c. Interface

d. Component
============================================================
Question 2

In _____ model data flow diagrams may be used to show how data is processed at different stages in the system.

a. Data Processing

b. Composition

c. Classification

d. Process
============================================================
Question 3

In _____ model entity-relation diagrams may be used to show how some entities in the system are composed of other entities.

a. Classification

b. Composition

c. Stimulus-response

d. Process
============================================================
Question 4

In _____ model objects class/inheritance diagrams may be used to show how entities have common characteristics.

a. Composition

b. Process

c. Classification

d. Data Processing
============================================================
Question 5

_____ is a list of names used by the systems, arranged alphabetically.

a. Software list

b. Hardware list

c. Data Directory

d. Data Dictionary
============================================================

UNIT=5

============================================================
Question 1

A/An _____ is an entity that has a state and a defined set of operations, which operate on that state.

a. Class

b. Message

c. Interface

d. Object
============================================================
Question 2

Objects are organized into a/an _____ structure that shows how one object is composed of a number of other objects.

a. Aggregation

b. Hierarchy

c. Inheritance

d. None of the above
============================================================
Question 3

_____ is concerned with developing an object-oriented model of a software system to implement the identified requirements.

a. Object oriented programming

b. Object oriented design

c. Procedural programming

d. Object oriented analysis
============================================================
Question 4

_____ is concerned with developing an object-oriented model of the application domain.

a. Object oriented analysis

b. Object oriented design

c. Object oriented programming

d. Functional programming
============================================================
Question 5

_____ is concerned with realizing a software design using an object oriented programming language.

a. Object oriented design

b. Structural programming

c. Object oriented programming

d. Object oriented analysis
============================================================
                                   UNIT:6
==========================================================
Question 1
The process of changing a system after it has been delivered and is in use is called _____

a. Configuration Management

b. Software Maintenance

c. Software Re-engineering

d. Software Refactoring

==========================================================
Question 2

_____ is concerned with taking existing legacy systems and re-implementing them to make it more maintainable.

a. Configuration Management

b. Software Maintenance

c. Software Re-engineering

d. Software Refactoring
==========================================================

Question 3

_____ is the process of analyzing a program in an effort to create a representation of the program at a higher level of obstruction than source code.

a. Reverse Engineering

b. Forward Engineering

c. Document Restructuring

d. Inventory Analysis
==========================================================
Question 4

_____ is the process of factoring the design module.

a. Configuration Management

b. Software Maintenance

c. Software Re-engineering

d. Software Refactoring

==========================================================

Question 5

_____ is the process, which controls the changes made to a system and manages the different versions of the evolving software product.
a. Configuration Management

b. Software Maintenance

c. Software Re-engineering

d. Software Refactoring
==========================================================
                                        UNIT:7

==========================================================

Question 1

Black-box testing, also called _____

a. Behavioral testing

b. Structural testing

c. System testing

d. Unit testing
==========================================================
Question 2
Testing should begin "_____" and progress toward testing "_____".

a. In the large, in the small

b. In the small, in the large

c. In the medium, in the medium

d. None of the above
==========================================================
Question 3

Testing time and resources are _____

a. Abundant

b. Unlimited

c. Limited

d. None of the above
==========================================================
Question 4

The Pareto principle implies that _____ percent of all errors uncovered during testing will likely be traceable to _____ percent of all program components.

a. 80, 20

b. 50, 50

c. 20, 80

d. 60, 40
==========================================================
Question 5

White-Box testing, sometimes called _____ testing

a. Plastic-box testing

b. Iron-box testing

c. Metal-box testing

d. Glass-box testing
==========================================================

                                                          UNIT:8
==========================================================
Question 1

_____ does provide the last bastion from which quality can be assessed and, more pragmatically, errors can be uncovered.

a. Analysis

b. Coding

c. Testing

d. Maintenance
==========================================================
Question 2

_____ involves testing the modules at the lower levels in the hierarchy, and then working up the hierarchy of modules until the final module is tested. (4 marks)

a. Bottom-up testing

b. Black-box testing

c. Top-down testing

d. White-box testing
==========================================================
Question 3
_____ refers to a set of activities that ensure that the software that has been built is traceable to customer requirements. (1 mark)

a. Testing

b. Validation

c. Maintenance

d. Verification
==========================================================
Question 4

_____ refers to the set of activities that ensure that software correctly implements a specific function.

a. Verification

b. Validation

c. Testing

d. Maintenance
==========================================================
Question 5

_____ testing tests the high levels of a system before testing its detailed components.

a. White-box

b. Bottom-up

c. Black-box

d. Top-down
==========================================================
                                                     UNIT-9
==========================================================
Question 1

In the spiral model of software engineering process, _____ testing begins at the vertex of the spiral.

a. Unit

b. System

c. Integration

d. White-box
==========================================================

Question 2

Integration testing makes heavy use of _____ testing techniques.

a. Red-box

b. Green-box

c. White-box

d. Black-box
==========================================================
Question 3

Modules are integrated by moving _____ through the control hierarchy, beginning with the main control module.

a. Downward

b. Upward

c. Sideward

d. None of the above
==========================================================
Question 4

Testing begins at _____ level.

a. System

b. Component

c. Module

d. None of the above
==========================================================
Question 5
Testing within the context of software engineering is a series of _____ steps that are implemented sequentially.

a. Two

b. Four

c. Three

d. Five
==========================================================
Question 6

The software engineering process may be viewed as the _____ model.

a. Relational

b. Incremental

c. Bottom-up

d. Spiral
==========================================================
Question 7

Unit testing makes heavy use of _____ testing techniques, exercising specific paths in a module's control structure to ensure complete coverage of maximum error detection.

a. Black-box

b. Green-box

c. White-box

d. Red-box
==========================================================
Question 8

_____ is a set of activities that can be planned in advance and conducted systematically.

a. Testing

b. Validation

c. Verification

d. Maintenance
==========================================================
Question 9

_____ must be accommodated in any testing strategy.

a. Analysis

b. Coding

c. Debugging

d. Maintenance
==========================================================
Question 10

_____ testing begins construction and testing with atomic modules.

a. Top-down integration

b. Bottom-up integration

c. Sideward integration

d. None of the above

==========================================================
                                                   UNIT-10
==========================================================

Question 1

Business schools have been using case studies for years to develop a student's _____ abilities.

a. Analytical

b. Logical

c. Arithmetical

d. Soft skill
==========================================================
Question 2

Clients communicate with the databases through _____.

a. C

b. Structured Query Language (SQL).

c. C++

d. Java
==========================================================
Question 3

For any organization, _____ will be the top most priority.

a. Growth

b. System availability

c. Backup

d. Recovery
==========================================================
Question 4

In any organization, central databases will be available in _____.

a. Corporate office

b. Regional offices

c. Local offices

d. None of the above
==========================================================
Question 5

In order to protect the competitors from hacking into the highly sensitive information of an organization _____ should be used.

a. Database software

b. Network software

c. OS software

d. Security software
==========================================================
Question 6

The important data for any organization is _____.

a. HR records

b. Employee details

c. Customer's transactions

d. Maintenance files
==========================================================
Question 7

_____ is a key factor in determining the system's success.

a. System breakdown

b. Data integrity

c. Growth

d. System recovery
==========================================================
Question 8

_____ is a most popularly used relational database system.

a. Oracle

b. Access

c. Excel

d. Power Point
==========================================================
Question 9

_____ is an example for messaging and queuing software.

a. Sybase

b. MQ Series

c. Informix

d. DB2
==========================================================
Question 10

_____ is responsible for distributing data across the systems.

a. COBRA

b. COARB

c. CORBA

d. COBAR
==========================================================

1. Suppose cursor refers to a node in a linked list (using the IntNode class with instance variables Called data and link). What statement changes cursor so that it refers to the next node?

A. cursor++;

B. cursor = link;

C. cursor += link;

D. cursor = cursor.link;

2. Suppose cursor refers to a node in a linked list (using the Node class with instance variables called data and link). What boolean expression will be true when cursor refers to the tail node of the list?

A. (cursor == null)

B. (cursor.link == null)

C. (cursor.data == null)

D. (cursor.data == 0.0)

E. None of the above.

3. Which boolean expression indicates whether the numbers in two nodes (p and q) are the same. Assume that neither p nor q is null.

A. p == q

B. p.data == q.data

C. p.link == q.link

D. None of the above.

4. Suppose that p is a reference variable that contains the null reference. What happens at runtime if the program tries to activate a method of p?

A. IllegalArgumentException

B. IllegalStateException

C. NullPointerException

D. The results are unpredictable.

5. Suppose that a method has one node as a parameter and it returns two references to nodes. What's the best header for the method?

A. IntNode foo(IntNode p)

B. IntNode, IntNode foo(IntNode p)

C. IntNode[ ] foo(IntNode p)

D. void foo(IntNode p, IntNode answer1, IntNode answer2)

6. In the linked list version of the Bag class an instance variable manyNodes is used to keep track of how long the linked list is. Why not just make a call to the IntNode method listLength()?

A. The listLength() method is O(n) and the alternative is O(1).

B. The listLength() method is private.

C. The listLength() method results in an infinite loop for circular lists.

D. The listLength() method works only for lists of integers.

7. Suppose that the Bag is implemented with a linked list. Which of these operations are likely to have a constant worst-case time?

A. add

B. countOccurrences

C. remove

D. None of (A), (B), and (C) have a constant worst-case time

E. TWO of (A), (B), and (C) have a constant worst-case time

F. ALL of (A), (B), and (C) have a constant worst-case time

8. What is the expression for generating a pseudorandom number in the range 1...N?

A. (int) (Math.random() * N);

B. (int) (Math.random() / N);

C. (int) (Math.random() * (N + 1));

D. (int) (Math.random() / (N + 1));

E. (int) (Math.random() * N) + 1;

9. Which expression computes a pseudorandom integer between -10 and 10 using rand() from stdlib.h?

A. (int) (Math.random( ) * 20) - 10

B. (int) (Math.random( ) * 21) - 10

C. (int) (Math.random( ) * 22) - 10

D. (int) (Math.random( ) * 20) - 11

E. (int) (Math.random( ) * 21) - 11

10. For the linked-list version of the Sequence ADT, which operations are constant time operations in the worst case?

A. addAfter is constant time, but not addBefore

B. addBefore is constant time, but not addAfter

C. Both addAfter and addBefore are constant time

D. Neither addAfter nor addBefore are constant time

11. Suppose that the Sequence is implemented with a linked list. Which of these operations are likely to have a constant worst-case time?

A. addBefore

B. countOccurrences

C. remove

D. None of (A), (B), and (C) have a constant worst-case time

E. TWO of (A), (B), and (C) have a constant worst-case time

F. ALL of (A), (B), and (C) have a constant worst-case time

12. What kind of list is best to answer questions such as "What is the item at position n?"

A. Lists implemented with an array.

B. Doubly-linked lists.

C. Singly-linked lists.

D. Doubly-linked or singly-linked lists are equally best

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

A. A collection of Stacks can be sorted.

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

C. The entries must be stored in a linked list.

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

14. . The operation for adding an entry to a stack is traditionally called:

A. add

B. append

C. insert

D. push

15. The operation for removing an entry from a stack is traditionally called:

A. delete

B. peek

C. pop

D. remove

16. Which of the following stack operations could result in stack underflow?

A. is_empty

B. pop

C. push

D. Two or more of the above answers

17. . Which of the following applications may use a stack?

A. A parentheses balancing program.

B. Keeping track of local variables at run time.

C. Syntax analyzer for a compiler.

D. All of the above.

18. . Consider the following pseudocode:

declare a stack of characters

while ( there are more characters in the word to read )

{

read a character

push the character on the stack

}

while ( the stack is not empty )

{

pop a character off the stack

write the character to the screen

}

19.What is written to the screen for the input "carpets"?

1. A. serc

2. B. carpets

3. C. steprac

4. D. ccaarrppeettss

20. Here is an INCORRECT pseudocode for the algorithm which is supposed to determine whether a sequence of parentheses is balanced:

declare a character stack

while ( more input is available)

{

read a character

if ( the character is a '(' )

push it on the stack

else if ( the character is a ')' and the stack is not empty )

pop a character off the stack

else

print "unbalanced" and exit

}

print "balanced"

21.Which of these unbalanced sequences does the above code think is balanced?

A. ((())

B. ())(()

C. (()()))

D. (()))()

22. Consider the usual algorithm for determining whether a sequence of parentheses is balanced. What is the maximum number of parentheses that will appear on the stack AT ANY ONE TIME when the algorithm analyzes: (()(())(()))?

A. 1

B. 2

C. 3

D. 4

E. 5 or more

23.. Consider the usual algorithm for determining whether a sequence of parentheses is balanced. Suppose that you run the algorithm on a sequence that contains 2 left parentheses and 3 right parentheses (in some order). What is the maximum number of parentheses that will ever appear on the stack AT ONE TIME during the computation?

A. 1

B. 2

C. 3

D. 4

E. 5 or more

24. Suppose we have an array implementation of the stack class, with ten items in the stack stored at data[0] through data[9]. The CAPACITY is 42. Where does the push method place the new entry in the array?

A. data[0]

B. data[1]

C. data[9]

D. data[10]

25.. Consider the implementation of the Stack using a partially-filled array. What goes wrong if we try to store the top of the Stack at location [0] and the bottom of the Stack at the last used position of the array?

A. Both peek and pop would require linear time.

B. Both push and pop would require linear time.

C. The Stack could not be used to check balanced parentheses.

D. The Stack could not be used to evaluate postfix expressions.

26. In the linked list implementation of the stack class, where does the push method place the new entry on the linked list?

A. At the head

B. At the tail

C. After all other entries that are greater than the new entry.

D. After all other entries that are smaller than the new entry.

27.. In the array version of the Stack class, which operations require linear time for their worst-case behavior?

A. is_empty

B. peek

C. pop

D. push when the stack is below capacity

E. None of these operations require linear time.

28.. In the linked-list version of the Stack class, which operations require linear time for their worst-case behavior?

A. is_empty

B. peek

C. pop

D. push

E. None of these operations require linear time.

29.What is the value of the postfix expression 6 3 2 4 + - *:

A. Something between -15 and -100

B. Something between -5 and -15

C. Something between 5 and -5

D. Something between 5 and 15

E. Something between 15 and 100

30. Here is an infix expression: 4+3*(6*3-12). Suppose that we are using the usual Stack algorithm to convert the expression from infix to postfix notation. What is the maximum number of symbols that will appear on the stack AT ONE TIME during the conversion of this expression?

A. 1

B. 2

C. 3

D. 4

E. 5

31. One difference between a queue and a stack is:

A. Queues require linked lists, but stacks do not.

B. Stacks require linked lists, but queues do not.

C. Queues use two ends of the structure; stacks use only one.

D. Stacks use two ends of the structure, queues use only one.

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

A. ABCD

B. ABDC

C. DCAB

D. DCBA

Which of the following expressions evaluates to true with approximate probability equal to P? (P is double and 0 <= P <= 1).

A. Math.random() < P

B. Math.random() > P

C. Math.random() < P * 100

D. Math.random() > P * 100

33. Suppose we have a circular array implementation of the queue class, with ten items in the queue stored at data[2] through data[11]. The current capacity is 42. Where does the insert method place the new entry in the array?

A. data[1]

B. data[2]

C. data[11]

D. data[12]

34. Consider the implementation of the Queue using a circular array. What goes wrong if we try to keep all the items at the front of a partially-filled array (so that data[0] is always the front).

A. The constructor would require linear time.

B. The getFront method would require linear time.

C. The insert method would require linear time.

D. The isEmpty method would require linear time.

36. Consider an undirected graph G with n vertices and e edges. What is the time taken by Depth First Search(DFS) if the graph is represented by(i)Adjacency matrix, and(ii)Adjacency list?

(a) O(n^2),O(n) (b) O(n^2),O(e)

(c) O(e),O(n^2) (d) O(e + n),O(e)

37 . An undirected graph G with n vertices and e edges is represented by adjacency list. What is the time required to generate all the connected components?

(a) O(n) (b) O(e)

(c) O(e + n) (d) O(e^2)

38 . Which of the following statements is false?

(a) every tree is a bipartite graph (b) a tree contains a cycle

(c) a tree with n nodes contains (d) a tree is a connected graph

n-1 edges

39 . A graph G with n nodes is bipartite if it contains

(a) n edges (b) a cycle of odd length

(c) no cycle of odd length (d) n^2 edges

40 . In what tree, for every node the height of its left sub tree and right subtree differ at least by one

(a) binary search tree (b) AVL-tree

(c) Complete tree (d) Threaded binary tree

41 . Which of the following sorting method is stable?

(a) straight insertion sort (b) binary insertion sort

(c) Shell sort (d) Heap sort

42 . A complete binary tree with the property that the value at each node is at least as large as the values at its children is known as

(a) binary search tree (b) AVL tree

(c) Completely balanced tree (d) Heap

43. The recurrence relation T(n)=mT(n/2)+an^2 is satisfied by

(a) T(n) = O(n^m) (b) T(n) = O(n log m)

(c) T(n) = O(n log m) (d) T(n) = O(m log n)

44. The time required to find shortest path in a graph with n vertices and e edges is

(a) O(e) (b) O(n)

(c) O(e^2) (d) O(n^2)

45. The goal of hashing is to produce search that takes

(a) O(1) time (b) O(n^2)time

(c) O(log n)time (d) O(n log n)time

46. In which of the folling sorting algorithm the num of comparisons needed is the minimum

if the items sre initially in reverse order and is maximum if the items are in order?

(a) Straight insertion (b) Binary insertion sort

(c) Heap sort (d) Bubble sort

47. Which of the following best describes sorting?

(a) accessing and processing each record exactly once

(b) finding the location of the record with a given key

(c) arranging the data (record) in some given order

(d) adding a new record to the data struture

48. The order of magnitude of the worst case performance of the linear search over N elements is

(a) N log2 n (b) N

(c) N^2 (d) log2 N

49. The order of magnitude of the worst case performance of the binary search ove N elements is

(a) N log2 n (b) N

(c) N^2 (d) log2 N

50. The order of magnitude of the worst case performance of ordered binary tree with N elements is

(a) N log2 N (b) N

(c) Hash coded search (d) Radix search

51. A search procedure which associates an address with a key value and provides a machnism

for dealing with two or more values assigned to the same address is called

(a) Linear search (b) Binary search

(c) Hash coded search (d) Radix search

52. The order of magnitude of the worst case performance of a coded search (over N elements) is

(a) N (b) N log2 N

(c) log2 N (d) not dependent upon N

53. When key values are reals a similar data representation might de produced by using a hashing function with

(a) mod (b) heap sort

(c) trunc (d) log N

54. A characteristic of the data that binary search uses but the linear search ignores, is the

(a) insertion sort (b) length of the list

(c) maximum value in the list (d) bubble sort

55. A sort which compares adjacent element in a list and switch where nessary is a

(a) insertion sort (b) heap sort

(c) quick sort (d) bubble sort

56. A sort which iteratively passes through a list to exchange the first element with any element

less than it and then repeats with a new first element is called

(a) insertion sort (b) selection sort

(c) heap sort (d) quick sort

57. A full binary tree with n leaves contains

(a) n nodes (b) log2 n nodes

(c) 2n-1 nodes (d) 2^n nodes

58. A full binary tree with n non leaf nodes contains

(a) log2 n nodes (b) n+1 nodes

(c) 2n nodes (d) 2n+1 nodes

59. A sort which uses the binary tree concept such that any number is larger than all the numbers

in the subtree below it is called

(a) selection sort (b) insertion sort

(c) heap sort (d) quick sort

60. Which of the following sortingalgorithms does not have a worst case running time of O(n^2)

(a) insertion sort (b) merge sort

(c) quick sort (d) bubble sort

61. Which of the following sortingalgorithms has a worst case running time of O(n^r)where

1 ?<="" p="">

(a) bubble sort (b) insertion sort

(c) shell sort (d) merge sort

62 . For a linear search in an array of n elements the time complexity for best, worst and average cases are…., …and ……respectively.

(a) O(n),O(1),and O(n/2) (b) O(1),O(n) and O(n/2)

(c) O/1, O(n) and O(n) (d) O(1), O(n) and(n-1/2)

63 . What is the minimum number of fields with each node of doubly linked list

(a) 1 (b) 2

(c) 3 (d) 4

64 . Let A be a sorted array of n = 10 elements. Assume that only one comparison is required to determine whether the target is equal to, less than, or greater than A[i].Which of the following denotes the average successful time of finding an arbitrary element x in A using binary search?

(a) 1.6 (b) 2.9

(c) 4.2 (d) 5.5

65 . A digital search key is implemented as a tree with n nodes each of which can contain m pointers, corresponding to the m possible symbols in each position of the key. The number of nodes that must be accessed to find a particular tree is

(a) m (b) n

(c) n^m (d) m^n

66. In the linked list implementation of the queue class, where does the insert method place the new entry on the linked list?

1. A. At the head

2. B. At the tail

3. C. After all other entries that are greater than the new entry.

4. D. After all other entries that are smaller than the new entry.

67. In the circular array version of the Queue class, which operations require linear time for their worst-case behavior?

a. A. getFront

b. B. insert when the capacity has not yet been reached

c. C. isEmpty

d. D. None of these operations require linear time.

68. In the linked-list version of the Queue class, which operations require linear time for their worst-case behavior?

a. A. getFront

b. B. insert

c. C. isEmpty

d. D. None of these operations require linear time.

69. If data is a circular array of CAPACITY elements, and rear is an index into that array, what is the formula for the index after rear?

a. A. (rear % 1) + CAPACITY

b. B. rear % (1 + CAPACITY)

c. C. (rear + 1) % CAPACITY

d. D. rear + (1 % CAPACITY)

70. I have implemented the queue with a circular array, keeping track of front, rear, and manyItems (the number of items in the array). Suppose front is zero, and rear is one less than the current capacity. What can you tell me about manyItems?

a. A. manyItems must be zero.

b. B. manyItems must be equal to the current capacity.

c. C. count could be zero or the capacity, but no other values could occur.

d. D. None of the above.

Ques.#71

The number of edges in a complete graph of n vertices is

(a) n

(b) n(n-1)/2

(c) n(n-1)/2

(d) n^2/2

Ques.#72

A vertex of in-degree zero in a directed graph is called a/an

(a) articulation point

(b) sink

(c) isolated vertex

(d) root vertex

Ques.#73

If there exists at least on path between every pair of vertices in a graph,the graph is known as

(a) connected graph

(b) complete graph

(c) planar graph

(d) simple graph

Ques.# 74

The minimum number of spanning trees in a connected graph with n vertices is

(a) 1

(b) n-1

(c) 2

(d)n/2

Ques.#75

The number of edges in a spanning tree of a graph with n vertices is

(a) (n-1)/2

(b) n-1

(c) n(n+1/2

(d) n^2/2

Ques.#76

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 has value.

(d) Two entries with the exact same key have different hash values.

Ques.#77

Which guideline is NOT suggested from empirical or theoretical studies of hash table;

(a) Hash table size should be the product of two primes.

(b) Hash table size should be the upper of pair of twin primes.

(c) Hash table size should have the form 4K+3 for some K.

(d) Hash table size should not be too near a power of two.

Ques.#78

To represent a binary tree of height h using an array,an array of minimum size_______ will be required.

(a) 2^h

(b) 2h+1

(c) 2^h-1

(d) 2(h-1)

Ques.#79

Which of the following statement is true about topological sort of a directed graph?

(a) It indicate precedence among vertices representing events.

(b) It is basically a linear ordering of vertices such that if a graph

contains edge(u,v) then u appears before v in the ordering.

(c) Topological sort is possible only if the directed graph is acyclic.

(d) All of above

Ques.#80

Which of the following is not an open addressing technique to resolve collisions?

(a) Quadratic probing

(b) Double hashing

(d) Cubic probing

(d) Linear probing.

Ques.#81

A chained hash table has an array size of 512.What is the maximum number of entries that can be placed in the table?

(a) 256

(b) 512

(c) 1024

(d) There is no maximum.

Ques.#82

Given an array named nums containing 22 integer numbers sorted on descending order?In the worst case,what will be number of comparison performed by binary search technique?

(a) 22

(b) 5

(c) 4

(d) 6

Ques.#83

The average case complexity of quicksort for sorting n numbers is

(a) O(log2n)

(b) O(n)

(c) O(nlog2n)

(d) O(n2)

Ques.#84

In a selection sort of n elements, how many times ,at most, the swap function is called in the complete execution of the algorithm?

(a) 1

(b) n-1

(c) nlog2n

(d) n2

Ques.#85

Merge sort and quick sort both fall into the same category of sorting algorithms. What is this category?

(a) O(nlog2n)sorts

(b) Interchange sort

(c) Average time is quadratic

(d) None of above

Ques.#86

Suppose that a selection sort of 100 items has completed 42 iteration of the main loop. How many elements are now guaranteed to be in their final spot?

(a) 21

(b) 41

(c) 42

(d) 43

Ques.#87

Suppose we are sorting an array of eight integers in the ascending order using some quadratic sorting algorithm. After four iterations of the algorithm’s main loop, the array elements are ordered as shown below here:

52 54 55 57 58 51 53

Which statement is correct ?

(a) The algorithm might be either selection sort or insertion sort

(b) The algorithm might be selection sort, but it is not insertion sort

(c) The algorithm is not selection sort, but if might be insertion sort

(d) The algorithm is neither selection sort nor insertion sort

Ques.#88

Suppose we are sorting an array of ten integers in ascending order using some quadratic sorting algorithm. After four iterations of the algorithm’s main loop,the array elements are ordered as shown here :

11 22 33 42 55 50 66 87 98 80

Which statement is correct ?

(a) The algorithm might be either selection sort or insertion sort

(b) The algorithm might be selection sort,but it is not insertion sort

(c) The algorithm is not selection sort, but if might be insertion sort

(d) The algorithm is neither selection sort nor insertion sort

Ques.#89

When is insertion sort a good choice for sorting an array?

(a) Each element of array requires a large amount of memory

(b) The processor speed is fast

(c) Each element of array requires a small amount of memory

(d) The array has only a few elements out of place

Ques.#90

What is the worst-case time for merge sort an array of n elements in element in descending order?

(a) O(n2)

(b) O(log2n)

(c) O(nlog2n)

(d) O(n)

Ques.#91

What is the worst-case time for quicksort to sort an array of n elements?

(a) O(n2)

(b) O(log2n)

(c) O(nlog2n)

(d) O(n)

Ques.#92

Merge sort makes two recursive calls. Which statement is true after these recursive calls finish, but before the merge step?

(a) Elements in the first of the array are less than or equal to elements in the second half of the array

(b) Array elements form a heap

(c) Elements in each half of the array are sorted amongst themselves

(d) None of the above

Ques.#93

Suppose we are sorting an array of eight integers in ascending order using quick sort, and we have just finished the first partitioning with the array looking like this:

2 5 1 7 9 12 11 10

Which statement is correct?

(a) The pivot could be the 7,but it is not the 9

(b) Neither the 7 nor the 9 is the pivot

(c) The pivot could be either the 7 or the 9

(d) The pivot is not the 7, but it could be the 9

Ques.#94

What is the best-case time for quick to sort an array of n alements?

(a) O(n2)

(b) O(log2n)

(c) O(nlog2n)

(d) O(n)

Ques.#95

Suppose we are sorting an array of eight integers in ascending order, using heapsort, and we have just finished one of the downheap operations. The array now looks like this:

6 4 5 1 2 7 8

How many downheap downward have been performed

(a) 1

(b) 2

(c) 3

(d) 4

Ques.#96

What is the best-case time for quicksort to sort an array of n elements?

(a) O(n2)

(b) O(log2n)

(c) O(nlog2n)

(d) O(n)

Ques.#97

Consider te following array

23 15 5 12 40 10 7

After the first pass of a particular algorithm,the array looks like

15 5 12 23 10 7 40

Name the algorithm used

(a) Heap sort

(b) Selection sort

(c) Insertion sort

(d) Bubble sort

Ques.#98

Which of the following algorithms can be used even if all the elements of an array are not available before stating the process?

(a) Heap sort

(b) Shell sort

(c) Tree sort

(d) Bubble sort

Ques.#99

A queue where all the elements have equal priority is a

(a) LIFO data structure

(b) FIFO data structure

(c) LILO data structure

(d) ILFO data structure

Ques.#100

With an array based queue.the algorithm for enqueue operation is

(a) Save the item in position 0;shift the items towards 0;decrement rear

(b) Decrement rear;save the item in position 0;shift the item toward 0

(c) Add the item to the last location and the increment rear

(d) Increment rear and add item to te new rear location

Ques.#101

If the charaters ‘z’,’y’,’x’, and ‘w’ enqueue in a queue, in that order, and then dequeued one at a time,in what order will they be dequeued?

(a) wxzy

(b) zywx

(c) zyxw

(d) wxyz

Ques.#102

Suppose we have a circular array implementation of the queue with 18 items n the queue stored at data[12] through data[29].The CAPACITY of the queue is 30.Where does the enqueue operation place the new entry in the array?

(a) Data[30]

(b) Data[0]

(c) Data[13]

(d) Data[11]

Ques.#103

In the linked list implementation of the queue,where does the enqueue operation place the new entry in the linked list?

(a) At the beginning

(b) At the end

(c) After all other entries that are greater than the new entry

(d) After all other entries that are similar than the new entry.

Ques.#104

In the circular queue,with a fixed-sized array,which operations require linear time for its worst-case behavior?

(a) Is empty()

(b) Enqueue()

(c) Dequeue()

(d) None of the above

Ques.#105

Suppose we have implemented a circular queue with track of first element(front),last element(rear),and the number of items in the array(count).suppose front is zero and rear is CAPACITY-1.What can you tell about the count?

(a) Count must be equal to zero

(b) Count must be equal to CAPACITY

(c) Count could be equal to zero or CAPACITY,but no other values could occur

(d) None of he above.

106. Which of the following abstract data types can be used to represent a many to many relation?

(a) tree only (b) plex only

(c) graph only (d) b and c above

107. Which of the following remarks about Trie Indexing if false?

(a) It is efficient in dealing with strings of variable length.

(b) It is efficient if there are a few number of data items.

(c) The number of disk accesses can’t exceed the length of the particular string that is

searched.

(d) It can handle insertions and deletions, dynamically and efficiently.

108. The average search time of hashing with linear probing will be less if the load factor

(a) is far less than one (b) equals one

(c) is far greater than one (d) none of the above

109. Which of the following remarks about Trie Indexing is false?

(a) It is an m-ary tree.

(b) It is a search tree of order m.

(c) Successful searches should terminate in leaf nodes.

(d) Unsuccessful searches may terminate at any level of the tree structure.

110. The number of vertices of odd degree in a graph is

(a) always even (b) always odd

(c) either even or odd (d) always zero

111. A graph in which all nodes are of equal degree are known as

(a) multigraph (b) non regular graph

(c) regular graph (d) complete graph

112. A vertex of degree one is called as

(a) pendant (b) isolated vetex

(c) null vertex (d) coloured vertex

113. The maximum degree of any node in a simple graph with n vertices is

(a) n-1 (b) n

(c) n/2 (d) n-2

114. Two isomorphic graphs must have

(a) the same number of vertices (b) the same number of edges

(c) an equal number of vertices (d) all of the above

115. The terminal vertices of a path are of degree

(a) one (b) two

(c) zero (d) more than four

116. If there exists one path between every pair of vertices in a graph, the graph is known as

(a) complete graph (b) disconnected graph

(c) connected graph (d) Euler graph

117. A simple graph with n vertices and k components can have atmost

(a) n edges (b) n-k edges

(c) (n-k)(n-k-1)/2 edges (d) (n-k)(n-k+1)/2 edges

118. A given connected graph G is a Euler graph if and only if all vertices of G are of

(a) same degree (b) even degree

(c) odd degree (d) different degree

119. A circuit in a connected graph which includes every vertex of the graph is known as

(a) Euler (b) Unicursal

(c) Hamiltonian (d) Clique

120. The length of a Hamiltonian path (if exists) in a connected graph of n vertices is

(a) n - 1 (b) n

(c) n + 1 (d) n/2

121. A simple graph in which there exists an edge between every pair of vertices is called a(an)

(a) incomplete graph (b) complete graph

(c) Euler graph (d) planner graph

122. The total number of edges in a complete graph of n vertices is

(a) n (b) n2/2

(c) n(n+1)/2 (d) n(n-1)/2

123. A tree with n nodes has

(a) n/2 edges (b) n – 1 edges

(c) n edges (d) n + 1 edges

124. The number of paths between any pair of nodes in a tree on n nodes is

(a) 0 (b) 1

(c) (n – 1) (d) n

125. A complete graph with five vertices is

(a) nonplanar (b) planar

(c) a non - regular graph (d) a tree

126. Kuratowski’s first graph is the nonplanar complete graph with the smallest number of vertices.

The number of vertices is

(a) 4 (b) 5

(c) 6 (d) 7

127. I have implemented the queue with a linked list, keeping track of a front node and a rear node with two reference variables. Which of these reference variables will change during an insertion into a NONEMPTY queue?

A. Neither changes

B. Only front changes.

C. Only rear changes.

D. Both change.

128. I have implemented the queue with a linked list, keeping track of a front node and a rear node with two reference variables. Which of these reference variables will change during an insertion into an EMPTY queue?

A. Neither changes

B. Only front changes.

C. Only rear changes.

D. Both change.

129. The number of circuits in a tree with n nodes is

(a) zero (b) 1 (c) n-1 (d) n/2

130. A graph is a tree if and only if it

(a) is completely connected (b) is minimally connected

(c) contains a circuit (d) is planar

131.The minimum number of spanning trees in a connected graph with n nodes is

(a) 1 (b) 2 (c) n-1 (d) n/2

132. The rank of a graph with n vertices , e edges and k components is

(a) n (b) e- n+ k (c) n-1 (d) n+ k

133. The nullity of a graph with n vertices , e edges and k components is

(a) n (b) e-n+ k (c) n-k (d) n+ k

134. The number of elements (edges) in a cutest of a tree with n vertices is

(a) 1 (b) n/2 (c) n-1 (d) n

135. Let a graph G has edge connectivity and node connectivity. Then

(a) α < β (b) α = β (c) α >= β (d) α <= β

136. What is the edge connectivity of a complete graph with n vertices?

(a) 1 (b) n-1 (c) n +1 (d) n(n+1)/2

137. If A(G) is an incident matrix of a connected graph G with n vertices, the rank of

A(G) is

(a) 1 (b) 2 (c) n-1 (d) n

138. If G is a disconnected graph with n vertices and k components, the rank of the incident matrix A(G) of the graph is

(a) n-k-1 (b) n-k (c) n+ k-1 (d) n+ k

139. A graph with n vertices and n-1 edges that is not a tree is

(a) connected (b) disconnected (c) Eular (d) a circuit

140. If B is a circuit matrix of a graph with k components, e edges and n vertices, the

rank of B is

(a) n-k (b) e-n-k (c) e-n+ k (d) e+ n-k

141. Consider a graph G having cutest matrix C(G) and incidence matrix A(G). the rank of C(G) is

(a) same as the rank of A(G) (b) more than the rank of A(G)

(c) less than the rank of S(G) (d) independent of the rank of A(G)

142. Let X be the adjacency matrix of graph G with no self loops. The entries along the principle diagonal of X are

(a) all zeros (b) all ones

(c) both zeros and ones (d)different

143. If a graph requires k different colour for its proper colouring, then the chromatic number of the graph is

(a) k/2 (b) k-1

(c) k (d) 1

144. A graph consisting of only isolated n vertices is

(a) 1-chromatic (b) 2-chromatic

(c) 3-chromatic (d) n-chromatic

145.A graph with one or more edges(without self loop) is at least

(a) 1-chromatic (b) 2-chromatic

(c) 3-chromatic (d) n-chromatic

146. A complete graph with n vertices is

(a) 2-chromatic (b) n/2 chromatic

(c) (n-1) chromatic (d) n-chromatic

147. If d(max) is the maximum degree of the vertices in a graph G, the chromatic number of G is

(a) equal to d (b) less than or equal to d(max)

(c) less than or equal to d(max)+1 (c) greater than d(max)

148. If the vertex set V of a graph can be decomposed into two subsets V1 and V2 such that every edge in G joins a vertex in V1 with a vertex in V2, the graph is called

(a) bipartite (b) tri-partite

(c) 1-chromatic (d) V-partite

149. A covering of an n-vertex graph has atleast

(a) n/2 edge (b) [n/2] edges

(c) [(n-1)/2] edges (d) n edges

150. The number of colours required to properly colour the vertices of every planar graph is

(a) 3 (b) 2

(c) 4 (d) 5

151.If A(G) is the incidence matrix of a connected digraph of n vertices the rank of A(G) is

(a) n (b) n/2

(c) 2 (d) n-1

152.The number of different rooted labeled trees with n vertices is

(a) 2^n-1 (b) 2^n

(c) n^n-1 (d) n^n

153.Let A={1,2,3,4,5} Which of the following sets equal A?

(a) {4,1,2,3,5} (b) {5,1,3,2,1}

(c) {3,2,4,1} (d) {3,4,5}

154. Which of the following sets are empty?

(a) {x/x is a real number and x^2-1=0} (b) {x/x is a real number and x^2+1=0}

(c) {x/x is a real number and x=2x+1} (d) {x/x is a real number and x^2=-9}

155. Let a={1,2,5,8,11}. Which of the following is false?

(a) {5,1}is subset of or equal to A (b) {8,1} belongs to A

(c) ø is subset of or equal to A (d) {2} is subset of or equal to A

156. Suppose we have implemented the queue with a linked list keeping track of a front element with frontptr pointer and a rear element with rearptr pointer. Which of these pointer will change with an enqueue operation on a nonempty queue?

(a) neither changes

(b) only frontptr changes

(c) only rearptr changes

(d) both changes

157:- Suppose we have implemented the queue with a linked list, keeping track of a front element with frontptr pointer and a rear element with rearptr pointer. Which of these pointer will change with a enqueue operation on an empty queue?

(a) neither changes

(b) only frontptr changes

(c) only rearptr changes

(d) both change

158:- Suppose we have implemented the queue with a linked list, keeping tarck of a front element with frontptr pointer and a rear element with rearptr pointer. Which of these pointers will changes with a dequeue operation on a queue having two or more elements?

(a) neither changes

(b) only frontptr changes

(c) only rearptr changes

(d) both changes

159:- Suppose we have implemented the queue with a linked list. keeping tarck of front element with frontptr pointer and a rear element with rearptr pointer. Which of these pointer will change with a dequeue operation on a queue having only one element?

(a) neither changes

(b) only frontptr changes

(c) only rearptr changes

(d) both changes

160:- Suppose a priority queue has two elements with same priority. How is the return value of dequeue operation selected?

(a) The implementation needs to choose either one.

(b) The one which was inserted first

(c) The one which was inserted most recently

(d) This can never happen, i.e. its violates the precondition

161:- Which of the following data structure is required to convert an arithmetic expression in infix to its equivalent postfix notation?

(a) linked list

(b) binary search tree

(c) queue

(d) none of above

162:- Which of the following statement is not true about a binary search tree?

(a) It is a two way search tree.

(b) At eachj node, the elements of the left sub tree are less than the node valve and the element in the right subtree are greater than the node value.

(c) It can be efficiently represented using an array.

(d) It provides the best of both arrays and linked list

163:- Which of the following tree maintains a list of the keys in sequential order?

(a) m-way search tree

(b) B-tree

(c) B*-tree

(d) B+-tree

164:- An array is declared as

int a[3][4] { {1,2}, {4,5,6} };

What is the value of a[1][2]?

(a) 5

(b) 6

(c) 2

(d) Garbage

165:- Which of the following statement is true about strings in C?

(a) String is a primitive data type in C

(b) Every string must be terminated by a newline character('\n')

(c) A string value can be assigned to a string variable using assignment operator '='

(d) Strings are represented in C using array of type char.

166:- If a number 125.456 is written to a file that is opened in text mode, how many bytes it will need for its storage?

(a) 4 bytes

(b) 7 bytes

(c) 8 bytes

(d) 5 bytes

167:- Which of the following file organization allow an application to access the records directly as well as sequentially?

(a) Relative file organization

(b) sequential file organization

(c) indexed sequential file organization

(d) none of above

168:- Changes that are going to be applied to a master file, in a batch-oriented application, are collected in a file?

(a) work file

(b) report file

(c) activity file

(d) transaction file

169:- Which of the following file organizations is not suitable for an interactive application?

(a) ralative file organization

(b) sequential file organization

(c) indexed sequential file organization

(d) inverted file organization

170:- If an undirected graph with n vertices and e edges is represented using an adjacency list, what will the total number of nodes in the adjacency lists?

(a) n

(b) e

(c) 2e

(d) 2n

171:- Suppose we have a linear array implementation of the queue, with 18 items in the queue atored at data[12] through data[29]. The CAPACITY of the queue is 30. Where does the enqueue operation place the new entry in the array, when the queue is readjusted if it is not full?

(a) data[30]

(b) data[18]

(c) data[0]

(d) data[17]

172:- An index is a pair of elements comprising key and a file pointer or record number. A file in which indices are stored is known as _________

(a) sort file

(b) key file

(c) index file

(d) none of above

173:- A file is only read by a program is known as_____________________

(a) temporary file

(b) work file

(c) I/o file

(d) input file

174:- Which of following operation are generally not performed on report files?

(a) Updation

(b) Maintenance

(C) Retreval

(d) All the above

175:- Which of following is not a type of a I/O channel?

(a) selector

(b) multiplexer

(c) demoltiplexer

(d) block multiplexer

176:- Name the tree in which, for every node, the height of left subtree

and height of right subtree can difer by at most one

(a) Complete tree

(b) AVL tree

(c) Threaded tree

(d) B-tree

177:- A graph in which all vertices have equal degree is known as______

(a) complete graph

(b) simple graph

(c) multiple graph

(d) regular graph

178:- A binary tree in all its levels except the last, have maximum members of nodes, and all nodes in the last level having only one child it will be its left child name the tree.

(a) Full binary tree

(b) M-way search tree

(c) Complete binary tree

(d) Threaded tree

179:- A linear list in which elements ca be added or removed at either end is known as

(a) Deque

(b) Queue

(c) priorty queue

(d) Circular queue

180:- Items A,B,C,D and E are pushed onto a stack, in order. Then the stack is popped four times and each popped element is added to a FIFO queue, then two elements are removed from the queue and pushed onto a stack again in order. Finally,one element is popped from the stack. The popped element is..........

(a) B

(b) D

(c) A

(d) E

181:- Which of the following sorting algo is the slowest?

(a) Quick sort

(b) Shel sort

(c) Heap sort

(d) Bubble sort

182. Items A,B,C,D and E are added to an empty FIFO queue ,in order. The three elements are removed frpm the queue and pushed to an empty stack, in order.then two elements are popped from the stack and added to the queue, Finally, one elements is removed from the Queue. The removed element is

(a) B

(b) A

(c) D

(d) E

183:- Items A,B,C,D and E are pushed onto first stack, in order. Then the elements of stack are popped one by one and pushed onto second stack. Then the process is reversed, that is elements of second stack are popped one by one and pushed onto first stack. Which item will be on top of the first stack?

(a) E

(b) C

(c) A

(d) B

184:- If two trees have same structure and node content, then they are called __________

(a) similar trees

(b) equivalent trees

(c) joint trees

(d) synonyms trees

185:- Minimum number of fields in each node of a doubly linked list is ___________

(a) 2

(b) 3

(c) 4

(d) none of above

186:- Consider the following graph

Which of the following represents its correct topological sort?

(a) 2 1 3 4

(b) 1 2 3 4

(c) 1 3 4 2

(d) 1 3 4 2

187:- If two trees have same structure and but different node content, then they are called __________

(a) similar trees

(b) equivalent trees

(c) joint trees

(d) synonyms trees

188:- Consider the directed graph

Suppose the graph is represented using the following adjacency list

1-->2-->3

2-->4

3-->2-->4

4

Which of the following represents its correct breadth first search(BFS) with vertex 1 as the starting vertex?

(a) 2 1 3 4

(b) 1 2 3 4

(c) 1 3 2 4

(d) 1 3 4 2

189:- Consider the directed graph

Suppose the graph is represented using the following adjacency list

1-->2-->3

2-->4

3-->2-->4

4

Which of the following represents its correct depth first search (DFS) with vertex 1 as the starting vertex?

(a) 4 1 3 1

(b) 1 2 3 4

(c) 4 2 1 3

(d) 4 2 3 1

190:- Which of the following data structure can be used to represent many-to-many relation?

(a) binary tree

(b) graph

(c) B-tree

(d) all of above

191:- Given an arithmetic expression in infix notation as "(A+B)*C/D". What be its equivalent in postfix notation?

(a) AB+CD*/

(b) AB+C*/D

(c) AB+*CD/

(d) AB+C*D/

192:-Given following traversal of a tree T:

In-order : C F A K L D

Pre-order A C F D K L

The tree is

(a) (b) (c) (d)

193:- Given an arithmetic expression in infix notation as "(a+b)*c/d". what be its equivalent in prefix notation?

(a) +AB*/CD

(b) /*A+BCD

(c) /*+ABCD

(d) /+*ABCD

194:- The expresion "75 - 92/ * " in postfix notation evaluates to

(a) 10

(b) 9.5

(c) 9

(d) 11

195:- Given an arithmetic expression in postfix notation as "PQ+R*S/". What be its equivalent expression in infix notation?

(a) (P+Q)*R/S

(b) P+Q*R/S

(c) (P+Q)/R*S

(d) (P+Q*R)/S

196:-

which of the following data structure is more appropriate for

implementing quick sort iteratively?

(a) stack

(b) Queue

(c) priorty oueue

(d) deque

197:- Which of the following data structure is more appropriate

to represent a heap?

(a) Linked list

(b) Linear Array

(c) Doubly linked list

(d) Two-dimensional array

198:- The desired complexity of the pop operation on a stack, irrespective of whether it is implemented using an array or a linked list, must be......

(a)O(i)

(b)O(n)

(c)O(logn)

(d)O(nlogn)

199:- Which of the following operation is not supported by a queue?

(a) Inserting element at rear

(b) Removing element from front

(c) Removing element from middle

(d) None of above

200:- Which of the following statement is not true about linked lists?

(a) Elements are not necessarily stored in contigous location.

(b) Inserteion and deletions can be performed efficiently as

compared to arrays.

(c) Element in a linked list,if it is stored,can be quickely

searched by applying binary search technique.

(d) Linked list is a dynamic structure.

201. An enqueue operation adds an element

(a) to the rear of the queue

(b) to the front of the queue

(c) at any position in the queue

(d) none of above

202. Which of the following sequence of operations does not result in a queue containing: 2,3,5,7?

(a) enqueue(1), enqueue(2), enqueue(3), enqueue(5), enqueue(7), dequeue()

(b) enqueue(2), enqueue(3), enqueue(5), enqueue(7)

(c) enqueue(1), dequeue(), enqueue(2), enqueue(3), enqueue(5), enqueue(7)

(d) enqueue(2), enqueue(3), enqueue(4), dequeue(), enqueue(5), enqueue(7)

203. One difference between a queue and a stack is that

(a) Queues have a first-in-last-out algorithm; stacks have a first-in-first-out

(b) Stacks require implementation as a dynamic linked list; queues do not

(c) Queues require using two ends of the structure; stack use only one

(d) Stacks require using two ends of the structure; queues use only one

204. To implement a queue as a circular array of CAPACITY elements, we need to keep rear as an index to the tail of the queue, and front as an index to the head. What is the formula to calculate the position where an element should be pushed?

(a) front + 1

(b) (rear % CAPACITY) + 1

(c) (rear + 1) % CAPACITY

(d) (front + 1) % CAPACITY

205. Which of the following statements about a binary tree is not true?

(a) It allows traversals that are inorder, preorder, and postorder

(b) Each node has both a pointer to the left and a pointer to the right

(c) None of above

206. What is the maximum number of nodes at level l, when root is given level 0?

(a) 2l

(b) 2(l-1)

(c) 2l-1

(d) none of above

207. What is the maximum number of nodes in a binary tree of height h?

(a) 2h

(b) 2h+1

(c) 2h-1

(d) 2(h-1)

208. To perform level-order traversal on a binary tree, which of the following data structure will be required?

(a) Stack

(b) Binary search tree

(c) Queue

(d) Hash table

Question 209-213 pertains to the following binary tree.

Question#209

How many leaves does it have?

(a) 2

(b) 4

(c) 6

(d) 8

Question#210

How many of the nodes have at least one sibling?

(a) 5

(b) 6

(c) 7

(d) 8

Question#211

How many descendants does the root have?

(a) 2

(b) 6

(c) 7

(d) 8

Question#212

What is the depth of the tree?

(a) 2

(b) 4

(c) 5

(d) 3

Question#213

Which of the following statement is correct?

(a) The tree is neither complete not full

(b) The tree is complete but not full

(c) The tree is full but not complete

(d) The tree is both full and complete

Question#214

What is the number of nodes in a full binary tree with depth 3?

(a) 5

(b) 6

(c) 7

(d) 8

Question#215

What is the minimum number of nodes in a complete binary tree with depth 3?

(a) 4

(b) 5

(c) 7

(d) 6

Question#216

Which of the following statements about a binary tree is correct?

(a) Every binary tree is either complete or full

(b) Every complete binary tree is also a full binary tree

(c) Every full binary tree is also a complete binary tree

(d) No binary tree is both complete and full

Question#217

Suppose T is a binary tree with 14 nodes. What is the minimum possible height of T?

(a) 4

(b) 5

(c) 3

(d) 6

Question#218

Suppose T is a binary tree with 14 nodes. What is the maximum possible height of T?

(a) 4

(b) 14

(c) 10

(d) 9

Question#219

Which of the following statements about a binary tree is not correct?

(a) Every binary tree has at least one node

(b) Every non-empty tree has exactly one root node

(c) Every node has at most two children

(d) Every non-root node has exactly one parent

Question#220

Consider the node of a complete binary tree whose value is stored in tree[i] for an array implementation. If this node has a right child, where will the right child’s value be stored?

(a) tree[i+1]

(b) tree[2*i]

(c) tree[2*i+1]

(d) tree[2*i+2]

Question#221

Tree algorithms typically run in time O(d). What is d?

(a) The height of the tree

(b) The number of nodes at level d

(c) The number of nodes in the tree

(d) The number of leaf nodes

Question 222-225 pertains to the following tree.

Question#222

What is the order of nodes visited using a pre-order traversal?

(a) 1 2 3 14 7 10 11 40 30

(b) 14 2 1 3 11 10 7 30 40

(c) 1 3 2 7 10 40 30 11 14

(d) 14 2 11 1 3 10 30 7 40

Question#223

What is the order of nodes visited using an in-order traversal?

(a) 1 2 3 14 7 10 11 40 30

(b) 14 2 1 3 11 10 7 30 40

(c) 1 3 2 7 10 40 30 11 14

(d) 14 2 11 1 3 10 30 7 40

Question#224

What is the order of nodes visited using a post-order traversal?

(a) 1 2 3 14 7 10 11 40 30

(b) 14 2 1 3 11 10 7 30 40

(c) 1 3 2 7 10 40 30 11 14

(d) 14 2 11 1 3 10 30 7 40

Question#225

What is the order of nodes visited using a level-order traversal?

(a) 1 2 3 14 7 10 11 40 30

(b) 14 2 1 3 11 10 7 30 40

(c) 1 3 2 7 10 40 30 11 14

(d) 14 2 11 1 3 10 30 7 40

Question#226

Consider the following binary search tree

Suppose we remove the root, replacing it with something from the left subtree. What will be the new root?

(a) 12

(b) 16

(c) 9

(d) 13

Question#227

Consider the following binary search tree

Suppose we remove the root, replacing it with something from the right subtree. What will be the new root?

(a) 25

(b) 27

(c) 45

(d) 39

Question#228

What feature of heaps allows them to be efficiently implemented using a partially filled array?

(a) Heaps are binary search trees

(b) Heaps are complete binary trees

(c) Heaps are full binary trees

(d) Heaps contain only integer data

Question#229

If a max heap is implemented using a partially filled array named data[1..CAPACITY-1], and the array contains n elements (n>0), where is the entry with the greatest value?

(a) data[1]

(b) data[n-1]

(c) data[2*n+1]

(d) data[2*n+2]

Question#230

Select the true statement about the worst-case time for operation on heaps.

(a) Neither insertion nor removal is better than linear

(b) Insertion is better than linear, but removal is not

(c) Removal is better than linear, but insertion is not

(d) Both insertion and removal are better than linear

Question#231

Suppose that we have implemented a priority queue by storing the items in a max heap, where max heap is represented using a partially filled array named data[1..CAPACITY-1]. We are now executing an reheapify upward operation and the out-of-place node is at data[i] with priority given by data[i]. Which of the following Boolean expressions is TRUE to indicate that the reheapify upward IS NOT YET DONE?

(a) i > 1

(b) data[i/2] < data[i]

(c) i > 1 && data[i/2]

(d) i > 1

data[i/2] < data[i]

Question#232

Suppose that we have implemented a priority queue by storing the items in a max heap, where max heap is represented using a partially filled array named data[1..CAPACITY-1]. We are now executing an reheapify downward operaton and the out-of-place node is at data[i] with priority given by data[i]. Which of the following boolean expression is TRUE to indicate that the reheapify downward IS NOT YET DONE?

(a) i < CAPACITY-1

(b) data[i] < max(data[2i], data[2i+1])

(c) i < CAPACITY-1

data[i] < max(data[2i], data[2i+1)

(d) i < CAPACITY-1 && data[i] < max(data[2i], data[2i+1])

Question#233

Suppose that we have implemented a priority queue by storing the items in a max heap, where max heap is represented using a partially filled array named data[1..CAPACITY-1]. We are now executing a reheapify upward operation and the out-of-place node has priority of 42. The node’s parent has a priority of 72, the left child has priority 52 and the right child has priority 62. Which statement best describes the status of the reheapify upward operation?

(a) The reheapify upward is done

(b) It will interchange the two children of the out-of-place node

(c) It will swap the out-of-place node with its parent

(d) It will swap the out-of-place node with its right child

Question#234

Which of the following formula gives best approximation for the height of a heap with n nodes?

(a) log2n

(b) log10n

(c) n

(d) n(1/2)

Question#235

A graph is a tree if and only if graph is

(a) completely connected

(b) planar

(c) contains no cycles

(d) directed graph

236. In the linked list implementation of the queue class, where does the insert method place the new entry on the linked list?

A. At the head

B. At the tail

C. After all other entries that are greater than the new entry.

D. After all other entries that are smaller than the new entry.

237. In the circular array version of the Queue class, which operations require linear time for their worst-case behavior?

A. getFront

B. insert when the capacity has not yet been reached

C. isEmpty

D. None of these operations require linear time.

238. In the linked-list version of the Queue class, which operations require linear time for their worst-case behavior?

A. getFront

B. insert

C. isEmpty

D. None of these operations require linear time.

239. If data is a circular array of CAPACITY elements, and rear is an index into that array, what is the formula for the index after rear?

A. (rear % 1) + CAPACITY

B. rear % (1 + CAPACITY)

C. (rear + 1) % CAPACITY

D. rear + (1 % CAPACITY)

240. I have implemented the queue with a circular array, keeping track of front, rear, and manyItems (the number of items in the array). Suppose front is zero, and rear is one less than the current capacity. What can you tell me about manyItems?

A. manyItems must be zero.

B. manyItems must be equal to the current capacity.

C. count could be zero or the capacity, but no other values could occur.

D. None of the above.

241. I have implemented the queue with a linked list, keeping track of a front node and a rear node with two reference variables. Which of these reference variables will change during an insertion into a NONEMPTY queue?

A. Neither changes

B. Only front changes.

C. Only rear changes.

D. Both change.

242. I have implemented the queue with a linked list, keeping track of a front node and a rear node with two reference variables. Which of these reference variables will change during an insertion into an EMPTY queue?

A. Neither changes

B. Only front changes.

C. Only rear changes.

D. Both change.

243. Suppose getFront is called on a priority queue that has exactly two entries with equal priority. How is the return value of getFront selected?

A. One is chosen at random.

B. The one which was inserted first.

C. The one which was inserted most recently.

D. This can never happen (violates the precondition)

244. An array of queues can be used to implement a priority queue, with each possible priority corresponding to its own element in the array. When is this implementation not feasible?

A. When the number of possible priorities is huge.

B. When the number of possible priorities is small.

C. When the queues are implemented using a linked list.

D. When the queues are implemented with circular arrays.

245. There is a tree in the box at the top of this section. How many leaves does it have?

A. 2

B. 4

C. 6

D. 8

E. 9

246. There is a tree in the box at the top of this section. How many of the nodes have at least one sibling?

A. 5

B. 6

C. 7

D. 8

E. 9

247. There is a tree in the box at the top of this section. What is the value stored in the parent node of the node containing 30?

A. 10

B. 11

C. 14

D. 40

E. None of the above

248. There is a tree in the box at the top of this section. How many descendants does the root have?

A. 0

B. 2

C. 4

D. 8

249. There is a tree in the box at the top of this section. What is the depth of the tree?

A. 2

B. 3

C. 4

D. 8

E. 9

250. There is a tree in the box at the top of this section. How many children does the root have?

A. 2

B. 4

C. 6

D. 8

E. 9

251. Consider the binary tree in the box at the top of this section. Which statement is correct?

A. The tree is neither complete nor full.

B. The tree is complete but not full.

C. The tree is full but not complete.

D. The tree is both full and complete.

252. What is the minimum number of nodes in a full binary tree with depth 3?

A. 3

B. 4

C. 8

D. 11

E. 15

253. What is the minimum number of nodes in a complete binary tree with depth 3?

A. 3

B. 4

C. 8

D. 11

E. 15

254. Select the one true statement.

A. Every binary tree is either complete or full.

B. Every complete binary tree is also a full binary tree.

C. Every full binary tree is also a complete binary tree.

D. No binary tree is both complete and full.

255. Suppose T is a binary tree with 14 nodes. What is the minimum possible depth of T?

A. 0

B. 3

C. 4

D. 5

256. Select the one FALSE statement about binary trees:

A. Every binary tree has at least one node.

B. Every non-empty tree has exactly one root node.

C. Every node has at most two children.

D. Every non-root node has exactly one parent.

257. Suppose t is a BTNode variable from Chapter 9, which expression indicates that t represents an empty tree?

A. (t == null)

B. (t->data == 0)

C. (t->data == null)

D. ((t->left == null) && (t->right == null))

258. Consider the node of a complete binary tree whose value is stored in data[i] for an array implementation. If this node has a right child, where will the right child's value be stored?

A. data[i+1]

B. data[i+2]

C. data[2*i + 1]

D. data[2*i + 2]

259. Suppose that a binary taxonomy tree includes 8 animals. What is the minimum number of NONLEAF nodes in the tree?

A. 1

B. 3

C. 5

D. 7

E. 8

14

/ \

2 11

/ \ / \

1 3 10 30

/ /

7 40

260. There is a tree in the box at the top of this section. What is the order of nodes visited using a pre-order traversal?

A. 1 2 3 7 10 11 14 30 40

B. 1 2 3 14 7 10 11 40 30

C. 1 3 2 7 10 40 30 11 14

D. 14 2 1 3 11 10 7 30 40

261. There is a tree in the box at the top of this section. What is the order of nodes visited using an in-order traversal?

A. 1 2 3 7 10 11 14 30 40

B. 1 2 3 14 7 10 11 40 30

C. 1 3 2 7 10 40 30 11 14

D. 14 2 1 3 11 10 7 30 40

262. There is a tree in the box at the top of this section. What is the order of nodes visited using a post-order traversal?

A. 1 2 3 7 10 11 14 30 40

B. 1 2 3 14 7 10 11 40 30

C. 1 3 2 7 10 40 30 11 14

D. 14 2 1 3 11 10 7 30 40

263. Consider this binary search tree:

14

/ \

2 16

/ \

1 5

/

4

Suppose we remove the root, replacing it with something from the left subtree. What will be the new root?

A. 1

B. 2

C. 4

D. 5

E. 16

264. What is the worst-case time for serial search finding a single item in an array?

A. Constant time

B. Logarithmic time

C. Linear time

D. Quadratic time

265. What is the worst-case time for binary search finding a single item in an array?

A. Constant time

B. Logarithmic time

C. Linear time

D. Quadratic time

266. What additional requirement is placed on an array, so that binary search may be used to locate an entry?

A. The array elements must form a heap.

B. The array must have at least 2 entries.

C. The array must be sorted.

D. The array's size must be a power of two.

267. 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.

268. Which guideline is NOT suggested from from empirical or theoretical studies of hash tables:

A. Hash table size should be the product of two primes.

B. Hash table size should be the upper of a pair of twin primes.

C. Hash table size should have the form 4K+3 for some K.

D. Hash table size should not be too near a power of two.

269. In an open-address hash table there is a difference between those spots which have never been used and those spots which have previously been used but no longer contain an item. Which method has a better implementation because of this difference?

A. put

B. containsKey

C. remove

D. size

E. Two or more of the above methods

270. What kind of initialization needs to be done for an open-address hash table?

A. None.

B. The key at each array location must be initialized.

C. The head pointer of each chain must be set to null.

D. Both B and C must be carried out.

271. What kind of initialization needs to be done for a chained hash table?

A. None.

B. The key at each array location must be initialized.

C. The head pointer of each chain must be set to null.

D. Both B and C must be carried out.

272. A chained hash table has an array size of 512. What is the maximum number of entries that can be placed in the table?

A. 256

B. 511

C. 512

D. 1024

E. There is no maximum.

273. Suppose you place m items in a hash table with an array size of s. What is the correct formula for the load factor?

A. s + m

B. s - m

C. m - s

D. m * s

E. m / s

274. In a selection sort 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²

275. Selection sort and quick sort 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.

276. Suppose that a selection sort of 100 items has completed 42 iterations of the main loop. How many items are now guaranteed to be in their final spot (never to be moved again)?

A. 21

B. 41

C. 42

D. 43

277. Suppose we are sorting an array of ten integers using some quadratic sorting algorithm. After four iterations of the algorithm's main loop, the array elements are ordered as shown here:

1 2 3 4 5 0 6 7 8 9

Which statement is correct? (Note: Our selection sort picks largest items first.)

A. The algorithm might be either selection sort or insertion sort.

B. The algorithm might be selection sort, but could not be insertion sort.

C. The algorithm might be insertion sort, but could not be selection sort.

D. The algorithm is neither selection sort nor insertion sort.

278. Suppose we are sorting an array of eight integers using a some quadratic sorting algorithm. After four iterations of the algorithm's main loop, the array elements are ordered as shown here:

2 4 5 7 8 1 3 6

Which statement is correct? (Note: Our selection sort picks largest items first.)

A. The algorithm might be either selection sort or insertion sort.

B. The algorithm might be selection sort, but it is not insertion sort.

C. The algorithm is not selection sort, but it might be insertion sort.

D. The algorithm is neither selection sort nor insertion sort.

279. When is insertion sort a good choice for sorting an array?

A. Each component of the array requires a large amount of memory.

B. Each component of the array requires a small amount of memory.

C. The array has only a few items out of place.

D. The processor speed is fast.

280. What is the worst-case time for mergesort to sort an array of n elements?

A. O(log n)

B. O(n)

C. O(n log n)

D. O(n²)

281. What is the worst-case time for quicksort to sort an array of n elements?

A. O(log n)

B. O(n)

C. O(n log n)

D. O(n²)

282. 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 amongst 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. None of the above.

283. Suppose we are sorting an array of eight integers using quicksort, and we have just finished the first partitioning with the array looking like this:

2 5 1 7 9 12 11 10

Which statement is correct?

A. The pivot could be either the 7 or the 9.

B. The pivot could be the 7, but it is not the 9.

C. The pivot is not the 7, but it could be the 9.

D. Neither the 7 nor the 9 is the pivot.

284. What is the worst-case time for heapsort to sort an array of n elements?

A. O(log n)

B. O(n)

C. O(n log n)

D. O(n²)

285. Suppose we are sorting an array of eight integers using heap sort, and we have just finished one of the reheapifications downward. The array now looks like this:

6 4 5 1 2 7 8

How many reheapifications downward have been performed so far?

A. 1

B. 2

C. 3 or 4

D. 5 or 6

286. In a real computer, what will happen if you make a recursive call without making the problem smaller?

A. The operating system detects the infinite recursion because of the "repeated state"

B. The program keeps running until you press Ctrl-C

C. The results are nondeterministic

D. The run-time stack overflows, halting the program

287. When the compiler compiles your program, how is a recursive call treated differently than a non-recursive method call?

A. Primitive values are all treated as reference variables

B. Reference variables are all treated as primitive values

C. There is no duplication of local variables

D. None of the above

288. When a method call is executed, which information is not saved in the activation record?

A. Current depth of recursion.

B. Formal parameters.

C. Location where the method should return when done.

D. Local variables.

289. Consider the following statements:

int *p;

int i;

int k;

i = 42;

k = i;

p = &i;

After these statements, which of the following statements will change the value of i to 75?

A. k = 75;

B. *k = 75;

C. p = 75;

D. *p = 75;

E. Two or more of the answers will change i to 75.

290. Consider the following statements:

int i = 42;

int j = 80;

int *p1;

int *p2;

p1 = &i;

p2 = &j;

*p1 = *p2;

cout << i << j << endl;

What numbers are printed by the output statement?

A. 42 and then another 42

B. 42 and then 80

C. 80 and then 42

D. 80 and then another 80

291. What is printed by these statements?

int i = 1;

int k = 2;

int *p1;

int *p2;

p1 = &i;

p2 = &k;

p1 = p2;

*p1 = 3;

*p2 = 4;

cout << i;

A. 1

B. 2

C. 3

D. 4

292. What is printed by these statements?

int i = 1;

int k = 2;

int* p1;

int* p2;

p1 = &i;

p2 = &k;

p1 = p2;

*p1 = 3;

*p2 = 4;

cout << k;

A. 1

B. 2

C. 3

D. 4

293.What is printed by these statements?

int i = 1;

int k = 2;

int* p1;

int* p2;

p1 = &i;

p2 = &k;

*p1 = *p2;

*p1 = 3;

*p2 = 4;

cout << i;

A. 1

B. 2

C. 3

D. 4

294.When allocating an array of objects, what constructor is used to initialize all of the objects in the array?

A. The automatic copy constructor.

B. The constructor specified at the declaration.

C. The default constructor.

D. None of the above.

295.In which location do dynamic variables reside?

A. The code segment.

B. The data segment.

C. The heap.

D. The run-time stack.

296. When should a pointer parameter p be a reference parameter?

A. When the function changes p, and you want the change to affect the actual pointer argument.

B. When the function changes p, and you do NOT want the change to affect the actual pointer argument.

C. When the function changes *p, and you want the change to affect the the object that is pointed at.

D. When the function changes *p, and you do NOT want the change to affect the the object that is pointed at.

E. When the pointer points to a large object.

297.Suppose you have the following function prototype and variable declaration:

void goop(int z[ ]);

int x[10];

Which is the correct way to call the goop function with x as the argument:

A. goop(x);

B. goop(x[ ]);

C. goop(x[10]);

D. goop(&x);

E. goop(&x[ ]);

298.Suppose that the goop function from the previous question changes the value of z[1]. Does this change effect the value of the actual argument?

A. Yes

B. No

299.Here is a function declaration:

void goo(int* x)

{

*x = 1;

}

Suppose that a is an int* variable pointing to some integer, and *a is equal to zero. What is printed if you print *a after the function call goo(a)?

A. 0

B. 1

C. address of a

D. address of x

E. None of the above

300.Suppose you are implementing an assignment operator, a copy constructor, and an operator +=. For which of these functions do you need to worry about possible "self-application" (where the argument is the same as the object that activates the function):

A. Only one of the three functions has possible self-application

B. The assignment operator and the copy construtor have possible self-application

C. The assignment operator and the operator += have possible self-application

D. The copy construtor and the operator += have possible self-application

E. All three functions have possible self-application

301.What is the usual worst-case performance for resizing a container class that stores its data in a dynamic array?

A. Constant time

B. Logarithmic time

C. Linear time

D. Quadratic time

302.When a class uses dynamic memory, what member functions should be provided by the class?

A. The assignment operator.

B. The copy constructor.

C. A destructor.

D. All of the above.

303.Which situation does not use the copy constructor?

A. Calling a function with a reference parameter

B. Calling a function with a value parameter

C. Declaring a variable to be a copy of another existing object

D. Returning a value from a function

E. All of the above situations use the copy constructor

304. Suppose that you want to declare an array of characters to hold a C++ string with exactly 9 letters. Which declaration is best?

A. char s[8];

B. char s[9];

C. char s[10];

D. char s[11];

E. char s[12];

305.Suppose that x and y are two C++ strings. Which expression will return true whenever x and y contain the same sequence of characters?

A. (x = y)

B. (x == y)

C. (x != y)

D. (strcmp(x, y))

306.Suppose that you want to develop two different + operators that calculate and return an object of some class. Which statement is correct?

A. One operator must be a friend and the other must not.

B. One operator must be public and the other private.

C. The operators must have a different parameter lists.

D. It is not possible to have two different + operators

307. Linked lists are collections of data items "lined up in a row"—insertions and deletions can be made only at the front and the back of a linked list.

True

False

308. Binary trees facilitate high-speed searching and sorting of data, efficient elimination of duplicate data items, compilation of expressions into machine language and many other interesting applications.

True

False

309. Self-referential objects can be linked together to form useful data structures such as lists, queues, stacks and trees.

True

False

310. A null pointer normally indicates the end of a data structure.

True

False

311. The limit for dynamic memory allocation can be as large as the amount of available physical memory in the computer or the amount of available disk space in a virtual-memory system

True

False

312. The size of lists, stacks, queues and trees must be determined in advance of using these data structures to ensure that the proper amount of memory is allocated for their elements.

True

False

313. Stacks and queues are linear data structures and are constrained versions of linked lists.

True

False

314. Conventional Java arrays can change size dynamically to accommodate new elements.

True

False

315. An array can be declared to contain more elements than the number of items expected, but this can waste memory. Linked lists can provide better memory utilization in these situations. Linked lists allow the program to adapt at run time.

True

False

316. The elements of a linked list are stored contiguously in memory. This allows immediate access to any linked list element because the address of any element can be calculated directly based on its offset from the beginning of the linked list.

True

False

317. The primary methods used to manipulate a stack are put and get. Method put adds a new node to the top of the stack. Method get removes a node from the top of the stack and returns the data object from the popped node.

True

False

318. Compilers use stacks to evaluate arithmetic expressions and generate machine language code to process the expressions. [

True

False

319. Composition enables us to hide the methods of class List that should not be in the interface to a stack by providing public interface methods only to the required List methods. This technique of implementing each stack method as a call to a List method is called offloading—the stack method invoked delegates the call to the appropriate List method.

True

False

320. Information packets wait in queues in computer networks. Each time a packet arrives at a network node, it must be routed to the next node on the network along the path to the packet's final destination. The routing node routes one packet at a time, so additional packets are enqueued until the router can route them.

True

False

321. A queue can be implemented by extending a stack class. ] True

False

322. Computer scientists normally draw trees from the root node down—exactly the opposite of the way most trees grow in nature.

True

False

323. The steps for an inorder traversal are:

1. Traverse the left subtree.

2. Process the value in the node.

3. Traverse the right subtree.

True

False

324. The steps for a postorder traversal are:

1. Process the value in the node.

2. Traverse the left subtree.

3. Traverse the right subtree.

True

False

True or False Quiz

325.

Which of the following abstract data types are NOT used by Integer Abstract Data type group?

Short

Int

float

long

326.

The byte abstract data type is the smallest abstract data type in the integer group and is declared by using the keyword byte

True

False

327.

Signed numbers do not have any impact on the memory

True

False

UGC NET SOLVED PAPER

UGC NET STUDY MATERIALS

COMPUTER NETWORK

SOFTWARE ENGINEERING QUIZ QUESTIONS???

DATA STRUCTURE

Popular Posts

Categories

Recent Posts

sponser

ugc net exam

Blog Archive