[开课学院]:资电学院 (ex:金融学院,商学院,理工学院,资电学院,建设学院,文学院...) [开课系所]:资讯 (ex:中文系,外文系,电机系,财税系..) [课程名称]:资料结构 [老师名称]:戴婵玲 老师 [开课学期]:971 [类型]:97-1期中考 ex:(第n次)小考/98-2期中考/98-2期末考 1. 以下的 java 函数 int zero_count(int a[])计算阵列 a 中的 0 有多少个。请采用 表列方式，以 N 的函数写出下列程式片段的步骤计数值(step count)，并以 Big-O notation 写出其时间复杂度。 (15%) (Big O 定义如下：若且为若 f(n) = O(g(n))，则存在大於0的常数 c 与 n0，使得对 所有的 n值， n >= n0 时，f(n) <= cg(n)均成立。) static int zero_count(int a[]) { int count = 0; for (int i=0 ; i < a.length ; i++) /*a.length表示阵列的资料个数 N*/ { if (a[i] == 0) count = count + 1; } return count; } 2. 证明 2+4+8...+2^N = O(2^N) (10%) 3. A为二维的阵列(array)，A[4][2]的位址为1978，A[2][3]的位址为1986，假设每一个 元素占两个的 bytes，则 A 的列数(row)是多少？ (10%) 提示：请先判断阵列是以列序或行序储存。 4. 以阵列定义 stack 的结构如下： (20%) #define MAX_STACK_SIZE 10 typedef struct{ int key; }element; element stack[MAX_DEQUE_SIZE] (a) 写出堆叠的 add_stack. 函数 (b) 写出堆叠的 stack_full 函数 5. 设运算元均为单一字元或数字，运算符号有~,+,-,x,/,(,)，其中~代表负号。关於中 序(intfix)运算式转换成後序(postfix)： (25%) (a) 定义上述运算符号的 ICP(in_coming precedence) 和 ISP(in_stack precedence )。 (b) 规定转换过程中若遇到 precedence相同的符号，则先将堆叠中的符号取出。写出 下列运算式的後序表示法，必须同时写出转换过程用的 STACK 之内容： i. a+bxc/(d/(e-f)+3) ii. (~b+(bx~4xaxc)*(1/2))/(2xa) 6. 阵列(array)与链结串列(linked list)结构均可视为有序串列(ordered list)，请就 存取资料及记忆体配置两方面说明它们有何差异？ (10%) 7. 若五个字元A,B,C,D,E依序输入，利用堆叠来重排其顺序时，写出不可能产生的顺序。 (10%) --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 140.134.237.201 ※ 编辑: MOTG 来自: 140.134.237.201 (03/14 16:33)