《数据结构和C程序设计题库完整.docx》由会员分享，可在线阅读，更多相关《数据结构和C程序设计题库完整.docx（20页珍藏版）》请在三一办公上搜索。
1、数据结构Parti一. 选择1. 组成数据的基本单位是（）A）数据项 B）数据类型C）数据元素D）数据变量2算法分析的目的是（）A）找出数据结构的合理性B）研究算法的输入/输出关系C）分析算法的效率以求改进D）分析算法的易读性3在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是（）A） O（1） B） 0（n）C） O（n2） D） O（nlog2n）4 若线性表采用顺序存储结构，每个元素占用4个存储单元，第一个元素的存储地址为100， 则第12个元素的存储地址是（）A） 112 B） 144C） 148 D） 4125下面关于线性表的叙述中，错误的是（）A）顺序表使用一维
2、数组实现的线性表 B）顺序表必须占用一片连续的存储单元.C）顺序表的空间利用率高于链表 D）在单链表中，每个结点只有一个链域.6在需要经常查找结点的前驱与后继的情况下，使用（）比较合适A）单链表 B）双链表 C）顺序表 D）循环链表7队列通常采用的两种存储结构是（）A）顺序存储结构和链式存储结构B）散列方式和索引方式C）链表存储结构和线性存储结构D）线性存储结构和非线性存储结构8在一个单链表中，若删除p所指结点的后继结点，则执行（）A ） p-next=p-next-next ；B ） p=p-next ； p-nex=p-next-next ；C） p-next=p-next ；D） p=p
3、-next-next ；9若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则 采用（）存储方式最节省运算时间A）单链表 B）仅有头指针的单循环链表C）双链表D）仅有尾指针的单循环链表10 按二叉树的定义，具有三个结点的二元树共有（）种形态。A）3B）4C）5D）611 任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序（）A）发生改变B）不发生改变C）不能确定D）以上都不对12 深度为5的二叉树至多有（）个结点A） 16B） 32C） 31D） 1013 在一棵度为3的树中，度为3的结点数为2个，度为2的结点数为1个，度为1的结点 数为2个，那么度为0的结点
4、数为（）个。A） 4B） 5C） 6D） 714 对于一个具有n个顶点的无向图，若采用邻接表表示，则存放表头结点的数组（顶点表） 的大小为（）A） nB） n+1C） n-1D） n/215静态查找表和动态查找表二者的根本差别在于（）A）它们的逻辑结构不同B）施加在其上的操作不同C）所包含的数据元素的类型不一样D）存储实现不一样二填空1 某程序的时间复杂性为（3n+nlog2n+n9 一个哈夫曼（Huffman）树有19个结点，则其叶结点的个数 。10.栈S和队列Q的初始状态皆为空，元素a1,a2,a3,a4,a5和a6依次通过S栈，一个元素出 栈后即进入队列Q，若6个元素出队列的顺序是a3,
5、a5,a4,a6,a2,a1，则栈S至少应该容纳 个元素。三判断 线性表的链式存储结构优于顺序行储结构。（） 2在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取 的存储结构。（） 对于n个记录的集合进行归并排序，存最坏的情况下所需要的时间是0（2）。（） 表中的每一个元素都有一个前驱和后继元素。（） 进栈操作push（x，s）作用于链接栈时，无须判满。（） 只有在初始数据为逆序时，冒泡排序所执行的比较次数最多。（） 在索引顺序表查找方法中，对索引顺序表可以使用顺序表查找方法，也可以使用二分查 找方法。（） 数据元素是数据的最小单位。（） 顺序存储方式的优点是存储密度
6、大，且插入、删除运算效率高。（）10 按中序遍历一棵二叉排序树所得到的中序遍历序列是一个递增序列。（）四简答1. 对于下图所示的树：（1）写出先序遍历得到的结点序列；（2）画出转换后得到的二叉树。+8）,其数量级表示为。2线性表L=（a1,a2,，an ）采用顺序结构存储，假定在不同的位置上插入的概率相同，则插 入一个新元素平均需要移动的元素个数 。3. 对于一株具有n个结点的树，该树中所有结点的度数之和为。4. 在一个图中，所有顶点的度数之和等于所有边数的 倍。5. 一棵二叉树有67个结点，这些结点的度要么是0，要么是2。这棵二元树中度数为2的结点有 个。6 在一个无向图的邻接表中，若表结点
7、的个数是m，则图中边的条数是。7采用堆排序、快速排序、冒泡排序，对初态有序的表，最省时间的 。8 设二叉树结点的先根序列为 ABDECFGH，中根序列为DEBAFCHG,则二元树中叶结点是2请画出与下列二元树对应的森林。五算法设计1 已知一个int类型的数组arra，其长度为n，要求用冒泡排序算法对其从小到大排序， 请实现该算法，(要求后面开始循环，大的数值下沉)。2利用一个栈实现以下递归函数的非递归计算：1 = 0P n (x)=2xn = 12xP (x ) - 2(n -1)P (x) n 1n-1n 一 2Part2一、单项选择1、在数据结构的讨论中把数据结构从逻辑上分为（）A）内部结
8、构与外部结构C）线性结构与非线性结构2、算法分析的目的是（）A）找出数据结构的合理性C）分析算法的效率以求改进B）静态结构与动态结构D）紧凑结构与非紧凑结构。B）研究算法中输入和输出的关系D）分析算法的易懂性和文档性3、在一个单链表中，若q结点是p结点的前驱结点，若在q与p之间插入结点s，则执行 （）A） sFink =pFink;plink = s;B）pFink = s;sFink = q;C）pFink =sFink;sFink = p;D）qFink = s;sFink = p;4、如果想在4092个数据中只需要选择其中最小的5个，采用（）方法最好。A）起泡排序B）堆排序 C）锦标赛排
9、序D）快速排序5、设有两个串t和p，求p在t中首次出现的位置的运算叫做（）。A）求子串 B）模式匹配 C）串替换D）串连接6、将一个递归算法改为对应的非递归算法时，通常需要使用（）。A）栈B）队列C）循环队列D）优先队列7、在循环队列中用数组A0.m-1存放队列元素 其队头和队尾指针分别为front和rear，则当前队列中的元素个数是()。B)( rear - front + 1) % m D)( rear - front + m) % mC) O(m*n)D) O(m+n)A) ( front - rear + 1) % mC) ( front - rear + m) % m8、下面程序段的
10、时间复杂度为()for (int i=0;im;i+)for (int j=0;jlink=p;p-link=s;B） s-link=p-link;p-link=s;C） s-link=p-link;p=s;D） p-link=s;s-link=p;10、 当利用大小为n的数组顺序存储一个队列时，该队列的最大长度为（）A）n-2B）n-1C）nD）n+111、某二叉树的前序和后序序列正好相反，则该二叉树一定是（）的二叉树。A）空或只有一个结点B）高度等于其结点数C）任一结点无左孩子D）任一结点无右孩子12、对于任何一棵二叉树T，如果其终端结点数为n0,度为2的结点为n2，则（）A）n0= n2
11、+1B）n2= n0+1C）n0= 2n2+1D）n2=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、 栈中存取数据的原则，队列
12、中存取数据的原则。5、设目标串T= abccdcdccbaa”，模式P= cdcc”则第 次匹配成功。三、判断1、数据的逻辑结构是指各数据元素之间的逻辑关系，是用户按使用需要建立的。（）2、线性表的逻辑顺序与物理顺序总是一致的。（）3、每种数据结构都应具备三种基本运算：插入、删除、搜索。（）4、深度为h的非空二叉树的第h层最多有2h-1个结点。（）5、完全二叉树就是满二叉树。（）6、最优二叉搜索树一定是平衡的二叉搜索树。（）7、线性表中所有结点的类型必须相同。（）8、连通分量是无向图中的极小连通子图。（）9、空串与由空格组成的串没有区别。（）10、带权连通图的最小生成树的权值之和一定小于它的其
13、它生成树的权值之和。（）四、简答1、在结点个数为n（n1）的各棵树中，高度最小的树的高度是多少？它有多少个叶结 点？多少个分支结点？高度最大的树的高度是多少？它有多少个叶结点？多少个分支结 点？八、2、将下面的森林变换成二叉树。3、有图如下，请画出其邻接多重表。五算法设计1、编写算法实现链表的创建、遍历、销毁。2、编写算法，实现快速排序。Part3一. 选择1、在数据结构的讨论中把数据结构从逻辑上分为（A）内部结构与外部结构C）线性结构与非线性结构B）静态结构与动态结构D）紧凑结构与非紧凑结构。2、下面程序段的时间复杂度为（for (int j=0;jlink=p-link; p-link=s
14、;B) q-link=s; s-link=pC) p-link=s-link; s-link=p;D) p-link=s; s-link=q;8、设单循环链表中结点的结构为(data,link)，且f irst为指向链表表头的指针，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
15、,b10、设链式栈中结点的结构为(data, link)，且top是指向栈顶的指针。若想摘除链式栈 的栈顶结点，并将被摘除结点的值保存到x中，则应执行下列( )操作。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)
16、n-1C) nD) n+113、某二叉树的前序和后序序列正好相反，则该二叉树一定是()的二叉树。A)空或只有一个结点B)高度等于其结点数C)任一结点无左孩子D)任一结点无右孩子14、顺序搜索算法适合于存储结构为()的线性表。A)散列存储B)顺序存储或链接存储C)压缩存储D)索引存储15、判断一个有向图是否存在回路，除了可以利用拓扑排序方法外，还可以利用()。A)求关键路径的方法B)求最短路径的Dijkstra方法C)深度优先遍历算法D)广度优先遍历算法二、判断1、从逻辑关系上讲，数据结构主要分为两大类：线性结构和非线性结构()。2、每种数据结构都应具备三种基本运算：插入、删除、搜索（）。3、非
17、空线性表中任意一个数据元素都有且仅有一个直接前驱元素。（）4、将T在S中首次出现的位置作为T在S中的位置的操作称为串的模式匹配。（）5、已知一棵二叉树的前序序列和中序序列可以唯一地构造出该二叉树。（）6、线性表的顺序存储结构的特点是逻辑关系上相邻的两个元素在物理位置上也相邻）7、用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中顶点个数有关，而与图的边数无关（）。8、邻接表只能用于有向图的存储，邻接矩阵对于有向图和无向图的存储都适用）9、连通分量是无向图中的极小连通子图。（）10、快速排序是对起泡排序的一种改进。（）三、）1、某子系统在通信联络中只可能出现8种字符，
18、其出现的概率分别为0.05,0.29,0.07， 0.08，0.14,0.23,0.03,0.11 试设计赫夫曼编码。四算法设计已知一个int类型的数组arra，其长度为n，要求用选择排序算法对其从小到大排序， 请实现该算法。面向对象程序设计C+Parti一、单项选择1. 下面对于指针的描述不正确的是（A.指针是地址变量C.两个指针变量的加减法无意义2. 下面对于析构函数的描述中不正确的是（A.析构函数是内置函数C.析构函数不能有参数3. 下列指针用法中错误的是（）。A. int i; int *ptr = &i;C. int *ptr; ptr=0;4. 派生类的对象对它的基类成员中什么是可
19、访问的（8.指针不能用除0以外的常量赋值D.指针指向不同基类型的变量长度不同 ）。B.析构函数与类名相同D.析函数在对象撤销时自动执行B. int i; int *ptr; i= *ptr;D. int i=5;int *ptr;*ptr=i; )?A.公有继承的公有成员B.公有继承的私有成员C.公有继承的保护成员D.私有继承的公有成员5. 在（）情况下适宜采用inline定义内联函数。A.函数体含有循环语句B.函数体含有递归语句C.需要加快程序的执行速度D.函数代码多、不常调用6. 在类中说明的成员可以使用关键字（）进行修饰。A. publicB. externC. cpuD. regist
20、er）。7. 如果类A被说明成类B的友元，则（A.类A的成员即类B的成员C.类A的成员函数不得访问类B的成员8. 定义析构函数时，应该注意（A.其名与类名完全相同C.无形参，也不可重载B.类B的成员即类A的成员D.类B不一定是类A的友元）。B.返回类型是void类型D.函数体中必须有delete语句9. 在类中声明一般函数时不能指定（）。A.参数B.访问权限（1操作D.标识符10. 在派生类中重新定义虚函数时必须在（A. 参数类型B.参数名字（1操作内容D.返回值类型11. 设 int a=3,b=4,c=5;表达式（a+b）c&b=A. 2B. -1C. 0D. 112. 下列标识符中，不合
21、法的用户标识符为（A. a#bB. _intC. a_10D. PAd13. while（!x）中的（!x）与下面条件（）等价。A. x= = 1B. x!=1）方面与基类保持一致。=c的值是（）。C. x!=0D. x=014. 每个类（）构造函数。A.只能有一个B.只可有公有的C.可以有多个D.只可有缺省的15. 静态成员函数不能说明为（）。A.整型函数B.浮点函数C.虚函数D.字符型函数16. 重载赋值操作符时，应声明为（）函数。A.友元B.虚C.成员D.多态17. 下面描述中，表达错误的是（）A. 公有继承时基类中的public成员在派生类中仍是public的B. 公有继承时基类中的p
22、rivate成员在派生类中仍是private的C. 公有继承时基类中的protected成员在派生类中仍是protected的D. 私有继承时基类中的public成员在派生类中是private的18. 通过（）调用虚函数时，采用动态指定。A.对象指针B.对象名C.成员名限定D.派生类名19. 在用class定义一个类时，数据成员和成员函数的默认访问权限是（）A. private B. publicC. protected D. virtual20. C+语言的跳转语句中，对于break和continue说法正确的是（）A. break语句只应用与循环体中B. continue语句只应用与循环体
23、中C. break是无条件跳转语句，continue不是D. break和continue的跳转范围不够明确，容易产生问题二、完成程序1. 在下面程序的底画线处填上适当的字句，使该程序执行结果为60。# include class CBase int X;public:void Init （int initX）X = initX; int GetNum（） return X+7; void main（）couttest.Getnum（）;2. 在下面程序的底画线处填上适当的字句，完成类中成员函数的定义。# include calss line;class boxprivate :int col
24、or;int upx,upy;int lowx,lowy;public: int same_color(line a,box b);void SetColor(int iCl)color = iCl;void define_box(int x1,int y1,int x2,int y2)upx=x1;upy=y1;lowx=x2;lowy=y2; ;class lineprivate:int color;int startx,starty;int len;public:friend int same_color(line a,box b);void setlen(int iL)len=iL;v
25、oid define_line(int x,int y)startx=x ;straty=y;int same_color(line a,box b)if ( a.color = =b.color) return 1;return 0;void main()line l;box bb;bb.SetColor(1);l.SetColor(1);if (same_color(l,bb)=1) coutThe Same Color!endl;3. 已知 int DBL(int n)return n + n;和 long DBL(long n)return n+n;是一个函数模板的两个实例，则该函数模
26、板的定义是4. 在下列程序的空格处填上适当的字句，使输出为：0，8,5。# include # include class Magicdouble x;public :Magic(double d=0.00) : x(fabs(d)return Magic(sqrt(x*x+c.x*c.x);friend ostream& operator(ostream & os,Magic c)return osc.x;void main()Magic ma;coutma，Magic(-8)，ma+Magic(-3)+Magic(-4);三、综合应用1. 分析下列程序可能的输出结果。# include “
27、iostream.h”class testprivate:int num;float fl;public:test();int getint( )return num;float getfloat( )return fl;test();test:test()coutlnitalizing defaultendl;num=0;fl=0.0;test:test()coutDesdtructor is activeendl;int main()test array2;coutarray1.getint ( ) array1.getfloat()endl;2. 下列shape类是一个表示形状的抽象类，
28、length()为求图形周长的函数，total()则是一 个通用的用以求不同形状的图形周长总和的函数。请从shape类派生三角形类(triangle)、 矩形类(rectangle)，并给出具体的求周长函数。给出shape,total的定义如下所示。class shapepublic:virtual float length（ ）=0；float total（shape *s,int n）float sum=0.0;for（int i=0;ilength（）;return sum;Part2一、选择1、面向对象的程序设计思想中，首先在问题域中识别出若干个（）A.函数 B.类C.文件 D.过程2
29、、定义类模板用关键字（）A.const B.new C.delete D.template3、运算结果类型相同的（）A. 9.0/2.0 9.0/2 B. 9/2.0 9/2C. 9.0/2 9/2 D. 9/29.0/2.04、已知f1 f2同一类两个成员函数，但f1不能调用f2,说明（）A.f1 f2都是静态函数 B.f1是静态函数，f2不是C.f1不是，f2是静态函数 D.f1 f2都不是静态函数5、调用一成员函数时，使用动态联编的情况是（）A.通过对象调用一虚函数 B.通过指针或引用调用一虚函数C. 通过对象调用静态函数D.通过指针或引用调用一静态函数6、假定一个类构造函数为：“A（i
30、nt aa=1,int bb=0）a=aa;b=bb;则执行”A x（4）后，x.a 和x.b值分别是：（）A.1，0B.1，4C.4,0D.4,17、在派生类中能直接访问基类的（）A.公有成员，私有成员B.保护成员，私有成员C.不可访问成员，私有成员D.公有成员，保护成员8、不具访问权限属性的是：（）A.非类成员B.类成员C.数据成员D.函数成员9、类定义中 private,protected,public 出现次数为（）A.任意多次 B.至多一次C.public至少一次 D.至少一次10、C+ +鼓励程序员将（）A.数据操作分别封装B.不同类型数据封装C.数据操作封装在一起D.不同作用操作
31、封装在一起二、填空1、C+ +中，最好用（）代替malloc2、函数模板中template之后尖括号的类型参数冠以保留字（）3、在IOS类中定义的用于格式控制的枚举变量中十、八、十六进制是dec,oct,（）4、如果重载了运算符+，则相应运算函数名是()5、由static修饰的数据成员为该类的所有对象()6、为了实现多态性，派生类需要重新定义基类中的()7、编译时多态性通过()虚函数实现。8、派生类中实现基类成员初始化，需由派生类的构造函数调用()来完成。9、C+ +中访问指令所指对象的静态成员函数使用运算符()10、重载函数在参数类型或参数个数上不同但()相同。三、改错1、类定义有错，正确结
32、果为5 + 8i#include #include class complexdouble real;double imag;public:complex(double r=0.0,double i=0.0):real(r),imag(i);void show()coutreal=0?+:-)fabs(imag)iendl;friend complex&operator +=(complex c1,complex c2)c1.real+=c2.real;c1.imag+=c2.imag;return c1;void main()complex c(3,5);c+=complex(2,3);c.
33、show();2、改一处错#includeclass shapepublic:int area()return 0;class rectangle:public shapepublic:int a,b;void setlength(int x,int y)a=x;b=y;int area()return a*b;void main()rectangle r;r.setlength(3,5);shape *s = r;cout r.area()endl;cout s.area()endl;3、指出下面类中的错误，并改正： class Aint a,b;public:A(int aa=0,int
34、bb)a=aa;b=bb;4、指出下面类中的错误，并改正class Locationint x,y;protected:int SetZero(int zeroX,int XeroY);private:int length,height;public:void Location (int initX,int initY);int getx();int gety();四、程序填空1、在空白处填上正确的内容，使输出结果为：5 4 3 2 10 5.5 4.4 3.3 2.2 1.1#includetemplate void f(, )T t;for (int i=0;in;i+)t=ai; ai=
35、an-1-i; an-1-i=t;void main ()int a5 = 1,2,3,4,5;double d6 = 1.1,2.2,3.3,4.4,5.5f(a,5);f(d,6);for(int i=0;i5;i+)cout ai;cout endl;for ()coutdi;cout endl;2、在空白处填上正确的内容，使类定义完整class line;class boxprivate:int color;int upx,upy;int lowx,lowy;public: int same_color( , box b);void set_color(int c)color =c;v
