合肥学院期末考试卷及答案

1、合肥学院 20 13至 20 14学年第 2学期数据结构与算法设计课程考试 （ A ）卷系级专业学号姓名题号一二三四五六七八九十总 分得分阅卷一、选择题：（ 2 分15=30 分）大题得分1 栈和队列的共同特点是 ( A)。A 、只允许在端点处插入和删除元素B、都是先进后出C、都是先进先出D、没有共同点2 以下数据结构中哪一个是非线性结构？( D )A 、 队列B、 栈C、 线性表D、 二叉树3下面程序的时间复杂为（ B）。for（i=1， s=0； i=n ； i+ ） t=1 ；for(j=1 ；jnext=p-next;p-next=sBq-next=s;s-next=p订C p-nex

2、t=s-next;s-next=pDp-next=s;s-next=q线 5. 设一组初始记录关键字序列为 (45，80，55，40，42，85)，则以第一个记录关键字 45 为基准而得到一趟快速排序的结果是（C ）。A 、 40，42，45，55， 80，83B、 42，40， 45，80，85， 88C、 42， 40，45，55， 80，85D、 42，40，45，85，55， 806设一个有序的单链表中有 n 个结点，现要求插入一个新结点后使得单链表仍然保持有序，则该操作的时间复杂度为（ D ）。A 、 O(log2 n)B、 O(1)C、 O(n2)D、 O(n)7. 设有 6 个结

3、点的无向图，该图至少应有 ( A )条边才能确保是一个连通图。A 、5B、 6C、7D、 88设连通图 G 中的边集 E=(a，b)， (a，e)，(a， c)， (b，e)， (e，d)，(d， f)，(f ，c) ，则从顶点 a 出发可以得到一种深度优先遍历的顶点序列为（A ）。A 、 abedfcB、 acfebdC、 aebdfcD、 aedfcb9. 设散列表长 m=14,散列函数 H（ K ）=K 11，已知表中已有4 个结点： r(15)=4; r(38)=5;r(61)=6；r(84)=7，其他地址为空，如用 二次探测 再散列处理冲突，关键字为49 的结点地址是( D )。A

4、、 8B 、3C、 5D 、 910. 设用邻接矩阵 A 表示有向图 G 的存储结构，则有向图G 中顶点 i 的入度为（B ）。A 、 第 i 行非 0 元素的个数之和B、 第 i 列非 0 元素的个数之和C、 第 i 行 0 元素的个数之和D、 第 i 列 0 元素的个数之和11.设指针变量 top 指向当前链式栈的栈顶，则删除栈顶元素的操作序列为（D ）。命题教师胡春玲共 5 页，第1 页A 、 top=top+1 B、 top=top-1C、 top-next=top; D、 top=top-next12. 二叉树的第 K 层的结点数最多为 ( D )。A 、2k-1B、2K +1C、

5、2K-1 +1D、 2k-113. 设有向无环图 G 中的有向边集合 E=， ， ，则下列属于该有向图 G 的一种拓扑排序序列的是（ A ）。A 、 1，2，3，4B、 2， 3， 4，1C、 1，4，2，3D、1，2，4，314. 设有一组初始记录关键字序列为 (34，76，45，18，26，54， 92)，则由这组记录关键字生成的二叉排序树的深度为（A ）。A 、 4 B、 5 C、 6 D、 715.图的深度优先遍历类似于二叉树的 ( A )。A. 先序遍历B.中序遍历C.后序遍历D.层次遍历二、填空题：（ 2 分 10=20 分）大题得分1设顺序线性表中有n 个数据元素，则在第i 个位

6、置上插入一个数据元素需要移动表中数据元素个数是n-i+1。2设指针变量 p 指向单链表中结点A ，指针变量 s 指向被插入的新结点X ，则在 p 后进行插入操作的语句序列为 （s-next=p-next;p-next=s）（设结点的指针域为next）。3. 设有一组初始关键字序列为 (24，35，12，27，18，26)，则第 3 趟直接插入排序结束后的结果的是12 24 27 35 18 26。4设某无向图G 中有 n 个顶点，用邻接矩阵A 作为该图的存储结构，则顶点i 和顶点 j互为邻接点的条件是Aij=1。5.设二叉排序树的高度为h，则在该树中查找关键字key 最多需要比较h次。6. 设

7、一组初始记录关键字序列 (k1，k2， kn)是小根堆，则对 i=1，2， n/2 而言满足的条件为ki k2i 且 ki k2i+1(2i+1 n)。7. 下面程序段的功能是实现二分查找算法，请在下划线处填上正确的语句。 struct recordint key; int others;int bisearch(struct record r , int k)int low=0,mid,high=n-1; while(low=high)mid=(low+high)/2;if(rmid.key=k) return(mid+1);else if( krmid.key ) high=mid-1;

8、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 设有

9、无向图 G，要求给出用普里姆算法构造最小生成树和所走过的边的集合。小题得分5、 假设一棵二叉树的先序序列是ABCDEFGHIJ 和中序序列是 CDBFEAIHGJ, 请画出该树。小题得分共 5 页，第3页四、算法阅读题：（12 分）大题得分1、LinkList mynote(LinkList L)（7 分）小题得分/L 是不带头结点的单链表的头指针if(L&L-next)q=L；L=L next；p=L ；S1：while(p next) p=pnext；S2：pnext=q；qnext=NULL ；returnL;请回答下列问题：（1）说明语句 S1 的功能。查询链表的尾结点（2）说明语句组 S2 的功能。将第一个结点连接到链表的尾部，作为新的尾结点（3）设链表表示的线性表为（ a1,a2, ,an） ,写出算法执行后的返回值所表示的线性表。返回的线性表为：（a2,a3, an,a1）2void ABC(BTNode * BT)（ 5 分）小题得分ifBT ABC (BT-left);ABC