资源描述：
《数据结构C语言第一次作业.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。
1、2011年上半年数据结构（C语言）作业一一、单选题（每题2分，共20分）1、链表不具有的特点是___A____。A.可随机访问任一元素B.插入删除不需要移动元素C.不必事先估计存储空间D.所需空问与线性表长度成正比2、假设图的顶点数=n,边数=e，那么当用邻接表表示图时，拓扑排序算法的时间复杂度为____B____。A.O(n2)B.O(n+e)C.O(n*e)DO(n3)3、广义表((f),(f))的表尾是C。A.fB.(f)C.((f))D.()4、若指针L指向一带头结点的循环单链表的头结点，该表为空表的条件是____D___为真值；A.!(L->link);B.L=
2、=(L->link)->link;C.L->link;D.L==L->link;5、采用分块查找时，若线性表中共有625个元素，查找每个元素的概率相同，假设采用顺序查找来确定结点所在的块时，每块应分为____B____个结点最佳。A.10B.25C.6D.6256、若线性表最常用的操作是存取第i个元素及其直接前驱的值，则采用__A___存储方式节省时间。A．顺序表B．双链表C．单循环链表D．单链表7、下列排序算法中时间复杂度不受数据初始状态影响，恒为O(n2)的是____C______。A、堆排序B、起泡排序C、直接选择排序D、快速排序8、若某链表中最常用的操作是在最后一
3、个结点之后插入一个结点和删除最后一个结点，则采用___D_____存储方式最节省运算时间（假设链表仅设有一个first指针）。A.单链表B.双链表C.单循环链表D.带头结点的双循环链表9、一棵左右子树均不为空的二叉树在后序线索化后（不带头结点的线索化），其空指针域数为____B_____。A、0B、1C、2D、不确定10、某二叉树的先序序列和后序序列正好相反，则该二叉树一定是___B_____的二叉树。A.空或只有一个结点B.高度等于其结点数（空树高度为0）C.任一结点无左孩子D.任一结点无右孩子二、填空作图解答题（第4小题6分，其余9分，共60分）1.依次插入30，43
4、，21，9，15，51并由空树构成一棵平衡二叉树，画出该平衡二叉树形成过程及其中序线索二叉树。1.已知广义表为（(),‘a’,(2,(‘c’,5,8)))；试画出该广义表的存储表示。2.用快速排序对下列关键字进行排序（图示）,基准元素取第一个元素。7033796746243040写出两趟排序的结果。第一趟排序之后:{40,33,67,46,24,30}70{79}或{40,33,30,67,46,24}70{79};第二趟排序之后:{30,33,24}40{67,46}70,79或{24,33,30}40{46,67}70,79;若基准元素按“三者取中”的原则取，则两趟排
5、序的结果是：第一趟排序之后:第二趟排序之后:;3.已知9个结点的值分别为1～9，请将各结点的值填入下面二叉排序树中：4.如下图已知哈希表为空，哈希函数为H（Key）=KeyMOD11,冲突解决方法分别用线性探测再散列和二次探测再散列。填入在依次插入关键字14，37，25，16之后的情况，并求等概率情况下所要求的平均查找长度。（1）线性探测再散列01234567891014372516（2）二次探测再散列01234567891025143716线性探测再散列查找不成功时的平均查找长度=____21/11_;二次探测再散列查找成功时的平均查找长度=___6/4=3/2=1.5
6、_;1.已知一字符串bcbdebcecbdcabd，试设计其赫夫曼编码并画出相应的赫夫曼树。a：1；b：5；c：4；d：3；e：2；2.在下面数组a中链接存储着一个线性表，其表头“指针”为head==0，可利用空间表第一个元素的“指针”av==5：a012345678data6056423812742520link437-128-116a012345678data8856423812742520link471-152-136现在依次进行如下操作：1)在元素56前插入元素78；2）删除元素60；3）删除25；4）在元素56后插入66；5）在元素66前插入88。请问，在进行上
7、面操作后，av==8,并将此时数组a的内容填入下表：一、程序填空题（每空2分，共20分）1.下面是仅给出了部分操作的二叉树类的定义和实现。试在程序的每一划线部分填入一条语句或表达式，完成计算度为1的结点个数的操作countNodes1()。typedefstructBinNode{intdata;structBinNode*leftchild,*rightchild;}BinNode,*BinTree;voidInitBinTree(BinTree&root)//初始化二叉树root{root=Null;}voidDestro
