选择填空判断

一、 判断题顺序表和一维数组一样，都可以按下标随机（或直接）访问。（J）数据的逻辑结构是指各数据元素之间的逻辑关系，是用户根据应用需要建立的。（J）只有用面向对象的计算机语言才能描述数据结构算法。（X）在对双向循环链表做删除一个结点操作时，应先将被删除结点的前驱结点和后继结点链接好再执行删除结点操作。（J）数据元素是数据的最小单位。（X）算法和程序都应具有下面一些特征：输入，输出，确定性，有穷性，可行性。（J）插入与删除操作是数据结构中最基本的两种操作，因此这两种操作在数组中也经常被使用。（ X）线性表若采用链式存储表示，在删除时不需要移动元素。（J）用一组地址连续的存储单元存放的元素一定构成线性表。（X）线性表的逻辑顺序与物理顺序总是一致的。（X）线性表的顺序存储表示优于链式存储表示。（X）链表的每个结点中都恰好包含一个指针。（X）二、 填空题若经常需要对线性表进行查找操作，则最好采用（顺序）存储结构。（循环）链表从任何一个结点出发，都能访问到所有结点。若经常需要对线性表进行插入与删除操作，该线性表最好采用（链式）存储结构。通常用时间复杂度和（空间复杂度）两种方法衡量算法的效率已知一顺序存储的线性表，每个元素占用k个存储单元，若第一个元素的地址为Loc1，则第i个元素的地址为（Loc1+（i-1）*k）。在以L为头指针的带头结点的单链表和单循环链表中，判断链表是否为空的条件分别为（L->next==NULL和_L->next==L）。顺序表中逻辑上相邻的元素的物理位置（相邻），单链表中逻辑上相邻的元素的物理位置（不一定相邻）。数据的逻辑结构包括集合、（线性结构）、树形结构和图状结构四种类型。已知有实现同一功能的两个算法，其时间复杂度分别为O（log2n）和O（n），哪个算法的效率更高？（O（logn））2在一个单链表L中，若要在指针q所指结点的后面插入一个由指针p所指向的结点，则应进行的操作序列为：（p->next=q->next）,q一>next=po在单链表设置表头结点的作用是插入和删除表中第一个元素时不必对（头指针）进行特殊处理。在双向链表中，每个结点含有两个指针域，一个指向（直接前驱）结点，另一个指向（直接后继）结点。在非空线性表中除第一个元素外，集合中每个数据元素只有一个（直接前驱）；除最后一个元素之外，集合中每个数据元素均只有一个（直接后继）。一个算法一该具有有穷性，（确定性），可行性，输入和输出这五种特性。三、 选择题计算机识别、存储和加工处理的对象被统称为A数据B.数据元素C.数据结构D.数据类型线性表若采用链式存储结构时必须是连续的线性表若采用链式存储结构时必须是连续的C.一定是不连续的线性表若采用顺序存储结构时A.必须是连续的C.一定是不连续的要求内存中可用存储单元的地址__D.部分地址必须是连续的D.连续，不连续都可以要求内存中可用存储单元的地址__A部分地址必须是连续的D.连续，不连续都可以在一个长度为n的顺序存储的线性表中，向第i个元素(1WiWn+1)位置之前插入一个新元素时，需要移动B个元素。A.n-i B.n-i+1 C.n-i-1 D.i在长度为n的顺序存储的线性表中，删除第i个元素(1WiWn)时，需要从前向后依次前移―A个元素。A.n-i B.n-i+1n-i-1 D.i链表不具有的特点是A。A.随机访问 B.不必事先估计所需存储空间大小插入与删除时不必移动元素 D.所需空间与线性表长度成正比在一个单链表L中，若要删除由指针q所指向结点的后继结点，则执行D―。A.q=q->next; B.q->next=p->next;C.p=q->next; D.q->next=q->next->next;在一个单链表HL中，若要删除由指针q所指向结点的后继结点，则执行__B___。A.p=q->next;p->next=q->next; B.p=q->next;q->next=p->next;C.p=q->next;q->next=p; D.q->next=q->next->next;q->next=q;在一个长度为n的顺序存储线性表中，删除第i个元素(1WiWn)时，需要移动A个元素。A.n-iB.n-i+1C.n-i-1D.i下面算法的时间复杂度为B。intf(unsignedintn){if(n==0||n==1)return1;elsereturnn*f(n-1);B.O(n)A.O(1)B.O(n)C.O(n2) D.O(n!)下面程序段的时间复杂度为C。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)数据结构通常是研究数据的—A 及它们之间的联系。A存储和逻辑结构 B存储和抽象C理想和抽象 D理想与逻辑算法分析的目的是___BA、找出数据结构的合理性 B、分析算法的效率以求改进、研究算法中的^输入和输出的关系D、分析算法的易懂性和文档性算法分析的两个主要方面是：AA空间复杂性和时间复杂性 B正确性和简明性C可读性和文档性 D数据复杂性和程序复杂线性表L在_^—情况下适用于使用链式结构实现。A需经常修改L中的结点值B需不断对L进行删除插入CL中含有大量的结点 DL中结点结构复杂四、程序题typedefstructLNode{intdata;structLNode*next;}LNode,*LinkList;将下面算法填完整。voidListInsert_L(nodeL,inti,elementtypex){LinkListp=L,s;intk=0;while(&&){ ;k++;}if(!p||j>i-1)returnERROR;s=(LinkList)malloc(sizeof(node));s->data=x; }Pk<i-1p=p->nexts->next=p->next;p->next=s;简述下面算法的功能voidAC(LinkList&L){//L为一个无头结点的单链表if(L&&L->next){q=L;L=L->next;p=L;while(p->next)p=p->next;p->next=q;q->next=NULL;}}将该单链表的表头元素移到表尾简述下面算法的功能voidAE(LNode*s,LNode*q){p=s;while(p->next!=q)p=p->next;p->next=s;}voidAD(LNode*pa,LNode*pb){//pa和pb分别指向单循环链表中的两个结点AE(pa,pb);AE(pb,pa);}将一个单循环链表拆分成两个单循环链表(指针pa和pb分别指向这两个单循环链表中的某两个节点)下列算法为删除带头结点的单链表head中值为x的算法，将程序填完整(每空2分)已知结构体：typedefstructLNode{ElemTypedata;structLNode*next;}LNode,*LinkList;voiddel(LinkListhead){q=head; ;while(p&& )){q=p; ;}if(p==null)printf(“error”);else{;free(p);printf("success!”)；}}p=q->nextp->data!=xp=p->nextq->next=p->next下列算法为删除单链表中值为X的算法，将程序填完整(4分，每空2分)已知结构体：structnode{ElemTypedata;structLNode*next;};voiddel(structnode*head){q=head;p=q->next;while((p )&&(p->data!=x )){q=p;___ ;}if(p==null)printf("error”);else{;free(p);printf("success!”);}}p=q->nextq->nex=p->next下列算法为利用尾插法，建立一个单链表，将程序填完整程序voidCreateList(LinkList&L,intn){LinkListr,p;inti;L=(LinkList)malloc(sizeof(node));L->next=NULL;for(i=n;i>0;一i){p=(LinkList)malloc(sizeof(node));scanf(“％c”，&p->data);r->next=p;}}r=L;p->next=NULL;r=p;队栈串数组广义表一、 判断题：递归的算法简单、易懂、容易编写，而且执行效率也高。（f）链式栈与顺序栈相比，一个明显的优点是通常不会出现栈满的情况。（t）堆栈、队列和数组的逻辑结构都是线性表结构。（t）单链表形式的队列，头指针F指向队列的第一个结点，尾指针R指向队列的最后一个结点（f）若某堆栈的输入序列为1,2,3,4,则4,3,1,2不可能是堆栈的输出序列之一。（t）栈和队列都是限制取点的线性结构（t）栈和队列都是顺序存取的线性表，但它们对存取位置的限制不同。（t）稀疏矩阵压缩存储后，必会失去随机存取功能。（t）如果两个串中含有相同的字符，则这两个串相等（f）广义表的表头和表尾既可以是单元素，也可以是广义表。（f）二、 填空题：在初始为空的队列中插入元素A,B,C,D以后，紧接着做了两次删除操作，此时的队尾元素是__d__。已知循环队列的存储空间为数组a[21]，且头指针（指向队头元素）和尾指针（队尾元素的下一位置）分别为8和3,则该队列的当前长度为_16__。栈结构允许进行删除操作的一端为—栈顶__。队列又称为—先进先出—的线性表

对于顺序存储的队列，存储空间大小为n,头指针为F,尾指针为R。若在逻辑上看一个环，则队列中元素的个数为—(r+n)-f__。队列的特点是—先进先出_。栈又称为先进后出的线性表，队列又称为先进先出的线性表。设数组A[m]为循环队列Q的存储空间，font为头指针，rear为尾指针，判定Q为空队列的条件__front==rear 。设元素1,2,3,4,5依次进栈S，若要在输出端得到序列34251，则应进行的操作序列为：push(S,1)，push(S,2)，push(S,3)，pop(S)，push(S,4)，pop(S)，pop(S)，push(S,5)，pop(S)，pop(S)。一个串的任意个连续的字符组成的子序列称为该串的子串包含该子序列的串称为主串，该子序列在串中的位置用子串的第一个字符在主串中的位置来表示。在串的链式存储方式中，结点越大，运算处理越不方便(方便/不方便)，存储占用量越小(大/小)。求串T在主串S中首次出现的位置的操作是—模式匹配_。广义表(A,(a,b),d,e,((i,j),k))，则广义表的长度为5,深度为3,表头为A，表尾为((a,b),d,e,((i,j),k))。已知广义表ls=(a,(b,c,d),e),运用head和tail函数取出ls中的原子b的运算是_head(head(tai1(1s)))。设有二维数组A[5][6]，其每个元素占两个存储单元，第一个元素的存储地址为1100，若按行优先顺序存储，则元素A[2][3]的存储地址为山0,按列优先顺序存储，元素A[2][3]的存储地址为1134。设有二维数组A[9][19](下标从0开始)，其每个元素占两个字节，第一个元素的存储地址为100，若按行优先顺序存储，按列优顺序存储，元素A[6,6]的存储地址为__220__。设二维数组A[m][n]按列优先存储，每个元素占1个存储单元，元素A00的存储地址loc(A00)，则.的存储地址loc(A..)=—loc(a00)+(j*m+i)*1—。18.三、选择题：判定一个栈ST(最多元素为m0)为空的条件是___b__A.ST->top<>0B.ST->top=0C.ST->top<>m0D.ST->top=m0C.ST->top<>m0D.ST->top=m0链式栈与顺序栈相比，一个比较明显的优点是___b。A.插入操作更加方便 B.通常不会出现栈满的情况C.不会出现栈空的情况 D.删除操作更加方便假定一个顺序队列的队首和队尾指针分别为front和rear，则判断队空的条件是__d。A.front+1==rearB.rear+1==frontC.front==0D.front==rea队和栈的主要区别是__dA.逻辑结构不同 B.存储结构不同C.所包含的运算个数不同 D.限定插入和删除的位置不同假定利用数组a[N]循环顺序存储一个队列，用front（指向队首元素）和rear（指向队尾元素的下一位置）分别表示队首和队尾指针，并已知队列未空，当出队并返回队首元素时所执行的操作为__d。A.returna[++rear%N]; B.returna[一rear%N];C.returna[++front%N]; D.returna[front++%N];入栈次序是a,b,c,d,e，则出栈次序不可能是―c。A.e,d,c,b,a B.d,e,c,b,a C.d,c,e,a,b D.a,b,c,d,e由两个栈共享一个向量空间的好处是___b___oA减少存取时间，降低下溢发生的机率 B节省存储空间，降低上溢发生的机率C减少存取时间，降低上溢发生的机率 D节省存储空间，降低下溢发生的机率假定利用数组a[N]顺序存储一个栈，用top表示栈顶指针，top==0表示栈空，并已知栈未满，当元素x进栈时所执行的操作为___D___OA.a[一top]=x;B.a[top一]=x;C.a[++top]=x;D.B.a[top++]=x;假定利用数组a[N]顺序存储一个栈，用top表示栈顶指针，top==0表示栈空，并已知栈未空，当出栈并返回栈顶元素时所执行的操作为—_A__。A.returna[一top]; B.returna[top一]; C.returna[++top];D.returna[top++];假定一个循环顺序队列的队首和队尾指针分别为f和r，则判断队空的条件是__D___。A.f+1==r B.r+1==fC.f==0 D.f==r若让元素1,2,3依次进栈，则出栈次序不可能出现___C___种情况。A.3,2,1B.2,1,3C.3,1,2D.1,3,2当利用大小为N的一维数组存储一个循环队列时，则该队列的最大长度为__B_。A.N-2B.N-1C.ND.N+1假定利用数组a[N]循环顺序存储一个队列，用front和rear分别表示队首和队尾指针，并已知队列未满，当元素x入队时所执行的操作为___B_A.a[++rear%N]=x;B.a[rear++%N]=x;C.a[一rear%N]=x; D.a[rear一%N]=x;如下陈述中正确的是__A___。A.串是一种特殊的线性表 B.串的长度必须大于零C.串中元素只能是字母 D.两个串si和s2若长度相同，则这两个串相等如下陈述中正确的是__A___。A.串是一种特殊的线性表 B.串的长度必须大于零C.串中元素只能是字母 D.空串就是空白串在以下的叙述中，正确的是__A___。二维数组可以看做它的每个数据元素为一个线性表的线性表栈的操作方式是先进先出线性表的线性存储结构优于链表存储结构队列的操作方式是先进后出。一个非空广义表的表头—D___。A.不可能是子表 B.只能是子表C.只能是原子 D.可以是子表或原子在目标串T[0„n-1]="xwxxyxy”中，对模式串p[0„mT]="yy”进行子串定位操作的结果A A.0 B.2 C.3 D.5数组A中，每个元素的长度为3字节，行下标从1到8,列下标从1到10,从首地址SA开始连续存放在存储器中，按行存放时，元素a[8][5]地址为（C）ASA+141 BSA+180CSA+222 DSA+225串是一种特殊的线性表，其特殊性体现在：BA.可以顺序存储 B.数据元素只能来自字符集C.可以链式存储 D.数据元素可以是多个字符五、算法Q是一个循环队列，请分别写出插入和删除一个元素的算法#defineMAXSIZE100//最大队列长度typedefstruct{QElemType*base;intfront,rear;}SqQueue;（以下算法3分：）intEnQueue(SqQueue&Q,QElemTypex){//Q是一个循环队列，若队列不满，则将x插入并返回1；否则返回0if((Q.rear+1)%MAXSIZE==Q.front)return0; //队列满Q.base[Q.rear]=x;Q.rear=(Q.rear+1)%MAXSIZE;return1;}(以下算法3分：)intDeQueue(SqQueue&Q,QElemType&x){//Q是一个循环队列，若队列不空，则删除队头元素并由x带回，//且返回1；否则返回0if(Q.front==Q.rear)return0;else{x=Q.base[Q.front];Q.front=(Q.front+1)%MAXSIZE;return1;})已知：Q是一个循环队列，并且已知下列定义：#defineMAXSIZE100typedefstruct{QElemTypebase[MAXSIZE];intfront,rear;}SqQueue;约定：顺序队中，非空队中，头指针始终指向队列头元素的前一个元素，而尾指针始终指向队列尾元素。请写出插入一个元素的算法(6分，每空2分)intEnQueue(SqQueue&Q,QElemTypex){if()return0;Q.rear=;Q.base[]=x;return1;}算法分析简述下列算法的功能(栈和队列的元素类型为int)1.StatusAA(StackS){inti,n,A[255];n=0;while(!StackEmpty(S)){n++;Pop(S,A[n]);}for(i=1;i<=n;i++)Push(S,A[i]);}栈S就地逆置。StatusAB(StackS,inte){StackT;intd;InitStack(T);while(!StackEmpty(S)){Pop(S,d);if(d!=e)Push(T,d);}while(!StackEmpty(T)){Pop(T,d);Push(S,d);}}删除栈S中值等于e的元素。voidAC(Queue&Q){StackS;intd;InitStack(S);while(!QueueEmpty(Q)){DeQueue(Q,d);Push(S,d);}while(!StackEmpty(S)){Pop(S,d);EnQueue(Q,d);}}队列Q就地逆置。简述下面算法的功能。(2分)voidconversion(){initstack(s);//初始化栈scanf(“％d”，n);while(n)

{push(s,n%8);n=n/8;}while（!Stackempty（s））//Stackempty（s）为栈判空{pop（s,e）;printf（“％d”，e）;} }功能是：十进制数转化成八进制数。树一、判断题：二叉树是一棵无序树。（X）在一棵二叉树中，假定每个结点只有左子女，没有右子女，对它分别进行中序遍历和后序遍历，则具有相同的结果。（J）度为二的有序树等价于二叉树。（J）树的带权路径长度最小的二叉树中必定没有度为1的结点。（J）哈夫曼树一定是满二叉树。（X）满二叉树也是完全二叉树。（J）设与一棵树T所对应的二叉树为BT，则与T中的叶子结点所对应的BT中的结点也一定是叶子结点。（X）将一棵树转换成二叉树后，根结点没有左子树（X）已知一棵二叉树的前序序列和后序序列可以唯一地构造出该二叉树。（J）10用二叉树的前序遍历和中序遍历可以导出树的后序遍历。（J）在完全二叉树中，若某结点无左孩子，则它必是叶结点。（J）。12.任何一棵二叉树都有n°=n2+1的关系式。顷）已知一棵树的前序遍历和后序遍历序列能唯一地确定这棵树。（J）二、填空题假定一棵二叉树的结点个数为32,则它的最小深度为___6__。假定一棵树的广义表表示为A（B（C,D（E,F,G）,H（I,J））），则结点H的双亲结点为__B__,在一棵二叉树中，度为2的结点有5个，度为1的结点有6个，那么叶子结点有__6_个。树的双亲表示法便于实现涉及到—双亲—的操作，孩子表示法便于实现涉及到孩子的ACBDEF操作。ACBDEF对于一颗具有n个结点的二叉树，对应二叉链表中指针域有__n-1__个用于指向子结点。下图所示二叉树存储在一维数组中，则元素F的下标位置为___11___。（A为1）高度为k的二叉树具有的结点数目，最少为—K_,最多为_2k-1_。对任何一棵二叉树，若n0，nl，n2分别是度为0,1,2的结点的个数，则n0=__n2+1__。一棵含有16个结点的完全二叉树，对他按层编号，对于编号为7的结点，他的双亲结编号点为_3—左孩子编号为_14—、右孩子编号为_15_。在含100个结点的完全二叉树，叶子结点的个数为_50__。度数为0的结点，即没有子树的结点叫作—叶子—结点。同一个结点的儿子结点之间互称为—兄弟—结点。若一棵完全二叉树含有121个结点，则该树的深度为_7_。已知一棵树的前序序列为ABCDEF，后序序列为CEDFBA，则对该树进行层次遍历得到的序列为_ABCDFEO 三、选择题在一棵具有n个结点的二叉树中，所有结点的空子树个数等于—C_。nB.n-lC.n+lD.2*n在一棵二叉树的第5层上，最多具有_B_个结点。A.14B.16C.31D.32在一棵深度为h的完全二叉树中，所含结点个数不少于—__D___。A.2hB.2h+i C.2h-1 D.2h-i一棵树的广义表表示为a(b(c),d(e(g(h)),f))，则该二叉树的高度为___D___。A.2B.3C.4D.5将一棵有40个结点的完全二叉树从上到下，从左到右依次对结点进行编号，根结点的编号为1，则编号为15的结点的左孩子的编号为___A___。A.30 B.31C.16 D.32在一棵树中，每个结点最多有___B___个直接前驱结点。A.0B.lC.2D.任意多个7.树中所有结点的度数之和等于结点总数加___C___。A.0B.lC.-lD.2二叉树中第5层上的结点个数最多为―CA.8 B.15C.16 D.32将一棵有100个结点的完全二叉树从上到下，从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的左孩子的编号为___A___。B.9998B.99TOC\o"1-5"\h\zC.50 D.48由权值分别为3,8,6,2,5的叶子结点生成一颗赫夫曼树，它的带权路径长度为__D___OA.24B.48C.72D.53把一棵树转换为二叉树后，这棵二叉树的形态是一A 。A.唯一的 B.有多种C.有多种，但根结点都没有左孩子D.有多种，但根结点都没有右孩子具有n(n>0)个结点的完全二叉树的深度为_C 。A「log2(n)] BLlog2(n)J C|_log2(n)」+1 D「log2(n)+1]算法：假设二叉树采用链表存储结构，设计一个算法计算一棵给定二叉树的叶子结点数。请先写出存储结构，然后再完成算法。存储结构定义：typedefstructBiTNode{//结点结构Selemtypedata;structBiTNode*lchild,*rchild; }BiTNode,*BiTree;intleafs(BTree*b){intnum1,num2;if(b==NULL)return0;elseif(b->lchild==NULL&&b->rchild==NULL)return1;else{num1=leafs(b->lchild);num2=leafs(b->rchild);return(num1+num2);}}或：voidCountLeaf(BiTreeT,int&count){if(T){if((!T->lchild)&&(!T->rchild))count++;//对叶子结点计数CountLeaf(T->lchild,count);CountLeaf(T->rchild,count);}//if}//CountLeaf图一、 判断题：在AOE网络中一定只有一条关键路径。（X）图的深度优先搜索是一种典型的回溯搜索的例子，可以通过递归算法求解。（J）用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中的顶点个数有关，而与图的边数无关。（J）对于AOE网络，加速任一关键活动就能使整个工程提前完成。（X）如果有向图中各个顶点的度都大于2,则该图中必有回路。（X）邻接表只能用于有向图的存储，邻接矩阵对于有向图和无向图的存储都适用。（X）邻接矩阵适用于稠密图（边数接近于顶点数的平方），邻接表适用于稀疏图（边数远小于顶点数的平方）。（J）对于AOE网络，任一关键活动延迟将导致整个工程延迟完成。（J）无向图的邻接矩阵是对称的，有向图的邻接矩阵是不对称的。（J）对于有向图，顶点的度分为入度和出度，入度是以该顶点为终点的入边数目；出度是以该顶点为起点的出边数目，该顶点的度等于其入度和出度之和。（J）若图G的最小生成树不唯一，则G的边数一定多于n-1，并且权值最小的边有多条（其中n为G的顶点数）。（X）具有n个顶点的连通图的生成树具有n-1条边（J）在n个结点的无向图中，若边数＞n-1，则该图必是连通图.（X）若一个有向图的邻接矩阵中对角线以下元素均为零，则该图的拓扑有序序列必定存在（J）二、 二、填空题对于一个具有n个顶点的图，若采用邻接矩阵表示，则矩阵大小为___n2_。有一个n个顶点的有向完全图的弧数n（n-1）。在无向图中，若从顶点A到顶点B存在―路径，则称A与B之间是连通的。在一个无向图中，所有顶点的度数之和等于所有边数的2―倍。三、 选择题顶点个数为n的无向图最多有___B___条边。n-1B.n（n-1）/2C.n（n+1）/2D.n（n-1）n个顶点的连通图至少有___A―条边。

A.n-1B.nC.n+1D.0A.n-1B.nC.n+1D.0在一个有向图中，所有顶点的度数之和等于所有弧数的___B___倍。3B.2C.1D.1/2有向图的一个顶点的度为该顶点的__C。A.入度B.出度C.入度与出度之和 D.(入度+出度)/2一个连通图的生成树是包含图中所有顶点的一个___C___子图。A.极小B.连通C.极小连通D.无环图的深度优先遍历类似于树的___A。A.先序遍历 B.中序遍历C.后序遍历 D.层次遍历下面关于图的存储的叙述中，哪一个是正确的。―A用邻接矩阵法存储图，占用的存储空间数只与图中结点个数有关，而与边数无关用邻接矩阵法存储图，占用的存储空间数只与图中边数有关，而与结点个数无关用邻接表法存储图，占用的存储空间数只与图中结点个数有关，而与边数无关用邻接表法存储图，占用的存储空间数只与图中边数有关，而与结点个数无关如果某图的邻接矩阵是对角线元素均为零的上三角矩阵，则此图是D___A.有向完全图 B.连通图C.强连通图 D.有向无环图具有e条边的有向图，它的逆邻接表中有___B___个弧结点。TOC\o"1-5"\h\zA.e-1 B. e C. 2(e-1) D.2e具有e条边的无向图，它的邻接表中有―D—个边结点。A.e-1 B. e C. 2(e-1) D.2e在一个图中，所有顶点的度数之和等于图的边数的C倍。A.1/2 B. 1C.2 D. 4用邻接表表示图进行广度优先遍历时，通常是采用 B 来实现算法的。A.栈 B.队列 C.树 D.图排序和查找一、判断题进行折半查找的表必须是顺序存储的有序表。(J)在任何情况下，快速排序需要进行关键码比较的次数都是O(nlog2n)。(X)当从一个最小堆中删除一个元素时，需要把堆尾元素填补到堆顶位置，然后再按条件把它逐层向下调整，直到调整到合适位置为止。（J）直接选择排序是一种稳定的排序方法。（X）堆排序是一种稳定的排序算法。（X）快速排序法是一种稳定性排序法。（X）散列法存储的基本思想是由关键字的值决定数据的存储地址（J）对n个元素的表用堆排序法进行排序，时间复杂度是O（log2n）（X）在采用线性探测法处理冲突的散列表中，所有同义词在表中一定相邻（X）。堆排序是所需辅助空间最少的排序。（J）一个好的哈希函数应使函数值均匀的分布在存储空间的有效地址范围内，以尽可能减少冲突。（J）二、填空题若要对某二叉排序树进行遍历，保证输出元素的值序列按增序排列，应对该二叉排序树采用遍历法。中序元素关键字转换为该元素存储位置的函数f称为。哈希函数在数据的存放无规律而言的线性表中进行检索的最佳方法是 —。假设在有序线性表a[20]上进行折半查找，则比较一次查找成功的结点数为1；比较两次查找成功的结点数为一；比较四次查找成功的结点数为一；平均查找长度为一。解：显然，平均查找长度=心^<5次（"但具体是多少次，则不应当按照公式n+1ASL=log2（n+1）来计算（即（21Xlog21）/20=4.6次并不正2确！）。因为这是在假设n=2m-1的情况下推导出来的公式。应当用穷举法罗列：全部元素的查找次数为=（1+2X2+4X3+8X4+5X5）=74；ASL=74/20=3.7!!!将一个数据元素（或记录）的任意序列，重新排列成一个按关键字有序的序列叫排序。先将整个待排序列分割成若干子序列分别进行直接插入排序，待整个序列“基本有序”时，再对全体进行一次直接插入排序，此种排序方法叫做—希尔排序__排序。每次使两个相邻的有序表合并成一个有序表的排序方法叫做归并排序。每次从无序表中挑选出一个最大或最小元素，把它交换到有序表的一端，此种排序方法叫做简单选择排序。每次从无序表中取出一个元素，把它插入到有序表中的适当位置，此种排序方法叫做 直接插入排序。每次直接或通过“枢轴”元素间接比较两个元素，若出现逆序排列时就交换它们的位置，此种排序方法叫做快速 排序。假定一组数据的关键字为{46,79,56,38,40,84}，则利用堆排序方法建立的初始小顶堆为__{38,40,56，79，46，84}__。假定一组数据的关键字为{46,79,56,38,40,84}，则以第一个记录为枢轴，对其进行第一趟快速排序的结果为{40,38,46,56,79,84}。若待散列的序列为(18,25,63,50,42,32,9)，散列函数为H(key)=keyMOD9，与18发生冲突的元素有9三、选择题(共20分，每题2分)对于顺序存储的有序表(5,12,20,26,37,42,46,50,64)，哨兵位在前，为查找元素26,若采用顺序查找，需要比较D__次才能查找成功。A.3B.4C.5D.6设哈希表长为14,哈希函数f(k)=k%11，已知表中已有4个元素，关键字分别为15,38,61，84，存储位置分别为4,5,6,7,其它存储位置为空，如用二次探测再散列处理冲突，关键字为49的存储位置是__D。A.8B.3C.5D.9对于顺序存储的有序表(5,12,20,26,37,42,46,50,64),为查找元素26,若采用折半查找，需要比较___B__—次才能查找成功。A.3B.4C.5D.6对线性表进行折半查找时，要求线性表必须__C。以顺序方式存储以链接方式存储以顺序方式存储，且元素按关键字有序排序以链接方式存储，且元素按关键字有序排序对于哈希函数H(key)=key%13,被称为同义词的关键字是___DA.35和41 B.23和39C.15和44 D.25和51适于对动态查找表进行高效率查找的组织结构是__C。A.有序表B.顺序表C.二叉排序树 D,链表设哈希表长为14,哈希函数f(k)=k%11，已知表中已有4个元素，关键字分别为15,38,61,84，存储位置分别为4,5,6,7,其它存储位置为空，如用二次探测再散列处理冲突，关键字为49的存储位置是___D___。A.8359A.8359用某种排序方法对关键字序列(23,72,21,47,15,27,59,35,20)进行排序时，前三趟的结果情况如下23,21,47,152759,3520,7221,23,1527357221,1523,27357223,21,47,152759,3520,7221,23,1527357221,1523,273572则所采用的排序方法是.B.起泡排序A.B.起泡排序C.归并排序D.C.归并排序在对n个元素进行简单选择排序的过程中，需要进行―B—趟选择和交换。A.n/2B.n-1C.nD.n+1若一组记录的排序码为(46,79,56,38,40,84)，则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为C38,40,46,56,79,8440,38,46, 79,56,8440,38,46, 56,79,8440,38,46,84,56,79对于哈希函数H(key)=key%13，被称为同义词(即冲突)的关键字是—DA.35和41 B.23和39C.15和44 D.25和51若对n个元素进行直接插入排序，在进行i趟(2WiWn)排序时，为寻找插入位置最多需要进行 C 次元素的比较。A.i+1B.i-1C.iD.1在对n个元素进行快速排序的过程中，第一趟排序最多需要交换__B对元素。A.n/2 B.n-1 C.n D.n+1在对n个元素进行简单选择排序的过程中，需要进行___B___趟选择和交换。A.n/2 B.n-1 C.n D.n+1堆的形状是一棵___A。A.二叉排序树 B.满二叉树C.完全二叉树 D.平衡二叉树对于哈希函数H(key)=key%13,被称为同