湖大数据结构及答案
- 格式:doc
- 大小:157.50 KB
- 文档页数:13
数据结构基础及深入及考试复习资料习题及实验参考答案见附录结论1、数据的逻辑结构是指数据元素之间的逻辑关系。
即从逻辑关系上描述数据,它与数据的存储无关,是独立于计算机的。
2、数据的物理结构亦称存储结构,是数据的逻辑结构在计算机存储器内的表示(或映像)。
它依赖于计算机。
存储结构可分为4大类:顺序、链式、索引、散列3、抽象数据类型:由用户定义,用以表示应用问题的数据模型。
它由基本的数据类型构成,并包括一组相关的服务(或称操作)。
它与数据类型实质上是一个概念,但其特征是使用与实现分离,实行封装和信息隐蔽(独立于计算机)。
4、算法:是对特定问题求解步骤的一种描述,它是指令的有限序列,是一系列输入转换为输出的计算步骤。
5、在数据结构中,从逻辑上可以把数据结构分成( C )A、动态结构和表态结构B、紧凑结构和非紧凑结构C、线性结构和非线性结构D、内部结构和外部结构6、算法的时间复杂度取决于( A )A、问题的规模B、待处理数据的初态C、问题的规模和待处理数据的初态线性表1、线性表的存储结构包括顺序存储结构和链式存储结构两种。
2、表长为n的顺序存储的线性表,当在任何位置上插入或删除一个元素的概率相等时,插入一个元素所需移动元素的平均次数为( E ),删除一个元素需要移动的元素的个数为( A )。
A、(n-1)/2B、nC、n+1D、n-1E、n/2F、(n+1)/2G、(n-2)/23、“线性表的逻辑顺序与存储顺序总是一致的。
”这个结论是( B )A、正确的B、错误的C、不一定,与具体的结构有关4、线性表采用链式存储结构时,要求内存中可用存储单元的地址( D )A、必须是连续的B、部分地址必须是连续的C一定是不连续的D连续或不连续都可以5、带头结点的单链表为空的判定条件是( B )A、head==NULLB、head->next==NULLC、head->next=headD、head!=NULL6、不带头结点的单链表head为空的判定条件是( A )A、head==NULLB、head->next==NULLC、head->next=headD、head!=NULL7、非空的循环单链表head的尾结点P满足( C )A、p->next==NULLB、p==NULLC、p->next==headD、p==head8、在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是(B )A、O(1)B、O(n)C、O(n2)D、O(nlog2n)9、在一个单链表中,若删除p所指结点的后继结点,则执行( A )A、p->next=p->next->next;B、p=p->next;p->next=p->next->next;C、p->next=p->next;D、p= p->next->next;10、在一个单链表中,若在p所指结点之后插入s所指结点,则执行( B )A、s->next=p;p->next=s;B、s->next=p->next;p->next=s;C、s->next=p->next;p=s;D、p->next=s;s->next=p;11、在一个单链表中,已知q是p的前趋结点,若在q和p之间插入结点s,则执行(C )A、s->next=p->next;p->next=s;B、p->next=s->next;s->next=p;C、q->next=s;s->next=p;D、p->next=s;s->next=q;12、在线性结构中,第一个结点没有前趋结点,其余每个结点有且只有 1 个前趋结点。
大数据结构试题及答案高中一、选择题1. 在大数据结构中,以下哪个算法是用于搜索数据的?A. 排序算法B. 哈希表C. 堆排序D. 二分查找答案:D2. 以下哪个数据结构适合于实现大数据的快速访问?A. 链表B. 数组C. 树D. 图答案:B3. 在大数据结构中,以下哪种数据结构可以有效地支持数据的插入和删除操作?A. 栈B. 队列C. 哈希表D. 双向链表答案:D二、简答题1. 简述大数据结构中哈希表的基本原理。
答:哈希表是一种通过哈希函数将输入(例如字符串或者数字)转换为索引值,从而在表中存储和检索数据的数据结构。
它利用数组的快速访问特性,通过哈希函数将键映射到数组的一个位置来访问数据,从而实现快速的数据查找、插入和删除。
2. 描述大数据结构中二叉树的遍历方法。
答:二叉树的遍历方法主要有前序遍历、中序遍历和后序遍历三种。
前序遍历的顺序是先访问根节点,然后递归遍历左子树,最后递归遍历右子树。
中序遍历的顺序是先递归遍历左子树,然后访问根节点,最后递归遍历右子树。
后序遍历的顺序是先递归遍历左子树,然后递归遍历右子树,最后访问根节点。
三、计算题1. 给定一个大数据集,使用二分查找算法找出数据集中的特定值。
假设数据集已经排序。
答:二分查找算法的基本步骤如下:- 确定数据集的中间位置。
- 比较中间位置的值与目标值。
- 如果目标值等于中间位置的值,则查找成功。
- 如果目标值小于中间位置的值,则在左半部分继续查找。
- 如果目标值大于中间位置的值,则在右半部分继续查找。
- 重复以上步骤,直到找到目标值或搜索范围为空。
四、论述题1. 论述大数据结构在现代信息技术中的应用及其重要性。
答:大数据结构在现代信息技术中扮演着至关重要的角色。
随着数据量的爆炸性增长,如何高效地存储、管理和分析这些数据成为了一个挑战。
大数据结构提供了多种高效的数据存储和访问方式,如哈希表、树结构、图结构等,它们能够支持快速的数据检索、插入和删除操作。
数据结构(c语言版)课后习题答案完整版数据结构(C语言版)课后习题答案完整版一、数据结构概述数据结构是计算机科学中一个重要的概念,用来组织和存储数据,使之可以高效地访问和操作。
在C语言中,我们可以使用不同的数据结构来解决各种问题。
本文将提供完整版本的C语言数据结构的课后习题答案。
二、顺序表1. 顺序表的定义和基本操作顺序表是一种线性表,其中的元素在物理内存中连续地存储。
在C 语言中,我们可以通过定义结构体和使用指针来实现顺序表。
以下是顺序表的一些基本操作的答案:(1)初始化顺序表```ctypedef struct{int data[MAX_SIZE];int length;} SeqList;void InitList(SeqList *L){L->length = 0;}```(2)插入元素到顺序表中```cbool Insert(SeqList *L, int pos, int elem){if(L->length == MAX_SIZE){return false; // 顺序表已满}if(pos < 1 || pos > L->length + 1){return false; // 位置不合法}for(int i = L->length; i >= pos; i--){L->data[i] = L->data[i-1]; // 向后移动元素 }L->data[pos-1] = elem;L->length++;return true;}```(3)删除顺序表中的元素```cbool Delete(SeqList *L, int pos){if(pos < 1 || pos > L->length){return false; // 位置不合法}for(int i = pos; i < L->length; i++){L->data[i-1] = L->data[i]; // 向前移动元素 }L->length--;return true;}```(4)查找顺序表中的元素```cint Search(SeqList L, int elem){for(int i = 0; i < L.length; i++){if(L.data[i] == elem){return i + 1; // 找到元素,返回位置 }}return -1; // 未找到元素}```2. 顺序表习题解答(1)逆置顺序表```cvoid Reverse(SeqList *L){for(int i = 0; i < L->length / 2; i++){int temp = L->data[i];L->data[i] = L->data[L->length - 1 - i]; L->data[L->length - 1 - i] = temp;}}```(2)顺序表元素去重```cvoid RemoveDuplicates(SeqList *L){for(int i = 0; i < L->length; i++){for(int j = i + 1; j < L->length; j++){if(L->data[i] == L->data[j]){Delete(L, j + 1);j--;}}}}```三、链表1. 单链表单链表是一种常见的链式存储结构,每个节点包含数据和指向下一个节点的指针。
数据结构(C语言版)(第2版)课后习题答案李冬梅2015.3目录第1章绪论 (1)第2章线性表 (5)第3章栈和队列 (13)第4章串、数组和广义表 (26)第5章树和二叉树 (33)第6章图 (42)第7章查找 (54)第8章排序 (65)第1章绪论1.简述下列概念:数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。
答案:数据:是客观事物的符号表示,指所有能输入到计算机中并被计算机程序处理的符号的总称。
如数学计算中用到的整数和实数,文本编辑所用到的字符串,多媒体程序处理的图形、图像、声音、动画等通过特殊编码定义后的数据。
数据元素:是数据的基本单位,在计算机中通常作为一个整体进行考虑和处理。
在有些情况下,数据元素也称为元素、结点、记录等。
数据元素用于完整地描述一个对象,如一个学生记录,树中棋盘的一个格局(状态)、图中的一个顶点等。
数据项:是组成数据元素的、有独立含义的、不可分割的最小单位。
例如,学生基本信息表中的学号、姓名、性别等都是数据项。
数据对象:是性质相同的数据元素的集合,是数据的一个子集。
例如:整数数据对象是集合N={0,±1,±2,…},字母字符数据对象是集合C={‘A’,‘B’,…,‘Z’,‘a’,‘b’,…,‘z’},学生基本信息表也可是一个数据对象。
数据结构:是相互之间存在一种或多种特定关系的数据元素的集合。
换句话说,数据结构是带“结构”的数据元素的集合,“结构”就是指数据元素之间存在的关系。
逻辑结构:从逻辑关系上描述数据,它与数据的存储无关,是独立于计算机的。
因此,数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。
存储结构:数据对象在计算机中的存储表示,也称为物理结构。
抽象数据类型:由用户定义的,表示应用问题的数学模型,以及定义在这个模型上的一组操作的总称。
具体包括三部分:数据对象、数据对象上关系的集合和对数据对象的基本操作的集合。
数据结构基础及深入及考试复习资料习题及实验参考答案见附录结论1、数据的逻辑结构是指数据元素之间的逻辑关系.即从逻辑关系上描述数据,它与数据的存储无关,是独立于计算机的。
2、数据的物理结构亦称存储结构,是数据的逻辑结构在计算机存储器内的表示(或映像)。
它依赖于计算机。
存储结构可分为4大类:顺序、链式、索引、散列3、抽象数据类型:由用户定义,用以表示应用问题的数据模型。
它由基本的数据类型构成,并包括一组相关的服务(或称操作)。
它与数据类型实质上是一个概念,但其特征是使用与实现分离,实行封装和信息隐蔽(独立于计算机).4、算法:是对特定问题求解步骤的一种描述,它是指令的有限序列,是一系列输入转换为输出的计算步骤。
5、在数据结构中,从逻辑上可以把数据结构分成( C )A、动态结构和表态结构B、紧凑结构和非紧凑结构C、线性结构和非线性结构D、内部结构和外部结构6、算法的时间复杂度取决于( A )A、问题的规模B、待处理数据的初态C、问题的规模和待处理数据的初态线性表1、线性表的存储结构包括顺序存储结构和链式存储结构两种.2、表长为n的顺序存储的线性表,当在任何位置上插入或删除一个元素的概率相等时,插入一个元素所需移动元素的平均次数为( E ),删除一个元素需要移动的元素的个数为( A )。
A、(n—1)/2B、nC、n+1D、n-1E、n/2F、(n+1)/2G、(n-2)/23、“线性表的逻辑顺序与存储顺序总是一致的."这个结论是( B )A、正确的B、错误的C、不一定,与具体的结构有关4、线性表采用链式存储结构时,要求内存中可用存储单元的地址( D )A、必须是连续的B、部分地址必须是连续的C一定是不连续的D连续或不连续都可以5、带头结点的单链表为空的判定条件是( B )A、head==NULLB、head—>next==NULLC、head->next=headD、head!=NULL6、不带头结点的单链表head为空的判定条件是( A )A、head==NULLB、head-〉next==NULLC、head—>next=headD、head!=NULL7、非空的循环单链表head的尾结点P满足( C )A、p—>next==NULLB、p==NULLC、p->next==headD、p==head8、在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是( B )A、O(1)B、O(n)C、O(n2)D、O(nlog2n)9、在一个单链表中,若删除p所指结点的后继结点,则执行( A )A、p-〉next=p—〉next—>next;B、p=p—〉next;p-〉next=p—>next-〉next;C、p—〉next=p-〉next;D、p= p—>next->next;10、在一个单链表中,若在p所指结点之后插入s所指结点,则执行( B )A、s—>next=p;p-〉next=s;B、s—〉next=p—>next;p-〉next=s;C、s->next=p—〉next;p=s;D、p->next=s;s->next=p;11、在一个单链表中,已知q是p的前趋结点,若在q和p之间插入结点s,则执行( C )A、s—>next=p-〉next;p—>next=s;B、p->next=s—>next;s—〉next=p;C、q-〉next=s;s-〉next=p;D、p-〉next=s;s-〉next=q;12、在线性结构中,第一个结点没有前趋结点,其余每个结点有且只有 1 个前趋结点。
2022年湖北民族大学数据科学与大数据技术专业《计算机系统结构》科目期末试卷A(有答案)一、选择题1、目前,MO由()实现,M1用()实现,M2至M5大多用()实现。
A.软件,固件,硬件B.固件,软件,硬件C.硬件,软件,固件D.硬件,固件,软件2、下列说法中不正确的是( )A.软件设计费用比软件重复生产费用高B.硬件功能只需实现一次,而软件功能可能要多次重复实现C.硬件的生产费用比软件的生产费用高D.硬件的设计费用比软件的设计费用低3、计算机组成设计不考虑()A.专用部件设置B.功能部件的集成度C.控制机构的组成D.缓冲技术4、最能确保提高虚拟存贮器访主存的命中率的改进途径是( )A.增大辅存容量B.采用FIFO替换算法并增大页面C.改用LRU替换算法并增大页面D.改用LRU替换算法并增大页面数5、静态流水线是指( )A.只有一种功能的流水线B.功能不能改变的流水线C.同时只能完成一种功能的多功能流水线D.可同时执行多种功能的流水线6、多处理机的各自独立型操作系统()。
A.要求管理程序不必是可再入的B.适合于紧耦合多处理机C.工作负荷较平衡D.有较高的可靠性7、直接执行微指令的是( )A.汇编程序B.编译程序C.硬件D.微指令程序8、非线性流水线是指( )A.一次运算中使用流水线中的多个功能段B.一次运算中要多次使用流水线中的某些功能段C.流水线中某些功能段在各次运算中的作用不同D.流水线的各个功能段在各种运算中有不同的组合9、在流水机器中,全局性相关是指( )。
A.先写后读相关B.先读后写相关C.指令相关D.由转移指令引起的相关10、计算机中优化使用的操作码编码方法是( )。
(书上为扩展编码法)A哈夫曼编码B ASCII码C BCD码D扩展操作码二、填空题11、页面替换是发生于页面失效,同时又发生________的时候。
12、Cache存贮器对应用程序员是________的。
对系统程序员是________的(填“透明”或“不透明”)13、评价地址码个数不同的4种指令的优缺点的主要标准是________和________14、在Cache存贮器中,CPU每次写Cache的同时,也写入主存,称这种更新主存块内容的方法为________法。
数据结构(C语言版)习题参考答案数据结构(C语言版)习题参考答案1. 数据结构简介数据结构是计算机科学中重要的概念之一,它关注如何组织和存储数据,以便有效地进行访问和操作。
C语言是一种广泛应用于数据结构实现的编程语言。
本文将提供一些常见数据结构习题的参考答案,帮助读者理解和掌握数据结构的基本概念与实现。
2. 数组数组是一种线性结构,存储具有相同数据类型的元素。
以下是一些数组习题的参考答案:2.1 统计数组中某个元素出现的次数```int countOccurrences(int arr[], int n, int x) {int count = 0;for (int i = 0; i < n; i++) {if (arr[i] == x) {count++;}}return count;}```2.2 查找数组中的最大值和最小值```void findMinMax(int arr[], int n, int* min, int* max) { *min = arr[0];*max = arr[0];for (int i = 1; i < n; i++) {if (arr[i] < *min) {*min = arr[i];}if (arr[i] > *max) {*max = arr[i];}}}```3. 链表链表是一种动态数据结构,每个节点包含数据和指向下一个节点的指针。
以下是一些链表习题的参考答案:3.1 反转链表```Node* reverseLinkedList(Node* head) {Node* prev = NULL;Node* curr = head;while (curr != NULL) {Node* next = curr->next;curr->next = prev;prev = curr;curr = next;}return prev;}```3.2 合并两个有序链表```Node* mergeLists(Node* list1, Node* list2) {if (list1 == NULL) {return list2;}if (list2 == NULL) {return list1;}if (list1->data < list2->data) {list1->next = mergeLists(list1->next, list2);return list1;} else {list2->next = mergeLists(list1, list2->next);return list2;}}```4. 栈和队列栈和队列是两种重要的线性数据结构,栈支持后进先出(LIFO),队列支持先进先出(FIFO)。
数据结构试题及答案 一.单项选择题(3) 与数据元素本身的形式、容、相对位萱、个数无关的是数据的()oA )存储结构B )逻辑结构C )算法D )操作(4) 从逻辑上可以把数据结构分为()两大类。
A )动态结构、静态结构 C )线性结构、非线性结构 (5)下列叙述中正确的是()。
A ) 一个逻辑数据结构只能有一种存储结构B )数据的逻辑结构属于线性结构,存储结构属于非线性结构C ) 一个逻辑数据结构可以有多种存储结构,且各种存储结构不影响数据处理的效率D ) 一个逻辑数据结构可以有多种存储结构,且各种存储结构影响数据处理的效率(9)程序段如下:sum=0; for(i=l;i<=n;i++)(1) 一个算法应该是()oA )程序C )要满足五个基本属性 ⑵算法指的是()。
A )计算机程序C )排序算法 B )问题求解步骤的描述D ) A 和 CB )解决问题的计算方法D )解决问题的有限运算序列。
B )顺序结构、链式结构 D )初等结构、构造型结构(6) 数据的基本单位是()A )数据项B )数据类型(7) 下列程序的时间复杂度为()i=0; s 二0;while(s<n ) {i++;s=s+i; }A ) O (、斤)B ) O (厉)(8) 下列程序段的渐进时间复杂度为(for ( int i=];j<=n;i++) for ( int j=l;j<= m; j++)C )数据元素D )数据变量C)O (n)D) O (n 2))oC) O(m*n) D) (m+n)for(j=l;j<=n;j++)sum++;其中n 为正整数,则最后一行的语句频度在最坏情况下是( )A) O(n)B) O(nlogn)(10) 在下面的程序段中,对X 的赋值语句的频度为(for (i=l;i >二n; i++)for (j=l; j >二n; j++)x:二 x+1;for(i=l;i<m;i++) for(j=0;j<=i;j++) s+=j; m(m-\)B) — (14)若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素,则最节 省运算时间的存储方式是( )。
数据结构考研真题及其答案数据结构是计算机科学与技术专业考研中的重要科目之一,它对于培养学生的程序设计和算法分析能力具有关键作用。
以下将为大家呈现一些典型的数据结构考研真题,并提供详细的答案解析。
一、选择题1、若一个栈的输入序列为 1, 2, 3, 4, 5,不可能得到的输出序列是()A 2, 3, 4, 1, 5B 5, 4, 3, 2, 1C 1, 5, 4, 3, 2D 3, 4, 2, 5, 1答案:C解析:栈的特点是“后进先出”。
对于选项 C,先输出 1,意味着 2、3、4、5 都已入栈,此时栈顶元素为 5,不可能接着输出 5 之后就输出4。
2、已知一棵二叉树的先序遍历序列为 ABCDEFG,中序遍历序列为 CBDAEGF,则其后序遍历序列为()A CDBAFGEB CDBGFEAC CDBAGFED BCDAFGE答案:B解析:先根据先序和中序遍历序列构建二叉树。
先序遍历中第一个节点 A 为根节点,在中序遍历中找到 A,其左边的 CBD 为左子树,右边的 EGF 为右子树。
同样的方法确定左子树和右子树的结构。
然后按照“左子树右子树根节点”的顺序得到后序遍历序列 CDBGFEA。
3、对于一个具有 n 个顶点的无向图,若采用邻接矩阵表示,则该矩阵的非零元素个数为()A n(n 1) / 2B n(n + 1) / 2C n(n 1)D n(n + 1)答案:A解析:无向图的邻接矩阵是对称的。
对于顶点 i 和 j(i ≠ j),若它们之间有边,则矩阵中对应位置为 1,共有 n(n 1) / 2 对不同的顶点对,所以非零元素个数为 n(n 1) / 2 。
二、简答题1、简述冒泡排序的基本思想,并分析其时间复杂度和空间复杂度。
答案:冒泡排序的基本思想是通过相邻元素的两两比较和交换,将最大(或最小)的元素逐步“浮”到数组的一端。
时间复杂度:在最坏情况下,即数组完全逆序,需要进行 n 1 轮比较,每轮比较 n i 次(i 为轮数,从 1 到 n 1),所以总的比较次数为n(n 1) / 2,时间复杂度为 O(n^2)。
杭州电子科技大学数据结构数据结构试题及答案一、选择题1. 下面哪一个不是线性结构的特点?()A. 有且只有一个根结点B. 每个结点最多有一个前驱,最多有一个后继C. 至少有一个结点D. 结构中任意两个结点都可以相邻答案:D解析:线性结构的特点包括有且只有一个根结点,每个结点最多有一个前驱,最多有一个后继,至少有一个结点。
而结构中任意两个结点都可以相邻并不是线性结构的特征。
2. 下面关于栈的叙述中,正确的是()A. 栈是一种先进先出的线性表B. 栈是一种后进先出的线性表C. 栈是一种随机存取的线性表D. 栈是一种非线性结构答案:B解析:栈是一种后进先出的线性表,即最后进入的元素最先被删除。
二、填空题3. 一个栈的初始状态为空。
首先将元素5、3、2依次进栈,然后退栈一次,再进栈一个元素6,然后再退栈三次,此时栈顶元素的值为______。
答案:2解析:元素进栈的顺序是5、3、2,退栈一次后栈顶元素是3,再进栈一个元素6,栈顶元素变为6,退栈三次后,栈顶元素是2。
4. 设栈S和队列Q的初始状态都为空。
元素a、b、c、d、e依次进栈S,然后再依次出栈,并将出栈的元素放入队列Q 中,则队列Q的元素顺序是______。
答案:e d c b a解析:元素a、b、c、d、e依次进栈后,出栈顺序是e、d、c、b、a,因此队列Q的元素顺序也是e、d、c、b、a。
三、判断题5. 在链表中,存储结点包含数据域和指针域两部分。
()答案:正确解析:链表中的每个存储结点确实包含数据域和指针域两部分,其中数据域存储元素值,指针域存储下一个结点的地址。
6. 二分查找法适用于顺序存储的有序表。
()答案:正确解析:二分查找法只适用于顺序存储的有序表,因为它是通过比较中间元素与目标值的大小来逐步缩小查找范围的。
四、应用题7. 设有一个长度为12的线性表,元素依次为(a1, a2, a3, ..., a12),采用二分查找法查找元素a7,请写出查找过程。
考试中心填写: 湖 南 大 学 课 程 考 试 试 卷
课程名称:数据结构 ;试卷编号: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 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; jfor (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、(n log n) (或n log n)) 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分)
46
4588397010110586634
平均查找长度=(1×1+2×2+3×3+4×2+5×2)/10=3.2 (1分)
3、 广度优先搜索生成树(1为起点)(2.5分)
1
2
43
5 深度优先搜索生成树(2为起点)(2.5分)
1
2
43
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分)
1
23456798 6、(参考)哈夫曼树如下:(2分) 1
0.410.590.200.21
0.100.110.280.310.120.160.040.08
fa
bcde
g 哈夫曼编码分别为:(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分) 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)||( 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->data <= ’9’)) cout<< T->data <<’ ’; PreOrderChar(T-> 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; 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; } } }
课程名称: 数据结构 - 引言,算法分析,线性表 课程考试试卷 题 号 一 二 三 四 五 六 七 八 总分 阅卷 教师