koorio.com
海量文库 文档专家
赞助商链接
当前位置:首页 >> 其它课程 >>

2015年春季数据结构期末试卷(A卷)


华南农业大学期末考试试卷(A 卷) 2014-2015 学年第 2 学期 考试科目:数据结构 考试类型: (闭卷)考试 考试时间: 120 分钟 学号姓名年级专业 题号 一 二 三 四 总分 得分 评阅人 考生须知: 1. 答案必须写在"答卷"上,写在试卷上不得分; 2. 考试结束时,只回收答卷,不回收试卷; 3. 必须在答卷上正确填写班级、学号、姓名等内容,否则没有考试成绩。 得分 一、选择题(本大题共 10 小题,每小题 2 分,共 20 分) 1、在存储数据时,通常不仅要存储各数据元素的值,而且还要存储() 。 A.数据的处理方法 B.数据元素的类型 C.数据元素间的关系 D.数据的存储方法 2、某链表最常用的操作是在最后一个节点之后插入节点或删除节点,则采用()存储方式 最节省运算时间。 A.单链表 B.给出表头指针的单循环链表 C.双链表 D.有头结点的双循环链表 3、一个栈的进栈序列是 a、b、c、d、e,则不可能的出栈序列是() 。 A.edcba B.decba C.dceab D.abcde 4、二维数组 M 的每一个元素占用 4 个字节的存储空间,行下标 i 的范围从 0 到 4,列下标 j 的范围从 0 到 5,M 按行优先存储时元素 M[3][5]的地址与 M 按列优先存储时元素()的 地址相同。 A.M[2][4] B. M[3][4] C.M[4][4] D.M[3][5] 5、 一个 n*n 的对称矩阵采用压缩存储, 以行优先的方式放入内存, 则占用的存储空间为( )。 A.n*n B.n*n/2 C. n*(n+1)/2 D.n*(n-1)/2 6、用希尔排序对一个数据序列进行排序时,若第 1 趟排序结果为 9,1,4,13,7,8,20,23,15,则 该趟排序采用的增量(间隔)可能是() 。 A. 2 B. 3 C. 4 D. 5。 7、设高度为 h 的二叉树只有度为 0 和度为 2 的结点,则此类二叉树结点数至少为() 。 A.2h B.2h-1 C.2h+1 D.h+1 8、下列程序段的时间复杂度是() 。 x=0; for(k=1;k<=n;k=k*2)

for(j=1;j<=n;j++) x++; A. O(log2n) B. O(nlog2n) C. O(n2) D. O(n) 9、在长度为 12 的有序表上应用折半查找法,在各元素查找概率相同的情况下平均查找长 度为() 。 A. 35/12 B. 37/12 C. 39/12 D. 41/12 10、一组记录的关键字为(41,79,56,38,40,84) ,使用快速排序法,以第一个记录为界点进 行第一次划分后得到的结果是 ( ) 。 A.40,38,41,56,79,84 B.40,38,41,79,56,84 C.38,40,41,56,79,84 D.40,38,41,84,56,79 得分 二、应用题(本大题共 5 小题,每小题 6 分,共 30 分,要求写出解题过程) 1、已知一棵二叉树的中序序列为 cbedahgijf,后序序列为 cedbhjigfa,画出这棵树,并写出 它的先序序列。 2、一份电文中使用了 8 种字符 a,b,c,d,e,f,g,h,每个字符出现的频率分别是 7,19,2,6,32,3,21,10,为这 8 个字符设计哈夫曼编码,并画出对应的哈夫曼树。 3、连通图有 5 个顶点 V1、V2、V3、V4、V5,其邻接矩阵如下,画出这一连通图并使用普 里姆算法求出它的最小生成树(要给出过程) 。 4、有一组关键字{19,1,23,14,55,2,84,27,68,11,10,78},采用 哈希函数:H(key)= key %13 ,采用线性探测再散列方法解决冲突,请在地址为 0~18 的 存储空间中构建哈希表,并计算平均查找长度。 5、判断以下两序列是否为最小化堆?如不是,将其调整为堆,并采用图的方式展示堆调整 的过程。 (1) (3,10,12,22,36,18,28,40) (2) (5,8,11,15,23,20,32,7) 6、依据整数序列(1, 12, 5, 8, 10, 7, 13, 9)的先后次序构造一棵平衡二叉树,画出每一次插 入及平衡化处理的过程。 得分 三、程序填空题(本大题共 5 小题,共 15 个空白处,每空 2 分,共 30 分,注意:每空只 填一个语句) 1、以递归的方法先序创建二叉树,结点的值为字符型,'#'字符表示空树 Status CreateBiTree(BiTree &T) { char ch; scanf("%c",&ch); if (ch=='#') T = NULL; else { if (!(T = (BiTNode *)malloc(sizeof(BiTNode)))) return ERROR; (1) (2) (3) } return OK; }

2、利用字符栈 s,从终端接收一行并送至调用过程的数据区,#为退格符,&为退行符 void LineEdit() { SqStack s; char ch,c; InitStack(&s); printf("请输入一个文本文件,^Z 结束输入:\n"); ch=getchar(); while(ch!=EOF) { while(ch!=EOF&&ch!='\n') { switch(ch) { case '#': (4) break; case '@':ClearStack(&s); break; default : } (6) } StackTraverse(s,copy); /* 将从栈底到栈顶的栈内字符传送至文件 */ ClearStack(&s); /* 重置 s 为空栈 */ fputc('\n',fp); if(ch!=EOF) ch=getchar(); } DestroyStack(&s);} 3、输入 n 个元素的值,按输入次序建立带头结点的单链表 void CreateList(LinkList *L,int n) { int i; LinkList p,q; *L=(LinkList)malloc(sizeof(struct LNode)); /* 生成头结点 */ (*L)->next=NULL; q=*L; printf("请输入%d 个数据\n",n); for(i=1;i<=n;i++) { (7) scanf("%d",&p->data); (8) q=q->next; } (5)

(9) } 4、对顺序表 L 作快速排序 void QSort(SqList *L,int low,int high) { /* 对顺序表 L 中的子序列 L.r[low..high]作快速排序。算法 10.7 */ int pivotloc; if( (10) ) { /* 长度大于 1 */ pivotloc=Partition(L,low,high); /* 将 L.r[low..high]一分为二 */ (11) /* 对低子表递归排序,pivotloc 是枢轴位置 */ (12) /* 对高子表递归排序 */ } } void QuickSort(SqList *L) { /* 对顺序表 L 作快速排序*/ QSort(L,1,(*L).length); } 5、对顺序表 L 作折半插入排序 void BInsertSort(SqList *L) { int i,j,m,low,high; for(i=2;i<=(*L).length;++i) { (*L).r[0]=(*L).r[i]; /* 将 L.r[i]暂存到 L.r[0] */ low=1; high=i-1; while( (13) ) { /* 在 r[low..high]中折半查找有序插入的位置 */ m=(low+high)/2; /* 折半 */ if LT((*L).r[0].key,(*L).r[m].key) /* 小于中点*/ (14) ; else (15) ; } for(j=i-1;j>=high+1;--j) (*L).r[j+1]=(*L).r[j]; /* 记录后移 */ (*L).r[high+1]=(*L).r[0]; /* 插入 */ } } 得分 四、算法设计题(本大题共 2 小题,每小题 10 分,共 20 分。请先简要说明算法思想,然 后写出算法的 C 语言源代码实现) 1、 将头指针为 a 的单链表 A 分解成两个单链表 A 和 B, 表 A 头指针为 a, 表 B 的头指针为 b, 表 A 含有原单链表 A 序号为奇数的元素,而表 B 含有原单链表 A 序号为偶数的元素,且均

保持原来的相对次序。 单链表存储结构定义如下: struct LNode { int data; struct LNode *next; }; typedef struct LNode *LinkList; 统一使用函数名:void Split(LinkList & A,LinkList & B) 2、一个具有 n 个结点的完全二叉树采用顺序存储方式,其数据存放在整型一维数组 a 中, 编写非递归算法对其进行先序遍历。 算法可以直接调用栈的基本操作: 初始化:InitStack(SqStack &S) 入栈:Push(SqStack &S,int e) 出栈:Pop(SqStack &S,int &e) 判断栈空: Empty(SqStack S) 统一使用函数名:void preorder(int a[], int n)

2 1


赞助商链接
推荐相关:

2014-2015学年二学期数据结构期末考试试卷(A卷)

石家庄学院 2014-2015 学年二学期数据结构期末考试试卷(A 卷) 班级:___学号:___姓名:___得分:___ 题号 得分 阅卷 题目部分,(卷面共有 23 题,100 分,...


安徽大学2014数据结构期末考试试卷(A卷)

安徽大学 2014-2015 学年第一学期《数据结构期末考试试卷(A 卷) (含参考答案)一、 单项选择题(本大题共 15 小题,第小题 2 分,共 30 分)在每小题...


《数据结构》期末考试试卷(A卷)

数据结构期末考试试卷(A卷) - 广州轻工职业学校(大源校区) 2015-2016 学年第二学期《数据结构期末考试试卷(A 卷) 注意事项 1、请首先按要求在试卷的标...


2014-2015B学年二学期数据结构期末考试试卷(A卷)

石家庄学院 2014-2015 学年二学期数据结构期末考试试卷(A 卷) 班级:___学号:___姓名:___得分:___ 题号 得分 阅卷 题目部分,(卷面共有 94 题,397 分,...


《数据结构与算法》期末试题试卷A

后进先出 2014 级计算机应用专业《数据结构与算法》试题 A 卷 2015 年 01 月 19 日注意: 本试卷共 4 页,满分 100 分,考试时间为 90 分钟,考试方式为闭...


《数据结构与算法》期末考试试卷(A卷)

数据结构与算法》期末考试试卷(A卷)_教育学_高等教育_教育专区。数据结构与算法 清远职业技术学院 2015-2016 学年度第二学期 《数据结构与算法(java 版)》期末...


2015年数据结构期末考试题及答案

2015年数据结构期末考试题及答案 - 2012 年数据结构期末考试题及答案 一、选择题 1.在数据结构中,从逻辑上可以把数据结构分为 A.动态结构和静态结构 C.线性...


长沙理工大学 2014-2015学年一学期数据结构期末考试试卷5

长沙理工大学计算机与通信工程学院 2014-2015 学年一学期数据结构期末考试试卷(A 卷) 班级:___学号:___姓名:___得分:___ 题号 得分 阅卷 题目部分,(卷面...


2015年数据结构期末考试题及答案

2015年数据结构期末考试题及答案 - 2012 年数据结构期末考试题及答案 一、选择题 1.在数据结构中,从逻辑上可以把数据结构分为 C 。 A.动态结构和静态结构 B....


数据结构A卷3答案

数据结构A卷3答案_教育学_高等教育_教育专区。兰州交通大学博文学院 2014-2015 学年第二学期 《数据结构期末考试试卷 (A 卷) 考核形式 (闭卷)题号 得分 ...

网站首页 | 网站地图
All rights reserved Powered by 酷我资料网 koorio.com
copyright ©right 2014-2019。
文档资料库内容来自网络,如有侵犯请联系客服。zhit325@126.com