试卷详情
-
程序员-数据结构
-
[单项选择]数组A[-5..5,0..8]按列存储。若第一个元素的首地址为100,且每个元素占用4个存储单元,则元素A[2,3]的存储地址为______。
A. 244
B. 260
C. 364
D. 300
-
[单项选择]在执行递归过程时,通常使用的数据结构是______。
A. 堆栈(stac
B. 队列(queu
C. 图(grap
D. 树(tre
-
[单项选择]如果要求一个线性表既能较快地查找,又能适应动态变化的要求,则可采用______的方法。
A. 分块
B. 顺序
C. 二分法
D. 基于属性
-
[单项选择]对长度为n的线性表排序,在最坏的情况下,比较次数不是n(n-1)/2的排序方法是______。
A. 快速排序
B. 冒泡排序
C. 直接插入排序
D. 堆排序
-
[单项选择]堆栈操作中,______保持不变。
A. 堆栈的顶
B. 堆栈中的数据
C. 堆栈指针
D. 堆栈的底
-
[单项选择]采用邻接表表示一有向图,若图中某顶点的入度和出度分别为d1和d2,则该顶点对应的单链表的结点数为______。
A. d1
B. d2
C. d1-d2
D. d1+d2
-
[单项选择]______是线性结构的数据结构。
A. 列表
B. 高维数组
C. 双端队列
D. 二叉树
-
[单项选择]在一棵非空二叉树中,叶子节点的总数比度为2的节点总数多 (43) 个。
A. -1
B. 0
C. 1
D. 2
-
[单项选择]对长度为n的线性表进行顺序查找,在最坏情况下,所需要的比较次数为()
A. 1og2n
B. n/2
C. n
D. n+1
-
[单项选择]下列数据结构中,能用二分法进行查找的是______
A. 顺序存储的有序线性表
B. 线性链表
C. 二叉链表
D. 有序线性链表
-
[单项选择]在程序的执行过程中,用______结构可以实现嵌套调用函数的正确返回。
A. 队列
B. 栈
C. 树
D. 图
-
[单项选择]对具有n个元素的有序序列进行二分查找时,()
A. 查找元素所需的比较次数与元素的位置无关
B. 查找序列中任何一个元素所需要的比较次数不超过log2(n+1)
C. 元素位置越靠近序列后端,查找该元素所需的比较次数越少
D. 元素位置越靠近序列前端,查找该元素所需的比较次数越少
-
[单项选择]设栈S和队列Q的初始状态为空,元素e1、e2、e3、e4、e5和e6依次通过栈S,一个元素出栈后即进入队列Q,若6个元素出队的序列是e2、e4、e3、e6、e5、e1,则栈S的容量至少应该是()
A. 6
B. 4
C. 3
D. 2
-
[单项选择]用二分法来检索数据,最确切的说法是______。
A. 仅当数据随机排列时,才能正确地检索数据
B. 仅当数据有序排列时,才能正确地检索数据
C. 仅当数据量较大时,才能有效地检索数据
D. 仅当数据量较小时,才能有效地检索数据
-
[单项选择]为了描述n个人之间的同学关系,可用______结构表示。
A. 线性表
B. 树
C. 图
D. 队列
-
[单项选择]二叉排序树或者是一棵空树,或者是具有如下性质的二叉树:若其左子树非空,则左子树上所有结点的值均小于根结点的值;若其右子树非空,则右子树上所有结点的值均大于根结点的值;其左、右子树本身就是两棵二叉排序树。根据该定义,对一棵非空的二叉排序树进行______遍历,可得到一个结点元素的递增序列。
A. 先序(根、左、右)
B. 中序(左、根、右)
C. 后序(左、右、根)
D. 层序(从树根开始,按层次)
-
[单项选择]已知N个数已存入数组A[1..M]的前N个元素中(N<M),为在A[i](1≤i≤N)之前插入一个新数,应先(),以挪出一个空闲位置插入该数。
A. 从A开始直到A[1],每个数向后移动一个位置
B. 从A[1]开始直到A,每个数向后移动一个位置
C. 从A开始直到A,每个数向前移动一个位置
D. 从A开始直到A,每个数向后移动一个位置
-
[单项选择]为了用一个数代表一批数,人们常用这批数据的算术平均值(简称平均值)或中位数来代表。中位数就是位于这批数中间的数(大于它的数与小于它的数一样多)。对于奇数个数而言,排序后很容易确定中间那个数;对于偶数个数而言,排序后中间会有两个数,再取这两个数的算术平均,就是中位数。以下关于平均值与中位数的叙述中,______是不正确的。
A. 中位数比平均值稳健,不易受极端值影响
B. 每个数据加倍后,平均值也加倍;每个数据增加1后,平均值也增加1
C. 三组各有n个数据有三个中位数,它们的中位数就是这三组数据全体的中位数
D. 三组各有n个数据有三个平均值,它们的平均值就是这三组数据全体的平均值
-
[单项选择]下面的排序方法中,关键字比较次数与记录的初始排列无关的是______。
A. 希尔排序
B. 冒泡排序
C. 直接插入排序
D. 直接选择排序
-
[单项选择]判断“链式队列为空”的条件是______(front为头指针,rear为尾指针)。
A. front==NULL
B. rear==NULL
C. front==rear
D. front!=rear
-
[单项选择]在链表结构中,采用()可以用最少的空间代价和最高的时间效率实现队列结构。
A. 仅设置尾指针的单向循环链表
B. 仅设置头指针的单向循环链表
C. 仅设置尾指针的双向链表
D. 仅设置头指针的双向链表
-
[单项选择]冒泡排序在最坏情况下的比较次数是()
A. n(n+1)/2
B. nlog2n
C. n(n-1)/2
D. n/2
-
[单项选择]以下数据结构中属于线性数据结构的是______。
A. 集合
B. 线性表
C. 二叉树
D. 图
-
[单项选择]设初始栈为空,s表示入栈操作,x表示出栈操作,则______是合法的操作序列。
A. sxxsssxxx
B. xxssxxss
C. sxsxssxx
D. xssssxxx
-
[单项选择]在文件“局部有序”或文件长度较小的情况下,最佳内部排序方法是______。
A. 直接插入排序
B. 冒泡排序
C. 简单选择排序
D. 归并排序
-
[单项选择]若一个栈以向量V[1..n)存储,且空栈的栈顶指针top为n+1,则将元素x入栈的正确操作是______。
A. top=top+1;V[top]=x;
B. V[top]=x;top=top+1;
C. top=top-1;V[top]=x;
D. V[top]=x;top=top-1;
-
[单项选择]若需将一个栈S中的元素逆置,则以下处理方式中正确的是______。
A. 将栈S中元素依次出栈并入栈T,然后栈T中元素依次出栈并进入栈S
B. 将栈S中元素依次出栈并入队,然后使该队列元素依次出队并进入栈S
C. 直接交换栈顶元素和栈底元素
D. 直接交换栈顶指针和栈底指针
-
[单项选择]设栈S初始状态为空。元素a、b、c、d、e、f依次通过栈S,若出栈的顺序为c、f、 e、 d、b、a,则栈S的容量至少应该为______。
A. 6
B. 5
C. 4
D. 3
-
[单项选择]判断一个表达式中左右括号是否匹配,采用______实现较为方便。
A. 线性表的顺序存储
B. 队列
C. 线性表的链式存储
D. 栈
-
[单项选择]一个栈的输入序列为123…n,若输出序列的第一个元素是n,输出第i(1≤i≤n)个元素是______。
A. 不确定
B. n-i+l
C. i
D. n-i
-
[单项选择]在长度为64的有序线性表中进行顺序查找,最坏情况下需要比较的次数为______。
A. 63
B. 64
C. 6
D. 7
-
[单项选择]数据结构中的树最适合用来表示______的情况。
A. 数据元素有序
B. 数据元素之间具有多对多关系
C. 数据元素无序
D. 数据元素之间具有一对多关系
-
[单项选择]无向图的邻接矩阵一定是()
A. 对角矩阵
B. 稀疏矩阵
C. 三角矩阵
D. 对称矩阵
-
[单项选择]从未排序的序列中依次取出一个元素与已排序序列中的元素进行比较,然后将其放在已排序序列的合适位置上,该排序方法称为______。
A. 插入排序
B. 选择排序
C. 希尔排序
D. 归并排序
-
[单项选择]在深度为7的满二叉树中,叶子结点的个数为()
A. 32
B. 31
C. 64
D. 63
-
[单项选择]字符串是一种线性表,其特殊性表现在______。
A. 它的数据元素是一个字符
B. 它可以链式存储
C. 它可以顺序存储
D. 它的数据元素可以是多个字符
-
[单项选择]一棵二叉树中共有70个叶子结点与80个度为1的结点,则该二叉树中的总结点数为 ______。
A. 219
B. 221
C. 229
D. 231
-
[单项选择]对矩阵压缩存储的主要目的是______。
A. 方便运算
B. 节省存储空间
C. 降低计算复杂度
D. 提高运算效率
-
[单项选择]下列叙述中正确的是()
A. 数据的逻辑结构与存储结构必定是一一对应的
B. 由于计算机存储空间是向量式的存储结构,因此,数据的存储结构一定是线性结构
C. 程序设计语言中的数组一般是顺序存储结构,因此,利用数组只能处理线性结构
D. 以上三种说法都不对
-
[单项选择]链表不具备的特点是______。
A. 可随机访问任何一个元素
B. 插入、删除操作不需要移动元素
C. 无需事先估计存储空间大小
D. 所需存储空间与线性表长度成正比
-
[单项选择]在深度为5的满二叉树中,结点的个数为______。
A. 32
B. 31
C. 16
D. 15
-
[单项选择]字符串computer中长度为3的子串有______个。
A. 4
B. 5
C. 6
D. 7
-
[单项选择]若push、pop分别表示入栈、出栈操作,初始栈为空且元素1、2、3依次进栈,则经过操作序列push、push、pop、pop、push、pop之后,得到的出栈序列为______。
A. 321
B. 213
C. 231
D. 123
-
[单项选择]已知递归函数f(n)的功能是计算1+2+…+n,且n≥1,应采用的代码段是______。
A. if n>1 then return 1 else return n+f(n-1)
B. if n>1 then return 1 else return n+f(n+1)
C. if n<1 then return 0 else return n+f(n-1)
D. if n<1 then return 0 else return n+f(n+1)
-
[单项选择]对于长度为n的线性表,在最坏情况下,下列各排序法所对应的比较次数中正确的是 ______。
A. 冒泡排序为n/2
B. 冒泡排序为n
C. 快速排序为n
D. 快速排序为n(n-1)/2
-
[单项选择]假设一棵二叉树的后序遍历序列为DGJHEBIFCA,中序遍历序列为DBGEHJACIF,则其前序遍历序列为()
A. ABCDEFGHIJ
B. ABDEGHJCFI
C. ABDEGHJFIC
D. ABDEGJHCFI
-
[单项选择]采用哈希(或散列)技术构造查找表时,需要考虑冲突(碰撞)的处理,冲突是指______。
A. 关键字相同的记录被映射到不同的哈希地址
B. 关键字依次被映射到编号连续的哈希地址
C. 关键字不同的记录被映射到同一个哈希地址
D. 关键字的数目超过哈希地址的数目
-
[单项选择]二叉树的查找有深度优先和广度优先二类,深度优先包括______。
A. 前序遍历、后序遍历、中序遍历
B. 前序遍历、后序遍历、层次遍历
C. 前序遍历、中序遍历、层次遍历
D. 中序遍历、后序遍历、层次遍历
-
[单项选择]下列对于线性链表的描述中正确的是______。
A. 存储空间不一定连续,且各元素的存储顺序是任意的
B. 存储空间不一定连续,且前件元素一定存储在后件元素的前面
C. 存储空间必须连续,且前件元素一定存储在后件元素的前面
D. 存储空间必须连续,且各元素的存储顺序是任意的
-
[单项选择]若二维数组P[1..5,0..8]的首地址为base,数组元素按行存储,且每个元素占用1个存储单元,则元素P[3,3]在该数组空间的地址为______。
A. base+13
B. base+16
C. base+18
D. base+21
-
[单项选择]若in、out分别表示入、出队操作,初始队列为空且元素a、b、c依次入队,则经过操作序列in、in、out、out、in、out之后,得到的出队序列为()
A. cba
B. bac
C. bca
D. abe
-
[单项选择]栈和队列的共同点是______。
A. 都是先进先出
B. 都是先进后出
C. 只允许在端点处插入和删除元素
D. 没有共同点
-
[单项选择]设数组a[1..3,1..4]中的元素以列为主序存放,每个元素占用1个存储单元,则数组元素a[2,3]相对于数组空间首地址的偏移量为()
A. 6
B. 7
C. 8
D. 9
-
[单项选择]设最优的分配方案为完成这三项工作所需的总天数最少,则在最优分配方案中,()
A. 甲执行P
B. 甲执行Q
C. 乙执行P
D. 乙执行R
-
[单项选择]如果待排序序列中两个元素具有相同的值,在排序前后它们的相互位置发生颠倒,则称该排序算法是不稳定的。______是稳定的排序方法,因为这种方法在比较相邻元素时,值相同的元素并不进行交换。
A. 冒泡排序
B. 希尔排序
C. 快速排序
D. 简单选择排序
-
[单项选择]对于长度为11的顺序存储的有序表,若采用折半查找(向下取整),则找到第5个元素需要与表中的______个元素进行比较操作(包括与第5个元素的比较)。
A. 5
B. 4
C. 3
D. 2
-
[单项选择]PUSH和POP命令常用于______操作。
A. 队列
B. 数组
C. 栈
D. 记录
-
[单项选择]n个元素进行冒泡排序的过程中,最好情况下的时间复杂度为()
A. O(1)
B. O(1og2
C. O(n2)
D. O(
-
[单项选择]在具有100个结点的树中,其边的数目为______。
A. 101
B. 100
C. 99
D. 98
-
[单项选择]在排序算法中每一项都与其他诸项进行比较,计算出小于该项的项的个数,以确定该项的位置叫______。
A. 插入排序
B. 交换排序
C. 选择排序
D. 枚举排序
-
[单项选择]设某种二叉树有如下特点:结点的子树数目不是2个,则是0个。这样的一棵二叉树中有m(m>0)个子树为0的结点时,该二叉树上的结点总数为______。
A. 2m+1
B. 2m-1
C. 2(m-1)
D. 2(m+1)
-
[单项选择]下面叙述不正确的是______。
A. 算法的执行效率与数据的存储结构有关
B. 算法的空间复杂度是指执行这个算法所需要的内存空间
C. 算法的有穷性是指算法必须能在执行有限个步骤之后终止
D. 算法的时间复杂度是指执行这个算法所需要的时间
-
[单项选择]设有100个结点,用二分法查找时,最大比较次数是______。
A. 25
B. 50
C. 10
D. 7
-
[单项选择]n个元素依次全部进入栈后,再陆续出栈并经过一个队列输出。那么,______。
A. 元素的出队次序与进栈次序相同
B. 元素的出队次序与进栈次序相反
C. 元素的进栈次序与进队次序相同
D. 元素的出栈次序与出队次序相反
-
[单项选择]与单向链表相比,双向链表______。
A. 需要较少的存储空间
B. 遍历元素需要的时间较长
C. 较易于访问相邻结点
D. 较易于插入和删除元素
-
[单项选择]若线性表采用链式存储结构,则适用的查找方法为______。
A. 随机查找
B. 散列查找
C. 二分查找
D. 顺序查找
-
[单项选择]数据结构主要研究数据的______。
A. 逻辑结构
B. 存储结构
C. 逻辑结构和存储结构
D. 逻辑结构和存储结构及其运算的实现
-
[单项选择]在数据结构中,结点(数据元素)及结点间的相互关系组成数据的逻辑结构。按逻辑结构的不同,数据结构通常可分为______两类。
A. 线性结构和非线性结构
B. 紧凑结构和稀疏结构
C. 动态结构和静态结构
D. 内部结构和外部结构
-
[单项选择]以下关于字符串的判定语句中正确的是______。
A. 字符串是一种特殊的线性表
B. 串的长度必须大于零
C. 字符串不属于线性表的一种
D. 空格字符组成的串就是空串
-
[单项选择]数据的存储结构是指______。
A. 数据所占的存储空间量
B. 数据的逻辑结构在计算机中的表示
C. 数据在计算机中的顺序存储方式
D. 存储在外存中的数据
-
[单项选择]已知有一维数组T[0..m*n-1],其中m>n。从数组T的第一个元素(T[0])开始,每隔n个元素取出一个元素依次存入数组B[1..m]中,即B[1]=T[0],D[2]=T[n],依此类推,那么放入B[k](1≤k≤n)的元素是______。
A. T[(k-1)*n]
B. T(k*
C. T[(k-1)*m]
D. T[k*m]
-
[单项选择]若原始数据序列(23,4,45,67,12,8,19,7)采用直接插入排序法(顺序地将每个元素插入到它之前的适当位置)排序,则进行完第4趟后的排序结果是______。
A. 4,8,45,23,67,12,19,7
B. 4,7,8,12,23,45,67,19
C. 4,12,8,19,7,23,45,67
D. 4,12,23,45,67,8,19,7
-
[填空题]设一棵二叉树的中序遍历结果为DBEAFC,前序遍历结果为ABDECF,则后序遍历结果为()
-
[单项选择]在下列算法中,______算法可能出现下列情况:在最后一趟开始之前,所有的元素都不在其最终的位置上。
A. 堆排序
B. 冒泡排序
C. 插入排序
D. 快速排序
-
[单项选择]在最坏情况下,下列排序方法中时间复杂度最小的是______。
A. 冒泡排序
B. 快速排序
C. 插入排序
D. 堆排序
-
[单项选择]某二叉树中度为2的结点有18个,则该二叉树中有______个叶子结点。
A. 18
B. 19
C. 8
D. 20
-
[单项选择]若线性表(23,14,45,12,8,19,7)采用散列法进行存储和查找。设散列函数为 H(Key)=Key mod 7并采用线性探查法(顺序地探查可用存储单元)解决冲突,则构造的散列表为______,其中,mod表示整除取余运算。
A. 哈希地址 0 1 2 3 4 5 6 关键字 14 8 23 45 7 12 19
B. 哈希地址 0 1 2 3 4 5 6 关键字 7 8 12 14 19 23 45
C. 哈希地址 0 1 2 3 4 5 6 关键字 7 8 23 45 12 19 14
D. 哈希地址 0 1 2 3 4 5 6 关键字 14 7 12 8 45 23 19