资源描述:
《《数据结构》试卷(样卷)》由会员上传分享,免费在线阅读,更多相关内容在工程资料-天天文库。
1、中南大学考试试卷(样卷)20〜20学年_学期数据结构课程时间100分钟-O--O商学院专业班级得分评卷人/JO得分评卷人一、填空题(本题20分,每空1分)1.在单琏表屮,除第一个元素结点外,任一结点的存储位置均由—其肓接前驱结点的链域的值指2.以折半查找方法査找一个线性表时,此线性表必须是—顺序存储结构存储的—有序表。3.在长度为n的顺序表中删除第i个元素(l
2、(能或不能)。6.在一个小顶堆屮,堆顶结点的值是所有结点屮的最小值,在一个人顶堆屮,堆顶结点的值是所有结点中的最人值O7.若给定数组a[0..6]的各分蜃值分别为:A,B,C,D,E,F,G,按这些值顺序建立的完全二叉树的中序遍历结果序列为—DBEAFCG,后序遍历的结果序列为DEBFGCAo8.在一棵二叉树中,第5层上的结点数最多为_16o9.假定一组记录的关键字为(46,79,56,38,40,80,36,40,75,66,84,24),对其进行插入排序的过程中,笫三趟插入排序的结果为:46567938,40,80,36,40,75,
3、66,84,24。(注:按非降序排列)。10.一棵含999个结点的完全二叉树的深度为_10o11.链式堆栈屮弹出一个元素的操作序列为(设栈顶指针为top)、二、构图题(木题40分)1•设有八个权值分别为(&7,6,5,4,3,2,1)的结点,构造其哈夫曼树,并计算其WPL的值。(注:WPL为带权路径长度。要求:画出哈夫曼树的完整构造过程)(10分)1022.从空树起,依次插入关键字11,22,9,88,7,10,12,30,23,构造一棵二叉排序树。(1)画出该二叉排序树;(7分)(2)画出从(1)所得树中删除关键字为88的结点Z后的二叉
4、排序树。(3分)3.写出下面这棵普通树的先根及后根遍历结果,并将Z转化为二叉树。(要求:画出转化过程)(10分)先根遍历:即为二叉树的前序遍历12596103478后根遍历:即为二叉树的中序遍历951062378414.试写出序列{50,26,3&80,70,90,8,30}按快速排序方法的第一趟排序过程及其它各趟排序结果。(10分)232638850907080得分评卷人三、Hash表(本题15分)1.设哈希表为HTE0..12],即表的大小为m=13o现釆用线性探测法及链地址法解决冲突。散列函数为:H(key)=key%13;(注:%
5、是求余数运算,即mod)O--O若插入的关键码序列为{2,8,31,20,19,18,53,27}。(1)(9分)试画出用线性探测法解决冲突后插入这8个关键码后的哈希表并计算ASLsUCCO(2)(6分)试画出用链地址法解决冲突后插入这8个关键码后的哈希表并计算ASLSUCCO商学院专业班级(注:ASLsucc为成功查找吋的平均查找长度。)得分评卷人四、算法设计题(本题25分)1.设单链表中结点的存储结构为:structnode{intdata;structnode*next;};要求:(1)建立带头结点的单链表:(2)对所建立的单链表就
6、地逆置。(15分)voidListInverse_L(LinkList&L){〃--单链表的就地逆置■…〃LNode*p,*q;p=L->next;L->next=NULL;while(p!=NULL){q=p->next;p->next=L->next;L->next=p;p=q;structLNode*insert(structLNode*head,intxjnti){intj=l;structLNode*s,*q;q=head;s=(structLNode*)malloc(sizeof{structLNode));s->data=x
7、;if(i==l){s->next=q;head=s;}elsevvhile(q->next!=NULL)q=q->next;j++;}if{j=i-l){s->next=q・>next;q->next=s;}noposition*”);elseprintf(nerror!thereis}return(head);2.对一个有序的顺序结构存储的线性表编写一个折半查找的递归算法(10分)。