نمونه سوالات ساختمان داه استاد شمس الدینی

- فرض کنید برای نگهداری یک سری عدد صحیح از یک صف حلقوی queue[100] استفاده نموده ایم بطوریکه queue[0] ، حاوی مقدار queue[1] , front حاوی مقدار near ( انتهای صف ) بکار میرود و queue[2] تا queue[q a] برای نمایش عناصر صف حلقوی بكار می روند. توابع ایجاد ، اضافه کردن مقداری به صف حلقوی و حذف مقداری از آن را بجای این مورد بنویسید .
4- الف ) حداکثر تعداد عناصر صفر یک ماتریس سه قطری چند است ؟ب) آرایه سه بعدی A[4][6][7] مفروض است . اگر آدرس شروع این آرایه a باشد آدرس شروع عنصر A[3][1][4] را محاسبه کنید .
5- از یک آرایه یک بعدی با طول n می توان برای پیاده سازی دو پشته استفاده نمود به طوری که عناصر پشته اول با شروع از ابتدای آرایه و عناصر پشته دوم با شروع از انتهای آرایه در آن قرار گیرند . توابع مربوط به ایجاد پشته خالی ، حذف عنصری از پشته و افزودن عنصری به پشته را برای هر یک از دو پشته بنویسید .
6- الف ) توضیح دهید که چرا در پیاده سازی صف حلقوی با آرایه ، یک خانه از صف باید خالی بماند . ب) توابع مربوط به افزودن عنصری به صف حلقوی و حذف عنصری از آن را بنویسید .
7- یک ماتریس 15*10 که هر یک از عناصر آن ، شش بایتی هستند را در نظر بگیرید . تعداد عناصر غیر صفر این ماتریس چقدر میتواند باشد که نگهداری آن به شکل ویژه اسپارس ، از لحاظ حافظه به صرفه تر از نگهداری معمولی آن به شکل آرایه دو بعدی باشد ؟ فضای لازم برای ذخیره شماره سطر و ستونهای عناصر صفر را دو بایت در نظر بگیرید .
8- الف ) حداکثر تعداد عناصر غیر صفر یک ماتریس سه قطری چند است ؟ب ) عناصر غیر صفر یک ماتریس بالا مثلثی محض را به چه ترتیبی می توان در یک ارایه یک بعدی ذخیره نمود ؟ رابطه دستیابی این عناصر را بدست آورید .
9 – عبارت زیر را به شکل میانوندی داده شده است . با ذکر مراحل ، معادل پسوندی آنرا بیابید . سپس عبارت پسوندی را به ازای مقادیر داده شده با ذکر مراحل ، ارزیابی کنید .
Infix = 6+a/b-(3/x*2) +1)/5         a = 2 b=3 x=6
10- كاربرى صف اولویت و انواع آن را توضیح دهید . چگونه می توان صف اولویت را با استفاده از آرایه صعودی پیاده سازی نمود ؟ در هر مورد دستورات لازم برای حذف و اضافه عنصر به صف اولویت به تفکیک نوع آن را ذکر کنید .
11- عبارت میانوندی زیر را با رسم تغییرات پشته به پسوندی تبدیل کنید . سپس با نوشتن تابع ارزیابی ، عبارت پسوندی حاصل را به ازای مقادیر داده شده ارزیابی کنید . -A + (B/C * A-2) ^ K*B A=2              B=6        C=3     K=4
12- أرایه ای به طول m موجود است . می خواهیم n صف ساده را در این آرایه پیاده سازی کنیم دستورات لازم برای ایجاد صف شماره i ، حذف عنصری از صف شماره i و افزودن عنصری به صف شماره i را بنویسید .
13- الف ) تابعی بنویسید که یک ماتریس اسپارس را که به شکل ویژه ذخیره شده است دریافت نموده و ترانها ده آن را بدست آورد . ب) 60 درصد عناصر یک ماتریس 200 * 200 غیر صفر هستند هر عنصر ماتریس ، یک ساختار 15 بایتی است ، توضیح دهید که آیا پیاده سازی این ماتریس به روش ویژه بهتر است یا خیر ؟
14- تابعی بنویسید که دو آرایه مرتب را از ورودی دریافت کند و آنها را طوری ادغام کند که آرایه حاصل نیز مرتب باشد .
15- عبارت میانوندی زیر را با رسم مراحل ، به عبارت پسوندی تبدیل کنید . سپس با ذکر مراحل ، عبارت پسوندی حاصل را به ازای مقادیر داده شده ارزیابی نمایید . Infix = a+b/((c-d)*e)           a= 2 b=3 c=4 d=5 e=6
16- الف ) ماتریس اسپارس روبرو را به شکل ویژه نمایش دهید .ب) ترانهاده آن را بیابید .ج) میزان حافظه لازم برای ذخیره نمودن این ماتریس را در دو حالت ذخیره معمولی و ویژه بدست آورید .
0 4 2 0 0
0 0 0 0 0
6 3 0 0 0
0 0 3 0 5
0 1 0 0 5
0 0 0 0 0

15- مشکلات پیاده سازی صف ساده را با آرایه با یک مثال توضیح دهید . سپس تابع افزودن عنصری به صف حلقوی را بنویسید .
16- ماتریس A ( m * n ) را در نظر بگیرید . اگر عنصری مانند a[i][j] در این ماتریس وجود داشته باشد بگونه ای که مقدار این عنصر ، کمترین مقدار در سطر شماره i و بزرگترین مقدار در ستون شماره j باشد ، گوییم که ماتریس A دارای saddle point است . تابعی بنویسید که یک ماتریس m *n را دریافت کرده و در صورت یافتن saddle point موقعیت آنرا مشخص نماید .
17- توابع مربوط به ایجاد یک صف حلقوی ، افزودن عنصری به صف حلقوی و حذف عنصری از آن را با استفاده از آرایه items [n] بنویسید . رابطه ای برای محاسبه تعداد عناصر موجود در صف حلقوی بدست آورید .
18- فرض کنید آرایه A به طول m موجود است . می خواهیم n پشته را با استفاده از این آرایه نمایش دهیم بگونه ای که سهم هر پشته m/n خانه های پشته باشد . در حالت ساده فرض کنید هر پشته تنها مجاز به حرکت در محدوده مربوط به خود میباشد . فرض کنید آرایه ای به نام top [n] وجود دارد بگونه ای که top [i] ، مشخص کننده اندیس عنصر بالای پشته شماره i است . توابع مربوط به ایجاد پشته i ام ( مقدار دهی اولیه آرایه top ) ، حذف عنصری از پشته i ام و افزودن عنصری به پشته i ام را بنویسید . m–1 ............. 2[m/n]-1 [m/n]-1 0   .............      
19- الف) آرایه سه بعدی A[7][6][4] مفروض است . اگر ادرس شروع حافظه در ذخیره این ارایه a باشد ، عنصر A[3][2][1] در چه آدرسی نسبت به a در حافظه قرار میگیر د ؟ ب) ماتریس قطری n*n مفروض است ( یاداوری : در ماتریس قطری فقط عناصر روی قط اصلی غیر صفر هستند ) برای چه مقادیر n ذخیره سازی این ماتریس به شکل ویژه اسپارس از لحاظ حافظه مقرون به صرفه تر است ؟
20- الف) توابع مربوط به پیاده سازی پشته را با لیست پیوندی ، شامل ایجاد پشته خالی ، افزودن عنصری به بالای پشته و حذف عنصری از بالای پشته را بنویسید ب) تابعی برای افزودن گرهی به یک لیست پیوندی ساده مرتب بنویسید .

درخت:
1.پیاده سازی درخت با استفاده از آرایه را توضیح دهید . روش را برای یک درخت نمونه پیاده کرده و توضیح دهید این روش برای چه درختهایی مناسب است و برای چه درختهایی مناسب نمیباشد .
2- تابعی بنویسید که بزرگترین عنصر موجود در یک درخت جستجوی دودویی (BST) راحذف کند .
3.الف) پیاده سازی درخت با استفاده از آرایه را توضیح دهید . روش را برای یک درخت نمونه پیاده کنید .ب) بطور کامل و با ذکر دلیل توضیح دهید این روش برای چه درختهایی مناسب است و برای چه درختهایی مناسب نمیباشد .
4- تابعی بنویسید که آدرس گره ریشه یک درخت دودویی را دریافت کرده و آن درخت را به یک درخت دودویی نخی سمت راست تبدیل کند . - تابع حذف یک گره از یک درخت جستجوی دودویی (BST) را بنویسید حالتهای بدون فرزندی ، تک فرزندی و دو فرزندی را در نظر بگیرید .
5- حاصل پیمایش RLV (زیر درخت راست ، زیر درخت چپ و سپس زیشه ) درخت دودویی زیر ، چیست ؟
6- تعداد درخت های دودویی متمایزی که با چهار نود می توان رسم نمود چند تا است ، آنها را رسم کنید .
ثابت کنید برای هر درخت دودویی ، رابطه زیر برقرار است : n0 = n2 + 1
n0 : تعداد نود های بدون فرزند     n2 : تعداد نودهای با دو فرزند
 
7- الف ) ثابت کنید تعداد گروه های یک درخت دودویی پر با عمق d برابر است با تعداد گره های غیر برگ این درختها را نیز مشخص کنید . ب) برای عبارت زیر درخت دودویی رسم کنید . سپس با پیمایش درخت ، عبارت پیشوندی و پسوندی آن را مشخص کنید .
((A * (B+C)) / (D-(E+F))) * (G/ (H/I * J)))
8- تابعی برای ساخت یک درخت جستجوی دودویی نخی چپ و راست بنویسید . در این درخت از فیلد right بدون استفاده برای اشاره به گره بعدی که در پیمایش inorder ظاهر میشود و از فیلد leftبدون استفاده برای اشاره به گره قبلی که در پیمایش inorder ظاهر میشود استفاده میشود . در هر گره علاوه بر داده و فیلد, rthread فیلدی مانند lthread نیز در نظر بگیرید تا مشخص کننده نخی بدون یا نبودن فیلد left هر گره باشد.
9- تابع حذف یک گره از درخت جستجوی دودویی را بنویسید .
10-درخت جستجوی دودویی نخی راست حاصل از اعداد زیر را رسم كنید. 27 67 60 43 45 50 25 20 40
11- تابع پیمایش preorder درخت دودویی نخی راست را بنویسید.
12- پیمایش های inorder ، preorder یك درخت داده شده اند. درخت را رسم كنید.
inorder: GFHKDLAWRQPZ
preorder: FGHDKALWPQRZ

لیست:
1- روشهای مختلف پیاده سازی ماتریس اسپارس با لیست پیوندی را برای ماتریس زیر ترسیم نموده ، مزایا و معایب هر یک را توضیح دهید .
0 0 6 0
0 0 2 0
0 0 0 0
0 1 0 0

2- تابعی بنویسید که آدرس شروع یک لیست پیوندی ساده را دریافت کرده و به صورت غیر بازگشتی و تنها با یکبار پیمایش آن ، لیست را معکوس کند .
3- گاهی اوقات برای حذف یک نود از لیست پیوندی به جای آزاد نمودن فضای حافظه آن نود ، آن را به لیستی به نام av اضافه میکنند تا در صورت نیاز مجدد به حافظه از آن استفاده کنند . فرض کنید میخواهیم کلیه نودهای یک لیست حلقوی را حذف کنیم . با بکارگیری روش فوق ، کلیه نودهای این لیست حلقوی باید در لیست av قرار گیرند . تابعی بنویسید که آدرس شروع یک لیست حلقوی و لیست ساده av را دریافت کرده و بدون پیمایش هیچ یک از دو لیست ( بدون حلقه تکرار ) آنها را به هم متصل نماید و آدرس شروع لیست حاصل را بر گردانید .
4- تابعی بنویسید که آدرس شروع یک لیست پیوندی نامرتب را دریافت نموده و لیست جدیدی بسازد که شامل عناصر لیست اولیه بصورت مرتب باشد و این لیست را بر گرداند .
5- ماتریس اسپارس زیر را با کاملترین ساختار لیست پیوندی نمایش دهید.
0 0 2 4 0
0 0 0 0 0
0 0 0 3 6
5 0 0 0 0
5 0 0 1 0
0 0 0 0 0

6- گره راس در لیست پیوندی چه گرهی است و به چه منظور به لیست اضافه می شود ؟ توابع حذف و اضافه گرهی به لیست پیوندی ساده با گره راس را بنویسید . 
7- تابعی بنویسید که آدرس شروع یک لیست دو پیوندی و شماره یک گره را دریافت نموده و گره با آن شماره را از لیست حذف نماید .(گره ها با شروع از شماره یک ، شماره گذاری شده اند ) 
8- دستورات لازم را برای پیاده سازی پشته با لیست پیوندی شامل ایجاد پشته خالی ، افزودن عنصری به پشته و حذف عنصری از پشته را بنویسید .
9- تابعی بنویسید که جملات یک چند جمله ای را از کاربر دریافت كند و پس از تشکیل لیست پیوندی آن ، چند جمله ای را به ازای مقدار ورودی x ارزیابی نماید .
10- الف ) چند جمله ای زیر را با یک استفاده از یک لیست پیوندی ساده با گره راس نمایش دهید . P(x) = 8 x ^ 7 – x ^ 5 + 12 x ^ 4 + 5 x ^ 2 – x + 3ب) تابعی بنویسید که آدرس شروع یک چند جمله ای و عدد k را بعنهوان پارامتر پذیرفته و ضریب x^k را در چند جمله ای برگرداند .
11- تابعی بنویسید که آدرس گرههای راس لیست پیوندی مربوط به دو چند جمله ای اسپارس را دریافت کرده و حاصلضرب آن دو چند جمله ای را در لیست پیوندی سوم ( حاوی گره راس ) قرار دهد ( لیست حاصلضرب باید فاقد جملاتی با توانهای یکسان با شد ) .
12- زیر برنامه ای بنویسید که آدرس شروع یک لیست دو پیوندی و عدد صحیح k را دریافت کند و گرهی با محتویات k را طوری به لیست اضافه کند که ترتیب صعودی عناصر لیست ، حفظ شود . ( لیست دو پیوندی ، صعودی و مرتب است )

گراف:
1- تابعی بنویسید که با توجه به یک ماتریس همجواری و گره j , i از یک گراف ، تعداد مسیر های با طول معین بین آن دو گره را محاسبه کند.
 2- گراف وزن دار زیر مفروض است . کمترین درخت پوشا برای این گراف را بهمراه رسم درخت پوشای مینیمال ( کمینه ) به روش وارشال مشخص کنید . - با شروع از گره A پیمایش عرضی و عمقی برروی گراف انجام داده نتیجه را مشخص کنید .
3- در یک گراف بدون جهت همبند ( connect) به یك یال " پل " گفته میشود اگر با حذف آن از گراف ، گراف غیر همبند شود . برنامه ای بنویسید که یک گراف را دریافت کرده و یالهای پل آنرا مشخص نماید( یادآوری : گرافی همبند است که بین هر دو گره آن ، مسیری وجود داشته با شد ) 
4- گراف زیر داده شده است : الف با شروع از گره A پیمایش عرضی و عمقی گراف را بنویسید .ب ) پس از نوشتن ماتریس همجواری ، ماتریس مسیر آنرا نیز بدست آمورید .ج) گراف را بدون جهت فرض نموده ، به روش kruskal (وارشال ) درخت پوشای کمینه معادل آن را بدست آورید .
6-در گراف زیر ، كوتاهترین مسیر از راس صفر تا بقیه رئوس را به روش دیكسترا بدست آورید. ب)جستجوی عرضی و عمقی را با شروع از راس صفر انجام دهید.

 

 

نظر فراموش نشه

 


مطالب مشابه :


ترانهاده كردن ماتريس اسپارس

تکنیک های پیشرفته کامپیوتر - ترانهاده كردن ماتريس اسپارس - ترانهاده كردن ماتريس




بردار و ماتریس در متلب

ترانهاده کردن ماتریس با تک کوتیشن انجام می تبدیل یک ماتریس تقریبا خالی به ماتریس اسپارس :




ساختمان داده در C++

ترانهاده يك ماتريس اسپارس: ترانهاده يك ماتريس يعني جاي سطرها و ستونهاي آن را عوض كنيم.




آرم کافی نت جگوار

كافي نت جگوار گچساران - آرم کافی نت جگوار - سرعت- امنيت- كيفيت- آرامش - با خطوط پرسرعت adsl




دانلود چندین برنامه برای درس ساختمان داده ها

الگوریتم تبدیل ماتریس پایین مثلثی ضرب دو ماتریس اسپارس ایجاد ترانهاده یک ماتریس




نمونه سوالات ساختمان داه استاد شمس الدینی

16- الف ) ماتریس اسپارس روبرو را به شکل ویژه نمایش دهید .ب) ترانهاده آن را بیابید .ج)




برچسب :