厦门理工学院12级数据结构期末试卷与答案

第1页共5页考生信息栏系专业级班级姓名学号装订线厦门理工学院试卷2012－2013学年第一学期课程名称数据结构与算法试卷卷别A■B□专业2011级班级考试方式闭卷■开卷□本试卷共四大题(4页)，满分100分，考试时间120分钟。请在答题纸上作答，在试卷上作答无效。一、选择题：（本题共20小题，每题2分，共40分）1、链式存储的存储结构所占存储空间（）。A．分两部分，一部分存放结点的值，另一部分存放表示结点间关系的指针B．只有一部分，存放结点的值C．只有一部分，存储表示结点间关系的指针D．分两部分，一部分存放结点的值，另一部分存放结点所占单元素2、已知一个顺序存储的线性表，设每个结点占m个存储单元，若第一个结点的地址为B，则第i个结点的地址为（）。A．B+(i-1)*mB．B+i*mC．B-i*mD．B+(i+1)*m3、两个指针P和Q，分别指向单链表的两个元素，P所指元素是Q所指元素前驱的条件是（）。A．P-next==Q-nextB．P-next==QC．Q-next==PD．P==Q4、下面关于线性表的叙述中，错误的是（）关系。A．顺序表必须占一片地址连续的存储单元B．顺序表可以随机存取任一元素C．链表不必占用一片地址连续的存储单元D．链表可以随机存取任一元素5、等概率情况下，在有n个结点的顺序表上做插入结点运算，需平均移动结点的数目为（）。A．nB．(n-1)/2C．n/2D．(n+1)/26、设数组data[m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出队操作后其头指针front值为（）。A．front=front+1B．front=(front+1)%(m-1)C．front=(front-1)%mD．front=(front+1)%m□第2页共5页7、下列算法的时间复杂度是（）。for(i=0;in;i++)for(j=0;jn;j++)c[i][j]=i+j;A.O（1）B.O（n）C.O（log2n）D.O（n2）8、从一个栈顶指针为top的链栈中删除一个结点时，用x保存被删除的结点的值，应执行下列()命令。A．x=top;top=top-next;B．top=top-next;x=top-data;C．x=top-data;D．x=top-data;top=top-next;9、经过下列栈的运算后，x的值是（）。InitStack(s)（初始化栈）;Push(s,a);Push(s,b);ReadTop(s);Pop(s,x);A．aB．bC．1D．010、一个栈的入栈次序ABCDE，则栈的不可能的输出序列是()。A．EDCBAB．DECBAC．DCEABD．ABCDE11、设某棵二叉树中有2000个站点，则该二叉树的最小高度为（）。A、9B、10C、11D、1212、若用一个大小为6的数组来实现循环队列，且当前front和rear的值分别为3和0，当从队列中删除一个元素，再加入两个元素后，front和rear的值分别为()。A．5和1B．4和2C．2和4D．1和513、根据二叉树的定义，具有3个结点的二叉树有（）种树型。A．3B．4C．5D．614、如右图所示的二叉树，后序遍历的序列是（）A．A、B、C、D、E、F、G、H、IB．A、B、D、H、I、E、C、F、GC．H、D、I、B、E、A、F、C、GD．H、I、D、E、B、F、G、C、A15、下列陈述正确的是（）。A．二叉树是度为2的有序树B．二叉树中结点只有一个孩子时无左右之分C．二叉树中必有度为2的结点D．二叉树中最多只有两棵子树，且有左右子树之分16、在有n个叶子结点的哈夫曼树中，非叶子结点的总数是（）。Ａ．n-1Ｂ．nＣ．2n-1Ｄ．2nABADECFGHI第3页共5页17、对于一个具有n个顶点的有向图的边数最多有（）。A．nB．n(n-1)C．n(n-1)/2D．2n18、对于一个具有n个顶点和e条边的无向图，采用邻接表表示，则表头向量大小为（）。A．n-1B．n+1C．nD．n+e19、下面关于图的存储结构的叙述中正确的是（）。A．用邻接矩阵存储图，占用空间大小只与图中顶点数有关，而与边数无关B．用邻接矩阵存储图，占用空间大小只与图中边数有关，而与顶点数无关C．用邻接表存储图，占用空间大小只与图中顶点数有关，而与边数无关D．用邻接表存储图，占用空间大小只与图中边数有关，而与顶点数无关20、二叉树为二叉排序树的（）条件是其任一结点的值均大于其左孩子的值，小于其右孩子的值。A．充分不必要B．必要不充分C．充分必要D．既不充分也不必要二、分析运算题（本题共6小题，每题5分，共30分）1、如果输入序列为123,先进入栈结构后进入队列结构，试写出所有的出队列序列。2、假设一棵二叉树的前序(先序)遍历序列为ABDECF和中序序列为DBEAFC，画出二叉树并写出后序遍历序列。图1图2图33、用二叉树表示算术表达式如图1所示。①按图画出对应的算术表达式②写出后序（后缀）表达式4、请写出有向图2中顶点1-6的入度和出度。5、给定一组项及其权值，假定项都存放于二叉树的树叶结点，则具有最小带权外部路径长度的树称为huffman(赫夫曼)树。给定项及相应的权如下表：画出相应的huffman树。序号123456789项ABCDEFGHI权值15671225461156、已经邻接矩阵如图3所示，判断该图是有向图还是无向图，用顶点1-6画出该图。第4页共5页三、程序填空题（本题共5空，每空2分，共10分）1、下面程序段的功能是在单链表中查找元素数据x，若找到，返回指向该结点的指针；否则返回空指针，请在下划线处填上正确的内容。//在单链表L中查找元素xtypedefstructLNode{DataTypedata;structLNode*next;}LNode,*LinkList;LinkListFind(LinkListL,DataTypex){p=L-next;//L为带头节点的单链表while(（1）){if(p-data==x)returnp;//找到x（2）}returnNULL;//未找到}2、下面程序段的功能实现删除队列中的队头数据（若队列不空），并用x返回其值，要求在下划线处填上正确的语句。typedefstructQNode{DataTypedata;structQNode*next;}QNode,*QueuePtr;typedefstructLQ{QueuePtrfront;QueuePtrrear;}LinkQueue;intDeQueue(LinkQueue&Q,DataType&x){if(（3）)returnERROR;p=Q.front-next;x=p-data;（4）if(Q.rear==p)（5）free(p);returnOK;}线订装第5页共5页考生信息栏系专业级班级姓名学号装订线四、算法设计题（本题共2小题，共20分）1、（10分）已知一个顺序表，每个元素都是整数，试设计用最少时间把所有值为负数的元素移动到全部正数值元素前面的算法。typedefstruct{int*elem;intlength;intlistSize;}sqlist;2、（10分）以二叉链表为存储结构，编写计算二叉树中叶子结点数目的递归函数。typedefstructBiTNode{intdata;structBiTNode*lchild,*rchild;}BiTNode,*BiTree;第6页共5页数据结构与算法A卷答案12-13学年第一学期一、选择题：（本题共20小题，每题2分，共40分）1-5：AABDC6-10：DDDBC11-15：CBCDD16-20：ABCAB二、分析运算题（本题共6小题，每题5分，共30分）(1)如果输入序列为123,先进入栈结构后进入队列结构，试写出所有的出队列序列。输出序列123（1分）输出序列132（1分）输出序列213（1分）输出序列231（1分）输出序列321（1分）输出序列312（扣3分）(2)假设一棵二叉树的前序(先序)遍历序列为ABDECF和中序序列为DBEAFC，画出二叉树并写出后序遍历序列。①（3分）②后序遍历：DEBFCA（2分）(3)用二叉树表示算术表达式如图1所示。①按图画出对应的算术表达式②写出后序（后缀）表达式算术表达式：(a+b+c*(d+e)+f)*(g+h)（2分）后序表达式：ab+cde+*+f+gh+*（3分）(4)请写出有向图2中顶点1-6的入度和出度1:入度：3出度：02:入度：2出度：23:入度：1出度：24:入度：1出度：35:入度：2出度：16:入度：2出度：3(入度2.5分，出度2.5分)第7页共5页(5)给定一组项及其权值，假定项都存放于二叉树的树叶结点，则具有最小带权外部路径长度的树称为huffman(赫夫曼)树。给定项及相应的权如下表：画出相应的huffman树。(5分)(6)已经邻接矩阵如图3所示，判断该图是有向图还是无向图，用顶点1-6画出该图。有向图（2分）（3分）三、程序填空题（本题共5空，每空2分，共10分）(1)：p!=NULL(2)：p=p-next;(3):Q.front==Q.rear(4):Q.front-next=p-next;(5):Q.rear=Qfront;四、算法设计题（本题共2小题，共20分）1、（10分）算法如下：voidmove(sqlistL)91385323281113515I1H4F6B12D25E6G7C15A第8页共5页{inti=0,j=L.lenght-1,k;1分inttemp;while(ij)1分{while(L.elem[i]=0)i++;2分while(L.elem[j]=0)j--;2分if(ij)1分{temp=L.elem[i];L.elem[i]=L.elem[j];L.elem[j]=temp;3分}}}注：算法执行次数（时间）比给定算法更多，不得超过6分。2、算法如下：intleaf(BiTreeT)1分{if(T==NULL)1分return0;2分elseif(T-lchild==NULL&&T-rchild==NULL)2分return1;2分elsereturn(leaf(T-lchild)+leaf(T-rchild));2分}