贵州大学理学院数学系信息与计算科学专业《数据结构》期末考试试题及答案(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至k6．具有60个结点的二叉树，其叶子结点有12个，则度过1的结点数为（）（A）、11 （B）、13 （C）、48 （D）、377．图的Depth-First Search(DFS)遍历思想实际上是二叉树（）遍历方法的推广。

（A）、先序（B）、中序（C）、后序（D）、层序8．在下列链队列Q中，元素a出队的操作序列为（）（（（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．线索二叉链表是利用（）域存储后继结点的地址。

（A）、lchild （B）、data （C）、rchild （D）、root二、填空题1． 逻辑结构决定了算法的 ，而存储结构决定了算法的 。

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

3． 线性表（a 1,a 2,…,a n ）的顺序存储结构中，设每个单元的长度为L ，元素a i 的存储地址LOC(a i )为 4． 已知一双向链表如下(指针域名为next 和prior)：现将p 所指之间，其操作步骤为： ； ； ； ； 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 的压缩存储三元组表如下：写出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． 已知有如下的有向网：求顶点A6分）三、 1． #define LIST_INIT_SIZE 100 //顺序表初始分配容量 typedef struct {Elemtype *elem; //顺序存储空间基址int length; //当前长度（存储元素个数） }SqList;设计一个算法，删除其元素值为x 的结点（假若x 是唯一的）。

并求出其算法的⎥⎥⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎢⎢⎣⎡∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞64266346751275356156F E D C B A平均时间复杂度。

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

其中结点定义如下：typedef struct {Elemtype *base; //栈底指针Elemtype *top; //栈顶指针}Stack;设计算法，将栈顶元素出栈并存入e 中． base3．设二叉链树的类型定义如下：typedef int Elemtype;typedef struct node{Elemtype data;struct node *lchild, *rchild;}BinNode, *BinTree;试写出求该二叉树叶子结点数的算法:S tatus CountLeaves(BinTree &root,int &n){//n is the number of leaves……} 答案：选择题（每题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二、应用题（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)、（3）、（3分） 3、(5分，每行4、 初始关键字： [18] 12 25 53 18第 一 趟：[12 18] 25 53 18第 二 趟：[12 18 25] 53 18第 三 趟：[12 18 第 四 趟：[12 18 18 （4分）O （n 2）（1分）。

5、7分（1）4分（2）4分6、(1) 3分（2）WPL=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分)A B 1 C 3 2 5 D 4 E FStatus 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->elem[j+1];L->length--;} （8分）平均时间复杂度：（2分）设元素个数记为n，则平均时间复杂度为：2（10分）void pop(Stack &S,Elemtype &e){if(S.top==S.base) return ERROR;S.top--;e=*s.top;}2、（10分）voidCountLeaves(BinTree T,int &n){if(T){if((!(T->lchild)&&!( T->rchild)) n++;CountLeaves (T->lchild,n);CountLeaves (T->rchild,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.不好说8. 数据结构作为一门独立的课程出现是在（）年。

A.1946B.1953C.1964D.19689. 数据结构只是研究数据的逻辑结构和物理结构，这种观点（）。

A.正确B.错误C.前半句对，后半句错D.前半句错，后半句对10. 计算机内部数据处理的基本单位是（）。

A.数据B.数据元素C.数据项D.数据库二、填空题1. 数据结构按逻辑结构可分为两大类，分别是____________?__和_________________。

2. 数据的逻辑结构有四种基本形态，分别是________________、__________________、__________________和__________________。

3. 线性结构反映结点间的逻辑关系是__________________的，非线性结构反映结点间的逻辑关系是__________________的。