《数据结构》期中试题1.doc

20042005年第二学期08级信息班数据结构期中测试一、 填空题【每空1分 共25分】1、一个数据结构在计算机中 称为存储结构2、在线性结构中第一个结点 个前驱结点，其余每个结点 个前驱结点，最后一个结点 个后续结点，其余每个结点 个后继结点。3、对于顺序存储的栈，因为栈的空间是有限的，在进行 运算时，可能发生栈的上溢，在进行 运算时，可能发生栈的下溢。4、设根结点的层数为0，定义树的高度为树中层数最大的结点的层数加1。则高度为k的二叉树具有的结点数目，最少为 ,最多为 。6、在树结构里，有且仅有一个结点没有前驱，称为根。非根结点有且仅有一个 ,且存在一条从根到该结点的 。7、给出下列广义表运算的结果：head(p,h,w) tail(b,k,p,h) head(a,b),(c,d) ) head(tail(a,b),(c,d) 。8、链表相对于顺序表的优点有 和 操作方便9、栈、队列和数组都是 结构，可以在数组 位置插入和删除元素；对于栈只能在 插入和删除元素；对于队列只能在 插入和删除元素。10、有n个结点的二叉链表中，其中空的指针域为n+1.指向孩子的指针个数为 。11、深度为k的完全二叉树至多有 个结点，最多有 个结点。12、设有如图所示，则结点E的度为 ，层次为 ，双亲为 ，树的度为 ，树的深度为 。ABCDEFGHIJKLM13、现有按中序遍历的二叉树结果为：abc，问有 不同形态的二叉树可以得到这一遍历结果，试画出这些二叉树 。14、树的三种主要的遍历方法是：_、_和层次遍历。二、单项选择题（每题1分 共20分）1、串是一种特殊的线性表，其特殊性体现在 。A、可以顺序存储 B、数据元素是一个字符C、可以链式存储D、数据元素可以是多个字符 2、向一个栈顶指针为HS的链栈中将一个S指针所指的结点入栈，执行( )。 A、HS-next=s; B、S-next=HS-next;HS-next=s; C、S-next=HS-next;HS=s; D、S-next=HS;HS=HS-next; 3、评价一个算法时间性能的主要标准是( )。 A、算法易于调试 B、算法易于理解 C、算法的稳定性和正确性 D、算法的时间复杂度4、线性表的顺序存储结构是一种( )的存储结构。 A、随机存取 B、顺序存取 C、索引存取 D、散列存取5、从一个具有n个结点的单链表中查找其值等于x的结点时，在查找成功的情况下，需平均比较 个结点。A、nB、n/2C、（n-1）/2D、（n+1）/26、线性表采用链式存储时，结点的存储地址（ ） A必须是不连续的 B连续与否均可 C必须是连续的 D和头结点的存储地址相连续7、设数组datam作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出队操作后其头指针front值为（ ） Afront=front+1 Bfront=(front+1)%(m-1) Cfront=(front-1)%m Dfront=(front+1)%m8、栈和队列的共同特点是 。A、都是先进先出B、都是先进后出C只允许在端点处插入和删除元素 D、没有共同特点9、在一棵度为3的树中,度为3的结点个数为2,度为2 的结点个数为1,则度为0的结点个数为()A4 B5C6D710、判断一个循环队列QU(最多元素为m0个)为空的条件是 。A、QU-front= QU-rearB、QU-front！= QU-rearC、QU-front=( QU-rear+1)%m0D、QU-front！=（ QU-rear+1）%m011、树中所有结点的度等于所有结点数加（ ）A0 B1 C-1 D212、用单链表方式存储的线性表，存储每个节点需要两个域，一个是数据域，另一个是（）A 当前结点所在地址域 B 指针域C 空指针域 D 空闲域13、某个顺序表第一个元素的存储地址是100，每个元素的长度为2，则第6个元素的地址是（）A 110 B 108 C 100 D 12014、一个具有n个顶点的无向图最多有（） 条边A n B n（n-1） C n（n-1）/2 D 2n15、二叉树的第I层上最多含有结点数为（）A 2i B 2i-1-1 C 2i-1 D 2i-116、一颗具有n个节点的完全二叉树的树高度（深度）是（）A +1 B log2 n+1 C D log2 n+1 17、将递归转换成非递归算法通常需要使用 作为辅助存储结构A、队列B、栈C、链表D、树18、在需要经常查找结点的前驱与后继的场合中，使用( )比较合适。 A.单链表 B.双链表 C.顺序表 D.循环链表19、按照二叉树的定义，具有3个结点的二叉树有( )种。 A.3 B.4 C.5 D.6 20、已知某二叉树的后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是 A、acbedB、decabC、deabcD、cedba三、简答题（8分）设将整数1，2，3，4依次进栈，但只要出栈时栈非空，则可将出栈操作按任何次序夹入其中，请回答下述问题：(1)若入、出栈次序为Push(1), Pop(),Push(2),Push(3), Pop(), Pop( ),Push(4), Pop( ),则出栈的数字序列为何(这里Push(i)表示i进栈，Pop( )表示出栈)?(2) 能否得到出栈序列1423和1432?并说明为什么不能得到或者如何得到。四、根据要求完成下列个题（10分）1、 如图1所示画出此树的二叉链表的存储的二叉树。并画出该二叉树先序线索二叉树。2、如图2：写出该树的先序遍历序列，和后续遍历序列，并将该树转换成一颗对应的二叉树。图1 五、假设用于通信的电文由字符集a,b,c,d,e,f,g,h中的字母构成，这8个字母在电文中出现的概率分别为0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10.为这8个字母设计哈夫曼编码。（给出实现的过程）（7分）六、下列是先序遍历二叉树的非递归子程序，请阅读子程序，填充空格，使其成为完整的算法。void example(b) btree *b;ABCDEFGHI图2 btree *stack20, *p；int top;if (b!=null) top=1; stacktop=b;while (top0) p=stacktop; top-;printf(“%d”,p-data);if (p-rchild!=null)(1)_; (2)_;i