(完整word版)数据结构试卷及答案(word文档良心出品)
- 格式：doc
- 大小：127.00 KB
- 文档页数：6
本试卷共 6 页第1页 本试卷共 6 页第2页
注意事项：
题号 一 二 三 四 总分 核分人
得分
1、下面关于串的叙述中，哪一个是不正确的？（ ）
A．串是字符的有限序列 B．空串是由空格构成的串
C．模式匹配是串的一种重要运算
D．串既可以采用顺序存储，也可以采用链式存储
2、设无向图的顶点个数为n，则该图最多有（ ）条边。
A．n-1 B．n(n-1)/2 C． n(n+1)/2 D．0
3、以下数据结构中，（ ）是非线性数据结构。
A．树 B．字符串 C．队列 D．栈
4、下面关于线性表的叙述中，错误的是哪一个？（ ）
A．线性表采用顺序存储，必须占用一片连续的存储单元。
B．线性表采用顺序存储，便于进行插入和删除操作。
C．线性表采用链接存储，不必占用一片连续的存储单元。
D．线性表采用链接存储，便于插入和删除操作。
5、假设以数组A[m]存放循环队列的元素,其头尾指针分别为front和rear，则当前队列中的元素个数为（ ）。
A．(rear-front+m)%m B．rear-front+1
C．(front-rear+m)%m D．(rear-front)%m
6、在单链表指针为p的结点之后插入指针为s的结点,正确的操作是（ ）。
A．p->next=s; s->next=p->next; B．s->next=p->next; p->next=s;
C．p->next=s; p->next=s->next; D．p->next=s->next; p->next=s;
7、设栈的输入序列是1，2，3，4,则（ ）不可能是其出栈序列。
A．1，2，4，3 B．2，1，3，4 C．1，4，3，2 D．4，3，1，2，
8、广义表（a,(b,c),d,e）的表头和表尾分别为（ ）。
A．a和(b,c),d,e B．（a）和(b,c),d,e
C．a 和 ((b,c)，d,e) D．(a) 和((b,c)，d,e) 9、栈和队都是（ ）
A．顺序存储的线性结构 B．链式存储的非线性结构
C．限制存取点的线性结构 D．限制存取点的非线性结构
10、从逻辑上可以把数据结构分为（ ）两大类。
A．动态结构、静态结构 B．顺序结构、链式结构
C．线性结构、非线性结构 D．初等结构、构造型结构
11、下列四个序列中，哪一个是堆（ ）。
A．75,65,30,15,25,45,20,10 B．75,65,45,10,30,25,20,15
C．75,45,65,30,15,25,20,10 D．75,45,65,10,25,30,20,15
12、在下述结论中，正确的是（ ）
①只有一个结点的二叉树的度为0;
②二叉树的度为2；
③二叉树的左右子树可任意交换;
④深度为K的完全二叉树结点个数小于或等于深度相同的满二叉树。
A．①②③ B．②③④ C．②④ D．①④
13、若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（ ）
A．9 B．11 C．15 D．不确定
14、设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是（ ）。
A．M1 B．M1+M2 C．M3 D．M2+M3
15、在下面的程序段中，对x的赋值语句的频度为（ ）。
FOR i:=1 TO n DO
FOR j:=1 TO n DO
x:=x+1;
A． O(2n) B．O(n) C．O(n2) D．O(log2n)
16、一个n个顶点的连通无向图，其边的个数至少为（ ）。
A．n-1 B．n C．n+1 D．nlogn；
17、二叉树的第I层上最多含有结点数为（ ）
A．2I B． 2I-1-1 C． 2I-1 D．2I -1
18、下列排序算法中( )排序在一趟结束后不一定能选出一个元素放在其最终位置上。
A．选择 B．冒泡 C．归并 D．堆
19、二维数组A的元素都是6个字符组成的串，行下标i的范围从0到8，列下标j的范围从1到10。若A按行存放，元素A[8，5]的起始地址与A按列存放时的元素（ ）的起始地址一致。
A．A[8,5] B． A[3,10] C． A[5,8] D． A[0,9]
20、散列文件使用散列函数将记录的关键字值计算转化为记录的存放地址，因为散列函数是一对一的关系，则选择好的（ ）方法是散列文件的关键。
A．散列函数 B．除余法中的质数
C．冲突处理 D．散列函数和冲突处理 期末考试《数据结构》A卷
得分 评卷人 一、单项选择题（请将正确答案的字母填写在每题对应的括号内，每小题1分，共20分）
姓名:________ 学号:__________ 年级:______________ 专业:_____________
…….……………………….密…………………封…………………线………………………… 本试卷共 6 页第3页 本试卷共 6 页第4页 1、算法是由若干条指令组成的有穷序列，而一个程序不一定满足有穷性。（ ）
2、顺序存储方式只能用于存储线性结构。( )
3、对任何数据结构链式存储结构一定优于顺序存储结构。( )
4、有向图的邻接矩阵是对称矩阵，无向图的邻接矩阵是非对称矩阵。（ ）
5、所有二叉树的度均为2。（ ）
6、满二叉树一定是完全二叉树，但完全二叉树不一定是满二叉树。（ ）
7、循环链表不是线性表。 (
)
8、文件是记录的集合，文件上的操作主要有两类：检索和维护。（ ）
9、线性表的特点是每个元素都有一个前驱和一个后继。( )
10、按中序遍历二叉排序树所得到中序序列是一个递增有序序列。（ ）
1、已知一棵树边的集合为：
{( I , M ),( I ,N ),( E, I ),( B,E ),( B,D ),( A,B ),( G,
J ),( G,K ),( C,G ),( C,F ),(H,L ),( C,H ),( A,C )}
用树形表示法画出此树，并回答下列问题：
（1）哪个是此树的根结点？哪些是叶子结点？
（2）树的度数和树的深度是多少？
（3）写出结点G的双亲、祖先、孩子？
（4）写出结点E的子孙、兄弟和结点E所在的层次？
2、已知一棵二叉树的中序遍历序列和后序遍历序列分别为EBIFJAGDH和EIJFBGHDA。要求：（1）画出这棵二叉树；
（2）写出这棵二叉树的前序遍历序列。
3、已知世界六大城市为:北京(Pe)、纽约(N)、巴黎(Pa)、 伦敦(L) 、 东京(T) 、 墨西哥(M),下表给定了这六大城市之间的交通里程:
世界六大城市交通里程表(单位:百公里)
（1）画出这六大城市的交通网络图;
（2）画出该交通网络图按权值递增的顺序来构造的最小(代价)生成树。
4、假设用于通信的电文由字符集{a,b,c,d,e,f,g，h}中的字母构成。它们在电文中出现的频度分别为{7,19,2,6,32,3,21,10}。要求：
（1) 请为这8个字母设计哈夫曼编码，并画出对应的哈夫曼树；
（2）计算该哈夫曼树的最小加权路径长度WPL。
5、对给定的一组关键字：49，38，65，97，76，13，27，49，55，4 得分 评卷人 二、判断题，在正确的题后括号内打“√”，在错误的题后括号内打“×”（每小题1分，共10分）
得分 评卷人 三、应用题（第1、4、6题每题10分，第2、3题每题8分，第5题9分，共55分） Pe N Pa L T M
Pe 109 82 81 21 124
N 109 58 55 108 32
Pa 82 58 3 97 92
L 81 55 3 95 89
T 21 108 97 95 113
M 124 32 92 89 113
姓名:________ 学号:__________ 年级:______________ 专业:_____________
…….……………………….密…………………封…………………线………………………… 本试卷共 6 页第5页 本试卷共 6 页第6页 分别写出希尔排序（增量为5，3，1）、起泡排序和归并排序的前3趟排序结果。
6、设散列表长度为13，即其地址空间为0-12，散列函数H(k)=K mod 13,对关键字序列{19，14，23，01，68，20，84，27，55，11，10，79}。要求：
（1）画出用线性探查法解决冲突时构造的散列表（哈希表）。
（2）设每个记录的查找概率相等，计算查找成功的平均查找长度（ASLsucc）以及查找不成功的平均查找长度(ASLunsucc)。
1、已知带头结点的动态单链表L中的结点是按整数值递增排列，试写一算法将值为X的结点插入链表L中，使L仍然有序。单链表的描述如下：
typedef int datatype;
typedef struct node
{ datatype data;
struct node *next;
}linklist;
2、试写出递归的二分查找（折半查找）算法。得分 评卷人
四、算法设计题（第1题7分，第2题8分，共15分）
姓名:________ 学号:__________ 年级:______________ 专业:_____________
…….……………………….密…………………封…………………线…………………………
