【www.bbjkw.net--教学考试试卷】
数据结构试卷篇(1):数据结构练习试题
一、单项选择题
1.关系数据模型的三个组成部分中,不包括( C )
A.完整性规则 B.数据结构 C.恢复D.数据操作
2. 五种基本关系代数运算是 ( A )
A. ∪,-,×,π和σ B. ∪,-,∞,π和σ
C. ∪,∩,×,π和σ D. ∪,∩,∞,π和σ
3.公司中有多个部门和多名职员,每个职员只能属于一个部门。一个部门可以有多名职员,从部门到职员的联系类型是( D )
A.多对多 B.一对一 C.多对一 D.一对多
4.关系代数表达式的优化策略中,首先要做的是( B )
A.对文件进行预处理 B.尽早执行选择运算
C.执行笛卡儿积运算 D.投影运算
5.下列四项中,不属于关系数据库特点的是( D )
A.数据冗余小 B.数据独立性高 C.数据共享性好 D.多用户访问
6. 下列聚合函数中不忽略空值 (null) 的是( C )
A. SUM (列名) B. MAX (列名) C. COUNT ( * ) D. AVG (列名)
7.SQL语言中,修改表结构的语句是( D )。
A、CREATE B、SELECT C、UPDATE D、ALTER
8.下列四项中说法不正确的是( C ) 共四页第二页
A.数据库减少了数据冗余 B.数据库中的数据可以共享
C.数据库避免了一切数据的重复 D.数据库具有较高的数据独立性
9.在关系数据库系统中,为了简化用户的查询操作。而又不增加数据的存储空间,常用的方法是创建( C )
A. 另一个表(table) B. 游标(cursor) C. 视图(view)D.索引(index)
10. 如果事务T获得了数据项Q上的排它锁,则T对Q ( C )
A.只能读不能写 B.只能写不能读 C. 既可读又可写 D. 不能读不能写
二.填空题
1.数据库系统一般由数据库, _________, _应用系统_________ 。数据库管理员和用户构成。
2.数据库的存储结构改变了,由数据库管理员对_________映像作相应改变。可以使_模式_与应用程序保持不变,从而保证了数据的物理独立性。
3. DB并发操作通常会带来三类问题,它们是丢失更新、不可重复读和____________。
4. 事务必须具有的四个性质是:原子性、___________、____________和持久性。
5.用树型结构表示实体类型及实体间联系的数据模型称为_______________。
6.从关系规范化理论的角度讲,一个只满足1NF的关系可能存在的四方面问题是:数据冗余度大、修改异常、插入异常和______。
三、简答题
1、数据库
2、候选码
3、试述DBMS的主要功
4、数据模型的组成要素.
数据结构试卷篇(2):数据结构试题答案
一、单项选择题(每题2分,共30分)
1.若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素,则采用( )存储方式最节省时间。
A) 单链表 B) 双链表 C) 单向循环链表 D) 顺序表
2.串是任意有限个( )。
A) 符号构成的序列 B) 符号构成的集合
C) 字符构成的序列 D) 字符构成的集合
3.设矩阵A的任一元素aij(1≤i,j≤10)满足:
aij≠0;(i≥j,1≤i,j≤10)
aij=0; (i<j,1≤i,j≤10)
现将A的所有非0元素以行序为主序存放在首地址为2000的存储区域中,每个元素占有4个单元,则元素A[9,5]的首地址为( )。
A) 2340 B) 2336 C) 2164 D) 2160
4.如果以链表作为栈的存储结果,则出栈操作时( )。
A) 必须判别栈是否为满 B) 对栈不作任何判别
C) 必须判别栈是否为空 D) 判别栈元素的类型
5.设数组Data[0..m]作为循环队列SQ的存储空间,front为队头指针,rear为队尾指针,则执行出队操作的语句为( )。
A) front = front+1 B) front = (front+1) % m
C) rear = (rear+1) % m D) front = (front+1) % (m+1)
6.深度为6(根的层次为1)的二叉树至多有( )结点。
A) 64 B) 32 C) 31 D) 63
7.将含100个结点的完全二叉树从根这一层开始,每层上从左到右依次堆结点编号,根结点的编号为1。编号为49的结点X的双亲的编号为( )。
A) 24 B) 25 C) 23 D) 无法确定
8.设有一个无向图 和 ,如果 为 的生成树,则下面不正确的说法是( )。
A) 为 的子图 B) 为 的连通分量
C) 为 的极小连通子图且 D) 为 的一个无环子图
9.用线性探测法查找闭散列表,可能要探测多个散列地址,这些位置上的键值( )。
A) 一定都是同义词 B) 一定都不是同义词
C) 多相同 D) 不一定都是同义词
10.二分查找要求被查找的表是( )。
A) 键值有序的链接表 B) 链接表但键值不一定有序
C) 键值有序的顺序表 D) 顺序表但键值不一定有序
11.当初始序列已经按键值有序,用直接插入算法对其进行排序,需要循环的次数为( )。
A) B) C) D) n-1
12.堆是一个键值序列 ,对 ,满足( )。
A) B)
C) 且 ( ) D) 或 ( )
13.使用双向链表存储数据,其优点是可以( )。
A) 提高检索速度 B) 很方便地插入和删除数据
C) 节约存储空间 D) 很快回收存储空间
14.设计一个判别表达式中左右括号是否配对出现地算法,采用( )数据结构最佳。
A) 线性表地顺序存储结构 B) 栈
C) 队列 D) 线性表达的链式存储结构
15.设深度为k的二叉树上只有度为0和2的结点,则此类二叉树中所含的结点数至少为( )。
A) k + 1 B) 2k C) 2k - 1 D) 2k + 1
二、填空题(每空2分,共28分)
1.设r指向单链表的最后一个结点,要在最后一个结点之后插入s所指的结点,需执行的三条语句是_____________________________________________r=s;r->next=NULL。
2.在单链表中,指针p所指结点为最后一个结点的条件是___________________。
3.设一个链栈的栈顶指针是ls,栈中结点格式为 ,栈空的条件为_____________。如果栈不为空,则出栈操作为p=ls;______________;free(p)。
4.已知一棵度为3的树有2个度为1的结点,3个度为2的结点,4个度为3的结点,则该树有________个叶子结点。
5.树有三种常用的存储结构,即孩子链表法,孩子兄弟链表法和____________。
6.n个顶点的连通图的生成树有__________条边。
7.一个有向图G中若有弧 、 和 ,则在图G的拓扑序列中,顶点 的相对位置为___________。
8.设表中元素的初始状态是按键值递增的,分别用堆排序、快速排序、冒泡排序和归并排序方法对其进行排序(按递增顺序),________最省时间,__________最费时间。
9.下面是将键值为x的结点插入到二叉排序树中的算法,请在划线处填上适当的内容。
Typedef struct pnode
{ int key;
struct node * left, * right;
}
Void search (int x; pnode t )
{ if (_____________)
{p = malloc (size);
p->key=x;p->left=NULL;
p->right=NULL;
t=p;
}
else
if (xkey) search (x,t->left)
else _________________
}
10.线性表的____________的主要优点是从表中任意结点出发都能访问到所有结点。而使用____________,可根据需要在前后两个方向上方便地进行查找。
三、应用题(每题10分,共30分)
1.在双链表中,要在指针变量P所指结点之后插入一个新结点,请按顺序写出必要的算法步骤。(设:P所指结点不是链表的首尾结点,q是与p同类型的指针变量)
2.已知待排序文件各记录的排序码顺序如下:
72 73 71 23 94 16 05 68
请列出快速排序过程中每一趟的排序结果。
四、算法题(共12分)
编写算法,实现单链表上的逆置运算(说明:即将单链表中的元素次序反转)
参考答案:
一、单项选择题(每题2分,共30分)
1.D 2.C 3.D 4.C 5.D 6.D 7.A 8.B 9.D 10.C 11.D 12.C 13.A 14.B 15.C
二、填空题(每空2分,共28分)
1. r->next=s; 2. p->next=NULL;
3. ls = = NULL; ls=ls->link。 4. 12
5. 双亲表示法 6. n-1
7. i,j,k 8. 冒泡排序,快速排序
9. t= =NULL,search(x,t->right); 10.循环链表,双向链表
三、应用题(每题10分,共30分)
1.new(q);
q↑.llink ← p;
q↑.rlink ← p↑.rlink;
p↑.rlink↑.llink ← q;
p↑.rlink ← q。
评分细则:按顺序每对一个给2分,全对计10分。
2.各趟结果如下:
[68 05 71 23 16] 72 [94 73]
[16 05 23] 68 [71] 72 [94 73]
[05] 16 [23] 68 [71] 72 [94 73]
05 16 [23] 68 [71] 72 [94 73]
05 16 23 68 71 72 [94 73]
05 16 23 68 71 72 [73] 94
05 16 23 68 71 72 73 94
四.算法题(共12分)
void invert( pointer head)
{p=NULL;
while ( head<>NULL)
{u=head;
head=head->next;
u->next=p;
p=u;
}
head=p;
}
数据结构试卷篇(3):2017年计算机考试试题及答案
一、单项选择题
1在深度为7的满二叉树中,叶子结点的个数为( )
A.32B.31C.64D.63
参考答案:C
参考解析:在满二叉树中每层的结点数都达到最大值, 而且叶子结点全部出现在最底层。第1层(根结点所在的层)有20个结点,第2层有21个结点,……第n层有2n-1个结点。在深度为7的满二叉树中,第7层有2 7-1=64个结点(全部是叶子结点)、在深度为7的满二叉树中,共有2^(7-1)=64个结点、因此本题的正确答案是C。
2下列叙述中正确的是( )
A.程序执行的效率与数据的存储结构密切相关
B.程序执行的效率只取决于程序的控制结构
C.程序执行的效率只取决于所处理的数据量
D.以上三种说法都不对
参考答案:A
参考解析:程序的执行效率与算法和数据结构有密切的关系,瑞士科学家沃士说过“程序=算法+数据结构”。所以程序执行的效率与数据的存储结构密切相关;程序执行的效率与程序的控制结构、所处理的数据量有关,但不绝对相关。因此本题的正确答案是A。
3下列工具为需求分析常用工具的是
A.PADB.PFDC.N-SD.DFD
参考答案:D
4以下算法设计基本方法中基本思想不属于归纳法的是( )
A.递推法B.递归法C.减半递推技术D.回溯法
参考答案:D
5对长度n的线性表排序,在最坏情况下,比较次数不是n(n-1)/2的排序方法是( )
A.快速排序B.冒泡排序C.直接插入排序D.堆排序
参考答案:D
参考解析:排序技术有:①交换类排序法(冒泡排序法、快速排序法);②插入类排序法(简单插入排序、希尔排序);③选择类排序法(简单选择排序法、堆排序法)。在最坏情况下,希尔排序需要的比较次数是O(nl.5)、堆排序需要的比较次数是O(nlog2n)、其它排序方法需要的比较次数都是n(n.1)/2。因此本题的正确答案是D。
6按软件的功能划分,需求分析工具软件属于
A.应用软件B.系统软件C.支撑软件D.专用软件
参考答案:C
7对右下图二叉树进行后序遍历的结果为( )
A.ABCDEFB.DBEAFCC.ABDECFD.DEBFCA
参考答案:D
参考解析:后序遍历的方法是:若二叉树为空,则结束返回。否则先后序遍历左子树,再后序遍历右子树,最后访问根结点。本题后序遍历左子树的结果是DEB,后续遍历右子树的结果是FC,最后根是A,所以后续遍历的结果是DEBFCA。因此本题的正确答案是D。
8在E-R图中,用来表示实体之间联系的图形是( )
A.矩形B.椭圆形C.菱形D.平行四边形
参考答案:C
参考解析:在E-R图中用矩形表示实体集,用椭圆表示属性,用菱形表示联系,用无向线段表示实体集(联系)与属性、实体集与联系间的联接关系。因此本题的正确答案是C。
9下面不属于软件工程的三个要素的是
A.工具B.过程C.方法D.环境
参考答案:D
10原因排除法属于
A.软件调试方法B.黑盒测试方法C.白盒测试方法D.动态测试方法
参考答案:A
11下列叙述中正确的是
A.软件测试的主要目的是发现程序中的错误
B.软件测试的主要目的是确定程序中错误的位置
C.为了提高软件测试的效率,最好由程序编制者自己来完成软件测试的工作
D.软件测试是证明软件没有错误
参考答案:A
参考解析:软件测试是为了发现错误而执行程序的过程,所以软件测试的主要目的是发现程序中的错误。为了提高软件测试的效率,程序员应该避免检查自己的程序。软件测试是为了证明软件有错,而不能证明程序没有错。因此本题的正确答案是A。
12数据库概念设计过程分三个步骤进行:首先选择局部应用,再进行局部视图设计,最后进行( )
A.数据集成B.视图集成C.过程集成D.视图分解
参考答案:B
13检查软件产品是否符合需求定义的过程是
A.单元测试B.集成测试C.确认测试D.系统测试
参考答案:C
14数据库设计的基本任务是根据用户对象的信息需求、处理需求和数据库的支持环境设计出( )
A.数据模式B.过程模式C.数据类型D.数据结构
参考答案:A
15下面哪一项不是消息的组成部分?
A.发送消息的对象的名称B.接受消息的对象的名称C.消息标志符D.零个或多个参数
参考答案:A
16下列几种耦合中独立性最强的是
A.内容耦合B.公共耦合C.数据耦合D.非直接耦合
参考答案:D
17消息传递中所传递的消息实质上是哪种对象所具有的操作(或方法)名称?
A.发送对象B.接受对象C.请求对象D.调用对象
参考答案:B
18下列哪一项不是结构化分析的常用工具?
A.控制流图B.数据字典C.数据流图D.判定树
参考答案:A
19下面哪一项不是面向对象方法的优点?
A.稳定性好B.可重用性好C.运行效率高D.可维护性好
参考答案:C
20软件调试的目的是
A.发现错误B.改正错误C.改善软件的性能D.验证软件的正确性
参考答案:B
参考解析:软件测试是为了发现错误而执行程序的过程;软件调试的任务是诊断和改正程序中的错误。软件测试贯穿整个软件生命周期,调试主要在开发阶段。因此本题的正确答案是B。
21在用二分法求解方程在一个闭区间上的实根时,采用的算法没计技术是( )
A.列举法B.归纳法C.递归法D.减半递推法
参考答案:D
22下列叙述中正确的是( )
A.循环队列有队头和队尾两个指针,因此,循环队列是非线性结构
B.在循环队列中,只需要队头指针就能反映队列中元素的动态变化情况
C.在循环队列中,只需要队尾指针就能反映队列中元素的动态变化情况
D.循环队列中元素的个数是由队头指针和队尾指针共同决定
参考答案:D
参考解析:所谓循环队列,就是将队列存储空间的最后一个位置绕到第一个位置,形成逻辑上的环状空间,供队列循环使用。在循环队列中,用队尾指针rear指向队列中的队尾元素,用排头指针front指向排头元素的前一个位置,因此,从排头指针front指向的后一个位置直到队尾指针real指向的位置之间所有的元素均为队列中的元素。求解队列中元素个数的方法是:若front>rear,队列中有n-front+rear个元素(其中n为循环队列的容量);若front
23概要设计中要完成的事情是
A.系统结构和数据结构的设计
B.系统结构和过程的设计
C.过程和接口的设计
D.数据结构和过程的设计
参考答案:A
24在软件生命周期中,能准确地确定软件系统必须做什么和必须具备那些功能的阶段是
A.概要设计B.详细设计C.可行性分析D.需求分析
参考答案:D
25已知元素的入栈顺序为abcde,则下列哪种出栈顺序是不可能的(出栈和入栈操作可交叉进行?( )
A.edcbaB.cabdeC.dcbaeD.bcdea
参考答案:B
参考解析:abCde依次入栈,再依次出栈,得到出栈顺序edCba,所以选项A可能;我们现在来看选项B.第一个出栈的是C,&-Itl可以肯定栈中有b、a,等待入栈的是d、e,此时出栈的可能是b或d(d入栈马上出栈),不可能是a,所以选项B不可能;选项C,第一个出栈的是d,可以肯定栈中有C、b、a,等待入栈的是e,此时出栈的可能是C或e(C入栈马上出栈),若C、b、a依次出栈,e入栈马上出栈,刚好得到出栈顺序dCbae,因此选项C可能;选项D.第l个出栈的是b,可以肯定栈中有a,等待入栈的是c、d、e,C、d、e分别入栈马上又出栈得到出栈顺序bcde,最后a出栈,刚好得到出栈顺序bcdea,所以选项D可能。因此本题的正确答案是B。
26下列关于栈的描述正确的是( )
A.在栈中只能插入元素而不能删除元素
B.在栈中只能删除元素而不能插入元素
C.栈是特殊的线性表,只能在-端插入或删除元素
D.栈是特殊的线性表,只能在-端插入元素,而在另-端删除元素
参考答案:C
参考解析:栈是一个特殊的线性表,只能在栈顶进行插入(又叫入栈)和删除(又叫出栈)操作;队列是一个、允许在队尾插入元素(又叫入队),在队头删除元 不素又叫出队)的线性袁 因此选项C正确。
27按照结构化程序的设计原则和方法,下列叙述中正确的是
A.语言中所没有的控制结构,应该采用前后一致的方法来模拟
B.基本结构在程序设计中不允许嵌套
C.在程序中不要使用GOT0语句
D.选用的结构只准有一个入口,但可以有多个出口
参考答案:A
28边界值分析法属于哪一类测试的常用方法?
A.静态测试B.白盒测试C.黑盒测试D.集成测试
参考答案:C
29当数据库中的数据遭受破坏后要实施的数据库管理是( )
A.数据库的备份B.数据库的恢复C.数据库的监控D.数据库的加载
参考答案:B
30下列哪一项方法不是说明面向对象的易于修改的特性?
A.对象的封装性B.继承机制C.隐藏机制D.多态性机制
参考答案:C
31为提高数据库的运行性能和速度而对数据库实施的管理活动有( )
A.数据库的建立和加载
B.数据库的调整和重组
C.数据库安全性控制和完整性控制
D.数据库的故障恢复
参考答案:B
32软件是指
A.程序B.程序和文档C.算法加数据结构D.程序、数据与相关文档的完整集合
参考答案:D
参考解析:软件是计算机系统中与硬件相互依存的另一部分,是包括程序、数据及相关文档的完整集合。其中,程序是软件开发人员根据用户需求开发的、用程序设计语言描述的、适合计算机执行的指令(语句)序列;数据是使程序能正常操纵信息的数据结构;文档是与程序开发、维护和使用有关的图文资料。因此本题的正确答案是D。
33在软件设计中,不属于过程设计工具的是
A.PDL(过程设计语言)B.PAD图C.N-S图D.DFD图
参考答案:D
参考解析:常见的过程设计工具有:①图形工具:程序流程图,N.S,PAD(问题分析图),HIP0;②表格工具:判定表;⑧语言工具:PDL(过程设计语言)。结构化分析的常见工具有:DFD图(数据流图)、DD(数据字典)、判定树、判定表。过程设计工具用在软件开发的详细设计阶段,结构化分析工具用在软件开发的需求分析阶段。因此选项D正确。
34对右图二叉树进行前序遍历的结果为( )
A.DYBEAFCZX
B.YDEBFZXCA
C.ABDYECFXZ
D.ABCDEFXYZ
参考答案:C
参考解析:前序遍历(DLR)的基本思想是:先访问根结点,后前序遍历dzq-树,再前序遍历右子树。本题根结点是A,前序遍历左子树得到的序列为BDYE,前序遍历右子树得到的序列为CFXZ,所以对本题二叉树进行前序遍历的结果为ABDYECFXZ。因此本题的正确答案是C。
35数据库的三级模式中不涉及具体的硬件环境与平台,也与具体的软件环境无关的模式是( )
A.概念模式B.外模式C.内模式D.子模式
参考答案:A
二、填空题
36在两种基本测试方法中,________测试的原因之一是保证所测模块中每一个独立路径至少要执行一次。
参考解析:白盒测试
【分析】软件测试按照功能划分可以分为白盒测试和黑盒测试方法。保证所测模块中每一独立路径至少执行一次是白盒测试的基本原则之一。
37在数据流图中用○表示________、用→表示________ 、用〓表示________ 、用口表示________。在数据字典中用【...
本文来源:https://www.bbjkw.net/fanwen170617/
推荐访问:数据结构期末试卷