1、 1 顺序存储结构中数据元素之间的逻辑关系是由（存储位置）表示的。 2 若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（顺序表）存储方式最节省时间。 3. 执行下面程序段时，语句 S 的执行次数为 (n+1)(n+2)/2 4 对于线性表最常用的操作是查找指定序号的元素和在末尾插入元素，则选择（顺序表）存储方式最节省时间。 5 在长度为 n 的顺序表的第 i 个位置上插入一个元素（ 1 i n+1），元素的移动次数为：n i + 1 6非空的单循环链表由头指针 head 指示， p 指针指向链尾结点的条件是（ p-next=head）。 7下列选项中，（可以随
2、机访问表中的任意元素）是链表不具有的特点。 8.假设有如下遗产继承规则：丈夫和妻子可以相互继承遗产；子女可以继承父亲或母亲的遗产；子女间不能相互继承。则表示该遗产继承关系的最合适的数据结构应该是（图）。 9栈和队列的共同点是（只允许在端点处插入和删除元素） 10一个队列的入队序列是 a,b,c,d，则该队列的出队序列是（ a,b,c,d）。 11.带头结点的单链表 h 为空的判断条件是（ h-next= NULL）。 12. 下面关于串的叙述中，哪一个是不正确的？（空串是由空格构成的串） 13判断一个最大容量为 m 的循环队列 Q 为空的条件是（ Q-front=Q-rear ）。 14在一棵
3、树中，每个节点最多有（ 1）前驱节点？ 15已知完全二叉树的第 7 层有 10 个叶子结点，则整个二叉树中结点数为（ 73）。 16. 下面的说法中，不正确的是（稀疏矩阵中大量值为零的元素分布有规律，因此可以采用三元组表方法存储） 17在一棵深度为 k 的满二叉树中，结点总数为（ 2k-1） 18数组 A 中，每个元素的长度 为 3 个字节，行下标从 1到 5，列下标从 1 到 6，从首地址SA 开始连续存放在存储器内，存放该数组至少需要的字节数是（ 90）。 19. 如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有的顶点，则该图一定是（连通图）。 20. 设计一个判别表达式中左右括
4、号是否配对的算法，采用（栈）数据结构最佳 21设无向图的顶点个数为 n，则该图最多有 n(n-1)/2 条边。 22下面关于求关键路径的说法不正确的是（一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的差）。 23.最小生成树指的是（连通网中所有生成树中权值之和为最小的生成树） 。 24.已知一个有向图的邻接矩阵表示，要删除所有从第 i 个结点发出的边，应该：（将邻接矩阵的第 i 行元素全部置为 0） 25适用于折半查找的表的存储方式及元素排列要求为 (顺序方式存储，元素有序 ) 26下面给出的四种排序法中 (堆排序 )排序法是不稳定性排序法。 27.静态查找与动态
5、查找的根本区别在于（施加在其上的操作不同）。 28.顺序查找法适合于存储结构为 (顺序存储结构或链式存储结构 )的线性表。 29.下列四种排序中（归并排序）的空间 复杂度最大。 30快速排序在（待排序的数据已基本有序）情况下最不利于发挥其长处。 1线性表的特点是每个元素都有一个前驱和一个后继。 2若一个广义表的表头为空表，则此广义表亦为空表。 3数组元素的下标值越大，存取时间越长。 4.线性结构只能用顺序结构来存放，非线性结构只能用非顺序结构来存放。 5.对于一棵非空二叉树，它的根结点作为第一层，则它的第 i 层上最多能有 2i-1 个结点。 6.用二叉链表法存储包含 n 个结点的二叉树，结点
6、的 2n 个指针区域中有 n+1 个为空指针。 7广义表（ a,b,c,d）的表尾是（ b,c,d）。 8当一棵具有 n 个叶子结点的二叉树的 WPL 值为最小时，称其树为 Huffman 树，且其二叉树的形状必是唯一的。 9树与二叉树是两种不同的树型结构。 10.完全二叉树中，若一个结点没有左孩子，则它必没有右孩子。 11.在 AOV 网络中如果存在环，则拓扑排序不能完成。 12.每种数据结构都具备三个基本操作：插入、删除和查找。 13完全二叉树中，若一个结点没有左孩子，则它必是树叶。 14通常使用队列来处理函数或过程的调用。 15对一个 堆，按二叉树层次进行遍历可以得到一个有序序列。 16
7、.如果一个串中的所有字符均在另一个串中出现，则说前者是后者的子串。 17.给定一棵树，可以找到唯一的一棵二叉树与之对应。 18.在一个大根堆中，最小元素不一定在最后。 19.内排序中的快速排序方法，在任何情况下均可得到最快的排序效果。 20由树转换成二叉树，其根结点的右子树总是空的。 1在线性结构、树状结构和图结构中，数据元素之间分别存在着一对一、一对多和多对多联系。 2.在循环单链表 L（ L 为头指针）中，指针 p 所指结点为表尾结点 的条件是 (p-next=L) 3. 若用一个大小为 6 的数组来实现循环队列，且当前的 rear 和 front 的值分别为 0 和 3，当从队列中删除一
8、个元素后， front 的值为 4，再加入两个元素后， rear 的值为 2。 4.已知数组 A0.5,0.7的每个元素占 6 个字节存储，将其按行优先次序存储在起始地址为 1000 的连续的内存单元中，则数组 A 的体积（即存储量）为 288 个字节，元素 A1， 4的起始地址为 1072。 5.广义表 (a,b),(c,d)的表头是 (a,b)，的表尾是 (c,d)。 6.有三个结点的二 叉树共有 5 种形态。 7按 13、 24、 37、 90、 53 的次序形成平衡二叉树，则该平衡二叉树的高度是 _3,其根为 _24,在等概率下，查找成功的时候平均查找长度为 11/5。 8假设一棵二叉
9、树的先序遍历序列为 ABCDEF,中序遍历序列为 BCDAFE。则该二叉树的后序遍历序列为 (DCBFEA)。 1数据结构中评价算法的两个重要指标是（ 1）时间复杂度（ 2）空间复杂度 2数据的逻辑结构主要分为（ 1）集合 （ 2）线性结构 （ 3）树形结构 （ 4）图状结构（网状结构）四种基本类型。 3设有一个空栈，现 有输入序列为 1、 2、 3、 4、 5， 经过 push， push， pop， push， pop，push， push 后，输出序列是 _2、 3_，栈顶元素是 _5_。 4串是一种特殊的线性表，其特殊性体现在数据元素的类型是一个字符 _。 6在二叉树中，指针 p 所指
10、结点为叶子结点的条件是 （ p-lchild=NULL p= L-next; L-next=NULL; while(p ) q=p-next; p-next=L-next; L-next=p; p=q; 2.编写递归算法，将二叉树中所有结点的左、右子树相互交换。并给出算法中使用的二叉树的存储结构（数据类型）的定义。 typedef struct bitnode char data； struct bitnode *lchild， *rchild； *BiTree； void exchange(BiTree T) BiTree p; if(T) p=T-lchild; T-lchild= T-r
11、child; T-rchild=p; exchange (T-lchild); exchange (T-rchild); 3. 编写递归算法，求二叉树的深度。并给出你在算法中使用的二叉树的存储结构（数据类型）的定义。 typedef struct bitnode char data； struct bitnode *lchild， *rchild； bitnode， *bitree； int heightbt(bitree t) int n1,n2; if(!t) return(0); else n1= heightbt(t-lchild); n2= heightbt(t-rchild); return(n1n2?n1+1:n2+1);
