数据结构期末考试题28
兰州商学院吧-给领导的感谢信
：
专
业
：
姓
得 分
评卷人
一、判断题：（共10分，每题1分）
3.
一个序列中有10000个元素，若只想得到其中前10个最小元素，最好采用_______方法
A.快速排序 B.堆排序
封密
C.插入排序 D.二路归并排序
4.队和栈的主要区别是___________
A.逻辑结构不同
C.所包含的运算个数不同
A.（a,(b,c)）
B.存储结构不同
D.限定插入和删除的位置不同
C.((a),b,c) D.((a,b,c))
级
1.字符串是一种非线性结构。（ ）
2.哈希的查找无需进行关键字的比较。（ ）
3.队列是一种插入和删除操作在表的一端进行的线性表。（ ）
4.若频繁地对线性表进行插入和删除操作，该线性表采用链式存储结构更合适。（ ）
5.稀疏矩阵中0元素的分布有规律，因此可以采用三元组方法进行压缩存储。（ ）
班
5. 已知广义表的表头为a，表尾为(b,c)，则此广义表为___________
B.（a,b,c）
6.假定一个顺序队列的队首和队尾指针分别为front和rear，存放该队列的数
组长度为N，则判断队空的条件为________
A.（front+1）% N ==
rear B．（rear+1）% N == front
C．front ==
0 D．front == rear
7．在一个单链表HL中，若要向表头插入一个由指针p指向的结点，则执行 ________
= p;p->next = HL;
C.p->next = HL;p = HL;
B.p->next = HL;HL = p;
D.p->next = HL->next;HL->next = p;
6.
若线性表采
用顺序存储结构，每个数据元素占用4个存储单元，第12个数据元素的存储地
址为144，则第1个数
据元素的存储地址是101。（ ）
7.无向完全图的边的个数最大值为n(n-1)。（
）
8.数组是向量推广。（ ）
9.二叉排序树在进行结点的插入后仍是二叉排序树。（ ）
10.要将指针p得到它所指的结点的下一个结点的数据域值是执行语句p=p->next。（
）
得 分
评卷人
8．一个无向连通图的生成树是含有该连通图的全部项点的_______。
A.极小连通子图 B.极小子图
C.极大连通子图
D.极大子图
9．在一个单链表HL中，若要在指针q所指结点的后面插入一个由指针p所指向的结点
，则
执行____。
二、填空题：（共20分，每空2分）
1.线性表可以在 _______位置进行插入，栈可以在_____位置进行插入，队列可以在__
___位置
进行插入。
2.有n各结点的二叉树的最大高度为________,最小高度为___________。
3.在栈的顺序实现中，栈顶指针top，栈为空条件______________。
4.
某带头结点的单链表的头指针head，判定该单链表非空的条件________________。
5. 设一行优先顺序存储的数组A[5][6]，A[0][0]的地址为1100，且每个元素占2
个存储单元，
则A[2][3]的地址为_____________。
6．有向图所有结点度的和等于他的_______和值。
7．若图的邻接矩阵是对称矩阵，则该图一定是____________。
A.
q一>next=p一>next；p一>next=q；C.
q一>next=p一>next；p一>next=q；
B.
p一>next=q一>next；q=p； D.
p一>next=q一>next；q一>next=p；
10．设散列表长m=14,散列函数H（K）=K％11，已知表中已有4个结点：r(15)=4;
r(38)=5;
r(61)=6;r(84)=7，其他地址为空，如用二次探测再散列处理冲突，
关键字为49的结点地址是
________。
A 8
C 5
B 3
D 9
三、选择题：（共20分，每题2分，）
得 分
评卷人
1. 图的深度优先遍历类似于二叉树的_______。
A.先序遍历
B.中序遍历
得分
得
分
评卷人
评卷人
C.后序遍历 D.层次遍历
2.线性表若采用链表存储结构时，要求内存中可用存储单元的地址_________
A.必须是连续的
C.一定是不连续的
B.部分地址必须是连续的
D.连续不连续都可以
四、应用题（30分）
1．已知稀疏矩阵如下，请写出该稀疏矩阵三元组表示。（6分）
第 1 页 共 3 页
1
4
2
3
5
2、下图中给出由7个顶点组成的无向图。从顶点1出发，写出对它进
行深度优先遍历得到的
顶点序列，进行广度优先遍历得到的顶点序列，画出该图的邻接表。（6分）
3、请画出下图中的极大连通子图。（6分）
6
4、写出{23，12，09，67，43，32，20，18，3}按直接插入排序、直接选择排序的第一、第
二
趟排序结果。（12分）
直接插入排序：
1趟：
2趟：
直接选择排序：
1趟：
2趟：
五．程序题（20分）
1．算法填空：完成计算二叉树叶子结点的算法。（每空2分，共10分）
Void
midtravel(struct treenode *bt)
{struct
treenode *p,*a[n];
int top= - 1,true
=1, j =0;
while(true)
{ p=bt;
while(p != null)
{ top + +;
___________;
p=________} if
(top != -1)
{ p=a[top];
第 2 页 共 3 页
top --
printf(“%c”,p->data);
if (p->left = = null )&&__________
______________;
p=p->right;}
Else true
= 0; }
Printf(“%d”,_______);}
2、阅读下列算法，并回答下列问题：（10分）
完善程序,并回答该算法完成什么功能？算法中r[n+1]的作用是什么？
void
sort (elemtype r[],int n)
{int k,i;
for(k=n-1;k>=1;k- -)
if(r[k]>r[k+1])
{
r[n+1]=r[k];
for(i=k+1;r[i]
;}
}}
第 3 页 共 3 页
：
专
业
：
姓
得 分
评卷人
一、判断题：（共10分，每题1分）
3.
一个序列中有10000个元素，若只想得到其中前10个最小元素，最好采用_______方法
A.快速排序 B.堆排序
封密
C.插入排序 D.二路归并排序
4.队和栈的主要区别是___________
A.逻辑结构不同
C.所包含的运算个数不同
A.（a,(b,c)）
B.存储结构不同
D.限定插入和删除的位置不同
C.((a),b,c) D.((a,b,c))
级
1.字符串是一种非线性结构。（ ）
2.哈希的查找无需进行关键字的比较。（ ）
3.队列是一种插入和删除操作在表的一端进行的线性表。（ ）
4.若频繁地对线性表进行插入和删除操作，该线性表采用链式存储结构更合适。（ ）
5.稀疏矩阵中0元素的分布有规律，因此可以采用三元组方法进行压缩存储。（ ）
班
5. 已知广义表的表头为a，表尾为(b,c)，则此广义表为___________
B.（a,b,c）
6.假定一个顺序队列的队首和队尾指针分别为front和rear，存放该队列的数
组长度为N，则判断队空的条件为________
A.（front+1）% N ==
rear B．（rear+1）% N == front
C．front ==
0 D．front == rear
7．在一个单链表HL中，若要向表头插入一个由指针p指向的结点，则执行 ________
= p;p->next = HL;
C.p->next = HL;p = HL;
B.p->next = HL;HL = p;
D.p->next = HL->next;HL->next = p;
6.
若线性表采
用顺序存储结构，每个数据元素占用4个存储单元，第12个数据元素的存储地
址为144，则第1个数
据元素的存储地址是101。（ ）
7.无向完全图的边的个数最大值为n(n-1)。（
）
8.数组是向量推广。（ ）
9.二叉排序树在进行结点的插入后仍是二叉排序树。（ ）
10.要将指针p得到它所指的结点的下一个结点的数据域值是执行语句p=p->next。（
）
得 分
评卷人
8．一个无向连通图的生成树是含有该连通图的全部项点的_______。
A.极小连通子图 B.极小子图
C.极大连通子图
D.极大子图
9．在一个单链表HL中，若要在指针q所指结点的后面插入一个由指针p所指向的结点
，则
执行____。
二、填空题：（共20分，每空2分）
1.线性表可以在 _______位置进行插入，栈可以在_____位置进行插入，队列可以在__
___位置
进行插入。
2.有n各结点的二叉树的最大高度为________,最小高度为___________。
3.在栈的顺序实现中，栈顶指针top，栈为空条件______________。
4.
某带头结点的单链表的头指针head，判定该单链表非空的条件________________。
5. 设一行优先顺序存储的数组A[5][6]，A[0][0]的地址为1100，且每个元素占2
个存储单元，
则A[2][3]的地址为_____________。
6．有向图所有结点度的和等于他的_______和值。
7．若图的邻接矩阵是对称矩阵，则该图一定是____________。
A.
q一>next=p一>next；p一>next=q；C.
q一>next=p一>next；p一>next=q；
B.
p一>next=q一>next；q=p； D.
p一>next=q一>next；q一>next=p；
10．设散列表长m=14,散列函数H（K）=K％11，已知表中已有4个结点：r(15)=4;
r(38)=5;
r(61)=6;r(84)=7，其他地址为空，如用二次探测再散列处理冲突，
关键字为49的结点地址是
________。
A 8
C 5
B 3
D 9
三、选择题：（共20分，每题2分，）
得 分
评卷人
1. 图的深度优先遍历类似于二叉树的_______。
A.先序遍历
B.中序遍历
得分
得
分
评卷人
评卷人
C.后序遍历 D.层次遍历
2.线性表若采用链表存储结构时，要求内存中可用存储单元的地址_________
A.必须是连续的
C.一定是不连续的
B.部分地址必须是连续的
D.连续不连续都可以
四、应用题（30分）
1．已知稀疏矩阵如下，请写出该稀疏矩阵三元组表示。（6分）
第 1 页 共 3 页
1
4
2
3
5
2、下图中给出由7个顶点组成的无向图。从顶点1出发，写出对它进
行深度优先遍历得到的
顶点序列，进行广度优先遍历得到的顶点序列，画出该图的邻接表。（6分）
3、请画出下图中的极大连通子图。（6分）
6
4、写出{23，12，09，67，43，32，20，18，3}按直接插入排序、直接选择排序的第一、第
二
趟排序结果。（12分）
直接插入排序：
1趟：
2趟：
直接选择排序：
1趟：
2趟：
五．程序题（20分）
1．算法填空：完成计算二叉树叶子结点的算法。（每空2分，共10分）
Void
midtravel(struct treenode *bt)
{struct
treenode *p,*a[n];
int top= - 1,true
=1, j =0;
while(true)
{ p=bt;
while(p != null)
{ top + +;
___________;
p=________} if
(top != -1)
{ p=a[top];
第 2 页 共 3 页
top --
printf(“%c”,p->data);
if (p->left = = null )&&__________
______________;
p=p->right;}
Else true
= 0; }
Printf(“%d”,_______);}
2、阅读下列算法，并回答下列问题：（10分）
完善程序,并回答该算法完成什么功能？算法中r[n+1]的作用是什么？
void
sort (elemtype r[],int n)
{int k,i;
for(k=n-1;k>=1;k- -)
if(r[k]>r[k+1])
{
r[n+1]=r[k];
for(i=k+1;r[i]
;}
}}
第 3 页 共 3 页