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

(2003-2004学年第2学期)

一、 单项选择题

1对于一个算法 当输入非法数据时也要能作出相应的处理这种要求称为 。

(A)、正确性 (B).可行性 (C).健壮性 (D). 输入性

2设S为C语言的语句,计算机执行下面算法时算法的时间复杂度为 。for(i=n-1 i>=0 i--)for(j=0 j<i j++) S

(A)、 n2 (B).O(nlgn) (C).O(n) (D). O(n2)

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出队的操作序列为 

A、 p=Q.front->ne xt;p->ne xt=Q.front->ne xt;

B、 p=Q.front->ne xt;Q.front->ne xt=p->ne xt;

C、 p=Q.re ar->next;p->next=Q.re ar->next;

D、 p=Q->n e xt;Q->ne xt=p->ne xt;

9 Huffman树的带权路径长度WPL等于 

A、除根结点之外的所有结点权值之和 B、所有结点权值之和C、各叶子结点的带权路径长度之和 D、根结点的值

10线索二叉链表是利用 域存储后继结点的地址。

A、 lchild B、 data C、 rchild D、 root

二、填空题

1 逻辑结构决定了算法的  而存储结构决定了算法的 。

2 栈和队列都是一种 的线性表栈的插入和删除只能在 进行。

3 线性表a1,a2,…,an的顺序存储结构中设每个单元的长度为L元素ai

4 已知一双向链表如下(指针域名为next和prior) 

现将 p 所指的结点插入到 x和 y 结点之间 其操作步骤为 

  

5 n个结点无向完全图的的边数为 n个结点的生成树的边数为 。

6 已知一有向无环图如下

A

任意写出二种拓扑排序序列 、 。

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的压缩存储三元组表如下

A B

写出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 已知数据六个字母及在通信中出现频率如下表

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

1 画出对应的Huffman树。

2 计算带权路径长度WPL。

3 求A、 B、 C、 D、 E、 F的Huffman编码。

7 已知有如下的有向网

求顶点A到其它各顶点的最短路径采2用Dijkstra算法要有过程。 6分

三、 设计题30分每题10分,用C语言写出算法做在答题纸

上

1 已知线性表a1,a2,…,an以顺序存储结构为存储结构其类型定义如下

#define LIST_INIT_SIZE 100 //顺序表初始分配容量

设计一个算法删除其元素值为x的结点假若x是唯一的。并求出其算法的平均时间复杂度。其算法函数头部如下

Status ListDelete(Sqlist&L,Elemtype x)

{

……

}

设计算法将栈顶元素出栈并存入e中 base

3设二叉链树的类型定义如下typedef int Elemtype;typedef struct node{

Elemtype data;struct node *lchild,*rchild;

}BinNode, *BinTre e;

试写出求该二叉树叶子结点数的算法:

Status CountLeaves(BinTree&root,int&n)

{//n is the number of leaves

……

}

答案

选择题每题1分

1、 C2、 D3、A4、 D5、 C6、 D7、A8、 B9、 C10、 C

一、填空题

1设计、实现

2特殊、栈顶

3 LO Ca 1 +(i-1)*L

4 p->next=q->next;q->next->prior=p; q->next=p;p->pr i or=q;

5 n(n-1)/2、 n-1

6 AD CBFEG、 ABCD EFFG

7 AB C、 AB C

二、应用题

1  1Hash表4分

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分

(2)、 10 1415 1920212256 2分

3、 3分

3、 (5分每行0.5)

4、 初始关键字 [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n2 1分。

5、 7分

1 4分

2 4分

6、 (1)3分

A B C D

2WP L=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&L,ElemType x)

{int i,j;for(i=0;i<L->length;i++)if(L->elem[i]==x)break;if(i=L->length) return ERROR;for(j=i;j<L->lengthi-1;j++)

L->elem[j]=L->e lem[j+1];

;

平均时间复杂度 2分

设元素个数记为n则平均时间复杂度为

E

2 10分void pop(Stac k&S,Elemtype&e)

{if(S.top==S.bas e)return ERROR;

S.top--;e=*s.top;

}

2、 10分voidCountLeaves(BinTree T,int&n)

{if(T)

{if((!(T->lchild)&&!(T->rchild))n++;

CountLeaves (T->lc hild,n);

CountLeaves (T->rc hild,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++;

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.易读性稳定性和安全性

7.数据在计算机内有链式和顺序两种存储方式在存储空间使用的灵活性上链式存储比顺序存储要  。

A.低 B.高 C.相同 D.不好说