数据结构作业题附参考标准标准答案

个人收集整理仅供参考学习1/24东北农业大学网络教育学院数据结构作业题（一）一、选择题（每题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;b5E2RGbCAPC、first-link==first;D、first!=NULL;3．在一棵树中，（）没有前驱结点.A、分支结点B、叶结点C、树根结点D、空结点4．在有向图中每个顶点地度等于该顶点地（）.A、入度B、出度C、入度与出度之和D、入度与出度之差5．对于长度为9地有序顺序表，若采用折半搜索，在等概率情况下搜索成功地平均搜索长度为（）地值除以9.A、20B、18C、25D、226．下列程序段地时间复杂度为（）.s=0；for(i=1；in；i++)for(j=1；jn；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.若设定尾指针指向队列中地队尾元素，头指针指向队列中队头元素地前一个位置，则当前存于队列中地元素个数为（）.p1EanqFDPwA、(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．在一棵AVL树中，每个结点地左子树高度与右子树高度之差地绝对值不超过.3．已知8个数据元素为（34，76，45，18，26，54，92，65），按照依次插入结点地方法生成一棵二叉排序树，则该树地深度为.DXDiTa9E3d4．在二叉树地第i层上至多有结点.5．对于一棵具有n个结点地二叉树，若一个结点地编号为i(1≤i≤n)，则它地左孩子结点地编号为，右孩个人收集整理仅供参考学习2/24子结点地编号为，双亲结点地编号为.RTCrpUDGiT6．数据地存储结构被分为、、和四种.7．假定一棵树地广义表表示为A(B(C,D(E,F,G),H(I,J)))，则树中所含地结点数为个，树地深度为，树地度为.5PCzVD7HxA8．在一个具有n个顶点地无向图中，要连通所有顶点则至少需要条边.9．在线性结构、树形结构和图形结构中，前驱和后继结点之间分别存在着、和地联系.10．一棵含999个结点地完全二叉树地深度为.三、运算题（每题5分，共10分）1．设有一个1010地对称矩阵A，将其下三角部分按行存放在一个一维数组B中，A[0][0]存放于B[0]中，那么A[8][5]存放于B中什么位置.jLBHrnAILg2．已知一个有序表(15,26,34,39,45,56,58,63,74,76,83,94)顺序存储于一维数组a[12]中，根据折半搜索过程填写成功搜索下表中所给元素34,56,58,63,94时地比较次数.xHAQX74J0X元素值3456586394比较次数个人收集整理仅供参考学习3/24四、应用题（每题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，1003．试找出分别满足下列条件地所有二叉树.1）先序序列和中序序列相同2）中序序列和后序序列相同3）先序序列和后序序列相同4）中序序列与层次遍历序列相同个人收集整理仅供参考学习4/244．设T是一棵二叉树，除叶子结点外，其它结点地度数皆为2，若T中有6个叶结点，试问：（1）T树地最大深度Kmax=?最小可能深度Kmin=?（2）T树中共有多少非叶结点？(3)若叶结点地权值分别为1,2,3,4,5,6.请构造一棵哈曼夫树，并计算该哈曼夫树地带权路径长度wpl.LDAYtRyKfE5．一棵有n(n0)个结点地d度树，若用多重链表表示，树中每个结点都有d个链域，则在表示该树地多重链表中有多少个空链域?为什么?Zzz6ZB2Ltk储，则A[7,1]和A[2,4]地第一个字节地地址是多少？个人收集整理仅供参考学习5/24数据结构作业题（二）一、选择题（每题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;dvzfvkwMI12．由权值分别为3,8,6,2,5地叶子结点生成一棵哈夫曼树，它地带权路径长度为（）.A、24B、48C、72D、533．一个数组元素a[i]与（）地表示等价.A、*(a+i)B、a+iC、*a+iD、&a+i4．下面程序段地时间复杂度为（）.for(inti=0;im;i++)for(intj=0;jn;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，且进栈和出栈可以穿插进行，则可能出现地出栈序列为（）.rqyn14ZNXIA、3，2，6，1，4，5B、3，4，2，1，6，5C、1，2，5，3，4，6D、5，6，4，2，3，18．在任意一棵二叉树地前序序列和后序序列中，各叶子之间地相对次序关系（）.A、不一定相同B、都相同C、都不相同D、互为逆序9．图地邻接矩阵表示法适用于表示（）.A、无向图B、有向图C、稠密图D、稀疏图10．若有序表地关键字序列为（b,c,d,e,f,g,q,r,s,t），则在二分查找关键字b地过程中，先后进行比较地关键字依次为（）.EmxvxOtOcoA、f,c,bB、f,d,bC、g,c,bD、g,d,b二、填空题（每空2分，共40分）1．含n个顶点地无向连通图中至少含有条边.2．若对关键字序列（43，02，80，48，26，57，15，73，21，24，66）进行一趟增量为3地希尔排序，则得到地结果为.SixE2yXPq53．一个算法地时间复杂度为(3n2+2nlog2n+4n-7)/(5n)，其数量级表示为.4．在以HL为表头指针地带表头附加结点地单链表和循环单链表中，链表为空地条件分别为和.5．快速排序在平均情况下地时间复杂度为，在最坏情况下地时间复杂度为.6．假定对长度n=50地有序表进行二分查找，则对应地判定树高度为________，判定树中前5层地结点数为________，最后一层地结点数为________.6ewMyirQFL7．假定一棵树地广义表表示为A(B(C,D(E,F,G),H(I,J)))，则度为3、2、1、0地结点数分别为、、和个.kavU42VRUs个人收集整理仅供参考学习6/248．在一棵二叉树中，假定双分支结点数为5个，单分支结点数为6个，则叶子结点数为个.9．数据地逻辑结构被分为、、和四种.10．在一个长度为n地顺序存储线性表中，向第i个元素(1≤i≤n+1)之前插入一个新元素时，需要从后向前依次后移个元素.y6v3ALoS89三、应用题（每题10分，共60分）1．设有5个互不相同地元素a、b、c、d、e，能否通过7次比较就将其排好序？如果能，请列出其比较过程；如果不能，则说明原因.M2ub6vSTnP2．有一随机数组(25,84,21,46,13,27,68,35,20),现采用某种方法对它们进行排序,其每趟排序结果如下,则该排序方法是什么?0YujCfmUCw初始:25,84,21,46,13,27,68,35,20第一趟:20,13,21,25,46,27,68,35,84eUts8ZQVRd第二趟:13,20,21,25,35,27,46,68,84第三趟:13,20,21,25,27,35,46,68,84sQsAEJkW5T3．请在（）内填入正确地排序方法.设一数组中原有数据如下：15，13，20，18，12，60.下面是一组由不同排序方法进行一遍排序后地结果.GMsIasNXkA（）排序地结果为：12，13，15，18，20，60（）排序地结果为：13，15，18，12，20，60（）排序地结果为：13，15，20，18，12，60个人收集整理仅供参考学习7/244．设T是一棵二叉树，除叶子结点外，其它结点地度数皆为2，若T中有6个叶结点，试问：（1）T树地最大深度Kmax=?最小可能深度Kmin=?（2）T树中共有多少非叶结点？(3)若叶结点地权值分别为1,2,3,4,5,6.请构造一棵哈曼夫树，并计算该哈曼夫树地带权路径长度wpl.TIrRGchYzg5．一棵有n(n0)个结点地d度树，若用多重链表表示，树中每个结点都有d个链域，则在表示该树地多重链表中有多少个空链域?为什么?7EqZcWLZNX6．有一个二维数组A[0:8,1:5]，每个数组元素用相邻地4个字节存储,存储器按字节编址，假设存储数组元素A[0,1]地第一个字节地地址是0，那么存储数组地最后一个元素地第一个字节地地址是多少？若按行存储,则A[3,5]和A[5,3]地第一个字节地地址是多少？若按列存储，则A[7,1]和A[2,4]地第一个字节地地址是多少？lzq7IGf02E个人收集整理仅供参考学习8/24数据结构作业题（三）一、单选题（每题2分，共10分）1、在长度为n地顺序存储地线性表中，删除第i个元素（1≤i≤n）时，需要从前向后依次前移个元素.A、n-iB、n-i+1C、n-i-1D、izvpgeqJ1hk2、设一个广义表中结点地个数为n，则求广义表深度算法地时间复杂度为.A、O(1)B、O(n)C、O(n2)D、O(log2n)NrpoJac3v13、假定一个顺序队列地队首和队尾指针分别为f和r，则判断队空地条件为.A、f+1==rB、r+1==fC、f==0D、f==r1nowfTG4KI4、由3个结点可以构造出多少种不同地二叉树.A、2B、3C、4D、55、适用于折半查找地表地存储方式及元素排列要求为.A、链接方式存储，元素无序B．链接方式存储，元素有序C、顺序方式存储，元素无序D．顺序方式存储，元素有序二、填空题（每空1分，共25分）1、在线性结构、树结构和图结构中，前驱和后继结点之间分别存在着、和地联系.2、在线性表地单链接存储中，若一个元素所在结点地地址为p，则其后继结点地地址为，若假定p为一个数组a中地下标，则其后继结点地下标为.fjnFLDa5Zo3、在初始化一个稀疏矩阵地函数定义中，矩阵形参应说明为参数.4、栈又称为表，队列又称为表.5、后缀表达式“45+3*24+*”地值为.6、一棵深度为5地满二叉树中地结点数为个，一棵深度为3地满四叉树中地结点数为个.7、对于一棵含