华东交通大学 2004 — 2005 学年第 1 学期考试卷
数据结构 课程 课程类别:必修 闭卷
题号
一
二
三
四
五
六
七
八
九
总 分
分数
评卷人
一, 填空题(每空 1 分,共 20 分)
1, 现有一个程序,它能够处理气象卫星收集的数据用来预测今后两天的天气,但
是却要算上将近一个星期,故其在实践中应该来讲是没有什么意义的,不能称
其为算法,因为它违背了算法的___可行性_______。
2, 若设 L 是带表头结点的单链表的表头指针,则语句 L->next= L->next-
>next 的作用是__删除单链表的第一个结点_____。(其中 next 是节点指
针域)
3, 我国的权力机构由各级人民代表大会组成,如果将所有代表大会当作一个数据
整体,则根据我国的实际管理关系,用数据结构里面的术语,它们之间是__树
状____关系。
4, 在线性表的顺序存储实现中,假设线性表的长度为 n,则平均插入一个数据元
素平均要移动元素的次数为___n/2____________。(假设元素插入到各个位
置的概率相同)
5, 后缀表达式“4 5 * 3 2 + - 4 -”的值为___11____。(注意所有数都为 1 位
个位数)
6, 设有一个顺序栈 S,元素 s
1
, s
2
, s
3
, s
4
, s
5
, s
6
依次进栈,如果 6 个元素的出
栈顺序为 s
2
, s
3
, s
4
, s
6
, s
5
, s
1
,则顺序栈的容量至少应为___3_____。
7, 设有关键码序列(Q,H,C,Y,Q,A,M,S,R,D,F,X),要按照
关键码值递增的次序进行排序,若采用步长为 5,3,1 的 Shell 排序法,则进
行 到 步 长 为 3 之 后 , 执 行 步 长 为 1 之 前 的 结 果 是
_A,D,C,M,H,F,Q,Q,X,R,S,Y____;若采用以最后一个元素为分界元素的快速
排序法,则一趟扫描的结果是__Q,H,C,F,Q,A,M,S,R,D,X,Y_____。
8, 一个具有 567 个结点的完全二叉树,其叶子结点个数为__284__。
9, 一颗二叉树有 13 个结点,则这颗二叉树的高度最大为 ___14___,最小为__
第 1 页 共 10 页
承诺:我将严格遵守考场纪律,并知道考试违纪、作弊的严重性,承担由此引起的一切后果。
专业 班级 学号
学生签名:
承诺:我将严格遵守考场纪律,并知道考试违纪、作弊的严重性,承担由此引起的一切后果。
专业 班级 学号
学生签名: