下载文档原格式
2022年中国农业大学计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、n个结点的完全有向图含有边的数目（）。
A.n*nB.n(n+1)C.n/2D.n*(n-1)2、哈希文件使用哈希函数将记录的关键字值计算转化为记录的存放地址，因为哈希函数是一对一的关系，则选择好的（）方法是哈希文件的关键。
A.哈希函数B.除余法中的质数C.冲突处理D.哈希函数和冲突处理3、静态链表中指针表示的是（）。
A.下一元素的地址B.内存储器的地址C.下一元素在数组中的位置D.左链或右链指向的元素的地址4、已知串S='aaab'，其next数组值为（）。
A.0123B.1123C.1231D.12115、在下列表述中，正确的是（）A.含有一个或多个空格字符的串称为空格串B.对n（n>0）个顶点的网，求出权最小的n-1条边便可构成其最小生成树C.选择排序算法是不稳定的D.平衡二叉树的左右子树的结点数之差的绝对值不超过l6、下列选项中，不能构成折半查找中关键字比较序列的是（）。
A．500，200，450，180 B．500，450，200，180C．180，500，200，450 D．180，200，500，4507、若一棵二叉树的前序遍历序列为a，e，b，d，c，后序遍历序列为b， c，d，e，a，则根结点的孩子结点（）。
A．只有e B．有e、b C．有e、c D．无法确定8、有n（n>0）个分支结点的满二叉树的深度是（）。
A.n2-1B.log2（n+1）+1C.log2（n+1）D.log2（n-l）9、在下述结论中，正确的有（）。
①只有一个结点的二叉树的度为0。
②二叉树的度为2。
③二叉树的左右子树可任意交换。
④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。
A.①②③B.⑦③④C.②④D.①④10、一组记录的关键码为（46，79，56，38，40，84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（）。
2022年黄山学院计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、下列排序算法中，占用辅助空间最多的是（）。
A.归并排序B.快速排序C.希尔排序D.堆排序2、无向图G=(V，E)，其中：V={a，b，c，d，e，f}，E={(a，b)，(a， e)，(a，c)，(b，e)，(c，f)，(f，d)，(e，d)}，对该图进行深度优先遍历，得到的顶点序列正确的是（）。
A.a，b，e，c，d，fB.a，c，f,e，b，dC.a，e，b，c，f, dD.a，e，d，f，c，b3、线性表的顺序存储结构是一种（）。
A.随机存取的存储结构B.顺序存取的存储结构C.索引存取的存储结构D.Hash存取的存储结构4、有六个元素6，5，4，3，2，1顺序入栈，下列不是合法的出栈序列的是（）。
A.543612B.453126C.346521D.2341565、已知有向图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，V7B.V1，V3，V2，V6，V4，V5，V7C.V1，V3，V5，V2，V6，V7D.V1，V2，V5，V3，V4，V6，V76、若一棵二叉树的前序遍历序列为a，e，b，d，c，后序遍历序列为b， c，d，e，a，则根结点的孩子结点（）。
A．只有e B．有e、b C．有e、c D．无法确定7、已知关键字序列5，8，12，19，28，20，15，22是小根堆（最小堆），插入关键字3，调整后的小根堆是（）。
A．3，5，12，8，28，20，15，22，19B．3，5，12，19，20，15，22，8，28C．3，8，12，5，20，15，22，28，19D．3，12，5，8，28，20，15，22，198、有n（n>0）个分支结点的满二叉树的深度是（）。
2022年哈尔滨工程大学计算机科学与技术专业《操作系统》科目期末试卷A（有答案）一、选择题1、驱动调度算法中，（）算法可能会随时改变移动臂的运动方向。
A.电梯调度B.最短寻道时间优先C.扫描D.单向扫描2、无结构文件的含义是（）A.变长记录的文件B.索引文件C.流式文件D.索引顺序文件3、系统中有3个不同的临界资源R1，R2和R3，被4个进程pl，p2，p3 及p4共享。
各进程对资源的需求为：pl申请RI和R2，p2申请R2和R3，p3申请R1和R3，p4申请R2。
若系统出现死锁，则处于死锁状态的进程数至少是（）。
A.1B.2C.3D.44、一个进程的读磁盘操作完成后，操作系统针对该进程必做的是（），A.修改进程状态为就绪态B.降低进程优先级C.给进程分配用户内存空间D.增加进程时间片大小5、某计算机系统中有8台打印机，有K个进程竞争使用，每个进，程最多需要3台打印机，该系统可能会发生死锁的K的最小值是（）A.2B.3C.4D.56、在页式虚拟存储管理系统中，采用某些页面置换算法，会出现Belady异常现象，即进程的缺页次数会随着分配给该进程的页框个数的增加而增加。
下列算，法中，可能出现Belady异常现象的是（）。
I.LRU算法 II.FIFO算法 III.OPT 算法A. 仅IB.仅IIC.仅I、IIID. 仅I、III7、考虑一个分页式存储管理系统，其页表常驻内存。
I.如果内存访问耗时200ns，那么访问内存中的数据需要多长时间？II.如果引入关联寄存器（Associative Registers），而月.75%的页面可以从关联寄存器中找到，那么此时的有效访问时间（Effective Memory Reference Time）应为（）。
假设访问关联寄存器的时间可以忽略。
注：有效访问时间即为平均访问时间。
A.200ns，150nsB.400ns，150nsC.400ns，250nsD.600ns.250ns8、假设4个作业到达系统的时刻和运行时间见表。
2022年哈尔滨工业大学数据科学与大数据技术专业《操作系统》科目期末试卷A（有答案）一、选择题1、与早期的操作系统相比，采用微内核结构的操作系统具有很多优点，但是这些优点不，包括（）。
A.提高了系统的可扩展性B.提高了操作系统的运行效率C.增强了系统的可靠性D.使操作系统的可移植性更好2、下列指令中，不能在用户态执行的是（）A.trap指令B.跳转指令C.压栈指令D.关中断指令3、一次性分配所有资源的方法可以预防死锁的发生，这种方法破坏的是产生死锁的4个必要条件中的（）。
A.互斥条件B.占有并请求C.不剥夺条件D.循环等待4、有若干并发进程均将一个共享变量count的值加1一次，那么有关count中的值的说法正确的是（）。
I.肯定有不正确的结果II.肯定有正确的结果，III.若控制这些并发进程互斥执行count加1操作，count中的值正确A. I和IIIB.II和IIIC.IIID. I、II和III的说法均不正确5、一个进程被唤醒意味着（）。
A.该进程可以重新占用CPUB.优先级变为最大C.PCB移到就绪队列之首D.进程变为运行态6、采用SPOOLing技术后，使得系统资源利用率（）。
A.提高了B.有时提高，有时降低C.降低了D.提高了，但出错的可能性增人了7、采用SPOOLing技术将磁盘的一部分作为公共缓冲区以代替打印机，用户对打印机的操作实际上是对磁盘的存储操作，用以代替打印机的部分是（）。
A.独占设备B.共享设备C.虚拟设备D.一般物理设备8、下列选项中，磁盘逻辑格式化程序所做的T作是（）I.对磁盘进行分区II.建立文件系统的根目录III.确定磁盘扇区校验码所占位数IV.对保存空闲磁盘块信息的数据结构进行初始化，A. 仅IIB.仅II、IVC.仅III，IVD.仅I、II、IV9、一个磁盘的转速为7200r/min，每个磁道有160个扇区，每个扇区为512B.那么理想情况下，其数据传输率为（）。
2022年青海大学计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、哈希文件使用哈希函数将记录的关键字值计算转化为记录的存放地址，因为哈希函数是一对一的关系，则选择好的（）方法是哈希文件的关键。
A.哈希函数B.除余法中的质数C.冲突处理D.哈希函数和冲突处理2、下列排序算法中，占用辅助空间最多的是（）。
A.归并排序B.快速排序C.希尔排序D.堆排序3、计算机算法指的是解决问题的步骤序列，它必须具备（）三个特性。
A.可执行性、可移植性、可扩充性B.可执行性、确定性、有穷性C.确定性、有穷性、稳定性D.易读性、稳定性、安全性4、最大容量为n的循环队列，队尾指针是rear，队头：front，则队空的条件是（）。
A.（rear+1）MOD n=frontB.rear=frontC.rear+1=frontD.（rear-1）MOD n=front5、下列关于AOE网的叙述中，不正确的是（）。
A.关键活动不按期完成就会影响整个工程的完成时间B.任何一个关键活动提前完成，那么整个工程将会提前完成C.所有的关键活动提前完成，那么整个工程将会提前完成D.某些关键活动若提前完成，那么整个工程将会提前完成6、若一棵二叉树的前序遍历序列为a，e，b，d，c，后序遍历序列为b， c，d，e，a，则根结点的孩子结点（）。
A．只有e B．有e、b C．有e、c D．无法确定7、下列叙述中，不符合m阶B树定义要求的是（）。
A．根结点最多有m棵子树 B．所有叶结点都在同一层上C．各结点内关键字均升序或降序排列 D．叶结点之间通过指针链接8、一棵哈夫曼树共有215个结点，对其进行哈夫曼编码，共能得到（）个不同的码字。
A.107B.108C.214D.2159、有n（n>0）个分支结点的满二叉树的深度是（）。
A.n2-1B.log2（n+1）+1C.log2（n+1）D.log2（n-l）10、若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL为（）。
2022年河南工程学院计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、哈希文件使用哈希函数将记录的关键字值计算转化为记录的存放地址，因为哈希函数是一对一的关系，则选择好的（）方法是哈希文件的关键。
A.哈希函数B.除余法中的质数C.冲突处理D.哈希函数和冲突处理2、若需在O（nlog2n）的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（）。
A.快速排序B.堆排序C.归并排序D.直接插入排序3、某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（）存储方式最节省运算时间。
A.单链表B.仅有头指针的单循环链表C.双链表D.仅有尾指针的单循环链表4、已知有向图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，V7B.V1，V3，V2，V6，V4，V5，V7C.V1，V3，V5，V2，V6，V7D.V1，V2，V5，V3，V4，V6，V75、在用邻接表表示图时，拓扑排序算法时间复杂度为（）。
A.O(n)B.O(n+e)C.O(n*n)D.O(n*n*n)6、排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一趟排序。
下列排序方法中，每一趟排序结束时都至少能够确定一个元素最终位置的方法是（）。
Ⅰ．简单选择排序Ⅱ．希尔排序Ⅲ．快速排序Ⅳ．堆排Ⅴ．二路归并排序A．仅Ⅰ、Ⅲ、Ⅳ B．仅Ⅰ、Ⅱ、Ⅲ C．仅Ⅱ、Ⅲ、Ⅳ D．仅Ⅲ、Ⅳ、Ⅴ7、下列关于无向连通图特性的叙述中，正确的是（）。
Ⅰ．所有的顶点的度之和为偶数Ⅱ．边数大于顶点个数减1 Ⅲ．至少有一个顶点的度为1A．只有Ⅰ B．只有Ⅱ C．Ⅰ和Ⅱ D．Ⅰ和Ⅲ8、一棵哈夫曼树共有215个结点，对其进行哈夫曼编码，共能得到（）个不同的码字。
2022年湘南学院计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、n个结点的完全有向图含有边的数目（）。
A.n*nB.n(n+1)C.n/2D.n*(n-1)2、将线性表的数据元素进行扩充，允许带结构的线性表是（）。
A.串B.树C.广义表D.栈3、线性表的顺序存储结构是一种（）。
A.随机存取的存储结构B.顺序存取的存储结构C.索引存取的存储结构D.Hash存取的存储结构4、有六个元素6，5，4，3，2，1顺序入栈，下列不是合法的出栈序列的是（）。
A.543612B.453126C.346521D.2341565、用不带头结点的单链表存储队列，其队头指针指向队头结点，队尾指针指向队尾结点，则在进行出队操作时（）。
A.仅修改队头指针B.仅修改队尾指针C.队头、队尾指针都可能要修改D.队头、队尾指针都要修改6、若元素a，b，c，d，e，f依次进栈，允许进栈、退栈操作交替进行，但不允许连续三次进行退栈操作，则不可能得到的出栈序列是（）。
7、循环队列放在一维数组A中，end1指向队头元素，end2指向队尾元素的后一个位置。
假设队列两端均可进行入队和出队操作，队列中最多能容纳M－1个元素。
初始时为空，下列判断队空和队满的条件中，正确的是（）。
A．队空：end1＝＝end2；队满：end1＝＝（end2＋1）mod MB．队空：end1＝＝end2；队满：end2＝＝（end1＋1）mod （M－1）C．队空：end2＝＝（end1＋1）mod M；队满：end1＝＝（end2＋1） mod MD．队空：end1＝＝（end2＋1）mod M；队满：end2＝＝（end1＋1） mod （M－1）8、有n（n>0）个分支结点的满二叉树的深度是（）。
A.n2-1B.log2（n+1）+1C.log2（n+1）D.log2（n-l）9、一棵非空的二叉树的前序序列和后序序列正好相反，则该二叉树一定满足（）。
2022年哈尔滨工程大学公共课《大学计算机基础》期末试卷A(有答案）一、单项选择题1、十进制数83，用二进制表示是（）A.00010011B.01010011C.00111110D.011011102、用8位二进制数，能表示的最大十进制数是（）A.256B.255C.128D.1273、下列数据中，最小数是（）A.(10111100)2B. (162)sC. (264)10D. (CD)164、微机中.一位二进制代码可表示的状态有（）A.1种B.2种C.3种D.4种5、以下4项中，不属于计算机病毒特征的是（）A.潜伏性B.传染性C.激发性D.免疫性6、用拼音输入法输入“北京奥运”四个汉字，它们的内码占用的存储空间为（）A.2个字节B.4个字节C.6个字节D.8个字节7、第四代计算机的逻辑器件，采用的是（）A. 晶体管B. 大规模、超大规模集成电路C. 中、小规模集成电路D. 微处理器集成电路8、在Windows 7任务栏中，不包括（）A.撤销按钮B.语言栏C.快速启动区D.程序按钮9、下列不属于Microsoft Office 2000软件包的软件是（）A. WordB. ExcelC. OutlookD. Adobe10、可以方便地进行Windows 7组件安装工作的是“控制面板”中的（）A.管理工具B.添加/删除程序C.添加/删除硬件D.辅助功能选项11、Windows 7是一中微型机上使用的（）A.工具软件B.应用软件C.系统软件.D.图形软件12、Windows 7系统提供了4种桌面图标的排列方式，分别是按：名称、大小，以及（）A.访问频率和最近访问日期排列B.项目类型和访问频率排列C.项目类型和修改日期排列D.项目类型和创建日期排列13、下列有关Windows7“回收站”的叙述中，筚译的是（）A.被删除到“回收站”中的文件可以编辑B.“回收站”中的所有文件都可以还原C.“回收站”中的文件可以有选择的删除D.“回杈站”中的全部文件可以一次性清空14、在Word2010中，对已选中的浮于文字上方的图片位置向上微调应使用（）A "Alt+向上键"B"Ctrl+向上键"C"Esc+向上键"D"Shif+向上键"15、在Word 2010文档中插入分节符，便于实现（）A.修改文档B.创建文档目录C.阅读文档D.创建不同的页眉16、在Word的编辑状态,对当前文档中的文字进行”字数统计”操作,应当使用（）A.“文件”菜单B.编辑菜单C.“视图”菜单D.“工具”菜单17、在Word中，用户同时打开了4个文档窗口，当前活动窗口有（）A.1个B.2个C.3个D.4个18、在Word中，对艺术字设置阴影效果的工具栏是（）A.图片B.艺术字C.绘图D.格式19、在Word中对选中的一段文字设置边框和底纹.应选择的菜单是（）A.“视图"菜单B.“工具"菜单C.“格式”菜单D.“编辑"菜单20、打印Excel 2010的工作表时.在文件菜单的“页面设置”命令中.不可能设置（）A.打印方向B.纸张大小C.页边距D.打印份数21、在Excel 2010的数据库中，自动筛选是对各（）A. 记录进行条件选择的筛选B. 字段进行条件选择的筛选C. 行号进行条件选择的筛选D. 列号进行条件选择的筛选22、在Exce12010中可以为单元格命名，下列单元格名称正确的是（）A.A3B.ЗAC.成绩，优D.成绩优23、在Excel2010中，提供了多种图表类型，其中“饼图”用于显示（）A各项数据系列的比较情况B数据系列的数据变化趋势C在两组数据间查找最优组合D构成数据系列的项目相对于项目总和的比例大小24、Excel 2010一个单元格中存储的信息不包括（）A.批注B.格式C.内容D.图片25、在Excel 2010工作表中，如图所示的数据，在A4单元格中输人公式“=SUM(A1：A3）/AVERAGE(A1，A2，A3)”，则（）A4 B.3 C.2 D.126、在PowerPoint 2010中提供了4种动画设置类型，正确的是（）A.进入、强调、退出和动作路径B.退出、进入、强调和减弱C.动作路径、进入、强调和自定义D.自定义、进入、退出和动作路径27、在PowerPoint 2010中，对幻灯片进行幻灯片切换效果的设置应选择（）A.“视图”菜单B.“插入”菜单C.“幻灯片放映”菜单D.“工具”菜单28、下列属于局域网的是（）A.国家网B.校园网C.城市网D.因特网29、电子邮件地址的用户名和邮件服务器名之间用（）A./ 符号隔开B.\ 符号隔开C.：// 符号隔开D.30、能够实现在计算机和网络介质之间进行信息编码转换的设备是（）A.网卡B.集线器C.交换机D.路由器二、填空题31、在Windows 7默认情况下，按组合键_____________可以实现各种输入法的切换。
2022年哈尔滨工程大学计算机科学与技术专业《计算机系统结构》科目期末试卷A（有答案）一、选择题1、下列说法正确的是( )A.Cache容量一般不大，命中率不会很高B.Cache芯片速度一般比CPU的速度慢数十倍C.Cache本身速度很快。
但地址变换的速度很慢D.Cache存贮器查映象表和访问物理Cache其间可以流水，使速度与CPU匹配2、对汇编语言程序员透明的是（）A.I/O方式中的DMA访问B.浮点数据表示C.访问方式保护D.程序性中断3、下列关于虚拟存贮器的说法，比较正确的应当是( )A.访主存命中率随页面大小增大而提高B.访主存命中率随主存容量增加而提高C.更换替换算法能提高命中率D.在主存命中率低时，改用堆栈型替换算法，并增大主存容量，可提高命中率4、计算机系统多级层次中，从下层到上层，各级相对顺序正确的应当是（）。
A.汇编语言机器级，操作系统机器级，高级语言机器级B.微程序机器级，传统机器语言机器级，汇编语言机器级C.传统机器语言机器级，高级语言机器级，汇编语言机器级D.汇编语言机器级，应用语言机器级，高级语言机器级5、计算机系统结构不包括( )。
A.主存速度B.机器工作状态C.信息保护D.数据6、下列说法中不正确的是（）A.软件设计费用比软件重复生产费用高B.硬件功能只需实现一次，而软件功能可能要多次重复实现C.硬件的生产费用比软件的生产费用高D.硬件的设计费用比软件的设计费用低7、CRAY-I的流水线是( )A.多条单功能流水线B.一条单功能流水线C.多条多功能流水线D.一条多功能流水线8、传统机器语言机器级，是用（）来（）机器指令。
A.硬件，翻译B.编译程序，翻译C.微指令程序，解释D.微指令程序，翻译9、不同系列的机器之间，实现软件移植的途径不包括( )A.用统一的高级语言B.用统一的汇编语言C.模拟D.仿真10、IBM360/91属于（）A.向量流水机B.标量流水机C.阵列流水机D.并行流水机11、从计算机系统结构上讲，机器语言程序员所看到的机器属性是（）A.计算机软件所要完成的功能B.计算机硬件的全部组成C.编程要用到的硬件组织D.计算机各部件的硬件实现。
第2页 共 2页8、一棵二叉树高度为h ，所有结点的度或为0或为2，则这棵二叉树最少有( )个结点。
A ．2hB ．2h-1C ．2h+1D ．h+19、对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用( )次序的遍历实现编号。
A ．先序B ．中序C ．后序D ．按层次遍历10、一棵二叉树的先序遍历序列为ABCDEFG ，它的中序遍历序列可能是（ ）。
A ．CABDEFGB ．ABCDEFGC ．DACEFBGD ．ADBCFEG11、一棵有n 个结点的二叉树，按层次从上到下，同一层从左到右顺序存储在一维数组A[1..n]中，则二叉树中第i 个结点（i 从1开始用上述方法编号）的右孩子在数组A 中的位置是（ ）A ．A[2i](2i<=n)B ．A[2i+1](2i+1<=n)C ．A[i-2]D ．条件不充分，无法确定12、一个n 个顶点的连通无向图，其边的个数至少为（ ）。
A ．n-1B ．nC ．n+1D ．nlogn13、下列关于AOE 网的叙述中，不正确的是（ ）。
A ．关键活动不按期完成就会影响整个工程的完成时间B ．任何一个关键活动提前完成，那么整个工程将会提前完成C ．所有的关键活动提前完成，那么整个工程将会提前完成D ．某些关键活动提前完成，那么整个工程将会提前完成 14、下面关于折半查找的叙述正确的是( )。
A ．表必须有序，表可以顺序方式存储，也可以链表方式存储C ．表必须有序，而且只能从小到大排列B ．表必须有序且表中数据必须是整型，实型或字符型D ．表必须有序，且表只能以顺序方式存储A．直接插入排序B．起泡排序C．快速排序D．直接选择排序二、判断题（每空1分，共10分）1、数据的逻辑结构说明数据元素之间的顺序关系，它依赖于计算机的储存结构。
( )2、对任何数据结构，链式存储结构一定优于顺序存储结构。
2022年哈尔滨工程大学计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、已知广义表LS=（（a，b，c），（d，e，f）），用head和tail数取出LS中原子e的运算是（）。
A.head（tail（LS））B.tail（head（LS））C.head（tail（head（tail（LS））））D.head（tail（tail（head（LS））））2、有一个100*90的稀疏矩阵，非0元素有10个，设每个整型数占2字节，则用三元组表示该矩阵时，所需的字节数是（）。
A.60B.66C.18000D.333、若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（）存储方式最节省时间。
A.顺序表B.双链表C.带头结点的双循环链表D.单循环链表4、下面关于串的叙述中，不正确的是（）。
A.串是字符的有限序列B.空串是由空格构成的串C.模式匹配是串的一种重要运算D.串既可以采用顺序存储，也可以采用链式存储5、在用邻接表表示图时，拓扑排序算法时间复杂度为（）。
A.O(n)B.O(n+e)C.O(n*n)D.O(n*n*n)6、循环队列放在一维数组A中，end1指向队头元素，end2指向队尾元素的后一个位置。
假设队列两端均可进行入队和出队操作，队列中最多能容纳M－1个元素。
初始时为空，下列判断队空和队满的条件中，正确的是（）。
A．队空：end1＝＝end2；队满：end1＝＝（end2＋1）mod MB．队空：end1＝＝end2；队满：end2＝＝（end1＋1）mod （M－1）C．队空：end2＝＝（end1＋1）mod M；队满：end1＝＝（end2＋1） mod MD．队空：end1＝＝（end2＋1）mod M；队满：end2＝＝（end1＋1） mod （M－1）7、已知字符串S为“abaabaabacacaabaabcc”，模式串t为“abaabc”，采用KMP算法进行匹配，第一次出现“失配”（s!＝t）时，i＝j＝5，则下次开始匹配时，i和j的值分别（）。
A．i＝1，j＝0 B．i＝5，j＝0 C．i＝5，j＝2 D．i＝6，j＝28、一个具有1025个结点的二叉树的高h为（）。
A.11B.10C.11至1025之间D.10至1024之间9、已知一棵二叉树的前序遍历结果为ABCDEF，中序遍历结果为CBAEDF，则后序遍历结果为（）。
A.CBEFDAB.FEDCBAC.CBEDFAD.不定10、若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL为（）。
A.(n-1)/2B.n/2C.(n+1)/2D.n二、填空题11、设m、n均为自然数，m可表示为一些不超过n的自然数之和，f（m，n）为这种表示方式的数目。
例f（5，3）=5，有5种表示方式：3+2，3+1+1，2+2+1，2+1+1+1，1+1+1+1+1。
①以下是该函数的程序段，请将未完成的部分填入，使之完整。
②执行程序，f（6，4）=______。
12、顺序查找n个元素的顺序表，若查找成功，则比较关键字的次数最多为______次；当使用监视哨时，若查找失败，则比较关键字的次数为______。
13、n个顶点的有向图用邻接矩阵array表示，下面是其拓扑排序算法，试补充完整。
注：(1)图的顶点号从0开始计。
(2)indegree是有n个分量的一维数组，放顶点的入度，(3)函数crein用于计算顶点入度。
(4)有三个函数push(data)，pop()，check()其含义为数据data入栈，出栈和测试栈是否空(不空返回l，否则0)。
14、在基于关键字比较且时间为O（nlog2n）的排序中，若要求排序是稳定的，则可选用______排序；若要求就地排序（及辅助空间为O（1）），则可选用______排序。
15、检索是为了在文件中寻找满足一定条件的记录而设置的操作。
检索可以按______检索。
也可以按______检索；按______检索又可以有 ______检索和______检索。
16、在顺序存储的二叉树中，编号为i和j的两个结点处在同一层的条件是______。
17、一棵有n个结点的满二叉树有______个度为1的结点、有______个分支（非终端）结点和______个叶子，该满二叉树的深度为______。
18、设有N个结点的完全二叉树顺序存放在向量A[1：N]中，其下标值最大的分支结点为______。
三、判断题19、哈希表与哈希文件的唯一区别是哈希文件引入了“桶”的概念。
（）20、对处理大量数据的外存介质而言，索引顺序存取方法是一种方便的文件组织方法。
（）21、在链队列中，即使不设置尾指针也能进行入队操作。
（）22、稀疏矩阵压缩存储后，必会失去随机存取功能。
（）23、哈夫曼树度为1的结点数等于度为2和0的结点数之差。
（）24、对于有n个结点的二叉树，其高度为log2n。
（）25、快速排序和归并排序在最坏情况下的比较次数都是O（nlog2n）。
（）26、线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。
（）27、连通图上各边权值均不相同，则该图的最小生成树是唯一的。
（）28、有向图中顶点V度等于其邻接矩阵中第V行中的1的个数。
（）四、简答题29、对于具有n个叶结点且所有非叶结点都有左、右孩子的二叉树。
(1)试问这种二叉树的结点总数是多少?(2)试证明2-（li-1）=1。
其中：l i表示第i个叶结点所在的层号（设根结点所在层号为1）。
30、将下列由三棵树组成的森林转换为二叉树（只要求给出转换结果）。
31、二叉树的带权路径长度（WPL）是二叉树中所有叶结点的带权路径长度之和，给定一棵二叉树T，采用二叉链表存储，节点结构为：其中叶节点的weight域保存该结点的非负权值。
设root为指向T的根节点的指针，设计求T的WPL的算法。
要求：（1）给出算法的基本设计思想。
（2）使用C或C++语言，给出二叉树结点的数据类型定义。
（3）根据设计思想，采用C或C++语言描述算法，关键之处给出注释。
五、算法设计题32、若x和y是两个采用顺序结构存储的串，编写一个比较两个串是否相等的函数。
33、给出以十字链表作存储结构，建立图的算法，输入(i，j，v)，其中i，j为顶点号，v 为权值。
34、串以静态存储结构存储，结构如下所述，试实现串操作equal算法。
35、假设在二叉链表的结点中增设两个域：parent域指示其双亲结点：flag域（取值为0~2）区分在遍历过程中到达该结点时应继续向左、向右或访问该结点。
试以此存储结构编写不用栈进行后序遍历的递推形式的算法。
参考答案一、选择题1、【答案】C2、【答案】B3、【答案】A4、【答案】B5、【答案】B6、【答案】A7、【答案】C8、【答案】C9、【答案】A10、【答案】C二、填空题11、【答案】① 1；1；f（m，n-1）；n② 912、【答案】n；n+113、【答案】0；j；i；0；indegree[i]=0；[vex][i]；k==l；indegree[i]=0【解析】有向图用邻接矩阵表示时，顶点i的入度等于第i列的所有元素之和。
拓扑排序过程：首先将入度为0的顶点全部进栈。
然后弹出栈顶结点，并将与弹出的顶点相连的其他顶点的入度减一，然后判断这些顶点的入度是否为零，如果为零，继续进栈，重复这些操作，完成拓扑排序。
14、【答案】归并；堆15、【答案】关键字；记录号；记录号；顺序；直接16、【答案】++a*b3*4-cd；18【解析】中缀式相当于中序遍历，前缀式相当于前序遍历，后缀式相当于后序遍历。
17、【答案】【解析】满二叉树没有度为1的结点，度为0的结点等于度为2的结点个数+1。
18、【答案】【解析】最大的分支结点是最后一个叶子结点的父结点。
三、判断题19、【答案】×20、【答案】×21、【答案】√22、【答案】√23、【答案】×24、【答案】×25、【答案】×26、【答案】×27、【答案】√28、【答案】×四、简答题29、答：（1）根据二叉树中度为2的结点个数等于叶结点个数减1的性质，故具有n个叶结点且非叶子结点均有左子树的二叉树的结点数是2n-1。
（2）证明：当i=1时，2-（1-1）=20=1，公式成立。
设当i=n-1时公式成立，证明当i=n时公式仍成立。
设某叶结点的层号为t，当将该结点变为内部结点，从而再增加两个叶结点时，这两个叶结点的层号都是t+1，对于公式的变化，是减少了一个原来的叶结点，增加了两个新叶结点，反映到公式中，因为2-（t-1）=2-（t+1-1）+2-（t+1-1），所以结果不变，这就证明当i=n时公式仍成立。
证毕。
30、答：森林转换为二叉树分以下三步：（1）连线（将兄弟结点相连，各树的根看作兄弟）。
（2）切线（保留最左边子女为独生子女，将其他子女分支切掉）。
（3）旋转（以最左边树的根为轴，顺时针向下旋转45度）。
所以由上面三棵树转换得到的二叉树如图所示：31、答：（1）算法的基本思路是利用递归的思想来求解二叉树的带权路径长度，如果当前节点不是叶子节点，那么当前节点为根的树的带权路径长度便等于它的子树的带权路径长度之和，对于此函数要传入一个当前节点的树高的形参，那么递归调用孩子节点时只需要将这个形参加一即可。
（2）五、算法设计题32、答：算法如下：33、答：算法如下：34、答：算法如下：35、答：算法如下：。
