09级数据结构试卷(B)20120520

2011—2012学年第2学期闽江学院考试试卷考试课程：数据结构试卷类别：A卷口E卷丁 考试形式：闭卷丁开卷口适用专业年级：09级地理信息系统，09级资源环境得分O班级 姓名 学号O题号-——-二四五八七八九十总分得分…、选择题（每小题1分，共10分）10%1、带权有向图G用邻接矩阵A存储，则顶点i的人度等于A中（A、A、第i行非°°的元素之和第i列非R的元素之和C、C、第i行非8且非0的元素个数D、第i列非R且非0的元素个数2、一个栈的输入序列为12345,则下列序列中不可能是栈的输出序列的是（）。A、23415B.54132C、23145D.154323、 对二叉树从1开始进行连续编号，要求每个结点的编号大于其左右孩子的编号，同一个结点的左右孩子中，其左孩子的编号小于其右孩子的编号，则可采用（）遍历实现编号。A、无序 E、中序 C、后序 D、前序4、 在长度为n的顺序表的第i个位置上插入一个元素（1<iWn+1）,元素的移动次数为A、n-i+1B>n_i C、i D、i-15、 已知一个有向图的邻接矩阵表示，要删除所有从第i个结点发出的边，应该（）。A、将邻接矩阵的第i行删除E、将邻接矩阵的第i行元素全部置为0C、将邻接矩阵的第i列删除D、将邻接矩阵的第i列元素全部置为06、 线性表是具有n个（ ）的有限序列（n〉0）oA.表元素B.字符C.数据元素D.数据项7、 链表不具有的特点是（ ）。A.插入、删除不需要移动元素B.可随机访问任一元素C.不必事先估计存储空间D.所需空间与线性长度成正比8、 对于栈操作数据的原则是（ ）。A.先进先出B.后进先出C.后进后出D.不分顺序9、 最大容量为n的循环队列，队尾指针是rear,队头是front,则队空的条件是（）。A.（rear+1）MODn二frontB.rear=frontC.rear+l=frontD.(rear-1)MODn二front10、设广义表L二((a,b,c)),贝此的长度和深度分别为( )。A.1和1E.1和3C.1和2D.2和3二、填空题(每小题2二、填空题(每小题2分，共30分)30%得分1、假设用循环单链表实现队列，若队列非空，且队尾指针为R,则将新结点S加入队列时,需执行下面语句： ； ；R=S；o2、 一定能够对 图所有结点进行拓扑排序。3、 有n个顶点的无连通图至少有 条边。4、 序列可以唯一决定一棵的二叉树。5、 图的广度优先搜索类似于树的 次序遍历。。6、 设有一个链表头结点为first的单链表，设指针域为next。填充算法，通过遍历一趟链表，将链表中所有结点按逆序链接。LinkReverse(Linkfirst)/*link为结点指针类型，函数值返回链表头*/{Linkp,q;if( )rerurnNULL;p=first—〉next;TOC\o"1-5"\h\zfirst_〉next二 ;while(p!=NULL){q= ；p->next二 ;first—〉next二p;P=q；}return ;}7、 已知二维数组A[10][20]采用行序为主方式存储，每个元素占2个存储单元，并且A[0][0]的存储地址是1024,则A[6][18]的地址是 o8、 通常是以算法执行所耗费的 和所占用的 来判断一个算法的优劣。9、 将一棵有100个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点编号为1,则编号最大的非叶结点的编号为 三、判断题（每小题1分，对的打“V7错的打“X”共5分）5%1、处理的数据有相同的逻辑和存储结构，那么设计出来的算法相同。（）2、 中序遍历一棵一叉排序树，必定得到一个关键字值的有序序列。（）3、 用邻接矩阵存储图，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中结点个数有关，而与图的边数无关。（）4、 一个无向连通图的生成树是一个极大的连通子图。（）5、 用循环链表作为存储结构的队列就是循环队列。（）得分四、简答题（每小题4分，共20分）20%得分1、给出下列稀疏矩阵的行三元组表示。TOC\o"1-5"\h\z_3 0 0 2 0 0_0 0 6 0 0 80 0 0 0 0 07 0 0 0 0 00 0 0 1 0 50 0 0 0 4 02、计算模式串P="aabaabac”的next[]的值。j12345678PaabaabacNext[j]3、画出下图中的二叉树所对应的树或森林。4、已知一个图的顶点为A、E、C、D,其邻接矩阵的上三角元素（包括主对角线元素）全为0,其他元素均为1。请画出该图，并给出其邻接表。5、在一般的顺序队列中，什么是假溢出？怎样解决假溢出问题?五、解答题（共20分）20% 得分1、（5分）已知中序序列为DGBAECF,后序序列为GDBEFCA。请画出对应的构造二叉树。2、（10分）已知下列AOE网络，请给出每个事件ai最早开始时间ei及最迟开始时间li和关键路径。=1an=4a3=53-5=a8=ai=6io=1an=4a3=53-5=a8=ai=6io=2a2=4且9二4得分个算法判断两棵二叉树是否相似,所谓二叉树六、算法设计题（每小题7分，1、假设二叉树采用二叉链存储结构,设计t1和t2是相似的指的是t1和t2都是空的二叉树；或者t1和t2的根结点是相似的,以及t1的左子树和t2