中科院计算机技术研究所数据结构-2000考研试题研究生入学考试试题考研真题
● 摘要
中科院计算机技术研究所2000年硕士研究生入学试题
考试科目：数据结构
一、选择题（20分）
1．下述函数中渐近时间最小的是（ ）。
A ） T1(n)=nC ）
T3(n)= -1000+1000. B）T2(n)=n D ）T4(n)=2n -1000-1000
2．下述编码中哪一个不是前缀码（ ）。
A ）。（00，01，10，11） B ）。（0，1，00，11）
C ）。（0，10，110，111） D ）。（1，01，000，001）
3．当各边上的权值（ ）时，BFS 算法可用来解决单源最短路径问题
A ）均相等 B ）均互不相等 C ）不一定相等
4，在含有n 个关键字的小根堆（堆顶元素最小）中，关键字最大的记录有可能存储在（ ）位置上。
A ）n/2 B ）n/2-1 C ）1 D ）n/2+2
5．若要求排序是稳定的，且关键字为实数，则在下列排序方法中应选（ ）为宜。
A ）直接插入 B ）直接选择 C ）堆 D ）快速排序 E ）基数排序
6．在一棵含有n 个关键字的m 阶B ——树中进行查找，至多读盘（ ）次。
A ）B ）1+C ）1+D ）
1+
7．下述文件中适合于磁带存储的是（ ）。
A ）顺序文件 B ）索引文件 C ）散列文件 D ）多关键字文件
8．“typdef int(*F) (char , int)：表示F 是一个（ ）。
A ）函数 B ）指针 C ）指针类型 D ）函数指针类型
9．在快速排序中，要使最坏情况的空间复杂度为O() 则要对快速排序作（ ）修改。
A ）划分元素为三者取中 B ）采用表排序
C ）先排最小集合 D ）先排大集合
10．设栈的输入序列是1，2，3，4，则（ ）不可能是其出栈序列：
A ）1，2，4，3， B ）2，1，3，4， C ）1，4，3，2，
D ）4，3，1，2， E ）3，2，1，4，
1