最新数据结构作业题套计算机专业

1、东北农业大学网络教育学院数据结构作业题(一)、选择题(每题 2分，共20 分)1在一个长度为n的顺序表的任一位置插入一个新元素的渐进时间复杂度为()。2A Qn)B、O(n/2)C、O(1)D O(n )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、入度与出度之

2、差5. 对于长度为9的有序顺序表，若采用折半搜索，在等概率情况下搜索成功的平均搜索长度为()的值除以9。A、20B、18C、25D、226下列程序段的时间复杂度为()。s=0;for(i=1 ; i<n; i+)for(j=1 ; j<n ; j+)s+=i*j ;2A、O(1)B、O(n)C、O(2n)D、O(n)7栈是一种操作受限的线性结构，其操作的主要特征是()。A、先进先出B、后进先出C、进优于出D、出优于进&假设以数组 An存放循环队列的元素，其头、尾指针分别为front和rear。若设定尾指针指向队列中的队尾元素，头指针指向队列中队头元素的前一个位置，则当前存于

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.在一棵AVL树中，每个结点的左子树高度与右子树高度之差的绝对值不超过3.已知8个数据元素为(34, 76, 45,18, 26, 54

4、, 92 , 65),按照依次插入结点的方法生成一棵二叉排 序树，则该树的深度为 。4在二叉树的第i层上至多有 结点。5.对于一棵具有n个结点的二叉树，若一个结点的编号为1 / 17i(1 < i w n)，则它的左孩子结点的编号为，右孩子结点的编号为 ，双亲结点的编号为 。6. 数据的存储结构被分为 、和四种。7 假定一棵树的广义表表示为A(B(C,D(E,F,G),H(I,J)，则树中所含的结点数为 个，树的深度为，树的度为。&在一个具有n个顶点的无向图中，要连通所有顶点则至少需要 条边。9. 在线性结构、树形结构和图形结构中，前驱和后继结点之间分别存在着、和的联系。10.

5、一棵含999个结点的完全二叉树的深度为 。三、运算题(每题 5分，共10分)1. 设有一个10 10的对称矩阵A ,将其下三角部分按行存放在一个一维数组B中，A00存放于B0中,那么A85存放于B中什么位置。2.已知一个有序表(15, 26, 34, 39, 45, 56, 58, 63, 74, 76, 83, 94 )顺序存储于一维数组a12 中，根据折半搜索过程填写成功搜索下表中所给元素34, 56, 58, 63, 94时的比较次数。兀素值3456586394比较次数18 / 17四、应用题（每题 10 分，共 50 分）1设待排序的记录共 7 个，排序码分别为 8，3， 2，5，9，

6、1， 6。（1）用直接插入排序。试以排序码序列的变化描述形式说明排序全过程（动态过程）要求按递减顺 序排序。（2）用直接选择排序。试以排序码序列的变化描述形式说明排序全过程（动态过程）要求按递减顺 序排序。2判断下列序列是否是堆（可以是小堆，也可以是大堆，若不是堆，请将它们调整为堆）1）100，85，98，77，80，60，82，40，20，10，662）100，98，85，82，80，77，66，60，40，20，103）100，85，40，77，80，60，66，98，82，10，204）10，20，40，60，66，77，80，82 ，85，98，1003试找出分别满足下列条件的所有二叉

7、树。1）先序序列和中序序列相同3）先序序列和后序序列相同2）中序序列和后序序列相同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个链域，则在表示该树的多重链表中有多少个空链域 ? 为什么 ?储，则 A7,1 和 A2,4 的第

8、一个字节的地址是多少？数据结构作业题（二）、选择题（每题 2分，共20 分）1.在一个单链表 HL中，若要向表头插入一个由指针HL=p; p_>n ext=HL;p_>n ext=HL; p=HL;由权值分别为24 B、 48A、C、p指向的结点，则执行（B、p->next=HL; HL=p;D、p->next=HL->next; HL->next=p;2.A、3,8,6,2,5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（53）的表示等价。*a+iD、&a+i）°C、 72 D、 ai 与(B、a+i3. 一个数组元素A、*（a+i）4

9、. 下面程序段的时间复杂度为（for（i nt i=0; i<m; i+）for（i nt j=0; j< n; j+）aij=i*j;2 2A、O（m ）B、O（n ）5数据结构是（）°一种数据类型数据的存储结构一组性质相同的数据元素的集合相互之间存在一种或多种特定关系的数据元素的集合C、O(m*n)D、0(m+n)A、B、C、删除1, 2，4，54，6C、排序 D、定位3，4，5，6，且进栈和出栈可以穿插进行，则可能出现的出栈序列为（B、3，4，2，1，6，5D、5，6，4，2，3，1C、都不相同）°C、稠密图D、稀疏图b,c,d,e,f,g,q,r,s,t

10、），则在二分查找关键字b的过程中，先后进行比较的关键D、互为逆序A、f,c,bB、f,d,bC、g,c,bD、 g,d,b6在线性表的下列运算中，不改变数据元素之间结构关系的运算是（A、插入7. 若进栈序列为A、3， 2， 6， 1，C、 1， 2， 5， 3，&在任意一棵二叉树的前序序列和后序序列中，各叶子之间的相对次序关系（ A、不一定相同B、都相同9. 图的邻接矩阵表示法适用于表示（A、无向图B、有向图10. 若有序表的关键字序列为（字依次为（）°二、填空题（每空 2分，共40 分）1. 含n个顶点的无向连通图中至少含有 条边。2. 若对关键字序列（43，02，80，4

11、8，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

12、、2、1、0的结点数分别为 、和个。&在一棵二叉树中，假定双分支结点数为5个，单分支结点数为 6个，则叶子结点数为个。9数据的逻辑结构被分为 、和四种。10在一个长度为n的顺序存储线性表中，向第i个元素（1 < i < n+1）之前插入一个新元素时，需要从后向前依次后移个元素。三、应用题（每题 10分，共60分）2.有一随机数组(25,84,21,46,13,27,68,35,20),则该排序方法是什么？初 始:25,84,21,46,13,27,68,35,20第二趟:13,20,21,25,35,27,46,68,841. 设有5个互不相同的元素 a、b、c、d、e,能

13、否通过7次比较就将其排好序？如果能，请列出其比较过 程；如果不能，则说明原因。现采用某种方法对它们进行排序，其每趟排序结果如下第一趟:20,13,21,25,46,27,68,35,84第三趟:13,20,21,25,27,35,46,68,843.请在（）内填入正确的排序方法。设一数组中原有数据如下15,13, 20, 18, 12, 60。下面是一组由不冋排序方法进行一遍排序后的结果。（）排序的结果为：12, 13,15, 18, 20, 60）排序的结果为：13, 15,18, 12, 20, 60）排序的结果为：13, 15,20, 18, 12, 604设 T 是一棵二叉树，除叶子结

14、点外，其它结点的度数皆为2，若 T 中有 6 个叶结点，试问：(1)T 树的最大深度 Kmax=? 最小可能深度 Kmin=?( 2)T 树中共有多少非叶结点？(3) 若叶结点的权值分别为 1,2,3,4,5,6。请构造一棵哈曼夫树， 并计算该哈曼夫树的带权路径长度 wpl 。5.棵有n(n>0)个结点的d度树，若用多重链表表示，树中每个结点都有d个链域，则在表示该树的多重链表中有多少个空链域 ? 为什么 ?6. 有一个二维数组 A0:8,1:5 ，每个数组元素用相邻的 4 个字节存储 ,存储器按字节编址，假设存储数组元 素 A0,1 的第一个字节的地址是 0，那么存储数组的最后一个元素

15、的第一个字节的地址是多少？若按行存 储，则A3,5和A5,3的第一个字节的地址是多少？若按列存储，则A7,1和A2,4的第一个字节的地址是多少？数据结构作业题(三)一、单选题(每题 2分，共10分)1、在长度为n的顺序存储的线性表中,删除第i个元素(1 < i炙时，需要从前向后依次前移A、n-iB、n-i+12、设一个广义表中结点的个数为A、0(1)B、0(n)C、n-i-1D、in,则求广义表深度算法的时间复杂度为 2nC、0(n )D、O(log 2 )3、假定一个顺序队列的队首和队尾指针分别为f和r,则判断队空的条件为 A、f+1=rB、r+1=fC、f=0D、 f=r4、由3个结

16、点可以构造出多少种不同的二叉树 A、2B、3C、4D、55、适用于折半查找的表的存储方式及元素排列要求为 。A、链接方式存储，元素无序B 链接方式存储，元素有序C、顺序方式存储，元素无序D 顺序方式存储，元素有序二、填空题(每空1分，共25分)1、 在线性结构、树结构和图结构中，前驱和后继结点之间分另存在着、和的联系。2、 在线性表的单链接存储中， 若一个元素所在结点的地址为p，则其后继结点的地址为 若假定p为一个数组a中的下标，则其后继结点的下标为 。3、 在初始化一个稀疏矩阵的函数定义中，矩阵形参应说明为 参数。4、 栈又称为 表，队列又称为 表。5、 后缀表达式 “ 4 5 + 3 *

17、2 4 + *的值为。6、 一棵深度为 5的满二叉树中的结点数为 个，一棵深度为 3的满四叉树中的结点数为 个。7、对于一棵含有 40个结点的理想平衡树，它的高度为 。&从一棵二叉搜索树中查找一个元素时，若元素的值等于根结点的值，则表明，若元素的值小于根结点的值，则继续向 查找，若元素的值大于根结点的值，则继续向 查找。9、对于一个具有n个顶点的图，若采用邻接矩阵表示，则矩阵大小为。10、对于一个具有n个顶点和e条边的连通图，其生成树中顶点数和边数分别为 和。11、 二分查找过程所对应的判定树既是一棵 ，又是一棵 。12、 在归并排序中，进行每趟归并的时间复杂度为，整个排序过程的时间复

18、杂度为，空间复杂度为。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,

19、 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)In itList(HL);In sertRear(HL,30);In

20、 sertRear(HL,50);int a5 = 15,8,9,26,12;for ( int i=0;i<5;i+ )In sertFro nt(HL,ai);该算法被调用执行后，得到的以HL为表头指针的单链表中的数据元素依次 为：。2、void AH(Heap & HBT , constElemType item)/ HBT 为一个小根堆HBT.heapHBT.size=item;HBT.size+;ElemType x=itemint i=HBT.size-1;while( i != 0 )int j=(i-1)/2;if( x>=HBT.he apj)break;

21、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 )intmid = (low+high)/2;if ( K=Amid.key);else if (K<Amid.key );elseelse return -1;六、编写算法（14分）item的结

22、点的非递归算法，若查找成功则由编写在以BST为树根指针的二叉搜索树上进行查找值为item带回整个结点的值并返回true,否则返回false。bool Fi nd( BTreeNode* BST , ElemType & item )数据结构作业题（四）一、选择题（每题 2分，共20分）1 从逻辑上可以把数据结构分为（）两大类。A. 动态结构、静态结构B.顺序结构、链式结构C.线性结构、非线性结构D.初等结构、构造型结构2. 以下数据结构中，哪一个是线性结构（）？A. 广义表 B. 二叉树 C.稀疏矩阵D.串3. 连续存储设计时，存储单元的地址（）。A. 定连续 B .一定不连续C .不

23、一定连续D .部分连续，部分不连续4若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（）。2A. 0（0） B. 0（1） C. 0（ n）D. O（n）5. 在双向链表指针p的结点前插入一个指针q的结点操作是（）。A. p->Lli nk=q;q->Rli nk=p;p->Lli nk->Rli nk=q;q->Lli nk=q;B. p->Lli nk=q;p->Lli nk->Rli nk=q;q->Rli nk=p;q->Lli nk=p->Lli nk;C. q->Rli nk

24、=p;q->Lli nk=p->Lli nk;p->Lli nk->Rli nk=q;p->Lli nk=q;D. q->Lli nk=p->Lli nk;q->Rli nk=q;p->Lli nk=q;p->Lli nk=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.

25、3 4 6 5 2 1 D. 2 3 4 1 5 6&用链接方式存储的队列，在进行删除运算时（ A.仅修改头指针B.仅修改尾指针C.头、尾指针都要修改D.头、尾指针可能都要修改9.若用一个大小为 6的数组来实现循环队列，且当前 一个元素，再加入两个元素后，A. 1 和 5 B. 2和10栈和队列的共同点是（A.都是先进先出rear 禾口 frontC. 4rear 和 的值分别为多少?和 2 D. 5front的值分别为0和3,（）和1当从队列中删除）。B.C.只允许在端点处插入和删除元素D.都是先进后出 没有共同点二、填空题（每空 2分，共30 分）1.2.3.4.数据结构中评价算法

26、的两个重要指标是一个算法具有在一个长度为对于双向链表和。，有零个或多个输入、有一个或多个输出。 需向后移动 个，单链表为5个特性：n的顺序表中第i个元素（1<=i<=n ）之前插入一个元素时,在两个结点之间插入一个新结点需修改的指针共 5._个元素。 个。的基地址为2000,每个元素占2个存储单元，若以行序为主序顺序存储，则元a45,68的存储地址为。设数组 a1.50,1.80素a45,68的存储地址为_若以列序为主序顺序存储，则元素6所谓稀疏矩阵指的是 。7.广义表的 定义为广义表中括弧的重数。&具有256个结点的完全二叉树的深度为 。9 .已知一棵度为3的树有2个度为

27、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,(

28、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=<0,2>,<1,3>,<1,4>,<2,4>,<2,5>,<3,6>,<3,7>,<4,7>,<4,8>,<5,7>,<6,7>,<7,8> 若存储它采用邻接表，并且每个顶

29、点邻接表中的边结点都是按照终点序号从小到大的次序链接的，则 按主教材中介绍的进行拓扑排序的算法，写出得到的拓扑序列(提示：先画出对应的图形，然后再运算) 拓扑序列：5假定一组记录的排序码为 。(46,79,56,38,40,80,25,34) ，则对其进行快速排序的第一次划分后的结果为四、算法填空（10分）1.向以EST为树根指针的二叉搜索树上插入值为讥潮的结点的谨归算法. void Insert (BTreeNode BST, const EleinTypefe item) if(BST=NULL) BSTnew BTreeNode;BST"data=itemi；else if (

30、itejft<BST->data) else '五、编程（10分）1. 设计算法以求解从集合1.n中选取k （ k<=n）个元素的所有组合。例如，从集合1.4中选取2个元素的所有组合的输出结果为：1 2，1 3，1 4，2 3，2 4 ，3 4。数据结构作业题（五）、选择题（每题 2分，共20 分）1若需要利用形参直接访问实参，则应把形参变量说明为（）参数。A指针B引用C值2在一个单链表HL中，若要在指针q所指结点的后面插入一个由指针p所指向的结点，则执行（）。Aq 一>next=p 一一 >n ext;p一 >next=q;Bp 一>next

31、=q 一一 >n ext;q=p；C9 ->next=p 一一 >n ext;p一 >next=q;Dp 一一n ext=q 一一 >n ext;q一 >next=p ;3在一个顺序队列中，队首指针指向队首元素的（）位置。A前一个B后一个C当前4向二叉搜索树中插入一个元素时，其时间复杂度大致为（）。A O （1）BO （1og2n）C O （ n）D O （ nlog2n）5. 假设有两个串 A和B，求B在A中首次出现的位置的操作，我们称为（）。A.连接B.模式匹配C.求子串D.求串长6 我们对记录进行排序的目的是（）。A.分类B.合并C.存储D.查找7在最

32、坏的情况下，冒泡排序法的时间复杂度为（）。A.O(lg n)B.O( nig n)2C.O(n )D.O( n)& 广义表（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

33、分）1 数据的逻辑结构被分为 、和四种。2对于一个长度为 n的顺序存储的线性表，在表头插入元素的时间复杂度为 ，在表尾插入元素的时间复杂度为。3在一个稀疏矩阵中，每个非零元素所对应的三元组包括该元素的、和_项。4 在广义表的存储结构中，每个结点均包含有 个域。5.当用长度为N的数组顺序存储一个栈时，假定用 top = =N表示栈空，则表示栈满的条件为 <6假定一棵三叉树的结点个数为50,则它的最小深度为，最大深度为 7 在一棵二叉树中，第5层上的结点数最多为 。&在一个小根堆中，堆顶结点的值是所有结点中的 ，在一个大根堆中，堆顶结点的值是所有结点中的。9.在一个具有n个顶点的无向

34、圄中，要连通所有顶点则至少需要 条边。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,