1 数据结构期末样卷 一． 单项选择题( 1 0 分) 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.快速排序 2 二．填空题( 2 0 分) 1．下面程序段的时间复杂度是 O(n2) 。 for (i=0;i
