《数据结构》4次作业.docx

《《数据结构》4次作业.docx》由会员分享，可在线阅读，更多相关《《数据结构》4次作业.docx（9页珍藏版）》请在优知文库上搜索。

1、数据结构4次作业一、单项选择题1 .连续存储设计时，存储单元的地址（）。A.一定连续B.一定不连续C.不一定连续D.部分连续，部分不连续2 .以下属于逻辑结构的是（）oA.顺序表B.哈希表C.有序表D.单链表3 .设有数组Ai,j,数组的每个元素长度为3字节，i的值为1到8,j的值为1到10,数组从内存首地址BA开始顺序存放，当用以列为主存放时，元素A5,8的存储首地址为（）。A.B+141B.B+180C.B+222D.BA+2254 .若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（）存储方式最节省时间。A.顺序表B.双链表C.带头结点的双循环链表D.单循

2、环链表5 .某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（）存储方式最节省运算时间。A.单链表B.仅有头指针的单循环链表C.双链表D.仅有尾指针的单循环链表6 .线性表（al,a2,an）以链接方式存储时，访问第i位置元素的时间复杂性为（）。A.0（i）B,0（1）C.0（n）D.0（i-l）7 .对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是（）o.head=NULLB.head-next=NULLC.head-next=headD.head!=NULL8 .若已知一个栈的入栈序列是1,2,3,n,其输出序列为pl,p2,p3,，pN,若

3、PN是n,则Pi是（）。,iB.n-iC.n-i+1D.不确定9 .有六个元素6,5,4,3,2,1的顺序进栈，问下列哪一个不是合法的出栈序列？（）。A.543612B.453126C.346521D.23415610. 散列文件使用散列函数将记录的关键字值计算转化为记录的存放地址，因为散列函数是一对一的关系，则选择好的（）方法是散列文件的关键。.散列函数B.除余法中的质数C.冲突处理D.散列函数和冲突处理11. 对一个算法的评价，不包括如下O方面的内容。A.健壮性和可读性B.并行性C.正确性D.时空复杂度12. 在带有头结点的单链表HL中，要向表头插入一个由指针P指向的结点，则执行（）。A.

4、p-next=HL-next;HL-next=p;B.p-next=HL;HL=p;C.p-next=HL;p=HL;D.HL=p;p-next=HL;13. 对线性表，在下列哪种情况下应当采用链表表示？（）A.经常需要随机地存取元素B.经常需要进行插入和删除操作C.表中元素需要占据一片连续的存储空间D,表中元素的个数不变14. 个栈的输入序列为123,则下列序列中不可能是栈的输出序列的是（）A.231B.321C.312D.12315. AOV网是一种（）oA.有向图B.无向图C.无向无环图D.有向无环图16. 若需要利用形参直接访问实参时，应将形参变量说明为（）参数。A.值B.函数C.指针

5、D.引用17. 在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点都具有相同的（）。A.行号B.列号C.元素值D.非零元素个数二、填空题1 .数据的物理结构包括的表示和的表示。2 .数据结构中评价算法的两个重要指标是。3 .当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用存储结构。4 .线性表L=（al,a2,an）用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是O5 .在一个长度为n的顺序表中第i个元素（k=i=n）之前插入一个元素时，需向后移动一个元素。6 .链接存储的特点是利用一来表示数据元素之间

6、的逻辑关系。7 .一个栈的输入序列是：L2,3则不可能的栈输出序列是o8 .区分循环队列的满与空，只有两种方法，它们是和o9 .数据结构是指数据及其相互之间的o当结点之间存在M对N（M：N）的联系时，称这种结构为O10 .队列的插入操作是在队列的尾进行，删除操作是在队列的_首进行。11 .当用长度为N的数组顺序存储一个栈时，假定用top-N表示栈空，则表示栈满的条件是top=0o12 .对于一个长度为n的单链存储的线性表，在表头插入元素的时间复杂度为,在表尾插入元素的时间复杂度为o13 .二叉树是指度为2的树。一棵结点数为N的二叉树，其所有结点的度的总和是O14 .对一棵二叉搜索树进行中序遍历

7、时，得到的结点序列是一个o对一棵由算术表达式组成的二叉语法树进行后序遍历得到的结点序列是该算术表达式的O三、判断题1 .算法可以用不同的语言描述，如果用C语言或PASCAL语言等高级语言来描述，则算法实际上就是程序了。()2 .数据结构的基本操作的设置的最重要的准则是，实现应用程序与存储结构的独立。()3 .稀疏矩阵压缩存储后，必会失去随机存取功能。()4 .数组是同类型值的集合。()5 .数组可看成线性结构的一种推广，因此与线性表一样，可以对它进行插入，删除等操作。()6 .稀疏矩阵压缩存储后，必会失去随机存取功能。()7 .二维以上的数组其实是一种特殊的广义表。()8 .文件是记录的集合，

8、每个记录由一个或多个数据项组成，因而一个文件可看作由多个记录组成的数据结构。()三、解答题1 .数据结构是一门研究什么内容的学科？2 .数据元素之间的关系在计算机中有几种表示方法？各有什么特点？3 .有5个元素，其入栈次序为：,B,C,D,E,在各种可能的出栈次序中，以元素C,D最先出栈(即C第一个且D第二个出栈)的次序有哪几个？四、程序阅读题1.请阅读以下程序，写出此程序所要完成的功能，及时间复杂度。intcompare(SqListA,SqListB)j=0;while(j.length&jB.length)if(A.elemjB.elemj)return(1);elsej+;if(.le

9、ngth=B.length)return(0);elseif(.lengthrchild=(2);(3)_=q;if(p-lchild)(4)if(p-rchild)(5);)五、算法设计题1.写出广度优先搜索遍历的遍历算法。六、运算题1. 已知一个6x5稀疏矩阵如下所示，试:（1） 写出它的三元组线性表；0000100000()-1()000000-25000000700（2）给出三元组线性表的顺序存储表示。2. 设有一个输入数据的序列是46,25,78,62,12,80,试画出从空树起，逐个输入各个数据而生成的二叉搜索树。七、阅读算法1. intPrime(intn)inti=l;intx

10、=(int)sqrt(n);while(+ix)return1;elsereturnO;(1)指出该算法的功能；(2)该算法的时间复杂度是多少？2. 写出下述算法的功能：voidAJ(adjlistGL,inti,intn)QueueQ;InitQueue(Q);coutiadjvex;if(!visitedj)coutjnext;HL是单链表的头指针，试写出删除头结点的算法。ElemTypeDeleFront(LNode*&HL)数据结构复习资料一、选择题1-5ABCAC6-10DDCBB17. D11.B12.A13.B14.C15.D16.A二、填空题1. (n-2)(n+3)22. n

11、=n2+l3. 3144. nl-ln2+n35. 5046. 直接插入排序和冒泡排序7.8.9. 联系图(或图结构)10. 尾首11. top=012. 0(1)0(n)13. 1284410814. 3365515132-145-2515637图7三、判断题1. 2.3.4.5.6. 7.8.X四、解答题1、数据结构是计算机存储、组织数据的方式.数据结构是指相互之间存在种或多种特定关系的数据E盍的集合.通常情况下,精心选择的数据结构可以带来更高的运行或者存储效率.数据结构往往同高效的检索算法和索引技术有关2、数据元素之间的关系在计算机中有几种表示方法？各有什么特点？答：四种表示方法（1）顺

12、序存储方式。数据元素顺序存放，每个存储结点只含一个元素,存储位置反映数据元素间的逻辑关系。存储密度大，但有些操作（如插入、删除）效率较差。（2）链式存储方式。每个存储结点除包含数据元素信息外还包含一组（至少一个）指针。指针反映数据元素间的逻辑关系。这种方式不要求存储空间连续，便于动态操作（如插入、删除等），但存储空间开销大（用于指针），另外不能折半查找等。（3）索引存储方式。除数据元素存储在一地址连续的内存空间外，尚需建立一个索引表，索引表中索引指示存储结点的存储位置（下标）或存储区间端点（下标），兼有静态和动态特性。（4）散列存储方式。通过散列函数和解决冲突的方法，将关键字散列在连续的有限的

13、地址空间内，并将散列函数的值解释成关键字所在元素的存储地址，这种存储方式称为散列存储。其特点是存取速度快，只能按关键字随机存取，不能顺序存取，也不能折半存取。3、栈是操作受限制的线性表，出栈是先进后出。CD固定后可以先进E,再出E,再出B再出A,就CDEBA,或者是先出B,再进E,再出E,再出A,就是CDBEA,或者先出B,再出A,再进E,再出E,即为CDBAE。故为三种。五、算法设计题1 .算法源代码如下：intflag=l;intmax;voidsortbitree（bitreeT）ifC）sortbitree（T-lchild）;k+;if（k=l）max=T-data;elseif(T-datamax)max=T-data;elseflag=O;)sortbitree(T-rchild);