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

《数据结构期末样卷(含答案).doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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．判定一个循环队列Q

2、U（最多元素为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.是任

3、意一棵二叉树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，

4、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.快速排序二．填空题(20分)1．下面程序段的时间复杂度是O(n2)。for(i=0;i

5、链表是一种物理存储单元上非连续、非顺序的存储结构。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.采用邻接表存储的图，

6、其广度优先遍历类似于二叉树的按层遍历。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分）。statusalgo2(StackS，inte){StackT；i

7、ntd；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分）4．请对下图的无向带权图，写出它的邻接表，并按克鲁斯卡尔/Prim算法求其最小生成树（10分）。5．设散列表的长度ｍ=13；散列函数为

8、H(K)=Kmodm，给定的关键码序列