2012海南省数据结构试题及答案
- 格式:docx
- 大小:17.39 KB
- 文档页数:2
2012年数据结构期末考试题及答案一、选择题1.在数据结构中,从逻辑上可以把数据结构分为C。
A.动态结构和静态结构B.紧凑结构和非紧凑结构C.线性结构和非线性结构D.内部结构和外部结构2.数据结构在计算机内存中的表示是指A。
A.数据的存储结构B.数据结构C.数据的逻辑结构D.数据元素之间的关系3.在数据结构中,与所使用的计算机无关的是数据的A结构。
A.逻辑B.存储C.逻辑和存储D.物理4.在存储数据时,通常不仅要存储各数据元素的值,而且还要存储C。
A.数据的处理方法B.数据元素的类型C.数据元素之间的关系D.数据的存储方法5.在决定选取何种存储结构时,一般不考虑A。
A.各结点的值如何B.结点个数的多少C.对数据有哪些运算D.所用的编程语言实现这种结构是否方便。
6.以下说法正确的是D。
A.数据项是数据的基本单位B.数据元素是数据的最小单位C.数据结构是带结构的数据项的集合D.一些表面上很不相同的数据可以有相同的逻辑结构7.算法分析的目的是C,算法分析的两个主要方面是A。
(1)A.找出数据结构的合理性B.研究算法中的输入和输出的关系C.分析算法的效率以求改进C.分析算法的易读性和文档性(2)A.空间复杂度和时间复杂度B.正确性和简明性C.可读性和文档性D.数据复杂性和程序复杂性8.下面程序段的时间复杂度是O(n2)。
s =0;for(I =0;i<n;i++)for(j=0;j<n;j++)s +=B[i][j];sum =s ;9.下面程序段的时间复杂度是O(n*m)。
for(i =0;i<n;i++)for(j=0;j<m;j++)A[i][j] =0;10.下面程序段的时间复杂度是O(log3n)。
i =0;while(i<=n)i =i * 3;11.在以下的叙述中,正确的是B。
A.线性表的顺序存储结构优于链表存储结构B.二维数组是其数据元素为线性表的线性表C.栈的操作方式是先进先出D.队列的操作方式是先进后出12.通常要求同一逻辑结构中的所有数据元素具有相同的特性,这意味着 B 。
第一章概论一、选择题1、研究数据结构就是研究(D )。
A. 数据的逻辑结构B。
数据的存储结构C. 数据的逻辑结构和存储结构D。
数据的逻辑结构、存储结构及其基本操作2、算法分析的两个主要方面是( A )。
A。
空间复杂度和时间复杂度 B. 正确性和简单性C。
可读性和文档性D。
数据复杂性和程序复杂性3、具有线性结构的数据结构是( D )。
A。
图B。
树C。
广义表D。
栈4、计算机中的算法指的是解决某一个问题的有限运算序列,它必须具备输入、输出、( B )等5个特性。
A. 可执行性、可移植性和可扩充性B。
可执行性、有穷性和确定性C。
确定性、有穷性和稳定性 D. 易读性、稳定性和确定性5、下面程序段的时间复杂度是( C )。
for(i=0;i<m;i++)for(j=0;j〈n;j++)a[i][j]=i*j;A. O(m2) B。
O(n2) C。
O(m*n) D. O(m+n)6、算法是(D )。
A。
计算机程序 B. 解决问题的计算方法C。
排序算法 D. 解决问题的有限运算序列7、某算法的语句执行频度为(3n+nlog2n+n2+8),其时间复杂度表示( C )。
A。
O(n) B. O(nlog2n) C。
O(n2) D. O (log2n)8、下面程序段的时间复杂度为( C ).i=1;while(i<=n)i=i*3;A. O(n)B。
O(3n) C。
O(log3n) D. O(n3)9、数据结构是一门研究非数值计算的程序设计问题中计算机的数据元素以及它们之间的()和运算等的学科。
A. 结构B。
关系C。
运算D。
算法10、下面程序段的时间复杂度是(A )。
i=s=0;while(s<n){i++;s+=i;}A. O(n) B。
O(n2)C。
O(log2n)D。
O(n3)11、抽象数据类型的三个组成部分分别为(A)。
A. 数据对象、数据关系和基本操作B. 数据元素、逻辑结构和存储结构C. 数据项、数据元素和数据类型D. 数据元素、数据结构和数据类型12、通常从正确性、易读性、健壮性、高效性等4个方面评价算法的质量,以下解释错误的是()。
数据结构习题集(自编)第一章绪论一、选择题1.数据结构是一门研究非数值计算的程序设计问题中的操作对象以及它们之间的()和运算的学科。
A.结构B.关系 C.运算 D.算法2.在数据结构中,从逻辑上可以把数据结构分成()。
A.动态结构和静态结构 B.紧凑结构和非紧凑结构C.线性结构和非线性结构 D.逻辑结构和存储结构3.线性表的逻辑顺序和存储顺序总是一致的,这种说法()。
A.正确B.不正确 C.无法确定 D.以上答案都不对4.算法分析的目的是()。
A.找出算法的合理性 B.研究算法的输人与输出关系C.分析算法的有效性以求改进 D.分析算法的易懂性5. 算法的时间复杂度取决于()A.问题的规模B待处理数据的初态 C. A和B6.一个算法应该是()。
A.程序B.问题求解步骤的描述C.要满足五个基本特性 D.A和C.7. 下面关于算法说法错误的是()A.算法最终必须由计算机程序实现B.为解决某问题的算法与为该问题编写的程序含义是相同的C. 算法的可行性是指指令不能有二义性D. 以上几个都是错误的8.以下与数据的存储结构无关的术语是()。
A.循环队列 B. 链表 C. 哈希表 D. 栈9.在下面的程序段中,对x的赋值语句的频度为()for(i=0;i<n;i++)for(j=0;j<n;j++)x=x+1;nA. 2n B.n C.n2 D.log210.以下数据结构中,()是非线性数据结构A.树 B.字符串 C.队列 D.栈11. 下列数据中,()是线性数据结构。
A.哈夫曼树 B.有向无环图 C. 二叉排序树 D. 栈12.以下属于逻辑结构的是()。
A.顺序表 B. 哈希表 C.有序表 D. 单链表二、填空题1、_______是信息的载体,是对客观事物的符号表示,它能够被计算机识别、存储、加工和处理,________是对能够有效的输人到计算机中并且能够被计算机处理的符号的总称。
(数据、数据)2、数据元素是数据的______,有些情况下也称为元素、结点、顶点、记录等。
海南大学2012-2013学年度第1学期试卷科目:《数据结构》试题( A卷) 学院:信息学院专业班级:姓名:学号:阅卷教师: 2010 年月日考试说明:本课程为闭卷考试,可携带计算器。
1.栈的逻辑特点是,队列的逻辑特点是。
2.线性表的顺序存储结构是一种()的存储结构,线性结构的链式存储是一种()的存储结构。
A.随机存取 B.顺序存取 C.索引存取 D.散列存取3.向一个栈顶指针为的带头结点的非空的链栈中删除结点,则其操作步骤是( C )>; >>>; (s)C. s = >(s)D. s = > >(s)4. 向一个栈顶指针的链栈中插入一个s所指的结点时,执行的操作是(B)>; >>>; (s)C. s = >(s)D. s = > >(s)5. 设链队列的队头指针为,队尾指针为,队列为空的条件是;,队列为满的条件是。
6.带头结点的单向循环链表为空的判断条件是()A. B. > C. > D.7. 在一个长度为n的单链表的第i(0<<n)个元素后面插入一个元素时,需要向后移动()个元素。
A. 1 1 D.08.在一个长度为n的顺序存储的线性表中,删除第i个元素(1≤i≤1)时,需要从前向后依次前移()个元素。
A. 1 1 D.09. 若某线性表最常用的操作是在最后一个元素之后插入一个元素和删除进入表中的最后一个元素,则采用()存储方式最节省运算时间和存储空间。
A.单链表B.仅有头指针的单循环链表C.双向链表D.仅有头尾指针的单循环链表单链表最后一个元素之后插入一个元素的时间复杂度为O(n)仅有尾指针的单循环链表最后一个元素之后插入一个元素的时间复杂度为O(1)10. 设有一个顺序栈S,元素a b c d e f依次进栈,如果6个元素出栈的顺序是b d c f e a,则栈的容量至少应该是()A.2B.3C.5D.611. 设有一个顺序栈S,元素, c, d, e, f依次进栈,如果6个元素的出栈顺序为a, c, d, b, f, e, 则栈的容量至少应该是()A.2B.3C.5D.612.试编写算法,在一个循环单链表中删除结点S,且要求函数返回该链表的一个入口指针。
武汉大学计算机学院2012年-2013学年第一学期“数据结构”考试试题(A )姓名学号(序号)_ 班号要求:所有的题目的解答均写在答题纸上,需写清楚题目的序号。
每张答题纸都要写上姓名和序号。
一、单项选择题(每小题2分,共30分)1. 数据结构在计算机内存中的表示是指 。
A. 数据的存储结构 B. 数据结构 C. 数据的逻辑结构 D. 数据元素之间的关系2. 若线性表最常用的运算是存取第i 个元素及其前趋元素的值,则采用 存储方式节省时间。
A.单链表B.双链表C.单循环链表D.顺序表3. 在一个具有n 个结点的有序单链表中插入一个新结点使得仍然有序,其算法的时间复杂度为 。
A.O(log 2n)B.O(1)C.O(n 2)D.O(n) 4. 栈和队列的共同点是 。
A.都是先进后出 B.都是先进先出 C.只允许在端点处插入和删除元素 D.没有其同点5. 判定一个循环队列Q (存放元素位置为0~QueueSize-1,front 指向队中队首元素的前一个位置,rear 指向队中队尾元素的位置)队空的条件是 。
A.Q.front==Q.rearB.Q.front+1==Q.rearC.Q.front==(Q.rear+1)%QueueSizeD.Q.rear==(Q.front+1)%QueueSize 6. 串是 。
A.不少于一个字母的序列B.任意个字母的序列C.不少于一个字符的序列D.有限个字符的序列 7. 一个n×n 的对称矩阵A ,如果采用以列优先(即以列序为主序)的压缩方式存放到一个一维数组B 中,则B 的容量为 。
A. n 2B.22nC. 2)1(+n nD.2)1(2+n8. 若一棵3次树中有a 个度为1的节点,b 个度为2的节点,c 个度为3的节点,则该树中有 个叶子节点。
A.1+2b +3cB.a +2b +3cC.2b +3cD.1+b +2c 9. 一棵完全二叉树中有501个叶子节点,则至少有 个节点。
2012数据结构_习题及程序设计整理疯狂记忆力数据结构是计算机科学中非常重要的一个领域,它主要研究数据的组织、存储和管理方式。
在学习数据结构的过程中,习题和程序设计是提高理解和应用的重要手段。
下面将整理一些2012年的数据结构习题及程序设计内容,帮助读者巩固和深入理解这一领域的知识。
一、线性结构1. 线性表是数据结构中最基本的一种结构,它的特点是元素之间存在一对一的关系,先后次序唯一确定。
请写一个C语言程序,实现线性表的基本操作,包括插入、删除、查找等。
2. 栈是一种特殊的线性表,具有“先进后出”的特点。
设计一个栈,支持判断栈是否为空、入栈和出栈操作,并实现一个简单应用情境,例如操作系统任务的进出栈操作。
3. 队列也是一种特殊的线性表,具有“先进先出”的特点。
设计一个队列,支持判断队列是否为空、入队和出队操作,并实现一个简单应用情境,例如模拟排队等待的场景。
二、非线性结构1. 树是一种重要的非线性结构,它以分层的方式存储数据。
定义一个树的基本数据结构,包括节点的定义、插入节点、删除节点等操作。
2. 图是由节点和边组成的数据结构,用于表示多对多的关系。
请设计一个简单的图结构,实现图的初始化、添加节点、添加边以及遍历等基本操作。
三、查找与排序1. 二分查找是一种常见的查找算法,适用于有序数组。
请编写一个二分查找算法的Java程序,并验证其正确性。
2. 快速排序是一种常见的排序算法,通过分治法实现。
请实现一个快速排序算法的Python程序,并对随机生成的一组数据进行排序。
四、高级数据结构1. 堆是一种完全二叉树,主要用于实现高效的优先队列。
设计一个堆的数据结构,并实现堆排序算法。
2. 哈希表是一种以键值对存储数据的数据结构,通过哈希函数实现高效的数据查找。
请实现一个简单的哈希表,包括哈希函数的设计、数据的插入和查找等操作。
以上是一些2012年的数据结构习题及程序设计内容,涵盖线性结构、非线性结构、查找与排序以及高级数据结构等方面的内容。
1、对待排序的元素序列进行划分,将其分为左、右两个子序列,再对两个子序列施加同样的排序操作,直到子序列为空或只剩一个元素为止。
这样的排序方法是( A )。
A)直接选择排序 B)直接插入排序
C)快速排序 D)起泡排序
2、n个顶点的图的最小生成树必定( D ),是不正确的描述。
A)不唯一 B)权的总和唯一
C)不含回路 D)有n条边
3、下面程序段的时间复杂度是( A )。
s =0;
for( i =0; i<n; i++)
for(j=0;j<n;j++)
s +=B[i][j];
sum = s ;
A) O(n2) B) O(n)
C) O(m*n) D)O(1)
4、采用链结构存储线性表时,其地址( B )。
A)必须是连续的 B)连续不连续都可以
C)部分地址必须是连续 D)必须是不连续的
5、在一个具有n个单元的顺序栈中,假定以地址低端(即0单元)作为栈底,以top作为栈顶指针,当做出栈处理时,top变化为( C )。
A)top不变 B)top=0 C)top-- D)top++
6、以下属于顺序存储结构优点的是( A )。
A) 存储密度大B) 插入运算方便
C)删除运算方便D)可方便地用于各种逻辑结构的存储表示
7、若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算,则利用( D )存储方式最节省时间。
A)顺序表B)双链表C)带头结点的双循环链表 D)单循环链表
8、在一个具有n个单元的顺序栈中,假定以地址低端(即0单元)作为栈底,以top作为栈顶指针,当做出栈处理时,top变化为( C )。
A)top不变 B)top=0 C)top-- D)top++
9、如果结点A有3个兄弟,而且B为A的双亲,则B的度为( B )。
A)3 B)4 C)5 D)1
10、设一数列的顺序为1,2,3,4,5,6,通过栈结构不可能排成的顺序数列为( B )。
A)3,2,5,6,4,1 B)1,5,4,6,2,3
C)2,4,3,5,1,6 D)4,5,3,6,2,1
11、已知广义表L=((x,y,z),a,(u,t,w)),从L 表中取出原子项t 的操作是( D )。
A) Head(Head(Tail(Tail(L))))
B) Tail(Head(Head(Tail(L))))
C) Head(Tail(Head(Tail(L))))
D)Head(Tail(Head(Tail(Tail(L)))))
12、采用链结构存储线性表时,其地址( B )。
A)必须是连续的 B)连续不连续都可以
C)部分地址必须是连续 D)必须是不连续的
13、广义表A=(A,B,(C,D),(E,(F,G))),则head(tail(head(tail(tail(A)))))=( D )。
A) (G) B) (D) C) C D) D。