资源描述：
《数据结构05有答案》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、山东06年专升本《数据结构》试卷一、填空题：(每空1分，共22分)1.数据结构按结点间的关系被分为四种逻辑结构,分别是—集合—、线性结构、一图—和树结构四种。2.若经常需要对线性表进行插入和删除操作，则最好采用链式—存储结构，若经常需要对线性表进行查找操作，则最好采用顺序存储结构。3.在一个单链表中删除指针p所指向结点的后继结点时，需要把—p->next->next的值赋给p->next指针域。4.在一个长度为n的顺序存储的线性表中,向第i个元素(lWiWn+1)位置插入一个新元素时，需要从后向前依次后移一n-i-1—个元素。5•对于一个长度为n的顺序存储的线性表
2、，在表头插入元素的时间复杂度为0(n)表尾插入元素的时I'可复杂度为0(1)o6.设元素1,2,3,4,5依次进入栈S,若要在输出端得到序列34251,则应进行的操作序列为push(S,1),push(S,2),push(s,3)—,pop(S),push(S,4),pop(S),pop(s),push(s,5),pop(S),pop(S)o7.已知广义表A=((a,b,c),(d,e,f)),则广义表运算head(tail(tail(A)))=.e8.一个NXN的对称矩阵，如果以行为主序或以列为主序存入内存，则其存储容量为n(n+l)/2—。9.在一棵树中，—根
3、—结点没有前驱结点，其余每个结点有并且只有一个—前驱_,可以有任意多个—后继—结点。10.在分块查找方法中，首先查找索引，然后再查找相应的块。11.在一,个具有n个顶点的无向图屮，要连通所有顶点则至少需要n-l]条边。12.在对n个元素进行直接插入排序的过程中，共需要进行—趟。13.顺序查找法的平均查找长度为—(n+l)/2_；分块查找法(以顺序查找确定块)的平均查找长度是_(s，+2s+n)/2S。二、选择题(每题2分，共30分)1.在一个带头结点的双向循环链表中，若要在P所指向的结点之前插入一个新的结点，则需要相继修改()个指针域的值。A.2B.3C.4D.6
4、2.不带头结点的单链表L为空的判定条件是()A.L二二NULLB.L->next==NULLC.L->next==LD.L!=NULL3.循环队列用数组A[m](下标从0到m-1)存放其元素值，已知其头尾指针分别是front和rear,则当前队列中的元素个数是()A.(rear—front4-m)%mB.rear—front+1C・rear—front—1D.rear—front4.深度为K的二叉树所含叶子的个数最多为()A.2KB.KC.2-1D.2kH5.一个栈的入栈序列是a,b,c,d,e,则栈的不可能的输出序列是()A.e,d,c,b,aB.d,e,c,b
5、,ad,c,e,a,bD.a,b,c,d,e6.如图所示的4棵二叉树屮，不是完全二叉树的是()(A)(B)(C)(D)1.利用n个值生成的哈夫曼树中共有()个结点AnBn+1C2n■2n—12.有一个有序表为{1,3,9,12,32,41,45,62,75,77,82,95,100},当二分法查找值为82的结点时，()次比较后查找成功。A.1B.2C.4D.83.若对n个元素进行归并排序,则进行每一趟归并的吋间复杂度为()A.0(1)B.O(n)C.0(logm)D.0(n")4.排序方法中，从未排序序列中挑选元素，并将其依次放入已排序序列(初始时为空)的一端的方
6、法，称为()A.希尔排序B.归并排序C.插入排序I).起泡排序5.如果要求一个线性表既能较快地查找，又能适应动态变化的要求，可以采用()查找方法。A.分块B.顺序C.折半D.散列0.436.如图所示的带权无向图，在该图的最小生成树中各条边上权值之和为()A.31B.387.有一个MXN的矩阵A,若采用行序为主序进行顺序存储，每个元素占用8个字节，1)XN+j-1)XA：J(lWiWM,lWjWN)元素的相对字节地址(相对首元素地址而言)为()A.((i-1)XN+j)X8B.((i-C.(iXN+j-1)X8D.((i-1)XN+j+1)X88.某二叉树的先序遍历
7、结点访问顺序是abdgcefh,中序遍历的结点访问顺序是dgbaechf,则其后序遍历的结点访问顺序是()A.bdgcefhaB.gdbecfhaC.bdgaechfD.gdbehfca15如图所示，一个图若从顶点3出发按广度优先搜索法进行遍历，则可能得到的一种顶点序列为()A.abecdefB.abcefdC.aebcfdD・aedfeb三、算法设计题(第一题8分，第二题7分，第三题8分，共23分)1.已知单链表A,B和C为三个元素值递增有序的线性表，现要求对表A作如下运算：删去那些既在表B中出现又在表C中出现的元素。t=p;p=s-〉next;free(t);
8、q二q->
