2013年6月全国高等教育自学考试数据结构试题。
每个子问题所列的四个选项中，只有一个符合题目要求。请在题目后的括号里填上它的代码，选多不选都无所谓。
在数据结构中，数据的逻辑结构可以分为()
a内部结构和外部结构b线性结构和非线性结构
c紧密结构和非紧密结构D动态结构和静态结构
在以单链表为存储结构的线性表中，数据元素之间的逻辑关系用()表示
a数据元素的相邻地址表示表中b数据元素的序列号表示。
指向后继元素的指针表示D数据元素的值表示。
设P指向单链表中的一个节点S，指向要插入的节点，那么下面程序段的作用是()
s & gtnext = p & gt接下来；p & gtnext = s；
t = p & gt数据；p & gtdata = s & gt数据；s & gt数据= t；
交换节点A *p和节点S的数据字段。
在p指向的节点的元素前插入元素。
在p指向的节点的元素后插入一个元素。
d在节点* p之前插入节点*s。
堆栈和队列都是()
受限访问位置的线性结构顺序存储的线性结构
C链存储的线性结构和D受限访问位置的非线性结构
如果数组s[ n]是两个栈S和S的* * *存储空间，并且只有当s[ n]满了，每个栈都进不了栈，那么为这两个栈分配空间的最佳方案是S和S的栈顶指针的初始值分别为()。
a和n+ B和n/
c和nd和n+
执行下面的程序段后，字符串X的值是()
s =『abcdefgh』；t =『xyzw』；
substr(X S strlen(T))；
substr (Y S中柱(T))；
strcat(X Y)；
a〔cdefgh〕B〔cdxyzw〕
c〔cdefxy〕D〔cdefef〕
多维数组有两种存储方法，行优先级和列优先级，因为()
数组A的元素是行列关系，数组B的元素必须按从左到右的顺序排列。
C数组的元素之间是有顺序关系的。d数组是多维结构，内存是一维结构。
从广义表LS =( (p q) r s)，分解原子q的运算是()。
a尾(头(LS)) B头(尾(头(LS))
c头(尾(LS)) D尾(尾(头(LS)))
在具有n个叶节点的严格二叉树中，节点总数是()
一个名词+一个名词
中国日报
有向图的一条边叫做()
A v i与v j相邻B v j与v i相邻
C v i和v j相邻，D v i和v j不相邻。
在一个加权连通图G中，具有最小权重的边必定包含在G的()中。
在最小生成树中，b是深度第一的生成树
c宽度优先生成树和D深度优先生成林
在二叉排序树中插入新节点时，如果树中没有与待插入节点关键字相同的节点，且新节点的关键字小于根节点的关键字，则新节点将成为()。
左子树的叶节点左子树的分支节点
C右子树的叶节点D右子树的分支节点
希尔排序的增量序列必须是()
a递增b随机
c递减，d不递减。
如果在排序过程中，每次根据关键字大小将一条要排序的记录添加到先前排序的子表中的适当位置，则调用排序方法()。
插入排序b合并排序
c冒泡排序d堆排序
设置溢出区的文件是()
a索引非顺序文件B ISAM文件
VSAM文件d序列文件
填空题(这个大题* *小题* *每个小题加分)
请在每个小问题的空白处填上正确答案，填错与否都没关系。
下列程序段的时间复杂度是_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
产品=；
for(I = n；我& gt；我)
for(j = I+；j & ltn；j++)
乘积* = j；
17.已知指针P指向单链表中的一个节点，那么语句P->；next = p-& gt；下一个-& gt；next的功能是_ _ _ _ _ _ _ _ _ _ _。温维特。
65438+
19.如果链串节点中的指针占4个字节，每个字符占1个字节，那么节点大小为2的链串的存储密度是_ _ _ _ _ _ _ _ _ _ _ _ _ _。
20.右图所示的概化表是_ _ _ _ _ _ _ _ _ _ _ _ _ _。
21.如果一个完整的三叉戟树包含121个节点，那么
这棵树的深度是_ _ _ _ _ _ _ _ _ _ _。
22.如果有向图用邻接矩阵表示，邻接矩阵
第I行中非零元素的个数是顶点v的_ _ _ _ _ _ _ _ _ _ _ _ _ _。
23.如果只想通过8次排序找出4800个元素中值最小的8个元素，又想在排序过程中尽可能少的比较关键词，那么就应该选择_ _ _ _ _ _ _ _ _ _ _ _ _ _ _排序方式。
24.要在包含20个关键字的三阶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)。写的是函数Merge(R，low，mid，high根据MergeSortDC算法在R的自顶向下的双向合并排序过程中调用了5次。
void MergeSortDC (int R[]，int low，int mid，int high)
{
int mid
if(低& lt高)p = " " & gt& lt/high)>
{
mid =(低+高)/2；
MergeSortDC (R，低，中)；
MergeSortDC (R，mid+1，高)；
合并(R，低，中，高)；
}
} // MergeSortDC
(1)第一次调用时的参数值；
(2)第二次调用的参数值；
(3)第三次调用的参数值；
(4)第四次调用时的参数值；
(5)第五次调用的参数值；
四、算法阅读题(本大题*** 4小题，每小题5分，*** 20分)
30.下面这个函数的作用是以前导节点的单链表为存储结构，对两个增量有序表(表中没有相同值的数据元素)进行如下操作:将Lb表中存在而La表中没有的所有节点插入La中，其中La和Lb分别是两个链表的头指针。请在空白处填入适当的内容，使之成为一个完整的算法。
无效联合(链表La，链表Lb)
{
//这个算法的作用是将Lb表中存在而La表中不存在的所有节点插入La表中。
LinkList pre = La，q；
链表pa = La-& gt；接下来；
链表pb = Lb ->。接下来；
免费(磅)；
而(pa & amp& amppd)
{
如果(pa-& gt；数据资料)
{ pre = papa = pa-& gt；接下来；}
else if(pa-& gt；数据& gtpb - >数据)
{
(1) ;
pre = pb
Pb = p B- & gt；接下来；
(2) ;
}
其他
{
q = pbPb = p B- & gt；接下来；免费(q)；
}
}
中频(铅)
(3) ;
}
(1)
(2)
(3)