Medan string biasa akan dengan senang hati menyimpan hal yang tidak masuk akal. Minta jenis kendaraan, lalu seseorang mengetik Pisang — program menerimanya tanpa protes. Namun jika Anda…
English narration · English + 中文 subtitles burned in · Narasi bahasa Inggris · Subtitle bahasa Inggris + 中文 disematkan langsung
13.1
User-defined data types · Tipe data yang didefinisikan pengguna
Syllabus · Silabus
English
Candidates should be able to:
Notes and guidance
Show understanding of why user-defined types are necessary
Define and use non-composite types
Including enumerated, pointer
Define and use composite data types
Including set, record and class/object
Choose and design an appropriate user-defined data type for a given problem
Bahasa Indonesia
Kandidat harus mampu:
Catatan dan panduan
Tunjukkan pemahaman mengapa tipe yang didefinisikan pengguna diperlukan
Definisikan dan gunakan tipe non-komposit
Termasuk terurut, penunjuk
Definisikan dan gunakan tipe data komposit
Termasuk himpunan, rekaman dan kelas/objek
Pilih dan rancang tipe data yang didefinisikan pengguna yang sesuai untuk masalah yang diberikan
Source: Cambridge International syllabus · Sumber: Silabus Cambridge International
English
The built-in types (INTEGER, REAL, STRING, CHAR, BOOLEAN) cover the simplest cases. For richer problems you can define user-defined types 用户定义类型, making the code clearer and the compiler stricter.
Why they are needed
A built-in STRING lets you store nonsense in a field that should hold one of a few legal values; a user-defined type can restrict it. Real entities are usually a collection of values of different types. And DECLARE Taxi : Vehicle is clearer (self-documenting) than DECLARE Taxi : STRING.
"Describe the purpose of a user-defined data type" (two marks).A data type defined by the programmer, built from existing (built-in) types, so that data specific to the problem can be represented when no built-in type fits. Both halves score: defined by the programmer and based on existing types. The examiner also accepts "to make the program easier to read and maintain" as a supporting point, never on its own.
"Explain what is meant by non-composite and composite data types" (four marks). A non-composite type is defined without reference to another type: it holds a single value, for example an integer, a real, or an enumerated value. A composite type is a collection of other types (which may themselves be composite): it holds several values under one identifier, for example a record, a set, an array or a class. Give an example with each definition; the exam asks for one.
Non-composite types
Enumerated type
An enumerated type 枚举类型 has values that are a fixed list of named constants:
The names are values of the new type (stored internally as small integers); you cannot assign anything outside the list. Uses: days of the week, colours, status codes.
"State what is meant by an enumerated data type."A non-composite user-defined type defined by listing all its possible values (in order). Because the values are ordered, they can be compared and stepped through: with TYPE Month = (January, February, ..., December), the test IF ThisMonth > June is legal, and the values are stored internally as integers. The pseudocode has three parts and the exam marks each: the keyword TYPE, the identifier with =, and the list in brackets separated by commas.
Worked example. Write pseudocode to define an enumerated type for the days on which a school is open (Monday to Friday), and declare a variable of that type set to Wednesday.
A variable of an enumerated type cannot be given a value outside the list, which is the whole point: Today ← Saturday is a compile-time error, whereas a STRING would have accepted "Saturdy".
Pointer type
A pointer 指针 holds the memory address of another variable (or NULL for "no target"). Pointers build dynamic structures (linked lists, trees) and pass references without copying.
To dereference 解引用 (p^) means to reach the variable it points to.
"State what is meant by a pointer data type."A non-composite type whose value is the memory address of (a reference to) a variable of a given type. The pseudocode declares the type with a caret before the type it points to, and the exam asks for exactly that line:
Pointers are what a dynamic linked list or binary tree (Topic 19) is built from: each node holds a pointer to the next. Two marks are commonly lost here: writing the pointer type as if it held the value itself, and forgetting the caret when reading through the pointer.
Composite types
A composite type 复合类型 (one of the composite data types) groups several values under one name.
record 记录 (Topic 10) — fields of different types in a TYPE ... ENDTYPE block.
set 集合 — an unordered collection of unique values, with operations add, remove, membership test, union, intersection:
class 类 / object 对象 — the OOP composite type, combining data fields (attributes 属性) with operations on them (methods 方法). An object is an instance of a class:
Choosing a type
Use enumerated for a value from a fixed list, pointer for indirection, record for a group of fields, set for an unordered unique collection, and class when you need state and behaviour together.
"Describe the user-defined data type set" (three marks).A composite type that holds a collection of values of the same type, in no particular order and with no duplicates; values can be added and removed, and a value can be tested for membership. Declare the type with SET OF, then define a set constant with its values in brackets:
"Describe the user-defined data type record" (three marks).A composite type made up of a fixed number of fields (items), each with its own identifier and its own type, referred to under a single identifier; the fields are accessed with dot notation.
Worked example. Write pseudocode to declare a record type ClubMember for a club member's first name, last name, membership code (an integer), date of joining and whether fees have been paid; then declare a variable and set two of its fields.
Every field needs its own DECLARE line with an appropriate type, the block ends with ENDTYPE, and a field 字段 is reached as variable.field. Asked to choose a type for each field, match it to the data: a code that is only ever compared is a STRING if it can contain letters, an INTEGER if arithmetic or ordering is needed; a yes/no is BOOLEAN; a date is DATE. A field that can take one of a few named values (a pet's species, a colour) is the one to make an enumerated type.
Records in arrays and files. A table of many members is DECLARE Members : ARRAY[1:100] OF ClubMember; then Members[3].LastName is one field of one element, and a loop over the index processes every record. A record is also the natural unit written to and read from a file (below), one record per PUTRECORD or WRITEFILE.
Worked example. A composite type Pet stores each pet's name (string), species (one of dog, cat, rabbit or hamster) and weight in kilograms (real). Define the types and declare a variable.
The enumerated type is defined first, because the record uses it: order matters in pseudocode as it does in a compiler.
Classes in pseudocode. A class is the composite type that also carries behaviour. The exam asks for the declaration with its attributes marked PRIVATE, a constructor 构造函数 named NEW that sets them, and PUBLIC methods to get or change them:
Attributes are private so that they can only be changed through methods (encapsulation, Topic 20); the constructor is a procedure called NEW with one parameter per attribute; a getter is a function that returns the attribute. Each of these is a separate mark.
Bahasa Indonesia
Tipe bawaan (INTEGER, REAL, STRING, CHAR, BOOLEAN) mencakup kasus paling sederhana. Untuk masalah yang lebih kompleks, Anda dapat mendefinisikan tipe yang didefinisikan pengguna, membuat kode lebih jelas dan compiler lebih ketat.
Mengapa tipe ini diperlukan
Sebuah STRING bawaan memungkinkan Anda menyimpan data tak bermakna di dalam sebuah field yang seharusnya berisi salah satu dari beberapa nilai sah; tipe yang didefinisikan pengguna dapat membatasinya. Entitas nyata biasanya merupakan kumpulan nilai dari berbagai tipe. Dan DECLARE Taxi : Vehicle lebih jelas (mandiri menjelaskan) daripada DECLARE Taxi : STRING.
"Jelaskan tujuan dari tipe data yang didefinisikan pengguna (dua nilai).** Tipe data yang didefinisikan oleh programmer, dibangun dari tipe yang sudah ada (bawaan), sehingga data spesifik dari masalah dapat direpresentasikan ketika tidak ada tipe bawaan yang cocok. Kedua bagian bernilai: didefinisikan oleh programmer dan berdasarkan pada tipe yang sudah ada. Penguji juga menerima "untuk memudahkan pembacaan dan pemeliharaan program" sebagai poin pendukung, namun tidak bisa berdiri sendiri.
"Jelaskan apa yang dimaksud dengan tipe data non-komposit dan komposit" (empat nilai). Tipe non-komposit didefinisikan tanpa merujuk pada tipe lain: ia menyimpan satu nilai tunggal, misalnya bilangan bulat, bilangan riil, atau nilai terenumerasi. Tipe komposit adalah kumpulan tipe lain (yang mungkin sendiri merupakan komposit): ia menyimpan beberapa nilai di bawah satu pengenal, misalnya rekaman, himpunan, array, atau kelas. Berikan contoh untuk setiap definisi; ujian meminta satu.
Tipe non-komposit
Tipe terenumerasi
Tipe terenumerasi memiliki nilai yang merupakan daftar tetap dari konstan bernama:
Nama-nama tersebut adalah nilai dari tipe baru (disimpan secara internal sebagai bilangan bulat kecil); Anda tidak dapat menetapkan apa pun di luar daftar tersebut. Kegunaan: hari dalam seminggu, warna, kode status.
"Nyatakan apa yang dimaksud dengan tipe data terenumerasi."Tipe non-komposit buatan pengguna yang didefinisikan dengan mencantumkan semua nilainya (secara berurutan). Karena nilai-nilai tersebut berurutan, mereka dapat dibandingkan dan dilintasi: dengan TYPE Month = (January, February, ..., December), uji IF ThisMonth > June adalah sah, dan nilai-nilai disimpan secara internal sebagai bilangan bulat. Pseudokode memiliki tiga bagian dan ujian memberikan nilai untuk masing-masing: kata kunci TYPE, pengenal dengan =, dan daftar dalam kurung yang dipisahkan oleh koma.
Contoh terpecahkan. Tulis pseudokode untuk mendefinisikan tipe terenumerasi untuk hari-hari di mana sekolah buka (Senin hingga Jumat), dan deklarasikan variabel dari tipe tersebut yang diatur ke Rabu.
Variabel dari tipe terenumerasi tidak dapat diberi nilai di luar daftar, yang merupakan inti utamanya: Today ← Saturday adalah kesalahan saat kompilasi, sedangkan STRING akan menerima "Saturdy".
Tipe terenumerasi adalah daftar tetap dari nilai-nama
Tipe pointer
Sebuah pointer menyimpan alamat memori dari variabel lain (atau NULL untuk "tidak ada target"). Pointer membangun struktur dinamis (daftar linked, pohon) dan meneruskan referensi tanpa menyalin.
TYPE PNode = ^TNode // pointer to a TNode
DECLARE p : PNode
p ← NEW TNode
p^.Value ← 42 // dereference to reach the fields
Untuk dereference (p^) berarti mengakses variabel yang ditunjuknya.
"Nyatakan apa yang dimaksud dengan tipe data pointer."Tipe non-komposit yang nilainya adalah alamat memori dari (referensi ke) variabel dari tipe tertentu. Pseudokode mendeklarasikan tipe dengan tanda ^ sebelum tipe yang ditunjuknya, dan ujian meminta tepat baris tersebut:
TYPE SelectParts = ^Parts // a pointer to a value of type Parts
DECLARE Chosen : SelectParts
Chosen ← ^Keyboard // Chosen now holds the address of Keyboard
OUTPUT Chosen^ // dereference: the value stored at that address
Pointer adalah dasar dari daftar linked atau pohon biner dinamis (Topik 19): setiap simpul menyimpan pointer ke simpul berikutnya. Dua nilai sering hilang di sini: menulis tipe pointer seolah-olah menyimpan nilainya sendiri, dan melupakan tanda ^ saat membaca melalui pointer.
Pointer menyimpan alamat; p^ melakukan dereference untuk mencapai bidang-bidang simpul
Tipe komposit
Tipe komposit (salah satu dari tipe data komposit) mengelompokkan beberapa nilai di bawah satu nama.
Himpunan adalah koleksi tak berurutan dari nilai-nilai unikRekaman mengelompokkan bidang-bidang dari tipe berbeda di bawah satu nama
rekaman (Topik 10) — bidang-bidang dari tipe berbeda dalam blok TYPE ... ENDTYPE.
himpunan — koleksi tak berurutan dari nilai-nilai unik, dengan operasi add, remove, uji keanggotaan, union, intersection:
DECLARE Available : SET OF Colour
Available ← {Red, Blue}
IF Green IN Available THEN
...
ENDIF
class / object — tipe komposit OOP, menggabungkan bidang data (atribut) dengan operasi atasnya (metode). Sebuah object adalah实例 dari sebuah class:
CLASS Taxi
PRIVATE Capacity : INTEGER
PUBLIC FUNCTION GetCapacity() RETURNS INTEGER
RETURN Capacity
ENDFUNCTION
ENDCLASS
Memilih tipe
Gunakan terenumerasi untuk nilai dari daftar tetap, pointer untuk indirection, rekaman untuk kelompok bidang, himpunan untuk koleksi unik tak berurutan, dan class ketika Anda memerlukan state dan perilaku bersama-sama.
"Deskripsikan tipe data buatan pengguna himpunan" (tiga nilai).Tipe komposit yang menyimpan koleksi nilai dari tipe yang sama, tanpa urutan tertentu dan tanpa duplikat; nilai dapat ditambahkan dan dihapus, dan nilai dapat diuji untuk keanggotaan. Deklarasikan tipe dengan SET OF, lalu definisikan konstanta himpunan dengan nilainya dalam kurung:
TYPE EvenNumbers = SET OF INTEGER
DEFINE Evens (2, 4, 6, 8, 10, 12) : EvenNumbers
TYPE SymbolSet = SET OF CHAR
DEFINE Operators ('+', '-', '*', '/') : SymbolSet
"Deskripsikan tipe data buatan pengguna rekaman" (tiga nilai). *Tipe komposit yang terdiri dari jumlah bidang (item) yang tetap, masing-masing dengan pengenal dan tipenya sendiri, dirujuk di bawah satu pengenal; bidang-bidang diakses dengan notasi titik.
Contoh terpecahkan. Tulis pseudokode untuk mendeklarasikan tipe rekaman ClubMember untuk nama depan, nama belakang, kode keanggotaan (bilangan bulat), tanggal bergabung, dan apakah iuran telah dibayar; kemudian deklarasikan variabel dan atur dua bidangnya.
Setiap bidang memerlukan baris DECLARE sendiri dengan tipe yang sesuai, blok berakhir dengan ENDTYPE, dan sebuah bidang dicapai sebagai variable.field. Ditanya untuk memilih tipe untuk setiap bidang, cocokkan dengan data: kode yang hanya pernah dibandingkan adalah STRING jika dapat mengandung huruf, INTEGER jika aritmatika atau pengurutan diperlukan; ya/tidak adalah BOOLEAN; tanggal adalah DATE. Bidang yang dapat mengambil salah satu dari beberapa nilai bernama (spesies hewan peliharaan, warna) adalah yang harus dibuat menjadi tipe terenumerasi.
Array rekaman: setiap elemen adalah seluruh rekaman, index memilih elemen, dan titik memilih bidang
Rekaman dalam array dan file. Tabel dengan banyak anggota adalah DECLARE Members : ARRAY[1:100] OF ClubMember; kemudian Members[3].LastName adalah satu bidang dari satu elemen, dan perulangan atas indeks memproses setiap rekaman. Rekaman juga merupakan unit alami yang ditulis dan dibaca dari file (di bawah), satu rekaman per PUTRECORD atau WRITEFILE.
Contoh terpecahkan. Tipe komposit Pet menyimpan nama hewan peliharaan (string), spesies (salah satu dari anjing, kucing, kelinci atau hamster) dan berat dalam kilogram (real). Definisikan tipe-tipe tersebut dan deklarasikan variabel.
TYPE Species = (Dog, Cat, Rabbit, Hamster)
TYPE Pet
DECLARE Name : STRING
DECLARE Kind : Species
DECLARE Weight : REAL
ENDTYPE
DECLARE MyPet : Pet
MyPet.Kind ← Rabbit
Tipe terenumerasi didefinisikan pertama, karena rekaman menggunakannya: urutan itu penting dalam pseudocode sama seperti dalam compiler.
Kelas dalam pseudocode.Kelas adalah tipe komposit yang juga membawa perilaku. Ujian meminta deklarasi dengan atributnya ditandai PRIVATE, konstruktor bernama NEW yang mengaturnya, dan PUBLIC metode untuk mengambil atau mengubahnya:
CLASS Appointment
PRIVATE PatientName : STRING
PRIVATE Treatment : STRING
PRIVATE Medication : STRING
PUBLIC PROCEDURE NEW(Name : STRING, Treat : STRING, Med : STRING)
PatientName ← Name
Treatment ← Treat
Medication ← Med
ENDPROCEDURE
PUBLIC FUNCTION GetTreatment() RETURNS STRING
RETURN Treatment
ENDFUNCTION
ENDCLASS
DECLARE Visit : Appointment
Visit ← NEW Appointment("A. Chen", "filling", "none")
OUTPUT Visit.GetTreatment()
Atribut bersifat privat agar hanya dapat diubah melalui metode (enkapsulasi, Topik 20); konstruktor adalah prosedur yang dipanggil NEW dengan satu parameter per atribut; getter adalah fungsi yang mengembalikan atribut. Masing-masing dari ini adalah nilai skor terpisah.
Explore · Jelajahi
Programming concept lab · Makmal konsep pengaturcaraan
Connect examples to the programming idea they show. · Sambungkan contoh kepada idea pengaturcaraan yang ditunjukkannya.
File organisation and access · Organisasi dan akses file
Syllabus · Silabus
English
Candidates should be able to:
Notes and guidance
Show understanding of the methods of file organisation and select an appropriate method of file organisation and file access for a given problem
Including serial, sequential (using a key field), random (using a record key)
Show understanding of methods of file access
Including Sequential access for serial and sequential files Direct access for sequential and random files
Show understanding of hashing algorithms
Describe and use different hashing algorithms to read from and write data to a random/sequential file
Bahasa Indonesia
Kandidat harus mampu:
Catatan dan panduan
Tunjukkan pemahaman tentang metode organisasi berkas dan pilih metode organisasi berkas dan akses berkas yang sesuai untuk masalah yang diberikan
Termasuk serial, sekuensial (menggunakan bidang kunci), acak (menggunakan kunci rekaman)
Tunjukkan pemahaman tentang metode akses berkas
Termasuk Akses sekuensial untuk berkas serial dan sekuensial. Akses langsung untuk berkas sekuensial dan acak
Tunjukkan pemahaman tentang algoritma pencacahan
Deskripsikan dan gunakan berbagai algoritma pencacahan untuk membaca dan menulis data ke berkas acak/sekuensial
Source: Cambridge International syllabus · Sumber: Silabus Cambridge International
English
File organisation 文件组织 is how the data is laid out; file access is how the program reaches a record.
serial file 串行文件 — records in the order added, no sorting. Access is sequential only; appending is fast; searching is slow. Used for logs and audit trails.
sequential file 顺序文件 — records sorted by a key. Searching is faster (you can stop early or binary-search); inserting is slow (records must shift). Used for master files updated in batch.
random file 随机文件 (direct-access file) — records at positions computed from the key (often by a hash). Direct access by key is very fast; reading in key order is harder. Used for large lookup tables and customer accounts.
The two access methods are sequential access 顺序存取 (read from start to end) and direct access 直接存取 (jump straight to a known position). Match the structure to the dominant operation: single-key lookups favour random; in-order reports favour sequential.
Describing each organisation (the wording that scores).Serial: records are stored one after another in the order in which they were added, with no ordering by key. Sequential: records are stored in order of a key field (sorted). Random: each record is stored at an address calculated from its key by a hashing algorithm, so the records are not in any order. Comparing serial and sequential: both store records one after another and both are read sequentially, but a sequential file is ordered by key, so a search can stop as soon as a key larger than the target is read, and a new record must be inserted in its correct position (usually by rewriting the file), whereas a serial file is simply appended to.
Describing each access method.Sequential access: start at the beginning of the file and read the records one after another (in the order stored) until the required record is found or the end of the file is reached. Applied to a serial file this means reading every record up to the match, and reading the whole file to establish that a record is absent; applied to a sequential file the search can stop early, as soon as a key greater than the target is read. Direct access: the address of the record is calculated from its key (by a hashing algorithm, or from an index), and the program goes straight to that position without reading the records before it; this is the access method for random files, and for a record referenced by a unique address on a disk.
Choosing. A payroll or utility-billing master file processed in batch, every record in turn, suits a sequential file; a log of transactions in the order they happened suits a serial file; a stock or customer file where single records are looked up and updated by key while the program runs suits a random file with direct access.
File handling in pseudocode. The exam expects the standard statements, and Paper 3 sets algorithms that use them:
Task
Statements
open a text file
OPENFILE "Scores.txt" FOR READ (or FOR WRITE, which creates or overwrites, or FOR APPEND)
read or write a line
READFILE "Scores.txt", Line and WRITEFILE "Scores.txt", Line
test for the end
WHILE NOT EOF("Scores.txt")
close
CLOSEFILE "Scores.txt"
open a random file
OPENFILE "Stock.dat" FOR RANDOM
move to a record position
SEEK "Stock.dat", Address
read or write a whole record
GETRECORD "Stock.dat", Item and PUTRECORD "Stock.dat", Item
Worked example. A random file Stock.dat holds records of type StockItem, stored at the address given by ItemID MOD 100. Write pseudocode that stores a new item at its hashed address if that position is empty, reporting the position if it is already in use.
Two details the mark scheme checks: SEEKbefore each GETRECORD or PUTRECORD (reading moves the position on, so seek again before writing), and the file opened FOR RANDOM and closed at the end. To copy every record of a random file to another, loop over the addresses with SEEK, GETRECORD from one file and PUTRECORD to the other, skipping empty positions.
Bahasa Indonesia
Organisasi file adalah bagaimana data tersusun; akses file adalah bagaimana program mencapai sebuah rekaman.
file serial — rekaman dalam urutan penambahan, tanpa pengurutan. Akses hanya berurutan; penambahan akhir cepat; pencarian lambat. Digunakan untuk log dan jejak audit.
file berurutan — rekaman diurutkan berdasarkan kunci. Pencarian lebih cepat (Anda bisa berhenti lebih awal atau menggunakan pencarian biner); penyisipan lambat (rekaman harus bergeser). Digunakan untuk file master yang diperbarui secara batch.
file acak (file akses langsung) — rekaman di posisi yang dihitung dari kunci (sering kali melalui hash). Akses langsung berdasarkan kunci sangat cepat; membaca dalam urutan kunci lebih sulit. Digunakan untuk tabel pencarian besar dan akun pelanggan.
File serial: rekaman disimpan dalam urutan penambahanFile berurutan: rekaman diurutkan berdasarkan bidang kunciFile acak: rekaman berada di posisi yang dihitung dari kunci
Dua metode akses adalah akses berurutan (dibaca dari awal hingga akhir) dan akses langsung (lompat langsung ke posisi yang diketahui). Cocokkan struktur dengan operasi dominan: pencarian kunci tunggal mendukung random; laporan berurutan mendukung sequential.
Mendeskripsikan setiap organisasi (kata-kata yang bernilai).Serial: rekaman disimpan satu setelah lainnya dalam urutan penambahan, tanpa pengurutan berdasarkan kunci. Berurutan: rekaman disimpan berdasarkan urutan bidang kunci (terurut). Acak: setiap rekaman disimpan pada alamat yang dihitung dari kuncinya oleh algoritma hashing, sehingga rekaman tidak dalam urutan apa pun. Membandingkan serial dan berurutan: keduanya menyimpan rekaman satu setelah lainnya dan keduanya dibaca secara berurutan, tetapi file berurutan diurutkan berdasarkan kunci, sehingga pencarian dapat berhenti segera setelah kunci yang lebih besar dari target terbaca, dan rekaman baru harus disisipkan pada posisi yang benar (biasanya dengan menulis ulang file), sedangkan file serial sekadar ditambahkan di akhirnya.
Dua metode akses sebagai prosedur: akses langsung menghitung tempat untuk melihat; akses berurutan melihat semuanya secara bergantian
Mendeskripsikan setiap metode akses.Akses berurutan: mulai dari awal file dan baca rekaman satu setelah lainnya (dalam urutan penyimpanan) hingga rekaman yang diinginkan ditemukan atau akhir file tercapai. Diterapkan pada file serial ini berarti membaca setiap rekaman hingga cocok, dan membaca seluruh file untuk menetapkan bahwa rekaman tidak ada; diterapkan pada file berurutan pencarian dapat berhenti lebih awal, segera setelah kunci yang lebih besar dari target terbaca. Akses langsung:alamat rekaman dihitung dari kuncinya (oleh algoritma hashing, atau dari indeks), dan program pergi langsung ke posisi tersebut tanpa membaca rekaman sebelumnya; ini adalah metode akses untuk file acak, dan untuk rekaman yang dirujuk oleh alamat unik di disk.
Pemilihan. File master gaji atau tagihan utilitas yang diproses secara batch, setiap rekaman secara bergantian, cocok untuk file berurutan; log transaksi sesuai dengan urutan kejadiannya cocok untuk file serial; file stok atau pelanggan di mana rekaman tunggal dicari dan diperbarui berdasarkan kunci selama program berjalan cocok untuk file acak dengan akses langsung.
Penanganan file dalam pseudocode. Ujian mengharapkan pernyataan standar, dan Paper 3 menetapkan algoritma yang menggunakannya:
Tugas
Pernyataan
buka file teks
OPENFILE "Scores.txt" FOR READ (atau FOR WRITE, yang membuat atau menimpa, atau FOR APPEND)
baca atau tulis baris
READFILE "Scores.txt", Line dan WRITEFILE "Scores.txt", Line
uji untuk akhir
WHILE NOT EOF("Scores.txt")
tutup
CLOSEFILE "Scores.txt"
buka file acak
OPENFILE "Stock.dat" FOR RANDOM
pindah ke posisi rekaman
SEEK "Stock.dat", Address
baca atau tulis seluruh rekaman
GETRECORD "Stock.dat", Item dan PUTRECORD "Stock.dat", Item
Contoh terpecahkan. File acak Stock.dat menyimpan rekaman bertipe StockItem, disimpan pada alamat yang diberikan oleh ItemID MOD 100. Tulis pseudocode yang menyimpan item baru pada alamat hashnya jika posisi tersebut kosong, melaporkan posisinya jika sudah digunakan.
DECLARE Item, Existing : StockItem
DECLARE Address : INTEGER
INPUT Item.ItemID, Item.Description, Item.Quantity
Address ← Item.ItemID MOD 100
OPENFILE "Stock.dat" FOR RANDOM
SEEK "Stock.dat", Address
GETRECORD "Stock.dat", Existing
IF Existing.ItemID = 0 THEN
// 0 marks an empty position
ENDIF
SEEK "Stock.dat", Address
PUTRECORD "Stock.dat", Item
OUTPUT "Stored at ", Address
ELSE
OUTPUT "Position ", Address, " is in use"
ENDIF
CLOSEFILE "Stock.dat"
Dua hal yang diperiksa oleh kunci jawaban: SEEKsebelum setiap GETRECORD atau PUTRECORD (pembacaan memindahkan posisi, jadi cari lagi sebelum menulis), dan file dibuka FOR RANDOM dan ditutup di akhir. Untuk menyalin setiap rekaman dari file acak ke file lain, lakukan perulangan pada alamat dengan SEEK, GETRECORD dari satu file dan PUTRECORD ke file lainnya, melewati posisi kosong.
Explore · Jelajahi
File access route · Rute akses file
Follow a file from storage to program and back safely. · Ikuti alur file dari penyimpanan ke program dan kembali dengan aman.
A hash function 散列函数 (a hashing algorithm) takes a record key and produces an address where the record is stored. A good one is fast, deterministic 确定性, and spreads keys evenly.
Common hashing algorithms for $N$ slots: modulo hash address ← key MOD N; folding (split the key, add the pieces, MOD N); a string hash (sum the character codes, MOD N).
A collision 冲突 is when two keys hash to the same address. Three ways to resolve it:
Strategy
How it works
Trade-off
linear probing 线性探测
use the next free slot (wrapping around)
simple, but keys cluster
chaining 链接法
each slot points to a linked list 链表 of records
no clustering, but uses more memory
rehashing
apply a second hash function
spreads keys, but more work
To search: hash the key, read that slot; if the keys match you are done, else follow the resolution strategy until a match or an empty slot. To insert: hash the key, write to that slot or the next free one. Keep the load factor 装填因子 (records ÷ slots) below about 70% for near-O(1) lookups.
"Explain what is meant by a hashing algorithm in the context of file access" (three marks).A calculation (function) performed on the key field of a record that produces a value, which is used as the address (location) at which the record is stored in the file and from which it is retrieved. The same calculation on the same key always gives the same address, which is why the record can be found again without searching.
"Outline two methods of overcoming a collision." (1) Linear probing (open addressing): store the record in the next free location after the calculated address, wrapping round to the start if necessary; to retrieve, start at the hashed address and read forward until the key matches. (2) An overflow area 溢出区 or chaining: store the colliding record in a separate overflow area (or a linked list attached to the address), which is searched sequentially after the main address fails to match. Either scores; describe the retrieval as well as the storage.
Worked example. A random file has 11 record positions, numbered 0 to 10, and the hashing algorithm is Address ← Key MOD 11. Records with keys 1250, 1381, 1452, 1613 and 1470 are stored in that order, using linear probing. Show where each record goes, and describe how key 1470 is retrieved.
$1250 \bmod 11 = 7$; $1381 \bmod 11 = 6$; $1452 \bmod 11 = 0$; $1613 \bmod 11 = 7$, a collision with 1250, so 1613 takes the next free position, 8; $1470 \bmod 11 = 7$ again, and positions 7 and 8 are full, so 1470 goes to 9. To retrieve 1470: calculate $7$, read position 7 (key 1250, no match), read 8 (1613, no), read 9 (1470, found). If an empty position is reached before a match, the record is not in the file. Collisions are the price of a small file: a good hashing algorithm spreads the keys evenly, and the file is kept well below full so that probes stay short.
Bahasa Indonesia
Sebuah fungsi hash (algoritma penghashan) mengambil kunci rekaman dan menghasilkan alamat tempat rekaman disimpan. Fungsi yang baik itu cepat, deterministik, dan menyebarkan kunci secara merata.
Algoritma penghashan umum untuk slot $N$: modulo hash address ← key MOD N; folding (pecah kunci, tambahkan bagian-bagiannya, MOD N); string hash (jumlahkan kode karakter, MOD N).
Tabrakan terjadi ketika dua kunci dihash ke alamat yang sama. Tiga cara untuk menyelesaikannya:
Strategi
Cara kerja
Kompromi
penelusuran linear
gunakan slot berikutnya yang kosong (melingkari)
sederhana, tetapi kunci mengelompok
penganting
setiap slot menunjuk ke daftar terhubung rekaman
tidak ada pengelompokan, tetapi menggunakan lebih banyak memori
rehashing
terapkan fungsi hash kedua
menyebarkan kunci, tetapi lebih banyak pekerjaan
Menyelesaikan tabrakan hash: penelusuran linear menggunakan slot berikutnya yang kosong; penganting mempertahankan daftar terhubung per slot
Untuk mencari: hash kunci, baca slot tersebut; jika kuncinya cocok Anda selesai, jika tidak ikuti strategi penyelesaian hingga menemukan kecocokan atau slot kosong. Untuk menyisipkan: hash kunci, tulis ke slot tersebut atau slot berikutnya yang kosong. Jaga faktor beban (rekaman ÷ slot) di bawah sekitar 70% untuk pencarian hampir-O(1).
"Jelaskan apa yang dimaksud dengan algoritma penghashan dalam konteks akses file (tiga nilai).** Suatu perhitungan (fungsi) yang dilakukan pada bidang kunci rekaman yang menghasilkan nilai, yang digunakan sebagai alamat (lokasi) di mana rekaman disimpan dalam file dan dari mana rekaman diambil. Perhitungan yang sama pada kunci yang sama selalu menghasilkan alamat yang sama, itulah sebabnya rekaman dapat ditemukan kembali tanpa perlu mencari.
"Gambarkan dua metode untuk mengatasi tabrakan." (1) Penelusuran linear (pengalamatan terbuka): simpan rekaman di lokasi berikutnya yang kosong setelah alamat yang dihitung, melingkari kembali ke awal jika perlu; untuk mengambil, mulai dari alamat dihash dan baca maju hingga kuncinya cocok. (2) Area tumpukan atau penganting: simpan rekaman yang bertabrakan di area tumpukan terpisah (atau daftar terhubung yang melekat pada alamat), yang dicari secara berurutan setelah alamat utama gagal cocok. Keduanya mendapat nilai; jelaskan juga pengambilan data selain penyimpanan.
Contoh pengerjaan. Sebuah file acak memiliki 11 posisi rekaman, bernomor 0 hingga 10, dan algoritma penghashannya adalah Address ← Key MOD 11. Rekaman dengan kunci 1250, 1381, 1452, 1613, dan 1470 disimpan sesuai urutan tersebut, menggunakan penelusuran linear. Tunjukkan ke mana setiap rekaman pergi, dan jelaskan bagaimana kunci 1470 diambil.
$1250 \bmod 11 = 7$; $1381 \bmod 11 = 6$; $1452 \bmod 11 = 0$; $1613 \bmod 11 = 7$, sebuah tabrakan dengan 1250, sehingga 1613 mengambil posisi berikutnya yang kosong, yaitu 8; $1470 \bmod 11 = 7$ lagi, dan posisi 7 dan 8 sudah penuh, sehingga 1470 masuk ke 9. Untuk mengambil 1470: hitung $7$, baca posisi 7 (kunci 1250, tidak cocok), baca 8 (1613, tidak), baca 9 (1470, ditemukan). Jika mencapai posisi kosong sebelum menemukan kecocokan, rekaman tidak ada dalam file. Tabrakan adalah harga dari ukuran file yang kecil: algoritma penghashan yang baik menyebarkan kunci secara merata, dan file dijaga jauh di bawah kapasitas penuh agar probe tetap pendek.
Explore · Jelajahi
A hash table · Tabel hash
Watch each key get hashed to a bucket. A good hash spreads keys out so lookups stay fast. · Saksikan setiap kunci dihash ke wadah. Hash yang baik menyebarkan kunci agar pencarian tetap cepat.
13.3
Floating-point numbers · Bilangan titikaplangit
Syllabus · Silabus
English
Candidates should be able to:
Notes and guidance
Describe the format of binaryfloating-point real numbers
Use two's complement form Understand of the effects of changing the allocation of bits to mantissa and exponent in a floating-point representation
Convert binaryfloating-point real numbers into denary and vice versa
Normalise floating-point numbers
Understand the reasons for normalisation
Show understanding of the consequences of a binary representation only being an approximation to the real number it represents (in certain cases)
Understand how underflow and overflow can occur
Show understanding that binary representations can give rise to rounding errors
Bahasa Indonesia
Kandidat harus mampu:
Catatan dan panduan
Deskripsikan format bilangan riil floating-point biner
Gunakan bentuk komplemen dua Pahami efek dari perubahan alokasi bit ke mantissa dan eksponen dalam representasi floating-point
Konversi bilangan riil floating-point biner ke desimal dan sebaliknya
Normalisasikan bilangan floating-point
Pahami alasan untuk normalisasi
Tunjukkan pemahaman tentang konsekuensi dari representasi biner yang hanya merupakan pendekatan terhadap bilangan riil yang diwakilinya (dalam kasus tertentu)
Pahami bagaimana underflow dan overflow dapat terjadi
Tunjukkan pemahaman bahwa representasi biner dapat menimbulkan kesalahan pembulatan
Source: Cambridge International syllabus · Sumber: Silabus Cambridge International
English
To store real numbers of very different sizes, computers use a floating-point 浮点 format — a binary form of scientific notation, with two fields:
a mantissa 尾数 — the significant digits.
an exponent 指数 — the power of 2 to multiply by.
Both are stored as two's complement 补码 integers. The value is
Read the mantissa as a binary fraction — the first bit after the point is worth $1/2$, the next $1/4$, then $1/8$, and so on. So 0.1010000 is $1/2 + 1/8 = 0.625$; with exponent 00000010 (= 2) the value is $0.625 \times 2^{2} = 2.5$.
Converting
binary → denary: read the mantissa (use two's-complement rules if negative) as a fraction, read the exponent as a signed integer, then multiply mantissa by $2^{\text{exponent}}$.
denary → binary: write the number as a binary fraction × a power of 2, then store the mantissa and exponent in the agreed formats.
Worked example. A number has mantissa 10110000 and exponent 00000011. Find its denary value.
The exponent 00000011 is $+3$. The mantissa begins with a 1, so it is negative. Read as 1.0110000 in two's complement, the sign bit is worth $-1$ and the fraction bits add $\tfrac{1}{4} + \tfrac{1}{8} = 0.375$, so the mantissa is $-1 + 0.375 = -0.625$. Then
$$\text{number} = -0.625 \times 2^{3} = -5.0.$$
Worked example. Store $+2.5$ in this format.
In binary $2.5 = 10.1$. Written as a normalised fraction, $2.5 = 0.101 \times 2^{2}$. So the mantissa is 01010000 (sign bit 0, then .101) and the exponent is 00000010 ($= 2$).
The exam's format: two's complement, a mantissa and an exponent
The exam states a format such as 10 bits for the mantissa and 6 bits for the exponent, both in two's complement. The mantissa's binary point sits after its first (sign) bit, so a positive mantissa is 0.xxxxxxxxx and a negative one 1.xxxxxxxxx; the exponent is an ordinary signed integer. Every conversion uses the same three moves: read the mantissa as a fraction (two's-complement rules if it starts with 1), read the exponent as an integer, multiply by $2^{\text{exponent}}$.
Worked example (binary to denary). Mantissa 0101100000, exponent 000011.
Worked example (negative mantissa). Mantissa 1011000000, exponent 000010.
The mantissa starts with 1, so it is negative. Its value is $-1 + 0.011000000_2 = -1 + (\tfrac{1}{4} + \tfrac{1}{8}) = -0.625$; exponent $= 2$; value $-0.625 \times 4 = -2.5$. (Alternatively, take the two's complement of the mantissa, 0101000000$= 0.625$, and attach the minus sign.) A negative exponent such as 111110$= -2$ divides instead: a mantissa of $0.5$ with that exponent is $0.5 \times 2^{-2} = 0.125$.
Worked example (denary to binary). Store $+6.5$ and $-6.5$ in the 10-bit and 6-bit format, normalised.
$6.5 = 110.1_2 = 0.1101_2 \times 2^{3}$, so the mantissa is 0110100000 and the exponent 000011. For $-6.5$, take the two's complement of the mantissa: 1001100000 (check: $-1 + 0.0011_2 = -1 + 0.1875 = -0.8125$, and $-0.8125 \times 8 = -6.5$), exponent 000011 unchanged. The sign never goes into the exponent; a negative number has a negative mantissa.
Normalisation
A number is normalised 规格化 when the first significant bit is immediately after the binary point (no wasted leading zeros). This maximises precision, because every mantissa bit carries information. To normalise, shift the mantissa left and decrease the exponent (or shift right and increase it) until the first significant bit is in place; the value is unchanged. For negative (two's-complement) mantissas, the sign bit (1) is followed immediately by a 0.
Recognising and producing normalised form. A positive normalised mantissa begins 01; a negative one begins 10. So 0011000000 is not normalised (shift left one place and subtract one from the exponent: 0110000000, exponent one less) and 1100000000 is not either (shift left until the pattern is 10...). Each shift left of the mantissa must be matched by subtracting one from the exponent, or the value changes.
"Explain why numbers are stored in normalised form" (two marks). (1) It gives the maximum precision (accuracy) for the number of bits available, because no bits are wasted on leading zeros (or leading ones for a negative number); (2) each number then has a unique representation, so numbers can be compared; and (3) it makes the best use of the available range. Any two of these score.
Approximation and rounding errors
Many denary reals cannot be stored exactly in binary — e.g. $0.1_{10}$ is the repeating binary fraction $0.000110011\ldots_{2}$, which must be truncated. Consequences:
rounding errors 舍入误差 build up over many operations (0.1 + 0.2 is not exactly 0.3).
comparisons fail — never test a real for equality. Test that the difference is smaller than a small tolerance, IF Difference < 0.000001, where the difference is taken the right way round or through a modulus function that the question would define. ABS is not on the 9618 insert or in the Pseudocode Guide, so do not assume it: the guide says any function a question needs will be given.
subtracting two nearly-equal values loses precision.
overflow 溢出 (a result too large for the exponent's range) and underflow 下溢 (a result too small, rounding to zero) occur when the exponent runs out of range.
For exact needs (currency), use fixed-point 定点 or BCD 二进码十进数 instead of floating-point.
"Describe the effect of changing the allocation of bits" (three marks). With a fixed total number of bits, increasing the mantissa and reducing the exponent gives greater precision 精度 (more significant figures, smaller rounding errors) but a smaller range 范围 (the largest and smallest magnitudes that can be stored shrink); increasing the exponent does the opposite: a larger range at the cost of precision. Name both effects and both directions.
Largest and smallest. In the 10-bit mantissa, 6-bit exponent format the largest positive number has mantissa 0111111111 ($= 1 - 2^{-9}$) and exponent 011111 ($= 31$): about $2^{31}$. The smallest positive normalised number has mantissa 0100000000 ($= 0.5$) and exponent 100000 ($= -32$): $0.5 \times 2^{-32} = 2^{-33}$. The most negative number has mantissa 1000000000 ($= -1$) and exponent $31$: $-2^{31}$.
"Explain what is meant by overflow and underflow."Overflow occurs when the result of a calculation is larger than the largest number that can be represented, so the exponent would need more bits than it has; underflow occurs when a result is smaller than the smallest (non-zero) number that can be represented, too close to zero for the exponent to express, so it is stored as zero. Both come from the exponent's range, not the mantissa's.
Why a binary representation is only an approximation. A binary fraction can only represent sums of $\tfrac{1}{2}, \tfrac{1}{4}, \tfrac{1}{8}, \ldots$ exactly; a value such as $0.1$ or $\tfrac{1}{3}$ has an infinite binary expansion, and the mantissa has a fixed number of bits, so the stored value is the nearest one that fits. The difference is a rounding error; it is small for one number but accumulates over repeated calculations (adding $0.1$ ten times may not give exactly $1$), which is why real numbers should never be tested for exact equality.
Bahasa Indonesia
Untuk menyimpan bilangan riil dengan ukuran yang sangat berbeda, komputer menggunakan format titikaplangit — bentuk biner dari notasi ilmiah, dengan dua bidang:
mantissa — digit signifikan.
eksponen — pangkat dari 2 yang dikalikan.
Keduanya disimpan sebagai bilangan bulat komplemen dua. Nilainya adalah
Baca mantissa sebagai pecahan biner — bit pertama setelah titik bernilai $1/2$, berikutnya $1/4$, kemudian $1/8$, dan seterusnya. Jadi 0.1010000 adalah $1/2 + 1/8 = 0.625$; dengan eksponen 00000010 (= 2) nilainya adalah $0.625 \times 2^{2} = 2.5$.
Nilai tempat dari mantissa 8-bit dan eksponen 8-bit
Konversi
biner → desimal: baca mantissa (gunakan aturan komplemen dua jika negatif) sebagai pecahan, baca eksponen sebagai bilangan bulat bertanda, lalu kalikan mantissa dengan $2^{\text{exponent}}$.
desimal → biner: tulis angka sebagai pecahan biner × pangkat dari 2, lalu simpan mantissa dan eksponen dalam format yang disepakati.
Contoh pengerjaan. Suatu angka memiliki mantissa 10110000 dan eksponen 00000011. Temukan nilai desimalnya.
Eksponen 00000011 adalah $+3$. Mantissa dimulai dengan 1, jadi negatif. Dibaca sebagai 1.0110000 dalam komplemen dua, bit tanda bernilai $-1$ dan bit pecahan menambah $\tfrac{1}{4} + \tfrac{1}{8} = 0.375$, sehingga mantissa adalah $-1 + 0.375 = -0.625$. Kemudian
$$\text{number} = -0.625 \times 2^{3} = -5.0.$$
Contoh pengerjaan. Simpan $+2.5$ dalam format ini.
Dalam biner $2.5 = 10.1$. Ditulis sebagai pecahan ternormalisasi, $2.5 = 0.101 \times 2^{2}$. Jadi mantissanya adalah 01010000 (bit tanda 0, kemudian .101) dan eksponennya adalah 00000010 ($= 2$).
Format ujian: komplemen dua, mantissa, dan eksponen
Ujian menyatakan format seperti 10 bit untuk mantisa dan 6 bit untuk eksponen, keduanya dalam dua komplemen. Titik biner mantisa berada setelah bit pertama (tanda)nya, sehingga mantisa positif adalah 0.xxxxxxxxx dan mantisa negatif 1.xxxxxxxxx; eksponen adalah bilangan bulat bertanda biasa. Setiap konversi menggunakan tiga langkah yang sama: baca mantisa sebagai pecahan (aturan dua komplemen jika dimulai dengan 1), baca eksponen sebagai bilangan bulat, kalikan dengan $2^{\text{exponent}}$.
Contoh terpecahkan (biner ke desimal). Mantisa 0101100000, eksponen 000011.
Mantisa dimulai dengan 1, jadi bernilai negatif. Nilainya adalah $-1 + 0.011000000_2 = -1 + (\tfrac{1}{4} + \tfrac{1}{8}) = -0.625$; eksponen $= 2$; nilai $-0.625 \times 4 = -2.5$. (Atau, ambil dua komplemen dari mantisa, 0101000000$= 0.625$, dan tambahkan tanda minus.) Eksponen negatif seperti 111110$= -2$ berarti pembagian: mantisa $0.5$ dengan eksponen tersebut bernilai $0.5 \times 2^{-2} = 0.125$.
Contoh terpecahkan (desimal ke biner). Simpan $+6.5$ dan $-6.5$ dalam format 10-bit dan 6-bit, dinormalisasi.
$6.5 = 110.1_2 = 0.1101_2 \times 2^{3}$, jadi mantisanya 0110100000 dan eksponennya 000011. Untuk $-6.5$, ambil dua komplemen dari mantisa: 1001100000 (cek: $-1 + 0.0011_2 = -1 + 0.1875 = -0.8125$, dan $-0.8125 \times 8 = -6.5$), eksponen 000011 tetap. Tanda tidak masuk ke eksponen; bilangan negatif memiliki mantisa negatif.
Normalisasi
Sebuah bilangan dinormalisasi ketika bit signifikan pertama berada tepat setelah titik biner (tidak ada nol awalan yang sia-sia). Ini memaksimalkan presisi, karena setiap bit mantisa membawa informasi. Untuk menormalisasi, geser mantisa ke kiri dan kurangi eksponen (atau geser ke kanan dan tingkatkan) hingga bit signifikan pertama berada di tempatnya; nilainya tetap sama. Untuk mantisa negatif (dua komplemen), bit tanda (1) diikuti segera oleh 0.
Mengenal dan menghasilkan bentuk normal. Mantisa positif dinormalisasi dimulai 01; yang negatif dimulai 10. Jadi 0011000000 tidak dinormalisasi (geser ke kiri satu tempat dan kurangi satu dari eksponen: 0110000000, eksponen berkurang satu) dan 1100000000 juga tidak (geser ke kiri hingga polanya menjadi 10...). Setiap pergeseran ke kiri mantisa harus diikuti pengurangan satu dari eksponen, atau nilainya berubah.
"Jelaskan mengapa angka disimpan dalam bentuk normal" (dua nilai). (1) Memberikan presisi maksimum (akurasi) untuk jumlah bit yang tersedia, karena tidak ada bit yang sia-sia pada nol awalan (atau satu awalan untuk bilangan negatif); (2) setiap bilangan kemudian memiliki representasi unik, sehingga bilangan dapat dibandingkan; dan (3) ini memanfaatkan rentang yang tersedia sebaik mungkin. Dua dari poin ini mendapat nilai.
Normalisasi: geser mantisa ke kiri untuk menghilangkan nol awalan, menurunkan eksponen dengan jumlah yang sama
Pendekatan dan kesalahan pembulatan
Banyak bilangan riil desimal tidak dapat disimpan secara tepat dalam biner — mis. $0.1_{10}$ adalah pecahan biner berulang $0.000110011\ldots_{2}$, yang harus dipotong. Konsekuensinya:
kesalahan pembulatan menumpuk selama banyak operasi (0.1 + 0.2 tidak sama persis dengan 0.3).
perbandingan gagal — jangan pernah menguji bilangan riil untuk kesamaan. Ujilah bahwa selisihnya lebih kecil dari toleransi kecil, IF Difference < 0.000001, di mana selisih diambil dengan arah yang benar atau melalui fungsi modulus yang akan didefinisikan oleh soal. ABS tidak ada di lampiran 9618 atau dalam Panduan Pseudocode, jadi jangan asumsikan itu: panduan menyatakan bahwa fungsi apa pun yang diperlukan soal akan diberikan.
mengurangi dua nilai yang hampir sama kehilangan presisi.
overflow (hasil terlalu besar untuk rentang eksponen) dan underflow (hasil terlalu kecil, dibulatkan menjadi nol) terjadi ketika eksponen melebihi batas.
Untuk kebutuhan presisi (mata uang), gunakan titik tetap atau BCD alih-alih titik mengambang.
Total bit yang sama dibagi dua cara: bit mantisa membeli presisi, bit eksponen membeli rentang, dan satu hanya bisa tumbuh di atas pengorbanan yang lain
"Deskripsikan efek perubahan alokasi bit" (tiga nilai). Dengan total jumlah bit tetap, meningkatkan mantisa dan mengurangi eksponen memberikan presisi yang lebih besar (lebih banyak angka signifikan, kesalahan pembulatan lebih kecil) tetapi rentang yang lebih kecil (besar dan kecilnya besaran yang dapat disimpan menyusut); meningkatkan eksponen melakukan sebaliknya: rentang lebih besar dengan mengorbankan presisi. Sebutkan kedua efek dan kedua arah.
Terbesar dan terkecil. Dalam format mantisa 10-bit, eksponen 6-bit, bilangan positif terbesar memiliki mantisa 0111111111 ($= 1 - 2^{-9}$) dan eksponen 011111 ($= 31$): sekitar $2^{31}$. Bilangan positif dinormalisasi terkecil memiliki mantisa 0100000000 ($= 0.5$) dan eksponen 100000 ($= -32$): $0.5 \times 2^{-32} = 2^{-33}$. Bilangan paling negatif memiliki mantisa 1000000000 ($= -1$) dan eksponen $31$: $-2^{31}$.
"Jelaskan apa yang dimaksud dengan overflow dan underflow."Overflow terjadi ketika hasil perhitungan lebih besar dari bilangan terbesar yang dapat direpresentasikan, sehingga eksponen memerlukan lebih banyak bit daripada yang dimilikinya; underflow terjadi ketika hasil lebih kecil dari bilangan terkecil (non-nol) yang dapat direpresentasikan, terlalu dekat dengan nol sehingga eksponen tidak dapat mengekspresikannya, sehingga disimpan sebagai nol. Keduanya berasal dari rentang eksponen, bukan mantisa.
Mengapa representasi biner hanyalah sebuah pendekatan. Pecahan biner hanya dapat merepresentasikan jumlah dari $\tfrac{1}{2}, \tfrac{1}{4}, \tfrac{1}{8}, \ldots$ secara tepat; nilai seperti $0.1$ atau $\tfrac{1}{3}$ memiliki ekspansi biner tak hingga, dan mantisa memiliki jumlah bit yang tetap, sehingga nilai yang disimpan adalah nilai terdekat yang muat. Perbedaan ini adalah kesalahan pembulatan; nilainya kecil untuk satu angka tetapi terakumulasi melalui perhitungan berulang (menambahkan $0.1$ sebanyak sepuluh kali mungkin tidak menghasilkan tepat $1$), oleh karena itu bilangan riil seharusnya tidak pernah diuji untuk kesamaan eksak.
Explore · Jelajahi
Build a floating-point number · Membangun angka titikapung
Flip the mantissa and exponent bits to make a value, and check whether it is normalised. · Balik bit mantissa dan eksponen untuk membuat nilai, dan periksa apakah itu dinormalisasi.
Explore · Jelajahi
Normalising a floating-point number · Menormalisasi angka titikapung
Step through normalisation. Shifting the mantissa to remove wasted leading zeros — and adjusting the exponent to match — keeps the value the same but spends every bit on precision. · Langkah-langkah normalisasi. Menggeser mantissa untuk menghilangkan nol awal yang sia-sia — dan menyesuaikan eksponen agar sesuai — mempertahankan nilai yang sama tetapi menghabiskan setiap bit untuk presisi.
Definitions the examiner accepts · Definisi yang diterima oleh penguji
English
A definition question is marked against fixed wording. Learn these exactly, and give one answer only.
Term
Definition
user-defined data type
a data type defined by the programmer, based on existing types, to represent data specific to the problem
non-composite type
a type defined without reference to another type; it holds a single value (integer, real, enumerated, pointer)
composite type
a type made up of other types; it holds several values under one identifier (record, set, array, class)
enumerated type
a non-composite type defined by listing all its possible values, in order
pointer type
a non-composite type whose value is the memory address of a variable of a given type
set
a composite type holding a collection of values of one type, unordered and without duplicates
record
a composite type with a fixed number of fields, each with its own identifier and type, accessed by dot notation
class
a composite type combining attributes (data) with the methods (procedures and functions) that act on them; an object is an instance of a class
serial file
records stored one after another in the order in which they were added
sequential file
records stored one after another in order of a key field
random file
records stored at addresses calculated from their keys by a hashing algorithm
sequential access
reading the records in turn from the start of the file until the one required is found
direct access
calculating the address of a record from its key and going straight to that position
hashing algorithm
a calculation on the key of a record that gives the address at which the record is stored and found
collision
two different keys producing the same address
mantissa
the part of a floating-point number that holds its significant bits, as a two's-complement fraction
exponent
the two's-complement integer giving the power of two by which the mantissa is multiplied
normalised
a floating-point number whose mantissa begins 01 (positive) or 10 (negative), so no bits are wasted on leading zeros or ones
overflow
a result too large to be represented in the number of bits available
underflow
a non-zero result too small to be represented, so it is stored as zero
rounding error
the difference between a real number and the nearest value that the binary representation can hold
Bahasa Indonesia
Soal definisi dinilai berdasarkan frasa tetap. Hafalkan ini persis, dan berikan hanya satu jawaban.
Istilah
Definisi
tipe data yang didefinisikan pengguna
sebuah tipe data yang didefinisikan oleh pemrogram, berdasarkan tipe yang sudah ada, untuk merepresentasikan data spesifik pada masalah
tipe non-komposit
sebuah tipe yang didefinisikan tanpa merujuk pada tipe lain; ia menyimpan satu nilai (integer, real, terenumerasi, pointer)
tipe komposit
sebuah tipe yang tersusun dari tipe-tipe lain; ia menyimpan beberapa nilai di bawah satu pengenal (rekaman, set, array, kelas)
tipe terenumerasi
sebuah tipe non-komposit yang didefinisikan dengan mencantumkan semua nilainya yang mungkin, berurutan
tipe pointer
sebuah tipe non-komposit yang nilainya adalah alamat memori dari sebuah variabel bertipe tertentu
set
sebuah tipe komposit yang menyimpan kumpulan nilai dari satu tipe, tidak berurutan dan tanpa duplikat
rekaman
sebuah tipe komposit dengan jumlah bidang yang tetap, masing-masing dengan pengenal dan tipenya sendiri, diakses menggunakan notasi titik
kelas
sebuah tipe komposit yang menggabungkan atribut (data) dengan metode (prosedur dan fungsi) yang bekerja padanya; objek adalah实例 dari sebuah kelas
file serial
rekaman yang disimpan satu demi satu sesuai urutan saat mereka ditambahkan
file sekuensial
rekaman yang disimpan satu demi satu sesuai urutan bidang kunci
file acak
rekaman yang disimpan pada alamat yang dihitung dari kuncinya melalui algoritma hashing
akses sekuensial
membaca rekaman secara bergantian dari awal file hingga rekaman yang dibutuhkan ditemukan
akses langsung
menghitung alamat rekaman dari kuncinya dan pergi langsung ke posisi tersebut
algoritma hashing
sebuah perhitungan pada kunci rekaman yang memberikan alamat di mana rekaman disimpan dan ditemukan
tabrakan
dua kunci berbeda yang menghasilkan alamat yang sama
mantisa
bagian dari bilangan floating-point yang menyimpan bit signifikan-nya, sebagai pecahan dua komplemen
eksponen
bilangan bulat dua komplemen yang memberikan pangkat dua yang dikalikan dengan mantisa
dinormalisasi
bilangan floating-point yang mantisanya dimulai dengan 01 (positif) atau 10 (negatif), sehingga tidak ada bit yang terbuang pada nol atau satu di depan
overflow
hasil yang terlalu besar untuk direpresentasikan dalam jumlah bit yang tersedia
underflow
hasil non-nol yang terlalu kecil untuk direpresentasikan, sehingga disimpan sebagai nol
kesalahan pembulatan
perbedaan antara bilangan riil dan nilai terdekat yang dapat disimpan oleh representasi biner
13.3
Exam tips · Tips ujian
English
Pseudocode declarations are marked line by line: TYPE ... = (...) for enumerated, TYPE ... = ^... for pointer, TYPE ... = SET OF ... then DEFINE ... (...) : ... for a set, TYPE ... DECLARE ... ENDTYPE for a record, CLASS ... PRIVATE ... PUBLIC PROCEDURE NEW ... ENDCLASS for a class.
Match the type to the data: fixed named values, enumerated; a group of different fields, record; a collection of unique values, set; data plus behaviour, class; an address, pointer.
File organisation is how records are stored; file access is how they are found. Serial and sequential are read sequentially; random files use direct access via a hash of the key. Sequential search of a sequential file can stop early; of a serial file it cannot.
Random-file pseudocode: OPENFILE ... FOR RANDOM, SEEK before every GETRECORD or PUTRECORD, CLOSEFILE at the end. Say how a collision is resolved when you describe hashing.
Floating point: mantissa as a two's-complement fraction (point after the sign bit), exponent as an integer, multiply by $2^{\text{exponent}}$; shift left and subtract one from the exponent to normalise; the mantissa buys precision, the exponent buys range.
The three "explain" stock answers: why normalise (precision, unique form, range), the effect of re-allocating bits (precision against range), and why $0.1$ cannot be stored exactly (an infinite binary fraction in a finite mantissa).
Common mistakes
Writing DECLARE instead of TYPE for a new type, or leaving out ENDTYPE; declaring a set without SET OF, or an enumerated type with quotation marks round its values.
Putting the sign of a floating-point number in the exponent; the sign is the first bit of the mantissa.
Reading a negative mantissa as if it were sign-and-magnitude; it is two's complement, so 1011000000 is $-0.625$, not $-0.375$.
Shifting the mantissa to normalise without changing the exponent, or changing it the wrong way (shift left, exponent down).
Describing a random file as "in random order"; the records are at addresses computed from their keys.
Saying sequential access reads "the whole file" for a sequential file; it stops when a larger key is met.
Explaining hashing without saying what the calculated value is used for (the address to store and retrieve the record), or without a way of handling collisions.
Defining overflow as "too many digits" instead of a result beyond the largest representable value, or blaming the mantissa for it.
Bahasa Indonesia
Deklarasi pseudocode diberi nilai per baris: TYPE ... = (...) untuk enumerated, TYPE ... = ^... untuk pointer, TYPE ... = SET OF ... kemudian DEFINE ... (...) : ... untuk set, TYPE ... DECLARE ... ENDTYPE untuk record, CLASS ... PRIVATE ... PUBLIC PROCEDURE NEW ... ENDCLASS untuk class.
Cocokkan tipe dengan datanya: nilai bernama tetap, terenumerasi; kelompok bidang berbeda, rekaman; kumpulan nilai unik, set; data ditambah perilaku, kelas; sebuah alamat, pointer.
Organisasi file adalah bagaimana rekaman disimpan; akses file adalah bagaimana mereka ditemukan. Serial dan sekuensial dibaca secara sekuensial; file acak menggunakan akses langsung melalui hash dari kunci. Pencarian sekuensial pada file sekuensial dapat berhenti lebih awal; pada file serial hal itu tidak bisa.
Pseudokode file acak: OPENFILE ... FOR RANDOM, SEEK sebelum setiap GETRECORD atau PUTRECORD, CLOSEFILE di akhir. Jelaskan bagaimana tabrakan diselesaikan ketika Anda mendeskripsikan hashing.
Floating point: mantisa sebagai pecahan dua komplemen (titik setelah bit tanda), eksponen sebagai bilangan bulat, kalikan dengan $2^{\text{exponent}}$; geser ke kiri dan kurangi satu dari eksponen untuk menormalisasikan; mantisa membeli presisi, eksponen membeli jangkauan.
Tiga jawaban "jelaskan" standar: mengapa dinormalisasi (presisi, bentuk unik, jangkauan), efek mengalokasikan ulang bit (presisi melawan jangkauan), dan mengapa $0.1$ tidak dapat disimpan secara eksak (pecahan biner tak hingga dalam mantisa terbatas).
Kesalahan umum
Menulis DECLARE alih-alih TYPE untuk tipe baru, atau melewatkan ENDTYPE; mendeklarasikan set tanpa SET OF, atau tipe terenumerasi dengan tanda kutip di sekitar nilainya.
Memasukkan tanda bilangan floating-point ke dalam eksponen; tanda adalah bit pertama dari mantisa.
Membaca mantisa negatif seolah-olah itu sign-and-magnitude; itu adalah dua komplemen, jadi 1011000000 adalah $-0.625$, bukan $-0.375$.
Menggeser mantisa untuk menormalisasi tanpa mengubah eksponen, atau mengubahnya dengan cara yang salah (geser ke kiri, eksponen turun).
Mendeskripsikan file acak sebagai "berurutan secara acak"; rekaman berada pada alamat yang dihitung dari kuncinya.
Mengatakan akses sekuensial membaca "seluruh file" untuk file sekuensial; ia berhenti ketika kunci yang lebih besar ditemui.
Menjelaskan hashing tanpa mengatakan apa nilai yang dihitung digunakan untuk (alamat untuk menyimpan dan mengambil rekaman), atau tanpa cara menangani tabrakan.
Mendefinisikan overflow sebagai "terlalu banyak digit" alih-alih hasil melebihi nilai terbesar yang dapat direpresentasikan, atau menyalahkan mantisa atasnya.
Interactive lessons on this topic · Pelajaran interaktif untuk topik ini
Work through it step by step, with instant-check exercises. · Kerjakan langkah demi langkah, dengan latihan pengecekan instan.
Pick one and the site follows you — notes, papers, videos and practice all open on it. · Pilih satu dan situs mengikuti Anda — catatan, kertas, video, dan latihan semua terbuka di sana.
Type to search notes, lessons, code, vocabulary and past-paper questions across every subject. · Ketik untuk mencari catatan, pelajaran, kode, kosakata, dan pertanyaan soal lama di setiap mata pelajaran.
![Array empat rekaman ClubMember digambar sebagai baris bidang, dengan callout Members[3].LastName memilih satu bidang dari satu elemen, dan assignment menulis satu bidang dari elemen lain](/handout-media/a_level_computer_science/assets/13-array-of-records.png?v=1788672854)
