《函授习题2008.doc》由会员分享，可在线阅读，更多相关《函授习题2008.doc（3页珍藏版）》请在金锄头文库上搜索。
1、习题，仅供参考一、 选择填空1、 线形表若采用链式存储结构时，要求内存中可用存储单元的地址是_A_。 A.必须是连续的 B.部分地址必须是连续的 C.一定是不连续的 D.连续或不连续都可以2.下面程序段的时间复杂度是_C_。s=0;for (i=0;in;i+) for (j=0;jnext=null B. p=null C. p-next=head D. p=head5. 向一个栈顶指针为HS的链栈中插入一个s所指结点时，则执行_D_。A. HS-next=s B. s-next=HS-next; HS-next=sC. S-next=HS D. s-next=HS; HS=s6. 在一个具
2、有n个顶点的无向图中，要连通全部顶点至少需要（ C ）条边。 A n B n+1 C n-1 D n/27、按照二叉树的定义，具有3个结点的二叉树有_种。 A. 3 B. 4 C. 5 D. 2 A 3 B4 C5 D68、在一棵二叉树中，度为2的结点数为15个，度为1的结点数为32个，则叶子结点数为个_D_。 A、47 B、17 C、15 D、16性质3:对任何一棵二叉树T,如果其终端结点数为n0,度为2的结点数为n2,则n0=n2+19、一棵二叉树的结点数为18个，则它的最小高度为_A_。 A、4 B、5 C、6 D、1810带头结点的单链表head为空的判定条件是_B_。14586237
3、A. head=null B. head-next=null C. head-next=head D. head !=null10、如果要求一个线性表既能较快地查找，又能适应动态变化的要求，可以采用A 分块 B顺序 C二分 D散列二、操作题 1由如图所示的二叉树，试写出中序遍历序列，前序遍历序列，后序遍历序列。（15分）中序遍历序列 78421536前序遍历序列 12478356后序遍历序列 78425631 2.图的遍历 下图为一图形结构，现对该图进行深度优先搜索和广度优先搜索（按照先左后右），试写出从顶点0出发得到的深度优先搜索的顶点序列； 从顶点0出发得到的广度优先搜索的顶点序列。深度优
4、先 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采用开放地址法的线性探测再散列方法解决冲突，试在012的散列地址空间中对该关键字序列构造哈希表。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四、简答题1. 空串
5、和空白串的区别 （6分）空串:长度为零的串,它不包含任何字符. 空白串:仅由一个或多个空格组成的串 2写出下面有向图中每个顶点的入度和出度。（6分）(1)入度 3 出度 2 4 (2)入度 6 出度 1 5 (3)入度 无 出度 1 4 (4)入度 1 3 出度 5(5)入度 4 出度 2 6 (6)入度 2 5 出度 无 3. 什么是数据结构？通常分为哪几类？（6分） 它用来反映一个数据的内部构成，即一个数据由那些成分数据构成，以什么方式构成，呈什么结构。数据结构有逻辑上的数据结构和物理上的数据结构之分 4. 什么是栈？简述顺序栈的入栈操作和出栈操作步骤。（7分） 栈是线情表中的一种类型，先进后出，后进先出。
