《数据结构》期末考试试题及答案(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)、正确性但).可行性(C).健壮性2 •设S为C语言的语句,计算机执行下面算法时，for(i=n-1 ; i>=0; i--)for(j=0 ; jvi; j++)(A)、n2(B). O(nlgn)3•折半查找法适用于( a(D). 输入性算法的时间复杂度为(dS；(C). O(n) (D).)。

O(n2) (A)、有序顺序表(B)、有序单链表(C)、有序顺序表和有序单链表都可以4 .顺序存储结构的优势是( d )。

(A)、利于插入操作(B)、利于删除操作(C)、利于顺序访问(D)、利于随机访问5. 深度为k的完全二叉树，其叶子结点必在第(A)、k-1 ( B)、k (C)、k-1 和6. 具有60个结点的二叉树，其叶子结点有(A)、11 ( B)、13 ( C)、48(D)、无限制c )层上。

(D)、1 至k12个，则度过1(D)、37k的结点数为(7 .图的Depth-First Search(DFS) 遍历思想实际上是二叉树(法的推广。

(A)、先序(B)、中序(C)、后序(D)、层序8.在下列链队列Q中，元素a出队的操作序列为(a )遍历方front(A )、(B )、(C)、(D )、p=Q.front->next; p->next= Q.front->next; p=Q.front->next; Q.front->next=p->next; p=Q.rear->next; p->next= Q.rear->next; p=Q->next; Q->next=p->next;9. Huffman树的带权路径长度WPL等于((A)、除根结点之外的所有结点权值之和(C)、各叶子结点的带权路径长度之和(B)、(D))所有结点权值之和根结点的值b■10.线索二叉链表是利用(c )域存储后继结点的地址。

(A)、Ichild ( B)、data ( C)、rchild (D)、root二、填空题1. 逻辑结构决定了算法的______________________ 设计，而存储结构决定了算法的__________________ 实现_______ 。

2. 栈和队列都是一种特殊的线性表，栈的插入和删除只能在栈顶进行。

3. 线性表(a i,a2,…,a n)的顺序存储结构中，设每个单元的长度为L,元素a的存储地址LOC(a)为__________________________4. 已知一双向链表如下(指针域名为next和prior):现将p所指的结点插入到x和y结点之间，其操作步骤___________________ ? __________________ ? ______________________?5. n个结点无向完全图的的边数为 __________________ ,n 个结点的生成树的边数为________________________ 。

6 .已知一有向无环图如下：任意写出二种拓扑排序序列：__________________ 、 _______________________ 。

7.已知二叉树的中序遍历序列为BCA后序遍历序列为CBA则该二叉树的先序遍历序列为__________________ ，层序遍历序列为 ___________________。

三、应用题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) 按元素在表中的次序，建立一棵二叉排序树(2) 对(1)中所建立的二叉排序树进行中序遍历，写出遍历序列。

(3) 画出对(2)中的遍历序列进行折半查找过程的判定树。

3.已知二个稀疏矩阵 A 和B 的压缩存储三元组表如下：18,12,25,53,18_),试写出插入排序(升序)过 程。

并指出具有n 个元素的插入排序的时间复杂度是多少？ (5分)(2)分别画出以 A 为起点的DFS 生成树和BFS 生成树。

把这些字母和频率作为叶子结点及权值，完成如下工作(7分，要有过程)。

(1) 画出对应的Huffman 树。

4.已知一维数组中的数据为(5.已知一网络的邻接矩阵如下，求从顶点 过程)A B C DA 冋 6 5 1B 6 od cd 5C 5 od oo7D 1 57odE□03oo6 F2 4 (1)求从顶点A 开始的最小生成树。

A 开始的最小生成树。

(8分，要有E F3 od26466乂A B写出A-B 压缩存储的三元组表。

（5分）od od "|(2) 计算带权路径长度 WPL(3)求 A B 、C 、D E 、F 的 Huffman 编码。

7.已知有如下的有向网:求顶点A 到其它各顶点的最短路径(采用 Dijkstra算法，要有过程)。

(6分)三、 设计题(30分，每题10分,用C 语言写出算法，做在答题纸 上)1. 已知线性表(a 1,a 2,…,a n )以顺序存储结构为存储结构，其类型定义如下：#define LIST_INIT_SIZE typedef struct { Elemtype *elem; int length; }SqList;设计一个算法，删除其元素值为 x 的结点 平均时间复杂度。

其算法函数头部如下：S tatus ListDelete(Sqlist &L,Elemtype x) { }2•设顺序栈如左图所示。

其中结点定义如下： typedef struct {Elemtype *base; 〃栈底指针 Elemtype *top; 〃栈顶指针 }Stack; 设计算法，将栈顶元素出栈并存入e 中.3 .设二叉链树的类型定义如下： typedef intElemtype;typedef struct node{ Elemtypedata;struct node *lchild, *rchild; }BinNode, *BinTree;试写出求该二叉树叶子结点数的算法 ： S tatus CountLeaves(BinTree &root,int &n) {〃n is the number of leaves }100 〃顺序表初始分配容量〃顺序存储空间基址〃当前长度(存储元素个数)base答案：选择题(每题1分)1、C2、D3、A4、D5、C6、D7、A8、B9、C 10、C一、填空题1 •设计、实现2 .特殊、栈顶3. LOC (a1) +(i-1)*L4. p_>next=q_>next;q_>next->prior=p; q_>next=p;p_>prior=q;5. n(n-1)/2、n-16. ADCBFEG、ABCDEFFG7. ABC、ABC二、应用题(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分)⑵、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 8 4、初始关键字：[18] 12 25 53 18第一趟:[12亠「8] 25 53 18第二趟：[12 18 25] 5318第三趟:[12 18 25 53] 18第四趟：[12 18 18 -25 ' 53]O ( n2) (1 分)。

5、7分(1) 4 分(4分) (2) 4 分6、(1) 3 分F(2) WPL=0.1*3+0.1*3+0.2*2+0.15*3+0.15*3+03*2仁(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分—k设计题（20 分卜）1、(10 分)Status ListDelete(Sqlist &L,ElemType x){int i,j;for(i=0;i<L->le ngth;i++) if(L->elem[i]==x) break;if(i=L->length) return ERROR;for(j=i;j<L->le ngthi_1;j++) L->elem[j]=L->elem[j+1];L->le ngth--;} (8 分)平均时间复杂度：(2分)设元素个数记为n,则平均时间复杂度为:1nE (n - i)二n i #2( 10 分)void pop(Stack &S,Elemtype &e) { if(S.top==S.base) return ERROR;S.top--;e=*s.top;}2、(10 分)voidCo un tLeaves(B in Tree T,i nt &n) { if(T){if((!(T->lchild)&&!( T->rchild)) n++; Coun tLeaves (T->lchild, n);Coun tLeaves (T->rchild, n);人生中每一次对自己心灵的释惑，都是一种修行，都是一种成长。

相信生命中的每一次磨砺，都会让自己的人生折射出异常的光芒，都会让自己的身心焕发出不一样的香味。

我们常常用人生中的一些痛，换得人生的一份成熟与成长，用一些不可避免的遗憾，换取生命的一份美丽。

在大风大雨，大风大浪，大悲大喜之后，沉淀出一份人生的淡然与淡泊，静好与安宁，深邃与宽厚，慈悲与欣然……生活里的每个人，都是我们的一面镜子，你给别人什么，别人就会回待你什么。

当你为一件事情不悦的时候，应该想想你给过人家怎样负面的情绪。

世界上的幸福，没有一处不是来自用心经营和珍惜。

当你一味的去挑剔指责别人的时候，有没有反思过自己是否做得尽善尽美呢？假如你的心太过自我，不懂得经营和善待，不懂得尊重他人的感受，那么你永远也不会获得真正的爱和幸福……人生就像一场旅行，我们所行走的每一步都是在丰富生命的意义。