Computer Science — Introductory level

Les questions du quiz

1. 1. The access matrix approach to protection has the difficulty that
   1. the matrix, if stored directly, is large and can be clumsy to manage
   2. it is not capable of expressing complex protection requirements
   3. deciding whether a process has access to a resource is undecidable
   4. there is no way to express who has rights to change the access matrix itself
2. 2. An integer c is a common divisor of two integers x and y if and only if c is a divisor of x and c is a divisor of y. Which of the following sets of integers could possibly be the set of all common divisors of two integers?
   1. {-6,-2, -1, 1, 2, 6}
   2. {-6, -2, -1, 0, 1, 2, 6}
   3. {-6, -3, -2, -1, 1, 2, 3, 6}
   4. {-6, -3, -2, -1, 0, 1, 2, 3, 6}
3. 3. In the NoNicks operating system, the time required by a single file-read operation has four nonoverlapping components:
   disk seek time-25 msec
   disk latency time-8 msec
   disk transfer time- 1 msec per 1,000 bytes
   operating system overhead-1 msec per 1,000 bytes + 10 msec
   In version 1 of the system, the file read retrieved blocks of 1,000 bytes. In version 2, the file read (along with the underlying layout on disk) was modified to retrieve blocks of 4,000 bytes. The ratio of-the time required to read a large file under version 2 to the time required to read the same large file under version 1 is approximately
   1. 1:4
   2. 1:3.5
   3. 1:1
   4. 1.1:1
4. 4. You want to cluster 7 points into 3 clusters using the k-Means Clustering algorithm. Suppose after the first iteration, clusters C1, C2 and C3 contain the following two-dimensional points: C1 contains the 2 points: {(0,6), (6,0)} C2 contains the 3 points: {(2,2), (4,4), (6,6)} C3 contains the 2 points: {(5,5), (7,7)} What are the cluster centers computed for these 3 clusters?
   1. C1: (3,3), C2: (4,4), C3: (6,6)
   2. C1: (3,3), C2: (6,6), C3: (12,12)
   3. C1: (6,6), C2: (12,12), C3: (12,12)
   4. C1: (0,0), C2: (48,48), C3: (35,35)
5. 5. Any set of Boolean operators that is sufficient to represent all Boolean expressions is said to be complete. Which of the following is NOT complete?
   1. {AND, NOT}
   2. {NOT, OR}
   3. {AND, OR}
   4. {NAND}
6. 6. Consider the collection of all undirected graphs with 10 nodes and 6 edges. Let M and m, respectively, be the maximum and minimum number of connected components in any graph in the collection. If a graph has no selfloops and there is at most one edge between any pair of nodes, which of the following is true?
   1. M = 10, m = 10
   2. M = 10, m = 1
   3. M = 7, m = 4
   4. M = 6, m = 4
7. 7. Resolution theorem proving for showing that a formula of propositional logic is not satisfiable has which of the following properties?
   I. It is a sound proof system in the sense that there does not exist a proof of the unsatisfiability of a satisfiable formula of propositional logic.
   II. It is a complete proof system in the sense that there is a proof of unsatisfiability for every unsa tisfiable formula of propositional logic.
   III. It is a succinct proof system in the sense that whenever an unsatisfiable formula F of propositional logic has a resolution proof, F also has a proof whose length is polynomial in the length of F.
   1. I only
   2. III only
   3. I and II only
   4. I and III only
8. 8. Which of the following statements describe(s) properties of a purely segmented memory system?
   I. It divides memory into units of equal size.
   II. It permits implementation of virtual memory.
   III. It suffers from internal fragmentation.
   1. I only
   2. II only
   3. III only
   4. I and III
9. 9. Which of the following statements about floating-point arithmetic is NOT true?
   1. It is inherently nonassociative because some numbers have no exact representation.
   2. It is inherently nonassociative because there have to be upper and lower bounds on the size of numbers.
   3. Associativity can be achieved with appropriate roundoff conventions.
   4. Some rational numbers have no exact representation.
10. 10. Suppose sharing of tiles in a multilevel directory structure is achieved with directory entries that are links pointing to a node containing information about a shared file. Information in this node includes (1) the owner of the file, (2) a count of the number of links to the tile, and (3) the disk block numbers of the file. What is a primary drawback to this approach to sharing?
    1. If the owner modifies the file, another user who does not share will see the changes.
    2. If the owner renames the file, other users will not be able to access it.
    3. If the owner is allowed to delete a file, dangling links may result.
    4. If any user who shares the file appends to it, others who share it will not be able to access the new disk blocks.
11. 11. Mergesort works by splitting a list of n numbers in half, sorting each half recursively, and merging the two halves. Which of the following data structures will allow mergesort to work in O(n log n) time?
    I. A singly linked list
    II. A doubly linked list
    III. An array
    1. None
    2. III only
    3. I and II only
    4. I, II, and III
12. 12. If p(x) is the minimal-degree interpolating polynomial for the real-valued function f(x) at the n + 1 distinct real numbers x0, .... xn what is the maximum possible degree of p(x)?
    1. n
    2. n + 1
    3. n + 2
    4. 2n
13. 13. An internal hash table has 5 buckets, numbered 0, 1, 2, 3, 4. Keys are integers, and the hash function h(i) = i mod 5 is used, with linear resolution of collisions (i.e., if bucket h(i) is filled, the buckets h(i) + 1, h(i) + 2, ... are tried successively with all bucket numbers computed modulo 5). If elements with keys 13, 8, 24, 10, and 3 are inserted, m that order, into an initially blank hash table, then the content of the bucket numbered 2 is
    1. 3
    2. 8
    3. 10
    4. 13
14. 14. TCP protocol is responsible (among other things) for
    1. Routing packets through the network
    2. Reliable delivery of packets between directly connected machines
    3. Reliable delivery of large (multi-packet) messages between machines that are not necessarily directly connected
    4. Dealing with differences among operating system architectures
15. 15. Let A and B be two sets of words (strings) from Σ*, for some alphabet of symbols Σ. Suppose that B is a subset of A. Which of the following statements must always be true of A and B ?
    I. If A is finite, then B is finite.
    II. If A is regular, then B is regular.
    III. If A is context-free, then B is context-free.
    1. I only
    2. II only
    3. III only
    4. I and II only
16. 16. For all strings x, the function x^M is defined recursively as follows.
    e^M= e, and
    if w is a string and a is a string with length 1, then
    (aw)^M = aw^Ma.
    Let a be a string with length 1, and let x and y be arbitrary strings. Which of the following is true?
    1. a^M = a
    2. (ax)^M = (xa)^M
    3. (xy)^M = y^Mx^M
    4. None of the above
17. 17. Which of the following is NOT a reasonable justification for choosing to busy-wait on an asynchronous event?
    1. The wait is expected to be short.
    2. A busy-wait loop is easier to code than an interrupt handler.
    3. There is no other work for the processor to do.
    4. The program executes on a time-sharing system.
18. 18. The language {ww | w in (0 + 1)*} is
    1. not accepted by any Turing machine
    2. accepted by some Turing machine, but by no pushdown automaton
    3. accepted by some pushdown automaton, but not context-free
    4. context-free, but not regular
19. 19. Which of the following statements about Ethernets is typically FALSE?
    1. Ethernets use circuit switching to send messages.
    2. Ethernets use buses with multiple masters.
    3. Ethernet protocols use a collision-detection method to ensure that messages are transmitted properly.
    4. Networks connected by Ethernets are limited in length to a few hundred meters.
20. 20. Let P be a procedure that for some inputs calls itself (i.e., is recursive). If P is guaranteed to terminate, which of the following statements must be true?
    I. P has a local variable.
    II. P has an execution path where it does not call itself.
    III. P either refers to a global variable or has at least one parameter.
    1. I only
    2. II only
    3. I and II only
    4. II and III only
21. 21. Which of the following comes closest to being a perfectly secure encryption scheme?
    1. The Caesar Cipher, a substitution cipher
    2. DES (Data Encryption Standard), a symmetric-key algorithm
    3. Enigma, a transposition cipher
    4. One-time pad
22. 22. Of the following problems concerning a given undirected graph G, which is currently known to be solvable in polynomial time?
    1. Finding a longest simple cycle in G
    2. Finding a shortest cycle in G
    3. Finding ALL spanning trees of G
    4. Finding a largest clique in G
23. 23. Let x = 1. What is x << 3 in Python 3?
    1. 1
    2. 3
    3. 8
    4. 16
24. 24. In Python 3, which of the following function convert a string to an int in python?
    1. int(x [,base])
    2. long(x [,base] )
    3. float(x)
    4. str(x)
25. 25. A user enters a Web address in a browser, and a request for a file is sent to a Web server. Which of the following best describes how the file is sent to the user?
    1. The file is broken into packets for transmission. The packets must be reassembled upon receipt.
    2. The file is broken into packets for transmission. The user's browser must request each packet in order until all packets are received.
    3. The server attempts to connect directly to the user's computer. If the connection is successful, the entire file is sent. If the connection is unsuccessful, an error message is sent to the user.
    4. The server repeatedly attempts to connect directly to the user's computer until a connection is made. Once the connection is made, the entire file is sent.
26. 26. Digital images are often represented by the red, green, and blue values (an RGB triplet) of each individual pixel in the image. A photographer is manipulating a digital image and overwriting the original image. Which of the following describes a lossless transformation of the digital image?
    1. Compressing the image in a way that may lose information but will suffer only a small loss of image quality.
    2. Creating the gray scale of an image by averaging the amounts of red, green, and blue in each pixel and assigning this new value to the corresponding pixel in the new image. The new value of each pixel represents a shade of gray, ranging from white to black.
    3. Creating the negative of an image by creating a new RGB triplet for each pixel in which each value is calculated by subtracting the original value from 255. The negative of an image is reversed from the original; light areas appear dark, and colors are reversed.
    4. Modifying part of the image by taking the pixels in one part of the picture and copying them to the pixels in another part of the picture.
27. 27. A programmer is writing a program that is intended to be able to process large amounts of data. Which of the following considerations is LEAST likely to affect the ability of the program to process larger data sets?
    1. How long the program takes to run
    2. How many programming statements the program contains
    3. How much memory the program requires as it runs
    4. How much storage space the program requires as it runs
28. 28. Suppose the characters 0,1, . . . ,8,9,A,B,C,D, E,F are used to represent a hexadecimal (base-16) number. Here A = 10, B = 11, . . . ,F = 15. What is the largest base-10 integer that can be represented with a two-digit hexadecimal number, such as 14 or 3A?
    1. 32
    2. 225
    3. 255
    4. 256
29. 29. A large data set contains information about all students majoring in computer science in colleges across the United States. The data set contains the following information about each student.
    ° The student's gender
    ° The state in which the student attends college
    ° The student's grade point average on a 4.0 scale
    
    Which of the following questions could be answered by analyzing only information in the data set?
    1. Do students majoring in computer science tend to have higher grade point averages than students majoring in other subjects?
    2. How many states have a higher percentage of female computer science majors than male computer science majors attending college in that state?
    3. What percent of students attending college in a certain state are majoring in computer science?
    4. Which college has the highest number of students majoring in computer science?
30. 30. The code segment below uses the procedure IsFound (list, item), which returns true if item appears in list and returns false otherwise. The list resultList is initially empty.
    FOR EACH item IN inputList1{
    IF (isFound (inputList2, item) )
    APPEND (resultList, item)
    }
    Which of the following best describes the contents of resultList after the code segment is executed?
    1. All elements in inputListl followed by all elements in inputList2
    2. Only elements that appear in both inputListl and inputList2
    3. Only elements that appear in either inputListl or inputList2 but not in both lists
    4. Only elements that appear in inputListl but not in inputList2

… et 10 autres questions.