2011-2012学年第一学期期末考试试题 （a）卷。
课程名称 《算法与数据结构》 任课教师签名
出题教师签名 2011计算机合作联盟命题组审题教师签名
考试方式 （ 闭 ）卷适用专业 10计科1-2
考试时间 （ 110 ）分钟。
注：判断题和选择题的答案写在答题纸上）
1.与数据元素本身的形式、内容、相对位置、个数无关的是数据的( )
a.存储结构b.储存实现。
c.逻辑结构d.运算实现。
2. 已知指针p和q分别指向某单链表中第一个结点和最后一个结点。假设指针s指向另一个单链表中某个结点，则在s所指结点之后插入上述链表应执行的语句为( )
a. q->next=s->next；s->next=p； b. s->next=p；q->next=s->next；
c. p->next=s->next；s->next=q； d. s->next=q；p->next=s->next；
3.队和栈的主要区别是( )
a.逻辑结构不同b.存储结构不同。
c.所包含的运算个数不同d.限定插入和删除的位置不同。
4.已知广义表的表头为a，表尾为(b,c)，则此广义表为( )
a.(a,(b,cb.(a,b,c)
c.((a),b,cd.((a,b,c))
5. 二维数组a[10][6]采用行优先的存储方法，若每个元素占4个存储单元，已知元素a[3][4]的存储地址为1000，则元素a[4][3]的存储地址为( )
a. 1020b. 1024c. 1036 d. 1240
6. 用二叉链表表示具有n个结点的二叉树时，值为空的指针域的个数为( )
a. n-1b. n+lc. nd. 2n
7.二叉树中第5层上的结点个数最多为( )
a.8b.16
c.15d.32
8．一棵完全二叉树上有1001个结点，其中叶子结点的个数是( )
a． 250 b． 500 c． 254 d． 501
9. 若非连通无向图g含有21条边，则g的顶点个数至少为( )
a. 7b. 8c. 21 d. 22
10. 若采用邻接矩阵法存储一个n个顶点的无向图，则该邻接矩阵是一个。
a. 上三角矩阵b. 稀疏矩阵。
c. 对角矩阵d. 对称矩阵。
11. 以v1为起始结点对下图进行深度优先遍历，正确的遍历序列是( )
a．v1，v2，v3，v4，v5，v6，v7 b．v1，v2，v5，v4，v3，v7，v6
c．v1，v2，v3，v4，v7，v5，v6 d．v1，v2，v5，v6，v7，v3，v4
12.对表长为n的顺序表进行顺序查找，在查找概率相等的情况下，查找成功的平均查找长度为( )
13. 在长度为32的有序表中进行二分查找，当查找成功时和给定值进行比较的关键字个数最多为( )
a. 4b. 5c. 6d. 7
14. 对关键字序列(6，1，4，3，7，2，8，5)进行快速升序排序时，以第1个元素为基准的一次划分的结果为( )
a. (5，1，4，3，6，2，8，7) b. (5，1，4，3，2，6，7，8)
c. (5，1，4，3，2，6，8，7) d. (8，7，6，5，4，3，2，1)
15. 下列排序方法中稳定的为( )
a. 冒泡排序 b. 堆排序 c. 希尔排序 d. 快速排序。
1．数据元素及其关系在计算机存储器内的表示称为。
2. 已知在结点个数大于1的单循环链表中，指针p指向表中某个结点，则下列程序段执行结束时，指针q指向结点*p的结点。
q=p;while (q->next!=p) q=q->next;
3. 假设s和x分别表示进栈和出栈操作，由输入序列“abc”得到输出序列“bca”的操作序列为ssxsxx，则由“a*b+c/d”得到“ab*cd/+”的操作序列为___
4. 假设以行优先顺序将一个n阶的3对角矩阵压缩存储到一维数组q中，则数组q的大小至少为。
5. 森林的中根遍历序列正是相应二叉树的遍历序列，森林的先根遍历序列正是相应二叉树的遍历序列。
6．一棵含999个结点的完全二叉树的深度为。
普里姆）算法适用于求网的最小生成树；kruskal（克鲁斯卡尔）算法适用于求网的最小生成树。
8. 在一个无向图中，所有顶点的度数之和等于所有边数的倍。
9．对于关键字序列，进行2-路归并升序排序，则第一趟归并排序的结果为。
10.若**性表中采用二分查找法查找元素，该线性表应该元素按值有序，且采用存储结构。
1.假设通信电文使用的字符集为，字符的哈夫曼编码依次为：0110，10，110，111，00，0111和010。(约定左分支编码为0，右分支编码为1)
1)请根据哈夫曼编码画出此哈夫曼树，并在叶子结点中标注相应字符；（5分）
2)若这些字符在电文**现的频度分别为：3，35，13，15，20，5和9，求该哈夫曼树的带权路径长度wpl。（2分）
2．用prim算法（从顶点b出发）求如下连通图的最小生成树，要求：画出最小生成树，并给出树中每条边的生成顺序（如第1条边：（v0，v1），第2条边：（v0，v3） …
3．从空树起，依次插入关键字37，50，42，18，48，12，56，30，23，构造一棵二叉排序树。
1）画出该二叉排序树；（4分）
2）画出从（1）所得树中删除关键字为37的结点之后的二叉排序树。（3分）
4．在地址空间为0~16的散列区中，对以下关键字序列构造哈希表：
job,fly,man,apple,max,key,kid,big,lady,no,set,oct,name）
用线性探测再散列开放地址法处理冲突。并求在等概率情况下查找成功时的平均查找长度。设哈希函数为（例如：）,其中i为关键字中第一个字母在字母表中的序号(字母a的序号为1)。
1. 设栈s=(1,2,3,4,5,6,7),其中7为栈顶元素。
1）写出调用f4_1(&s)后的s；（4分）
2）简述函数f4_1中第1个循环语句的功能。（2分）
void f4_1 (stack *s)
queue q;
stack t;
int i=0;
initqueue(&q);
initstack(&t);
while(!stackempty(s))
i++;if (i%2= =1) push(&t,pop(s));
else enqueue(&q,pop(s));
while (!stackempty(&t))
push(s,pop(&t));
while(!queueempty(&q))
push(s,dequeue(&q));
2．已知下列程序，ls指向带头结点的单链表。
typedef struct node *linklist;
void f4_2( linklist ls )
linklist p, q;
q = ls->next;
if ( q &&q->next )
ls->next = q->next;
p=qwhile ( p->next )
p = p->next;
p->next = q;
q->next = null;
请回答下列问题：
1)当ls指向的链表如下图所示，请画出执行本函数之后的链表的结果。（4分）
2)请简述算法的功能。（2分）
假设以带头结点的单链表表示有序表(非递减排列)，单链表的类型定义如下：
typedef struct node{
datatype data;
struct node *next
linknode, *linklist;
编写算法，从有序表a中删除所有和有序表b中元素相同的结点。算法的函数原型给定为：
void f5(linklist a,linklist b)；
数据结构与算法
本章知识要点 算法的基本概念 数据结构的定义 线性表的定义和存储 树 二叉树的定义和存储 查找与排序算法。算法 algorithm 是一组有穷的规则，规定了解决某一特定类型问题的一系列运算，是对解题方 与完整的描述。算法是解题的步骤，可以把算法定义成解一确定类问题的任意一种特殊的方法。在计算机科学中...
算法与数据结构
学院专业姓名学号。实验1 线性表的操作 12学时 问题描述 假设一个班级内有n个学生，定义一个学生类和一个班级类。学生类中包括学号 姓名 性别 年龄 专业等属性 班级类包括一个学生对象链表。定义如下 class student class myclass student stu head 链表表头指...
算法与数据结构
1 简述算法的概念及其五个重要特性。2 下图是用邻接表存储的图，请画出此图，写出其邻接矩阵以及从c点开始分别按广度优先搜索和深度优先搜索遍历该图的结果。给定一棵用二叉链表表示的二叉树，其根指针为root，编写求此二叉树叶结点个数的算法，要求先写出二叉链表的类型定义。2.编写简单选择排序的算法。1 用...