数据结构(第二版)模拟测试题4套及答案

试卷B一、选择题（本题共20分,每题2分）1．在数据结构中，从逻辑上可以把数据结构分成（）。A．动态结构和静态结构B.线性结构和非线性结构C.紧凑结构和非紧凑结构D.内部结构和外部结构2.下列程序段的时间复杂度是（）count=0;for(k=1;k<=n;k*=2)for(j=1;j<=n;j++)count++;A.O(nlog2n)B.O(n)C.O(log2n)D.O(n2)3.以下描述错误的是：（） A.线性表是n个数据元素的有限非空集合。 B.栈和队列都是操作受限的线性表。 C.串（或字符串）是由零个或多个字符组成的有限序列。 D.非空栈中的栈顶指针top始终指向栈顶元素的下一个位置。4.若采用少用一个队列空间的方法来区分队满队空两种状态，则判定一个顺序循环队列Q（最大队列长度MAXSIZE）为满队列的条件是()。A.Q.front=Q.rearB.Q.front!=Q.rearC.Q.front=(Q.rear+1)%MAXSIZED.Q.front!=(Q.rear+1)%MAXSIZE5.按照二叉树的定义，具有3个结点的二叉树有（）种。A.3B.4C.5D.66.设矩阵A（如下图所示）是一个对称矩阵，为了节省存储，将其下三角（包括对角线）部分按行序存放在一维数组B[n(n+1)/2]中，对下三角部分中任一元素ai,j(i≥j)，在一维数组B的下标位置k的值是（）。A.i(i-1)/2+j-1B.i(i-1)/2+jC.i(i+1)/2+j-1D.i(i+1)/2+j7.有一个有序表为｛5,18，23,33,42,54,56,78｝，当折半查找56时，经过（）次比较后查找成功。A.1B.2C.3D.88.一组记录的排序关键字为（39，19，36，68，35，84），则利用快速排序方法进行正序排列时，以第一个记录为基准得到的一次划分结果为（）。A.35，36，19，39，68，84B.19，35，36，39，68，84C.35，19，36，39，84，68D.35，19，36，39，68，849.若对下图a中的二叉树进行先序线索化，则结点x的左、右线索指向的结点分别是（）A.e,cB.e,aC.d,cD.b,abdbdxeac(a)(b)10.已知一有向图的邻接表存储结构如上图b所示，根据有向图的广度优先遍历算法，从顶点v1出发，所得到的顶点序列是（）。A.v1，v2，v3，v5，v4B.v1，v3，v2，v4，v5C.v1，v3，v4，v5，v2D.v1，v4，v3，v5，v2二、填空题（本题共20分，每题2分）1.设无向图G中顶点数为n，则图G最多有_____条边2.在一个长度为n（n≥1）的顺序表中的第i个元素（1≤i≤n）之前插入一个元素时，需向后移动_____个元素。3.在一个双向链表中，要删除p所指结点，应执行的操作序列为_____。4.有一棵树如右图所示，回答下面问题：树的度：_____；树的深度：_____；结点C的孩子结点：_____；结点F的祖先结点：_____。5.一棵完全二叉树的第5层有5个结点，则这棵完全二叉树共有_____个结点。01010101010101010101010111010001100ABCDE7.在一棵平衡二叉树中，每个结点的左子树深度与右子树深度之差可以是。8．若一组记录的关键字序列为（50，40，95，20，15，70，60，45，80），要对其按关键字从小到大进行堆排序时，则创建的初始堆序列为_____________________。9.对n个不同的关键字从小到大进行冒泡排序，最好情况下，需要经过比较____________次将其排好；最坏情况下，需要经过比较____________次排好。10.已知一个有向图的边集为{<a,b>,<a,c>,<b,d>,<b,e>,<c,b><d,e>}，则由该图产生的一种可能的拓扑序列为______________________。三、应用题（本题共40分，1-4每小题5分，5-6题每小题10分）1.利用普里姆算法，对于下面所示的连通图，从结点a出发，构造最小生成树。2.设给定权集w={2，4，3，7，8，9}，试构造关于w的一棵Huffman树，并计算所构造Huffman树的带权路径长度WPL。3.已知一棵二叉树的中序序列为CBEDAHGIJF，后序序列为CEDBHJIGFA，画出该二叉树。4.设数据集合D={24，13，53，37，90，48}，依次取D中各数据，构造一棵平衡二叉树，画出构造过程（说明平衡旋转的类型）及结果。5.假设有一组关键字{32，01，23，14，55，20，84，27，68}，要求：（1）散列函数为H(key)=key%13，计算这组关键字的散列地址并填入下表：Key320123145520842768H（key）冲突次数（2）采用线性探测法解决冲突，在0-12的散列地址空间中对该关键字序列构造散列表，将各关键字填入下表：地址0123456789101112关键字（3）计算成功查找时的平均查找长度ASLS，要求写出计算过程和结果：ASLS=6.下图是一个有7个顶点的网图，边上的权值为相邻两顶点的距离。使用Dijkstra算法，计算顶点a到所有其余顶点的最短路径。计算过程和结果填入下表，要求：(1)从第1步至第6步，每步选择的顶点填入表格倒数第二行；（4分）(2)表格中D值在填写时，请注意存储两部分信息：顶点a至其余顶点的“当前最短距离”，以及相应的路径顶点信息。将每一步的计算过程填入相应的位置。（6分）终点从a到各个终点的D值和最短路径的求解过程步骤1步骤2步骤3步骤4步骤5步骤6b距离值顶点序列c距离值顶点序列d距离值顶点序列e距离值顶点序列f距离值顶点序列g距离值顶点序列筛选顶点终点集S四、算法设计题（本题共20分）1.编写算法，实现将值为e的元素插入到单链表L的第i个结点的位置上。(本题10分)单链表结构定义如下：typedefstructLNode{ElemTypedata;StructLnode*next;}Lnode,*LinkList;2.试写一个判别给定二叉树是否为二叉排序树的算法，设此二叉树以二叉链表作为存储结构，且树中结点的关键字均不同。（本题10分）参考答案一、选择题答案（本题共20分，每小题2分）1.B2.A3.A4.C5.C6.D7.C8.D9.A10.B二、填空题答案（本体共20分，每小题2分）n(n-1)/2。n-i+1。p->prior->next=p->next;p->next->prior=p->prior;free(p);3_;4，G;A,B20连通图;20,1,-115,20,60,45,40,70,95,50,80(小顶堆)/95,80,70,45,15,50,60,40,20（大顶堆）n-1;n(n-1)/2a,c,b,d,e三、应用题答案要点（本题共40分，1-4每小题5分，5-6题每小题10分）1.最小生成树2.解：哈夫曼树如图其带权路径长度WPL=7×2+8×2+4×3+2×4+3×4+9×2=803.二叉树的结构为：4.平衡二叉树的构造过程及结果：RL24375390RL2437539048131324539037485.（1）关键字的散列地址并填入下表：（4分）key320123145520842768H(Key)6110137613冲突次数000100232（2）采用线性探测法解决冲突，在0-12的散列地址空间列构造散列表，（3分）地址0123456789101112关键字011455276832208423（3）计算成功查找时的平均查找长度ASLS，要求写出计算过程和结果：（3分）ASLS=(1×5+2×1+3×2+4×1)/9=17/96.最短路径：（10分）终点从a到各个终点的D值和最短路径的求解过程步骤1步骤2步骤3步骤4步骤5步骤6b距离值151515151515顶点序列（a,b）（a,b）（a,b）（a,b）（a,b）（a,b）c距离值2顶点序列(a,c)d距离值12121111顶点序列(a,d)(a,d)(a,c,f,d)(a,c,f,d)e距离值1010顶点序列(a,c,e)(a,c,e)f距离值6顶点序列(a,c,f)g距离值161614顶点序列(a,c,f,g)(a,c,f,g)(a,c,f,d,g)筛选顶点cfedgb终点集S{a,c}{a,c,f}{a,c,f,e}{a,c,f,e,d}{a,c,f,e,d,g}{a,c,fe,d,g,b算法设计题（只列出答案要点，可以有不同的答案，酌情给分）1、参考代码如下：（10分）statusListInsert(LinkList&L,inti,ElemTypee){//在带头结点的单链表L中第i个位置插入值为e的新结点p=L;j=0;while(p&&j<i-1){p=p->next;++j;}if(!p||j>i-1)returnERROR;s=(LinkList)malloc(sizeof(LNode));s->data=e;p->next=s;s->next=p->next;}2.主要代码如下：（10分）算法思路：对二叉排序树来说，其中序遍历序列为一个递增有序序列，因此，对给定的二叉树进行中序遍历，如果始终能保持前一个值比后一个值小，则说明该二叉树是一棵二叉排序树。中序遍历整棵二叉树，访问根结点时将根结点信息存入一个数组中，以用来比较中序遍历后序列是否为空。比较数组元素时，从下标为0的数组元素开始比较，先将下标为i=0的a[i]与下标为1的a[i+1]比较，如果a[i]>a[i+1]，则结束比较，即该二叉树不是二叉排序树，否则继续比较，直至比较完整个数组元素。int

IsSearchTree(struct

Bitree

*root){

if(!root)

{

return

1;

}

else

if(!(root->lChild)

&&

!(root->rChild))

//左,右子树都没有

{return

1;

}

else

if((root->lChild)

&&

!(root->rChild))

//只有左子树

{

if(root->lChild->data

>

root->data)

{

return

0;

//

0:不是二叉排序树}

else

{

return

IsSearchTree(root->lChild);

}

}

else

if((root->rChild)

&&

!(root->lChild))

//只有右子树

{if(root->rChild->data

<

root->data)

{return

0;

//

0:不是二叉排序树

}

else

{

return

IsSearchTree(root->rChild);

}

}

else

//左,右子树都有

{

if((root->lChild->data

>

root->data)

||

(root->rChild->data

<

root->data))

{

return

0;

//

0:不是二叉排序树

}

else

{

return

(

IsSearchTree(root->lChild)

&&

IsSearchTree(root->rChild)

);

}

}}试卷一一、选择题（本题共30分,每题2分）1.计算机识别、存储和加工处理的对象被统称为________。A.数据B.数据元素C.数据结构D.数据类型2.已知一栈的进栈序列为：1234，则下列哪个序列为不可能的出栈序列________。A．1234 B．4321C．2143 D．41233.链表不具有的特点是________。A.随机访问B.不必事先估计所需存储空间大小C.插入与删除时不必移动元素D.所需空间与线性表长度成正比4.设InitQueue(Q)、EnQueue(Q,e)、DeQueue(Q,e)分别表示队列初始化、入队和出队的操作。经过以下队列操作后，队头的值是________InitQueue(Q);EnQueue(Q,a);EnQueue(Q,b);EnQueue(Q,c);DeQueue(Q,x)A.aB.bC.NULLD.x5.在一个单链表HL中，若要删除由指针q所指向结点的后继结点，则执行________。A．p=q->next;p->next=q->next;free(p);B．p=q->next;q->next=p;free(p);C．p=q->next;q->next=p->next;free(p);D．q->next=q->next->next;q->next=q;free(p);6.一个顺序表第一个元素的存储地址是100,每个元素占2个存储单元，则第5个元素的地址是________。A．110B．108C．100D．1207.在一个长度为n的顺序存储的线性表中，在其第i个位置插入一个新元素时，需要移动元素的次数是________。A.n-iB.n-i+1C.n-i-1D.i8．下面关于线性表的叙述错误的是________。 A.线性表采用顺序存储必须占用一片连续的存储空间 B.线性表采用链式存储不必占用一片连续的存储空间C.线性表采用链式存储便于插入和删除操作的实现D.线性表采用顺序存储便于插入和删除操作的实现9.Push(e)表示e进栈，Pop(e)表示退栈并将栈顶元素存入e。下面的程序段可以将A,B的值交换的操作序列是________。A.Push(A)Push(B)Pop(A)Pop(B)B.Push(A)Push(B)Pop(B)Pop(A)C.Push(A)Pop(B)Push(B)Pop(A)D.Push(B)Pop(A)Push(A)Pop(B)10.下列查找方法中哪一种不适合元素的链式存储结构________。A．顺序查找B．分块查找C．二分查找D．散列查找11.下列排序算法中，不能保证每趟排序至少能将一个元素放到其最终的位置上的算法是________。快速排序B.希尔排序C.堆排序D.冒泡排序12.设一棵二叉树的深度为k，则该二叉树中最多有________个结点。 A．2k-1 B.2k C.2k-1 D.2k-113.下列四个选项中，能构成堆的是________。A.75,65,30,15,25,45,20,10B.75,65,45,10,30,25,20,15C.75,45,65,30,15,25,20,10D.75,45,65,10,25,30,20,1514.在一个具有n个顶点的无向图中，要连通全部顶点至少需要多少条边________。A．n(n-1)/2B．n-1C．nD．n+115.栈和队列的共同特点是________。A.都是操作受限的线性表B.都是先进后出C.都是后进先出D.无共同点二、填空题（本题共10分，每空1分）若经常需要对线性表进行查找操作，则最好采用________存储结构。某带头结点单链表的头指针为L，判定该单链表非空的条件________________。数据的逻辑结构包括集合、________、________和图状结构四种类型。图的两种遍历方式为：广度优先遍历和_______________。线性表的链式存储结构中的结点包含________域和________域。向一棵二叉搜索树中插入一个元素时，若元素的值小于根结点的值，则应把它插入到根结点的_______上。下面程序段的功能实现数据x进栈，要求在下划线处填上正确的语句。typedefstruct{intstack[100];inttop;}seqstack;voidpush(seqstack*s,intx){if(s->top==99)printf(“overflow”);else{_____(1)_______________;__(2)_______________;}}三、应用题（本题共40分）1．设散列表长度为11，散列函数h(key)=key%11。给定的关键字为1，13，12，34，38，33，2，22。试画出用线性探查法解决冲突时所构造的散列表。并计算在查找成功时候的平均查找长度。（6分）2．有一组权值14、21、32、15、28，画出哈夫曼树，并计算其WPL。（6分）3．已知图G=(V,E)，其中V={1,2,3,4,5},E={(1,2),(1,3),(1,4),(2,3),(2,5),(3,4),(4,5)}。要求完成如下操作：（6分）（1）写出图的邻接矩阵（2）写出采用邻接矩阵存储时，从顶点1出发的广度优先搜索遍历序列。4．已知序列{503，87，512，61，908，170，897，275，653，462}，分别写出执行下列排序算法的各趟排序结束时，关键字序列的状态：（10分）（1）直接插入排序（2）基数排序5．对于下面所示的连通图，写出由Prim算法生成的最小生成树。（5分）6.将下面的树转化为一棵二叉树,并写出对二叉树进行层序遍历的序列。（7分）AABCDEFGH四、算法题（本题共20分）1．完成中序遍历二叉树。Typedefstructnode{Chardata;Structnode*lchild;Structnode*rchild;}BTreeNode,*LinkBtree;VoidInOrder(LinkBtreeBt_pointer){If(Bt_pointer!=NULL){_________(1)_____________;__________(2)_____________;__________(3)____________;}}2.完成二分查找算法：#Definen10typedefintKeyType;typedefstruct{KeyTypekey;}NodeType;TypedefNodeTypeSeqList[n+1];intBinSearch(SeqListR,KeyTypek){intlow=1,high=n,mid;while(_____（4）_______){mid=(low+high)/2;if(R[mid].key==k)returnmid;if(R[mid].key>k)_____（5）_____;else________（6）_______;}return0;}3.编写算法实现直接插入排序。（8分）参考答案一、选择题（本题共30分,每题2分）123456789101112131415ADABCBBDACBDCBA二、填空题（本题共10分，每空1分）1）顺序2）L->next!=NULL3）线性结构树形结构4）深度优先遍历5）数据指针6）左子树7）s->top++s->stack[s->top]=x三、应用题（本题共40分）1、（6分）H(1)=1H(13)=2H(12)=1冲突，H1=2冲突，H2=3H(34)=1冲突，H1=2冲突，H2=3冲突，H3=4H(38)=5H(33)=0H(2)=2冲突，H1=3冲突，H2=4冲突，H3=5冲突，H4=6H(22)=0冲突，H1=1冲突，H2=2冲突，H3=3冲突，H4=4冲突，H5=5冲突，H6=6冲突，H7=7ASL=(1+1+3+4+1+1+5+8)/8=24/8=32、（6分）1101104961212829321415Wpl=2493、图的邻接矩阵：（3分）广度优先序列：12345（3分）01110101011101010101010104、1）（503）8751261908170897275653462（5分）（87503）51261908170897275653462（87503512）61908170897275653462（6187503512）908170897275653462（6187503512908）170897275653462（6187170503512908）897275653462（6187170503512897908）275653462（6187170275503512897908）653462（6187170275503512653897908）462（6187170275462503512653897908）2）第一趟：1706151246250365327587897908（5分）第二趟：5039085126536146217027587897第三趟：61871702754625035126538979085、（5分）ABDABDEFGHC层序遍历序列:ABECFDGH四、算法题（本题共20分）1、（1）InOrder(Bt_pointer->lchild);（2分）(2)printf(“%c”,Bt_pointer->data);（2分）(3)InOrder(Bt_pointer->rchild);（2分）2、（4）low<=high（5）high=mid-1;（6）low=mid+1;（6分）3、voidInsertSort(inta[],intn)（8分）{inti,j;for(i=2;i<=n;i++){a[0]=a[i];j=i-1;while(a[0]<a[j]){a[j+1]=a[j];j--;}a[j+1]=a[0];}}试卷一一、选择题（本题共30分,每题2分）1.计算机识别、存储和加工处理的对象被统称为________。A.数据B.数据元素C.数据结构D.数据类型2.已知一栈的进栈序列为：1234，则下列哪个序列为不可能的出栈序列________。A．1234 B．4321C．2143 D．41233.链表不具有的特点是________。A.随机访问B.不必事先估计所需存储空间大小C.插入与删除时不必移动元素D.所需空间与线性表长度成正比4.设InitQueue(Q)、EnQueue(Q,e)、DeQueue(Q,e)分别表示队列初始化、入队和出队的操作。经过以下队列操作后，队头的值是________InitQueue(Q);EnQueue(Q,a);EnQueue(Q,b);EnQueue(Q,c);DeQueue(Q,x)A.aB.bC.NULLD.x5.在一个单链表HL中，若要删除由指针q所指向结点的后继结点，则执行________。A．p=q->next;p->next=q->next;free(p);B．p=q->next;q->next=p;free(p);C．p=q->next;q->next=p->next;free(p);D．q->next=q->next->next;q->next=q;free(p);6.一个顺序表第一个元素的存储地址是100,每个元素占2个存储单元，则第5个元素的地址是________。A．110B．108C．100D．1207.在一个长度为n的顺序存储的线性表中，在其第i个位置插入一个新元素时，需要移动元素的次数是________。A.n-iB.n-i+1C.n-i-1D.i8．下面关于线性表的叙述错误的是________。 A.线性表采用顺序存储必须占用一片连续的存储空间 B.线性表采用链式存储不必占用一片连续的存储空间C.线性表采用链式存储便于插入和删除操作的实现D.线性表采用顺序存储便于插入和删除操作的实现9.Push(e)表示e进栈，Pop(e)表示退栈并将栈顶元素存入e。下面的程序段可以将A,B的值交换的操作序列是________。A.Push(A)Push(B)Pop(A)Pop(B)B.Push(A)Push(B)Pop(B)Pop(A)C.Push(A)Pop(B)Push(B)Pop(A)D.Push(B)Pop(A)Push(A)Pop(B)10.下列查找方法中哪一种不适合元素的链式存储结构________。A．顺序查找B．分块查找C．二分查找D．散列查找11.下列排序算法中，不能保证每趟排序至少能将一个元素放到其最终的位置上的算法是________。快速排序B.希尔排序C.堆排序D.冒泡排序12.设一棵二叉树的深度为k，则该二叉树中最多有________个结点。 A．2k-1 B.2k C.2k-1 D.2k-113.下列四个选项中，能构成堆的是________。A.75,65,30,15,25,45,20,10B.75,65,45,10,30,25,20,15C.75,45,65,30,15,25,20,10D.75,45,65,10,25,30,20,1514.在一个具有n个顶点的无向图中，要连通全部顶点至少需要多少条边________。A．n(n-1)/2B．n-1C．nD．n+115.栈和队列的共同特点是________。A.都是操作受限的线性表B.都是先进后出C.都是后进先出D.无共同点二、填空题（本题共10分，每空1分）若经常需要对线性表进行查找操作，则最好采用________存储结构。某带头结点单链表的头指针为L，判定该单链表非空的条件________________。数据的逻辑结构包括集合、________、________和图状结构四种类型。图的两种遍历方式为：广度优先遍历和_______________。线性表的链式存储结构中的结点包含________域和________域。向一棵二叉搜索树中插入一个元素时，若元素的值小于根结点的值，则应把它插入到根结点的_______上。下面程序段的功能实现数据x进栈，要求在下划线处填上正确的语句。typedefstruct{intstack[100];inttop;}seqstack;voidpush(seqstack*s,intx){if(s->top==99)printf(“overflow”);else{_____(1)_______________;__(2)_______________;}}三、应用题（本题共40分）1．设散列表长度为11，散列函数h(key)=key%11。给定的关键字为1，13，12，34，38，33，2，22。试画出用线性探查法解决冲突时所构造的散列表。并计算在查找成功时候的平均查找长度。（6分）2．有一组权值14、21、32、15、28，画出哈夫曼树，并计算其WPL。（6分）3．已知图G=(V,E)，其中V={1,2,3,4,5},E={(1,2),(1,3),(1,4),(2,3),(2,5),(3,4),(4,5)}。要求完成如下操作：（6分）（1）写出图的邻接矩阵（2）写出采用邻接矩阵存储时，从顶点1出发的广度优先搜索遍历序列。4．已知序列{503，87，512，61，908，170，897，275，653，462}，分别写出执行下列排序算法的各趟排序结束时，关键字序列的状态：（10分）（1）直接插入排序（2）基数排序5．对于下面所示的连通图，写出由Prim算法生成的最小生成树。（5分）6.将下面的树转化为一棵二叉树,并写出对二叉树进行层序遍历的序列。（7分）AABCDEFGH四、算法题（本题共20分）1．完成中序遍历二叉树。Typedefstructnode{Chardata;Structnode*lchild;Structnode*rchild;}BTreeNode,*LinkBtree;VoidInOrder(LinkBtreeBt_pointer){If(Bt_pointer!=NULL){_________(1)_____________;__________(2)_____________;__________(3)____________;}}2.完成二分查找算法：#Definen10typedefintKeyType;typedefstruct{KeyTypekey;}NodeType;TypedefNodeTypeSeqList[n+1];intBinSearch(SeqListR,KeyTypek){intlow=1,high=n,mid;while(_____（4）_______){mid=(low+high)/2;if(R[mid].key==k)returnmid;if(R[mid].key>k)_____（5）_____;else________（6）_______;}return0;}3.编写算法实现直接插入排序。（8分）参考答案一、选择题（本题共30分,每题2分）123456789101112131415ADABCBBDACBDCBA二、填空题（本题共10分，每空1分）1）顺序2）L->next!=NULL3）线性结构树形结构4）深度优先遍历5）数据指针6）左子树7）s->top++s->stack[s->top]=x三、应用题（本题共40分）1、（6分）H(1)=1H(13)=2H(12)=1冲突，H1=2冲突，H2=3H(34)=1冲突，H1=2冲突，H2=3冲突，H3=4H(38)=5H(33)=0H(2)=2冲突，H1=3冲突，H2=4冲突，H3=5冲突，H4=6H(22)=0冲突，H1=1冲突，H2=2冲突，H3=3冲突，H4=4冲突，H5=5冲突，H6=6冲突，H7=7ASL=(1+1+3+4+1+1+5+8)/8=24/8=32、（6分）1101104961212829321415Wpl=2493、图的邻接矩阵：（3分）广度优先序列：12345（3分）01110101011101010101010104、1）（503）8751261908170897275653462（5分）（87503）51261908170897275653462（87503512）61908170897275653462（6187503512）908170897275653462（6187503512908）170897275653462（6187170503512908）897275653462（6187170503512897908）275653462（6187170275503512897908）653462（6187170275503512653897908）462（6187170275462503512653897908）2）第一趟：1706151246250365327587897908（5分）第二趟：5039085126536146217027587897第三趟：61871702754625035126538979085、（5分）ABDABDEFGHC层序遍历序列:ABECFDGH四、算法题（本题共20分）1、（1）InOrder(Bt_pointer->lchild);（2分）(2)printf(“%c”,Bt_pointer->data);（2分）(3)InOrder(Bt_pointer->rchild);（2分）2、（4）low<=high（5）high=mid-1;（6）low=mid+1;（6分）3、voidInsertSort(inta[],intn)（8分）{inti,j;for(i=2;i<=n;i++){a[0]=a[i];j=i-1;while(a[0]<a[j]){a[j+1]=a[j];j--;}a[j+1]=a[0];}}试卷二一、选择题（本题共20分,每题2分）1.下面程序段的时间复杂度为（）。for(i=1;i<=n;i++)for(j=1;j<=n;j++)s++;A.O(n)B.O(n2)C.O(2*n)D.O（i*j）2.线性表采用链式存储时，结点的存储地址（）。A．必须是不连续的B．部分地址必须是连续的C．连续与否均可D．和头结点的存储地址相连续3.若让元素1，2，3依次进栈，则出栈时的序列不可能出现的是（）。A．3，2，1B．1，2，3C．3，1，2D．2，1，34.下面说法不正确的是()A．串S1=“this_is_a_string”的长度是16。B．串S2=“this”是串S1的子串。C．串S3=“thisis”在串S1中的位置是1。D．串S4=“a”在串S1中的位置是9。5.一个非空广义表的表头（）。A．不可能是子表B．只能是子表C．只能是原子D．可以是子表或原子6.完全二叉树()满二叉树A．不一定是B．一定不是C．一定是D．不能确定关系7.用链表表示线性表的优点是（）便于随机存取便于插入和删除操作花费的存储空间较顺序存储少元素的物理顺序与逻辑顺序相同8.在一个具有n个顶点的无向图中，要连通全部顶点至少需要多少条边()。A．n(n-1)/2B．n-1C．nD．n+19.下列查找方法中哪一种不适合元素的链式存储结构()A．顺序查找B．分块查找C．二分查找D．散列查找10.下面哪种排序方法稳定性最好()。A．希尔排序B．冒泡排序C．快速排序D．堆排序二、填空题（本题共20分）1.数据的逻辑结构可以分为两大类：_________和________。2.在二叉树的第i层上最多有___________个结点。3.无向图中恰好有__________条边，才称为无向完全图。4.用单链表方式存储的线性表，存储每个结点需要有两个域，一个是_________，另一个是________。5.设二维数组A5×6的每个元素占4个字节，已知LOC（a00）=1000，则A一共占用_______字节。如果按行优先存储时，a25的起始地址是_________。6.3个结点的树有_______种形态，3个结点的二叉树有________种形态。7.一个广义表为（a，（a，b），d，e，（（i，j），k）），则该广义表的深度为________。8.栈的插入操作在_______进行，删除操作在_______进行。9.在二叉树中，结点的最大度数是_______。10.判定一个有向图中是否存在回路，即是否含有环，可以使用_________方法。11.二分查找的效率较高，但是要求查找表中的关键字_______，并且要求表的存储为________。12.在构造散列表的过程中，不可避免会出现冲突，通常解决它的方法有_______和_______。13．从任何一个结点开始都能成功查找其他结点的单链表是表。三、应用题（本题共50分，