北京师范大学12-13-数据结构试卷-A+答案

《北京师范大学12-13-数据结构试卷-A+答案》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、北京师范大学2012～2013学年第1学期期末考试试卷（A卷）课程名称：数据结构任课教师姓名：刘玉铭卷面总分：100分考试时长：120分钟考试类别：闭卷院（系）：数学科学学院专业：年级：2011姓名：学号：题号第一题第二题第三题第四题总分得分阅卷教师（签字）：装订线一、单项选择题（每题2分，共10题20分）题号12345678910答案CADDDABBAC1．从逻辑上可以把数据结构分为两大类。A．动态结构、静态结构B．顺序结构、链式结构C．线性结构、非线性结构D．初等结构、构造型结构2．在双向链表中，删除p

2、所指的结点时修改指针_________________。A．p->next->prior=p->prior;p->prior->next=p->next;B．p->next=p->next->next;p->next-prior=p;C．p->prior->next=p;p->prior=p->prior->prior;D．p->prior=p->next->next;p->next=p->prior->prior;3．已知二维数组A[4][6]采用列序为主序方式存储，每个元素占用4个存储单元，并且A[3]

3、[4]的存储地址为1234，元素A[0][0]的存储地址是（）。A．1322B．1146C．1310D．11584．设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1，则T中的叶子数为_________________。A．5B．6C．7D．81．由3个结点可以构造出多少种不同的二叉树？__________。A．2B．3C．4D．52．已知一棵二叉树的前序遍历结果为ABCDEF，中序遍历结果为CBAEDF，则后序遍历的结果为___________。A．CBEFDAB．FEDCBAC．CBE

4、DFAD．不定3．为便于判别有向图中是否存在回路，可借助于____。A．广度优先搜索算法B．拓扑排序算法C．最短路径算法D．最小生成树算法4．具有n个顶点的无向连通图至少含有的边数为()。A．nB．n-1C．n+1D．2n5．具有12个关键字的有序表，折半查找的平均查找长度___________。A.3.1B.4C.2.5D.56．用某种排序方法对序列（25，84，21，47，15，27，68，35，20）进行排序，记录序列的变化情况如下，则采取的排序方法是_________。（25，84，21，47，15

5、，27，68，35，20）（15，20，21，25，47，27，68，35，84）（15，20，21，25，35，27，47，68，84）（15，20，21，25，27，35，47，68，84）A．直接选择排序B．冒泡排序C．快速排序D．二路归并排序一、判断（每题1分，共10题10分）题号12345678910答案×√×√××√×√×1．顺序存储方式只能用于存储线性结构。2．栈和队列都是限制存取点的线性结构。3．若输入序列为1，2，3，4，5，6，则通过一个栈可以输出序列1，5，4，6，2，3。1．稀疏矩阵

6、压缩存储后，必会失去随机存取功能。2．数组可看成线性结构的一种推广，因此与线性表一样，可以对它进行插入，删除等操作。3．广义表中的元素或者是一个不可分割的原子，或者是一个非空的广义表。4．采用二叉链表作存储结构，树的先根序遍历和其相应的二叉树的先根序遍历的结果是一样的。5．用一维数组存储二叉树时，总是以先根序遍历顺序存储结点。6．有n个顶点的无向图,采用邻接矩阵表示,图中的边数等于邻接矩阵中非零元素个数之和的一半。7．Hash表的平均查找长度与处理冲突的方法无关。一、填空题（每题2分，共10题20分）1．已

7、知指针p指向单链表L中的某结点，则删除其后继结点的语句是：p->next=p->next->next;free(p);。2．表达式a+((b*c-d)/e+f*g/h)+i/j的后缀表达式是：abc*d-e/fg*h/++ij/+。3．循环队列用数组A[0..m-1]存放其元素值，已知其头尾指针分别是front和rear，则当前队列的元素个数是：(rear–front+m)%m。4．广义表A=（（（a，b），（c，d，e））），取出A中的原子e的操作是：Head(Tail(Tail(Head(Tail(He

8、ad(A))))))。5．在一棵二叉树中，度为零的结点的个数为n0,度为2的结点的个数为n2,则有：n0=n2+1。6．高度为8的完全二叉树至少有26=64个叶子结点。7．己知有序表为(12,18,24,35,47,50,62,83,90,115，134)，当用二分法查找90时，需比较2次查找成功。8．非叶子结点最大深度为3的3阶B-树中，最多有2+2*3+2*9=26个关键字。9．高度为5（除叶子层之外）的3阶