Questions 65- 66 refer to the space requirements of different methods of storing graphs. The choices for these questions are combinations of the following statements.

　?、? The space required depends on the number of vertices.

　?、? The space required depends on the number of edges.

　　(65) When the adjacency matrix method is used to store a graph, which of the statements is (are) true?

　　A) None B) Ⅰ only C) Ⅱ only D) Ⅰ and Ⅱ

　　(66) When the adjacency list method is used to store a graph, which of the statements is (are) true?

　　A) None B) Ⅰ only C) Ⅱ only D) Ⅰ and Ⅱ

　　Questions 67-68 are based on the following information,

　　A hash table with hash function

　　h1(k)=k mod 13

　　is shown below.

　　0 1 2 3 4 5 6 7 8 9 10 11 12

　　35 33 48 25

　　Collision is resolved using the hash function h2(k)=(k mod 11)+1.

　　(67) How many key comparisons occur in searching for key 35 in the given hash table? (2分)

　　A) 0 B) 1 C) 2 D) 3

　　(68)& If a new key 67 is inserted into the given hash table, what will be its address? (2分)

　　A) 3 B) 4 C) 5 D) 6

　　(69) Suppose the contents of the DOS IF1.BAT file on the hard disk is as follows.

　　@ECHO OFF

　　MEM>FILE1

　　SORTFILE2

　　DEL FILE1

　　@DATE

　　@TIME

　　IF EXIST %1 ECHO % IF FOUND

　　If all of the commands are successfully executed after IF1 FILE1 is

　　typed, then the screen displays?

　　A) None B) Date and time C) FILE1 IS FOUND D) FILE2 IS FOUND

　　(70) If the files in the current directory are

　　aac, abc, acb,acc, aca, ao, al, a2, ab, ac, aa,

　　and the command ls a?[bc] is executed, how many files will be listed?

　　(2分)

　　A) 3 B) 4 C) 5 D) 6

　　(71) In order to append a standard output to an existing file, which of the following operators is used in the UNIX system?

　　A) | B) & C) > D) >>

　　(72) Consider the following figure, where the shaded parts represent already assigned blocks of memory, and the unshaded parts represent free blocks. (2分) If there is a request for 40KB of memory and the best-fit algorithm is used, then the beginning address of memory that is allocated in response to the request is

　　A) 100KB B) 190KB C) 330KB D) 410KB

　　(73) On a certain disk, there are 200 tracks, numbered 0-199, the current position of the disk head is track 53. If the shortest-seek-time-first scheduling algorithm is used when the tracks

　　98, 183, 37, 122, 14, 124, 65, 67

　　are requested, then the head-moving sequence that results will be (2分)

　　A) 65, 67, 37, 14, 98, 122, 124, 183

　　B) 65, 67, 37, 98, 122, 124, 183, 14

　　C) 65, 67, 98, 122, 124, 183, 37, 14

　　D) 98, 183, 37, 122, 14, 124, 65, 67

　　(74) Whant operation on relations R and S produces the relation shown below?

　　{tuple│tuple∈R۸tuple∈\ S}

　　A) Union B) Difference C) Intersection D) Division

　　(75) When embedding SQL in a C language program, the prefix that should be added to all SQL statements in order to distinguish SQL statements from the host language statements is

　　A) ： B) EXEC C) EXEC SQL D) SQL

　　(76) In the ORACLE system,sets of SQL statements and control flow statements that have been named,compiled,and stored tn the database are referred to as stored

　　A) batches B) procedures C) triggers D) transactions

　　(77) Which of the following statements about object oriented databases is NOT correct? (2分)

　　A) Each object has a unique object identity in the system.

　　B) Encapsulation and inheritance are two important features of object oriented databases.

　　C) A subclass can inherit the attributes and methods of all its superclasses.

　　D) A superclass includes the attributes and methods of all its subclasses.

　　(78) In the design phase of software engineering, decomposition of the program into modules should follow the principles of

　　A) low cohesion with low corpling B) low cohesion with high coupling

　　C) high cohesion with low coupling D) high cohesion with high coupling

　　(79) Specifications for software should contain&nbs p;several components, e.g., specifications of

　　information flow,

　　user interface,

　　functional requirements, and

　　design constraints.

　　Two other important components are specifications of the (2分)

　　A) methods of testing and ways to obtain quality assurance

　　B) criteria for testing and ways to obtain quality assurance

　　C) methods of testing and criteria for function assurane

　　D) criteria for testing and methods of function assurance

　　(80) Which of the following statements about testing software with data is (are) true?

　　I. The primary purpose of such testing is to find errors.

　　II. Such testing can demonstrate the existence of errors but cannot

　　demonstrate the absence of errors.

　　A) Neither B) Ⅰ only C) Ⅱ only D) Ⅰ and Ⅱ

　　(81) The type of testing done during software implementation and beforemodule integration is called

　　A) unit testing B) beta testing

　　C) system testing D) acceptance testing

　　(82) Which of the following is (are) true about software portability?

　　I. Using a high-level language that conforms to an ISO standardguarantees portability across the range of machines that support the language.

　　II. Portability is guaranteed across all machines that have the same instruction set and operating system. (2分)

　　A) Neither B) Ⅰ only C) Ⅱ only D) Ⅰ and Ⅱ

　　(83) A memory-memory, machine instruction for a certain machine has the following format.

　　(Such an instruction is similar to a register-register instruction

　　except that the operands are displaced addresses in memory.)

　　opcode meml displ1 mem2 displ2

　　Which of the following could be an assembly lanuage instruction that would be translated into a memory-to-memory instruction for this machine?

　　A) ADD 10(R1), 20(R2) B) ADD(10R1), (20R2)

　　C) ADD R1, 10(R2), 20 D) ADD R1, 10, 20(R2)

　　(84) In a certain cache system, the modified cache block is written to main memory only when the block is replaced. All of the following are used to describe this policy EXCEPT

　　A) store-in B) write-back C) copy-back D) write-through

　　(85) When an amount of memory is requested that is less than the size of a page, but a full page is allocated, the r esulting waste of memory is called

　　A) external fragmentation B) internal fragmentation

　　C) inaccessible page faults D) inaccessible garbage

　　(86) The time that the CPU spends on a given program can be computed using all of the following expressions EXCEPT (2分)

　　A) (CPU clock cycles for the program)*(clock cycle time)

　　B) CPU clock cycles for the program

　　clock rate

　　C) (Instruction count)*CPI

　　clock rate

　　D) (CPU clock cycles for the program)*CPI

　　clock rate

　　(87) The methods used in Asynchronous Transfer Mode (ATM) are switch technology and which of the following is used to describe this mode?

　　A) cell exchange B) packet exchange

　　C) message exchange D) information exchange

　　(88) In a data communication system, the transport media with the widest frequency band and best reliability is the

　　A) telephone line B) coaxial cable

　　C) radio channel D) fiber optic cable

　　(89) Which of the following statements about the Internet is (are) true?

　　I. It is possible to have multiple names corresponding to the same IP address. II. All host names must be registered with an Internet-wide central registry.

　　A) Neither B) Ⅰ only C) Ⅱ only D) Ⅰ and Ⅱ

　　(90) According to the principle of CRC calculation, given a frame-bit series M =11100111 and the multiple-term formula, frame-bit series generated by the CRC G =110011, then the CRC is (2分)

　　A) 111101 B) 00011 C) 11010011 D) 1101001

　　二、論述題(兩個(gè)論述題可任選其一,并只選其一,多選無(wú)效,滿(mǎn)分30分。)

　　論述題 1

　　局域網(wǎng)是當(dāng)前計(jì)算機(jī)網(wǎng)絡(luò)研究與應(yīng)用的一個(gè)熱點(diǎn),而符合IEEE 802.3標(biāo)準(zhǔn)的傳統(tǒng)Ethenet(MAC層采用CSMA/CD方法,物理層采用 10BASE-T標(biāo)準(zhǔn))應(yīng)用最為廣泛。隨著網(wǎng)絡(luò)應(yīng)用的發(fā)展,以及大型信息系統(tǒng)與多媒體技術(shù)的應(yīng)用,人們對(duì)局域網(wǎng)性能提出了越來(lái)越高的要求,出現(xiàn)了符合 100BASE-T標(biāo)準(zhǔn)的Fast Ethernet、交換局域網(wǎng)Switching LAN與ATM等高速局域網(wǎng)產(chǎn)品。盡管高速局域網(wǎng)技術(shù)發(fā)展十分迅速,但是Ethernet仍然會(huì)被廣泛地使用。今后的網(wǎng)絡(luò)應(yīng)該是傳統(tǒng)Ethernet、FastEthernet LAN與ATM共存的結(jié)構(gòu)。因此,研究 Ethernet的基本工作原理、優(yōu)點(diǎn)與缺點(diǎn),討論高速局域網(wǎng)絡(luò)發(fā)展的趨勢(shì)與特點(diǎn),對(duì)我們學(xué)習(xí)和掌握局域網(wǎng)應(yīng)用技術(shù)是十分重要的。

　　(1) 請(qǐng)用Ethernet發(fā)送與接收流程框圖說(shuō)明CSMA/CD介質(zhì)訪問(wèn)控制方法的基本工作原理。(15分)

　　(2) 為什么說(shuō)CSMA/CD屬于共享介質(zhì)、隨機(jī)爭(zhēng)用型的介質(zhì)訪問(wèn)控制方法?這種方法主要缺點(diǎn)是什么? (5分)

　　(3) 你認(rèn)為Fast Ethernet與ATM、Switching LAN是從哪兩個(gè)方面改進(jìn)了傳統(tǒng)的Ethernet?它們各有什么優(yōu)缺點(diǎn)? (10分)

　　論述題 2

　　進(jìn)程通信就是進(jìn)程之間進(jìn)行信息交換。系統(tǒng)中各進(jìn)程異步執(zhí)行,但有些進(jìn)程之間必須保持一定的聯(lián)系,以便協(xié)調(diào)一致地完成指定任務(wù)。這種聯(lián)系就是通過(guò)交換一定數(shù)量的信息來(lái)實(shí)現(xiàn)的。

　　消息緩沖通信技術(shù)是一種高級(jí)通信機(jī)制,由Hansen首先提出。其基本思想是:根據(jù)"生產(chǎn)者-消費(fèi)者關(guān)系"原理,利用公共消息緩沖區(qū)實(shí)現(xiàn)進(jìn)程之間的信息交換。

　　(1) 試敘述高級(jí)通信機(jī)制與低級(jí)通信機(jī)制P、V原語(yǔ)操作的主要區(qū)別。(5分)

　　(2) 試敘述解釋消息緩沖通信技術(shù)的基本原理。 (10分)

　　(3) 消息緩沖通信機(jī)制中提供發(fā)送消息原語(yǔ)。Send(receiver,a)和接收消息原語(yǔ)Receive(a)。調(diào)用參數(shù)a分別表示發(fā)送消息的內(nèi)存區(qū)首地址或接收進(jìn)程的內(nèi)存消息區(qū)首地址。試設(shè)計(jì)相應(yīng)的數(shù)據(jù)結(jié)構(gòu),并用P、V操作原語(yǔ)實(shí)現(xiàn)Send和Receive原語(yǔ)。 (15分)