《数据结构c语言》数据结构（甲）复习题

《《数据结构c语言》数据结构（甲）复习题》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、一.是非题I.数据结构可用三元式表示（D,S,P）«其中：D是数据对象，S是D上的关系，P是对D的基本操作集。⑴数据结构是二元式2简单地说,数据结构是带有结构的数据元素的集合。⑴3判断带头结点的非空循坏单链表（头指针为L）中指针p所指结点是最后一个元素结点的条件是：p->next==Lo（t）4线性表的链式存储结构具有可直接存取表中任一元素的优点。（05线性表的顺序存储结构优于链式存储结构。⑴6.在单链表P指针所指结点之后插入S结点的操作是：P->next=S;S->next=P->next；o（f）S->next=P->next;P->next=S;7对于插入、删除而言，线性表

2、的链式存储优于顺序存储。（t）8.顺序存储方式的优点是存储密度大，且插入、删除运算效率高。（09.栈和队列是操作上受限制的线性表。（t）10.队列是与线性表完全不同的一种数据结构。⑴II.队列是一种操作受限的线性表，凡对数据元素的操作仅限一端进行。（D12.栈和队列也是线性表。如果需要，可对它们屮的任一元素进行操作。⑴13.栈是限定仅在表头进行插入和表尾进行删除运算的线性表。⑴14.二叉树中每个结点有两个子结点，而对一般的树，则无此限制，所以，二叉树是树的特殊情形。（f）二叉树是有序树，树是无序的15二叉树是一棵结点的度最大为二的树。⑴子数有左右之分16赫夫曼树屮结点个数一定是奇

3、数。⑴17在二叉树的中序遍历序列中，任意一个结点均处在其左孩子结点的后面。（t）18假设B是--棵树，B'是对应的二叉树。则B的后根遍历相当于的后序遍历。（f）19.通常，二叉树的第i层上有2□个结点。（0至多有20.中序线索二叉树的优点是便于在中序下查找直接前驱结点和直接后继结点。（t）21二叉树的先序遍历序列屮，任意一个结点均处在其孩子结点的前面。⑴22由树结点的先根序列和后根序列可以唯一地确定一棵树。（t）23邻接多重表可以用以表示无向图，也可用以表示有向图。⑴无向图的链式存储结构24可从任意有向图中得到关于所有顶点的拓扑次序。（f）25有向图的十字链表是将邻接表和逆邻接表

4、合二为一的链表表示形式。（t）26关键路径是AOE网屮源点到汇点的最短路径。（f）最长路径27连通图G的生成树是一个包含G的所有n个顶点和n-1条边的子图。（f）有n-1条边的图不一定是生成树，要是连接这n个顶点的n-1条边28一个无向图的连通分量是其极大的连通子图。（t）29十字链表可以表示无向图，也可用以表示有向图。⑴冇向图的一种链式存储结构30邻接表可以表示有向图，也可以表示无向图。（t）31.二叉排序树的平均查找长度为0（logn）0（t）32.二叉排序树的最大查找长度与（LOG2N）同阶。⑴最好的情况logm33选用好的HASH函数可避免冲突。⑴34折半查找不适用于有序

5、链表的查找。⑴35.对于目前所知的排序方法，快速排序具有最好的平均性能。（t）36对于任何待排序序列来说，快速排序均快于冒泡排序。（f）37在最坏情况下，堆排序的吋间性能是O（nlogn）,比快速排序好⑴38快速排序具有最好的平均时间性能，它在任何时候的时间复杂度都是O（nlogn）。（f）39.字符串是数据对象特定的线性表。⑴40.空串与空格串是相同的。⑴41.对于一棵ni阶的B树.树中每个结点至多有m个关键字.除根之外的所有非终端结点至少有「m/2「个关键字。(f)“关键宁”应为“子树”42.当二叉排序树是一棵平衡二叉树时，其平均查找长度为O(log2n)o(t)43.广义表

6、的表头和表尾都是广义表。⑴44二维数组是其数据元素为线性表的线性表。⑴选择题。1从逻辑上可以把数据结构分成(c)。A.动态结构和静态结构B.顺序组织和链接组织C.线性结构和非线性结构D.基本类型和组合类型2线性表1_在(b)情况下适于使用链表结构实现。A.不需修改L的结构B.需不断对L进行删除、插入C.需经常修改L中结点值D.L中含有大量结点3带头结点的单链表L为空的判断条件是b。带头结点的循环链表L为空的判断条件是c。A.L==nullB.L->next==nullC.L->next==LD.L!=null4若顺序表中各结点的查找概率不等，则可用如卜策略提高顺序查找的效率：若找

7、到指定的结点，将该结点与其后继(若存在)结点交换位置，使得经常被查找的结点逐渐移至表尾。以下为据此策略编写的算法，请选择适当的内容，完成此功能。顺序表的存储结构为：typedefstruct{ElemType*elem;//数据元素存储空间，0号单元作监视哨intlength;//表长度}SSTablc;intsearch_seq(SSTableST,KeyTypekey){〃在顺序表ST中顺序查找关键字等于key的数据元素。〃若找到，则将该元素与其后继交换位置，并返回其在表中的