内容发布更新时间 : 2024/5/3 9:01:06星期一 下面是文章的全部内容请认真阅读。

福建师范大学数学与计算机科学学院 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 页 第- 1 -页）

二 三 四 五 六 七 八 总分 6、一棵含有n个节点的k叉树，可能达到的最小深度为多少？（ C ） A n-k B n-k+1 C |logkn|+1 D |logkn| 其中|k|表示下取整 得分 评卷人 三、简答（共22分） 1、对于线性表的两种存储结构（顺序存储和链式存储结构），如果线性表基本稳定，并且很少进行插入和删除操作，但是要求以最快速度存取线性表中的元素，则应选择哪种存储结构？试说明理由。（5分） 答：选择顺序存储。因为顺序存储可以通过下标随意访问线性表中的元素，效率较高。而链式存储要访问某个元素是，需要遍历链表来找到这个元素，效率比较低。 选择顺序存储结构；理由有两点（1）主要从插入删除操作在移动元素的个数上分析，（2）顺序存储定位块，可直接定位。 2、哈夫曼树在构造时，首先进行初始化存储空间，结果如左下图，当构造完成后，请填写最后状态表，如右下图。（6分）（见课本P148） weight Parent 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 5 29 7 8 14 23 3 11 -- -- -- -- -- -- -- Lchild Rchild 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 weight Parent 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 5 29 7 8 14 23 3 11 8 15 19 29 42 58 100 Lchild Rchild 0 0 0 0 0 0 0 0 1 3 8 5 6 2 13 0 0 0 0 0 0 0 0 7 4 9 10 11 12 14 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 9 14 10 10 12 13 9 11 11 12 13 14 15 15 0 3、内存中一片连续空间（不妨假设地址从1到m）提供给两个栈s1和s2使用，怎样分配这部分存储空间，使得对任一栈，仅当这部分空间全满时才发生上溢。如何判断栈满，栈空，并对两个栈的容量进行分析。（7分） （共 9 页 第- 2 -页）

答： 把两个栈的栈底分别设定为空间的两头，也就是1，m。其中一个栈从低地址向高地址增长，另外一个从高地址往低地址存放。这样可以保证空间利用更好。空、满、容量分析 将s1,s2栈底分别设在连续内存空间的两端，栈顶向内存中间进发； 注：栈顶=0，或栈顶=m+1 当|s1.top-s2.top|=1时，栈满；当一个栈顶为0，另一个栈顶为m+1时，栈空； 容量分析： 从低地址向高地址增长时，容量为栈顶top的值； 从高地址往低地址存放时，容量为m+1-（栈顶top的值）。 4、设某二叉树的前序遍历序列为：ABCDEFGHI，中序遍历序列为：BCAEDGHFI。（1）试画出该二叉树；（2）画出该二叉树后序线索化图。（3）试画出该二叉树对应的森林。（10分） （1） （3）（四棵树） A B C E G D F I B C E G A D F I G B F H A C E I D H H （2）后序序列：CBEHGIFDA体现到图上便可 得分 评卷人 四、阅读算法（每小题5分，共25分） 1. void AE(Stack& S){ InitStack(S); Push(S,3); Push(S,4); int x=Pop(S)+2*Pop(S); Push(S,x); int i,a[5]={1,5,8,12,15}; for(i=0;i<5;i++) Push(S,2*a[i]); while(!StackEmpty(S)) cout<