南阳理工学院软件学院数据结构

《南阳理工学院软件学院数据结构》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、一、填空题：(每空1分，共10分)1.数据元素在计算机中有两种基本存储结构，分别是顺序存储结构和链式存储结构。2.已知广义表A=(a，b，(c，d))，则head(A)等于_a。3.假定一棵树的广义表表示为A(C,D(E,F,G)，H(I，J))，则树中所含的结点数为_9个，树的深度为_3’树的度为_3o4.在对一组记录(54，38,96，23,15，72，60,45,83)进行直接插入排序时，当把第7个记录60插入到有序表时，为寻找插入位置需比较次。5.冒泡排序在最好的情况下的元素交换次数为次。6.6个顶点的连通图至少有条边。7.设哈夫曼树中共有n个结点，则该哈夫曼树中共有个度数为1的结点

2、。二、单选题：(每题2分，共30分)1.栈和队列的共同特点是A。B.都是先进后出D.没有共同点A.只允许在端点处插入和删除元素C.都是先进先出2.二叉排序树中左子树上所有结点的值均根结点的值。A.小于B.大于C.等于D.不确定3.数据的最小单位是_A。A.数据项B.数据类型C.数据元素D.数据变量4.采用顺序查找方法查找长度为n的线性表时，每个元素的平均査找长度是A.nB.n/2C.(n+l)/2D.(n-1)/25.执行一趟快速排序能够得到的序列是。A.[63,12，34,45,27]55[41,72]B.[45,34，12,41]55[72,63,27]C.[41,12,34,45,27

3、]55[72,63]D.[12,27,45,41]55[34,63,72]6.使用二叉线索树的目的是便于D。A.二叉树中结点的插入与删除B.在二叉树中查找双亲C.确定二叉树的高度D.查找一个结点的前趋和后继7.设某无向图有n个顶点，则该无向图的邻接表中有个表头结点。A.2nB.n(n-l)C.n/2D.n8.设指针变量top指向当前链式栈的栈项，则删除栈项元素的操作为__D_。A.top=top+l;B.top=top+l;C.top->next=top;D.top=top->next;1.K列说法正确的是BA.二叉树中任何一个结点的度都为2B.二叉树中结点的度可以小于2C.任何二叉树中至少

4、有一个结点的度为2D.二叉树的度为22.具有10个叶结点的二叉树中有个度为2的结点，A.8B.9C.10D.113.某栈的输入序列为a，b，c,d，下面的四个序列中，不可能是它的输出序列的是_D。A.a,c,b，dB.b，c,d,aC.c，d,b,aD.d，c,a,b4.在一棵树中，若结点A有3个兄弟，结点B是结点A的双亲结点，那么结点B的度为C_0A.3B.lC.4D.55.可进行拓扑排序的图只能是。A.无向连通图B.有向有环图C.有向图D.无向图6.字符串的长度是指C。A.串中不同字符的个数B.串中不同字母的个数C.串中所含字符的个数D.串中不同数字的个数7.假设以数组A[m]存放循环队

5、列的元素，其头尾指针分别为front和rear,则当前队列中的元素个数为。A.（front-rear+m）%mB.rear-front+1C.（rear-front+m）%mD.（rear-front）%m三、判断题：（每题1分，共10分）1.满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。（正确）2.线性表的顺序存储结构比链式存储结构更好。（错误）3.由树转化成二叉树，该二叉树的右子树不一定为空。（错误）4.空串是由空格构成的串。（错误）5.对连通图进行深度优先遍历nJ以访问到该图中的所有顶点。（）6.顺序表杏找指的是在顺序存储结构上进行查找。（）7.子串’’ABC”在主串’’AAB

6、CABCD”中的位置为2。（）8.当向二叉排序树中插入一个结点，则该结点一定成为叶子结点。（正确）9.如果某个有向图的领接表中第i条单链表为空，则第i个顶点的出度为零。（）10.非空的双向循环链表中任何结点的前驱指针均不为空。（）四、应用题：(每题6分，共30分)1.下面程序段的功能是实现折半插入排序，请在下划线处填上正确的语句。voidBlnsertSort(SqList&L){for(i=2;i<=L.length;++i){L.r[0]=L.r[i];Low=l;high=i-1;while(low<=high)if(L.r[0].key

7、e;)for(j=i-l;j>=high+l;-j)L.r[j+l]=L.r[j];L.r[high+l]=L.r[O];})2.己知二叉树的前序和中序序列，构造出相应的二叉树前序：ABDEC中序：DBEAC3.某无向图的顶点表为(1,2,3,4),下图为其邻接矩阵表，请画出该无14图。'0110_1011110001004.在如下数组A屮链接存储了一个线性表，A[01为头结点，试写出该线性表。A012345