数据结构高等教育自学考试

一 单项选择题(本大题共 小题 每小题 分 共 分)

在每小题列出的四个备选项中只有一个是符合题目要求的 请将其代码填写在题后的括号内 错选 多选或未选均无分

在数据结构中 数据的逻辑结构可以分成()

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 (X S strlen(T));

substr (Y S stelen(T) );

strcat (X Y);

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 的作用是 ________________ 。WiNGwit.

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)

一 单项选择题(本大题共 小题 每小题 分 共 分 在每小题的四个备选答案中 选出一个正确答案 并将正确答案的序号填在题干的括号内)

下面程序段的时间复杂度是( )

for(i= ;i

for(j=1;j

A[i][j]=0;

A.O(n) B.O(m+n+1) C.O(m+n) D.O(m*n)

2.在单链表中，指针p指向元素为x的结点，实现“删除x的后继”的语句是( )

A.p=p->next; B.p->next=p->next->next;

C.p->next=p; D.p=p->next->next;

3.在头指针为head且表长大于1的单循环链表中，指针p指向表中某个结点，若p->next->next=

head,则( )

A.p指向头结点 B.p指向尾结点

C.*p的直接后继是头结点 D.*P的直接后继是尾结点

4.判定“带头结点的链队列为空”的条件是( )

A.Q.front==NULL B.Q.rear==NULL

C.Q.front==Q.rear D.Q.front!=Q.rear

5.设有两个串T和P，求P在T中首次出现的位置的串运算称作( )

A.联接 B.求子串 C.字符定位 D.子串定位

6.广义表A=(a,(b),(),(c,d,e))的长度为( )

A.4 B.5 C.6 D.7

7.一棵含18个结点的二叉树的高度至少为( )

A.3 B.4 C.5 D.6

8.已知二叉树的先序序列为ABDECF，中序序列为DBEAFC，则后序序列为( )

A.DEBAFC B.DEFBCA C.DEBCFA D.DEBFCA

9.无向图中一个顶点的度是指图中( )

A.通过该顶点的简单路径数 B.与该顶点相邻接的顶点数

C.通过该顶点的回路数 D.与该顶点连通的顶点数

10.已知一个图如下所示，从顶点a出发进行广度优先遍历可能得到的序列为( )

A.a c e f b d

B.a c b d f e

C.a c b d e f

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个元素，按分块查找的要求等分成3块。若对索引表采用顺序查找来确定块，并在确定的块中进行顺序查找，则在查找概率相等的情况下，分块查找成功时的平均查找长度为( )

A.21 B.23 C.41 D.62

14.索引非顺序文件的特点是( )

A.主文件无序，索引表有序 B.主文件有序，索引表无序

C.主文件有序，索引表有序 D.主文件无序，索引表无序

15.倒排文件的主要优点是( )

A.便于进行插入和删除运算 B.便于进行文件的恢复

C.便于进行多关键字查询 D.节省存储空间

二、填空题 (本大题共10小题，每小题2分，若有两个空格，每个空格1分，共20分)

16.抽象数据类型的特点是将____________和____________封装在一起，从而现实信息隐藏。

17.从顺序表中删除一个元素时，表中所有在被删元素之后的元素均需____________一个位置。

18.在队列中，允许进行插入操作的一端称为____________，允许进行删除操作的一端称为____________。

19.如图两个栈共享一个向量空间，top1和top分别为指向两个栈顶元素的指针，则“栈满”的判定条件是____________。

20.设S1="good",S2=" ",S3="book"，则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，试为这6个字符设计哈夫曼编码。请先画出你所构造的哈夫曼树(要求树中左孩子结点的权值小于右孩子结点的权值)，然后分别写出每个字符对应的编码。

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.如图所示，利用同一循环向量空间实现两个队列，其类型Queue2定义如下：

typedef struct {

DataType data[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

if(i<0||i>1)return 0;

if( (1) )

return 0;

Q->data[ (2) ]=x;

Q->length[ (3) ]++;

return 1;

}

(1)

(2)

(3)

31.某二叉树的线索链表存储结构如图(b)所示，其中p为指向根结点的指针，图(a)为结点结构。阅读下列算法，并回答问题：

(1)写出执行函数调用f(p)的输出结果;

(2)简述函数f的功能。

{

while(t)

{

printf(t->data);

if(t->lchild)

t=t->lchild;

else

t=t->rchild;

}

}

(1)

(2)

32.下列函数FindCycle(G,i)的功能是，对一个采用邻接表作存储结构的有向图G，利用深度优先搜索策略寻找一条经过顶点v i 的简单回路。数组cycle_path用于保存搜索过程中形成的回路，cycle_path[k]=j(j≥0)表示在回路中顶点v k 的下一个顶点是v j 。请在空缺处填入合适的内容，使其成为一个完整的算法。

vertex firstedge

已知邻接表的顶点表结点结构为：

adjvex next

边表结点 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;

return DFSPath(G,i,i);

}

int DFSPath(ALGraph*G,int j,int i)

{

EdgeNode *p;

int cycled=0;

for(p=G->adjlist[j].firstedge;p&&!cycled;p=p->next)

{

cycle_path[j]=p->adjvex;

if( (1 ) )cycled=1;//已找到回路

else

if(cycle_path[p->adjvex]==-1)cycled= (2) ;

}

return (3)

}

(1)

(2)

(3)

33.阅读下列函数algo,并回答问题。

(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;

while (i!=(n+1)/2)

{

int x=L[s];

i=s;j=t;

while(i