山西省专升本考试试题

山西省专升本考试试题 山西省专升本考试试题 数据结构试题 1(222) 一、是非题(下列各题，你认为正确的，请在题干的括号内打“?” ，错的打“×” 。每题 1 分，共 15 分) 1、 数据结构概念包括数据之间的逻辑结构， 数据在计算机中的存储方式和数据的运算三个 方面...............( ) 2、线性 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 中的每个结点最多只有一个前驱和一个后继。......( ) 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、 评价 LEC评价法下载LEC评价法下载评价量规免费下载学院评价表文档下载学院评价表文档下载 数据结构的两条基本标准是:( )和( )。 3、对于顺序存储的栈，因为栈的空间是有限的，在进行( )运算时，可能发生栈的上溢，在 进行( )运算时，可能发生栈的下溢。 4、对于单链表形式的队列，其空队列的 F 指针和 R 指针都等于( )。 5、若 S1=„linked,st',S2='ring',则 S1//S2=( )。 6、设根结点的层数为 0，定义树的高度为树中层数最大的结点的层数加 1。则高度为 k 的二 叉树具有的结点数目，最少为( ),最多为( )。 三、单选题(在本题的每一小题的备选 答案 八年级地理上册填图题岩土工程勘察试题省略号的作用及举例应急救援安全知识车间5s试题及答案 中，只有一个答案是正确的，请把你认为正确答 案的题号，填入题干的括号内。多选不给分。每题 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、单链表从任何一个结点出发，都能访问到所有结点.......