四川师范大学-第二学期数据结构期末试题A.doc

资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。

四川师范大学计算机科学学院电子商务、 教育技术学专业
－ 第二学期期末考试
数据结构试卷 A卷
答卷说明: 1.本试卷共 8页, 五个大题, 满分 100分, 120分钟完卷。
2.本试卷为闭卷考试, 请将所有题目直接做在试卷上。
3.本试卷适用于 级 4、 5班。
题号
分数
一
二
三
四
五
总分
总分人
得分
评卷人
一、 单项选择题(每题 2分, 共 20分, 请将答案填在答题卡中)
答题卡
题号
答案
题号
答案
1
6
2
3
8
4
9
5
7
10
1．下列说法正确的是: (
)
A．线性表的逻辑顺序和存储顺序总是一致的
B．线性表的链式存储结构中, 内存中可用的存储单元能够是连续的, 也能够不连续
C．线性表的顺序存储结构优于链式存储结构
D．每种数据结构都具有插入、 删除和查找三种基本操作。
2.带头指针 L的双向循环链表中, 指针 p指向双向循环链表的尾结点的条件是: (
)
A．p==L
B．p==NULL
C．L->prior==p
D．p->next==NULL
3.一个栈的输入序列为 12345, 则栈的不可能输出序列是(
A．54321 B．45321 C．12345
) 。
D．43512
4.设有两个串 p和 q, 求 q在 p中首次出现的位置的运算称作(
A.连接 B .模式匹配 C.求子串
)
D.求串长
计算机科学学院电子商务、 教育技术学专业《数据结构》试卷 A 第 1页(共 8页)

5.已知广义表 A=( a, b) , B=( A, A) , C=( a, ( b, A) , B) , 则 GetTail( GetHead( GetTail
( C) ) ) 的值为: (
A.( a,b)
)
B. ((a,b))
C.
b
D. a
6.程序段: for(i=0;i<=n;i++){++x;s+=x;}中, 语句++x;的频度为(
) 。
A．n
B．n+1
C．n+2
D．n-1
7.最大容量为 n的循环队列, 队尾指针是 rear, 队头指针是 front, 则队满的条件是(
)
)
A.( rear+1) %n==front
C.rear+1==front
B.rear==front
D.(rear-1)%n==front
8.以二叉链表作为二叉树存储结构, 在具有n结点的二叉链表中( n>0) , 空链域的个数为(
A.2n-1
C.n+1
B.n-1
D.2n+1
9.有 8个结点的无向图最多有(
) 条边。
A．14
B.
28
C.
56
D.
112
10.用快速排序法对数据文件进行排序时, (
) 记录在排序第一趟后就放在了合适的位
置。
A．关键值最大的
C．第一条
B．关键值最小的
D．最后一条
得分
评卷人
二、 填空题(每题 2分, 共 10分, 请将答案填在答题卡中。)
答题卡
题号
答案
1
2
3
4
5
1．深度为 K的满二叉树共有
个结点。
2.在一个图中, 所有顶点的度数之和等于图的边( 弧) 数的
倍
计算机科学学院电子商务、 教育技术学专业《数据结构》试卷 A 第 2页(共 8页)

3．哈夫曼树的结点数目 n与叶结点数目 m满足如下关系
4.有一个 10阶对称矩阵 A, 采用压缩存储方式( 以行序为主存储, 且 A[1][1]=1) , 则 A[8][5]的
地址是_______________。
5.一个无向图采用邻接矩阵存储方法, 其邻接矩阵一定是一个
。
得分
评卷人
三、 判断题(每题 1分, 共 10分, 正确: √, 错误: ×, 请将答案填在答题卡中。)
答题卡
题号
答案
题号
答案
1
6
2
7
3
8
4
9
5
10
1.
2.
3.
线性表的逻辑顺序与存储顺序总是一致的。
栈和队列是一种非线性数据结构。
(
(
)
)
队是一种插入与删除操作分别在表的两端进行的线性表, 是一种先进先出结构。(
)
4.设有两个串 p和 q, 求 q在 p中首次出现的位置的运算称作求子串。
(
)
5.
6.
7.
二叉树是树的特殊形式。
(
)
一棵树的度为树中各个结点的度数之和
(
)
对任意一个图, 从它的某个顶点出发进行一次深度优先或广度优先遍历可访问到该图的
每个顶点。
(
)
8.向二叉排序树插入一个新结点时, 新结点一定成为二叉排序树的一个叶子结点。(
)
9.
对无序表用折半查找比顺序查找快。
(
)
10.用邻接矩阵存储一个图时, 在不考虑压缩存储的情况下, 所占用的存储空间大小只与图
中结点个数有关, 而与图的边数无关。
(
)
计算机科学学院电子商务、 教育技术学专业《数据结构》试卷 A 第 3页(共 8页)

得分
评卷人
三、 简答题(共 6道小题, 每小题 6分, 共 36分)
已知一棵二叉树的中序序列和后序序列分别为BDCEAFHG和DECBHGFA, 画出这棵二叉树
1.
并画出该二叉树的中序线索化树。
2.设某密码电文由 8个字母( A, B, C, D, E, F, G, H) 组成, 每个字母在电文中的出现
频率分别是 7, 19, 2, 6, 32, 3, 21, 10, 试为这 8个字母设计相应的哈夫曼编码。
计算机科学学院电子商务、 教育技术学专业《数据结构》试卷 A 第 4页(共 8页)

3．记录的关键字集合 key={ 49, 38, 66, 90, 75, 10, 20 }, 写出快速排序第一趟和第二趟之后的
状态, 并判断快速排序是否稳定。
4．给定下列网G:
试着画出网 G的最小生成树;
计算机科学学院电子商务、 教育技术学专业《数据结构》试卷 A 第 5页(共 8页)

5.对于有向无环图
( 1 ) 叙述求拓扑有序序列的步骤;
( 2) 对于下图写出它的四个不同的拓扑有序序列。
6．若关键字序列为( 10, 24, 32, 17, 31, 30, 46, 47, 40, 63, 49) , 哈希函数为: H( K)
＝K
MOD
11, K为关键字。给出用线性探测再散列法处理冲突所构造的哈希表。
计算机科学学院电子商务、 教育技术学专业《数据结构》试卷 A 第 6页(共 8页)

得分
评卷人
五、 用类C语言描述下列算法, 并给出必要说明。( 第一题14分, 第二题10分, 共24分)
1、 用算法建立含 n个结点的带头结点的单链表 La( n个结点的值由键盘输入) , 并删除所有
等于数值 x的结点。( 14分)
已知线性表的单链表存储结构如下:
typedef struct Lnode {
elemtype data;
Lnode * next;
}Lnode,*LinkList;
给出算法 void creatList( LinkList &La, int n )、 void DeleteList( LinkList &La, elemtype
x)
并给出必要的说明。
计算机科学学院电子商务、 教育技术学专业《数据结构》试卷 A 第 7页(共 8页)

2、 设二叉树采用二叉链表存储结构, 试设计一个算法计算一棵给定二叉树的深度。( 10分)
//二叉树的存储表示
typedef struct BiTNode{
ElemType data;
Stuct BiTNode * lchild,*rchild;//左右指针标志
}BiTNode,*BiTree
计算机科学学院电子商务、 教育技术学专业《数据结构》试卷 A 第 8页(共 8页)