《2017年上海海事大学文理学院828数据结构及程序设计之数据结构考研导师圈点必考题汇编.doc》由会员分享，可在线阅读，更多相关《2017年上海海事大学文理学院828数据结构及程序设计之数据结构考研导师圈点必考题汇编.doc（4页珍藏版）》请在金锄头文库上搜索。
1、2017年上海海事大学文理学院828数据结构及程序设计之数据结构考研导师圈点必考题汇编一、填空题1 对于一个具有n 个结点的二叉树，当它为一棵_二叉树时具有最小高度，当它为一棵_ 时. 具有最大高度【答案】完全；只有一个叶结点的二叉树 2 栈是_的线性表，其运算遵循_的原则。；后进先出 【答案】操作受限（或限定仅在表尾进行插入和删除操作） 3 属于不稳定排序的有_。【答案】希尔排序、简单选择排序、快速排序、堆排序等 4 检索是为了在文件中寻找满足一定条件的记录而设置的操作。检索可以按_检索。也可以按_检索；按_检索又可以有_检索和_检索。【答案】关键字；记录号；记录号；顺序；直接 5 在一个无
2、向图的的邻接表中，若表结点的个数是m , 则图中边的条数是_条。【答案】m/2【解析】对于无向图，在邻接表中，如果存在n 条边，则会有2n 个表结点。 6 线性表用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是_。【答案】（n 1）/2【解析】删除第一个元素需要移动n i 次，以此类推，删除最后一个元素需要移动0次。平 均次数为 7 深度为H 的完全二叉树至少有_个结点; 至多有_个结点; H 和结点总数N 之间的关系是_。 【答案】 8 外排序的基本操作过程是_和_。；归并 【答案】生成有序归并段（顺串） 9 若用n 表示图中顶点数目，则有_条边的无向图成为
3、完全图。【答案】n （n-l ）/2【解析】无向完全图中任意一个顶点都和其他n-1个顶点都有一条边，即为n （n-l ）。又因为每条边重复出现两次，所有无向完全图的边数为n （n-l ）/2。 10假设一个15阶的上三角矩阵A 按行优先顺序压缩存储在一维数组B 中，则非零元素中的存储位置k=_。（注：矩阵元素下标从1开始）【答案】93【解析】对于上三角矩阵，11当两个栈共享一存储区时，栈利用一维数组当栈1空时，【答案】为_，栈2空时， 将代入得93。 表示，两栈顶指针为则在B 为_，栈满时为_。 【解析】共享栈的栈底在共享存储区的两端，当栈满时栈顶相邻。 12已知如下程序段： 语句1执行的时间
4、复杂度为_；语句2执行的时间复杂度为_；语句3执行的时间复杂度为_；语句4执行的时间复杂度为_。【答案】（1）n 1（2）n（3）n （n 3）/2（4）n （n l ）/2【解析】语s 句1执行到不符合条件情况下，执行了n 1次。当语句1不符合条件了是不会执行语句2的，所以语句2被执行了n 次。语句3每次都要执行到不符合条件，故为234. （n l ）加起来就是n （n 3）/2。语句3不符合条件了是不会执行语句4的。所以语句4被执行了123. n 即n （n l ）/2。 13设单链表的结点结构为为指针域，已知指针px 指向单链表中data 为x 的结_；点，指针py 指向data 为y
5、的新结点，若将结点y 插入结点x 之后，贝懦要执行以下语句：_; 【答案】 14己知有序表为（12，18，24，35，47，50，62，83，90，115，134）当用二分法查找90时，需_次查找成功，查找47时_成功，查找100时，需_次才能确定不成功。【答案】2；4；3【解析】二分法查找元素次数列表 查找100是找到115就停止了。 15文件由_组成；记录由_组成。【答案】记录；数据项 二、选择题16已知一棵完全二叉树的第6层（设根为第1层）有8个叶结点，则该完全二叉树的结点个数最多是（ ）。A.39B.52C.111D.119【答案】C【解析】完全二叉树的一个特点是：叶子结点只能出现在最
6、下层和次下层。题目中没有说明完全二叉树的高度，首先由完全二叉树的特点确定题目中树的高度。根据题意，一棵完全二叉树的第6层（设根为第1层）有8个叶结点，可知此二叉树的高度是6或7。题目中求二叉树的结点数最多的情况，因此此完全二叉树的高度为7。由于高度为7的完全二叉树的前6层是一棵满二叉树，根据二叉树的性质2可知，高度为6的满二叉树的结点数是-1=63。又根据二叉树的性质1可知，题目中二叉树的第6层结点数是=32个结点，已知有8个叶子结点，那么其余32-8=24个结点均为分支结点，这些结点在第7层上最多有48个子结点（即叶子结点）。所以此二叉树的结点数最多可达-1+（-8）2=lll。 17下述二叉树中，哪一种满足性质：从任一结点出发到根的路径上所经过的结点序列按其关键字有序（ ）。A. 二叉排序树B. 哈夫曼树C.D. 堆【答案】D【解析】堆的定义：n 个关键字序列称为堆，当且仅当该序列满足如下性质（简称为堆性质）：树一、填空题考研试题
