上海交通大学一九九八年硕士研究生入学考试试题 试题名称:数据结构和程序设计技术 试题编号:19 题一(20分)判断题:若认为下列命题正确,打“ˇ“,反之打“ 1、数据元素是数据的最小单位() 2、队列逻辑上是一个下端口和上端能增加又能减少的线性表 3、任何一个递归过程都可以转换成非递归过程。( 4、只有那种使用了局部变量的递归过程在转换成非递归过程时才必须使用栈() 5、数组可看成线性结构的一种推广,因此与线性表一样,可以对它进行插入、删除等操 作。() 6、两叉树是树的一种特殊情况() 7、在树中,如果从结点K出发,存在两条分别到达K,K”的长度相等的路径,由结点 K和k互为兄弟() 8、线索两叉树的优点是便于在中序遍历下,查找前趋和后继结点() 9、n个结点的两叉树有多种,其中树高最小的两叉树排序树是最佳的 10、最佳两叉排序树的任何子树都是最佳的() 11、设T为一棵平衡树,在其中插入一个结点N,然后立即删除该结点得到T1,T与T1 必定相同() 12、一个有向图的邻接表和逆邻接表中结点的个数可能不等。( 13、任何有向图的结点都可以排成拓扑排序,而且拓扑排序不唯一() 14、当改变网上某一关键路上任一关键活动后,必将产生不同的关键路径( 15、两分法插入排序所需比较次数与待排序记录的初始排列状态相关() 16、当待排序记录已经从小到大排序或者已经从大到小排序时,快速排序的执行时间最省 17、在索引顺序表中,实现分块查找,在等概率查找情况下,其平均查找长度不仅与表中 元素个数有关,而且与每块中元素个数有关() 18、在执行某个排序算法过程中,出现了排序码朝着最终排序序列相反方向移动,则该算上海交通大学一九九八年硕士研究生入学考试试题 试题名称：数据结构和程序设计技术 试题编号：１９ 题一（２０分）判断题：若认为下列命题正确，打““，反之打““ １、 数据元素是数据的最小单位（ ） ２、 队列逻辑上是一个下端口和上端能增加又能减少的线性表（ ） ３、 任何一个递归过程都可以转换成非递归过程。（ ） ４、 只有那种使用了局部变量的递归过程在转换成非递归过程时才必须使用栈（ ） ５、 数组可看成线性结构的一种推广，因此与线性表一样，可以对它进行插入、删除等操 作。（ ） ６、 两叉树是树的一种特殊情况（ ） ７、 在树中，如果从结点 K 出发，存在两条分别到达 K’，K”的长度相等的路径，由结点 K’和 k”互为兄弟（ ） ８、 线索两叉树的优点是便于在中序遍历下，查找前趋和后继结点（ ） ９、 n 个结点的两叉树有多种，其中树高最小的两叉树排序树是最佳的（ ） １０、最佳两叉排序树的任何子树都是最佳的（ ） １１、设 T 为一棵平衡树，在其中插入一个结点 N，然后立即删除该结点得到 T1，T 与 T1 必定相同（ ） １２、一个有向图的邻接表和逆邻接表中结点的个数可能不等。（ ） １３、任何有向图的结点都可以排成拓扑排序，而且拓扑排序不唯一（ ） １４、当改变网上某一关键路上任一关键活动后，必将产生不同的关键路径（ ） １５、两分法插入排序所需比较次数与待排序记录的初始排列状态相关（ ） １６、当待排序记录已经从小到大排序或者已经从大到小排序时，快速排序的执行时间最省 ( ) １７、在索引顺序表中，实现分块查找，在等概率查找情况下，其平均查找长度不仅与表中 元素个数有关，而且与每块中元素个数有关（ ） １８、在执行某个排序算法过程中，出现了排序码朝着最终排序序列相反方向移动，则该算