一、习题篇

       (一) 概念题

                1. 试述数据结构研究的3个方面的内容。

                         解析：数据结构研究的3个方面分布是：

                               数据的逻辑结构

                               数据的存储结构

                               数据的运算(操作)

2. 试述集合、线性结构、树形结构和图形结构4种常见的数据结构的特性。

                       集合结构

                               集合中数据元素之间除了“同属于一个集合”的特性外，数据元素之间无其他关系，它们之间的关系称为是松散性的

                       线性结构

                               线性结构中数据元素之间存在“一对一”的关系。

                               若结构非空，则它有且仅有一个开始结点和终端结点，开始结点没有前驱但有一个后继。终端结点没有后继但有一个前驱。其余结点有其仅有一个前驱和后继。

                       树形结构

                               树形结构中数据元素之间存在“一对多”的关系。

                               若结构非空，则它有一个称为根的结点，此结点无前驱结点，其余结点有且仅有一个前驱，所有结点都可能有多个后继。

                       图形结构

                        图形结构中数据元素之间存在“多对多”的关系。

             若结构非空，则在这种数据结构中任何结点都可能有多个前驱和后继。

3. 设有数据的逻辑结构的二元组定义形式为B=(D,R), 其中D = {a1,a2,a3,......an} ,  R={< ai,a i+1 > | i = 1,2,3.......n -1},请画出此逻辑结构对应的顺序存储结构和链式存储结构的示意图。

顺序存储结构示意图:

链式结构示意图：

              4. 设一个数据结构的逻辑结构如下图，请写成它的二元组定义形式。

                       解析：由于二元组的定义形式为B= (D,R) ; 如图可知：

                               D = {k1,k2,k3,k4,k5,k6,k7,k8,k9} ；

                               则R = {ROW,COL} 【{行,列}】。故：R = { , , , , , , , , , , }

                 5. 试确定下列程序段中有标记符号 ‘ # ’ 的语句行的语句频度(其中n为正整数)

(1)  语句频度：n-1

i = 1 ; k = 0 ;
while ( i <= n -1 ) {
    k += 10*i ;             // #
    i++ ;
}

(2)  语句频度：当n <= 1 时频度为 1 ， 当n > 1 时语句频度 为 n-1

i = 1 ; k = 0 ;
do {
    k += 10 * i ;        //#
    i++ ;
}while (i <= n-1 )；

(3)  语句频度：n-1

i = 1 ; k = 0 ;
while ( i <= n -1 ) {
    i++ ;
     k += 10*i ;             // #
}

(4)  语句频度：n(n+1)/2

k = 0 ;
for(int i = 1 ; i <= n ; i++ ) {
    for( int j = 1; j <= i ; j++ ) {
        k++ ;         // #
    }
}

(5)  语句频度：n

i = 1 ; j = 0 ;
while (i + j <= n) {
    if(i > j ) {
        j ++ ;      //#
    }else {
        i ++ ;
    }
}

(6)  语句频度：根号n 取整

x = n ; y = 0 ;        //n 是不小于1 的整数
while (x >= (y+1) * (y+1) ) {
    y ++ ;            //#
}

(7)   语句频度：1100

x = 91 ; y = 100 ;
while( y > 0 ) {
    if(x > 100 ) {
        x -= 10 ; 
        y -- ;        //#
    }else {
        x++ ;
    }
}

(8)  语句频度：log3 n 【3 为下标】

a = 1 ; m = 1 ;
while(a < n) {
    m += a ;
    a *= 3 ;         //# 
}