《公共基础知识卡》PPT课件.ppt

1,2,3,数据结构,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,典型考题分析,47,【例1-1】问题处理方案的正确而完整的描述称为 。（2005年4月） 答案 算法,48,【例1-2】算法复杂度主要包括时间复杂度和 复杂度。（2005年9月） 答案 空间,49,【例1-3】算法的时间复杂度是指_。 A）执行算法程序所需要的时间 B）算法程序的长度 C）算法执行过程中所需要的基本运算次数 D）算法程序中的指令条数 答案 C,50,【例1-4】算法的空间复杂度是指_。 A）算法程序的长度 B）算法程序中的指令条数 C）算法程序所占的存储空间 D）算法执行过程中所需要的存储空间 答案 D,51,【例1-5】下列叙述中正确的是 。（2006年9月） A）一个算法的空间复杂度大，则其时间复杂度也必定大 B）一个算法的空间复杂度大，则其时间复杂度必定小 C）一个算法的时间复杂度大，则其空间可复杂度必定小 D）上述三种说法都不对 答案 D,52,【例1-6】下列叙述中正确的是 。（2005年9月） A）一个逻辑数据结构只能有一种存储结构 B）数据的逻辑结构属于线性结构，存储结构属于非线性结构 C）一个逻辑数据结构可以有多种存储结构，且各种存储结构不影响数据处理的效率 D）一个逻辑数据结构可以有多种存储结构，且各种存储结构影响数据处理的效率 答案 D,53,【例1-7】数据结构分为逻辑结构和存储结构，循环队列属于 结构。（2005年9月） 答案 逻辑,54,【例1-8】数据结构分为线性结构和非线性结构，带链的队列属于 。（2006年9月） 答案 线性结构,55,【例1-9】下列叙述中正确的是_。（2006年4月） A）线性链表是线性表的链式存储结构 B）栈与队列是非线性结构 C）双向链表是非线性结构 D）只有根结点的二叉树是线性结构 答案 A,56,【例1-10】某线性表采用顺序存储结构，每个元素占4个存储单元，首地址为200，则第12个元素的存储地址为 。 A）248 B）247 C）246 D）244 答案 D a=a0+(i-1)k,57,【例1-11】在长度为n的顺序表的第i（1in+1）个位置上插入一个元素，元素的移动次数为 。 A）n-i+1 B）n-i C）i D）i-1 答案 A,58,【例1-12】在一个长度为n的顺序表中，删除第i（1in）个元素时，需要移动的元素个数为 。 A）n-i+1 B）n-i C）i D）i-1 答案 B,59,【例1-13】以下描述的中，不是线性表的顺序存储结构的特征的是 。 A）不便于插入和删除 B）需要连续的存储空间 C）可随机访问 D）需另外开辟空间来保存元素之间的关系 答案 D,60,【例1-14】下列关于栈的描述中错误的是_。（2005年4月） A）栈是先进后出的线性表 B）栈只能顺序存储 C）栈具有记忆作用 D）对栈的插入与删除操作中，不需要改变栈底指针 答案 B,61,【例1-15】栈和队列的共同点是_。 A）都是先进先出 B）都是先进后出 C）只允许在端点处插入和删除元素 D）没有共同点 答案 C,62,【例1-16】栈的输入序列为1，2，3，n-1，n，输出序列的第1个元素为n，则第个输出元素为_。 A）n-i+1 B）n-1 C）i D）哪个元素无所谓 答案 A,63,【例1-17】一个队列的入队序列是1、2、3、4，则队列的输出序列是 。 A）4、3、2、1 B）1、2、3、4 C）1、4、3、2 D）3、2、4、1 答案 B,64,【例1-18】队列是限定只能在表的一端进行插入和在另一端进行删除操作的线性表。允许插入的一端称作_。 答案 队尾,65,【例1-19】下列对于线性链表的描述中正确的是 。（2005年4月） A）存储空间不一定是连续，且各元素的存储顺序是任意的 B）存储空间不一定是连续，且前件元素一定存储在后件元素的前面 C）存储空间必须连续，且各前件元素一定存储在后件元素的前面 D）存储空间必须连续，且各元素的存储顺序是任意的 答案 A,66,【例1-20】下列叙述中，错误的是 。 A）线性表是由n个数据元素组成的一个有限序列 B）线性表是一种线性结构。 C）线性表的所有结点有且只有一个前件和一个后件 D）线性表可以是空表。 答案 C,67,【例1-21】下列描述的不是链表的优点是_。 A）逻辑上相邻的结点物理上不必邻接 B）插入、删除运算操作方便，不必移动结点 C）所需存储空间比线性表节省 D）无需事先估计存储空间的大小 答案 C,68,【例1-23】一棵二叉树第六层（根结点为第一层）的结点数最多为 个。（2005年9月） 答案 32,69,【例1-24】深度为5的二叉树至多有_个结点。 A）16 B）32 C）31 D）10 答案 C,70,【例1-25】设树T的度为4，其中度为1，2，3，4的结点个数分别为4，2，1，1。则T中的_。 A）8 B）7 C）6 D）5 答案 A 叶子结点基数为1，每增加1个度为k的结点增加k-1个叶子结点 n1=4 n2=2 n3=1 n4=1 0X4 + 1X2 + 2x1 + 3x1 +1=8,71,【例1-26】某二叉树中度为2的结点有18个，则该二叉树中有 个叶子结点。（2005年4月） 答案 19,72,【例1-27】具有88个结点的二叉树，其深度至少为_。 答案 7 64=88128,73,【例1-28】在深度为7的满二叉树中，叶子结点的个数为（2006年4月） A）32 B）31 C）64 D）63 答案 C,74,【例1-29】设一棵完全二叉树共有700个结点，则在该二叉树中有_个叶子结点。 答案 350 n0=n2+1,完全二叉树n1=0或1 最后结点（第700个）的父结点为350（最后父结点）其余350为叶子结点,75,【例1-30】对如图1-30所示的二叉树，进行后序遍历的结果为 。（2006年4月） A）ABCDEF B）DBEAFC C）ABDECF D）DEBFCA 答案 D,76,【例1-31】假设一棵二叉树的后序遍历序列为DGJHEBIFCA，中序遍历序列为DBGEHJACIF，则其前序遍历序列为 。 答案：ABDEGHJCFI,77,【例1-32】对长度为n的线性表进行顺序查找，在最坏情况下所需要的比较次数为_。（2005年4月） A）log2n B）n/2 C）n D）n+l 答案 C,78,【例1-33】下列数据结构中，能用二分法进行查找的是 。（2005年9月） A）顺序存储的有序线性表 B）线性链表 C）二叉链表 D）有序线性链表 答案 A,79,【例1-34】已知一个有序表为（13，18，24，35，47，50，62，83，90，115，134），当使用二分法查找值为90的元素时，查找成功的比较次数为 。 A）1 B）2 C）3 D）9 答案 B,80,【例1-35】对长度为10的线性表进行冒泡排序，最坏情况下需要比较的次数为 。（2006年4月） 答案 45,81,【例1-36】在排序算法中，两两比较待排序的记录，当发现不满意顺序要求时，变更它们的相对位置，这就是 排序。 A）希尔排序 B）交换排序 C）插入排序 D）选择排序 答案 B,82,【例1-37】设待排序关键码序列为（33，18，9，25，67，82，53，95，12，70），要按关键码值递增的顺序排序，采取以第一个关键码为基准元素的快速排序法，第一趟排序完成后关键码33被放到了第_位置。 A）3 B）5 C）7 D）9 答案 B,83,【例1-38】对于给定的一组关键字 （12，2，16，30，8，28，4，10，20，6，18），按照希尔排序算法 进行递增排序 （增量为 5 ）， 第一趟排序后得到 的结果是 。 答案 12，2，10，20，6，28，4，16，30，8，18,84,【例1-39】对数据元素序列进行排序，原序列及前三趟排序结束时的结果为： 原序列：49，72，68，13，38，50，97，27 第一趟：13，72，68，49，38，50，97，27； 第二趟：13，27，68，49，38，50，97，72； 第三趟：13，27，38，49，68，50，97，72。 该排序采用的方法是_。 A）简单插入排序法 B）冒泡排序法 C）简单选择排序法 D）快速排序法 答案 C,85,【例1-40】以下各组序列中，属于堆的是_。 A）19，34，26，97，56，75 B）97，26，34，75，19，56 C）19，56，26，97，34，75 D）19，75，34，26，97，56 答案 A 堆：父=子或父=子,86,【例1-41】对于长度为n的线性表，在最坏情况下，下列各排序法所对应的比较次数中正确的是_。（2005年4月） A）冒泡排序为n/2 B）冒泡排序为n C）快速排序为n D）快速排序为n(n-1)/2 答案 D,87,2.4 典型考题分析,【例2-1】从程序设计方法和技术的发程序角度来说，程序设计主要经历了结构化设计和_的程序设计阶段。 答案 面向对象,88,2.4 典型考题分析,【例2-2】对建立良好的程序设计风格，下面描述正确的是_。 A）程序应简单、清晰、可读性好 B）符号名的命名只要符合语法 C）充分考虑程序的执行效率 D）程序的注释可有可无 答案 A,89,2.4 典型考题分析,【例2-5】在设计程序时，应采纳的原则之一是_。 A）程序结构应有助于读者理解 B）不限制GOTO语句的使用 C）减少或取消注解行 D）程序越短越好 答案 A,90,2.4 典型考题分析,【例2-6】下列选项中不属于结构化程序设计方法的是_。（2006年4月） A）自顶向下 B）逐步求精 C）模块化 D）可复用 答案 D,91,2.4 典型考题分析,【例2-7】下列选项不符合良好程序设计风格的是_。（2006年9月） A）源程序要文档化 B）数据说明的次序要规范化 C）避免滥用 GOTO 语句 D）模块设计要保证高耦合、高内聚 答案 D,92,2.4 典型考题分析,【例2-8】结构化程序设计的三种基本控制结构是_。 A）过程、子程序和分程序 B）顺序、选择和重复 C）递归、堆栈和队列 D）调用、返回和转移 答案 B,93,2.4 典型考题分析,【例2-9】结构化程序设计主要强调的是_。 A）程序的规模 B）程序的易读性 C）程序的执行效率 D）程序的可移植性 答案 B,94,2.4 典型考题分析,【例2-10】关于结构化程序设计原则和方法的描述错误的是_。 A）选用的控制结构只准许有一个入口和一个出口 B）复杂结构应该用嵌套的基本控制结构进行组合嵌套来实现 C）不允许使用GOTO语句 D）语言中所没有的控制结构，应该采用前后一致的方法来模拟 答案 C,95,2.4 典型考题分析,【例2-12】在面向对象方法中，类的实例称为_。（2005年4月） 答案 对象,96,2.4 典型考题分析,【例2-14】一个对象在收到消息时，要予以响应。不同的对象收到同一消息可以产生完全不同的结果，这一现象叫做对象的_。 A）继承性 B）多态性 C）抽象性 D）封装性 答案 B,97,2.4 典型考题分析,【例2-15】在面向对象程序设计中，从外面看只能看到对象的外部特征，而不知道也无需知道数据的具体结构以及实现操作的算法，这称为对象的_。 答案 封装性,98,2.4 典型考题分析,【例2-16】使用已经存在的类作为基础建立新类的定义，这种技术叫做类的_。 答案 继承,99,2.4 典型考题分析,【例2-17】一个类允许有多个父类，这种继承称为_。 答案 多重继承,100,【例3-1】下列描述中正确的是_。（2005年4月） A）程序就是软件 B）软件开发不受计算机系统的限制 C）软件既是逻辑实体，又是物理实体 D）软件是程序、数据与相关文档的集合 答案 D,101,【例3-4】下列叙述中正确的是_。（2005年9月） A）软件交付使用后还需要进行维护 B）软件一旦交付使用就不需要再进行维护 C）软件交付使用后其生命周期就结束 D）软件维护是指修复程序中被破坏的指令 答案 A,102,【例3-5】下列选项中不属于软件生命周期开发阶段任务的是_。（2006年9月） A）软件测试 B）概要设计 C）软件维护 D）详细设计 答案 C,103,【例3-17】两个或两个以上模块之间关联的紧密程度称为_。（2006年4月） A）耦合度 B）内聚度 C）复杂度 D）数据传输特性 答案 A,104,【例3-29】程序测试分为静态分析和动态测试，其中_是指不执行程序，而只是对程序文本进行检查，通过阅读和讨论，分析和发现程序中的错误。（2006年4月） 答案 静态分析,105,【例3-30】使用白盒测试方法时，确定测试数据应根据_和指定的覆盖标准。 A）程序的内部逻辑 B）程序的复杂结构 C）使用说明书 D）程序的功能 答案 A,106,【例3-31】等价类型划分法是_测试常用的方法。 答案 黑盒,107,【例3-34】_的任务是诊断和改正程序中的错误。（2006年9月） 答案 调试,108,【例3-35】下列叙述中正确的是_。（2005年9月） A）程序设计就是编制程序 B）程序的测试必须由程序员自己去完成 C）程序经调试改错后还应进行再测试 D）程序经调试改错后不必进行再测试 答案 C,109,【例3-28】为了提高测试的效率，应该_。 A）随机地选取测试数据 B）取一切可能的输入数据作为测试数据 C）在完成编码以后制定软件的测试计划 D）选择发现错误可能性大的数据作为测试数据 答案 D,110,【例3-19】为了使模块尽可能独立，要_。（2005年4月） A）模块的内聚程度要尽量高，且各模块间的耦合程度要尽量强 B）模块的内聚程度要尽量高，且各模块间的耦合程度要尽量弱 C）模块的内聚程度要尽量低，且各模块间的耦合程度要尽量弱 D）模块的内聚程度要尽量低，且各模块间的耦合程度要尽量强 答案 B,111,【例3-8】计算机辅助软件工程，简称为_。 A）SA B）SD C）SC D）CASE 答案 D,112,【例4-1】数据库技术的根本目标是要解决数据的_。（2006年9月） A）存储问题 B）共享问题 C）安全问题 D）保护问题 答案 B,113,【例4-2】数据库DB，数据库系统DBS，数据库管理系统DBMS之间的关系是_。（2006年4月） A）DB包含DBS和DBMS B）DBMS包含DB和DBS C）DBS包含DB和DBMS D）没有任何关系 答案 C,114,【例4-3】数据库系统的核心是_。（2005年9月） A）数据模型 B）数据库管理系统 C）数据库 D）数据库管理员 答案 B,115,【例4-4】DBA是数据库系统的一个重要组成，有很多职责。以下选项不属于DBA职责的是_。 A）定义数据库的存储结构和存取策略 B）定义数据库的结构 C）定期对数据库进行重组和重构 D）设计和编写应用系统的程序模块 答案 D,116,【例4-5】数据管理技术发展过程经过人工管理、文件系统和数据库系统三个阶段，其中数据独立性最高的阶段是_。（2005年9月） 答案 数据库系统,117,【例4-10】数据库的3级模式之间存在映射关系正确的是_。 A）外模式/内模式 B）外模式/概念模式 C）外模式/外模式 D）概念模式/概念模式 答案：B,118,【例4-12】用树形结构表示实体之间联系的模型是_。（2005年4月） A）关系模型 B）网状模型 C）层次模型 D）以上三个都是 答案 C,119,【例4-13】“商品”与“顾客”两个实体集之间的联系一般是_。（2006年4月） A）一对一 B）一对多 C）多对一 D）多对多 答案 D,120,【例4-14】在E-R图中，用来表示实体的图形是_。（2006年4月） A）矩形 B）椭圆形 C）菱形 D）三角形 答案 A,121,【例4-15】在下面列出的数据模型中，_是概念数据模型。 A）关系模型 B）层次模型 C）网状模型 D）实体-联系模型 答