忻州师院2006—2007学年第二学期《数据结构》期末考试试题A卷.doc

第页，共NUMPAGES3页
忻州师院计算机科学与技术系
2006—2007学年第二学期《数据结构》期末考试试题（A卷）
（考试班级：2005级专18、19、20班考试时间：110分钟）
一、单项选择题（在每小题的四个备选答案中，选出一个正确答案，并将正确答案的序号填在题干的括号内。每小题1分，共10分）
1.在数据结构中,与所使用的计算机无关的数据叫（C）结构。
A.存储B.物理C.逻辑D.物理和存储
2.在一个长度为n的顺序表中,向第i个元素(1≤i≤n+1)之前插入一个新元素时，需向后移动（B）个元素。
A.n-1B.n-i+1C.n-i-1D.i
3.线性表是（）。
A.一个有限序列,可以为空B.一个有限序列,不能为空
C.一个无限序列,可以为空D.一个无限序列,不能为空
4.对顺序存储的线性表，设其长度为n，在任何位置上插入或删除操作都是等概率的,删除一个元素时大约要移动表中的（）个元素。
A.n+1B.n-1C.(n-1)/2D.n
5.线性表采用链式存储时，其地址（D）。
A.必须是连续的B.部分地址必须是连续的
C.一定是不连续的D.连续与否均可以
6.设单链表中指针p指着结点(数据域为m)，指针f指着将要插入的新结点(数据域为x)，当x插在结点m之后时，只要先修改（）后修改p->link=f即可。
A.f->link=p;B.f->link=p->link;
C.p->link=f->link;D.f=nil;
7.顺序队列的人队操作应为()
A.sq.rear=sq.rear+1sq.data[sq.rear]=x
B.sq.data[sq.rear]=xsq.rear=sq.rear+1
C.sq.rear=(sq.rear+1)%maxsize;sq.data[sq.rear]=x
D.sq.data[sqrear]=xsq.rear=(sq.rear+1)%maxsize
8.任何一个带权的无向连通图的最小生成树（）
A.只有一棵
B.有一棵或多棵
C.一定有多棵
D.可能不存在
9.用顺序查找法对具有n个结点的线性表查找的时间复杂性量级为（）
A.O（n2）B.O（nlog2n）
C.O（n）D.O（log2n）
10.从一个具有n个节点的单链表中查找其值等于x结点时，在查找成功的情况下，需平均比较（）个结点。
A.nB.n/2C.(n-1)/2D.(n+1)/2

二、填空题(每空1分，共25分)
1.在线性结构中第一结点_______，其余每个结点有且只有_______；最后一个结点________，其余每个结点有且只有________。
2.对于顺序存储的线性表，当随机插入或删除一个元素时，约需平均移动表长___的元素。
3.在一棵树中，______结点没有后继结点。
4.根据数据元素之间关系的不同特性，通常有_________、_________、__________和__________四种基本结构。
5.在线性表的单链表存储结构中，每个结点包含域和域。
6.栈的插入与删除操作在进行。在队列中，新插入的节点只能添加到________________，被删除的只能排在______________。
7.一棵树上的任何结点（不包括根本身）称为根的________。若B是A的子孙，则称A是B的________
8.二叉树第i(i>=1)层上至少有______个结点。深度为k(k>=1)的二叉树至多有______个结点。
9.平衡二叉排序树上任一结点的平衡因子只可能是________、________或________。
10.若待排序的序列中存在多个记录具有相同的键值，经过排序，这些记录的相对次序仍然保持不变，则称这种排序方法是________的，否则称为________的。
11.在一个具有n个顶点的无向图中，要连通所有顶点则至少需要________条边。
三、判断题(每小题1分，共10分)
1. 数据元素是数据的最小单位。（）
2. 链式存储在插入和删除时需要保持物理存储空间的顺序分配，不需要保持数据元素之间的逻辑顺序。（）
3. 在用循环单链表表示的链式队列中，可以不设队头指针，仅在链尾设置队尾指针。（）
4. 存储图的邻接矩阵中，邻接矩阵的大小不但与图的顶点个数有关，而且与图的边数也有关。（）
5. 在顺序表中，逻辑上相邻的元素在物理位置上不一定相邻。（）
6.线性表若采用链式存储表示时，其存储结点的地址可连续也可不连续。（）
7.链式栈与顺序栈相比,一个明显的优点是通常不会出现栈满的情况。（）
8.若让元素1,2,3依次进栈，则出栈次序1,3,2是不可能出现的情况。（）
9.二叉树是一棵无序树。（）
10.对于AOE网络，加速任一关键活动就能使整个工程提前完成。（）
四、简答题