以下为《-学年二学期数据结构期末考试试卷(A卷)》的无排版文字预览,完整格式请下载
下载前请仔细阅读文字预览以及下方图片预览。图片预览是什么样的,下载的文档就是什么样的。
课程代码: 座位号:
新疆大学2012-2013学年度第二学期期末考试
《数据结构》试卷
姓名: 学号: 专业:
学院: 班级:
2013年7月
题号
一
二
三
四
五
六
七
总分
得分
第一部分 选择题(共 分)
评卷人
得分
一、单选题(共13小题,每选项1分,共20分)
1.设单某某中指针P指着结点M,指针f指着将要插入的新结点X,问:
(1)X插在链表中两个数据元素M和N之间时,只要先修改( ),后修改( )即可。
(2)当X插在链表中最后一个结点M之后时,只要先修改( ),后修改( )即可。
供选择的答案:
(1):
A. p→link=f; B. p→link=p→link→link; C. p→link=f→link;
D. f→link=p→link; E. f→link=NIL; F. f→link=p;
(2):
A. f→link=p; B. f→link=p→link; C. p→link=f;
D. p→link=f→link; E. f=NIL;
【 】【 】【 】【 】
2.一个栈的输入序列为1 2 3 4 5,则下列序列中不可能是栈的输出序列的是【 】。
A. 2 3 4 1 5 B. 5 4 1 3 2 C. 2 3 1 4 5 D. 1 5 4 3 2
3.设有一表示算术表达式的二叉树(见下图),它所表示的算术表达式是 【 】
A. A*B+C/(D*E)+(F-G) B. (A*B+C)/(D*E)+(F-G)
C. (A*B+C)/(D*E+(F-G)) D. A*B+C/D*E+F-G
4.若一棵二叉树具有10个度为2的结点,5个度为1的结点,则度为0的结点个数是 【 】
A.9??????????? B.11???????? C.15?????? D.不确定
5.在一棵高度为k的满二叉树中,结点总数为 【 】
A.2k-1 B.2k C.2k-1 D.(log2k(+1
6.对二叉树的结点从1开始进行连续编号,要求每个结点的编号大于其左、右孩子的编号,同一结点的左右孩子中,其左孩子的编号小于其右孩子的编号,可采用( )次序的遍历实现编号。
【 】
A.先序 B. 中序 C. 后序 D. 从根开始按层次遍历
7.二叉树的先序遍历和中序遍历如下: 先序遍历:EFHIGJK;中序遍历: HFIEJKG 。该二叉树根的右子树的根是: 【 】
内容过长,仅展示头部和尾部部分文字预览,全文请查看图片预览。 ??????? ??????????_情况下最不利于发挥其长处,在_??????????????????? __情况下最易发挥其长处。
6. 动态查找表和静态查找表的重要区别在于前者包某某__________和__________运算,而后者不包含这两种运算。
评卷人
得分
四、简答题(共4小题,每小题5分,共20分)
1.用三元组表示下面稀疏矩阵的转置矩阵
0 1 0 0 0
M= 2 0 0 0 3
0 0 4 0 0
0 0 0 5 0
2.已知一棵二叉树的前序遍历序列为:ABDECF,中序遍历序列为:DBEAFC。请完成:
(1)构造出这棵二叉树;
(2)写出这棵二叉树的后序遍历序列。
3.对如下图所示的有向图,试给出:
(1)邻接矩阵; (2)邻接表; (3)逆邻接表; (4)强连通分量;
(5)从①出发的深度优先遍历序列; (6)从⑥出发的广度优先遍历序列。
4.假定对有序表:(3,4,5,7,24,30,42,54,63,72,87,95)进行折半查找,试回答下列问题:
(1).画出描述折半查找过程的判定树;
(2).若查找元素54,需依次与那些元素比较?
(3).若查找元素90,需依次与那些元素比较?
评卷人
得分
五、计算题(共2小题,每小题10分,共20分)
1.若对序列(tang,deng,an,wan,shi,bai,fang,liu)按字典顺序进行排序,分别给出:
(1)冒泡排序第一趟的结果;
(2)初始步长为4得希尔排序第一趟的结果;
(3)以第一个元素为分界元素的快速排序第一趟的结果;
(4)堆排序时的初始堆。
2.设哈希(Hash)表的地址范围为0~17,哈希函数为:H (K)=K MOD 16, K为关键字,用线性探测法处理冲突,输入关键字序列: (10,24,32,17,31,30,46,47,40,63,49)造出哈希表,试回答下列问题:(1) 画出哈希表示意图;
(2) 若查找关键字63,需要依次与哪些关键字比较?
(3) 若查找关键字60,需要依次与哪些关键字比较?
(4) 假定每个关键字的查找概率相等,求查找成功时的平均查找长度。
评卷人
得分
六、程序填空(共1小题,每空2分,共10分)
阅读下列程序,该程序是在单某某中删除一个结点的算法,在空出的地方填上正确的语句。
void demo (LinkList head, ListNode *p)
//head 是带头结点的单某某,删除P指向的结点
{
ListNode *q=head;
while(q!=NULL && )
;
if(q== )
printf(“*p not in List”);
;
;
}
评卷人
得分
七、程序设计(共1小题,共10分)
已知线性表中的元素按递增顺序排序,并以带表头结点的单某某作存储结构,试写算法,删除表中所有值大于min,且小于max元素。
[文章尾部最后300字内容到此结束,中间部分内容请查看底下的图片预览]
以上为《-学年二学期数据结构期末考试试卷(A卷)》的无排版文字预览,完整格式请下载
下载前请仔细阅读上面文字预览以及下方图片预览。图片预览是什么样的,下载的文档就是什么样的。