以下关于单链表的叙述中错误的是（）。字符串可定义为n(n≥0)个字符的有限（         ），其中，n是字符串的长度，表明字符串中字符的个数。A:结点的数据域用于存储线性表的一个数据元素 B:所有数据通过指针的链接而组织成单链表 C:结

对一个初始为空的栈s执行操作Push(s,5),Push(s,2),Push(s,4),Pop(s,x),getTop(s,x)后，x的值应是（  ）。

A:5
B:0
C:4
D:2
答案: 2

用S表示进栈操作，用X表示出栈操作，若元素的进栈顺序是1234，为了得到1342出栈顺序，相应的S和X的操作序列为（  ）。

A:SXSXSSXX
B:SXSSXXSX
C:SSSXXSXX
D:SXSSXSXX
答案: SXSSXSXX

假设一个栈的输入序列是1,2,3,4，则不可能得到的输出序列是（  ）。

A:4,3,2,1
B:1,2,3,4
C:1,3,4,2
D:4,1,2,3
答案: 4,1,2,3

已知一个栈的进栈序列为1,2,3,…,n，其输出序列的第一个元素是i，则第j个出栈元素是（  ）。

A:不确定
B:j-i
C:n-i
D:j-i+1
答案: 不确定

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

A:不确定
B:n-i
C:i
D:n-i+1
答案: n-i+1

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

A:一定是1
B:一定是2
C:可能是1
D:可能是2
答案: 可能是2

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

A:一定是3
B:可能是2
C:不可能是2
D:一定是2
答案: 不可能是2

设一个循环队列Q[maxSize]的队头指针为front，队尾指针为rear，队列最大容量为maxSize，除此之外该队列再没有其他数据成员，则该队列的队满条件是（  ）。

A:Q.front==(Q.rear+1)%maxSize
B:Q.front==Q.rear
C:Q.front+Q.rear>=maxSize
D:Q.rear==(Q.front+1)%maxSize
答案: Q.front==(Q.rear+1)%maxSize

设循环队列的存储容量为maxSize，队头和队尾指针分别为front和rear。若有一个循环队列Q，可应用下列语句（  ）计算队列元素个数？

A:(Q.rear-Q.front+maxSize)%maxSize
B:(Q.rear-Q.front)%maxSize+1
C:Q.rear-Q.front+1
D:Q.rear-Q.front
答案: (Q.rear-Q.front+maxSize)%maxSize

一个队列的进队顺序是1,2,3,4，则该队列可能的输出序列是（  ）。

A:1,2,3,4
B:4,3,2,1
C:1,4,2,3
D:1,3,2,4
答案: 1,2,3,4

对于链式队列，在执行插入操作时（  ）。

A:头尾指针都要修改 
B:头尾指针可能都要修改
C:仅修改尾指针
D:仅修改头指针
答案: 头尾指针可能都要修改

最适合用作链式队列的链表是（  ）。

A:只带队头指针的循环单链表
B:带有队头指针和队尾指针的非循环单链表
C:只带队头指针的非循环单链表
D:带有队头指针和队尾指针的循环单链表
答案: 带有队头指针和队尾指针的非循环单链表

最不适合用作链式队列的链表是（  ）。

A:带有队头指针的双向非循环链表
B:带有队头指针的双向循环链表
C:只带队尾指针的循环单链表
D:只带队尾指针的双向循环链表
答案: 带有队头指针的双向非循环链表

设一个链式队列q的队头指针和队尾指针分别为front和rear，则判断队列空的条件是（  ）。

A:q.front!=NULL
B:q.rear==NULL
C:q.front==q.rear
D:q.front==NULL
答案: q.front==NULL

将递归算法转换成非递归算法时， 通常要借助的数据结构是（   ）。

A:队列
B:树
C:栈
D:线性表
答案: 栈

栈与一般线性表的区别在于（）。

A:数据元素的类型不同
B:逻辑数据不同
C:运算是否受限制
D:数据元素的个数不同
答案: 运算是否受限制

栈和队列都是顺序存取结构。

A:错
B:对
答案: 对

对循环队列初始化时 · 要求队头指针与队尾指针指向同一个位置， 不论队列存储中什么位置都可以。

A:错
B:对
答案: 对

栈 是 实 现 过 程 和 函 数 等 子 程 序 调 用 所 必 需 的 结 构。

A:对
B:错
答案: 对

字符串可定义为n(n≥0)个字符的有限（         ），其中，n是字符串的长度，表明字符串中字符的个数。

A:序列
B:集合
C:聚合
D:数列
答案: 序列

串是一种特殊的线性表，其特殊性体现在（  ）。

A:可以顺序存储
B:数据元素是一个字符
C:数据元素可以是多个字符
D:可以链接存储
答案: 数据元素是一个字符

有n个字符的字符串的非空子串个数最多有（     ）。

A:n(n+1)/2
B:n-1
C:n(n-1)/2
D:n
答案: n(n+1)/2

两个字符串相等的条件是（      ）。

A:两个串的长度相等，并且两个串包含的字符相同
B:两个串的长度相等
C:两个串包含的字符相等
D:两个串的长度相等，并且对应位置上的字符相同
答案: 两个串的长度相等，并且对应位置上的字符相同

设有两个串：T和P，求P在T中首次出现的位置的运算叫做（     ）。

A:模式匹配
B:串替换
C:求子串
D:串连接
答案: 模式匹配

在以下关于串的说法中正确的是（）。

A:用块链存储表示实现的串的结点大小为4,说明每个结点可存储4个字符
B:串长度是指串中不同字符的个数
C:子串是从串中抽取出若干字符组成的串
D:空串是由空格组成的串
答案: 用块链存储表示实现的串的结点大小为4,说明每个结点可存储4个字符

设有两个串T和P，求P在T中首次出现的位置的运算叫做（）。

A:模式匹配
B:串替换
C:串连接
D:求子串
答案: 模式匹配

设T=”aaaaaacaaaca”，P=“aaac”，使用BF算法的模式匹配过程需要执行的趟数为（）。

A:3
B:2
C:7
D:4
答案: 4

应用 KMP 算法进行模式匹配时，next 函数值序列的产生仅与模式串有关。

A:错
B:对
答案: 对

KMP 算法的特点是在模式匹配时指示目标串当前比对位置的指针不会回退。

A:错
B:对
答案: 对

对稀疏矩阵进行压缩存储的目的是（  ）。

A:便于进行矩阵运算
B:降低运算的时间复杂度
C:节省存储空间
D:便于输入和输出
答案: 节省存储空间

一个稀疏矩阵采用压缩后，和直接采用二维数组存储相比会失去（   ）特性。

A:输入输出
B:顺序存储
C:其余选项都不对
D:随机存取
答案: 随机存取

稀疏矩阵常用的压缩存储方法有（   ）。

A:二维数组          
B:三元组和散列表      
C:散列表和十字链表
D:三元组和十字链表          
答案: 三元组和十字链表          

以下关于一维数组与顺序表不同之处的说法中错误的是（）。

A:前者的元素可以不连续存放，后者的元素必须相继存放
B:前者的元素数据类型相同，后者的元素数据类型可以不相同
C:前者既可以是逻辑结构也可以是存储结构，后者是线性表的存储结构
D:前者的长度不变，后者的长度可变
答案: 前者的元素数据类型相同，后者的元素数据类型可以不相同

将一个n*n的对称矩阵A的对角线和对角线以上的部分按列优先存放于一个一维数组中，那么A有(    )个矩阵元素未被存于sa中。

A:n^2/2
B:n(n-1)/2
C:n(n+1)/2
D:n(n-1)
答案: n(n-1)/2

设一维数组 A[n]中每个元素占用 6 个存储单元，若A[5]的存储地址从 100 开始，则该数组的首地址是（ )。

A:30
B:76
C:64
D:95
答案: 64

在二维数组A[9][10]中，每个数组元素占用3个存储单元，从首地址SA开始按行优先连续存放。在这种情况下，元素A[8][5]的起始地址为 （  ）。

A:SA+144
B:SA+255
C:SA+222
D:SA+141
答案: SA+255

设一个稀疏矩阵有1000行850列，其中有1000个非零元素。设每个整数占2字节，数据占4字节。则用三元组表存储该矩阵时所需字节数是（）。

A:8000
B:1000
C:18000
D:4000
答案: 8000

二维数组是其数组元素为线性表的线性表。

A:错
B:对
答案: 错

用一维数组存储特殊矩阵，可以简化对矩阵的存取操作。

A:错
B:对
答案: 错

树最合适用来表示（   ）。

A:有序数据元素
B:元素之间具有分支层次关系的数据
C:无序数据元素
D:元素之间无联系的数据
答案: 元素之间具有分支层次关系的数据

一棵有n个结点的树的所有结点的度数之和为（   ）。

A:n-1
B:n+1
C:2n
D:n
答案: n-1

设树中某结点不是根结点，则离它最近的祖先结点是（      ）。

A:父结点的父结点
B:父结点
C:该结点本身     
D:根结点
答案: 父结点

在二叉树中某一结点的深度为3,高度为4,该树的髙度至少为（          ）。

A:7
B:6
C:5
D:8
答案: 6

设一棵高度为h的满二叉树有n个结点，其中有m个叶结点，则（          ）。

A:h+m=2n
B:m=h-1
C:n=2^h-1
D:n=h+m
答案: n=2^h-1

具有33个结点的完全二叉树，有（    ）个度为1的结点。

A:1
B:12
C:16
D:0
答案: 0

一颗有124个叶子结点的完全二叉树最多有（       ）个结点。

A:250
B:248
C:249
D:247
答案: 248

一颗有129个叶结点的完全二叉树最少有（   ）个结点。

A:255
B:258
C:254
D:257
答案: 257

如果二叉树T₂是由一棵树T₁转换而来的二叉树，那么T₁中结点的先根序列对应T₂的（     ）序列。

A:中序遍历          
B:层次遍历
C:后序遍历          
D:先序遍历          
答案: 先序遍历          

如果二叉树T₂是由一棵树T₁转换而来的二叉树，那么T₁中结点的后根序列对应T₂的（   ）序列。

A:层次遍历
B:先序遍历          
C:后序遍历          
D:中序遍历          
答案: 中序遍历          

一个深度为k且只有k个结点的二叉树，按照完全二叉树顺序存储的方式存放于一个一维数组A[n]中，那么n应至少是（）。

A:2^k-1
B:2k
C:2k+1
D:2^k
答案: 2^k-1

二叉树的叶子结点在前序中序和后序遍历过程中的相对顺序（  ）。

A:其余选项都不对
B:发生改变
C:无法确定
D:不发生改变
答案: 不发生改变

设nm为一棵二叉树上的两个结点，在中序遍历序列中，n在m前的条件是（）。

A:n在m右方
B:n是m的祖先
C:n是m的子孙
D:n在m左方
答案: n在m左方

在一棵二叉树中有两个结点n和m。在该二叉树的前序遍历序列中n在m之前，而在其后序遍历序列中n在m之后，则n和m的关系是（）。

A:n是m的子孙
B:n是m的左兄弟
C:n是m的祖先
D:n是m的右兄弟
答案: n是m的祖先

前序序列与中序序列正好相反的非空二叉树是（）。

A:右单支树
B:完全二叉树
C:满二叉树
D:左单支树
答案: 左单支树

在中序线索二叉树中，指针 t 所指结点的左子树为空的充要条件是（ ） 。

A:其余选项都不对
B:t->ltag==1 且 t->lchild==NULL
C:t->ltag==1
D:t->lchild== NULL
答案: t->ltag==1 且 t->lchild==NULL

设森林F对应的二叉树为A，它有m个结点。A的根为p，p的右子树中结点个数为n，则森林F中第一棵树的结点个数是（）。

A:m-n
B:n+1
C:无法确定
D:m-n-1
答案: m-n

设F是一个森林，B是由F转换得到的二叉树，F中有n个非叶结点，则B中右指针域为空的结点有（）个。

A:n-1
B:n+1
C:n
D:n+2
答案: n+1

用n个权重构造出来的Huffman 树共有（ ）个结点。

A:2n-1
B:n+1
C:2n
D:2n+1
答案: 2n-1

设T是Huffman树，具有5个叶结点，树T的高度最高可以是（）。

A:3
B:4
C:6
D:5
答案: 5