2018年数据结构考研题库【名校考研真题＋章节题库＋模拟试题】

下载地址:http://free.100xuexi.com/Ebook/156772.html
目录                                                                                        封面
内容简介
目录
第一部分　名校考研真题
　一、选择题
　二、综合应用题
第二部分　章节题库
　第1章　绪　论
　第2章　线性表
　第3章　栈和队列
　第4章　树与二叉树
　第5章　图
　第6章　查　找
　第7章　排　序
　第8章　文　件
第三部分　模拟试题
　数据结构考研模拟试题及详解（一）
　数据结构考研模拟试题及详解（二）

内容预览
第一部分　名校考研真题
一、选择题
1．已知程序如下：

程序运行时使用栈来保存调用过程的信息，自栈底到栈顶保存的信息依次对应的是（　　）。[2015年联考真题]
A．main（）->S（1）->S（0）
B．S（0）->S（1）->main（）
C．main（）->S（0）->S（1）
D．S（1）->S（0）->main（）
【答案】A查看答案
【解析】函数S（int n）是一个递归函数：①当实际参数小于等于零时则返回0，并终止递归；②当实际参数大于零时则递归调用S（n-1），并将S（n-1）的结果加上n作为返回值。程序从main（）函数开始，首先调用main（）函数；在main（）函数中调用S（1）函数时，将main（）函数的上下文保存到栈中，并进入函数S（1）；由于函数S（1）的实际参数大于零，需要调用S（0），故将S（1）函数的上下文保存到栈中，进入S（0）；在S（0）中，实际参数小于等于零，递归终止。
2．算法分析的目的是（　　）。[北京理工大学考研真题]
A．找出数据结构的合理性　
B．研究算法中的输入和输出的关系
C．分析算法的效率以求改进　
D．分析算法的易懂性和文档性
【答案】C查看答案
【解析】分析算法为的就是能对算法有更多、更好的改进。
3．先序序列为a，b，c，d的不同二叉树的个数是（　　）。[2015年联考真题]
A．13
B．14
C．15
D．16
【答案】B查看答案
【解析】二叉树的先序遍历定义为：若二叉树为空，则空操作；否则，访问根节点，然后先序遍历左子树，最后先序遍历右子树。本题中，结点a为二叉树的根节点，左右子树的先序遍历可能存在下面四种情况：①左子树为空，bcd为右子树；②b为左子树，cd为右子树；③bc为左子树，d为右子树；④bcd为左子树，右子树为空。然后将左右子树继续分解，如第①种情况的右子树先序遍历（bcd）可能有：a．左子树为空，右子树为cd；b．左子树为c，右子树为d；c．左子树为cd，右子树为空。按照这种方法继续分解左右子树，直到不能再分解为止，可得第①和④种情况各包含5种不同情况，第②和③种情况各包含2种情况，因此总共有14种不同的二叉树。
4．下列选项给出的是从根分别到达两个叶结点路径上的权值序列，能属于同一棵哈夫曼树的是（　　）。[2015年联考真题]
A．24，10，5和24，10，7
B．24，10，5和24，12，7
C．24，10，10和24，14，11
D．24，10，5和24，14，6
【答案】D查看答案
【解析】哈夫曼树是带权路径长度最短的二叉树。由根结点出发到两个叶子结点路径中，第二个被访问的两个结点的权值要么相等，要么和为根结点的权值，故B项错误。同理，通过第三个被访问的结点排除A项。C项，由两条路径可推出三个叶子结点的权值分别是：3、10和11，而根据哈夫曼树的定义可知，权值为3的结点应该和权值为10的结点结合，故C项错误。D项，反推出有四个叶子结点，权值分别为：5、5、6和8，满足哈夫曼树的条件。
5．当输入非法错误时，一个“好”的算法会进行适当处理，而不会产生难以理解的输出结果。这称为算法的（　　）。[中山大学考研真题]
A．可读性　
B．健壮性　
C．正确性　
D．有穷性
【答案】B查看答案
【解析】健壮性是指当输入数据非法时，算法能作适当的处理并作出反应，而不应死机或输出异常结果。
6．现在有一颗无重复关键字的平衡二叉树（AVL树），对其进行中序遍历可得到一个降序序列。下列关于该平衡二叉树的叙述中，正确的是（　　）。[2015年联考真题]
A．根节点的度一定为2
B．树中最小元素一定是叶节点
C．最后插入的元素一定是叶节点
D．树中最大元素一定是无左子树
【答案】D查看答案
【解析】二叉树的中序遍历定义是“若二叉树为空，则空操作；否则：①中序遍历左子树；②访问根节点；③中序遍历右子树”。A项错误，当树中仅有一个或者两个结点时，根节点的度就可能不为2；B项错误，树中最小元素是中序遍历时最后访问的节结点，当没有右子树时，最后访问的结点是根结点；C项错误，当最后插入的元素破坏树的平衡后，树会进行调整，使其成为中间结点；D项正确，由中序遍历的特点可知，左子树的值大于根结点，所以最大元素一定没有左子树。
7．设有向图G＝（V，E），顶点集V＝{V0，V1，V2，V3}，边集E＝{，，，}，若从顶点V0开始对图进行深度优先遍历，则可能得到的不同遍历序列个数是（　）。[2015年联考真题]
A．2
B．3
C．4
D．5
【答案】D查看答案
【解析】根据题意知有向图的结构如图所示。深度优先遍历的特点是尽可能先对纵深方向进行搜索，所以可能得到的不同遍历序列分别是：①V0→V2→V1→V3；②V0→V2→V3→V1；③V0→V1→V3→V2；④V0→V3→V2→V1；⑤V0→V3→V1→V2。


8．程序段

其中n为正整数，则最后一行的语句频度在最坏情况下是（　　）。[南京理工大学考研真题]
A．D（n）　
B．O（nlogn）　
C．O（n3）　
D．O（n2）
【答案】D查看答案
【解析】这个是冒泡排序，最坏的情况下需要进行1+2+...+n-1次交换，即时间复杂度是O（n2）。
9．下列选项中，不能构成折半查找中关键字比较序列的是（　）。[2015年联考真题]
A．500，200，450，180
B．500，450，200，180
C．180，500，200，450
D．180，200，500，450
【答案】A查看答案
【解析】折半查找的过程是：先确定待查找记录所在的范围，然后逐步缩小范围直到找到或找不到该记录为止。折半查找的关键字序列满足：对每一个关键字，其后面的所有关键字序列或者都小于等于该关键字或者都大于等于该关键字。A项错误，第三次比较的关键字为450，说明待查关键字位于200～450间，所以第四次比较时不会遇到关键字180。
10．已知字符串S为“abaabaabacacaabaabcc”，模式串t为“abaabc”，采用KMP算法进行匹配，第一次出现“失配”（s!＝t）时，i＝j＝5，则下次开始匹配时，i和j的值分别是（　　）。[2015年联考真题]
A．i＝1，j＝0
B．i＝5，j＝0
C．i＝5，j＝2
D．i＝6，j＝2
【答案】C查看答案
【解析】模式匹配（KMP）算法对普通的暴力匹配的改进在于：每当匹配过程中匹配失败时，主串（本题为S）的指针（i）不需要回溯，而是利用已经得到的“部分匹配”的结果将模式串（t）向右“滑动”尽可能远的一段距离后，继续进行比较。模式串“滑动”的距离是由模式串（t）本身决定的，即t的子串t[0…j-1]中前缀串和后缀串相等的最长长度。本题中第一次失配i＝5，字串为“abaab”，其相等且最长的前后缀为“ab”，一次下一个j＝2。
11．设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用（　）最节省时间。[江苏大学考研真题]
A．带头结点的双循环链表　
B．单循环链表
C．带尾指针的单循环链表　
D．单链表
【答案】A查看答案
【解析】要快速地在末尾插入元素，需要能立马得到末尾元素结点，故最好是循环链表。要快速地在末尾删除元素，需要立马得到末尾元素结点的前继结点，故最好是双向链表。综上可见为双循环链表。
12．下列排序算法中元素的移动次数和关键字的初始排列次序无关的是（　）。[2015年联考真题]
A．直接插入排序
B．起泡排序
C．基数排序
D．快速排序
【答案】C查看答案
【解析】C项，基数排序是采用分配和收集实现的，不需要进行关键字的比较。ABD三项都依赖关键字的比较，不同的初始排列次序下元素移动的次数有很大变化，最好情况元素正序，则不用移动，最坏情况元素反序，则需要移动n（n-1）/2次（n为元素个数）。
13．已知小根堆为8，15，10，21，34，16，12，删除关键字8之后需重建堆，在此过程中，关键字之间的比较数是（　）。[2015年联考真题]
A．1
B．2
C．3
D．4
【答案】C查看答案
【解析】堆排序中，依次输出堆顶的最小值，然后重新调整堆，如此反复执行，便得到一个有序序列。本题中，删除堆顶元素8后将最后一个元素12置于堆顶，然后调整堆：首先与15比较，12小于15，所以不用交换；然后与10比较，因为10小于12，所以交换10和12的位置；调整后12再与16比较，12小于16，调整堆过程结束。因此12共与15、10、16进行了三次比较。
14．下面关于线性表的叙述中，错误的是哪一个?（　　）[北方交通大学考研真题]
A．线性表采用顺序存储，必须占用一片连续的存储单元
B．线性表采用顺序存储，便于进行插入和删除操作
C．线性表采用链接存储，不必占用一片连续的存储单元
D．线性表采用链接存储，便于插入和删除操作
【答案】B查看答案
【解析】顺序存储，插入删除时会移动大量的元素，效率相对较低。
15．希尔排序的组内排序采用的是（　）。[2015年联考真题]
A．直接插入排序
B．折半插入排序
C．快速排序
D．归并排序
【答案】A查看答案
【解析】希尔排序基本思想是：先将整个待排元素序列按某个增量分割成若干个子序列，在子序列内进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。
16．下列程常段的时间复杂度是（　　）。[2014年联考真题]
count＝0;
for（k＝1;k2n）　
B．O（n）　
C．O（nlog2n）　
D．O（n2）
【答案】C查看答案
【解析】外部循环的退出条件是k>n，而对于k，每次循环都执行k＝k*2,所以循环次数为log2n；内部循环的退出条件是j>n,对于j，每次循环都执行j＝j+1，所以每次循环次数为n次。所以此程序段的时间复杂度为O（nlog2n），即选C。
17．若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（　　）存储方式最节省时间。[哈尔滨工业大学考研真题]
A．顺序表　
B．双链表　
C．带头结点的双循环链表　
D．单循环链表
【答案】A查看答案
【解析】线性表采用顺序表，便于进行存取任一指定序号的元素；线性表采用链表，便于进行插入和删除操作。但该题是在最后进行插入和删除运算，所以利用顺序表存储方式最节省时间。
18．假设栈初始为空，将中缀表达式

转换为等价后缀表达式的过程中，当扫描到f时，栈中的元素依次是（　　）[2014年联考真题]
A．

B．

　
C．

　
D．

【答案】B查看答案
【解析】中缀表达式转后缀表达式遵循以下原则：
（1）遇到操作数，直接输出；
（2）栈为空时，遇到运算符，入栈；
（3）遇到左括号，将其入栈；
（4）遇到右括号，执行出栈操作，并将出栈的元素输出，直到弹出栈的是左括号，
左括号不输出；
（5）遇到其他运算符'+''-''*''/'时，弹出所有优先级大于或等于该运算符的栈顶
元素，然后将该运算符入栈；
（6）最终将栈中的元素依次出栈，输出。
所以扫描到’/’，入栈‘描到’+’,由于’+’优先级比’/’低，所以将’/’弹出，’+’入栈；扫描到’*’,优先级比’+’高，入栈；扫描到’（‘,入栈;扫描到’-‘,将栈中优先级更高的’*’弹出，‘-’ 入栈;扫描到’*’,优先级比’-‘高，入栈。所以扫描到f的时候，栈中元素为：


19．循环两列放在一维数组A[0…M-1]中，end1指向队头元素，end2指向队尾元素的后一个位置。假设队列两端均可进行入队和出队操作，队列中最多能容纳M-1个元素。初始时为空，下列判断队空和队满的条件中，正确的是（　　）[2014年联考真题]
A．队空：end1＝＝end2；　 队满：end1＝＝（end2+1）modM
B．队空：end1＝＝end2;　 队满：end2＝＝（end1+1）mod（M-1）
C．队空：end2＝＝（end1+1）modM ;　 队满：end1＝＝（end2+1）modM
D．队空：end1＝＝（end2+1）modM;　 队满：end2＝＝（end1+1）mod（M-1）
【答案】A查看答案
【解析】在循环队列中，在少用一个元素空间的前提下，可约定入队前，测试尾指针在循环意义下加1后是否等于头指针，若相等，则队满。而队空的条件还是首尾指针是否相等。
20．对于双向循环链表，在p指针所指的结点之后插入s指针所指结点的操作应为（　　）。[北京工业大学考研真题]
A．p->right=s；s->left=p；p->right->left=s；s->right=p->right；
B．p->right=s；p->right->left=s；s->left=p；s->right=p->right；
C．s->left=p；s->right=p->right；p->right=s；P->right->left=s；
D．s->left=p；s->right=p->right；P->right->left=s；P->right=s；
【答案】D查看答案
【解析】先建立好s指向p和p的后继节点的链接，即s->left=p；s->right=p->right；然后建立p的后继节点指向s的链接，即p->right->left=s；最后，断开p与后继节点的链接，将p指向s，即p->right=s。
21．若对如下的二叉树进行中序线索化，则结点x的左、右线索指向的结点分别是（　）。[2014年联考真题]
A．e,c　
B．e,a
C．d,c　
D．b,a

【答案】D查看答案
【解析】此二叉树的中序遍历序列为：debxac,由于节点x左右孩子都为空，所有进行中序线索化时，它的左右孩子指针分别指向它的中序遍历序列的直接前驱结点b和直接后继结点a，所以选D
22．将森林F转换为对应的二叉树T，F中叶结点的个数等于（　　）。[2014年联考真题]
A．T中叶结点的个数
B．T中度为1的结点个数　
C．T中左孩子指针为空的结点个数　
D．T中右孩子指针为空的结点个数
【答案】C查看答案
【解析】森林转化为对应的二叉树是‘孩子-兄弟’存储的，即左孩子指针指向当前结点的孩子结点，右孩子指针指向当前结点的兄弟结点，所以在T中左孩子指针为空则代表它在森林中并没有孩子即为叶结点。所以选C。
23．线性表的顺序存储结构是一种（　）。[北京理工大学考研真题]
A．随机存取的存储结构　
B．顺序存取的存储结构
C．索引存取的存储结构　
D．Hash存取的存储结构
【答案】A查看答案
【解析】线性表包括顺序存储结构和链式存储结构，顺序存储结构能够随机存取表中的元素，但插入和删除操作较麻烦，链式存储结构不能随机访问表中的元素，但是能够表示元素之间的先后次序，而且插入和删除操作较容易。
24．5个字符有如下4种编码方案，不是前缀编码的是（　　）。[2014年联考真题]
A．01,0000,0001,001,1　
B．011,000,001,010,1
C．000,001,010,011,100
D．0,100,110,1110,1100
【答案】D查看答案
【解析】在一个字符集中，任何一个字符的编码都不是另一个字符编码的前缀。约定左分支表示字符‘0’，右分支表示字符‘1’，则可以用从根结点到叶子结点的路径上的分支字符串作为该叶子结点字符的编码。如此得到的编码必是前缀编码。D项中，编码110是编码1100的前缀，故不符合前缀编码的定义。
25．对如下所示的有向图进行拓扑排序，得到的拓扑序列可能是（　）。[2014年联考真题]
A．3,1,2,4,5,6　
B．3,1,2,4,6,5
C．3,1,4,2,5,6
D．3,1,4,2,6,5

【答案】D查看答案
【解析】拓扑排序方法如下:
（1）从有向图中选择一个没有前驱（即入度为0）的顶点并且输出它；
（2）从图中删去该顶点,并且删去从该顶点发出的全部有向边；
（3）重复上述两步,直到剩余的网中不再存在没有前趋的顶点为止。
对于此有向图进行拓扑排序所有序列为：3,1,4,6,2,5和3,1,4,2,6,5。所以选D
26．向一个栈顶指针为h的带头结点的链栈中插入指针S所指的结点时，应执行（　　）。[北京理工大学考研真题]
A．h->next=s； 　
B．s->next=h；
C．s->next=h；h->next=s；　
D．s->next=h-next；h->next=s；
【答案】D查看答案
【解析】本题是向一个链栈中插入结点，可从头结点后插入。先将s结点指向第一个头结点之后的结点之前，再将头结点指向s结点。
27．用哈希（散列）方法处理冲突（碰撞）时可能出现堆积（聚集）现象，下列选项中，会受堆积现象直接影响的是（　　）。[2014年联考真题]
A．存储效率　　
B．数列函数　
C．装填（装载）因子　  
D．平均查找长度
【答案】D查看答案
【解析】哈希方法冲突会使在查找冲突的关键字时，还要根据冲突处理办法多次比较关键字，则直接影响了平均查找长度。
28．在一棵具有15个关键字的4阶B树中，含关键字的结点数最多是（　　）。[2014年联考真题]
A．5　
B．6
C．10　
D．15
【答案】D查看答案
【解析】m阶B树非根结点含关键字个数

┌m/2┐ - 11，P2，P3……Pn。若，则P2＝3，则P3可能取值的个数是（　）。[2013年联考真题]
A．n-3
B．n-2
C．n-1
D．无法确定
【答案】C
【解析】除了3本身以外,其他的值均可以取到,因此可能取值的个数为n-1。
35．对于循环队列（　　）。[北京理工大学考研真题]
A．无法判断队列是否为空　
B．无法判断队列是否为满
C．队列不可能满　
D．以上说法都不是
【答案】D查看答案
【解析】，循环队列也会出现队列满的情况，并且循环队列也可以判断是否为空或满。至少可以通过两种方法进行判断：①另设一个布尔变量来区别队列是空还是满；②队满时，（rear+1）==font。
36．若将关键字1，2，3，4，5，6，7依次插入到初始为空的平衡二叉树T中，则T中平衡因子为0的分支结点的个数是（　　）。[2013年联考真题]
A．0
B．1
C．2
D．3
【答案】D
【解析】将图中给定的关键字序列依次插入到平衡树中，构成的平衡树如下图所示,由图可知平衡因子为0的分支结点为3个叶子结点，故答案为D。


37．已知三叉树T中6个叶结点的权分别是2，3，4，5，6，7，T的带权（外部）路径长度最小是（　　）。[2013年联考真题]
A．27
B．46
C．54
D．56
【答案】B
【解析】利用三叉树的6 个叶子结点的权构建最小带权生成树，最小的带权路径长度为（2+3）*3+（4+5）*2+（6+7）*1＝46
38．循环队列A[0．．m-1]存放其元素值，用front和rear分别表示队头和队尾，则当前队列中的元素数是（　　）。[南京理工大学考研真题]
A．（rear-front+m）％m　
B．rear-front+1　
C．rear-front-1 　
D．rear-front
【答案】A查看答案
【解析】对于循环队列，需要深刻理解队头（font）和队尾（rear）的概念，在队头进行出队操作，在队尾进行进队操作。rear-front可能为正也可能为负，为正时元素个数=（rear-front）；如果为负则元素的个数=（rear-front+m），所以统一的公式就是（rear-front+m）％m。
39．若X是后序线索二叉树中的叶结点，且X存在左兄弟结点Y，则X的右线索指向的是（　　）。[2013年联考真题]
A．X的父结点
B．以Y为根的子树的最左下结点
C．X的左兄弟结点Y
D．以Y为根的子树的最右下结点
【答案】A
【解析】根据后续线索二叉树的定义，X结点为叶子结点且有左兄弟，那么这个结点为右孩子结点，利用后续遍历的方式可知X结点的后继是其父结点，即其右线索指向的是父结点。
40．在任意一棵非空二叉排序树T1中，删除某结点v之后形成二叉排序树T2，再将v插入T2形成二叉排序树T3。下列关于T1与T3的叙述中，正确的是（　　）。[2013年联考真题]
I．若v是T1的叶结点，则T1与T3不同
II．若v是T1的叶结点，则T1与T3相同
III．若v不是T1的叶结点，则T1与T3不同
IV．若v不是T1的叶结点，则T1与T3相同
A．仅I、III
B．仅I、IV
C．仅II、III
D．仅II、IV
【答案】C
【解析】在一棵二叉排序树中删除一个结点后再将此结点插入到二叉排序树中，如果删除的结点是叶子结点那么在插入结点后，后来的二叉排序树与删除结点之前相同。如果删除的结点不是叶子结点，那么再插入这个结点后，后来的二叉树可能发生变化，不完全相同。
41．栈和队的共同点是（　　）。[大连理工大学考研真题]
A．都是先进后出　
B．都是后进先出
C．只允许在端点处插入和删除元素　
D．没有共同点
【答案】C查看答案
【解析】栈和队列的区别是栈是先进后出的数据结构，队列是先进先出的数据结构，栈和队列的共同点是都只能在端点处插入和删除元素。
42．设图的邻接矩阵A如下所示,各顶点的度依次是（　　）。[2013年联考真题]

A．1，2，1，2
B．2，2，1，1
C．3，4，2，3
D．4，4，2，2
【答案】C
【解析】当图用邻接矩阵存储时，各顶点的度是矩阵中此结点对应的横行和纵列非零元素之和。
43．若对如下无向图进行遍历，则下列选项中，不是广度优先遍历序列的是（　　）。[2013年联考真题]

A．h，c，a，b，d，e，g，f
B．e，a，f，g，b，h，c，d
C．d，b，c，a，h，e，f，g
D．a，b，c，d，h，e，f，g
【答案】D
【解析】根据广度优先遍历的定义，可知ABC三项都为广度优先遍历，而D项是深度优先遍历而不是广度优先遍历，故答案为D。
44．执行（　　）操作时，需要使用队列做辅助存储空间。[华中科技大学考研真题]
A．查找哈希（Hash）表　
B．广度优先搜索网
C．前序（根）遍历二叉树　
D．深度优先搜索网
【答案】B查看答案
【解析】查找哈希表不需要辅助存储空间，前序遍历二叉树和深度优先搜索网需要使用栈做辅助存储空间，广度优先搜索树需要队列做辅助存储空间。
45．下列AOE网表示一项包含8个活动的工程。通过同时加快若干进度可以缩短整个工程的工期。下列选项中，加快其进度就可以缩短工程工期的是（　　）。[2013年联考真题]

A．c和e
B．d和e
C．f和d
D．f和h
【答案】C
【解析】根据AOE网的定义可知，同时缩短几条关键路径上的活动时间，可以缩短整个工期。
46．在一株高度为2的5阶B树中，所含关键字的个数最少是（　　）。[2013年联考真题]
A．5
B．7
C．8
D．14
【答案】A
【解析】根据B树的定义可知，跟结点最少含有max（2,（m-1））个关键字，高度为2的阶B树最少有（5-1）+1＝5个关键字，其中根节点含有（5-1）个关键字，第2层结点含有1关键字。
47．在一棵三元树中度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数为（　　）个。[哈尔滨工业大学考研真题]
A．4　
B．5　
C．6　
D．7
【答案】C查看答案
【解析】设度为0的结点数为x，则度为3的树总结点数n=度为0的结点数+度为1的结点数+度为2的结点数+度为3的结点数=x+2+1+2=x+5；从每个结点所指向的结点数的和的角度来计算度为3的树总结点数n=2×3+1×2+2×1+1=11。两种方法所计算出来的n相等，所以x=6。
48．对给定的关键字序列110，119，007，911，114，120，122进行基数排序，则第2趟分配收集后得到的关键字序列是（　　）[2013年联考真题]
A．007，110，119，114，911，120，122
B．007，110，119，114，911，122，120
C．007，110，911，114，119，120，122
D．110，120，911，122，114，007，119
【答案】C
【解析】基数排序的第1趟排序是按照个位数字来排序的,第2趟排序是按然十位数字的大小进行排序的,故答案是C项。
49．求整数n（n≥0）阶乘的算法如下，其时间复杂度是（　）。[2012年联考真题]

A．O（log2n）
B．O（n）
C．O（nlog2n）
D．O（n2）
【答案】B查看答案
【解析】设fact（n）的运行时间函数是T（n）。

该函数中语句①的运行时间是0（1），语句②的运行时间是T（n-1）+O（1），其中O（1）为乘法运算的时间。
因此，当n≤1时，T（n）-0（1）；当n>1时，T（n）＝T（n-1）+O（1）。则，T（n）＝O（1）+T（n-1）
＝2×O（1）+T（n-2）＝（n-1）×O（1）+T（1）＝n× O（1）
＝O（n）
即fact（n）的时间复杂度为O（n）。
50．设森林F中有三棵树，第一、第二、第三棵树的结点个数分别为M1、M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是（　）。[北方交通大学考研真题]
A．M1　
B．M1+M2　
C．M3　
D．M2+M3
【答案】D查看答案
【解析】森林转换成二叉树的原则：将第一棵树的根结点作为根结点，所有结点的第一个左孩子作为左孩子，下一个兄弟结点作为右孩子，其它树作为第一棵树的右孩子。所以森林F对应的二叉树根结点的右子树上的结点个数是除第一棵树外其他所有树的结点总数。即M2+M3。
51．已知操作符包括‘+’、‘-’、‘*’、‘／’、‘（’和‘）’。将中缀表达式a+b-a*（（c+d）／e-f）+g转换为等价的后缀表达式ab+acd+e／f-*-g+时，用栈来存放暂时还不能确定运算次序的操作符。若栈初始时为空，则转换过程中同时保存在栈中的操作符的最大个数是（　　）。[2012年联考真题]
A．5
B．7
C．8
D．11
【答案】A查看答案
【解析】基本思想是：采用运算符栈是为了比较运算符的优先级，所有运算符必须进栈。只将大于栈顶元素优先级的运算符直接进栈，否则需要退栈栈顶运算符（先出栈的运算符先计算，同优先级的运算符在栈中的先计算）。表达式a+b-a*（（c+d）／e-f）+g产生后缀表达式的过程如下表所列：


通过上表可以看出，显然转换过程中同时保存在栈中的操作符的最大个数是5。
52．若一棵二叉树的前序遍历序列为a，e，b，d，c，后序遍历序列为b，c，d，e，a，则根结点的孩子结点（　　）。[2012年联考真题]
A．只有e
B．有e、b
C．有e、c
D．无法确定
【答案】A查看答案
【解析】由题目可知，若一棵二叉树的前序遍历序列为a，e，b，d，c，后序遍历序列为b，c，d，e，a，其中a为这棵二叉树的根结点，接下来，在前序遍历的第二个结点为e，而后序遍历的倒数第二个结点为e，说明a的孩子结点只有e。
53．有关二叉树下列说法正确的是（　）。[南京理工大学考研真题]
A．二叉树的度为2
B．一棵二叉树的度可以小于2
C．二叉树中至少有一个结点的度为2
D．二叉树中任何一个结点的度都为2
【答案】B查看答案
【解析】树的度=MAX（结点1的度,结点2的度,结点3的度,...,结点n的度）。二叉树之所以称为二叉树，是因为二叉树中节点的度最大是2，也可以小于2。
54．若平衡二叉树的高度为6，且所有非叶结点的平衡因子均为1，则该平衡二叉树的结点总数为（　　）。[2012年联考真题]
A．12
B．20
C．32
D．33
【答案】B查看答案
【解析】本题题目的实际问题是，具有6层结点的平衡二叉树含有最少的结点数是多少。 Nh表示深度为h的平衡二叉树中含有的最少结点数，有N0＝0，N1＝1，N2＝2……Nh＝Nh-1+Nh-2+1
由此可得N5＝20。对应的平衡二叉树如下图所示。

55．对有2个顶点e条边且使用邻接表存储的有向图进行广度优先遍历，其算法时间复杂度是（　　）。[2012年联考真题]
A．0（n）
B．0（e）
C．O（n+e）
D．O（n×e）
【答案】C查看答案
【解析】遍历图的过程实质上是对每个顶点查找其邻接点的过程。其耗费的时间则取决于所采用的存储结构。当用二维数组表示邻接矩阵图的存储结构时，查找每个顶点的邻接点所需时间为O（n2），其中n为图中顶点数。而当以邻接表作图的存储结构时，找邻接点所需时间为0（e），其中e为无向图中边的数或有向图中弧的数。由此，当以邻接表作存储结构时，深度优先搜索遍历图的时间复杂度为O（n+e）。即可得出正确答案。
56．深度为h的满m叉树的第k层有（　　）个结点（1≤k≤h）。[北京航空航天大学考研真题]
A．mk-1　
B．mk-1　
C．mh-1 　
D．mh-1
【答案】A查看答案
【解析】满m叉树第k层必有mk-1个结点。
57．若用邻接矩阵存储有向图，矩阵中主对角线以下的元素均为零，则关于该图拓扑序列的结论是（　　）。[2012年联考真题]
A．存在，且唯一
B．存在，且不唯一不唯一
C．存在，可能不唯一
D．无法确定是否存在
【答案】C查看答案
【解析】图的基本应用——拓扑排序，用邻接矩阵存储有向图，矩阵中主对角线以下的元素均为零，说明该图为有向无环图，所以其拓扑序列存在，但不一定唯一，如图的邻接矩阵为

，则存在两个拓扑序列。
58．有向带权图如题58图所示，若采用迪杰斯特拉（Dijkstra）算法求从源点a到其他各顶点的最短路径，则得到的第一条最短路径的目标顶点是b，第二条最短路径的目标顶点是c，后续得到的其余各最短路径的目标顶点依次是（　　）。[2012年联考真题]

题58图有向带权图
A．d, e, f
B．e，d，f
C．f，d，e
D．f，e，d
【答案】C查看答案
【解析】本题主要考查Dijkstra算法的思想和解题步骤。题目执行算法过程中各步的状态如下表所示。
执行Dijkstra算法过程中各步的状态表，故后续目标顶点依次为f,d,e。

59．将有关二叉树的概念推广到三叉树，则一棵有244个结点的完全三叉树的高度为（　）。[南京理工大学考研真题]
A．4　
B．5　
C．6　
D．7
【答案】C查看答案
【解析】若二叉树中最多只有最下面两层的结点的度数可以小于2，并且最下面一层的叶结点都依次排列在该层最左边的位置上，则这样的二叉树称为完全二叉树。具有n个（n>0）结点的完全二叉树的高度为

log2（n+1）

或

log2n

+1；由完全二叉树类推到完全三叉树可知，n个结点的完全三叉树的高度为

log3（n+1）

或

log3n

+1。
60．下列关于最小生成树的叙述中，正确的是（　　）。[2012年联考真题]
Ⅰ．最小生成树的代价唯一 Ⅱ．所有权值最小的边一定会出现在所有的最小生成树中 Ⅲ．使用普里姆（Prim）算法从不同顶点开始得到的最小生成树一定相同Ⅳ．使用普里姆算法和克鲁斯卡尔（Kruskal）算法得到的最小生成树总不相同
A．仅Ⅰ
B．仅Ⅱ
C．仅Ⅰ、Ⅲ
D．仅Ⅱ、Ⅳ
【答案】A查看答案
【解析】当图中存在相同权值的边时，其最小生成树可能是不唯一的，但最小生成树的代价一定是相同的，所以说法Ⅰ正确。从n个顶点的连通图中选取n-1条权值最小的边可能构成回路，所以说法Ⅱ错误。当某个顶点有权值相同的边，使用普里姆（Prim）算法从不同顶点开始得到的最小生成树并不一定相同，所以说法Ⅲ错误。当最小生成树不唯一时，使用普里姆算法和克鲁斯卡尔（Kruskal）算法得到的最小生成树可能相同，也可能不同，所以说法Ⅳ错误。由此可得出正确答案。
61．设有一棵3阶B树，如题61图所示。删除关键字78得到一棵新B树，其最右叶结点所含的关键字是（　　）。[2012年联考真题]

题61图3阶B树图
A．60
B．60，62
C．62，65
D．65
【答案】D查看答案
【解析】本题主要考查B树删除操作。即被删关键字所在的结点中的关键字个数等于［m/2］-1，而与该结点相邻的右兄弟（或左兄弟）结点中的关键字数目大于［m/2］-1，则需将其兄弟结点中最小（或最大）的关键字上移至双亲结点中，而将双亲结点中小于（或大于）且紧靠该上移关键字的关键字下移至被删关键字所在结点中。题目中删除关键字78得到一棵新B树如下，其最右叶结点所含的关键字是65。


62．排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一趟排序。下列排序方法中，每一趟排序结束时都至少能够确定一个元素最终位置的方法是（　　）。[2012年联考真题]
Ⅰ．简单选择排序　Ⅱ．希尔排序　Ⅲ．快速排序　Ⅳ．堆排　V．二路归并排序A．仅Ⅰ、Ⅲ、Ⅳ
B．仅Ⅰ、Ⅱ、Ⅲ
C．仅Ⅱ、Ⅲ、Ⅳ
D．仅Ⅲ、Ⅳ、Ⅴ
【答案】A查看答案
【解析】其中简单选择排序、堆排序属于选择类排序，每一趟排序结束时将确定最大（或最小）关键字所在的位置。快速排序每一趟排序结束时将确定基准关键字所在的位置。希尔排序、二路归并排序每一趟排序结束时不一定能确定一个元素的最终位置。
63．对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，在同一结点的左、右孩子中，其左孩子的编号小于其右孩子的编号，可采用（　　）次序的遍历实现编号。[北京理工大学考研真题]
A．前序　
B．中序　
C．后序　
D．从根开始按层次遍历
【答案】C查看答案
【解析】为了满足条件：每个结点的编号大于其左、右孩子的编号，同一结点的左孩子的编号小于其右孩子的编号，访问结点的次序必须是左一右一根，所以采用后序遍历。
64．某二叉树中序序列为A，B，C，D，E，F，G，后序序列为B，D，C，A，F，G，E则前序序列是（　　）。[南京理工大学考研真题]
A．E，G，F，A，C，D，B
B．E，A，C，B，D，G，F
C．E，A，G，C，F，B，D
D．上面的都不对
【答案】B查看答案
【解析】由后序序列可知E为根结点，再由中序遍历结果知A，B，C，D，为E的左孩子，且A为B，C，D的父结点，到此可排除A项，按照这种逻辑依次推理，便可得出结果。
65．对同一待排序列分别进行折半插入排序和直接插入排序，两者之间可能的不同之处是（　　）。[2012年联考真题]
A．排序的总趟数
B．元素的移动次数
C．使用辅助空间的数量
D．元素之间的比较次数
【答案】D查看答案
【解析】折半插入排序所需附加存储空间和直接插入排序相同，从时间上比较，折半插入排序仅减少了关键字间的比较次数，而记录的移动次数不变。折半插入排序的时间复杂度仍为O（n2）,所以两者之间的不同只可能是元素之间的比较次数。
66．设n是描述问题规模的非负整数，下面程序片段的时间复杂度是（　　）。[2011年联考真题]
x＝2：
while（x2n）
B．O（n）
C．O（nlog2n）
D．O（n2）
【答案】A查看答案
【解析】其中，以基本的原操作重复执行的次数作为算法的时间度量。题目中的基本运算是语句x＝2×x，设其执行时间为T（n），则有2T（n）2（n/2）＝O（log2n）。
67．在二叉树结点的前序序列、中序序列和后序序列中，所有叶结点的先后顺序（　　）。[北方交通大学考研真题]
A．都不相同　
B．完全相同
C．前序和中序相同，而与后序不同　
D．中序和后序相同，而与前序不同
【答案】B查看答案
【解析】前序遍历形式为：根左右。中序遍历形式为：左根右。后序遍历形式为：左右根。可知左右相对顺序不变，叶结点都是在左右位置上，因此，他们的相对位置不变。
68．元素a，b，c，d，e依次进入初始为空的栈中，若元素进栈后可停留、可出栈，直到所有元素都出栈，则在所有可能的出栈序列中，以元素d开头的序列个数是（　　）。[2011年联考真题]
A．3
B．4
C．5
D．6
【答案】B查看答案
【解析】d首先出栈后的状态如下图所示。

此时可有以下4种操作：
（1）e进栈后出栈，出栈序列为decba。
（2）c出栈，e进栈后出栈，出栈序列为dceba。
（3）cb出栈，e进栈后出栈，出栈序列为dcbea。
（4）cba出栈，e进栈后出栈，出栈序列为dcbae。
69．已知循环队列存储在一维数组A[0…n-1]中，且队列非空时front和rear分别指向队头元素和队尾元素。若初始时队列为空，且要求第1个进入队列的元素存储在A[0]处，则初始时front和rear的值分别是（　）。[2011年联考真题]
A．0，0
B．0，n-1
C．n-1，0
D．n-1，n-1
【答案】B查看答案
【解析】题目要求队列非空时front和rear分别指向队头元素和队尾元素，若初始时队列为空，且要求第1个进入队列的元素存储在A[0]处，则此时front和rear的值都为0。由于进队操作要执行（rear+1）% n，则初始时front的值为0、rear的值为n-1。
70．设F是一个森林，B是由F变换得到的二叉树。若F中有n个非终端结点，则B中右指针域为空的结点有（　　）个。[西安电子科技大学考研真题]
A．n-1　
B．n　
C．n+1　
D．n+2
【答案】C查看答案
【解析】B中右指针为空的点，就是森林中的每棵树中的每个非终端结点最右边那个子树的根结点，也可以说是每棵树的每一棵子树的每一层的最后一个结点。每个非终端结点都有一个最右边的结点（X），转化成二叉树的时候，X就是那个右指针为空的点，所以F中N个非终端结点就对应着N个B中右指针为空的结点。
还有一个结点，就是森林中最右边那个树的根结点（T），如果这个森林只有一棵树，这个结点就是这棵树的根结点，这个结点不是任何结点的最右边的孩子，但是转化成二叉树B的时候，他的右指针可以是为空。所以答案的n+1。
71．若一棵完全二叉树有768个结点，则该二叉树中叶结点的个数是（　）。[2011年联考真题]
A．257
B．258
C．384
D．385
【答案】C查看答案
【解析】由n＝n0+n1+n2和n0＝n2+1可知，n＝2n0-1+n1，即2n0-1+n1＝768，显然n1＝1，2n0＝768，则n0＝384，所以二叉树的叶结点个数是384。还可以根据完全二叉树的另一个性质：最后一个分支结点的序号为[768/2]，故非叶子结点数为384，而叶子结点的个数为768-384＝384。（［x］表示不大于x的最大整数，比如［3.14］＝3）。
72．若一棵二叉树的前序遍历序列和后序遍历序列分别为l，2，3，4和4，3，2，1，则该二叉树的中序遍历序列不会是（　　）。[2011年联考真题]
A．1，2，3，4
B．2，3，4，1
C．3，2，4，1
D．4，3，2，1
【答案】C查看答案
【解析】题目中的二叉树的先序序列和后序序列正好相反，这样的二叉树每层只有一个结点。该二叉树的形态如下图所示。

从左至右，这8棵二叉树的中序序列分别为：
（1）4，3，2，1，
（2）3，4，2，1
（3）2，4，3，1
（4）2，3，4，1
（5）1，4，3，2
（6）1，3，4，2
（7）1，2，4，3
（8）1，2，3，4
显然选项C的中序序列不会出现。
73．一个有n个结点的图，最少有（　　）个连通分量，最多有（　　）个连通分量。[北京邮电大学考研真题]
A．0　
B．1　
C．n-l　
D．n
【答案】1 B 2 D查看答案
【解析】若图G中任意两个顶点都是连通的，则称图G为连通图。无向图中的极大连通子图称为图的连通分量。图的连通分量的个数小于或等于图的结点数。当图的各个结点彼此都没有边相连时，连通分量数最大为n。当图的各个结点彼此都与边相连时，连通分量数最小为1。
74．已知一棵有2011个结点的树，其叶结点个数为ll6，该树对应的二叉树中无右孩子的结点个数是（　　）。[2011年联考真题]
A．115
B．116
C．1895
D．1896
【答案】D查看答案
【解析】每个非终端结点转换成二叉树后都对应一个无右孩子的结点（因为一个非终端结点至少有一个孩子结点，其最右边的孩子结点转换成二叉树后一定没有右孩子），另外，树根结点转换成二叉树后也没有右孩子。题目中树的总结点数是2011，叶结点个数是116，则非终端结点个数是2011-116＝1895，则该树对应的二叉树中无右孩子的结点个数是1895+1＝1896。
75．对于下列关键字序列，不可能构成某二叉排序树中一条查找路径的序列是（　　）。[2011年联考真题]
A．95，22，91，24，94，71
B．92，20，91，34，88，35
C．21，89，77，29，36，38
D．12，25，71，68，33，34
【答案】A查看答案
【解析】各选项对应的查找过程如下图所示，从中看到BCD三项对应的查找树都是二叉排序树，只有A项对应的查找树不是一棵二叉排序树，因为在以91为根的左子树中出现了比91大的结点94。


76．用邻接表存储图所用的空间大小＿＿。[北京交通大学考研真题]
A．与图的顶点数和边数都有关　
B．只与图的边数有关
C．只与图的顶点数有关　 　
D．与边数的平方有关
【答案】A查看答案
【解析】所谓邻接表就是对图G中的每个顶点vi建立一个单链表，第i个单链表中的结点表示依附于顶点vi的边，这个单链表就称为顶点vi的边表。因此邻接表既存储图的所有顶点，也存储顶点之间的边的信息。
77．下列关于图的叙述中，正确的是（　　）。[2011年联考真题]
Ⅰ．回路是简单路径
Ⅱ．存储稀疏图，用邻接矩阵比邻接表更省空间
Ⅲ．若有向图中存在拓扑序列，则该图不存在回路
A．仅Ⅱ
B．仅Ⅰ、Ⅱ
C．仅Ⅲ
D．仅Ⅰ、Ⅲ
【答案】C查看答案
【解析】第一个顶点和最后一个顶点相同的路径称为回路；序列中顶点不重复出现的路径称为简单路径；回路显然不是简单路径，所以选项Ⅰ错误。稀疏图用邻接表表示比邻接矩阵节省存储空间，稠密图适合用邻接矩阵的存储表示，所以选项Ⅱ错误。利用拓扑排序算法可以判断图中是否存在回路，即在拓扑排序输出结束后所余下的顶点都有前驱，则说明了只得到了部分顶点的拓扑有序序列，图中存在回路。所以选项Ⅲ正确。
78．为提高散列（Hash）表的查找效率，可以采用的正确措施是（　）。[2011年联考真题]
Ⅰ．增大装填（载）因子
Ⅱ．设计冲突（碰撞）少的散列函数
Ⅲ．处理冲突（碰撞）时避免产生聚集（堆积）现象
A．仅Ⅰ
B．仅Ⅱ
C．仅Ⅰ、Ⅱ
D．仅Ⅱ、Ⅲ
【答案】D查看答案
【解析】散列表的查找效率（比较次数）取决于：散列函数、处理冲突的方法和散列表的装填因子α。α标志着散列表的装满程度，通常情况下，α越小，发生冲突的可能性越小；反之，α越大，表示已填入的记录越多，再填入记录时，发生冲突的可能性越大。因此选项Ⅰ错误，越是增大装填因子，发生冲突的可能性就越大，查找效率也越低。选项Ⅱ正确。选项Ⅲ正确。采用合适的处理冲突的方法避免产生聚集现象，也将提高查找效率。例如，用拉链法解决冲突时不存在聚集现象，用线性探测法解决冲突时易引起聚集现象。
79．无向图G=（V，E），其中：V={a，b，c，d，e，f）}，E={（a，b），（a，e），（a，c），（b，e），（c，f），（f,d）,（e，d），对该图进行深度优先遍历，得到的顶点序列正确的是（　　）。[南京理工大学考研真题]
A．a，b，e，c，d，f　
B．a，c，f,e，b，d
C．a，e，b，c，f, d　
D．a，e，d，f，c，b
【答案】D查看答案
【解析】图的深度优先遍历过程是：从图中某个初始顸点v出发，首先访问初始顶点v，然后选择一个与顶点v相邻且没被访问过的顶点u为初始顶点。再从u出发进行深度优先搜索，直到图中与当前顶点v邻接的所有顶点都被访问过为止。
根据E={（a，b），（a，e），（a，c），（b，e），（c，f），（f，d），（e，d）}可知各顶点之间的邻接关系。依据上面的原则遍历，得出遍历顺序a，e，d，f，c，b。
80．为实现快速排序算法，待排序序列宜采用的存储方式是（　　）。[2011年联考真题]
A．顺序存储
B．散列存储
C．链式存储
D．索引存储
【答案】A查看答案
【解析】对绝大部分内部排序而言，只适用于顺序存储结构，快速排序在排序过程中，既要从后向前查找，也要从前向后查找，因此宜采用顺序存储。
81．已知序列25，13，10，12，9是大根堆，在序列尾部插入新元素18，将其再调整为大根堆，调整过程中元素之间进行的比较次数是（　　）。[2011年联考真题]
A．1
B．2
C．4
D．5
【答案】B查看答案
【解析】对堆插入或删除一个元素，有可能不满足堆的性质，堆被破坏，需要调整为新堆。
（1）为原堆，
（2）为插入18后，
（3）比较10与18，交换后，
（4）比较25与18，不交换，即为调整后的新的大根堆。
因此调整过程中元素之间进行的比较次数为2。


82．在有向图的邻接表存储结构中，顶点v在链表中出现的次数是（　　）。[北京理工大学考研真题]
A．顶点v的度　
B．顶点v的出度　
C．顶点v的入度　
D．依附于顶点v的边数
【答案】B查看答案
【解析】在有向图中，第j个链表中的结点个数只是顶点vi的出度，为求入度，必须遍历整个邻接表。因此顶点v在链表中出现的次数是顶点v的入度。
83．若元素a，b，c，d，e，f依次进栈，允许进栈、退栈操作交替进行，但不允许连续三次进行退栈操作，则不可能得到的出栈序列是（　　）。[2010年联考真题]
A．d，c，e，b，f，a
B．c，b，d，a，e，f
C．b，c，a，e，f，d
D．a，f，e，d，c，b
【答案】D查看答案
【解析】4个选项所给序列的进、出栈操作序列分别为：
选项A．Push，Push，Push，Push，Pop，Pop，Push，Pop，Pop，Push，Pop，Pop
选项B．Push，Push，Push，Pop，Pop，Push，Pop，Pop，Push，Pop，Push，Pop
选项C．Push，Push，Pop，Push，Pop，Pop，Push，Push，Pop，Push，Pop，Pop
选项D．Push，Pop，Push，Push，Push，Push，Push，Pop，Pop，Pop，Pop，Pop
按照题目要求，不允许连续三次进行退栈操作，所以D项所给序列为不可能得到的出栈顺序。
84．某队列允许在其两端进行入队操作，但仅允许在一端进行出队操作，元素a，b，c，d，e依次入此队列后再进行出队操作，则不可能得到的出队序列是（　　）。[2010年联考真题]
A．b，a，c，d，e
B．d，b，a，c，e
C．d，b，c，a，e
D．e，c，b，a，d
【答案】C查看答案
【解析】根据题意，队列两端都可以输入数据元素，但是只能在一端输出数据元素，这种队列为输出受限的双端队列。本题解题方法分别判断每个选项如何入队和出队，从而得出不可能的情况。
假设L代表从左端入队，R代表从右端入队，出队都是从左端L出。四个选项所给序列的进队操作序列分别为：
选项A．aL（或aR），bL，cR，dR，eR
选项B．aL（或aR），bL，cR，dL，eR
选项C．不可能出现
选项D．aL（或aR），bL，cL，dR，eL
85．已知有向图G=（V，E），其中V={V1，V2，V3，V4，V5，V6，V7}，E=｛1，V2>，1，V3>，1，V4>，2，V5>，3，V5>，3，V6>，4，V6>，5，V7>，6，V7>｝，G的拓扑序列是（　　）。[北京航空航天大学考研真题]
A．V1，V3，V4，V6，V2，V5，V7　
B．V1，V3，V2，V6，V4，V5，V7
C．V1，V3，V5，V2，V6，V7　
D．V1、V2，V5，V3，V4，V6，V7
【答案】A查看答案
【解析】设G=（V，E）是一个具有n个顶点的有向图，V中顶点序列v1，v2，…，vn，能被称为拓扑序列的条件：若i，vj>是图中的边（即从顶点vi到vj有一条路径），则在序列中顶点vi必须排在顶点vj之前。根据上面拓扑序列的定义，就可以得出G的拓扑序列是V1，V3，V4，V5，V2，V5．V7。
86．下列线索二叉树中（用虚线表示线索），符合后序线索树定义的是（　　）。[2010年联考真题]

【答案】D查看答案
【解析】线索二叉树利用二叉链表的空链域来存放结点的前驱和后继信息，解题思路较简单。题中所给二叉树的后序序列为dbca。结点d无前驱和左子树，左链域空，无右子树，右链域指向其后继结点b；结点b无左子树，左链域指向其前驱结点d；结点c无左子树，左链域指向其前驱结点b，无右子树，右链域指向其后继结点a。所以正确选项为D。
87．在下图所示的平衡二叉树中，插入关键字48后得到一棵新平衡二叉树。在新平衡二叉树中，关键字37所在结点的左、右子结点中保存的关键字分别是（ 　）。[2010年联考真题]

A．13、48
B．24、48
C．24、53
D．24、90
【答案】C查看答案
【解析】题目中，插入48以后，树根结点的平衡因子由-1变为-2，失去平衡。这属于RL（先右后左）型平衡旋转，需做两次（先右旋后左旋转）旋转操作。过程如下图所示：

显然，在调整后的新平衡二叉树中，关键字37所在结点的左、右子结点中保存的关键字分别是24，53。
88．在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是（　　）。[南京理工大学考研真题]
A．G中有弧i，Vj>　
B．G中有一条从Vi到Vj的路径
C．G中没有弧i，Vj）　
D．G中有一条从Vj到Vi的路径
【答案】D查看答案
【解析】若想实现图的一个拓扑排序，需要满足的一个条件为：若顶点A在序列中排在顶点B的前面，则在图中不存在从顶点B到顶点A的路径。又因为若G中有一条从Vj到Vi的路径，则在拓扑序列中Vi不可能在Vj前。
89．在一棵度为4的树T中，若有20个度为4的结点，10个度为3的结点，1个度为2的结点，10个度为1的结点，则树T的叶结点个数是（　　）。[2010年联考真题]
A．41
B．82
C．113
D．122
【答案】B查看答案
【解析】根据二叉树的性质3的推广公式：N0＝l+N2+2N3+…+（m-1）Nm可直接在将数据带入公式，即N0＝l+N2+2N3+3N4＝l+1×1+2×10+3×20＝82。树T的叶子结点的个数是82。如果考生不能熟练掌握二叉树的性质3的推广公式，得到本题的正确答案将费时费力。因此，需要熟练掌握二叉树的性质及推广。
90．对n（n≥2）个权值均不相同的字符构成哈夫曼树。下列关于该哈夫曼树的叙述中，错误的是（　　）。[2010年联考真题]
A．该树一定是一棵完全二叉树
B．树中一定没有度为1的结点
C．树中两个权值最小的结点一定是兄弟结点
D．树中任一非叶结点的权值一定不小于下一层任一结点的权值
【答案】A查看答案
【解析】哈夫曼树为带权路径长度最小的二叉树，但不一定是完全二叉树，A项错误；哈夫曼树中没有度为1的结点，B项正确；构造哈夫曼树时，最先选取两个权值最小的结点作为左右子树构造一棵新的二叉树，C项正确；哈夫曼树中任一非叶结点P的权值为其左右子树根结点权值之和，其权值不小于其左右子树根结点的权值，在与结点P的左右子树根结点处于同一层的结点中，若存在权值大于结点P权值的结点Q，那么结点Q与其兄弟结点中权值较小的一个应该与结点P作为左右子树构造新的二叉树，由此可知，哈夫曼树中任一非叶结点的权值一定不小于下一层任一结点的权值。
91．在下述几种树中，（　　）可以表示静态查找表。[中国科学技术大学考研真题]
A．次优查找树　
B．二叉排序树　
C．B-树　
D．平衡二叉树
【答案】A查看答案
【解析】在有序序列的查找中，如果各个元素的查找概率都是一样的，那么二分查找是最快的查找算法，但是如果查找元素的查找概率是不一样的，那么用二分查找就不一定是最快的查找方法。基于这种查找元素概率不想等的有序序列，可以通过构造最优二叉树的方法，使得该二叉树的带权路径长度最小，这样的二叉树的构造代价是非常大的，所以用一种近似的算法，构造次优查找树，该树的带权路径长度近似达到最小
92．若无向图G＝（V，E）中含7个顶点，则保证图G在任何情况下都是连通的，则需要的边数最少是（　　）。[2010年联考真题]
A．6
B．15
C．16
D．21
【答案】C查看答案
【解析】要保证无向图G在任何情况下都是连通的，即任意变动图G中的边，G始终保持连通。首先需要图G的任意6个结点构成完全连通子图G1，需n（n-l）／2＝6×（6—1）／2＝15条边，然后再添加一条边将第7个结点与G1连接起来，共需l6条边。本题非常容易错误地选择选项A，主要原因是对“保证图G在任何情况下都是连通的”的理解，分析选项A，在图G中，具有7个顶点6条边并不能保证其一定是连通图，即有n-1条边的图不一定是连通图。分析选项D，图G有7个顶点21条边，那么图G一定是无向完全图，无向完全图能保证其在任何情况下都是连通的，但是这不符合题目中所需边数最少的要求。
93．对下图进行拓扑排序，可以得到不同的拓扑序列的个数是（　　）。[2010年联考真题]

A．4
B．3
C．2
D．1
【答案】B查看答案
【解析】拓扑排序的步骤为：
（1）在有向图中选一个没有前驱的顶点并且输出它；
（2）从图中删除该顶点和以它为尾的弧。重复上述两步，直至全部顶点均已输出。由于没有前驱的顶点可能不唯一，所以拓扑排序的结果也不唯一。题中所给图有三个不同的拓扑排序序列，分别为abced，abecd，aebcd。
94．如果要求一个线性表既能较快地查找，又能适应动态变化的要求，可以采用下列哪一种查找方法。[北京交通大学考研真题]
A．分块　
B．顺序　
C．折半　
D．哈希
【答案】A查看答案
【解析】分块查找，把线形表分成若干块，块间是顺序存储的，所以查找速度较快。在每一块中的数据元素的存储顺序是任意的，所以便于线性表的动态变化。
95．已知一个长度为l6的顺序表L，其元素按关键字有序排列。若采用折半查找法查找一个L中不存在的元素，则关键字的比较次数最多是（　　）。[2010年联考真题]
A．4
B．5
C．6
D．7
【答案】B查看答案
【解析】折半查找法在查找不成功时和给定值进行比较的关键字个数最多为（log2n）+1，在本题中，n＝l6，故比较次数最多为5。
96．采用递归方式对顺序表进行快速排序。下列关于递归次数的叙述中，正确的是（　　）。[2010年联考真题]
A．递归次数与初始数据的排列次序无关
B．每次划分后，先处理较长的分区可以减少递归次数
C．每次划分后，先处理较短的分区可以减少递归次数
D．递归次数与每次划分后得到的分区的处理顺序无关
【答案】D查看答案
【解析】快速排序是递归的，递归过程可用一棵二叉树给出，递归调用层次数与二叉树的深度一致。例如：待排序列{48，62，35，77，55，14，35，98），采用快速排序方法，其对应递归调用过程的二叉树如下图所示。

在最坏情况下，若初始序列按关键码有序或基本有序时，快速排序反而蜕化为冒泡排序。即其对应递归调用过程的二叉树是一棵单支树。因此快速排序的递归次数与初始数据的排列次序有关。但快速排序的递归次数与每次划分后得到的分区处理顺序无关，即先处理较长的分区或先处理较短的分区都不影响递归次数。
97.m阶B-树是一棵（　　）。[北京邮电大学考研真题]
A．m又排序树　
B．m叉平衡排序树
C．m-1叉平衡排序树
D．m+1叉平衡排序树
【答案】B查看答案
【解析】一棵m阶的B-树，或为空树，或为满足下列特性的m叉树：①树中每个结点至多有m棵子树；②若根结点不是叶子结点，则至少有两棵子树；③除根结点之外的所有非终端结点至少有ém/2ù棵子树；④所有的叶子结点都出现在同一层次上，并且不带信息。因此m阶B-树是一棵m叉平衡排序树。
98．对一组数据（2，12，16，88，5，10）进行排序，若前三趟排序结果如下：
第一趟：2，12，16，5，10，88
第二趟：2，12，5，10，16，88
第三趟：2，5，10，12，16，88
则采用的排序方法可能是（　）。[2010年联考真题]
A．起泡排序
B．希尔排序
C．归并排序
D．基数排序
【答案】A查看答案
【解析】题目中所给的三趟排序过程，显然是使用起泡排序方法，每趟排序时从前往后依次比较，使大值“沉底”。希尔排序的基本思想是：先对序列进行“宏观调整”，待序列中的记录“基本有序”时再进行直接插入排序。宏观调整的方法是：通过某种规则将大的待排序序列分割为若干小的待排序序列，再依次对这些小的序列直接插入排序。宏观调整可以多次，每次分割的序列数逐渐增多，而每个序列中所包含的元素数逐渐减少。归并排序的基本操作是将多个小的有序序列合并为一个大的有序序列，然后“逐趟归并”，直至整个序列为有序为止。基数排序是分配排序的一种，这类排序不是通过关键字比较，而是通过“分配”和“收集”过程来实现排序的。本题中，很容易看出大值逐渐“沉底”，显然使用的是起泡排序法。
99．为解决计算机主机与打印机之间速度不匹配问题，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是（　　）。[2009年联考真题]
A．栈
B．队列
C．树
D．图
【答案】B查看答案
【解析】这类问题一般都先分析题目中的数据具有什么操作特性或是结构特性比如“先进后出”、“先进先出”等再判断其逻辑结构。栈和队列是操作受限的线性表，栈具有先进后出的特性而队列具有先进先出的特性。由于本题中先进入打印数据缓冲区的文件先被打印，因此打印数据缓冲区具有先进先出性，则它的逻辑结构应该是队列。
100．设哈希表长M=14，哈希函数H（KEY）=KEYMOD 11。表中已有4个结点：ADDR（15）=4，ADDR（38）=5，ADDR（61）=6，ADDR（84）=7，其余地址为空，如用二次探测再哈希法解决冲突，关键字为49的结点的地址是（ 　）。[东华大学考研真题]
A．8　
B．3　
C．5
D．9
【答案】D查看答案
【解析】15，38，61，84用哈希函数H（key）=key%11计算后得地址:4,5,6,749计算后为5,发生冲突.用二次探测再散列法解决冲突:1:（key+1^2）%11=（49+1）%11=6,仍然发生冲突.2:（key-1^2）%11=（49-1）%11=4,仍然发生冲突.3:（key+2^2）%11=（49+4）%11=9,不再发生冲突.
101．设栈S和队列Q的初始状态均为空，元素a，b，c，d，e，f，g依次进入栈S。若每个元素出栈后立即进入队列Q，且7个元素出队的顺序是b，d，c，f，e，a，g，则栈S的容量至少是（　　）。[2009年联考真题]
A．1
B．2
C．3
D．4
【答案】C查看答案
【解析】由于栈具有先进后出的特性，队列具有先进先出的特性，出队顺序即为人队顺序。在本题中，每个元素出栈S后立即进入队列Q，出栈顺序即为入队顺序，所以本题中队列的作用形同虚设，根据题意出队顺序即为出栈顺序。根据出栈顺序可以分析各个元素进出栈的过程：第一个出栈元素为b，表明栈内还有元素a，b出栈前的深度为2；第二个出栈元素为d，栈内元素为a和c，d出栈前的深度为3；c出栈后，剩余元素为a，c出栈前的深度为2；f出栈后，剩余元素为a和e，f出栈前的深度为3；e出栈后，剩余元素为a，e出栈前的深度为2；a出栈后，无剩余元素，a出栈前的深度为1；g出栈后，无剩余元素，g出栈前的深度为1。所以栈容量至少是3。
102．给定二叉树如下图所示。设N代表二叉树的根，L代表根结点的左子树，R代表根结点的右子树。若遍历后的结点序列为3，1，7，5，6，2，4，则其遍历方式是（　　）。[2009年联考真题]
A．LRN
B．NRL
C．RLN
D．RNL

【答案】D查看答案
【解析】对“二叉树”而言，一般有三条搜索路径：
①先上后下的按层次遍历；
②先左（子树）后右（子树）的遍历；
③先右（子树）后左（子树）的遍历。
其中第1种搜索路径方式就是常见的层次遍历，第2种搜索路径方式包括常见的先序遍历NLR、中序遍历LNR、后序遍历LRN，第3种搜索路径方式则是不常使用的NRL、RNL、RLN。本题考查的是第3种搜索路径方式的一种情况。根据遍历的序列以及树的结构图，可以分析出该遍历的顺序是先右子树再跟结点最后左子树，故答案为D。
103．排序算法的稳定性是指（　　）。[北京理工大学考研真题]
A．经过排序之后，能使值相同的数据保持原顺序中的相对位置不变
B．经过排序之后，能使值相同的数据保持原顺序中的绝对位置不变
C．算法的排序性能与被排序元素的数量关系不大
D．算法的排序性能与被排序元素的数量关系密切
【答案】A查看答案
【解析】假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，ri=rj，且ri在rj之前，而在排序后的序列中，ri仍在rj之前，则称这种排序算法是稳定的；否则称为不稳定的。
104．下列二叉排序树中，满足平衡二叉树定义的是（　　）。[2009年联考真题]

【答案】B查看答案
【解析】平衡二叉树是指左右子树高度差（平衡因子）的绝对值不超过1的二叉树。A项中根结点的平衡因子是2；B项中每个结点的平衡因子的绝对值均不超过1；C项中根结点的平衡因子是-2；D项中根结点的平衡因子是3。
105．已知一棵完全二叉树的第6层（设根为第1层）有8个叶结点，则该完全二叉树的结点个数最多是（　　）。[2009年联考真题]
A．39
B．52
C．111
D．119
【答案】C查看答案
【解析】完全二叉树的一个特点是：叶子结点只能出现在最下层和次下层。题目中没有说明完全二叉树的高度，首先由完全二叉树的特点确定题目中树的高度。根据题意，一棵完全二叉树的第6层（设根为第1层）有8个叶结点，可知此二叉树的高度是6或7。题目中求二叉树的结点数最多的情况，因此此完全二叉树的高度为7。由于高度为7的完全二叉树的前6层是一棵满二叉树，根据二叉树的性质2可知，高度为6的满二叉树的结点数是26-1＝63。又根据二叉树的性质1可知，题目中二叉树的第6层结点数是25＝32个结点，已知有8个叶子结点，那么其余32-8＝24个结点均为分支结点，这些结点在第7层上最多有48个子结点（即叶子结点）。所以此二叉树的结点数最多可达26-1+（25-8）×2＝111。
106．下面给出的四种排序方法中，排序过程中的比较次数与排序方法无关的是（　　）。[北京航空航天大学考研真题]
A．选择排序法　
B．插入排序法　
C．快速排序法　
D．堆排序法
【答案】A查看答案
【解析】选择排序的基本思想是：
第i趟排序开始时，当前有序区和无序区分别为R[0．．i-1]和R[i．．n-1]（______0≤i＝2e（n为图的总结点数，e为总边数），因此，Ⅰ项正确。对于Ⅱ、Ⅲ项中的特性不是一般无向连通图的特性，可以轻松地举出反例。“至少有一个顶点的度为1”的反例如下图（1）所示，“边数大于顶点个数减1”的反例如下图（2）所示。

（1）

（2）
109．设被排序的结点序列共有N个结点，在该序列中的结点已十分接近排序的情况下，用直接插入法、归并法和一般的快速排序法对其排序，这些算法的时间复杂性应为（　　）。[上海交通大学考研真题]
A．O（N），O（N），O（N）　
B．O（N），O（N*log2N），O（N*log2N）
C．O（N），O（N*log2N），O（N2）　
D．O（N2），O（N*log2N），O（N2）
【答案】C查看答案
【解析】因为该序列中的结点已经十分接近排序的情况，对于直接插入法，大部分结点只需要直接插入后面即可，因此时间复杂度为O（N）。对于采用归并法，它是一种稳定的排序方法，它的时间复杂度为O（Nlog2N）。对于一般的快速排序法，序列越接近有序，所需要的比较次数越多，此时的时间复杂度为O（N2）。
110．下列叙述中，不符合m阶B树定义要求的是（　　）。[2009年联考真题]
A．根结点最多有m棵子树
B．所有叶结点都在同一层上
C．各结点内关键字均升序或降序排列
D．叶结点之间通过指针链接
【答案】D查看答案
【解析】B树就是指B-树。根据B-树的定义，m阶B-树中每个结点最多有m个分支，因此，根结点最多有m棵子树，A项正确；B-树中所有叶结点都在最底层，位于同一层，B项正确；结点内各关键字互不相等且有序排列，C项正确。但是，所有叶子结点之间通过指针链接，是B+树的定义，而B-树中没有。因此，D项是错误的。
111．已知关键字序列5，8，12，19，28，20，15，22是小根堆（最小堆），插入关键字3，调整后的小根堆是（　　）。[2009年联考真题]
A．3，5，12，8，28，20，15，22，19
B．3，5，12，19，20，15，22，8，28
C．3，8，12，5，20，15，22，28，19
D．3，12，5，8，28，20，15，22，19
【答案】A查看答案
【解析】在堆中插入或删除一个元素后，将不再满足堆的性质。为了使其成为新堆，在输出堆顶元素后，需要调整剩余元素。具体过程如图（1）～（5）所示，（1）为原堆，（2）为插入3后，（3）、（4）为调整过程，（5）为调整后的小根堆。










112．有些排序算法在每趟排序过程中，都会有一个元素被放置在其最终的位置上，下列算法不会出现此情况的是（　　）。[北京交通大学考研真题]
A．希尔排序　
B．堆排序　
C．起泡排序　
D．快速排序
【答案】A查看答案
【解析】选择排序、起泡排序和堆排序一趟排序后，在序列首部或尾部应该有最大或最小值。
113．若数据元素序列11，12，13，7，8，9，23，4，5是采用下列排序方法之一得到的第二趟排序后的结果，则该排序算法只能是（　　）。[2009年联考真题]
A．起泡排序
B．插入排序
C．选择排序
D．二路归并排序
【答案】B查看答案
【解析】经过两趟排序后，A项起泡排序的结果是两个最小或最大的元素放到了序列的最终位置；B项插入排序的结果是前三个数有序即可；C项选择排序结果是两个最小的元素在最前面按顺序排好；D项二路归并排序的结果是长度为4的子序列有序，即前4个数排好序，接下来的4个数排好序。显然题目中的元素序列只能是插入排序第二趟排序后的结果，因此，B项正确。

下载地址:http://free.100xuexi.com/Ebook/156772.html