data representation exam questions

Data representation exercises

Exercises not as directly relevant to this year’s class are marked with ⚠️.

DATAREP-1. Sizes and alignments

QUESTION DATAREP-1A. True or false: For any non-array type X, the size of X ( sizeof(X) ) is greater than or equal to the alignment of type X ( alignof(X) ).

True. This also mostly true for arrays. The exception is zero-length arrays: sizeof(X[0]) == 0 , but alignof(X[0]) == alignof(X) .

QUESTION DATAREP-1B. True or false: For any type X, the size of struct Y { X a; char newc; } is greater than the size of X.

QUESTION DATAREP-1C. True or false: For any types A1 ... An (with n ≥ 1), the size of struct Y is greater than the size of struct X , given:

struct X { A1 a1; ... An an; };

struct Y { A1 a1; ... An an; char newc; };

False (example: A1 = int , A2 = char )

QUESTION DATAREP-1D. True or false: For any types A1 ... An (with n ≥ 1), the size of struct Y is greater than the size of union X , given:

union X { A1 a1; ... An an; };

struct Y { A1 a1; ... An an; };

False (if n = 1 )

QUESTION DATAREP-1E. Assume that structure struct Y { ... } contains K char members and M int members, with K ≤ M , and nothing else. Write an expression defining the maximum sizeof(struct Y) .

QUESTION DATAREP-1F. You are given a structure struct Z { T1 a; T2 b; T3 c; } that contains no padding. What does (sizeof(T1) + sizeof(T2) + sizeof(T3)) % alignof(struct Z) equal?

QUESTION DATAREP-1G. Arrange the following types in increasing order by size. Sample answer: “1 < 2 = 4 < 3” (choose this if #1 has smaller size than #2, which has equal size to #4, which has smaller size than #3).

• struct minipoint { uint8_t x; uint8_t y; uint8_t z; }
• unsigned short[1]

#6 < #1 < #4 < #2 < #3 < #5

DATAREP-2. Expressions

QUESTION DATAREP-2A. Here are eight expressions. Group the expressions into four pairs so that the two expressions in each pair have the same value, and each pair has a different value from every other pair. There is one unique answer that meets these constraints. m has the same type and value everywhere it appears (there’s one unique value for m that meets the problem’s constraints). Assume an x86-32 machine: a 32-bit architecture in which pointers are 32 bits long.

• sizeof(&m)
• 16 >> 2

1—5; 2—7; 3—8; 4—6 1—5 is easy. m + ~m + 1 == m + (-m) == 0 , and m & ~m == 0 , giving us 3—8. Now what about the others? m & -m (#3) is either 0 or a power of 2, so it cannot be -1 (#2). The remaining possiblities are m and 1 . If (m & -m) == m , then the remaining pair would be 1 and -1, which clearly doesn’t work. Thus m & -m matches with 1, and m == -1 .

DATAREP-3. Hello binary

This problem locates 8-bit numbers horizontally and vertically in the following 16x16 image. Black pixels represent 1 bits and white pixels represent 0 bits. For horizontal arrangements, the most significant bit is on the left as usual. For vertical arrangements, the most significant bit is on top.

Examples : The 8-bit number 15 (hexadecimal 0x0F, binary 0b00001111) is located horizontally at 3,4, which means X=3, Y=4.

• The pixel at 3,4 is white, which has bit value 0.
• 4,4 is white, also 0.
• 5,4 is white, also 0.
• 6,4 is white, also 0.
• 7,4 is black, which has bit value 1.
• 8,4, 9,4, and 10,4 are black, giving three more 1s.
• Reading them all off, this is 0b00001111, or 15.

15 is also located horizontally at 7,6.

The 8-bit number 0 is located vertically at 0,0. It is also located horizontally at 0,0 and 1,0.

The 8-bit number 134 (hexadecimal 0x86, binary 0b10000110) is located vertically at 8,4.

QUESTION DATAREP-3A. Where is 3 located vertically? (All questions refer to 8-bit numbers.)

QUESTION DATAREP-3B. Where is 12 located horizontally?

QUESTION DATAREP-3C. Where is 255 located vertically?

DATAREP-4. Hello memory

Shintaro Tsuji wants to represent the image of Question DATAREP-3 in computer memory. He stores it in an array of 16-bit unsigned integers:

Row Y of the image is stored in integer cute[Y] .

QUESTION DATAREP-4A. What is sizeof(cute) , 2, 16, 32, or 64?

QUESTION DATAREP-4B. printf("%d\n", cute[0]); prints 16384 . Is Shintaro’s machine big-endian or little-endian?

Little-endian

DATAREP-5. Hello program

Now that Shintaro has represented the image in memory as an array of unsigned short objects, he can manipulate the image using C. For example, here’s a function.

Running swap produces the following image:

Shintaro has written several other functions. Here are some images (A is the original):

For each function, what image does that function create?

QUESTION DATAREP-5A.

H. The code flips all bits in the input.

QUESTION DATAREP-5B.

QUESTION DATAREP-5C.

The following programs generated the other images. Can you match them with their images?

f3 —I; f4 —B; f5 —C; f6 —F; f7 —G; f8 —A; f9 —E

DATAREP-6. Memory regions

Consider the following program:

This program allocates objects a through g on the heap and then stores those pointers in some stack and global variables. We recommend you draw a picture of the state setup creates.

QUESTION DATAREP-6A. Assume that (uintptr_t) a == 0x8300000 , and that malloc returns increasing addresses. Match each address to the most likely expression with that address value. The expressions are evaluated within the context of main . You will not reuse an expression.

1—D; 2—C; 3—E; 4—B; 5—A Since p has automatic storage duration, it is located on the stack, giving us 5—A. The global variable has static storage duration, and so does its component global.y ; so the pointer &global.y has an address that is below all heap-allocated pointers. This gives us 2—C. The remaining expressions go like this: global.y == e ; p.y == &e[1] , so *p.y == e[1] == (int) &d[100000] , and (int *) *p.y == &d[100000] ; p.x == g , so p.x[0] == g[0] == *g == c , and *p.x[0] == *c == (int) a . Address #4 has value 0x8300000, which by assumption is a ’s address; so 4—B. Address #3 is much larger than the other heap addresses, so 3—E. This leaves 1—D.

DATAREP-7. ⚠️ Garbage collection ⚠️

⚠️ Here is the top-level function for the conservative garbage collector we wrote in class.

This garbage collector is not correct because it doesn’t capture all memory roots.

Consider the program from the previous section, and assume that an object is reachable if do_stuff can access an address within the object via variable references and memory dereferences without casts or pointer arithmetic . Then:

QUESTION DATAREP-7A. Which reachable objects will m61_collect() free? Circle all that apply.

b , f . The collector searches the stack for roots. This yields just the values in struct ptrs p (the only pointer-containing variable with automatic storage duration at the time m61_collect is called). The objects directly pointed to by p are g and e . The collector then recursively marks objects pointed to by these objects. From g , it finds c . From e , it finds nothing. Then it checks one more time. From c , it finds the value of a ! Now, a is actually not a pointer here—the type of *c is int —so by the definition above, a is not actually reachable. But the collector doesn’t know this. Putting it together, the collector marks a , c , e , and g . It won’t free these objects; it will free the others ( b , d , and f ). But b and f are reachable from global .

QUESTION DATAREP-7B. Which unreachable objects will m61_collect() not free? Circle all that apply.

QUESTION DATAREP-7C. Conservative garbage collection in C is often slower than precise garbage collection in languages such as Java. Why? Circle all that apply.

• C is generally slower than other languages.
• Conservative garbage collectors must search all reachable memory for pointers. Precise garbage collectors can ignore values that do not contain pointers, such as large character buffers.
• C programs generally use the heap more than programs in other languages.
• None of the above.

DATAREP-8. Memory errors

The following function constructs and returns a lower-triangular matrix of size N . The elements are random 2-dimensional points in the unit square. The matrix is represented as an array of pointers to arrays.

This code is running on an x86- 32 machine ( size_t is 32 bits , not 64). You may assume that the machine has enough free physical memory and the process has enough available virtual address space to satisfy any memory allocation request.

QUESTION DATAREP-8A. Give a value of N so that, while make_random_lt_matrix(N) is running, no new fails, but a memory error (such as a null pointer dereference or an out-of-bounds dereference) happens on Line A. The memory error should happen specifically when i == 1 .

(This problem is probably easier when you write your answer in hexadecimal.)

We are asked to produce a value of N so that no memory error happens on Line A when i == 0 , but a memory error does happen when i == 1 . So reason that through. What memory errors could happen on Line A if malloc() returns non- nullptr ? There’s only one memory operation, namely the dereference m[i] . Perhaps this dereference is out of bounds. If no memory error happens when i == 0 , then a m[0] dereference must not cause a memory error. So the m object must contain at least 4 bytes. But a memory error does happen on Line A when i == 1 . So the m object must contain less than 8 bytes. How many bytes were allocated for m ? sizeof(point2_vector) * N == sizeof(point2 *) * N == 4 * N . So we have: (4 * N) ≥ 4 (4 * N) < 8 It seems like the only possible answer is N == 1 . But no, this doesn’t cause a memory error, because the loop body would never be executed with i == 1 ! The key insight is that the multiplications above use 32-bit unsigned computer arithmetic. Let’s write N as X + 1 . Then these inequalities become: 4 ≤ 4 * (X + 1) = 4 * X + 4 < 8 0 ≤ (4 * X) < 4 (Multiplication distributes over addition in computer arithmetic.) What values of X satisfy this inequality? It might be easier to see if we remember that multiplication by powers of two is equivalent to shifting: 0 ≤ (X << 2) < 4 The key insight is that this shift eliminates the top two bits of X . There are exactly four values for X that work: 0 , 0x40000000 , 0x80000000 , and 0xC0000000 . For any of these, 4 * X == 0 in 32-bit computer arithmetic, because 4× X = 0 (mod 2 32 ) in normal arithmetic. Plugging X back in to N , we see that N ∈ {0x40000001, 0x80000001, 0xC0000001} . These are the only values that work. Partial credit was awarded for values that acknowledged the possibility of overflow.

QUESTION DATAREP-8B. Give a value of N so that no new fails, and no memory error happens on Line A, but a memory error does happen on Line B.

If no memory error happens on Line A, then N < 2 30 (otherwise overflow would happen as seen above). But a memory error does happen on Line B. Line B dereferences m[i][j] , for 0 ≤ j ≤ i ; so how big is m[i] ? It was allocated on Line A with size `sizeof(point2) (i + 1) == 2 * sizeof(double) * (i + 1) == 16 * (i + 1) . If i + 1 ≥ 2<sup>32</sup> / 16 = 2<sup>28</sup>, this multiplication will overflow. Since i < N , we can finally reason that any N greater than or equal to 2<sup>28</sup> = 0x10000000 and less than 2<sup>30</sup> = 0x40000000` will cause the required memory error.

DATAREP-9. Data representation

Assume a 64-bit x86-64 architecture unless explicitly told otherwise.

Write your assumptions if a problem seems unclear, and write down your reasoning for partial credit.

QUESTION DATAREP-9A. Arrange the following values in increasing numeric order. Assume that x is an int with value 8192.

A possible answer might be “a < b < c = d < e < f < g < h.”

h < a = d = f < b < c < e < g

For each of the remaining questions, write one or more arguments that, when passed to the provided function, will cause it to return the integer 61 (which is 0x3d hexadecimal ). Write the expected number of arguments of the expected types.

QUESTION DATAREP-9B.

QUESTION DATAREP-9C.

"61"

QUESTION DATAREP-9D. Your answer should be different from the previous answer.

" 0x3d" , " 61 " , etc.

QUESTION DATAREP-9E. For this problem, you will also need to define a global variable. Give its type and value.

This code was compiled from: int f4 ( int a, int b) { extern unsigned char y; return (a & 5 ) * 2 + b - y; } A valid solution is a =0, b =61, unsigned char y =0.

DATAREP-10. Sizes and alignments

QUESTION DATAREP-10A. Use the following members to create a struct of size 16, using each member exactly once, and putting char a first; or say “impossible” if this is impossible.

• char a; (we’ve written this for you)
• unsigned char b;

QUESTION DATAREP-10B. Repeat Part A, but create a struct with size 12.

abdc, acbd, acdb, adbc, adcb, …

QUESTION DATAREP-10C. Repeat Part A, but create a struct with size 8.

QUESTION DATAREP-10D. Consider the following structs:

Give definitions for T, U, and V so that there is one byte of padding in struct x after x2 , and two bytes of padding in struct y after y1 .

Example: T = short[2] , U = char , V = int

DATAREP-11. Dynamic memory allocation

QUESTION DATAREP-11A. True or false?

• free(nullptr) is an error.
• malloc(0) can never return nullptr .

False, False

QUESTION DATAREP-11B. Give values for sz and nmemb so that calloc(sz, nmemb) will always return nullptr (on a 32-bit x86 machine), but malloc(sz * nmemb) might or might not return null.

(size_t) -1, (size_t) -1 —anything that causes an overflow

Consider the following 8 statements. ( p and q have type char* .)

• q = nullptr;
• p = (char*) malloc(12);
• q = (char*) malloc(8);

QUESTION DATAREP-11C. Put the statements in an order that would execute without error or evoking undefined behavior. Memory leaks count as errors. Use each statement exactly once. Sample answer: “abcdefgh.”

cdefghab (and others). Expect “OK”

QUESTION DATAREP-11D. Put the statements in an order that would cause one double-free error, and no other error or undefined behavior (except possibly one memory leak). Use each statement exactly once.

efghbcad (and others). Expect “double-free + memory leak”

QUESTION DATAREP-11E. Put the statements in an order that would cause one memory leak (one allocated piece of memory is not freed), and no other error or undefined behavior. Use each statement exactly once.

efghadbc (and others). Expect “memory leak”

QUESTION DATAREP-11F. Put the statements in an order that would cause one boundary write error, and no other error or undefined behavior. Use each statement exactly once.

eafhcgbd (and others). Expect “out of bounds write”

DATAREP-12. Pointers and debugging allocators

You are debugging some students’ m61 code from Problem Set 1. The codes use the following metadata:

Their linked-list manipulations in m61_malloc are similar.

But their linked-list manipulations in m61_free differ.

Alice’s code: void m61_free ( void * ptr, ...) { ... meta * m = (meta * ) ptr - 1 ; if (m -> next != nullptr ) { m -> next -> prev = m -> prev; } if (m -> prev == nullptr ) { mhead = nullptr ; } else { m -> prev -> next = m -> next; } ... }

Bob’s code: void m61_free ( void * ptr, ...) { ... meta * m = (meta * ) ptr - 1 ; if (m -> next) { m -> next -> prev = m -> prev; } if (m -> prev) { m -> prev -> next = m -> next; } ... }

Chris’s code: void m61_free ( void * ptr, ...) { ... meta * m = (meta * ) ptr - 1 ; m -> next -> prev = m -> prev; m -> prev -> next = m -> next; ... }

Donna’s code: void m61_free ( void * ptr, ...) { ... meta * m = (meta * ) ptr - 1 ; if (m -> next) { m -> next -> prev = m -> prev; } if (m -> prev) { m -> prev -> next = m -> next; } else { mhead = m -> next; } ... }

You may assume that all code not shown is correct.

QUESTION DATAREP-12A. Whose code will segmentation fault on this input? List all students that apply.

QUESTION DATAREP-12B. Whose code might report something like “ invalid free of pointer [ptr1], not allocated ” on this input? (Because a list traversal starting from mhead fails to find ptr1 .) List all students that apply. Don’t include students whose code would segfault before the report.

QUESTION DATAREP-12C. Whose code would improperly report something like “ LEAK CHECK: allocated object [ptr1] with size 1 ” on this input? (Because the mhead list appears not empty, although it should be.) List all students that apply. Don’t include students whose code would segfault before the report.

QUESTION DATAREP-12D. Whose linked-list code is correct for all inputs? List all that apply.

DATAREP-13. Arena allocation

Chimamanda Ngozi Adichie is a writing a program that needs to allocate and free a lot of nodes, where a node is defined as follows:

She uses an arena allocator variant. Here’s her code.

QUESTION DATAREP-13A. True or false?

• This allocator never has external fragmentation.
• This allocator never has internal fragmentation.

QUESTION DATAREP-13B. Chimamanda’s frenemy Paul Auster notices that if many nodes are allocated right in a row, every 1024th allocation seems much more expensive than the others. The reason is that every 1024th allocation initializes a new group, which in turn adds 1024 nodes to the free list. Chimamanda decides instead to allow a single element of the free list to represent many contiguous free nodes . The average allocation might get a tiny bit slower, but no allocation will be much slower than average. Here’s the start of her idea:

Complete this function by writing code to replace // ??? .

if (n -> key == 1 ) { a -> frees = n -> right; } else { a -> frees = n + 1 ; a -> frees -> key = n -> key - 1 ; a -> frees -> right = n -> right; } Another solution: if (n -> right) { a -> frees = n -> right; } else if (n -> key == 1 ) { a -> frees = NULL ; } else { a -> frees = n + 1 ; a -> frees -> key = n -> key - 1 ; }

QUESTION DATAREP-13C. Write a node_free function that works with the node_alloc function from the previous question.

void node_free (arena * a, node * n) { n -> right = a -> frees; n -> key = 1 ; a -> frees = n; } Or, if you use the solution above: void node_free (arena * a, node * n) { n -> right = a -> frees; a -> frees = n; }

QUESTION DATAREP-13D. Complete the following new function.

arena_group * node_find_group (arena * a, node * n) { for (arena_group * g = a -> groups; g; g = g -> next_group) { if ((uintptr_t) & g -> nodes[ 0 ] <= (uintptr_t) n && (uintptr_t) n <= (uintptr_t) & g -> nodes[ 1023 ]) { return g; } } return nullptr ; }

QUESTION DATAREP-13E. Chimamanda doesn’t like that the node_find_group function from part D takes O ( G ) time, where G is the number of allocated arena_groups. She remembers a library function that might help, posix_memalign :

The function posix_memalign() allocates size bytes and places the address of the allocated memory in *memptr . The address of the allocated memory will be a multiple of alignment , which must be a power of two and a multiple of sizeof(void*) . ...

“Cool,” she says, “I can use this to speed up node_find_group !” She now allocates a new group with the following code:

Given this allocation strategy, write a version of node_find_group that takes O (1) time.

arena_group * node_find_group (arena * a, node * n) { uintptr_t n_addr = (uintptr_t) n; return (arena_group * ) (n_addr - n_addr % 32768 ); }

DATAREP-14. Data representation

Sort the following expressions in ascending order by value, using the operators <, =, >. For example, if we gave you:

• int B = 0x6;

you would write C < A = B .

• unsigned char a = 0x191;
• char b = 0x293;
• unsigned long c = 0xFFFFFFFF;
• int d = 0xFFFFFFFF;
• int e = d + 3;
• size_t g = sizeof(*s) (given short *s )
• long h = 256;
• i = 0b100000000000000000000000000000000000 (binary)
• unsigned long j = 0xACE - 0x101;

b < d < e = g < a < h < j < c < f < i

DATAREP-15. Memory

For the following questions, select the part(s) of memory from the list below that best describes where you will find the object.

• between the heap and the stack
• in a read-only data segment
• in a text segment starting at address 0x08048000
• in a read/write data segment
• in a register

Assume the following code, compiled without optimization.

QUESTION DATAREP-15A. The value 0xdeadbeef, when we are returning from main.

7, in a register

QUESTION DATAREP-15B. The variable maxitems

4, in a read-only data segment

QUESTION DATAREP-15C. The structure s

6, in a read/write data segment

QUESTION DATAREP-15D. The structure at sp[9]

QUESTION DATAREP-15E. The variable u

2, stack, or 7, in a register

QUESTION DATAREP-15F. main

5, in a text segment starting at address 0x08048000

QUESTION DATAREP-15G. printf

3, between the heap and the stack

QUESTION DATAREP-15H. argc

QUESTION DATAREP-15I. The number the user enters

QUESTION DATAREP-15J. The variable L

DATAREP-16. Memory and pointers

⚠️ This question may benefit from Unit 4, kernel programming. ⚠️

If multiple processes are sharing data via mmap , they may have the file mapped at different virtual addresses. In this case, pointers to the same object will have different values in the different processes. One way to store pointers in mmapped memory so that multiple processes can access them consistently is using relative pointers. Rather than storing a regular pointer, you store the offset from the beginning of the mmapped region and add that to the address of the mapping to obtain a real pointer. An alternative representation is called self-relative pointers. In this case, you store the difference in address between the current location (i.e., the location containing the pointer) and the location to which you want to point. Neither representation addresses pointers between the mmapped region and the rest of the address space; you may assume such pointers do not exist.

QUESTION DATAREP-16A. State one advantage that relative pointers have over self-relative pointers.

The key thing to understand is that both of these approaches use relative pointers and both can be used to solve the problem of sharing a mapped region among processes that might have the region mapped at different addresses. Possible advantages: Within a region, you can safely use memcpy as moving pointers around inside the region does not change their value. If you copy a self relative pointer to a new location, its value has to change. That is, imagine that you have a self-relative pointer at offset 4 from the region and it points to the object at offset 64 from the region. The value of the self relative pointer is 60. If I copy that pointer to the offset 100 from the region, I have to change it to be -36. If you save the region as a uintptr_t or a char * , then you can simply add the offset to the region; self-relative-pointers will always be adding/subtracting from the address of the location storing the pointer, which may have a type other than char * , so you'd need to cast it before performing the addition/subtraction. You can use a larger region: if we assume that we have only N bits to store the pointer, then in the base+offset model, offset could be an unsigned value, which will be larger than the maximum offset possible with a signed pointer, which you need for the self-relative case. That is, although the number of values that can be represented by signed and unsigned numbers differs by one, the implementation must allow for a pointer from the beginning of the region to reference an item at the very last location of the region -- thus, your region size is limited by the largest positive number you can represent.

QUESTION DATAREP-16B. State one advantage that self-relative pointers have over relative pointers.

You don't have to know the address at which the region is mapped to use them. That is, given a location containing a self-relative pointer, you can find the target of that pointer.

For the following questions, assume the following setup:

QUESTION DATAREP-16C. Propose a type for TYPE1 and give 1 sentence why you chose that type.

A good choice is ptrdiff_t , which represents differences between pointers. Other reasonable choices include uintptr_t and unsigned long .

QUESTION DATAREP-16D. Write a C expression to generate a (properly typed) pointer to the element referenced by the r_next field of ll1 .

(ll1*) (region + node1.r_next)

QUESTION DATAREP-16E. Propose a type for TYPE2 and give 1 sentence why you chose that type.

The same choices work; again ptrdiff_t is best.

QUESTION DATAREP-16F. Write a C expression to generate a (properly typed) pointer to the element referenced by the sr_next field of ll2 .

(ll2*) ((char*) &node2.sr_next + node2.sr_next)

DATAREP-17. Data representation: Allocation sizes

How much user-accessible space is allocated on the stack and/or the heap by each of the following statements? Assume x86-64.

QUESTION DATAREP-17A. union my_union { ... };

0; this declares the type , not any object

QUESTION DATAREP-17B. void* p = malloc(sizeof(char*));

16: 8 on the heap plus 8 on the stack

QUESTION DATAREP-17C. my_union u;

16 (on the stack)

QUESTION DATAREP-17D. my_union* up = &u;

8 (on the stack)

DATAREP-18. Data representation: ENIAC

Professor Kohler has been developing Eddie’s NIfty Awesome Computer (ENIAC). When he built the C compiler for ENIAC, he assigned the following sizes and alignments to C’s fundamental data types. (Assume that every other fundamental type has the same size and alignment as one of these.)

QUESTION DATAREP-18A. This set of sizes is valid: it obeys all the requirements set by C’s abstract machine. Give one different size assignment that would make the set as a whole invalid.

Some examples: sizeof(char) = 0 ; sizeof(char) = 2 ; sizeof(short) = 8 (i.e., longer than int ); sizeof(int) = 2 (though not discussed in class, turns out that C++ requires ints are at least 2 bytes big); etc.

QUESTION DATAREP-18B. What alignment must the ENIAC malloc guarantee?

For the following two questions, assume the following struct on the ENIAC:

QUESTION DATAREP-18C. What is sizeof(struct s) ?

f1 is 7 bytes. f2 is 16 bytes with 16-byte alignment, so add 9B padding. f3 is 4 bytes (and is already aligned). f4 is 8 bytes with 8-byte alignment, so add 4B padding. That adds up to 7 + 9 + 16 + 4 + 4 + 8 = 16 + 16 + 16 = 48 bytes. That’s a multiple of the structure’s alignment, which is 16, so no need for any end padding.

QUESTION DATAREP-18D. What is alignof(struct s) ?

The remaining questions refer to this structure definition:

Indicate for each statement whether the statement is always true, possibly true, or never true on the ENIAC.

QUESTION DATAREP-18E : sizeof(outer) > sizeof(inner) (Always / Possibly / Never)

QUESTION DATAREP-18F : sizeof(outer) is a multiple of sizeof(inner) (Always / Possibly / Never)

QUESTION DATAREP-18G : alignof(outer) > alignof(struct inner) (Always / Possibly / Never)

QUESTION DATAREP-18H : sizeof(outer) - sizeof(inner) < 4 (Always / Possibly / Never)

QUESTION DATAREP-18I : sizeof(outer) - sizeof(inner) > 32 (Always / Possibly / Never)

QUESTION DATAREP-18J : alignof(inner) == 2 (Always / Possibly / Never)

DATAREP-19. Undefined behavior

Which of the following expressions, instruction sequences, and code behaviors cause undefined behavior? For each question, write Defined or Undefined. (Note that the INT_MAX and UINT_MAX constants have types int and unsigned , respectively.)

QUESTION DATAREP-19A. INT_MAX + 1 (Defined / Undefined)

QUESTION DATAREP-19B. UINT_MAX + 1 (Defined / Undefined)

QUESTION DATAREP-19C.

(Defined / Undefined)

Defined (only C++ programs can have undefined behavior; the behavior of x86-64 instructions is always defined)

QUESTION DATAREP-19D. Failed memory allocation, i.e., malloc returns nullptr (Defined / Undefined)

QUESTION DATAREP-19E. Use-after-free (Defined / Undefined)

QUESTION DATAREP-19F. Here are two functions and a global variable:

C’s undefined behavior rules would allow an aggressive optimizing compiler to simplify the code generated for f . Fill in the following function with the simplest C code you can, under the constraint that an aggressive optimizing compiler might generate the same object code for f and f_simplified .

return i * 2;

DATAREP-20. Bit manipulation

It’s common in systems code to need to switch data between big-endian and little-endian representations. This is because networks represent multi-byte integers using big-endian representation, whereas x86-family processors store multi-byte integers using little-endian representation.

QUESTION DATAREP-20A. Complete this function, which translates an integer from big-endian representation to little-endian representation by swapping bytes. For instance, big_to_little(0x01020304) should return 0x04030201 . Your return statement must refer to the u.c array, and must not refer to x . This function is compiled on x86-64 Linux (as every function is unless we say otherwise).

return (u.c[ 0 ] << 24 ) | (u.c[ 1 ] << 16 ) | (u.c[ 2 ] << 8 ) | u.c[ 3 ];

QUESTION DATAREP-20B. Complete the function again, but this time write a single expression that refers to x (you may refer to x multiple times, of course).

return ((x & 0xFF ) << 24 ) | ((x & 0xFF00 ) << 8 ) | ((x & 0xFF0000 ) >> 8 ) | (x >> 24 );

QUESTION DATAREP-20C. Now write the function little_to_big , which will translate a little-endian integer into big-endian representation. You may introduce helper variables or even call big_to_little if that’s helpful.

return big_to_little (x);

DATAREP-21. Computer arithmetic

Bitwise operators and computer arithmetic can represent vectors of bits, which in turn are useful for representing sets . For example, say we have a function bit that maps elements to distinct bits; thus, bit(X) == (1 << i) for some i . Then a set {X0, X1, X2, …, Xn} can be represented as bit(X0) | bit(X1) | bit(X2) | … | bit(Xn) . Element Xi is in the set with integer representation z if and only if (bit(Xi) & z) != 0 .

QUESTION DATAREP-21A. What is the maximum number of set elements that can be represented in a single unsigned variable on an x86 machine?

QUESTION DATAREP-21B. Match each set operation with the C operator(s) that could implement that operation. (Complement is a unary operation.)

intersection & equality == complement ~ union | toggle membership ^

QUESTION DATAREP-21C. Complete this function, which should return the set difference between the sets with representations a and b . This is the set containing exactly those elements of set a that are not in set b .

Any of these work: return a & ~ b; return a - (a & b); return a & ~ (a & b);

QUESTION DATAREP-21D. Below we’ve given a number of C++ expressions, some of their values, and some of their set representations for a set of elements. For example, the first row says that the integer value of expression 0 is just 0, which corresponds to an empty set. Fill in the blanks. This will require figuring out which bits correspond to the set elements A , B , C , and D , and the values for the 32-bit int variables a , x , and s . No arithmetic operation overflows; abs(x) returns the absolute value of x (that is, x < 0 ? -x : x ).

Expression e Integer value Represented set 0 0 {} a == a 1 {A} (unsigned) ~a < (unsigned) a 1 {A} a < 0 1 {A} (1 << (s/2)) - 1 15 {A,B,C,D} a * a 4 {C} abs(a) 2 {D} x & (x - 1) 0 {} x - 1 3 {A,D} x 4 {C} s 8 {B}

DATAREP-22. Bit Tac Toe

Brenda Bitdiddle is implementing tic-tac-toe using bitwise arithmetic. (If you’re unfamiliar with tic-tac-toe, see below.) Her implementation starts like this:

Each position on the board is assigned a distinct bit.

Tic-tac-toe, also known as noughts and crosses, is a simple paper-and-pencil game for two players, X and O. The board is a 3x3 grid. The players take turns writing their symbol (X or O) in an empty square on the grid. The game is won when one player gets their symbol in all three squares in one of the rows, one of the columns, or one of the two diagonals. X goes first; played perfectly, the game always ends in a draw. You may access the Wikipedia page for tic-tac-toe .

QUESTION DATAREP-22A. Brenda’s current code doesn’t check whether a move reuses a position. Write a snippet of C code that returns –1 if an attempted move is reusing a position. This snippet will replace line 3.

Lots of people misinterpreted this to mean the player reused their own position and ignored the other player. That mistake was allowed with no points off. The code below checks whether any position was reused by either player. if ((b -> moves[XS] | b -> moves[OS]) & ttt_values[row][col]) { return - 1 ; } OR if ((b -> moves[XS] | b -> moves[OS] | ttt_values[row][col]) == (b -> moves[XS] | b -> moves[OS])) { return - 1 ; } OR if ((b -> moves[XS] + b -> moves[OS]) & ttt_values[row][col]) { return - 1 ; } OR if ((b -> moves[p] ^ ttt_values[row][col]) < b -> moves[p]) { return - 1 ; } etc.

QUESTION DATAREP-22B. Complete the following function. You may use the following helper function:

• int popcount(unsigned n) Return the number of 1 bits in n . (Stands for “population count”; is implemented on recent x86 processors by a single instruction, popcnt .)

For full credit, your code should consist of a single “ return ” statement with a simple expression, but for substantial partial credit write any correct solution.

return popcount (b -> moves[XS] | b -> moves[OS]);

QUESTION DATAREP-22C. Write a simple expression that, if nonzero, indicates that player XS has a win on board b across the main diagonal (has marks in positions 0,0 , 1,1 , and 2,2 ).

(b -> moves[XS] & 0x421 ) == 0x421

Lydia Davis notices Brenda’s code and has a brainstorm. “If you use different values,” she suggests, “it becomes easy to detect any win.” She suggests:

QUESTION DATAREP-22D. Repeat part A for Lydia’s values: Write a snippet of C code that returns –1 if an attempted move is reusing a position. This snippet will replace line 3 in Brenda’s code.

The same answers as for part A work.

QUESTION DATAREP-22E. Repeat part B for Lydia’s values: Use popcount to complete tictactoe_nmoves .

Either of: return popcount ((b -> moves[ 0 ] | b -> moves[ 1 ]) & 0x777 ); return popcount ((b -> moves[ 0 ] | b -> moves[ 1 ]) & 0x777000 );

QUESTION DATAREP-22F. Complete the following function for Lydia’s values. For full credit, your code should consist of a single “ return ” statement containing exactly two constants, but for substantial partial credit write any correct solution.

return (b -> moves[p] + 0x11111111 ) & 0x88888888 ; // Another amazing possibility (Allen Chen and others): return b -> moves[p] & (b -> moves[p] << 1 ) & (b -> moves[p] << 2 );

DATAREP-23. Memory and Pointers

Two processes are mapping a file into their address space. The mapped file contains an unsorted linked list of integers. As the processes cannot ensure that the file will be mapped at the same virtual address, they use relative pointers to link elements in the list. A relative pointer holds not an address, but an offset that user code can use to calculate a true address. Our processes define the offset as relative to the start of the file.

Thus, each element in the linked list is represented by the following structure:

offset == (size_t) -1 indicates the end of the list. Other offset values represent the position of the next item in the list, calculated relative to the start of the file.

QUESTION DATAREP-23A. Write a function to find an item in the list. The function's prototype is:

The mapped_file parameter is the address of the mapped file data; the list parameter is a pointer to the first node in the list; and the value parameter is the value for which we are searching. The function should return a pointer to the linked list element if the value appears in the list or nullptr if the value is not in the list.

ll_node * find_element ( void * mapped_file, ll_node * list, int value) { while ( 1 ) { if (list -> value == value) return list; if (list -> offset == (size_t) - 1 ) return NULL ; list = (ll_node * ) (( char * ) mapped_file + list -> offset); } }

DATAREP-24. Integer representation

Write the value of the variable or expression in each problem, using signed decimal representation.

For example, if we gave you:

• int i = 0xA;
• int j = 0xFFFFFFFF;

you would write A) 10 B) -1.

QUESTION DATAREP-24A. int i = 0xFFFF; (You may write this either in decimal or as an expression using a power of 2)

2 16 - 1 or 65535

QUESTION DATAREP-24B. short s = 0xFFFF; (You may write this either in decimal or as an expression using a power of 2)

QUESTION DATAREP-24C. unsigned u = 1 << 10;

1024 or 2 10

QUESTION DATAREP-24D. ⚠️ From WeensyOS: unsigned long l = PTE_P | PTE_U;

QUESTION DATAREP-24E. int j = ~0;

QUESTION DATAREP-24F. ⚠️ From WeensyOS: sizeof(x86_64_pagetable);

4096 or 2 12

QUESTION DATAREP-24G. Given this structure:

This expression: sizeof(ps);

TRICK QUESTION! 8

QUESTION DATAREP-24H. Using the structure above: sizeof(*ps);

QUESTION DATAREP-24I. unsigned char u = 0xABC;

0xBC == 11*16 + 12 == 160 + 16 + 12 == 188

QUESTION DATAREP-24J. signed char c = 0xABC;

0xBC has most-significant bit on, so the value as a signed char is less than zero. We seek x so that 0xBC + x == 0x100 . The answer is 0x44: 0xBC + 4 == 0xC0 , and 0xC0 + 0x40 == 0x100 . So −0x44 == −4*16 − 4 == −68 .

DATAREP-25. Data representation

In gdb, you observe the following values for a set of memory locations.

For each C expression below, write its value in hexadecimal. For example, if we gave you:

the answer would be 0xa0 .

Assume the following structure and union declarations and variable definitions.

QUESTION DATAREP-25A. cp[4] =

QUESTION DATAREP-25B. cp + 7 =

0x100001027

QUESTION DATAREP-25C. s1 + 1 =

0x100001038

QUESTION DATAREP-25D. s1->i =

0xd3c2b1a0 (-742215264)

QUESTION DATAREP-25E. sizeof(s1) =

QUESTION DATAREP-25F. &s2->s =

0x100001028

QUESTION DATAREP-25G. &u->s =

0x100001020

QUESTION DATAREP-25H. s1->l =

0x9f8e7d6c5b4a3928 (-6949479270644565720)

QUESTION DATAREP-25I. s2->s.s =

0xf201 (-3583)

QUESTION DATAREP-25J. u->l =

0x1706f5e4d3c2b1a0 (1659283875886707104)

DATAREP-26. Sizes and alignments

Here’s a test struct with n members. Assume an x86-64 machine, where each Ti either is a basic x86-64 type (e.g., int , char , double ) or is a type derived from such types (e.g., arrays, structs, pointers, unions, possibly recursively), and assume that ai ≤8 for all i .

In these questions, you will compare this struct with other structs that have the same members, but in other orders.

QUESTION DATAREP-26A. True or false: The size of struct test is minimized when its members are sorted by size. In other words, if s1 ≤ s2 ≤…≤ sn , then sizeof(struct test) is less than or equal to the struct size for any other member order.

If true, briefly explain your answer; if false, give a counterexample (i.e., concrete types for T1 , …,  Tn that do not minimize sizeof(struct test) ).

False. T1 = char , T2 = int , T3 = char[5]

QUESTION DATAREP-26B. True or false: The size of struct test is minimized when its members are sorted by alignment. In other words, if a1 ≤ a2 ≤…≤ an , then sizeof(struct test) is less than or equal to the struct size for any other member order.

If true, briefly explain your answer; if false, give a counterexample.

True. Padding only occurs between objects with different alignments, and is limited by the second alignment; sorting by alignment therefore minimizes padding.

QUESTION DATAREP-26C. True or false: The alignment of struct test is minimized when its members are sorted in increasing order by alignment. In other words, if a1 ≤ a2 ≤…≤ an , then alignof(struct test) is less than or equal to the struct alignment for any other member order.

True. It’s all the same; alignment is max alignment of every component, and is independent of order.

QUESTION DATAREP-26D. What is the maximum number of bytes of padding that struct test could contain for a given n ? The answer will be a pretty simple formula involving n . (Remember that ai ≤8 for all i .)

Alternating char and long gives the most padding, which is 7*(n/2) when n is even and 7*(n+1)/2 otherwise.

QUESTION DATAREP-26E. What is the minimum number of bytes of padding that struct test could contain for a given n ?

DATAREP-27. Undefined behavior

QUESTION DATAREP-27A. Sometimes a conforming C compiler can assume that a + 1 > a , and sometimes it can’t. For each type below, consider this expression:

and say whether the compiler:

• Must reject the expression as a type error.
• May assume that the expression is true (that a + (int) 1 > a for all a ).
• Must not assume that the expression is true.
• unsigned char a
• struct {int m;} a

1—May assume; 2—Must not assume; 3—May assume; 4—May assume (in fact due to integer promotion, this statement really is always true, even in mathematical terms); 5—Must reject.

QUESTION DATAREP-27B. The following code checks its arguments for sanity, but not well: each check can cause undefined behavior.

Rewrite these checks to avoid all undefined behavior. You will likely add one or more casts to uintptr_t . For full credit, write each check as a single comparison (no && or || , even though the current ptr_into_array check uses || ).

array_size check:

ptr_into_array check:

array_size check: (uintptr_t) array + 4 * array_size < (uintptr_t) array ptr_into_array check: (uintptr_t) ptr_into_array - (uintptr_t) array > 4 * array_size

QUESTION DATAREP-27C. In lecture, we discussed several ways to tell if a signed integer x is negative. One of them was the following:

But this is incorrect: it has undefined behavior. Correct it by adding two characters.

(x & (1UL << (sizeof(x) * CHAR_BIT - 1))) != 0

DATAREP-28. ⚠️ Memory errors and garbage collection ⚠️

⚠️ We didn’t discuss garbage collectors in class this year.

Recall that a conservative garbage collector is a program that can automatically free dynamically-allocated memory by detecting when that memory is no longer referenced. Such a GC works by scanning memory for currently-referenced pointers, starting from stack and global memory, and recursing over each referenced object until all referenced memory has been scanned. We built a conservative garbage collector in lecture datarep6.

QUESTION DATAREP-28A. An application program that uses conservative GC, and does not call free directly, will avoid certain errors and undefined behaviors. Which of the following errors are avoided? List all that apply.

• Use-after-free
• Double free
• Signed integer overflow
• Boundary write error
• Unaligned access

QUESTION DATAREP-28B. Write a C program that leaks unbounded memory without GC, but does not do so with GC. You should need less than 5 lines. (Leaking “unbounded” memory means the program will exhaust the memory capacity of any machine on which it runs.)

while ( 1 ) { ( void ) malloc( 1 ); }

QUESTION DATAREP-28C. Not every valid C program works with a conservative GC, because the C abstract machine allows a program to manipulate pointers in strange ways. Which of the following pointer manipulations might cause the conservative GC from class to inappropriately free a memory allocation? List all that apply.

Storing the pointer in a uintptr_t variable

Writing the pointer to a disk file and reading it back later

Using the least-significant bit of the pointer to store a flag:

Storing the pointer in textual form:

Splitting the pointer into two parts and storing the parts in an array:

DATAREP-29. Bitwise

QUESTION DATAREP-29A. Consider this C fragment:

Or, shorter:

Write a single expression that evaluates to the same value, but that does not use the conditional ?: operator. You will use the fact that a < b always equals 0 or 1. For full credit, do not use expensive operators (multiply, divide, modulus).

Examples: (a < b) * x , (-(uintptr_t) (a < b)) & x

QUESTION DATAREP-29B. This function returns one more than the index of the least-significant 1 bit in its argument, or 0 if its argument is zero.

This function runs in O ( B ) time, where B is the number of bits in an unsigned long . Write a version of ffs that runs instead in O (log  B ) time.

int ffs ( unsigned long x) { if ( ! x) { return 0 ; } int ans = 1 ; if ( ! (x & 0x00000000FFFFFFFFUL )) { ans += 32 ; x >>= 32 ; } if ( ! (x & 0x0000FFFF )) { ans += 16 ; x >>= 16 ; } if ( ! (x & 0x00FF )) { ans += 8 ; x >>= 8 ; } if ( ! (x & 0x0F )) { ans += 4 ; x >>= 4 ; } if ( ! (x & 0x3 )) { ans += 2 ; x >>= 2 ; } return ans + (x & 0x1 ? 0 : 1 ); }

DATAREP-30. Data representation

QUESTION DATAREP-30A. Write a type whose size is 19,404,329 times larger than its alignment.

char[19404329]

QUESTION DATAREP-30B. Consider a structure type T with N members, all of which have nonzero size. Assume that sizeof(T) == alignof(T) . What is N ?

QUESTION DATAREP-30C. What is a C type that obeys (T) -1 == (T) 255 on x86-64?

char (or unsigned char or signed char )

Parts D–G use this code. The architecture might or might not be x86-64.

Assume that (uintptr_t) s2 - (uintptr_t) s1 == 4 and *s1 > *s2 .

QUESTION DATAREP-30D. What is sizeof(a) ?

QUESTION DATAREP-30E. What is sizeof(unsigned) on this architecture?

QUESTION DATAREP-30F. Is this architecture big-endian or little-endian?

QUESTION DATAREP-30G. Might the architecture be x86-64?

DATAREP-31. Memory errors

Mavis Gallant is starting on her debugging memory allocator. She’s written code that aims to detect invalid frees, where a pointer passed to m61_free was not returned by an earlier m61_malloc .

Help her track down bugs.

QUESTION DATAREP-31A. What is sizeof(struct m61_metadata) ?

QUESTION DATAREP-31B. Give an m61_ function call (function name and arguments) that would cause both unsigned integer overflow and invalid memory accesses.

m61_malloc((size_t) -15) . This turns into malloc(1) and the dereference of meta->magic becomes invalid.

QUESTION DATAREP-31C. Give an m61_ function call (function name and arguments) that would cause integer overflow, but no invalid memory access within the m61_ functions . (The application might or might not make an invalid memory access later.)

m61_malloc((size_t) -1)

QUESTION DATAREP-31D. These functions have some potential null pointer dereferences. Fix one such problem, including the line number(s) where your code should go.

C3: if (p) { memset(p, 0, sz * count); }

QUESTION DATAREP-31E. Put a single line of C code in the blank. The resulting program should (1) be well-defined with no memory leaks when using default malloc / free / calloc , but (2) always cause undefined behavior when using Mavis’s debugging malloc / free / calloc .

free(nullptr);

QUESTION DATAREP-31F. A double free should print a different message than an invalid free. Write code so Mavis’s implementation does this; include the line numbers where the code should go.

F4: fprintf(stderr, meta->magic == 0xB0B0B0B0 ? "double free of %p" : "invalid free of %p", ptr) after F6: meta->magic = 0xB0B0B0B0;

DATAREP-32. Memory word search

QUESTION DATAREP-32A. What is decimal 61 in hexadecimal?

0x3d, 2 pts

The following is a partial dump of an x86-64 Linux program’s memory. Note that each byte is represented as a hexadecimal number. Memory addresses increase from top to bottom and from left to right.

QUESTION DATAREP-32B. What memory segment contains the memory dump?

Data segment (globals), 2 pts

For questions 3C–3I, give the last two digits of the address of the given object in this memory dump (so for the object located at address 0x6010a8, you would write “a8”). There’s a single best answer for every question, and all questions have different answers .

QUESTION DATAREP-32C. A long (64 bits) of value 61.

QUESTION DATAREP-32D. A long of value -61.

QUESTION DATAREP-32E. An int of value 61.

QUESTION DATAREP-32F. A pointer to an object in the heap.

QUESTION DATAREP-32G. A pointer to a local variable.

QUESTION DATAREP-32H. A pointer that points to an object present in the memory dump.

QUESTION DATAREP-32I. The first byte of a C string comprising at least 4 printable ASCII characters. (Printable ASCII characters have values from 0x20 to 0x7e.)

DATAREP-33. Architecture

QUESTION DATAREP-33A. Write a C++ expression that will evaluate to false on all typical 32-bit architectures and true on all typical 64-bit architectures.

3pts sizeof(void*) == 8

QUESTION DATAREP-33B. Give an integer value that has the same representation in big-endian and little-endian, and give its C++ type. Assume the same type sizes as x86-64.

2pts ex: int x = 0

QUESTION DATAREP-33C. Repeat question B, but with a different integer value.

2pts ex: int x = -1 :)

QUESTION DATAREP-33D. Complete this C++ function, which should return true iff it is called on a machine with little-endian integer representation. Again, you may assume the same type sizes as x86-64.

3pts bool is_little_endian () { union { int a; char c[ 4 ]; } u; u.a = 0 ; u.c[ 0 ] = 1 ; return u.a == 1 ; }

DATAREP-34. Undefined behavior

The following code is taken from the well-known textbook Mastering C Pointers (with some stylistic changes). Assume it is run on x86-64.

QUESTION DATAREP-34A. List all situations in which this program will not execute undefined behavior. (There is at least one.)

3pts If malloc returns nullptr .

QUESTION DATAREP-34B. True or false? The expression ++x could be replaced with ++y without changing the meaning of the program.

3pts True! The undefined behavior is the same either way.

Here’s an updated version of the program.

QUESTION DATAREP-34C. True or false? The expression *(x + y) could be replaced with x[y] without changing the meaning of the program.

QUESTION DATAREP-34D. True or false? The expression *(x + y) could be replaced by * (int*) ((uintptr_t) x + y) without changing the meaning of the program.

3pts False (address arithmetic isn’t the same for pointer arithmetic, except for pointers with type equivalent to char )

DATAREP-35. Odd alignments

QUESTION DATAREP-35A. Write a struct definition that contains exactly seven bytes of padding on x86-64.

3pts struct {long a; char b;}

QUESTION DATAREP-35B. Can an x86-64 struct comprise more than half padding? Give an example if so, or explain briefly why not.

3pts Yes. struct {char a; long b; char c;} has size 24 and 14 bytes of padding.

The remaining questions consider a new architecture called x86-64-rainbow , which is like x86-64 plus special support for a fundamental data type called color . A color is a three-byte data type with red, green, and blue components, kind of like this:

But unlike struct color on x86-64, which has size 3 and alignment 1, color on x86-64-rainbow has size 3 and alignment 3 . All the usual rules for C abstract machine sizes and alignments still hold.

QUESTION DATAREP-35C. What is the alignment of pointers returned by malloc on x86-64-rainbow?

QUESTION DATAREP-35D. Give an example of an x86-64-rainbow struct that ends with more than 16 bytes of padding.

2pts struct { long a[2]; color b[3]; } has alignment lcm(8, 3) = 24 and size 8 + 8 + 3 + 3 + 3 = 25, so it ends with 23 bytes of padding!

DATAREP-36. Debugging allocators

In problem set 1, you built a debugging allocator that could detect many kinds of error. Some students used exclusively internal metadata , where the debugging allocator’s data was stored within the same block of memory as the payload. Some students used external metadata , such as a separate hash table mapping payload pointers to metadata information.

QUESTION DATAREP-36A. Which kind of error mentioned by the problem set could not be detected by external metadata alone?

2pts Boundary write errors.

The problem set requires the m61 library to detect invalid frees, which includes double frees. However, double frees are so common that a special double-free error message can help users. Jia Tolentino wants to print such a message. Her initial idea is to keep a set of recently freed pointers:

QUESTION DATAREP-36B. What eviction policy is used for the recently_freed array?

2pts FIFO (round-robin).

Jia uses these helpers in m61_free as follows. (You may assume that is_invalid_free(ptr) returns true for every invalid or double free.)

She has not yet changed m61_malloc , though she knows she needs to. Help her evaluate whether her design achieves the following mandatory and desirable (that is, optional) requirements.

Note : As you saw in tests 32 and 33 in pset 1, aggressive attacks from users can corrupt metadata arbitrarily. You should assume for the following questions that such aggressive attacks do not occur. The user might free something that was never allocated, and might double-free something, but will never overwrite metadata.

QUESTION DATAREP-36C. Mandatory : The design must not keep unbounded, un-reusable state for pointers that have been freed. Write “Achieved” or “Not achieved” and explain briefly.

6 pts for C-E together. +5 if one serious error; +3 if two serious errors Achieved. The design only keeps space for 10 recently-freed pointers.

QUESTION DATAREP-36D. Desirable : The design should report a double-free as a double-free, not an invalid free. Write “Achieved” or “Not achieved” and explain briefly.

Not achieved. If a pointer falls off the list after 10 frees, Jia’s design will report a double-free of that pointer as an invalid free.

QUESTION DATAREP-36E. Mandatory : The design must never report valid frees as double-frees or invalid frees. Write “Achieved” or “Not achieved” and explain briefly.

Not achieved. A recently-freed pointer can be reused by malloc, but she hasn’t accounted for that. So if (1) a pointer is freed, (2) a malloc returns the same pointer, (3) the user frees that pointer again, that valid free will be reported as a double free.

QUESTION DATAREP-36F. Describe code to be added to m61_malloc that will achieve all mandatory requirements, if any are required.

3pts Here’s the cleanest solution to the 4E problem. Remove returned pointers from recently_freed . Add this code to malloc before return ptr : for ( int i = 0 ; i != 10 ; ++ i) { if (recently_freed[i] == ptr) { recently_freed[i] = nullptr ; } }

DATAREP-37. Representations

Your job in the following questions is to complete each C++ program so that it prints 61 to standard output when run. Your answer should fill in the blank _________ , and you may assume system calls execute without error. If a question cannot be answered so that the program reliably prints 61 with no undefined behavior, say so and explain briefly.

To compile these programs, use a command line such as c++ -std=gnu++17 -pthread x.cc .

QUESTION DATAREP-37A.

QUESTION DATAREP-37B.

61L or (long) 61 are best; 61 will cause a compiler warning, because it’s an int and the format expects a long .

QUESTION DATAREP-37C.

6 * 16 + 1 , 0x61 , 97

QUESTION DATAREP-37D.

157 , - x + 61 , 96 + 61

QUESTION DATAREP-37E.

char c[61];

QUESTION DATAREP-37F.

This cannot be done. struct sixtyfun has minimum alignment of 4 (because int has alignment 4), so its size must be a multiple of 4.

QUESTION DATAREP-37G.

Anything with size 20, such as char c[20]; or int x[5]; .

QUESTION DATAREP-37H.

int a = 255, b = 0, c = 61; int a = -1, b = 0 (or anything ≤31), c = 61; unsigned a = 0x10000, b = 12, c = 0xFF; int a = 32, b = 1, c = 63; There are many other possibilities!

QUESTION DATAREP-37I.

This cannot be done without undefined behavior, because y is computed using an uninitialized variable.

QUESTION DATAREP-37J.

Anything that adds 15 total to x[0] … x[2] . For example, 5

QUESTION DATAREP-37K.

{ "echo", "61", nullptr }

QUESTION DATAREP-37L.

dup2(pfd[0], 0); close(pfd[0]); close(pfd[1]); The sleep(3) , which is not waitpid , makes many other solutions work too. dup2(pfd[0], 0); works; pipe hygiene isn't important because the parent exits. printf("61\n"); almost works, but something weird happens on Mac OS X.

QUESTION DATAREP-37M.

waitpid(p, nullptr, 0)

QUESTION DATAREP-37N. Note that there are three blanks to fill in with code (you may also leave them empty).

#1, #3: nothing. #2: std::unique_lock<std::mutex> guard(m); If the lock is in #1 (and there is no unlock in #3), that causes deadlock.

If you're seeing this message, it means we're having trouble loading external resources on our website.

If you're behind a web filter, please make sure that the domains *.kastatic.org and *.kasandbox.org are unblocked.

To log in and use all the features of Khan Academy, please enable JavaScript in your browser.

Praxis Core Math

Course: praxis core math   >   unit 1, data representations | lesson.

• Data representations | Worked example
• Center and spread | Lesson
• Center and spread | Worked example
• Random sampling | Lesson
• Random sampling | Worked example
• Scatterplots | Lesson
• Scatterplots | Worked example
• Interpreting linear models | Lesson
• Interpreting linear models | Worked example
• Correlation and Causation | Lesson
• Correlation and causation | Worked example
• Probability | Lesson
• Probability | Worked example

What are data representations?

• How much of the data falls within a specified category or range of values?
• What is a typical value of the data?
• How much spread is in the data?
• Is there a trend in the data over time?
• Is there a relationship between two variables?

What skills are tested?

• Matching a data set to its graphical representation
• Matching a graphical representation to a description
• Using data representations to solve problems

How are qualitative data displayed?

• A vertical bar chart lists the categories of the qualitative variable along a horizontal axis and uses the heights of the bars on the vertical axis to show the values of the quantitative variable. A horizontal bar chart lists the categories along the vertical axis and uses the lengths of the bars on the horizontal axis to show the values of the quantitative variable. This display draws attention to how the categories rank according to the amount of data within each. Example The heights of the bars show the number of students who want to study each language. Using the bar chart, we can conclude that the greatest number of students want to study Mandarin and the least number of students want to study Latin.
• A pictograph is like a horizontal bar chart but uses pictures instead of the lengths of bars to represent the values of the quantitative variable. Each picture represents a certain quantity, and each category can have multiple pictures. Pictographs are visually interesting, but require us to use the legend to convert the number of pictures to quantitative values. Example Each represents 40 ‍   students. The number of pictures shows the number of students who want to study each language. Using the pictograph, we can conclude that twice as many students want to study French as want to study Latin.
• A circle graph (or pie chart) is a circle that is divided into as many sections as there are categories of the qualitative variable. The area of each section represents, for each category, the value of the quantitative data as a fraction of the sum of values. The fractions sum to 1 ‍   . Sometimes the section labels include both the category and the associated value or percent value for that category. Example The area of each section represents the fraction of students who want to study that language. Using the circle graph, we can conclude that just under 1 2 ‍   the students want to study Mandarin and about 1 3 ‍   want to study Spanish.

How are quantitative data displayed?

• Dotplots use one dot for each data point. The dots are plotted above their corresponding values on a number line. The number of dots above each specific value represents the count of that value. Dotplots show the value of each data point and are practical for small data sets. Example Each dot represents the typical travel time to school for one student. Using the dotplot, we can conclude that the most common travel time is 10 ‍   minutes. We can also see that the values for travel time range from 5 ‍   to 35 ‍   minutes.
• Histograms divide the horizontal axis into equal-sized intervals and use the heights of the bars to show the count or percent of data within each interval. By convention, each interval includes the lower boundary but not the upper one. Histograms show only totals for the intervals, not specific data points. Example The height of each bar represents the number of students having a typical travel time within the corresponding interval. Using the histogram, we can conclude that the most common travel time is between 10 ‍   and 15 ‍   minutes and that all typical travel times are between 5 ‍   and 40 ‍   minutes.

How are trends over time displayed?

How are relationships between variables displayed.

• (Choice A)   A
• (Choice B)   B
• (Choice C)   C
• (Choice D)   D
• (Choice E)   E
• Your answer should be
• an integer, like 6 ‍  
• a simplified proper fraction, like 3 / 5 ‍  
• a simplified improper fraction, like 7 / 4 ‍  
• a mixed number, like 1   3 / 4 ‍  
• an exact decimal, like 0.75 ‍  
• a multiple of pi, like 12   pi ‍   or 2 / 3   pi ‍  
• a proper fraction, like 1 / 2 ‍   or 6 / 10 ‍  
• an improper fraction, like 10 / 7 ‍   or 14 / 8 ‍  

Things to remember

• When matching data to a representation, check that the values are graphed accurately for all categories.
• When reporting data counts or fractions, be clear whether a question asks about data within a single category or a comparison between categories.
• When finding the number or fraction of the data meeting a criteria, watch for key words such as or , and , less than , and more than .

Want to join the conversation?

• Upvote Button navigates to signup page
• Downvote Button navigates to signup page
• Flag Button navigates to signup page

• ACT Exam Info
• What's Tested on the ACT
• What's a Good ACT Score?
• ACT Test Dates
• ACT Math Tips and Tricks
• ACT English Tips and Tricks
• ACT Reading Tips and Tricks
• ACT Science Tips and Tricks
• Applying to College
• ACT Question of the Day
• ACT Pop Quiz
• ACT 20-Minute Workout
• Free ACT Practice Test
• ACT Prep Courses

ACT Science: Data Representation

Locate the label (or label it yourself).

When you come across a table or a graph, read all of the labels. What is this chart called? If there is no label, or it is generic (such as “Table 1” or “Figure 1”), go back to the paragraph and see how the table or figure is described and then write a title yourself above the table/graph. Always locate the label for each set of data as you go. This will help you later figure out where to refer back for the correct answer.

Find out what the axes/columns/rows represent

Just like we located the label for the entire table, you will also need to read and understand each part of the data. Don’t let an eagerness to get to those questions prevent you from reading the fine-print first! What is on the x-axis? What is on the y-axis? What is the label for each row and column? What are the individual parts of the diagram? You can’t skip the small stuff and feel free to underline and circle to your heart’s content. Anything that helps you remember is useful!

Note the units of measurement

If heat is a variable, is it in Fahrenheit or Celsius? Is the mass in grams, kilograms, pounds? It may sound silly, but this can help you answer questions quickly and correctly later on! Check to see if there are little asterisks (*) at the bottom of the table or graph. They can offer some important supplemental information, so make sure to read those too!

Note the overall trends in the data

You might also like.

Call 1-800-KAP-TEST or email [email protected]

Prep for an Exam

MCAT Test Prep

LSAT Test Prep

GRE Test Prep

GMAT Test Prep

SAT Test Prep

ACT Test Prep

DAT Test Prep

NCLEX Test Prep

USMLE Test Prep

Courses by Location

NCLEX Locations

GRE Locations

SAT Locations

LSAT Locations

MCAT Locations

GMAT Locations

Useful Links

Kaplan Test Prep Contact Us Partner Solutions Work for Kaplan Terms and Conditions Privacy Policy CA Privacy Policy Trademark Directory

Create Your Folder And File

Change name, enter your email ( requried * ).

You can upload any content you feel is missing or add more resource to any specific category. Just be on that specific folder and click upload. After approval, your content will be live on PapaCambridge.

Create Your Folder

Upload files.

• AS & A Level
• Past Papers
• Other Resource

Share this page

Data representation Topical Past Papers Computer Science 0478 IGCSE Past Papers

Common search terms:, past papers , past papers 1.1.1-binary-systems.pdf data representation 1.1.1-binary-systems.pdf topical past papers 1.1.1-binary-systems.pdf data representation 1.1.1-binary-systems.pdf computer science - 0478 1.1.1-binary-systems.pdf data representation 1.1.1-binary-systems.pdf topical past papers 1.1.1-binary-systems.pdf data representation 1.1.1-binary-systems.pdf igcse 1.1.1-binary-systems.pdf data representation 1.1.1-binary-systems.pdf topical past papers 1.1.1-binary-systems.pdf data representation 1.1.1-binary-systems.pdf computer science - 0478 1.1.1-binary-systems.pdf data representation 1.1.1-binary-systems.pdf topical past papers 1.1.1-binary-systems.pdf data representation 1.1.1-binary-systems.pdf may june 2024, past papers 1.1.1-binary-systems.pdf data representation 1.1.1-binary-systems.pdf topical past papers 1.1.1-binary-systems.pdf data representation 1.1.1-binary-systems.pdf computer science - 0478 1.1.1-binary-systems.pdf data representation 1.1.1-binary-systems.pdf topical past papers 1.1.1-binary-systems.pdf data representation 1.1.1-binary-systems.pdf igcse 1.1.1-binary-systems.pdf data representation 1.1.1-binary-systems.pdf topical past papers 1.1.1-binary-systems.pdf data representation 1.1.1-binary-systems.pdf computer science - 0478 1.1.1-binary-systems.pdf data representation 1.1.1-binary-systems.pdf topical past papers 1.1.1-binary-systems.pdf data representation 1.1.1-binary-systems.pdf march 2024, question papers 1.1.1-binary-systems.pdf data representation 1.1.1-binary-systems.pdf topical past papers 1.1.1-binary-systems.pdf data representation 1.1.1-binary-systems.pdf computer science - 0478 1.1.1-binary-systems.pdf data representation 1.1.1-binary-systems.pdf topical past papers 1.1.1-binary-systems.pdf data representation 1.1.1-binary-systems.pdf igcse 1.1.1-binary-systems.pdf data representation 1.1.1-binary-systems.pdf topical past papers 1.1.1-binary-systems.pdf data representation 1.1.1-binary-systems.pdf computer science - 0478 1.1.1-binary-systems.pdf data representation 1.1.1-binary-systems.pdf topical past papers 1.1.1-binary-systems.pdf data representation 1.1.1-binary-systems.pdf 2024, mark scheme 1.1.1-binary-systems.pdf data representation 1.1.1-binary-systems.pdf topical past papers 1.1.1-binary-systems.pdf data representation 1.1.1-binary-systems.pdf computer science - 0478 1.1.1-binary-systems.pdf data representation 1.1.1-binary-systems.pdf topical past papers 1.1.1-binary-systems.pdf data representation 1.1.1-binary-systems.pdf igcse 1.1.1-binary-systems.pdf data representation 1.1.1-binary-systems.pdf topical past papers 1.1.1-binary-systems.pdf data representation 1.1.1-binary-systems.pdf computer science - 0478 1.1.1-binary-systems.pdf data representation 1.1.1-binary-systems.pdf topical past papers 1.1.1-binary-systems.pdf data representation 1.1.1-binary-systems.pdf 2024, grade thresholds 1.1.1-binary-systems.pdf data representation 1.1.1-binary-systems.pdf topical past papers 1.1.1-binary-systems.pdf data representation 1.1.1-binary-systems.pdf computer science - 0478 1.1.1-binary-systems.pdf data representation 1.1.1-binary-systems.pdf topical past papers 1.1.1-binary-systems.pdf data representation 1.1.1-binary-systems.pdf igcse 1.1.1-binary-systems.pdf data representation 1.1.1-binary-systems.pdf topical past papers 1.1.1-binary-systems.pdf data representation 1.1.1-binary-systems.pdf computer science - 0478 1.1.1-binary-systems.pdf data representation 1.1.1-binary-systems.pdf topical past papers 1.1.1-binary-systems.pdf data representation 1.1.1-binary-systems.pdf 2024, confidential instructions 1.1.1-binary-systems.pdf data representation 1.1.1-binary-systems.pdf topical past papers 1.1.1-binary-systems.pdf data representation 1.1.1-binary-systems.pdf computer science - 0478 1.1.1-binary-systems.pdf data representation 1.1.1-binary-systems.pdf topical past papers 1.1.1-binary-systems.pdf data representation 1.1.1-binary-systems.pdf igcse 1.1.1-binary-systems.pdf data representation 1.1.1-binary-systems.pdf topical past papers 1.1.1-binary-systems.pdf data representation 1.1.1-binary-systems.pdf computer science - 0478 1.1.1-binary-systems.pdf data representation 1.1.1-binary-systems.pdf topical past papers 1.1.1-binary-systems.pdf data representation 1.1.1-binary-systems.pdf 2024, examiner reports latest 1.1.1-binary-systems.pdf data representation 1.1.1-binary-systems.pdf topical past papers 1.1.1-binary-systems.pdf data representation 1.1.1-binary-systems.pdf computer science - 0478 1.1.1-binary-systems.pdf data representation 1.1.1-binary-systems.pdf topical past papers 1.1.1-binary-systems.pdf data representation 1.1.1-binary-systems.pdf igcse 1.1.1-binary-systems.pdf data representation 1.1.1-binary-systems.pdf topical past papers 1.1.1-binary-systems.pdf data representation 1.1.1-binary-systems.pdf computer science - 0478 1.1.1-binary-systems.pdf data representation 1.1.1-binary-systems.pdf topical past papers 1.1.1-binary-systems.pdf data representation 1.1.1-binary-systems.pdf 2024, 📑 update(s):, 11/01/2024 :, may / june 2023 and oct / nov 2023 past papers are updated., 24/08/2023 :, caie a levels, o levels and igcse 2023 past papers of march and may /june are updated, 24/03/2023 :, caie a levels have new 2022 updated topical past papers with answers. exclusively available on papacambridge, 12/01/2023 :, october and november 2023 past papers of caie are updated., 2022 and 2023 updates :, 17/10/2022 past papers section is upgraded., may june 2022 and feb march 2022 past papers are updated..

if any paper paper is still missing, please report using the Contact Us! tab.

   1.1.1-Binary-systems.pdf

Download app now.

Get our app now and unlock exclusive features

Click here Or Scan QR.

For Android

Data Representation

Lesson Presentations

Exam Style Questions

Binary Numbers

Binary Numbers (2)

Compression

Quizlet - Data Representation

Data Representation

Class 11 - computer science with python sumita arora, checkpoint 2.1.

What are the bases of decimal, octal, binary and hexadecimal systems ?

The bases are:

• Decimal — Base 10
• Octal — Base 8
• Binary — Base 2
• Hexadecimal — Base 16

What is the common property of decimal, octal, binary and hexadecimal number systems ?

Decimal, octal, binary and hexadecimal number systems are all positional-value system .

Complete the sequence of following binary numbers : 100, 101, 110, ............... , ............... , ............... .

100, 101, 110, 111 , 1000 , 1001 .

Complete the sequence of following octal numbers : 525, 526, 527, ............... , ............... , ............... .

525, 526, 527, 530 , 531 , 532 .

Complete the sequence of following hexadecimal numbers : 17, 18, 19, ............... , ............... , ............... .

17, 18, 19, 1A , 1B , 1C .

Convert the following binary numbers to decimal and hexadecimal:

(c) 101011111

(e) 10010101

(f) 11011100

Converting to decimal:

Equivalent decimal number = 8 + 2 = 10

Therefore, (1010) 2 = (10) 10

Converting to hexadecimal:

Grouping in bits of 4:

1010 undefined \underlinesegment{1010} 1010 ​

Therefore, (1010) 2 = (A) 16

Equivalent decimal number = 32 + 16 + 8 + 2 = 58

Therefore, (111010) 2 = (58) 10

0011 undefined 1010 undefined \underlinesegment{0011} \quad \underlinesegment{1010} 0011 ​ 1010 ​

Therefore, (111010) 2 = (3A) 16

Equivalent decimal number = 256 + 64 + 16 + 8 + 4 + 2 + 1 = 351

Therefore, (101011111) 2 = (351) 10

0001 undefined 0101 undefined 1111 undefined \underlinesegment{0001} \quad \underlinesegment{0101} \quad \underlinesegment{1111} 0001 ​ 0101 ​ 1111 ​

Therefore, (101011111) 2 = (15F) 16

Equivalent decimal number = 8 + 4 = 12

Therefore, (1100) 2 = (12) 10

1100 undefined \underlinesegment{1100} 1100 ​

Therefore, (1100) 2 = (C) 16

Equivalent decimal number = 1 + 4 + 16 + 128 = 149

Therefore, (10010101) 2 = (149) 10

1001 undefined 0101 undefined \underlinesegment{1001} \quad \underlinesegment{0101} 1001 ​ 0101 ​

Therefore, (101011111) 2 = (95) 16

Equivalent decimal number = 4 + 8 + 16 + 64 + 128 = 220

Therefore, (11011100) 2 = (220) 10

1101 undefined 1100 undefined \underlinesegment{1101} \quad \underlinesegment{1100} 1101 ​ 1100 ​

Therefore, (11011100) 2 = (DC) 16

Convert the following decimal numbers to binary and octal :

Converting to binary:

Therefore, (23) 10 = (10111) 2

Converting to octal:

Therefore, (23) 10 = (27) 8

Therefore, (100) 10 = (1100100) 2

Therefore, (100) 10 = (144) 8

Therefore, (145) 10 = (10010001) 2

Therefore, (145) 10 = (221) 8

Therefore, (19) 10 = (10011) 2

Therefore, (19) 10 = (23) 8

Therefore, (121) 10 = (1111001) 2

Therefore, (121) 10 = (171) 8

Therefore, (161) 10 = (10100001) 2

Therefore, (161) 10 = (241) 8

Convert the following hexadecimal numbers to binary :

(A6) 16 = (10100110) 2

(A07) 16 = (101000000111) 2

(7AB4) 16 = (111101010110100) 2

(BE) 16 = (10111110) 2

(BC9) 16 = (101111001001) 2

(9BC8) 16 = (1001101111001000) 2

Convert the following binary numbers to hexadecimal and octal :

(a) 10011011101

(b) 1111011101011011

(c) 11010111010111

(d) 1010110110111

(e) 10110111011011

(f) 1111101110101111

0100 undefined 1101 undefined 1101 undefined \underlinesegment{0100} \quad \underlinesegment{1101} \quad \underlinesegment{1101} 0100 ​ 1101 ​ 1101 ​

Therefore, (10011011101) 2 = (4DD) 16

Converting to Octal:

Grouping in bits of 3:

010 undefined 011 undefined 011 undefined 101 undefined \underlinesegment{010} \quad \underlinesegment{011} \quad \underlinesegment{011} \quad \underlinesegment{101} 010 ​ 011 ​ 011 ​ 101 ​

Therefore, (10011011101) 2 = (2335) 8

1111 undefined 0111 undefined 0101 undefined 1011 undefined \underlinesegment{1111} \quad \underlinesegment{0111} \quad \underlinesegment{0101} \quad \underlinesegment{1011} 1111 ​ 0111 ​ 0101 ​ 1011 ​

Therefore, (1111011101011011) 2 = (F75B) 16

001 undefined 111 undefined 011 undefined 101 undefined 011 undefined 011 undefined \underlinesegment{001} \quad \underlinesegment{111} \quad \underlinesegment{011} \quad \underlinesegment{101} \quad \underlinesegment{011} \quad \underlinesegment{011} 001 ​ 111 ​ 011 ​ 101 ​ 011 ​ 011 ​

Therefore, (1111011101011011) 2 = (173533) 8

0011 undefined 0101 undefined 1101 undefined 0111 undefined \underlinesegment{0011} \quad \underlinesegment{0101} \quad \underlinesegment{1101} \quad \underlinesegment{0111} 0011 ​ 0101 ​ 1101 ​ 0111 ​

Therefore, (11010111010111) 2 = (35D7) 16

011 undefined 010 undefined 111 undefined 010 undefined 111 undefined \underlinesegment{011} \quad \underlinesegment{010} \quad \underlinesegment{111} \quad \underlinesegment{010} \quad \underlinesegment{111} 011 ​ 010 ​ 111 ​ 010 ​ 111 ​

Therefore, (11010111010111) 2 = (32727) 8

0001 undefined 0101 undefined 1011 undefined 0111 undefined \underlinesegment{0001} \quad \underlinesegment{0101} \quad \underlinesegment{1011} \quad \underlinesegment{0111} 0001 ​ 0101 ​ 1011 ​ 0111 ​

Therefore, (1010110110111) 2 = (15B7) 16

001 undefined 010 undefined 110 undefined 110 undefined 111 undefined \underlinesegment{001} \quad \underlinesegment{010} \quad \underlinesegment{110} \quad \underlinesegment{110} \quad \underlinesegment{111} 001 ​ 010 ​ 110 ​ 110 ​ 111 ​

Therefore, (1010110110111) 2 = (12667) 8

0010 undefined 1101 undefined 1101 undefined 1011 undefined \underlinesegment{0010} \quad \underlinesegment{1101} \quad \underlinesegment{1101} \quad \underlinesegment{1011} 0010 ​ 1101 ​ 1101 ​ 1011 ​

Therefore, (10110111011011) 2 = (2DDB) 16

010 undefined 110 undefined 111 undefined 011 undefined 011 undefined \underlinesegment{010} \quad \underlinesegment{110} \quad \underlinesegment{111} \quad \underlinesegment{011} \quad \underlinesegment{011} 010 ​ 110 ​ 111 ​ 011 ​ 011 ​

Therefore, (10110111011011) 2 = (26733) 8

1111 undefined 1011 undefined 1010 undefined 1111 undefined \underlinesegment{1111} \quad \underlinesegment{1011} \quad \underlinesegment{1010} \quad \underlinesegment{1111} 1111 ​ 1011 ​ 1010 ​ 1111 ​

Therefore, (1111101110101111) 2 = (FBAF) 16

001 undefined 111 undefined 101 undefined 110 undefined 101 undefined 111 undefined \underlinesegment{001} \quad \underlinesegment{111} \quad \underlinesegment{101} \quad \underlinesegment{110} \quad \underlinesegment{101} \quad \underlinesegment{111} 001 ​ 111 ​ 101 ​ 110 ​ 101 ​ 111 ​

Therefore, (1111101110101111) 2 = (175657) 8

Checkpoint 2.2

Multiple choice questions.

The value of radix in binary number system is ..........

The value of radix in octal number system is ..........

The value of radix in decimal number system is ..........

The value of radix in hexadecimal number system is ..........

Which of the following are not valid symbols in octal number system ?

Which of the following are not valid symbols in hexadecimal number system ?

Which of the following are not valid symbols in decimal number system ?

The hexadecimal digits are 1 to 0 and A to ..........

The binary equivalent of the decimal number 10 is ..........

Question 10

ASCII code is a 7 bit code for ..........

• other symbol
• all of these ✓

Question 11

How many bytes are there in 1011 1001 0110 1110 numbers?

Question 12

The binary equivalent of the octal Numbers 13.54 is.....

• 1101.1110 ✓
• None of these

Question 13

The octal equivalent of 111 010 is.....

Question 14

The input hexadecimal representation of 1110 is ..........

Question 15

Which of the following is not a binary number ?

Question 16

Convert the hexadecimal number 2C to decimal:

Question 17

UTF8 is a type of .......... encoding.

• extended ASCII

Question 18

UTF32 is a type of .......... encoding.

Question 19

Which of the following is not a valid UTF8 representation?

• 2 octet (16 bits)
• 3 octet (24 bits)
• 4 octet (32 bits)
• 8 octet (64 bits) ✓

Question 20

Which of the following is not a valid encoding scheme for characters ?

Fill in the Blanks

The Decimal number system is composed of 10 unique symbols.

The Binary number system is composed of 2 unique symbols.

The Octal number system is composed of 8 unique symbols.

The Hexadecimal number system is composed of 16 unique symbols.

The illegal digits of octal number system are 8 and 9 .

Hexadecimal number system recognizes symbols 0 to 9 and A to F .

Each octal number is replaced with 3 bits in octal to binary conversion.

Each Hexadecimal number is replaced with 4 bits in Hex to binary conversion.

ASCII is a 7 bit code while extended ASCII is a 8 bit code.

The Unicode encoding scheme can represent all symbols/characters of most languages.

The ISCII encoding scheme represents Indian Languages' characters on computers.

UTF8 can take upto 4 bytes to represent a symbol.

UTF32 takes exactly 4 bytes to represent a symbol.

Unicode value of a symbol is called code point .

True/False Questions

A computer can work with Decimal number system. False

A computer can work with Binary number system. True

The number of unique symbols in Hexadecimal number system is 15. False

Number systems can also represent characters. False

ISCII is an encoding scheme created for Indian language characters. True

Unicode is able to represent nearly all languages' characters. True

UTF8 is a fixed-length encoding scheme. False

UTF32 is a fixed-length encoding scheme. True

UTF8 is a variable-length encoding scheme and can represent characters in 1 through 4 bytes. True

UTF8 and UTF32 are the only encoding schemes supported by Unicode. False

Type A: Short Answer Questions

What are some number systems used by computers ?

The most commonly used number systems are decimal, binary, octal and hexadecimal number systems.

What is the use of Hexadecimal number system on computers ?

The Hexadecimal number system is used in computers to specify memory addresses (which are 16-bit or 32-bit long). For example, a memory address 1101011010101111 is a big binary address but with hex it is D6AF which is easier to remember. The Hexadecimal number system is also used to represent colour codes. For example, FFFFFF represents White, FF0000 represents Red, etc.

What does radix or base signify ?

The radix or base of a number system signifies how many unique symbols or digits are used in the number system to represent numbers. For example, the decimal number system has a radix or base of 10 meaning it uses 10 digits from 0 to 9 to represent numbers.

What is the use of encoding schemes ?

Encoding schemes help Computers represent and recognize letters, numbers and symbols. It provides a predetermined set of codes for each recognized letter, number and symbol. Most popular encoding schemes are ASCI, Unicode, ISCII, etc.

Discuss UTF-8 encoding scheme.

UTF-8 is a variable width encoding that can represent every character in Unicode character set. The code unit of UTF-8 is 8 bits called an octet. It uses 1 to maximum 6 octets to represent code points depending on their size i.e. sometimes it uses 8 bits to store the character, other times 16 or 24 or more bits. It is a type of multi-byte encoding.

How is UTF-8 encoding scheme different from UTF-32 encoding scheme ?

UTF-8 is a variable length encoding scheme that uses different number of bytes to represent different characters whereas UTF-32 is a fixed length encoding scheme that uses exactly 4 bytes to represent all Unicode code points.

What is the most significant bit and the least significant bit in a binary code ?

In a binary code, the leftmost bit is called the most significant bit or MSB. It carries the largest weight. The rightmost bit is called the least significant bit or LSB. It carries the smallest weight. For example:

1 M S B 0 1 1 0 1 1 0 L S B \begin{matrix} \underset{\bold{MSB}}{1} & 0 & 1 & 1 & 0 & 1 & 1 & \underset{\bold{LSB}}{0} \end{matrix} MSB 1 ​ ​ 0 ​ 1 ​ 1 ​ 0 ​ 1 ​ 1 ​ LSB 0 ​ ​

What are ASCII and extended ASCII encoding schemes ?

ASCII encoding scheme uses a 7-bit code and it represents 128 characters. Its advantages are simplicity and efficiency. Extended ASCII encoding scheme uses a 8-bit code and it represents 256 characters.

What is the utility of ISCII encoding scheme ?

ISCII or Indian Standard Code for Information Interchange can be used to represent Indian languages on the computer. It supports Indian languages that follow both Devanagari script and other scripts like Tamil, Bengali, Oriya, Assamese, etc.

What is Unicode ? What is its significance ?

Unicode is a universal character encoding scheme that can represent different sets of characters belonging to different languages by assigning a number to each of the character. It has the following significance:

• It defines all the characters needed for writing the majority of known languages in use today across the world.
• It is a superset of all other character sets.
• It is used to represent characters across different platforms and programs.

What all encoding schemes does Unicode use to represent characters ?

Unicode uses UTF-8, UTF-16 and UTF-32 encoding schemes.

What are ASCII and ISCII ? Why are these used ?

ASCII stands for American Standard Code for Information Interchange. It uses a 7-bit code and it can represent 128 characters. ASCII code is mostly used to represent the characters of English language, standard keyboard characters as well as control characters like Carriage Return and Form Feed. ISCII stands for Indian Standard Code for Information Interchange. It uses a 8-bit code and it can represent 256 characters. It retains all ASCII characters and offers coding for Indian scripts also. Majority of the Indian languages can be represented using ISCII.

What are UTF-8 and UTF-32 encoding schemes. Which one is more popular encoding scheme ?

UTF-8 is a variable length encoding scheme that uses different number of bytes to represent different characters whereas UTF-32 is a fixed length encoding scheme that uses exactly 4 bytes to represent all Unicode code points. UTF-8 is the more popular encoding scheme.

What do you understand by code point ?

Code point refers to a code from a code space that represents a single character from the character set represented by an encoding scheme. For example, 0x41 is one code point of ASCII that represents character 'A'.

What is the difference between fixed length and variable length encoding schemes ?

Variable length encoding scheme uses different number of bytes or octets (set of 8 bits) to represent different characters whereas fixed length encoding scheme uses a fixed number of bytes to represent different characters.

Type B: Application Based Questions

Convert the following binary numbers to decimal:

Equivalent decimal number = 1 + 4 + 8 = 13

Therefore, (1101) 2 = (13) 10

Equivalent decimal number = 2 + 8 + 16 + 32 = 58

Equivalent decimal number = 1 + 2 + 4 + 8 + 16 + 64 + 256 = 351

Convert the following binary numbers to decimal :

Equivalent decimal number = 4 + 8 = 12

(b) 10010101

(c) 11011100

Convert the following decimal numbers to binary:

Therefore, (0.25) 10 = (0.01) 2

Therefore, (122) 10 = (1111010) 2

(We stop after 5 iterations if fractional part doesn't become 0)

Therefore, (0.675) 10 = (0.10101) 2

Convert the following decimal numbers to octal:

Therefore, (122) 10 = (172) 8

Therefore, (0.675) 10 = (0.53146) 8

Convert the following hexadecimal numbers to binary:

(23D) 16 = (1000111101) 2

Convert the following binary numbers to hexadecimal:

(a) 1010110110111

(b) 10110111011011

(c) 0110101100

0001 undefined 1010 undefined 1100 undefined \underlinesegment{0001} \quad \underlinesegment{1010} \quad \underlinesegment{1100} 0001 ​ 1010 ​ 1100 ​

Therefore, (0110101100) 2 = (1AC) 16

Convert the following octal numbers to decimal:

Equivalent decimal number = 7 + 40 + 128 = 175

Therefore, (257) 8 = (175) 10

Equivalent decimal number = 7 + 16 + 320 + 1536 = 1879

Therefore, (3527) 8 = (1879) 10

Equivalent decimal number = 3 + 16 + 64 = 83

Therefore, (123) 8 = (83) 10

Integral part

Fractional part

Equivalent decimal number = 5 + 384 + 0.125 + 0.0312 = 389.1562

Therefore, (605.12) 8 = (389.1562) 10

Convert the following hexadecimal numbers to decimal:

Equivalent decimal number = 6 + 160 = 166

Therefore, (A6) 16 = (166) 10

Equivalent decimal number = 11 + 48 + 256 + 40960 = 41275

Therefore, (A13B) 16 = (41275) 10

Equivalent decimal number = 5 + 160 + 768 = 933

Therefore, (3A5) 16 = (933) 10

Equivalent decimal number = 9 + 224 = 233

Therefore, (E9) 16 = (233) 10

Equivalent decimal number = 3 + 160 + 3072 + 28672 = 31907

Therefore, (7CA3) 16 = (31907) 10

Convert the following decimal numbers to hexadecimal:

Therefore, (132) 10 = (84) 16

Therefore, (2352) 10 = (930) 16

Therefore, (122) 10 = (7A) 16

Therefore, (0.675) 10 = (0.ACCCC) 16

Therefore, (206) 10 = (CE) 16

Therefore, (3619) 10 = (E23) 16

Convert the following hexadecimal numbers to octal:

(38AC) 16 = (11100010101100) 2

011 undefined   100 undefined   010 undefined   101 undefined   100 undefined \underlinesegment{011}\medspace\underlinesegment{100}\medspace\underlinesegment{010}\medspace\underlinesegment{101}\medspace\underlinesegment{100} 011 ​ 100 ​ 010 ​ 101 ​ 100 ​

(38AC) 16 = (34254) 8

(7FD6) 16 = (111111111010110) 2

111 undefined   111 undefined   111 undefined   010 undefined   110 undefined \underlinesegment{111}\medspace\underlinesegment{111}\medspace\underlinesegment{111}\medspace\underlinesegment{010}\medspace\underlinesegment{110} 111 ​ 111 ​ 111 ​ 010 ​ 110 ​

(7FD6) 16 = (77726) 8

(ABCD) 16 = (1010101111001101) 2

001 undefined   010 undefined   101 undefined   111 undefined   001 undefined   101 undefined \underlinesegment{001}\medspace\underlinesegment{010}\medspace\underlinesegment{101}\medspace\underlinesegment{111}\medspace\underlinesegment{001}\medspace\underlinesegment{101} 001 ​ 010 ​ 101 ​ 111 ​ 001 ​ 101 ​

(ABCD) 16 = (125715) 8

Convert the following octal numbers to binary:

Therefore, (123) 8 = ( 001 undefined   010 undefined   011 undefined \bold{\underlinesegment{001}}\medspace\bold{\underlinesegment{010}}\medspace\bold{\underlinesegment{011}} 001 ​ 010 ​ 011 ​ ) 2

Therefore, (3527) 8 = ( 011 undefined   101 undefined   010 undefined   111 undefined \bold{\underlinesegment{011}}\medspace\bold{\underlinesegment{101}}\medspace\bold{\underlinesegment{010}}\medspace\bold{\underlinesegment{111}} 011 ​ 101 ​ 010 ​ 111 ​ ) 2

Therefore, (705) 8 = ( 111 undefined   000 undefined   101 undefined \bold{\underlinesegment{111}}\medspace\bold{\underlinesegment{000}}\medspace\bold{\underlinesegment{101}} 111 ​ 000 ​ 101 ​ ) 2

Therefore, (7642) 8 = ( 111 undefined   110 undefined   100 undefined   010 undefined \bold{\underlinesegment{111}}\medspace\bold{\underlinesegment{110}}\medspace\bold{\underlinesegment{100}}\medspace\bold{\underlinesegment{010}} 111 ​ 110 ​ 100 ​ 010 ​ ) 2

Therefore, (7015) 8 = ( 111 undefined   000 undefined   001 undefined   101 undefined \bold{\underlinesegment{111}}\medspace\bold{\underlinesegment{000}}\medspace\bold{\underlinesegment{001}}\medspace\bold{\underlinesegment{101}} 111 ​ 000 ​ 001 ​ 101 ​ ) 2

Therefore, (3576) 8 = ( 011 undefined   101 undefined   111 undefined   110 undefined \bold{\underlinesegment{011}}\medspace\bold{\underlinesegment{101}}\medspace\bold{\underlinesegment{111}}\medspace\bold{\underlinesegment{110}} 011 ​ 101 ​ 111 ​ 110 ​ ) 2

Convert the following binary numbers to octal

111 undefined 010 undefined \underlinesegment{111} \quad \underlinesegment{010} 111 ​ 010 ​

Therefore, (111010) 2 = (72) 8

(b) 110110101

110 undefined 110 undefined 101 undefined \underlinesegment{110} \quad \underlinesegment{110} \quad \underlinesegment{101} 110 ​ 110 ​ 101 ​

Therefore, (110110101) 2 = (665) 8

(c) 1101100001

001 undefined 101 undefined 100 undefined 001 undefined \underlinesegment{001} \quad \underlinesegment{101} \quad \underlinesegment{100} \quad \underlinesegment{001} 001 ​ 101 ​ 100 ​ 001 ​

Therefore, (1101100001) 2 = (1541) 8

011 undefined 001 undefined \underlinesegment{011} \quad \underlinesegment{001} 011 ​ 001 ​

Therefore, (11001) 2 = (31) 8

(b) 10101100

010 undefined 101 undefined 100 undefined \underlinesegment{010} \quad \underlinesegment{101} \quad \underlinesegment{100} 010 ​ 101 ​ 100 ​

Therefore, (10101100) 2 = (254) 8

(c) 111010111

111 undefined 010 undefined 111 undefined \underlinesegment{111} \quad \underlinesegment{010} \quad \underlinesegment{111} 111 ​ 010 ​ 111 ​

Therefore, (111010111) 2 = (727) 8

Add the following binary numbers:

(i) 10110111 and 1100101

1 1 0 1 1 1 0 1 1 1 1 1 1 + 1 1 0 0 1 0 1 1 0 0 0 1 1 1 0 0 \begin{matrix} & & \overset{1}{1} & \overset{1}{0} & 1 & 1 & \overset{1}{0} & \overset{1}{1} & \overset{1}{1} & 1 \\ + & & & 1 & 1 & 0 & 0 & 1 & 0 & 1 \\ \hline & \bold{1} & \bold{0} & \bold{0} & \bold{0} & \bold{1} & \bold{1} & \bold{1} & \bold{0} & \bold{0} \end{matrix} + ​ 1 ​ 1 1 0 ​ 0 1 1 0 ​ 1 1 0 ​ 1 0 1 ​ 0 1 0 1 ​ 1 1 1 1 ​ 1 1 0 0 ​ 1 1 0 ​ ​

Therefore, (10110111) 2 + (1100101) 2 = (100011100) 2

(ii) 110101 and 101111

1 1 1 1 0 1 1 1 0 1 1 + 1 0 1 1 1 1 1 1 0 0 1 0 0 \begin{matrix} & & \overset{1}{1} & \overset{1}{1} & \overset{1}{0} & \overset{1}{1} & \overset{1}{0} & 1 \\ + & & 1 & 0 & 1 & 1 & 1 & 1 \\ \hline & \bold{1} & \bold{1} & \bold{0} & \bold{0} & \bold{1} & \bold{0} & \bold{0} \end{matrix} + ​ 1 ​ 1 1 1 1 ​ 1 1 0 0 ​ 0 1 1 0 ​ 1 1 1 1 ​ 0 1 1 0 ​ 1 1 0 ​ ​

Therefore, (110101) 2 + (101111) 2 = (1100100) 2

(iii) 110111.110 and 11011101.010

0 1 0 1 1 1 1 1 0 1 1 1 1 1 1 1 . 1 1 1 0 + 1 1 0 1 1 1 0 1 . 0 1 0 1 0 0 0 1 0 1 0 1 . 0 0 0 \begin{matrix} & & \overset{1}{0} & \overset{1}{0} & \overset{1}{1} & \overset{1}{1} & \overset{1}{0} & \overset{1}{1} & \overset{1}{1} & \overset{1}{1} & . & \overset{1}{1} & 1 & 0 \\ + & & 1 & 1 & 0 & 1 & 1 & 1 & 0 & 1 & . & 0 & 1 & 0 \\ \hline & \bold{1} & \bold{0} & \bold{0} & \bold{0} & \bold{1} & \bold{0} & \bold{1} & \bold{0} & \bold{1} & \bold{.} & \bold{0} & \bold{0} & \bold{0} \end{matrix} + ​ 1 ​ 0 1 1 0 ​ 0 1 1 0 ​ 1 1 0 0 ​ 1 1 1 1 ​ 0 1 1 0 ​ 1 1 1 1 ​ 1 1 0 0 ​ 1 1 1 1 ​ . . . ​ 1 1 0 0 ​ 1 1 0 ​ 0 0 0 ​ ​

Therefore, (110111.110) 2 + (11011101.010) 2 = (100010101) 2

(iv) 1110.110 and 11010.011

0 1 1 1 1 1 1 0 1 . 1 1 1 0 + 1 1 0 1 0 . 0 1 1 1 0 1 0 0 1 . 0 0 1 \begin{matrix} & & \overset{1}{0} & \overset{1}{1} & \overset{1}{1} & 1 & \overset{1}{0} & . & \overset{1}{1} & 1 & 0 \\ + & & 1 & 1 & 0 & 1 & 0 & . & 0 & 1 & 1 \\ \hline & \bold{1} & \bold{0} & \bold{1} & \bold{0} & \bold{0} & \bold{1} & \bold{.} & \bold{0} & \bold{0} & \bold{1} \end{matrix} + ​ 1 ​ 0 1 1 0 ​ 1 1 1 1 ​ 1 1 0 0 ​ 1 1 0 ​ 0 1 0 1 ​ . . . ​ 1 1 0 0 ​ 1 1 0 ​ 0 1 1 ​ ​

Therefore, (1110.110) 2 + (11010.011) 2 = (101001.001) 2

Question 21

Given that A's code point in ASCII is 65, and a's code point is 97. What is the binary representation of 'A' in ASCII ? (and what's its hexadecimal representation). What is the binary representation of 'a' in ASCII ?

Binary representation of 'A' in ASCII will be binary representation of its code point 65.

Converting 65 to binary:

Therefore, binary representation of 'A' in ASCII is 1000001.

Converting 65 to Hexadecimal:

Therefore, hexadecimal representation of 'A' in ASCII is (41) 16 .

Similarly, converting 97 to binary:

Therefore, binary representation of 'a' in ASCII is 1100001.

Question 22

Convert the following binary numbers to decimal, octal and hexadecimal numbers.

(i) 100101.101

Decimal Conversion of integral part:

Decimal Conversion of fractional part:

Equivalent decimal number = 1 + 4 + 32 + 0.5 + 0.125 = 37.625

Therefore, (100101.101) 2 = (37.625) 10

Octal Conversion

100 undefined 101 undefined . 101 undefined \underlinesegment{100} \quad \underlinesegment{101} \quad \bold{.} \quad \underlinesegment{101} 100 ​ 101 ​ . 101 ​

Therefore, (100101.101) 2 = (45.5) 8

Hexadecimal Conversion

0010 undefined 0101 undefined   .   1010 undefined \underlinesegment{0010} \quad \underlinesegment{0101} \medspace . \medspace \underlinesegment{1010} 0010 ​ 0101 ​ . 1010 ​

Therefore, (100101.101) 2 = (25.A) 16

(ii) 10101100.01011

Equivalent decimal number = 4 + 8 + 32 + 128 + 0.25 + 0.0625 + 0.03125 = 172.34375

Therefore, (10101100.01011) 2 = (172.34375) 10

010 undefined 101 undefined 100 undefined . 010 undefined 110 undefined \underlinesegment{010} \quad \underlinesegment{101} \quad \underlinesegment{100} \quad \bold{.} \quad \underlinesegment{010} \quad \underlinesegment{110} 010 ​ 101 ​ 100 ​ . 010 ​ 110 ​

Therefore, (10101100.01011) 2 = (254.26) 8

1010 undefined 1100 undefined   .   0101 undefined   1000 undefined \underlinesegment{1010} \quad \underlinesegment{1100} \medspace . \medspace \underlinesegment{0101} \medspace \underlinesegment{1000} 1010 ​ 1100 ​ . 0101 ​ 1000 ​

Therefore, (10101100.01011) 2 = (AC.58) 16

Decimal Conversion:

Equivalent decimal number = 2 + 8 = 10

001 undefined 010 undefined \underlinesegment{001} \quad \underlinesegment{010} 001 ​ 010 ​

Therefore, (1010) 2 = (12) 8

(iv) 10101100.010111

Equivalent decimal number = 4 + 8 + 32 + 128 + 0.25 + 0.0625 + 0.03125 + 0.015625 = 172.359375

Therefore, (10101100.010111) 2 = (172.359375) 10

010 undefined 101 undefined 100 undefined . 010 undefined 111 undefined \underlinesegment{010} \quad \underlinesegment{101} \quad \underlinesegment{100} \quad \bold{.} \quad \underlinesegment{010} \quad \underlinesegment{111} 010 ​ 101 ​ 100 ​ . 010 ​ 111 ​

Therefore, (10101100.010111) 2 = (254.27) 8

1010 undefined 1100 undefined   .   0101 undefined   1100 undefined \underlinesegment{1010} \quad \underlinesegment{1100} \medspace . \medspace \underlinesegment{0101} \medspace \underlinesegment{1100} 1010 ​ 1100 ​ . 0101 ​ 1100 ​

Therefore, (10101100.010111) 2 = (AC.5C) 16

Text, Sound and Images ( CIE IGCSE Computer Science )

Topic questions.

The Unicode character set is used to represent text that is typed into a computer.

How did you do?

Did this page help you?

Nina is recording some music tracks that she has written. She is researching whether she should  record them in MIDI or MP3 format. Explain what is meant by MIDI and MP3 format. MIDI ......................................................................................

MP3 ......................................................................................

Have an account?

Data representation and Computer Systems...

Data representation and Computer Systems, IGCSE CS 0478 1.1.1-1.1.3 - dfm

52 questions

Introducing new   Paper mode

No student devices needed.   Know more

• 1. Multiple Choice Edit 2 minutes 1 pt What is 27 in hexadecimal 1B 17 11011 1C
• 2. Multiple Choice Edit 2 minutes 1 pt What is 126 in hexadecimal 7E 111110 76 7F
• 3. Multiple Choice Edit 2 minutes 1 pt What is 253 in hexadecimal FD 11111101 FF CD
• 4. Multiple Choice Edit 1 minute 1 pt Convert 128 to binary 10000000 01111110 10000001 11001100
• 5. Multiple Choice Edit 1 minute 1 pt A byte is 8 bits 4 bits

Which is the smallest form of data?

8 Binary Digits

Which is larger?

Convert 64 to binary

Convert 3 to binary

• 11. Multiple Choice Edit 2 minutes 1 pt 00010111 + 01001100 = 1100011 11100011 1110001 1111011
• 12. Multiple Choice Edit 2 minutes 1 pt 01100110 + 00001101 = 1110011 11110011 1110010 1100011
• 13. Multiple Choice Edit 2 minutes 1 pt 01010101 + 10101010 = 11111111 11111110 11110000 10101011
• 14. Multiple Choice Edit 45 seconds 1 pt Makes the file smaller by deleting parts of the file permanently (forever) Lossy Compression Lossless Compression
• 15. Multiple Choice Edit 45 seconds 1 pt Makes the file smaller by giving repeated patterns/colours a specific code Lossy Compression Lossless Compression
• 16. Multiple Choice Edit 45 seconds 1 pt A set of instructions for the computer to follow Algorithm Iteration
• 17. Multiple Choice Edit 45 seconds 1 pt Which of these is an advantage for Lossy compression? The file size becomes significantly (much) smaller The file size does not become much smaller than 50%

Which of the following would not be suitable for Lossy Compression?

Compression in general makes it _______ to send, upload and stream data

Lossy compression would be suitable for text files

There are _____ different types of compression

• 22. Multiple Choice Edit 30 seconds 1 pt 26. The word “PIXEL:” is a short for which of the following? Perfect elements Picture Elements None of the above
• 23. Multiple Choice Edit 45 seconds 1 pt The code for representing binary as letters and numbers is called SQL ASCII DECIMAL ALPHABET

How do you calculate the number of bits of a body of text in ASCII?

Number of characters * 7

Number of characters (including spaces) *7

bits in Huffman * 7

bits in Huffman / 7

• 27. Multiple Choice Edit 30 seconds 1 pt What logic circuit function performs the inverter function? AND OR NOT NOR

An electronic component on a computer's motherboard that performs arithmetic and logical operations.

Processing device

Processing unit

System processing unit

Central processing unit

• 29. Multiple Choice Edit 30 seconds 1 pt Holds many components of the system and provides connectors for other peripherals. USB Touch screen Motherboard CPU
• 30. Multiple Choice Edit 30 seconds 1 pt Consists of electronic components that store instructions waiting to be executed by the processor Random fetching memory Random execute memory Random access memory Random devices
• 31. Multiple Choice Edit 30 seconds 1 pt What is the function of output device? The device that allow users to do a specific task The device that allow memory to store data The device that convey information to people The device that help printer to print the output
• 32. Multiple Choice Edit 30 seconds 1 pt System software consists of the program that controls the operations of the computer and its devices. Two types of system software are ; Microsoft Word and Windows 10 Utility programs and Windows Operating systems and utility programs Operating system and application software

An input device is defined as . . .

a device that sends data to the end user.

a device that sends data to the computer.

a device that creates soft copy.

a device that creates hard copy.

Which of the following is an example of Optical Storage?

Memory stick

Clock speed in a computer is measured in . . .

• 42. Multiple Choice Edit 20 seconds 1 pt The binary language consists of ____________ digit(s). 8 2 1,000 1
• 43. Multiple Choice Edit 1 minute 1 pt Convert 01011 2 to decimal 11 35 15 10

Storage of 1 KB means the following number of bytes:

• 51. Multiple Choice Edit 1 minute 1 pt What is the output of an OR gate if the inputs are 1 and 0? 0 1 OFF 2
• 52. Multiple Choice Edit 1 minute 1 pt What is the output of an AND gate if the inputs are 1 and 0? ON 2 1 0

Explore all questions with a free account

Continue with email

Continue with phone

AS Level Mechanics and Statistics - Data Presentation and Representation

• Data Structures
• Linked List
• Binary Tree
• Binary Search Tree
• Segment Tree
• Disjoint Set Union
• Fenwick Tree
• Red-Black Tree
• Advanced Data Structures
• Tree Data Structure
• Data Structures | Binary Trees | Question 3
• Data Structures | Binary Trees | Question 4
• Data Structures | Binary Trees | Question 1
• Data Structures | Binary Trees | Question 9
• Data Structures | Binary Trees | Question 12
• Data Structures | Binary Trees | Question 14
• Data Structures | Binary Trees | Question 11
• Data Structures | Binary Trees | Question 13
• Data Structures | Binary Trees | Question 15
• Tango Tree Data Structure
• Applications of tree data structure
• Data Structures | Binary Search Trees | Question 7
• Data Structures | Binary Search Trees | Question 8
• Data Structures | Binary Search Trees | Question 5
• Data Structures | Binary Search Trees | Question 6
• Data Structures | Binary Search Trees | Question 2

Binary Tree Data Structure

A Binary Tree Data Structure is a hierarchical data structure in which each node has at most two children, referred to as the left child and the right child. It is commonly used in computer science for efficient storage and retrieval of data, with various operations such as insertion, deletion, and traversal.

Introduction:

• Introduction to Binary Tree – Data Structure and Algorithm Tutorials
• Properties of Binary Tree
• Types of Binary Tree
• Applications, Advantages and Disadvantages of Binary Tree
• Binary Tree (Array implementation)
• Complete Binary Tree
• Perfect Binary Tree

Basic Operations on Binary Tree:

• Tree Traversals (Inorder, Preorder and Postorder)
• Level Order Tree Traversal
• Find the Maximum Depth or Height of given Binary Tree
• Insertion in a Binary Tree
• Deletion in a Binary Tree
• Enumeration of Binary Trees

Some other important Binary Tree Traversals :

• Level order traversal in spiral form
• Reverse Level Order Traversal
• BFS vs DFS for Binary Tree
• Inorder Tree Traversal without Recursion
• Morris traversal for Preorder
• Iterative Preorder Traversal
• Iterative Postorder Traversal Using Two Stacks
• Diagonal Traversal of Binary Tree
• Boundary Traversal of binary tree

Easy Problems on Binary Tree Data Structure:

• Calculate depth of a full Binary tree from Preorder
• Construct a tree from Inorder and Level order traversals
• Check if a given Binary Tree is SumTree
• Check if two nodes are cousins in a Binary Tree
• Check if removing an edge can divide a Binary Tree in two halves
• Check whether a given binary tree is perfect or not
• Check if a Binary Tree contains duplicate subtrees of size 2 or more
• Check if two trees are Mirror
• Foldable Binary Trees
• Symmetric Tree (Mirror Image of itself)
• Write Code to Determine if Two Trees are Identical
• Subtree with given sum in a Binary Tree
• Succinct Encoding of Binary Tree
• Write a program to Calculate Size of a tree
• Diameter of a Binary Tree
• Get Level of a node in a Binary Tree

Medium Problems on Binary Tree Data Structure:

• Find all possible binary trees with given Inorder Traversal
• Populate Inorder Successor for all nodes
• Construct Complete Binary Tree from its Linked List Representation
• Minimum swap required to convert binary tree to binary search tree
• Convert a given Binary Tree to Doubly Linked List | Set 1
• Convert a tree to forest of even nodes
• Flip Binary Tree
• Print root to leaf paths without using recursion
• Check if given Preorder, Inorder and Postorder traversals are of same tree
• Check whether a given Binary Tree is Complete or not | Set 1 (Iterative Solution)
• Check if a binary tree is subtree of another binary tree | Set 2
• Find largest subtree sum in a tree
• Maximum sum of nodes in Binary tree such that no two are adjacent
• Lowest Common Ancestor in a Binary Tree | Set 1
• Height of a generic tree from parent array
• Find distance between two given keys of a Binary Tree

Hard Problems on Binary Tree Data Structure:

• Modify a binary tree to get Preorder traversal using right pointers only
• Construct Full Binary Tree using its Preorder traversal and Preorder traversal of its mirror tree
• Construct a special tree from given preorder traversal
• Construct tree from ancestor matrix
• Construct the full k-ary tree from its preorder traversal
• Construct Binary Tree from String with bracket representation
• Convert a Binary Tree into Doubly Linked List in spiral fashion
• Convert a Binary Tree to a Circular Doubly Link List
• Convert Ternary Expression to a Binary Tree
• Check if there is a root to leaf path with given sequence
• Remove all nodes which don’t lie in any path with sum>= k
• Maximum spiral sum in Binary Tree
• Sum of nodes at k-th level in a tree represented as string
• Sum of all the numbers that are formed from root to leaf paths
• Merge Two Binary Trees by doing Node Sum (Recursive and Iterative)
• Find root of the tree where children id sum for every node is given

Quick Links :

• ‘Practice Problems’ on Trees
• ‘Quizzes’ on Binary Trees
• ‘Videos’ on Trees

Recommended:

• Learn Data Structure and Algorithms | DSA Tutorial

Please Login to comment...

Similar reads, improve your coding skills with practice.

What kind of Experience do you want to share?