-学年二学期数据结构期末考试试卷(A卷)

本文由用户“年轻修炼手册”分享发布 更新时间:2022-03-31 21:54:53 举报文档

以下为《-学年二学期数据结构期末考试试卷(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卷)》的无排版文字预览,完整格式请下载

下载前请仔细阅读上面文字预览以及下方图片预览。图片预览是什么样的,下载的文档就是什么样的。

图片预览