数据结构期末复习试卷B(共7页).doc
精选优质文档-倾情为你奉上装 订 线数据结构复 习 卷 B题号一二三四总分得分得分评卷人 一 选择题(1*15=15分)1算法指的是.（ ） A计算机程序 B解决问题的计算方法 C排序算法 D解决问题的有限运算序列2某程序的时间复杂度为（3n +n2+8）, 其数量级表示为.（ ）AO（3n） BO（n） CO（n2） D13线性表采用链式存储时，结点的存储地址.（ ） A必须是不连续的 B连续与否均可 C必须是连续的 D和头结点的存储地址相连续4设数组datam作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出队操作后其头指针front值为（ ） Afront=front+1 Bfront=(front+1)%(m-1) Cfront=(front-1)%m Dfront=(front+1)%m5若已知一个栈的入栈序列是1 2 3 4 5，不可能有下列那个出栈序列（ ）A1 2 3 4 5 B1 3 4 2 5C3 4 5 2 1 D1 4 2 3 56一个线性表第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（ ）A. 110 B. 108 C. 100 D. 1207一棵二叉树有8个叶子,则度为2的结点个数为. .( )A8 B2C9 D78一棵深度为5层的二叉树，其结点总数最多不会超过：. .( )A 31个 B36个 C 72个D63个9串是一种特殊的线性表，其特殊性体现在： ( )A可以顺序存储 B 串中的每个数据元素仅由一个字符组成C可以链式存储 D数据元素可以是多个字符10下面程序段的时间复杂度为. ( )y=0;For(i=1;i<=n;i+) y+;AO(n) BO(n2)CO(sqrt(n) DO(1)11设有两个串p和q，求q在p中首次出现的位置的运算称作（ ）连接 B子串定位操作C求子串 D求串长12已知二叉树的先序序列为ABDECF，中序序列为DBEAFC，则后序序列为（ ）ADEBAFC BDEFBCA CDEBCFA DDEBFCA13按照二叉树的定义,具有3个结点的二叉树的状态数为.（ ）A. 5 B. 4 C. 3 D. 214将长度为n的单链表链接在长度为m的单链表之后的的时间复杂度为（ ） AO（1） BO（n） CO（m） DO（m+n）装 订 线15在线性表的下列运算中，不改变数据元素之间结构关系的运算是.（ ）A插入 B删除 C排序 D定位 得分评卷人 二填空题(1*20=20分)1所有能输入到计算机中并被计算机程序处理的符号总称，被称为_。在计算机程序中通常作为一个整体进行考虑和处理的，通常被称为 _。不可分割的、含有独立意义的数据的最小单位，被称为_。2在一个带头结点的单循环链表中，p指向尾结点的直接前驱，则指向头结点的指针head可用p表示为head=_ _。3 线性结构包括_ 、_、_、数组、串。4 判定顺序表a为空的条件是：_。5 顺序存储结构的队列称为_，链式存储结构的队列称为_。6 串的存储方式主要分为二种：_存储结构和_存储结构。7若二叉树有m个叶结点，则度为2的结点有 个。 8树中结点的最大层次称为树的_。树中除根结点以外，每个结点都有_个前驱和0到多个后继。9对于一棵完全二叉树按层次从左到右编号之后，结点i的左孩子编号为_，右孩子编号为_，其父结点的编号为_。10深度为K的二叉树，结点最多有 个，最少有 个。得分评卷人 三综合运用题(5*5=25分)1写出按先根序列遍历下面二叉树的结果： CBAIHFDKJGE24把下列森林转换为对应的二叉树。3.已知一棵二叉树的后序扫描序列和中序扫描序列分别为DECBHGFA和BDCEAFHG，试画出该二叉树。ABCDEFGHLIJK4画出下面树的孩子兄弟表示法。装 订 线CBAIHFDKJGE5将以下二叉树转换为森林。得分评卷人 四、选择填空（4*5=20分）已知L是无头结点的单链表，且p结点既不是首结点，也不是尾结点，试从下列提供的语句中选出合适的语句序列。（1）在p结点后插入s结点： 。（2）在p结点前插入s结点： 。（3）在表首插入s结点： 。（4）在表尾插入s结点： 。（5）删除p结点： 。p->next=s;s->next=L;free(p)s->next=p->next;L=s;q->next=p->next;q=L;while(q->next!=p)q=q->next;q ->next=s;while(q->next!=null)q=q->next; s->next=q->next; s->next=p; 得分评卷人 五程序实践题(10*2=20分)1.写一函数求带头结点单链表head中所有元素值的平均值。typedef struct node int data;struct node *next; LINKLIST;int average(LINKLIST *head)2. 采用中序递归遍历算法，编制一个求二叉树结点元素总和的函数。typedef struct node1 int data;struct node1 *lchild,*rchild;BTCHINALR;int sum(BTCHINALR *bt)3编写算法：已知线性链表head，在p指针所指向的结点后插入一个元素x。命题人： 校对：命题人：马建林 校对：单击此处输入试题校对专心-专注-专业
