数据结构期末考试试题及答案

第 1 页 共 129 页贵州大学理学院数学系信息与计算科学专业数据结构期末考试试题及答案(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） 、p=Q.rear-next; p-next= Q.rear-next;（D） 、p=Q-next; Q-next=p-next;9 Huffman 树的带权路径长度 WPL 等于（ ）（A） 、除根结点之外的所有结点权值之和 （B） 、所有结点权值之和b c d afrontrear第 2 页 共 129 页（C） 、各叶子结点的带权路径长度之和 （D） 、根结点的值10线索二叉链表是利用（ ）域存储后继结点的地址。（A） 、lchild （B） 、data （C） 、rchild （D） 、root二、填空题1 逻辑结构决定了算法的 ，而存储结构决定了算法的 。2 栈和队列都是一种 的线性表，栈的插入和删除只能在 进行。3 线性表（a 1,a2,an）的顺序存储结构中，设每个单元的长度为 L，元素ai的存储地址 LOC(ai)为 4 已知一双向链表如下(指针域名为 next 和 prior)：qp现将 p 所指的结点插入到 x 和 y 结点之间，其操作步骤为： ； ； ；5n 个结点无向完全图的的边数为 ，n 个结点的生成树的边数为 。6已知一有向无环图如下：任意写出二种拓扑排序序列： 、 。7已知二叉树的中序遍历序列为 BCA，后序遍历序列为 CBA，则该二叉树的先序遍历序列为 ，层序遍历序列为 。三、应用题1 设散列函数 H(k)=k % 13,设关键字系列为22,12,24,6,45,7,8,13,21,要求用线性探测法处理冲突。(6 分)(1) 构造 HASH 表。(2) 分别求查找成功和不成功时的平均查找长度。x yeBACDFEG第 3 页 共 129 页2 给定表（19,14,22,15,20,21,56,10）.（8 分）（1） 按元素在表中的次序，建立一棵二叉排序树（2） 对(1)中所建立的二叉排序树进行中序遍历，写出遍历序列。（3） 画出对(2)中的遍历序列进行折半查找过程的判定树。3 已知二个稀疏矩阵 A 和 B 的压缩存储三元组表如下：A Bi j V i j V1 3 -5 2 5 22 4 6 3 3 72 5 2 4 1 34 2 -1 5 2 -95 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 生成树和 BFS 生成树。6已知数据六个字母及在通信中出现频率如下表：A B C D E F0.15 0.15 0.1 0.1 0.2 0.3把这些字母和频率作为叶子结点及权值，完成如下工作(7 分，要有过程)。64237516FE第 4 页 共 129 页（1） 画出对应的 Huffman 树。（2） 计算带权路径长度 WPL。（3） 求 A、B、C、D、E、F 的 Huffman 编码。7 已知有如下的有向网：求顶点 A 到其它各顶点的最短路径（采用 Dijkstra 算法，要有过程） 。 （6 分）三、 设计题（30 分，每题 10 分,用 C 语言写出算法，做在答题纸上）1 已知线性表（a 1,a2,an）以顺序存储结构为存储结构，其类型定义如下：#define LIST_INIT_SIZE 100 /顺序表初始分配容量typedef struct Elemtype *elem; /顺序存储空间基址int length; /当前长度（存储元素个数）SqList;设计一个算法，删除其元素值为 x 的结点（假若 x 是唯一的） 。并求出其算法的平均时间复杂度。其算法函数头部如下：Status ListDelete(Sqlist /栈底指针Elemtype *top; /栈顶指针Stack;设计算法，将栈顶元素出栈并存入 e 中 base3设二叉链树的类型定义如下：2 5364 10 6 1 22ABC DEana2a1第 5 页 共 129 页typedef int Elemtype;typedef struct nodeElemtype data;struct node *lchild, *rchild; BinNode, *BinTree;试写出求该二叉树叶子结点数的算法:Status CountLeaves(BinTree q-next-prior=p; q-next=p;p-prior=q;5n(n-1)/2、n-16ADCBFEG、ABCDEFFG7ABC、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 分）1914 2210 15 20 5621第 6 页 共 129 页(2)、10 14 15 19 20 21 22 56（2 分）（3） 、 （3 分）3、(5 分，每行 0.5)i j v1 3 -52 4 63 3 74 1 34 2 -15 2 185 5 84、 初始关键字： 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（n 2） （1 分） 。5、7 分（1）4 分（2）4 分6、(1) 3 分AB 1 C 3 25 D 4 E F第 7 页 共 129 页（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(i=L-length) return ERROR;for(j=i;jlengthi-1;j+)L-elemj=L-elemj+1;L-length-; （8 分）平均时间复杂度：（2 分）设元素个数记为 n，则平均时间复杂度为：niE121)(2（10 分）void pop(Stack S.top-;e=*s.top;2、 （10 分）voidCountLeaves(BinTree T,int E FA B C D第 8 页 共 129 页CountLeaves (T-lchild,n);CountLeaves (T-rchild,n);习题1一、单项选择题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+;第 9 页 共 129 页A.O(1) B.O( ) C.O(n) D.O( )5. 算法分析的目的是（1 ） ，算法分析的两个主要方面是（2） 。（1） A.找出数据结构的合理性 B.研究算法中的输入和输出关系C.分析算法的效率以求改进 D.分析算法的易懂性和文档性（2） A.空间复杂度和时间复杂度 B.正确性和简明性C.可读性和文档性 D.数据复杂性和程序复杂性6. 计算机算法指的是（1 ） ，它具备输入，输出和（2 ）等五个特性。（1） A.计算方法 B.排序方法C.解决问题的有限运算序列 D.调度方法（2） A.可行性，可移植性和可扩充性 B.可行性，确定性和有穷性C.确定性，有穷性和稳定性 D.易读性，稳定性和安全性第 10 页 共 129 页7. 数据在计算机内有链式和顺序两种存储方式，在存储空间使用的灵活性上，链式存储比顺序存储要（ ） 。A.低 B.高 C.相同 D.不好说8. 数据结构作为一门独立的课程出现是在（ ）年。A.1946 B.1953 C.1964 D.19689