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

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

2、，删除一个元素需要移动元素的平均个数为（ A） A (n-1)/2 B n/2 C n D n-13、设双向循环链表中节点的结构为(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

3、=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) 在队尾入队，队头出队6、一棵含有n个节点的k叉树，可能达到的最小深度为多少？（ C ） A n-k B n-k+1 C

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

5、后，请填写最后状态表，如右下图。（6分）（见课本P148）weightParentLchildRchildweightParentLchildRchild123456789101112131415500029000700080001400023000300011000-000-000-000-000-000-000-00012345678910111213141559002914007100081000141200231300390011110081117151234191389291451042156115815212100013143、内存中一片连续空间（不妨假设地址从1到m）提供给两个栈

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

7、某二叉树的前序遍历序列为：ABCDEFGHI，中序遍历序列为：BCAEDGHFI。（1）试画出该二叉树；（2）画出该二叉树后序线索化图。（3）试画出该二叉树对应的森林。（10分） （1） （3）（四棵树）ABCDEFGIH（2）后序序列：CBEHGIFDA体现到图上便可ABCDEFGIHABCDEFGHI得分评卷人四、阅读算法（每小题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,a5=1,5,8,12,15; for(i=0;i5;

8、i+) Push(S,2*ai); while(!StackEmpty(S) coutPop(S)left,c1,c2); c1+; if (BT-left=NULL&BT-right=NULL) c2+; ABC(BT-right,c1,c2); /if 该函数执行的功能是什么？ 答：该函数的功能是统计，二叉树结点总数，和叶子结点总数。 c1为二叉树结点数，c2为二叉树中叶子结点数3. 在下面的每个程序段中，假定线性表La的类型为List，e的类型为ElemType,元素类型ElemType为int，并假定每个程序段是连续执行的。试写出每个程序段执行后所得到的线性表La。（1）InitLis

9、t(La); Int a=100,26,57,34,79;（1）79 34 57 26 100 For (i=0;i5;i+) ListInsert(La,1,ai); /逆序；（2）ListDelete(La,1,e); /e=79; （2）34 57 26 100 79ListInsert(La,ListLength(La)+1,e); /在最后一个位置插入e；（3）ClearList(La); For (i=0;i5;i+)（3）100 26 57 34 79 ListInsert(La,i+1,ai); /顺序；ListInsert( &L , i , e ) /前插(入) 初始条件:

10、 线性表L 已存在 , 1 i ListLength ( L )+1 。 操作结果: 在L 中第 i 个位置之前插入新的 数据元 素e , L的长度加1 。ListDelete( &L , i , &e ) /删除 初始条件: 线性表L 已存在且非空 , 1 i ListLength( L ) 。 操作结果: 删除L 的第 i 个数据元素 , 并 用e 返回其值, L的长度减1 。 ClearList ( &L ) /置空 初始条件:线性表L 已存在。 操作结果:将L重置为空表。4. int Prime(int n) int i=1; int x=(int) sqrt(n); while (+

11、ix) return 1; /不能被2中的数整除，为素数； else return 0; /为合数； (1)指出该算法的功能；(2)该算法的时间复杂度是多少？答：（1）求素数（该算法的功能是判断n是否为素数，是返回1，否则返回0） （2）O（）；一个数，如果只有1和它本身两个因数，这样的数叫做质数，又称素数。例如（10以内） 2，3，5，7 是质数，而 4，6，8，9 则不是，后者称为合成数或合数。特别声明一点，1既不是质数也不是合数。为什么1不是质数呢?因为如果把1也算作质数的话,那么在分解质因数时,就可以随便添上几个1了。比如30，分解质因数是2*3*5，因为分解质因数是要把一个数写成质数

12、的连乘积，如果把1算作质数的话，那么在这个算式中，就可以随便添上几个1了，分解质因数也就没法分解了。从这个观点可将整数分为三种，一种叫质数，一种叫合成数，还有一个1。（1不是质数，也不是合数）。著名的高斯唯一分解定理说，任何一个整数。可以写成一串质数相乘的积。质数中除2是偶数外，其他都是奇数。5. 写出下述算法A的功能： 其中BiTree定义如下: Typedef struct BiTNode TElemType data; struct BiTNode *LChild, *RChild;BiTNode, *BiTree;Status A(BiTree T) Queue Q; InitQueu

13、e(Q); ENQueue(Q,T); While(not QueueEmpty(Q) DeQueue(Q,e); If(e=NULL) break; Else Print(e.data);ENQueue(Q,e.LChild); ENQueue(Q.e.RChild); 答：层次遍历二叉树的非递归算法 得分评卷人五、算法填空（每空1分，共9分）1堆分配存储方式下，串连接函数。typedef struct char * ch； int len； HString； HString *s， t; Status StrCat(s， t) /* 将串t连接在串s的后面 */ int i; char *

14、temp; temp=(char*)malloc(s-len+t.len); if (temp=NULL) return(0); for (i=0; ilen ;i+) tempi=s-chi; for ( i=s-len ;ilen + t.len;i+) tempi=t.chi-s-len; s-len+=t.len; free(s-ch); s-ch=temp; return(1); 2向单链表的末尾添加一个元素的算法。 LNode是一个包含（data，Next）的结构体Void InsertRear(LNode*& HL,const ElemType& item)LNode* newp

15、tr;newptr=new LNode;If (_newptr=NULL_)cerrMemory allocation failare!data=item; _newptr-next=NULL;if (HL=NULL) HL=_newptr_;elseLNode* P=HL;While (P-next!=NULL) _p=p-next_;p-next=newptr; 得分评卷人六、编写算法（每小题10分，共20分）1编写算法，将一单链表逆转。要求逆转在原链表上进行，不允许重新构造一个链表（可以申明临时变量、指针）。该链表带头节点、头节点和数据节点的结构定义如下typedef struct LN

16、ode ElemType data; Struct LNode* next;*List, LNode;函数定义：void invert(List & L)void invert (List & L)/链表的就地逆置;带头结点的单链表；p=L-next; q=p-next; s=q-next; p-next=NULL;while(s!=NULL)q-next=p; p=q; / p为新表表头结点;q=s; s=s-next; /把L的元素逐个插入新表表头q-next=p; L-next=q; /将头结点指向最后一个结点。/ invert本算法的思想：逐个地把L的当前元素q插入新的链表头部，将元素

17、指针反向。2编写算法计算给定二叉树中叶结点的个数。 其中树节点定义如下 typedef struct BiTNode DataType data; Struct BiTNode *LChild, * RChild; BiTNode, *BiTree; 函数定义：CountLeaf (BiTree T, int & LeafNum)void CountLeaf (BiTree T, int& LeafNum) if ( T ) if (!T-lchild)& (!T-rchild) LeafNum +; / 对叶子结点计数 CountLeaf( T-lchild, LeafNum); / 求左子

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