1、第 1 页 共 126 页 贵州大学理学院数学系信息与计算科学专业 数据结构期末考试试题及答案 (2003-2004 学年第 2 学期 ) 一、 单项选择题 1对于一个算法，当输入非法数据时，也要能作出相应的处理，这种要求称为（ ）。 (A)、 正确性 (B). 可行性 (C). 健壮性 (D). 输入性 2设 S为 C 语言的语句 ,计算机执行下面算法时，算法的时间复杂度为（ ）。 for(i=n-1； i=0； i-) for(j=0； jnext; p-next= Q.front-next; （ B）、 p=Q.front-next; Q.front-next=p-next; （ C）、
2、 p=Q.rear-next; p-next= Q.rear-next; （ D）、 p=Q-next; Q-next=p-next; 9 Huffman 树的带权路径长度 WPL 等于（ ） （ A）、除根结点之外的所有结点权值之和 （ B）、所有结点权值之和 （ C）、各叶子结点的带权路径长度之和 （ D）、根结点的值 10线索二叉链表是利用（ ）域存储后继结点的地址。 b c d a front rear 第 2 页 共 126 页 （ A）、 lchild （ B）、 data （ C）、 rchild （ D）、 root 二、填空题 1 逻辑结构决定了算法的 ，而存储结构决定了算法
3、的 。 2 栈和队列都是一种 的线性表，栈的插入和删除只能在 进行。 3 线性表（ a1,a2, ,an）的顺序存储结构中，设每个单元的长度为 L，元素 ai的存储地址 LOC(ai)为 4 已知一双向链表如下 (指针域名为 next和 prior)： q p 现将 p 所 指 的 结 点 插 入 到 x 和 y 结 点 之 间 ， 其 操 作 步 骤为： ； ； ； ； 5 n 个结点无向完全图的的边数为 ， n 个结点的生成树的边数为 。 6已知一有向无环图 如下： 任意写出二种拓扑排序序列： 、 。 7已知二叉树的中序遍历序列为 BCA，后序遍历序列为 CBA，则该二叉树的先序遍历序列为
4、 ，层序遍历序列为 。 三、应用题 1 设散列函数 H(k)=k % 13,设关键字系列为 22,12,24,6,45,7,8,13,21,要求用线性探测法处理冲突。 (6 分 ) (1) 构造 HASH表。 (2) 分别求查找成功和不成功时的平均查找长度。 2 给定表（ 19,14,22,15,20,21,56,10） .（ 8分） （ 1） 按元素在表中的次序，建立一棵二叉排序树 x y e B A C D F E G 第 3 页 共 126 页 （ 2） 对 (1)中所建立的二叉排序树进行中序遍历，写出遍历序列。 （ 3） 画出对 (2)中的遍历序列进行折半查找过程的判定树。 3 已知二
5、个稀疏矩阵 A和 B的压缩存储三元组表如下： A B i j V i j V 1 3 -5 2 5 2 2 4 6 3 3 7 2 5 2 4 1 3 4 2 -1 5 2 -9 5 2 9 5 5 8 写出 A-B压缩存储的三元组表。（ 5 分） 4 已知一维数组中的数据为（ 18,12,25,53,18） , 试写出插入排序（升序）过程。并指出具有 n个元素的插入排序的时间复杂度是多少？ (5分 ) 5 已知一网络的邻接矩阵如下，求从顶点 A 开始的最小生成树。 (8 分，要有过程 ) A B C D E F （ 1）求从顶点 A开始的最小生 成树。 （ 2）分别画出以 A为起点的 DFS
6、生成树和 BFS生成树。 6已知数据六个字母及在通信中出现频率如下表： A B C D E F 0.15 0.15 0.1 0.1 0.2 0.3 把这些字母和频率作为叶子结点及权值，完成如下工作 (7分，要有过程 )。 （ 1） 画出对应的 Huffman树。 （ 2） 计算带权路径长度 WPL。 （ 3） 求 A、 B、 C、 D、 E、 F的 Huffman编码。 64266346751275356156FEDCBA第 4 页 共 126 页 7 已知有如下的有向网： 求顶点 A 到其它各顶点的最短路径（采用 Dijkstra 算法，要有过程）。（ 6分 ） 三、 设计题 （ 30 分，
7、每题 10 分 ,用 C 语言写出算法，做在答题纸上） 1 已知线性表（ a1,a2, ,an）以顺序存储结构为存储结构，其类型定义如下： #define LIST_INIT_SIZE 100 /顺序表初始分配容量 typedef struct Elemtype *elem; /顺序存储空间基址 int length; /当 前长度（存储元素个数） SqList; 设计一个算法，删除其元素值为 x 的结点（假若 x 是唯一的） 。并求出其算法的平均时间复杂度。其算法函数头部如下： Status ListDelete(Sqlist /栈底指针 Elemtype *top; /栈顶指针 Stack
8、; 设计算法，将栈顶元素出栈并存入 e 中 base 3设二叉链树的类型定义如下： typedef int Elemtype; typedef struct node Elemtype data; struct node *lchild, *rchild; BinNode, *BinTree; 试写出求该二叉树叶子结点数的算法 : 2 5 3 6 4 10 6 1 2 2 A B C D E an a2 a1 第 5 页 共 126 页 Status CountLeaves(BinTree q-next-prior=p; q-next=p;p-prior=q; 5 n(n-1)/2、 n-1
9、6 ADCBFEG、 ABCDEFFG 7 ABC、 ABC 二、 应用题 1 （ 1） Hash 表（ 4 分） 地址 0 1 2 3 4 5 6 7 8 9 10 11 12 关键安 13 21 6 45 7 22 8 24 12 探测次数 1 7 1 2 3 1 3 1 1 （ 2）查找成功的平均查找长度：（ 1 分） （ 5*1+1*2+2*3+1*7） /9=20/9 查找不成功的平均查找长度：（ 1 分） （ 2+1+9+8+7+6+5+4+3+2+1） /13= 2（ 1）、构造（ 3 分） (2)、 10 14 15 19 20 21 22 56（ 2 分） （ 3）、（ 3
10、分） 19 14 22 10 15 20 56 21 第 6 页 共 126 页 3、 (5 分，每行 0.5) i j v 1 3 -5 2 4 6 3 3 7 4 1 3 4 2 -1 5 2 18 5 5 8 4、 初始关键字： 18 12 25 53 18 第 一 趟： 12 18 25 53 18 第 二 趟： 12 18 25 53 18 第 三 趟： 12 18 25 53 18 第 四 趟： 12 18 18 25 53 （ 4 分） O（ n2）（ 1 分）。 5、 7 分 （ 1） 4 分 （ 2） 4 分 6、 (1) 3 分 A B 1 C 3 2 5 D 4 E F
11、E F A B C D 第 7 页 共 126 页 （ 2） WPL=0.1*3+0.1*3+0.2*2+0.15*3+0.15*3+03*21= (1 分 ) （ 3） A： 010 B： 011 C： 110 D： 111 E： 00 F； 10 （ 3 分） 12、 A-B：（ A、 B） 1 分 A-C：（ A、 D、 C） 2 分 A-D：（ A、 D） 1 分 A-E：（ A、 D、 E） 2 分 三，设计题（ 20 分） 1、 (10 分 ) Status ListDelete(Sqlist for(i=0;ilength;i+) if(L-elemi=x) break; if(
12、i=L-length) return ERROR; for(j=i;jlengthi-1;j+) L-elemj=L-elemj+1; L-length-; （ 8 分） 平均时间复杂度：（ 2 分） 设元素个数记为 n，则平均时间复杂度为： ni ninnE 1 2 1)(1 2（ 10 分） void pop(Stack S.top-; e=*s.top; 2、（ 10 分） voidCountLeaves(BinTree T,int CountLeaves (T-lchild,n); CountLeaves (T-rchild,n); 第 8 页 共 126 页 习题 1 一、单项选择题
13、 1. 数据结构是指（ ）。 A.数据元素的组织形式 B.数据类型 C.数据存储结构 D.数据定义 2. 数据在计算机存储器内表示时，物理地址与逻辑地址不相同的，称之为（ ）。 A.存储结构 B.逻辑结构 C.链式存储结构 D.顺序存储结构 3. 树形结构是数据元素之间存在一种（ ）。 A.一对一关系 B.多对多关系 C.多对一关系 D.一对多关系 4. 设语句 x+的时间是单位时间，则以下语句的时间复杂度为（ ）。 for(i=1; i=n; i+) for(j=i; j=n; j+) x+; A.O(1) B.O( ) C.O(n) D.O( ) 5. 算法分析的目的是（ 1），算法分析的
14、两个主要方面是（ 2）。 第 9 页 共 126 页 （ 1） A.找出数据结构的合理性 B.研究算法中的输入和输出关系 C.分析算法的效率以求改进 D.分析算法的易懂性和文档性 （ 2） A.空间复杂度和时间复杂度 B.正确性和简明性 C.可读性和文档性 D.数据复杂性和程序复杂性 6. 计算机算法指的是（ 1），它 具备输入，输出和（ 2）等五个特性。 （ 1） A.计算方法 B.排序方法 C.解决问题的有限运算序列 D.调度方法 （ 2） A.可行性，可移植性和可扩充性 B.可行性，确定性和有穷性 C.确定性，有穷性和稳定性 D.易读性，稳定性和安全性 7. 数据在计算机内有链式和顺序两
15、种存储方式，在存储空间使用的灵活性上，链式存储比顺序存储要（ ）。 A.低 B.高 C.相同 D.不好说 第 10 页 共 126 页 8. 数据结构作为一门独立的课 程出现是在（ ）年。 A.1946 B.1953 C.1964 D.1968 9. 数据结构只是研究数据的逻辑结构和物理结构，这种观点（ ）。 A.正确 B.错误 C.前半句对，后半句错 D.前半句错，后半句对 10. 计算机内部数据处理的基本单位是（ ）。 A.数据 B.数据元素 C.数据项 D.数据库 二、填空题 1. 数据结构按逻辑结构可分为两大类，分别是_?_和 _。 2. 数据的逻辑结构有 四种基本形态，分别是_、 _、_和 _。 3. 线性结构反映结点间的逻辑关系是_的，非线性结构反映结点间的逻辑关系是 _的。 4. 一个算法的效率可分为 _效率和_效率。
