数据结构期末样卷(含答案)

1数据结构期末样卷一．单项选择题(10分)1．线性表逻辑顺序与存储顺序总是一致的，这种说法A。A正确B不正确2.在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入s结点，则执行。A.s-next=p-next;p-next=s;B.p-next=s-next;s-next=p;C.q-next=s;s-next=p;D.p-next=s;s-next=q;3．一个栈的入栈序列是a，b，c，d，e，则栈的不可能的输出序列是___________。A．edcbaB．decbaC．dceabD．abcde4．判定一个循环队列QU（最多元素为m0）为满队列的条件是。A．QU-front==QU-rearB．QU-front！==QU-rearC．QU-front==（QU-rear+1）％m0(不是很确定)D．QU-front!==（QU-rear+1）％m05．串是一种特殊的线性表，其特殊性体现在__________。A．可以顺序存储B.数据元素是一个字符C．可以链接存储D.数据元素可以是多个字符6．一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足_________。A.所有的结点均无左孩子B.所有的结点均无右孩子C.只有一个叶子结点D.是任意一棵二叉树7．若采用三元组压缩技术存储稀疏矩阵，只要把每个元素的行下标和列下标互换，就完成了对该矩阵的转置运算，这种观点。A．正确B．错误8．广义表((a，b，c，d))的表头是，表尾是。A．aB．()C．(a，b，c，d)D．((a，b，c，d))9．一组记录的排序码为（46，79，56，38，40，84），则利用堆排序的方法建立的初始堆为。A．79，46，56，38，40，80B.84，79，56，38，40，46C.84，79，56，46，40，38D.84，56，79，40，46，3810．用某种排序方法对线性表（25，84，21，47，15，27，68，35，20）进行排序时，元素序列的变换情况如下：（1）25，84，21，47，15，27，68，35，20（2）20，15，21，25，47，27，68，35，84（3）15，20，21，25，35，27，47，68，84（4）15，20，21，25，27，35，47，68，84则所采用的排序方法是。A.选择排序B.希尔排序C.归并排序D.快速排序2二．填空题(20分)1．下面程序段的时间复杂度是O(n2)。for(i=0;in;i++)for(j=0;jm;j++)A[i][j]=0;2．在单链表中，要访问某个结点，只要知道该结点的指针即可；因此，单链表是一种物理存储单元上非连续、非顺序的存储结构。3．向栈中压入元素的操作是_先移动栈顶指针，后存入元素_。4．在无向图G的邻接矩阵A中，若A[i][j]等于1，则A[j][i]等于1。5．在散列函数H（key）=key%p中，p应取某个不大于哈希表表长m的数。6．在对一组记录（54，38，96，23，15，72，60，45，83）进行直接插入排序时，当把第7个记录60插入到有序表时，为寻找插入位置需比较3次。7．有一个10阶对称矩阵A，采用压缩存储方式（以行序为主存储，且A[0][0]=1），则A[8][5]的地址是86。8.采用邻接表存储的图，其广度优先遍历类似于二叉树的按层遍历。9．基数排序不需要进行记录关键字间的比较。10．一个有n个顶点的无向图最多有__n*(n-1)/2条边。三．综合题(50分)1．简述以下算法的功能（5分）。StatusA(LinkedListL){//L是无表头结点的单链表if(L&&-next){Q=L;L=L-next;P=L;While(P-next)P=P-next;P-next=Q;Q-next=NULL;}returnOK;}//A//形成一个循环链表2．简述以下算法的功能（5分）。3statusalgo2(StackS，inte){StackT；intd；InitStack(T)；while(!StackEmpty(S))｛Pop(S，d)；if(d!=e)Push(T，d)；}while(!StackEmpty(S))｛Pop(T，d)；//这里应该有点问题把S改成T（我自己认为）Push(S，d)；}}将堆栈S中的为e的值去掉。。（T充当临时存放的堆栈）3．设给定权集w={1，23，14，7，28，9}，试构造关于w的一棵赫夫曼树，并求其加权路径长度WPL。（10分）44．请对下图的无向带权图，写出它的邻接表，并按克鲁斯卡尔/Prim算法求其最小生成树（10分）。55．设散列表的长度ｍ=13；散列函数为H(K)=Kmodm，给定的关键码序列为20，21，14，68，19，23，30，1，84，15，27，79，试画出用线性探测再散列法解决冲突时所构造的散列表。并求出在等概率的情况下，这种方法搜索成功时的平均搜索长度。012345678910111214168301519202184232779平均搜索长度=40/12=3.36.已知序列{583，87，512，61，908，170，897，275，623，462}，采用基数排序法对该序列作升序排序时的每一趟的结果（10分）。61706146251262358327587897908四．算法设计题(20分)1．设顺序表va中的数据元素递增有序。试写一算法，将x插入到顺序表的适当位置上，以保持该表的有序性。IntIntsert（SqList*va,datatypex）{If(va-length==MAXSIZE)rerurnERROR;intk=va-Length;for(inti=0;iva-Length;i++){if(va-data[i]x){k=i;break;}}For(intj=va-length-1;jk-1;j--){va-data[j+1]=va-data[j];}Va-data[k]=x;Va-length++;ReturnOK;}2．假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点(注意不设头指针)，试编写相应的队列初始化、入队列的算法。typedefstructN0de{intdata;structN0de*next;}N0de,*QueuePtr;typedefstruct{QueuePtrrear;}SqListVoidInitalSql(SqList*Q){//初始化Q-rear=(QueuePtr)newNOde();Q-rear-next=Q-rear;7}VoidEnSqlList(Sqlist*Q，inte){//插入QueuePtrp;p=(QueuePtr)malloc(sizeof(N0de));p-data=e;p-next=Q-rear-next;Q-rear-next=p;returnOK;}