《数据结构》期末考试试题及答案.docxVIP

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