試題 3

閱讀下列說明和流程圖，回答問題 1～3 ，把解答寫在答卷的對(duì)應(yīng)欄內(nèi)。

[說明]

流程圖的功能是對(duì)預(yù)處理后的正文進(jìn)行排版輸出。

假定：預(yù)處理后的正文存放在字符串 S 中，S 由連續(xù)的單詞組成，單詞由連續(xù)的英文字母組成。在預(yù)處理過程中已產(chǎn)生以下信息：

變量 NW 存放正文中單詞的個(gè)數(shù)，數(shù)組元素 SL(1)存放正文中第 1 個(gè)單詞在S中的字符位置，SN(1) 存放正文中第 1 個(gè)單詞的長度。規(guī)定 S 中的字符位置從 1 開始計(jì)數(shù)，每個(gè)字符占一個(gè)位置。字符串S中的某個(gè)單詞可用如下的子串形式來存�。�

S( 單詞起始位置：單詞終止位置 )

并規(guī)定在對(duì)字符串( 或子串 )賦值時(shí)，賦值號(hào)兩端的字符串( 或子串 )長度必須相等。

排版輸出的要求如下：

(1)每行輸出 80 個(gè)字符；

(2)一個(gè)單詞不能輸出在兩行中；

(3)除最后一行外，所有輸出行既要左對(duì)齊又要右對(duì)齊。即每行的第一個(gè)字符必須是某個(gè)單詞的第一個(gè)字母，最后一個(gè)字符必須是某個(gè)單詞的最后一個(gè)字母；

(4)單詞之間必須有 1 個(gè)或 1 個(gè)以上的空格；

(5)最后一行只須左對(duì)齊，且單詞之間均只有一個(gè)空格；

(6)使字格盡可能地均勻分布在單詞之間，即同一行中相鄰的單詞間的空格數(shù)最多相差1。

假定正文中至少有兩個(gè)以上單詞，每個(gè)單詞的長度均小于 40。此外，流程圖中省略了數(shù)據(jù)的輸入部分。圖中「W」表示不超過W的最大整數(shù)。

[問題1]

填充流程圖中的 ①～⑥，使之成為完整的流程圖。

[問題2]

圖中的“輸出末行”框未經(jīng)細(xì)化。如果將圖中的虛線部分復(fù)制到“輸出末行”框上，那么復(fù)制部分應(yīng)作怎樣的修改?可用圖中所標(biāo)的 a，b，…，j來回答，例如 a 改成 1→I ：刪除 b。

[問題3]

如將圖中開始部分的 SN(1)→LN 改成 0→LN；2→I 改成 1→I，則修改后的流程圖是否正確。

[流程圖]

試題4

閱讀下列說明和 E—R 圖，回答問題 1～3，把解答寫在答卷的對(duì)應(yīng)欄內(nèi)。

試用 SQL 語言定義教師( TEACHER )模式。回答時(shí)字段的數(shù)據(jù)類型以及題中未指明的名字由考生自己定義。

[說明]

設(shè)有下列關(guān)于教務(wù)管理系統(tǒng)的 E—R 圖。圖中矩形表示實(shí)體，圓表示屬性，雙圓表示關(guān)鍵字屬性，菱形表示實(shí)體間的聯(lián)系。為了答題的方便，圖中的實(shí)體和屬性同時(shí)給出了中英文兩種名字，回答問題時(shí)只須寫出英文名即可。

[問題1]

寫出與上述 E—R 圖對(duì)應(yīng)的關(guān)系模式，并用下劃線標(biāo)明相應(yīng)的關(guān)鍵字。

[問題2]

問題 1 中的關(guān)系模式屬于第幾范式? 如果屬于第三范式，則說明理由；如果不屬于第三范式，則將它化為第三范式( 回答時(shí)只須寫出修改的部分 )。

[問題3]

試用 SQL 語言定義教師( TEACHER )模式�；卮饡r(shí)字段的數(shù)據(jù)類型以及題中未指明的名字由考生自己定義。

[E-R]圖

試題5

閱讀下列說明和流程圖5．3．4—8，回答問題1和2，把解答寫在答卷的對(duì)應(yīng)欄內(nèi)。

[說明]

流程圖對(duì)順序存貯的二叉樹按非遞歸形式進(jìn)行后序遍歷打印。順序存貯的二叉樹存放在數(shù)組 data(1：m) 和 right(1：m)中，data 存放結(jié)點(diǎn)的值，right 存放指針值。

本題中順序存貯的二叉樹是指對(duì)樹中任意兩個(gè)結(jié)點(diǎn) nodel 和 node2 ( 它們?cè)陧樞虼尜A數(shù)組中的下標(biāo)分別為 q₁和q₂)，它們的指針值滿足下列條件：

(1)如果nodel是根結(jié)點(diǎn)，則q₁＝1。如果從nodel出發(fā)按前序遍歷所得到的下一個(gè)結(jié)點(diǎn)是node2，則q₂＝q_l+1。

(2)如果 nodel 的右后件是 node2，則

如果 nodel 存在左后件，則 right(q₁)＝q₂+1；

如果 nodel 不存在左后件，則 right(q₁)＝-(q₂+1)；

(3)如果 nodel 沒有右后件，則

如果 nodel 存在左后件，則 right(q₁)=1

如果 nodel 不存在左后件，則當(dāng) nodel 是按前序遍歷的最后一個(gè)結(jié)點(diǎn)時(shí)，right(q₁)=0；否則right(q₁)=-1。

例如，二叉樹( 下圖 ) 的順序存貯情況如右下表。

流程圖中 stack(1：N) 是遍歷過程中存放順序存貯數(shù)組下標(biāo)的棧，sign·(1：N) 是配合棧操作設(shè)立的標(biāo)志位( 第一次進(jìn)棧時(shí)值為1，第二次進(jìn)棧時(shí)值為2 )，變量 top 是棧頂指針，變量 first 是順序存貯二叉樹的首指針。若樹空，則 first＝0；否則，first＝1。指針 pointer 用來指出結(jié)點(diǎn)在數(shù)組中的下標(biāo)。

假定給出的順序存貯二叉樹是正確的，且 stack 和 sign 都足夠大，不會(huì)溢出。

[問題1]

填充流程圖中的①～⑤，使之成為完整的流程圖。

{問題2]

將流程圖中的“打印 data( pointer )”框移至⑤處，則流程圖執(zhí)行的結(jié)果是什么?

[流程圖]