2019-2020(1)数据结构B卷 - 副本

B)B)head=NULLD)head!=NULL江酉理工大学考试试卷试卷墙号， (A、B、C),共3大題2019_-2020学年第1学期课程名称： 费建构考试性质：［正考/补考］考试方式：［开卷/闭卷］适用专业班级: 考试时间： 年 月 日时段 (100彻)温馨提示本试卷的所有解答均应写在答题纸的指定位置，否则无效。一、 选择题(共10小题，每小题3分，共计30分)1、 下面程序片段的时间复杂度是 .X=2;while(x<n/2)x=2♦x;OClo&n)B)0(n)C)0(nlog»n)D)0(n32、 在双链表中向p所指的结点之前插入一个结点q的操作是 ・p->prior=q;q->next=p;p->prior->next=q;q->prior=p->prior;q->prior=p->prior:p->prior->next=q:q->next=p;p->prior=q->next:q->next=p;p->next=q;q->prior->next=q;q->next=p;p->prior->next=q;q->next=p;q->prior=p->prior;p->prior=q;3、 对于一个头指针为head的不带头结点的单链表，判定该表为空的条件是—・A)head->next=NULLC)head->next=head4、 若元素a,b,c,d,e,f依次进栈，允许进栈、出栈操作交替进行，则不可能得到的出栈序列是 ・A)fedcbaB)bcafedC)dcefbaD)cabdef5、 若一棵二叉树的前序遍历序列和后序遍历序列分别为1,2,3,4和4,3,2,1则该二叉树的中序遍历序列不会是 ・A)1,2,3,4B)2,3,4,1C)3,2,4,1D)4,3,2,16、 若X是后序线索二叉树中的叶子结点，且X存在左兄弟结点Y,则X的右线索指向的是 ・A)X的父结点 B)以Y为根的子树中最左下结点0X的左兄弟结点Y D)以Y为根的子树中最右下结点7、 将森林F转换为对应的二叉树T,F中叶子结点的个数等于 ・A)T中叶子结点的个数 B)T中度为1的结点个数0T中左孩子指针为空的结点个数 D)T中右孩子指针为空的结点个数8、 以下关于图的叙述中，正确的是 ・强连通有向图的任何顶点到其他所有顶点都有弧图的任意顶点的入度等于出度0有向完全图一定是强连通有向图D)有向图边集的子集和顶点集的子集可构成原有向图的子图9、 无向图G=(V,E),其中V={a,b,c,d,e,f},E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)}.对该图进行深度优先遍历，下面不能得到的序列是 。 A)acfdebB)aebdfcC)aedfcbD)abecdf10、 以下叙述中正确的是 ・只要无向流通图中没有权值相同的边，则其最小生成树唯一只要无向图中有权值相同的边，则其最小生成树一定不唯一三、综合题（共5小题，每小题10分，共计50分）1三、综合题（共5小题，每小题10分，共计50分）1、 设L为带头结点的单链表，编写算法实现从尾到头反向输出每个结点的值。2、 设计算法求二叉树的深度。template<classDataType>intBiTree<DataType>::Depth（BiNode<DataType>奉bt）｛D）连通图G有n个顶点，含有n个顶点n-1条边的子图一定是G的生成树二、填空题（共10小题，每小题2分，共计20分）1、 对于顺序表，在第i个位置插入一个元素的时间复杂度为 。2、 在长度为n的顺序表中删除第i（IWiWn）个元素时，需要向前移动 个元素。3、 元素a,b,c,d,e依次进入初始为空的栈中，若元素进栈后可停留、可出栈，3、 对给定的一组权值W=（5,2,9,11,8,3,7）,试构造相应的哈夫曼树，并计算它的带权路径长度。3、 对给定的一组权值W=（5,2,9,11,8,3,7）,试构造相应的哈夫曼树，并计算它的带权路径长度。4、 写出下面二叉树的前序、中序和后序序列，并把它转换为森林。4、 设栈初始为空，将中綴表达式a*b+（cT/e）*f转为后綴表达式的过程中，当扫描到e时，运算符栈中的元素依次（栈顶至栈底）是 ・5、 在一棵度为4的树T中，若有20个度为4的结点，10个度为3的结点，1个度为2的结点，10个度为1的结点，则树T的叶子结点个数是 ―.6、 已知一棵完全二叉树的第6层（设根为第1层）有8个叶子结点，则该完全二叉树的结点个数最少是 .7、 若对右图所示的二叉树进行中序线索化，则结点X的右线索指向的结点是 ・5、设无向图G=（V,E）的邻接矩阵存储如图所示，画出图G及其邻接表存储（边表序号从小到大排列，顶点以数字1,2,3,4,5表示）。85、设无向图G=（V,E）的邻接矩阵存储如图所示，画出图G及其邻接表存储（边表序号从小到大排列，顶点以数字1,2,3,4,5表示）。9、 一个有28条边的非连通无向图至少有 个顶点。010101010110、 一个具有n个顶点的无向连通图，其边数至少为 。0101010101答题纸第答题纸第I ■共2页，阅卷 江酉理工大学考试试卷答题纸试卷编号， (A，阅卷 江酉理工大学考试试卷答题纸试卷编号， (A、B、C),共_ 大題2019 2020学年第1学期考试性员：［正考/补考］课程名称:數据結构考试方式：［开卷/闭卷］温V请考生自觉遵守考试乜律，争做文明诚卡照《江西理工大学学生违纪处分规定〉处理。E示f的大学生。如有违犯考试乜律，将尸格按题号—二三总分得分一、选择题（共10小题，每小題3分，共30分）。得分 ，阅者 二、填空題（共10小题，每小題2分，共计20分）。得分 ,阅卷 10(n)6392n-i7A348694/-(+9958210n-1三、综合题(共5小题，每小题10分，共计50分)。得分 说明：可在反面作答•1〃参见实验指导P23算法2-4template<classDataType>voidLinkList<DataType>::Reverse()(Node<DataType>”=first->next;Node<DataType>*pre=NULL;Node<DataType>*r=NULL;while(p!=NULL)(r=p->next:p->next=pre;pre=p；P=r;)first->next=pre;PrintListO；)〃头插法，参见实验指导P25算法2-6template<classDataType>voidLinkList<DataType>::Reversel0(Node<DataType>*p=first->next;first->next=NULL;Node<DataType>*u=NULL;while(p!=NULL)(答题纸第答题纸第2页，共2页u=p->next;p->next=first->next;first->next=p;P=u;}PrintList();2template<classDataType>intBiTree<DataType>::Depth(BiNode<DataType>*bt)(if(!bt)returnO;//bt=