搜索
一、单项选择题（每小题3分，共30分）在每小题列出的四个选项中只有一个选项是符合题目要求的，请将正确选项前的字母填在题后的括号内。1．算法指的是（d）A．计算机程序B．解决问题的计算方法C．排序算法D．解决问题的有限运算序列2.带头结点的单链表first为空的判定条件是：(b)A、first==NULLB、first一next＝＝NULLC、first一next==firstD、first!＝NULL3．将长度为n的单链表链接在长度为m的单链表之后的算法的时间复杂度为（c）A．O（1）B．O（n）C．O（m）D．O（m+n）4．由两个栈共享一个向量空间的好处是：（b）A．减少存取时间，降低下溢发生的机率B．节省存储空间，降低上溢发生的机率C．减少存取时间，降低上溢发生的机率D．节省存储空间，降低下溢发生的机率5、当利用大小为n的数组顺序存储一个队列时，该队列的最大长度为(b)。A、n一2B、n—lC、nD、n+16．6．线性表采用链式存储时，结点的存储地址（b）A．必须是不连续的B．连续与否均可C．必须是连续的D．和头结点的存储地址相连续7．若目标串的长度为n，模式串的长度为[n/3]，则执行模式匹配算法时，在最坏情况下的时间复杂度是（c）A．O（）B．O（n）C．O（n2）D．O（n3）8．一个非空广义表的表头（d）A．不可能是子表B．只能是子表C．只能是原子D．可以是子表或原子9.在计算机中存储器内表示时，物理地址和逻辑地址相同并且是连续的，称之为（b）。A．逻辑结构B．顺序存储结构C．链式存储结构D.以上都对10．在一棵度为3的树中,度为3的结点个数为2,度为2的结点个数为1,则度为0的结点个数为(c)A．4B．5C．6D．711．适于对动态查找表进行高效率查找的组织结构是（c）A．有序表B．分块有序表C．三叉排序树D．线性链表12、在一棵树中，(c)没有前驱结点。A、分支结点b、叶结点C、树根结点D、空结点填空题：（每题3分，共30分）1．线性表是由n个类型相同的数据元素组成的有限序列。2．在一个带头结点的单循环链表中，p指向尾结点的直接前驱，则指向头结点的指针head可用p表示为head=p－next－next。3．栈顶的位置是随着进栈和退栈操作而变化的。4．数据的逻辑结构是从逻辑关系上描述数据，它与数据的存储结构无关，是独立于计算机的。5．队列是一种只允许在一端进行插入，而在另一端进行删除的线性表。6．在单链表上难以实现的排序方法有快速排序、堆排序、希尔排序。7．在有序表（12，24，36，48，60，72，84）中二分查找关键字72时所需进行的关键字比较次数为2。8．多重表文件和倒排文件都归属于多关键字文件。9．串是由零个或多个字符组成的有限序列。10．二叉树是一种度≤2的有序树，它的特点是每个结点至多只有两棵子树，并且其子树有左右之分，其次序不能任意颠倒。判断题。每题3分，共15分。（对）（1）数组是一种复杂的数据结构，数组元素之间的关系既不是线性的也不是树形的。（对）（2）直接选择排序是一种不稳定的排序方法。（错）（3）链式存储在插人和删除时需要保持物理存储空间的顺序分配，不需要保持数据元素之间的逻辑顺序。（对）（4）当3阶B树中有255个关键码时，其最大高度（包括失败结点层）不超过8。（错）（5）一棵3阶B树是平衡的3路搜索树，反之，一棵平衡的3路搜索树是3阶B树。（对）（6）在用循环单链表表示的链式队列中，可以不设队头指针，仅在链尾设置队尾指针。（错）（7）在只有度为0和度为k的结点的k叉树中，设度为0的结点有n0个，度为k的结点有nk个，则有n0=nk+1。（错）（8）折半搜索只适用与有序表，包括有序的顺序表和有序的链表。四、算法题（共两题，第一题15分，第二题10分）顺序表的插入算法intInsert(ElemtypeList[],int*num,inti,Elemtypex)intj;if(i0||i*num+1){printf(“Error!”);returnFALSE;}if(*num=MAXNUM-1){printf(“overflow!”);returnFALSE;for(j=*num;j=i;j--)List[j+1]=List[j];List[i]=x;(*num)++;returnTRUE;}第2小题画图题10分