《2017年北京语言大学计算机系统结构825数据结构与程序设计考研导师圈点必考题汇编.doc》由会员分享，可在线阅读，更多相关《2017年北京语言大学计算机系统结构825数据结构与程序设计考研导师圈点必考题汇编.doc（4页珍藏版）》请在金锄头文库上搜索。
1、2017年北京语言大学计算机系统结构825数据结构与程序设计考研导师圈点必考题汇编一、填空题1 以下是用类C 语言写山的算法，该算法将以二叉链表存储的二叉树中的叶结点按从左到右的顺序链成一个带头结点的双向循环链表，链接时，结点的Lchild 域作为前链域，指向结点的直接前驱，结点的Rchild 域作为后链域，指向结点的直接后继。算法中，使用一个顺序栈stack , 栈顶head 为双向循坏链表的头指针。 指针为top , P , t 为辅助指针，试填充算法中的空格，使算法完整。void leafchain（BiTree Abt）p=BiTree）malloc （sizeof （BiTNode
2、）; If （!p ）print（“OVERFLOWn”; exit （1）; head=p; top=0; if （bt ）top+; stacktop=bt; while （top ）t=stacktop; top-;if （it-Lchild & !t-Rchild） （1） ; （2） ; （3） ; else if（ （4） ）top+; stacktop= （5） ; if （ （6） ）top+; stacktop= （5） ; （8） ; （9） ; 【答案】p-Rchild=t:t-Lchild=p:p=t: t-Rchild!=null:t-Rchild: t-Lchild
3、!=null: t-Lchild: p-Rchild=head:head-Lchild=p2 在一个无向图的的邻接表中，若表结点的个数是m , 则图中边的条数是_条。【答案】m/2【解析】对于无向图，在邻接表中，如果存在n 条边，则会有2n 个表结点。3 文件可按其记录的类型不同而分成两类，即_和_文件。【答案】操作系统文件；数据库 4 高度为h 的堆中，最多有_元素，最少有_个元素。【答案】 当最后一层只有第 2 页，共 53 页【解析】当这个堆构成的是满二叉树时，元素的个数最多，元素个数为一个元素时，此时堆的元素个数最少，元素个数为 5 线性表用数组表示，假定删除表中任一元素的概率相同，则
4、删除一个元素平均需要移动元素的个数是_。【答案】（n 1）/2【解析】删除第一个元素需要移动n i 次，以此类推，删除最后一个元素需要移动0次。平 均次数为 6 在单链表中设置头结点的作用是_。【答案】方便运算 7 【答案】5 8 设二维数组A 的行和列的下标范围分别为【答案】 当其值为和每个元素占2个单元，按行优先顺处的元素为_。=_序存储，第一个元素的存储起始位置为b ，则存储位置为【解析】令这个元素的行标为i ，列标为j 。则它的存储位置是时，则i=2，j=3。9 在下面的程序段中，对X 的赋值语句的时间复杂度为_（表示为n 的函数）。 【答案】1（12）（123）?（l 2. n ）=
5、n（n 1）（n 2）/6，即 【解析】当i=l时，赋值语句就被执行了一次。当i=2时，赋值语句被执行了12次。当i=3时，赋值语句被执行了123次。可以推出赋值语句总共被执行了1（12）（123）（l 2. n ）=n（n 1）（n 2）/6次。10试利用下列栈和串的基本操作完成下述填空题。initstack （S ） 置S 为空找； push （S , X ） 元素X 入找； pop （S ） 出栈操作； gettop （S ） 返回栈顶元素； sempty （S ） 判找空函数； 置串 判串为空串；是否相等的函数；第 3 页，共 53 页length （st ） 返回串st 的长度； 返
6、回联接empty （st ） 判串空函数 之后的串；sub （S , i , 1） 返回S 中第i 个字符； 若给定的表达式的前缀式pre 正确，本过程求得和它相应的表达式exp 并返回true , 否则exp 为空串，并返回false 。已知原表达式中不包含括弧，opset 为运算符的集合。） 注意：毎个空格只填一个语句。 【答案】（1）（2）（3）（4）（5）（6）（7）exp （8）（9）exp （10）（11）（12）取栈顶操作符 操作符取出后，出栈将pre 的最后一个字符（操作数）加入到中缀式exp 的最后若ch 是操作数且栈非空，则形成部分中缀表达式栈S 初始化为空栈 串exp 初始化为空串 判取出字符是否是操作符如ch 是运算符，则入操作符栈s 判栈8是否为空若读出ch 是操作数且栈为空，则按出错处理 11索引顺序文件既可以顺序存取，也可以_存取。【答案】随机第 4 页，共 53 页 一、填空题考研试题
