辅导CSE101留学生、讲解C/C++、C/C++程序语言调试、讲解data structures
讲解Database|讲解R语言编程
CSE101 Stack Recursion Test Questions:
Eschew self-reference
c C. Seshadhri, 2020
• All code must be written in C/C++.
• Please be careful about using built-in libraries or data structures. The
instructions will tell you what is acceptable, and what is not. If you have any
doubts, please ask the instructors or TAs.
1 Setting
You already have recursive and stack-based code that prints all subsequences of
an input string.
The I/O format has been fixed. The input and output files are given as
command line arguments. The first line of the input file is read into a string.
This is processed by a function to produce a list of strings as output. This list
is sorted and then printed to a file. This is exactly the setting you will see in
your test.
For the stack section test, you will have to implement one of the following
functions. Pay attention to the declaration. You cannot use recursion to
implement these functions. You must use a stack based implementation.
1.1 The test questions
There are three functions that you need to study for the test. For your test, you
will be given one of these to code up. In all cases, you can assume that input is
purely alphanumeric and that the argument k ≥ 0.
• List allAnagrams(string input). An anagram of a string is just a
permutation of the string. You must write a function that produces all anagrams
of the input string in a list. The order does not matter. For example, if the
input string was “abc”, the function should output a list containing the following
strings: abc, acb, bac, bca, cab, cba.
• List language(string input, int k). You will see a lot about languages
when you study Computational Models. Just think of the input string
as a set of characters Σ (formally called an alphabet). The language generated
by Σ is the set of all strings comprising of characters (symbols) in Σ. This
1
function generates a list of all strings in the language, whose length is at most
k. Note that empty string is also part of the language. The order of the list
does not matter. For example, if the input is “abc” and k = 2, then the output
list has the following strings: (the empty string), a, b, c, aa, bb, cc, ab, ac, ba,
bc, ca, cb. You can assume that input does not have repeated characters.
• List stretch(string input, int k). A stretch of the input string is
generated by repeating each character in order up to k times (and at least once).
For input string “abc” and k = 2, the output list should have: abc, aabc, abbc,
abcc, aabbc, aabcc, abbcc, aabbcc. (Again, the order does not matter.)
1.2 How it works
You will get a stackrecursion.cpp file with the right function declaration, and
an identical setup to what you have in this box. Your job is to simply code up
the function (that you will only get one as a test question).
You will also get a small test input and test output. To make life easier, I
will actually give you access to my grading scripts (that you can run directly
through a shell script). If it catches a bug in your code, it will give you a test
input where your code file. So you will get to see your score before you submit.
The test is completely closed book. You cannot bring any written material,
but you can get one blank sheet of scratch paper. You will get and can only
open the specific Codio box for the test. You cannot refer to any other codes,
or even open any other Codio box. If you do so, it will be considered cheating
and you will get -10 points.
1.3 What should you do
Start by writing recursive code for these function. You should be able to do
so within 20 lines of code (probably less). Then, convert this recursive code
into code that uses a stack. The stack will store objects corresponding to each
recursive call. Note that you may want to construct some extra objects (like
the Pair used in the current code), though it is possible to avoid that. (Instead
of creating a stack of Pairs, I could have used a stack of strings. Each push/pop
should actually be two pushes/pops, to get both the in str and the fixed str.
Think about it.)
This test uses a bit more C++. Firstly, you need to manipulate the strings.
If you find that painful, you can copy it into a character array, and then process
this array. (You can see the function that does this in my listwrapper code, just
before calling strtok.) Also, you can use the inbuilt C++ stack, so you need to
see how to create a stack of any desired object. This is called templating. This
is nothing too fancy, you simply specify the type in the stack definition. Look
at my code to understand, and play around with it.
2
1.4 Other questions
A few other questions, that might be good practice. (And great interview
practice.)
• For each of the functions, can you write the formula for the size of the
output (or the length of the output list)?
• Can you change the order of the stack pushes? If you do, what happens?
• Suppose you wanted to store the anagrams in lexicographic order directly.
How would you do that?
• Can you use a queue instead of a stack? (In some cases you might luck
out and get the right output, but it is not a faithful simulation of recursion.)
• If you really wanted more coding practice, you could write your own stack.
Actually, you can just modify the existing list code to simulate your stack. As
we discussed in class, the insert is already like a push.
3