数据结构试题及答案(10套最新).doc

一、                  单选题(每题2分,共20分)1、     对一个算法得评价,不包括如下(B)方面得内容。 。正确性D。时空复杂度2、    在带有头结点得单链表HL中,要向表头插入一个由指针p指向得结点,则执行(A )。 A、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;3、    对线性表,在下列哪种情况下应当采用链表表示?(B)A、经常需要随机地存取元素 B、经常需要进行插入与删除操作 C、表中元素需要占据一片连续得存储空间 D、表中元素得个数不变4、     一个栈得输入序列为123,则下列序列中不可能就是栈得输出序列得就是( C)A、 23 1ﻩﻩ B、 321C、3 12ﻩﻩﻩﻩD、 1235、    AOV网就是一种(D)。 A。 、     采用开放定址法处理散列表得冲突时,其平均查找长度(B)。 B、高于链接法处理冲突 D。高于二分查找7、    若需要利用形参直接访问实参时,应将形参变量说明为(D)。函数 C。指针 、     在稀疏矩阵得带行指针向量得链接存储中,每个单链表中得结点都具有相同得(A).。列号 D。非零元素个数9、    快速排序在最坏情况下得时间复杂度为( D).A。O(log2n) (nlog2n) C。0(n) (n2)10、从二叉搜索树中查找一个元素时,其时间复杂度大致为( C). A、O(n) B、O(1) C、O(log2n) D、 O(n2) 二、                  运算题(每题 6分,共24分)1、        数据结构就是指数据及其相互之间得______________。当结点之间存在M对N(M:N)得联系时,称这种结构为_____________________。2、       队列得插入操作就是在队列得__尾______进行,删除操作就是在队列得____首______进行。3、       当用长度为N得数组顺序存储一个栈时,假定用top==N表示栈空,则表示栈满得条件就是___top==0___(要超出才为满)_______________。4、       对于一个长度为n得单链存储得线性表,在表头插入元素得时间复杂度为_________,在表尾插入元素得时间复杂度为____________。5、       设W为一个二维数组,其每个数据元素占用4个字节,行下标i从0到7,列下标j从0到3 ,则二维数组W得数据元素共占用_______个字节。W中第6行得元素与第4列得元素共占用_________个字节。若按行顺序存放二维数组W,其起始地址为100,则二维数组元素W[6,3]得起始地址为__________。6、       广义表A= (a,(a,b),((a,b),c)),则它得深度为____________,它得长度为____________。7、        二叉树就是指度为2得____________________树。一棵结点数为N得二叉树,其所有结点得度得总与就是_____________。8、       对一棵二叉搜索树进行中序遍历时,得到得结点序列就是一个______________。、       对于一棵具有n个结点得二叉树,用二叉链表存储时,其指针总数为_____________个,其中_______________个用于指向孩子,、   若对一棵完全二叉树从0开始进行结点得编号,并按此编号把它顺序存储到一维数组A中,即编号为0得结点存储到A[0],则A[ i]元素得左孩子元素为________,右孩子元素为_______________,双亲元素为____________。11、    在线性表得散列存储中,、   当待排序得记录数较大,排序码较随机且对稳定性不作要求时,宜采用_______________排序;当待排序得记录数较大,存储空间允许且要求排序就是稳定时,宜采用________________________排序。 三、                  运算题