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

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

筆試部分

1.

以下哪些圖是樹？如果是樹，請標明它的樹根。

2.

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

3.

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

4.

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

5.

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

6.

解釋為什麼在程式語言中，兩個 bytes 的整數資料形態恰能表達介於 -32768 到 32767 之間 (含兩端) 的所有整數？ (2¹⁵=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)。

上機操作部分

1.

求

在 之間的根，準確到小數點下第四位。

2.

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

3.

考慮遞迴公式 x_n+1 = r x_n(1-x_n)， 其中 0 < x₀ < 1 是初始值、 1<= r <= 3 是個參數。請試驗不同的 x₀ 值和 r 值，並盡量歸納出一些具體而量化的結論。

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 和 N² 之間的整數亂數，每個數一行，一共 N 行。(整數可以重複出現)

• Back to the home page of Wei-Chang Shann.
• Connect to the home page of Department of Mathematics, National Central University, Taiwan.