2024年大学试题(计算机科学)-数据结构笔试参考题库含答案

“人人文库”水印下载源文件后可一键去除，请放心下载！（图片大小可任意调节）2024年大学试题(计算机科学)-数据结构笔试参考题库含答案“人人文库”水印下载源文件后可一键去除，请放心下载！第1卷一.参考题库(共75题)1.已知一个无向图顶点有5个，则边可能有（）个。A、10B、11C、8D、92.删除一单向链表中P指针所指向结点的后继结点，正确的操作是（）。A、p->next=p->next->nextB、p=p->nextC、p->next=pD、p->next->next=p->next3.对一个算法的评价，不包括如下（）方面的内容。A、健壮性和可读性B、并行性C、正确性D、时空复杂度4.为整数定义一个抽象数据类型，包含整数的常见运算，每个运算对应一个基本操作，每个基本操作的接口需定义前置条件、输入、功能、输出和后置条件。5.用邻接表表示图进行深度优先遍历时，通常是采用（）来实现算法的。A、栈B、队列C、树D、图6.在含有n个关键字的小根堆（堆顶元素最小）中，关键字最大的记录有可能存储在（）位置上。A、n/2B、n/2-1C、1D、n/2+27.稳定的排序方法是（）A、直接插入排序和快速排序B、折半插入排序和起泡排序C、简单选择排序和四路归并排序D、树形选择排序和shell排序8.下列序列中，（）是执行第一趟快速排序的结果。A、da，ax，eb，de，bb]ff[ha，gc]B、cd，eb，ax，da]ff[ha，gc，bb]C、gc，ax，eb，cd，bb]ff[da，ha]D、ax，bb，cd，da]ff[eb，gc，ha]9.结构体是基本类型的。10.假定一棵三叉树的结点数为50，则它的最小高度为（）。A、3B、4C、5D、611.假定对有序表：（3，4，5，7，24，30，42，54，63，72，87，95）进行折半查找。若查找元素90，需依次与哪些元素比较？12.已知单链表中各结点的元素值为整型且递增有序，设计算法删除链表中所有大于mink且小于maxk的所有元素，并释放被删结点的存储空间。13.对于线性表的两种存储结构，如果有n个线性表同时并存，而且在处理过程中各表的长度会动态发生变化，线性表的总数也会自动改变，在此情况下，应选用哪一种存储结构？为什么？14.某完全有向图G含有n个结点，则它含有边的数目（）。A、（n-1）n/2B、n（n+1）C、n/2D、n（n－l）15.若要对某二叉排序树进行遍历，保证输出所有结点的值序列按增序排列，应对该二叉排序树采用（）遍历法。16.顺序表的特点是（）。A、表中元素的个数为表长B、按顺序方式存储数据元素C、逻辑结构中相邻的结点在存储结构中仍相邻D、按表中元素的次序存储17.根据n个元素建立一棵二叉搜索树时，其时间复杂度大致为（）。A、O（n）B、O（log2n）C、O（n2）D、O（nlog2n）18.一棵二叉树的中序、后序遍历序列分别为： G L D H B E I A C J F K和L G H D I E B J K F C A，请回答：画出二叉树逻辑结构的图示。19.数据结构里，汉诺塔问题，是递归解决的问题，需要（）来帮助算法实现。A、栈B、图C、二叉树D、队列20.简述线性结构与非线性结构的不同点。21.设有两个串p和q，求q在p中首次出现的位置的运算称作（）A、连接B、模式匹配C、求子串D、求串长22.二叉树的第5层最多有（）个结点。A、17B、16C、15D、1423.简述字符串与一维字符型数组的区别与联系。24.向一个栈顶指针为HS的链中插入一个S所指结点时，则执行（）。25.在一棵树中，（）没有前趋结点。A、叶子结点B、树根结点C、空结点D、树枝结点26.算法的计算量的大小称为计算的（）。A、效率B、复杂性C、现实性D、难度27.设有一个双向循环链表，每个结点中除有pre，data和next三个域外，还增设了一个访问频度域freq。在链表被起用之前，频度域freq的值均初始化为零，而每当对链表进行一次Locate（L，x）的操作后，被访问的结点（即元素值等于x的结点）中的频度域freq的值便增1，同时调整链表中结点之间的次序，使其按访问频度非递增的次序顺序排列，以便始终保持被频繁访问的结点总是靠近表头结点。试编写符合上述要求的Locate操作的算法。28.二叉树如果有根结点，只能有（）个。A、一B、两C、三D、四29.链表每个结点包含数据域和指针域，其指针域可以有（）个。A、0个B、1个C、2个D、多个30.在单链表中，头指针的作用是（）A、方便运算的实现B、用于标识单链表C、使单链表中至少有一个结点D、用于标识首结点位置31.栈和队列的共同点是（）。A、都是树形结构B、都是限制存取点的线性结构C、都是线性结构D、都不对32.链式存储的线性表可以随机存取33.设哈希函数H（key）=keyMOD13，用线性探测再散列法解决冲突.对关键字序列{55，19，01，68，23，27，20，84}在地址空间为0-10的散列区中建哈希表，画出此表，并求等概率情况下查找成功时的平均查找长度.34.哈夫曼树的总结点个数（多于1时）不能为偶数。35.在顺序存储的二叉树中，编号为i和j的两个结点处在同一层的条件是（）。36.单循环链表的主要优点是（）。A、不再需要头指针了B、从表中任一结点出发都能扫描到整个链表；C、已知某个结点的位置后，能够容易找到它的直接前趋；D、在进行插入、删除操作时，能更好地保证链表不断开。37.设二叉排序树中有n个结点，则在二叉排序树的平均查找长度为（） A、AB、BC、CD、D38.单链表中在p指针后插入元素的时间复杂度是（）。A、O（1）B、O（n）C、O（nn）D、都不对39.队列的特点是（）。A、先进先出B、后进先出C、先进后出D、不进不出40.设串长为n，模式串长为m，则KMP算法所需的附加空间为（）。A、O（m）B、O（n）C、O（m*n）D、O（nlog2m）41.试编写算法求单循环链表的表长。42.在顺序表中插入或删除一个元素，需要平均移动（）元素，具体移动的元素个数与（）有关。43.栈的运算规则为（），队列的运算规则为（）。44.设s=’I︺AM︺A︺TEACHER’，其长度是（）45.裴波那契（Fibonacci）数列的定义为：它的第1项和第2项均为1，以后各项为其前两项之和。若裴波那契数列中的第n项用Fib（n）表示，则计算公式为： 试编写出计算Fib（n）的递归算法和非递归算法，并分析它们的时间复杂度和空间复杂度。46.在初始序列已基本有序（除去n个元素中的某k个元素后即呈有序，kA、快速排序B、直接插入排序C、二路归并排序D、简单选择排序E、起泡排序F、堆排序47.一个数据结构是由一个逻辑结构和这个逻辑结构上的一个基本运算集构成的整体。48.假设在有序线性表A[1..20]上进行折半查找，则比较一次查找成功的结点数为（），则比较二次查找成功的结点数为（），则比较三次查找成功的结点数为（），则比较四次查找成功的结点数为（），则比较五次查找成功的结点数为（）49.对下列四个序列进行快速排序，各以第一个元素为基准进行第一次划分，则在该次划分过程中需要移动元素次数最多的序列为（）A、  1， 3， 5， 7， 9B、  9， 7， 5， 3， 1C、  5， 3， 1， 7， 9D、  5， 7， 9， 1， 350.某完全二叉树按层次编号后，某结点是i，若有左孩子，则左孩子的编号不可能是（）。A、2iB、2i+1C、2i-1D、i/251.满二叉树也是完全二叉树。52.栈和队列都是操作受限的线性表，栈的运算特点是（），队列的运算特点是（）53.一颗二叉树度为2的结点的个数是6，则问度为0的结点的个数是（）。A、6B、7C、8D、554.采用环形队列可以解决队列中假溢出的现象。55.设主串为“FABcCDABcdEFaBc”，以下模式串能与主串成功匹配的是（）。A、EFaBcB、ABCdEC、DABCCD、.FAbcC56.设A=（a1，…，am和B=（b1，…，bn）均为顺序表，Aˊ和Bˊ分别为A和B中除去最大共同前缀后的子表。若Aˊ=Bˊ空表，则A=B；若Aˊ=空表，而Bˊ≠空表，或者两者均不为空表，且Aˊ的首元小于Bˊ的首元，则A＜B；否则A＞B。试写一个比较A，B大小的算法。57.设计一个算法，其功能为：利用中序线索求结点的中序后继。请将代码补充完整。 58.设散列地址空间为0~m-1，k为关键字，用P去除k，将余数作为k的散列地址，即：h（k）=k%P，为了减少发生冲突的可能性，一般取P为（）。A、小于m的最大奇数B、小于m的最大素数C、小于m的最大偶数D、小于m的最大合数59.以下（）不是队列的基本运算A、从队尾插入一个新元素B、从队列中删除第i个元素C、判断一个队列是否为空D、读取队头元素的值60.若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点，则采用（）存储方式最节省运算时间。A、单链表B、给出表头指针的单循环链表C、双链表D、带头结点的双循环链表61.数据结构里，6个顶点的有向图，最多有（）条边。A、30B、15C、14D、3162.假定对线性表(38,25,74,52,48)进行哈希存储，采用H(K)=K%7作为哈希函数，采用线性探测法处理冲突，则在建立哈希表的过程中，将会碰到（）次存储冲突。63.对于一个无向图，下面（）种说法是正确的。A、 每个顶点的入度等于出度B、 每个顶点的度等于其入度与出度之和C、 每个顶点的入度为0D、 每个顶点的出度为064.待排序的序列为8，3，4，1，2，5，9， 采用直接选择排序算法，当进行了两趟选择后，结果序列为（）。65.结构体指针的定义方式正确的是（）A、struct结构体名指针变量名；B、struct结构体名；C、struct指针变量名；D、struct指针变量名结构体名；66.在线性表的哈希存储中，装填因子又称为装填系数，若用m表示哈希表的长度，n表示线性表中的元素的个数，则α等于（）67.空串与空格串是相同的。68.设指针变量top指向当前链式栈的栈顶，则删除栈顶元素的操作序列为（） A、AB、BC、CD、D69.深度为K的完全二叉树至少有（）个结点，至多有（）个结点70.阅读下列算法，并回答下列问题： 该算法采用何种策略进行排序？ 71.非空左斜树的先序遍历序列和后序遍历序列正好相反。72.在9阶B-树中，除叶子以外的任意结点的分支数介于5和9之间。73.一棵有n个叶结点的哈夫曼树，则该树共有（）个结点。74.在对n个元素进行直接插入排序的过程中，算法的空间复杂度为（）A、O（1）B、O（log2n）C、O（n2）D、O（nlog2n）75.数据结构里，下列选项中是定义结构体类型的指针变量的格式的是（）。A、struct结构名指针变量名B、struct结构名变量名C、static结构名指针变量名D、struct指针变量名结构名第2卷一.参考题库(共75题)1.在索引表中，每个索引项至少包含有（）域和（）域这两项。2.试推导含有12个结点的平衡二叉树的最大深度，并画出以棵这样的树。3.在进行直接插入排序时，其数据比较次数与数据的初始排列（）关；而在进行直接选择排序时，其数据比较次数与数据的初始排列（）关。4.当向一个大根堆插入一个具有最大值的元素时，需要逐层（）调整，直到被调整到（）位置为止。5.如果希望循环队列中的元素都能得到利用，则需设置一个标志域tag，并以tag的值为0和1来区分，尾指针和头指针值相同时的队列状态是“空”还是“满”。试编写与此结构相应的入队列和出队列的算法，并从时间和空间角度讨论设标志和不设标志这两种方法的使用范围（如当循环队列容量较小而队列中每个元素占的空间较多时，哪一种方法较好）。6.数据元素是数据最小的单位。7.数据的逻辑结构和数据的存储结构是相同的。8.数据结构里，线性表的链式存储结构优于顺序存储结构。9.设要将序列（Q，H，C，Y，P，A，M，S，R，D，F，X）中的关键码按升序排列，则（）是起泡排序一趟扫描的结果，（）是增量为4的希尔排序一趟扫描的结果，（）二路归并排序一趟扫描的结果，（）是以第一个元素为轴值的快速排序一趟扫描的结果，（）是堆排序初始建堆的结果。10.在n个结点的线性表的数组实现中，算法的时间复杂度是O（1）的操作是（）。A、访问第i（1＜＝i＜＝n）个结点和求第i个结点的直接前驱（1＜i＜＝n）B、在第i（1＜＝i＜＝n）个结点后插入一个新结点C、删除第i（1＜＝i＜＝n）个结点D、以上都不对11.对字符串s=’data-structure’ 执行操作replace（s，substring（s，6，8），’bas’）的结果是（）。A、‘database’B、‘data-base’C、‘bas’D、‘data-basucture’12.单链表形式的队列，头指针F指向队列的第一个结点，尾指针R指向队列的最后一个节点。13.设一个有向图为G=（V，E），其中V={v1，v2，v3，v4}，E={，，，，}，请回答下列各问：画出该有向图，求出每个顶点的入度和出度。14.什么是队列的上溢现象？一般有几种解决方法，试简述之。15.数据结构里，strcpy和strcat的返回值类型一样。16.对包含n个元素的哈希表进行查找，平均查找长度为（）A、O（log2n）B、O（n）C、O（nlog2n）D、不直接依赖于n17.采用顺序搜索方法查找长度为n的顺序表示，搜索成功的平均搜索长度为（）。A、nB、n/2C、（n-1）/2D、（n+1）/218.若根据查找表建立长度为m的哈希表，采用线性探测法处理冲突，假定对一个元素第一次计算的哈希地址为d，则下一次的哈希地址为（）。A、 dB、 d+1C、 （d+1）/mD、 （d+1）%m19.为解决计算机主机与打印机间速度不匹配问题，通常设一个打印数据缓冲区。主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是（）。A、队列B、栈C、 线性表D、有序表20.设语句x++的时间是单位时间，则以下语句的时间复杂度为（） A、O（1）B、O（n2）C、O（n）D、O（n3）21.简述在顺序栈的栈顶插入一个元素的操作过程。22.在所有排序方法中，（）方法使数据的组织采用的是完全二叉树的结构。23.抽象数据类型与计算机内部表示和实现无关24.字符串的处理函数strcpy是系统定义的，作用是进行字符串拷贝，两个参数，返回值为char*。25.假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点（注意不设头指针），试编写相应的队列初始化、入队列何处队列的算法。26.设关键字序列为（71，12，88，53，11，25，65，27，16），散列函数为H（key）=key%7，采用链地址法解决冲突。请回答：请求等概率下查找成功的平均查找长度ASL27.对于长度为8的顺序存储结构的有序表，若采用二分查找法查找，在等概率的情况下的平均查找长度为（）的值除以8。A、17B、19C、21D、2028.磁盘上的顺序文件中插入新的记录时，必须复制整个文件。29.下面（）不是算法所必须具备的特性。A、有穷性B、确切性C、高效性D、可行性30.从栈顶指针为top的链栈中删除一个结点，用x保存被删除结点的值，则执行（）。A、x=top；top=top->next；B、x=top->data；C、top=top->next；x=top->data；D、x=top->data；top=top->next；31.在一棵二叉树中，若编号为15的结点是其双亲结点的右孩子，则双亲结点的顺序编号为（）A、30B、8C、31D、732.一棵深度为h的B-树，任一个叶子结点所处的层数为（），当向B-树中插入一个新关键字时，为检索插入位置需读取（）个结点。33.证明：一棵满k叉树上的叶子结点数和非叶子结点数之间满足关系：n0=（k-1）n0+134.任何一棵二叉树的叶子结点在前序、中序和后序遍历序列中的相对次序（）。A、不发生改变B、发生改变C、不能确定D、以上都不对35.数据结构中，数据元素之间的抽象关系称为（）结构。36.在散列技术中，处理冲突的两种主要方法是（）和（）。37.在待排序的元素序列基本有序的前提下，效率最高的排序方法是（）A、插入排序B、选择排序C、快速排序D、希尔排序38.经过下列栈的运算后EmptyStack（s）[判断是否为空栈，是返回1，否返回0]的值是（）。 A、aB、bC、1D、039.简述以下算法的功能（栈的元素类型SElemType为int）。 40.对于一个长度为n的单链存储的线性表，在表头插入元素的时间复杂度为（），在表尾插入元素的时间复杂度为（）。41.在n个结点的元向图中，若边数在于n-1，则该图必是连通图。42.算法的时间复杂度数量级包括（）。A、线性阶O（n）B、平方阶O（nn）C、立方阶O（nnn）D、对数阶O（log2n）43.在一个单向链表中，在p所指结点之后插入一个s所指的结点时，可执行（）；和p->next=s；。A、p=s；B、p->next=s->next；C、p=s->next；D、s->next=p->next；44.如图所示为一个有向网图及其带权邻接矩阵，要求对有向图采用Dijkstra算法，求从V0到其余各顶点的最短路径。 45.将二叉排序树T按前序遍历序列依次插入初始为空的二叉排序树T’中，则T与T’是相同的，这种说法是否正确？46.判定一个栈ST（最多元素为m0）为空的条件是（）A、ST->top0B、ST->top=0C、ST->topm0D、ST->top=m047.给定权值2，10，12，4，8，5，构造相应的哈夫曼树并求出带权路径长度WPL。48.设在一棵度数为3的树中，度数为3的结点数有2个，度数为2的结点数有1个，度数为1的结点数有2个，那么度数为0的结点数有（）个。A、4B、5C、6D、749.度数为0的结点，即没有子树的结点叫作（）结点或（）结点。同一个结点的儿子结点之间互称为（）结点。50.设将整数1，2，3，4依次进栈，但只要出栈时栈非空，则可将出栈操作按任何次序夹入其中，请回答下述问题： （1）若入、出栈次序为Push（1），Pop（），Push（2），Push（3），Pop（），Pop（），Push（4），Pop（），则出栈的数字序列为何？（这里Push（i）表示i进栈，Pop（）表示出栈） （2）能否得到出栈序列1423和1432？并说明为什么不能得到或者如何得到。 （3）请分析1，2，3，4的24种排列中，哪些序列是可以通过相应的入出栈操作得到的。51.实现任意二叉树的后序遍历的非递归算法而不适用栈结构，最佳的二叉树方法是采用（）。52.给定权值{8，12，4，5，26，16，9}，构造一棵带权路径长度最短的二叉树，并计算其带权路径长度。53.数据结构里，函数参数为哪项时，参数传递属于地址传递。（）A、数组B、float型C、char型D、int型54.线性表可以看成是广义表的特例，如果广义表中的每个元素都是原子，则广义表便成为线性表。55.对于键值序列（12，13，11，18，60，15，7，18，25，100），用筛选法建堆，必须从键值为（）的结点开始。56.堆排序是一种（）排序。A、插入B、选择C、交换D、归并57.数据结构是指（）。A、数据元素的组织形式B、数据类型C、数据存储结构D、数据定义58.常用的图的遍历方法有深度优先遍历和广度优先遍历。59.栈的存储结构有（）和（）。60.对图所示的无向图，依次输入各边：（v1，v2）、（v1，v4）、（v2，v3）、（v3，v4）、（v3，v5），请回答下列各问： 对（2）中的邻接表，给出从顶点v1出发的DFS序列和DFS生成树。61.队列的特点之一是：元素进、出队的次序是：先进（）。62.对具有n个结点的堆进行插入一个元素运算的时间复杂度为O（n）。63.假定一个顺序表的长度为50，并假定查找每个元素的概率都相同，则在查找成功情况下的平均查找长度（），在查找不成功情况下的平均查找长度（）64.一个广义表中的元素分为（）元素和（）元素两类。65.设待排序的记录序列用单链表作存储结构，试写出直接插入排序算法。66.线索链表中的rtag域值为（）时，表示该结点无右孩子，此时（）域为指向该结点后继线索的指针。67.设有一棵深度为6的完全二叉树，第6层上有3个结点，该树共有（）个结点。68.要求在n个数据元素中找值最大的元素，其基本操作为元素间的比较。算法的时间复杂度为（）69.一棵一般树的结点的前序遍历和后序遍历分别与它相应二叉树的结点前序遍历和后序遍历是一致的。70.数据结构里，算法是对（）求解步骤的描述。A、特定问题B、特定时间C、特定公式D、以上都不对71.对输入文件（101，51，19，61，3，71，31，17，19，100，55，20，9，30，50，6，90）；当k=6时，使用置换-选择算法，写出建立的初始败者树及生成的初始归并段。72.设计算法，判断一棵二叉树是否为完全二叉树。73.在单链表上实现线性表的求表长ListLength（L）运算。74.下面算法的时间复杂度为（） A、O（1）B、O（n）C、O（n2）D、O（n!）75.设有一组初始记录关键字序列（K1，K2，…，Kn），要求设计一个算法能够在O（n）的时间复杂度内将线性表划分成两部分，其中左半部分的每个关键字均小于Ki，右半部分的每个关键字均大于等于Ki。第1卷参考答案一.参考题库1.参考答案：A,C,D2.参考答案：A3.参考答案：B4.参考答案：整数的抽象数据类型定义如下： A.DTinteger D.ata 整数a：可以是正整数（1，2，3，…）、负整数（-1，-2，-3，…）和零 O.peration C.onstructor前置条件：整数a不存在输入：一个整数b功能：构造一个与输入值相同的整数 输出：无 后置条件：整数a具有输入的值 S.et前置条件：存在一个整数a输入：一个整数b 功能：修改整数a的值，使之与输入的整数值相同输出：无 后置条件：整数a的值发生改变 A.dd前置条件：存在一个整数a输入：一个整数b 功能：将整数a与输入的整数b相加输出：相加后的结果 后置条件：整数a的值发生改变 S.ub前置条件：存在一个整数a输入：一个整数b 功能：将整数a与输入的整数b相减输出：相减的结果 后置条件：整数a的值发生改变 M.ulti前置条件：存在一个整数a输入：一个整数b 功能：将整数a与输入的整数b相乘输出：相乘的结果 后置条件：整数a的值发生改变 D.iv前置条件：存在一个整数a输入：一个整数b 功能：将整数a与输入的整数b相除 输出：若整数b为零，则抛出除零异常，否则输出相除的结果后置条件：整数a的值发生改变 M.od前置条件：存在一个整数a输入：一个整数b 功能：求当前整数与输入整数的模，即正的余数 输出：若整数b为零，则抛出除零异常，否则输出取模的结果后置条件：整数a的值发生改变 E.qual前置条件：存在一个整数a输入：一个整数b 功能：判断整数a与输入的整数b是否相等输出：若相等返回1，否则返回0 后置条件：整数a的值不发生改变 E.ndADT5.参考答案：A6.参考答案：D7.参考答案：B8.参考答案：A9.参考答案：错误10.参考答案：C11.参考答案：查找元素90，需依次与30，63，87，95，72等元素比较。12.参考答案：因为是在有序单链表上的操作，所以，要充分利用其有序性。在单链表中查找第一个大于mink的结点和第一个小于maxk的结点，再将二者间的所有结点删除。 13.参考答案：应选用链接存储结构，因为链式存储结构是用一组任意的存储单元依次存储线性表中的各元素，这里存储单元可以是连续的，也可以是不连续的：这种存储结构对于元素的删除或插入运算是不需要移动元素的，只需修改指针即可，所以很容易实现表的容量的扩充。14.参考答案：D15.参考答案：中序16.参考答案：B17.参考答案：D18.参考答案： 19.参考答案：A20.参考答案： 线性结构反映结点间的逻辑关系是一对一的，非线性结构反映结点间的逻辑关系是多对多的。21.参考答案：B22.参考答案：B23.参考答案：字符串简称串，它是一种以字符为元素的特殊线性表。字符串可以看成是以字符为元素的一维数组。具体实现时，在C/C++中的字符串使用为字符型数组来表示。为了便于确定字符串的结尾，在字符型数组中使用/0（就是0）作为字符串的截止符。24.参考答案：S->next=HS,HS=S25.参考答案：B26.参考答案：B27.参考答案： 28.参考答案：A29.参考答案：B,C,D30.参考答案：B31.参考答案：B,C32.参考答案：错误33.参考答案： ASLsucc=(1+2+1+2+1+1+3+1)/8=1.534.参考答案：正确35.参考答案：[log2i]=[log2j]36.参考答案：B37.参考答案：B38.参考答案：A39.参考答案：A40.参考答案：A41.参考答案： 42.参考答案：表中一半表长和该元素在表中的位置43.参考答案：后进先出；先进先出44.参考答案：1445.参考答案： 递归算法： 递归算法的时间复杂度为O（2n），空间复杂度为O（n）；非递归算法的时间复杂度为O（n），空间复杂度为O（1）。46.参考答案：B47.参考答案：正确48.参考答案：1；2；4；8；549.参考答案：D50.参考答案：B,C,D51.参考答案：正确52.参考答案：LIFO；FIFO53.参考答案：B54.参考答案：正确55.参考答案：A56.参考答案： 57.参考答案： 58.参考答案：B59.参考答案：B60.参考答案：D61.参考答案：A62.参考答案：563.参考答案：A64.参考答案：1，2，4，8，3，5，965.参考答案：A66.参考答案：n/m67.参考答案：错误68.参考答案：D69.参考答案：2k-1+1；2k-170.参考答案： 直接插入排序。71.参考答案：正确72.参考答案：正确73.参考答案：2n-174.参考答案：A75.参考答案：A第2卷参考答案一.参考题库1.参考答案：索引；开始地址2.参考答案：令Fk表示含有最少结点的深度为k的平衡二叉树的结点树目，则： F.1=1，F2=2，…，Fn=Fn-2+Fn-1+1。含有12个结点的平衡二叉树的最大深度为5，例如： 3.参考答案：有；无4.参考答案：向上；根结点5.参考答案： 6.参考答案：错误7.参考答案：错误8.参考答案：错误9.参考答案：（H，C，Q，P，A，M，S，R，D，F，X，Y）；（P，A，C，S，Q，D，F，X，R，H，M，Y）；（H，Q，C，Y，A，P，M，S，D，R，F，X）；（F，H，C，D，P，A，M，Q，R，S，Y，X）；（A，D，C，R，F，Q，M，S，Y，P，H，X）10.参考答案：A11.参考答案：D12.参考答案：正确13.参考答案： 14.参考答案： 在队列的顺序存储结构中，设队头指针为front，队尾指针为rear，队列的容量（即存储的空间大小）为maxnum。当有元素要加入队列（即入队）时，若rear=maxnum，则会发生队列的上溢现象，此时就不能将该元素加入队列。对于队列，还有一种“假溢出”现象，队列中尚余有足够的空间，但元素却不能入队，一般是由于队列的存储结构或操作方式的选择不当所致，可以用循环队列解决。 一般地，要解决队列的上溢现象可有以下几种方法： （1）可建立一个足够大的存储空间以避免溢出，但这样做往往会造成空间使用率低，浪费存储空间。 （2）要避免出现“假溢出”现象可用以下方法解决： 第一种：采用移动元素的方法。每当有一个新元素入队，就将队列中已有的元素向队头移动一个位置，假定空余空间足够。 第二种：每当删去一个队头元素，则可依次移动队列中的元素总是使front指针指向队列中的第一个位置。 第三种：采用循环队列方式