2014数据结构试题及答案

101. 【第1章 绪论】一个算法的时间复杂度为(n3+n2log2n+14n)/n2，其数量级表示为____O(n)____。

102. 【第1章 绪论】数据的物理结构主要包括_____________和______________两种情况。 元素的表示，关系的表示

103. 【第1章 绪论】for(i=1，t=1，s=0；i<=n；i++) {t=t*i；s=s+t；}的时间复杂度为_________。 O(n)

104.【第2章 线性表】设指针变量p指向双向循环链表中的结点X，则删除结点X需要执行的语句序列为_________________________________________________________（设结点中的两个指针域分别为llink和rlink）。

p>llink->rlink=p->rlink; p->rlink->llink=p->rlink

105. 【第2章 线性表】设有一个顺序循环队列中有M个存储单元，则该循环队列中最多能够存储________

个队列元素；当前实际存储________________个队列元素（设头指针F指向当前队头元素的前一个位置，尾指针指向当前队尾元素的位置）。 M-1 ， (R-F+M)%M

106. 【第2章 线性表】设顺序线性表中有n个数据元素，则第i个位置上插入一个数据元素需要移动表中

_______个数据元素；删除第i个位置上的数据元素需要移动表中_______个元素。 n+1-i ，n-i

107. 【第2章 线性表】设指针变量p指向单链表中结点A，指针变量s指向被插入的新结点X，则进行插入操作的语句序列为__________________________（设结点的指针域为next）。 s->next=p->next; p->next=s

108.【第2章 线性表】设F和R分别表示顺序循环队列的头指针和尾指针，则判断该循环队列为空的条件为_____________________。 F==R

109.【第4章 栈和队列】后缀算式9 2 3 +- 10 2 / -的值为__________。中缀算式（3+4X）-2Y/3对应的后缀算

式为_______________________ -1 ，3 4 X * + 2 Y * 3 / -

110. 【第4章 栈和队列】不论是顺序存储结构的栈还是链式存储结构的栈，其入栈和出栈操作的时间复杂度

均为____________。 O（1）

111. 【第4章 栈和队列】栈的插入和删除只能在栈的栈顶进行，后进栈的元素必定先出栈，所以又把栈称为

__________表；队列的插入和删除运算分别在队列的两端进行，先进队列的元素必定先出队列，所以又把队列称为_________表。 后进先出 ,先进先出

112. 【第5章 树】若用链表存储一棵二叉树时，每个结点除数据域外，还有指向左孩子和右孩子的两个指针。

在这种存储结构中，n个结点的二叉树共有________个指针域，其中有________个指针域是存放了地址，有________________个指针是空指针。 2n ，n-1 ， n+1

113. 【第5章 树】假定一棵树的广义表表示为A（C，D（E，F，G），H（I，J）），则树中所含的结点数为

_----_________个，树的深度为___________，树的度为_________。 9 ，3 ，3

114.【第5章 树】设一棵完全二叉树中有500个结点，则该二叉树的深度为__________；若用二叉链表作为该完全二叉树的存储结构，则共有___________个空指针域 9，501

115. 【第5章 树】设有n个结点的完全二叉树，如果按照从自上到下、从左到右从1开始顺序编号，则第i

个结点的双亲结点编号为____________，右孩子结点的编号为___________。 i/2，2i+1

116. 【第5章 树】设前序遍历某二叉树的序列为ABCD，中序遍历该二叉树的序列为BADC，则后序遍历该

二叉树的序列为_____________。 BDCA

117. 【第5章 树】设一棵完全二叉树的顺序存储结构中存储数据元素为ABCDEF，则该二叉树的前序遍历序

列为___________，中序遍历序列为___________，后序遍历序列为___________。 ABDECF，DBEAFC，DEBFCA

118. 【第5章 树】设一棵完全二叉树有128个结点，则该完全二叉树的深度为________，有__________个叶

子结点。 8，64

119. 【第5章 树】设二叉树中度数为0的结点数为50，度数为1的结点数为30，则该二叉树中总共有_______个结点数。 129

120. 【第5章 树】设二叉树中结点的两个指针域分别为lchild和rchild，则判断指针变量p所指向的结点为叶子结点的条件是_____________________________________________。 p->lchild==0&&p->rchild==0

121. 【第6章 特殊树】设哈夫曼树中共有n个结点，则该哈夫曼树中有________个度数为1的结点。 0

122. 【第7章 图】设有向图G中有n个顶点e条有向边，所有的顶点入度数之和为d，则e和d的关系为

_________。

e=d

123. 【第7章 图】设无向图对应的邻接矩阵为A，则A中第i上非0元素的个数_________第i列上非0元素

的个数（填等于，大于或小于）。 等于

124. 【第7章 图】在图的邻接表中用顺序存储结构存储表头结点的优点是____________________。 可以随机访问到任一个顶点的简单链表

125. 【第8章 图的应用】设有向图G中有向边的集合E={<1，2>，<2，3>，<1，4>，<4，2>，<4，3>}，则

该图的一种拓扑序列为____________________。 (1，4，3，2)

126. 【第8章 图的应用】设有向图G的二元组形式表示为G =（D，R），D={1，2，3，4，5}，R={r}，r={<1,2>，<2,4>，<4,5>，<1,3>，<3,2>，<3,5>}，则给出该图的一种拓扑排序序列__________。 (1，3，2，4，5)

127. 【第9章 查找】向一棵B_树插入元素的过程中，若最终引起树根结点的分裂，则新树比原树的高度

___________。 增加1

128. 【第9章 查找】为了能有效地应用HASH查找技术，必须解决的两个问题是____________________和

__________________________。

构造一个好的HASH函数，确定解决冲突的方法

129. 【第9章 查找】设查找表中有100个元素，如果用二分法查找方法查找数据元素X，则最多需要比较

________次就可以断定数据元素X是否在查找表中。 7

130. 【第9章 查找】散列表中解决冲突的两种方法是_____________和_____________。 开放定址法，链地址法

131. 【第10章 排序】在堆排序的过程中，对任一分支结点进行筛运算的时间复杂度为________，整个堆排

序过程的时间复杂度为________。 O（log2n）、O(nlog2n);

132. 【第10章 排序】设有n个无序的记录关键字，则直接插入排序的时间复杂度为________，快速排序的

平均时间复杂度为_________。 O(n2)，O(nlog2n)

133.【第10章 排序】在快速排序、堆排序、归并排序中，_________排序是稳定的。 归并排序

134. 【第10章 排序】快速排序的最坏时间复杂度为___________，平均时间复杂度为__________。 O(n2),

135. 【第10章 排序】中序遍历二叉排序树所得到的序列是___________序列（填有序或无序）。 有序

136. 【第10章 排序】快速排序算法的空间复杂度平均情况下为__________，最坏的情况下为__________。 O(nlogn) , O(n log n)。

137.【第10章 排序】设一组初始记录关键字序列为(20，18，22，16，30，19)，则以20为中轴的一趟快速排序结果为______________________________。 (19,18,16,20,30,22)

138. 【第10章 排序】设一组初始记录关键字为(72，73，71，23，94，16，5)，则以记录关键字72为基准的

一趟快速排序结果为___________________________。 (5,16,71,23,72,94,73)

139. 【第10章 排序】设一组初始记录关键字序列为(55，63，44，38，75，80，31，56)，则利用筛选法建

立的初始堆为___________________________。 80、75、50、56、63、44、31、38

140. 【第10章 排序】简单选择排序和直接插入排序算法的平均时间复杂度为___________。

O(n2)

【第2章 线性表】

设计在单链表中删除值相同的多余结点的算法。(提示：用双重循环)（可以只填写关键的类

型定义及函数定义，其他简答题也是如此）

typedef int datatype; typedef struct node {datatype data; struct node *next;}lklist; void del(lklist *&head)

142. 【第3章 集合矩阵广义表】

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

存储结构表示。（仅填关键类型定义及函数）

typedef struct node {int data; struct node *next;}lklist; 󰀀󰀀void interse(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;} 󰀀󰀀} 󰀀󰀀}

143.【第5章 树】

设计在链式存储结构上交换二叉树中所有结点左右子树的算法。（提示：用递归）

typedef struct node {int data; struct node *lchild,*rchild;} bitree;󰀀 void sbitree(bitree *bt)󰀀 {󰀀 bitree *p;󰀀 if(bt==0) return;󰀀 sbitree(bt->lchild); sbitree(bt->rchild);󰀀 p=bt->lchild; bt->lchild=bt->rchild; bt->rchild=p;󰀀}

144. 【第6章 特殊树】

向小根堆中加入数据4, 2, 5, 8, 3时，每加入一个数据后堆的变化。（可以用画图的办法，然后

再表示成广义表）。

4󰀀2,4󰀀2,4,5󰀀2,4,5,8󰀀2,3,5,8,4

145. 【第7章 图】

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

typedef struct {int vertex[m]; int edge[m][m];}gadjmatrix;󰀀 typedef struct node1{int info;int adjvertex; struct node1 *nextarc;}glinklistnode;󰀀 typedef struct node2{int vertexinfo;glinklistnode *firstarc;}glinkheadnode;󰀀 void adjmatrixtoadjlist(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;󰀀 }

146.

【第8章 图的应用】

已知一个图的顶点集V和边集E分别为：V={1,2,3,4,5,6,7}; E={(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15,

(3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25};

用克鲁斯卡尔算法得到最小生成树，试写出在最小生成树中依次得到的各条边。

(1,2)3, (4,6)4, (1,3)5, (1,4)8, (2,5)10, (4,7)20

147. 【第9章 查找】

设计在顺序有序表中实现二分查找的算法。

struct record {int key; int others;};󰀀 int bih(struct record r[ ], int k)󰀀 {󰀀 int low=0,mid,high=n-1;󰀀 while(low<=high)󰀀 {󰀀 mid=(low+high)/2;󰀀 if(r[mid].key==k) return(mid+1); else if(r[mid].key>k) high=mid-1; else low=mid+1;󰀀 }󰀀 return(0);󰀀}

148.【第10章 排序】

已知序列（10，18，4，3，6，12，1，9，18，8）请用快速排序写出每一趟排序的结果。

第一趟：[10,18][3,4][6,13][1,9][8,18]󰀀󰀀第二趟：[3,4,10,18，][1,6,9,12][8,18]󰀀󰀀第三趟：[3,4,10,18,][1,6,8,9,12,18]󰀀󰀀第四趟：[1,3,4,6,8,9,10,12,18,18]