數(shù)據(jù)結(jié)構(gòu)與算法分析期末試題

2011年～2012年第一學(xué) 數(shù)據(jù)結(jié)構(gòu)與算法分 期末試卷〖A卷★考試時間共120分鐘題123456789總得閱卷得閱卷（得閱卷Pleasetranslatethefollowingtermsintoalgorithmefficiencyysis; datatype;linkedlist;LIFO;template;pseudocode;enqueue;inordertraversal;amortizedysis;diminishingincrementsort.得閱卷（得閱卷Pleasetranslatethefollowingtermsinto得閱卷（得閱卷TrueorFalseQuestions(Circlethecorrect 1.Iff(n)isapolynomialofdegreek,thenf(n)=(nk) 2.Letf(n)=nlognandg(n)=n1.5.Thenthefunctionf(n)growsfasterthan 3.AnO(n2)algorithmc waysbeslowerthananO(n3)algorithmiftheconstantislarge 4.Inaninordertraversal,theworkatanodeisdoneafteritschildrenare 5.Intheworstcase,theheightofthebinarysearchtreescanbelinearinthenumberofnodesinthetree.得閱卷（得閱卷Describeinformallyasmany(atleasttwo)algorithmsaspossibletosolvetheSelectionProblem:Findthekth-largestnumberfromagroupofnnumbers.得閱卷（得閱卷WhythefollowingprogramisterriblyinefficientforcomputingFibonaccilongfib(intn{if(n<=1)return1;returnfib(n–1)+fib(n–2}得閱卷（得閱卷Describethefollowingoperationsofastack.push_back,pop_back.得閱卷（得閱卷ForthefollowingwhichnodeistheWhichnodesaretheWhichnodeistheparentofListthechildrenofComputethedepthandheightof得閱卷（得閱卷Converta+b*c+(d*e+f)*gintopostfix得閱卷（得閱卷WriteoutthedefinitionofAVLtree.Showtheresultofinserting2,1,4,5,9,3,6,7intoaninitiallyemptyAVL得閱卷（得閱卷Shownbelowisthecodeforsometemplate<typenameconstComparable&???(vector<Comparable>&a,intleft,intright{intcenter=(left+right)/2;if(a[center]<a[left])swap(a[left],a[center]if(a[right]<a[left])swap(a[left],a[right]);if(a[right]<a[center])swap(a[center],a[right]);swap(a[center],a[right-1]);returna[right