数据结构试题答案

一、单项选择题（每题2分，共30分）

1.若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用（  ）存储方式最节省时间。

A) 单链表           B) 双链表          C) 单向循环链表     D) 顺序表

2.串是任意有限个（  ）。

A) 符号构成的序列                      B) 符号构成的集合

C) 字符构成的序列                      D) 字符构成的集合

3.设矩阵A的任一元素aij(1≤i,j≤10)满足：

aij≠0；(i≥j,1≤i,j≤10)

aij=0； (i<j,1≤i,j≤10)

现将A的所有非0元素以行序为主序存放在首地址为2000的存储区域中，每个元素占有4个单元，则元素A[9,5]的首地址为（  ）。

A) 2340             B) 2336            C) 2164              D) 2160

4.如果以链表作为栈的存储结果，则出栈操作时（  ）。

A) 必须判别栈是否为满                  B) 对栈不作任何判别

C) 必须判别栈是否为空                  D) 判别栈元素的类型

5.设数组Data[0..m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针,则执行出队操作的语句为（  ）。

A) front = front+1                     B) front = (front+1) % m

C) rear = (rear+1) % m                 D) front = (front+1) % (m+1)

6.深度为6(根的层次为1)的二叉树至多有（  ）结点。

A) 64               B) 32              C) 31                D) 63

7.将含100个结点的完全二叉树从根这一层开始，每层上从左到右依次堆结点编号，根结点的编号为1。编号为49的结点X的双亲的编号为（  ）。

A) 24               B) 25              C) 23                D) 无法确定

8.设有一个无向图 和 ，如果 为 的生成树，则下面不正确的说法是（  ）。

A)  为 的子图                       B)  为 的连通分量

C)  为 的极小连通子图且       D)  为 的一个无环子图

9.用线性探测法查找闭散列表，可能要探测多个散列地址，这些位置上的键值（  ）。

A) 一定都是同义词                      B) 一定都不是同义词

C) 多相同                               D) 不一定都是同义词

10.二分查找要求被查找的表是（  ）。

A) 键值有序的链接表                    B) 链接表但键值不一定有序

C) 键值有序的顺序表                    D) 顺序表但键值不一定有序

11.当初始序列已经按键值有序，用直接插入算法对其进行排序，需要循环的次数为（  ）。

A)               B)           C)             D) n－1

12.堆是一个键值序列 ,对 ，满足（  ）。

A)                        B)

C)  且 ( )      D)  或 ( )

13.使用双向链表存储数据，其优点是可以（  ）。

A) 提高检索速度                        B) 很方便地插入和删除数据

C) 节约存储空间                        D) 很快回收存储空间

14.设计一个判别表达式中左右括号是否配对出现地算法，采用（  ）数据结构最佳。

A) 线性表地顺序存储结构                B) 栈

C) 队列                                D) 线性表达的链式存储结构

15.设深度为k的二叉树上只有度为0和2的结点，则此类二叉树中所含的结点数至少为（  ）。

A) k + 1            B) 2k              C) 2k - 1             D) 2k + 1

二、填空题（每空2分，共28分）

1.设r指向单链表的最后一个结点，要在最后一个结点之后插入s所指的结点，需执行的三条语句是_____________________________________________r=s;r->next=NULL。

2.在单链表中，指针p所指结点为最后一个结点的条件是___________________。

3.设一个链栈的栈顶指针是ls，栈中结点格式为              ，栈空的条件为_____________。如果栈不为空，则出栈操作为p=ls;______________;free(p)。

4.已知一棵度为3的树有2个度为1的'结点，3个度为2的结点，4个度为3的结点，则该树有________个叶子结点。

5.树有三种常用的存储结构，即孩子链表法，孩子兄弟链表法和____________。

6.n个顶点的连通图的生成树有__________条边。

7.一个有向图G中若有弧 、 和 ，则在图G的拓扑序列中，顶点 的相对位置为___________。

8.设表中元素的初始状态是按键值递增的，分别用堆排序、快速排序、冒泡排序和归并排序方法对其进行排序(按递增顺序)，________最省时间，__________最费时间。

9.下面是将键值为x的结点插入到二叉排序树中的算法，请在划线处填上适当的内容。

Typedef struct pnode

{ int key;

struct node * left, * right;

}

Void search (int x; pnode t )

{ if (_____________)

{p = malloc (size);

p->key=x;p->left=NULL;

p->right=NULL;

t=p;

}

else

if (xkey) search (x,t->left)

else  _________________

}

10.线性表的____________的主要优点是从表中任意结点出发都能访问到所有结点。而使用____________，可根据需要在前后两个方向上方便地进行查找。

三、应用题（每题10分，共30分）

1.在双链表中，要在指针变量P所指结点之后插入一个新结点，请按顺序写出必要的算法步骤。(设：P所指结点不是链表的首尾结点，q是与p同类型的指针变量)

2.已知待排序文件各记录的排序码顺序如下：

72  73  71  23  94  16  05  68

请列出快速排序过程中每一趟的排序结果。

四、算法题(共12分)

编写算法，实现单链表上的逆置运算(说明：即将单链表中的元素次序反转)

参考答案：

一、单项选择题（每题2分，共30分）

1.D   2.C  3.D   4.C   5.D   6.D   7.A   8.B   9.D   10.C   11.D   12.C  13.A   14.B   15.C

二、填空题（每空2分，共28分）

1. r->next=s;                             2. p->next=NULL;

3. ls = = NULL; ls=ls->link。 4. 12

5. 双亲表示法   6. n-1

7. i,j,k    8. 冒泡排序，快速排序

9. t= =NULL，search（x,t->right）； 10.循环链表，双向链表

三、应用题（每题10分，共30分）

1．new(q)；

q↑k ← p；

q↑k ← p↑k；

p↑k↑k ← q；

p↑k ← q。

评分细则：按顺序每对一个给2分，全对计10分。

2．各趟结果如下：

[68 05 71 23 16] 72 [94 73]

[16 05 23] 68 [71] 72 [94 73]

[05] 16 [23] 68 [71] 72 [94 73]

05 16 [23] 68 [71] 72 [94 73]

05 16 23 68 71  72 [94 73]

05 16 23 68 71  72 [73] 94

05 16 23 68 71  72  73 94

四．算法题(共12分)

void invert（ pointer head）

{p=NULL;

while ( head<>NULL)

{u=head;

head=head->next;

u->next=p;

p=u;

}

head=p;

}