《数据结构》期中试题(有答案)

《《数据结构》期中试题(有答案)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、福建师范大学数学与计算机科学学院2009--2010学年度上学期08电信《数据结构》期中试题试卷类别：闭卷考试时间：90分钟专业：学号：姓名：题号一二三四五六七八总分得分得分评卷人一、选择题（每小题1分，共6分）1、关于线性表的说法,下面选项正确的是（B）A线性表的特点是每个元素都有一个前驱和一个后继（除头、尾元素，直接的）B线性表是具有n(n>=0)个元素的一个有限序列C线性表就是顺序存储的表（可以是链式存储结构）D线性表只能用顺序存储结构实现（可以是链式存储结构）2、表长为n的顺序存储的线性表，当在

2、任何一个位置上插入或者删除一个元素的概率相等时，删除一个元素需要移动元素的平均个数为（A）A(n-1)/2Bn/2CnDn-13、设双向循环链表中节点的结构为(data,LLink,RLink)，且不带头节点。若想在指针p所指节点之后插入指针s所指节点，则应执行下列哪一个操作？（D）Ap->RLink=s;s->LLink=p;p->RLink->LLink=s;s->RLink=p->RLink;Bp->RLink=s;p->RLink->LLink=s;s->LLink=p;s->RLink=p->

3、RLink;Cs->LLink=p;s->RLink=p->RLink;p->RLink=s;p->RLink->LLink=s;Ds->LLink=p;s->RLink=p->RLink;p->RLink->LLink=s;p->RLink=s;4、栈和队列都是（A）A限制存取位置的线性结构（都是一种特殊的线性链表）B链式存储的非线性结构（可以顺序存储）C顺序存储的线性结构（可以链式存储）D限制存取位置的非线性结构（如：树）5、单循环链表表示的队列长度为n，若只设头指针，则入队的时间复杂度为（A）（共

4、9页第-9-页）AO(n)BO(1)CO(n*n)DO(n*logn)在队尾入队，队头出队6、一棵含有n个节点的k叉树，可能达到的最小深度为多少？（C）An-kBn-k+1C

5、logkn

6、+1D

7、logkn

8、其中

9、k

10、表示下取整得分评卷人三、简答（共22分）1、对于线性表的两种存储结构（顺序存储和链式存储结构），如果线性表基本稳定，并且很少进行插入和删除操作，但是要求以最快速度存取线性表中的元素，则应选择哪种存储结构？试说明理由。（5分）答：选择顺序存储。因为顺序存储可以通过下标随意访问线性表中的元素，

11、效率较高。而链式存储要访问某个元素是，需要遍历链表来找到这个元素，效率比较低。选择顺序存储结构；理由有两点（1）主要从插入删除操作在移动元素的个数上分析，（2）顺序存储定位块，可直接定位。2、哈夫曼树在构造时，首先进行初始化存储空间，结果如左下图，当构造完成后，请填写最后状态表，如右下图。（6分）（见课本P148）weightParentLchildRchildweightParentLchildRchild123456789101112131415500029000700080001400023000

12、300011000--000--000--000--000--000--000--00012345678910111213141559002914007100081000141200231300390011110081117151234191389291451042156115815212100013143（共9页第-9-页）、内存中一片连续空间（不妨假设地址从1到m）提供给两个栈s1和s2使用，怎样分配这部分存储空间，使得对任一栈，仅当这部分空间全满时才发生上溢。如何判断栈满，栈空，并对两个栈的容量进

13、行分析。（7分）答：把两个栈的栈底分别设定为空间的两头，也就是1，m。其中一个栈从低地址向高地址增长，另外一个从高地址往低地址存放。这样可以保证空间利用更好。空、满、容量分析将s1,s2栈底分别设在连续内存空间的两端，栈顶向内存中间进发；注：栈顶=0，或栈顶=m+1当

14、s1.top-s2.top

15、=1时，栈满；当一个栈顶为0，另一个栈顶为m+1时，栈空；容量分析：从低地址向高地址增长时，容量为栈顶top的值；从高地址往低地址存放时，容量为m+1-（栈顶top的值）。4、设某二叉树的前序遍历序列为：ABC

16、DEFGHI，中序遍历序列为：BCAEDGHFI。（1）试画出该二叉树；（2）画出该二叉树后序线索化图。（3）试画出该二叉树对应的森林。（10分）（1）（3）（四棵树）ABCDEFGIH（2）后序序列：CBEHGIFDA体现到图上便可ABCDEFGIHABCDEFGHI得分评卷人四、阅读算法（每小题5分，共25分）1.      voidAE(Stack&S){InitStack(S);Push(S,3);Push(S,4);intx=Po