CS50 Quiz 1 Practice Problems
These are some practice problems for quiz 1 of CS50 2012. If there are any similarities between these questions and those on the quiz, they are purely coincidental.
To generate these questions, I went through the notes for each class.
Try doing them on paper to simulate an actual exam environment.
Week 5
Question: What is a file format?
Answer: A standard for how to interpret the bytes in a file.
Q: How many bytes does it take to represent an RGB triple in a bitmap file?
A: 3 bytes, one for each R, G, and B.
Q: How many different colors can be represented given a pixel encoded using 24 bits?
A: 2^24 == 16,777,216 ~ 16 million. Each bit can have two values, so 24 things that can represent two values each gives 2^24 possibilities.
Note: Big powers of two can be approximated quickly. Memorize that 2^10 == 1,024 ~ 1,000. Therefore, 2^20 == (2^10) * (2^10) ~ 1,000,000. Thus, 2^24 == (2^20) * (2^4) ~ 1,000,000 * 16 == 16,000,000.
Q: Aside from this being a useless program, find the error:
#include<stdio.h>
int main(int argc, char* argv[]) {
bool passed_no_args = argc == 1;
if(passed_no_args) printf("You passed no arguments!\n");
else printf("You passed an argument!\n");
return 1;
}
A: Forgot to include stdbool.h or any other library that defines the type bool. The bool data type is not included by default.
Q: What happens when a line cannot be read by GetInt(), as defined in the CS50 Library?
A: INT_MAX is returned, indicating an error occured.
Q: How does GetString() deal with a line of input that contains more characters than it initially allocated for its buffer?
A: It calls realloc, which can modify the size of the buffer.
Week 6
Q: Give some advantages of a linked list over an array.
A: A linked list supports addition and removal of elements in constant time (i.e. the same speed no matter how long the linked list is).
Q: Give some advantages of an array over a linked list.
A: An array supports accessing and modifying any particular element in constant time.
Note: Many languages provide dynamic arrays, which automatically allocate more space for themselves as needed. Examples include vector in C++ and Java’s ArrayList. This isn’t magic; underneath, C++ and Java are using things like realloc which you would use if asked to create dynamic arrays in C. Chances are, however, that there will be fewer bugs and inefficiencies in their versions of dynamic arrays due to the extensive amount of real world testing of the code.
Q: Write the type definition of a singly linked list that stores a pointer to an integer at each node.
A:
typedef struct node {
int* num;
struct node *next;
} node;
Q: Write the type definition of a doubly linked list that stores a pointer to an integer at each node.
A:
typedef struct node {
int* num;
struct node *prev;
struct node *next;
} node;
Q: Using the previous definitions of a linked list node, is it possible to use num to access more than one integer, or is a pointer to an integer just that, a pointer to a single integer?
A: We can use num to access multiple integers if we, for example, call in our code num = (int*)malloc(8 * sizeof(int)); . This would allocate 8 slots, each slot with enough space for an int. We can then use array notation to access and modify the slots.
Q: Assume the variable cur is of type node* using the singly linked list type definition above. What is equivalent code to cur->num[1]?
A: (*cur).num[1]
Q: Write a function that takes in a node* and frees all of the nodes in the list. Assume the singly linked list type definition above.
A:
void free_list(node* list) {
while(list != NULL) {
node* next = list->next;
free(list);
list = next;
}
}
Q: True or false: A queue data structure can be implemented as a special linked list.
A: True.
Q: True or false: A stack data structure can be implemented as a special linked list.
A: True.
Q: Which data structure is LIFO and which is FIFO?
A: A queue is first in first out. A stack is last in first out.
Q: What might this indicate if this is the result of running Valgrind on a program:
HEAP SUMMARY:
in use at exit: 40 bytes in 2 blocks
total heap usage: 2 allocs, 0 frees, 40 bytes allocated
LEAK SUMMARY:
definitely lost: 40 bytes in 2 blocks
A: There’s a memory leak, most likely due to not freeing memory that was allocated by calling malloc or calloc.
Q: What is a desired property of a hash function?
A: A good hash function should map its inputs to outputs in an even manner, minimizing the number of collisions that occur.
Q: What’s a possible way of dealing with collisions in a hash table?
A: Make the hash table an array of linked lists so that the things that map to the same hash function output can be stored.
Q: Write the type definition for a binary search tree, where each node stores an integer.
A:
typedef struct node {
int n;
struct node* left;
struct node* right;
} node;
Q: How many computer scientists does it take to screw in a lightbulb?
A: That’s a hardware issue. Another acceptable answer: The dead bulb is a feature, not a bug.
Week 7
Q: The Huffman character frequency table for a compressed file has been corrupted. Can I decompress this file using another file’s intact character frequency table?
A: If the other file was a copy of this file or extremely similar, there is a chance that the correct Huffman tree will be produced. In all likelihood, however, using a random compressed file’s character frequency table would not correctly decompress this file.
Q: 15 & 2 ==
A: 2
Q: 25 ^ 16 ==
A: 9
Q: 5 | 10 ==
A: 15
Q: 2 << 5
A: 64
Q: At a minimum, how many bytes does it take to store 16 boolean values?
A: 2. A boolean can be represented by a bit. Each bit within a single byte can be individually accessed and modified with bitwise operators.
Q: What type of program is clang?
A: A compiler.
Q: What is the goal of program compilation?
A: Translation of source code that is human-readable into machine code that can be executed by the computer.
Q: Write an HTML file that has a title of “This is” and bold text in the body “CS50”.
A:
<!DOCTYPE html>
<html>
<head>
<title>This is</title>
</head>
<body>
<b>CS50</b>
</body>
</html>
Q: You want to fool someone into clicking a link on your webpage. Use the <a> tag to send someone to http://www.youtube.com/watch?v=dQw4w9WgXcQ while making them think they’re going to facebook.com.
A:
<a href=”http://www.youtube.com/watch?v=dQw4w9WgXcQ”>facebook.com</a>
Q: Is HTML a programming language?
A: No. HTML is a markup language used to tell a web browser how to display a web page.
Q: Why is it a good idea to provide alt text for images?
A: It makes your website more accessible to the visually impaired and those who can’t download the image.
Q: What are the ports used by HTTP, HTTPS, SMTP, SSH?
A: 80, 443, 25, 22, respectively.
Q: Why don’t you have to type a server’s address to access a web page stored on that server?
A: This service is provided by DNS, which translates names like “google.com” to IP addresses like 74.125.226.231.
Q: I try to access hello.html in the appliance, but when I navigate to localhost/hello.html, I get a Forbidden error. When I do ls -l in hello.html‘s directory, I see that it has the permissions -rw-------. What’s the issue and how could I fix it?
A: hello.html is not world-readable. Do chmod a+r to modify permissions so that anyone can see the file.
Week 8
Q: I have a div that has an id called “header”. How do I use CSS to center it?
A:
#header {
text-align: center;
}
Q: Declare an array of the numbers 0, 1, 2, 3, 4, 5 in PHP. How is this array different from that in C?
A:
$numbers = [0, 1, 2, 3, 4, 5];
A PHP array is a hash table, not a contiguous chunk of memory as in C. There is an implicit creation of key-value mappings from the initialization of a PHP array: 0 => 0, 1 => 1, 2 => 2, 3 => 3, 4 => 4, 5 => 5.
Q: What do I add to the program hello.php below to be able to run ./hello.php instead of php hello.php.
<?php
printf("hello, I'm a php program");
?>
A: We need to add #! followed by the path of the program php on our machine. On our machine, we could write #!/bin/php since php is located in the /bin directory. In general, you can do #!/bin/env php, because env is a program that finds and executes the program with the name you give it.
Q: What kind of a variable is $_SESSION in PHP? What is it useful for?
A: $_SESSION is a superglobal and can keep track of user data across web pages during a user’s session. It can be used as a hash table.
Q: Are there scope issues in the code below?
if($argc == 1) {
$message = "no arguments passed";
} else {
$message = "some arguments passed";
}
echo $message;
A: No. In PHP, if statements don’t have their own scope. This means that variables declared inside an if statement can be accessed outside of it as well.
Q: What is a necessary condition for a primary key in a SQL database?
A: A primary key must uniquely identify a row of data in a table.
Week 9
Q: What is the process of factoring out redundant information from a database called?
A: Normalization.
Q: Declare an array with five numbers in Javascript.
A:
var numbers = [0, 1, 2, 3, 4];
Q: What’s the downside of doing client-side validation versus server-side validation?
A: It is not guaranteed that Javascript will be executed on a user’s browser. Client-side validation is therefore not guaranteed to work.
Q: What’s an advantage of using jQuery instead of native Javascript?
A: jQuery solves many issues related to different browsers’ behavior with Javascript. With jQuery, you can write a single piece of code and know that it will work on all major browsers.
Q: What does the code below do?
function submitData(userData, callback) {
$.ajax({
url: 'submit.php',
type: 'POST',
dataType: 'json',
data: userData,
success: function(response) {
callback(response);
}
});
}
A: This is a function that takes in userData and POSTs it to submit.php in the form of json. Upon a successful POST, the server sends a response, which the function passes to the callback function to handle. Note that in Javascript, functions can be passed as arguments. This means that we can pass a function we wrote to submitData and it will be executed after a successful response. This also means that we can pass in different functions if we want to handle responses differently.
woshibo 