計算機概論二期末考@June 23, 1999

共分兩部分。一部分筆試,另一部分上機測驗。每部分考試時間 50 分鐘

筆試部分

1.
以下哪些圖是樹?如果是樹,請標明它的樹根。

2.
比較循序搜尋和二分搜尋的強處和限制。

3.
在執行方式上, Perl 程式語言是經由編譯器還是直譯器轉換成機器語言? 在應用範疇上,Perl 程式語言的主要用途是屬於科學計算、商務處理、人工智慧、 還是系統管理? 在抽象化的程度上,Perl 程式語言屬於組合語言、高階語言、超高階程式語言、 還是巨集 (macro) 語言?

4.
試論述主從型 (client-server) 與分散型 (distributed) 資料庫的異同。

5.
找出一種由正整數 1, 2, 3, ..., N 排列而成的序列, 這種序列造成氣泡排序法的最差狀況。 並計算這種狀況下採用氣泡排序法總共需要交換多少次?

6.
解釋為什麼在程式語言中,兩個 bytes 的整數資料形態恰能表達介於 -32768 到 32767 之間 (含兩端) 的所有整數? (215=32768$)

7.
試解釋以下 SQL 語句的意義。
	    CREATE TABLE Course
		(CNUM     CHAR(5)        NOT NULL,
		 CNAME    VARCHAR(30)    NOT NULL,
		 TNAME    VARCHAR(8)     NOT NULL,
		 CREDIT   INT,
		 ROOM     CHAR(5),
		 PRIMARY KEY (CNUM));

8.
畫出以下程式的流程圖 (flow chart)。
	    #!/bin/perl -w
	    print "Input a positive integer: ";
	    chomp($n = <>);
	    $b = '';
	    while ($n > 0) {
		if ($n % 2) {
		    $b = '1'.$b;
		    $n = ($n-1)/2;
		}
		else {
		    $b = '0'.$b;
		    $n /= 2;
		}
	    }
	    print "$b\n";

9.
試找出以下加權無向圖 (weighted undirected graph) 的最小擴展樹 (minimal spanning tree)。

上機操作部分

以下三題使用 Matlab

1.
之間的根,準確到小數點下第四位。

2.
x 是一個維度 n 的向量,s 是一個常數。 寫一段程式,將 x 中數值大於 s 的元素全部變成 s, 而保留其他的元素不動。

3.
考慮遞迴公式 xn+1 = r xn(1-xn), 其中 0 < x0 < 1 是初始值、 1<= r <= 3 是個參數。請試驗不同的 x0 值和 r 值,並盡量歸納出一些具體而量化的結論。
以下二題使用 Perl

4.
寫一個程式,要求使用者輸入一個二進位表達的正整數,就說是 n。 然後輸出 n 的十進位數目字。

5.
在 Perl 中有一個函數 rand() 每呼叫一次會產生一個介於 0 和 1 之間的浮點數亂數 $t。您可以利用以下程式來測試。
	    #!/usr/bin/perl -w
	    for ($i=0; $i<10; $i++) {
		$t = rand();
		print "$t\n"; }
利用函數 rand() 寫一個程式,由使用者輸入一個正整數, 就說是 N,此程式輸出 N 個介於 0 和 N2 之間的整數亂數,每個數一行,一共 N 行。(整數可以重複出現)

Created: Jun 24, 1999
Last Revised: Jun 24, 1999
© Copyright 1999 Wei-Chang Shann

shann@math.ncu.edu.tw