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

《09级数据结构试卷(b)20120520》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、2011—2012学年第2学期闽江学院考试试卷考试课程：数据结构试卷类别：A卷口B卷V考试形式：闭卷V开卷口适用专业年级：09级地理信息系统，09级资源环境班级姓名学号rws题号*ia三四五六七A九十总分得分1、选择题（每小题1分，共10分）10%得分带权有向图G用邻接矩阵A存储，则顶点i的人度等于A中（）。A、第i行非…的元素之和B、第i列非…的元素之和C、第i行非°°且非0的元素个数D、第i列非°°且非0的元素个数2、一个栈的输入序列为12345,则下列序列中不可能是栈的输出序列的是（）。A、23415B>54132C、23145D、154323、对二叉树

2、从1开始进行连续编号，要求每个结点的编号大于其左右孩子的编号，同一个结点的左右孩子中，其左孩子的编号小于其右孩子的编号，则可采用（）遍历实现编号。A、无序B、中序C、后序I）、前序4、在长度为n的顺序表的第i个位置上插入一个元素（1

3、符C.数据元素D.数据项7、链表不具有的特点是（）。A.插入、删除不需要移动元素B.可随机访问任一元素C.不必事先估计存储空间D.所需空间与线性长度成正比8、对于栈操作数据的原则是（）。A.先进先出B.后进先出C.后进后出D.不分顺序9、最大容量为n的循环队列，队尾指针是rear,队头是front,则队空的条件是（A.（rear+1）MODn=frontB.rear=front)0C.rear+l=frontD.(rear-1)MODn=front10、设广义表L=((a，b，c)),则L的长度和深度分别为(A.1和1B.1和3C.1和2D.2和3二、填空题(

4、每小题2分，共30分)30%得分1、假设用循环单链表实现队列，若队列非空，且队尾指针为R，则将新结点S加入队列时，需执行下而语句：；；R=S;。2、一定能够对图所右结点进行拓扑排序。3、有n个顶点的无连通图至少有条边。4、序列可以唯一决定一棵的二叉树。5、图的广度优先搜索类似于树的次序遍历。。6、设有一个链表头结点为first的单链表，设指针域为next。填充算法，通过遍历一趟链表，将链表中所有结点按逆序链接。LinkReverse(Linkfirst)/*link为结点指针类型，函数值返回链表头*/{Linkp,q;if()rerurnNULL;p=firs

5、t->next;first->next=;while(p!=NULL){;p->next=;first.->nGxt=p;p=q;}return;}7、已知二维数组A[10][20]采用行序为主方式存储，每个元素占2个存储单元,并且A[0][0]的存储地址是1024,则A[6][18]的地址是。8、通常是以算法执行所耗费的和所占用的来判断一个算法的优劣。9、将一棵有100个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编得分3、画出下图中的二叉树所对应的树或森林。号，根结点编号为1，则编号最大的非叶结点的编号为_三、判断题（每小题1分，对的打“V

6、”，错的打“X”共5分）5%1、处理的数据有相同的逻辑和存储结构，那么设计出來的算法相同。（）2、中序遍历一棵二叉排序树，必定得到一个关键字值的有序序列。（）3、用邻接矩阵存储图，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中结点个数有关，而与图的边数无关。（）4、一个无向连通图的生成树是一个极大的连通子图。（）5、用循环链表作为存储结构的队列就是循环队列。（）四、简答题（每小题4分，共20分）20%得分1、给出下列稀疏矩阵的行三元组表示。•J12345678PaabaabacNext[j]2、计算模式串P=“aabaabac”的next□的值。5、在

7、一般的顺序队列中，什么是假溢出？怎样解决假溢出问题?4、己知一个图的顶点为A、B、C、D,其邻接矩阵的上三角元素（包括主对角线元素）全为0,其他元素均为1。请画出该图，并给出其邻接表。五、解答题（共20分）20%得分1、（5分）已知中序序列为DGBAECF，后序序列为GDBEFCA。请画出对应的构造二叉树2、（10分）己知下列A0E网络，请给出每个事件ai最早开始时间ei及最迟开始时间li和关键路径。3、（5分）写出下图的邻接表及以1开始的深度优先和广度优先遍历顶点序列。O5六、算法设计题（每小题7分，共14分）得分1、假设二叉树采用二叉链存储结构,设计一个算

8、法判断两棵二叉树是否相似，所谓二叉树t