山东轻工业学院数据结构2004真题

山东轻工业学院 2004年攻读硕士学位研究生入学考试试题（答案一律写在答题纸上，答在试题上无效，试题附在答卷内交回）考试科目：数据结构试题适用专业：计算机应用技术 B 卷共 2 页 B 卷第 1页一、选择题（每空2分，共20分）（答案写在答题纸上）1、一个栈的入栈序列是123，则栈的不可能的输出序列为。A.321B.123C.312D.1322、广义表（（（）），（））的表头为，表尾为。A.（）B.（（））C.（（（）））D.（（（（））））3、在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的倍；所有顶点的度数之和等于所有边数的倍。A.1B.2C.3D.44、下面可以判断出一个有向图中是否有环（回路）？A.深度优先遍历B.拓朴排序C.求最短路径D.求关键路径5、对二叉排序树进行遍历，可以得到该二叉树所有结点构成的排序序列。A.前序B．中序C．后序D．按层次6、在一个无序的顺序表上进行查找，可以采用下面哪一种查找方法_______。A顺序查找B折半查找C静态树表的查找D索引顺序表的查找7、下述二叉树中，满足性质：从任一节点出发到根的路径上所经过的节点序列按其关键字有序。A.二叉排序树B.哈夫曼树C.AVL树D.堆8、下列排序方法中_______是稳定的排序方法。A.基数排序B.快速排序C.堆排序D.希尔排序二、（共20分）已知二叉树如图1所示。1、写出对此二叉树分别进行先序、中序、后序、层次遍历后的结点序列。（8分）2、对此二叉树进行后序线索化。（7分）3、将此二叉树转化为森林。（5分）三、（共26分）已知一无向图如图2所示。1、给出该图的邻接矩阵。（6分）2、写出从顶点V1出发对该图进行深度优先搜索和广度优先搜索遍历得到的顶点序列。（10分）3、画出其深度优先生成树和广度优先生成树。（10分） V1 图 2 V2 V3 V6 V7 V4 V5 V8 A C B D E F H G 图 1B 卷第 2 页四、（共20分）给定关键字序列{46，88，45，39，70，58，101，10，66，34}1、生成相应的二叉排序树，并求等概率情况下查找成功的平均查找长度ASL。(10分)2、手工执行冒泡排序算法，写出每一趟排序结束时的关键码状态。(10分)五、（10分）设给定权集w＝｛2，3，4，7，8，9｝，试构造关于w的一棵哈夫曼树。（注意事项：以下算法设计题建议采用类C语言书写）六、（6分）已知整型矩阵A[n][n]。写一算法，计算矩阵两条对角线上的元素的乘积。七、（共18分）已知带头节点的双向链表L，P是指向某结点的指针，S指向一个即将插入的新节点（如图3所示）（设节点中指向其前驱的指针为prior，指向其后继的指针为next）。1、写出在P指向的结点之前插入S结点的语句序列。（5分）2、写出删除P指向的结点的语句序列。（3分）3、求L的表长。（10分）八、（共15分）已知n个整型元素按递增有序存放于数组A中，并设A的空间大于n＋1：1、编写函数查找一个元素值等于x的元素位置。（要求以较高的效率实现）（10分）2、若查找x成功，则删除此元素；否则，插入此元素。（5分）九、（15分）已知二叉树T采用顺序存储结构存储于数组 BT[0..n]中。试写一算法，计算T的深度。（设在数组中元素值为 null 表示空节点） P S 图 3