数据结构(I卷)

《数据结构(I卷)》由会员分享，可在线阅读，更多相关《数据结构(I卷)（8页珍藏版）》请在装配图网上搜索。

1、数据结构试卷(I卷)班级:_学号:_姓名:_得分:_题号一二三四五六七八九十成绩复核得分阅卷题目部分，(卷面共有45题,100分,各大题标有题量和总分)一、判断正误(11小题,共11分)1即使对不含相同元素的同意输入序列进行两组不同的、合法的入栈和出栈组合操作，所得的输出序也一定相同。（ ）2栈和队列都是限制存取点的线性结构。( )3任何一个非空广义表，其表头可能是单元素或广义表，其表尾必定是广义表。( ) 4己知二叉树的前序遍历序列和后序遍历序列并不能唯一地确定这棵树，因为不知道树的根结点是哪一个。( )5有n个数存放在伊维数组h1n中，在进行顺序查找时这n个数的排列有序或无序其平均查找长度

2、小同。( ) 6二叉树中，具有两个子女的结点的中序后继结点最多只能有一个子女。7用希尔(Shell)方法排序时，若关键字的初始排序杂乱无序，则排序效率就低。（ ）8外部排序是把外存文件调入内存，可利用内部排序的方法进行排序，因此排序所花的时间取决于内部排序的时间。 （ ）9完全二叉树就是满二叉树。（ ）10在散列法中，一个可用散列函数必须保证绝对不产生冲突。（ ）11快速排序是对起泡排序的一种改进。( )二、单项选择题(20小题,共42分)1在双向循环链表中，在p指针所指的结点后插入一个指针q所指向的新结点，其修改指针的操作是_A、 B、 C、 D、2双向链表中有两个指针域，llink和rli

3、nk分别指向前趋及后继，设p指向链表中的一个结点，现要求删去p所指结点，则正确的删除是（ ）（链中结点数大于2，p不是第一个结点）A、p.llink.rlink:=p.llink; p.llink.rlink:=p.rlink; dispose(p); B、dispose(p); p.llink.rlink:=p.llink; p.llink,rlink:=p.rlink; C、p.llink.rlink:=p.llink; dispose(p); p.llink.rlink:=p.rlink; D、以上A，B，C都不对。 3某堆栈的输入序列为a, b，c ，d,下面的四个序列中，不可能是它的

4、输出序列的是 A、 a，c，b，d B、 b, c，d，a C、 c, d，b, a D、 d, c，a，b4栈和队都是A、顺序存储的线性结构 B、 链式存储的非线性结构 C、 限制存取点的线性结构 D、 限制存取点的非线性结构5数组的基本操作主要包括 。 A、 建立与删除 B、 索引与修改 C、 访问与修改 D、 访问与索引 6下面说法不正确的是A、 广义表的表头总是一个广义表 B、 广义表的表尾总是一个广义表 C、 广义表难以用顺序存储结构 D、 广义表可以是一个多层次的结构7设有一表示算术表达式的二叉树（见下图），它所表示的算术表达式是A、 A*B+C/(D*E)+(F-G) B、 (A

5、*B+C)/(D*E)+(F-G) C、 (A*B+C)/(D*E+（F-G）) D、 A*B+C/D*E+F-G8深度为（根据的层次为）的二叉树至多有( )个结点。A、 64 B、 63 C、 31 D、 32 9下面不正确的说法是 (1) 在AOE网中减小任一关键活动上的权值后，整个工期也就相应减小 (2)AOE一网工程工期为关键活动上的权之和；(3)在关键活路径上的活动都是关键活动，而关键活动也必在关键路径上， A、(1) B、(2) C、(3) D、(1)、(2)10下列说法中不正确的是 A、无向图中的极大连通子图称为连通分量 B、连通图的广度优先搜索中一般要采用队列来暂存刚访问过的顶

6、点 C、图的深度优先搜索中一般要采用栈来暂存刚访问过的顶点 D、有向图的遍历不可采用广度优先搜索方法11设有一个按各元素的值排好序的线性表且长度大于2，对给定的值K，分别用顺序查找法和二分法查找一个与K相等的元素，比较次数分别s 和b；在查找不成功的情况下，正确的s 和b的数量关系是_ A、 总有s=b B、总有sb C、总有sb D、与K大小有关12设散列表的长m=14，散列函数为h(k)=k11，表中已有4个记录(如图所示)，如果采用二次探测再散列来处理冲突，则关键字为49的记录其存储地址是 A、 8 B、 3 C、 5 D、 913归并排序中，归并的趟数是A、O（n） B、O(logn)

7、 C、O(nlogn) D、O(n*n) 14下列排序算法中，在待排序数据已有序时，花费时间反而最多的是( )排序。 A、 冒泡 B、 希尔 C、 快速 D、 堆 15快速排序在最坏情况下时间复杂度是，比（ ）的性能差。 A、堆排序 B、起泡排序 C、选择排序16若对一个元素进行直接选择排序，则进行任一趟排序的过程中，为寻找最小值元素所需要的时间复杂性为 A、O(l) B、 C、 D、17数据表示是指数据。 A、 书写在纸上B、 从机外转为机内C、 磁盘中的数据D、 光盘中的数据 18以下数据结构中，哪一个是线性结构？ A、广义表 B、 二叉树 C、稀疏矩阵 D、 串19某二叉树的前序和后序序

8、列正好相反，则该二叉树一定是（）的二叉树。A、空或只有一个结点 B、高度等于其结点数 C、任一结点无左孩子 D、任一结点无右孩子20在10阶B-树中根结点所包含的关键码个数最多为（ ），最少为A、1 B、2 C、9 D、10三、填空题(14小题,共47分)1在一个不带头结点单链表中，在表头插入或删除与在其他位置插入或删除其操作过程_。2根据需要，用适当的语句填入下面算法的_中：问题：设有n件物品，重量分别为w1,w2,w3,wn和一个能装载总重量为T的背包。能否从n件物品中选择若干件恰好使它们的重量之和等于T。若能，则背包问题有解，否则无解。解此问题的算法如下： FUNCTION kanp_s

9、tack(VAR stack,w:ARRAY1.n OF real; VAR top:integer; T:real):boolean; w1：n 存放n件物品的重量，依次从中取出物品放入背包中，检查背包重量，若不超过T，则装入，否则弃之，取下一个物品试之。若有解则返回函数值true,否则返回false BEGIN top:=0; i:=1; i指示待选物品 WHILE (1)_ AND(2)_DO IF (3)_ OR (4)_ AND (i0) THEN i:=(7)_;取出栈顶物品 top:= (8)_ ；T:= (9)_ ; 恢复T值 i:=i+1 准备挑选下一件物品 ; ; RETU

10、RN(10)_) 背包无解 END;3设有三对角矩阵如下图所示，将带状区域中的元素（|i-j|=1)放在一维数组B中，则B的大小为_。元素在B 中的位置是_下标从0开始计)4二叉树结点的对称序序列为A,B,C,D,E,F,G,后序序列为B,D,C,A,F,G,E,则该二叉树结点的前序序列为 ,则该二叉树对应的树林包括 棵树。5对于前序遍历和中序遍历结果相同的二叉树为_,对于前序遍历和后序遍历结果相同的二叉树为_.A、一般二叉树 B、只有根结点的二叉树 C、根结点无左孩子的二叉树 D、根结点无右孩子的二叉树 E、所有结点只有左子树的二叉树 F、所有结点只有右子树的二叉树6设有N个结点的完全二叉树

11、顺序存放在向量A1:N中，其下标值最大的分支结点为_。7具有n个结点的满二叉树，其叶结点的个数是_。8n个顶点的连通图用邻接矩阵表示时，该矩阵至少有_个非零元崇。9对长度为n的查找表进行查找时假定查找笫i个元素的概率为Pi，查找长度(即在查找过程中依次同有关元素比较的总次数)为Ci，则在查找成功情况下的平均查找长度的计算公式为_。10对闭散列表来说，_的方法就是处理冲突的方法。11在一棵有n个结点的非平衡二叉树中进行查找，平均时间复杂度的上限(即最坏情况平均时间复杂度)为_。12在折半查找判定树中，成功查找终止于它的_结点，不成功查找终止于它的_结点。n个结点的用于折半查找的判定树，表示查找失败的外部结点共有_。13对于给定的n个元素,可以构造出的逻辑结构有_，_，_，_四种。14对于含有n个顶点和e条边的无向连通图，利用普里姆算法产生的最小生成树，其时间复杂度为 、利用克鲁斯卡尔算法产生的最小生成树，其时间复杂度为