数据结构考习题

1、精心整理、单项选择1 .数据结构是一门研究非数值计算的程序设计问题中，数据元素的g数据信息在计算机中的a以及一组相关的运算等的课程。5a.操作对象B.计算方法C.逻辑结构D,数据映象A.存储结构B.关系C.运算D.算法2 .以下数据结构中，)是线性结构。A.广义表B.二叉树C.稀疏矩阵D.用3 .从逻辑上可以把数据结构分为C两大类。A.动态结构和静态结构B而结构和链式结构C,线性结构和非线性结构D.初等结构和构造型结构4 .以下数据结构中，D_是线性结构。A.广义表B.二叉树C.稀疏矩阵D.用5 .以下数据结构中，»是非线性结构。A.栈B.二叉树C.队列D.字符串6 .数据结构DS(

2、DataStruct)可以被形式地定义为DS=(D,R),其中D是B的有限集合，R是D上的2有限集合。A.算法B.数据元素C.数据操作D.数据对象A.操作B.映象C.存储D.关系7 .线性表的顺序存储结构是一种A的存储结构，线性表的链式存储结构是一种的存储结构。A.随机存取B.顺序存取C.索引存取D.散列存取8 .线性表的逻辑顺序与存储顺序总是一致的，这种说法BA.正确B.不正确.;9 .下面那一条是顺序存储结构的优点？(A)A.存储密度大B.插入运算方便C.删除运算方便D.可以方便的用于各种逻辑结构的存储表示10 .线性表采用链式存储结构时，要求内存中可用的存储单元的地址二A.必须是连续的B

3、.部分地址必须是连续的C.一定不连续D.连续和不连续都可以11 .表长为n的顺序存储的线性表，当在任何位置上插入和删除一个元素的概率相等时，插入一个元素所需要移动元素的平均次数为&删除一个元素所需要移动元素的平均次数为AA.(n-1)/2B.nC.n+1D.n-1E.n/2F.(n+1)/2G.(n-2)/212 .带头结点的单链表head为空的判定条件是B。A.head=NULLB.head->next=NULLC.head->next=headD.head!=NULL13 .在一个单链表中，若删除p所指向结点白后继结点，则执行_AoA.p->next=p->

4、next->nextB.p=p->next;p->next=p->next->nextC.p=p->next->nextD.p=p->next14 .若已知一个栈的入栈序列是1,2,3,，n,其输出序列为p1,p2,p3,，pn,若p1=n,贝Upi为C。A.iB.n=iC.n-i+1D.不确定15 .设栈的输入次序为：1,2,3,4,5,则不可能是其出栈序列一A.54321B.45321C.43512D.12345精心整理16 .一个递归算法必须包括BA.递归部分B.终止条件和递R部分C.迭代部分D.终止条件和迭代部分17 .用链接方式存储的队

5、列，在进行删除操作时DA仅修改头指针B.仅修改尾指针C.头尾指针都要修改D.头尾指针可能都要修改18 .数组Am存放循环队列的元素，其头尾指针分别是front和rear,则当前队列的元素个数是_A_0A.(rear-front+m)%mB.(front-rear+m)%mC.front-rear+1D.rear-front+119 .栈和队列的共同特点_C_A.都是先进先出B.都是先进后出C.允许在端点插入和删除元素D.没有共同点20 .一个栈的入栈序列a,b,c,d,e,则栈的输出序列是_A_>A.edcbaB.decbaC.dceabD.abcde21 .栈的特点是_B一队列的特点是

6、_A_。A.先进先出B.先进后出22 .从一个栈顶指针HS的链表中删除一个结点，用x保存被删除的结点值，执行的语句为_CA.x=HS;HS=HS->nextB.HS=HS->next;x=HS->dataC.x=HS->data;HS=HS->nextD.HS->next=HS;x=HS->data23 .在链队列Q中，插入s所指向的结点执行的语句为_CA.Q.front->next=s;B.Q.rear->next=s;Q.rear=sC.s->next=Q.rear;Q.rear=sD.s->next=Q.front;Q.f

7、ront=s24 .空用与空格用是相同的，这种说法_BA.正确B.不正确25 .下面关于用的叙述，哪一个是不正确的_BA.用是字符的有限序列B.空用是由空格构成的用C.匹配模式是用的一种重要运算D.用可以采用链式存储结构26 .设有两个用p和q,求q在p中首次出现的位置的运算称作_BA.连接B.模式匹配C.求子用D.求出长27 .若用s='software',其子用的数目为BA.8B.37C.36D.928 .二维数组A中，每个元素A的长度为3个字节，行下标i从0到7,列下标j从0到9,从首地址SA开始连续存放在存储器内，该数组按行存放时，数组元素A74的起始地址为_C_A.S

8、A+141B.SA+144C.SA+222D.SA+22529 .对稀疏矩阵进行压缩存储的目的是_C_.A.便于进行矩阵运算B.便于输入输出C节省存储空间D.降低运算的时间复杂度30 .在以下叙述中正确的是BA.线性表的线性存储结构优于链表存储结构B.二维数组可以看成是其数据元素为线性表的线性表C.栈的操作方式是先进先出D.队列的操作方式是先进后出31 .广义表(a),a)的表头为C,表尾为C.A.()B.aC.(a)D.(a)32 .已知广义表L=(x,y,z),a,(u,t,w),从L中取出原子项t的运算为_D_>A.Head(Tail(Tail(L)B.Tail(Head(Head

9、(Tail(L)精心整理C.Head(Tail(Head(Tail(L)D.Head(Tail(Head(Tail(Tail(L)33 .树最适合用来表示BA.有序的数据元素B.数乐之间具有分支层次关系的数据C.无序的数据元素D.无太多关系的数据元素34 .如果某二叉树的前根次序遍历结果为stuwv,中序遍历为uwtvs,那么该二叉树的后序为_B_A.uwvtsB.vwutsC.wuvtsD.wutsv35 .某二叉树的前序遍历结点访问顺序是abdgcefh,中序遍历的结点访问顺序是dgbaechf,则其后序遍历的结点访问顺序是_D_>A.bdgcefhaB.gdbecfhaC.bdga

10、echfD.gdbehfca36 .在一非空二叉树的中序遍历序列中，根结点的右边_A_0A.只有右子树上的所有结点B.只有右子树上的部分结点C.只有左子树上的部分结点D.只有左子树上的所有结点37 .设m和n是一棵二叉树上的两个结点，在中序遍历,n在m前的条件是CA.n在m的右方B.n是m的祖先C.n在m的左方D.n是m的子孙38 .深度为5的二叉树至多有_C结点。A.16B.32C.31D.1039 .由权(8,2,5,7)的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度为DA.23B.37C.46D.4340 .利用二叉链表存储树，则根结点的右指针是CA.指向最左孩子B.指向最右孩子C.

11、空D.非空41 .下列存储方式中，哪一个不是树的存储形式？DA.双亲表示法B.孩子链表表示法C.孩子兄弟表示法D.顺序存储表示法42 .在一个无向图中，所有顶点的度数之和等于所有边数的_C。A.1/2B.1C.2D.443 .具有n个顶点和多于n-1条边的无向图区A.有可能是树B.一定不是树C.一定是树D.以上答案都不对44 .具有6个顶点的无向图至少应有A条边才能确保是一个连通图。A.5B.6C.7D.845 .无向图G=(V,E),其中:V=a,b,Gd,e,f),E=(a,b),(a,e),(a,c),(b,e),(Gf),(f,d),(e,d),则对该图进行深度优先遍历，得到的序列为：

12、DA.abecdfB.acfebdC.aebcfdD.aedfcb46 .下述几种排序方法中，要求内存量最大的是_D-A.插入排序B.选择排序C.快速排序D.归并排序47 .排序方法中，从未排序序列中依次取出元素与已排序序列(初始时为空)中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为_C_>A.希尔排序B.起泡排序C.插入排序D.选择排序48 .在待排序的元素序列基本有序的前提下，效率最高的排序方法是_A_0A.插入排序B.选择排序C.快速排序D.归并排序49 .下列排序算法中，哪一个是稳定的排序算法？BA.直接选择排序B.二分法插入排序C.希尔排序D.快速排序50 .将两

13、个各有n个元素的有序表归并成一个有序表，其最少的比较次数AA.nB.2n-1C.2nD.n-1二、填空题1 .算法的五个五个特性是有穷性，确定性，可行性，输入和输出.2 .数据的树型结构和图(网)状结构合称非线性结构.3 .抽象数据类型的定义仅取决干它的一组逻辑特性，而与数据在计算机中的表示和实现无关.精心整理4 .评价算法质量的指标是正确性，易读性，健壮性，高效性.5 .数据结构中评价算法的两个重要指标是:时间复杂度和空间复杂度.6 .分析下面算法(程序段)，的时间复杂度是O(mn)。s=0;for(i=0;i<n;i+)for(j=0;j<m;j+)s+=Bij；7 .当线性表

14、元素的总数基本稳定，且很少进行删除和插入操作时，但是要求以最快的速度存取线性表中的元素，应该采取躯庄存储结构.8 .顺序表中逻辑上相邻的元素的物理位置必定f骁口,而单链表中逻辑上相邻的元素的物理位置不一定相邻.9 .而”结点查找概率相等的情况下,从n个结点的单链表中查找一个结点,平均要访问n/2个结百八、.10 .在单链表中设置头指针的作用是：简化操作，减少边界条件的判断.11 .在单链表中，除首元结点外，任一名击点的存储位置由其直接前驱的指针域指示.12 .对于一个具有n个结点的单链表，在已知p所指向结点后插入一个新结点的时间复杂度是0(1),在值域为给定值的结点后插入一个新结点的时间复杂度

15、为0(n).一一，13 .在双链表中，每个结点有两个指针域，一个指向_前驱结点另一个指向后继结点。14 .根据线性表的链式存储结构中每一结点包含的指针个数，将线性表分成单链表和多重链表.15 .在非空双向链表中，在结点q的前面插入结点p的过程如下，请补充p->prior=q->prior;q->prior->next=p;p->next=q;q->prior=p;16 .一般情况下，将递归算法转换成等价的非递归算法应该设置栈_.17 .在解决计算机主机与打印机速度不匹配问题时，通常设置一个打印数据缓冲区，该缓冲区通常是一个队列数据结构.18 .循环队列的引入

16、，目的是为了克服假溢出现象.19 .在栈顶指针为HS的链栈中，判断栈空的条件是HS=NULL.20 .在具有n个单元的循环队列中，如果不专门设置队满标志，则队满时共n-1有个元素.21 .实现字符串拷贝的函数如下，请补足Voidstrcpy(char*s,char*t)while(*s+=*t+)!='0');22 .空格用是由一个或多个空格字符组成的用,其长度等于其包含的空格个数。23 .空串是不包含任何字符的用，其长度为历24 .设s='IAMASTUDENT'其长度为：区25 .组成用的元素只能是：W.26 .设s1='Good',s2=&

17、quot;,s3='bye!',贝Us1,s2和s3连接的结果是Goodbye!27 .若广义表中每个元素都是原子时，广义表便成为线性表.28 .广义表的表尾是指除第一个元素外，剩余元素组成的表.29 .广义表A=(a,b,c,d)的表头为(a,b,c,d),表尾为().30 .数组的存储结构采用顺序存储方式.31 .设二维数组a0.5,0.6,其每个字节占5个字节，第一个元素的存储地址为1000，若按列存储,则元素a5,5存储地址为1175.32 .高度为k的完全二叉树至少有2g个叶子结点.33 .若一棵二叉树有50个叶子结点，则该二叉树的总结点数至少是99.精心整理34 .

18、有n个叶子结点的哈夫曼树的结点总数为2n-1.35 .根据二叉树的定义，具有三个结点的二叉树有4种.36 .某棵二叉树的中序遍历序列为abcdefg,后序遍历序列为bdcafge,则该二叉树的前序遍历序列eacbdgf,该二叉树对应的森林包含2_棵二叉树.37 .若二叉树采用二叉链表存储结构，要受换其所有分支结点的左,右子树的位置,利用中序遍历方法最为合适.38 .线索二叉树的左线索指向其前驱，右线索指向其后继.39 .树所对应的二叉树其根结点的右王树一定为空.40 .利用树的孩子兄弟表示法存储，可以将一棵树转化成二叉树.41 .设无向图的顶点个数为n,则该图最多有n(n-1)/2条边.42

19、.n个顶点的连通图至少有n-1条边.43 .已知一个图用领接矩阵表1"计算第i个结点的入度的方法是求第i列非零元素的和.44 .G是一个非连通的无向图，共有28条边，则该图至少有9个顶点.45 .一个图的邻接矩阵表示法是唯一的,而邻接表表示法是不唯一的。01046 .从邻接矩阵A=101可以看出，该图共有3个顶点，如果是无向图，则共有2条边.-010一47 .n个顶点的连通图用邻接矩阵表示时，则该矩阵至少有2(n-1)个顶点.48 .设图中有n个顶点,e条边，如果用邻接表表示图,进行深度优先搜索遍历的时间复杂度为O(n+e),如果用邻接夕!阵表示图，时间复杂度为O(n2)49 .从平

20、均时间性能而言，快速排序排序最佳.50 .堆排序是一种选择排序,堆实质上是一棵完全二叉树结点的层次序列.对于含有n个元素的排序，堆排序的时间复杂度为O(log2n).所需附加的存储结点是O(T).三、用图表回答下列问题1 .设某通信系统使用A,B,C,D,E,F,GH个字符，出现的频率w=5,29,7,8,14,23,3,11,试构造对应的哈夫曼树(请按左子树根结点的权小于右子树树根结点的权的次序构造)？答案如图：答案如图所44V1vv23v34.画出和35B2.根据下面的邻接链表)画出相应的图，写出每个顶点的度，并用邻接矩阵表示.V1:3V2:2V3:3V4:2V5:4V6:2先根遍历序列V

21、6ABDEGFC答案如图所小：3.精心整理while(p)if(2)(3);m=p->data;(4);p=p->next;q=r->next;(5);free(q);一答案:(1)L->next=NULL;(2)p!=NULL;(3)q!=NULL;(4)p->next=r->next(5)r->next=p.2 .阅读下列算法，说明该算法的作用。Statusalgorithm1(LinkQueue&Q)SqStackStack;QElemTypeElement;InitStack(Stack);while(!QueueEmpty(Q)DeQ

22、ueue(Q,Element);Push(Stack,Element);while(!StackEmpty(Stack)Pop(Stack,Element);EnQueue(Q,Element);答：利用栈实现队列的逆置.3 .阅读下列算法，说明该算法的作用。Statusalgorithm2(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);答:利用辅助栈T,将栈S中的元素e删除.4 .将下面程序改写

23、成递归过程.voidalgohthm3(intn)inti=n;while(i>1)printf(i-);答：voidalgorithm4(intj)if(j>1)printf(j);algorithm4(j-1)5 .阅读下列算法，说明该算法的作用。BiTreealgohthm5(ElemTypePre口,ElemTypeln儿intPreLen,InLen;inti,j;BiTreeBT;ElemType*subPre,*subIn;PreLen=strlen(Pre);InLen=strlen(In);if(PreLen!=InLen|PreLen=0)returnNULL;

24、for(i=0;i<InLen&&Ini!=Pre0;i+);if(i=InLen)returnNULL;BT=(BiTNode*)malloc(sizeof(BiTNode);BT->data=Pre0;subPre=(ElemType*)malloc(i+1)*sizeof(ElemType);subIn=(ElemType*)malloc(i+1)*sizeof(ElemType);for(j=0;j<i;j+)subPrej=Prej+1;subInj=Inj;subPrej='0'subInj='0'BT->lc

25、hild=CreatBT(subPre,subIn);subPre=(ElemType*)malloc(PreLen-i)*sizeof(ElemType);subIn=(ElemType*)malloc(PreLen-i)*sizeof(ElemType);for(j=i+1;j<PreLen;j+)subPrej-i-1=Prej;subIni-1=Inj;subPrej-i-1='0'subInj-i-1='0'BT->rchild=CreatBT(subPre,subIn);returnBT;精心整理答：利用一棵二叉树的先序遍历和中序遍历还原该二叉树.五、算法设计题1 .设顺序表L中的数据元素递增有序.试写一个算法，将e插入顺序表中，要求插入后保持该表的有序性.voidInsertElem(SqList&L,ElemType)j=L.length-1;while(L.elemj>e)L.elemj+