大数据结构习题及问题详解

第1章数据结构一、选择题.算法指的是()。A计算机程序B解决问题的计算方法C排序方法 D解决问题的有限运算序列.在数据的树形结构中，数据元素之间为()的关系。A0:0B1:1C1:nDm:n.数据的存储结构包括顺序、、散列和()4种基本类型。A索引B数组C集合D向量.一个数组元素2国与()的表示等价。A&a+iB*(a+i)C*a+iDa+i.若只需要利用形参间接访问实参指针所指向的对象，而形参本身具有相应的存储空间，则应把形参变量说明为()参数。A指针B引用C值D指针引用.若只需要利用形参实现对实参值的拷贝，函数体操作形参时与实参无关，则应把形参变量说明为()参数。A指针B引用C值D指针引用.下面程序的时间复杂性的量级为()。inti=0，s1=，s2=0；while(i++<n){if(i%2)s1+=i;elses2+=i;)A.O(1)B.O(1bn)C.O(n) D.O(2n).下面程序段的时间复杂度为()。for(inti=0;i<m;i++)for(intj=0;j<n;j++)a[i][j]=i*j;A.O(m2)B,O(n2)C,O(m+n)D,O(m*n).执行下面程序段时，S语句的执行次数为()。for(inti=1;i<=n;i++)for(intj=1,j<=i;j++)S;A.n(n-1)/2B,n(n+1)/2 C.n2/2D.n.在一个长度为n的顺序存储结构的线性表中，向第i个元素(1WiWn+1)位置插入一个元素时，需要从后向前依次后移()个元素。A.n-iB,n-i+lC,n-i-lD.i.在一个长度为n的顺序存储结构的线性表中，删除第i个元素(1WiWn+1)时，需要从前向后依次后移()个元素。A.n-iB,n-i+lC.n-i-lD.i.在一个长度为n的线性表中，删除值为x的元素时需要比较元素和移动元素的总次数为()。A.(n+1)/2 B,n/2C.nD,n+1.在一个顺序表的表尾插入一个元素的时间复杂度为()。A.O（n）B.O（1）C.O（n*n）D.O（lbn）.在一个顺序表中的任何位置插入一个元素的时间复杂度为（）。A.O（n）B.O（n/2）C.O（1）D.O（n2）.在一个单链表中删除p所指向结点的后继结点时，其算法的时间复杂度为（）。A.O（n）B.O（n/2）C.O（1）D.O（n2）.线性表的链式存储比顺序存储更有利于进行（）操作。A.查找 B.表尾插入和删除C.按值插入和删除D.表头的插入和删除.线性表的顺序存储比链式存储更有利于进行（）操作。A.查找 B.表尾插入和删除C.按值插入和删除D.表头的插入和删除.在一个单链表中，若要在P所指向的结点之后插入一个新结点，则需要相继修改（）个指针域的值.A.1 B.2 C.3 D.4.在一个带头结点的循环双向链表中，若要在P所指向的结点之前插入一个新结点，则需要相继修改（）个指针域的值。A.2B.3C.4D.6.在一个表头指针为ph的单链表中，若要向表头插入一个由指针p指向的结点，则应执行（）操作。A.ph=p;p->next=ph;B.p->next=ph;ph=p;C.p->next=ph;p=ph;D.p->next=ph->next;ph->next=p;21.在一个表头指针为ph的单链表中，若要在指针q所指结点的后面插入一个由指针p所指向的结点，则执行（）操作。A.q->next=p->next;p->next=q; B.p->next=q->next;q=p;C.q->next=p->next;p->next=q; D.p->next=q->next;q->next=p;22.在一个单链表HL中，若要删除由指针q所指向结点的后继结点（若存在的话），则执行（）操作。A.p=q->next;p->next=q->next;B.p=q->next;q->next=p;C.p=q->next;q->next=p->next;D.q->next=q->next->next;q->next=q;.在一个带头结点的循环双向链表中，若要在指针p所指向的结点之后插入一个q指针所指向的结点，则需要对q->next赋值为（）。A.P->prior B.p->nextC.p->next->next D.p->prior->prior.在一个带头结点的循环双向链表中，若要在指针p所指向的结点之前插入一个q指针所指向的结点，则需要对p->prior->next赋值为（）。A.qB.pC.p->nextD.p->prior.在一个带头结点的循环双向链表中，若要删除指针p所指向的结点则执行（）操作。p->prior->next=p->next;p->next->prior=p->prior;p->next->prior=p;p->next=p->next->next;p->prior->next=p;p->next=p->next->prior;p=p->next;p->prior->next=p->prior;.栈的插入和删除操作在（）进行。A.栈顶B.栈底C.任意位置D.指定位置.当利用大小为N的数组顺序存储一个栈时，假定用top==N表示栈空，则向这个栈插入一个元素时，首先应执行（）语句修改top指针。A.top++B.top--C.top=0D.top=N-1.假定利用数组a[N]顺序存储一个栈，用top表示栈顶指针，用top=N+1表示栈空，该数组所存储的栈的最大长度为N，则表示栈满的条件为（）。A.top==1B.top==-1C.top=0D.top=N-1.假定利用数组a[N]顺序存储一个栈，用top表示栈顶指针，用top==-1表示栈空，并已知栈未满，当元素x进栈时所执行的操作为（）。A.a[--top]=xB.a[top--]=xC.a[++top]=xD.a[top++]=x.假定利用数组a[N]顺序存储一个栈，用top表示栈顶指针，用top==-1表示栈空，并已知栈未空，当退栈并返回栈顶元素时所执行的操作为（）。Areturna[--top]Breturna[top--]Creturna[++top]Dreturna[top++].假定一个链式栈的栈顶指针用top表示，该链式栈为空的条件（）。A.top！=NULL;B.top==top->next;C.top==NULL;D.top！=top->next;.假定一个链式栈的栈顶指针用top表示，每个结点结构为，当p所指向的结点进栈时，执行的操作为（）。A.p->next=top;top=top->next;B.top=p;p->next=top;C.p->next=top->next;top->next=p;D.p->next=top;top=p;.假定一个链式栈的栈顶指针用top表示，每个结点结构为，退栈时所执行的操作为（）。A.top->next=top；B.top=top->data;C.top=top->next;D.top->next=top->next->next;.若让元素1，2,3,4依次进栈，则出栈次序不可能出现（）的情况。A.3，2，1，4B,2，1，4，3C.4，3，2，1D.1，4，2，3..在一个顺序循环队列中，队首指针指向队首元素的（）位置。A前一个B后一个C当前D最后.当利用大小为N的数组循环存储一个队列时，该队列的最大长度为（）。A.N-2B.N-1C.ND.N+1.从一个顺序循环队列中删除元素时，首先需要（）。A.前移队首指针 B.后移队首指针C.取出队首指针所指位置上的元素D.取出队尾指针所指位置上的元素.假定一个顺序循环队列的队首和队尾指针分别用f和r表示，则判断队空的条件为（）。A.f+1==r B.r+1==fC.f==0D.f==r.假定一个顺序循环队列存储于数组a[N]，其队首和队尾指针分别用f和r表示，则判断队满的条件为（）。A.（r-1）%N==fB,（r+1）%N==fC.（f-1）%N==rD,（f+1）%N==r.假定利用数组a[N]循环顺序存储一个队列，其队首和队尾指针分别用f和r表示，并已知队列未满，当元素x入列时所执行的操作为（）。A.a[++r%N]=xB.a[r++%N]=xC.a[--r%N]=x D.a[r--%N]=x.假定利用数组a[N]循环顺序存储一个队列，其队首和队尾指针分别用f和r表示，并已知队列未空，当出列并返回队首元素时所执行的操作为（）。A.returna[++r%N]B.returna[--r%N]C.returna[++f%N]D.returna[f++%N].假定一个链式队列的队首和队尾指针分别为front和rear，则判断队空的条件为（）。A.front==rearB.front！=NULLC.rear！=NULLD.front==NULL.假定一个链式队列的队首和队尾指针分别为front和rear，每个结点结构为,当出列时所进行的操作为（）。A.front=front->nextB.rear=rear->nextC.front->next=rear；rear=rear->nextD.front=front->next；front->next=rear；.假定一个带头结点的循环链式队列的队首和队尾指针分别用front和rear表示，则判断对空的条件为（）。A.front=rear->nextB.rear==NULLC.front==NULLD.front==rear.假定一个链式队列的队首和队尾指针分别为front和rear，每个结点结构为包含值域data和指针域next,则使p所指结点入列所执行的操作为（）。A.p->next=NULL；rear=rear->next=p；B.p->next=rear->next；rear=rear->next=p；C.p->next=front；front=p；D.p->next=front->next；front->next=p；.在一个长度为N的数组空间中，循环顺序存储着一个队列，该队列的队首和队尾指针分别用front和rear表示，则该队列中数组元素个数为（）。A.（rear-front）%NB.（rear-front+N）%NC.（rear+N）%ND.（front+N）%N.二维数组A[12,10]采用行优先存储，每个数据元素占用4个存储单元，该数组的首地址（即A[0，0]的地址）为1200，则A[6，5]的地址为（）。A.1400B,1404C,1372D,1460.有一个MXN的矩阵A,若采用行优先进行顺序存储，每个元素占用8个字节，则Aij（1WiWM,1WjWN）元素的相对字节地址（相对首元素地址而言）为（）。A.（（i-1）XN+j）X8B.（（i-1）XN+j-1）X8C.（iXN+j-1）X8 D.（（i-1）XN+j+1）X849.有一个NXN的下三角矩阵A,若采用行优先进行顺序存储，每个元素占用k个字节，则Aij（1WiWN,1WjWi）元素的相对字节地址（相对首元素地址而言）为（）。A.（iX（i+1）/2+j-1）X4B.（iXi/2+j）X4C.（iX（i-1）/2+j-1）X4D.（iX（i-1）/2+j）X4.树中所有结点的度等于所有结点数加（）。A.0B.1C.-1D.2.在一棵树中，（）没有前驱结点。A.树枝结点B.叶子结点C.树根结点D.空结点.在一棵树中，每个结点最多有（）个前驱结点。A.0B.1C.2D.任意多个.在一棵二叉树的二叉链表中，空指针域数等于非空指针域数加（）。A.2B.1C.0D.-1.在一棵具有n个结点的二叉树中，所有结点的空子树个数等于（）。A.nB.n-1C.n+1D.2n.在一棵具有n个结点的二叉树的第i层上，最多具有（）个结点。A.2iB.2i+1C.2i-1D.2n.在一棵深度为h的完全二叉树中，所含结点个数不小于（）。A.2hB.2h+1C.2h-1D.2h-1.在一棵深度为h的完全二叉树中，所含结点个数不大于（）。A.2hB.2h+1C.2h-1D.2h-1.在一棵具有35个结点的完全二叉树中，该树的深度为（）。A.6B.7C.5D.8.在一棵完全二叉树中，若编号为i的结点存在左孩子，则左孩子结点编号为（）。A.2iB.2i-1C,2i+1D,2i+2.在一棵完全二叉树中，若编号为i的结点存在右孩子，则右孩子结点编号为（）。A.2iB.2i-1C,2i+1D,2i+2.在一棵完全二叉树中，对于编号为i（i>1）的结点其双亲结点的编号为（）。A.（i+1）/2B.（i-1）/2C,i%2D.i/2.有如图1.1所示的一棵二叉树，则该二叉树所含单支结点数为（）。A.2B.3C.4D.5.有如图1.2所示的一棵二叉树，则该二叉树的中序遍历序列为（）。A.ABCDEFGB.CDBGFEAC.CBDAEGFD.ABECDFG.有如图1.2所示的一棵二叉树，则该二叉树的先序遍历序列为（）。A.ABCDEFGB.CDBGFEA C.CBDAEGFD.ABECDFG.有如图1.2所示的一棵二叉树，则该二叉树的后序便利序列为（）。A.ABCDEFGB.CDBGFEA C.CBDAEGFD.ABECDFG.利用n个值生成的哈夫曼树中共有（）个结点。A.nB.n+1C.2nD.2n-1.利用3,6,8,12这4个值作为叶子结点的权，生成一棵哈夫曼树，该树的带权路径长度为（）。A.55 B.29 C.58 D.38.在一个具有n个顶点的有向图中，若所有顶点的出度数之和为s，则所有的入度数之和为（）。A.sB.s-1C.s+1D.n.在一个具有n个顶点的有向图中，若所有顶点的出度数之和为s，则所有的度数之和为O。A.sB.s-1C.s+1D.2s.在一个具有n个顶点的无向图中，若具有e条边，则所有顶点的度数为（）。A.nB.eC.n+eD.2e.在一个具有n个顶点的无向完全图中，所含的边数为（）。A.n B.n（n-1） C.n（n-1）/2D.n（n+1）/2.在一个具有n个顶点的有向完全图中，所含的边数为（）。A.n B.n（n-1） C.n（n-1）/2D.n（n+1）/2.在一个具有n个顶点的无向连通图中，它包含的连通分量的个数为（）。A.0B.1C.nD.n+1.若有一个图中包含k个连通分量，若按照深度优先搜索的方法访问所有顶点，则必须调用（）次深度优先搜索遍历的算法。A.kB.1C.k-1D.k+1.若要把n个顶点连接为一个连通图，则至少需要（）条边。A.nB.n+1C.n-1D.2n.在一个具有n个顶点和e条边的无向图的邻接矩阵中，表示边存在的元素（又称为有效元素）的个数为（）。A.nB.neC.eD.2e.在一个具有n个顶点和e条边的有向图的邻接矩阵中，表示边存在的元素的个数为（）。A.nB.neC.eD.2e.在一个具有n个顶点和e条边的无向图的邻接矩阵中，边结点的个数为（）。A.nB.neC.eD.2e.对于一个有向图，若一个顶点的度为k1，出度为k2,则对应邻接表中该顶点单链表的边数结点为（）。A.klB.k2C,k1-k2D,k1+k2.对于一个有向图，若一个顶点的度为kl，出度为k2,则对应逆邻接表中该顶点单链表的边数结点为（）。A.klB.k2C,k1-k2D,k1+k2.对于一个无向图，下面（）的说法是正确的。A.每个顶点的入度等于出度B.每个顶点的度等于入度和出度之和C.每个顶点的入度为0 D.每个顶点的出度为0.在一个有向图的邻接表中，每个顶点单链表中结点的个数等于该顶点的（）。A.出边数8.入边数C.度数D.度数减一.若一个图的边集为｛（A，B）（A，C）（B，D）（C，F）（D，E）（D，F）｝，则从顶点A开始对该图进行深度优先搜索，得到的顶点序列可能为（）。A.ABCFDEB.ACFDEBC.ABDCFED.ABDFEC.若一个图的边集为｛（A，B）（A，C）（B，D）（C，F）（D，E）（D，F）｝，则从顶点A开始对该图进行广度优先搜索，得到的顶点序列可能为（）。A.ABCDEFB.ABCFDEC.ABDCEFD.ACBFDE.若一个图的边集｛（1，2）（1，4）（2，5）（3，1）（3，5）（4，3）｝，则从顶点1开始对该图进行深度优先搜索，得到的顶点序列可能为（）。A.1，2，5，4，3B,1，2，3，4，5 C,1，2，5，3，4D,1，4，3，2，5.若一个图的边集｛（1，2）（1，4）（2，5）（3，1）（3，5）（4，3）｝，则从顶点1开始对该图进行广度优先搜索，得到的顶点序列可能为（）。A.1，2，3，4，5B,1，2，4，3，5C,1，2，4，5，3D,1，4，2，5，3.由一个具有n个顶点的连通图生成的最小树中有（）条边。A.nB.n-1C.n+1D.2n.若查找每一个元素的概率相等，则在长度为n的顺序表上查找任一元素的平均查找长度为（）。A.nB,n+1C.（n-1）/2D,（n+1）/2.对长度为n的单链有序表，若查找每个元素的概率相等，则查找任一个元素的平均查找长度为（）。A.n/2B.（n+1）/2C,（n-1）/2D,n/4.对于长度为9的顺序存储的有序表，若采用二分查找，在等概率情况下的平均查找长度为（）的值除以9。A.20B.18C.25D.22.对于长度为18的顺序存储的有序表，若采用二分查找，则查找第15个元素的查找长度为（）。A.2B.3C.4D.6.对于顺序存储的有序表（5，12，20，26，37，42，46，50，64），若采用二分查找，则查找元素26的查找长度为（）。A.2B.3C.4D.5.在分块查找中，若用于保存数据元素的主表长度为n，它被分为k个子表，每个子表的长度均为n/k，若用顺序查找确定块，则分块查找的平均查找长度为（）。A.n+kB,k+n/kC.（k+n/k）/2D.（k+n/k）/2+1.在分块查找中，若用于保存数据元素的主表长度为144,它被分为12个子表，每个子表的长度均为12,若用顺序查找确定块，则分块查找的平均查找长度为（）。A.13 B.24 C.12 D.79.在一棵深度为h的具有n个元素的二叉排序树中，查找所有元素的最长查找长度为（）。A.nB.lbnC.（h+1）/2D.h.在一棵平衡二叉排序树中，每个结点的平衡因子的取值围是（）。A.-1〜1B.-2〜2C.1〜2D.0〜1.若根据查找表（23,44,36,48,52,73,64,58）建立线性哈希表，采用H（K）=K%13计算哈希地址，则元素64的哈希地址为（）。A.4B.8C.12D.13.若根据查找表（23,44,36,48,52,73,64,58）建立线形哈希表，采用H（K）=K%13计算哈希地址，则哈希地址为3的元素个数为（）。A.1B.2C.3D.4.若根据查找表建立长度为m的线性哈希表，采用线性探测再哈希法处理冲突，假定对一个元素第一次计算的哈希地址为d,则下一次的哈希地址为（）。A.dB.d+1C.（d+1）/mD.（d+1）%m.在采用线性探测再哈希法处理冲突的线性哈希表上，假定装填因子a的值为0.5,则查找任一个元素的平均查找长度为（）。A.1B.1.5C.2D.2.5.在哈希查找中，平均查找长度主要与（）有关。A.哈希表长度B.哈希元素个数C.装填因子 D.处理冲突方法.若对n个元素进行直接插入排序，则进行第i趟排序过程前，有序表中元素的个数为O。A.iB,i+1C,i-1D.1.若对n个元素进行直接插入排序，在进行第i趟排序时，为寻找插入位子最多需要进行（）次元素的比较，假定第0号元素放有待查的键值。A.iB,i-1C,i+1D.1.若对n个元素进行直接插入排序，在进行第i趟排序时，假定元素r[i+1]的插入位置为r[j],则需要移动元素的次数为（）。A.j-iB.i-j-1C.i-jD.i-j+1.若对n个元素进行直接插入排序，在进行任意一趟排序的过程中，为寻找插入位置而需要的时间复杂度为（）。A.O（1）B.O（n）C.O（n2）D.O（lbn）.在对n个元素进行直接插入排序的过程中，共需要进行（）趟。A.nB.n+1C.n-1D.2n.对n个元素进行直接插入排序的时间复杂度为（）。A.O（1）B.O（n）C.O（n2）D.O（lbn）.在对n个元素进行冒泡排序的过程中，第一趟排序至多进行（）对相邻元素之间的交换。A.nB.n-1C.n+1D.n/2.在对n个元素进行冒泡排序的过程中，最坏情况下的时间复杂度为（）。A.O（1）B.O（lbn） C.O（n2）D.O（n）.在对n个元素进行冒泡排序的过程中，至多需要（）趟完成。A.1B.nC.n-1D.n/2.在对n个元素进行快速排序的过程中，最好情况下需要进行（）趟。A.nB,n/2C.lbnD.2n.在对n个元素进行快速排序的过程中，最坏情况下需要进行（）趟。A.nB,n-1C.n/2D.lbn.对下列4个序列进行快速排序，各以第一个元素为基准进行第一次划分，则在该次划分过程中需要移动元素次数最多的序列为（）。A.1，3，5，7，9B,9，7，5，3，1C,5，3，1，7，9D,5，7，9，1，3.假定对元素序列（7,3,5,9,1，12,8,15）进行快速排序，则进行第一次划分后，得到的左区间中元素的个数为（）。A.2B.3C.4D.5.在对n个元素进行简单选择排序的过程中，在第i趟需要从（）个元素中选择出最小值元素。A,n-i+1B,n-iC,iD.i+1.若对n个元素进行简单选择排序，则进行任一趟排序的过程中，为寻找最小值元素所需要的时间复杂度为（）。A.O（1）B.O（lbn）C.O（n2）D.O（n）.假定一个初始堆为（1,5,3,9,12,7,15,10）,则进行第一趟堆排序后得到的结果为（）。A.3,5,7,9,12,10,15,1B.3,5,9,7,12,10,15,1C.3，7，5，9，12，10，15，1D.3，5，7，12，9，10，15，1.若一个元素序列基本有序，则选用（）方法较快。A.直接插入排序B.简单选择排序C.堆排序D.快速排序.若要从1000个元素中得到10个最小元素，最好采用（）方法。A.直接插入排序B.简单选择排序C.堆排序 D.快速排序.在平均情况下速度最快的排序方法为（）。A.简单选择排序B.冒泡排序C.堆排序 D.快速排序二、填空题.数据的逻辑结构可分为—和—两大类。.数据的存储结构被分为—,,和4种。.在下面的程序段中，s=s+p语句被执行次数为—，p*=j语句的执行次数为—，该程序的复杂度为inti=0,s=0；while(++i<=n){intp=1;for(intj=1;j<=i;j++)p*=j;s=s+p;）.一种数据结构的元素集合K和它的二元关系R为：K={a,b,c,d,e,f,g,h}R={<a,b>,<b,c>,<c,d>,<d,e>,<e,f>,<f,g>,<g,h>}则该数据结构具有—结构。.线性表的两种存储结构分别为—和—。.线性表的顺序存储结构称为—，链式存储结构称为—。.若经常需要对线性表进行插入和删除运算，则最好采用_存储结构，若经常需要对线性表进行查找运算，则最好采用—存储结构。.对于一个长度为n的顺序存储的线性表，在表头插入元素的时间复杂度为一。.对于一个单链表存储的线性表，在表头插入结点的时间复杂度为—，在表尾插入结点的时间复杂度为一。.在线性表的单链表存储中，若一个元素所在结点的地址为p，则其后的断结点的地址为.在以HL为头指针的带头结点的单链表和循环单链表中，链表为空的条件分别为—和.在—链表中，既可以通过设定一个头指针，也可以通过设定一个尾指针来确定它，即通过头指针或尾指针可以访问到该链表的每个结点。.在一个单链表中删除指针p所指向结点的后继结点时，需要把—的值赋给p->next指针域。.在一个单链表中指针p所指向结点的后面插入一个指针q所指向的节点时，首先把—的值赋给p->next，然后把 的值赋给p->next。.假定指向单链表中第一个结点的头指针为head，则像该单链表的表头插入指针p所指向的新结点时，首先执行—赋值操作，然后执行—赋值操作。.访问一个顺序表和一个单链表中第i个元素的时间复杂度分别为—和—。.在一个带头结点的循环单链表中，在表头插入或删除与在其它位置插入和删除，其操作过程是否相同？。.在双向链表中每个结点包含有两个指针域，一个指向其—结点，另一个指向其—结点。.在一个双向链表中指针p所指向的结点之后插入一个指针q所指向的结点时，需要对p->next->prior指针域赋值为。.在一个双向链表中删除指针p所指向的结点时，需要对p->next->prior指针域赋值为一。.栈又称为—表，队列又称为—表。.在一个用一维数组a[N]表示的顺序栈中，该栈所含元素的个数最少为一个，最多为—个。.像一个顺序栈插入一个元素时，首先使—后移一个位置，然后把新元素—到这个位子。.从一个栈删除元素时，首先取出—，然后再使—减一。.一个顺序栈存储一个一维数组a[M]中，栈顶指针用top表示，当栈顶指针等于—时为空栈，栈顶指针为一时为满栈。.假定一个链栈的栈顶指针为top，每个结点包含值域data和指针域next，当p所指向的结点入栈时，则首先执行—操作，然后执行—操作。.假定一个链栈的栈顶指针为top，每个结点包含值域data和指针域next，当进行出栈运算时(假定栈非空)，需要把栈顶指针修改为—的值。.设元素1，2,3,4,5依次进栈，若要在输出端得到序列34251，则应进行的操作序列为Push(s,1),Push(s,2),,Pop(s),Push(s,4),Pop(s),,,Pop(s),Pop(s)。.设元素a，b，c，d依次进栈，若要在输出端得到序列cbda，则应进行的操作序列为push(s,a),push(s,b),push(s,c),,，pop(s),pop(s)。.队列的插入操作在—进行，删除操作在—进行。.一个顺序循环队列存在于a[M]中,假定队首和队尾指针分别为front和rear，则判断对空的条件为—，判断对满的条件为—。.一个顺序循环队列存在于a[M]中,假定队首和队尾指针分别为front和rear，则求出队首和队尾指针的下一个位置的计算公式分别为 和。.在一个用一维数组a[N]存储的顺序循环队列中，该队列中的元素个数最少为一个，最多为个。.向一个顺序循环队列中插入元素时，需要首先移动―，然后再向它所指位置—新元素。.在一个空链队列中，假定队首和队尾指针分别为f和r，当向他插入一个新结点*p时，则首先执行—操作，然后执行—操作。.在一个带头结点的循环链队列中，假定队首和队尾指针分别为f和r，当向它插入一个新结点*p时，则首先执行—操作，然后执行—操作。.假定front和rear分别为一个链队列的对首和队尾指针，则该链队列中只有一个结点的条件为。.在一个链栈中，若栈顶指针等于NULL则为—；在一个链队列中，若对首和队尾的指针相同，则表示该队列为—或该队列—。.一个二维数组A[15,10]采用行优先方式存储，每个数据元素占用4个存储单元，以该数组第3列第0行的地址（即A[3,0]的地址）1000为首地址，则A[12,9]的地址为—。.在二维数组a[10,20]中，每个元素占8个存储单元，假定该数组的首地址为2000，则数组元素a[6,15]的字节地址为—。.有一个8X8的下三角矩阵A,若将其进行顺序存储于一维数组a[N]中，则N的值为。.有一个10X10的下三角矩阵A,若将其进行顺序存储于一维数组a[N]中，则Aij（1WiW10,1WjWi）存储于a中的下标位置为。.有一个8X8的下三角矩阵A,若将其进行顺序存储，每个元素占用4个字节，则A5,4元素的相对字节地址为（相对首元素地址而言）—。.一种数据结构的元素集合K和它的二元关系R为：K={a,b,c,d,e,f,g,h}R={<d,b>,<d,g>,<b,a>,<b,c>,<g,e>,<g,h>,<e,f>}则该数据结构具有结构。.对于一棵具有n个结点的树，则该树中所有结点的度数之和为—。.在一棵树中，—结点没有前驱结点，其余每个结点有并且只有一个—，可以有人以多个一结点。.如图1.3所示为一棵树，该树的叶子结点数为一个，单支结点数为一个，双分支结点数为一个，三分支结点数为一个。.如图1.3所示的一棵树，结点K的所有祖先的结点数为一个，结点B的所有子结点数为个。.如图1.3所示的一棵树，结点D和X的层数分别为—和—。.如图1.4所示的一棵树，则树中所含的结点数为一个，树的深度为—,树的度为―。.如图1.4所示的一棵树，则度为3,2,1,0的结点数分别为—,—,—。.如图1.4所示一棵树，则结点H的双亲为—，孩子结点为—。.在一棵二叉树中，假定双分支结点数为5个，单分支结点数为6个，则叶子结点数为—。.对于一棵二叉树，若一个结点的编号i,若它的左孩子结点存在，则其编号为—，若右孩子结点存在，则其编号为—，若双亲结点存在，则其编号为—。.在一棵二叉树中，第5层上的结点数最多为—。.假定一棵二叉树的结点数为18,则它的最小深度为—，最大深度为一。.如图1.5所示为一棵二叉树，则E结点的双亲结点数为—，左孩子结点为—，右孩子结点为一。.如图1.5所示为一棵二叉树，它含有双支结点一个，单分支结点一个，叶子结点―

个。.假定一棵二叉树顺序存储在一维数组a中，若a[5]元素的左孩子存在则对应的元素为—，若右孩子存在则对应的元素为—，双亲元素为—O.若对一棵二叉树从0开始进行结点编号，并按此编号把它存储到一维数组a中，即编号为0的结点存储到a[0]中，依次类推，则a[i]元素的左孩子为—，右孩子为—，双亲元素（i>0）为o.对于一棵具有n个结点的二叉树，对应二叉链表中指针总数为一个，其中一个用于指向孩子结点，一个指针空闲。.在一棵深度为h的完全平衡二叉树中，最少含有一个结点，最多含有一个结点。.一棵深度为5的完全二叉树中的结点数最少为一个，最多为一个。.如图1.6所示为一棵二叉树，对它进行先序遍历结果为—o.若将如图1.7所示为一棵树转换为二叉树，该二叉树中双支结点的个数为一个，单支结点的个数为一个，叶子结点个数为—O।—，叶子结点数为―O棵树。则该树的深度为—，带3,4,5,6}6)}.一棵树转换为二叉树后如图1.8所示，则原树中分支结点数为67.一个树林转换成二叉树后如图1.9所示，则该素林中包含—।—，叶子结点数为―O棵树。则该树的深度为—，带3,4,5,6}6)}.一种数据结构的元素集合K和它的二元关系R为：K=｛1，2,R=｛（1，2）（2，3）（2，4）（3，4）（3，5）（3，6）（4，5）（4,则该数据结构具有—数据结构。.在一个图中，所有顶点的度数之和等于所有边数的一倍。.在一个具有n个顶点的无向完全图中，包含有一条边，在一个具有n个顶点的有向完全图中，包含有一条边。.已知一个连通图的边集为｛（1,2）,（1,3）,（1,4）,（2,3）,（2,5）,（3,5）,（4,5）｝,则度为3的顶点的个数有一个。.假定一个有向图的顶点的集为｛a,b,c,d,e,f｝,边集｛<a,c>,<a,e>,<c,f>,<d,c>,<e,b>,<e,d>｝,则出度为0的顶点个数为—，入度为1的顶点个数为—。.在一个具有n个顶点的无向图中，要连通所有顶点则至少需要一条边。.表示图的两种存储结构为—和—。.在一个连通图中存在着一个连通分量。.若一个图的顶点集为｛a,b,c,d,e,f｝,边集为｛（a,b）,（a,c）,（b,c）,（d,e）｝,则该图含有—一个连通分量。.若一个图的边集为｛<0,1>,<0,2>,<0,3>,<0,4>,<1,2>,<2,4>,<3,4>｝,则从顶点V0到顶点V4共有一条简单路径。.如图1.10所示为一个带权有向图，从顶点V0到顶点V4的最短路径长度为—。.对于一个具有n个顶点的图，若采用邻接矩阵表示，则矩阵大小至少为—X—。.对于一个具有n个顶点和e条边的有向图和无向图，在其对应的邻接表中，所含边结点的个数分别为—和—。.在有向图的邻接表和逆邻接表表示中，每个顶点邻接表分别着该顶点的所有—和—。.有一个图的边集为｛（a,c）,（a,e）,（b,e）,（c,d）,（d,e）｝，从顶点a出发进行深度优先搜索遍历得到的顶点序列为.,从顶点a出发进行广度优先搜索遍历得到的顶点序列为索遍历得到的顶点序列为. O.一个图的边集为{(a,c),(a,e),(c,f),(d,c),(e,b),(e,d)},从顶点a出发出发进行深点序列为。度优先搜索遍历得到的顶点序列为.,从顶点度优先搜索遍历得到的顶点序列为.,从顶点a出发进行广度优先搜索遍历得到的顶.图的—优先搜索遍历算法是一种递归算法，图的—优先搜索遍历算法需要使用队列。.若一个连通图中每个边上的权值均不同，则得到的最小生成树是—(唯一/不唯一)。.以顺序查找方法从长度为n的顺序表或单链表中查找一个元素时，平均查找长度为―。.对长度为n的查找表进行查找时，假定查找第i个元素的概率为P,查找长度(即在查找过程中依次同有关元素比较的总次数)为C,则在查找成功的情况下的平均查找长度的计算公式为。.假定一个顺序表的长度为40,并假定查找每个元素的概率都相同，则在查找成功的情况下的平均查找长度—，则在查找不成功的情况下的平均查找长度—。.以折半查找方法从长度为n的有序表中查找一个元素时，平均查找长度约等于—减一。.以折半查找方法从长度为50的有序表中查找一个元素时，其查找长度不超过一。.从有序表(12,18,30,43,56,78,82,95)中分别折半查找43和56元素时，其查找长度分别为—和—。.假定对长度n=50的有序表进行折半查找，则对应的判定树深度为—，最后一层的结点数为—。.在分块查找中，假定查找表(即主表)的长度为96,被等分为8个子表，则进行分块查找的平均查找长度为一。.假定对长度为n的有序表进行分块查找，并假定每个子表的长度为，则进行分块查找的平均查找长度为—。.在一棵二叉树排序中，每个分支结点的左子树上所有结点的值一定—该结点的值，右子树上所有结点的值一定—该结点的值。.从一棵二叉排序树中查找某个元素时，若元素的值等于根结点的值，则表明—，若元素的值小于根结点的值，则继续向—查找，若元素的值大于根结点的值，则继续向—查找。.向一棵二叉排序树种插入一个元素时，若元素的值小于根结点的值，则接着向根结点的—插入，若元素的值大于根结点的值，则接着向根结点的—插入。.在一棵平衡二叉排序树中，每个结点的左子树深度与右子树深度之差的绝对值不超过一.假定对线性表(38,25,74,52,48),进行散列存储，采用H(K)=K%7作为哈希函数，采用线性探测再散列法处理冲突，则在建立哈希表过程中，将会碰到一次冲突。.假定对线性表(38,25,74,52,48)进行散列存储，采用H(K)=K%7作为哈希函数，采用线性探测再散列法处理冲突，则平均查找长度为—。.在线性表的散列存储中，装填因子a又称装填系数，若用m表示散列表的长度，n表示散列存储的元素个数，则a等于—。.对线性表(18,25,63,50,42,32,90)进行散列存储时，若选用H(K)=K%9作为哈希函数，则散列地址为0的元素有一个，则散列地址为5的元素有一个。.每次从无序子表中取出一个元素，把它插入到有序子表的适当位置，此种排序方法叫做—排序；每次从无序子表中挑选出一个最小或最大元素，把它交换到有序表的一段，此种排序方法叫做—排序。.若对一组记录(46,79,56,38,40,80,35,50,74)进行直接插入排序，当把第8个记录插入到前面已排序的有序表时，为寻找插入位置需比较一次。.—排序方法能够每次使无序表中的第一个记录插入到有序表中。.对n个记录进行冒泡排序时，最少的比较次数为—，最少的趟数为—。.假定一组记录为(46,79,56,38,40,84),在冒泡排序过程中进行第一趟排序后的结果为—。.假定一组记录为(46,79,56,64,38,40,84,43),在冒泡排序过程中进行第一趟排序时，元素97将最终下沉到其后第一位置。.—排序方法使键值达的记录逐渐下沉，使键值小的记录逐渐上浮。.假定一组记录为(46,79,56,38,40,80)对其进行快速排序的过程中，共需要—趟。.假定一组记录为(46,79,56,25,76,38,40,80)对其进行快速排序的第一次划分后，右区间元素个数为—。.假定一组记录为(46,79,56,38,40,80),对其进行快速排序的第一次划分后的结果为。.在所有排序方法中，―排序方法采用的是折半查找法的思想。.在简单选择排序中，记录比较次数的时间复杂度为—，记录移动次数的时间复杂度为 O.若对一组记录(46,79,56,38,40,80,35,50,74)进行简单选择排序，用k表示最小值元素的下标，进行第一趟是可得初值为1,则在第一趟选择最小值的过程中，k的值被修改次。.在时间复杂度为O(n2)的所有排序方法中，—排序方法使不稳定的。.假定一个堆为(38,40,56,79,46,84),则利用堆排序方法进行第一趟交换和对根结点筛运算后得到的结果为—O.在所有排序方法中，—方法使数据的组织采用的是完全二叉树的结构。.―排序方法能够每次从无序表中查找出一个最小值。三、名词解释1.数据2.数据元素3.数据对象4.数据结构5.逻辑结构6.时间复杂度7.空间复杂度8.栈9.队列10.压缩存储11.树形结构12.结点的度13.树的度14.树的深度15.有序树16.遍历17.哈夫曼树18.邻接关系19.路径20.连通图21.强连通图22.完全无向图23.完全有向图24.主关键字四、简答题.简述线性结构，树形结构，网状结构的不同。.简述算法复杂度的评价方法。.设有两个算法在同一台机器上运行，其执行时间分别为100n2和2n,要使前者快于后者，n至少为多大？.在顺序表中插入和删除一个结点需平均移动多少个结点，具体移动的次数取决于哪些因素？.简述定义：线性表、单链表、线性表的存储方式、循环链表、双向链表。.在单链表，双向链表和单循环链表中，若仅知道指针p指向某结点，不知道头指针，能否将p从相应的链表中删去？若可以，其时间复杂度分别为多少？.有哪些链表可仅有一个尾指针来唯一确定，即从尾指针出发能访问到链表上任何一个结点？.何时选用顺序表，何时选用链表作为线性表的存储结构？.简述栈与队列的不同之处。.设将整数1,2,3,4依次进栈，但只要出栈时栈非空，则可将出栈操作按任何次序压入其中，请回答下述问题：若入、出栈次序为Push(1),Pop(),Push(2),Push(3),Pop(),Pop(),Push(4),Pop(，则出栈的数字序歹U如何？能否得到出栈序列1423和1432,并说明为什么不能得到或者如何得到。请分析1,2,3,4的各种排列中，哪些序列是可以通过相应的人出栈操作得到的。.举例说明栈的“上溢”和“下溢”现象。.循环队列的优点是什么？如何判别它的空和满？.假定用一维数组a[7]顺序存储一个循环队列，队首和队尾指针分别用front和rear表示，当前队列中有5个元素：23,45,67,80,34,其中23为队首元素，front的值为3,请画出对应的存储状态，当连续进行4次出队运算后，再让15,36,48元素依次进队，请再次画出对应的存储状态。.空串和空格串有何区别？字符串中空格符有何意义？空串在串的处理中有何作用？.两个字符串相等的充要条件是什么？.二叉树和树之间有何区别？一棵度为2的树与二叉树有何区别？.在一棵二叉树如图1.11所示。写出对此树进行先序，中序，后序遍历时得到的结点序列。.已知一棵二叉树的中序遍历序列为CDBAEGF先序遍历序列为ABCDEFG试问能不能唯一确定一棵二叉树？若能，画出该二叉树。若给定先序遍历序列和后序遍历序列，能否唯一确定？.将图1.12所示的树转换成二叉树。.一棵度为2的有序树与一棵二叉树有何区别？.试分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。.高度为h的完全二叉树至少有多少个结点？至多有多少个结点？.试采用顺序存储方法和链式存储方法分别画出如图1.13所示各二叉树的存储结构。.假定用于通信的电文由8个字母组成，分别是A,B,C,D,E,F,G,和H,各字母在电文中出现的概率为：5%,25%,4%,7%,9%,12%,30%,8%,试为8个字母设计哈夫曼编码。.根据如图1.14所示的带权有向图G,试回答下面问题：(1)给出从结点V1出发按深度优先搜索遍历G所得的结点序列，并给出按广度优先搜索遍历G所得的结点序列。(2)给出从结点V1到结点V8的最短路径。.对于如图1.15所示的有向图，请给出(1)对应的邻接矩阵，并给出A,B,C三个顶点的出度与入度。(2)邻接表表示和逆邻接表表示。(3)强连通分量。27.假设组的顶点是A,B,C,D,…请根据下述邻接矩阵画出相应的有向图和无向图。(1)0111 (2)01100101100010110110001111001010.对n个顶点的无向图和有向图，采用邻接矩阵和邻接表表示时，如何判别下列有关问题:(1)图中有多少条边？(2)任意两个顶点i和j是否有边相连？(3)任意一个顶点的度是多少？.试述顺序查找法，折半查找法和分块查找法对查找表中元素的要求。.若有一个长度为n的表，其查找该表中每个元素的概率相同，采用顺序查找、折半查找和分块查找3种查找方法进行查找时的其平均查找长度各为多少？.设有一组关键字(17，13，14，153，29，35)需插入到表长为12的散列表中，请回答下列问题：(1)设计一个适合该散列表的哈希函数。(2)用设计的哈希函数将上述关键字插入到散列表中，画出其结构，并指出用线性探测再散列法解决冲突时构造散列表的装填因子为多少？.选择排序算法是否稳定？为什么？.给出一组关键字(19，01，26，92，87，11，43，87，21)，进行冒泡排序，列出每一遍排序后关键字的排列次序，并统计每遍排序进行的关键字比较次数。.直接插入排序算法是否稳定？为什么？.堆排序为什么是不稳定的排序？试举例说明。五、应用题.指出下列每个算法的功能并求出其时间复杂性。(1)intsum1(intn){intp=1,s=0;for(inti=1；i<=n;i++){p*=i;s+=p；)returns;)2)voidmtable(intn){for(inti=1；i<=n;i++)for(intj=i；j<=n;j++)printf(“i*j=%d”，i*j)；printf(“\n");)(3)voidcmatrix(inta[M][N],intd)/*M和N为全局整型常量*/{for(inti=0；i<M;i++)for(intj=0；j<N;j++)a[i][j]*=d;).voidAA(sqlist&L)/*L为一个顺序表*/{initiate_sqlist(L);/*初始化顺序表L*/end_insert(L,30);/^Em十个元素插入到表尾*/begin_insert(L，50)/*把五十个元素插入到表头*/inta[4]={5,8,12,15};inti;for(i=0;i<=4;i++)end_insert(L,a[i]);/*依次把每个元素插入到表尾*/for(i=0;i<=4;i++)begin_insert(L,a[i]);/*依次把每个元素插入到表头*/)该算法被调用执行后，得到的顺序表L为：―。.viodAC(lklist&HL)/*HL为一个单链表*/{initiate_lklist(HL)；/*初始化单链表HL*/insert_lklist(HL,30,1);/*向单链表第一个位置插入元素30*/insert_lklist(HL,50,2);/*向单链表第二个位置插入元素50*/inta[5]={15，8，9，26，12}；for(inti=0；i<5;i++)begin_insert(HL,a[i]);/*向HL的表头依次插入数组a中的前五个元素值*/intx=delete_lklist(HL，3)；/*此函数删除HL中的第三个结点并返回该结点的值*/end_lklist(HL，x)；/*向HL的表尾插入x*/}该算法被调用执行后，得到的HL单链表所对应的线性表为：。.分别编写在顺序表和带头结点的单链表上统计出值为x的元素个数的算法，统计结果由函数值返回。.分别编写在顺序表和带头结点的单链表上删除其值等于x的所有元素。.分别编写在顺序表和单链表上删除具有重复值的多余结点，使每个结点的值均不同。如将线性表(2，8，9，2，5，5，6，8，7，2)变为(2，8，9，5，7)。.有6个元素A，B，C，D，E，F依次入栈，允许任何时候出栈，能否得到下列的各个出栈序列，若能，给出出栈操作的过程，若不能，简述其理由。(1)CDBEFA(2)ABEDFC(3)DCEABF(4)BAEFCD.设计一个递归算法，计算出返回1至n之间的所有整数平方和。.斐波那契(Fibonacci)数列的定义为：它的第一项和第二项均为1，以后各项为前两项之和。若斐波那契数列中第n项用Fib(n)表示，则计算公式为：试编写出计算Fib(n)的递归算法和非递归算法。.假定在一个链式队列中只设置队尾指针，不设置队首指针，并且让队尾结点的指针域指向队首结点(称此为循环队列)，试分别写出在循环队列上进行插入和删除操作的算法。.设以二叉链表为二叉树的存储结构，结点的结构如下：其中data为整数，试设计一个算法voidchange(bitreptrr),若结点左孩子data的值大于右孩子的data域的值，则交换其左右子树。.设计一个算法，统计出二叉树中等于给定值x的结点个数，该统计值由变量k带回(k的初值为0)。Voidcountl(bitreptrr，datatypex,int&k).设计一个算法，从一棵二叉树查找出所有结点的最大值并返回。Datatypemaximum(bitreptrr).假设用于通信的电文有8个字母组成，字母在电文中出现的频率分别为：7,19,2,6，32,3,21，10。试为这8个字母设计哈夫曼编码。.已知一个无向图的邻接矩阵如图1.16所示，试写出从顶点V0出发分别进行深度优先和广度优先搜索遍历得到的顶点序列。

深度优先搜索序列:—。广度优先搜索序列：—。.已知一个无向图的邻接表如图1.17所示，试写出从顶点V0出发分别进行深度优先和广度优先搜索遍历得到的顶点序列。深度优先搜索序列:—。广度优先搜索序列：—。.已知一个带权有向图如1.18所示，用迪杰斯特拉提出的算法求其任一对结点之间的最短路径。.构造如图1.19所示加权图的最小生成树(给出利用克鲁斯卡尔算法构造的过程)。.对长度为11有序集，进行折半查找，试画出它的一棵判定树，并求在等概率情况下的平均查找长度。.已知一个顺序存储的有序表为(15,26,34,39,45,56,58,63,74,6),试画出对应的二分查找判定树，求出其平均查找长度。.假定一个线性表为(38,52,25,74,68,16,30,54,90,72)画出按线性表中元素的次序生成的一棵二叉排序树，求出其平均查找长度。.假定一个待散列存储的线性表为(32,75,29,63,48,94,25,36,18,70,49,80),散列地址空间为HT[11],若采用除留余数法构造散列函数和法处理冲突，试画出最后得到的链式哈希函数列表，并求出平均查找长度。.已知一组记录为(46,74,53,14,26,38,86,65,27,34)。(1)给出采用直接插入排序法进行排序时每一趟的排序结果。(2)给出采用冒泡排序法进行排序时每一趟的排序结果。(3)给出采用快速排序法进行排序时每一趟的排序结果。(4)给出采用直接选择排序法进行排序时每一趟的排序结果。(5)给出采用堆排序法进行排序时每一趟的排序结果。24.编写一个对整型数组A[n+1]中的A[1]至A[n]元素进行选择排序的算法，使得首先从待排序区间中选择出一个最小值并同第一个元素交换，再从待排序区间中选择一个最大值并同最后一个元素进行交换，反复进行直到最后待排序区间中元素个数不超过1为止。参考答案一选择题1.D2.C3.A 4.B 5.A 6.C 7.C8.D 9.B10.B11.A12.C13.B14.A15.C16.D17.B18.B19.C20.B21.D22.C23.B24.A25.A26.A27.B28.A29.C30.B31.C32.D33.C34.D35.A36.B37.B38.D39.B40.A41.C42.D43.A44.D45.B46.B47.D48.B49.C50.C51.C52.B53.A54.C55.C56.D57.C58.A59.A60.C61.D62.B63.C64.A65.B66.D67.A68.A69.D70.D71.C72.B73.B74.A75.C76.D77.C78.D79.B80.C81.A82.A83.B84.D85.A86.C87.B88.D89.B90.C91.B92.C93.D94.A95.D96.B97.C98.B99.D100.B101.C102.A103.C104.D105.B106.C107.C108.B109.D110.A111.C112.B113.D114.B115.A116.D117.A118.A119.B120.D二填空题1.线形；非线形2.顺序；链式；索引；散列存储结构3.n；n(n+1)/2；O(n) 4.线性5.顺序；链式 6.顺序表；链式表7链式;顺序 8.O(n)；O(1)9.O(1)；O(n) 10.p->next11.HL->next==NULL;HL->next==HL12,循环13.p->next->next15.p->next=head;head=p13.p->next->next15.p->next=head;head=p17.相同19.q21.先进后出；先进先出23.栈顶指针；插入(写入)25.-1；M-127.top->next29.Pop(s);Pop(s);Push(s,d)31.front=rear;(r+1)%M==front33.0;N-135.p->next=NULL;r=f=p16.O(1);O(n)18.前趋；后续p->prior22.0;1栈顶元素；栈顶指针p->next=top;top=p28.Push(s,3);Pop(s);Push(s,5)30.队尾；队首32.(front+1)%M;(r+1)%M34.队尾指针；插入(写入)36.p->next=r->next;r=r->next=p37.(front=rear)&&(front!=NULL)或者(front=rear)&&(rear!=NULL)38.空栈；空；只含有一个结点40.308043.5240.308043.5245.n-147.7；1；4；149.3；451.2；1；1；653.641.3642.i(i-1)/2+j-144.树型或层次46,根；前趋(父)后续(子)48.2；650.10；4；352.B;I和J54.2i；2i+1；i/255.1656.5；857.A；F；空58.2；2；359.a[10];a[11];a[2]60.a[2i+1];a[2i+2];a[(i-1)/2]61.2n,n-1,n+162.2h-1;2h-163.16;3164.ABCDEF;CBAEDF;CBEFDA65.2;4;366.4;567.368.4;8769.图状70.271.n(n-1)/2;n(n-1)72.473.2;474.n-1.邻接矩阵；邻接表76.177.378.479.7.n;n.e;2e.出边；入边.acdeb;acedb(答案不唯一).acfebd;acefbd(答案不唯一).深度；广度.唯一.(n+1)/2.89.20.5;4190.1b(n+1)91.692.1;393.6;1994.11..小于；大于.查找成功；左子树；右子树.左子树；右子树99.1100.5101.2102.n/m103.3;2.插入；选择105.4.直接插入107.n-1;1108.(46,56,38,40,79,84)109.4.冒泡.3112.4.[4038]46[567980].快速115.O(n2);O(n)116.2.快速.（40,46,56,79,84,38）.堆排序.简单排序三名词解释数据是指反映客观事物的信息的集合，它是数据结构所要描述的东西。.数据元素是数据的一个个体，它是数据的基本单位。数据对象是指在数据这个集体中人们感兴趣的一个子集，通常，数据对象中的元素具有某些相同的特性。数据结构是指相互之间有关联的数据元素的集合。逻辑结构是指数据之间的逻辑关系。算发在计算机执行时在时间资源方面消耗的多少。算发在计算机执行时在空间资源方面消耗的多少。栈是被限定为仅能在表尾进行插入和删除运算的线性表。列对是一种只允许在表的一端进行插入，而在另一端进行删除的受限的线性表。压缩存储是指给多个值相同的元素只分配一个空间，对零元素不分配空间。树型结构是一类很重要的非线性数据结构，在这类结构中，元素结点之间存在明显的分支和层次关系。一个结点的子树的个数称为该结点的度。树的所有结点中最大的度称为树的度。树的深度是指树的所有结点中最大的层次，又称树的高度。有序树是指如果一棵树所有结点的子结点的左右顺序不可颠倒的树。遍历是指循某条线路，依次访问某数据结构中的全部结点，而且每个结点只被访问一次。哈夫曼树是指以文本中出现的字符为叶子结点的最优二叉树，其中叶子结点的全值为该字符在文本中出现的几率。邻接关系是指在无向图中若存在边（Vi,Vj）,则称结点Vi邻接于Vj或结点Vj邻接于Vi；在有向图中若存在边（Vi,Vj）,则称结点Vj邻接于结点Vi。路径是连接两个结点的边的集合。如果无向图中的任意两个结点都是通的，则称无向图是连通图。在有向图中，任意一对结点Vi和Vj之间都存在路径，则称有向图为强连通图。若一个有向图中每一对结点之间都存在一条边，则称无向图为完全无向图。若一个有向图中每一对结点之间都存在两条不同的边，则称有向图为完全有向图。主关键字是指能用来唯一标识该记录的数据项。四简答题线性结构是指数据元素之间存在一对一的关系。树型结构是指元素之间存在一对多的关系。图或网状结构是指数据元素之间存在多对多的关系。算法的复杂度分析可分为时间复杂度和空间复杂度。时间复杂度以基本操作重复执行的次数为算法的时间量度。空间复杂度指算发所存储空间的量度。.要使100n2快于2n时，必须满足100n2（2n,可以算出n的值为15时,2n恰好大于100n2,所以至少应该是15..插入一个结点要平均移动n/2结点；删除一个结点要平均移动(n-1)/2结点；具体的移动次数取决于n的大小和插入或删除的位置这两个因素。.线性表是指由n(n>=0)个数据元素｛a0,a1.a2….an-2,an-1｝组成的有限序列。该序列要么为空或仅有一个元素，要么除了第一个元素没有前趋以及最后一个元素没有后续之外，其他元素都有且仅有一个前趋，也有且仅有一个后续。线性表可以表示为：｛aill属于[0，n-1]｝单链表是指必须是有一个称为表头的指针向连接，N个结点形成一个链，且每个结点只有一个指针域的线性表。线性表的存储方式是指线性表的存储方式分为线性存储和链式存储两种，其中顺序存储是指线性表的顺序存储，链式存储是指线性表中的每一个结点其物理位置可连续，也可不连续，但是各结点间通过指针相连。循环链表是指把单链表的末尾结点种的指针域指向头结点，形成环型的链表。双向链表是指必须具有一个头指针，每个结点有两个指针域，一个指向该结点的前趋，一个指向该结点的后继的线性表。.在单链表中不能删除，而在双链表和单循环莲表中可以删除p结点。双向链表的删除p结点的时间复杂度为0(1),单循链表删除p结点的时间复杂度为O(1)。.在循环链表中可以由尾指针表示。.因为在顺序表中插入或删除时，需要移动大量的数据，所以在需要提高查找效率，而较少插入或删除的情况下，可以采用顺序储存；链式存储结构便于插入和删除。但是不便于查找结点。所以对于需要经常修改线性表结点位置的情况下，采用链式存储为宜。.栈，队列都是一种线性结构，只是他们的运算规则不同。栈是遵循先进后出的运算规则，堆栈的操只能在栈的一端(栈顶)进行；队列则遵循先进先出的运算规则，队的操作只能在队列的队首删除，队尾插入。.(1)1234。(2)能得到1432,不能得到1423。因为同时压入2,3,在弹出时根据堆栈的运算规则只能弹出3,2。(3)在1,2,3,4的各种排列中，根据堆栈的运算规则(先进后出)可能出现的次序是1234,1324,1432,2143,2134,3214,4321。.例如，在空间限定的情况下火车站的一条铁轨上已经停满了火车以后，火车已无法再进站，这属于上溢；调度在车辆派空以后，到时间没有车派了，这属于下溢。.循环队列的储存，可以解决假溢出的问题。空的条件是队首追上队尾，既front；满的条件是队尾追上队首，既rear+1=front。.两次对应的储存状态分别为：.不含任何字符的串称为空串，其串长度为零；仅含有空格字符的串称作空格，其长度为串中空格符的个数。空格符在字符串中可用来分隔一般的字符，便于阅读和识别，空格符会占用串长。空串在处理过程中可用于作为任意字符串的子串。.两个字符串相等的充要条件是：两个串的长度相等，且对应位置的字符相等。.二叉树与树的区别：(1)二叉树的结点至多有两个子树，数则不然；(2)二叉树的一个结点的子树有左，右之分，而树则没有此要求。度为2的树有两个分支，没有左，右之分，一颗二叉树边也可有两个分支。但左右之分。且左右不能交换。.先序遍历序列：ABDEFC中序遍历序列：DEFBAC

后序遍历序列：FEDBCA.(1)由中序遍历序列和先序遍历序列，或中序遍历序列和后序遍历序列，可以唯一确定一颗二叉树。由先序序列知，根结点最先被访问，就可确定根结点为A,而又由中序序列得知一棵树的根结点是其左，右子树的分隔点，从而可确定以A为根的左子树的结点为B,C,D,右子树的结点为E,F,G。重复进行就可得到二叉树。(2)由先序遍历序列和后序遍历序列不能唯一确定一棵二叉树。因为两种遍历方法只能确定根结点，而分不清左右子树。.二叉树如图1.20所示..度为2的有序树是指子树从左向右是有次序的，每个结点最多有两个分支，二叉树的最大度也是2,并且子树有左右之分。从表面上看好像没有什么不同，但是当只有一个子树时，度为2的有序树没有左右之分，而二叉树必须有左右之分，这就是度为2的有序树和二叉树的主要区别。.假设结点为A,B,C,3个结点的树的状态如图1.21所示.3个结点的二叉树的状态如图1.22所示..最少应为2h-1+1个结点，最多为2h-1个结点。.顺序存储如图1.23所示.链式存储如图1.24所示..答：假设8个字母所对应的权值为{5,25,4,7,9,12,30,8},并且n=8。根据哈夫曼的构造方法。将8个结点构成哈夫曼树，按照左0右1的原则，可以得到字母的豪夫曼编码为：A.1001 B.11 C.1000 D.0000E.101 F.001 G.01 H.0001.(1)深度优先遍历：V1,V2,V3,V8,V5,V7,V4,V6广度优先遍历：V1,V2,V4,V6,V3,V5,V7,V8(2)最短路径为：(V1,V2,,V5,V7,V8)26.26.(1)邻接矩阵为：A 0 0 0B 1 0 1C 0 0 0D 0 0 0E 1 1 0F 0 1 0(2)邻接表为如图1.25所示。ADB1 0 0 A的入度为2,出度为10 0 0 B的入度为2,出度为21 1 1 C的入度为1,出度为3000100010ACCDEFDEABDFBE逆邻接表按边的方向反之即可。(3)强连通分量如图1.26所示。图1.26(1)的无向图如图1.27(a)所示；(2)的有向图如图1.27(b)所示。(b)图1.27(1)采用邻接矩阵表示时，无向图的总边数为所有数值之和除以2；有向图的总边数为各行数值之和。采用邻接表表示时，无向图的边数为部顶点个数除以2；有向图的边数为部顶点个数。(2)对于无向图是以图中i行和j列的交叉点的值是否为1；对于有向图是以图中i行j列交叉点或i列j行交叉点的值是否为1来判断顶点i和j是否有边相连。(3)无向图顶点的度为每一行的数值之和；有向图顶点度为该行和该列数值之和。顺序查找：表中元素可以任意存放。折半查找：表中元素必须以关键字的大小按递增或递减的次序存放。分块查找：表中元素每块的元素可以任意存放，但是块与块之间必须以关键字的大小按递增或递减的次序存放。顺序查找：查找成功时的平均查找长度为：ASL=(n+1)/2折半查找：查找成功时的平均查找长度为：ASL=lg(n+1)-1分块查找：查找成功时的平均查找长度的大小与其确定所在块所采用的查找方法有关。若用顺序查找法确定所在块，则平均查找长度为(n/s+s)/2+1；若用折半查找法确定所在的块，平均查找长度为lg(n/s+1)+s/2,其中s为每块含有的元素个数。(1)由于散列表的长度为12,则可选不超过表长的最大素数11作为除留余数法的模，则可得其哈希函数为H(k)=k%11。(2)若用线性探测再散列法解决冲突，则可构造出散列表如131435172915301234567891011此时，其装填因子为6/12=1/2,若用链式法解决冲突，则其散列表如图1.28所示。.此种排序算法是不稳定的。由于选择排序算法的原则是从记录中找到最小(或最大)者并与第一个记录交换，一旦被换到某个位置以后再也不动了，此种方法不能保证具有相同排序码的记录原来所具有的相对次序，即原来排在前面的经排序后有可能排在具有相同排序码记录的后面，所以此种排序算法是不稳定的。.初始关键字序列为：(19,01,26,92,87,11,43,87,21)第一遍排序比较8次，交换6次后成为：(01,19,26,87,11,43,87,21,92)第二遍排序比较7次，交换3次后成为：(01,19,26,11,43,87,21,87,92)第三遍排序比较6次，交换2次后成为：(01,19,11,26,43,21,87,87,92)第四遍排序比较5次，交换2次后成为：(01,1