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

-东北农业大学网络教育学院数据结构作业题（一）一、选择题（每题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、20B、18C、25D、226下列程序段的时间复杂度为（ ）。 s=0； for(i=1；in；i+) for(j=1；j0)个结点的d度树，若用多重链表表示，树中每个结点都有d个链域，则在表示该树的多重链表中有多少个空链域? 为什么?储，则A7,1和A2,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、533一个数组元素ai与（ ）的表示等价。A、*(a+i)B、a+iC、*a+iD、&a+i 4下面程序段的时间复杂度为（ ）。 for(int i=0; im; i+) for(int j=0; j0)个结点的d度树，若用多重链表表示，树中每个结点都有d个链域，则在表示该树的多重链表中有多少个空链域? 为什么?6有一个二维数组A0:8,1:5，每个数组元素用相邻的4个字节存储,存储器按字节编址，假设存储数组元素A0,1的第一个字节的地址是0，那么存储数组的最后一个元素的第一个字节的地址是多少？若按行存储,则A3,5和A5,3的第一个字节的地址是多少？若按列存储，则A7,1和A2,4的第一个字节的地址是多少？数据结构作业题（三）一、单选题（每题2分，共10分）1、在长度为n的顺序存储的线性表中，删除第i个元素（1in）时，需要从前向后依次前移 个元素。A、n-i B、n-i+1 C、n-i-1 D、i2、设一个广义表中结点的个数为n，则求广义表深度算法的时间复杂度为 。A、O(1) B、O(n) C、O(n2) D、O(log 2 n)3、假定一个顺序队列的队首和队尾指针分别为f和r，则判断队空的条件为 。A、f+1=r B、r+1=f C、f=0 D、f=r4、由3 个结点可以构造出多少种不同的二叉树 。A、2 B、3 C、4 D、5 5、适用于折半查找的表的存储方式及元素排列要求为 。A、链接方式存储，元素无序 B链接方式存储，元素有序C、顺序方式存储，元素无序 D顺序方式存储，元素有序二、填空题（每空1分，共25分）1、在线性结构、树结构和图结构中，前驱和后继结点之间分别存在着 、 和 的联系。 2、在线性表的单链接存储中，若一个元素所在结点的地址为p，则其后继结点的地址为 ，若假定p为一个数组a中的下标，则其后继结点的下标为 。 3、在初始化一个稀疏矩阵的函数定义中，矩阵形参应说明为 参数。 4、栈又称为 表，队列又称为 表。 5、后缀表达式“4 5 + 3 * 2 4 + * ”的值为 。 6、一棵深度为5的满二叉树中的结点数为 个，一棵深度为3的满四叉树中的结点数为 个。 7、对于一棵含有40个结点的理想平衡树，它的高度为 。 8、从一棵二叉搜索树中查找一个元素时，若元素的值等于根结点的值，则表明 ，若元素的值小于根结点的值，则继续向 查找，若元素的值大于根结点的值，则继续向 查找。 9、对于一个具有n个顶点的图，若采用邻接矩阵表示，则矩阵大小为 。10、对于一个具有n个顶点和e条边的连通图，其生成树中顶点数和边数分别为 和 。 11、二分查找过程所对应的判定树既是一棵 ，又是一棵 。12、在归并排序中，进行每趟归并的时间复杂度为 ，整个排序过程的时间复杂度为 ，空间复杂度为 。13、给定一组数据6，2，7，10，3，12以它构造一棵哈夫曼树，则树高为_，带权路径长度WPL的值为_。三、运算题（每题6分，共24分） 1、假定一棵普通树的广义表表示为 a(b(e),c(f(h,i,j),g),d)，分别写出先根、后根、按层遍历的结果。先根： 。后根： 。按层： 。 2、已知一个带权图的顶点集V和边集G分别为： V = 0，1，2，3，4，5，6，7； E = （0，1）8，（0，2）5，（0，3）2，（1，5）6，（2，3）25，（2，4）13， （3，5）9，（3，6）10，（4，6）4，（5，7）20 ； 则求出该图的最小生成树的权。最小生成树的权： 。 3、对于线性表（18,25,63,50,42,32,90,66）进行散列存储时，若选用H(K)=K%9作为散列函数，则散列地址为0的元素有 个，散列地址为3的元素有 个，散列地址为5的元素有 个。 4、假定一组记录的排序码为（46，79，56，38，40，80，25，34），在对其进行快速排序的过程中，对应二叉搜索树的深度为 ，分支结点数为 。四、阅读算法（第一题7分，第二题8分） 1、void AA(LNode * & HL) InitList(HL); InsertRear(HL,30); InsertRear(HL,50);int a5 = 15,8,9,26,12;for ( int i=0; i=HBT.heapj) break; HBT.heapi=HBT.heapj; i=j; HBT.heapi=x; 该算法的功能为： 。五、算法填空，在画有横线的地方填写合适的内容。（12分）从一维数组An中二分查找关键字为K的元素的递归算法，若查找成功则返回对应元素的下标，否则返回-1。int Binsch( ElemType A , int low , int high , KeyType K ) if ( low=high )int mid = (low+high)/2;if ( K=Amid.key) ; else if (KLlink=q;q-Rlink=p;p-Llink-Rlink=q;q-Llink=q；B. p-Llink=q;p-Llink-Rlink=q;q-Rlink=p;q-Llink=p-Llink;C. q-Rlink=p;q-Llink=p-Llink;p-Llink-Rlink=q;p-Llink=q;D. q-Llink=p-Llink;q-Rlink=q;p-Llink=q;p-Llink=q;6若一个栈的输入序列为1,2,3,n，输出序列的第一个元素是i，则第j个输出元素是（ ）。 A. i-j-1 B. i-j C. j-i+1 D. 不确定的7有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列？（ ）A. 5 4 3 6 1 2 B. 4 5 3 1 2 6 C. 3 4 6 5 2 1 D. 2 3 4 1 5 6 8用链接方式存储的队列，在进行删除运算时（ ）。A. 仅修改头指针 B. 仅修改尾指针 C. 头、尾指针都要修改D. 头、尾指针可能都要修改9若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少？( ) A. 1和 5 B. 2和4 C. 4和2 D. 5和1 10栈和队列的共同点是（ ）。A. 都是先进先出 B. 都是先进后出 C. 只允许在端点处插入和删除元素 D. 没有共同点二、填空题（每空2分，共30分）1数据结构中评价算法的两个重要指标是 和 。2一个算法具有5个特性: 、 、 ，有零个或多个输入、有一个或多个输出。3在一个长度为n的顺序表中第i个元素（1=i=n）之前插入一个元素时，需向后移动_个元素。4对于双向链表,在两个结点之间插入一个新结点需修改的指针共 _个，单链表为_个。5设数组a1.50,1.80的基地址为2000，每个元素占2个存储单元，若以行序为主序顺序存储，则元素a45,68的存储地址为_ _;若以列序为主序顺序存储，则元素a45,68的存储地址为_ _。6所谓稀疏矩阵指的是_。7广义表的_ 定义为广义表中括弧的重数。8具有256个结点的完全二叉树的深度为_。9已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点，则该树有_个叶子结点。10高度为8的完全二叉树至少有_个叶子结点。三、计算题（每题6分，共30分）1如果输入序列为1 2 3 4 5 6,试问能否通过栈结构得到以下两个序列:4 3 5 6 1 2和1 3 5 4 2 6;请说明为什么不能或如何才能得到。2假定一棵二叉树广义表表示为a(b(c),d(e,f)，分别写出对它进行先序、中序、后序、按层遍历的结果。先序：中序：后序：按层：3已知一个图的顶点集V和边集G分别为：V=0,1,2,3,4,5,6,7;E=(0,1)8,(0,2)5,(0,3)2,(1,5)6,(2,3)25,(2,4)13,(3,5)9,(3,6)10, (4,6)4,(5,7)20,(6,7)30;按照普里姆算法从顶点0出发得到最小生成树，试写出在生成最小生成树的过程中依次得到的各条边。_, _, _, _, _, _, _。4. 已知一个图的顶点集V和边集G分别为：V=0,1,2,3,4,5,6,7,8;E=,;若存储它采用邻接表，并且每个顶点邻接表中的边结点都是按照终点序号从小到大的次序链接的，则按主教材中介绍的进行拓扑排序的算法，写出得到的拓扑序列（提示：先画出对应的图形，然后再运算）。拓扑序列：5假定一组记录的排序码为(46,79,56,38,40,80,25,34)，则对其进行快速排序的第一次划分后的结果为_。四、算法填空（10分）1 五、编程（10分）1设计算法以求解从集合1.n中选取k（knext=p一next；p一next=q；B p一next=q一next；q=p；C 9一next=p一next；p一next=q；D p一next=q一next；q一next=p；3在一个顺序队列中，队首指针指向队首元素的（ ）位置。A前一个 B后一个 C当前4向二叉搜索树中插入一个元素时，其时间复杂度大致为（ ）。A O（1） B O（1og2n）C O（n） D O（nlog2n）5假设有两个串A和B，求B在A中首次出现的位置的操作，我们称为（ ）。A.连接B.模式匹配 C.求子串 D.求串长6我们对记录进行排序的目的是（ ）。A.分类 B.合并 C.存储 D.查找7在最坏的情况下，冒泡排序法的时间复杂度为（ ）。A.O(lgn) B.O(nlgn) C.O(n2) D.O(n)8广义表(A,B,E,F,G)的表尾是（ ）。A.(B, E , F, G) B.( )C.（A，B， E，F，G) D.（G）9线性表如果采用链式存储结构，要求内存中的存储单元的地址（ ）。A.必须是连续的B.部分要求是连续的C.一定不是连续的D.可以是连续的，也可以是不连续的10在数据结构中，从逻辑结构上，我们可以把数据结构分为（ ）。A.线性结构和非线性结构B.内部结构和外部结构C.顺序结构和链式结构 D.动态结构和静态结构二、填空题（每空1分，共25分）1数据的逻辑结构被分为 、 、 和 四种。2对于一个长度为n的顺序存储的线性表，在表头插入元素的时间复杂度为 ，在表尾插入元素的时间复杂度为 。3在一个稀疏矩阵中，每个非零元素所对应的三元组包括该元素的 、 和 三项。4在广义表的存储结构中，每个结点均包含有 个域。5当用长度为N的数组顺序存储一个栈时，假定用top = =N表示栈空，则表示栈满的条件为 。6假定一棵三叉树的结点个数为50，则它的最小深度为 ，最大深度为 。7在一棵二叉树中，第5层上的结点数最多为 。8在一个小根堆中，堆顶结点的值是所有结点中的 ，在一个大根堆中，堆顶结点的值是所有结点中的 。9在一个具有n个顶点的无向圄中，要连通所有顶点则至少需要 条边。10假定一个图具有n个顶点和e条边，贝采用邻接矩阵、邻接表和边集数组表示时，其相应的空间复杂度分别为 、 和 。11以二分查找方法查找一个线性表时，此线性表必须是 存储的 表。12在索引表中，若一个索引项对应主表中的一条记录，则称此索引为 表。13快速排序在平均情况下的空间复杂度为 ，在最坏情况下的空间复杂度为 。三、运算题（每题5分，共20分）1假定一个大堆为（56，38，42，30，25，40，35，20），则依次从中删除两个元素后得到的堆为 。2已知一个图的顶点集V和边集6分别为： V=0，1，2，3，4，5，6，7； E=（04）8，（0，2）5，（0，3）2，（1，5）6，（2，3）25，（2，4）13，（3，5）9，（3，6）10，（4，6）4，（5，7）20； 按照克鲁斯卡尔算法得到最小生成材，拭写出在最小生成树中依次得到的各条边。 ， ， ， ， ， ， 。3假定一组数据的初始堆为（84，79，56，42，40，46，50，38），请写出在堆排序阶段进行前三次对换和筛运算后数据的排列情况。 数据排列情况： 。4假定一组记录的徘序码为（46，79，56，38，40，80，36，40，75，66，84，24），对其进行归并排序的过程中，第三趟归并后的结果为： 。四、阅读算法，回答问题（每题5分，共10分）1void AA （ListL） InitList（L）； InsertRear （L，30）； InsertFront（L，50）； int a 4=5，8，12，15 for（int i=0；14；i InsertRear（L，a i）； 该算法被调用执行后，得到的线性表L为： 。2void AF（QueueQ） InitQueue（Q）： int a 4=5，8，12，15 for（int i一0；i4；i斗 Qlnsert（Q，迁6）； QInsert（Q，QDelete（Q）； QInsert（Q，30）； QInsert（Q，QDelete（Q）10）； whi1e（！QueueEmpty（Q） coutQDeleie（Q）”； 该算法被调用后得到的输出结果为： 。五、算法填空，在画有横线的地方填写合适的内容（10分）从一维数组An上进行快速排序的递归算法。void QuickSort（ElemType A ， int s， int t） int i=s j=t十1； ElemType x=As； d0 do i+； while ；填写一个循环条件 do j - - ； while（A j stnxstn）； if（I0）个结点的d度树共有nd个链域，除根结点外，每个结点均有一个指针所指，故该树的空链域有nd-(n-1)=n(d-1)+1个。习题二参考答案一、选择题（每题2分，共20分）12345678910BDACDDBBCA二、填空题（每空2分，共40分）1n-12（15，02，21，24，26，57，43，66，81，48，73）3O（n）4HL-next=NULL HL-next=HL5O(nlog2n) ；O(n2)66； 31； 1972； 1； 1； 68 6 9集合结构；线性结构；树型结构；图形结构10n-i+1三、应用题（每题10分，共60分）1答：可以做到。取a与b进行比较，c与d进行比较。设ab,cd(ab和cd，则有序abd；若bdb，此时已进行了3次比较。再把另外两个元素按折半插入排序方法，插入到上述某个序列中共需4次比较，从而共需7次比较。2该排序方法为快速排序。3快速排序 冒泡排序 直接插入排序4答：（1）T树的最大深度Kmax=6（除根外，每层均是两个结点）T树的最小深度Kmin=4（具有6个叶子的完全二叉树是其中的一种形态）456123（2）非叶子结点数是5。（n2=n0-1） （3）哈夫曼树见下图，其带权路径长度wpl=51Wpl=4*3+3*3+2*(4+5+6)=515答：n（n0）个结点的d度树共有nd个链域，除根结点外，每个结点均有一个指针所指，故该树的空链域有nd-(n-1)=n(d-1)+1个。6答：（1）176 （2）76和108 （3）28和116。习题三参考答案一、单选题（每题2分，共10分） 1、A 2、B 3、D 4、D5、D二、填空题（每空1分，共25分） 1、1:1 1:N M:N （或者 1对1 1对N M对N） 2、p-next ap.next 3、引用 4、后进先出 先进先出 5、162 6、31 21 7、6 8、查找成功 左子树 右子树 9、n2 10、n n-111、二叉搜索树 理想平衡树 （次序无先后） 12、O(n) O(nlog2n) O(n)13、596 三、运算题（每题6分，共24分） 1、 先根：a,b,e,c,f,h,i,j,g,d; （2分） 后根：e,b,h,i,j,f,g,c,d,a; （2分） 按层：a,b,c,d,e,f,g,h,i,j; （2分） 2、 最小生成树的权：55 3、 3 1 2 4、 5 6 四、阅读算法，回答问题（第一题7分，第二题8分） 1、（12，26，9，8，15，30，50） 2、向HBT堆中插入一个值为item的元素，使得插入后仍是一个堆。五、算法填空，在画有横线的地方填写合适的内容（12分） return mid return Binsch(A , low , mid-1 , K) return Binsch(A , mid+1 , high , K)六、编写算法（14分） 评分标准：请根据编程情况酌情给分。bool Find( BTreeNode * BST , ElemType & item ) while ( BST != NULL ) if ( item = BT-data ) item = BST-data;return true; else if (itemdata) BST=BST-left;else BST=BST-right; return false;习题四参考答案一、选择题（每题2分，共20分）12345678910CDACCDCDBC二、填空题（每空2分，共30分）1算法的时间复杂度和空间复杂度2有穷性； 确定性； 可行性。3n