数据结构期末试题与答案

第1页，共6页仲恺农业工程学院试卷（答案及评分标准）《数据结构与算法》2011至2012学年度第2学期期末（A）卷专业班级姓名学号（考生注意：考试时间为120分钟。答案须写在答题纸上，并注明题号，考试结束后将试卷连同答题纸一齐交）一、选择题（每小题选出一个最合适的答案，共30分）1、在以单链表为存储结构的线性表中，数据元素之间的逻辑关系用（C）A．数据元素的相邻地址表示B．数据元素在表中的序号表示C．指向后继元素的指针表示D．数据元素的值表示2、线性表采用链式存储时，结点的存储地址（B）A．必须是不连续的B．连续与否均可C．必须是连续的D．和头结点的存储地址相连续3、设数组data[m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出队操作后其头指针front值为（D）A．front=front+1B．front=(front+1)%(m-1)C．front=(front-1)%m题号一二三四五六七八合计得分评卷人第2页，共6页D．front=(front+1)%m4、设有一个顺序栈S，元素s1，s2，s3，s4，s5，s6依次进栈，如果6个元素的出栈顺序为s2，s3，s4，s6，s5，s1，则顺序栈的容量至少应为多少（C）A．1B．2C．3D．45、栈和队列都是（A）A．限制存取位置的线性结构B．顺序存储的线性结构C．链式存储的线性结构D．限制存取位置的非线性结构6、现有一“遗传”关系：设x是y的父亲，则x可以把它的属性遗传给y。表示该遗传关系最适合的数据结构为（B）A．线性表B．树C．图D．二叉树7、下列陈述中正确的是（D）A．二叉树是度为2的有序树B．二叉树中结点只有一个孩子时无左右之分C．二叉树中必有度为2的结点D．二叉树中最多只有两棵子树，并且有左右之分8、在具有n个叶子结点的严格二叉树（即结点的度要么是0要么是2）中，结点总数为（C）A．2n+1B．2nC．2n-1D．2n-29、N个顶点的有向完全图中含有有向边的数目最多为（D）A．N-1B．NC．N(N-1)/2D．N(N-1)10、在含n个顶点和e条边的无向图的邻接矩阵中,零元素的个数为（D）A．eB．2eC．n2－eD．n2－2e二、填空题（每小题4分，共20分）1、栈顶的位置是随着进栈和出栈操作（栈操作）而变化的。2、对于单链表形式的队列，其空队列的front指针和rear指针都等于头结点的地址。第3页，共6页3、n个记录的折半查找，若查找失败，进行了[log2n]+1次比较。4、从顺序表中删除一个元素时，表中所有在被删元素之后的元素均需向前移动一个位置。5、在队列中，允许进行插入操作的一端称为队尾，允许进行删除操作的一端称为队头。三、给出线性表的单链表存储结构，并实现用e返回线性表中第i个元素的值（即编写完整的函数GetElem(L,i,e)，这里只给出函数的名称和参数名，未给出类型）。（10分）typedefstructLNode{ElemTypedata;structLNode*next;}LNode,*LinkList;StatusGetElem(LinkListL,inti,ElemType&e){LinkListp;intj;p=L-next;j=1;while(p&&ji){p=p-next;++j;}if(!p||ji)returnERROR;e=p-data;returnOK;}四、给出单链队列的存储结构（数据类型名为LinkQueue），下面是入队函数，但有缺漏，请补全（说明在哪一行补什么内容）。（10分）第4页，共6页StatusEnQueue(LinkQueueQ,e){p=newQNode;if(!p)return0;p—data=e;Q.rear—=p;return1;}typedefstructQNode{QElemTypedata;structQNode*next;}QNode,*QueuePtr;typedefstruct{QueuePtrfront;QueuePtrrear;}LinkQueue;StatusEnQueue(LinkQueue&Q,QElemTypee){QueuePtrp;p=newQNode;if(!p)return0;p-data=e;p-next=NULL;Q.rear-next=p;Q.rear=p;return1;}五、给出二叉树的三叉存储结构，若二叉树后序遍历的序列为BDECA，请画出该二叉树。（10分）typedefstructTrTNode{TElemTypedata;structTrTNode*lchild,*rchild,*parent;第5页，共6页}TrTNode,*TrTree;六、假设通信电文使用的字符集为{a,b,c,d,e,f}，名字符在电文中出现的频度分别为：34，5，12，23，8，18，试为这6个字符设计哈夫曼编码。请先画出你所构造的哈夫曼树(要求树中左孩子结点的权值小于右孩子结点的权值)，然后分别写出每个字符对应的编码。（10分）a:11第6页，共6页b:1010c:100d:01e:1011f:00七、给出图的邻接多重表的存储结构，并说明其主要适用于存储何种图。（10分）typedefstructEBox{VisitIfmark;intivex,jvex;structEBox*ilink,*jlink;InfoType*info;}EBox;typedefstructVexBox{VertexTypedata;EBox*firstedge;}VexBox;typedefstructVexBox{VexBoxadjmulist[Max_VERTEX_NUM];intvexnum,edgenum;}AMLGraph;这个结构主要适用于存贮无向图