2011年上半年数据结构（C语言）作业一年上半年数据结构数据结构（语言）
一、
单选题（单选题（每题2分，共20分）
1、链表不具有的特点是___A____。A可随机访问任一元素B插入删除不需要移动元素C不必事先估计存储空间D所需空问与线性表长度成正比2、假设图的顶点数
边数e，那么当用邻接表表示图时，拓扑排序算法的时间复杂度为____B____。AO
2BO
eCO
eDO
33、广义表ff的表尾是C。AfBfCfD4、若指针L指向一带头结点的循环单链表的头结点，该表为空表的条件是____D___为真值；ALli
kBLLli
kli
kCLli
kDLLli
k5、采用分块查找时，若线性表中共有625个元素，查找每个元素的概率相同，假设采用顺序查找来确定结点所在的块时，每块应分为____B____个结点最佳。A10B25C6D6256、若线性表最常用的操作是存取第i个元素及其直接前驱的值，则采用__A___存储方式节省时间。A．顺序表B．双链表C．单循环链表D．单链表7、下列排序算法中时间复杂度不受数据初始状态影响，恒为O
2的是____C______。A、堆排序B、起泡排序C、直接选择排序D、快速排序8、若某链表中最常用的操作是在最后一个结点之后插入一个结点和删除最后一个结点，则采用___D_____存储方式最节省运算时间（假设链表仅设有一个first指针）。A单链表B双链表C单循环链表D带头结点的双循环链表9、一棵左右子树均不为空的二叉树在后序线索化后（不带头结点的线索化），其空指针域数为____B_____。A、0B、1C、2D、不确定10、某二叉树的先序序列和后序序列正好相反，则该二叉树一定是___B_____的二叉树。A空或只有一个结点B高度等于其结点数（空树高度为0）C任一结点无左孩子D任一结点无右孩子二、1
填空作图解答题（填空作图解答题（第4小题6分，其余9分，共60分）
依次插入30，43，21，9，15，51并由空树构成一棵平衡二叉树，画出该平衡二叉树形成过程及其中序线索二叉树。
f23
已知广义表为（‘a’2‘c’58；试画出该广义表的存储表示。
用快速排序对下列关键字进行排序（图示）基准元素取第一个元素。7033796746243040写出两趟排序的结果。第一趟排序之后4033674624307079或4033306746247079第二趟排序之后3033244067467079或2433304046677079

若基准元素按“三者取中”的原则取，则两趟排序的结果是：第一趟排序之后第二趟排序之后
4
已知9个结点的值分别为1～9，请将各结点的值填入下面二叉排序树r