一、单选题（共 25 道试题，共 50 分。）
V
1. 已知广义表L=（（x,y,z），a，（u，t，w）），从L表中取出原子项t的运算是（ ）。
A. head（tail（tail（L）））
B. tail（head（head（tail（L））））
C. head（tail（head（tail（L））））
D. head（tail(head（tail（tail（L）））)）
满分：2 分
2. 下列排序算法中，占用辅助空间最多的是：( )
A. 归并排序
B. 快速排序
C. 希尔排序
D. 堆排序
满分：2 分
3. 由3 个结点可以构造出多少种不同的二叉树（ ）
A. 2
B. 3
C. 4
D. 5
满分：2 分
4. 具有12个关键字的有序表，折半查找的平均查找长度（ ）
A. 3.1
B. 4
C. 2.5
D. 5
满分：2 分
5. 数组A[0..4,-1..-3,5..7]中含有元素的个数（ ）。
A. 55
B. 45
C. 36
D. 16
满分：2 分
6. 设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（ ）
A. 13
B. 33
C. 18
D. 40
满分：2 分
7. 树的后根遍历序列等同于该树对应的二叉树的（ ）
A. 先序序列
B. 中序序列
C. 后序序列
D. 都不正确
满分：2 分
8. 下面的程序段中，对x的赋值语句的频度为（ ）FOR i:=1 TO n DOFOR j:=1 TO n DO x:=x+1;
A. O(2n)
B. O(n)
C. O(n2)
D. O(log2n)
满分：2 分
9. 对关键码序列28，16，32，12，60，2，5，72快速排序，从小到大一次划分结果为（ ）
A. (2,5,12,16)26(60,32,72)
B. (5,16,2,12)28(60,32,72)
C. (2,16,12,5)28(60,32,72)
D. (5,16,2,12)28(32,60,72)
满分：2 分
10. 从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为（ ）排序法。
A. 插入
B. 选择
C. 希尔
D. 二路归并
满分：2 分
11. 若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度（ ）(1<=i<=n+1)。
A. O(0)
B. O(1)
C. O(n)
D. O(n2)
满分：2 分
12. 广义表A=(a,b,(c,d),(e,(f,g))),则下面式子的值为（ ）。 Head(Tail(Head(Tail(Tail(A)))))
A. （a）
B. A
C. a
D. d
满分：2 分
13. 要连通具有n个顶点的有向图，至少需要（ ）条边。
A. n-l
B. n
C. n+l
D. 2n
满分：2 分
14. 字符串‘ababaabab’ 的nextval 为（ ）
A. (0,1,0,1,04,1,0,1)
B. (0,1,0,1,0,2,1,0,1)
C. (0,1,0,1,0,0,0,1,1)
D. (0,1,0,1,0,1,0,1,1 )
满分：2 分
15. 已知广义表L=（（x,y,z），a，（u，t，w）），从L表中取出原子项t的运算是（ ）
A. head（tail（tail（L）））
B. tail（head（head（tail（L））））
C. head（tail（head（tail（L））））
D. head（tail(head（tail（tail（L）））)）
满分：2 分
16. 具有10个叶结点的二叉树中有（ ）个度为2的结点，
A. 8
B. 9
C. 10
D. ll
满分：2 分
17. 具有10个叶结点的二叉树中有（ ）个度为2的结点，
A. 8
B. 9
C. 10
D. ll
满分：2 分
18. 对于栈操作数据的原则是（ ）
A. 先进先出
B. 后进先出
C. 后进后出
D. 不分顺序
满分：2 分
19. 就平均性能而言，目前最好的内排序方法是( )排序法。
A. 冒泡
B. 希尔插入
C. 交换
D. 快速
满分：2 分
20. 一棵二叉树的前序遍历序列为ABCDEFG，它的中序遍历序列可能是（ ）
A. CABDEFG
B. ABCDEFG
C. DACEFBG
D. ADCFEG
满分：2 分
21. 设森林F对应的二叉树为B，它有m个结点，B的根为p,p的右子树结点个数为n,森林F中第一棵树的结点个数是（ ）
A. m-n
B. m-n-1
C. n+1
D. 条件不足，无法确定
满分：2 分
22. 有n个叶子的哈夫曼树的结点总数为（ ）。
A. 不确定
B. 2n
C. 2n+1
D. 2n-1
满分：2 分
23. 最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是 （ ）。
A. (rear+1) MOD n=front
B. rear=front
C. rear+1=front
D. (rear-l) MOD n=front
满分：2 分
24. 在下面的排序方法中，辅助空间为O（n）的是（ ）
A. 希尔排序
B. 堆排序
C. 选择排序
D. 归并排序
满分：2 分
25. 若要求排序是稳定的，且关键字为实数，则在下列排序方法中应选（ ）排序为宜。
A. 直接插入
B. 直接选择
C. 堆
D. 快速
| 满分：2 分 |
| 窗体底端 |
| 窗体顶端 二、判断题（共 20 道试题，共 40 分。） V 1. 数据结构的抽象操作的定义与具体实现有关。 A. 错误 B. 正确 满分：2 分 2. 用一维数组存储二叉树时，总是以前序遍历顺序存储结点（ ） A. 错误 B. 正确 满分：2 分 3. 顺序查找法适用于存储结构为顺序或链接存储的线性表。 A. 错误 B. 正确 满分：2 分 4. 折半查找法的查找速度一定比顺序查找法快（ ） A. 错误 B. 正确 满分：2 分 5. 顺序存储结构的主要缺点是不利于插入或删除操作（ ） A. 错误 B. 正确 满分：2 分 6. 线性表的特点是每个元素都有一个前驱和一个后继（ ） A. 错误 B. 正确 满分：2 分 7. 一棵一般树的结点的前序遍历和后序遍历分别与它相应二叉树的结点前序遍历和后序遍历是一致的。 A. 错误 B. 正确 满分：2 分 8. 对一棵二叉树进行层次遍历时，应借助于一个栈 A. 错误 B. 正确 满分：2 分 9. 广义表中的元素或者是一个不可分割的原子，或者是一个非空的广义表。 A. 错误 B. 正确 满分：2 分 10. 队列是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构（ ）。 A. 错误 B. 正确 满分：2 分 11. 若一个广义表的表头为空表，则此广义表亦为空表（ ） A. 错误 B. 正确 满分：2 分 12. 循环链表不是线性表（ ） A. 错误 B. 正确 满分：2 分 13. 数据的逻辑结构说明数据元素之间的顺序关系,它依赖于计算机的储存结构. A. 错误 B. 正确 满分：2 分 14. 在顺序存储结构中，有时也存储数据结构中元素之间的关系。 A. 错误 B. 正确 满分：2 分 15. 在查找树（二叉树排序树）中插入一个新结点，总是插入到叶结点下面。 A. 错误 B. 正确 满分：2 分 16. 二维以上的数组其实是一种特殊的广义表。 A. 错误 B. 正确 满分：2 分 17. 二叉树是度为2的有序树 A. 错误 B. 正确 满分：2 分 18. 查找相同结点的效率折半查找总比顺序查找高 A. 错误 B. 正确 满分：2 分 19. 循环队列也存在空间溢出问题。 A. 错误 B. 正确 满分：2 分 20. 循环链表不是线性表. A. 错误 B. 正确 满分：2 分 |
| 窗体底端 |
| 窗体顶端 三、多选题（共 5 道试题，共 10 分。） V 1. 下列关于m阶B-树的说法正确的是( ) A. 根结点至多有m棵子树 B. 所有叶子都在同一层次上 C. 非叶结点至少有m/2 (m为偶数)或m/2+1（m为奇数）棵子树 D. 根结点中的数据是有序的 满分：2 分 2. 下面说法正确的是( )。 A. 广义表的表头总是一个广义表 B. 广义表的表尾总是一个广义表 C. 广义表难以用顺序存储结构 D. 广义表可以是一个多层次的结构 满分：2 分 3. 下面关于串的的叙述中，正确的是（ ） A. 串是字符的有限序列 B. 空串是由空格构成的串 C. 模式匹配是串的一种重要运算 D. 串既可以采用顺序存储，也可以采用链式存储 满分：2 分 4. 某堆栈的输入序列为a, b，c ，d,下面的四个序列中，可能是它的输出序列的是（ ） A. a，c，b，d B. b, c，d，a C. c, d，b, a D. d, c，a，b 满分：2 分 5. 下面关于二分查找的叙述不正确的是（ ） A. 表必须有序，表可以顺序方式存储，也可以链表方式存储 B. 表必须有序，而且只能从小到大排列 C. 表必须有序且表中数据必须是整型，实型或字符型 D. 表必须有序，且表只能以顺序方式存储 满分：2 分 |
| 窗体底端 |
Copyright © 2019-2025 51dongshi.net 版权所有
违法及侵权请联系：TEL:177 7030 7066 E-MAIL:11247931@qq.com 本站由北京市万商天勤律师事务所王兴未律师提供法律服务
