北京师范大学数据结构教学资料12级数据结构试卷

《北京师范大学数据结构教学资料12级数据结构试卷》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、北京师范大学2013-2014学年第1学期期末考试试卷（A卷）课程名称：数据结构任课教师姓名:郑新肖永康卷面总分：100分考试时长：100分钟考试类别：闭卷0开卷口其他口院（系）：专业：年级：姓名：学号：题号第一题第二题第三题第四题总分得分阅卷教师（签字）：一、选择题（每小题2分，共20分）1.算法分析的目的是（）。A.研究算法的输入与输出Z间的关系B.找出数据结构的合理性C.分析算法的效率以求改进算法D.分析算法的可读性与可移植性2.与双向链表相比较，单向链表的缺点之一是（）。A.无法省略头结点指针B.插入和删除操作麻烦C.无法进行随机访问D.占用更大的存储空间3.在非空双向循环链表中由

2、q所指的那个链结点前面插入一个由p指的链结点的动作对应的语句依次为：p->rlink=q;p->llink=q->llink;q->llink=p和（）。A.q->rlink=pB.q-Allink-ArlinkrpC・p->llink->rlink=pD.p->rlink->rlink=p4.一个以整数为栈元素的栈，若元素的进栈顺序为1,2,3,4,5,出栈可以发生在任何时刻。则下面的序列中，（）是可能的出栈序列。A.2,5,4,1,3B.3丄4,2,5C.5,4,3丄2D.2,3,1,5,41.n个结点的线索二叉树上，含有的线索数为（）。A・2nB・n・lC・n+1D・n2.已知某非空

3、二叉树采用顺序存储结构，树屮结点的数据信息依次存放在一个一维数组中，该二叉树的中序遍历系列为（）ABCDFEGHA.GDBAFHCEB.GBDAFHCEC.BDGAFHCED.BGDAFHCE3.以下序列不是堆的是()oA.(100,85,98,77,80,60,82,40,20,10,66)B.(100,98,85,82,80,77,66,60,40,20,10)C.(10,20,40,60,66,77,80,82,85,98,100)D.(100,85,40,77,80,60,66,98,82,10,20)&导致图的遍历序列不唯一的因素有（）。A.出发点不同、存储结构不同、遍历方法不同

4、B.出发点不同、存储结构不同C.遍历方法不同、存储结构不同D.出发点不同、遍历方法不同9.一个递归算法必须包括（）。A.递归部分B.终止条件和递归部分C.迭代部分D.终止条件和迭代部分10.对序列｛15,9,7,8,20,-1,4｝用希尔（Shell）排序方法排序，经一趟后序列变为｛15,・1,4,8,20,9,7）,则该次采用的增量是（）。A・1B・4C・3D・2二、填空题（每空2分，共20分）2.若节点的结构如下图所示，则向一个栈顶指针为h的带头节点的链式栈中插入指针为s所指的节点时，应执行的操作为（）。data*nexl3.设有一个二维数组A[12,10],采用以行序为主序存储，每个

5、数据占有2个字节,该数组的首元素A[0][0]的地址为1200,则A[6,5]的地址为（）。4•哈夫曼树的叶结点数目为nO,则分支总数B%（）。5.当栈的最大长度难以估计时，栈最好采用（）存储结构。6.三个结点的二叉树共有（）种形态。7.已知一个二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历结果为（）。8.若具有n个顶点的无向连通图采用邻接矩阵表示，则邻接矩阵中至少有（）个非零元素。9.已知有序表为{12,18,24,35,47,50,62,83,90,115,134},当用二分法查找47时（）次查找。10.快速排序法在（）情况下最有利于发挥其长处。三、判断题（

6、每小题2分，共10分）1.二叉树叶结点的数目只与度为2的结点的数目有关。（）2.按照关键字值有序链接的链表，可对数据采用折半查找。（）3.霍夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。（）4.稳定排序算法和不稳定排序算法的排序结果有差别，通常稳定排序算法的性能优于不稳定排序算法。（）5.m阶B+树是一棵m叉平衡索引树。按“最大关键码复写”原则建立的B+树的每个结点最多有m个关键字；除根节点外，其他结点至少有「m/2]个子树。（）四、简答题（每小题10分，共50分）1.下面的函数实现带附加头结点的单链表数据结点逆序连接，请填空完善之。//通过一趟遍历，将链表屮所有结点的链接方

7、向逆转(1)(2分)voidList::Inverse(){LinkNode*p=first->link;LinkNode*pr=0;if()//空链表(2分)return;while(p->link){first->link=p->link;p->link=pr;(3);(3分)p=first->link;}(4);(3分)2.将序列25,45,90,65,55,10,75,40,30,88分别建立二