山西省专升本考试试题
山西省专升本考试试题 数据结构试题 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、评价数据结构的两条基本
标准
excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载
是:( )和( )。 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、单链表从任何一个结点出发,都能访问到所有结点.......