数据结构与算法学习通超星期末考试答案章节答案2024年

数据结构与算法学习通超星期末考试章节答案2024年在双向循环链表中,在p指针所指的结点后插入q所指向的新结点,其修改指针的操作是(

)。

答案:q->prior=p;q->next=p->next;p->next->prior=q;p->next=q;在双向链表存储结构中,删除p所指的结点时须修改指针(

)。

答案:p->next->prior=p->prior;p->prior->next=p->next;在单链表中,要将s所指结点插入到p所指结点之后,其语句应为(

)。

答案:s->next=p->next;p->next=s;以下说法错误的是(

)。

答案:线性表的链式存储结构优于顺序存储结构创建一个包括n个结点的有序单链表的时间复杂度是(

)。

答案:O(n2)线性表L=(a1,a2,……an),下列说法正确的是(

)。

答案:除第一个和最后一个元素外,其余每个元素都有一个且仅有一个直接前驱和直接后继。在一个长度为n的顺序表中,在第i个元素(1≤i≤n+1)之前插入一个新元素时须向后移动(

)个元素。

答案:n-i+1将两个各有n个元素的有序表归并成一个有序表,其最少的比较次数是(

)。

答案:n单链表的存储密度(

)。

答案:小于1线性表L在(

)情况下适用于使用链式结构实现。

答案:需不断对L进行删除插入线性表若采用链式存储结构时,要求内存中可用存储单元的地址(

)。

答案:连续或不连续都可以链接存储的存储结构所占存储空间(

)。

答案:分两部分,一部分存放结点值,另一部分存放表示结点间关系的指针向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变,平均要移动

的元素个数为(

)。

答案:63.5在n个结点的顺序表中,算法的时间复杂度是O(1)的操作是(

)。

答案:访问第i个结点(1≤i≤n)和求第i个结点的直接前驱(2≤i≤n)顺序表中第一个元素的存储地址是100,每个元素的长度为2,则第5个元素的地址是(

)。

答案:108(13)设广义表L=((a,b,c)),则L的长度和深度分别为(

)。

答案:1和2(12)广义表((a,b,c,d))的表头是（）。

答案:(a,b,c,d)(11)广义表A=(a,b,(c,d),(e,(f,g))),则Head(Tail(Head(Tail(Tail(A)))))的值为(

)。

答案:d(10)数组A[0..4,-1..-3,5..7]中含有元素的个数(

)。

答案:45(9)设二维数组A[1..m,1..n](即m行n列)按行存储在数组B[1..m*n]中,则二维数组元素A[i,j]在一维数组B中的下标为(

)。

答案:(i-1)*n+j-1(8)二维数组A的每个元素是由10个字符组成的串,其行下标i=0,1,…,8,列下标j=1,2,…,10。若A按行先存储,元素A[8,5]的起始地址与当A按列先存储时的元素(

)的起始地址相同。设每个字符占一个字节。

答案:A[3,10](7)若对n阶对称矩阵A以行序为主序方式将其下三角形的元素(包括主对角线上所有元素)依次存放于一维数组B[1..(n(n+1))/2]中,则在B中确定aij(i答案:j*(j-1)/2+i(6)设有一个10阶的对称矩阵A,采用压缩存储方式,以行序为主存储,a11为第一元素,其存储地址为1,每个元素占一个地址空间,则a85的地址为(

)。

答案:33(5)设有数组A[i,j],数组的每个元素长度为3字节,i的值为1到8,j的值为1到10,数组从内存首地址BA开始顺序存放,当用以列为主存放时,元素A[5,8]的存储首地址为(

)。

答案:BA+180(4)假设以行序为主序存储二维数组A=array[1..100,1..100],设每个数据元素占2个存储单元,基地址为10,则LOC[5,5]=(

)。

答案:818(3)串的长度是指(

)。

答案:串中所含字符的个数(2)串下面关于串的的叙述中,(

)是不正确的?

答案:空串是由空格构成的串(1)串是一种特殊的线性表,其特殊性体现在(

)。

答案:数据元素是一个字符n(n≥2)个权值均不相同的字符构成哈夫曼树,关于该树的叙述中,错误的是()。

答案:该树一定是一棵完全二叉树设F是一个森林,B是由F变换得的二叉树。若F中有n个非终端结点,则B中右指针域为空的结点有(

)个。

答案:n+1引入二叉线索树的目的是(

)。

答案:加快查找结点的前驱或后继的速度若X是二叉中序线索树中一个有左孩子的结点,且X不为根,则X的前驱为(

)。

答案:X的左子树中最右结点设哈夫曼树中有199个结点,则该哈夫曼树中有(

)个叶子结点。

答案:100一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反,则该二叉树一定满足(

)。

答案:只有一个叶子结点在下列存储形式中,(

)不是树的存储形式?

答案:顺序存储表示法若二叉树采用二叉链表存储结构,要交换其所有分支结点左、右子树的位置,利用(

)遍历方法最合适。

答案:后序对二叉树的结点从1开始进行连续编号,要求每个结点的编号大于其左、右孩子的编号,同一结点的左右孩子中,其左孩子的编号小于其右孩子的编号,可采用(

)遍历实现编号。

答案:后序利用二叉链表存储树,则根结点的右指针是(

)。

答案:空(5)深度为h的满m叉树的第k层有(

)个结点。(1=答案:mk-1一个具有1025个结点的二叉树的高h为(

)。

答案:11至1025之间一棵完全二叉树上有1001个结点,其中叶子结点的个数是(

)。

答案:501由3个结点可以构造出多少种不同的二叉树?(

)

答案:5把一棵树转换为二叉树后,这棵二叉树的形态是(

)。

答案:唯一的(15)下面(

)方法可以判断出一个有向图是否有环。

答案:拓扑排序/star3/origin/3485b625a8a12694386c6e533805f687.jpg

答案:0123/star3/origin/e98db2fa50f06a7205a06e3ea4dad5ed.jpg

答案:0134256(12)图的BFS生成树的树高比DFS生成树的树高(

)。

答案:小或相等(11)广度优先遍历类似于二叉树的(

)。

答案:层次遍历(10)深度优先遍历类似于二叉树的(

)。

答案:先序遍历(9)用邻接表表示图进行深度优先遍历时，通常借助(

)来实现算法。

答案:栈(8)用邻接表表示图进行广度优先遍历时，通常借助(

)来实现算法。

答案:队列(7)下面()算法适合构造一个稠密图G的最小生成树。

答案:Prim算法(6)若从无向图的任意一个顶点出发进行一次深度优先搜索可以访问图中所有的顶点，则该图一定是(

)图。

答案:连通(5)G是一个非连通无向图，共有28条边，则该图至少有(

)个顶点。

答案:9(4)n个顶点的连通图用邻接距阵表示时，该距阵至少有(

)个非零元素。

答案:2(n-1)(2)在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的(

)倍。

答案:1(1)在一个图中，所有顶点的度数之和等于图的边数的(

)倍。

答案:2(15)采用线性探测法处理冲突，可能要探测多个位置，在查找成功的情况下，所探测的这些位置上的关键字(

)。

答案:不一定都是同义词(14)设哈希表长为14，哈希函数是H(key)=key%11，表中已有数据的关键字为15，38，61，84共四个，现要将关键字为49的元素加到表中，用二次探测法解决冲突，则放入的位置是(

)。

答案:9(13)下面关于哈希查找的说法，不正确的是(

)。

答案:采用链地址法处理冲突时，查找一个元素的时间是相同的(12)下面关于哈希查找的说法，正确的是(

)。

答案:不存在特别好与坏的哈希函数，要视情况而定(11)m阶B-树是一棵(

)。

答案:m叉平衡排序树(10)下面关于B-和B+树的叙述中，不正确的是(

)。

答案:B-树和B+树都能有效地支持顺序检索(9)下列关于m阶B-树的说法错误的是(

)。

答案:非叶结点至少有m/2(m为偶数)或m/2+1(m为奇数)棵子树(8)在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A，并已知A的左孩子的平衡因子为0右孩子的平衡因子为1，则应作(

)型调整以使其平衡。

答案:RL(7)分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是(

)。

答案:(100，60，80，90，120，110，130)(6)折半搜索与二叉排序树的时间性能(

)。

答案:有时不相同(5)对22个记录的有序表作折半查找，当查找失败时，至少需要比较(

)次关键字。

答案:4(4)折半查找有序表(4，6，10，12，20，30，50，70，88，100)。若查找表中元素58，则它将依次与表中(

)比较大小，查找结果是失败。

答案:20，70，30，50(3)如果要求一个线性表既能较快的查找，又能适应动态变化的要求，最好采用(

)查找法。

答案:分块查找(2)适用于折半查找的表的存储方式及元素排列要求为(

)。

答案:顺序方式存储，元素有序(1)对n个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为(

)。

答案:(n+1)/2深度为5(设根的层数为1)的完全二叉树至少有_______个结点,至多有_______个结点。

答案:16；31数据结构是一门研究非数值计算程序设计中的_____________，以及这些对象之间的_____________和_____________的学科。

答案:操作对象；关系；操作数据结构算法中，通常用__________________和__________________两种方法衡量其效率。

答案:时间复杂度;空间复杂度链式存储结构中的结点包含____________域，_______________域。

答案:数据；指针求串T在主串S中首次出现的位置的操作是________________。

答案:模式匹配线性表、栈和队列都是

结构，可以在线性表的

位置插入和删除元素；对于栈只能在

插入和删除元素；对于队列只能在

插入元素和在

删除元素。

答案:线性；任意；栈顶；队尾；队头串的长度是指(

)。

答案:串中所含字符的个数设广义表L=((a,b,c)),则L的长度和深度分别为(

)。

答案:1和2广义表A=(a,b,(c,d),(e,(f,g))),则Head(Tail(Head(Tail(Tail(A)))))的值为(

)。

答案:d串是一种特殊的线性表,其特殊性体现在(

)。

答案:数据元素是一个字符假设以行序为主序存储二维数组A=array[1..100,1..100],设每个数据元素占2个存储单元,基地址为10,则LOC[5,5]=(

)。

答案:818设有数组A[i,j],数组的每个元素长度为3字节,i的值为1到8,j的值为1到10,数组从内存首地址BA开始顺序存放,当用以列为主存放时,元素A[5,8]的存储首地址为(

)。

答案:BA+180栈在(

)中有所应用。

答案:前三个选项都有用链接方式存储的队列,在进行删除运算时()。

答案:头、尾指针可能都要修改链式栈结点为:(data,link),top指向栈顶.若想摘除栈顶结点,并将删除结点的值保存到x中,则应执行操作(

)。

答案:x=top->data;top=top->link;数组Q[n]用来表示一个循环队列,f为当前队列头元素的前一位置,r为队尾元素的位置,假定队列中元素的个数小于n,计算队列中元素个数的公式为(

)。

答案:(n+r-f)%n若让元素1,2,3,4,5依次进栈,则出栈次序不可能出现在(

)种情况。

答案:4,3,1,2,5以下数据结构中,(

)是非线性数据结构

答案:树算法的时间复杂度取决于(

)。

答案:A和B(3)通常要求同一逻辑结构中的所有数据元素具有相同的特性,这意味着(

)。

答案:不仅数据元素所包含的数据项的个数要相同,而且对应数据项的类型要一致与数据元素本身的形式、内容、相对位置、个数无关的是数据的(

)。

答案:逻辑结构在数据结构中,从逻辑上可以把数据结构分成(

)。

答案:线性结构和非线性结构顺序表可以按下标随机（或直接）访问，顺序表还可以从某一指定元素开始，向前或向后逐个元素顺序访问

答案:对在顺序表中，逻辑上相邻的元素在物理位置上不一定相邻

答案:错已知顺序表长度为n（元素序号为0~n-1），在i位置（0≤i≤n-1）插入一个元素需要移动________个元素，把i位置（0≤i≤n-1）的元素删除需要移动_____个元素

答案:n-i;n-i-1线性表采用____存储结构时，其存储地址通常必须是连续的

答案:顺序线性表的_______存储结构是一种随机存取的存储结构

答案:顺序在一个长度为n的顺序表的表尾插入一个新元素的渐进时间复杂度为（

）

答案:O(1)已知顺序表长度为n（元素序号为0~n-1），把i位置（0≤i≤n-1）的元素删除需要移动（

）个元素

答案:n-i-1已知顺序表长度为n（元素序号为0~n-1），在i位置（0≤i≤n-1）插入一个元素需要移动（

）个元素

答案:n-i数据的逻辑结构与数据元素本身的内容和形式无关

答案:对从逻辑关系上讲，数据结构主要分为两大类：线性结构和非线性结构

答案:对数据结构是数据对象与对象中数据元素之间关系的集合

答案:对算法就是程序

答案:错数据元素是最小的项

答案:错数据结构的逻辑结构包括________结构和_______结构两大类

答案:线性;非线性数据结构包括_________、_________和数据的运算三个方面

答案:数据;结构数据是_

的载体，它能够被计算机程序识别、

和加工处理

答案:信息;存储算法的一个特性是

，即算法必须执行有限步就结束

答案:有穷性算法的一个特性是________，即针对一组确定的输入，算法应始终得出一组确定的结果。

答案:确定性i=1;while(i答案:O(logn)i=1;

的时间复杂度为（

）

答案:O(1)/star3/origin/a3b7bfdaccfee165d28b0118c4bf7827.png

答案:O(n)/star3/origin/3118fc46771e4e2420a7d18a25114e5e.png

答案:O(n^2)链表中每个结点都是两个域

答案:错链式存储在插入和删除时需要保持数据元素原来的物理顺序(地址)，不需要保持原来的逻辑顺序

答案:错线性表若采用链式存储表示时所有存储结点之间的地址可连续可不连续

答案:对在具有n个结点的按结点数据有序的线性单链表中插入一个新结点并使链表依然有序的操作的时间复杂度是____

答案:O(n含有n个结点的双向链表中，在指针p所指结点后插入一个新结点的时间复杂度为____，在指针p所指结点前插入一个新结点的时间复杂度为____

答案:O(1;O(1含有n个结点的单链表中（指针域指向后继结点），在指针p所指结点后插入一个新结点的时间复杂度为_____，在指针p所指结点前插入一个新结点的时间复杂度为______

答案:O(1;O(n线性表采用____存储结构时，其存储地址连续与否均可以

答案:链式线性表的_____存储结构是一种顺序存取的存储结构

答案:链式设单链表中结点的结构为（data,

link）。已知指针q所指结点是指针p所指结点的直接前驱，若在*q与*p之间插入结点*s，则应执行下列哪一个操作（

）

答案:s->link

=

p;

q->link

=

s;

当栈的最大长度难以估计时，最好采用______存储结构

答案:链式若堆栈采用顺序存储结构，在不产生溢出的情况下往堆栈中插人一个新元素，首先将_____游标____一个位置，然后将被插入元素放在修改后的_____游标所指出的位置

答案:栈顶<;br>;后移<;br>;栈顶<;br>在具体的程序设计过程中，栈的顺序存储结构一般是利用一个____描述的，同时还要定义一个整型变量来给出____的位置

答案:数组;栈顶;栈顶元素栈的插入和删除操作都是在_____置进行

答案:栈顶对某栈执行删除操作时，只有在(

)的情况下，才会将栈底元素删除

答案:栈中只剩1个元素若非空栈采用链式存储结构，栈的头结点指针为top，删除堆栈的一个元素的过程是依次执行：1.p=top->next，2.(

)，3.free(p)

答案:top->link=p->link若栈采用顺序存储结构，正常情况下，弹出堆栈中一个元素，栈顶指针top的变化是(

)

答案:top--若栈采用顺序存储结构，正常情况下，往堆栈中放入一个元素，栈顶指针top的变化是(

)

答案:top++若5个元素的出栈序列为1，2，3，4，5，则进栈序列可能是

答案:3，1，2，5，4栈是一种（

）的数据结构

答案:先进后出链接队列不存在溢出问题

答案:对对采用链式存储结构的栈进行操作不必判断溢出

答案:对元素进出队列一定满足“先进先出”的规律

答案:对栈允许进行删除操作的一端称为栈顶，而栈底元素是不能删除的

答案:错只要栈不空，就能任意删除栈的元素

答案:错没有元素的栈称为空栈，空栈用不着栈顶指针

答案:错只允许在表的一端进行插入和删除操作的线性表称为栈

答案:对栈和队列都是特殊的线性表

答案:对若队列采用顺序存储结构，未溢出时插入一个元素首先将_______游标_______一个位置，然后再将被插入元素放在修改后的______游标所指出的位置。

答案:队尾;后移;队尾在循环队列中，若front与rear分别表示队头元素和队尾元素的位置，则判断循环队列队空的条件是(

)

答案:front==rear若非空队列采用链式存储结构，队头元素指针与队尾元素指针分别为front和rear，删除队列的一个元素的过程是依次执行：1.p=front->next，2.(

)，3.free(p)。

答案:front=p->next若队列采用链式存储结构，队头元素指针与队尾元素指针分别为front和rear，向队列中插入一个由p所指的新结点的过程是依次执行：1.(

)，2.rear=p

答案:rear->next=p若队列采用顺序存储结构，元素的排列顺序(

)

答案:由元素进入队列的先后顺序决定某队列初始为空，若它的输入序列为a，b，c，d，它的输出序列应为(

)。

答案:a，b，c，d队列是一种（

）的数据结构

答案:先进先出对于广义表GL=（a1,a2,...,an），head(GL)=_____________。tail(GL)=__________________

答案:a1;(a2,...,an广义表的长度是指_____________________________，深度是指_________________________________。原子类型的深度为_________，空表的深度为____________

答案:最外层包含的元素个数;所含括弧的重数;0;1设n行n列的下三角矩阵A已压缩到一维数组B中，令B[1]为数组B的第一个元素。若按行为主序存储，则A[i，j]对应的B中存储位置为B[_______]

答案:i*(i-1通常采用________存储结构来存放数组。对二维数组可有两种存储方法：一种是以为______主序的存储方式，另一种是以为_______主序的存储方式。

答案:顺序;行;行序;行优先;列;列序;列优先设有二维数组A[6][8]，每个元素占6个字节存储，实现存放，A[0][0]的起始地址为1000，则数组的最后一个元素A[5][7]的地址=____________，按行优先存放时元素A[1][4]的地址=____________，按列优先存放时元素A[4][7]的地址=______________

答案:1282;1072;1276两个串相等的充分必要是___________且______________

答案:字符串长度相同;对应位置字符相同设T和P是两个给定的串，在T中找等于P的子串的过程称为

，又称P为

答案:模式匹配;模式串下面说法不正确的是（）

答案:广义表的表头总是一个广义表设广义表L=（a,（b，c，d），（e,（f））,

g），则L的长度和深度分别为（

）

答案:4和3广义表（（a，b，c，d））的表尾是（）

答案:(

)广义表（（a，b，c，d））的表头是（）

答案:(a,b,c,d)已知广义表LS=（（a，b，c），（d，e，f）），运用head和tail函数取出LS中原子e的运算是

答案:head(tail(head(tail(LS))))一个n*n的对称矩阵，如果以行或列为主序采用压缩存储，其容量为

答案:n*(n+1)/2二维数组A[10...20，5...10]，采用列优先方式存储，每个数据元素占4个存储单元，且A[10，5]的存储地址是1000，则A[20，9]的地址是

答案:1216二维数组M[i,j]的行下标i的范围从0到4，列下标j的范围从0到5，M按行存储时元素M[3,5]的起始地址与M按列存储时元素（

）的起始地址相同

答案:M[3，4]数组通常具有的两种基本操作是

答案:读取和写入对矩阵压缩存储是为了

答案:节省空间递归函数的两个要素是递归方程和

答案:边界条件对二叉链表的访问只能从_______开始

答案:根二叉树通常有_______存储结构和______存储结构两类存储结构

答案:顺序;链式具有n个结点的完全二叉树的深度为_____

答案:ceil(log2(n+1一般的，二叉树有____二叉树、只有____的二叉树、只有______的二叉树、只有______的二叉树、同时有______的二叉树五种基本形态

答案:空;根;左子树;左孩子;右子树;右孩子;左子树、右子树；左孩子、右孩子树（及一切树形结构）是一种_____结构。在树上，_____结点没有直接前趋。

答案:层次;根设二叉树有n个结点，则其深度为(

)

答案:无法确定深度为6的二叉树最多有(

)个结点

答案:63

/star3/origin/eab6be1b6225a0bc291aa7cd76bb1e96.png

答案:abdcefhg;dbachfeg;dbhfgeca/star3/origin/b2e7c41e7cd9b35523aec82b67cf9675.png

答案:abdcefg;bdacfeg;dbfgeca某二叉树的先序遍历结点访问顺序是abdgcefh,中序遍历的结点访问顺序是dgbaechf,则其后序遍历的结点访问顺序是（

）

答案:gdbehfca已知某二叉树的后续遍历序列是dabec,中序遍历序列是deabc,它的先序遍历序列是（

）

答案:cedba二叉树的中序遍历序列中，任意一个结点均处于其左子树所有结点的后面、其右子树所有节点的前面，这说说法是（

）

答案:正确二叉树的后序遍历序列中，任意一个结点均处在其子女结点的中间，这种说法（

）

答案:错误二叉树的先序遍历序列中，任意一个结点均处在其子女结点的前面，这种说法（

）

答案:正确深度优先搜索遍历类似于树的____遍历，它所有到的数据结构是____；广度优先搜索遍历类似于树的___遍历，它所用到的数据结构是___

答案:先序;栈;层次;队列图的遍历的基本方法有______优先搜索和____优先搜索两种

答案:深度;广度图的存储结构主要有____和____两种

答案:邻接矩阵;邻接表无向图的邻接矩阵是一个_____矩阵

答案:对称一个具有n个顶点的完全无向图的边数为________。一个具有n个顶点的完全有向图的弧度数为_____。

答案:n(n-1;n(n-1若顶点的偶对是有序的，此图为____图，有序偶对用_____括号括起来；若顶点偶对是无序的，此图为____图，无序偶对用____括号括起来

答案:有向;尖;<>;无向;圆;(/star3/origin/ffc3578aeefd7e7fdb9573cfb724b32a.png

答案:V1,V3,V4,V5,V2/star3/origin/b9824388450c27d7c48c44717df5bcde.png

答案:V1

V5

V3

V4

V2V7

V6

在无向图中，所有顶点的度数之和是所有边数的（

）倍

答案:2对无序表用二分法查找比顺序查找快

答案:错假设在有序线性表A[1,...,20]上进行二分查找，则比较一次查找成功的结点个数为_______，比较两次查找成功结点个数为__________，比较三次查找成功结点个数为___________，比较四次查找成功结点个数为___________，比较五次查找成功结点个数为___________，平均查找次数为__________

答案:1;2;4;8;5;3.45己知有序表为(12,18,24,35,47,50,62,83,90,115,134)当用二分法查找90时，需______次查找成功，47时_____成功，查100时，需______次才能确定不成功

答案:2;4;3采用二分查找方法查找长度为n的线性表时，每个元素的平均查找长度为

答案:O(logn)采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为A.nB.n/2C.(n+1)/2D.(n-1)/2

答案:(n+1)/2对线性表进行二分查找时，要求线性表必须

答案:以顺序方式存储，且结点按关键字有序排列顺序查找法适合于存储结构为_____________的线性表。

答案:顺序存储或链接存储设有100个数据元素，采用折半查找时，最大比较次数为（

）

答案:7对有14个数据元素的有序表R[14]进行折半查找，查找到R[3]的关键码等于给定值，此时元素比较顺序依次为（

）

答案:R[6]，R[2]，R[4]，R[3]设哈希表长为14，哈希函数是H(key)=key%11,表中已有数据的关键字为15，38，61，84共四个，现要将关键字为49的结点加到表中：（1）用线性探测法解决冲突，则放入位置是_________；（2）用平方探测法解决冲突，则放入的位置是____________

答案:8;9设哈希表长为14，哈希函数是H(key)=key%13,表中已有数据的关键字为15，29，43，70共四个，现要将关键字为56的结点加到表中：（1）用线性探测法解决冲突，则放入的位置为_________；（2）用平方探测法解决冲突，则放入的位置是___________。

答案:6;8在对一组记录（54，38，96，23，15，72，60，45，83）进行直接插入排序时，当把第7个记录60插入到有序表时，为寻找插入位置至少需比较____________

次

答案:3若一组记录的排序码为（46,79,56,38,40,84），则利用堆排序的方法建立的初始堆为（

）

答案:84,79,56,38,40,46

设要将序列（Q,H,C,Y,P,A,M,S,R,D,F,X）中的关键码按字母序的升序重新排列,二路归并排序一趟扫描的结果是__________

答案:HQCYAPMSDRFX对于n个记录的集合进行归并排序，时间复杂度为________，空间复杂度为________。

答案:O(nlog2n;O(n对于n个记录的表进行2路归并排序，整个归并排序需进行（

）趟

答案:⌈log2(n)⌉下述几种排序方法中，要求内存最大的是（

）

答案:归并排序快速排序的最坏情况,可以通过适当选择中轴元素避免。

答案:对快速排序算法在每一趟排序中都能找到一个元素放在其最终位置上。

答案:对冒泡排序的时间复杂度是O(n^2)。

答案:对对n个记录采用快速排序,所需要的平均时间是O(nlog2n)。

答案:对简单选择排序和堆排序性能都受初始序列顺序的影响。

答案:错简单选择排序和堆排序性能不受初始序列顺序的影响。

答案:对在插入排序、选择排序、快速排序、归并排方法中,要求内存量最大的是归并排。

答案:对采用堆排序时,若关键字的排列杂乱无序,则效率最高。

答案:错对序列{15,9,7,8,20,-1,4}进行排序,进行一趟后数据的排列变为{9,15,7,8,20,-1,4},则采用的排序方法是()。

答案:直接插入排序对n个不同的排序码进行冒泡(递增)排序,在下列(

)情况比较的次数最多。。

答案:从大到小排列好的对下列整数序列使用基数排序,一趟分配收集之后的结果是()。(179,208,93,306,55,859,984,9,271,33)

答案:{271,93,33,984,55,306,208,179,859,9}不同关键字序列,构造的二叉排序树的平均查找长度都相同。

答案:错二分查找法要求待查表的关键字值必须有序。

答案:对在查找过程中,不做增加、删除或修改的查找称为动态查找。

答案:错在二叉排序树上删除一个结点时,不必移动其它结点,只要将该结点的父结点的相应的指针域置空即可。

答案:错同样的数据集合,二叉排序树的查找性能与关键字的输入序列有关系。

答案:对由同一关键字集合构造的各棵二叉排序树形态和平均查找长度都不一定相同

答案:对哈希表是一种将关键字转换为存储地址的存储方法。

答案:对Hash表的平均查找长度与处理冲突的方法无关。

答案:错有n个元素存放在一维数组A[1...n]中,在进行顺序查找时,这n个数的不同排列,其平均查找长度不同。

答案:错以下不适合用分块查的数据集是()。

答案:数据分成若干块,每块(除最后一块外)中数据个数需相同;数据分成若干块,块内数据必须有序,块间不必有序;数据分成大小相等的若干块,块内数据有序对线性表进行折半查找时,要求线性表()。

答案:关键字有序;顺序存储关于哈希查找,以下说法正确的是()。

答案:装填因子越大,越容易产生冲突;哈希查找有两个关键问题:哈希函数和处理冲突的方法;链地址法和线性探测再散列都是解决冲突的方法具有12个关键字的有序表,折半查找的平均查找长度()。

答案:‘37/12已知一如下10个记录的表,其关键字序列为(2,15,19,25,30,34,44,55,58,80),用折半查找法查找关键字为55的记录,比较次数是()。

答案:2次关键路径上的活动都是关键活动,它们是否按时完成会影响工期。

答案:对任何一个有向图都一定存在拓扑序列。

答案:错若一个无向图的以顶点V1为起点进行深度优先遍历,所得的遍历序列唯一,则可以唯一确定该图。

答案:对迪杰斯特拉算法求最短路径时,是按照路径长度递增的顺序求解的。

答案:对若一个无向图中任一顶点出发,进行一次深度优先遍历,就可以访问图中所有的顶点,则该图一定是连通的。

答案:对存储无向图的邻接矩阵是对称的,因此只要存储邻接矩阵的上三角(或下三角)部分就可以了。

答案:对求稀疏图的最小生成树,用克鲁斯卡尔算法来求解较好。

答案:对判断一个有向图是否存在回路,可以用()。

答案:深度优先遍历算法;拓扑排序任何一个无向连通网的最小生成树()。

答案:有一棵或多棵如果含有n个顶点的图形成一个环,则它有(

)棵生成树。

答案:n关键路径是事件结点网络中(

)。

答案:从源点到汇点的最长路径给定二叉树先、中和后序遍历序列中的两个,可以唯一确定一棵二叉树。

答案:错完全二叉树一定存在度为1的结点。

答案:错二叉树的遍历结果不是唯一的。

答案:对满二叉树一定完全是二叉树。

答案:对具有n个叶子结点的哈夫曼树共有2n-1个结点。

答案:对一棵二叉树中,中序遍历序列的最后一个结点,必定是该二叉树前序遍历的最后一个结点。

答案:错以数据集{4,5,6,7,10,12,18}为叶结点权值所构造的哈夫曼树,其带权路径长度为()。

答案:165已知一棵度为3的树有2个度为1的结点,3个度为2的结点,4个度为3的结点,则该树中有()个叶子结点。

答案:12树最适合用来表示的结构是(

)。

答案:元素间具有分支及层次关系的结构设森林T中有4棵树,其结点个数分别为n1,n2,n3,n4,那么当森林T转换成一棵二叉树后,则根结点的右子树上有(

)个结点。

答案:n2+n3+n4广义表B=(a,B)=(a,(a,(a,…,

)))的长度为无穷大。

答案:对从逻辑结构上看,n维数组的每个元素均属于n个向量。

答案:对多维数组可以看作是一种特殊的线性表。

答案:对稀疏矩阵中非零元素的个数远小于矩阵中元素的总数。

答案:对tail(head(((a,b,c,d,e))))=(a,b,c,d,e)。

答案:错经常对数组进行的两种基本操作是查找和修改。

答案:对在稀疏矩阵的三元组顺序表中,每个三元组表示()。

答案:矩阵中非零元素的行号;矩阵中非零元素的列号;矩阵中非零元素的数据值假设以行序为主序存储二维数组A=array[1...100,1...100],设每个数组元素占2个存储单元,基地址为10,则LOC[5,5]=()。

答案:818串'student'和'Student'相等。

答案:错KMP算法的特点是在模式匹配时指示主串的指针不会回溯。

答案:对如果两个串含有相同的字符,则说明它们相等。

答案:错模式串

P=‘abaabcac'的next函数值序列为01122312。

答案:对串的存储结构有顺序串、堆串和块链串三种。

答案:对子串的定位运算称为串的模式匹配。

答案:对串是一种特殊的线性表,其特殊性体现在()。

答案:数据元素是字符消除递归不一定需要使用栈。

答案:对栈和队列都是限制存取点的线性结构。

答案:对在对不带头结点的链队列作出队操作时,不会改变头指针的值。

答案:错顺序栈因为是顺序存储,所以可以随机存取栈中任意元素。

答案:错设计一个判别表达式中括号是否匹配出现的算法,采用()的数据结构最佳。

答案:栈

顺序表适宜于顺序存取,而链表适宜于随机存取。

答案:错线性表的链式存储结构中,逻辑上相邻的两个元素在物理位置上并不一定相邻。

答案:对线性表的特点是每个元素都有一个前驱和一个后继。

答案:错静态链表与动态链表在元素的插入、删除上类似,不需做元素的移动。

答案:对若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算,则利用()存储方式最节省时间。

答案:顺序表

顺序存储方式的优点是存储密度大,且插入、删除运算效率高。

答案:错算法必须具备()这三个特性。

答案:可执行性;确定性;有穷性在数据结构中,从存储结构上可以将之分为()。

答案:顺序结构;非顺序结构在数据结构中,从逻辑上可以把数据结构分成()。

答案:线性结构和非线性结构以下数据结构中,()是非线性数据结构。

答案:树在下面的程序段中,x=x+1;的语句频度为()。for(i=1;i<=n;i++)for(j=1;j<=n;j++)x=x+1;

答案:O(n^2)评价一个算法性能好坏的重要标准是()。

答案:算法的时间和空间复杂度若需要利用形式参数直接访问修改实参值,则应将形参说明为()参数。

答案:指针下列程序段的时间复杂度为

。sum=0;for(i=0;i<=n;i++)

for(j=0;j答案:O(n3设n为正整数，下列划线语句的执行频度为

。

i=1;k=0;while(i答案:n-1;f(n一个算法的时间复杂度为(n3+n2log2n+14n)/n2，其数量级表示为________。

答案:O(n通常从四个方面评价算法的质量：_________、_________、_________和_________。

答案:正确性;正确;易读性;可读性;强壮性;健壮;健壮性;高效率低存储;高效率低存储量需求评估一个算法的优劣，通常从

和

空间复杂度两个方面考察。

答案:时间复杂度;时间数据元素的存储结构形式有两种：顺序存储结构和

。

答案:链式存储结构线性结构中元素之间存在一对一关系，树形结构中元素之间存在

关系，图形结构中元素之间存在

多对多

关系。

答案:一对多数据逻辑结构包括集合结构、线性结构、树形结构和

四种类型。

答案:图状结构;图形结构以下数据结构中哪一个是非线性结构？(

)

答案:二叉树数据结构在计算机内存中的表示是指

答案:数据的存储结构在数据结构中，与所使用的计算机无关的是数据的

结构。

答案:逻辑在数据结构中，从逻辑上可以把数据结构分为

答案:线性结构和非线性结构在存储数据时，通常不仅要存储各数据元素的值，而且还要存储

答案:数据元素之间的关系顺序存储结构的主要缺点是不利于插入或删除操作。

答案:对在顺序表中取出第i个元素所花费的时间与i成正比。

答案:错在顺序表中逻辑上相邻的元素，其对应的物理位置也是相邻的。

答案:对顺序存储的线性表可以随机存取。

答案:对对于顺序存储的长度为n的线性表，删除第一个元素和插入最后一个元素的时间复杂度分别对应为O(1)和O(n)。

答案:错所谓随机存取，就是通过首地址和元素的位序号值可以在O(1)的时间内找到指定的元素。

答案:对在顺序表上进行插入、删除操作时需要移动元素的个数与待插入或待删除元素的位置无关。

答案:错在长度为n的顺序表的第i个位置上插入一个元素（1≤i≤n+1），元素的移动次数为

。

答案:n-i+1顺序存储表示中数据元素之间的逻辑关系是由（

）表示的。

答案:存储位置用数组表示线性表的优点是（

）。

答案:便于随机存取线性表的（

）元素没有直接后继。

答案:最后一个下面关于线性表的叙述错误的是（

）。

答案:线性表采用顺序存储便于插入和删除操作的实现若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为(

)。

答案:O(n)下述哪一条是顺序存储结构的优点？(

)

答案:存储密度大对于一单链表L（L为头指针，且结点的后继指针分量为next），其p结点（p为链表中某结点的指针）既不是第一个结点，也不是最后一个结点。（1）在p结点后的插入s结点（s为某结点的指针）的语句序列是

;p->next=s;

。（2）删除p结点的直接后继结点的语句序列是

;p->next=q->next;free(q);

。（3）若L为带头结点的单链表，则在表首插入q结点的语句序列为

;L->next=q;

，链表为空的判定条件为

。（4）若L为不带头结点的单链表，则在表首插入q结点的语句序列为

;L=q;

，链表为空的判定条件为

。

答案:s->next=p->next;q=p->next;q->next=L->next;L->next==NULL;q->next=L;L==NULL设指针变量p指向单链表中结点A，若删除单链表中结点A，则需要修改指针的操作序列为（

）。

答案:

q=p->next；p->data=q->data；p->next=q->next；free(q)；在一个具有n个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是(

)。

答案:O(n)链表不具备的特点是

答案:可随机访问任一结点非空的循环单链表head的尾结点（由p所指向）满足

答案:p->next==head不带头结点的单链表head为空的判定条件是

答案:head==NULL不论是顺序栈还是链栈，其入栈和出栈操作的时间复杂度均为____________。

答案:O(1设输入序列为1、2、3，则经过栈的作用后可以得到___________种不同的输出序列。

答案:5后缀算式923+-102/-的值为__________。中缀算式(3+4X)-2Y/3对应的后缀算式为_________。

答案:-1;34X*+2Y*3/-栈的逻辑特点是

，只允许在

插入和删除数据元素。

答案:后进先出;先进后出;栈顶输入序列为ABC，要变为ACB，经过的栈操作为(

)。

答案:push,pop,push,push,pop,pop链栈与顺序栈相比，有一个较明显的优点是(

)。

答案:通常不会出现栈满的情况若已知一个栈的进栈序列是1，2，3，，n，其输出序列为p1，p2，p3，…，pn，若p1＝n，则pi为(

)。

答案:n-i+1一个栈的进栈序列是a，b，c，d，e，则栈的不可能的输出序列是(

)。

答案:dceab已知链队列Q的头、尾指针分别是front和rear，则出队操作是：p=Q->front;

;free(p);

答案:Q->front=Q->front->next有容量为MAXSIZE的循环顺序队列cq，头指针front，尾指针rear，队空的条件是

，队满的条件是

。

答案:cq.front==cq.rear;cq.rear==cq.front;(cq.rear+1队列的逻辑特点是

。

答案:先进先出;后进后出设顺序循环队列Q[0：M-1]的头指针和尾指针分别为F和R，头指针F总是指向队头元素的前一位置，尾指针R总是指向队尾元素的当前位置，则该循环队列中的元素个数为(

)。

答案:(R-F+M)％M以下(

)不是队列的基本运算？

答案:从队列中删除第i个元素一个队列的入队序列是1，2，3，4，则队列的输出序列是(

)。

答案:1，2，3，4__________遍历二叉排序树中的结点可以得到一个递增的关键字序列（填先序、中序或后序）。

答案:中序设一棵完全二叉树中有500个结点，则该二叉树的深度为__________；若用二叉链表作为该完全二叉树的存储结构，则共有___________个空指针域。

答案:9;501若用链表存储一棵二叉树时，每个结点除数据域外，还有指向左孩子和右孩子的两个指针。在这种存储结构中，n个结点的二叉树共有________个指针域，其中有________个指针域是存放了地址，有________________个指针是空指针。

答案:2n;n-1;n+1假定一棵树的广义表表示为A（C，D（E，F，G），H（I，J）），则树中所含的结点数为__________个，树的深度为___________，树的度为_________。

答案:9;3;3已知一棵完全二叉树有47个结点，则该二叉树有(

)个叶子结点。

答案:24已知一棵高度为5的二叉树，则该二叉树的结点总数为(

)。

答案:5~31设某棵二叉树中有2000个结点，则该二叉树的最小高度为（

）。

答案:11设某棵二叉树的中序遍历序列为ABCD，前序遍历序列为CABD，则后序遍历该二叉树得到序列为（

）。

答案:BADC树最适合用来表示(

)。

答案:元素之间具有分支层次关系的数据数据元素的存储结构形式有两种：顺序存储结构和

存储结构。

答案:链式图的遍历算法有深度优先搜索和

。

答案:广度优先搜索一个算法的时间复杂度为(n3+n2log2n+14n)/n2，其数量级表示为__________。

答案:O(n已知顺序表的首地址为1000，且每个元素占用2个存储单元，则第5个数据元素的存储地址为________。

答案:1008无向图的邻接矩阵是一个_________。

答案:对称矩阵顺序栈S为空时，则栈顶指针top值为_______。

答案:-1设单链表中指针p指向结点m，若要删除m之后的结点（若存在），则需修改指针的操作为__________。

答案:p->next=p->next->next;在插入排序、冒泡排序、选择排序中，

排序是不稳定的。

答案:选择排序判断不带头结点的单链表L为空的条件是

。

答案:L==NULL树形结构中数据元素之间存在

的关系。

答案:一对多哈夫曼树是其树的带权路径长度

的二叉树。

答案:最小;最短某二叉树的前序遍历序列为ABDEC，则该二叉树的根结点为_________。

答案:A串S1=“structure”，S2=“data”,则StrDelete(S1,6,StrLength(S2))=

。

答案:struc单链表是

的链接存储表示。

答案:线性表二叉树中各结点度的

称为二叉树的度。

答案:最大值判断带头结点head的单链表为空的条件是

。

答案:head->next==NULL向一个长度为n的向量中删除第i个元素（1≤i≤n）时，需向前移动

个元素。

答案:n-i顺序查找的时间复杂度是

。

答案:O(n具有5个顶点的有向图，弧的总数最多为

。

答案:20以下哪种排序方式，第一轮排序之后一般无法找出最大（小）值（

）。

答案:希尔排序顺序查找法适用于存储结构为(

)的线性表。

答案:顺序存储或链接存储以下属于顺序存储结构优点的是（

）。

答案:存储密度大设有一个栈，按A、B、C、D的顺序进栈，则可能为出栈序列的是(

)。

答案:DCBA树的路径长度是从树根到每个结点的路径长度的(

)。

答案:总和算法是指（

）。

答案:问题求解步骤的描述树的先序遍历与(

)等价。

答案:二叉树的前序遍历链栈与顺序栈相比，有一个较明显的优点是(

)。

答案:通常不会出现栈满的情况链式存储表示中数据元素之间的逻辑关系是由(

)表示的。

答案:指针对关键字（10,14,35,20,7,43）从小到大直接插入排序，第3趟的排序结果是(

)。

答案:10,14,20,35,7,43栈的插入和删除操作在（

）。

答案:栈顶图形结构的特点是(

)。

答案:多对多两个字符串相等的条件是（

）。

答案:两串的长度相等，并且对应位置上的字符相同设无向图G中有n个顶点，则该无向图的最小生成树上有(

)条边。

答案:n-1已知一棵完全二叉树深度为6层，第6层有8个结点,则该完全二叉树的结点个数是(

)。

答案:39设s1=”Hello”,s2=”student”,函数StrDel(s2，strlen(s1)，3)的值是（

）。

答案:stud假定一个循环队列的队头和队尾指针分别为p和q，则判断队空的条件为（

）。

答案:p==q单链表中p为s的前驱结点,则删除s结点的操作是(

)。

答案:p->next=s->next;free(s);

权值集合W=(7，11，3，9，5)构造的哈夫曼树的带权路径长度是(

)。

答案:78数据结构被形式地定义为（K，R），其中K是（

）的有限集合，R是K上的关系的有限集合。

答案:数据元素设a，b为一棵二叉树上的两个节点，在中序遍历时，a在b前面的条件是(

)。

答案:a在b的左方对线性表，在下列哪种情况下应当采用链表表示？(

)

答案:经常需要进行插入和删除操作

单链表中，增加头结点的目的是为了（

）。

答案:方便运算的实现

对有6个元素的无序表进行直接插入排序，需要进行多少趟排序？(

)。

答案:5设某棵二叉树中有2000个结点，则该二叉树的最小高度为（

）。

答案:11设指针变量top指向当前顺序栈的栈顶，则删除栈顶元素的操作序列为(

)。

答案:top=top-1;串的长度是指(

)。

答案:串中所含字符的个数最小生成树边的集合里一定会包含权值

的边。

答案:最小在选择存储结构时，既要考虑数据值本身的存储，还需要考虑数据之间_______的存储。

答案:关系n个顶点的连通图的生成树含有________条边。

答案:n-1有一个算法的执行次数是f(n)=4n2-2n+6，该算法的时间复杂度是

。

答案:O(n2树所转的二叉树的根结点无

。

答案:右子树有n个叶子结点的哈夫曼树共有

结点。

答案:2n-1将一棵有100个结点的完全二叉树，按照从上到下、同一层次上按从左到石的顺序对所有结点从1开始编号，则编号为50的结点，其左孩子编号是____________。

答案:100字符串模式匹配算法有BF匹配算法和

。

答案:KMP匹配算法若用链表存储一颗二叉树时，每个结点除数据域外，还有指向左孩子和右孩子的两个指针。在这种存储结构中，n个结点的二叉树共用_______个指针域。

答案:2n判断带头结点head的单链表为空的条件是

。

答案:head->next==NULL在无向图G的邻接矩阵A中，对角线上A[i][i]的值等于_______。

答案:0若以{4，5，6，7，8}作为叶子结点的权值构造哈夫曼树，则其带权路径长度是_________。

答案:69在串S=“study”中，以t为首字符的子串有______个。

答案:4已知顺序表中每个元素占用3个存储单元，第13个元素的存储地址为336，则顺序表的首地址为_______。

答案:300栈s经过运算InitStack(s)；Push(s,a)；Push(s,b)后StackTop(s)的值是________。

答案:b对无向图，其邻接矩阵是一个关于__________对称的矩阵。

答案:主对角线顺序查找通常将给定值k放置在顺序表下标

的位置作为哨兵。

答案:0具有n个顶点的无向连通图其最小生成树具有_______边。

答案:n-1若两个串的长度相等且对应位置上的字符也相等，则称两个串

。

答案:相等字符串s="data"，它有

个子串。

答案:10在一个具有n个顶点的有向图中，若所有顶点的出度数之和为s，则所有顶点的入度数之和为(

)。

答案:s在一棵具有5层的满二叉树中结点总数为(

)。

答案:31在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队头指针和队尾指针，则判断队空的条件为（

）。

答案:rear==front栈和队列共同具有的特点是(

)。

答案:只允许在端点进行操作运算线性表的（

）元素没有直接前驱。

答案:第一个一棵完全二叉树度为1的结点个数是(

)。

答案:1或0在一个单链表中，已知q结点是p结点的前驱结点，若在q和p之间插入s结点，则须执行（

）。

答案:q->next=s;s->next=p下面的说法中，只有（

）是正确的。

答案:串是一种特殊的线性表已知一棵高度为5的二叉树，则该二叉树的结点总数为(

)。

答案:5～31以下数据结构中哪一个是非线性结构？(

)。

答案:二叉树在一个长度为n的顺序表中删除第i个元素（0<=i<=n）时，需向前移动（

）个元素。

答案:n-i

下列哪项不是树转换为二叉树的步骤？(

)

答案:删去二叉树中所有的双亲结点与右孩子结点的连线。有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为(

)。

答案:匹配已知栈的容量为4。若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则可能出现的出栈序列为（

）。

答案:3,2,5,4,1,6栈和队列具有相同的(

)。

答案:逻辑结构在一个具有n个单元的顺序栈中，假定以地址低端（即0单元）作为栈底，以top作为栈顶指针，当做出栈处理时，top变化为（

）。

答案:top--顺序查找平均情况下算法的时间复杂度为(

)。

答案:O(n)一个栈的输入序列为abc，则下列序列中不可能是栈的输出序列的是(

)。

答案:

cab折半查找法适用于存储结构为(

)的有序表。

答案:顺序存储字符串“key”有(

)个子串。

答案:7下列哪一种图的邻接矩阵是对称矩阵？(

)

答案:无向图数据结构在计算机内存中的表示是指(

)。

答案:数据的存储结构有关二叉树下列说法正确的是（

）。

答案:一棵二叉树的度可以小于2以下(

)不是队列的基本运算。

答案:从队列中删除第i个元素编写算法，实现将两个非递减顺序表L1和L2合并到新的顺序表L中，使合并后的顺序表仍然保持非递减的特性，函数头部定义如下

List*merge(List*L1,List*L2){}已知：1）创建新表的算法List*MakeEmpty(){

List*PtrL;

PtrL=(List*)malloc(sizeof(List));

PtrL->Last=-1;

returnPtrL;}2）插入元素算法voidInsert(ElementTypeX,inti,List*PtrL){

intj;

if(PtrL->Last==MAXSIZE-1){

/*表空间已满，不能插入*/

printf("表满");

return;

}

if(i<1||i>PtrL->Last+2){/*检查插入位置的合法性*/

printf("位置不合法");

return;

}

for(j=PtrL->Last;j>=i-1;j--)

PtrL->Data[j+1]=PtrL->Data[j];

/*将ai～an倒序向后移动*/

PtrL->Data[i-1]=X;

/*新元素插入*/

PtrL->Last++;

/*Last仍指向最后元素*/

return;

}

1、完成时间本周日19：00,互评完成时间本周日22：00前2、函数头不要变更，只需完成函数内部的实现代码，不需要调通程序。

答案:评分标准：1、算法的插入步骤正确：分别比较L1、L2中元素大小分别插入顺序表L得70分

2、在1的基础上，分别考虑到L1、L2表中剩余的元素插入情况70分~90分

3、在前两点基础上，算法简洁，可阅读性强得90-100分List*merge(List*L1,List*L2){inti=0,j=0;

List*L=MakeEmpty();

/*初始化顺序表L*/

while(iLast+1&&jLast+1)

if(L1->Data[i]Data[j])

/*将L1->data[i]插入到L尾部*/

{

Insert(L1->Data[i],L->Last+2,L);

i++;}

else

/*将L2->data[j]插入到L的尾部*/

{

Insert(L2->Data[j],L->Last+2,L);j++;}

while(iLast+1)

/*L2中的元素已插完,将L1的剩余部分插入到L尾部*/

{

Insert(L1->Data[i],L->Last+2,L);

i++;

}

while(jLast+1)

/*L1中的元素已插完,将L2的剩余部分插入到L尾部*/

{

Insert(L2->Data[j],L->Last+2,L);

j++;

}

returnL;}/star3/origin/f357f617e5e9e3c65b32affb1fa236c2.png

答案:LinkList*CreatList(intn){

LinkList*head,*p,*s;

/*p用于指向新链入结点,s用于指向新开辟结点*/

inti;

p=head=(LinkList*)malloc(sizeof(LinkList));/*1、创建头结点head，p为当前的尾节点*/

for(i=1;i<=n;i++)

{

s=(LinkList*)malloc(sizeof(LinkList));

/*2、s指向新开辟结点*/

scanf("%d",&s->data);

/*新结点数据域赋值*/

p->next=s;

/*将新结点连接到p所指结点的后面*/

p=s;

/*p指向新链入结点*/

}

p->next=NULL;

/*尾结点的指针域置为空*/

returnhead;

/*返回头指针*/}编写算法，将十进制正整数m转换成n(2≤n≤9)进制数。已知栈的初始化函数为：sqStack*createStack()出栈函数为intpop(sqStack*s)，压栈函数为：voidpush(sqStack*s,intx)算法头：voidconversion(intm,intn)（要求在conversion中输出n进制转换后的每一位对应的数值）

答案:评分标准：1、算法的插入步骤正确：使用题目中给定的新建栈，入栈压栈函数完成此题功能得80分

2、在1的基础上，算法简洁，可阅读性强得90-100分voidconversion(intm,intn){/*---------------1、新建栈--------------------------*/

sqStack*s=createStack();

/*---------------2、辗转相除取余数m%n，余数压栈，循环操作，直至m为0-----------------*/

while(m)

{

intremainder=m%n;

m=m/n;

push(s,remainder);

}

printf("十进制数%d转换为%d数为:",m,n);

/*---------------3、元素依次出栈，即为转换后的进制------------------------*/

while(s->top!=-1)

{

printf("%d",pop(s));

}

printf("\n");}设计一个递归算法，实现对顺序查找表ST中key为k的二分查找,，表的长度为n；算法头给定：intbinsearch(stable*ST,intlow,inthigh，intk)评分标准：1、使用递归函数设计正确

得80-90分

2、程序简洁可读性强得90-100分

3、代码简洁易懂得90-100分

答案:intbinsearch(stable*ST,intlow,inthigh，intk){

if(lowdata[mid].key==key)

returnmid;

/*找到*/

elseif(keydata[mid].key)

returnbinsearch(ST,low,mid-1,k);

/*在左半区*/

elselow=mid+1;

returnbinsearch(ST,mid+1,high,k);

/*在右半区*/

}某算法的时间复杂度为O(N*N)，表明该算法的()。【武汉大学2006]

答案:问题规模是N*N27.可以用()定义一个完整的数据结构。【中山大学2004一、1(1分)】

答案:抽象数据类型在定义ADT时。除数据对象和数据关系外，还需说明()。【北京理工大学2005一l分)】

答案:基本操作6.在数据结构中，数据的最小本单位是()。【北京理工大学2006九、1(1分)】

答案:数据项6.在数据结构中，数据的基本单位是()。【北京理工大学2004五、1(1分)】

答案:数据元素下面算法的时间复杂度x=0;y=0;for(k=1;k<=n;k++)x++;for(i=1;i<=m;i++)for(j=1;j<=n;j++)y++;

答案:o(n+n*m)下面程序段的时间复杂度是（

）。

for(i=0;i答案:O(m*n)在数据结构的讨论中把数据结构从逻辑上分为（）两大类。

答案:线性结构与非线性结构研究数据结构就是研究（

）

答案:数据的逻辑结构、存储结构及其基本操作完善下列算法，实现二叉树所有结点左右子树的交换voidexchange(BiTreebt)//将二叉树bt所有结点的左右子树交换{

if(

1

)

{BiTrees；

s=bt->lchild;

2

;

3

;

4

;

exchange(bt->rchild);

}}

答案:bt;bt!=NULL;bt->lchild=bt->rchild;bt->rchild=s;exchange(bt->lchild完善下列算法，实现返回二叉树先序遍历序列的最后一个结点BiTreeLastNode(BiTreebt)//返回二叉树bt先序序列的最后一个结点的指针{BiTreep=bt;if(

1

)return(NULL);elsewhile(

2

)

if(p->rchild)

3

;

elseif(p->lchild)p=p->lchild;

else

4

;

}

答案:bt==NULL;p==NULL;p!=NULL;p;p=p->rchild;returnp；return(p有一份电文中共使用6个字符:a,b,c,d,e,f,它们的出现频率依次为2,3,4,7,8,9，试构造一棵哈夫曼树，则其加权路径长度WPL为_(1)__，字符c的编码是_(2)__。【中国矿业大学2000一、7（3分）】

答案:80;000；001；010；100；110；101；111；011一棵左子树为空的二叉树在先序线索化后，其中的空链域的个数为：______。【厦门大学2002六、1（4分）】

答案:2如果结点A有3个兄弟，而且B是A的双亲，则B的度是______。【西安电子科技大学1999软件一、4（2分）】

答案:4在二叉树中，使用二叉链表保存（指向左右孩子的指针分别为lchild,rchild）指针p所指结点为叶子结点的条件是______。【合肥工业大学1999三、7（2分）】

答案:p->lchild==NULL&&p->rchild==NULL

；p->rchild==NULL&&p->lchild==NULL下述编码中哪一个不是前缀码（

）。【中科院计算所2000一、2（2分）】

答案:（0，1，00，11）48.一棵左右子树均不空的二叉树在先序线索化后，其中空的链域的个数是：(

)。

【合肥工业大学2000一、5（2分）】

答案:1一棵二叉树的前序遍历序列为ABCDEFG，它的中序遍历序列可能是（

）【北京工业大学2001一、2(2分)】A．

B．

C．

D．

答案:ABCDEFG对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用(

)次序的遍历实现编号升序排列。【北京理工大学2000一、4（2分）】

答案:后序利用二叉链表存储树，则根结点的右指针是（

）。【青岛大学2001五、5（2分）】

答案:空将有关二叉树的概念推广到三叉树，则一棵有244个结点的完全三叉树的高度（）【南京理工大学2000一、51.5分）】

答案:6一棵完全二叉树上有1001个结点，其中叶子结点的个数是（

）【西安交通大学1996三、2(3分)】

答案:501设森林F对应的二叉树为B，它有m个结点，B的根为p,p的右子树结点个数为n,森林F中第一棵树的结点个数是（

）

【南京理工大学2000一、17（1.5分）】

答案:m-n算术表达式a+b*（c+d/e）转为后缀表达式后为（

）

答案:abcde/+*+对于长度为n的关键字序列创建一颗二叉排序树，该树可能的最大高度是（

）。

答案:n对于下列关键字序列，不可能构成某二叉排序树中一条查找路径的序列是（)。【2011年全国试题7(2分)】

答