数据结构期末试卷及答案

数据结构期末试卷及答案一、单项选择题（本大题共10小题，每小题2分，共20分，在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。）设某算法的时间复杂度递归关系式为T(n)=2T(n/2)+n，其中T(1)=1，则该算法的时间复杂度为（一个栈的入栈序列是1,2,3,4,5，则下列不可能的出栈序列是（）A.3,2,1,4,5B.2,4,3,1,5C.5,4,3,2,1D.4,2,3,1,5下列关于循环队列的叙述中，正确的是（）A.队列只能用顺序存储结构实现B.长度为MaxSize的循环队列中，元素个数为(reaD.循环队列不存在空队和满队的判定问题一个具有100个结点的完全二叉树（根结点在第1层），其深度为（）A.6B.7C.8D.9对于有n个顶点e条边的无向图，采用邻接矩阵存储时，邻接矩阵中零元素的个数为（）

A.eB.2eC.n2−2设哈夫曼树中有199个结点，则该哈夫曼树中叶子结点的个数为（）A.99B.100C.101D.102下列关于二叉排序树的叙述，正确的是（）A.二叉排序树的中序遍历序列一定是升序序列B.二叉排序树一定是平衡二叉树C.二叉排序树的查找时间复杂度一定是O(logn连通分量是对下列哪类图中极大连通子图的定义（）A.连通无向图B.强连通图C.有向图D.无向非连通图对有序表(5,13,19,21,37,56,64,75,80,88,92)进行折半查找，查找关键字21时，需要进行关键字比较的次数为（）A.2B.3C.4D.5对于关键字序列(25,50,15,35,80,85,20,40,36,70)，采用堆排序建立初始大根堆后，堆顶元素为（）A.25B.85C.50D.70二、填空题（本大题共15空，每空1分，共15分，请将答案填写在题中横线上）数据结构的三要素是指__________、__________和数据运算。字符串"abcd"（字符串最后一个字符为空格）的长度是__________，空格串""（包含三个空格）的长度是__________。对于不带头尾指针的长度为n的单链表，在表头插入结点的时间复杂度为__________，在表尾插入结点的时间复杂度为__________。一棵二叉树的前序遍历序列为ABDGCFE，中序遍历序列为DGBAFCE，则该二叉树的后序遍历序列为__________。深度为k（根结点在第1层）的满二叉树，其结点总个数为__________，所有叶子结点带权路径长度之和最小的二叉树称为__________。采用邻接表存储的图，其深度优先遍历算法类似于二叉树的__________遍历，广度优先遍历算法类似于二叉树的__________遍历。具有n个顶点的连通无向图，其生成树中包含__________条边，包含__________个顶点。二分查找法在长度为m的有序顺序表中进行查找，最坏情况下的时间复杂度为__________。若初始关键字序列基本有序，采用__________排序算法的时间效率最高。三、判断题（本大题共10小题，每小题1分，共10分，你认为正确的打√，错误的打×）线性表采用链式存储结构时，存储数据的内存单元地址一定是不连续的。（）空串的长度为0，因此空格串的长度也为0。（）栈和队列本质上都是操作受限的线性表。（）完全二叉树一定是满二叉树，满二叉树一定是完全二叉树。（）一棵非空二叉树，其前序遍历序列和后序遍历序列正好相反，则该二叉树一定只有一个叶子结点。（）具有n个顶点的无向图，最多有n(n−邻接表存储结构只能用来存储有向图，不能存储无向图。（）哈希表的查找效率主要取决于装填因子，装填因子越大，查找效率越高。（）快速排序在初始序列有序或基本有序的情况下，时间复杂度最差，退化为O(n2直接插入排序是稳定的排序算法，希尔排序也是稳定的排序算法。（）四、简答题（本大题共5小题，每小题6分，共30分）计算下列两个程序段的时间复杂度，写出推导过程：

for(i=1;i<=n;i++)

for(j=1;j<=i;j++)

x++;

i=1;

while(i<=n)

i=i*2;设栈的输入序列为1,2,3,4,5，利用栈得到输出序列为3,2,5,1,4，请说明该输出序列是否合法，若合法写出操作过程（约定：push(x)表示将元素x入栈，pop()表示出栈，按操作顺序写出即可），若不合法说明理由。给定二叉树的结构如下：根结点为A，A的左孩子为B，右孩子为C；B的左孩子为D，右孩子为E；C的左孩子为F，右孩子为G；D、E、F、G均无左右孩子。请分别写出该二叉树的前序遍历序列、中序遍历序列、后序遍历序列。给定六个字符的权值分别为(1,3,5,7,9,12)，请画出构造哈夫曼树的过程，并计算该哈夫曼树的带权路径长度WPL。给定有向图的顶点集合为{v1,v2,

请写出从v1五、算法设计与综合应用题（本大题共2小题，第1小题10分，第2小题15分，共25分）给定一个带头结点的单链表，结点的C语言定义如下：

typedefstructLNode{

intdata;

structLNode*next;

}LNode,*LinkList;请设计一个算法，删除单链表中所有数据域值等于x的结点，要求算法空间复杂度为O(1)，时间复杂度不超过O(

typedefstructBiTNode{

intdata;

structBiTNode*lchild,*rchild;

}BiTNode,*BiTree;请设计一个递归算法，统计二叉树中叶子结点的个数，写出算法的完整实现代码，并分别说明算法的时间复杂度和空间复杂度。参考答案一、单项选择题（每小题2分，共20分）B解析：根据主定理，对于T(n)=aT(D解析：若第一个出栈元素为4，说明1、2、3已经全部入栈，栈顶元素为3，第二个出栈元素只能是3，不可能是2，因此该序列不可能。B解析：队列既可以用顺序存储也可以用链式存储，A错误；队列插入端为队尾，删除端为队头，C错误；循环队列需要解决队空队满的判定问题，D错误；B选项的计算公式正确。B解析：完全二叉树的深度公式为⌊log2n⌋+C解析：n个顶点的邻接矩阵是n×n的方阵，共n2个元素，无向图中每条边对应两个非零元素，因此非零元素共2B解析：哈夫曼树中，若有m个叶子结点，总结点数为2m−1，代入得2A解析：二叉排序树的定义要求任意结点的左子树所有结点小于根，右子树所有结点大于根，因此中序遍历一定得到升序序列，A正确；其他选项都是平衡二叉树的性质，二叉排序树不一定平衡，最坏情况查找时间复杂度为O(D解析：连通分量是无向非连通图中极大连通子图的定义，因此选D。B解析：第一次比较中点下标5对应元素56，21<56，调整右边界；第二次比较中点下标2对应元素19，21>19，调整左边界；第三次比较中点下标3对应元素21，查找成功，共比较3次，选B。B解析：大根堆要求堆顶元素是整个堆中的最大值，初始序列中最大值为85，因此堆顶为85，选B。二、填空题（每空1分，共15分）逻辑结构；存储结构（或物理结构）5；3O(1GDBFECA2k先序；层序n−1O(log2直接插入三、判断题（每小题1分，共10分）×解析：链式存储只要求逻辑结构连续，物理地址可以连续也可以不连续，因此错误。×解析：空格串是由空格组成的非空串，长度等于空格的个数，因此错误。√解析：栈只允许在一端插入删除，队列只允许队尾插入队头删除，都是操作受限的线性表，正确。×解析：满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树，因此错误。√解析：前序遍历顺序为根-左-右，后序为左-右-根，若序列相反，说明任意结点都不可能同时有左右子树，二叉树是一条斜树，只有一个叶子结点，正确。√解析：无向图中任意两个顶点之间最多一条边，总边数为组合数C(×解析：邻接表既可以存储有向图也可以存储无向图，存储无向图时每条边对应两个结点，因此错误。×解析：装填因子越大，哈希表中元素越密集，发生冲突的概率越高，查找效率越低，因此错误。√解析：快速排序每次划分选第一个元素为基准，有序情况下每次划分只能分出一个元素，递归深度为n，时间复杂度退化为O(×解析：希尔排序会将相同关键字分到不同组，可能改变相对位置，因此是不稳定排序，错误。四、简答题（每小题6分，共30分）（每小题3分，共6分）循环执行次数为1+2+3+设循环执行次数为k，循环结束条件为i=2k>n，即k（6分）该输出序列不合法，理由如下：第一个出栈元素为3，操作序列为push(1),push(2),push(3),pop()，得到第一个出栈元素3；第二个出栈元素为2，执行pop()得到第二个元素2，此时栈中剩余元素为[1]（栈底到栈顶）；第三个出栈元素为5，操作序列为push(4),push(5),pop()，得到第三个出栈元素5，此时栈中从栈底到栈顶依次为1、4，栈顶元素为4；按照输出序列要求，第四个出栈元素应为1，此时1被4压在栈底，不可能先出栈，因此该输出序列不合法。（每遍历序列2分，共6分）前序遍历序列：ABDECFG中序遍历序列：DBEAFCG后序遍历序列：DEBFGCA（构造过程3分，WPL3分，共6分）构造哈夫曼树的过程：所有叶子结点权值初始为[1,3,5,7,9,12]①取出两个最小权值1和3，合并得到新结点权值为1+3=4，剩余权值集合为[4,5,7,9,12]；②取出两个最小权值4和5，合并得到新结点权值为4+5=9，剩余权值集合为[7,9,9,12]；③取出两个最小权值7和9，合并得到新结点权值为7+9=16，剩余权值集合为[9,12,16]；④取出两个最小权值9和12，合并得到新结点权值为9+12=21，剩余权值集合为[16,21]；⑤合并16和21得到根结点，权值为37，构造完成。计算WPL：WP（每个序列3分，共6分）深度优先遍历序列：v1→v2→v五、算法设计与综合应用题（共25分）（10分）算法实现代码如下：

voiddeleteAllX(LinkList\&L,intx){

//L是带头结点的单链表，删除所有值为x的结点

LNode*p=L->next;//p指向当前遍历结点

LNode*pre=L;//pre指向p的前驱结点

while(p!=NULL){

if(p->data==x){

//找到值为x的结点，删除

pre->next=p->next;

free(p);

p=pre->next;

}else{

//未找到，指针后移

pre=p;

p=p->next;

}

}

}评分标准：思路正确得4分，指针处理正确得4分，满足空间复杂度O(1)和时间复杂度O(n)得2分，共10分。（15分）递归算法实现代码如下：

intcountLeaf(BiTreeT){

//统计二叉树T中叶子结点的个数，返回结果

if(T==NULL){

//空树，叶子结点数为0

return0;

}

if(T->lchild==NULL\&\&T->rchild==NULL){