山东校园网：www.xyw.me 山东招生考试资讯网 2009年普通高等教育专升本考试 《数据结构》（C语言版）试题
计算机科学与技术专业综合二试题（科目1，满分：50分）
题号 得分 一 二 三 四 总分 一、填空题（10分，每空0.5分） 1．根据数据元素之间关系的不同，数据的逻辑结构划分为_______、________、________、__________。
2．栈是一种特殊的线性表，它允许在表的一端进行______________操作，栈中元素的进出原则为__________________。
3．深度为k的二叉树其结点数最多有__________________结点。
4．通常像交通、道路问题的数学模型是一种称为______________的数据结构。 5．算法的五个重要的特性是______、________、______、_______、_______。 6．两个字符串相等的充分必要条件是____________________________________。 7．在一棵二叉树中，度为零的结点个数为n0，度为2的结点个数为n2，则有n0=______。
8．树的度是指______________________________________________的最大值。 9．在一个有向图中，某个结点的度是指该结点的_________和_________之和。 10．在线性表的的二分查找法中要求线性表的存储结构必须是采用______________，且表中的元素必须是___________________。 二、选择题（10分，每题1分）
1．一个具有10个顶点的无向完全图应有___________条边。 （ ） A．9 B．45 C．55 D．90
2．长度为n（1…n）的顺序循环队列中，front和rear分别指示队首和队尾，判断对列为满队列的条件是 （ ） A．rear=front B．（rear+1）%n==front C．rear=0 D．front=0
更多专升本资料 请到山东校园网：www.xyw.me
1
山东校园网：www.xyw.me 山东招生考试资讯网 3．由_______________组成的集合是一个数据对象。 （ ） A．不同类型的数据项 B．不同类型的数据元素 C．相同类型的数据项 D．相同类型的数据元素
4．_______________是表示线性数据结构的。 （ ） A．循环链表 B．邻接多重表 C．孩子链表 D．单链表
5．设一个栈的入栈元素序列为a，b，c，d，e，则不可得到出栈的元素序列有 （ ）
A．edcba B．decba C．dceab D．abcde
6．________________又是一棵满二叉树 。 （ ） A．二叉排序树 B．深度为5有31个结点的二叉树 C．有15个节点的完全二叉树 D．哈夫曼（Huffman）树
7．折半查找有序表（2，5，8，20，25，36，40，60），若查找元素60，需依次与表中元素____进行比较。 （ ） A．20，36，40，60 B．25，40 C．25，40，60 D．20，36，40 8．查找哈希（Hash）表，解决冲突的方法有 （ ） A．链地址法 B．线性探测再散列法
C．直接地址法 D．除留余数法
9．一个排序算法时间复杂度的大小_________有关。 （ ） A．不与所需移动记录的数目 B．与该算法的稳定性
C．与所需比较关键字的次数 D．与所需辅助存储空间的大小
10．数据的基本单位是 （ ） A．结点 B．数据元素 C．数据类型 D．数据项
更多专升本资料 请到山东校园网：www.xyw.me 2
山东校园网：www.xyw.me 山东招生考试资讯网 三、求解下列问题（10分，每题5分）
1．将下面的一个普通树转换成一棵二叉树，并写出它的先序、中序、后序三种遍历的遍历序列。
转换后的二叉树：
更多专升本资料 请到山东校园网：www.xyw.me
3
山东校园网：www.xyw.me 山东招生考试资讯网 先序遍历序列：
中序遍历序列：
后序遍历序列：
更多专升本资料 请到山东校园网：www.xyw.me
4
