2008年硕士研究生入学考试数据结构与C语言程序设计(991）试题与答案.pdf

2008 年硕士研究生入学考试 数据结构与C 语言程序设计(991) 试题与答案 一、简答题（本题共20 分，每小题各5 分） 1 一般情况下，线性表可以采用哪几种存储结构？请分别叙述每一种存储结构的构造原理。 2 ．若5 个元素A,B,C,D,E 按此先后次序进入一个初始为空的堆栈，则在所有可能的出栈序 列中，第一个元素为C、且第二个元素为D 的出栈序列是哪几个？ 3 ．设散列函数为H(key)=key MOD 7 ，散列地址范围为[0..7]，采用线性探测再散列法处理 冲突。依次将序列(20, 11,13,21,34)中各关键字值插入初始为空的散列表以后，查找关键字值34， 需要依次与散列表中哪些关键字值进行比较？ 符号MOD 表示求模运算） 4 在设计快速排序法的非递归算法时，能否不用堆栈保存当前尚未参加排序的子序列的首、 尾位置，而改为其他机制？如队列。请说明理由。 二、综合题（本题共20 分，每小题各5 分） 1 已知在非空双向循环链表中由指针q 指的那个链结点的前面插入一个由指针p 指的链结 点的过程的前3 个动作对应的赋值语句依次为 “p-rlink=q; p-llink=q-llink; q-llink=p; ”，请 写出第4 个动作对应的语句。 2 ．请证明具有n 个叶结点的满二叉树的分支数为2(n -1)。 0 0 3 已知有向图 G=(V,E) ，其中，顶点的集合为 V= {v ,v ,v ,v ,v } ，弧的集合为 1 2 3 4 5 E= {v ,v ,v ,v ,v ,v ,v ,v ,v ,v ,v ,v } ，请写出G 的所有拓扑序列。 1 2 1 3 1 4 2 5 3 4 4 5 4 ．请画出依次插入关键字序列(6,7,10,14,9,2,13,5,4,11)中各关键字值以后的4 阶B-树。 三、算法设计题 （本题15 分） 请写一算法，依次输出通过键盘输入的一组整型数据中的最后k 个元素。 约定：以Ctrl+z 作为键盘输入的结束，并假设k 输入的数据元素的个数。 限制：算法中不允许使用数组，也不允许有计算输入数据个数的过程。 四、算法设计题 （本题20 分） 已知二叉树采用二叉链表存储结构，链结点构造为 lchild data rchild ，根结点指 针为T，请写一非递归算法，判断该二叉树是否为二叉排序树。若是二叉排序树，算法返回1， 否则，返回0。 五、单项选择题 （本题共20 分，每小题各2 分） 1．在下面给出的四个选项中，值为1 的表达式是 。 A 1- \0 ’ B 1- 0’ C 1’-0 D \0’- 0’ 2 对于条件表达式(E)?(x++):(x--) ，其中的表达式E 等价于 。 A E==0 B E== 1 C E !=0 D E != 1 3 ．以下语句中存在语法错误的是 。 A char *S[]={“right?”}; B char S[][20]={“right?”}; 1 C char *S[6]; S[1]= “right?”; D char S[6][20]; S[1]= “right?”; 4 ．若变量a,b 已经正确定义并赋值，以下符合C 语言语法规则的表达式是 。 A a+ 1=y B ++a,b=a-- C a=a+ 10=a+b D double(a)/ 10 5 ．设已有定义 “int x; float y; ”，执行语句“scanf(“%2d%f”,x,y); ”时，若从键盘输入 数据876 543.0CR，x 和y