Description of this paper

computer science data questions

Description

solution


Question

2. The table following shows a dynamic implementation of a list of characters. Some of;the locations contain a letter, and each is followed by a location that holds a pointer to;the next letter in the list.;Notice that a pointer points to a character. For example, assume there is a pointer;called list pointing to the first character in the list. Say list has the value 62;then the first character is E.;0 is used for the NULL pointer.;What are the characters in the list in the correct order?;Address ---Contents;52------------- V;53 -------------0;54------------- M;55 -------------58;56 -------------T;57 -------------54;58------------- S;59 -------------52;60 -------------W;61 -------------56;62 -------------E;63 -------------60;list is: ____E;3. The table following shows a dynamic implementation of a list. The pointer to the;first item in the list has value 40.;What is the list?;Address--- Contents;32 -------------I;33 -------------38;34 -------------P;35 -------------0;36 -------------S;37 -------------34;38 -------------S;39 -------------42;40 -------------Q;41 -------------32;42 -------------C;43 -------------36;list is;4. The table following shows the contents of main memory. Put addresses into the;empty pointer fields to build a list of the characters in alphabetical order. Use 0 for;the NULL pointer.;If a pointer called list is to point to the first letter in the list, what would be the;value of list?;Address --Contents;40 -------------N;41;42------------- U;43;44 -------------B;45;46 -------------J;47;48 -------------W;49;50 -------------F;51;value of list;5. Unlike static implementations, deleting items from dynamic data structures is;extremely efficient.;Given that the list below is to remain in alphabetical order, alter whichever pointers;are necessary to delete T. (The list begins with C.);Address ---Contents;14------------- Y;15------------- 0;16 -------------I;17 -------------20;18 -------------T;19------------- 14;20 -------------K;21 -------------18;22 -------------F;23 -------------16;24 -------------C;25 -------------22;6. Inserting a new item is similarly efficient.;Below is the previous list. First cross-out the letter T in the table and write-in the;letter H. Now update whatever pointers are necessary to insert H into the list;maintaining the list in alphabetical order. The list begins with C.;Address --Contents;14 -------------Y;15 -------------0;16 -------------I;17 -------------20;18 -------------T;19 -------------14;20 -------------K;21 -------------18;22------------- F;23 -------------16;24 -------------C;25 -------------22;7. Which of the following pseudocode algorithms correctly inserts a record called;new_record immediately after the record called current_record in a linked;list?;(HINT: to help you solve the problem, draw a picture of a linked list with 3 items;where current_record is the middle item. Draw new_record outside the list;then follow the steps of each algorithm to see how the list is changed.);Algorithm #1;1. set the pointer field of current_record to point to new_record;2. set the pointer field of new_record to point to the record pointed to by;current_record;Algorithm #2;1. set the pointer field of new_record to point to the record pointed to by;current_record;2. set the pointer field of current_record to point to new_record;correct algorithm is;briefly, what is wrong with the other algorithm?;8. A record in a dynamic data structure can contain more than one pointer field. Given;the table following, fill-in the first location after each letter to build a list of the letters;in alphabetical order. Set the second location after each letter so that the letters are;found in reverse alphabetical order. Make sure that each list ends correctly, using 0;for the NULL pointer.;If the pointer alpha points to the start of the list in alphabetical order and reverse;points to the start of the reverse order list, what are the values of these two pointers?;Address ---Contents;30 -------------Y;31;32;33 -------------C;34;35;36------------- A;37;38;39------------- G;40;41;42 -------------W;43;44;value of alpha is;value of reverse is;9. Each node in a binary tree can be stored using 3 memory locations. The first holds;the key value of the node (a letter here), the second contains a pointer to the node's;left child and the third contains a pointer to the right child. Using this representation;method, fill-in the pointer fields so that the table represents the tree given below.;What should the value of the root pointer be?;Address ---Contents;30 -------------T;31;32;33 -------------Z;34;35;36 -------------S;37;38;39------------- I;40;41;42 -------------R;43;44;45 -------------K;46;47;R;/ \;k t;/ / \;i s z;Value of root pointer is

 

Paper#73292 | Written in 18-Jul-2015

Price : $22
SiteLock