浙江理工大学935数据结构2008年考研真题考研试题

浙 江 理 工 大 学
二 OO 八年硕士学位研究生招生入学考试试题
考试科目： 数据结构 代码： 935
（*请考生在答题纸上答题，在此试题纸上答题无效）
一． 单项选择题(28 分)
1．如果某线性表中最常用的操作是取得第 i 个结点及其前驱，则采用_______存储方式
最节省时间。
A．单链表； B．双向链表； C．单循环链表； D．顺序表；
2．在数据结构中，逻辑上数据结构可分为 。
A．动态结构和静态结构； B．线性结构和非线性结构；
C．紧凑结构和非紧凑结构； D．内部结构和外部结构；
3．下列排序方法中， 是从未排序序列中依次挑选元素，并将其放入已排序序
列（初始时为空）的一端。
A．希尔排序； B．归并排序； C．选择排序； D．插入排序；
4．哈希查找中，k 个关键字具有同一哈希函数值，若用线性探测法把这 k 个关键字值存
入到哈希表中，至少要进行________探测。
A．k-1 次； B．k 次； C．k+1 次； D．k(k+1)/2 次；
5．下述哪个命题不成立_________。
A. m 阶 B_树每一个结点的子树个数都小于或等于 m；
B. m 阶 B_树每一个结点的子树个数都小于或等于m/2；
C. m 阶 B_树任何一个结点的左右子树的高度都相等；
D. m 阶 B_树具有 k 个子树的非叶子结点含有 k-1 个关键字；
6．假设 8 行 10 列的二维数组 a[1..8,1..10]分别以行序为主序和以列序为主序顺序存
储时，其首地址相同，那么以行序为主序时元素 a[3,5]的地址与以列序为主序时元素的
_________地址相同。
A．a[5,3]； B．a[8,3]； C．a[1,4]； D．A、B、C 均不对；
7．在有向图的邻接表存储结构中，顶点 v 在表结点中出现的次数等于_________。
A．顶点 v 的度； B．顶点 v 的出度； C．顶点 v 的入度； D．依附于顶点 v 的边数；
二．填空题(20 分)
1. 用 S 表示入栈操作，X 表示出栈操作，若元素入栈顺序为 1234,为了得到 1342 出栈顺
序，相应的 S、X 操作串为__ ___。
2．若二叉树 T 的前序遍历序列和中序遍历序列分别是：b,d,c,a,e,f 和 c,d,e,a,b,f，
则其后序遍历序列是_ ____。
第 1 页，共 2 页