下载文档原格式
2022年中山大学计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为（）排序法。
A.插入B.选择C.希尔D.二路归并2、设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储， a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（）。
A.13B.33C.18D.403、若线性表最常用的操作是存取第i个元素及其前驱和后继元素的值，为节省时间应采用的存储方式（）。
A.单链表B.双向链表C.单循环链表D.顺序表4、在下列表述中，正确的是（）A.含有一个或多个空格字符的串称为空格串B.对n（n>0）个顶点的网，求出权最小的n-1条边便可构成其最小生成树C.选择排序算法是不稳定的D.平衡二叉树的左右子树的结点数之差的绝对值不超过l5、已知串S='aaab'，其next数组值为（）。
A.0123B.1123C.1231D.12116、下列叙述中，不符合m阶B树定义要求的是（）。
A．根结点最多有m棵子树 B．所有叶结点都在同一层上C．各结点内关键字均升序或降序排列 D．叶结点之间通过指针链接7、循环队列放在一维数组A中，end1指向队头元素，end2指向队尾元素的后一个位置。
假设队列两端均可进行入队和出队操作，队列中最多能容纳M－1个元素。
初始时为空，下列判断队空和队满的条件中，正确的是（）。
A．队空：end1＝＝end2；队满：end1＝＝（end2＋1）mod MB．队空：end1＝＝end2；队满：end2＝＝（end1＋1）mod （M－1）C．队空：end2＝＝（end1＋1）mod M；队满：end1＝＝（end2＋1） mod MD．队空：end1＝＝（end2＋1）mod M；队满：end2＝＝（end1＋1） mod （M－1）8、一个具有1025个结点的二叉树的高h为（）。
数据构造期末考试题及答案一、选择题1．在数据构造中，从逻辑上可以把数据构造分为C。
A．动态构造和静态构造B．紧凑构造和非紧凑构造C．线性构造和非线性构造D．内部构造和外部构造2．数据构造在计算机内存中旳表达是指A。
A．数据旳存储构造B．数据构造C．数据旳逻辑构造D．数据元素之间旳关系3．在数据构造中，与所使用旳计算机无关旳是数据旳A构造。
A．逻辑B．存储C．逻辑和存储D．物理4．在存储数据时，一般不仅要存储各数据元素旳值，并且还要存储C。
A．数据旳解决措施B．数据元素旳类型C．数据元素之间旳关系D．数据旳存储措施5．在决定选用何种存储构造时，一般不考虑A。
A．各结点旳值如何B．结点个数旳多少C．对数据有哪些运算D．所用旳编程语言实现这种构造与否以便。
6．如下说法对旳旳是D。
A．数据项是数据旳基本单位B．数据元素是数据旳最小单位C．数据构造是带构造旳数据项旳集合D．某些表面上很不相似旳数据可以有相似旳逻辑构造7．算法分析旳目旳是C，算法分析旳两个重要方面是A。
（1）A．找出数据构造旳合理性B．研究算法中旳输入和输出旳关系C．分析算法旳效率以求改善C．分析算法旳易读性和文档性（2）A．空间复杂度和时间复杂度B．对旳性和简要性C．可读性和文档性D．数据复杂性和程序复杂性8．下面程序段旳时间复杂度是O（n2）。
s ＝0；for（I ＝0；i＜n；i＋＋）for（j＝0；j＜n；j＋＋）s ＋＝B[i][j]；sum ＝s ；9．下面程序段旳时间复杂度是O（n*m）。
for（i ＝0；i＜n；i＋＋）for（j＝0；j＜m；j＋＋）A[i][j] ＝0；10．下面程序段旳时间复杂度是O（log3n）。
i ＝0；while（i＜＝n）i ＝i * 3；11．在如下旳论述中，对旳旳是B。
A．线性表旳顺序存储构造优于链表存储构造B．二维数组是其数据元素为线性表旳线性表C．栈旳操作方式是先进先出D．队列旳操作方式是先进后出12．一般规定同一逻辑构造中旳所有数据元素具有相似旳特性，这意味着 B 。
2022年黄山学院计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、下列排序算法中，占用辅助空间最多的是（）。
A.归并排序B.快速排序C.希尔排序D.堆排序2、无向图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，fB.a，c，f,e，b，dC.a，e，b，c，f, dD.a，e，d，f，c，b3、线性表的顺序存储结构是一种（）。
A.随机存取的存储结构B.顺序存取的存储结构C.索引存取的存储结构D.Hash存取的存储结构4、有六个元素6，5，4，3，2，1顺序入栈，下列不是合法的出栈序列的是（）。
A.543612B.453126C.346521D.2341565、已知有向图G=(V，E)，其中V={V1，V2，V3，V4，V5，V6，V7}， E=｛<V1，V2>，<V1，V3>，<V1，V4>，<V2，V5>，<V3，V5>， <V3，V6>，<V4，V6>，<V5，V7>，<V6，V7>｝，G的拓扑序列是（）。
A.V1，V3，V4，V6，V2，V5，V7B.V1，V3，V2，V6，V4，V5，V7C.V1，V3，V5，V2，V6，V7D.V1，V2，V5，V3，V4，V6，V76、若一棵二叉树的前序遍历序列为a，e，b，d，c，后序遍历序列为b， c，d，e，a，则根结点的孩子结点（）。
A．只有e B．有e、b C．有e、c D．无法确定7、已知关键字序列5，8，12，19，28，20，15，22是小根堆（最小堆），插入关键字3，调整后的小根堆是（）。
A．3，5，12，8，28，20，15，22，19B．3，5，12，19，20，15，22，8，28C．3，8，12，5，20，15，22，28，19D．3，12，5，8，28，20，15，22，198、有n（n>0）个分支结点的满二叉树的深度是（）。
2022年三峡大学计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、若需在O（nlog2n）的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（）。
A.快速排序B.堆排序C.归并排序D.直接插入排序2、n个结点的完全有向图含有边的数目（）。
A.n*nB.n(n+1)C.n/2D.n*(n-1)3、若线性表最常用的操作是存取第i个元素及其前驱和后继元素的值，为节省时间应采用的存储方式（）。
A.单链表B.双向链表C.单循环链表D.顺序表4、下面关于串的叙述中，不正确的是（）。
A.串是字符的有限序列B.空串是由空格构成的串C.模式匹配是串的一种重要运算D.串既可以采用顺序存储，也可以采用链式存储5、已知串S='aaab'，其next数组值为（）。
A.0123B.1123C.1231D.12116、已知字符串S为“abaabaabacacaabaabcc”，模式串t为“abaabc”，采用KMP算法进行匹配，第一次出现“失配”（s!＝t）时，i＝j＝5，则下次开始匹配时，i和j的值分别（）。
A．i＝1，j＝0 B．i＝5，j＝0 C．i＝5，j＝2 D．i＝6，j＝27、下列选项中，不能构成折半查找中关键字比较序列的是（）。
A．500，200，450，180 B．500，450，200，180C．180，500，200，450 D．180，200，500，4508、在下述结论中，正确的有（）。
①只有一个结点的二叉树的度为0。
②二叉树的度为2。
③二叉树的左右子树可任意交换。
④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。
A.①②③B.⑦③④C.②④D.①④9、一棵非空的二叉树的前序序列和后序序列正好相反，则该二叉树一定满足（）。
A.其中任意一个结点均无左孩子B.其中任意一个结点均无右孩子C.其中只有一个叶结点D.其中度为2的结点最多为一个10、分别以下列序列构造二叉排序树，与用其他三个序列所构造的结果不同的是（）。
窗体顶端1. 邻接表是图的一种____。
正确答案点评A 顺序存储结构B 链式存储结构C 索引存储结构D 散列存储结构正确答案：B答案讲解：无【试题出处】第6章第3节1窗体底端窗体顶端2. 一组记录的关键字为（46,79,56,38,40,84）,则利用快速排序的方法，以第一个记录为基准元素得到的一次划分结果为。
正确答案点评A 38,40,46,56,79,84B 40,38,46,79,56,84C 40,38,46,56,79,84D 40,38,46,84,56,79正确答案：C窗体底端窗体顶端3. 设深度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至多为_____(注意C和D中h是指数)。
正确答案点评A 2h-1B 2(h-1)C 2*h-1D 2*h正确答案：A窗体底端窗体顶端4. 一个栈的入栈序列是a,b,c,d, 则下列序列中不可能的输出序列是_______。
正确答案点评A acbdB dcbaC acdbD dbac正确答案：D窗体底端窗体顶端5. 计算机算法是指______。
正确答案点评A 计算方法B 排序方法C 调度方法D 解决问题的有限运算序列正确答案：D窗体底端窗体顶端6. 关于二叉树的三种遍历，下列说法正确的是____。
正确答案点评A 任意两种遍历序列都不可以唯一决定该二叉树B 任意两种遍历序列都可以唯一决定该二叉树C 先序遍历序列和后序遍历序列可以唯一决定该二叉树D 先序遍历序列和中序遍历序列可以唯一决定该二叉树正确答案：D窗体底端窗体顶端7. 顺序表的特点是______。
正确答案点评A 逻辑上相邻的结点其物理位置不相邻B 逻辑上相邻的结点其物理位置亦相邻C 顺序表不是随机存储结构D 在顺序表中插入和删除操作比在链表上方便正确答案：B窗体底端窗体顶端8. 设散列表长为14，散列函数是H(key)=key%11,表中已有数据的关键字为15，38，61，84共四个，现要将关键字为49的结点加到表中，用二次探测法解决冲突，则放入的位置是____________。
2022年吉首大学计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、下列说法不正确的是（）。
A.图的遍历是从给定的源点出发每个顶点仅被访问一次B.遍历的基本方法有两种：深度遍历和广度遍历C.图的深度遍历不适用于有向图D.图的深度遍历是一个递归过程2、用数组r存储静态链表，结点的next域指向后继，工作指针j指向链中结点，使j沿链移动的操作为（）。
A.j=r[j].nextB.j=j+lC.j=j->nextD.j=r[j]->next3、算法的计算量的大小称为计算的（）。
A.效率B.复杂性C.现实性D.难度4、有六个元素6，5，4，3，2，1顺序入栈，下列不是合法的出栈序列的是（）。
A.543612B.453126C.346521D.2341565、下面关于串的叙述中，不正确的是（）。
A.串是字符的有限序列B.空串是由空格构成的串C.模式匹配是串的一种重要运算D.串既可以采用顺序存储，也可以采用链式存储6、下列关于无向连通图特性的叙述中，正确的是（）。
Ⅰ．所有的顶点的度之和为偶数Ⅱ．边数大于顶点个数减1 Ⅲ．至少有一个顶点的度为1 A．只有Ⅰ B．只有Ⅱ C．Ⅰ和Ⅱ D．Ⅰ和Ⅲ7、下列选项中，不能构成折半查找中关键字比较序列的是（）。
A．500，200，450，180 B．500，450，200，180C．180，500，200，450 D．180，200，500，4508、一棵哈夫曼树共有215个结点，对其进行哈夫曼编码，共能得到（）个不同的码字。
A.107B.108C.214D.2159、在下述结论中，正确的有（）。
①只有一个结点的二叉树的度为0。
②二叉树的度为2。
③二叉树的左右子树可任意交换。
④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。
A.①②③B.⑦③④C.②④D.①④10、在文件“局部有序”或文件长度较小的情况下，最佳内部排序的方法是（）。
2022年浙江大学计算机科学与技术专业《计算机组成原理》科目期末试卷A（有答案）一、选择题1、局部性原理是一个持久的概念，对硬件和软件系统的设计和性能都有着极大的影响。
局部性通常有两种不同的形式：时间局部性和空间局部性。
程序员是否编写出高速缓存友好的代码，就取决于这两方面的问题。
对于下面这个函数，说法正确的是（）。
int sumvec(int v[N]){int i, sum=0;for(i=0;i<N;i++)sum+= v[i]eturn sum;}A.对于变量i和sum，循环体具有良好的空间局部性B.对于变量i、sum和v[N]，循环体具有良好的空间局部性C.对于变量i和sum，循环体具有良好的时间局部性D.对于变量i、sum和v[N]，循环体具有良好的时间局部性22、主存储器主要性能指标有（）。
1.存储周期Ⅱ.存储容量Ⅲ.存取时间Ⅳ.存储器带宽A.I、IⅡB.I、IⅡ、IVC. I、Ⅲ、lVD.全部都是3、由3个“1”和5个“0”组成的8位二进制补码，能表示的最小整数是（）。
A.-126B.-125C.-32D.-34、当定点运算发生溢出时，应（）。
A.向左规格化B.向右规格化C.舍入处理D.发出出错信息5、并行加法器中，每位全和的形成除与本位相加两数数值位有关外，还与（）有A.低位数值大小B.低位数的全和C.高位数值大小D.低位数送来的进位6、内部总线（又称片内总线）是指（）。
A.CPU内部连接各寄存器及运算部件之间的总线B.CPU和计算机系统的其他高速功能部件之间互相连接的总线C.多个计算机系统之间互相连接的总线D.计算机系统和其他系统之间互相连接的总线7、关于同步控制说法正确的是（）。
A.采用握手信号B.由统一时序电路控制的方式C.允许速度差别较大的设备一起接入工作D.B和C8、假定机器M的时钟频率为200MHz，程序P在机器M上的执行时间为12s。
对P优化时，将其所有乘4指令都换成了一条左移两位的指令，得到优化后的程序P。
2022年中国计量大学计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、下列排序算法中，占用辅助空间最多的是（）。
A.归并排序B.快速排序C.希尔排序D.堆排序2、设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储， a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（）。
A.13B.33C.18D.403、链表不具有的特点是（）。
A.插入、删除不需要移动元素B.可随机访问任一元素C.不必事先估计存储空间D.所需空间与线性长度成正比4、向一个栈顶指针为h的带头结点的链栈中插入指针s所指的结点时，应执行（）。
A.h->next=sB.s->next=hC.s->next=h;h->next=sD.s->next=h-next;h->next=s5、有六个元素6，5，4，3，2，1顺序入栈，下列不是合法的出栈序列的是（）。
A.543612B.453126C.346521D.2341566、若一棵二叉树的前序遍历序列为a，e，b，d，c，后序遍历序列为b， c，d，e，a，则根结点的孩子结点（）。
A．只有e B．有e、b C．有e、c D．无法确定7、循环队列放在一维数组A中，end1指向队头元素，end2指向队尾元素的后一个位置。
假设队列两端均可进行入队和出队操作，队列中最多能容纳M－1个元素。
初始时为空，下列判断队空和队满的条件中，正确的是（）。
A．队空：end1＝＝end2；队满：end1＝＝（end2＋1）mod MB．队空：end1＝＝end2；队满：end2＝＝（end1＋1）mod （M－1）C．队空：end2＝＝（end1＋1）mod M；队满：end1＝＝（end2＋1） mod MD．队空：end1＝＝（end2＋1）mod M；队满：end2＝＝（end1＋1） mod （M－1）8、有n（n>0）个分支结点的满二叉树的深度是（）。
2022年浙江工业大学计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、有一个100*90的稀疏矩阵，非0元素有10个，设每个整型数占2字节，则用三元组表示该矩阵时，所需的字节数是（）。
A.60B.66C.18000D.332、下列排序算法中，占用辅助空间最多的是（）。
A.归并排序B.快速排序C.希尔排序D.堆排序3、以下数据结构中，（）是非线性数据结构。
A.树B.字符串C.队D.栈4、在下列表述中，正确的是（）A.含有一个或多个空格字符的串称为空格串B.对n（n>0）个顶点的网，求出权最小的n-1条边便可构成其最小生成树C.选择排序算法是不稳定的D.平衡二叉树的左右子树的结点数之差的绝对值不超过l5、有六个元素6，5，4，3，2，1顺序入栈，下列不是合法的出栈序列的是（）。
A.543612B.453126C.346521D.2341566、排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一趟排序。
下列排序方法中，每一趟排序结束时都至少能够确定一个元素最终位置的方法是（）。
Ⅰ．简单选择排序Ⅱ．希尔排序Ⅲ．快速排序Ⅳ．堆排Ⅴ．二路归并排序A．仅Ⅰ、Ⅲ、Ⅳ B．仅Ⅰ、Ⅱ、Ⅲ C．仅Ⅱ、Ⅲ、Ⅳ D．仅Ⅲ、Ⅳ、Ⅴ7、若元素a，b，c，d，e，f依次进栈，允许进栈、退栈操作交替进行，但不允许连续三次进行退栈操作，则不可能得到的出栈序列是（）。
8、一棵非空的二叉树的前序序列和后序序列正好相反，则该二叉树一定满足（）。
A.其中任意一个结点均无左孩子B.其中任意一个结点均无右孩子C.其中只有一个叶结点D.其中度为2的结点最多为一个9、有关二叉树下列说法正确的是（）。
A.二叉树的度为2B.一棵二叉树的度可以小于2C.二叉树中至少有一个结点的度为2D.二叉树中任何一个结点的度都为210、对{05，46，13，55，94，17，42}进行基数排序，一趟排序的结果是：A.05，46，13，55，94，17，42B.05，13，17，42，46，55.94C.42，13，94，05，55，46，17D.05，13，46，55，17，42，94二、填空题11、顺序查找n个元素的顺序表，若查找成功，则比较关键字的次数最多为______次；当使用监视哨时，若查找失败，则比较关键字的次数为______。
2022年兰州大学计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、哈希文件使用哈希函数将记录的关键字值计算转化为记录的存放地址，因为哈希函数是一对一的关系，则选择好的（）方法是哈希文件的关键。
A.哈希函数B.除余法中的质数C.冲突处理D.哈希函数和冲突处理2、下列排序算法中，占用辅助空间最多的是（）。
A.归并排序B.快速排序C.希尔排序D.堆排序3、若线性表最常用的操作是存取第i个元素及其前驱和后继元素的值，为节省时间应采用的存储方式（）。
A.单链表B.双向链表C.单循环链表D.顺序表4、用不带头结点的单链表存储队列，其队头指针指向队头结点，队尾指针指向队尾结点，则在进行出队操作时（）。
A.仅修改队头指针B.仅修改队尾指针C.队头、队尾指针都可能要修改D.队头、队尾指针都要修改5、动态存储管理系统中，通常可有（）种不同的分配策略。
A.1B.2C.3D.46、下列选项中，不能构成折半查找中关键字比较序列的是（）。
A．500，200，450，180 B．500，450，200，180C．180，500，200，450 D．180，200，500，4507、排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一趟排序。
下列排序方法中，每一趟排序结束时都至少能够确定一个元素最终位置的方法是（）。
Ⅰ．简单选择排序Ⅱ．希尔排序Ⅲ．快速排序Ⅳ．堆排Ⅴ．二路归并排序A．仅Ⅰ、Ⅲ、Ⅳ B．仅Ⅰ、Ⅱ、Ⅲ C．仅Ⅱ、Ⅲ、Ⅳ D．仅Ⅲ、Ⅳ、Ⅴ8、已知一棵二叉树的前序遍历结果为ABCDEF，中序遍历结果为CBAEDF，则后序遍历结果为（）。
A.CBEFDAB.FEDCBAC.CBEDFAD.不定9、一棵非空的二叉树的前序序列和后序序列正好相反，则该二叉树一定满足（）。
A.其中任意一个结点均无左孩子B.其中任意一个结点均无右孩子C.其中只有一个叶结点D.其中度为2的结点最多为一个10、对序列{15，9，7，8，20，-1，4}用希尔排序方法排序，经一趟后序列变为{15，-1，4，8，20，9，7}则该次采用的增量是（）。
2022年浙江大学计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、将线性表的数据元素进行扩充，允许带结构的线性表是（）。
A.串B.树C.广义表D.栈2、哈希文件使用哈希函数将记录的关键字值计算转化为记录的存放地址，因为哈希函数是一对一的关系，则选择好的（）方法是哈希文件的关键。
A.哈希函数B.除余法中的质数C.冲突处理D.哈希函数和冲突处理3、静态链表中指针表示的是（）。
A.下一元素的地址B.内存储器的地址C.下一元素在数组中的位置D.左链或右链指向的元素的地址4、循环队列A[0..m-1]存放其元素值，用front和rear分别表示队头和队尾，则当前队列中的元素数是（）。
A.（rear-front+m）%mB.rear-front+1C.rear-front-1D.rear-front5、在下列表述中，正确的是（）A.含有一个或多个空格字符的串称为空格串B.对n（n>0）个顶点的网，求出权最小的n-1条边便可构成其最小生成树C.选择排序算法是不稳定的D.平衡二叉树的左右子树的结点数之差的绝对值不超过l6、下列选项中，不能构成折半查找中关键字比较序列的是（）。
A．500，200，450，180 B．500，450，200，180C．180，500，200，450 D．180，200，500，4507、已知关键字序列5，8，12，19，28，20，15，22是小根堆（最小堆），插入关键字3，调整后的小根堆是（）。
A．3，5，12，8，28，20，15，22，19B．3，5，12，19，20，15，22，8，28C．3，8，12，5，20，15，22，28，19D．3，12，5，8，28，20，15，22，198、下述二叉树中，哪一种满足性质：从任一结点出发到根的路径上所经过的结点序列按其关键字有序（）。
A.二叉排序树B.哈夫曼树C.AVL树D.堆9、一棵哈夫曼树共有215个结点，对其进行哈夫曼编码，共能得到（）个不同的码字。
A.107B.108C.214D.21510、在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A，并已知A 的左孩子的平衡因子为0，右孩子的平衡因子为l，则应作（）型调整以使其平衡A.LLB.LRC.RLD.RR二、填空题11、如果按关键码值递增的顺序依次将关键码值插入到二叉排序树中，则对这样的二叉排序树检索时，平均比较次数为______。
12、在哈希函数H（key）=key%p中，p值最好取______。
13、如下的算法分别是后序线索二叉树求给定结点node的前驱结点与后继结点的算法，请在算法空格处填上正确的语句。
设线索二叉树的结点数据结构为（lflag，left，data，right，rflag），其中：lflag=0，left指向其左孩子，lflag=1，left指向其前驱；rflag=0，right指向其右孩子，rflag=1，right指向其后继。
14、设T是一棵结点值为整数的二叉排序树，A是一个任意给定的整数。
在下面的算法中，free_tree（T）在对二叉排序树丁进行后序遍历时释放二又排序树T的所有结点；delete_subtree（T，A），首先在二叉排序树T中查找值为A的结点，根据查找情况分别进行如下处理：（1）若找不到值为A的结点，则返回根结点的地址（2）若找到值为A的结点，则删除以此结点为根的子树，并释放此子树中的所有结点，若值为A的结点是查找树的根结点，删除后变成空的二叉树，则返null；否则返回根结点的地址。
15、数据结构中评价算法的两个重要指标是______。
16、设T和P是两个给定的串，在T中寻找等于P的子串的过程称为______，又称P为______。
17、下列程序是快速排序的非递归算法，请填写适当的语句，完成该功能。
18、在顺序存储的二叉树中，编号为i和j的两个结点处在同一层的条件是______。
三、判断题19、文件系统采用索引结构是为了节省存储空间。
（）20、直接访问文件也能顺序访问，只是一般效率不高。
（）21、队列和栈都是运算受限的线性表，只允许在表的两端进行运算。
（）22、稀疏矩阵压缩存储后，必会失去随机存取功能。
（）23、中序遍历一棵二叉排序树的结点就可得到排好序的结点序列。
（）24、深度为k的二叉树中结点总数小于等于2k-1。
（）25、为提高排序速度，进行外排序时，必须选用最快的内排序算法。
（）26、在用堆排序算法排序时，如果要进行增序排序，则需要采用“大根堆”。
（）27、连通图上各边权值均不相同，则该图的最小生成树是唯一的。
（）28、若一个有向图的邻接矩阵对角线以下元素均为零，则该图的拓扑有序序列必定存在。
（）四、简答题29、已知n阶下三角矩阵A（即当i＜j时，有a ij=0），按照压缩存储的思想，可以将其主对角线以下所有元素（包括主对角线上元素）依次存放于一维数组B中，请写出从第一列开始采用列序为主序分配方式时在B 中确定元素a ij的存放位置的公式。
30、将下列由三棵树组成的森林转换为二叉树（只要求给出转换结果）。
31、已知图的邻接矩阵为：当用邻接表作为图的存储结构，且邻接点都按序号从大到小排列时，试写出：(1)以顶点V1为出发点的唯一的深度优先遍历序列。
当用邻接表作为图的存储结构，且邻接点都按序号从大到小排列时，试写出：(1)以顶点V1为出发点的唯一的深度优先遍历序列。
(2)以顶点V1为出发点的唯一的广度优先遍历序列。
(3)该图唯一的拓扑有序序列。
五、算法设计题32、已知深度为h的二叉树，以一维数组BT[0..2h-2]作为其存储结构，试编写一算法，求该二叉树中叶结点的个数，为简单起见，设二叉树中元素结点为非负整数，要求写出算法基本思想及相应的算法。
33、写一算法找出n个数的最大值和最小值，要求最坏条件下的元素比较次数为34、元素集合已存入整型数组A[1..n]中，试写出依次取A中各值A[i]（1≤i≤n）构造一棵二叉排序树T的非递归算法：CSBT（r，A）35、已知一棵高度为K具有n个结点的二叉树，按顺序方式存储。
（1）编写用前序遍历树中每个结点的非递归算法。
（2）编写将树中最大序号叶结点的祖先结点全部打印输出的算法。
参考答案一、选择题1、【答案】C2、【答案】D3、【答案】C4、【答案】A5、【答案】C6、【答案】A7、【答案】A8、【答案】D9、【答案】B10、【答案】C二、填空题11、【答案】（n+1）/212、【答案】小于等于表长的最大素数或不包含小于20的质因子的合数13、【答案】node->rflag==0；*x=bt；*x=node->right；prior（t，x）14、【答案】free（T）；q&&q->data!=A；q=q->rchild；p->lchild=null；p->rchild=null15、【答案】算法的时间复杂度和空间复杂度16、【答案】模式匹配；模式串17、【答案】a[j]=a[k]；low=stack[top][0]；stack[top][0]=k+1【解析】快速排序(quick sort)的基本思想是，通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
18、【答案】【解析】用顺序存储结构存储二叉树时，要按完全二叉树的形式存储，非完全二叉树存储时，要加“虚结点”。
设编号为i和j的结点在顺序存储中的下标为s和t，则结点i和j在同一层上的条件是三、判断题19、【答案】×20、【答案】×21、【答案】×22、【答案】√23、【答案】√24、【答案】√25、【答案】×26、【答案】√27、【答案】√28、【答案】√四、简答题29、答：2阶下三角矩阵元素A[i][j]（1≤i，j≤n，i≥j）。
第1列有n个元素，第j 列有n-j+1个元素，第1列到第j-1列是梯形，元素数为（n+（n-j+2）（j-1）/2，而a ij在第j列上的位置是为i-j+1。
所以n阶下三角矩阵A按列存储，其元素a ij在一维数组B中的存储位置k与i和j的关系为：30、答：森林转换为二叉树分以下三步：（1）连线（将兄弟结点相连，各树的根看作兄弟）。
（2）切线（保留最左边子女为独生子女，将其他子女分支切掉）。
（3）旋转（以最左边树的根为轴，顺时针向下旋转45度）。
所以由上面三棵树转换得到的二叉树如图所示：31、答：(1)V1，V4，V9，V10，V7，V6，V8，V3，V2，V5(2)V1，V4，V3，V2，V9，V7，V6，V5，V10，V8(3)V1，V2，V5，V3，V4，V6，V8，V7，V9，V10五、算法设计题32、答：算法如下：33、答：算法如下：34、答：算法如下：35、答：（1）算法如下：（2）算法如下：。
