数据结构(C语言)试卷(1).doc

成都东软信息技术学院200 200 学年第 学期期末试题数据结构(C语言) 题号一二三四五六总分分数本课程为闭卷考试，试卷共六道大题，试卷满分100分，考试时间120分钟。一选择题（102分）：共10小题，请将答案填入题中的括号中，每小题只有一个正确答案，错选或不选均不给分。1组成数据的基本单位是（ ）数据项 数据类型C数据元素 D数据变量2线性表的链式存储实现有利于（ ）运算。 A插入 B读表元 C查找 D定位3二叉树第i(i1)层最多有（ ）个结点。 A2i B2i C2i-1 D2i -14设单链表中指针p指向结点A，若删除A后的结点存在，则需要修改指针的操作为（ ）。Ap-next=p-next-next Bp=p-nextCp=p-next-next Dp-next=p5设一数列的输入顺序为1,2,3,4,5,6，通过栈操作不可能排成的输出序列为（ ）。A3,2,5,6,4,1 B1,5,4,6,2,3C2,4,3,5,1,6 D4,5,3,6,2,16如果结点A有3个兄弟，而且B为A的双亲，则B是度为（ ）3 4C5 D17设循环队列Q0.N-1的头尾指针为F.R，当插入元素时尾指针R加1，头指针F总是指向队列中第一个元素的前一个位置，则队列中元素计数为（ ）。 AR-F BN-(R-F) C(R-F+N)%N D(F-R+N)%N8若给定的关键字集合为20,15,14,18,21,36,40,10，一趟快速排序结束后，键值的排序为（ ）。 A10,15,14,18,20,36,40,21 B10,15,14,18,20,40,36,21 C10,15,14,20,18,40,36,21 D15,10,14,18,20,36,40,219设有100个元素，用二分法查找时，最大比较次数是（ ），最小比较次数是（ ）。A25 B7C10 D110具有2000个结点的二叉树，其高度至少为（ ）。A9 B10C11 D12二填空题（20分）：每空2分，前序序列和中序序列相同的二叉树为 。2具有64个结点的完全二叉树的深度为 。3数据结构讲述的三大关系是 、 、 。4已知二叉树中的叶子树为50，仅有一个孩子的结点数为30，则总结点数为 。5简单选择排序在最好情况下所做的交换元素次数为 。6队列的原则是 。7快速排序算法在最差的情况下其时间复杂度是 。8顺序存储的队列如果不采用循环方式，则会出现 问题。三简答题（45分）1 试比较顺序存储和链式存储的优缺点。（5分）2 简述栈和队列这两种数据结构的相同点和不同点。（5分）3 已知一棵二叉树的中序序列和后序序列分别是BDCEAFHG和DECBHGFA，试画出这棵二叉树。（5分）4 采用简单选择排序对线性表（26,15,12,16,5,30）进行排序，进行交换的第一对元素是哪两个元素？在什么情况下，第一趟不需要进行元素的交换？（5分）四判断题（52分）如果某数据结构的每一个元素都最多只有一个直接前驱和一个直接后继，则该数据结构必为线性表。( )2若有一个叶子结点是某子树的中序遍历的最后一个结点，则它必是该子树的先序遍历的最后一个结点。( )3进栈操作时，必须判断栈是否已满。( )4如果某排序算法是稳定的，那么该方法一定具有实际应用价值。( )5折半查找法的前提之一是线性表有序。( ) 五程序填空题（35分）1以下是采用冒泡排序法对数组a进行排序，完成程序。（4分） bsort(int a, int n) int n, int i,int j, int temp; for (i= ;j=i;-j) if( ) temp=aj;aj=aj+1;aj+1=temp;2在单链表（表头指针为head）的元素中找出最后一个值为e的元素，返回其指针；如果找不到，返回NULL。完成以下程序。(6分) typedef srruct LinkNode int data; struct LinkNode *next; Node;Node *search_link(Node *head, int e) Node *p, *q; q= ; for(p=head; ;p=p-next) if(p-data = = e) ;return q;3下列算法是输出一棵二叉树的第i层的所有结点的值。假定根结点是第1层，完成以下程序。（5分） typedef srruct LinkNode int data; struct LinkNode *lchild, *rchild; Node; void outi(Node *tree, int i) if (tree = NULL) return; if(i=1) printf(“%dn”,tree-data);return;outi( );outi( );六算法设计题（15分）1编写算法，删除顺序表第i个元素。（8分）已知顺序表的数据结构如下： typedef struct int data100; int last; SeqList;2编写算法，求不带头结点的单链表的表表长。（7分）已知单链表结点数据结构如下：typedef struct node int data; struct node *next; LNode, *LinkList;答案及评分标准：数据结构(C语言)答案及评分标准一选择题（102分）：每小题只有一个正确答案，错选或不选均不给分。12345678910CACABBCABC二填空题（20分）：每空2分。1没有左子树的二叉树; 27; 3一对一的线性关系 一对多的树关系 多对多的图关系; 4129; 50; 6先进先出； 7O(n2)； 8假溢出。三简答题（45分）1顺序存储查找效率高，插入和删除效率低；链式存储插入和删除效率高，查找效率低。2栈和队列都是操作受限的线性表。栈是先进后出，操作在一端进行；队列是先进先出，插入在一端，删除在另一端进行。3HBFCADEA4交换的第一对元素是26和15，第一个元素比其他元素都小时不需要进行元素的交换。四判断题（52分）1；2；3；4；5五程序填空题（35分）10;aj+1lchild,i-1;tree-rchild,i-1六算法设计题（15分）1int delete_SeqList(SeqList *L,int i) int j; if (i L-last+1) printf(“不存在第i个元素”); return 0;for (j=i; jL-last;