暨南大学 2011 年信息科学技术学院830数据结构考研真题

                     

贡献者: xzllxls

   声明:“该内容来源于网络公开资料,不保证真实性,如有侵权请联系管理员”

1. 一.选择题(每题 2 分,共 30 分)

   1.算法分析的目的是( )。
A.找出数据结构的合理性
B.研究算法中的输入和输出关系
C.分析算法的效率以求改进
D.分析算法的易读性和文档性

   2.下列函数中渐近时间复杂度最小的是( )。
A. $T1(n)=1og_2n+5000n$
B. $T2(n)=n^2-8000n$
C. $T3(n)=n^3+5000n$
D. $T4(n)=2nlogn-1000n$

   3.线性表的动态链表存储结构与顺序存储结构相比,优点是( )。
A.所有的操作算法实现简单
B.便于随机存取
C.便于插入与删除
D.便于节省存储器空间

   4.若进栈序列为 1, 2, 3, 4, 5, 6,且进栈和出栈可以穿插进行,则可能出现的出栈序列为( )。
A. 3, 2, 6, 1, 4, 5
B. 5, 6, 4, 2, 3, 1
C. 5, 1, 2, 3, 4, 6
D. 3, 4, 2, 1, 6, 5

   5.顺序存储的线性表的第一-个元素的存储地址是 100,每个元素的长度为 4,则第 4 个元素的存储地址是( )。
A.108
B.112
C.116
D.120

   6.在任意一一棵二叉树的先序序列和后序序列中,各叶子之间的相对次序关系( )。
A.不一定相同
B.互为逆序
C.都不相同
D.都相同

   7.高度为 5 的二叉树至多有结点数为()。
A. 63
B. 32
C. 31
D. 64

   8.图的邻接矩阵表示法适用于表示( )。
A.无向图
B.有向图
C.稠密图
D.稀疏图

   9.在一个单链表中,若 p 所指的结点不是最后一个结点,在 p 之后插入 s 所指的结点,则执行( )。
A. s->next=p; p->next=s
B. p->next=s; s->next=p
C. p=s; s->next=p->next
D. s->next=p->next; p->next=s

   10.若在线性表中采用折半查找法查找元素,该线性表应该是( )。
A.元素按值有序
B.采用顺序存储结构
C.元素按值有序且采用顺序存储结构
D.元素按值有序且采用链式存储结构

   11.已知一棵二叉树结点的先序序列为 ABDGCFK,中序序列为 DGBAFCK,则结点的后序序列为().
A. GDBFKCA
B. DGBFKCA
C. KFCABDG
D. CAFKGDB

   12.对于元素是整数(占 2 个字节)的 n 行 n 列对称矩阵 A,采用以行序为主的压缩存储方式存储到一维数组 s[n* (n+1)/2]中(下三角),若 A[1][1]的起始地址是 400,问元素 A[8][5]的存储地址是( 5 心).
A. 432
B. 563
C. 484
D. 464

   13.在所有排序方法中,关键字的比较次数与记录的初始排列无关的是()。
A. Shell 排序
B.冒泡排序
C. 直接插入排序
D.直接选择排序

   14.具有 6 个顶点的无向图至少应有( ) 条边才能确保是一个连通图。
A. 5
B. 6
C. 7
D. 8

   15. 如果 T2 是由树 T1 转换而来的二叉树,那 T1 中结点的先序就是 T2 中结点的( )。
A. 先序
B. 中序
C. 后序
D. 层次序

2. 二.填空题(每题 2 分,共 20 分)

   1.在数据结构中,数据的逻辑结构分()和().

   2.若对关键字序列(12, 18, 4,3, 6, 13,2, 9, 19, 8)进行快速排序(以第-一个元素为支点),则第一趟排序得到的结果为().

   3.堆排序采用了()作为其数据结构,如果希望第一次就能找出最小关键字记录,就建立()堆。

   4.二叉树中度为 0 的结点数为 30,度为 1 的结点数为 30,总结点数为().

   5.向栈中压入元素的操作是先()后().

   6.在()的情况下,链队列的出队操作需要修改尾指针。

   7.所谓连通图 G 的生成树,是 G 的包含其全部 n 个顶点的一一个 极小连通子图。它必定包含且:包含 G 的()条边.

   8.对于一个有向图,若一个顶点的度为 k1, 出度为 k2,则对应邻接表中该顶点单链表中的边节点数为().

   9.设 GetHead(p)为求广义表 p 的表头函数,GetTail (p)为求广义表 p 的表尾函数。其中()是函数符号,运算 GetTail (GetHead(a, b), (c, d, e)))的结果是().

   10.对 n 个结点进行快速排序,最大比较次数是().

3. 三,判断题(每题 1 分,共 10 分,正确的选 T,错误的选 F)

   1.一个广义表的表尾总是一个广义表。( )

   2.顺序表用一维数组作为存储结构,因此顺序表是一-维数组。( )

   3.双循环链表中,任一结点的前驱指针均为不空。( )

   4.存储图的邻接矩阵中,邻接矩阵的大小不但与图的顶点个数有关,而且与图的边数也有关。()

   5.当从一个最小堆中删除一个元素时,需要把堆尾元素填补到堆顶位置,然后再按条件把它逐层向下调整,直到调整到合适位置为止。()

   6.栈和队列都是顺序存取的线性表,但它们对存取位置的限制不同。( )

   7.一个无序的元素序列可以通过构造-棵二叉排序树而变成-一个有序的元素序列。(t)

   8.一棵 m 阶 B+树中每个结点最多有 m 个关键码,最少有 2 个关键码。( )

   9.拓扑排序是一种内部排序的算法。()

   10.空串与空格相同。()


致读者: 小时百科一直以来坚持所有内容免费无广告,这导致我们处于严重的亏损状态。 长此以往很可能会最终导致我们不得不选择大量广告以及内容付费等。 因此,我们请求广大读者热心打赏 ,使网站得以健康发展。 如果看到这条信息的每位读者能慷慨打赏 20 元,我们一周就能脱离亏损, 并在接下来的一年里向所有读者继续免费提供优质内容。 但遗憾的是只有不到 1% 的读者愿意捐款, 他们的付出帮助了 99% 的读者免费获取知识, 我们在此表示感谢。

                     

友情链接: 超理论坛 | ©小时科技 保留一切权利