李春葆《数据结构教程》（第4版）配套题库【名校考研真题＋课后习题＋章节题库＋模

下载地址:http://free.100xuexi.com/Ebook/88816.html
目录                                                                                        封面
内容简介
目录
第一部分　名校考研真题
　　说明：我们从指定李春葆《数据结构教程》为考研参考书目的名校历年考研真题以及计算机联考真题中挑选具有代表性的考研真题，并对其进行了详细的解答。通过这一部分的练习，可以帮助学员巩固基础知识、夯实专业基础，从而做到全方位备考。
　一、选择题
　二、综合应用题
第二部分　课后习题
　第1章　绪　论
　第2章　线性表
　第3章　栈和队列
　第4章　串
　第5章　递　归
　第6章　数组和广义表
　第7章　树和二叉树
　第8章　图
　第9章　查　找
　第10章　内排序
　第11章　外排序
　第12章　文　件
　第13章　采用面向对象的方法描述算法（无）
第三部分　章节题库
　第1章　绪　论
　第2章　线性表
　第3章　栈和队列
　第4章　串
　第5章　递　归(无)
　第6章　数组和广义表
　第7章　树和二叉树
　第8章　图
　第9章　查　找
　第10章　内排序
　第11章　外排序
　第12章　文　件
　第13章　采用面向对象的方法描述算法（无）
第四部分　模拟试题
　李春葆《数据结构教程》（第4版）模拟试题及详解（一）
　李春葆《数据结构教程》（第4版）模拟试题及详解（二）
                                                                                                                                                                                                    内容简介                                                                                            
　　“十二五”普通高等教育本科国家级规划教材《数据结构教程》（第4版，李春葆主编，清华大学出版社）是我国高校广泛采用的计算机专业权威教材之一，也被众多高校（包括科研机构）指定为计算机专业考研考博专业课参考书目。
　　为了帮助参加研究生入学考试指定考研参考书目为李春葆主编的《数据结构教程》（第4版）的考生复习专业课，我们根据教材和名校考研真题的命题规律精心编写了李春葆《数据结构教程》（第4版）辅导用书（均提供免费下载，免费升级）：
　　1．[3D电子书]李春葆《数据结构教程》（第4版）笔记和课后习题详解[免费下载，送手机版]
　　2．[3D电子书]李春葆《数据结构教程》（第4版）配套题库【名校考研真题+课后习题+章节题库+模拟试题】[免费下载，送手机版]
　　不同一般意义的传统题库，本题库是详解研究生入学考试指定考研参考书目为李春葆《数据结构教程》（第4版）的专业课复习题库，包括名校考研真题、课后习题、章节题库和模拟试题四大部分。具体来说包括以下四部分：
　　第一部分为名校考研真题。精选部分名校考研真题以及相关教辅资料的典型习题，每道试题均提供详尽答案解析。学员可以熟悉考试真题的特点，并测试自己的水平。
　　第二部分为课后习题。本部分内容选用李春葆《数据结构教程》（第4版）的全部课后习题，并提供详细答案和解析，由于李春葆《数据结构教程》知识点涵盖广，因此考生可在第一轮复习中通过此部分内容的练习，打好专业课基础。
　　第三部分为章节题库。遵循李春葆《数据结构教程》（第4版）的章目编排，共分为11章，精选详析了部分名校近年的考研真题，同时针对该教材的重难点相应整理了典型题，并对题库中的试题进行详细解析。
　　第四部分为模拟试题。根据历年考研真题的命题规律及热门考点进行押题，其试题数量、试题难度、试题风格与研究生入学考试真题完全一样。通过模拟试题的练习，学员既可以用来检测学习该考试科目的效果，又可以用来评估对自己的应试能力。
　　圣才学习网│计算机类（www.100xuexi.com）提供全国各高校计算机类专业考研考博辅导班【一对一辅导（面授/网授）、网授精讲班等】、多媒体e书、多媒体题库（免费下载，免费升级）、全套资料（历年真题及答案、笔记讲义等）、计算机类国内外经典教材名师讲堂、考研教辅图书等。本书特别适用于参加研究生入学考试指定考研参考书目为李春葆《数据结构教程》的考生，也可供各大院校学习数据结构的师生参考。
　　与传统图书相比，本书具有以下七大特色：
1．互动学习：摇一摇，找学友，交友学习两不误　　摇一摇，找到学习本书的所有学友，可精确查找学友的具体位置；与学友互动，交流学习（视频、语音等形式），交友学习两不误；学习圈内有学霸解答本书学习中的问题，并配有专职教师指导答疑解惑。

2．720度立体旋转：好用好玩的全新学习体验　　圣才电子书带给你超逼真的3D学习体验，720度立体场景，任意角度旋转，模拟纸质书真实翻页效果，让你学起来爱不释手！

3．手机扫码即可阅读，精彩内容，轻松分享　　圣才电子书扫码即可在手机阅读，随处随学。可以不用客户端不用账号，简单方便！
4．质量保证：每本电子书都经过图书编辑队伍多次反复修改，年年升级　　我们拥有一支强大图书编辑团队，他们专门从事图书的编辑工作，对各类职称考试、考研考博等教材教辅深入研究，以及各类职称考试、考研考博的历年真题进行详尽仔细研究与分析，掌握考试命题的规律和方向，并结合行业最新前沿动态，不断分析整理各个科目的考试要点，把重要考点全部固化为试题形式，形成精准领先及时的备考电子书。同时，依托北京高校资源，我们聘请知名高校众多专家组成顾问团队严格审核圣才电子书，确保质量。
5．免费升级：更新并完善内容，终身免费升级　　如购买本书，可终生使用。免费自动升级指我们一旦对该产品的内容有所修订、完善，系统立即自动提示您免费在线升级您的产品，您将自动获得最新版本的产品内容。真正做到了一次购买，终身使用。当您的电子书出现升级提示时，请选择立即升级。
6．功能强大：记录笔记、答案遮挡等十大功能　　本书具有“知识点串联列举”“划线添加笔记”、“答案自动遮挡”、“全文检索”等功能。
　　（1）知识点串联列举——相同知识点内容列表呈现，便于读者记忆和复习，举一反三，触类旁通。【为考试教辅量身定做】

　　（2）划线添加笔记——使用颜色笔工具，划一条线，写笔记，提交纠错。【圣才电子书独家推出】

　　（3）答案遮挡——先看题后看答案，学习效果好。【圣才电子书独家推出】

　　（4）全文检索——输入关键词，本书相关内容一览无余。【圣才电子书独家推出】

7．多端并用：电脑手机平板等多平台同步使用　　本书一次购买，多端并用，可以在PC端（在线和下载）、手机（安卓和苹果）、平板（安卓和苹果）等多平台同步使用。同一本书，使用不同终端登录，可实现云同步，即更换不同设备所看的电子书页码是一样的。

　　特别说明：本书的部分内容参考了部分网络资料及相关资料。但由于特殊的原因，比如作者姓名或出处在转载之前已经丢失，或者未能及时与作者取得联系等，因而可能没有注明作者的姓名或出处。如果原作者或出版人对本书有任何异议，请与我们联系，我们会在第一时间为您处理！
　　圣才学习网（www.100xuexi.com）是一家为全国各类考试和专业课学习提供辅导方案【保过班、网授班、3D电子书、3D题库】的综合性学习型视频学习网站，拥有近100种考试（含418个考试科目）、194种经典教材（含英语、经济、管理、证券、金融等共16大类），合计近万小时的面授班、网授班课程。
　　如您在购买、使用中有任何疑问，请及时联系我们，我们将竭诚为您服务！
　　全国热线：400-900-8858（8:30-00:30）
　　咨询QQ：4009008858(8:30-00:30)

　　详情访问：http://it.100xuexi.com/（圣才学习网|计算机类）
圣才学习网编辑部
                                                                                                                                    本书更多内容>>
                                                                                                                                                                                                                    使用说明                                                                                                   
                                                                                    

内容预览
第一部分　名校考研真题
说明：我们从指定李春葆《数据结构教程》为考研参考书目的名校历年考研真题以及计算机联考真题中挑选具有代表性的考研真题，并对其进行了详细的解答。通过这一部分的练习，可以帮助学员巩固基础知识、夯实专业基础，从而做到全方位备考。
一、选择题
1．已知程序如下：
int S（int n）
{
return （nS（1）->S（0）
B．S（0）->S（1）->main（）
C．main（）->S（0）->S（1）
D．S（1）->S（0）->main（）
【答案】A查看答案
【解析】函数S（intn）是一个递归函数：①当实际参数小于等于零时则返回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．程序段
FOR i：=n-1 DOWNT0 1DO
FOR j：=l TO i DO
IF A[j]>A[j+1]
THEN A[j]与A[j+1]对换；
其中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┐- 1 1，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产生后缀表达式的过程如下表所列：

当前字符	运算符栈内容	后缀表达式	说明
a
+	+		“+”进栈
b	+	ab
-	-	ab+	“-”与栈顶元素“+”的优先级相同，则“+”出栈，“-”进栈
a	-	ab+a
*	-*	ab+a	“*”的优先级大于栈顶元素“-”，则“*”进栈
（	-*（	ab+a	“（”对它之前后的运算符起隔离作用
（	-*（（	ab+a	“（”对它之前后的运算符起隔离作用
	-*（（	ab+ac
+	-*（（+	ab+ac	“+”进栈
d	-*（（+	ab+acd
）	-*（	ab+acd+	与其配对的左括号及其前所有运算符出栈
／	-*（／	ab+acd+	“／”进栈
e	-*（／	ab+acd+e
-	-*（-	ab+acd+e／	“-”的优先级小于栈顶元素“／”，则“／”出栈，“-”进栈
f	-*（-	ab+acd+e／f
）	-*	ab+acd+e／f-	与其配对的左括号及其前所有运算符出栈
+	-	ab+acd+e／f-*	“+”的优先级小于栈顶元素“*”，则“*”出栈
	+	ab+acd+e／f-*-	“+”与栈顶元素“-”的优先级相同，则“-”出栈，“+”进栈
g	+	ab+acd+e／f-*-g
		ab+acd+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。

顶点   趟数	b	c	d	e	f	集合S
k＝1	2   （a，b）	5   （a，c）				（a，b）
k＝2		（a，b，c）	（a，b，d）			{a，b，c}
k＝3			（a，b，d）	4（a，b，c，f）	（a，b，c，e）	{a，b，c，f}
k＝4			（a，b，d）		（a，b，c，e）	{a，b，c，f，d）
k＝5					（a，b，d，e）	{a, b，c，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）=KEY MOD 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,7
49计算后为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项正确。
二、综合应用题
1．用单链表保存m个整数，节点的结构为（data，link），且|data|＜n（n为正整数）。现要求设计一个时间复杂度尽可能高效地算法，对于链表中绝对值相等的节点，仅保留第一次出现的节点而删除其余绝对值相等的节点。[2015年联考真题]
例如若给定的单链表head如下：

删除节点后的head为：

要求:
（1）给出算法的基本思想。
（2）使用c或c++语言，给出单链表节点的数据类型定义。
（3）根据设计思想，采用c或c++语言描述算法，关键之处给出注释。
（4）说明所涉及算法的时间复杂度和空间复杂度。
答：（1）算法思想：
定义一个大小为n的布尔数组flag，初始时所有的元素都赋值为false，用来标识遍历过程中是否出现元素绝对值为flag的节点。然后遍历链表，遍历过程中，每一个当前结点data域的绝对值所对应的flag位：若为真，则删除该结点；若为假（false），则将flag位置为真（true）。
（2）节点的数据结构定义如下：

（3）bool flag[n]；　 //全局数组标志节点的绝对值是否出现过
Node* deleteABSEnqualNode（Node * head）
{
memset（flag, false, sizeof（flag））;
Node *pre ＝ head;
Node *p ＝ head->next;
while（ p !＝ NULL ）{
if（ flag[ abs（p->data） ] ）{//如果此绝对值已经在节点值的绝对值中出现过则删除该节点
　 pre->next＝ p->next;
　 deletep;
　 p＝ pre->next;
} else {//否则，将flag中对应的位置置为true，并将指针指向下一个元素
flag[ abs（p->data）] ＝ true;
p ＝ p->next;
}
}
return head;
}
（4）只遍历一次链表，所以时间复杂度为O（m）（m为单链表中元素的个数），申请大小为n的数组，所以空间复杂度为O（n）（n为节点绝对值的最大值）。
2．已知P是指向单向循环链表最后一个结点的指针，试编写只包含一个循环的算法，将线性表（a1，a2，…，an-1，an）改造为（a1，a2，…，an-1，an，an-1，…，a2，a1）。[北京理工大学考研真题]
答:




3．已知有5个顶点的图G如下图所示。

请回答下列问题:
（1）写出图G的邻接矩阵A（行、列下标从0开始）。
（2）求A2，矩阵A2中位于0行3列元素值的含义是什么？
（3）若已知具有n（n>＝2）个顶点的邻接矩阵为B，则Bm（22为：

0行3列的元素的含义是顶点0到顶点3间是相通的，并且路径长度为2的路径有2条。
（3）Bm中非零元素的含义是：假设此顶点位于i行j列，表示从i结点到j结点路径长度为m的路径的条数。。
4．二叉树的带权路径长度（WPL）是二叉树中所有叶结点的带权路径长度之和，给定一棵二叉树T，采用二叉链表存储，节点结构为：

left

weight

right

其中叶节点的weight域保存该结点的非负权值。设root为指向T的根节点的指针，设计求T的WPL的算法。要求：
（1）给出算法的基本设计思想；
（2）使用C或C++语言，给出二叉树结点的数据类型定义；
（3）根据设计思想，采用C或C++语言描述算法，关键之处给出注释。[2014年联考真题]
答：（1）算法的基本思路是利用利用递归的思想来求解二叉树的带权路径长度，如果当前节点不是叶子节点，那么当前节点为根的树的带权路径长度便等于它的子树的带权路径长度之和，对于此函数要传入一个当前节点的树高的形参，那么递归调用孩子节点时只需要将这个形参加一即可。
（2）typedefstruct BiNode
{
　 int weight; //权值
　 struct BiNode *left;　 //左孩子指针
　 struct BiNode *right;　 //右孩子指针
}BiNode,*BiTree;
（3）具体算法实现如下：
intCalcWPL（BiTree BT, int height）
{
　 if（BT ＝＝NULL） //如果当前节点为空节点
　return 0;
　 //如果当前节点的左右孩子节点都为空，即当前节点为叶子节点，直接返回当前节点的WPL
　 if（!BT->left && !BT->right）
　return BT.weight * height;
　 //如果当前节点不是叶子节点，则对当前节点的左右子树进行递归，返回左右子树WPL之和
　 else
　return CalcWPL（BT->left, height+1） + CalcWPL（BT->right,height+1）;
}
5．已知带头结点的单链表有data和next两个域，设计一个算法，将该链表中的重复元素结点删除。[北京邮电大学考研真题]
答：

【解析】
本题并未说单链表有序，因此要依次从每个结点出发，遍历整个链表，删除重复元素。
整个过程需要两重遍历。删除结点要记住被删结点的前驱，不能断链。
6．已知一个整数序列

，其中

,若存在

且

，则称x为A的主元素。例如

,则称5为主元素；又如

则A中没有主元素。假设A中的n个元素保存在一个一维数组中，请设计一个尽可能高效的算法，找出A的主元素。若存在主元素，则输出该元素；否则输出-1。要求：
（1）给出算法的基本设计思想。
（2）根据设计思想，采用C或C++或Java语言描述算法，关键之处给出注释。
（3）说明你所设计算法的时间复杂度和空间复杂度。[2013年联考真题]
答：
（1）算法的策略是从前向后扫描数组元素,标记出一个可能成为主元素的元素Num。然后重新计数,确认Num是否是主元素。
算法可分为以下两步：
①选取候选的主元素：依次扫描所给数组中的每个整数，将第一个遇到的整数Num保存到c中，记录Num的出现次数为1；若遇到的下一个整数仍等于Num，则计数加1否则计数减1；当计数减到0时，将遇到的下一个整数保存到c中，计数重新记为1，开始新一轮计数，即从当前位置开始重复上述过程，直到扫描完全部数组元素。
②判断c中元素是否是真正的主元素，再次扫描该数组，统计c中元素出现的次数，若大于n/2，则为主元素；否则，序列中不存在主元素。
（2）算法实现如下：
int Majority （int A[],int n）{
int i,c,count＝1;　 //c用来保存候选主元素，count用来计数
c＝A[0];　//设置A[0]为候选主元素
for（i＝1;i0）　 //处理不是候选主元素的情况
count--;
　 else{//更换候选主元素
c＝A;
count＝1;
　 }
　 }
　 }
　 if（count>0）
　 for（i＝count＝0;in/2）//确认候选主元素
　 return c;
　 else
　 return -1; //不存在主元素
}
（3）时间复杂度为O（n）,空间复杂度为O（1）。
7．设包含4个数据元素的集合S＝{“do”，“or”，“repeat”，“while”}，各元素的查找概率依次为：p1＝0.35，p2＝0.15，p3＝0.15，p4＝0.35。将S保存在一个长度为4的顺序表中，采用折半查找法，查找成功时的平均查找长度为2.2。请回答：
（1）若采用顺序存储结构保存S，且要求平均查找长度更短，则元素应如何排列？应使用何种查找方法？查找成功时的平均查找长度是多少？
（2）若采用链式存储结构保存S，且要求平均查找长度更短，则元素应如何排列？应使用何种查找方法？查找成功时的平均查找长度是多少？[2013年联考真题]
答：
（1）由于个元素的查找概率不同，很自然的把查找小的位置用于存放查找概率大的元素，故要使查找长度更短，应该采用顺序存储结构，数据元素按其查找概率降序排列。这样查找成功时的平均查找长度ASL＝0.35*1+0.35*2+0.15*3+0.15*4＝2.1。
（2）链式存储则可以采用二叉链表存储结构，构造二叉排序树，元素存储方式见下图，

采用二叉排序树的查找方法，查找成功时的平均查找长度ASL＝0.15*1+0.35*2+0.35*2+0.15*5＝2.0。
8．已知三个带头结点的线性链表A、B和C中的结点均依元素值自小至大非递减排列（可能存在两个以上值相同的结点），编写算法对A表进行如下操作：使操作后的链表A中仅留下三个表中均包含的数据元素的结点，且没有值相同的结点，并释放所有无用结点。限定算法的时间复杂度为O（m+n+p），其中m、n和p分别为三个表的长度。[清华大学考研真题]
答：


9．设有6个有序表A、B、C、D、E、F，分别含有10、35、40、50、60和200个数据元素，各表中元素按升序排列。要求通过5次两两合并，将6个表最终合并成1个升序表，并在最坏情况下比较的总次数达到最小。请回答下列问题。[2012年联考真题]
（1）给出完整的合并过程，并求出最坏情况下比较的总次数。
（2）根据你的合并过程，描述n（n≥2）个不等长升序表的合并策略，并说明理由。
答：
（1）6个表的合并顺序如下图所示。

对应于合并过程的哈夫曼树
根据上图中的哈夫曼树，6个序列的合并过程为：
第1次合并：表A与表B合并，生成含45个元素的表AB；
第2次合并：表AB与表C合并，生成含85个元素的表ABC；
第3次合并：表D与表E合并，生成含ll0个元素的表DE；
第4次合并：表ABC与表DE合并，生成含l95个元素的表ABCDE；
第5次合并：表ABCDE与表F合并，生成含395个元素的最终表。
由于合并两个长度分别为m和n的有序表，最坏情况下需要比较m+n-1次，故最坏情况下比较的总次数计算如下：
第1次合并：最多比较次数＝10+35-1＝44；
第2次合并：最多比较次数＝45+40-l＝84；
第3次合并：最多比较次数＝50+60-1＝109；
第4次合并：最多比较次数＝85+110-1＝194；
第5次合并：最多比较次数＝195+200-1＝394；比较的总次数最多为：44+84+109+194+394＝825。
（2）各表的合并策略是：在对多个有序表进行两两合并时，若表长不同，则最坏情况下总的比较次数依赖于表的合并次序。可以借用哈夫曼树的构造思想，依次选择最短的两个表进行合并，可以获得最坏情况下最佳的合并效率。
解析：本题具有较强的综合性，主要考查了构造哈夫曼树的算法思想和过程、归并排序的过程等。
10．假定采用带头结点的单链表保存单词，当两个单词有相同的后缀时，则可共享相同的后缀存储空间。例如，“loading”和“being”的存储映像如下图所示。

存储映像示意图
设strl和str2分别指向两个单词所在单链表的头结点，链表结点结构为[data，next]，请设计一个时间上尽可能高效的算法，找出由strl和str2所指的两个链表共同后缀的起始位置（如图中字符i所在结点的位置p）。要求：
（1）给出算法的基本设计思想。
（2）根据设计思想，采用C或C++或JAVA语言描述算法，关键之处给出注释。
（3）说明你所设计算法的时间复杂度。[2012年联考真题]
答：
（1）算法的基本设计思想：
①分别求出strl和str2所指的两个链表的长度m和n；
②将两个链表以表尾对齐：令指针p、q分别指向strl和str2的头结点，若m> n，则使p指向链表中的第n+1个结点；若m2n）和O（1）。
15．给出一组关键字T=（12，2，16，30，8，28，4，10，20，6，18），写出用下列算法从小到大排序时第一趟结束时的序列。[上海交通大学考研真题]
（1）希尔排序（第一趟排序的增量为5）；
（2）快速排序（选第一个记录为枢轴（分隔））；
（3）链式基数排序（基数为10）。
答：（1）一趟希尔排序：12，2，10，20，6，18，4，16，30，8，28 （D=5）
（2）一趟快速排序：6，2，10，4，8，12，28，30，20，16，18
（3）链式基数排序：

收集：→30→10→20→12→2→4→16→6→8→28→18
16．将关键字序列（7，8，30，11，18，9，14）散列存储到散列表中，散列表的存储空间是一个下标从0开始的一维数组。散列函数是：H（key）＝（key×3）MOD7，处理冲突采用线性探测再散列法，要求装填（载）因子为0.7。
（1）请画出所构造的散列表。
（2）分别计算等概率情况下查找成功和查找不成功的平均查找长度。[2010年联考真题]
答：（1）要求装填因子为0.7，数组的长度应该为7/0.7＝10，数组下标为0～9。各关键字的散列函数值如下表：

key	7	8	30	11	18	9	14
H（key）	O	3	6	5	5	6	O

采用线性探测法再散列法处理冲突，所构造的散列表为：

地址	0	1	2	3	4	5	6	7	8	9
关键字	7	14		8		11	30	18	9

（2）查找成功时，在等概率情况下，查找表中每个元素的概率是相等的，因此是根据表中元素个数来计算平均查找长度，各关键字的比较次数如下表所示：

关键字	7	8	30	11	18	9	14
次数	l	1	1	1	3	3	2

故查找成功的平均查找长度为（1+1+1+1+3+3+2）/7＝12/7。
在不成功的情况下，由于任意关键字key，H（key）的值只能是0～6之间，H（key）为0需要比较3次，H（key）为1需要比较2次，H（key）为2需要比较l次，H（key）为3需要比较2次，H（key）为4需要比较l次，H（key）为5需要比较5次，H（key）为6需要比较4次，共7种情况，如下表所示：

H（key）	0	1	2	3	4	5	6
次数	3	2	1	2	l	5	4

所以，在等概率下，查找失败的平均查找长度为：（3+2+1+2+1+5+4）/7＝18/7。
17．试画出从空树开始，由字符序列（t，d，e，s，u，g，b，j，a，k，r，i）构成的二叉平衡树，并为每一次的平衡处理指明旋转类型。[清华大学考研真题]
答：


18．设将n（n>1）个整数存放到一维数组R中。试设计一个在时间和空间两方面都尽可能高效的算法，将R中存有的序列循环左移P（00，X1，…, Xn-1）变换为（xp，xp+1，…，xn-1，x0，x1，…, xp-1）。要求：
（1）给出算法的基本设计思想。
（2）根据设计思想，采用C或C++或JAVA语言描述算法，关键之处给出注释。
（3）说明你所设计算法的时间复杂度和空间复杂度。[2010年联考真题]
答：（1）算法的基本设计思想：先将n个数据由x0,x1,…,xp,…,xn-1原地逆置，得到xn-1,…,xp,xp-1，…,x0然后再将数组R中的前，n-P个数和后P个数分别原地逆置，最终得到结果xp,xp+1,…,xn-1,x0,x1,…,xp-1。
（2）用C语言算法描述如下：

（3）说明算法的复杂性：上述算法中3个Reverse函数的的时间复杂度分别为O（p/2）、O（（p-2）/2）为0（n/2），故算法的时间复杂度为O（n）,算法的空间复杂度为0（1）。
19．带权图（权值非负，表示边连接的两顶点间的距离）的最短路径问题是找出从初始顶点到目标顶点之间的一条最短路径，假设从初始顶点到目标顶点之间存在路径，现有一种解决该问题的方法：
①该最短路径初始时仅包含初始顶点，令当前顶点为初始顶点；
②选择离υ最近且尚未在最短路径中的顶点ν，加入到最短路径中，修改当前顶点υ＝ν；
③重复步骤②，直到υ是目标顶点时为止。请问上述方法能否求得最短路径?若该方法可行，请证明之；否则请举例说明。[2009年联考真题]
答：题目中方法不一定能（或不能）求得最短路径。举例说明：



图（a）中，假设初始顶点1到目标顶点4之间有一条边，权值x＝2。显然图（a）中这顶点1和顶点4之间的最短路径长度为2。若按照题目中给定的方法找到的路径为初始顶点1经过中间结点2、3到目标顶点4，即初始顶点1—2—3一目标顶点4，所经过的边的权值分别为y1＝1、y2＝1、y3＝1。显然，y1+y2+y3＝3大于2。因此按照题目中给定的方法所求得的路径并不是这两个顶点之间的最短路径。
图（b）中，假设初始顶点为1、目标顶点为4，欲求从顶点1到顶点4之间的最短路径。显然，按照题目中给定的方法无法求出顶点1到顶点4的路径，而事实上顶点1到顶点4的最短路径为1到4。
20．已知2棵2—3 B-树如下（省略外结点）：[吉林大学考研真题]
（1）对树（a），请分别画出先后插入26，85两个新结点后的树；
（2）对树（b），请分别画出先后删除53，37两个结点后的树。
（a）

（b）

答：（1）

（2）


21．已知一个带有表头结点的单链表，结点结构为

，假设该链表只给出了头指针1ist。在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第k个位置上的结点（k为正整数）。若查找成功，算法输出该结点的data域的值，并返回1；否则，只返回0。要求：
（1）描述算法的基本设计思想；
（2）描述算法的详细实现步骤；
（3）根据设计思想和实现步骤，采用程序设计语言描述算法（使用C或C++或JAVA语言实现），关键之处请给出简要注释。[2009年联考真题]
答：（1）算法的基本设计思想定义两个指针变量p和q，初始时均指向头结点的下一个结点。p指针沿链表移动；当p指针移动到第k个结点时，q指针开始与p指针同步移动；当p指针移动到链表最后一个结点时，因为p和q相隔k，故q指针所指元素为倒数第k个结点。以上过程对链表仅进行一遍扫描。
（2）算法的详细实现步骤：
①count＝0，p和q指向链表表头结点的下一个结点；
②若p为空，转⑤；，
③若count等于k，则q指向下一个结点；否则，count＝count+1；
④p指向下一个结点，转步骤②；
⑤若count等于k，则查找成功，输出该结点的data域的值，返回1；否则，查找失败，返回0；
⑥算法结束。
（3）算法实现：


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