2017年合肥工业大学科研机构和宣城校区848软件工程学科专业基础综合之数据结构考研导师圈点必考题汇编
● 摘要
目录
2017年合肥工业大学科研机构（智能制造技术研究院、科学技术研究院、工业与装备技术研究院）和宣城校区848软件工程学科专业基础综合之数据结构考研导师圈点必考题汇编（一） . .. 2 2017年合肥工业大学科研机构（智能制造技术研究院、科学技术研究院、工业与装备技术研究院）和宣城校区848软件工程学科专业基础综合之数据结构考研导师圈点必考题汇编（二） . 10 2017年合肥工业大学科研机构（智能制造技术研究院、科学技术研究院、工业与装备技术研究院）和宣城校区848软件工程学科专业基础综合之数据结构考研导师圈点必考题汇编（三） . 18 2017年合肥工业大学科研机构（智能制造技术研究院、科学技术研究院、工业与装备技术研究院）和宣城校区848软件工程学科专业基础综合之数据结构考研导师圈点必考题汇编（四） . 26 2017年合肥工业大学科研机构（智能制造技术研究院、科学技术研究院、工业与装备技术研究院）和宣城校区848软件工程学科专业基础综合之数据结构考研导师圈点必考题汇编（五） . 33
第 1 页，共 41 页
一、填空题
1． 对于双向链表，在两个结点之间插入一个新结点需修改的指针共_____个，单链表为_____个。
【答案】4; 2
2． 分别采用堆排序，快速排序，起泡排序和归并排序，对初态为有序的表，则最省时间的是_____算法，最费时间的是_____算法。
【答案】起泡；快速
，【解析】当初态为有序表时，冒泡排序只需要进行一趟比较即可，此时时间复杂度为〇（n ）而快速排序算法需要比较的次数达到最大，时间复杂度为
3． 一个有2001个结点的完全二叉树的高度是_____。
【答案】11
【解析】完全二叉树的高度
4． 己知有序表为（12，18，24，35，47，50，62，83，90，115，134）当用二分法查找90时，需_____次查找成功，查找47时_____成功，查找100时，需_____次才能确定不成功。
【答案】2；4；3
【解析】二分法查找元素次数列表
查
找100是找到115就停止了。
5． 在进行入栈运算时应先判别栈是否_____:在进行出栈运算时应先判别栈是否_____:当栈中元素为n 个，进行入栈运算时发生上溢，则说明该栈的最大容量为_____。为了增加内存空间的利用率和减少溢出的可能性，由两个栈共享一片连续的空间时，应将两栈的_____分别设在内存空间的两端，这样只有当_____时才产生溢出。
【答案】满；空；n ; 栈底；两栈顶指针相邻（即值之差的绝对值为1）
6． 在单链表L 中，指针P 所指结点有后继结点的条件是_____
【答案】
第 2 页，共 41 页
【解析】指针所指节点的指针域所指向的元素非空，说明该指针所指节点有后继结点。
7． 起始地址为480，大小为8的块，其伙伴块的起始地址是_____；若块大小为32，则其伙伴块的起始地址为_____。
【答案】
【解析】起始地址为P ，大小为的内存块，其伙伴块的起始地址计算公式如下：
根据上述公式起始地址就为488。 8． 假定查找有序表中每个元素的概率相等，则进行折半查找时的平均查找长度为_____
【答案】37/12
【解析】折半查找时每个的次数如表所示：
表
平均查找次数为
9． 已知一循环队列的存储空间为环队列判满的条件是（ ）
【答案】
10．在单链表中设置头结点的作用是_____。
【答案】方便运算
其中
队头和队尾指针分别为front 和rear , 则此循
二、判断题
11．在一个设有头指针和尾指针的单链表中，执行删除该单链表中最后一个元素的操作与链表的长度无关。（ ）
【答案】
【解析】必须从头指针开始，查找到尾指针所指结点的前驱结点的指针。
12．在索引顺序表中，实现分块查找，在等概率查找情况下，其平均查找长度不仅与表中元素个数有关，而且与每块中元素个数有关。（ ）
【答案】√
【解析】在进行分块查找时，首先查找元素在哪一块，然后在确定的块中查找元素，因此，在索引顺序表中，进行分块查找的平均查找长度不仅与表中元素的个数有关，而且与每块中的元素个数有关。
第 3 页，共 41 页
13．设尾指针的循环链表表示队列，则入队和出队算法的时间复杂度均为
【答案】
（ ）。
【解析】入队和出队操作分别在队尾和队头进行，设有尾指针的循环链表对头和尾元素的操 作的时间复杂度是
14．用向量和单链表表示的有序表均可使用折半查找方法来提高查找速度。（ ）
【答案】×
【解析】单链表不能使用折半查找方法。折半查找主要用于数据元素有序且存储方式为顺序存储的表。
15．为提高排序速度，进行外排序时，必须选用最快的内排序算法。（ ）
【答案】×
【解析】外部排序算法最常用的是多路归并，即将原文件分解成多个能够一次性装人内存的部分，分别把每一部分调入内存完成排序。然后，对已经排序的子文件进行归并排序。
16．—个有向图的邻接表和逆邻接表中的结点个数一定相等。（ ）
【答案】×
【解析】图的邻接表表示法类似于树的孩子链表示法。对于图G 中的每个顶点V i ，该方法把所以邻接于顶点V i 的V j 链接成一个带头。在有向图中，为图中每个顶点V i 建立一个入边表的方法称为逆邻接表示法。
17．若一个广义表的表头为空表，则此广义表亦为空表。（ ）
【答案】×
【解析】广义表的表头就是广义表的第一个元素。只有非空广义表才能取表头。
18．静态链表就是一直不发生变化的链表。（ ）
【答案】
【解析】用数组描述的链表，即称为静态链表。仍具有链式存储结构的主要优点。不是指不发生变化的的链表。
19．数据的逻辑结构是指数据的各数据项之间的逻辑关系。（ ）
【答案】
【解析】数据的逻辑结构是指数据元素之间的逻辑关系。
20．二叉树中除叶结点外，任一结点其左子树根结点的值小于该结点点的值大于等于该结点
【答案】×
第 4 页，共 41 页
的值；其右子树根结
的值，则此二叉树一定是二叉排序树。（ ）