1) What is the first step in problem-solving? A) Writing code B) Debugging C) Understanding the problem D) Optimizing the solution Answer: C 2) Which of these is not a step in the problem-solving process? A) Algorithm development B) Problem analysis C) Random guessing D) Testing and debugging Answer: C 3) What is an algorithm? A) A high-level programming language B) A step-by-step procedure to solve a problem C) A flowchart D) A data structure Answer: B 4) Which of these is the simplest data structure for representing a sequence of elements? A) Dictionary B) List C) Set D) Tuple Answer: B 5) What does a flowchart represent? A) Errors in a program B) A graphical representation of an algorithm C) The final solution to a problem D) A set of Python modules Answer: B 6) What is pseudocode? A) Code written in Python B) Fake code written for fun C) An informal high-level description of an algorithm D) A tool for testing code Answer: C 7) Which of the following tools is NOT commonly used in pr...
Directory Structure
Storage Structure
* A disk can be used in its entirety for a file system.
* Alternatively a physical disk can be broken up into multiple partitions, slices, or mini-disks, each of which becomes a virtual disk and can have its own file system. ( or be used for raw storage, swap space, etc. )
* Or, multiple physical disks can be combined into one volume, i.e. a larger virtual disk, with its own file system spanning the physical disks.
* Directory operations to be supported include:
• Search for a file
• Create a file - add to the directory
• Delete a file - erase from the directory
• List a directory - possibly ordered in different ways.
• Rename a file - may change sorting order
• Traverse the file system.
Single-Level Directory
Draw Backs:
* Naming Problem
* Grouping Problem
Two-Level Directory
* Each user gets their own directory space.
* File names only need to be unique within a given user's directory.
* A master file directory is used to keep track of each user’s directory, and must be
maintained when users are added to or removed from the system.
* A separate directory is generally needed for system ( executable ) files.
* Systems may or may not allow users to access other directories besides their own
• If access to other directories is allowed, then provision must be made to specify
the directory being accessed.
• If access is denied, then special consideration must be made for users to run programs located in system directories. A search path is the list of directories in which to search for executable programs, and can be set uniquely for each user.
Tree-Structured Directories
* An obvious extension to the two-tiered directory structure, and the one with which we are all most familiar.
* Each user / process has the concept of a current directory from which all ( relative )
searches take place.
* Files may be accessed using either absolute pathnames ( relative to the root of the tree ) or relative pathnames (relative to the current directory. )
* Directories are stored the same as any other file in the system, except there is a bit that identifies them as directories, and they have some special structure that the OS understands.
* One question for consideration is whether or not to allow the removal of directories that are not empty - Windows requires that directories be emptied first, and UNIX provides an option for deleting entire sub-trees.
Acyclic-Graph Directories
* When the same files need to be accessed in more than one place in the directory structure ( e.g. because they are being shared by more than one user / process ), it can be useful to provide an acyclic-graph structure. ( Note the directed arcs from parent to child. )
* UNIX provides two types of links for implementing the acyclic-graph structure. ( See "man ln" for more details. )
• A hard link ( usually just called a link ) involves multiple directory entries that
both refer to the same file. Hard links are only valid for ordinary files in the same
file system.
• A symbolic link that involves a special file, containing information about where
to find the linked file. Symbolic links may be used to link directories and/or files
in other file systems, as well as ordinary files in the current file system.
* Windows only supports symbolic links, termed shortcuts.
* Hard links require a reference count, or link count for each file, keeping track of how many directory entries are currently referring to this file. Whenever one of the references is removed the link count is reduced, and when it reaches zero, the disk space can be reclaimed.
* For symbolic links there is some question as to what to do with the symbolic links when the original file is moved or deleted:
• One option is to find all the symbolic links and adjust them also.
• Another is to leave the symbolic links dangling, and discover that they are no
longer valid the next time they are used.
• What if the original file is removed, and replaced with another file having the
same name before the symbolic link is next used?
General Graph Directory
* If cycles are allowed in the graphs, then several problems can arise:
• Search algorithms can go into infinite loops. One solution is to not follow links in search algorithms. ( Or not to follow symbolic links, and to only allow symbolic
links to refer to directories. )
• Sub-trees can become disconnected from the rest of the tree and still not have
their reference counts reduced to zero. Periodic garbage collection is required to
detect and resolve this problem. ( chkdsk in DOS and fsck in UNIX search for these problems, among others, even though cycles are not supposed to be allowed
in either system. Disconnected disk blocks that are not marked as free are added
back to the file systems with made-up file names, and can usually be safely
deleted. )
