湖大数据结构及答案.docx

1、湖大数据结构及答案考试中心填写：湖 南 大 学 课 程 考 试 试 卷课程名称：数据结构 ；试卷编号：01 ；考试时间：120分钟年 月 日考 试 用（请将所有答案写在答题纸上）一、填空题。（20分）1. 已知单链表中指针q所指结点是指针p所指结点的直接前驱，若在*q与*p之间插入*s，则应执行（ ）语句。2. 将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是（ ）。3. 堆栈的特点是（ ）。4. 已知完全二叉树的第5层有4个结点(根结点在第1层), 则其叶结点数是（ ）。5. 在有n个叶结点的Huffman树中, 共有（ ）个结点。6. 若数据表中每个元素已距其最终位置不远,

2、则采用（ ）算法最省时间。7. 内部排序问题的时间复杂度的下限是（ ）。8. 对线性表进行折半查找时性能要能达到O(logn)，要求线性表必须（ ）。9. 如果具有n个顶点的图是一个环, 则它有（ ）棵生成树。10. 具有n个顶点的无向图最多有（ ）条边。二、请将下面的算法填写完整。（10分）下面算法的功能是：用基数排序法对n个无符号整数进行排序（递增），在算法空缺处填上适当语句或表达式，使得算法完整且正确。template void radix(elem a, elem b, int n, int k, int r, int cnt) /k为排序码的个数，r为基数 int i, j,x, m

3、=1; for (i=1; i=k; i+) /分别对第i个排序码进行分配 for ( j=0; jr; j+) cntj=0; /初始计数器为0 for (j=0; jn; 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、叉树，其中序序列可能是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，,结点中的元素为整型

5、数据，试编写算法，判断该单链表L中的元素，是否成等差关系，即各元素植依次为a1, a2, a3, a4,an判断ai+1-ai=ai- ai1是否成立，其中i满足1=i=n-1 2设一棵二叉树，结点结构为|lchild |data |rchild其中 data域中存放一个字符，设计一个算法按前叙遍历顺序，仅打印出data域为数字的字符（即0=datalink=s; s-link=p; (两个先后没有关系; link写成next也可以)2、13、后进先出（或LIFO、先进后出）4、105、2n-16、插入排序7、(n log n) （或n log n)）8、按关键码的值大小有序9、n10、n（n

6、1）/2二、程序填空题（10分）1、-cnt(aj/m)%r (3分)2、aj=bj (4分)3、m*r (3分)三、应用题（每小题5分，共35分）1、使用一个数组来存储两个栈，每个栈从各自的端点向中间延伸，从而减少空间的浪费。（3分），当两个栈顶指针相遇时（|top2top1|1），栈满（1分）；当栈顶指针为1或n时，栈空（1分）。（数组下标从0到n1）2、二叉查找树如下：（4分）平均查找长度（1122334252）/103.2 （1分）3、广度优先搜索生成树（1为起点）（2.5分）深度优先搜索生成树（2为起点）（2.5分）4、下标0123456789101112散列表03292003245

7、5810010126400冲突次数11222散列表 (3分)，冲突次数（2分）5、（1）不可能。 （1分）反证法证明：假设存在这棵二叉树，则从前序序列可知，1为二叉树的根节点。同时，从中序序列可知，节点4位于该二叉树的左子树，节点2、3位于右子树。对于这样一棵二叉树，按照前序遍历的规则，在其前序遍历序列中，节点4应该位于节点2、3之前，这与已知相矛盾。因此，这棵二叉树不存在。（2分）（2）（2分）6、（参考）哈夫曼树如下：（2分）哈夫曼编码分别为：（2分）abcdefg111010111001011001000平均编码长度20.3130.1630.1040.0830.1120.2040.042

8、.61 （1分）7、插入排序是稳定的排序算法（1分），因为排序过程是建立在相邻元素比较的基础之上的（2分）。最佳情况下，需要进行n1次比较，移动0次元素（1分）；最差情况下，需要比较n（n1）/2次，移动元素n（n1）/2次（1分）。四、算法设计（共35分）1、(10分)typedef struct ListNode int data; Struct ListNode * next; ListNode;BOOL CheckList(ListNode *L) ListNode *a, *pa, *qa;qa = L-next-next;a = L-next;pa = L; if(pa=NULL)

9、|( a=NULL)|( qa=NULL)return false;while ( qa != NULL) if (qa-data+pa-data)!=(2*a-data) )return false;qa = qa-next;a = a-next;pa = pa-next;2、(10分)typedef struct TreeNode char data; Struct TreeNode * lchild; Struct TreeNode * rchild; ListNode;BOOL PreOrderChar(TreeNode *T) if(T!=NULL)if(T-data = 0)&(T

10、-data = 9)coutdata lchild);PreOrderChar(T- rchild);3、(15分)typedef struct ListNode double cost; int num; Struct ListNode * next; ListNode;BOOL AddTV(int m, double c, ListNode *L) ListNode *a, *p, *q; a = new ListNode; a-cost = c; a-num = m; if(L-next=NULL) a-next = L; L-next = a;else p= L; q= L-next;

11、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;in*n;i+) sum+;（A）O(n/2) （B）O(n) （C）O(log2n) （D）O(n2)2下面程序段的时间

12、复杂度是 。sum = 0; for(i=0;ilink=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线性表中的所有元素都有一个前驱和

13、一个后继。 （ ）2线性表是一种抽象数据类型。 （ ）3算法的时间复杂度等于算法运行的时间。 （ ） 4由于顺序表中的记录是连续存储的，所以适合数据经常增加或删除的应用。 （ ）5队列是一种操作受限的线性表。 （ ）得分四、解析题（每题10分，共50分）1 简述下列概念：数据、数据元素、数据类型、数据结构、逻辑结构、存储结构、线性结构、非线性结构。2 设n为正整数，利用大O记号，将下列程序段的执行时间表示为n的函数。 i=1; k=0;while(in) k=k+10*i;i+;3设n个人围坐在一个圆桌周围，现在从第s个人开始报数，数到第m个人，让他出局；然后从出局的下一个人重新开始报数，数到

14、第m个人，再让他出局，如此反复直到所有的人全部出局为止。下面要解决的Josephus问题是：对于任意给定的n, s和m，求出这n个人的出局序列。请以n = 9, s = 1, m = 5为例，人工模拟Josephus的求解过程以求得问题的解。4顺序表的插入和删除要求仍然保持各个元素原来的次序。设在等概率情形下, 对有127个元素的顺序表进行插入, 平均需要移动多少个元素? 删除一个元素, 又平均需要移动多少个元素?5铁路进行列车调度时, 常把站台设计成栈式结构的站台，如右图所示。试问： (1) 设有编号为1,2,3,4,5,6的六辆列车, 顺序开入栈式结构的站台, 则可能的出栈序列有多少种?

15、(2) 若进站的六辆列车顺序如上所述, 那么是否能够得到435612, 325641, 154623和135426的出站序列, 如果不能, 说明为什么不能; 如果能, 说明如何得到(即写出进栈或出栈的序列)。得分五、算法设计题（每题10分，共30分）1已知数组存储了n个整数。下面给出了顺序查找算法，如果数组中存在某个整数等于K，返回K在数组的下标位置；否则返回1表示数组中没有整数K。请在算法的空缺处填入适当内容，使之能够正常工作。/值K如果在数组array中返回存储的下标位置，否则返回-1表示没有查找到。int binary(int R , int n, int K) int i; ; whi

16、le ( ) if (K = Ri) ; / 在数组中 ; ; / 不在数组中2假设线性表中存储了一些整数，试编写算法找到最大值。3设计一个算法，实现一个单链表的就地逆置（不另外增加多余的辅助空间）课程名称：数据结构- 树、排序课程考试试卷题号一二三四五六七八总分阅卷教师得分得分一、单选题（每小题 2 分，共10分，本题所给四个答案中只有一个是正确的）1将含有100个结点的完全二叉树从根结点开始顺序编号，根结点为第0号，其他结点自上而下，同一层从左向右连续编号，则编号最小的叶子结点的编号为 。（A）47 （B）48 （C）49 （D）502对一颗二叉排序树进行 得到的结点序列是一个有序序列。（

17、A）前序周游 （B）中序周游 （C）后序周游 （D）层次周游3设只含根结点的二叉树的高度为1，则高度为10的二叉树, 至少有_个结点。（A）10 （B）20 （C）30 （D）404如果待排序序列中两个数据元素具有相同的值，在排序前后它们的相互位置发生颠倒，则称该排序算法是不稳定的。下列四种排序方法中 是稳定的排序方法。（A）shell排序 （B）快速排序 （C）归并排序 （D）简单选择排序5若表R在排序前已按键值递增顺序排列，则 算法的比较次数最少。（A）直接插入排序 （B）快速排序 （C）归并排序 （D）选择排序得分二、填空题（每空 1 分，共5分）5. 已知完全二叉树的第5层有8个结点(

18、根结点在第1层), 则其叶结点数是_。6. 在有n个叶结点的Huffman树中, 共有_个结点。7. 采用_ _结构来存储和表示完全二叉树是最有效的。8. 当记录个数比较少且基本有序时，_是最有效的排序方法。9. 内部排序问题的时间复杂度的下限是 _ 。得分三、判断题（若正确，在括号内打“”，否则打“”；每题1分，共5分）1没有一个结点的二叉树称为空树。 （ ）2一棵二叉树不能存储在一维数组中。 （ ）3归并排序即适合内排序，也适合外排序。 （ ） 4快速排序在最差情况下的时间复杂度是O（n2），此时它的性能并不比冒泡排序更好。 （ ）5删除二叉排序树中的一个结点, 再重新插入进去, 一定能得

19、到原来的二叉排序树。 （ ）得分四、解析题（每题10分，共50分）2 根据下面的字母/频率表构造一棵Huffman树, 并给出各字母的Huffman编码。 ABCDE14916253 已知一棵二叉树如下，请分别写出按前序、中序、后序和层次遍历时得到的结点序列。3请证明非空满二叉树的叶结点数等于其分支结点数加1。4请画出把如下的完全二叉树构建成最大值堆的过程。5采用直接插入排序算法, 对关键字序列(49, 38, 65, 97, 76, 13, 27 )按从小到大的次序进行排序, 写出每趟排序的结果。得分五、算法设计题（每题10分，共30分）1下面给出了冒泡排序的算法，请在算法的空缺处填入适当内容，使之能够正常工作，得到一个递增的序列。Void bubsort(Elem A, int n) /数组R中有n个记录 int i,j; Elem t； for (i=0; ; i+) for (int j=n-1; ; j-) if (Aj arraymid) low = mid + 1; if (K = arraymid) ; if (K arraymid) ; ; / 不在数组中2试设计一个图的深度优先搜索算法。3试设计一个图的广度优先搜索算法。