《2017年南昌航空大学软件学院817数据结构考研导师圈点必考题汇编.doc》由会员分享，可在线阅读，更多相关《2017年南昌航空大学软件学院817数据结构考研导师圈点必考题汇编.doc（4页珍藏版）》请在金锄头文库上搜索。
1、2017年南昌航空大学软件学院817数据结构考研导师圈点必考题汇编一、填空题1 棵深度为k 的平衡二叉树， 其每个非终端结点的平衡因子均为0，则该树共有_个结点。【答案】 【解析】每个非终端结点都是0表示该平衡二叉树没有高度落差。也就是说它是一棵满二叉 树。故结点个数为 2 下列程序是快速排序的非递归算法，请填写适当的语句，完成该功能。 【答案】 【解析】快速排序（quicksort ）的基本思想是，通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。 3 从平均时间性能而言，_排序最佳。【答案】快
2、速【解析】快速算法的平均时间复杂度为nlogn 。4 起始地址为480，大小为8的块，其伙伴块的起始地址是_；若块大小为32，则其伙伴块的起始地址为_。【答案】 【解析】起始地址为P ，大小为的内存块，其伙伴块的起始地址计算公式如下： 根据上述公式起始地址就为488。5 索引顺序文件既可以顺序存取，也可以_存取。【答案】随机 6 遍历图的过程实质上是_，广度优先遍历图的时间复杂度_; 深度优先遍历图的时间复杂度_, 两者不同之处在于_, 反映在数据结构上的差别是_。【答案】查找顶点的邻接点的过程；0（n+e）; 0（n+e）; 访问顶点的顺序不同；队列和栈 【解析】广度优先遍历图使用队列这种数
3、据结构，深度优先遍历图使用栈这种数据结构。7 文件由_组成；记录由_组成。【答案】记录；数据项 8 根据线性表的链式存储结构中每一个结点包含的指针个数，将线性链表分成_和_; 而又根据指针的连接方式，链表又可分成_和_。【答案】单链表；双链表；（动态）链表；静态链表【解析】线性表的链式存储结构根据每个结点包含的指针个数分为单链表和双链表，单链表只包含一个指针，指向后续元素，双链表包括两个指针，指向前一个元素和后续元素。根据指针的连接方式，链表可分为动态链表和静态链表。静态链表的指针指向下一个元素的编号，动态链表的指针指向下一个元素的物理位置。9 在单链表中设置头结点的作用是_。【答案】方便运算
4、 10如某二叉树有20个叶结点，有30个结点仅有一个孩子，则该二叉树的总结点数为_。【答案】69【解析】二叉树叶结点数为20, 则度为2的结点数为19, 所以总的结点数为20+19+30=69。二、选择题11假定基准程序A 在某计算机上的运行时间为100秒，其中90秒为CPU 时间，其余为间。若CPU速度提高A.55秒 B.60秒 C.65秒 D.70秒 【答案】D 。 CPU 速度提高【解析】秒。即CRJ 性能提高比为1.5, 改进之后的CPU 运行时间速度不变，仍维持10秒，所以运行基准程序A 所耗费的时间为70秒。速度不变，则运行基准程序A 所耗费的时间是（ ）。时 12静态链表中指针表
5、示的是（ ）。A. 下一元素的地址 B. 内存储器的地址 C. 下一元素在数组中的位置 D. 左链或右链指向的元素的地址 【答案】C【解析】静态链表的一般结构为： 这种结构是预先分配一个较大的空间，类似于一次申请一个较大的数组，但是元素的增删操作都不会移动元素，只需要移动next 成员就行。因此，静态链表中的指针实际上表示的就是下一个元素在数组中的位置。 13直接插入排序在最好情况下的时间复杂度为（ ）。 【答案】B【解析】当序列是按照直接插入排序的顺序有序时，此时进行插入时，每次都只需要和末尾 的一个元素进行比较，此时的时间复杂度最好，为 14若对如下的二叉树进行中序线索化，则结点x 的左、右线索指向的结点分别是（ ）A.B.C.D.一、填空题考研试题
