全国2009年1月高等教育自学考试数据结构试题
课程代码:02331

一、单项选择题(本大题共15小题,每小题2分,共30分)
在每小题列出的四个备选项中只有一个是符合题目要求的,请将其代码填写在题后的括号内.错选、多选或未选均无分.
1.下列程序段的时间复杂度为（　　）
s=0；
for(i=1；i<n；i++)
for(j=1；j<n；j++)
s+=i*j；
A.O(1)
B.O(n)
C.O(2n)
D.O(n²)

2.假设某个带头结点的单链表的头指针为head,则判定该表为空表的条件是（　　）
A.head==NULL；
B.head->next==NULL；
C.head!=NULL；
D.head->next==head；

3.栈是一种操作受限的线性结构,其操作的主要特征是（　　）
A.先进先出
B.后进先出
C.进优于出
D.出优于进

4.假设以数组A[n]存放循环队列的元素,其头、尾指针分别为front和rear.若设定尾指针指向队列中的队尾元素,头指针指向队列中队头元素的前一个位置,则当前存于队列中的元素个数为（　　）
A.(rear-front-1)%n
B.(rear-front)%n
C.(front-rear+1)%n
D.(rear-front+n)%n

5.判断两个串大小的基本准则是（　　）
A.两个串长度的大小
B.两个串中首字符的大小
C.两个串中大写字母的多少
D.对应的第一个不等字符的大小

6.二维数组A[4][5]按行优先顺序存储,若每个元素占2个存储单元,且第一个元素A[0][0]的存储地址为1000,则数组元素A[3][2]的存储地址为（　　）
A.1012
B.1017
C.1034
D.1036

7.高度为5的完全二叉树中含有的结点数至少为（　　）
A.16
B.17
C.31
D.32

8.已知在一棵度为3的树中,度为2的结点数为4,度为3的结点数为3,则该树中的叶子结点数为（　　）
A.5
B.8
C.11
D.18

9.下列所示各图中是中序线索化二叉树的是（　　）

10.已知含6个顶点(v₀,v₁,v₂,v₃,v₄,v₅)的无向图的邻接矩阵如图所示,则从顶点v₀出发进行深度优先遍历可能得到的顶点访问序列为（　　）

A.(v₀,v₁,v₂,v₅,v₄,v₃)
B.(v₀,v₁,v₂,v₃,v₄,v₅)
C.(v₀,v₁,v₅,v₂,v₃,v₄)
D.(v₀,v₁,v₄,v₅,v₂,v₃)

11.如图所示有向图的一个拓扑序列是（　　）

A.ABCDEF
B.FCBEAD
C.FEDCBA
D.DAEBCF

12.下列关键字序列中,构成大根堆的是（　　）
A.5,8,1,3,9,6,2,7
B.9,8,1,7,5,6,2,33
C.9,8,6,3,5,1,2,7
D.9,8,6,7,5,1,2,3

13.对长度为15的有序顺序表进行二分查找,在各记录的查找概率均相等的情况下,查找成功时所需进行的关键字比较次数的平均值为（　　）
A. 39/15
B.49/15
C. 51/15
D.55/15

14.已知一个散列表如图所示,其散列函数为H(key)=key%11,采用二次探查法处理冲突,则下一个插入的关键字49的地址为（　　）

15.数据库文件是由大量带有结构的（　　）
A.记录组成的集合
B.字符组成的集合
C.数据项组成的集合
D.数据结构组成的集合

二、填空题(本大题共10小题,每小题2分,共20分)
请在每小题的空格中填上正确答案.错填、不填均无分.
16.估算算法时间复杂度时考虑的问题规模通常是指算法求解问题的_________.
17.在双向循环链表中插入一个新的结点时,应修改_________个指针域的值.
18.若进栈序列为a,b,c,且进栈和出栈可以穿插进行,则可能出现_________个不同的出栈序列.
19.链串的结点大小定义为结点的_________中存放的字符个数.
20.广义表(a,(d,(c)))的深度为_________.
21.在含有3个结点a,b,c的二叉树中,前序序列为abc且后序序列为cba的二叉树有_________棵.
22.若用邻接矩阵表示有向图,则顶点i的入度等于矩阵中_________.
23.对关键字序列(15,18,11,13,19,16,12,17,10,8)进行增量为5的一趟希尔排序的结果为_________.
24.索引顺序查找的索引表由各分块中的最大关键字及各分块的_________构成.
25.VSAM文件的实现依赖于操作系统中的_________存取方法的功能.

三、解答题(本大题共4小题,每小题5分,共20分)
26.假设有一个形如的8×8矩阵,矩阵元素都是整型量(次对角线以上的元素都是0).
若将上述矩阵中次对角线及其以下的元素按行优先压缩存储在一维数组B中,请回答下列问题:
(1)B数组的体积至少是多少？
(2)若a₁₈存储在B[0]中,a₅₆存储在B[k]中,则k值为多少？
(1)
(2)
27.对关键字序列(5,8,1,3,9,6,2,7)按从小到大进行快速排序.
(1)写出排序过程中前两趟的划分结果；
(2)快速排序是否是稳定的排序方法？
(1)
(2)
28.假设通信电文使用的字符集为{a,b,c,d,e,f,g,h},各字符在电文中出现的频度分别为:7,26,2,28,13,10,3,11,试为这8个字符设计哈夫曼编码.要求:
(1)画出你所构造的哈夫曼树(要求树中左孩子结点的权值不大于右孩子结点的权值)；
(2)按左分支为0和右分支为1的规则,分别写出与每个字符对应的编码.
(1)
(2)
29.已知3阶B—树如图所示,
 
(1)画出将关键字6插入之后的B—树；
(2)画出在(1)所得树中插入关键字2之后的B—树.
(1)
(2)　

四、算法阅读题(本大题共4小题,每小题5分,共20分)
30.假设以带头结点的单链表表示线性表,单链表的类型定义如下:
typedef int DataType;
typedef struct node {
DataType data;
struct node * next;
} LinkNode, * LinkList;
阅读下列算法,并回答问题:
(1)已知初始链表如图所示,画出执行f30(head)之后的链表；

题30图
(2)简述算法f30的功能.
void f30( LinkList head)
　　{ LinkList p,r, s;
　　　　if (head - > next) {
　　　　　　r = head - > next;
　　　　　　p = r->next;
　　　　　　r - > next = NULL;
　　　　　　while (p) {
　　　　　　　　s =p;
　　　　　　　　p = p->next;
　　　　　　　　if ( s - > data% 2 = = 0) {
　　　　　　　　　　s - > next = head - > next;
　　　　　　　　　　head - > next = s;
　　　　　　　　} else {
　　　　　　　　s - > next = r - > next;
　　　　　　　　r->next = s;
　　　　　　　　r =s;
　　　　　　　　}
　　　　　　}
　　　　}
　　}
(1)
(2)
31.假设以二叉链表表示二叉树,其类型定义如下:
typedef struct node {

[1]