得分评卷人 全真试题(五) 填空题(每空1分,共15分) 1.数据类型是一个 集合和定义在这个集合上的 的总 称 2.算法有五个特征它们是 、可行性、输入和输出。 3.一个线性表是n个元素的 4.在双向链表的结点中,除了含数据元素域外,还含有 个指针域 5.栈是限定仅在 进行插入和删除的线性表。不含元素的空表称 为 6.对于数组来说,一旦确定了它的 ,便可以为它分 配内存空间。 7.树的 包含一个数据元素及若干指向其子树的分支。 8.满二叉树是一棵深度为k且含有 个结点的二叉树。 9.在有向图G中,如果对于每一对顶点V和v1(V1≠V),从V到V和从v到v都存 在路径,则称G为 10.根据排序过程中涉及到的存储器不同,可将排序方法分为 和 二.单项选择题(在每个小题的四个备选答案中,选出一个正确的,并将正确 得分评卷人的答案的号码添在题干好的括号内,每小题1分,共10分 1.单链表结点的数据元素只能是哪一种? A.整型 B.字符串 C.任何数据类型 D.实型 2.若已有一个栈,输入序列为A,B,C,D,E,那么下面哪种序列不可能得到?() A. AbCde B. EDCBA C. BAEDO D. ECDBA 3.二叉树后序遍历的次序是什么? A根、左子树、右子树 B左子树、根、右子树 C左子树、右子树、根 D根、右子树、左子树 4.已给如图二叉树,它的中序遍历是哪一项? B A. ABECDE B. ABCDEF C. CBDAEF D. CDBFEA 5.在串的静态存储结构中,下面的哪一项不是紧缩格式的特点? A.节省空间 B.存取速度慢 C.存取的速度快 D.一个存取单元可能放多个字符
全真试题（五） 1．数据类型是一个 集合和定义在这个集合上的 的总 称。 2．算法有五个特征它们是 、 、可行性、输入和输出。 3．一个线性表是 n 个元素的 。 4．在双向链表的结点中，除了含数据元素域外，还含有 个指针域。 5．栈是限定仅在 进行插入和删除的线性表。不含元素的空表称 为 。 6．对于数组来说，一旦确定了它的 和 ，便可以为它分 配内存空间。 7．树的 包含一个数据元素及若干指向其子树的分支。 8．满二叉树是一棵深度为 k 且含有 个结点的二叉树。 9．在有向图 G 中，如果对于每一对顶点 Vi 和 Vj（Vi≠Vj），从 Vi 到 Vj 和从 Vj 到 Vi 都存 在路径，则称 G 为 。 10 ． 根 据 排 序 过 程 中 涉 及 到 的 存 储 器 不 同 ， 可 将 排 序 方 法 分 为 和 。 得分 评卷人 1．单链表结点的数据元素只能是哪一种？ （ ） A．整型 B．字符串 C．任何数据类型 D．实型 2．若已有一个栈，输入序列为 A，B，C，D，E，那么下面哪种序列不可能得到？（ ） A．ABCDE B．EDCBA C．BAEDC D．ECDBA 3．二叉树后序遍历的次序是什么？ （ ） A 根、左子树、右子树 B 左子树、根、右子树 C 左子树、右子树、根 D 根、右子树、左子树 4．已给如图二叉树，它的中序遍历是哪一项？ （ ） A．ABECDF B．ABCDEF C．CBDAEF D．CDBFEA 5．在串的静态存储结构中，下面的哪一项不是紧缩格式的特点？ （ ） A．节省空间 B．存取速度慢 C．存取的速度快 D．一个存取单元可能放多个字符 得分 评卷人 一．填空题（每空 1 分，共 15 分） 二．单项选择题（在每个小题的四个备选答案中，选出一个正确的，并将正确 的答案的号码添在题干好的括号内。每小题 1 分，共 10 分。） F E D B A C
6.已知完全二叉树有26个结点,则整棵二叉树有多少个度为1的结点?( A.1 0 C.2 不确定 7.已给下图,哪一项是该图的拓扑排序? A.1,2,3,4,5 B.1,3,2,4,5 C.1,2,4,3,5 D.1,2,3,5,4 8.在常用的哈希表处理冲突的方法中,哪一种方法容易产生“二次聚集”( A.开放定址法B.再哈希法C.链地址法E.都不会产生 9.直接插入排序的算法复杂性是多少? AO(n2) B O(nlogn) C O(n) D. O(ogn) 10串联文件的记录之间有何关系? A相继的两个物理记录的存储位置相邻 B.物理记录之间的次序由指针相联 C.两个逻辑相邻的记录物理上相邻 D.都不是 得分评卷人 三、简释名词(每小题3分,共15分) 1.线索二叉树 2.拓扑排序 3.关键路径 4.堆排序 直接存取文件 得分评卷人 四、简答题(每小题5分,共30分) 1.已给一个栈S,写出对S的所有操作。 2.以数据集{3,4,5,8,12,18}为叶结点的权值,构造一棵哈夫曼树 写出其邻接矩阵,并画出从顶点0"(2 3.已给右图 开始的最小生成树。 4.已给输入序列{17,60,29,38,42,50},按除留余数法,填写如下哈希表。其中除留余数 法的公式如下: H (key )=key %11 当出现冲突时,按H=(H(key)+1)MOD11的线性探测再散列的方法进行 地址|o123|45678910 5.已给有8个的无序序列:{49,38,65,97,76,13,27,49},画出建立初始堆的过程的示
6．已知完全二叉树有 26 个结点，则整棵二叉树有多少个度为 1 的结点？ （ ） A．1 B．0 C．2 D．不确定 7．已给下图，哪一项是该图的拓扑排序？ （ ） A．1，2，3，4，5 B．1，3，2，4，5 C．1，2，4，3，5 D．1，2，3，5，4 8．在常用的哈希表处理冲突的方法中，哪一种方法容易产生“二次聚集” （ ） A．开放定址法 B．再哈希法 C．链地址法 E．都不会产生 9．直接插入排序的算法复杂性是多少？ （ ） A．O（n 2） B. O（nlogn） C. O(n) D. O(logn) 10.串联文件的记录之间有何关系? A 相继的两个物理记录的存储位置相邻 B．物理记录之间的次序由指针相联 C．两个逻辑相邻的记录物理上相邻 D．都不是 得分 评卷人 1． 线索二叉树 2． 拓扑排序 3． 关键路径 4． 堆排序 5． 直接存取文件 得分 评卷人 1． 已给一个栈 S，写出对 S 的所有操作。 2． 以数据集{3，4，5，8，12，18}为叶结点的权值，构造一棵哈夫曼树。 3． 已给右图 写出其邻接矩阵，并画出从顶点① 开始的最小生成树。 4． 已给输入序列{17，60，29，38，42，50}，按除留余数法，填写如下哈希表。其中除留余数 法的公式如下： H（key）=key % 11 当出现冲突时，按 Hi=（H（key）+1）MOD 11 的线性探测再散列的方法进行。 地址 0 1 2 3 4 5 6 7 8 9 10 关键字 5． 已给有 8 个的无序序列：{49，38，65，97，76，13，27，49}，画出建立初始堆的过程的示 三、简释名词（每小题 3 分，共 15 分） 四、简答题（每小题 5 分，共 30 分） 5 1 2 3 4 5 1 3 2 4 6 12 2 3 4 6 7 5
例图。 6.已给无向图如下: 要求:写出该图从顶点① 开始的广度优先和深度优先搜索 序列,并画出该图的生成树 卷人五、综合题(用类c语言写出下列各题的算法。每小题10分共30分) 1.设栈用顺序结构实现,写出表示栈的数据结构,并实现如下操作: O void push stak(stack s, elemtp x) 2 void pop stack(stack s) 2.设用邻接矩阵表示一个有向图,编写一个算法,求一个结点的入度和出度的和。 3.设thrt是指向中序双向线索二叉树头结点的指针,写出从thrt起沿后继点进行遍历的算法
例图。 6． 已给无向图如下： 要求：写出该图从顶点① 开始的广度优先和深度优先搜索 序列，并画出该图的生成树 1． 设栈用顺序结构实现，写出表示栈的数据结构，并实现如下操作： ① void push_stak(stack s, elemtp x) ② void pop_stack(stack s) 2．.设用邻接矩阵表示一个有向图，编写一个算法，求一个结点的入度和出度的和。 3．设 thrt 是指向中序双向线索二叉树头结点的指针，写出从 thrt 起沿后继点进行遍历的算法。 得分 评卷人 五、综合题（用类 C 语言写出下列各题的算法。每小题 10 分共 30 分） 5 1 4 2 3 6