【北京大学】08281006-数据结构-2019秋（资料）
08281006-数据结构-2019秋
分数：100题数：70
总体情况
姓名 开始时间 结束时间 用时(分钟) 得分 得分率 是否通过 考试状态
朱小勇 2019-09-22 16:15:44 2019-09-25 19:26:29 65.07 *** *** *** 考试中
一、选择题(共30题，每题1分，共30分)
1. （第一章）数据的逻辑结构被形式地定义为B=(K,R),其中K是 ______的有限集合。
A. 存储
B. 数据操作
C. 数据元素
D. 操作
E. 逻辑结构
F. 映象
G. 算法
H. 关系
试题编号：1.01.1
试题类型：单选题
标准答案：***
试题难度：一般
试题解析：***
考生答案：C
考生得分：***
是否评分：未评分
评价描述：***
2. （第一章）数据的逻辑结构被形式地定义为B=(K,R),其中R是K上的______的有限集合。
A. 存储
B. 数据操作
C. 数据元素
D. 操作
E. 逻辑结构
F. 映象
G. 算法
H. 关系
试题编号：1.01.2
试题类型：单选题
标准答案：***
试题难度：一般
试题解析：***
考生答案：H
考生得分：***
是否评分：未评分
评价描述：***
3. （第一章）以下关于算法的说法不正确的是______________。
A. 一个算法应包含有限个步骤
B. 算法越简单越好
C. 算法中的所有操作都可以通过已经实现的基本操作运算有限次实现之
D. 算法中的每个步骤都能在有限时间内完成
试题编号：1.02
试题类型：单选题
标准答案：***
试题难度：一般
试题解析：***
考生答案：
考生得分：***
是否评分：未评分
评价描述：***
4. （第一章）设某数据结构的二元组形式表示为A=(D，R)，D={01，02，03，04，05，06，07，08，09}，R={r}，r={<01，02>，<01，03>，<01，04>，<02，05>，<02，06>，<03，07>，<03，08>，<03，09>}，则数据结构A是______________。
A. 线性结构
B. 树型结构
C. 物理结构
D. 图型结构
试题编号：1.03
试题类型：单选题
标准答案：***
试题难度：一般
试题解析：***
考生答案：
考生得分：***
是否评分：未评分
评价描述：***
5.
（第一章）下面程序段的时间复杂度为______
int sum=0;
for(i=0; i<m;i++)
for(j=i;j<n;j++)
s++;
A. O(m+n)
B. O(n*n)
C. O(m*n)
D. O(m*logn)
试题编号：1.04
试题类型：单选题
标准答案：***
试题难度：一般
试题解析：***
考生答案：
考生得分：***
是否评分：未评分
评价描述：***
6. （第二章）下列有关线性表的叙述中，正确的是________。
A. 一个线性表是 n 个数据元素的有限序列
B. 线性表中任何一个元素有且仅有一个直接前驱
C. 线性表中任何一个元素有且仅有一个直接后继
D. 以上说法都不正确
试题编号：1.05
试题类型：单选题
标准答案：***
试题难度：一般
试题解析：***
考生答案：
考生得分：***
是否评分：未评分
评价描述：***
7. （第二章）在含有n个结点的顺序存储的线性表中，在任一位置插入一个结点所需移动结点的平均次数为______
A. n
B. (n-1)/2
C. n/2
D. (n+1)/2
试题编号：1.06
试题类型：单选题
标准答案：***
试题难度：一般
试题解析：***
考生答案：
考生得分：***
是否评分：未评分
评价描述：***
8. （第四章）若栈采用链式存储结构,则下面的说法中正确的是________
A. 不需要判断栈满但需要判断栈是否为空
B. 需要判断栈是否栈空与栈满
C. 需要判断栈满但不需要判断栈空
D. 栈满栈空都不需要判断
试题编号：1.07
试题类型：单选题
标准答案：***
试题难度：一般
试题解析：***
考生答案：
考生得分：***
是否评分：未评分
评价描述：***
9. （第四章）在一个链栈中，已知s为栈顶指针（直接指向栈顶元素结点，无头结点），t为栈底指针，直接指向栈底元素，则插入r结点的操作为____________。
A. t->next=r;t=r;
B. r->next=s;s=r;
C. s->next=r;s=r;
D. r->next=t;
试题编号：1.08
试题类型：单选题
标准答案：***
试题难度：一般
试题解析：***
考生答案：
考生得分：***
是否评分：未评分
评价描述：***
10. （第二章）链表不具备的特点是____________。
A. 不必事先估计存储空间
B. 插入删除不需要移动元素
C. 可顺序访问任一结点
D. 所需空间与其长度无关
试题编号：1.09
试题类型：单选题
标准答案：***
试题难度：一般
试题解析：***
考生答案：
考生得分：***
是否评分：未评分
评价描述：***
11. （第二章）带附加头结点的双循环链表L为空表的条件是____________。
A. L==NULL
B.L->next==NULL
C.L->prior==L
D. L->prior==NULL
试题编号：1.10
试题类型：单选题
标准答案：***
试题难度：一般
试题解析：***
考生答案：
考生得分：***
是否评分：未评分
评价描述：***
12. （第三章）设广义表L=（a,（b,c,d））,则L的长度与深度分别为____________。
A. 1和3
B. 1和2
C. 2和3
D. 2和2
试题编号：1.11
试题类型：单选题
标准答案：***
试题难度：一般
试题解析：***
考生答案：
考生得分：***
是否评分：未评分
评价描述：***
13. （第四章）一个栈的输入序列为1，2，3，4，5，6下面哪一个序列不可能是这个栈的输出序列______
A. 1, 2, 3, 4, 5, 6
B. 3, 2, 6, 4, 5, 1
C. 2, 4, 6, 5, 3, 1
D. 6, 5, 4, 3, 2, 1
试题编号：1.12
试题类型：单选题
标准答案：***
试题难度：一般
试题解析：***
考生答案：
考生得分：***
是否评分：未评分
评价描述：***
14. （第四章）循环队列用数组A存放其元素值，已知其头尾指针分别是front和rear，则当前队列中的元素个数是____________。
A. (rear-front+m)%m
B. rear-front+1
C. rear-front-1
D. rear-front
试题编号：1.13
试题类型：单选题
标准答案：***
试题难度：一般
试题解析：***
考生答案：
考生得分：***
是否评分：未评分
评价描述：***
15. （第四章）栈和队列的共同特点是____________。
A. 只允许在端点处插入和删除元素
B. 都是先进后出
C. 都是先进先出
D. 没有共同点
试题编号：1.14
试题类型：单选题
标准答案：***
试题难度：一般
试题解析：***
考生答案：A
考生得分：***
是否评分：未评分
评价描述：***
16. （第四章）中缀表达式(A+B)*D+E/(F+A*D)+C的后缀形式是______
A. AB+D*E/FA+*DC+
B. ABD*+EFAD*+/C+
C. ABDEFADC+*+/+*+
D. AB+D*EFAD*+/+C+
试题编号：1.15
试题类型：单选题
标准答案：***
试题难度：一般
试题解析：***
考生答案：
考生得分：***
是否评分：未评分
评价描述：***
17. （第五章）如下图所示的4棵二叉树，_________不是完全二叉树。
A.
B.
C.
D.
试题编号：1.16.
试题类型：单选题
标准答案：***
试题难度：一般
试题解析：***
考生答案：
考生得分：***
是否评分：未评分
评价描述：***
18. （第五章）设某棵二叉树中有2000个结点，则该二叉树的最小高度为____________。
A. 9
B. 10
C. 11
D. 12
试题编号：1.17
试题类型：单选题
标准答案：***
试题难度：一般
试题解析：***
考生答案：C
考生得分：***
是否评分：未评分
评价描述：***
19. （第五章）深度为6(根的层次为1)的二叉树至多有__________结点
A. 64
B. 63
C. 31
D. 32
试题编号：1.18
试题类型：单选题
标准答案：***
试题难度：一般
试题解析：***
考生答案：
考生得分：***
是否评分：未评分
评价描述：***
20. （第五章）二叉树的第k层的结点数最多为____________。
A. 2k-1
B. 2k+1
C. 2k-1
D. 2k-1
试题编号：1.19
试题类型：单选题
标准答案：***
试题难度：一般
试题解析：***
考生答案：C
考生得分：***
是否评分：未评分
评价描述：***
21. （第五章）如果一棵二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树满足的条件是__________。
A. 空或只有一个结点
B. 高度等于其结点数
C. 任一结点无右孩子
D. 任一结点无左孩子
试题编号：1.20
试题类型：单选题
标准答案：***
试题难度：一般
试题解析：***
考生答案：C
考生得分：***
是否评分：未评分
评价描述：***
22. （第五章）树的基本遍历策略分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。结论__________是正确的。
A. 树的先根遍历序列与其对应的二叉树的先序遍历序列相同
B. 树的后根遍历序列与其对应的二叉树的先序遍历序列相同
C. 树的先根遍历序列与其对应的二叉树的中序遍历序列相同
D. 以上都不对
试题编号：1.21
试题类型：单选题
标准答案：***
试题难度：一般
试题解析：***
考生答案：
考生得分：***
是否评分：未评分
评价描述：***
23. （第六章）根据使用频率为5个字符设计的哈夫曼编码不可能是____________。
A. 100，111，110，101，0
B. 111，110，10，01，00
C. 000，001，010，011，01
D. 001，000，01，11，10
试题编号：1.22
试题类型：单选题
标准答案：***
试题难度：一般
试题解析：***
考生答案：
考生得分：***
是否评分：未评分
评价描述：***
24. （第六章）下列数据结构中,不属于二叉树的是____________
A. 堆
B. 哈夫曼树
C. 线索二叉树
D. B树
试题编号：1.23
试题类型：单选题
标准答案：***
试题难度：一般
试题解析：***
考生答案：
考生得分：***
是否评分：未评分
评价描述：***
25. （第七章）采用邻接表存储的图的广度优先遍历算法类似于二叉树的__________。
A. 先序遍历
B. 中序遍历
C. 后序遍历
D. 层次遍历
试题编号：1.24
试题类型：单选题
标准答案：***
试题难度：一般
试题解析：***
考生答案：D
考生得分：***
是否评分：未评分
评价描述：***
26. （第七章）对用邻接表表示的图进行深度优先遍历时，通常是借助_________来实现算法。
A. 队列
B. 栈
C. 树
D. 图
试题编号：1.25
试题类型：单选题
标准答案：***
试题难度：一般
试题解析：***
考生答案：
考生得分：***
是否评分：未评分
评价描述：***
27. （第七章）在一个图中，所有顶点的度数之和等于图的边数的_________倍。
A. 1/2
B. 1
C. 2
D. 4
试题编号：1.26
试题类型：单选题
标准答案：***
试题难度：一般
试题解析：***
考生答案：C
考生得分：***
是否评分：未评分
评价描述：***
28. （第九章）对线性表进行二分查找，要求线性表必须____________。
A. 以顺序方式存储
B. 以顺序方式存储，且结点按关键字有序排序
C. 以链接方式存储
D. 结点按关键字有序排序，存储方式无所谓
试题编号：1.27
试题类型：单选题
标准答案：***
试题难度：一般
试题解析：***
考生答案：B
考生得分：***
是否评分：未评分
评价描述：***
29. （第十章）排序方法中，每次从未排序序列中查找值最小的元素放到已排序序列（初始时为空）的末尾，该排序方法称为____________。
A. 选择排序
B. 冒泡排序
C. 希尔排序
D. 插入排序
试题编号：1.28
试题类型：单选题
标准答案：***
试题难度：一般
试题解析：***
考生答案：
考生得分：***
是否评分：未评分
评价描述：***
30. （第十章）下列四种排序中，____________是空间复杂度最大的。
A. 选择排序
B. 冒泡排序
C. 归并排序
D. 快速排序
试题编号：1.29
试题类型：单选题
标准答案：***
试题难度：一般
试题解析：***
考生答案：C
考生得分：***
是否评分：未评分
评价描述：***
二、填空题(共30题，每题1分，共30分)
31. （第一章）数据结构分为和物理结构两种结构。
试题编号：2.01
试题类型：填空题
标准答案：***
试题难度：一般
试题解析：***
考生答案：逻辑结构
考生得分：***
是否评分：未评分
评价描述：***
32. （第一章）线性结构中元素之间存在一对一关系，而图形结构中元素之间存在关系。
试题编号：2.02.1
试题类型：填空题
标准答案：***
试题难度：一般
试题解析：***
考生答案：多对多
考生得分：***
是否评分：未评分
评价描述：***
33. （第一章）线性结构中元素之间存在一对一关系，而树形结构中元素之间存在关系。
试题编号：2.02.2
试题类型：填空题
标准答案：***
试题难度：一般
试题解析：***
考生答案：一对多
考生得分：***
是否评分：未评分
评价描述：***
34. （第一章）一个算法的最基本的原操作执行次数为(3n2+2nlog2n+4n-7)/(7n),则该算法的时间复杂度为。
试题编号：2.03
试题类型：填空题
标准答案：***
试题难度：一般
试题解析：***
考生答案：
考生得分：***
是否评分：未评分
评价描述：***
35. （第二章）链式存储结构用一组地址任意的存储单元依次存放数据元素，数据元素之间的逻辑关系通过间接地反映。
试题编号：2.04
试题类型：填空题
标准答案：***
试题难度：一般
试题解析：***
考生答案：
考生得分：***
是否评分：未评分
评价描述：***
36. （第二章）向一个长度为n的顺序表中的第i个元素(1≤i≤n)之后插入一个元素时，需向后移动个元素。
试题编号：2.05
试题类型：填空题
标准答案：***
试题难度：一般
试题解析：***
考生答案：
考生得分：***
是否评分：未评分
评价描述：***
37. （第二章）当线性表的元素总数不固定，且很少随机存取表中元素，但插入和删除操作较多时，应采用存储结构。
试题编号：2.06
试题类型：填空题
标准答案：***
试题难度：一般
试题解析：***
考生答案：
考生得分：***
是否评分：未评分
评价描述：***
38. （第二章）在单链表中，要删除某一指定的结点，必须找到该结点的结点。
试题编号：2.07
试题类型：填空题
标准答案：***
试题难度：一般
试题解析：***
考生答案：前件
考生得分：***
是否评分：未评分
评价描述：***
39. （第二章）删除单链表中结点p所指向的下一个结点（假设不为空）时，应执行以下操作： 第一步 q=;
试题编号：2.08.1
试题类型：填空题
标准答案：***
试题难度：一般
试题解析：***
考生答案：
考生得分：***
是否评分：未评分
评价描述：***
40. （第二章）第二步 p->next=;
试题编号：2.08.2
试题类型：填空题
标准答案：***
试题难度：一般
试题解析：***
考生答案：
考生得分：***
是否评分：未评分
评价描述：***
41. （第二章）第三步 ;
试题编号：2.08.3
试题类型：填空题
标准答案：***
试题难度：一般
试题解析：***
考生答案：
考生得分：***
是否评分：未评分
评价描述：***
42. （第三章）设广义表L=（（a,b,c））,则L的长度为。
试题编号：2.09.1
试题类型：填空题
标准答案：***
试题难度：一般
试题解析：***
考生答案：1
考生得分：***
是否评分：未评分
评价描述：***
43. （第三章）设广义表L=（（a,b,c））,则L的深度为。
试题编号：2.09.2
试题类型：填空题
标准答案：***
试题难度：一般
试题解析：***
考生答案：2
考生得分：***
是否评分：未评分
评价描述：***
44. （第四章）栈的特点是，与之对应后进先出，队列的特点是。
试题编号：2.10
试题类型：填空题
标准答案：***
试题难度：一般
试题解析：***
考生答案：先进先出
考生得分：***
是否评分：未评分
评价描述：***
45. （第四章）在栈顶进行插入删除一个元素的时间复杂度是。
试题编号：2.11
试题类型：填空题
标准答案：***
试题难度：一般
试题解析：***
考生答案：
考生得分：***
是否评分：未评分
评价描述：***
46. （第四章）后缀算式9 2 3 +- 10 2 / -的值为。
试题编号：2.12
试题类型：填空题
标准答案：***
试题难度：一般
试题解析：***
考生答案：
考生得分：***
是否评分：未评分
评价描述：***
47. （第四章）一个环形队列中共有MaxSize个单元，那么队满时共有个元素。
试题编号：2.13
试题类型：填空题
标准答案：***
试题难度：一般
试题解析：***
考生答案：
考生得分：***
是否评分：未评分
评价描述：***
48. （第四章）设栈S和队列Q的初始状态为空，元素a1,a2,a3,a4,a5,a6,a7,a8依次通过栈S，一个元素出栈后立即进入队列Q，若8个元素出队列的次序是a3,a5,a4,a8,a7,a6,a2,a1，则栈S的容量至少应该是。
试题编号：2.14
试题类型：填空题
标准答案：***
试题难度：一般
试题解析：***
考生答案：
考生得分：***
是否评分：未评分
评价描述：***
49. （第五章）一棵高度为5的完全二叉树至少有个结点。
试题编号：2.15.1
试题类型：填空题
标准答案：***
试题难度：一般
试题解析：***
考生答案：16
考生得分：***
是否评分：未评分
评价描述：***
50. （第五章）一棵高度为5的完全二叉树最多有个结点。
试题编号：2.15.2
试题类型：填空题
标准答案：***
试题难度：一般
试题解析：***
考生答案：
考生得分：***
是否评分：未评分
评价描述：***
51. （第五章）如果一个完全二叉树的叶子结点个数为n，则这棵二叉树的总结点数为或。
试题编号：2.16
试题类型：填空题
标准答案：***
试题难度：一般
试题解析：***
考生答案：
考生得分：***
是否评分：未评分
评价描述：***
52. （第五章）设某棵二叉树的中序遍历序列为ABCD，后序遍历序列为BADC，则其前序遍历序列为。
试题编号：2.17
试题类型：填空题
标准答案：***
试题难度：一般
试题解析：***
考生答案：
考生得分：***
是否评分：未评分
评价描述：***
53. （第七章）已知一个有向图的邻接矩阵表示，计算第i个结点的度的方法是。
试题编号：2.18
试题类型：填空题
标准答案：***
试题难度：一般
试题解析：***
考生答案：
考生得分：***
是否评分：未评分
评价描述：***
54. （第七章）一个图的三种存储方法中，表示法是唯一的。
试题编号：2.19.1
试题类型：填空题
标准答案：***
试题难度：一般
试题解析：***
考生答案：
考生得分：***
是否评分：未评分
评价描述：***
55. （第七章）一个图的三种存储方法中，和边集数组表示法是不唯一的。
试题编号：2.19.2
试题类型：填空题
标准答案：***
试题难度：一般
试题解析：***
考生答案：
考生得分：***
是否评分：未评分
评价描述：***
56. （第七章）一个有n个顶点的无向连通图最少有条边。
试题编号：2.20.1
试题类型：填空题
标准答案：***
试题难度：一般
试题解析：***
考生答案：
考生得分：***
是否评分：未评分
评价描述：***
57. （第七章）一个有n个顶点的无向连通图最多条边。
试题编号：2.20.2
试题类型：填空题
标准答案：***
试题难度：一般
试题解析：***
考生答案：
考生得分：***
是否评分：未评分
评价描述：***
58. （第八章）设一个连通图G中有n个顶点e条边，则其最小生成树上有条边。
试题编号：2.21
试题类型：填空题
标准答案：***
试题难度：一般
试题解析：***
考生答案：
考生得分：***
是否评分：未评分
评价描述：***
59. （第十章）外排序是指在排序前后，数据在上，排序时数据调入内存进行的排序方法。
试题编号：2.22
试题类型：填空题
标准答案：***
试题难度：一般
试题解析：***
考生答案：
考生得分：***
是否评分：未评分
评价描述：***
60. （第十章）在选择排序、冒泡排序、归并排序中，排序是空间复杂度最大的。
试题编号：2.23
试题类型：填空题
标准答案：***
试题难度：一般
试题解析：***
考生答案：
考生得分：***
是否评分：未评分
评价描述：***
三、简答题(共10题，每题4分，共40分)
61. （第二章）简述顺序表和链表存储方式的特点。
顺序表的优点是可以随机访问数据元素；缺点是大小固定，不利于增删结点。链表的优点是采用指针方式增减结点，非常方便（只需要改变指针指向，不移动结点）；缺点是不能进行随机访问，另外，每个结点上增加指针域，造成额外存储空间增大。
试题编号：3.1
试题类型：简答题
标准答案：***
试题难度：一般
试题解析：***
考生答案：
顺序表的优点是可以随机访问数据元素；缺点是大小固定，不利于增删结点。链表的优点是采用指针方式增减结点，非常方便（只需要改变指针指向，不移动结点）；缺点是不能进行随机访问，另外，每个结点上增加指针域，造成额外存储空间增大。
考生得分：***
是否评分：未评分
评价描述：***
62. （第二章）
在一个单链表HL中删除指针p所指结点，应执行如下关键操作：
if(________)
HL = HL->next;
else
{
q = HL;
while(________)
q = q->next;
_____________;
}
delete p;
请将代码补充完整。
试题编号：3.2
试题类型：简答题
标准答案：***
试题难度：一般
试题解析：***
考生答案：
考生得分：***
是否评分：未评分
评价描述：***
63. （第四章）
以下2个问题基于下面的环形队列：
设环形队列Q的当前状态如下，
写出队列Q的队空、队满定条件及进队、出队操作的的描述语句。
试题编号：3.3
试题类型：简答题
标准答案：***
试题难度：一般
试题解析：***
考生答案：
考生得分：***
是否评分：未评分
评价描述：***
64. （第四章）画出元素a0,a1,a2出队，元素a4,a5,a6,a7进队后队列Q的状态。
试题编号：3.4
试题类型：简答题
标准答案：***
试题难度：一般
试题解析：***
考生答案：
考生得分：***
是否评分：未评分
评价描述：***
65. （第五章）写出下图这棵二叉树的前序遍历、中序遍历、后序遍历和层次遍历序列。
试题编号：3.5
试题类型：简答题
标准答案：***
试题难度：一般
试题解析：***
考生答案：
考生得分：***
是否评分：未评分
评价描述：***
66. （第六章）已知一组元素为(30,46,62,27,32,49,13,45)，画出按元素排列顺序输入生成的一棵二叉搜索树，并写出在这棵二叉搜索树中查找元素49所需的元素比较次数。
试题编号：3.6
试题类型：简答题
标准答案：***
试题难度：一般
试题解析：***
考生答案：
考生得分：***
是否评分：未评分
评价描述：***
67. （第六章）给定权值{6,7,12,10,30,25}，构造相应的哈夫曼树，要求写出构造步骤，并计算该树的带权路径长度。
试题编号：3.7
试题类型：简答题
标准答案：***
试题难度：一般
试题解析：***
考生答案：
考生得分：***
是否评分：未评分
评价描述：***
68. （第七章）
已知一个无向图的邻接表表示为：
画出该图的图形表示，并写出在该邻接表存储结构下，以顶点v4为出发点进行深度优先遍历的遍历序列。
试题编号：3.8
试题类型：简答题
标准答案：***
试题难度：一般
试题解析：***
考生答案：
考生得分：***
是否评分：未评分
评价描述：***
69. （第八章） 对如下的图，用Prim算法从顶点5开始求最小生成树，写出按次序产生的边。采用 Kruscal算法产生的边次序是哪些？画出最小生成树。
.
试题编号：3.9
试题类型：简答题
标准答案：***
试题难度：一般
试题解析：***
考生答案：
考生得分：***
是否评分：未评分
评价描述：***
70. （第十章）已知序列（50，39，65，97，76，13，27，50）请用插入排序写出每一趟排序的结果。
试题编号：3.9+1
试题类型：简答题
标准答案：***
试题难度：一般
试题解析：***
考生答案：
考生得分：***
是否评分：未评分
评价描述：***
姓名：朱小勇
编号：1170300475
一、选择题
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
二、填空题
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
三、简答题
61
62
63
64
65
66
67
68
69
70
页:
[1]