数据结构试卷及答案

12. 设有向图G中的有向边的集合E={<1，2>，<2，3>，<1，4>，<4，5>，<5，3>，<4，6>，<6，5>}，则该图的一个拓扑序列为【124653】。

13. 下面程序段的功能是建立二叉树的算法，请在下划线处填上正确的内容。

typedef struct node {

int data;

struct node *lchild; 【struct node *rchild】; }bitree;

void createbitree(bitree *&bt) {

scanf(“%c”,&ch); if(ch=='#')

【bt=0】; else {

bt=(bitree*)malloc(sizeof(bitree));

bt->data=ch; 【createbitree(bt->lchild)】; createbitree(bt->rchild); } }

14. 下面程序段的功能是利用从尾部插入的方法建立单链表的算法，请在下划线处填上正确的内容。

typedef struct node {

int data;

struct node *next; } lklist;

void lklistcreate(【lklist】 *&head ) {

for (i=1;i<=n;i++)

{

p=(lklist *)malloc(sizeof(lklist)); scanf(“%d”,&(p->data)); p->next=0; if(i==1)

head=q=p; else {

q->next=p; 【q=p】; } } }

1. 4，10 2. 3. 4. 5.

O(nlog2n)，O(n2) n 1，2

n(m-1)+1

6. q->next

7. 线性结构，树型结构，图型结构 8. O(n2)， O(n+e) 9. 8/3

10. (38，13，27，10，65，76，97) 11. (10，13，27，76，65，97，38) 12. 124653

13. struct node *rchild，bt=0，createbitree(bt->lchild) 14. lklist，q=p

1. 设顺序循环队列Q[0：m-1]的队头指针和队尾指针分别为F和R，其中队头指针F指向当前队头元素的前一个位置，队尾指针R指向当前队尾元素所在的位置，则出队列的语句为【F =(F+1) % m;】。 2. 设线性表中有n个数据元素，则在顺序存储结构上实现顺序查找的平均时间复杂度为【O(n)】，在链式存储结构上实现顺序查找的平均时间复杂度为【O(n)】。 3. 设一棵二叉树中有n个结点，则当用二叉链表作为其存储结构时，该二叉链表中共有【2n】个指针域，【n+1】个空指针域。

4. 设指针变量p指向单链表中结点A，指针变量s指向被插入的结点B，则在结点A的后面插入结点B的操作序列为【s->next=p->next; s->next=s】。 5. 设无向图G中有n个顶点和e条边，则其对应的邻接表中有【n】个表头结点和【2e】个表结点。 6. 设无向图G中有n个顶点e条边，所有顶点的度数之和为m，则e和m有【m=2e】关系。 7. 设一棵二叉树的前序遍历序列和中序遍历序列均为ABC，则该二叉树的后序遍历序列为【CBA】。 8. 设一棵完全二叉树中有21个结点，如果按照从上到下、从左到右的顺序从1开始顺序编号，则编号为8的双亲结点的编号是【4】，编号为8的左孩子结点的编号是【16】。 9. 下列程序段的功能实现子串t在主串s中位置的算法，要求在下划线处填上正确语句。 int index(char s[ ], char t[ ]) {

i=j=0;

while(i

10. 设一个连通图G中有n个顶点e条边，则其最小生成树上有【n-1】条边。

1. (F+1) % m 2. O(n)，O(n)

3. 2n，n+1

4. s->next=p->next; s->next=s 5. n, 2e

6. m=2e 7. CBA 8. 4，16 9. i-j+1，0 10. n-1

1. 为了能有效地应用HASH查找技术，必须解决的两个问题是【构造一个好的HASH函数】和【确定解决冲突的方法】。 2. 下面程序段的功能实现数据x进栈，要求在下划线处填上正确的语句。 typedef struct {int s[100]; int top;} sqstack; void push(sqstack &stack,int x)

{

if (stack.top==m-1) printf(“overflow”);

else {【stack.top++】; 【stack.s[stack.top]=x】;} }

3. 中序遍历二叉排序树所得到的序列是【有序】序列（填有序或无序）。 4. 快速排序的最坏时间复杂度为【O(n2)】，平均时间复杂度为【O(nlog2n)】。

5. 设某棵二叉树中度数为0的结点数为N0，度数为1的结点数为N1，则该二叉树中度数为2的结点数为【N0-1】；若采用二叉链表作为该二叉树的存储结构，则该二叉树中共有【2N0+N1】个空指针域。

6. 设某无向图中顶点数和边数分别为n和e，所有顶点的度数之和为d，则e=【d/2】。

7. 设一组初始记录关键字序列为(55，63，44，38，75，80，31，56)，则利用筛选法建立的初始堆为【(31，38，54，56，75，80，55，63)】。

8. 设某无向图G的邻接表为，则从顶点V1开始的深度优先遍历序列为【(1，3，4，2)】；广度优先遍历序列为【(1，3，2，4)】。

1. 构造一个好的HASH函数，确定解决冲突的方法 2. stack.top++，stack.s[stack.top]=x 3. 有序

4. O(n2)，O(nlog2n) 5. N0-1，2N0+N1

6. d/2

7. (31，38，54，56，75，80，55，63) 8. (1，3，4，2)，(1，3，2，4)

计算题

1. 在如下数组A中链接存储了一个线性表，表头指针为A [0].next，试写出该线性表。 A 0 1 2 3 4 5 6 7

data next 3

2. 请画出下图的邻接矩阵和邻接表

3. 已知一个图的顶点集V和边集E分别为：

V={1,2,3,4,5,6,7}；

E={(1,2)3， (1,3)5， (1,4)8,，(2,5)10，(2,3)6，(3,4)15，(3,5)12，(3,6)9，(4,6)4，

(4,7)20，(5,6)18，(6,7)25}；

用克鲁斯卡尔算法得到最小生成树，试写出在最小生成树中依次得到的各条边。

4. 画出向小根堆中加入数据4, 2, 5, 8, 3时，每加入一个数据后堆的变化。

1. 线性表为：（78，50，40，60，34，90）

?0?1?12. 邻接矩阵： ???1

??060 5 50 7 78 2 90 0 34 4 40 1

101011101110101

0??1?1??1?0??

邻接表：

3. 用克鲁斯卡尔算法得到的最小生成树为：

(1,2)3, (4,6)4, (1,3)5, (1,4)8, (2,5)10, (4,7)20