内容发布更新时间 : 2024/5/27 16:56:05星期一 下面是文章的全部内容请认真阅读。

装订线—————————————————————————————————————————————————————————— 2008－2009学年第二学期

计算机科学学院《数据结构》期末考试试卷（A卷）

答案与评分标准

年级：07级 专业： 班级： 学号： 姓名： 题号 得分 一 二 三 四 五 六 总分 签名 注：1、共100分，考试时间120分钟。

2、此试卷适用于计算机科学与技术本科、信息管理与信息系统专业。

一 得 分 阅卷教师 一、填空题（本题共10小题，每个空2分，共20分）

1．数据是对客观事物的符号的表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的（ 符号的总称 ）。

2．抽象数据类型是指一个（ 数学模型 ）以及定义在该模型上的一组操作。

3. 在顺序表中插入或删除一个元素，需要平均移动（ 表中一半 ）元素，具体移动的元素个数与（ 表长和该元素在表中的位置 ）有关。

4. 顺序表中第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的存储地址是（ 108 ）。

5．循环队列的引入是为了克服（ 假溢出 ）。 6．head(tail(head(((a，b)，(c，d)))))= b 。

7．已知一棵完全二叉树共有768个结点，则该树中有（ 384 ）个叶子结点。 8．某二叉树的先序遍历序列是8，5，1，3，2，4，6，7，10，9，11 ，中序遍历序列是1，2，3，4，5，6，7，8，9，10，11，则其后序遍历序列是（2，4，3，1，7，6，5，9，11，10，8）。

9．有向图G用邻接矩阵存储，其第i行的所有元素之和等于顶点i的（ 出度 ）。

2

10．对n个待排序记录序列进行快速排序，其最坏时间复杂度为（ O（n） ）。

二 得 分 阅卷教师 二、选择题（本题共5小题，每个空2分，共10分）

1．算法是指 （ A ）

A．对特定问题求解步骤的一种描述，是指令的有限序列

B．计算机程序 C．解决问题的计算方法 D．数据处理

《数据结构与算法》期末考试试卷（A卷）第 1 页 共 5 页

2．若某线性表中最常用的操作是取第i个元素和查找第i个元素的前驱，则采用（ A ）存储方法最节省时间。

A．顺序表 B．单链表 C．双链表 D．单循环链表

3．设计一个判别表达式中左右括号是否配对的算法，采用（ B ）数据结构最佳。 A．队列 B．栈 C．链表 D．树

4．若一棵二叉树有10个叶子结点，则该二叉树中度为2的结点个数是 （ D ）

A．11 B．10 C．不确定 D．9

5．二叉排序树中，最小值的结点的 （ B ）

A．右指针一定为空 B．左指针一定为空

C．左、右指针均一定为空 D．左、右指针均不为为空

三 得 分 阅卷教师 三、名词解释(本题共3小题，每小题2分，共6分)

数据类型——一个值得集合和定义在这个值上的一组操作的总称；

数据结构——相互之间存在一种或多种特定关系的数据元素的集合。

栈——限定仅在表尾进行插入或删除操作的线性表。

四 得 分 阅卷教师 四、简答题与应用题(本题共7小题，每小题7分，共49分) 1、在什么情况下用顺序表比链表好？

答：在需要查找与修改数据元素值的操作比插入与删除元素的操作频繁的情况，和在存储密度要求高的情况，顺序表比链表好。

2、简述栈和线性表的差别。

答： 栈和线性表的差别在于：栈规定了插入和删除运算只能在线性表的表尾进行，通常表尾端称为栈顶，插入运算称为入栈，删除运算称为出栈，而线性表无此运算限定。

3、设字符串P=‘aabaac’，请求出P的next值和nextval值。 解：p的next与nextval值分别为012123和002003。

4、有一份电文中共使用五个字符：a、b、c、d、e，它们的出现频率依次为

《数据结构与算法》期末考试试卷（A卷）第 2 页 共 5 页

（8、14、10、4、18），请构造相应的哈夫曼树（要求左子树根结点的权小于等于右子树根结点的权），求出每个字符的哈夫曼编码。

解：哈夫曼树为：

————————————————————————————————————————————————————————— （2分）

相应的哈夫曼编码为： a：011； b：10； c：00； d：010； e：11（每个1分）

装 5、已知一棵度为k的树中有n1个度为1的结点，n2个度为2的结点，……，nk个度为k的结点，问该树中有多少个叶子结点？

解：设树上结点总数 n = n0 + n1 + n2 + …… + nk （1分）

又树上分支总数 b = 1*n1 + 2*n2 + …… + k*nk （1分） 而 b = n-1 = n0 + n1 + n2 + …… + nk – 1 （3分） 由此， n0 = 1 + 0*n1 + 1*n2 + …… + (k-1)*nk = 1??(i?1)n （2分）

ii?1k订线

6、某AOE网如右图，问事件4的最早发生时间与最迟发生时间，活动E的最早开始时间与最迟开始时间和该AOE网代表的工程完成的最短时间（即关键路径的长度）。 解：

事件4的最早发生时间=15（1分）

最迟发生时间=18（1分）

活动E的最早开始时间=3（1分）

最迟开始时间=3（1分）

该AOE网代表的工程完成的最短时间=33（3分）

7、画出对长度为10的有序表进行折半查找的判定树，并求其等概率时查找成功的平均查找长度。

解：ASL＝（1+2*2+3*4+4*3）/10＝2.9 （3分）

《数据结构与算法》期末考试试卷（A卷）第 3 页 共 5 页

（4分）

五 得 分 阅卷教师 五、程序填空：（共2小题，每小空2分，共10分）

已知L是带头结点的非空单链表，且P结点既不是首元结点，也不是尾元结点，试从下列提供的答案中选择合适的语句序列。

a、删除P结点的直接后续结点的语句序列是： 11，3，14

b、删除P结点的直接前驱结点的语句序列是： 10，12，8，11，3，14 c、删除P结点的语句序列是： 10，12，7，3，14 d、删除首元结点的语句序列是： 12，11，3，14 e、删除尾元结点的语句序列是： 9，11，3，14

（1）P=P->next; （2）P->next=P;

（3）P->next=P->next->next; （4）P=P->next->next; （5）while(P!=Null) P=P->:next;

（6）while(Q->next!=Null){P=Q;Q=Q->next;} （7）while(P->next!=Q) P=P->next;

（8）while(P->next->next!=Q) P=P->next; （9）while(P->next->next!=Null) P=P->next;

（10）Q=P; （11）Q=P->next; （12）P=L; （13）L=L->next; （14）free(Q);

六 得 分 阅卷教师 六、程序设计题(共5分)

对于采用定长顺序存储结构的串S，编写一个函数删除其值等于ch的所有字符。

解：从后向前删除值为ch的所有元素，这样所有移动的元素中没有值为ch的元素，能减少移动元素的次数，提高算法的效率。算法如下：

void Delch（SString S,char ch） （1分） {

for(i=S[0];i>0;i--) （1分） if (S[i]==ch) { （1分）

for(j=i+1;j<=S[0];j++) S[j-1]=S[j]; （1分）

《数据结构与算法》期末考试试卷（A卷）第 4 页 共 5 页

S[0]--; （1分） } }

《数据结构与算法》期末考试试卷（A卷）第 5 页 共 5 页