Stanford Programming Paradigms Flashcards
Name a feature that distinguishes C++ from C
The presence of classes; object-orientation.
C was written by ___ in ___, C++ was written by ___ in ___.
Dennis Ritchie (w/ Bell Labs) wrote C in 1972, Bjarne Stroustrup expanded it to C++ in 1985.
Who designed Java and when did it appear?
James Gosling w/ Sun Microsystems designed Java in 1995.
Assembly is to C/C++ as ___ is to Java
Java bytecode.
In C, when using malloc to set aside 160 bytes in the heap, what actually happens?
A small pre-node header is added in front of the 160 bytes with meta information about the memory being allocated, e.g. it’s length, and a pointer is returned to the actual node. 164 or 168 bytes are actually set aside. You must be aware of this when returning to free the memory later.
Because C does not have automatic garbage collection, if you lose track of a piece of data (e.g. lose reference to it) it is referred to as a ___.
memory leak.
For efficiency and speed, the implementations of malloc and realloc do not perform ___.
error checking, this is the client’s responsibility to write error-free code.
In one implementation of storing dynamic data in the heap, the heap can be organized how? What is a different heuristic?
Into blocks of specific size and data, depending on its size, is always allocated a certain space, e.g. always 8 bytes or always 64 bytes, despite its actual size. Another implementation is to maintain a linked-list of blobs from each end of a piece of data, to search for a large enough free space.
Sometimes in C, an implementation of free may postpone execution until
malloc or realloc are called again, or free memory is actually needed.
In a CPU, local data that is being processed is stored in a
processor register.
The fastest data access in a CPU is provided by
processor registers.
Describe how arithmetic operations are conducted in a CPU?
data is loaded into registers where then it can be manipulated or tested by machine instructions in the arithmetic logic unit, a combinatorial digital electronic circuit.
In compiler optimization, ___ ___ is used to assign locations of program variables for access during execution.
register allocation. Access to registers is much faster than access to RAM.
A single unit of memory is a ___.
A byte is ___.
A KB is ___.
1 bit.
8 bits = 1 byte.
1024 bytes = 1 KB.
Is memory access in the stack or heap faster?
The stack is faster because memory management in the heap is much more involved.
The stack and heap are both stored in
main memory, RAM.
A very efficient way to implement an associative array as a data structure is to use a
hash table, which uses a hash function to map keys to specific integer values which can then be used for direct lookup. The hash function is the challenge, because all the data needs to be mapped evenly by the function (to minimize collisions). The hash function basically computers the index to an array of buckets or slots from the key value. Hash tables tend to be more efficient than search trees or other table structures.
A priority queue is
an abstract data type based on a queue but in which items have priority. Higher priority items will be served before lower priority items, and items of equal priority will be served based on their order in the queue.
Describe a space optimized way of storing a lexicon as a data structure
A radix tree/radix trie/prefix tree which is a tree where each node is part of a prefix of a word and every path through the tree from parent to child represents a valid word.
A binary tree is
A version of the tree data structure in which each parent node has only two children, a left and right child. Binary trees can be used for efficient searching and sorting.
In machine code, how is the type of operation to be performed on a piece of data indicated?
By an opcode which usually precedes the actual data.
