数据结构期末考试试题(含答案).pdfVIP

数据结构期末考试试题(含答案)

C.{100,98,85,77,80,60,82,40,20,10,66}答：C。

10.在哈夫曼编码中，若有n个字符，其权值分别为w1，

w2，…，wn，编码长度分别为l1，l2，…，ln，则哈夫曼编

码的平均长度为a。

A.∑(wi/2li)B.∑(wi/li)

C.∑(wi/2li-1)D.∑(wi/li-1)

答：A。

2005-2006学年第二学期“数据结构”考试试题（A）

要求：所有的题目的解答均写在答题纸上。每张答题纸上

需写清楚姓名、班号和学号，并在上面写上题目的序号。

一、单项选择题（每小题2分，共20分）

1.数据的运算效率与采用何种存储结构有关。因此，选项

A是正确答案。

2.链表不具备的特点是可随机访问任一结点。参见本节要

点3.因此，选项A是正确答案。

3.在顺序表中删除一个元素的时间复杂度为O(n)。因此，

选项C是正确答案。

4.具有随机存取功能的线性表存储结构是顺序表。因此，

选项D是正确答案。

5.一个栈的进栈序列是a，b，c，d，e，则栈的不可能的

输出序列是dceab。因此，选项C是正确答案。

6.循环队列qu的队空条件是qu.rear==qu.front。因此，选

项D是正确答案。

7.两个串相等必有串长度相等且串中各位置字符均对应相

等。因此，选项B是正确答案。

8.用直接插入排序对下面四个序列进行递增排序，元素比

较次数最少的是21,32,46,40,80,69,90,94.因此，选项C是正确

答案。

9.以下序列不是堆（大根或小根）的是

{100,98,85,77,80,60,82,40,20,10,66}。因此，选项C是正确答

案。

10.在哈夫曼编码中，若有n个字符，其权值分别为w1，

w2，…，wn，编码长度分别为l1，l2，…，ln，则哈夫曼编

码的平均长度为∑(wi/2li)。因此，选项A是正确答案。

C。{10.20.40.60.66.77.80.82.85.98.100}

D。{100.85.40.77.80.60.66.98.82.10.20}

答案：D。

解析：题目给出两个序列，要求选择其中一个序列进行排

序。观察两个序列，发现D序列是C序列的逆序，因此选择

D序列进行排序可以使用归并排序，并且时间复杂度为

O(nlogn)。

修改后的小幅度改写：

给定两个序列C和D，选择D序列进行排序可以使用归

并排序，并且时间复杂度为O(nlogn)，因为D序列是C序列

的逆序。

2.将f=1+++…(n3)转化成递归函数，其递归出口是①，

递归体是②。

答案：①f(1)=1，②f(n)=f(n-1)+(n-2)。

解析：题目要求将f=1+++…(n3)转化成递归函数。观

察式子，可以发现f(n)=f(n-1)+(n-2)，且f(1)=1，因此递归

出口是f(1)=1，递归体是f(n)=f(n-1)+(n-2)。

修改后的小幅度改写：

将式子f=1+++…(n3)转化成递归函数，递归出口是f(1)

=1，递归体是f(n)=f(n-1)+(n-2)。

3.广义表((),a,(a),((a)))的长度是4①，深度是3②。

答案：4，3.

解析：题目给出广义表((),a,(a),((a)))，要求计算其长度和

深度。观察广义表，可以发现其长度为4，深度为3.

修改后的小幅度改写：

给定广义表((),a,(a),((a)))，其长度为4，深度为3.

4.具有n个结点的二叉树采用二叉链存储结构，共有n+1

个空指针域。

答案：n+1.

解析：题目给出具有n个结点的二叉树采用二叉链存储结

构，要求计算共有多少个空指针域。观察二叉链存储结构，可

以发现每个结点都有两个指针域，因此共有2n个指针域，而

每个叶子结点有两个