（共 9 页第- 1 -页）福建师范大学数学与计算机科学学院2009--2010学年度上学期 08 电信《数据结构》期中试题试卷类别：闭卷考试时间： 90 分钟专业：学号：姓名： ZhengKen 题号一二三四五六七八总分得分得分评卷人一、选择题（每小题1 分，共 6 分）1、关于线性表的说法,下面选项正确的是（B ）A 线性表的特点是每个元素都有一个前驱和一个后继（除头、尾元素，直接的）B 线性表是具有n(n>=0) 个元素的一个有限序列C 线性表就是顺序存储的表（可以是链式存储结构）D 线性表只能用顺序存储结构实现（可以是链式存储结构）2、表长为 n 的顺序存储的线性表，当在任何一个位置上插入或者删除一个元素的概率相等时，删除一个元素需要移动元素的平均个数为（ A ）A (n-1)/2 B n/2 C n D n-1 3、设双向循环链表中节点的结构为(data,LLink,RLink)，且不带头节点。若想在指针 p 所指节点之后插入指针s 所指节点，则应执行下列哪一个操作？（ D ）A p->RLink=s; s->LLink=p; p->RLink->LLink=s; s->RLink=p->RLink; B p->RLink=s; p->RLink->LLink=s; s->LLink=p; s->RLink=p->RLink; C s->LLink=p; s->RLink=p->RLink; p->RLink=s; p->RLink->LLink=s; D s->LLink=p; s->RLink=p->RLink; p->RLink->LLink=s; p->RLink=s; 4、栈和队列都是（ A ）A 限制存取位置的线性结构（都是一种特殊的线性链表）B 链式存储 的非线性结构（可以顺序存储）C 顺序存储的线性结构（可以链式存储）D 限制存取位置的非线性 结构 （如：树）5、单循环链表表示的队列长度为n，若只设头指针， 则入队的时间复杂度为（ A ）A O(n) B O(1) C O(n*n) D O(n*logn) 在队尾入队，队头出队（共 9 页第- 2 -页）6、一棵含有n 个节点的 k 叉树，可能达到的最小深度为多少？（ C ）A n-k B n-k+1 C |log kn|+1 D |logkn| 其中 |k|表示下取整得分评卷人三、简答（共22 分）1、对于线性表的两种存储结构（顺序存储和链式存储结构），如果线性表基本稳定，并且 很少 进行插入和删除操作，但是要求以 最快速度存取 线性表中的元素，则应选择哪种存储结构？试说明理由。（5 分）答：选择顺序存储。 因为顺序存储可以通过下标随意访问线性表中的元素，效率较高。而链式存储要访问某个元素是，需要遍历链表来找到这个元素，效率比较低。选择顺序存储结构； 理由有两点 （1）主要从插入...
