中国大学数据结构_12答案(mooc完整答案)
69 min read中国大学数据结构_12答案(mooc完整答案)
1. 数据结构研究的中国内容及相关概念随堂测验
1、逻辑结构是大学答案答案与计算机无关的。逻辑结构在计算机中的数据表示就是存储结构。
2、结构数据结构的完整选择影响相应算法的效率。
3、中国根据数据元素之间关系的大学答案答案不同特性，通常将数据的数据逻辑结构分为下列四类：集合结构、线性结构、结构树和 。完整
2. 算法与算法分析随堂测验
1、中国分析以下算法的大学答案答案时间复杂度。 int fun(int n) { int i=1,数据j=100 ; while (i<n) { ++j; i+=2; } }
2、分析以下算法的结构时间复杂度。 int fun(int n) { int i=1,完整s=1 ; while (s<n) s+=++i ; return i; }
绪论
1、以下与数据的存储结构无关的术语是
A、循环队列
B、链表
C、哈希表
D、栈
2、数据结构中数据之间的逻辑关系被称为
A、数据的存储结构
B、数据的基础操作
C、程序的算法
D、数据的逻辑结构
3、算法分析的目的是
A、找出数据结构的合理性
B、研究算法中的输入和输出的关系
C、分析算法的效率以求改进
D、分析算法的易读性和文档性
4、数据项是数据的最小单位
5、每种数据结构都应具备三种基本运算：插入、删除和查找。
6、算法独立于具体的程序设计语言，与具体的计算机无关。
7、数据结构中评价算法的两个重要指标是
8、数据结构是由数据的 、 和 三部分组成。
程序设计基本原则
1、生命游戏在无边界的矩形网格上进行,被占据的单元称为活的，否则死的。哪一个单元是活的是由周围活的邻居数目决定。一个单元是活的，它有2个或3个活的邻居单元，则下一代它还是活的；有0个或1个、4个或4个以上的活的邻居，此单元在下一代会死亡；如果单元是死的，它有3个活的邻居，此单元在下一代会复活。
第二章 栈
1. 栈的定义随堂测验
1、设栈S和队列Q的初始状态均为空，元素a,b,c,d,e,f,g依次进入栈S。若每个元素出栈后立即进入队列Q，且7个元素出队的顺序是b,d,c,f,e,a,g，则栈S的容量至少是？
A、1
B、2
C、3
D、4
2、如进栈序列1,2,3,4,5.可能得到的出栈序列为？
A、1,2,5,3,4
B、3,1,2,5,4
C、3,2,5,4,1
D、1,4,2,3,5
3. 栈的应用实例：逆波兰计算器随堂测验
1、中缀表达式(A+B)*(C-D)/(E-F*G)的后缀表达式是
A、A+B*C-D/E-F*G
B、AB+CD-*EFG*-/
C、AB+C*D-E/F-G*
D、ABCDEFG+*-/-*
4. 栈的顺序实现随堂测验
1、顺序存储结构要求连续的存储区域，在存储管理上不够灵活，因此不常用。
2、对任何数据结构，链式存储结构一定优于顺序存储结构。
栈
1、若元素a,b,c,d,e,f依次进栈，允许进栈、退栈操作交替进行，但不允许连续三次进行退栈操作，则不可能得到的出栈序列是
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
2、表达式a*(b+c)-d的后缀表达式是
A、abcd*+-
B、abc+*d-
C、abc*+d-
D、-+*abcd
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
4、同一组不重复输入序列执行不同的入、出栈组合操作，所得结果也可能相同。
5、设栈采用顺序存储结构。若已有i-1个元素入栈，则将第i个元素入栈时，入栈算法的时间复杂性为O(i）。
6、栈是实现过程和函数等子程序必须的结构。
7、栈是受限的线性表，其运算遵循 的原则。
8、设a=6，b=4，c=2，d=3，e=2，则后缀表达式abc-/de*+的值为
9、有五个数据依次进栈：1，2，3，4，5.在各种出栈的序列中，以3，4先出栈的序列有 个。
栈的特性
1、所谓回文，是指从前向后顺读和从后向前倒读都一样的不含空白字符的串。例如did，madamimadam，pop即是回文。试编写一个算法（函数） ，以判断一个串是否是回文。
2、请写一个算法（函数），将一个数的质因数进行分解并输出。
栈的实现及应用
1、可包括后缀表达式求值、中缀表达式求值、括号匹配等栈的综合应用。 举例如下： 题目：中缀表达式求值 [问题描述] 中缀表达式是我们熟悉的表达式形式。为了能正确表示运算的先后顺序，中缀表达式中难免要出现括号。假设我们的表达式中只允许有圆括号。 读入一个浮点数为操作数的中缀表达式后，对该表达式进行运算。 要求中缀表达式以一个字符串的形式读入，可含有加、减、乘、除运算符和左、右括号，并假设该表达式以“#”作为输入结束符。 如输入“3.5*(20+4)-1#”，则程序运行结果应为83。
第三章 队列
1. 队列的定义随堂测验
1、栈和队列的共同点是
A、都是先进先出
B、都是后进先出
C、只允许在端点处插入和删除元素
D、没有共同点
2、栈和队列都是操作受限的线性表。栈是插入和删除只能在一端进行的线性表；队列是插入在一端进行，删除在另一端进行的线性表。
2. 顺序队列随堂测验
1、已知循环队列存储在一维数组A[0..n-1]中，且队列非空时front和rear分别指向队头元素和队尾元素。若初始时队列为空，且要求第1个进入队列的元素存储在A[0]处，则初始时front和rear的值分别是
A、0,0
B、0，n-1
C、n-1,0
D、n-1，n-1
2、循环队列的引入，目的是为了克服
顺序队列
1、为解决计算机主机与打印机之间速度不匹配问题，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是
A、栈
B、队列
C、树
D、图
2、已知循环队列存储在一维数组A[0..n-1]中，且队列非空时front和rear分别指向队头元素和队尾元素。若初始时队列为空，且要求第1个进入队列的元素存储在A[0]处，则初始时front和rear的值分别是
A、0，0
B、0，n-1
C、n-1，0
D、n-1，n-1
3、允许对队列进行的操作有
A、对队列中元素排序
B、取出最近进队列的元素
C、在队头元素之前插入元素
D、删除队头元素
4、栈和队列都是顺序存取的线性表，但它们对存取位置的限制不同。
5、通常使用队列的FILO特性进行函数或过程的调用。
6、循环队列是逻辑上形成了环状，物理实现上仍然是连续的数组。
7、已知一循环队列的存储空间为[m..n]，其中n>m，队头和队尾指针分别为front和rear，则此循环队列判断队满的条件是
8、循环队列容量为Q，当rear<front时，队列的长度为
队列的顺序实现
1、如果允许在循环队列的两端都可以进行插入和删除操作，请写出循环队列的类型定义，并写出“从队尾删除”和“从队头插入”的算法。
第四章 链栈和链队列
2. 栈的链式实现随堂测验
1、和顺序栈相比，链栈有一个比较明显的优势是
A、通常不会出现栈满的情况
B、通常不会出现栈空的情况
C、插入操作更容易实现
D、删除操作更容易实现
3. 队列的链式实现随堂测验
1、用单链表表示的链式队列的队头在链表的 位置。
A、链头
B、链尾
C、链中
D、位置可任意
2、在链式队列中，即使不设置尾指针也能进行入队操作。
3、在链式队列中执行出队操作是在队头进行的，故不可能改变尾指针的值。
栈和队列
1、队列的“先进先出”特性是指
A、最后插入队列中的元素总是最后被删除
B、当同时进行插入、删除操作时，总是插入操作优先
C、每当有删除操作时，总要先做一次插入操作
D、每次从队中删除的总是最早插入的元素
2、四个元素1，2，3，4依次进栈，出栈次序不可能出现的情况是
A、1，2，3，4
B、4，1，3，2
C、1，4，3，2
D、4，3，2，1
3、若用单链表来表示队列，下列几种数据结构中最合适的是
A、带尾指针的非循环链表
B、带尾指针的循环链表
C、带头指针的非循环链表
D、带头指针的循环链表
4、设尾指针的循环链表表示队列，则入队和出队算法的时间复杂度均为O（1）。
5、栈和队列都是线性表，只是在插入和删除时受到了一些限制。
6、已知链队列的头尾指针分别是f和r，则将值x入队的操作序列是
7、用循环链表表示的队列长度为n，若只设头指针，则出队和入队的时间复杂度分别是 和 。
8、用S表示入栈操作，X表示出栈操作，若元素入栈顺序为1，2，3，4，为了得到1，3，4，2的出栈顺序，相应的S和X操作串为 。
栈和队列的综合应用
1、小猫钓鱼纸牌游戏 [问题描述] A和B两个同学玩简单的纸牌游戏，每人手里有n张牌，两人轮流出牌并依次排列在桌面上，每次出掉手里的第1张牌，出牌后如果发现桌面上有跟刚才打出的牌的数字相同的牌，则把从相同的那张牌开始的全部牌按次序放在自己手里的牌的末尾。当一个人手中的牌先出完时，游戏结束，对方获胜。 如n为5，A手里的牌依次为2 3 5 6 1，B手里的牌依次为1 5 4 2 9； A出2； B出1； A出3； B出5； A出5，发现前面有一张5，则把两个5都拿掉，这时他手里有6 1 5 5； 桌子上的牌依次为2 1 3； B出4； A出6； B出2，发现前面有一张2，则把从2开始的牌全部拿掉，这时他手里有9 2 1 3 4 6 2； 桌子上没有牌了； A出1； B出9； A出5； B出2； 依次类推，直到某人先出完牌为止，则对方是胜者。 编写程序，利用栈和队列，判断谁是胜者。
第五章 线性表和串
1.线性表的概念和顺序实现随堂测验
1、查找顺序表中i号元素的直接前驱结点时，___________。
A、查找时间为O(n)
B、查找时间为O(1)
C、查找结点的次数约为n/2
D、找不到
2、设线性表(a0，a1，…，an-1)以顺序存储结构存储，每个元素占用4个存储单元，a0的基地址为0，则线性表的第k号元素ak的存储位置为 。
3、在一个长度为n的顺序表中的第position（0≤position≤n）个位置插入某个元素时，需向后移动 个元素。
2.单链表的基本操作实现随堂测验
1、设p为指向单循环链表上某内部结点的指针，则查找p指向结点的直接前驱结点时，___________。
A、查找时间为O(n)
B、查找时间为O(1)
C、查找结点的次数约为n/2
D、找不到
3.线性表的其他链式存储及存储结构比较随堂测验
1、若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用________存储方式最节省时间。
A、顺序存储结构
B、单链表存储结构
C、单向循环链表
D、双向链表
2、In a doubly linked list, each node has links to the previous and next nodes in the list.
3、对于双向链表,在两个结点之间插入一个新结点需修改的指针共______个。
线性表
1、线性表是一个（ ）。
A、有限序列，可以为空
B、有限序列，不能为空
C、无限序列，可以为空
D、无限序列，不能为空
2、单链表中增加一个头结点的目的是（ ）
A、使单链表至少有一个结点
B、标识表结点中首结点的位置
C、方便运算的实现
D、说明单链表是线性表的链式存储
3、对于双向循环链表，在p指针所指的结点之后插入s指针所指结点的操作应为（ ）
A、p->next=s; s->back=p; p->next->back=s; s->next=p->next;
B、p->next=s; p->next->back=s; s->back=p; s->next=p->next
C、s->back=p; s->next=p->next; p->next=s; p->next->back=s;
D、s->back=p; s->next=p->next; p->next->left=s; p->next=s;
4、能在O（1）时间内访问线性表的第i个元素的结构是
A、顺序表
B、单链表
C、单向循环链表
D、双向循环链表
5、线性表的插入、删除总是伴随着大量数据的移动。（ ）
6、在一个设有头指针和尾指针的单链表中，执行删除该单链表中最后一个元素的操作与链表的长度无关。（ ）
7、串长度是指串中不同字符的个数。（ ）
8、对于一个具有n个结点的单链表，在已知的结点*p后插入一个新结点的时间复杂度为 。
9、链接存储的特点是利用 来表示数据元素之间的逻辑关系。
10、删除长度为n的顺序表的第i个数据元素之前需要移动表中 个元素。（i<=1,i<=n)
线性表综合应用
1、题目：长整数运算 [问题描述] （1）实现线性表顺序存储结构、链式存储结构的基本操作，包括顺序表、单链表、双链表、单循环链表、双循环链表等； （2）设计并实现两个长整数的加、减、乘运算。
第六章 查找
1.查找的基本概念和顺序查找随堂测验
1、不带监视哨的顺序查找，成功查找时平均查找长度为：
A、n
B、(n-1)/2
C、n/2
D、(n+1)/2
2、带监视哨的顺序查找，失败查找时比较次数为n次。
3、顺序查找的时间复杂度是 。
2.有序表及不识别相等的二分查找随堂测验
1、用二分查找法对有n个元素的有序线性表查找一个元素时所需的平均比较次数是 。
A、
B、O(nlogn)
C、O(n)
D、O(logn)
2、二分查找必须是在有序表结构下进行。
3.识别相等的二分查找随堂测验
1、对一个长度为10的有序表进行识别相等的二分查找，查找成功时，关键字的比较次数至少为 次。
2、假设在有序表A[0..9]上进行不识别相等的二分查找，则比较1次查找成功的元素的数组下标为 号。
4.二分查找比较树及性能分析随堂测验
1、对于一个长度为n（n较大）的有序表，作不识别相等的二分查找的平均查找长度小于识别相等的二分查找的平均查找长度。
2、在基于关键字比较的查找算法中，时间复杂度的最好性能是。
5.散列函数随堂测验
1、散列法存储的基本思想是根据关键码值来决定 。
A、存储地址
B、元素的序号
C、平均检索长度
D、散列表空间
2、一个好的哈希函数应满足的条件不包含： 。
A、散列均匀
B、计算简单
C、对于某一个关键字，每次计算都应得到相同的结果。
D、不能产生冲突。
3、在散列函数H(key)=key MOD p中，一般来说，p应取 。
A、奇数
B、偶数
C、充分大的整数
D、素数
6.散列冲突处理随堂测验
1、对包含n个元素的散列表进行检索，平均检索长度为
A、
B、O(n)
C、
D、不直接依赖于n
2、装填因子小于1时,向散列表中存储元素时不会引起冲突。
3、若一个散列存储的线性表长度为n，用于散列的散列表长度为m,则装填因子为
单元测验
1、对线性表进行二分查找时，要求线性表必须 。
A、以顺序方式存储
B、以顺序方式存储，且结点按关键字值有序排列
C、以链接方式存储，且结点按关键字值有序排列
D、以链接方式存储
2、哈希表的地址区间为0-17，哈希函数为h(key)=key %17。采用线性探测法处理冲突，并将关键字序列{ 26,25,72,38,8,18,59}依次存储到哈希表中，则在哈希表中查找元素59需要搜索的次数为 。
A、2
B、3
C、4
D、5
3、若结点的存储地址与其关键字之间存在某种映射关系，则称这种存储结构为 。
A、顺序存储结构
B、链式存储结构
C、索引存储结构
D、散列存储结构
4、用二分法查找具有n个结点的顺序表时，查找每个结点的平均比较次数是 。
A、
B、
C、
D、O(n)
5、对一个长度为10的有序表，进行不识别相等的二分查找，关键字比较的次数至少为
A、4
B、1
C、3
D、5
6、对长度为4的顺序表进行查找，若查找第一个记录的概率为1/24，查找第二个记录的概率为1/6，查找第三个记录的概率为2/3，查找第四个记录的概率为1/8，则查找任意一个记录的平均查找长度为 。
A、23/8
B、20/8
C、17/8
D、14/8
7、查找算法的时间性能与对应判定树的高度一致。
8、哈希法存储中，冲突指的是 。
9、对线性表进行二分查找时，要求线性表必须 。
查找算法实现及性能比较
1、在顺序线性表中存放n个整数，n的值由用户输入确定，线性表可以是有序表或无序表。比较各查找算法在不同情况下的时间性能。 各查找算法的实测时间性能包括两个指标：算法执行的绝对时间和关键字的平均比较次数。 各查找算法要求评测查找成功与不成功的两种情形。 为了能比较出各种查找算法执行的绝对时间，需要对表中的数据进行较大量的查找，设为m次，m的值也由用户输入确定。当输入m为1000000时，则对线性表作1000000次查找。 （1）比较在有序表和无序表中进行顺序查找时，查找成功和查找失败时的算法执行的绝对时间和关键字的平均比较次数。 （2）比较在同一有序表中进行顺序查找和二分查找时的时间性能。 （3）比较在同一有序表中进行非递归二分查找和递归二分查找的时间性能。
第七章 排序
1.排序基本概念、排序性能评价指标、内部排序的基本操作随堂测验
1、内排序要求数据一定要顺序方式存储。
2、排序的稳定性是指排序算法中的比较次数保持不变，且算法能终止。
3.选择排序随堂测验
1、排序方法中，关键字比较次数与记录的初始排列无关的是（）
A、简单选择排序
B、快速排序
C、直接插入排序
D、shell排序
2、采用简单选择排序，比较次数与移动次数分别为（）
A、O(n), O(logn)
B、O(logn),O(n*n)
C、O(n*n),O(n)
D、O(nlogn),O(n)
3、直接选择排序算法的时间复杂度为O()，不受数据初始排列的影响。
4.希尔排序随堂测验
1、对序列{ 15，9，7，8，20，-1，4}用希尔排序方法排序，经过一趟后序列变成了{ 15，-1，4，8，20，9，7}，则该次采用的增量是（）
A、1
B、4
C、3
D、2
2、由于希尔排序的最后一趟与直接插入排序过程相同，因此前者一定比后者花费的时间更多。
3、用希尔方法排序时，若关键字的初始排序杂乱无序，则排序效率很低。
6.归并排序随堂测验
1、将两个各有N个元素的有序表归并成一个有序表，其最少的比较次数是（ ）
A、N
B、2N-1
C、2N
D、N-1
2、归并排序要求的辅助空间最多。
3、在任何情况下，归并排序都比简单插入排序快。
7.快速排序随堂测验
1、快速排序算法在最好情况下的时间复杂度是（）
A、O(n)
B、O()
C、O()
D、O()
2、快速排序总比简单排序要快。
3、快速排序的速度在所有排序方法中最快，而且所需辅助空间也最少。
9.堆排序随堂测验
1、已知关键字序列5，8，12，19，28，20，15，22是小顶堆，插入关键字3，调整得到的小顶堆是（）
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
2、以下序列不是堆的是（）
A、（100，85，98，77，80，60，82，40，20，10，66）
B、（100，98，85，82，80，77，66，60，40，20，10）
C、（10，20，40，60，66，77，80，82，85，98，100）
D、（100，85，40，77，80，60，66，98，82，10，20）
3、堆是满二叉树。
4、堆肯定是一棵平衡二叉树。
10.排序算法比较随堂测验
1、下列给出的四种排序方法中，（）排序法是不稳定性排序法。
A、插入
B、冒泡
C、二路归并
D、堆
2、下列给出的四种排序方法中，排序过程中的比较次数与排序方法无关的是（）
A、选择排序法
B、插入排序法
C、快速排序法
D、堆排序法
3、在待排序数据基本有序的情况下，快速排序的效果最好。
11.基数排序随堂测验
1、对{ 05，46，13，55，94，17，42}进行基数排序，一趟排序的结果是（）
A、05，46，13，55，94，17，42
B、05，13，17，42，46，55，94
C、42，13，94，05，55，46，17
D、05，13，46，55，17，42，94
2、基数排序只适用于以数字为关键字的情况，不适用以字符串为关键字的情况。
排序单元测验
1、为实现快速排序算法，待排序序列宜采用的存储方式是（）
A、顺序存储
B、散列存储
C、链式存储
D、索引存储
2、已知小顶堆为8，15，10，21，34，16，12，删除关键字8之后需要重建堆，在此过程中，关键字之间的比较数是（）
A、1
B、2
C、3
D、4
3、下列几种排序方法中，要求内存量最大的是（）
A、归并排序
B、快速排序
C、插入排序
D、选择排序
4、就平均性能而言，目前最好的内排序方法是（）排序方法。
A、冒泡
B、希尔插入
C、交换
D、快速
5、排序趟数与序列的原始状态有关的排序方法有（）排序法。
A、插入
B、选择
C、冒泡
D、快速
6、在下列排序中，（）方法的平均时间复杂度为O（nlogn）。
A、选择排序
B、快速排序
C、归并排序
D、基数排序
7、若某内排序算法不稳定，则该算法没有实用价值。
8、直接选择排序算法的时间复杂度为，不受数据初始排列的影响。
9、（101，88，46，70，34，39，45，58，66，10）是堆。
10、对n个记录的表r[1..n]进行简单选择排序，所需进行的关键字间的比较次数为
11、快速排序在 情况下最易发挥其长处。
排序算法比较
1、（1）编写程序创建一些整数文件用于排序。创建的这些文件可以根据需要生成不同的长度，如长度分别为20，200和2000，以正序、逆序、随机顺序的方式创建这些文件，通过把所有这些测试数据保存在文件中（而不是每次在测试程序时用随机数生成），可以使用同样的数据去测试不同的方法，因此会更易于比较这些方法的性能。 （2）数据表采用顺序存储结构，实现插入排序，选择排序，希尔排序，归并排序，快速排序，堆排序等排序，并对这些算法的实现效率进行比较和分析。 （3）排序的指标包含：运行时间，比较次数，移动次数。
第八章 二叉树
1.二叉树的概念随堂测验
1、二叉树的度是2。
2、二叉树是一种层次型的数据结构。
3、3个结点的二叉树具有 种不同形态。
2.二叉树的性质随堂测验
1、在高度 h 的 ，不在最下层的每个结点的度都为2。
A、满二叉树
B、二叉树
C、完全二叉树
D、单支二叉树
2、一棵具有100个结点的完全二叉树，其叶结点的个数为： 。
3、有1023个结点的二叉树的最小高度是 。
3.二叉树的遍历随堂测验
1、先序和后序序列正好相反的二叉树一定是 的二叉树。
A、任何一个结点都无左孩子
B、高度等于结点的个数
C、任何一个结点都无右孩子
D、空或只有一个结点
2、在二叉树的先序、中序和后序序列中，所有叶子结点的先后次序 。
A、都不相同
B、完全相同
C、先序和中序相同，而与后序不同
D、中序和后序相同，而与先序不同
3、由一棵二叉树的先序和后序序列可以唯一确定该二叉树。
4.二叉树的存储和实现随堂测验
1、n个结点的二叉树，若用二叉链表作为存贮结构，则非空链域的个数为 （ ） A. n B. 2n C. n-1 D. n+1
A、n
B、2n
C、n-1
D、n+1
2、不使用递归，也能实现二叉树的先序遍历。
3、二叉链表的每个结点包含2个指针域，分别指向该结点的左右孩子结点。
4、对二叉树层次遍历的算法需要使用的辅助数据结构是 。
5.哈夫曼树与哈夫曼编码随堂测验
1、哈夫曼树中，权值越大的叶子离根越近。
2、哈夫曼编码中，任意一个字符的编码不是其它字符编码的前缀部分。
3、n个叶子结点的哈夫曼树的总结点数是 。
6.二叉查找树及查找随堂测验
1、任何非空二叉查找树值最小的元素结点一定没有右孩子。
2、任何非空二叉查找树最大的元素结点一定有双亲结点。
3、两棵二叉排序树，所有结点存储的关键字集合相同，但形状不同，则对它们作 遍历，可得到相同的序列。
7.二叉查找树下的插入算法随堂测验
1、输入一个递增序列，通过n次插入算法的调用，创建出的二叉查找树是一棵 二叉树。
A、右单支
B、左单支
C、平衡二叉树
D、随机形态
2、在一棵二叉查找树下插入一个新结点，则新结点成为一个叶子。
8.二叉查找树下的删除算法随堂测验
1、在一棵二叉查找树下删除一个度为2的结点，可以用该结点的左子树上的最小值去替换该结点的值，然后删除这个值最小的结点。
2、二叉查找树的结点删除算法时间复杂度为O(logn)
二叉树
1、由三个结点可以构造出多少种形状不同的二叉树?
A、2
B、3
C、4
D、5
2、二叉树度为2的结点为3个，度为1的结点为4个，则度为0的结点是多少个？
A、2
B、3
C、4
D、5
3、假定根结点的层次为1，则一棵具有36个结点的完全二叉树的高度为 （ ）
A、5
B、6
C、7
D、8
4、完全二叉树中，若一个结点没有右孩子，则它必是树叶。
5、对二叉树的先序遍历和层次遍历，都是递归定义的遍历方法。
6、二叉树结点的左右孩子是严格区分左右的。
7、对n个结点的二叉树进行先序遍历，算法时间复杂度是： 。
8、双亲结点是同一个的结点之间互为 结点。
9、以权值{ 2，5，7，9，12}构造哈夫曼树，并设计的哈夫曼编码，哈夫曼编码的最大长度是几位二进制位？
10、二叉树的中序序列和后序序列分别为：DBHEAFICG和DHEBIFGCA，则其先序序列为：
二叉查找树
1、下列选项中（ ）可能是在二叉排序树中查找35时所比较的关键字序列。
A、2,25,40,39,53,34,35
B、25,39,2,40,53,34,35
C、53,40,2,25,34,39,35
D、39,25,40,53,34,2,35
2、中根遍历一棵二叉排序树所得到的结点访问序列是一个怎样的序列？
A、递增或递减
B、递减
C、递增
D、无序
3、若在一棵二叉排序树T1中插入一个结点后再删除该结点，得到一棵二叉排序树T2，则T1一定与T2相同。
4、若在一棵二叉排序树T1中删除一个结点后再插入该结点，得到一棵二叉排序树T2，则T1一定与T2相同。
5、在二叉排序树上删除一个结点时，不必移动其他结点，只要将该结点的父结点的相应指针域置空即可。
6、二叉排序树下的查找性能与二分查找的时间性能一致。
7、如果在二叉查找树T上先插入x，再插入y得到的二叉查找树A； 在二叉查找树T上先插入y，再插入x得到的二叉查找树B； 则A和B的结构肯定是不同的。
8、当所有结点关键码都相等时，用这些结点构造的二叉排序树只有 。
二叉树的基本操作实现
1、对二叉树进行各种基本操作。 二叉树基本操作包括： 1、通过先序和中序序列，构造二叉树 2、递归先序、中序、后序遍历 3、非递归中序遍历 4、层序遍历 5、求二叉树的深度、宽度 6、统计度为0，1，2的结点数 7、按先序遍历次序输出每个结点的层次 8、查找值为x的结点，找值为x的结点的兄弟 9、插入值为x的结点 10、删除值为x的结点。
通过两个序列创建二叉树
1、已知一棵二叉树的中序和层序序列分别是DGBAECHF和ABCDEFGH。画出二叉树。
哈夫曼树的构造
1、以权值（20,4,7,11,32,6,5,15）创建一棵哈夫曼树。
第九章 多叉树
1.树的定义、存储和遍历随堂测验
1、树是一种逻辑关系，表示数据元素之间存在的关系为（）
A、集合关系
B、一对一关系
C、一对多关系
D、多对多关系
2、在下列存储形式中，哪一个不是树的存储形式？（）
A、双亲表示法
B、孩子链表表示法
C、孩子兄弟表示法
D、顺序存储表示发
3、在含有n个结点的树中，边数只能是n-1条。
2.树和森林与二叉树的转换随堂测验
1、设森林F中有三棵树，第一、第二、第三棵树的结点分别为M1，M2和M3.与森林F对应的二叉树根结点的右子树上的结点个数是（）
A、M1
B、M1+M2
C、M3
D、M2+M3
2、必须把一般树转换成二叉树后才能进行存储。
多叉树
1、将森林转换为对应的二叉树，若在二叉树中，结点u是结点v的父结点的父结点，则在原来的森林中，u和v可能具有的关系是（）。
A、兄弟关系
B、父子关系，或者兄弟关系
C、父子关系，或者u的父结点与v的父结点是兄弟关系
D、父子关系，或者兄弟关系，或者u的父结点与v的父结点是兄弟关系
2、在一颗度为4的树T中，若有20个度为4的结点，10个度为3的结点，1个度为2的结点，10个度为1的结点，则树T的叶结点个数是（）。
A、41
B、82
C、113
D、122
3、将森林F转换成对应的二叉树T，F中的叶结点的个数等于（）。
A、T中叶结点的个数
B、T中度为1的结点的个数
C、T中左孩子指针为空的结点个数
D、T中右孩子指针为空的结点个数
4、树的父链表示法其实就是用数组表示树的存储结构。
5、树有先根遍历和后根遍历，树可以转化为对应的二叉树，树的后根遍历与其对应的二叉树的后根遍历相同。
6、将一棵树转换成二叉树后，根结点没有左子树。
第十章 图
1. 图的定义及术语随堂测验
1、下列关于无向连通图特性的叙述中，正确的是 （1）所有顶点的度之和为偶数 （2）边数大于顶点个数减1 （3）至少有一个顶点的度为1
A、只有（1）正确
B、只有（2）正确
C、（1）和（2）正确
D、（1）和（3）正确
2、若无向图G=（V，E）中含有7个顶点，要保证图G在任何情况下都是连通的，则需要的边数最少是
A、6
B、15
C、16
D、21
2. 图的存储随堂测验
1、设图的邻接矩阵A如下所示，各顶点的度依次是（）。
A、1，2，1，2
B、2，2，1，1
C、3，4，2，3
D、4，4，2，2
2、无向网（加权图）的邻接矩阵是（ ）矩阵。
A、下三角
B、上三角
C、稀疏
D、对称
3、无向图的邻接矩阵一定是对称矩阵，有向图的邻接矩阵一定是非对称矩阵。
3. 图的深度优先搜索遍历随堂测验
1、需要借助一个队列来实现DFS算法。
4. 图的广度优先搜索遍历随堂测验
1、对有n个结点、e条边且使用邻接表存储的有向图进行广度优先遍历，其算法时间复杂度是（ ）。
A、O（n）
B、O（e）
C、O（n+e）
D、O（n*e）
5. 拓扑排序随堂测验
1、若一个有向图的邻接矩阵中，主对角线以下的元素均为零，则该图的拓扑序列（）
A、存在
B、不存在
C、不能确定
D、一定唯一确定
2、下面哪一方法可以判断出一个有向图是否有环（回路）？
A、深度优先遍历
B、拓扑排序
C、求最短路径
D、求关键路径
3、拓扑序列的最后一个顶点必定是（ ）的顶点
7. 最小生成树随堂测验
1、任何无向图都存在生成树。
2、一个带权的无向连通图的最小生成树的权值之和是唯一的。
图综合应用
1、若用邻接矩阵存储有向图，矩阵中对角线以下的元素均为零，则关于该图拓扑序列的结论是（）
A、存在且唯一
B、存在但不唯一
C、存在，可能不唯一
D、无法确定是否存在
2、以下图的叙述中，正确的是（）
A、图与树的区别在于图的边数大于或等于顶点数
B、假设有图G=(V,{ E})，顶点集，，则和构成G的子图
C、无向图的连通分量指无向图中的极大连通子图
D、图的遍历就是从图中某一顶点出发访遍图中其余顶点
3、设无向图的顶点个数为n，则该图最多有（）条边
A、n-1
B、n(n-1)/2
C、n(n+1)/2
D、
4、无向连通图的最小生成树是唯一的。
5、若有向图不存在回路，即使不使用访问标志位，同一结点也不会被访问两次。
6、采用邻接表存储的图，其广度优先遍历类似于二叉树的先序遍历。
7、已知一个图的邻接矩阵表示，删除所有从第i个结点出发的边的方法是
8、Prim（普里姆）算法适用求 的网的最小生成树。
图的综合应用
1、给定n个小区之间的交通图，若小区i和小区j之间有直达道路，则将顶点i和顶点j用边连接，边上面的权重表示该条道路的长度。现在要从这n个小区中选择一个建立一所大型超市，问选哪个小区才能使得离超市最远的小区到达超市的路程最短？设计一个解答上述问题的算法，并给出具体的实例。
