没有合适的资源?快使用搜索试试~ 我知道了~
数据结构期末复习习题,包含各种题型,方便学生更好地复习已获得更好的分数
资源推荐
资源详情
资源评论
《数据结构》期末复习题
一、单选题
1.某程序的时间复杂度为(3n+nlog
2
n+n
2
+8), 其数量级表示为( )。
A.O(n) B.O(nlog
2
n)
C.O(n
2
) D.O(log
2
n)
2.队列的插入操作是在( )进行。
A.队首 B.队尾
C.队前 D.对后
3.二叉树上叶结点数等于( )。
A.分支结点数加 1 B.单分支结点数加 1
C.双分支结点数加 1 D.双分支结点数 减 1
4.每次从无序表中取出一个元素,把它插入到有序表中的适当位置,此种排序方法叫做(
)排序
A.插入 B.交换
C.选择 D.归并
5.在一个图中,所有顶点的度数之和等于所有边数的( )倍。
A.2 B.1
C.3 D.4
6.队列的删除操作是在( )进行。
A.队首 B.队尾
C.队前 D.对后
7.当利用大小为 N 的数组顺序存储一个栈时,假定用 top = = N 表示栈空,则退栈时,用
( )语句修改 top 指针。
A.top++; B.top=0;
C.top--; D.top=N;
8.由权值分别为 3,6,7,2,5 的叶子结点生成一棵哈夫曼树,它的带权路径长度为( )。
A.51 B.23
C.53 D.74
9.在一棵二叉树中,第 4 层上的结点数最多为( )。
A.31 B.8
C.15 D.16
10. 向堆中插入一个元素的时间复杂度为( )。
A.O(log
2
n) B.O(n)
C.O(1) D.16 O(nlog
2
n)
11.在一个长度为 n 的顺序存储的线性表中,向第 i 个元素(1≤i≤n+1)之前插入一个新
元素时,需要从后向前依次后移( )个元素。
A.n-i B.n-i+1
C.n-i-1 D.i
12.在线性表的散列存储中,若用 m 表示散列表的长度,n 表示待散列存储的元素的个数,
则装填因子等于( )。
A.n/m B.m/n
C.n/(n+m) D.m/(n+m)
13.从一棵 B_树删除元素的过程中,若最终引起树根结点的合并,则新树高度是( )。
A.原树高度加 1 B.原树高度减 1
C.原树高度 D.不确定
14.在稀疏矩阵的带行指针向量的链接存储中,每个行单链表中的结点都具有相同的(
)。
A.行号 B.列号
C.元素值 D.地址
15.在一个具有 n 个顶点的无向图中,要连通所有顶点则至少需要( )条边。
A.n B.2n
C.n-1 D.n+1
16.某程序的时间复杂度为(10n+nlog
2
n+n
2
), 其数量级表示为( )。
A.O(n) B.O(nlog
2
n)
C.O(n
2
) D.O(log
2
n)
17.在一个长度为 n 的顺序存储的线性表中,向第 i 个元素(1≤i≤n+1)之前插入一个新
元素时,需要从后向前依次后移( )个元素。
A.n-i B.n-i+1
C.n-i-1 D.i
18.在一棵二叉搜索树中,每个分支结点的左子树上所有结点的值一定( )该结点的值。
A.小于 B.大于
C.不小于 D.大于等于
19.对于一棵具有 n 个结点的树,该树中所有结点的度数之和为( )。
A.n-1 B.n
C.n+1 D.2n
20.某程序的时间复杂度为(3n+100×log
2
n+ nlog
2
n), 其数量级表示为( )。
A.O(n) B.O(nlog
2
n)
C.O(100) D.O(log
2
n)
21. 设一组初始记录关键字序列(5,2,6,3,8),以第一个记录关键字 5 为基准进行一
趟快速排序的结果为( )。
A. 2,3,5,8,6 B. 3,2,5,8,6
C.3,2,5,6,8 D. 2,3,6,5,8
22.根据 n 个元素建立一棵二叉搜索树时,其时间复杂度大致为( )。
A.O(n) B.O(log
2
n )
C.O(n
2
) D.O(nlog
2
n)
23. 按照数据逻辑结构的不同,可以将数据结构分成 C 。
A. 动态结构和静态结构 B. 紧凑结构和非紧凑结构
C. 线性结构和非线性结构 D. 内部结构和外部结构
24. 下列关于数据结构的叙述中正确的是 A 。
A. 数组是同类型值的集合
B. 递归算法的程序结构比迭代算法的程序结构更为复杂
C. 树是一种线性的数据结构
D. 用一维数组存储二叉树,总是以先序顺序遍历各结点
25. 在计算机的存储器中表示时,物理地址与逻辑地址相同并且是连续的,称之为 B
A.逻辑结构 B.顺序存储结构
C.链式存储结构 D.以上都不对
26. 以下关于算法特性的描述中, B 是正确的。
(1)算法至少有一个输入和一个输出
(2)算法至少有一个输出但是可以没有输入
(3)算法可以永远运行下去
A. (1) B. (2) C. (3) D. (2)和(3)
27. 对顺序存储的线性表(a
1
,a
2
,…,a
n
)进行插入操作的时间复杂度是 C 。
A.O(n) B. O(n-i) C. (n/2) D. O(n-1)
28. 链表不具有的特点是 A 。
A.可随机访问任一元素 B.插入和删除时不需要移动元素
C.不必事先估计存储空间 D.所需空间与线性表的长度成正比
29.线性链表中各链结点之间的地址 C 。
A.必须连续 B.部分地址必须连续
C.不一定连续 D.连续与否无关
30. 以下关于链式存储结构的叙述中, C 是不正确的。
A.结点除自身信息外还包括指针域,因此存储密度小于顺序存储结构
B.逻辑上相邻的结点物理上不必邻接
C.可以通过计算直接确定第 i 个结点的存储地址
D.插入、删除操作方便,不必移动结点
31. 设依次进入一个栈的元素序列为 d, a, c, b,得不到出栈的元素序列为 D 。
A. dcba B. acdb C. abcd D. cbda
32. 将新元素插入到链式队列中时,新元素只能插入到 B 。
A. 链头 B. 链尾 C. 链中
D. 第 i 个位置,i 大于等于 1,大于等于表长加 1
33. 设栈 S 和队列 Q 的初始状态为空,元素 e1、e2、e3、e4、e5 和 e6 依次通过栈 S,一个
元素出栈后即进入队列 Q,若 6 个元素出队的顺序是 e2、e4、e3、e6、e5、和 e1,则栈 S
容量至少应该是 C 。
A. 6 B. 4 C. 3 D. 2
34.下面 D 是‘abcd321ABCD’的子串。
A. abcd B. 321ab C. ‘abc ABC’ D. ‘21AB’
35.假设 8 行 10 列的二维数组 A[1…8,1…10]分别以行序为主序和以列序为主序顺序存储
时,其首地址相同,那么以行序为主序时元素 a[3,5]的地址与以列序为主序时 C
元素相同。
A. a[7,3] B. a[8,3] C. a[1,4] D. ABC 都不对
36. 数组 A[0…5,0…6]的每个元素占 5 个字节,将其按列优先次序存储在起始地址为 1000
的内存单元中,则元素 A[5,5]的地址为 A 。
A. 1175 B. 1180 C. 1205 D.1210
37.下列广义表中,长度为 3 的广义表为 B 。
A.(a,b,c,( )) B. ((g),(a,b,c,d,f),( )) C. (a,(b,(d))) D. ((( )))
39.若树 T 有 a 个度为 1 的结点,b 个度为 2 的结点,c 个度为 3 的结点,则该树有 D 个叶
结点。
A. 1+2b+3c B. a+2b+3c C.2b+3c D. 1+b+2c
40.若一棵二叉树有 102 片叶子结点,则度二叉树度为 2 的结点数是 B 。
A. 100 B. 101 C. 102 D. 103
41. 在有 n 个叶子结点的霍夫曼树中,其结点总数为: 。
A. n B. 2n C. 2n +1 D. 2n - 1
42.具有 12 个结点的完全二叉树有 B 。
A. 5 个叶子结点 B. 5 个度为 2 的结点
C. 7 个分支结点 D. 2 个度为 1 的结点
43.设结点 x 和 y 是二叉树中的任意两结点,若在先根序列中 x 在 y 之前,而后根序列中 x
在 y 之后,则 x 和 y 的关系是 C 。
A. x 是 y 的左兄弟 B. x 是 y 的右兄弟
C. x 是 y 的祖先 D. x 是 y 的后代
44. 先序遍历序列与中序遍历序列相同的二叉树为 。
A. 根结点无左子树的二叉树 B.根结点无右子树的二叉树
C. 只有根结点的二叉树或非叶子结点只有左子树的二叉树
D. 只有根结点的二叉树或非叶子结点只有右子树的二叉树
45.若二叉树 T 的前序遍历序列和中序遍历序列分别是 bdcaef 和 cdeabf,则其后序遍历序列
为 A 。
A. ceadfb B. feacdb C. eacdfb D. 以上都不对
46.设无向图的顶点个数为 n,则该图最多有 C 条边。
A. n-1 B. n(n-1) C. n(n-1)/2 D. N
47.对于一个有 n 个顶点和 e 条边的无向图,若采用邻接表表示,邻接表中的结点总数是 C
。
A. e/2 B. e C. n+2e D. n+e
48. 无 向 图 G= ( V , E ) , 其 中 V= { a,b,c,d,e,f } ,E= { (a,b),(a,e),(a,c),(b,e),(c,f),(f,d),
(e,d)}。
对该图进行深度优先遍历,下面不能得到的序列是 D 。
A. acfdeb B. aebdfc C. aedfcb D. abecdf
49. 直接插入排序在最好情况下的时间复杂度为 B 。
A. O(log
2
n) B. O(n) C. O(nlog
2
n) D. O(n
2
)
50.对有 n 个记录的表作快速排序,在最坏情况,算法的时间复杂度是 D 。
A. O(n
3
) B. O(n) C. O(nlog
2
n) D. O(n
2
)
30.下面的排序算法中,稳定是 A 。
A. 直接插入排序法 B. 快速排序法
C. 直接选择排序法 D. 堆排序法
51.数据结构是( )
A.一种数据类型
B.数据的存储结构
C.相互之间存在一种或多种特定关系的数据元素的集合
D.一组性质相同的数据元素的集合
剩余20页未读,继续阅读
资源评论
yuan5243
- 粉丝: 0
- 资源: 3
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功