第1章 绪论

第1章绪论测试

1、研究数据结构就是研究( )。
    A、数据的逻辑结构
    B、数据的存储结构
    C、数据的逻辑结构和存储结构
    D、数据的逻辑结构、存储结构及其数据在运算上的实现

2、下面关于算法的说法,正确的是( )。
    A、算法最终必须由计算机程序实现
    B、为解决某问题的算法和为该问题编写的程序含义是相同的
    C、算法的可行性是指指令不能有二义性
    D、其它三项说法都是错误的

3、数据的( )结构包括集合、线性表、树和图4种基本类型。
    A、存储结构
    B、逻辑结构
    C、基本运算
    D、算法描述

4、下面算法的时间复杂度为( )。 for(i=0;i<m;i++) for(j=0;j<n;j++) A[i][j]=i*j;
    A、O(m*m)
    B、O(n*n)
    C、O(m*n)
    D、O(m+n)

5、数据的存储结构包括顺序、链式、散列和( )4种基本类型。
    A、向量
    B、数组
    C、集合
    D、索引

6、以下( )属于设计一个“好”的算法应考虑达到的目标。
    A、正确性
    B、可读性
    C、健壮性
    D、效率与低存储量要求

7、下列说法正确的有( )。
    A、算法和程序原则上没有区别,在讨论数据结构时二者通用
    B、从逻辑关系上讲,数据结构分为两大类:线性结构和非线性结构
    C、所谓数据的逻辑结构是指数据元素之间的逻辑关系  
    D、“同一数据逻辑结构中的所有数据元素都具有相同的特性”是指数据元素所包含的数据项的个数相等

8、依据所有数据成员之间的逻辑关系的不同,数据的逻辑结构的分类包括( )。
    A、非线性结构
    B、逻辑结构
    C、物理结构
    D、线性结构

9、在存储数据时,不仅要存储各数据元素的值,而且还要存储数据元素之间的关系。

10、数据的逻辑结构和数据的存储结构其含义是相同的。

11、在逻辑结构上定义的操作与具体实现有关。

12、算法是对解题方法和步骤的描述。

13、算法分析的两个主要方面是时间复杂度和空间复杂度的分析。

第2章线性表

第2章线性表测试

1、线性表是( )
    A、一个有限序列,可以为空。
    B、一个有限序列,不能为空。
    C、一个无限序列,可以为空。
    D、一个无限序列,不能为空。

2、若某线性表中最常用的操作是获取第i个元素和查找第i个元素的前驱,则采用( )存储方法最节省时间。
    A、顺序表
    B、单链表
    C、双向链表
    D、循环链表

3、单链表中,增加一个头结点的目的是为了( )。
    A、使单链表至少有一个结点
    B、标识链表中首结点的位置
    C、方便运算的实现
    D、说明单链表是线性表的链式存储

4、在带有头结点的单链表Head中,要向表头插入一个由指针p指向的结点,则执行( )。
    A、p->next=Head->next; Head->next=p;
    B、p->next=Head; Head=p;
    C、p->next=Head; p=Head;
    D、Head=p;p->next=Head;

5、在有n个数据元素的顺序表中,算法的时间复杂度是O(1)的操作是()。
    A、删除第i个元素(1≤i≤n)
    B、访问第i个元素(1≤i≤n)和求第i个结点的直接前驱(2≤i≤n)
    C、将n个元素从小到大排序
    D、在第i个元素后插入一个新结点(1≤i≤n)

6、下面关于线性表的叙述正确的是( )。
    A、线性表采用顺序存储必须占用一片连续的存储空间
    B、线性表采用链式存储不必占用一片连续的存储空间
    C、线性表采用链式存储便于插入和删除操作的实现
    D、线性表采用顺序存储便于插入和删除操作的实现 

7、下列( )不是顺序存储结构的优点。
    A、存储密度大
    B、插入运算方便
    C、可方便的用于各种逻辑结构的存储表示
    D、删除运算方便

8、线性表的顺序存储结构是一种可实现( )的存储结构。
    A、随机存取
    B、顺序存取
    C、索引存取
    D、散列存取

9、线性表的逻辑顺序和存储顺序总是一致的。

10、在线性表的顺序存储结构中,插入和删除时移动元素的个数与该元素的位置有关。

11、顺序存储结构只能存储线性结构,链式存储结构只能存储非线性结构。

12、线性表的链式存储结构优于顺序存储结构。

13、链式存储方式以指针表示元素间的逻辑关系。

顺序表的应用

1、假设某顺序表(a1,a2…,an)中无重复元素,试查找元素x在该顺序表升序排序后的位置。

链表应用

1、已知两个已经按升序排好的带头结点的单链表,要求将它们合并为一个升序排列的带头结点的单链表。要求按升序提供两个原始单链表的数据(均为整型),以输入-1为结束标志。

第3章 栈与队列

第3章栈与队列测试

1、栈的特点是( )
    A、先进后出
    B、先进先出
    C、进优于出
    D、出优于进

2、设循环队列的容量为20,序号从0到19,经过一系列的入队和出队后,front=5,rear=10,问队列中有多少个元素(采用少用一个队列存储空间的方式)( )。
    A、4
    B、5
    C、6
    D、7

3、一个队列的入队序列是1,2,3,4,则队列的出队序列是( )
    A、4,3,2,1
    B、1,2,3,4
    C、1,4,3,2
    D、3,2,4,1

4、一般情况下,将递归算法转换成等价的非递归算法应该设置( )
    A、栈
    B、队列
    C、栈或队列
    D、数组

5、设用链表作为栈的存储结构则退栈操作( )
    A、必须判别栈是否为满
    B、必须判别栈是否为空
    C、判别栈元素的类型
    D、对栈不作任何判别

6、已知一个栈的进栈序列是a1,a2,a3....an.其输出序列为1,2,3...n,若a3=1则a1为( )
    A、可能是2
    B、一定是2
    C、不可能是2
    D、不可能是3
    E、可能是3

7、以下说法中错误的是( )
    A、利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素,这种形式的栈称为顺序栈。
    B、top=-1时为空栈,元素进栈时指针top不断减1。
    C、当top等于数组最大下标时(top=MAXSIZE)则栈满。
    D、栈不能对输入序列部分或全局求逆。

8、以下说法中正确的是( )
    A、当队列中无数据元素时,称空队列。
    B、队列被称为“先进后出”表。
    C、栈是一种操作不受限制的线性表。
    D、栈是一种只允许在一端进行插入和删除的线性表。

9、同一个栈内的各个数据元素类型可以不一致。

10、入栈操作和入队列操作在链式存储结构上实现时一般不需要考虑溢出的情况。

11、若元素a,b,c,d,e,f依次进栈,允许进栈、退栈操作交替进行,则不可能得到出栈序列:a,f,e,d,c,b。

12、栈和队列都是限制存取位置的线性表。

13、在顺序栈空的情况下不能进行出栈操作,否则将产生“下溢”。

栈与队列应用

1、功能:对于一个已知的一个表达式字符串,函数功能功能检验其左右括号是否匹配。如果匹配则返回一个1否则返回0。

队列应用-数制转换

1、对于一个从键盘输入的一个十进制纯小数,将其转换为指定数制(2,8,16)的纯小数并输出转换后的结果。下列代码给出队列的基本操作函数并提供了主函数,请完善函数void NumConve(float x,int r,int n),以实现将纯十进小数x转换为r进制的纯小数,要求至多保留n位小数。

第4章串

第4章串测试

1、若串S=”software”,其子串的数目是( )。
    A、8
    B、37
    C、36
    D、9

2、下面( )不是 “abcd321ABCD”的子串( )。
    A、abcd
    B、321AB
    C、abcAB
    D、21AB

3、已知模式串为“aaab”,其next数组值为( )
    A、-1,0,1,2
    B、0,0,1,2
    C、0,1,2,0
    D、-1,1,0,0

4、设主串为“abccdcdccdbaa”,模式串为“cdcc”,用BF算法在第( )次匹配成功
    A、4
    B、5
    C、6
    D、7

5、设串s1=“ABCDEFG”,s2=“12345”,用字符数组从0下标位置存储,函数strcat(s, t)返回s和t串的连接串,strsub(s, i, j)返回串s中从第i个字符开始的连续j个字符组成的子串,strlen(s)返回串s的长度,则strcat(strsub(s1, 2, strlen(s2)), strsub(s1, strlen(s2),2))的结果是( )
    A、CDEFG12
    B、BCDEFG1
    C、CD12345
    D、CDEFGFG

6、串是一种特殊的线性表,下列( )并不是串这个数据结构所特有的特性。
    A、可以顺序存储
    B、数据元素是字符型数据
    C、可以链接存储
    D、数据元素可以是非字符数据

7、以下关于串的说法中错误的是( ) 。
    A、串是一种特殊的线性表
    B、串的长度必须大于零
    C、串中的元素只能是字母
    D、空串就是空白串

8、两个串相等必须满足的条件是( )
    A、串长度相等
    B、串中的各位置字符任意
    C、串中各位置字符均对应相等
    D、串长度不相等
    E、串长度任意

9、KMP算法的特点是在模式匹配时指示主串的指针不会变小。

10、假如两个串用两个一维字符数组存储,两个串比较大小时可以使用关系运算符进行整体比较。

11、串的存储可以采用顺序存储也可以用链表存储,用链式存储比顺序存储占用空间大。

12、设有两个串P和Q,其中Q是P的子串,把Q在P中首次出现的位置作为子串Q在P中的位置的算法称为模式匹配算法。

13、设模式串(子串)的长度为m,目标串(主串)的长度为n。当n≈m且处理只匹配一次的模式时,简单模式匹配(BF)算法所花费的时间代价也可能会比KMP算法更节省。

第5章数组与广义表

第5章数组与广义表测试

1、下面说法不正确的是( )
    A、广义表的表头总是一个广义表
    B、广义表的表尾总是一个广义表
    C、广义表难以用顺序结构存储
    D、广义表可以是一个多层次结构

2、设二维数组A[0~m][0~n]按行优先顺序存储在内存中,第一个元素的地址为p,每个元素占k个字节,则a[i][j]的地址为( )
    A、p + (i*n+j)*k
    B、p + ((i-1)*n+j-1)*k
    C、p + ((j-1)*n+i-1)*k
    D、p + (j*n+i-1)*k

3、设有一个10阶的下三角矩阵A(包括对角线),按照从上到下、从左到右的顺序存储到连续的55个存储单元中,每个数组元素占1个字节的存储空间,则A[5][4]地址与A[0][0]的地址之差为( )
    A、10
    B、19
    C、28
    D、55

4、在稀疏矩阵的带行指针向量的链接存储中,每个单链表中的结点都具有相同的( )
    A、行号
    B、列号
    C、元素值
    D、非零元素个数

5、对行下标由1到50、列下标由1到80的二维数组a,若该数组的起始地址为2000且每个元素占2个存储单元,并以行为主序顺序存储,则元素a[45][68]的存储地址为( )
    A、9172
    B、9173
    C、9174
    D、9175

6、以下不属于数组操作的是( )
    A、存取
    B、修改
    C、插入
    D、删除
    E、查找

7、以下属于特殊矩阵的是( )
    A、对角矩阵
    B、上三角矩阵
    C、下三角矩阵
    D、对称矩阵

8、广义表((a), (a))的表头和表尾是( )
    A、a
    B、b
    C、(a)
    D、((a))

9、属于常见的稀疏矩阵的压缩存储的方法是( )
    A、三元组存储
    B、十字链表存储
    C、顺序存储
    D、索引存储

10、广义表中元素的个数即为广义表的深度。

11、广义表中原子个数即为广义表的长度。

12、数组的存储结构是一组连续的内存单元。

13、数组可看成线性结构的一种推广,因此与线性表一样,可以对它进行插入,删除等操作。

14、稀疏矩阵压缩存储后,必会失去随机存取功能。

第6章树与二叉树

第6章树与二叉树测试

1、一棵完全二叉树上有1001个结点,其叶子结点的个数是()。
    A、250
    B、500
    C、505
    D、都不对

2、一棵有124个叶结点的完全二叉树最多有( )个结点。
    A、247
    B、248
    C、249
    D、250

3、在n个结点的线索二叉树中,线索的数目为( )。
    A、n-1
    B、n
    C、n+1
    D、2n

4、设有13个值,用它们组成一棵哈夫曼树,则该哈夫曼树共有( )个结点。
    A、13
    B、12
    C、26
    D、25

5、树的基本遍历策略可分为先根遍历和后根遍历,而二叉树的基本遍历策略可分为先序、中序和后序这三种遍历。我们把由树转化得到的二叉树称为该树对应的二叉树,则下面( )是正确的。
    A、树的先根遍历与其对应的二叉树先序遍历序列相同
    B、树的后根遍历与其对应的二叉树后序遍历序列相同
    C、树的先根遍历与其对应的二叉树中序遍历序列相同
    D、以上都不对

6、完全二叉树()。
    A、适合于顺序存储结构存储
    B、不一定适合顺序存储结构存储
    C、叶子结点可在任一层出现
    D、某结点有左子树时则必有右子树
    E、某结点有右子树时则必有左子树

7、对于二叉树,下列描述正确的是()
    A、边的个数比结点个数少1个
    B、叶子结点数目比度数为2的结点数目多1个
    C、
    D、n个结点共有n-1个非空指针域
    E、一定有度数为1的结点
    F、高度为k的二叉树结点数最多时一定是满二叉树

8、关于哈夫曼编码的说法正确的是( )
    A、不允许出现频度相同的字符
    B、两个频度相同的字符其编码长度一定相等
    C、是一种最佳编码
    D、编码无二义性
    E、WPL最小

9、存在这样的二叉树,对它采用任何次序进行遍历得到的结果都相同。()。

10、二叉树就是结点度为2的有序树。()

11、若一个结点是二叉树子树的中序遍历序列中的最后一个结点,则它必是该子树的先序遍历序列中的最后一个结点。()

12、

13、线索二叉树的左线索指向其某种遍历序列的直接前驱结点,右线索指向其某种遍历序列的直接后继结点。()

二叉树的遍历的应用

1、利用先序遍历算法创建二叉树并查找二叉树指定结点的双亲结点。

二叉树的遍历的应用2

1、利用先序遍历创建二叉树,中序遍历为升序,使得插入一个结点后,中序遍历仍为升序。

第7章图

第7章图的测试

1、无向图的邻接矩阵是( )矩阵
    A、下三角
    B、上三角
    C、稀疏
    D、对称

2、用邻接表存储的图所用空间大小( )
    A、与图的顶点数和边数都有关
    B、只与图的边数有关
    C、只与图的顶点数有关与边数的平方有关
    D、与边数的平方有关

3、不论基于图的邻接表还是基于邻接矩阵存储,图的广度优先遍历算法类似于树的( )。
    A、中序遍历
    B、先序遍历
    C、后序遍历
    D、层次遍历

4、一个连通图的生成树是包含该图的所有顶点的( )
    A、极小连通子图
    B、极小子图
    C、极大连通子图
    D、极大子图

5、具有n个顶点的连通有向图中,至少需要( )条边。
    A、n-1
    B、n
    C、n+1
    D、2n

6、下列哪些算法是属于图的应用算法( )。
    A、克鲁斯卡尔(Kruskal)算法
    B、哈夫曼(Huffman)算法
    C、迪杰斯特拉(Dijkstra)算法
    D、欧几里德算法
    E、拓扑排序算法

7、下列( )算法可用于构造图的生成树。
    A、Prim
    B、kruskal
    C、Floyd
    D、BFS
    E、DFS

8、下列( )是构造最短路径的方法。
    A、Floyd
    B、Prim
    C、Kruskal
    D、Dijkstra
    E、BFS

9、n个结点的无向图,若没有顶点到自身的边,也没有一个顶点到另一个顶点的多重边,此时若有n(n-1)/2条边 ,则该无向图一定是连通图。

10、用邻接矩阵存储一个图时,在不考虑压缩存储的情况下,所占用空间大小与图的顶点数有关,与图的边数无关。

11、对于任意一个图,从它的某个顶点出发进行一次深度或者广度遍历可以访问到该图的每个顶点。

12、对于无向图连通网的生成树,从同一顶点出发所得的生成树相同。

13、有向图中顶点v的度是其邻接矩阵中顶点v所对应行中非0元素的个数。

图的遍历

1、以下是无向无权连通图的深度优先搜索程序,但深度优先搜索函数void DFS(Graph *p, int v)未完成编写,请将其补充完整,并确保程序正常运行。

第8章查找

第8章查找测试

1、衡量一个查找算法执行效率高低的最重要的指标是( )。
    A、查找表中的元素个数
    B、查找过程中关键字比较的最大次数
    C、所需的内存大小
    D、平均查找长度

2、对线性表进行二分查找时,要求线性表必须 ( )。
    A、采用顺序存储结构
    B、采用顺序存储结构且元素按查找关键字有序排列
    C、采用链接存储结构
    D、采用链接存储结构且结点按查找关键字有序排列

3、哈希查找中的冲突是指( ).
    A、两个元素具有相同序号
    B、两个元素的关键字值不同
    C、不同关键字值的元素对应相同的存储地址
    D、两个元素的关键字值相同

4、对于一棵二叉排序树进行( )遍历可得到按关键字有序排列的数据序列。
    A、先序
    B、中序
    C、后序
    D、层序

5、顺序查找适合于采用( )存储结构的线性表。
    A、散列
    B、压缩
    C、索引
    D、顺序或链式

6、下面关于哈希查找的说法中,正确的是( )
    A、采用链地址法处理冲突时,查找任何一个元素的时间都相同
    B、采用链地址法处理冲突时,若规定采用头插法进行插入,则插入任何一个元素的时间是相同的
    C、用链地址处理冲突,不会引起二次聚集的现象
    D、用链地址处理冲突,适合表长不确定的情况
    E、链地址法处理冲突的平均查找长度小于线性探测和二次探测

7、以下关于二叉排序树的说法中,正确的是( )
    A、在二叉排序树上的查找过程与折半查找过程类似
    B、二叉排序树中左子树上所有结点的关键字值均小于它的根结点
    C、二叉排序树中右子树上所有结点的关键字值均大于它的根结点
    D、对某棵二叉排序树进行中序遍历,一定能得到按关键字升序排列的有序序列
    E、二叉排序树一定为一棵平衡二叉树

8、在一个结点值按照查找关键字有序排列的单链表上可以采用折半查找方法来提高查找速度。

9、折半查找过程所对应的判定树一定是一棵平衡二叉树。

10、在任意一个数据表上,采用折半查找一定比采用顺序查找的查找速度快。

11、在结点数确定的二叉排序树上进行查找的平均查找长度与二叉树的形态有关,最好的情况是二叉排序树为平衡二叉树的时候。

12、折半查找的效率与二叉排序树的查找效率是一样的。

折半查找算法设计题

1、编写折半查找函数BinSearch,实现在一个按学号降序排列的学生信息顺序表上查找指定学号学生的功能。请在以下代码基础上完成BinSearch函数的编写及在主函数对BinSearch函数的调用。

第9章排序

第9章排序测试

1、对同一组数据分别采用直接插入排序和折半插入排序进行排序,二者可能存在的不同之处在于( )。
    A、排序的总趟数
    B、占用的辅助内存空间大小
    C、整个排序过程中的关键字比较次数
    D、整个排序过程中的元素移动次数

2、希尔排序属于( )类排序方法。
    A、插入
    B、选择
    C、交换
    D、归并

3、堆排序中所采用的堆在内存中存储的形态为一棵( )。
    A、二叉排序树
    B、完全二叉树
    C、平衡二叉树
    D、满二叉树

4、以下关于排序算法的说法中正确的是( )。
    A、稳定的排序算法执行效率优于不稳定的排序算法
    B、排序算法都是应用在顺序表上的,在链表上无法应用
    C、在顺序表上可以应用的排序算法都可以应用在链表上
    D、对同一组数据采用不同的排序算法,排序的结果有可能不同

5、n个元素构成的降序顺序表,采用冒泡排序按照关键字升序排列时共需进行( )趟排序。
    A、n-1
    B、1
    C、log2n
    D、趟数不确定

6、以下排序方法中,排序的趟数与数据表的初始排列顺序无关的是( )。
    A、冒泡排序
    B、快速排序
    C、直接插入排序
    D、简单选择排序
    E、堆排序

7、以下排序方法中,具有稳定性的是( )。
    A、冒泡排序
    B、快速排序
    C、直接插入排序
    D、希尔排序
    E、堆排序
    F、折半插入排序
    G、简单选择排序

8、以下排序方法中,空间复杂度为O(1)的是( )。
    A、冒泡排序
    B、快速排序
    C、直接插入排序
    D、希尔排序
    E、堆排序

9、若采用某种排序方法对某一组数据进行排序后,关键字值相同的元素的相对次序与排序前保持一致,则说明该排序算法具有稳定性。

10、在外排序中需要使用外存储器来保存待排序的数据。

11、空间复杂度是衡量排序算法在执行过程中存储全部待排序数据所使用的总空间大小的一个指标。

12、对于任意一组数据,采用折半插入排序时的关键字比较次数一定小于直接插入排序。

13、快速排序当数据表每次划分得到的子表长度均衡时,算法的效率最高,时间复杂度为O(n)。

冒泡排序算法设计题

1、编写冒泡排序函数BubbleSort实现对一个整型顺序表的降序排列,并在函数中输出排序的各趟结果。

期末考试

数据结构客观题试卷

1、数据结构在计算机内存中的表示是指( )。
    A、数据的存储结构
    B、数据结构
    C、数据的逻辑结构
    D、数据元素之间的关系

2、在存储数据时,不仅要考虑存储各数据元素的值,而且还要存储( )。
    A、数据处理的方法
    B、数据元素的类型
    C、数据元素之间的关系
    D、数据的存储方法

3、算法计算量的大小称为算法的( )。
    A、效率
    B、时间复杂度
    C、现实性
    D、难度

4、数据结构是一门研究非数值计算的程序设计问题中计算机的数据元素以及它们之间的( )和运算等的学科。
    A、结构
    B、关系
    C、运算
    D、算法

5、某算法的所有语句频度之和为(3n+nlog2n+n*n+8), 其时间复杂度度表示为( )。
    A、O(n)
    B、O(nlog2n)
    C、O(n*n)
    D、O(log2n)

6、抽象数据类型的三个组成部分分别为( )。
    A、数据对象、数据关系和基本操作
    B、数据元素、逻辑结构和存储结构
    C、数据项、数据元素和数据类型
    D、数据元素、数据结构和数据类型

7、在单链表的一个结点中有( )个指针。
    A、1
    B、2
    C、0
    D、3

8、使用双向链表存储数据,其优点是可以( )。
    A、提高检索速度
    B、很方便地插入和删除数据
    C、结约存储空间
    D、很快回收存储空间

9、在带有头结点的单链表Head中,要向表头结点之后插入一个由指针p指向的结点,则执行( )。
    A、p->next=Head->next; Head->next=p;
    B、p->next=Head; Head=p;
    C、p->next=Head; p=Head;
    D、Head=p;p->next=Head;

10、线性表L在( )情况下适合用链式存储结构实现。
    A、需经常修改L中的结点值
    B、需要对L频繁进行删除插入
    C、L中含有大量的结点
    D、L中结点结构复杂

11、链式的每个结点中的信息( )。
    A、只有一部分,存储表示结点间关系的指针。
    B、分两部分,一部分存放元素值,另一部分存放表示结点间关系的指针
    C、分两部分,一部分存放元素值,另一部分存放结点所占单元数
    D、只有一部分,存放元素值

12、在n个结点的顺序表中,其时间复杂度是O(1)的操作是()。
    A、删除第i个元素(1≤i≤n)
    B、访问第i个元素(1≤i≤n)和求第i个结点的直接前驱(2≤i≤n)
    C、将n个元素从小到大排序
    D、在第i个元素后插入一个新结点(1≤i≤n)

13、一棵非空的二叉树其先序遍历序列与后序遍历序列正好相反,则该二叉树一定满足( )
    A、所有的结点均无左孩子
    B、所有的结点均无右孩子
    C、该二叉树一定只有一个叶子结点
    D、是任意一棵二叉树

14、下面几个符号串编码集合中,不是前缀编码的是( )。
    A、{0,10,110,1111}
    B、{11,10,001,101,0001}
    C、{00,010,0110,1000}
    D、{b,c,aa,ac,aba,abb,abc}

15、设输入序列为1、2、3、4、5、6,则通过栈的操作后可以得到的输出序列为( )
    A、5,3,4,6,1,2
    B、3,2,5,6,4,1
    C、3,1,2,5,4,6
    D、1,5,4,6,2,3

16、一个顺序栈一旦定义,那么它的大小是()
    A、固定的
    B、可以改变
    C、不能固定
    D、动态变化

17、若用一个大小为6的数组实现循环队列(少用一个队列存储空间的实现方式),且当前rear和front的值分别为0和3,当从队列中删除两个元素,再加入一个元素后,rear和front的值分别是多少?( )。
    A、1和5
    B、2和4
    C、4和2
    D、5和1

18、允许对队列进行的操作有( )。
    A、对队列中的元素排序
    B、取出最近进入队列的元素
    C、在队头之前插入元素
    D、删除队头元素

19、若一个栈以数组A[1...n]存储,初始化栈顶指针为n+1,则下面将元素x入栈的正确代码是( )。
    A、top = top +1; A[top] = x;
    B、A[top] = x; top = top + 1;
    C、top = top -1; A[top] = x;
    D、A[top] = x; top = top - 1;

20、串是一种特殊的线性表,其特殊性体现在( )
    A、可以顺序存储.
    B、数据元素是一个字符
    C、可以链式存储
    D、数据元素可以有多个

21、若串S=”software”,其子串的数目是( )
    A、8
    B、37
    C、36
    D、9

22、下面说法中,只有( )是正确的.
    A、字符串的长度是指串中包含字母的个数
    B、字符串的长度是指串中包含不同字符的个数
    C、若T包含在S中,则T一定是S的一个子串
    D、一个字符串不能说是它自身的一个子串

23、字符串的长度是指( )。
    A、串中不同字符的个数
    B、串中不同字母的个数
    C、串中所含字符的个数
    D、串中不同数字的个数

24、设有两个串S1和S2,求S1在S2中首次出现的位置的运算称为( )
    A、求子串
    B、判断是否相等
    C、模式匹配
    D、连接

25、深度为5的满二叉树有( )个叶子结点。
    A、14
    B、15
    C、16
    D、17

26、设一棵完全二叉树共有700个结点,则该完全二叉树中的叶子结点数为( )。
    A、348
    B、349
    C、350
    D、351

27、某二叉树共有7个结点,其中叶子结点只有1个,则该二叉树的深度为( )?(假设根结点在第一层)
    A、2
    B、3
    C、5
    D、7

28、若已知一棵二叉树的前序序列是BEFCGDH,中序序列是FEBGCHD,则它的后序序列是( )。
    A、FEGHDCB
    B、EFCGDHB
    C、FEGCHDB
    D、FEGDHCB

29、若二叉树采用二叉链表存储结构,要交换其所有分支结点左、右子树的位置,利用( )遍历算法是最最合适的。
    A、先序
    B、中序
    C、后序
    D、按层次

30、任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序()。
    A、不发生改变
    B、发生改变
    C、不能确定
    D、其它三个都不对

31、设a、b为一棵二叉树上的两个结点,则中序遍历时a在b前面的条件是( )。
    A、a在b的右方
    B、a在b的左方
    C、a是b的祖先
    D、a是b的子孙

32、有n个权重构造的哈夫曼树中共有( )个结点。
    A、2n-1
    B、2n
    C、2n+1
    D、n+1

33、设T是一棵哈夫曼树,具有5个叶子结点,树T的高度最高可以是( )。
    A、3
    B、4
    C、5
    D、6

34、由权重为8,4,5,7的叶子结点构造的哈夫曼树,该树的带权路径长度为( )。
    A、24
    B、36
    C、48
    D、72

35、在一个无向图中,所有顶点的度数之和等于边数的( )倍。
    A、1/2
    B、2
    C、1
    D、4

36、具有6个顶点的无向图,当有( )条边时才能确保它是一个连通图。
    A、8
    B、9
    C、10
    D、11

37、一个有n个顶点的无向连通图,其边的个数至少有( )
    A、n-1
    B、n
    C、n+1
    D、2n

38、对图的邻接表的叙述中,( )是正确的。
    A、无向图的邻接表中第i个顶点的度为第i个边链表中结点数的2倍
    B、邻接表比邻接矩阵的操作更简便
    C、邻接矩阵比邻接表的操作更简便
    D、求有向图结点的度,必须遍历整个邻接表

39、任何一个无向连通图的最小生成树( )。
    A、只有一棵
    B、一棵或多棵
    C、一定有多棵
    D、可能不存在

40、求单源最短路径的Dijkstra算法的时间复杂度为( )
    A、O(n)
    B、O(n+e)
    C、O(n2)
    D、O(n*e)

41、下列关于无向连通图的特性叙述中,正确的是( ) Ⅰ 所有顶点的度之和为偶数 Ⅱ 边数大于顶点数减1 Ⅲ 至少有一个顶点的度数为1
    A、只有Ⅰ
    B、只有Ⅱ
    C、Ⅰ和Ⅱ
    D、Ⅰ和Ⅲ

42、设无向图的顶点数为n,则该图最多有( )条边
    A、n-1
    B、n(n-1)/2
    C、n(n+1)/2
    D、n(n+1)

43、对7个元素构成的线性表进行快速排序时,在最差情况下共需进行( )次关键字比较。
    A、18
    B、20
    C、21
    D、23

44、堆排序属于( )类排序方法。
    A、插入
    B、选择
    C、交换
    D、归并

45、对序列{15,9,7,8,20,-1,4}进行一趟排序后结果为{9,15,7,8,20,-1,4},则采用的是( )排序。
    A、简单选择
    B、堆
    C、直接插入
    D、冒泡

46、用希尔排序方法对一个数据序列进行升序排序时,若第1趟排序结果为9,1,4,13,7,8,20,23,15,则该趟排序采用的增量(间隔)可能是( )。
    A、2
    B、3
    C、4
    D、5

47、对7个元素构成的线性表进行快速排序时,在最好情况下共需进行( )次划分。
    A、6
    B、5
    C、4
    D、3

48、下列排序方法的执行过程中,占用内存空间最大的是( )。
    A、堆排序
    B、归并排序
    C、希尔排序
    D、快速排序

49、从未排序的序列中依次取出一个元素与已排序序列中的元素进行比较,然后将其放在已排序序列的合适位置,该排序方法称为( )。
    A、插入排序
    B、冒泡排序
    C、快速排序
    D、选择排序

50、下列排序方法中关键字比较次数与记录初始排列状态无关的是( )。
    A、简单选择排序
    B、直接插入排序
    C、冒泡排序
    D、快速排序

51、一组关键字为(46,79,56,38,40,84),则利用堆排序的方法建立大顶堆的初始堆为( )。
    A、79,46,56,38,40,84
    B、84,79,56,38,40,46
    C、84,79,56,46,40,38
    D、84,56,79,40,46,38

52、采用递归方式对顺序表进行快速排序,下列关于递归次数的叙述中,正确的是( )。
    A、递归次数与初始数据的排列次序无关
    B、每次划分后,先处理较长的子表可以减少递归次数
    C、每次划分后,先处理较短的子表可以减少递归次数
    D、递归次数与每次划分后得到的子表处理次序无关

53、二维数组A的每个元素是由6个字符组成的串,其行下标i=0,1,…,8,列下标j=1,2,…,10。若数组A以行为主序存储,元素A[8][5]的起始地址与数组A以列为主序存储时的元素( )的起始地址相同(设每个字符占一个字结)。
    A、A[8][5]
    B、A[3][10]
    C、A[5][8]
    D、A[0][9]

54、稀疏矩阵一般的压缩方法有( )两种。
    A、二维数组和三维数组
    B、三元组和散列表
    C、三元组和十字链表
    D、散列表和十字链表

55、已知二维数组的行下标i=-3,-2,-1,0,…,5,列下标j=0,1,…,10,则该数组含有的元素个数为( )
    A、88
    B、99
    C、80
    D、90

56、已知一个三对角矩阵A的行、列下标均由1到100,并以行为主序存入下标由1到298的一维数组B中。则A中元素a[66][65]在数组B中的位置k为( ) 。
    A、198
    B、195
    C、197
    D、185

57、广义表(a,(a,b),d,e,((i,j),k))的长度是( )。
    A、5
    B、8
    C、6
    D、7

58、设有一个10阶对称矩阵A采用压缩存储方式(以行为主序存储,行、列下标从0开始,第一个数据元素为a(0,0),则a(8,5)的存储地址为( )。(每个元素占一个字节)
    A、40
    B、41
    C、42
    D、43

59、一个n*n的对称矩阵,如果以行或列为主序放入内存,则容量为( )。
    A、n*n
    B、n*n/2
    C、n*(n+1)/2
    D、(n+1)*(n+1)/2

60、对稀疏矩阵进行压缩的目的是( )。
    A、便于进行矩阵运算
    B、便于输入和输出
    C、节省存储空间
    D、降低运算的时间复杂度

61、已知广义表L=((a,b,c),(d,e,f)),运用head和tail取表头和表尾两种操作,取出L中的原子e的过程是( )。
    A、head(tail(L))
    B、tail(head(L))
    C、head(tail(head(tail(L))))
    D、head(tail(tail(head(L))))

62、设广义表L=((a,b,c)),则L的长度和深度分别为( )。
    A、1和1
    B、1和3
    C、2和3
    D、1和2

63、有一个表长为50的哈希表,若采用除留余数法构造哈希函数,即哈希函数形式为:H(k)=k%P,为使哈希函数具有较好的性能,则一般情况下除数P的值应选取( )。
    A、49
    B、47
    C、51
    D、50

64、按照以下关键字序列创建二叉排序树,与其它三个序列所创建的二叉排序树不同的是( )。
    A、{4,3,2,1,6,8,5}
    B、{4,3,6,2,1,5,8}
    C、{4,3,6,1,2,8,5}
    D、{4,3,6,5,2,1,8}

65、在一棵二叉排序树上查找指定关键字值的元素,在等概率条件下查找成功时的时间复杂度大致为( )。
    A、O(n2)
    B、O(n)
    C、O(log2n)
    D、O(nlog2n)

66、在结点数确定的二叉排序树上进行查找的平均查找长度与二叉树的形态有关,最差的情况是二叉排序树为( )二叉树的时候。
    A、满
    B、完全
    C、平衡
    D、单支树

67、若某线性表中最常用的操作是取第i个元素和查找第i个元素的前驱,则采用( )存储方法最结省时间。
    A、顺序表
    B、单链表
    C、双向链表
    D、循环链表

68、下列选项中,不可能构成折半查找过程中关键字比较序列的是( )。
    A、500,200,450,180
    B、500,450,200,180
    C、180,500,200,450
    D、180,200,500,450

69、设有一个按照查找关键字有序排列且表长大于2的顺序表,分别采用顺序查找和二分查找来查找关键字值等于k的元素,比较的次数分别是s和b。在查找不成功的情况下,正确的s和b的数量关系是( )。
    A、总有s=b
    B、总有s>b
    C、总有s<b
    D、与k值大小有关

70、静态查找表与动态查找表的根本区别在于( )。
    A、逻辑结构不同
    B、施加在其上的操作不同
    C、所包含的数据元素类型不同
    D、存储结构不同

71、对于n(n>=2)个权重互不相同的字符构造的哈夫曼,下面说法不正确的是( )。
    A、该树一定是完全二叉树
    B、树中一定没有度数为1的结点。
    C、树中两个权重最小的结点一定是亲兄弟。
    D、树中任意一个分支结点的权重一定不小于下一层任意结点的权重。

72、把一棵结点次序确定的树转换为二叉树,相同的转换规则下转换后的二叉树的形态是( )。
    A、唯一的。
    B、有多种。
    C、有多种,但根结点都没有左孩子。
    D、有多种,但根结点都没有右孩子。

73、下列选项中,以下不可能是折半查找过程中形成的关键字比较的序列是( )。
    A、500,200,450,180
    B、500,450,200,180
    C、180,500,200,450
    D、180,200,500,450

74、以下( )属于设计一个“好”的算法应考虑达到的目标。
    A、正确性
    B、可读性
    C、健壮性
    D、效率与低存储量要求

75、下列( )结构是非线性结构 ?  
    A、图
    B、队列
    C、线性表
    D、树

76、下列说法正确的有( )。
    A、算法和程序原则上没有区别,在讨论数据结构时二者通用
    B、从逻辑关系上讲,数据结构分为两大类:线性结构和非线性结构
    C、所谓数据的逻辑结构是指数据元素之间的逻辑关系  
    D、“同一数据逻辑结构中的所有数据元素都具有相同的特性”是指数据元素所包含的数据项的个数相等
    E、数据的逻辑结构与数据元素本身的内容和形式无关

77、下面的叙述不正确的是()。
    A、线性表在链式存储时,查找第i个元素的时间同i值无关
    B、线性表在链式存储时,查找第i个元素的时间同i值成正比
    C、线性表在顺序存储时,查找第i元素的时间同i值无关
    D、线性表在顺序存储时,查找第i个元素的时间同i值成正比

78、对表中任一结点都可访问其直接前驱和直接后继的是()
    A、双向静态链表
    B、单链表
    C、顺序表
    D、双链表
    E、循环链表

79、下列关于链式存储结构,那一项是正确的( )
    A、结点除自身信息外还包括指针域,因此存储密度小于顺序存储结构
    B、逻辑上相邻的结点物理上不必邻接
    C、可以通过计算直接确定第i个结点的存储地址
    D、插入、删除操作方便,不必移动结点

80、循环队列是( )
    A、顺序存储结构
    B、不会产生下溢
    C、不会产生上溢
    D、队满时有rear=front
    E、不会产生假溢出

81、两个串相等必须同时有下列条件( )
    A、串长度相等
    B、串中的各位置字符任意
    C、串中各位置字符均对应相等
    D、串长度不相等
    E、串长度任意

82、在以下关于串的说法中正确和是( )
    A、空串中没有任何字符
    B、子串一定全部包含在主串中
    C、元素都是字符
    D、两个串可以像数值那样比较大小

83、串可以用以下方法存储( )
    A、顺序存储
    B、链式存储
    C、块链存储
    D、索引存储

84、以下说法中正确的是( ) 
    A、无向图中极大连通子图称为连通分量
    B、连通图的广度优先搜索中一般采用队列来暂存访问过的顶点
    C、图的深度优先搜索中一般采用栈来暂存刚访问的顶点
    D、有向图的遍历不可采用广度搜索方法

85、在用Kruskal算法求解带权连通图的最小生成树时,选择边应该同时满足的条件包含:( )。
    A、重边
    B、有向环
    C、该边不能在图中最小生成树中构成回路
    D、权值重复的边
    E、权值最小的

86、可以作为判断一个有向图是否有回路的方法有( )。
    A、深度遍历
    B、广度遍历
    C、拓扑排序
    D、求最短路径
    E、求关键路径

87、下面关于哈希查找的说法中,不正确的是( )。
    A、哈希函数构造得越复杂则冲突越少
    B、哈希查找的平均查找长度与哈希表中的元素个数有关
    C、除留余数法是所有哈希函数中最好的
    D、不存在特别好与坏的哈希函数,应根据实际数据选择最适合的哈希函数
    E、哈希函数的值域必须在表长范围内

88、以下关于折半查找的说法,正确的是( )。
    A、折半查找只适用于顺序表
    B、在某个有序顺序表上查找任意指定关键字的元素时,采用折半查找一定比顺序查找所需的关键字比较次数少
    C、折半查找不适用于元素频繁变化的顺序表
    D、折半查找的平均时间复杂度低于顺序查找
    E、折半查找的判定树一定为一棵完全二叉树

89、以下排序方法中,属于交换排序的是( )。
    A、冒泡排序
    B、快速排序
    C、希尔排序
    D、堆排序

90、下面结论正确的是( )。
    A、一个广义表的表头肯定不是一个广义表
    B、一个广义表的表尾肯定是个广义表
    C、广义表L=((),(A,B))的表头为空表
    D、广义表中原子个数即为广义表的长度

91、三元组表中的每个结点对应于稀疏矩阵的一个非零元素,它包含的数据项有:( )。
    A、行号
    B、列号
    C、数据
    D、总行数

92、已知广义表L=(((a))),则L的表头与表尾是( )。
    A、a
    B、(a)
    C、((a))
    D、()

93、一棵二叉树的组成可描述成( )。
    A、根结点、左子树、右子树
    B、度数为0的结点,度数为1的结点和度数为2的结点
    C、右子树
    D、叶子结点
    E、右子树

94、在逻辑结构定义的操作与具体实现有关。

95、数据结构概念包括数据的逻辑结构、数据在计算机中的存储结构以及数据的运算三个方面。

96、算法分析的两个主要方面是时间复杂度和空间复杂度的分析。

97、数据的存储结构是指数据在计算机内的物理存储形式。

98、算法是对解题方法和步骤的描述。

99、数据的逻辑结构是依赖于计算机的。

100、从逻辑关系上讲,数据结构主要分为线性结构和非线性结构两类。

101、数据的存储结构是数据的逻辑结构的存储映像。

102、数据的逻辑结构和数据的存储结构是相同的。

103、顺序存储方式插入和删除时效率太低,因此它不如链式存储方式好。

104、线性表就是顺序存储的表。

105、循环链表是线性表的一种存储方式。

106、在链表中进行插入、删除操作时,比在顺序表中效率高。

107、双向链表可随机访问任一结点。

108、在单链表中,给定任一结点的地址 p ,则可用下述语句将新结点 s 插入结点 p 的后面: p->next=s; s->next=p->next;

109、在顺序栈满的情况下不能做进栈操作,否则将产生“上溢”

110、即使对不含相同元素的同一输入序列进行两组不同的入栈和出栈操作,所得到的输出序列也一定相同。

111、在循环队列中,front指向队头,rear指向队尾元素的后一个位置,则队满条件是front==rear。

112、栈可作为函数调用的一种数据结构。

113、队列的操作特点是后进先出。

114、串的长度是指串中不同字符的个数。

115、串是由有限个字符构成的连续序列,子串是主串中任意个连续字符构成的有限序列。

116、空串与空格串是相同的。

117、KMP算法的特点是在模式匹配时指示主串的指针不会变小。

118、串相等是指两个串中字符个数相等且各对应位置上的字符也一一相等。

119、一棵具有257个结点的完全二叉树,它的深度是8。

120、树与二叉树的一个区别是树中结点的最大度数没有限制,而二叉树结点的最大度数为2。

121、用二叉链表法存储包含n个结点的二叉树,结点的2n个指针区域中有n+1个为空指针。

122、具有12个结点的完全二叉树有5个度为2的结点。

123、已知二叉树的中序遍历序列是DBGEAFHC,后序遍历序列是DGEBHFCA,则前序遍历序列是ABDGECFH。

124、由3个结点所构成的二叉树有6种形态。

125、完全二叉树的某结点若无左孩子,则它必是叶结点。

126、kruskal算法是一种贪心算法。

127、利用Dijkstra算法求每一对顶点之间的最短路径时间复杂度为

128、对于一个有向图,除了拓扑排序的方法外,还可以通过对有向图进行深度优先遍历的方法来判断有向图是否有回路存在。

129、一个图的广度优先生成树是唯一的。

130、不同的求最小生成树的方法得到的最小生成树相同。

131、需要借助一个队列实现DFS算法。

132、无向图的邻接矩阵一定是对称的,而有向图的邻接矩阵一定是非对称的。

133、强连通图的各顶点间均可达。

134、在一个表长为n的线性表上进行顺序查找,当元素查找关键字分别排列有序和无序时其平均查找长度不同

135、快速排序当数据表初态为有序排列时,算法的效率最低,时间复杂度为

136、内排序方法要求数据一定要以顺序方式存储。

137、对于任意一组数据,采用折半插入排序时的元素移动次数与直接插入排序完全相同。

138、排序的稳定性是指排序算法中比较次数保持不变且算法能够终止。

139、任何无向图都存在生成树。

140、广义表中的单元素(原子)个数即为广义表的长度。

141、一个稀疏矩阵Am×n采用三元组形式表示。若把三元组中有关行下标与列下标的值互换,并把m和n值互换,就完成了Am×n的转置运算。

142、数组是一种复杂的数据结构;数组元素之间的关系既不是线性的,也不是树形的。

143、二维数组和多维数组都是线性结构。

144、邻接表只能用于有向图的存储,邻接矩阵对于有向图和无向图都适用。

145、广义表中元素的个数即为广义表的深度。

146、数组的存储结构是一组连续的内存单元。

147、稀疏矩阵压缩存储后,必会失去随机存取功能。

148、若有向图有n个顶点,则其强连通分量最多有n个。

149、设n0为哈夫曼树叶子结点的数目,则该哈夫曼树共有2n0个结点。