山西省专升本考试试题_山西省专升本历年真题
山西省专升本考试试题由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“山西省专升本历年真题”。
山西省专升本考试试题
数据结构试题1(222)
一、是非题(下列各题，你认为正确的，请在题干的括号内打“√”，错的打“×”。每题1分，共15分）
1、数据结构概念包括数据之间的逻辑结构，数据在计算机中的存储方式和数据的运算三个方面...............()
2、线性表中的每个结点最多只有一个前驱和一个后继。......()
3、从本质上看，文件是一种非线性结构。..................()
4、线性的数据结构可以顺序存储，也可以链接存储。非线性的数据结构只能链接存储。.......................()
5、栈和队列逻辑上都是线性表。..........................()
6、单链表从任何一个结点出发，都能访问到所有结点........()
7、单链表形式的队列，头指针F指向队列的第一个结点，尾指针R指向队列的最后一个结点。.................................................()
8、对某一确定的可利用空间表，给定一串内存请求，若采用最佳适配和首次适配这两
种方法之中的一种能满足该串请求，则也一定能用另一种方法满足该串请求。()
9、多维数组是向量的推广。..............................()
10、设串S=a1a2...ai...aj...an,则有ord(ai)>ord(aj)。....()
11、设串S的长度为n,则S的子串个数为n(n+1)/2。...........()
12、一般树和二叉树的结点数目都可以为0。................()
13、在拓朴排序序列中，任意两个相继结点Vi和Vj都存在从Vi到Vj的路径。()
14、网络的最小代价生成树是唯一的。.....................()
15、磁带是顺序存取的外存储设备。.......................()
二、填空题(每空1分，共10分）
1、在树结构里，有且仅有一个结点没有前驱，称为根。非根结点有且仅有一个(),且存在一条从根到该结点的()。
2、评价数据结构的两条基本标准是：()和()。
3、对于顺序存储的栈，因为栈的空间是有限的，在进行()运算时，可能发生栈的上溢，在进行()运算时，可能发生栈的下溢。
4、对于单链表形式的队列，其空队列的F指针和R指针都等于()。
5、若S1=‘linked￡st',S2='ring',则S1//S2=()。
6、设根结点的层数为0，定义树的高度为树中层数最大的结点的层数加1。则高度为k的二叉树具有的结点数目，最少为(),最多为()。
三、单选题(在本题的每一小题的备选答案中，只有一个答案是正确的，请把你认为正确答案的题号，填入题干的括号内。多选不给分。每题3分，共9分)
1、对于顺序存储的队列，存储空间大小为n，头指针为F，尾指针为R。若在逻辑上看一个环，则队列中元素的个数为......................()
⑴.R-F
⑵.n+R-F
⑶.(R-F+1)mod n
⑷.(n+R-F）mod n
2、n个记录直接插入排序所需的记录最小移动次数是.......()
⑴.2(n-1)
⑵.2n
⑶.(n+3)(n-2)/2
⑷.n2/2
3、现有一“遗传”关系：设x是y的父亲，则x可以把它的属性遗传给y。表示该遗传关系最适合的数据结构为..............................⑴.向量
⑵.树
⑶.图
⑷.二叉树
四、简单应用题(第1题6分，其它题每题3分，共18分）
1、已知稀疏矩阵如下：
⑴请写出该稀疏矩阵顺序存储的带辅助行向量的二元组表示。
⑵请写出该稀疏矩阵链接存储的带行指针向量的单链表示。
解：
2、在包含n个关键码的线性表里进行顺序查找，若查找第i个关键码的概率为pi，pi如下分布：p1=1/2,p2=1/4,......,pn-1=1/2n-1,pn=1/2n。求成功检索的平均比较次数。
解：
3、设根结点的层数为0，定义树的高度为树中层数最大的结点的层数加1，试问高度为k≥
1、非叶结点的度数等于1的树有多少棵？
解：
4、给出下列二叉树的前序序列。
解：
5、设二叉树t的对称序序列为BADCE，后序序列为BDECA，请给出二叉树。
解：
五、综合题(每题4分，共16分)
1、假设有如下关键码及其散列函数值：
key ABCD ABDC ACBD ACDB BDAC BACD CADB CBDA
h(key)4 4 0 1 2 3 6 5
基本存储区编址为0--7，请用建立分离的同义词子表的方法解决碰撞问题，画出其存储图式。
解：
2、下面列举的是常用的排序方法：直接插入排序，二分法插入排序，起泡排序，快速排序，直接选择排序，堆排序，归并排序。试问，哪些排序方法是稳定的？
解：
3、设有50个值不同的元素存于内存一片连续单元中，若用顺序选择的方法，选出这50个元素的最大值和最小值则至少需要97次比较。请给出另一种选出最大值和最小值的方法，其比较次数一定少于97次，说明该方法的操作过程和比较次数。
解：
4、快速排序在什么情况下，所需记录之关键码的比较次数为最多？此时记录之关键码比较次数应为多少？
解：
六、算法设计题(第1、2题，每题8分，第3题6分，第4题10分，共32分)
1、双链表结点类型和变量说明如下：
TYPE pointer=↑node;
node=RECORD
info:datatype;
llink,rlink:pointer
END;
double=RECORD
head,rear:pointer
END;
VAR DL:double;
p,q:pointer;
设DL.head和DL.rear已分别指向该双链表的头结点和尾结点。下述算法应实现的操作为：在信息值为x0的结点(设该结点一定存在)之后，插入信息值为x1的新结点。试填充算法中的空框，使该算法正确。
⑴[置初值] P←DL.head ⑵[查找]
循环 当P↑info≠x0时，反复执行
⑶[准备结点〕
new(q)；q↑.info←x1 ⑷[插入〕
若P=DL.rear
则q↑.rlinknil；q↑.llinkP；、答案
1、数据结构概念包括数据之间的逻辑结构，数据在计算机中的存储方式和数据的运算三个方面...............(y)
2、线性表中的每个结点最多只有一个前驱和一个后继。......(y)
3、从本质上看，文件是一种非线性结构。..................(n)
4、线性的数据结构可以顺序存储，也可以链接存储。非线性的数据结构只能链接存储。.......................(n)
5、栈和队列逻辑上都是线性表。..........................(y)
6、单链表从任何一个结点出发，都能访问到所有结点........(n)
7、单链表形式的队列，头指针F指向队列的第一个结点，尾指针R指向队列的最后一个结点。.................................................(?)
8、对某一确定的可利用空间表，给定一串内存请求，若采用最佳适配和首次适配这两
种方法之中的一种能满足该串请求，则也一定能用另一种方法满足该串请求。(n)
9、多维数组是向量的推广。..............................(y?)
10、设串S=a1a2...ai...aj...an,则有ord(ai)>ord(aj)。....(n)
11、设串S的长度为n,则S的子串个数为n(n+1)/2。...........(n)
12、一般树和二叉树的结点数目都可以为0。................(n)
13、在拓朴排序序列中，任意两个相继结点Vi和Vj都存在从Vi到Vj的路径。(n)
14、网络的最小代价生成树是唯一的。.....................(n)
15、磁带是顺序存取的外存储设备。.......................(y?)
二、填空题(每空1分，共10分）
1、在树结构里，有且仅有一个结点没有前驱，称为根。非根结点有且仅有一个(前驱),且存在一条从根到该结点的(路径)。
2、评价数据结构的两条基本标准是：(存贮需要量)和(运算的时间效率)。
3、对于顺序存储的栈，因为栈的空间是有限的，在进行(push)运算时，可能发生栈的上溢，在进行(pop)运算时，可能发生栈的下溢。
4、对于单链表形式的队列，其空队列的F指针和R指针都等于(null)。
5、若S1=‘linked￡st“,S2=”ring“,则S1//S2=(linked￡string)。
6、设根结点的层数为0，定义树的高度为树中层数最大的结点的层数加1。则高度为k的二叉树具有的结点数目，最少为(k),最多为((2^k)-1)。
三、单选题(在本题的每一小题的备选答案中，只有一个答案是正确的，请把你认为正确答案的题号，填入题干的括号内。多选不给分。每题3分，共9分)
1、对于顺序存储的队列，存储空间大小为n，头指针为F，尾指针为R。若在逻辑上看一个环，则队列中元素的个数为......................(d)
⑴.R-F
⑵.n+R-F
⑶.(R-F+1)mod n
⑷.(n+R-F）mod n
2、n个记录直接插入排序所需的记录最小移动次数是.......(a)
⑴.2(n-1)
⑵.2n
⑶.(n+3)(n-2)/2
⑷.n2/2
3、现有一“遗传”关系：设x是y的父亲，则x可以把它的属性遗传给y。表示该遗传关系最适合的数据结构为..............................b
⑴.向量
⑵.树
⑶.图
⑷.二叉树
山西省专升本考试试题 数据结构试题1(222) 一、是非题(下列各题，你认为正确的，请在题干的括号内打“√”，错的打“×”。每题1分，共15分）1、数据结构概念包括数据之间的逻辑结构......
2010年专升本高代试题一、选择题（4小题）1.向量在基下的坐标2.两向量正交的条件3.实系数多项式因式分解定理4.AB=0，则R（A）+R（B）不超过n二、填空题（4小题）1.g(x)x21,f(x)x32x22x3,求g(x......
山西省二○○五年专升本招生考试试题实用英语（003）Part Ⅰ.Structure (1 point×20=20 points) Directions: This part is to test your ability to construct grammatically......
2009年山西省汉语言文学专业专升本试题（现代文学）一、单选1.1917年1月胡适的《文学改良刍议》出版于2.《人的文学》的作者3.建国后第一次有关对“资产阶级唯心主义”的文化批......
2017年上半年山西省普法考试考试试题一、单项选择题（共 25题，每题2分，每题的备选项中，只有1个事最符合题意） 1、公民应当增强环境保护意识，采取（ A ）的生活方式，自觉履行环境保护义务......
