教师招聘考试计算机专业试卷.doc

教师招聘计算机考试专业试卷内容包括1、计算机基础知识部分2、数据结构部分3、程序设计部分计算机基础知识部分1、CPU的主要功能是进行（ ）。A、算术运算 B、逻辑运算C、算术逻辑运算 D、算术逻辑运算与全机的控制答：D分析：中央处理器（CPU），它包括运算器和控制器，其中运算器完成各种运算任务（包括算术运算与逻辑运算两大类），控制器根据指令的内容产生指挥其他硬件部件直辖市工作的控制信号。所以正确答D。2、CPU能直接访问的存储部件是（ ）。A、软盘 B、硬盘 C、内存 D、光盘答：C分析：内存与外存有一个重要区别：内存能够被CPU直接访问，而外存的信息只能由CPU通过输入输出操作来存取，不能与CPU直接交换信息。所以，当前CPU正在执行的程序、正在处理的数据都存在内存里，外存上保存的程序、数据只有先调入内存，才能再被CPU访问。换句话说，内存是工作存储器，外存是后备性的存储器，是内存的扩充与备份。内、外存组成这样一种层次结构，在存取速度、容量、价革几方面实现了合理的配合。本题正确答是C。3、如果一个存储单元存放一个字节，那么一个64KB的存储单元共有（ ）个存储单元，用十六进制的地址码则编号为0000（ ）。A、64000 B、65536 C、10000H D、0FFFFH答：依次为B和D分析：存储器的容量是指它能存放多少个字节的二进制信息，1KB代表1024个字节，64KB就是65536个字节。内存储器是由若个存储单元组成的，每个单元有一个唯一的序号以便识别，这个序号称为地址。通常一个存储单元存放一个字节，那么总共就有65536个存储单元。要有65536个地址，从0号编起，最末一个地址号为65536-1=65535，即十六进制FFFF。所以本题的两个正确答依次为B和D。注意地址的编号都从0开始，因此最高地址等于总个数减1。4、计算机中访问速度最快的存储器是（ ）。A、RAM B、Cache C、光盘 D、硬盘答：B分析：在微机存储器的层次结构里，内存、外存是两大层次，而内存又可分为高速缓冲存储器（Cache）和主存。主存是内存的主体，Cache也用半导体电路构成，访问速度很高，但容量很小，有的甚至就做在CPU芯片内，所以严格地说，Cache只起一个缓冲器的作用，其中保存着最近一段时间内刚刚从内存读来的信息。每当CPU要访问内存时，将先到Cache中查找，如果没有再到主存中去做实际的访问操作。所以，存取速度最高的是Cache，其次是主存（如果没有Cache则最高的就是主存）。所以本题的正确答是B。5、通常所说的CPU芯片包括（ ）。A、控制器、运算器和寄存器组 B、控制器、运算器和内存储器C、内存储器和运算器 D、控制器和内存储器答：A分析：CPU芯片是微机硬件系统的核心，又称微处理器芯片，其中包括控制器、运算器和寄存器组。注意：CPU不仅包括控制器和运算器，而且包括寄存器组。寄存器组是CPU内部的一些存储单元，例如，存储程序运行状态的状态寄存器，存储正在运行指令的指令寄存器，存储将要执行的下一条指令地址的程序计数器，存储参与运算的数据及运算结果的累加器、寄存器等。所以正确答是A。6、在内存中，每个基本单位都被赋予一个惟一的序号，这个序号称为（ ）。A、字节 B、编号 C、地址 D、容量答：C分析：在内存中，通常是以字节为基本单位，所赋予的序号称为地址，在读写过程中都必须给出地址，才能进行读写。所以正确答为C。7、在微机的性能指标中，用户可用的内存储器容量是指（ ）。A、ROM的容量 B、RAM的容量C、ROM和RAM的容量总和 D、CD-ROM的容量答：B分析：ROM是只读存储器的英文简称，它对用户来说是只读而不能写的。只能有计算机生产厂商用特殊方式写入一些重要的软件和数据，如引导程序、监控程序等，断电后，其内容不会丢失。RAM是随机存储器的英文简称，由用户随时对其进行读写操作。CPU需要的数据只能从外存储器调入RAM，CPU根据程序来处理数据，处理完成的结果数据暂时存入RAM中。人们常说的可用的内存容量就是指RAM的容量。断电后，RAM中的数据将丢失。CD-ROM是只读光盘的英文简称。其特点也是一次性写入，写入的数据将永久保存在光盘上。CD-ROM属于外存，不属于内存。8、5.25英寸软盘片外框上有一个矩形缺口，其作用是（ ）。A、机械定位 B、“0”磁道定位C、写保护作用 D、磁道的起点定位答：C分析：5.25英寸软盘片的矩形缺口是写保护口，用于对盘片中的内容写保护，5.25英寸软盘用胶纸贴住此缺口不透光时即禁止写入，防止由于意外写操作而破坏原存储信息。9、DRAM存储器的中文含义是（ ）。A、静态随机存储器 B、静态只读存储器C、动态随机存储器 D、动态只读存储器答：C分析：RAM是随机存储器。随机存储器分为静态随机存储器和动态随机存储器。DRAM为动态随机存储器。半导体动态存储器DRAM的存储容量大，价革比静态存储器便宜。目前市场上多为动态随机存储器DRAM。10、在不同的计算机中，字节的长度是固定不变的。设计算机的字长是4B，那么意味着（ ）。A、该机最长可使用4B的字符串B、该机在CPU中一次可以处理32位C、CPU可以处理的最大数是24D、该机以4个字节为1个单位将信息存放在软盘上答：B分析：字节是计算机系统存储信息的基本单位，不同计算机中字节的长度是不变的，都占8位二进制位。字长是CPU一次处理的信息长度，不同计算机系统的字长是不同的。若计算机字长是4个字节，则意味着该机在CPU一次可以处理的信息长度为32位。11、计算机的I/O设备和主机之间的数据传送可通过（ ）或（ ）实现，其中远距离的数据通信一般通过（ ）来实现。A、串行接口 B、并行接口 C、双向接口 D、单向接口答：串行接口 并行接口 串行接口分析：I/O设备和主机之间的数据传送可通过并行接口和串行接口实现。其中串行接口由串行接口电路和串行接口信号线两部分组成。目前计算机常用的串行接口是RS-232C接口。用并行接口进行数据传输时若干位二进制位同时传输，这种接口的传输距离比较短，所以一般要进行远距离数据通信，通过串行接口来实现。12、高性能的多媒体计算机中，多采用（ ）。A、PCI B、EISA C、ISA D、MCA答：A分析：一般性能的多媒体计算机可以采用ISA总线结构；较高性能的多媒体计算机可采用EISA总线结构，PCI是总线的新技术，可满足许多多媒体应用程序对数据传输速率的要求，PCI为32/64位总线，它的数据传输速率也从132MB/S发展到了2676MB/S，可以满足高清晰度电视信号与实时的三维目标实体化过程的要求。因此，高性能的多媒体计算机中，多采用PCI总线结构。13、下列叙述正确的是（ ）。A、指令中操作数规定准备招待的功能B、断开电源后，DRAM中的内容便会丢失C、在16位计算机中，一个字节由16位组成D、软盘驱动器属于主机，软盘属于外设答：B分析：指令由操作码和操作数（或者操作数的地址码）构成，其中操作码规定该条指令将要招待的功能，操作数只是操作的对象。一个字节总是由8个二进制位组成，16位计算机通常指的是其数据总线为16位。软盘驱动器和软盘片都属于I/O设备。主存中的RAM分为动态RAM（DRAM）和静态RAM（SRAM），RAM只要一断电，其内容便会全部丢失，故选B。14、存储的内容在被读出后并不被破坏，这是（ ）的特性。A、随机存储器 B、内存 C、磁盘 D、存储器共同答：D分析：目前所使用的存储器一般都具有“非破坏性读出”的存取特性，即读出时并不破坏原来存储的内容，只有在写入新内容时才使原有的内容丢失。理解这个特性可以用录音磁带来做形象的类比：把录音带放入录音机内放送多遍，录音带上的内容依然如旧；只有当录入新内容时，原有的节目才被“洗掉”。对于用半导体电路构成的内存（包括随机存储器和只读存储器）、磁盘、磁带等外存，都有这样的特性。15、激光打印机属于（ ）。A、点阵式打印机 B、击打式打印机C、非击打式打印机 D、热敏式打印机答：C分析：打印机是另一种常用输出设备，从工作原理上可分为两大类：击打式与非击找式。击打式打印机（包括点阵式的、链式的等），通过“机头”向纸上打击而印出字符。其缺点是工作时噪声大，其优点是点阵式的比较便宜。非击打式的印字机（如激光式、喷墨式、热敏式等），工作时没有机件与纸面发生撞击，所以严格地说不应叫“打”印机，而应叫“印字机”。不过，人们习惯上还是称呼“激光打印”、“喷墨打印”等等。激光打印机印刷质量高、速度高、工作时噪声很小，但价革偏高。虽然它在工作时也有一道对纸张加热的工序，但那只是为 了固定印在纸上的墨粉，并不是通过加热才显出字符来，所以不属于“热敏式打印机”。能力训练：一、选择题1、PIII微机是（ ）的计算机A、8位 B、64位 C、16位 D、32位2、微型计算机的分类通常以微处理器的（ ）来划分。A、规格 B、芯片名 C、字长 D、寄存器的数目3、以80386微处理器为CPU的微机是（ ）位的微型计算机。A、8 B、16 C、32 D、644、ROM与RAM的主要区别是（ ）。A、断电后，ROM内保存的信息会丢失，而RAM则可长期保存，不会丢失B、断电后，RAM内保存的信息会丢失，而ROM则可长期保存，不会丢失C、ROM是外存储器，RAM是内存储器D、ROM是内存储器，RAM是外存储器5、计算机存储器主要由内存储器和（ ）组成。A、外存储器 B、硬盘 C、软盘 D、光盘6、在下列设备中，不能作为微机的输出设备的是（ ）。A、打印机 B、显示器 C、绘图仪 D、键盘7、存储器是用来存放（ ）信息的主要部件。A、十进制 B、二进制 C、八进制 D、十六进制8、SRAM存储器是（ ）。A、静态随机存储器 B、静态只读存储器C、动态随机存储器工 D、静态只读存储器9、16根地址总线的寻址范围是（ ）。A、512KB B、64KB C、640KB D、1MB10、下面的四个叙述中，有一个是错误的，它是（ ）。A、个人微机键盘上的Ctrl键是起控制作用的，它必须与其他键同时按下才有作用B、键盘属于输入设备，但显示器上显示的内容既有机器输出的结果，又有用户通过键盘打入的内容，所以显示器既是输入设备，又是输出设备C、计算机指令是指挥CPU进行操作的命令，指令通常由操作码和操作数组成D、个人微机在使用过程中突然断电，内存RAM中保存的信息全部丢失，ROM中保存的信息不受影响11、在微机中，VGA的含义是（ ）。A、微机的型号 B、键盘的型号 C、显示标准 D、显示器型号12、CD-ROM是一种大容量的外部存储设备，其特点是（ ）。A、只能读不能写 B、处理数据速度低于软盘C、只能写不能读 D、既能写也能读13、在CPU中，指令寄存器的作用是（ ）。A、用来保存后续指令地址B、保存当前正在执行的一条指令C、保存将被存储的下一个数据字节的地址D、保存CPU所访问的主存单元的地址14、数据一旦存入后，不能改变其内容，所存储的数据只能读取，但无法将新数据写入的存储器，叫做（ ）。A、磁芯 B、只读存储器 C、硬盘 D、随机存取存储器15、电子计算机的算术/逻辑单元、控制单元及存储单元统称为（ ）。A、UP B、ALU C、CPU D、CAD16、磁盘存储器的主要技术指标有4项，下面不属于这4项指标之一的是（ ）。A、存储容量 B、盘片数 C、磁道尺寸 D、寻址时间17、微机外存是指（ ）。A、RAM B、ROM C、磁盘 D、虚拟盘18、磁盘上的磁道是（ ）。A、记录密度不同的同心圆 B、记录密度相同的同心圆C、一条阿基米德螺线 D、两条阿基米德螺线19、在程序查询方式下控制外设，（ ）可进行数据传送。A、随时 B、外设准备就绪时C、外设没有准备就绪 D、外设正在进行其他工作时20、中断过程的顺序是（ ）。中断请求 中断响应 中断处理 中断识别 中断返回A、 B、 C、 D、21、关于DMA传递方式的特点，其中不正确的是（ ）。A、数据从外设读到CPU，再从CPU把数据送到内存B、DMA方式指高速外设（一般指磁盘存储器）与内存之间直接进行数据交换C、数据传输需要使用总线D、在DMA期间总线使用权是交给DMA控制器的22、（ ）是指从CPU芯片上引出的信号。A、系统总线 B、地址总线 C、局部总线 D、标准局部总线23、软盘上的扇区标志在（ ）是建立。A、低级格式化 B、格式化 C、存入数据 D、建立分区24、某种双面高密度软盘片格式化后，若每面有80个磁道，每个磁道有18个扇区，每个扇区存512个字节，则这种软盘片的容量是（ ）。A、720KB B、360KB C、1.2MB D、1.44MB25、下面是关于磁盘的四条叙述，其中正确的一条是（ ）。A、软盘格式化后，可以在任何微机上使用B、装在硬盘上的信息可以直接读入CPU进行处理C、可以用A驱动器或C驱动器启动DOS系统D、装在软盘上的信息必须经过硬盘才能被计算机处理26、微型计算机系统采用总线结构对CPU、存储器和外部设备进行连接。总线通常由三部分组成，它们是（ ）。A、逻辑总线、传输总线和通信总线B、地址总线、运算总线和逻辑总线C、数据总线、信号总线和传输总线D、数据总线、地址总线和控制总线27、微型计算机内存储器是（ ）。A、按二进制位编址 B、按字节编址C、按字长编址 D、根据微处理器型号不同而编址不同28、硬盘工作时应特别注意避免（ ）。A、噪声 B、震动 C、潮湿 D、日光29、光驱的倍速越在，（ ）。A、数据传输越快 B、纠错能力越强C、所能读取光盘的容量越大 D、播放VCD效果越好30、分辨率为12801024，256种颜色的17英寸显示器的显存容量至少应为（ ）。A、1MB B、2MB C、4MB D、8MB31、Cache和RAM一般是一种（ ）存储器。A、随机存取 B、顺序存取 C、先进先出存取 D、先进后出存取32、Cache存储器一般采用（ ）半导体芯片。A、ROM B、PROM C、DRAM D、SRAM33、主存现在主要由（ ）半导体芯片组成。A、ROM B、PROM C、DRAM D、SRAM34、计算机的主机包括（ ）。A、运算器和控制器 B、CPU和磁盘存储器C、硬件和软件 D、CPU和主存35、5.25英寸软盘上的DS，DD标记的意义是（ ）。A、单面单密度 B、单面双密度C、双面单密度 D、双面双密度36、5.25英寸软盘片外框上的一个矩形缺口，其作用是（ ）。A、机械定位 B、“0”磁道定位C、写保护作用 D、磁道的起点定位37、5.25英寸软盘片内圆边上有一个小圆孔，其作用是（ ）。A、机械定位 B、“0”磁道定位C、写保护作用 D、磁道的起点定位38、软盘驱动器在寻找数据时，（ ）。A、盘片不动，磁头动 B、盘片动，磁头不动C、盘片和磁头都动 D、盘片和磁头都不动39、3.5英寸软盘片上的一个矩形孔，其作用是（ ）。A、写保护作用 B、“0”磁道定位C、机械定位 D、磁道的起点定位40、在磁盘存储器中，无需移动磁头即可读取的一组磁道称为（ ）。A、单元 B、扇区 C、柱面 D、文卷41、CPU控制外设工作的方式有（ ）。程序查询输入/输出方式中断输入/输出方式DMA输入/输出方式A、 B、+ C、+ D、+42、标准接口的鼠标器一般连接在（ ）。A、并行接口上 B、串行接口上C、显示器接口上 D、打印机接口上43、微处理器Pentium4的主频高达1500MHz，制造它的美国公司是（ ）。A、IBM公司 B、Intel公司 C、Microsoft公司 D、AMD公司二、填空题1、光驱用倍速来表示数据的传输速度，其中4倍速是指每秒钟传输_KB的数据。2、显示器的分辨率用_来表示。3、在磁盘中，信息存放在若干个同心圆上，这些同心圆称为_。具有相同直径的所有磁道的组合称为_。4、微机中常把CD-ROM称为_光盘，它属于_存储器。5、CRT显示器也叫_显示器，是目前台式机显示器的主流。6、CGA、EGA、VGA这三种显示器中，显示性能最差的是_。7、在微机系统中的总线由_、_和_组成。8、某机器有32根地址线，直接寻址范围可达_MB。9、目前常用的微型计算机总线类型有_、_、_和_。10、显示卡的分辨率为800600的情况下，颜色数量是16种，则显示缓冲区为_。11、不论数据的多少，软盘上的信息是按_和_存放的。12、计算机可以直接执行的指令一般包括_和_两部分。13、显示器三大技术指标为_、点间距与恢度级。参考答：一、选择题1、D 2、C 3、C 4、B 5、A 6、D 7、B 8、A 9、B 10、B11、C 12、A 13、B 14、B 15、C 16、C 17、C 18、A 19、B 20、D21、A 22、C 23、B 24、D 25、C 26、D 27、B 28、B 20、A 30、B31、A 32、D 33、D 34、D 35、D 36、C 37、D 38、C 39、A 40、C41、D 42、B 43、B二、填空题1、600 2、屏幕上每行的象素数乘以每列的象素数3、磁道 柱面 4、只读 只读 5、阴极射线管6、CGA 7、地址总线 数据总线 控制总线 8、232B或4GB9、ISA总线 PCI总线 VESA总线 MCA总线10、256KB 11、扇区 磁道 12、操作码 地址码 13、分辨率能力训练：数据结构试题一、 单选题1、 在数据结构的讨论中把数据结构从逻辑上分为 （C ） A 内部结构与外部结构 B 静态结构与动态结构 C 线性结构与非线性结构 D 紧凑结构与非紧凑结构。2、采用线性链表表示一个向量时，要求占用的存储空间地址（D ） A 必须是连续的 B 部分地址必须是连续的 C 一定是不连续的 D 可连续可不连续3、采用顺序搜索方法查找长度为n的顺序表时，搜索成功的平均搜索长度为（ D ）。 A n B n/2 C (n-1)/2 D (n+1)/24、在一个单链表中，若q结点是p结点的前驱结点，若在q与p之间插入结点s，则执行（ D ）。A slink = plink; plink = s; B plink = s; slink = q;C plink = slink; slink = p; D qlink = s; slink = p;5、如果想在4092个数据中只需要选择其中最小的5个，采用（ C ）方法最好。 A 起泡排序 B 堆排序 C 锦标赛排序 D 快速排序 6、设有两个串t和p，求p在t中首次出现的位置的运算叫做（ B ）。 A 求子串 B 模式匹配 C 串替换 D 串连接7、在数组A中，每一个数组元素Aij占用3个存储字，行下标i从1到8，列下标j从1到10。所有数组元素相继存放于一个连续的存储空间中，则存放该数组至少需要的存储字数是（ C ）。A 80 B 100 C 240 D 2708、将一个递归算法改为对应的非递归算法时，通常需要使用（ A ）。A 栈 B 队列 C 循环队列 D 优先队列9、一个队列的进队列顺序是1, 2, 3, 4，则出队列顺序为（ C ）。10、在循环队列中用数组A0.m-1 存放队列元素，其队头和队尾指针分别为front和rear，则当前队列中的元素个数是（ D ）。 A ( front - rear + 1) % m B ( rear - front + 1) % mC ( front - rear + m) % m D ( rear - front + m) % m11、一个数组元素ai与（ A ）的表示等价。A *（a+i） B a+i C *a+i D &a+i 12、若需要利用形参直接访问实参，则应把形参变量说明为（ B ）参数。A 指针 B 引用 C 值 D 变量13、下面程序段的时间复杂度为（ C ） for (int i=0;im;i+) for (int j=0;jlink=p;p-link=s;B s-link=p-link;p-link=s;C s-link=p-link;p=s;D p-link=s;s-link=p;19、设单链表中结点结构为(data,link).已知指针q所指结点是指针p所指结点的直接前驱，若在*q与*p之间插入结点*s，则应执行下列哪一个操作（ B ）A s-link=p-link; p-link=s; B q-link=s; s-link=pC p-link=s-link;s-link=p; D p-link=s; s-link=q;20、设单链表中结点结构为(data,link).若想摘除结点*p的直接后继，则应执行下列哪一个操作（ A ）A p-link=p-link-link; B p=p-link; p-link=p-link-link;C p-link=p-link; D p=p-link-link;21、设单循环链表中结点的结构为（data,link）,且rear是指向非空的带表头结点的单循环链表的尾结点的指针。若想删除链表第一个结点，则应执行下列哪一个操作（ D ）A s=rear; rear=rear-link; delete s; B rear=rear-link; delete rear; C rear=rear-link-link; delete rear; D s=rear-link-link; rear-link-link=s-link; delete s;s为第一个结点硫22、设单循环链表中结点的结构为（data,link）,且first为指向链表表头的指针，current为链表当前指针，在循环链表中检测current是否达到链表表尾的语句是( D )。A current-link =null B first-link=currentC first=current D current-link=first？23、一个栈的入栈序列为a，b，c，则出栈序列不可能的是( C )。A c,b,a B b,a,c C c,a,b D a,c,b24、栈的数组表示中，top为栈顶指针，栈空的条件是( A )。A top=0 B top=maxSize C top=maxSize D top=-125、栈和队列的共同特点是( C )。A 都是先进后出 B 都是先进先出C 只允许在端点处插入和删除 D 没有共同点26、假定一个顺序存储的循环队列的队头和队尾指针分别为f和r ,则判断队空的条件为( D ).A f+1= =r B r+1= =f C f= =0 D f= =r27、当利用大小为n 的数组顺序存储一个队列时，该队列的最大长度为（ B ）A n-2 B n-1 C n D n+128、当利用大小为n 的数组顺序存储一个栈时，假定用top= =n 表示栈空，则向这个栈插入一个元素时，首先应执行（ ）语句修改top指针。A top+; B top-; C top=0; D top;29、设链式栈中结点的结构为（data, link）,且top是指向栈顶的指针。若想摘除链式栈的栈顶结点，并将被摘除结点的值保存到x中，则应执行下列（ A ）操作。A x=top-data; top=top-link; B top=top-link; x=top-data; C x=top; top=top-link; D x=top-data;30、设循环队列的结构是： const int Maxsize=100; typedef int Data Type; typedef struct Data Type dataMaxsize; Int front, rear; Queue;若有一个Queue类型的队列Q，试问判断队列满的条件应是下列哪一个语句（ D ）A Q.front= = Q.rear; B Q.front - Q.rear= = Maxsize; C Q.front + Q.rear= = Maxsize; D Q.front= = (Q.rear+1)% Maxsize;31、设有一个递归算法如下：int fact (int n ) if (n=0) return 1;else return n*fact(n-1);下面正确的叙述是（ B ）A 计算fact(n) 需要执行n次递归 B fact(7)=5040 C 此递归算法最多只能计算到fact(8) D 以上结论都不对32、设有一个递归算法如下int x (int n) if (n递归表纯表线性表 B 递归表线性表再入表纯表 C 递归表再入表纯表线性表 D递归表再入表线性表纯表37、某二叉树的前序和后序序列正好相反，则该二叉树一定是（B）的二叉树。A 空或只有一个结点 B 高度等于其结点数 C 任一结点无左孩子 D 任一结点无右孩子38、对于任何一棵二叉树T，如果其终端结点数为n0，度为2的结点为n2.,则( A )A n0= n2+1 B n2= n0+1 C n0= 2n2+1 D n2=2n0+1 39、 由权值分别为11，8，6，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（B ）A 24 B 73 C 48 D 5340、已知一个顺序存储的线性表，设每个结点需占m个存储单元，若第一个结点的地址为da1,则第I 个结点的地址为（A）。A da1+(I-1)*m B da1+I*m C da1-I*m D da1+(I+1)*m41、34 具有35个结点的完全二叉树的深度为( A )A 5 B 6 C 7 D 842、对线性表进行折半搜索时，要求线性表必须（ C ）A 以链接方式存储且结点按关键码有序排列 B 以数组方式存储 C 以数组方式存储且结点按关键码有序排列 D以链接方式存储43、顺序搜索算法适合于存储结构为（ B ）的线性表。A 散列存储 B 顺序存储或链接存储 C 压缩存储 D 索引存储44、采用折半搜索算法搜索长度为n的有序表时，元素的平均搜索长度为（ C ）A O（n2） B O（n log2n） C O（log2n） D O（n）45、对于一个具有n个顶点和e条边的无向图，进行拓扑排序时，总的时间为( A )A n B n+1 C n-1 D n+e46、判断一个有向图是否存在回路，除了可以利用拓扑排序方法外，还可以利用（C ）。A 求关键路径的方法 B 求最短路径的Dijkstra方法 C 深度优先遍历算法 D 广度优先遍历算法47、在10阶B-树中根结点所包含的关键码个数最多为（C ），最少为( A )A 1 B 2 C 9 D 1048、对包含n 个元素的散列表进行搜索，平均搜索长度为（ C ）A O（log2n） B O（n）C 不直接依赖于n D 上述都不对二、 填空题（）1、数据的逻辑结构被分为集合结构、线性结构、树形结构、图形结构 四种2、数据的存储结构被分为顺序结构、链接结构、索引结构、散列结构 四种3、一种抽象数据类型包括（数据 ）和（操作 ）两个部分。4、 设有两个串p和q，求p在q中首次出现的位置的运算称为（模式匹配） 5、 栈、队列逻辑上都是（线性存储）结构。6、 线性结构反映结点间的逻辑关系是（一对一）的，图中的数据元素之间的关系是（多对多）的，树形结构中数据元素间的关系是（一对多）的。7、栈中存取数据的原则（后进先出），队列中存取数据的原则（先进先出）8、串是由（零个或多个）字符组成的序列。（长度为零的串）称为空串，（由一个或多个空格组成的串）称为空格串。9、设目标串T=”abccdcdccbaa”,模式P=”cdcc”则第（6）次匹配成功。10、一维数组的逻辑结构是（线性结构），存储结构是（顺序存储表示）。对于二维数组，有（行优先顺序）和（列优先顺序）两种不同的存储方式，对于一个二维数组Amn,若采用按行优先存放的方式，则任一数组元素Aij相对于A00的地址为（ n*i+j）。11、向一个顺序栈插入一个元素时，首先使（ 栈顶指针 ）后移一个位置，然后把待插入元素（ 写 ）到这个位置上。从一个顺序栈删除元素时，需要前移一位（栈顶指针）。12、在一个循环队列Q中，判断队空的条件为（Q.front= =Q.rear）, 判断队满的条件为（ (Q.rear+1)%MaxSize= =q.front ）13、对于一棵具有n个结点的树，该树中所有结点的度数之和为（ n-1 ）。14、一棵高度为5的满二叉树中的结点数为（ 63 ）个，一棵高度为3满四叉树中的结点数为（ 85 ）个。15、若对一棵二叉树从0开始进行结点编号，并按此编号把它顺序存储到一维数组中，即编号为0的结点存储到a0中，其余类推，则ai元素的左子女结点为（ 2*i+1），右子女结点为（ 2*i+2 ），双亲结点（i=1）为（(i-1)/2 ）.16、在一个最大堆中，堆顶结点的值是所有结点中的（最大值），在一个最小堆中，堆顶结点的值是所有结点中的（最小值）。17、已知具有n个元素的一维数组采用顺序存储结构，每个元素占k个存储单元，第一个元素的地址为LOC(a1)，那么，LOC(ai)= LOC(a1)+(i-1)*k 。18、在霍夫曼编码中，若编码长度只允许小于等于4,则除掉已对两个字符编码为0和10外，还可以最多对（ 4 ）个字符编码。19、设高度为h的空二叉树的高度为-1，只有一个结点的二叉树的高度为0，若设二叉树只有度为2上度为0的结点，则该二叉树中所含结点至少有（2h+1）个。20、由一棵二叉树的前序序列和（中序序列）可唯一确定这棵二叉树。 21、以折半搜索方法搜索一个线性表时，此线性表必须是（顺序）存储的（有序）表。22、已知完全二叉树的第8层有8个结点，则其叶子结点数是（68）。若完全二叉树的第7有10个叶子结点，则整个二叉树的结点数最多是（235）23、对于折半搜索所对应的判定树，它既是一棵（二叉搜索树），又是一棵（理想平衡树）。24、假定对长度n=50的有序表进行折半搜索，则对应的判定树高度为（），判定树中前层的结点数为（），最后一层的结点数为（）。25、在一个无向图中，所有顶点的度数之和等于所有边数的（）倍。在一个具有n个顶点的无向完全图中，包含有（ n(n-1)/2 ）条边，在一个具有n个顶点的有向完全图中，包含有（ n(n-1) ）条边。26、对于一个具有n个顶点和e条边的连通图，其生成树中的顶点数和边数分别为（n）和（n-1）。27、设线性表中元素的类型是实型，其首地址为1024，则线性表中第6个元素的存储位置是( 1044)。28、在插入和选择排序中，若初始数据基本正序，则选择（插入排序），若初始数据基本反序，则最好选择（选择排序）。29、算法是对特定问题的求解步驟的一种描述，它是（指令）的有限序列，每一条（指令）表示一个或多个操作。30、对于一个具有n个顶点肯e 条边的无向图，进行拓朴排序时，总的进间为（n）31、构造哈希函数有三种方法，分别为(平方取中)法、(除留余数)法、(折迭移位)法。32、处理冲突的三种方法，分别为(线性探测)、（ 随机探测 ）、（ 链地址法）。33、对于含有n个顶点和e条边的无向连通图，利用普里姆算法产生的最小生成树，其时间复杂度为（ （n2） ）、利用克鲁斯卡尔算法产生的最小生成树，其时间复杂度为（elog2e） ）34、快速排序在平均情况下的时间复杂度为（nlog2n），在最坏情况下的时间复杂度为（n2）；快速排序在平均情况下的空间复杂度为（log2n），在最坏情况下的空间复杂度为（n）。35、假定一组记录的排序码为（，），对其进行归并排序的过程中，第二趟排序后的结果是（）36、假定一组记录的排序码为（，），对其进行快速排序的第一次划分的结果是（）。37、一个结点的子树的（ 个数 ）称为该结点的度。度为（ 零 ）的结点称为叶结点或终端结点。度不为（ 零 ）的结点称为分支结点或非终端结点。树中各结点度的（ 最大值 ）称为树的度。38、设Ki=Kj (1=i=n, 1=j=n,ji)且在排序前的序列中Ri领先于Rj (ij),若排序后的序列中Ri仍领先于Rj，则这种排序方法是（稳定的），反之是（不稳定的）。40 、在堆排序的过程中，对任一分支结点进行调整运算的时间复杂度为（log2n），整个排序过程的时间复杂度为（nlog2n）。41、在索引表中，每个索引项至少包含有（关键码值）域和（子表地址）域这两项。42、假定一个线性表为（”abcd”,”baabd”,”bcef”,”cfg”,”ahij”,”bkwte”,”ccdt”,”aayb”）,若按照字符串的第一个字母进行划分，使得同一个字母被划分在一个子表中，则得到的a,b,c三个子表的长度分别为（），（），（）。43、对于包含个关键码的阶B-树，其最小高度为（），最大高度为（）。44