1.2.2填空题(将正确的答案填在相应的空中) 1.数据逻辑结构包括、和④三种类型树形结构和图形结构合称为① 答;①线性结构②树形绪构⑧图形结构④①非线性结构 2.在线性结构中,第一个结点①前驱结点,其余每个结点有且只有②个前驱结点;最 后一个结点④后续结点,其余每个结点有且只有①个后续结点。 答:①没有②1③没有①1 3.在树形结构中,树根结点没有①结点,其余每个结点有且只有②个前驱结点;叶子 结点没有③结点,其余每个结点的后续结点可以④。 答:①前驱②1③后续④任意多个 1.在图形结构中,每个结点的前驱结点数和后续结点数可以① 答:①任意多个 5.线性结构中元素之间存在①关系,树形结构中元素之间存在②关系,图形结构中 元素之间存在④关系 答:T一对一②一对多③多对多 6.算法的五个重要特性是 答:有穷性确定性可行性输入输出 7.下面程序段的时间复杂度是①。 for(=0;i<n;++) for (j=Oujsm:i+-) AI[门=0 答:O(m“n) 8.下面程序段的时间复杂度是① while (s<n) i=i+1 答:了O(n) 9.下面程序段的时间复杂度是D for (i=Oi<n: i for (=O: <n: j s+=B[
数据结构习题与解析C语言篇 答:①O(n2) 10.下面程序段的时间复杂度是①。 while (I 13习题解析 1.设有数据逻辑结构为: B=(K, R) R={<k1,k3>,<k1,k8>,<k2,k3>,<k2,k4>,<k2k5>,<k3,k9>,<k5 k6>,<k8,k9>,<k9,k7>,<k4,k7>,<k4,k6>} 画出这个逻辑结构的图示,并确定相对于关系R哪些结点是开始结点哪些结点是终 端结点? 解:该题的逻辑绪构图示如图1.2所示。 开始结点是指无前驱的结点这里满足该定义的开始结点为k1,k2 终端结点是指无后续的结点,这里满足该定义的终端结点为k6k7。 该逻辑结构是非线性结构中的图形结构 图1.2逻辑结构图示 2设有如图1.3所示的逻辑结构图示给出它的逻辑结构 解:本题的逻辑结构如下: B= (K R) K={k1,k2 R={<k1k2>,<k1,k3>,<k3,k4>,<k3,k6>,<k6,k8>,<k4k5>,<k6
该逻辑纬构是一个树形结构,其树根为k1,叶子结点为k2、k5、k7和k9 图1.3逻辑结构图示 下列是几种用二元组表示的数据结构,画出它们分别对应的逻辑图形表示,并指出它 们分别属于何种结构 (1)A=(K,R),其中 K=1a.bcdef g,h R=r r=;<ab>,<b,c>,<c,d>,<d,e>,<e,f>,<f,g>,<gh> (2)B=(K,R)其中: K b.c.d.e. g,hy =:<db>,<d,g>,<da>,<bc>,<g,e>,<g,h>,<e,f>} (3)C=(K,R).其中: K=1,2,3.4,5,6 R=rk r=:(1,2)(2.3),(2,4),(3,4),(3,5),(3,6),(4,5),(4,6)} 这里的圆括号对表示两结点是双向的 (4)D=(K,R).其中 K=48,25.64,57,82、36.75} R= rl.2 r1=:<25.36>,<36,48>,<48,57>,<5764>,<64,75>,<75,82>} r2=;<18.25>,<48.64>,<64,57>、<64,82>,<25,36 解
数据结构习题与解析(C语育篇 (1)A对应逻辑图形如图1.4所示,它是一种线性结构。 图1.4对应A的逻辑结构图示 (2)B对应逻辑图形如图1.5所示,它是一种树形结构。 图1.5对应B的逻辑结构图示 (3)C对应逻辑图形如图1.6所示,它是一种图形结构。 (4)D对应逻辑图形如图1.7所示,它是一种图形结构r1(对应图中虚线部分)为线性 结构,r2(对应图中实线部分)则为树形结构。 有如下递归函数fact(n),分析其时间复杂度 fact(int n) If (n<=1)return(1); else retum(n fact (n-1));
图1.6对应C的逻辑结构图示 图1.7对应D的逻辑结构图示 解:设fact(n)的运行时间函数是T(n)。该函数中语句①的运行时间是0(1),语句②的 运行时间是T(n-1)+((1),其中O(1)为运算的时间。 (1) ≤ 因此:T T(n-1)+O(1)n>1 则:T(n)=O(1)+T(n-1) 2#O)(1)+T(n-2) (n-1)*O(1)+T(1) =n*O(1) 即fact(n)的时间复杂度为O(n)