北京交通大学2001年数据结构考研试题

来源：时间：2007-06-06 13:36:19

2001年硕士研究生入学考试试卷（北方交大）(f)
一．选择题
1：以下数据结构中，哪一个是线形结构？
A）广义表 B）二叉树 C）稀疏矩阵 D）串
2：以下那一个术语与数据结构无关？
A）栈 B）哈希表 C）线索树 D）双向链表
3：有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列？
A）5 4 3 6 1 2 B）4 5 3 1 2 6 C）3 4 6 5 2 1 D）2 3 4 1 5 6
4：下述哪一条是顺序存储结构的优点？
A）存储密度大 B）插入运算方便
C）删除运算方便 D）可方便地用与各种逻辑结构的存储表示
5：下面关于串的的叙述中，哪一个是不正确的？
A）串是字符的有限序列
B）空串是空格构成的串
C）模式匹配是串的一种重要运算
D）串既可以采用顺序存储，也可以采用链式存储
6：由3 个结点可以构造出多少种不同的有向树？
A）2 B）3 C）4 D）5
7：有3 个结点可以构造出多少种不同的二叉树？
A）2 B）3 C）4 D）5
8：下列排序方法中，哪一个是稳定的排序二叉树？
A）直接选择排序 B）二分法插入排序
C）希尔排序 D）快速排序
9：对n 个记录文件进行堆排序，最坏情况下的执行时间是多少？
A）O（log2n） B）O（n） C）O（nlog2n） D）O（n*n）
10：对包含n 个元素的散列表进行检索，平均检索长度______________。
A）为O（log2n） B）为O（n）
C）为O（nlog2n） D）不直接依赖与n
11：下列哪一种图的的邻接矩阵？
A）有向图 B）无向图
CD）AOV网 D） AOE网
12：用链接方式存储的队列，在进行删除运算时_____________。
A）仅修改头指针 B）仅修改尾指针
C）头，尾指针都要修改 D）头，尾指针可能都要修改
13.下面过程是二叉树的何种遍历方法？
Procedure traverse(p:pointer);
Begin
If p<>nil
Then begin.
Process(p);
Traverse(p^.left);
Travrse(p^.right)
end
end
A)中序 B）前序 C)后序D)层次
14.下面有关线性表的叙述中，错误的是哪一个？
A)线性表采用顺序存储，必须占用一片连续的存储单元。
B)线性表采用顺序存储，便于进行插入和删除操作。
C)线性表采用链接存储，不必占用一片连续的存储单元。
D)线性表采用链接存储，便于插入和删除操作。
15．用直接插入排序方法对下面四个序列进行排序（由小到大），元素比较次数最少的是_。
A)94,32,40,90,80,46,21,69 B)32,40,21,46,69,94,90,80
C)21,32,46,40,80,69,90,94 C)90,69,80,46,21,32,94,40
16.设森林F中有三棵树，第一，第二棵树的结点个数分别为M1，M2，和M3。与森林F对应的二叉树根结点的右子树上的结点个数是___________。
A）M1 B）M1 M2 C）M3 D）M2 M3
17.下面关于B和B 树的叙述中，不正确的是_。
A）B树和B 树都是平衡的多叉树。
B）B树和B 树都可用于文件的索引结构。
C）B树和B 树都能有效地支持顺序检索。
D）B树和B 树都能有效地支持随机索。
18．对下列关键字序列用快速排序法进行排序时，速度最快的情是_.
A){21,25,5,17,9,23,30} B){25,23,30,17,21,5,9}
C){21,9,17,30,25,23,5} C){5,9,17,21,23,25,30}
19-20 题列描述:
散列表的地址间为0-17,散列函数为H(K)=K mod 17。采用线性探测法处理冲突，并将关键字序列26，25，72，38，8，18，59依次存储到散列表中。
19.元素59存在散列表中的地址是_。
A)8 B)9 C)10 D)11
20.存放元素59需要搜索的次数是_。
A）2 B）3 C）4 D）5
21.二叉树的先序遍历和中序遍历如下：
先序遍历：EFHIGJK
中序遍历： HFIEJKG
该二叉树的右子树的根是（）
A）E B)Ｆ　Ｃ）Ｇ　Ｄ）Ｈ
22.在完全二叉树中，若一个节点是叶节点，则它没（）。
A)左子结点 B) 右子结点　
　C)左子结点和右子结点　 D) 左子结点，右子结点和兄弟结点
23．在下列存储形式中，哪一个不是树的存储形式？（）
A) 双亲表示法 B) 孩子链表表示法Ｃ）孩子兄弟表示法 D) 顺序存储表示法
24．图中有关路径的定义是（）
A) 由顶点和相邻顶点序偶构成的边所形成的序列
B) 由不同顶点所形成的序列
C) 由不同边所形成的序列
D) 上述定义都不是
25．在二叉树结点的先序序列，中序序列和后序序列中，所有叶子结点的先后顺序（　　　）
A)都不相同　　　　　　　　　　B)　完全相同　
C)先序和中序相同，而与后序不同　D)　　中序和后序相同，而与先序不同
二．填空题
１．假设根结点的层数为１，具有ｎ各结点的二叉树的最大高度是＿＿＿＿。
２．在顺序表（８，１１，１５，１９，２５，２６，３０，３３，４２，４８，５０）　中，用二分（折半）法查找关键码值20，序做的关键码比较数为_______.
３．设下三角矩阵
|-a11 -|
| a21 a22 |
A = | a31 a32 a33 |
| ………………. |
|-An1 an2 an3 …… ann -|

如果按行序为主序降下三角元素A(I j) 存储在一个一维数组B[ 1……n(n 1)/2]中，对人一个三角矩阵元素Aij ,它在数组B中的下标为_______.
４．当现行标的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用_______存储结构。
５．队列是限制插入只能在表的一端，而删除在表的另一端进行的线性表，其特点是_____.
６．在一棵二叉树中，度为零的结点的个数为N0,度为2的结点的个数为N2,择优N0 =_____
７．设有字母序列{Q,D,F,X,A,P,N,B,Y,M,C,W},请写出按2路归并排序方法对该序列进行一趟扫描后的结果___________.
８．对于具有144 个纪录的文件，若采用分块查找法，且每块长度为8，则平均查找长度为_______.
９．线性表L=（a1,a2,……,an）用数组表示，假定删除表中任意元素的概率相同，则删除一个元素平均需要移动元素的个数是________.
三请设计算法将不带头结点的单链表就地逆置。
四请设计算法按层次顺序遍历二叉树。

结束

特别声明：①凡本网注明稿件来源为"原创"的，转载必须注明"稿件来源：育路网"，违者将依法追究责任；

②部分稿件来源于网络，如有侵权，请亚洲2019AV无码网站在线_波多野结衣免费一区视频_国产IGAO视频网在线观看_国产人妖乱国产精品人妖沟通解决。