数据结构课程试卷1卷 苏州大学
- 格式：doc
- 大小：59.00 KB
- 文档页数：5
1
苏州大学 数据结构 课程试卷1卷（共 5 页）
考试形式：闭卷 年 月
院系 ______________ 年级 ______________ 专业 ______________
学号 ______________ 姓名 ______________ 成绩 ______________
一、填空（2分×16）
1、对于一个栈作进栈运算时，应先判别栈是否为__满______，作退栈运算时，应先判别栈
是否为____空____。
2、下面程序段的时间复杂度为_____O(mnt)_____。
for (i=0; i
3、算术表达式A*(B-C)+T/(D+E)-F/(S*H)的逆波兰式为_A?B?C?-*T?D?E?+/+F?S?H?*/-
_____________________。
4、假设以行序为主序，下三角表格的元素（i，j）对应到顺序数组的元素下标为
_________i*(i+1)+j____；若以列序为主序，则下三角表格的元素（i，j）对应到顺序数组的
元素下标________________。
5、设图G有n个顶点和e条边，当用邻接矩阵作图的存储结构时，进行深度优先搜索遍历
的时间复杂度为__________________。
6、哈希表的装填因子定义为_____________________________；直观地看，装填因子越
________，发生冲突的可能性就越小。
7、拓扑排序的方法为____________________________________________________________
_____________________________________________________________________________。
8、设F是森林，B是由F转换得到的二叉树，F中有n个非终端结点，B中右指针域为空的
结点有___________个。
9、已知一个有序表为（5，13，19，21，37，56，64，75，80，88，92），当折半查找值为
21的元素时，若采用binary_search_1方法，需_______次比较可查找成功。
10、在Dijkstra算法中，S为_________________________________________的集合，算法的
时间复杂度为____________________。
11、快速排序的最坏情况是初始序列为______已排好序或倒序__________，其时间复杂度为
___O(n2)_______。
2
二、应用题
1、将队列存储在下标范围0到（maxqueue-1）的数组中，队列满时数组留有一个空位，试
写出Queue类的定义，并给出队空和队满的条件（8分）
Queue类的定义如下：
const int maxqueue = 10;
class Queue {
public:
Queue( );
bool empty( ) const;
Error_code serve( );
Error_code append(const Queue_entry &item);
Error_code retrieve(Queue_entry &item) const;
protected:
int count;
int front, rear;
Queue_entry entry[maxqueue];
};（5分）
队空条件为(rear+1)%maxqueue=front （1.5分）
队满条件为(rear+2)%maxqueue=front （1.5分）
2、设有关键字输入序列：{haerbin，shanghai，cengdu，kunming，guangzhou，wuhan，
changchun，beijing，jinan，fuzhou，changsha，xian，nanjing，tianjin}，画出生成的二叉排
序树，求出在等查找概率情况下查找成功时的平均查找长度，并画出删除haerbin之后所得
的二叉排序树。（12分）
3
3、Prim算法求下图的最小生成树，请写出求解过程。（8分）
7
12
8
5
10
68245361215
6
1
4、将序列（100，85，40，75，80，60，65，95，82，10，20）分别调整为小顶堆（堆顶元
素取最小值）和大顶堆（堆顶元素取最大值）。请给出在初始大顶堆中将关键字最大的记录
与序列中最后一个记录交换后，再进行调整建成的新大顶堆。分析堆排序方法最坏情况下的
时间性能和辅助存储量。（10分）
4
三、算法设计题
1、编写算法，在一个带头结点的非递减有序单链表中插入一个元素，使其仍然是一个有序
单链表。（10分）
typedef struct Lnode{
ElemType data；
Struct Lnode *next;
}Lnode,*LinkList;
Error_code ListInsert(LinkList &L, ElemType x);
void insert(LinkList L,ElemType x)
{
q=L; p=L->next;
while ((p!=NULL) && (p->data < x)) {
p =p->next;
q =q->next;
} （5分）
s = (ListList) malloc(sizeof(LNode));
s->data=x;
q->next=s;
s->next=p;
}
2、编写算法，将String original中最多n个字符复制到String copy中。（10分）
void strncpy(String ©, const String &original，int n);
void strncpy(String ©, const String &original, int n)
{
const char *temp = original.c_str( ); （1分）
char *s = new char[n+1]; （2分）
strncpy(s, temp, n); （4分）
s[n] = 0; （1分）
copy = s; （1分）
delete []s; （1分）
}
5
3、斐波纳契数列定义如下：F0=0，F1=1，Fn=Fn-1+Fn-2。试画出F6的递归树，并编写一
个迭代程序求斐波纳契数。（10分）
i
nt fibonacci(int n)
int fibonacci(int n)
{
if n=0 return 0; （1分）
if n=1 return 1; （1分）
int f1=0;
int f2=1;
int f=0; （2分）
for (i=2;i<=n;i++){
f=f1+f2;
f1=f2;
f2=f; （5分）
}
Return f; （1分）
}
}
}
