数据结构试卷(一)

数据结构试卷(一)

ID:24351331

大小:559.78 KB

页数:33页

时间:2018-11-13

数据结构试卷(一)_第1页
数据结构试卷(一)_第2页
数据结构试卷(一)_第3页
数据结构试卷(一)_第4页
数据结构试卷(一)_第5页
资源描述:

《数据结构试卷(一)》由会员上传分享,免费在线阅读,更多相关内容在工程资料-天天文库

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

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。