数据结构试卷2(含答案)讲解.docVIP

数据结构期末试卷 出卷人：09数煤（1）班1~9号 判断题（5分） 1、线性表是一种随机存取结构-------------------------------------------------------------------（ ） 2、循环链表的特点是最后一个结点的指针域为NULL--------------------------------------（ ） 3. 下列不等式是否正确： O(n)O(nlog2n)O(n2)O(n3)O(nk)O(2n) ----------------------------------------------------（ ） 4. 数据元素之间的关系在计算机中有两种不同的表示方法：顺序映像和非顺序映像，分别对应两种不同的存储结构：链式存储结构和顺序存储结构---------------------------------（ ） 5. 抽象数据类型不可通过固有数据类型来表现和实现--------------------------------------（ ） 选择题（15分） 1、对顺序存储的线性表，设其长度为n，在任何位置上插入或删除操作都是等概率的。插入一个元素时平均要移动表中的（ ）个元素。 (A) n/2 (B) (n+1)/2 (C) (n -1)/2 (D) n 2、一个栈的入栈序列是1，2，3，4，5，则栈的不可能的输出序列是（ ） A 3，5，4，2，1 B 3，2，4，5，1 C 1，2，3，4，5 D 5，4，3，1，2 3、已知广义表LS＝((a,b,c),(d,e,f)),运用head和tail函数取出LS中原子e的运算是( )。 A. head(tail(LS)) B. tail(head(LS)) C. head(tail(head(tail(LS))) D. head(tail(tail(head(LS)))) 4、对稀疏矩阵进行压缩存储目的是（ ）。 A．便于进行矩阵运算 B．便于输入和输出 C．节省存储空间 D．降低运算的时间复杂度 5、假设以行序为主序存储二维数组A=array[1..100，1..100]，设每个数据元素占2个存储单元，基地址为10，则LOC[5，5]=（ ）。 A. 808 B. 818 C. 1010 D. 1020 6.在一个具有n个顶点的有向图中，若所有顶点的出度之和为s,则所有顶点的入度之和为（ ） A．s B.s-1 C.s+1 D.n 7.若要把n个顶点连接为一个连通图，则至少需要（ ）条边 A．n B.n+1 C.n-1 D.2n 8.已知一个有向图的边集为{a,b,a,c,.b,d,.b,e,d,e},则由该图产生的一种可能的拓扑序列为（ ） A．a,b,c,d,e B.a,b,d,e,b C.a,c,b,e,d D.a,c,d,b,e 9.若在线性表中采用二分查找法查找元素，该线性表应该（ ） A．元素按值有序 B.采用顺序存储结构 C．元素按值有序，且采用顺序存储结构 D．元素按值有序，且采用链式存储结构 10.二分查找法要求查找表中各元素的键值必须是（ ）排序 A．递增或递减 B．递增 C．递减 D．无序 11.采用顺序有哪些信誉好的足球投注网站方法查找长度为n的顺序表时，有哪些信誉好的足球投注网站成功的平均有哪些信誉好的足球投注网站长度为（ ） A．n B.n/2 C.（n-1）/2 D.(n+1)/2 12适用于动态查找表进行高效率查找的组织结构是（ ） A．有序表 B.分块有序表 C.三叉排序表 D,线性链表 13.设有序表中有1000个元素，则用二分查找查找元素X最多哦需要比较（ ）次 A．25 B.10 C.7 D.1 14、下列对于循环队列的说法，正确的是： ( ) A 循环队列就是队列的顺序存储方式 B 判断循环队列Q满的条件是：Q.rear=Q.front（即队头指针与队尾指针值相同） C 判断循环队列Q满的条件是：Q.rear=Q.front＝0 D 循环队列的存储不要求用一组地址连续的存储单元 15、在一个链栈中，已知s为栈顶指针（直接指向栈顶元素结点，无头结点），t为栈底指针，直接指向栈底元素，则插入r结点的操作为： ( ) A t-next=r; t=r; B r-next=s; s=r; C s