2009-2010学年第1学期2009 级《计算机导论》考试试题A卷考试时间：2009年12月日班级学号姓名✧请将答案写在答题纸上，写明题号，不必抄题，字迹工整、清晰；✧请在答题纸和试题纸上都写上你的班级，学号和姓名，交卷时请将试题纸、答题纸和草纸一并交上来。

一、Choice Questions(20 questions, 1 score for each question)1. In the von Neumann model, the _______subsystem accepts data and programs and sends processing results to output devices.a. ALUb. Input/outputc. memoryd. control unit2. FORTRAN and COBOL are examples of ________.a. hardwareb. an operating systemsc. computer languagesd. algorithms3. The first computing machine to use the idea of storage and programming was called_______.a. the Madelineb. EDV ACc. the Babbage machined. the Jacquard loom4. A 32-bit code was developed by ______ to represent symbols in all languages.a. ANSIb. ISOc. EBCDICd. Hamming5. The bitmap graphic method and the vector graphic method are used to represent ______in a computer.a. audiob. videoc. imagesd. numbers6. When converting a decimal number to binary, you repeatedly divide by _______.a. 2b. 8c. 10d. 167. In ______ number representation, 1111 in memory represents –0.a. unsigned integersb. sign-and-magnitudec. one’s complementd. two’s complement8. Which number representation method is often used to convert analog signals to digital signals?a. unsigned integersb. sign-and magnitudec. one’s complementd. two’s complement9. For an 8-bit allocation, the smallest decimal number that can be represented in two’s complement form is _____.a. -8b. -127c. -128d. -25610. You use a bit pattern called a ________ to modify another bit pattern.a. maskb. carryc. floatd. byte11. ______ is a memory type with capacitors that need to be refreshed periodically.a. SRAMb. DRAMc. ROMd. a tape drive12. The _____ memory contains a copy of a portion of main memory.a. CPUb. cachec. maind. ROM13. The _____ controller is a high-speed serial interface that transfers data in packets.a. SCSIb. FireWirec. USBd. IDE14. The ______ layer of the OSI model is responsible for source-to-destination delivery of the entire message.a. transportb. networkc. data-linkd. session15. A ______ is a connecting device that only regenerates the signal.a. repeaterb. bridgec. routerd. gateway16. ______ is a protocol for mail services.a. FTPb. SMTPc. TELNETd. HTTP17. In paging, memory is divided into equally sized sections called _______.a. pagesb. framesc. segmentsd. partitions18. To prevent ______, an operating system can put resource restrictions on processes.a. starvationb. synchronizationc. pagingd. deadlock19. _______ is english like representation of the code.a. A flowchartb. A structure chartc. Pseudocoded. an algorithm20. A process in the ready state goes to the running state when _________.a. it enters memoryb. it gets access to the CPUc. it requests I/Od. it finishes running二、Questions(6 questions, 5 scores for each question)1. What is the formal definition of an algorithm?2. What kinds of states can a process be in?3. What are the three common topologies in LANs? Which is the most popular today?4. What is a bit pattern?5. What are the two major types of searches?6. Name the layers of the TCP/IP protocol suite.三、Calculation(5 subjects, 4 scores for each subject)1. Change the following 8-bit two’s complement numbers to decimal.(1). 10000000 (2). 01100100 (3). 11001000 (4). 11000011 (5).110101012. Change the following decimal numbers to 8-bit two’s complement integers, and then convert the result to hexadecimal.(1). -48 (2). 25 (3). -127 (4). 98 (5). -553. Using an 8-bit allocation, first convert each of the following numbers to two’s complement, do the operation, and then convert the result to hexadecimal.(1) 35+63 (2) 35-63 (3) -35 +63 (4) -35-63 (5) 63-14. Show the result of the following operations, and then convert the result to hexadecimal.(1) NOT 129 (2) 15 AND 10 (3) x55 OR xAA (4) 100 AND 255(5) (xFF XOR xBB) AND (xFF OR xBB)5. A computer has 64MB (megabytes) of memory. Each word is 4 bytes. How many bits are needed to address each single word in memory?四. Analyzing and Design (2 subjects, 10 scores for each subject)1. Using the selection sort algorithm, manually sort the following list and show your work in each pass:12, 6, 78, 31, 50, 46, 99, 2, 20, 442. A list contains the following elements. Using the binary search algorithm, trace the steps followed to find 18. At each step, show the values of first,last and mid.2, 5, 18, 28, 30, 40, 66, 1003. Write a recursive algorithm to find the greatest common divisor(gcd) of two integers using following definition.gcd(x, y)= gcd(y, x) , if x<ygcd(x, y)= x , if y=0gcd(x, y)= gcd(y, x mod y) , otherwise4. Imaging a power plant that pumps water to a city using eight pumps(P8, P7, P6, P5, P4, P3, P2, and P1). The states of the pumps (on or off) can be represented by 8-bit pattern. For example, the pattern 10001111 shows that pumps 1 to 4(from right), and 8 are on (running) while pumps 5, 6, and 7 are off (shut down). How can you shut down all pumps, after two minutes, let the pump P2 and P5 running, and after one hour, shut down the P2 pump and turn on the P6 pump simultaneously, and remain the P5 running too?5. An imaginary computer has sixteen data registers Rx(R0 to R15), 512M words in memory, the address can address words in the 64M words memory, and have 128 different instructions (ADD, SUB, etc.). A typical instruction of the computer uses the following format: ADD address, Rx(1) What is the minimum size of an instruction in bits?(2) If the instruction is in the minimum size and the computer uses the same size of word for data and instructions, what is the size of the data bus?(3) What is the size of the program counter?(4) What is the size of the address bus?(5) What is the minimum size of the control bus?。