湖大数据结构模拟卷.doc

Source： 30:10007/Course/Index.htm考试中心填写：湖 南 大 学 课 程 考 试 试 卷课程名称： 数据结构 ；试卷编号： A ；考试时间：120分钟年 月 日考 试 用专业班级：题 号一二三四五六七八九十总 分应得分10105030100实得分评分：评卷人得分一、填空题（每空 1分，共10分）1、在具有n个单元的循环队列中，队满时共有 个元素。2、假设在有序线性表a20上进行折半查找，则比较3次查找成功的结点数为 。3、对有序数组进行二分查找的时间复杂度为 。4、设栈S和队列Q的初始状态为空，元素E1、E2、E3、E4、E5和E6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出列的顺序为E2、E4、E3、E6、E5和E1，则栈S的容量至少应该是 。5、当待排序的记录数较大，排序码较随机且对稳定性不作要求时，宜采用 排序。6、一棵结点数为N的二叉树，其所有结点的度的总和是 。7、设一棵二叉树的前序遍历序列和中序遍历序列均为ABC，则该二叉树的后序遍历序列为 。8、散列法存储的基本思想是由 决定数据的存储地址。9、对不带权图进行 遍历可求得单源最短路径。10、设一个连通图G中有n个顶点e条边，则其最小生成树上有 条边。装订线（答题不得超过此线）学号：姓名： 第 1 页（共4 页）分二、单选题（每小题 1 分，共10分，本题所给四个答案中只有一个是正确的）1、若已知一个栈的入栈序列是1，2，3，n，其输出序列为p1，p2，p3，pn，若p1=n，则pi为（ ）（）i （）n=i （）n-i+1 （）不确定2、线性表若采用链式存储结构时，要求内存中可用存储单元的地址: （ ）（A）必须是连续的 （B）部分地址必须是连续的（C）一定是不连续的 （D）连续或不连续都可以3. 在n个结点的顺序表中，算法的时间复杂度是O（1）的操作是：（ ）（A） 访问第i个结点（1in）和求第i个结点的直接前驱（2in） （B） 在第i个结点后插入一个新结点（1in）（C） 删除第i个结点（1in）（D） 将n个结点从小到大排序4、具有n(n0)个结点的完全二叉树的深度为（ ）。() log2(n) () log2(n) () log2(n)+1 () log2(n)+15、有n个顶点e条边的无向图G,它的邻接表中的表结点总数是（ ）。 (A) 2n (B)n (C) 2e (D) e6、静态查找表与动态查找表二者的根本差别在于（ ）（A） 它们的逻辑结构不一样 （B） 施加在其上的操作不同（C） 所包含的数据元素的类型不一样（D） 存储实现不一样7、连通图G中有n个顶点,G的生成树是（ ）连通子图. (A)包含G的所有顶点 (B)包含G的所有边 (C)不必包含G的所有顶点 (D)必须包含G的所有顶点和所有的边8、设有5000个无序的元素，希望用最快的速度挑选出其中前50 个最大的元素，最好选用（ ） 法。（A） 冒泡排序 （B）快速排序 （C）堆排序 （D）基数排序9、下面的排序算法中，（ ）是不稳定的？ （A）希尔排序 （B）冒泡排序 （C）直接插入排序 （D）基数排序10、散列文件使用散列函数将记录的关键字值计算转化为记录的存放地址。因为散列函数不是一对一的关系，所以选择好的（ ）方法是散列文件的关键。（A）散列函数 （B） 除余法中的质数（C） 冲突处理 （D） 散列函数和冲突处理得分四、应用题（每小题 1 0分，共50分）1. 已知一棵二叉树的后序遍历的结果是ACDBHJIGFE, 中序遍历的结果是ABECDFGHIJ, 试画出这棵二叉树，并给出前序遍历的结果。2. 假设某AVL树的输入关键码的顺序为16, 3, 7, 11, 9, 26, 18, 14, 15，请给画出这棵AVL树，（要求画出插入和调整过程）。454542310 A1 B2 C3 D4 E5 F3已知一有向图的邻接表（如图），试写出:1） 从顶点A出发进行广度优先搜索所得到的广度优先生成树；2） 请对其进行拓扑排序，输出其拓扑排序序列。4. 排序的排序码序列为12, 16, 30, 28, 10, 18, 试分别写出使用以下排序方法按从小到大排列，每趟排序后的结果。(1) 快速排序(2) 冒泡排序5. 设散列表为HT13, 散列函数为 H (key) = key %13。用闭散列法解决冲突, 对下列关键码序列 12, 23, 45, 57, 20, 03, 78, 31, 15, 36 造表。(1) 采用线性探查法寻找下一个空位, 画出相应的散列表, (2) 计算等概率下搜索成功的平均搜索长度。得分五、算法设计题（共30分）1请根据函数f(n)的C语言代码，写出f(n)的值和推导过程，并给出算法的阶O(?)：（5分）int f(int n)int i, j, k, sum=0;for (i=1; ii-1; j-)for (k=1; kj+1; k+)sum+;printf(sum=%dn, sum)return (sum);2已知数组存储了n个整数。下面给出了顺序查找算法，如果数组中存在某个整数等于K，返回K在数组的下标位置；否则返回1表示数组中没有整数K。请在算法的空缺处填入适当内容，使之能够正常工作。（5分）/值K如果在数组array中返回存储的下标位置，否则返回-1表示没有查找到。int binary(int R , int n, int K) int i; ; while ( ) if (K = Ri) ; / 在数组中 ; ; / 不在数组中3假设队列中存储了n个整数，请利用堆栈以及堆栈的基本操作（出栈和入栈），把队列中的n个数进行逆置后仍然存储在同一个队列中。（10分）4编写求二叉树的叶结点数目的算法。（10分） 第4 页（共4 页数据结构期末考试参考答案（试卷A）一、填空题（每空1分，共10分）1、 n-1 2、 4 3、 O(logn) 4、 3 5、 快速 6、 N-1 7、 CBA 8、 关键字的值 9、 广度优先 10、 n-1 二、选择题（每小题1分，共10分）15 C D A C C610 B A C A D三、应用题（每小题10分，共50分）1.二叉树：5分前序遍历结果为：EBAFDCGIHJ （5分）2（10分）3：（1） 广度优先搜索生成树为：（5分）（2） 拓扑排序序列（有三个，答出一个给满分）：（5分）1：A，B，C，D，F，E2：A，B，D，C，F，E 3：A，D，B，C，F，E4：（1） 快速排序： （5分）第一趟，（10）12 （30，28，16，18）第二趟：（10）12 （18，28，16）30第三趟：（10）12 16 （18，28）30（2） 冒泡排序：，（5分）第一趟：12，16，28，10，18，30第二趟：12，16，10，18，28第三趟：12，10，16，18第四趟：10，12，16第五趟：10，125：(1) 哈希表为：（5分）012345678910111278150357452031233612(2) 等概率下平均查找成功长度=（8*1+1*2+1*4）/10=1.4 （5分）四、算法设计题（30分）1、（5分）第一层FOR循环判断n+1次，往下执行n次，第二层FOR执行次数为(n+(n-1)+(n-2)+1)，第三层循环受第一层循环和第二层循环的控制，其执行次数如下表：i = 1 2 3 nj=n n n n nj=n-1 n-1 n-1 n-1 j=3 3 3j=2 2 2j=1 1 (1+2+n)+(2+3+n)+n=n*n(n+1)/2-n(n*n-1)/6算法的阶为O（n3）2、（5分）（1）： i = 0；（2）: i n （或i n1）（3）: return i（4）: i+（5）: return 13、（10分）堆栈的数据结构（顺序表实现）template class Stack private: / Maximum size of stack int size; / Index for top element int top; / Array holding stack elements Elem *listArray;bool push(const Elem& item) if (top = size) return false; else listArraytop+ = item; return true; bool pop(Elem& it) if (top = 0) return false; else it = listArray-top; return true; 队列的数据结构（链表实现）template class Queue private: Link *front; Link *rear; int size; bool enqueue(const Elem& it) if (rear=NULL) front=rear=new Link(it, NULL); else rear-next = new Link(it, NULL); rear = rear-next; size+; return true;bool dequeue(Elem& it) if (size=0) return false; it=front-element; Link *ltemp=front; front = front-next; delete ltemp; if (front = NULL) rear = NULL; size-; return true; void reverse(Queue& Q, Stack& S) ELEM X;while (!Q.isEmpty() X = Q.dequeue();S.push(X);while (!S.isEmpty() X = S.pop();Q.enqueue(X);4、（10分）int leafnodenumber (bitree *root)if (root = = NULL) return 0;if (root-lchild = = NULL)&( root- rchild = = NULL) return 1;return (leafnodenumber (root-lchild) + leafnodenumber (root-rchild);考试中心填写：湖 南 大 学 课 程 考 试 试 卷课程名称：数据结构 ；试卷编号：01 ；考试时间：120分钟年 月 日考 试 用专业班级：题 号一二三四五六七八九十总 分应得分20103535100实得分评分：评卷人（请将所有答案写在答题纸上）一、填空题。（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 void radix(elem a, elem b, int n, int k, int r, int cnt) /k为排序码的个数，r为基数 int i, j,x, m=1; for (i=1; i=k; i+) /分别对第i个排序码进行分配 for ( j=0; jr; j+) cntj=0; /初始计数器为0 for (j=0; jn; j+)装订线（答题不得超过此线）学号：姓名： 第 1 页（共3 页） 第 2页（共3 页）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- 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、W(n log n) （或n log n)）8、按关键码的值大小有序9、n10、n（n1）/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散列表032920032455810010126400冲突次数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.61 （1分）7、插入排序是稳定的排序算法（1分），因为排序过程是建立在相邻元素比较的基础之上的（2分）。最佳情况下，需要进行n1次比较，移动0次元素（1分）；最差情况下，需要比较n（n1）/2次，移动元素n（n1）/2次（1分）。四、算法设计（共35分）1、(10分)typedef struct ListNodeint 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)|( 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 TreeNodechar data;Struct TreeNode * lchild;Struct TreeNode * rchild; ListNode;BOOL PreOrderChar(TreeNode *T) if(T!=NULL)if(T-data = 0)&(T-data = 9)coutdata lchild);PreOrderChar(T- rchild);3、(15分)typedef struct ListNodedouble 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;elsep= 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;elsep-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下面程序段的时间复杂度是 。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线性表中的所有元素都有一个前驱和一个后继。 （ ）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个人，让他出局；然后从出局的下一个人重新开始报数，数到第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表示没有查找到。int binary(int R , int n, int K) int i; ; while ( ) if (K = Ri) ; / 在数组中 ; ; / 不在数组中2假设线性表中存储了一些整数，试编写算法找到最大值。3设计一个算法，实现一个单链表的就地逆置（不另外增加多余的辅助空间）课程名称：数据结构- 树、排序课程考试试卷题号一二三四五六七八总分阅卷教师得分得分一、单选题（每小题 2 分，共10分，本题所给四个答案中只有一个是正确的）1将含有100个结点的完全二叉树从根结点开始顺序编号，根结点为第0号，其他结点自上而下，同一层从左向右连续编号，则编号最小的叶子结点的编号为 。（A）47（B）48（C）49（D）502对一颗二叉排序树进行 得到的结点序列是一个有序序列。（A）前序周游 （B）中序周游（C）后序周游（D）层次周游3设只含根结点的二叉树的高度为1，则高度为10的二叉树, 至少有_个结点。（A）10（B）20（C）30（D）404如果待排序