2005年1月数据导论导论自考试题
- 格式:doc
- 大小:87.50 KB
- 文档页数:4
全国2011年1月自学考试数据结构导论试题课程代码:02142一、单项选择题(本大题共15小题,每小题2分,共30分)在每小题列出的四个备选项中只有一个是符合题目要求的,请将其代码填写在题后的括号内。
错选、多选或未选均无分。
1.在顺序表中查找第i个元素,时间效率最高的算法的时间复杂度为( )A.O(1)B.O(n)C.O(log2n)D.O(n)2.树形结构中,度为0的结点称为( )A.树根B.叶子C.路径D.二叉树3.已知有向图G=(V,E),其中V={V1,V2,V3,V4,V5,V6,V7},E={<V1,V2>,<V1,V3>,<V1,V4>,<V2,V5>,<V3,V5>,<V3,V6>,<V4,V6>,<V5,V7>,,<V6,V7>},则图G的拓扑序列是( ) A.V1,V3,V4,V6,V2,V5,V7 B.V1,V3,V2,V6,V4,V5,V7C.V1,V3,V4,V5,V2,V6,V7D.V1,V2,V5,V3,V4,V6,V74.有关图中路径的定义,表述正确的是( )A.路径是顶点和相邻顶点偶对构成的边所形成的序列B.路径是不同顶点所形成的序列C.路径是不同边所形成的序列D.路径是不同顶点和不同边所形成的集合5.串的长度是指( )A.串中所含不同字母的个数B.串中所含字符的个数C.串中所含不同字符的个数D.串中所含非空格字符的个数6.组成数据的基本单位是( )A.数据项B.数据类型C.数据元素D.数据变量7.程序段i=n;x=0;do{x=x+5*i;i--;}while (i>0);的时间复杂度为( )A.O(1)B.O(n)C.O(n2)D.O(n3)8.与串的逻辑结构不同的...数据结构是( )A.线性表B.栈C.队列D.树9.二叉树的第i(i≥1)层上所拥有的结点个数最多为( )A.2iB.2iC.2i-1D.2i-110.设单链表中指针p指向结点A,若要删除A的直接后继,则所需修改指针的操作为( ) A.p->next=p->next->next B.p=p->nextC.p=p->next->nextD.p->next=p11.下列排序算法中,某一趟结束后未必能选出一个元素放在其最终位置上的是( )A.堆排序B.冒泡排序C.直接插入排序D.快速排序12.设字符串S1=″ABCDEFG″,S2=″PQRST″,则运算S=CONCAT(SUBSTR(S1,2,LENGTH(S2)),SUBSTR(S1,LENGTH(S2),2))后S的结果为( )A.″BCQR″B.″BCDEF″C.″BCDEFG″D.″BCDEFEF″13.在平衡二叉树中插入一个结点后造成了不平衡,设最低的不平衡结点为A,并且A的左孩子的平衡因子为-1,右孩子的平衡因子为0,则使其平衡的调整方法为( )A.LL型B.LR型C.RL型D.RR型14.如果结点A有3个兄弟结点,而且B为A的双亲,则B的度为( )A.1B.3C.4D.515.数据表A中每个元素距其最终位置较近,则最省时间的排序算法是( )A.堆排序B.插入排序C.直接选择排序D.快速排序二、填空题(本大题共13小题,每小题2分,共26分)请在每小题的空格中填上正确答案。
数据结构导论自考题-1(总分100,考试时间90分钟)一、单项选择题在每小题列出的四个备选项中只有一个是符合题目要求的。
1. 算法的便于阅读和理解的特性称为( )A.正确性 B.易读性C.健壮性 D.时空性2. 给定有n个元素,建立一个有序单链表的时间复杂度为( )A.O(1) B.O(n)C.O(n2) D.O(nlog2n)3. 在双链表中某结点(已知其地址)前插入一新结点,其时间复杂度为( )A.O(n) B.O(1)C.O(n2) D.O(log2n)4. 顺序栈s中top为栈顶指针,指向栈顶元素所在的位置,elem为存放栈的数组,则元素e 进栈操作的主要语句为( )A.s.elem[top]=e;s.top=s.top+1;B.s.elem[top+1]=e;s.top=s.top+1;C.s.top=s.top+1;s.elem[top+1]=e;D.s.top=s.top+1;s.elem[top]=e;5. 一个数组的第一个元素的存储地址是100,每个元素占2个存储单元,则第5个元素的存储地址是( )A.110 B.108C.100 D.1206. 已知某完全二叉树采用顺序存储结构,结点数据的存放顺序依次为A、B、C、D、E、F、G、H,该完全二叉树的后序遍历序列为( )A.HDBEFCGA B.HDEBFGCAC.DHEBFGACA D.DEHBFGCA7. 除根结点外,树上每个结点( )A.可有任意多个孩子、一个双亲 B.可有任意多个孩子、任意多个双亲C.可有一个孩子、任意多个双亲 D.只有一个孩子、一个双亲8. 一棵完全二叉树上有1001个结点,其中叶子结点的个数是( )A.250 B.500C.501 D.5059. 设有6个结点的无向图,若要确保此图是一个连通图,则至少应有边的条数是( )A.5 B.6C.7 D.810. 在含有n个顶点e条边的无向图的邻接矩阵中,零元素的个数为( )A.e B.2eC.n2-e D.n2-2e11. 设有无向图G=(V,E)和(G'=(V',E'),如G'为G的生成树,则下面说法不正确的是( )A.G'为G的子图 B.G'为G的连通分量C.G'为G的极小连通子图且V'=V D.G'是G的无环子图12. 利用逐点插入法建立序列(50,72,43,85,75,20,35,45,65,30)对应的二叉排序树以后,查找元素35要进行元素间比较的次数是( )A.4次 B.5次C.7次 D.10次13. 采用二分查找法,若当前取得的中间位置MID的元素值小于被查找值,则表明待查元素可能在表的后半部分,下次查找的起始位置通常应( )A.从MID/2位置开始 B.从MID位置开始C.从MID-1位置开始 D.从MID+1位置开始14. 当待排序序列中记录数较少或基本有序时,最适合的排序方法为( )A.直接插入排序法 B.快速排序法C.堆排序法 D.归并排序法15. 一组记录的关键码为(46,79,56,38,40,84),则利用快速排序的方法,以第一个记录为基准得到的一次划分结果为( )A.(38,40,46,56,79,84) B.(40,38,46,79,56,84)C.(40,38,46,56,79,84) D.(40,38,46,84,56,79)二、填空题16. 算法的空间性能是指算法需要的______。
全国2018年1月自考数据库系统原理试题课程代码:04735一、单项选择题(本大题共15小题,每小题2分,共30分)在每小题列出的四个备选项中只有一个是符合题目要求的,请将其代码填写在题后的括号内。
错选、多选或未选均无分。
1.数据库管理系统是( )A.采用了数据库技术的计算机系统B.包括DBA、计算机硬件及DB的系统C.位于用户与OS之间的数据管理软件D.包括OS在内的数据管理软件2.外模式DDL用来描述( )A.数据库的总体逻辑结构B.数据库的局部逻辑结构C.数据库的物理存储结构D.数据库的概念结构3.下列关于数据冗余的叙述中,不正确...的是( )A.冗余的存在容易破坏数据库的完整性B.冗余的存在给数据库的维护增加困难C.不应该在数据库中存储任何冗余数据D.冗余数据是指可由基本数据导出的数据4.适当调整DB的模式和内模式,使DB适应新的应用环境称为DB的( )A.重组织B.监控分析C.查询优化D.重构造5.关系模型中将不含有多余属性的超键称为( )A.内键B.候选键C.主键D.外键6.如果一个关系属于3NF,则它( )A.必然属于2NFB.必然属于4NFC.可能不属于2NFD.必然属于BCNF7.设有关系模式R(A,B,C),F是R上成立的FD集,F={B→C,C→A},那么分解ρ={AB,AC}相对于F( )A.是无损分解,也保持函数依赖B.是无损分解,但不保持函数依赖C.不是无损分解,但保持函数依赖D.既不是无损分解,也不保持函数依赖8.已知关系S1和S2如下表所示,则S1与S2进行并运算,其结果的元组数为( )12A.0B.4C.5D.69.设有关系R 和S ,与R —S 等价的元组表达式是( )A.{t|R(t)V ┐S(t)}B.{t|R(t)∧┐S(t)}C.{t|∃u(R(t)∨┐S(u))}D.{t|∃u(R(t) ∧┐S(u))}10.在SQL 语言中,用于测试列值非空的短语是( )A.IS NOT EMPTYB.NOT UNIQUEC.IS NOT NULLD.NOT EXISTS11.SQL 语言中,条件“年龄BETWEEN 20 AND 30”表示年龄在20至30之间,且( )A.包括20岁和30岁B.不包括20岁和30岁C.包括20岁但不包括30岁D.包括30岁但不包括20岁12.要求事务在读取数据前先加共享锁,且直到该事务执行结束时才释放相应的锁,这种封锁协议是( )A.一级封锁协议B.二级封锁协议C.三级封锁协议D.两段锁协议13.断言是DBS 采用的( )A.安全性措施B.完整性措施C.恢复措施D.并发控制措施 14.在对象联系图中,如果从A 到B 有双线箭头,则表示A 是B 的( )A.一个子类B.同类C.一个父类D.一个属性15.一个UML 类图,如下图所示。
浙江省2018年1月自学考试数据结构导论试题课程代码:02142一、单项选择题(在每小题的四个备选答案中,选出一个正确答案,并将正确答案的序号填在题干的括号内。
每小题1分,共14分)1.计算机算法指的是( )。
A.计算方法B.排序方法C.解决某一问题的有限运算序列D.调度方法2.在一个单链表中,若p↑结点不是最后结点,在p↑之后插入s↑结点,则实行( )。
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;3.某个向量第一元素的存储地址为100,每个元素的长度为2,则第五个元素的地址是( )。
A.110B.108C.100D.1204.循环队列用数组A[0..m-1]存放其元素值,已知其头尾指针分别是front和rear,则当前队列中的元素个数是( )。
A.(rear-front+m) MOD mB.rear-front+1C.rear-front-1D.rear-front5.栈和队列的共同特点是( )。
A.都是先进后出B.都是先进先出C.只允许在端点处插入和删除元素D.没有共同点6.深度为n的二叉树中所含叶子结点的个数最多为( )个。
A.2nB.nC.2n-1D.2n-17.树最适合用来表示( )。
A.有序数据元素B.无序数据元素C.元素之间具有分支层次关系的数据D.元素之间无联系的数据8.下面的二叉树中,( )不是完全二叉树。
9.下列说法错误的是( )。
A.一个图的邻接矩阵表示是唯一的B.一个图的邻接表表示是不唯一的C.一个图的生成树必为该图的极小连通子图D.一个无环有向图的拓扑排序序列必唯一10.设有6个结点的无向图,该图至少应有( )条边才能确保是一个连通图。
A.5B.6C.7D.811.对线性表进行二分查找时,要求线性表必须( )。
数据科学导论考试试题一、选择题(每题 3 分,共 30 分)1、以下哪项不是数据科学的主要研究内容?()A 数据预处理B 数据可视化C 数据库管理D 数学建模2、数据清洗的主要目的是()A 去除重复数据B 处理缺失值C 纠正错误数据D 以上都是3、在数据分析中,箱线图主要用于()A 展示数据的分布情况B 比较不同组数据的均值C 观察数据的趋势D 检测异常值4、以下哪种数据结构适合用于快速查找元素?()A 链表B 栈C 队列D 二叉搜索树5、聚类分析属于()A 有监督学习B 无监督学习C 强化学习D 半监督学习6、决策树算法在数据挖掘中用于()A 分类B 回归C 聚类D 关联规则挖掘7、以下哪项不是数据仓库的特点?()A 面向主题B 集成性C 易变性D 时变性8、数据挖掘中的关联规则挖掘,常用的算法是()A Apriori 算法B KMeans 算法C C45 算法D ID3 算法9、以下关于数据隐私保护的方法,错误的是()A 数据加密B 数据匿名化C 数据共享D 差分隐私10、数据科学项目中,最重要的步骤之一是()A 数据收集B 模型选择C 模型评估D 问题定义二、填空题(每题 3 分,共 30 分)1、数据的质量可以从_____、完整性、一致性、准确性和时效性等方面进行评估。
2、常见的数据分析方法包括描述性分析、_____分析和预测性分析。
3、数据预处理中的特征工程包括特征提取、_____和特征选择。
4、机器学习中的监督学习任务包括分类和_____。
5、数据库中的关系模型通过_____、行和列来组织数据。
6、数据可视化的原则包括准确性、_____和简洁性。
7、大数据的特点通常被概括为 5V,即 Volume(大量)、Velocity (高速)、Variety(多样)、Value(价值)和_____。
8、朴素贝叶斯分类器基于_____假设。
9、在数据挖掘中,分类算法的性能评估指标通常包括准确率、_____和 F1 值等。
全国2002年10月高等教育自学考试数据结构导论试题课程代码:02142一、单项选择题(在下列每小题四个备选答案中选出一个正确答案,并将其字母标号填入题干的括号内。
每小题2分,共30分)1.下列数据组织形式中,()的结点按逻辑关系依次排列形成一个“锁链”。
A.集合B.树形结构C.线性结构D.图状结构2.数据结构可以形式化地定义为(S,△),其中S指某种逻辑结构,△是指()A.S上的算法B.S的存储结构C.在S上的一个基本运算集D.在S上的所有数据元素3.下列说法正确的是()A.线性表的逻辑顺序与存储顺序总是一致的B.线性表的链式存储结构中,要求内存中可用的存储单元可以是连续的,也可以不连续C.线性表的线性存储结构优于链式存储结构D.每种数据结构都具有插入、删除和查找三种基本运算4.设非空单链表的数据域为data,指针域为next,指针p指向单链表中第i个结点,s指向已生成的新结点,现将s结点插入到单链表中,使其成为第i个结点,下列算法段能正确完成上述要求的是()A.s->next=p->next;p->next=s;B.p->next=s;s->next=p->next;C.s->next=p->next;p->next=s;交换p->data和s->data;D.p=s;s->next=p;5.稀疏矩阵一般采用()方法压缩存储。
A.三维数组B.单链表C.三元组表D.散列表6.树若用双亲链表表示,则()A.可容易地实现求双亲及子孙的运算B.求双亲及子孙的运算均较困难C.可容易地实现求双亲运算,但求子孙运算较困难D.可容易地实现求子孙运算,但求双亲运算较困难7.将一棵有50个结点的完全二叉树按层编号,则对编号为25的结点x,该结点()A.无左、右孩子B.有左孩子,无右孩子C.有右孩子,无左孩子D.有左、右孩子8.用邻接表作为有向图G的存储结构。
全国自学考试数据结构导论试题及答案4套第一套试题一、选择题(每题4分,共40分)1. 下列哪个数据结构是一种非线性结构?A. 数组B. 栈C. 队列D. 树2. 下列哪种算法不适用于解决排序问题?A. 冒泡排序B. 快速排序C. 深度优先搜索D. 归并排序3. 在数据结构中,堆的底层实现通常采用哪种数据结构?A. 数组B. 栈C. 链表D. 队列4. 下列哪个选项是描述图结构的准确说法?A. 图结构是一种线性结构B. 图结构由节点和指向节点的边构成C. 图结构不能存储数据D. 图结构不支持插入和删除操作5. 下列哪个排序算法具有最坏时间复杂度为O(nlogn)?A. 冒泡排序B. 插入排序C. 选择排序D. 希尔排序二、填空题(每题4分,共40分)1. 在二叉树中,每个节点最多有____个子节点。
2. 图的两个顶点之间的路径长度是指连接这两个顶点所需的____数。
3. 链表是一种____结构。
4. 快速排序算法的核心思想是____。
5. 栈和队列都属于线性结构,其主要区别在于____操作的限制。
三、简答题(每题10分,共30分)1. 请简要描述栈的特点以及栈的应用场景。
2. 请简要介绍图的基本概念,并说明图的应用领域。
3. 请解释递归算法的原理,并给出一个使用递归算法解决问题的例子。
四、编程题(共30分)请使用任意编程语言实现一个简单的栈数据结构,并编写测试代码进行验证。
第二套试题一、选择题(每题4分,共40分)1. 在二叉搜索树中,中序遍历的结果是____。
A. 升序排列B. 降序排列C. 随机排序D. 不确定的排序2. 在哈希表结构中,解决冲突问题的常用方法是____。
A. 线性探测B. 链地址法C. 开放地址法D. 扩容法3. AVL树是一种____。
A. 二叉搜索树B. 哈希表C. B树D. 红黑树4. 以下哪个算法不是用于解决查找问题?A. 二分查找B. 深度优先搜索C. 广度优先搜索D. 哈希查找5. 以下哪个数据结构不支持随机访问元素?A. 数组B. 栈C. 链表D. 哈希表二、填空题(每题4分,共40分)1. 在二叉树中,每个节点最多有____个子节点。
全国2018年1月高等教育自学考试数据结构导论试题课程代码:02142一、单项选择题(本大题共15小题,每小题2分,共30分)在每小题列出的四个备选项中只有一个是符合题目要求的,请将其代码填写在题后的括号内。
错选、多选或未选均无分。
1.数据的四种基本逻辑结构是指( )A.数组、链表、树、图形结构B.线性表、链表、栈队列、数组广义表C.线性结构、链表、树、图形结构D.集合、线性结构、树、图形结构2.数据结构中,通常采用两种方法衡量算法的时间复杂性,即( )A.最大时间复杂性和最小时间复杂性B.最好时间复杂性和最坏时间复杂性C.部分时间复杂性和总体时间复杂性D.平均时间复杂性和最坏时间复杂性3.下列关于线性表的叙述中,不正确的是( )A.线性表是n个结点的有穷序列B.线性表可以为空表C.线性表的每一个结点有且仅有一个前趋和一个后继D.线性表结点间的逻辑关系是1:1的联系4.在一个单链表中,若p所指结点不是最后结点,则删除p所指结点的后继结点的正确操作是( )A.p=p->nextB.p->next=p->nextC.p->next=p->next->nextD.p->next=p5.栈和队列( )A.共同之处在于二者都是先进先出的特殊的线性表B.共同之处在于二者都是先进后出的特殊的线性表C.共同之处在于二者都只允许在顶端执行删除操作D.没有共同之处6.二维数组A[5][6]采用按列为主序的存储方式,每个元素占3个存储单元,若A[0][0]的存储地址是100,则A[4][3]的存储地址是( )A.127B.142C.150D.1577.深度为k的二叉树至多有( )A.2k个结点B.2k-1个结点C.2k-1个结点D.2k-1-1个结点8.对于如图所示二叉树采用中根遍历,正确的遍历序列应为( )A.ABCDEFB.ABECDFC.CDFBEAD.CBDAEF129.下面关于生成树的描述中,不正确的是( )A.生成树是树的一种表现形式B.生成树一定是连通的C.生成树一定不含有环D.若生成树顶点个数为n ,则其边数一定为n-110.图的邻接表如下所示,从顶点V 1出发采用深度优先搜索法遍历该图,则可能的顶点序列 是()A.V 1V 2V 3V 4V 5B.V 1V 2V 3V 5V 4C.V 1V 4V 3V 5V 2D.V 1V 3V 4V 5V 211.下列查找方法中,不属于动态的查找方法是( )A.二叉排序树法B.平衡树法C.散列法D.斐波那契查找法12.要解决散列引起的冲突问题,常采用的方法有( )A.数字分析法、平方取中法B.数字分析法、线性探测法C.二次探测法、平方取中法D.二次探测法、链地址法13.用于外存储器的数据组织结构散列文件,主要适用于( )A.顺序存取B.随机存取C.索引存取D.以上三种都可以14.堆排序属于一种选择排序,其时间复杂性为( )A.O(1)B.O(nlog 2n)C.O(n)D.O(n 2)15.下列排序方法中,属于不稳定的排序方法是( )A.直接插入排序法B.冒泡排序法C.基数排序法D.归并排序法二、填空题(本大题共13小题,每小题2分,共26分)请在每小题的空格中填上正确答案。
全国2003年1月高等教育自学考试数据结构导论试题课程代码:02142一、单项选择题(在每小题的四个备选答案中,选出一个正确答案,并将正确答案的序号填在题干的括号内。
错选、多选或未选均无分。
每小题2分,共30分)1.下列数据结构中,( )不都是线性结构。
A.栈和队列B.队列和数组C.数组和串D.文件和队列2.为了最快地对线性结构的数据进行某数据元素的读取操作,则其数据存储结构宜采用( )方式。
A.顺序存储B.链式存储C.索引存储D.散列存储3.设双链表中结点的前趋指针和后继指针的域名分别为t1和r1,则删除双链表中指针s所指结点的操作为( )A.s->t1->r1=s->t1;s->r1->t1=s->r1;B.s->t1->r1=s->r1;s->r1->t1=s->t1;C.s->r1=s->t1->r1;s->t1=s->r->t1;D.s->t1=s->t1->r1;s->r1=s->r->t1;4.假设left和right为双向链表中指向直接前趋结点和直接后继结点的指针域,现要把一个指针s所指的新结点作为非空双链表中q所指地点(中间结点)的直接后继结点插入到该双向链表中,则下列算法段能正确完成上述要求的是( )A.q->right=s; s->left=q; q->right->left=s; s->right=q->right;B.s->left=q; q->right=s; q->right->left=s; s->right=q->right;C.s->left=q; s->right=q->right; q->right->left=s; q->right=s;D.以上都不对5.由下列三棵树组成转的森林换成一棵二叉树为( )6.具有100个结点的完全二叉树的深度为( )A.6B.7C.8D.97.已知一个稀疏矩阵的三元组表如下:(1,2,3),(1,6,1),(3,1,5),(3,2,-1),(4,5,4),(5,1,-3),则其转置矩阵的三元组表中第3个三元组为( )A.(2,1,3)B.(3,1,5)C.(3,2,-1)D.(2,3,-1)8.无向图的邻接矩阵是一个( )A.对称矩阵B.零矩阵C.上三角矩阵D.对角矩阵9.下列说法中正确的是( )A.一个具有n个顶点的无向完全图的边数为n(n-1)B.连通图的生成树是该图的一个极大连通子图C.图的广度优先搜索是一个递归过程D.对于非连通图的遍历过程中每调用一次深度优先搜索算法都得到该图的一个连通分量10.顺序查找法与二分查找法对存储结构的要求是( )A.顺序查找与二分查找均只适用于顺序表B.顺序查找与二分查找既适用于顺序表,也适用于链表C.顺序查找只适用于顺序表D.二分查找只适用于顺序表11.在开散列表上,每个地址单元所链接的同义词表( )A.其键值相同B.其元素值相同C.其散列地址相同D.其含义相同12.散列文件中的记录通常成组存放,若干个记录组成一个存储单位,这个存储单位称为( )A.磁道B.块C.柱面D.桶13.索引非顺序文件中的索引表是( )A.非稠密索引B.稠密索引C.主索引D.多级索引14.对n个记录的文件进行堆排序,最坏情况下的执行时间为( )A.O(log2n)B.O(nlog2n)C.O(n)D.O(n2)15.一组记录的关键码为(46,79,56,38,40,84),则利用快速排序方法,以第一个记录为基准得到的一次划分结果为( )A.38,40,46,56,79,84B.40,38,46,79,56,84C.40,38,46,56,79,84D.40,38,46,84,56,79二、填空题(每小题2分,共26分)请在每小题的空格中填上正确答案。
2005年1月全国邮电管理工程数据库及其应用试卷(1)
各位读友大家好,此文档由网络收集而来,欢迎您下载,谢谢一、单项选择题(本大题共20小题,每小题2分,共40分)
在每小题列出的四个备选项中只有一个是符合题目要求的,请将其代码填写在题后的括号内。
错选、多选或未选均无分。
1.下列关于“联系”的描述,正确的是()
a.联系不是实体,也没有属性b.联系是实体,但没有属性
c.联系不是实体,但有属性d.联系是实体,也有属性
2.在层次模型中,用来表示记录类型及其联系的结构是()
a.层次b.树
c.网状d.关系
3.下面对网状模型描述错误的是()
a.结点间的联系不受层次限制,可以任意发生联系
b.有一个以上结点无父结点
c.至少有一个结点有多于一个父结点
d.在具体实现上,直接支持多对多的联系
4.设r(u)是属性集合u上的一个关系模式,x、y是u的子集。
x′是x的真子集,若对于r(u)的任何一个可能的关系,都有x→y,但x′→/y,则()
a.y传递函数依赖于xb.y完全函数依赖于x
c.x为u的候选键d.r属于2nf
5.集合r与s的交可以用关系代数的基本运算表示为()
a.r-(r-s)b.r+(r-s)
c.r-(s-r)d.s-(r-s)
6.包含在候选键中的属性,称为
()
a.非主属性b.主属性
c.域d.外部键
7.关系r与s的连接操作用关系代数的基本运算表示为()
a.r(a)θs(b)b.σaθb(r×s)
各位读友大家好,此文档由网络收集而来,欢迎您下载,谢谢。
一、单项选择题(本大题共15小题,每小题2分,共30分)
在每小题列出的四个备选项中只有一个是符合题目要求的,请将其代码填写在题后的括号内。
错选、多选或未选均无分。
1.数据的四种基本逻辑结构是指( )
A.数组、链表、树、图形结构
B.线性表、链表、栈队列、数组广义表
C.线性结构、链表、树、图形结构
D.集合、线性结构、树、图形结构
2.数据结构中,通常采用两种方法衡量算法的时间复杂性,即( )
A.最大时间复杂性和最小时间复杂性
B.最好时间复杂性和最坏时间复杂性
C.部分时间复杂性和总体时间复杂性
D.平均时间复杂性和最坏时间复杂性
3.下列关于线性表的叙述中,不正确的是( )
A.线性表是n个结点的有穷序列
B.线性表可以为空表
C.线性表的每一个结点有且仅有一个前趋和一个后继
D.线性表结点间的逻辑关系是1:1的联系
4.在一个单链表中,若p所指结点不是最后结点,则删除p所指结点的后继结点的正确操作是( )
A.p=p->next
B.p->next=p->next
C.p->next=p->next->next
D.p->next=p
5.栈和队列( )
A.共同之处在于二者都是先进先出的特殊的线性表
B.共同之处在于二者都是先进后出的特殊的线性表
C.共同之处在于二者都只允许在顶端执行删除操作
D.没有共同之处
6.二维数组A[5][6]采用按列为主序的存储方式,每个元素占3个存储单元,若A[0][0]的存储地址是100,则A[4][3]的存储地址是( )
A.127
B.142
C.150
D.157
8.对于如图所示二叉树采用中根遍历,正确的遍历序列应为( )
A.ABCDEF
B.ABECDF
C.CDFBEA
D.CBDAEF
9.下面关于生成树的描述中,不正确的是( )
A.生成树是树的一种表现形式
B.生成树一定是连通的
C.生成树一定不含有环
D.若生成树顶点个数为n,则其边数一定为n-1
10.图的邻接表如下所示,从顶点V1出发采用深度优先搜索法遍历该图,则可能的顶点序列
是( )
11.下列查找方法中,不属于动态的查找方法是( )
A.二叉排序树法
B.平衡树法
C.散列法
D.斐波那契查找法
12.要解决散列引起的冲突问题,常采用的方法有( )
A.数字分析法、平方取中法
B.数字分析法、线性探测法
C.二次探测法、平方取中法
D.二次探测法、链地址法
13.用于外存储器的数据组织结构散列文件,主要适用于( )
A.顺序存取
B.随机存取
C.索引存取
D.以上三种都可以
14.堆排序属于一种选择排序,其时间复杂性为( )
A.O(1)
B.O(nlog2n)
C.O(n)
D.O(n2)
15.下列排序方法中,属于不稳定的排序方法是( )
A.直接插入排序法
B.冒泡排序法
C.基数排序法
D.归并排序法
二、填空题(本大题共13小题,每小题2分,共26分)
请在每小题的空格中填上正确答案。
错填、不填均无分。
16.根据不同的描述方式,对数据的操作运算通常可分为加工型运算和__________两种基本类型。
17.数据结构中的算法,通常采用最坏时间复杂度和____________两种方法衡量其效率。
18.判断带头结点head的单链表为空的条件是___________。
19.若顺序表每个元素长度均为5,其中第一个元素的存储地址为30,则第6个元素的存储地址为___________。
20.若front和rear分别表示循环队列Q的头指针和尾指针,m0表示该队列的最大容量,则判断循环队列为满的条件是___________。
21.对于顺序存储结构的二维数组,通常采用___________两种存放方式存储数据元素。
22.若某二叉树的先根遍历序列为CEDBA,中根遍历序列为DEBAC,则其后根遍历序列为___________。
23.具有n个结点的完全二叉树,其深度为___________。
24.图主要采用___________两种存储结构存放。
25.索引顺序查找通常分两个阶段进行,首先采用顺序查找法或二分法确定所要查找的块,然后再用___________法在块中找到具体的元素值。
26.二叉排序树是一种特殊的有序表,若要保证输出序列其键值完全按递增排列,则应对二叉排序树采用___________法遍历。
27.文件常见的存储结构有顺序文件、链接文件、索引文件和___________四种。
28.在各种内部排序中,占用存储空间较大的排序通常是___________排序。
三、应用题(本大题共5小题,每小题6分,共30分)
31.已知散列函数为H(key)=key%7,散列表长度为7(散列地址空间为0..6),待散列序列为:(25,48,32,50,68)。
要求:
(1)根据以上条件构造一散列表,并用线性探测法解决有关地址冲突;
(2)若要用该散列表查找元素68,给出所需的比较次数。
32.已知一组键值序列为(38,64,73,52,40,37,56,43),试采用快速排序法对该组序列
作升序排序,并给出每一趟的排序结果。
33.已知一组键值序列(26,21,32,56,78,89,90),试采用二路归并排序法对该组序列作升序排序,并给出每一趟的排序结果。
四、设计题(本大题共2小题,每小题7分,共14分)
34.试编写一算法,以完成在带头结点单链表L中第i个位置前插入元素X的操作。
35.二叉树是由所有度数不大于2的结点构成的一种特定树,若某结点度为2,则该结点有左
右两个孩子,请编写算法计算一二叉树所有度数为2的结点个数。