ParsX.com
سايت دانشجويان رشته كامپيوتر و راهنماي كنكور كارشناسي ارشد و كارداني به كارشناسي (كارشناسي ناپيوسته )
 
   ProfileProfile   Log in to check your private messagesLog in to check your private messages  |  FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups Log inLog in   RegisterRegister 

چند تست ساختمان داده

 
Post new topic   Reply to topic    ParsX.com Forum Index -> اصول ساختمان داده ها
View previous topic :: View next topic  
Author Message
parnia_mb
مهمون يكي دو روزه


Joined: 10 Dec 2007
Posts: 7
PostPosted: Sat Jan 26, 2008 1:04 pm    Post subject: چند تست ساختمان داده Reply with quote
میشه یکی اینا رو برا من حل کنه؟


1-اگر عناصر یک درخت جستجوی باینری را به صورت inorder پیمایش کنیم و در داخل یک استک قرار دهیم و سپس عناصر استک را خارج کنیم و یک درخت جستجوی باینری بسازیم درخت حاصل چه درختی خواهد بود؟
1)درخت باینری تغییر نمی کند 2)درخت باینری مورب به چپ
3)درخت باینری مورب به راست 4)زیر درختهای چپ و راست درخت باینری عوض می شود

جواب اینو زده گزینه 2. در حالیکه من فک میکنم جواب گرینه 3 هست. میشه خواهش کنم بگید چرا گفته گزینه 2 درسته؟؟


2-اگر بخواهیم دو min heap به تعداد m و n را با هم merge کنیم پیچیدگی زمانی آن برابر است با :
1) m log mn 2) mlogn + nlogm 3) nlogn . logm 4) m.logn.logm
جواب گزینه 1 است. چرا؟

3-در یک درخت باینری T با n گره در چه حالتی اولین گره در پیمایش postorder مشابه آخرین گره در پیمایش inorder است؟
1)زیر درخت چپ T خالی باشد 2) دارای ارتفاع n-1 باشد
3) زیر درخت راست T خالی باشد 4)T حداکثر 3 گره داشته باشد

جواب گزینه 2 است . تو این سوال می خوام بدونم که آیا درختی با ارتفاع n-1 به غیر از درختهای مورب چپ و راست دیگه درختی هست؟ اگه اینجوری باشه که جواب نمی تونه گزینه 2 باشه . درخت مورب چپ رو امتحان کنید . پس چرا گفته 2 ؟؟؟؟؟
Back to top
vahid
بي تو هرگز


Joined: 26 Nov 2004
Posts: 2704
Location: Tehran
PostPosted: Sun Jan 27, 2008 9:15 pm    Post subject: Reply with quote
جوابش رو تا كي مي خواي ؟
اين جوابها رو از كجا پيدا كردي ؟
Back to top
parnia_mb
مهمون يكي دو روزه


Joined: 10 Dec 2007
Posts: 7
PostPosted: Mon Jan 28, 2008 10:56 am    Post subject: Reply with quote
جوابش رو تا قبل از کنکور ارشد می خوام یعنی اول اسفند.
اینا هم سوالای ارشد علوم کامپیوتر پارساله . با پاسخنامه سازمان سنجش.
Back to top
Saeid_yousefpour
مهمون يكي دو روزه


Joined: 09 Sep 2009
Posts: 1
Location: Tabriz
PostPosted: Wed Sep 09, 2009 11:17 pm    Post subject: Reply with quote
سلام
جواب سوال اول:
بله گزینه 2 درست است. دلیلش اینه که
- اگر شما یک درخت جستجوی دودویی رو به صورت inorder پیمایش کنید یعنی داده ها را بصورت مرتب شده صعودی به خروجی می برید. پس در مسئله شما داده ها به صورت صعودی وارد پشته می شوند. در نهایت شما بزرگترین عدد را در بالای پشته دارید و کوچکترین عدد را هم در پایین پشته. حال می خواهیم از پشته یکی یکی pop کرده و یک درخت دیگر بسازیم. با توجه به عناصر داخل گشته بزرگترین عنصر در ابتدا pop می شود و اولین گره درخت را ایجاد میکند. بعد از آن دومین عنصر حذف می شود و دومین گره درخت ساخته می شود. اما چون دومین عنصر از اولین عنصر کوچکتر است پس در درخت به زیر درخت سمت چپ اضافه می شود و عناصر به همین ترتیب از پشته حذف شده و در درخت اضافه می شود. بنابر این ما در نهایت یک درخت دودویی مورب چپ را خواهیم داشت. چون هر گره جدید که اضافه می شود از همه گره های قبلی کوچکتر خواهد بود.
خودتون هم می توانید با رسم یک شکا درخت و پشته قضیه را به خوبی متوجه شوید.

اگر سوال دیگری داشتید حتما مطرح کنید
Back to top
vahid
بي تو هرگز


Joined: 26 Nov 2004
Posts: 2704
Location: Tehran
PostPosted: Sat Sep 12, 2009 8:52 am    Post subject: Reply with quote
تشکر آقا سعید
Back to top
Display posts from previous:   
Post new topic   Reply to topic    ParsX.com Forum Index -> اصول ساختمان داده ها All times are GMT + 3.5 Hours
Page 1 of 1

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum


s Powered by phpBB © 2001, 2007 phpBB Group