2017年北方民族大学计算机应用技术832C语言程序设计与数据结构之数据结构考研导师圈点必考题汇编
● 摘要
一、填空题
1． 在顺序存储的二叉树中，编号为i 和j 的两个结点处在同一层的条件是_____。
【答案】要加“虚结点”。
设编号为
和
的结点在顺序存储中的下标为
和
。
2． 对n 个记录的表r[l..n]进行简单选择排序，所需进行的关键字间的比较次数为_____。
【答案】n （n-1）/2
【解析】第一次需要n-1次比较，第i 此需要n-i 此比较，所以共需要、n-l+n-2+...+l=n（n-l ）/2。
3． 一个有2001个结点的完全二叉树的高度是_____。
【答案】11
【解析】完全二叉树的高度
4． 深度为H 的完全二叉树至少有_____个结点; 至多有_____个结点; H 和结点总数N 之间的关系是_____。
【答案】
，）则
的地址为_____。
若
5． 设有一个10阶对称矩阵A 采用压缩存储方式（以行为主序存储：
【答案】33
【解析】设存储的元素的行标为i ，列标为j 。若的地址为将代入得33。
6． 完善算法：求KMP 算法.next 数组。
则
END ；
第 2 页，共 41 页
【解析】用顺序存储结构存储二叉树时，要按完全二叉树的形式存储，非完全二叉树存储时，
，
则结点
和
在同一层上的条件是
则的地址为
【答案】
表示，两栈顶指针为
则
7． 当两个栈共享一存储区时，栈利用一维数组当栈1空时
，
【答案】
为_____，栈2空时
，
为_____，栈满时为_____。
【解析】共享栈的栈底在共享存储区的两端，当栈满时栈顶相邻。
8． 已知一循环队列的存储空间为其中队头和队尾指针分别为front 和rear , 则此循环队列判满的条件是（ ）
【答案】
9． —棵深度为k 的平衡二叉树， 其每个非终端结点的平衡因子均为0，则该树共有_____个结点。
【答案】
【解析】每个非终端结点都是0表示该平衡二叉树没有高度落差。也就是说它是一棵满二叉 树。故结点个数为
10．分别采用堆排序，快速排序，起泡排序和归并排序，对初态为有序的表，则最省时间的是_____算法，最费时间的是_____算法。
【答案】起泡；快速
，【解析】当初态为有序表时，冒泡排序只需要进行一趟比较即可，此时时间复杂度为〇（n ）而快速排序算法需要比较的次数达到最大，时间复杂度为
二、判断题
11．设栈采用顺序存储结构。若已有杂性为
（ ）
【答案】
个元素入栈，则将第i 个元素入栈时，入栈算法的时间复
【解析】由于该栈采用顺序存储结构，时间复杂度应该为0（1）。
12．一个广义表可以为其他广义表所共享。（ ）
【答案】√
【解析】因为广义表中的元素还可能是表，所以对于一个广义表可以为其他广义表所共享。
13．连通图上各边权值均不相同，则该图的最小生成树是唯一的。（ ）
【答案】√
【解析】由最小生成树的构建过程知，在确定根结点之后，因为连通图上各边权值均不相同，下一个结点的选择是唯一的，所以该图的最小生成树是唯一的。
第 3 页，共 41 页
14．广义表的取表尾运算，其结果通常是个表，但有时也可是个单元素值。（ ）
【答案】×
【解析】广义表的取表尾运算，是非空广义表除去表头元素，剩余元素组成的表，不可能是原子。
15．在用堆排序算法排序时，如果要进行增序排序，则需要采用“大根堆”。（ ）
【答案】√
，使其n 个元素的最大（小）【解析】堆排序：基本思想先将原始序列构造成一个堆（初始堆）
值处于序列的第一个位置；然后交换序列第一个元素与最后一个元素的位置。
16．二叉树中除叶结点外，任一结点其左子树根结点的值小于该结点的值；其右子树根结点的值大于等于该结点
【答案】×
【解析】二叉排序树按中序遍历的结点序列是从小到大的因为某结点的左子树根结点不一定是它的中序前驱，可能会出现某结点的左子树根结点的右子树上的值大于这个结点；其右子树根结点也不一定是它的中序后继。可能会出现右子树根结点的左子树的值小于这个结点。
17．当改变网上某一关键路径上任一关键活动后，必将产生不同的关键路径。（ ）
【答案】×
【解析】当改变任意关键路径上的关键活动之后，这个活动可能还是关键活动，因此不会产生不同的关键路径。
18．算法的优劣与算法描述语言无关，但与所用计算机有关。（ ）
【答案】
【解析】算法的优劣和它的时间复杂度和空间复杂度有关，与算法描述语言和所用计算机都无关。
19．在一个设有头指针和尾指针的单链表中，执行删除该单链表中最后一个元素的操作与链表的长度无关。（ ）
【答案】
【解析】必须从头指针开始，查找到尾指针所指结点的前驱结点的指针。
20．最小生成树的Krusakl 算法是一种贪心法。（ ）
【答案】√
【解析】在构建最小生成树常见的有三种贪心算法：kruskal , prim , soilion 。
的值，则此二叉树一定是二叉排序树。（ ）
三、算法设计题
第 4 页，共 41 页