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

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

四川师范大学计算机科学学院电子商务、 教育技术学专业
－ 第二学期期末考试
数据结构试卷
C卷
答卷说明: 1.本试卷共 8页, 五个大题, 满分 100分, 120分钟完卷。
2.本试卷为闭卷考试, 请将所有题目直接做在试卷上。
3.本试卷适用于 级 4、 5班。
题号
分数
一
二
三
四
五
总分
总分人
得分
评卷人
一、 单项选择题(每题 2分, 共 20分, 请将答案填在答题卡中)
答题卡
题号
答案
题号
答案
1
6
2
7
3
8
4
9
5
10
1．在 n个结点的顺序表中, 算法的时间复杂度是 O( 1) 的操作是:
A)访问第 i个结点( 1≤i≤n) 和求第 i个结点的直接前驱( 2≤i≤n)
B)在第 i个结点后插入一个新结点( 1≤i≤n)
C)删除第 i个结点( 1≤i≤n)
D)将 n个结点从小到大排序
2．设有一个足够大的栈, 入栈元素的顺序为 ABCD,, 则栈的可能输出序列是(
A) DACB B) CABD C) ABCD D) DBCA
) 。
3．串是一种特殊的线性表, 其特殊性体现在:
A) 能够顺序存储
B) 数据元素是一个字符
D) 数据元素能够是多个字符
C) 能够链式存储
4．若广义表 A=( (a,b,c),(d,e,f )) ,则式子 GetHead(GetTail(GetHead(GetTail(A))))的值为(
A) ( a,b,c) B) (d,e) C) e D) f
) 。
计算机科学学院电子商务、 教育技术学专业《数据结构》试卷 C 第 1页(共 8页)

5．下列程序段的时间复杂度是(
) 。
i=1;
while (i<=n)
i*=3;
A) O(1)
B) O(㏒ 3n)
C) O(n)
D) O(n )
3
6．有 m个叶子结点的哈夫曼树, 其结点总数为 (
A) 2m B) 2m-1
)。
C) 2m+1
D) 2m+2
7．设矩阵 A是一个对称矩阵, 为了节省存储, 将其下三角部分按行序存放在一维数组 B[ 1,
n(n-1)/2 ]中, 对下三角部分中任一元素 ai,j(i≥j),在一维数组 B中下标 k的值是( )。
A) i(i-1)/2+j-1 B) i(i-1)/2+j C) i(i+1)/2+j-1 D) i(i+1)/2+j
8．设满二叉树的深度为 m, 现采用顺序表示法存储该满二叉树, 每个结点占 L个存储单元,
则共需要( )个存储单元。
A)
m
B)
2
m
*L
C)
(2
m
-1)*L
D)
(2 +1)*L
m
9．有 8个结点的无向图最多有(
)条边。
A)
14
B)
28
C)
56
D)
112
10．二分查找法适用于存储结构为(
A) 顺序存储
) 的, 且按关键字排序的线性表。
B) 链接存储
C) 顺序存储或链接存储
D) 索引存储
得分
评卷人
二、 填空题(每题 2分, 共 20分, 请将答案填在答题卡中。)
答题卡
题号
答案
题号
答案
1
6
2
3
8
4
9
5
①
②
①
②
7
10
①
②
计算机科学学院电子商务、 教育技术学专业《数据结构》试卷 C 第 2页(共 8页)

1．数据的存储结构可用四种基本的存储方法表示, 它们分别是①
、 ②
、
索引和散列。
2．一个算法的效率可分为① 效率和② 效率。
3．向一个长度为n的顺序表中删除第i个元素(1≤i≤n)时, 需向前移动
个元素。
4．一棵具有258个结点的完全二叉树, 它的深度为
5．具有n个顶点的有向简单图最多有
。
条边。
6．若已知一个栈的入栈序列是1, 2, 3, …, n, 其输出序列为p1, p2, p3, …, pn, 若p1=n,
则pi为 。
7．拓扑排序算法是经过重复选择具有
个前驱顶点的过程来完成的。
8．用二叉链表法( link-rlink) 存储包含n个结点的二叉树, 结点的2n个指针区域中有
个为空指针。
9．有向图G用邻接矩阵存储, 其第i行的所有元素之和等于顶点i的
10、 大多数排序算法都有两个基本的操作① 和②
。
。
得分
评卷人
三、 简答题( 共 30分, 每小题 6分)
1.给出数组A[1..m, 1..n], 当它在内存中按行主序存放和按列主序存放时, 分别写出数组
元素A[i,j]的地址LOC( i,j) 的计算公式。( 设LOC(1,1)为数组的基地址, 每个元素占k个
存储单元)
计算机科学学院电子商务、 教育技术学专业《数据结构》试卷 C 第 3页(共 8页)

2．假设字符 a、 b、 c、 d、 e、 f的使用次数分别是 7, 9, 12, 22, 23, 27, 画出 Huffman树, 并根据
这棵树写出 a、 b、 c、 d、 e、 f的 Huffman( 哈夫曼) 编码。
3、 已知待排序文件各记录的关键字顺序如下
49
38
65
97
76
13
27
49
( 1) 请写出快速排序过程中第一趟的排序结果;
( 2) 什么是排序算法的稳定性? 判断快速排序算法的稳定性。
计算机科学学院电子商务、 教育技术学专业《数据结构》试卷 C 第 4页(共 8页)

4 .( 1) 简述图的深度优先遍历算法的基本思想;
( 2) 下图是用邻接表存储的图, 画出此图, 并写出从 C点开始按深度优先遍历该图的结果。
5．对于线性表(18, 25, 63, 50, 41, 32, 90, 66)进行散列存储时, 若选用H(K)＝K％11
作为散列函数, 则分别计算: 散列地址为0的元素的个数, 散列地址为3的元素的个数, 散
列地址为8的元素的个数。如果用一个长度为11的数组来存储散列后的数据, 并假设采用
线性探测再散列的方式进行冲突检测, 试写出散列后的序列。
计算机科学学院电子商务、 教育技术学专业《数据结构》试卷 C 第 5页(共 8页)

得分
评卷人
四、 阅读下面的算法( 10分)
//结点结构类型说明
typedefstructLNode{
int
data;
structLNode*next;
}Lnode,*LinkList;
Statusxyz(LinkList&head1,LinkList&head2,intx1,intx2){
//p,q,y,f均为LinkList类型变量, head1指向已经生成的单循环链表的表头结点,
//head2初值为NULL
f=head1;p=head1->next;
q=(LinkList)malloc(sizeof(Lnode));
head2=q;head2->data=0;head2->next=head2;
while(p!=head1)
if(p->data>x1)&&(p->data<x2){
y=p;f->next=p->next;
p=p->next;y->next=head2->next;head2->next=y;
}
else{f=p;p=p->next}
}//xyz
已知:
head1
0
100
250
290
300
400
500
x1=100;x2=400;
则: 1.简述算法xyz的功能;
2.执行算法xyz后, head1和head2两链表的结果如何? 请图示之。
五、 用类C语言描述下列算法, 并给出必要说明( 每小题10分, 共20分)
计算机科学学院电子商务、 教育技术学专业《数据结构》试卷 C 第 6页(共 8页)

1、 在带头结点的单链表 La中删除所有大于数值 x的结点并打印出所删除的结点个数。
已知线性表的单链表存储结构如下:
typedef struct Lnode {
elemtype data;
Lnode * next;
}Lnode,*LinkList;
给出算法 Status DeleteList( LinkList &La, ElemType x), 并给出必要的注释。
计算机科学学院电子商务、 教育技术学专业《数据结构》试卷 C 第 7页(共 8页)

2.写出二叉树的层次遍历的算法。
//二叉树的存储表示
typedef struct BiTNode{
ElemType data;
Stuct BiTNode * lchild,*rchild;//左右指针标志
}BiTNode,*BiTree
计算机科学学院电子商务、 教育技术学专业《数据结构》试卷 C 第 8页(共 8页)