实用标准文档
《数据结构》习题汇编
一、单项选择题
1. 在数据结构中，从逻辑上可以把数据结构分成（ ）。
A. 动态结构和静态结构 C. 线性结构和非线性结构
B. 紧凑结构和非紧凑结构 D. 内部结构和外部结构
2. 数据结构在计算机内存中的表示是指（ ）。
A. 数据的存储结构 C. 数据的逻辑结构
B. 数据结构
D. 数据元素之间的关系
3. 在数据结构中，与所使用的计算机无关的是数据的（ ）结构。
A. 逻辑
B. 存储
C. 逻辑和存储
D. 物理
4. 计算机算法指的是（ ① ），它必须具备输入、输出和（ ② ）等5个特性。
①A. 计算方法
B. 排序方法 D. 调度方法
B. 可行性、确定性和有穷性 D. 易读性、稳定性和安全性
C. 解决问题的有限运算序列 C. 确定性、有穷性和稳定性
②A. 可行性、可移植性和可扩充性
5. 在一个长度为n的顺序表中向第i个元素（1≤i≤n+1）位置插入一个新元素时，需要从后向前依次后
移（ ）个元素。
A. n-i
B. n-i+1
C. n-i-1
D. i
6. 在一个长度为n的顺序表中删除第i个元素（1≤i≤n）时，需要从前向后依次前移（ ）个元素。
A. n-i
B. n-i+1
C. n-i-1
D. i
7. 在一个长度为n的顺序表的表尾插入一个新元素的渐进时间复杂度为（ ）。
A. O(n)
B. O(1)
C. O(n)
2
D. O(log2n)
8. 在一个长度为n的顺序表的任一位置插入一个新元素的渐进时间复杂度为（ ）。
A. O(n)
B. O(n/2)
C. O(1)
D. O(n)
2
9. 不带头结点的单链表first为空的判定条件是：（ ）
A. first == NULL;
B. first->next == NULL; D. first != NULL;
C. first->next == first;
10. 带头结点的单链表first为空的判定条件是：（ ）
A. first == NULL;
B. first->next == NULL; D. first != NULL;
C. first->next == first;
11. 设单链表中结点的结构为（data, next）。已知指针p所指结点不是尾结点，若在*p之后插入结点*s，
则应执行下列哪一个操作？（ ）
A. s->next = p; p->next = s; C. s->next = p->next; p = s;
文案大全
B. p->next = s; s->next = p; D. s->next = p->next; p->next = s;
实用标准文档
12. 设单链表中结点的结构为（data, next）。若想摘除结点*p(*p既不是第一个也不是最后一个结点)的直
接后继，则应执行下列哪一个操作？（ ）
A. p->next = p->next->next; C. p->next = p->next;
B. p = p->next; p->next = p->next->next; D. p = p->next->next;
13. 非空的循环单链表first的尾结点（由p所指向）满足：（ ）
A. p->next == NULL;
B. p == NULL;
C. p->next == first;
D. p == first;
14. 若让元素1,2,3依次进栈，则出栈次序不可能出现（ ）种情况。
A. 3, 2, 1
B. 2, 1, 3
C. 3, 1, 2
D. 1, 3, 2
15. 当利用大小为n的数组顺序存储一个队列时，该队列的最大长度为（ ）。
A. n-2
B. n-1
C. n
D. n+1
16. 从一个顺序存储的循环队列中删除一个元素时，需要（ ）。
A. 队头指针加一
B. 队头指针减一
D. 取出队尾指针所指的元素
C. 取出队头指针所指的元素
17. 假定一个顺序存储的循环队列的队头和队尾指针分别为front和rear，则判断队空的条件为（ ）。
A. front+1 == rear C. front == 0
B. rear+1 == front D. front == rear
18. 树中所有结点的度等于所有结点数加（ ）。
A. 0
B. 1
C. -1
D. 2
19. 在一棵二叉树的二叉链表中，空指针域数等于非空指针域数加（ ）。
A. 2
B. 1
C. 0
D. -1
20. 在一棵具有n个结点的二叉树中，所有结点的空子树个数等于（ ）。
A. n
B. n-1
C. n+1
D. 2*n
21. 在一棵具有n个结点的二叉树的第i层上（假定根结点为第1层，i大于等于1而小于等于树的高度），
最多具有（ ）个结点。
A. 2
i
B. 2
i+1
C. 2
i-1
D. 2
n
22. 在一棵高度为h（假定根结点的层号为1）的完全二叉树中，所含结点个数不小于（ ）。
A. 2
h-1
B. 2
h+1
C. 2-1
h
D. 2
h
23. 在一棵具有35个结点的完全二叉树中，该树的高度为（ ）。假定空树的高度为0。
A. 5
B. 6
C. 7
D. 8
24. 在一棵具有n个结点的完全二叉树中，分支结点的最大编号为（ ）。假定树根结点的编号为1。
A. ?(n-1)/2?
文案大全
B. ?n/2? C. ?n/2? D. ?n/2? -1
实用标准文档
25. 在一棵完全二叉树中，若编号为i的结点存在左孩子，则左子女结点的编号为（ ）。假定根结点
的编号为1
A. 2i
B. 2i-1
C. 2i+1
D. 2i+2
26. 在一棵完全二叉树中，假定根结点的编号为1，则对于编号为i（i＞1）的结点，其双亲结点的编号为
（ ）。
A. ?(i+1)/2?
B. ?(i-1)/2?
C. ?i/2?
D. ?i/2? -1
27. 设无向图的顶点个数为n，则该图最多有（ ）条边。
A. n-1
B. n(n-1)/2
C. n(n+1)/2
D. n(n-1)
28. n个顶点的连通图至少有（ ）条边。
A. n-1
B. n
C. n+1
D. 0
29. 在一个无向图中，所有顶点的度数之和等于所有边数的 ( ) 倍。
A. 3
B. 2
C. 1
D. 1/2
30. 图的深度优先搜索类似于树的（ ）次序遍历。 A. 先根 B. 中根 C. 后根
31. 图的广度优先搜索类似于树的（ ）次序遍历。
A. 先根
B. 中根
C. 后根
D. 层次
D. 层次
32. n (n＞1) 个顶点的强连通图中至少含有（ ）条有向边。
A. n-1
B. n
C. n(n-1)/2
D. n(n-1)
33. 具有n个顶点的有向无环图最多可包含（ ）条有向边。
A. n-1
B. n
C. n(n-1)/2 D.n(n-1)
34. 一个有n个顶点和n条边的无向图一定是（ ）。
A. 连通的
B. 不连通的
C. 无环的
D. 有环的
35. 在n个顶点的有向无环图的邻接矩阵中至少有（ ）个零元素。
A. n
B. n(n-1)/2 C. n(n+1)/2
D. n(n-1)
36. 为了实现图的广度优先遍历，BFS算法使用的一个辅助数据结构是（ ）。
A. 栈
B. 队列
C. 二叉树
D. 树
37. 若搜索每一个元素的概率相等，则在长度为n的顺序表上搜索到表中任一元素的平均搜索长度为
（ ）。
A. n
B. n+1
C. (n-1)/2
D. (n+1)/2
38. 对长度为10的顺序表进行搜索(从表头开始搜索)，若搜索前面5个元素的概率相同，均为1/8，搜索后
面5个元素的概率相同，均为3/40，则搜索到表中任一元素的平均搜索长度为（ ）。
A. 5.5
文案大全
B. 5 C. 39/8 D. 19/4