资源描述：
《华东交通大学2010-2011_数据结构试卷》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、一、选择题(每题2分，共30分)1.计算机算法指的是（）。A．计算方法B.排序方法C.解决问题的步骤序列D.调度方法2．算法的计算量的大小称为计算的（）。A．效率B.复杂性C.现实性D.难度3.在下面的程序段中，对x的赋值语句的频度为（）FOR（i=1；i≤n；++i）FOR（j=1；j≤n；++j）x:=x+1;A．O(2n)B．O(n)C．O(n2)D．O(log2n)4.线性表是具有n个（）的有限序列（n>0）。A．表元素B．字符C．数据元素D．数据项E．信息项5.在单链表指针为p的结点之后插入指针为s
2、的结点，正确的操作是：（）。A．p->next=s;s->next=p->next;B．s->next=p->next;p->next=s;C．p->next=s;p->next=s->next;D．p->next=s->next;p->next=s;6.在循环队列中用数组A[0..m-1]存放队列元素，其队头和队尾指针分别为front和rear，则当前队列中的元素个数是（）A．(front-rear+1)%mB.(rear-front+1)%mC．(front-rear+m)%mD.(rear-front+
3、m)%m7.栈和队都是（）A．顺序存储的线性结构B.链式存储的非线性结构C.限制存取点的线性结构D.限制存取点的非线性结构8.某堆栈的输入序列为a,b，c，d,下面的四个序列中，不可能是它的输出序列的是（）。A.a，c，b，dB.b,c，d，aC.c,d，b,aD.d,c，a，b9.广义表A=(a,b,(c,d),(e,(f,g))),则下面式子的值为（）。Head(Tail(Head(Tail(Tail(A)))))A.(g)B.(d)C.cD.d10．在数组A中，每一个数组元素A[i][j]占用3个存储字
4、，行下标i从1到8，列下标j从1到10。所有数组元素相继存放于一个连续的存储空间中，则存放该数组至少需要的存储字数是（）。A.80B.100C.240D.27011.若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（）A．9B．11C．15D．不确定12.在有n个结点的二叉链表中，值为非空的链域的个数为()A．n-1B．2n-1C．n+1D．2n+113.由权值分别为11，8，6，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（）A.24B.71C.48D.5314．下列哪一种
5、图的邻接矩阵是对称矩阵（）A．有向图B．无向图C．AOV网D．AOE网15.采用顺序查找方法查找长度为n的顺序表时，搜索成功的平均搜索长度为（）。A.nB.n/2C.(n-1)/2D.(n+1)/2二、填空题(每题2分，共20分)1.数据结构中评价算法的两个重要指标是。2.一个长度为n的顺序表中第i个元素（1<=i<=n）之前插入一个元素时，需向后移动______个元素。3.链接存储的特点是利用来表示数据元素之间的逻辑关系。4.INDEX（‘DATASTRUCTURE’，‘STR’）=5.两个字符串相等的充分
6、必要条件是。6.一棵具有257个结点的完全二叉树，它的深度为。7.一棵完全二叉树有900个结点，则共有个叶子结点。8.由一棵二叉树的前序序列和唯一确定这棵二叉树。9.已知一无向图G=（V，E），其中V={a,b,c,d,e}E={(a,b),(a,d),(a,c),(d,c),(b,e)}现用某一种图遍历方法从顶点a开始遍历图，得到的序列为abecd，则采用的是__遍历方法。10.对于一个具有n个顶点和e条边的连通图，其生成树的边数为。四、应用题（每题8分，共4０分）１.请读下列程序，该程序是在单链表中删除一
7、个结点的算法，为空出的地方填上正确的语句。（8分）voiddemo2(LinkListhead,ListNode*p){//head是带头结点的单链表，删除P指向的结点ListNode*q=head;while(q&&)q=q->next;（2分）if(!q)Error(“*pnotinhead”);；（3分）；（3分）}2.已知一棵二叉树的前序遍历的结果是ABECDFGHIJ,中序遍历的结果是EBCDAFHIGJ,试画出与其对应的二叉树并中序线索化（6分），并给出这棵二叉树的后序遍历序列(2分)。3．将下面
8、的森林变换成二叉树（8分）。4．已知带权无向图，求解下列问题：1)写出它的邻接矩阵。（2分）2)用普里姆算法求出最小生成树，要求从顶点1出发，并给出在构造最小生成树过程。(6分)解：邻接矩阵为：最小生成树为：5.下图所示的AOE网络(1)给出全部的拓扑排序。（2分）(2)这个工程最早可能在什么时间结束和关键路径。（3分）(3)求每个事件的最早开始时间Ve[i]和最迟开始时间Vl[i]。（3分）解：(
