数据结构英文试题

杭州电子工业学院学生考试卷（A）卷

1.(8分) Imagine we have two empty stacks of integers, s1 and s

2. draw a picture of each stack after the following operations:

PushStack (s1, 3);

PushStack (s1, -5);

PushStack (s1, 7);

PushStack (s1, -9);

PushStack (s1, 11);

PushStack (s1, -13);

while (not emptyStack (s1)) {

popStack (s1, x);

if (x < 0) {

pushStack (s2, x);

}

} //while

2. (8分)Using manual transformation, change the following postfix or prefix expressions to infix form.

a. ABC+*D-

b. -*A+BCD

3. (8分) what would be the contents of queue Q1 after the following code is executed and the following data are entered?

Q1 = CreateQueue

S1 = CreateStack

loop (not end of file)

read number

if (number not 0)

pushStack (S1, number)

else

popStack (S1, x)

popStack (S1, x)

loop (not emptyStack (S1))

popStack (S1, x)

enqueue (Q1, x)

end loop

end if

end loop

The data are 5, 7, 12, 4, 0, 4, 6, 8, 67, 34, 23 , 5, 0, 44, 33, 22, 6, 0.

4. (8分) Create a AVL tree using the following data entered as a sequential set :

7, 10, 14, 23, 33, 56, 66, 70, 80, 90.

5. (8分)Show the resulting heap after 33, 22, and 8 are added to the following heap :

50, 30, 40, 20, 10, 25, 35, 10, 5.

6. (8分) After two passes of a sorting algorithm, the follow array :

48, 5, 29, 36, 7, 61, 88

has been rearranged as shown below :

5, 7, 48, 29, 36, 61, 88

which sorting algorithm is being used (straight selection, bubble, straight insertion) ? Defend your answer.

7.(8分)A graph can be used to show relationships, for example, from the following list of people belonging to the same club (vertices) and their friendships (edges). People = {George, Jim, Jean, Frank, Fred, John, Susan} FriendShip = {(George, Jean), (Frank, Fred), (George, John), (Jim, Fred), (Jim, Frank),

(Jim, Susan), (Susan, Frank) }

Give the adjacency list representation of this graph.

Algorithm Design

1.(11分)Write an algorithm that traverses a linked list and deletes all nodes whose keys are negative.

2.(11分)Write an algorithm that counts the number of leaves in a binary tree.

3.(11分)Write an algorithm called QueueToStack that creates a stack from a queue. At the end of the algorithm, the queue should be unchanged; the front of the queue should be the top of the stack; and the rear of the queue should be the base of the stack.

4. (11分) Develop a non-recursive BST (Binary Search Tree) search algorithm SearchBST.