2005年－2006学年第二学期“数据结构”考试试题（A）
姓名
学号序号_答案隐藏
班号
要求：所有的题目的解答均写在答题纸上（每张答题纸上要写清楚姓名、班号和学号），需写清楚题目的序号。每张答题纸都要写上姓名和序号。
一、单项选择题（每小题2分，共20分）
1．数据的运算a。
A效率与采用何种存储结构有关
B是根据存储结构来定义的
C有算术运算和关系运算两大类
D必须用程序设计语言来描述
答：A。
2链表不具备的特点是a。
A可随机访问任一结点
B插入删除不需要移动元素
C不必事先估计存储空间
D所需空间与其长度成正比
答：参见本节要点3。本题答案为：A。
3在顺序表中删除一个元素的时间复杂度为c。
AO1
BOlog2

CO

DO
2
答：C。
4．以下线性表的存储结构中具有随机存取功能的是d。
A不带头结点的单链表
B带头结点的单链表
C循环双链表
D顺序表
解D。
5一个栈的进栈序列是a，b，c，d，e，则栈的不可能的输出序列是c。
fAedcba
Bdecba
Cdceab
Dabcde
答：C。
6循环队列qu的队空条件是d。
Aqurear1MaxSizequfro
t1MaxSize
Bqurear1MaxSizequfro
t1
Cqurear1MaxSizequfro
t
Dqurearqufro
t
答：D。
7两个串相等必有串长度相等且b。
A串的各位置字符任意
B串中各位置字符均对应相等
C两个串含有相同的字符
D两个所含字符任意
答：B。
8用直接插入排序对下面四个序列进行递增排序，元素比较次数最少的是c。
A943240908046216980
B32402146699490
C213246408069909440
D90698046213294
答：C。
9以下序列不是堆（大根或小根）的是d。
A10085987780608240201066776660402010
B10098858280
C10204060667780828598100606698821020
D10085407780
f答：D。
10以下排序方法中，b，在初始序列已基本有序的情况下，排序效率最高。
A直接选择排序
B昌泡排序
C快速排序
D堆排序
答：B。
二、填空题（每题2分，共10分）1将f1…
3转化成递归函数，其递归出口是①，递归体是②
答：①f11②f
f
1
评分标准：每空1分
2．广义表aaa的长度是4①，深度是3②。
答：43
评分标准：每空1分
3具有
个结点的二叉树采用二叉链存储结构，共有
1个空指针域。
答：
1。
4在有
个顶点的有向图中，每个顶点的度最大可达2
1
1。
答：2
1。
5外排序的基本方法是归并法。它一般要经历文件预处理①和多路归并②两个阶段。
答：产生初始归并段（或顺串）多路归并
评分标准：每空1分
三、问答r