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

《数据结构作业题及参考答案》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、东北农业大学网络教育学院数据结构作业题（一）一、选择题（每题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、

2、出度C、入度与出度之和D、入度与出度之差5．对于长度为9的有序顺序表，若采用折半搜索，在等概率情况下搜索成功的平均搜索长度为（）的值除以9。A、20B、18C、25D、226．下列程序段的时间复杂度为（）。s=0；for(i=1；i

3、。若设定尾指针指向队列中的队尾元素，头指针指向队列中队头元素的前一个位置，则当前存于队列中的元素个数为（）。A、(rear-front-1)％nB、(rear-front)％nC、(front-rear+1)％nD、(rear-front+n)％n9．高度为5的完全二叉树中含有的结点数至少为（）。A、16B、17C、31D、3210．如图所示有向图的一个拓扑序列是()A、ABCDEFB、FCBEADC、FEDCBAD、DAEBCF二、填空题（每空1分，共20分）1．n(n﹥0)个顶点的无向图最多有条边，最少有条边。2．在一

4、棵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．

5、在一个具有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]中，根据折半搜索过程填写成功搜索下表中所给元

6、素34,56,58,63,94时的比较次数。元素值3456586394比较次数四、应用题（每题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

7、）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，1003．试找出分别满足下列条件的所有二叉树。1）先序序列和中序序列相同2）中序序列和后序序列相同3）先序序列和后序序列相同4）中序序列与层次遍历序列相同4．设T是一棵二叉树，除叶子结点外，其它结点的度数皆为2，若T中有6个叶结点，试问：（1）T树的最大深度Kmax=?最小可能深度Kmin=?（2）T树中共有多少非叶结点

8、？(3)若叶结点的权值分别为1,2,3,4,5,6。请构造一棵哈曼夫树，并计算该哈曼夫树的带权路径长度wpl。5．一棵有n(n>0)个结点的d度树，若用多重链表表示，树中每个结点都有d个链域，则在表示该树的多重链表中有多少个空链域?为什么?储，则A[7,1]和A[2,4]的第一个字节的地址是多少？数据结