一单项选择题(本大题共 小题每小题 分共 分)
在每小题列出的四个备选项中只有一个是符合题目要求的请将其代码填写在题后的括号内错选多选或未选均无分
在数据结构中数据的逻辑结构可以分成()
A 内部结构和外部结构 B 线性结构和非线性结构
C 紧凑结构和非紧揍结构 D 动态结构和静态结构
在以单链表为存储结构的线性表中数据元素之间的逻辑关系用()
A 数据元素的相邻地址表示 B 数据元素在表中的序号表示
C 指向后继元素的指针表示 D 数据元素的值表示
设 p 指向单链表中的一个结点 s 指向待插入的结点则下述程序段的功能是()
s > next = p > next; p > next = s;
t = p > data; p > data = s > data; s >data = t;
A 结点 *p 与结点 *s 的数据域互换
B 在 p 所指结点的元素之前插入元素
C 在 p 所指结点的元素之后插入元素
D 在结点 *p 之前插入结点 *s
栈和队列都是()
A 限制存取位置的线性结构 B 顺序存储的线性结构
C 链式存储的线性结构 D 限制存取位置的非线性结构
若数组 s[n] 为两个栈 s 和 s 的共用存储空间且仅当 s[n] 全满时各栈才不能进行进栈操作则为这两个栈分配空间的最佳方案是 s 和 s 的栈顶指针的初值分别为()
A 和 n+ B 和 n/
C 和 n D 和 n+
执行下列程序段后串 X 的值为()
S= 〞 abcdefgh 〞 ; T= 〞 xyzw 〞 ;
substr (XSstrlen(T));
substr (YS stelen(T));
strcat (XY);
A 〞 cdefgh 〞 B 〞 cdxyzw 〞
C 〞 cdefxy 〞 D 〞 cdefef 〞
多维数组之所以有行优先顺序和列优先顺序两种存储方式是因为()
A 数组的元素处在行和列两个关系中 B 数组的元素必须从左到右顺序排列
C 数组的元素之间存在次序关系 D 数组是多维结构内存是一维结构
从广义表 LS =( (p q) r s )中分解出原子 q 的运算是()
A tail (head (LS)) B head (tail (head (LS)))
C head (tail (LS)) D tail (tail (head (LS)))
在具有 n 个叶子结点的严格二叉树中结点总数为()
A n+ B n
C n D n
若 是有向图的一条边则称()
A v i 邻接于 v j B v j 邻接于 v i
C v i 和 v j 相互邻接 D v i 与 v j 不相邻接
在一个带权连通图 G 中权值最小的边一定包含在 G 的()
A 最小生成树中 B 深度优先生成树中
C 广度优先生成树中 D 深度优先生成森林中
当在二叉排序树中插入一个新结点时若树中不存在与待插入结点的关键字相同的结点且新结点的关键字小于根结点的关键字则新结点将成为()
A 左子树的叶子结点 B 左子树的分支结点
C 右子树的叶子结点 D 右子树的分支结点
希尔排序的增量序列必须是()
A 递增的 B 随机的
C 递减的 D 非递减的
如果在排序过程中每次均将一个待排序的记录按关键字大小加入到前面已经有序的子表中的适当位置则该排序方法称为()
A 插入排序 B 归并排序
C 冒泡排序 D 堆排序
设置溢出区的文件是()
A 索引非顺序文件 B ISAM 文件
C VSAM 文件 D 顺序文件
二填空题(本大题共 小题每小题 分共 分)
请在每小题的空格中填上正确答案错填不填均无分
下列程序段的时间复杂度为 ________________
product = ;
for (i = n;i>; i)
for (j = i+; j product *=j;
17 .已知指针 p 指向单链表中某个结点，则语句 p -> next =p -> next -> next 的作用是 ________________ 。tw.wINgWIt.cOM
18 .假设元素只能按 a,b,c,d 的顺序依次进栈，且得到的出栈序列中的第一个元素为 c ，则可能得到的出栈序列为 ________________ ，不可能得到的出栈序列为 ________________ 。
19 .若链串结点中的指针占 4 个字节，每个字符占 1 个字节，则结点大小为 2 的链串的存储密度为 ________________ 。
20 .右图表示的广义表为 ________________ 。
21 .若一棵满三叉树中含有 121 个结点，则该
树的深度为 ________________ 。
22 .若以邻接矩阵表示有向图，则邻接矩阵上
第 i 行中非零元素的个数即为顶点 v i 的 ________________ 。
23 .若希望只进行 8 趟排序便能在 4800 个元素中找出其中值最小的 8 个元素，并且要求排序过程中所进行的关键字比较次数尽可能少，则应该选用 ________________ 排序方法。
24 .在含 20 个关键字的 3 阶 B 树( 2 - 3 树)上查找一个关键字，至多需要访问 ___________ 次外存。
25 .文件上的两类主要操作为 ________________ 和 ________________ 。
三、解答题(本大题共 4 小题，每小题 5 分，共 20 分)
26 .设栈 S1 的入栈序列为 1 2 3 4 (每个数字为 13 个元素)，则不可能得到出栈序列 3142 。但可通过增设栈 S2 来实现。例如，按下图中的箭头指示，依次经过栈 S1 和 S2 ，便可得到序列 3 1 4 2 。
如果用 H1 和 H2 分别表示栈 S1 和 S2 的进栈操作，用 P1 和 P2 分别表示两个栈的出栈操作，则得到 3 1 4 2 的一个操作步骤为
H1 ， H1 ， H1 ， P1 ， H2 ， P2 ， P1 ， H2 ， P1 ， H2 ， P2 ， H1 ， P1 ， H2 ， P2 ， P2
请仿照上例写出利用两个栈从 1 2 3 4 得到 4 1 3 2 的操作步骤。
27 .已知树如右图所示，
( 1 )写出该树的后序序列;
( 2 )画出由该树转换得到的二叉树。
28 .为关键字( 17 ， 33 ， 31 ， 40 ， 48 )构造一个长度为 7 的散列表，设散列函数为 h(key)=key%7, 用开放定址法解决沖突的探查序列是
hi = (h(key) + i(key%5+1))%7 0 ≤ i ≤ 6
( 1 )画出构造所得的散列表;
( 2 )求出在等概率情况下查找成功时的平均查找长度。
29 .已知 R [ 1..8 ]中的元素依次为( 12 ， 5 ， 9 ， 20 ， 6 ， 31 ， 24 ， 27 )，写出按算法 MergeSortDC 对 R 进行自顶向下的二路归并排序过程中，前 5 次调用函数 Merge(R, low, mid, high) 时参数 low, mid 和 high 的值。
void MergeSortDC (int R[], int low, int mid, int high )
{
int mid;
if (low {
mid = (low +high)/2;
MergeSortDC (R, low, mid);
MergeSortDC (R, mid+1, high);
Merge (R, low, mid, high);
}
} // MergeSortDC
( 1 )第一次调用时的参数值;
( 2 )第二次调用时的参数值;
( 3 )第三次调用时的参数值;
( 4 )第四次调用时的参数值;
( 5 )第五次调用时的参数值;
四、算法阅读题(本大题共 4 小题，每小题 5 分，共 20 分)
30 .下列函数的功能是，对以带头结点的单链表作为存储结构的两个递增有序表(表中不存在值相同的数据元素)进行如下操作：将所有在 Lb 表中存在而 La 表中不存在的结点插入到 La 中，其中 La 和 Lb 分别为两个链表的头指针。请在空缺处填入合适内容，使其成为一个完整的算法。
void union (LinkList La, LinkList Lb)
{
// 本算法的功能是将所有 Lb 表中存在而 La 表中不存在的结点插入到 La 表中
LinkList pre = La, q;
LinkList pa = La -> next;
LinkList pb = Lb -> next;
free (Lb);
while (pa && pd)
{
if (pa -> data data)
{ pre = pa; pa = pa -> next;}
else if (pa -> data > pb ->data)
{
(1) ;
pre = pb;
pb = pb -> next;
(2) ;
}
else
{
q = pb; pb = pb -> next; free (q);
}
}
if (pb)
(3) ;
}
(1)
(2)
(3)
31 .已知串的存储结构为动态存储分配的顺序串。阅读下列算法，并<
