2009山东专升本《数据结构》真题

PAGEPAGE82009年普通高等教育专升本考试《数据结构》（C语言版）试题计算机科学与技术专业综合二试题（科目1，满分：50分）题号题号一二三四总分得分一、填空题（10分，每空0.5分）根据数据元素之间关系的不同，数据的逻辑结构划分为 、 、 、 。栈是一种特殊的线性表，它允许在表的一端进行 操作，栈元素的进出原则为 。深度为k的二叉树其结点数最多有 结点。通常像交通、道路问题的数学模型是一种称为 的数据结构。算法的五个重要的特性是 、 、 、 、 。两个字符串相等的充分必要条件是 。在一棵二叉树中，度为零的结点个数为n0，度为2的结点个数为n2，则n0= 。树的度是指 的最大值。在一个有向图中，某个结点的度是指该结点的 和 之和。10．在线性表的的二分查找法中要求线性表的存储结构必须是采用 ，且表中的元素必须是 二、选择题（10分，每题1分）一个具有10个顶点的无向完全图应有 条边。 （ ）A．9 B．45C．55 D．90n（1…n）的顺序循环队列中，frontrear分别指示队首和队尾，判断对列为满队列的条件是A．rear=front（B（rear+）%n==front）C．rear=0D．front=0由 组成的集合是一个数据对象。 （ ）不同类型的数据项 B．不同类型的数据元素C．相同类型的数据项 相同类型的数据元素 是表示线性数据结构的。 （ ）循环链表 B．邻接多重表C．孩子链表 D．单链表设一个栈的入栈元素序列为a，b，c，d，e，则不可得到出栈的元素序列有（ ）edcba B．decbaC．dceab D．abcde 又是一棵满二叉树。 （ ）A．二叉排序树 B．深度为5有31个结点的二叉C．有15个节点的完全二叉树D．哈夫曼（Huffman）树7．折半查找有序表2582025364060，若查找元素60，需依与表中元素 进行比较。 （ ）A．20，36，40，60 B．25，40C．25，40，60 D．20，36，408．查找哈希（Hash）表，解决冲突的方法有 （ 链地址法BC．直接地址法D．除留余数法一个排序算法时间复杂度的大小 有关。 （ ）不与所需移动记录的数目B．与该算法的稳定性C．与所需比较关键字的次数D数据的基本单位是 （ ）结点 B．数据元素 C．数据类型 D．数据项三、求解下列问题（10分，每题5分）1遍历的遍历序列。转换后的二叉树：先序遍历序列：中序遍历序列：后序遍历序列：2．用克鲁斯卡尔所算法将下面的图构造成最小生成树，画出生成过程。四、程序填空（10分，每空1分）将下面折半查找算法补充完整算法说明：已知r[1…n]n个记录的递增有序表，用折半查找法查找关键字k构定义如下：#definetypedefMAXSIZEstruct100{keytype key；}Nodetype；typedef Nodetype Sqlist[MAXSIZE]算法（C函数：intbinsearch（Sqlistr，datatypek，intn）{int low=1， high=n， midwhile（ { ；if（r[mid].key==k） ；elseif（r[mid].key>k） ；else ；}Return（0；}将下面单链表的插入算法补充完整typedef {DataType data；struct node *next；}LNode，*Linklist；intlistinsert（LinkList head，int i，DataType x）{LinkList p=head，s；int j=0;while（p！=NULL&&j<i－1）{ ；j＋＋；}ip==