《数据结构》试卷（C卷）
一、单项选择题
1. 空串与空格字符组成的串的区别在于（ ）。
A.没有区别 B.两串的长度不相等
C.两串的长度相等 D.两串包含的字符不相同
2. 一个子串在包含它的主串中的位置是指（ ）。
A.子串的最后那个字符在主串中的位置
B.子串的最后那个字符在主串中首次出现的位置
C.子串的第一个字符在主串中的位置
D.子串的第一个字符在主串中首次出现的位置
3. 下面的说法中，只有（ ）是正确的。
A.字符串的长度是指串中包含的字母的个数
B.字符串的长度是指串中包含的不同字符的个数
C.若T包含在S中，则T一定是S的一个子串
D.一个字符串不能说是其自身的一个子串
4. 两个字符串相等的条件是（ ）。
A.两串的长度相等
B.两串包含的字符相同
C.两串的长度相等，并且两串包含的字符相同
D.两串的长度相等，并且对应位置上的字符相同
5. 若SUBSTR（S，i，k）表示求S中从第i个字符开始的连续k个字符组成的子串的操作，则对于S=“Beijing＆Nanjing”，SUBSTR（S，4，5）=（ ）。
A. “ijing” B. “jing＆”
C. “ingNa” D. “ing＆N”
6. 若INDEX（S，T）表示求T在S中的位置的操作，则对于S=“Beijing＆Nanjing”，T=“jing”，INDEX（S，T）=（ ）。
A.2 B.3 C.4 D.5
7. 若REPLACE（S，S1，S2）表示用字符串S2替换字符串S中的子串S1的操作，则对于S=“Beijing＆Nanjing”，S1=“Beijing”，S2=“Shanghai”，REPLACE（S，S1，S2）=（ ）。
A. “Nanjing＆Shanghai” B. “Nanjing＆Nanjing”
C. “ShanghaiNanjing” D. “Shanghai＆Nanjing”
8. 在长度为n的字符串S的第i个位置插入另外一个字符串，i的合法值应该是（ ）。
A.i＞0 B. i≤n
C.1≤i≤n D.1≤i≤n+1
9. 字符串采用结点大小为1的链表作为其存储结构，是指（ ）。
A.链表的长度为1
B.链表中只存放1个字符
C.链表的每个链结点的数据域中不仅只存放了一个字符
D.链表的每个链结点的数据域中只存放了一个字符
10. 在一棵度为3的树中，度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数为（ ）个。
A. 4 B. 5 C. 6 D. 7
11. 假设在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子结点数为（ ）个。
A. 15 B. 16 C. 17 D. 47
12. 假定一棵三叉树的结点数为50，则它的最小高度为（ ）。
A. 3 B. 4 C. 5 D. 6
13. 在一棵二叉树上第4层的结点数最多为（ ）。
A. 2 B. 4 C. 6 D. 8
14. 用顺序存储的方法将完全二叉树中的所有结点逐层存放在数组中R[1..n]，结点R[i]若有左孩子，其左孩子的编号为结点（ ）。
A. R[2i+1] B. R[2i] C. R[i/2] D. R[2i-1]
15. 由权值分别为3,8,6,2,5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（ ）。
A. 24 B. 48 C. 72 D. 53
16. 线索二叉树是一种（ ）结构。
A. 逻辑 B. 逻辑和存储 C. 物理 D. 线性
17. 线索二叉树中，结点p没有左子树的充要条件是（ ）。
A. p->lc=NULL B. p->ltag=1
C. p->ltag=1 且p->lc=NULL D. 以上都不对
18. 设n , m 为一棵二叉树上的两个结点，在中序遍历序列中n在m前的条件是（ ）。
A. n在m右方 B. n在m 左方
C. n是m的祖先 D. n是m的子孙
19. 如果F是由有序树T转换而来的二叉树，那么T中结点的前序就是F中结点的（ ）。
A. 中序 B. 前序 C. 后序 D. 层次序
20. 欲实现任意二叉树的后序遍历的非递归算法而不必使用栈，最佳方案是二叉树采用（ ）存储结构。
A. 三叉链表 B. 广义表 C. 二叉链表 D. 顺序
21. 下面叙述正确的是（ ）。
A. 二叉树是特殊的树
B. 二叉树等价于度为2的树
C. 完全二叉树必为满二叉树
D. 二叉树的左右子树有次序之分
22. 任何一棵二叉树的叶子结点在先序、中序和后序遍历序列中的相对次序（ ）。
A. 不发生改变 B. 发生改变
C. 不能确定 D. 以上都不对
二、填空题
1. 计算机软件系统中，有两种处理字符串长度的方法：一种是___________，第二种是___________________。
2. 两个字符串相等的充要条件是_____________________和___________________。
3. 设字符串S1= “ABCDEF”，S2= “PQRS”，则运算S=CONCAT（SUB（S1，2，LEN（S2）），SUB（S1，LEN（S2），2））后的串值为___________________。
4. 串是指___________________。
5. 空串是指___________________，空格串是指___________________。
6. 假定一棵树的广义表表示为A（B（E），C（F（H，I，J），G），D），则该树的度为_____，树的深度为_____，终端结点的个数为______，单分支结点的个数为______，双分支结点的个数为______，三分支结点的个数为_______，C结点的双亲结点为_______，其孩子结点为_______和_______结点。
7. 设F是一个森林，B是由F转换得到的二叉树，F中有n个非终端结点，则B中右指针域为空的结点有_______个。
8. 对于一个有n个结点的二叉树，当它为一棵________二叉树时具有最小高度，即为_______，当它为一棵单支树具有_______高度，即为_______。
9. 由带权为3，9，6，2，5的5个叶子结点构成一棵哈夫曼树，则带权路径长度为___。
10. 在一棵二叉排序树上按_______遍历得到的结点序列是一个有序序列。
11. 对于一棵具有n个结点的二叉树，当进行链接存储时，其二叉链表中的指针域的总数为_______个，其中_______个用于链接孩子结点，_______个空闲着。
12. 在一棵二叉树中，度为0的结点个数为n0，度为2的结点个数为n2，则n0=______。
13. 一棵深度为k的满二叉树的结点总数为_______，一棵深度为k的完全二叉树的结点总数的最小值为_____，最大值为______。
14. 由三个结点构成的二叉树，共有____种不同的形态。
15. 设高度为h的二叉树中只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为____。
16. 一棵含有n个结点的k叉树，______形态达到最大深度，____形态达到最小深度。
三、算法设计题
1. 设有一个长度为s的字符串，其字符顺序存放在一个一维数组的第1至第s个单元中（每个单元存放一个字符）。现要求从此串的第m个字符以后删除长度为t的子串，m
解：1、算法描述为：
int delete(r,s,t,m) //从串的第m个字符以后删除长度为t的子串
char r[ ];
int s,t,m;
{ int i,j;
for(i=1;i<=m;i++)
r[s+i]=r[i];
for(j=m+t-i;j<=s;j++)
r[s-t+j]=r[j];
return (1);
} //delete
2、算法思想为：
（1）链表s中取出一个字符；将该字符与单链表t中的字符依次比较；
（2）当t中有与从s中取出的这个字符相等的字符，则从t中取下一个字符重复以上比较；
（3）当t中没有与从s中取出的这个字符相等的字符，则算法结束。
设单链表类型为LinkList；注意，此时类型 LinkList中的data成分为字符类型。
LinkString find(s,t)
LinkString *s, *t;
{ LinkString *ps, *pt;
ps=s;
while(ps!=NULL)
{ pt=t;
while((pt!=NULL)&&(ps->data!=pt->data))
pt=pt->next;
if(pt= =NULL)
ps=NULL;
else
{ ps=ps->next;
s=ps;
}
}
return s;
} //find
一、单项选择题
1. 空串与空格字符组成的串的区别在于（ ）。
A.没有区别 B.两串的长度不相等
C.两串的长度相等 D.两串包含的字符不相同
2. 一个子串在包含它的主串中的位置是指（ ）。
A.子串的最后那个字符在主串中的位置
B.子串的最后那个字符在主串中首次出现的位置
C.子串的第一个字符在主串中的位置
D.子串的第一个字符在主串中首次出现的位置
3. 下面的说法中，只有（ ）是正确的。
A.字符串的长度是指串中包含的字母的个数
B.字符串的长度是指串中包含的不同字符的个数
C.若T包含在S中，则T一定是S的一个子串
D.一个字符串不能说是其自身的一个子串
4. 两个字符串相等的条件是（ ）。
A.两串的长度相等
B.两串包含的字符相同
C.两串的长度相等，并且两串包含的字符相同
D.两串的长度相等，并且对应位置上的字符相同
5. 若SUBSTR（S，i，k）表示求S中从第i个字符开始的连续k个字符组成的子串的操作，则对于S=“Beijing＆Nanjing”，SUBSTR（S，4，5）=（ ）。
A. “ijing” B. “jing＆”
C. “ingNa” D. “ing＆N”
6. 若INDEX（S，T）表示求T在S中的位置的操作，则对于S=“Beijing＆Nanjing”，T=“jing”，INDEX（S，T）=（ ）。
A.2 B.3 C.4 D.5
7. 若REPLACE（S，S1，S2）表示用字符串S2替换字符串S中的子串S1的操作，则对于S=“Beijing＆Nanjing”，S1=“Beijing”，S2=“Shanghai”，REPLACE（S，S1，S2）=（ ）。
A. “Nanjing＆Shanghai” B. “Nanjing＆Nanjing”
C. “ShanghaiNanjing” D. “Shanghai＆Nanjing”
8. 在长度为n的字符串S的第i个位置插入另外一个字符串，i的合法值应该是（ ）。
A.i＞0 B. i≤n
C.1≤i≤n D.1≤i≤n+1
9. 字符串采用结点大小为1的链表作为其存储结构，是指（ ）。
A.链表的长度为1
B.链表中只存放1个字符
C.链表的每个链结点的数据域中不仅只存放了一个字符
D.链表的每个链结点的数据域中只存放了一个字符
10. 在一棵度为3的树中，度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数为（ ）个。
A. 4 B. 5 C. 6 D. 7
11. 假设在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子结点数为（ ）个。
A. 15 B. 16 C. 17 D. 47
12. 假定一棵三叉树的结点数为50，则它的最小高度为（ ）。
A. 3 B. 4 C. 5 D. 6
13. 在一棵二叉树上第4层的结点数最多为（ ）。
A. 2 B. 4 C. 6 D. 8
14. 用顺序存储的方法将完全二叉树中的所有结点逐层存放在数组中R[1..n]，结点R[i]若有左孩子，其左孩子的编号为结点（ ）。
A. R[2i+1] B. R[2i] C. R[i/2] D. R[2i-1]
15. 由权值分别为3,8,6,2,5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（ ）。
A. 24 B. 48 C. 72 D. 53
16. 线索二叉树是一种（ ）结构。
A. 逻辑 B. 逻辑和存储 C. 物理 D. 线性
17. 线索二叉树中，结点p没有左子树的充要条件是（ ）。
A. p->lc=NULL B. p->ltag=1
C. p->ltag=1 且p->lc=NULL D. 以上都不对
18. 设n , m 为一棵二叉树上的两个结点，在中序遍历序列中n在m前的条件是（ ）。
A. n在m右方 B. n在m 左方
C. n是m的祖先 D. n是m的子孙
19. 如果F是由有序树T转换而来的二叉树，那么T中结点的前序就是F中结点的（ ）。
A. 中序 B. 前序 C. 后序 D. 层次序
20. 欲实现任意二叉树的后序遍历的非递归算法而不必使用栈，最佳方案是二叉树采用（ ）存储结构。
A. 三叉链表 B. 广义表 C. 二叉链表 D. 顺序
21. 下面叙述正确的是（ ）。
A. 二叉树是特殊的树
B. 二叉树等价于度为2的树
C. 完全二叉树必为满二叉树
D. 二叉树的左右子树有次序之分
22. 任何一棵二叉树的叶子结点在先序、中序和后序遍历序列中的相对次序（ ）。
A. 不发生改变 B. 发生改变
C. 不能确定 D. 以上都不对
二、填空题
1. 计算机软件系统中，有两种处理字符串长度的方法：一种是___________，第二种是___________________。
2. 两个字符串相等的充要条件是_____________________和___________________。
3. 设字符串S1= “ABCDEF”，S2= “PQRS”，则运算S=CONCAT（SUB（S1，2，LEN（S2）），SUB（S1，LEN（S2），2））后的串值为___________________。
4. 串是指___________________。
5. 空串是指___________________，空格串是指___________________。
6. 假定一棵树的广义表表示为A（B（E），C（F（H，I，J），G），D），则该树的度为_____，树的深度为_____，终端结点的个数为______，单分支结点的个数为______，双分支结点的个数为______，三分支结点的个数为_______，C结点的双亲结点为_______，其孩子结点为_______和_______结点。
7. 设F是一个森林，B是由F转换得到的二叉树，F中有n个非终端结点，则B中右指针域为空的结点有_______个。
8. 对于一个有n个结点的二叉树，当它为一棵________二叉树时具有最小高度，即为_______，当它为一棵单支树具有_______高度，即为_______。
9. 由带权为3，9，6，2，5的5个叶子结点构成一棵哈夫曼树，则带权路径长度为___。
10. 在一棵二叉排序树上按_______遍历得到的结点序列是一个有序序列。
11. 对于一棵具有n个结点的二叉树，当进行链接存储时，其二叉链表中的指针域的总数为_______个，其中_______个用于链接孩子结点，_______个空闲着。
12. 在一棵二叉树中，度为0的结点个数为n0，度为2的结点个数为n2，则n0=______。
13. 一棵深度为k的满二叉树的结点总数为_______，一棵深度为k的完全二叉树的结点总数的最小值为_____，最大值为______。
14. 由三个结点构成的二叉树，共有____种不同的形态。
15. 设高度为h的二叉树中只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为____。
16. 一棵含有n个结点的k叉树，______形态达到最大深度，____形态达到最小深度。
三、算法设计题
1. 设有一个长度为s的字符串，其字符顺序存放在一个一维数组的第1至第s个单元中（每个单元存放一个字符）。现要求从此串的第m个字符以后删除长度为t的子串，m
解：1、算法描述为：
int delete(r,s,t,m) //从串的第m个字符以后删除长度为t的子串
char r[ ];
int s,t,m;
{ int i,j;
for(i=1;i<=m;i++)
r[s+i]=r[i];
for(j=m+t-i;j<=s;j++)
r[s-t+j]=r[j];
return (1);
} //delete
2、算法思想为：
（1）链表s中取出一个字符；将该字符与单链表t中的字符依次比较；
（2）当t中有与从s中取出的这个字符相等的字符，则从t中取下一个字符重复以上比较；
（3）当t中没有与从s中取出的这个字符相等的字符，则算法结束。
设单链表类型为LinkList；注意，此时类型 LinkList中的data成分为字符类型。
LinkString find(s,t)
LinkString *s, *t;
{ LinkString *ps, *pt;
ps=s;
while(ps!=NULL)
{ pt=t;
while((pt!=NULL)&&(ps->data!=pt->data))
pt=pt->next;
if(pt= =NULL)
ps=NULL;
else
{ ps=ps->next;
s=ps;
}
}
return s;
} //find
版权声明
声明：有的资源均来自网络转载，版权归原作者所有，如有侵犯到您的权益
请联系本站我们将配合处理！
上一篇 : 《护理学导论模拟试题一》20年春山东大学参考答案