数据结构期中试题有答案

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

2、（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

3、=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叉树，可能达到的最

4、小深度为多少？（C）三、简答（共22分）1、对于线性表的两种存储结构并且很少进行插入和删除操作,择哪种存储结构？试说明理由。An-kBn-k+1C|logkn|+1D|logkn|其中|k|表示下取整得分评卷人（顺序存储和链式存储结构），如果线性表基本稳定，但是要求以最快速度存取线性表中的元素，则应选（5分）答：选择顺序存储。因为顺序存储可以通过下标随意访问线性表中的元素，效率较高。而链式存储要访问某个元素是，需要遍历链表来找到这个元素，效率比较低。选择顺序存储结构；理由有两点（1）主要从插入删除操作在移动元素的个数上分析，（2）顺序存储定位块，可直接定位。2、哈夫曼树在构造时，首先进行初始化

5、存储空间，结果如左下图，当构造完成后，请填写最后状态表，如右下图。（6分）（见课本P148）weightParentLchildRchildweightParentLchildRchild15000159002290002291400370003710004800048100051400051412006230006231300730007390081100081111009-00098111710-0001015123411-0001119138912-00012291451013-00013421561114-00014581521215-00015100013143、内存中一片连续空间（

6、不妨假设地址从1到m）提供给两个栈si和s2使用，怎样分配这部分存储空间，使得对任一栈，仅当这部分空间全满时才发生上溢。如何判断栈满，栈空，并对两个栈的容量进行分析。（7分）答：把两个栈的栈底分别设定为空间的两头，也就是1,m。其中一个栈从低地址向高地址增长，另外一个从高地址往低地址存放。这样可以保证空间利用更好。空、满、容量分析将s1,s2栈底分别设在连续内存空间的两端，栈顶向内存中间进发；注：栈顶=0,或栈顶=m+1当|s1.top-s2.top|=1时，栈满；当一个栈顶为0,另一个栈顶为m+1时，栈空;容量分析：从低地址向高地址增长时，容量为栈顶top的值；从高地址往低地址存放时，容量为

7、m+1-（栈顶top的值）。4、设某二叉树的前序遍历序列为：ABCDEFGHI,中序遍历序列为：BCAEDGHFI。（1）试画出该二叉树；（2）画出该二叉树后序线索化图。（3）试画出该二叉树对应的森林。（10分）(1)（2）后序序列：CBEHGIFDA体现到图上便可（3）（四棵树）得分评卷人四、阅读算法(每小题5分，共25分)1. voidAE(Stack&S)InitStack(S);Push(S,3);Push(S,4);intx=Pop(S)+2*Pop(S);Push(S,x);inti,a5=1,5,8,12,15;for(i=0;i<5;i+)Push(S,2*ai)

8、;while(!StackEmpty(S)cout<<Pop(S)<<该算法被调用后得到的输出结果为：答：30、24、16、10、2、102. voidABC(BTNode*BT,int&c1,int&c2)if(BT!=NULL)ABC(BT->left,c1,c2);c1+;if(BT->left=NULL&&BT->right=NULL)c2+;ABC(BT->right,c1,c2);/if该函数执行的功能是什么？答：该函数的功能是统计，二叉树结点总数，和叶子结点总数。c1为二叉树结点数，c2为二叉树中叶子

9、结点数3. 在下面的每个程序段中，假定线性表La的类型为List,e的类型为ElemType,元素类型ElemType为int,并假定每个程序段是连续执行的。试写出每个程序段执行后所得到的线性表La。11)InitList(La);Inta=100,26,57,34,79;For(i=0;i<5;i+)ListInsert(La,1,ai);/逆序；(2) ListDelete(La,1,e);/e=79;ListInsert(La,ListLength(La)+1,e);/在最后一个位置插入e;(3) ClearList(La);For(i=0;i<5;i+)ListInsert

10、(La,i+1,ai);/顺序；答：(1)79345726100(2) 34572610079(3) 10026573479ListInsert(&L,i,e)/前插(入)初始条件：线性表L已存在，Ki<ListLength(L)+1。操作Z果：在L中第i个位置之前插入新的数据元素e,L的长度加1。ListDelete(&L,i,&e)/删除初始条件：线性表L已存在且非空，1<i<ListLength(L)。操作Z果：删除L的第i个数据元素，并用e返回其值，L的长度减1。ClearList(&L)/置空初始条件：线性表L已存在。操作Z果：将L重

11、置为空表。4 .intPrime(intn)(inti=1;intx=(int)sqrt(n);while(+i<=x)if(n%i=0)break;/为合数；if(i>x)return1;/不能被2Jn中的数整除，为素数；elsereturn0;/为合数；(1)指出该算法的功能；(2)该算法的时间复杂度是多少？答：(1)求素数(该算法的功能是判断n是否为素数，是返回1,否则返回0)(2)O(.n);一个数，如果只有1和它本身两个因数，这样的数叫做质数，又称素数。例如(10以内)2,3,5,7是质数，而4,6,8,9则不是，后者称为合成数或合数。特别声明一点，1既不是质数也不是合数

12、。为什么1不是质数呢？因为如果把1也算作质数的话，那么在分解质因数时，就可以随便添上几个1了。比如30,分解质因数是2*3*5,因为分解质因数是要把一个数写成质数的连乘积，如果把1算作质数的话，那么在这个算式中，就可以随便添上几个1了，分解质因数也就没法分解了。从这个观点可将整数分为三种，一种叫质数，一种叫合成数，还有一个1。(1不是质数，也不是合数)。著名的高斯唯一分解定理说，任何一个整数。可以写成一串质数相乘的积。质数中除2是偶数外，其他都是奇数。5 .写出下述算法A的功能：其中BiTree定义如下：TypedefstructBiTNodeTElemTypedata;structBiTNo

13、de*LChild,*RChild;BiTNode,*BiTree;StatusA(BiTreeT)QueueQ;InitQueue(Q);ENQueue(Q,T);While(notQueueEmpty(Q)DeQueue(Q,e);If(e=NULL)break;ElsePrint(e.data);ENQueue(Q,e.LChild);ENQueue(Q.e.RChild);答：层次遍历二叉树的非递归算法得分评卷人五、算法填空(每空1分，共9分)1 .堆分配存储方式下，串连接函数。typedefstructchar*ch;intlen;HString;HString*s,t;Status

14、StrCat(s,t)/*将串t连接在串s的后面*/inti;char*temp;temp=(char*)malloc(s->len+t.len);if(temp=NULL)return(0);for(i=0;i<s->len;i+)tempi=s->chi;for(i=s->len;i<s->len+t.len;i+)tempi=t.chi-s->len;s->len+=t.len;free(s->ch);s->ch=temp;return(1);2 .向单链表的末尾添加一个元素的算法。LNode是一个包含(data,Next

15、)的结构体VoidInsertRear(LNode*&HL,constElemType&item)(LNode*newptr;newptr=newLNode;If(newptr=NULL)(cerr<<"Memoryallocationfailare!"<<endl;exit(1);newptr->data=item;newptr->next=NULL;if(HL=NULL)HL=_newptr;elseLNode*P=HL;While(P->next!=NULL)p=p->next;p->next=ne

16、wptr;得分评卷人六、编写算法(每小题10分，共20分)1 .编写算法，将一单链表逆转。要求逆转在原链表上进行，不允许重新构造一个链表(可以申明临时变量、指针)。该链表带头节点、头节点和数据节点的结构定义如下typedefstructLNodeElemTypedata;StructLNode*next;*List,LNode;函数定义：voidinvert(List&L)voidinvert(List&L)/链表的就地逆置；带头结点的单链表；p=L->next;q=p->next;s=q->next;p->next=NULL;while(s!=NULL

17、)q->next=p;p=q;/p为新表表头结点；q=s;s=s->next;/把L的元素逐个插入新表表头)q->next=p;L->next=q;/invert本算法的思想：逐个地把L的当前元素q插入新的链表头部，将元素指针反向。2 .编写算法计算给定二叉树中叶结点的个数。其中树节点定义如下typedefstructBiTNodeDataTypedata;StructBiTNode*LChild,*RChild;BiTNode,*BiTree;函数定义：CountLeaf(BiTreeT,int&LeafNum)voidCountLeaf(BiTreeT,in

18、t&LeafNum)if(T)if(!T->lchild)&&(!T->rchild)LeafNum+;/对叶子结点计数CountLeaf(T->lchild,LeafNum);/求左子树叶子数CountLeaf(T->rchild,LeafNum);/求右子树叶子数/CountLeaf算法的基本思想：先序(或中序或后序)遍历二叉树，在遍历过程中查找叶子结点，并计数。由此，需在遍历算法中增添一个“计数”的参数，并将算法中“访问结点”的操作改为：若是叶子，则计数器增1。得分评卷人七、计算(每小题4分，共12分)1、对比f(n)和g(n),当n接近无穷时，哪个函数增长更快。Af(n)=(ln(n!)+5)2g(n)=13n2.5g(n)增长速度快Bf(n)=2(n*n*n)+(2n)2g(n尸n(n*n)+n5F(n)增长速度快2、具有n个节点的满二叉树的叶子节点的个数是多