计算机数据结构期末复习题
1. 数据结构是一门研究非数值计算的程序设计问题中计算机的 操作对象 以及它们之间的 关系 和运算等的学科。
2. 数据结构被形式地定义为（D, R），其中D是 数据元素 的有限集合，R是D上的 关系 有限集合。
3. 数据结构包括数据的 逻辑结构 、数据的 存储结构 和数据的 运算 这三个方面的内容。
4. 数据结构按逻辑结构可分为两大类，它们分别是 线性结构 和 非线性结构 。
5.有n个球队参加的足球联赛按主客场制进行比赛，共需进行n(n-1)场比赛。 参考答案： n(n-1)
6.一棵树的前根遍历序列为EFHIGJK，后根遍历序列为HFIEJKG，将树转换成二叉树形式后，该二叉树的后序遍历序列为HIFKJGE。 5. 线性结构中元素之间存在一对一关系，树形结构中元素之间存在一对多关系，图形结构中元素之间存在多对多关系。
6． 在线性结构中，第一个结点 没有 前驱结点，其余每个结点有且只有 1个前驱结点；最后一个结点 没有 后续结点，其余每个结点有且只有1个后续结点。
7. 在树形结构中，树根结点没有 前驱 结点，其余每个结点有且只有 1 个前驱结点；叶子结点没有 后续 结点，其余每个结点的后续结点数可以任意多个 。
8. 在图形结构中，每个结点的前驱结点数和后续结点数可以 任意多个 。
9．数据的存储结构可用四种基本的存储方法表示，它们分别是顺序 、 链式 、 索引 和 散列 。
10. 数据的运算最常用的有5种，它们分别是插入 、 删除、修改、 查找 、排序。
11.在一棵m阶B树上，每个内部结点的关键字数目最少为?m/2?-1个，最多为m-1个，其子树数目最少为?m/2?，最多为m。
12. 后缀算式9 2 3 +- 10 2 / -的值为 -1；
中缀算式8-(3+5)*(5-6/2)对应的后缀算式为8 3 5 + 5 6 2 / - * -。
13. 在一段文字中，5个常用汉字及出现频度如下：于 个 和 是 有
18 17 14 10 1
要求：
(1)求出每个汉字的Huffman编码：于:11 个:10 和01 是:001 有:000（5分） (2)其带权路径长度为131。（1分）
14. 栈是一种特殊的线性表，允许插入和删除运算的一端称为 栈顶 。不允许插入和删除运算的一端称为 栈底 。
15. 队列 是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。
16. 对于一棵具有n个结点的二叉树，用二叉链表存储时，其指针总数为2n个，其中n-1个用于指向孩子，n+1个指针是空闲的。
17. 设有向图G中有向边的集合E={<1,2>,<2,3>,<1,4>,<4,2>,<4,3>}，则该图的一种拓扑序列为(1,4,2,3)。
18． 由３个结点所构成的二叉树有 5 种形态。
19．一棵具有２５７个结点的完全二叉树，它的深度为 9
20．设一棵完全二叉树有700个结点，则共有 350 个叶子结点。 21．在数据的存放无规律而言的线性表中进行检索的最佳方法是 顺序查找（线
性查找） 。
22. 线性有序表（a1，a2，a3，…，a256)是从小到大排列的，对一个给定的值k，用二分法检索表中与k相等的元素，在查找不成功的情况下，最多需要检索 8 次。设有100个结点，用二分法查找时，最大比较次数是 7 。
23. 假设在有序线性表a[20]上进行折半查找，则比较一次查找成功的结点数为1；比较两次查找成功的结点数为 2 ；比较四次查找成功的结点数为 8 ；平均查找长度为 3.7 。
24．折半查找有序表（4，6，12，20，28，38，50，70，88，100），若查找表中元素20，它将依次与表中元素 28，6，12，20 比较大小。
25. 在各种查找方法中，平均查找长度与结点个数n无关的查找方法是 散列查
找 。
26. 散列法存储的基本思想是由 关键字的值 决定数据的存储地址。 27.设一组初始记录关键字序列为(15,9,7,8,20,-1,6,4)，则根据这些初始关键字序列建成的初始小顶堆为(-1,4,6,8,20,7,15,9)。 参考答案：
28. 下图是某一工程作业的网络图G的邻接表表示法，则：
（1）以结点V1出发深度遍历图G所得的结点序列为：(20)； （2）以结点V1出发广度遍历图G所得的结点序列为：(21)；
（3）从结点V1到结点V8的最短路径为：(22)，最短路径的长度为：(23)； （4）从结点V1到结点V8的关键路径为：(24)，关键路径的长度为：(25)天。 参考答案：
（1）V1,V2,V3,V8,V5,V7,V4,V6； （2）V1,V2,V4,V6,V3,V5,V7,V8；
（3）V1到V8最短路径为V1-V2-V5-V7-V8，长度为56；
（4）V1到V8的关键路径是V1-V6-V5-V3-V8，长度为97。
（ B ）1. 非线性结构是数据元素之间存在一种：
A）一对多关系 B）多对多关系 C）多对一关系 D）
一对一关系
（ C ）2. 数据结构中，与所使用的计算机无关的是数据的 结构；
A) 存储 B) 物理 C) 逻辑 D) 物理
和存储
（ C ）3. 算法分析的目的是：
A) 找出数据结构的合理性 B) 研究算法中的输入和输出的
关系
C) 分析算法的效率以求改进 D) 分析算法的易懂性和文档性
（ A ）4. 算法分析的两个主要方面是：
A) 空间复杂性和时间复杂性 B) 正确性和简明性
C) 可读性和文档性 D) 数据复杂性和程序复杂性
（ C ）5. 计算机算法指的是：
A) 计算方法 B) 排序方法 C) 解决问题的有限运算序列
D) 调度方法
（ B ）6. 计算机算法必须具备输入、输出和 等5个特性。
A) 可行性、可移植性和可扩充性 B) 可行性、确定性和有
穷性
C) 确定性、有穷性和稳定性 D) 易读性、稳定性和安
全性
（ B ）7.对一个算法的评价，不包括如下（ ）方面的内容。
A．健壮性和可读性 B．并行性 C．正确性 D．时空复杂度 （ A ）8。数据结构是指（ ）。
A．数据元素的组织形式 B．数据类型 C．数据存储结构 D．数据定义
（ C ）9.在长度为n的顺序表的第i个位置插入一个新元素的算法的时间复杂度为（ ）(1<=i<=n+1)。
A．O(0) B．O(1) C．O(n) D．O(n2) （ B ）10.设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用（ ）最节省时间。
A．单链表 B．带头结点的双循环链表 C．带尾指针的单循环链表 D．单循环链表 （ B ）11.下列说法错误的是（ ）。
(1)静态链表由于兼顾了顺序存储和动态链表的优点，所以它存取表中第i
个元素的时间与i无关。
(2)静态链表中能容纳的元素个数的最大数在表定义时就确定了，以后不能增加。 (3)静态链表与动态链表在元素的插入、删除上类似，不需做元素的移动。 A．(1)和(2) B．(1) C．(1)、(2)和(3) D．(2)
（ D ）12.若一个栈的输入序列为1,2,3,…,n，输出序列的第一个元素是i，则第j个输出元素是（ ）。
A．i-j-1 B．i-j C．j-i+1 D．不确定的 （ C ）13．数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为：
（A）存储结构 （B）逻辑结构 （C）顺序存储结构
（D）链式存储结构
（ B ）14.一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是
（A）110 （B）108 （C）100 （D）120
（ A ）15. 在n个结点的顺序表中，算法的时间复杂度是O（1）的操作是：
（A） 访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i
≤n）
（B） 在第i个结点后插入一个新结点（1≤i≤n） （C） 删除第i个结点（1≤i≤n） （D） 将n个结点从小到大排序
（ B ）16. 向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动 个元素
（A）8 （B）63.5 （C）63 （D）7
（ D ）17.若元素a,b,c,d,e,f依次进栈，允许进栈、退栈操作交替进行，但不允许连续三次进行退栈工作，则不可能得到的出栈序列是（ ）。
A．dcebfa B．cbdaef C．bcaefd D．afedcb （ D ）18.循环队列存储在数组A[0..m-1]中，则入队时的操作为（ ）。
A．rear=rear+1 B．rear=(rear+1) mod (m+1) C．rear=(rear+1) mod m-1 D．rear=(rear+1) mod m
（ B ）19.设在一不带头结点的链队列Q中，Q.front和Q.rear分别为其队头和队尾指针，则下列语句序列中能实现将指针p所指结点插入队列Q的是（ ）。
A．Q.front->next=p; Q.front=p; B．Q.rear->next=p; Q.rear=p; C．p->next=Q.rear; Q.rear=p; D.p->next=Q.front;Q.front=p; （ A ）20.数组A[6][7]的每个元素占五个字节，将其按列优先次序存储，若首元素A[0][0]的存储地址为1000，则元素A[5][5]的存储地址为（ ）。
A．1175 B．1180 C．1205 D．1210 （ A ）21. 链接存储的存储结构所占存储空间：
（A） 分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针 （B） 只有一部分，存放结点值
(C） 只有一部分，存储表示结点间关系的指针
（D） 分两部分，一部分存放结点值，另一部分存放结点所占单元数
（ B ）22. 链表是一种采用 存储结构存储的线性表；
（A）顺序 （B）链式 （C）星式 （D）网状
（ D ）23. 线性表若采用链式存储结构时，要求内存中可用存储单元的地址:
（A）必须是连续的 （B）部分地址必须是连续的 （C）一定是不连续的 （D）连续或不连续都可以
（ B ）24． 线性表Ｌ在 情况下适用于使用链式结构实现。
（Ａ）需经常修改Ｌ中的结点值 （Ｂ）需不断对Ｌ进行删除插入 （Ｃ）Ｌ中含有大量的结点 （Ｄ）Ｌ中结点结构复杂
（ B ）25.栈中元素的进出原则是
Ａ．先进先出 Ｂ．后进先出 Ｃ．栈空则进
Ｄ．栈满则出
（ C ）26. 8．设一组初始记录关键字序列(5，2，6，3，8)，以第一个记录关键字5
为基准进行一趟快速排序的结果为（ ）。 (A) 2，3，5，8，6 (B) 3，2，5，8，6
