2011澳门特别行政区数据结构基础试题及答案
- 格式:pdf
- 大小:79.07 KB
- 文档页数:2
1、#define maxsize 栈空间容量void InOutS(int s[maxsize])//s是元素为整数的栈,本算法进行入栈和退栈操作。
{int top=0; //top为栈顶指针,定义top=0时为栈空。
for(i=1; i<=n; i++) //n个整数序列作处理。
{scanf(“%d”,&x); //从键盘读入整数序列。
if(x!=-1) // 读入的整数不等于-1时入栈。
if(top==maxsize-1){printf(“栈满\n”);exit(0);}else s[++top]=x; //x入栈。
else //读入的整数等于-1时退栈。
{if(top==0){printf(“栈空\n”);exit(0);}else printf(“出栈元素是%d\n”,s[top--]);}}}//算法结2、给定n个村庄之间的交通图,若村庄i和j之间有道路,则将顶点i和j用边连接,边上的Wij表示这条道路的长度,现在要从这n个村庄中选择一个村庄建一所医院,问这所医院应建在哪个村庄,才能使离医院最远的村庄到医院的路程最短?试设计一个解答上述问题的算法,并应用该算法解答如图所示的实例。
(20分)3、本题要求建立有序的循环链表。
从头到尾扫描数组A,取出A[i](0<=i<n),然后到链表中去查找值为A[i]的结点,若查找失败,则插入。
LinkedList creat(ElemType A[],int n)//由含n个数据的数组A生成循环链表,要求链表有序并且无值重复结点{LinkedList h;h=(LinkedList)malloc(sizeof(LNode));//申请结点h->next=h; //形成空循环链表for(i=0;i<n;i++){pre=h;p=h->next;while(p!=h && p->data<A[i]){pre=p; p=p->next;} //查找A[i]的插入位置if(p==h || p->data!=A[i]) //重复数据不再输入{s=(LinkedList)malloc(sizeof(LNode));s->data=A[i]; pre->next=s; s->next=p;//将结点s链入链表中}}//forreturn(h);}算法结束4、设t是给定的一棵二叉树,下面的递归程序count(t)用于求得:二叉树t中具有非空的左,右两个儿子的结点个数N2;只有非空左儿子的个数NL;只有非空右儿子的结点个数NR和叶子结点个数N0。
一、一、单选题(每题2 分,共20分)1. 1. 栈和队列的共同特点是( )。
A.只允许在端点处插入和删除元素B.都是先进后出C.都是先进先出D.没有共同点2. 2. 用链接方式存储的队列,在进行插入运算时( ).A. 仅修改头指针B. 头、尾指针都要修改C. 仅修改尾指针D.头、尾指针可能都要修改3. 3. 以下数据结构中哪一个是非线性结构?( )A. 队列B. 栈C. 线性表D. 二叉树4. 4. 设有一个二维数组A[m][n],假设A[0][0]存放位置在644(10),A[2][2]存放位置在676(10),每个元素占一个空间,问A[3][3](10)存放在什么位置?脚注(10)表示用10进制表示。
A.688 B.678 C.692 D.6965. 5. 树最适合用来表示( )。
A.有序数据元素B.无序数据元素C.元素之间具有分支层次关系的数据D.元素之间无联系的数据6. 6. 二叉树的第k层的结点数最多为( ).A.2k-1 B.2K+1 C.2K-1 D. 2k-17.7. 若有18个元素的有序表存放在一维数组A[19]中,第一个元素放A[1]中,现进行二分查找,则查找A[3]的比较序列的下标依次为( )A. 1,2,3B. 9,5,2,3C. 9,5,3D. 9,4,2,38.8. 对n个记录的文件进行快速排序,所需要的辅助存储空间大致为A. O(1)B. O(n)C. O(1og2n)D. O(n2)9.9. 对于线性表(7,34,55,25,64,46,20,10)进行散列存储时,若选用H(K)=K %9作为散列函数,则散列地址为1的元素有()个,A.1 B.2 C.3 D.410.10. 设有6个结点的无向图,该图至少应有( )条边才能确保是一个连通图。
A.5B.6C.7D.8二、二、填空题(每空1分,共26分)1. 1. 通常从四个方面评价算法的质量:_________、_________、_________和_________。
第1 章绪论1.简述下列概念:数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。
答案:数据:是客观事物的符号表示,指所有能输入到计算机中并被计算机程序处理的符号的总称。
如数学计算中用到的整数和实数,文本编辑所用到的字符串,多媒体程序处理的图形、图像、声音、动画等通过特殊编码定义后的数据。
数据元素:是数据的基本单位,在计算机中通常作为一个整体进行考虑和处理。
在有些情况下,数据元素也称为元素、结点、记录等。
数据元素用于完整地描述一个对象,如一个学生记录,树中棋盘的一个格局(状态)、图中的一个顶点等。
数据项:是组成数据元素的、有独立含义的、不可分割的最小单位。
例如,学生基本信息表中的学号、姓名、性别等都是数据项。
数据对象:是性质相同的数据元素的集合,是数据的一个子集。
例如:整数数据对象是集合N={0,±1,±2,… },字母字符数据对象是集合C={‘A’,‘B’,… ,‘Z’,‘a’,‘b’,…,‘z’},学生基本信息表也可是一个数据对象。
数据结构:是相互之间存在一种或多种特定关系的数据元素的集合。
换句话说,数据结构是带“结构”的数据元素的集合,“结构”就是指数据元素之间存在的关系。
逻辑结构:从逻辑关系上描述数据,它与数据的存储无关,是独立于计算机的。
因此,数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。
存储结构:数据对象在计算机中的存储表示,也称为物理结构。
抽象数据类型:由用户定义的,表示应用问题的数学模型,以及定义在这个模型上的一组操作的总称。
具体包括三部分:数据对象、数据对象上关系的集合和对数据对象的基本操作的集合。
2.试举一个数据结构的例子,叙述其逻辑结构和存储结构两方面的含义和相互关系。
答案:例如有一张学生基本信息表,包括学生的学号、姓名、性别、籍贯、专业等。
每个学生基本信息记录对应一个数据元素,学生记录按顺序号排列,形成了学生基本信息记录的线性序列。
数据结构考试试题及答案数据结构考试试题及答案数据结构是计算机科学中非常重要的一门课程,它涉及到了计算机程序设计中的数据组织、存储和管理等方面。
在学习数据结构的过程中,掌握基本的数据结构类型、操作和算法是非常重要的。
为了帮助大家更好地掌握数据结构,下面将提供一些常见的数据结构考试试题及答案。
一、选择题1. 下面哪个不是线性数据结构?A. 数组B. 链表C. 栈D. 队列答案:D. 队列2. 下面哪个数据结构可以实现先进先出(FIFO)的操作?A. 栈B. 队列C. 链表D. 树答案:B. 队列3. 下面哪个数据结构可以实现后进先出(LIFO)的操作?A. 栈B. 队列C. 链表D. 树答案:A. 栈4. 下面哪个数据结构可以实现快速查找和插入操作?A. 数组B. 链表C. 栈D. 队列答案:A. 数组5. 下面哪个数据结构可以实现快速查找和删除操作?A. 数组B. 链表C. 栈D. 队列答案:B. 链表二、填空题1. 请写出数组的插入操作的时间复杂度。
答案:O(n)2. 请写出链表的删除操作的时间复杂度。
答案:O(1)3. 请写出栈的出栈操作的时间复杂度。
答案:O(1)4. 请写出队列的入队操作的时间复杂度。
答案:O(1)5. 请写出二叉搜索树的查找操作的时间复杂度。
答案:O(log n)三、简答题1. 什么是数据结构?答案:数据结构是计算机存储、组织数据的方式,它定义了数据的逻辑结构和存储结构,以及对数据进行操作的算法。
2. 请解释什么是时间复杂度和空间复杂度。
答案:时间复杂度是衡量算法执行时间的度量,它表示算法执行所需的时间与问题规模之间的关系。
空间复杂度是衡量算法所需的存储空间的度量,它表示算法所需的存储空间与问题规模之间的关系。
3. 请解释什么是递归算法,并给出一个例子。
答案:递归算法是一种自己调用自己的算法。
一个经典的例子是计算斐波那契数列的第n项。
代码如下:```int fibonacci(int n) {if (n <= 1) {return n;}return fibonacci(n-1) + fibonacci(n-2);}```以上就是一些常见的数据结构考试试题及答案。
数据结构试卷及答案一、选择题(共30题,每题2分,共60分)1. 数据结构是解决什么问题的基础?A. 数据的存储和组织问题B. 数据的计算和分析问题C. 数据的传输和交换问题D. 数据的加密和解密问题2. 下列哪种数据结构可以实现后进先出(LIFO)的特性?A. 栈B. 队列C. 链表D. 树3. 哪种数据结构可以快速地查找和插入元素?A. 数组B. 链表C. 栈D. 队列4. 在二叉树中,每个节点最多有几个子节点?A. 0B. 1C. 2D. 35. 下列哪种排序算法的时间复杂度是O(nlogn)?A. 冒泡排序B. 插入排序C. 快速排序D. 选择排序...二、填空题(共10题,每题4分,共40分)1. 数据结构中,关系密切的元素组成的集合称为________。
2. 对一个链表进行插入或删除操作,时间复杂度是________。
3. 在树结构中,没有子节点的节点称为________。
4. 广度优先搜索(BFS)使用的数据结构是________。
5. 在堆排序中,堆的建立时间复杂度是________。
...三、简答题(共5题,每题10分,共50分)1. 请简要解释什么是数组,并说明其在数据结构中的优势和限制。
2. 请解释栈和队列这两种数据结构的特点和应用场景,并给出一个实际的例子。
3. 请解释什么是二叉树,给出一个二叉树的例子,并说明其遍历的方法。
4. 请简要解释图的概念,并说明图的遍历方法。
5. 请解释并比较快速排序和归并排序两种常用的排序算法,包括它们的时间复杂度和空间复杂度。
...答案解析:一、选择题答案:1. A2. A3. B4. C5. C二、填空题答案:1. 集合2. O(1)3. 叶节点4. 队列5. O(n)三、简答题答案:1. 数组是一种连续存储数据的结构,其优势是在已知索引的情况下能快速访问元素,但限制在插入和删除操作上效率较低。
2. 栈是一种后进先出(LIFO)的数据结构,适用于需要倒序处理的场景,如函数调用栈。
1、设一棵完全二叉树共有699个结点,则在该二叉树中的叶子结点数为(B) 注:利用公式n=n0+n1+n2、n0=n2+1和完全二叉数的特点可求出A. 349B. 350C. 255D. 3512、设有下列二叉树:图见书P46对此二叉树中序遍历的结果为(B)A. ABCDEFB. DBEAFCC. ABDECFD. DEBFCA3、算法的时间复杂度是指(C)A. 执行算法程序所需要的时间B. 算法程序的长度C. 算法执行过程中所需要的基本运算次数D. 算法程序中的指令条数4、下列工具中属于需求分析常用工具的是(D)A. PADB. PFDC. N-SD. DFD5、在软件开发中,下面任务不属于设计阶段的是(D)A. 数据结构设计B. 给出系统模块结构C. 定义模块算法D. 定义需求并建立系统模型6、算法的时间复杂度是指(C)A. 执行算法程序所需要的时间B. 算法程序的长度C. 算法执行过程中所需要的基本运算次数D. 算法程序中的指令条数7、用树形结构来表示实体之间联系的模型称为(B)A. 关系模型B. 层次模型C. 网状模型D. 数据模型8、在一棵二叉树上第5层的结点数最多是(B) 注:由公式2(k-1)得A. 8B. 16C. 32D. 159、数据的存储结构是指(B)A. 数据所占的存储空间量B. 数据的逻辑结构在计算机中的表示C. 数据在计算机中的顺序存储方式D. 存储在外存中的数据10、数据的存储结构是指(B)A. 数据所占的存储空间量B. 数据的逻辑结构在计算机中的表示C. 数据在计算机中的顺序存储方式D. 存储在外存中的数据11、数据流图用于抽象描述一个软件的逻辑模型,数据流图由一些特定的图符构成。
下列图符名标识的图符不属于数据流图合法图符的是(A)A. 控制流B. 加工C. 数据存储D. 源和潭12、用树形结构来表示实体之间联系的模型称为(B)A. 关系模型B. 层次模型C. 网状模型D. 数据模型13、数据的存储结构是指(B)A. 数据所占的存储空间量B. 数据的逻辑结构在计算机中的表示C. 数据在计算机中的顺序存储方式D. 存储在外存中的数据14、在数据管理技术的发展过程中,经历了人工管理阶段、文件系统阶段和数据库系统阶段。
数据结构考试及答案一、简介数据结构是计算机科学中的基础课程之一,旨在让学生掌握和运用各种数据结构的原理、方法和技巧。
本文将为大家介绍数据结构考试的内容和答案。
二、线性表1. 顺序表顺序表是一种连续存储的线性表,通过下标来访问元素。
常用的操作有插入、删除和查找。
其时间复杂度为O(n)。
2. 链表链表是一种离散存储的线性表,通过指针来连接各个节点。
常见的链表有单向链表和双向链表。
插入和删除操作的时间复杂度为O(1),查找的时间复杂度为O(n)。
三、栈和队列1. 栈栈是一种特殊的线性表,具有先进后出(LIFO)的特点。
常用的操作有压栈和出栈,时间复杂度为O(1)。
2. 队列队列是一种特殊的线性表,具有先进先出(FIFO)的特点。
常用的操作有入队和出队,时间复杂度为O(1)。
四、树1. 二叉树二叉树是一种每个节点最多有两个子节点的树结构。
常见的操作有插入、删除和查找。
平均情况下,插入、删除和查找操作的时间复杂度为O(logn)。
2. 平衡二叉树平衡二叉树是一种保持左右子树高度差不超过1的二叉树。
常用的平衡二叉树有AVL树和红黑树。
五、图图是由节点和边构成的一种非线性数据结构。
常用的操作包括插入节点、插入边、删除节点、删除边以及查找节点的邻接节点等。
六、算法答案1. 插入排序插入排序是通过将元素逐个插入已排序的部分中,从而完成排序的算法。
时间复杂度为O(n^2)。
2. 快速排序快速排序是通过选择一个基准元素,将数组分为两部分,然后对这两部分分别进行快速排序的算法。
时间复杂度为O(nlogn)。
3. 广度优先搜索广度优先搜索是一种图遍历算法,常用于查找最短路径。
通过先访问离当前节点最近的节点,再逐渐向外扩展。
4. 深度优先搜索深度优先搜索是一种图遍历算法,常用于查找可达性问题。
通过先访问最后一个邻接节点,再逐渐返回。
七、总结本文介绍了数据结构考试的内容和答案,涵盖了线性表、栈和队列、树、图以及常见的排序和搜索算法。
1、给定n个村庄之间的交通图,若村庄i和j之间有道路,则将顶点i和j用边连接,边上的Wij表示这条道路的长度,现在要从这n个村庄中选择一个村庄建一所医院,问这所医院应建在哪个村庄,才能使离医院最远的村庄到医院的路程最短?试设计一个解答上述问题的算法,并应用该算法解答如图所示的实例。
(20分)2、若第n件物品能放入背包,则问题变为能否再从n-1件物品中选出若干件放入背包(这时背包可放入物品的重量变为s-w[n])。
若第n件物品不能放入背包,则考虑从n-1件物品选若干件放入背包(这时背包可放入物品仍为s)。
若最终s=0,则有一解;否则,若s<0或虽然s>0但物品数n<1,则无解。
(1)s-w[n],n-1 //Knap(s-w[n],n-1)=true(2)s,n-1 // Knap←Knap(s,n-1)3、二叉树的层次遍历序列的第一个结点是二叉树的根。
实际上,层次遍历序列中的每个结点都是“局部根”。
确定根后,到二叉树的中序序列中,查到该结点,该结点将二叉树分为“左根右”三部分。
若左、右子树均有,则层次序列根结点的后面应是左右子树的根;若中序序列中只有左子树或只有右子树,则在层次序列的根结点后也只有左子树的根或右子树的根。
这样,定义一个全局变量指针R,指向层次序列待处理元素。
算法中先处理根结点,将根结点和左右子女的信息入队列。
然后,在队列不空的条件下,循环处理二叉树的结点。
队列中元素的数据结构定义如下:typedef struct{ int lvl; //层次序列指针,总是指向当前“根结点”在层次序列中的位置int l,h; //中序序列的下上界int f; //层次序列中当前“根结点”的双亲结点的指针int lr; // 1—双亲的左子树 2—双亲的右子树}qnode;BiTree Creat(datatype in[],level[],int n)//由二叉树的层次序列level[n]和中序序列in[n]生成二叉树。
数据结构试题(含答案)数据结构试题(含答案)一、选择题1. 数据结构是计算机科学中的一个重要概念。
下列选项中,不属于数据结构的是:A. 数组B. 栈C. 数据库D. 链表答案:C2. 在数据结构中,栈(Stack)是一种后进先出(LIFO)的数据结构。
下列操作中,不属于栈的是:A. 入栈B. 出栈C. 遍历D. 清空栈答案:C3. 链表(Linked List)是一种常见的数据结构,它由一系列节点组成,每个节点包含两个部分:数据和指向下一个节点的指针。
下列选项中,不属于链表的是:A. 单链表B. 双链表C. 循环链表D. 二叉树答案:D4. 哈希表(Hash Table)是一种根据关键码直接访问存储位置的数据结构。
下列选项中,不属于哈希表的优点是:A. 快速查找B. 插入和删除操作效率高C. 数据无序D. 冲突较少答案:C二、填空题1. 树(Tree)是一种非线性数据结构,它由一组以边连接的节点组成。
树中每个节点最多可以有________个子节点。
答案:无限制/任意个2. 图(Graph)是由节点和连接节点的边组成的数据结构。
图中节点的度是指与该节点相连接的边的________。
答案:数量3. 广度优先搜索(BFS)和深度优先搜索(DFS)是常用的图遍历算法。
在BFS中,使用________结构来保存待访问的节点。
答案:队列4. 在二叉搜索树(Binary Search Tree)中,左子树中的每个节点的值都小于根节点的值,右子树中的每个节点的值都大于根节点的值。
这种特性称为_______________。
答案:二叉搜索树性质三、简答题1. 请简要说明线性数据结构和非线性数据结构的区别。
答案:线性数据结构是指数据元素之间存在一对一的线性关系,例如数组、栈、队列等;而非线性数据结构是指数据元素之间存在一对多或多对多的关系,例如树、图等。
线性数据结构的存储方式是连续的,非线性数据结构的存储方式是离散的。
1、设单链表中指针p指着结点A,若要删除A之后的结点(若存在),则需要修改指针的操作为( A )。
A)p->next=p->next->next B)p=p->next
C)p=p->nexe->next D)p->next=p
2、数据结构中,在逻辑上可以把数据结构分成( B )。
A)动态结构和静态结构
B)线性结构和非线性结构
C)紧凑结构和非紧凑结构
D)内部结构和外部结构
3、与无向图相关的术语有( C )。
A)强连通图 B)入度
C)路径 D)弧
4、在一棵度为3的树中,度为3的结点个数为2,度为2的结点个数为1,则度为0的结点个数为( C )。
A)4 B)5
C)6 D)7
5、设单链表中指针p指向结点m,若要删除m之后的结点(若存在),则需修改指针的操作为( A )。
A)p->next=p->next->next; B) p=p->next;
C)p=p->next->next; D) p->next=p;
6、若采用邻接矩阵法存储一个n个顶点的无向图,则该邻接矩阵是一个( D )。
A)上三角矩阵 B) 稀疏矩阵
C) 对角矩阵 D) 对称矩阵
7、设有一个栈,元素的进栈次序为A, B, C, D, E,下列是不可能的出栈序列是( C )。
A) A, B, C, D, E
B) B, C, D, E, A
C) E, A, B, C, D
D) E, D, C, B, A
8、下列各种数据结构中属于线性结构的有( A )。
A)栈 B) 二叉树
C) 广义表 D) 图
9、若一棵二叉树具有10个度为2的结点,5个度为1的结点,则度为0的结点的个数是( B )。
A)9 B)11 C)15 D)不能确定
10、线索二叉树中某结点D,没有左孩子的条件是( B )。
A)D->Lchild=Null B) D->ltag=1
C) D->Rchild=Null D) D->ltag=0
11、以下属于顺序存储结构优点的是( A )。
A) 存储密度大B) 插入运算方便
C)删除运算方便D)可方便地用于各种逻辑结构的存储表示
12、与无向图相关的术语有( C )。
A)强连通图 B)入度
C)路径 D)弧
13、n个顶点的图的最小生成树必定( D ),是不正确的描述。
A)不唯一 B)权的总和唯一
C)不含回路 D)有n条边
14、栈进行插入和删除操作的特点是( A )。
A)LIFO B)FIFO
C)FCFS D)HPF
15、采用链结构存储线性表时,其地址( B )。
A)必须是连续的 B)连续不连续都可以
C)部分地址必须是连续 D)必须是不连续的。