数据结构---考研题_用链接方式存储的队列,在进行删除运算时

目录

第1章：绪论考研题及解析 2
1.1．选择题 2
1.2．判断题 3
1.3．填空题 4
1.4．回答题 4
第2章：线性表考研题及解析 4
2.1．填空题 4
2.2 选择题 5
2.3．判断题 5
2.4. 算法题 5
第3章：栈的考研题及相关解析 7
3.1 选择题 7
3.2 判断题 7
3.3 填空题 7
第4章：队列的考研题及相关解析 8
4.1 选择题 8
4.2 判断题 8
4.3 填空题 9
第6章：数组和广义表的考研题及相关解析 9
6.1 填空题 9
6.2 选择题 9
第7章：二叉树和树的考研题及相关解析 10
7.1 填空题 10
7.2 选择题 11
7.3 判断题 12
7.4 算法题 12
第8章：图论的考研题及相关解析 13
8.1 填空题 14
8.2 选择题 15
8.3 判断题 17
8.4 解答题 17
第11章：排序考研题及相关解析 18
11.1 选择题 19
11.2 判断题 20
11.3 填空题 21
11.4 简答题 23

第1章：绪论相关习题及解析

1.1选择题

1. 计算机算法指的是（ ），它必须具备（ ）这三个特性。
   （1） A. 计算方法 B. 排序方法
   C. 解决问题的步骤序列 D. 调度方法
   （2） A. 可执行性，可移植性，可扩充性
   B. 可执行性，确定性，有穷性
   C. 确定性，有穷性，稳定性
   D. 易读性，稳定性，安全性
   答案：C B
   解析：（1）算法是对特定问题求解步骤的一种描述，是指令的有限序列，其中每一条指令表示一个或多个操作。（2）一个算法应该具有有穷性，确定性，可行性，零个或多个输入，一个或多个输出等特征。
   2．以下属于逻辑结构的是（ ）
   A. 顺序表 B. 哈希表 C. 有序表 D. 单链表
   答案：C
   解析：顺序存储结构是把逻辑上相邻的数据元素存储在物理位置也相邻的存储单元里，数据元素之间的逻辑关系是由存储单元的邻接关系来体现。
   3.以下与数据的存储结构无关的术语是（ ）
   A.循环列队 B. 链表 C. 哈希表 D. 栈
   答案：D
   解析：数据的存储结构包括四种，它们分别是顺序存储结构，链式存储结构，索引存储 结构，哈希存储结构。
   4.以下哪个数据结构不是多型数据类型（ ）
   A.栈 B. 广义表 C. 有向图 D. 字符串
   答案：D
   解析：多形数据结构是指其值的成分不确定的数据类型。它其中的数据元素可以是整数， 实数，字符，字符串，也可以是更为复杂的结构体类型。
   5.连续存储设计时，存储单元的地址（ ）
   A.一定连续 B. 一定不连续
   C. 不一定连续 D. 部分连续，部分不连续顺序存储结构
   答案：A
   解析：把逻辑上相邻的数据元素存储在物理位置也相邻的存储单元里，数据元素间的逻 辑关系是由存储单元的邻接关系来体现。
   6.以下关于算法的说法是错误的是（）
   A. 算法必须最终由计算机程序来实现
   B. 为解决某种问题的算法同为该问题写的程序的含义相同
   C. 算法的可行性是指指令不能有二义性
   D. 以上几个都是错误的
   答案：D
   解析：（1）算法是对特定问题求解步骤的一种描述，是指令的有限序列，其中每一条 指令表示一个或多个操作。
   （2）一个算法应该具有有穷性，确定性，可行性，零个或多个输入，一个多个输出等
   （3）算法的要求：a正确性：算法的执行结果应当满足预先规定的功能和性能要求， 可读性:一个算法应当思路清晰，层次分明，简单明了，易读易懂，c健壮性:输入不合 法数据时，应能适当处理，不至引起严重后果，d通用性：算法应具有一般性，即算法 的处理结果对于一般的数据集合都成立，e高效率与低存储量需求:“高效率”指的是算 法执行的时间要快，“低存储量需求”指算法执行过程中所需要的最大存储空间要小。 在一般情况下，两者与问题的规模有关，且“高效率”与“低存储”是一对矛盾体。
2. 从逻辑上来看，可以把数据结构分为（ ）两大类
   A. 动态结构，静态结构 B顺序结构，链式结构
   C. 线性结构，非线性结构 D.初等结构，构造性结构
   答案：C
   解析：数据的逻辑结构可分为线性结构和非线性结构，线性结构又包括一般线性表，操 作受限线性表（栈，队列，串）和线性表推广（数组，广义表）。非线性结构又包括集 合，树形结构和图形结构。
3. 在下面一段程序中，对X的赋值语句最频度为（ ）
   FOR i： =1 TO n DO
   FOR j: +1 TO n DO
   X:=x+1
   A.0(2n) B. 0(n) C. 0(n^n) D . 0(log2n)
   答案：C
   解析：出现次数最多的一句是X=x+1;
   1.2．判断题
4. 数据的的逻辑结构是指数据的各数据项之间的逻辑关系（ ）
   答案：×
   解析：数据元素之间都不会是孤立的，他们之间都存在这样那样的关系，这种数据元素 之间的关系称为结构。根据数据元素间关系的不同特性，通常有集合结构，线性结构， 树形结构，图形结构等四种基本的逻辑结构。（数据元素是数据项的集合）。
   2.健壮的算法不会因非法的输入数据而出现莫名其妙的状态（ ）
   答案：√
   解析：算法的健壮性。
   3.在顺序存储结构中，有时也存储数据结构中元素之间的关系（ ）
   答案：×
   解析：数据元素之间的逻辑关系是由存储单元的邻接关系来体现。
   4.顺序存储方式的优点是存储密度大，且插入，删除运算效率高（ ）
   答案：×
   解析：顺序存储结构的优点是可以实现随机存取，每个元素占用最少的储存空间，即存 储密度大。 哈希存储结构的优点是检索，增加，删除结点的操作都很快。
   5.数据结构的基本操作的设置的最重要的准则是，实现应用程序与存储结构的独立（ ）
   答案：√
   6.数据的逻辑结构说明数据元素之间的顺序关系，它依赖于计算机的存储结构（ ）
   答案：×
   解析：数据元素之间都不会是孤立的，他们之间都存在这样那样的关系，这种数据元素之间的关系称为结构。根据数据元素间关系的不同特性，通常有集合结构，线性结构，树形结构，图形结构等四种基本的逻辑结构。

1.3．填空题
1.数据的物理结构包括数据元素的表示和数据元素间关系的表示。
2.对于给定的n个元素，可以构造的逻辑结构有集合结构，线性结构，树形结构，图形结构四种。
3数据的逻辑结构是指数据的组织形式，即数据元素之间逻辑关系的总体。而逻辑关系是指数据元素之间的关联方式或称“邻接关系”。
4.数据结构中评价算法的两个重要指标是算法的时间复杂度和空间复杂度。
5.数据结构是研讨数据的逻辑结构和顺序结构，以及他们之间的相互关系，并对与这种结构定义相应的操作，设计出相应的算法。
6.一个算法具有5个特性：有穷性，确定性，可行性，零个或多个输入，一个或多个输出。
1.4．回答题
1.在数据结构课程中，数据的逻辑结构，数据的存储结构及数据之间的运算之间存在着怎样的关系？
答：数据的逻辑结构反映的是数据元素之间的逻辑关系。数据的存储结构是依赖于计算 机语言，是具体的，通常，一个数据元素在计算机内用一块连续的存储单元来表示的。 数据的运算是为了有效的处理数据，将数据按照一定的逻辑结构组织起来，并选择适当 的存储方法存储数据，然后再对数据进行运算。数据的逻辑结构和存储结构是密不可分 的两个方面，一个算法的设计取决于所选定的逻辑结构，而算法的思想依赖所采用的存 储结构。
第2章：线性表习题及解析

1.1．填空题

1. 线性表中结点的集合是有限的，结点之间的关系是一对一的。
2. 一个长度为n的向量的第i个元素（1<=i<=n+1）之间插入一个元素时，需要向后移动n-i+1个元素。
3. 向一个长度为n的向量中删除第i个元素（1<=i<=n）之间插入一个元素时，需要向 前移动n-i个元素。
4. 在n个结点的单链表中，要删除已直结点*p，需要找到它的前驱结点的地址，其时间复杂度为O(n)。
5. 带头结点的空链表为空的操作是：首先分配一个类型为LinkList的结点空间，并让头指针head指向该结点然后将改结点的指针域赋值为空地址。
6. 设指针P指向单链表中的结点A，指针S指向被插入的结点X，则在结点A的前面插入结点X时的操作为：1）s->next=p->next; 2）p->next=s;3）t=p->data; 4）p->data=s->data; 5）s->data=t;
   1.2选择题
   1．设单链表中指针p指着结点A，若要删除A之后的结点（若存在），则需要修改指针的操作为（ ）
   A. p->next=p->next->next B. p=p->next
   C. p=p->next->next D. p->next=p
   答案：A
   解析：在删除操作中，首先要将待删除的信息返回，然后将ai+1到an的n-i个元素依 次向前移动一个位置，最后修改顺序表的长度length即可。要删除A之后的结点，只 需将A以后所有的结点都指向p->next。
   2．一维数组A进行顺序存储时，若起始地址为loc(A1)，元素长度为c，则A的第i个数组单元在存放地址loc(Ai)，等于（ ）
   A. loc(A1)+ic B. loc(A1)+(i-1) C. loc(A1)+ic+1 D. loc(A1)+(i+1)*c 答案：B
   解析：loc(ai+1)和第i个数据元素的存储位置Loc(ai)之间满足关系：Loc(ai+1)=loc(ai)+d。
7. 在某线性表中最常用的操作是最后一个元素之后插入一个元素和删除第一个元素，则（）和（）存储方式最节省运算空间
   A. 单链表 B. 仅有头指针的单循环链
   C. 双链表 D. 仅有尾指针的单循环链表
   答案：B
   解析：单链表的存储结构只需要修改指针就可以实现插入和删除操作，还可以降低时间 复杂度。

1.3．判断题
1．线性表在物理存储空间中也一定是连续的。（）
答案：×
解析：线性表有两种存储方式，顺序存储和链式存储，链式存储结构不要求连续存放。
2.顺序存储结构只能存储线性结构（ ）
答案：×
解析：顺序存储结构不仅适用存储线性结构，还可以用来存放非线性结构。
1.4. 算法题

1. 若有100个学生，每一个学生有学号，姓名，平均成绩，采用什么样的数据结构最方便，写出这些结构？
   解析：将学生的学号，姓名，平均成绩看成一个记录（含三个数据项），将100个这样 的记录存于数组中，因为没有增加和删除的操作，所以使用顺序存储结构最好。
   Typedef struct
   {
   int num;
   char name[10];
   float score；
   }node
   node student[100]
2. 写出顺序结构插入法的核心步骤。
   For(j=L->length-1;j>=i-1;j–)
   L->elem[j+1]=L->elem[j];
   L->elem[i-1]=e;
   L->length++;
   Return OK;
   3.已知有两个顺序表LA和LB，其元素均为非递减有序排列，编写一个算法，将他们合并成一个顺序表LC,要求LC也是非递减有序数列 。
   解析：算法设计：设表LC是一个空表，为使LC也是非递减有序排列，可设两个指针i， j 分别指向表LA和LB中的元素，LA.elem[i]>LB.elem[j]，则当 LB.elem[j]插入到表LC 中， LA.elem[i]<=LB.elem[j]，则当前先将LA.elem[i]插入到表LC中，如此进行下去，直到其中 的一个表被扫描完毕，然后再将未扫描完的表中剩余的所有元素放到表LC中。
   算法如下：
   #include<stdio.h>
   void merge(Seqlist *LA,Seqlist *LB,Seqlist *LC)
   {int i,j,k;
   i=0;j=0;k=0;
   while(i<=LA->last&&j<=LB->last)
   if(LA->elem[i]<=LB->elem[j])
   {LC->elem[k]=LA->elem[i];
   i++;
   k++;}
   else
   { Lc->elem[k]<=LB->elem[j]);
   j++;
   k++;}
   while(i<=LA->last)
   {LC->elem[K]=LA->elem[i];
   i++;
   k++;}
   while(i<=LB->last)
   {LC->elem[K]=LA->elem[j];
   j++;
   k++;}
   Lc->last=LA->last+LB->last+1;}

第3章：栈的考研题及相关解析
1.1选择题
1.对于栈操作数据结构的原则是（ ）
A. 先进后出 B. 后进先出 C. 后进后出 D. 不分顺序
答案：B
解析：栈是限制在表的同一端进行插入和删除的线性表，其运算遵循后进先出的原则。
2.有6个元素6,5,4,3,2,1的顺序进栈，问下列哪一个不是合法的出栈序列？（ ）
A.5 4 3 6 1 2 B. 4 5 3 1 2 6 C. 3 4 6 5 2 1 D. 2 3 4 1 5 6
答案：C
解析：C选项中的6和5出栈错误，在出栈时一定为5先出，6后出。
3.输入序列为ABC，可以变成CBA时，经过的栈的操作为（ ）
A. push,pop,push,pop,push,pop
B. push,push,push,pop,pop,pop
C. push,push,pop,pop,push,pop
D. push,pop,push,push,pop,pop
答案：B
解析：push代表入栈，pop代表出栈。先进行入栈，把ABC全部入栈，然后依次取出 来后为CBA。
4.表达式a*(b+c)-d的后缀表达式为（ ）
A.abcd*± B. abc+d- C. abc+d- D.-+abcd
答案：B
解析：后缀表达式为abc+d-。
1.2判断题
1.栈是实现过程和函数等子程序所必需的结构 （ ）
答案：√
2.若输出序列为1,2,3,4,5,6，则通过一个栈可以输出序列3,2,5,6,4,1. （ ）
答案：×
解析：若输出的序列为1,2,3,4,5,6时，进栈顺序为6,5,4,3,2,1,不可以输出序列3,2,5,6,4,1 时，先进栈6,5,4,3进入，再让3出,让2进,再让2出,再让4,5,6出，再让1进，再让1 出。所以输出的序列为3,2,4,5,6,1
3.栈和队列都是运算受限的线性表，只允许在表的两端进行运算（ ）
答案：×
解析：只允许在表的端点位置进行操作。
1.3填空题
1.栈是限制在表的同一端进行插入和删除的线性表，其运算遵循后进先出的原则。
2.队列是限定仅在表尾进行插入或删除操作的线性表。
3.表达式23+（（123-2）/4+345/7）+108/9的后缀表达式是231232-4/3457/+1089/++

第4章：队列的考研题及相关解析
1.1选择题
1.用链接方式存储的队列，在进行删除运算时（ ）
A.仅修改头指针 B. 仅修改尾指针
C. 头,尾指针都要修改 D. 头,尾指针可能要修改
答案：D
解析：队头指针front和队尾指针rear是两个独立的指针变量，所以在进行删除运算时， 头尾指针可能都要修改
2.用单链表表示的链式队列的队头在链表的（ ）位置。
A.链头 B. 链尾 C. 链中
答案：A
3.栈和队列的共同特点是（ ）
A.都是先进先出 B. 都是先进后出
C. 只允许在端点处插入和删除元素 D. 没有共同特点
答案：D
解析：栈的特点是先进后出的，队列的特点是先进先出的。
栈是限制在表的同一端进行删除和插入的线性表。而队列是一种运算受限制的线性表， 只允许插入的一端叫队尾，把允许删除的另一端叫队头。·
4.循环队列A[0…m-1]存放其元素值，用front和rear分别表示队头和队尾，则当前队列中的元素数是（ ）
A.(rear-front+m)%m B. rear-front+1
C. rear-front-1 D. rear-front
答案：A
解析：循环队列解决溢出问题时，用了取余的思想。该题用的就是这种办法。
1.2判断题
1.队列是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。（ ）
答案：×
解析：队列是一种运算受限制的线性表，插入与删除操作分别在表的两端进行，所以队 列又称后进后出或先进先出的线性表。
2.队列逻辑上是一个下端和上端既能增加又能减少的线性表。（ ）
答案:×
解析：队列是一种运算受限制的线性表，只允许插入的一端叫队尾，把允许删除的另一 端叫队头。
3.循环队列存在空间溢出问题。（ ）
答案：×
解析：解决溢出的方法之一是将队列的数据区看成头尾相接的循环结构，称其为循环队 列。
1.3填空题
1.队列的特点是先进先出。
2.循环队列的引入，目的是为了克服溢出问题。
3.区分循环队列的空与满的方法是只要队头指针和队尾指针在同一位置上队列就是空的。语句为front==rear。

第6章：数组和广义表的考研题

1.1填空题
1.二维数组A[12][16]采用列优先的存储方法，若每个元素各占三个存储单元，且第1个元素的地址为150，则元素A[9][6]的地址为354。
解析：二维数组按列优先存储公式有LOC（a ij）=LOC(a11)+((j-1)*m+(i-1))*d
带入可得答案为354。
2.二维数组A有m行n列，采用行优先存储，每个数据元素占K个字节，并且第一个元素的存储地址是LOC(A[1,1])，则数据元素A[i,j]的地址是LOC（aij）=LOC(a11) +((i-1)*n+(j-1))*K。
3.广义表（a（a,b）d,e,（i,j）k）的长度是6。
解析：广义表的长度是指元素的个数。
4.广义表A=（a,（b）,（c,d））,则表头为a，表尾为((b),(c,d))，长度为3。
解析：广义表的表头是第一个元素，表尾是除第一个元素外的其他元素。
1.2选择题
1.假设以行为主序存储二维数组，A=array[1…100,1…100],设每个数据元素占两个存储单元，基地址是10，则LOC[5,5]=( )
A.808 B. 818 C. 1010 D. 1020
答案：B
解析：以行为主序存储二维数组A[100][100]，利用公式LOC（aij） =LOC(a11)+((i-1)*n+(j-1))*d,带入可得答案为818。
2.二维数组a[0…8, 1…10]按行存放元素a[8,5]的起始地址与按列存放时元素（ ）的起始地址相同。
A.a [8,5] B. a [3,10] C.a [5,8] D.a [0,9]
答案：C
解析：按行存放LOC(aij)=LOC(a11)+((i-1)*n+(j-1))d,LOC(a85 )=LOC(a11)+67d
按列存储LOC（aij）=LOC(a11)+((j-1)m+(i-1))d,LOC(a85)=LOC(a11)+43d,
LOC(a3,10)=LOC(a11)+83d,LOC(a58)=LOC(a11)+67d,LOC(a09)=LOC(a11)+72d.
所以可得答案选C。
3.三维数组A[4][5][6]按行优先存储方法存储在内存中，若每个元素占2个存储单元，且数组中第一个元素的存储地址为120，则元素A[3][4][5]的存储地址为( )。
A.356 B. 358 C. 360 D. 362
答案：B
解析：据公式Loc(aijk)=Loc(a000)+(kmn+jm+i)*d.
其中, i=3,j=4,k=5,m=4,n=5,p=6,d=2.
代入公式得Loc(a345)=120+(100+16+3)*2=120+72=358
4.非空的广义表可与有跟有序的有向图对应，如果一个有跟的有向图中含有回路，那么它对应的广义表是（ ）。
A.线性表 B. 纯表 C. 再入表 D. 递归表
答案：C
解析：把允许结点共享的表称为再入表 。也就是题目中所描述的含有回路是同一个意 思。
5.稀疏矩阵的三元组存储方法_______。
A．实现转置运算很简单，只需将每个三元组中的行标和列标交换
B．是一种链式存储方法
C．矩阵的非零元个数和位置在操作过程中变化不大时较有效
D．比十字链表法更高效
答案：B
解析：三元组的存储是按照行优先且每行中的元素是按照列号从小到大的规律顺序存放 的。稀疏矩阵有两种压缩存储方式：顺序存储方式和链式存储方式。
6.稀疏矩阵一般的压缩存储方法有两种,即:（ ）。
A. 二维数组和三维数组 B. 三元组和散列
C. 三元组和十字链表 D. 散列和十字链表
答案：C
解析：稀疏矩阵一般的两种压缩存储方法：顺序存储方法、链式存储方法（三元组和十 字链表 ）。
7.已知广义表(( ),(a), (b, c, (d), ((d, f))))，则以下说法正确的是（ ）。
A．表长为3，表头为空表，表尾为((a), (b, c, (d), ((d, f))))
B．表长为3，表头为空表，表尾为(b, c, (d), ((d, f)))
C．表长为4，表头为空表，表尾为((d, f))
D．表长为3，表头为(())，表尾为((a), (b, c, (d), ((d, f))))
答案：A
解析：表头是一个空表，表尾是((a), (b, c, (d), ((d, f))))，表长即去掉最外的一个括号，数 里面的一对的括号的个数。
8.广义表L=((a,b,c)),则L的长度和深度分别为( )
A.1和1 B. 1和3 C. 1和2 D. 2和3
答案：C
解析：广义表的长度是指元素个数，深度是指表展开后所含括号的层数。

第7章：二叉树和树的考研题
1.1填空题
1.线索二元树的左线索指向其直接前驱结点，右线索指向其直接后继结点。
解析：在线索二叉树中，利用某结点空的左指针域（left）指出该结点在某种遍历序列 中直接前驱结点的存储地址，利用结点空的右指针域（right）指出该结点在某种遍历序 列中直接后继结点的存储地址。这些直接前驱结点和直接后继结点的指针被称为线索。
2.有6个结点的不同的二叉树有132颗。
解析：公式：B[n] = C[n,2n] / (n+1)，将n=6带入上述公式，可以得出，组合数C[n,2n] 的n为上标，2n为下标，将n=6代入公式，B[6] = C[6,12] / (6+1) =132
3.高度为h的m阶B树至少有F(h+2)-1个结点。
解析：设二叉树根的层次为1 如果 N(h) 是深度为 h 的平衡二叉树的最少结点数 对 于 h >= 1，有 N(h) = F(h + 2) – 1 成立 其中F代表Fibonacci数序列：1, 1, 2, 3, 5, 8, 13, 21, 34, 55。
4.二叉树中，第i层最多有2的i-1方个结点。
解析：二叉树的性质1：一颗非空二叉树的第i层上最多有2的i-1方个结点。
5.深度为K的二叉树最多有2的K次方-1个结点。
解析：二叉树的性质2：一颗深度为K的二叉树最多有2的i-1方个结点。
6.已知二叉树的中序序列为ADBEC，后序序列为ABDCE，则其先序序列为EDABC。
解析：由已知中序序列（左子树 根节点 右子树），后序序列（左子树 右子树 根节点），可以推出先序序列（根节点 左子树 右子树）。
7.二叉树由根结点，左子树，右子树等三个基本单元组成。
8.二叉树的先序序列和中序序列相同的条件是每个结点都无左孩子。
9.后序线索二叉树中结点的左线索指向其直接前驱结点，右线索指向其直接后继结点。
10.具有n个结点的满二叉树叶子结点的个数是[n/2]+1。
1.2选择题
1.含有n个顶点的图形成一个环，它的生成树个数为（ ）
A.1 B. n C. n(n-1)/2 D. n-1
答案：B
解析：每删去一条边就可以得到一个有n个顶点的道路，道路也是树（树无环的连通图），
那么一共有n种删法，这个本质就是破圈法。
2.设n,m为一颗二叉树上的两个结点，在中序遍历中，n在m前的条件是（ ）
A.n在m右方 B.n是m的祖先
C.n在m左方 D. n是m的子孙
答案：C
解析：题目已知条件是在中序遍历中，由中序序列（左子树 根节点 右子树），设A 为两者的最近的共同祖先(包括双亲），n在A的左子树、m在A的右子树，则中序遍 历时，n在m前。
3.引入线索二叉树的目的是（ ）
A.为了方便找到双亲 B. 加快查找结点的前驱结点或后继结点的速度
C. 使二叉树的遍历结果唯一 D. 为了能在二叉树中方便的进行插入与删除
答案：C
解析：由于序列可由不同的遍历方法得到，加入线索，可使遍历结果唯一。
4.在以下结论中，正确的是（ ）
①只有一个节点的二叉树的度为0
②二叉树的度为2.
③二叉树的左右子树可任意交换
④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树
A.①②③ B. ②③④ C. ②④ D. ①④
答案：D
解析：②二叉树的度不为2，③二叉树的左右子树不可交换。
5.某二叉树的中序序列为ABCDEFG，后序序列为BDCAFGE，则先序序列是（ ）
A.EGFACDB B. EACBDGF C. EAGCFBD D.以上都不对
答案：B
解析：由中序序列（左子树 根节点 右子树），后序序列（左子树，右子树，根节点），可以得出根节点是E，先序序列为（根节点，左子树，右子树），依次推理即可得出。
6.深度为h的满m二叉树 的第K层有（ ）个结点。
A.m的k-1次方 B.m的k次方-1
B.m的h-1次方 D. m的h次方-1
答案：A
解析：树的根节点为1，满二叉树第n层结点数肯定是前一层的m倍。
7.高度为K的二叉树最大的结点数为（ ）。
A.2的K次方 B. 2的K-1次方 C. 2的K次方-1 D. 2的K-1次方-1
答案：C
解析：二叉树的最大节点数，就是满二叉树的节点数，需要把根节点层次转换为1，那么高度就是K+1。所以最大节点数是2的K次方-1（满二叉树的节点总数公式）
8.一颗完全二叉树上有1001个结点，其中叶子结点的个数是（ ）
A.251 B. 500 C. 505 D. 以上答案都不对
答案：D
解析n = n。+ n1 + n2( n: 总结点个数，n。:无孩纸的结点个数（即叶子结点），n1:有一个孩子的结点个数，n2:有两个孩子的结点个数，结点要么有两个孩子，要么一个，要么没有），由完全二叉树性质可知，若给每个结点依次序标上1~n序号，序号为 i 的结点（假设有两个孩子存在）其左孩子序号为 2i（皆为偶数），右孩子序号为 2i + 1 （皆为奇数），故 1001 为右孩子，其父结点序号为 500 （ 2i + 1 = 1001 解得 i = 500 ）
故n2 = 500 （按规律501的孩纸序号应为501 * 2 = 1002 和 1003， 此题一共只有1001个结点，故501 没有孩子），n1要么为 0 要么为 1 ，奇数个结点时为最后一个叶子结点为右孩子，偶数个结点时最后一个为左孩子。此时 n1 = 0 (1001是右孩子)，n = n。+ n1 + n2，1001 = n。+ 0 + 500，n。= 501。
9. 在一颗三叉树中度为3 的结点数为2个，度为2 的结点数为1个，度为1 结点数为2个，则度薇的结点数为（ ）个。
A. 4 B. 5 C. 6 D. 7
答案：C
解析：树中结点数等于所有结点度数的和+1，所以2+1+2+X=23+12+21+X0+1，解得 X等于6。
9.设森林F对应的二叉树为B，它有M个结点，B的根节点为p,p的右子树结点个数为n,森林F中第一棵树的结点个数是（ ）
A.m-n B. m-n-1 C. n+1 D. 条件不足，无法确定
答案：A
解析： 根据二叉树与森林的对应关系，将森林F转换成对应二叉树B的规则如下：
①若森林F为空，则二叉树B为空。
②若森林F非空，则F中的第一棵树的根为二叉树B的根；第一棵树的左子树所构成的森林按规则转换成一个二叉树成为B的左子树，森林F的其他树所构成的森林按本规则转换成一个二叉树成为B的右子树。依此规则可知：二叉树B结点的个数减去其右子树的结点的个数就是森林F的第1棵树的结点的个数。
10．二叉树是非线性数据结构，所以（ ）
A.它不能用顺序存储结构存储
B.它不能用链式存储结构存储
C.顺序存储结构和链式存储结构都能存储
D.顺序存储结构和链式存储结构都不能使用
答案：C
解析：二叉树肯定能用链式方法存储，而且链式方法是目前最适合二叉树存储的方式；但是这道题目问的是能不能，而不是最好用，那么顺序存储也是可以的。我们可以按照层次来编号存储，第i号节点的左右孩子分别是2i和2i+1（当然存在的话），这样就可以用数组这类顺序结构来存放了，当然如果是用顺序二叉树这类结构很有特点的二叉树的话，用顺序结构比用链式还要好用，当然对于一般二叉树，链式比较好用。

1.3判断题
1.存在这样的二元树，对他采用任何次序的遍历，结果相同。（ ）
答案：√
解析：只有一个根节点的二叉树，无论什么遍历次序结果都一样的。
2.二元树就是结点为二的树。（ ）
答案：×
解析：二叉树的度不大于2，有序树的结点次序是相对于另一结点而言的，若有序树的 子树中只有一个孩子时，这个孩子的结点无须区分左右次序；二叉树无论孩子树是否为 2，均需确定左右次序。
3.完全二元树中，若一个节点没有左儿子，则必是树叶。（ ）
答案：√
解析：对完全二叉树的编号是由上而下，由左而右进行的，所以若某节点无左孩子，则 必然无右孩子。即为叶子结点。
4.满二叉树可能不是完全二叉树，完全二叉树也不可能是满二叉树。（ ）
答案：√
解析：满二叉树：除最后一层无任何子节点外，每一层上的所有结点都有两个子结点（最 后一层上的无子结点的结点为叶子结点）。也可以这样理解，除叶子结点外的所有结点 均有两个子结点。节点数达到最大值。所有叶子结点必须在同一层上。
完全二叉树：若一棵二叉树至多只有最下面的两层上的结点的度数可以小于2，并且最 下层上的结点都集中在该层最左边的若干位置上，则此二叉树成为完全二叉树。
所以说，满二叉树是完全二叉树的特例，因为满二叉树已经满了，而完全并不代表满。
5.一颗128个结点的完全二叉树，其深度最少为6.（ ）
答案：×
解析：根据二叉树的主要性质4:具有n个结点的完全二叉树的深度为[log2 n]+1.
带入公式可得深度为8.
6.完全树的叶结点都是在层数最大的一层。（ ）
答案：×
解析：满二叉树的叶子节点都在层次最大的一层，从满二叉树的最后一个叶子节点开始， 依次向前（向左）删除若干个叶子节点，得到一棵完全二叉树，被删叶子节点的上一层 （层次第二大的）节点因失去叶子，成为新的叶子节点。如此，叶子节点出现在最大层 和次大层。只有当最大层叶子节点删除完，才可以删除次大层叶子节点，此时次大层变 成新的最大层，叶子节点仍然只可能出现在层次最大的两层上。
7.二叉树中每个结点的两棵子树的高度差等于1。（ ）
答案：×
解析：二叉树中每个结点的两棵子树的高度差可以大于1.
8.二叉树中所有结点，如果不存在非空左子树，则不存在非空右子树。（ ）
答案：×
解析：不存在非空左子树，不一定不存在非空右子树。
9.二叉树中每个结点有两棵非空子树或有两棵空子树。（ ）
答案：×
解析：二叉树中每个结点有：①两棵非空子树；②两棵空子树；③一棵子树。
10.若二叉树用二叉链表作存贮结构，则在n个结点的二叉树链表中只有n—1个非空指针域。（ ）
答案：×
解析：假如有三个结点 一个头结点和两个子节点， 那么在头结点的指针域里面放的是两个子节点的地址， 在子节点里面的指针域里 都为NULL，这样 就有两个指针域非空 ，再假如有5个结点 头结点两个，左子树有两个，也符合N-1个非空指针域。
1.4算法题
1.已知一个非空二元树，其按先根和后根遍历的结果分别为：先根：C G B A H E D J F I，后根：G B C H E J I F D A。试将这样的二元树构造出来，若已知先根和后根的遍历结果，能否构造这颗二元树，为什么？
解析：根据树与二叉树的转换关系及树和二叉树的遍历定义可以推知，树或树林的先根 遍历序列与其转换后对应的二叉树的先序遍历序列相同；树或树林的后根遍历序列与其 转换后对应的二叉树的中序遍历序列相同。所以可以构造出这颗二元树。
2.8个字母的权分别为7,19,2,6,32,3,21,10，试构造出对应的哈夫曼树并为这八个数设计哈夫曼编码。
答案：
第8章：图论的考研题
1.1填空题
1.有向图G的强连通分量是指极大强连通子图。
2.一个连通图的生成树是一个极小连通子图。
3.为了实现图的广度优先搜索，除了一个标志数组标志已访问的图的结点外，还需要队列存放被访问的结点以实现遍历。
4.具有10个顶点的无向图，边的总数最多为45条。
解析：带入公式n(n-1)/2可得。
5.图的两种遍历方式是深度优先遍历和广度优先遍历。
6. 已知一有向图的邻接表存储结构如下图：
从顶点1出发，深度优先（DFS）遍历的输出序列是 1 3 4 5 2，
广度优先（BFS）遍历的输出序列是 1 3 2 4 5 。

7. 一个无向图有n个顶点和e条边，则所有顶点的度的和为 2e 。
   解析：无向图中，顶点的度数之和等于边数*2。与顶点数无关。
8. 已知一无向图G=(V,E),其中V={a,b,c,d,e}，E={(a,b),(a,d),(a,c),(d,c),(b,e)}，现在用某一种图的遍历方法从顶点a开始遍历图，得到的序列为abecd，则采用的是深度优先遍历方法。
   解析：深度优先遍历采用的是栈的思想，深度优先遍历是按照深度方向搜索，它类似与树的先根遍历。
9. 有n个顶点的有向图中,若要使任意两点间可以互相到达,则至少需要条弧n条
   解析：n条弧形成一个环。
   11.具有10个顶点的无向图,边的总数最多为45。
   解析：n个顶点的无向图最多有n(n-1)/2条边，所以答案是10×9/2=45。
   1.2选择题
   1.在一个无向图中，所有顶点的入度之和等于所有顶点的出度的（ ）倍
   A.1/2 B. 2 C. 1 D. 4
   答案：C
   解析：所有顶点的出度之和等于所有顶点的入度之和等于边数的二倍。
   2.设无向图的顶点个数为n，则该图最多有（ ）条边。
   A.n^2 B. n(n-1)/2 C. n(n+1)/2 D. 0
   答案：B
   解析：在一个无向图中，如果任意两个顶点之间都有一条边直接相连，则称该图为无 向完全图。在一个含有n个顶点的完全图中有n(n-1)/2条有向边。
   3.若让一个具有n个顶点的有向图是强连通图，则至少需要（ ）条弧。
   A.n B. n+1 C. 2n D. n(n-1)
   答案：D
   解析：强连通图，表示任意两个顶点都有可以到达的路径，根据递归推算：n=1,0条弧； n=2,2条弧；n=3，6条弧；n=4,12条弧……以此类推，让一个具有n个顶点的有向图是 强连通图，则至少需要n(n-1)条弧。所以选择D。
   4.设用邻接矩阵A表示有向图G的存储结构，则有向图G中顶点i的入度为（ ）。
   A.第i行非0元素的个数之和 B.第i列非0元素的个数之和
   C.第i行0元素的个数之和 D.第i列0元素的个数之和
   答案：B
   解析：顶点的入度：是指以该顶点为终点的弧的数目，（出度与行相关联，入度与列相 关联），所以排除A,C。而要求顶点的度数，度数与非零元素有关，所以选择B。
10. 设某有向图的邻接表中有n个表头结点和m个表结点，则该图中有（ ）条有向边。 A. n B.n-1 C.m D. m-1
    答案：C
    解析：有向图中，m个节点对应m条边，每一个边都是有向的。表头结点：（图的节 点）第一个元素的节点，也是头结点后面的第一个节点；表节点：便于操作所设置的节 点。
11. 对于一个具有n个顶点的无向连通图，它包含的连通分量的个数为( )
    A.0 B.1 C.n D.n+1
    答案：C
    解析：连通分量：无向图的极大连通子图。
12. 设无向图G中边的集合E={(a,b)，(a,e)，(a,c)，(b,e)，(e,d)，(d,f)，(f,c)}，则从顶点a出发进行深度优先遍历可以得到的一种顶点序列为（ ）。
    A. Aebcfd B.acfebd C. aedfcb D. aedfbc
    答案：D
    解析：深度优先遍历：类似于树的先根遍历；所做的图如下： 所以从a点出发进行深度优先遍历可以得到的顶点序列为： abedfc,aebcfd,acfdeb,aedcfb,abecfd,等等，但是，D选项，f与b顶点之间，有定点c,而 顶点c之前未被访问
13. 设完全无向图中有n个顶点，则该完全无向图中有( )条边
    A.n(n-1)/2 B. n(n-1)
    C. n(n+1)/2 D. (n-1)/2
    答案：A
    解析：完全无向图：无向图中，任意两个顶点之间都有一条边直接相连接，则称该图为 有向完全图。在一个含有n个顶点的无向完全图中有n(n-1)/2条边。
14. 下列说法不正确的是( )。
    A.图的遍历是从给定的源点出发每一个顶点仅被访问一次
    B.遍历的基本算法有两种:深度遍历和广度遍历
    C.图的深度遍历不适用于有向图
    D.图的深度遍历是一个递归过程
    答案：C
    解析：图的广度遍历不适用于有向图
15. 下列哪一种图的邻接矩阵是对称矩阵?( )
    A.有向图 B.无向图 C.AOV网 D.AOE网
    答案：B
    解析：无向图是没有方向的，所以它的邻接矩阵是对称的。AOV网是点表示活动的网 AOE网是边表示活动的网。
    1.3判断题
    1.如果不考虑结点到其自身的边，也不允许一条边在图中重复出现，则对于任何一个具有 n个结点的无向图，其边数小于等于n*(n-1)/2。（ ）
    答案：×
    解析：在一个含有n个顶点的无向图中至少有n(n-1)/2条有向边。
    2.若连通图上各边权值均不相同，则该图的最小生成树是唯一的。（ ）
    答案：√
    3.领接矩阵适用于有向图和无向图存储，但不能存储带权的有向图和无向图，而只能使用领接表来存储。（ ）
    答案：×
    解析：领接矩阵适用于稠密图，领接表适用于稀疏图。
    4.需要借助于一个队列来实现DFS算法（ ）
    答案：×
    解析：实现DFS算法需要出栈入栈的思想来完成，实现BFS算法需要借助一个队列。
    5.有e条边的无向图，在领接表中有e个结点（ ）
    答案：×
    解析：一个N个顶点的连通无向图中边的个数至少为N-1个。
    6.强连通图中任一顶点均可达（）
    答案：√
    解析：任意两点间可达的称为强连通图。
    7.强连通分量是无向图的极大强连通子图（ ）
    答案：×
    解析：首先要区分极大连通子图和极小连通子图，极大连通子图是无向图的连通分量，极大即要求该连通子图包含其所有的边；极小连通子图既要求保持图连通，又要使得边数最少的子图。无向图中的极大连通子图称为连通分量，而不是强连通分量。强连通分量表示在有向图中，若从顶点V到顶点W和从顶点W到顶点V之间都有路径，则称这两个顶点是强连通的。
    8.十字链表是无向图的一种存储结构（ ）
    答案：×
    解析：十字链表是有向图的另一种 链式存储结构 。该结构可以看成是将有向图的 邻接表 和逆邻接表结合起来得到的。用十字链表来存储有向图，可以达到高效的存取效果。同时，代码的可读性也会得到提升。
    9.一个有向图的邻接表和逆邻接表中结点的个数可能不等（ ）
    答案：√
    解析：邻接表和逆邻接表的表是一一对应的，边的总数也是相同的，节点个数也是一样 的
    10.用邻接矩阵存储一个图时,在不考虑压缩存储的情况下,所占用的存储空间大小与图中结点个数有关,而与图的边数无关（ ）
    答案：√
    解析：邻接矩阵是用一维数组存储图中顶点的信息，用矩阵表示图中顶点之间的邻接关 系。都是顶点之间的关系
    1.4解答题
    1.已知一个带权有向图G的顶点集V和边集E分别为： V = { v1，v2，v3，v4，v5}，E ={(v1，v2)，(v1，v3)，(v1，v4)，(v2，v4)，(v2，v5)，(v3，v4)，(v4，v5) }，E中各边对应的权值如下：(v1，v2)：3， (v1，v3)：10， (v1，v4)：7， (v2，v4)：5，(v2，v5)：7， (v3，v4)：9， (v4，v5)：15
    请完成： （共15分）
    （1）画出图G；（3分）
    （2）画出图G的邻接表表示；（3分）
    （3）写出从顶点v1出发进行深度优先搜索（DFS）产生的深度优先生成树；（4分）
    （4）写出从顶点v1出发进行广度优先搜索（BFS）产生的广度优先生成树；（4分）

2.下图是带权的有向图G的领接表表示法，求（1）以结点V1出发深度遍历图G所得的结点序列（2）以结点v1出发广度优先遍历图G所得的结点序列。

第11章：排序考研题及其解析
1.1选择题
1．折半查找不成功时，指针Low和High的关系是（ ）
A. Low

1.2判断题
1.希尔排序算法的时间复杂度为O（n^2）。（ ）
答案：×
解析：希尔排序算法的时间性能是所取增量的函数，其时间性能在O（n^{2）与O（nlog2}n） 之间。当n在某个特定的范围时，希尔排序的时间复杂度约为O（n^1.3），最坏情况 下希尔排序的时间复杂度为O（n^2）。
2. 快速排序是一种交换排序（ ）
答案：√
解析：快速排序通过一趟排序将要排序的数据分割成独立的两部分：分割点左边都是比 它小的数，右边都是比它大的数。然后再按此方法对这两部分数据分别进行快速排序， 整个排序过程可以递归进行，以此达到整个数据变成有序序列。
3. 用折半查找法的查找速度一定比用顺序查找法的查找速度快。（ ）
答案：×
解析：例如在一个数组中有10个元素.
1：第一个是要找的元素.
折半查找：先找第六（下标为5）个,再找第三个（下标为2）,然后是第二个（下标为1）, 最后是第一个（下标为0）…
顺序查找：只要找一次就ok了.
2：第10个是要找的元素.
折半查找：先找第六（下标为5）个,再找第八个（下标为7）,然后是第九个（下标为8）, 最后是第十个（下标为9）…
顺序查找：需要10次.
3：第三个是要找的元素.
折半查找：先找第六（下标为5）个,再找第三个（下标为2）
顺序查找：需要三次（效率一样）.
1.3填空题
1.在堆排序和快速排序中，如果从平均情况下排序的速度最快的角度来考虑最好选择快速排序，如果从节省存储空间的角度来考虑最好选择堆排序。
2.折半查找的存储结构仅限于线性表，而且是有序的。
3.若在线性表中采用折半查找法查找元素，该线性表应满足条件元素按值有序，且采用顺序存储结构。
解析：能采用折半查找法查找元素的线性表，必须是有序表，且是顺序存储的，不能死 链式存储的。
4.按排序过程依据的不同原则的关系，可以把排序方法分成插入类排序，交换类排序，选择类排序，归并排序和基数排序。

1.4简答题

1.试写出折半查找的递归算法。
#include <stdio.h>
int bin_search(int key[],int low, int high,int k)
{
int mid;
if(low>high)
return -1;
else{
mid = (low+high) / 2;
if(key[mid]==k)
return mid;
if(k>key[mid])
return bin_search(key,mid+1,high,k); /在序列的后半部分查找/
else
return bin_search(key,low,mid-1,k); /在序列的前半部分查找/
}
}

int main()
{
int n , i , addr;
int A[10] = {2,3,5,7,8,10,12,15,19,21};
printf(“The contents of the Array A[10] are\n”);
for(i=0;i<10;i++)
scanf("%d",&n); /输入待查找的元素/
addr = bin_search(A,0,9,n);
if(-1 != addr) /查找成功/
printf("%d is at the %dth unit is array A\n ",n,addr);
else printf(“There is no %d in array A\n”,n); /查找失败/
getchar();
return 0;
}