湖大数据结构及答案.docx
- 文档编号:10280084
- 上传时间:2023-05-24
- 格式:DOCX
- 页数:22
- 大小:66.67KB
湖大数据结构及答案.docx
《湖大数据结构及答案.docx》由会员分享,可在线阅读,更多相关《湖大数据结构及答案.docx(22页珍藏版)》请在冰点文库上搜索。
湖大数据结构及答案
考试中心填写:
湖南大学课程考试试卷
课程名称:
数据结构;试卷编号:
01;考试时间:
120分钟
年月日
考试用
(请将所有答案写在答题纸上)
一、填空题。
(20分)
1.已知单链表中指针q所指结点是指针p所指结点的直接前驱,若在*q与*p之间插入*s,则应执行()语句。
2.将两个各有n个元素的有序表归并成一个有序表,其最少的比较次数是()。
3.堆栈的特点是()。
4.已知完全二叉树的第5层有4个结点(根结点在第1层),则其叶结点数是()。
5.在有n个叶结点的Huffman树中,共有()个结点。
6.若数据表中每个元素已距其最终位置不远,则采用()算法最省时间。
7.内部排序问题的时间复杂度的下限是()。
8.对线性表进行折半查找时性能要能达到O(logn),要求线性表必须()。
9.如果具有n个顶点的图是一个环,则它有()棵生成树。
10.具有n个顶点的无向图最多有()条边。
二、请将下面的算法填写完整。
(10分)
下面算法的功能是:
用基数排序法对n个无符号整数进行排序(递增),在算法空缺处填上适当语句或表达式,使得算法完整且正确。
template
voidradix(elema[],elemb[],intn,intk,intr,intcnt[])
{//k为排序码的个数,r为基数
inti,j,x,m=1;
for(i=1;i<=k;i++)//分别对第i个排序码进行分配
{for(j=0;j for(j=0;j 装订线(答题不得超过此线) 学号: 姓名: 4、设一个散列表包含13个表项,.其下标从0到12,采用线性探查法解决冲突(p(K,i)=i),请按以下要求,将下列关键码按从左到右的顺序散列到表中。 10,100,32,45,58,126,3,29,200,400,0 散列函数采用除留余数法,用%SIZE(对表长取余运算)将各关键码映像到表中.,请指出每一个产生冲突的关键码可能产生多少次冲突? 5、一棵前序序列为1,2,3,4的二叉树,其中序序列可能是4,1,2,3吗,为什么? 设一棵二叉树的前序序列为1,2,3,4,5,6,7,8,9,其中序序列为2,3,1,5,4,7,8,6,9,试画出该二叉树。 6、假设用于通信的电文由字符集{a,b,c,d,e,f,g}中的字母构成。 它们在电文中出现的幅度分别为{0.31,0.16,0.10,0.08,0.11,0.20,0.04},为这7个字母统计哈夫曼编码,并计算其平均编码长度。 7、插入排序是否为稳定的排序算法? 为什么? 插入排序在最佳情况和最坏情况下,比较次数和移动数据次数分别为多少? (假设共有n个元素) 四、算法设计。 (35分) 1.设某带头结点的单链表L,,结点中的元素为整型数据,试编写算法,判断该单链表L中的元素,是否成等差关系,即各元素植依次为a1,a2,a3,a4,……an判断ai+1-ai=ai-ai-1是否成立,其中i满足1<=i<=n-1 2.设一棵二叉树,结点结构为|lchild|data|rchild其中 data域中存放一个字符,设计一个算法按前叙遍历顺序,仅打印出data域为数字的字符(即‘0’<=data<=’9’) 3.某百货公司仓库中电视机的价格和数量信息,按其价格从低到高存储在一个带头结点的循环链表中,链表中的结点由价格、数量和链指针三个域组成: |cost|num|next|,现新到m台价格为c的电视机需入库,试为此编写修改循环链表中存储的电视机信息的算法。 数据结构试题答案 一、填空题(每空2分,共20分) 1、q->link=s;s->link=p;(两个先后没有关系;link写成next也可以) 2、1 3、后进先出(或LIFO、先进后出) 4、10 5、2n-1 6、插入排序 7、(nlogn)(或nlogn)) 8、按关键码的值大小有序 9、n 10、n(n-1)/2 二、程序填空题(10分) 1、--cnt[(a[j]/m)%r](3分) 2、a[j]=b[j](4分) 3、m*r(3分) 三、应用题(每小题5分,共35分) 1、使用一个数组来存储两个栈,每个栈从各自的端点向中间延伸,从而减少空间的浪费。 (3分),当两个栈顶指针相遇时(|top2-top1|=1),栈满(1分);当栈顶指针为-1或n时,栈空(1分)。 (数组下标从0到n-1) 2、 二叉查找树如下: (4分) 平均查找长度=(1×1+2×2+3×3+4×2+5×2)/10=3.2(1分) 3、 广度优先搜索生成树(1为起点)(2.5分) 深度优先搜索生成树(2为起点)(2.5分) 4、 下标 0 1 2 3 4 5 6 7 8 9 10 11 12 散列表 0 3 29 200 32 45 58 100 10 126 400 冲突 次数 1 1 2 2 2 散列表(3分),冲突次数(2分) 5、 (1)不可能。 (1分) 反证法证明: 假设存在这棵二叉树,则从前序序列可知,1为二叉树的根节点。 同时,从中序序列可知,节点4位于该二叉树的左子树,节点2、3位于右子树。 对于这样一棵二叉树,按照前序遍历的规则,在其前序遍历序列中,节点4应该位于节点2、3之前,这与已知相矛盾。 因此,这棵二叉树不存在。 (2分) (2)(2分) 6、(参考)哈夫曼树如下: (2分) 哈夫曼编码分别为: (2分) a b c d e f g 11 101 011 1001 011 00 1000 平均编码长度=2×0.31+3×0.16+3×0.10+4×0.08+3×0.11+2×0.20+4×0.04=2.61(1分) 7、 插入排序是稳定的排序算法(1分),因为排序过程是建立在相邻元素比较的基础之上的(2分)。 最佳情况下,需要进行n-1次比较,移动0次元素(1分);最差情况下,需要比较n×(n-1)/2次,移动元素n×(n-1)/2次(1分)。 四、算法设计(共35分) 1、(10分) typedefstructListNode { intdata; StructListNode*next; }ListNode; BOOLCheckList(ListNode*L) { ListNode*a,*pa,*qa; qa=L->next->next; a=L->next; pa=L; if((pa==NULL)||(a==NULL)||(qa==NULL)) returnfalse; while(qa! =NULL) { if((qa->data+pa->data)! =(2*a->data)) returnfalse; qa=qa->next; a=a->next; pa=pa->next; } 2、(10分) typedefstructTreeNode { chardata; StructTreeNode*lchild; StructTreeNode*rchild; }ListNode; BOOLPreOrderChar(TreeNode*T) { if(T! =NULL) { if((T->data>=’0’)&&(T->data<=’9’)) cout< PreOrderChar(T->lchild); PreOrderChar(T->rchild); } } 3、(15分) typedefstructListNode { doublecost; intnum; StructListNode*next; }ListNode; BOOLAddTV(intm,doublec,ListNode*L) { ListNode*a,*p,*q; a=newListNode; a->cost=c; a->num=m; if(L->next==NULL) { a->next=L; L->next=a; } else { p=L; q=L->next; while((q->next! =L)&&(c>=q->cost)) { p=p->next; q=q->next; } if(q->next==L) { q->next=a; a->next=L; } else { p->next=a; a->next=q; } } } 课程名称: 数据结构-引言,算法分析,线性表 课程考试试卷 题 号 一 二 三 四 五 六 七 八 总分 阅卷 教师 得 分 …………………………………………………………………………………………………… 得 分 一、单选题(每小题2分,共10分,本题所给四个答案中只有一个是正确的) 1.下面程序段的时间复杂度是。 sum=0; for(i=0;i (A)O(n/2)(B)O(n)(C)O(log2n)(D)O(n2) 2.下面程序段的时间复杂度是。 sum=0; for(i=0;i (A)O(n/2)(B)O(n)(C)O(log2n)(D)O(n2) 3.在有n个元素组成的顺序表中,删除第i个元素(1≤i≤n)后,需要向前移动位置的元素个数为。 (A)n-i-1(B)n-i(C)n-i+1(D)i 4.在有n个元素组成的链表中,删除第i个元素(1≤i≤n)后,需要向前移动位置的元素个数为。 (A)0(B)1(C)i(D)n-i-1 5.已知单链表中指针q所指结点是指针p所指结点的直接前驱,若在*q与*p之间插入*s,则应执行操作? (A)s->link=p->link;p->link=s;(B)q->link=s;s->link=p; (C)p->link=s->link;s->link=p;(D)p->link=s;s->link=q; 得 分 二、填空题(每空1分,共5分) 1.从逻辑结构上讲,数据结构主要分为三大类: 线性结构结构和网状结构。 2.算法有效性的评价指标包括空间复杂度和。 3.堆栈的特点是_____,队列的特点是_________。 4.在顺序表示的线性表中,插入一个新的记录的时间复杂度为________。 得 分 三、判断题(若正确,在括号内打“”,否则打“×”;每题1分,共5分) 1.线性表中的所有元素都有一个前驱和一个后继。 () 2.线性表是一种抽象数据类型。 () 3.算法的时间复杂度等于算法运行的时间。 () 4.由于顺序表中的记录是连续存储的,所以适合数据经常增加或删除的应用。 () 5.队列是一种操作受限的线性表。 () 得 分 四、解析题(每题10分,共50分) 1.简述下列概念: 数据、数据元素、数据类型、数据结构、逻辑结构、存储结构、线性结构、非线性结构。 2.设n为正整数,利用大"O"记号,将下列程序段的执行时间表示为n的函数。 i=1;k=0; while(i {k=k+10*i;i++; } 3.设n个人围坐在一个圆桌周围,现在从第s个人开始报数,数到第m个人,让他出局;然后从出局的下一个人重新开始报数,数到第m个人,再让他出局,……,如此反复直到所有的人全部出局为止。 下面要解决的Josephus问题是: 对于任意给定的n,s和m,求出这n个人的出局序列。 请以n=9,s=1,m=5为例,人工模拟Josephus的求解过程以求得问题的解。 4.顺序表的插入和删除要求仍然保持各个元素原来的次序。 设在等概率情形下,对有127个元素的顺序表进行插入,平均需要移动多少个元素? 删除一个元素,又平均需要移动多少个元素? 5.铁路进行列车调度时,常把站台设计成栈式结构的站台,如右图所示。 试问: (1)设有编号为1,2,3,4,5,6的六辆列车,顺序开入栈式结构的站台,则可能的出栈序列有多少种? (2)若进站的六辆列车顺序如上所述,那么是否能够得到435612,325641,154623和135426的出站序列,如果不能,说明为什么不能;如果能,说明如何得到(即写出"进栈"或"出栈"的序列)。 得 分 五、算法设计题(每题10分,共30分) 1.已知数组存储了n个整数。 下面给出了顺序查找算法,如果数组中存在某个整数等于K,返回K在数组的下标位置;否则返回-1表示数组中没有整数K。 请在算法的空缺处填入适当内容,使之能够正常工作。 //值K如果在数组array中返回存储的下标位置,否则返回-1表示没有查找到。 intbinary(intR[],intn,intK){ inti; ①; while(②) { if(K==R[i])③;//在数组中 ④; } ⑤;//不在数组中 } 2.假设线性表中存储了一些整数,试编写算法找到最大值。 3.设计一个算法,实现一个单链表的就地逆置(不另外增加多余的辅助空间) 课程名称: 数据结构-树、排序 课程考试试卷 题 号 一 二 三 四 五 六 七 八 总分 阅卷 教师 得 分 …………………………………………………………………………………………………… 得 分 一、单选题(每小题2分,共10分,本题所给四个答案中只有一个是正确的) 1.将含有100个结点的完全二叉树从根结点开始顺序编号,根结点为第0号,其他结点自上而下,同一层从左向右连续编号,则编号最小的叶子结点的编号为。 (A)47(B)48(C)49(D)50 2.对一颗二叉排序树进行得到的结点序列是一个有序序列。 (A)前序周游(B)中序周游(C)后序周游(D)层次周游 3.设只含根结点的二叉树的高度为1,则高度为10的二叉树,至少有_________个结点。 (A)10(B)20(C)30(D)40 4.如果待排序序列中两个数据元素具有相同的值,在排序前后它们的相互位置发生颠倒,则称该排序算法是不稳定的。 下列四种排序方法中是稳定的排序方法。 (A)shell排序(B)快速排序 (C)归并排序(D)简单选择排序 5.若表R在排序前已按键值递增顺序排列,则算法的比较次数最少。 (A)直接插入排序 (B)快速排序 (C)归并排序 (D)选择排序 得 分 二、填空题(每空1分,共5分) 5.已知完全二叉树的第5层有8个结点(根结点在第1层),则其叶结点数是____________。 6.在有n个叶结点的Huffman树中,共有_____个结点。 7.采用________结构来存储和表示完全二叉树是最有效的。 8.当记录个数比较少且基本有序时,_____是最有效的排序方法。 9.内部排序问题的时间复杂度的下限是_。 得 分 三、判断题(若正确,在括号内打“”,否则打“×”;每题1分,共5分) 1.没有一个结点的二叉树称为空树。 () 2.一棵二叉树不能存储在一维数组中。 () 3.归并排序即适合内排序,也适合外排序。 () 4.快速排序在最差情况下的时间复杂度是O(n2),此时它的性能并不比冒泡排序更好。 () 5.删除二叉排序树中的一个结点,再重新插入进去,一定能得到原来的二叉排序树。 () 得 分 四、解析题(每题10分,共50分) 2.根据下面的字母/频率表构造一棵Huffman树,并给出各字母的Huffman编码。 A B C D E 1 4 9 16 25 3.已知一棵二叉树如下,请分别写出按前序、中序、后序和层次遍历时得到的结点序列。 3.请证明非空满二叉树的叶结点数等于其分支结点数加1。 4.请画出把如下的完全二叉树构建成最大值堆的过程。 5.采用直接插入排序算法,对关键字序列(49,38,65,97,76,13,27)按从小到大的次序进行排序,写出每趟排序的结果。 得 分 五、算法设计题(每题10分,共30分) 1.下面给出了冒泡排序的算法,请在算法的空缺处填入适当内容,使之能够正常工作,得到一个递增的序列。 Voidbubsort(ElemA[],intn){//数组R中有n个记录 inti,j;Elemt; for(i=0;①;i++){ for(intj=n-1;②;j--) {
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 答案