数据结构期末模拟真题 测试.docVIP

PAGE PAGE 4 全真模拟试题（一） 单项选择题（在每小题的4个备选答案中，选出正确的答案，并将其号码填在 题干的括号内。每小题2分，共24分） 若某线性表中最常用的操作是取第i 个元素和找第i个元素的前趋元素，则采用（ ）存储方式最节省时间。 ①单链表 ②双链表 ③单向循环 ④顺序表 串是任意有限个（ ） ①符号构成的序列 ②符号构成的集合 ③字符构成的序列 ④字符构成的集合 设矩阵A（aij ，l≤i,j≤ 10）的元素满足： aij≠0(i≥j, l≤i, j≤ 10) aij=0 (ij, l≤i, j≤ 10) 现将A的所有非0元素以行序为主序存放在首地址为2000的存储区域中，每个元素占有4个单元，则元素A[9][5]的首址为 ①2340 ②2336 ③2164 ④2160 如果以链表作为栈的存储结构，则退栈操作时（ ） 必须判别栈是否满 对栈不作任何判别 必须判别栈是否空 判别栈元素的类型 设数组Data[0..m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出队操作的语句为（ ） ①front=front+1 ②front=(front+1)% m ③rear=(rear+1)%m ④front=(front+1)%(m+1) 深度为6（根的层次为1）的二叉树至多有（ ）结点。 64 ②32 ③31 ④63 将含100个结点的完全二叉树从根这一层开始，每层上从左到右依次对结点编号，根结点的编号为1。编号为49的结点X的双亲编号为（ ） ①24 ②25 ③23 ④无法确定 设有一个无向图G=（V，E）和G’=（V’，E’）如果G’为G的生成树，则下面不正确的说法是（ ） ①G’为G 的子图 ②G’为G 的边通分量 ③G’为G的极小连通子图且V’=V ④G’为G的一个无环子图 用线性探测法查找闭散列表，可能要探测多个散列地址，这些位置上的键值（ ） 一定都是同义词 ②一定都不是同义词 ③都相同 ④不一定都是同义词 二分查找要求被查找的表是（ ） 键值有序的链接表 ②链接表但键值不一定有序 ③ 键值有序的顺序表 ④顺序表但键值不一定有序 当初始序列已经按键值有序，用直接插入算法对其进行排序，需要循环的次数为（ ） ①n2 ②nlog2n ③log2n ④n-1 堆是一个键值序列{k1,k2,…, kn},对i=1,2,…,|_n/2_|,满足( ) ①ki≤k2i≤k2i+1 ②kik2i+1k2i ③ki≤k2i且ki≤k2i+1(2i+1≤n) ④ki≤k2i 或ki≤k2i+1(2i+1≤n) 判断题（判断下列各题是否正确，正确在括号内打“V”，错的找“X”。每小题1分，共10分） 双链表中至多只有一个结点的后继指针为空。（ ） 在循环队列中，front指向队列中第一个元素的前一位置，rear指向实际的队尾元素，队列为满的条件是front=rear。（ ） 对链表进行插入和删除操作时，不必移动结点。（ ） 栈可以作为实现程序设计语言过程调用时的一种数据结构。（ ） 在一个有向图的拓朴序列中，若顶点a在顶点b之前，则图中必有一条弧a,b。( )i 对有向图G，如果从任一顶点出发进行一次深度优先或广度优先有哪些信誉好的足球投注网站就能访问每个顶点，则该图一定是完全图。( ) “顺序查找法”是指在顺序表上进行查找的方法。（ ） 向二叉排序树插入一个新结点时，新结点一定成为二叉排序树的一个叶子结点。（） 键值序列{A，C，D，E，F，E，F}是一个堆。 二路归并时，被归并的两个子序列中的关键字个数一定要相等。（） 填空题（每空2 分，共24分） 设r指向单链表的最后一个结点，要在最后一个结点之后插入s所指的结点，需执行的三条语句是___________；r=s; r-next=null;。 在单链表中，指针p 所指结点为最后一个结点的条件是___________。 设一个链栈的栈顶指针是ls，栈中结点格式为info | link ,栈空的条件是__________.如果栈不为空，则退栈操作为p=ls；___________；free