《数据结构》期末考试试题及答案(共7页).doc
精选优质文档-倾情为你奉上数据结构期末考试试题及答案(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；j<i；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至k6具有60个结点的二叉树，其叶子结点有12个，则度过1的结点数为（ ）（A）、11 （B）、13 （C）、48 （D）、377图的Depth-First Search(DFS)遍历思想实际上是二叉树（ a ）遍历方法的推广。 （A）、先序 （B）、中序 （C）、后序 （D）、层序8在下列链队列Q中，元素a出队的操作序列为（ a b ）b c d afrontrear 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）、所有结点权值之和（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)： y x e q p现将p所指的结点插入到x和y结点之间，其操作步骤为： ； ； ； ；5n个结点无向完全图的的边数为 ， n个结点的生成树的边数为 。6已知一有向无环图如下： BACDFEG 任意写出二种拓扑排序序列： 、 。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 BijVijV13-525224633725241342-152-9529558写出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已知数据六个字母及在通信中出现频率如下表：ABCDEF0.150.150.10.10.20.3把这些字母和频率作为叶子结点及权值，完成如下工作(7分，要有过程)。（1） 画出对应的Huffman树。（2） 计算带权路径长度WPL。（3） 求A、B、C、D、E、F的Huffman编码。7 已知有如下的有向网： 2 5 36 4 10 6 1 2 2 AEBDC求顶点A到其它各顶点的最短路径（采用Dijkstra算法，要有过程）。（6分）三、 设计题（30分，每题10分,用C语言写出算法，做在答题纸上）1 已知线性表（a1,a2,an）以顺序存储结构为存储结构，其类型定义如下： #define LIST_INIT_SIZE 100 /顺序表初始分配容量 typedef struct Elemtype *elem; /顺序存储空间基址 int length; /当前长度（存储元素个数） SqList;设计一个算法，删除其元素值为x的结点（假若x是唯一的）。并求出其算法的平均时间复杂度。其算法函数头部如下： Status ListDelete(Sqlist &L,Elemtype x) ana2a12设顺序栈如左图所示。 其中结点定义如下： top typedef struct Elemtype *base; /栈底指针Elemtype *top; /栈顶指针 Stack;设计算法，将栈顶元素出栈并存入e中 base3设二叉链树的类型定义如下： typedef int Elemtype; typedef struct node Elemtype data; struct node *lchild, *rchild; BinNode, *BinTree;试写出求该二叉树叶子结点数的算法: Status CountLeaves(BinTree &root,int &n) /n is the number of leaves 答案：选择题（每题1分）1、C 2、D 3、A 4、D 5、C 6、D 7、A 8、B 9、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二、 应用题1 （1）Hash表（4分）地址0123456789101112关键安132164572282412探测次数171231311（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分） 19 14 22 10 15 20 56 21(2)、10 14 15 19 20 21 22 56（2分）（3）、（3分）3、(5分，每行0.5)ijv13-524633741342-152185584、 初始关键字： 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分A B 1 C 3 2 5 D 4 E F（2）4分6、(1) 3分 E F A B C D （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分)Status ListDelete(Sqlist &L,ElemType x) int i,j; for(i=0;i<L->length;i+)if(L->elemi=x) break; if(i=L->length) return ERROR; for(j=i;j<L->lengthi-1;j+) L->elemj=L->elemj+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);专心-专注-专业
