新疆师范大学
计算机科学技术学院 2010—2011学年第一学期期末考试试卷
《数据结构》B试卷
专业 电子 班级 08-11 姓名 学号
题
快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题
号
一
二
三
四
五
总分
分值
20
20
20
20
20
100
得分
一、选择题：(请将正确
答案
八年级地理上册填图题岩土工程勘察试题省略号的作用及举例应急救援安全知识车间5s试题及答案
填入“ ”中，每题2分 共20分）
1．算法指的是（ ）
A．计算机程序 B．解决问题的计算
方法
快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载
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．一个非空广义表的表头（ ）
A．不可能是子表 B．只能是子表
C．只能是原子 D．可以是子表或原子.
6．栈的插入和删除操作在（ ）进行。
A 栈顶 B 栈底 C 任意位置 D 指定位置
7．在一棵度为3的树中,度为3的结点个数为2,度为2 的结点个数为1,则度为0的结点个数为( )
A．4 B．5 C．6 D．7
8．在含n个顶点和e条边的无向图的邻接矩阵中,零元素的个数为( )
A．e B．2e C．n2－e D．n2－2e
9．设一棵完全二叉树中有65个结点，则该完全二叉树的深度为（ ）。
(A) 8 (B) 7 (C) 6 (D) 5
10．在一个单链表中,若q所指结点是p所指结点的前驱结点,若在q与p之间插入一个s所指的结点,则执行( )。
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;
二、填空题 (每小题2分,共20分)
1．数据结构是研究从解决现实问题中抽象出来的数据如何在计算机系统中很好地 表示、 和 的方法。
⒊ 带头结点的单向链表L为空的判定条件是 。
4．栈和队列是两种特殊的线性表，栈的特点是 。
5.栈的典型应用有 和 。
6．稀疏矩阵一般的压缩存储方法有两种，即 和十字链表。
7．已知一棵完全二叉树的第5层有3个结点，其叶子结点数是 。
8. 一个栈的入栈序列是12345，则栈的输出序列是 。
9.深度为K的完全二叉树至少有 个结点。
10. 后缀算式9 2 3 +- 10 2 / -的值为______。中缀算式（3+4X）-2Y/3对应的后缀算式为_______________________________。
三、按题意解答如下问题：(每小题10分,共20分)
1、已知稀疏矩阵A如下图所示：
1). 写出它的三元组线性表；
2). 给出它的顺序存储表示；
3)．给出它的转置矩阵的三元组和顺序存储表示。
A =
2.什么是满二叉树？什么是完全二叉树？
四、
阅读程序，简述以下算法的功能(每题10分，共20分）
1．HS是指向一个链栈的指针变量，则以下函数的功能是： 。
void ClearStack(SNode*& HS)
{
SNode *cp, *np;
cp=HS; //给cp指针赋初值，使之指向栈顶结点
while(cp!=NULL)
{ //从栈顶到栈底依次删除每个结点
np=cp->next;
delete cp;
cp=np;
}
HS=NULL; //置链栈为空
}
2．BT指向一个二叉树的指针变量，则以下函数的功能是： 。
bool FindBTree(BTreeNode* BT, ElemType& x)
{
if(BT==NULL) return false; //树为空返回假
else {
if(BT->data==x) { //树根结点的值等于x则由x带回结点值并返回真
x=BT->data; return true;
}
else {
//向左子树查找若成功则继续返回真
if(FindBTree(BT->left,x)) return true;
//向右子树查找若成功则继续返回真
if(FindBTree(BT->right,x)) return true;
//左、右子树查找均失败则返回假
return false;
}
}
}
五、程序填空（每题5分，共10分）
.1．以下程序是清除一棵二叉树，使之变为一棵空树。请在下划线处填空使它完善（10分）。
void ClearBTree(BTreeNode*& BT)
{
if(BT!= ) {
(BT->left); //清除左子树
ClearBTree( ); //清除右子树
BT; //释放根结点
BT=NULL; //置根指针为空
}
}
2．以下程序是从树中查找值为item的结点时，若存在该结点则由item带回它的完整值并返回true，否则返回false表示查找失败。请在下划线处填空使它完善（10分）。
bool FindGTree(GTreeNode* GT, ElemType& item)
{
if(GT== ) return false; //树空返回假
else {
if(GT->data==item) { //带回结点值并返回真
item=GT->data; return ;
}
for(int i=0; i
t[i],item)) return ;
return false; //查找不成功返回假
}
}
六、编程题 (1小题共10分)。
1．从一个单链表中查找出所有元素的最大值，改自由函数返回，若单链表为空，则显示出错信息并停止运行。
浙公网安备 33021202002483