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

211山东专升本-《数据结构》真题.txt对的时间遇见对的人是一生幸福；对的时间遇见错的人是一场心伤；错的时间遇见对的人是一段荒唐；错的时间遇见错的人是一声叹息。 本文由hanliankuo贡献
doc文档可能在WAP端浏览体验不佳。建议您优先选择TXT，或下载源文件到本机查看。
2011 年普通高等教育专升本考试 （ 《数据结构》 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 C．55 B．45 D．90 （ ）
一
二
三
四
总分
2．长度为 n（1…n）的顺序循环队列中，front 和 rear 分别指示队首和队尾，判 断对列为满队列的条件是 A．rear=front C．rear=0
1
（ B． （rear+1）%n==front D．front=0
）
3．由组成的集合是一个数据对象。 A．不同类型的数据项 C．相同类型的数据项 4．是表示线性数据结构的。 A．循环链表 C．孩子链表 B．邻接多重表 D．单链表
（
）
B．不同类型的数据元素 D．相同类型的数据元素 （ ）
5．设一个栈的入栈元素序列为 a，b，c，d，e，则不可得到出栈的元素序列有 （ ） A．edcba C．dceab B．decba D．abcde 。 （ ）
6．又是一棵满二叉树 A．二叉排序树 C．有 15 个节点的完全二叉树
B．深度为 5 有 31 个结点的二叉树 D．哈夫曼（Huffman）树
7．折半查找有序表（2，5，8，20，25，36，40，60） ，若查找元素 60，需依次 与表中元素进行比较。 A．20，36，40，60 C．25，40，60 8．查找哈希（Hash）表，解决冲突的方法有 A．链地址法 B．线性探测再散列法 C．直接地址法 D．除留余数法 9．一个排序算法时间复杂度的大小有关。 A．不与

所需移动记录的数目 B．与该算法的稳定性 C．与所需比较关键字的次数 D．与所需辅助存储空间的大小 10．数据的基本单位是 A．结点 B．数据元素 C．数据类型 （ ） D．数据项 （ ） （ ） B．25，40 D．20，36，40 （ ）
2
三、求解下列问题（10 分，每题 5 分） 求解下列问题（ 1．将下面的一个普通树转换成一棵二叉树，并写出它的先序、中序、后序三种 遍历的遍历序列。
转换后的二叉树：
3
先序遍历序列：
中序遍历序列：
后序遍历序列：
4
2．用克鲁斯卡尔所算法将下面的图构造成最小生成树，画出生成过程。
5
四、程序填空（10 分，每空 1 分） 程序填空（ 1．将下面折半查找算法补充完整 算法说明：已知 r[1…n]是 n 个记录的递增有序表，用折半查找法查找关键字 为 k 的记录，若查找失败返回零；否则返回该记录的序号值。查找表顺序存储结 构定义如下：
#define
MAXSIZE
100
typedef struct { keytype } Nodetype； typedef Nodetype Sqlist[MAXSIZE] key；
算法（C 函数） ： int binsearch（Sqlist r， datatype k，int n） { int low=1， high=n， mid
while（） { ； if（r[mid].key= =k） ； else if（r[mid].key>k） ； else ； } Return（0） ； }
6
2．将下面单链表的插入算法补充完整。 typedef { DataType struct node data； *next；
}LNode，*Linklist；
int listinsert（LinkList { LinkList int j=0;
head，int
i，DataType
x）
p=head，s；
while（p！=NULL&&jdata=x； ； ； return（1） ； }
7
五、算法设计（10 分） 算法设计（ 已知 S 为顺序栈。 写出 S 的存储结构类型描述。 编写算法实现将元素 x 入栈操作 Push（S，x） ，入栈成功返回 1，否则返回 0 和删除栈顶元素的出栈操作 Pop（S） 出栈成功返回 1，否则返回 0。
8

1