数据结构(专科)

第1次自检自测

一、单选题（每小题2分，共8分）

1.执行下面的程序段时，执行S语句的次数为（　D　　）

for ( int i=1 ; i <=n ; i++ )

for ( int j=1 ; j <= i ; j++ )

             S ;

    A. n2       B. n2/2            C.n (n+1)             D.n (n+1)/2

2.请指出下面二元组表示的数据结构属于何种结构。（　B　　）

    D＝（K，R）

    K＝（1，2，3，4，5）

    R＝｛（1，2），（1，5），（2，3），（2，4）｝

    A. 线性表           B. 树                C. 集中                D. 图

3.在单链表HL中，若要在指针q所指向结点的后面插入一个由指针p所指向的结点，则执行（　D　　）

　　A. q－>next ＝ p－>next ; p－>next ＝ q ;

    B. p－>next ＝ q－>next ; q ＝ p ;

    C. q－>next ＝ p－>next ; p－>next ＝ q;

    D. p－>next ＝ q－>next ; q－>next ＝ p ;

4.当利用大小为N的数组顺序存储一个栈时，假定用top＝＝N表示栈空，则向这个栈插入一个元素时，首先应执行（　　C　）语句修改top指针。

    A.top＋＋        B. top=0           C. top――           D. top＝－1

二、填空题（每空1分，共23分）

1. 一个算法的时间复杂度为（4n2＋2nlog2n＋3n－7）/ (5n)，其数量级表示为（　O（n）　　）。

2. 对于线性表（11，43，15，50，30，22，94，72）进行散列存储时，若选用H(K)=K%8作为散列函数，则散列地址为0的元素有（　　　1　　　）个，散列地址为3的元素有（　　　2　　）个，散列地址为6的元素有（　　3　）个。

3. 从一个数组a[7]中顺序查找元素时，假定查找第一个元素a[0]的概率为1/3，查找第二个元素a[1]的概率为1/4，查找其余元素的概率均相同，则在查找成功时同元素的平均比较次数为（　35/12 或 2.92　　　）。

4. 队列的插入操作在（　队尾　进行，删除在（　队首　）进行；而栈的插入与删除均在（栈顶　）进行。

5. 在一个顺序队列Q中，判断队空的条件为（　Q.front＝＝Q.rear　　）,判断队满的条件为（　（Q.rear＋1）%Maxsize＝＝Q.front　　　　　　）

6. 中缀表达式　7×（8＋x）－5/（y－3）　所对应的后缀表达式为：（　7　8　x　＋　×　5　y　3　－　/　－　　　　）

7. 在一棵5层的完全二叉树中，结点数最多为（　31　）个，结点数最少为（　16　）个。

8. 对于一棵具有n个结点的二叉树，若一个结点的编号为i(0≤i≤n－1)，则它的左孩子结点的编号为（　2i＋1），右孩子结点的编号为（　2i+2），双亲结点的编号为（　（i－1）/2 ）。

9. 在一棵m阶B_树上，每个非树根结点的关键字数目最少为（　「m/2」-1　）个，最多为（　 m-1　　）个，其子树数目最少为（　 「m/2」　　），最多为（　m   　　　）。

10. 一个广义表为((a),(c,(d,(e,f))) ,b)，则该广义表的长度为（　3　），深度为（　4　）。

11. 已知一个稀疏矩阵如下，试写出它对应的三元组线性表：(        (1,4,3),(2,1,2),(2,5,5),(3,3,4),(4,2,6),(5,5,1))       　　）。

三、运算题（每小题9分，共18分）

1. （9分）画出下面给出的广义表的带表头附加结点的链接存储结构图，并计算出它的长度和深度。

　　F＝（a,（b,（）,c,（（d）,e）））

答：

长度为：2　，　深度为：4

2. （9分）已知一个带权图的顶点集V和边集G分别为：

    V={0，1，2，3，4，5}；

    E={(0，l)7，(0，2)9，(0，3)10，(l，4)5，(l，5)6，(2，3)15，(2，4)13，(3，5)11 }；

    则求出该图的最小生成树的权。（要求写出解题步骤）

答：最小生成树的权：37

四、分析题（每小题9分，共36分）

1.（9分）已知有６个数据：４、１５、６、８、２０、１２，试把它们作为叶子结点的权值，画出对应的哈夫曼树，并计算出此树的带权路径长度ＷＰＬ。

答：1．ＷＰＬ＝１５８

2. （9分）写出下图分别按前、中、后序遍历时得到的结点序列。

答案：

前序：25　　16　　8　　37　　30　　28　　26　　29　　32　　35　　48　　60

中序：8　　16　　25　　26　　28　　29　　30　　32　　35　　37　　48　　60

后序：8　　16　　26　　29　　28　　35　　32　　30　　60　　48　　37　　25

3．（9分）一个广义表为E=((a,(a,b),((a,b),((a,b),c))))，请用图形表示该广义表。

答案：

4．（9分）已知一个图如左图所示，它的邻接表如右图所示，试写出从Va出发分别按深度优先遍历和广度优先遍历得到的顶点序列。

深度优先遍历：VA,VB,VD,VF,VC,VE

广度优先遍历：VA,VB,VC,VF,VD,VE

五、算法题（15分）

1. 阅读算法，回答问题（10分）

void AA(LNode*& HL)

{

    InitList(HL);

    InsertRear(HL,51);

    int a[5]={17,10,11,28,14};

for(int i=0;i<5;i++) InsertFront(HL,a[i]);

    InsertRear(HL,35);

}

该算法被调用执行后，得到的以HL为表头指针的单链表中的数据元素依次为：

（　　答案：(14,28,11,10,17,51,35)　　）。

2．编写算法（5分）

编写在以BST为树根指针的二叉搜索树上进行查找值为item的结点的非递归算法，若查找成功，则由item带回整个结点的值并返回true，否则返回false。

    bool  Find(BtreeNode * BST,ElemType &item)

答案：bool  Find（BtreeNode *BST，ElemType＆item）

    ｛

         while（BST!=NULL）

         {

            if（item==BST->data）｛item=BST->data；return  true；｝

            else if（item＜BST->data＝BST=BST->left；

else BST=BST->right；

          ｝

          return false ；

    ｝

数据结构（专科）

第2次自检自测

一、单选题（每小题2分，共8分）

1.执行下面的程序段时，执行S语句的次数为（　A　　）

for ( int i=1 ; i <=n ; i++ )

for ( int j=1 ; j <= n ; j++ )

             S ;

    A. n2        B. n2/2   C.n (n+1)       D.n (n+1)/2

2.请指出下面二元组表示的数据结构属于何种结构。（　D　　）

    D＝（K，R）

    K＝（1，2，3，4，5，6）

    R＝｛（1，2），（2，3），（2，4），（3，4），（3，5），（3，6），（4，5），（4，6）｝

    A. 线性表           B. 树                C. 集中                D. 图

3.若让元素a,b,c依次进栈，则出栈次序不可能出现的是（　B　　）种情况。

    A. c,b,c           B. c,a,b           C. b,a,c             D. a,c,b

4.当利用大小为N的数组顺序存储一个栈时，假定用top＝＝－1表示栈空，则向这个栈插入一个元素时，首先应执行（　A　　）语句修改top指针。

    A.top＋＋        B. top=0          C. top――             D. top＝－1

二、填空题（每空1分，共17分）

1. 一个算法的时间复杂度为（n3＋20n2log2n＋3）/ (12n)，其数量级表示为（　　　　　）。

2. 对于线性表（18，25，63，50，42，32，90，66）进行散列存储时，若选用H(K)=K%9作为散列函数，则散列地址为0的元素有（　　　　　　　）个，散列地址为3的元素有（　　　　　　　）个，散列地址为5的元素有（　　　　　　　）个。

3. 从一个数组a[9]中顺序查找元素时，假定查找第一个元素a[0]的概率为1/3，查找第二个元素a[1]的概率为1/4，查找第三个元素a[2]的概率为1/6，查找其余元素的概率均相同，则在查找成功时同元素的平均比较次数为（　　　　）。

4. 在循环单链表中，最后一个结点的指针域指向（　　　　）结点。

5. 从一个链栈中删除一个结点时．需要把栈顶结点的（　　　　　　　　）域的值赋给（　　　　　　　　）。

6. 在一个顺序队列Q中，判断队空的条件为（　　　　　　　　　　　　　　　　　　）,判断队满的条件为（　　　　　　　　　　　　　　　　　　　　　）

7. 中缀表达式3×（x＋2）－5所对应的后缀表达式为：（　　　　　　　　　　　　　　）

8. 在一棵二叉树中，第5层上的结点数最多为（　　　　）个。

9. 对于一棵具有n个结点的二叉树，若一个结点的编号为i(1≤i≤n)，则它的左孩子结点的编号为（　　   　　），右孩子结点的编号为（　　   　　），双亲结点的编号为（　   　　　）。

10. 一个广义表为((a),b,(c,(d)),(e,f))，则该广义表的长度为（　　　），深度为（　　　）。

1.答案：O（n2）　　　　　2.答案：3、1、2　　　　　3.答案：71/24 或　2.96

4.答案：表头　　　　　　5.答案：指针、栈顶指针

6.答案：Q.front＝＝Q.rear　　，　（Q.rear＋1）%Maxsize＝＝Q.front

7.答案：3　x  2  ＋　×　5　－

8.答案：16　　　　9.答案：2i、2i+1、i/2(或[i/2])　　　　　10.答案：4、3

三、运算题（每小题10分，共20分）

1. （10分）画出下面给出的广义表的带表头附加结点的链接存储结构图，并计算出它的长度和深度。

　　F＝（a,（b,（）,c）,（（d）,e））

1. 答案：

长度为：3　，　深度为：3

2. （10分）已知一个带权图的顶点集V和边集G分别为：

    V={0，1，2，3，4，5，6，7}；

    E={(0，l)8，(0，2)5，(0，3)2，(l，5)6，(2，3)25，(2，4)13，(3，5)9，(3，6)10，(4，6)4，(5，7)20}；

    则求出该图的最小生成树的权。（要求写出解题步骤）

2.答案：

最小生成树的权：55

四、分析题（每小题10分，共40分）

1.（10分）已知有7个数据：5、3、23、7、14、9、12，试把它们作为叶子结点的权值，画出对应的哈夫曼树，并计算出此树的带权路径长度ＷＰＬ。

1．ＷＰＬ＝190

2. （10分）写出下图分别按前、中、后序遍历时得到的结点序列。

2.答案：

前序：25　　16　　8　　37　　30　　28　　26　　29　　32　　60　　48

中序：8　　16　　25　　26　　28　　29　　30　　32　　37　　48　　60

后序：8　　16　　26　　29　　28　　32　　30　　48　　60　　37　　25

3．（10分）一个广义表为E=((a,(a,b),((a,b),c)))，请用图形表示该广义表。

答案：

4．（10分）采用折半查找的方法对一维数组A(1:12)进行查找时，根据查找每一元素需要比较的次数填写下表。

答案：

五、算法题（15分）

1. 阅读算法，回答问题（10分）

void AA(LNode*& HL)

{

    InitList(HL);

    InsertRear(HL,50);

    int a[5]={15,8,9,26,12};

for(int i=0;i<5;i++) InsertFront(HL,a[i]);

    InsertRear(HL,30);

}

该算法被调用执行后，得到的以HL为表头指针的单链表中的数据元素依次为：

（答案：(12,26,9,8,15,50,30)　　　　）。

2．编写算法（5分）

编写在以BST为树根指针的二叉搜索树上进行查找值为item的结点的非递归算法，若查找成功，则由item带回整个结点的值并返回true，否则返回false。

    bool  Find(BtreeNode * BST,ElemType &item)

答案：bool  Find（BtreeNode *BST，ElemType＆item）

    ｛

         while（BST!=NULL）

         {

            if（item==BST->data）｛item=BST->data；return  true；｝

            else if（item＜BST->data＝BST=BST->left；

else BST=BST->right；

          ｝

          return false ；

｝

数据结构（专科）

第3次自检自测

一、单选题（每小题2分，共10分）

1. 在以HL为表头指针的带表头附加结点的循环单链表中，链表为空的条件为（　　　）。

    A. HL->next= =NULL               B. HL->next= = －1                

C. HL->next= =HL                  D. HL->next= = 1

2. 对于一棵具有n个结点的二叉树，若一个结点的编号为i(1≤i≤n)，则它的双亲结点的编号为（　　　）。

    A. 2i                             B. 2i+1   

C. 2i－1                          D. i/2　（注：下取整）

3. 在一个具有n个顶点的有向完全图中，包含有（　　　）条边。

    A. n                             B. n(n-1)/2   

C. 2n                            D. n(n-1)

4. 中缀算术表达式3*(5+x)/y所对应的后缀算术表达式为（　　　）。

    A. 5  x  +  3  *  y  /            B. 3  5  x  +  *  y  /   

C. 3  *  5  +  x  /  y            D. 3  5  *  x  +  y  /

5. 当从一个小根堆中删除一个元素时，需要把（　　　）元素填补到堆顶位置，然后再按条件把它逐层向下调整。

    A. 堆顶元素的左孩子              B. 堆顶元素的右孩子   

C. 堆的最左边一个元素            D. 堆尾

1.答案：C    2.答案：D    3.答案：D    4.答案：B    5.答案：D

二、填空题（每空1分，共20分）

1. 一个算法的时间复杂度为（n3＋5nlog2n＋2）/ (7n)，其数量级表示为（　　　　　）。

2．计算机执行一个递归调用语句或函数时，首先把值参和（　　　　　　　　）的当前值以及调用后的返回地址压入栈，接着计算每个值参所对应的实在参数表达式的值并把它赋给（　　　　　　　　），然后无条件转向算法的第一条语句继续执行。

3．假定一个线性表为(12，23，74，55，63．40．82，36)，若按Key％3条件进行划分，使得同一余数的元素成为一个子表，则得到的三个子表分别为（　　　　　　　　）、（　　　　　　　　）和（　　　　　　　　）。

4．在一个顺序队列中，队首指针指向队首元素的（　　　　　　　）位置。

5．后缀表达式“　2　50　*　3　－　”的值为（　　　　）。

6．一棵深度为6的满二叉树中的结点数为（　　　　）个，一棵深度为3的满三叉树中的结点数为（　　　　）个。

7．数据的逻辑结构被分为集合结构、（　　　　　　）、（　　　　）和图结构四种。

8．在广义表的存储结构中，每个结点均包含有3个域，分别是行号、列号和（　　　　　）。

9. 队列的插入操作在（　　　　　）进行，删除在（　　　　　）进行。

10. 在一个顺序队列Q中，判断队空的条件为（　　　　　　　　　　　　　　　　　　）。

11. 在一棵m阶B_树上，每个非树根结点的关键字数目最少为（　   　　　）个，最多为（　   　　　）个。

12. 一个广义表为((a),b,(c,(d,(g))),(e,f))，则该广义表的深度为（　　　）。

13. 已知一个稀疏矩阵如下，试写出它对应的三元组线性表：（　           　　）。

答案：

1．O（n2）

2．局部变量、值参变量

3．(12,63,36)、(55,40,82)、(23,74)

4．前一个

5． 97

6．63、13

7．线性结构、树结构

8．元素值

9．答案：队尾，队首

10．答案：Q.front＝＝Q.rear

11．答案：「m/2」-1、m-1

12. 5

13.答案：((1,4,3),(2,1,2),(2,5,5),(3,3,4),(4,2,6),(5,5,1))

三、分析题（每小题10分，共50分）

1．按照元素36、25、45、16、20、48、72、18的插入次序，生成一颗二叉排序树，试画出此二叉排序树。

答案：

2. 已知一个带权无向图如下：

    请画出其最小生成树。

答案：

3．已知一维数组A（1：10）中的数据如下，试写出在快速排序的过程中每次划分后数据的排列情况。

    ⑴[33 14 42 35] 46 [50 92 53 78 60]

 ⑵14 33 [42 45] 46 50 [92 53 78 60]

 ⑶14 33 35 42 46 50 [60 53 78] 92

 ⑷14 33 35 42 46 50 53 60 78 92

4．采用折半查找的方法对一维数组A(1:12)进行查找时，根据查找每一元素需要比较的次数填写下表。

答案：

5．假定一棵普通树的广义表表示为a(b(e)，c(f(h，i，j)，g)，d)，分别写出先根、后根、按层遍历的结果。

答案：先根：a，b，e，c，f，h，i，j，g，d；

    后根：e，b，h，i，j，f，g，c，d，a；

    按层：a，b，c，d，e，f，g，h，i，j；

四、算法题（每题10分，共20分）

1．阅读程序，回答问题。

    void AF(Queue & Q)

    {

       InitQueue(Q);

       int  a[4]={5,8,12,15};

for ( int i=0 ; i<4 ; i++ ) Qinsert( Q , a[i] );

       Qinsert( Q , Qdelete(Q) );

       Qinsert( Q , 30 );

       Qinsert( Q , Qdelete(Q)+10 );

       while ( ! QueueEmpty(Q) ) cout<< Qdelete(Q) <<' ';

    }

    该算法被调用后得到的输出结果为：_______________。

答案：12  15  5  30  18

2．从一维数组A[n]上进行快速排序的递归算法。

    void QuickSort( ElemType  A[],  int  s,  int  t )

    {

      int  i=s , j=t+1;

      ElemType  x=A[s];

      do {

      do i+ +; while ( __________________________________ );

      //填写一个循环条件

do j- -; while( A[j].stn > x.stn );

         if ( i           {

ElemType  temp=A[i];

A[i]=A[j];

A[j]=temp;

}

} while ( i      A[s]=A[j];

A[j]=x;

if ( s if( j+1    }

A[i].sin＜x.sin

    QuickSort(A，s，j-1)

    QuickSort(A，j+1，t)

数据结构（专科）

第4次自检自测

一、单选题（每小题2分，共10分）

1. 对于一棵具有n个结点的二叉树，若一个结点的编号为i(1≤i≤n)，则它的左孩子结点的编号为（　　　）。

    A. 2i                             B. 2i+1   

C. 2i－1                          D. i/2　（注：下取整）

2. 对于一棵具有n个结点的二叉树，若一个结点的编号为i(1≤i≤n)，则它的右孩子结点的编号为（　　　）。

    A. 2i                             B. 2i+1   

C. 2i－1                          D. i/2　（注：下取整）

3. 在线性表的散列存储中，装填因子α又称为装填系数。若用m表示散列表的长度，n表示待散列存储的元素的个数，则α等于（　　　）。

    A. m/n                             B. 2m/n   

C. n/m                             D. 2n/m

4. 在如下一维数组Ａ中折半查找85时，所需比较的次数为(　　　)。

    A.2                             B.3   

C.4                             D. 5

5. 对于一棵含有40个结点的理想平衡树，它的高度为（　　　）。

    A. 5                              B. 6   

C. 7                              D. 8

1.答案：A    2.答案：B    3.答案：C    4.答案：C    5.答案：B

二、填空题（每空1分，共20分）

1. 一个算法的时间复杂度为（n3＋200n2－98）/ (200n)，其数量级表示为（　　　　　）。

2．计算机执行一个递归调用语句或函数时，首先把（　　　　　　　　）和局部变量的当前值以及调用后的返回地址压入栈，接着计算每个值参所对应的实在参数表达式的值并把它赋给值参变量，然后无条件转向算法的（　　　　　　　　）继续执行。

3．假定一个线性表为(12，23，74，55，63．40．82，36)，若按Key％2条件进行划分，使得同一余数的元素成为一个子表，则得到的两个子表分别为（　　　　　　　　）和（　　　　　　　　）。

4．数据的存储结构被划分为（　　　　　　　　）、（　　　　　　　　）、索引和散列四种。

5．栈又称为（　　　　　　　　）表，队列又称为（　　　　　　　　）表。

6．后缀表达式“　18　3　－　5　/　”的值为（　　   　　）。

7．一棵深度为4的满二叉树中的结点数为（　　       　　）个，一棵深度为4的满四叉树中的结点数为（　      　　　）个。

8．在广义表的存储结构中，每个结点均包含有3个域，分别是（　　       　　　）、（　　　     　　）和元素值。

9．栈的插入与删除均在（　　　      　　　）进行。

10．从一棵二叉搜索树中查找一个元素时，若元素的值等于根结点的值，则表明（　　　　　　），若元素的值小于根结点的值，则继续向（　　　　　　）查找，若元素的值大于根结点的值，则继续向下查找。

11．在线性表的单链接存储中，若一个元素所在结点的地址为P，则其后继结点的地址为（　　　　　　　　　），若假定P为一个数组a中的下标，则其后继结点的下标的（　　　　　　　　　）。

12. 一个广义表为 ( ( a ) , ( c , ( d , ( e , f ) ) ) , b , g ) ，则该广义表的长度为（　　 　）

答案：

1． O（n2）

2．值参、第一条语句

3．(12,74,40,82,36)、(23,55,63)

4．顺序、链接

5．后进先出、先进先出

6． 3

7．15、85

8．行号、列号

9．栈顶 

10．堆尾、堆顶

11．P->next、a[p].next

12．4

三、分析题（每小题10分，共50分）

1．已知一颗二叉树如下图所示，试分别写出按照中序、先序和后序遍历时得到的结点序列。

答案：1．中序：17、26、38、42、45、52、63、68、74、84

   先序：45、38、17、26、42、74、63、52、68、84

   后序：26、17、42、38、52、68、63、84、74、45

2. 已知一个带权无向图如下：

    请画出其最小生成树。

答案：

3．已知一维数组A（1：10）中的数据如下，试写出在快速排序的过程中每次划分后数据的排列情况。

答案：⑴[33 25 14] 38 [70 45 92 53 42 60]

 ⑵[14 25] 33 38 [70 45 92 53 42 60]

 ⑶14 25 33 38 [70 45 92 53 42 60]

 ⑷14 25 33 38 [60 45 42 53] 70 [92]

 ⑸14 25 33 38 [53 45 42] 60 70 [92]

 ⑹14 25 33 38 [42 45] 53 60 70 [92]

 ⑺14 25 33 38 42 45 53 60 70 92

4．利用堆排序的方法给已知数组Ａ中的数据排序，必须先构成初始堆。请写出构成初始堆的过程中A中数据的变化。

构成初始堆的过程：

答案：构成初始堆的过程

   ⑴　45 28 49 75 37 82 56 16

   ⑵　45 28 82 75 37 49 56 16

   ⑶　45 75 82 28 37 49 56 16

   ⑷　82 75 56 28 37 49 45 16

5. 已知有６个数据：４、１５、６、８、２０、１２，试把它们作为叶子结点的权值，画出对应的哈夫曼树，并计算出此树的带权路径长度ＷＰＬ。

答案：ＷＰＬ＝１５８

四、算法题（每小题10分，共20分）

1．阅读程序，回答问题。

    void AA( List & L )

    {

       InitList(L);

       InsertRear(L,30);

       InsertFront(L,50);

int  a[4]={5,8,12,15};

For (int i=0;i<4;i++) InsertRear( L , a[i] );

    }

    请写出算法被调用执行后所得到的线性表L。

线性表L：

1．（50，30，5，8，12，15）

2．阅读程序，回答问题。

    void AH ( Heap &HBT , const ElemType item )

       //HBT为一个小根堆

    {

        HBT.heap[HBT.size]=item;

        HBT.size+ +;

        ElemType  x=item;

        int  i=HBT.size-1;

        while ( i!=0 )

        {

           int j=(i-1)/2;

           if ( x>=HBT.heap[j] )  break;

           HBT.heap[i]=HBT.heap[j];

           I=j;

         }

         HBT.heap[i]=x;

    }

答案：向HBT堆中插人一个值为item的元素，使得插入后仍是一个堆。