CS3304 (Data and Information Structures)

  1. Write a method to print a (singly) linked list of integers in reverse order using a stack. (Pseudocode, assuming that a stack class is already defined for you) (10 points)

2. Assume that a queue is implemented using a SinglyLinkedList (with head and tail references). Write a method in Pseudocode to delete an element from the queue.(10 points)

3. Using the following linked list data structure(15 points):

typedef struct n { int data; struct n *next; } Node;

typedef Node *List;

write a C function, void cut(List *, int, int) that removes a section of a list. The first argument is a pointer to the list pointer, the second argument is the position of the first element to be removed (0 denotes the first element, 1 the second element, and so on), and the third argument is the number of elements to be removed. The function should behave the same as the following Miranda function:

> cut :: [num] -> num -> num -> [num]

> cut list start count

= [] , if list = []

= (hd list) : cut (tl list) (start-1) count, if start > 0

= cut (tl list) start (count-1) , if count > 0

= list , otherwise

Here are some examples, using Miranda list notation, to show how cut works:

/* L == [1,2,3,4,5,6,7,8] */ cut(&L, 0, 2); /* L == [3,4,5,6,7,8] */

/* L == [1,2,3,4,5,6,7,8] */ cut(&L, 1, 3); /* L == [1,5,6,7,8] */

/* L == [1,2,3,4,5,6,7,8] */ cut(&L, 2, 8); /* L == [1,2] */

/* L == [1,2,3,4,5,6,7,8] */ cut(&L, 5, 0); /* L == [1,2,3,4,5,6,7,8] */

/* L == [1,2,3,4,5,6,7,8] */ cut(&L, 0, 9); /* L == [] */

4. Compose a method in Pseudocode to store strings from a text file into a binary search tree(7 points), and a method in Pseudocode to store a binary search tree into a text file(7 points).

5.For each tree given below, choose all the descriptions that apply from the list below: (4 points each, total 16 points)

  1. binary tree
  2. binary search tree
  3. AVL tree
  4. complete binary tree
  5. heap

(a) 10 (b) 10 (c) 6 (d) 5

/ \ / \ / \ / \

20 30 5 11 2 10 6 7

\ / \ / \ /

22 1 12 1 3 8

7. (1) Show what the following AVL tree looks like after inserting 12. (3 points)

10

/ \

5 30

/ / \

3 20 35

/ \

15 21

(2) Show the preorder numbering for the tree in (1).(3 points)

8. Assume you have a hash table with 10 locations. Assume the hash function is: hash(n) = (n+1) % 10
For the questions below, assume you insert the following keys into an empty table in the following order: 13 104 88 99 89 93 22 27

  1. Use linear probing to resolve the collisions. Show what the table looks like after inserting all the items. (4 points)
  2. Use chaining and show what the table looks like after inserting all the items. (4 points)

9.For this question you will be writing code to swap two nodes in a doubly-linked list. (10 points)

Assume you have a doubly-linked list containing integer keys. Here is the structure definition:

struct node {

int key;

struct node *next, *prev;

};

typedef struct node listnode;

You need to write the function swap which takes a pointer to the first node in the list and an integer as input. Assume the first node is a sentinel node. Your function will find the node with the given key and then swap that node with the node following it. Do not just swap the keys. I want you to actually swap the nodes themselves.
For example, if the list looks like: sentinel->1->2->3->4->5->NULL (not showing prev pointers) and you call swap(first, 4), then afterwards the list should look like: sentinel->1->2->3->5->4->NULL. Here is the prototype for the swap function: void swap(listnode *first, int swapkey)

10.

  1. Define "heap". (3 points)
  2. Write pseudo code to implement "insert" in a heap. (5 points)
  3. Write C code declaring the data structure for a heap containing integer keys. You may assume that the heap will have at most 100 items in it.(3 points)