1、第1页共5页三 峡 大 学2015年研究生入学考试试题(B卷)科目代码： 773 科目名称： 数据结构与算法 考试时间为3小时，卷面总分为150分答案必须写在答题纸上一、填空题（301.5分=45分）1数据的逻辑结构是从逻辑关系上描述数据，它与数据的 无关，是独立于计算机的。2设一组初始记录关键字序列为(49，38，65，97，76，13，27，50)，则以d=4为增量的一趟希尔排序结束后的结果为_ _ _。3栈顶的位置是随着 操作而变化的。4在串S=“structure”中，以t为首字符的子串有 个。5假设一个9阶的上三角矩阵A按列优先顺序压缩存储在一维数组B中，其中B0存储矩阵中第1个元素
2、a1,1,则B31中存放的元素是 。6一棵完全二叉树含有2015个结点，其中叶子结点的个数是_ _。 7已知一个图的广度优先生成树如右图所示，则与此相 应的广度优先遍历序列为 。 8在单链表上难以实现的排序方法有 和 。 9在有序表（12，24，36，48，60，72，84）中二分查找关键字72时所需进行的关键字比较次数为 。 10多重表文件和倒排文件都归属于 文件。第 2页11通常从四个方面评价算法的质量：_ 、_、_和_。12设指针变量p指向单链表中结点A，指针变量s指向被插入的结点X，则在结点A的后面插入结点X需要执行的语句序列：s-next=p-next; _;。13二维数组A149采
3、用行优先的存储方法，若每个元素占4个存储单元，且第一个元素的首地址为50，则A65的地址为_ _。14后缀算式9 2 3 +- 10 2 / -的值为_。中缀算式（3+4X）-2Y/3对应的后缀算式为_。15设某棵二叉树中度数为0的结点数为n0，度数为1的结点数为n1，则该二叉树中度数为2的结点数为_；若采用二叉链表作为该二叉树的存储结构，则该二叉树中共有_个空指针域。16用具有n个元素的一维数组存储一个循环队列，则其队尾指针总是指向队尾元素的_，该循环队列的最大长度为_。17AOV网是一种_的图。18在一个具有n个顶点的无向完全图中，包含有_条边，在一个具有n个顶点的有向完全图中，包含有_条
4、边。19快速排序的最坏时间复杂度为_，平均时间复杂度为_。20二维数组A74按行主序存储，且数组元素A00和A32的存储地址分别为101和185，则每个数组元素所占有的存储单元个数为_ _。21. 设某无向图G的顶点数为n，边数为e，所有顶点的度数之和为d，则e=_。二、运算题（36分+210分+14分+13分=65分）1在如下数组A中链接存储了一个线性表，表头指针为A 0.next，试写出该线性表。（6分） A 0 1 2 3 4 5 6 7 data605078903440next3572041第 3页2阅读算法，回答问题：（6分）void AC(List &L) InitList(L)；
5、 InsertRear(L，25)； InsertFront(L，50)； int a55，8，12，15，36; for(int i0; i5; i+) if (a i 20) InsertFront(L，ai)； else InsertRear(L，ai)； 该算法被调用执行后，得到的线性表L为： 3. 请画出与下列二叉树对应的森林。（6分）4设一组有序的记录关键字序列为(13，18，24，35，47，50，62，83，90)，查找方法用二分查找，要求构造二叉判定树，计算出查找关键字62时的比较次数,并计算出查找成功时的平均查找长度。（10分）第4 页5.一个线性表为B=（12，23，45
6、，57，20，03，78，31，15，36），设散列表为HT0.12，散列函数为H（key）= key % 13并用线性探查法解决冲突，请画出散列表，并计算等概率情况下查找成功的平均查找长度。（10分）6.已知一棵二叉树的前序遍历的结果序列是ABCEFGDHIJKLMON，中序遍历的结果是CFEGBAIJHDKMOLN，试写出这棵二叉树的后序遍历结果并画出二叉树。（14分）7. 设无向图G（所下图所示），要求给出该图的深度优先遍历和广度优先遍历的序列，并采用克鲁斯卡尔算法给出该图的最小生成树。（13分）三、算法填空，在画横线的地方填写合适的内容（10分）对顺序存储的有序表进行二分查找的递归算法
7、： int Binsch( ElemType A ,int low ,int high, KeyType K ) if (low = high) int mid = ; /1 if ( K= = A mid .key ) return mid; else if ( K Amid.key) return ; /2第 5页else return ; /3else return ; /4四、编写算法（8分+14分+8分=30分）1. 在如下二叉链表存储结构上，编写递归算法，计算二叉树中叶子结点数目。（8分）typedef char TElemType; / 树结点数据域暂且为字符类型typedef
8、struct BiTNode / 二叉树的类型定义 TElemType data; struct BiTNode *lchild,*rchild; BiTNode,*BiTree;void CalcLeafNum(BiTree T, int &count) /计算二叉树叶子数2编写递归算法：对于二叉树中每一个元素值为x的结点，删去以它为根的子树，并释放相应的空间。(14分)void DelSubTree(BiTree T, TElemType x)/递归删除二叉树中以x为根的子树3. 已知一维数组An中存有线性表的数据元素，编写算法，逆序创建单链线性表L。（8分）typedef int ElemType;typedef struct LNodeElemType data;Struct LNode *next;LNode, *LinkType; / 结点类型和指针类型void CreateList_L(LinkType &L, ElemType A, int n)
