※ [本文转录自 NTU-Exam 看板 #1BTZ7xFP ] 作者: andy74139 (月^4) 看板: NTU-Exam 标题: [试题] 98上 周承复 计算机概论 期末考 时间: Sat Feb 13 13:00:41 2010 课程名称︰ 计算机概论 课程性质︰ 必修 课程教师︰ 周承复 开课学院： 电机资讯学院 开课系所︰ 资讯工程学系 考试日期（年月日）︰ 2010/01/09 考试时限（分钟）： 100分钟 是否需发放奖励金： 是 （如未明确表示，则不予发放） 试题 : 1. (20%) Security a) (5%) Distinguish between symmetric-key and asymmetric-key cryptography b) (5%) List the security services provided by a digital signature c) (5%) Alice often needs to encipher plaintext written in lowercase letter (a to z). If she uses a shift cipher, what is the range of keys from which she can select. (Remember that the ciphertext would be composed of the lowercase letters.) d) (5%) In a simple transposition cipher, what is the maximum number of characters that will be changed in the ciphertext if only a single character is changed in the plaintext? 2. (30%) Programming Language a) (10%) Draw the parse tree for the expression ｘ－ｙ✕ｚ＋ｙ✕ｘ based on the syntax diagrams in Figure 1? Figure 1: http://w.csie.org/~b97902133/CS/ntuexam_CS_F1.png b) (10%) Briefly describe the task of each of the following. (a) Lexical analyzer, (b) Parser, and (c) Code Generator c) (5%) The following is a program segment and the definition of a procedure named sub. ． procedure sub ． ． X ← 8; ． apply procedure sub; X ← 2; print the value of X; ． ． ． ． What value will be printed by the program segment if X is a global variable? What value will be printed by the program segment if X is a declared as a local variable within the procedure? d) (5%) What does it mean to say that a programming language is strongly typed? 3. (30%) Software Engineering a) (10%) What is the difference between coupling and cohesion? Which should be minimized and which should be maximized? Why? b) (10%) Describe (a) the data coupling, and (b) the control coupling, which are represented by the following structure chart. ┌──┐ │ Ａ │ └──┘ ╱│＼ w↗╱ │ ＼＼w ╱╱ │ ＼↘ ↙ ↓ ↘ ┌──┐ ┌──┐ ┌──┐ │ Ｂ │ │ Ｃ │ │ Ｄ │ └──┘ └──┘ └──┘ ＼ │ ＼ ││w ＼ │↓ ↘ ↓ ┌──┐ │ Ｅ │ └──┘ c) (10%) In each case below indicate whether the activity relates to glass-box testing or black-box testing. (i) Testing to see if the system performs in a timely manner (ii) Designing test data to ensure that each instruction is executed at least once (iii) Testing to see if the software system meets the requirements identified during original analysis 4. (30%) Data Structure a) (5%) Suppose the expression X[1,1] referred to the first-row, first-column entry in a two-dimensional array with 5 rows and 7 columns. If the array is stored in row-major order beginning at memory address x and each entry in the array requires n memory cells, what address polynomial would be used to compute the address of the biginning of the entry X[I,J]? b) (5%) Suppose the expression X[0,0] referred to the first-row, first-column entry in a two-dimensional array with 5 rows and 7 columns. If the array is stored in column-major order beginning at memory address x and each entry in the array requires n memory cells, what address polynomial would be used to compute the address of the beginning of the entry X[I,J]? c) (5%) What sequence of nodes from the tree Ａ ／ ＼ Ｂ Ｃ ／ ＼ ／ ＼ Ｄ Ｅ Ｆ Ｇ would be printed if the follwing recursive procedure were applied to it? procedure printTree (Tree) if (Tree is not empty) then (print the root of Tree; apply the procedure printTree to the right subtree of Tree) d) (5%) If the longest path in a binary tree contains five nodes, what is the maximum number of terminal nodes that could be in the tree? e) (10%) The following represents a portion of a computer's main memory. Address Contents 50 51 51 56 52 53 53 57 54 58 55 50 56 57 57 52 58 53 (i) What would be stored at address 50 after executing the instruction "Copy the contents of the memory cell at address 54 to address 50"? (ii) What would be stored at address 50 after executing the instruction "Copy the contents of the memory cell pointed to by the cell at address 54 to address 50"? 5. (20%) DataBase a) (10%) Given the relation Parts containing the attributes PartName, PartNumber, and SupplierID as well as the relation Suppliers containing the attributes SupplierID, Address, FaxNumber, write a sequence of SELECT, PROJECT, and JOIN operations to obtain the supplier identifications and fax numbers for all the suppliers that supply the part whose part number is X4J26. b) (5%) Describe the distinction between class description and cluster analysis. c) (5%) Which structures are designed to provide efficient access to randomly chosen items：(a) sequential file, (b) indexed file, (c) hash file, (d) hash table (multiple choice) ※ 编辑: cchao28 来自: 140.112.239.109 (01/02 12:38)