数据构造和C程序设计题库完好.docx

《数据构造和C程序设计题库完好.docx》由会员分享，可在线阅读，更多相关《数据构造和C程序设计题库完好.docx（40页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据构造和C程序设计题库完好（数据构造）Part1一选择1.组成数据的基本单位是A数据项B数据类型C数据元素D数据变量2算法分析的目的是A找出数据构造的合理性B研究算法的输入/输出关系C分析算法的效率以求改良D分析算法的易读性3在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是AO(1)B0(n)CO(n2)DO(nlog2n)4若线性表采用顺序存储构造，每个元素占用4个存储单元，第一个元素的存储地址为100，则第12个元素的存储地址是A112B144C148D4125下面关于线性表的叙述中，错误的是A顺序表使用一维数组实现的线性表B顺序表必须占用一片连续的存储单元.C顺序

2、表的空间利用率高于链表D在单链表中,每个结点只要一个链域.6在需要经常查找结点的前驱与后继的情况下，使用比拟适宜A单链表B双链表C顺序表D循环链表7队列通常采用的两种存储构造是A顺序存储构造和链式存储构造B散列方式和索引方式C链表存储构造和线性存储构造D线性存储构造和非线性存储构造8在一个单链表中，若删除p所指结点的后继结点，则执行Ap-next=p-next-next；Bp=p-next；p-nex=p-next-next；Cp-next=p-next；Dp=p-next-next；9若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用存储方式最节省运算时间A单链

3、表B仅有头指针的单循环链表C双链表D仅有尾指针的单循环链表10按二叉树的定义，具有三个结点的二元树共有种形态。A3B4C5D611任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序A发生改变B不发生改变C不能确定D以上都不对12深度为5的二叉树至多有个结点A16B32C31D1013在一棵度为3的树中，度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，那么度为0的结点数为个。A4B5C6D714对于一个具有n个顶点的无向图，若采用邻接表表示，则存放表头结点的数组(顶点表)的大小为AnBn+1Cn-1Dn/215静态查找表和动态查找表二者的根本差异在于A它们的逻辑构造不

4、同B施加在其上的操作不同C所包含的数据元素的类型不一样D存储实现不一样二填空1某程序的时间复杂性为(3n+nlog2n+n2+8),其数量级表示为_。2线性表L=(a1,a2,an)采用顺序构造存储,假定在不同的位置上插入的概率一样，则插入一个新元素平均需要移动的元素个数是_。3.对于一株具有n个结点的树，该树中所有结点的度数之和为_。4.在一个图中,所有顶点的度数之和等于所有边数的_倍。5.一棵二叉树有67个结点,这些结点的度要么是0，要么是2。这棵二元树中度数为2的结点有_个。6在一个无向图的邻接表中，若表结点的个数是m，则图中边的条数是_。7采用堆排序、快速排序、冒泡排序，对初态有序的表

5、，最省时间的是_。8设二叉树结点的先根序列为ABDECFGH，中根序列为DEBAFCHG,则二元树中叶结点是_.9一个哈夫曼(Huffman)树有19个结点，则其叶结点的个数是_。10.栈S和队列Q的初始状态皆为空,元素a1,a2,a3,a4,a5和a6依次通过S栈，一个元素出栈后即进入队列Q，若6个元素出队列的顺序是a3,a5,a4,a6,a2,a1，则栈S至少应该包容_个元素。三判定1线性表的链式存储构造优于顺序行储构造。2在单链表中，要获得某个元素，只要知道该元素的指针即可，因而，单链表是随机存取的存储构造。3对于n个记录的集合进行归并排序，存最坏的情况下所需要的时间是O(n2)。4表中

6、的每一个元素都有一个前驱和后继元素。5进栈操作push(x，s)作用于链接栈时，无须判满。6只要在初始数据为逆序时，冒泡排序所执行的比拟次数最多。7在索引顺序表查找方法中，对索引顺序表能够使用顺序表查找方法，可以以使用二分查找方法。8数据元素是数据的最小单位。9顺序存储方式的优点是存储密度大，且插入、删除运算效率高。10按中序遍历一棵二叉排序树所得到的中序遍历序列是一个递增序列。四简答1.对于下列图所示的树：(1)写出先序遍历得到的结点序列；(2)画出转换后得到的二叉树。2请画出与下列二元树对应的森林。五算法设计1已知一个int类型的数组arra，其长度为n，要求用冒泡排序算法对其从小到大排序

7、，请实现该算法，要求后面开场循环，大的数值下沉。2利用一个栈实现下面递归函数的非递归计算：Pn(x)=?=-11)()1(2)(22121nnnxPnxxPxnnPart2一、单项选择1、在数据构造的讨论中把数据构造从逻辑上分为A内部构造与外部构造B静态构造与动态构造C线性构造与非线性构造D紧凑构造与非紧凑构造。2、算法分析的目的是A找出数据构造的合理性B研究算法中输入和输出的关系C分析算法的效率以求改良D分析算法的易懂性和文档性3、在一个单链表中，若q结点是p结点的前驱结点，若在q与p之间插入结点s，则执行Aslink=plink;plink=s;Bplink=s;slink=q;Cplin

8、k=slink;slink=p;Dqlink=s;slink=p;4、假如想在4092个数据中只需要选择其中最小的5个，采用方法最好。A起泡排序B堆排序C锦标赛排序D快速排序5、设有两个串t和p，求p在t中初次出现的位置的运算叫做。A求子串B形式匹配C串替换D串连接6、将一个递归算法改为对应的非递归算法时，通常需要使用。A栈B队列C循环队列D优先队列7、在循环队列中用数组A0.m-1存放队列元素，其队头和队尾指针分别为front和rear，则当前队列中的元素个数是。A(front-rear+1)%mB(rear-front+1)%mC(front-rear+m)%mD(rear-front+m

9、)%m8、下面程序段的时间复杂度为for(inti=0;ilink=p;p-link=s;Bs-link=p-link;p-link=s;Cs-link=p-link;p=s;Dp-link=s;s-link=p;10、当利用大小为n的数组顺序存储一个队列时，该队列的最大长度为An-2Bn-1CnDn+111、某二叉树的前序和后序序列正好相反，则该二叉树一定是的二叉树。A空或只要一个结点B高度等于其结点数C任一结点无左孩子D任一结点无右孩子12、对于任何一棵二叉树T，假如其终端结点数为n0，度为2的结点为n2，则()An0=n2+1Bn2=n0+1Cn0=2n2+1Dn2=2n0+113、由权

10、值分别为11，8，6，2，5的叶子结点生成一棵哈夫曼树，它的带权途径长度为A24B73C48D5314、对线性表进行折半搜索时，要求线性表必须A以链接方式存储且结点按关键码有序排列B以数组方式存储C以数组方式存储且结点按关键码有序排列D以链接方式存储15、顺序搜索算法合适于存储构造为的线性表。A散列存储B顺序存储或链接存储C压缩存储D索引存储二、填空1、数据的存储构造被分为、四种。2、一种抽象数据类型包括和两个部分。3、栈、队列逻辑上都是构造。4、栈中存取数据的原则，队列中存取数据的原则。5、设目的串T=abccdcdccbaa,形式P=cdcc则第次匹配成功。三、判定1、数据的逻辑构造是指各

11、数据元素之间的逻辑关系，是用户按使用需要建立的。()2、线性表的逻辑顺序与物理顺序总是一致的。3、每种数据构造都应具备三种基本运算：插入、删除、搜索。4、深度为h的非空二叉树的第h层最多有2h-1个结点。5、完全二叉树就是满二叉树。6、最优二叉搜索树一定是平衡的二叉搜索树。7、线性表中所有结点的类型必须一样。8、连通分量是无向图中的极小连通子图。9、空串与由空格组成的串没有区别。10、带权连通图的最小生成树的权值之和一定小于它的其它生成树的权值之和。四、简答1、在结点个数为n(n1)的各棵树中，高度最小的树的高度是多少？它有多少个叶结点？多少个分支结点？高度最大的树的高度是多少？它有多少个叶结

12、点？多少个分支结点？2、将下面的森林变换成二叉树。3、有图如下，请画出其邻接多重表。当前位置：文档视界数据构造和C程序设计题库完好数据构造和C程序设计题库完好DataTypedataMaxsize;Intfront,rear;Queue;若有一个Queue类型的队列Q，试问判定队列满的条件应是下列哪一个语句A)Q.front=Q.rear;B)Q.front-Q.rear=Maxsize;C)Q.front+Q.rear=Maxsize;D)Q.front=(Q.rear+1)%Maxsize;8、在循环队列中用数组A0.m-1存放队列元素，其队头和队尾指针分别为front和rear，则当前队

13、列中的元素个数是。A)(front-rear+1)%mB)(rear-front+1)%mC)(front-rear+m)%mD)(rear-front+m)%m9、将一个递归算法改为对应的非递归算法时，通常需要使用。A)栈B)队列C)循环队列D)优先队列10、下列广义表是线性表的有A)Ea,(b,c)B)E(a,E)C)E(a,b)D)E(a,L()11、设有两个串t和p，求p在t中初次出现的位置的运算叫做。A)求子串B)形式匹配C)串替换D)串连接12、对于任何一棵二叉树T，假如其终端结点数为n0，度为2的结点为n2.,则()A)n0=n2+1B)n2=n0+1C)n0=2n2+1D)n2

14、=2n0+113、由权值分别为11，8，6，2，5的叶子结点生成一棵哈夫曼树，它的带权途径长度为A)24B)73C)48D)5314、对线性表进行折半搜索时，要求线性表必须A)以链接方式存储且结点按关键码有序排列B)以数组方式存储C)以数组方式存储且结点按关键码有序排列D)以链接方式存储15静态查找表和动态查找表二者的根本差异在于A它们的逻辑构造不同B施加在其上的操作不同C所包含的数据元素的类型不一样D存储实现不一样二判定1、数据元素是数据的最小单位。2、数据构造是指互相之间存在一种或多种关系的数据元素的全体。3、线性表的逻辑顺序与物理顺序总是一致的4、每种数据构造都应具备三种基本运算：插入、

15、删除、搜索。5、空串与由空格组成的串没有区别。6、深度为h的非空二叉树的第h层最多有2h-1个结点7、完全二叉树就是满二叉树。8、最优二叉搜索树一定是平衡的二叉搜索树。9、快速排序是对起泡排序的一种改良。()10、B-树是一种动态索引构造，它既适用于随机搜索，也适用于顺序搜索。三简答1、已知一棵二叉树的前序遍历的结果是ABECDFGHIJ,中序遍历的结果是EBCDAFHIGJ。1试画出这棵二叉树；2给出这棵二叉树的后序遍历序列。2、已知一颗树如下列图所示，请用孩子兄弟存储表示法表示该树。四算法设计已知一个int类型的数组arra，其长度为n，要求用冒泡排序算法对其从小到大排序，请实现该算法，要

16、求后面开场循环，大的数值下沉。Part4一、单项选择2、在数据构造的讨论中把数据构造从逻辑上分为A)内部构造与外部构造B)静态构造与动态构造C)线性构造与非线性构造D)紧凑构造与非紧凑构造。2、下面程序段的时间复杂度为intf(unsignedintn)if(n=0|n=1)return1;elsereturnn*f(n-1);A)O(1)B)O(n)C)O(n2)D)O(n!)3、一个数组元素ai与的表示等价。A)*a+iB)a+iC)*a+iD)&a+i4、若需要利用形参直接访问实参，则应把形参变量讲明为参数。A)指针B)引用C)值D)变量5、在数组A中，每一个数组元素Aij占用3个存储字

17、，行下标i从1到8，列下标j从1到10。所有数组元素相继存放于一个连续的存储空间中，则存放该数组至少需要的存储字数是。A)80B)100C)240D)2706、在一个长度为n的顺序存储的线性表中，删除第i个元素1in时，需要从前向后依次前移()个元素。A)1-iB)n-i+1C)nj-1D)i7、设单链表中结点构造为(data,link).已知指针q所指结点是指针p所指结点的直接前驱，若在*q与*p之间插入结点*s，则应执行下列哪一个操作A)s-link=p-link;p-link=s;B)q-link=s;s-link=pC)p-link=s-link;s-link=p;D)p-link=s

18、;s-link=q;8、设单循环链表中结点的构造为data,link,且first为指向链表表头的指针，current为链表当前指针，在循环链表中检测current能否到达链表表尾的语句是()。A)current-link=nullB)first-link=currentC)first=currentD)current-link=first9、一个栈的入栈序列为a，b，c，则出栈序列不可能的是()。A)c,b,aB)b,a,cC)c,a,bD)a,c,b10、设链式栈中结点的构造为data,link,且top是指向栈顶的指针。若想摘除链式栈的栈顶结点，并将被摘除结点的值保存到x中，则应执行下列

19、操作。A)x=top-data;top=top-link;B)top=top-link;x=top-data;C)x=top;top=top-link;D)x=top-data;11、假定一个顺序存储的循环队列的队头和队尾指针分别为f和r,则判定队空的条件为()。A)f+1=rB)r+1=fC)f=0D)f=r12、当利用大小为n的数组顺序存储一个队列时，该队列的最大长度为A)n-2B)n-1C)nD)n+113、某二叉树的前序和后序序列正好相反，则该二叉树一定是的二叉树。A)空或只要一个结点B)高度等于其结点数C)任一结点无左孩子D)任一结点无右孩子14、顺序搜索算法合适于存储构造为的线性表

20、。A)散列存储B)顺序存储或链接存储C)压缩存储D)索引存储15、判定一个有向图能否存在回路，除了能够利用拓扑排序方法外，还能够利用。A)求关键途径的方法B)求最短途径的Dijkstra方法C)深度优先遍历算法D)广度优先遍历算法二、判定1、从逻辑关系上讲，数据构造主要分为两大类：线性构造和非线性构造。2、每种数据构造都应具备三种基本运算：插入、删除、搜索。3、非空线性表中任意一个数据元素都有且仅有一个直接前驱元素。4、将T在S中初次出现的位置作为T在S中的位置的操作称为串的形式匹配。5、已知一棵二叉树的前序序列和中序序列能够唯一地构造出该二叉树。6、线性表的顺序存储构造的特点是逻辑关系上相邻

21、的两个元素在物理位置上也相邻。7、用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中顶点个数有关，而与图的边数无关。8、邻接表只能用于有向图的存储，邻接矩阵对于有向图和无向图的存储都适用。9、连通分量是无向图中的极小连通子图。10、快速排序是对起泡排序的一种改良。()三、1、某子系统在通信联络中只可能出现8种字符，其出现的概率分别为0.05，0.29，0.07，0.08，0.14，0.23，0.03，0.11试设计赫夫曼编码。2、将下面的森林变换成二叉树。四算法设计已知一个int类型的数组arra，其长度为n，要求用选择排序算法对其从小到大排序，请实现该算法。（面向

22、对象程序设计C+）Part1一、单项选择1.下面对于指针的描绘不正确的是()。A.指针是地址变量B.指针不能用除0以外的常量赋值C.两个指针变量的加减法无意义D.指针指向不同基类型的变量长度不同2.下面对于析构函数的描绘中不正确的是()。A.析构函数是内置函数B.析构函数与类名一样C.析构函数不能有参数D.析函数在对象撤销时自动执行3.下列指针用法中错误的是()。A.inti;int*ptr=&i;B.inti;int*ptr;i=*ptr;C.int*ptr;ptr=0;D.inti=5;int*ptr;*ptr=i;4.派生类的对象对它的基类成员中什么是可访问的()?A.公有继承的公有成员

23、B.公有继承的私有成员C.公有继承的保护成员D.私有继承的公有成员5.在()情况下适宜采用inline定义内联函数。A.函数体含有循环语句B.函数体含有递归语句C.需要加快程序的执行速度D.函数代码多、不常调用6.在类中讲明的成员能够使用关键字()进行修饰。A.publicB.externC.cpuD.register7.假如类A被讲明成类B的友元，则()。A.类A的成员即类B的成员B.类B的成员即类A的成员C.类A的成员函数不得访问类B的成员D.类B不一定是类A的友元8.定义析构函数时，应该注意()。A.其名与类名完全一样B.返回类型是void类型C.无形参，也不可重载D.函数体中必须有delete语句9.在类中声明一般函数时不能指定()。A.参数B.访问权限C.操作D.标识符10.在派生类中重新定义虚函数时必须在()方面与基类保持一致。A.参数类型B.参数名字C.操作内容D.返回值类型11.设inta=3,b=4,c=5;表达式(a+b)c&b=c的值是()。A.2B.-1C.0D.112.下列标识符中，不合法的用户标识符为()。A.a#bB._intC.a_10D.PAd13.while(!x)中的(!x)与下面条件()等价。A.x1B.x!=1