数据结构复习题

单项选择题1、向一个有255个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动〔〕个元素。A.8

B.127.5

C.127

D.72、带头结点的单链表first为空的判定条件是：()A.first==NULLB.first->link==NULLC.first->link==firstD.first!=NULL3、

设某线性链表的头结点指针为L,L->data表示该链表的结点个数，L->next指向该链表的第一个结点，p指向新建立的结点，其类型与L相同。在建立该链表的过程中，假设希望L->next始终指向新输入的结点，可采用如下的C语言语句实现：A.p->next=L->next,L->next=p，L->data++;B.p->next=NULL,L->next=p,L->data++;C.L->data++,L->next=p->next,p->next=L;D.以上都不是。 4、设A、B、C三个字符按先后顺序依次进栈，下面哪个序列为不合法的出栈序列：A.ABC B.ACB C.BAC D.CAB5、如下陈述中正确的选项是〔

〕A．串是一种特殊的线性表

B．串的长度必须大于零C．串中元素只能是字母

D．空串就是空白串6、在二叉树的第4层上至多有多少个结点：A.10个 B.8个 C.16个D.以上都不是。7、假设一棵二叉树具有8个度为2的结点，那么该二叉树的叶子个数是〔〕A.9B.11C.7D.8、在含n个顶点和e条边的无向图的邻接矩阵中,零元素的个数为(

)

A.e

B.2e

C.n2－e

D.n2－2e9、5个不同的数据元素进行直接插入排序，最多需要进行〔〕次比拟。A.8 B.10 C.14 D10、设有关键码初始序列{Q,H,C,Y,P,A,M,S,R,D,F,X}，新序列{F,H,C,D,P,A,M,Q,R,S,Y,X}是采用以下哪种排序方法对初始序列进行第一趟扫描的结果？A.直接插入排序B.二路归并排序C.以第一元素为分界元素的快速排序D.基数排序1、在一个长度为n的顺序表的任一位置插入一个新元素的渐进时间复杂度为()。A.O(n)B.O(n/2)C.O(1)D.O(n2)2、当利用大小为n的数组顺序存储一个队列时，该队列的最大长度为()A.n-2B.n-1C.nD.n+13、链表表示线性表的优点是:A.便于随机存取B.花费的存储空间比顺序表少C.便于插入与删除D.数据元素的物理顺序与逻辑顺序相同4、设有两个串p和q，求q在p中首次出现的位置的运算称作〔〕A.连接B.模式匹配C.求子串D.求串长5、设有一个二元数组A[m][n],假设A[0][0]存放位置在644(10),A[2][2]存放位置在676(10)，每个元素占一个空间，那么A[4][5]在〔

〕位置,(10)说明用10进数表示。A.692(10)B.626(10)

C.709(10) D.724(10)6、在一棵二叉树的二叉链表中，空指针域数等于非空指针域数加()。A.2B.-1C.07、n个顶点的连通图至少有〔

〕条边A.n+1

B.n

C.n-1

D.08、无向图中一个顶点的度是指图中(

)A.通过该顶点的简单路径数

B.与该顶点相邻接的顶点数C.通过该顶点的回路数

D.与该顶点连通的顶点数9、在以下排序算法中，()算法的最坏情况下时间复杂度不高于O(nlog2n)。A.起泡排序B.希尔排序C.归并排序D.快速排序10、以下说法中错误的选项是()A.n个结点的树的各结点度数之和为n-1B.n个结点的无向图最多有n*(n-1)条边C.用相邻矩阵存储图时所需存储空间大小与图的结点数有关,而与边数无关D.散列表中碰撞的可能性大小与负载因子有关1、向顺序栈中压入新元素时，应当〔〕。A．先移动栈顶指针，再存入元素 B．先存入元素，再移动栈顶指针C．先后次序无关紧要D．同时进行2、设有向图有n个顶点和e条边，采用领接表作为其存储表示，在进行拓扑排序时，总的计算时间为〔〕。A．O〔nlog2e〕B．O〔n+e〕 C．O(ne)D．O(n2)3、线性链表不具有的特点是〔〕。A．随机访问 B．不必事先估计所需存储空间大小C．插入与删除时不必移动元素D．所需空间与线性表长度成正比4、设有一个10阶的对称矩阵A[10][10]，采用压缩存储方式按行将矩阵中下三角局部的元素存入一维数组B[]中，A[0][0]存入B[0]中，那么A[8][5]在B[]中〔〕位置。A．32 B．33 C．41D．655、设F是一个森林，B是由F转换得到的二叉树，F中有n个非叶结点，那么B中右指针域为空的结点有〔〕个。A．n-1B．nC．n+1D．n+26、具有65个结点的完全二叉树的高度为〔〕。〔根的层次号为0〕A．8B．7C．6D．57、假设待排序对象序列在排序前已按其排序码递增顺序排序，那么采用〔〕方法比拟次数最少。A．直接插入排序B．快速排序 C．归并排序D．直接选择排序8、在一个无向图中，所有顶点的度数之和等于所有边数的〔〕倍。A．3B．2C．1D．1/29、某二叉树进行前序遍历的结果为ABDEFC，中序遍历的结果为DBFEAC，那么后序遍历的结果为〔〕。A.DBFEACB.DFEBCA C.BDFECAD.BDEFAC10、假定有k个关键字互为同义词，假设用线性探测法把这k个关键字存入散列表中，至少要进行多少次探测？()1、用单链表表示的链式队列的队头在链表的〔〕位置。A.链头 B.链尾 C.链中2、只想得到1024个元素组成的序列中第5个最小元素之前的局部排序的序列，用〔〕方法最快。A.起泡排序B.快速排序 C.简单项选择择排序D.堆排序3、假设待排序序列中两个数据元素具有相同的值，在排序前后它们的相互位置发生颠倒，那么称该排序算法是不稳定的。〔〕就是不稳定的排序方法。A.起泡排序B.归并排序 C.直接插入排序D.简单项选择择排序4.数据结构中，与所使用的计算机无关的是数据的〔〕结构；A.存储 B.物理 C.逻辑 D.物理和存储5.向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动〔〕个元素A.8 B.63.5 C.63 D.76.设串s1=’ABCDEFG’，s2=’PQRST’，函数con(x,y)返回x和y串的连接串，subs(s,i,j)返回串s的从序号i开始的j个字符组成的子串，len(s)返回串s的长度，那么con(subs(s1,2,len(s2)),subs(s1,len(s2),2))的结果串是〔〕。A．BCDEF B．BCDEFG C．BCPQRST D．BCDEFEF7．二叉树是非线性数据结构，所以〔〕。A.它不能用顺序存储结构存储; B.它不能用链式存储结构存储;C.顺序存储结构和链式存储结构都能存储;D.顺序存储结构和链式存储结构都不能使用8.有8个结点的无向连通图最少有〔〕条边。A．5B.6C.7D.9．折半查找有序表〔4,6,10,12,20,30,50,70,88,100〕。假设查找表中元素58，那么它将依次与表中〔〕比拟大小，查找结果是失败。A．20,70,30,50B．30,88,70,50C．20,5010．把一棵树转换为二叉树后，这棵二叉树的形态是〔〕。A.有多种 B.唯一的C.有多种,但根结点都没有左孩子D.有多种,但根结点都没有右孩子A．k-1次B.k次C.k+1次D.k(k+1)/2次1、设H为带头结点单向循环链表的头指针，指针域为link，P为移动指针，那么表尾的判断条件是〔〕A.H->link=HB.P=HC.P->link=NULLD.P->link=H2、假设一个栈的输入序列是1，2，3，…，n,输出序列的第一个元素是n,那么第x个输出元素是〔〕A．n-x B．n-x+1 C．x D．n-x-13、广义表A=(a,(b),(),(c,d,e))的长度为(

)A4

B5

C6

D74、将一个A[1..100,1..100]的下三对角矩阵，按以行优先存入一维数组B[1..298]中，A中元素a66,65(即该元素下标i=66,j=65)在数组中的位置k为〔〕。 A194 B195 C196 D1975、以{4，5，6，7，8}作为叶子结点的权值构造哈夫曼树，那么其带权路径长度是〔〕。A65 B67 C68 D 696、具有200个结点的完全二叉树的深度为()A6 B7 C8 D97、有向图的邻接矩阵是一个()A对称矩阵 B上三角矩阵 C对角矩阵D上述说法都不对8、对线性表进行折半查找时，要求线性表必须〔〕A以顺序方式存储 B以链接方式存储C以顺序方式存储，且结点按关键字有序排列D以链接方式存储，且结点按关键字有序排列9、快速排序在〔〕情况下最不利于发挥其特长。 A被排序的数据量太大 B被排序的含有多个相同值 C被排序的数据已根本有序 D被排序的数据中有实数10、以下序列不是堆的是〔〕A(100,85,98,77,80,60,82,40,20,10,66〕B(100,95,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)1.算法分析的两个主要方面是〔〕A.空间复杂性和时间复杂性 B.正确性和简明性C.可读性和文档性 D.数据复杂性和程序复杂性2.链表是一种采用〔〕存储结构存储的线性表A.顺序 B.链式 C.星式 D.网状3、在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机那么从该缓冲区中取走数据打印。该缓冲区应该是一个〔〕结构。 A堆栈 B数组 C队列 D线性表4．线性表Ｌ在〔〕情况下适用于使用链式结构实现。A.需经常修改Ｌ中的结点值 B.Ｌ中结点结构复杂C.Ｌ中含有大量的结点 D.需不断对Ｌ进行删除插入5、先序遍历能得到A，B，C序列的不同二叉树，最多有几种〔〕A4B5 C6 D76、假设树中用一条线段把两个结点连接起来，那么〔〕。 A不一定出现环 B一定出现环 C使树的度数增1 D前面说法都不正确7、在一个图中，所有顶点的度数之和等于所有边数的〔〕倍。A1/2 B1 C2 D48、无向图中定义顶点Vi与Vj之间的路径为从Vi到达Vj的一个〔〕A顶点和边序列B边的条数C权值总和D边序列9、任何一个无向连通图的最小生成树〔〕A．只有一棵B.一棵或多棵C.一定有多棵D.可能不存在10.折半查找与二叉排序树查找的时间性能〔〕A.相同B.完全不同C.数量级都是O(log2n)D.有时不相同1．在以下存储结构中，具备随机存取特性的是〔〕A．顺序表B．单链表C．单循环链表D．带头结点的双循环链表2．在循环双向链表的p所指结点之后插入q所指结点，可执行〔〕操作来完成。A．q->prior=p;q->next=p->next;p->next->prior=q;p->next=q;B．q->prior=p;q->next=p->next;p->next=q;p->next->prior=q;C．p->next=q;p->next->prior=q;q->prior=p;q->next=p->next;D．p->next=q;q->prior=p;p->next->prior=q;q->next=p->next;3．假设一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，…，pi，…，pn，假设p1=n，那么pi为〔〕A．iB．n=iC.n-i+1D.不确定4．数组q[0..maxsize-1]作为循环队列Q的存储空间，front为队头指针，rear为队尾指针，那么出队操作为〔〕A.front=front+1B.front=(front+1)%maxsizeC.front=(rear-front+1)%maxsizeD.front=(rear-front+maxsize)%maxsize5．设有二维数组A[1..6][1..8]，每个元素用相邻的6个字节存储，存储器按字节编址。起始地址为1000，假设按行优先方式存储，元素A[1，4]的地址是〔〕A．1024B．1018C．1004D．10036.在一棵非空树中，〔〕没有双亲结点。A.根结点B.叶子结点C.分支结点D.内部结点7．具有3个结点的二叉树的形态有〔〕种。A．2B．3C．4D．58．图G有n个结点和e条边,在用邻接表表示该图时，建立图的算法的时间复杂度为〔〕A．O〔n〕

B．O(n+e)

C．O〔n3〕D．O〔n2〕9.在以下无向图G中，顶点V2的度是〔〕A.3B.A.3B.2C.4D.010．用二分查找法进行查找时，要求查找表中各元素按键值〔〕排列。A．递增 B．递减 C．递增或递减 D．无序二、填空题1、数据结构的形式定义为：数据结构是一个二元组Data_Structure=(D，S)，其中D是_________________、S是_________________.2、在一个长度为n的向量中删除第i个元素(1≤i≤n)时，需向前移动__________个元素。3、________是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。4.设S=”A;/document/Mary.doc”，那么strlen(s)=____________,“/”的字符定位的位置为_______。5、在哈希造表过程中，处理冲突的方法主要有：________________，________________，________________，________________。6、所谓稀疏矩阵指的是_______。7在图结构中，如果一个从Vp到Vq的路径上除Vp和Vq可以相同外，其它结点都不相同，那么称此路径为________________。8.一棵深度为6的满二叉树有__________个分支结点和___________个叶子。9、对于n个记录的表进行2路归并排序，整个归并排序需进行_______趟〔遍〕。1、数据结构有如下四类根本结构：集合、_________________、_________________、_________________。2、在顺序表中插入或删除一个元素，需要平均移动__________元素，具体移动的元素个数与________________有关。3.栈是一种特殊的线性表，允许插入和删除运算的一端称为________。不允许插入和删除运算的一端称为________。4、____________________________________称为空串；5、假设有二维数组A6×8，每个元素用相邻的6个字节存储，存储器按字节编址，那么数组A的体积〔存储量〕为_______________。6、一棵具有257个结点的完全二叉树，它的深度为________。7.有向图G用邻接表矩阵存储，其第i行的所有元素之和等于顶点i的_______。8、图的深度优先遍历序列______惟一的。9、从平均时间性能而言，__________排序最正确。10、线性有序表〔a1，a2，a3，…，a256〕是从小到大排列的，对一个给定的值k，用折半法检索表中与k相等的元素，在查找不成功的情况下，最多需要检索______次。设有100个结点，用折半查找时，最多比拟次数是______。1、数据结构包括数据的逻辑结构、数据的_________和数据的_________这三个方面的内容。2、在n个结点的单链表中要删除结点*p，需找到它的____________________，其时间复杂度为__________。3、循环队列的引入，目的是为了克服_______。4、子串的定位运算称为串的模式匹配；____________________称为目标串，____________________称为模式。5、三元组表中的每个结点对应于稀疏矩阵的一个非零元素，它包含有三个数据项，分别表示该元素的__________、__________和__________。6、由3个结点所构成的二叉树有__________种形态。7、n个顶点e条边的图，假设采用邻接矩阵存储，那么空间复杂度为__________。8、对于n个记录的集合进行冒泡排序，在最坏的情况下所需要的时间是________。假设对其进行快速排序，在最坏的情况下所需要的时间是__________。9、在数据的存放无规律的线性表中进行检索的最正确方法是________________。1、数据结构是一门研究非数值计算的程序设计问题中计算机的_________以及它们之间的_________和运算等的学科。2、在一个长度为n的向量的第i个元素(1≤i≤n+1)之前插入一个元素时，需向后移动__________个元素。3、用S表示入栈操作，X表示出栈操作，假设元素入栈的顺序为1234，为了得到1342出栈顺序，相应的S和X的操作串为_______。4、设S=“A:/document/Mary.doc”，那么strlen(s)=_________________,“/”的字符定位的位置为___________。5、设数组a[1…60,1…70]的基地址为2048，每个元素占2个存储单元，假设以列序为主序顺序存储，那么元素a[32,58]的存储地址为___________。6、一棵含有n(n>1)个结点的k叉树，可能到达的最大深度为___________，最小深度为___________。7、设有一稀疏图G，那么G采用___________存储较省空间。8、在插入和选择排序中，假设初始数据根本正序，那么选用___________；假设初始数据根本反序，那么选用___________。9、折半查找有序表〔4,6,12,20,28,38,50,70,88,100〕，假设查找表中元素20，它将依次与表中元素______________________比拟大小。10、在哈希函数H〔key〕=key%p中，p值最好取________________________________。11、哈夫曼树是__________________________________________________。1.算法的五个重要特征是、、可行性、输入、输出。2.将长度为n的线性表顺序存储，在表中插入或删除一个元素，在平均情况下其时间复杂度为。3.在双向链表中，每个结点含有两个指针域，一个指向前驱,一个指向。4.数组与广义表可视为的推广。5.在树中，树中所有结点度的最大值是树的，树中所有结点层次的最大值是树的。6.一棵深度为k〔k>=1〕的二叉树，它的第i〔i>=1〕层上最多有个结点，整棵树最多有个结点。7.在一个图中,如果顶点之间的连线是没有方向的，那么称该图为图；如果顶点之间的连线是有方向的，那么称该图为图。8.直接插入排序算法的平均时间复杂度是，排序过程中仅需用个辅助单元。9.查找表是同一种数据类型的数据元素的有限集合，查找表分为________查找表和________查找表。1.线性结构中元素之间存在____________关系，树形结构中元素之间存在__________________关系，2．链接存储的特点是利用_______________来表示数据元素之间的逻辑关系。循环单链表的最大优点是：_______________________。3、在顺序表中插入或删除一个元素，需要平均移动______________元素，具体移动的元素个数与______________有关。4.二维数组A[10…20][5…10]采用行序为主方式存储，每个元素占4个存储单元，并且A[10][5]的存储地址是1000，那么A[18][9]的地址是____________。5.广义表((a),((b),c),((d)))的表头是_________，表尾是___________________。6．在二叉树中，指针p所指结点为叶子结点的条件是______。7.无向图G=〔V，{E}〕中从顶点v到顶点v’的路径是一个____________序列。8.G是一个非连通无向图，共有28条边，那么该图至少有___________个顶点。9．设n0为哈夫曼树的叶子结点的数目，那么哈夫曼树共有___________个结点。10.设要将序列〔Q,H,C,Y,P,A,M,S,R,D,F,X〕中的关键码按字母顺序的升序重新排列，那么：冒泡排序一趟扫描的结果是____________________________________.11.对于长度为255的表，采用分块查找，每块的最正确长度为__________。1.树形结构中元素之间存在__________关系，图形结构中元素之间存在________________关系。2.在一个长度为n的向量中删除第i个元素(1≤i≤n)时，需向前移动__________个元素。3.设一棵完全二叉树中有500个结点，那么该二叉树的深度为__________。4._________是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。5.设无向图G中有n个顶点和e条边，那么其对应的邻接表中有_________个表头结点和_________个表结点。6.设有n个结点的完全二叉树，如果按照从自上到下、从左到右从1开始顺序编号，那么第i个结点的双亲结点编号为____________，右孩子结点的编号为___________。7.AOV网中,结点表示______,边表示______。AOE网中,边表示__________。8.设用希尔排序对数组{98，36，-9，0，47，23，1，8，10，7}进行排序，给出的步长〔也称增量序列〕依次是4，2，1那么排序需__________趟，写出第一趟结束后，数组中数据的排列次序___________________________________。9.在数据的存放无规律的线性表中进行检索的最正确方法是____________________。三、判断题()1、数据结构一般包括数据之间的逻辑结构，数据在计算机中的存储方式和数据的运算三个方面。()2、单链表从任何一个结点出发，都能访问到所有结点()3、线性表中的每个结点最多只有一个前驱和一个后继。()4、一个nXn的对称矩阵，如果采用压缩存储，其容量为n(n+1)/2。()5、n个结点的树的各结点度数之和为n-1()6、霍夫曼树一定是满二叉树。()7、只允许最下面的二层结点的度数小于2的二叉树是完全二叉树。

()8、在有向图G中，所有结点的出度之和一定等于所有结点的出度之和()9、顺序查找法与折半查找法对存储结构的要求是：顺序查找与折半查找既适用于顺序表，也适用于链表()10、散列表中碰撞的可能性大小与负载因子有关()1.记录是数据处理的最小单位。()2.链表的删除算法很简单，因为当删除链中某个结点后，计算时机自动将后续各个单元向前移动。()3.栈和队列是一种非线性数据结构。()4．假设输入序列为1,2,3,4,5,6,那么通过一个栈可以输出序列1,5,4,6,2,3。()5.从逻辑结构上看，n维数组的每个元素均属于n个向量。()6.稀疏矩阵压缩存储后，必会失去随机存取功能。()7.二叉树中每个结点的两棵子树的高度差等于1。()8．强连通图的各顶点间均可达。()9．当待排序的元素很大时，为了交换元素的位置，移动元素要占用较多的时间，这是影响时间复杂度的主要因素。()10．采用线性探测法处理散列时的冲突，当从哈希表删除一个记录时，不应将这个记录的所在位置置空，因为这会影响以后的查找。()1、记录是数据处理的最小单位。()2、线性表的逻辑顺序与存储顺序总是一致的。()3、在表结构中最常用的是线性表，栈和队列不太常用。()4、一个稀疏矩阵Am*n采用三元组形式表示，假设把三元组中有关行下标与列下标的值互换，并把m和n的值互换，那么就完成了Am*n的转置运算。()5、二维以上的数组其实是一种特殊的广义表。()6.假设二叉树用二叉链表作存贮结构，那么在n个结点的二叉树链表中只有n-1个非空指针域。()7．强连通图的各顶点间均可达。()8．对一个AOV网，从源点到终点的路径最长的路径称作关键路径。()9．当待排序的元素很大时，为了交换元素的位置，移动元素要占用较多的时间，这是影响时间复杂度的主要因素。()10．采用线性探测法处理散列时的冲突，当从哈希表删除一个记录时，不应将这个记录的所在位置置空，因为这会影响以后的查找。〔〕1、数据的根本单位是数据项。〔〕2、带权的无向连通图的最小生成树是唯一的。〔〕3、数组元素之间的关系，既不是线性的，也不是树形的。〔〕4、对于有n个对象的待排序序列进行归并排序，所需平均时间为O〔nlog2n〕。〔〕5、用邻接矩阵法存储一个图所需的存储单元数目与图的边数有关。〔〕6、在霍夫曼编码中，当两个字符出现的频率相同时，其编码也相同，对于这种情况应当特殊处理。〔〕7、线性表采用顺序存储表示时，必须占用一片连续的存储单元。〔〕8、由树转化成二叉树，其根的右子女指针总是空的。〔〕9、直接选择排序是一种稳定的排序方法。〔〕10、装载因子是散列表的一个重要参数，它反映了散列表的装满程度。〔〕1．数据元素是构成数据的根本单位，具有相对独立的含义而且是不可再分的。〔〕2．在单链表中任何两个元素的存储位置之间都有固定的联系，因为可以从头结点进行查找任何一个数据元素。〔〕3．链栈的元素入栈操作需先判断栈满。〔〕4．如果两个串含有相同的字符，那么这两个串相同。〔〕5．广义表C=〔a，〔b，c，d〕〕，取尾操作Tail〔C〕=(d)。〔〕6．具有n(n>0)个结点的完全二叉树的深度为[log2(n)]。〔〕7．完全二叉树未必是满二叉树,满二叉树也未必是完全二叉树。〔〕8．一个具有n个顶点的完全有向图的弧数为n*(n-1)。〔〕9．对任意一个图来说，从它的某个顶点出发进行一次广度优先搜索便能立刻访问到该图的所有顶点。〔〕10．对一个堆进行按层次遍历，不一定能得到一个有序序列。()1.顺序存储方式的优点是存储密度大，且插入、删除运算效率高。()2．线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。()3.用链表表示线性表的优点是便于随机存取。()4.长度为1的串和字符是相同的。()5.对于一棵非空二叉树，它的根结点作为第一层，那么它的第i层上最多能有2i－1个结点。()6.AOV网的含义是以边表示活动的网。〔〕()7.路径长度最长的路径叫做关键路径。()8.用二叉树的先序遍历和中序遍历可以导出后序遍历。()9.快速排序的速度在所有排序方法中为最快，而且所附加空间也最小。()10.负载因子(装填因子)是散列表的一个重要参数,它反映散列表的装满程度〔〕1．在待排数据根本有序的情况下，快速排序效果最好。〔〕2．稀疏矩阵的压缩存储可以用一个三元组表来表示稀疏矩阵中的非0元素。〔〕3.无向图的邻接矩阵可用一维数组存储。〔〕〔〕4．满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。〔〕5.二叉树中所有结点，如果不存在非空左子树，那么不存在非空右子树。〔〕6.假设输入序列为1,2,3,4,5,6,那么通过一个栈可得到输出序列3,2,5,6,4,1.〔〕7.线性表只能用顺序存储结构实现。〔〕8．堆是满二叉树。〔〕9．完全二叉树中的叶子结点只可能在最后两层中出现。〔〕10．Hash表的平均查找长度与处理冲突的方法无关四、简答、应用题1、设n为正整数，给出以下程序段的时间复杂度。voidfunc(intn){intk;k=1;while(k<n)k=k*3;}2、列出先序遍历能得到ABC序列的所有不同的二叉树。3、某算法如下，试说明该算法实现的功能。#defineMax100302302034516856321379217{intst[Max],top=0;while(num!=0){st[top++]=num%r;num=num/r;}while(top>0)cout<<st[--top]<<““;cout<<endl;}4、G是一个非连通无向图，共有28条边，那么该图至少有多少个顶点？〔5、对于以下图所示的有向图G，给出从顶点0到其余各顶点的最短路径及路径长度。(上图)6某二叉树先序遍历的结果为：ABDGECFH，其中序遍历的结果为：DGBEAHFC，试画出这棵二叉树。7对关键字序列〔7，4，1，14，100，30，5，9，20，134〕，设哈希函数为h(k)=k%13,试给出表长为13的哈希表〔用线性探测开放定址法处理冲突〕，并求出在等概率情况下，查找成功的平均查找长度。1、数据结构的主要研究对象是什么？2．线性表有两种存储结构：一是顺序表，二是链表。试问：〔1〕如果有n个线性表同时并存,并且在处理过程中各表的长度会动态变化,线性表的总数也会自动地改变。在此情况下，应选用哪种存储结构？为什么？〔2〕假设线性表的总数根本稳定，且很少进行插入和删除，但要求以最快的速度存取线性表中的元素，那么应采用哪种存储结构？为什么？3.设循环队列的容量为40(序号从0到39)，现经过一系列的入队和出队运算后，有：①front=11，rear=19;②front=19，rear=11；问在这两种情况下，循环队列中各有元素多少个？4.二维数组Am×m采用按行优先顺序存放，每个元素占K个存储单元，并且第一个元素的存储地址为Loc(a11)，请写出求Loc(aij)的计算公式。5.一棵度为2的树与一棵二叉树有何区别？6.图1所示的有向图，请给出该图的:(8分)(1)每个顶点的入/出度；(2)邻接矩阵；(3)邻接表； (4)逆邻接表。顶点顶点123456入度出度7．设有5个互不相同的元素a、b、c、d、e，能否通过7次比拟就将其排好序？如果能，请列出其比拟过程；如果不能，那么说明原因。〔6分〕12101461210146820152552图16537163214S：顶点号Edge：〔顶点，顶点，权值〕①〔，，〕①〔，，〕①〔，，〕①〔，，〕①〔，，〕①(,,)2、某二叉树的结点数据采用顺序存储表示如下：012345678910111213141516171819EAF0D0H00C000GI0000B〔1〕试画出此二叉树的图形表示。〔2〕将此二叉树看作森林的二叉树表示，试将它复原为森林。3、设散列表的长度为11，散列函数为H(k)=k%11，给定的关键码序列为56,74,23,11,69,22,59,29。试画出用线性探查法解决冲突时所构成的散列表。0123456789104.一棵度为m的树中有n1个度为1的结点，n2个度为2的结点，…nm个度为m的结点，问该树中有多少片叶子？5．对于堆排序法，快速排序法和归并排序法，假设仅从节省存储空间考虑，那么应该首先选取其中哪种方法？其次选取哪种方法？假设仅考虑排序结果的稳定性，那么应该选取其中哪种方法？6、如果输入序列为123456,试问能否通过栈结构得到以下两个序列:435612和135426;请说明为什么不能或如何才能得到。1.设循环队列的容量为40(序号从0到39)，现经过一系列的入队和出队运算后，有①front=11,rear=19;②front=19,rear=11;问在这两种情况下,循环队列中各有元素多少个？2.假设在树中，结点x是结点y的双亲时，用(x,y)来表示树边。一棵树边的集合为：{(i,m),(i,n),(b,e),(e,i),(b,d),(a,b),(g,k),(c,g),(c,f),(h,l),(c,h),(a,c)}用树形表示法画出此树。〔3．简述树和二叉树之间的区别与联系？4、一棵高度为h的满k叉树有如下性质：第h层上的结点都是叶结点，其余各层上每个结点都有k棵非空子树，如果按层次自顶向下，同一层自左向右，顺序从l开始对全部结点进行编号，试问：〔1〕第j层的结点个数是多少〔j=1，2，…h〕？〔2〕编号为i的结点的父结点〔假设存在〕的编号是多少？〔3〕编号为i的结点的第m个孩子结点〔假设存在〕的编号是多少？5．设一组初始记录关键字序列为(25，50，35，15，80，85，40，20，36，70)，用二路归并排序法排序并给出每一趟的排序结果。6.试比拟顺序存储结构和链式存储结构的优缺点。〔7．〔1〕．如果G1是一个具有n个顶点的连通无向图，那么G1最多有多少条边？G1最少有多少条边？〔2〕．如果G2是一个具有n个顶点的强连通有向图，那么G2最多有多少条边？G2最少有多少条边？1、数据结构的主要研究对象是什么？2.试写出如以下图所示的二叉树分别按先序、中序、后序遍历时得到的结点序列。3．假设一颗完全二叉树包含A,B,…,G七个结点，写出其邻接表和邻接矩阵。4.对具有10个数据的初始序列{100，86，48，73，35，39，42，57，66，21}，写出采用二路归并排序算法排序的每一趟的结果。5.请对如以下图所示的无向带权图，写出它的邻接矩阵，并按普里姆算法求其最小生成树6.假定对有序表：〔3，4，5，7，24，30，42，54，63，72，87，95〕进行折半查找，试答复以下问题：(1)画出描述折半查找过程的判定树；(2)假设查找元素54，需依次与哪些元素比拟？1、设n为正整数，写出以下程序段的时间复杂度(1) i=1;while(i<=n)i=i*3; }(2) I=1;j=0;while(I+j<=n){if(I<j)j++;elseI++;} 2、写一算法，输入一个任意的非负十进制数，将其转换为等值的10进制数3、给定以下网G:(1)试着找出网G的最小生成树，画出其逻辑结构图；(2)用两种不同的表示法画出网G的存储结构图；4．一关键码序列为：3