3- فرض کنید برای نگهداری یک سری عدد صحیح از یک صف حلقوی 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-در گراف زیر ، كوتاهترین مسیر از راس صفر تا بقیه رئوس را به روش دیكسترا بدست آورید. ب)جستجوی عرضی و عمقی را با شروع از راس صفر انجام دهید.