数据结构相关试题

1、(1)简述数据与数据元素的关系与区别。(2)说出数据结构中的四类基本逻辑结构，并说明哪种关系最简单、哪种关系最复杂。(3)画出线性结构的示意图。(4)画出树形结构的示意图。(5)画出图状结构的示意图。(6)什么是逻辑结构、存储结构？有哪几种存储结构？(7)简述顺序存储结构与链式存储结构在表示数据元素之间关系上的主要区别。(8)简述逻辑结构与存储结构的关系。(9)通常从哪几个方面评价算法的质量？(10)算法的时间复杂度主要有哪几种？按从优到劣的顺序写出各种表示形式。(11)简述下列概念：数据、数据元素、数据类型、数据结构、逻辑结构、存储结构、线性结构、非线性结构。(12)下列算法的时间复杂度是(

2、)。for(i=0；i<n；i+)for(j=0；j<n；j+)cij=i+j2A.O(1)B.O(n)C.O(log2n)D.O(n2)(13)下列算法的时间复杂度是()。for(i=0；i<n；i+)cii=i+iA.O(1)B.O(n)C.O(log2n)D.O(n2)5派<习题二>(1)若某线性表采用顺序存储结构，每个元素占四个存储单元，首地址为100,则下标为11的(第12个)元素的存储地址为()。(2)下列说法正确的是()。A.线性表的逻辑顺序与存储顺序总是一致的B.线性报第链式存储结构中，内存中可用的存储单元可以使连续的，也可以不连续C.线性表弟顺序

3、存储结构优于链式存储结构D.每种数据结构都具有插入、删除和查找三种基本运算(3) L是线性表，已知ListLength(L)的值是5,运算DeleteList(L,2)后ListLength(L)的值是()。A.5B.0C.4D.6(4)线性表中哪些元素只有一个直接前驱和一个直接后继()。A.首元素B.尾元素C.中间元素D.所有的元素(5)线性表(L)经运算InitList(L)后，函数lEmpty(L)的值是()A.0B.,falseC.1D.Null(6)指针P指向循环链表L的首元素的条件是()。A.P=LB.P->nest=LC.L->nest=PD.P->nest=n

4、ull(7)线性表中各元素之间的关系是()关系。A.层次B.网状C.有序D.集合(8)在单链表的一个结点中有()个指针。A.1B.2C.0D.3在双向链表的一个结点中有()个指针。A.1B.2C.0D.3(10)设非空单链表的数据字段为data,指针字段为next,指针p指向单链表中第i个结点，s指向已生成的新结点，现将s结点插入到单链表中，使其成为第i+1个结点，下列算法段能正确完成上述要求的是()。A.s->next=p->next=s;B.p->next=s;s->next=p->next;C.s->next=p->next;p->next

5、=s;交换p->data和s->data;D.p=s;s->next=p(11)设双链表中结点的前趋指针的字段分别为t1和rl,则删除双链表中指针s所指结点白操作为()。A.s->t1-r1=s->t1;s-r1=s->r1;B.s->t1-r1=s->r1;s->r1=s->t1;C.s->r1=s->t1;s->t1=s->r1->t1;D.s->t1=s-t1->r1;s->r1=s->t1;(12)假设left和right为双向链表中指向直接前趋结点和直接后继结点的指针字段

6、，现要把一个指针s所指的新结点作为非空双链表中q所指结点(中间结点)的直接后继结点插入到该双向链表中，则下列算法段能正确完成上述要求的是()。A. q->right=s;s-left=q;q-right->left=s;s-right=q->right;B. s->left=q;q->right=s;q->right->left=s;s->right=q->right;C. s->left=q;s-right=q->right;q->right-left=s;q-right=s;D.以上都不对5派<习题三>(1

7、)栈是限定在处进行插入或删除操作的线性表()0A、端点B、栈底C、栈顶D、中间(2)在栈顶一端可进行的全部操作时()。A、插入B、删除C、插入和删除D、进栈(3)4个元素按A、B、C、D、顺序连续进Szhan栈，进行Pop(S,x)元素后，x的值是()A、AB、B(4)栈的特点是()。A先进先出B后进先出(5)栈结构的元素个数是()oA不变的B可变的(6)4个元素进S栈的顺序是A、B、栈顶元素的值是()。C、CD、DC后进后出D不进不出C任意的D0C、D,进行两次Pop(S,x)操作后,C、C(7)同一个栈内各元素的类型()A必须一致B可以不一致(8)顺序栈存储空间的实现使用A链表B数组C不能

8、一致D不必不一致()。C循环链表D变量(9)一个顺序栈一旦说明，其占用空间的大小()。D动态变化D非D插入、删除元素A已固定B可以改变C不能固定(10)栈是一个线性表结构()。A不加限制的B加了限制的C推广了的(11)栈与一般线性表区别主要在方面()。A元素个数B元素类型C逻辑结构的位置(12)顺序栈是空栈的条件是()A.top=0B.top=1C.top=-1D.top=m(13)元素A、B、C、D依次进顺序栈后，栈顶元素是()。A.AB.BC.CD.D(14)经过下列栈的运算后GetTop(s)的值是()。InitStack(s)；Push(s,a)；Push(s,b)；Pop(s);A.

9、aB.bC.1D.2(15)经过下列栈的运算后EmptyStack(s)的值是()。InitStack(s)；Push(s,a)；Push(s,b)；Pop(s,x)；Pop(s,x)；A.aB.bC.1D.0(16)队列是限定在处进行插入操作的线性表()。A.端点B.队头C.队尾D.中间(17)队列是限定在处进行删除操作的线性表()。A.端点B.队头C.队尾D.中间(18)队列的特点是。A.先进先出B.后进先出C.先进后出D.不进不出(19)循环队列Sq是空队列的条件是()。ASq->read=Sq->frontB(Sq->read+1)%maxsize=Sq->fr

10、ontCSq->read=0DSq->front=0(20)循环队列Sq是满队列的条件是()。ASq->read=Sq->frontB(Sq->read+1)%maxsize=Sq->frontCSq->read=0DSq->front=0(21)当循环队列Sq是满队歹I时，存放队列元素的数组data有n个元素，则data中存放个队列元素()。A.nB.n-1C.n-2D.0(22)经过下列运算后GetHead(Q)的值是()。InitQueue(Q);EnQueue(Q,a);EnQueue(Q,b);OutQueue(Q,x)；A.aB.bC

11、.1D.2(23)链栈ls是空栈的条件是()。A.ls=nullB.ls->next=nullC.Ls=0D.ls->next=ls(24)设将整数1,2,3,4依次进栈，但只要出栈时栈非空，则可将出栈操作按任何次序夹入其中，请回答下述问题：若入、出栈次序为Push(1),Pop(),Push(2),Push(3),Pop(),Pop(),Push(4),Pop(),则出栈的数字序列为何(这里Push(i)表示进栈，Pop()表示出栈)？能否得到出栈序列1423和1432?并说明为什么不能得到或者如何得到。请分析1,2,3,4的24种排列中，哪些序列是可以通过相应的入出栈操作得到的

12、。5派<习题四>(1)设S="IAMASTUDENT”，其长度是()。(2)用是一种特殊的线性表，其特征体现在。A可以顺序存储B数据元素是一个字符C可以链接存储D数据元素可以使多个字符(3)设有两个用p和q,求q在p中首次出现的位置的运算称作()。A连接B模式匹配C求用长D求子用(4)设字符串S1="ABCDEFG,S2="PQRST,M运算：S=CONCAT(SUBSTR(S1,2,LEN(S2);SUBSTR(S1,LEN(S2),2);后的用值为()。A、BCDEFB、BCDEFGC、BCDPQRSTD、BCDEFER(5)判断题空格用和孔用的长

13、度均为1。()用是一种特殊的线性表，其特殊性体现在数据元素可以使多个字符。()判断两个用是否相等，只需要判断这两个用是否包含相同的字符即可。()将一个n刈的对称矩阵，以行为主序或以列为主序存入内存，其容量至少为n2。（）若采用三元组压缩技术存储稀疏矩阵，只要把每个元素的行标和列标互换，就完成了对该矩阵的转置运算。（）5派习题五（1）对于一个二维数组A0.m0.n,若按行序为主序存储，则人一元素Aij的存储地址为（）。（2）设数组R1.10,-2.6,2.8以行序为主序存储，设第一个元素的首地址为100,每个元素占3个存储单元，则元素A5,0,7的存储地址为（）。（3）设有一个10阶对称矩阵A采

14、用压缩存储方式以行序为主序位存储，a85的存储地址为（）。（4）数组的基本操作主要包括（）。A建立与删除B索引与修改C访问与修改D访问与索引（5）稀疏矩阵一般的压缩存储方法有两种，即（）。A二维数组和三维数组B三元组和散列C三元组和十字链表D散列和十字链表（6）设矩阵A是一个对称矩阵，为了节省空间，将其下三角矩阵按行序存放在一维数组B1,n（n+1）/2中，对下三角部分中任一元素aij（i户,j在一维数B中下标k的值是（）。Ai（i-1）/2+j-1Bi（i-1/2+jCi（i+1）/2+j-1Di（i+1）/2+j习题六填空题（1）假定一棵树的嵌套括号表示法为A（B（E）,C（F（H,I,J

15、）,G）,D）,则该树的度为（），树的深度为（），终端点的个数为（），分支结点的个数为（），双分支结点为（），三分支结点的个数为（），C结点的双亲结点为（），其孩子结点为（）和（）。（2）设F是一个森林，B是由F转换得到的二叉树，F中有n个非终端结点，则B中右指针字段为空的结点有（）。（3）对于一个具有n个结点的二叉树，当它储存在二叉树表中时，其指针字段的总数为（）个，其中（）个用于链接孩子点，（）个空暇，（4）一棵深度为K的满二叉树结点总数为（）,一棵深度为K的完全二叉树的结点总数的最小值为（），最大值为（）。（5）如果T2是由有序树T转换而来的二叉树，那么T中结点的（）序是T2中结点的（）

16、。（6）具有n个结点的完全二叉树，若按层次从上到下、从左到右对其编号（根结点为1号），则编号最大的分支结点序号为（），编号最小的分支结点序号为（）,编号最大的叶子结点序号为（），编号最小的叶子结点序号为（）。（7）有m个叶子结点的哈夫曼树，其结点总数为（）。（8）由三个结点构成的二叉树，共有（）种不同的结构。选择题（1）将一棵有100个结点的完全二叉树，从根这一层开始，每一层从左到右依次对结点编号，根据点的编号为1,则编号为49的结点的双亲的编号为（）oA.24B.25C.23D无法确定（2）深度为6（根据的层次为1）的二叉树至多有（）结点。A64B63C31D32（3）设二叉树有n个结点，则

17、其深度为。An-1BnClog2nD无法确定（4）设森林T中有三棵树，第一、第二、三棵数的活结点个数分别为n1n2n3,那么将森林转换成二叉树后，其根结点的右子树上有（）个结点。An1-1Bn2+n3Cn1+n2+n3Dn1（5）设森林T中有三棵树，第一、二、三棵数的结点个数分别为n1n2n3,那么将森林转换成二叉树后，其根结点的左子树上有（）个结点。A.n1-1B.n2+n3C.n1+n2+n3D.n1（6）设深度为K的二叉树上只有度为0或度为2的结点，则这类二叉树上所含结点总数至少（）。A.K+lB.2KC2K1D2K+1（7）树转换成二叉树后，以下结论正确的是（）。A树的先根遍历序列与其

18、对应的二叉树的先序遍历序列相同B树的先根遍历序列与其对应的二叉树的中序遍历序列相同C树的后根遍历序列与其对应的二叉树的后序遍历序列相同D以上都不对（8）某二叉树的前序遍历结点访问顺序为，ABDGCDFH中序遍历结点访问顺序为DGBAECHE,则其后续遍历结点访问顺序为（）。A.BDGCEFHAB.GDBECFHAC.BDGAECHFD.GDBDHFCA（9）在一棵非空二叉树的中序遍历序列中，根结点的右边（）。A只有右子树上的所有结点B只有右子树砂锅内的部分结点C只有左子树上的所有结点D只有左子树上的部分结点（10）任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序（）。A不发生变化B

19、发上变化C不能确定D以上都不对判断题一棵度为2的树就是一棵二叉树。()无序树的子树没有顺序之分，而二叉树的子树分为左子树和右子树。()给定二叉树的先序遍历序列和后序遍历序列，就能惟一地确定一棵二叉树。()先根序列和中根序列相同的二叉树中任意一个结点都无左孩子。()解答题(1)已知一棵树边的集合为(I,M,(I,N)(E,I),(B,E),(B,D),(A,B),(G,J),(G,K),(C,0,(C,F),(H,L),(C,H),(A,C),画出这棵树，并回答下列问题：A哪个结点是根结点？B、哪些结点是叶子结点？C、哪个结点是结点G的双亲结点？D、哪些结点是结点G的祖先结点？E、哪些结点是结点

20、G的孩子结点？哪些结点是结点E的子孙结点？F、哪些结点是结点E的兄弟结点？哪些是结点F的兄弟结点？G、结点B和N的层次分别是多少？H、树的深度是多少？I、以结点C为根的子树的深度是多少？(2)说明一棵度为2的树与一棵二叉树之间的区别。(3)试分别画出具有3个结点的树和具有3个结点的二叉树的所有结构图。(4)按照下列给定二叉树的先序遍历序列、中序遍历和后序遍历序列，分别构造出二叉树。先序遍历序歹U:EBADCFHGIK叶序遍历系歹U:ABCDEFGHIJK中序遍历序列：ACBGED而序遍历序列：ABCDEFG(5)给定的权值2,3,4,7,8,9,构造出相应的赫夫曼树和赫夫曼编码，并求出带权路径

21、的长度WPL。(6)对于图6.1给出的树，指出树中的根结点、叶结点和分支结点。并指出各个结点的度数和层数。(7)对图6.1所示的树，采用先根次序、后根次序和中根次序遍历。问得到怎样的结点序列？(8)对图6.1所示的树，分别采用先根次序的父指针表示法、子表表示法、长子-兄弟表示法，试画出各种方法的图示。(9)已知一棵度为m的树中有n1个度为1的结点，n2个度为2的结点，nm个度为m的结点，问该树中有多少个叶子结点？(10)用三个结点A,B,C可以构成多少种不同的二叉树？请把它们画出来。(11)将图6.1所示的树转换成对应的二叉树是什么样子？请把它画出来。A图6.2(12)请按先根、后根和对称序遍

22、历图6.2所示的二叉树，列出遍历所得的结点序列0(13)请将图6.2所示的二叉树转换成对应的树林，并按先根次序和后根次序遍历树林，将遍历结果与上题结果对照比较。(14)已知某二叉树的先根遍历序列为：A,B,D,E,G,C,F,H,I,J,对称次序遍历序列为：D,B,G,E,A,H,F,I,J,C,试给出该二叉树的后根次序遍历'序列。(15)试给出图6.2所示的二叉树的穿线树表示(按对称序穿线)。(16)对下图所示的森林：1)求各树的前序序列和后序序列；2)求森林的前序序列和后序序列；3)将此森林转换为相应的二叉树；4)给出(a)所示树的双亲链表表示、孩子链表表示、双亲孩子链表表示及孩子

23、兄弟链表表示等四种存储结构，并指出哪些存储结构易于求指定结点的祖先，哪些易于求指定结点的后代？6(17)画出下图所示的各二叉树所对应的森林（18）假设用于通信的电文由字符集a,b,c,d,e,f,g,h中的字母构成，这8个字母在电文中出现的概率分别为0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10。为这8个字母设计Huffman编码。若用三位二进制数（0-7）对这8个字母进行等长编码，则Huffman编码的平均码长是等长编码的百分之几？它使电文总长平均压缩多少？5派习题七填空题一个具有n个顶点的完全图的边数为（）。无向图中的连通分量定义为无向图的（）。设无向图G的

24、顶点数为n,则G最少有（）条边。一个具有n个顶点的有向完全图的弧数为（）。有向图中的强连通分量定义为有向图的（）。单项选择题（1）连通分量是（）极大连通子图。A.无向图B.有向图C树D图（2）强连通分量是（）极大连通子图。A.无向图B.有向图C.树D.图（3）有n个顶点的无向图的邻接矩阵是用（）组存储。A.n行n列B.一维C.任意行n列D.n行任意列（4）有n条边的无向图的邻接表存储法中，链边中结点的个数是（）个。A.nB.2nC.n/2D.n*n(5)一个加权的无向连通图的最小生成树()。A.有一棵或多棵B.只有一棵C.一定有多棵D.可能不存在(6)下列有关图遍历的说法中不正确的是()。A.

25、连通图的深度优先搜索是个递增过程B.图的广度优先搜索中邻接点的寻找具有“先进先出”的特征C.非连通图不能用深度优先搜索法D.图的遍历要求每个顶点仅被访问一次(7)无向图的邻接矩阵是一个()。A.对称矩阵B零矩阵C.上三角矩阵D.对角矩阵(8)下列说法中正确的是()。A.一个具有n个顶点的无向完全图的边数为n(n-1)B.连通图的生成树是该图的一个极大连通子图C.图的广度优先搜索是一个递归过程D.在非连通图的遍历过程中，每调用一次深度优先搜索算法都得到该图的一个连通分量(9)如果从无向的任一顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是()0A.完全图B.连通图C.有回路D.一棵树问

26、答题(1)假设一棵完全图包含A、B,，G七个结点，写出其邻接矩阵。(2)假设一棵完全图包含A,B,C,D四个结点，画出其邻接表。(3)设有一有向图为G=(V,E)。其中，V=v0,v1,v2,v3,E=<v1,v0>,<v2,v1>,<v3,v2>,<v3,v1>,<v0,v3>。请画出该有向图。(4)对于下面的带权有向图，写出其相邻矩阵表示，并画出其邻接表表示。(5)对于下图，从顶点v0出发分别画出其深度优先生成树和广度优先生成树VI(6)对于图所示的网络，请分别用Prim算法和Kruskal算法构造该网络的最小生成树。(7)画出以

27、顶点V1为初始源点遍历所示的有向图所得到的深度优先遍历和广度优先遍历生成森林。(8)试写出下图所示有向图的利用无前趋顶点优先算法求得的拓扑序列，设邻接表的边表结点中的邻接点序号是递增有序的。5派习题八略5派习题九填空题(1)采用二分法进行查找的查找表，应选择方式的存储结构。(2)在各种查找法中，平均查找长度与结点个数n无关的查找方法是(3) 在分块查找法中，首先查找然后再查找相应的(4) 假设在有序表A09中进行二分查找，比较一次查找成功的结点数为，比较二次查找成功的结点数为，比较三次查找成功的结点数为，比较四次查找成功的结点数为，比较五次查找成功的结点数为,平均查找长度为。(5) 查找有序表

28、R011中每个数据元素，假设查找在等概率情况下进行，则进行顺序查找的平均查找长度为,进行二次查找的平均查找长度为。(6) 假设在线性表R059中进行分块查找，共分10块，每块长度为6,若利用顺序查找法对索引表和子块进行查找，则查找每个元素的平均查找长度为。(7) 在散列存储中，装填因子a的值越大，存取数据元素时发生冲突的可能性就,装填因子a的值越小，存取数据元素时发生冲突的可能性就。(8) 在一个10阶B-树中，每个根结点所含关键字的数目最多允许为,最少允许为。(9) 一棵深度为h的B-树上，任一个叶子结点所处的层数为,当向该B-树插入一个新结点时，为了检索插入位置需读取个结点。(10)当向B

29、-树中插入关键字时，可能引起结点,最终可能导致该B-树的高度,当从B-树中删除关键字时，可能引起结点,最终可能导致该B-树的高度。(1)采用顺序查找法检索长度为n的线性表，则检索每个元素的平均比较次数为0A.nB.n/2C.(n+1)/2D.(n-1)/2(2)适于对动态查找表进行高效率查找的组织结构是。A.有序表B.分块有序表C.二叉排序树D.线性链表(3)如果要求一个线性表既能快速查找，又能适应动态变化的要求，则宜采用的检索方法是。A.分块检索B.顺序检索C.二分检索D.基于属性检索(4)对线性表进行二分查找时，要求线性表必须。A.键值有序的链接表B.键值有序的顺序表C. 链接表但键值不一

30、定有序D.顺序但键值不一定有序(5) 有一个有序表1,4,6,10,18,35,42,53,67,71,78,84,92,99,当用二分查找法查找键值为84的结点时，经比较后查找成功。A.2B.3C.4D.12(6)顺序检索一个具有n个数据元素的线性表，其时间复杂度为，二分检索一个具有n个数据元素的线性表，其时间复杂度为。A.O(n)B.O(log2n)C.O(n2)D. O(nlog2n)(7)在一棵3阶B-树上，每个结点包括的子树相同，最多为，最少为。A.1B.2C.3D.4(8)设散列表长度为m,散列函数为H(key)=key%p,为了减少发生冲突的可能性，p应取。A.小于m的最大奇数B

31、.小于m的最大素数C.小于m的最大偶数D.小于m的最大合数判断题(1)在等概率情况下实现分块查找，具平均查找长度不仅与表的个数有关，而且与每一块中的元素个数有关。()(2)删除一个排序二叉树中的一个结点，在重新插入上去，一定能得到原来的二叉排序树。()(3)只要采用顺序存储结构存放的数据元素，都可以利用折半查找法进行查找。()(4)二叉平衡树要求任意结点的左右子树的高度必须相等。()5派习题十填空题(1)排序是将一组任意排列的数据元素按的值从小到大或从大到小重新排列成有序的序列。(2)在排序前，关键字值相等的不同记录间的前后相对位置保持的排序方法称为稳定的排序方法。(3)在排序前，关键字值相等

32、的不同记录间的前后相对位置的排序方法称为不稳定的排序方法。(5)当数据已经有序时，不再进行排序的方法是排序方法。(6)在堆排序中，首先要使数据成堆，在堆中所有的都不比其孩子结点小(或大)。(7)在直接插入排序的方法中，当需要将第i个数据插入时，此时前i-1个数据是的。(8)对一个基本有序的数据进行排序排序方法运算次数最少。选择题(1)排序是根据的大小重新安排各元素的顺序。A.数组B.关键字C.元素D.结点(2)内部排序是根据关键字的大小重新安排各的顺序。A.关键字B.数据项C.文件D.数据元素(3)稳定的排序方法是指在排序中，关键字相等的不同记录间的前后相对位置A.保持不变B.保持相反C.不定

33、D.无关(4)不稳定的排序方法是指在排序中,关键字相等的不同记录间的前后相对位置。A.保持不变一步B.保持相反C.不定D.无关(5)内部排序是指在排序的整个过程中，全部数据都在计算机的A.内存储器B.外存储器C.内存储器和外存储器D.寄存器(6)直接插入排序的方法是的排序方法。A.稳定B.不稳定C.外部D.选择(7)直接插入排序的方法是从第个元素开始，插入前边适当位置的排序方法。A.1B.2C.3D.n(8)冒泡排序的方法是的排序方法。A.稳定B.不稳定C.外部D.选择(9)用冒泡排序的方法对n个数据进行排序，第一趟共比较对元素。A.1B.2C.n-1D.n(10)快速排序的方法是的排序方法。

34、A.稳定B.不稳定C.外部D.选择(11)用快速排序的方法对n个数据进行排序，首先将第个元素移到在排序后的位置。A. 1B.2C.n-1D.n(12)直接选择排序的方法是的排序方法。A.稳定B.不稳定C.外部D.选择(13)使用直接选择排序的方法对n个数据进行排序，首先将选择的元素放在第个元素的位置。B. 1B.2C.n-1D.n(14)堆排序的方法是的排序方法。A.稳定B.不稳定C.外部D.选择(15)用堆排序的方法堆n个数据进行排序，首先从堆的根选择出最大(或最小)的元素移到位置oC. 1B.2C.n-1D.n(16)基数排序的方法是的排序方法。A.稳定B.不稳定C.外部D.选择(17)用

35、基数排序的方法对n个十进制数据进行排序，对n个元素进行一趟分配时，最多被分成组，两两归并。D. 10B.2C.n-1D.n(18)直接插入排序的方法要求被排序的数据存储。A.必须是顺序B.必须是链表C.顺序或链表D.二叉树(19)冒泡排序的方法要求被排序的数据存储。A.必须是顺序B.必须是链表C.顺序或链表D.二叉树(20)快速排序的方法要求被排序的数据存储。A.必须是顺序B.必须是链表C.顺序或链表D.二叉树(21)直接选择排序的方法要求被排序的数据存储。A.必须是顺序B.必须是链表C.顺序或链表D.二叉树(22)基数排序的方法要求被排序的数据存储。A.必须是顺序B.必须是链表C.顺序或链表

36、D.二叉树(23)在下列排序方法中，是不稳定的排序方法。A.直接插入排序B.直接选择排序C.冒泡D.基数排序简答题(1)简述什么是稳定的排序，什么是不稳定的排序。(2)写出使用直接插入排序法、冒泡排序法、快速排序法、直接选择排序法、堆排序法、归并排序法对下列数据进行从小到大排序的中间过程和最后结果。83,40,63,13,84,35,96,57,39,79,61,15(3)下列程序是按关键字的值从大到小进行直接选择排序的算法，将算法补充完整。Select(listr,intn)for(i=1;i+)k=i；for(j=i+1;j+)if(rk.key<rj.key);if()swap(r

37、k,ri);/*rk与ri交换*/)(4)将下列程序按关键字值从小到大直接插入排序的算法补充完整。Straightsort(listr)for(；i+)=ri；j=i-1；while(r0.key<rj.key)=rj;J-；)=r0;)(5)将下列按关键字值从小到大进行冒泡排序的算法补充完整。Bubblesort(intn,listr)flag=;m=n-1;while(m>0&&flag)flag=0;for(i=1;i<=m;i+)if(ri.keyri+1.key)flag=;swap(ri,ri+1;/*riri+1*/)m-;)(6)若快速排序算法

38、中完成一趟快速排序的算法是Quickpass(listr,inth,intp,inti),将完整的快速排序递归算法补充完整。Quicksort(listr,ints,intt)if(s<t)Quickpass(r,s,t,i);Quicksort(r,);Quicksort(r,);)(7)若进行一趟二路归并的算法是Mpass(lista,listb,intn,inth),其中a和b是数组，该算法是将a中相邻的、长度为h的两个有序的子序列合并成一个长度为2h的一个有序子序列，n是a中记录的个数。将下列二路归并算法补充完整。Msort(lista,intn)h=;while(h<n)

39、Mpass(a,b,);h*=2;Mpass(,n,h);h*=2;)5习题H>(1)外部排序是指在排序的整个过程中，全部数据在计算机的中完成的排序。A.内存储器B.外存储器C.内存储器和外存储器D.寄存器(2)简述什么是外部排序。(3)外部排序是指在排序前被排序的全部数据都存储在计算机的储器中。一、单选题(每题2分，共20分)1. 1.对一个算法的评价，不包括如下(B)方面的内容。A.健壮性和可读性B.并行性C.正确性D.时空复杂度2. 2.在带有头结点的单链表HL中，要向表头插入一个由指针p指向的结点，则执行()。A.p->next=HL->next;HL->nex

40、t=p;B.p->next=HL;HL=p;C.p->next=HL;p=HL;D.HL=p;p->next=HL;3. 3.对线性表，在下列哪种情况下应当采用链表表示？()A.经常需要随机地存取元素B.经常需要进行插入和删除操作C.表中元素需要占据一片连续的存储空间D.表中元素的个数不变4. 4.一个栈的输入序列为123,则下列序列中不可能是栈的输出序列的是(C)A.231B.321C.312D.1235. 5.AOV网是一种()。A.有向图B.无向图C.无向无环图D.有向无环图6. 6.采用开放定址法处理散列表的冲突时，其平均查找长度()。A.低于链接法处理冲突B.高于链

41、接法处理冲突C.与链接法处理冲突相同D.高于二分查找7. 7,若需要利用形参直接访问实参时，应将形参变量说明为()参数。A.值B.函数C.指针D.引用8. 8.在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点都具有相同的()。A.行号B.列号C.元素值D,非零元素个数9. 9.快速排序在最坏情况下的时间复杂度为()。2、A.O(log2n)B.O(nlog2n)C.0(n)D.0(n)1.10. .从二叉搜索树中查找一个元素时，其时间复杂度大致为()。一-一一-_2A.O(n)B.O(1)C.O(log2n)D.O(n)2、 二、运算题(每题6分，共24分)1. 1.数据结构是指数据及

42、其相互之间的，当结点之间存在M对N(M:N)的联系时，称这种结构为2. 2.队列的插入操作是在队列的尾进行，删除操作是在队列的首进行。3. 3.当用长度为N的数组顺序存储一个栈时，假定用top=N表示栈空，则表示栈满的条件是top=0(要超出才为满)o4. 4.对于一个长度为n的单链存储的线性表，在表头插入元素的时间复杂度为,在表尾插入元素的时间复杂度为05. 5.设W为一个二维数组，其每个数据元素占用4个字节，行下标i从0到7,列下标j从0到3,则二维数组W的数据元素共占用个字节。W中第6行的元素和第4列的元素共占用个字节。若按行顺序存放二维数组W,其起始地址为100,则二维数组元素W6,3

43、的起始地址为。6. 6.广义表A=(a,(a,b),(a,b),c),则它的深度为,它的长度为7. 7.二叉树是指度为2的捌。一棵结点数为N的二叉树，其所有结点的度的总和是08. 8.对一棵二叉搜索树进行中序遍历时，得到的结点序列是一个0对一棵由算术表达式组成的二叉语法树进行后序遍历得到的结点序列是该算术表达式的9. 9.对于一棵具有n个结点的二叉树，用二叉链表存储时，其指针总数为个，其中个用于指向孩子，个指针是空闲的。10. 10.若对一棵完全二叉树从0开始进行结点的编号，并按此编号把它顺序存储到一维数组A中，即编号为0的结点存储到A0中。其余类推，则Ai元素的左孩子元素为，右孩子元素为2双

44、亲元素为11. 11.在线性表的散列存储中，处理冲突的常用方法有口凶种。12. 12.当待排序的记录数较大，排序码较随机且对稳定性不作要求时，宜采用排序；当待排序的记录数较大，存储空间允许且要求排序是稳定时,宜采用排序。3、 三、运算题(每题6分，共24分)1. 1.已知一个6M5稀疏矩阵如下所示，0000100000|0-10000000-25000000700试：(1) (1)写出它的三元组线性表；(2) (2)给出三元组线性表的顺序存储表示。2. 2.设有一个输入数据的序列是46,25,78,62,12,80)，试画出从空树起,逐个输入各个数据而生成的二叉搜索树。3. 3.对于图6所示的

45、有向图若存储它采用邻接表，并且每个顶点邻接表中的边结点都是按照终点序号从小到大的次序链接的，试写出：(1)从顶点出发进行深度优先搜索所得到的深度优先生成树；(2)从顶点出发进行广度优先搜索所得到的广度优先生成树；4. 4.已知一个图的顶点集V和边集E分别为：V=1,2,3,4,5,6,7);E=<2,1>,<3,2>,<3,6>,<4,3>,<4,5>,<4,6>,<5,1>,<5,7>,<6,1>,<6,2>,<6,5>若存储它采用邻接表，并且每个顶点邻接表中的

46、边结点都是按照终点序号从小到大的次序链接的，按主教材中介绍的拓朴排序算法进行排序，试给出得到的拓朴排序的序列4、 四、阅读算法(每题7分，共14分)1.1.intPrime(intn)(inti=1;intx=(int)sqrt(n);while(+i<=x)if(n%i=0)break;if(i>x)return1;elsereturn0;(1) (1)指出该算法的功能；(2) (2)该算法的时间复杂度是多少？(3) 2.写出下述算法的功能：voidAJ(adjlistGL,inti,intn)(QueueQ;InitQueue(Q);cout<<i<<&

47、#39;'visitedi=true;QInsert(Q,i);while(!QueueEmpty(Q)intk=QDelete(Q);edgenode*p=GLk;while(p!=NULL)intj=p->adjvex;if(!visitedj)cout<<j<<''visitedj=true;QInsert(Q,j);p=p->next;5、 五、算法填空(共8分)如下为二分查找的非递归算法，试将其填写完整。IntBinsch(ElemTypeA,intn,KeyTypeK)(intlow=0;inthigh=n-1;while

48、(low<=high)(intmid=if(K=Amid.key)returnmid;查找成功，返回元素的下标elseif(K<mid.key);/在左子表上继续查找else;在右子表上继续查找return-1;/查找失败，返回-16、 六、编写算法(共8分)HL是单链表的头指针，试写出删除头结点的算法。ElemTypeDeleFront(LNode*&HL)参考答案1、 一、单选题（每题2分，共20分）1.B2,A3.B4.C5.D6.B7.D8.A9.D10.C2、 二、填空题（每空1分，共26分）1. 1.联系图（或图结构）2. 2.尾首3. 3.top=04. 4.

49、O（1）O（n）5. 5.128441086. 6.3365515132-145-2515631.12.图77.1.（2）.有序n-1有序序列后缀表达式(或逆波兰式)2nn-1n+12i+12i+2(i-1)/2开放定址法链接法快速归并三、运算题(每题6分，共24分)(1)(1,5,1),(3,2,-1),(4,5,-2),(5,1,5),(6,3,7)三兀组线性走的顺序存储表不如图7本。（3分）4,4（a）（b>（e）<d>（t）（f）图82. 2.如图8所示。3. 3.DFS:BFS:4. 4.拓朴排序为：43657214

50、、 四、阅读算法（每题7分，共14分）1. 1.（1）判断n是否是素数（或质数）（2） O（赤）2. 2.功能为：从初始点vi出发广度优先搜索由邻接表GL所表示的图。5、 五、算法填空（8分）（low+high）/2high=mid-1low=mid+16、 六、编写算法（8分）ElemTypeDeleFront(LNode*&HL)(if(HL=NULL)cerr<<"空表"<<endl;exit(1);)LNode*p=HL;HL=HL->next;ElemTypetemp=p->data;deletep;returntemp

51、;)一、单选题（每题2分，共20分）1. 1.栈和队列的共同特点是（）。A.只允许在端点处插入和删除元素B.都是先进后出C.都是先进先出D.没有共同点2. 2.用链接方式存储的队列，在进行插入运算时（）.A.仅修改头指针B.头、尾指针都要修改C.仅修改尾指针D.头、尾指针可能都要修改3. 3.以下数据结构中哪一个是非线性结构？（）A.队列B.栈C.线性表D.二叉树4. 4.设有一个二维数组Amn,假设A00存放位置在644(10),A22存放位置在676(10),每个元素占一个空间，问A33(10)存放在什么位置？脚注(10)表示用10进制表示。A.688B.678C.692D.6965. 5

52、.树最适合用来表示()。A.有序数据元素C.元素之间具有分支层次关系的数据6. 6.二叉树的第k层的结点数最多为().A.2k-1B.2K+1C.2K-1B.无序数据元素D.元素之间无联系的数据D.2k-17. 7.若有18个元素的有序表存放在一维数组A19中，第一个元素放A1中，现进行二分查找，则查找A3的比较序列的下标依次为()A.1,2,3B.9,5,2,3C.953D.94238. 8.对n个记录的文件进行快速排序，所需要的辅助存储空间大致为A.O(1)B.O(n)C.O(1og2n)D.O(n2)9. 9.对于线性表(7,34,55,25,64,46,20,10)进行散列存储时，若选

53、用H(K)=K%9作为散列函数，则散列地址为1的元素有()个，A.1B.2C.3D.410.10.设有6个结点的无向图，该图至少应有()条边才能确保是一个连通图。A.5B.6C.7D.8二、二、填空题(每空1分，共26分)1. 1.通常从四个方面评价算法的质量：>和O2. 2.一个算法的时间复杂度为(n3+n2log2n+14n)/n2,其数量级表示为O3. 3.假定一棵树的广义表表示为A(C,D(E,F,G),H(I,J),则树中所含的结点数为个，树的深度为,树的度为O4. 4.后缀算式923+-102/-的值为o中缀算式(3+4X)-2Y/3对应的后缀算式为5. 5.若用链表存储一棵

54、二叉树时，每个结点除数据域外，还有指向左孩子和右孩子的两个指针。在这种存储结构中，n个结点的二叉树共有个指针域，其中有个指针域是存放了地址，有个指针是空指针。6. 6.对于一个具有n个顶点和e条边的有向图和无向图，在其对应的邻接表中，所含边结点分别有个和个。7. 7.AOV网是一种的图。8. 8.在一个具有n个顶点的无向完全图中，包含有条边，在一个具有n个顶点的有向完全图中，包含有条边。9. 9.假定一个线性表为(12,23,74,55,63,40),若按Key%4条件进行划分，使得同一余数的元素成为一个子表，则得到的四个子表分别为口10. 10.向一棵B树插入元素的过程中，若最终引起树根结点

55、的分裂，则新树比原树的高度011. 11.在堆排序的过程中，对任一分支结点进行筛运算的时间复杂度为,整个堆排序过程的时间复杂度为。12.12.在快速排序、堆排序、归并排序中，排序是稳定的。3、 三、运算题(每题6分，共24分)1. 1.在如下数组A中链接存储了一个线性表，表头指针为A0.next,试写出该线性表。6050789034403572041A01234567datanext图102. 2.请画出图10的邻接矩阵和邻接表。3. 3.已知一个图的顶点集V和边集E分别为：V=1,2,3,4,5,6,7;E=(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15,(3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25;用克鲁斯卡尔算法得到最小生成树，试写出在最小生成树中依次得到的各条边4. 4.画出向小根堆中加入数据4,2,5,8,3时，每加入一个数据后堆的