《计算机与软件学院《数据结构》笔试题及答案》由会员分享，可在线阅读，更多相关《计算机与软件学院《数据结构》笔试题及答案（4页珍藏版）》请在金锄头文库上搜索。
1、閣的邻接麦存储结相计算机与软件学院考试试卷及参考答案课程名称：数据结构一、填空题（24分）1. 为了能有效地应用HASH查找技术，必须解决的两个问题是和2. 下面程序段的功能实现数据x进栈，要求在下划线处填上正确的语句。typedef struct int s100; int top; sqstack;void push（sqstack & stack,int x）if （stack.top=m-l） pri ntf（“ overflow”）；else ;3. 中序遍历二叉排序树所得到的序列是列（填有序或无序）。4. 快速排序的最坏时间复杂度为，平均时间复杂度为。5. 设某棵二叉树中度数为0的
2、结点数为N,度数为1的结点数为N,则该二叉树中度数为2的结点数为;若采用二叉链表作为该二叉树的存储结构，则该二叉树中共有个空指针域。6. 设某无向图中顶点数和边数分别为n和e，所有顶点的度数之和为小，则。=。7. 设一组初始记录关键字序列为（55, 63，44，38，75，80，31，56），则利用筛选法建立的初始堆为。8. 已知一有向图的邻接表存储结构如下：从顶点1出发，DFS遍历的输出序列是，BFS遍历的输出序列是二、应用题（36分）1. 设一组初始记录关键字序列为（45, 80, 48, 40，22，78），则分别给出第4趟简单选择排 序和第4趟直接插入排序后的结果。2. 设指针变量p指
3、向双向链表中结点A,指针变量q指向被插入结点B,要求给出在结点A的后面插入结点B的操作序列（设双向链表中结点的两个指针域分别为llink和rlink）。3. 设一组有序的记录关键字序列为(13, 18, 24, 35, 47, 50, 62, 83, 90)，查找方法用二 分查找，要求计算出查找关键字62时的比较次数并计算出查找成功时的平均查找长度。4.设一棵树 T 中边的集合为(A, B), (A, C), (A, D), (B, E), (C, F), (C, G)，要求用 孩子兄弟表示法(二叉链表)表示出该树的存储结构并将该树转化成对应的二叉树。5.设有无向图G,要求给出用普里姆算法构造
4、最小生成树所走过的边的集合。三、算法设计题(16分)1. 设有一组初始记录关键字序列(K,K,，K),要求设计一个算法能够在0(n)的时间复12n杂度内将线性表划分成两部分，其中左半部分的每个关键字均小于K,右半部分的每个关1 键字均大于等于K。i2. 设有两个集合A和集合B,要求设计生成集合C=AHB的算法，其中集合A、B和C用链式存储结构表示。参考答案一、填空题1. 构造一个好的 HASH 函数，确定解决冲突的方法2. stack.top+，stack.sstack.top=x3. 有序4.O(n2)，O(nlog n)5.N -1，2N +NCl016.0 0 1d/27.(31，38，
5、54，56，75，80，55，63)8.(1，3，4，5，2)，(1，3，2，4，5)二、应用题1.(22，40，45，48，80，78)，(40，45，48，80，22，78)2. q-llink=p; q-rlink=p-rlink; p-rlink-llink=q; p-rlink=q;3. 2,ASL=91*1+2*2+3*4+4*2)=25/94. 树的链式存储结构略，二叉树略5. E=(1，3)，(1，2)，(3，5)，(5，6)，(6，4)三、算法设计题1. 设有一组初始记录关键字序列(K,K,，K),要求设计一个算法能够在0(n)的时间复12n杂度内将线性表划分成两部分，其中左
6、半部分的每个关键字均小于K,右半部分的每个关1 键字均大于等于 Ki。ivoid quickpass(int r, int s, int t) int i=s, j=t, x=rs; while(ij) while (ix) j=j-1; if (ij) ri=rj;i=i+1; while (ij & rix) i=i+1; if (inext) for(q=hb;q!=0;q=q-next) if (q-data=p-data) break;if(q!=0) t=(lklist *)malloc(sizeof(lklist); t-data=p-data;t-next=hc; hc=t;
