Fundamental Of Automata

1. The following grammar
G = (N, T, P, S)
N = {S, A, B}
T = {a, b, c}
P : S → aSa
S → aAa
A → bB
B → bB
B → c is

a. is type 3
b. is type 2 but not type 3
c. is type 1 but not type 2
d. is type 0 but not type 1


2. The following grammar
G = (N, T, P, S)
N = {S, A, B, C, D, E}
T = {a, b, c}
P : S → aAB
  AB → CD
  CD → CE
  C → aC
  C → b
  bE → bc is

a. is type 3
b. is type 2 but not type 3
c. is type 1 but not type 2
d. is type 0 but not type 1

3. The following grammar
G = (N, T, P, S)
N = {S, A, B, C}
T = {a, b, c}
P : S → aS
A → bB
B → cC
C → a is

a. is type 3
b. is type 2 but not type 3
c. is type 1 but not type 2
d. is type 0 but not type 1

4. The following grammar
G = (N, T, P, S)
N = {S, A, B, C, D, E}
T = (a, b, c}
P : S → ABCD
  BCD → DE
  D → aD
  D → a
  E → bE
  E → c is

a. is type 3
b. is type 2 but not type 3
c. is type 1 but not type 2
d. is type 0 but not type 1

5. Consider the following CFG
S → aB S → bA
B → b A → a
B → bS A → aS
B → aBB A → bAA

Consider the following derivation
S ⇒ aB
  ⇒ aaBB
  ⇒ aaBb
  ⇒ aabSb
  ⇒ aabbAb
  ⇒ aabbab

This derivation is

a. a leftmost derivation
b. a rightmost derivation
c. both leftmost and rightmost derivation
d. neither leftmost nor rightmost derivation

6. Consider the following language
L = {anbncndn|n ≥ 1}
L is

a. CFL but not regular
b. CSL but not CFL
c. regular
d. type 0 language but not type 1

7. Consider the following language
L = {anbn|n ≥ 1}
L is

a. CFL but not regular
b. CSL but not CFL
c. regular
d. type 0 language but not type 1

8. Consider the following language
L = {anbmcpdq|n, m, p, q ≥ 1}
L is
a. CFL but not regular
b. CSL but not CFL
c. regular
d. type 0 language but not type 1

9. The following CFG is in
S → AB
B → CD
B → AD
B → b
D → AD
D → d
A → a
C → a
a. Chomsky normal form but not strong Chomsky normal form
b. Weak Chomsky normal form but not Chomsky normal form
c. Strong Chomsky normal form
d. Greibach normal form

10. The following CFG is in
S → aBB
B → bAA
A → a
B → b
a. Chomsky normal form but not strong Chomsky normal form
b. Weak Chomsky normal form but not Chomsky normal form
c. Strong Chomsky normal form
d. Greibach normal form

11. Which of the following CF language is inherently ambiguous?
a. {anbncmdm|n, m ≥ 1}
b. {anbmcpdq|n = p or m = q, n, m, p, q ≥ 1}
c. {anbmcpdq|n ≠ m ∧ p ≠ q}
d. {anbmcpdq|n ≠ m ∨ p ≠ q}

12. Which string is not accepted by the following FSA?
a. 00111
b. 01010
c. 00110
d. 11010

13. Which string is accepted by the following FSA?
 a. 00111
b. 11011
c. 01101
d. 0101

14. Can a DFSA simulate a NFSA
a. No
b. Yes
c. sometimes
d. depends on NFA

15. Which of the following is true for an arbitrary language L.
a.
b. L* = L+ ∪ {λ}
c. L* = L+
d. L* = L+ − {λ}

16. The concept of FSA is much used in this part of the compiler
a. lexical analysis
b. parser
c. code generation
d. code optimization

17. The concept of grammar is much used in this part of the compiler
a. lexical analysis
b. parser
c. code generation
d. code optimization

18. (a + b)(cd)*(a + b) denotes the following set
a. {a(cd)nb|n ≥ 1}
b. {a(cd)na|n ≥ 1} ∪ {b(cd)nb/n ≥ 1}
c. {a(cd)na|n ≥ 0} ∪ {a(cd)nb/n ≥ 0} ∪ {b(cd)na/n ≥ 0} ∪ {b(cd)nb/n ≥ 0}
d. {acndnb|n ≥ 1}

19. baa*c denotes the set
a. {bnamcp|n, m, p ≥ 1}
b. {banc|n ≥ 0}
c. {banc|n ≥ 1}
d. {w|w is a string of a, b, c}

20. The set of all strings over the alphabet Σ = {a, b} (including ε) is denoted by
a. (a + b)*
b. (a + b)+
c. a+b+
d. a*b*

21. Palindromes can’t be recognized by any FSA because
a. FSA cannot remember arbitrarily large amount of information
b. FSA cannot deterministically fix the midpoint
c. Even if the mid point is known an FSA cannot find whether the second half of the string matches the first half
d. all of the above

22. Let Σ = {a, b, c, d, e}. The number of strings in Σ* of length 4 such that no symbol is used more than once in a string is
a. 360
b. 120
c. 35d. 36

23. Which of the following denotes Chomskian hiearchy?
a. REG ⊂ CFL ⊂ CSL ⊂ type0
b. CFL ⊂ REG ⊂ type0 ⊂ CSL
c. CSL ⊂ type0 ⊂ REG ⊂ CFL
d. CSL ⊂ CFL ⊂ REG ⊂ type0

24. A language L is accepted by a FSA iff it is
a. CFL
b. CSL
c. recursive
d. regular

25. Which of the following regular expressions denotes a language comprising of all possible strings over Σ = {a, b} of length n where n is a multiple of 3.
a. (a + b + aa + bb + aba + bba)*
b. (aaa + bbb)*
c. ((a + b)(a + b)(a + b))*
d. (aaa + ab + a) + (bbb + bb + a)

26. A language is represented by a regular expression (a)*(a + ba). Which of the following string does not belong to the regular set represented by the above expression.
a. aaa
b. aba
c. ababad. aa

27. Which of the following is not primitive recursive but partially recursive?
a. McCarthy’s function
b. Riemann function
c. Ackermann’s function
d. Bounded function

28. Consider the following right-linear grammar G = (N, T, P, S) N = {S}
P : S → aS|aA T = {a, b}
A → bA|b

Which of the following regular expression denotes L(G)?
a. (a + b)*
b. a(ab)*b
c. aa*bb*
d. a*b*

29. Which of the following strings is not generated by the following grammar? S→ SaSbS|ε
a. aabb
b. abab
c. aababb
d. aaabb

30. Consider the following NFSA
 The automaton accepts
a. all words of the form {(ab)na|n ≥ 1}
b. all words that end with a and ε
c. all words that end with a and not ε
d. all words containing substring ba

31. Consider a language L for which there exists a Turing machine (TM), T, that accepts every word in L and either rejects or loops for every word that is not in L. The language L is
a. NP hard
b. NP complete
c. recursive
d. recursively enumerable

32. Consider the following statements
I. Recursive languages are closed under complementation
II. Recursively enumerable languages are closed under union
III. Recursively enumerable languages are closed under complementation
Which of the above statement are TRUE?
a. I only
b. I and II
c. I and III
d. II and III

33. Which of the following statement is wrong?
a. Any regular language can be generated by a context-free grammar
b. Some non-regular languages cannot be generated by any CFG
c. the intersection of a CFL and regular set is a CFL
d. All non-regular languages can be generated by CFGs.

34. Recursively enumerable languages are not closed under
a. union
b. homomorphism
c. complementation
d. concatenation

35. Which of the following problem is undecidable?
a. membership problem for CFL
b. membership problem for regular sets
c. membership problem for CSL
d. membership problem for type 0 languages

36. Recursive languages are
a. a proper superset of CFL
b. always recognized by PDA
c. are also called type 0 languages
d. always recognized by FSA

37. R1 and R2 are regular sets. Which of the following is not true?
a. R1 ∩ R2 neet not be regular
b. Σ* − R1 is regular
c. R1 ∪ R2 is regular
d.  is regular

38. Which of the following regular expression identity is true?
a. r(*) = r*
b. (r*s*)* = (r + s)*
c. (r + s)* = r* + s*
d. r*s* = r* + s*

39. Which one of the following statement is FALSE?
a. context-free languages are closed under union
b. context-free languages are closed under concatenation
c. context-free languages are closed under intersection
d. context-free languages are closed under Kleene closure

40. Which of the following conversion is not possible (algorithmically)?
a. regular grammar to context-free grammar
b. nondeterministic FSA to deterministic FSA
c. nondeterministic PDA to deterministic PDA
d. nondeterministic TM to deterministic TM

41. Consider three decision problems P1, P2 and P3. It is known that P1 is decidable and P2 is undecidable. Which one of the following is TRUE?
a. P3 is decidable if P1 is reducible to P3
b. P3 is undecidable if P3 is reducible to P2
c. P3 is undecidable if P2 is reducible to P3
d. P3 is decidable if P3 is reducible to P2’s complement

42. Consider three problems P1, P2 and P3. It is known that P1 has polynomial time solution and P2 is NP-complete and P3 is in NP. Which one of the following is true.
a. P3 has polynomial time solution if P1 is polynomial time reducible toP3
b. P3 is NP complete if P3 is polynomial time reducible to P2
c. P3 is NP complete if P2 is reducible to P3
d. P3 has polynomial time complexity and P3 is reducible to P2

43. Consider the FSA M
 The language recognized by M is
a. {w ∊ {a, b}* | every a in w is followed by exactly two b’s}
b. {w ∊ {a, b}* | every a in w is followed by atleast two b’s}
c. {w ∊ {a, b}* |w contains the substring ‘abb’}
d. {w ∊ {a, b}* |w does not contain ‘aa’ as substring}

44. Let Nf and Np denote the classes of languages accepted by nondeterministic FSA and nondeterministic PDA, respectively. Let Df and Dp denote the classes of languages accepted by deterministic FSA and PDA respectively. Which of the following is TRUE?
Some of these questions have appeared in GATE examinations.
a. Df ⊂ Nf Dp ⊂ Np
b. Df ⊂ Nf Dp = Np
c. Df = Nf Dp ⊂ Np
d. Df = Nf Dp = Np


45. Consider the languages
L1 = {anbncm|n, m > 0} and L2 = {anbmcm|n, m > 0}
Which one of the following statements is false?
a. L1 ∩ L2 is a CFL
b. L1 ∪ L2 is a CFL
c. L1 ∪ L2 is inherently ambiguous
d. L1 ∩ L2 is a CSL

46. Consider the languages
L1 = {anbmcndp|n, m, p > 0} and L2 = {anbmcpdm|n, m, p> 0}
Which one of the following statements is false?
a. L1 ∩ L2 is a CFL
b. L1 ∪ L2 is a CFL
c. L1 ∪ L2 is inherently ambiguous
d. L1 ∩ L2 is a CSL

47. Consider the languages
L1 = {anbmcmdn|n, m > 0} and L2 = {anbncmdm|n, m > 0}
Which one of the following statements is false?
a. L1 ∪ L2 is a CFL
b. L1 ∩ L2 is a CFL
c. L1 and L2 are CFL
d. L1 ∩ L2 is a CSL

48. Let L and   be a language and its complement. Which one of the following possibilities will not hold?
a. L and   are recursive
b. L is recursively enumerable but not recursive   is not recursively enumerable
c. L and   are not recursively enumerable
d. L and   are recursively enumerable but not recursive

49. Let L1 be a recursive language and let L2 be a recursively enumerable language which is not recursive. Which one of the following is TRUE?
a.  is recursive,   is recursively enumerable.
b.  is recursive,   is not recursively enumerable.
c.  and   are recursively enumerable.
d.  is recursively enumerable and   is recursive.

50. Consider the languages
L1 = {wwR|w ∊ {0,1}*}
L2 = {wcwR|w ∊ {0,1}*}
L3 = {ww|w ∊ {0,1}*}
Which one of the following is TRUE?
a. L1 is deterministic CFL
b. L2 is deterministic CFL
c. L3 is a CFL but not a deterministic CFL
d. L3 is deterministic CFL

51. Let S be a NP–complete problem and Q and R be two other problems not known to be in NP. Q is polynomial time reducible to S and S is polynomial time reducible to R. Which one of the following statements is TRUE?
a. R is NP complete
b. R is NP hard
c. Q is NP complete
d. Q is NP hard

52. L1 = {an + m bn cm|n, m ≥ 0}
L2 = {an + m bn + m cm|n, m ≥ 0}
L3 = {an + m bn + m cm + n|n, m ≥ 0}
Which of these languages are not CF.
a. L1 only
b. L3 only
c. L1 and L2
d. L2 and L3

53. If s is a string over (0+1)* then let m0 (s) denote the number of 0’s in s andn1 (s) the number of 1’s in s. Which one of the following languages is not regular?
a. L = {s ∊ (0+1)*|n0(s) is a 3-digit prime}
b. L = {s ∊ (0+1)*|for every prefix s′ of s, |n0 (s′) − n1(s′)| ≤ 2}
c. L = {s ∊ (0+1)*‖n0(s) − n1(s)| ≤ 4}
d. L = {s ∊ (0+1)*|n0(s) mod 7 = n1(s) mod 5 = 0}

54. For s ∊ (0+1)*let d(s) denote the decimal value of s (eg. D(|0|) = 5).
Let L = {s ∊ (0+1)*|d(s) mod 5 = 2 and d(s) mod 7 ≠ 4}
Which one of the following statements is TRUE?
a. L is recursively enumerable but not recursive
b. L is recursive, but not context-free
c. L is context-free, but not regular
d. L is regular

55. Let FHAM be the problem of finding a Hamiltonian cycle in a graph G and DHAM be the problem of determining if a Hamiltonial cycle exists in a graph. Which one of the following is TRUE?
a. Both FHAM and DHAM are NP-hard
b. FHAM is NP hard, but DHAM is not
c. DHAM is NP hard, but FHAM is not
d. Neither FHAM nor DHAM is NP hard

56. Consider the following statements about the context-free grammar G = {S →SS, S → ab, S → ba, S → c}
I. G is ambiguous
II. G produces all strings with equal number of a’s and b’s
III. G can be accepted by a deterministic PDA
Which combination below expresses all the true statements about G?
a. I only
b. I and III only
c. II and III only
d. I, II and III

57. Let L1 be a regular language and L2 a deterministic CFL. L3 is recursively enumerable but not recursive. Which one of the following statement is FALSE?
a. L1 ∩ L2 is a DCFL
b. L3 ∩ L1 is recursive
c. L1 ∪ L2 is context-free
d. L1 ∩ L2 ∩ L3 is recursively enumerable

58. Consider the regular language L = (111 + 11111)*. The minimum number of states in any DFA accepting the language is
a. 3
b. 5
c. 8
d. 9

59. Which one of the following grammars generates the language L = {aibj|i ≠j}.
a.
S → AC|CB
C → aCb|a|b
A → aA|ε
B → Bb|ε

b.
S → aS|Sb|a|b

c.
S → AC|CB
C → aCb|ε
A → aA|ε
B → Bb|ε

d.
S → AC|CB
C → aCb|ε
A → aA|a
B → bB|b


60. In the above correct grammar what is the minimum length of the derivation (number of steps starting from S) to generate the string a1 bm with l ≠ m?
a. max(l, m) + 2
b. l + m + 2
c. l + m + 3
d. max(l, m) + 3

61. Consider S → SS|a.
What is the number of different derivation trees for aaaaa
a. 3
b. 5
c. 7
d. 14

62. Which one of the following grammar generates L = {ai bj ck|i ≠ k, i, j, k ≥ 1}
a. S → AC|CB
A → aA|a
B → Bc|c
C → aCc|bD|b
D → bD|b
b. S → aS|aA
A → bA|bB
B → cB|c
c. S → AB
A → aAb|ab
B → bBc|bc
d. S → AC|CB
A → aA|ε
B → Bc|ε
C → aCc|ε|bD
D → bD|b|ε

63. A minimum state deterministic automaton accepting the language L = {w|w ∊ {0,1}*, the number of 0’s and 1’s in w are divisible by 3 and 5 respectively} has
a. 15 states
b. 11 states
c. 10 states
d. 9 states

64. The language L = {0i21i / i ≥ 0} over the alphabet {0, 1, 2} is
a. not recursive
b. is recursive and is a deterministic CFL
c. is a regular language
d. is not a deterministic CFL but a CFL

65. Which of the following languages is regular?
a. {wwR|w ∊ {0, 1}+}
b. {wwRx|w, x ∊ {0, 1}+}
c. {w x w R|w, x ∊ {0, 1}+}
d. {xwwR|w, x ∊ {0, 1}+}

66. Let Σ = {0, 1}, L1 = Σ* and L2 = {0n 1n|n ≥ 1} then the languages L1 ∪ L2and L2 are respectively
a. regular, regular
b. regular, not regular
c. not regular, regular
d. not regular, not regular

67. Which of the following statements is false?
a. The halting problem for Turing machines is undecidable
b. determining whether a context-free grammar is ambiguous is un-decidable
c. given two arbitrary context-free grammar, G1 and G2, it is undecidable with L(G1) = L(G2)
d. given two regular grammars G1 and G2, it is undecidable whetherL(G1) = L(G2)

68. Two of the following four regular expressions are equivalent. Which two?
i. (00)* (0 + ε)
ii. (00)*
iii. 0*
iv. 0(00)*
a. (i) and (ii)
b. (ii) and (iii)
c. (i) and (iii)
d. (iii) and (iv)

69. Let L ⊆ Σ* where Σ = {a, b}. Which of the following is true?
a. L = {x|x has an equal number of a’s and b’s } is regular
b. L = {an bn | n ≥ 1} is regular
c. L = {am bn | m, n ≥ 1} is regular
d. L = {x|x has more a’s than b’s} is regular

70. Define for a CFL L, init (L) = {u | uv ∊ L for some v ∊ {0, 1}*}. In other words init (L) is the set of prefixes of L. Let L = {w|w ∊ {0, 1}+, w has equal number of 0’s and 1’s}. Then init (L) is
a. the set of all binary strings with unequal number of 0’s and 1’s
b. the set of all binary stings including ε
c. the set of all binary strings with exactly one more 0 than the number of 1’s or one more 1 than the number of 0’s.
d. none of the above

71. If L1 and L2 are CFL and R a regular set, one of the languages below is not necessarily a CFL. Which one?
a. L1L2
b. L1 ∪ L2
c. L1 ∩ L2
d. L1 ∩ R

72. The grammar whose productions are
〈stmt〉 → if 〈id〉 then 〈stmt〉
〈stmt〉 → if 〈id〉 then 〈stmt〉 else 〈stmt〉
〈stmt〉 → 〈id〉 := 〈id〉
〈id〉 → a|b|c|d|f
is ambiguous because
a. the sentence if a then if b then c := d has more than one derivation trees
b. the leftmost and rightmost derivation of the sentence if a then if bthen c := d give rise to different parse trees
c. the sentence if a then if b then c := d else c := f has more than two parse trees
d. the sentence if a then if b then c := d else c := f has two parse trees

73. Which one of the following regular expressions over {0, 1} denotes the set of all strings not containing 100 as a substring?
a. 0*(11*0)*
b. 0*1010*
c. 0*1*01
d. 0*(10 + 1)*

74. Which one of the following is not decidable?
a. given a Turing machine M, a string s, and an integer k, M acceptss with k steps
b. equivalence of two given Turing machines
c. language accepted by a given DFSA is nonempty
d. language generated by a CFG is nonempty

75. Which of the following languages over {a, b, c} is accepted by a deterministic PDA?
a. {wbwR|w ∊ {a, c}*}
b. {wwR|w ∊ {a, b, c}*}
c. {anbncn|n ≥ 1}
d. {w|w is a palindrome over {a, b, c}}

76. Which of the following instances of the post correspondence problem has a viable sequence (a solution)?
a. {(b, bb), (bb, bab), (bab, abb), (abb, babb)}
b. {(ab, aba), (baa, aa), (aba, baa)}
c. {(ab, abb), (ba, aaa), (aa, a)}
d. none of the above

77. It is undecidable, whether
a. an arbitrary TM has 15 states
b. an arbitrary TM halts after 10 steps
c. an arbitrary TM ever prints a specific letter
d. an arbitrary TM accepts a string w in 5 steps

78. Let r = 1(1+0)*, s = 11*0 and t = 1*0 be three regular expressions and R, S, T the regular sets corresponding to them. Which of the following is true?
a. S ⊂ R
b. R ⊂ S
c. T ⊂ S
d. R ⊂ T

79. Which one of the following is the strongest correct statement about a finite language L over a finite alphabet Σ?
a. L is undecidable
b. L is recursive
c. L is a CSL
d. L is a regular set

80. Which of the following statements is TRUE?
a. infinite union of regular sets is regular
b. infinite union of finite sets is regular
c. finite union of finite sets is regular
d. complement of a finite set need not be regular

Introduction To Networking

1. Telephone systems may be classified as:
A. duplex and asymmetrical.
B. simplex and asymmetrical.
C. duplex and symmetrical.
D. simplex and symmetrical.

2. A network that provides a constant bandwidth for the complete duration of a message transfer is a:
A. cell switched network.
B. circuit switched network.
C. packet switched network.

3. A router:
A.forwards a packet to all outgoing links, except the link upon which the packet originated.
B.forwards a packet to all outgoing links.
C.determines on which outgoing link a packet is to be forwarded.
D.forwards a packet to the next free outgoing link.

4. The Internet is an example of a:
 A.cell switched network.
 B.circuit switched network.
 C.packet switched network.

5. A data link between the head office of a financial organization and one of its branches runs continuously at 2.048 Mbps. Between the hours of 0900 and 1700 it is noted that there are 295 bits received in error. Determine the bit error rate.
A. 2 x 10-10
B. 5 x 10-8
C. 5 x 10-9
D. 2 x 10-7

6. The optical fibre trans-Atlantic cable TAT-14 includes a section from Bude, Cornwall to Tuckerton, New Jersey. Determine the propagation delay if the route length is 6,254 km.
A. 31.27 ms.
B. 3.198 ms.
C.31.98 ms.
D.312.7 ms.

7. A file is downloaded to a home computer using a 56 kbps modem connected to an Internet Service Provider. If the download completes in 2 minutes, estimate the maximum size of data downloaded.
A. 6.72 Mbit.
B. 26.88 Mbit.
C. 336 Kbit.
D. 13.44 Mbit.

8. Baseband transmission may be defined as the transmission of a signal over a link:
A. at a different band of frequencies.
B. which is relatively short.
C. by means of wires.
D. without any change in frequency.

9. Skin effect may be described as: 
(Note: more than one answer is correct.)   
A. conduction of electricity through skin.
B. a thin layer of electricity.
C. conduction restricted to a small central region of a conductor.
D. conduction restricted to the outer layer of a conductor.

10. A block of data consisting of 2048 bits is transmitted between two computers interconnected by 450 m of twisted-pair wire. If the transmission rate is 34 kbps determine a, the ratio of propagation delay to transmission delay.
A. 376 x 10-6
B. 37.6 x 10-6
C. 3.76 x 10-3
D. 3.76 x 10-6

11. Asynchronous transmission may be defined as:
A. communication where receiver will operate satisfactorily, even if its clock frequency is appreciably different to that of the transmitter.
B. communication where the receiver clock must be in exact synchronism with that of the transmitter.
C. communication where the receiver clock must be in approximate synchronism with that of the transmitter.

12. Synchronous transmission may be defined as:
 A. communication where the receiver clock is arranged to be in exact synchronism with that of the receiver.
 B. communication where the receiver will operate satisfactorily, even if its clock frequency is appreciably different to that of the transmitter.
 C. communication where the receiver clock must be in approximate synchronism with that of the transmitter.

13. Manchester encoding is principally designed to:
A. increase the bandwidth of a signal transmitted on the medium.
B. have more than one symbol per bit period.
C. ensure that a transition occurs in the centre of each bit period.
D. ensure that the line remains unbalanced.

14. Is the following statement true of the Go-back-N error control strategy? 
A transmitter may send up to N packets before it receives an acknowledgment.
A. True
B. False
 
15. A protocol data unit (PDU) is exchanged between the same layer in two separate protocol stacks. It comprises the PDU passed from the layer immediately above and its own protocol control information.
A. True
B. False



16: In OSI network architecture, the dialogue control and token management are responsibility of
a. session layer
b. network layer
c. transport layer
d. data link layer
e. none of above

17: In OSI network architecture, the routing is performed by
a. network layer
b. data link layer
c. transport layer
d. session layer
e. none of above

18: Which of the following performs modulation and demodulation?
a. fiber optics
b. satellite
c. coaxial cable
d. modem
e. none of the above

19: The process of converting analog signals into digital signals so they can be processed by a receiving computer is referred to as:
a. modulation
b. demodulation
c. synchronizing
d. digitising

20: How many OSI layers are covered in the X.25 standard?
a. Two
b. Three
c. Seven
d. Six
e. None of above

21: Layer one of the OSI model is
a. physical layer
b. link layer
c. transport layer
d. network layer
e. none of above

22: The x.25 standard specifies a 
a. technique for start-stop data
b. technique for dial access
c. DTE/DCE interface
d. data bit rate
e. none of above

23: Which of the following communication modes support two-way traffic but in only one direction at a time?
a. simplex
b. half duplex
c. three-quarters duplex
d. all of the above
e. none of the above

24: Which of the following might be used by a company to satisfy its growing communications needs?
a. front end processor
b. multiplexer
c. controller
d. concentrator
e. all of the above

25: What is the number of separate protocol layers at the serial interface gateway specified by the X.25 standard?
a. 4
b. 2
c. 6
d. 3
e. none of the above

26: The interactive transmission of data within a time sharing system may be best suited to 

a. simplex lines

b. half-duplex lines

c. full duplex lines

d. biflex-lines

27: Which of the following statement is incorrect?

a. The difference between synchronous and asynchronous transmission is the clocking derived from the data in synchronous transmission.

b. Half duplex line is a communication line in which data can move in two directions, but not at the same time.

c. Teleprocessing combines telecommunications and DP techniques in online activities

d. Batch processing is the prefered processing mode for telecommunication operation.

28: Which of hte following is considered a broad band communication channel?

a. coaxial cable

b. fiber optics cable

c. microwave circuits

d. all of above

29: Which of the following is not a transmission medium?

a. telephone lines

b. coaxial cables

c. modem

d. microwave systems

30: Which of the following does not allow multiple uses or devices to share one communication line?

a. doubleplexer

b. multiplexer

c. concentrator

d. controller

31: Which of the following signal is not standard RS-232-C signal?

a. VDR

b. RTS

c. CTS

d. DSR

32: Which of the following statement is incorrect?

a. Multiplexers are designed to accept data from several I/O devices and transmit a unified stream of data on one communication line

b. HDLC is a standard synchronous communication protocol.

c. RTS/CTS is the way the DTE indicates that it is ready to transmit data and the way the DCW indicates that it is ready to accept data

d. RTS/CTS is the way the terminal indicates ringing

33: Which of the following is an advantage to using fiber optics data transmission?

a. resistance to data theft

b. fast data transmission rate

c. low noise level

d. all of above

34: Which of the following is required to communicate between two computers?

a. communications software

b. protocol

c. communication hardware

d. all of above including access to transmission medium

35: The transmission signal coding method of TI carrier is called

a. Bipolar

b. NRZ

c. Manchester

d. Binary

36: Which data communication method is used to transmit the data over a serial communication link?
a. simplex
b. half-duplex
c. full-duplex
d. b and c
e. None of above

37: What is the minimum number of wires needed to send data over a serial communication link layer?
a. 1
b. 2
c. 4
d. 6
e. none of above

38: Which of the following types of channels moves data relatively slowly?
a. wide band channel
b. voice band challen
c. narrow band channel

39: Most data communications involving telegraph lines use:
a. simplex lines
b. wideband channel
c. narrowband channel
d. dialed service

40: A communications device that combines transmissions from several I/O devices into one line is a 
a. concentrator
b. modifier
c. multiplexer
d. full-duplex line

41: How much power (roughly) a light emitting diode can couple into an optical fiber?
a. 100 microwatts
b. 440 microwatts
c. 100 picowatts
d. 10 miliwatts

42: The synchronous modems are more costly than the asynchronous modems because
a. they produce large volume of data
b. they contain clock recovery circuits
c. they transmit the data with stop and start bits
d. they operate with a larger bandwidth
e. none of above

43: Which of the following statement is correct?
a. terminal section of a synchronous modem contains the scrambler
b. receiver section of a synchronous modem contains the scrambler
c. transmission section of a synchronous modem contains the scrambler
d. control section of a synchronous modem contains the scrambler
e. none of the above

44: In a synchronous modem, the digital-to-analog converter transmits signal to the 
a. equilizer
b. modulator
c. demodulator
d. terminal
e. none of aobve

45: Which of the following communications lines is best suited to interactive processing applications?
a. narrow band channel
b. simplex lines
c. full duplex lines
d. mixed band channels

46:  A remote batch-processing operation in which data is solely input to a central computer would require
a. telegraphp line
b. simplex lines
c. mixed bad channel
d. all of above

47: A band is always equivalent to 
a. a byte
b. a bit
c. 100 bits
d. none of above

48: The loss in signal power as light travels down the fiber is called
a. attenuation
b. progragation
c. scattering
d. interruption

49: Avalanche photodiode receivers can detect bits of transmitted data by receiving
a. 100 photons
b. 200 photons
c. 2000 photons
d. 300 photons

50: Communiction circuits that transmit data in both directions but not at the same time are operating in
a. a simplex mode
b. a half duplex mode
c. a full duplex mode
d. an asynchronous mode

51: An example of a medium speed, switched communications service is
a. series 1000
b. data phone 50
c. DDD
d. All of the above

52: In communication satellite, multiple repeaters are known as
a. detector
b. modulator
c. stations
d. transponders

53: While transmitting odd-parity coded symbols, the number of zeros in each symbol is
a. odd
b. even
c. a and b both
d. unknown

54: Data communications monitors available on the software marked include
a. ENVIRON/1
b. TOTAL
c. BPL
d. Telnet

55: An example of an analog communication method is
a. laser beam
b. microwave
c. voice grade telephone line
d. all of the above

56: Number of bits per symbol used in Baudot code is
a. 7

b. 5

c. 8

d. 9

57: What is the main difference between DDCMP and SDLC?

a. DDCMP does not need special hardware to final the beginning of a message

b. DDCMP has a message header

c. SDLC has a IP address

d. SDLC does not use CRC

58: An example of digital, rather than analog, communication is

a. DDD

b. DDS

c. WATS

d. DDT

59: Terminals are required for 

a. real-time, batch processing & time-sharing

b. real time, time-sharing & distributed message processing

c. real time, distributed processing & manager inquiry

d. real-time,  time sharing & message switching

60: The receive equilizer reduces delay distortions using a

a. tapped delay lines

b. gearshift

c. descrambler

d. difference engine

61: Ina synchronous modem, the receive equilizer is known as

a. adaptive equilizer

b. impariment equilizer

c. statistical equilizer

d. compromise equilizer 

62: The channel in the data communication model can be

a. postal mail services

b. telephone lines

c. radio lines

d. any of the above

63: A data terminal serves as an

a. Effector

b. sensor

c. both a and b

d. neither a nor b

64: Which of the following transmission systems provide the highest data rate to in individual device?

a. computer bus

b. telephone lines

c. voice and mode

d. lease lines

65: A protocol is a set of rules governing a time sequence of events that must take place

a. between peers

b. between an interface

c. between modems

d. across an interface

66. The memory address of the first element of an array is called

a. floor address
b. foundation address
c. first address
d. base address  

67. The memory address of fifth element of an array can be calculated by the formula

a. LOC(Array[5]=Base(Array)+w(5-lower bound), where w is the number of words per memory cell for the array 
b. LOC(Array[5])=Base(Array[5])+(5-lower bound), where w is the number of words per memory cell for the array
c. LOC(Array[5])=Base(Array[4])+(5-Upper bound), where w is the number of words per memory cell for the array
d. None of above
  

68. Which of the following data structures are indexed structures?

a. linear arrays 
b. linked lists
c. both of above
d. none of above
  

69. Which of the following is not the required condition for binary search algorithm?

a. The list must be sorted
b. there should be the direct access to the middle element in any sublist
c. There must be mechanism to delete and/or insert elements in list 
d. none of above
 

70. Which of the following is not a limitation of binary search algorithm?

a. must use a sorted array
b. requirement of sorted array is expensive when a lot of insertion and deletions are needed
c. there must be a mechanism to access middle element directly
d. binary search algorithm is not efficient when the data elements are more than 1000.  

71. Two dimensional arrays are also called

a. tables arrays
b. matrix arrays
c. both of above 
d. none of above
 

72. A variable P is called pointer if

a. P contains the address of an element in DATA. 
b. P points to the address of first element in DATA
c. P can store only memory addresses
d. P contain the DATA and the address of DATA
 

73. Which of the following data structure can't store the non-homogeneous data elements?

a. Arrays 
b. Records
c. Pointers
d. None
 

74. Which of the following data structure store the homogeneous data elements?

a. Arrays
b. Records 
c. Pointers
d. None
 

75. Each data item in a record may be a group item composed of sub-items; those items which are indecomposable are called

a. elementary items
b. atoms
c. scalars
d. all of above  

76. The difference between linear array and a record is

a. An array is suitable for homogeneous data but hte data items in a record may have different data type
b. In a record, there may not be a natural ordering in opposed to linear array.
c. A record form a hierarchical structure but a lienear array does not
d. All of above  

77. Which of the following statement is false?

a. Arrays are dense lists and static data structure
b. data elements in linked list need not be stored in adjecent space in memory
c. pointers store the next data element of a list 
d. linked lists are collection of the nodes that contain information part and next pointer
 

78. Binary search algorithm can not be applied to

a. sorted linked list 
b. sorted binary trees
c. sorted linear array
d. pointer array
 

79. When new data are to be inserted into a data structure, but there is no available space; this situation is usually called

a. underflow
b. overflow 
c. housefull
d. saturated
 

80. The situation when in a linked list START=NULL is

a. underflow 
b. overflow
c. housefull
d. saturated
 

81. Which of the following is two way list?

a. grounded header list
b. circular header list
c. linked list with header and trailer nodes
d. none of above  

82. Which of the following name does not relate to stacks?

a. FIFO lists 
b. LIFO list
c. Piles
d. Push-down lists
 

83. The term "push" and "pop" is related to the

a. array
b. lists
c. stacks 
d. all of above
 

84. A data structure where elements can be added or removed at either end but not in the middle

a. Linked lists
b. Stacks
c. Queues
d. Deque  

85. When inorder traversing a tree resulted E A C K F H D B G; the preorder traversal would return
a. FAEKCDBHG
b. FAEKCDHGB 
c. EAFKHDCBG
d. FEAKDCHBG

86. Two main measures for the efficiency of an algorithm are

a. Processor and memory
b. Complexity and capacity
c. Time and space 
d. Data and space
  

87. The time factor when determining the efficiency of algorithm is measured by

a. Counting microseconds
b. Counting the number of key operations
c. Counting the number of statements
d. Counting the kilobytes of algorithm

88. The space factor when determining the efficiency of algorithm is measured by

a. Counting the maximum memory needed by the algorithm 
b. Counting the minimum memory needed by the algorithm
c. Counting the average memory needed by the algorithm
d. Counting the maximum disk space needed by the algorithm

89. Which of the following case does not exist in complexity theory

a. Best case
b. Worst case
c. Average case
d. Null case

90. The Worst case occur in linear search algorithm when

a. Item is somewhere in the middle of the array
b. Item is not in the array at all
c. Item is the last element in the array
d. Item is the last element in the array or is not there at all

91. The Average case occur in linear search algorithm

a. When Item is somewhere in the middle of the array 
b. When Item is not in the array at all
c. When Item is the last element in the array
d. When Item is the last element in the array or is not there at all

92. The complexity of the average case of an algorithm is

a. Much more complicated to analyze than that of worst case 
b. Much more simpler to analyze than that of worst case
c. Sometimes more complicated and some other times simpler than that of worst case
d. None or above

93. The complexity of linear search algorithm is

a. O(n) 
b. O(log n)
c. O(n2)
d. O(n log n)

94. The complexity of Binary search algorithm is

a. O(n)
b. O(log ) 
c. O(n2)
d. O(n log n)

95. The complexity of Bubble sort algorithm is

a. O(n)
b. O(log n)
c. O(n2) 
d. O(n log n)


96. The complexity of merge sort algorithm is

a. O(n)
b. O(log n)
c. O(n2)
d. O(n log n)


97. The indirect change of the values of a variable in one module by another module is called

a. internal change
b. inter-module change
c. side effect 
d. side-module update

98. Which of the following data structure is not linear data structure?

a. Arrays
b. Linked lists
c. Both of above
d. None of above

99. Which of the following data structure is linear data structure?

a. Trees
b. Graphs
c. Arrays 
d. None of above

100. The operation of processing each element in the list is known as

a. Sorting
b. Merging
c. Inserting
d. Traversal

101. Finding the location of the element with a given value is:

a. Traversal
b. Search 
c. Sort
d. None of above

102. Arrays are best data structures

a. for relatively permanent collections of data 
b. for the size of the structure and the data in the structure are constantly changing
c. for both of above situation
d. for none of above situation

103. Linked lists are best suited

a. for relatively permanent collections of data
b. for the size of the structure and the data in the structure are constantly changing 
c. for both of above situation
d. for none of above situation

104. Each array declaration need not give, implicitly or explicitly, the information about

a. the name of array
b. the data type of array
c. the first data from the set to be stored 
d. the index set of the array

105. The elements of an array are stored successively in memory cells because

a. by this way computer can keep track only the address of the first element and the addresses of other elements can be calculated 
b. the architecture of computer memory does not allow arrays to store other than serially
c. both of above
d. none of above.



106. If a computer on the network shares resources for others to use, it is called ____
a. Server
b. Client
c. Mainframe


107. Terminators are used in ______ topology.
a. Bus
b. Star


108. In _____ topology, if a computer’s network cable is broken, whole network goes down.
a. Bus
b. Star


109. For large networks, _______ topology is used.
a. Bus
b. Star
c. Ring


110. ISO stands for
a. International Standard Organization
b. International Student Organization
c. Integrated Services Organization


111. ISO OSI model is used in
a. Stand alone PC
b. Network environment


112. Network cable lies on _____ layer
a. Application
b. Network
c. Physical


113. ____ layer decides which physical pathway the data should take.
a. Application
b. Network
c. Physical


114. ISDN is an example of ______ network
a. Circuit switched
b. Packet switched


115. X.25 is an example of ______ network
a. Circuit switched
b. Packet switched


116. _____________ allows LAN users to share computer programs and data.
a. Communication server
b. Print server
c. File server


117. Print server uses ________ which is a buffer that holds data before it is send to the printer.
a. Queue
b. Spool
c. Node


118. A standalone program that has been modified to work on a LAN by including concurrency controls such as file and record locking is an example of____
a. LAN intrinsic software
b. LAN aware software
c. Groupware
d. LAN ignorant software


119. The ______ portion of LAN management software restricts access, records user activities and audit data etc.
a. Configuration management
b. Security management
c. Performance management


120. What is the max cable length of STP?
a. 100 ft
b. 200 ft
c. 100 m
d. 200 m


121. What is the max data capacity of STP?
a. 10 mbps
b. 100 mbps
c. 1000 mbps
d. 10000 mbps


122. Which connector STP uses?
a. BNC
b. RJ-11
c. RJ-45
d. RJ-69


123. What is the central device in star topology?
a. STP server
b. Hub/switch
c. PDC
d. Router


124. What is max data capacity for optical fiber cable?
a. 10 mbps
b. 100 mbps
c. 1000 mbps
d. 10000 mbps


125. Which of the following architecture uses CSMA/CD access method?
a. ARCnet
b. Ethernet