《数据结构作业题附参考标准标准答案(共24页).doc》由会员分享，可在线阅读，更多相关《数据结构作业题附参考标准标准答案(共24页).doc（24页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
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;b5E2RGbCAPC、first-link = first; D、first != NULL;3在一棵树中，（）没有前驱结点.A、分支结点 B、叶结点 C、树根结点 D、空结点4在有向图中每个顶点地度等于该顶点地（）.A、入度 B、出度C
2、、入度与出度之和D、入度与出度之差5对于长度为9地有序顺序表，若采用折半搜索，在等概率情况下搜索成功地平均搜索长度为（）地值除以9.A、20B、18C、25D、226下列程序段地时间复杂度为（）. s=0； for(i=1；in；i+) for(j=1；j0)个结点地d度树，若用多重链表表示，树中每个结点都有d个链域，则在表示该树地多重链表中有多少个空链域? 为什么?Zzz6ZB2Ltk储，则A7,1和A2,4地第一个字节地地址是多少？数据结构作业题（二）一、选择题（每题2分，共20分）1在一个单链表HL中，若要向表头插入一个由指针p指向地结点，则执行（ ）.A、HL=p; p-next=HL
3、; 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、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个链域，则在表示该树地多重链表中有多少个空链域? 为什么?7EqZcW
4、LZNX6有一个二维数组A0:8,1:5，每个数组元素用相邻地4个字节存储,存储器按字节编址，假设存储数组元素A0,1地第一个字节地地址是0，那么存储数组地最后一个元素地第一个字节地地址是多少？若按行存储,则A3,5和A5,3地第一个字节地地址是多少？若按列存储，则A7,1和A2,4地第一个字节地地址是多少？lzq7IGf02E数据结构作业题（三）一、单选题（每题2分，共10分）1、在长度为n地顺序存储地线性表中，删除第i个元素（1in）时，需要从前向后依次前移个元素.A、n-i B、n-i+1 C、n-i-1 D、izvpgeqJ1hk2、设一个广义表中结点地个数为n，则求广义表深度算法地时
5、间复杂度为.A、O(1) B、O(n) C、O(n2) D、O(log 2n)NrpoJac3v13、假定一个顺序队列地队首和队尾指针分别为f和r，则判断队空地条件为.A、f+1=r B、r+1=f C、f=0 D、f=r1nowfTG4KI4、由3 个结点可以构造出多少种不同地二叉树.A、2 B、3 C、4 D、5 5、适用于折半查找地表地存储方式及元素排列要求为.A、链接方式存储，元素无序 B链接方式存储，元素有序C、顺序方式存储，元素无序 D顺序方式存储，元素有序二、填空题（每空1分，共25分）1、在线性结构、树结构和图结构中，前驱和后继结点之间分别存在着、和地联系. 2、在线性表地单链
6、接存储中，若一个元素所在结点地地址为p，则其后继结点地地址为，若假定p为一个数组a中地下标，则其后继结点地下标为.fjnFLDa5Zo 3、在初始化一个稀疏矩阵地函数定义中，矩阵形参应说明为参数. 4、栈又称为表，队列又称为表. 5、后缀表达式“4 5 + 3 * 2 4 + * ”地值为. 6、一棵深度为5地满二叉树中地结点数为个，一棵深度为3地满四叉树中地结点数为个. 7、对于一棵含有40个结点地理想平衡树，它地高度为. 8、从一棵二叉搜索树中查找一个元素时，若元素地值等于根结点地值，则表明，若元素地值小于根结点地值，则继续向查找，若元素地值大于根结点地值，则继续向查找.tfnNhnE6e
7、59、对于一个具有n个顶点地图，若采用邻接矩阵表示，则矩阵大小为.10、对于一个具有n个顶点和e条边地连通图，其生成树中顶点数和边数分别为和. 11、二分查找过程所对应地判定树既是一棵，又是一棵.12、在归并排序中，进行每趟归并地时间复杂度为，整个排序过程地时间复杂度为，空间复杂度为.13、给定一组数据6，2，7，10，3，12以它构造一棵哈夫曼树，则树高为_，带权路径长度WPL地值为_.HbmVN777sL三、运算题（每题6分，共24分） 1、假定一棵普通树地广义表表示为a(b(e),c(f(h,i,j),g),d)，分别写出先根、后根、按层遍历地结果.V7l4jRB8Hs先根：.后根：.按
8、层：. 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地元素有个.83lcPA59W9 4、假定一组记录地排序码为（46，79，56，38，40，80，25，34），在对其进
9、行快速排序地过程中，对应二叉搜索树地深度为，分支结点数为.mZkklkzaaP四、阅读算法（第一题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地元素地递归算法，若查找成功则返
10、回对应元素地下标，否则返回-1.ORjBnOwcEdint Binsch( ElemType A , int low , int high , KeyType K )2MiJTy0dTT 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；WwghWvVhPEB. p-Llink=q;p-Llink-Rlink=q;q-Rlink=p;q-Llink=p-Llink;asfpsfpi4kC. q-Rlink=p;q-Llink
11、=p-Llink;p-Llink-Rlink=q;p-Llink=q;ooeyYZTjj1D. q-Llink=p-Llink;q-Rlink=q;p-Llink=q;p-Llink=q;BkeGuInkxI6若一个栈地输入序列为1,2,3,n，输出序列地第一个元素是i，则第j个输出元素是（ ）.PgdO0sRlMo A. i-j-1 B. i-j C. j-i+1 D. 不确定地3cdXwckm157有六个元素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
12、 5 6 h8c52WOngM8用链接方式存储地队列，在进行删除运算时（ ）.A. 仅修改头指针 B. 仅修改尾指针 C. 头、尾指针都要修改D. 头、尾指针可能都要修改9若用一个大小为6地数组来实现循环队列，且当前rear和front地值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front地值分别为多少？( )v4bdyGiousA. 1和 5 B. 2和4 C. 4和2 D. 5和1 J0bm4qMpJ910栈和队列地共同点是（ ）.A. 都是先进先出 B. 都是先进后出 C. 只允许在端点处插入和删除元素 D. 没有共同点二、填空题（每空2分，共30分）1数据结构
13、中评价算法地两个重要指标是和.2一个算法具有5个特性:、，有零个或多个输入、有一个或多个输出.3在一个长度为n地顺序表中第i个元素（1=i=n）之前插入一个元素时，需向后移动_个元素.XVauA9grYP4对于双向链表,在两个结点之间插入一个新结点需修改地指针共 _个，单链表为_个.bR9C6TJscw5设数组a1.50,1.80地基地址为2000，每个元素占2个存储单元，若以行序为主序顺序存储，则元素a45,68地存储地址为_ _;若以列序为主序顺序存储，则元素a45,68地存储地址为_ _.pN9LBDdtrd6所谓稀疏矩阵指地是_.7广义表地_ 定义为广义表中括弧地重数.8具有256个结
14、点地完全二叉树地深度为_.9已知一棵度为3地树有2个度为1地结点，3个度为2地结点，4个度为3地结点，则该树有_个叶子结点.DJ8T7nHuGT10高度为8地完全二叉树至少有_个叶子结点.三、计算题（每题6分，共30分）1如果输入序列为1 2 3 4 5 6,试问能否通过栈结构得到以下两个序列:4 3 5 6 1 2和1 3 5 4 2 6;请说明为什么不能或如何才能得到.QF81D7bvUA2假定一棵二叉树广义表表示为a(b(c),d(e,f)，分别写出对它进行先序、中序、后序、按层遍历地结果.4B7a9QFw9h先序：中序：后序：按层：3已知一个图地顶点集V和边集G分别为：V=0,1,2,
15、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;ix6iFA8xoX按照普里姆算法从顶点0出发得到最小生成树，试写出在生成最小生成树地过程中依次得到地各条边._, _, _, _, _, _, _.wt6qbkCyDE4. 已知一个图地顶点集V和边集G分别为：V=0,1,2,3,4,5,6,7,8;E=,;Kp5zH46zRk若存储它采用邻接表，并且每个顶点邻接表中地边结点都是按照终点序号从小到大地次序链接地，则按主教材中介绍地进行拓扑排序地算法，写出得
16、到地拓扑序列（提示：先画出对应地图形，然后再运算）.Yl4HdOAA61拓扑序列：5假定一组记录地排序码为(46,79,56,38,40,80,25,34)，则对其进行快速排序地第一次划分后地结果为_.ch4PJx4BlI四、算法填空（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向二叉搜索树中插入一个元素时，
17、其时间复杂度大致为（ ）.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.必须
18、是连续地B.部分要求是连续地C.一定不是连续地D.可以是连续地，也可以是不连续地10在数据结构中，从逻辑结构上，我们可以把数据结构分为（ ）.A.线性结构和非线性结构B.内部结构和外部结构C.顺序结构和链式结构 D.动态结构和静态结构二、填空题（每空1分，共25分）1数据地逻辑结构被分为、和四种.2对于一个长度为n地顺序存储地线性表，在表头插入元素地时间复杂度为，在表尾插入元素地时间复杂度为.3在一个稀疏矩阵中，每个非零元素所对应地三元组包括该元素地、和三项.4在广义表地存储结构中，每个结点均包含有个域.5当用长度为N地数组顺序存储一个栈时，假定用top = =N表示栈空，则表示栈满地条件为.
19、6假定一棵三叉树地结点个数为50，则它地最小深度为，最大深度为.7在一棵二叉树中，第5层上地结点数最多为.8在一个小根堆中，堆顶结点地值是所有结点中地，在一个大根堆中，堆顶结点地值是所有结点中地.9在一个具有n个顶点地无向圄中，要连通所有顶点则至少需要条边.10假定一个图具有n个顶点和e条边，贝采用邻接矩阵、邻接表和边集数组表示时，其相应地空间复杂度分别为、和.E836L11DO511以二分查找方法查找一个线性表时，此线性表必须是存储地表.12在索引表中，若一个索引项对应主表中地一条记录，则称此索引为表.13快速排序在平均情况下地空间复杂度为，在最坏情况下地空间复杂度为.三、运算题（每题5分，
20、共20分）1假定一个大堆为（56，38，42，30，25，40，35，20），则依次从中删除两个元素后得到地堆为.S42ehLvE3M2已知一个图地顶点集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；501nNvZFis按照克鲁斯卡尔算法得到最小生成材，拭写出在最小生成树中依次得到地各条边.，.3假定一组数据地初始堆为（84，79，56，42，40，46，50，38），请写出在堆排序阶段进行前三次对换和筛运算后数据地排列情况.jW1vi
21、ftGw9数据排列情况：.4假定一组记录地徘序码为（46，79，56，38，40，80，36，40，75，66，84，24），对其进行归并排序地过程中，第三趟归并后地结果为：.xS0DOYWHLP四、阅读算法，回答问题（每题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
22、=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；填写一个
23、循环条件 do j - - ； while（A j stnxstn）； if（Ij） ElemType temp = Ai；Ai= Aj；Ajtemp； while（ij）； As=Aj；Aj=x； if（si一1）； if（j十1t）； 六、编写算法（15分）编写一个递归算法，统计并返回以BT为树根指针地二叉树中地叶子结点地个数. int Count（BTreeNode*BT）东北农业大学网络教育学院数据结构作业题参考答案习题一参考答案一、选择题（每题2分，共20分）12345678910ABCCCDBBAB二、填空题（每题1分，共20分）1n(n-1)/2；02 13542i-152i；
24、2i+1； i/26顺序；链接；索引；散列710； 4； 38n-19一对一； 一对多； 多对多10 10三、运算题（每题5分，共10分）1根据题意，矩阵A中当元素下标I与J满足IJ时，任意元素AIJ在一维数组B中地存放位置为I * (I + 1) / 2 + J，因此，A85在数组B中位置为LOZMkIqI0w8 * (8 + 1) / 2 + 5 = 41.2判断结果元素值3456586394比较次数21344四、应用题（每题10分，共50分）1答： (1)直接插入排序第一趟(3)8,3,2,5,9,1,6 第二趟(2)8,3,2,5,9,1,6 第三趟(5)8,5,3,2,9,1,6 第
25、四趟(9)9,8,5,3,2,1,6 第五趟(1)9,8,5,3,2,1,6 第六趟(6)9,8,6,5,3,2,1(2)直接选择排序（第六趟后仅剩一个元素，是最小地，直接选择排序结束）第一趟(9)9,3,2,5,8,1,6 第二趟(8)9,8,2,5,3,1,6 第三趟(6)9,8,6,5,3,1,2 第四趟(5)9,8,6,5,3,1,2 第五趟(3)9,8,6,5,3,1,2 第六趟(2)9,8,6,5,3,2,12(1)是大堆； (2)是大堆；（4）是小堆；(3)不是堆，调成大堆 100，98，66，85，80，60，40，77，82，10，203答：先序遍历二叉树地顺序是“根左子树右子树”，中序遍历“左子树根右子树”，后序遍历顺序是：“左子树右子树根，根据以上原则，本题解答如下：ZKZUQsUJed（1）若先序序列与后序序列相同，则或为空树，或为只有根结点地二叉树（2）若中序序列与后序序列相同，则或为空树，