Somereviewquestions

  1. Giventhe graph below, perform abreadth-firstsearch startingat vertex A. What doesthebreadth-firstspanning treelooklike?
  1. What isthedegreeofvertex Ainthisgraph?
  1. Whoaretheneighbours ofvertex Ainthisgraph?
  1. Arethevertices Band Eadjacentinthegraph?
  1. Givetheadjacency matrix representationofthegraph.
  1. Drawanadjacency listrepresentationofthegraph .
  1. Howmuch time doesittake tocheckifedge(u,v)isinthe graph ifyouuseanadjacency matrix representation?Ifyouuseanadjacency listrepresentation?
  1. What isanother nameforaconnected, acyclicgraph?
  1. Howmanyedgesdoesaconnected, acyclicgraph haveifithasnvertices?
  1. What isthe largest number ofedgesadirected graph canhaveifithasnvertices, noself- loopsandnoduplicate edges? What ifthegraph isundirected?
  1. Apply Kruskal’sand Prim’s algorithms to graph below
  1. Both Prim’s and Kruskal’s algorthms can be used to build a minimum cost spanning tree T. 0neofthese algorithms adds edgessuchthat Tisconnected at alltimes. Whichone?
  1. What isthedifferencebetweenabinary treeandabinary searchtree?
  2. Givesomepseudocode forthe recursive algorithms that perform the followingtraversalsofabinary tree

•pre-order traversal.

•in-order traversal.

•post-order traversal.

  1. Youperformapre-order traversalofabinary treeanditprints thefollowingvalues

AHCPKT.

What value wasat the root ofthe tree? Ifthe root has aleftchild, what value isstored there?

  1. Youperformanin-order traversalofabinary treewithrootR. Thevaluesprintedoutare

DKLCRTS.

What valuesareintheleftsubtree ofRandwhat valuesareintherightsubtree?

  1. When performing asearchforakeyx,youfirstcompare xagainst r,thenmovetotheleft subtree tocontinue yoursearch. The next comparison isbetween xand £,after whichyou movetotherightsubtree of£. What doyouknowabout therelation betweenthevaluesx, rand£?
  1. Thebinary treebelowcontained somevalueswhichweprintedoutusingapost-order traver- sal. The outputwas.JH DE QWP X. Wethen erased the values fromthe tree. Put them back.
  1. What isthemaximum height(depth)ofatreewithnnodes?
  2. What istheminimum height(depth)ofatreewithnnodes?
  3. What isa(binary max) heap? What areitsproperties?
  4. Canaheapcontain twokeyswiththesamevalue? Canabinarysearchtreecontain twokeys withthesamevalue?
  1. What isthe big0hrunning time forfindingthe third largest element ina(binary max) heap?
  1. What isthebig0hrunning timeforfindingthesmallest elementina(binary max)heap?
  1. Startingwith thebinary search tree below,showwhat the tree lookslikeafter performing

insert1,insert5,insert10,insert8,insTereret 4

5

29

7

  1. Performing asearch forthe number 1999inabinary search tree, youpasskeysnumbered 2400,6,1964,2300,2217.Atthispointisitpossibleforyoutoencounter thenumber 1700 intheremainder ofyoursearch?
  1. Howdoyoudeleteanodewithtwochildren fromabinary searchtree?
  1. Howdoyoufindthesmallest elementstored inabinary searchtree?
  1. What istheworst-case running timeofasearchinabinary searchtree?
  1. What isabalanced tree?
  1. What properties doAVLtreeshave?
  1. What istheworst-case running timeofasearchinanAVLtree?
  1. HowdoyouperformanLLrotationinanAVLtree? Whenissucharotationappropriate?
  1. Repeat question 71fortheRR,LR,andRLrotations
  1. When youinsert akeyxintoanAVLtree, and thiscausesthetreetobecomeunbalanced, onwhichnodedoyouperformarotation?
  1. For the hash function h(k) =k mod 53,what isthe range ofhash addresses that keyscanbesentto?
  1. What dowecallitwhentwonon-identicalkeysaresenttothesamehashaddress?
  1. Give two methods for resolving collisions in a hash table and state the advantagesand disadvantagesofboth.
  1. Therunning timeofasearchinahashtable ismostlydependentonwhat measure?
  1. Define greedy algorithm, dynamic programming, backtracking and clustering.