汕 头 职 业 技 术 学 院

2008-2009学年第一学期期末试卷（D）

课程名称 数据结构 学分_____ 拟题人 何汉阳 审题人___________ 系(校区) 计算机系 班级_____________ __ 学号_____ 姓名_ _________

题 号 得 分 一 二 三 四 五 六 七 八 总 分 评卷人

一、填空（每空1分，共20分）

1. 数据结构是研究数据的__________和________以及他们之间的相互关系，并对这种结构定义相应的__________。

2. 在线性表的顺序存储中，元素之间的逻辑关系是通过_________决定的；在线性表的链接存储中，元素之间的逻辑关系是通过_____________决定的。

3. 对于一个具有N个结点的单链表，在已知的结点*P后插入一个新结点的时间复杂度为_________,在给定值为X的结点后插入一个新结点的时间复杂度为_____________。

4. 一个字符串相等的充要条件是__________________和______________________。

5. 对于一棵具有n个结点的二叉树，对应二叉链表中指针总数为________个，其中_______个用于指向子女结点，__________个指针空闲着。

6. 在一棵三叉树中，度为3的结点数有2个，度为2的结点数有1个，度为1的结点数为2个，那么度为0的结点数有__________个。

7. 在霍夫曼编码中，若编码长度只允许小于等于4，则除了已对两个字符编码为0和10外，还可以最多对__________个字符编码。

8. 在一个无向图中，所有顶点的度数之和等于所有边数的______倍。在一个具有n个顶点的无向图中，要连通所有顶点则至少需要________条边。

9. 以折半搜索方法从长度为12的有序表中搜索一个元素时，平均搜索长度为___________。

10. 在直接选择排序中，记录比较次数的时间复杂度为________,记录移动次数的时间复杂度为______。 11. 假定一组记录的排序码为（46，79，56，38，40，80），对其进行快速排序的一次划分的结果为_____________________。

二、选择题（在正确答案上打“√”，共20分，每小题2分）

1. 根据具有n个元素的一个线性表,建立一个有序单链表的时间复杂性为:

(A). O(1) (B). O(n) (C). O(n) (D). O(logN) 2.采用链接方式存储线性表的优点是_________。

2

(A).便于随机存取 (B).花费的存储空间较顺序存储少

(C).便于插入和删除操作 (D).数据元素的物理顺序和逻辑顺序相同 3．队列操作的原则是_________。

(A).先进先出 (B).后进先出

(C).只能进行插入 (D).只能进行删除

4．在有n个结点的二叉链表中，值为非空的链域的个数为______。 (A). n-1 (B). n+l (C). 2n-1 (D). 2n+l

5. 在一个链队列中,假定front和rear分别为队首指针和队尾指针,则进行插入s结点 的操作时应执行________。

(A). front->next=s; front=s; (B). rear->next=s; rear=s; (C). s->next=rear; rear=s; (D). s->next=front; front=s;

6. 在一个长度为n的顺序表中，删除值为x的元素需要比较和移动元素的平均次数为_______。 (A).n/2 (B).(n+1)/2 (C).n (D).n+1 7．下面关于图的存储的叙述中，哪一个是正确的。 （ ）

(A)．用相邻矩阵法存储图,占用的存储空间数只与图中结点个数有关,而与边数无关 (B)．用相邻矩阵法存储图,占用的存储空间数只与图中边数有关,而与结点个数无关 (C)．用邻接表法存储图，占用的存储空间数只与图中结点个数有关，而与边数无关 (D)．用邻接表法存储图，占用的存储空间数只与图中边数有关，而与结点个数无关 8．非空的循环单链表head的尾结点(有指针p所指)满足______。 (A). p->next = NULL (B). p->next = head

(C). p = NULL (D). p = head 9. 下列陈述中正确的是( )

(A).二叉树是度为2的有序树 (B).二叉树中结点只有一个孩子时无左右之分 (C).二叉树中必有度为2的结点 (D).二叉树中最多只有两棵子树，并且有左右之分 10. 在最好和最坏情况下的时间复杂度均为O(nlog2n)且稳定的排序方法是( ) (A).快速排序 (B).堆排序 (C).归并排序 (D).基数排序

三、判断题（每小题2分，共20分）

1、逻辑结构不相同的数据，要采用不同的存储方法来存储。（ ）

2、在有n个元素的顺序表中，删除任意一个元素所需移动结点的平均次数为n-1。（ ） 3、线性表的链式存储方式优于顺序存储方式。（ ）

4、对顺序栈进行进栈、出栈操作，不涉及元素的前、后移动问题。（ ） 5、已知二叉树的先序和后序序列，并不能唯一确定这棵二叉树。（ ） 6、哈夫曼树中，权值较大的叶子结点一般都离根结点较远。（ ）

7、如果表示有向图的邻接矩阵是对称矩阵，则该有向图一定是完全有向图。（ ） 8、若无向网中没有权值相同的边，其最小生成树就是唯一的。（ ） 9、在有序的单链表中，可采用二分查找来提高查找速度。（ ）

10、对一个堆，按二叉树层次进行遍历可以得到一个有序序列。（ ）

四、假设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别为7，19，2，6，32，3，21，10，试为这8个字母设计哈夫曼编码。（10分）

五、假定在学生的档案中含有：姓名、学号、年龄、性别。如采用线性表作为数据结构来实现档案管理问题，分别给出线性表的在顺序实现下的类型定义和在链接实现下的类型定义。（10分）

六、设哈希函数为 H(K) = K mod 11，地址空间为 0..12，用线性探测法解决冲突。请画出依次插入 23，6，35，12，17，32，9，57，33，21所得到的散列地址表示意图。并计算平均查找长度。（10分）