题集2_数据结构试题一份

数据结构试题一、单选题1、在数据结构的讨论中把数据结构从逻辑上分为（C）A内部结构与外部结构B静态结构与动态结构C线性结构与非线性结构D紧凑结构与非紧凑结构。2、采用线性链表表示一个向量时，要求占用的存储空间地址（D）A必须是连续的B部分地址必须是连续的C一定是不连续的D可连续可不连续3、采用顺序搜索方法查找长度为n的顺序表时，搜索成功的平均搜索长度为（D）。AnBn/2C(n-1)/2D(n+1)/24、在一个单链表中，若q结点是p结点的前驱结点，若在q与p之间插入结点s，则执行（D）。As→link=p→link;p→link=s;Bp→link=s;s→link=q;Cp→link=s→link;s→link=p;Dq→link=s;s→link=p;5、如果想在4092个数据中只需要选择其中最小的5个，采用（C）方法最好。A起泡排序B堆排序C锦标赛排序D快速排序6、设有两个串t和p，求p在t中首次出现的位置的运算叫做（B）。A求子串B模式匹配C串替换D串连接7、在数组A中，每一个数组元素A[i][j]占用3个存储字，行下标i从1到8，列下标j从1到10。所有数组元素相继存放于一个连续的存储空间中，则存放该数组至少需要的存储字数是（C）。A80B100C240D2708、将一个递归算法改为对应的非递归算法时，通常需要使用（A）。A栈B队列C循环队列D优先队列9、一个队列的进队列顺序是1,2,3,4，则出队列顺序为（C）。10、在循环队列中用数组A[0..m-1]存放队列元素，其队头和队尾指针分别为front和rear，则当前队列中的元素个数是（D）。A(front-rear+1)%mB(rear-front+1)%mC(front-rear+m)%mD(rear-front+m)%m注意：A[0]总为空，数据从A[1]开始存放。11、一个数组元素a[i]与（A）的表示等价。A*（a+i）Ba+iC*a+iD&a+i12、若需要利用形参直接访问实参，则应把形参变量说明为（B）参数。A指针B引用C值D变量13、下面程序段的时间复杂度为（C）for(inti=0;im;i++)for(intj=0;jn;j++)a[i][j]=i*j;AO(m2)BO(n2)CO(m*n)DO(m+n)注意：时间复杂度：循环体执行次数。14、下面程序段的时间复杂度为（B）intf(unsignedintn){if(n==0||n==1)return1;elsereturnn*f(n-1);//递归}AO(1)BO(n)CO(n2)DO(n!)15、线性表若是采用链式存储结构时，要求内存中可用存储单元的地址(D)。A必须是连续的B部分地址必须是连续的C一定是不连续的D连续或不连续都可以16、数据结构的定义为(D，S)，其中D是(B)的集合。A算法B数据元素C数据操作D逻辑结构17、算法分析的目的是(A)。A找出数据结构的合理性B研究算法中输入和输出的关系C分析算法的效率以求改进D分析算法的易懂性和文档性18、在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行(B)。As-link=p;p-link=s;Bs-link=p-link;p-link=s;Cs-link=p-link;p=s;Dp-link=s;s-link=p;19、设单链表中结点结构为(data,link).已知指针q所指结点是指针p所指结点的直接前驱，若在*q与*p之间插入结点*s，则应执行下列哪一个操作（B）As-link=p-link;p-link=s;Bq-link=s;s-link=pCp-link=s-link;s-link=p;Dp-link=s;s-link=q;20、设单链表中结点结构为(data,link).若想摘除结点*p的直接后继，则应执行下列哪一个操作（A）Ap-link=p-link-link;Bp=p-link;p-link=p-link-link;Cp-link=p-link;Dp=p-link-link;21、设单循环链表中结点的结构为（data,link）,且rear是指向非空的带表头结点的单循环链表的尾结点的指针。若想删除链表第一个结点，则应执行下列哪一个操作（D）As=rear;rear=rear-link;deletes;Brear=rear-link;deleterear;Crear=rear-link-link;deleterear;Ds=rear-link-link;rear-link-link=s-link;deletes;s为第一个结点（循环结构，链表表头为一个空结点）22、设单循环链表中结点的结构为（data,link）,且first为指向链表表头的指针，current为链表当前指针，在循环链表中检测current是否达到链表表尾的语句是(D)。Acurrent-link=nullBfirst-link=currentCfirst=currentDcurrent-link=first？23、一个栈的入栈序列为a，b，c，则出栈序列不可能的是(C)。Ac,b,aBb,a,cCc,a,bDa,c,b24、栈的数组表示中，top为栈顶指针，栈空的条件是(D)。Atop=0Btop=maxSizeCtop=maxSizeDtop=-125、栈和队列的共同特点是(C)。A都是先进后出B都是先进先出C只允许在端点处插入和删除D没有共同点26、假定一个顺序存储的循环队列的队头和队尾指针分别为f和r,则判断队空的条件为(D).Af+1==rBr+1==fCf==0Df==r27、当利用大小为n的数组顺序存储一个队列时，该队列的最大长度为（B）An-2Bn-1CnDn+128、当利用大小为n的数组顺序存储一个栈时，假定用top==n表示栈空，则向这个栈插入一个元素时，首先应执行（）语句修改top指针。Atop++;Btop--;Ctop=0;Dtop;29、设链式栈中结点的结构为（data,link）,且top是指向栈顶的指针。若想摘除链式栈的栈顶结点，并将被摘除结点的值保存到x中，则应执行下列（A）操作。Ax=top-data;top=top-link;Btop=top-link;x=top-data;Cx=top;top=top-link;Dx=top-data;30、设循环队列的结构是：constintMaxsize=100;typedefintDataType;typedefstruct{DataTypedata[Maxsize];Intfront,rear;}Queue;若有一个Queue类型的队列Q，试问判断队列满的条件应是下列哪一个语句（D）AQ.front==Q.rear;BQ.front-Q.rear==Maxsize;CQ.front+Q.rear==Maxsize;DQ.front==(Q.rear+1)%Maxsize;31、设有一个递归算法如下：intfact(intn){if(n=0)return1;elsereturnn*fact(n-1);}下面正确的叙述是（B）A计算fact(n)需要执行n次递归Bfact(7)=5040C此递归算法最多只能计算到fact(8)D以上结论都不对32、设有一个递归算法如下intx(intn){if(n=3)return1;elsereturnx(n-2)+x(n-4)+1;}试问计算x(x(8))时需要计算（D）次x函数。A8次B9次C16次D18次33、设有广义表D(a,b,D),其长度为（B），深度为（A）A∞B3C2D534、广义表A(a),则表尾为（C）AaB(())C空表D（a）35、下列广义表是线性表的有（C）AE（a,(b,c)）BE(a,E)CE(a,b)DE(a,L())36、递归表、再入表、纯表、线性表之间的关系为（C）A再入表递归表纯表线性表B递归表线性表再入表纯表C递归表再入表纯表线性表D递归表再入表线性表纯表37、某二叉树的前序和后序序列正好相反，则该二叉树一定是（B）的二叉树。A空或只有一个结点B高度等于其结点数C任一结点无左孩子D任一结点无右孩子38、对于任何一棵二叉树T，如果其终端结点数为n0，度为2的结点为n2.,则(A)An0=n2+1Bn2=n0+1Cn0=2n2+1Dn2=2n0+139、由权值分别为11，8，6，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（B）A24B71C48D5340、已知一个顺序存储的线性表，设每个结点需占m个存储单元，若第一个结点的地址为da1,则第I个结点的地址为（A）。Ada1+(I-1)*mBda1+I*mCda1-I*mDda1+(I+1)*m41、具有35个结点的完全二叉树的深度为(A)A5B6C7D8解析：2k-1≥n42、对线性表进行折半搜索时，要求线性表必须（C）A以链接方式存储且结点按关键码有序排列B以数组方式存储C以数组方式存储（顺序存储）且结点按关键码有序排列D以链接方式存储43、顺序搜索算法适合于存储结构为（B）的线性表。A散列存储B顺序存储或链接存储C压缩存储D索引存储44、采用折半搜索算法搜索长度为n的有序表时，元素的平均搜索长度为（C）AO（n2）BO（nlog2n）CO（log2n）DO（n）45、对于一个具有n个顶点和e条边的无向图，进行拓扑排序时，总的时间为(A)AnBn+1Cn-1Dn+e46、判断一个有向图是否存在回路，除了可以利用拓扑排序方法外，还可以利用（C）。A求关键路径的方法B求最短路径的Dijkstra方法C深度优先遍历算法D广度优先遍历算法47、在10阶B-树中根结点所包含的关键码个数最多为（C），最少为(A)A1B2C9D1048、对包含n个元素的散列表进行搜索，平均搜索长度为（C）AO（log2n）BO（n）C不直接依赖于nD上述都不对二、填空题（）1、数据的逻辑结构被分为集合结构、线性结构、树形结构、图形结构四种2、数据的存储结构被分为顺序存储结构、链式存储结构、索引存储结构、哈希（或散列）存储结构四种3、一种抽象数据类型包括（数据）和（操作）两个部分。4、设有两个串p和q，求p在q中首次出现的位置的运算称为（模式匹配）5、栈、队列逻辑上都是（线性）结构。6、线性结构反映结点间的逻辑关系是（一对一）的，图中的数据元素之间的关系是（多对多）的，树形结构中数据元素间的关系是（一对多）的。7、栈中存取数据的原则（后进先出），队列中存取数据的原则（先进先出）8、串是由（零个或多个）字符组成的序列。（长度为零的串）称为空串，（由一个或多个空格组成的串）称为空格串。9、设目标串T=”abccdcdccbaa”,模式P=”cdcc”则第（6）次匹配成功。10、一维数组的逻辑结构是（线性结构），存储结构是（顺序存储表示）。对于二维数组，有（行优先顺序）和（列优先顺序）两种不同的存储方式，对于一个二维数组A[m][n],若采用按行优先存放的方式，则任一数组元素A[i][j]相对于A[0][0]的地址为（n*i+j）。11、向一个顺序栈插入一个元素时，首先使（栈顶指针）后移一个位置，然后把待插入元素（写）到这个位置上。从一个顺序栈删除元素时，需要前移一位（栈顶指针）。12、在一个循环队列Q中，判断队空的条件为（Q.front==Q.rear）,判断队满的条件为（(Q.rear+1)%MaxSize==q.front）13、对于一棵具有n个结点的树，该树中所有结点的度数之和为（n-1）。（因为只有根结点没有指向它的树枝）14、一棵高度为5的满二叉树中的结点数为（63）个，一棵高度为4满四叉树中的结点数为（85）个。高度为h的满m叉树的结点总数N=mh-1+mh-2...+m1+m015、若对一棵二叉树从0开始进行结点编号，并按此编号把它顺序存储到一维数组中，即编号为0的结点存储到a[0]中，其余类推，则a