Cs223 midterm topics and sample questions

The midterm for CS 223b is Wednesday February 22nd, in class.

The exam will focus on C programming topics, including the following:

K&R, Van Wyk, and Aspnes
Logical problems.  
Command line arguments
File i/o
Functions
Pointers
Dynamic memory allocation, e.g., malloc, free
Structs
Arrays and strings
Linked lists
Hash tables

*************************************************************************
Review all code in /c/cs223/current/lectures/code including mt directory.
*************************************************************************

Most, if not all, of the questions will be either (a) given the
following code, what are the bugs and fix them? or (b) write a program
to do X.

Here are some sample questions. 

Implement an algorithm to determine if a string has all unique
characters. What if you can not use additional data structures?


Design an algorithm and write code to remove the duplicate characters
in a string without using any additional buffer. NOTE: One or two
additional variables are fine. An extra copy of the array is
not. FOLLOW UP Write the test cases for this function.


Write a function to decide if two strings are anagrams or not. 


Write a function to replace all spaces in a string with ‘%20’. 


The C library function strstr() checks if one word is a substring of
another. Given two strings, s1 and s2, write code to check if s2 is a
rotation of s1 using only one call to strstr() (i.e., “waterbottle” is
a rotation of “erbottlewat”).


Linked Lists:


Write code to remove duplicates from an unsorted linked list. FOLLOW
UP How would you solve this problem if a temporary buffer is not
allowed?


Implement an algorithm to find the nth to last element of a singly
linked list.



Given a circular linked list, implement an algorithm which returns
node at the beginning of the loop.

DEFINITION Circular linked list: A (corrupt) linked list in which a
node’s next pointer points to an earlier node, so as to make a loop in
the linked list.

EXAMPLE input: A -> B -> C -> D -> E -> C [the same C as earlier]
output: C