中级软件设计师题库_计算机软件水平考试题库

单项选择题

对于线性表，相对于顺序存储，采用链表存储的缺点是______。

A．数据元素之间的关系需要占用存储空间，导致存储密度不高
B．表中结点必须占用地址连续的存储单元，存储密度不高
C．插入新元素时需要遍历整个链表，运算的时间效率不高
D．删除元素时需要遍历整个链表，运算的时间效率不高

单项选择题

在字符串的KMP模式匹配算法中，需要先求解模式串中的next函数值，其定义如下式所示，j表示模式串中字符的序号(从1开始)。若模式串p为"abaac"，则其。next函数值为______。

A．01234
B．01122
C．01211
D．01111

单项选择题

某双端队列如下图所示，要求元素进出队列时必须在同一端口，即从A端进入的元素必须从A端出，从B端进入的元素必须从B端出，则对于4个元素的序列e1、e2、e3、e4，若要求前2个元素(e1，e2)从A端口按次序全部进入队列，后两个元素(e3，e4)从B端口按次序全部进入队列，则可能得到的出队序列是______。

A．e1、e2、e3、e4
B．e2、e3、e4、e1
C．e3、e4、e1、e2
D．e4、e3、e2、e1

单项选择题

采用顺序表和单链表存储长度为n的线性序列，根据序号查找元素，其时间复杂度分别为______。

A．O(1)、O(1)
B．O(1)、O(n)
C．O(n)、O(1)
D．O(n)、O(n)

单项选择题

输出受限的双端队列是指元素可以从队列的两端输入、但只能从队列的一端输出，如下图所示。若有e1、e2、e3、e4依次进入输出受限的双端队列，则得不到输出队列______。

A．e4、e3、e2、e1
B．e4、e2、e1、e3
C．e4、e3、e1、e2
D．e4、e2、e3、e1

单项选择题

若对线性表的最常用操作是访问任意指定序号的元素，并在表尾加入和删除元素，则适宜采用______存储。

A．顺序表
B．单链表
C．双向链表
D．哈希表

单项选择题

以下关于线性表存储结构的叙述，正确的是______。

A．线性表采用顺序存储结构时，访问表中任意一个指定序号元素的时间复杂度为常量级
B．线性表采用顺序存储结构时，在表中任意位置插入新元素的运算时间复杂度为常量级
C．线性表采用链式存储结构时，访问表中任意一个指定序号元素的时间复杂度为常量级
D．线性表采用链式存储结构时，在表中任意位置插入新元素的运算时间复杂度为常量级

单项选择题

设循环队列Q的定义中有front和size两个域变量，其中front表示队头元素的指针，size表示队列的长度，如下图所示(队列长度为3，队头元素为X、队尾元素为Z)。设队列的存储空间容量为M，则队尾元素的指针为______。

循环队列O示意图

A．(Q.front+Q.size-1)
B．(Q.front+Q.size-1+M)%M
C．(Q.front-Q.size)
D．(Q.front-Q.size+M)%M

单项选择题

在字符串的模式匹配过程中，如果模式串的每个字符依次和主串中的一个连续的字符序列相等，则成为匹配成功。如果不能在主串中找到与模式串相同的子串，则称为匹配失败。在布鲁特·福斯模式匹配算法(朴素的或基本的模式匹配)中，若主串和模式串的长度分别为n和m(且n远大于m)，且恰好在主串末尾的n个字符处匹配成功，则在上述的模式匹配过程中，字符的比较次数最多为______。

A.n^*m
B.(n-m+1)^*m
C.(n-m-1)^*m
D.(n-m)^*n

单项选择题

对于一个长度大于1且不存在重复元素的序列，令其所有元素依次通过一个初始为空的队列后，再通过一个初始为空的栈。设队列和栈的容量都足够大，一个序列通过队列(栈)的含义是序列的每个元素都入队列(栈)且出队列(栈)一次且仅一次。对于该序列在上述队列和栈上的操作，正确的是______。

A．出队序列和出栈序列一定相同
B．出队序列和出栈序列一定互为逆序
C．入队序列和出队序列一定相同，入栈序列和出栈序列不一定相同
D．入栈序列和出栈序列一定互为逆序，入队序列和出队序列不一定互为逆序

单项选择题

某二叉树如图1所示，若进行顺序存储(即用一维数组元素存储该二叉树中的结点且通过下标反映结点间的关系，例如，对于下标为i的结点，其左孩子的下标为2i、右孩子的下标为2i+1)，则该数组的大小至少为；若采用三叉链表存储该二叉树(各个结点包括结点的数据、父结点指针、左孩子指针、右孩子指针)，则该链表的所有结点中空指针的数目为。

图1

A．6
B．10
C．12
D．15

单项选择题

一个高度为h的满二叉树的节点总数为2 ^h -1，从根结点开始，自上而下、同层次结点从左至右，对结点按照顺序依次编号，即根节点编号为1，其左、右孩子节点编号分为2和3，再下一层从左到右的编号为4、5、6、7，依次类推。那么，在一颗满二叉树中，对于编号为m和n的两个节点，若n=2m+1，则______结点。

A．m是n的左孩子
B．m是n的右孩子
C．n是m的左孩子
D．n是m的右孩子

单项选择题

某二叉树如图1所示，若进行顺序存储(即用一维数组元素存储该二叉树中的结点且通过下标反映结点间的关系，例如，对于下标为i的结点，其左孩子的下标为2i、右孩子的下标为2i+1)，则该数组的大小至少为；若采用三叉链表存储该二叉树(各个结点包括结点的数据、父结点指针、左孩子指针、右孩子指针)，则该链表的所有结点中空指针的数目为。

图1

A．6
B．8
C．12
D．14

单项选择题

以下关于哈夫曼树的叙述，正确的是______。

A．哈夫曼树一定是满二叉树，其每层结点数都达到最大值
B．哈夫曼树一定是平衡二叉树，其每个结点左右子树的高度差为-1、0或1
C．哈夫曼树中左孩子结点的权值小于父结点、右孩子结点的权值大于父结点
D．哈夫曼树中叶子结点的权值越小则距离树根越远、叶子结点的权值越大则距离树根越近

单项选择题

若某二叉树的后序遍历序列为KBFDCAE，中序遍历序列为BKFEACD，则该二叉树为______。

若n ₂ 、n ₁ 、n ₀ 分别表示一个二叉树中度为2、度为1和叶子节点的数目(节点的度定义为节点的子树数目)，则对于任何一个非空的二叉树，______。

A．n2一定大于n1
B．n1一定大于n0
C．n2一定大于n0
D．n0一定大于n2

单项选择题

一棵满二叉树，其每一层节点个数都达到最大值，对其中的节点从1开始顺序编号，即根节点编号为1，其左、右孩子节点编号分别为2和3，再下一层从左到右的编号为4、5、6、7，依此类推，每一层都从左到右依次编号，直到最后的叶子节点层为止，则用______可判定编号为m和n的两个节点是否在同一层。

______是由权值集合{8,5,6,2}构造的哈夫曼树(最优二叉树)。

以下编码方法中，______属于熵编码。

A．哈夫曼编码
B．小波变换编码
C．线性预测编码
D．行程编码

单项选择题

算术表达式采用逆波兰式表示时不用括号，可以利用进行求值。与逆波兰式ab-cd+ ^* 对应的表达式是。

A．数组
B．.栈
C．队列
D．散列表

单项选择题

在______中，任意一个节点的左、右子树的高度之差的绝对值不超过1。

A．完全二叉树
B．二叉排序树
C．线索二叉树
D．最优二叉树

单项选择题

算术表达式采用逆波兰式表示时不用括号，可以利用进行求值。与逆波兰式ab-cd+ ^* 对应的表达式是。

A.a-b+c^*d
B.(a-b)^*c+d
C.(a-b)^*(c+d)
D.a-b^*c+d

单项选择题

在一个有向图G的拓扑序列中，顶点
排列在
之前，说明图G中______。

拓扑排序是将有向图中所有顶点排成一个线性序列的过程，并且该序列满足：若在AOV网中从顶点Vi到Vj有一条路径，则顶点Vi必然在顶点Vj之前。对于如下图所示的有向图，______是其拓扑序列。

A．1234576
B．1235467
C．2135476
D．2134567

单项选择题

从存储空间的利用率角度来看，以下关于数据结构中图的存储的叙述，正确的是______。

A．有向图适合采用邻接矩阵存储，无向图适合采用邻接表存储
B．无向图适合采用邻接矩阵存储，有向图适合采用邻接表存储
C．完全图适合采用邻接矩阵存储
D．完全图适合采用邻接表存储

单项选择题

无向图中一个顶点的度是指图中与该顶点相邻接的顶点数。若无向图G中的顶点数为n，边数为e，则所有顶点的度数之和为______。

A．n×e
B．n+e
C．2n
D．2e

单项选择题

设一个包含N个顶点、E条边的简单无向图采用邻接矩阵存储结构(矩阵元素A[i][j]等于1/0分别表示顶点i与顶点j之间有/无边)，则该矩阵中的非零元素数据为______。

A．.N
B．.E
C．2E
D．N+E

单项选择题

实现二分查找(折半查找)时，要求查找表______。

A．顺序存储，关键码无序排列
B．顺序存储，关键码有序排列
C．双向链表存储，关键码无序排列
D．双向链表存储，关键码有序排列

单项选择题

某哈希表(散列表)的长度为n，设散列函数为H(Key)=Key mod p，采用线性探测法解决冲突。以下关于p值的叙述中，正确的是______。

A．p的值一般为不大于n且最接近n的质数
B．p的值一般为大于n的任意整数
C．p的值必须为小于n的合数
D．p的值必须等于n

单项选择题

在13个元素构成的有序表M[1..13]中进行折半查找(向下取整)，若找到的元素为M[4]，则被比较的元素依次为______。

A．M[7]、M[3]、M[5]、M[4]
B．M[7]、M[5]、M[4]
C．M[7]、M[6]、M[4]
D．M[7]、M[4]

单项选择题

下图所示为一棵N阶B-树，N最有可能的值为______。

A．1
B．2
C．3
D．4

单项选择题

对n个元素的有序表A[1..n]进行顺序查找，其成功查找的平均查找长度(即在查找表中找到指定关键码的元素时，所进行比较的表中元素个数的期望值)为______。

A.n
B.(n+1)/2
C.log₂n
D.n²

单项选择题

对于关键字序列(26，25，72，38，8，18，59)，采用散列函数H(Key)=Key mod 13构造散列表(哈希表)。若采用线性探测的开放定址法解决冲突(顺序地探查可用存储单元)，则关键字59所在散列表中的地址为______。

A．6
B．7
C．8
D．9

单项选择题

快速排序算法在排序过程中，在待排序数组中确定一个元素为基准元素，根据基准元素把待排序数组划分成两个部分，前面一部分元素值小于基准元素，而后面一部分元素值大于基准元素，然后再分别对前后两个部分进一步进行划分。根据上述描述，快速排序算法采用了算法设计策略。已知基准元素操作的时间复杂度为O(n)，则快速排序算法的最好和最坏情况下的时间复杂度为。

A．分治
B．动态规划
C．贪心
D．回溯

单项选择题

快速排序算法在排序过程中，在待排序数组中确定一个元素为基准元素，根据基准元素把待排序数组划分成两个部分，前面一部分元素值小于基准元素，而后面一部分元素值大于基准元素，然后再分别对前后两个部分进一步进行划分。根据上述描述，快速排序算法采用了算法设计策略。已知基准元素操作的时间复杂度为O(n)，则快速排序算法的最好和最坏情况下的时间复杂度为。

A.O(n)和O(nlgn)
B.O(n)和O(n²)
C.O(nlgn)和O(nlgn)
D.O(nlgn)和O(n²)

单项选择题

对一待排序序列分别进行直接插入排序和简单选择排序，若待排序序列中有两个元素的值相同，则______保证这两个元素在排序前后的相对位置不变。

A．直接插入排序和简单选择排序都可以
B．直接插入排序和简单选择排序都不能
C．只有直接插入排序可以
D．只有简单选择排序可以

单项选择题

对n个基本有序的整数进行排序，若采用插入排序算法，则时间和空间复杂度分别为；若采用快速排序算法，则时间和空间复杂度分别为。

A.O(n²)和O(n)
B.O(n)和O(n)
C.O(n²)和O(1)
D.O(n)和O(1)

单项选择题

对n个基本有序的整数进行排序，若采用插入排序算法，则时间和空间复杂度分别为；若采用快速排序算法，则时间和空间复杂度分别为。

A.O(n²)和O(n)
B.O(nlgn)和O(n)
C.O(n²)和O(1)
D.O(nlgn)和O(1)

单项选择题

将数组{1,1,2,4,7,5}从小到大排序，若采用排序算法，则元素之间需要进行的比较次数最少，共需要进行次元素之间的比较。

A．直接插入
B．归并
C．.堆
D．快速

单项选择题

将数组{1,1,2,4,7,5}从小到大排序，若采用排序算法，则元素之间需要进行的比较次数最少，共需要进行次元素之间的比较。

A．5
B．6
C．7
D．8

单项选择题

递增序列A(a ₁ ,a ₂ ,…,a _n )和B(b ₁ ，b ₂ ，…，b _n )的元素互不相同，若需将它们合并为一个长度为2n的递增序列，则当最终的排列结果为______时，归并过程中元素的比较次数最多。

A．a1,a2,…,an,b1,b2,…,bn
B．b1,b2,…,bn,a1,a2,…,an
C．a1,b1,b2,b2,…,ai,bi,…,an,bn
D．a1,a2,…,ai/2,b1,b2,…,bi/2,ai/2+1,ai/2+2,…an,bi/2+1,bi/2+2,…,bn

单项选择题

用插入排序和归并排序算法对数组＜3,1,4,1,5,9,6,5＞进行从大到小排序，则分别需要进行______次数组元素之间的比较。

A．12,14
B．10,14
C．12,16
D．10,16

单项选择题

已知一个文件中出现的各个字符及其对应的频率如下表所示。若采用定长编码，则该文件中字符的码长应为上。若采用Huffman编码，则字符序列“face”的编码应为。

字符 a b c d e f

频率(%) 45 13 12 16 9 5

A．2
B．3
C．4
D．5

单项选择题

已知一个文件中出现的各个字符及其对应的频率如下表所示。若采用定长编码，则该文件中字符的码长应为上。若采用Huffman编码，则字符序列“face”的编码应为。

字符 a b c d e f

频率(%) 45 13 12 16 9 5

A．110001001101
B．001110110011
C．101000010100
D．010111101011

对n个基本有序的整数进行排序，若采用插入排序算法，则时间和空间复杂度分别为______；若采用快速排序算法，则时间和空间复杂度分别为______。

你可能感兴趣的试题

对于线性表，相对于顺序存储，采用链表存储的缺点是______。

在字符串的KMP模式匹配算法中，需要先求解模式串中的next函数值，其定义如下式所示，j表示模式串中字符的序号(从1开始)。若模式串p为"abaac"，则其。next函数值为______。

采用顺序表和单链表存储长度为n的线性序列，根据序号查找元素，其时间复杂度分别为______。

输出受限的双端队列是指元素可以从队列的两端输入、但只能从队列的一端输出，如下图所示。若有e1、e2、e3、e4依次进入输出受限的双端队列，则得不到输出队列______。

若对线性表的最常用操作是访问任意指定序号的元素，并在表尾加入和删除元素，则适宜采用______存储。

以下关于线性表存储结构的叙述，正确的是______。

在字符串的KMP模式匹配算法中，需要求解模式串p的next函数值，其定义如下所示。若模式串p为“aaabaaa”，则其next函数值为______。

对于线性表(由n个同类元素构成的线性序列)，采用单向循环链表存储的特定之一是______。

对二维数组a[1..N,1..N]中的一个元素a[i,j](1≤i，j≤N)，存储在a[i,j]之前的元素个数______。

若二维数组arr[1..M,1..N]的首地址为base，数组元素按列存储且每个元素占用K个存储单元，则元素arr[i,j]在该数组空间的地址为______。

在某棵二叉查找树(即二叉排序树)中进行查找时，效率最差的情形是该二叉查找树是______。

以下关于哈夫曼树的叙述，正确的是______。

若某二叉树的后序遍历序列为KBFDCAE，中序遍历序列为BKFEACD，则该二叉树为______。

若n 2 、n 1 、n 0 分别表示一个二叉树中度为2、度为1和叶子节点的数目(节点的度定义为节点的子树数目)，则对于任何一个非空的二叉树，______。

______是由权值集合{8,5,6,2}构造的哈夫曼树(最优二叉树)。

以下编码方法中，______属于熵编码。

算术表达式采用逆波兰式表示时不用括号，可以利用______进行求值。与逆波兰式ab-cd+ * 对应的表达式是______。

在______中，任意一个节点的左、右子树的高度之差的绝对值不超过1。

算术表达式采用逆波兰式表示时不用括号，可以利用______进行求值。与逆波兰式ab-cd+ * 对应的表达式是______。

在一个有向图G的拓扑序列中，顶点 排列在 之前，说明图G中______。

拓扑排序是将有向图中所有顶点排成一个线性序列的过程，并且该序列满足：若在AOV网中从顶点Vi到Vj有一条路径，则顶点Vi必然在顶点Vj之前。对于如下图所示的有向图，______是其拓扑序列。

从存储空间的利用率角度来看，以下关于数据结构中图的存储的叙述，正确的是______。

无向图中一个顶点的度是指图中与该顶点相邻接的顶点数。若无向图G中的顶点数为n，边数为e，则所有顶点的度数之和为______。

设一个包含N个顶点、E条边的简单无向图采用邻接矩阵存储结构(矩阵元素A[i][j]等于1/0分别表示顶点i与顶点j之间有/无边)，则该矩阵中的非零元素数据为______。

实现二分查找(折半查找)时，要求查找表______。

某哈希表(散列表)的长度为n，设散列函数为H(Key)=Key mod p，采用线性探测法解决冲突。以下关于p值的叙述中，正确的是______。

在13个元素构成的有序表M[1..13]中进行折半查找(向下取整)，若找到的元素为M[4]，则被比较的元素依次为______。

下图所示为一棵N阶B-树，N最有可能的值为______。

对n个元素的有序表A[1..n]进行顺序查找，其成功查找的平均查找长度(即在查找表中找到指定关键码的元素时，所进行比较的表中元素个数的期望值)为______。

对于关键字序列(26，25，72，38，8，18，59)，采用散列函数H(Key)=Key mod 13构造散列表(哈希表)。若采用线性探测的开放定址法解决冲突(顺序地探查可用存储单元)，则关键字59所在散列表中的地址为______。

对一待排序序列分别进行直接插入排序和简单选择排序，若待排序序列中有两个元素的值相同，则______保证这两个元素在排序前后的相对位置不变。

对n个基本有序的整数进行排序，若采用插入排序算法，则时间和空间复杂度分别为______；若采用快速排序算法，则时间和空间复杂度分别为______。

对n个基本有序的整数进行排序，若采用插入排序算法，则时间和空间复杂度分别为______；若采用快速排序算法，则时间和空间复杂度分别为______。

将数组{1,1,2,4,7,5}从小到大排序，若采用______排序算法，则元素之间需要进行的比较次数最少，共需要进行______次元素之间的比较。

将数组{1,1,2,4,7,5}从小到大排序，若采用______排序算法，则元素之间需要进行的比较次数最少，共需要进行______次元素之间的比较。

递增序列A(a 1 ,a 2 ,…,a n )和B(b 1 ，b 2 ，…，b n )的元素互不相同，若需将它们合并为一个长度为2n的递增序列，则当最终的排列结果为______时，归并过程中元素的比较次数最多。

用插入排序和归并排序算法对数组＜3,1,4,1,5,9,6,5＞进行从大到小排序，则分别需要进行______次数组元素之间的比较。

已知一个文件中出现的各个字符及其对应的频率如下表所示。若采用定长编码，则该文件中字符的码长应为______上。若采用Huffman编码，则字符序列“face”的编码应为______。 字符 a b c d e f 频率(%) 45 13 12 16 9 5

已知一个文件中出现的各个字符及其对应的频率如下表所示。若采用定长编码，则该文件中字符的码长应为______上。若采用Huffman编码，则字符序列“face”的编码应为______。 字符 a b c d e f 频率(%) 45 13 12 16 9 5

对n个基本有序的整数进行排序，若采用插入排序算法，则时间和空间复杂度分别为；若采用快速排序算法，则时间和空间复杂度分别为。

若n ₂ 、n ₁ 、n ₀ 分别表示一个二叉树中度为2、度为1和叶子节点的数目(节点的度定义为节点的子树数目)，则对于任何一个非空的二叉树，______。

算术表达式采用逆波兰式表示时不用括号，可以利用进行求值。与逆波兰式ab-cd+ ^* 对应的表达式是。

算术表达式采用逆波兰式表示时不用括号，可以利用进行求值。与逆波兰式ab-cd+ ^* 对应的表达式是。

在一个有向图G的拓扑序列中，顶点
排列在
之前，说明图G中______。

对n个基本有序的整数进行排序，若采用插入排序算法，则时间和空间复杂度分别为；若采用快速排序算法，则时间和空间复杂度分别为。

对n个基本有序的整数进行排序，若采用插入排序算法，则时间和空间复杂度分别为；若采用快速排序算法，则时间和空间复杂度分别为。

将数组{1,1,2,4,7,5}从小到大排序，若采用排序算法，则元素之间需要进行的比较次数最少，共需要进行次元素之间的比较。

将数组{1,1,2,4,7,5}从小到大排序，若采用排序算法，则元素之间需要进行的比较次数最少，共需要进行次元素之间的比较。

递增序列A(a ₁ ,a ₂ ,…,a _n )和B(b ₁ ，b ₂ ，…，b _n )的元素互不相同，若需将它们合并为一个长度为2n的递增序列，则当最终的排列结果为______时，归并过程中元素的比较次数最多。

已知一个文件中出现的各个字符及其对应的频率如下表所示。若采用定长编码，则该文件中字符的码长应为上。若采用Huffman编码，则字符序列“face”的编码应为。

字符 a b c d e f

频率(%) 45 13 12 16 9 5

已知一个文件中出现的各个字符及其对应的频率如下表所示。若采用定长编码，则该文件中字符的码长应为上。若采用Huffman编码，则字符序列“face”的编码应为。

字符 a b c d e f

频率(%) 45 13 12 16 9 5