数据结构经典十套卷之八_设初始记录关键字基本有序,则快速排序

一、选择题(30分)

1.       字符串的长度是指（   ）。

    (A)串中不同字符的个数          (B) 串中不同字母的个数

    (C)串中所含字符的个数          (D) 串中不同数字的个数

2.  建立一个长度为n的有序单链表的时间复杂度为（  ）

    (A)O(n)        (B) O(1)        (C) O(n2)       (D) O(log2n)

3.  两个字符串相等的充要条件是（  ）。

    (A)两个字符串的长度相等        (B) 两个字符串中对应位置上的字符相等

    (C)同时具备(A)和(B)两个条件    (D)以上答案都不对

4.  设某散列表的长度为100，散列函数H(k)=k % P，则P通常情况下最好选择（  ）。

解：实践 证明，当P取小于哈希表长的最大质数时，产生的哈希函数较好

    (A)99          (B) 97          (C) 91          (D) 93

5.  在二叉排序树中插入一个关键字值的平均时间复杂度为（  ）。

在二叉排序树中插入一个结点的时间复杂度为（O(n) 最差 ）

    (A)O(n)        (B) O(1og2n)    (C) O(nlog2n)   (D) O(n2)

6.  设一个顺序有序表A[1:14]中有14个元素，则采用二分法查找元素A[4]的过程中比较元素的顺序为(  )。

解：

1 14 7

1 6 3

4 6 5

4 5 4

    (A)A[1]，A[2]，A[3]，A[4]      (B)A[1]，A[14]，A[7]，A[4]

    (C)A[7]，A[3]，A[5]，A[4]      (D)A[7]，A[5] ，A[3]，A[4]

7.  设一棵完全二叉树中有65个结点，则该完全二叉树的深度为（  ）。

    (A)8           (B) 7           (C) 6           (D) 5

8.  设一棵三叉树中有2个度数为1的结点，2个度数为2的结点，2个度数为3的结点，则该三叉链权中有（  ）个度数为0的结点。

设一棵m叉树中度数为0的结点数为N0，度数为1的结点数为Nl，……，度数为m的结点数为Nm，则N0=（  ）。l+N2+2N3+3N4+……+(m-1)Nm

3：1+2+2*2=7

    (A)5           (B) 6           (C) 7           (D) 8

9.  设无向图G中的边的集合E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，则从顶点a出发进行深度优先遍历可以得到的一种顶点序列为（  ）。

    (A) aedfcb      (B) acfebd      (C)aebcfd      (D) aedfbc

10.  队列是一种（  ）的线性表。

    (A)先进先出    (B) 先进后出    (C) 只能插入    (D) 只能删除

 

二、判断题(20分)

1.  如果两个关键字的值不等但哈希函数值相等，则称这两个关键字为同义词。（  1）

2.  设初始记录关键字基本有序，则快速排序算法的时间复杂度为O(nlog2n)。（  0）

3.  分块查找的基本思想是首先在索引表中进行查找，以便确定给定的关键字可能存在的块号，然后再在相应的块内进行顺序查找。（  1）

4.  二维数组和多维数组均不是特殊的线性结构。（  0）

5.  向二叉排序树中插入一个结点需要比较的次数可能大于该二叉树的高度。（ 0 ）

6.  如果某个有向图的邻接表中第i条单链表为空，则第i个顶点的出度为零。（  1）

7.  非空的双向循环链表中任何结点的前驱指针均不为空。（ 1 ）

8.  不论线性表采用顺序存储结构还是链式存储结构，删除值为X的结点的时间复杂度均为O(n)。（ 1 ）

9.  图的深度优先遍历算法中需要设置一个标志数组，以便区分图中的每个顶点是否被访问过。（ 1 ）

10.  稀疏矩阵的压缩存储可以用一个三元组表来表示稀疏矩阵中的非0元素。（ 1 ）

 

三、填空题(30分)

1．  设一组初始记录关键字序列为(49，38，65，97，76，13，27，50)，则以d=4为增量的一趟希尔排序结束后的结果为___49 13 27 50 76 38 65 97__

2．  下面程序段的功能是实现在二叉排序树中插入一个新结点，请在下划线处填上正确的内容。

Typedef struct node{

int data;

struct node *lchild;

struct node  *rchild;

}bitree;

void bstinsert(bitree *&t,int k)

{

if (t==0 ) {____________________________;

t->data=k;

t->lchild=t->rchild=0;}

else if(t->data>k) bstinsert(t->lchild,k);else__________________________;

}

3．  设指针变量p指向单链表中结点A，指针变量s指向被插入的结点X，则在结点A的后面插入结点X需要执行的语句序列：s->next=p->next;_ p->next =s;。

4．  设指针变量head指向双向链表中的头结点，指针变量p指向双向链表中的第一个结点，则指针变量p和指针变量head之间的关系是p=_head->rlink________和head=_ p->llink_________（设结点中的两个指针域分别为llink和rlink）。

5．  设某棵二叉树的中序遍历序列为ABCD，后序遍历序列为BADC，则其前序遍历序列为_CABD_________。

6．  完全二叉树中第5层上最少有___1_____个结点，最多有_16________个结点。

7．  设有向图中不存在有向边<Vi,Vj>，则其对应的邻接矩阵A中的数组元素A[i][j]的值等于_____0_______。

8．  设一组初始记录关键字序列为(49，38，65，97，76，13，27，50)，则第4趟直接选择排序结束后的结果为_13，27，38，50，76，49，65，97

9．  设连通图G中有n个顶点e条边，则对应的最小生成树上有__n-1_________条边。

10．     设有一组初始记录关键字序列为(50，16，23，68，94，70，73)，则将它们调整成初始堆只需把16与___________相互交换即可。

 

四、算法设计题(20分)

1.  设计一个在链式存储结构上统计二叉树中结点个数的算法。

2.  设计一个算法将无向图的邻接矩阵转为对应邻接表的算法。

 

 

参考答案

 

一、选择题

1．C       2．C       3．C       4．B       5．B

6．C       7．B       8．C       9．A      10．A

 

二、判断题

1．对     2．错     3．对     4．错     5．错

6．对     7．对     8．对     9．对     10．对

 

三、填空题

1.        (49，13，27，50，76，38，65，97)

2.        t=(bitree*)malloc(sizeof(bitree))，bstinsert(t->rchild,k)

3.        p->next=s

4.        head->rlink，p->llink

5.        CABD

6.        1，16

7.        0

8.        (13，27，38，50，76，49，65，97)

9.        n-1

10.    50

 

四、算法设计题

1.  设计一个在链式存储结构上统计二叉树中结点个数的算法。

voidcountnode(bitree *bt,int &count)

{

   if(bt!=0)

{count++;countnode(bt->lchild,count); countnode(bt->rchild,count);}

}

2.  设计一个算法将无向图的邻接矩阵转为对应邻接表的算法。

typedef struct {intvertex[m]; int edge[m][m];}gadjmatrix;

typedef structnode1{int info;int adjvertex; struct node1 *nextarc;}glinklistnode;

typedef structnode2{int vertexinfo;glinklistnode *firstarc;}glinkheadnode;

voidadjmatrixtoadjlist(gadjmatrix g1[ ],glinkheadnode g2[ ])

{

int i,j;glinklistnode *p;

for(i=0;i<=n-1;i++)g2[i].firstarc=0;

for(i=0;i<=n-1;i++)for(j=0;j<=n-1;j++)

if(g1.edge[i][j]==1)

{

p=(glinklistnode*)malloc(sizeof(glinklistnode));p->adjvertex=j;

p->nextarc=g[i].firstarc;g[i].firstarc=p;

p=(glinklistnode*)malloc(sizeof(glinklistnode));p->adjvertex=i;

p->nextarc=g[j].firstarc;g[j].firstarc=p;

}

}