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

1、贵州大学理学院数学系信息与计算科学专业数据结构期末考试试题及答案(2003-2004学年第2学期)一、单项选择题1. 对于一个算法，当输入非法数据时，也要能作出相应的处理，这种要求称为 ()o(A)、正确性 (B).可行性 (C).健壮性 (D).输入性2设S为C语言的语句，计算机执行下面算法时，算法的时间复杂度为()。for(i=n-l； i>=0； i)for(j=0； j<i； j+) S；(A)、n2 (B). O(nlgn) (C). O(n) (D)0(1?)3折半査找法适用于( )o(A)、有序顺序表(B)、有序单链表(C)、有序顺序表和有序单链表都可以(D)、无限制

2、4. 顺序存储结构的优势是()。(A)、利于插入操作(B)、利于删除操作(0、利于顺序访问(D)、利于随机访问5. 深度为k的完全二叉树，其叶子结点必在第()层上。(A)、k-1(B)、k (C)、k-1 和 k (D)、1 至 k6. 具有60个结点的二叉树,其叶子结点有12个,则度过1的结点数为()(A)、11(B)、13(C)、48(D)、377. 图的Depth-First Search (DFS)遍历思想实际上是二叉树()遍历方法的推广。(A)、先序 (B)、中序 (C)、后序 (D)、层序&在下列链队列Q中，元素a出队的操作序列为(A) 、p=Q.front->nex

3、t; p->next= Q.front->next;(B) 、p=Q.front->next; Q.front->next=p->next;第1页共7页)(B)、所有结点权值之和(D)、根结点的值(C) 、p=Q.rear->next; p->next= Q.rear->next;(D) 、p=Q->next; Q->next=p->next;9. Huffman树的带权路径长度WPL等于(A)、除根结点之外的所有结点权值之和(C)、各叶子结点的带权路径长度之和10.线索二叉链表是利用()域存储后继结点的地址。(A)> l

4、child (B)> data (C)> rch订d(D). root二、填空题1. 逻辑结构决定了算法的,而存储结构决定了算法的。2. 栈和队列都是一种的线性表，栈的插入和删除只能在进行。3. 线性表(&,%,&)的顺序存储结构中，设每个单元的长度为L,元素业的存储地址LOC (ai)为4. 已知一双向链表如下(指针域名为next和prior):现将P所指的结点插入到x和y结点之间，其操作步骤 为：;5. n个结点无向完全图的的边数为n个结点的生成树的边数为6. 已知一有向无环图如下：任意写出二种拓扑排序序列：、O7. 己知二叉树的中序遍历序列为BCA,后序遍历序

5、列为CBA,则该二叉树的先序遍历序列为,层序遍历序列为o三、应用题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) 对中所建立的二叉排序树进行中序遍历，写出遍历序列。(3) 画出对(2)中的遍历序列进行折半査找过程的判定树。3. 已知二个稀疏矩阵A和B的压缩存储三元组表如下：AB1jV13-52462524

6、2-1529ijV25233741352"9558写出A-B压缩存储的三元组表。(5分)4. 已知一维数组中的数据为(18,12,25, 53,18),试写出插入排序(升序)过 程。并指出具有n个元素的插入排序的时间复杂度是多少？(5分)5. 已知一网络的邻接矩阵如下，求从顶点A开始的最小生成树。(8分，要有 过程)A B C D E FAoo 651 co 00B6 oo oo 53 ooC5 oo oo 7 co 2D157 s 64Eoo 3 oo 6 co 6Foo oo 246 oo(1)求从顶点A开始的最小生成树。(2)分别画出以A为起点的DFS生成树和BFS生成树。6.

7、已知数据六个字母及在通信中出现频率如下表：ABCDEF0.150.150.10.10.20.3把这些字母和频率作为叶子结点及权值，完成如下工作(7分，要有过程)。(1) 画出对应的Huffman树。(2) 计算带权路径长度WPL。求 A、B、C、D、E、F 的 Huffman 编码。第5页共7页7. 已知有如下的有向网:第6页共7页第#页共7页求顶点A到其它各顶点的最短路径（釆用Dijkstra算法，要有过程）。（6分）三、 设计题（30分，每题10分，用C语言写出算法，做在答题纸 上）1.已知线性表（创,如亠）以顺序存储结构为存储结构，其类型定义如下： #define LIST_INIT_S

8、IZE 100 顺序表初始分配容量 typedef struct Elemtype *elem;顺序存储空间基址int length;当命丧应（右储元素个数）SqList;设计一个算法，删除其元素值为X的结点（假若X是唯一的）。并求出其算法的 平均时间复杂度。其算法函数头部如下：Status ListDelete（Sqlist &L,Elemtype x）base2设顺序栈如左图所示。其中结点定义如下： typedef struct Elemtype *base; 栈底指针Elemtype *top; 栈顶指针 Stack;设计算法，将栈顶元素出栈并存入e中.3.设二叉链树的类型定义如

9、下：typedef int Elemtype;typedef struct node Elemtype data; struct node *lchild, *rchild;BinNode, *BinTree;试写出求该二叉树叶子结点数的算法:Status CountLeaves(BinTree &rootjnt &n) /n is the number of leaves答案:选择题(每题1分)1、C2、D3、A4、D5、C6、D7、A8、B 9、CIO、C一、填空题1. 设计、实现2. 特殊、栈顶3. LOC (al) +(i-l)*L4. p->next=q->

10、;next;q->next->pnoi-p; q->next=p;p->prior=q;5. n(n-l)/2n-16. ADCBFEG、ABCDEFFG7. ABC、ABC二、应用题1(1) Hash 表(4 分)地址0123456789101112关键安132164572282412探测次数171231311（2）查找成功的平均查找长度：（1分）(5*1+1*24-2*3+1*7) /9=20/9查找不成功的平均查找长度：(1分)(2+1+9+S+7+6+5+4+3+2+1) /13=2 (1)、构造(3分)(2) 、10 14 15 19 20 21 22 56

11、(2 分)、(3 分)第7页共7页3、（5分，每行0.5）iJV13-524633741342-152185584、初始关键字:1812255318第趟:12«<8255318第二趟：12182勺V18第三趟:1218255318第四趟：12181853O (112)(1分)o5、7分(1) 4 分（4分）(2) 4 分6、（1）3 分0A B C D(2) WPL=O1*3十0.1*3十0.2*2十015*3十015*3十03*21=(1 分)(3) A： 010 B： OilC： 110 D： 111 E： 00 F； 10 (3 分)12、A-B： (A、B)1分A-C：

12、 (A、D、C)2分A-D： (A、D)1分A-E： (A、D、E)2分三,设计题（20分）1、（10 分）Status ListDelete(Sqlist &L.ElemTvpe x)mt ij;fbi(i=O;i<L->length;i+)if(L->elemi=x) break;if(i=L->length) letuin ERROR;for(j=i;j<L->lengthi-l ;j 十十)L->elemj =L->elemj+1 ;L->length;(8 分)平均时间复杂度：(2分)设元素个数记为n,则平均时间复杂度为:n-i) =22 (10 分)void pop(Stack &S.Elemtype &e)if(S.top=S.base)