资源预览内容
第1页 / 共8页
第2页 / 共8页
第3页 / 共8页
第4页 / 共8页
第5页 / 共8页
第6页 / 共8页
第7页 / 共8页
第8页 / 共8页
亲,该文档总共8页全部预览完了,如果喜欢就下载吧!
资源描述
第 1 页 共 8 页数据结构 复 习 卷 A题号一二三四五总分得分一一 选择题选择题(1*15=151*15=15 分分)1数据结构是 ( D )A一种数据类型B数据的存储结构C一组性质相同的数据元素的集合D相互之间存在一种或多种特定关系的数据元素的集合2计算机算法必须具备输入、输出和 5 个特性。 ( B )A. 可行性、可移植性和可扩充性 B. 可行性、确定性和有穷性C. 确定性、有穷性和稳定性 D. 易读性、稳定性和安全性3下面程序段的时间复杂度为. ( B )y=0;for(i=1;irear _。3栈顶的位置是随着_ _操作而变化的。4深度为 K 的二叉树,结点最多有 个,最少有 个。5在串 S=“factory”中,以 t 为首字符的子串有 个。6线性结构包括_ 、_、_、数组、串。7. 有循环队列 q,头指针为 fornt,尾指针为 rear,队列长度为 MAXSIZE,则循环队列的队空条件为:_ _;循环队列的队满条件为:_。得分评卷人装 订 线班级: 学号: 姓名: 第 4 页 共 8 页8串的存储方式主要分为二种:_ _存储结构和_存储结构。9对于一棵完全二叉树按层次从左到右编号之后,结点 i 的左孩子编号为_,右孩子编号为_,其父结点的编号为_。10遍历二叉树通常有三种顺序,分别为_ _,_ _ _和_ _。三程序填空题三程序填空题(2*10=20*10=20 分分)1以下函数功能是:顺序表中在指定位置上插入一个元素,请填空。int insert(SEQUENLIST * a, DATATYPE1 x, int i) int k;if(ia-last+1 |a-last=_ _)return 0; else for(k=a-last;k=i;k- -) a-datask=_; a-datasi-1=_; a-last=_;return 1;2.有双向链表 struct dlinklistchar data;struct dlinklist *prior,*next;已知结点 p,删除 p 结点本身void deleltedlink(struct dlinklist *p)p-prior-next= ;=p-prior;得分评卷人第 5 页 共 8 页3. 有顺序栈 typedef struct char datamaxsize;int top;SEQSTACK;SEQSTACK * s;将以下进栈函数补充完整:int push (SEQSTACK *s, char x) if ( )printf(“overflown”);return o;else s-data =x ;s-top ;return 1;四综合应用题四综合应用题(5*5=255*5=25 分分)12写出下面二叉树的先序、中序和后序遍历结果。得分评卷人装 订 线班级: 学号: 姓名: 第 6 页 共 8 页2有叶子结点、,权值分别为2、1、4、3、5、7,ABCDEF画出构造后的哈夫曼树。3已知一棵二叉树的先序结果为:ABDECFHIGJ,中序为:DBEAHFICJG,请画出这棵二叉树。第 7 页 共 8 页4. 画出下面树的孩子表示法。5将下面二叉树转换位森林。五程序实践题五程序实践题(10*2=2010*2=20 分分)1 写一函数求带头结点单链表 head 中所有元素之和。函数定义如下:typedef struct node int data; struct node *next; LINKLIST; int sum (LINKLIST *head) 得分评卷人ABCDEFGHLIJKCBAIHFDKJGE班级: 学号: 姓名: 第 8 页 共 8 页 2 采用中序递归遍历算法,编制一个求二叉树结点元素的平均值的函数。typedef struct node1 int data; struct node1 *lchild,*rchild; BTCHINALR; int average (BTCHINALR *bt)3、初始化栈、栈顶元素的插入与删除算法4、头、尾插入建立单链表算法5、建立二叉树、统计二树结点个数、二叉树三种遍历算法6、顺序表中插入与删除元素算法7、单链表中的插入与删除算法8、取队头元素、队列元素的插入与删除算法9、双向链表中的插入与删除算法10、循环队列的元素的插入与删除算法。
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号