数据结构作业题及参考答案

东北农业大学网络教育学院

数据结构作业题（一）

一、选择题（每题2分，共20分）

1．在一个长度为n的顺序表的任一位置插入一个新元素的渐进时间复杂度为（ ）。

A、O(n) B、O (n/2) C、O (1) D、O (n2)

2．带头结点的单链表first为空的判定条件是（ ）。

A、first == NULL; B、first->link == NULL;

C、first->link == first; D、first != NULL;

3．在一棵树中，（）没有前驱结点。

A、分支结点 B、叶结点 C、树根结点 D、空结点

4．在有向图中每个顶点的度等于该顶点的（）。

A、入度 B、出度

C、入度与出度之和 D、入度与出度之差

5．对于长度为9的有序顺序表，若采用折半搜索，在等概率情况下搜索成功的平均搜索长度为（）的值除以9。

A、20 B、18 C、25 D、22

6．下列程序段的时间复杂度为（）。

s=0；

for(i=1；i

for(j=1；j

s+=i*j；

A、O (1) B、O (n)C、O (2n) D、O (n2)

7．栈是一种操作受限的线性结构，其操作的主要特征是（ ）。

A、先进先出 B、后进先出C、进优于出 D、出优于进

8．假设以数组A[n]存放循环队列的元素，其头、尾指针分别为front和rear。若设定尾指针指向队列中的队尾元素，头指针指向队列中队头元素的前一个位置，则当前存于队列中的元素个数为（ ）。

A、(rear-front-1)％n B、(rear-front)％n

C、(front-rear+1)％n D、(rear-front+n)％n

9．高度为5的完全二叉树中含有的结点数至少为（ ）。

A、16B、17C、31 D、32

10．如图所示有向图的一个拓扑序列是( )

A、ABCDEF

B、FCBEAD

C、FEDCBA

D、DAEBCF

二、填空题（每空1分，共20分）

1．n (n﹥0) 个顶点的无向图最多有条边，最少有条边。

2．在一棵AVL树中，每个结点的左子树高度与右子树高度之差的绝对值不超过。

3．已知8个数据元素为（34，76，45，18，26，54，92，65），按照依次插入结点的方法生成一棵二叉排序树，则该树的深度为。

4．在二叉树的第i层上至多有结点。

5．对于一棵具有n个结点的二叉树，若一个结点的编号为i(1≤i≤n)，则它的左孩子结点的编号为，右孩子结点的编号为，双亲结点的编号为。

6．数据的存储结构被分为、、和四种。

7．假定一棵树的广义表表示为A(B(C,D(E,F,G),H(I,J)))，则树中所含的结点数为个，树的深度为，树的度为。

8．在一个具有n个顶点的无向图中，要连通所有顶点则至少需要条边。

9．在线性结构、树形结构和图形结构中，前驱和后继结点之间分别存在着、

和的联系。

10．一棵含999个结点的完全二叉树的深度为。

三、运算题（每题5分，共10分）

1．设有一个1010的对称矩阵A，将其下三角部分按行存放在一个一维数组B中，A[0][0]存放于B[0]中，那么A[8][5]存放于B中什么位置。

2．已知一个有序表 (15,26,34,39,45,56,58,63,74,76,83,94) 顺序存储于一维数组a[12]中，根据折半搜索过程填写成功搜索下表中所给元素34, 56, 58, 63, 94时的比较次数。

元素值 34 56 58 63 94

比较次数

四、应用题（每题10分，共50分）

1．设待排序的记录共7个，排序码分别为8，3，2，5，9，1，6。

（1）用直接插入排序。试以排序码序列的变化描述形式说明排序全过程（动态过程）要求按递减顺序排序。

（2）用直接选择排序。试以排序码序列的变化描述形式说明排序全过程（动态过程）要求按递减顺序排序。

2．判断下列序列是否是堆（可以是小堆，也可以是大堆，若不是堆，请将它们调整为堆）。

（1）100，85，98，77，80，60，82，40，20，10，66

（2）100，98，85，82，80，77，66，60，40，20，10

（3）100，85，40，77，80，60，66，98，82，10，20

（4）10，20，40，60，66，77，80， 82，85，98，100

3．试找出分别满足下列条件的所有二叉树。

1）先序序列和中序序列相同 2）中序序列和后序序列相同

3）先序序列和后序序列相同4）中序序列与层次遍历序列相同

4．设T是一棵二叉树，除叶子结点外，其它结点的度数皆为2，若 T中有6个叶结点，试问：

（1）T树的最大深度Kmax=?最小可能深度Kmin=?

（2）T树中共有多少非叶结点？

(3) 若叶结点的权值分别为1,2,3,4,5,6。请构造一棵哈曼夫树，并计算该哈曼夫树的带权路径长度wpl。

5．一棵有n(n>0)个结点的d度树，若用多重链表表示，树中每个结点都有d个链域，则在表示该树的多重链表中有多少个空链域? 为什么?

储，则A[7,1]和A[2,4]的第一个字节的地址是多少？

数据结构作业题（二）

一、选择题（每题2分，共20分）

1．在一个单链表HL中，若要向表头插入一个由指针p指向的结点，则执行（ ）。

A、HL=p; p->next=HL; B、p->next=HL; HL=p;

C、p->next=HL; p=HL; D、p->next=HL->next; HL->next=p;

2．由权值分别为3,8,6,2,5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（ ）。

A、24 B、48 C、72 D、53

3．一个数组元素a[i]与（ ）的表示等价。

A、*(a+i)B、a+iC、*a+i D、&a+i

4．下面程序段的时间复杂度为（ ）。

for(int i=0; i

for(int j=0; j

a[i][j]=i*j;

A、O(m2) B、O(n2) C、O(m*n) D、O(m+n)

5．数据结构是（ ）。

A、一种数据类型

B、数据的存储结构

C、一组性质相同的数据元素的集合

D、相互之间存在一种或多种特定关系的数据元素的集合

6．在线性表的下列运算中，不改变数据元素之间结构关系的运算是（ ）。

A、插入 B、删除 C、排序 D、定位

7．若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则可能出现的出栈序列为（ ）。

A、3，2，6，1，4，5 B、3，4，2，1，6，5

C、1，2，5，3，4，6 D、5，6，4，2，3，1

8．在任意一棵二叉树的前序序列和后序序列中，各叶子之间的相对次序关系（ ）。

A、不一定相同 B、都相同 C、都不相同 D、互为逆序

9．图的邻接矩阵表示法适用于表示（ ）。

A、无向图 B、有向图 C、稠密图 D、稀疏图

10．若有序表的关键字序列为（b,c,d,e,f,g,q,r,s,t），则在二分查找关键字b的过程中，先后进行比较的关键字依次为（ ）。

A、f,c,b B、f,d,b C、g,c,b D、g,d,b

二、填空题（每空2分，共40分）

1．含n个顶点的无向连通图中至少含有条边。

2．若对关键字序列（43，02，80，48，26，57，15，73，21，24，66）进行一趟增量为3的希尔排序，则得到的结果为。

3．一个算法的时间复杂度为(3n2+2nlog2n+4n-7)/(5n)，其数量级表示为。

4．在以HL为表头指针的带表头附加结点的单链表和循环单链表中，链表为空的条件分别为和。

5．快速排序在平均情况下的时间复杂度为，在最坏情况下的时间复杂度为。

6．假定对长度n=50的有序表进行二分查找，则对应的判定树高度为________，判定树中前5层的结点数为________，最后一层的结点数为________。

7．假定一棵树的广义表表示为A(B(C,D(E,F,G),H(I,J)))，则度为3、2、1、0的结点数分别为、、和个。

8．在一棵二叉树中，假定双分支结点数为5个，单分支结点数为6个，则叶子结点数为个。

9．数据的逻辑结构被分为、、和四种。