2013 1全国高等教育自学考试数据结构试题
下列程序段的时间复杂度是()
for(I =；我& ltn；i++)p = " " & gt；& lt/n；i++)& gt；
for(j = 1；j & ltm；j++)p = " " & gt；& lt/m；j++)>
a[I][j]= 0；
A.(m+n+1) C.O(m+n) D.O(m*n)
2.在单链表中，指针P指向元素为X的节点，实现“删除X的后继者”的语句是()。
p = p-& gt；接下来；b . p-& gt；next = p-& gt；下一个-& gt；接下来；
C.p->next = p；d . p = p-& gt；下一个-& gt；接下来；
3.在头指针、表长大于1的单循环链表中，指针P指向链表中的一个节点。如果P->；下一个-& gt；下一个=
头，然后()
A.p指向首节点B.p指向尾节点。
C.*p的直接后继是头节点D.*P的直接后继是尾节点。
4.判断“首节点链队列为空”的条件是()
A.Q.front==NULL
C.Q.front==Q.rear D.Q.front！=Q.rear
5.有两个字符串T和P，寻找P在T中第一次出现的位置的字符串操作叫做()。
A.Join B .查找子串c .字符定位d .子串定位
6.广义表A=(a，(b)，()，(c，d，e))的长度是()。
a4 b . 5 c . 6d . 7
7.具有18个节点的二叉树的高度至少为()。
a3 b . 4 c . 5d . 6
8.已知二叉树的前序序列为ABDECF，中间序列为DBEAFC，后序序列为()。
A.DEBCFA D.DEBFCA
9.无向图中顶点的度数指的是图的()
A.通过顶点b的简单路径的数目。与该顶点相邻的顶点的数目
C.通过顶点的回路数d .与该顶点相连的顶点数
10.已知下图，从顶点A开始广度优先遍历得到的可能序列是()。
英法德
英国航空公司
英国皇家航空公司
D.a c d b f e
11.在以下排序方法中，平均时间性能为O(nlogn)，空间性能最好的是()。
A.快速排序b .堆排序c .归并排序d .基数排序
12.一组关键字称为{25，48，36，72，79，82，23，40，16，35}，其中每两个相邻的关键字是有序子序列。合并这些子序列的结果。WingwIT.CoM是()。
A.{25,36,48,72,23,40,79,82,16,35}
B.{25,36,48,72,16,23,40,79,82,35}
C.{25,36,48,72,16,23,35,40,79,82}
D.{16,23,25,35,36,40,48,72,79,82}
13.设顺序存储的线性表* * *有123个元素，按照块搜索的要求分为三块。如果索引表使用顺序搜索来确定块，并在所确定的块中执行顺序搜索，则当搜索概率相等时，块搜索成功时的平均搜索长度为()。
21
14.索引非顺序文件的特点是()
A.主文件有问题，索引表有问题。b .主文件有序，索引表无序。
C.主文件有序，索引表有序。d .主文件乱序，索引表乱序。
15.倒排文件的主要优点是()
A.易于插入和删除操作b .易于恢复文件。
c、方便多关键字查询D、节省存储空间。
二、填空(这个大题是***10小题，每个小题2分，如果有两个空格，每个空格1分，* * 20分)。
16.抽象数据类型的特点是把_ _ _ _ _ _ _ _ _和_ _ _ _ _ _ _ _封装在一起，这样真实的信息就隐藏起来了。
17.从顺序表中删除元素时，表中被删除元素之后的所有元素都需要一个_ _ _ _ _ _ _ _ _位置。
18.在队列中，允许插入操作的末端称为_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
19.如图所示，两个栈* * *共用一个向量空间，top1和top分别是指向两个栈顶元素的指针，所以“满栈”的判断条件是_ _ _ _ _ _ _ _ _ _。
20.设S1=“好”，S2=“”，S3=“书”，那么S1，S2和S3依次相连，结果是_ _ _ _ _ _ _ _ _。
21.假设三维数组A[10][9][8]按行优先级顺序存储，如果每个元素占用3个存储单元，首地址为100，则元素A[9][8][7]的存储地址为_ _ _ _ _ _ _ _。
22.已知在一个有n个节点的树中，只有度为k的分支节点和度为0的叶节点，所以树中包含的叶节点数为_ _ _ _ _ _ _ _ _ _。
23.能成功完成拓扑排序的图一定是_ _ _ _ _ _ _ _ _ _。
24.如果排序前关键字顺序接近正序或逆序，那么在堆排序和快速排序之间选择_ _ _ _ _ _ _ _ _ _ _ _更合适。
25.假设哈希表的表长为m，哈希函数为H(key)，如果用线性探针法解决冲突，探针地址序列的形式表示为_ _ _ _ _ _ _ _ _ _。
三、解决问题(这个大问题***4个小问题，每个小问题5分，***20分)
26.假设通信消息中使用的字符集为{a，b，c，d，e，f}，消息中第一个字符出现的频率为34，5，12，23，8，18，试着为这六个字符设计霍夫曼编码。请先画出你构造的霍夫曼树(要求树中左边子节点的权重小于右边子节点的权重)，然后分别写出每个字符对应的代码。
27.已知一个图如下图所示，其顶点按照A、B、C、D、E、f的顺序存储在邻接表的顶点表中，请画出这个图的邻接表，使得根据这个邻接表进行深度优先遍历得到的顶点序列为acbefd，广度优先遍历得到的顶点序列为acbdfe。
28.两个已知的4×5稀疏矩阵的三元表如下:
0 1 4 16 0 1 1 32
1 2 2 18 1 2 2 - 22
2 3 4 - 25 2 2 5 69
3 4 2 28 3 3 4 25
4 4 2 51
请画出这两个稀疏矩阵之和的三元表。
29.从空树开始，依次插入关键字40，8，90，15，62，95，12，23，56，32，构建一棵二叉排序树。
(1)画出二叉树。
(2)删除树中元素值为90的节点后，画一棵二叉排序树。
四、算法阅读题(本大题***4小题，每小题5分，***20分)
30.如图所示，两个队列使用相同的循环向量空间实现，队列2的类型定义如下:
typedef结构{
数据类型数据[MaxSize]；
int front[2]，length[2]；
} Queue2
对于i=0或1，front[i]和length[i]分别是第I个队列的头指针和长度字段。请在空白处填入适当的内容，实现第I个循环队列的入队操作。
int EnQueue(Queue2*Q，int i，DataType x)
{//如果第I个队列不满足，元素X进入队列，返回1，否则返回0。
如果(我& lt0 | | i & gt1)返回0；
如果((1))
返回0；
q->；data[(2)]= x；
q->；长度[(3)]++；
返回1；
}
(1)
(2)
(3)
31.二叉树的线索列表的存储结构如图(b)所示，其中P是指向根节点的指针，图(a)是节点结构。阅读以下算法并回答问题:
(1)写执行函数调用f(p)的输出结果；
(2)简述函数f的作用。
void f(二叉树t) {
while(t)
{
printf(t-& gt；数据)；
if(t->；lchild)
t = t-& gt；lchild
其他
t = t-& gt；rchild
}
}
(1)
(2)
32.下面这个函数FindCycle(G，I)的作用是对一个以邻接表为存储结构的有向图G采用深度优先搜索策略，找到一个通过顶点v i的简单回路。数组cycle_path用于保存搜索过程中形成的循环，cycle_path[k]=j(j≥0)表示循环中顶点v k的下一个顶点是v j，请在空白处填入适当的内容，使其成为一个完整的算法。
顶点第一边
已知邻接表的顶点表的节点结构是:
接下来是adjvex
边表节点EdgeNode的结构是:
int cycle _ path[MaxNum]；
int FindCycle(ALGraph*G，int i)
{//如果存在循环，返回1，否则返回0。
int j；
for(j = 0；j n；j++)cycle _ path[j]=-1；
返回DFSPath(G，I，I)；
}
int DFSPath(代数*G，int j，int i)
{
edge node * p；
int cycled = 0；
for(p = G-& gt；adjlist[j]。firstedge宝洁公司。& amp！循环；p = p-& gt；下一个)
{
cycle _ path[j]= p-& gt；adjvex
如果((1))循环= 1；//找到电路。
其他
if(循环路径[p-& gt；adjvex]==-1)循环=(2)；
}
回归(三)
}
(1)
(2)
(3)
33.阅读下面的函数算法并回答问题。
(1)假设整数数组A [1...8]依次是(3，8，9，1，7，4，2，6)。执行函数调用algo(A，8)时，外层while的循环体执行多少次？函数的返回值是什么？
(2)简述algo(L，n)的作用。
int algo(int L[]，intn)
{
int i=0，j，s=1，t = n；
而(我！=(n+1)/2)
{
int x = L[s]；
I = s；j = t；
while(我& ltj)p = " " & gt；& lt/j)>