第1页 / 共30页
第2页 / 共30页
第3页 / 共30页
第4页 / 共30页
第5页 / 共30页
第6页 / 共30页
第7页 / 共30页
第8页 / 共30页
专升本历年数据结构真题.doc
2009 年普通高等教育专升本统一考试
计算机科学与技术专业综合二试卷
本试卷共 13 页。满分 100 分，考试时间是 180 分钟。考试结束后，将本试卷交回。答
题前考生务必将自己的姓名、准考证号、座号和所在学校填写在规定的位置。
数据结构（50 分）
一、填空题（10 分，每空 1 分）
1．根据数据元素之间关系的不同，数据的逻辑结构划分为________、________、________、
________。
2．栈是一种特殊的线性表，它允许在表的一端进行__________操作，栈中元素的进出原则
为_____________。
3．深度为 K 的二叉树其结点数最多有__________个结点。
4．通常象交通、道路问题的数学模型是一种称为_________的数据结构。
5．算法的五个重要的特性是________、__________、___________、_________、________。
6．两个字符串相等的充分必要条件是_____________________________。
7．在一棵二叉树中，度为零的结点个数为 n0，度为 2 的结点个数为 n２，则有 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
3．由________组成的集合是一个数据对象。
A．不同类型的数据项
B．不同类型的数据元素
C．相同类型的数据项
D．相同类型的数据元素
4．______是表示线性数据结构。
（
）
A．循环链表
B．邻接多重表 C．孩子链表
D．单链表
1
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．数据项
三、求解下列问题（10 分，每题 5 分）
1．将下面的一个普通树转换成一棵二叉树，并写出它先序、中序、后序三种遍历的遍历序
列。
C
B
D
F
A
G
H
E
I
K
J
L
M
转换后的二叉树：
先序遍历序列：
中序遍历序列：
后序遍历序列：
2
2．用克鲁斯卡尔算法将下列的图构造成最小生成树，画出生成过程。
0
1
5
6
6
5
1
3
6
3
2
5
4
2
5
4
四、程序填空（10 分，每空 1 分）
1．将下面折半查找的算法补充完整
算法说明：已知 r[1..n]是 n 个记录的递增有序表，用折半查找法查找关键字为 k 的记录，若
查找失败返回零；否则返回该记录的序号值。查找表顺序存储结构定义如下：
#define MAXSIZE 100
typedef struct
{
Keytype key;
}Nodetype;
typedef Nodetype sqlist[MAXSIZE];
算法（C 函数）
binsearch(sqlist y,datatype k,int n)
int
int low=1,high=n,mid;
{
while(______________)
{
___________________;
if(r[mid].key==k)
________________;
else if (r[mid].key>k)
________________;
3
else
________________;
}
return(0) ;
}
2.将下列单链表的插入算法补充完整。
算法说明，在带有头结点的单链线性表中第 i 个位置之前插入元素 x；
data;
_____________
typedef
{DateType
Struct node
}Lnode,*LinkList;
int listinsert(LinkList head,int I,DataType x)
{
*next;
p=head,s;
LinkList
int j=0;
while(p!=NULL&&jdata=x;
_________________;
_________________;
return(1);
}
五、算法设计（10 分）
已知 S 为顺序栈。写出 S 的存储结构类型描述。编写算法实现将元素 x 入栈操作 push(S,x),
入栈成功返回 1，否则返回 0 和删除栈顶元素的出栈操作 Pop(S)，出栈成功返回 1，否则返
回 0。
4
山东省 2009 年普通高等教育专升本统一考试
计算机科学与技术专业综合二试卷参考答案
数据结构（50 分）
一、填空题（10 分，每空 0.5 分）
1. 【答案】集合、线性结构、树形结构、图状结构或网状结构
【解析】相互之间存在一种或多种特定关系的数据元素的集合称为数据结构，根据数据元素
之间关系的不同特性通常分出了以上四种逻辑结构。
2．【答案】插入和删除、后进先出（LIFO）
【解析】考查的栈的定义及性质，队列的定义及性质也需要牢固掌握。
3. 【答案】2k-1
【解析】考查二叉树的性质 2。
4. 【答案】图
【解析】根据图数据结构的特性。
5．【答案】有穷性、确定性、可行性、输入（0 或多个）、输出（至少有 1 个）
【解析】算法是特定问题的求解步骤的一种描述，其五个基本性质如上。
6.【答案】串的长度相等且两串中对应位置的字符也相等
【解析】考查两个字符串相等的定义。
7．【答案】n2+1
【解析】考查二叉树的性质 3。
8.【答案】树内各结点的度
【解析】考查树的度的定义。
9．【答案】入度、出度
【解析】考查有向图中顶点度的定义。
10. 【答案】顺序存储、有序
【解析】因为折半查找需要拿表中第 mid（其中 mid=(low+high）/2)个元素与查找的关键字
进行比较，所以要求查找表需要能随机存取，因此，要求顺序存储；另外，实施折半查找的
前提必须是有序表，顺序表不可以。
二、选择题（本大题共 10 小题，每小题 1 分，共 10 分）
1. 【答案】B
【解析】根据具有 n 个顶点的无向完全图的边数为 n(n-1)/2，代入公式即可。
2. 【答案】B
5
【解析】在循环队列中队列满的条件是以牺牲一个存储空间为代价的，即当满足选项 B 时就
判断该队列已满。
3. 【答案】D
【解析】考查数据对象的定义。
4. 【答案】AD
【解析】无论是循环链表还是单链表都属于线性表的链式存储，所以选 A、D。邻接多重表
属于图的存储结构，孩子链表属于树的存储结构。
5. 【答案】C
【解析】考查栈的基本性质，选项 C 中 a 先于 b 入栈，因此出栈顺序 a 应该在 b 的后面。
6. 【答案】BC
【解析】考查完全二叉树的定义及二叉树的基本性质。
7. 【答案】A
【解析】该有序表中有 8 个元素，因此，折半查找时，查找第 8 个元素，根据判定树可以获
得需先后与第 4、6、7、8 个元素进行比较 4 次，所以选 A。
8. 【答案】AB
【解析】处理冲突的方法主要有四种：分别是开放定址法（包含线性探测再散列以及二次探
测再散列等）、再哈希法、链地址法和建立一个公共溢出区。
9. 【答案】C
【解析】一个排序算法的时间复杂度主要与所需关键字的比较次数有关。
10. 【答案】B
【解析】考查数据元素的概念。
三、求解下列问题（10 分，每题 5 分）
1．答：根据树与二叉树的转换方法，得出转化为的二叉树如下图所示：
A
G
C
B
D
F
E
H
I
J
K
L
M
由此可得先序遍历序列为：ABCDFEGHIJKLM
中序遍历序列为：CFDEBGJILMKHA;
2．答：根据克鲁斯卡尔算法思想画图表示最小生成树的生成过程如下：
后序遍历序列为：FEDCJMLKIHGBA
6
2
0
1
5
2
4
1
3
2
0
1
5
2
4
1
3
3
0
5
1
3
1
3
3
2
4
2
4
0
1
5
2
4
0
1
5
1
3
0
1
5
5
1
3
3
2
4
2
4
2
4
四、程序填空（本大题共 3 小题，每小题 5 分，共 15 分）
1．答：low<=high;
mid=(low+high)/2;
return(mid);
high=mid-1;
low=mid+1;
2．答：struct node
p=p->next;
Linklist 或是 LNode *
s->next=p->next;
p->next=s
(注意字母大小写与类型定义一致)
五、算法设计（本大题共 1 小题，共 10 分）
答：栈的类型定义：
typedef struct{
SElemType *base ；
SElemType *top；
int stacksize；
}sqstack；
入栈操作：
int push (sqstack &S，SElemType e){
if(S.top-S.base>=S.stacksize)
else { *S.top++ = e；
return 0；
return 1；
}
}
出栈操作：
int pop( sqstack &S , SElemType &e){
if(S.top = S.base) return 0；
else {
e = * -- S.top；
return 1；
7
}
}
山东省 2008 年普通高等教育专升本统一考试
计算机科学与技术专业综合二试卷
本试卷共 8 页。满分 100 分，考试时间是 180 分钟。考试结束后，将本试卷交回。答
题前考生务必将自己的姓名、准考证号、座号和所在学校填写在规定的位置。
数据结构（50 分）
一、单项选择题（10 分，每题 1 分）
1．若一个栈的输入序列位 1，2，3…,n，输出序列的第一个元素是 i,则第 i 个输出的元素
是
（
）
A．i-j-1
B．i-j
C．j-i+1
D．不确定的
2．循环队列存储在数组 A[0..m]中，则入队时的操作是
（
）
A．rear=rear+1
B．rear=(rear+1)mod(m-1)
C．rear=(rear+1)mod m
D．rear=(rear+1)mod(m+1)
3．二维数组 A 的每个元素是由 6 个字符组成的串,其下标 i=0,1,…8，列下标 j=1,2,3…10。
若 A 按行序位主序存储，元素 A[8][5]的起始地址与当 A 按列序为主序存储时的元素____的
起始地址相同。（设每个字符占一个字节）
A．A[8][5]
B．A[3][10]
C．A[5][8]
D．A[0][9]
4．下面说法不正确的是
A．广义表的表头总是一个广义表
B．广义表的表尾总是一个广义表
C．广义表难以用顺序存储结构
D．广义表可以是一个多层次的结构
5．算术表达式 A+B*C-D/E 转为前缀表达式后为
（
（
（
A．-A+B*C/DE
B．-A+B*CD/E
C．-+*ABC/DE
D．-+A*BC/DE
6．有 n 个叶子的哈夫曼树的结点总数为
（
A．不确定
B．2n
C．2n+1
D．2n-1
）
）
）
）
7．若 X 是中序线索二叉树中一个有左孩子的结点,且 X 不为根，则 X 的前驱为 （
）
A．X 的双亲
B．X 的右子树中最左的结点
C．X 的左子树中最右的结点
D．X 的左子树中最右叶结点
8．无向图 G=（V，E）, V={a,b,c,d,e,f}，E={{a,b},{a,e},{a,c},{b,e},{c,f},{f,d},{e,d}},
对该图进行广度优先遍历，得到的顶点序列正确的是
（
）
8
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
