答案数据结构函授习题2008.docVIP

习题，仅供参考 一、 选择填空 1、 线形表若采用链式存储结构时，要求内存中可用存储单元的地址是__A___。 A.必须是连续的 B.部分地址必须是连续的 C.一定是不连续的 D.连续或不连续都可以 2.下面程序段的时间复杂度是___C__。 s=0; for (i=0;in;i++) for (j=0;jn;j++) s+=B[i][j]; sum=s; A. O(n) B. O(nlogn) C. O(n2) D. O(logn) 3．一个队列的入队序列是1、2、3、4，则队列的输出序列是__B___。 A． 4、3、2、1 B．1、2、3、4 C． 1、4、3、2 D．3、2、4、1 4. 非空的循环单链表head的尾结点（由p指向）满足__A___。 A. p-next=null B. p=null C. p-next=head D. p=head 5. 向一个栈顶指针为HS的链栈中插入一个s所指结点时，则执行___D__。 A. HS-next=s B. s-next=HS-next; HS-next=s C. S-next=HS D. s-next=HS; HS=s 6. 在一个具有n个顶点的无向图中，要连通全部顶点至少需要（ C ）条边。 A n B n+1 C n-1 D n/2 7、按照二叉树的定义，具有3个结点的二叉树有___B__种。 A. 3 B. 4 C. 5 D. 2 A． 3 B．4 C．5 D．6 8、在一棵二叉树中，度为2的结点数为15个，度为1的结点数为32个，则叶子结点数为个__D____。 A、47 B、17 C、15 D、16性质3:对任何一棵二叉树T,如果其终端结点数为n0,度为2的结点数为n2,则n0=n2+1 ___A__。 A、4 B、5 C、6 D、1810．带头结点的单链表head为空的判定条件是__B___。 A. head=null B. head-next=null C. head-next=head D. head !=null 10、如果要求一个线性表既能较快地查找，又能适应动态变化的要求，可以采用 A． 分块 B．顺序 C．二分 D．散列 二、操作题 1．由如图所示的二叉树，试写出中序遍历序列，前序遍历序列，后序遍历序列。（15分） 中序遍历序列前序遍历序列后序遍历序列 2.图的遍历 下图为一图形结构，现对该图进行深度优先有哪些信誉好的足球投注网站和广度优先有哪些信誉好的足球投注网站（按照先左后右），试写出从顶点0出发得到的深度优先有哪些信誉好的足球投注网站的顶点序列； 从顶点0出发得到的广度优先有哪些信誉好的足球投注网站的顶点序列。 深度优先 0 1 3 7 8 4 9 5 6 2 广度优先 0 1 2 3 4 5 6 7 8 9 三、 设有一组关键字{19，01，23，14，55，20，84，27，68，38 }，采用哈希函数：H(key)=key Mod 11采用开放地址法的线性探测再散列方法解决冲突，试在0~12的散列地址空间中对该关键字序列构造哈希表。 H(19)=19%11=8H(01)=1%11=1H(23)=23%11=12H(14)=14%11=3H(55)=55%11=0H(20)=20%11=9H(84)=84%11=7H(27)=27%11=5H(68)=68%11=2H(38)=38%11=5四、简答题 空串和空白串的区别 （6分）空串:长度为零的串,它不包含任何字符. 空白串:仅由一个或多个空格组成的串它用来反映一个数据的内部构成，即一个数据由那些成分数据构成，以什么方式构成，呈什么结构。数据结构有逻辑上的数据结构和物理上的数据结构之分栈是线表中的一种类型，先进后出，后进先出。 1 4 5 8 6 2 3 7