试题科目代码:823科目名称:数据结构+操作系统注意：答案必须全部写在考点提供的答题纸上，写在试题上无效；答案要标注题号，答题纸要填写姓名和考号，并标注页码与总页数；交卷时，将答题纸与试题一起装入原试卷袋，用我校提供的密封条密封并签名。PartⅠ：数据结构部分一、单选题（每小题2分，共10小题，合计20分）1.判定一个队列QU（最多元素为m0）为满队列的条件是（A）QU->rear－QU->front==m0（B）．QU->rear－QU->front－1==m0（C）．QU->front==QU->rear（D）．QU->front==QU->rear+12.链表是一种采用（）存储结构存储的线性表（A）顺序（B）链式（C）星式（D）网状3.线性表若采用链式存储结构时，要求内存中可用存储单元的地址:（A）必须是连续的（B）部分地址必须是连续的（C）一定是不连续的（D）连续或不连续都可以4．线性表Ｌ在（）情况下适用于使用链式结构实现。（A）需经常修改Ｌ中的结点值（B）需不断对Ｌ进行删除插入（C）Ｌ中含有大量的结点（D）Ｌ中结点结构复杂5.若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为（）（A）i（B）n=i（C）n-i+1（D）不确定6.若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则最节省运算时间的存储方式是（）（A)单链表（B）双链表（C）仅有头指针的单循环链表（D）仅有尾指针的单循环链表7.树中所有结点的度之和等于所有结点数（）（A)加0（B）加1（C）减1（D）加n8在一棵具有n个结点的二叉链表中，所有结点的空域个数等于（）（A)n（B）n-1（C）n+1（D）2n9.某二叉树的先序序列和后序序列正好相反，则该二叉树一定是（）（A）空或只有一个结点（B）任一结点无左孩子（C）高度等于其节点数（D）任一结点无右孩子10.有10个结点的二叉树中，度为0的结点数为4，则度为2的结点数为（）。（A）3（B）4（C）5（D）6二、算法应用题（每小题10分，共3小题，合计30分）1、已知散列函数为H(key)=key%7，散列表长度为7(散列地址空间为0..6)，待散列序列为：(25，48，32，50，68)。要求：第1页共4页(1)根据以上条件构造一散列表，并用线性探测法解决有关地址冲突；(2)若要用该散列表查找元素68，给出所需的比较次数。2、给出一组关键字：29，18，25，47，58，12，51，10，分别写出按下列各种排序方法进行排序时的变化过程：1）归并排序，每归并一次书写一个次序。2）快速排序，每划分一次书写一个次序。3、已知一个表{jan,feb,mar,ap...
