cmsc230 Midterm Review

Spring 2001

1. In the sortedList data structure what happens when inserting if the key value equals one of the values already in the linked list? (refer to code)

a. key is inserted before current link

b. key is inserted after current link

c. key is not inserted

d. key is not inserted but the frequency is incremented.

2. Write the code that would accomplish the following:

3. An object containing a reference to items in some data structure and used to traverse the data structure is called

a. link

b. linked list

c. iterator

d. current

4. If object A is an instance of a linked list class, it is impossible for object A to create another object which references object A. T/F

5. In writing a deleteCurrent() method for an iterator class, where should the iterator end up pointing?

a. at the end of the list

b. at the beginning of the list

c. at the previous link

d. at the next item

6. Write a method that returns the number of nodes in a linked list. Include a header and any local declarations that may be needed.

7. What class is the best choice to include the above method?

a. link

b. linklist

c. linklistclient

d. linkiterator

8. Write the statement(s) that deletes the first node in a linked list.

9. What operation(s) with complexity O(1) does a double-ended list allow that an ordinary singly linked list does not.

a. insertion after

b. insertion before

c. deletion of a key value

d. insertion or deletion at either end

10. A linked list does not have subscripts which can be used to access data in specific locations in the list. T/F

11. To determine if you are at the end of a linked list test whether the 'next' data member equals nElems. T/F

12. atEnd() is a method that returns true when the end of a list has been reached. atEnd() has 2 references to links, called 'previous' and 'current'. Explain two ways this can be done. (use English, Java, or pseudocode)

13. What is the complexity of deletion of an arbitrary item from a sorted linked list?

a. O(1) b. O(n) c. O(n²) d. O(log n)

14. What is the complexity of deletion of an arbitrary item from an unsorted linked list?

a. O(1) b. O(n) c. O(n²) d. O(log n)

15. What is the complexity of deletion of an arbitrary item from a sorted doubly linked list?

a. O(1) b. O(n) c. O(n²) d. O(log n)

16. What is the complexity of deletion of an arbitrary item from an unsorted doubly linked list?

a. O(1) b. O(n) c. O(n²) d. O(log n)

17. Which is true of a listInsertionSort

a. It is no more efficient than the insertion sort of an array.

b. It has the same complexity as the insertion sort of an array but fewer copies.

c. It has the same complexity as the insertion sort of an array but more copies.

d. It has complexity O(2n) instead of O(n²)

18. Write a brief algorithm for a list insertion sort using English.

19. The ADT priority queue can NOT be implemented by

a. a linked list

b. an array

c. a stack

d. a doubly linked list

20. Which of the following are NOT true?

a. insertFirst() and deleteFirst() are both done at the beginning of a linked list.

b. deletion of an arbitrary item in an array is O(1)

c. deletion of an arbitrary item in a linked list is O(n) but faster than deletion in

an array because no moves or shifts are needed

d. once a key value has been found in a linked list insertionAfter() is O(1)

21. Which of the following is NOT true?

a. A link, or node is an object of a class.

b. A link class is different from a linked list class.

c. A link object really contains another link object.

d. The 'next' field of a link contains the address in computer memory of an object

22. Which of the following is NOT true?

a. A reference contains a number or address.

b. All references are the same size.

c. The previously defined identifier 'this' refers to the current object.

d. The size of a 'next' field depends on the size of the object it references.

23. A class with a data field of the same type as itself is

a. self-referential b. circular d. doubly linked e. invalid in Java

24. Dynamic memory allocation occurs

a. at compilation time.

b. when the previously defined 'insert' operation is executed.

c. during execution of the program.

d. when a reference is declared such as: link next.

25. Memory in a linked list that has been allocated dynamically

b. can always be accessed by name.

c. can not have more than 2 data members

d. can be a primitive.

26. A queue

a. not an abstract data type.

b. can be implemented by a linked list but not by an array.

c. requires methods that enforce Last In First Out.

d. permits removal from the front only.

27. A stack

a. is a data structure.

b. can be implemented by a linked list but not by an array.

c. requires methods that enforce Last In First Out.

d. permits insertion at either end.

28. Most microprocessors use ___________based architecture for example in the

handling of methods.

a. queue b. postfix c. stack d. array

29. The acronym that expresses the processing rule for a stack is:

a. LIFO b. FOFI c. LOFI d. FIFO

30. The acronym that expresses the processing rule for a queue is:

a. LIFO b. FOFI c. LOFI d. FIFO

31. An array implementation of a queue requires initializing

a. rear = 0 front = 1

b. rear = -1 front = 0

c. rear = 0 front = 0

d. rear = -1 front = -1

32. To insert into a queue

a. rear++ front++

b. rear-- front--

c. front++

d. rear++

33. To remove from a queue

a. rear--

b. front--

c. rear++

d. front++

34. When quick access to values with highest priority is important use a

a. stack

b. queue

c. priority queue

d. array implementation of a queue

35. Priority queue methods are the same as those of a queue except

a. initializing b. deleting c. inserting d. sorting

36. The complexity of inserting an item into a priority queue is

a. O(1) b. O(n) c. O(n²) d. O(log n)

37. The complexity of removing an item from a priority queue is

a. O(1) b. O(n) c. O(n²) d. O(log n)

38. A priority queue permits removal of

a. the item of highest priority whether it is the largest or smallest.

b. the first item stored in the queue only.

c. the last item stored in the queue only.

d. any arbitrary key value.

39. Convert to postfix: a + (b - c) / d

40. Convert to prefix: a + (b - c) / d

41. If (a ==1 && b == 2 && c == 3 && d == 4) is true, what is the value of acdb/*- ?

42. Convert this postfix expression to infix with no more parentheses than necessary:

ab-c/d+

43. A computer program must be written which, when used by the user, will be called on

to insert new data very frequently. Based on that need, which data structure

would be most efficient?

a. ordered array or linked list

b. unordered array or linked list

c. ordered array or priority queue

d. unordered array or priority queue

44. A computer program must be written which, when used by the user, will be called on

to search for data very frequently. Based on that need, which data structure

would be most efficient?

a. ordered array

b. unordered array

c. linked list

d. queue

45. Write a binary search. (use Java, pseudocode, or an algorithm in English)

46. Write a linear search. (use Java, pseudocode, or an algorithm in English)

47. Write a bubble sort. (use Java, pseudocode, or an algorithm in English)

48. Write a selection sort. (use Java, pseudocode, or an algorithm in English)

49. Write an insertion sort. (use Java, pseudocode, or an algorithm in English)

50. Which of the following is not a built-in method of the class String?

a. subString(x,y) b. charAt(x) c. readLine() d. length()

51. Classes that are declared __________ are available to any other class in the

same folder.

a. private b. public c. static d. extends

52. Methods that are declared __________ are available to any other class in the

same folder without instantiation of an object of the class to which they belong.

a. private b. public c. static d. extends

53. Write a statement that will copy the first 5 items of array ray1 to the last 5 cells

of ray2.

Refer to the following code segment to answer numbers 54, 55 & 56.

class file2ArrayStr{

String word;

strArray myArray = new strArray(5000);

.

.

.

public void readFile(String filename) throws IOException

{

try{

FileInputStream fs = new FileInputStream(filename);

while (true){

word = getWord(fs);

if (word.equals("eof"))

break;

else

if (word.length()!=0)

myArray.insert(word);

}//end while

fs.close();}//end try

catch{

.

.

.

54. To view the source code of the method insert() look into class

a. FileInputStream b. strArray c. file2ArrayStr d. String

55. To view the source code of the method getWord(fs) look into class

a. FileInputStream b. strArray c. file2ArrayStr d. String

56. To view the source code of the method close() look into class

a. FileInputStream b. strArray c. file2ArrayStr d. String

Refer to the following code segment to answer questions 57 & 58

public static String getString() throws IOException{

String s;

InputStreamReader isr = new InputStreamReader(system.in);

BufferedReader br = new BufferedReader(isr);

s = br.readLine();

return s;}

57. To view code of the readLine() method look in the _______class.

a. InputStreamReader b. BufferedReader c. String d. StringArray

58. The 'throws IOException' used here will generate an error because there is no

'try/catch' clause. T/F

59. This method along with other code must be used to read numeric data from the

keyboard because all data from the keyboard is first read as a string in Java. T/F

60. This method includes what is called 'wrapping'. T/F

Review 'gottagoslo' push/pop/insert/remove exercise.

Answers:

1.a 2. temp.next = current.next; current = temp; 3. c 4. F 5. d

6. int count(linklist l){

int ct = 0;

link temp = l.first;

while (temp != null)

ct++;

return ct; }

7. d 8. first = first.next 9. d. 10. T 11. F

12 current = the last node in the list (current.next == null is true)

or previous == last & current == null is true

13. b 14. b 15. b 16.b 17. b

18. step 1: insert items from array into ll in order

step 2: remove items from list and replace in array

19. c 20. b 21. c 22. d 23. a 24. c 25. a 26. d 27. c 28. c 29. a 30. d

31. b 32. d 33. d 34. c 35. c 36. b 37. a 38. a 39. abc-d/+ 40.+a/-bcd

41. -5 42. (a-b)/c+d 43. b 44. a 45-49 see text/notes

50. c 51. b 52. c 53. System.arrayCopy(ray1,0,ray2,ray2.length-5,5)

54. b 55. c 56. a 57. b 58. F 59. T 60 T