2015年网络大专下半年数据结构C语言(一)答案.doc

数据结构（C语言）作业一 单选题（每题2分，共20分） 下述哪一条是顺序存储结构的优点?___C____。 A. 插入运算方便 B. 可方便地用于各种逻辑结构的存储表示C. 存储密度大 D. 删除运算方便 2、一个栈的入栈序列为A,B,C,D,E,则栈的不可能的出栈序列是___D______。 A.ABCDE B. EDCBA C. DECBA D. DCEAB 3、广义表(a,(b,c),d,e)的表头是 A 。 A. a B. a,(b,c) C.( a,(b,c)) D. (a) 4、 在单链表指针为p的结点之后插入指针为S的结点，正确的操作时__C____为真值； A.p-next=s;s-next=p-next; B. s-next=p-next;p-next=s; C. p-next=s;p-next=s-next; D. p-next=s-next;p-next=s; 采用分块查找时，若线性表中共有625个元素，查找每个元素的概率相同，假设采用顺序查找来确定结点所在的块时，每块应分为___B_____个结点最佳。 A. 10 B. 25 C. 6 D. 625 6、若线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则采用__D__存储方式节省时间。 A．单链表 B．双链表 C．单循环链表 D．顺序表 7、下列排序算法中时间复杂度不受数据初始状态影响，恒为O(n2)的是___C_____。 A、堆排序 B、起泡排序 C、直接选择排序 D、快速排序 8、设无向图的顶点个数为n，则该图最多有___D_____条边。 A. n(n-1)/2 B. n-1 C. n(n+1)/2 D. n2 一棵左右子树均不为空的二叉树在后序线索化后（不带头结点的线索化），其空指针域数为____B_____。 A、0 B、1 C、2 D、不确定 10、某二叉树的先序序列和后序序列正好相反，则该二叉树一定是_____C___的二叉树。 A. 空或只有一个结点 B. 任一结点无左孩子C. 高度等于其结点数（空树高度为0） D. 任一结点无右孩子 填空作图解答题（第4小题6分，其余9分，共60分） 依次插入60，34，41，38，15,9并由空树构成一棵平衡二叉树， 画出该平衡二叉树形成过程及其中序线索二叉树。 答： 已知广义表为（(), ‘a’, (2,(‘c’,5,8)))；试画出该广义表的存储表示。 答： 对下面的数据表,写出采用希尔排序算法排序的每一趟的结果,并标出数据移动情况。 ( 125 11 22 34 15 44 76 66 100 8 14 20 2 5 1) 答： 第一趟排序之后：{40,33,67,46,24,30}70,79或{40,33,30,67,46,24}70{79}； 第二趟排序之后：{30,33,24}40{67,46}70.79或{2,30}40{46,67}70,79； 若基准元素按“三者取中”的原则取，则两趟排序的结果是： 第一趟排序之后:{40，33，46，24，30} 67 {79，70} 或 {33，40，30，24，46} 67，{70，79}; 第二趟排序之后:{30，33，24} 40 {46} 67，70，79 或 {24，30} 33 {40，46} 67，70，79; 对下面的关键字集{30,15,21,40,25,26,36,37}若查找表的装填因子为0.8，采用线性探测再哈希方法解决冲突 设计哈希函数 答： H(key)=key % 7 画出哈希表 答： 散列地址 0 1 2 3 4 5 6 7 8 9 关键字 21 15 30 36 25 40 26 37 比较次数 1 1 1 3 1 1 2 6 （3）计算查找成功和查找失败的平均查找长度 答： ASLunsncc=(9+8+7+6+5+4+3+2+1+1)/10=4.6 ASLsucc=16/8=2 已知一字符串bcbdebcecbdcabd，试设计其赫夫曼编码并画出相应的赫夫曼树。