计算机科学与工程系《数据结构》精品课程题库
（选择题）
1. 在一棵度为3的树中，度为3的结点个数为2，度为2 的结点个数为1，则度为0的结点个数为 ( )
A.4 B.5
C.6 D.7
2. 一棵左右子树均不空的二叉树在先序线索化后，其空指针域数为 ( )
A.0 B.1
C.2 D.不确定
3. 二叉树在线索化后，仍不能有效求解的问题是 ( )
A.先序线索二叉树中求先序后继 B.中序线索二叉树中求中序后继
C.中序线索二叉树中求中序前趋 D.后序线索二叉树中求后序后继
4. 有64个结点的完全二叉树的深度为__(根的层次为1)( )
A.8 B.7
C.6 D.5
5. 在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A，并已知A的左孩子的平衡因子为-1，右孩子的平衡因子为0，则应作__ 型调整以使其平衡( )
A. LL B. LR
C. RL D. RR
6. 一棵含18个结点的二叉树的高度至少为( )
A.3 B.4
C.5 D.6
7. 已知二叉树的先序序列为ABDECF，中序序列为DBEAFC，则后序序列为( )
A.DEBAFC B.DEFBCA
C.DEBCFA D.DEBFCA
8. 二叉树中第5层上的结点个数最多为( )
A.8 B.15
C.16 D.32
9. 在具有n个叶子结点的严格二叉树中，结点总数为( )
A.2n+1 B.2n-1
C.2n D.2N-2
10. 当在二叉排序树中插入一个新结点时，若树中不存在与待插入结点的关键字相同的结点，且新结点的关键字小于根结点的关键字，则新结点将成为( )
A．左子树的叶子结点 B．左子树的分支结点
C．右子树的叶子结点 D．右子树的分支结点
11. 已知含10个结点的二叉排序树是一棵完全二叉树，则该二叉排序树在等概率情况下查成功的平均查长度等于( )
先序中序后序遍历二叉树A．1.0 B．2.9
C．3.4 D．5.5
12. 假设一棵完全二叉树按层次遍历的顺序依次存放在数组BT[m]中，其中根结点存放在BT[0]，若BT[i]中的结点有左孩子，则左孩子存放在 ( )
A.BT[i/2] B.BT[2*i-1]
B.BT[2*i] D.BT[2*i+1]
13. 由同一关键字集合构造的各棵二叉排序树( )
A. 其形态不一定相同，但平均查长度相同
B. 其形态不一定相同，平均查长度也不一定相同
C. 其形态均相同，但平均查长度不一定相同
D. 其形态均相同，平均查长度也都相同
14. 除第一层外，满二叉树中每一层结点个数是上一层结点个数的( )
A．1/2倍 B．1倍
C．2倍 D．3倍
15. 下列陈述中正确的是( )
A.二叉树是度为2的有序树 B.二叉树中结点只有一个孩子时无左右之分
C.二叉树中必有度为2的结点 D.二叉树中最多只有两棵子树，并且有左右之分
16. ALV树是一种平衡的二叉排序树，树中任一
结点的( )
A.左、右子树的高度均相同 B.左、右子树高度差的绝对值不超过1
C.左子树的高度均大于右子树的高度 D.左子树的高度均小于右子树的高度
17. 在线索化二叉树中，t所指结点没有左子树的充要条件是( )
A.t->left==NULL B.t->ltag==1
C.t->ltag==1且t->left==NULL D.以上都不对
18. 已知某二叉树的后序遍历是dabec，中序遍历序列是debac，它的前序遍历序列是 ( )
A.acbed B.decab
C.deabc D.cedba
19. 如果T2是有序树T转换而来的二叉树，那么T中结点的前序就是T2中结点的( )
A.前序 B.中序
C.后序 D.层次序
20. 如果T2是有序树T转换而来的二叉树，那么T中结点的后序就是T2中结点的( )
A.前序 B.中序
C.后序 D.层次序
21. 某二叉树的前序遍历结点的访问顺序是abdgcefh，中序遍历的结点访问顺序是dghaechf，则其后序遍历的结点访问顺序是( )
A.bdgcefha B.gdbecfha
C.bdgaechf D.gdbehfca
22. 按照二叉树的定义，具有3个结点的二叉树有__种( )
A.3 B.4
C.5 D.6
23. 深度为5的二叉树至多有__个结点( )
A.16 B.32
C.31 D.10
24. 在以非空二叉树的中序遍历中，跟结点的右边( )
A.只有右子树上的所有结点 B.只有右子树上的部分结点
C.只有左子树上的所有结点 D.只有左子树上的部分结点
25. 树最适合用来表示( )
A.有序数据元素 B.无序数据元素
C.元素之间具有分层次关系的数据 D.元素之间无联系的数据
26. 任何一颗二叉树的叶结点在先序，中序和后序遍历中的相对次序( )
A.不发生改变 B.发生改变
C.不能确定 D.以上都不对
27. 实现任意二叉树的后序遍历的非递归算法而不使用栈结构，最佳方案是二叉树采用__存储结构( )
A.二叉链表 B.广义表存储结构
C.三叉链表 D.顺序存储结构
28. 对一个满二叉树，M个树叶,N个结点，深度为H，则( )
A.N=H+M B.H+M=2H
C.M=H-1 D.N=2*eh-1
29. 如果某二叉树的前序为stuwv，中序为uwtvs，那么该二叉树的后序中( )
A.uwvts A.uwvst
C.wuvts D.wutsv
30. 具有五层结点的二叉平衡树至少__个结点( )
A.10 A.12
C.15 D.17
31. 设N,M唯一可二叉树上的两个结点，在中序遍历时，N在M前的条件是( )
A.N在M右方 B.N是M祖先
C.N在M左方 D.N是M子孙
32. 线索二叉树是一种__结构( )
A.逻辑 B.逻辑和存储
C.物理 D.线性
33. l 将一棵有 100个结点的完全二叉树，从根这一层开始，每一层从左到右依次对结点编号，根据点的 编号为1，则编号为49的结点的双亲的编号为 ( )
A.24
B .25
C.30 D无法确定
34. 深度为６（根据的层次为１）的二叉树至多有__结点( )
Ａ .６４ Ｂ.６３
Ｄ.３１ Ｄ.３２
35. 设二叉树有 n个结点，则其深度为( )
Ａ .n-1 B. n
C .㏒2n D. 无法确定
36. 设森林Ｔ中有三棵树，第一、第二、 三棵数的活结点个数分别为n1 n2 n3 ，那么将森林转换成二叉树后，其根结点的右子树上有__个结点( )
Ａ .n1-1 B.n2+n3
C .n1 +n2+n3 D.n1
37. 设森林Ｔ中有三棵树，第一 二 三棵数的结点个数分别为 n1 n2 n3，那么将森林转换成二叉树后，其根结点的左子树上有__个结点( )
Ａ .n1-1 Ｂ.n2+n3
Ｃ.n1+n2+n3 Ｄ.n1
38. 设深度为Ｋ的二叉树上只有度为０或度为２的结点，则这类二叉树上所含结点总数至少 ( )
Ａ .Ｋ＋１ Ｂ.２Ｋ
Ｃ２Ｋ—１ Ｄ２Ｋ＋１
39. 树转换成二叉树后，以下结论正确的是( )
Ａ .树的先根遍历序列与其对应的二叉树的先序遍历序列相同
Ｂ.树的先根遍历序列与其对应的二叉树的中序遍历序列相同
Ｃ.树的后根遍历序列与其对应的二叉树的后序遍历序列相同
Ｄ.以上都不对
40. 某二叉树的前序遍历结点访问顺序为， ABDGCDFH中序遍历结点访问顺序为DGBAECHE，则其后续遍历结点访问顺序为 ( )
A. BDGCEFHA B. GDBECFHA
C. BDGAECHF D. GDBDHFCA
41. 在一棵非空二叉树的中序遍历序列中，根结点的右边 ( )
A.只有右子树上的所有结点 B. 只有右子树砂锅内的部分结点
C.只有左子树上的所有结点 D.只有左子树上的部分结点
42. 任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序( )
A.不发生变化 B. 发上变化
C.不能确定 D.以上都不对
43. 给出不同的输入序列建造二叉排序树，一定得到不同的二叉排序树。( )
A.对 B.错
C.不能确定 D.以上都不对
44. 二叉树中的叶子结点就是二叉树中没有左右子树的结点。( )
A.对 B.错
C.不能确定 D.以上都不对
45. 一棵树中的叶子结点数一定等于与其对应的二叉树中的叶子结点数。( )
A.对 B.错
C.不能确定 D.以上都不对
46. 长度为12的按关键字有序的查表采用顺序组织方式，若用二分查方法，则在等概率情况下，查不成功的平均查长度是( )
A）49/13 B）63/13
C）37/12 D）39/12
47. 散列查是由键值（）确定散列表中的位置来进行存储个查( )
A）本身 B）散列函数值
C）相反数 D）平方
48. 在m阶B-树中插入一个关键字时
，
首先在最低层的某个非终端结点添加一个关键字，若该点的关键字数目不超过（），则插入完成。( )
A）[m/2]-1 B）[m/2]+1
C）m-1 D）m+1
49. 采用二分查方法查长度为n的线性表时，每个元素的平均查长度为( )
A）O(n2) B）O(nlog2n)
C）O(n) D）O(log2n)
50. 采用顺序查方法查长度为n的线性表时，每个元素的平均查长度为( )
A）n B）n/2
C）(n+1)/2 D）(n-1)/2
51. 通常把查过场中对关键字需要执行的（ ）作为衡量一个查算法效率优劣大标准( )
A）BST B）WPL
C）ASL D）BFS
52. 在表长是N的顺序表中，实施顺序查，在查不成功时，与关键字比较的次数( )
A）N B）1
C）N+1 D）N-1
53. 如果要求一个线性表既能较快的查，又能适应动态变化的要求，则可采用（ ）查方法( )
A）顺序 B）折半
C）分块 D）基于属性
54. 线性表必须是（ ），才能进行二分查( )
A）用向量存储的线性表 B）用向量存储的有序表
C）用链表存储的线性表 D）用链表存储的有序表
55. 用二分法在有序表{3，4，10，13，33，42，46，63，76，78，95，96，120}中查95时，要进行比较的次数为( )
A）2 B）3
C）4 D）5
56. 设有100个元素，用折半查法进行查时，最小比较次数是( )
A）1 B）2
C）3 D）6
57. 下列（ ）不是利用查表中数据元素的关系进行查的方法( )
A）平衡二叉树 B）有序表的查
C）散列查 D）二叉排序树的查
58. 有一个有序表为{1，3，9，12，32，41，45，62，75，77，82，95，100}，当二分查值为82的结点时，（ ）次比较后查成功( )
A）2 B）4
C）8 D）16
59. 二分查要求结点( )
A）有序、链接存储 B）有序、顺序存储
C）无序、链接存储 D）无序、顺序存储
60. 顺序查法适用于存储结构为（ ）的线性表( )
A）散列存储 B）压缩存储
C）索引存储 D）顺序存储或链接存储
61. m阶B-树中所有非终端（除根之外）结点中的关键字个数必须大于或等于( )
A）[m/2]+1 B）[m/2]-1
C）[m/2] D）m
62. 在查过程中，若同时还要做增、删工作，这种查则称为( )
A）静态查 B）内查
C）动态查 D）外查
63. 下面关于B树和B+树的叙述中不正确的是( )
A）B树和B+树都是平衡的多分树
B）B树和B+树都是可用于文件的索引结构
C）B树和B+树都能有效的支持顺序检索 D）B树和B+树都能有效的支持随机检索
64. 设矩阵A是一个对称矩阵，为了节省空间，将其下三角部分按行优先存放在一个一维数组B中对下三角矩阵中任一原素aij(i>=j)，在一维数组B中下标K的值是( )
A i(i-1)/2+j-1 B i(i+1)/2+j
C i(i+1)/2+j-1 D i(i+1)/2+j
65. 稀疏矩阵的一般的压缩方法有( )
A 二维数组 B 广意表
C 三元表组 D 一维数组
66. 数组A中，每个元素A的长度为３个字节，行下标i从１到８，列下标j从１到１０，从首地址SA开始连续存放在存储器内，该数组按行存放时，元素A[8][5]的起始地址为( )
A SA+140 B SA+144
C SA+ 222 D SA+ 225
67. 在稀疏矩阵的三元组表表示法中，每个三元组表示( )
A 矩阵中数据元素的行号，列号和值 B 矩阵中非零元素的值
C 矩阵中非零元素的行号和列号 D 矩阵中非零元素的行号，列号和值
68. 数组与一般线性表的区别主要在( )
A 存储方面 B 元素类型一致
C 逻辑结构方面 D 不能进行插入、删除运算。
69. 设二维数组-1][0..n-1]行优先顺序存储在内存中，每个元素占d个字节，则元素A[i][j]的地址为( )
A LOC(A[1][1])+[(i-1)*n+j-1]*d B LOC(A[1][1])+[(i-1)*n+j-1]*d
C LOC(A[1][1])+[(j-1)*n+i-1]*d D LOC(A[1][1])+[(j-1)*n+i-1]*d
70. 已知数组A中，每个元素A[I，J]在存储时要占3个字节，设I从1变化到8，J从1变化到10，分配内存时是从地址SA开始连续按行存储分配的。试问：A[5，8]的起始地址为( )
A．SA+141 B．SA+180
C．SA+222 D．SA+225
71. 一维数组与线性表的区别是( )
A．前者长度固定，后者长度可变 B．后者者长度不变前者长度可变
C．两者长度均固定 D．两者长度均可变
72. ．空串与空格字符组成的串的区别在于（. ）( )
A.没有区别 B.两串的长度不相等
C.两串的长度相等 D.两串包含的字符不相同
73. 一个子串在包含它的主串中的位置是指（ ）( )
A． 子串的最后那个字符在主串中的位置
B． 子串的最后那个字符在主串中首次出现的位置
C.子串的第一个字符在主串中的位置
D.子串的第一个字符在主串中首次出现的位置
74. 下面的说法中，只有（ ）是真确的( )
A. 字符串的长度是指串中包含的字母的个数
B. 字符串的长度是指串中包含的不同字符的个数
C. 若T包含在S中，则T一定是S的一个子串
D. 一个字符串不能说是其自身的一个
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论