2015福建省数据结构(C++)考试题库

1 . 以下说法正确的是（)A . 二叉树的特点是每个结点至多只有两棵子树。

B . 二叉树的子树无左右之分。

C . 二叉树只能进行链式存储。

D . 树的结点包含一个数据元素及若干指向其子树的分支。

答案：A，D解析：2 . 算法设计的要求包括____。

A . 正确性B . 可读性C . 健壮性D . 确定性答案：A，B，C解析：“确定性”属于算法特性而非要求。

3 . 下列属于算法的重要特征的是：A . 有穷性B . 确定性C . 可行性D . 输入和输出答案：A，B，C，D解析： ABCD4 . 图的四中存储结构A . 邻接矩阵B . 邻接表C . 邻接多重表D . 十字链表答案：A，B，C，D解析：5 . 依据所有数据成员之间的逻辑关系的不同，数据结构分为（）A . 非线性结构B . 逻辑结构C . 物理结构D . 线性结构答案：A，D解析：6 . 图的应用算法有（）A . 克鲁斯卡尔算法B . 哈弗曼算法C . 迪杰斯特拉算法D . 拓扑排序算法答案：A，C，D解析：7 . 计算机算法必须具备________________等特性。

A . 可行性、确定性B . 可行性、可移植性C . 输入、输出D . 有穷性E . 易读性F . 稳定性答案：A，C，D解析：8 . 下列数据结构中，属于线性数据结构的是____A . 栈B . 队列C . 树D . 图答案：A，B解析：9 . 下列说法正确的有：A . 算法和程序原则上没有区别，在讨论数据结构时二者通用B . 从逻辑关系上讲，数据结构分为两大类：线性结构和非线性结构C . 所谓数据的逻辑结构是指数据元素之间的逻辑关系D . 同一数据逻辑结构中的所有数据元素都具有相同的特性是指数据元素所包含的数据项的个数相等E . 数据的逻辑结构与数据元素本身的内容和形式无关F . 数据结构是指相互之间存在一种或多种关系的数据元素的全体答案：B，C，E解析：10 . 线性表的特点正确的（）A . 存在唯一的一个被称作”第一个“的数据元素。

栈1设有三个元素X,Y,Z顺序进栈(进的过程中允许出栈),下列得不到的出栈排列是()。

•A、XYZ•B、YZX•C、ZXY•D、ZYX正确答案：C 我的答案：C 得分：14.2分2向一个栈顶指针为hs的链栈中插入一个s结点时,应执行()。

•A、hs->next=s;•B、s->next=hs; hs=s;•C、s->next=hs->next; hs->next=s;•D、s->next=hs; hs=hs->next;正确答案：B 我的答案：B 得分：14.2分3栈在()中应用。

•A、递归调用•B、子程序调用•C、表达式求值•D、A,B,C正确答案：A 我的答案：D 得分：0.0分4栈的操作原则是()。

•A、先进先出•B、后进先出•C、先进后出•D、不分顺序正确答案：B 我的答案：B 得分：14.2分5一个栈的输入序列为123…n,若输出序列的第一个元素是n,输出第i(1<=i<=n)个元素是()。

•A、不确定•B、n-i+1•C、i•D、n-i正确答案：B 我的答案：B 得分：14.2分6链栈与顺序栈相比,有一个比较明显的优点,即()•A、插入操作方便•B、通常不会出现栈满的情况•C、不会出现栈空的情况•D、删除操作更方便正确答案：B 我的答案：D 得分：0.0分二.简答题（共1题,14.8分）1假定有四个元素A,B,C,D依次进栈,进栈过程中允许出栈,试写出所有可能的出栈序列。

正确答案：共有14中可能的出栈序列","分别为: ABCD","ABDC","ACBD"," ACDB","BACD","ADCB","BADC","BCAD"," BCDA","BDCA","CBAD"," CBDA","CDBA"," DCBA。

要求：所有的题目的解答均写在答题纸上，需写清楚题目的序号。

每张答题纸都要写上姓名和学号。

一、单项选择题(每小题2分，共20小题，共计40分)1.某算法的空间复杂度为0(1),则。

A.该算法执行不需要任何辅助空间B.该算法执行所需辅助空间大小与问题规模n无关C.该算法执行不需要任何空间D.该算法执行所需全部空间大小与问题规模n无关2.在长度为n的顺序表中插入一个元素，对应算法的时间复杂度为。

A.0(1)B.O(log2n)C.0(n)D.0(n2)3.设线性表中有n个元素，以下运算中，在单链表上实现要比在顺序表上实现效率更高。

A.删除指定位置元素的后一个元素B.在最后一个元素的后面插入一个新元素C.顺序输出前k个元素D.交换第i个元素和第n-i+1个元素的值(i=1, 2,…，n)4.以下数据结构中元素之间为非线性关系的是。

A.栈B.队列C.线性表D.以上都不是5.若一个栈用数组data[1..n]存储，初始栈顶指针top为n+1,则以下元素x进栈的正确操作是。

A.top++;data[top]=x;B.data[top]=x;top++;C.top-- ;data[top]=x;D.data[top]=x;top --;6.若某循环队列有队首指针front和队尾指针rear,在队不满时进队操作仅会改变。

A.frontB.rearC.front 和rearD.以上都不队7.设循环队列中数组的下标是0〜N-1,其队头、队尾指针分别为f和r(f指向队首元素的前一位置，r指向队尾元素)，则其元素个数为。

A.r-fB.r-f-1C.(r-f)%N+1D.(r-f+N)%N8.设树T的度为4,其中度为1、2、3、4的结点个数分别为4、2、1、1,则T中的叶子结点个数是。

A.5B.6C.7D.89. 一棵哈夫曼树中共有199个结点，它用于多少个字符的编码。

A.99B.100C.101D.19910.设森林F中有4棵树，第1、2、3、4棵树的结点个数分别为a、b、c、d,将森林F转换为一颗二叉树B,则二叉树B根结点的左子树上的结点个数是。

1 . 数据的（C）是面向计算机的A. 数据结构B. 逻辑结构C. 物理结构D. 线性结构E. 非线性结构2 .（C）是组成数据的基本单位。

A. 数据项B. 数据对象C. 数据元素D. 数据类型E. 操作F. 抽象数据类3 .（B）特点是：信息隐蔽和数据封装，使用与实现相分离。

A. 操作B. 抽象数据类型C. 数据元素D. 数据4 . 下面程序段执行时，语句S的执行次数为：（D）A. n2B. n2/2C. n（n+1）D. n(n+1)/25 . 下面程序段的时间复杂度为：（B）A. O（1)B. O（n）C. O（n2）D. O（n!）6 . 一个算法的时间复杂度为(3n2+2nlog2n+4n-7)/(5n)，其数量级表示为：（C ）A. O（n2）B. O（nlog2n)C. O（n）D. O（log2n）7 . 在下面程序段中，s=s+p语句的执行次数为：（E）A. n2B. n2/2C. n（n+1）D. n(n+1)/2E. nF. n/28 . 下面程序段的时间复杂度为：（C）A. O（1）B. O（n）C. O（n2）D. O（n!）9 . 在线性表的下列运算中，不改变数据元素之间结构关系的运算是（D）A. 插入B. 删除C. 排序D. 定位10 . 线性表采用链式存储时，其地址（D）A. 必须是连续的B. 一定是不连续的C. 部分地址必须是连续的D. 连续与否均可以11 . 线性表L在(B)情况下适用于使用链式结构实现。

A. 需经常修改Ｌ中的结点值B. 需不断对Ｌ进行删除插入C. L中含有大量的结点D. L中结点结构复杂12 . 设单链表中结点的结构为（data,link），单链表中指针p指向结点m，若要删除m之后的结点（若存在），则需修改指针的操作为（A）A. p->Link=p->Link->Link;B. p=p->Link;C. p=p->Link->Link;D. p->Link=p;13 . 在顺序表中，只要知道(D)，就可在相同时间内求出任一表项的存储地址。

第 1 章 绪论一、选择题1. 算法的计算量的大小称为计算的（ ）。

【北京邮电大学 2000 二、 3( 20/8 分） 】A . 效 率B.复杂性C.现实性 D. 难度2. 算法的时间复杂度取决于（ ）【 中科院计算所 1998 二、 1（ 2 分）】A.问题的规模B. 待处理数据的初态C. A 和 B3. 计算机算法指的是（ 1），它必须具备（ 2） 这三个特性。

（1） A ．计算方法 B. 排序方法 C. 解决问题的步骤序 列 D. 调度方法（2） A ．可执行性、可移植性、可扩充性 B. 可执行性、确定性、有穷性 C. 确定性、有穷性、稳定性 D. 易读性、稳定性、安全 性B. 为解决某问题的算法同为该问题编写的程序含义是相同的C. 算法的可行性是指指令不能有二义性 误的 6.下面说法错误的是（）【南京理工大学 2000 一、 2 （1.5 分）】（1）算法原地工作的含义是指不需要任何额外的辅助空间（2）在相同的规模 n 下，复杂度0（n ）的算法在时间上总是优于复杂度 0（2"）的算法（ 3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界（ 4）同一个算法，实现语言的级别越高，执行效率就越低A . （1） B.（1）,（2）7. 从逻辑上可以把数据结构分为（ 4（ 2 分）】A .动态结构、静态结构 C.线性结构、非线性结构 8. 以下与数据的存储结构无关的术语是（ 分）】A . 循 环 队 列 表 D. 栈9. 以下数据结构中，哪一个是线性结构（ 分）】A . 广 义 表C.（1）,（4）D.（3））两大类。

【武汉交通科技大学 1996 B.顺序结构、链式结构D.4．【南京理工大学 一个算法应该是（ A .程序性5. 1999 一、 1（ 2 分） 【武汉交通科技大学 ）。

【中山大学 1998 二、B .问题求解步骤的描述D. A 和 C.下面关于算法说法错误的是（A. 算法最终必须由计算机程序实现 1996 一、1（ 4 分）】1（2 分）】 C.要满足五个基本特 ）【南京理工大学2000 一、 1（ 1.5 分）】D. 以上几个都是错）。

第1章绪论一、选择题1. 算法的计算量的大小称为计算的（）。

【北京邮电大学2000二、3（20/8分）】A．效率 B.复杂性 C.现实性 D.难度2. 算法的时间复杂度取决于（）【中科院计算所1998二、1（2分）】A．问题的规模 B.待处理数据的初态 C. A 和 B3.计算机算法指的是（ 1），它必须具备（ 2）这三个特性。

(1) A．计算方法 B.排序方法 C.解决问题的步骤序列 D.调度方法(2) A ．可执行性、可移植性、可扩充性 B.可执行性、确定性、有穷性C. 确定性、有穷性、稳定性D.易读性、稳定性、安全性【南京理工大学1999一、1（2分）【武汉交通科技大学1996一、1（ 4 分）】4．一个算法应该是（）。

【中山大学1998二、1（2分）】A．程序B．问题求解步骤的描述C．要满足五个基本特性D．A 和 C.5. 下面关于算法说法错误的是（）【南京理工大学2000一、1（1.5分）】A．算法最终必须由计算机程序实现B.为解决某问题的算法同为该问题编写的程序含义是相同的C. 算法的可行性是指指令不能有二义性D. 以上几个都是错误的6. 下面说法错误的是（）【南京理工大学2000一、 2（ 1.5分）】(1 ）算法原地工作的含义是指不需要任何额外的辅助空间（ 2）在相同的规模n 下，复杂度 O(n) 的算法在时间上总是优于复杂度nO(2 ) 的算法（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界（4）同一个算法，实现语言的级别越高，执行效率就越低A． (1) B.(1),(2) C.(1),(4) D.(3)7．从逻辑上可以把数据结构分为（）两大类。

【武汉交通科技大学1996 一、4（ 2 分）】A．动态结构、静态结构B．顺序结构、链式结构C．线性结构、非线性结构D．初等结构、构造型结构8．以下与数据的存储结构无关的术语是（）。

【北方交通大学2000二、 1（2分）】A．循环队列 B.链表 C.哈希表 D.栈9．以下数据结构中，哪一个是线性结构（）？【北方交通大学2001一、 1（2分）】A．广义表 B.二叉树 C.稀疏矩阵 D.串10．以下那一个术语与数据的存储结构无关？（）【北方交通大学2001一、 2（2 分）】A ．栈 B.哈希表 C.线索树 D.双向链表11．在下面的程序段中，对 x 的赋值语句的频度为（）【北京工商大学2001一、10（ 3 分）】FOR i:=1TOn DOFOR j:=1TOn DOx:=x+1;A． O(2n)B． O(n)C． O(n2)D． O(logn 2 )12．程序段FOR i:=n-1DOWNTO1DOFOR j:=1 TO i DOIF A[j]>A[j+1]THEN A[j]与 A[j+1]对换；其中 n 为正整数，则最后一行的语句频度在最坏情况下是（）A. O （ n）B. O(nlogn)C. O(n 3)D. O(n 2)【南京理工大学 1998 一、 1(2 分 ) 】13．以下哪个数据结构不是多型数据类型（）【中山大学1999一、 3（ 1 分）】A．栈B．广义表C．有向图D．字符串14．以下数据结构中，（）是非线性数据结构【中山大学1999一、 4】A．树B．字符串C．队D．栈15.下列数据中，（）是非线性数据结构。

《数据结构（C语言版第2版）》（严蔚敏著）第三章练习题答案第3章栈和队列1．选择题（1）若让元素1，2，3，4，5依次进栈，则出栈次序不可能出现在（）种情况。

A．5，4，3，2，1 B．2，1，5，4，3 C．4，3，1，2，5 D．2，3，5，4，1答案：C解释：栈是后进先出的线性表，不难发现C选项中元素1比元素2先出栈，违背了栈的后进先出原则，所以不可能出现C选项所示的情况。

（2）若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为（）。

A．i B．n-i C．n-i+1 D．不确定答案：C解释：栈是后进先出的线性表，一个栈的入栈序列是1，2，3，…，n，而输出序列的第一个元素为n，说明1，2，3，…，n一次性全部进栈，再进行输出，所以p1=n，p2=n-1，…，pi=n-i+1。

（3）数组Ｑ［ｎ］用来表示一个循环队列，ｆ为当前队列头元素的前一位置，ｒ为队尾元素的位置，假定队列中元素的个数小于ｎ，计算队列中元素个数的公式为（）。

A．r-f B．(n+f-r)%n C．n+r-f D．（n+r-f)%n答案：D解释：对于非循环队列，尾指针和头指针的差值便是队列的长度，而对于循环队列，差值可能为负数，所以需要将差值加上MAXSIZE（本题为n），然后与MAXSIZE（本题为n）求余，即（n+r-f)%n。

（4）链式栈结点为：(data,link)，top指向栈顶.若想摘除栈顶结点，并将删除结点的值保存到x中,则应执行操作（）。

A．x=top->data;top=top->link；B．top=top->link;x=top->link；C．x=top;top=top->link；D．x=top->link；答案：A解释：x=top->data将结点的值保存到x中，top=top->link栈顶指针指向栈顶下一结点，即摘除栈顶结点。

福建省计算机等级考试二级（C ）试题一、选择题1、若定义：int x=2; y=3; float i ； 则以下符合C 语言语法的表达式是（B ）A 、x=x* 3=2B 、x=(y= = 1)C 、i=float(x)D 、i%(-3)2、若有定义：int a=5, b=2, c=1；则表达式a-b<c11b= =c 的值是（A ）A 、0B 、1C 、2D 、-13、若有定义：float x=3.5; int z=8; 则表达式x+z%3/4的值是（B ）A 、3.75B 、3.5C 、3D 、44、有如下定义 int a[ ][3]={1，2，3，4，5，6，7，8，}；则数组a 的行数（B ）A 、 2B 、 3C 、 4D 、无法确定5、C 程序中main 函数的位置（C ）A 、必须在最开始B 、必须在系统库函数后面C 、可以在自定义函数后面D 、必须在最后6、下面关于C 语言用户标识符的描述，正确的是（D ）A 、不能区分大小写B 、用户标识符不能描述常量C 、类型名也是用户标识D 、用户标识符可以作为变量名7.若有定义：int a=1，b=2，c=3；语句++a||++b ＆＆++a 运行后b的值为（D ） A ．1 B.0 C.2 D.38.设单精度型变量+，g 的值均为2.0，使+为4.0的表达式为（A ）A.1B.0C.2D.39.对于整型变量x 。

下述计语句（B ）与赋值句：x=x%2= =0？1：0；不等价A .if （x%2！=0）x=0；else x=1；B if （x%2）x=1；else x=0；C.if （x%2= =0）x=1；else x=0； D .if （x%2==1） x=0；else x=1；10.以下数组定义中，正确的是（B ）A.int a[2] [3]={1，2，3，4，5，6，7}；B.int a[] []={{1，2，3}，{4，5，6}，{7，8，9}}；C.int a[2] []={1，2，3，4，5，6}；D.int a[] [4]={6}；11.若有定义：#define PI 3，则表达式PI ＊2＊2的值为（A ）A.12B.4C.3D.不确定12.下面语句正确的是（ B ）A int ＊P ；＊P=20； B.char ＊s=“abcdef ”；printf （“%s\n ”,S ）;C char str[]=“abcdf ”；printf （“%S ”,str ）;D.[](){',','};int "%",;char str a b c pr f s str =13.若有定义:int ａ＝２；则正确的赋值表达式是（Ａ）Ａ.ａ- =(a＊3) B.double(-a) C.a＊ D.a＊4=314.若有定义:int a=6,b=2;char C1=‘a’，C2=‘b’；则表达式a+b%5+C2-C1的值是（C）A .7 B.8 C.9 D表达式错误15.若有定义：char str[6]=“abcdm”，＊ps，＊str2=“abcdef”；正确的是（B）A.stycpy（str1，str2）；B.表达式strcmp（str1，str2）的值＞0C.str1=str2；D.表达式strlen（str1）的值为616.关于C语言函数的描述中，正确的是（B）A.函数的定义可以嵌套，但函数的调用不可以嵌套B.函数的定义不可以嵌套，但函数的调用得意嵌套C.函数的定义和函数的调用都可以嵌套D . 函数的定义和函数的调用都不可以嵌套17.设有如下定义typedef int ＊INTEGER；INTEGER P，＊q；则（C）是正确的表述A.P是int型变量 B .q是基类型为int的指针变量C.P是基类型为int的指针变量D.程序中可用INTEGER代替int类型名。

《数据结构（C语言版第2版）》（严蔚敏著）第七章练习题答案第7章查找1．选择题（1）对n个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为（）。

A．(n-1)/2B．n/2C．(n+1)/2D．n答案：C解释：总查找次数N=1+2+3+…+n=n(n+1)/2，则平均查找长度为N/n=(n+1)/2。

（2）适用于折半查找的表的存储方式及元素排列要求为（）。

A．链接方式存储，元素无序B．链接方式存储，元素有序C．顺序方式存储，元素无序D．顺序方式存储，元素有序答案：D解释：折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。

（3）如果要求一个线性表既能较快的查找，又能适应动态变化的要求，最好采用()查找法。

A．顺序查找B．折半查找C．分块查找D．哈希查找答案：C解释：分块查找的优点是：在表中插入和删除数据元素时，只要找到该元素对应的块，就可以在该块内进行插入和删除运算。

由于块内是无序的，故插入和删除比较容易，无需进行大量移动。

如果线性表既要快速查找又经常动态变化，则可采用分块查找。

（4）折半查找有序表（4，6，10，12，20，30，50，70，88，100）。

若查找表中元素58，则它将依次与表中（）比较大小，查找结果是失败。

A．20，70，30，50B．30，88，70，50C．20，50D．30，88，50答案：A解释：表中共10个元素，第一次取⎣(1+10)/2⎦=5，与第五个元素20比较，58大于20，再取⎣(6+10)/2⎦=8，与第八个元素70比较，依次类推再与30、50比较，最终查找失败。

（5）对22个记录的有序表作折半查找，当查找失败时，至少需要比较（）次关键字。

A．3B．4C．5D．6答案：B解释：22个记录的有序表，其折半查找的判定树深度为⎣log222⎦+1=5，且该判定树不是满二叉树，即查找失败时至多比较5次，至少比较4次。

（6）折半搜索与二叉排序树的时间性能（）。

第1章绪论一、选择题1. 算法的计算量的大小称为计算的（）。

【北京邮电大学2000 二、3 （20/8分）】A．效率 B. 复杂性 C. 现实性 D. 难度2. 算法的时间复杂度取决于（）【中科院计算所1998 二、1 （2分）】A．问题的规模 B. 待处理数据的初态 C. A和B3.计算机算法指的是（1），它必须具备（2）这三个特性。

(1) A．计算方法 B. 排序方法 C. 解决问题的步骤序列 D. 调度方法(2) A．可执行性、可移植性、可扩充性 B. 可执行性、确定性、有穷性C. 确定性、有穷性、稳定性D. 易读性、稳定性、安全性【南京理工大学1999 一、1（2分）【武汉交通科技大学1996 一、1（4分）】4．一个算法应该是（）。

【中山大学1998 二、1（2分）】A．程序B．问题求解步骤的描述C．要满足五个基本特性D．A和C.5. 下面关于算法说法错误的是（）【南京理工大学2000 一、1（1.5分）】A．算法最终必须由计算机程序实现B. 为解决某问题的算法同为该问题编写的程序含义是相同的C. 算法的可行性是指指令不能有二义性D. 以上几个都是错误的6. 下面说法错误的是（）【南京理工大学2000 一、2 （1.5分）】(1）算法原地工作的含义是指不需要任何额外的辅助空间（2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界（4）同一个算法，实现语言的级别越高，执行效率就越低A．(1) B.(1),(2) C.(1),(4) D.(3)7．从逻辑上可以把数据结构分为（）两大类。

【武汉交通科技大学1996 一、4（2分）】A．动态结构、静态结构B．顺序结构、链式结构C．线性结构、非线性结构D．初等结构、构造型结构8．以下与数据的存储结构无关的术语是（）。

【北方交通大学2000 二、1（2分）】A．循环队列 B. 链表 C. 哈希表 D. 栈9．以下数据结构中，哪一个是线性结构（）？【北方交通大学2001 一、1（2分）】A．广义表 B. 二叉树 C. 稀疏矩阵 D. 串10．以下那一个术语与数据的存储结构无关？（）【北方交通大学2001 一、2（2分）】A．栈 B. 哈希表 C. 线索树 D. 双向链表11．在下面的程序段中，对x的赋值语句的频度为（）【北京工商大学2001 一、10（3分）】FOR i:=1 TO n DOFOR j:=1 TO n DOx:=x+1;A．O(2n) B．O(n) C．O(n2) D．O (log2n)12．程序段FOR i:=n-1 DOWNTO 1 DOFOR j:=1 TO i DOIF A[j]>A[j+1]THEN A[j]与A[j+1]对换；其中n为正整数，则最后一行的语句频度在最坏情况下是（）A. O（n）B. O(nlogn)C. O(n3)D. O(n2) 【南京理工大学1998一、1(2分)】13．以下哪个数据结构不是多型数据类型（）【中山大学1999 一、3（1分）】A．栈B．广义表C．有向图D．字符串14．以下数据结构中，（）是非线性数据结构【中山大学1999 一、4】A．树B．字符串C．队D．栈15. 下列数据中，（）是非线性数据结构。