作者：圣才电子书
出版社：圣才电子书
格式: AZW3, DOCX, EPUB, MOBI, PDF, TXT
2018年数据结构考研题库【名校考研真题＋章节题库＋模拟试题】试读：
第一部分 名校考研真题
一、选择题
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＝{
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） 3
C．O（n） 2
D．O（n）【答案】D【解析】这个是冒泡排序，最坏的情况下需要进行1+2+...+n-1次2交换，即时间复杂度是O（n）。
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[i]!＝t[i]）时，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;k<＝n; k*2）
for（j＝1;j<＝n;j+1）
count++;
A．O（logn） 2
B．O（n）
C．O（nlogn） 22
D．O（n）【答案】C【解析】外部循环的退出条件是k>n，而对于k，每次循环都执行k＝k*2,所以循环次数为logn；内部循环的退出条件是j>n,对于j，每次2循环都执行j＝j+1，所以每次循环次数为n次。所以此程序段的时间复杂度为O（nlogn），即选C。2
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 <＝ j <＝ m – 1。
4阶B树非根结点含关键字1～3个，所以要使关键字结点数量最多，那么每个结点只有一个关键字，一共有15个关键字那么最多有15个含有关键字的结点
29．表达式a*（b+c）-d的后缀表达式是（ ）。[南京理工大学考研真题]
A．abcd*+-
B．abc+*d-
C．abc*+d-
D．-+*abcd【答案】B【解析】后缀表达式：在程序语言中，运算符位于两个操作数后面的表达式。
30．用希尔排序方法对一个数据序列进行排序时，若第1趟排序结果为9,1,4,13,7,8,20,23,15，则该趟排序采用的增量（间隔）可能是（ ）[2014年联考真题]
A．2
B．3
C．4
D．5【答案】B【解析】对于A，增量为2，那么9,4,7,20,15是一组，而它们是无序的，所以A错误
对于C，增量为4，那么9,7,15是一组，而它们是无序的，所以C错误
对于D，增量为5，那么9,8是一组，降序，1,20是一组，而它们是升序，所以D也错误。对于B，分为3组：9,13,20；1,7,23；4,8,15都是升序有序，所以B正确
31．下列选项中，不可能是快速排序第2趟排序结果的是（ ）[2014年联考真题]
A．2,3,5,4,6,7,9
B．2,7,5,6,4,3,9
C．3,2,5,4,7,6,9
D．4,2,3,5,7,6,9【答案】C【解析】对于快速排序，每一趟都会使一个元素位于有序时的位置，而有序序列为2,3,4,5,6,7,9，与C进行对比，只有9位于它有序的时候的位置，显然不是第二趟快速排序的结果
32．允许对队列进行的操作有（ ）。[华中科技大学考研真题]
A．对队列中的元素排序
B．取出最近进队的元素
C．在队头元素之前插入元素
D．删除队头元素【答案】D【解析】队列的原则是先进先出，出队操作应该删除队头元素。
33．已知两个长度分别为m和n的升序链表，若将它们合并为一个长度为m+n的降序链表，则最坏情况下的时间复杂度是（ ）。[2013年联考真题]
A．O（n）
B．O（m*n）
C．O（min（m,n））
D．O（max（m,n））【答案】D【解析】m和n是两个升序链表，长度分别为m和n，在合并过程中最坏的情况是两个链表中的元素依次进行比较，比较的次数是m和n中的最大值。
34．一个栈的入栈序列为1,2,3,……,n，其出栈序列是P，P，12P……P。若，则P＝3，则P可能取值的个数是（ ）。[2013年联3n23考真题]
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（logn）2
B．O（n）
C．O（nlogn）22
D．O（n）【答案】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对应的二叉树根结点的右子树上的结点个数是除第一棵树外其他所有树的结点总数。即M+M。23
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层结点的平衡二叉树含有最少的结点数是多少。 N表示深度为h的平衡二叉树中含有的最少结h点数，有N＝0，N＝1，N＝2……N＝N+N+1012hh-1h-2
由此可得N＝20。对应的平衡二叉树如下图所示。5
55．对有2个顶点e条边且使用邻接表存储的有向图进行广度优先遍历，其算法时间复杂度是（ ）。[2012年联考真题]
A．0（n）
B．0（e）
C．O（n+e）
D．O（n×e）【答案】C【解析】遍历图的过程实质上是对每个顶点查找其邻接点的过程。其耗费的时间则取决于所采用的存储结构。当用二维数组表示邻2接矩阵图的存储结构时，查找每个顶点的邻接点所需时间为O（n），其中n为图中顶点数。而当以邻接表作图的存储结构时，找邻接点所需时间为0（e），其中e为无向图中边的数或有向图中弧的数。由此，当以邻接表作存储结构时，深度优先搜索遍历图的时间复杂度为O（n+e）。即可得出正确答案。
56．深度为h的满m叉树的第k层有（ ）个结点（1≤k≤h）。[北京航空航天大学考研真题]k-1
A．m k
B．m-1 h-1
C．m h
D．m-1【答案】Ak-1【解析】满m叉树第k层必有m个结点。
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）结点的完全二叉树的高度为log（n+1）或logn+1；由完全二叉树类推到完全三叉树22可知，n个结点的完全三叉树的高度为log（n+1）或logn+1。33
60．下列关于最小生成树的叙述中，正确的是（ ）。[2012年联考真题]
Ⅰ．最小生成树的代价唯一 Ⅱ．所有权值最小的边一定会出现在所有的最小生成树中 Ⅲ．使用普里姆（Prim）算法从不同顶点开始得到的最小生成树一定相同 Ⅳ．使用普里姆算法和克鲁斯卡尔（Kruskal）算法得到的最小生成树总不相同
A．仅Ⅰ
B．仅Ⅱ
C．仅Ⅰ、Ⅲ
试读结束[说明：试读内容隐藏了图片]