2016.6月数据结构习题

更新时间：2024-04-13 00:56:01 阅读量：综合文库文档下载

说明：文章内容仅供预览，部分内容可能不全。下载后的文档，内容与下面显示的完全一致。下载之前请确认下面内容是否您想要的，是否完整无缺。

2016.6六级作文推荐度：
相关推荐

1、一棵二叉树没有单分支结点，有6个叶结点，则该树总共有____11____个结点。

2、数据结构的实质就是研究数据的、以及定义在逻辑结构上所进行的一组。

3、栈和队列的操作特点分别是___ 后进先出 ____和 _____ 先进先出 ___。 4、设一棵完全二叉树，其最高层上最右边的叶结点的编号为奇数，该叶节点的双亲结点的编号为10，该完全二叉树一共有____21____个结点。

5、一个图的_________表示法是唯一的，而___________表示法是不唯一的。 6、已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点，则该树中有个叶子结点。

7、G为无向图，如果从G的某个顶点出发，进行一次广度优先搜索，即可访问图的每个顶点，则该图一定是。

8、结构中的数据元素存在多对多的关系称为_____ 图状（网状） ___结构。 9、按照二叉树的递归定义，对二叉树遍历的常用算法有先序；中序；后序三种。 10、在具有n个单元的循环队列中，队满时共有__________个元素。 11、3个结点可构成棵不同形态的树。

12、一棵深度为h的满二叉树上的结点总数为，一棵深度为h的完全二叉树上的结点总数的最小值为，最大值为。

13、在一棵完全二叉树中有n个结点，对这些结点按层序编号，若一个结点编号为69，则其双亲编号为，有左孩子的条件是，其左孩子编号为。

14、根据数据元素间关系的不同特性，通常可分为集合、线性、树形、图状四类基本结构。

15、数据结构中的数据元素存在一对多的关系称为__树形_____结构。

16、要求在n个数据元素中找其中值最大的元素，设基本操作为元素间的比较。则比较的次数和算法的时间复杂度分别为__n-1和 O(n)__ 。

17、顺序存储的栈中，在作进栈运算时,应先判别栈是否,在进行出栈运算时应先判别栈是否。当栈中元素为n个,作进栈运算时发生上溢,则说明该栈的最大容量

为。

18、在带头结点的循环链表h中，判断表空的条件是。 19、具有n个顶点的有向完全图的弧数为_________。 20、数据的存储结构被分为_________和_________。

21、设有一顺序栈S，元素s1,s2,s3,s4,s5,s6依次进栈，如果6个元素出栈的顺序是s2,s3,s4,s6,s5,s1,则栈的容量至少应该是________。

22、在线性表的顺序存储中，元素之间的逻辑关系是通过决定的；在线性表的链式存储中，元素之间的逻辑关系是通过_________决定的。

23、把数据存储到计算机中,并具体体现数据之间的逻辑结构称为____物理（存储）____结构。

24、在一个单向链表中p所指结点之后插入一个s所指向的结点时，应执行___ s->next=p->next ____和p->next=s;的操作。 25、3个结点可以构成棵不同形态的二叉树。

26、对于一棵具有n个结点的二叉树，当它为一棵二叉树时具有最小高度，即为，当它为一棵单支树时具有高度，即为。

27、一个图的_________表示法是唯一的，而___________表示法是不唯一的。 28、在一棵有n个结点的完全二叉树中，对这些结点按层序编号，若一个结点编号为59，则其双亲编号为，若一个结点编号为23，则其有右孩子的条件是。 29、一棵深度为h的完全二叉树上的结点总数的最小值为，最大值为。 30、查找法的平均查找长度与元素个数n无关。 31、在带头结点的循环链表h中，判断表空的条件是。 32、一个具有n个顶点的无向完全图的边数为。

33、数组M中每个元素的长度是3个字节，行下标i从1到8，列下标j从1到10，从首地址EA开始连续存放在存储器中。若按行优先方式存放，元素M[8][5]的起始地址为_____________；若按列优先方式存放，元素M[8][5]的起始地址为___________。

34、对于一个具有n个结点的单链表，在p所指结点后插入一个新结点的时间复杂度为__________；在给定值为x的结点后插入一个新结点的时间复杂度为_____________。

35、数据结构的实质就是研究数据的、以及定义在逻辑结构上所进行的一组操作。

36、在线性表的顺序存储中，元素之间的逻辑关系是通过决定的；在线性表的链式存储中，元素之间的逻辑关系是通过指针决定的。 37、n个顶点的连通图的生成树有条边。

38、通常数组只有________和________两种运算，因此常采用_________来存储数组。

39、具有n个顶点的有向完全图的弧数为_________。

40、任何连通图的连通分量有__________个，即________________。

41、结构中的数据元素存在一对一的关系称为____线性 ___结构。

42、在二叉树的链式存储结构中，通常每个结点中设置三个域，它们是值域左指针、右指针。

43、有44个结点的完全二叉树，编号为22的结点的左孩子的编号为_________，其右孩子_________。

44、树中元素之间的关系是一对多的，而图中元素之间的关系为_________。 1、在具有n个结点的二叉排序树上插入一个新结点时，其时间复杂度大致为（）。

A、O（n2） B、O(n) C、O(log2n) D、O(nlog2n) 2、下面程序段的时间复杂度为（）。

for (i=1;i<=m;++i) for (j=1;j<=n;++j)

A[i,j]=i*j;

A、O（m2） B、O（n2） C、O（m*n） D、O（m+n） 3、带头结点的单链表h为空的判断条件是（）。

A、h==NULL B、h->next==NULL C、h->next==h D、h!=NULL 4、单链表中，增加头结点的目的是为了（）。

A、方便运算的实现 B、标识单链表

C、使单链表中至少有一个结点 D、用于标识起始结点的位置

5、某二叉树的前序和后序序列正好相同，则该二叉树一定是（）的二叉树。

A．空或只有一个结点 B．高度等于其结点数 C．任一结点无左孩子 D．任一结点无右孩子

6、一棵非空的二叉树的前序遍历与后序遍历序列正好相反，则该二叉树一定满足（）。

A: 所有的节点均无左孩子； B: 所有的节点均无右孩子； C: 只有一个叶子节点； D: 是任意一棵二叉树

7、在一个具有n个单元的顺序栈中，假定以地址低端（即下标为0的单元）作为栈底，以top作为栈顶指针，则当作退栈处理时，top的变化为（）。

A、top不变 B、top=0 C、top＝top+1 D、top=top-1 8、链栈与顺序栈相比，有一个较明显的优点是（）。

A、通常不会出现栈满的情况 B、通常不会出现栈空的情况 C、插入操作更加方便 D、删除操作更加方便

9、若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用（）存储方式最节省时间。

A、单链表 B、双链表 C、单向循环链表 D、顺序表

10、若用一个大小为6 的数组来实现循环队列，且当前rear 和front 的值分别为0 和3，当从队列中删除一个元素，再插入两个元素后，rear 和front 的值分别为（）。

A. 1 和 5 B. 2 和4 C. 4 和2 D. 5 和1

11、设有一个无向图G＝（V，E）和G｀＝（V｀，E｀），如果G｀为G的生成树，则下面不正确的说法是（）。

A、G｀为G的子图 B、G｀为G的连通分量 C、G｀为G的极小连通子图且V｀＝V D、G｀是G的一个无环子图

12、以下说法错误的是（） A．每个存储结点只能存放一个数据元素

B．数据元素之间的关联方式可由存储结点之间的关联方式直接表达 C．一种存储结构可以在两个级别上讨论。其一是机器级，其二是语言级 D．语言级描述可经编译自动转换成机器级，因此也可以看成是一种机内表示 13、设两个串(S1和S2) ，求S1在S2中首次出现的位置的运算称为_______。 (A) 联接操作 (B) 定位操作 (C) 置换操作 (D)赋值操作 14、串的长度是________。

(A) 串中不同字母的个数 (B)串中不同字符的个数 (C) 串中所含字符的个数，且大于0 (D) 串中所含字符的个数

15、设循环队列中数组的下标范围是0—(n-1)，其头尾指针分别为f和r，其中，f表示队头元素位置，r表示队尾元素后面一个元素的位置，则其队满的条件为________。

(A) r+1==n (B) (r+1)%n==f (C) (r+1)%n==n (D) (f+1)%n==r 16、设有一个无向图G＝（V，E）和G｀＝（V｀，E｀），如果G｀为G的生成树，则下面不正确的说法是（）。

用链接方式存储的队列，在进行插入运算时（）。 A．仅修改头指针 B．头、尾指针都要修改 C．仅修改尾指针

D．头、尾指针可能都要修改

17、设计一个判别表达式中左右括号是否配对出现的算法，采用（）数据结构

V2 V5 V6

V4 V8 V7

最佳。

A、线性表的顺序存储结构 B、栈

C、队列 D、线性表的链式存储结构 18、在具有n个叶子的哈夫曼树中，其结点总数为（）。

A、不确定 B、2n C、2n+1 D、2n-1 19、循环队列的出队操作为（） A．sq.front=(sq.ftont+1)% maxsize B．sq.front=sq.front+1

C．sq.rear=(sq.rear+1)% maxsize D．sq.rear=sq.rear+1

20、设数组Data[0..m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出队操作的语句为（） A．front=front+1 B．front=(front+1)% m C．rear=(rear+1)%m D．front=(front+1)%(m+1)

21、在具有n个结点的二叉排序树上插入一个新结点时，其时间复杂度大致为（）。

A、O（n2） B、O(n) C、O(log2n) D、O(nlog2n) 22、下面程序段的时间复杂度为（）。

for (i=1;i<=m;++i) for (j=1;j<=n;++j)

A[i,j]=i*j;

A、O（m） B、O（n） C、O（m*n） D、O（m+n） 23、带头结点的单链表h为空的判断条件是（）。

A、h==NULL B、h->next==NULL C、h->next==h D、h!=NULL 4、单链表中，增加头结点的目的是为了（）。 A、方便运算的实现 B、标识单链表

C、使单链表中至少有一个结点 D、用于标识起始结点的位置

24、一棵非空的二叉树的前序遍历与后序遍历序列正好相反，则该二叉树一定满足（）。

A: 所有的节点均无左孩子； B: 所有的节点均无右孩子； C: 只有一个叶子节点； D: 是任意一棵二叉树

25、在一个具有n个单元的顺序栈中，假定以地址低端（即下标为0的单元）作为栈底，以top作为栈顶指针，则当作退栈处理时，top的变化为（）。

A、top不变 B、top=0 C、top＝top+1 D、top=top-1 7、链栈与顺序栈相比，有一个较明显的优点是（）。 A、通常不会出现栈满的情况 B、通常不会出现栈空的情况 C、插入操作更加方便 D、删除操作更加方便

26、设有一个无向图G＝（V，E）和G｀＝（V｀，E｀），如果G｀为G的生成树，则下面不正确的说法是（）。

A、G｀为G的子图 B、G｀为G的连通分量 C、G｀为G的极小连通子图且V｀＝V D、G｀是G的一个无环子图 27、以下说法错误的是（）

A．树形结构的特点是一个结点可以有多个直接前趋 B．线性结构中的一个结点至多只有一个直接后继 C．树形结构可以表达(组织)更复杂的数据 D．树(及一切树形结构)是一种\分支层次\结构

28、中序遍历二叉排序树可以得到一个有序的序列（） A正确 B错误

29、用非递归方法实现递归算法时一定要使用递归工作栈。（） A正确 B错误

30、将f = 1 + 1/2 + 1/3+ … + 1/n转化为递归函数时，递归部分为f (n) = f (n-1) + 1/n，递归结束条件为f (1) = 1。（） A正确

B错误

31、线性表的顺序存储表示优于链式存储表示。（） A正确 B错误

32、一个广义表 ( (a), ( (b), c), ( ( (d) ) ) ) 的表尾是 ( (b), c), ( ( (d) ) )。（） A正确 B错误

33、如果结点A是结点B的双亲，而且结点B有4个兄弟，则结点A的度是_______。 (A)3 (B) 4 (C) 5 (D) 6

34、设有一棵树的度为4，其中度为1、2、3、4结点的个数分别为4、2、1、1，则这棵树中叶子结点的个数为_______。

(A)5 (B) 6 (C)7 (D) 8 35、下面关于图的存储的叙述中正确的是_______。

(A)用邻接矩阵存储图占用的存储空间大小只与图中顶点个数有关，与边数无关 (B)用邻接矩阵存储图占用的存储空间大小只与图的边数有关，与顶点个数无关 (C)用邻接表存储图占用的存储空间大小只与图中顶点个数有关，与边数无关 (D)用邻接表存储图占用的存储空间大小只与图的边数有关，与顶点个数无关 36、深度为6的满二叉树上有_______个结点。

（A）32 （B） 64 （C） 31 （D） 63

37、设森林T中有三棵树，第一、二、三棵树的结点个数分别是n1，n2，n3，那么当把森林转换成二叉树后，其根结点的左子树上有（）个结点，右子树上有（）个结点。

A、n1-1 B、n1 C、n1+n2 D、n2+n3

38、设计一个判别表达式中左右括号是否配对出现的算法，采用（）数据结构

V2 V5 V6

V4 V8 V7

最佳。

A、线性表的顺序存储结构 B、栈

C、队列 D、线性表的链式存储结构 39、在具有n个叶子的哈夫曼树中，其结点总数为（）。

A、不确定 B、2n C、2n+1 D、2n-1

1、已知某系统在通信联络中只可能出现8种字符，其频率分别为9，17，6，19，11，21，5，12。试设计哈夫曼编码。（必须画出哈夫曼树）

2、试用普里姆算法与克鲁斯卡尔算法分别构造如下网络的最小生成树，并画出基本步骤。