数据结构试题及答案(2).doc

(完整word版)数据结构试题及答案(2)
数据结构试题 

一、 单选题（每题 2 分，共20分）
1. 1.     对一个算法的评价，不包括如下（ B ）方面的内容。
A．健壮性和可读性 B．并行性 C．正确性 D．时空复杂度
2. 2.     在带有头结点的单链表HL中，要向表头插入一个由指针p指向的结点，则执行( A )。
A. p->next=HL->next; HL->next=p; B. p->next=HL; HL=p;
C. p->next=HL; p=HL; D. HL=p; p->next=HL;
3. 3.     对线性表，在下列哪种情况下应当采用链表表示？( B )
A.经常需要随机地存取元素 B.经常需要进行插入和删除操作
C.表中元素需要占据一片连续的存储空间 D.表中元素的个数不变
4. 4.     一个栈的输入序列为1 2 3，则下列序列中不可能是栈的输出序列的是( C )
A. 2 3 1 B. 3 2 1
C. 3 1 2 D. 1 2 3
5. 5.     AOV网是一种（ D ）。
A．有向图 B．无向图 C．无向无环图 D．有向无环图
6. 6.     采用开放定址法处理散列表的冲突时，其平均查找长度（ B ）。
A．低于链接法处理冲突 B. 高于链接法处理冲突
C．与链接法处理冲突相同 D．高于二分查找
7. 7.     若需要利用形参直接访问实参时，应将形参变量说明为（ D ）参数。
A．值 B．函数 C．指针 D．引用
8. 8.     在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点都具有相同的（ A ）。
A．行号 B．列号 C．元素值 D．非零元素个数
9. 9.     快速排序在最坏情况下的时间复杂度为（ D ）。
A．O(log2n) B．O(nlog2n) C．O(n) D．O(n2)
10. 10. 从二叉搜索树中查找一个元素时，其时间复杂度大致为( C )。
A. O(n) B. O(1) C. O(log2n) D. O(n2)
二、运算题（每题 6 分，共24分）
1. 1. 数据结构是指数据及其相互之间的_对应关系(联系)。当结点之间存在M对N（M：N）的联系时，称这种结构为图（或图结构）。
2. 2.队列的插入操作是在队列的__队尾___进行，删除操作是在队列的_对头_进行。
3. 3.  当用长度为N的数组顺序存储一个栈时，假定用top==N表示栈空，则表示栈满的条件是_top==0__。
4. 4.   对于一个长度为n的单链存储的线性表，在表头插入元素的时间复杂度为_O(1)_，在表尾插入元素的时间复杂度为__O(n)_。
5. 5.  设W为一个二维数组，其每个数据元素占用4个字节，行下标i从0到7 ，列下标j从0到3 ，则二维数组W的数据元素共占用＿128＿个字节。W中第6 行的元素和第4 列的元素共占用＿44___个字节。若按行顺序存放二维数组W，其起始地址为100，则二维数组元素W[6，3]的起始地址为＿108__。
6. 6.  广义表A= (a,(a,b),((a,b),c)),则它的深度为__3___，它的长度为__3____。
7. 7. 二叉树是指度为2的__有序__树。一棵结点数为N的二叉树，其所有结点的度的总和是__n-1__。
8. 8. 对一棵二叉搜索树进行中序遍历时，得到的结点序列是一个__有序序列__。对一棵由算术表达式组成的二叉语法树进行后序遍历得到的结点序列是该算术表达式的__后缀表达式_。
9. 9.对于一棵具有n个结点的二叉树，用二叉链表存储时，其指针总数为___2n____个，其中__n-1__个用于指向孩子，__n+1__个指针是空闲的。
10. 10.若对一棵完全二叉树从0开始进行结点的编号，并按此编号把它顺序存储到一维数组A中，即编号为0的结点存储到A[0]中。其余类推，则A[ i ]元素的左孩子元素为___2i+1,右孩子元素为__2i+2__，双亲元素为_(i-1)/2__。
11. 11.在线性表的散列存储中，处理冲突的常用方法有_开放地址法__和__链接法__两种。
12. 12.当待排序的记录数较大，排序码较随机且对稳定性不作要求时，宜采用__快速___排序；当待排序的记录数较大，存储空间允许且要求排序是稳定时，宜采用__归并__排序。

三、运算题（每题6分，共24分）
1. 1. 已知一个6´5稀疏矩阵如下所示，

试：（1）写出它的三元组线性表；（2）给出三元组线性表的顺序存储表示。
2. 2. 设有一个输入数据的序列是 { 46, 25, 78, 62, 12, 80 }, 试画出从空树起，逐个输入各个数据而生成的二叉搜索树。
3. 3. 对于图6所示的有向图若存储它采用邻接表，并且每个顶点邻接表中的边结点都是按照终点序号从小到大的次序链接的，试写出：
(1) 从顶点①出发进行深度优先搜索所得到的深度优先生成树；
(2) 从顶点②出发进行广度优先搜索所得到的广度优先生成树；
4. 4. 已知一个图的顶点集V和边集E分别为：
图6

V={1,2,3,4,5,6,7};
E={<2,1>,<3,2>,<3,6>,<4,3>,<4,5>,<4,6>,<5,1>,<5,7>,<6,1>,<6,2>,<6,5>};
若存储它采用邻接表，并且每个顶点邻接表中的边结点都是按照终点序号从小到大的次序链接的，按主教材中介绍的拓朴排序算法进行排序，试给出得到的拓朴排序的序列。

四、阅读算法（每题7分，共14分）
1. 1. int Prime(int n)
{
int i=1;
int x=(int) sqrt(n);
while (++i<=x)
if (n%i==0) break;
if (i>x) return 1;
else return 0;
}
(1) (1) 指出该算法的功能；
(2) (2)  该算法的时间复杂度是多少？
2. 2.  写出下述算法的功能：
void AJ(adjlist GL, int i, int n)
{
Queue Q;
InitQueue(Q);
cout<<i<<' ';
visited[i]=true;
QInsert(Q,i);
while(!QueueEmpty(Q)) {
int k=QDelete(Q);
edgenode* p=GL[k];
while(p!=NULL)
{
int j=p->adjvex;
if(!visited[j])
{
cout<<j<<' ';
visited[j]=true;
QInsert(Q,j);
}
p=p->next;
}
}
}

五、算法填空（共8分）
如下为二分查找的非递归算法，试将其填写完整。
Int Binsch(ElemType A[ ],int n,KeyType K)
{
int low=0;
int high=n-1;
while (low<=high)
{
int mid=_______________________________；
if (K==A[mid].key) return mid; //查找成功，返回元素的下标
else if (K<[mid].key)
______________________________________; //在左子表上继续查找
else __________________________________; //在右子表上继续查找
}
return -1; //查找失败，返回-1
}

六、编写算法（共8分）
HL是单链表的头指针，试写出删除头结点的算法。
ElemType DeleFront(LNode * & HL)

  参考答案

    三、运算题（每题6分，共24分）
1. 1.  （1） ((1,5,1),(3,2,-1),(4,5,-2),(5,1,5),(6,3,7)) (3分)
6
5
5
1
5
1
3
2
-1
4
5
-2
5
1
5
6
3
7
（2）三元组线性表的顺序存储表示如图7示。
2. 2. 如图8所示。
3. 3.  DFS：‚ƒ„…
BFS：‚ƒ„…
4. 4. 拓朴排序为： 4 3 6 5 7 2 1
图7
图8

四、阅读算法（每题7分，共14分）
1. 1.  (1) 判断n是否是素数（或质数）
（2）O（）
2. 2. 功能为：从初始点vi出发广度优先搜索由邻接表GL所表示的图。
五、算法填空（8 分）
(low+high)/2 high=mid-1 low=mid+1
六、编写算法（8分）
ElemType DeleFront(LNode * & HL)
{
if (HL==NULL){
cerr<<"空表"<<endl;
exit(1);
}
LNode* p=HL;
HL=HL->next;
ElemType temp=p->data;
delete p;
return temp;
}

课程测试试题（ 1卷）
 一、单选题（每题 2 分，共20分）
1. 1.     栈和队列的共同特点是( A )。
A.只允许在端点处插入和删除元素
B.都是先进后出
C.都是先进先出
D.没有共同点
2. 2.     用链接方式存储的队列，在进行插入运算时( D ).
A. 仅修改头指针 　 B. 头、尾指针都要修改
C. 仅修改尾指针 D.头、尾指针可能都要修改
3. 3.     以下数据结构中哪一个是非线性结构？( D )
A. 队列 　　 B. 栈 C. 线性表 　　 D. 二叉树
4. 4.     设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每个元素占一个空间，问A[3][3](10)存放在什么位置？脚注(10)表示用10进制表示。( C )
A．688 B．678 C．692 D．696
5. 5.     树最适合用来表示( C )。
A.有序数据元素 B.无序数据元素
C.元素之间具有分支层次关系的数据 D.元素之间无联系的数据
6. 6.     二叉树的第k层的结点数最多为( D ).
A．2k-1 B.2K+1 C.2K-1 　　　D. 2k-1
7. 7.     若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二分查找，则查找A［3］的比较序列的下标依次为( D )
A. 1，2，3 B. 9，5，2，3
C. 9，5，3 D. 9，4，2，3
8. 8.     对n个记录的文件进行快速排序，所需要的辅助存储空间大致为( C )
A. O（1） 　　B. O（n）　　 C. O（1og2n） D. O（n2）
9. 9.     对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用H（K）=K %9作为散列函数，则散列地址为1的元素有（ D ）个，
A．1 B．2 C．3 D．4
10. 10. 设有6个结点的无向图，该图至少应有( A )条边才能确保是一个连通图。
A.5 B.6 C.7 D.8

二、填空题（每空1分，共26分）
1. 1.  通常从四个方面评价算法的质量：_正确性_、_易读性_、_强壮性_和_高效率_。
2. 2.一个算法的时间复杂度为(n3+n2log2n+14n)/n2，其数量级表示为_ O(n)_。
3. 3.  假定一棵树的广义表表示为A（C，D（E，F，G），H（I，J）），则树中所含的结点数为_9__个，树的深度为_3_，树的度为_3_。
4. 4.   后缀算式9 2 3 +- 10 2 / -的值为__-1__。中缀算式（3+4X）-2Y/3对应的后缀算式为_ 3 4 X * + 2 Y * 3 / -_。
5. 5.  若用链表存储一棵二叉树时，每个结点除数据域外，还有指向左孩子和右孩子的两个指针。在这种存储结构中，n个结点的二叉树共有_ 2n _个指针域，其中有_ n-1_个指针域是存放了地址，有__ n+1__个指针是空指针。
6. 6.  对于一个具有n个顶点和e条边的有向图和无向图，在其对应的邻接表中，所含边结点分别有__e__个和_2e _个。
7. 7.   AOV网是一种___有向无回路___的图。
8. 8.  在一个具有n个顶点的无向完全图中，包含有__ n(n-1)/2 _条边，在一个具有n个顶点的有向完全图中，包含有_ n(n-1)_条边。
9. 9.  假定一个线性表为(12,23,74,55,63,40)，若按Key % 4条件进行划分，使得同一余数的元素成为一个子表，则得到的四个子表分别为__（12，40）__、__（ ）__、_（74） __和__（23,55，63）__。
10. 10.    向一棵B_树插入元素的过程中，若最终引起树根结点的分裂，则新树比原树的高度__增加1_。
11. 11.    在堆排序的过程中，对任一分支结点进行筛运算的时间复杂度为_ O(log2n)_，整个堆排序过程的时间复杂度为_ O(nlog2n)_。
12. 12.    在快速排序、堆排序、归并排序中， _归并_排序是稳定的。

三、运算题（每题 6 分，共24分）
1. 1.        在如下数组A中链接存储了一个线性表，表头指针为A [0].next，试写出该线性表。
A 0 1 2 3 4 5 6 7
data

60
50
78
90
34

40
next
3
5
7
2
0
4

1
2. 2.        图10

请画出图10的邻接矩阵和邻接表。
3. 3.        已知一个图的顶点集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};
用克鲁斯卡尔算法得到最小生成树，试写出在最小生成树中依次得到的各条边。
4. 4.        画出向小根堆中加入数据4, 2, 5, 8, 3时，每加入一个数据后堆的变化。

四、阅读算法（每题7分，共14分）
1. 1.     LinkList mynote(LinkList L)
{//L是不带头结点的单链表的头指针
if(L&&L->next){
q=L；L=L－>next；p=L；
S1： while(p－>next) p=p－>next；
S2： p－>next=q；q－>next=NULL；
}
return L；
}
请回答下列问题：
（1）说明语句S1的功能；
（2）说明语句组S2的功能；
（3）设链表表示的线性表为（a1,a2, …,an）,写出算法执行后的返回值所表示的线性表。
2. 2.     void ABC(BTNode * BT)
{
if BT {
ABC (BT->left);
ABC (BT->right);
cout<<BT->data<<' ';
}
}
该算法的功能是：

五、算法填空（共8分）
二叉搜索树的查找——递归算法:
bool Find(BTreeNode* BST,ElemType& item)
{
if (BST==NULL)
return false; //查找失败
else {
if (item==BST->data){
item=BST->data;//查找成功
return ___________;}
else if(item<BST->data)
return Find(______________,item);
else return Find(_______________,item);
}//if
}

六、编写算法（共8分）
统计出单链表HL中结点的值等于给定值X的结点数。
int CountX(LNode* HL,ElemType x)

  参考答案
三、运算题（每题6分，共24分）
1. 1.     线性表为：（78，50，40，60，34，90）
2. 2.     邻接矩阵：
邻接表如图11所示：

图11
3. 3.     用克鲁斯卡尔算法得到的最小生成树为：
(1,2)3, (4,6)4, (1,3)5, (1,4)8, (2,5)10, (4,7)20
4. 4.     见图12
4

4

4

4

4

2

2

2

5

5

2

8

5

2

8

3

4

5

2

8

4

3

图12
四、阅读算法（每题7分，共14分）
1. 1.     （1）查询链表的尾结点
（2）将第一个结点链接到链表的尾部，作为新的尾结点
（3）返回的线性表为（a2,a3,…,an,a1）
2. 2.     递归地后序遍历链式存储的二叉树。
五、算法填空（每空2分，共8 分）
true BST->left BST->right
一、 六、                      编写算法（8分）
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

课程测试试题（2卷）
一、单选题（每小题2分，共8分）
1、 1、在一个长度为n的顺序线性表中顺序查找值为x的元素时，查找成功时的平均查找长度（即x与元素的平均比较次数，假定查找每个元素的概率都相等）为 ( C )。
A n B n/2 C (n+1)/2 D (n-1)/2
2、 2、在一个单链表中,若q所指结点是p所指结点的前驱结点,若在q与p之间插入一个s所指的结点,则执行( D )。
A s→link=p→link; p→link=s; B p→link=s; s→link=q;
C p→link=s→link; s→link=p; D q →link=s; s→link =p;
3、 3、      栈的插入和删除操作在（ A ）进行。
A 栈顶 B 栈底 C 任意位置 D 指定位置
4、 4、      由权值分别为11，8，6，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（ B ）
A 24 B 71 C 48 D 53
二、填空题（每空1分，共32分）
5、 1、数据的逻辑结构被分为___集合____、 ___线性______ 、___树_____和___图_____四种。
6、 2、一种抽象数据类型包括_数据描述____和_操作声名___两个部分。
7、 3、在下面的数组a中链接存储着一个线性表，表头指针为a[o].next，则该线性表为_（38，56，25，60，42，74）。
a 0 1 2 3 4 5 6 7 8

60
56
42
38

74
25

4
3
7
6
2

0
1

data
next

8、 4、在以HL为表头指针的带表头附加结点的单链表和循环单链表中，判断链表为空的条件分别为_HL→next =NULL__和_ HL=HL→next _。
9、 5、用具有n个元素的一维数组存储一个循环队列，则其队首指针总是指向队首元素的_前一个位置__，该循环队列的最大长度为__ n-1__。
10、 6、当堆栈采用顺序存储结构时，栈顶元素的值可用S.stack [S.top]表示；当堆栈采用链接存储结构时，栈顶元素的值可用_HS→data _表示。
11、 7、一棵高度为5的二叉树中最少含有_5_个结点，最多含_31_个结点。
12、 8、在图的邻接表中，每个结点被称为_边结点__，通常它包含三个域：一是_邻接点域__；二是__权域___；三是__链域__。
13、 9、在一个索引文件的索引表中，每个索引项包含对应记录的_索引值域_和_开始位置域_两项数据。
14、 10、            假定一棵树的广义表表示为A（B（C，D（E，F，G），H（I，J））），则树中所含的结点数为_10__个，树的深度为__3__,树的度为_3_, 结点H的双亲结点为__B___,孩子结点为_I和J _ 。
15、 11、            在堆排序的过程中，对任一分支结点进行筛运算的时间复杂度为_O（log2n）_,整个堆排序过程的时间复杂度为_ O(nlog2n)_。
16、 12、            在对m阶的B_树插入元素的过程中，每向一个结点插入一个索引项（叶子结点中的索引项为关键字和空指针）后，若该结点的索引项数等于_ m _个，则必须把它分裂为_ m - 1__个结点。

三、运算题（每小题6分，共24分）
17、 1、已知一组记录的排序码为（46，79，56，38，40，80, 95，24），写出对其进行快速排序的每一次划分结果。

18、 2、一个线性表为B=（12，23，45，57，20，03，78，31，15，36），设散列表为HT[0..12]，散列函数为H（key）= key % 13并用线性探查法解决冲突，请画出散列表，并计算等概率情况下查找成功的平均查找长度。

19、 3、已知一棵二叉树的前序遍历的结果序列是ABECKFGHIJ，中序遍历的结果是EBCDAFHIGJ，试写出这棵二叉树的后序遍历结果。

20、 4、已知一个图的顶点集V各边集G如下：
V = {0，1，2，3，4，5，6，7，8，9}；
E = {（0，1），（0，4），（1，2），（1，7），（2，8），（3，4），（3 ，8），（5，6），（5，8），（5，9），（6，7），（7，8），（8，9）}
当它用邻接矩阵表示和邻接表表示时，分别写出从顶点V0出发按深度优先搜索遍历得到的顶点序列和按广度优先搜索遍历等到的顶点序列。
假定每个顶点邻接表中的结点是按顶点序号从大到小的次序链接的。
图
深度优先序列
广度优先序列
邻接矩阵表示时

邻接表表示时

四、阅读算法，回答问题（每小题8分，共16分）

1、假定从键盘上输入一批整数，依次为：78 63 45 30 91 34 –1，请写出输出结果。
# include < iostream.h>
# include < stdlib.h >
consst int stackmaxsize = 30;
typedef int elemtype;
struct stack {
elemtype stack [stackmaxsize];
int top;
};
# include “stack.h”
Void main ( )
{
stack a;
initstack(a);
int x;
cin >>x;
while (x! = -1) {
push (a, x );
cin >>x;
}
while (!stackempty (a))
cout <<pop (a) <<”” ;
cout <<end1;
}
该算法的输出结果为：
__________________________________________________________.

2、阅读以下二叉树操作算法，指出该算法的功能。
Template <calss type > void BinTree <Type> ：：
unknown (BinTreeNode<Type>*t) {
BinTreeNode< Type> *p =t, *temp;
if (p!=NULL) {
temp = p→leftchild;
p→leftchild = p→rightchild;
p→rightchild = temp;
unknown(p→leftchild);
undnown(p→rightchild);
}
}
该算法的功能是：________________________________

五、算法填空，在画有横线的地方填写合适的内容（10分）

对顺序存储的有序表进行二分查找的递归算法 。
int Binsch( ElemType A[ ],int low ,int high,KeyType K )
{
if (low <= high)
{
int mid = 1
if ( K= = A[ mid ].key )
return mid;
else if ( K < A[mid].key)
return 2
else
return 3
}
else
return 4

六、编写算法（10分）

编写算法，将一个结点类型为Lnode的单链表按逆序链接，即若原单链表中存储元素的次序为a1，……an-1，an，则逆序链接后变为, an，an-1，……a1。
Void contrary (Lnode * & HL)

数据结构试题（答案）

三、运算题（每小题6分，共24分）
1、
划分次序
划分结果
第一次
[38 24 40] 46 [56 80 95 79]
第二次
24 [38 40] 46 [56 80 95 79]
第三次
24 38 40 46 [56 80 95 79]
第四次
24 38 40 46 56 [80 95 79]
第五次
24 38 40 46 56 79 [80 95]
第六次
24 38 40 46 56 79 80 95

2、
0 1 2 3 4 5 6 7 8 9 10 11 12

78

15
03

57
45
20
31

23
36
12

查找成功的平均查找长度：ASL SUCC=14/10= 1.4
3、此二叉树的后序遍历结果是：EDCBIHJGFA
4、
图
深度优先序列
广度优先序列
邻接矩阵表示时
0，1，2，8，3，4，5，6，7，9
0，1，4，2，7，3，8，6，5，9
邻接表表示时
0，4，3，8，9，5，6，7，1，2
0，4，1，3，7，2，8，6，9，5
四、阅读算法，回答问题（每小题8分，共16分）
21、 1、  该算法的输入结果是：34 91 30 45 63 78
22、 2、  该算法的功能是：交换二叉树的左右子树的递归算法。
五、算法填空，在画有横线的地方填写合适的内容（10分）
1、1是：（low + high）/2;
2是： Binsch(A,low,mid–1,K);
3是： Binsch(A,mid+1,high,K);
4是： -1；
六、编写算法（10分）
根据编程情况，酌情给分。
{
Lnode *P=HL;
HL=NULL;
While (p!=null)
{
Lnode*q=p;
P=p→next;
q→next=HL;
HL=q;
}
}

课程测试试题（卷）
第一部分 选择题(30分)

一、项选择题
1．算法指的是（ D ）
A．计算机程序 B．解决问题的计算方法
C．排序算法 D．解决问题的有限运算序列
2．线性表采用链式存储时，结点的存储地址（ Ｂ ）
A．必须是不连续的 B．连续与否均可
C．必须是连续的 D．和头结点的存储地址相连续
3．将长度为n的单链表链接在长度为m的单链表之后的算法的时间复杂度为（Ｃ）
A．O（1） B．O（n） C．O（m） D．O（m+n）
4．由两个栈共享一个向量空间的好处是：（Ｂ ）
A．减少存取时间，降低下溢发生的机率
B．节省存储空间，降低上溢发生的机率
C．减少存取时间，降低上溢发生的机率
D．节省存储空间，降低下溢发生的机率
5．设数组data[m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出队操作后其头指针front值为（Ｄ）
A．front=front+1 B．front=(front+1)%(m-1)
C．front=(front-1)%m D．front=(front+1)%m
6．如下陈述中正确的是（ Ａ ）
A．串是一种特殊的线性表 B．串的长度必须大于零
C．串中元素只能是字母 D．空串就是空白串
7．若目标串的长度为n，模式串的长度为[n/3]，则执行模式匹配算法时，在最坏情况下的时间复杂度是（ Ｃ ）
A．O（） B．O（n） C．O（n2） D．O（n3）
8．一个非空广义表的表头（ Ｄ ）
A．不可能是子表 B．只能是子表
C．只能是原子 D．可以是子表或原子
9．假设以带行表的三元组表表示稀疏矩阵，则和下列行表
0
2
3
3
5
对应的稀疏矩阵是（ Ａ ）

10．在一棵度为3的树中,度为3的结点个数为2,度为2 的结点个数为1,则度为0的结点个数为( Ｃ )
A．4 B．5 C．6 D．7
11．在含n个顶点和e条边的无向图的邻接矩阵中,零元素的个数为( Ｄ )
A．e B．2e C．n2－e D．n2－2e
12．假设一个有n个顶点和e条弧的有