下载后可任意编辑一、 单项选择题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+1下载后可任意编辑2．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．什么情况下用顺序表比链表好? 答: 顺序表适于做查找这样的静态操作, 链表适于做插入和删除这样的动态操作。假如线性表的变化...
