2011-2012第1学期数据结构基础期末考卷2

《2011-2012第1学期数据结构基础期末考卷2》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、年级：_____________专业：_____________________班级：_________________学号：_______________姓名：__________________…………………………………………………………..装………………….订…………………..线………………………………………………………诚信应考考出水平考出风格浙江大学城市学院2011—2012学年第一学期期末考试试卷《数据结构基础》开课单位：计算分院；考试形式：闭卷；考试时间：2012年1月3日；所需时间：120分钟题序一二三四五六总分得分评卷人得

2、分一．选择题(本大题共15题，每题1分，共15分)1．从逻辑上可以把数据结构分成。A.动态结构和静态结构B.顺序组织和链接组织C.线性结构和非线性结构D.基本类型和组合类型2．执行下面程序段时，执行S语句的频度为。for(inti=1;i<=n;i++)for(intj=1;j<=i;j++)S;A.n2B.n2/2C.n(n+1)D.n(n+1)/23．若某线性表最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用下列存储方式最节省运算时间。A.单链表B.仅有指向表头指针的单循环链表C.双链表D.仅有指向表尾指针的单循环

3、链表4．带头结点的单链表L为空的判断条件是。A.L==NULLB.L->next==NULLC.L->next==LD.L!=NULL5．允许对队列进行的操作有。A.对队列中的元素排序B.取出最近入队的元素C.在队头元素之前插入元素D.删除队头元素6．在计算递归函数时，如不用递归过程，应借助于这种数据结构。A.线性表B.栈C.队列D.双向队列7．若用一个大小为6的一维数组来实现循环队列，且当前rear和front的值分别为0和3。当从队列中删除一个元素，再加入两个元素后，rear和front的值分别是()。A.4和2B.2和4C.1和5D

4、.5和18．在有n个结点的二叉树的二叉链表表示中，空指针数。A.不定B.n+1C.nD.n-19．设x和y是二叉树中的任意两个结点，若在先序遍历中x在y之前，而在后序遍历中x在y之后，则x和y的关系是。A.x是y的左兄弟B.x是y的右兄弟C.x是y的祖先D.x是y的子孙10．设森林F中有三棵树，第一、第二和第三棵树的结点个数分别为m1、m2和m3，则与森林F对应的二叉树根结点的右子树上的结点个数是。A.m1B.m1+m2C.m3D.m2+m311．深度为5的二叉树至多有_______个结点.A.31B.32C.33D.1612．在一个有向

5、图的邻接表中，每个顶点单链表中结点的个数等于该顶点的_________。A.出边数B.入边数C.度数D.度数减１13．对某个无向图的邻接矩阵来说，下列叙述错误的是。A.第i行与第i列上的非零元素的总数等于顶点vi的度数B.矩阵中的非零元素个数等于图中的边数的2倍C.第i行上的非零元素个数和第i列上的非零元素个数一定相等D.矩阵是一个n×n的方阵（n为图的顶点数）14．在一个具有n个顶点的有向完全图中，所含的边数为_________。A.nB.n(n-1)C.n(n-1)/2D.n(n+1)/215．对于，从它的某个顶点出发进行一次深度或广

6、度优先搜索就可以访问到该图的每一个顶点。A.无向图B.有向图C.无向连通图D.任何一个图得分二．填空题(本大题共20空，每空1分，共20分)1．数据结构是相互之间存在一种或多种特定关系的数据元素的集合，它包括3方面的内容，分别是数据的逻辑结构、⑴和操作（运算）。2．n个元素的线性表，采用顺序存储结构，插入一个元素要平均移动表中⑵个元素，删除一个元素要平均移动表中⑶个元素。3．已知指针P指向单链表中的结点，后继指针域为next，则在P指向结点后插入S指向结点的语句为：⑷；⑸。4．顺序表中逻辑上相邻的元素物理位置⑹相邻，单链表中逻辑上相邻的元

7、素物理位置⑺相邻。5．设栈S的初始状态为空，队列Q的初始状态如图所示：___________________________________________a1a2a3a4___________________________________________↑队头↑队尾对栈S和队列Q进行以下两步操作：（1）删除Q中的元素，将删除的元素插入栈S，直到Q为空（2）依次将栈S中的元素插入Q，直到S为空在上述两步操作后，队列Q的状态是⑻。6．如果对完全二叉树中结点从1开始按层进行编号，设最大编号为n；那么，可以断定编号为i(i>1)的结点的父结点

8、编号为⑼；所有编号满足⑽的结点为叶子结点。7．有三个结点组成的二叉树共有⑾种不同的结构形态。深度为5的完全二叉树至少有⑿个分支结点。8．n个顶点的有向强连通图至少有⒀条边。若一个无向图有10条