资源描述:
《数据结构试卷(一)》由会员上传分享,免费在线阅读,更多相关内容在工程资料-天天文库。
1、数据结构试卷(一)参考答案一、选择题(每题2分,共20分)l.A2.D3.D4.C5.C6.D7.D8.C9.D10.A二、填空题(每空1分,共26分)1.正确性易读性强壮性高效率2.O(n)3.9334.-134X*+2Y*3/-5.2nn-1n+16.e2e7.有向无回路8.n(n-l)/2n(n-l)9.(12,40)()(74)(23,55,63)10.増加1ll.O(log2n)O(nlog2n)12.归并三、计算题(每题6分,共24分)1.线性表为:(78,50,40,60,34,90)?0?1?
2、?1??1?02.邻接矩阵:?1110?0101??1011??0101?1110??邻接表如阁11所示:阁113.用克魯斯卡尔算法得到的最小生成树为:(1,2)3,(4,6)4,(1,3)5,(1,4)8,(2,5)10,(4,7)204.见图1226四、诿算法(每题7分,共14分)1.(1)查询链表的尾结点(2)将第一个结点链接到链表的尾部,作力新的尾结点(3)返回的线性表为(a2,a3,?,an,al)2.递归地后序遍历链式存储的二叉树。五、法填空(每空2分,共8分)trueBST->leftBST->
3、right六、编写算法(8分)intCountX(LNode*HL'ElemTypex){inti=0;LNode*p=HL;//i为计数器while(p!=NULL){if(P->data==x)i++;p=p->next;}//while,出循环时i中的值即为x结点个数returni;}//CountX数据结构试卷(二)一、选择题(24分)1.下而关于线性表的叙述错误的是()。(A)线性表采用顺序存储必须占用一片连续的存储空间(B)线性表采用链式存储不必占用一片连续的存储空间(C)线性表采用链式存储便于插
4、入和删除操作的实现(D)线性表采用顺序存储便于插入和删除操作的实现2.设哈夫曼树屮的叶子结点总数为m,若用二叉链表作为存储结构,则该哈夫曼树屮总共有()个空指针域。(A)2m-l(B)2m(C)2m+l(D)4m3.设顺序循环队列Q[0:M-l]的头指针和尾指针分别为F和R,头指针F总是指向队头元素的前一位置,尾指针R总是指向队尾元素的当前位置,则该循环队列中的元素个数为()。(A)R-F(B)F-R(C)(R-F+M)%M(D)(F-R+M)%M4.设某棵二义树的屮序遍历序列为ABCD,前序遍历序列为CAB
5、D,则后序遍历该二义树得到序列为()。(A)BADC(B)BCDA(C)CDAB(D)CBDA5.设某完企无向图中有n个顶点,则该完企无向图中有()条边。22(A)n(n-l)/2(B)n(n-l)(C)n(D)n-16.设某棵二叉树中有2000个结点,则该二叉树的最小高度为()。(A)9(B)10(C)11(D)127.设某有向图屮有n个顶点,则该有向图对应的邻接表屮有()个表头结点。(A)n-1(B)n(C)n+1(D)2n-l8.设一组初始记录关键字序列(5,2,6,3,8),以第一个记录关键字5为基准
6、进行一趟快速排序的结果为()。(A)2,3,5,8,6(B)3,2,5,8,6(C)3,2,5,6,8(D)2,3,6,5,8二、填空题(24分)1.为了能有效地应用HASH査找技术,必须解决的两个问题是和2.下面程序段的功能实现数据x进栈,要求在下划线处填上正确的语句。typedefstruct{ints[100];inttop;}sqstack;voidpush(sqstack&stackjntx){if(stack.top==m-l)printf("overflow〃};else{;;}}3.中序遍历二
7、叉排序树所得到的序列是序列(填有序或无序)。4.快速排序的最坏时间复杂度为,平均时间复杂度为。5.设某棵二叉树中度数为0的结点数为N0,度数为1的结点数为N1,则该二叉树中度数为2的结点数为;若采川二叉链表作力该二叉树的存储结构,则该二叉树屮共有个空指针域。41.设某无向图中顶点数和边数分别为n和e,所有顶点的度数之和为d,则6=。2.设一组初始记录关键字序列为(55,63,44,38,75,80,31,56),则利用筛选法建立的初始堆为。3.己知一有向图的邻接表存储结构如下:从顶点1出发,DFS遍历的输出序
8、列是BFS遍历的输出序列是三、应用题(36分)1.设一组初始记录关键字序列为(45,80,48,40,22,78>,则分别给出第4趟简单选择排序和第4趟直接插入排序后的结果。2.设指针变量p指向双叫链表屮结点A,指针变量q指向被插入结点B,要求给出在结点A的后面插入结点B的操作序列(设双向链表中结点的两个指针域分别为llink和dink)。3.设一组有序的记录关键字序列为(13,18,24,35,4