IB DP Computer Science Paper 1 Theory - all sets combined

Original work belongs to their authors on Quizlet - topics 2-7: elijahoogz topic 1: pwalton78

Explain why cache memory can speed up the processing within a computer [2M]

Cache memory can be accessed/is faster than RAM;

It is used to hold common/expected/frequently used data/operations;

Closer to CPU than RAM/situated between RAM and CPU/on same board as CPU/with faster read/write speed;

Cache memory is static RAM and this memory doesn't need to be constantly refreshed;

One of the functions of an operating system is memory management.

Describe how this function prevents the system from crashing when more than one program is run at the same time [2M]

The OS allocates (and deallocates) specific sections of memory to each program/process/module;

This ensures that the memory assigned to one program is not overwritten;

Uses secondary/virtual memory to allow more processes to run simultaneously;

Outline how truth tables can be used to test that any two logic diagrams are equivalent [2M]

Two truth tables can be compared;

The same outputs from the same inputs, the circuits are equivalent;

State where all instructions and data are stored [1M]

Primary memory / RAM

The machine instruction cycle is the process by which a program instruction is fetched, decoded, executed and the results are stored.

Outline the role of the data bus and address bus in this process [2M]

The data bus transports data from/to CPU,

whereas the address bus the memory address where the data is supposed to go/be;

Define the term bit [1M]

Binary digit;

Smallest unit of storage that can be set to 0 or 1;

An application package used in an office includes a word processor.

Describe how a spellchecker checks whether a word in a text file is correctly spelt or not [2M]

Each word in the text file is compared with words in a dictionary;

If the word is found in the dictionary it is correctly spelt / if the word is not found in the dictionary, spellchecker will recognize that it is incorrectly spelt;

Identify two functions of the operating system [2M]

Memory management;

Resource allocation / Resource and Hardware management;

Booting / bootstrapping;

Loading and execute / provide service for applications software;

Disk/File system management;

Data security;

Provides a user interface to other levels of the machine;

etc.

Outline the role of the memory data register in the machine execution cycle [2M]

Holds the contents of the memory;

Which are to be transferred from/to memory to/from other CPU components;

Allowing the processor and memory to act independently/processor not affected by differences in the speed of operation;

Calculate how many different colours can be represented using two hexadecimal characters [2M]

2 hex = 4 + 4 = 8 bits; hence 2^8 or 16^2 = 256 colours;

Explain the importance of the memory management function of an operating system [3M]

The function of the memory management [1].

An example if its use [1].

Reason for the importance [1].

Example:

Allocates and de-allocates memory/ assigns blocks of memory to programs;

Ensures a program has sufficient memory to run/manages virtual memory if needed;

To avoid overwriting /clashing of programs/optimise system performance/maximise memory usage

Distinguish between random access memory (RAM) and read only memory (ROM) [3M]

RAM acts as temporary storage of data, instructions and programs currently running (for the operating system and for the running applications) whilst ROM is permanent memory (stores the instructions and data that won't change/stores the instructions that the computer needs in order to boot up;

Memory access, both read and write operations are performed on RAM whilst ROM works with read only operation;

If power failures happened during access to RAM then all data will be permanently lost/RAM is volatile memory/whilst if power failure happened during the ROM access no data will be lost/ROM is non-volatile memory;

Explain the roles of the data bus and the address bus in the machine instruction cycle [4M]

Bus is defined as a system that transfers data between hardware components/data bus and address bus enable a processor to communicate with the primary memory;

When the computer processor needs to fetch an instruction from the memory it uses the address bus to specify the address (of the memory block it needs to access);

It will get the data from (the specific) memory (block) (after checking the address bus to get the read address);

And then it will place this data on to the data bus/data bus carries the data;

When the processor wants to store results of execution to the memory it will set the write address on the address bus;

And put the data/results/to be written to memory on to the data bus;

State how the data stored in the following byte will be represented in hexadecimal: 0 1 0 1 1 1 1 0 [1M]

5E

State how many integers could be represented a byte [1M]

2^8 = 256

Outline why a byte could not be used to represent characters such as those used in Chinese [2M]

The characters must be represented as numbers so that computer can deal with them;

One byte (gives us the ability to represent only 256 characters) is enough to hold every possible character in a language which uses a limited set of text symbols, punctuation marks and special characters (for example, English, Spanish, etc);

Chinese exceeds the 256 character limit and therefore requires more bytes to represent all of the characters in this language;

Identify two features of a graphical user interface (GUI) [2M]

Menus;

Dialogue boxes;

Windows;

Icons;

Pointers;

Buttons;

Outline the purpose of the memory address register (MAR) in the central processing unit (CPU) [2M]

The MAR holds the memory location of data/instructions;

that need to be accessed (read/write) (fetch/store);

Identify two characteristics of RAM [2M]

RAM is volatile/ contents erased when power is switched off;

Access speed is fast / faster than hard drive;

Data / instructions can be read from and written to it//RAM can be overwritten;

Size is limited;

A company that provides training for teachers plans to set up a training room in its offices with a network of 15 computers. Each computer has 1TB of storage and 16GB of random access memory (RAM).

State the purpose of persistent storage on the computers [1M]

To store programs / files / data in a non-volatile device so it isn't lost;

Stores more data as it has a larger capacity;

In order to minimize costs, the company decided only to install general application software on the training computers.

Identify two types of general application software that would be installed on the training computers [2M]

Word processor;

Spreadsheet;

Database management system;

Email;

Web browser;

Explain the purpose of cache memory [3M]

Cache memory is a memory that a computer microprocessor can access more quickly than it can access regular RAM;

It is integrated directly with the CPU chip or placed on a separate chip which has a separate bus interconnect with the CPU;

and stores frequently used data only until a computer is powered up;

Thus, when a processor requests data that already has an instance in the cache memory;

it does not need to go to the main memory or the hard disk to fetch the data;

Cache memory is a small-sized type of volatile computer memory; that provides high-speed data access to a processor; and stores frequently used computer programs, applications and data;

Cache memory can be primary or secondary cache memory, where primary cache memory is directly integrated to the processor; And secondary cache memory is a reserved portion on a disk stores and provide access to frequently accessed data/applications from the disk.

State why hexadecimal numbers are frequently used in computing [1M]

Hexadecimal numbers are used for shorter representation of data because a (modern) byte can be represented exactly by two hexadecimal digits;

Hexadecimal numbers are used for shorter representation of data, because computers store and handle binary digits, and four binary digits make one hexadecimal digit;

State the number of bits used to represent a non-primary colour, such as yellow [1M]

24

State the maximum number of colours that can be represented in a computer pixel [1M]

256 x 256 x 256 or (2^8 )^3 or 2^24; 256^3 ;

= 16 777 216;

Explain the role of the operating system (OS) in terms of managing the hardware resources [4M]

Thus the role of OS is:

to keep track of who is using which resource;

to grant resource requests;

to mediate conflicting requests from different users/programs;

to allocate time to different programs or different users/ each one gets their turn to use that resource (for example printer);

to allocate space for different users, each one gets a part of the resource (for example sharing main memory/ hard disk);

Outline one feature of a word processor that could reduce the amount of typing required when writing letters [1M]

Auto-correct/short sequences/codes; can be used to represent longer phrases;

Mail merge; allows production of many letters by only typing the (body of a) letter once;

Voice recognition; allows easy entry of text;

State the part of the central processing unit (CPU) that performs the decoding [1M]

CU/Control Unit

A company promotes its products online. To make a purchase, customers are required to register with the company and provide data like their name, date of birth, age, gender and email address. Once registered, more than one customer is able to access the server to retrieve and modify their data at the same time.

State where the customer data is held during the process of modifying their data [1M]

RAM/primary memory;

It's held by the process/thread handling the customer access, which may be in RAM or in other storage if the process is swapped out while handling the access;

A company promotes its products online. To make a purchase, customers are required to register with the company and provide data like their name, date of birth, age, gender and email address. Once registered, more than one customer is able to access the server to retrieve and modify their data at the same time.

Explain how the operating system ensures that each customer's data is secure when multiple users are accessing the data at the same time [4M]

OS (memory management function) allocates / deallocates memory to each process/customer task, and guarantee each customer task the resources it needs to run correctly;

moves processes back and forth between main memory and secondary memory during execution to prevent overwriting / accidental interchange;

OS (hardware memory protection- part of an OS) isolates/protects customer's data/applications;

and control access rights to the specified memory area (for example, prevents write access to the memory which is not allocated to the process/ customer task);

and protects data / applications when in memory / RAM from malicious code (prevents attempts to execute the contents of the partition/ allocated memory)

Calculate the denary (base 10) equivalent of the hexadecimal number BF [2M]

11 x 16 + 15;

= 191;

Identify any two of the layers of the OSI model [2M]

Physical layer;

Data link layer;

Network layer;

Transport layer;

Session layer;

Presentation layer;

Application layer;

Explain how compression of data may lead to negative consequences [3M]

Some compression methods (lossy) discard data;

Decompression will not return the complete file/some detail will have been removed;

Which in some cases eg audio/video may be unacceptable;

If original not saved/lost there is no way to recover it;

Explain how the use of media access control (MAC) addresses can improve security [3M]

The MAC address identifies a specific device (network card/controller);

MAC address checked against list of approved addresses/whitelist If not on list access to network is denied;

Prevents unauthorised access/makes access more difficult/(unless the NIC is cloned)/providing an extra layer to authentication process;

data sent to a specific MAC address can only be accessed on that device;

Identify one hardware component of the WLAN, other than computers [1M]

Wireless router/modem;

Access points;

Switch;

Wireless repeater/extender/booster;

A wireless local area network (WLAN) is used to extend access to a school's wired local area network.

The advantages of this WLAN are user-mobility and economical access points.

Outline two disadvantages of this WLAN [4M]

Data transfer will decrease (compared with a wired LAN); Because the number of computers using the network increases; (and because) WLAN has lower bandwidth than a wired LAN;

Less data security; As devices from outside the school can access the network/intercept transmissions;

More easily open to misuse; As teacher/administrator cannot directly monitor a specific student/teacher/ machine;

Intermittent connectivity due to physical barriers (walls); Results in low transfer/speed and may hinder operations.

Identify three ways in which the network administrator can reduce the risk of unauthorized access to confidential data [3M]

Give each user appropriate login details/passwords;

Different access rights for students, teachers, school administrators (file-level and share-level security);

All passwords and files /disk should be encrypted;

Use the latest Wi-Fi protocol/WPA2;

Require MAC address authentication;

Password protect the documents;

Define the term protocol [1M]

Set of rules for data transmission

Explain how data is transferred by packet switching [6M]

Example of general description:

Data is organized in specially formatted units (data packets) which are routed from source to destination using network switches and routers;

Network switches and routers determine how best to transfer the packet between a number of intermediate devices (routers and switches) on the path to its destination (rather than flowing directly over a single wire on the path to its destination);

Data packets are reassembled at the destination;

Example of referencing content:

Addresses have to be in a standard format so that each switch/routing station recognizes the address; Address of sender identifies the sending computer, so that any packets not received can be re-requested;

Address of receiver identifies intended recipient so it can be forwarded on correctly;

The protocol used must be identified so that the correct rules are followed;

Size of packet / size of fields in packet - All packets/fields must have the same size so that the data can be reassembled;

Sequence number so that packets can be reassembled in correct order;

Transmission codes to show whether the data packet is transmitted or re-transmitted;

Control bits, to maintain the integrity of the data by ensuring that the data received is the same as the data sent;

Error checking code - when an error is detected, an algorithm either corrects the error or requests that the packet is resent;

After 5 years a company decided to replace the LAN with a wireless local area network (WLAN).

Outline two advantages, to this company, of installing a WLAN [4M]

Award [1] for stating an advantage, [1] for expansion/example in context.

Answers may include:

Use on the move;

More versatile staff encouraged to collaborate etc.;

Allows BYOD(bring your own device):

Which could lead to greater productivity (as familiarity with device);

No extra equipment is needed for expansion after initial set-up; Which will save the company time and money;

Reduces wiring;

Therefore improved safety for employees;

The company is considering expanding their network to allow employees to connect from anywhere in the world. The expanded network would need to provide security and allow the employees full functionality of the internal network.

Explain how setting up a virtual private network (VPN) would provide a suitable solution [4M]

A VPN/ tunnelling allows the employee's device to appear to be part of / a node of the internal company network;

Thus affording him/her full access to the network resources;

Data that passes through a VPN can be encrypted;

So any unauthorized access will not be able to understand the data;

Tunnelling allows the company's own protocols to be used/IPsec/TSL ensure security;

Even though the data is passing over an outside network;

Multiple exit nodes / hidden IP addresses/encrypted connections;

Make it hard to distinguish where the data was generated;

Outline what is meant by the term computer network [2M]

A group of computers and other computing hardware devices that are linked together through communication channels/cables/wirelessly;

To enable communication (sharing files, sharing information) between systems/among a wide range of users;

Describe one problem resulting from low bandwidth in a computer network [2M]

Bandwidth indicates the maximum amount of data that can be transferred from one point to another in a unit of time;

Low bandwidth means slow network performance / extended duration when transferring large amounts of data / loss of users' time (money) / the whole area (of the users) is not covered;

Outline how a virtual private network (VPN) will allow employees who are in Europe to communicate with the Head Office in Asia [2M]

VPN allows secure communication with the Head Office in Asia;

A VPN is the company's private network that uses a public network (in this situation the Internet) to connect remote sites/employees together;

Privacy is protected using VPN tunnelling;

VPN uses encrypted connections routed through the Internet from the company's private network (Europe)to the remote site in Asia (or employee);

Hiding IP addresses to prevent unwanted exposure and data leaks;

Data security is ensured by encryption - anyone intercepting the encrypted data cannot read it;

Describe how data is transmitted by packet switching [4M]

Packet switching entails data being separated into specially formatted units (packets);

Each packet contains data and information such as packet number, address that identifies the sending computer and intended recipient, etc;

Packets are routed from source to destination using (different) network switches and routers;

Using these addresses, network switches and routers determine how best to transfer the packet on the path to its destination;

Packets are reassembled at the destination (using packet numbers);

If any of packets is missing it should be retransmitted;

The company also uses the internet to enable communication with employees working on exploration and production in many remote geographical areas.

Identify one network security measure [1M]

Encryption;

UserID;

Trusted MAC addresses;

Identify two characteristics of a personal area network (PAN) [2M]

Smallest type of network;

Consists of connected devices in close proximity to the individual using them;

Connected via Bluetooth/wireless;

Suitable example: smartphone to car connection;

Outline one reason why protocols are used in communications between computers [2M]

To provide a set of rules/procedures;

To enable two or more different electronic devices/computers/entities to understand each other during data transfer / enable successful communication;

Describe one method of security that may be used on this wireless network [2M]

Encryption; Scrambles the contents of the network transmissions so that if they are intercepted they can't be understood (without the decryption key);

User ID (and password); Only allows authorized users to access the network;

Media Access Control (MAC) addresses; Unique identification codes embedded in networkable equipment so that only authorized equipment may access the network;

Firewall; Checks traffic coming into the network and leaving the network, and can block suspicious data;

Explain why the speed of data transmission on a wireless network may vary [4M]

The speed of data transmission (on a wireless network) slows down;

The further the receiver is from the transmitter;

Passing through obstructions such as solid walls; Can slow down transmissions (on a wireless network);

The bandwidth available for transmission on a wireless network is finite; So, transmission speeds can be affected if the number of users on the network increases;

Outline two advantages of a school using a computer network [4M]

File sharing/resource sharing;

instead of using a disk or USB key to carry files from one computer to another, files can be shared directly using a network/all computers in the network can share resources such as printers, scanners;

Communication;

students/teachers can communicate with people around the world via the network; Interactive teamwork; software (like Microsoft Office) enables many users to contribute to a document concurrently;

Flexible access;

network allows students to access files from different computers (throughout the network) (one can begin work on a project on one computer and finish up on another);

Software cost;

software products are available for networks at a substantial savings in comparison to buying individually licensed software;

Software management;

load software on the server saves time compared to installing and tracking files on independent computers/upgrades are also easier because changes only have to be done once on the file server instead of on individual computers;

Improved network security;

if the school has its own network, it can monitor network traffic / can create a security culture (everyone who has a username and password is responsible for keeping data secure);

Describe the purpose of a router [2M]

A network router is a hardware device that is connected to multiple channels for different networks; through an interface that is situated on each network;

Router acts as a processing unit for information packets; it duplicates information packets for use during transmission from one network to another;

The router uses a protocol or set of rules; to determine which information packets are to be routed to certain interfaces within the network;

Describe the purpose of a Network Interface Card [2M]

Network interface cards are used to connect each computer to the network; so they can communicate with the network router to receive information packets;

Interface cards determine the infrastructure of a local area network (LAN); and allow all of the computers to connect to the network;

Outline why protocols are necessary [2M]

Protocols define the rules that govern network communication (for example, packet format, type and size, what happens when an error occurs, and which part of the network is supposed to handle the error and how);

Computer networks consists of various types of equipment (such as routers, switches, hubs and network interface cards) and the equipment comes from different vendors, but they must all work together or the network does not operate correctly;

Protocols work in layers (the highest being what the user sees, and the lowest being the wire that the information is transferred along) and these layers communicate with each other according to the rules (allowing communication to occur accurately and efficiently);

Define the term data encryption [1M]

Data encryption refers to calculations/algorithms that transform plain text into a form that is non-readable to unauthorized parties (authorized recipient of an encrypted text uses a key and the algorithm to decrypt the data/ to transform it to the original plain text version);

Evaluate the use of trusted media access control (MAC) addresses as one method of network security [4M]

Each (wireless network) adapter has a unique label called a MAC address;

Routers uses these addresses to identify/authenticate computers (routers include an option to whitelist or blacklist certain devices based on MAC addresses, so access could be restricted to any device which is not in the whitelist);

One disadvantage is that the whitelist should be amended any time a new device is purchased / when access to guests should be granted;

Also this method is useless against hackers who use programs which intercept data passing through network and report the MAC address of any device communicating on the network;

A school has a local area network (LAN) connecting its computers and peripheral devices. The LAN also provides access to the internet.

Describe the role of a router in this network [3M]

controls the flow of data in the network;

inspects address of data packets;

directs to the appropriate network path/ selects a path between networks (by inspecting address of data packets);

securely transmits data packets (across that path toward the intended destination);

Users have been troubled by slow speeds when accessing the internet.

Outline two reasons why there might be a reduction in data transmission speed at certain times [4M]

malicious software/spyware/malware / viruses; attacking the system;

the type of connection;

valid outline for the slow down (depending on the type of connection);

hardware malfunction;

internet speed can considerably slow down if modem-router configuration is not correct / updated;

external factors;

during the peak hours of daytime the most visited websites encounter more network traffic than what has been anticipated;

Outline two measures that a school could take to safeguard its data from unlawful access via the internet [4M]

Preventing unauthorized access/No access without user names/passwords;

which should be regularly changed/made difficult to guess;

Data should be encrypted;

Allowing only those with decrypting code access;

Teachers/students should be trained for safe practices;

to create a risk-conscious /security-aware culture within the school;

Installation of virus checkers/spyware software; to prevent damage to data files or the system / to prevent data being extracted from the files/system;

Identify two roles that a computer can perform in a network [2M]

Client;

Server/email server/DNS server/file server;

Router;

Firewall;

Identify two reasons why fibre optic cable would be preferred over wireless connectivity [2M]

Fibre optics allow faster transmission speeds;

Fibre optic cables are more secure/harder to break into;

Fibre optic cable transmission is more reliable/less likely to suffer interference;

Fibre optics allow transmission over longer distance;

Fibre optics allow greater bandwidth;

A school currently has a cabled network but wants to add wireless networking across the whole campus.

Describe two hardware components the school will need to implement the wireless network [4M]

(Wireless) router; A central hub for all the computers to connect to; Enables wireless network packet forwarding and routing;

Wireless Network Interface Card (NIC); To allow the computer to 'talk to' the (wireless) router;

Wireless access points; allow Wi-Fi devices to connect to a wired network;

Wireless repeaters; To expand the reach of the network;

Identify two advantages to the students of a new wireless network [2M]

The ability to use their own devices at school;

The ability to access the school network from anywhere in the school;

No cables laid, so reduces the risk of tripping over cables;

Numbers of connections are not limited to cable ports, so greater numbers of students can connect at any given time;

The school has decided to implement a virtual private network (VPN) to provide access to its network.

Identify two technologies a school would require to provide a VPN [2M]

Client VPN software (to make a secure remote connection);

VPN-aware routers and firewalls (to permit VPN traffic to pass);

VPN appliance/server (to handle incoming VPN traffic);

Encryption protocol IPSec or SSL;

Explain one benefit to staff of using a VPN to remotely access a school network [3M]

Enhanced security of data;

for example, using encryption;

This prevents unauthorised access;

Remote access to data and resources (from any location);

Normal access of materials on the network;

as though the user was using the network on site;

Wciąż się uczę (1)

Pojęcia, których już się uczysz. Tak trzymaj!

Identify the components of a node in a doubly linked list [3M]

Data;

A pointer/reference to the previous node;

A pointer/reference to the next node;

Outline the reason why recursive solutions can be memory intensive [2M]

A recursive call involves the use of stacks; For storing/pushing on/popping out data/ return addresses/return values etc;

If many recursive calls are made, the memory usage can be very large;

Outline the steps involved in performing a binary search on an array of ascending numbers [4M]

Note: you can assume that the search value is present in the array and that initially LOW is the index of the first value in the array and HI is the index of the last value.

A position/index of the middle value calculated from HI and LOW;

If search value equals to value in the array at this position, then end;

Otherwise, change HI or LOW according to whether search value is above or below;

Repeat the process until search value is found;

A collection called NUMBERS is to be searched to see if it contains a specified value.

Construct an algorithm in pseudocode to perform the following:

1. input the number, S, to be searched for

2. read in the values from the NUMBERS collection into the array D. (Note: you can assume that the array is large enough and that the collection is not empty)

3. perform a linear search for S on the array D

4. output the message "found" or "not found" as appropriate.

[5M]

[1] mark for a loop through collection NUMBERS

[1] mark for the assignment into the array

[2] marks for a correct linear search,

[1] mark for the loop and [1] mark for the comparison and use of flag

[1] mark for correct input of search value and output message

Example Answer:

input S // search item

COUNT = 0

FOUND = false

loop while NUMBERS.hasNext() // or ... while not NUMBERS.isEmpty() //

D[COUNT] = NUMBERS.getNext()

if S == D[COUNT]

FOUND = true

end if

COUNT = COUNT + 1

end loop

if FOUND

output "found"

else

output "not found"

end if

A binary search can be performed on the array D, if the values in D are in ascending order. As the values are being read from NUMBERS into D they are checked to see if they are in order.

Without writing pseudocode, suggest how this check could be performed. [3M]

[1] mark for setting and changing a flag

[1] mark for starting from the 2nd entry and checking all values as being entered

[1] mark for comparing the current value with the previous one

One of the laptop's game applications stores the data relating to the different actions of one of its characters in a stack.

Suggest one reason why the character's actions might be stored in a stack [2M]

A stack is a LIFO data structure;

In the game it allows the "undo" function to work / movements/steps can be retraced;

At specific moments during a game data is read from the stack (S) into a queue (Q).

Using appropriate access methods for stacks and queues, construct an algorithm that reads the data from the stack and enters it into the queue [6M]

(You should assume that the queue structure exists and that both structures are of a fixed size)

Award [1] for while loop;

Award [2] for the correct condition in while statement (stack is not empty and queue is not full) award [1] in case of the minor error;

Award [1] for pop. (Note: Do not allow alternatives) Award [1] for enqueue; (Note: Allow alternatives) Award [1] for the output only if stack is not empty after the loop;

Example Answer:

loop while NOT S.isEmpty() and NOT Q.isFull()

N = S.pop()

Q.enqueue(N)

end loop

if NOT S.isEmpty() //accept NOT S.isEmpty()and Q.isFull()//

output "incomplete process"

end if

Outline one advantage of making a queue dynamic [2M]

A dynamic queue would not have predetermined/fixed size;

Memory is allocated as required/efficient use of memory/flexible size//there is always sufficient memory to accommodate the queue;

The collection WEATHER contains the temperatures that have been measured for one city over the course of one week, starting on Monday and ending on Sunday. Each day, 24 readings were taken, one each hour, the first being at 00:00, the second at 01:00 and so on. The data is stored in chronological order with the data for Monday stored in the collection first, followed by Tuesday and so on.

Construct the algorithm to read this data into a 2D array, A, that would allow the temperature on a specific day at a specific time to be accessed directly [4M]

Example answer 1:

Award [1] for any nested loop.

Award [1] for the correct nested loop.

Award [1] for the correct assignment to A.

Award [1] for the correct retrieval from WEATHER.

loop for DAY from 0 to 6

loop for HOUR from 0 to 23

A[DAY][HOUR] = WEATHER.getNext() // A[DAY][HOUR] = WEATHER.getData() //

end loop

end loop

Example answer 2:

Award [1] for initialization of POS and correct increment within the loop

Award [1] for the correct loop.

Award [1] for the correct calculation of DAY

Award [1] for the correct calculation of HOUR

Award [1] for the correct assignment to A( correct retrieval from WEATHER )

POS=0

loop while WEATHER.hasNext() //accept not WEATHER.isEMPTY()//

DAY=POS div 24

HOUR=POS mod 24

POS=POS+1

A[DAY][HOUR]=WEATHER.getData() // WEATHER.getNext()//

end loop

The collection WEATHER contains the temperatures that have been measured for one city over the course of one week, starting on Monday and ending on Sunday. Each day, 24 readings were taken, one each hour, the first being at 00:00, the second at 01:00 and so on. The data is stored in chronological order with the data for Monday stored in the collection first, followed by Tuesday and so on.

Construct the algorithm that will output the day, as a word (for example Tuesday), on which the highest temperature was recorded [6M]

Award [1] for initialization of HIGHEST.

Award [1] for the correct outer loop

Award [1] for the correct inner loop

Award [1] for the correct comparison and assignment of HIGHEST

Award [1] for the assignment MAX_DAY within if statement

Award [1] for the if statement after the outer loop (accept switch statement)

Award [1] for the correct output statement (may be written within if statement)

Example Answer:

HIGHEST = A[0][0] //accept for example HIGHEST=-1000//

loop for DAY from 0 to 6

loop for HOUR from 0 to 23

if A[DAY][HOUR] > HIGHEST

HIGHEST = A[DAY][HOUR]

MAX_DAY = DAY

end if

end loop

end loop

if MAX_DAY == 0 then

D = "Monday"

else if MAX_DAY == 1 then

etc....

end if output D

The collection WEATHER contains the temperatures that have been measured for one city over the course of one week, starting on Monday and ending on Sunday. Each day, 24 readings were taken, one each hour, the first being at 00:00, the second at 01:00 and so on. The data is stored in chronological order with the data for Monday stored in the collection first, followed by Tuesday and so on.

This is extended so that each week the value and date of the highest temperature recorded that week are stored chronologically in a collection, HIGHEST. At any point in time, the data from the HIGHEST collection can be read into a suitable data structure that will allow the details of the highest temperatures recorded to be output in descending order. The structure is chosen in order to minimize processing.

Explain how a suitable data structure can be constructed and used for this purpose [4M]

Note: Do not give any marks if the proposed structure is not dynamic.

A binary search tree could hold a series of nodes each of which contains the data for each reading;

and two pointers (to the left and right child);

Each node is inserted according to the temperature, higher temperature to the left, lower to the right;

An in-order traversal would output the data sorted in descending order of temperature;

Note: Linked list would not minimise processing but should get credit.

Identify two essential features of a computer language [2M]

Fixed vocabulary;

Unambiguous meaning;

Consistent grammar;

Consistent syntax;

Provide a way to define basic data types and operations on those types (ability to write functions/procedures);

Provide ability of Input and output handling;

Provide some kind of loop that can be stopped / conditional statement / branching (conditional and unconditional branching);

It should have variables that reference computer memory, syntax for basic arithmetic and logical operations on those memory locations;

It has to run on/be processed by a computer (i.e. it must have a compiler/interpreter);

Consider the following recursive method, where N is a positive integer:

mystery(N)

if (N > 0) AND (N mod 2 = 0) then

mystery(N−2)

end if

output N

end mystery

Determine the output produced by the method call mystery(5) [1M]

5;

Consider the following recursive method, where N is a positive integer:

mystery(N)

if (N > 0) AND (N mod 2 = 0) then

mystery(N−2)

end if

output N

end mystery

Determine the output produced by the method call mystery(4) [3M]

0

2

4

Consider the following recursive method, where N is a positive integer:

mystery(N)

if (N > 0) AND (N mod 2 = 0) then

mystery(N−2)

end if

output N

end mystery

Construct an iterative algorithm for the method mystery(), which uses a single while loop instead of recursion [4M]

Award marks as follows up to [4 max]. (There are 5 marking points);

Award [1] for determining whether N is odd/even; Award [1] for correctly initializing and changing the value of the loop controlling variable (K);

Award [1] for the correct condition in while loop (note K < N);

Award [1] for output within the loop for an even N; Award [1] for outputting N after the loop;

Example Answer:

mystery(N)

K = 0

loop while (K < N) AND (N mod 2 = 0)

output K

K = K + 2

end loop

output N

end mystery

One of the methods in a software is findFirst(CH, CHARARRAY) which accepts a character, CH, and a one-dimensional array of characters, CHARARRAY, and returns the position of the first occurrence of character CH in CHARARRAY. It returns −1 if CH does not appear in the array CHARARRAY.

For example, consider the character array MESSAGE, which is of length 19.

For this array:

1. The character at position 8 in the sentence is "U" and hence MESSAGE[8] = "U".

2. The character at position 18 in the sentence is "." and hence MESSAGE[18] = ".".

3.The method findFirst('A', MESSAGE) returns 0.

4. The method findFirst('S', MESSAGE) returns 9.

5. The method findFirst('Z', MESSAGE) returns −1.

Construct an efficient algorithm for the method findFirst(). You should use the function len(), which returns the number of characters in an array (for example, len(MESSAGE) returns 19)

[6M]

Award [1] for correctly initializing and changing indexes in MESSAGE (variable K);

Award [1] for comparing CH with the character at position K in MESSAGE;

Award [1] for terminating the while loop when there are no more characters to check (Accept 19 instead of len(MESSAGE));

Award [1] for terminating the loop when CH is found in MESSAGE;

Award [1] for correctly returned value of POS when CH does not appear in MESSAGE. (Note: output not accepted);

Award [1] for correct assignment (or value) of POS when CH appears in MESSAGE;

Example Answer:

POS = -1

FOUND = false

K = 0

loop while (K < len(MESSAGE)) AND (NOT FOUND)

if MESSAGE[K] = CH then

FOUND = true

POS = K

end if

K = K + 1

end loop

return POS

Describe the features of a dynamic data structure [2M]

Each node contains data and also a link to other nodes;

Links between nodes are implemented by pointers (a pointer references a location in memory or holds a memory address);

List size is not fixed / predetermined;

Define the term recursion [1M]

Process/method/ procedure/ subroutine/ function/ algorithm that calls itself

Describe the characteristics of a queue [2M]

FIFO data structure;

Items can be added only to one end (rear/tail) and removed from the other end (front/head);

Compare the use of a linked list with an array to store and process the daily sales in a business [3M]

Award [1] for size comparison.

Award [1] for access comparison.

Award [1] for relation to the given scenario.

Example:

Size/length of a static array is predetermined/fixed / size of a linked list can be changed / size of a linked list depends only on memory available;

Linked list can be expanded to suit the daily sales;

Each item in a static array can be directly accessed whilst access to the items in a linked list is sequential;

And searching for the given item in the linked list is slower /an item in the linked list cannot be searched for using binary search;

A medical centre uses a computer system to manage both patients' data and appointments. This system, which is used by the doctors, nurses and secretaries, has two unordered files: a patients' file and an appointments' file, both of which can only be accessed sequentially.

Every evening the following processing takes place:

• a list of appointments for the next day is printed out

• reminders are sent by SMS text messages to the patients' mobile devices.

Outline the pseudocode that the processing must follow when the system sends out the text reminders [5M]

Award [5 max] as follows:

Iterate through the appointments file;

Check for correct day;

Repeat for each appointment on that day;

Using the patient ID for that appointment;

Iterate through the patients file until record for that ID found;

Retrieve phone number and send out SMS;

Example:

loop for every appointment in the appointments file

if the appointment is for the correct day

Store patient ID

loop until found in the patients file

if patient ID (patients file) = patient ID (appointments file)

get phone number from patient's file to send SMS end if

end loop

end if

end loop

Define the term concurrent processing [1M]

Processes/task are carried out simultaneously/at the same time;

Explain the benefits of using a binary search tree, compared to a stack, when searching for a specific item [3M]

Example answer 1 (time efficiency):

The data in the binary search tree (BST) is ordered;

Such that as each node is checked for the item, half of the remaining nodes are ignored;

But each element in the stack has to be checked; Which, for large data sets, may be inefficient compared to the BST;

Example answer 2 (memory efficiency):

Each element on the stack has to be popped off/removed from the stack to be checked for the searched item;

When the item is found the stack will be empty/stack contents will be changed;

When an element in the BST is checked for the item it is not removed from the BST;

So there is no need to create an additional copy of the BST (but a real copy of the stack must be created which for large data sets may be inefficient);

If the tree is populated with the data from the stack, the first item popped off will become the root. For each subsequent item popped from the stack, a recursive procedure is followed until the item is correctly placed in the tree.

Without writing code, describe this recursive procedure [4M]

The (next) stack item is (placed into a new node and) compared (alphabetically) to the root;

If the root is empty it would be placed here (and this recursive procedure terminates);

Else, depending upon the comparison, it would look to the node to the left or right and the (recursive) procedure calls itself again (with the new root);

If it is lower than the root, then the left child of the root becomes the new root;

If it is higher than the root, then the right child of the root becomes the new root;

Explain the importance of the method isEmpty() when constructing an algorithm which performs operations on a stack data structure [3M]

Method isEmpty() returns True if there are no elements on the stack, False otherwise;

It is important to call this method in logical expression/condition in algorithm constructs such as branches and loops (if/while);

Before popping an element from the stack / popStack();

To prevent errors/stack underflow/program crash;

Outline the need for higher level languages [2M]

High-level language(HLL) provides statements (for example, high level if(...), while(...) , etc) which are not dependent on the specific machine / and ability to create various data structures;

Which saves the programmer's time;

Higher level languages are closer to human language;

So programmers find them easier to understand/work with than lower level languages;

HLL saves programmer from knowing details of computer architecture (and using all the specific (machine) instructions); So giving more time to creating/developing the best way of coding a problem/process of coding is simpler and more understandable;

Explain two benefits of using sub-procedures within a computer program [4M]

Award [1] for an answer stressing the usefulness of sub-procedures in any of the following:

Program organization;

Program coding;

Program testing;

Maintenance;

Etc.

Award [1] for the expansion up to [2 max].

Problem could be divided into smaller/easier parts; Which means solving easier/smaller parts of the problem for one programmer;

Or for a team of programmers, each programmer could work on different smaller parts;

Simpler testing;

Each part of the program could be separately tested; By the programmer who created the code or someone else in the team of programmers;

Reusable code;

Sub-procedures already written/tested could be used in various programs;

Simpler maintenance and changes;

Could be done only on required sub-programs;

Identify three characteristics of a collection [3M]

Award [1] for data structure implementation/objects/elements of collections. Award [1] for algorithms/methods/callback functions. Award [1] for showing that collection reduces programming effort / increases performance (by providing efficient implementations of data structures and algorithms).

Collection is a container of discrete values;

Usually of the same type (primitive data values and also some other data structures);

(But) collection objects can be of different types (pointers afford a flexibility and thus collection objects permit references to any data structure as well as to primitive values);

Collections have a set of methods that define operations performed on the elements/objects of that collection;

Such as adding/removing elements to/from collection, comparing elements of collection, searching, etc;

Which reduces programming effort (because implementations of data structures and algorithms are provided);

Which increases performance of the program (because efficient implementations are provided);

Collection NUMBERS already exists and stores real numbers.

Construct in pseudocode an algorithm, using the access methods of a collection, which will iterate through the collection NUMBERS and count how many elements stored in the collection are in the interval [-1,1]. The final answer should be output [6M]

Award [1] for initialization and for outputting correct result (COUNTER).

Award [1] for using collection methods.

Award [1] for correct loop.

Award [1] for retrieving a number (ELEMENT) from the collection.

Award [1] for if statement within the loop.

Award [1] for correct condition in if statement.

Award [1] for increasing COUNTER if needed.

Example answer:

COUNTER = 0

NUMBERS.resetNext()

loop while NUMBERS.hasNext()

ELEMENT = NUMBERS.getNext()

if ELEMENT >= -1 and ELEMENT <= 1 then

COUNTER = COUNTER + 1

end if

end loop

output COUNTER

The names of vegetables must be always held in alphabetical order in a list in the main memory. The application program should allow insertion and deletion of the names of vegetables from this list.

Compare the use of a dynamic linked list for holding these names of vegetables with a static one-dimensional array [3M]

The size of the dynamic list does not have to be predetermined as in an array;

The size of the dynamic list is not fixed whilst the size of an array is always fixed;

If names are sorted they can be added/deleted (more easily) by changing the pointers without having to shuffle the names;

As records can be dynamically added/deleted the memory is better used because there are no wasted / missing spaces as in an array;

The following method, swap(A,B)is written to exchange the values of variables A and B:

swap(A,B)

TEMP = A

B = TEMP

A = B

end swap

Assume A = 3 and B = 5. State the values of A and B after execution of swap(A,B) [1M]

A = 3 and B = 3;

The following method, swap(A,B)is written to exchange the values of variables A and B:

swap(A,B)

TEMP = A

B = TEMP

A = B

end swap

Suggest how the algorithm used in method swap() would need to be modified to successfully exchange the values of variables A and B [2M]

The algorithm does not correctly swap the values because the value of B is overwritten/lost in the second line of the algorithm;

To obtain the correct result the line B = TEMP should be swapped with the line A = B

or

the order of statements should be changed as follows:

TEMP = A

A = B

B = TEMP

Explain the difference between a dynamic data structure and a static data structure [3M]

Award [1] for stating a feature of a static/dynamic data structure

Award [1] for stating a difference to dynamic/static data structure

Award [1] for an explanation

Memory is allocated to the static data structure in compile time (a pre-set amount of memory/fixed size);

Memory is allocated to the dynamic data structure at run-time;

The size of a static data structure can never change during run-time whilst the size of dynamic data structure can be randomly updated during run time which makes efficient use of RAM;

Memory allocated to the static data structure is always available in order to be used by the data structure and elements can be accessed either directly or sequentially;

Whilst direct access to elements in the dynamic data structure is not allowed and elements should be accessed sequentially;

So in some/most cases algorithms which use dynamic data structures are slower (during execution) than algorithms with static data structures;

Identify one alternative data structure for storing class marks [1M]

Linked list (Collection)

Binary tree;