試題 3

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

[說明]

流程圖的功能是對預處理后的正文進行排版輸出。

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

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

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

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

排版輸出的要求如下：

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

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

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

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

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

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

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

[問題1]

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

[問題2]

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

[問題3]

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

[流程圖]

試題4

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

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

[說明]

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

[問題1]

寫出與上述 E—R 圖對應的關系模式，并用下劃線標明相應的關鍵字。

[問題2]

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

[問題3]

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

[E-R]圖

試題5

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

[說明]

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

本題中順序存貯的二叉樹是指對樹中任意兩個結點 nodel 和 node2 ( 它們在順序存貯數(shù)組中的下標分別為 q₁和q₂)，它們的指針值滿足下列條件：

(1)如果nodel是根結點，則q₁＝1。如果從nodel出發(fā)按前序遍歷所得到的下一個結點是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 不存在左后件，則當 nodel 是按前序遍歷的最后一個結點時，right(q₁)=0；否則right(q₁)=-1。

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

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

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

[問題1]

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

{問題2]

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

[流程圖]