江西师范大学数据结构2003年考研真题考研专业课真题
● 摘要
江西师范大学2003年硕士学位研究生入学考试
数据结构 试题
一、 选择题（每空2分，共20分）
1. 设一个栈的输入序列为A ，B ，C ，D ，则借助一个栈所得到的输出序列不可能是。
（1）A ，B ，C ，D （2）D ，C ，B ，A （3）A ，C ，D ，B （4）C ，A ，B ，D
2. 散列函数有一个共同性质，即函数值应按取其值域的每一个值。
（1）最大概率 （2）最小概率 （3）同等概率（4）平均概率
3. 直接插入排序在最好情况下的时间复杂度为。
（1）O(logN) (2) O(N) (3) O(N*logN) (4) O(N*N)
4. 表长为n 的顺序存储的线性表，当在任何位置上插入或删除一个元素的概率相等时，插入一个元素所需移动元素的平均个数为 ，删除一个元素所需移动元素的平均个数为 。
（1）（n-1)/2 (2) n (3) n+1 (4) n-1 (5) n/2 (6) (n+1)/2 (7) (n-2)/2
5. 下列序列中，是执行第一趟快速排序后得到的序列。
（1）[da,ax,eb,de,bb]ff[ha,gc] (2) [cd,eb,ax,da]ff[ha,gc,bb]
(3) [gc,ax,eb,cd,bb]ff[da,ha] (4) [ax,bb,cd,da]ff[eb,gc,ha]
6. 求最短路径的DIJKSTRA 算法的时间复杂度为。
（1）O （n) (2) O(n+e) (3) O(n*n) (4) O(n*e)
7. 在平衡二叉树中插入一个节点后造成了不平衡，设最低的不平衡节点为A ，并已知A 的左孩子的平衡因子为-1，右孩子的平衡因子为0，则应作 型调整以使其平衡。
(1) LL (2) LR (3) RL (4) RR
8. 若一棵二叉树具有10个度为2的结点，则该二叉树的度为0的结点个数是
(1) 9 (2) 11 (3) 12 (4)不确定
9. 若在线性表中采用折半查找法查找元素，该线性表应该
(1)元素按值有序 (2)采用顺序存储结构
(3)元素按值有序，且采用顺序存储结构
(4)元素按值有序，且采用链式存储结构
二、 判断题（每小题1分，共10分）
1. 一个栈的输入序列为1 2 3 …n ，其输出序列的第二个元素为n 的输出序列的个数有n-1种。( )
2. 二叉树中除叶节点外，任一节点x ，其左子树根节点的值该节点(x)的值，其右子树根节点的值 该节点(x)的值，则此二叉树一定是二叉排序树。( )
3. 有n 个节点的无向图，采用邻接矩阵表示，图中的边数等于邻接矩阵中非零元素之和的一半。( )
4. 外部排序是把外存文件调入内存，可利用内部排序的方法进行排序，因此排序所花的时间取决于内部排序的时间。( )
5. (101,88,46,70,34,39,45,58,66,10)是堆。( )
6. 哈夫曼树是带权路径长度最短的树，路径上权值较大的节点离根较近。( )
相关内容
相关标签