代写CSE101留学生、代做C/C++、C/C++程序语言调试、代做data structures

日期：2020-02-07 10:10

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