《数据结构期末复习试卷a》由会员分享，可在线阅读，更多相关《数据结构期末复习试卷a（8页珍藏版）》请在金锄头文库上搜索。
1、第 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 的二叉树，结点最多有 个，最少有
2、个。5在串 S=“factory”中，以 t 为首字符的子串有 个。6线性结构包括_ 、_、_、数组、串。7. 有循环队列 q，头指针为 fornt，尾指针为 rear，队列长度为 MAXSIZE，则循环队列的队空条件为：_ _；循环队列的队满条件为：_。得分评卷人装 订 线班级： 学号： 姓名： 第 4 页 共 8 页8串的存储方式主要分为二种：_ _存储结构和_存储结构。9对于一棵完全二叉树按层次从左到右编号之后，结点 i 的左孩子编号为_，右孩子编号为_，其父结点的编号为_。10遍历二叉树通常有三种顺序，分别为_ _，_ _ _和_ _。三程序填空题三程序填空题(2*10=20*10=2
3、0 分分)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
4、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写出下面二叉树的先序、中序和后序遍历结果。得分评卷人装 订 线班级： 学
5、号： 姓名： 第 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) 得
6、分评卷人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、循环队列的元素的插入与删除算法。
