《数据结构》期中试题（有答案）

本文格式为Word版，下载可任意编辑——《数据结构》期中试题（有答案）福建师范大学数学与计算机科学学院2023--2023学年度上学期08电信

《数据结构》期中试题

试卷类别：闭卷考试时间：90分钟

专业：学号：姓名：ZhengKen题号一得分得分评卷人一、选择题（每题1分，共6分）1、关于线性表的说法,下面选项正确的是（B）A线性表的特点是每个元素都有一个前驱和一个后继（除头、尾元素，直接的）B线性表是具有n(n>=0)个元素的一个有限序列C线性表就是顺序存储的表（可以是链式存储结构）D线性表只能用顺序存储结构实现（可以是链式存储结构）2、表长为n的顺序存储的线性表，当在任何一个位置上插入或者删除一个元素的概率相等时，删除一个元素需要移动元素的平均个数为（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->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）AO(n)BO(1)CO(n*n)DO(n*logn)在队尾入队，队头出队（共9页第-1-页）

二三四五六七八总分6、一棵含有n个节点的k叉树，可能达到的最小深度为多少？（C）An-kBn-k+1C|logkn|+1D|logkn|其中|k|表示下取整得分评卷人三、简答（共22分）1、对于线性表的两种存储结构（顺序存储和链式存储结构），假使线性表基本稳定，并且很少进行插入和删除操作，但是要求以最快速度存取线性表中的元素，则应选择哪种存储结构？试说明理由。（5分）答：选择顺序存储。由于顺序存储可以通过下标随意访问线性表中的元素，效率较高。而链式存储要访问某个元素是，需要遍历链表来找到这个元素，效率比较低。选择顺序存储结构；理由有两点（1）主要从插入删除操作在移动元素的个数上分析，（2）顺序存储定位块，可直接定位。2、哈夫曼树在构造时，首先进行初始化存储空间，结果如左下图，当构造完成后，请填写最终状态表，如右下图。（6分）（见课本P148）weightParent123456789101112131415529781423311--------------LchildRchild000000000000000000000000000000weightParent12345678910111213141552978142331181519294258100LchildRchild000000001385621300000000749101112140000000000000009141010121391111121314151503、内存中一片连续空间（不妨假设地址从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）（四棵树）ABCEGDFIBCEGADFIGBFHACEIDHH（2）后序序列：CBEHGIFDA表达到图上便可得分评卷人四、阅读算法（每题5分，共25分）1.voidAE(StackPush(S,3);Push(S,4);intx=Pop(S)+2*Pop(S);Push(S,x);inti,a[5]={1,5,8,12,15};for(i=0;iright,c1,c2);}//if}该函数执行的功能是什么？答：该函数的功能是统计，二叉树结点总数，和叶子结点总数。c1为二叉树结点数，c2为二叉树中叶子结点数3.在下面的每个程序段中，假定线性表La的类型为List，e的类型为ElemType,元素类型ElemType为int，并假定每个程序段是连续执行的。试写出每个程序段执行后所得到的线性表La。（1）InitList(La);Inta[]={100,26,57,34,79};（1）79345726100For(i=0;ix)return1;//不能被2…n中的数整除，为素数；elsereturn0;//为合数；}(1)指出该算法的功能；(2)该算法的时间繁杂度是多少？答：（1）求素数（该算法的功能是判断n是否为素数，是返回1，否则返回0）（2）O（n）；一个数，假使只有1和它本身两个因数，这样的数叫做质数，又称素数。例如（10以内）2，3，5，7是质数，而4，6，8，9则不是，后者称为合成数或合数。特别声明一点，1既不是质数也不是合数。为什么1不是质数呢?由于假使把1也算作质数的话,那么在分解质因数时,就可以随便添上几个1了。譬如30，分解质因数是2*3*5，由于分解质因数是要把一个数写成质数的连乘积，假使把1算作质数的话，那么在这个算式中，就可以随便添上几个1了，分解质因数也就没法分解了。从这个观点可将整数分为三种，一种叫质数，一种叫合成数，还有一个1。（1不是质数，也不是合数）。著名的高斯「唯一分解定理」说，任何一个整数。可以写成一串质数相乘的积。质数中除2是偶数外，其他都是奇数。5.写出下述算法A的功能：其中BiTree定义如下:TypedefstructBiTNode{TElemTypedata;structBiTNode*LChild,*RChild;}BiTNode,*BiTree;StatusA(BiTreeT){QueueQ;InitQueue(Q