数据结构试题B及参考答案(计算机专业)

由天下分享时间：2024/12/21 13:34:45 加入收藏我要投稿点赞

2010-2011 学年第 2 学期课号 BT11107

课程名称数据结构（B卷; 闭卷）适用班级（或年级、专业） 08011103、104、105

考试时间 120 分钟班级学号姓名题号满分得分评卷人一 20 二 20 三 50 四 10 五六七八九十成绩一、填空题（每小题2分，共20分）

(1) 数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的（）和运算等的学科。

(2) 在一个长度为n的顺序表中第i个元素（1 ≤ i ≤ n）之前插入一个元素时，需向后移动（）个元素。

(3）假设以S和X分别表示进栈和退栈操作，则对输入序列a，b，c，d，e进行一系列栈

操作SSXSXSSXXX之后，得到的输出序列为（）。（4）数据的逻辑结构在计算机存储器内的表示，称为数据的（）。（5）在具有n个单元的循环队列中，队满时共有____个元素。（6）二叉树有（）种基本形态。

（7）在具有n个结点的完全二叉树中，若结点i有左孩子，则结点i的左孩子编号为（）。（8）若用二叉树表示具有n个结点的二叉树，则有（）个空链域。（9）深度为 k（k>0）的二叉树，至多有（）个结点，第i层上之多有（）结点。 (10) 一个有n个顶点的无向图最多有____条边。

二、选择题（每小题2分，共20分）

1. 研究数据结构就是研究（）。 (A) 数据的逻辑结构

(B) 数据的存储结构

s=0;

for (i=0;i

（A）O（m） (B) O（n） (C) O（m×n） (D) O（m+n）

3.计算机识别、存储和加工处理的对象被统称为( )

（A）数据（B）数据元素（C）数据结构（D）数据类型

4. 在一个单链表中，若删除p所指结点的后续结点，则执行____。

（A）p—＞next= p—＞next—＞next； (B) p—＞next= p—＞next; (C) p= p—＞next; p—＞next= p—＞next—＞next； (D) p= p—＞next—＞next；

5. 在一非空二叉树的中序遍历序列中，根结点的右边____。

（A）只有右子树上的所有结点（B）只有右子树上的部分结点（C）只有左子树上的部分结点（D）只有左子树上的所有结点

6.队和栈的主要区别是( )

（A）逻辑结构不同（B）存储结构不同（C）所包含的运算个数不同（D）限定插入和删除的位置不同 7. 设有两个串p和q，求q在p中首次出现的位置的运算称作____。（A）连接（B）. 模式匹配（C）求子串（D）求串长 8. 具有35个结点的完全二叉树的深度为（）。（A）5 （B）6 （C）7 （D）8 9.下列编码中属前缀码的是( )

（A）{1,01,000,001} （B）{1,01,011,010} （C）{0,10,110,11} （D）{0,1,00,11}

10．用某种排序方法对线性表（ 25，84，21，47，15，27，68，35，20）进行排序时，元素序列的变化情况如下：

⑴ 25，84，21，47，15，27，68，35，20 ⑵ 20，15，21，25，47，27，68，35，84 ⑶ 15，20，21，25，35，27，47，68，84 ⑷ 15，20，21，25，27，35，47，68，84 则所采用的排序方法是____。

（A）选择排序（B）希尔排序（C）归并排序（D）快速排序

三、简答题（8小题，共50分）

1．对于如图1所示的树，请问：（5分）（1）树的根结点是哪个结点？（2）结点E的父结点是哪个结点？（3）E的兄弟结点是有哪些结点？（4）树的深度是多少？（5）树的度是多少？

2. 写出图2所示二叉树的先根遍历、中根遍历、后根遍历的结点序列，并将其转换为森林。（8分）

3. 有一份电文中共使用7个字符：a、b、c、d、e、f、g，它们的出现频率依次为4，5，6，12，8,10,18。要求：（9分）（1）试画出对应的哈夫曼树；（2）每个字符的哈夫曼编码；

（3）在对该电文进行最优二进制编码处理后，电文的二进制位数。

图2 I C B A E H ○I ○J ○B ○ A ○C ○D ○E ○F ○G ○图1

F H G 3