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

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

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．abc

2、de4．判定一个循环队列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.所有的结点均无左孩子

3、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

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

5、0;j

6、个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

7、=NULL;}returnOK;}//A//形成一个循环链表2．简述以下算法的功能（5分）。7statusalgo2(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

8、的一棵赫夫曼树，并求其加权路径长度WPL。（10分）74．请对下图的无向带权图，写出它的邻接表，并按克鲁斯卡尔/Prim算法求其最小生成树（10分）。75．设散列表的长度ｍ=13；散列函数为H(K)=Kmodm，给定的关