数据结构试题
一、 单选题
1、 在数据结构的讨论中把数据结构从逻辑上分为 （C ）
A 内部结构与外部结构 B 静态结构与动态结构
C 线性结构与非线性结构 D 紧凑结构与非紧凑结构。
2、采用线性链表表示一个向量时，要求占用的存储空间地址（D ）
A 必须是连续的 B 部分地址必须是连续的
C 一定是不连续的 D 可连续可不连续
3、采用顺序搜索方法查找长度为n 的顺序表时，搜索成功的平均搜索长度为（ D ）。
A n B n /2 C (n -1)/2 D (n +1)/2
4、在一个单链表中，若q 结点是p 结点的前驱结点，若在q 与p 之间插入结点s ，则执行（ D ）。
A s →link = p →link ; p →link = s ;
B p →link = s ; s →link = q ;
C p →link = s →link ; s →link = p ;
D q →link = s ; s →link = p ;
5、如果想在4092个数据中只需要选择其中最小的5个，采用（ C ）方法最好。
A 起泡排序 B 堆排序 C 锦标赛排序 D 快速排序
6、设有两个串t 和p ，求p 在t 中首次出现的位置的运算叫做（ B ）。
A 求子串 B 模式匹配 C 串替换 D 串连接
7、在数组A 中，每一个数组元素A [i][j]占用3个存储字，行下标i 从1到8，列下标j 从1到10。所有数组元素相继存放于一个连续的存储空间中，则存放
该数组至少需要的存储字数是（ C ）。
A 80 B 100 C 240 D 270
8、将一个递归算法改为对应的非递归算法时，通常需要使用（ A ）。
A 栈 B 队列 C 循环队列 D 优先队列
9、一个队列的进队列顺序是1, 2, 3, 4，则出队列顺序为（ C ）。
10、在循环队列中用数组A [0..m -1] 存放队列元素，其队头和队尾指针分别为front 和rear ，则当前队列中的元素个数是（ D ）。
A ( front - rear + 1) % m
C ( front - rear + m ) % m B ( rear - front + 1) % m D ( rear - front + m ) % m
11、一个数组元素a[i]与（ A ）的表示等价。
A *（a+i） B a+i C *a+i D &a+i
12、若需要利用形参直接访问实参，则应把形参变量说明为（ B ）参数。
A 指针 B 引用 C 值 D 变量
13、下面程序段的时间复杂度为（ C ）
for (int i=0;i
for (int j=0;j
a[i][j]=i*j;
A O(m2) B O(n2) C O(m*n) D O(m+n)
14、下面程序段的时间复杂度为（ B ）
int f(unsigned int n) {
if(n= =0 || n= =1) return 1;
else return n*f(n-1);
}
A O(1) B O(n) C O(n2) D O(n !)
15、线性表若是采用链式存储结构时，要求内存中可用存储单元的地址( D )。
A 必须是连续的
B 部分地址必须是连续的
C 一定是不连续的
D 连续或不连续都可以
16、数据结构的定义为(D，S) ，其中D 是( B )的集合。
A 算法 B数据元素 C 数据操作 D 逻辑结构
17、算法分析的目的是( A )。
A 找出数据结构的合理性
B 研究算法中输入和输出的关系
C 分析算法的效率以求改进
D 分析算法的易懂性和文档性
18、在一个单链表中，若p 所指结点不是最后结点，在p 之后插入s 所指结点，则执行( B )。
A s->link=p;p->link=s;
B s->link=p->link;p->link=s;
C s->link=p->link;p=s;
D p->link=s;s->link=p;
19、设单链表中结点结构为(data,link).已知指针q 所指结点是指针p 所指结点的直接前驱，若在*q 与*p之间插入结点*s，则应执行下列哪一个操作（ B ）
A s->link=p->link; p->link=s; B q->link=s; s->link=p
C p->link=s->link; s->link=p; D p->link=s; s->link=q;
20、设单链表中结点结构为(data,link).若想摘除结点*p的直接后继，则应执行下列哪一个操作（ A ）
A p->link=p->link->link;
B p=p->link; p->link=p->link->link;
C p->link=p->link; D p=p->link->link;
21、设单循环链表中结点的结构为（data,link ）, 且rear 是指向非空的带表头结点的单循环链表的尾结点的指针。若想删除链表第一个结点，则应执行下列哪一个操作（ D ）
A s=rear; rear=rear->link; delete s;
B rear=rear->link; delete rear;
C rear=rear->link->link; delete rear;
D s=rear->link->link; rear->link->link=s->link; delete s;s 为第一个结点硫
22、设单循环链表中结点的结构为（data,link ）, 且first 为指向链表表头的指针，current 为链表当前指针，在循环链表中检测current 是否达到链表表尾的语句是( D )。
A current->link =null B first->link=current
C first=current D current->link=first
？23、一个栈的入栈序列为a ，b ，c ，则出栈序列不可能的是( C )。
A c,b,a B b,a,c C c,a,b D a,c,b
24、栈的数组表示中，top 为栈顶指针，栈空的条件是( A )。
A top=0 B top=maxSize C top=maxSize D top=-1
25、栈和队列的共同特点是( C )。
A 都是先进后出 B 都是先进先出
C 只允许在端点处插入和删除 D 没有共同点
26、假定一个顺序存储的循环队列的队头和队尾指针分别为f 和r , 则判断队空的条件为( D ).
A f+1= =r B r+1= =f C f= =0 D f= =r
27、当利用大小为n 的数组顺序存储一个队列时，该队列的最大长度为（ B ）
A n-2 B n-1 C n D n+1
28、当利用大小为n 的数组顺序存储一个栈时，假定用top= =n 表示栈空，则向这个栈插入一个元素时，首先应执行（ ）语句修改top 指针。
A top++; B top--; C top=0; D top;
29、设链式栈中结点的结构为（data, link）, 且top 是指向栈顶的指针。若想摘除链式栈的栈顶结点，并将被摘除结点的值保存到x 中，则应执行下列（ A ）操作。
A x=top->data; top=top->link;
C x=top; top=top->link;
30、设循环队列的结构是：
const int Maxsize=100;
typedef int Data Type;
typedef struct {
Data Type data[Maxsize];
Int front, rear;
} Queue;
若有一个Queue 类型的队列Q ，试问判断队列满的条件应是下列哪一个语句（ D ）
A Q.front= = Q.rear; B Q.front - Q.rear= = Maxsize; B top=top->link; x=top->data; D x=top->data;
C Q.front + Q.rear= = Maxsize; D Q.front= = (Q.rear+1)% Maxsize;
31、设有一个递归算法如下：
int fact (int n )
{ if (n
else return n*fact(n-1);
}
下面正确的叙述是（ B ）
A 计算fact(n) 需要执行n 次递归 B fact(7)=5040
C 此递归算法最多只能计算到fact(8) D 以上结论都不对
32、设有一个递归算法如下
int x (int n) {
if (n
else return x(n-2)+x(n-4)+1;
}
试问计算 x(x(8))时需要计算（ D ）次x 函数。
A 8 次 B 9 次 C 16 次 D 18
33、设有广义表D(a,b,D),其长度为（ B ），深度为（ A ）
A ∞ B 3 C 2 D 5
次
34、广义表A(a),则表尾为（ C ）
A a B (( ) ) C 空表 D （a ）
35、下列广义表是线性表的有（ C ）
A E（a,(b,c)） B E(a,E) C E (a,b) D E(a,L( ) )
36、递归表、再入表、纯表、线性表之间的关系为（ C ）
A 再入表>递归表>纯表>线性表 B 递归表>线性表>再入表>纯表
C 递归表>再入表>纯表>线性表 D递归表>再入表>线性表>纯表
37、某二叉树的前序和后序序列正好相反，则该二叉树一定是（ B ）的二叉树。
A 空或只有一个结点 B 高度等于其结点数
C 任一结点无左孩子 D 任一结点无右孩子
38、对于任何一棵二叉树T ，如果其终端结点数为n 0，度为2的结点为n 2., 则( A )
A n0= n2+1 B n2= n0+1 C n0= 2n2+1 D n2=2n0+1
39、 由权值分别为11，8，6，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（B ）
A 24 B 73 C 48 D 53
40、已知一个顺序存储的线性表，设每个结点需占m 个存储单元，若第一个结点的地址为da1, 则第I 个结点的地址为（ A ）。
A da1+(I-1)*m B da1+I*m C da1-I*m D da1+(I+1)*m 41、34 具有35个结点的完全二叉树的深度为( A )
A 5 B 6 C 7 D 8
42、对线性表进行折半搜索时，要求线性表必须（ C ）
A 以链接方式存储且结点按关键码有序排列 B 以数组方式存储
C 以数组方式存储且结点按关键码有序排列 D以链接方式存储
43、顺序搜索算法适合于存储结构为（ B ）的线性表。
A 散列存储
C 压缩存储 B 顺序存储或链接存储 D 索引存储
44、采用折半搜索算法搜索长度为n 的有序表时，元素的平均搜索长度为（ C ）
A O（n 2） B O （n log2n ） C O（log 2n ） D O（n ）
45、对于一个具有n 个顶点和e 条边的无向图，进行拓扑排序时，总的时间为( A )
A n B n+1 C n-1 D n+e
46、判断一个有向图是否存在回路，除了可以利用拓扑排序方法外，还可以利用
（C ）。
A 求关键路径的方法 B 求最短路径的Dijkstra 方法
C 深度优先遍历算法 D 广度优先遍历算法
47、在10阶B-树中根结点所包含的关键码个数最多为（C ），最少为( A )
A 1 B 2 C 9 D 10
48、对包含n 个元素的散列表进行搜索，平均搜索长度为（ C ）
A O（log 2n ） B O（n ） C 不直接依赖于n D 上述都不对
二、 填空题（）
1、 数据的逻辑结构被分为集合结构、线性结构、树形结构、图形结构 四种
2、 数据的存储结构被分为顺序结构、链接结构、索引结构、散列结构 四种
3、一种抽象数据类型包括（数据 ）和（操作 ）两个部分。
4、 设有两个串p 和q ，求p 在q 中首次出现的位置的运算称为（模式匹配）
5、 栈、队列逻辑上都是（线性存储）结构。
6、 线性结构反映结点间的逻辑关系是（一对一）的，图中的数据元素之间的关
系是（多对多）的，树形结构中数据元素间的关系是（一对多）的。
7、栈中存取数据的原则（后进先出），队列中存取数据的原则（先进先出）
8、串是由（零个或多个）字符组成的序列。（长度为零的串）称为空串，（由一个或多个空格组成的串）称为空格串。
9、设目标串T=”abccdcdccbaa ”, 模式P=”cdcc ”则第（6）次匹配成功。
10、一维数组的逻辑结构是（线性结构），存储结构是（顺序存储表示）。对于二维数组，有（行优先顺序）和（列优先顺序）两种不同的存储方式，对于一个二维数 组A[m][n],若采用按行优先存放的方式，则任一数组元素A[i][j]相对于A[0][0]的地址为（ n*i+j）。
11、向一个顺序栈插入一个元素时，首先使（ 栈顶指针 ）后移一个位置，然后把待插入元素（ 写 ）到这个位置上。从一个顺序栈删除元素时，需要前移一位
14、一棵高度为5的满二叉树中的结点数为（ 63 ）个，一棵高度为3满四叉树中的结点数为（ 85 ）个。
15、若对一棵二叉树从0开始进行结点编号，并按此编号把它顺序存储到一维数组中，即编号为0的结点存储到a[0]中，其余类推，则a[i]元素的左子女结点为（ 2*i+1），右子女结点为（2*i+2 ），双亲结点（i>=1）为（「(i-1)/2 ┐）.
16、在一个最大堆中，堆顶结点的值是所有结点中的（最大值），在一个最小堆中，堆顶结点的值是所有结点中的（最小值）。
17、已知具有n 个元素的一维数组采用顺序存储结构，每个元素占k 个存储单元，第一个元素的地址为LOC(a1)，那么，LOC(ai)= LOC(a1)+(i-1)*k 。
18、在霍夫曼编码中，若编码长度只允许小于等于4, 则除掉已对两个字符编码为0和10外，还可以最多对（ 4 ）个字符编码。
19、设高度为h 的空二叉树的高度为-1，只有一个结点的二叉树的高度为0，若
设二叉树只有度为2上度为0的结点，则该二叉树中所含结点至少有（2h+1）个。
20、由一棵二叉树的前序序列和（中序序列）可唯一确定这棵二叉树。
21、以折半搜索方法搜索一个线性表时，此线性表必须是（顺序）存储的（有序）表。
22、已知完全二叉树的第8层有8个结点，则其叶子结点数是（68）。若完全二叉树的第7有10个叶子结点，则整个二叉树的结点数最多是（235）
23、对于折半搜索所对应的判定树，它既是一棵（二叉搜索树），又是一棵（理想平衡树）。
24、假定对长度n=50的有序表进行折半搜索，则对应的判定树高度为（ ５ ），判定树中前５层的结点数为（３１），最后一层的结点数为（１９）。
25、在一个无向图中，所有顶点的度数之和等于所有边数的（２）倍。在一个具有n 个顶点的无向完全图中，包含有（ n(n-1)/2 ）条边，在一个具有n 个顶点的有向完全图中，包含有（ n(n-1) ）条边。
26、对于一个具有n 个顶点和e 条边的连通图，其生成树中的顶点数和边数分别为（n ）和（n-1）。
27、设线性表中元素的类型是实型，其首地址为1024，则线性表中第6个元素的存储位置是(1044)。
28、在插入和选择排序中，若初始数据基本正序，则选择（插入排序），若初始数据基本反序，则最好选择（选择排序）。
29、算法是对特定问题的求解步驟的一种描述，它是（指令）的有限序列，每一条（指令）表示一个或多个操作。
30、对于一个具有n 个顶点肯e 条边的无向图，进行拓朴排序时，总的进间为（n ）
31、构造哈希函数有三种方法，分别为(平方取中) 法、(除留余数) 法、(折迭移位) 法。
32、处理冲突的三种方法，分别为(线性探测) 、（ 随机探测 ）、（ 链地址法）。 33、对于含有n 个顶点和e 条边的无向连通图，利用普里姆算法产生的最小生成树，其时间复杂度为（ Ｏ（n 2） ）、利用克鲁斯卡尔算法产生的最小生成树，其时间复杂度为（Ｏ（elog 2e ） ）
34、快速排序在平均情况下的时间复杂度为（Ｏ（nlog 2n ）），在最坏情况下的时间复杂度为（Ｏ（n 2））；快速排序在平均情况下的空间复杂度为（Ｏ（log 2n ）），在最坏情况下的空间复杂度为（Ｏ（n ））。
35、假定一组记录的排序码为（４６，７９，５６，３８，４０，８０），对其进行归并排序的过程中，第二趟排序后的结果是（［３８ ４６ ５６ ７９］［４０ ８０］）
36、假定一组记录的排序码为（４６，７９，５６，３８，４０，８０），对其进行快速排序的第一次划分的结果是（［３８ ４０］４６［５６ ７９ ８０］）。 37、一个结点的子树的（个数）称为该结点的度。度为（零）的结点称为叶结点或终端结点。度不为（零）的结点称为分支结点或非终端结点。树中各结点度的（最大值）称为树的度。
38、设K i =Kj (1i)且在排序前的序列中R i 领先于R j (i
40 、在堆排序的过程中，对任一分支结点进行调整运算的时间复杂度为（Ｏ（log 2n ）），整个排序过程的时间复杂度为（Ｏ（nlog 2n ））。
41、在索引表中，每个索引项至少包含有（关键码值）域和（子表地址）域这两项。
42、假定一个线性表为
（”abcd ”, ”baabd ”, ”bcef ”, ”cfg ”, ”ahij ”, ”bkwte ”, ”ccdt ”, ”a ayb ”）, 若按照字符串的第一个字母进行划分，使得同一个字母被划分在一个子表中，则得到的a,b,c 三个子表的长度分别为（３），（３），（２）。
43、对于包含５０个关键码的３阶B-树，其最小高度为（４），最大高度为（５）。 44、从一棵B-树删除关键码的过程，若最终引起树根结点的合并，则新树比原树的高度（减１）
45、假定要对长度n=100的线性表进行散列存储，并采用开散列法处理冲突，则对于长度m=20的散列表，每个散列地址的同义词子表的长度平均为（５）。
46、在散列存储中，装载因子α又称为装载系数，若用m 表示散列表的长度，n 表示待散列存储的元素的个数，则α等于（n/m）。
47、在有向图的邻接矩阵中，第i 行中“1”的个数是第i 个顶点的（出度），第i 列中“1”的个数是第i 个顶点的（入度）。在无向图的邻接矩阵中，第i 行（列）中“1”的个数是第i 个顶点的（度），矩阵中“1”的个数的一半是图中的（边数）。
48、在对m 阶B-树中，每个非根结点的关键码数最少为（「m/2┐-1）个，最多为（m-1）个，其子树棵数最少为（「m/2┐），最多为（m ）。 三、
判断题
四、运算应用题
1、在一个有n 个元素的顺序表的第i 个元素（1 ≤ i ≤ n ）之前插入一个新元素时，需要向后移动多少个元素？ 答案：需要向后移动 n- i + 1个元素
2、 当一个栈的进栈序列为1234567时，可能的出栈序列有多少种？6457321
是否是合理的出栈序列？ 答案：
1114*13*12*11*10*9*87
C 14=*=4297+187*6*5*4*3*2*1
可能的出栈序列有
种，6457321不是合理的出栈序列。
4、设有序顺序表为 { 10, 20, 30, 40, 50, 60, 70 }，采用折半搜索时，搜索成功的平均搜索长度是多少？ 答案：
ASL succ = (1*1 + 2*2 + 3*4 ) / 7 = 17 / 7
5、 在结点个数为n(n>1)的各棵树中，高度最小的树的高度是多少？它有多少个叶结点？多少个分支结点？高度最大的树的高度是多少？它有多少个叶结点？多少个分支结点？
答案：结点个数为n 时，高度最小的树的高度为1，有2层；它有n-1个叶结点，1个分支结点；高度最大的树的高度为n-1, 有n 层；它有1个叶结点，n-1个分支结点。
6、 一棵高度为h 的满k 叉树有如下性质: 第h 层上的结点都是叶结点, 其余各层上每个结点都有k 棵非空子树, 如果按层次自顶向下, 同一层自左向右, 顺序从1开始对全部结点进行编号, 试问:
(1) 各层的结点个数是多少?
(2) 编号为i 的结点的父结点(若存在) 的编号是多少?
(3) 编号为i 的结点的第m 个孩子结点(若存在) 的编号是多少?
(4) 编号为i 的结点有右兄弟的条件是什么? 其右兄弟结点的编号是多少?
(5) 若结点个数为 n, 则高度h 是n 的什么函数关系?
答案：
（1）各层的结点个数是k i (i=0,1,2,....,h)
（2）编号为i 的结点的父结点(若存在) 的编号是└ (i+k-2)/k」 （3）编号为i 的结点的第m 个孩子结点(若存在) 的编号是(i-1)*k+m+1 （4）当(i-1)%k0时有右兄弟， 右兄弟的编号为 i+1
（5）若结点个数为 n ，则高度h 和n 的关系为：h=logk (n*(k-1)+1)-1 (n=0时h=-1)
9、题目：11、将下面的森林变换成二叉树（7分）。 答案：
10、将算术表达式 ((a+b)+c*(d+e)+f)*(g+h) 转化为二叉树。（7分） 答案：
12、 将给定的图简化为最小的生成树，要求从顶点1出发。（7分）
答案:
13、某子系统在通信联络中只可能出现8种字符，其出现的概率分别为0.05，0.29，0.07，0.08，0.14，0.23，0.03，0.11试设计赫夫曼编码。 答案：
为方便起见，设各种字符的权值w={5,29,7,8,14,23,3,11}。因为n=8，所以要构造的赫夫曼树共有m=2n-1=2*8-1=15个结点。生成的赫夫曼树为下图所示：
赫夫曼编码为：概率为0.23的字符编码为：00 概率为0.11的字符编码为：010
概率为0.05的字符编码为：0110 概率为0.03的字符编码为：0111 概率为0.29的字符编码为：10
概率为0.14的字符编码为：110 概率为0.07的字符编码为：1110 概率为0.08的字符编码为：1111
14、已知一棵二叉树的前序遍历的结果是ABECDFGHIJ, 中序遍历的结果是EBCDAFHIGJ, 试画出这棵二叉树，并给出这棵二叉树的后序遍历序列。 答案：根据前序序列和中序序列能得到唯一的二叉树，所得二叉树如图：
这棵二叉树的后序遍历序列为：EDCBIHJGFA
15、在结点个数为n(n>1)的各棵树中，高度最小的树的高度是多少？它有多少个叶结点？多少个分支结点？高度最大的树的高度是多少？它有多少个叶结点？多少个分支结点？
答案：结点个数为n 时，高度最小的树的高度为1，有2层；它有n-1个叶结点，1个分支结点；高度最大的树的高度为n-1, 有n 层；它有1个叶结点，n-1个分支结点。
16、 对于一个高度为h 的AVL 树，其最少结点数是多少？反之，对于一个有n 个结点的AVL 树, 其最大高度是多少? 最小高度是多少?
答案：设高度为h(空树的高度为-1) 的AVL 树的最少结点为N h ，则N h = Fh+3 -1。 F h 是斐波那契数。又设AVL 树有n 个结点，则其最大高度不超过3/2*log2(n+1),
最小高度为「log 2(n+1) ┐-1。
17、7-7 设有序顺序表中的元素依次为017, 094, 154, 170, 275,503, 509, 512, 553, 612, 677, 765, 897, 908。试画出对其进行折半搜索时的判定树, 并计算搜索成功的平均搜索长度和搜索不成功的平均搜索长度。
ASL SUCC =1/14（1+2*2+3*4+4*7）=45/14 ASL UNSUCC =1/15（3*1+4*14）=59/15
五、算法分析题
6、请读下列程序，该程序是在单链表中删除一个结点的算法，为空出的地方填上正确的语句。（7分）
void demo2(LinkList head,ListNode *p) {//head 是带头结点的单链表，删除P 指向的结点 ListNode *q=head;
while(q&&q->next!=p ) q=q->next; if (q) Error(“*p not in head”); q->next=p->next; free(p);
}
10、判断一个带表头结点的双向循环链表L 是否对称相等的算法如下所示，请在算法的 处填入正确的语句。 int symmetry(DblList DL) { int sym=1;
DblNode p=DL->rLink,q=DL->lLink; While(p!=q&&p->lLink==q)&& sym==1 ) if (p->data==q->data){ p=p->rLink; q=q->lLink; }
else sym=0; return sym;}
数据结构试题
一、 单选题
1、 在数据结构的讨论中把数据结构从逻辑上分为 （C ）
A 内部结构与外部结构 B 静态结构与动态结构
C 线性结构与非线性结构 D 紧凑结构与非紧凑结构。
2、采用线性链表表示一个向量时，要求占用的存储空间地址（D ）
A 必须是连续的 B 部分地址必须是连续的
C 一定是不连续的 D 可连续可不连续
3、采用顺序搜索方法查找长度为n 的顺序表时，搜索成功的平均搜索长度为（ D ）。
A n B n /2 C (n -1)/2 D (n +1)/2
4、在一个单链表中，若q 结点是p 结点的前驱结点，若在q 与p 之间插入结点s ，则执行（ D ）。
A s →link = p →link ; p →link = s ;
B p →link = s ; s →link = q ;
C p →link = s →link ; s →link = p ;
D q →link = s ; s →link = p ;
5、如果想在4092个数据中只需要选择其中最小的5个，采用（ C ）方法最好。
A 起泡排序 B 堆排序 C 锦标赛排序 D 快速排序
6、设有两个串t 和p ，求p 在t 中首次出现的位置的运算叫做（ B ）。
A 求子串 B 模式匹配 C 串替换 D 串连接
7、在数组A 中，每一个数组元素A [i][j]占用3个存储字，行下标i 从1到8，列下标j 从1到10。所有数组元素相继存放于一个连续的存储空间中，则存放
该数组至少需要的存储字数是（ C ）。
A 80 B 100 C 240 D 270
8、将一个递归算法改为对应的非递归算法时，通常需要使用（ A ）。
A 栈 B 队列 C 循环队列 D 优先队列
9、一个队列的进队列顺序是1, 2, 3, 4，则出队列顺序为（ C ）。
10、在循环队列中用数组A [0..m -1] 存放队列元素，其队头和队尾指针分别为front 和rear ，则当前队列中的元素个数是（ D ）。
A ( front - rear + 1) % m
C ( front - rear + m ) % m B ( rear - front + 1) % m D ( rear - front + m ) % m
11、一个数组元素a[i]与（ A ）的表示等价。
A *（a+i） B a+i C *a+i D &a+i
12、若需要利用形参直接访问实参，则应把形参变量说明为（ B ）参数。
A 指针 B 引用 C 值 D 变量
13、下面程序段的时间复杂度为（ C ）
for (int i=0;i
for (int j=0;j
a[i][j]=i*j;
A O(m2) B O(n2) C O(m*n) D O(m+n)
14、下面程序段的时间复杂度为（ B ）
int f(unsigned int n) {
if(n= =0 || n= =1) return 1;
else return n*f(n-1);
}
A O(1) B O(n) C O(n2) D O(n !)
15、线性表若是采用链式存储结构时，要求内存中可用存储单元的地址( D )。
A 必须是连续的
B 部分地址必须是连续的
C 一定是不连续的
D 连续或不连续都可以
16、数据结构的定义为(D，S) ，其中D 是( B )的集合。
A 算法 B数据元素 C 数据操作 D 逻辑结构
17、算法分析的目的是( A )。
A 找出数据结构的合理性
B 研究算法中输入和输出的关系
C 分析算法的效率以求改进
D 分析算法的易懂性和文档性
18、在一个单链表中，若p 所指结点不是最后结点，在p 之后插入s 所指结点，则执行( B )。
A s->link=p;p->link=s;
B s->link=p->link;p->link=s;
C s->link=p->link;p=s;
D p->link=s;s->link=p;
19、设单链表中结点结构为(data,link).已知指针q 所指结点是指针p 所指结点的直接前驱，若在*q 与*p之间插入结点*s，则应执行下列哪一个操作（ B ）
A s->link=p->link; p->link=s; B q->link=s; s->link=p
C p->link=s->link; s->link=p; D p->link=s; s->link=q;
20、设单链表中结点结构为(data,link).若想摘除结点*p的直接后继，则应执行下列哪一个操作（ A ）
A p->link=p->link->link;
B p=p->link; p->link=p->link->link;
C p->link=p->link; D p=p->link->link;
21、设单循环链表中结点的结构为（data,link ）, 且rear 是指向非空的带表头结点的单循环链表的尾结点的指针。若想删除链表第一个结点，则应执行下列哪一个操作（ D ）
A s=rear; rear=rear->link; delete s;
B rear=rear->link; delete rear;
C rear=rear->link->link; delete rear;
D s=rear->link->link; rear->link->link=s->link; delete s;s 为第一个结点硫
22、设单循环链表中结点的结构为（data,link ）, 且first 为指向链表表头的指针，current 为链表当前指针，在循环链表中检测current 是否达到链表表尾的语句是( D )。
A current->link =null B first->link=current
C first=current D current->link=first
？23、一个栈的入栈序列为a ，b ，c ，则出栈序列不可能的是( C )。
A c,b,a B b,a,c C c,a,b D a,c,b
24、栈的数组表示中，top 为栈顶指针，栈空的条件是( A )。
A top=0 B top=maxSize C top=maxSize D top=-1
25、栈和队列的共同特点是( C )。
A 都是先进后出 B 都是先进先出
C 只允许在端点处插入和删除 D 没有共同点
26、假定一个顺序存储的循环队列的队头和队尾指针分别为f 和r , 则判断队空的条件为( D ).
A f+1= =r B r+1= =f C f= =0 D f= =r
27、当利用大小为n 的数组顺序存储一个队列时，该队列的最大长度为（ B ）
A n-2 B n-1 C n D n+1
28、当利用大小为n 的数组顺序存储一个栈时，假定用top= =n 表示栈空，则向这个栈插入一个元素时，首先应执行（ ）语句修改top 指针。
A top++; B top--; C top=0; D top;
29、设链式栈中结点的结构为（data, link）, 且top 是指向栈顶的指针。若想摘除链式栈的栈顶结点，并将被摘除结点的值保存到x 中，则应执行下列（ A ）操作。
A x=top->data; top=top->link;
C x=top; top=top->link;
30、设循环队列的结构是：
const int Maxsize=100;
typedef int Data Type;
typedef struct {
Data Type data[Maxsize];
Int front, rear;
} Queue;
若有一个Queue 类型的队列Q ，试问判断队列满的条件应是下列哪一个语句（ D ）
A Q.front= = Q.rear; B Q.front - Q.rear= = Maxsize; B top=top->link; x=top->data; D x=top->data;
C Q.front + Q.rear= = Maxsize; D Q.front= = (Q.rear+1)% Maxsize;
31、设有一个递归算法如下：
int fact (int n )
{ if (n
else return n*fact(n-1);
}
下面正确的叙述是（ B ）
A 计算fact(n) 需要执行n 次递归 B fact(7)=5040
C 此递归算法最多只能计算到fact(8) D 以上结论都不对
32、设有一个递归算法如下
int x (int n) {
if (n
else return x(n-2)+x(n-4)+1;
}
试问计算 x(x(8))时需要计算（ D ）次x 函数。
A 8 次 B 9 次 C 16 次 D 18
33、设有广义表D(a,b,D),其长度为（ B ），深度为（ A ）
A ∞ B 3 C 2 D 5
次
34、广义表A(a),则表尾为（ C ）
A a B (( ) ) C 空表 D （a ）
35、下列广义表是线性表的有（ C ）
A E（a,(b,c)） B E(a,E) C E (a,b) D E(a,L( ) )
36、递归表、再入表、纯表、线性表之间的关系为（ C ）
A 再入表>递归表>纯表>线性表 B 递归表>线性表>再入表>纯表
C 递归表>再入表>纯表>线性表 D递归表>再入表>线性表>纯表
37、某二叉树的前序和后序序列正好相反，则该二叉树一定是（ B ）的二叉树。
A 空或只有一个结点 B 高度等于其结点数
C 任一结点无左孩子 D 任一结点无右孩子
38、对于任何一棵二叉树T ，如果其终端结点数为n 0，度为2的结点为n 2., 则( A )
A n0= n2+1 B n2= n0+1 C n0= 2n2+1 D n2=2n0+1
39、 由权值分别为11，8，6，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（B ）
A 24 B 73 C 48 D 53
40、已知一个顺序存储的线性表，设每个结点需占m 个存储单元，若第一个结点的地址为da1, 则第I 个结点的地址为（ A ）。
A da1+(I-1)*m B da1+I*m C da1-I*m D da1+(I+1)*m 41、34 具有35个结点的完全二叉树的深度为( A )
A 5 B 6 C 7 D 8
42、对线性表进行折半搜索时，要求线性表必须（ C ）
A 以链接方式存储且结点按关键码有序排列 B 以数组方式存储
C 以数组方式存储且结点按关键码有序排列 D以链接方式存储
43、顺序搜索算法适合于存储结构为（ B ）的线性表。
A 散列存储
C 压缩存储 B 顺序存储或链接存储 D 索引存储
44、采用折半搜索算法搜索长度为n 的有序表时，元素的平均搜索长度为（ C ）
A O（n 2） B O （n log2n ） C O（log 2n ） D O（n ）
45、对于一个具有n 个顶点和e 条边的无向图，进行拓扑排序时，总的时间为( A )
A n B n+1 C n-1 D n+e
46、判断一个有向图是否存在回路，除了可以利用拓扑排序方法外，还可以利用
（C ）。
A 求关键路径的方法 B 求最短路径的Dijkstra 方法
C 深度优先遍历算法 D 广度优先遍历算法
47、在10阶B-树中根结点所包含的关键码个数最多为（C ），最少为( A )
A 1 B 2 C 9 D 10
48、对包含n 个元素的散列表进行搜索，平均搜索长度为（ C ）
A O（log 2n ） B O（n ） C 不直接依赖于n D 上述都不对
二、 填空题（）
1、 数据的逻辑结构被分为集合结构、线性结构、树形结构、图形结构 四种
2、 数据的存储结构被分为顺序结构、链接结构、索引结构、散列结构 四种
3、一种抽象数据类型包括（数据 ）和（操作 ）两个部分。
4、 设有两个串p 和q ，求p 在q 中首次出现的位置的运算称为（模式匹配）
5、 栈、队列逻辑上都是（线性存储）结构。
6、 线性结构反映结点间的逻辑关系是（一对一）的，图中的数据元素之间的关
系是（多对多）的，树形结构中数据元素间的关系是（一对多）的。
7、栈中存取数据的原则（后进先出），队列中存取数据的原则（先进先出）
8、串是由（零个或多个）字符组成的序列。（长度为零的串）称为空串，（由一个或多个空格组成的串）称为空格串。
9、设目标串T=”abccdcdccbaa ”, 模式P=”cdcc ”则第（6）次匹配成功。
10、一维数组的逻辑结构是（线性结构），存储结构是（顺序存储表示）。对于二维数组，有（行优先顺序）和（列优先顺序）两种不同的存储方式，对于一个二维数 组A[m][n],若采用按行优先存放的方式，则任一数组元素A[i][j]相对于A[0][0]的地址为（ n*i+j）。
11、向一个顺序栈插入一个元素时，首先使（ 栈顶指针 ）后移一个位置，然后把待插入元素（ 写 ）到这个位置上。从一个顺序栈删除元素时，需要前移一位
14、一棵高度为5的满二叉树中的结点数为（ 63 ）个，一棵高度为3满四叉树中的结点数为（ 85 ）个。
15、若对一棵二叉树从0开始进行结点编号，并按此编号把它顺序存储到一维数组中，即编号为0的结点存储到a[0]中，其余类推，则a[i]元素的左子女结点为（ 2*i+1），右子女结点为（2*i+2 ），双亲结点（i>=1）为（「(i-1)/2 ┐）.
16、在一个最大堆中，堆顶结点的值是所有结点中的（最大值），在一个最小堆中，堆顶结点的值是所有结点中的（最小值）。
17、已知具有n 个元素的一维数组采用顺序存储结构，每个元素占k 个存储单元，第一个元素的地址为LOC(a1)，那么，LOC(ai)= LOC(a1)+(i-1)*k 。
18、在霍夫曼编码中，若编码长度只允许小于等于4, 则除掉已对两个字符编码为0和10外，还可以最多对（ 4 ）个字符编码。
19、设高度为h 的空二叉树的高度为-1，只有一个结点的二叉树的高度为0，若
设二叉树只有度为2上度为0的结点，则该二叉树中所含结点至少有（2h+1）个。
20、由一棵二叉树的前序序列和（中序序列）可唯一确定这棵二叉树。
21、以折半搜索方法搜索一个线性表时，此线性表必须是（顺序）存储的（有序）表。
22、已知完全二叉树的第8层有8个结点，则其叶子结点数是（68）。若完全二叉树的第7有10个叶子结点，则整个二叉树的结点数最多是（235）
23、对于折半搜索所对应的判定树，它既是一棵（二叉搜索树），又是一棵（理想平衡树）。
24、假定对长度n=50的有序表进行折半搜索，则对应的判定树高度为（ ５ ），判定树中前５层的结点数为（３１），最后一层的结点数为（１９）。
25、在一个无向图中，所有顶点的度数之和等于所有边数的（２）倍。在一个具有n 个顶点的无向完全图中，包含有（ n(n-1)/2 ）条边，在一个具有n 个顶点的有向完全图中，包含有（ n(n-1) ）条边。
26、对于一个具有n 个顶点和e 条边的连通图，其生成树中的顶点数和边数分别为（n ）和（n-1）。
27、设线性表中元素的类型是实型，其首地址为1024，则线性表中第6个元素的存储位置是(1044)。
28、在插入和选择排序中，若初始数据基本正序，则选择（插入排序），若初始数据基本反序，则最好选择（选择排序）。
29、算法是对特定问题的求解步驟的一种描述，它是（指令）的有限序列，每一条（指令）表示一个或多个操作。
30、对于一个具有n 个顶点肯e 条边的无向图，进行拓朴排序时，总的进间为（n ）
31、构造哈希函数有三种方法，分别为(平方取中) 法、(除留余数) 法、(折迭移位) 法。
32、处理冲突的三种方法，分别为(线性探测) 、（ 随机探测 ）、（ 链地址法）。 33、对于含有n 个顶点和e 条边的无向连通图，利用普里姆算法产生的最小生成树，其时间复杂度为（ Ｏ（n 2） ）、利用克鲁斯卡尔算法产生的最小生成树，其时间复杂度为（Ｏ（elog 2e ） ）
34、快速排序在平均情况下的时间复杂度为（Ｏ（nlog 2n ）），在最坏情况下的时间复杂度为（Ｏ（n 2））；快速排序在平均情况下的空间复杂度为（Ｏ（log 2n ）），在最坏情况下的空间复杂度为（Ｏ（n ））。
35、假定一组记录的排序码为（４６，７９，５６，３８，４０，８０），对其进行归并排序的过程中，第二趟排序后的结果是（［３８ ４６ ５６ ７９］［４０ ８０］）
36、假定一组记录的排序码为（４６，７９，５６，３８，４０，８０），对其进行快速排序的第一次划分的结果是（［３８ ４０］４６［５６ ７９ ８０］）。 37、一个结点的子树的（个数）称为该结点的度。度为（零）的结点称为叶结点或终端结点。度不为（零）的结点称为分支结点或非终端结点。树中各结点度的（最大值）称为树的度。
38、设K i =Kj (1i)且在排序前的序列中R i 领先于R j (i
40 、在堆排序的过程中，对任一分支结点进行调整运算的时间复杂度为（Ｏ（log 2n ）），整个排序过程的时间复杂度为（Ｏ（nlog 2n ））。
41、在索引表中，每个索引项至少包含有（关键码值）域和（子表地址）域这两项。
42、假定一个线性表为
（”abcd ”, ”baabd ”, ”bcef ”, ”cfg ”, ”ahij ”, ”bkwte ”, ”ccdt ”, ”a ayb ”）, 若按照字符串的第一个字母进行划分，使得同一个字母被划分在一个子表中，则得到的a,b,c 三个子表的长度分别为（３），（３），（２）。
43、对于包含５０个关键码的３阶B-树，其最小高度为（４），最大高度为（５）。 44、从一棵B-树删除关键码的过程，若最终引起树根结点的合并，则新树比原树的高度（减１）
45、假定要对长度n=100的线性表进行散列存储，并采用开散列法处理冲突，则对于长度m=20的散列表，每个散列地址的同义词子表的长度平均为（５）。
46、在散列存储中，装载因子α又称为装载系数，若用m 表示散列表的长度，n 表示待散列存储的元素的个数，则α等于（n/m）。
47、在有向图的邻接矩阵中，第i 行中“1”的个数是第i 个顶点的（出度），第i 列中“1”的个数是第i 个顶点的（入度）。在无向图的邻接矩阵中，第i 行（列）中“1”的个数是第i 个顶点的（度），矩阵中“1”的个数的一半是图中的（边数）。
48、在对m 阶B-树中，每个非根结点的关键码数最少为（「m/2┐-1）个，最多为（m-1）个，其子树棵数最少为（「m/2┐），最多为（m ）。 三、
判断题
四、运算应用题
1、在一个有n 个元素的顺序表的第i 个元素（1 ≤ i ≤ n ）之前插入一个新元素时，需要向后移动多少个元素？ 答案：需要向后移动 n- i + 1个元素
2、 当一个栈的进栈序列为1234567时，可能的出栈序列有多少种？6457321
是否是合理的出栈序列？ 答案：
1114*13*12*11*10*9*87
C 14=*=4297+187*6*5*4*3*2*1
可能的出栈序列有
种，6457321不是合理的出栈序列。
4、设有序顺序表为 { 10, 20, 30, 40, 50, 60, 70 }，采用折半搜索时，搜索成功的平均搜索长度是多少？ 答案：
ASL succ = (1*1 + 2*2 + 3*4 ) / 7 = 17 / 7
5、 在结点个数为n(n>1)的各棵树中，高度最小的树的高度是多少？它有多少个叶结点？多少个分支结点？高度最大的树的高度是多少？它有多少个叶结点？多少个分支结点？
答案：结点个数为n 时，高度最小的树的高度为1，有2层；它有n-1个叶结点，1个分支结点；高度最大的树的高度为n-1, 有n 层；它有1个叶结点，n-1个分支结点。
6、 一棵高度为h 的满k 叉树有如下性质: 第h 层上的结点都是叶结点, 其余各层上每个结点都有k 棵非空子树, 如果按层次自顶向下, 同一层自左向右, 顺序从1开始对全部结点进行编号, 试问:
(1) 各层的结点个数是多少?
(2) 编号为i 的结点的父结点(若存在) 的编号是多少?
(3) 编号为i 的结点的第m 个孩子结点(若存在) 的编号是多少?
(4) 编号为i 的结点有右兄弟的条件是什么? 其右兄弟结点的编号是多少?
(5) 若结点个数为 n, 则高度h 是n 的什么函数关系?
答案：
（1）各层的结点个数是k i (i=0,1,2,....,h)
（2）编号为i 的结点的父结点(若存在) 的编号是└ (i+k-2)/k」 （3）编号为i 的结点的第m 个孩子结点(若存在) 的编号是(i-1)*k+m+1 （4）当(i-1)%k0时有右兄弟， 右兄弟的编号为 i+1
（5）若结点个数为 n ，则高度h 和n 的关系为：h=logk (n*(k-1)+1)-1 (n=0时h=-1)
9、题目：11、将下面的森林变换成二叉树（7分）。 答案：
10、将算术表达式 ((a+b)+c*(d+e)+f)*(g+h) 转化为二叉树。（7分） 答案：
12、 将给定的图简化为最小的生成树，要求从顶点1出发。（7分）
答案:
13、某子系统在通信联络中只可能出现8种字符，其出现的概率分别为0.05，0.29，0.07，0.08，0.14，0.23，0.03，0.11试设计赫夫曼编码。 答案：
为方便起见，设各种字符的权值w={5,29,7,8,14,23,3,11}。因为n=8，所以要构造的赫夫曼树共有m=2n-1=2*8-1=15个结点。生成的赫夫曼树为下图所示：
赫夫曼编码为：概率为0.23的字符编码为：00 概率为0.11的字符编码为：010
概率为0.05的字符编码为：0110 概率为0.03的字符编码为：0111 概率为0.29的字符编码为：10
概率为0.14的字符编码为：110 概率为0.07的字符编码为：1110 概率为0.08的字符编码为：1111
14、已知一棵二叉树的前序遍历的结果是ABECDFGHIJ, 中序遍历的结果是EBCDAFHIGJ, 试画出这棵二叉树，并给出这棵二叉树的后序遍历序列。 答案：根据前序序列和中序序列能得到唯一的二叉树，所得二叉树如图：
这棵二叉树的后序遍历序列为：EDCBIHJGFA
15、在结点个数为n(n>1)的各棵树中，高度最小的树的高度是多少？它有多少个叶结点？多少个分支结点？高度最大的树的高度是多少？它有多少个叶结点？多少个分支结点？
答案：结点个数为n 时，高度最小的树的高度为1，有2层；它有n-1个叶结点，1个分支结点；高度最大的树的高度为n-1, 有n 层；它有1个叶结点，n-1个分支结点。
16、 对于一个高度为h 的AVL 树，其最少结点数是多少？反之，对于一个有n 个结点的AVL 树, 其最大高度是多少? 最小高度是多少?
答案：设高度为h(空树的高度为-1) 的AVL 树的最少结点为N h ，则N h = Fh+3 -1。 F h 是斐波那契数。又设AVL 树有n 个结点，则其最大高度不超过3/2*log2(n+1),
最小高度为「log 2(n+1) ┐-1。
17、7-7 设有序顺序表中的元素依次为017, 094, 154, 170, 275,503, 509, 512, 553, 612, 677, 765, 897, 908。试画出对其进行折半搜索时的判定树, 并计算搜索成功的平均搜索长度和搜索不成功的平均搜索长度。
ASL SUCC =1/14（1+2*2+3*4+4*7）=45/14 ASL UNSUCC =1/15（3*1+4*14）=59/15
五、算法分析题
6、请读下列程序，该程序是在单链表中删除一个结点的算法，为空出的地方填上正确的语句。（7分）
void demo2(LinkList head,ListNode *p) {//head 是带头结点的单链表，删除P 指向的结点 ListNode *q=head;
while(q&&q->next!=p ) q=q->next; if (q) Error(“*p not in head”); q->next=p->next; free(p);
}
10、判断一个带表头结点的双向循环链表L 是否对称相等的算法如下所示，请在算法的 处填入正确的语句。 int symmetry(DblList DL) { int sym=1;
DblNode p=DL->rLink,q=DL->lLink; While(p!=q&&p->lLink==q)&& sym==1 ) if (p->data==q->data){ p=p->rLink; q=q->lLink; }
else sym=0; return sym;}