数据结构模拟题开卷

1、数据结构模拟题（补）一 单项选择题1. 在线性表的下列存储结构中，读取元素花费时间最少的是【 】。a单链表b双链表c顺序表d循环链表2. 设计一个判定表达式中左、右括号是否配对出现的算法，采用【 】数据结构最佳。a集合b线性表c队列d栈3. n个结点的线索二叉树上含有的线索数为【 】。a2nbn-1cndn+14. 设广义表d=(a,(b,c),则tail(d）=【 】。ab,c b(b,c) c(b,c) dc5. 由4个结点可以构造出【 】种不同的二叉树。a12b13c14d156. 在栈中，出栈操作的时间复杂度为【 】。ao(1)bo(n)co(log2n)do(n2)7. 假设q0.l

2、en-1表示循环队列，f为队头指针，r为队尾指针，则进队操作语句是【 】。af=f+1br=r+1cf=(f+1)%lendr=(r+1)%len8. 一个n*n的对称矩阵，如果以行或列为主序放入内存，则其容量为【 】。an*nbn*n/2cn*(n+1)/2d(n+1)*(n+1)/29. 队列操作的原则是【 】。a进优于出b出优于进c先进先出d后进先出10. 下列数据结构中，【 】是非线性数据结构。a栈b串c队列d树11. 两个指针p和q，分别指向单链表的两个元素，p所指元素是q所指元素的前驱，则【 】。ap=qbq->next=pcp->next=qdp->next=q

3、->next12. 数组a中，每个元素的长度为4个字节，行下标i从1到5，列下标j从1到4，从首地址sa开始连续存放在存储器内，该数组按行存放时，元素a32的起始地址为【 】。asa+20bsa+36csa+40dsa+4513. 已知一个顺序存储的线性表，设每个结点需占m个存储单元，若第一个结点的地址为d1，则第i个结点的地址为【 】。ad1+(i-1)*mbd1+i*mcd1+(i+1)mdd1-i*m14. 分析下列算法suanfa1(n)的时间复杂度是【 】。 void suanfa1(int n) int i,j,x=1； for(i=0；i<n；i+) for(j=0；

4、j<n；j+) x=x*2； ao(2n) bo(2n) co(n2) do(n2+2)15. 将一个a1.10,1.10的三对角矩阵，按行优先存入一维数组b1,30中，a中元素a6,5在b数组中的位置i为【 】。a15b16c55d6516. 深度为6的二叉树最多有【 】个结点。a62b63c64c6517. 由3个结点可以构造出【 】种不同的二叉树。a2b3c4d518. 栈的插入和删除操作在【 】进行。a栈顶b栈底c指定位置d随机位置19. 数组a中，每个元素的长度为3个字节，行下标i从1到5，列下标j从1到4，从首地址sa开始连续存放在存储器内，该数组占用的字节数为【 】。a20

5、b60c80d12020. 下面语句的时间复杂度为【 】。s=0;for(i=1;i<=n;i+) s=s+i; ao(n) bo(n5) co(5n) do(n2)21. 二叉树中，叶子的数组等于【 】。a度为2的结点数加1 b度为2的结点数减1 c度为2的结点数 d度为2的结点数的两倍 22. 设广义表d=(a,(b,c)，则tail(d）=【 】。ab,c b(b,c) c(b,c) dc23. 数制转换的算法，采用【 】数据结构最佳。a集合b线性表c队列d栈24. 一个n*n的对称矩阵，如果以行或列为主序放入内存，则其容量为【 】。an*nbn*n/2cn*(n+1)/2d(n+

6、1)*(n+1)/225. 线性表采用链式存储时，其地址是【 】。a必须是连续的b一定是不连续的c部分地址必须是连续的d连续或不连续都可以26. 数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为【 】。a物理结构b逻辑结构c顺序存储结构d链式存储结构27. 两个指针p和q，分别指向单链表的两个元素，p所指元素是q所指元素的前驱，则【 】。ap=qbq->next=pcp->next=q->nextdp->next=q28. 线性表在【 】时, 宜用顺序表作存储结构。a经常随机存取 b经常作插入、删除 c无足够连续存储空间 d经常作动态增减二、 判断

7、题1. 【 】二叉排序树中每个结点的关键字值大于其左非空孩子（若存在的话）的关键字值，且小于其右非空孩子（若存在的话）结点的关键字值。2. 【 】算法必须具备的5个特征是：有穷性、确定性、可行性、有0或多个输入量，至少有1个输出量。3. 【 】完全二叉树的某结点若没有左孩子，则它必是叶子结点。4. 【 】哈夫曼树是带权路径最短的树,路径上权值较大的结点离根较近。5. 【 】空栈就是所有元素都为0的栈。6. 【 】在单链表中，要访问某个结点，只要知道该结点的指针即可；因此，单链表是一种随机存取结构。7. 【 】n*n对称矩阵经过压缩存储后占用的存储单元是原来的1/2。8. 【 】一个栈的输入序列

8、是12345，则栈的输出序列可以是54312。9. 【 】对于一个非空二叉树，它的根节点作为第一层，则第i层上最多能有2i-1个结点。10. 【 】稀疏矩阵压缩存储后，必会失去随机存取功能。11. 【 】完全二叉树中，若一个结点没有左孩子，则它必是树叶。12. 【 】用带表头结点的单链表表示队列，则判断队列为空的标准是头指针和尾指针均指向同一个结点。13. 【 】做进栈运算时应先判别,栈是否为空。14. 【 】广义表中原子个数即为广义表的长度。三、 填空题1. 数据结构包含四种基本结构，它们是集合、【 1 】、树形结构、【 2 】。2. 二叉树的深度为k的二叉树最多有【 3 】个结点，其中第i

9、层最多有【 4 】个结点。3. n个结点的完全二叉树，使用一维数组t存储结点元素的值，假设ti存储第i个结点，那么ti的双亲是【 5 】，左小孩是【 6 】，右小孩是t2*i+1。4. 由权值分别为11,8,6,2,5的叶子结点生成一颗哈夫曼树，它的带权路径长度为【 7 】。5. 若串s="hello"，其子串个数是【 8 】。6. 将含100个结点的完全二叉树从根这一层开始，每层上从左到右依次对结点编号，根结点的编号为1。编号为24的结点x的左孩子编号为【 9 】，右孩子编号为【 10 】。7. 长度为n的单链表链接在长度为m的单链表之后的算法时间复杂度为【 11 】。8

10、. wpl(t)指的是树的【 12 】，即每个叶子的权与根到该叶子的路径长度的乘积之和。9. 深度为k且有【 13 】个结点的二叉树称为满二叉树。10. 3层完全二叉树至少有【 14 】个结点。四、简答题1. 画出二叉树的5种基本形态。2. 线性表的顺序存储结构相比链式存储结构，有什么优缺点？适用于什么情况的存储？3. 已知一颗非空二叉树，按前序遍历的结果是acbgdehfji，按中序遍历的结果是cgbahedjfi，请画出该二叉树，并写出后序遍历的序列结果。4. 若比较频繁的对一个线性表进行插入和删除操作，该线性表适合采用哪种存储结构？为5. 简述二叉排序树（二叉查找树）的定义及特点。参考答

11、案：一单项选择题12345678910caddbdcacb11121314151617181920aabbcbdaba2122232425262728acdcdcda二判断题1234567×××891011121314×××三填空题12345线性结构图状结构2k-12i-1ti/2678910t2*i3215484911121314o(n)带权路径长度2k-14四、简答题1. 画出二叉树的5种基本形态。2. 线性表的顺序存储结构相比链式存储结构，有什么优缺点？适用于什么情况的存储？优点：1）是一种随机存储结构，存取任何元素的时间是一个

12、常数，速度快；2）结构简单，逻辑上相邻的元素在物理上也是相邻的；3）不使用指针，节省存储空间。缺点：1）插入和删除元素要移动大量元素，消耗大量时间；2）需要一个连续的存储空间；3）插入元素可能发生“溢出”；4）自由区中的存储空间不能被其他数据占用（共享）。适用于经常用于检索、存取元素，但是插入和删除元素操作较少的情况。3. 已知一颗非空二叉树，按前序遍历的结果是acbgdehfji，按中序遍历的结果是cgbahedjfi，请画出该二叉树，并写出后序遍历的序列结果。二叉树：后序遍历的结果是gbchejifda4.若比较频繁的对一个线性表进行插入和删除操作，该线性表适合采用哪种存储结构？为什么？时间复杂度是多少？链式存储结构。因为