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

数据结构期末样卷 一． 单项选择题( 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．e d c b a B．d e c b a C．d c e a b D．a b c d e 4．判定一个循环队列QU（最多元素为m0）为满队列的条件是 。 A．QU-front==QU-rear B．QU-front！==QU-rear C．QU-front==（QU-rear+1）％m0 (不是很确定) D．QU-front!==（QU-rear+1）％m0 5．串是一种特殊的线性表，其特殊性体现在__________。 A．可以顺序存储 B.数据元素是一个字符 C．可以链接存储 D.数据元素可以是多个字符 6．一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足_________。 A. 所有的结点均无左孩子 B. 所有的结点均无右孩子 C. 只有一个叶子结点 D. 是任意一棵二叉树 7．若采用三元组压缩技术存储稀疏矩阵，只要把每个元素的行下标和列下标互换，就完成了对该矩阵的转置运算，这种观点 。 A．正确 B．错误 8．广义表((a，b，c，d))的表头是 ，表尾是 。 A．a B．( ) C．(a，b，c，d) D．((a，b，c，d)) 9．一组记录的排序码为（46，79，56，38，40，84），则利用堆排序的方法建立的初始堆为 。 A．79，46，56，38，40，80 B. 84，79，56，38，40，46 C. 84，79，56，46，40，38 D. 84，56，79，40，46，38 10．用某种排序方法对线性表（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.快速排序 二．填空题( 20分) 1．下面程序段的时间复杂度是 O(n2) 。 for (i=0;in;i++) for (j=0;jm;j++) A[i][j]=0; 2．在单链表中，要访问某个结点，只要知道该结点的指针即可；因此，单链表是一种物理存储单元上非连续、非顺序的存储结构先??移动栈顶指针??，后??存入元素某个不大于哈希表表长m的数按层遍历 4．请对下图的无向带权图，写出它的邻接表，并按克鲁斯卡尔/Prim算法求其最小生成树（10分）。 5．设散列表的长度ｍ=13；散列函数为H(K)=K mod m，给定的关键码序列为20，21，14，68，19，23，30，1，84，15，27，79，试画出用线性探测再散列法解决冲突时所构造的散列表。并求出在等概率的情况下，这种方法有哪些信誉好的足球投注网站成功时的平均有哪些信誉好的足球投注网站长度。 0 1 2 3 4 5 6 7 8 9 10 11 12 14 1 68 30 15 19 20 21 84 23 27 79 平均有哪些信誉好的足球投注网站长度=40/12=3.3 6. 已知序列{583，87，512，61，908，170，897，275，623，462}，采用基