1、数据结构和C+程序设计题库数据结构Part1一选择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）144 C）148 D）412 5下面关于线性表的
2、叙述中，错误的是（ ）A） 顺序表使用一维数组实现的线性表 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
3、-next；C）p-next=p-next； D）p=p-next-next； 9若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ ）存储方式最节省运算时间 A）单链表 B）仅有头指针的单循环链表 C）双链表 D）仅有尾指针的单循环链表 10按二叉树的定义，具有三个结点的二元树共有（ ）种形态。 A）3 B）4 C）5 D）6 11任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序（ ）A）发生改变 B）不发生改变 C）不能确定 D）以上都不对 12深度为5的二叉树至多有（ ）个结点A）16 B）32 C）31 D）10 13在一棵度为3的树中，度为
4、3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，那么度为0的结点数为（ ）个。 A）4 B）5 C）6 D）7 14对于一个具有n个顶点的无向图，若采用邻接表表示，则存放表头结点的数组(顶点表)的大小为（ ）A）n B）n+1 C）n-1 D）n/2 15静态查找表和动态查找表二者的根本差别在于（ ） A）它们的逻辑结构不同 B）施加在其上的操作不同 C）所包含的数据元素的类型不一样 D）存储实现不一样二填空1某程序的时间复杂性为(3n+nlog2n+n2+8),其数量级表示为_。2线性表L=(a1,a2,an)采用顺序结构存储,假定在不同的位置上插入的概率相同，则插入一个新元素
5、平均需要移动的元素个数是_ 。3. 对于一株具有n个结点的树，该树中所有结点的度数之和为_。4. 在一个图中,所有顶点的度数之和等于所有边数的_倍。5. 一棵二叉树有67个结点,这些结点的度要么是0，要么是2。这棵二元树中度数为2的结点有_个。 6在一个无向图的邻接表中，若表结点的个数是m，则图中边的条数是_。7采用堆排序、快速排序、冒泡排序，对初态有序的表，最省时间的是_ 。8设二叉树结点的先根序列为ABDECFGH，中根序列为DEBAFCHG,则二元树中叶结点是_. 9一个哈夫曼(Huffman)树有19个结点，则其叶结点的个数是_。10.栈S和队列Q的初始状态皆为空,元素a1,a2,a3
6、,a4,a5和a6依次通过S栈，一个元素出栈后即进入队列Q，若6个元素出队列的顺序是a3,a5,a4,a6,a2,a1，则栈S至少应该容纳_ 个元素。三判断1线性表的链式存储结构优于顺序行储结构。（ ）2在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。（ ）3 对于n个记录的集合进行归并排序，存最坏的情况下所需要的时间是O(n2)。（ ）4 表中的每一个元素都有一个前驱和后继元素。（ ）5 进栈操作push(x，s)作用于链接栈时，无须判满。（ ）6 只有在初始数据为逆序时，冒泡排序所执行的比较次数最多。 （ ）7 在索引顺序表查找方法中，对索引顺序表可
7、以使用顺序表查找方法，也可以使用二分查找方法。（ ）8 数据元素是数据的最小单位。（ ）9 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。（ ） 10 按中序遍历一棵二叉排序树所得到的中序遍历序列是一个递增序列。（ ） 四简答1. 对于下图所示的树： (1) 写出先序遍历得到的结点序列；(2) 画出转换后得到的二叉树。2请画出与下列二元树对应的森林。五算法设计1已知一个int类型的数组arra，其长度为n，要求用冒泡排序算法对其从小到大排序，请实现该算法，（要求后面开始循环，大的数值下沉）。2利用一个栈实现以下递归函数的非递归计算： P (x)= Part2一、单项选择1、 在数据结
8、构的讨论中把数据结构从逻辑上分为（ ） A）内部结构与外部结构 B）静态结构与动态结构C）线性结构与非线性结构 D）紧凑结构与非紧凑结构。2、算法分析的目的是（ ）A）找出数据结构的合理性 B）研究算法中输入和输出的关系C）分析算法的效率以求改进 D）分析算法的易懂性和文档性3、在一个单链表中，若q结点是p结点的前驱结点，若在q与p之间插入结点s，则执行（ ）A）slink = plink; plink = s; B）plink = s; slink = q;C）plink = slink; slink = p; D）qlink = s; slink = p;4、如果想在4092个数据中只需要
9、选择其中最小的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) % m B）( rear - front + 1) % mC）( front - rear + m) % m D）
10、( rear - front + m) % m8、下面程序段的时间复杂度为（ ） 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-2 B）n-1 C）n D）n+111、某二叉树的前序和后序序列正好相反，则该二叉树一定是（）的二叉树。A）空或只有一个结点 B）高度等于其结点数 C）任一结点无左孩子 D）任一结点无右孩子12、对于任何
11、一棵二叉树T，如果其终端结点数为n0，度为2的结点为n2，则( )A）n0= n2+1 B）n2= n0+1 C）n0= 2n2+1 D）n2=2n0+113、 由权值分别为11，8，6，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（ ）A）24 B）73 C）48 D）5314、对线性表进行折半搜索时，要求线性表必须（ ）A）以链接方式存储且结点按关键码有序排列 B）以数组方式存储 C）以数组方式存储且结点按关键码有序排列 D）以链接方式存储15、顺序搜索算法适合于存储结构为（ ）的线性表。A）散列存储 B）顺序存储或链接存储 C）压缩存储 D）索引存储二、填空1、数据的存储结构被分
12、为 、 、 、 四种。2、一种抽象数据类型包括 和 两个部分。3、栈、队列逻辑上都是 结构。4、栈中存取数据的原则 ，队列中存取数据的原则 。5、设目标串T=”abccdcdccbaa”,模式P=”cdcc”则第 次匹配成功。三、判断1、 数据的逻辑结构是指各数据元素之间的逻辑关系，是用户按使用需要建立的。( )2、 线性表的逻辑顺序与物理顺序总是一致的。（ ）3、 每种数据结构都应具备三种基本运算：插入、删除、搜索。（ ）4、深度为h的非空二叉树的第h层最多有2h-1个结点。（ ）5、完全二叉树就是满二叉树。（ ）6、最优二叉搜索树一定是平衡的二叉搜索树。（ ）7、线性表中所有结点的类型必须
13、相同。（ ）8、连通分量是无向图中的极小连通子图。（ ）9、 空串与由空格组成的串没有区别。（ ）10、带权连通图的最小生成树的权值之和一定小于它的其它生成树的权值之和。（ ）四、简答1、 在结点个数为n(n1)的各棵树中，高度最小的树的高度是多少？它有多少个叶结点？多少个分支结点？高度最大的树的高度是多少？它有多少个叶结点？多少个分支结点？ 2、将下面的森林变换成二叉树。3、有图如下，请画出其邻接多重表。五算法设计1、编写算法实现链表的创建、遍历、销毁。2、编写算法，实现快速排序。Part3一选择1、 在数据结构的讨论中把数据结构从逻辑上分为 （ ） A）内部结构与外部结构 B）静态结构与动
14、态结构 C）线性结构与非线性结构 D）紧凑结构与非紧凑结构。2、下面程序段的时间复杂度为（ ） for (int i=0;im;i+) for (int j=0;jlink=p-link; p-link=s; B) q-link=s; s-link=pC) p-link=s-link; s-link=p; D) p-link=s; s-link=q;8、设单循环链表中结点的结构为（data,link）,且first为指向链表表头的指针，current为链表当前指针，在循环链表中检测current是否达到链表表尾的语句是( )。A) current-link =null B) first-lin
15、k=currentC) first=current D) current-link=first9、一个栈的入栈序列为a，b，c，则出栈序列不可能的是( )。A) c,b,a B) b,a,c C) c,a,b D) a,c,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、假定一个顺序存储的
16、循环队列的队头和队尾指针分别为f和r ,则判断队空的条件为( )。A) f+1= =r B) r+1= =f C) f= =0 D) f= =r12、当利用大小为n 的数组顺序存储一个队列时，该队列的最大长度为（ ）A) n-2 B) n-1 C) n D) n+113、某二叉树的前序和后序序列正好相反，则该二叉树一定是（ ）的二叉树。A) 空或只有一个结点 B) 高度等于其结点数 C) 任一结点无左孩子 D) 任一结点无右孩子14、顺序搜索算法适合于存储结构为（ ）的线性表。A) 散列存储 B) 顺序存储或链接存储 C) 压缩存储 D) 索引存储15、判断一个有向图是否存在回路，除了可以利用
17、拓扑排序方法外，还可以利用（ ）。A) 求关键路径的方法 B) 求最短路径的Dijkstra方法 C) 深度优先遍历算法 D) 广度优先遍历算法二、判断1、 从逻辑关系上讲，数据结构主要分为两大类：线性结构和非线性结构（ ）。2、 每种数据结构都应具备三种基本运算：插入、删除、搜索（ ）。3、 非空线性表中任意一个数据元素都有且仅有一个直接前驱元素。（ ）4、 将T在S中首次出现的位置作为T在S中的位置的操作称为串的模式匹配。（ ）5、 已知一棵二叉树的前序序列和中序序列可以唯一地构造出该二叉树。（ ）6、线性表的顺序存储结构的特点是逻辑关系上相邻的两个元素在物理位置上也相邻。（ ）7、用邻接
18、矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中顶点个数有关，而与图的边数无关（ ）。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，要求用选择排序算法对其从小到大排序，请实现该算法。面向对象程序设计C+Pa
19、rt1一、单项选择1.下面对于指针的描述不正确的是( )。A.指针是地址变量 B.指针不能用除0以外的常量赋值C.两个指针变量的加减法无意义 D.指针指向不同基类型的变量长度不同2.下面对于析构函数的描述中不正确的是( )。A.析构函数是内置函数 B.析构函数与类名相同C.析构函数不能有参数 D.析函数在对象撤销时自动执行3.下列指针用法中错误的是( )。A. int i; int *ptr = &i; B. int i; int *ptr; i= *ptr;C. int *ptr; ptr=0; D. int i=5;int *ptr;*ptr=i;4.派生类的对象对它的基类成员中什么是可访
20、问的( )?A.公有继承的公有成员 B.公有继承的私有成员C.公有继承的保护成员 D.私有继承的公有成员5.在( )情况下适宜采用inline定义内联函数。A.函数体含有循环语句 B.函数体含有递归语句C.需要加快程序的执行速度 D.函数代码多、不常调用6.在类中说明的成员可以使用关键字( )进行修饰。A. public B. externC. cpu D. register7.如果类A被说明成类B的友元，则( )。A.类A的成员即类B的成员 B.类B的成员即类A的成员C.类A的成员函数不得访问类B的成员 D.类B不一定是类A的友元8.定义析构函数时，应该注意( )。A.其名与类名完全相同 B
21、.返回类型是void类型C.无形参，也不可重载 D.函数体中必须有delete语句9.在类中声明一般函数时不能指定( )。A.参数 B.访问权限C.操作 D.标识符10.在派生类中重新定义虚函数时必须在( )方面与基类保持一致。A.参数类型 B.参数名字C.操作内容 D.返回值类型11.设int a=3,b=4,c=5;表达式(a+b)c&b= =c的值是( )。A. 2 B. -1C. 0 D. 112.下列标识符中，不合法的用户标识符为( )。A. a#b B. _intC. a_10 D. PAd13.while(!x)中的(!x)与下面条件( )等价。A. x1 B. x!=1C. x!=0 D. x014.每个类( )构造函数。A.只能有一个 B.只可有公有的C
