发布时间 : 星期日 文章2013-2014第二学期数据结构期末试卷A卷更新完毕开始阅读
合肥学院20 13 至20 14 学年第 2 学期
数据结构与算法设计 课程考试（ A ）卷
系 级 专业 学号 姓名
题号 得分 阅卷 一 二 三 四 五 六 七 八 九 十 总 分 装 订 线
大题得分 一、选择题：（2分×15=30分）
1． 栈和队列的共同特点是( )。
A、只允许在端点处插入和删除元素 B、都是先进后出 C、都是先进先出 D、没有共同点
2． 以下数据结构中哪一个是非线性结构？( )
A、 队列 B、 栈 C、 线性表 D、 二叉树 3．下面程序的时间复杂为（ ）。
for（i=1，s=0； i<=n； i++） {t=1；for(j=1；j<=i；j++) t=t*j；s=s+t；} A、 O(n) B、 O(n2) C、 O(n3) D、 O(n4)
4．在一个单链表中，已知q结点是p结点的前趋结点，若在q和p之间插入s结点，则须执行（ ）。
A．s->next=p->next; p->next=s B．q->next=s; s->next=p C．p->next=s->next; s->next=p D．p->next=s; s->next=q
5. 设一组初始记录关键字序列为(45，80，55，40，42，85)，则以第一个记录关键字45为基准而得到一趟快速排序的结果是（ ）。
A、 40，42，45，55，80，83 B、 42，40，45，80，85，88 C、 42，40，45，55，80，85 D、 42，40，45，85，55，80 6．设一个有序的单链表中有n个结点，现要求插入一个新结点后使得单链表仍然保持有序，则该操作的时间复杂度为（ ）。
A、 O(log2n) B、 O(1) C、 O(n2) D、 O(n)
7. 设有6个结点的无向图，该图至少应有( )条边才能确保是一个连通图。
A、5 B、6 C、7 D、8
8．设连通图G中的边集E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，则从顶点a出发可以得到一种深度优先遍历的顶点序列为（ ）。 A、 abedfc B、 acfebd C、 aebdfc D、 aedfcb
9. 设散列表长m=14,散列函数H（K）=K％11，已知表中已有4个结点：r(15)=4; r(38)=5; r(61)=6；r(84)=7，其他地址为空，如用二次探测再散列处理冲突，关键字为49的结点地址是( )。
A、 8 B 、3 C、 5 D 、9
10. 设用邻接矩阵A表示有向图G的存储结构，则有向图G中顶点i的入度为（ ）。 A、 第i行非0元素的个数之和 B、 第i列非0元素的个数之和 C、 第i行0元素的个数之和 D、 第i列0元素的个数之和
11.设指针变量top指向当前链式栈的栈顶，则删除栈顶元素的操作序列为（ ）。
命题教师 胡春玲 共 5 页，第 1 页 A、 top=top+1 B、 top=top-1 C、 top->next=top; D、 top=top->next 12. 二叉树的第K层的结点数最多为( )。
A、2k-1 B、2K+1 C、2K-1 +1 D、 2k-1
13. 设有向无环图G中的有向边集合E={<1，2>，<2，3>，<3，4>，<1，4>}，则下列属于该有向图G的一种拓扑排序序列的是（ ）。 A、 1，2，3，4 B、 2，3，4，1 C、 1，4，2，3 D、1，2，4，3
14. 设有一组初始记录关键字序列为(34，76，45，18，26，54，92)，则由这组记录关键字生成的二叉排序树的深度为（ ）。 A、 4 B、 5 C、 6 D、 7
15.图的深度优先遍历类似于二叉树的( )。
A.先序遍历 B.中序遍历 C.后序遍历 D.层次遍历
大题得分 二、填空题：（2分×10=20分）
1．设顺序线性表中有n个数据元素，则在第i个位置上插入一个数据元素需要移动表中 数据元素个数是 。
2．设指针变量p指向单链表中结点A，指针变量s指向被插入的新结点X，则在p后进行插入操作的语句序列为（ ; ）（设结点的指针域为next）。 3. 设有一组初始关键字序列为(24，35，12，27，18，26)，则第3趟直接插入排序结束后的结果的是 。
4．设某无向图G中有n个顶点，用邻接矩阵A作为该图的存储结构，则顶点i和顶点j互为邻接点的条件是 。
5. 设二叉排序树的高度为h，则在该树中查找关键字key最多需要比较 次。 6. 设一组初始记录关键字序列(k1，k2，……，kn)是小根堆，则对i=1，2，…，n/2而言满足的条件为 。
7. 下面程序段的功能是实现二分查找算法，请在下划线处填上正确的语句。 struct record{int key; int others;}; int bisearch(struct record r[ ], int k) {
int low=0,mid,high=n-1; while(low<=high) {
; if(r[mid].key==k) return(mid+1);
else if( ) high=mid-1;
else low=mid+1;}
return(0);}
8．若要对某二叉排序树进行遍历，保证输出所有结点的值序列有序排列，应对该二叉排序树采用________遍历法。
大题得分 三、应用题：（5分×5=25分）
1． 设一棵树T中边的集合为{(A，B)，(A，C)，(A，D)，(B，E)，(C，F)，(C，G)}，要求用孩子兄弟表示法（二叉链表）表示出该树的存储结构并将该树转化成对应的二叉树。
小题得分 共 5 页，第 2 页
2．请画出下图的邻接矩阵和邻接表。
小题得分 装 订 线 3． 设有一组初始记录关键字为(45，80，48，40，22，78)，要求构造一棵二叉排序树并给 出构造过程。
小题得分
4． 设有无向图G，要求给出用普里姆算法构造最小生成树和所走过的边的集合。 小题得分
共 5 页，第 3 页
5、 假设一棵二叉树的先序序列是ABCDEFGHIJ和中序序列是CDBFEAIHGJ,请画出该树。 小题得分
大题得分 四、算法阅读题：（12分）
1、LinkList mynote(LinkList L) （7分） 小题得分 {//L是不带头结点的单链表的头指针 if(L&&L->next){
q=L；L=L－>next；p=L； S1： while(p－>next) p=p－>next； S2： p－>next=q；q－>next=NULL； }
return L； }
请回答下列问题：
（1）说明语句S1的功能。 （2）说明语句组S2的功能。
（3）设链表表示的线性表为（a1,a2, …,an）,写出算法执行后的返回值所表示的线性表。
2．void ABC(BTNode * BT) （5分） 小题得分 {
if BT {
ABC (BT->left); ABC (BT->right); visit(BT); } }
该算法的功能是：
大题得分 五、算法设计题：（13分）
小题得分 1． 设计两个有序单链表的合并排序算法。（7分）
共 5 页，第 4 页