Title FE Exam Preparation Book VOL1 Limite Binary Coded Decimal Array Data Structure Bit Decimal Databases 2.8 MB 448
```                            VOL1_00_Cover_LimitedDisclosureVersion.pdf
VOL1_01_Index.pdf
VOL1_02_Part1_Chapter1.pdf
VOL1_02_Part1_Chapter2.pdf
VOL1_02_Part1_Chapter3.pdf
VOL1_02_Part1_Chapter4.pdf
VOL1_02_Part1_Chapter5.pdf
VOL1_02_Part1_Chapter6.pdf
VOL1_02_Part1_Chapter7.pdf
VOL1_03_Part2_TrialExam_Morning_.pdf
VOL1_04_Part2_TrialExam_Afternoon_.pdf
VOL1_99_Colophon.pdf
```
##### Document Text Contents
Page 1

FE Exam
Preparation Book

Preparation Book for Fundamental Information Technology Engineer Examination

Vol.1

Information-Technology Promotion Agency, Japan

Part1: Preparation for Morning Exam
Part2: Trial Exam Set

Limited Disclosure
Version

Page 2

i

FE Exam Preparation Book

Part 1 PREPARATION FOR MORNING EXAM

Chapter 1

Computer Science Fundamentals 2

1.1 Basic Theory of Information 3
1.1.2 Numerical Representations 7
1.1.3 Non-Numerical Representations 10
1.1.4 Operations and Accuracy 11
Quiz 14

1.2 Information and Logic 15
1.2.1 Logical Operations 15
1.2.2 BNF 18
1.2.3 Reverse Polish Notation 21
Quiz 24

1.3 Data Structures 25
1.3.1 Arrays 25
1.3.2 Lists 27
1.3.3 Stacks 29
1.3.4 Queues (Waiting lists) 30
1.3.5 Trees 32
1.3.6 Hash 34
Quiz 37

1.4 Algorithms 38
1.4.1 Search Algorithms 38
1.4.2 Sorting Algorithms 41
1.4.3 String Search Algorithms 45
1.4.4 Graph Algorithms 48
Quiz 50

Vol. 1

Page 224

5. Database Technology

FE Exam Preparation Book Vol.1

-- Part1. Preparation For Morning Exam --
218

Below is an E-R diagram showing a many-to-many relation.

Company Shareholder

Here, the double arrow indicates a many-to-many relation between “Company” and
“Shareholder.” This suggests that a shareholder may hold shares of multiple companies and that
a company may have multiple shareholders. In other words, we can interpret this figure as
follows: “There are multiple companies, each of which has multiple shareholders.”

5.1.4 Normalization and Reference Constraints

Points Normalization means eliminating data redundancy. There are first, second, and third normal forms.

Normalization (data normalization) means to maintain the consistency and integrity of data by
eliminating redundant data. There are first normal forms, second normal forms, and third
normal forms. Normalization is a concept that is used only for relational databases. The
mainstream databases used today are relational databases, so normalization is an extremely
important theme.

Non-normal Form
A non-normal form is a form in which items are simply listed. In general, repeated items are
also included. In the figure below, the combination (ProductNumber, Quantity, UnitPrice) is
repeated. In the following explanations, the underlined items indicate the primary keys. Here,
the fact that the InvoiceNumber is used as the primary key assumes that there is no duplication
of the InvoiceNumber.14

Product information (1) Product information (2)

Invoice
Number

Customer
Number

Customer
Name

Product
Number Quantity

Unit
Price

Product
Number Quantity

Unit
Price

14 (Hints & Tips) There cannot be two records whose primary key values are the same. In this example of the non-normal
form, since the InvoiceNumber is the primary key, there are no duplicate InvoiceNumbers.

Share-holding

Page 225

5. Database Technology

FE Exam Preparation Book Vol.1

-- Part1. Preparation For Morning Exam --
219

First Normal Form
A first normal form has no repeated items in the table. To convert a non-normal form into a
first normal form, we separate the combination “ProductNumber, Quantity, UnitPrice” in the
non-normal form. Then, it is possible that there are multiple records in which “InvoiceNumber,
CustomerNumber, CustomerName” are all the same but “product information” is different, so
“InvoiceNumber” by itself cannot be the primary key. Hence, we include “ProductNumber”
also, and we may use both of these items together as the primary keys.

In the example of the non-normal form above, there is repetition, so the first normal form has
only two records as shown below.

If there are multiple pieces of
product information, the same
contents may be repeated.

There should be only one piece of
product information.

Invoice
Number

Customer
Number

Customer
Name

Product
Number Quantity

Unit
Price

Second Normal Form
In the first normal form, the two items “InvoiceNnumber” and “ProductNumber” are together
used as the primary keys. In databases, all non-key attributes must be functionally dependent
on the entire primary key.15 However, the item “UnitPrice” is not related to “InvoiceNumber.”
The item “UnitPrice” is determined only by “ProductNumber.” Hence, we now separate
“UnitPrice”; in doing so, since “ProductNumber” and “UnitPrice” need to be in correspondence,
we use “ProductNumber” as the primary key. Further, “CustomerNumber” can be determined
uniquely if “InvoiceNumber” is selected, so “ProductNumber” is unnecessary. Yet, to
determine “Quantity,” we must have “InvoiceNumber” and “ProductNumber.” For later
explanations, we name these new tables “Invoice_table,” “Detail_table,” and “Product_table.”
The result of separating the data into these three tables is called a second normal form.16

Invoice
Number

Customer
Number

Customer
Name

Product
Number Quantity

Unit
Price

Invoice
Number

Customer
Number

Customer
Name

Invoice
Number

Product
Number Quantity

Product
Number

Unit
Price

(Invoice_table) (Detail_table) (Product_table)

15 (Note) Dependency on the primary key means that each item can be identified by the values of the primary key.
16 Complete functional dependency/ Partial functional dependency: In the first normal form, “Quantity” is determined
for the entire primary key “InvoiceNumber + ProductNumber.” As seen in this example, the dependency on the entire
combination of primary-key items is called complete functional dependence. The unit price, on the other hand, depends only
on one of the primary keys (in this example, on “ProductNnumber”); When an item is determined by one of the primary keys,
we call it partial functional dependency.
Strictly speaking, a second normal form can be defined as “a first form in which all non-key items are in complete functional
dependence.”

Page 447

FE(Afternoon) Trial

FE Exam Preparation Book Vol.1
-- Part2. Trial Exam Set --

441

Incidentally, an anonymous class is used in various situations, such as when we take an existing
class or interface, modify it partially to create a new class, and wish to use the new class locally
within a class. In such a case, packaging and inheriting take place without “extends” or
“implements” key words.

C:
Blank C corresponds to the argument used when the instance “event” is generated when the
input value is 0 through 9. The argument is delivered, considering cases like = and +, and the first
argument is CalculatorEvent.DIGIT. For the second argument, the program can simply
deliver the number entered, but the characters “0” through “9” need to be converted to numbers 0
through 9. When characters “0” through “9” correspond to 0x30 through 0x39 in hexadecimal
numbers, conversion to numerical values can be accomplished simply by subtracting the
hexadecimal number 0x30. Therefore, what needs to be inserted to blank C is
“CalculatorEvent.DIGIT, c - ‘0’.”

Subquestion2 : [Correct Answer] D – a, E – d, F – i

D:
This is the case where the input is the character string “3*4***=”. When the multiplication key is
entered multiple times consecutively, the next statement after displaying the operation result
executes “register = 0;”, setting the variable that retains the result (“register”) to 0.
Hence, even if the equal key is pressed in the end, the display result remains 0.

E:
At the time “3*4 =” is entered, both the display and the value of the variable “accumulator”
are 12. When “+5” follows, the value displayed in the end is the last input value “5.” This is
because “register” becomes 0 when the equal sign is pressed. With “register” 0, until another
number is added to the input value 5, the display shows “5.” Hence, the display result is “5.”

F:
At the time “3 + 4 / 0” is entered, “accumulator” contains 7, which is the result of the
calculation “3 + 4”, while “register” stores the last input value 0. Then, when the last equal
key is pressed, division by 0 occurs, triggering the exception processing
“ArithmeticException”. Hence, “Error” is displayed.

Page 448

FE Exam Preparation Book Vol.1
Part 1: Preparation for Morning Exam
Part 2: Trial Exam Set

First Edition: January, 2008

The product names appearing in this book are trademarks or registered trademarks of the

respective manufactures.

This book, prepared by Information-Technology Promotion Agency, Japan (IPA) with

approval, is a modified, English translation of the books written by Tetsuro Hidaka and