学海网

滁州学院2012-2013学年度第一学期地理信息系统、测绘工程、地理科学专业（本）11级《数据结构与算法》期末考试试卷及答案A卷
选择题（每题1.5分，共30分）
1、下面哪一个不是线性表的特性（ D ）
A.除第一个元素外，每个元素都有前驱 B.除最后一个元素外，每个元素都有后继
C.线性表是数据的有限序列 D.线性表的长度为n，并且n不等于0
2、在一个单链表中，已知q结点是p结点的前驱结点，若在q和p之间插入s结点，则执行（ C ）
A.s->next=p->next; p->next=s; B.p->next=s->next; s->next=p;
C.q->next=s; s->next=p; D. p->next=s; s->next=q;
3、若线性表采用链式存储，则表中各元素的存储地址（D ）
A.必须是连续的 B.部分地址是连续的
C.一定是不连续的 D.不一定是连续的
4、串是（ D ）
A.一些符号构成的序列 B.一些字母构成的序列
C.一个以上字符构成的序列 D.任意有限个字符构成的序列
5、设输入的序列为1、2、3、4，则借助于一个栈可以得到的输出序列是（ A ）
A.1342 B.3142 C.4312 D.4123
6、栈和队列都是（ C ）
A.顺序存储的线性表 B.链式存储的线性表
C.限制插入和删除位置的线性表 D.限制插入和删除的非线性表
7、将8阶对称矩阵A的下三角部分逐行存储到起始地址为1000的内存单元中，已知每个元素占4个字节，下标下界都为0，则A[7][4]的地址为（ D ）
A.35 B.36 C.3400 D.1128
8、有100个结点的完全二叉树，由根开始从上到下，从左到右对结点进行编号，根节点为1，则编号43的结点的左孩子的编号是（ D ）
A.50 B.48 C.98 D.86
9、对一颗n个结点的树，则该树中结点的度之和为（ B ）
A.n B.n-1 C.n+1 D.不确定
10、霍夫曼树中度为1的结点个数为（ A ）
A.0 B. 1 C.2 D.不确定
11、具有n个顶点的无向完全图，边的总数为（ D ）
A.n B.n-1 C.n+1 D.n（n-1）/2
12、有n个顶点的连通图的最小生成树有（ A ）条边
A.n-1 B.n C.n+1 D.不确定
13、以邻接表作为图的存储结构，其深度优先遍历和广度优先遍历的时间复杂度都为（ D ）
A.O(e) B.O(n) C.O(n-e) D.O(n+e)
14、下列排序算法中，第一趟排序结束后，其最大或最小元素一定在其最终位置上的算法是（ D ）
A.归并排序 B. 直接插入排序 C.快速排序 D.起泡排序
15、快速排序的平均时间复杂度为（ C ）
A.O(log2n) B.O(n) C.O(nlog2n) D.O(n2)
。。。。。