数据构造（本）形成性考核作业答案作业 1一、单项选择题1．C 2．D 3．B 4．C 5．D 6．C 7．B 8．C 9．A 10．B11．C 12．D 13．C 14．A 15．B 16．C 17．C 18．B 19．B 20．D二、填空题 1．n-i+12．n-i 3．集合 线性构造 树形构造 图状构造 4．物理构造 存储构造 5．线性构造 非线性构造6．有穷性 确定性 可形性 有零个或多种输入 有零个或多种输出 7．图状构造 8．树形构造 9．线性构造 10． n-1 O(n)11．s->next=p->next; 12．head 13．q->next=p->next; 14．p->next=head; 15．单链表16．次序存储 链式存储17．存储构造18．两个 直接后继 直接前驱 尾结点 头结点19．头结点的指针 指向第一种结点的指针20．链式 链表三、问答题1．简述数据的逻辑构造和存储构造的区别与联络，它们怎样影响算法的设计与实现？答：若用结点表达某个数据元素，则结点与结点之间的逻辑关系就称为数据的逻辑构造。数据在计算机中的存储表达称为数据的存储构造。可见，数据的逻辑构造是反应数据之间的固有关系，而数据的存储构造是数据在计算机中的存储表达。尽管因采用的存储构造不一样，逻辑上相邻的结点，其物理地址未必相似，但可通过结点的内部信息，找到其相邻的结点，从而保留了逻辑构造的特点。采用的存储构造不一样，对数据的操作在灵活性，算法复杂度等方面差异较大。2．解释次序存储构造和链式存储构造的特点，并比较次序存储构造和链式存储构造的优缺陷。答：次序构造存储时，相邻数据元素的寄存地址也相邻，即逻辑构造和存储构造是统一的，，规定内存中存储单元的地址必须是持续的。长处：一般状况下，存储密度大，存储空间运用率高。缺陷：（1）在做插入和删除操作时，需移动大量元素；（2）由于难以估计，必须预先分派较大的空间，往往使存储空间不能得到充足运用；（3）表的容量难以扩充。链式构造存储时，相邻数据元素可随意寄存，所占空间分为两部分，一部分寄存结点值，另一部分寄存表达结点间关系的指针。长处：插入和删除元素时很以便，使用灵活。缺陷：存储密度小，存储空间运用率低。3．什么状况下用次序表比链表好？答：次序表适于做查找这样的静态操作，链表适于做插入和删除这样的动态操作。假如线性表的变化长度变化不大，且其重要操作是查找，则采用次序表；假如线性表的长度变化较大，且其重要操作是插入、删除操作，则采用链表。4．解释头结点、第一种结点（或称首元结点）、头指针这...
