数据结构三套试卷详细分析

答案如下：

int CountX(LNode* HL,ElemType x)

{ int i=0; LNode* p=HL;//i为计数器 while(p!=NULL)

{ if (P->data==x) i++; p=p->next;

}//while, 出循环时i中的值即为x结点个数 return i; }//CountX

数据结构试卷（二）

一、选择题(24分)

1．下面关于线性表的叙述错误的是（ D ）。

(A) 线性表采用顺序存储必须占用一片连续的存储空间 (B) 线性表采用链式存储不必占用一片连续的存储空间 (C) 线性表采用链式存储便于插入和删除操作的实现 (D) 线性表采用顺序存储便于插入和删除操作的实现

Ps:顺序表具有的缺点之一就是不利于插入和删除操作，所以将存储方式改进为链式存储。

2．设哈夫曼树中的叶子结点总数为m，若用二叉链表作为存储结构，则该哈夫曼树中总共有（ B ）个空指针域。 (A) 2m-1 (B) 2m (C) 2m+1 (D) 4m

Ps：哈夫曼树只有叶子和度为2的结点，用二叉链表存储时每个结点都会有一个左孩子，一个右孩子,所以空指针域为2m。

3．设顺序循环队列Q[0：M-1]的头指针和尾指针分别为F和R，头指针F总是指向队头元素的前一位置，尾指针R总是指向队尾元素的当前位置，则该循环队列中的元素个数为（ C ）。 (A) R-F (B) F-R (C) (R-F+M)％M (D) (F-R+M)％M Ps：根据循环队列的定义可知C是正确的。

4．设某棵二叉树的中序遍历序列为ABCD，前序遍历序列为CABD，则后序遍历该二叉树得到序列为（ A ）。 (A) BADC (B) BCDA (C) CDAB (D) CBDA

Ps：根据前序和中序遍历可知，C为根结点，A为左子树，D为右子树，B为A的右子树。 5．设某完全无向图中有n个顶点，则该完全无向图中有（ A ）条边。

22

(A) n(n-1)/2 (B) n(n-1) (C) n (D) n-1 Ps：该题和试卷一的一道填空题一样。

6．设某棵二叉树中有2000个结点，则该二叉树的最小高度为（ C）。 (A) 9 (B) 10 (C) 11 (D) 12

Ps：根据二叉树的性质2可知，该二叉树的最小高度应该是结点数最多的时候，这样列出一个表达式即可知道该二叉树的最小高度。

7．设某有向图中有n个顶点，则该有向图对应的邻接表中有（ B ）个表头结点。 (A) n-1 (B) n (C) n+1 (D) 2n-1 Ps：根据邻接表的定义可知，表头结点数目与顶点数目相同。

8．设一组初始记录关键字序列(5，2，6，3，8)，以第一个记录关键字5为基准进行一趟快速排序的结果为（ C ）。 (A) 2，3，5，8，6 (B) 3，2，5，8，6 (C) 3，2，5，6，8 (D) 2，3，6，5，8

Ps：快速排序是将一个数为基准，然后分为左右两个序列，左边的数都比基准小，右边的数都比基准大。

二、填空题(24分)

1. 为了能有效地应用HASH查找技术，必须解决的两个问题是_构造一个好的HASH函数_

和__确定解决冲突的方法__。

2. 下面程序段的功能实现数据x进栈，要求在下划线处填上正确的语句。

typedef struct {int s[100]; int top;} sqstack; void push(sqstack &stack,int x) {

if (stack.top==m-1) printf(“overflow”);

1. else {_stack.top++__;___stack.s[stack.top]=x__;}

}

3. 中序遍历二叉排序树所得到的序列是__有序____序列（填有序或无序）。

2

4. 快速排序的最坏时间复杂度为__O(n)__，平均时间复杂度为__O(nlog2n)__。 5. 设某棵二叉树中度数为0的结点数为N0，度数为1的结点数为N1，则该二叉树中度数为

2的结点数为__N0-1_；若采用二叉链表作为该二叉树的存储结构，则该二叉树中共有__2N0+N1__个空指针域。

6. 设某无向图中顶点数和边数分别为n和e，所有顶点的度数之和为d，则e=d/2__。 7. 设一组初始记录关键字序列为(55，63，44，38，75，80，31，56)，则利用筛选法建立

的初始堆为_(31，38，54，56，75，80，55，63)_。

8． 已知一有向图的邻接表存储结构如下：从顶点1出发，DFS遍历的输出序列是

(1，3，4，5，2) ，BFS遍历的输出序列是 (1，3，2，4，5)

Ps:DFS:深度优先遍历，BFS：广度优先遍历。 三、应用题(36分)

1． 设一组初始记录关键字序列为(45，80，48，40，22，78)，则分别给出第4趟简单选择

排序和第4趟直接插入排序后的结果。

简单选择排序：(22，40，45，48，80，78)；直接插入排序：(40，45，48，80，22，78) 2． 设指针变量p指向双向链表中结点A，指针变量q指向被插入结点B，要求给出在结点A

的后面插入结点B的操作序列（设双向链表中结点的两个指针域分别为llink和rlink）。 q->llink=p; q->rlink=p->rlink; p->rlink->llink=q; p->rlink=q;

3． 设一组有序的记录关键字序列为(13，18，24，35，47，50，62，83，90)，查找方法用

二分查找，要求计算出查找关键字62时的比较次数并计算出查找成功时的平均查找长度。

2,ASL=91*1+2*2+3*4+4*2)=25/9

4． 设一棵树T中边的集合为{(A，B)，(A，C)，(A，D)，(B，E)，(C，F)，(C，G)}，要求

用孩子兄弟表示法（二叉链表）表示出该树的存储结构并将该树转化成对应的二叉树。 5． 设有无向图G，要求给出用普里姆算法构造最小生成树所走过的边的集合。 E={(1，3)，(1，2)，(3，5)，(5，6)，(6，4)}

6． 设有一组初始记录关键字为(45，80，48，40，22，78)，

要求构造一棵二叉排序树并给出构造过程。

四、算法设计题(16分)

1． 设有一组初始记录关键字序列（K1，K2，…，Kn），要求设计一个算法能够在O(n)的时间

复杂度内将线性表划分成两部分，其中左半部分的每个关键字均小于Ki，右半部分的每个关键字均大于等于Ki。

Ps：该算法即为快速排序算法 void quickpass(int r[], int s, int t) {

int i=s, j=t, x=r[s]; while(i

while (ix) j=j-1; if (i

r[i]=x; }

2． 设有两个集合A和集合B，要求设计生成集合C=A∩B的算法，其中集合A、B和C用链

式存储结构表示。

typedef struct node {int data; struct node *next;}lklist;

void intersection(lklist *ha,lklist *hb,lklist *&hc) {

lklist *p,*q,*t;

for(p=ha,hc=0;p!=0;p=p->next)

{ for(q=hb;q!=0;q=q->next) if (q->data==p->data) break;

if(q!=0){ t=(lklist *)malloc(sizeof(lklist)); t->data=p->data;t->next=hc; hc=t;} }

}

数据结构试卷（三）

一、选择题(每题1分，共20分)

1．设某数据结构的二元组形式表示为A=(D，R)，D={01，02，03，04，05，06，07，08，09}，R={r}，r={<01，02>，<01，03>，<01，04>，<02，05>，<02，06>，<03，07>，<03，08>，<03，09>}，则数据结构A是（ B ）。 (A) 线性结构 (B) 树型结构 (C) 物理结构 (D) 图型结构 Ps：将该题的结构图画出即可看出是什么结构。 2．下面程序的时间复杂为（B ）

for（i=1，s=0； i<=n； i++） {t=1；for(j=1；j<=i；j++) t=t*j；s=s+t；}

234

(A) O(n) (B) O(n) (C) O(n) (D) O(n) Ps：这里面有双层循环嵌套在一起，每层都有运行n次，两次即为n*n。

3．设指针变量p指向单链表中结点A，若删除单链表中结点A，则需要修改指针的操作序列为（ A ）。

(A) q=p->next；p->data=q->data；p->next=q->next；free(q)； (B) q=p->next；q->data=p->data；p->next=q->next；free(q)； (C) q=p->next；p->next=q->next；free(q)； (D) q=p->next；p->data=q->data；free(q)；

Ps：首先用指针变量q指向结点A的后继结点B，然后将结点B的值复制到结点A中，最后删除结点B。

4．设有n个待排序的记录关键字，则在堆排序中需要（ A ）个辅助记录单元。

2

(A) 1 (B) n (C) nlog2n (D) n

5．设一组初始关键字记录关键字为(20，15，14，18，21，36，40，10)，则以20为基准记录的一趟快速排序结束后的结果为(A )。 (A) 10，15，14，18，20，36，40，21 (B) 10，15，14，18，20，40，36，21 (C) 10，15，14，20，18，40，36，2l (D) 15，10，14，18，20，36，40，21

6．设二叉排序树中有n个结点，则在二叉排序树的平均平均查找长度为（ B ）。

2

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

7．设无向图G中有n个顶点e条边，则其对应的邻接表中的表头结点和表结点的个数分别为（ D ）。 (A) n，e (B) e，n (C) 2n，e (D) n，2e 8. 设某强连通图中有n个顶点，则该强连通图中至少有（C ）条边。 (A) n(n-1) (B) n+1 (C) n (D) n(n+1)

9．设有5000个待排序的记录关键字，如果需要用最快的方法选出其中最小的10个记录关键字，则用下列（ D ）方法可以达到此目的。 (A) 快速排序 (B) 堆排序 (C) 归并排序 (D) 插入排序

Ps：快速排序、归并排序和插入排序必须等到整个排序结束后才能够求出最小的10个数，而堆排序只需要在初始堆的基础上再进行10次筛选即可，每次筛选的时间复杂度为O(log2n)。

10.下列四种排序中（ D ）的空间复杂度最大。 (A) 插入排序 (B) 冒泡排序 (C) 堆排序 (D) 归并排序

二、填空殖(每空1分 共20分)

1. 数据的物理结构主要包括_顺序存储结构__和__链式存储结构__两种情况。