简述计算机科学的核心内容,北京大学计算机科学与技术(2018秋)作业及复习

59.(第十章)外排序是指在排序前后&＃xff0c;数据在外存上&＃xff0c;排序时数据调入内存进行的排序方法.

60.(第十章)在选择排序、冒泡排序、归并排序中, 归并排序是空间复杂度最大的。

三、简答和程序题(共10题&＃xff0c;每题4分&＃xff0c;共40分)

61.(第二章)简述顺序表和链表存储方式的特点。

顺序表的优点势可以随机访问数据元素&＃xff1b;缺点是大小固定&＃xff0c;不利于增减结点(增减操作需要移动元素)。链表的优点是采用指针方式增减结点&＃xff0c;非常方便(只需要改变指针指向&＃xff0c;不移动结点)。其缺点是不能进行随机访问&＃xff0c;只能顺序访问&＃xff1b;另外&＃xff0c;每个结点上增加指针域&＃xff0c;造成额外存储空间增大。

62.(第二章)在一个单链表HL中删除指针p所指结点&＃xff0c;应执行如下关键操作&＃xff1a;

if(p &＃61;&＃61; HL) HL &＃61; HL->next;

else{

q &＃61; HL;

while(q->next !&＃61; p) q &＃61; q->next;

q->next &＃61; p->next; 或q->next &＃61; q->next->next;

}delete p;

63.(第四章)以下2个问题基于下面的环形队列&＃xff1a;设环形队列Q[7]的当前状态如下&＃xff0c;

写出队列Q的队空、队满定条件及进队、出队操作的的描述语句。

空&＃xff1a;rear &＃61;&＃61; front

满&＃xff1a;(rear&＃43;1)%MaxSize &＃61;&＃61; front