数据结构期末考试试题及答案资料.doc

贵州大学理学院数学系信息与计算科学专业 《数据结构》期末考试试题及答案 ( 2003-2004 学年第 2 学期 ) 一、 单项选择题 1．对于一个算法，当输入非法数据时，也要能作出相应的处理，这种要求称为 （ ）。 (A) 、正确性 (B). 可行性 (C). 健壮性 (D). 输入性 2．设 S 为 C 语言的语句 , 计算机执行下面算法时， 算法的时间复杂度为 （ ）。 for(i=n-1 ； i=0 ； i--) for(j=0 ； ji ； j++) S； 2 (B). O(nlgn) (C). O(n)(D). 2 (A) 、 n O(n ) 3．折半查找法适用于（ ）。 A）、有序顺序表（ B）、有序单链表 C）、有序顺序表和有序单链表都可以（ D）、无限制 4．顺序存储结构的优势是（ ）。 （A）、利于插入操作 （ B）、利于删除操作 （C）、利于顺序访问 （D）、利于随机访问 5．深度为 k 的完全二叉树，其叶子结点必在第（ ）层上。 （ A）、 k-1 （ B）、k （ C）、 k-1 和 k （ D）、1 至 k 6．具有 60 个结点的二叉树， 其叶子结点有 12 个，则度过 1 的结点数为 （ ） （ A）、 11 （ B）、13 （ C）、 48 （ D）、 37 7．图的 Depth-First Search(DFS) 遍历思想实际上是二叉树（ ）遍历方法 的推广。 （A）、先序 （ B）、中序 （ C）、后序 （ D）、层序 8．在下列链队列 Q中，元素 a 出队的操作序列为（ ） front a b c d ∧ Q A）、 p=Q.front-next; 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）、所有结点权值之和 （ C）、各叶子结点的带权路径长度之和 （ D）、根结点的值 10．线索二叉链表是利用（ ）域存储后继结点的地址。 第 1 页 共 126 页 （ A）、 lchild （ B）、 data （ C）、 rchild （D）、 root 二、填空题 1． 逻 辑 结 构 决 定 了 算 法 的 ， 而 存 储 结 构 决 定 了 算 法 的 。 2． 栈和队列都是一种 的线性表，栈的插入和删除只能在 进行。 3． 线性表（ a ,a , ,a n ）的顺序存储结构中，设每个单元的长度为 L，元素 a 1 2 i 的存储地址 LOC(a ) 为 i 4． 已知一双向链表如下 ( 指针域名为 next 和 prior) ： x y q p e 现 将 p 所 指 的 结 点 插 入 到 x 和 y 结 点 之 间 ， 其 操 作 步 骤 为： ； ； ； ； 5．n 个结点无向完全图的的边数为 ， n 个结点的生成树的边数为 。 6．已知一有向无环图如下： B F D A G C E 任意写出二种拓扑排序序列： 、 。 7．已知二叉树的中序遍历序列为 BCA，后序遍历序列为 CBA，则该二叉树的先序 遍历序列为 ，层序遍历序列为 。 三、应用题 1． 设散列函数 H(k)=k % 13, 设关键字系列为 {22,12,24,6,45,7,8,13,21}, 要 求用线性探测法处理冲突。 (6 分 ) 构造 HASH表。 分别求查找成功和不成功时的平均查找长度。 2． 给定表（ 19,14,22,15,20,21,56,10 ） . （ 8 分） （ 1） 按元素在表中的次序，建立一棵二叉排序树 第 2 页 共 126 页 2） 对 (1) 中所建立的二叉排序树进行中序遍历，写出遍历序列。 3） 画出对 (2) 中的遍历序列进行折半查找过程的判定树。 3． 已知二个稀疏矩阵 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